Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors aims to analyze the limitations of existing MPNNs on performing link prediction. Specifically, they identify that existing node-based MPNNs are not able to handle out-of-distribution (OOD) graphs for inductive link prediction, where the ``distribution'' is related to node size. Then, they further propose an edge-based MPNN to overcome this issue.  
strengths_and_weaknesses: Strengths
1. The authors conduct theoretical analysis to study the OOD issue for inductive link prediction when the test graph is large. 
2. The authors conducted comprehensive results to verify the correctness of their theories. 
3. A new framework is proposed to address the OOD issue for the link prediction task.

Weakness
1. A large portion of the analyses are based on the SBM model. Also, the features for nodes in the same block are assumed to be the same (Definition 6). Furthermore, the analyses are generally based on SBM models with isomorphic blocks. It is not clear how these analyses can be extended to more general cases.  
2. It is not very clear whether it is really an OOD issue. It seems that node-based MPNNs will experience difficulty to learn distinguishable node representations for nodes from distinct isomorphic blocks when the size of the test graph increases, regardless of the training graph.    
questions: 1. It is not very clear whether it is really an OOD issue. It seems that node-based MPNNs will experience difficulty to learn distinguishable node representations for nodes from distinct isomorphic blocks when the size of the test graph increases, regardless of the training graph. So, is it an OOD issue or an issue of learning distinguishable representations for isomorphic nodes? It would be better if the authors could provide more detailed explanations on this. For example, is there an OOD issue when the test graph is smaller than the training graph? If the training graph and test graph are both large, will the test performance be good? 

2. A large portion of the analyses are based on a specific kind of SBM model, where isomorphic blocks exist. It seems the OOD issue identified in this paper is strongly related to isomorphic blocks. So, does the OOD issue exist in other kinds of graphs (for example, graphs generated from SBM model without isomorphic blocks)? 
Also, there are some other papers[1] suggesting that MPNNs are not able to deal with graphs with isomorphic patterns.  It would be better if the authors could provide a discussion and comparison with these existing works. 

3. In general, it would be better if the authors could provide a more detailed and accurate description on the OOD issue that they try to address. As mentioned in the first two points, the analyses seems to be limited to very specific cases while the title and the introduction is very general. 


[1] Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning
limitations: N/A
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper theoretically analyze the GNN's capalability for handling link prediction. The main results show that using node embeddings for link prediction could fail to distinguish two nodes even though they are distinct in the graph as node numbers increase, and using pairwise (edge) embeddings for link prediction could successfully learn a correct prediction model and generalize the OOD graphs with larger sizes. Experiments on synthetic datasets verify the theoretical results. 
strengths_and_weaknesses: Strengths: 1. The insight of this paper is helpful for understanding the capablity and behaviors of GNN models for OOD generalization link prediction tasks, which is an active and open problem in the community. 2. Most of the results are intuitive and see correct though I did not carefully check the proof. 3. The paper is well written and easy to follow with very clear and clean notations.

Weaknesses: 1. Some of the results are confusing and need more illustration (see comments below). 2. Experiments are only conducted on synthetic datasets and more results on real-world datasets especially common GNN benchmarks are expected.
questions: While the main body of the paper seems interesting, there are still some confusing parts which would impact how the contributions are interpreted and need to be clarified before a proper evaluation could be made. I hope the following the questions could be properly addressed during the rebuttal.

1. As far as I understand, the key result of Section 3.2 is Prop 1 (though it is claimed to be contained in the Appendix) which cliams to show that for two nodes which are even distinct in the graph the link prediction model would also map them into the same embedding as the node numbers increase. If this holds true, such a result implies that the models based on node embeddings may fail to generalize to larger graphs. However, I fail to find Prop 1 in the Appendix, so cannot check its soundness and could overally downweigh the significance/contribution of Section 3.2.

2. In Section 4, the results show that the models based on pairwise embeddings would converge to an "ideal" model whose stationary solution is the graphon as node numbers increase. Then a conclusion is made that the models would successfully generalize to larger graphs. I am a little confused at this point: 1) what is the implication of the stationary point, does it mean one of the optimums or the unique one? 2) the stationary point is obtained from assumptions for the specific forms of \Phi and \Psi, does it mean the conclusion only holds for very specific situation and cannot be applied to the general regime? 3) why such a stationary point implies desirable OOD performance, it seems these two have no clear connection. 
limitations: The major limitation lies in the experiments, though most of contents seem reasonable and sound. The experiment datasets only cover synthetic datasets which are simple and limited. I suggest adding more experiments on real-world datasets, especially some common GNN benchmarks for link prediction and comparing with some SOTA approaches (even though they are not designed for OOD regime). Though I understand that the main focus of this paper lies in the theoretical insights and perspecitve, more results on benchmarks and comparison with more strong models (currently used baselines seem too weak and simple) could make this work more complete and convincing, especially that one of the contributions of this work is a new approach for OOD link prediction. 

Also, there are some recent works on out-of-distribution generalization on graphs, e.g., [1, 2, 3], which are missing in the related works and need to be discussed.

[1] Size-Invariant Graph Representations for Graph Classification Extrapolations, ICML 21.

[2] Handling Distribution Shifts on Graphs: An Invariance Perspective, ICLR 22.

[3] From Local Structures to Size Generalization in Graph Neural Networks, ICML 21.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies the ability of message passing neural network (MPNN) to perform prediction tasks on a test graph larger than the train graph. It first gives a definition of random graph and continuous MPNN (cMPNN) and proves that as the test random graph size approaches infinity, gMPNN converges to cMPNN. Then authors focus on Stochastic Block Model (SBM) and illustrate how the convergence leads to bad generalization on SBM: node representations of distinct SBM blocks can become increasingly similar as the test graph size grows even if they are non-isomorphic with a high probability. Then authors introduce structural pairwise embedding and prove that this method can solve the problem. Empirical results on SBM verify the theoretical analysis.
strengths_and_weaknesses: Strength:

1. Good originality and significance: the first theoretical study on the ability of GNNs to perform inductive out-of-distribution (OOD) link prediction tasks.

2. Novel theoretical analysis.

3. Clear representation.

Weakness:

The theoretical analysis and experiments are constrained to SBM. However, real-world graphs are different. For example, some graphs have no node features.

 
questions: Is there any results for random graphs other than SBM?
limitations: Not related.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the out-of-distribution (OOD) inductive link prediction capability of graph message passing neural networks (gMPNNs) in terms of graph sizes. While showing gMPNNs predictions can converge to random guesses when test graphs get larger, they also propose to use pairwise embeddings which can provably resolve the issue. The theoretical results are validated with synthetic experiments on random graphs.
strengths_and_weaknesses: *Originality & Significance*: Studying the OOD ability of gMPNNs is of great importance to the community, though the theoretical tools used in the paper are similar to Maskey et. al., 2022, and the solution is not new in the literature (Srinivasan and Ribeiro, 2020).

*Quality*: The authors conduct extensive works on the theoretical analysis which is appreciated. However, there are several concerns raised regarding the scope and novelty of both the theoretical and empirical results. See the Questions below for more details.

*Clarity*: The paper is well-written and organized. The authors provide informative explanations for each theoretical result which makes the paper easy to follow despite lots of theories.

questions: The authors conduct extensive works on the theoretical analysis which is appreciated. However, the theoretical tools used in the paper are similar to [1], and the solution is not new in the literature [2]. There are several concerns raised regarding the scope and novelty of both the theoretical and empirical results:

The scope studied in this work seems to be limited:
- *Task*: This paper studies the OOD inductive link prediction task in terms of graph sizes. However, it seems many of existing link prediction applications, such as knowledge graph and recommender system, focus more on the transductive settings [3,4], or ``inductive’’ settings where the training graph is a subgraph of the test graph, which is different from the setting studied in the paper. It would further strengthen the paper if the authors could provide more concrete examples for the inductive applications studied in the paper, or analysis on other settings.

- *Distribution shifts*: Moreover, the distribution shifts in graphs can be more complicated than graph sizes, as discussed in [5,6,7,8]. It would make the paper more impactful if the authors could also discussed other potential distribution shifts, such as covariate shifts on node features, subgraph appearance frequencies, averaged graph degrees [8].

- *Graph model*: The main results seem to rely largely on a certain graph model, i.e., SBM. And the failure cases seem to be limited to certain nodes in the model. I understood that providing general results for all graph models would be too difficult, however, if authors could provide more results for other graph models or more realistic graphs, it would further strengthen the paper by providing more guide for practitioners as well as future works built on the results of this work.


Regarding the novelty:
- The hardness example seems to rely on the convergence results of gMPNNs to cMPNNs in terms of the node embeddings. Does the similar results can also be developed for graph classification and node classification, too?

- Since the main results of this paper largely rely on the convergence of gMPNNs to cMPNNs on node embeddings, which seems to be similar to Theorem 3.1 from [1]. More discussions on the differences seem to be expected, especially when the convergence can also be applied to other tasks. Otherwise the results for link prediction seem to be a straightforward extension of [1] which may weaken the novelty of the work. 

- To mitigate the issue of gMPNNs when generalizing to larger test graphs, the authors propose to use pairwise embeddings [2]. Does it mean using the original pairwise node embeddings [2] can already solve the issue? It would be more helpful for the future works built on the paper if the authors could summarize the implications of the theoretical results to the practitioners. 

Minor points:
- The causal graph seems not to provide further implications.
- In line 190, i \in S_A should be I \in S_a .

== post rebuttal ==
The authors adequately resolve my concerns during the rebuttal. Hence I'd like to raise my ratings to 7. 

References:

[1] Sohir Maskey, Yunseok Lee, Ron Levie, and Gitta Kutyniok. Stability and generalization capabilities of message passing graph neural networks. arXiv 2022.

[2] Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. ICLR 2020.

[3] Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen and Philip S. Yu. A Survey on Knowledge Graphs: Representation, Acquisition, and Applications. TNNLS 2022.

[4] Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero. A Survey of Link Prediction in Complex Networks. ACM Computing Survey 2017.

[5] Beatrice Bevilacqua, Yangze Zhou, and Bruno Ribeiro. Size-invariant graph representations for graph classiﬁcation extrapolations. ICML 2021.

[6] Yingxin Wu, Xiang Wang, An Zhang, Xiangnan He, Tat-Seng Chua. Discovering Invariant Rationales for Graph Neural Networks. ICLR 2022.

[7] Qitian Wu, Hengrui Zhang, Junchi Yan, David Wipf. Handling Distribution Shifts on Graphs: An Invariance Perspective. ICLR 2022.

[8] Yongqiang Chen, Yonggang Zhang, Yatao Bian, Han Yang, Kaili Ma, Binghui Xie, Tongliang Liu, Bo Han, James Cheng. Invariance Principle Meets Out-of-Distribution Generalization on Graphs. arXiv 2022.

limitations: Since this is a theoretical work, potential negative social impacts may not be applicable.
review_title: null

Meta-review: metareview: This paper makes a compelling contribution to the study of size generation in the inductive link prediction setting. The authors extend previous results on size generalization for graph classification in a non-trivial manner and propose a new MPNN architecture with improved theoretical properties. Though the analysis is based on contrived random graph models (graphons), it's very encouraging to see that the proposed changes to the MPNN architecture lead to better experimental results. The authors also made a good effort in the rebuttal to explain their work and to enhance their experiments following the reviewers' feedback. 
confidence: Less certain
Decision: Accept