Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses on the link prediction task of graph neural networks. The authors delve into the structural link representation and propose a labeling trick that enables existing GAE models to distinguish between non-isomorphic links.
main_review: The authors note the performance gap between GAE and SEAL on the link prediction task, and argue that the former can only learn the structural node representation, while the latter can further learn the structural link representation, which is significant for the link prediction problem. Based on the above analysis, the authors put forward the labeling trick, which theoretically proved to be a good solution to this problem. This strategy can be seamlessly integrated with existing GAE approaches so that they can learn structural link representation to distinguish between non-isomorphic links in the graph. The authors also demonstrate that SEAL, ID-GNN, and other methods are essentially special cases of the labeling trick. In general,  the paper examines a very interesting problem and provides a useful but not novel enough solution.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of using GNN for link prediction. The contributions are mainly two folds. First, it studies the limitation of using GAE for link prediction, which directly aggregate a pair of nodes embedding. Secondly, it proposes the labeling trick which is sufficiently expressive and unifies some of the existing frameworks. The proposed method is general for high-order node set prediction where link prediction is a special case. 
main_review: This paper first points out the limitation of GAE for link prediction, showing that GAE learn same representations for isomorphism nodes, this would give non-isomorphism links the same link representation. To address that, this paper proposes a zero-one labeling trick that labels the nodes in the target set $S$. This proposed trick unifies some existing GNN methods for link prediction. The expressive power of the labeling trick is also studied with theoretical guaranteed. I think the proposed method is general enough as it unifies the existing methods such as SEAL and could be applied for high-order link set prediction or hypergraph prediction. My mainly concern for the proposed method, which I also mentioned in the limitation section, is that the labeling trick need to perform node embeddings for each given target set $S$. For GAE, we could first obtain node representations for all nodes and then make link predictions for any pair of nodes. While the labeling trick seems to be link-specific, and should be computationally cost when applying to large scale data and predicting multiple links. I wonder in your experiments, how does the order of computational cost for GAE-based method and labeling based method? 
limitations_and_societal_impact: I think one major limitation is the computational cost of the proposed labeling framework. In comparison to GAE, where node representation for all nodes are learned first and link prediction could be made for multiple links at the same time, the labeling trick need to compute node representations under a given node $S$. For predicting multiple links, that is computationally cost. Would this be implemented in parallel for link prediction for multiple node pairs?
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: This paper dives into the study of some theoretical properties of GNNs and their training for the task of link prediction. In particular, it addresses the expressive power of GNNs for learning structural link representations, and points out that even with full node representation power, GNNs can fail to represent edges adequately. The authors show that the graph autoencoder method for link prediction cannot learn structural link predictions, resulting in some non-isomorphic graph edges getting the same representation. This is due to the fact that GAE methods learn node representations independently, as opposed to conditioning the representation of the target nodes on each other. The authors continue to describe a labeling trick that helps GNNs learn structural link representations, show that the trick works, and further prove that the SEAL method uses a valid labeling trick. The authors conduct experiments on three datasets to verify their theoretical results, and compare their method with a class of very basic link prediction approaches (MLP, node2vec,...) and another class of popular GNN approaches (GCN, GraphSAGE, SEAL,...). The experiments confirm their findings.

main_review: This is a very good paper that addresses important theoretical questions about GNNs that go beyond WL testing. 
The paper is very well written. The notation is consistent and laid out with care. Definitions are clear and formal. The authors motivate the reasons for studying their problem with examples, which are very helpful in following the buildup of the lemmas leading to the main conclusions in the paper. In the Related Work section, the authors cover the range of existing work on the topic and place their contribution very nicely among existing work and lay out its differences clearly. 
Experiments are well described and adequate. The authors provide many  details in the appendix, and show results of various ablations that explore questions about number of layers vs number of hops, subgraph-level readout, power of zero-one labeling, ...etc.

The paper enhances our core understanding of limitations of some GNN methods for link prediction. It also provides a labeling technique that unifies some of the existing attempts to improve the expressive ability of graph link representation. The theoretical discussions are presented general enough to apply to generalized link prediction (e.g. in hypergraphs).


Minor comments:
- Line 210: "rest nodes" should be something like "remaining nodes"
- Line 378: "then" should be "them"

limitations_and_societal_impact: Limitations address adequately across the paper/appendix.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces a new concept "labeling trick" along with multiple ways of using or decorating it such as "valid labeling trick" and "zero-one labeling trick". It proves that popular link prediction algorithms such as SEAL, Distance Encoding, and ID-GNN can all be considered as specific implementations of the labeling trick. So the new concept, though was not explicitly referred in the literature, has demonstrated its significance. The paper offers a theoretical analysis to explain the outperformance of the labeling trick over plain GAE. The authors' response addressed most of my concerns when I had a difficulty to digest the new concepts and combine them with the theory. An important suggestion is offering a figure to illustrate the labeling trick and show the specifications of the three algorithms (how they are sharing the labeling trick philosophy and still having their uniqueness of implementation). That will significantly help broad readers catch the point of this paper at the beginning.
main_review: Originality: In the authors' response, they clarified the difference between the labeling trick and graph data augmentation. It's good to know the authors will discuss this point in the paper revision. Quoting from the authors' response:
"The labeling tensor L(S) is not “new data added into the original data A”. The labeled tensor “A concat L(S)” is the new data, and this new data is not “added” into the original data. Instead, it replaces the original data A."
I suggest the authors to clarify the difference between "concat+replace" and "add" - why concatenating labeling tensor and then replacing is not adding the labeling tensor into the original data A.
Also, I need to point out that the augmentation techniques were narrowly considered (within the computer vision studies) in the authors' responses. In the two papers I've given as well as Lecture on "Graph Augmentation" in Prof. Jure Leskovic's Machine Learning on Graphs course, graph augmentation is looking for the optimal computational graph - some techniques could be adding/dropping node attributes and/or edges beyond flipping or rotating operations in computer vision.
[1] Data augmentation for graph neural networks. AAAI'21.
[2] Nodeaug: Semi-supervised node classification with data augmentation. KDD'20.

Quality: "Structural link representation" must be well defined. The definition is missing. It looks like this concept must include at least "count of common neighbors", but what else? What can GAE learn - and if the things it learned is not about structural links, why it performs better than random guess. The authors' response was not able to address my confusion at this point, though it's not a big case.

Clarity: The authors' response has made the idea and contributions of this work much more clear. I appreciate that. I would still suggest several ways to improve the clarify as aforementioned. 

Significance: I encourage exploration on the theory of graph neural networks. It is impactful to generalize the advantage of several algorithms as a new concept and provide theoretical analysis on its advantage over GAE.

I changed my score from 5 to 6.
limitations_and_societal_impact: Not included or discussed.
review_title: null

Meta-review: The paper focuses on GNNs for link prediction and sheds light on the performance gap between GAE and SEAL by identifying a key limitation in GAE. To overcome this limitation, a labeling trick is proposed that enables the unification of existing frameworks and that generalizes to high-order node set prediction. 

The AC and reviewers carefully examined the author feedback and all agree that this paper makes some very pertinent contributions leading to a better understanding of GNNs for link prediction. 

It would be important to incorporate into the main text the remark on computational complexity from the author response. As noted by the authors, the labeling trick can result in significant computational overhead, and such a limitation should not be completely relegated to the supplements.
Decision: Accept (Poster)