Line Graph Neural Networks for Link Prediction

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.

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].