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

###### Abstract

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

## 1 Introduction

Machine learning on graphs with Graph Neural Networks (GNNs) [53, 5] is now a well-established domain, with application fields ranging from combinatorial optimization [6] to recommender systems [50, 11], physics [45, 1], chemistry [16], epidemiology [37], physical networks such as power grids [41], and many more. Despite this, there is still much that is not properly understood about GNNs, both empirically and theoretically, and their performances are not always consistent [52, 22], compared to simple baselines in some cases. It is generally admitted that a better theoretical understanding of GNNs, especially of their fundamental limitations, is necessary to design better models in the future.

Theoretical studies of GNNs have largely focused on their _expressive power_, kickstarted by a seminal study [54] that relates their ability to _distinguish non-isomorphic graphs_ to the historical Weisfeiler-Lehman (WL) test [51]. Following this, many works have defined improved versions of GNNs to be "more powerful than WL" [34, 35, 26, 49, 38], often by augmenting GNNs with various features, or by implementing "higher-order" versions of the basic message-passing paradigm. Among the simplest and most effective idea to "augment" GNNs is the use of _Positional Encodings_ (PE) as input to the GNN, inspired by the vocabulary of Transformers [48]. The idea is to equip nodes with carefully crafted input features that would help break some of the indeterminancy in the subsequent message-passing framework. In early works, unique and/or random node identifiers have been used [32, 47], but they technically break the permutation-invariance/equivariance - consistency with a reordering of the nodes in the graph - of the GNN. Most PEs in the current literature are based on eigenvectors of the adjacency matrix or
Laplacian of the graph [12, 13] (with recent variants to handle the sign/basis indeterminancy [31]), random-walks [13], node metrics [56, 30], or subgraphs [4]. Some of these have been shown to have an expressive power beyond WL [30, 4, 31].

In some contexts however, WL-based analyses have limitations: they pertain to tasks on graphs (e.g. graph classification or regression) and have limited to no connections to tasks on nodes or links; and they are mostly relevant for small-scale graphs, as medium or large graphs are never isomorphic but exhibit different characteristics (e.g. community structures). At the other end of the spectrum, the properties of GNNs on _large_ graphs have been analysed in the context of latent positions Random Graphs (RGs) [24, 25, 43, 44, 29, 2, 36], a family of models slightly more general than graphons [33]. Such statistical models of large graphs are classically used in graph theory [18, 9] to model various data such as epidemiological [27, 39], biological [17], social [20], or protein-protein interaction [19] networks, and are still an active area of research [9]. For GNNs, the use of such models has shed light on their stability to deformations of the model [44, 29, 24], expressive power [25], generalisation [15, 36], or some phenomena such as oversmoothing [23, 3]. One basic idea is that, as the number of nodes in a random graph grows, GNNs converge to "continuous" equivalents [24, 8], whose properties are somewhat easier to characterize than their discrete counterpart. As prediction tasks on _nodes_ are far more common and relevant on large graphs modelled by random graphs, this paper will focus on _permutation-equivariant_ GNNs, rather than permutation-invariant. In the limit, it has been shown that their output converge to _functions_ over some latent space to label the nodes, but the descriptions of this space of functions and its properties are still very much incomplete. A partial answer was given in [25], in which some universality properties are given for specific models of GNNs, but for limited models of random graphs _with no random edges_, and specific models of GNNs that no not include node features or PEs.

Contributions.In this paper, we significantly extend existing results by providing a **complete description of the function space generated by permutation-equivariant GNNs** (Theorem 1), in terms of simple stability rules, and show that it is equivalent to previous implicit definitions that were based on convergence bounds. We outline the **role of the input node features**, and particularly of Positional Encodings (PEs). We then study the several representative examples of PEs on large random graphs. In particular, we analyze SignNet [31] (eigenvector-based) PEs (Theorem 2), and distance-based PEs [30] (Theorem 3). We derive simple normalization rules that are necessary for convergence, and show that they are relevant even on real data. Finally, our proofs contain new universality results for square-integrable functions and new concentration inequalities that are of independent interest. All technical proofs, and the code to reproduce the figures, are available as supplementary material or in the Appendix.

## 2 Background on Random Graphs and Graph Neural Networks

Let us start with generic notations and definitions. The norm \(\left\lVert\cdot\right\rVert\) is the Euclidean norm for vectors and the operator norm for matrices and compact operators between Hilbert spaces. The latent space \(\mathcal{X}\) is a compact metric set with a probability distribution \(P\) over it. Square-integrable functions from \(\mathcal{X}\) to \(\mathbb{R}^{q}\) w.r.t. \(P\) are denoted by \(L_{q}^{2}\), and are equipped with the Hilbertian norm \(\left\lVert f\right\rVert_{L^{2}}^{2}\stackrel{{\text{\tiny def.}}} {{=}}\int_{\mathcal{X}}\left\lVert f(x)\right\rVert^{2}dP(x)\). The (disjoint) union of multidimensional functions \(L_{\cup}^{2}\stackrel{{\text{\tiny def.}}}{{=}}\bigsqcup_{q\in \mathbb{N}^{*}}L_{q}^{2}\) is a metric space for a metric defined as \(\left\lVert f-g\right\rVert_{L^{2}}\) if \(f,g\in L_{q}^{2}\) for some \(q\), and \(1\) otherwise. Continuous _Lipschitz_ functions between metric spaces \(\mathcal{X}\rightarrow\mathcal{Y}\) are denoted by \(\mathcal{C}_{\text{Lip}}(\mathcal{X},\mathcal{Y})\). For \(X=\left\{x_{1},\ldots,x_{n}\right\}\) where \(x_{i}\in\mathcal{X}\), we define the sampling of \(f:\mathcal{X}\rightarrow\mathbb{R}^{d}\) as \(\iota_{X}f=\left[f(x_{i})\right]_{i=1}^{n}\in\mathbb{R}^{n\times d}\). Given \(Z\in\mathbb{R}^{n\times d}\), the Frobenius norm is \(\left\lVert Z\right\rVert_{\text{F}}\) and we define the normalized Frobenius norm as \(\left\lVert Z\right\rVert_{\text{MSE}}=n^{-\frac{1}{2}}\left\lVert Z\right\rVert _{\text{F}}\). The notation comes from the fact that \(\left\lVert\iota_{X}(f-f^{\star})\right\rVert_{\text{MSE}}^{2}=n^{-1}\sum_{i} \left\lVert f(x_{i})-f^{\star}(x_{i})\right\rVert^{2}\) which is akin to an empirical Mean Square Error.
Latent position Random Graphs.In this paper, we consider _latent position random graphs_[20, 28, 33], a family of models that includes Stochastic Block Models (SBM), graphons, random geometric graphs, and many other examples. They are the primary models used for the study of GNNs in the literature [24, 25, 29, 43]. We generate a graph \(G=(X,A,Z)\), where \(X\in\mathbb{R}^{n\times d}\) are _unobserved_ latent variables, \(A\in\{0,1\}^{n\times n}\) its symmetric adjacency matrix, and \(Z\in\mathbb{R}^{n\times p}\) are (optional) observed node features. The latent variables and adjacency matrix are generated as such:

\[\forall i,\ x_{i}\stackrel{{ iid}}{{\sim}}P,\qquad\forall i<j,\ a_{ij}\sim\text{Bernoulli}(\alpha_{n}w(x_{i},x_{j}))\quad\text{ independently} \tag{1}\]

where \(w:\mathcal{X}\times\mathcal{X}\to[0,1]\) is a continuous _connectivity kernel_ and \(\alpha_{n}\) is the _sparsity-level_ of the graph, such that the expected degrees are in \(\mathcal{O}\left(n^{2}\alpha_{n}\right)\). Non-dense graph can be obtain with \(\alpha_{n}=o(1)\), here we will go down to the _relatively sparse_ case \(\alpha_{n}\gtrsim(\log n)/n\), a classical choice in the literature [28, 24]. Note that the continuity hypothesis of the kernel \(w\) is not really restrictive: neither \(\mathcal{X}\) nor the support of the distribution \(P\) need be connected. For instance, SBMs can be obtained by taking \(\mathcal{X}\) to be a finite set. We do not specify a model for the node features yet, see Sec. 4.

Graph shift matrix and operator.When the number of nodes grows on random graphs, it is known that certain discrete operators associated to the graph converge to their continuous version, as well as the GNNs that employ them [24, 8]. Here, some of our results will be valid under quite generic assumptions. We consider a **graph shift matrix**[46]\(S=S(G)\in\mathbb{R}^{n\times n}\), which can be either directly the adjacency matrix of the graph or various notions of graph Laplacians. We define an associated **graph shift operator**\(\mathbf{S}:L^{2}_{\sqcup}\to L^{2}_{\sqcup}\) such that the restriction \(\mathbf{S}_{|L^{2}_{q}}\) is a compact linear operator of \(L^{2}_{q}\) onto itself. Note that we reserve "matrix" and "operator" respectively for the discrete and continuous versions. The results in Sec. 3 will be valid under generic convergence assumptions from \(S\) to \(\mathbf{S}\), while the results of Sec. 4 will focus on the following two representative examples.

**Example 1** (Normalized adjacency matrix and kernel operator).: _Here \(S=\bar{A}=(n\alpha_{n})^{-1}A\) and \(\mathbf{S}f=\mathbf{A}f=\int w(\cdot,x)dP(x)\). This choice requires to know, or estimate, the sparsity level \(\alpha_{n}\). In this case, our results will hold whenever \(\alpha_{n}\gtrsim(\log n)/n\) with an arbitrary multiplicative constant._

**Example 2** (Normalized Laplacian matrix1 and operator).: _Here \(S=L=D_{A}^{-1/2}AD_{A}^{-1/2}\) where \(D_{A}=\operatorname{diag}(A1_{n})\) is the degree matrix of \(G\), and \(\mathbf{S}f=\mathbf{L}f=\int\frac{w(\cdot,x)}{\sqrt{d(\cdot)d(x)}}dP(x)\) where \(d(\cdot)=\int w(\cdot,x)dP(x)\) is the degree function. Whenever we opt for this choice, we assume that \(d_{\min}\stackrel{{ iid}}{{\equiv}}\inf_{\mathcal{X}}d(x)>0\), and our results will hold whenever \(\alpha_{n}\geqslant C(\log n)/n\) with a multiplicative constant \(C\) that depends (in a non-trivial way) on \(w\), see Thm. 9 in App. D._

Footnote 1: Note that the normalized Laplacian is traditionally defined as \(\operatorname{Id}-L\), here it does not change our definition of GNNs since they include residual connections

To sometimes unify notations, when we adopt these examples, we define \(w_{\mathbf{S}}\) such that \(w_{\mathbf{S}}(x,y)=w(x,y)\) in the adjacency case and \(w_{\mathbf{S}}(x,y)=\frac{w(x,y)}{\sqrt{d(x)d(y)}}\) in the normalized Laplacian case. Therefore for these two examples the continuous operator has a single expression \(\mathbf{S}f=\int w_{\mathbf{S}}(\cdot,x)dP(x)\).

Graph Neural Network.As mentioned in the introduction, we focus on _equivariant_ GNNs that can compute functions over _nodes_, as this makes the most sense on large graphs that RGs seek to model. Recall that we observe a graph shift operator \(S\) and node features \(Z\in\mathbb{R}^{n\times p}\), and we return a vector per nodes \(\Phi(S,Z)\in\mathbb{R}^{n\times d_{L}}\). We adopt a traditional message-passing neural network (MPNN) that uses the graph shift matrix \(S\): given input features \(Z^{(0)}\in\mathbb{R}^{n\times d_{0}}\),

\[Z^{(\ell)} =\rho\left(Z^{(\ell-1)}\theta_{0}^{(\ell-1)}+SZ^{(\ell-1)}\theta_ {1}^{(\ell-1)}+1_{n}(b^{(\ell)})^{\top}\right)\in\mathbb{R}^{n\times d_{\ell}},\] \[\Phi_{\theta}(S,Z^{(0)}) =Z^{(L-1)}\theta^{(L-1)}+1_{n}(b^{(L)})^{\top} \tag{2}\]
where \(\rho\) is the ReLU function applied element-wise, and \(\theta^{(\ell)}_{i}\in\mathbb{R}^{d_{\ell}\times d_{\ell+1}}\), \(b^{(\ell)}\in\mathbb{R}^{d_{\ell}}\) are learnable parameters gathered in \(\theta\in\Theta\). We denote by \(\Theta\) the set of all possible parameters. We note that here we employ the ReLU function as a non-linearity, as some of our results will use its specific properties. Multi-Layer Perceptrons (MLP, densely connected networks) using the ReLU activation, and with potentially more than one hidden layer, will be denoted by \(f^{\text{MLP}}_{\gamma}\), where \(\gamma\) gathers their parameters.

Following recent literature [12, 13], we consider inputing _Positional Encoding_ (PE) at each node. Such PE are generally computed using only the graph structure and concatenated to existing node features \(Z\), here we simply introduce a generic notation:

\[Z^{(0)}=\text{PE}_{\gamma}(S,Z)\in\mathbb{R}^{n\times d_{0}} \tag{3}\]

with some parameter \(\gamma\in\Gamma\). In our notations, the PE module uses the node features \(Z\), generally by concatenating them to its output. For short, we may denote the whole architecture with PE and GNN as \(\Phi_{\theta,\gamma}(S,Z)\stackrel{{\text{\tiny def.}}}{{=}} \Phi_{\theta}(S,\text{PE}_{\gamma}(S,Z))\). It is not difficult to see that if the PE computation is equivariant, then the whole GNN is equivariant: denoting by \(\sigma\) a permutation matrix of \(\{1,\dots,n\}\),

\[\forall\sigma,\ \Phi_{\theta,\gamma}(\sigma S\sigma^{\top},\sigma Z)= \sigma\Phi_{\theta,\gamma}(S,Z)\quad\Leftrightarrow\quad\forall\sigma,\ \text{PE}_{\gamma}(\sigma S\sigma^{\top},\sigma Z)=\sigma\text{PE}_{\gamma}(S, Z).\]

All the examples of PEs examined in Sec. 4 are equivariant.

## 3 Function spaces of Graph Neural Networks

In this section, we provide a complete and intuitive description of the function space approximated by equivariant GNNs applied on RGs. All technical proofs are provided in App. A. It has been shown [24, 25, 8, 29] that GNNs converge to functions over the latent space: when the node features are a sampling of a certain function \(\iota_{X}f^{(0)}\), then the output of the GNN is close to being a sampling of another function \(\iota_{X}f^{(L)}\). Assuming the node features or PEs approximate some function set \(\mathcal{B}\subset L^{2}_{\sqcup}\), we define the space of functions that a GNN can approximate as follows.

**Definition 1**.: _Given a base set \(\mathcal{B}\subset L^{2}_{\sqcup}\), the **set of functions approximated by GNNs**\(\mathcal{F}_{\mathrm{GNN}}(\mathcal{B})\) is formed by all the functions \(f\in L^{2}_{\sqcup}\) such that: for all \(\varepsilon>0\), there are \(\theta\in\Theta,f^{(0)}\in\mathcal{B}\) such that_

\[\mathbb{P}\Big{(}\left\|\Phi_{\theta}(S,\iota_{X}f^{(0)})-\iota_{X}f\right\|_ {\mathrm{MSE}}\geqslant\varepsilon\Big{)}\xrightarrow[n\to\infty]{}0. \tag{4}\]

In other words, \(\mathcal{F}_{\mathrm{GNN}}(\mathcal{B})\) are the functions whose sampling can be \(\varepsilon\)-approximated by the output of a GNN, with probability going to \(1\) as \(n\) grows. Note that if the quantifiers of \(\theta,f^{(0)}\) and \(\varepsilon\) were reversed, the MSE would converge to \(0\) in probability. Here this is _not_ the case: \(\theta,f^{(0)}\)_may depend on_\(\varepsilon\), which is akin to an approximation level. Similar to the permutation equivariance of GNNs, there is a notion of continuous equivariance for functions well-approximated by GNNs [24, 25, 8], where the permutations are replaced by bijections over the latent space \(\mathcal{X}\). We adopt the notations \(\mathcal{F}_{\mathrm{GNN}}(\mathcal{B})=\mathcal{F}_{\mathrm{GNN}}(\mathcal{B },w,P)\). For all continuous bijections \(\phi\) over \(\mathcal{X}\), we define \(w_{\phi}(x,y)=w(\phi(x),\phi(y))\), \(P_{\phi}=\phi^{-1}\sharp P\) where \(\sharp\) is the push-forward operation, and \(\mathcal{B}_{\phi}=\{f\circ\phi\ |\ f\in\mathcal{B}\}\). Then, we have the following result.

**Proposition 1**.: _Let \(S=S(A)\) be a graph shift operator that only depends on the adjacency matrix of the graph in a permutation-equivariant manner. Then, for all continuous bijections \(\phi:\mathcal{X}\to\mathcal{X}\),_

\[\mathcal{F}_{\mathrm{GNN}}(\mathcal{B}_{\phi},w_{\phi},P_{\phi})= \left\{f\circ\phi\ |\ f\in\mathcal{F}_{\mathrm{GNN}}(\mathcal{B},w,P)\right\}.\]

That is, if one "permutes" the kernel \(w\), the distribution \(P\) and the base set \(\mathcal{B}\), then the function space \(\mathcal{F}_{\mathrm{GNN}}\) contains exactly the permuted version of the original space.
The goal of this section is to provide a more intuitive description of the space \(\mathcal{F}_{\mathrm{GNN}}\), which we will do under some basic convergence assumption from \(S\) to \(\mathbf{S}\). GNNs (2) basically include two components: dense connections and MLPs that can approximate any continuous function by the universality theorem [40], and applications of \(S\). Hence, we define the following function space.

**Definition 2**.: _We define \(\mathcal{F}_{\mathbf{S}}(\mathcal{B})\subset L^{2}_{\sqcup}\) the (minimal) \(\mathbf{S}\)**-extension** of a base set \(\mathcal{B}\subset L^{2}_{\sqcup}\) by the following rules:_

1. _Base space:_ \(\mathcal{B}\subset\mathcal{F}_{\mathbf{S}}(\mathcal{B})\)_;_
2. _Stability by composition with continuous functions:_ _for all_ \(f\in\mathcal{F}_{\mathbf{S}}(\mathcal{B})\) _with a_ \(p\)_-dimensional output and_ \(g\in\mathcal{C}_{\mathrm{Lip}}(\mathbb{R}^{p},\mathbb{R}^{q})\)_, it holds_2 _that_ \(g\circ f\in\mathcal{F}_{\mathbf{S}}(\mathcal{B})\)_;_ Footnote 2: Note that, since \(g\) is Lipschitz, when \(f\in L^{2}_{\sqcup}\) we indeed have \(g\circ f\in L^{2}_{\sqcup}\).
3. _Stability by graph operator:_ _for all_ \(f\in\mathcal{F}_{\mathbf{S}}(\mathcal{B})\)_, it holds that_ \(\mathbf{S}f\in\mathcal{F}_{\mathbf{S}}(\mathcal{B})\)_;_
4. _Linear span:_ _for all_ \(q\)_,_ \(\mathcal{F}_{\mathbf{S}}(\mathcal{B})\cap L^{2}_{q}\) _is a vector space;_
5. _Closure:_ \(\mathcal{F}_{\mathbf{S}}(\mathcal{B})\) _is closed in_ \(L^{2}_{\sqcup}\)_;_
6. _Minimality:_ _for all_ \(\mathcal{G}\subset L^{2}_{\sqcup}\) _satisfying all the properties above,_ \(\mathcal{F}_{\mathbf{S}}\subset\mathcal{G}\)_._

In words, \(\mathcal{F}_{\mathbf{S}}\) take a base set \(\mathcal{B}\), and extend it to be stable by composition with Lipschitz functions, application of the graph operator, and linear combination (of its elements with the same dimensionality). Our result will use the following assumption, which is naturally true for our running examples.

**Assumption 1**.: _With probability going to \(1\), \(\|S\|\) is bounded. Moreover, for all \(f\in L^{2}_{\sqcup}\),_

\[\left\|S_{tX}f-\iota_{X}\mathbf{S}f\right\|_{\mathrm{MSE}}\xrightarrow[n\to \infty]{\mathcal{P}}0\]

_where \(\xrightarrow[n]{\mathcal{P}}\) indicates convergence in probability._

**Proposition 2**.: _Assumption 1 is true for the adjacency matrix (ex. 1) and normalized Laplacian (ex. 2)._

Under this assumption, the main result of this section states that the functions well-approximated by GNNs are exactly the \(\mathbf{S}\)-extension of the base input features \(\mathcal{B}\).

**Theorem 1**.: _Under Assumption 1, for all \(\mathcal{B}\subset L^{2}_{\sqcup}\), we have:_

\[\mathcal{F}_{\mathrm{GNN}}(\mathcal{B})=\mathcal{F}_{\mathbf{S}}(\mathcal{B})\]

Given the definition of GNNs (2) and construction of \(\mathcal{F}_{\mathbf{S}}\), Theorem 1 appears quite natural. Its proof, provided in App. A.3, is however far from trivial. The inclusion \(\mathcal{F}_{\mathbf{S}}(\mathcal{B})\subset\mathcal{F}_{\mathrm{GNN}}( \mathcal{B})\) is similar in spirit to previous convergence results [24], since one has to construct a GNN that approximates a particular function. It involves however a new extended universality theorem for MLPs for square-integrable functions (Lemma 3 in App. A.3), which uses the _special properties of ReLU_. The reverse inclusion \(\mathcal{F}_{\mathrm{GNN}}(\mathcal{B})\subset\mathcal{F}_{\mathbf{S}}( \mathcal{B})\) is quite different from previous work on GNN convergence: given \(f\in\mathcal{F}_{\mathrm{GNN}}(\mathcal{B})\) whose only property is to be well-approximated by GNNs, one must construct a sequence of functions in \(\mathcal{F}_{\mathbf{S}}(\mathcal{B})\) that converge to \(f\), and uses the closure of \(\mathcal{F}_{\mathbf{S}}(\mathcal{B})\). The need to work within square-integrable function is here obvious, as we only have convergence of the MSE, an approximation of the \(L^{2}\)-norm. For instance, this inclusion would not be true in the space of continuous functions.

Using composition with continuous functions, if \(\mathcal{F}_{\mathbf{S}}(\mathcal{B})\) contains a continuous bijection \(\phi:\mathcal{X}\to\mathrm{Im}(\phi)\), then \(\mathcal{F}_{\mathbf{S}}(\mathcal{B})\) contains all continuous functions, and by density all square integrable functions. That is, the equivariant GNNs are then **universal** over \(\mathcal{X}\): they can generate any function to label the nodes. Another criterion using the Stone-Weierstrass theorem (e.g. [21]), similar to the proofs in [25], is the following.
**Proposition 3**.: _Assume that for all \(x\neq x^{\prime}\) in \(\mathcal{X}\), there is a continuous function \(f\in\mathcal{F}_{\mathbf{S}}(\mathcal{B})\cap\mathcal{C}_{\mathrm{Lip}}( \mathcal{X},\mathbb{R})\) such that \(f(x)\neq f(x^{\prime})\). Then, \(\mathcal{F}_{\mathbf{S}}(\mathcal{B})=L^{2}_{\sqcup}\)._

In the rest of the paper, we study several examples of PEs and corresponding set \(\mathcal{B}\), that will generalize the results of [25]. We expect many other interesting characteristics of \(\mathcal{F}_{\mathbf{S}}\) to be derived in the future.

## 4 Node features and Positional encodings

In the previous section, we have provided a complete description of the function space generated by equivariant GNNs when fed samplings of functions as node features, and the set of \(\mathcal{B}\) is thus crucial for the properties of \(\mathcal{F}_{\mathbf{S}}(\mathcal{B})\). For instance, in the absence of node features and PEs, it is classical to input _constant features_ to GNNs [25], such that the space of interest is \(\mathcal{F}_{\mathbf{S}}(1)\). However, similar to the failure of the WL test on regular graphs, if \(\mathbf{S}1\propto 1\) (e.g. constant degree function), then \(\mathcal{F}_{\mathbf{S}}(1)\)_contains only constant functions_! The role of PEs is often to mitigate such situations.

**Definition 3**.: _The **set of functions approximated by PEs**\(\mathcal{F}_{\mathrm{PE}}\) is formed by all the functions \(f\in L^{2}_{\sqcup}\) such that: for all \(\varepsilon>0\), there is \(\gamma\in\Gamma\) such that_

\[\mathbb{P}\Big{(}\left\|\mathrm{PE}_{\gamma}(S,Z)-\iota_{X}f\right\|_{ \mathrm{MSE}}\geqslant\varepsilon\Big{)}\xrightarrow[n\to\infty]{}0\,. \tag{5}\]

Note that, as before, \(\gamma\) may depend on \(\varepsilon\). When passing PEs as input to GNNs, \(\mathcal{F}_{\mathrm{PE}}\) serves as the base space \(\mathcal{B}\), and the space of interest to characterize the functions well approximated by the whole architecture \(\Phi_{\theta,\gamma}\) is therefore \(\mathcal{F}_{\mathbf{S}}(\mathcal{F}_{\mathrm{PE}})\). In fact, by simple Lipschitz property: for any \(f\in\mathcal{F}_{\mathbf{S}}(\mathcal{F}_{\mathrm{PE}})\) and \(\varepsilon>0\), there are \(\theta\in\Theta,\gamma\in\Gamma\) such that

\[\mathbb{P}\Big{(}\left\|\Phi_{\theta,\gamma}(S,Z)-\iota_{X}f\right\|_{ \mathrm{MSE}}\geqslant\varepsilon\Big{)}\xrightarrow[n\to\infty]{}0\]

In the rest of the section, we therefore aim to characterize \(\mathcal{F}_{\mathrm{PE}}\) for several representative examples. We first briefly comment on observed node features, then move on to PEs. Proofs are in App. B.

### Node features

A first, simple example, is when observed node features are actually a sampling of some function \(Z=\iota_{X}f^{(0)}\). This is a convenient choice that is often adopted in the literature [24, 25, 23, 8, 29]. In this case, by adopting the identity \(\mathrm{PE}_{\gamma}(S,Z)=Z\), it is immediate that \(\mathcal{F}_{\mathrm{PE}}=\{f^{(0)}\}\). A more realistic example is the presence of centered noise:

\[Z=\iota_{X}f^{(0)}+\nu\in\mathbb{R}^{n\times d_{0}} \tag{6}\]

where \(\nu=[\nu_{1},\dots,\nu_{n}]\) and the \(\nu_{i}\) are i.i.d. noise vectors with \(\mathbb{E}\nu_{i}=0\) and \(\mathrm{Cov}(\nu_{i})=C_{\nu}\). This time, \(\mathcal{F}_{\mathrm{PE}}\) cannot contain directly \(f^{(0)}\), as the Law of Large Numbers (LLN) gives

\[\left\|Z-\iota_{X}f^{(0)}\right\|_{\mathrm{MSE}}^{2}=\left\|\nu\right\|_{ \mathrm{MSE}}^{2}\xrightarrow[n\to\infty]{}\mathrm{Tr}(C_{\nu})>0\]

However, when applying the graph shift matrix at least once, one obtains convergent PEs.

**Proposition 4**.: _Consider the adjacency matrix (ex. 1) or normalized Laplacian (ex. 2). If the node features are a noisy sampling (6) and the PE are defined \(\mathrm{PE}_{\gamma}(S,Z)=SZ\), then, \(\mathcal{F}_{\mathrm{PE}}=\{\mathbf{S}f^{(0)}\}\)._

Of course this may not be the only possibility for removing noise from node features, and moreover it is not clear how realistic the node features model (6) actually is. The study of more refined models linking graph structure and node features is a major path for future work.
### Positional Encodings

In this section, we consider classical PEs computed solely from the graph structure and show how they articulate with our framework. We consider two examples that are the most-often used in the literature: PEs as eigenvectors of the graph shift matrix [12, 13] (actually a recent variant that account for sign indeterminancy [31]), and PE based on distance-encoding [30] (again a variant that, as we will see, generalize other architectures [49]). For most of the results below, we will focus on two representative cases of kernels, that include many practical examples:

**Example a** (Stochastic Block Models).: _In this case, the space of latent variables \(\mathcal{X}=\{1,\ldots,K\}\) is finite, each element correspond to a community label. The kernel \(w\) is represented by a matrix \(C\stackrel{{\text{\tiny def.}}}{{=}}[w(\ell,k)]\in\mathbb{R}_{+} ^{K\times K}\) that gives the probability of connection between communities \(\ell\) and \(k\), and \(P\in\mathbb{R}_{+}^{K}\) is a probability vector of size \(K\) that sum to \(1\)._

**Example b** (P.s.d. kernel).: _Here we assume that \(w\) is positive semi-definite (p.s.d.). This includes for instance the Gaussian kernel._

For any symmetric matrix (resp. self-adjoint compact operator) \(M\), we denote by \(\lambda_{i}^{M}\) its eigenvalues and \(u_{i}^{M}\) its eigenvectors (resp. eigenfunctions), with any arbitrary choice of sign or basis here. Since in all our examples operators are either p.s.d. or finite-rank, the eigenvalues are ordered as such: first the non-zero eigenvalues by decreasing order (from positive to negative), then all zero eigenvalues.

#### 4.2.1 Eigenvectors and SignNet

It has been proposed [12, 13] to feed the first \(q\) eigenvectors of the graph into the GNN, for a fixed \(q\). A potential problem with this approach is the sign ambiguity of the eigenvectors, or even the basis ambiguity in case of eigenvalues with multiplicities. Here we consider only the sign ambiguity for simplicity: we will assume that the first eigenvalue of \(\mathbf{S}\) are distinct. The sign ambiguity was alleviated in [31] by taking a _sign-invariant_ function: considering an eigenvector \(u_{i}^{S}\) of \(S\),

\[(\mathbf{Q}f)(u_{i}^{S})\stackrel{{\text{\tiny def.}}}{{=}}f(u_{ i}^{S})+f(-u_{i}^{S})\in\mathbb{R}^{n\times p} \tag{7}\]

where \(f:\mathbb{R}\rightarrow\mathbb{R}^{p}\) is a function applied to each coordinate of \(u_{i}^{S}\) to preserve permutation-equivariance. The resulting function is sign-invariant, and one can parameterized \(f\). Given the first \(q\) eigenvectors \(u_{i}^{S}\) and a collection of MLPs \(f_{\gamma_{i}}^{\text{MLP}}:\mathbb{R}\rightarrow\mathbb{R}^{p_{i}}\) for some output dimensions \(p_{i}\), the PE considered in this subsection concatenates the outputs:

\[\text{PE}_{\gamma}(S)=[(\mathbf{Q}f_{\gamma_{i}}^{\text{MLP}})(\sqrt{n}u_{i} ^{S})]_{i=1}^{q}\in\mathbb{R}^{n\times p} \tag{8}\]

where \(p=\sum_{i=1}^{q}p_{i}\) and the MLP are applied element-wise. The parameter \(\gamma\) gathers the \(\gamma_{i}\). The equation (8) involves a renormalization of the eigenvectors \(u^{S}\) by the square root of the size of the graph \(\sqrt{n}\): indeed, as \(u_{i}^{S}\) is normalized _in_\(\mathbb{R}^{n}\), this is necessary for consistency across different graph sizes. See Sec. 4.2.3 for a discussion and some numerical illustrations.

As can be expected, the eigenvectors of \(S\) generally converge to the eigenfunctions of \(\mathbf{S}\), under a spectral gap assumption. We provide the theorem below which handles all of our running examples. We suppose that the relevant eigenvalues have single multiplicities, to only have sign ambiguity.

**Theorem 2**.: _Consider either SBM (ex. a) or p.s.d. kernel (ex. b), and either adjacency matrix (ex. 1) or normalized Laplacian (ex. 2). Fix \(q\), assume the first \(q+1\) eigenvalues \(\lambda_{1}^{\mathbf{S}},\ldots,\lambda_{q+1}^{\mathbf{S}}\) of \(\mathbf{S}\) are two-by-two distinct. We define_

\[\mathcal{F}_{\mathrm{Eig}}\stackrel{{\text{\tiny def.}}}{{=}} \left\{[(\mathbf{Q}f_{i})\circ u_{i}^{\mathbf{S}\dagger q}_{i}]=1\ |\ f_{i}\in\mathcal{C}_{\mathrm{Lip}}(\mathbb{R},\mathbb{R}^{p_{i}}),p_{i}\in \mathbb{N}^{*}\right\} \tag{9}\]

_Then \(\mathcal{F}_{\mathrm{PE}}=\overline{\mathcal{F}_{\mathrm{Eig}}}\)._

Hence \(\mathcal{F}_{\mathrm{PE}}\) contains the eigenfunctions of \(\mathbf{S}\), modified by the SignNet architecture to account for the sign indeterminancy. We further discuss this space in Sec. 4.2.3. An illustration is provided in Fig. 1.
#### 4.2.2 Distance-encoding PEs

In [30], the authors propose to define PEs through the aggregation of a set of "distances" \(\xi(i,j)\) from each node \(i\) to a set \(j\in V_{T}\) of target nodes (typically, labelled nodes in semi-supervised learning, or anchor nodes selected randomly [56]):

\[(\text{PE}_{\gamma})_{i,:}=\text{AGG}(\{\xi(i,j)\ |\ j\in V_{T}\})\]

where AGG is an _aggregation_ function that acts on (multi-)sets, and \(\xi(i,j)\) is selected in [30] as random-walk based distances \(\xi(i,j)=[(AD_{A}^{-1})_{ij},\ldots,((AD_{A}^{-1})^{q})_{ij}]\in\mathbb{R}^{q}\). For simplicity, since here we do not consider any particular set of target nodes, we just consider \(V_{T}=V\) the set of all nodes. Moreover, to use our convergence results, we replace the random walk matrix with our graph shift matrix \(S\). As aggregation, we opt for the deep-set architecture [58], which applies an MLP on each \(\xi(i,j)\) then a sum. Deep sets can approximate any permutation-invariant function. As we will see below, with the proper normalization to ensure convergence, we obtain:

\[\text{PE}_{\gamma}=\tfrac{1}{n}\sum_{j}f_{\gamma}^{\text{MLP}}\left(n\cdot[Se _{j},\ldots,S^{q}e_{j}]\right)\in\mathbb{R}^{n\times q}\]

where \(f_{\gamma}^{\text{MLP}}:\mathbb{R}^{q}\rightarrow\mathbb{R}^{p}\) is applied row-wise and \(e_{j}\in\mathbb{R}^{n}\) are one-hot basis vectors. We note that a similar architecture was proposed in a different line of work: it was called Structured Message Passing by [49], or Structured GNN by [25]. In these works, the inspiration is to give nodes unique identifiers, _e.g._, one-hot encodings \(e_{i}\). However, this process is not equivariant. To restore equivariance, [49] propose a deep-set pooling in the "node-id" dimension \(\text{PE}_{\gamma}(S)=\sum_{j}\Phi_{\gamma}(S,e_{j})\), where \(\Phi_{\gamma}\) is itself a permutation-equivariant GNN, and the equivariance of \(\text{PE}_{\gamma}\) is restored. By choosing \(\Phi_{\gamma}(\mathbf{S},e_{j})=n^{-1}f_{\gamma}^{\text{MLP}}\left(n\cdot[Se _{j},\ldots,S^{q}e_{j}]\right)\) (which is a valid choice for a message-passing GNN), we obtain exactly distance-encoding PEs above.

In [25], powerful universality results were shown for this choice of architecture _in the case of non-random edges_\(a_{ij}=w(x_{i},x_{j})\) and \(q=1\). With our notations, they implicitely studied PE functions of the following form: \(\int f(w(\cdot,x))dP(x)\). This allows to _modify the values of the kernel_ before computing the degree function, and can therefore break potential indeterminancy such as constant degrees. Unfortunately, their proof technique and the concentration inequalities they use are _not true anymore for Bernoulli random edges_, which are far more realistic than deterministic weighted edges. Here we show that for a large class of kernels, concentration can be restored when we add an MLP filter on the eigenvalues of \(S\) with ReLU. Our definition of distance-encoding PEs is therefore:

\[\text{PE}_{\gamma}=\tfrac{1}{n}\sum_{j}f_{\gamma_{1}}^{\text{MLP}}\left(n \cdot[S_{\gamma_{2}}e_{j},\ldots,S_{\gamma_{2}}^{q}e_{j}]\right) \tag{10}\]

where \(S_{\gamma_{2}}\stackrel{{\text{\tiny def.}}}{{=}}h_{f_{\gamma_{2} }^{\text{MLP}}}(S)\) is a filter that applies an MLP \(f_{\gamma_{2}}^{\text{MLP}}\) on the eigenvalues of \(S\).

Figure 1: Illustration of the role of the SignNet architecture and of the renormalization by \(\sqrt{n}\) of the eigenvectors on synthetic data, with a latent space \(\mathcal{X}=[-1,1]\) (\(x\)-axis), a Gaussian kernel \(w\), and uniform distribution \(P\). Blue dots represent a graph from the training set, orange dot a test graph that is twice bigger. **From left to right:** eigenvectors with renormalization (with a different sign for the two graphs), eigenvectors without, PEs with, and PEs without, with the regression test errors of a GNN trained using these PE with or without renormalization. We observe that SignNet indeed fixed the sign ambiguity. The absence of renormalization yields unconsistent PEs across graphs of different sizes, which results in a high test error on test graphs than training graphs.
**Theorem 3**.: _Consider either SBM (ex. a) or p.s.d. kernel (ex. b), and either adjacency matrix (ex. 1) or normalized Laplacian (ex. 2). Consider the PE (10). We define_

\[\mathcal{F}_{\mathrm{Dist}}\stackrel{{\text{\tiny{def.}}}}{{=}} \left\{\int f([\mathbf{S}\delta_{x}(\cdot),\ldots,\mathbf{S}^{q}\delta_{x}( \cdot)])dP(x)\ |\ f\in\mathcal{C}_{\mathrm{Lip}}([0,1]^{q},\mathbb{R}^{p}),p\in \mathbb{N}^{*}\right\} \tag{11}\]

_where \(\mathbf{S}\delta_{x}\stackrel{{\text{\tiny{def.}}}}{{=}}\{z \mapsto w_{\mathbf{S}}(z,x)\}\) by abuse of notation. Then \(\mathcal{F}_{\mathrm{Dist}}\subset\mathcal{F}_{\mathrm{PE}}\)._

Note that here we only have an inclusion \(\mathcal{F}_{\mathrm{Dist}}\subset\mathcal{F}_{\mathrm{PE}}\) instead of an equality as in Thm. 2: indeed, we show that the PE (10) can approximate functions in \(\mathcal{F}_{\mathrm{Dist}}\), but they may converge to other functions. Nevertheless, as a consequence of our analysis, all the universality results of [25, Sec. 5.3] are valid with the choice of PE (10), see Appendix C for a reminder using our notations. This is a strict, and non-trivial improvement over [25], as their results were only derived for non-random edges. For this, Theorem 3 relies mostly on a new concentration inequality for Bernoulli matrices with ReLU filters in Frobenius norm, that we give below since it is of independent interest.

**Theorem 4**.: _Consider either SBM (ex. a) or p.s.d. kernel (ex. b), and either adjacency matrix (ex. 1) or normalized Laplacian (ex. 2). Define the Gram matrix \(W=[w_{\mathbf{S}}(x_{i},x_{j})/n]_{ij}\). For all \(\varepsilon>0\), there is an MLP filter \(S_{\gamma}=h_{f_{\gamma}^{\mathrm{MLP}}}(S)\) such that_

\[\mathbb{P}(\left\|S_{\gamma}-W\right\|_{\mathrm{F}}\geqslant\varepsilon)\to 0.\]

The proof of this theorem, given in appendix B.3, is inspired by the so-called USVT estimator [7]. One notes that the use of an MLP graph filter is quite unconventional. A more classical choice is polynomial filters: this avoids the diagonalization of \(S\) by computing \(\sum_{k}a_{k}S^{k}\), it is for instance the basis for the ChebNet architecture [10]. For the purpose of Theorems 3 and 4, _polynomial filters do not work, and ReLU is of crucial importance_: indeed, we need the filter to zero-out \(\mathcal{O}\left(n\right)\) eigenvalues _uniformly_ in some interval \([-\tau,\tau]\). With polynomial, this could be done by taking learned parameters that depend on \(n\) (to get a finer approximation as \(n\) increases), but this is not allowed in our framework, where we want to generalize on large graphs \(n\to\infty\). On the other hand, when choosing \(f\) as an MLP with ReLU, due to the shape of this non-linearity, \(f_{\gamma_{2}}^{\mathrm{MLP}}\) can be _uniformly_\(0\) on a whole domain. Of course, polynomial filters offer great computational advantages, and perform well in practice, despite their flaw in our asymptotic analysis. Moreover, ReLU is technically non-differentiable. Designing filters that offer both computational advantages and exact approximation is still an open question. In practice, we observe that the ReLU-filter does learn to approximate its expected shape, when we minimize the reconstruction error \(\left\|S_{\gamma}-W\right\|_{\mathrm{F}}\) on synthetic data where \(W\) is known, see Fig. 2.

#### 4.2.3 Discussion

Approximation power.As mentioned above, in the absence of node features, one may opt for constant input, but this may lead to degenerate situations. PEs aim to counteract that, by increasing GNNs' approximation power. We quickly verify that this is indeed the case for our two examples.

**Proposition 5**.: _There are cases where \(\mathcal{F}_{\mathbf{S}}(1)\subset\mathcal{F}_{\mathbf{S}}(\mathcal{F}_{ \mathrm{Eig}})\) or \(\mathcal{F}_{\mathbf{S}}(1)\subset\mathcal{F}_{\mathbf{S}}(\mathcal{F}_{ \mathrm{Dist}})\) with strict inclusions._

Figure 2: Illustration of Theorem 4 on synthetic data where \(W\) is known, with a Gaussian kernel. Unfiltered eigenvalues of \(S\) are represented by blue crosses, filtered ones obtained by minimizing \(\min_{\gamma_{2}}\left\|S_{\gamma_{2}}-W\right\|_{\mathrm{F}}\) by orange dots, and the ideal ReLU-filter used in the proof of Thms. 3 and 4 is represented by a red line.
Moreover, as mentioned in the previous section, existing universality results [25] can be generalized in our case, see App. C. Another interesting question is somewhat the opposite: given the already rich class of functions generated by PEs, are GNNs really more powerful?

**Proposition 6**.: _There are cases where \(\mathcal{F}_{\mathrm{Eig}}\subset\mathcal{F}_{\mathbf{S}}(\mathcal{F}_{\mathrm{ Eig}})\) or \(\mathcal{F}_{\mathrm{Dist}}\subset\mathcal{F}_{\mathbf{S}}(\mathcal{F}_{ \mathrm{Dist}})\), with strict inclusions._

The proof, which is not so trivial, invokes functions with at least one round of message-passing after the computation of PEs, so the additional approximation power does not come only from MLPs. Intuitively, it seems natural that message-passing rounds are useful for other reasons, e.g. noise reduction or smoothing [23]. We leave these complementary lines of investigation for future work.

Renormalization.A striking point in our variants of PEs is the presence of various normalization factors by the graph size \(n\) to ensure convergence: the equation (8) involves a renormalization of the eigenvectors \(u^{S}\) by the square root of the size of the graph \(\sqrt{n}\), while (10) involves a multiplicative factor \(n\)_inside_ the MLP \(f_{\gamma_{1}}^{\mathrm{MLP}}\) (the \(1/n\) outside of the sum is more classical). Our analysis shows that these normalization factors are necessary for convergence when \(n\to\infty\), and more generally for consistency across different graph sizes.

In practice, this is generally not used. Indeed, if the training and testing graphs have roughly the same "range" of sizes \(n\in[n_{\min},n_{\max}]\), then a GNN model can _learn_ the proper normalization to perform, which is not the point of view of our analysis \(n\to\infty\). While in-depth benchmarking of PEs has been done in the literature [13] and is out-of-scope of this paper, we give a small numerical illustration of the effect of normalization, for a synthetic dataset (Fig. 1) and two real-world datasets that contain graphs of different sizes3 (Tab. 1). On a synthetic dataset that is exactly formed of random graphs of vastly different sizes, the renormalization is of course necessary to obtain good performance, as predicted by our theory: without it, the PEs do not converge when \(n\) grows. On real data, we see that renormalization generally helps generalization, and this is more true for IMDB-BINARY, which contains a larger range of graph sizes, and distance-based PEs. Note that here we use relatively small GNNs that are _not state-of-the-art_, as well as a different train/test split than most papers (\(K=5\) CV-folds instead of \(K=10\)): indeed, we do not want our models to _learn_ the proper normalization on the limited range of sizes \(n\) in the dataset, so we limit their number of parameters and use a smaller training set. We do not expect our simple renormalization process to make a significant difference on large-scale benchmarks with state-of-the-art models [13], but this is a pointer in an interesting direction that will be explored in the future. In particular, this type of normalization may be useful in real-world scenarii where the test graphs are far larger than the labelled training graphs.

Footnote 3: Technically, these datasets are graph-tasks instead of node-tasks. Indeed, we needed graphs of different sizes to test the renormalization, and there are few (if any) node-task datasets containing many graphs of different sizes. We perform a final pooling on our equivariant GNNs to obtain permutation-invariant versions.

## 5 Conclusion

On large random graphs, the manner in which GNNs label _nodes_ can be modelled by functions. The analysis of the resulting function spaces is still in its infancy, and of a very different nature

\begin{table}
\begin{tabular}{l r r r r} \hline \hline Dataset & \multicolumn{2}{c}{Eigenvectors} & \multicolumn{2}{c}{Distance-encoding} \\  & w/ norm. & w/o norm. & w/ norm. & w/o norm. \\ \hline IMDB-BINARY[55] & 67.80 & 66.10 & 71.10 & 63.95 \\ COLLAB[55] & 73.74 & 74.77 & 75.65 & 75.02 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Test accuracy for GNNs with different PEs, with or without renormalization by the graph size \(n\). Results for 5-fold cross-validation averaged over 3 experiments.
to the studies of _graph-tasks_, both discrete [54] or in the limit [36]. In this paper, we clarified significantly the nature of the space of functions well-approximated by GNNs on large-graphs, showing that it can be defined by a few extension rules within the space of square-integrable functions. We then showed the usefulness of Positional Encodings by analyzing two popular examples, established new universality results, as well as some concentration inequalities of independent interest. Our theory hinted at some process for consistency across graphs of different sizes that can help generalization in practice. This paper, which in large part consisted in _properly defining_ the objects of interest, is without doubt only a first step in their analysis. Future studies might look at specific settings and derive more useful properties of the space \(\mathcal{F}_{\mathbf{S}}\), more powerful PEs, a better understanding of their limitations, or more realistic models for node features.
