On the Universality of Graph Neural Networks on Large Random Graphs
Year: 2022

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.

heading: 1 Introduction
text: Graph Neural Networks (GNNs) are deep architectures defined over graph data that have garnered a lot of attention in recent years. They represent the state-of-the-art in many graph Machine Learning (graph ML) problems, and have been successfully applied to e.g. node clustering [7], semi-supervised learning [24], quantum chemistry [17], and so on. See [5, 44, 18, 21] 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 the 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 as the famous Weisfeiler-Lehman (WL) test [43] for graph isomorphism. Since then, several works [45, 31, 8] have derived new architectures, for instance involving high-order tensors [31], with improved discriminative power equivalent to “higher-order” variants of the WL test. In another line of works, several recent papers have advocated the use of unique node identifiers [28, 27], with
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
strategies to preserve the permutation-equivariance/invariance of GNNs coined Structural Message 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 WL test in [41], and even universal on graphs with bounded degrees, however for powerful layers that cannot be implemented in practice.
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-graph limit. In [22, 38], GNNs are shown to converge to limiting “continuous” architectures (coined c-GNNs in [22]). A few works have studied the discriminative power of 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. 1), and the question is still largely open.
Contribution and outline. In this paper, we study the convergence of SGNNs on large random graphs towards “c-SGNNs”, and analyze the approximation power of c-GNNs and cSGNNs. After some preliminary results in Sec. 2, we study the convergence of SGNNs in Sec 3. In Sec. 4 and 5, we show that c-SGNNs are strictly more powerful than cGNNs in both permutation-invariant and equivariant case. We then prove the universality of c-SGNNs on several popular models of random graphs, including Stochastic Block Models (SBMs) and radial kernels. For instance, we show in Sec. 5.3 that c-SGNNs can perfectly identify the communities of most SBMs, including some for which any c-GNN provably fails (Fig. 1). The code for the numerical illustrations is available at https://github.com/ nkeriven/random-graph-gnn.
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-invariant GNNs were at best as powerful as the WL test, and later models [31, 8, 16] were constructed to be as powerful as higher-order WL tests, using for instance higher-order tensors [31]. The link between the graph isomorphism problem and function approximation was made in [8, 23] and extended in [3]. Some architectures were proven to be universal [32, 23] but involve tensors of unbounded order. When graphs are equipped with unique node identifiers, the approximation power of GNNs can be significantly improved if relaxing permutation-invariance/equivariance [28, 27, 10], or assuming that it holds only in expectation with respect to additional sources of randomness [39, 1]. 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 permutation-invariance/equivariance. As mentioned above, SGNNs are more powerful than the WL test [41], 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.
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 [6, 13] or identify various graph properties [15, 46]. Several works have studied the large-graphs limit of GNNs [38, 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-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 (S)GNNs in the continuous limit. Finally, we note that universal architectures exist on measures [11, 49], which can be seen as limits of point clouds, but, similar to the discrete case [48, 32, 23], the graph case may be significantly harder to study.

heading: 2 Preliminaries
text: In this section, we group notations on random graphs and GNNs, 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 a symmetric adjacency matrix A ∈ Rn×n. It is isomorphic to all graphs with adjacency matrices σAσ>, for any permutation matrix σ ∈ {0, 1}n×n. Matrix rows (resp. columns) are denoted by Ai,: (resp. A:,i). The norm ‖·‖ is the operator norm for matrices and Euclidean norm for vectors. For a compact metric space X , we denote by C(X ,R) the space of bounded continuous functions X → R, equipped with ‖f‖∞ = supx |f(x)|. For a multivariate function f ∈ C(X ,Rd), fi denotes its ith coordinate, and ‖f‖∞ = ( ∑ i ‖fi‖ 2 ∞) 1/2.

heading: 2.1 Random graph model
text: 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 xi drawn i.i.d. For the edges, we will examine two cases: an “ideal” one with deterministic weighted edges, and a more “realistic” one where the edges are randomly drawn independently. In the literature, the latter is often considered as 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 ε-covering numbers1 of X scale as O ( ε−dX ) for some dimension dX . We denote byW the set of symmetric bivariate functions in C(X × X , [0, 1]) that are LW -Lipschitz in each variable, and by P the set of probability distributions over X equipped with the total variation norm ‖·‖TV. A graph with n nodes is generated according to a random graph model (W,P ) ∈ W ×P as follows:
x1, . . . , xn i.i.d∼ P, aij = { W (xi, xj) deterministic edges case α−1n Bernoulli(αnW (xi, xj)) random edges case
where αn is the sparsity level of the graph in the random edges case, which we assume to be known for simplicity. When αn ∼ 1, the graph is said to be dense, when αn ∼ 1n the graph is sparse, and when α ∼ lognn the graph is relatively sparse. Note that we have normalized the Bernoulli edges by 1/αn such that Eaij = W (xi, xj) conditionally on xi, xj . When X is finite, the model is called an SBM (see Sec. 4.3).
Like finite graphs, random graph models can be isomorphic to one another [22, 29]. In this paper, similar to [22] we consider that, for any bijection ϕ : X → X , the model (W,P ) is isomorphic to (Wϕ, ϕ −1 ] P ), where Wϕ(x, y) = W (ϕ(x), ϕ(y)) and f]P is the pushforward of P (the distribution of f(X)). Indeed, it is easy to see that both produce exactly the same distribution over graphs.

heading: 2.2 Graph Neural Networks
text: 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 h defined as h(A) = ∑ k βkA
k 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 ρ : R → R which satisfies ρ(0) = 0 and |ρ(x)− ρ(y)| 6 |x− 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 Z(0) ∈ Rn×d0 , at each layer ` = 0, . . . ,M − 1:
Z (`+1) :,j = ρ (∑d` i=1 h (`) ij ( 1 nA ) Z (`) :,i + b (`) j 1n ) ∈ Rn j = 1, . . . , d`+1 , (1)
where h(`)ij (A) = ∑ k β (`) ijkA
k are trainable graph filters, b(`)j ∈ R are trainable additive biases and ρ is applied pointwise. We note the normalization A/n that will be necessary for convergence. GNNs exist in two main versions: so-called “permutation-invariant” GNNs Φ̄ output a single vector for the entire graph, while “permutation-equivariant” GNNs Φ output a graph signal:
ΦA(Z (0)) = g ( Z(M) ) ∈ Rn×dout Φ̄A(Z(0)) = g ( 1 n ∑n i=1 Z (M) i,: ) ∈ Rdout , (2)
1the number of balls of radius ε required to cover X
where g : RdM → Rdout is an MLP applied row-wise in the equivariant case. By construction, such GNNs are indeed equivariant or invariant to node permutation: for all permutation matrices σ, we have ΦσAσ>(σZ(0)) = σΦA(Z(0)) and Φ̄σAσ>(σZ(0)) = Φ̄A(Z(0)).
Continuous GNNs. In [22], the authors show that, in the large random graphs limit, GNNs converge to the following “continuous” models (coined c-GNNs), which propagate functions over the latent space f (`) ∈ C(X ,Rd`) instead of graph signals. Given an input function f (0) ∈ C(X ,Rd0):
f (`+1) j = ρ (∑d` i=1 h (`) ij (TW,P )f (`) i + b (`) j ) ,
where TW,P is the operator TW,P f = ∫ W (·, x)f(x)dP (x). Then similar to (2) the permutationequivariant/invariant versions of c-GNNs are defined as:
ΦW,P (f (0)) = g ◦ f (M), Φ̄W,P (f (0)) = g (∫ f (M)(x)dP (x) ) .
Remark that ΦW,P (f (0)) is itself a function in C(X ,Rdout) while Φ̄W,P (f (0)) ∈ Rdout is a vector. Moreover, by virtue of the polynomial filters, the four architectures ΦA, Φ̄A,ΦW,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 ϕ : X → X , we have ΦWϕ,ϕ−1] P (f ◦ ϕ) = ΦW,P (f) ◦ ϕ and Φ̄Wϕ,ϕ−1] P (f ◦ ϕ) = Φ̄W,P (f).
Let us now turn to convergence of GNNs to c-GNNs. The following result is adapted2 from [22]. While the outputs of permutation-invariant GNNs and c-GNNs are vectors in Rdout that can be directly compared, the output graph signal of a permutation-equivariant GNN is compared with a sampling of the output function of the corresponding c-GNN: for a graph signal Z ∈ Rn×d, a function f : X → Rd and X = {xi}ni=1, we define the (square root of the) mean-square error as MSEX(Z, f) = ( 1n ∑n i=1 ‖Zi − f(xi)‖ 2 2)
1/2. The proof of Theorem 1 with all multiplicative constants is given in App. A.1. Recall that dX is the “dimension” of X . Theorem 1. Assume G is drawn from (W,P ) and has latent variables X . Fix ρ, ν > 0.
• In the deterministic edges case: with probability 1− ρ, for all Z(0):
MSEX(ΦA(Z(0)),ΦW,P (f (0))) 6 C ·MSEX(Z(0), f (0)) +R1(n) (3) for some constant C and R1(n) = O (√ (dX + log(1/ρ))/n ) .
• In the random edges case: assume that the sparsity level is αn & n−1 log n. There is a constant Cν such that, with probability 1− ρ− n−ν , for all Z(0):
MSEX(ΦA(Z(0)),ΦW,P (f (0))) 6 C ·MSEX(Z(0), f (0)) +R1(n) +R2(n) (4) where R2(n) = O ( Cν/ √ αnn ) .
• In the permutation-invariant case: The exact same results hold for ∥∥Φ̄A(Z(0))− Φ̄W,P (f (0))∥∥
instead of the MSE on the left-hand-side, with an added error term R3(n) = O (√ log(1/ρ)/n ) .
By the theorem above, a GNN converges to its continuous counterpart if Z(0) is (close to) a sampling of a function f (0) 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, a popular baseline is to simply take constant input Z(0) = 1n (which, by a 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-GNN with f (0) = 1. For simplicity in the rest of the paper we drop the notation “(1)” and write ΦA = ΦA(1n), ΦW,P = ΦW,P (1), and so on. It is known that GNNs are limited on regular graphs: for permutation-invariant GNNs, the WL test cannot distinguish regular graphs of the same order, and for permutation-equivariant GNNs, ΦA(1n) is constant over the nodes. Similarly for c-GNN, the degree function ∫ W (·, x)dP (x) is key in the discriminative power of c-GNNs [30], and if it is constant, then ΦW,P (1) is a constant function (see Fig. 1).
2The authors in [22] proved this for the normalized Laplacian, which allows bypassing the knowledge of αn. Here we use the adjacency matrix, for our later results on approximation power.

heading: 2.3 SGNN: GNN with unique node identifiers
text: To remedy the absence of input node features, in [41] the authors propose an architecture with unique node identifiers while still respecting permutation invariance/equivariance. More precisely, they first choose an arbitrary ordering of the nodes q = 1, . . . , n, apply a GNN to each one-hot vector eq = [0, . . . , 1, . . . , 0], and restore equivariance to permutation by a final pooling. For later purpose of convergence, we generalize this strategy to any collection Eq(A) ∈ Rn×d0 that satisfies:
Eq(σAσ >) = σEσ−1(q)(A) . (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 Eq(A) = h(A)eq . After the GNN ΦA, a pooling is applied to restore equivariance, then a second GNN Φ′A that is either invariant or equivariant:
ΨA = Φ ′ A ( 1 n ∑ q ΦA (Eq(A)) ) ∈ Rn×d′out , Ψ̄A = Φ̄′A ( 1 n ∑ q ΦA (Eq(A)) ) ∈ Rd′out (6)
In [41], these architectures, called SMPs, are interpreted as doing message-passing over matrices, and can use more general pooling and aggregation functions. In a sense, what we call SGNN are “spectral” versions of SMP, but are essentially the same idea. It is not difficult to see that SGNNs satisfy: ΨσAσ> = σΨA and Ψ̄σAσ> = Ψ̄A.

heading: 3 Convergence of SGNNs on large random graphs
text: In this section, we extend Theorem 1 to SGNNs. To define continuous SGNNs, we consider a bivariate input function ηW,P : X × X → Rd0 such that: the mapping (W,P ) 7→ ηW,P is continuous3, for any (W,P ), ηW,P is Cη-bounded and Lη-Lipschitz in each variable, and similar to (5) is respects the following:
ηWϕ,ϕ−1] P (x, y) = ηW,P (ϕ(x), ϕ(y)) , (7)
for all bijections ϕ : X → X . For instance, ηW,P = W or any filter ηW,P (x, y) = [h(TW,P )W (·, y)](x) satisfy these conditions. A c-SGNN is then defined as:
ΨW,P = Φ ′ W,P (∫ ΦW,P (ηW,P (·, x))dP (x) ) , (8)
for the equivariant case, or similarly Ψ̄W,P = Φ̄′W,P (∫ ΦW,P (ηW,P (·, x))dP (x) )
for the invariant case. Again, using the properties of c-GNNs, it is easy to see that c-SGNNs respect random graphs isomorphism: ΨWϕ,ϕ−1] P = ΨW,P ◦ ϕ and Ψ̄Wϕ,ϕ−1] P = Ψ̄W,P . We are now ready to extend Theorem 1. The proof and multiplicative constants are in App. A.2. Theorem 2. Assume G is drawn from (W,P ) with latent variables X . Fix ρ, ν > 0.
• In the deterministic edges case: with probability 1− ρ:
MSEX(ΨA,ΨW,P ) 6 C ′ · sup q MSEX(Eq(A), η(·, xq)) +R′1(n) (9)
for some constant C ′ and R′1(n) = O (√ (dX + log(1/ρ))/n ) .
• In the random edges case: assume that the sparsity level is αn & n−1 log n. There is a constant Cν such that, with probability 1− ρ− n−ν:
MSEX(ΨA,ΨW,P ) 6 C ′ · sup q MSEX(Eq(A), η(·, xq)) +R′1(n) +R′2(n) (10)
where R′2(n) = O ( Cν/ √ αnn ) .
• In the permutation-invariant case: The exact same results hold for ∥∥Ψ̄A − Ψ̄W,P∥∥ instead of
the MSE, with an added error term R′3(n) = O (√ log(1/ρ)/n ) .
Hence, we obtain convergence when the input signal Eq(A) is close to being a sampling of a function ηW,P at xq . The choice of input signal/function is therefore crucial. Let us examine a few strategies.
3for the norm ‖·‖∞ + ‖·‖TV onW ×P
One-hot vectors. If one chooses one-hot vectors Eq = eq as in [41], then we can see that the SGNN converges to the continuous architecture with input ηW,P = 0, since MSEX(eq, 0) → 0. Since ΨW,P is nothing more than a traditional c-GNN ΦW,P with constant input in that case, this is not a satisfying choice in terms of approximation power.
One-hop filtering. If we choose to “filter” eq once and take Eq(A) = Aeq , the natural continuous equivalent is ηW,P = W . Such a strategy only works for deterministic edges: indeed,
MSEX(Aeq,W (·, xq)) = ( n−1 ∑n i=1(aiq −W (xi, xq))2 )1/2{ = 0 with deterministic edges ≈ √ n−1 ∑ i V ar(aiq) ∼ α−1 with random edges, w.h.p.
where the last line comes from a simple application of Hoeffding’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 ηW,P (x, y) = TW,P [W (·, y)](x), that is, Eq(A) = A2eq/n. We have the following result.
Proposition 1. In the random edges case, with probability 1−ρ, we have for all q:
MSEX ( A2eq n , TW,P [W (·, xq)](·) ) . O (√ log(n/ρ) αn √ n ) .
In the deterministic edges case, the rate is O (1/ √ n).
Convergence is guaranteed when √ log n/(αn √ n)→ 0, which is stronger than relative sparsity. The difference between onehop and two-hop filtering is illustrated in Fig. 2. 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- or two-hop filtering.

heading: 4 Approximation power: permutation-invariant case
text: In this section, we study the approximation power of continuous architectures in the permutationinvariant case. We seek to characterize the functionsW×P → R that can be well-approximated by a c-GNN or c-SGNN. We derive a generic criterion for universality arising from the Stone-Weierstrass 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.

heading: 4.1 Generic result with Stone-Weierstrass theorem
text: A classical tool to prove universality of neural nets in the literature is the Stone-Weierstrass theorem [20, 23], which states that an algebra of functions that separates points on a compact space is dense in the set of continuous functions. Although NNs are typically not an algebra since they are not closed by multiplication, one of the original proofs of universality for MLPs solves this by a clever trick [20] which we recall in Lemma 1 in App. D. A direct application results in the following proposition.
Proposition 2. LetM⊂W×P be a compact subset ofW×P . c-SGNNs (resp. c-GNNs) are dense in C(M,R) if and only if: for all (W,P ) 6= (W ′, P ′) ∈M, there is a c-SGNN (resp. a c-GNN) such that Ψ̄W,P 6= Ψ̄W ′,P ′ (resp. Φ̄W,P 6= Φ̄W ′,P ′ ).
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 a larger set quotiented by random graph isomorphism.

heading: 4.2 c-SGNNs are more powerful than c-GNNs
text: SGNNs were proven to be strictly more powerful than the WL test, and therefore than GNNs, in [41]. In the theorem below, we check that this strict inclusion holds for their continuous limits. Theorem 3. The set of functions of the form (W,P ) → Φ̄W,P is strictly included in the set of functions (W,P )→ Ψ̄W,P , for both one- and two-hop input filtering.
This theorem is 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-Lehman test, and prove that there is however a SGNN that distinguishes them. In the proof of 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 subsetsM⊂W ×P that do not contain such models, and therefore on which c-GNNs and c-SGNNs have the same approximation power.

heading: 4.3 Examples
text: While a generic universality theorem on 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 on 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 a finite latent space |X | = K, typically X = {1, . . . ,K}. The kernel W (k, k′) = Wkk′ can be represented as a matrix W ∈ SK , where SK is the set of symmetric matrices in [0, 1]K×K , and the distribution P (k) = Pk as a vector P ∈ ∆K−1, where ∆K−1 = {P ∈ [0, 1]K , ∑ k Pk = 1} is the (K–1)-dimensional 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 matricesW , 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, 23] due to invariance to graph-isomorphism, here P can help to disambiguate this constraint. We will say that P ∈ ∆K−1 is incoherent if: for signs s ∈ {−1, 0, 1}k, having ∑K k=1 skPk = 0 implies s = 0. That is, no probability is an exact sum or difference of the others. We note that a vector drawn uniformly on ∆K−1 is incoherent with probability 1. 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 → Ψ̄W,P is dense in C(SK ,R). Moreover, there exists P incoherent and W 6= W ′ such that, for any c-GNN, Φ̄W,P = Φ̄W ′,P .
Additive kernel. Let us 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 (x, y) ≈ u(v(x) + v(y)) for some functions u, v. Inspired by this result, a kernel will be said to be additive if it can (exactly) be written as W (x, y) = u(v(x) + v(y)), and injectively additive if both u, v are continuous and injective. We prove universality in the unidimensional case below.
Proposition 4. Let X ⊂ R, and P̃ be any compact subset of P . Assume W is injectively additive with Im(v) ⊂ R. For one-hop filtering, the space of functions P → Ψ̄W,P is dense in C(P̃,R).
It is easy to see that injectively additive kernels include all SBMs for which Wij 6= Wij′ when j 6= j′, so Prop. 4 completes Prop. 3. However, unlike additive kernels, injectively additive kernels are a priori not universal approximators of symmetric continuous functions: this result [48] 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]2 to [0, 1], so if Im(v) = [0, 1]2, u cannot be both continuous and injective.
Radial kernel. We conclude this section with an important class of kernels, radial kernels W (x, y) = w(‖x− y‖) for some function w : R+ → [0, 1]. They include the popular Gaus-
sian kernel and so-called ε-graphs. Below, we give an 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 = [−1, 1] and W (x, y) = w(|x− y|) where w is continuous and injective. Let P̃ ⊂ 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̃,R).

heading: 5 Approximation power: permutation-equivariant case
text: In the equivariant case, recall that the outputs of c-(S)GNNs are functions on 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, as is done for the discrete case in [23, 3]. However, a potentially simpler and more relevant notion here is to fix (W,P ), and directly examine the properties of the space of functions X → R represented by c-(S)GNNs, that is, the space of functions {ΨW,P : X → R} for all possible c-SGNNs ΨW,P (and similar for ΦW,P ). Indeed, this directly answers such questions as: given an SBM, does there exist a c-GNN that can labels the communities (Fig. 1)? Or: given the structure of a mesh, what functions can be computed on it, e.g. for segmentation?

heading: 5.1 Generic result with Stone-Weierstrass theorem
text: As in the invariant case, the Stone-Weierstrass 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 6= x′ ∈ X , there is a c-SGNN (resp. a c-GNN) such that ΨW,P (x) 6= ΨW,P (x′) (resp. ΦW,P (x) 6= ΦW,P (x′)).
If (W,P ) are such that c-(S)GNNs satisfy some symmetry or invariance (see for instance Prop. 9), then the space X can be quotiented to obtain universality among functions satisfying these constraints.

heading: 5.2 c-SGNNs are more powerful than c-GNNs
text: Using a proof similar to Theorem 3, we can then prove that c-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 ΨW,P , and there exist (W,P ) such that the inclusion is strict.
Again, we note that, for some random graph models (W,P ), c-SGNNs and c-GNNs might have the same approximation power.

heading: 5.3 Examples
text: 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 to being able to distinguish communities, that is, ΨW,P : X → R returns a different value for each element of the latent space X . In the following result, we 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 on 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 constant function.
This proposition is illustrated in Fig. 1: on 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 be close to a c-SGNN that perfectly separates the communities.
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 in C(X ,R).
Radial kernel. Unlike the invariant case (Prop. 5) which was limited to symmetric distributions, we treat both symmetric and non-symmetric case: when P is symmetric, then so is ΨW,P (by permutationequivariance), 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], W (x, y) = w(|x − y|) a radial kernel with an invertible, continuous w, and P with a piecewise continuous density such that EPX = 0. Then, for one-hop input filtering: if P is symmetric, c-SGNNs are dense in the space of symmetric functions in C(X ,R), and if P is not symmetric, c-SGNNs are dense in C(X ,R).
Finally, we look at radial kernels on the d-dimensional sphere X = Sd−1 = {x ∈ Rd | ‖x‖ = 1}, an important example sometimes referred to as random geometric graphs [34, 2], or dot-product kernels [33], which are for instance popular in social networks analysis [47]. Indeed, in this case, the kernel only depends on the dot product W (x, y) = w(x>y). Denoting by dτ the uniform measure on Sd−1, it is known [14, 9] that functions in L2(dτ) can be uniquely decomposed as f(x) = ∑ k>0 fk(x) = ∑ k>0 ∑N(d,k) j=1 ak,jYk,j(x) where Yk,j are spherical harmonics, that is, homogeneous harmonic polynomials of degree k which form an orthonormal basis of L2(dτ). We will say that such a function is injectively decomposed if the mapping x→ [fk(x)]k>0 from Sd−1 to `2(R) is injective. Note that generically this is verified if fk is non-zero for more than d − 1 distinct values of k > 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 is based on the well-known Legendre/Gegenbauer polynomial decomposition of spherical harmonics [9] (see App. C.5).
Proposition 10. Assume that X = Sd−1, that W (x, y) = w(x>y) with continuous invertible w : [−1, 1]→ [0, 1], and that P = fdτ has a density f which is injectively decomposed. Then for one-hop input filtering c-SGNNs are dense in C(X ,R).

heading: 6 Conclusion and outlooks
text: It is known that permutation-invariant GNNs fail to distinguish regular graphs of the same order, and permutation-equivariant GNNs return constant output on regular graphs. Similarly, their continuous counterparts suffer from the same flaw on random graph with constant or almost-constant 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, we proved that both permutation-invariant and permutation-equivariant c-SGNNs are universal on many random graph models of interest, including a large class of SBMs and random geometric graphs.
We believe that our work opens many possibilities for future investigations. We examined very simple strategies for choosing the inputs Eq(A) of the SGNN, but more complex, spectral-based choices
could exhibit better convergence properties and approximation power. We showed universality in specific random graph models of interest, but deriving a more generic criterion is still an open question. More directly, most of our examples illustrate the one-dimensional case X ⊂ 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 xi is 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.

heading: Acknowledgement
text: This work was partly supported by ANR GraVa ANR-18-CE40-0005.

Review summaries:
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.

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.

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.