2008 AMatrixAlignApprForLinkPred
- (Scripps et al., 2008) ⇒ Jerry Scripps, Pang-Ning Tan, Feilong Chen, Abdol-Hossein Esfahanian. (2008). “A Matrix Alignment Approach for Link Prediction.” In: Proceedings of the 19th International Conference on Pattern Recognition (ICPR 2008).
Subject Headings: Link Prediction Task, Adjacency Matrix, Similarity Matrix.
Notes
Cited By
- Cited by ~1 (self) http://scholar.google.com/scholar?cites=3536309316814552762
Quotes
Abstract
This paper introduces a new discriminative learning technique for link prediction based on the matrix alignment approach. Our algorithm automatically determines the most predictive features of the link structure by aligning the adjacency matrix of a network with weighted similarity matrices computed from node attributes and neighborhood topological features. Experimental results on a variety of network data have demonstrated the effectiveness of this approach.
1 Introduction
Link prediction is a technique used to predict the formation of ties within a network. It can be used to recommend new relationships such as friends in a social network or to uncover previously unknown links such as regulatory interactions among genes. More generally, the link prediction problem can be formulated as a binary classification problem [4, 5] — given a node pair, we seek to accurately predict whether there is an edge between them based on their node attributes, neighborhood structure, or other properties of the network topology. Such a problem can be approached in two ways: (1) using a generative approach, where the focus is on learning a model of the joint probability density of the nodes, links, subgroups, etc., and then make a prediction by using Bayes rule [2, 6, 8], or (2) using a discriminative approach, which directly learns a target function that will map an input node pair to its class [3, 4, 5]. In this paper we introduce a new discriminative learning technique for link prediction based on the matrix alignment approach.
We assume that the node attributes contain information needed to make the prediction but that the links would help us to prioritize the attributes. For example, in social networks, people may become linked (friends, relatives, coworkers, accomplices, etc.) because they have shared some common characteristics or interest. While many attributes about a person may be known (e.g., eye color, height, books they like to read, school they attend, etc), it is a small set of them that are important when befriending. The challenge is to determine which subset of attributes are important to establish the links observed in a network. A link between two persons may also be determined by examining their existing ties (e.g. do they have common friends or are they popular figures?) It is not our purpose here to debate the merits of using attributes versus neighborhood topological features [5]. Indeed, what may be appropriate for one data set may not be for another. The objective of this paper is to present a flexible framework that allows us to identify the relevant attributes or topological features that are most well-aligned with the link structure.
4 Conclusions and Future Work
We presented a discriminative approach to predicting links that aligns attributes and link metrics to the link structure. The two general approaches to link prediction so far have been either generative or discriminative. While each approach has its advantages and disadvantages, it has been suggested [7] in general ”that discriminative classifiers are almost always to be preferred to generative ones”. Our approach has the advantage of being flexible, allowing many extensions to the framework. The extensions that were presented in this paper were to incorporate topological data and to make use of regularization to avoid overfitting. This framework can also be extended in other ways, e.g., by using nonlinear kernels as the similarity function.
References
- [1] R. Duda, P. Hart, and D. Stork. Pattern Classification. John Wiley & Sons, New York, 2000.
- [2] L. Getoor and C. P. Diehl. Link mining: a survey. SIGKDD Explorations, 2005.
- [3] M. Al Hasan, V. Chaoji, S. Salem, and M. Zaki. Link prediction using supervised learning. SDM’06: Workshop on Link Analysis, Counter-terrorism and Security, 2006.
- [4] H. Kashima and N. Abe. A parameterized probabilistic model of network evolution for supervised link prediction. ICDM, 2006.
- [5] D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. CIKM, 2003.
- [6] J. Neville and D. Jensen. Leveraging relational autocorrelation with latent group models. ICDM, 2005.
- [7] A. Ng and M. Jordan. On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes. Advances in Neural Information Processing Systems, 2002.
- [8] B. Taskar, P. Abbeel, and Daphne Koller. Discriminative probabilistic models for relational data. UAI02, 2002.
,