# Graph Neural Tangent Kernel: Convergence on Large Graphs

Sanjukta Krishnagopal  Luana Ruiz

###### Abstract

Graph neural networks (GNNs) achieve remarkable performance in graph machine
learning tasks but can be hard to train on large-graph data, where their
learning dynamics are not well understood. We investigate the training
dynamics of large-graph GNNs using graph neural tangent kernels (GNTKs) and
graphons. In the limit of large width, optimization of an overparametrized NN
is equivalent to kernel regression on the NTK. Here, we investigate how the
GNTK evolves as another independent dimension is varied: the graph size. We
use graphons to define limit objects—graphon NNs for GNNs, and graphon NTKs
for GNTKs—, and prove that, on a sequence of graphs, the GNTKs converge to the
graphon NTK. We further prove that the spectrum of the GNTK, which is related
to the directions of fastest learning which becomes relevant during early
stopping, converges to the spectrum of the graphon NTK. This implies that in
the large-graph limit, the GNTK fitted on a graph of moderate size can be used
to solve the same task on the large graph, and to infer the learning dynamics
of the large-graph GNN. These results are verified empirically on node
regression and classification tasks.

keywords

##  1 Introduction

Several real-world systems such as social-interactions, brain-connectome,
epidemic spread, recommender systems, and traffic patterns are best
represented by structured data in the form of large graphs. Graph neural
networks (GNNs) are deep neural network architectures that leverage these
graph structures to learn meaningful representations of node and edge data
(Kipf & Welling, 2017; Hamilton et al., 2017; Defferrard et al., 2016; Gama et
al., 2018). GNNs have shown remarkable empirical performance in a number of
graph machine learning tasks, but can be hard to train on large-graph data.
Recent research efforts have attempted to understand the large-graph behavior
of GNNs, and in particular why GNNs trained on small graphs scale well to
large networks (Ruiz et al., 2020; Levie et al., 2021; Keriven et al., 2020).
However, the specific learning dynamics of a GNN trained directly on the large
network, which are known to be challenging, are not as well understood.

Modern deep neural networks (DNNs) are typically overparametrized. The
benefits of overparametrization include faster convergence (Allen-Zhu et al.,
2019; Arora et al., 2018) and better generalization (Cao & Gu, 2019), but on
the other hand the parameters can be more difficult to interpret and the
learning dynamics harder to understand. A remarkable contribution of Jacot et
al. (2018) was the observation that, in the infinite width limit, learning the
weights of a DNN via gradient descent reduces to kernel regression with a
deterministic and fixed kernel called the _neural tangent kernel_ (NTK), which
captures the first-order approximation of the neural network’s evolution
during gradient descent (Lee et al., 2019). Since its introduction, the NTK
has been an important and widely-studied tool in the machine learning toolbox,
and kernel regression using the NTK has shown strong performance on small
datasets (Arora et al., 2019b).

In the graph case, it is straightforward to define the NTK associated with a
GNN, or the graph neural tangent kernel (GNTK) (Du et al., 2019). The GNTK
allows studying the training dynamics of the GNN when the number of features
(the analog of width in the DNN) is large. Nonetheless, the effect of graph
size on the GNN learning dynamics, which can itself be thought of as another
‘width dimension’, is not well understood, and there is limited research that
investigates this rigorously. Herein, we propose to to understand the training
dynamics of GNNs that are wide in both of these senses by combining the NTK
formalism with the theory of graphons (Lovász, 2012; Borgs et al., 2008).

A graphon is a symmetric bounded measurable function
${\mathbf{W}}:[0,1]^{2}\rightarrow[0,1]$ representing the limit of a sequence
of dense graphs. It can also be interpreted as a random graph model, in which
case we can use the graphon to sample stochastic graphs. The interpretation of
${\mathbf{W}}$ as both a graph limit and a random graph model makes it so that
each graphon defines a family of similar graphs. Hence, one can expect
properties of a graphon to generalize, in a probabilistic sense, the
properties of graphs belonging to its family. Graphons have been used to study
the limit behavior of GNNs, which converge to so-called graphon neural
networks (WNNs) (Ruiz et al., 2020). The fact that GNNs have a limit on the
graphon implies that they are transferable across graphs in the same family,
thus allowing a GNN to be trained on a graph of moderate size and transferred
to a larger graph.

###  1.1 Contributions

In this paper, our first contribution is to define the graphon NTK (WNTK)
associated with the WNN (Sec. 4). We then prove, using mathematical induction,
that the GNTK converges to the WNTK (Thm. 5.1). In practice, this implies that
GNTKs, like GNNs, are transferable across graphs of different sizes associated
with the same graphon. That is to say, one can subsample a small graph and the
corresponding data from a large graph, then fit the subsampled data to the
small-graph GNTK via kernel regression, and then transfer the fitted model to
the large-graph GNTK, which is particularly important for large graphs.

A more important implication of the convergence of the GNTK is that it is
possible to understand the training dynamics of GNNs on large graphs by
analyzing the behavior of the corresponding GNTK in graphs of moderate size.
For instance, the eigenvalues of the NTK are associated with the speed of
convergence along the corresponding eigendirections (Jacot et al., 2018). In
Thm. 5.2, we show that the eigenvalues of the graph GNTK, which indicate the
directions of fastest convergence of the GNN, converge to the eigenvalues of
the WNTK. This allows these eigenvalues to be estimated from GNTKs associated
with smaller graphs. Lastly, we verify our theoretical results in three
numerical applications: prediction of opinion dynamics on random graphs, movie
recommendation using the MovieLens dataset, and node classification on the
Cora, CiteSeer and PubMed networks. We observe the convergence of the GNTK
(Sec. 6.1), the effect of width in kernel regression and GNN training (Sec.
6.2), and the convergence of the GNTK eigenvalues on sequences of graphs (Sec.
6.3).

Let $\boldsymbol{\Phi}({\mathbf{x}},{\mathcal{H}})$ be a neural network where
${\mathbf{x}}\in{\mathbb{R}}^{d}$ is the input data and ${\mathcal{H}}$ is a
set containing the neural network’s learnable weights, which we stack in the
vector ${\mathbf{h}}\in{\mathbb{R}}^{|{\mathcal{H}}|}$. Consider the first-
order Taylor approximation of $\boldsymbol{\Phi}$ with respect to
${\mathbf{h}}$, explicitly

$\boldsymbol{\Phi}({\mathbf{x}},{\mathcal{H}})-\boldsymbol{\Phi}({\mathbf{x}},{\mathcal{H}}_{0})\approx\nabla_{\mathbf{h}}\boldsymbol{\Phi}({\mathbf{x}},{\mathcal{H}}_{0})^{T}({\mathbf{h}}-{\mathbf{h}}_{0})\text{.}$
(1)

Since this expression is linear in the model weights ${\mathbf{h}}$, if the
neural network is close to its linear approximation, finding the optimal
weights ${\mathbf{h}}$ consists of solving a linear regression where the
inputs ${\mathbf{x}}$ are modified by the function
$\nabla_{\mathbf{h}}\boldsymbol{\Phi}({\mathbf{x}},{\mathcal{H}}_{0})^{T}$.
Seeing this function as a feature map, we can define the corresponding kernel
$\boldsymbol{\Theta}({\mathbf{x}},{\mathbf{x}}^{\prime})=\nabla_{\mathbf{h}}\boldsymbol{\Phi}({\mathbf{x}},{\mathcal{H}}_{0})^{T}\nabla_{\mathbf{h}}\boldsymbol{\Phi}({\mathbf{x}}^{\prime},{\mathcal{H}}_{0})$.
This kernel—which depends only on the initial weights ${\mathcal{H}}_{0}$—is
called the neural tangent kernel or NTK (Jacot et al., 2018). In (Jacot et
al., 2018), it was shown that, in the infinite width limit as $d\to\infty$,
the neural network $\boldsymbol{\Phi}$ behaves very similarly to its linear
approximation. To see this, let ${\mathbf{y}}\in{\mathbb{R}}^{d}$ be target
output we are trying to approximate with $\boldsymbol{\Phi}$. When the neural
network has infinitely many parameters, a small change in ${\mathcal{H}}$ can
lead to a large change in $\boldsymbol{\Phi}({\mathbf{x}},{\mathcal{H}})$.
Hence, the change in ${\mathcal{H}}$ has to be very small in order for
$\boldsymbol{\Phi}$ not to deviate from its current estimate of
${\mathbf{y}}$. In other words, ${\mathcal{H}}$ stays almost constant (close
to ${\mathcal{H}}_{0}$), making it so that the first-order Taylor
approximation is accurate. In practice, the NTK is important because it helps
understand the training dynamics of wide neural networks. For example, the
eigenvalues of $\boldsymbol{\Theta}$ determine the speed at which training
converges along each eigendirection of the kernel. The NTK associated with
standard, fully connected neural networks has been the subject of much
research, and a handful of works have studied the graph NTK (GNTK) associated
with GNNs where the graph ${\mathbf{G}}$ is seen as the input data, such as in
graph classification, where the graphs (e.g., molecules) tend to be small. On
the other hand, the behavior of wide GNNs on node-level tasks, where the node
data varies but the graphs are fixed and typically large (e.g., user
similarity networks in recommendation systems), remains to be understood. At
Simons, Sanjukta Krishnagopal and I worked on this problem by defining the
appropriate GNTK and studying its convergence to the graphon NTK on dense
graphs. The convergence of the GNTK follows from the fact that the graph
spectra converges to the graphon spectra, and uses similar steps as the proof
of convergence of GNNs in (Jacot et al., 2018). In a preliminary set of
experiments, we observe that, in the same way that the NTK provides a good
approximation of fully connected neural networks as their width increases, the
GNTK provides a good approximation of the GNN as the number of features in its
layers increases. This is illustrated in Fig. LABEL:fig:wntk for GNNs with
$50$, $500$, and $1000$ features per layer trained to solve a consensus task.
In our future work, we plan on running experiments on graphs of growing size,
to analyze the convergence of the GNTK; and on understanding the influence of
the graph and graphon spectra in the spectra of the GNTK and of the WNTK. This
work will be featured in a paper under preparation for submission at ICML
2023.

##  2 Related Work

Neural tangent kernels. The connection between infinitely wide DNNs and kernel
methods (Gaussian processes) has been known since the 1990s (Neal & Neal,
1996; Williams, 1996), but a more theoretical formulation was presented by
Jacot et al. (2018), which introduced the NTK and proved its constancy
property in the infinite width limit, with Liu et al. (2020) later showing
that constancy only holds for architectures with linear output layer. Several
works have derived NTKs for a generalized classes of neural networks,
including convolutional neural networks (Arora et al., 2019a; Li et al.,
2019), ResNets (Huang et al., 2020) and, most closely related to our work,
GNNs (Du et al., 2019).

Graphons and size generalization in deep learning. Graphons have been used to
understand GNN convergence and transferability (Ruiz et al., 2020, 2021a;
Maskey et al., 2023), to analyze the generalization properties of GNNs in
large graphs (Maskey et al., 2022), and to propose more computationally
efficient training algorithms for large-scale GNNs (Cerviño et al., 2023).
More recently, Xia et al. (2022) proposed implicit graphon neural
representations, which use neural networks to estimate graphons.

Yehudai et al. (2021) study graphs in which the local structure depends on the
graph size—which is analogous to the dense graphs associated with graphons—,
and find that GNNs are not guaranteed to scale to large graph sizes. However,
their result foregoes the normalization of the adjacency matrix by the graph
size, while we leverage this normalization to show operator norm convergence
of the kernels associated with the graph convolution. It is also worth noting
that our work is fundamentally different than GNN convergence or
transferability results, because it relates not to the GNN architecture but to
the GNN learning dynamics, and uses a mathematical induction proof as opposed
to the spectral convergence argument typically used in GNN convergence proofs.

##  3 Graph and Graphon Neural Networks

Let ${\mathbf{G}}_{n}=({\mathcal{V}},{\mathcal{E}},w)$ be a graph where
${\mathcal{V}}$, $|{\mathcal{V}}|=n$, is the set of nodes or vertices,
${\mathcal{E}}\subseteq{\mathcal{V}}\times{\mathcal{V}}$ is the set of edges
and $w:{\mathcal{E}}\to{\mathbb{R}}$ is a map assigning weights to the edges
in ${\mathcal{E}}$. The size-normalized adjacency matrix of
${\mathbf{G}}_{n}$, denoted ${\mathbf{A}}_{n}\in{\mathbb{R}}^{n\times n}$, is
given by $[{\mathbf{A}}]_{ij}=w(i,j)/n$. In this paper we focus on undirected
graphs ${\mathbf{G}}_{n}$, with symmetric ${\mathbf{A}}_{n}$.

###  3.1 Graph Neural Networks

Supported on the graph ${\mathbf{G}}_{n}$ with $n$ nodes, we define node data
${\mathbf{x}}_{n}\in{\mathbb{R}}^{n}$—also called graph signals (Shuman et
al., 2013)—where $[{\mathbf{x}}_{n}]_{i}$ is the value of the signal at node
$i$. GNNs iteratively update each node’s data by aggregating the data from its
neighbors using graph convolutions. An order-$K$ graph convolution is defined
as

${\mathbf{y}}_{n}=H({\mathbf{x}}_{n})=\sum_{k=0}^{K-1}h_{k}{\mathbf{A}}_{n}^{k}{\mathbf{x}}_{n}$
(2)

where $h_{0},\dots,h_{K-1}$ are the convolution coefficients. When $K=2$ and
${\mathbf{A}}_{n}$ is binary, (2) can be seen as an aggregation operation akin
to the AGGREGATE operation in, e.g., (Xu et al., 2019; Hamilton et al., 2017),
or as the message-passing operation in message-passing neural networks (MPNNs)
(Gilmer et al., 2017).

More generally, let ${\mathbf{X}}_{n}\in{\mathbb{R}}^{n\times F}$ and
${\mathbf{Y}}_{n}\in{\mathbb{R}}^{n\times G}$ be $F$\- and $G$-dimensional
signals respectively, where the $f$th ($g$th) column is a feature
${\mathbf{x}}_{n}^{f}$ (${\mathbf{y}}_{n}^{g}$). In this case, the graph
convolution generalizes to

${\mathbf{Y}}_{n}=H({\mathbf{X}}_{n})=\sum_{k=0}^{K-1}{\mathbf{A}}_{n}^{k}{\mathbf{X}}_{n}{\mathbf{H}}_{k}$
(3)

with weights
${\mathbf{H}}_{0},{\mathbf{H}}_{1},\ldots,{\mathbf{H}}_{K-1}\in{\mathbb{R}}^{F\times
G}$. Note that the number of parameters of the graph convolutions in (2) and
(3), $K$ and $KFG$ respectively, are independent of $n$.

A GNN consists of $L$ layers, each of which composes a graph convolution and a
nonlinear activation function. Explicitly, the $l$th layer of a GNN can be
written as

$\displaystyle\begin{split}{\mathbf{X}}_{l,n}&=\sigma\left({\mathbf{U}}_{l,n}\right)\\\
{\mathbf{U}}_{l,n}&=H({\mathbf{X}}_{l-1,n})=\sum_{k=0}^{K-1}{\mathbf{A}}_{n}^{k}{\mathbf{X}}_{l-1,n}{\mathbf{H}}_{l,k}\end{split}$
(4)

where ${\mathbf{X}}_{l-1,n}\in{\mathbb{R}}^{n\times F_{l-1}}$ is the layer
input, ${\mathbf{X}}_{l,n}\in{\mathbb{R}}^{n\times F_{l}}$ is the layer
output, ${\mathbf{H}}_{l,k}\in{\mathbb{R}}^{F_{l-1}\times F_{l}}$ are the
layer weights and $\sigma$ is a pointwise nonlinear activation function, i.e.,
$[\sigma({\mathbf{X}})]_{ij}=\sigma([{\mathbf{X}}]_{ij})$. Typical choices for
$\sigma$ include ReLU, tanh, and sigmoid. At the first layer of the GNN, the
input ${\mathbf{X}}_{0,n}$ is the input data ${\mathbf{X}}$. Similarly, the
GNN output ${\mathbf{Y}}_{n}$ is given by the last layer output
${\mathbf{X}}_{n,L}$.

In the following, we represent the entire GNN consisting of the concatenation
of $L$ layers like (4) as the parametric map
${\mathbf{Y}}_{n}=f({\mathbf{X}}_{n};{\mathbf{A}}_{n},{\mathcal{H}})$, where
${\mathcal{H}}=\\{{\mathbf{H}}_{l,k}\\}_{l,k}$ groups the learnable weights
${\mathbf{H}}_{l,k}$ at all layers. This more concise representation
highlights the independence between the adjacency matrix ${\mathbf{A}}_{n}$
(i.e., the graph) and the parameters ${\mathcal{H}}$, which the GNN inherits
from the graph convolution. We note that while we describe a general class of
GNNs here, the methods in our paper can be directly adapted to other types of
GNNs.

###  3.2 Graphon Neural Networks

Table 1: Description of variables. Variable | Description
---|---
${\mathbf{A}}_{n}$ | Adjacency matrix of graph ${\mathbf{G}}_{n}$
${\mathbf{x}}_{n}$ | Graph signal on ${\mathbf{G}}_{n}$
${\mathbf{W}}_{n}$ | Graphon induced by ${\mathbf{G}}_{n}$
$X_{n}$ | Graphon signal induced by ${\mathbf{x}}_{n}$
${\mathbf{W}}$ | Limiting graphon
$X$ | Limiting graphon signal

Graphons are bounded, symmetric, measurable functions
${\mathbf{W}}:[0,1]^{2}\to[0,1]$ representing limits of sequences of dense
graphs (Lovász, 2012; Borgs et al., 2008). A graph sequence
$\\{{\mathbf{G}}_{n}\\}$ converges to a graphon in the sense that the
densities of homomorphisms of any finite, unweighted and undirected graph
${\mathbf{F}}=({\mathcal{V}}^{\prime},{\mathcal{E}}^{\prime})$ into
${\mathbf{G}}_{n}$ converge to the densities of homomorphisms of
${\mathbf{F}}$ into ${\mathbf{W}}$. The graphs ${\mathbf{F}}$ can be thought
of as motifs, such as triangles, $k$-cycles, $k$-cliques, etc. Explicitly, let
$\mbox{hom}({\mathbf{F}},{\mathbf{G}}_{n})$ denote the total number of
homomorphisms between ${\mathcal{V}}^{\prime}$ and ${\mathcal{V}}_{n}$. The
density of such homomorphisms is given by
$t({\mathbf{F}},{\mathbf{G}}_{n})={\mbox{hom}({\mathbf{F}},{\mathbf{G}}_{n})}/{n^{|{\mathcal{V}}^{\prime}|}}$
and we can similarly define $t({\mathbf{F}},{\mathbf{W}}$) (see (Borgs et al.,
2008)). Then, we say that ${\mathbf{G}}_{n}\to{\mathbf{W}}$ if and only if

$\lim_{n\to\infty}t({\mathbf{F}},{\mathbf{G}}_{n})=t({\mathbf{F}},{\mathbf{W}})$
(5)

for all simple ${\mathbf{F}}$ (Lovász & Szegedy, 2006).

Alternatively, the graphon can also be seen as a generative model for
stochastic (also called ${\mathbf{W}}$-random) graphs. Nodes are picked by
sampling points $u_{i}$, $1\leq i\leq n$, from the unit interval and
connecting edges between nodes $i$ and $j$ with probability
${\mathbf{W}}(u_{i},u_{j})$. Importantly, sequences of stochastic graphs
generated in this way converge almost surely to the graphon (Lovász,
2012)[Cor. 10.4].

The notion of graph signals is extended to graphons by defining graphon
signals, which are functions $X:[0,1]\to{\mathbb{R}}$ (Ruiz et al., 2021a). We
restrict attention to graphon signals with finite energy, i.e., $X\in
L^{2}([0,1])$.

Analogously to (3), given $F$\- and $G$-dimensional graphon signals
$X:[0,1]\to{\mathbb{R}}^{F}$ and $Y:[0,1]\to{\mathbb{R}}^{G}$, the graphon
convolution is defined as (Ruiz et al., 2021a)

$\displaystyle\begin{split}Y=T_{H}X&=\sum_{k=0}^{K-1}T_{W}^{(k)}X{\mathbf{H}}_{k}\\\
T_{W}^{(k)}X&=\int_{0}^{1}{\mathbf{W}}(u,v)T_{W}^{(k-1)}X(u)du\end{split}$ (6)

where $T_{W}^{(0)}={\mathbf{I}}$ is the identity and the convolution weights
are collected in the matrices
${\mathbf{H}}_{0},{\mathbf{H}}_{1},\ldots,{\mathbf{H}}_{K-1}\in{\mathbb{R}}^{F\times
G}$.

The extension of the GNN to graphon data is the graphon neural network (WNN).
Akin to the GNN, the WNN is formed by $L$ layers each of which composes a
graphon convolution and a nonlinear activation function. Explicitly, the $l$th
layer of the WNN is given by

$\displaystyle\begin{split}X_{l}&=\sigma\left(U_{l}\right)\\\
U_{l}&=T_{H_{l}}X_{l-1}=\sum_{k=0}^{K-1}T_{W}^{(k)}X_{l-1}{\mathbf{H}}_{l,k}\end{split}$
(7)

where $X_{l-1}:[0,1]\to{\mathbb{R}}^{F_{l-1}}$ is the layer input,
$X_{l}:[0,1]\to{\mathbb{R}}^{F_{l}}$ is its output,
${\mathbf{H}}_{l,k}\in{\mathbb{R}}^{F_{l-1}\times F_{l}}$ are its weights and
$\sigma$ is a pointwise nonlinearity (e.g., the ReLU). The input of the first
layer of the WNN is $X_{0}=X$, and the output of the WNN is the last layer
ouput, i.e., $Y=X_{L}$.

We can describe the WNN more compactly as the map
$Y=f(X;{\mathbf{W}},{\mathcal{H}})$, with
${\mathcal{H}}=\\{{\mathbf{H}}_{l,k}\\}_{l,k}$ the set of learnable parameters
at all layers. Note that, if the weights ${\mathcal{H}}$ are the same, the WNN
map $f(X;{\mathbf{W}},{\mathcal{H}})$ is the same as the GNN map
$f(X;{\mathbf{A}}_{n},{\mathcal{H}})$ with ${\mathbf{A}}_{n}$ swapped with
${\mathbf{W}}$. This is important because it implies that, similarly to how
graphons are generative models for graphs, _WNNs are generative models for
GNNs_. Indeed, we can use the WNN $f(X;{\mathbf{W}},{\mathcal{H}})$ to sample
the GNN ${\mathbf{y}}_{n}=f({\mathbf{x}}_{n};{\mathbf{A}}_{n},{\mathcal{H}})$
with

$\displaystyle[{\mathbf{A}}_{n}]_{ij}\sim\mbox{Ber}({\mathbf{W}}(u_{i},u_{j}))$
$\displaystyle[{\mathbf{x}}_{n}]_{i}=X(u_{i})$ (8)

where the $u_{i}$ are sampled uniformly and independently at random from
$[0,1]$ and $\mbox{Ber}()$ is the Bernoulli distribution.

As $n\to\infty$, sequences of GNNs sampled from the WNN as described above
converge to the WNN. In fact, as long as ${\mathcal{H}}$ is the same, any GNN
$f({\mathbf{x}}_{n};{\mathbf{A}}_{n},{\mathcal{H}})$ applied to a sequence
$\\{({\mathbf{G}}_{n},{\mathbf{x}}_{n})\\}$ converging to $({\mathbf{W}},X)$
converges to $f(X;{\mathbf{W}},{\mathcal{H}})$ (Ruiz et al., 2021a). A more
important result in practice is that this convergence implies that GNNs are
transferable across graphs associated with the same graphon, i.e., they can be
trained on graphs ${\mathbf{G}}_{n}$ and executed on graphs ${\mathbf{G}}_{m}$
with an error that decreases asymptotically with $n$ and $m$ (Ruiz et al.,
2021b, 2020).

In Sec. 5, we prove a similar convergence result for the neural tangent
kernels (NTKs) associated with
$f({\mathbf{x}}_{n};{\mathbf{A}}_{n},{\mathcal{H}})$ and
$f(X;{\mathbf{W}},{\mathcal{H}})$, but before doing so, we need to introduce
induced WNNs. The WNN induced by the GNN
$f({\mathbf{x}}_{n};{\mathbf{A}}_{n},{\mathcal{H}})$ is defined as
$Y_{n}=f(X_{n};{\mathbf{W}}_{n},{\mathcal{H}})$, with

$\displaystyle\begin{split}&{\mathbf{W}}_{n}(u,v)=\sum_{i=1}^{n}\sum_{j=1}^{n}[{\mathbf{A}}_{n}]_{ij}{\mathbb{I}}(u\in
I_{i}){\mathbb{I}}(v\in I_{j}),\\\
&X_{n}(u)=\sum_{i=1}^{n}[{\mathbf{x}}_{n}]_{i}{\mathbb{I}}(u\in
I_{i})\end{split}$ (9)

and where ${\mathbb{I}}$ is the indicator function, $I_{i}=[(i-1)/n,i/n)$ for
$1\leq i\leq n-1$, and $I_{n}=[(n-1)/n,1]$. The graphon ${\mathbf{W}}_{n}$ is
induced by the graph ${\mathbf{G}}_{n}$, and the graphon signals $X_{n}$ and
$Y_{n}$ are  induced by the graph signals ${\mathbf{x}}_{n}$ and
${\mathbf{y}}_{n}$. A succinct description of all graph and graphon variables
is provided in Table 1.

##  4 Graph and Graphon Neural Tangent Kernel

Consider a general, fully-connected neural network
$f({\mathbf{x}};{\mathcal{H}})$, with layers given by
${\mathbf{x}}_{l}=\sigma({\mathbf{H}}_{l}{\mathbf{x}}_{l-1})$, input
${\mathbf{x}}_{0}={\mathbf{x}}\in{\mathbb{R}}^{d_{0}}$ and learnable
parameters
${\mathcal{H}}=\\{{\mathbf{H}}_{l}\\}_{l}\in{\mathbb{R}}^{d_{l-1}\times
d_{l}}$, $[{\mathbf{H}}_{l}]_{pq}=h_{l,pq}$. For a training set
$\\{{\mathbf{x}}_{i},{\tilde{\mathbf{y}}}_{i}\\}_{i=1}^{M}$, assume that the
loss to be minimized is the mean squared error (MSE) or quadratic loss

$\min_{\mathcal{H}}\ell({\mathcal{H}})=\min_{\mathcal{H}}\sum_{i=1}^{M}(f({\mathbf{x}}_{i};{\mathcal{H}})-{\tilde{\mathbf{y}}}_{i})^{2}.$
(10)

As the training progresses, the output of the neural network for input
${\mathbf{x}}_{i}$ is updated as
${\mathbf{y}}_{i}(t)=f({\mathbf{x}}_{i};{\mathcal{H}}(t))$. As such, the
weight update rule is given by $\smash{{\frac{\partial{\mathcal{H}}}{\partial
t}=-\nabla\ell({\mathcal{H}}(t))}}$ and so the output evolves as

$\displaystyle\begin{split}&\frac{\partial{\mathbf{y}}_{i}(t)}{\partial
t}=\textstyle\sum_{j}\Theta({\mathbf{x}}_{i},{\mathbf{x}}_{j};{\mathcal{H}}(t))(f({\mathbf{x}}_{i};{\mathcal{H}}(t))-{\hat{\mathbf{y}}}_{i}),\\\
&\Theta({\mathbf{x}}_{i},{\mathbf{x}}_{j};{\mathcal{H}})\
=\sum_{l,p,q}\frac{\partial f({\mathbf{x}}_{i};{\mathcal{H}})}{\partial
h_{l,pq}}\frac{\partial f({\mathbf{x}}_{j};{\mathcal{H}})}{\partial
h_{l,pq}}.\end{split}$ (11)

In the infinite-width limit as $d_{l}\to\infty$, Jacot et al. (2018); Liu et
al. (2020) showed that, provided that the last layer has linear output (i.e.,
it does not have an activation $\sigma$),
$\Theta({\mathbf{x}}_{i},{\mathbf{x}}_{j};{\mathcal{H}})$ converges to a
limiting kernel, the NTK. This kernel stays constant during training—a
property called constancy—, which is equivalent to replacing the outputs of
the neural network by their first-order Taylor expansion in the parameter
space (Lee et al., 2019). Hence, in the infinite-width limit the training
dynamics of (11) reduce to kernel ridge regression111In practice, it is not
necessary to consider the MSE for this derivation. It suffices for the loss to
be such that the norm of the training direction
$f({\mathcal{H}}_{0})-f({\mathcal{H}}^{\star})$ is strictly decreasing during
training (Jacot et al., 2018). E.g., if we consider the cross-entropy loss,
the training dynamics reduce to kernel logistic regression. on the NTK, which
has a closed-form solution. This facilitates understanding the learning
dynamics of overparametrized neural networks, which are notoriously difficult
to study directly, by analysis of the corresponding NTK.

###  4.1 Graph Neural Tangent Kernel

For simplicity, we will consider a GNN with only one feature per layer; the
generalization to multiple features is more involved but straightforward.
Recall that the $L$-layer GNN supported on
${\mathbf{A}}_{n}\in{\mathbb{R}}^{n\times n}$ is written as

$\displaystyle{\mathbf{x}}_{n,0}={\mathbf{x}}_{n}\quad\quad\quad\ \ \
{\mathbf{u}}_{l,n}=H_{l}({\mathbf{x}}_{l-1,n})$
$\displaystyle{\mathbf{x}}_{l,n}=\sigma({\mathbf{u}}_{l,n})\quad\quad
f({\mathbf{x}}_{n};{\mathbf{A}}_{n},{\mathcal{H}})={\mathbf{x}}_{L,n}\text{.}$

The graph NTK (GNTK) associated with this GNN is

$\displaystyle\Theta({\mathbf{x}}_{n},{\mathbf{x}}^{\prime}_{n};{\mathbf{A}}_{n},{\mathcal{H}})=$
$\displaystyle\nabla_{\mathcal{H}}f({\mathbf{x}}_{n};{\mathbf{A}}_{n},{\mathcal{H}})^{T}\nabla_{\mathcal{H}}f({\mathbf{x}}^{\prime}_{n};{\mathbf{A}}_{n},{\mathcal{H}})$
$\displaystyle=\textstyle\sum_{k}\sigma^{\prime}({\mathbf{u}}_{L,n}){\mathbf{A}}_{n}^{k}{\mathbf{x}}_{L-1,n}\otimes\sigma^{\prime}({\mathbf{u}}_{L,n}^{\prime}){\mathbf{A}}_{n}^{k}{\mathbf{x}}_{L-1,n}^{\prime}$
$\displaystyle\quad+\sigma^{\prime}({\mathbf{u}}_{L,n})(\sigma^{\prime}({\mathbf{u}}_{L-1,n}){\mathbf{A}}_{n}^{k}{\mathbf{x}}_{L-2,n})$
$\displaystyle\quad\quad\otimes\sigma^{\prime}({\mathbf{u}}_{L,n}^{\prime})H_{L}(\sigma^{\prime}({\mathbf{u}}_{L-1,n}^{\prime}){\mathbf{A}}_{n}^{k}{\mathbf{x}}^{\prime}_{L-2,n})+\ldots$

where there are $L$ terms; the first term corresponds to the last layer, the
second term to the second-last layer, and so on. We have used
$\sigma^{\prime}({\mathbf{u}})$ to denote the diagonal matrix with $jj$th
entry equal to $\sigma^{\prime}([{\mathbf{u}}]_{j})$, where $\sigma^{\prime}$
is the derivative of $\sigma$. Note that $\nabla_{\mathcal{H}}f$ is a
$|{\mathcal{H}}|\times n$ matrix, hence the GNTK is a matrix
$\Theta_{n}({\mathbf{x}}_{n},{\mathbf{x}}_{n}^{\prime};{\mathbf{A}}_{n},{\mathcal{H}})\in{\mathbb{R}}^{n\times
n}$.

###  4.2 Graphon Neural Tangent Kernel

To derive the WNTK, we will also consider a WNN with only one feature per
layer for simplicity. Recall that the $L$-layer WNN associated with the
graphon ${\mathbf{W}}$ is given by

$\displaystyle X_{0}=X\quad\quad\quad\ \ U_{l}=\textstyle T_{H_{l}}X_{l-1}$
$\displaystyle X_{l}=\sigma(U_{l})\quad\quad
f(X;{\mathbf{W}},{\mathcal{H}})=X_{L}\text{.}$

Therefore, the WNTK is given by

$\displaystyle\begin{split}\Theta(X,X^{\prime};{\mathbf{W}},{\mathcal{H}})&=\\\
&=\textstyle\sum_{l,k}\partial_{h_{l,k}}f(X;{\mathbf{W}},{\mathcal{H}})\otimes\partial_{h_{l,k}}f(X^{\prime};{\mathbf{W}},{\mathcal{H}})\text{.}\end{split}$
(12)

Calculating the derivative with respect to the $k$th weight in layer
$l_{j}=L-j$, we get

$\partial_{h_{l_{j},k}}u_{L}=\textstyle T_{W}^{(k)}X_{L-1}$

for $j=0$, and similarly for $0<j<L$,

$\partial_{h_{l_{j},k}}u_{L}=\textstyle
T_{H_{L}}\sigma^{\prime}(U_{L-1})\dots\textstyle
T_{H_{l{j-1}}}\sigma^{\prime}(U_{L-j})\textstyle
T_{W}^{(k)}X_{l_{j-1}}\text{.}$

Hence, (12) has $L$ terms in total, explicitly

$\displaystyle\begin{split}\Theta(X,X^{\prime};{\mathbf{W}},{\mathcal{H}})&=\\\
&=\textstyle\sum_{k}\sigma^{\prime}(U_{L})T_{W}^{(k)}X_{L-1}\otimes\sigma^{\prime}(U_{L}^{\prime})T_{W}^{(k)}X_{L-1}^{\prime}\\\
&\quad+\sigma^{\prime}(U_{L})T_{H_{L}}(\sigma^{\prime}(U_{L-1})T_{W}^{(k)}X_{L-2})\\\
&\quad\quad\otimes\sigma^{\prime}(U_{L}^{\prime})T_{H_{L}}(\sigma^{\prime}(U^{\prime}_{L-1})T_{W}^{(k)}X^{\prime}_{L-2})+\ldots\end{split}$

where $\sigma^{\prime}(U_{L})$ is now evaluated and multiplied pointwise. Note
that $\Theta$ is a linear operator on graphon signals, i.e., given a signal
$Y\in L^{2}([0,1])$, the WNTK applied to this signal yields

$\displaystyle\Theta(X,X^{\prime};{\mathbf{W}},{\mathcal{H}})Y$
$\displaystyle=\textstyle\int_{0}^{1}\textstyle\sum_{k}\sigma^{\prime}(U_{L}(u))T_{W}^{(k)}X_{L-1}(u)$
$\displaystyle\quad\,\,\times\sigma^{\prime}(U_{L}^{\prime}(v))T_{W}^{(k)}X_{L-1}^{\prime}(v)Y(v)$
$\displaystyle\quad+\sigma^{\prime}(U_{L}(u))T_{H_{L}}(\sigma^{\prime}(U_{L-1})T_{W}^{(k)}X_{L-2})(u)$
$\displaystyle\quad\,\,\times\sigma^{\prime}(U_{L}(v))T_{H_{L}}(\sigma^{\prime}(U_{L-1})T_{W}^{(k)}X_{L-2})(v)Y(v)+\ldots\,dv$

where the first term corresponds to the last layer, the second corrresponds to
the second-last layer and so on.

For a graph ${\mathbf{A}}_{n}$ sampled from ${\mathbf{W}}$ with associated
induced graphon ${\mathbf{W}}_{n}$, and for input features ${\mathbf{x}}_{n}$
sampled from a graphon signal $X$ and associated induced graphon signal
$X_{n}$ [cf. (9)], the induced WNTK is given by the same formula as (12) but
with ${\mathbf{W}}$, $X$ replaced by ${\mathbf{W}}_{n}$, $X_{n}$.

##  5 Graph NTK Converges to Graphon NTK

Next, we consider a sequence of graph signals
$\\{({\mathbf{G}}_{n},{\mathbf{x}}_{n})\\}$ converging to a graphon signal
$({\mathbf{W}},X)$ to evaluate the convergence of the GNTK
$\Theta({\mathbf{x}}_{n},{\mathbf{x}}_{n}^{\prime};{\mathbf{A}}_{n},{\mathcal{H}})$
to the WNTK $\Theta(X,X^{\prime};{\mathbf{W}},{\mathcal{H}})$. First, for each
pair of signals $X,X^{\prime}$, the WNTK
$\Theta(X,X^{\prime};{\mathbf{W}},{\mathcal{H}})$—which we denote
$\Theta(X,X^{\prime})$ to simplify notation—is a linear operator on functions
in $L^{2}$. Hence, to prove convergence to this operator we introduce the
operator norm

$\displaystyle\left|\left|\Theta(X,X^{\prime})\right|\right|=\sup_{Y\neq
0}\frac{\left|\left|\Theta(X,X^{\prime})Y\right|\right|}{\left|\left|Y\right|\right|}\text{.}$
(13)

Figure 1: Difference between the test error achieved by the GNTK fitted on the
$n$-node graph when used for prediction the $n$-node graph, and the test error
achived by the same GNTK when used for predicition on the $N$-node graph.
(left) Opinion dynamics on geometric and SBM graphs, where the test error is
the MSE $N=300$. (right) Node classification on Cora, CiteSeer and Pubmed,
where the test error is the CE and $N=2708$, $3327$, and $10000$ respectively.

Let ${\mathbf{W}}$ be a graphon and $X,X^{\prime}$ be fixed graphon signals.
Consider a sequence of graph signals
$\\{({\mathbf{G}}_{n},{\mathbf{x}}_{n})\\}$ (respectively
$\\{({\mathbf{G}}_{n},{\mathbf{x}}_{n}^{\prime})\\}$) converging to
$({\mathbf{W}},X)$ (respectively $({\mathbf{W}},X^{\prime})$) in the sense of
(Ruiz et al., 2021a)[Def. 2]. The notion of convergence of graph signals on a
sequence of dense graphs is simple; ${\mathbf{G}}_{n}$ converges to
${\mathbf{W}}$ in the homomorphism density sense [cf. (5)], and $X_{n}$, the
graphon signal induced by ${\mathbf{x}}_{n}$, converges to $X$ in the $L^{2}$
norm, i.e.

$\|X_{n}-X\|\to 0$ (14)

up to node relabelings (see (Ruiz et al., 2021a) for further details, and in
particular Lemma 2 for the relationship between
$({\mathbf{G}}_{n},{\mathbf{x}}_{n})$ and the induced signal
$({\mathbf{W}}_{n},X_{n})$).

Let $({\mathbf{W}}_{n},X_{n})$ be the graphon signal induced by the graph
signal $({\mathbf{G}}_{n},{\mathbf{x}}_{n})$ [cf. (9)]. The main result of
this paper is the following theorem that shows that the WNTK induced by the
GNTK converges to the limiting WNTK. The proof is deferred to Appendix A.

######  Theorem 5.1.

Let W be a graphon and $X,X^{\prime}\in L^{2}([0,1])$ be arbitrary graphon
signals. Suppose that $\left\\{{\mathbf{G}}_{n}\right\\}$ is a sequence of
graphs converging to ${\mathbf{W}}$ [cf. (5)] and
$\left\\{{\mathbf{x}}_{n}\right\\},\left\\{{\mathbf{x}}_{n}^{\prime}\right\\}$
are sequences of graph signals converging to $X$ [cf. (14)].

$\displaystyle\lim_{n\to\infty}||X_{n}-X||=0$
$\displaystyle\lim_{n\to\infty}||X_{n}^{\prime}-X^{\prime}||=0$
$\displaystyle\lim_{n\to\infty}||W_{n}-W||=0.$

Then, for any $L$-layer GNN with finite $K$, fixed weights ${\mathcal{H}}$ and
$1$-Lipschitz nonlinearity $\sigma$, the associated GNTKs
$\Theta({\mathbf{x}}_{n},{\mathbf{x}}^{\prime}_{n};{\mathbf{A}}_{n},{\mathcal{H}})$
converge in the operator norm:

$\displaystyle\lim_{n\to\infty}\left|\left|\Theta(X_{n},X^{\prime}_{n};{\mathbf{W}}_{n},{\mathcal{H}})-\Theta(X,X^{\prime};{\mathbf{W}},{\mathcal{H}})\right|\right|=0$

where $\Theta(X_{n},X^{\prime}_{n};{\mathbf{W}}_{n},{\mathcal{H}})$ is the
WNTK induced by the GNTK
$\Theta({\mathbf{x}}_{n},{\mathbf{x}}_{n}^{\prime};{\mathbf{A}}_{n},{\mathcal{H}})$.

The convergence of the GNTK to a limit object—the WNTK—has two important
implications for machine learning on large-scale graphs. First, consider that
we have a large graph ${\mathbf{G}}_{N}$ on which we want to predict signals
${\mathbf{y}}_{N}$ using the GNTK, but that we do not have enough
computational resources to compute the full-sized GNTK
$\Theta({\mathbf{x}}_{N},{\mathbf{x}}_{N}^{\prime};{\mathbf{A}}_{N},{\mathcal{H}})$.
This is expected, since calculating the kernel regression weights on this
graph requires inverting a matrix with dimension proportional to $M$, the
number of training samples, and the graph size $N$, see Sec. 4. Thm. 5.1
implies that we can subsample the GNTK and the labels $Y_{N}$ on a smaller
graph ${\mathbf{G}}_{n}$, $n\ll N$—as
$\Theta({\mathbf{x}}_{n},{\mathbf{x}}_{n}^{\prime};{\mathbf{A}}_{n},{\mathcal{H}})$
and ${\mathbf{y}}_{n}$ respectively—and fit the data to the GNTK on this
smaller graph. Once the kernel regression weights are obtained, they can then
be transferred to make predictions on ${\mathbf{G}}_{N}$. Naturally, there
will be an error associated with this transference; however, due to
convergence, this error vanishes asymptotically in $n$.

The precise convergence bounds for different graphs can be computed by
plugging into (27). For instance, for graphs sampled from the graphon as in
(Ruiz et al., 2021b)[Def. 1], the bound is given by

$\displaystyle\left|\left|\Theta(X_{n},X_{n}^{\prime})-\Theta(X,X^{\prime})\right|\right|\leq
C(K^{4+L}\frac{2A_{w}}{n}+K^{2+L}\frac{A_{x}}{n}).$

where $C$ is a constant, and $A_{w}$ and $A_{x}$ are the Lipschitz constants
of the graphon and the graphon signal respectively.

In practice, transferability is useful in a variety of real-world
applications, especially on large graphs. For instance, one may be interested
in the learning dynamics of a GNN trained to provide ad recommendations on a
growing, dense social media network. Our theoretical results show that one can
calculate the GNTK on a smaller subgraph, e.g., the same social media network
at an earlier time, and then transfer it to the large target graph with
theoretical performance guarantees. This works because dense networks growing
under the same underlying ‘rule’ or ‘process’ should have similar homomorphism
densities, and converge to similar graphons; or, inversely, they can be
thought of as being sampled from similar graphons. The more similar these
limiting graphons are (under a metric such as the cut metric or the $L^{2}$
norm), the lower the error when transferring the GNTK across graphs.

A second implication of Thm. 5.1, which is perhaps more important, is that
GNTK convergence implies that a GNTK fitted on a smaller graph can be used to
infer details about the training dynamics of wide/overparametrized GNNs on
larger graphs. This follows from Thm. 5.1 in conjunction with theoretical
results by Liu et al. (2020), which proves that in the infinite-width limit
the training dynamics of general convolutional models (including GNNs) reduces
to kernel ridge regression on the corresponding NTK; and empirical results by
Sabanayagam et al. (2021) showing that even when the output layer is
nonlinear, constancy of the GNTK can still be observed.

An example of property of a large-graph GNTK
$\Theta({\mathbf{x}}_{N},{\mathbf{x}}_{N}^{\prime};{\mathbf{A}}_{N},{\mathcal{H}})$
that can be estimated from a small-graph GNTK
$\Theta({\mathbf{x}}_{n},{\mathbf{x}}_{n}^{\prime};{\mathbf{A}}_{n},{\mathcal{H}})$
is its eigenvalue spectrum. As we show in Thm. 5.2, the spectrum of
$\Theta(X_{n},X_{n}^{\prime};{\mathbf{W}}_{n},{\mathcal{H}})$ converges to the
the spectrum of $\Theta(X,X^{\prime};{\mathbf{W}},{\mathcal{H}})$. The proof
is deferred to Appendix B.

######  Theorem 5.2.

Let $\\{{\mathbf{x}}_{i,n}\\}_{i=1}^{M}$ be a set of $M$ signals on the graph
${\mathbf{G}}_{n}$, and $\\{X_{i,n}\\}_{i=1}^{M}$ the corresponding induced
signals on the induced graphon ${\mathbf{W}}_{n}$. Assume that
${\mathbf{G}}_{n}\to{\mathbf{W}}$ [cf. (5)] and $X_{i,n}\to X$ [cf. (14)] for
all $i$. Define the operators $\boldsymbol{\Theta}_{n}$ and
$\boldsymbol{\Theta}$ where
$[\boldsymbol{\Theta}_{n}]_{ij}=\Theta(X_{i,n},X_{j,n};{\mathbf{W}}_{n},{\mathcal{H}})$
and
$[\boldsymbol{\Theta}]_{ij}=\Theta(X_{i},X_{j};{\mathbf{W}},{\mathcal{H}})$.
Let $\lambda_{p}(T)$, $p\in{\mathbb{Z}}\setminus\\{0\\}$, denote the $p$th
eigenvalue of a compact, self-adjoint operator $T$, with
$\lambda_{-1}<\lambda_{-2}<\ldots\leq 0\leq\ldots<\lambda_{2}<\lambda_{1}$. If
the weights in ${\mathcal{H}}$ are bounded, then, for all $p$,

$\lim_{n\to\infty}|\lambda_{p}(\boldsymbol{\Theta}_{n})-\lambda_{p}(\boldsymbol{\Theta})|\to
0\text{.}$

Moreover, the corresponding eigenspaces converge in the sense that the
spectral projectors converge.

This is an important result because, as proved by Jacot et al. (2018), the
convergence of kernel gradient descent follows the kernel principal
components. Thus, if the GNN $f({\mathcal{H}})$ is sufficiently wide, and if
$f({\mathcal{H}}_{0})-f({\mathcal{H}}^{\star})$ is aligned with the $i$th GNTK
principal component, we can expect gradient descent to converge with rate
proportional to $\lambda_{i}$, the $i$th eigenvalue of the GNTK. Thm. 5.2
shows that the GNTK eigenvalues converge to the eigenvalues of the WNTK. As
such, we can estimate the speed of convergence of a large-graph GNN
$f({\mathbf{x}}_{N};{\mathbf{A}}_{N},{\mathcal{H}})$ from the eigenvalues of a
small-graph GNTK
$\Theta({\mathbf{x}}_{n},{\mathbf{x}}_{n}^{\prime};{\mathbf{A}}_{n},{\mathcal{H}})$.
A numerical example of this application of Thms. 5.1 and 5.2 is given in Sec.
6.3.

Spectral convergence of the GNTK is particularly relevant for practical
applications on large graphs. Convergence of the spectrum implies convergence
of the directions of learning. Intuitively, one can calculate the GNTK on the
smaller graph, then transfer it to the large graph with the guarantee that the
dominant directions of fastest convergence are being captured. We can learn
GNN architectures that harness this property by pretraining on a smaller
graph, and making adjustments on the large graph; or, by iterating between
different resolutions of graph size.

As a final comment, we point out that one can also deduce convergence of the
GNTK spectrum to the WNTK spectrum. The eigenvalues of the NTKs capture the
rate of convergence along the directions that are captured by the
eigenvectors. For instance, the eigenvector corresponds to the leading
eigenvalue is the direction of fastest convergence. terminology question:
should we use eigenfunctions instead for the WNTK? still working on this. Do
you happen to know the citation below off the top of your head?

######  Theorem 5.3.

For a bounded, linear operator $Q:L^{2}\to L^{2}$ denote $\sigma(Q)$ the
spectrum of $Q$. If $W$ is Lipschitz and $W_{n}\to W$ in the Lipschitz metric
and the coefficients $h_{k,n}$ are bounded uniformly, then for all
$X,X^{\prime}$ and sequences such that $\left|\left|X_{n}-X\right|\right|\to
0$ and $\left|\left|X_{n}^{\prime}-X^{\prime}\right|\right|\to 0$,

$\displaystyle\sup_{z\in\sigma(\Theta(X,X^{\prime}))}\inf_{z^{\prime}\in\sigma(\Theta(X_{n},X^{\prime}_{n}))}|z-z^{\prime}|\to
0.$

###### Proof.

Since $W$ and $W_{n}$ are Lipschitz, it follows that

$\displaystyle\left|\left|\partial_{u}T_{W}\right|\right|\leq\left|\left|\nabla
W\right|\right|_{L^{2}}$
$\displaystyle\left|\left|\partial_{u}T_{W_{n}}\right|\right|\leq\left|\left|\nabla
W_{n}\right|\right|_{L^{2}},$

and therefore the $T_{W},T_{W_{n}}$ are compact operators. Since the
coefficients are bounded, it follows from the formulae above that the graphon-
NTK and the induced graphon-NTKs are all compact operators on $L^{2}$. From
cite?!, the convergence of the spectrum (and in fact also of all finite
dimensional spectral projectors) follows. ∎

######  Corollary 5.4.

Let ${\mathbf{W}}$ be a Lipschitz continuous graphon and $X,X^{\prime}$ be
arbitrary, Lipschitz continuous graphon signals. Suppose that
$\left\\{{\mathbf{A}}_{n}\right\\}_{n=1}^{\infty}$ be a sequence of generic
GSO’s sampled from ${\mathbf{W}}$ of dimension ${\mathbb{R}}^{n\times n}$, and
let ${\mathbf{W}}_{n}$ be the associated induced graphons and
$X_{n},X_{n}^{\prime}$ be the induced graphon signals associated to
$X,X^{\prime}$ respectively. Then, for any $L$-layer WNN with $K$ fixed
(finite) and fixed filter coefficients ${\mathcal{H}}$, the associated NTK’s
converge in the operator norm:

$\displaystyle\lim_{n\to\infty}\left|\left|\Theta_{W}(X,X^{\prime})-\Theta_{W_{n}}(X_{n},X^{\prime}_{n})\right|\right|=0.$

###  5.1 Convergence for different random graph models

An approximate estimate depends on what kind of random graph is being
generated. For a weighted graph, Propositions 13 in the previous paper gives
with probability at least $(1-2\chi_{1})(1-\chi_{2})$ for $n\geq 4/\chi_{2}$,

$\displaystyle\|X-X_{n}\|$
$\displaystyle\leq\frac{A_{x}}{n}\log\left(\frac{(n+1)^{2}}{\log(1-\chi_{1})^{-1}}\right)\|X\|$

(where $A_{x}$ is the Lipschitz constant of $X$) and

$\displaystyle\|W_{n}-W\|$
$\displaystyle\leq\frac{2A_{w}}{n}\log\left(\frac{(n+1)^{2}}{\log(1-\chi_{1})^{-1}}\right).$

Let us now assume that $n$ is so large that

$\displaystyle\frac{A_{x}}{n}\log\left(\frac{(n+1)^{2}}{\log(1-\chi_{1})^{-1}}\right)<1.$

In the weighted graph case, it seems like we then have (assuming
$X,X^{\prime}$ have the same Lipschitz constants)

For stochastic graphs, the paper is a little less clear about exactly what the
estimate is, but I feel like similar estimates, possibly up to another
logarithm, hold due to Proposition 14.

L: I like the proof steps above, linking with the bounds from the
transferability paper which avoids all the ugly triangle inequalities and
Cauchy-Schwarz. However, I think we still need to polish this section and add
a bit more detail.

TO DO: (1) write estimates for $\|X-X_{n}\|$ and $\|W-W_{n}\|$ for stochastic
graphs? (2) Evaluate a quantitative estimate for Eqn 16 for 2 layers by adding
and subtracting (8 terms total) and using triangle inequality (since
$U_{l}=\sigma X_{l}$ and we have bounds on $U_{l}$ for graph and graphon in
terms of $W-W_{n}$. (3) Once we have this estimate, trivially write
transferability $\left|\left|\Theta_{n1}-\Theta_{n2}\right|\right|$ using
triangle inequality (Similar to how it’s done below).

L: Will get to (1) soon.

##  6 Numerical Results

Table 2: Movie recommendation results. Relative difference between the test MSE achieved by the GNTK fitted on the $n$-node graph when used for prediction the $n$-node graph, and the test error achived by the same GNTK when used for predicition on the $N$-node graph, where $N=1000$. Number of nodes | 100 | 200 | 300 | 400 | 500
---|---|---|---|---|---
Mean (%) | $6.80$ | $0.78$ | $0.09$ | $0.03$ | $0.03$
Std. dev. (p.p.) | $3.51$ | $1.16$ | $0.03$ | $0.01$ | $0.02$

Figure 2: Projections of the inputs and outputs of the GNTK and GNN, and of
the target or true labels onto the second eigenvector of the adjacency matrix
of a $80$-node SBM graph for widths $F=10$ (left), $F=50$ (center) and $F=250$
(right).

In the following, we illustrate the convergence of the GNTK to the WNTK on a
simulated opinion dynamics model on random graphs; on a movie recommendation
graph; and on citation networks (Sec. 6.1). In the opinion dynamics problem,
we further vary the width of the network to analyze the large width behavior
of the GNTK and how it relates to the behavior of the GNN (Sec. 6.2). We
conclude with an example of how the convergence of the GNTK can be used in
practice to estimate the eigenvalues of the GNTK, and thus the speed of GNN
training along its principal components, on large-scale graphs (Sec. 6.3).

Opinion dynamics. This is a node-level task modeling the outcomes of a
mathematical model for studying the evolution of ideologies, affiliations, and
opinions in society (Lorenz, 2007), including topics of important practical
interest such as political ideologies and misinformation spread. On an
undirected $n$-node graph ${\mathbf{G}}=({\mathcal{V}},{\mathcal{E}})$, we
consider an opinion dynamics process ${\mathbf{x}}_{t}\in{\mathbb{R}}^{n}$.
The node data $[{\mathbf{x}}_{t}]_{i}$ is the opinion of individual $i$ under
a standard bounded-confidence model described by Hegselmann et al. (2002):

$[{\mathbf{x}}_{t}]_{i}=\sum_{j\in{\mathcal{S}}_{i,t-1}}c[{\mathbf{x}}_{t-1}]_{j}.$
(15)

where $c>0$ is the so-called influence parameter and
${\mathcal{S}}_{i,t-1}={\mathcal{N}}_{i}\cap{\mathcal{X}}_{i,t-1}$ is the
intersection of ${\mathcal{N}}_{i}=\\{j\in{\mathcal{V}}\ |\
(i,j)\in{\mathcal{E}}\\}$, the neighborhood of $i$, and
${\mathcal{X}}_{i,t}=\\{j\in{\mathcal{V}}\ |\
|[{\mathbf{x}}_{t}]_{j}-[{\mathbf{x}}_{t}]_{i}|\leq\epsilon\\}$, the set of
nodes whose opinion at time $t$ diverges by at most $0\leq\epsilon\leq 1$ of
the opinion of node $i$. This model reduces to the classic De-Groot (DeGroot,
1974) opinion model for $\epsilon=1$. We fix $\epsilon=0.3$ and $c=0.1$.

After drawing the initial opinions ${\mathbf{x}}_{0}$ from a Gaussian
distribution with $\boldsymbol{\mu}=\boldsymbol{0}$ and
$\boldsymbol{\Sigma}=2{\mathbf{I}}$, we run the process (15) until convergence
(for at most $T=1000$ iterations) to obtain the final opinions
${\mathbf{x}}_{T}$. The goal of the learning problem is then to predict
${\mathbf{y}}={\mathbf{x}}_{T}$ from ${\mathbf{x}}={\mathbf{x}}_{0}$. We fix
the training set size to $300$ samples, and use $30$ samples for both
validation and testing.

Movie recommendation. In this problem, the graph is a movie similarity
network, the data are existing user ratings (ranging from 1 to 5), and the
task is to use the existing ratings to fill in the missing ratings for movie
recommendation. The movie similarity graph is a dense correlation graph built
by computing pairwise correlations between the rating vectors of the movies
rated in the MovieLens-100k dataset (Harper & Konstan, 2016). We only consider
movies with at least 10 ratings, and the large graph has $N=1000$ nodes
sampled at random from the set of admissible movies. The learning problem is
to predict the ratings of the movie “Contact”. We use a 90-10 train-test split
of the data, and build the graph using only the training samples. Due to
memory limitations, we only use 25% of the users (samples) to compute the
GNTK.

Citation networks. The third problem we consider is a node classification
problem on the Cora, CiteSeer and PubMed networks, where nodes represent
documents and undirected edges represent citations between papers in either
direction. The nodes a bag-of-words representations are grouped in
${\mathbf{X}}\in\\{0,1\\}^{n\times F}$ and each node is associated with one of
$C$ classes. We consider the networks and train-test-splits from the full
distribution (Bojchevski & Günnemann, 2017) available in PyTorch Geometric,
but only sample $F=1000$ features for CiteSeer and $N=10000$ nodes for PubMed
due to memory limitations. Through studying citation networks, we illustrate
the empirical manifestation of our results on real-world graphs. Although
citation networks are not best modeled by graphon limits, they certainly have
limits, and our results suggest that convergence is a global property of GNTKs
and graph limits.

Architectures and experiment details. In all experiments, the GNNs have $L=1$
layer (4) with ReLU nonlinearity followed by a perceptron layer. For opinion
dynamics, $K=2$, and for movie recommendation, $K=5$. In both cases, we
consider the MSE and fit the GNTK using linear regression. In the citation
network experiment, the GNN architecture has $K=2$ and includes a softmax
layer followed by argmax; and we consider the cross-entropy (CE) and fit the
GNTK using logistic regression. All reported results are averaged over $5$ and
$10$ realizations for opinion dynamics and movie recommendation/citation
networks respectively. Additional architecture and experiment details are
listed in each subsection. The code can be found in this repository. All
experiments were run on a NVIDIA RTX A6000 GPU.

###  6.1 Convergence

To visualize the convergence of the GNTK, we fit a GNTK with $F_{1}=10$ in the
opinon dynamics and citation network experiments, and $F_{1}=16$ in the
recommendation experiment, on the training set of a small $n$-node graph; and
transfer this GNTK, without retraining, to predict the outputs on the test set
of both the same $n$-node graph and a larger $N$-node graph. To visualize
convergence, we plot in Fig. 1 the absolute difference between the test errors
attained on the $n$-node and the $N$-node graph (normalized by the test error
on the $N$-node graph) as a function of the size of the smaller graph $n$, for
both the opinion dynamics (left) and node classification (right) experiments.
The results of the recommendation experiment are reported in Table 2.

Figure 3: The leading eigenvalue of the GNTK with width $F=10$ for Cora,
CiteSeer and PubMed as a function of the graph size $n$.

In opinion dynamics, $N=300$. We consider two types of graphs, corresponding
to two graphon families: (a) a symmetrized geometric $k$-nearest neighbor
graph where nodes are drawn at random from a $50\times 50$ square and
$k=n/10$; and (b) a stochastic block model (SBM) graph with intra-community
probability $p=0.1$ and inter-community probability $q=0.05$. As $n$ increases
from $20$ to $100$, we observe that the difference between the MSEs for the
$n$-node and the $N$-node graphs decrease steadily from $\sim 70$% to $\sim
20$% on the geometric graphs and from $\sim 90$% to $\sim 40$% on the SBM
graphs.

In the recommendation experiment, $N=1000$. As $n$ increases from $100$ to
$500$, we see from Table 2 that the average test MSE difference on the large
graph decreases from $6.8$% to $0.3$%, and so does the standard deviation,
thus confirming our theoretical findings. In particular, $n=300$ is enough to
achieve an MSE difference of less than $1$%.

In the node classification experiment, $N=2708$ for Cora, $N=3327$ for
CiteSeer, and $N=10000$ for PubMed (sampled from the $19717$ nodes in the
original due to memory limitations). For all datasets, the difference between
the CE loss for the $n$-node and the $N$-node graph also decreases as $n$
increases. This can be interpreted to mean that node classification on these
citation networks depends largely on local information, so beyond a critical
size $n$, the transference error saturates. An interesting point to make is
that although these citation networks are not dense (i.e., are not best
modeled by a graphon), we still see the empirical manifestation of our
theoretical results.

###  6.2 Wide Network Behavior

Next, we analyze the effect of width on both the GNN and the GNTK when they
are trained/fitted on a small graph and transferred to a large graph. From the
NTK analysis by Jacot et al. (2018), as the GNN width increases we expect (i)
the GNTK and the GNN to exhibit less variance over multiple weight
initializations and (ii) the GNN outputs to approach those of kernel
regression with the GNTK.

For the opinion dynamics experiment on SBMs, we consider three GNNs with
widths (number of features) $F^{(1)}_{1}=10$, $F^{(2)}_{1}=50$, and
$F^{(3)}_{1}=250$ supported on the same $80$-node graph. Using their initial
weights, we construct the corresponding GNTKs. We train the three GNNs by
minimizing the MSE loss over $20$ epochs and with batch size $32$, using ADAM
(Kingma & Ba, 2015) with learning rate $1e^{-3}$ and weight decay $5e^{-3}$.
Simultaneously, we fit the GNTKs to the training set, and then transfer both
the GNNs and the corresponding GNTKs to the $N$-node graph and compute their
outputs on the test set.

In Fig. 2, we plot the projection of the outputs ${\mathbf{y}}$ onto the
second graph eigenvector ${\mathbf{v}}_{2}$,
$[{\hat{\mathbf{y}}}]_{2}={\mathbf{v}}_{2}^{T}{\mathbf{y}}$ against the
projections of the inputs onto the same vector
$[{\hat{\mathbf{x}}}]_{2}={\mathbf{v}}_{2}^{T}{\mathbf{x}}$ (sorted in
ascending order) for both the GNNs and the GNTKs for $F^{(1)}_{1}=10$ (left),
$F^{(2)}_{1}=50$ (center), and $F^{(3)}_{1}=250$ (right). The second graph
eigenvector was chosen as it captures the community structure, however, note
that the same behavior was observed upon projecting onto other eigenvectors,
as shown in Appendix C. The results are averaged over $5$ GNN initializations,
with the solid lines representing the mean and the shaded areas representing
the standard deviation. The behavior is as expected: as the width increases,
the GNN and the GNTK have smaller variance in behavior for different weight
initializations, and the GNN and GNTK curves align. In Appendix C, we include
additional plots displaying the mean and variance over different
initializations as we vary the graph size.

###  6.3 Application: Eigenvalue Convergence

In this section, we elucidate an important application of the convergence of
the GNTK. Jacot et al. (2018) shows that the convergence of kernel gradient
descent follows the kernel principal components. Therefore, if the GNN is
sufficiently wide, and
$f({\mathbf{X}}_{n};{\mathbf{A}}_{n},{\mathcal{H}}_{0})-f({\mathbf{X}}_{n};{\mathbf{S}}_{n},{\mathcal{H}}^{\star})$
is aligned with the $i$th GNTK principal component, we can expect gradient
descent to converge with rate proportional to $\lambda_{i}$, the $i$th
eigenvalue of the GNTK222Theoretically, constancy of the NTK in the infinite-
width limit and equivalence between GNN training and kernel regression only
holds for architectures with linear output layer (Liu et al., 2020). Although
this is not the case of the GNNs used here, GNTKs associated with GNNs with
nonlinear output layers seem to exhibit constancy empirically (Sabanayagam et
al., 2021).

Recall that we prove, in Thm. 2, that the spectrum of the GNTKs converge in
the graphon limit. In this context, a simple application of the convergence of
the GNTK spectrum is as follows: say that we know that
$f({\mathbf{X}}_{N};{\mathbf{A}}_{N},{\mathcal{H}}_{0})-f({\mathbf{X}}_{N};{\mathbf{A}}_{N},{\mathcal{H}}^{\star})$
is aligned with the $p$th GNTK eigenvector, and we want to estimate its speed
of convergence, but the kernel
$\Theta({\mathbf{X}}_{N},{\mathbf{X}}_{N}^{\prime};{\mathbf{A}}_{N},{\mathcal{H}})$
is too expensive to compute. We could in this case sample a graph
${\mathbf{G}}_{n}$, $n\ll N$ from the induced graphon ${\mathbf{W}}_{N}$ and
calculate
$\Theta({\mathbf{X}}_{n},{\mathbf{X}}_{n}^{\prime};{\mathbf{A}}_{n},{\mathcal{H}})$.
From Thm. 5.2, $\lambda_{n,p}$ converges to $\lambda_{N,p}$. Hence, for large
enough $n$, $\lambda_{n,p}$ should provide a good approximation of
$\lambda_{N,p}$.

To illustrate this empirically, in Fig. 3 we plot the dominant eigenvalues of
the GNTK associated with a GNN with $F_{1}=10$ features supported on graphs of
increasing size $n$ sampled from the Cora, CiteSeer, and PubMed networks
(averaged over 10 initializations). As $n$ grows, we see that the difference
between the dominant eigenvalues of consecutive GNTKs reduces. I.e., for each
citation dataset, the value of the dominant eigenvalue converges as $n$
increases, indicating that the speed of convergence of the GNN along the
dominant GNTK eigenvector converges as the graph grows. For all but the PubMed
dataset, the $1600$-node graph gives an approximation of $\lambda_{N,1}$ that
is over $70$% good.

##  7 Conclusions

In this paper, we define WNTKs as the limiting objects of GNTKs, and study how
the GNTK evolves as the underlying graph of the corresponding GNN grows. We
show that GNTKs converge to the WNTK and that their spectra also converges,
thus providing theoretical insight into how the learning dynamics of a GNN
evolves as an important dimension—the graph size—grows. In practice, these
convergences imply that one can transfer the GNTK of a smaller graph to solve
the same task on a larger graph without any further optimization, with
theoretical guarantees of performance and insight on the rates of learning
along eigendirections that converge as the graph grows. These results were
demonstrated through simulations on synthetic and real-world graphs. To
conclude, a limitation of this work is that graphons are only good models for
dense graphs. In future work, we plan to extend our results to more general
graph models, and to better understand the relationship between the spectra of
the graph and of the GNTK.

## References

  * Allen-Zhu et al. (2019) Allen-Zhu, Z., Li, Y., and Song, Z.  A convergence theory for deep learning via over-parameterization.  In _Int. Conf. Mach. Learning_ , pp. 242–252. PMLR, 2019.
  * Anselone & Palmer (1968) Anselone, P. and Palmer, T.  Spectral analysis of collectively compact, strongly convergent operator sequences.  _Pacific Journal of Mathematics_ , 25(3):423–431, 1968.
  * Arora et al. (2018) Arora, S., Cohen, N., and Hazan, E.  On the optimization of deep networks: Implicit acceleration by overparameterization.  In _Int. Conf. Mach. Learning_ , pp. 244–253. PMLR, 2018.
  * Arora et al. (2019a) Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R. R., and Wang, R.  On exact computation with an infinitely wide neural net.  _Neural Inform. Process. Syst._ , 32, 2019a.
  * Arora et al. (2019b) Arora, S., Du, S. S., Li, Z., Salakhutdinov, R., Wang, R., and Yu, D.  Harnessing the power of infinitely wide deep nets on small-data tasks.  _arXiv preprint arXiv:1910.01663_ , 2019b.
  * Bojchevski & Günnemann (2017) Bojchevski, A. and Günnemann, S.  Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking.  _arXiv:1707.03815 [cs.LG]_ , 2017.
  * Borgs et al. (2008) Borgs, C., Chayes, J. T., Lovász, L., Sós, V. T., and Vesztergombi, K.  Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing.  _Adv. Math._ , 219(6):1801–1851, 2008.
  * Cao & Gu (2019) Cao, Y. and Gu, Q.  Generalization bounds of stochastic gradient descent for wide and deep neural networks.  _Neural Inform. Process. Syst._ , 32, 2019.
  * Cerviño et al. (2023) Cerviño, J., Ruiz, L., and Ribeiro, A.  Learning by transference: Training graph neural networks on growing graphs.  _IEEE Trans. Signal Process._ , 71:233–247, 2023.  doi: 10.1109/TSP.2023.3242374.
  * Defferrard et al. (2016) Defferrard, M., Bresson, X., and Vandergheynst, P.  Convolutional neural networks on graphs with fast localized spectral filtering.  In _Neural Inform. Process. Syst._ , Barcelona, Spain, 5-10 Dec. 2016\. NIPS Foundation.
  * DeGroot (1974) DeGroot, M. H.  Reaching a consensus.  _Journal of the American Statistical association_ , 69(345):118–121, 1974.
  * Du et al. (2019) Du, S. S., Hou, K., Salakhutdinov, R. R., Poczos, B., Wang, R., and Xu, K.  Graph neural tangent kernel: Fusing graph neural networks with graph kernels.  In _Neural Inform. Process. Syst._ , volume 32, 2019.
  * Gama et al. (2018) Gama, F., G. Marques, A., Leus, G., and Ribeiro, A.  Convolutional neural network architectures for signals supported on graphs.  _IEEE Trans. Signal Process._ , 67:1034–1049, 2018.
  * Gilmer et al. (2017) Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E.  Neural message passing for quantum chemistry.  In _Int. Conf. Mach. Learning_ , pp. 1263–1272. PMLR, 2017.
  * Hamilton et al. (2017) Hamilton, W., Ying, Z., and Leskovec, J.  Inductive representation learning on large graphs.  _Neural Inform. Process. Syst._ , 30, 2017.
  * Harper & Konstan (2016) Harper, F. M. and Konstan, J. A.  The movielens datasets: History and context.  _ACM Trans. Interactive Intell. Syst._ , 5:1–19, Jan. 2016\.
  * Hegselmann et al. (2002) Hegselmann, R., Krause, U., et al.  Opinion dynamics and bounded confidence models, analysis, and simulation.  _Journal of artificial societies and social simulation_ , 5(3), 2002.
  * Huang et al. (2020) Huang, K., Wang, Y., Tao, M., and Zhao, T.  Why do deep residual networks generalize better than deep feedforward networks?—a neural tangent kernel perspective.  _Neural Inform. Process. Syst._ , 33:2698–2709, 2020.
  * Jacot et al. (2018) Jacot, A., Gabriel, F., and Hongler, C.  Neural tangent kernel: Convergence and generalization in neural networks.  _Neural Inform. Process. Syst._ , 31, 2018.
  * Keriven et al. (2020) Keriven, N., Bietti, A., and Vaiter, S.  Convergence and stability of graph convolutional networks on large random graphs.  In _34th Neural Inform. Process. Syst._ , volume 33, pp. 21512–21523. NeurIPS Foundation, 2020.
  * Kingma & Ba (2015) Kingma, D. P. and Ba, J. L.  ADAM: A method for stochastic optimization.  In _3rd Int. Conf. Learning Representations_ , San Diego, CA, 7-9 May 2015. Assoc. Comput. Linguistics.
  * Kipf & Welling (2017) Kipf, T. N. and Welling, M.  Semi-supervised classification with graph convolutional networks.  In _5th Int. Conf. Learning Representations_ , Toulon, France, 24-26 Apr. 2017. Assoc. Comput. Linguistics.
  * Lee et al. (2019) Lee, J., Xiao, L., Schoenholz, S., Bahri, Y., Novak, R., Sohl-Dickstein, J., and Pennington, J.  Wide neural networks of any depth evolve as linear models under gradient descent.  _Neural Inform. Process. Syst._ , 32, 2019.
  * Levie et al. (2021) Levie, R., Huang, W., Bucci, L., Bronstein, M., and Kutyniok, G.  Transferability of spectral graph convolutional neural networks.  _J. Mach. Learning Res._ , 22(272):1–59, 2021\.
  * Li et al. (2019) Li, Z., Wang, R., Yu, D., Du, S. S., Hu, W., Salakhutdinov, R., and Arora, S.  Enhanced convolutional neural tangent kernels.  _arXiv preprint arXiv:1911.00809_ , 2019.
  * Liu et al. (2020) Liu, C., Zhu, L., and Belkin, M.  On the linearity of large non-linear models: when and why the tangent kernel is constant.  _Neural Inform. Process. Syst._ , 33:15954–15964, 2020\.
  * Lorenz (2007) Lorenz, J.  Continuous opinion dynamics under bounded confidence: A survey.  _International Journal of Modern Physics C_ , 18(12):1819–1838, 2007.
  * Lovász (2012) Lovász, L.  _Large Networks and Graph Limits_ , volume 60.  American Mathematical Society, 2012.
  * Lovász & Szegedy (2006) Lovász, L. and Szegedy, B.  Limits of dense graph sequences.  _J. Comb. Theory, Series B_ , 96(6):933–957, 2006\.
  * Maskey et al. (2022) Maskey, S., Levie, R., Lee, Y., and Kutyniok, G.  Generalization analysis of message passing neural networks on large random graphs.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Maskey et al. (2023) Maskey, S., Levie, R., and Kutyniok, G.  Transferability of graph neural networks: an extended graphon approach.  _Applied and Computational Harmonic Analysis_ , 63:48–83, 2023.
  * Neal & Neal (1996) Neal, R. M. and Neal, R. M.  Priors for infinite networks.  _Bayesian learning for neural networks_ , pp. 29–53, 1996.
  * Ruiz et al. (2020) Ruiz, L., Chamon, L. F. O., and Ribeiro, A.  Graphon neural networks and the transferability of graph neural networks.  In _34th Neural Inform. Process. Syst._ , Vancouver, BC (Virtual), 6-12 Dec. 2020. NeurIPS Foundation.
  * Ruiz et al. (2021a) Ruiz, L., Chamon, L. F. O., and Ribeiro, A.  Graphon signal processing.  _IEEE Trans. Signal Process._ , 69:4961–4976, 2021a.
  * Ruiz et al. (2021b) Ruiz, L., Chamon, L. F. O., and Ribeiro, A.  Transferability properties of graph neural networks.  _arXiv:2112.04629 [eess.SP]. Submitted to IEEE TSP_ , 2021b.
  * Sabanayagam et al. (2021) Sabanayagam, M., Esser, P., and Ghoshdastidar, D.  New insights into graph convolutional networks using neural tangent kernels.  _arXiv preprint arXiv:2110.04060_ , 2021.
  * Shuman et al. (2013) Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., and Vandergheynst, P.  The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.  _IEEE Signal Process. Mag._ , 30(3):83–98, May 2013.
  * Williams (1996) Williams, C.  Computing with infinite networks.  _Neural Inform. Process. Syst._ , 9, 1996.
  * Xia et al. (2022) Xia, X., Mishne, G., and Wang, Y.  Implicit graphon neural representation.  _arXiv preprint arXiv:2211.03329_ , 2022.
  * Xu et al. (2019) Xu, K., Hu, W., Leskovec, J., and Jegelka, S.  How powerful are graph neural networks?  In _7th Int. Conf. Learning Representations_ , pp. 1–17, New Orleans, LA, 6-9 May 2019. Assoc. Comput. Linguistics.
  * Yehudai et al. (2021) Yehudai, G., Fetaya, E., Meirom, E., Chechik, G., and Maron, H.  From local structures to size generalization in graph neural networks.  In _Int. Conf. Mach. Learning_ , pp. 11975–11986. PMLR, 2021.

##  Appendix A Proof of GNTK Convergence

###### Proof of Thm. 5.1.

To simplify notation, we will write
$\Theta(X,X^{\prime};{\mathbf{W}},{\mathcal{H}})=\Theta(X,X^{\prime})$ and
$\Theta(X_{n},X_{n}^{\prime};{\mathbf{W}}_{n},{\mathcal{H}})=\Theta(X_{n},X_{n}^{\prime})$.
Let $Y$ be an arbitrary $L^{2}$ signal. Using the triangle inequality,

$\displaystyle\begin{split}||\Theta(X,X^{\prime})Y-\Theta(X_{n},X_{n}^{\prime})Y||&\leq\sum_{k}||\sigma^{\prime}(U_{L})T_{W}^{(k)}X_{L-1}\langle\sigma^{\prime}(U_{L}^{\prime})T_{W}^{(k)}X_{L-1}^{\prime},Y\rangle\\\
&\quad-\sigma^{\prime}(U_{L,n})T_{W_{n}}^{(k)}X_{n,L-1}\langle\sigma^{\prime}(U_{L,n}^{\prime})T_{W_{n}}^{(k)}X_{L-1,n}^{\prime}Y\rangle||+\ldots\end{split}$
(16)

where there are $L$ terms for each $k$.

Since $\sigma$ is Lipschitz, from the formula we see that it suffices to prove
the following convergence statements for all $k\in{1,...,K-1}$ as
$n\to\infty$:

$\displaystyle\|U_{l,n}$ $\displaystyle-U_{l}\|\to 0$ (17)
$\displaystyle\|U_{l,n}^{\prime}$ $\displaystyle-U^{\prime}_{l}\|\to 0$ (18)

as well as

$\displaystyle\left|\left|T_{W_{n}}^{(k)}-T_{W}^{(k)}\right|\right|\to 0$ (19)
$\displaystyle\left|\left|T_{h_{l,n}}-T_{h_{l}}\right|\right|\to 0\text{.}$
(20)

These are proved for a more general class of (analytic) filters (i.e. with
$K\to\infty$ in a controlled way) using Fourier transforms in Appendix D of
the previous paper (cite). Here, we prove these statements for each finite $K$
using mathematical induction. Luana can you rewrite these lines: Still, our
result also holds for general analytic filters, because any polynomial in
$[0,1]$ is Lipschitz—ensuring the convergence (30) from (cite))—, and,
provided that the $H_{n,l}$ are Lipschitz, (31) converges per (cite). Is that
so clear? We would need to quantify the rate of convergence in terms of both
$k$ and $n$ in a more careful way I think, so a longer explanation I think
might be warranted to say we can do the case $K\to\infty$. It looks like if
$k^{2}/n\to 0$ then we can send $K\to\infty$ along with $n\to\infty$, provided
the $h_{k}$’s aren’t doing anything too crazy. For fixed, finite $K$, (19)
implies (20). The convergence in (17) and (18) are essentially the same, so
let us focus on the first without loss of generality. Expanding the first
layer, we have

$\displaystyle U_{1,n}-U_{1}$
$\displaystyle=\sum_{k}h_{1,k}(T_{W_{n}}^{(k)}X_{n}-T_{W}^{(k)}X)=\sum_{k}h_{1,k}(T_{W_{n}}^{(k)}X_{n}-T_{W}^{(k)}X+T_{W}^{(k)}X_{n}-T_{W}^{(k)}X_{n})$
$\displaystyle=\sum_{k}h_{1,k}((T_{W_{n}}^{(k)}-T_{W}^{k})X_{n}+T_{W}^{(k)}(X_{n}-X)).$

Therefore, by the triangle inequality and the definition of the operator norm,
we have

$\displaystyle\|U_{1,n}-U_{1}\|$
$\displaystyle\leq\sum_{k}|h_{1,k}|\|T_{W_{n}}^{(k)}-T_{W}^{k}\|\|X_{n}\|+\sum_{k}|h_{1,k}|\left|\left|T_{W}^{(k)}\right|\right|\|X_{n}-X\|$
(21)
$\displaystyle\leq\sum_{k}\max(|h_{1,k}|)\|T_{W_{n}}^{(k)}-T_{W}^{k}\|\|X_{n}\|+\sum_{k}\max(|h_{1,k}|)\|T_{W}^{(k)}\|\|X_{n}-X\|.$
(22)

Looking at layer $l$, we have

$\displaystyle
U_{l,n}-U_{l}=\sum_{k}h_{l,k}(T_{W_{n}}^{(k)}\sigma(U_{l-1,n})-T_{W}^{(k)}\sigma(U_{l-1})).$

From 22, using mathematical induction, we have, for arbitrary $l$,

$\displaystyle\|U_{l,n}-U_{l}\|$
$\displaystyle\leq(\|X_{n}\|\|X_{n}-X\|+\|T_{W_{n}}^{(k)}-T_{W}^{k}\|)\cdot(\max(|h|)k)^{l}$
(23)
$\displaystyle+\sum_{j=1}^{l-1}(\max(|h|)k)^{l-1-j}\max(|h|)\|T_{W_{n}}^{(k)}-T_{W}^{k}\|$
(24)

where $h$ is the max of $h_{l,k}$ over all $l$ and $k$, and so convergence of
$T_{W_{n}}^{(k)}\to T_{W}^{(k)}$ as in (19) and $X_{n}\to X$ implies
convergence of $U_{1,n}\to U_{1}$ and $U_{l,n}\to U_{l}$. Since the
nonlinearity $\sigma$ is Lipschitz, convergence of (18) follows from
convergence of (17).

We now focus on proving (19). By Cauchy-Schwarz,

$\displaystyle\left|\left|(T_{W_{n}}-T_{W})Y\right|\right|^{2}$
$\displaystyle=\int_{0}^{1}\left(\int_{0}^{1}({\mathbf{W}}_{n}(u,v)-{\mathbf{W}}(u,v))Y(v)dv\right)^{2}du$
$\displaystyle\leq\left(\int_{0}^{1}\int_{0}^{1}({\mathbf{W}}_{n}(u,v)-{\mathbf{W}}(u,v))^{2}dvdu\right)||Y||^{2}.$

Therefore, taking the square root, dividing by $||Y||$, and using (13), we get

$\displaystyle\left|\left|T_{W_{n}}-T_{W}\right|\right|\leq\left|\left|{\mathbf{W}}_{n}-{\mathbf{W}}\right|\right|_{L^{2}}.$
(25)

It follows that convergence of the induced graphons ${\mathbf{W}}_{n}$ to the
limiting graphon ${\mathbf{W}}$ implies (19) for $k=1$. For higher iterates we
note

$\displaystyle\left|\left|(T_{W_{n}}^{(k)}-T_{W}^{(k)})Y\right|\right|^{2}$
$\displaystyle\leq{\int_{0}^{1}\left(\int_{0}^{1}({\mathbf{W}}_{n}T_{W_{n}}^{(k-1)}Y(v)-{\mathbf{W}}T_{W}^{k-1}Y(v))dv\right)^{2}du}$
$\displaystyle\leq{\int_{0}^{1}\left(\int_{0}^{1}{\mathbf{W}}_{n}(T_{W_{n}}^{(k-1)}-T_{W}^{(k-1)})Y(v)dv\right)^{2}du}+{\int_{0}^{1}\left(\int_{0}^{1}({\mathbf{W}}_{n}-{\mathbf{W}})T_{W}^{(k-1)}Y(v)dv\right)^{2}du}.$

Therefore, by the same Cauchy-Schwarz argument above,
$\left|\left|T_{W_{n}}^{(k)}-T_{W}^{(k)}\right|\right|$ is upper bounded by

$\displaystyle\left|\left|{\mathbf{W}}_{n}\right|\right|\left|\left|T_{W_{n}}^{(k-1)}-T_{W}^{(k-1)}\right|\right|+\left|\left|{\mathbf{W}}_{n}-W\right|\right|\left|\left|T_{W}^{(k-1)}\right|\right|$

and so convergence ${\mathbf{W}}_{n}\to{\mathbf{W}}$ implies the convergence
of all the iterates $T^{(k)}_{W_{n}}\to T^{(k)}_{W}$ by induction. In fact,
one can write

$\displaystyle\left|\left|T_{W_{n}}^{(k)}-T_{W}^{(k)}\right|\right|\leq
k\left|\left|{\mathbf{W}}_{n}-{\mathbf{W}}\right|\right|_{L^{2}}$ (26)

since $\left|\left|T_{W}^{(k-1)}\right|\right|\leq 1$ and
$\left|\left|{\mathbf{W}}_{n}\right|\right|\leq 1$.

From the proof one can, with some simple algebra, compute a quantitative
estimate of
$\left|\left|\Theta(X_{n},X_{n}^{\prime})-\Theta(X,X^{\prime})\right|\right|$
in terms of $\left|\left|{\mathbf{W}}_{n}-{\mathbf{W}}\right|\right|$,
$\left|\left|X_{n}-X\right|\right|$, $\left|\left|X\right|\right|$ and
$\left|\left|X^{\prime}\right|\right|$. Precisely, by adding and subtracting
cross-terms for each term in (16) and using the triangle inequality, we get

$\displaystyle\left|\left|\Theta(X_{n},X_{n}^{\prime})-\Theta(X,X^{\prime})\right|\right|\leq
C(K^{4+L}\left|\left|{\mathbf{W}}_{n}-{\mathbf{W}}\right|\right|+K^{2+L}\left|\left|X_{n}-X\right|\right|),$
(27)

where $C$ is a constant in terms of $\|X\|,\|X^{\prime}\|,max(|h|),l$. For
different choices of graphs, one can then compute these quantities for an
explicit estimate of the convergence bound. (Ruiz et al., 2021b)[Appendix B]
provides quantitative estimates on
$\left|\left|{\mathbf{W}}_{n}-{\mathbf{W}}\right|\right|$ and
$\left|\left|X_{n}-X\right|\right|$ for random graph models such as so-called
template graphs, weighted graphs and stochastic graphs.

∎

##  Appendix B Proof of Spectrum Convergence

###### Proof of Theorem 5.2.

The proof relies on (Anselone & Palmer, 1968)[Prop. 7.1] which proves that if
a sequence of compact operators $T_{n}$ converges to a compact operator $T$ in
the appropriate operator norm, the spectrum of $T_{n}$ converges to the
spectrum of $T$. Additionally, from (Anselone & Palmer, 1968)[Thm. 6.3 and
Prop 7.1], for every $p$, the eigenspace associated with the $p^{th}$
eigenvalue of $T_{n}$ also converge to the corresponding eigenspace of $T$.
From Thm. 5.1, we know that $\boldsymbol{\Theta}_{n}\to\boldsymbol{\Theta}$.
It remains to show that $\boldsymbol{\Theta}_{n}$ and $\boldsymbol{\Theta}$
are compact.

For any graphon ${\mathbf{W}}$, the operators $T_{W}^{(k)}$ and $T_{H}$ [cf.
(6)] are compact as they are linear compositions of compact operators with
bounded linear weights. From (12), we thus conclude
$\|\Theta(X,X^{\prime};{\mathbf{W}},{\mathcal{H}})\|<\infty$. Therefore, for
$Y\in L^{2}([0,1])$,
$\|\Theta(X,X^{\prime};{\mathbf{W}},{\mathcal{H}})Y\|<\infty$, by which we
conclude that $\boldsymbol{\Theta}$ is compact. ∎

Figure 4: Projections of the inputs and outputs of the GNTK and GNN, and of
the target or true labels onto the first eigenvector of the adjacency matrix
of a $n$-node SBM graph for widths $F=10$ (left), $F=50$ (center) and $F=250$
(right). From top to bottom $n=20,40,60,90,100$.

##  Appendix C Wide Network Behavior: Additional Experiments

Under the same expeirmental setting of Sec. 6.2, in Fig. 4, we plot the
projection of the outputs ${\mathbf{y}}$ onto the first graph eigenvector
${\mathbf{v}}_{1}$,
$[{\hat{\mathbf{y}}}]_{1}={\mathbf{v}}_{1}^{T}{\mathbf{y}}$ against the
projections of the inputs onto the same vector
$[{\hat{\mathbf{x}}}]_{1}={\mathbf{v}}_{1}^{T}{\mathbf{x}}$ (sorted in
ascending order) for both the GNNs and the GNTKs for $F^{(1)}_{1}=10$ (left),
$F^{(2)}_{1}=50$ (center), and $F^{(3)}_{1}=250$ (right), and
$n=20,40,60,80,100$ (top to bottom). The results are averaged over $5$ GNN
initializations, with the solid lines representing the mean and the shaded
areas representing the standard deviation. The behavior is as expected: as the
width increases, the GNN and the GNTK have smaller variance in behavior for
different weight initializations, and the GNN and GNTK curves align. As $n$
increases, we also observe a slight improvement in the variance of the GNN
curves. This is expected as, when GNNs are trained on larger graphs, they have
better transferability (Ruiz et al., 2020). No significant trends are observed
for the GNTK curves for increasing $n$.


[1]#1 [1]

[sigconf]acmart BibTeX

2023 2023 acmlicensed[ApPLIED 2023]The 5th workshop on Advanced tools,
programming languages, and PLatforms for Implementing and Evaluating
algorithms for Distributed systemsJune 19, 2023Orlando, FL, USA The 5th
workshop on Advanced tools, programming languages, and PLatforms for
Implementing and Evaluating algorithms for Distributed systems (ApPLIED 2023),
June 19, 2023, Orlando, FL, USA 15.00 10.1145/3584684.3597275
979-8-4007-0128-3/23/06

graphicx appendix listings alltt url [1]#1ex [1]#1ex [1]2#1. .0 [1].0-0#1.-.0
enumitem leftmargin=64ex, itemsep=.6ex code-.0alltt