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

Published in

Neural Information Processing Systems(2021)

External Links:

Generate Graph

TL;DR

The Neural Bellman-Ford Network (NBFNet) is proposed, a general graph neural network framework that solves the path formulation with learned operators in the generalized Bell man-Ford algorithm, and outperforms existing methods by a large margin in both transductive and inductive settings.

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.

Authors

Zhaocheng Zhu

2 papers

Jian Tang

8 papers

Zuobai Zhang

2 papers

References88 items

QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering

OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs

Link Prediction with Persistent Homology: An Interactive View

Identity-aware Graph Neural Networks

xERTE: Explainable Reasoning on Temporal Knowledge Graphs for Forecasting Future Links

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

Published in

Neural Information Processing Systems(2021)

External Links:

Generate Graph

TL;DR

Abstract

Authors

Zhaocheng Zhu

2 papers

Jian Tang

8 papers

Zuobai Zhang

2 papers

References88 items

QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering

OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs

Link Prediction with Persistent Homology: An Interactive View

Identity-aware Graph Neural Networks

xERTE: Explainable Reasoning on Temporal Knowledge Graphs for Forecasting Future Links

Louis-Pascal Xhonneux

1 papers

PairRE: Knowledge Graph Embeddings via Paired Relation Vectors

Revisiting Graph Neural Networks for Link Prediction

RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs

Few-shot link prediction via graph neural networks for Covid-19 drug-repurposing

LowFER: Low-rank Bilinear Pooling for Link Prediction

GE-SpMM: General-Purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networks

Open Graph Benchmark: Datasets for Machine Learning on Graphs

Principal Neighbourhood Aggregation for Graph Nets

Relational Message Passing for Knowledge Graph Completion

Entity Context and Relational Paths for Knowledge Graph Completion

Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings

Reasoning on Knowledge Graphs with Debate Dynamics

Learning Hierarchy-Aware Knowledge Graph Embeddings for Link Prediction

Inductive Relation Prediction by Subgraph Reasoning

Orthogonal Relation Transforms with Graph Context Modeling for Knowledge Graph Embedding

Composition-based Multi-Relational Graph Convolutional Networks

DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs

PairNorm: Tackling Oversmoothing in GNNs

Dynamically Pruned Message Passing Networks for Large-Scale Knowledge Graph Reasoning

AutoSF: Searching Scoring Functions for Knowledge Graph Embedding

GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding

Simplifying Graph Convolutional Networks

Fine-Grained Evaluation of Rule- and Embedding-Based Systems for Knowledge Graph Completion

How Powerful are Graph Neural Networks?

RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space

Multi-Hop Knowledge Graph Reasoning with Reward Shaping

Embedding Logical Queries on Knowledge Graphs

Hyperspherical Variational Auto-Encoders

Variational Knowledge Graph Reasoning

Link Prediction Based on Graph Neural Networks

SimplE Embedding for Link Prediction in Knowledge Graphs

M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Search

Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning

Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning

Graph Attention Networks

DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning

Convolutional 2D Knowledge Graph Embeddings

Inductive Representation Learning on Large Graphs

Neural Message Passing for Quantum Chemistry

Modeling Relational Data with Graph Convolutional Networks

Differentiable Learning of Logical Rules for Knowledge Base Reasoning

Variational Graph Auto-Encoders

Semi-Supervised Classification with Graph Convolutional Networks

Layer Normalization

Chains of Reasoning over Entities, Relations, and Text using Recurrent Neural Networks

node2vec: Scalable Feature Learning for Networks

Compositional Learning of Embeddings for Relation Paths in Knowledge Base and Text

Complex Embeddings for Simple Link Prediction

Efficient and Expressive Knowledge Base Completion Using Subgraph Feature Extraction

Observed versus latent features for knowledge base and text inference

Compositional Vector Space Models for Knowledge Base Completion

LINE: Large-scale Information Network Embedding

A Review of Relational Machine Learning for Knowledge Graphs

Embedding Entities and Relations for Learning and Inference in Knowledge Bases

Knowledge Graph Embedding by Translating on Hyperplanes

DeepWalk: online learning of social representations

Translating Embeddings for Modeling Multi-relational Data

Visualizing and Understanding Convolutional Networks

AMIE: association rule mining under incomplete evidence in ontological knowledge bases

Relational retrieval using a combination of path-constrained random walks

Path Problems in Networks

How to Explain Individual Classification Decisions

Matrix Factorization Techniques for Recommender Systems

Collective Classification in Network Data

ON A ROUTING PROBLEM

Optimal oblivious routing in polynomial time

Scaling personalized web search

SimRank: a measure of structural-context similarity

The PageRank Citation Ranking : Bringing Order to the Web

Semirings: Algebraic Theory and Applications in Computer Science

Long Short-Term Memory

Error bounds for convolutional codes and an asymptotically optimum decoding algorithm

A new status index derived from sociometric analysis

: End-to-end differentiable rule

Hyperspherical Variational Auto-Encoders

Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality

TL;DR

Abstract

Authors

References88 items

QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering

OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs

Link Prediction with Persistent Homology: An Interactive View

Identity-aware Graph Neural Networks

xERTE: Explainable Reasoning on Temporal Knowledge Graphs for Forecasting Future Links

TL;DR

Abstract

Authors

References88 items

QA-GNN: Reasoning with Language Models and Knowledge Graphs for Question Answering

OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs

Link Prediction with Persistent Homology: An Interactive View

Identity-aware Graph Neural Networks

xERTE: Explainable Reasoning on Temporal Knowledge Graphs for Forecasting Future Links

PairRE: Knowledge Graph Embeddings via Paired Relation Vectors

Revisiting Graph Neural Networks for Link Prediction

RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs

Few-shot link prediction via graph neural networks for Covid-19 drug-repurposing

LowFER: Low-rank Bilinear Pooling for Link Prediction

GE-SpMM: General-Purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networks

Open Graph Benchmark: Datasets for Machine Learning on Graphs

Principal Neighbourhood Aggregation for Graph Nets

Relational Message Passing for Knowledge Graph Completion

Entity Context and Relational Paths for Knowledge Graph Completion

Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings

Reasoning on Knowledge Graphs with Debate Dynamics

Learning Hierarchy-Aware Knowledge Graph Embeddings for Link Prediction

Inductive Relation Prediction by Subgraph Reasoning

Orthogonal Relation Transforms with Graph Context Modeling for Knowledge Graph Embedding

Composition-based Multi-Relational Graph Convolutional Networks

DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs

PairNorm: Tackling Oversmoothing in GNNs

Dynamically Pruned Message Passing Networks for Large-Scale Knowledge Graph Reasoning

AutoSF: Searching Scoring Functions for Knowledge Graph Embedding

GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding

Simplifying Graph Convolutional Networks

Fine-Grained Evaluation of Rule- and Embedding-Based Systems for Knowledge Graph Completion

How Powerful are Graph Neural Networks?

RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space

Multi-Hop Knowledge Graph Reasoning with Reward Shaping

Embedding Logical Queries on Knowledge Graphs

Hyperspherical Variational Auto-Encoders

Variational Knowledge Graph Reasoning

Link Prediction Based on Graph Neural Networks

SimplE Embedding for Link Prediction in Knowledge Graphs

M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Search

Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning

Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning

Graph Attention Networks

DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning

Convolutional 2D Knowledge Graph Embeddings

Inductive Representation Learning on Large Graphs

Neural Message Passing for Quantum Chemistry

Modeling Relational Data with Graph Convolutional Networks

Deep Sets

Differentiable Learning of Logical Rules for Knowledge Base Reasoning

Variational Graph Auto-Encoders

Semi-Supervised Classification with Graph Convolutional Networks

Layer Normalization

Chains of Reasoning over Entities, Relations, and Text using Recurrent Neural Networks

node2vec: Scalable Feature Learning for Networks

Compositional Learning of Embeddings for Relation Paths in Knowledge Base and Text

Complex Embeddings for Simple Link Prediction

Efficient and Expressive Knowledge Base Completion Using Subgraph Feature Extraction

Observed versus latent features for knowledge base and text inference

Compositional Vector Space Models for Knowledge Base Completion

LINE: Large-scale Information Network Embedding

A Review of Relational Machine Learning for Knowledge Graphs

Embedding Entities and Relations for Learning and Inference in Knowledge Bases

Knowledge Graph Embedding by Translating on Hyperplanes

DeepWalk: online learning of social representations

Translating Embeddings for Modeling Multi-relational Data

Visualizing and Understanding Convolutional Networks

AMIE: association rule mining under incomplete evidence in ontological knowledge bases

PathSim

Relational retrieval using a combination of path-constrained random walks