Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: I liked the idea of GraphLog; it seems like an interesting and potentially very useful dataset. The "results" seemed little to do with the dataset (apart from being enabled by the dataset), but were comparing some models that were neither the current state-of-the-art or particularly novel. I could imagine a paper that does a comprehensive reevaluation the state-of-the-art algorithms (unchanged!) using the new data set and then reports on which ones work well for different tasks. Such reproducibility in science is important. However, this is not was done.

I would like to see more discussion about why doing well on the benchmark would translate into doing well on real-world problems. I would hypothesize that the real-world does not consist of a few simple rules chained together, but the underlying dynamics is much more complicated, and agents are trying to concoct a story to get some signal out of the noise. All of your tests assume there is a clean signal -- constructed by your rules (perhaps corrupted by random noise(?)).  You just assume that this will form a good testbed, but it isn't obvious to me.

The rules all seem overly simplistic. I was expecting your rule generator to generate more complex rules from simpler ones. But it doesn't; they all seem to be just the same complexity.  Here are some things I'm wondering:   By sharing subset of rules, the worlds are structurally similar? Are the entities shared in any meaningful way? I think they are just meaningless names, and so there is no commonalities between the worlds. I think they share relations. Is there any notion that a relation learned in one world are like the relation with the same name in other worlds? You are not learning about relations using diverse populations, or are you?

Minor comments

In RGCN, $\times_i$ what is $i$?

Figure 3, I thought was weird. If we divide the datasets into easy medium and hard, don't we always have a nice straight lines when plotted with difficulty? I think it is just trying to say that the E-GAT models work better across difficulties.

In figure 5, I can't see how/why "The colors of the bars depict how similar two distributions are"



After rebuttal:


Comment:
I am suspicious of your argument on "complex due to multiple resolution pathways".

Surely there is always a (unique) canonical deviation. For example, one could imagine extending Prolog to allow for any literal to be resolved; not just the left one. However that just adds extra complexity. Because we have to resolve all literals, we might as well do in a left-to-right order. Surely in your case, we can always do the leftmost (for example) one. Or the rules can be defined so that we can resolve them left to right.

One counter to my argument might be (parent, ancestor) -> ancestor parent -> ancestor.

Here we cannot go left-to-right, but need to go right to left. We do not need to search over orderings.

This issue is faced daily by Prolog programmers; we choose whichever one of (using your notation): (parent, ancestor) -> ancestor (ancestor, parent) -> ancestor works with your engine. I don't see why they get around it without problem and you claim it is not possible. The rules may depend on the order used, but what is the problem with that if it drastically reduces the search space? You don't have to search for all proofs; just one.

review_title: An interesting dataset but efficacy not demonstrated

final_score: rating: 6: Marginally above acceptance threshold
review_content: This work proposes a method for generating synthetic datasets for testing path-based (knowledge) graph completion. Until recently, there were not many good benchmarks for evaluating reasoning with learned rules or learned knowledge, but there has been a fair amount of work on developing benchmarks for this lately. The synthetic datasets generated here are distinguished by the ability to produce datasets that share a controllable amount of rules. This permits the benchmarks to be used to evaluate multitask learning, robustness to distribution shift, etc. As an illustration of this, the paper includes experiments with a variety of baseline methods showing how (a) the generalization ability of various methods grows and then declines as the number of tasks is increased and (b) fine-tuning on diverse tasks improves accuracy. They also show that in a continual learning setting, the baseline methods all exhibit catastrophic forgetting.

There is value in being able to control the "relatedness" of these synthetic tasks in a principled way (the experiments are a good illustration of how this may be used), so I am leaning towards acceptance. My hesitation is that it's a bit on the incremental side, and seems oversold in a few places, as follows:

The work suggests that the proposed benchmarks examine the "compositional generalization" abilities of models, but it is not clear to me how this is so. The relations are drawn from a fixed set of types. It's true that the rules may examine new combinations of relations, but the end result is just that one of the existing relations is inferred to hold between the start and end of the path. The fact that those rules hold for all bindings is a kind of generalization, but I would not call it "compositional." Compositional generalization would mean something more like learning how to map a grammatical structure to the logical form correctly, irrespective of what was in the constituent phrases.

Also, the work says "GraphLog is the only dataset specifically designed to test logical generalization capabilities on graph data." That seems a little bit of a stretch. CLUTTR seems to feature a very similar set of synthetic benchmarks, the only difference is that CLUTTR *additionally* produces some text, but the abstract focus of the task was an essentially similar knowledge graph completion task. Placing this work side-by-side with CLUTTR, the difference is really (just) in being able to tune the degree of shared structure between multiple datasets. That's valuable, I agree. But this one difference is only discussed by a table featuring four X's for each of the variants of the task setup that this feature enables. The lack of a proper discussion of related work obscures the actual extent of the contribution.
review_title: A refinement of synthetic knowledge graph benchmarks

final_score: rating: 4: Ok but not good enough - rejection
review_content: The authors propose a synthetic graph generator to evaluate graph neural networks. The generation process starts with defining rules, subset of rules are used to define a world, each world is then used to sample a graph. Test queries are generated by picking a pair of vertices u, v and generating a path connecting them via the rules. There are some biases in the generation process. For instance, the rules are exclusively open path or chain rules. And as noted above, the test queries mostly stick to a path (the authors allow some variations by adding nodes to vertices already on the path but the path seems to form the backbone of the test query). The remainder of the paper takes a few well known graph neural networks and evaluates them on data generated using GraphLog. Based on these results, the authors claim that E-GAT outperforms RGCNs.

This reviewer acknowledges the need for a benchmark for knowledge base completion. However, GraphLog seems to have one too many biases baked into it for it to form a definitive benchmark. The first bias is the adherence to open path or chain rules. I don't understand the need for this. I can think of two different property nodes p1, p2 hanging off a vertex u leading to an edge with another vertex v. Can this be captured by a chain rule? In section 3, the paper states "Path-based Horn clauses of this form ... encompass the types of logical rules learned by state-of-the-art rule induction systems" and then goes on to cite \partial ILP and NeuralLP. \partial ILP captures more than just chain rules, it tries to capture recursive logic programs, and NeuralLP is based on TensorLog which is much more general than this. If you are going to cite related work then might as well cite it properly. Another bias baked into GraphLog is how it generates its test queries which is mostly a path between two vertices. I found myself wondering whether these biases are what's causing RGCNs to underperform on GraphLog generated data. Such doubts lead me to believe there's some gap in GraphLog that needs bridging. Please don't get me wrong, I'm sure GraphLog will still be used to evaluate KBC approaches but I remain unconvinced that it is general enough to warrant a full conference research paper. 

Writing quality wise, the presentation is clear enough with details delegated to the appendices. Related work about graph neural networks and knowledge base completion seems to be well covered. One aspect of related work that seems missing is previously proposed synthetic graph generators. For instance, did the authors try to look for generative approaches for scale-free random graphs? Are these not of interest to the KBC and graph neural networks communities for some reason?
review_title: Proposes a rule-based synthetic graph generator; Biases in the generation process lead to doubts about the paper's conclusions

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors propose a benchmark for evaluating to which extend GNNs are able to reason in terms of logical/symbolic rules. The results show that standard GNNs are mostly lacking this capability (what is not really surprising). The paper is fairly understandable and the idea is interesting. The design of the benchmark makes sense to me. Since the writing could be more clear/thorough and I have issues with related work/systems that are not considered (details below), I however do not vote for acceptance.

(+) The benchmark consists of various datasets, interesting settings (e.g., multi-task training and continual learning), and proposes a small extension of GAT which improves performance.

(-) Logic Part: 
- There's a mix of first-order logic (FOL) terminology (constants, relations) and Semantic Web terminology (entities, relations). I suggest to use either constant and predicate or entity and relation. In FOL, a relation (the notion the paper uses for predicates) is the interpretation of a predicate.
-  Rule (1) is in the most typical format considered in rule learning and called a "chain rule". You should mention this at least besides dyadic definite datalog, since the latter seems to be not fully covered. Also, other parts of the paper mention unary rules, which are not covered by (1).
- I do not think assumption (2) is realistic and wonder in how far it helps with the evaluation.

(-) Related Work: The paper mentions several related works, especially benchmarks. However, I do not understand why the authors completely ignore the entire field of rule learning/ILP. While this area is not solely based on deep learning approaches, the research and insights (esp. how to evaluate logical generalization) are relevant. There are even existing rule learning approaches based on deep learning. The paper compares to benchmarks considering image/text data but does not even mention rule-based benchmarks such as the ILP competition or Rudas (see below links). I would not support the paper's claim as it is written: "GraphLog is the only dataset specifically designed to test logical generalization capabilities on graph data, whereas previous works have largely focused on the image and text modalities." The similarities and differences to existing benchmarks (I agree that there are some, e.g., support for continual learning) need to be pointed out.
- http://ilp16.doc.ic.ac.uk/competition
- https://github.com/IBM/RuDaS

(-) Experiments: While it is ok to generally focus on GNNs, the evaluation should consider established rule-learning approaches to set the context (e.g., the recently published Open Graph Benchmark also considers standard baselines), in particular, given that the GNNs perform so disappointing. There are competitive rule learning systems such as AMIE and also deep-learning based systems which could serve as baselines. 

----------------------------------------------
Smaller Comments:
- p.2 What is the difference between generalization and adaptation?
- I think it might be good to define the notion of "compositional generalization" more clearly.
- Table. 3 caption: I think the definition of rule similarity is important enough to come in the main paper.
- p.17 ?? Fig ref
- A.2 "we ensure that all generated rules are sound and consistent with respect to R." - why should a rule not be sound or consistent w.r.t R? 

----------------------------------------------
Update after Rebuttal: I have read the other reviews and authors' responses but do no change my scores.

I still share the impression of Reviewer 3 that several choices in the design of the benchmark seem to be very restricted and arbitrary (e.g., the single possible derivation sequence).

Related work in terms of rule learning has been incorporated partly now, but there is no proper comparison -- especially in terms of the dimensions mentioned in the previous item. Also, there have been proposals similar to the E-GAT model the authors introduce which are completely ignored in the paper (e.g., MEMORY-BASED GRAPH NETWORKS, ICLR 2020; Graph Neural Networks for Social Recommendation, WWW 2019).
review_title: Official Blind Review #4

Meta-review: The reviewers point out several important issues to be addressed, including comparing to other methods that can address the "combinatorial generalization" problems studied (one reviewer points out the crucial difference from "compositional generalization" studied before), addressing the gap between the proposed dataset (simple and has the value of diagnosing/model debug/research algorithm development) and real datasets/problem settings.   

As such the AC recommends Reject and encourages the authors to take the constructive feedback to improve. 
Decision: Reject