Reasoning on large-scale knowledge graphs has been long dominated by embedding methods. While path-based methods possess the inductive capacity that embeddings lack, their scalability is limited by the exponential number of paths. Here we present A*Net, a scalable path-based method for knowledge graph reasoning. Inspired by the A* algorithm for shortest path problems, our A*Net learns a priority function to select important nodes and edges at each iteration, to reduce time and memory footprint for both training and inference. The ratio of selected nodes and edges can be specified to trade off between performance and efficiency. Experiments on both transductive and inductive knowledge graph reasoning benchmarks show that A*Net achieves competitive performance with existing state-of-the-art path-based methods, while merely visiting 10% nodes and 10% edges at each iteration. On a million-scale dataset ogbl-wikikg2, A*Net not only achieves a new state-of-the-art result, but also converges faster than embedding methods. A*Net is the first path-based method for knowledge graph reasoning at such scale.
Paper
Similar papers
Peer review
Summary
The paper introduces ANet, a scalable path-based approach for reasoning on extensive knowledge graphs (KGs). In contrast to embedding techniques, path-based methods exhibit inductive capabilities but encounter challenges in terms of scalability due to the exponential growth of paths. ANet addresses this issue by incorporating a priority function, inspired by the A\* algorithm for shortest-path problems, which enables the selection of crucial nodes and edges during each iteration. This novel approach effectively reduces the time and memory requirements for both training and inference processes.
Strengths
S1: This paper proposes an efficient GNN called A\*Net for link prediction with good scalability. S2: A\*Net shows impressive results on various KGs.
Weaknesses
W1: Although the method proposed in this article has better scalability, the contributions from theoretical perspectives are incremental compared to NBFNet. W2: The introduction of the parameter sharing between the priority function and predictor is somewhat unclear, and the reason why the reasoning task can be regarded as weak supervision for the priority function is not well explained.
Questions
Q1: The priority function in A\*Net is similar to the attention used in RED-GNN except that A\*Net selects the nodes and edges according to the attention score. In the case where memory allows, how does the performance of A\* Net change when Top operation is disabled in Algorithm 1 (line 5 & line 7)? Q2: If some nodes and edges are discarded in the early phase of model training, it may introduce incorrect inductive biases and prevent the model from training effectively. How do you address this issue to avoid such problems or why is this not an issue in A\*Net?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
2 fair
Presentation
3 good
Contribution
3 good
Limitations
See **Weaknesses** and **Questions**.
Summary
This paper presents a scalable path-based method for knowledge graph reasoning, which is inspired by the A* algorithm for shortest path problems.
Strengths
1. The intriguing approach of applying the A$^*$ algorithm's principle to path reasoning in KG is proposed in this paper, along with the introduction of novel methods for crafting the priority function. 2. The paper achieves state-of-the-art results on the large-scale KG reasoning dataset, ogbl-wikikg2. 3. There's a substantial enhancement in efficiency, considering both time and memory usage, as opposed to the top-performing baseline, NBFNet.
Weaknesses
The proposed method performs slightly worse than NBFnet as shown in Table 1, and no results of NBFnet are reported on tail prediction in Table 2.
Questions
1. In the context of KG reasoning, a crucial question is, how many steps are typically required for a query? According to the vanilla path reasoning in Equation 1, the number of paths increases exponentially with respect to path length. However, if the path length is typically small, this might not pose a significant problem? Moreover, when dealing with a large-scale KG, the BF algorithm would need to visit $|\mathcal{V}|$ nodes and $|\mathcal{E}|$ edges for each step, which can be quite computationally intensive. Given these considerations, it leads to the question: If the path length is usually small, could vanilla path reasoning be a more efficient choice compared to BF? 2. Another question is, can we simply leverage the idea of beam search into vanilla path reasoning? For example, we keep top-K ranked paths for each step, which may also avoid the exponential growth of the number of paths.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
Yes
Summary
The main contribution of this paper is presenting a scalable path-based method A*Net, for link prediction on large-scale knowledge graphs. A*Net is inspired by the A* algorithm for solving shortest path problems, where it learns a priority function to select important nodes and edges at each iteration. This allows for the time and memory reducing for both training and inference. From an efficiency perspective, this could be considered as a path-pruning method to progressively reduce the subgraph based on the learned priority function. The empirical results also demonstrate efficiency improvement.
Strengths
1. The efficiency problem caused by the explosively increasing entities in deeper propagation layers is indeed serious in the recent GNN-based inductive methods. And the proposed method makes sense and technically sound. 2. The experimental results are impressive. The paper demonstrates the practical applications of A*Net in various settings and datasets, with the efficiency improvement compared with several recent baselines. Furthermore, the paper sets a new state-of-the-art on the million-scale dataset ogbl-wikikg2 and converges faster than embedding methods. 3. The paper's organization is well-executed and the content is easily comprehensible.
Weaknesses
1. The paper's comparison to the A* algorithm seems somewhat overstated. As a derivative work of NBFNet, this paper draws an analogy to another shortest path algorithm, A*. Contrary to the Bellman-Ford algorithm that resolves the shortest path problem from the source to all other points, the A* algorithm typically addresses the shortest path problem from the source to a specific target point. However, in the context of knowledge graph (KG) reasoning, the target point is unknown, rendering the core principle of A*, assessing the estimated remaining cost to the target point, unfeasible. In fact, the A* algorithm's priority rule, involving the distance to the target node, is not pertinent to the priority function in the proposed model. The A* algorithm appears to function primarily as a promotional point, rather than as a guiding principle. 2. Perhaps due to the overemphasis on the A* analogy, the paper's true technical contributions remain unclear. Comparing the core function of NBFNet in Eq. 3 and that of A*Net in Eq. 12, the only discernible difference lies in introducing the priority score, calculated based on the embeddings of the query and the current node. Stripping away the A* algorithm framework, it essentially seems to be a path-pruning technique reliant on an attention mechanism to select the top K nodes and top L edges in each layer for efficiency's sake. 3. The paper lacks insightful contributions regarding important paths beyond a weighted version of the NBENet method. The theoretical appendix focuses solely on integrating path selection into the NBFNet framework, premised on the assumption that a certain function can distinguish important nodes. However, how to ensure that important paths are chosen is not clear. In response to this, the authors propose weight sharing between the priority function and the predictor, asserting that the reasoning task can be seen as a weak supervision for the priority function. However, this appears counterintuitive, given that the priority score is dependent on a specific query. A high predictor score, indicating that the node x answers the query (u, r_1), should not contribute to the priority score of x for a different query (u, r_2).
Questions
1. As addressed in Weaknesses 3, could you elaborate on how weight sharing aids in the selection of important paths? 2. I observe that two handcrafted priority functions, PPR and Degree, are employed in the ablation studies. Given that high connectivity doesn't necessarily denote the importance of paths, what about the effectiveness and efficiency of a random pruning strategy, particularly with respect to the obgl_wikikg2 dataset? 3. In the Visualization section, only the results of the proposed method are displayed without any comparison. Could you clarify what distinct paths the Neural function selects compared to the two handcrafted ones? Furthermore, does the Neural-based path selection align more closely with knowledge semantics?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
Yes. The authors stated the limitation, future work and social impact.
Summary
This paper proposes a scalable path-based knowledge graph reasoning approach. The idea is to extend only important paths from the exponentially growing set of all possible paths. A heuristic priority function is parametrized by a feed-forward network and is trained to predict the priority of nodes to expand. Experiments show that the proposed approach can significantly improve time and memory efficiency and also achieve good results.
Strengths
- Scalability is an important issue for path-based reasoning approaches. The idea of selecting only important paths is interesting and sounds reasonable - The proposed approach is effective and supported by extensive experiments. Time and memory efficiency has been significantly improved. Benchmark results are also good.
Weaknesses
My concern is mainly about the design of the priority function Eq (10) In Eq (10), the first part $h_q^{(t)}(u, x)$ is already conditioned on q, u, and x, so in principle the second part $g([h_q^{(t)}(u, x), q])$ doesn't provide any additional information. Therefore, the priority function is purely based on the current path from the start and contains no information about the goal. In other words, the prediction of the priority function would be the same even if the goal changes. This is different from the design of the A* algorithm and may lose theoretical guarantees. It is not appropriate to present the approach in the manner of A* algorithm
Questions
Please see Weaknesses
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
properly addressed
Comment by Reviewer rgXX
I thank the authors for their detailed response I agree that $u$ and $q$ contain some information about the goal. Now the explanation is a bit clearer by regarding $q$ as some kind of "relative goal". But I still don't think the alignment between A\*Net and A\* algorithm is appropriate **In A\* algorithm, $d(u, x)$ and $g(x, v)$ model complementary information based on different inputs: the current shortest path from $u$ to $x$, and the estimation of the cost from $x$ to $v$, respectively. However, in A\*Net, $h_q(\cdot)$ and $g(\cdot)$ in Eq (10) are conditioned on the same variables $u$, $q$, $x$.** The authors' response argued that $\textbf{h}_q(\cdot)$ and $\textbf{g}(\cdot)$ can have different inductive biases, but this argument is too vague... It is still not clear enough what different information is modeled by $\textbf{h}_q(\cdot)$ and $\textbf{g}(\cdot)$, since $\textbf{h}_q(\cdot)$ also takes into account the "relative goal" $q$. Therefore I don't think there is a clear correspondence between A\*Net and A\* algorithm. I will raise my score to 4 to reflect the authors' further explanation
Discussion
Thank you for your feedback. We understand your concern that it looks like we fabricated the story to make A\*Net looks like the A\* algorithm, but they are actually well aligned. The basic logic behind the alignment is 1. The A* algorithm have two equivalent formulations, one based on the absolute goal $v$, and one based on the relative goal from $u$ to $v$, as illustrated in our attached PDF file. 2. A\*Net follows the relative goal formulation of the A\* algorithm. There are two reasons that we must use this design: 1) We don’t have access to the absolute goal $v$ in knowledge graph reasoning, so we reparameterize with the source node $u$ and the relative goal $q$. 2) An absolute goal can’t transfer to unseen entities in the inductive setting, while a relative goal can. 3. The reason that $\mathbf{h}_q(\cdot)$ and $\mathbf{g}(\cdot)$ are conditioned on the same variable is that we additionally condition the representation $\mathbf{h}_q(\cdot)$ on the query relation $q$ following the common practice in path-based methods[1, 2, 3, 4, 5]. This step is optional. In other words, we can think of that $\mathbf{h}(\cdot)$ is parameterized by $u$, $x$ and $\mathbf{g}(\cdot)$ is parameterized $u$, $x$, $q$. 4. We verify this with ablation studies that either remove $q$ from the condition of $\mathbf{h}_q(\cdot)$ or from the priority function $\mathbf{g}(\cdot)$. We observe that conditioning on $q$ has a small gain on the performance (1.0% absolute difference in MRR) and is general to both NBFNet and A\*Net, suggesting that conditioning is not the key to the sucess of A\*Net. However, there is a significant performance drop for A\*Net without $\mathbf{q}$ in the priority function (22.6% absolute difference in MRR). This means that the relative goal $\mathbf{q}$ plays an important role in the priority function, which aligns with the intuition of the A\* algorithm. |FB15k-237|MRR|Hits@1|Hits@3|Hits@10| |---|---|---|---|---| |NBFNet (w/o conditioning)|0.400|0.306|0.439|0.585| |NBFNet|**0.415**|**0.321**|**0.454**|**0.599**| |A\*Net (w/o conditioning)|0.401|0.311|0.439|0.580| |A\*Net (w/o relative goal)|0.185|0.105|0.203|0.350| |A\*Net|**0.411**|**0.321**|**0.453**|0.586| We are aware that the alignment between A\*Net and the A\* algorithm is important for understanding the methodology of this paper. Hence we will clarify this point and add the above ablation studies in the revised version. [1] Yang et al. Differentiable Learning of Logical Rules for Knowledge Base Reasoning. NIPS 2017. [2] Sadeghian et al. DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs. NeurIPS 2019. [3] Zhu et al. Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction. NeurIPS 2021. [4] Zhang and Yao. Knowledge Graph Reasoning with Relational Digraph. WWW 2022. [5] Zhang and Zhou et al. AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoning. KDD 2023.
Thanks for your rebuttal
The authors addressed my concerns. Since my score is already positive, I'm maintaining my score.
Thanks so much for the detailed responses! While the rebuttal does provide some clarification, I still have some concerns. 1. The authors explained the query vector $\mathbf{q}$ in the second term of Eq. 10 can represent the relative distance from $u$ to $v$. However, this interpretation seems to be more of an intuitive justification rather than an inherent aspect of the model design. Meanwhile, since $\mathbf{q}$ is also a factor in the computation of each $h^{(t)}_q(u,x)$, it remains unclear if $\mathbf{q}$ maintains its independence and intuitive significance throughout the training process. 2. The authors emphasized that the major contribution is the first path-based method that scales to ogbl-wikikg2. Nevertheless, I question the true significance of this experimental work for the inductive models calculating at subgraph level. Because the model would not calculate in the entire large-scale KG, excluding part of nodes/edges is an obvious strategy to improve efficiency and scalability. Compared with embedding-based methods, the natural drawback of inference complexity still exists. 3. I also have one additional concern on the model's performance. Table 1 illustrates that the proposed method performs slightly worse than NBFNet. I am skeptical of the statement that the performance of NBFNet represents a definitive upper bound. Notably, a recent study titled "AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoning" has outperformed both RED-GNN and NBFNet by leveraging an edge sampling strategy. Given these considerations, I would like to keep my initial score.
Discussion (1/2)
Thank you for your feedback. Regarding your further concerns, here is our response. It would be nice if you can give us a basic feedback before the end of the discussion period. **C1: The query vector $\mathbf{q}$ in the second term of Eq. 10 can represent the relative distance from $u$ to $v$. However, this interpretation seems to be more of an intuitive justification rather than an inherent aspect of the model design. Meanwhile, since $\mathbf{q}$ is also a factor in the computation of each $h_q^{(t)}(u, v)$, it remains unclear if $\mathbf{q}$ maintains its independence and intuitive significance throughout the training process.** A1: We should correct that the query vector $\mathbf{q}$ represents the **relative position**, not the **relative distance**, from $u$ to $v$. The relative position contains not only the relative distance, but also the relative direction. For both A\*Net and the A\* algorithm, knowing the relative distance can’t fully recover the position of $v$ from the position of $u$, but knowing the relative position can. We agree that this is an intuitive justification, but it is also an inherent aspect for A\*Net to be inductive. We conjecture that you expected A\*Net to use the position of $v$ as the absolute goal, faithful to the A\* algorithm. First, as we disccused in Line 171-173, unlike the shortest path problem, we don’t know the answer entity $v$ beforehand in knowledge graph reasoning. So we can only reparameterize $v$ by $u$ and $q$ from the query. Second, if we use the absolute goal, no matter from an oracle or predicted by the representations $\mathbf{u}$ and $\mathbf{q}$, the model will fit to some absolute positional information, thereby can’t generalize to unseen entities in the inductive setting. Hence a relative goal $\mathbf{q}$ is better for preserving the inductive advantage of path-based methods. Yes, it is not that clear whether the representation $\mathbf{q}$ effectively captures the relative goal, when it is used as both the relative goal and the condition in Eqn. 2 & 3. We conduct ablation study to verify whether $\mathbf{q}$ contributes more as the relative goal or the condition. We consider two variants of A\*Net: 1) A variant without conditioning on $q$, where the indicator function (Eqn. 2) is replaced with $\mathbb{1}(u=v) = \overrightarrow{1}\text{ if }u=v\text{ else } \overrightarrow{0}$, and the edge representation (Eqn. 3) is replaced with $\mathbf{w}(x, r, v) = \mathbf{r}$. 2) A variant without the representation $\mathbf{q}$ in the neural priority function (Eqn. 10). Here are the results |FB15k-237|MRR|Hits@1|Hits@3|Hits@10| |---|---|---|---|---| |NBFNet (w/o conditioning)|0.400|0.306|0.439|0.585| |NBFNet|**0.415**|**0.321**|**0.454**|**0.599**| |A\*Net (w/o conditioning)|0.401|0.311|0.439|0.580| |A\*Net (w/o relative goal)|0.185|0.105|0.203|0.350| |A\*Net|**0.411**|**0.321**|**0.453**|0.586| We observe that conditioning on $q$ has a small gain on the performance (1.5% absolute difference in MRR) and is general to both NBFNet and A\*Net, suggesting that conditioning is not the key to the sucess of A\*Net. Note the conditioning design is a common practice to improve performance in path-based methods[1, 2, 3, 4, 5]. However, we observed a significant performance drop for A\*Net without $\mathbf{q}$ in the priority function (22.6% absolute difference in MRR). Hence we think $\mathbf{q}$ captures the relatively goal in the neural priority function and aligns with the intuition of the A\* algorithm. [1] Yang et al. Differentiable Learning of Logical Rules for Knowledge Base Reasoning. NIPS 2017. [2] Sadeghian et al. DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs. NeurIPS 2019. [3] Zhu et al. Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction. NeurIPS 2021. [4] Zhang and Yao. Knowledge Graph Reasoning with Relational Digraph. WWW 2022. [5] Zhang and Zhou et al. AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoning. KDD 2023.
Discussion (2/2)
**C2: Because the model would not calculate in the entire large-scale KG, excluding part of nodes/edges is an obvious strategy to improve efficiency and scalability. Compared with embedding-based methods, the natural drawback of inference complexity still exists.** A2: It is always trivial to scale up models by random sampling and sacrificing the performance, but **it is not trivial if we can scale up models without performance drop**. This is also the main point of previous papers that studied sampling methods for GNNs on homogeneous graphs[6, 7]. As for A\*Net, we have shown in the answer to your Q2 that random pruning strategy is significantly worse than A\*Net on FB15k-237 (3.3% absolute difference in MRR) and ogbl-wikikg2 (9.5% absolute difference in MRR) under the same node and edge ratios. In other words, A\*Net is strictly better than random pruning in terms of efficiency and effectiveness. A\*Net has an inference complexity of $O(T(\alpha|\mathcal{V}|d^2+\alpha\beta|\mathcal{E}|d))$ for answering a single query $(u, q,?)$. By comparision, its full counterpart, NBFNet, has a complexity of $O(T(|\mathcal{V}|d^2+|\mathcal{E}|d))$. Embedding methods such as TransE or RotatE have a complexity of $O(|\mathcal{V}|d)$ for enumerating all entities to answer the query $(u, q,?)$. If we take the hyperparameters from ogbl-wikikg2, A\*Net is about $6\times(0.002\times2.5\text{M}\times32^2+0.002\times1\times16.1\text{M}\times32)=37\text{MFlops}$. Embedding methods are about $2.5\text{M}\times500=1.25\text{GFlops}$. Empirically, A\*Net is even faster than embedding methods due to its pruning ratios $\alpha$, $\beta$ and small dimension $d$. We would advocate to compare different knowledge graph reasoning methods through pareto frontiers, e.g. what is the best model at the complexity of $O(|\mathcal{V}|d)$, and what is the best model at the complexity of $O(|\mathcal{V}|^2d)$. A\*Net is a new pareto frontier here since it achieves competitive performance with NBFNet while uses signficantly less time. To our best knowledge, none of the embedding methods (e.g. TransE, RotatE) at the complexity of $O(|\mathcal{V}|d)$ is inductive, and none of the inductive methods (e.g. GraIL, NBFNet, A\*Net) can reach the complexity of $O(|\mathcal{V}|d)$. Also the inference complexity of embedding methods doesn’t suggest their actual time cost in applications. When the graph changes over time (e.g. Wikidata), embedding methods need to be frequently re-trained on the whole graph to accommodate any new entity, which is very costly. By contrast, inductive methods like A\*Net can directly perform inference over such new entities. **C3: I am skeptical of the statement that the performance of NBFNet represents a definitive upper bound. Notably, a recent study titled "AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoning" has outperformed both RED-GNN and NBFNet by leveraging an edge sampling strategy.** A3: We feel it is a standard practice to assume that a sampling method is upper bounded by a full inference method in performance[6, 7] when they are compared as apples to apples. A\*Net exactly follows the neural parameterization and hyperparameters of NBFNet, so it is natural to think that A\*Net is upper bounded by NBFNet. AdaProp is compared to its full variant RED-GNN with different sets of hyperparameters, rather than a fair comparsion like ours. For example, AdaProp uses 8 layers and RED-GNN uses 5 layers, which explains the performance gain of AdaProp. [6] Chen et al. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. ICLR 2018. [7] Chen et al. Stochastic Training of Graph Convolutional Networks with Variance Reduction. ICML 2018.
Discussion
Thank you for recognition of our work! Regarding curriculum learning conjecture, we are running ablation studies to verify this claim. Due to the congestion in our cluster, we are not sure if we can get the results before the end of the discussion period, but we'll try our best to give you an answer.
# Summary of Discussions We appreciate every reviewer who participated in the discussions. Here is a summary of updates in the discussions. **Previous concerns:** - **The technical contribution of A\*Net is incremental (Reviewer 7LW7, ALvG):** - Reviewer ALvG doesn’t have further concerns on this point. Reviewer 7LW7 thinks sampling is an obvious strategy to improve scalability, and the time complexity of path-based methods is worse than embedding methods. - We emphasize that it is not trivial to perform sampling without performance drop. In our experiments for Q2 of Reviewer 7LW7, A\*Net outperforms the random pruning strategy with similar time and memory by 9.5% absolute difference in MRR on ogbl-wikikg2. For the time complexity, A\*Net is empirically better than embedding methods on ogbl-wikikg2 due to the pruning ratios and small hidden dimensions. The complexity of embedding methods doesn’t fully reveal their actual time cost in applications, as they are not inductive and need to be re-trained when the graph changes. - **The neural priority function contains no information about the goal and is different from the A\* algorithm (Reviewer rgXX, 7LW7):** - Both reviewers question about the necessity of the query vector $\mathbf{q}$ as the relative goal in the priority function, especially given that $\mathbf{q}$ is also used as the condition in the path representations. - By design, A\*Net requires a relative goal, rather than an absolute goal in the A\* algorithm, in its priority function to be inductive. We conduct ablation studies for the representation $\mathbf{q}$ used as the condition and the relative goal on FB15k-237. Using $\mathbf{q}$ as a relative goal is important for A\*Net (22.6% absolute difference in MRR), while using $\mathbf{q}$ as the condition only slightly improves the performance (1.0% absolute different in MRR). We are aware that this is important for understanding the alignment between A*Net and the A* algorithm. We will clarify this with ablation studies in the revised version. - **The weight sharing between the priority function and the predictor is not clear (Reviewer 7LW7, ALvG):** Both reviewers don’t have further concerns on this point. We’ll include our clarification in the revised version. - **Comparison with a random pruning strategy (Reviewer 7LW7):** Reviewer 7LW7 doesn’t have further concerns on this point. - **Comparison on path visualization of A\*Net, NBFNet, and handcrafted priority functions (Reviewer 7LW7):** Reviewer 7LW7 doesn’t have further concerns on this point. - **Performance of NBFNet on tail prediction (Reviewer 2kB4):** Reviewer 2kB4 doesn’t have further concerns on this point. - **Performance of A\*Net when pruning is disabled (Reviewer ALvG):** Reviewer ALvG doesn’t have further concerns on this point. **New concerns:** - **A full inference method may not be an upper bound for a sampling method. AdaProp is better than RED-GNN (Reviewer 7LW7):** We feel it is a standard practice to assume a full inference method is the upper bound[1, 2]. AdaProp improves the performance of RED-GNN because it uses more layers, but here we seek a fair comparison between A\*Net and NBFNet. [1] Chen et al. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. ICLR 2018. [2] Chen et al. Stochastic Training of Graph Convolutional Networks with Variance Reduction. ICML 2018.
Decision
Accept (poster)