Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction

Abstract

Link prediction is a very fundamental task on graphs. Inspired by traditional path-based methods, in this paper we propose a general and flexible representation learning framework based on paths for link prediction. Specifically, we define the representation of a pair of nodes as the generalized sum of all path representations, with each path representation as the generalized product of the edge representations in the path. Motivated by the Bellman-Ford algorithm for solving the shortest path problem, we show that the proposed path formulation can be efficiently solved by the generalized Bellman-Ford algorithm. To further improve the capacity of the path formulation, we propose the Neural Bellman-Ford Network (NBFNet), a general graph neural network framework that solves the path formulation with learned operators in the generalized Bellman-Ford algorithm. The NBFNet parameterizes the generalized Bellman-Ford algorithm with 3 neural components, namely INDICATOR, MESSAGE and AGGREGATE functions, which corresponds to the boundary condition, multiplication operator, and summation operator respectively. The NBFNet is very general, covers many traditional path-based methods, and can be applied to both homogeneous graphs and multi-relational graphs (e.g., knowledge graphs) in both transductive and inductive settings. Experiments on both homogeneous graphs and knowledge graphs show that the proposed NBFNet outperforms existing methods by a large margin in both transductive and inductive settings, achieving new state-of-the-art results.

NeurIPS 2021

References in corpus (14)

• Simplifying Graph Convolutional Networks
• Variational Graph Auto-Encoders
• RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• Principal Neighbourhood Aggregation for Graph Nets
• OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs
• RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs
• Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings
• DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs
• QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering
• Few-shot link prediction via graph neural networks for Covid-19 drug-repurposing
• xERTE: Explainable Reasoning on Temporal Knowledge Graphs for Forecasting Future Links
• Identity-aware Graph Neural Networks
• Link Prediction with Persistent Homology: An Interactive View

Cited by in corpus (11)

• Knowledge Graph Reasoning with Relational Digraph
• RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs
• Normalizing Flow-based Neural Process for Few-Shot Knowledge Graph Completion
• Toward Degree Bias in Embedding-Based Knowledge Graph Completion
• LPFormer: An Adaptive Graph Transformer for Link Prediction
• Pitfalls in Link Prediction with Graph Neural Networks: Understanding the Impact of Target-link Inclusion & Better Practices
• Counterfactual Learning on Graphs: A Survey
• Learning Scalable Structural Representations for Link Prediction with Bloom Signatures
• Knowledge-Enhanced Recommendation with User-Centric Subgraph Network
• Hierarchical Position Embedding of Graphs with Landmarks and Clustering for Link Prediction
• Combining Optimal Path Search With Task-Dependent Learning in a Neural Network