Limits, approximation and size transferability for GNNs on sparse graphs via graphops

Summary

This paper analyzes the transferability and approximation qualities of Graph Neural Networks (GNNs) when applied to graphs or Graph Signal Operators (GSOs) sampled from graph limit objects, known as graphops. The authors demonstrate that when a sequence of graphs is sampled from a graphop, the sequence converges according to a well-known metric. The paper also introduces the concept of graphop neural networks, which are utilized as a tool for analysis. It is shown that when a GNN is applied to a sequence of graphs sampled from a graphop, the output converges to the corresponding output from the graphop neural network applied to the graphop itself.

Strengths

- Presents a novel integration of known techniques, specifically graphops and Graph Neural Networks (GNNs). The authors notably generalized the results for graphs converging to a graphon, which has been proven in [1,2,3]. - This research could potentially pave the way for further exploration into the transferability of GNNs in relation to sparse graphs. However, the authors miss to mention some work from Keriven et al. and Ruiz et al. which already consider non-dense graphs.

Weaknesses

- The quality of writing and presenting is poor leading to bad comprehensibility. None of the theorems are self-contained. While the proofs seem correct, it is difficult to follow them due to notational issues and gaps in the argumentation (see below for a non-complete list). Note that I did not check all proofs thoroughly. - The authors make some, at least, weird assumptions such as graphops being self-adjoint, but allowing them to be non-linear. The set of such operators is empty. Also, the choices of the convergence notion are not clear, even though a subsection is dedicated to it. - Some assumptions appear restrictive, e.g.: The graphops are assumed to be sampled from $[0,1]$, in contrast to many other transferability papers (e.g. [2-4]). Assumption 3.A also appears restrictive. - The paper lacks clear organization and writing, with numerous notational errors scattered throughout. The order of presenting assumptions before other information also appears confusing. The appendix also contains many, at least, notational issues. - The practical and theoretical implications of the results remain unclear. For instance, it would be beneficial to understand: a) The potential impact of this work on theorists and practitioners, b) Examples of graphs for which the results are applicable, c) How can the convergence stated in Theorem 2 and 3 be experimentally demonstrated?, and d) The restrictiveness of the assumptions made in the study.

Questions

- Could you clarify how your convergence definition aligns with the one proposed by Backhaus and Szegedy? In particular, how can we assure that convergence results still hold if we consider a sequence of Lipschitz constant $(C_{v_n})_n$ that grows sublinearly in n? Why does $d_M$ from Backhaus and Szegedy also converge to zero in this setting? If this is sufficient, why do the authors change the notion of convergence? What motivates the chosen notion of convergence? If not for mathematical convenience, what other reasons justify this choice? - What implications do these results have for practitioners? Maybe the authors can provide some (simple) experiments, where Theorem 2 and 3 are verified? This would help for clarification and realizing an example (other than dense graph convergence which was already covered in previous works) - What implications may these results have for developing new theories? For example, do you expect to achieve generalization bounds for sparse graphs such as in [4]? - On line 73, could you explain why nonlinear operators are significant? My understanding is that all Graph Signal Operators (GSOs) are linear operators. - You sample nodes deterministically, can you compare the loss of generality with works that do not assume this? E.g., [2,3,4] - You mention that all graphops are self-adjoint. In light of this, why are nonlinear operators brought up? Note that every self-adjoint operator is linear. - Regarding Theorem 4, could you clarify its utility? Also, the proof seems peculiar and certain terms such as $A$ and $A_n$ lack clear definitions. For example, why does $S_{k,L(n)} (A_n) \subset S_k(A)$ hold? These profiles consist of different distributions, right? More details are provided below. ### Minor Issues and Questions: - Line 12: Could you clarify why graphs sampled from the same graphop share structural properties? Especially, for graphops that are not induced by graphons. - Line 24: Please consider adding [2,3]. - Line 43: Please refer to Keriven's work on "relatively sparse" graphs in the context of random graph models. - Line 53: Do you mean "limits of GNNs of infinite sequences of graphs"? - Line 58: [3] generalized the results to unbounded graphon operators and more diverse GNNs. - Line 89: Ruiz's work also indicates a $\sqrt(n)$ dependence which decays to zero, this statement seems incorrect. Also, there are other works by Ruiz considering sparse graphs. - Line 100: Random Graph Models (RGMs) essentially consist of graphons/kernels which are graph limits, and they are not opposed to these. - Line 102: Could you define "closeness"? - Line 119: Please mention that the entire work considers only spectral (polynomial) GNNs. - Line 130: The space also contains limits of sparse graphs. - Line 185: What does "positiveness" mean? - Line 235: Do the results generalize to higher dimensional features? - Line 246: What is $F_m$? - Line 310: How do you define d_M for these non-linear operators that can neither be self-adjoint nor positive? - Line 334: What do you mean with "wild"? - Line 335: Could you elaborate on what "specifically designed for our discretization scheme" means? - Line 341: Why "high probability"? - Line 379: Could you clarify what this sentence means: "Then, A_n converges to the same limit as action convergence"? #### Proof of Theorem 2: - In bounding d_H, why is the maximum over certain quantities not considered? - Line 731: Could you define the conditions for epsilon in the phrase "for some epsilon"? There seem to be numerous typos throughout, such as in equation 56 and line 727, $S_k,C_v$. - The definition of $U_\varepsilon$ is difficult to locate and appears incorrect. Equality 60 should be an inequality. - Line 763: What does $\bar{\mathcal{E}}$ denote? #### Proof of Theorem 4: - Line 1007: Could you clarify what it means for $f''$ to be Lipschitz in $l^2(n)$? - Line 1011: What does the notation $\lim_\bar{S_{k,L(n)}(A_n)}$ signify? [1] Ruiz, L., Chamon, L., & Ribeiro, A. (2020). Graphon neural networks and the transferability of graph neural networks. Advances in Neural Information Processing Systems, 33, 1702-1712. [2] Keriven, N., Bietti, A., & Vaiter, S. (2020). Convergence and stability of graph convolutional networks on large random graphs. Advances in Neural Information Processing Systems, 33, 21512-21523. [3] Maskey, S., Levie, R., & Kutyniok, G. (2023). Transferability of graph neural networks: an extended graphon approach. Applied and Computational Harmonic Analysis, 63, 48-83. [4] Maskey, S., Levie, R., Lee, Y., & Kutyniok, G. (2022). Generalization analysis of message passing neural networks on large random graphs. In Advances in Neural Information Processing Systems.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors do not address limitations.

Summary

This paper analyzes the transferability of Graph Neural Networks (GNNs) in terms of size. It proposes Graphop Neural Networks that operate on graphop signals and discretization of the network. It proves that the discretization of graphop and the graph are close, and consequently, two discretizations of different resolutions are close. It also shows that the corresponding Graphop Neural Network outputs are close which implies the transferability of GNN in size.

Strengths

My background does not support me in evaluating the paper fairly. However, I believe the tackled problem of GNN size transferability is critical, and the author's analysis using graph limit and its discretization is promising. The assumption seems mild, which could make the theory applicable to most existing GNNs and real-world sparse graphs.

Weaknesses

The related work session is scarce, which makes it more difficult for me to understand the background. The paper is purely theoretical, which is fine. Still, it will be more sensible for readers like me if the authors can provide some form of experiment on synthetic graphs of variable size to better understand the implication of the theorem.

Questions

- What is the key difference between this work and the graphon neural network which also adopt a graph limit perspective? - The bounds require the number of vertices in both graphs to be sufficiently large. Then how to interpret the bound when one graph is large and the other is smaller, which is more important for graph size transferability, and also two small graphs.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Review Summary: Due to my lack of background knowledge, I could not appropriately relate it to previous research and assess the proof fairly. However, the paper addresses a crucial problem in graph learning and seems to provide a sound theoretical analysis, which leaves it on the borderline.

Summary

This paper explores the theoretical perspective of whether graph neural networks (GNNs) can generalize to graphs that are different from the ones they were trained on. The authors study the transferability and approximation results via graph limits, including sparse graphs such as bounded-degree or power law graphs. The paper presents various notions of graph limits and develops quantitative bounds on the distance between a finite GNN and its limit on an infinite graph. The authors also verify the regularity assumption for various graph sequences in this study. Overall, the paper's contributions include a theoretical framework for studying the generalization of GNNs to different graphs, as well as insights into the regularity of graph sequences and the use of graph limits for approximation and transferability analysis.

Strengths

S1. The paper takes a unique perspective of studying the transferability and approximation results of GNNs via graph limits. The proposed approach is novel and provides a theoretical framework for studying the generalization of GNNs to different graphs. S2. The authors provide rigorous mathematical proofs and analysis to support their claims, which potentially have important implications for the practical use of GNNs in real-world applications. S3. The paper's results hold for both dense and sparse graphs, and various notions of graph limits, which makes the paper's contributions applicable to a wide range of graph-based learning tasks.

Weaknesses

W1. Lack of real-world application examples: The paper focuses primarily on the theoretical aspects of graph limits and their implications for GNN generalization. However, it would be valuable to include real-world application examples where the proposed approach can be applied and demonstrate its practical utility. This would provide concrete evidence of the significance and relevance of the work in real-world scenarios. W2. Limited experimental evaluation: While the paper includes some experimental results, the evaluation could be more extensive and diverse. It would be beneficial to include experiments on a wider range of datasets and graph structures to demonstrate the effectiveness and generalizability of the proposed approach. Additionally, providing a detailed analysis of the experimental results, including statistical significance tests and comparisons with baseline methods, would further strengthen the empirical findings. W3. Lack of comparison with existing methods: The paper could benefit from a more comprehensive comparison with existing methods that address the generalization of GNNs to different graphs. This would provide a clearer understanding of the novelty and effectiveness of the proposed approach. Including a comparison with state-of-the-art methods and discussing the advantages and limitations of the proposed method in relation to existing approaches would strengthen the paper.

Questions

Q1. Could you expand the experimental evaluation by including experiments on a wider range of datasets and graph structures? This would provide a more comprehensive understanding of the effectiveness and generalizability of your proposed approach. Additionally, providing a detailed analysis of the experimental results, including statistical significance tests and comparisons with baseline methods, would strengthen the empirical findings. Q2. Can you provide real-world application examples where your proposed approach can be applied? Demonstrating the practical utility of your approach in real-world scenarios would further highlight the significance and relevance of your work. Could you discuss the limitations of your proposed approach in more detail? Specifically, addressing the scalability of the approach to larger graphs, considering different types of GNN architectures, and exploring the impact of different graph properties on generalization performance would be interesting. Q3. Have you considered the computational complexity of your proposed approach? It would be helpful to discuss the computational requirements and scalability of your method, especially when applied to larger graphs. Q4. Can you provide more insights into the regularity assumption verified for various graph sequences? How does the regularity assumption impact the generalization performance of GNNs, and are there any specific conditions or properties that need to be satisfied for effective generalization? Q5. Can you discuss potential future directions for your research? Specifically, addressing the scalability of the approach, exploring different types of graph structures, and considering the impact of different graph properties on generalization performance would be valuable areas for further investigation.

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The paper does not explicitly address the potential negative social impact of the proposed approach. While the paper focuses primarily on the theoretical aspects of graph limits and their implications for GNN generalization, it would be beneficial to include a discussion on the potential ethical implications of the proposed approach. Specifically, the authors could consider the potential impact of their work on issues such as privacy, fairness, and bias in machine learning. Additionally, the paper could benefit from a more comprehensive discussion of the limitations of the proposed approach. While the authors acknowledge some limitations, such as the need for regularity assumptions and the limited experimental evaluation, a more detailed discussion on the potential limitations and their impact on the generalization performance of GNNs would be valuable.

Summary

This work is essentially extending the existing theoretical study of GNNs through graphons by replacing them with graphops, an operator view on graphs that allows for results of sparse graphs. Then, standard results on size generalization for instance, are presented.

Strengths

The paper is technically sound as far as I could check. The theoretical contributions are non-trivial and present enough mathematical rigor for this venue. It is a first step towards moving being graphon-restricted analysis of GNNs.

Weaknesses

The issue I have with this paper is its usefulness for machine learning applications. We understand the space L^1([0,1]^2) pretty well for graphons, but the newly introduced operator view from Backhausz and Szegedy isn't clear to me yet. Could the authors give the readers more intuitions on how P-operators can generate real-world graphs? Remember that in the end of the day the GNN is applied to real-world graphs. Graphons can be seen as latent factor models, which is somehow interpretable as a graph generating process. How can P-operators be seen by the readers? This might be a flaw in my understanding that the authors can help me with, so I'm willing to raise my score. In particular how can (k,L)-profiles be interpreted in real-world? Graphs as operators make sense in a lot of fields, but I'm a little concerned that graph data isn't fit to this view.

Questions

Could the authors give the readers more intuitions on how P-operators can generate real-world graphs? how can (k,L)-profiles be interpreted in real-world?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

NA

ack rebuttal

Thank you for the reply. I think the paper still needs intuition on the relationship to real-world graph data, that was not provided in this reply. The paper still has valid theoretical contributions, so I keep my score.

Acknowledgement of rebuttal

I thank the authors for the replies. However, some of the replies only amplified my concerns. - W1. I understand the theoretical nature of this work, but it is still beneficial for even a very theoretical work to clearly discuss its application domains, to allow proper leverage of the theoretical findings. I see the authors mention molecular graphs, road networks, grammar trees etc. These are good application examples themselves, but it looks like the authors are rather reluctant to properly discuss them in the paper. - W2. It is good to see that the authors have plans to add some proof-of-concept experiments, but with the current lack of details, I cannot tell what kind of experiments can be added and how helpful they would be to support the theoretical findings. - W3. "State-of-the-art" means anything that exists and can best solve the problem at hand. I hoped the authors could clearly discuss the status of existing studies and enhance the discussions in the paper, instead of saying "it is unclear what the state-of-the-art methods are". A statement like this is not appropriate in the rebuttal, and certainly even more inappropriate to appear in a paper. Due to these amplified concerns, I had to reduce my rating.