What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding

Summary

This paper theoretically studies node classification on latent position random graphs, a generalization of graphons. More precisely, the family of functions that can be approximated using GNNs with positional encodings are determined in general and for the examples, sign-net (eigenvector PEs) and distance-based PEs.

Strengths

* Very important and interesting topic. Most of current GNN theory focuses on WL and hence is mostly applicable to graph-level tasks. This paper takes a deep look on node classification. * Uses (and apparently requires) significant novel techniques / bounds to achieve the results (e.g., USVT estimators, pp) of independent interest. * Strong extension of [25]

Weaknesses

Sometimes the paper is not fully self-contained, e.g.: * the proper definition of graph shift matrices. * more intuition on latent position random graphs and graphons. * "special properties" of ReLU. Why don't you just say what properties you mean, Lipschitzness etc. Minor: * References are very badly maintained: A lot of references are missing either the Arxiv id or the venue (ICML, NeurIPS, ICLR etc.). Please fix this! The three references with arxiv ids are all published by now, their published versions should be used instead. * Please cite also Morris et al., [2019] when you meantion the GNN vs WL connection (you only cite [51], while the papers essentially came out in parallel). * sometimes you write "latent position random graphs" and sometimes "latent position*s* random graphs" * the claim "as medium or large graphs are never isomorphic" is a bit of an exaggeration. Perhaps say "seldom" instead of never. * While the authors explain in the text that $PE(S,Z)$ does not depend on $Z$, I wonder about the choice of notation. Wouldn't it be a lot clearer if one instead writes e.g., $PE(S)\oplus Z$ where $\oplus$ is concatation? * The paper deals with node classification. However, it is written in a way such that the reader is left unsure whether the paper might deal with graph-level tasks or not. E.g., it's not mentioned in the abstract. Only at page 2 it is almost apologetically mentioned that the authors will focus on node classification "as this is makes more sense" on large graphs. Node classification is an important and interesting task on its own. Please mention that this is your subject of study clearly in the abstract and in the beginning of the paper. Typo: * Line 232 "that sum to 1" --> "that sums to 1" * Line 59 "no not" --> "do not" [Morris, et al., 2019] "Weisfeiler and leman go neural: Higher-order graph neural networks." AAAI 2019

Questions

1. I am a bit confused by Assumption 1 and that the authors claim that e.g., the adjacency matrix satisfies it. If I am not mistaken the operator norm of a matrix $A$ is its largest singular value. For adjacency matrices of graphs this is known to be lower bounded in terms of the (square root of) maximum degree in the graph. Hence $||S||$ seems to be unbounded even for simple (and sparse!) graphs such as trees. Only for graphs with upper bounded degree this assumption seems to hold. Please explain. 2. Can your results be generalized to general graph shift matrices, as defined by [46], i.e., matrices $S$ of size $n*n$ s.t. $S_{v,w}=0$ if ${v,w}$ is not an edge. 3. Theorem 2: What happens in the case of basis-invariance (and with non-distinct eigenvalues)? 4. Of course on some specific graphs GNNs will only be able to predict using the constant function (cliques, etc.). Still, in general the space of functions approximable by GNNs *without* PEs seems interesting and rich. Is there a reason that there is no theorem exactly determining the set of functions learnable by GNNs without PEs? I imagine that e.g., nodes in the same orbit (i.e., nodes that can be mapped by an automorphism onto each other) must habe the same function value, but besides that arbitrary functions are possible?

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.

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

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Please discuss the limitations of the latent position random graph model. On what kind of real-world data is it appropriate? Are there examples which cannot be modeled well with latent position random graphs?

Summary

The paper provides a complete description of the function space generated by equivariant GNNs on latent position random graphs in order to study the expressive power of GNNs on large graphs for node level tasks. Then the paper investigates how node features such as positional encodings would affect the function space by studying two popular PE examples on two random graph models. The theoretical results suggest some normalization tricks that would help generalization across graphs of different sizes, and the paper validates this observation numerically in both synthetic and real data.

Strengths

1. The paper studies the expressive power of GNNs by characterizing the function space generated by permutation-equivariant GNNs on latent position random graphs. As the paper argued in the paper, previous work on expressive power of GNNs has largely been focused on graph isomorphism testing, which is in fact a very limited framework when it comes to large graphs or node level tasks. The results established in the paper are much more relevant in those cases. 2. The question about what role does node features or positional encoding (PE) plays in graph learning is important, and has not been well-studied in the literature. This paper provides a novel way to study them outside the graph isomorphism framework, filling the gap between previous theoretical studies and the practice. - One particular weakness of results established under the graph isomorphism framework is that node features are often assume to be uniform/random/the unique node identifiers. This conditions are unrealistic and basically ignore the role of real node features play in learning on graphs. - While PE has been widely used empirically, to the best of my knowledge, theoretical understanding of it is very limited, particularly outside of graph isomorphism testing framework. 3. The paper is clearly written.

Weaknesses

1. Although the objects of interest and technical results in this paper are mathematically precise, they are obscure. It is hard to directly interpret the corresponding function space, and given a GNN architecture with a positional encoding, one cannot easily compute and compare the function space. 2. The results are established for random graph models. Although random graph models have been useful in helping gaining deeper insights into many graph learning problems, they are synthetic graphs and there are some real graph characteristics they cannot capture. For example, nodes in stochastic block models have similar degrees, while real graphs exhibit degree heterogeneity. It is hard to know how robust/relevant the results are to real graphs or other random graph models that are not studied in the paper.

Questions

Please consider adding indices to the subplots and rewriting the caption for Figure 1, and place it around the same place as the relevant text. Currently sentence right after "From left to right" is very confusing to read.

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.

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

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

n/a

Summary

The paper investigates the theoretical expressiveness of Graph Neural Networks (GNNs) on large random graphs, and the role of node features and Positional Encodings (PEs) in enhancing their approximation power. The paper makes several contributions, such as: - Providing a complete and intuitive description of the function space approximated by equivariant GNNs on random graphs, and showing that it is determined by a base set of input features and some extension rules; - Analyzing two representative examples of PEs based on eigenvectors and distance-encoding, and extending previous universality results to more general random graph models; - Proposing some normalization tricks to ensure convergence and consistency of PEs across different graph sizes, and demonstrating their effectiveness on synthetic and real data; - Proving some new concentration inequalities for filtered random matrices that are of independent interest.

Strengths

he paper is well-written and organized, and the technical proofs are detailed in the appendix or supplementary material. The paper also provides some interesting insights and discussions on the properties and limitations of GNNs and PEs. The paper deepens the theoretical understanding of GNNs and PEs, which are widely used and studied in various domains of machine learning on graphs.

Weaknesses

N/A

Questions

N/A

Rating

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

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

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

N/A

Summary

The paper analyzes the approximation capability of Graph Neural Networks (GNNs) in node-level tasks. The work presents a novel concept of expressivity that examines whether GNNs can approximate $L^2$-functions on measure spaces as the underlying graph grows and approximates operators on $L^2$ itself. The paper characterizes the precise class of functions that can be approximated and shows that positional encodings (eigenvector and distance-based) enhance the expressive power of GNNs in line with the new definition.

Strengths

- The authors give a new framework for investigating the expressivity of GNNs in node-level tasks. - They give mathematical results and proofs, enhancing the scientific rigor of the study. - The paper is well-written. - Beyond the GNN result, the concentration and universality results offer interesting and novel insights that enrich the paper.

Weaknesses

- The authors occasionally do not discuss related work or overstate their findings. For instance, they give a novel universality result on L^2 functions and assert that their normalization rules apply to real-world graphs. Nonetheless, they do not discuss related work and test the normalization only on two small datasets. - Similarly, they claim that their results are valid for general GNNs or MPNNs-like architecture, whereas the results are primarily applicable for GCN-like architectures with a normalized adjacency matrix or 1/n*A, which is not commonly used in practice. - The primary results and the majority of intermediate results in the appendix lack self-containment, which makes it challenging to follow the paper in these technical sections. - It's unclear why the broad applicability of graph matrices and operators S and $\mathbf{S}$ is necessary when the only examples given are the normalized adjacency matrix and the adjacency matrix normalized by the graph size itself. - The real-world experiments don't align with the theory as they involve graph-level predictions, but the expressivity measure introduced is at the node-level.

Questions

- Can the authors elaborate why the 1-WL test or the concept of separating isomorphic nodes in the node-classification context is unsuitable for large graphs? Proposition 3 uses Stone-Weierstrass, indicating that distinguishing isomorphic graphs remains key for achieving universality. - The SignNet architecture studied isn't commonly employed in practice. Can the authors comment on how the function (may) change if $f$ is another permutation equivariant function, such as GIN? This is interesting as GIN was used in the original paper. - It would be beneficial to reference related works on universality results and concentration inequality, perhaps in the appendix. - Regarding the enhanced expressive power, it would be good to discuss other works that demonstrate that positional encodings (PEs) indeed boost expressivity at the graph level or node level. - Can the authors test the importance of normalizing PEs in node-level tasks? (see e.g. PPI datasets or [1]) ## Minor Points: - In Definition 1, the dependence on $n$ and what $S$ refers to is unclear. Generally one has to search too long for definition when reading the main results and results in the appendix. - Out of interest: Are there any accessible condition under which $F_S(F_{\mathrm{PE}}) \subsetneq F_{S'}({F}_{{\mathrm{PE'}}})$ holds? - There is a typo in line 594. It should be $\nu$ instead of $\varepsilon$. ## Conclusion: This paper is a very nice and valuable read for anyone interested in GNNs and the utility of positional encodings (PEs) (from the perspective of large random graphs). Despite some overstated findings and certain ambiguity in the author's claims, the paper provides a new and valuable perspective on the expressivity of GNNs in the context of large random graphs. I recommend a score of 6, but am willing to increase my score if some issues are resolved. [1] Dwivedi, Vijay Prakash, et al. "Long range graph benchmark." Advances in Neural Information Processing Systems 35 (2022): 22326-22340.

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.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

yes

Summary

This paper aims to enhance the theoretical understanding of Graph Neural Networks (GNNs) concerning their expressive power, focusing on large graphs. The paper provides a comprehensive description of the function space generated by equivariant GNNs for node tasks, incorporating notions of convergence from previous examples. The role of input node features is emphasized, along with the study of node Positional Encodings and equivariant eigen-based features. The theoretical findings suggest that certain normalization tricks positively impact GNN generalization on synthetic and real data, supported by new concentration inequalities introduced in the paper.

Strengths

* The paper is very well written and was very enjoyable to read. * The analysis is fairly novel and studies GNNs with powerful features. * The positioning of the paper with respect to existing literature is clear and honest.

Weaknesses

* The connection between the derived analysis and the practical implementation of GNNs is not clear. * The paper suggests the message-passing operations might not add up to the representation power of the GNN output features, which is not very well supported. For example, the eigenvectors and eigenvalues of the graph shift operator are able to perfectly reconstruct the graph structure. The analysis suggests that equivariant eigen-based features, which are less expressive compared to eigenvectors, not to mention eigenvectors and eigenvalues combined, do not benefit from message-passing operations. Current analysis suggests the opposite. * The analysis is mainly based on random graphs, which admit certain regularities, that do not allow concrete conclusions about the representation power of GNNs. * There are certain claims that are not properly supported, e.g., "In some context, however, WL-based analyses have limitations: they pertain to tasks on graphs (e.g., graph classification or regression) and have limited to no connections to tasks on nodes or links; and they are mostly relevant for small-scale graphs, as medium or large graphs are never isomorphic but exhibit different characteristics." How is the size of the graph related to graph isomorphism? What do the authors mean by small-scale graphs, medium or large graphs?

Questions

* Please address the above concerns. * I would appreciate it if the authors make a direct connection between their analysis and practical implementations of GNNs. How is this work benefits deep learning on real graphs? * I would also expect some more detailed experiments with respect to the benefit of the proposed normalization.

Rating

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

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

The limitations of the work are discussed in the previous sections. I am willing to raise my score if my comments are addressed properly.

Summary

In this paper the authors provide characterisations of the class of functions that can be approximated by GNNs, possibly in the presence of positional encodings (PE). Here the notion of convergence is stated with high probability and for increasing graph size. So, in large graph limit.

Strengths

- There is a lot to be liked in this paper since it provides a rigorous analysis of the function spaces that can be approximated. - The technical statements seem correct to me. - Presentation in the beginning of the paper is fine, but section 4 is rather dense. - The problem considered is quite natural, if one is interested this kind of limiting behaviour of graph learning methods. - Recent, state-of-the-art PE approaches are considered. - Giving a bit of hints in the main paper as how things are proved is appreciated.

Weaknesses

- Although familiar with theoretical expressiveness results of GNNs, this material was new for me. It took some time to understand what was meant by "GNNs become functions in the limit". Once this was clear, I looked for insights as to what results about the limit situation could tell about capabilities of concrete practical GNN architectures. More effort could have been made to make the aim and reason why more accessible. - On line 57, it is mentioned that [25] does not consider random edges, but it does. This is a bit confusion. It is also mentioned the current paper generalises previous results from [25], but this could have been made more precise. - Throughout the paper I was looking for connections to approximation properties of GNNs (with PE) on finite graphs. It is well known that approximation capabilities are closely related to the distinguishing power of GNNs (and PE), and under conditions not unlike those in Definition 2, universality wrt functions with matching distinguishing power can be shown (see e.g., work by Azizian and Lelarge). Most of the result resemble this to some extent. A discussion on more classical approximation results in this context. - As mentioned earlier, section 4 is rather dense and the presentation could be improved. For example, what are are the precise assumptions on eigenvalues and vectors that you assume in Section 4.2.1? Also you define function classes in the theorems without much explanation. It makes reading and understanding the result more difficult than it should. - The results in section 4 seem to depend on SBM or PSD kernels. It is unclear why this assumption is made. **minor** l6. certains functions -> certain

Questions

- Please elaborate on what kind of practical insights one can get from the analyses. In the discrete finite case, approximation results are easier to interpret and use to build "better" models. - A gut feeling tells me that there must be a close connection to approximation properties in the finite case. Since, PEs for example, add to the distinguishing power and hence approximation capabilities. Could you comment? - Could you intuitively explain why SBM and PSD kernel assumptions are necessary in Section 4?

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

4 excellent

Presentation

2 fair

Contribution

2 fair

Limitations

Not applicable.

Reply to rebuttal

I have read the rebuttal and thank the authors for their feedback. Based on my own review and reading the other reviews, I am going to stick to my current score. The theoretical development is nice and solid, but it really needs more grounding in practice, possibly by relating it to finite case settings, or more widely used mpns's.

I am raising my score

I would like to thank the authors for their response. I am raising my score to 5. I cannot raise it to higher scores, since there are still concerns about the practicability of this analysis.