Loading [MathJax]/extensions/MathMenu.js
Line Graph Neural Networks for Link Prediction | IEEE Journals & Magazine | IEEE Xplore

Line Graph Neural Networks for Link Prediction


Abstract:

We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. With the advances of deep learning, current lin...Show More

Abstract:

We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. With the advances of deep learning, current link prediction methods commonly compute features from subgraphs centered at two neighboring nodes and use the features to predict the label of the link between these two nodes. In this formalism, a link prediction problem is converted to a graph classification task. In order to extract fixed-size features for classification, graph pooling layers are necessary in the deep learning model, thereby incurring information loss. To overcome this key limitation, we propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task. Experimental results on fourteen datasets from different applications demonstrate that our proposed method consistently outperforms the state-of-the-art methods, while it has fewer parameters and high training efficiency.
Published in: IEEE Transactions on Pattern Analysis and Machine Intelligence ( Volume: 44, Issue: 9, 01 September 2022)
Page(s): 5103 - 5113
Date of Publication: 14 May 2021

ISSN Information:

PubMed ID: 33989153

Funding Agency:

References is not available for this document.

1 Introduction

Link prediction models are used to learn the distribution of links in graphs and predict the existence of potential links [1], [2], [3], [4]. In many real-world applications, the input data is represented as graphs, and link prediction models can be applied to tasks like friend recommendation in social networks [5], product recommendation in e-commerce [6], [7], [8], knowledge graph completion [9], protein interaction analysis [10], and metabolic network reconstruction [11].

Select All
1.
D. Liben-Nowell and J. Kleinberg, "The link-prediction problem for social networks", J. Amer. Soc. Inf. Sci. Technol., vol. 58, no. 7, pp. 1019-1031, 2007.
2.
M. Schlichtkrull, T. N. Kipf, P. Bloem, R. Van Den Berg, I. Titov and M. Welling, "Modeling relational data with graph convolutional networks", Proc. Eur. Semantic Web Conf., pp. 593-607, 2018.
3.
M. Al Hasan, V. Chaoji, S. Salem and M. Zaki, "Link prediction using supervised learning", Proc. SDM: Workshop Link Anal. Counter-Terrorism Secur., pp. 798-805, 2006.
4.
L. Lü and T. Zhou, "Link prediction in complex networks: A survey", Physica A Stat. Mech. Appl., vol. 390, no. 6, pp. 1150-1170, 2011.
5.
L. A. Adamic and E. Adar, "Friends and neighbors on the web", Social Netw., vol. 25, no. 3, pp. 211-230, 2003.
6.
Y. Koren, R. Bell and C. Volinsky, "Matrix factorization techniques for recommender systems", Computer, vol. 41, no. 8, pp. 30-37, 2009.
7.
H. Wang et al., "Knowledge-aware graph neural networks with label smoothness regularization for recommender systems", Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, pp. 968-977, 2019.
8.
J. You, Y. Wang, A. Pal, P. Eksombatchai, C. Rosenburg and J. Leskovec, "Hierarchical temporal convolutional networks for dynamic recommender systems", Proc. World Wide Web Conf., pp. 2236-2246, 2019.
9.
M. Nickel, K. Murphy, V. Tresp and E. Gabrilovich, "A review of relational machine learning for knowledge graphs", Proc. IEEE, vol. 104, no. 1, pp. 11-33, Jan. 2016.
10.
E. M. Airoldi, D. M. Blei, S. E. Fienberg and E. P. Xing, "Mixed membership stochastic blockmodels", J. Mach. Learn. Res., vol. 9, pp. 1981-2014, 2008.
11.
T. Oyetunde, M. Zhang, Y. Chen, Y. Tang and C. Lo, "Boostgapfill: Improving the fidelity of metabolic network reconstructions through integrated constraint and pattern-based methods", Bioinformatics, vol. 33, no. 4, pp. 608-611, 2017.
12.
A.-L. Barabási and R. Albert, "Emergence of scaling in random networks", Science, vol. 286, no. 5439, pp. 509-512, 1999.
13.
I. A. Kovács et al., "Network-based prediction of protein interactions", Nat. Commun., vol. 10, no. 1, 2019.
14.
M. Zhang and Y. Chen, "Link prediction based on graph neural networks", Proc. Adv. Neural Inf. Process. Syst., pp. 5165-5175, 2018.
15.
M. Zhang, Z. Cui, M. Neumann and Y. Chen, "An end-to-end deep learning architecture for graph classification", Proc. AAAI Conf. Artif. Intell., pp. 4438-4445, 2018.
16.
H. Gao and S. Ji, "Graph u-nets", Proc. Int. Conf. Mach. Learn., pp. 2083-2092, 2019.
17.
H. Yuan and S. Ji, "StructPool: Structured graph pooling via conditional random fields", Proc. Int. Conf. Learn. Representations, 2019.
18.
Z. Ying, J. You, C. Morris, X. Ren, W. Hamilton and J. Leskovec, "Hierarchical graph representation learning with differentiable pooling", Proc. Adv. Neural Inf. Process. Syst., pp. 4800-4810, 2018.
19.
H. Gao, Z. Wang and S. Ji, "Large-scale learnable graph convolutional networks", Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, pp. 1416-1424, 2018.
20.
T. N. Kipf and M. Welling, "Semi-supervised classification with graph convolutional networks", 2016.
21.
M. Niepert, M. Ahmed and K. Kutzkov, "Learning convolutional neural networks for graphs", Proc. Int. Conf. Mach. Learn., pp. 2014-2023, 2016.
22.
W. Hamilton, Z. Ying and J. Leskovec, "Inductive representation learning on large graphs", Proc. Adv. Neural Inf. Process. Syst., pp. 1024-1034, 2017.
23.
T. Zhou, L. Lü and Y.-C. Zhang, "Predicting missing links via local information", Eur. Phys. J. B, vol. 71, no. 4, pp. 623-630, 2009.
24.
L. Katz, "A new status index derived from sociometric analysis", Psychometrika, vol. 18, no. 1, pp. 39-43, 1953.
25.
S. Brin and L. Page, "Reprint of: The anatomy of a large-scale hypertextual web search engine", Comput. Netw., vol. 56, no. 18, pp. 3825-3833, 2012.
26.
G. Jeh and J. Widom, "Simrank: A measure of structural-context similarity", Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, pp. 538-543, 2002.
27.
A. Y. Ng, M. I. Jordan and Y. Weiss, "On spectral clustering: Analysis and an algorithm", Proc. Adv. Neural Inf. Process. Syst., pp. 849-856, 2002.
28.
B. Perozzi, R. Al-Rfou and S. Skiena, "Deepwalk: Online learning of social representations", Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, pp. 701-710, 2014.
29.
J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan and Q. Mei, "Line: Large-scale information network embedding", Proc. Int. Conf. World Wide Web, pp. 1067-1077, 2015.
30.
J. Qiu, Y. Dong, H. Ma, J. Li, K. Wang and J. Tang, "Network embedding as matrix factorization: Unifying deepwalk LINE PTE and node2vec", Proc. ACM Int. Conf. Web Search Data Mining, pp. 459-467, 2018.
Contact IEEE to Subscribe

References

References is not available for this document.