Distance-Based Propagation for Efficient Knowledge Graph Reasoning
Authors: Harry Shomer
Yao Ma
Juanhui Li
Bo Wu
Charu C. Aggarwal
Jiliang Tang
Venue: EMNLP 2023 Main (2023)
Keywords: knowledge graphs
link prediction
graph neural network
TL;DR: We propose a new GNN for knowledge graphs that can efficiently aggregate path information.

Abstract: Knowledge graph completion (KGC) aims to predict unseen edges in knowledge graphs (KGs), resulting in the discovery of new facts. A new class of methods have been proposed to tackle this problem by aggregating path information. These methods have shown tremendous ability in the task of KGC. However they are plagued by efficiency issues. Though there are a few recent attempts to address this through learnable path pruning, they often sacrifice the performance to gain efficiency. In this work, we identify two intrinsic limitations of these methods that affect the efficiency and representation quality. To address the limitations, we introduce a new method, TAGNet, which is able to efficiently propagate information. This is achieved by only aggregating paths in a fixed window for each source-target pair. We demonstrate that the complexity of TAGNet is independent of the number of layers. Extensive experiments demonstrate that TAGNet can cut down on the number of propagated messages by as much as $90$%  while achieving competitive performance on multiple KG datasets.

Distance-Based Propagation for Efficient Knowledge Graph Reasoning
Harry Shomer! Yao Ma² Juanhui Li' Bo Wu
Charu C. Aggarwal* Jiliang Tang',
Michigan State University Rensselaer Polytechnic Institute 3 Colorado School of Mines
IBM T. Watson Research Center
{shomerha, li 1ijuanh1, tangjili]@msu.. edu; may1 perpi.rpp.co .du
bwuêmines. Dwuêmines.edu; charuêus. ibm. com
Abstract
approach and focus instead learning directly from path-based information. One recent GNN- based method, NBFNet (Zhu et al., 2021). draws inspiration from the Bellman-Fool Ford algorithm by computing path information through dynamic pro- gramming. By doing so, it learns pairwise em- beddings between all node pairs in an inductive fashion. It achieves tatee-ofthh-ann performance in both the transductive and inductive KGC settings, In this work, we refer to such methods as path- based GNNs. However, a downside of path-based GNNs is their inefficiency. This limits their ability in large real-world graphs. Furthermore, it inhibits their ability to propagate deeply in the graph. Two recent methods have been proposed to address the inefficiency problem, i.c., Net (Zhu et al., 2022) and AdaProp (Zhang et al., 2023), by only propa- gating subset of nodes every iteration. How- ever, they still tend to propagate unnecessary and redundant messages.
Knowledge graph completion (KGC) aims to predict unseen edges in knowledge graphs (KGs), resulting in the discovery of new facts. A new class of methods have been proposed to tackle this problem by aggregating path in- formation. These methods have shown tremen- dous ability in the task of KGC. However they are plagued by efficiency issues. Though there are few recent attempts to address this through learnable path pruning, they often sacrifice the performance to gain efficiency. In this work, we identify two intrinsic limitations of these methods that affect the efficiency and repre- sentation quality. To address the limitations, we introduce a new method, TAGNet, which is able to efficiently propagate information. This is achieved by only aggregating paths in fixed window for cach source-target pair. We demon- strate that the complexity of TAGNet inde- pendent of the number of layers. Extensive experiments demonstrate that TAGNet can cut down on the number of propagated messages by much as 90% while achieving competi- tive performance on multiple KG datasets
For path-based GNNs, only the source node is initialized with a non-zero message the begin- ning of the propagation process. Such models often run a total of T layers, where, in each layer, all nodes aggregate messages from their neighboring edges. We identify that this design is inefficient by making the following two observations. (1) Empty Messages: In the propagation process, node only obtains non-empty messages when the number of propagation layers 2 the shortest path distance between the source and the node. This means that a large number of nodes far from the source node only aggregate "empty" messages in the early prop- agation layers. Nonetheless, path- path-based GNN mod- els such as NBFnet propagate these unnecessary "empty messages" in these early propagation lay- ers. (2) Redundant Messages: To ensure path information from the source reach distant nodes, the number of layers T needs to be sufficiently large. However, a large T induces the propaga- tion of redundant messages for those nodes that
1 Introduction
Knowledge graphs (KGs) encode facts via edges in a graph. Because of this, one can view the task of predicting unknown edges (i.e. link prediction) as analogous to uncovering new facts. This task is referred to as knowledge graph completion (KGC) and has attracted bevy of research over the past decade (Bordes et al., 2013; Trouillon et al., 2016; Schlichtkrull et al., 2018; Zhu et al., 2021). Most work has focused on learning quality representa- tions for all nodes (i.e. entities) and edge types (i.e. relations) in the graph to facilitate KGC.
Recently, methods (Zhu et al., 2021: Sadeghian et al., 2019; Zhang and Yao, 2022), have been intro- duced that move away from the embedding-based
'The code is available at httpp://githuu com/ HarryShomer/TAGUA

---

are close the source node. Intuitively, short paths contain more sigmificant information than long ones (Katz, 1953). The "close" nodes typi- cally aggregate enough information from shorter paths in the early propagation layers. Propagating messages for longer paths in later layers for "close" nodes does not provide significant information and needlessly adds to the complexity. More details on these two observations are provided in Section 3.1.
(s, g, They consider doing so by aggregating all paths between s and o, conditional on the query g. We denote the maximum path length as T (in their paper they set 7 = -oo), P... represents all paths of length & connecting nodes and o, and (e(es) ) is the representation of an edge condi- tional on the relation q. The representation of an edge (s, q, o) is given by (y(8
To address these limitations and make the prop- agation process more efficient, we aim de- velop an algorithm that limits the propagation of "empty" and "redundant" messages. In particular, we propose a new method TAGNet - TruncAted propaGation Network. TAGNet only aggregates paths in fixed window for each source-target pair, which be considered form of path pruning. Our contributions can be summarized as follows: We propose new path- path-based GNN, TAGNet, which customizes the amount of path-pruning for each source-target node pair.
p
hg(5,0)
w (e(e
(1)
t=1
PEPS t=1
(Zhu al., 2021) show that this formulation can capture many existing graph algorithms including the Katz index (Katz, 1953), Personalized PageR- ank (Page et al., 1999) and others.
2.3 Generalized Bellman-Ford
Due the exponential relationship between path length and the number of paths, calculating Eq. (1) for large T is unfeasible. As such, Zhu al. (2021) instead model Eq. (1) via the general- ized Bellman-Fori algorithm (Baras and Theodor- akopoulos, 2010) which recursively computes such path information in more efficient manner. It is formulated as:
We demonstrate that the complexity of TAG- Net is independent of the number of layers, allowing for efficient deep propagation.
Extensive experiments demonstrate that TAG- Net reduces the number of aggregated mes- sages by up to 90% while matching or even slightly outperforming NBFNet multiple KG benchmarks.
1 o) = 1, 0),
(2)
2 Preliminary
(x,z)
(,,
In this section, we first introduce the notation used throughout the paper. We then introduce the path formulation from Zhu et al. (2021), the general- ized Bellman-Ford algorithm (Baras and Theodor- akopoulos, 2010), and NBFNet (Zhu et al., 2021).
hgg (s.
(3)
where (o) represents edges with o as the object entity, i.e., (s, +, o). Zhu et al. (2021) prove that iterations of the generalized Bellman-Ford is equal to Eq. (1) with max path length of T.
2.1 Notations
We denote a KG as G = (V, R, } with entities V. relations R, and edges E. An edge is denoted as a triple and is of the form (s, q, o) where is the subject, y the query relation, and o the object. for incomplete fact (s, q, ?). In such problem, refer to the node entity
2.4 NBFNet
Zhu et al. (2021) extend Eq. (2) via the inclusion of learnable parameters. (,( r. o) is replaced with a learnalle embedding (r) for each relation A linear transformation is further included in the aggregation. It is formulated the following where for convenience we set h (s, o) = h!!) and w (2r, r, o) = (r.
the source node and any possible answer ? as the target node. Lastly, we denote the shortest path distance between nodes s and o as dist(s, o). We assume an edge weight of since KGs typically don't contain edge weights.
(0) = INDICATOR( U,
2.2 Path Formulation
h AGG (OMSG(GS wg(r)) (4)
Zhu et al. (2021) introduce a general path formu- lation for determining the existence of an edge
(0,1,0) ((()) (n))) (n!"))

---

ltertions
k-Hop Neighbors Update
1-Hop
2-Hop
3-Hop
Hop
Iteration
Iteration
updates
Node doesn't update
Aggregated Edge
Non non-Aggregated
(a) Example of propagating for three iterations with 6=1.
(b) Update status of nodes when d==1.
Figure I: Example of our algorithm when 6 1. We note that an undirected blue edge indicates that both nodes aggregate each other. A directed edge indicates that only the head node aggnegates the tail node. E.g., at iteration 2 node aggregates node however node doesn't t aggregate node 2.
The representation of the source node h (0) is ini- tialized to learnt embedding, qr, corresponding the query relation r. For all other nodes (o + s), they learn a separate initial embedding. However in practice they simply initialize the other nodes to the 0 vector. For the AGG function they con- sider the sum, max, min and PNA operations. For the MSG function they consider the TransE (Bor- des et al., 2013), DistMult (Yang et al., 2015), and RotatE (Sun et al., 2019) operators. The final rep- resentation is passed to score function which is modeled via MLP.
any obvious benefit. We provide an illustrative example. In Figure la, during the first iteration, node 7 will try to aggregate path information from node 6. However, all node representations, out- side of the source, messages"). Hence, non-inforrative "empty mes- sage" will be passed node from node 6. In fact, in the first iteration, only the 1-hop neigh- bors of the source aggregate non-empty messages which contains information on paths with length 1. Only after two iterations will node 6 contain path information from the source. Therefore aggregat- ing any messages before the third iteration will not lead any path information for node 7. However, both NBFNet (Zhu et al., 2021) and A"Net (Zhu et al., 2022) will aggregate such messages, leading to increased complexity without any gain in addi- tional path information. This observation suggests that a node o of distance dist( o) from the source can only aggregate path information from iteration t dist(s, o) onwards.
initialized to zero ("empty
3 The Proposed Framework
In this section, we propose new approach to im- prove the efficiency of path-based GNN models. Inspired by observations in Section 3.1, we pro- posed a simple but effective distance-based pruning strategy. We then introduce a truncated version of the generalized Bellman-Ford algorithm that achieves the goal our proposed pruning strat- egy. Finally, we describe a neural network model based on the truncated Bellman-Fort
Observation #2: Redundant Messages. Due to their design, path-based GNNs with T layers can only learn representations for nodes within T hops of the source node. However, since the time com- plexity of all existing methods is proportional to the number of layers, learning representations for nodes far from the source (i.e., distant nodes) be very inefficient. In particular, we discussed in Section 1, this mainly afflicts target nodes closer to the source. Again, we utilize Figure la for il- lustration. In the first two iterations the node 4 aggregates two paths including (source, 4) and (source, 3, 4). These paths provide significant infor- mation between the source and 4. Comparatively, in the 6-th iteration node 4 aggregates paths? of
3.1 Motivation
In this subsection, we discuss the motivation behind framework design. In particular, suggest that the inefficiency of path-based GNNs mainly due two observations: (1) the aggregation of many empty messages and (2) the proliferation of redundant messages when the number of layers is large. Next, we detail our observations and how they inspire us to design a more efficient method.
Observation #1: Empty Messages. Most path- based GNNs aggregate empty messages that do not contain any path information. This has the ef- fect of increasing the model complexity without
Sttrictly, these walks are not paths, as they contain re-

---

length 6, which reach further nodes and return to node Since these paths already contain informa- tion present in shorter paths, little information gained by aggregating them. Our empirical study in Section 4.3 also verifies that aggregating paths of longer length relative to the target node have little to no positive effect on performance.
WN18RR Distance Distribution
35
0 30-
25
20
15
10-
5-
These two observations suggest that the effi- ciency of path-based GNN methods is low when there are nodes of diverse distances to the source. We verify this by analyzing the distance distribu- tion for all test samples on the WN18RR (Dettmers et al., 2018) dataset. For each sample we calcu- late the shortest path distance between both nodes and plot the distribution of the distances over all samples. The results are shown in Figure 2. We note that around 25% of samples have shortest distance 2 5. To aggregate information for these distant nodes, it is necessary set T 2 5. In this case, nodes of larger distance will propagate empty messages for the first few iterations (Obser- vation 1). Furthermore, about 35% of the samples have a shortest distance of 1. Such samples will aggregate redundant messages after few iterations (Observation 2).
1
2
3
5
7
8 9+
Distance
Figure 2: Test Distance Distribution for WNI8RR
distance. For example, when ò 0. it only ag- gregates those paths of the shortest distance for all node pairs. Empirical observations in Section 4.3 validate our use of pruning based on an offset ö.
Due to the high complexity of Eq. (5), it is not practical directly caleulate it. Hence, based on the generalized Bellman-Fort algorithm (Baras and Theodorakopoulos, 2010), we propose a truncated version of the Bellman- Ford algorithm for calculat- ing Eq. (5) in a more efficient fashion.
3.2 Truncated Bellman-Ford
From our design goal, we are interested in captur- ing all paths of length dist(s, o) S I S dist(s, o) + 8. To achieve this goal, for node we begin ag- gregating at iteration / dist(s, o) and stop ag- gregation after iteration = dist(s, ó. This helps avoid aggregating empty messages before dist(s, o)-th iteration and redundant messages after dist(s, o) + iterations. However, during the itera- tions between dist(s, o) and dist(s, o) + 8, there are still potential empty messages. For example, any node v with the shortest distance to source larger than dist (, o) + 1-allaay always contains empty messages during these iterations. Hence, to further avoid ag- gregating empty messages, only allow aggrega- tion from a subset of the neighboring nodes of o. More formally, we formulate the above intuition into the following constrained edge set C(s, o, t) through which node o aggregates information at iteration t.
Our Design Goal: The key to improving the ef- ficiency of path-based GNNs is to modify their aggregation scheme. particular, based on the aggregation scheme of path- based GNNs, all target nodes are aggregating paths with lengths ranging from 1 to T. Such paths contain many empty and redundant messages. To reduce the aggregation of those non-informative messages, we propose to customize the aggregations for each target node. Specifically, for close nodes, we do not aggregate long paths as they are redundant. For distant nodes, we do not aggregate short paths as they are empty. As such, we customize the aggregation process for each target node according to its distance from the source. Based on this intuition, reformulate the path formulation, Eq. (1), as follows.
dist(x.o)+e +5
Ipl
(8) ddsis(s,,)) PE
w(es),
(5)
0, if < dist(s, 0) or
t dist(s, o) + {(u,r,o) E(o) dist(s, v) dist(s, 6). else
C(s,
where 8 2 is offset. The parameter å can be considered form of path pruning as it controls the paths we aggregate relative the shortest path
(6)
peated nodes and edges. In this paper, we follow the con- vention of the base- GNN papers to loosely call them paths.
Based on this constraint set of edges for node o, we update the generalized Bellman-Fan Ford algorithm

---

(Bq. 2) as follows where C o,))
update as there is no available path information for them until iteration 4.
(s.
(x, (
3.3 Degree Messages
(o.T.0)EC
An effect of pruning paths, especially with low 6, that it can lead to very few messages being aggre- gated. This is especially true for smaller or sparser graphs. One consequence of few messages being aggregated is that it can make it difficult for a node to discern the properties of its neighborhood (e.g. degree). We give an example of node 4 in Figure 1. For each of the first 2 iterations, only aggregates messages from 2/4 of it's neighbors. As such, it never aggregates messages from all its neighbors at the same iteration. This can lead to a failure of node 4 to properly discern it's degree, as the num- ber of non-empty messages in each iteration is only portion of the overall degree. Since the degree is known to be an important factor in link predic- tion (Newman, 2001; Adamic and Adar, 2003), we want to preserve the degree information for all nodes.
(0) @ Xg (s, n).
(7)
The following theorem shows that the aggregation scheme proposed in Eq. (7) results in aggregation of the correct paths as described in Eq. (5).
Theorem 1. Given source node s, query q, and target node o, the final representation, X4 (s, o) only aggregates all path representations whose path length is between dist(s, o) and dist(s, 6 for all o C V. It therefore contains all information present in Eq. (5) such that,
dist(s,0)+6
lpl
x (s, = +
w(e)).
(8)
ds.i((s..)) PC PC
The detailed proof of Theorem 1 is provided in Appendix A. This design has the following advantages. (1) We don't begin aggregating messages until layer avoid the aggregation of many empty messages for nodes far from the source. (2) We stop aggregating messages at layer / = dist(s, o) + 8. This ensures that for close nodes we don't aggregate many redundant messages. Furthermore, it ensures that we will always aggregate paths of + 1 different lengths for all target nodes regardless of their distance from the source. (3) In Section B.2, we demonstrate that the complexity of this design is independent of the number of layers, allowing for deep propagation.
In order to preserve the degree information for each node, we consider encoding the degree via the use of pseudo messages. Specifically, we want to add enough messages such that the total number of messages aggregated for node is equivalent to its degree. We refer to such messages as degree messages. Going back our example in Figure 1, for node iteration 1 and we would add de- gree messages so that the total number of messages is 4. Formally, we denote the degree of a node o as by- The number of messages to add at iteration is given by Po = bo |C(s, f)].
dist(s. o). This helps
For the value of the messages, we learn a sep- arate embedding denoted as x(t) that is the same across all nodes. Since the value of each message is the same we can avoid explicitly aggregating each degree message individually. Instead, we just aggregate one message that is equal to the num- ber of degree messages multiplied by the degree embedding.
An Illustrative Example. We given an ex- ample of the effect of constraints propagation in Figure where = source. Figure la shows the involved nodes and edges over three iterations when 1. We observe that only portion of the nodes and edges are involved at any one iteration. For example, at iteration only the 1-hop neighbors and the edges connecting them to the source are involved. This is because they are the only nodes and edges able to receive any path information at that stage. Figure lb details the update status of nodes by distance from the source node. We note how the iteration increases the number of nodes updated shift to the right in groups of two. Furthermore since we only iterate for three iterations, the 4+ hop neighbors never
Xdeg (8, 0) = Po x deg?
(9)
where dog (s, 0) is the value of the degree message for node at iteration t. This edge is then added to the set of messages to be aggregated, C(s, o, l). Since this is equivalent to computing and aggregat- ing only one edge, it has no effect on the model complexity. Experimental results in Section 4.4 validate the effectiveness of degree messages.

---

3.4 GNN Formulation
the value of 6. Let's denote the value of the hy- perparameter ô as 8. For a source-target node pair (8, o), we only aggregate paths from length dist(s, o) to dist(s, o) At itteationn t dist(s, o) we aggregate paths of length dist(s, o) and at iter- ation & dist(s, o) + 1 only those paths of length dist(s, o) + 1, and so on until ( = dist(s, (s, 0) + 8. The set of hidden representations for node pair is as follows where for convenience we represent Xg (s, 0) as (s,o))-
We follow similar conventions to NBFNet when converting Eq. (6) and Eq. (7) to GNN. We denote the embedding of source node s and arbitrary target node (5, o). We further represent the indicator query embeddings as Xy and the layer- wise relation embeddings as x
We utilize the INDICATOR function described in Section 2.4, PNA (Corso et al., 2020) for the AGGREGATE function, and DistMult (Yang et al., 2015) for the MSG function. The probability of a link existing between source-target pair is de- termined via score function Both the final representation of the pair and the query embedding are given as input. The output of f is then passed to a sigmoid to produce a probability,
[ dist(s.o) (x,0) 3' (3,0)
(d))
Hiddens(s,
(11)
The first hidden representation only contains paths of shortest length and therefore corresponds to = 0. Since the paths accumulate over hidden representations via a self-loop, tains all paths of length dist(s, o) and dist(s, o) +1, corresponding to 8 = As such, the final hidden representation is equivalent to = 8. Therefore, choosing a target-specific ō is achieved by select- ing one of the hidden representations as the final representation.
{ (dist(s.o)++1) con-
X(s.0)
p(8,0) = (x(((s))) x,)),
(10)
where x, (x, 0) is the final pair representation. The full algorithm is detailed in Appendix B.I. We run total of T layers. We further show in in Appendix B.2 that time complexity is independent of the number of layers. This enables TAGNet to propagate for more layers than existing path-based GNNs.
We utilize attention determine which value of 8 is best for specific target node. This is formu- lated as the following:
Furthermore, due to its general design, TAGNet can also be integrated with other efficiency-minded methods like A Net. This is described in more detail in Appendix B.3. Extensive experiments in Sections 4.1 and 4.2 also demonstrate that com- bining both methods can significantly reduce the number of messages propagated by A Net without sacrificing performance.
8
((,00
Σ 8=0
5
(1.0))
(dist(s,o)
(12)
where ((.0)) is the corresponding attention weight for the hidden representation (dist(s.o)++)) For ((.0))
each possible value of ö, af..)) is given by:
ād (a,0) = 9 (x (dia(())))))) .x
(x,0)
3.5 Target-Specific
6 ((000) Softmax(a (a..)))
A drawback of our current design is that we as- sume a single offset 5 for all possible node pairs. However, for some pairs may want to consider propagating more or less iterations. For example, in Figure we may only want to consider 8 for the target node due to the limited number of paths connecting it to the source. However for node 4, which is concentrated in a denser portion of the subgraph, we may want to consider higher value of 5 such as or 2 to capture more path information. We next detail our method for achieving this.
We model g as MLP that takes both the hidden representation and the query embedding as input. Taking inspiration from A Net (Zhu et al., 2022), we conjecture that a well-learned score function can help determine which representations are better than others. As such, we further consider modeling g its own function or having it share parameters with the score function f. Eq. (10). Lastly, we show in Appendix B.2 that the time complexity is unchanged when using sprget-specific 8.
Experiment
3.5.1 Target-Specific 8 via Attention
A target-specific can be attained by realizing the connection between the hidden representations and
In this section, we evaluate the effectiveness our proposed framework on KGC under both the trans-

---

Table 1: Transductive Results. Best results are bold and the 2nd best underlined.
Method Type
Method
FB15k-237
WNISRR Hits@1
MRR
Hits@l
Hits @ 10
MRR
Hits@ 10
TransE
0.294
0.465
0.226
0.501
DistMult
0.241
0.155
0.419
0.43
0.39
0.49
Embeddings
ComplEx
0.247
0.158
0.428
0.44
0.41
0.51
R-GCN 0.273
0.182
0.456
0.402
0.345
0.494
GNNs
CompGCN
0.355
0.264
0.535
0.479
0.443
0,546
DRUM
0.343
0.255
0.516
0,486
0,425
0.586
RED-GNN
0.374
0.283
0.558
0,485
0.624
Path-Based
AdaProp
0.392
0.309
0.555
0,502
0.652
NBFNet
0.415
0.321
0.599
0.551
0,497
0.666
A Net
0.414
0.324
0.592
0.547
0.490
0.658
Net
0.409
0.323
0.577
0.555
0.502
0.657
TAGNet
Fixed
0.421
0.328
0.602
0.562
0.509
0.667
Specific
0.417
0.328
0.592
0.565
0.513
0.667
Table Inductive Results (evaluated with Hits 10). Ours results averaged over
FB 157-237
WNI8RR
Method
vl
v2
v3
v4
v1
v2
v3
v4
NeuralLP
0.468
0.586
0.571
0.593
0.772
0.749
0.476
0.706
DRUM
0.474
0.595
0.571
0.593
0.777
0.747
0).47
0.702
GralL
0.429
0.424
0.424
0.389
0.760
0.776
0.409
0.687
RED-GNN
0.483
0.629
0.603
0.621
0.799
0.780
0.524
0.721
AdaProp
0.470
0.651
0.620
0.614
0.798
0.836
0,582
0.732
NBENet
0.607
0.704
0.667
0.668
0.826
0.798
0.568
0.694
A Net
0.535
0.638
0.610
0.630
0.810
0.803
0.544
0.743
TAGNet A Net
0.541
0.646
0.604
0.623
0.813
0.805
0.535
0.745
TAGNet (fixed d)
0.596
0.700
0.677
0.666
0.816
0.796
0.534
0.734
TAGNet (spacific 6)
0.596
0.698
0.675
0.661
0.818
0.803
0.544
0.737
ductive and inductive settings. We also empirically analyze the efficiency and conduct ablation studies on each component. The experimental details are listed in Appendix C. We note that for a fair com- parison between path-based GNNs, run each model using 6 layers and hidden dimension of 32 is done in both (Zhu et al., 2021) and (Zhu et al.. 2022). Please see Appendix C.2 for more details.
mostly reduces redundant aggregations that do not impair the models effectiveness.
Table 2 shows the results on the inductive setting. TAGNet achieves strong perfor- mance on both datasets. In particular, it achieves comparable performance to the non-pruning ver- sion of NBFNet. Furthermore, TAGNet signif- icantly outperforms A Net and AdaProp on the FB 15k-237 splits, demonstrating the advantage of the proposed pruning strategy.
Inductive Setting:
4.1 Effectiveness of TAGNet
In this subsection, we present the results of TAGNet compared with baselines both transductive and inductive settings. We further detail the results when combining TAGNet with Net.
TAGNet + A Net: We further test combining the pruning strategy of both TAGNet and A to- gether (see Appendix B.3 for more details). Com- pared to A "et, we observe that TAGNet+A NNt achieves comparable if not better performance der all settings despite aggregating much fewer messages (see subsection 4.2). This suggests that the pruning strategy A N*ett fails to prune many irrelevant paths, allowing TAGNet to work comple- mentary to it.
Transductive Setting: The results on the trans- ductive setting are shown in Table 1. We observe that TAGNet achieves strong performance with just fixed 8. In particular, it outperforms A Net and AdaProp on most metrics. Also compared to NBFnet, which doesn't utilize pruning, TAGNet achieves comparable or even stronger performance. This indicates that the proposed pruning strategy

---

4.2 Efficiency of TAGNet
Table 3: Decrease in Msgs for Net vs. A N'et TAGNet
In this subsection, we empirically evaluate the effi- ciency of our model against NBFNet. Specifically, we compare the mean number of messages aggre- gated per sample during training.
Dataset
Layers
7 Layers
8 Layers
FB15k-237
39%
51%
59%
FB15K-237
30%
44%
66%
Figure 3 shows the % decrease in the number of messages of TAGNet as compared NBFNet. All models are fit with layers. We observe two trends. The first is that both FB15k-237 datasets follow a similar relationship that close to what's 's expected of the worst-case complexity detailed in Appendix B.2. On the other hand, the WN18RR datasets pass much fewer messages as they hover above 90% for all 6. This is likely be- cause WN18RR very sparse graph. This gives TAGNet plenty of opportunities prune paths.
WNISRR
10%
17%
26%
WNISRR vl
25%
37%
46%
chose version vl of both datasets as the represen- tative datasets. For both transductive datasets, we find that the performance plateaus at å 2. A similar trend is observed for FB15k-237 vl. Inter- estingly, for WN18RR the performance con- stant when varying 8. This suggests that for some datasets almost all of the important information is concentrated in paths of the shortest length.
% Decrease in # Msgs from NBFNet 100%
Vary 6 Transductive Setting
% Decrease Msgs
90%
0.55
80%
FB15k-237
Test MRR
0.50
70%
60%
WN1BRR v1
0.45
50%
FB15k-237 v1
40%
0.40
FB15k-237
30%
0.35
WN18RR
5
2
3
4
5
Figure 3: % Decrease in NBFNet Messages
Figure 4: Performance varying 8 on Transductive set- ting.
We further compare the efficiency of just A Net and A NNt + TAGNet. As before, we calculate the total number of messages passed for both methods. We fix 8 2. Table show the decrease in the number of messages when utilizing both tech-
Vary 5 on Inductive Setting
0.80
Test Hits Hits@lo
@10
0.75
niques compared to just Net.. We observe large reduction in both the inductive and transductive set- ting. Since the performance of A *Net + TAGNet is on par with just Net, it suggests that A Net fails to prune many unneeded messages that do not improve performance. Furthermore, we find that the reduction in the number of messages becomes more pronounced with more layers, suggesting that TAGNet is even more useful when deep propaga- tion is necessary.
0.70
FB15k-237 v1
0.65
WN18RR v1
0.60
0.55
2
3
5
Figure 5: Performance varying d on Inductive setting.
4.4 Effect of Degree Messages
4.3 Effect of 5
We demonstrate the effect of the degree messages described in Scction 3.3. Table 4 shows the per- formance of TAGNet when trained with and with- out degree messages. We report the performance on of the inductive splits for both FB 1k-233 and WN1SRR. Interestingly, we observe that while there is a consistent gain on FB 2515k-237, it often
In this subsection, evaluate the effect of the off- set on TAGNet test performance (w/o the target- specific setting). We fix the number of layers at and vary from to We report results for both the transductive and inductive settings in Figures and 5, respectively. For the inductive setting, we

---

hurts performance on WNI8RR. This may imply that preserving the degree information of each node is more important on 133--2237 than WNISRR.
2022) and AdaProp (Zhang al., 2023) attempt prove upon the efficiency of the previous methods by learning which nodes to propagate to.
Table 4: Effect of Degree Messages on Inductive Splits
Conclusion
In this paper we identify two intrinsic limitations of path-based GNNs that affect the efficiency and representation quality. We tackle these issues by introducing new method, TAGNet, which is able to efficiently propagate path information. This is realized by only aggregating paths in fixed win- dow for each sauree-target pair. We demonstrate that the complexity of TAGNet is independent of the number of layers. For future work, we plan on exploring methods to capture path information without having to perform a separate round of prop- agation for every individual source node.
Dataset
Split
w/o Msgs
with Msgs
V1
0.594
0.596
V2
0,684
0.698
FB15K-237
V3
0,653
0.675
V4
0.648
0.661
V1
0.815
0.818
V2
0.803
0.781
WNI8RR
V3
0.544
0.465
V4
0.737
0.718
5 Related Work
We give a brief overview of different types of (1) Simeediig-Baased Meth- ods: Such methods are concerned with modeling the interactions of entity and relation embeddings. TransE (Bordes al., 2013) models each fact as translation in the embedding space while Dist- Mult (Yang et al., 2015) scores each fact via bilin- ear diagonal function. ComplEx (Trouillon al., 2016) extends DistMult by further modeling the embeddings in the complex space. Lastly, Node- piece (Galkin et al., 2021) attempts to improve the KGC methods by representing each entity embedding combina- tion of smaller set of subword embeddings. Since this method concerns embedding- based techniques, it orthogonal our work. (2) GNN-Based Methods: GNN methods extend traditional GNNs by further considering the relational information. CompGCN (Vashishth et al., 2019) encodes each message as combination of neighboring entity- relation pairs via the use of compositional function. RGCN (Schlichtkrull et al., 2018) instead consid- ers relation-speeiie transformation matrix to in- tegrate the relation information. (3) Path-Based Methods: Path- based methods attempt to lever- age the path information connecting two entities to perform KGC. NeuralLP (Yang et al., 2017) and DRUM (Sadeghian et al., 2019) learn to weight different paths by utilizing logical rules. More re- cently, NBFNet (Zhu et al., 2021) considers path information by learning parameterized version of the Bellman-FFord algorithm. A similar framework. RED-GNN (Zhang and Yao, 2022) also attempts to take advantage of dynamic programming to ag- gregate path information. Both A "Net (Zhu et al.,
KGC methods.
Limitations
Our work has couple of limitations. One is that it our study is limited only knowledge graph completion. This excludes non-relational link pre- diction tasks. Future work can ascertain the effec- tiveness of TAGNet on other types of link predic- tion. Second, all path-based GNNs still require to propagate from each source-relation pair individu- ally. This can pose a significant bottleneck when many samples need to be tested. We plan on explor- ing methods capture path information without having propagate for each individual pair.
efficiency of embedding-basse
References
Lada A Adamic and Eytan Adar. 2003. Friends and neighbors on the web. Social networks, 25(3):111 230.
John Baras and George Theodorakopoulos. 2010. Path problems in networks. Synthesis Lectures on Communication Networks, 3(1):1-77.
Antoine Bordes, Nicolas Usunier, Alberto Garcia- Duran, Jason Weston, and Oksana Yakhnenko. 2013. Translating embeddings for modeling multi- relational data. Advances in neural information pro- cessing systems, 26.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. 2020. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260- 13271.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp. and Sebastian Riedel. 2018. Convolutional 2d knowl- edge graph embeddings. Proceedings of the AAAI conference on artificial intelligence, volume 32.

---

Mikhail Galkin, Etienne Denis, Jiapeng Wu, and William L Hamilton. 2021. Nodepiece: Composi- tional and parameter-efficent representations of large knowledge graphs. In International Conference on Learning Representations.
Zhiqing Sun, Zhi-Hong Deng, Yum Nie, and Jian Tang. 2019. Rotate:
Knowledge graph embedding by relational rotation in complex space. In International Conference on Learning Representations.
Komal Teru, Etienne Denis, and Will Hamilton. 2020. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, pages 9448 9457. PMLR.
Leo Katz, 1953, A new status index derived from socio- metric analysis. Psychometrika, 18(1):39-4) 43.
Diederik P Kingma and Jimmy Ba. 2014. Adam: A
method for stochastic optimization. arXiv preprint arXiv:1412.690
Kristina Toutanova and Danqi Chen. 2015. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd workshop on continuous vector space models and their composi- tionality. pages 57-66.
Sijie Mai, Shuangjia Zheng, Yuedong Yang. and Haifeng Hu. 2021. Communicative message passing for inductive relation reasoning. In Proceedings of the AAAI Conference on Artificial Intelligence, vol-
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. 2016. Complex embeddings for simple link prediction. In Interna- tional conference on machine learning, pages 2071- 2080. PMLR.
ume 35, pages 4294-4302.
Mark EJ Newman, 2001. Clustering and preferential attachment in growing networks. Physical review E, 64(2):025102.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. 2019. Composition- multi- relational graph convolutional networks. In Interna- tional Conference on Learning Representations.
Tu Dinh Nguyen, Dat Quoc Nguyen, Dinh Phung, et al. 2018. A novel embedding model for knowledge base completion based convolutional neural network. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computa- rional Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 327-333.
Wenhan Xiong. Thien Hoang, and William Yang Wang. 2017. Deeppath: A reinforcement learning method for knowledge graph reasoning. In Proceedings of the 2017 Conference on Empirical Methods in Natu- ral Language Processing, pages 564-573
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The pagerank citation rank- ing: Bringing order to the web. Technical report, Stanford InfoLab.
Bishan Yang, Scott Wen-tau Yih, Xiaodong He, Jian- feng Gao, and Li Deng, 2015. Embedding entities and relations for learning and inference in knowledge bases. In Proceedings of the International Confer- ence on Learning Representations (ICLR) 2015.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Te- jani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. 2019. Pytorch: An imperative style, high- perfforrfrm deep learning library. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d' d'Alché-Bue, F. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 0024-8035. Curran Associates, Inc
Fan Yang. Zhilin Yang, and William W Cohen. 2017. Differentiable learning of logical rules for knowledge base reasoning. Advances in neural information pro- cessing systems. 30.
Yongqi Zhang and Quamming Yao. 2022. Knowledge graph reasoning with relational digraph. Proceed- ings of the ACM Web Conference 2022, pages 912- 924.
Ali Sadeghian. Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. 2019. Drum: End-to- end diffcrentiable rule mining on knowledge graphs. Advances in Neural Information Processing Systems, 32.
Yongqi Zhang, Zhanke Zhou, Quanming Yao, Xiaowen Chu, and Bo Han. 2023. Adaprop: Learning adaptive propagation for graph neural network based knowl- edge graph reasoning. In KDD.
Zhaocheng Zhu, Xinyu Yuan, Louis-Pascal Xhon- neux, Ming Zhang. Maxime Gazeau, and Jian Tang. 2022. Learning to efficiently propagate for reasoning on knowledge graphs. arXiv preprint arXiv:2206.04798.
Tara Safavi and Danai Koutra. 2020. Codex: A com- prehensive knowledge graph completion benchmark. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 8328-8350
Zhaocheng Zhu, Zuobai Zhang, Louis- Xhon- neux, and Jian Tang. 2021. Neural bellman-ford net- works: A general graph neural network framework for link prediction. Advances in Neural Information Processigg Systems, 34:29466-29490.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. 2018. Modeling relational data with graph convolu- tional networks. In European semantic web confer- ence, pages 593-607. Springer.

---

A Proof Details of Theorem 1
induction on the path length 1. We denote nodes a distance | from the source node 8 as Vi- The path length offset is represented by 8. Lastly, for convenience we split the constraints in Eq. (6) into two: a node constraint and an edge constraint. We formulate it as the following where [odes(s, o,t) represents the node constraint and EdgeC3(s, o, u) the edge constraint:
We prove Theorem
Nodes(s, 0,() - 8 dist (, 0) S4 EdgeC, dist(s, u) < dist 0) +
(13)
(14)
Base Case (I=1): We want show for all = hop neighbors of s, E V their final representation by (s, o) aggregates all path representations in the range [0, 6]. To be true, the embedding of (s, o) must satisfy two conditions:
1.
Condition 1: The final embedding 2ig (s, o), contains all paths representations of length less than or
equal to 1 + 8 between and
F 2. Condition 2: The final embedding o (s, o) contains no other path information.
Condition 1: For it be true, a node o E V must aggregate all edges of the form (u, r, 0) where u belongs to the set:
( fu (u, E &.. ue (vo, V.l v. 8.0
(15)
where & represents all edges where is the target node. It's intuitive that all paths starting at length E [0, 8 + 1] must pass through the nodes in the set (0,6) in order to reach We prove in Theorem 2 that o will aggregate all nodes in the set (0.66)
Condition 2:
We want to demonstrate that the representation of node aggregates other path (s,
information such that Zy (6:1)(s,))))))))))))))) o) = x o). This is true as per the node constraint (Eq. (13)) the
representation of a node stops updating after iteration k = + 8.
We assume that for all m-hop neighbors of s, Vm their final representa- tion xn (s) aggregates all path representations of length between [m, + 6). This is achieved by node aggregating all edges (u, r, o) where u belongs to the set:
Inductive Step:
Ulm mmm-1m-1+8) 8,0
{u (u, o) Eo, u E {V-
(16)
as all such paths must pass through these nodes. We note that this implics that:
The set of nodes U U/(m-1mm-++)) must themselves only contain all path representations of lengths [m - 1, m 1 + 5] when aggregated by o E Vmm.
The set of nodes (mm 1. 11 must obtain such path information by iteration k: m 1 1 8. This must be true per the node constraint will last update iteration & m 8.
We now want to show for all (m + 1) hop neighbors of s, o E Vm their final representation xn (s, o) aggregates all path representations of of length between [m + 1, m + + 8). This requires showing that by (s,0) o) (1) contains all paths representations between [m + 1, m + 1 + 8] between and and (2) it contains other path information.
Condition 1: For o E Vm++ aggregate all paths of length between m + and 1 8. their representation must aggregate all edges (u, r, where u belongs the set:
(m.m %,
{ul (u, r, o) &., u E [V."... ....,.., 1mmi1 11)
(17)
Such edges are aggregated by o E 4m+1 via the edge constraint. Furthermore,

---

From the inductive step we know that nodes U 1,m 1 116)
Um 16) Vm=+ have already
aggregated all path representations of lengths (m 1, m 1 6] by iteration = m + 6.
From both constraints we know that Yu V. will only contain all path representations of length m + (i.c. shortest path) by iteration ht = m +
As such, after aggregating the nodes in the set U (mmm)+)) the representation (m++)) Iiq x.9 (s, u) will contain all paths representations between m and m + 8. Per the node constraint, Yo E V last
update at iteration = m + 1 + 6. Therefore by aggregating U.m..++)) at iteration = m + + 8. the representation mi
1+5+1+5)_m (s, o) will contain all path representations between length m++1 and m++1 +
Condition Lastly, we want to show that Vo E Vm++ the final representation (s, o) will only contain path representations of length m + 1 to m + 6. This is true as per the node constraint the representation of a node o E V- last updates at iteration k = m + + ó. Therefore 24 (m 116) (8, o) = = (8, As such, the final representation only aggregates paths of length between m + and m + +
Theorem 2. We are given source node query 9. and target node o which is a 1-hop neighbor of s. The final representation of I l-hop neighbor x5(s (s.0), will at minimum aggregate all path representations whose path length is between and 1 + 6. It therefore at least contains the path information,
1+8
pl
7
w(es).
(18)
t=
PEP.
This equivalent to stating that o will aggregate all nodes in the following set by iteration l +
(10,6) f (u,r,o) E Eo. u (vD) v.l v'.).
(19)
We prove this Theorem via induction on the layer iteration k in our algorithm (denoted their as l).
Base Case (k=l): We want first show that after one iteration, the representation of 1-hop
neighbor (s(s,) o) aggregates all paths of length I from the source. This is achieved by (s,
aggregating all edges connecting to 8, i.e. (s, o). Such edges are aggregated by o as both the edge and node constraints are satisfied:
(s, = NodeC5 1) 1151
(20)
(21)
Inductive Step: We assume that at some iteration = n, s.t. n + ō, the representation x (s, o) for o C V. aggregates all path representations up to a length n from the source. This achieved by aggregating all edges that contain nodes in the set:
1) {u ru, Eo, (Vo Vl s....
1)
(22)
Since we assume that 2 (8, o) contains path representations up to length n, then follows that Yu E (=(0.-1)) their corresponding representation or (s, o) must also contain all paths up to length n - 1. As such, by node aggregating 10) it extend the length of each path by 1.
We want to prove that at iteration k = + the representation 2ig (n+1) (s, aggregates all path representations up to length from the source. This is achieved by aggregating all edges that contain the nodes in the set:
U(0..) = fu (u,r, E E., u E (vo, V...... ... []]]] 800
(23)

---

Algorithm TAGNet Algorithm (fixed 6)
Require:
Source node
=
Query relation
T = Max Number of Layers
Emheddings
Offsct
Agg Degree= Whether to include degree mags
1: Initialize: (0)
0, Vo V
(0)
(0.0) Xg
2: for t 1...T do
3:
for E V do
4:
ift 5 2 dist(a, 0) then
5:
C(s, [(u, r, E(o) dist(s, < dist(s, o) +
Msgs (-1)) @ xf r,) E 0(s,
6:
7:
if Agg-Degges then io- [Msgs]
8:
9:
Msgs = Msgs U Do Xaz
10:
end if ((000) Aggregatel Msgs
11:
12:
end
13:
end
14:
end (d for E
15:
return x (1,0)
Per the previous inductive step, we assumed that the representations (,, o) Vo E V contain all path representations up to length n. Furthermore we noted that at iteration = n, the representations for Since (/(0.)) -1o0 (0. U VT. this implies that (0.x) contain all path representations up to length Thereby when Zn (n+1) (s, o) aggregates the nodes in (:(O.)) it aggregates all path representations up to length
each node in the set (0) must also contain all path representations up length
n + 1. A node o E V. will aggregate such nodes at iteration k = n + 1 per both constraints. (1 6) (s, o) aggregates all path represen- This proves by induction that for o E V/l. their representation zy tations of length less than or equal to 1 + 6.
B Further Details on TAGNet
B.1 TAGNet Algorithm
The algorithm for TAGNet, with fixed 8, is presented in Algorithm 1.
B.2
Time Complexity Analysis
Per the constraints in Eq. (6), each node can be updated at most + times and each edge can be aggregated at most + 1 times. The shortest path distance from source node to all other nodes can be calculated in linear time via breadth-fine first search. The worst-case complexity for the standard version of TAGNet is therefore:
O ((6 + +1 +
(24)
Of note is that the worst case-complexity is independent of the number of layers. This allows for much deeper propagation.
We further discuss the complexity when utilizing degree messages and target-specific 5. As noted in Section 3.3, the inclusion of degree messages is equivalent aggregating an additional edge each iteration. As such, doesn't effect the model complexity. Furthermore, when utilizing target-specific 8, an additional (6 + 1) d2 operations are added to calculate the attention scores. This equivalent to updating each one node one additional time and therefore also has no effect on the model complexity.

---

B.3 TAGNet Net
We further experiment with combining the pruning strategy of both AeNet and TAGNet. This achieved by taking the intersection of the edge sets produced by both methods for a node pair (s, o) at iteration t. This is because we only want to aggregate an edge if it is not pruned by both methods. For TAGNet, the edge set C(s, t) is defined as in Eq. (6). We further denote the edge set for A as A(s, t). Adapting Eq. (7) we arrive at:
(
(s,0)
x wylu,T,,))
(25)
The performance and efficiency when combining both methods is detailed in Section 4.1 and 4.2, respec- tively. Lastly, note that don't t consider combining with the pruning strategy in AdaProp (Zhang al., 2023) due its strong similarity with that of A" Net.
Experimental Settings
C.1 Datasets
We conduct experiments on both the transductive and inductive settings. For the transductive setting, we consider FB FB15K-237 (Toutanova and Chen, 2015) and WNI8RR (Dettmers et al., 2018). For the inductive setting, where the train and test entities are disjoint, we consider the splits generated by Teru al. (2020) from both FB 15K-237 and WN18RR. Four splits are generated from both datasets that vary in size. Of note that we omit the NELL-995 (Xiong et al., 2017) dataset from both sets of our experiments. This is due to concerns raised by Safavi and Koutra (2020), where they argue that most of the triples in NELL-995 are either meaningless or trivial. The statistics for all the transductive and inductive datasets are given in Tables 5 and 6, respectively.
Table 5: Statistics for Transductive Datasets.
Statistic
FB15K-237
WN18RR
#Entities
14,541
40,943
#Relations
237
11
#Train
272,115
86,835
#Validation
17,535
3,034
#Test
20,466
3,134
C.2 Baselines
the transductive setting, following (Zhu et al., 2021), we consider variety different models. For embedding-based methods we consider TransE (Bordes et al., 2013) (performance from (Nguyen et al., 2018)), DistMult (Yang et al., 2015), ComlEx (Trouillon et al., 2016). For GNN methods we include R-GCN (Schlichtkrull et al., 2018) (performance on WNI8RR taken from (Zhu et al., 2021)) and CompGCN (Vashishth et al., 2019). For path-based methods we include DRUM (Sadeghian et al., 2019), NBFNet (Zhu et al., 2021), RED-GNN (Zhang and Yao, 2022), A Net (Zhu et al., 2022), and AdaProp (Zhang et al., 2023). We note that for AdaProp the original results from (Zhang et al., 2023) utilize 7 and 8 layers for FB15k237 and WNISRR, respectively (see Table in (Zhang et al., 2023)). For other methods such as TAGNet, NBFNet, and A *NET, the number of layers fixed at 6. To facilitate a fair comparison, we run AdaProp on both datasets using 6 layers. We utilize the official source code and the published hyperparameters.
For the inductive setting, following (Teru et al., 2020; Zhu et al., 2021), we include GralL (Teru et al.. 2020), CoMPILE (Mai et al., 2021), !), and NeuralLP (Yang et al., 2017) in addition to NBFNet and A Net.

---

Table 6: Statistics for Inductive Datasets.
Datrect
*Relations
REntitie
Train RQueyy
dFact
#Eaniiis
Validation aQuary
iFact
Test PQuery
#Fact
v1
180
1,594
4,245
4.245
1,594
439
4,245
1,093
205
1,993
FBISK-237
v.5
92
215
200
2,608
3,668
17,985
9,739
17.956
9,750
2,608
3,658
2.194
1.365
17,98h
9,739
2,501
1,660
476
365
4,145
7,408
144
219
4,707
27,303
27,200
4,707
3,352
27,303
3
1,424
11,714
v1
2,746
5,410
5,410
2,746
630
5,410
922
195
1,18
WNIARR
1/2
10
6,554
15,262
15.202
6,954
1,538
15,262
27757
441
4011
12,078
23.501
25,901
3009
25.901
605
6.327
7,940
7,540
12.354
We note that embedding methods aren't applicable to the inductive setting as the train and test entities are disjoint. For NBFNet, the results on the inductive FB 153-237 splits are reported by us while the results for the WN18RR splits are from Zhu et al. (2022). This is because we observed that we can achieve better performance for NBFNet on the FB 15k-237 splits than what was reported in Zhu et al. (2022). Lastly, with the transductive setting, we run AdaProp with 6 layers facilitate fair comparison between it and other path-based GNNs. We also the hidden dimension to 32 is with all other path-bat path-based GNNs.
C.3 Evaluation Metries
the transductive sctting, we report the mean reciprocal rank (MRR), Hits 1, and Hits 10 following the filtered setting as described in (Bordes et al., 2013). For the inductive setting, following (Zhang et al., 2023; Zhu et al., 2022), we only report the Hits @ 10.
C.4 Hyperparameter Settings
We list the parameters settings for TAGNet. Under the fixed-ō formulation it is trained for 20 and 16 epochs the transductive and inductive setting, respectively. For the specific-ò formulation, train for 25 and 20 epochs on the transductive and inductive setting, respectively, as we've found it takes longer converge. For all transductive and inductive experiments in Table and 2 we set the maximum number of layers to 6 and the hidden dimension to 32. This to facilitate a fair comparison with NBFNet and Net. Furthermore the transductive batch size is fixed at 16. The number of negative samples is tuned from {128, 512, 1024, 2048]. the dropout from the range [0, 0.7]. the learning rate decay from {0.9, 0.95, 1}. the weight decay from [le-8, le-3], and the adversarial temperature from (0.5, 1). For the target specific setting further test setting g its tune the softmax temperature for attention from (0.5, 1, 5J. For the inductive setting further tune the batch size from (16, 32, 64, 128) and the learning rate from [le-4, 1e-2], Lastly, for all experiments, the offset 8 is tuned from {1, 2, 2.
function
equal to the score function, g f. We further
C.5 Implementation Details
The framework is implemented with PyTorch (Paszke et al., 2019). All experiments were run on single 32G Tesla V100 GPU. We train TAGNet with the binary cross-entropy loss optimized via the Adam optimizer (Kingma and Ba, 2014). We follow Yang et al. (2017) and augment the graph by including reciprocal edges, such that for an edge (h, r.,r.d t), its reciprocal edge (t, 1.h) is included. In this scenario -1 is considered a distinct relation from
D Additional Analysis on TAGNet
In this section we take a closer look as to what kind of messages are pruned by TAGNet. As noted in Section 3.1 we strive to limit the number of empty and redundant messages. We first analyze how well TAGNet prune both of those messages. We then examine the reason why some datasets may prunc more empty redundant messages.
We first analyze the number of empty and redundant messages pruned for both transductive datasets. We report the results Table 7 as a % of the total number of pruned messages. F.g., For FB 1k-233 51% the total number of pruned messages are empty messages. For simplicity, we limit this study to the the best versions each model, i.e. for FB15K-237 and 5 = 3 for WN18RR. We find that on

---

FB15k-237, the messages pruned are split evenly between empty and redundant messages. On the other hand, for WN18RR over 90% of the messages pruned are empty messages.
Table % of Messages Pruned that either Empty Redundant
Dataset
Empty
% Redundant
FB12k-237
51%
49%
WN18RR
91%
9%
An obvious question is: Why does the composition of pruned messages differ between datasets? We believe this can be explained via two properties of each datasets, the density and distance distribution. We measure the sparsity via the mean degree, which is shown in Table 8. We do this as graphs with a low mean degree will contain few connections between nodes, resulting in fewer paths between different nodes and thereby fewer redundant paths. Furthermore, there will be lower chance of node visiting another node already the path, most nodes are linked to only handful of nodes. We further show the distance distribution of the test samples, i... the % of test samples that are a distance from each other, in Table 9. This is because when nodes are typically far from each other, the target nodes will aggregate many empty messages. Using Figure as an example, the source and node are distance 3 from each other. Because of this, in the first two iterations NBFNet will propagate node 6 to node 7, even though node contains no information. However, this is less of an issue between nodes of shorter distances as there fewer iterations needed to reach it. From this, we hypothesize that graphs that feature, on average, larger distance between nodes will propagate more empty messages.
Table 8: Mean Degree of Transductive Datasets
Dataset
Mean Degree
FB15k-237 WN18RR
18.7
2.1
Table 9: Distance Distribution of Test Samples on the Transductive Datasets
Distance
FB15k-237
WN18RR
0%
35%
73%
9%
26%
21% %
0.2%
7%
0.005%
9%
6+
0%
18%
From the results in Table 8 and we make the following observations: (a) WNI8RR is much sparser than FB15k-237 The higher density of FB15k 5377 leads to many more paths and subsequent opportunities to visit node already the path. The opposite is true for WN1SRR since the average degree is low, few paths exist in the graph. This results in many more redundant paths existing in FB15k-237 compared to WNISRR. (b) For FB11k-227, the vast majority of test samples are close each other. This leads less empty messages. However, for WN18RR the distance covers a much wider range. For example, over 33% of test samples have a distance of between them. This only true for 0.205% of samples on 237..-237. This helps explain why TAGNet mostly prunes empty messages on WNI8RR, as the larger distance berween nodes leads to many messages that contain no information.


Reviews:
[{"review_id": "dDvc79pOec", "reviewer": "Reviewer_jKiL", "summary": "", "questions": "Question A: What is the running time of the proposed approach and how does it reduce compared to the other competitors?\nQuestion B: What is the complexity of computing the shortest distance for each node pair? How is it scalable?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. We respond to your comments below.\n\n> **Q1**: \"The writing and presentation of the paper could be further improved to be more understandable for various readers with different backgrounds.\"\n\nThank you for your suggestion. We hope to make our paper as accessible as possible to those from different backgrounds. To achieve this goal, we plan to give a more in-depth definition of the background equations in Section 2 below. We further define the different notations and operators used in the paper. We will revise our paper to more properly define these equations and other notations.\n\n**Equation 1**:\n\n$$\nh_q(s, o) = \\bigoplus_{t=1}^T \\bigoplus_{p \\in P_{s,o}^t} \\bigotimes_{i=1}^{\\lvert p \\rvert} \\mathbf{w}_q(e_i)\n$$\n\nWe are interested in whether there exists and edge $(s, q, o)$ where $s$ and $o$ are nodes and $q$ is a relation. Eq. 1 solves this by aggregating all paths between $s$ and $o$. Since this can be too computationally expensive, we limit to aggregating all paths up to a max length $T$. The set of all paths of length $t$ between $s$ and $o$ is given by $p \\in P_{s,o}^t$. A single path $p$ is characterized by all the edges in that path $e_i \\in p$. We assume that for each edge $e_i$ there exists an edge representation $\\mathbf{w}_q(e_i)$ that is conditional on the query relation $q$ we are trying to predict.\nThe operators $\\bigoplus$ and $\\bigotimes$ can be represented by the sum, max, min, or multiplication. In Zhu et al. (2021) they show that this formulation can capture many existing graph algorithms including the katz index, personalized pagerank, the graph distance, and more.\n\n**Equations 2 and 3**:\n\n$$\nh_q^{(0)} (s, o) = \\mathbf{1}_q (s = o)\n$$\n\n$$\nh_q^{(t)} (s, o) = \\bigg(\\bigoplus_{(x, r, o) \\in \\mathcal{E}(o)} \\mathbf{h}_q^{(t-1)}(s, x) \\otimes \\mathbf{w}_q(x, r, o) \\bigg)   \\oplus\\mathbf{h}_q^{(0)} (s, o),\n$$\n\nAn issue with Equation 1 is that even when $T$ is small, it can be very inefficient to consider all possible paths. To combat this problem, the generalized Bellman-Ford algorithm is used. This algorithm works in an iterative manner. For the edge we are trying to predict, $(s, q, o)$, we first initialize its edge representation via the indicator function in Eq. 2. This evaluates to the {**1** vector when the edge $s = 0$ and otherwise is **0**. As before, we also associate an edge representation for each edge, denoted as $\\mathbf{w}_q(x, r, o)$. \n\nThe iterative computation in Eq. 3 has two components. In the first, we consider all edges where $o$ is the object entity. They are combined via an aggregation function $\\bigoplus$ (e.g., sum, max, etc.). For each edge $(x, r, o)$ we consider the path information from $s$ to $x$, $\\mathbf{h}_q^{(t-1)}(s, x)$, and the edge representation from $x$ to $o$. Since the pair representations are initialized to **0**, at $t=1$ there is no path information from $s$ to $x$. As such only the edge representation $\\mathbf{w}_q(x, r, o) \\geq 0$. Therefore we only consider paths of length 1. At $t=2$ the representations $\\mathbf{h}^{(1)}(s, x)$ will not be non-zero. This will represent the cost of traversing the paths of length 1 between $s$ and $x$. Thereby aggregating $\\mathbf{h}^{(1)}(s, x)$ and $\\mathbf{w}(x, r, o)$, we are considering the cost from $s$ to $x$ and $x$ to $o$. This is a path of length 2. This is done until some maximum iteration $T$. \n\nThe second component $\\mathbf{h}_q^{(0)} (s, o)$ is the boundary condition. If $s = 0$ we know the shortest path between them must be 0. This equation degenerates to the shortest-path Bellman-Ford when $\\otimes=+$ and $\\oplus=min$.\n\n**Equation 4**\n\n$$\nh_o^{(0)} = \\text{INDICATOR}(u, v, q)\n$$\n\n$$\nh_o^{(t)} = \\text{AGG} \\Big( \\\\{ \\text{MSG} (\\mathbf{h}_x^{(t-1)}, \\mathbf{w}_q(r)) \\, | (x, r, o) \\in \\mathcal{E}(o) \\\\} \\cup  \\\\{ \\mathbf{h}_o^{(0)} \\\\} \\Big)\n$$\n\nZhu et al. (2021) introduce a neural version of the generalized bellman ford algorithm (Eq. 2 and 3) . This is achieved via the introduction of learnable parameters. This includes:\n- Instead of the **1** vector, the INDICATOR function assigns a learnable embedding when the condition is true. Otherwise it assigns the **0** vector.\n- A learnable embedding for each relation $r$. As such, $\\mathbf{w}_q(r)$ is not conditional on $q$ and can be written as $\\mathbf{w}(r)$. \n- A MSG function for combining the representation of node $x$ and the relation embedding, i.e., $\\mathbf{h}_x^{(t-1)}$ and $\\mathbf{w}(r)$. This replaces $\\otimes$. An example is the elementwise product.\n- Instead of the $\\bigoplus$ operator, an AGG function is used. An example is the summation. This also includes a learnable projection matrix $W$. In practice, NBFNet utilizes the PNA aggregation (Corso et al., 2020).\n\n> **Q2**: \"straightforward adjustment to existing research. Limited technical contribution.\"\n\nWe respectfully disagree this comment. In the following, we show that our work **identifies and solves two key efficiency issues plaguing all path-based GNNs**. Then we demonstrate that it provides a new perspective to improve the efficiency which are complementary to existing efficiency strategies. \n\nThese two issues are:\n- **Empty Messages**: Current path-based GNNs propagate many empty messages. These are messages that contain no information, a common problem in path-based GNNs. We give an example from Figure 1a in our paper. At iteration 1, node 6 contains no information (i.e., it was initialized to $\\mathbf{0}$). However, it is still aggregated by node 4 and node 7. **This needlessly adds additional computation without resulting in node 6 containing more path information.**\n- **Redundant Information**: Path-based GNNs are liable to aggregate paths that contain a lot of redundant information. This often occurs as some paths (note: strictly speaking they are walks not paths) may traverse the same nodes or edges multiple times. We give an example from Figure 1a when using NBFNet. In the first two iterations, node 4 aggregates two paths including (source, 4) and (source, 3, 4). However, in the 5th iteration, node 4 aggregates paths of length 5 that contain redundant nodes. For example, the path (source, 4, source, 4, source, 4), where we go back and forth between the source and node 4. **Such paths add little to no additional path information that wasn't already aggregated by previous messages**.\n\nWhile methods like A\\*Net do improve the efficiency of path-based GNNs, **they may still propagate empty or redundant messages**. Since in A\\*Net the nodes propagated to are selected via a set of learnable parameters, there's no guarantee it'll learn to remove the empty and redundant messages. We demonstrate this in Table 3 in our paper. We calculate the number of messages propagated when using  just A\\*Net and A\\*Net + TAGNet (our method). We observe that when using both methods, over 33\\% of the messages propagated by A\\*Net can be removed. Furthermore, we can also improve on the time of both NBFNet and A\\*Net when using TAGNet (see the Table in Q3). This proves the need for TAGNet. In addition, as shown in Tables 1 and 2, when pruning messages via both of our strategies **the performance is the same or better than only A\\*Net**.\n  \nThis means we can greatly improve the efficiency of A\\*Net with no loss in performance. The same can be applicable for AdaProp, which is similar to A\\*Net. We further emphasize that these gains in efficiency are on top of those already gained on just NBFNet, where we can remove over 90\\% of the messages (see Figure 3 in our paper). As such, **TAGNet can be added to any path-based GNN to improve the efficiency while achieving comparable or better performance**. \n\n>**Q3**:  \" What is the running time of the proposed approach and how does it reduce compared to the other competitors?\"\n\nThe runtime on both FB15k-237 and WN18RR are shown below for each method. We used the same batch size for each method and chose $\\delta=2$ for TAGNet. All experiments were run on a single NVIDIA RTX A5000. **The runtime represents the number of minutes needed to train 1 epoch**.\n\n\n| **Method** | **WN18RR** | **FB15k-237** |\n|-----------------|-----------------|-----------------|\n| NBFNet          | 16.0            | 48.1            |\n| TAGNet          | 10.8            | 34.4            |\n| A\\*Net          | 8.4             | 33.7            |\n| TAGNet + A\\*Net | 5.6             | 26.3            |\n\nWe find that both TAGNet and A\\*Net can improve the efficiency of NBFNet. \nWe note that A\\*Net is slightly faster than TAGNet. This is as expected as it tends to remove many more messages than A\\*Net. However, since A\\*Net and TAGNet are **complementary** and **not competing methods**, combining them (i.e., TAGNet + A\\*Net) can further improve the efficiency.\nFurthermore, when using TAGNet in conjunction with A\\*Net we are still able to significantly reduce the number of messages relative to A\\*Net. This is demonstrated in Table 3. Lastly, we note that TAGNet achieves strong performance even when improving the efficiency. As shown in Table 1, TAGNet can outperform even NBFNet on the transductive datasets.\n\n>**Q4**:  \"Theorem 1 looks somehow trivial.\" \n\nOur goal with Theorem 1 is to prove that the truncated Bellman-Ford algorithm (see Eqs. 6 and 7) can capture the same information as in Eq. 5. As a reminder, Eq. 5 demonstrates the information we hope for our algorithm to capture for a node pair (s, o). This is all paths of length in the range [dist(s, o), dist(s, o) + $\\delta$]. Furthermore, not only do we want to aggregate this information, but **we want this to be the only information we aggregate**. We do not want to aggregate any paths of length greater than dist(s, o) +$\\delta$. Therefore, in addition to our empirical results, **the theorem is necessary** to provide theoretical evidence to support the advantages of our method. \n\nMeanwhile, we also face challenges to prove this as all target nodes are being updated in parallel. That is, given a source $s$, all target nodes $o \\in \\mathcal{V}$ are also updated. This is due to the iterative nature of the algorithm. As such, we are faced with the challenge of ensuring we aggregate the paths of the correct length range for the different target nodes.  \n\nWe prove that our algorithm can achieve this. Specifically, Theorem 3.1 proves that our formulation (see Eqs. 6 and 7) does in fact satisfy Eq. 5. This is achieved by only aggregating the nodes in the set C(s, o, t) (see Eq. 6). This leads us to  only aggregate paths of length in the range [dist(s, o), dist(s, o) +$\\delta$]. As such the final representation of the node pair (s, o), denoted by $x_{(s, o)}^F$\n, only contains this path information. Please see Appendix A.1 for a detailed proof for this theorem.\n\n> **Q5**: \"target-specific $\\delta$ does not work\"\n\nWe respectfully point out that the target-specific $\\delta$ leads to an increase in performance on **all transductive and inductive versions** of the WN18RR dataset. Furthermore, the performance gains on some splits like WN18RR v1 and v3 can be significant with an increase in MRR of around 0.01. \n\nHowever, we admit that there is limited benefit to using a target-specific $\\delta$ on FB15k-237. This is likely caused by the different characteristics of the two graphs. Mainly, that FB15k-237 is much denser than WN18RR. For example, on the transductive version of FB15k-237, 99.8\\% of test samples have a shortest path distance of 2 or 3. However, for WN18RR the shortest path distances varies greatly, with about 33\\% of the test samples having a shortest path distance of $\\geq 4$. Please refer to Figure 1 in our paper for the full distribution.\n\nThe low variation in the shortest path length implies that a target-specific $\\delta$ will have a limited impact. This is because there is little difference in how any two nodes in the graph relate to each other. So one value of $\\delta$ will likely work well for most node pairs. On the other hand, for WN18RR the distance between nodes can vary greatly. As such, some node pairs may have many shorter paths connecting them while other may have few longer paths. In this case, tailoring the $\\delta$ to each sample may be desirable. \n\nLastly, we note that in general, there is a strong incentive to use a target-specific $\\delta$ as it provides additional flexibility. Instead of having one fixed $\\delta$, it allows us to customize the path information to each sample. This can be very useful for datasets where paths of different length relative to the shortest path distance may vary greatly in importance. Furthermore, it simplifies the tuning process, as only a maximum $\\delta$ needs to be specified. Lastly, we note that it has no effect on the complexity as shown in Appendix B.2. \n\n> **Q6**:  \"What is the complexity of computing the shortest distance for each node pair? How is it scalable?\"\n\nWe use a BFS. For a single sample the worst case is O($\\lvert E \\rvert + \\lvert V \\rvert$) where $\\lvert E \\rvert$ and $\\lvert V \\rvert$ are the number of edges and nodes in the graph, respectively. However, we note that this can be computed before training and stored on disk. As such, this can be considered an offline operation, **thereby not effecting the training and testing runtime**. \n\n> **Q7**:  Grammar+Writing\n\nThank you for your comments. We will revise our paper accordingly.", "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": "-- The paper points out an overlooked problem in recent state-of-the-art path-based link prediction methods and presents a way to address this problem.\n\n-- The proposed method preserves the performance while reducing the number of messages, addressing efficiency issues of previous works.", "reasons_to_reject": "-- The writing and presentation of the paper could be further improved to be more understandable for various readers with different backgrounds, e.g., equation 1 and its description are not enough to understand them well, as the notation and operators are not defined well and it is required to look at the references to find its actual meaning while it is expected that the paper is standalone, or similarly indicator and u, v, msg are not defined well. I have to read the NBFNet paper first to understand them.\n\n-- The central aspect of the suggested approach involves a straightforward adjustment to existing research, with a limited technical contribution. \n\n-- It is expected to have running time besides time complexity analysis. Moreover, a discussion about running time and time complexity should be in the main body of the paper as it is one important aspect of the paper.\n\n-- Theorem 1 looks somehow trivial. \nAdding target-specific \\delta does not work according to the overall results.", "questions_to_authors": "Question A: What is the running time of the proposed approach and how does it reduce compared to the other competitors?\nQuestion B: What is the complexity of computing the shortest distance for each node pair? How is it scalable?", "paper_topic_and_main_contributions": "Link prediction approaches aim to address the problem of knowledge graph incompleteness. The methods that leverage aggregation of path information through a learning process have recently shown promising performance in link prediction tasks. In particular, the neural Bellman-Ford method presents a neural version of the Bellman-Ford algorithm that computes path information via dynamic programming. The aim is to learn pairwise node representation inductively. \nThe paper points out that the neural Bellman-Ford algorithm suffers from inefficiency due to two reasons: a) Empty message: the nodes which are far from the source node receive empty messages when their shortest path to the source node is bigger than the number of propagation layers, b) Redundant message: For a large number of layers, the close nodes get most of the information from the shortest path propagation steps, and longer paths do not give substantial information while presenting a more complexity. \nBy proposing a modification over existing works, the paper aims to address the mentioned issues to enhance the efficiency of path-based methods. In particular, a new path-based GNN model is proposed by revising the formulation of the NBF model to only consider the iteration t between the shortest path with the offset of \\delta. As \\delta is a hyperparameter, the paper further proposes an attention mechanism to pay attention to the most relevant representation from 1 to \\delta offsets. \nThe experiments have been done on both transductive and inductive settings on popular benchmark datasets such as FB237 and WN18RR. The proposed method obtains competitive performance to NBFnet and A*-Net while reducing the number of propagated messages.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "Page 4, line 309:C ->  \\mathcal{c}\nPage 5, line 338: given -> give\nIn An Illustrative Example, it might be better to first determine s and o, and then run the process.\nPage 5, line 383: no verb is given"}}, {"review_id": "mgL5QHHlwK", "reviewer": "Reviewer_VWSR", "summary": "", "questions": "See Weaknesses", "limitations": "", "rating": 3, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the review for taking the time to help improve our paper. We respond to their questions and comments below.\n\n> **Q1:** More explanation and experiment comparison between your work and A\\* Net.\n\nThank you for your suggestion. We will add such additional discussions and experiments in our revision. We include both below.\n\nWe first give a brief explanation of our model vs. A\\*Net. Both methods attempt to reduce the number of messages propagated by NBFNet. This is of paramount importance as in practice NBFNet can be very computationally expensive to run.  A\\*Net attempts to do so by only propagating messages to a small subset of nodes at each iteration. The nodes are chosen based on a set of learnable parameters. However, we take a new perspective approach to solving this problem. Our framework improves the efficiency by instead not propagating messages we find unnecessary and redundant. These are reasoned from two observations found in Section 3.1. The first is that we want to avoid propagating **empty messages**. These are messages that contain no information, a common problem in path-based GNNs. Secondly, we also want to avoid aggregating paths with too much **redundant information**. This often occurs as some paths may traverse the same nodes or edges multiple times (note: these are strictly walks as they contain repeated nodes). As such, there is no utility in propagating such messages.\n\nHowever, **it is not guaranteed that A\\*Net (or AdaProp) will  remove the empty or redundant messages**. To remedy this, we can apply TAGNet to other path-based GNNs to further improve their efficiency. This is because TAGNet is a general framework that can work in conjunction with any path-based GNN. In our paper we show the results when combining the pruning strategies of TAGNet and A\\*Net. We refer to this as ``A\\*Net + TAGNet\".  We observe that when using both methods, over 33\\% of the messages propagated by A\\*Net can be removed (see Table 3 in our paper). This proves the need for TAGNet, even when using efficiency-minded methods like A\\*Net. Furthermore, as shown in Tables 1 and 2,  **when pruning messages via both of our strategies the performance is the same or better than only A\\*Net**. This means we can greatly improve the efficiency of A\\*Net with no loss in performance.  \n\nTo further compare TAGNet and A\\*Net, we also show the number of messages propagated by both methods **individually** and  **combined**. We further include a comparison with NBFNet. The results are shown in the Table below for FB15k-237 when varying the number of layers from 6, 7, and 8. For TAGNet, we use the best performing $\\delta$ (i.e., $\\delta=2$). \n\nWe observe that while A\\*Net may propagate less messages **by itself**, it still contains many empty and redundant messages. This can be seen as A\\*Net+TAGNet prunes a large percentage of the messages propagated by just A\\*Net. This is further amplified as the number of layers increases.  Most importantly we find the performance between A\\*Net and TAGNet on all datasets are comparable and better than just A\\*Net (see Tables 1 and 2 in paper). **This emphasizes the need for TAGNet even when using A\\*Net, as it can help remove unnecessary and potentially harmful messages**.  \n\nWe appreciate these suggestions and we will revise our paper with the explanation and experiment comparison.\n\n| **Method** | **Layers=6** | **Layers=7** | **Layers=8** |\n|-----------------|-------------------|-------------------|-------------------|\n| NBFNet          | 3,265,380         | 3,809,610         | 4,353,840         |\n| A\\*Net          | 230,638           | 284,198           |   336,523              |\n| TAGNet          | 1,626,144         | 1,627,239         | 1,627,397         |\n| A\\*Net + TAGNet | 84,237            | 138,581           | 139,249           |\n\n\n> **Q2**: Do you follow the principles of establishing bidirectional edges when exploring the shortest path in the WN18RR dataset?\n\nYes, we include all bidirectional edges when computing the shortest path. It is calculated via a BFS, which visits each node or edge in the graph at most once. We will include this in our revision. \n\n> **Q3**: Have you considered the paths of duplicate points and edges?\n\nIn fact, **this is one of the motivations and advantages of our method**. In our study we observe that methods such as NBFNet tend to aggregate paths with duplicates edges and nodes (see observation 2 in Section 3.1). We give an example using Figure 1a in our paper when running NBFNet with 6 layers. In the first two iterations node 4 aggregates two paths including (source, 4) and (source, 3, 4). However in the 5th iteration, node 4 aggregates paths of length 5 that contain redundant nodes. An example would be the path (source, 4, source, 4, source, 4), where we go back and forth between the source and node 4.\n\nThis observation is one of the guiding points of our model design. To combat excessive backtracking, we introduce a hyperparameter $\\delta$. Formally, $\\delta$ is an offset that defines the maximum path length that nodes can aggregate. I.e., when $\\delta=1$, we allow nodes to aggregate all paths of length up to and including $\\text{shortest-path}(u, v) + 1$. The hyperparameter $\\delta$ also allows us to indirectly control the amount of duplicate edges/nodes we aggregate. Going back to Figure 1a, when $\\delta=4$, node 4 will additionally aggregate the path (source, 4, 6, 7, 6, 4). This allows node 4 to gather information from node 7. However if $\\delta=3$, this path won't be aggregated. \n\nThe decision of whether to aggregate redundant messages depends on the dataset. Since $\\delta$ is a hyperparameter it can be customized for each dataset. Furthermore, we also introduce a target-specific $\\delta$ in Section 3.5. This allows further customization down to the sample level.\n\n> **Q4**: More experiments for the complexity analysis (time+space)\n\nThe runtime on both FB15k-237 and WN18RR are shown below for each method. We used the same batch size for each method and chose $\\delta=2$ for TAGNet. All experiments were run on a single NVIDIA RTX A5000. **The runtime represents the number of minutes needed to train 1 epoch**.\n\n\n| **Method** | **WN18RR** | **FB15k-237** |\n|-----------------|-----------------|-----------------|\n| NBFNet          | 16.0            | 48.1            |\n| TAGNet          | 10.8            | 34.4            |\n| A\\*Net          | 8.4             | 33.7            |\n| TAGNet + A\\*Net | 5.6             | 26.3            |\n\nWe find that both TAGNet and A\\*Net can improve the efficiency of NBFNet. \nWe note that A\\*Net is slightly faster than TAGNet. This is as expected as it tends to remove many more messages than A\\*Net. However, since A\\*Net and TAGNet are **complementary** and **not competing methods**, combining them (i.e., TAGNet + A\\*Net) can further improve the efficiency.\nFurthermore, when using TAGNet in conjunction with A\\*Net we are still able to significantly reduce the number of messages relative to A\\*Net. This is demonstrated in Table 3. Lastly, we note that TAGNet achieves strong performance even when improving the efficiency. As shown in Table 1, TAGNet can outperform even NBFNet on the transductive datasets.\n\n\n> **Q5**: Comparison between your work with some anchor-based efficient KGE models, such as Nodepiece\n\nWhile both papers are concerned with efficiency, we respectively point out that **their scopes are substantially different**. NodePiece is concerned with reducing the number of parameters for **KG embedding models (KGE)**. As opposed to standard KGEs that represent each node with one embedding, NodePiece constructs a node's representation from a series of anchor nodes and relational contexts. On the other hand, our work is concerned with improving efficiency of **path-based GNNs** by reducing the number of messages aggregated. Since path-based GNNs don't feature node embeddings, they often have a much smaller number of parameters than KG embedding models but they usually face the efficiency issue that motivates our current work. \n\nFurthermore, we note that the efficiency of NodePiece comes at a significant cost to performance. In their study, they are able to achieve a MRR of 0.256 and 0.403 on FB15k-237 and WN18RR, respectively. This is considerably lower than our performance of 0.421 and 0.562 on FB15k-237 and WN18RR, respectively.\n\nWe will revise our paper to include a discussion of NodePiece in the related work.", "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": "A. Point out two essential problems in NBFNet, i.e., \"empty messages\" and \"redundant messages\"\n\nB. Clear presentation and well-written.\n\nC. Technique solid. The effectiveness of the model is proven both experimentally and theorically.", "reasons_to_reject": "A. More explanation and experiment comparison between your work and A* Net.\n\nB. Do you follow the principles of establishing bidirectional edges when exploring the shortest path in the WN18RR dataset? Have you considered the paths of duplicate points and edges? I hope this analysis can be more specific.\n\nC. More experiments for the complexity analysis (time and space)\n\nD. Comparison between your work with some anchor-based efficient KGE models, such as Nodepiece [1].\n\n[1] Galkin, M., Denis, E., Wu, J., & Hamilton, W. L. (2021). Nodepiece: Compositional and parameter-efficient representations of large knowledge graphs. arXiv preprint arXiv:2106.12144.", "questions_to_authors": "See Weaknesses", "paper_topic_and_main_contributions": "This work is developed based on NBFNet. The paper point out and analyze the problems of \"empty messages\" and \"redundant messages\" in message communication. The author proposes a truncated Bellman-Ford method (TAGNet) to solve the problem. Extensive experiments demonstrate that TAGNet outperforms NBFNet.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "N/A"}, "extra_text": {}}, {"review_id": "KHUIzM7SEm", "reviewer": "Reviewer_NkaF", "summary": "", "questions": "How should we think about the performance difference of TagNet + A∗Net and the two methods applied independently?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review. We respond to your questions and comments below.\n\n> **Q1**:I don't think I really understand how to think about TagNet + A\\*Net? I feel the results are somewhat confusing why they are sometimes worse than both methods independently.\n\nWe apologize for the confusion. For the method \"TAGNet + A\\*Net'', we are actually applying the pruning strategies of both A\\*Net and TAGNet (our framework). This works by successively applying the strategies of both methods. We first chose which nodes to propagate to via the A\\*Net algorithm. Then, we use the TAGNet algorithm to remove the empty and redundant messages (see Section 3.1 for a detailed discussion on both). We refer to this strategy as **A\\*Net + TAGNet** as it combines the strengths of both methods. This is needed as A\\*Net is not guaranteed to remove **empty** or **redundant** messages. \n\nIn the paper, our method \"TAGNet'' is based on NBFNet (no pruning) by default. Therefore, \"TAGNet'' in the paper is actually referring to \"TAGNet+NBFNet\", which applies pruning techniques of \"TAGNet'' to NBFNet. \"TAGNet + A\\*Net'' aggregates fewer messages than \"TAGNet''. This is due to the addition of the A\\*Net pruning strategy which results in many messages being removed. Since A\\*Net' achieves worse performance than NBFNet, it is expected that A\\*Net + TAGNet is likely to achieve worse performance than TAGNet. We will update this in the paper to make it clear.\n\n\nComparing the performance of \"A\\*Net + TAGNet\" and A\\*Net, we find that **\"A\\*Net + TAGNet\" performs better than A\\*Net on 6/10 datasets**. On the other datasets it achieves comparable performance to A\\*Net. This is though \"A\\*Net + TAGNet\" can remove many of the messages propagated by A\\*Net. As shown in Table 3 in our paper, A\\*Net + TAGNet can reduce the number of messages by over 33\\% compared to only A\\*Net. \n\n**The strong performance of \"A\\*Net + TAGNet\" relative to A\\*Net validates our observations in Section 3.1. As even when removing both empty and redundant messages from A\\*Net, the performance is not compromised.** \n\nWe will clarify these in the revision. \n\n\n> **Q2**:I think understanding the differences in performance across datasets could be improved with some analysis of the underlying graphs.\n\nWe appreciate the suggestion. We take a closer look as to what kind of messages are pruned by TAGNet (i.e., empty or redundant) for the different datasets. We then examine the reason why some datasets may prune more empty or redundant messages. \n\nWe first analyze the number of **empty** and **redundant** messages pruned for each dataset. As a reminder, we identified these messages as a main cause of inefficiency in path-based GNNs. TAGNet is meant to address this. We therefore further report which types of messages are more prevalent in the different datasets. \n\nWe report the results below as a \\% of the total number of pruned messages. E.g., For FB15k-237 51\\% of the total number of pruned messages are empty messages. The table shows the analysis for the transductive version of both WN18RR and FB15K-237. For simplicity, we limit this study to the the best versions of each model, i.e. $\\delta=2$ for FB15K-237 and $\\delta=3$ for WN18RR. \n\n| **Dataset** | **\\% Empty** | **\\% Redundant** |\n|------------------|-------------------|-----------------------|\n| FB15k-237        | 51\\%              | 49\\%                  |\n| WN18RR           | 91\\%              | 9\\%                   |\n\nWe find that on FB15k-237, the messages pruned are evenly split between empty and redundant messages. On the other hand, for WN18RR over 90\\% of the messages pruned are empty messages. However, **it is not clear why the composition of empty and redundant messages differ so much between datasets**.\n\nTo better analyze this, we take a closer look at the sparsity and distance distribution of both datasets. We first analyze the sparsity via the average degree. We do this as graphs with a low average degree will contain few connections between nodes, resulting in fewer paths between different nodes and thereby fewer redundant paths. Furthermore, there will be a lower chance of a node visiting another node already on the path, as most nodes are linked to only a handful of nodes. \n\nWith this idea, we present the average degree of FB15k-237 and WN18RR below. We observe that WN18RR is very sparse while FB15k-237. The higher density of FB15k-237 allows many more paths and opportunities to visit a node already on the path. The opposite is true for WN18RR as since the average degree is low, few paths exist in the graph. **This gives us an indication as to why many redundant paths are pruned from FB15k-237 and not WN18RR**.\n\n| **Dataset** | **Avg Degree** |\n|------------------|---------------------|\n| FB15k-237        | 18.7                |\n| WN18RR           | 2.1                 |\n\n**To better understand the number of empty messages pruned**, we further examine the distance distribution of both datasets. This is because when nodes are typically far from each other, the target nodes will aggregate many empty messages. Using Figure 1a as an example, the source and node 7 are a distance 3 from each other. Because of this, in the first two iterations NBFNet will propagate node 6 to node 7, even though node 6 contains no information. However, this is less of an issue between nodes of shorter distances as there fewer iterations needed to reach it. **From this, we hypothesize that graphs that feature, on average, a larger distance between nodes will propagate more empty messages.**\n\nWe examine this by calculating the shortest path distance of all test samples. This is shown in the table below. We find that for FB15k-237, the vast majority of samples are close to each other. This limits the potential of empty messages being aggregated. However, for WN18RR the distance covers a much wider range. For example, over 33\\% of test samples have a distance of 4+ between them. This is only true for 0.205\\% of samples on FB15k-237. This gives further justification as to why most of the pruned messages on WN18RR are empty messages, **as the larger distance between nodes enables TAGNet to prune many messages that contain no information**.  \n\n| **Distance** | **FB15k-237** | **WN18RR** |\n|-------------------|--------------------|-----------------|\n| 1                 | 0\\%                | 35\\%            |\n| 2                 | 73\\%               | 9\\%             |\n| 3                 | 26\\%               | 21\\%            |\n| 4                 | 0.2\\%              | 7\\%             |\n| 5                 | 0.005\\%            | 9\\%             |\n| 6+                | 0\\%                | 18\\%            |\n\nWe thank the reviewer for their suggestion and will include this analysis in our revision.", "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": "This paper has several strengths: \n* **Carefully Targeted Improvements** - The authors nicely short comings of GNN based methods. Then they address these directly and even show that the proposed approach achieves its benefits from these properties (e.g. Table 4). I think this kind of analysis is nice.\n* **Empirical Benefits** - The method seems to have empirical advantages compared to past work. I think these gains are nice, \n* **Additional methodological twists** - I think that 3.5.1 adds a bit more methodological interest.", "reasons_to_reject": "I think the paper indeed has several nice contributions. On the other hand concerns include: \n* I don't think I really understand how to think about TagNet + A∗Net? I feel the results are somewhat confusing why they are sometimes worse than both methods independently. Perhaps I've missed something here. \n* I think understanding the differences in performance across datasets could be improved with some analysis of the underlying graphs.", "questions_to_authors": "How should we think about the performance difference of TagNet + A∗Net and the two methods applied independently?", "paper_topic_and_main_contributions": "This paper observes that a limitation of past work on path-based GNN methods for KG completion is (1) Empty Messages and (2) Redundant Messages. To remedy these, the authors present TAGNet, which uses a truncated version of Bellman-Ford to capture paths of a given range of distances (e.g, upper and lower bound). The authors present empirical results that demonstrate that TAGNet achieves state-of-the-art results in transductive settings and good results in inductive setting.\n\nupdate\nThanks very much for the additional analysis and detailed response. I have increased the soundness score from 3->4.", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "Line 008: would be nice to say what the efficiency issues are\nLine 037: specify recent in GNN."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents TAGNet, a new model for knowledge graph completion which addresses the limitations of a previous model that propagates “empty messages” and “redundant messages”. This is achieved by only aggregating paths in a fixed window for each source-target pair. The model is evaluated on two standard knowledge graph completion datasets (FB15k-237 and WN18RR).

The reviewers agree that the paper is sound. They also agree that the proposed model is carefully designed to deal with the presented limitations of previous models (such as NBFNet and A*Net). Furthermore, the model appears to be empirically stronger than previous methods. However, the reviewers raised concerns about the time complexity of the model and asked for a comparison of the running time of TAGNet with that of the other models. Those concerns were partially addressed in the response. Finally, the reviewers also raised concerns about the significance of the contribution and the lack of novelty with respect to NBFNet.

Overall, it is my opinion that the work is interesting and technically solid. I also agree with various concerns that were raised in the reviews, but I think that these concerns are minor.
Decision: Accept-Main