Link Prediction Based on Graph Neural Networks

By Muhan Zhang, Yixin Chen. 2018

2,394 citations recorded by the source corpus.

Link prediction is a key problem for network-structured data. Link prediction heuristics use some score functions, such as common neighbors and Katz index, to measure the likelihood of links. They have obtained wide practical uses due to their simplicity, interpretability, and for some of them, scalability. However, every heuristic has a strong assumption on when two nodes are likely to link, which limits their effectiveness on networks where these assumptions fail. In this regard, a more reasonable way should be learning a suitable heuristic from a given network instead of using predefined ones. By extracting a local subgraph around each target link, we aim to learn a function mapping the subgraph patterns to link existence, thus automatically learning a `heuristic' that suits the current network. In this paper, we study this heuristic learning paradigm for link prediction. First, we develop a novel $\gamma$-decaying heuristic theory. The theory unifies a wide range of heuristics in a single framework, and proves that all these heuristics can be well approximated from local subgraphs. Our results show that local subgraphs reserve rich information related to link existence. Second, based on the $\gamma$-decaying theory, we propose a new algorithm to learn heuristics from local subgraphs using a graph neural network (GNN). Its experimental results show unprecedented performance, working consistently well on a wide range of problems.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Position-aware Graph Neural Networks (2019, methodology): “Heuristics that alleviate the above issues include assigning an unique identiﬁer to each node (Kipf & Welling, 2017; Hamilton et al., 2017a) or using locally assigned node iden-tiﬁers plus pre-trained transductive node features (Zhang & Chen, 2018).”
Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, background): “…of graph representation learning with success in not only node-level tasks such as node classification (Kipf & Welling, 2016a) and link prediction (Zhang & Chen, 2018) but also graph-level tasks such as graph classification (Ying et al., 2018) and graph similarity/distance computation (Bai et…”
Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity (2019, neutral): “…graph representation learning with success in not only node-level tasks such as node classification [Kipf and Welling, 2016a] and link prediction [Zhang and Chen, 2018], but also graphlevel tasks such as graph classification [Ying et al., 2018] and graph similarity/distance computation [Bai et…”
Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks (2019, background): “25 1 INTRODUCTION Graph convolutional network (GCN) [9] has become increasingly popular in addressing many graph-based applications, including semi-supervised node classification [9], link prediction [17] and recommender systems [15]. Given a graph, GCN uses a graph convolution operation to obtain n”
Temporal Graph Networks for Deep Learning on Dynamic Graphs (2020, background): “…on such data is possible using graph neural networks (GNNs) [26] that typically operate by a message passing mechanism [4] aggregating information in a neighborhood of a node and create node embeddings that are then used for node-wise classiﬁcation [42, 61, 35] or edge prediction [72] tasks.”
Learning Discrete Structures for Graph Neural Networks (2019, methodology): “While a majority of the methods are based on some similarity measure between node pairs, there has been a number of neural network based methods (Zhang & Chen, 2017, 2018).”
Foundations and Modeling of Dynamic Networks Using Dynamic Graph Neural Networks: A Survey (2020, methodology): “When encoding graphs one option is to split the graph into sub-graphs and use a GNN to project each sub-graph as done by Zhang et al. [92] for static GNNs.”
GNNExplainer: Generating Explanations for Graph Neural Networks (2019, background): “To address this challenge, Graph Neural Networks (GNNs) have emerged as state-of-the-art for machine learning on graphs, due to their ability to recursively incorporate information from neighboring nodes in the graph, naturally capturing both graph structure and node features [16, 21, 40, 44].”
XGNN: Towards Model-Level Explanations of Graph Neural Networks (2020, background): “Graph Neural Networks (GNNs) have shown their effectiveness and obtained the state-of-the-art performance on different graph tasks, such as node classification [11, 37], graph classification [39, 47], and link prediction [46].”
Graph Neural Networks and Their Current Applications in Bioinformatics (2021, background): “, 2018), link prediction and node clustering of social networks (Zhang and Chen, 2018), network completion of missing information (Bojchevski and Günnemann, 2017), drug interaction prediction (Zitnik et al.”
A Fair Comparison of Graph Neural Networks for Graph Classification (2019, methodology): “One notable exception is DGCNN, which explicitly needs node degrees to perform well on all datasets.”
Graph Contrastive Learning with Augmentations (2020, background): “Numerous variants of GNNs have been proposed to achieve state-of-the-art performances in graph-based tasks, such as node or link classiﬁcation [1, 2, 4, 5, 6], link prediction [7] and graph classiﬁcation [8, 3].”
Explainability in Graph Neural Networks: A Taxonomic Survey (2020, background): “Several graphrelated tasks are widely studied, such as node classification [30], [31], [32], graph classification [5], [33], link predictions [34], [35], [36].”
Hyperbolic Graph Convolutional Neural Networks (2019, background): “We did not compare link prediction GNNs based on shallow embeddings such as [49] since they are not inductive.”
Open Graph Benchmark: Datasets for Machine Learning on Graphs (2020, background): “Broadly, there are two lines of efforts for the link-level task: link prediction in homogeneous networks (Liben-Nowell & Kleinberg, 2007; Zhang & Chen, 2018) and relation completion in (heterogeneous) knowledge graphs (Bordes et al., 2013; Hu et al., 2020b).”