Article

Link prediction via matrix factorization

Authors:

Aditya Krishna Menon,

Charles ElkanAuthors Info & Claims

ECMLPKDD'11: Proceedings of the 2011th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part II

Pages 437 - 452

https://doi.org/10.1007/978-3-642-23783-6_28

Published: 05 September 2011 Publication History

Abstract

We propose to solve the link prediction problem in graphs using a supervised matrix factorization approach. The model learns latent features from the topological structure of a (possibly directed) graph, and is shown to make better predictions than popular unsupervised scores. We show how these latent features may be combined with optional explicit features for nodes or edges, which yields better performance than using either type of feature exclusively. Finally, we propose a novel approach to address the class imbalance problem which is common in link prediction by directly optimizing for a ranking loss. Our model is optimized with stochastic gradient descent and scales to large graphs. Results on several datasets show the efficacy of our approach.

References

[1]

Adamic, L.A., Adar, E.: Friends and neighbors on the web. Social Networks 25(3), 211-230 (2003)

[2]

Agarwal, D., Chen, B.-C.: Regression-based latent factor models. In: KDD 2009, pp. 19-28. ACM, New York (2009)

Digital Library

[3]

Airoldi, E., Blei, D.M., Fienberg, S.E., Xing, E.P.: Mixed membership stochastic blockmodels. In: NIPS, pp. 33-40 (2008)

Digital Library

[4]

Batagelj, V., Ferligoj, A., Doreian, P.: Generalized blockmodeling. Informatica (Slovenia) 23(4) (1999)

[5]

Beck, N., King, G., Zeng, L.: Improving quantitative studies of international conflict: A conjecture. American Political Science Review 94(1), 21-36 (2000)

[6]

Chawla, N.V., Japkowicz, N., Kotcz, A.: Editorial: special issue on learning from imbalanced data sets. SIGKDD Explor. Newsl. 6, 1-6 (2004)

Digital Library

[7]

Chen, H., Li, X., Huang, Z.: Link prediction approach to collaborative filtering. In: Joint Conference on Digital Libraries, vol. 7, pp. 141-142 (2005)

Digital Library

[8]

Chu, W., Park, S.-T.: Personalized recommendation on dynamic content using predictive bilinear models. In: WWW 2009, pp. 691-700. ACM, New York (2009)

Digital Library

[9]

Doppa, J.R., Yu, J., Tadepalli, P., Getoor, L.: Learning algorithms for link prediction based on chance constraints. In: Balcázar, J.L., Bonchi, F., Gionis, A., Sebag, M. (eds.) ECML PKDD 2010. LNCS, vol. 6321, pp. 344-360. Springer, Heidelberg (2010)

Digital Library

[10]

Dunlavy, D.M., Kolda, T.G., Acar, E.: Temporal link prediction using matrix and tensor factorizations. ACM Transactions on Knowledge Discovery from Data (in Press, 2011)

Digital Library

[11]

Ruben Gabriel, K.: Generalized bilinear regression. Biometrika 85, 689-700 (1998)

[12]

Gantner, Z., Drumond, L., Freudenthaler, C., Rendle, S., Schmidt-Thieme, L.: Learning attribute-to-feature mappings for cold-start recommendations. In: ICDM, pp. 176-185 (2010)

Digital Library

[13]

Ghosn, F., Palmer, G., Bremer, S.: The MID3 data set, 1993-2001: Procedures, coding rules, and description. Conflict Management and Peace Science 21, 133-154 (2004)

[14]

Hasan, M.A., Chaoji, V., Salem, S., Zaki, M.: Link prediction using supervised learning. In: SDM Workshop on Link Analysis, Counterterrorism and Security (2006)

[15]

Hoff, P.: Modeling homophily and stochastic equivalence in symmetric relational data. In: NIPS (2007)

Digital Library

[16]

Hoff, P.D.: Bilinear mixed effects models for dyadic data. Journal of the American Statistical Association 32, 100-286 (2003)

[17]

Hofmann, T., Puzicha, J., Jordan, M.I.: Learning from dyadic data. In: NIPS II, pp. 466-472. MIT Press, Cambridge (1999)

Digital Library

[18]

Joachims, T.: Optimizing search engines using clickthrough data. In: KDD 2002, pp. 133-142. ACM, New York (2002)

Digital Library

[19]

Kashima, H., Kato, T., Yamanishi, Y., Sugiyama, M., Tsuda, K.: Link propagation: A fast semi-supervised learning algorithm for link prediction. In: SDM, pp. 1099-1110 (2009)

[20]

Koren, Y., Bell, R., Volinsky, C.: Matrix factorization techniques for recommender systems. Computer 42, 30-37 (2009)

Digital Library

[21]

Lichtenwalter, R., Lussier, J.T., Chawla, N.V.: New perspectives and methods in link prediction. In: KDD, pp. 243-252 (2010)

Digital Library

[22]

Lu, L., Zhou, T.: Link prediction in complex networks: A survey (2010), http://arxiv.org/abs/1010.0725

[23]

Menon, A.K., Elkan, C.: A log-linear model with latent features for dyadic prediction. In: ICDM (2010)

Digital Library

[24]

Miller, K., Griffiths, T., Jordan, M.: Nonparametric latent feature models for link prediction. In: NIPS, vol. 22, pp. 1276-1284 (2009)

Digital Library

[25]

Mørup, M., Schmidt, M.N., Hansen, L.K.: Infinite multiple membership relational modeling for complex networks. In: NIPS Workshop on Networks Across Disciplines in Theory and Application (2010)

[26]

Raymond, R., Kashima, H.: Fast and scalable algorithms for semi-supervised link prediction on static and dynamic graphs. In: Balcázar, J.L., Bonchi, F., Gionis, A., Sebag, M. (eds.) ECML PKDD 2010. LNCS, vol. 6323, pp. 131-147. Springer, Heidelberg (2010)

Digital Library

[27]

Rendle, S., Freudenthaler, C., Gantner, Z., Lars, S.-T.: BPR: Bayesian personalized ranking from implicit feedback. In: UAI 2009, pp. 452-461. AUAI Press, Arlington (2009)

Digital Library

[28]

Roweis, S.: NIPS dataset (2002), http://www.cs.nyu.edu/~roweis/data.html

[29]

Schein, A.I., Popescul, A., Ungar, L.H., Pennock, D.M.: Methods and metrics for cold-start recommendations. In: SIGIR 2002, pp. 253-260. ACM, New York (2002)

Digital Library

[30]

Sculley, D.: Large scale learning to rank. In: NIPS Workshop on Advances in Ranking (2009)

[31]

Tsuda, K., Noble, W.S.: Learning kernels from biological networks by maximizing entropy. Bioinformatics 20, 326-333 (2004)

Digital Library

[32]

Vert, J.-P., Jacob, L.: Machine learning for in silico virtual screening and chemical genomics: New strategies. Combinatorial Chemistry & High Throughput Screening 11(8), 677-685 (2008)

[33]

Wang, C., Satuluri, V., Parthasarathy, S.: Local probabilistic models for link prediction. In: ICDM, pp. 322-331 (2007)

Digital Library

[34]

Ward, M.D., Siverson, R.M., Cao, X.: Disputes, democracies, and dependencies: A reexamination of the Kantian peace. American Journal of Political Science 51(3), 583-601 (2007)

[35]

Watts, D.J., Strogatz, S.H.: Collective dynamics of "small-world" networks. Nature 393(6684), 440-442 (1998)

[36]

Yamanishi, Y., Vert, J.-P., Kanehisa, M.: Supervised enzyme network inference from the integration of genomic data and chemical information. In: ISMB (Supplement of Bioinformatics), pp. 468-477 (2005)

Digital Library

[37]

Yang, S.H., Long, B., Smola, A., Sadagopan, N., Zheng, Z., Zha, H.: Like like alike - joint friendship and interest propagation in social networks. In: WWW (2011)

Digital Library

[38]

Zhu, S., Yu, K., Chi, Y., Gong, Y.: Combining content and link for classification using matrix factorization. In: SIGIR 2007, pp. 487-494. ACM, New York (2007)

Digital Library

[39]

Zhu, X., Ghahramani, Z.: Learning from labeled and unlabeled data with label propagation. Technical report, CMU (2002)

Cited By

Yao KLi W(2024)Asymmetric Learning for Graph Neural Network based Link PredictionACM Transactions on Knowledge Discovery from Data10.1145/364034718:5(1-18)Online publication date: 10-Jan-2024
https://dl.acm.org/doi/10.1145/3640347
Li JShomer HMao HZeng SMa YShah NTang JYin DOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Evaluating graph neural networks for link predictionProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666291(3853-3866)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666291
Ramezani MAhadinia AZiaei Bideh ARabiee H(2023)Joint Inference of Diffusion and Structure in Partially Observed Social Networks Using Coupled Matrix FactorizationACM Transactions on Knowledge Discovery from Data10.1145/359923717:9(1-28)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3599237
Show More Cited By

Link prediction via matrix factorization
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Link prediction via matrix factorization
ECML PKDD'11: Proceedings of the 2011 European conference on Machine learning and knowledge discovery in databases - Volume Part II

We propose to solve the link prediction problem in graphs using a supervised matrix factorization approach. The model learns latent features from the topological structure of a (possibly directed) graph, and is shown to make better predictions than ...
Relational Topic Factorization for Link Prediction in Document Networks
Algorithms and Models for the Web Graph
Abstract
Link prediction is one of the fundamental problems in complex networks. In this paper, we focus on link prediction in document networks, in which nodes are text documents. We propose the relational topic factorization model (RTF), a model that ...
Co-manifold Matrix Factorization
ICCPR '20: Proceedings of the 2020 9th International Conference on Computing and Pattern Recognition

Matrix factorization plays a fundamental role in collaborative filtering. In collaborative filtering setting, the rating matrix R is very sparse. Thus, infinite number of matrices can fit the observed entries in the rating matrix. Without additional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ECMLPKDD'11: Proceedings of the 2011th European Conference on Machine Learning and Knowledge Discovery in Databases - Volume Part II

September 2011

676 pages

ISBN:9783642237829

Editors:
Dimitrios Gunopulos
Department of Informatics and Telecommunications, University of Athens, Greece
,
Thomas Hofmann
Google Switzerland GmbH, Zurich, Switzerland
,
Donato Malerba
Department of Computer Science, University of Bari "Aldo Moro", Bari, Italy
,
Michalis Vazirgiannis
Deptartment of Informatics, Athens University of Economics and Business, Greece

Sponsors

Pascal2 Network: Pascal2 Network
Xerox
Google Inc.
COST/MOVE: COST/MOVE
Yahoo! Labs

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 05 September 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

74
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yao KLi W(2024)Asymmetric Learning for Graph Neural Network based Link PredictionACM Transactions on Knowledge Discovery from Data10.1145/364034718:5(1-18)Online publication date: 10-Jan-2024
https://dl.acm.org/doi/10.1145/3640347
Li JShomer HMao HZeng SMa YShah NTang JYin DOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Evaluating graph neural networks for link predictionProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666291(3853-3866)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666291
Ramezani MAhadinia AZiaei Bideh ARabiee H(2023)Joint Inference of Diffusion and Structure in Partially Observed Social Networks Using Coupled Matrix FactorizationACM Transactions on Knowledge Discovery from Data10.1145/359923717:9(1-28)Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1145/3599237
Xu EYu ZSun ZGuo BYao L(2023)Modeling Within-Basket Auxiliary Item Recommendation with Matchability and UbiquityACM Transactions on Intelligent Systems and Technology10.1145/357415714:3(1-19)Online publication date: 13-Apr-2023
https://dl.acm.org/doi/10.1145/3574157
Lapid SKagan DFire M(2023)Co-Membership-based Generic Anomalous Communities DetectionNeural Processing Letters10.1007/s11063-022-11103-155:5(5619-5651)Online publication date: 5-Jan-2023
https://dl.acm.org/doi/10.1007/s11063-022-11103-1
Yang JWu Y(2023)A link prediction method based on compressed sensing for social networksApplied Intelligence10.1007/s10489-023-05060-y53:23(29300-29318)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s10489-023-05060-y
Zhao ZLuo LPan SNguyen QGong C(2023)Towards Few-Shot Inductive Link Prediction on Knowledge Graphs: A Relational Anonymous Walk-Guided Neural Process ApproachMachine Learning and Knowledge Discovery in Databases: Research Track10.1007/978-3-031-43418-1_31(515-532)Online publication date: 18-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-43418-1_31
Costa GManco GOrtale R(2022)A Generative Bayesian Model for Item and User Recommendation in Social Rating Networks with Trust RelationshipsMachine Learning and Knowledge Discovery in Databases10.1007/978-3-662-44848-9_17(258-273)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-662-44848-9_17
Yin JGao LZhang Z(2022)Scalable Nonnegative Matrix Factorization with Block-wise UpdatesMachine Learning and Knowledge Discovery in Databases10.1007/978-3-662-44845-8_22(337-352)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-662-44845-8_22
Phukon BAnil ASingh SSarmah P(2021)Synonymy Expansion Using Link Prediction Methods: A Case Study of Assamese WordNetACM Transactions on Asian and Low-Resource Language Information Processing10.1145/346796621:1(1-21)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3467966
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents