On the Universality of Graph Neural Networks on Large Random Graphs
Authors: Nicolas Keriven
Alberto Bietti
Samuel Vaiter
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural network
random graph
universality

Abstract: We study the approximation power of Graph Neural Networks (GNNs) on latent position random graphs. In the large graph limit, GNNs are known to converge to certain ``continuous'' models known as c-GNNs, which directly enables a study of their approximation power on random graph models. In the absence of input node features however, just as GNNs are limited by the Weisfeiler-Lehman isomorphism test, c-GNNs will be severely limited on simple random graph models. For instance, they will fail to distinguish the communities of a well-separated Stochastic Block Model (SBM) with constant degree function. Thus, we consider recently proposed architectures that augment GNNs with unique node identifiers, referred to as Structural GNNs here (SGNNs). We study the convergence of SGNNs to their continuous counterpart (c-SGNNs) in the large random graph limit, under new conditions on the node identifiers. We then show that c-SGNNs are strictly more powerful than c-GNNs in the continuous limit, and prove their universality on several random graph models of interest, including most SBMs and a large class of random geometric graphs. Our results cover both permutation-invariant and permutation-equivariant architectures.

On the Universality of Graph Neural Networks on Large Random Graphs
Nicolas Keriven CNRS, GIPSA-lab, Grenoble, France nicolas. keriven@cnrs.fr
Alberto Bietti
NYU Center for Data Science, New York, USA alberto. bietti@nyu. edu
Samuel Vaiter CNRS, LJAD, Nice, France samuel, wwiterrcnrs......... fr
Abstract
We study the approximation power of Graph Neural Networks (GNNs) on latent position random graphs. In the large graph limit, GNNs are known to converge to certain "continuous" models known as c-GNNs, which directly enables study their approximation power on random graph models. In the absence of input node features however, just GNNs are limited by the Weisfeiler-Lehme test, c-GNNs will be severely limited on simple random graph models. For instance, they will fail distinguish the communities of a well-separated Stochastic Block Model (SBM) with constant degree function. Thus, we consider recently proposed architectures that augment GNNs with unique node identifiers, referred as Structural GNNs here (SGNNs). We study the convergence of SGNNs to their continuous counterpart (c-SGNNs)
isomorphism
the large random graph limit, under new conditions on the node identifiers. We then show that c-SGNNs strictly more powerful than c-GNNs in the continuous limit, and prove their universality on several random graph models of interest, including most SBMs and large class random geometric graphs. Our results cover both permutation-invarite and commutation-equvarriin architectures.
Introduction
Graph Neural Networks (GNNs) are deep architectures defined over graph data that have gareredd lot of attention in recent years. They represent the state-of-the-ar in many graph Machine Learning (graph ML) problems, and have been successfully applicd to e.g. node clustering M. semi-supervised learning [24], quantum chemistry [7], and so on. See
18
for reviews.
As the universality of Multi-Layers Perceptrons (MLP) is one of the foundational theorems in deep learning - that is, any continuous function can be approximated arbitrarily well by an MLP in the last few years the approximation power of GNNs has been a topic of great interest. In the absence of special node features, i.e. when one has only access to graph structure, the crux of the problem has been proven to be the capacity of GNNs to solve the graph isomorphism problem, that is, deciding when two graphs are permutations of each other or not (a difficult problem for which no polynomial algorithm is known [4)). Indeed, this property is directly linked to the approximation power of GNNs [8] 3. In this light, the landmark paper 45 proves that classical GNNs are at best as powerful the famous Weisfeiler-Lehmal (WL) test [43] for graph isomorphism. Since then, several works 45 31 have derived new architectures, for instance involving high-order tensors [I], with improved discriminative power equivalent to "higher-order variants of the WL test. In another line works, several recent papers have advocated the use unique node identifiers (28 27], with
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

strategies to preserve the Passing (SMP) in 41 (see Sec. 2.3). We call these models Structural GNN (SGNN) here. SGNNs have been proved to be strictly more powerful than the WI. test in 41 and even universal on graphs with bounded degrees, however for powerful layers that cannot be implemented in practice.
of GNNs coined Structural Message
When the size of the graphs grows, the notion of graph isomorphism becomes somewhat moot: large graphs might share properties (number of well-connected communities, and so on) but are never isomorphic to each other. GNNs have nevertheless proven successful in identifying their large-scale structures, e.g. for node clustering [7]. Several papers have therefore used tools from random graph theory and graphons to study the behavior of GNNs in the large-gran graph limit. In [22] 38), GNNs are shown to converge to limiting "continuous" architectures (coined c- G-NNss (22)) A few works have studied the discriminative power of c- c-GNNs on graphons [30], however, analogously to how the WL test will fail on regular graphs, c-GNNs are severely limited on graph models with almost-constant degree function (Fig. D and the question is still largely open.
Contribution and outline. In this paper, we study the convergence of SGNNs on large ran- dom graphs towards "c-SGNNs", and analyze the approximation power of c-GNNs and c- SGNNs. After some preliminary results in Sec. 22 we study the convergence of SGNNs in Sec 3 In Sec. 4 and S we show that c-SGNNs are strictly more powerful than e- GNNs in both permutation-invarian and equiv- ariant case. We then prove the universality of c-SGNNs several popular models of ran- dom graphs, including Stochastic Block Models (SBMs) and radial kernels. For instance, show in Sec. 5.3 that c-SGNNs can perfectly identify the communities of most SBMs, in- cluding some for which any c-GNN provably fails (Fig. D. The code for the numerical illus- trations is available at hhttps:// //gi titb.....ccm com/ nkeriven/random. www.rranddogggg-h-aaee graph-gmm gann
GNN, Train
GNN, Test
SGNN, Train
SGNN, Test
Illustration of Prop. (Sec. 5.3 On an SBM with constant degree function, a GNN (top) might overfit the training set, but converges to a constant c- GNN. On the contrary, there exists a c-SGNN (bottom) that perfectly separates the communities. Details can be found in App. E
Figure 1:
Related work. The approximation power of GNNs (on finite graphs) has been a topic of great interest in recent years, and we do not attempt to make an exhaustive list of all results here. The landmark paper [45] showed that permutation-invarit
GNNs were at best as powerful as the WL test, and later models 31 g 16] were constructed to be as powerful as higher-order WL tests. using for instance higher-order tensors (3I. The link between
the graph isomorphism problem and function approximation was made in [8] 23 and extended in but involve tensors of unbounded order. When graphs are equipped with unique node identifiers, the approximation power of GNNs can be iotpuutatioi-invaaaaneeeeuiieiee
(3). Some architectures were proven to be universal (32 23
significantly improved if relaxing
28
27
10 or assuming that
it holds only in expectation with respect to additional sources of randomness 3 D. On the contrary,
as we will see in Sec. 2.3 the SGNN architecture proposed in [41 is inspired by the same ideas but still satisfies exact pormmtation-mvarrinn/eeeirrarrni powerful than the WL test [4), and even universal on graphs with bounded degrees when allowing powerful layers. To our knowledge, the approximation power of SGNNs as they are implemented in practice is still open. We treat of their continuous limit in this paper.
As mentioned above, SGNNs are more
Fewer results can be found in the large-graph limit. Beyond the graph-isomorphism paradigm, authors have studied the capacity of GNNs to count graph substructures 66 [3] or identify various graph properties [1] 46). Several works have studied the large-graphl limit of GNNs [8 30 26 22]. assuming random graph or graphon models. The degree function has been proven to be a crucial element for the discriminative power of c- c-GNNs, and they will not be able to distinguish graphons with close degree functions (30]. Here we show how c-SGNNs allow to overcome these limitations, and provide the first universality theorems for (SYGNNs in the continuous limit. Finally, we note that universal architectures exist on measures
44). which can be seen as limits of point clouds, but, the graph case may be significantly harder to study.
similar to the discrete case
[48 32 23

---

2 Preliminaries
In this section, we group notations random graphs and GNNNs present the convergence result of [22] slightly adapted to our context, and introduce the SGNNs of [41]. An undirected graph G with n nodes is represented by symmetric adjacency matrix A E R It is isomorphic all graphs with adjacency matrices a Ao for any permutation matrix о E {0. 1 Matrix rows (resp. columns) are denoted by Ai,: (resp. A...). The norm ||-Il is the operator norm for matrices and Euclidean norm for vectors. For a compact metric space X. we denote by C(X', I)) the space of bounded continuous functions X' + IR, equipped with Ilffl = sup, [f(r)] For a multivariate function f E C(X, R fi denotes its ith coordinate, and | (2, 3/2
2.1 Random graph model
We consider "latent position" random graphs, which include several popular models such as SBMs or graphons [29]. The nodes are associated with unobserved latent random variables x; drawn i..dd For the edges, we will examine two cases: "ideal" one with deterministic weighted edges, and more "realistic" one where the edges are randomly drawn independently. In the literature, the latter is often considered an idealized framework to study the behavior of various algorithms 42 37).
Let (X, mx) be a compact metric space that is not a singleton, and assume that the e-covering numben of X' scale as O (s-dx) ) for some dimension dx. We denote by W the set of symmetric bivariate functions in C(X x X, [0, 1J) that are Lw-Lisschitz each variable, and by P the set of probability distributions over X' equipped with the total variation norm I|- A graph with n nodes
generated according to a random graph model (W, P) E W x
as follows:
31
Tpp
Lid ~
P.
agj =
a,, "0r'\emmmlll(.,, W (1)) random edges case
W (Iz, zz)
deterministic edges case
where an is the sparsity level of the graph in the random edges case, which we assume to be known for simplicity. When on 1, the graph is said to be dense, when an ~ the graph sparse, and when a log the graph is relatively sparse. Note that we have normalized the Bernoulli edges by 1 1/a,, such that Eag-- W (Zx,, xzy) conditionally on 24, Zzz. When X' is finite, the model is called an SBM (see Sec. 4.3
Like finite graphs, random graph models can be isomorphic to another (2 29]. In this paper, similar to (22) we consider that, for any bijection y X - X, the model (W, P) is isomorphic to (W vp_ PP). where (2, y) = W ((p(x), (vv)) and fq is the pushforward P (the distribution of f(X)). Indeed, it is easy to see that both produce exactly the same distribution over graphs.
2.2 Graph Neural Networks
Following 22 12 in this paper we consider the so-called "spectral" version of GNNs, which include several message-passing models for certain aggregation functions. We consider polynomial filters defined as h(4) = Σx A* for a matrix or operator A. In practice, the order of the filters is always finite, but our results are valid for infinite-order filters (assuming that the sum always converges for simplicity). We consider any activation function p E E which satisfies p(0) 0 and (p(x) p(y)
< I - y| for which the universality theorem of MLPs applies [35), e.g. ReLU.
Spectral GNNs are defined by successive filtering of a graph signal. Given an input signal 2 Ian at each layer & = O,...................... M- - -1:
(E+1))
Σ i-1
(L (6) + ((((),n) 1n) E R ;=
(1)
((8) A are trainable graph filters, 699) E R are trainable additive biases and where 49 (A) = E. ijk
is applied pointwise. We note the normalization n that will be necessary for convergence. GNNs exist two main versions: so-called "permutation-invarian"" GNNs t output a single vector for the entire graph, while commutation-equivrraaa GNNs &o output a graph signal:
T (Z(0)) ()) E gaxd
Tb 22())) (1 E. k(:) E Rdont
(2)
the number of balls of radius required cover X
3

---

where g Rd + R is an MLP applied row-wise in the equivariant case. By construction, such GNNs are indeed equivariant or invariant node permutation: for all permutation matrices a, we have T Po (o 0 (Z) and $ Ao (0) 4 (2))).
In 22 the authors show that, in the large random graphs limit, GNNs converge the following "continuous" models (coined c-GNNs), which propagate functions over the latent space f()) E C(X, Rdc) instead of graph signals. Given input function f()) E Rd)):
Continuous GNNs.
f((+1) = Ei= b (Tw,P)), + +
where Tw.p is the operator Tw = ( (()))d(()())))) Then similar to equivariant/invarinnt versions of c-GNNs are defined as:
(2 the permutation-
(w: - f(M)
(w.p(r(0) = -9 (S (M)(()))(())
Remark that (w))(((0)) is itself a function in C(X, R while (w.r(f()) Roott is vector. Moreover, by virtue of the polynomial filters, the four architectures A AA, @w.P, P, &w.P have the exact same set of parameters. Like in the discrete case, one can prove that c-GNN are equivariant or invariant to isomorphisms of random graph models [22]: for all bijection sp X' + X, we have
WW..yg (f o :p) = @ o op and & W...,, (f a p) = @w.p(f).
Let us now turn convergence of GNNs to C-GNNs. The following result is adapted from 22 While the outputs of permutation-invariaat GNNs and c-GNNs are vectors in Rdout that can be directly compared, the output graph signal of a permutation-equivanee sampling of the output function of the corresponding C-GNN: for graph signal Z Rnxdd function f :: - Id and X = {a:)/=1, we define the (square root of the) mean-square error as MSEx (2, = - Zi fff=-fxx))ll ((xx))1)) The proof of Theorem with all multiplicative constants is given in App. A.I Recall that dx the "dimension" of X.
GNN compared with
Theorem 1. Assume G is drawn from (W, P) and has latent variables X. PiX,, 0.
In the deterministic edges case: with probability 1 - for all z
C.M MSEx ( (Z())), fw: & MSEX (2()) (2 (0) + Rn(
for some constant C and R1(n) = O (Vixx + log((//))//z)
In the random edges case: assume that the sparsity level is an 2 n Inlln There a constant
Cp such that, with probability 1 1-p ". all (
MSEx (4 Pw.p(f < C- (Z(x((()) f(0)) + R1(n) + R2(n)
(4)
where (2(n)= O OC,l v. In the permutation-invarint case: The exact same results holdfor [b5 -
instead of the MSE on the left-hand-side, with an added error term Ra(n) = O
(olo)-- (Vlog(1/p)//
By the theorem above, GNN converges to its continuous counterpart if 2 is (close to) sampling of a function f()) at the latent variables. This is directly assumed in [22). In the present paper however, we do not suppose that input node features are available. While several strategies have been proposed in the literature, popular baseline is to simply take constant input (0) 1n (which, by
multiplication by A on the first layer, is also equivalent to inputing the degrees as in 7 for instance). In this case, there is convergence to a c- C-GNN with f()) = 1. For simplicity in the rest of the paper we drop the notation "(1)" and write &. A = (1,)), Φw, p @w. and so on. It is known that GNNs are limited on regular graphs: for permutation- -nnvariinn GNNs, the WL. test cannot distinguish regular graphs of the same order, and for permutation-equivarre
GNNs, 4 (1..) is constant over the nodes. Similarly for C-GNN, the degree function (z))))( is key in the discriminative power of c-GNNs [30], and if is constant, then @w P (11) is a constant function (see Fig. D.
'The authors in 22 proved this for the normalized Laplacian, which allows bypassing the knowledge of o... Here use the adjacency matrix, for our later results approximation power.

---

2.3 SGNN: GNN with unique node identifiers
To remedy the absence of imput node features, in 41 the authors propose an architecture with unique node identifiers while still respecting permutation invariance//quiiariaace More precisely, they first choose an arbitrary ordering of the nodes q = I..... n, apply GNN to each one-hot vector Eq [0. ........ , 0J. and restore equivariance permutation by final pooling. For later purpose of convergence, we generalize this strategy to any collection Eg (A4) E Raxdo that satisfies:
Eg(oAo)) obE (g)
(5)
where by an abuse of notation (q) designates the permutation function applied to index q. For instance, it can be any filtering of one-hot vector Eg (A) h(A)eg. After the GNN A pooling is applicd to restore equivariance, then a second GNN 4 that either invariant or equivariant:
V A = D'A [, 2 (E, E Buxd
V D En 2 (E₂ E R (6)
In 41 these architectures, called SMPs, are interpreted as doing message message-passing over matrices, and can more general pooling and aggregation functions. In sense, what we call SGNN are "ppctrrll" versions of SMP, but are essentially the same idea. It is not difficult to see that SGNNs satisfy: V VOAOT
VVA a and Vo V.
3 Convergence of SGNNs on large random graphs
In this section, we extend Theorem[jo SGNNs. To define continuous SGNNs, we consider bivariate input function 7w,P X' X + R such that: the mapping (W, P) + Tw.P is continuous" for any (W, P), nw.p is Cy,-bounded and -,psIiipschiz in each variable, and similar to (5) is respects the following:
TW. 1
nw.p(p((x), ((((())))())))))
for all bijections yf X - X. For instance, f/r.r W any filter nw,r(a,,)) (x)) satisfy these conditions. A c-SGNN is then defined as:
Vw.P- 'ww.P (J (0w.>(w..((:)))dPP
for the equivariant case, or similarly WW.P = W..P (ʃ (ww. x)).d((())))())) for the invariant case. Again, using the properties of c-GNNs, is easy to see that c-SGNNs respect random graphs isomorphism: V W p = Ww.P o yp and V Woiggt Ap = W.... We are now ready to extend Theorem D The proof and multiplicative constants
App. A.2
Theorem 2. Assume G is drawn from PW, with latent variables X. Fix p. 0.
In the deterministic edges case: with probability 1- p
MSEx AA T Nw.r) & C' sup MSEx MSE (EG( + (m)
for some constant C" and R (n) = O ( (vidx+log() log(L/p))/m)
In the random edges case: assume that the sparsity level is Z n llogn. n. There is a constant
Cn such that, with probability
n-
MSEx A L w. & C' sup MSEx (E,( (.) R2
(2(
(10)
where = (C,/
In the vermutation-invatte case: The exact same results hold for | Ww.Pll instead of the MSE, with added error term (y(n) O (vlog(1/p)/n)
Hence, we obtain convergence when the input signal E, (A) is close to being sampling of function T at Tg. The choice of input signal/function is therefore crucial. Let us examine a few strategics.
for the norm al + Ily W
5

---

One-hot vectors. If one chooses one-hot vectors Eg = Eq as in [11, then we can see that the SGNN converges to the continuous architecture with input Tw.P 0, since MSEx (e,. 0) 0. Since Ww.r is nothing more than a traditional c-GNN ww.r with constant input in that case, this is not a satisfying choice in terms of approximation power.
One-hop filtering. If we choose "filter" eg once and take (A) Aeg, the natural continuous equivalent is 7/,.P = W. Such a strategy only works for deterministic edges: indeed,
MSEx (Acg, W(: xg)) (n- Eizi W(a;, (Fg)))
-
with deterministic edges
Vn-nIE, Varlasg) a- with random edges, w.h.p.
where the last line comes from simple application of Hoeffding's 's inequality. Hence, in the case of random edges, the MSE does not vanish and typically diverges for non-dense graphs (Fig 2
Two-hop filtering. We can therefore choose to filter twice and consider TW.p(x, y) = Tw.p(W(( (x)),, that is, (A)) /ne We have the following result.
Proposition 1. In the random edges case, with probability 1- p. have for all q:
MSE
20
(A'S.Tw.P T...I..eWW..,yll 2o
Vlog(n/p) On Gavn
One-hop
MSEx
Two-hop
Theary
In the deterministic edges case, the rate is O (1/vn).
Convergence guaranteed when Vlogn/ (ax, n - O, which is stronger than relative sparsity. The difference between one- hop and two-hop filtering is illustrated in Fig. Other strategies may also be examined, and we leave this for future work. For instance, based on Theorem 5 in App. D a strategy based on the eigenvectors of A could lead to convergence even in the relatively sparse case. In the rest of the paper, we explicitly write when our results are valid for one- two-hop filtering.
Figure 2: Difference between the out- puts of some V in the random edges case with
n 1/3 and in the deter- ministic edges case, which converges to Ww,r. Convergence is observed for twa-hop filtering only. The theoretical rate of Prop. [ is slightly pessimistic. Details can be found in App. F
Approximation power: permutation-invariant case
In this section. we study the approximation power of continuous architectures in the permutation- invariant case. We seek to characterize the functions W x P + E. that can be well-approximated by c-GNN or c-SGNN. We derive a generic criterion for universality arising from the Stone-Weieet Weierstrasss theorem, before proving that c-SGNNs are indeed strictly more powerful than c-GNNs. Finally, we give several examples of models for which c-SGNNs are universal.
4.1 Generic result with Stone-Weierstee theorem
A classical tool to prove universality of neural nets in the literature is the Weier-Waesss theorem 20 (33, which states that an algebra of functions that separates points on compact space is dense in the set of continuous functions. Although NNs are typically not algebra since they not closed by multiplication, one of the original proofs of universality for MLPs solves this by a clever trick D A direct application results in the following proposition.
20 which we recall in Lemma iin App.
Proposition 2. Let M Wx
be a compact subset W P. c-SGNNs (resp. c-GNNs) are dense in C(M, R) if and only if: for all (W, P) # (W",P) E M, there is a c-SGNN (resp. a c-GNN) such that V w. o Vw., pr (resp. Pw. P.P... + (.r...)
Note that, by construction of the permutation-invariant C-(S)GNNs, universality is only possible when M does not contain two isomorphic versions of the same random graph model. Equivalently, M may be larger set quotiented by random graph isomorphism.

---

4.2 c-SGNNs are more powerful than c-GNNS
SGNNSs were proven to be strictly more powerful than the WL test, and therefore than GNNs, in In the theorem below, we check that this striet inclusion holds for their continuous limits.
Theorem 3. The set of functions of the form (W, + Pw.P strictly included in the set of functions (W, P) + D..P.for both one- and two-hop input filtering.
This theorem proven by constructing two models that are distinguished by a c-SGNN but not by any c-GNN. The principle is similar to the proof in the discrete case: in [41 the authors construct two k-regular graphs (with constant degree k), which by construction cannot be distinguished by the Weisfeiler-Lehmae test, and prove that there is however SGNN that distinguishes them. In the proof
3 we construct two SBMs with the same constant degree function, such that any C-GNN returns the same result on them, and design a c-SGNN that distinguishes them. We note that there might be subsets M c W x P that do not contain such models, and therefore on which c-GNNs and c-SGNNs have the same approximation power.
4.3 Examples
While a generic universality theorem random graphs seems to be out-of-reach for the moment, we examine several interesting examples, and pave the way for future extensions. We focus on c-SGNNs, but, sometimes, may not conclude the power of c-GNNs: we could not prove that they are universal, but were not able to find a counter-example either. For simplicity, and since our purpose here is mainly illustrative, we mostly focus on one-hop input filtering.
Stochastic Block Models. SBMs 19 are classical models to emulate graphs with communities. In our settings, SBMs with K communities can be obtained with finite latent space |X] K, typically X' = (l,..., K). The kernel W (k: k') = W can be represented as a matrix W E SK. where Sy is the set of symmetric matrices in 10, 1] x| and the distribution P(k) Pss as a vector P E K where A K = {P E [0, Σ. Pk = 1] is the (K-1) dimmeniiiaa simplex.
In the following proposition, we fix P and examine universality with respect to W. In this case, continuous GNNs are actually quite similar to discrete ones on matrices W, except that the probability vector P also intervenes in the computation. While GNNs on finite graphs can only be universal when using high-order tensors [32 (33 due to invariance to graph-isomorphism. here P can help to disambiguate this constraint. We will say that P E A -1 is incoherent if: for signs E {-1, 13 having Σx= Py 0 implies s O. That is, no probability is an exact sum or difference of the others. We note that vector drawn uniformly on A K- is incoherent with probability For incoherent probability vectors, we can show universality of c-SGNNs. Moreover, this is actually a case where we can prove that c-GNNs are, in turn, not universal.
Proposition 3. For one-hop input filtering, if P is incoherent the space of functions W - T WWP dense in C(SK, IR). Moreover, there exists P incoherent and W + W' such that, for any C-GNN, dw.P = 2w'.P. P.
Additive kernel. Let now fix W and examine universality with respect to P. A classical theorem on symmetric continuous functions [48] states that any W can be arbitrarily well approximated as W(z, y) R u(v(x) + v(y)) for some functions u, Inspired by this result, kernel will be said to be additive if it can (exactly) be written as (z, y) = u(e(z) + v(y)). and injectively additive both u, V continuous and injective. We prove universality in the unidimensional case below.
Proposition 4. Let X C TR, and P be any compact subset of P. Assume W is injectively additive with Im(v) C R. For one-hop filtering, the space of functions P - Ww.P is dense in C(P, ((P,R).
It is easy to see that injectively additive kernels include all SBMs for which Wi; * Way when Prop. However, unlike additive kernels, injectively additive kernels
i + J', so Prop. Prop.4complett a priori not universal approximators of symmetric continuous functions: this result (88 is only valid when Im(v) can be multidimensional. But it is known for instance that there is no continuous injective map from [0, 1 [0, 1). so if Im(v) [0, 1J2, u cannot be both continuous and injective.
Radial kernel. We conclude this section with an important class of kernels, radial kernels (Zz w([le vll) for some function R + [0, 1]. They include the popular Gaus-
7

---

sian kernel and so-called E-graphs. Below, we give example in one dimension, for which c-SGNNs are universal on symmetric distributions. The case of non-symmetric distributions seems more involved and we leave it for future investigations.
Proposition 5. Assume that X' = [- and W(r,v) w([x - wl) where to is continuous and injective. Let C P be any compact set of symmetric distributions. For one-hop input filtering, the space of functions P + W..P is dense in C(P, IR).
Approximation power: permotattoon-equivariant case
In the equivariant case, recall that the outputs of c-(S)GNNs are functions X. The "traditional"
notion of universality is to evaluate the approximation power of mappings (W, P) + F, where F is some space of equivariant functions, is done for the discrete case 23 3 However, potentially simpler and more relevant notion here is to fix (W, P), and directly examine the properties of the space of functions X' + E represented by c-(S)GNNs, that is, the space of functions (Vw: all possible e- S-GNNNs ! W. (and similar for ww.P). Indeed, this directly answers such questions as: given an SBM, does there exist c-GNN that can labels the communities (Fig. I Or: given the structure of a mesh what functions can be computed on it, e.g. for segmentation?
IR for
5.1 Generic result with Seine--Wiesssrrsss theorem
As in the invariant case, the Sone-Weierssrass theorem yields a generic separation condition.
Proposition 6. Let (W, P) be fixed. Then c-SGNNs (resp. c-GNNs) are dense in C(X.R () iff: for all + x' E X, there c-SGNN (resp. a c-GNN) such that Ww)((x) # (w.)(x)) (resp. @w.p(z) # Dw.p(x')).
(W, P) are such that c-(S)GNNs satisfy some symmetry or invariance (see for instance Prop. 9p. then the space X' can be quotiented to obtain universality among functions satisfying these constraints.
5.2 e-SGNNs are more powerful than c-GNNS
Using a proof similar to Theorem 3 we can then prove that e-SGNNs are indeed strictly more powerful than c-GNNs for some (W,P).
Theorem 4. For both one- and two-hop input filtering, the following holds. For any (W, P), the set of functions of the form &w.p is included in the set of functions MwP, and there exist (W, such that the inclusion is striet.
Again, we note that, for some random graph models CW and c-GNNs might have the same approximation power.
5.3 Examples
We treat the same examples as before, with the addition of two-hop filtering for SBMs and radial kernels on the d-dimensional sphere.
SBM. Universality in the SBM case corresponds being able to distinguish communities. that is, Ww. X + I returns a different value for each element of the latent space X. In the following result, assume that W is invertible, and prove the result for both one- and two-hop filtering, meaning that c-SGNNs can indeed distinguish communities of SBMs with random edges under some mild conditions. On the other hand, c-GNNs may fail such models.
Proposition 7. Let P be incoherent, and W be invertible. For both one- and two-hop input filtering, c-SGNNs are dense in C(X, R.. Moreover, there exist (W, P) satisfying the conditions above such that any c-GNN @w,p is a constani function.
This proposition is illustrated in Fig. D an SBM with constant degree function, any GNN converges to a c-GNN with constant output, while a SGNN with two-hop input filtering can close to c-SGNN that perfectly separates the communities.

---

Figure 3: Illustration of Prop. 9 on Gaussian kemnl,, but with random edges and two-hop input filtering. The x-axis is the latent variables in X [-1.1]. The y-axis is the oulput of a SGNN trained to approximate some function (red curve). On the left, both distribution P and f symmetric, c-SGNNs are universal in that case. the center, symmetric but not f. and the training expectedly fails since the limit e-SGNN is symmetric. On the right, P and f are non symmetreercc and universality holds again. Details can be found in App. E
Additive kernel. As in the invariant case, injectively additive kernels lead to universality.
Proposition 8. Assume W is injectively additive, fix any P. Then, for one-hop input filtering, c-SGNNs are dense C(X,R) IR).
Radial kernel. Unlike the invariant case (Prop. 5) which limited symmetric distributions, treat both symmetric and non-symmetric case: when P is symmetric, then so is WP W.. (by permutation- equivariance), and we have universality among symmetric functions. When P is non-symmetric, we have universality among all functions. See Fig. 3 for an illustration.
Proposition 9. Consider X' = [-1,1], (x,, y) = w(x yl) a radial kernel with an invertible, continuous w, and P with a piecewise continuous density such that EEx = 0. Then, for one-hop input filtering: if P is symmetric, c-SGNNs are dense in the space of symmetric functions and if P is not symmetric, c-SGNNs are dense in C(X, R).
funnciioc in C(X, IR),
Finally, we look at radial kernels on the d-dimensional sphere = an important example sometimes referred to as random geometrie graphs [34, (2). or dot-product kernels [33], which are for instance popular in social networks analysis 47. Indeed, this case, the kernel only depends on the dot product W(x, y) = w(x y). Denoting by dr the uniform measure on gd-1, is known
Rd |||||| 1}.
14, 11 that functions in (ddd can be uniquely decomposed as
IN(dk) (k.)YE((D)) where Yk.j are spherical harmonics, that is, homogeneous harmonic polynomials of degree which form an orthonormal basis of I,7 We will say that such function is injectively decomposed the mapping x - [ff(<>]]k3o from $d-1 to (R) is injective. Note that generically this is verified if f& is non-zero for more than d - distinct values of & > 0. as this corresponds to solving an over-determined system of polynomial equations, but there may be degenerate situations where this is not enough. The proof of the following proposition based on the well-known Legendre/Gegenbauer polynomial decomposition of spherical
f() Ex (x) Ex Σj=1
harmonics (9] (see App. C.5
Proposition 10. Assume that X = ga-1, that W W(x,w) v) = w(x y) with continuous invertible w : 1, - [0, 1), and that P = fdr has density which is injectively decomposed. Then for one-hop imput filtering c-SGNNs are dense in C(X, RR).
Conclusion and outlooks
It is known that permutation-inet invariant GNNs fail to distinguish regular graphs of the same order, and permutation-equivaal GNNs return constant output on regular graphs. Similarly, their continuous counterparts suffer from the same flaw on random graph with constant or almost-constan degree function [30]. However, we showed that the recently proposed SGNNs converge to continuous architectures which, like in the discrete world, are strictly more powerful than C-GNNs. Moreover, c-SGNNs are universal on many random graph models of interest, including large class of SBMs and random geometric graphs.
proved that both permutation-invartii and cannuutation-qqivariii
We believe that our work opens many possibilities for future investigations. We examined very simple strategies for choosing the inputs Eg of the SGNN, but more complex, spectral-based based choices

---

could exhibit better convergence properties and approximation power. We showed universality in specific random graph models interest, but deriving more generic criterion still an open question. More directly, most of our examples illustrate the one-dimensional case X' C R, and a generalization to multidimensional latent spaces would be an important step forward. Besides SGNNs, architectures that include high-order tensors [31] (sometimes called FGNN (3) are known to be more powerful than the WL test. Conditions for their convergence on large graphs are still open, in particular since high-order tensors lead to high-order operators that may be difficult to manipulate. Finally, we remark that directly estimating the latent variables I; a classical task in statistics, for which conditions of success have been derived for various approaches, e.g. for Spectral Clustering 25 Comparing them with (S)GNNs is an important path for future work.
Acknowledgement
This work was partly supported by ANR GraVa ANR-18-CE400000
References
[1] Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewiez. The Surprising Power of Graph Neural Networks with Random Node Initialization. In IJCAI International Joint Conference Artificial Intelligence, pages 2112211112212 1212118, 2021.
[2] Ernesto Araya and Yohann de Castro. Latent distance estimation for random geometric graphs. In Advances in Neural Information Processing Systems, volume 32, 2019.
[3] Waiss Azizian and Marc Lelarge. Characterizing the expressive power of invariant and equivari- graph neural networks. In International Conference on Learning Representations (ICLR), 2021.
[4] László Babai. Graph isomorphism in quasipolynomial time. Proceedings of the Annual ACM Symposium on Theory of Computing, 2016.
[5] Michael M. Bronstein, Joan Bruna, Yann Lecun, Arthur Szlam, and Pierre Vandergheynst. Geometric Deep Learning: Going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
[6] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In Advances in Neural Information and Processing Systems (NeurIPS), 2020.
[7] Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International Conference on Learning Representations (ICLR), 2019.
[8] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with GNNs. In Advances in Neural Information Processing System (NeurIPS), pages 1-19, 2019.
[9] Feng Dai and Yuan Xu. Approximation Theory and Harmonic Analysis on Spheres and Balls. Springer, 2013.
[10] George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. IJCAI International Joint Conference on Artificial Intelligence, 2021 1
2020.
[11] Gwendoline de Bie, Gabriel Peyré, and Marco Cuturi. Stochastic deep networks. In International Conference on Machine Learning, 2018.
[12] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Advances Neural Information and Processing Systems (NIPS), 2016.
[13] Nima Dehmamy, Albert-L.as áäzld Barabàsi, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. Advances Neural Information and Processing Systems (NeurIPS), 2019.
10

---

[14] Costas Efthimiou and Christopher Frye. Spherical harmonics in dimensions. World Scientific, 2014.
[15] Vikas K. Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks, In International Conference on Machine Leurning (ICML), pages 1-22. 2020.
[16] Floris Geerts. The expressive power of kth-order invariant graph networks. arXiv:2007.12035, 2020.
[17] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural Message Passing for Quantum Chemistry. In International Conference on Machine Learning (ICML), pages 1-14, 2017.
[18] William L. Hamilton. Graph Representation Learning. Morgan Claypool, 2020.
[19] Paul W Holland. Stochastic blockmodels: First steps. Social Nenworks, 5(2):109-137, 1983.
[20] Kurt Horik,, Maxwell Stinchcombe, and Halbert White. Multilayer Feedforward Networks are Universal Approximators. Neural Networks, 2:359-366, 1989.
[21] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. Neural Information Processing Systems (NeurIPS), 2020.
[22] Nicolas Keriven, Alberto Bictti, and Samuel Vaiter. Convergence and Stability of Graph Convolutional Networks on Large Random Graphs. In Advances in Neural Information and Processing Systems (NeurIPS), pages 1 1-26, 2020.
[23] Nicolas Keriven and Gabriel Peyré. Universal Invariant and Equivariant Graph Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), pages 1-19, 2019.
[24] Thomas N Kipf and Max Welling. Semi-Supervised Learning with Graph Convolutional Networks. In International Conference on Learning Representutions (ICLR). 2017.
[25] Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. Annals of Statistics, 43(1) (((1):225222)) 207,23772222 2015.
[26] Ron Levie, Michael M. Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. urXiv:190..12977 pages 1-41, 2019.
[27] Andreas Loukas. How hard is to distinguish graphs with graph neural networks? In Advances in Neural Information and Processing Systems (NeurIPS), 2020.
[28] Andreas Loukas. What graph neural networks cannot leam: depth vs width. In ICLR, 2020.
[29] László Lovász. Large networks and graph limits. Colloquium Publications, 60, 2012.
[30] Abram Magner, Mayank Baranwal, and Alfred O. Hero. The Power of Graph Convolutional Networks to Distinguish Random Graph Models. arXiv:1910.12954 pages 1-27,20 2019.
[31] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably Powerful Graph Networks. In Advances in Neural Information Processing Systems (NeurIPS), pages
1-12, 2019.
[32] Haggai Maron, Ethan Fetaya, Nimrod Segol. and Yaron Lipman. On the Universality of Invariant Networks. In International Conference on Machine Learning (ICML), 2019.
[33] Christine Leigh Myers Nickel. Random Dot Product Graphs Model for Social Networks. PhD thesis, 2006.
[34] Mathew Penrose. Random Geometric Graphs. Oxford University Press, 2008
[35] Allan Pinkus. Approximation theory of the ML.P model in neural networks. Acta Numerica, 14319): 1999.

---

[36] Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimiza- tion with randomization in learning. In Advances in Neural Information Processing Systems (NIPS), 2009.
[37] Lorenzo Rosasco, Mikhail Belkin, and Ernesto De Vito. On learning with integral operators. Journal of Machine Learning Research, 11:905-9344 2010.
[38] Luana Ruiz, Luiz F.O. Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferability of graph neural networks. In Advances in Neural Information and Processing Systems (NeurIPS), 2020.
[39] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random Features Strengthen Graph Neural Networks. Proceedings of the 2021 SIAM International Conference on Data Mining (SDM),
2021.
[40] Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Cambridge University Press, 2018.
[41] Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with message- messagg-passing. In Advances in Neural Information and Processing Systems (NeurIPS), 2020.
[42] Ulrike Von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. Annals of Statistics, 36(2):55--86, 2008.
[43] Yu Weisfeiler and A Leman. The Reduction of Graph to Canonical Form and the Algebra Which Appears Therein. Nti, 2(9):12-16, 1968.
[44] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, pages 1-21, 2020.
[45] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How Powerful are Graph Neural Networks? In ICLR, pages 1-15, 2019.
[46] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. On Size General- ization in Graph Neural Networks. trXiv:2010.088355 2020.
[47] Stephen Young and Edward R. Scheinerman. Random dot product graph models for social networks. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4863 LNCS: 2007.
[48] Manzil Zaheer, Satwik Kottur, Siamak Ravanbhakhsh, Barnabás P6czos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets. Advances in Neural Information Processing Systems (NeurIPS), 2e0111/Deemmmbri)33333-0000000 2017.
[49] Aaron Zweig and Joan Bruna. functional perspective on learning symmetric functions with neural networks. arXiv, pages 1-19, 2020.
12


Reviews:
[{"review_id": "klIDs02kmbC", "reviewer": "Reviewer_5Rj4", "summary": "This paper considers structural Graph Neural Networks (SGNNs) which include unique node identifiers. The authors prove the convergence of SGNNs in the large graph limit to the continuous counterpart c-SGNNs. The c-SGNNs are proved to be more expressive than c-GNNs without the node identifiers. The universality is proved on some random graph models in both permutation-invariant and permutation-equivariant cases.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This paper presents a convergence analysis for SGNNs based on the previous convergence analysis for GNNs. It also presents a novel expressive power and universality analysis in both permutation-invariant and equivariant cases.\n\nQuality/Significance: This paper provides sound theoretical analysis with specific cases considered separately. This is also a frontier work that focuses on the continuous limit of more powerful GNNs. The universality is analyzed from the kernel respective which is representative and meaningful. The limitation that I can see is that the authors do not illustrate the advantages of the c-SGNNs straightforwardly with numerical simulations. I feel it is better to stress more about the motivations and the potential application values. I also have a question in Section 3. In one-hop filtering it seems to be even if the graph is dense, i.e. $\\alpha\\sim 1$, MSE still diverges with a constant value. Therefore I am not clear why one-hop filtering could be used as a general strategy in section 4.\n\nClarity: The paper is overall well-organized and clear. I feel a little lost in section 4 among the parallel examples and propositions. I recommend illustrating one or two cases in particular with numerical experiments while including the other cases in the appendix. The sparsity factor $\\alpha$ and $\\alpha_n$ are inconsistent in the paper, which may be a typo. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "FodSm3KTYjP", "reviewer": "Reviewer_Q8cJ", "summary": "The authors consider the SGNNs introduced in [36], they improve on the selection of unique node identifiers and extend the architecture to the limit of large random graphs. More importantly, the prove that by including the unique node identifiers, the resulting (c-)SGNN is more discriminative than the (c-)GNNs.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very interesting as it poses relevant theoretical results in the field of graph classification using GNNs. It is well written and it is technically solid. I, therefore, recommend it for acceptance at the conference.\n\nMy only comment, if the authors wish to consider it for future research in the area, relates to the nature of the permutation equivariance property of FIR graph filters. The authors state that GNNs with FIR graph filters are incapable of learning communities in an SBM model with the same degree. This is expected due to the permutation equivariance property of FIR graph filters. That is, FIR graph filters are designed to not being able to solve these problems, as this gives them the ability to learn faster and generalize better (as is the case with regular CNNs). Of course, the drawback is that FIR graph filters are not good at tasks in which permutation equivariance is a hassle (like is the case of identifying communities in an SBM). But they also should not be used for those cases. For cases in which permutation equivariance is a problem, there are many non-convolutional graph filters, like node-variant, or edge-variant (EdgeNets), that could work better in these problems. Maybe, instead of looking at unique node identifiers and how to adapt FIR graph filters to solve tasks that they are not suited for, one can just adopt a different kind of filter. Just an idea, that may be computationally less intensive (after all, unique node identifiers require additional N filters to be computed).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "Ce6NHGYLMpi", "reviewer": "Reviewer_nJaH", "summary": "This paper studies the universality of Structural Graph Neural Networks (SGNNs) and their continuous counterparts, termed c-SGNNs, in both the permutation-invariant and equivariant settings.  More specifically, the paper produces a theoretical convergence result between the recently proposed SGNNs and their continuous c-SGNNs in the limit of large graphs, analogously to existing connections between GNNs and their continuous counterparts c-GNNs. Then, the universality of SGNN is theoretically studied based on this convergence, and the expressive power of SGNNs is compared with that of standard GNNs. From this study, it is established that c-SGNNs are strictly more powerful than c-GNNs, and that c-SGNNs are universal on many random graph families, such as stochastic block models (SBMs), symmetric radial kernels, and injectively additive kernels. Finally, the overall universality of SGNNs and c-SGNNs, as well as open questions remaining in this regard, are discussed.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes several theoretical contributions that can be of benefit to the GNN community. In particular, the definition of c-SGNN and the establishment of the correspondence between the two models produces novel insights about the power of SGNNs, and yields analogous theoretical knowledge to what is already established for standard GNNs. The study of model universality over distinct families of random graphs is also informative. However, I have concerns about the significance of the results and the overall contribution that these findings make. More specifically, I find that the results about universality over families of random graphs are of rather limited applicability and scope, as the results pertain to relatively niche classes of random graphs, which do not (to my knowledge) provide insights towards standard use cases of GNNs, unlike analogous WL and structure-based results for the discrete setting. Moreover, the results in this section appear to be disjoint, and there does not seem to be a means to leverage each result directly towards making more general discussions and deductions, or establishing a framework for studying SGNNs. Therefore, I feel that the paper would benefit from a better clarification of the scope of its results.\n\nIn terms of related work, the paper mentions higher-order GNNs and c-GNNs, but omits relevant works from the literature on the expressive power of GNNs that use randomness for allocating node features:\n\n[1] R. Sato et al., \"Random Features Strengthen Graph Neural Networks\", SDM 2021.\n\n[2] G. Dasoulas et al., \"Coloring Graph Neural Networks for Node Disambiguation\", IJCAI 2020.\n\n[3] R. Abboud et al., \"The Surprising Power of Graph Neural Networks with Random Node Initialization\", IJCAI 2021.\n\nThese works achieve higher expressiveness (universality in [2] and [3]) and strong generalization simply by adding randomness to initial node features, and in fact randomly sampled features preserve invariance/equivariance in expectation and maintain the efficient running time of standard GNNs [3]. Therefore, these works should be presented in the paper and discussed against its contributions.\n\nFinally, the writing of the paper could be improved with some changes, e.g., some basic concept and model definitions (like graphons) should be explicitly presented, graph neural networks can be presented more intuitively, the notation for invariant and equivariant functions should be made more distinctive (rather than a simple bar).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "3xCbeRBTbDV", "reviewer": "Reviewer_uBKY", "summary": "This paper studies continuous limits of Structured Graph Neural Networks (SGNNs), which authors call c-SGNNs. Prior work studied the continuous limits of GNNs as c-GNNs. Another prior work proposed SGNNs and showed it is more powerful than GNNs. This work merges these two results and show that SGNNs converge to c-SGNNs, and also that c-SGNNs are more powerful than c-GNNs. Specifically, c-GNNs do not cover Stochastic Block Models (SBMs), whereas c-SGNNs do.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: Authors combine two recent innovations in GNNs. The first is c-GNN, the continuous limit of GNNs. The second is structured GNNs (SGNNs). Now authors study the continuous limit of SGNNs as c-SGNNs. The combination is not technically straightforward. SGNNs are based on one-hot encoding, but this does not have a straightforward continuous counterpart. Authors propose one-hop & two-hop filtering as alternatives, and study their convergence properties.\n\nQuality & Significance: Approximation power analysis of Neural Networks is outside of my area of expertise, and I was not able to carefully verify proofs in the appendix. However, the narrative in the main paper certainly sounds technically plausible. The convergence analysis follows the strategy of Keriven et al (NeurIPS 2020). For power analysis, authors show that c-GNNs don't cover SBMs, while c-SGNNs do. This seems to be a significant observation, as SBMs are important class of random graph models. Also, authors also show that c-SGNNs are dense on injectively additive & radial kernels. \n\nClarity: The paper is certainly well-organized and easy to follow. Authors do a great job explaining high-level implications of each theorem/proposition. On the other hand, the main body of the paper discusses little about what technical challenges they had to deal with, and what proof techniques were used to solve them. The paper is quite rich with technical content, and therefore this is probably inevitable for a conference paper.\n\nSignificance: The mere fact that c-SGNNs are stronger than c-GNNs is not particularly surprising. But the fact that SBMs are counter examples of c-GNNs and c-SGNNs fix it is quite meaningful, considering the importance of SBMs in graph modeling literature. Also, authors introduce a few techniques that help analyze SGNNs: a spectral version of SGNN, and one/two hop filtering that replaces one-hot encoding. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While injectively additive kernels and radial kernels are certainly important in the context they were proposed, it is unclear whether they can be interesting kernels for continuous limits of graphs. Maybe some discussions on the usefulness of these kernels on graph modeling context would strengthen the significance of the paper.\n\nAlthough authors demonstrate c-SGNNs are more powerful than c-GNNs, somehow the counterexample seems quite different from that from SGNN paper. It would be interesting to see how these counterexamples are related. For example, would GNNs have trouble fitting graphs from SBMs?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies structural GNNs in the large graph limit where they converge towards their continuous counterpart c-SGNN. The paper presents a variety of theoretical results showing that c-SGNNs are provably superior to the continuous version of vanilla GNNs namely, c-GNNs. In particular the paper shows that c-SGNNs can recover communities in a stochastic block models in regimes where c-GNNs fail.

All the reviewers agreed that the paper presents a novel and interesting set of theoretical results. However, the reviewers also felt that the paper can do a better job of discussing and comparing with existing literature. I recommend the paper for acceptance with a strong recommendation to the authors that they take into account the reviewer comments about existing work when preparing the camera ready version.
Decision: Accept (Poster)