Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction
Authors: Zhaocheng Zhu
Zuobai Zhang
Louis-Pascal A. C. Xhonneux
Jian Tang
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural networks
link prediction
knowledge graph completion
Bellman-Ford algorithm

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 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.

Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction
Zhaocheng Zhu 12, Zuobai Zhang"? Louis-Pascal Xhonneux!2 12, Jian Tang!
Mila Québec AI Institute', Université de Montréal
HEC Montréal", CIFAR AI Chair'
{zhaocheng: zhu, zuobai zhang, louis louis-pascal xhonneexx)miilla queubbb jian. tang@hec.c.......... ca.
Abstract
Link prediction is very fundamental task graphs. Inspired by traditional path-based methods, in this paper we propose general and flexible representation learning framework based
paths for link prediction. Specifically, representation of a pair of nodes as the generalized sum of all path representations between the nodes, with each path representation the edge representations in the path. Motivated by the Bellman- Ford algorithm for solving the shortest path problem, can be efficiently solved by the generalized Bellman-Forr algorithm. To further improve the capacity the path formulation, we propose the Neural Bellman- Network (NBFNet), 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- algorithm with 3 neural components, namely INDICATOR, MESSAGE and AGGREGATE functions, which corresponds to the boundary condition, multiplication operator, and summation operator respectively!I The NBFNet 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 homogencous graphs and knowledge graphs show that the proposed NBFNet outperforms existing methods by large margin in both transductive and inductive settings, achieving new state-of-the-arr results
define the
the generalized product of
show that the proposed path formulation
Introduction
Predicting the interactions between nodes (a.k.a. link prediction) a fundamental task the field of graph machine learning. Given the ubiquitous existence of graphs, such task has many applications, such as recommender system knowledge graph completion 41 and drug repurposing (27].
Traditional methods of link prediction usually define different heuristic metrics over the paths between pair of nodes. For example, Katz index [30] is defined weighted count of paths between two nodes. Personalized PageRank [42] measures the similarity of two nodes as the random walk probability from one the other. Graph distance [37 uses the length of the shortest path between two nodes to predict their association. These methods can be directly applied to new graphs. i.e., inductive setting, enjoy good interpretability and scale up large graphs. However, they are designed based on handcrafted metrics and may not be optimal for link prediction on real-world graphs.
'Unless stated otherwise, formulation, rather than the basic operations of arithmetic. "Code is available at
summation and multiplicatiin to refer the generalized operators in the path
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

To address these limitations, some link prediction methods adopt graph neural networks (GNNs) B2
48 59 to automatically extract important features from local neighborhoods for link prediction.
Thanks to the high expressiveness of GNNs, these methods have shown state-of-the-ar performance. However, these methods can only be applied to prediet new links on the training graph, í.e. transduc- tive setting, and lack interpretability. While some recent methods [73 55 extract features from local subgraphs with GNNs and support inductive setting, the scalability of these methods is compromised.
Therefore, we wonder if there exists an approach that enjoys the advantages of both traditional path-based methods and recent approaches based on graph neural networks, i.e., generalization in the inductive setting, interpretability. high model capacity and scalability.
In this paper, propose such solution. Inspired by traditional path-based methods, our goal is to develop a general and flexible representation learning framework for link prediction based on the paths between two nodes. Specifically, we define the representation of pair of nodes as the generalized sum of all the path representations between them, where each path representation is defined as the generalized product of the edge representations in the path. Many link prediction methods, such as Katz index [30], personalized PageRank [42), graph distance [37]. as well as graph theory algorithms like widest path 4 and most reliable path are special instances of this path formulation with different summation and multiplication operators. Motivated by the polynomial-time algorithm for the shortest path problem [5], we show that such formulation can be efficiently solved via the generalized Bellman- Ford algorithm 4 under mild conditions and scale up to large graphs.
The operators in the generalized Bellman-Ford choorithm-ssmmmatin and multiplication-aarc handcrafted, which have limited flexibility. Therefore, we further propose the Neural Bellman-Ford Networks (NBFNet), a graph neural network framework that solves the above path formulation with learned operators in the generalized Bellman-Ford algorithm. Specifically, NBFNet parameterizes the generalized Bellman-Ford algorithm with three neural components, namely INDICATOR, MESSAGE and AGGREGATE functions. The INDICATOR function initializes a representation on each node, which is taken as the boundary condition of the generalized Bellman-Ford algorithm. The MESSAGE and the AGGREGATE functions learn the multiplication and summation operators respectively.
We show that the MESSAGE function can be defined according to the relational operators in knowledge graph embeddings 6 68 58 (1 [5], e.g., as a translation in Euclidean space induced by the relational operators of TransE 6 The AGGREGATE. function can be defined as learnable set aggregation functions 7 651 9 With such parameterization, NBFNet can generalize to the inductive setting, meanwhile achieve one of the lowest time complexity among inductive GNN methods. A comparison of NBFNet and other GNN frameworks for link prediction is showed in Table | With other instantiations of MESSAGE and AGGREGATE functions, our framework can also recover some existing works on learning logic rules 69 46 for link prediction on knowledge graphs (Table (2).
Our NBFNet framework can be applied several link prediction variants, covering not only single- relational graphs (c.g., homogeneous graphs) but also multi-relational graphs (c.g., knowledge graphs) We empirically evaluate the proposed NBFNet for link prediction on homogeneous graphs and knowledge graphs in both transductive and inductive settings. Experimental results show that the proposed NBFNet outperforms existing state-of-ther ahr methods by large margin in all settings, with an average relative performance gain of 18% on knowledge graph completion (HITS@) 1) and 22% on inductive relation prediction (HITS@ 10). We also show that the proposed NBFNet is indeed interpretable by visualizing the top-k relevant paths for link prediction on knowledge graphs.
Table 1: Comparison of GNN frameworks for link prediction. The time complexity refers to the amortized time for predicting a single edge or triplet. [V] is the number of nodes, |[] is the number of edges, and d is the dimension of representations. The wall time is measured on FB 153-237 test set with 40 CPU cores and 4 GPUs We estimate the wall time of GralL based on a downsampled test set.
Method
Inductive
Interpretable
Learned Representation Time Complexity
Wall Time
VGAE
32
O(d)
18 secs
RGCN
45
Neura P 69
LE ( TVT + de) ((18)d)
2.1 mins
DRUM 46
SEAL 73
month
Grall.
55
NBFNet
0 18/4
+ d² [
4.0 mins
2

---

2 Related Work
Existing work on link prediction can be generally classified into main paradigms: methods, embedding methods, and graph neural networks.
path-based
Path-based Methods. Early methods on homogeneous graphs compute the similarity between two nodes based on the weighted count of paths (Katz index (30)) random walk probability (personalized
PageRank [42]) or the length of the shortest path (graph distance (37). SimRank [28] uses advanced
metrics such as the expected meeting distance on homogeneous graphs, which is extended by
PathSim [51] to heterogeneous graphs. On knowledge graphs, Path Ranking 35 15) directly uses
relational paths as symbolic features for prediction. Rule mining methods, such as Neurall.P [69] and DRUM 46 learn probabilistic logical rules to weight different paths. Path representation methods, such as Path-RNN [40] and its successors [I] 62], encode each path with recurrent neural networks (RNNs), and aggregate paths for prediction. However, these methods need to traverse an exponential number of paths and are limited to very short paths, e.g., S 3 edges. To scale up path-based methods, All-Paths (57] proposes to efficiently aggregate all paths with dynamic programming. However, All-Paths is restricted to bilinear models and has limited model capacity. Another stream of works [64] [0 22 learns an agent to collect useful paths for link prediction. While these methods can produce interpretable paths, they suffer from extremely sparse rewards and require careful engineering of the reward function (38] or the search strategy [50]. Some other works [8 44 adopt variational inference to learn a path finder and path reasoner for link prediction.
Embedding Methods. Embedding methods learn a distributed representation for each node and edge by preserving the edge structure of the graph. Representative methods include DeepWalk 43 and
LINE (53) on homogeneous graphs, and TransE (6). DistMult [68] and RotatE [52] on knowledge
graphs. Later works improve embedding methods with new score functions 588 13
52 76
that capture common semantic patterns of the relations, or search the score function in a general design space (75). Embedding methods achieve promising results link prediction, and can be scaled to very large graphs using multiple GPUs [78]. However, embedding methods do not explicitly encode local subgraphs between node pairs and cannot be applied to the inductive setting.
Graph Neural Networks. Graph neural networks (GNNs) 47 60, 65 are a family of represen- tation learning models that encode topological structures of graphs. For link prediction, the prevalent adopt an auto-encoder formulation, which uses GNNs to encode node representations, and decodes edges as a function over node pairs. Such frameworks are potentially inductive if the dataset provides node features, but are transductive only when node features are unavailable. Another stream of frameworks, such SEAL (73 and GralL (55), explicitly encodes the subgraph around each node pair for link prediction. While these frameworks are proved to be more powerful than the auto-encoder formulation 774 and can solve the inductive setting, they require to materialize a subgraph for each link, which is not scalable to large graphs. By contrast, our NBFNet explicitly captures the paths between two nodes for link prediction, meanwhile achieves relatively low time complexity (Table ID-GNN (70) formalizes link prediction as a conditional node classification task, and augments GNNs with the identity of the source node. While the archi- tecture of NBFNet shares some spirits with ID-GNN, our model is motivated by the generalized Bellman-Ford algorithm and has theoretical connections with traditional path-based methods. There are also some works trying to scale up GNNs for link prediction by dynamically pruning the set of nodes in message passing [66] (0). These methods are complementary NBFNet, and may be incorporated into our method to further improve scalability.
frameworks 32 48
12
5
3 Methodology
In this section, we first define a path formulation for link prediction. Our path formulation generalizes several traditional methods, and can be efficiently solved by the generalized Bellman-Fore algorithm. Then we propose Neural Bellman-Ford Networks to learn the path formulation with neural functions.
3.1 Path Formulation for Link Prediction
We consider the link prediction problem on both knowledge graphs and homogeneous graphs. A
We consider the inductive setting where model can generalize entirely new graphs without node features.
3

---

knowledge graph is denoted by G = (V.E.R), where V and & represent the set of entities (nodes) and relations (edges) respectively, and the set of relation types. We use N(w to denote the set of nodes connected to and E {()) to denote the set of edges ending with node u. A homogeneous graph g = E) can be viewed as a special case of knowledge graphs, with only one relation type for all edges. Throughout this paper, we use bold terms, wy (e) or hg (u. v), to denote vector representations, and italic terms, We or Wue. to denote scalars like the weight of edge (u, v) in homogeneous graphs or triplet (u, r, v) in knowledge graphs. Without loss of generality, we derive our method based on knowledge graphs, while our method can also be applied to homogeneous graphs.
Path Formulation. Link prediction is aimed at predicting the existence of a query relation between a head entity u and a tail entity t. From representation learning perspective, this requires to learn pair representation h (u, v), which captures the local subgraph structure between and e w.r.t the query relation q. In traditional methods, such local structure encoded by counting different types of random walks from to v [5 [5]. Inspired by this construction, we formulate the pair representation as a generalized sum of path representations between u and with a commutative summatton operator @D Each path representation (PP) is defined as generalized product of the edge representations in the path with the multiplication operator &
hg(u, 2) 1gg(1)) @ hg (P2) @ ... @ hg ( Pp..... PEPE
hy(P)
PEP
IP|
(P = (01, C2: ..., e2., (pI)) = (ele)) w. (e2) @ ... @ (pp)
wpyC)
where Puo denotes the set of paths from multiplication operator @ is not required to he commutative (e.g.. matrix multiplication), therefore we define 2 to compute the product following the exact order. Intuitively, the path formulation can be interpreted as depth-first-search (DFS) algorithm, where one searches all possible paths from u to u, computes their representations (Equation 2 and aggregates the results (Equation [ Such formulation is capable of modeling several traditional link prediction methods, as well as graph theory algorithms. Formally, Theorem 3 state the corresponding path formulations for 3 link prediction methods and 2 graph theory algorithms respectively. See Appendix A for proofs.
and (ey(e) is the representation of edge e;. Note the
Theorem Katz index a path formulation with @ +, @ and w. (c) fww.
Theorem Personalized PageRank a path formulation with + +, 2 x and wy(e)
awwa/ Ev))()) Wye'
Theorem 3 Graph distance is path formulation with + min, X + and (e) = we-
Theorem 4 Widest path is path formulaton with @ max, min and w.(e) We-
Theorem Most reliable path a path formulation with @ max, 3 x and w. (e) We.
Generalized Bellman-Ford Algorithm. While the above formulation is able model important heuristics for link prediction, it is computationally expensive since the number of paths grows exponentially with the path length. Previous works | 62) that directly computes the exponential number of paths can only afford a maximal path length of 3. A more scalable solution is to use the generalized Beolman-Ford algorithm 4 Specifically, assuming the operators (0) ()) satisfy a semiring system 21 with summation identity U and multiplication identity Oip we have the following algorithm.
(u, <- 11(u== = v)
(3)
h (u,
1ol 10 (u,x) 8 w,(,,,
+ h
(0) (u, v)
(4)
where (u = v) is the indicator function that outputs i if = v and U, otherwise. w,, r, v) the representation for edge e = (ar, r, v) and r is the relation type the edge. Equation 3 is known as the boundary condition, while Equation is known as the Bellman-Ford iteration. The high-level idea of the generalized Bellman-Ford algorithm is to compute the pair representation (u v) for a given entity u, a given query relation q and all v E V in parallel, and reduce the

---

total computation by the distributive property of multiplication over summation. Since u and q are fixed in the generalized Bellman-Ford algorithm, we may abbreviate h
(1) (u, v) he when the
context is clear. When e = min and & = +. it recovers the original Bellman-Ford algorithm for the shortest path problem 5 See Appendix B for preliminaries and the proof of the above algorithm.
Theorem 6 Katz index, personalized PageRank, graph distance, widest path and most reliable path can be solved via the generalized Bellman-Food algorithm.
Table 2: Comparison of operators NBFNet and other methods from the view of path formulation.
Method
(ei(e) 2 myye))
MESSAGE
(y(()) # k,(2%)
AGOREGATE
INDICATOR
04- 0,
Edge Representatinn wylc)
Traditional
Karz Index
(4,(4) (n
(P) P.(Ps)
Run
Link
Personalized PageRank
(a(e) x my
hg(P) + h.(2))
0,1
awee EesViss Maat d
Prediction
Graph Distance
(,,( (es)
min(H,(P))
(PP.
+00,0
Graph Theory
Widest Path [
min, w (ea), (e)))
max (P.) (P))
-O0, +o0
Algorithms
Most Reliable Puth
16,(51 mn (1()))
(2..
Logle Rules
NeuralLP 69 /
(r,(s) x myye))
(P) + 1,)
0,1
Weights leurned by LSTM 23
DRUM 46
NBFNet
Relational operators of knowledge graph emherklings è 1S 52
Leaeed set aggregators y
Larned indicator functions
Leamed relation embeddings
3.2
Neural Bellman-Fort Networks
While the generalized Bellman-Ford algorithm can solve many classical methods (Theorem 6 these methods instantiate the path formulation with handcrafted operators (Table and may not be optimal for link prediction. To improve the capacity of path formulation, propose general framework, Neural Bellman- Ford Networks (NBFNet), to learn the operators in the pair representations.
Neural Parameterization. We relax the semiring assumption and parameterize the generalized Bellman-Ford algorithm (Equation 3 and 4 with neural fune- tions, namely INDICATOR, MESSAGE and AGGReGATE functions. The INDI- CATOR function replaces the indicator function 1g (u = v). The MESSAGE function replaces the binary multiplica- tion operator @ The AGGREGATE func-
Algorithm 1 Neural Bellman- Networks
Input: source node u. query relation q, #layers T Output: pair representations h, (u, v) for all E
1: for E V do
Boundary condition
2: h.)) + INDICATOR (, v,
3: end for
4: for +- to T do
Bellman-Forrd iteration
5: for u E do do
6:
MS <- (0)
D. Message augmentation
7:
for (I,r, 0) E Elv) do
tion is permutation invariant function
8:
m (1)
(a.r.)) + (ME ((-1), (,,
over sets that replaces the n-ary summa-
M! < M u { (4)
tion operator O Note that one may alter-
9:
natively define AGGREGATE as the com-
10:
end for h + (M
mutative binary operator and apply it to a sequence of messages. However, this will make the parameterization more complicated.
11:
12:
end for
13:
end for
14: return hTT) as (u v) for all E
Now consider the generalized Bellman-Fort Ford algorithm for a given entity u and relation g. In this context, we abbreviate h (1)( v) as 11.). i.e., a representation on entity v in the 1-th iteration. should be stressed that he is still a pair representation, rather than a node representation. By substituting the neural functions into Equation 3 [ we get our Neural Bellman-Ford Networks.
h INDICATOR(U, v, h
(5)
AGGREGATE ({ (MESSAGE
( w. (,, ()) e E(w) u (on))(((n))) (n()))
(6)
NBFNet can be interpreted as a novel GNN framework for learning pair representations. Compared to common GNN frameworks [32 48 that compute the pair representation as two independent node representations huzu) and h. (v), NBFNet initializes a representation on the source node u, and readouts the pair representation the target node v. Intuitively, our framework can be viewed as
5

---

source-specific message passing process, where every node learns a representation conditioned on the source node. The pseudo code of NBFNet is outlined in Algorithm !
Design Space. Now we discuss some principled designs for MESSAGE, AGGREGATE and INDI- CATOR functions by drawing insights from traditional methods. Note the potential design space for NBFNet is way larger than what is presented here, as one can always borrow MESSAGE and AGGREGATE from the arsenal of message-passing GNNs [19 16 60 65].
For the MESSAGE function, traditional methods instantiate as natural summation, natural mul- tiplication min over scalars. Therefore, may use the vectorized version of summation or multiplication. Intuitively, summation of ((-1) and (2, r, u) can be interpreted as a translation of
he-²1) by w2 7, v) in the pair representation space, while multiplication corresponds to scaling. Such transformations correspond to the relational operators [T8] [4]] in knowledge graph embed-
dings [6] 68 58 31 52 For example, translation and scaling are the relational operators used in
TransE 66 and DistMult 688 respectively. We also consider the rotation operator in RotatE [52]
The AGGREGATE function is instantiated as natural summation, max or min in traditional methods, which are reminiscent of set aggregation functions [7] 65 9 used in GNNs. Therefore, we specify the AGGREGATE function to be sum, mean, max, followed by a linear transformation and non-linear activation. We also consider the prineipal neighborhood aggregation (PNA) proposed in a recent work [9] which jointly learns the types and scales of the aggregation function.
The INDICATOR function is aimed at providing a non-trivial representation for the source node u as the boundary condition. Therefore, we learn a query embedding for D2 and define INDICATOR function as 1 (u = v)* q. Note it is also possible to additionally learn an embedding for Og. However, we find single query embedding works better in practice.
The edge representations are instantiated as transition probabilities or length in traditional methods. We notice that an edge may have different contribution in answering different query relations. Therefore, we parameterize the edge representations as a linear function over the query relation, i.e., wy(a, r, v) W + b,. For homogeneous graphs knowledge graphs with very few relations, we simplify the parameterization to W,, r, v) = b, to prevent overfitting, Note that one may also parameterize (,,,,, r, v) with learnable entity embeddings æ and v. but such parameterization cannot solve the inductive setting. Similar to NeuralLP [69] & DRUM 46), we use different edge representations for different iterations, which is able to distinguish noncommutative edges in paths,
e.g., father's 's mother v.s. mother's ' father.
Link Prediction. We now show how to apply the learned pair representations hy(u, v) to the link prediction problem. We predict the conditional likelihood of the tail entity u as p(ulu, g) = a (f(hg(u, r))). where (-) is the sigmoid function and f()) is feed-forward neural network. The
conditional likelihood of the head entity u can be predicted by p(uju, q 1) of 1 (V. u))) with the same model. Following previous works 52). we minimize the negative log-likelihood of positive and negative triplets (Equation (7p. The negative samples are generated according to Partial Completeness Assumption (PCA) [[4]. which corrupts one of the entities in a positive triplet to create negative sample. For undirected graphs, symmetrize the representations and define P,(u, v) = (h( v) + h, u))). Equation g shows the loss for homogeneous graphs
LKG = - -lo--oggpe Mogr(u,, q, v)
log(1 - -p(u's q, v())
n
Chomo - loo
log(1 - 10pppppu,,, uf)).
(8)
n
where n is the number of negative samples per positive sample and (u4, q, v/) and (u/, uf) are the i-th negative samples for knowledge graphs and homogeneous graphs, respectively.
Time Complexity. One advantage of NBFNet is that it has a relatively low time complexity during inference 3 Consider a scenario where a model is required to infer the conditional likelihood of all possible triplets p(uju, q). We group triplets with the same condition u, g together, where each group contains |V triplets. For each group, we only need to execute Algorithm once to get their
'Athhough the same analysis can be applied to training on fixed number of samples, we note it is less instructive since one can trade-off' samples for performance, and the trade-off varies from method to method.

---

predictions. Since a small constant number of iterations T is enough for NBFNet to converge (Table 6b). Algorithm has time complexity of O(EE Vld²). where d is the dimension of representations. Therefore, the amortized time complexity for a single triplet is O LEd detailed derivation of time complexity of other GNN frameworks, please refer to Appendix C
[V + d² For
4 Experiment
4.1 Experiment Setup
We evaluate NBFNet three settings, knowledge graph completion, homogeneous graph link prediction and inductive relation prediction. The former two transductive settings, while the last is an inductive setting. For knowledge graphs, we use 15k-k-25 15k-237 [56] and WN18RR [13]. We use
the standard transductive splits [56] [3] and inductive splits 555 of these datasets. For homogeneous
graphs, we use Cora, Citeseer and PubMed [49]. Following previous works [32 12]. we split the
edges into train/valid/test with ratio of 85:5:10. Statistics of datasets can be found in Appendix b
Additional experiments of NBFNet on OGB (55 datasets can be found in Appendix G
Implementation Details. Our implementation generally follows the open source codebases of knowledge graph completiorDandd homogeneous graph link predictior For knowledge graphs, we follow [69 46 and augment each triplet (u, 4, 1) with flipped triplet {v q- u). For homogeneous graphs we follow [33 32 and augment each node u with a self loop (u, u). We instantiate NBFNet with 6 layers, each with 32 hidden units. The feed-forwart network f(-) is set to 2-layer MLP with 64 hidden units. ReLU is used as the activation function for all hidden layers. We drop out edges that directly connect query node pairs during training to encourage the model to capture longer paths and prevent overfitting, Our model is trained on 4 Tesla V100 GPUs for 20 epochs. We select the models based on their performance on the validation set. See Appendix FrpendixFforrr more details.
Evaluation. We follow the filtered ranking protocol (6] for knowledge graph completion. For a test triplet (4, q, v). we rank it against all negative triplets (u, q, v²) or (u 4, v) that do not appear in the knowledge graph. We report mean rank (MR), mean reciprocal rank (MRR) and HITS at N (H@N) for knowledge graph completion. For inductive relation prediction, we follow (55 and draw 50
negative triplets for each positive triplet and use the above filtered ranking. We report HITS @ 10 for inductive relation prediction. For homogencous graph link prediction, the positive edges against the same number of negative edges. We report area under the receiver operating characteristic curve (AUROC) and average precision (AP) for homogeneous graphs.
follow [32) and compare
Baselines. We compare NBFNet against path- methods, embedding methods, and GNNs. These include 11 baselines for knowledge graph completion, 10 baselines for homogeneous graph link prediction and baselines for inductive relation prediction. Note the inductive setting only includes path-based methods and GNNs, since existing embedding methods cannot handle this setting.
4.2 Main Results
JubleJsummarizes the results on knowledge graph completion. NBFNet significantly outperforms existing methods all metrics and both datasets. NBFNet achieves average relative gain of 21% in HITS@ @1 compared to the best path-based method, DRUM 446. on two datasets. Since DRUM is a special instance of NBFNet with natural summation and multiplication operators. this indicates the importance of learning MESSAGE and AGGREGATE functions in NBFNet. NBFNet also outperforms the best embedding method, LOwFER [.. with an average relative performance gain of 18% in HITS@ @1 on two datasets. Meanwhile, NBFNet requires much less parameters than embedding methods. NBFNet only uses 3M parameters on FB15k-237, while TransE needs 30M parameters. See Appendix D for details on the number of parameters.
Table 4 shows the results on homogeneous graph link prediction. NBFNet gets the best results on Cora and PubMed, meanwhile achieves competitive results on CiteSeer. Note CiteSeer is extremely sparse (Appendix E). which makes it hard to learn good representations with NBFNet. One thing to note here is that unlike other GNN methods, NBFNet does not use the node features provided by
http:///ghhhha..oooopppppppee/ep https::/gittuub.cmm///
MIT license.
MIT license.
7

---

Table Knowledge graph completion results. Results of NeuraLP and DRUM are taken from [46].
Results of RotatE, HAKE and LowFER are taken from their original papers [2 76 I.. Results of the other embedding methods are taken from [52]. Since Grall. has scalability issues in this setting, we evaluate it with 50 and 100 negative triplets for FB15k-237 and WN18RR respectively and report
MR based on an unbiased estimation.
FB15K-237
WNI8RR
Class
Method
MRR
H@1
H@3
H@10
MR
MRR
H@1
H@3
H@
Ranking
3521
0.174
0.119
0.285
0.324
0.360
Path-based
NeuralLP (69
0.240
0.362
0,435
0.371
0.434
0.566
DRUM 46
0.343
0.255
0.378
0,516
0.486
0.425
0.513
0.586
TransE 0
357
0.294
0,465
3384
0.226
0.501
DistMult 68
254
0.241
0.155
0.263
0.419
5110
0.43
0.39
0.44
0.49
Embeddings
ComplEx
339
0.247
0.158
0.275
0.428
5261
0.44
0.41
0.46
0.51
RotarE 52
0.338
0.241
0.375
0.553
3340
0.476
0.428
0.492
0.571
HAKE 76
0.346
0.250
0.381
0,542
0.497
0.452
0.516
0.582
LowFER
0.359
0.266
0.396
0,544
0.465
0.434
0.479
0.526
RGCN 48
221
0.273
0.182
0.303
0.456
2719
0.402
0.345
0.437
0.494
GNNs
GralL 55
2053
2539
NBFNet
0.415
0.321
0.454
0,599
0.497
0.573
Table 4: Homogeneous graph link prediction results. Results of VGAE and S-VGAE are taken from
their original papers 32
12
Cora
Citeseer
PubMed
Class
Method
AUROC
AP
AUROC
AP
AUROC
AP
Katz Index
0.834
0.889
0.768
0.810
0.757
0.856
Path-based
Personalized
PageRank 42
0.845
0.899
0.762
0.814
0.763
0,860
SimRank
28
0.838
0.888
0.755
0.805
0.743
0.829
DeepWate Walk
0.831
0.850
0.805
0.836
0.844
0.841
Embeddings
LINE 33
0.844
0.876
0.791
0.826
0.849
0,888
node2vec 17
0.872
0.879
0.838
0.868
0.891
0.914
VGAE 32
0,914
0.926
0.908
0.920
0.944
0,947
S- S-VGAE 12
0,941
0.941
0.947
0.952
0.960
0,960
GNNs
SEAL 73
0,933
0.942
0.905
0.924
0.978
0.979
TI.C-GNN 67
0.934
0.931
0.909
0.916
0.970
0.968
NBFNet
0.956
0.962
0.923
0.936
0.983
0.982
Table 5: Inductive relation prediction results (HITS@ 10).
V1-v4 corresponds to the 4 standard versions of inductive splits. Results of compared methods are taken from [53].
237
WNISRR
Class
Method
v1
v2
v3
v4
v1
v2
v3
NeuralLP 16
0.529
0.589
0.529
0.559
0.744
0.689
0.462
0.671
Path-based
DRUM
0.529
0.587
0,529
0.559
0.744
0.689
0.462
0.671
RuleN 39
0.498
0.778
0.877
0.856
0.809
0.782
0.534
0.716
GralL 55
0.642
0.818
0.828
0.893
0.825
0.787
0.584
0.734
GNNs
NBFNet
0.834
0.949
0.951
0.960
0.948
0.905
0.893
0.890
the datasets but is still able to outperform most other methods. We leave how to effectively combine node features and structural representations for link prediction
future work.
summarrzee the results on inductive relation prediction. On all inductive splits of two datasets, NBFNet achieves the best result. NBFNet outperforms the previous best method, GralL [55], with an average relative performance gain of 22% HITS @ 10. Note that Grall. explicitly encodes the local subgraph surrounding each node pair and has a high time complexity (Appendix C). Usually, Grall. can at most encode 2-hop subgraph, while our NBFNet can efficiently explore longer paths.
4.3 Ablation Study
MESSAGE & AGGREGATE Functions. Table 6a shows the results of different MESSAGE and AGGREGATE functions. Generally, NBFNet benefits from advanced embedding methods (DistMult,

---

RotatE > TransE) and aggregation functions (PNA > sum, mean, max). Among simple AGGREGATE functions (sum, mean, max), combinations of MESSAGE and AGGREGATE functions (TransE max, DistMult & sum) that satisfy the semiring assumption of the generalized Bellman-Ford algorithm, achieve locally optimal performance. PNA significantly improves over simple counterparts, which highlights the importance of learning more powerful AGGREGATE functions.
Number of GNN Layers. Table 6b compares the results of NBFNet with different number of layers. Although it has been reported that GNNs with deep layers often result in significant performance drop 36 777. we observe NBFNet does not have this issue. The performance increases monotonically with more layers, hitting saturation after 6 layers. We conjecture the reason is that longer paths have negligible contribution, and paths not longer than are enough for link prediction.
Performance by Relation Category. We break down the performance of NBFNet by the categories of query relations: one-to-one, one-to-many, many-to-one and many-to-many" prediction results for each category. It is observed that NBFNet not only improves on easy one-to-one cases, but also on hard cases where there are multiple true answers for the query.
[ Table shoows the
Table 6: Ablation studies of NBFNet on FB15k- 137. Due to space constraints, only report MRR here. For full results on all metrics, please refer to Appendix H
(a) Different MESSAGE and AGGREGATE functions.
(b) Different number of layers.
AGGREGATE
#Layers (T)
MESSAGE
Method
Sum
Mean
Max
PNA
2
TransE 66]
0,297
0.310
0.377
0.383
NBFNet
0.345
0.409
0.415
0.416
DistMult 69
0.388
0.384
0.374
0.415
RotatE 52
0.392
0.376
0.385
0.414
(c) Performance w.r.t. relation category. The two scores are the rankings over heads and tails respectively.
Relation Category 1-to-N
Method
1-to-1
N-to-1
N-to-N
TransE 6
0.498/0.488
0.455/0.071
0.079/0.744
0.224/0.330
RotatE [1] NBFNet
0.487/0.484
0.467/0.070
0,081/0.747
0.234/0.338
0.578/0.600
0.499/0.122
0.165/0.790
0.348/0.456
4.4 Path Interpretations of Predictions
One advantage of NBFNet is that can interpret its predictions through paths, which may be important for users to understand and debug the model. Intuitively, the interpretations should contain paths that contribute most to the prediction p(u, q, e). Following local interpretation methods (2.72. we approximate the local landscape of NBFNet with a linear model over the set of all paths, i.e., 1st-order Taylor polynomial. We define the importance of a path as its weight in the linear model, which can be computed by the partial derivative of the prediction w.r.t. the path. Formally, the top-k path interpretations for ((u,0 q, v) are defined as
Op(u,g.u) aP
Pr. Ps. PE = top-k
PEP...
Note this formulation generalizes the definition of logical rules 669 46 to non-linear models. While directly computing the importance of all paths is intractable, importance. Specifically, the importance of each path is approximated by the sum of the importance of edges in that path, where edge importance is obtained via auto differentiation. Then the top-k path interpretations are equivalent to the top-k longest paths on the edge importance graph, which can be solved by Callman-Ford-styyy beam search. Better approximation is left as a future work.
approximate them with edge
visualizes path interpretations from FB15k-237 test set. While users may have different Table 7
insights towards the visualization, here is our understanding. 1) In the first example, NBFNet leams
Here semiring is discussed under the assumption of linear activation functions. Rigorously, no combination satisfies a semiring if we consider non- non-linen linearity in the model.
'The categories are detined same as 633. We compute the average number of tails per head and the average number of heads per tail. The category is one if the average number is smaller than 1.5 and many otherwise.

---

soft logical entailment, such as impersonate A nationality distribution = nationality. 2) In second example, NBFNet performs analogical reasoning by leveraging the fact that Florence is similar to Rome. 3) In the last example, NBFNet extracts longer paths, since there no obvious connection between Pearl Harbor (film) and Japanese language.
nationality and ethnicity A
Table 7: Path interpretations of predictions FB15k-237 test set. For each query triplet, visualize the t path interpretations and their weights. Inverse relations are denoted with a superscript -!.
Query
(u. q. v): (0. Hardy, nationality, U.S.)
0.243
(0. Hardy, impersonate" 3, R. Litle) A (R. Litle, nationality, U.S.)
0.224
(O. Handy, ethnicity" Scottish American) A (Scottish American, distribution, U.S.)
Query
(u, q. v): (Florence, vacationer, D.C. Henrie)
0.251
(Plorence, contain Italy) A (Italy, capital, Rome) A (Rome, vacationer, D. Henrie) (Florence, place live G.F. Handel) A (G.F. Handel, place live, Rome) A (Rome, vacationer, D.C. Henrie)
0.183
Query
(u. q. v): (Peart Harbor (film), language, Japanese)
0.211 (Pearl Harbor (füm), film actor, C.-H. Tagawa) A (C.-H Tagawa, nationality, Japan)
h. (Japan, country of origin, Yu-Gi-Oh!) (Ye-GI-Oh!, language, Japanese)
0.208
(Peart Harbor (film), film actor, C.-.. Tagawa) A (C.-H. Tagawa, nationality, Japan) (Jupan, official language, Japanese)
5
Discussion and Conclusion
Limitations. There are a few limitations for NBFNet. First, the assumption of the generalized Bellman-Ford algorithm requires the operators (0, @) to satisfy a semiring. Due to the non-linear activation functions in neural networks, this assumption does not hold for NBFNet, and we do not have a theoretical guarantee on the loss incurred by this relaxation. Second, NBFNet is only verified on simple edge prediction, while there are other link prediction variants, e.g., complex logical queries with conjunctions (A) and disjunctions (V) [8 45). In the future, we would like to how NBFNet approximates the path formulation, as well as apply NBFNet to other link prediction settings.
Social Impacts. Link prediction has wide range of beneficial applications, including recommender systems, knowledge graph completion and drug repurposing. However, there are also some potentially negative impacts. First, NBFNet may encode the bias present in the training data, which leads to stereotyped predictions when the prediction is applied to a user on a social or e-commerce platform. Second, some harmful network activities could be augmented by powerful link prediction models, e.g., spamming, phishing, and social engineering. We expect future studies will mitigate these issues.
Conclusion. We present representation learning framework based on paths for link prediction. Our path formulation generalizes several traditional methods, and can be efficiently solved via the generalized Bellman-Ford algorithm. To improve the capacity of the path formulation, NBFNet, which parameterizes the generalized Bellman-Ford algorithm with learned INDICATOR, MESSAGE, AGGREGATE functions. Experiments on knowledge graphs and homogeneous graphs show that NBFNet outperforms a wide range of methods in both transductive and inductive settings.
propose
Acknowledgements
We would like to thank Komal Teru for discussion on inductive relation prediction, Guyue Huang for discussion on fused message passing implementation, and Yao Lu for assistance on large-scale GPU training. We thank Meng Qu, Chence Shi and Minghao Xu for providing feedback on our manuscript.
This project is supported by the Natural Sciences and Engineering Research Council (NSERC) Discovery Grant, the Canada CIFAR AI Chair Program, collaboration grants between Microsoft Research and Mila. Samsung Electronics Co., Ltd., Amazon Faculty Research Award, Tencent AI Lab Rhino-Bire Gift Fund and a NRC Collaborative R&D Project (44)-CCREE-6). This project was also partially funded by IVADO Fundamental Research Project grant PRF-2019-333 9-989331397777 The computation resource of this project supported by Calcul Québed
and and Compute Canada 10
http://wwww..aclllueeeeeea ca/
httpp://www/ httper//www.cppptteeadaaaaa computecanada.ca/
10

---

References
[1] Saadullah Amin, Stalin Varanasi, Katherine Ann Dunfield, and Günter Neumann. Lowfer: Low- rank bilinear pooling for link prediction. In International Conference on Machine Learning, pages 257-268. PMLR, 2020.
[2] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. arXiv preprint 1607 2016.
[3] David Bachrens, Timon Schroeter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Robert Müller. How to explain individual classification decisions. The Journal of Machine Learning Research, 11:1803-1831. 2010.
[4] John S Baras and George Theodorakopoulos. Path problems in networks. Synthesis Lectures on Communication Networks, 3(1):1-77, 2010.
[5] Richard Bellman. On routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958.
[6] Antoine Bordes, Nicolas Usumier, Alberto Garcia-Duram, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems, pages 1-9, 2013.
[7] Linlin Chao, Jianshan He, Taifeng Wang, and Wei Chu. PairRE: Knowledge graph embeddings via paired relation vectors. In Proceedingy of the 59th Annual Meeting of the Association for Computational Linguisties and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Pupers), pages 4360-4369, 2021.
[8] Wenhu Chen, Wenhan Xiong, Xifeng Yan, and William Yang Wang. Variational knowledge graph reasoning. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long Papers), pages 1823-1832, 2018
[9] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. volume 33, 2020.
[10] Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, and Andrew McCallum. Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In International Conference on Learning Representations, 2018.
[11] Rajarshi Das, Arvind Neelakantan, David Belanger, and Andrew McCallum. Chains of reasoning over entities, relations, and text using recurrent neural networks. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 132-141, Valencia, Spain, April 2017. Association for Computational Linguistics.
[12] Tim R Davidson, Luca Falorsi, Nicola De Cao, Thomas Kipf, and Jakub M Tomezak. Hyper- spherical variational auto-encoders. 2018.
[13] Tim Dettmers, Pasquale Minervini, Pontus Stenetorp. and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018
[14] Luis Antonio Galárraga, Christina Teflioudi, Katja Hose, and Fabian Suchanek. Amie: associa- tion rule mining under incomplete evidence in ontological knowledge bases. In Proceedings of the 22nd international conference on World Wide Web, pages 413-422, 2013.
[15] Matt Gardner and Tom Mitchell. Efficient and expressive knowledge base completion using subgraph feature extraction. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1488 1498,,19,,10 2015.
[16] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263-1272. PMLR, 2017.

---

[17] Aditya Grover and Jure Leskovec. node2vee: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
[18] William L Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. In Advances in Neural Information Processing Systems, pages 1030-2041 2018.
[19] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1025-1035, 2017.
[20] Zhen Han, Peng Chen, Yunpu Ma, and Volker Tresp. xerte: Explainable reasoning temporal knowledge graphs for forecasting future links. 2021.
[21] Udo Hebisch and Hanns Joachim Weinert. Semirings: algebraic theory and applications in computer science, volume 5. World Scientific, 1998.
[22] Marcel Hildebrandt, Jorge Andres Quintero Serna, Yunpu Ma. Martin Ringsquandl, Mitchell Joblin, and Volker Tresp. Reasoning on knowledge graphs with debate dynamics. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4123-4131 2020.
[23] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 18)5:1735-1780, 1997.
[24] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb- Isc: A large-scale challenge for machine learning on graphs. arXiv preprint arXiv:2103.09430, 2021.
[25] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs arXiv preprint N0iv:2005.00687. 2020.
[26] Guyue Huang, Guohao Dai, Yu Wang, and Huazhong Yang. Ge-spmm: Gerpral-purpose sparse matrix-matrix multiplication on gpus for graph neural networks. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-12.
IEEE, 2020.
[27] Vassilis N Ioannidis, Da Zheng, and George Karypis. Few-shot link prediction via graph neural networks for covid- 19 drug-repurposing. arXiv preprint arXiv:2007. 10261, 2020.
[28) Glen Jeh and Jennifer Widom. Simrank: measure of structural-context similarity. In Proceed- ings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 538-543 2002.
[29] Glen Jeh and Jennifer Widom. Scaling personalized web search. In Proceedings of the 12th international conference on World Wide Web, pages 271-279, 2003.
[30] Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-4) 43. 1953.
[31] Seyed Mehran Kazemi and David Poole. Simple embedding for link prediction in knowledge graphs. In Advances in Neural Information Processing Systems, pages 4289-4300, 2018.
[32] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:
2016.
[33] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[34] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 4208):30-37, 2009.
[35] Ni Lao and William W Cohen. Relational retrieval using a combination of path-constrained random walks. Machine learning, ((():53-67,2011
12

---

[36] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 32, 2018.
[37] David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks Journal of the American society for information science and technology, 58(7):1019-1031, 2007.
[38] Xi Victoria Lin, Richard Socher, and Caiming Xiong. Multi-hop knowledge graph reasoning with reward shaping. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing, EMNLP 2018, Brussels, Belgium, October 31-November 4, 2018, 2018.
[39] Christian Meilicke, Manuel Fink, Yanjie Wang, Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt. Fine-grained evaluation of rule-and embedding- based systems for knowledge graph completion. In International Semantic Web Conference, pages 3-20. Springer, 2018.
[40] Arvind Neelakantan, Benjamin Roth, and Andrew McCallum. Compositional vector space models for knowledge base completion. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 156-166, Beijing, China, July 2015. Association for Computational Linguistics.
[41] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11-33, 2015.
[42] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd, The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
[43] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pages 701-710, 2014.
[44] Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua Bengio, and Jian Tang. Rnnlogic: Learning logic rules for reasoning on knowledge graphs In International Conference Leurning Representations, 2021.
[45] Ren, W Hu, and Leskovee. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In International Conference on Learning Representations, 2020.
[46] Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to-end differentiable rule mining knowledge graphs. volume 32, pages 15347-15357, 2019.
[47] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks, 20(1):61-88) 80, 2008.
[48] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pages 593-607. Springer, 2018.
[49] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93 93, 2008.
[50] Yelong Shen, Jianshu Chen, Po-Sen Huang, Yuqing Guo, and Jianfeng Gao. M-walk: learning to walk over graphs using monte carlo tree search. In Advances in Neural Information Processing Systems, pages 6787-6798, 2018.
[51] Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S Yu, and Tianyi Wu. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. volume 4, pages 992-1003. VLDB Endowment, 2011.
[52] Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph em- bedding by relational rotation in complex space. In International Conference on Learning Representations, 2019.
13

---

[53] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. Proceedings of the 24th international conference on World Wide Web, pages 1067-1077, 2015.
[54] Yun Tang, Jing Huang, Guangtao Wang. Xiaodong He, and Bowen Zhou. Orthogonal relation transforms with graph context modeling for knowledge graph embedding. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2713-2722, 2020.
[55] Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, pages 9448-9457, PMLR, 2020.
[56] Kristina Toutanova and Danqi Chen, Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd workshop on continuous vector space models and their compositionality, pages 57-66, 2015.
[57] Kristina Toutanova, Xi Victoria Lin, Wen-tau Yih, Hoifung Poon, and Chris Quirk. Composi- tional learning of embeddings for relation paths in knowledge base and text. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1434-1444, 2016.
[58] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International Conference Machine Learning, pages 2071-2080. PMLR, 2016.
[59] Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition- based multi-relational graph convolutional networks. In International Conference on Learning Repre- sentations, 2020.
[60] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[61] Andrew Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE transactions on Information Theory, 13(2):260 269, 1967.
[62] Hongwei Wang, Hongyu Ren, and Jure Leskovec. Relational message passing for knowledge graph completion. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1697-1707, 2021.
[63] Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by translating hyperplanes. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 28, 2014.
[64] Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP 2017), Copenhagen, Denmark, September 2017. ACL.
[65] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[66] Xiaoran Xu, Wei Feng. Yunsheng Jiang, Xiaohui Xie, Zhiqing Sun, and Zhi-Hong Deng. Dynamically pruned message passing networks for large-scale knowledge graph reasoning. In International Conference on Learning Representations, 2019.
[67] Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, and Chao Chen. Link prediction with persistent homology: An interactive view. In International Conference Machine Learning, pages 11659-11669, PMLR, 2021.
[68] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In International Conference on Learning Representations, 2015.
14

---

[69] Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. Advances in Neural Information Processing Systems, pages 2316-2325, 2017.
[70] Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10737-10745, 2021.
[71] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. volume 30, 2017.
[72] Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks, In European conference on computer vision, pages 818-833. Springer, 2014.
[73] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. volume 31, pages 5165-5177 2018.
[74] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Revisiting graph neural networks for link prediction. arXiv preprint 20I1::2000016103,3 2020.
[75] Yongqi Zhang, Quanming Yao, Wenyuan Dai, and Lei Chen. Autosf: Searching scoring functions for knowledge graph embedding. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pages 433-444. IEEE, 2020.
[76] Zhanqiu Zhang, Jianyu Cai, Yongdong Zhang, and Jie Wang. Learning hierarchy-aware knowledge graph embeddings for link prediction. In Proceedings the Artificial Intelligence, volume 34, pages 2065-3072, 2020.
the AAAI Conference on
[77] Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations, 2019.
[78] Zhaocheng Zhu, Shizhen Xu, Meng Qu, and Jian Tang. Graphvite: A high- seach-eerfrrmmnce cpu-gpu hybrid system for node embedding. In The World Wide Web Conference, pages 2494-2504, 2019.
15


Reviews:
[{"review_id": "mE2YLOeW9Mg", "reviewer": "Reviewer_5weJ", "summary": "Summary: In this study the authors propose a general framework to learn neural INDICATOR, MESSAGE and AGGREGATE functions for the generalized Bellman-Ford (BF) algorithm. They apply the neural BF to link prediction problems in multirelational knowledge graphs in the in-sample setting as well as in the out-of-sample setting, and in homogeneous graphs. On a practical level the approach trades compute with memory and shows good results on benchmark datasets.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The approach combines the generalized BF algorithm with learnables neural operators and sets the approach well in context with previous work. \n \nQuality: The paper does not provide a proof or error bounds on the solution it can find. The study describes the proposed approach formally well but its usefulness is mostly backed up by empirical results. The approach is explored well, however, an aspect that was missing ---as the approach is very expensive--- it would be fair and important to show the compute trade-off as well as the memory trade-off for each of the groups (path-based, embedding, GNN) with the proposed approach in the performance comparison, as I don’t think it that they should be decoupled in such comparisons. While it does well regarding memory with embedding based methods, it does a lot worse compared to GRCN and even more so compared to embedding based methods. \n\nThe experimental results do not cite state of the art results for FB15k-237 and WNRR which are for FB15k-237 much closer to the results obtained by the proposed approach. Complex achieves 0.37 MRR on Fb15k-237 and 0.49 MRR on WN18RR [1]. There are methods and dataset for out-of-sample settings for knowledge graph completion [2] that should be considered in the comparison. \n\nAnother concern about the knowledge graph completion experiment ---and the evaluation description was not explicit about this and no code was provided--- is, which graph is known by the model during evaluation? Does it consist of (1) the training triples, or (2) the training-triples + the validation triples, or (3) the training+validation+testing triples (minus each testing triple once it is under evaluation of course)? Sometimes path-based methods use (2) or (3) which naturally leads to better results. Can the authors explicitly confirm which of the settings was the one that was used? For knowledge graph embedding methods the known graph corresponds to (1), i.e. only the training triples. If this is different in this study, then a performance comparison between embedding methods and this proposed method is not possible.  \n\nOne attractive property of the model is that the highest scoring paths can be inspected which can lead to new insights about datasets. \n\nClarity: The paper is written well and the presentation is great. The experimental setup could be clearer. \n\nSignificance: If the concerns can be ruled out, then the result would be important.  The method achieves good numbers on benchmark datasets. There is great interest in interpretable methods as well, which this method also does provide.   \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and societal impact have been addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "YtTa8r8yGSB", "reviewer": "Reviewer_QoNE", "summary": "The paper proposes an adaptive version of the generalised Bellman-Ford algorithm to solve link prediction problems in both knowledge bases and inductive settings. The resulting formulation is a slight variation of a standard graph neural network that accomodates different types of relations and computes pairwise node representations, that is, a different representation of node v for each neighbour.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper undoubtedly has merits, such as:\n\n- Mentioning the similarities between the usual message passing formulation of GNNs and the aforementioned algorithm.\n- Conducting an experimental comparison that looks fair (though something must be clarified by the authors), obtaining results that consistently surpass previous works. Despite this consistency ironically raising a red flag at the beginning, to the best of my knowledge the results seem solid. This may be attributed to the more general formulation (w.r.t. link prediction) of the proposed approach. Unfortunately, the code to inspect all the model selection and assessment phases is not available.\n\nWith that being said, the general feeling after reading the article is that it may have been written in a rush. This is due to the organisational choices and technical definitions that make it difficult to follow the discussion and are confusing in more than one passage. Moreover, some of the crucial claims of the authors about scalability and model capacity are mostly described in the appendix. Generally speaking, this may be perceived as unfair practice: appendices should support the main claims rather than address them. In other words, without reading the appendix, a reviewer would be unable to comprehensively evaluate all the claims made by these authors.\n\nAs concerns interpretability (the term is - wrongly - used intercheangebly with \"explainability\" by the authors), one of the fundamental challenges to be addressed by the authors, there is no solid qualitative evidence that the model, quote, \"learns soft logical entailment\" or \"performs analogical reasoning\". The three examples of Table 6 do not appear to be that meaningful. While we can argue about the most effective ways to \"prove\" interpretability, the evidence proposed by the authors cannot be considered sufficient.\n\nOverall, it appears that the authors made too many claims and were unable to properly fit them into a single conference paper. While the idea and results are (again) noteworthy, the quality of the paper definitely suffers because of its presentation, and this has to be taken into consideration given the level of the conference. Improving the manuscript in this sense may require substantial rewritring that might not be feasible at this point.\n\nTechnical comments:\n\nAbstract: \n\n- please specify that the generalized sum is over the paths *between the nodes*.\n- \"very general\" may be omitted\n\nSection 1:\n\n- Table 1 contains symbols that have not yet been introduced. Consider moving it at the end of Section 3. Also, a practical example of the MESSAGE, AGGREGATE and INDICATOR functions used in this work may help the reader.\n\nSection 2:\n\n- Could the authors please clarify why, on line 107, it is stated that autoencoders based on GNN do not work on the inductive setting? GNNs work on this setting off-the-shelf, so it is unclear to me why they should not generalise to new graphs at inference time. The authors reiterate this concept throughout the manuscript, including in Table 7 when R-GCN is defined as non-inductive, but it would be helpful to be on the same page about this.\n\nSection 3:\n\n- The mathematical formalisation is broken in more than one way, which makes the discussion confusing in many ways.\n  = The use of the query symbol q is ambiguous. Is it on of the possible relations in R, or is it a triple (see table 6)?\n  = The same is true for the definition og an edge: is it a tuple (u,v) or a triple (u,r,v)?\n  = Similarly, w(e) != w(u,r,v) according to the definitions in the paper\n  = Eqs 7 and 8: I believe the use of the expectation symbol in place of the mean is inappropriate. There are no formal distribution or random variables specified here. Please consider replacing the occurrences of the expectation with a uniformly weighted summation over the triples.\n- Possible typo in Eq 4: should h_q^{(0)}  be should h_q^{(t-1)}?\n\n- A suggestion: the abbreviation used before Eq 4 will confuse a lot of readers. The authors may consider expanding the notation despite its verbosity.\n\n- What do the authors mean by \"relatively low time complexity\"? Is NBFNet truly scalable or not? It seems not, given the inference time comparison of Table C (which should have been included in the main article). Moreover, is it also scalable at training time? 17 hour for 20 epochs on PubMed seems a very slow training time.\n\n- In general, it is not true that homogeneous graphs are undirected. Please rephrase.\n\nSection 4:\n\n- Why AllPath is not included in the empirical comparison? The authors stated it is the most similar solution compared to NBFNet, so we are expecting at least a comparison in the tables.\n- Also, it would be nice to include a simple inductive baseline in Table 3 that applies a simple transformation to the node features before computing a link prediction score. On a personal note, I found out this strategy obtains very similar results to the ones reported by the authors.\n\n- Table 5: did the authors fix the architecture, that is, 6 layers, based on the test results of Table 5? This would be a grave mistake (that would partially explain the consistent performance improvements over other methods). Please provide an honest answer.\n\n- Could the authors please detail how Eq 9 generalizes logical rules to non-linear models? It seems quite a statement, but there is no enough evidence to support this.\n\nBibliography: \n\nPlease consider better referencing the literature rather than citing directly most papers as arxiv preprints. As the authors know, other authors benefit from having their work indexed as part of a conference rather than as a preprint. Here, there are pretty obvious examples of arxiv-referenced papers that have already been published at important conferences.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "T2HBy9fAPuL", "reviewer": "Reviewer_HJVx", "summary": "This paper considers a link prediction framework called Neural Bellman-Ford Networks. The idea is to encode the relational structure between two nodes by using GNN message passing. The key here is to put the identity of the source node in the input feature. The provided framework demonstrates SoTA performance on the link prediction and KG completion datasets. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an interesting work in link prediction, and the performance is impressive. However, my biggest concern is the limited novelty, especially compared to the ID-GNN [1], which is not cited in the paper. ID-GNN already introduces the idea of using the node identity information in GNN's message passing and the idea of reformulating the link prediction as a conditional node prediction problem. \n\nHence, the main technical contributions of this paper are\n(1) Show the theoretical connection to PPR, Katz index, etc (Table 1)\n(2) Show more extensive experiments than ID-GNN.\n(3) More ablation studies than ID-GNN.\n\nI think the work still has some value. Especially, given that the experiments in ID-GNN are rather weak (mainly using synthetic graphs), this work serves as the empirical demonstration of the effectiveness of the ID-GNN framework in larger datasets.\n\nOne thing that would make this work more impactful from an empirical point of view is to try more established and standardized graph benchmarks such as the Open Graph Benchmark.  Both homogeneous and KG tasks are available, so it'd be great if authors can demonstrate the effectiveness there.\n\nOverall, I enjoyed reading the paper, but it misses an important related work of [1]. I think this paper requires substantial reframing (not to over-claim the novelty, clarify the contribution given [1]) before being published at a conference.\n\n[1] You et al. AAAI 2021 https://arxiv.org/abs/2101.10320\n\n=============Post-rebuttal\nThe authors' response addressed my comments; Hence, I increased my score to 7. While I do believe careful reframing of the paper in light of the very relevant P-GNN is necessary, the big strength of the paper is in empirically demonstrating that a completely novel paradigm can outperform exiting KGE methods. Especially, it is impressive to see the methods can be even scaled up to the OGB-LSC graph.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, may need to discuss more extensively on ID-GNN.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}, {"review_id": "FocWc8PpA-c", "reviewer": "Reviewer_4kGi", "summary": "1. This paper proposes a new method for Link Prediction dubbed NBFNet, which is a hybrid approach that combines path based and GNN based approaches for Link Prediction. \n2. The core idea of the paper is about computing the representation of a pair of nodes, which is used for predicting links between the nodes. This representation is computed using three neural operators namely INDICATOR, MESSAGE and AGGREGATE, which represent the parameterised version of Bellman-Ford algorithm. \n3. Authors present experimental results on the tasks of Knowledge graph completion, link prediction in homogenous graphs, and inductive relation prediction. The proposed method performs better than the baseline models in all the tasks.\n4. In addition, authors also perform ablation study with different MESSAGE & AGGREGATION functions. Furthermore, they also analyse the performance of NBFNet on different categories of relations. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. The proposed method seems novel, the idea of using a parameterised Bellman-Ford algorithm is a neat one. \n2. AGGREGATE functions used in the paper are sum, mean, or max followed by a linear transformation and a non-linear activation, and PNA. Just curios, why didn't the authors not consider a weighted sum, with learnable weights? All the paths may not be equally important for computing the representation.\n3. I am fairly satisfied with the quality and writing of the paper, I was able to follow the ideas in the paper without much struggle.\n4. I am not completely satisfied with the experimental results.  NBFNet outperforms the other baselines in all the mentioned tasks, but the authors need to compare with more recent baselines. \nAuthors should include at least a few of the following more recent baselines in their comparison. Or discuss why they are not relevant, if that is the case. \nCurrently, the most recent baseline they include is from 2018. \n\n- LowFER: Low-rank Bilinear Pooling for Link Prediction, Amin et al, ICML 2020. \n- A Multi-Scale Approach for Graph Link Prediction. Cai et al, AAAI 2020. \n-  Learning Hierarchy-Aware Knowledge Graph Embeddings for Link Prediction, Zhang et al , AAAI 2020. \n- Contextual Parameter Generation for Knowledge Graph Link Prediction, Stocia et al, AAAI 2020. \n- Link Prediction with Persistent Homology: An Interactive View, Yan et al, ICML 2021. \n\n\n===== \nPost author-response. \nAfter reading all the reviews and authors response. I have decided to keep my score the same. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please refer to the Main Review section. \n\nIf authors include more recent baselines in their experimental comparison, I am open to revising my recommendation. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed NBFNet a framework based on GNNs for representation learning tasks on graphs. All the reviewers agreed that the paper presents quite impressive empirical results and the proposed method is novel. There was also a general agreement amongst the reviewers that the paper seemed to be written in a rush and hence clarity was an issue. After taking into account the authors' responses it was decided that the paper is marginally above the acceptance threshold. I recommend acceptance and strongly urge the authors to improve the final camera ready version and take the reviewers' comments into account.
Decision: Accept (Poster)