Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a Logical Message Passing Neural Network (LMPNN), which relies on pre-trained knowledge graph embeddings and MLP-based local one-hop inference to perform the Complex Query Answering (i.e., EFO-1) task. Compared to the prior work CQD [1], which formalizes the KG reasoning as an optimization problem, this paper proposes to use the closed-form solution of ComplEX to approximate the single-hop inference and use an MLP-based multi-layer GNN to perform the multi-hop reasoning.

[1]: Arakelyan, Erik, Daniel Daza, Pasquale Minervini, and Michael Cochez. "Complex Query Answering with Neural Link Predictors." In International Conference on Learning Representations. 2020.
strength_and_weaknesses: Strength:

1. LMPNN is quite parameter-efficient, where only MLP and the embeddings of existential variable and free variable are learned.

2. Due to the novel design of closed-form approximation of single-hop ComplEx, LMPNN is inference-efficient (in a GNN manner) compared to optimization-based methods like CQD [1].

3. LMPNN achieves competitive or better performance on FB15k, FB15k-237, and NELL datasets.

4. Compared to previous work CQD, LMPNN can additionally model the negation operation.


Weaknesses:

1. My main concern is on the comparison with the optimization-based method (i.e., CQD). The author claims that "Moreover, it is unclear whether CQD can be applied to complex queries with negation operators". Could I interpret it as the CQD is evaluated without the negation operations for INP, PIN, PNI, etc settings? Would it be possible to just use Eq. 7&8 in the paper to get an optimization-based baseline? Since one of the contributions in the paper is a GNN-like inference, I believe a fair comparison with optimization-based methods is necessary.

2. The method is motivated by how to better perform one-hop queries, however, the experimental results show that LMPNN is usually outperformed by CQD in the 1P setting. Since in 1P, the one-hop ComplEx closed-form approximation should lead to the same solution as CQD, could the author explain the reasons?

3. I feel the claim of bridging the gap between EFO-1 query answering and "the long-standing achievements of KGR" is a little over-claimed, given that previous work like CQD already uses the exactly same pre-trained KGE model (ComplEx).

Typos:

Page 5, " In Figure 1, the central node x receives messages from all neighbor nodes, suo." what does "suo" mean?
clarity,_quality,_novelty_and_reproducibility: The paper is written clearly and technically sound. The proposed method (w.r.t one-hot inference-based GNN) is novel.
summary_of_the_review: The proposed LMPNN is 1) parameter-efficient, 2) inference-efficient (compared to optimization-based methods like CQD), and 3) achieves competitive or better performance on three EFO-1 datasets. My main concern is about the fair comparison with optimization-based methods with negations. Therefore, I can only recommend a weak accept for the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose to represent first-order logical queries as query graphs and then design a novel message passing-based framework LMPNN on the graphs to answer given queries. This is a successful attempt to combine the power of pretrained knowledge graph embeddings and message passing to perform logical reasoning. The proposed LMPNN is quite simple (a virtue) but experiments demonstrate its superior performance.
strength_and_weaknesses: ## Strength 
1. This paper manages to answer complex EFO-1 queries by exploiting the potential of pretrained knowledge graph embeddings, showing that pretrained embeddings also contain abundant semantic information for logical negation.    
2. The proposed LMPNN is simple but effective, attaining new SOTA results on benchmark datasets.    
3. The authors conduct extensive ablation studies to evaluate the influence of different hyper-parameters.    
4. This paper is clearly written and easy to follow.

## Weakness
1. The proposed framework is dependent on the underlying knowledge graph embeddings. The authors may want to provide more results using other KGE models (e.g., DistMult, TransE, RotatE, etc).   
2. To perform efficient logical message passing, it seems that a closed-form message encoding function is necessary. If the underlying KGE is TransE or ConvE, then how to implement PMPNN?    
3. The authors define a class of more expressive logical queries in Definition 1 and show that it can represent more queries compared with operator trees. However, there is no such kind of query in the current benchmark datasets.

clarity,_quality,_novelty_and_reproducibility: ## Clarity
This paper is clearly written and well organized

## Quality
This paper is technically sound. The main claims are well supported by theoretical analyses or experiments, and the experimental results are convincing.


## Novelty
The overall framework seems novel and interesting to me. The idea of exploiting the power KGE to perform logical reasoning is inspired by CQD (ICLR21), while the authors further incorporate message passing to the framework and succeed to model logical negation. 

## Reproducibility
The authors provide detailed experimental settings and the range of grid search, so the reproducibility looks nice.
summary_of_the_review: This paper proposes a novel and interesting model for logical reasoning. The proposed model is simple and shows strong performance on standard benchmarks. The submission will be more solid if analyses and experiments for more KGE models can be provided.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper focuses on query answering over knowledge graphs. The idea is to use standard link prediction knowledge graph embeddings to model each triplet or atomic formula, create a message and spread it out to do a message passing over the query graph. Experiments on standard benchmark shows the proposed method achieves better or comparable results than prior state-of-the-art methods.
strength_and_weaknesses: The paper proposes a simple and effective method for query answering over knowledge graphs. It seems a combination of the ideas of CQD and MPQE. The authors perform extensive experiments and ablation studies to evaluate the proposed method. However, they did not seem to include the results of other recent baselines. Please find some more questions below.
- It misses some words in the first paragraph on page 4. “is able to produce a continuous truth value…”
- What does “suo” mean at the end of Sec 4.1?
- In Eq.5, what is the search domain for the embedding? 
- How is the logical message passing neural network different from a regular message passing NN? The update function is almost exactly the same.
- The paper does not say how to handle the union operator. But I assume the way is to do a form of aggregation at the end. I suggest the authors add one paragraph about this.
- The paper mentioned one form of query that cannot be handled by the other methods? Does the proposed method handle such queries? How would you handle an atomic formula $\neg(a_1=a_2)$?
- How does the model perform on larger benchmarks in [1]?
- The baselines are not fully considered, there are GNNQE, kgTransformer and some other recently proposed query reasoning methods that are not compared in the main result.

[1] SMORE: Knowledge Graph Completion and Multi-hop Reasoning in Massive Knowledge Graphs
clarity,_quality,_novelty_and_reproducibility: Clarity: The method is clearly written and easy to follow. But, I do find the authors did not include a discussion on how they handle the union operation using their message passing architecture. Also there are some weird indents at the start of many paragraphs, which look like uncleaned comments.

Quality & Novelty: I think the paper produces a nice combination of CQD and MPQE. The experiment seems lacking, the authors did not compare the proposed method with all recent baselines.

Reproducibility: the results seem reproducible with all the details in section 7.1.

summary_of_the_review: Please find the details above.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary: The paper addresses the problem of answering complex queries (EFO-1 - Existentially quantified First Order queries and has a single free variable) over a knowledge graph. The proposed approaches, LMPNN, uses standard link prediction embeddings to model atomic formulae and does message passing over the query graph. Experiments on standard benchmark datasets showed that LMPNN either performed better or comparably to SoTA methods.

Strengths: All reviewers acknowledged that the paper is well-written and easy to follow. The proposed approach is novel, simple and yet effective in practice. While reviewers raised several minor concerns and clarification questions in their initial comments, I believe that the authors have done a good job addressing them, both in the rebuttal and in the updated version of the paper (with extended and detailed appendix sections).

Weaknesses: The problem addressed in this paper, while very interesting, might be interesting to a small community. While the method shows solid results on standard benchmark datasets, its effectiveness in real-world applications remains to be seen.
justification_for_why_not_higher_score: I believe the reviewers could've increased the scores slightly after reviewing the authors' updated version.
justification_for_why_not_lower_score: The paper is solid and the approach is novel.
Decision: Accept: poster