Link Prediction Based on Graph Neural Networks

Abstract

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.

arXiv commentAccepted by NIPS 2018

References in corpus (15)

• Semi-Supervised Classification with Graph Convolutional Networks
• Finding community structure in networks using the eigenvectors of matrices
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Link Prediction in Complex Networks: A Survey
• Spectral Networks and Locally Connected Networks on Graphs
• Predicting Missing Links via Local Information
• struc2vec: Learning Node Representations from Structural Identity
• Variational Graph Auto-Encoders
• Learning Convolutional Neural Networks for Graphs
• Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
• Discriminative Embeddings of Latent Variable Models for Structured Data
• Gated Graph Sequence Neural Networks
• Subgraph Matching Kernels for Attributed Graphs
• Leveraging Node Attributes for Incomplete Relational Data

Cited by in corpus (68)

• Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
• Towards Deeper Graph Neural Networks
• Scaling Graph Neural Networks with Approximate PageRank
• Mining Latent Structures for Multimedia Recommendation
• Multi-view Graph Contrastive Representation Learning for Drug-Drug Interaction Prediction
• Learning Discrete Structures for Graph Neural Networks
• Chip Placement with Deep Reinforcement Learning
• Examining COVID-19 Forecasting using Spatio-Temporal Graph Neural Networks
• Graph Convolutional Networks for Graphs Containing Missing Features
• MR-GNN: Multi-Resolution and Dual Graph Neural Network for Predicting Structured Entity Interactions
• Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
• GoGNN: Graph of Graphs Neural Network for Predicting Structured Entity Interactions
• Temporal Graph Networks for Deep Learning on Dynamic Graphs
• DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks
• When Does Self-Supervision Help Graph Convolutional Networks?
• Semi-Implicit Graph Variational Auto-Encoders
• Graph Representation Learning via Graphical Mutual Information Maximization
• PGM-Explainer: Probabilistic Graphical Model Explanations for Graph Neural Networks
• Dirichlet Energy Constrained Learning for Deep Graph Neural Networks
• Self-supervised Auxiliary Learning with Meta-paths for Heterogeneous Graphs
• Hypergraph Convolution and Hypergraph Attention
• Hashing-Accelerated Graph Neural Networks for Link Prediction
• Attacking Similarity-Based Link Prediction in Social Networks
• Graph Capsule Aggregation for Unaligned Multimodal Sequences
• Be Confident! Towards Trustworthy Graph Neural Networks via Confidence Calibration
• Semantic and Relational Spaces in Science of Science: Deep Learning Models for Article Vectorisation
• CAGNN: Cluster-Aware Graph Neural Networks for Unsupervised Graph Representation Learning
• Linkage Based Face Clustering via Graph Convolution Network
• Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training
• Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity
• Structack: Structure-based Adversarial Attacks on Graph Neural Networks
• UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks
• On the Equivalence of Decoupled Graph Convolution Network and Label Propagation
• Heterogeneous Information Network-based Interest Composition with Graph Neural Network for Recommendation
• Learning Edge Properties in Graphs from Path Aggregations
• On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphs
• Data Considerations in Graph Representation Learning for Supply Chain Networks
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs
• Gated Graph Recursive Neural Networks for Molecular Property Prediction
• Graph link prediction in computer networks using Poisson matrix factorisation
• Learning First-Order Rules with Relational Path Contrast for Inductive Relation Reasoning
• Self-supervised edge features for improved Graph Neural Network training
• Hierarchical Message-Passing Graph Neural Networks
• Mask-GVAE: Blind Denoising Graphs via Partition
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results
• Missing Data Estimation in Temporal Multilayer Position-aware Graph Neural Network (TMP-GNN)
• GMLP: Building Scalable and Flexible Graph Neural Networks with Feature-Message Passing
• Feature Interaction-aware Graph Neural Networks
• GCNScheduler: Scheduling Distributed Computing Applications using Graph Convolutional Networks
• Inference for Network Structure and Dynamics from Time Series Data via Graph Neural Network
• LinkLouvain: Link-Aware A/B Testing and Its Application on Online Marketing Campaign
• GraphITE: Estimating Individual Effects of Graph-structured Treatments
• Understanding Higher-order Structures in Evolving Graphs: A Simplicial Complex based Kernel Estimation Approach
• Task-Guided Pair Embedding in Heterogeneous Network
• Into the Battlefield: Quantifying and Modeling Intra-community Conflicts in Online Discussion
• On Local Aggregation in Heterophilic Graphs
• Generative Temporal Link Prediction via Self-tokenized Sequence Modeling
• Leap: Inductive Link Prediction via Learnable TopologyAugmentation
• Fast Graph Learning with Unique Optimal Solutions
• Label-informed Graph Structure Learning for Node Classification
• Co-embedding of Nodes and Edges with Graph Neural Networks
• STR-GODEs: Spatial-Temporal-Ridership Graph ODEs for Metro Ridership Prediction
• Adaptive Transfer Learning on Graph Neural Networks
• Brain dynamics via Cumulative Auto-Regressive Self-Attention
• Sequential Aggregation and Rematerialization: Distributed Full-batch Training of Graph Neural Networks on Large Graphs
• An Uncoupled Training Architecture for Large Graph Learning
• Contextual Scene Augmentation and Synthesis via GSACNet