Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper focuses on the problem of inductive relational prediction for KG completion. Previous works often regard the rules as paths, different from those works, this paper regards the rules as circles. Based on that, the authors propose a GCN-based method for learning rules. They conduct experiments on the public datasets of inductive relation prediction and the proposed method achieves better or similar performance compared to best baselines. 
main_review: strengths: 
* The problem of learning rules for inductive relation prediction is important. 
* The authors provided another view, circle-based rules, about learning logical rules.
* The authors conduct experiments on benchmarks and the method achieves good performance.

weaknesses:
* It’s not clear what can be done by the proposed circle-based rules but cannot be done by previous chain-based rules. Actually, all circle-based rules can be regarded by chain-like rules, and by optimizing the scores of chain-like rules, one can learn high-quality rules. 
* Suppose we have learned a circle (A, B, C), if we want to rewrite it as a rule, which of the following should we use?
A, B->C; A, C->B; B, C->A. 
In my opinion, they are significantly different, but it seems that the proposed method cannot distinguish them based on the circle-based methods. 
* The training time and the testing time should be reported separately. 
* It would be better to use early-stopping rather than training with a fixed number of epochs for performance comparison. 
* “We hypothesize that the good cycles tend to be short, and the desired cycle bases should generally contain short cycles.”
Personally, I don’t think it is convincing to me, because some rules are long but interesting. Actually, according to previous literature[1,2,3], the rules with lengths of 1,2,3 are all important. The examples are as follows,
film_edited_by(B,A)←nominated_for(A,B);
 partially_contains(C,A)←contains(B,A) ∧ contains(B,C); 
Person(X) ← Car(Y1) ∧ Inside(X, Y1) ∧On(Y2, X) ∧ Clothing(Y2). 
* It would be better if the authors also compare their method with NLIL[3], which can learn more complex rules. 
* Minor issue (typo):
O(|E||V|).


[1] Yang, Fan, Zhilin Yang, and William W. Cohen. "Differentiable learning of logical rules for knowledge base reasoning." Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017.

[2] Sadeghian, Ali, et al. "DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs." Advances in Neural Information Processing Systems 32 (2019): 15347-15357.

[3] Yang, Yuan, and Le Song. "Learn to Explain Efficiently via Neural Logic Inductive Learning." International Conference on Learning Representations. 2019.


summary_of_the_review: The paper proposed a circle-based method for rule learning, which is an interesting view. However, some claims (e.g., shorter rules are better) are not convincing, and the motivation of such a design is not clear. There is no substantial difference between the rule learned by this method and the previous works, and the search space of rules is even smaller (e.g., compared to NLIL[3]). I recommend the authors clarify these issues.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a GNN framework to solve the inductive relation prediction problem, namely CBGNN. The framework consists of three modules: 1)  a cycle extraction module that generates cycles graphs with clustering and SPT tree search; 2) a bi-directional LSTM that converts a cycle of triplets into a feature vector, and 3) a GNN model that learns the triplet confidence using the feature vectors. In experiments, the proposed method is evaluated with a set of differentiable ILP methods and GNN methods. Some ablation studies are conducted to validate the cycle extraction module and feature generation module.

main_review: Overall the paper is well-written and easy to follow. I find the idea of viewing relational paths as graph cycles to be interesting. However, despite the authors claiming that cycle representation is distinct from the path representation in multi-hop reasoning methods such as NeuralLP, it's worth noting that the path representation is guaranteed to be a cycle in these works (as a chain rule). Therefore, the search space of the two representations is in fact the same. I would suggest the author carefully address the claims and comparisons with the multi-hop reasoning methods in sections 1 and 2.


Some of the concepts and design choices need more elaborations and justifications:
 - The proposed method generates nodes with the spectral clustering algorithm. It's unclear why this particular algorithm is picked and how sensitive is the framework to the choice of clustering algorithms.
 - The authors generate cycles with SPT. However, other than claiming it follows Occam’s razor principle, there is no theoretical analysis or direct empirical experiment that shows the space always contains the answer cycle to the query.
 - The authors claim the cycle incidence matrix implicitly encodes interaction between the cycles. However, it's unclear why such interaction information is needed for answering the query. To justify this, the author should compare the method with a simpler baseline without the incidence matrix.

Cycle extraction only considers the KG's topological structure, treating the KG as an undirected graph with no edge label. I'm concerned about this approach, as the direction and the type of edge are critical to the KG. In fact, in the feature generation phase, the edge direction and type are indeed taken into consideration. It's unclear to me why not use this information at the very beginning.

Besides the aforementioned issues, my main concern with this work is that the proposed framework is unnecessarily complicated.
 - It generates cycles with clustering and SPT -> computes cycle incidence matrix -> generates cycle features with bi-LSTM -> builds GNN for each cycle basis -> computes cycle confidence with GNN -> aggregate final scores with weighted sum.
 - The current ablation study is far from sufficient to justify why this framework has to be this complicated.
 - For example, one can build a frequency-based baseline with cycles generated from SPT and compare it with the proposed method.
 - For the cycle incidence matrix, one can build a baseline without the matrix.
 - To predict the edges, one can also build a simpler classifier right on top of the bi-LSTM model. It's critical to show that the additional GNN structure is indeed necessary.

I'm also concerned about the method scalability. The computational costs of the proposed method grow quickly w.r.t |V|, |E| and beta. However, the largest dataset FB15K v5 only contains 5K nodes and 33K edges which is significantly smaller than the original FB15K dataset which contains 14K nodes and 272K edges. 
 - It's unclear to me what does the run time shown in Table 3 correspond to. Does the time correspond to the end-to-end processing time of CBGNN? Or it is the inference time of the GNN module alone?

The analysis on the influence of k is weak. The experiment is only conducted on the smallest subset of FB15K and WN18. Instead, the authors should analyze the necessary k values against a set of KGs of increasing sizes and show how well does the k scales w.r.t |V|, |E| and beta.
summary_of_the_review: In summary, although the idea of using cycle representation is interesting. The proposed method is unnecessarily complicated. And the current draft lacks too many justifications to the components in the proposed method. At this point, I would recommend rejection but I'm happy to raise my score if the authors address the aforementioned concerns.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The paper proposes an approach to predict the confidence of missing edges in a knowledge graph in the purely inductive setting, in which the test knowledge graph does not share any entities with the training graph. The key idea is to use cycles (or more specifically, cycle bases) as the basis for such reasoning; the paper builds and evaluates a model around this idea.

main_review: The approach put forward in this paper is not convincing since it's convoluted (W1), neither well-argued for and nor convincing (W2), partly unclear (W3), there is no analysis or theoretical insight (W4), and practical benefits and costs ultimately remain unclear (W5).

W1 (convoluted). In a nutshell, (1) run spectral clustering to obtain central nodes, (2) compute shortest-path trees from these nodes, (3) construct a "cycle basis" from each tree, (4) run a BILSTM to encode each cycle in the basis, (5) construct a cycle graph from each cycle basis, (6) run a GNN to predict cycle confidences, (7) repeat (1)-(6) k times and average, (8) predict the cycle confidence of the highest-weighted cycle that contains a triple as the triple confidence, (9) train this using negative sampling.

W2 (neither well-argued for and nor convincing). Many of the steps taken in this approach are heuristic and justified in a rather hand-wavy away; even key points (such as "what is a good cycle" and "why a complete cycle basis") are not precisely described. There is not clear, convincing argument for the approach. In fact, the ultimate approach suggests that if there is a single triple on a cycle that obtains a high-confidence prediction, so do all other triples on the cycle. This point alone makes the entire approach questionable: "son(x,y) and son(y,z) -> related(x, z)" (always true) should have a different confidence than "related(x,z) and son(y, z) -> son(x,y)" (clearly not always true). Another point is that it is known that useful rules may not necessarily be paths; e.g., they may require constants (e.g., "child(x,y) and gender(x,'male')->son(x,y)").

W3 (partly unclear). The paper talks largely about how cycle bases are constructed for a given KG, i.e., for the positive edges. But what happens with the negative edges? They clearly do not appear in any cycle of the cycle base. So how is prediction actually performed +++? For the test set, is leakage of information from the test triples prevented? (+++ needs to be performed for each test triple separately, hiding all other test triples---else information is leaked.)

W4 (no analysis or theoretical insight). Expressivity or properties of the proposed method are neither discussed nor rigidly analyzed.

W5 (practical benefits and costs unclear). First, the method does not fully enclose its cost. What is the time/space requirement for each of the steps 1-9 above? It seems like the method is very costly and does not scale to large graphs. It's unclear why there would be any performance benefit compared to just using a GNN (since it's a part of the proposed method and the graph is larger). Second, it's completely unclear why the proposed method shows strong empirical results; there is no discussion or analysis in the paper. Except there is test leakage (e.g., by constructing a single graph with all test triples; see also +++ in W3), in which case the proposed method is obviously faster and likely to be much better empirically. Apart from the points above, the usefulness of the setting used in the study is mysterious to me (it's taken from prior work): clearly, in the context of the knowledge graphs considered in the experimental, there is entity overlap between train and test (e.g., the higher-level wordnet synsets or the types and locations for Freebase). So why perform reasoning without? The resulting graphs are likely to be quite unnatural/unrealistic.

summary_of_the_review: The approach put forward in this paper is not convincing since it's convoluted (W1), neither well-argued for and nor convincing (W2), partly unclear (W3), there is no analysis or theoretical insight (W4), and practical benefits and costs ultimately remain unclear (W5).
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper addresses the problem of inductive relation prediction in knowledge graphs. The authors propose a novel GNN-based method. Treating rule learning as a cycle learning problem is very interesting. The experiments on popular knowledge graph completion datasets verify the effectiveness of the proposed method. 
main_review: strengths:
- The paper is well-written and easy to follow.
- Treating rule learning as a cycle learning problem is very interesting and novel. 
- The proposed method is shown to be effective and efficient. In terms of experimetns, the paper includes detailed experimental setup, a comprehensive set of baselines and ablation studies.

weaknesses: 
- I can't understand why there is difference between Table 1/2 and Table 6/7. Is this due to random seed? Some of the entries have really big differences. For example, (NELL-995 v1, CoMPILE) in Table 7 and Table 2 are 62.00 and 58.38 respectively. Do we need some statistical testing here or reporting the variance among different runs?
- The paper argues that the proposed method might work better on datasets with complex semantics, i.e. with more complicated relations. Given this, I would suggest running experiments on datasets like https://allenai.org/data/tuple-kb, which contains more than 1000 relations. 

summary_of_the_review: The paper proposes to treat rule learning as cycle learning in knowledge graphs. The approach is very interesting and novel with solid experiments showing its effectiveness. I would suggest accepting this paper.
review_title: null

Meta-review: The paper proposes a new approach to inductive rule prediction for knowledge graph completion. Reviewers highlighted as strengths that the paper proposes an interesting approach to an important problem that is relevant for the ICLR community. However, reviewers raised also concerns regarding model design and correctness as well as clarity of presentation (e.g., motivation, analysis, comparison to related work, evaluation). After author response and discussion, all reviewers and the AC agree that the paper is not yet ready for publication at ICLR due to the aforementioned issues.
Decision: Reject