Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: The paper proposed a graph-based reasoning task in an inductive setting. Different from previously studied transductive reasoning task, a reasoning task contains unseen entities at inference time. Previous QE methods are unable to handle unseen entities.
strengths_and_weaknesses: The paper discussed two methods to handle unseen entities at inference time, NodePiece-QE and NBFNet-QE. In NodePiece-QE, the model computes embeddings for unseen entities from the relations of their neighbors. In NBFNet-QE, the model does not explicitly compute entity embeddings, but instead matching the graph structures locally. Both methods are plausible in solving the problem of novel entities. Experiment results show that the proposed methods achieve reasonable results. 

However, I am a bit concern about the soundness of experiments. The authors experimented their models on a modified datasets to test models' ability in handle novel entities. They did not compare the performance of their model to any other external baselines, so it's not clear how well the proposed models perform. The reported metric, i.e. Hits@10, is highly dependent on the incoming / outgoing degree of the "anchor" nodes. Please consider carefully compare your models with other external baselines.
questions: 1. For both methods, do you make the assumption that "anchor" entities are seen at training time?

2. Could you please provide more information about the CQD-Beam method for decoding? How are the entity embeddings used in CQD-Beam? CQD-Beam is not a widely known methods so it may be confusing to readers.

3. In the NBFNet-QE method, the authors made an assumption that all edges (KB triples) that are required for prediction are present in the graph. How will your model be affected by an incomplete KB?

limitations: The authors claim the most important limitation of this work is the tradeoff between performance and computation complexity. While this is true, the authors should consider discussing more general limitations of this work, e.g. to what extent will this model work with unseen relations, sparse graphs with very few edges for nodes, types of supported reasoning operations, etc. More importantly, please compare your model with external baselines to justify your experiment results.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work proposes the task of Inductive Logical Query Answering which is the natural next step after past work on:
* KG Completion: Predicting new triples in a knowledge graph (KG) with a fixed set of entities
* Inductive KG Completion: Predicting triples for new entities (and some of their triples) added to an existing KG
* Logical Query Answering: Executing First-Order Logic (FOL) queries on a KG where we assume that the KG is incomplete and the set of answers contains more entities than those that can be predicted from just FOL query execution

Inductive Logical Query Answering is then executing FOL queries in a KG where new entities are added at inference time. The inductive settings are motivated by real-world scenarios where KGs are constantly being updated with new information and new entities.

The authors then propose two approaches (each with its own strengths and weaknesses) to solve the task.
strengths_and_weaknesses: Strengths

[+] Inductive query answering is well-motivated as an extension of past work. This work is also well-placed with respect to related work.

[+] The paper is well-presented and descriptions are mostly sufficient to understand the work.

[+] The baseline approaches described are suitable for the task and have complementary strengths and weaknesses.

Weaknesses

[-] There should be more discussion on evaluating FOL execution systems in the inductive setting and what the right metric for the task is. 

Reporting accuracy of the systems on train queries at inference is an important first step toward establishing "faithfulness". Can we trust a system that does not achieve 100% accuracy on "easy" answers?

Similarly, just reporting Hits@10 (after filtering out "Easy" answers) hides under the rug what it means to predict a "hard" answer at a higher rank than an "easy" answer (before filtering). Personally, I am of the opinion that the evaluation metric should penalize any entity being predicted as an answer before all the "easy" answers are enumerated. This ensures trust in the system to first execute the FOL query when possible and only then resort to "guessing" more answers by filling in missing edges.
questions: * Line 208: Can you flesh out how the mechanism of NBFNet is a *labeling trick*?
* This is somewhat implied from the text. Are the validation and test queries guaranteed to require missing edges to find the full answer set? Does the query sampling ensure this?
* How do you explain the initial increase in performance as the graph grows (e.g. in Fig 3)?
* Line 347: Performance in Table 2 on the large 2M node graph shows the accuracy of <10%. Why is this considered non-trivial? Is trivial just considered random guessing performance? There should be better baseline estimates that can scale to this graph size with graph neighborhood sampling.
* Following up on the discussion of better evaluation metrics, how many times does the system predict a "hard" answer higher than an "easy" answer? Is this a strict constraint that should be applied when evaluating systems on these tasks?
limitations: The weakness section highlights a missing discussion on the evaluation of systems in the inductive setting. This is a limitation of the query answering task in general and not just of this work. However, given that this work adds an additional component of inductive KG growth, this discussion seems relevant and necessary for completeness.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work studies the inductive query answering task where inference is performed on a graph containing new entities with queries over both seen and unseen entities. Which is a sound contribution to the field of query answering and knowledge graph completion.

The authors argue that several existing studies on complex query answering with logical operators have been conducted in transductive mode where the set of entities does not change at inference time.

The aim of this study is to extend the complex logical query answering to inductive representation learning algorithms. Focusing on the inductive setup where an inference graph is a superset of a training graph such that:
- Inference queries require reasoning over both seen and new entities; 
- Original training queries might have more correct answers at inference time with  the addition of new entities.

In this work;
- They show that inductive models are able to perform logical reasoning at inference time over unseen nodes generalizing to graphs up to 500% larger than training ones. 
- They also explore the efficiency-effectiveness trade-off, and the findings indicate that the inductive relational structure method generally achieves higher performance.
- Also the inductive node representation method is able to answer complex queries in the inference regime only without any training on queries and scale to graphs of millions of nodes.

strengths_and_weaknesses: - The paper extends the idea of inductive representation learning algorithms to logical query answering where inference queries require reasoning over both seen and new entities which is a sound contribution to the field of query answering and knowledge graph completion. 
- The authors also cite/explain the related works in both knowledge graph completion and complex query answering. The paper also makes a good differentiation between the proposed approach and the existing work.

- The paper is well written, with elaborative figures and experimental results support the proposed method.

questions: N/A
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors studied the problem of logical query answering over knowledge graphs under an inductive setting. Existing methods usually focus on the transductive setting where all nodes and edges are seen during the training stage. This work goes beyond and investigates the scenario where there are unseen nodes in the validation and testing stages. To tackle this problem, they proposed two methods and demonstrated their effectiveness via extensive experiments.
strengths_and_weaknesses: ### Strength
- The studied problem is novel and interesting. The inductive setting is novel and more generalized.
- They set up new benchmarks for the inductive logical query task by constructing two new datasets, one using FB15K-237 and a large one using OBG WikiKG.
- The proposed NBFNet-QE performs well on the new FB15K-237 dataset (The numbers are relatively higher compared to the transductive setting) and outperforms NodePiece-QE by a large margin. This finding is interesting and may provide directions for future improvement.
- The presentation is clear and easy to follow.

### Weakness
- The contribution to the model design is rather incremental. Both models (NodePiece and NBFNET) are based on existing works on link prediction (a simpler yet closely related task). The query answering part is also based on existing transductive logical query answering models  (e.g., CQD) on KG. 
- The proposed framework is only applicable to unseen nodes as the node representation learning process heavily depends on the edges (relations). It cannot deal with unseen relations.
- The discussion on the efficiency-effectiveness trade-off between NodePiece-QEand NBFNet-QE is a bit trivial. Solutions/insights that can address this trade-off are expected.

questions: - Since the node representation is learned using the edge structural patterns. I am wondering if the model will output the same representations for different nodes (which I think is not ideal). 
- Is there any way to marry the benefits of both models?

limitations: Although the NBFNet-QE can achieve good performance, it is not scalable, and no results are reported for the WikiKG dataset. However, the more efficient NodePiece-QE performs rather worse. This limitation makes me doubt the usability of the proposed two approaches.
review_title: null

Meta-review: metareview: It is very hard to make a final decision on this paper; the scores are: 4,6,8, and 5. The research problem raised in this paper is interesting and worth further study. 
However, reviewers have raised some concerns about the experimental resuls. In the original paper, they did not compare with any external baselines. In the discussion period, the authors presented additional results with BetaE, which were originally designed for transductive reasoning. Not surprisingly, BetaE delivers poor results. How strong is this comparison? One would expect some experiments with better initialization for unseen entities, e.g. with KB embeddings (e.g. TransE and ConvE used in KBC tasks).
confidence: Less certain
Decision: Accept