Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a novel inductive method for relation prediction over heterogeneous graphs. The method extracts supporting and refuting subgraphs to judge whether a relation exists between two nodes. In this way, the relation embedding can be implicitly expressed by the other relations in the subgraphs. The method is generalized to unseen relations. The method uses GNNs to encode subgraphs for similarity computation. Experiments on graph recommendation and link prediction demonstrated the effectiveness of the method.
main_review: Pros:

- A solid paper, well-motivated, and well-presented. The authors provide detailed examples to demonstrate the main idea of the proposed method, making the paper easy to follow.

- The method combines the logic/subgraph patterns and graph representation learning together to build an explainable reasoning method for relation prediction, such that it can be generalized to unseen relations.

- Experiments on graph recommendation and link prediction demonstrated the effectiveness of the method. It can further produce explainable heat maps of attention scores to help users understand the reasoning process of relation prediction.

Cons:

- The main weakness of the method, I think, is its poor robustness, as it requires each triple to have supporting patterns. The authors also pointed out this in the paper. I think the constraints of logical patterns are too strong. Maybe, loosening some constraints, such as not requiring the subgraphs to have the same shapes, would be helpful? I do not know—just a free discussion.

- In my view, the proposed method would cost more time than others, as it has an additional process of subgraph retrieval.

Detailed comments:

- It seems that the authors only provide the complexity analysis of retrieval and sampling. What about the overall time complexity of the proposed method? In my view, the method could cost more time than other baselines, such as those purely embedding-based methods for link prediction.

- What is the standard for choosing baselines of link prediction? It seems that some recent strong methods are not included.
summary_of_the_review: A solid, well-motivated, and well-presented work. Although the method would suffer from poor robustness, it is a meaningful attempt to connect logic/subgraph patterns and graph representation learning for explainable reasoning.

--- after rebuttal ---

The authors' response addressed my concerns. I would raise the score to 8.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper introduces a new framework for relation prediction by using "analogy" subgraphs. Authors extract some analogy subgraphs ( similar in shape ) containing the pair of source (*s*) and target (*t*) nodes, and compare them against other subgraphs sharing similar shapes. The method works by first storing base patterns (limited to pairs, 3-cycles and 4-cycles to manage complexity) and building three sets of subgraphs on top of each of these base patterns, *target*, *supporting* and *refuting* patterns for a given triplet *<s, r, t>*. Authors then sample *K* target subgraphs, and *Q* subgraphs each from *supporting* and *refuting*. This sampling is done for all *P* base patterns. These sets of subgraphs are then converted into a single vector representation using GNNs. The final prediction is derived by calculating the distance between embeddings for *target* and *supporting* (denoted as *s+*) and, *target* and *refuting* (denoted as *s-*) and feeding these numbers to a neural network, treating the final relation prediction problem as a binary classification problem.
main_review: **Strengths**
1. The core idea is deep rooted in real world applications and combines the expressive power of GNNs and raw graph pattern matching. 
2. The method is independent of the relation type and thus can be applied for *unseen* relations which makes the method more generalizable. 
3. Authors do extensice experimentation to prove the effectiveness of their method on heterogeneous graph recommendation datasets and knowledge graph relation prediction. Moreover to support the claims of generalization to unseen relation types, author conduct a separate experimentation which shows decent improvements over baseline methods.
4. Paper is well written and authors do a good job of explaining their method to the reader.

**Weaknesses/Questions**
1. Since the method relies on retrieval of subgraphs, the time complexity can take a hit. However, to resolve this issue authors limit the subgraph computation to pairs, 3-cycles and 4 cycles and precompute all such subgraphs and store on disk. This can result in high storage requirements.
2. While the gains in inductive setting are decent, the gains for knowledge graph completion and heterogeneous graph recommendation tasks are marginal. 

Q. How are the ties resolved while ranking for knowledge graph completion task? Please consider mentioning this in the main text. 
For more reference please take a look at Section 4 of [this](https://drive.google.com/file/d/1WhTapGnWM8u50E8vCcx_acGBEngUBu-i/view) paper. 
summary_of_the_review: Authors propose a new relation prediction framework *GraphANGEL* which is generalizable and combines GNNs and graph pattern matching. The experimentation done in the paper is extensive and shows the effectiveness of the method. 
Overall I feel the authors make a significant contribution to the relation prediction literature and I would like to recommend **accepting** this work.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a novel inductive relation prediction framework called ANalogy SubGraph Embedding Learning (GraphANGEL). The core idea of the approach is to compare a target subgraph (containing the nodes s and t between which the relation r is to be predicted) with other subgraphs in the graph that supports/refute the presence of the relationship. If the target subgraph is closer to the supporting pattern/subgraph then the target relationship r should also exist or vice versa. The subgraphs are constructed using 3 graph patterns namely pairs, 3-cycles, and 4-cycles.  The proposed approach is inductive as the approach doesn’t build an explicit embedding for relationships (unlike existing approaches) for prediction but masks the relationship edge while computing the subgraph representations for the supporting subgraphs. The paper proposes to precompute patterns like pair, 3-cycle, and 4-cycle and their corresponding subgraphs which are then retrieved during training and inference to get the target, supporting and refuting subgraphs. Considering specifically pairs, 3-cycles, and 4-cycles helps to keep the approach tractable. The approach is shown to consistently outperform existing approaches on heterogeneous recommendation and Knowledge Graph Completion (in both inductive and transductive settings for relation prediction) tasks.
main_review: Pros:
- The approach presented is simple and based on intuition from the real world.
- The approach is inductive and thus can be applied to unseen relations at inference time.
- Comparing multiple target subgraphs with multiple supporting/refuting subgraphs allows the use of non-local explicit structure at the prediction time. 
- Proposes efficient methods for pre-computing sub-graphs with 3-cycle and 4-cycle patterns.
- The comparison of the target with the supporting/refuting subgraphs is done using a co-attention module that allows for interpretability which can be important in certain domains like the medical domain.
- The ablation analysis is quite thorough supporting the design choices of their model.

Cons:
- While the approach is general, but the experiments are conducted by using patterns of up to 4-cycle which can be a problem if the target nodes s and t are quite far in the graph and/or the graph is disconnected. This is also pointed out by the authors.
- Because there is no explicit embedding for relation, it will not be possible to incorporate unseen relations as a part of the graph after actually observing them during inference. For instance, r1_unseen (e.g. basedin), r2_unseen(e.g. live) are 2 unseen relations observed during inference. Knowing r1_unseen can help with r2_unseen as pointed out by authors as well in the paper. As far as I know, there is no way for RGCN to incorporate the new relationship without explicitly re-training, it will miss out on using r1_unseen for predicting about r2_unseen. While having an explicit embedding/matrix for relation would actually be useful in that setting.
- The results are marginally better and the error bars (from multiple runs) are not shown which makes it harder to say if the difference is statistically significant. It would be great to have that just for the models in the main table.
- The approach precomputes the subgraphs which would be a single-time operation in a static graph. The authors also allude to this fact in Limitations on page 5.  But this may not be the case for heterogeneous recommendation settings, where I would expect that the graph to evolve very fast. In that scenario, I am concerned that there is a need to precompute the subgraphs again?

summary_of_the_review: 8: accept, Good Paper

Even though the proposed approach is simple, inductive, and is shown to be better than considered baselines, the gains seem to be marginal especially without error bars. Even in the inductive setting (i.e. section 5.4), the proposed approach doesn’t provide a significant boost compared to the baselines especially compared to CompEx-N3* baseline. For other reasons for my score please refer to the Cons section above. 

But, I think the proposed approach is interesting because of its simplicity and the problem it is trying to solve and I am on the fence leaning towards a weak acceptance. But, I am willing to raise my score if the authors can provide error bars that will validate that the results are statistically significant. I also think that the authors should add a discussion about how to scale the method when the graph changes especially in the recommendation setting. Is there a need to resample the subgraphs which means that this computation cost is no longer one-time and should be reported as a part of at least the training time imho (i.e in fig. A5)? If not, then this should strengthen the contributions of the paper and discussed (in Appendix perhaps if there is no space). 

Another interesting analysis to have is to see the performance of GraphANGEL based on the count of relations that are added for generalization study in section 5.4. Maybe, there is an interesting pattern there.  Even going a step further, instead of splitting the relations randomly split them based on the frequency of occurrence of the relation. I think that these additions will make this paper more impactful. 

Edit: Updated after reading response from the authors.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes GraphANGEL, a relation prediction framework that checks if subgraphs containing the node pair for predicting relation are similar to other subgraphs containing the particular relation. The overall idea is based on graph patterns in which analogy subgraphs are extracted for a node pair and compared against similar shape subgraphs. These subgraphs are based on three kinds of patterns I.e., target patterns, supporting patterns, and refuting patterns. The framework considers heterogeneous graph based recommendation as well as knowledge graph completion. Experiments are conducted for the above two tasks on six datasets against several baselines from the area of relation prediction.
main_review: Strengths: 
1. The idea of considering different analogy graph patterns as negative and positive ones with respect to target patterns is interesting that allows the relations to be inferred from similar relations. 
2. Paper is mostly explained well and easy to follow. 
3. Experiments show improved results for two tasks on 6 six datasets with significant margins. 
4. Time complexity is provided to get different graph patterns. 
5. The method can be plugged into any kind of GNN to see the significance of subgraph patterns being compared. 

Weaknesses: 
I find the idea interesting. However, I have some strong concerns: 
1. What about the graphs with noise since the majority of the real-world graphs have errors or noise? The method seems to focus on learning from similar subgraph patterns that would lead to incorrect results in the case of noisy graphs. 
2. I do not get the idea that says subgraphs have the same topology. All the subgraphs look similar (triangle and quadrangle) and would not make much difference in terms of structure. 
3. I believe the majority of the learning would be from the feature embeddings. I don’t see any exploitation/ usage of graph structure in the proposed method. 
4. The points mentioned under limitations in the paper are quite important. The results would be severely affected in case of missing links/ information in the graph. Also, how to overcome the second limitation. The problem would increase with larger/dense graphs. 
5. Experiments should have been conducted with different GNN architectures to see the significance of the proposed graph pattern comparisons. 

Questions to authors: 
1. What happens if a relation is being used in a different context i.e., the presence of ambiguity. Does that mean the method produces incorrect results? 
2. Did you consider cases where there are rare relations? For example, if the graph has a relation “live” only once in the graph. 
3. How large graphs can the proposed method handle? 
summary_of_the_review: The idea of the paper is different. Experiments show improved results. However, I have concerns about the methodology that majorly considers the feature embeddings without exploiting the graph structure. More experiments (mentioned in the main review) could be conducted to back the idea. Also, the points under limitations can severely affect the method in different scenarios.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a framework, which they refer to as GraphANGEL, for inductive relation prediction in heterogeneous graphs. One of the main and inarguably the most important aspects of this work is modeling the task of relation prediction as a subgraph matching problem. Since the method doesn’t require learning embeddings for relation types explicitly, it can easily generalize to new relations. Furthermore, since the proposed method requires generation of explicit graph patterns that represent logical rules, the method becomes inherently explainable. The authors further provide various algorithms for searching and retrieving subgraphs from the training data with appropriate proofs and runtime complexity wherever required. Exhaustive experiments have been conducted to demonstrate the efficacy of the proposed approach and the results provided in the main paper as well as the appendix thoroughly support the authors’ claims. The heatmaps provided in section 5.5 and A 6.3 further aid the claims about explainability and are indeed very interesting.

Formulating the problems of link and relation prediction as subgraph matching have been extensively studied in the literature and there is conclusive evidence that such approaches work very well.

It is also very informative that the authors talk about the limitations of their work in section A 4.1 . 

main_review: Strengths:

1) The proposed method doesn’t require learning explicitly embeddings for the relation types, which makes it quite effective. The ability to generalize to unseen relation types has been shown with an exhaustive set of experiments.

2) The gains provided in all the tables are very significant and the results in Tables 5 and 6 are particularly interesting and very substantial. 

3) The monotonic increase in the performance reported in section 5.3 clearly demonstrates the importance of the number of the subgraphs that are used.

4) The attention heatmaps in Figure 5 are indeed very informative and interesting. Figures 5 and A4 clearly support the authors’ claim about their method being explainable, further aiding its utility.

5) The authors have also put some effort on providing the extension of their method to complex logic in section A 4.3. It will be interesting to see some empirical work for that in the future. Although trivial, they have also mentioned the extension to homogeneous graphs.

6) The authors also provide various search and sampling algorithms while also noting the proofs of correctness and performing the complexity analysis for all of them. The proposed techniques are certainly useful in practice, at least for sparse graphs such as Wordnet. 


Weaknesses (and questions for authors):

1) Is it possible for the authors to compare against strong baselines methods for knowledge graph completion such [1] and [2]? I understand that the publication time for [1] is within 3 months of this submission, but it might be good to provide the results on at least one of the knowledge graph datasets to ensure completeness.

2) The authors’ claim about bridging logical expressions and graph patterns based on the two intuitions provided at the beginning of section 2 are indeed very sound and they have provided some examples in the subsequent paragraphs. Can they also provide reference to some relevant works that have explicitly identified such patterns?

3) Although the computation of 3-cycles and 4-cycles as a preprocessing step and storing explicitly is reasonable, this can limit the practical usage of this method, for which the authors suggest the use of Buffer B in section A 3.1. Can the authors provide more experimental details regarding the use of buffer and its size on various datasets? Can they also provide some statistics on the number of 3-cycles and 4-cycles generated for the benchmark graphs? An ablation study for the total number of cycles used in the training data could also be very useful.

4) Is there any specific reason that the authors used R-GCN? From Equation 11, it seems that some learnable parameters are required for the relation types present in training data, thus I expect that one can use any recent Graph based method proposed to operate on KGs. Can they also elaborate on the reason as to why a single layer has been used?

5) Can the authors also elaborate whether they have considered the graphs as directed or undirected? All the algorithms seem to be operating on undirected graphs. If that is the case, can they explain the reason to do so? The direction of the edges is extremely important in the benchmark graphs since it has explicit meaning. (If they have considered directed graphs, please ignore this point)

6) Can the authors also provide some more empirical runtime details, particularly on the Freebase dataset?

7) The authors mention this statement - “We note that such cases are rare in real-world graphs as they are usually scale-free, meaning that the topological distance is usually small.” at the end of section A 4.1 . Can they provide references to some relevant works that have explicitly studied this? At least for real-world knowledge graph completion tasks, the nodes can definitely be far away, with the hop distance (shortest path length) of the order of the diameter of the training graph.

[1] Zhu, Zhaocheng, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. "Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction." arXiv preprint arXiv:2106.06935 (2021).

[2] Zhang, Shuai, Yi Tay, Lina Yao, and Qi Liu. "Quaternion knowledge graph embeddings." arXiv preprint arXiv:1904.10281 (2019)

summary_of_the_review: Overall the paper is very well written, contains extensive experiments supporting their claims and proofs of correctness as well as runtime complexity analysis for all proposed algorithms, ensuring completeness. It will be very helpful if the authors can further address some of the  questions and weaknesses as pointed out in the previous subsection of this review, particularly the inclusion of some recent and strong knowledge graph completion baselines. I look forward to the rebuttal and am willing to improve the score if the authors can provide a satisfactory response. 

After addressing these minor pointers, I believe that the contributions will be worth presenting at the conference. I additionally support the simplicity of the proposed approach and given its versatility, it can be plugged with various types of  deep learning based components used for subgraph embedding computation and similarity computation.
review_title: null

Meta-review: The paper presents an approach to predict relations between node pairs in heterogeneous graphs, with application to recommendation and knowledge-base completion. 

The author's approach is to compute similarities between subgraphs that are neighborhoods of nodes where the relation holds or not to score a relation. The authors use graph neural networks to scores these subgraphs. The type of subgraphs that are considered are pairs of nodes, 3- and 4- cyles to make inference and training tractable. The paper lies in the stream of work that combines logical reasoning and neural network, even though in that particular instance it mostly combines graph mining techniques and neural networks. 

The reviewers unanimously liked the presentation of the paper and the high empirical performance. The rebuttal addressed most of the remaining concerns.
Decision: Accept (Poster)