What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding
Authors: Nicolas Keriven
Samuel Vaiter
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural network; random graph; positional encoding

Abstract: We aim to deepen the theoretical understanding of Graph Neural Networks (GNNs) on large graphs, with a focus on their expressive power.
Existing analyses relate this notion to the graph isomorphism problem, which is mostly relevant for graphs of small sizes, or studied graph classification or regression tasks, while prediction tasks on \emph{nodes} are far more relevant on large graphs. Recently, several works showed that, on very general random graphs models, GNNs converge to certains functions as the number of nodes grows.
In this paper, we provide a more complete and intuitive description of the function space generated by equivariant GNNs for node-tasks, through general notions of convergence that encompass several previous examples. We emphasize the role of input node features, and study the impact of \emph{node Positional Encodings} (PEs), a recent line of work that has been shown to yield state-of-the-art results in practice. Through the study of several examples of PEs on large random graphs, we extend previously known universality results to significantly more general models. Our theoretical results hint at some normalization tricks, which is shown numerically to have a positive impact on GNN generalization on synthetic and real data. Our proofs contain new concentration inequalities of independent interest.

What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding
Nicolas Keriven CNRS, IRISA, Rennes, France nicolas.kerivenn keriven@enss...r
Samuel Vaiter CNRS, LJAD, Nice, France samuel, vaiterocnrs.ft
Abstract
We aim to deepen the theoretical understanding of Graph Neural Networks (GNNs) large graphs, with focus on their expressive power. Existing analyses relate this notion to the graph isomorphism problem, which is mostly relevant for graphs of small sizes, or studied graph classification or regression tasks, while prediction tasks on nodes are far more relevant on large graphs. Recently, several works showed that, on very general random graphs models, GNNs converge to certains functions as the number of nodes grows. In this paper, we provide more complete and intuitive description of the function space generated by equivariant GNNs for node-tasks, through general notions of convergence that encompass several previous examples. We emphasize the role of input node features, and study the impact of node Positional Encodings (PEs), recent line of work that has been shown to yield state-of-the-an art results in practice. Through the study of several examples of PEs on large random graphs, we extend previously known universality results to significantly more general models. Our theoretical results hint at some normalization tricks, which is shown numerically to have a positive impact on GNN generalization on synthetic and real data. Our proofs contain new concentration inequalities of independent interest.
1 Introduction
Machine learning on graphs with Graph Neural Networks (GNNs) [53, 5] is now well-established domain, with application fields ranging from combinatorial optimization [6] to recommender systems [50. 11], physics [45, 1]. chemistry [16], epidemiology [37], physical networks such power grids [41], and many more. Despite this, there is still much that is not properly understood about GNNs, both empirically and theoretically, and their performances simple baselines in some cases. It is generally admitted that a better theoretical understanding of GNNs, especially of their fundamental limitations, is necessary to design better models in the future.
not always consistent [52, 22], compared
Theoretical studies of GNNs have largely focused on their expressive power, kickstarted by a seminal study [54] that relates their ability to distinguish non-isomorphic graphs to the historical Weisfeiler- Lehman (WL) test [51]. Following this, many works have defined improved versions of GNNs be "more powerful than WL" [34, 35, 26, 49, 38], often by augmenting GNNs with various features, by implementing "higher-order" versions of the basic message- passsnng paradigm. Among the simplest and most effective idea to "augment" GNNs is the use of Positional Encodings (PE) as input to the GNN, inspired by the vocabulary of Transformers [48]. The idea is to equip nodes with carefully crafted input features that would help break some of the indeterminancy in the subsequent message-passe passing framework. In early works, unique and/or random node identifiers have been used [32, 471, but they technically break the cemmutatoo-invarianneeeeivaaaiii in the graph- - of the GNN. Most PEs in the current literature are based on eigenvectors of the adjacency matrix or Laplacian of the graph [12, 13] (with recent variants to handle the sign/basis indeterminancy
consistency with reordering of the nodes
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

[3]],, random-walks [13], node metrics [56, 30], or subgraphs [4]. Some of these have been shown to have an expressive power beyond WL [30, 4, 31].
In some contexts however, WL.-hased analyses have limitations: they pertain to tasks on graphs (e.g. graph classification or regression) and have limited to no connections tasks on nodes; and they are mostly relevant for small-scale graphs, as medium or large graphs have a negligible chance of being exactly isomorphic to one another, but exhibit different characteristies (e.g. community structures) that might be useful for learning. At the other end of the spectrum, the properties of GNNS on large graphs have been analysed in the context of latent positions Random Graphs (RGs) [24, 25, 43, 44, 29, 2. 36], a family of models slightly more general than graphons [33]. Such statistical models of large graphs are classically used in graph theory [18. 9] to model various data such as epidemiological [27, 39], biological [17], social [20]. or -erotin interaction [19] networks, and are still an active area of research [9]. For GNNs, the use of such models has shed light on their stability to deformations of the model [44, 29, 24), expressive power [25], generalisation [15, 36], or some phenomena such as oversmoothing [23, 3]. One basic idea that, as the number of nodes in a random graph grows, GNNs converge to "continuous" equivalents [24, 8]. whose properties are somewhat easier to characterize than their discrete counterpart. As prediction tasks on nodes are far more common and relevant on large graphs modelled by random graphs, this paper will focus on germulation-equivvriinn In the limit, it has been shown that their output converge to functions over some latent space to label the nodes, but the descriptions of this space of functions and its properties are still very much incomplete. A partial answer was given in [25], in which some universality properties are given for specific models of GNNs, but for limited models of random graphs with no random edges, and specific models of GNNs that no not include node features or PEs. We will in particular extend some of their results to random edges, with the proper choice of PEs.
GNNs, rather than
inauutation-invariann
Contributions. In this paper, we significantly extend existing results by providing a complete descrip- tion of the function space generated by ceamuutaiio-eqqiariinnnn simple stability rules, and show that it is equivalent to previous implicit definitions that were based on con- vergence bounds. We outline the role of the input node features, and particularly of Positional Encodings (PEs). We then study the several representative examples of PEs on large random graphs. In particular, we analyze SignNet [31] (eigenvector-be based) PEs (Theorem 2), and distance-based PEs [30] (Theorem 3). We derive simple normalization rules that necessary for convergence, and illustrate them real data. Finally, our proofs contain new universality results for equare-iitegraan inequalities that are of independent interest. All technical proofs are available in the Appendix. The code to reproduce the figures can be found at https: / /i thub. coom/nkerivee weckeeriiee/eeeeeee
GNNs (Theorem 1), in terms of
functions and new concentration
wewrriiee/rannrrree random- graph- grnn
2 Background on Random Graphs and Graph Neural Networks
Let us start with generic notations and definitions. The norm ||-|| is the Euclidean norm for vectors and the operator norm for matrices and compact operators between Hilbert spaces. The latent space X' is a compact metric set with probability distribution P over it. Square-integrable functions from X' to R9 w.r.t. P are denoted by L3. and are equipped with the Hilbertian norm I| def Sx [lf(z)) dP(z).
The (disjoint) union of multidimensional functions L3 def. LyEN- LG is a metric space for metric defined as |f - gلl if f, E L3 for some q, and 1 otherwise. Continuous Lipschitz functions between metric spaces X' + ) are denoted by (L', V). For X = {xI,.... Φn} where x, E X, we define the sampling of f X' - Id as 1x = [f E Rad Given Z E Raxd the Frobenius norm is || ||: and we define the normalized Frobenius norm as || = n 1 || The notation comes from the fact that -f = -1 Σ, (l - f*()):]] ff which is akin to Mean Square Error.
Latent position Random Graphs. In this paper, we consider latent position random graphs [20, 28, 331, a family of models that includes Stochastic Block Models (SBM), graphons, random geometric graphs, and many other examples. They are the primary models used for the study of GNNs in the literature [24, 25, 29, 43]. We generate a graph G = (X, A, 2), where X E Rxd are unobserved latent variables, A {0, ]] its symmetric adjacency matrix, and Z RRxp are (optional) observed node features. The latent variables and adjacency matrix are generated as such:
Vi, Z4 idd P.
Vi j. ai ~ Bemoull((q,wx2z1.3 independently
(1)
2

---

where w: : A' x X' + 10. is a continuous connectivity kernel and ar is the sparsity-level of the graph, such that the expected degrees are in O (n²o,,)) Non-dense graph can be obtain with on = o(1), here we will go down to the relatively sparse case an Z (log n a classical choice in the literature [28, 24]. Note that the continuity hypothesis of the kernel w is not really restrictive: neither X' nor the support of the distribution P need be connected. For instance, SBMs can be obtained by taking X' to be a finite set. We do not specify a model for the node features yet, see Sec. 4.
Graph shift matrix and operator. When the number of nodes n grows on random graphs, it is known that certain discrete operators associated the graph converge to their continuous version, well as the GNNs that employ them [24, 8). Here, some of our results will be valid under quite general assumptions, hence
generic notations for our graph representations. When the results are only valid for particular examples, this will be specifically expressed.
We consider graph shift matrix [46] S = S(G) E RR"*, which can be either directly the adjacency matrix of the graph or various notions of graph Laplacians. We define an associated graph shift operator S : L. Lu such that the restriction S S1,33 ; is compact linear operator of L onto itself. Note that we reserve "matrix" and "operator" respectively for the discrete and continuous versions. The results in Sec. 3 will be valid under generic convergence assumptions from S to S, while the results of Sec. 4 will focus the following two representative examples.
Example (Normalized adjacency matrix and kernel operator). Here S (ncx)) A and SS = Aʃ = I w((, (()((.). This choice requires to know, or estimate, the sparsity level on- In this case, our results will hold whenever an 2 (logn)/n with an arbitrary multiplicatiiv constant.
Note that this choice requires to know (or estimate) the parameter On, otherwise we will not have convergence between S and S. which can be limiting. This is not the case of the next example.
AD 1/2 where DA= Example 2 (Normalized Laplacian matrix' and operator). Here S = L= = 1/2
=
diag( (A,,) is the degree matrix of G. and Sf Lf
ml m(.aa) d((x)) where d(-) = ʃ w w(.x))P((x)
Vat )d(x)
is the degree function. Whenever we opt for this choice, we assume that duii 'infx x d(x) > O, and our results will hold whenever an > C(log n)/n with a multiplicative constant C' that depends (in a non-trivial way) on w, see Thm. 9 in App. D.
To sometimes unify notations, when we adopt these examples, we define we such that ug (x, y) w(z, y) w(z..) in the normalized Laplacian case. Therefore for these in the adjacency case and ws ws(æ y) /a(z)d(y)
two examples the continuous operator has a single expression Sf ws ( x))P(x).
Graph Neural Network. As mentioned in the introduction, we focus on equivariant GNNs that can compute functions over nodes, as this makes the most sense on large graphs that RGs seek to model. Recall that we observe graph shift operator S and node features Z E Raax,, and we return vector per nodes (SS Z) R= We adopt traditional GNN that uses the graph shift matrix St given input features ( E R_xdo
20 = = 1 (f + -Z(0-1) + +11(((0)))) E Bnxde
(0()) = 2(L-1) + (6(44))
(2)
where p is the ReLU function applied element-wise, and ( E Rdxdds- b(() Re are learnable parameters gathered in 8 O. We denote by θ the set of all possible parameters. For all classic choices of S. our definition of GNNs are special case of message- gaassnigg NN (MPNN), which can be defined with a more general "aggregation" function. For the two examples above (adjacency and Laplacian), the aggregation function used is a sum, or normalized sum.
We note that here we employ the ReLU function as non-linearity, as some of our results will its specific properties. Multi-Layer Perceptrons (MLP, densely connected networks) using the ReLU activation, and with potentially more than one hidden layer, will be denoted by /MLP" where y gathers their parameters.
Note that the normalized Laplacian is traditionally defined as Ld L. here it does not change our definition of GNNs since they include residual connections
3

---

Following recent literature [12, 131, we consider inputing Positional Encoding (PE) at each node. Such PE are generally computed using only the graph structure and concatenated to existing node features Z, here we simply introduce generic notation:
Z (S, B=
(3)
with some parameter E T. In our notations, the PE module uses the node features Z. generally by concatenating them to its output. For short, we may denote the whole architecture with PE and GNN as (e,, 2) (s,S, (S, Z)). It is not difficult
that if the PE computation is equivariant, then the whole GNN is equivariant: denoting by o a permutation matrix of [I....,.).
Vo, p0, (oSo T oZ) = o (S,
Vo, (oSo ,o , =oPE
All the examples of PEs examined in Sec. are equivariant.
3 Function spaces of Graph Neural Networks
In this section, we provide a complete and intuitive description of the function space approximated by equivariant GNNs applied on RGs. All technical proofs are provided in App. A. It has been shown [24, 25, 8, 29] that GNNs converge to functions over the latent space: when the node features are a sampling of certain function 1x f then the output of the GNN is close to being a sampling of another function xx f(L), Assuming the node features PEs approximate some function set B L we define the space of functions that GNN can approximate as follows.
Definition 1. Given a base set B C. L2, the set of functions approximated by GNNs (B) is formed by all the fanctions f L2 such that: for all > 0, there are 0 E f(0) E B such that
IP( (1
1xf MSE 3 E)
n2-00 O.
(4)
other words, FBN are the functions whose sampling can be e-approximated by the output of a GNN, with probability going to as n grows. Note that if the quantifiers of 8, f()) and E were reversed, the MSE would converge to 0 in probability. Here this is not the case: 0, f(()) may depend on E, which is akin to approximation level. Similar to the permutation equivariance of GNNs, there is notion of continuous equivariance for functions vell-approximate
by GNNs [24, 25, 8]. where the permutations are replaced by bijections over the latent space X. We adopt the notations FGNN (B) FaNN (B, w. P). For all continuous bijections & over X, we define w (I. y) = w()(z), (yy)). Pg = x 1P where & is the push-forward operation, and B. {f & f E B}. Then, we have the following result.
Proposition 1. Let S S(A) be graph shift operator that only depends the adjacency matrix of the graph in a coimmutttio-qquivariiii manner. Then, for all continuous bijections Φ : X + X,
Fo Wo Po) =ff f e FoNN(B, w, P)}.
That is, if one "permutes" the kernel the distribution P and the base set B, then the function space FENN contains exactly the permuted version of the original space.
The goal of this section is to provide a more intuitive description of the space FaNN, which we will do under some basic convergence assumption from S to S. GNNs (2) basically include two components: dense connections and MLPs that can approximate any continuous function by the universality theorem [40]. and applications of S. Hence, we define the following function space.
Definition 2. We define FB( T.3 the (minimal) S-extension of a base set B C T. by the following rules:
(i) Base space: C. FB(B):
(ii) Stability by composition with continuous functions: for all f Fs(B) with p-dimensional (RR,,RRR))) RR), it holds² that o E FB(;); oulput and g E (RP,
(iii) Stability by graph operator: for all E (B)),, it holds that S, E FB(B);
Note that, since g is Lipschitz, when f E L3 we indeed have g o f L3

---

(iv) Linear span: for all Fs(B) n Lg is vector space;
(v) Closure: FB( is closed in L2; (vi) Minimality: for all 9 c LL satisfying all the properties above, Fs C C.
In words, Fs take base set B, and extend it to be stable by composition with Lipschitz functions, application the graph operator, and linear combination (of its elements with the same dimensionality). Our result will use the following assumption, which is naturally true for our running examples.
Assumption With probability going to 1, ||S]| is bounded. Moreover, for all f E T2
P p+0
|| - -xXf MSE
where En indicates convergence in probability.
Proposition 2. Assumption is true for the adjacency matrix (ex. 1) and normalized Laplacian (ex. 2).
Under this assumption, the main result of this section states that the functions well-approximated by GNNs are exactly the S-extension of the base input features B.
Theorem Under Assumption for all C T2 we have:
FGNN(B) = FB(
Given the definition of GNNs (2) and construction of Fs. Theorem 1 appears quite natural. Its proof, provided in App. A.3, is however far from trivial. The inclusion Fs (B) C. FBN is similar in spirit to previous convergence results [24], since one has to construct a GNN that approximates a particular function. It involves however new extended universality theorem for MI.ss for square-integrable functions (Lemma 3 in App. A.3), which uses the special properties of ReLU.. The reverse inclusion FB) (B) is quite different from previous work on GNN convergence: given f E FGNN (B) whose only property is to be well-approximated by GNNs, one must construct sequence of functions Fs(B) that converge f, and uses the closure of Fs (B). The need to work within square-integrable function is here obvious, as we only have convergence of the MSE, an approximation of the L norm. For instance, this inclusion would not be true in the space of continuous functions.
Using composition with continuous functions, Fs contains a continuous bijection Ø X - Im( then (B) contains all continuous functions, and by density all square integrable functions. That is, the equivariant GNNs are then universal over X:: they can generate any function to label the nodes. Another criterion using the Weierstassss theorem (e.g. [21]), similar to the proofs in [25], is the following.
Proposition 3. Assume that for all x # x' in X, there is continuous function f E ( IR) such that f(x) + f(x'). Then, FB( = L.
In the rest of the paper, study several examples of PEs and corresponding set B, that will generalize the results of [25]. We expect many other interesting characteristics of Fs to be derived in the future.
4 Node features and Positional encodings
In the previous section, we have provided a complete description of the function space generated by equivariant GNNs when fed samplings of functions as node features, and the set of B is thus crucial for the properties of Fs (B). For instance, in the absence of node features and PEs, it is classical to input constant features to GNNs [25], such that the space of interest is (1). However, similar to the failure of the WL test on regular graphs, S1 x 1 (e.g. constant degree function), then (1) contains only constant constant functions! The role of PEs is often to mitigate such situations.
Definition 3. The set of functions approximated by PEs FPE is formed by all the functions f E L such that: for all >> 0, there is 7 I such that
P PE, (S, [S, - -xxfll MMEE 26)
0.
(5)
Note that, as before, 7 may depend on e. When passing PEs as input to GNNs, Fre serves as the base space B, and the space of interest to characterize the functions well approximated by the whole
5

---

architecture yø,7 is therefore Fs((FE) In fact, by simple Lipschitz property: for any f E (FP) and > there are E 0,, E such that
P( fa, (S, 2) 1x 2 2
n--00
In the rest of the section, we therefore aim characterize FPF for several representative examples. We first briefly comment on observed node features, then move on to PEs. Proofs are in App. B.
4.1 Node features
A first, simple example, is when observed node features actually sampling of some function
Z = 1x f() This is a convenient choice that is often adopted in the literature [24, 25, 23, 8, 29]. In this case, by adopting the identity PE, (S, Z) = Z, it is immediate that JPE = {f }. A more realistic example is the presence of centered noise:
Z x (0) + E RR
(6)
where [y,....,Py Pn] and the v are i.i.d. noise vectors with Ey; 0 and Cov(4) Cy. This time, FPg cannot contain directly f()), as the Law of Large Numbers (LLN) gives
2| - xx - [(0 MSE = -|
Tr(C.) >
However, when applying the graph shift matrix at least once, one obtains convergent PEs.
Proposition 4. Consider the adjacency matrix (ex. 1) or normalized Laplacian (ex. 2). If the node features are a noisy sampling (6) and the PE are defined (E, 2) SZ, then, FPE = { ())
Of course this may not be the only possibility for removing noise from node features, and moreover it is not clear how realistic the node features model (6) actually is. The study of more refined models linking graph structure and node features is major path for future work.
4.2 Positional Encodings
In this section, we consider classical PEs computed solely from the graph structure and show how they articulate with our framework. We consider two examples that are the most-often used in the literature: PEs eigenvectors of the graph shift matrix [12, 13] (actually recent variant that account for sign indeterminancy [31]), and PE based on distance-encoding [30] (again a variant that, as we will see, generalize other architectures [49]). For most of the results below, we will focus two representative cases of kernels, that include many practical examples. We remark that these yield sufficient conditions to establish results, but by no mean necessary. Other cases could be examined in future work.
Example a (Stochastic Block Models). In this case, the space of latent variables X = (l,..., is finite, each element correspond to a community label. The kernel w represented by a matrix C del. [w(P, k)] E R K that gives the probability of connection between communities E. and k. and P RKK is a probability vector of size K that sum to 1.
Example (P.s.d. kernel). Here we assume that w is positive semi-definite (p.s.d.). This includes for instance the Gaussian kernel.
For any symmetric matrix (resp. self-adjoint compact operator) M, denote by X its eigenvalues and uM its eigenvectors (resp. eigenfunctions), with any arbitrary choice of sign basis here. Since in all our examples operators are either p.s.d. or finiterank, the eigenvalues are ordered as such: first the non-zero eigenvalues by decreasing order (from positive negative), then all zero eigenvalues.
4.2.1 Eigenvectors and SignNet
It has been proposed [12, 13] to feed the first eigenvectors of the graph into the GNN, for a fixed g. A potential problem with this approach is the sign ambiguity of the eigenvectors, ambiguity in case of cigenvalues with multiplicities. Here we consider only the sign ambiguity for simplicity: will assume that the first eigenvalue of S distinct. The sign ambiguity was alleviated [31] by taking a sign-invariant function: considering an eigenvector ug of S,
the basis
(Q.)) del f(u,) ((-u,) E "
(7)

---

errar-0.8..0 0.018
test brror-D.565
039
65
Train Test
Train
Test
si 120
10- odr su sde sls 18y
20 ca3 ab an
Figure Illustration of role of SignNet architecture and of renormalization by v of eigenvectors on synthetic data, with a latent space X' = [-1, 1] (æ-axis). a Gaussian kernel w. and uniform distribution P. Blue dots represent a graph from the training set, orange dot test graph that is twice bigger. From left to right: eigenvectors with renormalization (with a different sign for the two graphs), eigenvectors without, PEs with, and PEs without, with the regression test errors of GNN trained using these PE with or without renormalization. We observe that SignNet indeed fixed the sign ambiguity. The absence of renormalization yields unconsistent PEs across graphs different sizes, which results in high test crror on test graphs than training graphs
where f + R is function applied each coordinate of up to preserve permutation-cquivariii The resulting function is sign-invariant, and one can parameterized f. Given the first eigenvectors up and collection of MI.s /ALP, -> R.P for some output dimensions pt, the PE considered in this subsection concatenates the outputs:
(S) [0
(VTT (
(8)
where p- = Ei= Pr and the MLP are applied element-wise. The parameter gathers the %. The equation (8) involves a renormalization of the eigenvectors u by the square root of the size of the graph /n: indeed, as un is normalized in R this necessary for consistency across different graph sizes. See Sec. 4.2.3 for a discussion and some numerical illustrations.
As can be expected, the eigenvectors of S generally converge the eigenfunctions of S, under spectral gap assumption. We provide the theorem below which handles all of our rumning examples. We suppose that the relevant eigenvalues have single multiplicities, only have sign ambiguity.
Theorem 2. Consider either SBM (ex. a) p.s.d. kernel (ex. b), and either adjacencc matrix (ex. 1) or normalized Laplacian (ex. 2). Fix g, assume the first q + eigenvalues x distinct. We define
: N of S are two-by-two
FFg
def. {[(Q))) o 11 u Se (RR
Then FPE FEig-
Hence FPE contains the eigenfunctions of S, modified by the SignNet architecture to account for the sign indeterminancy. We further discuss this space in Sec. 4.2.3. An illustration provided in Fig. 1.
4.2.2 Distance-encoding PEs
In [30], the authors propose define PEs through the aggregation of a set of "distances" {ii, j) from each node i to set j Vr of target nodes (typically, labelled nodes in semi-supervised learning, or anchor nodes selected randomly [56]):
(PE,)..: AGG(EE()))
where AGG is an aggregation function that acts on (multi-)sets, and E(i,j) is selected in [30] as random- walk based distances E(i,j) = [(AD> "........................ ((AD=1)9)s) E Rd. For simplicity, since here we do not consider any particular set of target nodes, we just consider Vr V the of all nodes. Moreover, to use our convergence results, we replace the random walk matrix with our graph shift matrix S. As aggregation, we opt for the deep-set architecture [58], which applies an MLP on each {i,,)) then sum. function. As we will see below, with the proper
Deep sets can approximate any permutation-invant normalization to ensure convergence, we obtain:
PE 1 Σ, MLP (n (Se
Raxq
where MMP R + R2 is applied row-wise and ej E RD are one-hot basis vectors. We note that a similar architecture was proposed in different line of work: was called Structured Message Passing by [49], Structured GNN by [25]. In these works, the inspiration is to give nodes unique identifiers,
7

---

e.g., one-hot encodings e;. However, this process is not equivariant. To restore equivariance, [49] propose a deep-set pooling in the "node-id" dimension (S) = E (S, ej), where Φ,, is itself a cermutation-equivant n n= - (n [Se]..... Sye,]) (which a valid choice for a pessaae-passiing GNN), we obtain exactly distance-encoding PEs above.
GNN, and the equivariance of PE, is restored. By choosing Ly (S,( e,) =
In [25], powerful universality results were shown for this choice of architecture in the case of non-random edges 0zj = w w( 2z) and = 1. With our notations, they implicitely studied PE functions of the following form: J ((w(,)))dP(r))
This allows to modify the values of the kernel before computing the degree function, and can therefore break potential indeterminancy such as constant degrees. Unfortunately, their proof technique and the concentration inequalities they use are not true anymore for Bernoulli random edges, which are far more realistic than deterministic weighted edges. Here we show that for a large class of kernels, concentration can be restored when we add an MLP filter on the eigenvalues of S with ReLU. Our definition of distance-encoding encoding PEs is therefore:
PE = E, MAPP (n 1S
S ey)e
(10)
where Sy def. h (S) is a filter that applies an MLP MMP on the eigenvalues of S.
Theorem 3. Consider either SBM (ex. a) or p.s.d. kernel (ex. b), and either adjacency matrix (ex. 1) or normalized Laplacian (ex. 2). Consider the PE (10), We define
Fiist def. { ((..),)).....55....... (%),())))(z 15 CLp(10, 1), RP), E 3
(11)
where S def. {2 ws(2,x)) by abuse of notation. Then FDist FrE-
Note that here we only have an inclusion FDist C FPB instead of an equality as in Thm. 2: indeed, we show that the PE (10) can approximate functions in Fiit. but they may converge to other functions. Nevertheless, as a consequence of our analysis, all the universality results of [25, Sec. 5.3] are valid with the choice of PE (10), see Appendix C for a reminder using our notations. This is strict, and non-trivial improvement over [25], as their results were only derived for non-random edges. For this, Theorem 3 relies mostly on new concentration inequality for Bernoulli matrices with ReLU filters in Frobenius norm, that we give below since it is of independent interest.
Theorem 4. Consider either SBM (ex. a) or p.s.d. kernel (ex. b), and either adjacency matrix (ex. 1) or normalized Laplacian fex. 2). Define the Gram matrix W [ws( 2z)/n]jj- For all > O, there is an MLP filter S., = fa (S) such that
P(IIS, - |F > 8) + O.
The proof of this theorem, given in appendix B.3, is inspired by the so-called USVT estimator [7]. One notes that the use of an MLP graph filter is quite unconventional. A more classical choice is polynomial filters: this avoids the diagonalization of S by computing Σg S*, it is for instance the basis for the ChebNet architecture [10]. For the purpose of Theorems and 4, polynomial filters do not work, and ReLU is of crucial importance: indeed, we need the filter to zero-out O (n) eigenvalues uniformly in some interval [-T, 7). This cannot be done with polynomials with a fixed number of parameters and growing n + co. On the other hand, when choosing f as an MLP with ReLU, due to the shape of this non-linearity, /MLP can be uniformly 0 on a whole domain. Of course, polynomial filters offer great computational advantages, and perform well in practice, despite their flaw in our asymptotic analysis. Moreover, ReLU is technically non non-differentiable. Designing filters that offer both computational advantages and exact approximation is still an open question. In practice, we observe that the Rel ---lterl does learn to approximate its expected shape, when we minimize the reconstruction error ||S., WIl; on synthetic data where W is known, Fig. 2.
015-
filter
Leamned fllter
110
Ideal filter
665
600
-0.5
Illustration of Theo- rem 4 on synthetic data where W is known, with a Gaussian ker- nel. Unfiltered eigenvalues of S are represented by blue crosses, tered ones obtained by minimiz- ing min-; ||S.,, - Wll, by orange dots, and the ideal U-flltf used used in the proof of Thms. 3 and 4 is rep- resented by red line.
Figure 2:
8

---

4.2.3 Discussion
Approximation power. As mentioned above, in the absence of node features, one may opt for constant input, but this may lead to degenerate situations. PEs aim to counteract that, by increasing GNNs' approximation power. We quickly verify that this is indeed the case for our two examples.
Proposition 5. There are cases where Fs (I) Fs( or (F with strict inclusions.
Moreover, as mentioned in the previous section, existing universality results [25] can be generalized in our case, see App. C. Another interesting question is somewhat the opposite: given the already rich class of functions generated by PEs, are GNNs really more powerful?
Proposition 6. There are cases where FEgg C (F(e)) or F C FF with striet inclusions.
The proof, which is not so trivial, invokes functions with at least one round of message-passiing after the computation of PEs, so the additional approximation power does not come only from MLPs. Intuitively. it seems natural that pressage-passing rounds are useful for other reasons, c.g. noise reduction or smoothing [23]. We leave these complementary lines of investigation for future work.
Renormalization. A striking point in our variants of PEs is the presence of various normalization factors by the graph size n to ensure convergence: the equation (8) involves a renormalization of the eigenvectors uº by the square root of the size of the graph vn, while (10) involves a multiplicative factor n inside the MLP fMLP (the 1/n outside of the sum is more classical). Our analysis shows that these normalization factors necessary for convergence when - 0o, and more generally for consistency across different graph sizes.
In practice, this is generally not used. Indeed, if the training and testing graphs have roughly the same "range" of sizes n E [Mmmin: mmaa then a GNN model can learn the proper normalization perform, which is not the point of view of our analysis n - oc. While in-depth benchmarking of PEs has been done in the literature [13] and out-of-scope of this paper, we give a small numerical illustration of the effect of normalization in Table 1. We consider synthetic dataset with a classic classification problem on (unobserved) latent variables n; and a Gaussian kernel W. To emphasize the effect of the normalization, we also examine a situation where the test graphs are much larger than the training graphs while following the same model, which we denote by out-of of -dist. Concerning real data, since there are practically no datasets for node-classification with several graphs of sufficiently different size to test the renormalization, we artificially extract many subgraphs from a single large graph (Citeseer) with labelled nodes to create such dataset, denoted by wwseseer-suggaappp sapph--lassfficttinn datasets with many graphs of different sizes. Note that, to emphasize the effect of PEs, we discard eventual node features and use only the graph structure.
We also directly look at two
On synthetic data exactly formed of random graphs of vastly different sizes, the renormalization is of course necessary to obtain good performance, as predicted by our theory: without it, the PEs do not converge when n grows. On real data, we see that renormalization generally improve performance, and this is more true for IMDB-BINARY, which contains larger range of graph sizes, and distance-based PEs. Note that here we use relatively small GNNs that are not state-of-the-art (in particular since we do not use node features), as well as different train/test split than most papers (K 5 CV-folds instead of K = 10): indeed, we do not want our models to learn the proper normalization on the limited range of sizes n in the dataset, so we limit their number of parameters and use smaller training set. We do not expect our simple renormalization process to make a significant difference on large-scale benchmarks with state-of-the-art models [13], but this is a pointer in an interesting direction to be explored in the future. In particular, this type of normalization may be useful in real-world scenarii where the test graphs are far larger than the labelled training graphs.
5 Conclusion
On large random graphs, the manner in which GNNs label nodes can be modelled by functions. The analysis of the resulting function spaces is still in its infancy, and of very different nature to the studies of graph-tasks, both discrete [54] or in the limit [36]. In this paper, we clarified significantly the nature of the space of functions well-approximated by GNNs on large-graphs, showing that it can be defined by a few extension rules within the space of square-integrable functions. We then showed the usefulness of Positional Encodings by analyzing two popular examples, established new universality results, as
9

---

Dataset
Eigenvectors w/ norm.
Distance-cncoding w/o norm.
w/o norm.
w/ norm.
Synthetic
68.61
65.59
67.31
62.49
Synthetic (out-of-dist)
67.87
62.51
66.80
63.33
CiteSeer-subgrapal
49.45
49.43
48.99
37.09
INDB-BINARY [55] (graph-classif.)
67.80
66.10
71.10
63.95
COLLAB [55] (graph-classif.)
73.74
74.77
75.65
75.02
Table I: Test accuracy for GNNs with different PEs, with or without renormalization by the graph size n. Results for 5-fold cross-vass validaaii averaged over 3 experiments.
well as some concentration inequalities of independent interest. Our theory hinted at some process for consistency across graphs of different sizes that can help generalization in practice.
This paper, which in large part consisted in properly defining the objects of interest, is without doubt only first step in their analysis. Future studies might look at specific settings and derive useful properties of the space Fs. more powerful PEs, a better understanding of their limitations, or more realistic models for node features. In particular, better connection with the existing WL-based theory for finite small graphs, and associated "powerful" architectures, is major path for future work.
Acknowledgments
The authors acknowledge the fundings of ANR GraVa ANR-18-CF:40-005 and ANR GrandMa ANR- 21-CH23-0006.
References
[1] J. Arjona Martinez, O. Cerri, M. Spiropulu, R. Vlimant, and M. Pierini. Pileup mitigation at the Large Hadron Collider with graph neural networks. European Physical Journal Plus, 134(7):1-12, 2019.
[2] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph Convolution for Semi- Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization. pages 1-30, 2021.
[3] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of Graph Convolutions in Multi-layer Networks. pages 1-31, 2022.
[4] Giorgos Bouritsas, Stefanos Zafeiriou, Fabrizio Frasca, and Michael M. Bronstein. Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. arXiv:2006.09252, 2020.
[5] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometrie Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. 2021.
[6] Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. pages 1-43, 2021.
[7] Sourav Chatterjec. Matrix estimation by Universal Singular Value Thresholding, Annals of Statistics, 43(1):177-214, 2015.
[8] Matthieu Cordonnier, Nicolas Keriven, Nicolas Tremblay, and Samuel Vaiter. Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphs. pages 1-39, 2023.
[9] Harry Crane. Probabilistic Foundations of Statistical Network Analysis. Chapman & Hall, 2018.
[10] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Advances in Neural Information and Processing Systems (NIPS), 2016.
10

---

[11] Xin Luna Dong, Xiang He, Andrey Kan, Xian Li, Yan Liang, Jun Ma. Yifan Ethan Xu, Chenwei Zhang. Tong Zhao, Gabriel Blanco Saldana, Saurabh Deshpande, Alexandre Michetti Manduca, Jay Ren, Surender Pal Singh, Fan Xiao, Haw Shiuan Chang, Giannis Karamanolakis, Yuning Mao, Yaqing Wang. Christos Faloutsos, Andrew McCallum, and Jiawei Han. Auto Self-Driving Knowledge Collection for Products of Thousands of Types. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 2724-2734, 2020.
[12] Vijay Prakash Dwivedi and Xavier Bresson. A Generalization of Transformer Networks to Graphs. 2020.
[13] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph Neural Networks with Learnable Structural and Positional Representations. In ICLR, pages 1-25, 2022.
[14] Gerald B. Folland. Real Analysis. Wiley-Interscience, 1999.
[15] Kimon Fountoulakis, Dake He, Silvio Lattanzi, Bryan Perozzi, Anton Tsitsulin, and Shenghao Yang. On Classification Thresholds for Graph Attention with Edge Features. pages 1-37, 2022.
[16] Alex Fout, Basir Shariat, Jonathon Byrd, and Asa Bun-Hur. Protein Interface Prediction using Graph Convolutional Networks. In Neural Information Processing Systems (NeurIPS), pages 6512-6521, 2017.
[17] Michelle Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, 99(12):7821 7826, 2002.
[18] Anna Goldenberg, Alice X. Zheng, Stephen E. Fienberg, and Edoardo M. Airoldi. A survey of statistical network models. Foundations and Trends in Machine Learning, 2(2):129-233 2009.
[19] Desmond J Higham, Marija Rašajski, and Nataša Pržulj. Fitting a geometric graph to a protein- protein interaction network. Bioinformatics, 24(8): 1093-9999 2008
[20] Peter D. Hoff, Adrian E. Raftery, and Mark S. Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association, 97(460): 2002.
[21] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer Feedforward Networks are Universal Approximators. Neural Networks, 2:359-366 366, 1989.
[22] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open Graph Benchmark: Datasets for Machine Learning on Graphs. Neural Information Processing Systems (NeurIPS), (NeurIPS):1-34, 2020.
[23] Nicolas Keriven. Not too little, not too much: theoretical analysis of graph (over)smoothing. Advances in Neural Information Processing Systems (NeurIPS), 2022.
[24] Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. Convergence and Stability of Graph Convolu- tional Networks on Large Random Graphs. In Advances in Neural Information and Processing Systems (NeurIPS), pages 1-26, 2020.
[25] Nicolas Keriven, Alberto Bietti, and Samuel Vaiter. On the Universality of Graph Neural Networks on Large Random Graphs. In Advances in Neural Information and Processing Systems (NeurIPS), 2021.
[26] Nicolas Keriven and Gabriel Peyré. Universal Invariant and Equivariant Graph Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), pages 1-19, 2019.
[27] M. Kuperman and G. Abramson. Small world effect in an epidemiological model. Physical Review Letters, 96(13):2909-2913 2001.
[28] Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. Annals of Statistics, 43(1):215-255 2015.
11

---

[29] Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22:1-41, 2021.
[30] Pan Li. Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 2020-Decem(1)) (1)11299 2020.
[31] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and Basis Invariant Networks for Spectral Graph Representation Learning, pages 1-42, 2022.
[32] Andreas Loukas. What graph neural networks cannot learn: depth width. In ICLR, 2020.
[33]
László Lovász. Large networks and graph limits. Colloquium Publications, 60:487, 2012.
[34] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. In Advances in Neural Information Processing Systems (NeurlPS), pages 1-12, 2019.
[35] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the Universality of Invariant Networks. In International Conference on Machine Learning (ICML), 2019.
[36] Sohir Maskey, Yunseok Lee, Ron Levie, and Gitta Kutyniok. Generalization Analysis of Message Passing Neural Networks on Large Random Graphs. pages 1-63, 2022.
[37] Eli A Meirom, Haggai Maron, Shie Mamnor, and Gal Chechik. How to Stop Epidemics: Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networks. pages 1-23, 2020.
[38] Pál András Papp and Roger Wattenhofer. A Theoretical Comparison of Graph Neural Network Extensions. 2022.
[39] Lorenzo Pellis, Frank Ball, Shweta Bansal, Ken Fames, Thomas House, Valerie Isham, and Pieter Trapman. Eight challenges for network epidemic models. Epidemics, 10:58-62, 2015.
[40] Allan Pinkus. Approximation theory of the MLP model neural networks. Acta Numerica, 14-19,,, 1999.
[41] Martin Ringsquandl, Houssem Sellami, Marcel Hildebrandt, Dagmar Beyer, Sylwia Henselmeyer, Sebastian Weber, and Mitchell Joblin. Power to the Relational Inductive Bias; Graph Neural Networks in Electrical Power Grids, volume 1. Association for Computing Machinery, 2021.
[42] Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Journal of Machine Learning Research, 1 11:905-9900 934,,994,222 2010.
[43] Luana Ruiz, Luiz F. O. Chamon, and Alejandro Ribeiro. Graphon Signal Processing. S0t:::00330000300 pages 1-13, 2020.
[44] Luana Ruiz, Luiz F.O. Chamon, and Alejandro Ribeiro. Graphon neural networks and the trans- ferability of graph neural networks. In Advances in Neural Information and Processing Systems (NeurIPS), 2020.
[45] Alvaro Sanchez-Gonzaler Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia. Graph networks as learnable physics engines for inference and control. 1rxiv:1806.01242. 2018
[46] Aliaksei Sandryhaila and José MF Moura. Discrete signal processing on graphs. IEEE Trans. Sig. Proc., 61(7):1644-100 1656, 2013.
[47] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. SIAM International Conference on Data Mining, SDM 202/, pages 333-341, 2021.
[48] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, E. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
12

---

[49] Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with message-paste passiing. In Advances in Neural Information and Processing Systems (NeurIPS), 2020.
[50] Jizhe Wang, Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, and Dik Lun Lee. Billion-scale commodity embedding for E-commerce recommendation alibaba. Proceedings of the ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 239-848, 2018.
[51] B Yu Weisfeiler and A A Leman. The Reduction of a Graph to Canonical Form and the Algebra Which Appears Therein. Nii, 2(9):12-16, 1968.
[52] Felix Wu, Tianyi Zhang, Amauri Holanda de Souza, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. 36th International Conference on Machine Learning, JCML 2019, 2019-June: 1884-11894 2019.
[53] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip Yu. Comprehensive Survey Graph Neural Networks. IEEE Transactions Neural Networks and Learning Systems, pages 1-21, 2020.
[54] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How Powerful are Graph Neural Networks? In ICLR, pages 1-15, 2019.
[55] Pinar Yanardag and S. V.N. Vishwanathan. Deep Graph Kernels, pages 1365-1374, 2015.
[56] Jiaxuan You, Rex Ying, and Jure Leskovee. Position-awasd aware Graph Neural Networks. 2019.
[57] Yu, T. Wang. and J. Samworth. A useful variant of the Davis-Kahan theorem for statisticians. Biometrika, 102(2):315-333, 2015.
[58] Manzil Zaheer, Satwik Kottur, Siamak Ravanbhakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets. Advances in Neural Information Processing Systems, 2017- Decem(i):339223300) 2017.
13

---

A Proofs of Sec. 3
A.1 Proof of Prop. 1
Denote G the distribution of (X, with (w, P) and Go for (wa, Note that if X, A ~ Go. then ((X), 1~ ~ G, and recall that = (AA only depends on A.
Consider f FFNN (B, w, P). E > 0. and 0, (()) such that Pg ((xx(S))))(() Lx exfll E) O.
Then, denoting by (XX) (0(x1,.... ((x)))
Pg. (1 @o o o)) - 1x (f a の) I > =E) = -P& Bo((. ( (ox) ((0) - 60(x)5 (()
3 E))
MSE
=Ps
( @0( ixf
5) + 0
MSE
which shows that f E FONN Wep Pb) and one inclusion. The other inclusion is immediate by doing the same reasoning for oi
A.2
Proof of Prop. 2
Define W = [ws /n] the Gram matrix. Using Theorem 9, for both our examples we have
||S W
0
Since ||W|| < supn.y Ias (z. y) is bounded, it shows that [|S|] is bounded with probability going to 1. Let f E L3 and any E > 0. Since continuous functions are dense in equare-integrabbe functions on compact spaces (see e.g. [14, See. 8.21), let E (,, such that |lf gll & E. We have
1
( 2z)g((,) - / ws ug( x)(x))
[ - -
Sgl
n2
n2
Σ
ws( 2,((22))((z)) - ==s(:=)9(=)dP(())
T2-00
where have used Lemma 8 and the fact that g is bounded.
Finally,
| -
1xxxxxxXS[lln SXSSS < I|Sexs - W x /llASE + |[exx/ Wix M + +||Wexg Sxllll + 11exSg LxSffl
Using || < ||||||| B| and the LLN, and the fact that I| [|W]]. ||S|| are bounded, with
probability going to 1,
||Stx] - Lx MSE
< ||S - || + ||]]] [|xx - 9) ||MSE
+ | 4x S0llMME + S1x f)
< || - I/ + [W]] 2112و + 0 |S|| llg Allza S 8
which, since was chosen arbitrarily, concludes the proof.
A.3 Proof of Theorem
The proof uses intermediate results. Recall the definition of GNNs: given input node features (0)
R gnxde do
z = (2(--1))f-1) + S2(0-110((-)) + +I,(0(0)T) e Bande S 2(0) = 2(4-1)g(4-1) (6((
14

---

We can define continuous equivalent of GNNs, called c-GNNs in the literature [24], using the operator S. Given f(0) E Låg
f = ( g((=))) + (T + +b(0) E Lae s (S (0(4-1)) T (((--1) +b(l)
Then, under our assumption on the operators (S, S), discrete GNNs converge to continuous GNNs, Lemma 1. Suppose Assumption I holds. For all f E L3 and 0,
[ lx 1o MSE
0
Proof. Writing (
ixf and f(o) = f. we show by recursion on the layers that
|| 1x (
p
MSE
2-000
For 8= 0, we have exactly have,
|| - 1x 1x |IME 0. Assuming the convergence holds for t 1, we
12(0-1xx - -xx((0
( (21e-100 + (2 + In(((0)))
=
MSE
-xp((06 (( f(1-1) + (0( T f + b(1))
11(0-1)+b(()
zee 110-1)0 + (2((-11 0(((
(ex j(c 1) 00 (1) + (1x (1x (1 )(( MSE
-1108--1) b|| + | [SS|) ((6-1) ix (e-1))
11|
-Six - (xx MSE
+ +S((
using the Lipschitz property of in the first line, and ||A < || | after. The first term converges O by recursion hypothesis since |S|] is bounded with probability going and the second converges to 0 by Assumption 1. This concludes the proof.
Lemma 2. Given a base space B C L2, denote by Fc(B) C L3 the following space of all functions f of the form:
f(0) E
f(e+1) g6 (2) f(0 + o6 sf(0
where (
( g Crip (deet) pdets)
f f()( E L2a
(12)
for all k. L.d, Then Fc(B3 is dense in (B).
Proof. By definition, F. C Fs since its contruction uses only rules that leave Fs stable. Conversely, F. satisfies all the rules of stability of Fs so by minimality Fs C Fc.
Lemma (Universality in T.2), Let f E T and g E CLip RP), all e > 0, there exists an MLP MMPP that uses ReLU, with two hidden layers, such that
9 o f -MPP fll E
(13)
Proof. Denote by bg the Lipschitz constant of Let Ci. = (-kk k)4, and X = fx E X f(() E C.)),
and & - Sx, [l]( dP(x). We have & positive and increasing, and limg & |15 Define k
such that Ek. > 1 1l200) such that Sxq. [lf(z))1 dP(x) 1190011
e²
15

---

Since Ck2 is compact, by the universality theorem [21, 40], there is an MLP fy such that SuPyECk, [g(v) - ( & E. Moreover, using the property of ReLU, it is easy to see that the following function can be implemented by an MLP:
for t & - kis
1 T (1)
for - & 1 k2 for t > ks
Then, we define fMPP MIP o for where fn is applied coordinate wise. As a result, we have ke outside. Then, we have
STLP (v) f (y) Ck. and || (
119 - Sgup $1122 / 1100 f(x) suP ff(x)] dP(x)
(g0
M.PP o s(x)]] d())){dP(xx))
+ +2(
1lg S|ر aP(x)+ + /
||
S|l ap(x))
xxx
X
For the first term, since on Xr, we have f(x) E Ck., we use the approximation property and we have
/ Xxe 1 f(x) - faue o f(x)ll dP(x) < E²
For the second term, since [ > dh? > 1 on X we have
S l190 f1I dP(x) < / lgo |
x(0)| /l()) + / IdP(x)
N
2 + 11 (lo(0)))))
/ Xx_ |1SI dP(x) & 2=²
And for the third term, given the property of the built MLP.
|| o /|] dP(x) < / dh(dP(x)
XE.
<
|1 < <
N
which concludes the proof.
Lemma 4. Let f E FcB). For all >> 0, there exists O and f(0) B such that
Le (()) - E
(14)
Proof. Let f E Fe(B) be constructed as (12). Denote by in the Lipschitz constant of g Crip( (Red,,RRee))) Let 6 >
(
We build the following continuous GNN: f(() f0) and
f((+1) - PMLP
F(9 +
MLP 000
sf(()
(S (()) (()) = F(L))
for well-chosen MLPs. We design them by increasing layer indices: assuming the MLPs up layer f are choosen (i.e. f(() chosen), we use Lemma and choose g(0) (which depends on g(0) ((e-1) then) such that
(0) MLP) g
000 o ((0)
+ +1(
MLPP))
FF)
20
(0)
<
12
g=
L-1
[I
+ I
||||]
16

---

Then we get
| - f((+1)
<
91' o p( - of" o 50)
(0)
+
92 o
(2)
(9_
Mi o
S
L2
12
12
91
(1) p(() (6) f(0
+
92
(9)
( s
+ t
12
L 10) 2 |S||] f(0) 7())
+el0
112
Hence by a simple recursion and since
f()) = f(o) we have
L-1 $
II 9=2+1
L. + 10 [SSI)
800) 500) E
by our choice of e()), which concludes the proof.
Proof of Theorem 1. We start with the inclusion Fy S FONN. Let f E FB) and E > 0. By Lemma 2, there is fc FB) constructed as (12) such that [If - fell & e/3, and we use the weak law of
large numbers to obtain that P( - Ill e E/3) - 0.. By Lemma 4, there exists @ such n-tco that (S, (()) Ze & E//3. Again by the LLN, we have that (S, fe) MSE
E/ e/3) + 0. Finally, by Lemma 1), we also have
P (1) (|0o(S (x0o(S, MSE
3 = 0.
Using triangular inequality, we have
4olex - -cxf -xfl MSE
< { - (x -xx+0
+ +||x(B0(((0) - -fo) -fo)lMAsE
MSE
+ +1|ex (fe - f)
We conclude by a union bound, and f E (B)) For the reverse inclusion, let f FB))(B). By hypothesis, for all m E N, there are 0 E f B such that
P (xx() ixf
> 1/m)
0
MSE
2
By Lemma 1,
P (((oo(S.xx((0) - 1x $o f0)
3 1/m)
0
MSE
n
By the LLN,
(s. P -(])
|| (s (() (
> 1/m) + 0
-
MSE
12
Hence, b a union bound and triangular inequality, we obtain the deterministic bound ||s- (S |l & 3/m. Since f E (B) and Fs(()) closed, by taking m + we have f E FB(
A.4 Proof of Prop. 3
Remark that Fs(B) n CLi R) is in fact a subalgebra of CLip (X', R). Indeed it is a vector space,
and moreover it is stable by multiplication: for f.g E (B) n CLip (X,, (). by stability of Fs (B)) by composition with continuous functions we have that x + [fx), 0j. + 10, (()] are in FB()), then (x++ + [f(x), xx)))) (B( by linearity (that is, Js is stable by concatenation), and since (2, y) ay is continuous, (x + (()g(()) E (B) n (X, (2,, R).
Hence (B) n (2, R) is subalgebra of CLip (X', R)) and since it separates points by hypothesis, by the
theorem [21] it is dense in CLip (X, R) for the uniform norm, and a fortiori in LiCC (XY ( by concatenation. Since continuous functions are dense in iquare-integrable functions [14, See. 8.2] and the 1,2 norm is dominated by the uniform norm, results that FB(B) is dense in L22 and even Fs (B) L because it is closed.
17

---

B Proof of Sec. 4
We introduce general notations that are valid all throughout this section of appendix. this appendix, we will only assume:
Assumption 2. We have the following.
1. bounded kernel ws, and either us p.s.d. or X finite;
2. the operator SJ = ( ()))());
3. the Gram matrix = [ws (T,, /n)/ graph matrix S such that in probability.
|S W|l +
(15)
These assumptions are verified for both adjacency and normalized Laplacian: in the first case, we take ws w, and [IA/(a,,)) - W|| 0 by Theorem 9, and in the second, take ws(x, v) v vd(x)d(w)) which is bounded by our assumptions
w(a
and p.s.d. when w is itself p.s.d., and we have indeed -T- W|| - 0 by Theorem 9. We will also use the following property.
Lemma 5. FPg is closed.
Proof. Let fm be a sequence in FPF that converges to a J E 1 for some Remark that J' E L2 for all m big enough. Let & > 0, and m be such that [ - fllea & 8/2. By the law of large numbers, for any fixed m, ||<x probability, such that ([Ilex(fm f) 2 e/2)
f)MMSS converges to [ fll,a & e/2 almost surely and a fortiori in
0. By definition, there is E I' such that
n-
(S) 2)
1x Fm MISE 3 e/2) - O. Hence, by union bound
P(I]PF,, 7) 1x MSE 7 E) < PS, 2) Lx LxfmllMss > =/2) + P(] fl 3 E/2) 0
and therefore f E FPE.
B.1 Proof of Prop. 4
We have
2 1x
< S1x
1x
+ ||Su||MSE
MSE
MSE
The first term goes to 0 by Prop. 2. For the second term, using
|ABIE < |||||| Bl| we have
|Sv|
< ||
W |P/|
||
The first term goes to in probability since ||||| MSE is bounded with probability going 1 and |S - WIl + 0 for our examples of graph operators. For the second term, we have
2
da Σ
||
wg (1,
ug (3,,)))
n1
n
Using Lemma 8 with the iid variable yy (zj, pze) and Ews( (., x ) = 0 since v and X are indepen- dent, we obtain
Ve,
Σ ws (-, 133
0
which concludes the proof.
18

---

B.2 Eigenvectors positional encodings: SignNet
In this whole section, the number of eigenvectors q is fixed, and we assume that Ai..... Ag are pairwise distinct. We first start by generic results that allows to go from the graph matrix S to the Gram matrix.
Lemma (Intermediate result for SignNet). Suppose that Assumption 2 holds, that Ai.... g+1 are distinct, and that
min ||VVTU!."
(xu,
MSE + |
P 0.
(16)
1 9 of (1,-11
Then the result of Theorem 2 holds.
Proof. Let f E Feig. written as (9). By Assumption 2, ||S W|| + 0. By Kato's inequality, we have that sup; A X.W + 0, and by hypothesis, the eigenvalues of W converge to those of Given the hypotheses on the eigenvalues of S, with probability going to 1 the g+ 1 first eigenvalues of S have single multiplicities. When is the case, according Davis-Kahan theorem (Theorem 8), for all 1..... 9 there is E [-1, } such that
max Iasu
W 11
+
(17)
which, combined with our hypotheses, yields
max
min
||5/reg exu,
P 0. MSE x-+00
(18)
For i = 1,.... q, let fi : R +
R. be continuous functions and > O. By Lemma 3, there is MMPPP such
that (AMIP fi) u 22 & e2 Then, call L; the (uniform) Lipschitz constant of fMI on R. We have
IPE - -x(((..) o u $1
Sig MSE = MMPP ) (Vnu )1= - (x[(Xxff us R=1 MSE
|| [
(UQMPMPP ( == 1x xx[ MIPP)
MLP) 11
MSE
+ [[Q (MP)
MLP) Si - cx (x((())) o u Ji-1
MSE
(MPP)M))) ( -1 (Q. MLP) U MSE
|1xx(Q MLP) us -x (Q.ii) un
MSE
2 Σ min || AALALL(SsVVi (SiV 1x
MLP
u S
+E(11-1)
MSE
+ 2 ( S1) o u II
The first term goes to 0 in probability by what precedes, while for the second
Σ ||x (
fi) o I
Ello - fi) o u 11 E//2
which proves that FFig FPE, and thus FEig FPF since FPE closed by Lemma 5. For the reverse inclusion, let f FPE. By hypothesis, for all m E N, there 7 E T, such that (I Lx fllsSE > 1/m)
12+000
By what precedes, if we write PE,, (Q, (VTuu, ) we have
PE., 1x [Q
PMLP)
0
MSE 22020
By the LLN,
P (( - - [(Q
o u g 1 MSE - /|ʃ - [(Q. u 819 1 > 1/m) +
Hence, by union bound and triangular incquality, we obtain the deterministic bound || [Q MLP) u - La 3/m. Since [(QPMMPP)) u$19 1 Frgg. have f E Frgg
We must now prove the hypothesis of Lemma 6. This is done separately for p.s.d. kernel and SBM.
19

---

B.2.1 Positive semidefinite kernels
In this subsection, we assume that ws is p.s.d. The following result adapted from [42].
Theorem (Adapted from [42]). Suppose that Assumption 2 holds, that Xi.... ... g are painwise distinct, and that ws is p.s.d. (Ex, b). Then:
max min i= il.... sE(1,-1]
| W - exu, ! + +1!! 25 + 0
(19)
in probability.
Proaf. Denote by H the RKHS associated with wgg and by Tx H - H the kernel integral operator. Then, it is known [42] that the spectrum of S and T'x are the same (up to O's), and the eigenfunctions (normalized in H) U, of TH corresponding to positive cigenvalues satisfy:
(z) ()saa,)
for E supp(P) else
(x)
(20)
Note that 28 > >...> 2 9+1
by hypothesis. Following [42], we know that
sup AM W
$ +
(21)
in probability, and that in particular, with probability going to one AM > 0 for all = L,..., q. Assuming
this is satisfied for all i, we denote by D!!' Vn E, "s( zy) E H. Then, using the fact that
the eigenvalues of have single multiplicities, the proof of Theorem 12 in [42] tells us that for all
Q.
m
Σ
Σ
H + E
Σ ja
(0
02 u, /H 0
(22)
1=1 13
in probability. Since these are all nonnegative quantities, all partial sums go O. The first part (the term for j m) tells that Eigm+1 (nS, u. / -> 0, and the second part applied m 1 (again the term with j = m) gives us E (o, um H
W. + 0. Hence for all m I.....g. ..
W m H
+0 0
(23)
Since (uf)) and (x.) are orthonormal basis of H. we have Ilol .w2 (uS mm + 1. By the reproducing property
=1= E, (eg, )
)o and thus
S
W (
Vm H
Vn
Σ
= U U (xx)
AW
vn
Σ
u Mo
u ul (xx)
2
By the convergence W we obtain that Va (ut" .(xus)
in probability, and choosing the
sign of W such that (u. xxxs)) ) > O. we get vo (u ex ex
- 1. Finally
1 V|Vnu - 1x u 11 = (1- Ta (u (uw ,xxu)) + ||
MSE
by the LLN, | 1 1 in probability, which concludes the proof.
By combining Theorem 5 with Lemma 6, conclude the proof in the p.s.d. case.
20

---

B.2.2 SBM
Variants of the following result appear under (sometimes significantly) different formulations in the literature.
Theorem 6. Suppose that Assumption 2 holds, that Xς. ..... Aa are pairwise distinct, and that X is
finite (Ex. a). Then:
max
|sS/TUU -xu, (2,-11)
min
MSE | 1
P 0. 12000
(24)
Proof. In the SBM case, functions are represented by vectors of size K. The operator S acts as: Sf = C (tiag(Ps)) where C' d [ws (k, E)k Therefore C ddig((:: Px)u, = un for = 1,..., K. Note that u is orthonormal in (P). that is, (u,) diag( Px) = and (u²) diag( Pk PK) = 0. In particular,
(diagl/PE)ut is an eigenvalueeeeigenvetor pair of the symmetric matrix Op det. diag(v (oaggvPP)CC CC (Va)). Denoting by uf def. diag( (ong(v/a)uu Pu)uu we have Cp Σx (f
Since the space X' is finite, each 2, is equal to a community label & h < K. Define O (0, L///n/// the community matrix, as:
O vn
for all Iicn
(25)
(. = 0
otherwise
Then the Gram matrix is
W AC0T
(26)
Also note that θT diag(P), where Ps 1 E; 1A= + Ps almost surely by the LLN. Note that,
n2
when interpreting u as a function on X = [1...., K}, we have vnOuş = uxu..
Defining Pp O (iiag(1/VPP. have
W OpCrOp = (pp( = ExS una
where v, Oupf" Ou satisfies
|0 = ( diag (P))( +, uT (Tt)T diag Pk) +
(27)
in probability. Hence the v; are almost orthonormal but not exactly. Define their orthonormalization:
Tj = U1, Vi 2, K, ū, U3 Σ (o uy)u, and =
(28)
T
such that ",,..., KKK E R" are orthonormal and u E Span(vi u.). We define G Eis X5 uuu,, whose eigenvalues are the A and eigenvectors u. By the properties of v; we have supigien ||u uill + O, so [W] - O. Hence by Kato's inequality we have supigign AA I + 0, and since the A 1+1 have unique multiplicity, again by Davis- Kahan theorem for all í = 1..... a have min.e(-1.1)) ||su," - =u,ll O, and by consequence min.e(-1.1) | v nu,
MSE O. We conclude by recalling that /nu, vnluf ixu..
As before, we conclude by combining Theorem 6 with Lemma 6.
B.3 Distance-based encodings
Again, we start with an intermediate result, assuming some convergence in Frobenius norm that we will then show for our cases of interest.
Lemma (Intermediate result for Distance-based encodings). Suppose that Assumption holds, and that:
Ve > 0, 3,,,,, W > +
(29)
Then the result of Theorem 3 holds.
21

---

Proof. Let f E CLip (0, R*) and E > 0. By the universality theorem [40], let fh such that || /o & on [0. 1/9. Since it is MLP, fu is uniformly Lipschitz R2, call L its Lipschitz constant. Then, /22 such that
W 3 e/L) + S[
(30)
For convenience, define M ey ey.... ..... (.,))..)s,,,))) E Raxx M," [Weg...., WW%)...,WWWellJJJ.
(x)........ (x)) E [0. 1|9.
We write
PE - -x / F(U()))dP(T)
ISSE
MLP n N..M," M2Tx)
MMPP (n M
11
MSE
MLP (n. (o-M 1x / (J(s))))))(
x f fmt (J(,)))dP(xz) ix F(J(.x))dP(())
(31)
MSE
The third term in (31) is bounded by || fl1s2 E. The second term in (31) is
MLP (n. (n.M,) ix / (
MSE
MLP (n. (M.M,) 1
MLP (AL (J(,
n
MSE
MLP (J({)())))))) - f A (MI (J(
+
xx
MSSE
L
sup x,a²
Σ
ws( I., (Fi xizz) ws ws(ai, (2)
11
8=1
MLP (J(,(()))))))))))))))
- /
-f
MLP (M
where we have used the Lipschitz property of MMLP and supremum over æi, for the first term. The first term converges in probability by Lemma 9, while the second goes to using the boundedness of 4MP [0, 1) by Lemma 8.
22

---

Finally, using Schwartz inequality, the first term in (31) is bounded by
MLP (n.M) - p (nad,"))
n
ISE
/ALP (M
12
MSE
Σ
1MM (M (n()) )a.)) - Sa (M(MM" )o.))
72
> (AM (r. )e.: - (a.
L
< 1. Σ 11st w < I. Σ
Σ
s lf [|w]--11)
1|5
115T - Wll S 8²8
with probability going to 1. using (30) and the fact that [|]]|p is bounded, and thus ||S ll as well with probability going to 1. Gathering everything, f E FPE, which concludes the proof.
We then prove this property for both p.s.d. kernel and SBM. The following Theorem is similar to Theorem 4, but under Assumption 2, which is true for ex. and 2.
Theorem 7 (Theorem 4 reformulated). Suppose that Assumption 2 holds. For both p.s.d. kernel (Ex. b) or finite X (Ex. for all = > 0, there is an MLP filter S., -h (S) such that
Ve > 0, 3y, PP[ISS WIIp > E) 0
(32)
Proof. Note that S is trace-class (both w p.s.d. or the SBM case), such that E, |2$1 < xc. In particular, | = o(L/Vi). In the p.s.d. case, all X are nonnegative. We define Xg > 0 and the support T T= (il
S Aa}
i) Eiero (2 < E/2, which can be satisfied since S is trace class and therefore Hilbert-Schmidt
ii) / supiero |사 E/4, which can be satisfied since | o(1/vi)
iii) infieT.jere x s > O, which can be satisfied by choosing A in a gap in the spectrum of S, since all eigenvalues but 0 have finite multiplicities.
We will first start by approximating W with an ideal filtered matrix S = -iErr (M.)). We define = Eier AW u (u,)T. We decompose
s w|: F < <I -Bs-cl1, -
For the first term, since this matrix of rank at most /T), we have
$ c|| < 2 $ G|
We further decompose
$ < $ S + || W| + !|W G||
The second term is bounded by Theorem 9, we have || - W || + 0 in probability.
The third term is bounded by Kato inequality
sup X ieT
< sup X TET
+ sup A 1
23

---

the last term goes to O in probability.
The first term is bounded by supseTe Xp, and by Kato's inequality
sup X < sup A + I|S W||
iE
iere
which is combination of both previous cases.
At the end of the day, with probability going to 1,
$ - < 22 sup X; (1) < <E/2+
iET
Finally, we have
| - W = IAm 2
Σ (A$)² Eam (a9)*>Za>~- 25)2 TE
1ET
The first term is bounded by e/2, the second goes to O in probability: in the p.s.d. case, this is a result of [42], by an application of Hoeffding's inequality in the Hilbert space of Hilbert-Schmidt operators in an RKHS; in the SBM case, there is a finite number of non-zero eigenvalues for both W and S that converge to each other and the result follows.
Now
we need to bound
S, - S
for a well chosen MLP. Define (tr,Jr)
> 0 and Ā l +25
arg min JEr= S - 111,
Note that we have
T=
(il
À + 2T} and To {il {25
< x 2 Define the following fMPP, R +R
MMIP (A) = X+T
(0 - X x+ - p (A - - x) + (A-
(33)
2T
+ ー (p (-x - x+ -
7)) pp -
(34)
27
where p is ReLU. This is a continuous piecewise linear function that equal on (-o0,-X- on -, x - r]. and X on [A +,,++o0)
Recall that with probability going to 1, we have sup; A X & T. so in particular, for all e T we have |X > - r and for all E T we have | < X - T. In that case, the MLP filtering exactly
the ideal filtering and h(S)= S, which concludes the proof.
B.4 Proof of Prop. 5
The case of FDist was proven in [25, Theorem 4]. For FFig, we consider the SBM (ex. a) with adjacency matrix (ex. 1) and
-1/4 112 1/A)
C
P (1/3,2/3)
1/4
3/8)
We have S1 (1/3,1/3) therefore F1) contains only constant functions. Moreover, of (1, 1),2/
From the orthogonality equation (u=) diag P)u = 0 get (u²) )1 2( 22 Hence it is possible
( choose of such that f((us) h1) + f(-(u5))) * f((u5) )2) + f( (1(s(()) 22) thus FEig contains a non-constant
function, which concludes the proof.
B.5 Proof of Prop. 6
Consider the SBM case X' [1, (l,...,K] with K even and p = lx/K. Adopting the notations of the section above, we have S = C' diag Cp = diag( PP)) (iigg(VP)) = -EK, with uf" = diag(V/P)))) orthonormal (in Euclidean k).
For Frig. we consider the case where
X 2 > A 0 for i > 3
(uf) )5 = V 2/K
if is even otherwise,
0
if is even
(u
0
C
otherwise,
24

---

where C' is constant such that | = 1. Consider eigenvectors PEs with 1. The space Feig contains all the function g of the form
= s((x)) [[: + ((-())):.
for any f. By construction of uf. these functions have the property of being 2-periodic: for all i, 9: = 9:+2- Now, Fs (F(ig) contains e.g. the following function
S1 KCp1 A²
(((TTu))) u + 2 u )2
This function is not 2- 2-periodic: on odd, we have (u * (ug )e42 and therefore 9i * 91+2, which concludes the proof.
For Diu. taking again g 1, we consider K 4 and Cor = Cıo 1, and Cke = 0 otherwise. The space Fis contains all the function of the form
1
g K f(C)1
where f is applied element-wise on C. With this choice, for any f we have 9s 94 = f(0). However, the space Fs (FDia) contains the function
1 h K2 C((C)
Here we have h3 f(oN( + 7/10) and h4 f(0)², which can be made unequal. Hence h & FDist
8
which concludes the proof.
Universality
Here we recall the universality results of [25], that were derived for architecture called Structured GNN, the case of non-random edges. this paper, these results are valid for the distance-encoded PEs (10), through Theorem 3, our definition of Fis (11). The results in [25] basically proves that Fs (FDis) satisfies the hypotheses of Prop. 3. We recall them here without proof. The following results are valid for adjacency matrix (ex. 1), distance-encoding PE (10), and SBM (ex. a) p.s.d. kernel (ex. b), with other additional hypotheses in each cases.
SBM: if X is finite, C = [kr ()) is invertible, and P is such that for all {-1,0,1),
P = 0 implies O, then Fs (FrR) = L2.
Additive kernel: if w(2, v) = v(u(z) + u(3)) with u, v that are continuous and injective, then
Fs(FrE) L3
Unidimensional radial kernel: if X [-1,1] w(z v) v(x v/) with continuous injective v, and P is symmetric (that is, P((a,b) = P([-b, -al) for all intervals), then Fs(Fre) L3 n S(X) where S are symmetric functions. If P is not symmetric, then Fs(Fre) = L.
Spherical kernels: X' = gd-1 the d-dimensional sphere, w(x, y) = v(x y) with continu- injective v. and P has density p w.r.t. the uniform distribution the sphere such that: the unique decomposition p(z) = Σx20 N(d.k) (z)) where Yk.5 are spherical harmonics is such that x + [E M(d.)) ax Yk.3 (z)] is injective (see [25] and references therein), then Fs(Fr)) = L2
D Technical or third-parts results
The following Lemma can proved number of ways.
Lemma 8 (Lemma 4 in [24]). Let X be compact metric space, and y measurable space. Consider bivariate measurable function
X y + E that is uniformly bounded, and continuous in the first variable. Let .1...., ........ Ya be drawn i.i.d from a distribution P on Y. Then
n Σ n(..)))
n( n(-.))PP())
12000
25

---

We extend the previous results to polynomials of the kernel. Lemma For any bounded, continuous kernel ws, we have for all > 1:
sup a,
Σ
ws( Iiy (ws Fig) ...
(2)
p, 0
p
(35)
7
Proof. We prove by induction. For lt 1, we have
Σ us (z, (x))ss( - ws((, 2d)P(v))))
P
0
(36)
x,z' EX
by applying Lemma 8 on N' x H, and since us is continuous on compact domain and therefore bounded and Lipschitz.
Then, assuming the property for k 1, we write
sup a,,'
n
Σ
ws(
Iz, )uss( Fig) fig)... ws( 1g6tt1g.)(e
sup w. Ex
1 Σ
ws x1))
Σ
wg (b2) ... ws ( x') (8* (2
n
62.....2
82r) (11s)) - -f wu((1, &
us (x. Fi, (S*h Σ
sup x
The first part converge to using the boundedness ws and the recursive hypothesis, while the second converges to 0 using again Lemma 8.
Theorem (Simplified Davis-Kahan, see [57]). Let A, E IRdxd be symmetric with eigenvalues X and ) ordered by decreasing order and eigenvector ue ûgg Take p and assume that d min(Ap-1 Ap. Ap Apt1)= > O. Then there exists s E {-1,1} } such that
A A
|| upll &
(37)
Theorem 9. Denote W = [w(z,, 2t)///ss W
and L(M) DM MDM with
{(d(s))d((s)))
DM diag(MI)
or Z (logn)) then
A
W
0.
(38)
Moreover, ifd(z) duan > 0 and an > C(logn)/ /n where C' is constant that depends on w, then
(((A) W|
P 0.
(39)
2-000
Proof. The first result is due to Lei and Rinaldo [28].
For the second result, have from [24, Theorem 6] that
[L(A) L(W)I] + 0
(40)
Then, according to Lemma we have that
d
w xx)
0
(41)
n
n=+00
26

---

and in particular with probability going to one d:W del. (Dw)s > dmin/ 0 for all i.
Denoting by D = diag(d(z:)). and noticing that W - WD and ||]| 1, we have
W L(W)l = | WDD 1 Dw W WDW $
D 3 Di
1
max
Umin
v dmii
Vd(aa)
d
d(x;) d.
max
v Omin
Vd(a,)d /
<d(xx;) + )
d
wc (x))
p
d² min
n-000
which concludes the proof.
27


Reviews:
[{"review_id": "mQYTCJOewh", "reviewer": "Reviewer_2UtV", "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. ", "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.\n- 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?\n- Could you intuitively explain why SBM and PSD kernel assumptions are necessary in Section 4?\n", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "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.\n- The technical statements seem correct to me.\n- Presentation in the beginning of the paper is fine, but section 4 is rather dense.\n- The problem considered is quite natural, if one is interested this kind of limiting behaviour of graph learning methods.\n- Recent, state-of-the-art PE approaches are considered.\n- 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.\n- 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.\n- 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.\n- 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.\n- The results in section 4 seem to depend on SBM or PSD kernels. It is unclear why this assumption is made. \n\n\n**minor**\nl6. certains functions -> certain", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and insightful review.\n\n- **Practical insight**: as mentioned by the reviewer, on large (random) graphs, in the infinite-node limit, node-task GNNs approach functions. Approximation results indicate *which labelling functions the GNN is able to approximate*, e.g., will it be able to distinguish communities in an SBM in the limit with high probability -- something that is not directly reflected by *discrete* approximation power results. It is however true that, as of now, the *limitations* of GNNs have been less clearly identified than in the discrete case, where combinatorial reasonings *à la* WL yields obvious limitations. Hence the scarcity, for now, of ``better'' models built in the limit, but also the interest of a better understanding of these objects.\n\n- **Connection with finite case**: Indeed, thank you for pointing this out. Some (as of now, limited) connections can be made with results in the discrete case: for instance, in the absence of PEs, with constant input, GNNs will have a constant output on degree-regular graphs, just as in the limit they will have a constant output function on random graphs with constant degree function. Beyond this, it seems than GNNs on large graphs are less ``limited'' than in the discrete case (see first point), but on the other hand universality results are only known with PEs. A better connection with discrete analyses is definitely a major avenue for future work. As suggested, we will add a discussion in the final version.\n\n- **SBM/psd assumptions**: These assumptions are not necessary *per say*, but sufficient. Indeed, the strong convergence of PEs such as eigenvectors does not seem to be true for a generic kernel $W$ (to the best of our knowledge, this is still an open question), and some mild regularity assumptions on $W$ are generally made. We focused on two representative, very popular models of random graphs, for which the proofs are reasonable for all our examples of PEs and graph operators. On a case-by-case basis, other models may of course be studied in the future. We will add a clarifying sentence in the final version.\n\n- **Other remarks**: We will improve the connection with [25], as well as the readability of the theorems in Sec. 4."}, {"review_id": "m4OVNN2eb8", "reviewer": "Reviewer_gCL6", "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.", "questions": "* Please address the above concerns.\n\n* 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? \n\n* I would also expect some more detailed experiments with respect to the benefit of the proposed normalization.", "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.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "* The paper is very well written and was very enjoyable to read.\n\n* The analysis is fairly novel and studies GNNs with powerful features.\n\n* 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.\n\n* 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.\n\n* The analysis is mainly based on random graphs, which admit certain regularities, that do not allow concrete conclusions about the representation power of GNNs.\n\n* 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.\"\n\nHow is the size of the graph related to graph isomorphism? What do the authors mean by small-scale graphs, medium or large graphs?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and insightful review.\n\n- **Practical implementation**: the main goal of this paper is to better understand the theoretical properties of existing GNNs on large graphs, and we focus on classical implementations that use the adjacency matrix or normalized Laplacian, as well as classical PEs. We offer some (limited) recommendations of practical implementation: the small remark on normalization good practices, as well as the use of normalized Laplacian instead of adjacency matrix, since the latter requires additional knowledge of the sparsity level $\\alpha_n$. We also prove universality results for some choices of PEs. However we agree that leveraging this type of analysis to develop truly different, more ``powerful'' GNNs (in the infinite-node limit) remains a major avenue for future work.\n\n- **Message-Passing and PEs**: the eigenstructures are able to reconstruct the graph only when considering the full $n$ eigenvectors/values, which is not the case here (we cut at some finite $q$). The full spectrum is actually impossible in our analysis, since we let $n$ go to infinity. Our analysis does not really suggest that message-passing is not ``useful'', as it extends the space of available functions from $F_{PE} $ to $F_S(F_{PE})$: indeed, Prop. 6 even proves the contrary in some cases. The characterizations of these spaces is case-dependent however, and we agree that there are still many open questions on a case-by-case basis. We will add a clarifying sentence.\n\n- **Random graphs**: random graphs do indeed admit certain regularities. However they are, as of now, one of the only tools available to statistically model \"large\" graphs, which is necessary when we want to model large-scale phenomenon such as communities or manifold structure. The resulting analysis is indeed very different from the usual discrete combinatorial one (which may be what the reviewer meant by \"concrete conclusions about the representation power of GNNs\"?), but we see them as complementary analyses rather than competing ones.\n\n- **Isomorphism**: thank you for pointing this out, we will clarify the sentence in the final version. What we meant is the following: while distinguishing (non-)isomorphic graphs are important for small or medium graphs like molecules, large graphs have only a very, very small chance of being exactly isomorphic. However, they may present different characteristics for learning (eg communities), and it is these characteristics that we aim to modellize with random graphs. For instance, two large graphs drawn from an SBM model have an near-zero probability of being isomorphic, but they have the same number of communities, so it is interesting to characterize the fact that a GNN will indeed be able to approach a function that correctly labels the nodes in the limit. We precisely describe the space of such functions in this paper.\n\n- **More experiments**: as discussed in the paper, the proposed normalization is a by-product of our analysis that we do not expect to bring significant performance boost to state-of-the-art large architectures (that are able to learn such normalization within the range of graph sizes in the training set), but is an interesting fact nonetheless. We have however performed more experiments on synthetic data and the CiteSeer node classification dataset (modified to have several graphs of different sizes), described in the global rebuttal.\n\nWe hope to have addressed your concerns as stated in the Limitations section, and that you will be able to raise the proposed score."}, {"review_id": "5TPvfEpyBa", "reviewer": "Reviewer_mk3D", "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.\n", "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.\n -   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.\n  -  It would be beneficial to reference related works on universality results and concentration inequality, perhaps in the appendix.\n- 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. \n- Can the authors test the importance of normalizing PEs in node-level tasks? (see e.g. PPI datasets or [1])\n\n## Minor Points:\n\n   -  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.\n   -  Out of interest: Are there any accessible condition under which $F_S(F_{\\mathrm{PE}}) \\subsetneq F_{S'}({F}_{{\\mathrm{PE'}}})$ holds?\n   -  There is a typo in line 594. It should be $\\nu$ instead of $\\varepsilon$.\n\n## Conclusion:\n\nThis 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.\n\n[1] Dwivedi, Vijay Prakash, et al. \"Long range graph benchmark.\" Advances in Neural Information Processing Systems 35 (2022): 22326-22340.", "limitations": "yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-    The authors give a new framework for investigating the expressivity of GNNs in node-level tasks.\n-    They give mathematical results and proofs, enhancing the scientific rigor of the study.\n-    The paper is well-written.\n-    Beyond the GNN result, the concentration and universality results offer interesting and novel insights that enrich the paper.\n", "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.\n-    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.\n-    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.\n-    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.\n-    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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful and review.\n\n- **On related work and overstatement**: thank you for pointing this out, we will add more related work on universality (and other places where we feel it might be necessary). You are correct in pointing out that the normalization ``good practices'' are by-product of our analysis, that we do not expect to really improve large-scale state-of-the art models. We have performed more experiments in the global rebuttal, and will better frame the contribution.\n\n- **MPNN architecture**: apologies if our formulation is misleading, we indeed treat GNNs that use graph shift operators like the adjacency (Ex. 1) or normalized Laplacian (ex. 2), and did not claim to treat generic aggregation function. We will clarify this. You are also correct in noting that the normalization of the adjacency matrix $A/(\\alpha_n n)$, necessary for convergence, is generally not used in practice. This is why the normalized Laplacian (or other degree-based normalization) is generally preferred. \n\n- **On operators notations**: we mainly treat two cases, the adjacency matrix (indeed globally normalized) in Example 1 and the symmetric normalized Laplacian in Example 2. These are quite different operators, that give rise to different operators $\\mathbf{S}$ in the continuous case (see Ex. 1 and 2 in the paper). All of our results are valid for both, and some results more generally for any operators under some convergence assumption (Assumption 1). Hence we used generic notations.\n\n- **On experiments**: indeed, since our primary goal was to simply illustrate the normalization trick (on small models, with no claim to improve over state-of-the-art large models), we needed datasets with many graphs of very different sizes, which are far more common for graph-level tasks. We have however added three experiments for node-classification tasks, found in the global rebuttal.\n\n- **WL test**: What we meant is the following: while distinguishing (non-)isomorphic graphs are important for small or medium graphs like molecules (with dozens or hundreds of nodes, say), very large graphs have a very, very small chance of being exactly isomorphic, but they may present different characteristics for learning. For instance, two large graphs drawn from an SBM model have an exponentially small probability of being isomorphic, but they have the same number of communities, so it is interesting to characterize the fact that a GNN will indeed be able to approach a function that correctly labels the nodes in the limit. We precisely describe the space of such functions in this paper, as functions on the space of latent variables $\\mathcal{X}$. We use the Stone-Weierstrass theorem in a different manner than graph-level discrete analyses: the space under consideration is not the space of discrete graphs (up to isomorphism), but the space of latent variables.\n\n- **SignNet and function change**: the SignNet architecture is a variant for *eigenvector-based PEs*, which are (to our knowledge) a quite common choice. SignNet resolves the sign ambiguity of eigenvectors, which is usually done by choosing signs randomly, an additional level of randomness that we felt would significantly complexify our analysis and notations. We will clarify the relation between the two and add more references to eigenvectors-based PEs. We are not entirely sure what function $f$ the reviewer is referring to? The input function to the GNN can be anything (degrees, etc.), as long as our convergence assumptions are satisfied. We chose two representative examples of PEs. We will clarify this point in the final version.\n\n- **More experiments**: Thank you for the suggestions. We found the PPI dataset, one of the only node-classif dataset to include several graphs of different size, to be quite peculiar: it seems almost only the nodes features are used, and PEs are usually ignored by trained models. LRGB datasets are difficult tasks, and most vanilla GNNs fail on them. We however added three experiments on node-classification, described in the global rebuttal.\n\n- **Reference and minor points**: thank you for the suggestions, we will add more references on universality and PEs. We will correct the typos and try to clarify our definitions. To our knowledge, the subset property must be checked on a case-by-case basis, but a more generic condition is an interesting path for future work, thank you."}, {"review_id": "GmOQLsZmxB", "reviewer": "Reviewer_rtyh", "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:\n\n- 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;\n- Analyzing two representative examples of PEs based on eigenvectors and distance-encoding, and extending previous universality results to more general random graph models;\n- Proposing some normalization tricks to ensure convergence and consistency of PEs across different graph sizes, and demonstrating their effectiveness on synthetic and real data;\n- Proving some new concentration inequalities for filtered random matrices that are of independent interest.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We are delighted that you found our paper to be well-written and organized, with detailed technical proofs in the appendix."}, {"review_id": "JLV44YVTNm", "reviewer": "Reviewer_2T44", "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.", "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.", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "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.\n\n2. 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.\n    - 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.\n    - 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.\n\n3. 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.\n\n2. 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.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and insightful review. We agree with the reviewer's opinion that many questions remain on the interpretability of the function spaces defined in this work, beyond the results presented in this paper. We will complete the outlook section if space permits. We also agree that random graph models are imperfect, however they remain the main tool available to describe large graphs in the limit. We note that, beyond SBMs, random graphs using for instance a Gaussian kernel are quite flexible (eg, in terms of degree function), especially since the distribution of latent variables $P$ is not constrained. To our knowledge, not much is known concerning other models such as the preferential attachment model, and convergence properties of operators such as the graph Laplacian are still open. The analysis is likely to be very different in this case, and this is an important path for future work."}, {"review_id": "39L2S1wF7F", "reviewer": "Reviewer_Jsrn", "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.", "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.\n2. 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.  \n3. Theorem 2: What happens in the case of basis-invariance (and with non-distinct eigenvalues)?\n4. 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?", "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?", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "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.\n* Uses (and apparently requires) significant novel techniques / bounds to achieve the results (e.g., USVT estimators, pp) of independent interest.\n* Strong extension of [25]", "weaknesses": "\n\n\nSometimes the paper is not fully self-contained, e.g.:\n* the proper definition of graph shift matrices.\n* more intuition on latent position random graphs and graphons.\n* \"special properties\" of ReLU. Why don't you just say what properties you mean, Lipschitzness etc.\n\n\nMinor:\n* 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.\n* 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).\n* sometimes you write \"latent position random graphs\" and sometimes \"latent position*s* random graphs\"\n* the claim \"as medium or large graphs are never isomorphic\" is a bit of an exaggeration. Perhaps say \"seldom\" instead of never.\n* 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?\n* 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.  \n\nTypo:\n* Line 232 \"that sum to 1\" --> \"that sums to 1\"\n* Line 59 \"no not\" --> \"do not\"\n\n\n[Morris,  et al., 2019] \"Weisfeiler and leman go neural: Higher-order graph neural networks.\" AAAI 2019", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your very detailed review.\n\n**Questions:**\n\n1. In our analysis (Example 1) the adjacency matrix is normalized: $A/(\\alpha_n n)$, which guarantees that its eigenvalues are bounded with high probability. It requires however the knowledge (or approximate knowledge) of the ``sparsity level'' $\\alpha_n$, which is not the case for the normalized Laplacian, where the normalization is automatic.\n\n2. For the first theorem, our results are valid as long as the convergence in Assumption 1 is satisfied, this can indeed include weighted edges depending on the choice. We will add the reference. For the results on PEs, we did the analysis for two representative examples, but they could also be extended on a case-by-case basis.\n\n3. In this case, the convergence is known for so-called ``spectral projection'' operators, rather than individual eigenvectors (see eg Rosasco et al. [42]). For PEs in practice, the SignNet paper includes an architecture called BasisNet, which is used to handle eigenvalues with multiplicities by being basis-invariant (instead of sign-invariant). The expression is however quite more complex, and the convergence in the limit seems significantly more involved. We will add it to future work.\n\n4. Indeed, the *limitations* of continuous-GNNs in the limit are not well understood, even without PEs. A simple example is that of constant-degree function, for which the output of continuous-GNNs with constant input remains constant (just as GNNs fail on degree-regular graphs). Some examples in [25] (which we generalize with PEs, see our Appendix C) include some simple symmetry analysis, but many questions remain open. We will focus on these limitations in future work.\n\n**Limitations:**\n\nWe will add a more extensive introduction on latent positions random graphs in the available space. Such random graphs, generalizing SBMs and random geometric graphs, have been initially introduced for the analysis of social networks, but are also used for protein interaction networks, physical networks (road, computers), and many other examples. While very intuitive in their interpretation (latent variables can be made very concrete: user preferences, spatial positions, etc.), their drawbacks include mostly a limited capability to model degree power-laws or complex substructures. They remain however the most popular tool to model large graphs, with an active literature.\n\n**Other points/minor points**: \n- Thank you for pointing this out, we will fix the references, and add the suggested references\n- We will fix the terminology and notations as suggested"}]

Author rebuttal:
Dear reviewers,

We thank you for your valuable comments. We are glad to see that see that our paper is well-received and considered as *well-written* (gCL6, mk3D, rtyh, 2T44). The novelty is highlighted by several of you (gCL6, mk3D, 2T44, Jsrn). 

A common concern of the referees is the practical insights provided by our manuscript and the connection with existing discrete analyses. We detail below additional experiments, and address the latter point, and other comments, in each individual rebuttal.

We provide three node-classification experiments (in addition to IMDB-BINARY and COLLAB). Several referees emphasized that our analysis focused on node classification tasks, but that we implemented our numerical illustrations of the normalization trick on graph classification datasets. As mentioned in the paper, to illustrate the effect of normalization, the dataset needs to include several graphs, and the vast majority of datasets for node classification have only one large graph. One of the only classical node-classif dataset with several graphs, namely PPI, is challenging for our purpose: most vanilla GCNs learn to ignore PEs entirely and use almost exclusively node features. In the absence of node features, they generally fail to learn. Hence, we used a synthetic dataset (using sklearn's ``make_classification`` to create the $x_i$ then a Gaussian kernel $W$ to create the random graph, a strategy also adopted by the Pytorch Geometric library), and another "real-world" dataset created by *extracting many subgraphs* from a node-classification dataset that had originally only one large graph, such as Citeseer. Additionally, for synthetic data we test the effect of having test graphs significantly larger than training graphs, which we denote by OOD (out-of-distribution), which emphasize the importance of proper normalization for generalization.

Note that moreover, we forgot to mention in the paper that for all experiments (including IMDB-BINARY and COLLAB), we do not use the original node features, but only the PEs computed from the graph structure, to emphasize the effect of the PEs. This detail will be added.

These rebuttal experiments may be further refined for the final version.

|                   | Eigen w/norm | Eigen w/o norm | Dist w/norm | Dist w/o norm |
|-------------------|--------------|----------------|-------------|---------------|
| Synthetic         | 68.61        | 65.59          | 67.31       | 62.49         |
| Synthetic OOD     | 67.87        | 62.51          | 66.80           | 63.33             |
| Citeseer-subgraph | 49.45        | 49.43          | 48.99       | 37.09         |

Meta-review: The paper studies and generalizes known results regarding the expressive power of equivariant GNNs on random graphs, including special attention to the role of positional encoding in that setup. All reviewers liked the paper and supported acceptance. 

Some criticism was raised about the relation of this paper and its results to practical GNN architectures and also the relation to previous expressive power results on smaller graphs. I believe that the paper would greatly benefit from a deeper discussion of these relations.
Decision: Accept (poster)