Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Summary: In this study the authors propose a general framework to learn neural INDICATOR, MESSAGE and AGGREGATE functions for the generalized Bellman-Ford (BF) algorithm. They apply the neural BF to link prediction problems in multirelational knowledge graphs in the in-sample setting as well as in the out-of-sample setting, and in homogeneous graphs. On a practical level the approach trades compute with memory and shows good results on benchmark datasets.  
main_review: Originality: The approach combines the generalized BF algorithm with learnables neural operators and sets the approach well in context with previous work. 
 
Quality: The paper does not provide a proof or error bounds on the solution it can find. The study describes the proposed approach formally well but its usefulness is mostly backed up by empirical results. The approach is explored well, however, an aspect that was missing ---as the approach is very expensive--- it would be fair and important to show the compute trade-off as well as the memory trade-off for each of the groups (path-based, embedding, GNN) with the proposed approach in the performance comparison, as I don’t think it that they should be decoupled in such comparisons. While it does well regarding memory with embedding based methods, it does a lot worse compared to GRCN and even more so compared to embedding based methods. 

The experimental results do not cite state of the art results for FB15k-237 and WNRR which are for FB15k-237 much closer to the results obtained by the proposed approach. Complex achieves 0.37 MRR on Fb15k-237 and 0.49 MRR on WN18RR [1]. There are methods and dataset for out-of-sample settings for knowledge graph completion [2] that should be considered in the comparison. 

Another concern about the knowledge graph completion experiment ---and the evaluation description was not explicit about this and no code was provided--- is, which graph is known by the model during evaluation? Does it consist of (1) the training triples, or (2) the training-triples + the validation triples, or (3) the training+validation+testing triples (minus each testing triple once it is under evaluation of course)? Sometimes path-based methods use (2) or (3) which naturally leads to better results. Can the authors explicitly confirm which of the settings was the one that was used? For knowledge graph embedding methods the known graph corresponds to (1), i.e. only the training triples. If this is different in this study, then a performance comparison between embedding methods and this proposed method is not possible.  

One attractive property of the model is that the highest scoring paths can be inspected which can lead to new insights about datasets. 

Clarity: The paper is written well and the presentation is great. The experimental setup could be clearer. 

Significance: If the concerns can be ruled out, then the result would be important.  The method achieves good numbers on benchmark datasets. There is great interest in interpretable methods as well, which this method also does provide.   

limitations_and_societal_impact: Limitations and societal impact have been addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: 1. This paper proposes a new method for Link Prediction dubbed NBFNet, which is a hybrid approach that combines path based and GNN based approaches for Link Prediction. 
2. The core idea of the paper is about computing the representation of a pair of nodes, which is used for predicting links between the nodes. This representation is computed using three neural operators namely INDICATOR, MESSAGE and AGGREGATE, which represent the parameterised version of Bellman-Ford algorithm. 
3. Authors present experimental results on the tasks of Knowledge graph completion, link prediction in homogenous graphs, and inductive relation prediction. The proposed method performs better than the baseline models in all the tasks.
4. In addition, authors also perform ablation study with different MESSAGE & AGGREGATION functions. Furthermore, they also analyse the performance of NBFNet on different categories of relations. 
main_review: 1. The proposed method seems novel, the idea of using a parameterised Bellman-Ford algorithm is a neat one. 
2. AGGREGATE functions used in the paper are sum, mean, or max followed by a linear transformation and a non-linear activation, and PNA. Just curios, why didn't the authors not consider a weighted sum, with learnable weights? All the paths may not be equally important for computing the representation.
3. I am fairly satisfied with the quality and writing of the paper, I was able to follow the ideas in the paper without much struggle.
4. I am not completely satisfied with the experimental results.  NBFNet outperforms the other baselines in all the mentioned tasks, but the authors need to compare with more recent baselines. 
Authors should include at least a few of the following more recent baselines in their comparison. Or discuss why they are not relevant, if that is the case. 
Currently, the most recent baseline they include is from 2018. 

- LowFER: Low-rank Bilinear Pooling for Link Prediction, Amin et al, ICML 2020. 
- A Multi-Scale Approach for Graph Link Prediction. Cai et al, AAAI 2020. 
-  Learning Hierarchy-Aware Knowledge Graph Embeddings for Link Prediction, Zhang et al , AAAI 2020. 
- Contextual Parameter Generation for Knowledge Graph Link Prediction, Stocia et al, AAAI 2020. 
- Link Prediction with Persistent Homology: An Interactive View, Yan et al, ICML 2021. 


===== 
Post author-response. 
After reading all the reviews and authors response. I have decided to keep my score the same. 
limitations_and_societal_impact: Please refer to the Main Review section. 

If authors include more recent baselines in their experimental comparison, I am open to revising my recommendation.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes an adaptive version of the generalised Bellman-Ford algorithm to solve link prediction problems in both knowledge bases and inductive settings. The resulting formulation is a slight variation of a standard graph neural network that accomodates different types of relations and computes pairwise node representations, that is, a different representation of node v for each neighbour.
main_review: The paper undoubtedly has merits, such as:

- Mentioning the similarities between the usual message passing formulation of GNNs and the aforementioned algorithm.
- Conducting an experimental comparison that looks fair (though something must be clarified by the authors), obtaining results that consistently surpass previous works. Despite this consistency ironically raising a red flag at the beginning, to the best of my knowledge the results seem solid. This may be attributed to the more general formulation (w.r.t. link prediction) of the proposed approach. Unfortunately, the code to inspect all the model selection and assessment phases is not available.

With that being said, the general feeling after reading the article is that it may have been written in a rush. This is due to the organisational choices and technical definitions that make it difficult to follow the discussion and are confusing in more than one passage. Moreover, some of the crucial claims of the authors about scalability and model capacity are mostly described in the appendix. Generally speaking, this may be perceived as unfair practice: appendices should support the main claims rather than address them. In other words, without reading the appendix, a reviewer would be unable to comprehensively evaluate all the claims made by these authors.

As concerns interpretability (the term is - wrongly - used intercheangebly with "explainability" by the authors), one of the fundamental challenges to be addressed by the authors, there is no solid qualitative evidence that the model, quote, "learns soft logical entailment" or "performs analogical reasoning". The three examples of Table 6 do not appear to be that meaningful. While we can argue about the most effective ways to "prove" interpretability, the evidence proposed by the authors cannot be considered sufficient.

Overall, it appears that the authors made too many claims and were unable to properly fit them into a single conference paper. While the idea and results are (again) noteworthy, the quality of the paper definitely suffers because of its presentation, and this has to be taken into consideration given the level of the conference. Improving the manuscript in this sense may require substantial rewritring that might not be feasible at this point.

Technical comments:

Abstract: 

- please specify that the generalized sum is over the paths *between the nodes*.
- "very general" may be omitted

Section 1:

- Table 1 contains symbols that have not yet been introduced. Consider moving it at the end of Section 3. Also, a practical example of the MESSAGE, AGGREGATE and INDICATOR functions used in this work may help the reader.

Section 2:

- Could the authors please clarify why, on line 107, it is stated that autoencoders based on GNN do not work on the inductive setting? GNNs work on this setting off-the-shelf, so it is unclear to me why they should not generalise to new graphs at inference time. The authors reiterate this concept throughout the manuscript, including in Table 7 when R-GCN is defined as non-inductive, but it would be helpful to be on the same page about this.

Section 3:

- The mathematical formalisation is broken in more than one way, which makes the discussion confusing in many ways.
  = The use of the query symbol q is ambiguous. Is it on of the possible relations in R, or is it a triple (see table 6)?
  = The same is true for the definition og an edge: is it a tuple (u,v) or a triple (u,r,v)?
  = Similarly, w(e) != w(u,r,v) according to the definitions in the paper
  = Eqs 7 and 8: I believe the use of the expectation symbol in place of the mean is inappropriate. There are no formal distribution or random variables specified here. Please consider replacing the occurrences of the expectation with a uniformly weighted summation over the triples.
- Possible typo in Eq 4: should h_q^{(0)}  be should h_q^{(t-1)}?

- A suggestion: the abbreviation used before Eq 4 will confuse a lot of readers. The authors may consider expanding the notation despite its verbosity.

- What do the authors mean by "relatively low time complexity"? Is NBFNet truly scalable or not? It seems not, given the inference time comparison of Table C (which should have been included in the main article). Moreover, is it also scalable at training time? 17 hour for 20 epochs on PubMed seems a very slow training time.

- In general, it is not true that homogeneous graphs are undirected. Please rephrase.

Section 4:

- Why AllPath is not included in the empirical comparison? The authors stated it is the most similar solution compared to NBFNet, so we are expecting at least a comparison in the tables.
- Also, it would be nice to include a simple inductive baseline in Table 3 that applies a simple transformation to the node features before computing a link prediction score. On a personal note, I found out this strategy obtains very similar results to the ones reported by the authors.

- Table 5: did the authors fix the architecture, that is, 6 layers, based on the test results of Table 5? This would be a grave mistake (that would partially explain the consistent performance improvements over other methods). Please provide an honest answer.

- Could the authors please detail how Eq 9 generalizes logical rules to non-linear models? It seems quite a statement, but there is no enough evidence to support this.

Bibliography: 

Please consider better referencing the literature rather than citing directly most papers as arxiv preprints. As the authors know, other authors benefit from having their work indexed as part of a conference rather than as a preprint. Here, there are pretty obvious examples of arxiv-referenced papers that have already been published at important conferences.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers a link prediction framework called Neural Bellman-Ford Networks. The idea is to encode the relational structure between two nodes by using GNN message passing. The key here is to put the identity of the source node in the input feature. The provided framework demonstrates SoTA performance on the link prediction and KG completion datasets. 
main_review: This is an interesting work in link prediction, and the performance is impressive. However, my biggest concern is the limited novelty, especially compared to the ID-GNN [1], which is not cited in the paper. ID-GNN already introduces the idea of using the node identity information in GNN's message passing and the idea of reformulating the link prediction as a conditional node prediction problem. 

Hence, the main technical contributions of this paper are
(1) Show the theoretical connection to PPR, Katz index, etc (Table 1)
(2) Show more extensive experiments than ID-GNN.
(3) More ablation studies than ID-GNN.

I think the work still has some value. Especially, given that the experiments in ID-GNN are rather weak (mainly using synthetic graphs), this work serves as the empirical demonstration of the effectiveness of the ID-GNN framework in larger datasets.

One thing that would make this work more impactful from an empirical point of view is to try more established and standardized graph benchmarks such as the Open Graph Benchmark.  Both homogeneous and KG tasks are available, so it'd be great if authors can demonstrate the effectiveness there.

Overall, I enjoyed reading the paper, but it misses an important related work of [1]. I think this paper requires substantial reframing (not to over-claim the novelty, clarify the contribution given [1]) before being published at a conference.

[1] You et al. AAAI 2021 https://arxiv.org/abs/2101.10320

=============Post-rebuttal
The authors' response addressed my comments; Hence, I increased my score to 7. While I do believe careful reframing of the paper in light of the very relevant P-GNN is necessary, the big strength of the paper is in empirically demonstrating that a completely novel paradigm can outperform exiting KGE methods. Especially, it is impressive to see the methods can be even scaled up to the OGB-LSC graph.
limitations_and_societal_impact: Yes, may need to discuss more extensively on ID-GNN.
review_title: null

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