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.
翻译:链接的预测是图表上的一项非常根本的任务。 受基于路径的传统方法的启发, 我们在此文件中提议了一个基于链接预测路径的通用和灵活的代表性学习框架。 具体地说, 我们定义了一对节点的表示方式, 作为所有路径表达方式的统和, 每种路径表示方式都是路径表达方式的通用产物。 由Bellman- Ford 算法推动, 以解决最短路径问题, 我们显示, 拟议的路径配置方法可以通过通用的 Bellman- Ford 算法来有效解决。 为了进一步提高路径配置能力, 我们提议了 Neural Bellman- Ford 网络( NBFNet), 一个通用的图形网络神经网络框架, 用通用的 Bellman- Ford 算法中学习的操作者来解决路径表达方式的表达方式。 NBFFNet 将通用的算法和 AGGGGGGGGGGGA 的计算方法, 分别与拟议的边界条件、 倍增运算操作器和计算操作程序相匹配。 NBBFNet, 包括许多基于路径的路径的路径的方法, 和在直观的图中, 和直观的图形中, 以及直观的图中, 可以同时在正图中, 和直观的图中, 和直观的图中, 两种方法都用于在正态的图式的图形-, 和直观的图形- 。