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

By Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, Jian Tang. Neural Information Processing Systems, 2021

508 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/76305acf2bf94e3a5677f7547098eeffb6649706

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

1. Andrea Lodi
2. Didier Chételat
3. Yue Liu
4. Siwei Wang
5. Lingyuan Meng
6. Wenxuan Tu
7. Quentin Cappart
8. K. Liang

In Statistical and Nonlinear Physics

1. Xinwang Liu
2. Petar Velickovic
3. Elias Boutros Khalil

Citations in the corpus

• Combinatorial optimization and reasoning with graph neural networks (2021, background): “Answering logical queries can often be helped by path-finding primitives, which was recently embodied in the NBFNet model (Zhu et al., 2021).”
• A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multi-Modal (2022, methodology): “NBF-net[96]andRED-GNN[97] achievebetterefficiencybyleveragingthetraditionalalgo-rithm, i.e., bellman-ford algorithm and dynamic programming to optimize the propagation strategy in previous GNN models.”