Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposed a KBQA framework that scales linearly with the number of relation types in a knowledge graph. The framework contains three main components in general. They first adopt relational coalescing to combine the nodes which share the same relation to reduce the number of edges in a graph. Then, they utilized a relation-level model to extract a subgraph that contains a set of answer candidates. Finally, the answer candidates are refined by an edge-level model. Their experiments on knowledge-based question answering show that the proposed framework achieves a new state-of-the-art on the challenging WebQuestionsSP, and is orders of magnitude more scalable than competitive approaches.
main_review: Personally, I liked the idea of doing KBQA in a coarse-to-fine way. The proposed relational coalescing is simple and intuitive, yet very effective. The experimental results on the common datasets are quite strong and also show that the proposed method generalizes compositionally. These are all good merits that could spur further researches of KBQA in this coarse-to-fine fashion. Also, the paper is well-presented and I enjoyed the reading. 

Here are several questions I have:
1. What is the average length of the relational chains for WebQSP?
2. Could the proposed framework generalize to the question that contains several entities?
3. Are there some typical cases where the relational-level model fails to retrieve the correct chain?
limitations_and_societal_impact: The authors sufficiently addressed the limitations of their work and I don't think there are potential negative societal impacts.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper focuses on the task of knowledge graph question answering. It specifically aims to address the challenge of scalability issue of the current KGQA methods. The overall idea is to first obtain a question-specific coalesced subgraph out of the knowledge graph, which “merges” entities of the same type (connected by the same relation types). Then the method locates a subset of answer candidates on the subgraph by traversing on this coalesced subgraph with some relation sequences derived from the mentioned entities in the question. Then they run a GNN model to select the final answer to the question from the answer candidates.

Generally I feel the paper writing can be refactored and improved. I suggest the authors list all the model components at the beginning of Section 2. Currently they only introduce a relation-level model and the edge-level model in Section 2, then out of nowhere, they mention they further propose an autoencoder in Section 3. They also say that “the architecture of the model includes three main components: a question encoder, a relation encoder, and a graph-guided decoder” in line 163. Where is relation-level model and edge-level model?

One key assumption (or limitation) in the paper is that the graph is complete, which renders the proposed method weaker than the baselines, e.g., all Pullnet, embedkgqa, EmQL can deal with missing edges. Although the authors mention in line 147-154 that “it may still be able to retrieve alternative sequences of relations, provided that the training data are representative enough”, can you run experiments on incomplete MovieGraph for MetaQA? I assume the training questions in MetaQA are much more than that in WebQSP and should also be very “representative” since the questions in the dataset are generated using some templates.

Another general comment is that since the paper focuses on QA in the complete graph setting and aims to obtain a relation sequence as the “parsed representation” of the question. Can you also compare your method with the series of (unsupervised) semantic parsing methods? These methods aim to parse the input questions to some logic form and then execute the logical queries on KG for answers.


main_review: 1. I am confused by line 28-31, what exactly do you mean by “each forward pass scales at least linearly with the number of facts in the KG”? What is a forward pass? If you mean obtaining the subgraph for the question, I think in Pullnet obtaining the subgraph is not running a classifier on all the facts (edges) on the KG, but rather an iterative process, where at each step the classifier only needs to classify a small set of edges that are connected to the current retrieved subgraph. This is not linear to the number of facts on the KG and actually it is much less.
2. It seems that the paper misses one important section, which is the detailed architecture of the edge-level model.
3. Do you assume $\mathcal{V}_Q$ are given? The authors should make it clear what is given and what is not.
4. In line 83-93, the authors talk about how to obtain the coalesced graph. The term “Reachability” is conditioned on a sequence of relations as defined in the Reachability paragraph. However, in line 87, the authors only say “The nodes of $\tilde{\mathcal{G}_Q}$ are a set of nodes of $\mathcal{G}$ that are reachable from $\mathcal{V}_Q$” Then what is the relation sequence here? Do different questions have different relation sequences? How do you obtain the relation sequences? Significant amount of details are missing here and I could not find that in Appendix A. 
5. The notation is confusing for the equation after line 97. As in the definition, $\phi: \tilde{\mathcal{E}_Q} \to [0,1]$ really maps an edge in $\tilde{\mathcal{G}_Q}$ to a value between 0 and 1, but in the equation after line 97, for the argument of the function $\phi$, I do not think $reach_\mathcal{G}(\mathcal{V}_Q,R_{1\to i-1})$ represents a node on the KG but rather it represents **a set of nodes** on the KG as in the definition above line 83. Can you clarify the equation?
6. Also, how long is the $R_i*$? Do you allow different lengths for $R_i*, i=1,\dots,k$?
7. I am also confused by the motivation of the knowledge seeking process. It seems that $\tilde{\mathcal{A}_Q}$ is obtained using $R_i*$, which is obtained by maximum likelihood $p(R_i*|\tilde{\mathcal{G}_Q},\mathcal{V}_Q)$. This is saying that the answer candidates in the coalesced subgraph are only conditioned on the original KG and the question entities, but not conditioned on the original question. This is rather counterintuitive since there exist many questions with drastically different answers but with the same starting entities.
8. Besides, how would you train the network $\phi$?
9. What is $\mathcal{G}(\tilde{\mathcal{A}_Q})$ and $\mathcal{V}(\tilde{\mathcal{A}_Q})$ in line 106-107? $\mathcal{G}$ and $\mathcal{V}$ are not functions.

minor:
1. I would suggest using different notations for natural language question and logical query. Currently both are denoted as Q in different fonts. 
2. line 159: “We found useful” -> “We found it useful”

limitations_and_societal_impact: Please check the section above, I do not think it has potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an end-to-end KBQA system that can be directly used on the whole knowledge bases. This is in contrast to existing approaches that need a heuristic subgraph construction stage. More specifically, the proposed method trains a relation-following model to collect a candidate set of entities and the corresponding subgraph, which can then be processed by existing graph models. Empirically, the proposed method achieves state-of-the-art performance on MetaQA and WebQuestionsSP. Overall, this paper presents string empirical results over existing baselines on multi-hop KBQA, however, the main idea is hardly novel and has been applied to similar tasks. 
main_review: 
**Originality**: The core idea of the model is not new. The idea of sequentially selecting relation links to extend the reasoning chains has been extensively explored by KB reasoning work (DeepPath) and also semantic parsing methods on Freebase (such as stagg https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/ACL15-STAGG.pdf). The proposed method uses this process as an initial stage to replace pipelines like personalized page rank. 

**Quality**: The presentation is clear and the experiments are well designed. It not only shows state-of-the-art performance but also better compositional generalization. 

**Clarity**:  The writing is clear and easy to follow. 

**Significance**: While similar ideas have been applied to related tasks, this work shows benefits on multi-hop KBQA tasks.



limitations_and_societal_impact: I don't see any negative social impact of this work.
review_title: null

Meta-review: This work proposes a substantially more scalable approach to KBQA that scales with the number of relation types (rather than the number of edges) in a KG, and operates in a coarse-to-fine manner.  The overall idea of working first at relation types, and later refining to individual edges, is interesting, and the results in the setting considered are strong.

The detailed discussion during the reviewing + author response period clarified some aspects (e.g., that the main contribution is not traversing a KG for multi-hop reasoning but identifying in a coarse-to-fine and scalable way to identify subgraphs that contain the answer), and also included additional positive results such as improved performance even on incomplete KGs, which is what the PullNet and GraftNet baselines were originally designed for.

The paper is close to the fence, with several strengths and some weaknesses:

**Strengths**: Strong empirical performance, intuitive overall idea, and authors' active effort in addressing (and, I assume, incorporating in the revised draft) detailed feedback from the reviewers.

**Weaknesses**: Limited novelty (as many pieces of the overall idea exist), room for clarity of presentation of both technical details (some of which are in the appendix) and broad statements like existing methods scaling linearly in the size of the entire KG (whereas they scale linearly in the size of the *retrieved* subgraph, which is often much smaller for 2-4 hop questions).
Decision: Accept (Poster)