Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors proposes if GNNs (which typically take into account neighborhood information and aggregates then, can also utilize heuristic measures like pairwise node information for link Prediction tasks and whether that improves vanilla GNN for link Prediction. The author states through experiments that a combination of link heuristics and GNN-based neighborhood aggregation techniques results in comparatively better link Prediction than only vanilla GNN and heuristic-based models. 

strength_and_weaknesses: Strengths:
+ Good literature survey
+ Experiments are performed with due diligence

Weaknesses:
- Several issues with experiments (see the detailed review)
- Some important baselines (https://arxiv.org/abs/2110.04375, https://arxiv.org/abs/2012.08974) are missing
- No code
clarity,_quality,_novelty_and_reproducibility: The paper is clearly written. I may have missed the code which I was hoping to look into. Was that made available?
In terms of the technical quality, I would say there are scopes of improvements--- see below.  The paper lacks significant novelty, I think it is mainly because of the richness of this area. 
summary_of_the_review: I elaborate the strengths and weaknesses here:

Strengths
+ The background setting is established well for the importance of Link Prediction and its wide applications.  The authors have performed experiments on large datasets (typically Order of millions in nodes) and they have showcased empirically the comparative performance of their proposed methods w.r.t GNN based Link heuristic methods (like SOTA - SEAL), GNN based methods (SOTA - GraphSage).
+ The ablation study at the end of the effect of link heuristics and GNN modules in the proposed method is well investigated and clearly shows how sparsity of the graph effects each of the components contribution. The authors provide a strong reasoning behind this phenomenon and its empirically showcased.
+ Model complexity wise the author theoretically shows how their proposed method has less complexity than SOTA SEAL method.


Weakness:

-  Missing important baselines https://arxiv.org/abs/2110.04375, https://arxiv.org/abs/2012.08974

- The question raised in the introduction part is valid but the authors do not clearly convey what methods like SEAL fail to capture which traditional link based heuristics capture. That information could setup a more strong motivational setting for the rest of the paper to follow . Why is it important to capture link based heuristics ? Does it show significant improvement than GNNs which fail to capture such info. If so any empirical reference or short writing as to why it is so. 

- The author mentions that through experimental results they are able to show the gap why link based heuristics are important for LP. It would have been nice to showcase the gap also theoretically. In link heuristics only a few classical methods are mentioned while other important link based heuristics like simrank / simrank* and it's variations are not mentioned. 

- The generalization into the set structure is a bit unconvincing like in typical simrank computations which takes into account recursiveness of its computation for all its neighbours. The fixed one hop is only assumed. Also the definition for setop nullifies there. 

- Proposition I. states that GNNs doent take into account the attenetion for a particular node or pairwise. However, models like GAT have been proposed to take that into account. What if GNNs that take into account edge reperesnetations like NBFNet ( although here it's mentioned for only node level representationsl) then do we require such heuristics any more ? What if we had hybrid of NBFNet edge emebeddings along with traditional node representation based GNNs. Does that solve the problem? Did the authors perform experiments on those? 

- Proposition I  is not convincing.  Do the authors share any examples where the pooling information over elements in one set don't contribute? A pooling information over a set of neighborhoods of a particular node will also have the inherent pooling information of the individual neighborhood nodes via message passing. Does that information. Not similar in essence to link Prediction tasks. If not can it theoretically be shown or via suitable examples. 

- Proposition II also lacks the same mathematical rigour and explanation as to why combine operation doesn't capture the same info as compared to a set intersection. 

- Proposition III is well explained via an example. However we can use weighted attentetion or weighted mean in the pooling strategy or other pooling strategies can also be used to countereffect the loss in information. Only SEAL GNN based LP was analysed. But not any other GNN based LP. For the propositions to hold it needs to be shown for all GNN based LPs and should be mathematically motivated as to which information gets missed if we have a clever pooling strategy. Also empirical results should be cited in those propositions stating whether SEAL based LP performs poorly for certain examples. 

- Does combHGs heuristic embedding not lose information since it basically a concatenation of node embeddings and as per previous propositions it should lose some information. The node embeddings might change later on due to the GNN pooling. It's not clear. 

- As per table 2 if GNN based LP produces better than traditional LPs then it contradicts the proposition that GN based LP fail to capture those heuristics which is a fundamental notion of this paper ( why such heuristics are important).

- I think Hits are not so crucial metric in the context of LP, it does not capture the recall. MAP is better.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors propose a light link prediction framework ComHG by combining link heuristics and the GNN. Link heuristics in CombHG are encoded into trainable embeddings and combined with the representations produced by a GNN.
strength_and_weaknesses: Strengths of the paper:
Well-written and easy to follow.
Experiments are conducted on a number of datasets.

Weaknesses and main concerns of the paper:

The authors claim that “the information captured by link heuristics is different from that embedded in the node representations learned by GNNs.”. What’s the relationship between the information by link heuristics and GNNs then? Are they independent to each other?

It is unclear why the authors only focus on link prediction but not other tasks such as node classification, as the inferred embeddings can be utilized in other tasks. 

It is unclear if the link heuristics can be simply defined as in Equation (1).

The contribution of the proposed model, ComHG, is marginal, which is straightforward and built based on traditional GNN model and a traditional Encoder. In terms of GNN model and the Encoder models, the contribution is marginal.

Other baselines can be taken into account for comparisons such as:
Bouritsas et al., Improving graph neural networks expressivity via subgraph isomorphism counting, TPAMI, 2022.
Fang et al., Structure-aware random fourier kernel for graphs, in NeurIPS 2021.

Are there other information that are different from “link heuristic” and “node-wise attributes” that can be integrated into ComHG?

Other minor concerns:
The first two paragraphs in the introduction section can be deleted, as most machine learning researchers have the background knowledge. (up to you)

What’re the motivations to investigate the problem: whether the GNN-based LP methods can effectively learn the information equivalent to link heuristics for LP? Can the answers and analysis inspire research on other topics?

Can we use graph neural network distillation techniques to address the task?

clarity,_quality,_novelty_and_reproducibility: The paper is well-written and easy to follow.
Not sure if the readers can reproduce the proposed model by following the paper.
Is the code of the proposed model publicly available?
summary_of_the_review: The authors are encouraged to address the issues raised in the above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors question whether these methods can effectively learn the information equivalent to link heuristics such as Common Neighbors, Katz index, etc. (we refer to such information as heuristic information in this work). The authors show that link heuristics and GNNs capture different information. Link heuristics usually collect pair-specific information by counting the involved neighbors or paths between two nodes in a candidate link, while GNNs learn node-wise representations through a neighborhood aggregation algorithm in which two nodes
in the candidate link do not pay special attention to each other.
strength_and_weaknesses: Pros: The authors intuitively show that traditional link heuristics and GNNs capture different information. They analyze this finding in theory and conduct extensive experiments to distinguish the superior performance of their proposed method.

Cons: Authors mainly analyze the subgraph based graph neural networks and point out their limitations. There are also node-wise embedding based graph neural networks which are more efficient and effective than the subgraph based ones. The authors are suggested to discuss them in the motivation. Moreover, efficiency is another important metric for evaluation link prediction systems. The authors are suggested to evaluate the inference efficiency of their method.
clarity,_quality,_novelty_and_reproducibility: The paper is clear. The novelty is moderate. And the reproducibility is good.
summary_of_the_review: Please refer to the above points for improvements.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper presents a simple yet light framework, ComHG, to predict the existence of a link by directly combining embeddings of link heuristics (e.g., Adamic Adar, Katz, RA) and the representations from a GNN. The authors further analyze that existing SEAL-type GNNs cannot effectively capture heuristic information. Experiments on four Open Graph Benchmark datasets show the effectiveness of ComHG for link prediction compared to existing GNN-based methods and link heuristics.
strength_and_weaknesses: Strengths

- The problems of GNN-based LP methods were analyzed through the comparison between the existing GNN-based LP methods and link heuristics.
- Experiments show superior performances of ComHG compared to existing GNN-based methods and link heuristics.

Weaknesses

- My main concern is the lack of novelty. Rather than proposing a GNN that can learn link heuristics, the authors simply embed the results of link heuristics and leverage them for link prediction by concatenating with representations produced by GNNs.

- Insufficient explanation of the proposed method. The author mentioned that embeddings of each heuristic method (SPD, CN, and RA) are fed into ComHG as inputs, but there is no specific explanation of how each method is embedded.

- The performance of GNN only in the ablation study (Fig 5.) and the performance of baselines using only GNNs (e.g., GCN, GraphSAGE, JKNet, GAT) are inconsistent. Specifically, the performances of only using GNN in ogbl-ppa and ogbl-ddi datasets are 61.24 and 92.15, respectively while performances of the baselines using only GNNs are under 24 and 58. 

clarity,_quality,_novelty_and_reproducibility: The presentation of the paper is easy to follow, but some parts are unclear, and the novelty is limited. See the above section on strengths and weaknesses.
summary_of_the_review: This paper presents a simple yet light framework for link prediction by directly combining embeddings of link heuristics and the representations from a GNN. The presentation of the paper is easy to follow, but the technical novelty is limited.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Heuristic and SEAL-like methods are popular ones for link prediction. Authors theoretically show that SEAL-like methods cannot effectively capture heuristic information, which can be a potential problem to get better performance. Based on this observation, the authors propose to concat embeddings from heuristic and SEAL-like methods. Experiments on four OGB datasets have shown significant improvements can be achieved compared with existing methods.

Strength
- Theoretical analysis is provided.
- Literature review is extensive and well-organized.

Weakness
- The proposed method is simple.
- Insufficient analysis on the motivation of the paper. 
justification_for_why_not_higher_score: The proposed method is straightforward and lack a detailed analysis what kind of information by link heuristics GNN cannot learn. Experiments and analysis are all on macro-level.
Decision: Reject