# Infinite Width Graph Neural Networks for Node Regression/ Classification

Yunus<EMAIL_ADDRESS>work done as part of the Master
Thesis at the Department of Mathematics, Technical University of Munich

###### Abstract

This work analyzes Graph Neural Networks, a generalization of Fully-Connected
Deep Neural Nets on Graph structured data, when their width, that is the
number of nodes in each fully-connected layer is increasing to infinity.
Infinite Width Neural Networks are connecting Deep Learning to Gaussian
Processes and Kernels, both Machine Learning Frameworks with long traditions
and extensive theoretical foundations. Gaussian Processes and Kernels have
much less hyperparameters then Neural Networks and can be used for uncertainty
estimation, making them more user friendly for applications. This works
extends the increasing amount of research connecting Gaussian Processes and
Kernels to Neural Networks. The Kernel and Gaussian Process closed forms are
derived for a variety of architectures, namely the standard Graph Neural
Network, the Graph Neural Network with Skip-Concatenate Connections and the
Graph Attention Neural Network. All architectures are evaluated on a variety
of datasets on the task of transductive Node Regression and Classification.
Additionally, a Spectral Sparsification method known as Effective Resistance
is used to improve runtime and memory requirements. Extending the setting to
inductive graph learning tasks (Graph Regression/ Classification) is
straightforward and is briefly discussed in 3.5.

###### Contents

  1. 1 Introduction
    1. 1.1 Notation
    2. 1.2 Graph Neural Networks generalize Fully-Connected Deep Nets
  2. 2 Related Work
  3. 3 Infinite Width Graph Neural Networks
    1. 3.1 Recap: Fully-Connected Deep Nets
      1. 3.1.1 Gaussian Process
      2. 3.1.2 Neural Tangent Kernel
    2. 3.2 Graph Neural Networks
      1. 3.2.1 Graph Neural Network Gaussian Process
      2. 3.2.2 Graph Neural Tangent Kernel
    3. 3.3 Skip-Concatenate Graph Neural Network
      1. 3.3.1 Skip-Concatenate Graph Neural Network Gaussian Process
      2. 3.3.2 Skip-Concatenate Graph Neural Tangent Kernel
    4. 3.4 Graph Attention Neural Network
      1. 3.4.1 Gaussian Process
      2. 3.4.2 Neural Tangent Kernel
    5. 3.5 Infinite Width Graph Neural Networks for Graph Regression/ Classification
  4. 4 Experiments
    1. 4.1 Simulations
    2. 4.2 Datasets, Models & Evaluation
    3. 4.3 Code & Environment
    4. 4.4 Effective Resistance Spectral Graph Sparsification
    5. 4.5 Role of bias $\sigma_{b}^{2}$ for Regression
  5. 5 Conclusion
  6. A Appendix
    1. A.1 Fully-connected Deep Nets
      1. A.1.1 Gaussian Process (Theorem 3.1)
      2. A.1.2 Neural Tangent Kernel (Lemma A.1 and Theorem 3.1)
    2. A.2 NTK & GP for Graph Neural Network
      1. A.2.1 Gaussian Process (Theorem 3.3)
      2. A.2.2 Neural Tangent Kernel (Theorem 3.4)
    3. A.3 NTK & GP for Graph Neural Network with Skip-Concatenate Connections
      1. A.3.1 Gaussian Process (Theorem 3.5)
      2. A.3.2 Neural Tangent Kernel (Theorem 3.6)
    4. A.4 NTK & GP for Graph Attention Neural Network*
      1. A.4.1 Gaussian Process (Theorem 3.7)
      2. A.4.2 Neural Tangent Kernel (Theorem 3.8)

##  1 Introduction

Graph Neural Networks (GNNs), introduced in the paper [Kipf and Welling, 2017]
demonstrated their effectiveness in tasks involving graph-structured data,
like Node Regression/ Classification. GNNs have become a staple tool for Data
Scientists and a prominent area of research in Machine Learning. In recent
research, GNNs have been extended to different architectures such as Graph
Attention Neural Networks [Veličković et al., 2018], Transformer Graph Neural
Networks [Shi et al., 2021] and others. Since its’ inception, the GNN
framework has also been extended to inductive Learning tasks like Graph
Classification [Hamilton et al., 2017] and unsupervised learning tasks with a
Graph (Variational) Autoencoder [Kipf and Welling, 2016].
Another very active area of research are infinite width Neural Networks, also
referred to as Neural Tangent Kernels (NTK), introduced in the paper [Jacot et
al., 2018]. NTK establish link between Infinite Width Fully-Connected Deep
Neural Nets (FCN) and Kernels. NTK theory has been expanded to various
architectures [Yang, 2020] and used to analyze theoretical properties like
Generalization and Optimization [Arora et al., 2019, Du et al., 2019a]. It
sheds light on the importance of appropriate random initialization for
successful training [Xiao et al., 2020, Seleznova and Kutyniok, 2022]. This
work consists of extending Infinite Width Neural Network Theory to the setting
of Graph Neural Networks. The main contributions222Code is available at
https://github.com/yCobanoglu/infinite-width-gnns are

  1. 1.

Closed form expressions for the Graph Neural Networks Gaussian Process (GNNGP)
and Graph Neural Tangent Kernel (GNTK) for three different Graph Neural
Network Architectures on the task of Node Regression/ Classification, namely:
the Graph Neural Network, the Skip-Concatenate Graph Neural Network and the
Graph Attention Neural Network.

  2. 2.

Evaluation of GNNGP and GNTK to their Neural Network counterparts on a variety
of Datasets on the task of Node Classification/ Regression (including applying
Effective Resistance as a Spectral Graph Sparsification Method to improve
memory and runtime requirements.

###  1.1 Notation

Superscript for matrices (i.e. $W^{L}$) are identifiers and not matrix powers.
$I_{n}\in\mathbb{R}^{n\times n}$ is the identitiy Matrix. We define the
operator batchmultiply; $\operatorname{\mathrm{batchm}}(X,Y)_{ij}=\langle
X,Y_{IJ}\rangle_{F}$ with $X\in\mathbb{R}^{n\times n}$ and
$Y\in\mathbb{R}^{zn\times zn}$ for some integer $z$. So
$\operatorname{\mathrm{batchm}}(\cdot,\cdot)$ is taking the Frobenius Inner
Product of $X$ and block $IJ$ of size $n\times n$ of $Y$ and
$\operatorname{\mathrm{batchm}}(X,Y)\in\mathbb{R}^{z\times z}$. Concatenating
vectors/matrices horizontally is denoted $\operatorname{concat}(\cdot,\cdot)$.
The Hadamard Product is denoted with $\odot$. Convergence in probability is
denoted as $\overset{P}{\longrightarrow}$.

###  1.2 Graph Neural Networks generalize Fully-Connected Deep Nets

Graph Neural Networks (GNNs) are a powerful generalization of Fully-Connected
Nets (FCN). GNNs are extending the FCNs by making use of dependent data
samples, naturally incorporating unlabelled data, referred to as semi-
supervised learning and allowing for transductive learning tasks such as Node
Regression and Classification as well as inductives tasks like Graph
Regression/ Classification. We will start by establishing this connection
between FCNs and GNNs. A three layer Fully Connected Deep Neural Net (FCN) can
be defined as follows:

$\displaystyle f(x)$
$\displaystyle=W^{3}\sigma(W^{2}(\sigma(W^{1}x))\in\mathbb{R}^{d_{3}}$

with $x\in\mathbb{R}^{d_{0}}$ and Weights $W^{l}\in\mathbb{R}^{d_{l}\times
d_{l-1}}$. The single data point $x$ is a column vector of a batch of data
$X\in\mathbb{R}^{d_{0}\times n}$. Now defining a GNN as defined in Kipf and
Welling [2017]. Given a Graph Adjacency Matrix $A\in\mathbb{R}^{n\times n}$
and the data $X\in\mathbb{R}^{n\times d_{0}}$, the GNN is:

$\displaystyle
g(X)=A\sigma(A\sigma(AXW^{1})W^{2})W^{3}\in\mathbb{R}^{d_{L}\times n}$ (1)

with $W^{l}\in\mathbb{R}^{d_{l-1}\times d_{l}}$. There are different options
for the Adjacency Matrix $A$. The Adjacency Matrix can be the 0-1 Adjacency
Matrix of an undirected Graph, denoted as $A_{0\textbf{-}1}$. $A$ can be
$A_{0\textbf{-}1}+I$, which is the 0-1 Adjacency Matrix with self loops. $A$
can be the Laplacian Matrix $L=D-A$ with $D$ being the Degree Matrix,
$D_{ii}=\sum_{ij}A_{ij}$. One can use row, column or row & column
normalization on the Laplacian. $A$ can be Degree Normalized according to Kipf
and Welling [2017], which we will call Kipf & Welling Normalization, which is
$A=(D+I)^{-\frac{1}{2}}(A+I)(D+I)^{-\frac{1}{2}}$, with D being defined as
above. A can also be a directed Graph (e.g the Non-Backtracking Matrix as in
Chen et al. [2019]). If we set $A$ as the Identity Matrix $I$ and take the
transpose of $g(X)$, we end up with:

$\displaystyle
g(X)^{T}=W^{3^{T}}\sigma(W^{{2^{T}}}(\sigma(W^{1^{T}}X^{T}))\in\mathbb{R}^{d_{3}\times
n}$

$g(X)^{T}$ is equivalent to a FCN $f(X)$ where we pass as input all of the
(training and test) data $X$ instead of a single data point $x$. In the case
of Node Regression the training loss is minimized as follows:

$\displaystyle\underset{W}{\operatorname{argmin}}(||(Y^{T}-g(X)^{T})I_{train}||_{F}^{2})$
with $I_{train}=\operatorname{diag}([0,0,1,0,1,...,0,1])$

$I_{train}\in\mathbb{R}^{n\times n}$ consists of randomly selected diagonal
0,1 entries which correspond to the training samples. $I_{test}$ is defined as
$I_{test}=I_{n}-I_{train}$. We have Labels Y $\in\mathbb{R}^{n}$ and the
puropse of $I_{train}$ is to randomly select columns of $g(X)^{T}$ over which
the training loss is minimized. Columns in $g(X)^{T}$ correspond to individual
training samples when the GNN reduces to a FCN (i.e. $g(X)^{T}=f(X)$) or
individual nodes in when $g(X)^{T}$ is a proper GNN, in which case we will
call this setup Node Regression/Classification. The task of Node Regression/
Classification for Graph Neural Networks with the Identity Matrix is
equivalent to training a Neural Network with Gradient descent. Stochastic
Gradient Descent (SGD) can be generalized to GNNs in a straightforward manner,
too.

$\displaystyle
g(X)^{T}=W^{3^{T}}\sigma(W^{{2^{T}}}(\sigma(W^{1^{T}}X^{T}\operatorname{dropout}(I)))$

Sampling from $I$ without replacement some subset with size k is equivalent to
minimizing our objective using SGD with batch size k. This can be emulated
using dropout. To be precise Dropout generally is not sampling random subset
without replacement but with replacement. We can extend this now to GNNs.

$\displaystyle
g(X)^{T}=W^{3^{T}}\sigma(W^{{2^{T}}}(\sigma(W^{1^{T}}X^{T}\operatorname{dropout}(A))A)A$

It is more common to apply dropout to the adjacency A at every layer of the
GNN. One can complement this approach by additionally adding Dropout to the
weights how it is traditionally done in FCNs. Having established that GNNs are
generalizations of FCN, we can see the same being true for the Graph Neural
Network Gaussian Process (GNNGP) and Neural Network Gaussian Process (NNGP)
and similarly for the Graph Neural Tangent Kernel (GNTK) and Neural Tangent
Kernel (NTK). When plugging in the Identitiy Matrix $I$ as the Adjacency
Matrix $A$ into the closed form expressions of the GNNGP and GNTK, both
expressions are going to reduce to the closed form expression of the NNGP and
the NTK. The learning task of Node Regression/ Classification using GNNs, is a
transductive Learning Task. For a formal definition the reader is referred to
[Vapnik, 2006, transductive learning Section 10.1, Setting 1]. Transductive
learning means that the Learning Algorithm can incorporate the test data
during training. The test error is then evaluated on the test data with
labels. For the GNNs we can see that the expression $AXW$ in 1 can be
interpreted as, a linear transformation of the data X where each column
represents a single node feature of the Graph and an summation over all the
Neighbours of each Node, so $(AXW)_{i}=\sum_{k\in\text{Neighbours}(i)}x_{k}W$
(when $A$ is the standart 0-1 Adjacency Matrix). This summation will include
neighbouring nodes which could be part of the test set. That is precisely why
it is a transductive learning task. Unlabelled nodes similar to test nodes can
be used during training in the same manner. Cora [Yang et al., 2016] is
popular dataset which has unlabelled nodes. The Ability to incorporate
unlabelled Nodes is why Node Regression/ Classification is sometimes referred
to as semi-supervised learning.

##  2 Related Work

The Graph Neural Tangent Kernel (GNTK) for Graph Classification/ Regression
(inductive learning task as opposed to transductive Node Classification/
Regression, investigated in this work) was derived for the special case of $A$
being the 0-1 Adjacency with added self loops in Du et al. [2019b]. We will
see how their derivation can bee seen as a special case of our formulas as we
do not include any assumptions on $A$. Our GNTK formulas are easily extended
to the inductive learning setting in 3.5. Niu et al. [2023] derived the GNNGP
expression for the standart GNN with the 0-1 Adjacency Matrix known as GIN [Xu
et al., 2019], the Kipf & Welling Normalized Adjcacency as defined in section
1 and two variants of GNNS with Skip-Connections, namely the GraphSage
[Hamilton et al., 2017] and GCNII [Chen et al., 2020]. These Skip-Connections
are different from our Skip-Concatenate as the output of one Layer is a
summation of the postactivation and preactivations whereas we are
concatenating the postactivation and preactivations. Work on the GNTK for Node
Classification/Regression has been done by [Sabanayagam et al., 2022]. However
the authors ended up with an incorrect derivation of the GNTK for Node
Classification/ Regression namely,

######  Theorem 2.1 (incorrect, from [Sabanayagam et al., 2022, Theorem 1 (NTK
for Vanilla GCN)]).

For the vanilla GCN defined in (1) (with the difference that S is the
Adjacency Matrix and not A), the NTK $\Theta$ is given by

$\displaystyle\Theta$
$\displaystyle=\biggr{[}\sum_{i=1}^{d+1}\Sigma_{i}\odot(SS^{T})^{\odot(d+1-i)}\odot\bigl{(}\odot^{d+1-i}_{j=i}\dot{E}_{j}\bigr{)}\biggr{]}$
$\displaystyle\odot\,\underset{f\sim\mathcal{N}(0,\Sigma_{d})}{\mathbb{E}}[\dot{\Phi}(f)\dot{\Phi}(f)^{T}]$

Here $\Sigma_{i}\in\mathbb{R}^{n\times n}$ is the co-variance between nodes of
the layer $f_{i}$, and is given by $\Sigma_{1}:=SXX^{T}S^{T}$,
$\Sigma_{i}:=SE_{i-1}S^{T}$ with
$E_{i}:=c_{\sigma}\underset{f\sim\mathcal{N}(0,\Sigma_{i})}{\mathbb{E}}[\sigma(f)\sigma(f)^{T}]$
and
$\dot{E}_{i}:=c_{\sigma}\underset{f\sim\mathcal{N}(0,\Sigma_{i})}{\mathbb{E}}[\dot{\sigma}(f)\dot{\sigma}(f)^{T}]$.
$\Phi(x)\approx\frac{1}{1+e^{-x}}$ (i.e Sigmoid function).

Without going into the details of this Theorem it is straightforward to see
that when replacing $S$ with the Identity Matrix the Graph Neural Tangent
formula is not reducing to the Neural Tangent formula for Fully-Connected Deep
Nets. The final result will be a Kernel Matrix with all entries zero other
than the entries on the diagonal which can not be correct. For comparison the
correct GNTK is given in 3.4 and the NTK expression is given in 3.1.2).
Sabanayagam et al. [2023] used this wrongly derived GNTK in subsequent work to
investigate representational properties of the GNTK. The derivation of the
Graph Attention NTK and GP is conducted using results from Hron et al. [2020],
Yang [2019], as the NTK and GP for Attention Neural Networks are closely
related to the Graph Attention Neural Network.

##  3 Infinite Width Graph Neural Networks

Before stating the main results of this work we are going to summarize the
results on Infinite Width Fully-Connected Networks as our derivations for
Infinite Width Graph Neural Networks will be reduced to the Fully-Connected
derivations.

###  3.1 Recap: Fully-Connected Deep Nets

In Lemma A.1 we prove how the output of an FCN during training with $l_{2}$
loss with Gradient Flow (i.e. infinitesimally step size for Gradient Descent)
can be described by the following differential equation:

$\displaystyle\frac{du(\theta(t))}{dt}=\frac{\partial
u(\theta(t))}{\partial\theta}\left(\frac{\partial
u(\theta(t))}{\partial\theta}\right)^{T}\left(u(\theta(t))-\operatorname{vec}(Y)\right)$
(2)

with $u(\theta(t)):=\operatorname{vec}(F(\theta(t),X))$ and $\theta$ being all
trainable parameters flattened to a vector. This equation nothing is else then
Kernel Regression under Gradient Flow. When all widths of the hidden Layers of
$F(\theta(t),X))$ go to infinity, $\frac{\partial
u(\theta(t))}{\partial\theta}\left(\frac{\partial
u(\theta(t))}{\partial\theta}\right)^{T}=\Theta$ has a closed form expression
which stays constant during training and the equation reduces to Kernel
Regression. $\Theta$ is referred to as the NTK. For increased width during
training we can observe 1) the training loss approaches zero 2) the weights of
the GNN stay close to its initialization (measured in relative Frobenius norm)
and the empirical NTK, (i.e. $\frac{\partial
u(\theta(t))}{\partial\theta}\left(\frac{\partial
u(\theta(t))}{\partial\theta}\right)^{T}$) stays close to its initialization
during training. All these observations could be proven in the case of Fully-
Connected Deep Nets [Arora et al., 2019, Jacot et al., 2018]. The proof of 1)
consists of showing that the empirical NTK stays positive definite during
training [Du et al., 2019c, Lemma 3.3]. Proof of 2) consists of first showing
that during initialization the empirical NTK is close to the closed form
formula (which is derived by letting the widths of each layer go to infinity).
After that one is left with showing that during training the weights do not
change by a lot using Gradient Flow Dynamics and interpreting training as a
Perturbation on the Networks weights. For a detailed proof the reader is
referred to Arora et al. [2019]. Simulations in 4.1 confirm 1), 2) and 3) for
wide widths GNNs for Node Regression/ Classification using the Kipf & Welling
Normalized Adjacency Matrix and the GAT Model with the 0-1 Adjacency with self
loops. In the following sections we are stating the closed form expressions
for the NNGP and the NTK for Fully-Connected Deep Neural Nets. We are going to
formally define FCNs and rederive the NNGP and NTK closed form expressions.
The Weight Matrices are $W^{h}\in\mathbb{R}^{d_{h}\times d_{h-1}}$ and Data
Matrix is $X\in\mathbb{R}^{d_{0}\times n}$ where $d_{0}$ is the feature
dimension of the data and $n$ is number of data samples. $B$ denotes the rank-
one bias matrix. $\sigma$ is a non-linearity (e.g. Relu) and is applied
elementwise.

######  Definition 3.1 (Fully-connected Deep Neural Nets).

$\displaystyle F^{h}(X)$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{h-1}}}W^{h}G^{h-1}(X)+\sigma_{b}B^{h}\in\mathbb{R}^{d_{h}\times
n}$ $\displaystyle\text{with }B^{h}$
$\displaystyle=b^{h}\otimes\mathbf{1}_{n}^{T}\text{ and
}b^{h}\in\mathbb{R}^{d_{h}}$ $\displaystyle G^{h}(X)$
$\displaystyle=\sigma(F^{h}(X))$ $\displaystyle G^{0}$
$\displaystyle=X\in\mathbb{R}^{d_{0}\times n}$

The Weights are initialized as $W^{h}\sim N(0,1)$ and $b^{h}\sim N(0,1)$.
The final Network is
$F^{L}(X)=\frac{\sigma_{w}}{\sqrt{d_{L-1}}}W^{L}G^{L-1}(X)+\sigma_{b}B^{L}\in\mathbb{R}^{d_{L}\times
n}$

####  3.1.1 Gaussian Process

The FCN and NNGP equivalence first was shown by [Neal, 1996] for a one Layer
Neural Network $F^{1}(X)$ and later proven for Infinite Width by [Lee et al.,
2017, de G. Matthews et al., 2018]. The simplest form of this proof requires
the width of each layer of the FCN to go to infinity successively. [de G.
Matthews et al., 2018] could refine the proof by requiring all layers to go to
infinity simultaneously.

######  Theorem 3.1 (Neural Network GP).

If all the Weight dimensions $d_{L-1},d_{L-1},...,d_{1}$ other than the input
and the output dimensions of a Neural Network $F(X)^{L}$ successively go to
infinity with Weights initialization defined as above, then
$\operatorname{vec}(F(X)^{L})\sim$ GP(0, $\Lambda^{L-1}\otimes I_{d_{L}}$ ),
with

$\displaystyle\Lambda^{L}=\sigma^{2}_{w}\begin{pmatrix}\mathbb{E}\bigl{[}\sigma(u_{1})\sigma(u_{1})\bigr{]}&\mathbb{E}\bigl{[}\sigma(u_{1})\sigma(u_{2})\bigr{]}\dots&\mathbb{E}\bigl{[}\sigma(u_{1})\sigma(u_{n})\bigr{]}\\\
\vdots&\ddots&\vdots\\\
\mathbb{E}\bigl{[}\sigma(u_{n})\sigma(u_{1})\bigr{]}&\dots&\mathbb{E}\bigl{[}\sigma(u_{n})\sigma(u_{n})\bigr{]}\end{pmatrix}+\sigma_{b}^{2}$
$\displaystyle\text{ with }u\sim GP(0,\Lambda^{L-1})$ $\Lambda^{L}$ can be
written more compactly as the outer product of the random vector $u$
$\displaystyle\Lambda^{L}=\sigma^{2}_{w}\mathbb{E}\left[\sigma(u)\sigma(u^{T})\right]+\sigma_{b}^{2}$
and the base case concludes the theorem
$\displaystyle\Lambda^{0}=\frac{\sigma^{2}_{w}}{d_{0}}X^{T}X+\sigma_{b}^{2}$

The Integral $\mathbb{E}\left[\sigma(u)\sigma(u^{T})\right]$ with $u$ being a
multivariate Gaussian vector can be calculated in closed form for certain
activation functions like Relu. Han et al. [2022] present an overview with
closed form expressions for activation functions like Relu, Error function,
Leaky Relu, Exponential, RBF, and others. For a list of efficient
implementation see Novak et al. [2020]. The proof of Theorem 3.1 is given in
A.1.1.

###### Proof Sketch.

The proof is done by induction on the depth $l$ for $F^{l}(X)$. The Base Case
is established on the fact that the output of
$\operatorname{vec}(Y^{1})=\operatorname{vec}(F(X)^{1})$ is a weighted sum of
zero mean multivariate Gaussian. The induction step is based on the fact that
the output of $\operatorname{vec}(F^{l+1}(X))$ conditioned on
$\operatorname{vec}(G^{l}(X))$ is again a Zero Mean Multivariate Gaussian.
When the output of the previous layer goes to infinity, so
$d_{l}\rightarrow\infty$, we will have an infinite sum which will converge to
its mean by the Law of Large Numbers. ∎

####  3.1.2 Neural Tangent Kernel

######  Theorem 3.2 (NTK).

If all the Weight dimensions $d_{L-1},d_{L-1},...,d_{1}$ other than the input
and the output dimensions of a Neural Network $F(X)^{L}$ successively go to
infinity, the NTK as defined above has a closed form at initialization, namely
$\Theta^{L}\otimes I_{d_{l}}$ with

$\displaystyle\Theta^{L}=\Lambda^{L-1}+\left(\dot{\Lambda}^{L-1}\odot\Theta^{L-1}\right)$
$\displaystyle\Lambda^{L}=\sigma^{2}_{w}\mathbb{E}\left[\sigma(u)\sigma(u^{T})\right]+\sigma_{b}^{2}$
$\displaystyle\dot{\Lambda}^{L}=\sigma^{2}_{w}\mathbb{E}\left[\dot{\sigma}(u)\dot{\sigma}(u^{T})\right]+\sigma_{b}^{2}$
with $u\sim N(0,\Lambda^{L-1})$
$\displaystyle\Theta^{1}=\Lambda^{0}=\frac{\sigma^{2}_{w}}{d_{0}}X^{T}X+\sigma^{2}_{b}$

The proof of Theorem 3.2 is given in A.1.

###### Proof Sketch.

The proof is based on Induction on the Network Depth $l$ and uses the NNGP
derivations from above in addition with the Law of Large Numbers. ∎

The NTK Closed Form can be simplified by expanding the recursion and
reordering the terms.

######  Corollary 3.1 (Non-recursive NTK Formula [Equation 9 Arora et al.,
2019]).

$\displaystyle\dot{\Lambda}^{L+1}:=\mathds{1}_{n}$
$\displaystyle\Theta^{L}=\sum_{h=2}^{L+1}\left(\Lambda^{h-1}\odot(\dot{\Lambda}^{h}\odot\dot{\Lambda}^{h+1}\odot\cdots\odot\dot{\Lambda}^{L+1})\right)\otimes
I_{d_{L}}$

###  3.2 Graph Neural Networks

We define the Graph Neural Net recursively similar to the FCN previously. The
matrix A is commonly the Adjacency Matrix with $A\in\mathbb{R}^{n\times n}$,
but for the GP and NTK no assumptions about A are used.

######  Definition 3.2 (Graph Neural Network).

$\displaystyle F^{h}(X)$
$\displaystyle=\biggl{(}\frac{\sigma_{w}}{\sqrt{d_{h-1}}}W^{h}G^{h-1}(X)+\sigma_{b}B^{h}\biggr{)}A^{T}\in\mathbb{R}^{d_{h}\times
n}$ $\displaystyle\text{with }B^{h}$
$\displaystyle=b^{h}\otimes\mathbf{1}_{n}^{T}\text{ and
}b^{h}\in\mathbb{R}^{d_{h}}$ $\displaystyle G^{h}(X)$
$\displaystyle=\sigma(F^{h}(X))$ $\displaystyle G^{0}$
$\displaystyle=X\in\mathbb{R}^{d_{0}\times n}$

The Weights are initialized as $W^{h}\sim N(0,1)$ and $b^{h}\sim N(0,1)$
The final Network of depth $L$ is
$F^{L}(X)=\biggl{(}\frac{\sigma_{w}}{\sqrt{d_{L-1}}}W^{L}G^{L-1}(X)+\sigma_{b}B^{L}\biggr{)}A^{T}\in\mathbb{R}^{d_{L}\times
n}$

####  3.2.1 Graph Neural Network Gaussian Process

######  Theorem 3.3 (GNN Gaussian Process).

If all the Weight dimensions of the hidden layers $d_{L-1},d_{L-1},...,d_{1}$
of a GNN, $F(X)^{L}$ successively go to infinity, with Weights initialization
defined as above, then $\operatorname{vec}(F(X)^{L})\sim$ GP(0,
($A\Lambda^{L-1}A^{T})\otimes I_{d_{L}}$ ) with

$\displaystyle\Lambda^{L}$
$\displaystyle=\sigma^{2}_{w}\mathbb{E}\left[\sigma(u)\sigma(u^{T})\right]+\sigma_{b}^{2}$
with $u\sim N(0,A\Lambda^{L-1}A^{T})$ $\displaystyle\Lambda^{0}$
$\displaystyle=\frac{\sigma^{2}_{w}}{d_{0}}X^{T}X+\sigma^{2}_{b}$

###### Proof Sketch.

Applying a property of the Kronecker Product $(A\otimes B)(C\otimes
D)=(AC\otimes BD)$ and the bilinearity of the Covariance reduces the proof to
the Neural Network Gaussian Process (NNGP) proof (see 3.1). ∎

The proof of Theorem 3.3 is given in A.2.1. The expression
$\mathbb{E}\left[\sigma(u)\sigma(u^{T})\right]$ with $u$ being a multivariate
Gaussian vector can be calculated in closed form for certain activation
functions (see 3.1 for a detailed discussion).

####  3.2.2 Graph Neural Tangent Kernel

######  Theorem 3.4 (GNN NTK).

If all the Weight dimensions of the hidden layers $d_{L-1},d_{L-1},...,d_{1}$
of a GNN, $F(X)^{L}$ successively go to infinity, the Neural Tangent Kernel
has a closed form expression $\Theta^{L}\otimes I_{d_{L}}$, with

$\displaystyle\Theta^{L}=A\left(\Lambda^{L-1}+\left(\dot{\Lambda}^{L-1}\odot\Theta^{L-1}\right)A^{T}\right)\text{
with }$
$\displaystyle\Lambda^{L}=\sigma^{2}_{w}\mathbb{E}\left[\sigma(u)\sigma(u^{T})\right]+\sigma_{b}^{2}$
$\displaystyle\dot{\Lambda}^{L}=\sigma^{2}_{w}\mathbb{E}\left[\dot{\sigma}(u)\dot{\sigma}(u^{T})\right]+\sigma_{b}^{2}$
with $u\sim N(0,A\Lambda^{L-1}A^{T})$
$\displaystyle\Theta^{1}=\Lambda^{0}=\sigma^{2}_{w}X^{T}X+\sigma^{2}_{b}$

The proof of 3.4 is given in A.2.2.

###### Proof Sketch.

The NTK for Graph Neural Nets can be reduced to the standard NTK by using a
property of the Kronecker Product. ∎

The part $\Lambda^{L-1}+(\dot{\Lambda}^{L-1}\odot\Theta^{L-1})$ will be
positive definite [Jacot et al., 2018, A.4] or [Du et al., 2019a, Theorem
3.1]. For the GNTK the positive definiteness of the NTK will depend on $A$.
This could be one reason why using the Kipf & Welling Normalized Adjacency
Matrix which has eigenvalues between $[0,2]$ could confirm NTK theory (i.e.
loss is going to zero for increases width, weights are close to initialization
and empirical NTK stays close to initialization during training) whereas the
0-1 Adjacency Matrix (which generally will not be positive definite) is not
consistent with NTK theory (see 4.1). [Du et al., 2019a, Lemma 3.3] shows how
achieving zero training loss is related to the smallest eigenvalue of the
(empirical) NTK being positive. Nguyen et al. [2021] proves that the empirical
NTK of wide Neural Networks stays positive definite during training. Also note
that the expression reduces to the standart NTK formula for FCNs (see 3.1.2)
when replacing A with the Identity Matrix.

###  3.3 Skip-Concatenate Graph Neural Network

Skip-Concatenate Connections [Chen et al., 2019] consist of concatenating the
output of the non-linearity and pre-nonlinearity. The first layer is not
affected but starting from the second layer, $W^{h}$ with $h>1$ has dimensions
$W^{h}\in\mathbb{R}^{d_{l}\times 2d_{l-1}}$.

######  Definition 3.3 (Skip-Concatenate Graph Neural Network).

$\displaystyle F^{h}(X)$
$\displaystyle=\biggl{(}\frac{\sigma_{w}}{\sqrt{2d_{h-1}}}W^{h}G^{h-1}(X)+\sigma_{b}B^{h}\biggr{)}A^{T}\text{
for }h>1$ $\displaystyle F^{1}(X)$
$\displaystyle=\biggl{(}\frac{\sigma_{w}}{\sqrt{d_{1}}}W^{1}G^{0}(X)+\sigma_{b}B^{1}\biggr{)}A^{T}$
$\displaystyle\text{with }B^{h}$
$\displaystyle=b^{h}\otimes\mathbf{1}_{n}^{T}\text{ and
}b^{h}\in\mathbb{R}^{d_{h}}$ $\displaystyle G^{h}(X)$
$\displaystyle=\begin{pmatrix}\sigma(F^{h}(X))\\\ F^{h}(X)\end{pmatrix}\text{
so }G^{h}(X)\in\mathbb{R}^{2d_{l}\times n}$ $\displaystyle G^{0}$
$\displaystyle=X\in\mathbb{R}^{d_{0}\times n}$

The Weights are initialized as $W^{h}\sim N(0,1)$ and $b^{h}\sim N(0,1)$.
The final Network of depth $L$
$F^{L}(X)=\biggl{(}\frac{\sigma_{w}}{\sqrt{d_{L-1}}}W^{L}G^{L-1}(X)+\sigma_{b}B^{L}\biggr{)}A^{T}\in\mathbb{R}^{d_{L}\times
n}$.

####  3.3.1 Skip-Concatenate Graph Neural Network Gaussian Process

######  Theorem 3.5 (Skip-Concatenate GNN Gaussian Process).

If all the Weight dimensions of the hidden layers $d_{L-1},d_{L-1},...,d_{1}$
Skip-Concatenate GNN $F(X)^{L}$ successively go to infinity with Weights
initialization defined as above, then $\operatorname{vec}(F(X)^{L})\sim$ GP(0,
($A\Lambda^{L-1}A^{T})\otimes I_{d_{L}}$ ), with

$\displaystyle\Lambda^{L}$
$\displaystyle=\sigma^{2}_{w}\frac{1}{2}\left(\mathbb{E}\left[\sigma(u)\sigma(u^{T})\right]+A\Lambda^{L-1}A^{T}\right)+\sigma_{b}^{2}$
with $u\sim N(0,A\Lambda^{L-1}A^{T})$
$\displaystyle\Lambda^{0}=\frac{\sigma^{2}_{w}}{d_{0}}X^{T}X+\sigma^{2}_{b}$

The proof of Theorem 3.5 is given in A.3.1.

####  3.3.2 Skip-Concatenate Graph Neural Tangent Kernel

######  Theorem 3.6 (Skip-Concatenate GNN NTK).

Having Weight dimensions of the hidden layers $d_{L-1},d_{L-1},...,d_{1}$ of a
Skip-Concatenate GNN $F(X)^{L}$, approaching infinity with Weights
initialization defined as above, the NTK is $\Theta^{L}\otimes I_{d_{l}}$

$\displaystyle\Theta^{L}$
$\displaystyle=A\left(\Lambda^{L-1}+\left(\dot{\Lambda}^{L-1}\odot\Theta^{L-1}\right)\right)A^{T}$
$\displaystyle\Lambda^{L}$
$\displaystyle=\sigma^{2}_{w}\frac{1}{2}\left(\mathbb{E}\left[\sigma(u)\sigma(u^{T})\right]+A\Lambda^{L-1}A^{T}\right)+\sigma_{b}^{2}$
$\displaystyle\dot{\Lambda}^{L}$
$\displaystyle=\sigma^{2}_{w}\frac{1}{2}\left(\mathbb{E}\left[\dot{\sigma}(u)\dot{\sigma}(u^{T})\right]+1\right)+\sigma_{b}^{2}$
with $u\sim N(0,A\Lambda^{L-1}A^{T})$ $\displaystyle\Theta^{1}$
$\displaystyle=\Lambda^{0}=\sigma^{2}_{w}X^{T}X+\sigma^{2}_{b}$

The proof of Theorem 3.6 is given in A.3.2.

###  3.4 Graph Attention Neural Network

In this section we recap the Graph Attention Model (GAT) Model from Veličković
et al. [2018]. We will start by defining a single Attention Layer. We have
$X\in\mathbb{R}^{d_{0}\times n}$, $W\in\mathbb{R}^{d_{1}\times d_{0}}$ and
$A\in\mathbb{R}^{n\times n}$. A standard Graph Convolutional Layer without
Bias is $GCN(A,X)=\sigma(WXA^{T})$. A Graph Attention Layer is
$GAT(A,X)=\sigma_{2}(WX\alpha(c,A,WX)))$. The Attention Matrix commonly used
for the GAT is the standard 0-1 Attention Matrix $A_{0\text{-}1}$ with added
self loops, so $A=A_{0\text{-}1}+I$ and $\alpha(c,A,WX)$ is computed as
follows:

$\displaystyle H$ $\displaystyle:=XW\in\mathbb{R}^{n\times d_{out}}$
$\displaystyle M(H,c)_{ij}$ $\displaystyle=\langle
c,\operatorname{concat}(H_{\cdot i},H_{\cdot j})\rangle=c_{1}^{T}H_{\cdot
i}+c_{2}^{T}H_{\cdot j}$ with $c_{1}:=c_{[1,...,d_{out}]}$ and
$c_{2}:=c_{[d_{out},...,2d_{out}]}$ $\displaystyle\alpha(c,A,G)_{ij}$
$\displaystyle=\frac{\exp\left(\sigma_{1}\left(M(H,c)_{ij}\right)\right)}{\sum_{k\in
Neighbours(i)\mathop{\cup}\\{i\\}}\exp(\sigma_{1}\left(M(H,c)_{ik}\right)}$

The final step consists of computing the row wise $\operatorname{Softmax}$
only over neighbouring nodes of node $i$ and node $i$ itself. The Weight
vector $c\in\mathbb{R}^{2d_{0}}$ is called the Attention Weight vector and is
a parameter. $\sigma_{1}$ is an elementwise nonlinearity like the LeakyRelu.
The output of multiple Attention Layers can be stacked vertically before
serving as input for the consecutive layer. This is called Multiheaded
Attention. Instead of concatenating we can also average over the different
heads, so $\frac{1}{H}\sum_{h}GAT_{h}(A,X)$. The GAT model we are using to
derive the GP and NTK is a simplified version of the original GAT just
described. We are going to replace one of the $W$s by a copy $\tilde{W}$, so a
layer is $GAT(A,X)=\sigma_{2}(WX\alpha(c,A,\tilde{W}X))$. By doing so, we end
up with $M(H,c)_{ij}=c_{1}^{T}(\tilde{W}X)_{\cdot
i}+c_{2}^{T}(\tilde{W}X)_{\cdot j}=\tilde{c}_{1}^{T}X_{\cdot
i}+\tilde{c}_{2}^{T}X_{\cdot j}$ so we will just disregard $\tilde{W}$
alltogether. This simplification makes it possible to apply results from Yang
[2019] and Hron et al. [2020]. There seems to be no performance loss for our
simplified GAT model (which we will denote as GAT* (see table table 4) and 5.
We are going to replace $\operatorname{Softmax}$ by a elementwise nonlinearity
as there is currently no closed form expression for
$\mathbb{E}\left[\operatorname{Softmax}(u)\operatorname{Softmax}(u^{T})\right]$with
$u\sim N(0,\Lambda)$, ending up with the following simplified version
$\alpha(c,A,G)_{ij}=\sigma_{1}\left(A_{ij}(c_{1}^{T}X_{\cdot
i}+c_{2}^{T}X_{\cdot j})\right)$. Next we are going to give a recursive
definition of GAT*. The GAT* definition will not include a bias term as in
previous proofs but we will include the bias in the final version of the
Infinite Width Limit Formulas without proof (see Corollary 3.3).

######  Definition 3.4 (GAT*).

We have two elementwise nonlinearities $\sigma_{1}$ and $\sigma_{1}$ which are
polynomially bounded, (i.e. $\sigma(x)=c+m|x|\text{ for some
}c,m\in\mathbb{R}_{+}$) and $c,c_{1},c_{2}$ are defined as above, i.e
$c^{T}=\operatorname{concat}(c_{1}^{T},c_{2}^{T})$.

$\displaystyle G^{0}$ $\displaystyle=X\text{ with $X\in\mathbb{R}^{d_{0}\times
n}$}$ $\displaystyle L^{l,h}_{i,j}$
$\displaystyle=A_{ij}\frac{\sigma_{c}}{\sqrt{2{d_{l-1}}}}(c_{1}^{l,h^{T}}G^{l-1}_{\cdot
i}+c_{2}^{l,h^{T}}G^{l-1}_{\cdot j})$ with
$c_{1}^{l,h},c_{2}^{l,h}\in\mathbb{R}^{d_{l-1}}$ $\displaystyle F^{l,h}$
$\displaystyle=G^{l-1}\sigma_{1}(L^{l,h})$ $\displaystyle F^{l}$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{Hd_{l-1}}}W^{l}\left[F^{l,1},F^{l,2},\cdots,F^{l,H}\right]^{T}$
with $W\in\mathbb{R}^{d_{l}\times Hd_{l-1}}$. $F^{l}$ can also be written as
$\displaystyle F^{l}$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{Hd_{l-1}}}\sum_{h}^{H}W^{l,h}F^{l,h}$
$\displaystyle G^{l}$ $\displaystyle=\sigma_{2}(F^{l})$ and $W^{l},c^{l,h}\sim
N(0,1)$. The final Network of depth $l$ and heads $H$ is $\displaystyle F^{l}$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{Hd_{l-1}}}W^{l}\left[F^{l,1},F^{l,2},\cdots,F^{l,H}\right]^{T}$

####  3.4.1 Gaussian Process

######  Theorem 3.7 (GAT* GP).

If min$\\{H,d_{l-1}\\}\to\infty$ then $F^{l+1}$ (defined as above) is a
Gaussian Process with

$\displaystyle\operatorname{vec}(F^{l+1})\sim\text{GP}\left(0,\Lambda^{l}\otimes
I_{d_{l+1}}\right)$
$\displaystyle\Lambda^{l}:=\mathbb{E}\bigl{[}\sigma_{2}(u)\sigma_{2}(u^{T})\bigr{]}$
with u
$\sim\text{GP}\left(0,\operatorname{\mathrm{batchm}}\left(\sigma_{w}^{2}\Lambda^{l-1},\psi(\Lambda^{l-1})\right)\right)$
$\displaystyle\psi(\Lambda^{l}):=\mathbb{E}\bigl{[}\sigma_{1}(v)\sigma_{1}(v^{T})\bigr{]}$
with
$v\sim\text{GP}\left(0,\sigma_{c}^{2}\gamma_{A}(\Lambda^{l-1})\right)\text{and
}\gamma_{A}(\Omega):=J_{A}\begin{pmatrix}\Omega&\Omega\\\ \Omega&\Omega\\\
\end{pmatrix}J_{A}^{T}$ and
$J_{A}=\operatorname{diag}(\operatorname{vec}(A))\operatorname{concat}\left((\mathbf{1}_{n}\otimes
I_{n}),(I_{n}\otimes\mathbf{1}_{n})\right)$
$\displaystyle\Lambda^{0}=\frac{1}{d_{1}}X^{T}X$

The proof of Theorem 3.7 is given in A.4.1.

####  3.4.2 Neural Tangent Kernel

######  Theorem 3.8 (GAT* NTK).

The NTK (of a GAT* of depth $L$) is $\Theta^{L}\otimes I_{d_{l}}$, with

$\displaystyle\Lambda^{l}$
$\displaystyle:=\mathbb{E}\bigl{[}\sigma_{2}(v)\sigma_{2}(v^{T})\bigr{]}),\
\dot{\Lambda}^{l}:=\mathbb{E}\bigl{[}\dot{\sigma}_{2}(v)\dot{\sigma}_{2}(v^{T})\bigr{]}\text{
with $v\sim\text{GP}\left(0,\Lambda^{l-1}\right)$}$
$\displaystyle\dot{\psi}(\Lambda^{l})$
$\displaystyle:=\mathbb{E}\bigl{[}\dot{\sigma}_{1}(v)\dot{\sigma}_{1}(v^{T})\bigr{]}\text{
with $v\sim\text{GP}\left(0,\sigma_{c}^{2}\gamma_{A}(\Omega)\right)$}$
$\displaystyle\Theta^{1}$
$\displaystyle=\Lambda^{0}=\sigma_{w}^{2}\frac{1}{d_{1}}X^{T}X$
$\displaystyle\Theta^{L}$
$\displaystyle=\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\Lambda^{L-1},\psi(\Lambda^{L-1})\right]$
$\displaystyle+\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\Lambda^{L-1},\sigma_{c}^{2}\left(\gamma_{A}(\Lambda^{L-1})\odot\dot{\psi}(\Lambda^{L-1})\right)\right]$
$\displaystyle+\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\Lambda^{L-1},\sigma^{2}_{c}\left(\gamma_{A}(\Theta^{L-1}\odot\dot{\Lambda}^{L-1})\odot\dot{\psi}(\Lambda^{L-1})\right)\right]$
$\displaystyle+\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\left(\Theta^{L-1}\odot\dot{\Lambda}^{L-1}\right),\psi(\Lambda^{L-1})\right]$

The proof of Theorem 3.8 is given in A.4.2.

######  Corollary 3.2.

The NTK (of a GAT* of depth $L$ with $\sigma_{1}$ being the Identitiy Function
) is $\Theta^{L}\otimes I_{d_{l}}$, with

$\displaystyle\Lambda^{l}$
$\displaystyle:=\mathbb{E}\bigl{[}\sigma_{2}(v)\sigma_{2}(v^{T})\bigr{]}),\
\dot{\Lambda}^{l}:=\mathbb{E}\bigl{[}\dot{\sigma}_{2}(v)\dot{\sigma}_{2}(v^{T})\bigr{]}\text{
with $v\sim\text{GP}\left(0,\Lambda^{l-1}\right)$}$ $\displaystyle\Theta^{1}$
$\displaystyle=\Lambda^{0}=\sigma_{w}^{2}\frac{1}{d_{1}}X^{T}X$
$\displaystyle\Theta^{L}$
$\displaystyle=2\cdot\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\Lambda^{L-1},\sigma_{c}^{2}\gamma_{A}(\Lambda^{L-1})\right]+\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\Lambda^{L-1},\sigma^{2}_{c}\gamma_{A}\left(\Theta^{L-1}\odot\dot{\Lambda}^{L-1}\right)\right]$
$\displaystyle+\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\left(\Theta^{L-1}\odot\dot{\Lambda}^{L-1}\right),\sigma_{c}^{2}\gamma_{A}(\Lambda^{L-1})\right]$

######  Corollary 3.3 (GAT* NTK with bias (without proof)).

To include a bias term for the GAT NTK one can replace every occurrence of
$\sigma_{w}^{2}\Lambda^{l-1}$ by $\sigma_{w}^{2}\Lambda^{l-1}+\sigma_{b}^{2}$.

###  3.5 Infinite Width Graph Neural Networks for Graph Regression/
Classification

In the setting of inductive Learning, the task is to train a GNN on multiple
Graphs, e.g.:
${((A_{1},X_{1},y_{1}),(A_{2},X_{2},y_{2}),...,(A_{n},X_{n},y_{n})}$. Where
each triple consists of a Graph, its features and a label (like a class
assignment for classification). A two layer GNN with a final sum pooling
layer, can be written down as:
$F^{3}(A_{i},X_{i})_{h}=\sum_{h}F^{2}(A_{i},X_{i})_{\cdot h}$. So
$F^{3}(A_{i},X_{i})\in\mathbb{R}^{d_{3}}$ is a vector and
$F^{2}(A_{i},X_{i})\in\mathbb{R}^{d_{2}\times d_{3}}$ is defined like the GNN
for Node Regression/ Classification. The infinite GP in that case will be
$\operatorname{vec}(F^{3})\sim GP(0,\Sigma)$ with
$\Sigma_{ij}=\sum_{st}\left(A_{i}\Lambda^{1}A_{j}^{T}\right)_{st}$.

$\displaystyle\Lambda^{1}$
$\displaystyle=\sigma^{2}_{w}\mathbb{E}\left[\sigma(u)\sigma(u^{T})\right]+\sigma_{b}^{2}$
with $u\sim N(0,A_{i}\Lambda^{0}A_{j}^{T})$ $\displaystyle\Lambda^{0}$
$\displaystyle=\frac{\sigma^{2}_{w}}{d_{0}}X_{i}^{T}X_{j}+\sigma^{2}_{b}$

The GNTK extends similarly to the setting of Graph Induction. The NTK is
$\sum_{st}\Theta^{L}(i,j)_{st}$ with

$\displaystyle\Theta^{L}(i,j)=\sum_{st}\left(A_{i}\left(\Lambda^{L-1}+\left(\dot{\Lambda}^{L-1}\odot\Theta^{L-1}\right)\right)A_{j}^{T}\right)_{st}\text{
with }$
$\displaystyle\Lambda^{L}=\sigma^{2}_{w}\mathbb{E}\left[\sigma(u)\sigma(u^{T})\right]+\sigma_{b}^{2}$
$\displaystyle\dot{\Lambda}^{L}=\sigma^{2}_{w}\mathbb{E}\left[\dot{\sigma}(u)\dot{\sigma}(u^{T})\right]+\sigma_{b}^{2}$
with $u\sim N(0,A_{i}\Lambda^{L-1}A_{j}^{T})$
$\displaystyle\Theta^{1}=\Lambda^{0}=\sigma^{2}_{w}X_{i}^{T}X_{j}+\sigma^{2}_{b}$

$\Theta^{L}(i,j)$ is just the NTK for Node Classification/ Regression for
different datasamples $(A_{i},X_{i})$ and $(A_{j},X_{j})$. The proof can be
conducted using the same approach as in A.2.

##  4 Experiments

All models were evaluated on a variety of transductive Node Classification/
Regression Tasks. We are going to first summarize the datasets, proceed to the
simulations showing how GNNs are behaving for increasing width and finally
specify the models in detail and present the performance.

###  4.1 Simulations

In this section we empirically confirm the NTK findings, namely 1), 2), 3)
from 3.1. As a remainder 1) consists of showing the for increased width the
loss converges to zero, 2) consists of showing that the weight barley change
for increased width and 3) consists of showing that the NTK is close to its’
initialization during training. We use the KarateClub dataset [Zachary, 1977]
with 34 nodes of which we used 27 for training with four classes. We now show
for FCNs, GNNs, Skip-GNNs and the GAT that 1), 2) and 3) are valid (see Fig.
1). The were initalized randomly as defined in 3.1,3.2, 3.3 and 3.4. For the
GNN and Skip-GNN we use the Kipf & Welling Normlized Adjacency Matrix and for
the GAT the 0-1 Adjacency with added self loops. Finally using a GNN with the
0-1 Adjacency with self loops is not consistent with NTK theory. Figure 2
shows cleary that with increased width neither the weights are changing less
nor does the empirical NTK stay close to its initialization. For a detailed
discussion on why see 3.4.

| Wiki | Cora | Citeseer
---|---|---|---
GCN-8 | 0.09, 0.025 | 0,14, 0.22 | 0.17, 0.16
GCN-32 | 0.07, 0.32 | 0.14, 0.25 | 0.18, 0.2
GCN-128 | 0.07, 0.45 | 0.15, 0.13 | 0.17, 0.16
GCN-512 | 0.08, 0.49 | 0,16, 0.1 | 0.17, 0.16

Table 1: Overfitting with Gradient Descent, comma-seperated loss & accuracy

| Wiki | Cora | Citeseer
---|---|---|---
GCN-8 | 0.1, 0.15 | 0, 0.75 | 0.017, 0.57
GCN-32 | 0.06, 0.08 | 0, 0.73 | 0, 0.6
GCN-128 | 0.07, 0.45 | 0.15, 0.13 | 0.17, 0.16
GCN-512 | 0.01, 0.73 | 0, 0.76 | 0, 0.625

Table 2: Overfitting with Adam Optimizer, comma-seperated loss & accuracy

Table 2 display the training loss and accuracy comma-seperated for a two layer
GNN with increasing width for different datasets. In table 2 the GNN was
trained with Gradient Descent for with a learning rate of 0.001 and in table 2
Adam Optimizer with the same learning rate. For a FCN we would expect a very
wide Neural Net to achieve zero training loss and not overfit Arora et al.
[2019]. For GNNs we can observe that Gradient Descent fails completely
although the loss in each case is close to zero. For the adam optimizer
increased width improves accuracy with an outlier when we set the width to
128. The loss is already near zero for setting the width to 8. GNNs seem to be
very sensitive to the optimizer, step size and width more than would be
expected for FCNs.

Figure 1: First row corresponds to a two layer FCN, second row to a two layer
GNN with the Kipf & Normalized Adjcacency Matrix, third row is the Skip-GNN
with the same Adjacency Matrix and forth row a GAT with the number of Heads
equal to the Width and the Attention Heads are summed over. All models are
trained with learning rate of 0.001 and Gradient Descent. For each row the
left figures shows training loss for different widths, the middle figure shows
weight change (difference to weights at initialization) during training and
the right figures show the difference of the empirical NTK compared to its
initialization during training. These simulations confirm that for increased
width during training we can observe 1) the training loss approaches zero 2)
the weights of the GNN stay close to its initialization and 3) the empirical
NTK stays close to its initialization during training.

Figure 2: A GNN trained with the 0-1 Adjacency with self loops for a two layer
GNN with a learning rate of 0.001 is not consistent with 1), 2) and 3).

###  4.2 Datasets, Models & Evaluation

#### Datasets

The following section contains a short description of each dataset:

  1. 1.

Classification: The citation network dataset “Cora”, “CiteSeer” and “PubMed”
from Yang et al. [2016] and “Wiki” from Yang et al. [2020] are Node
Classification Tasks. The performance measure used is Accuracy.

  2. 2.

Regression: “Chameleon”, “Squirrel” and “Crocodile” are Node Regressions Tasks
which are part of the Wikipedia networks Dataset [Rozemberczki et al., 2021].
Nodes represent web pages and edges represent hyperlinks between them. Node
features represent several informative nouns in the Wikipedia pages. The task
is to predict the average daily traffic of the web page. The performance
measure used is the $R^{2}$-Score.

Dataset | Task | Nodes | Edges | Features | Classes | Train/Val/Test Ratio
---|---|---|---|---|---|---
Cora | Classification | 2,708 | 10,556 | 1,433 | 7 | 0.05/0.18/0.37
Citeseer | Classification | 3,327 | 9,104 | 3,703 | 6 | 0.04/0.15/0.30
PubMed | Classification | 19,717 | 88,648 | 500 | 3 | 0.003/0.025/0.051
Wiki | Classification | 2,405 | 17,981 | 4,973 | 17 | 0.60/0.20/0.20
Chameleon | Regression | 2,277 | 62,742 | 3,132 | Regression | 0.48/0.32/0.20
Squirrel | Regression | 5,201 | 396,706 | 3,148 | Regression | 0.48/0.32/0.20
Crocodile | Regression | 11,631 | 341,546 | 13,183 | Regression | 0.48/0.32/0.20
Table 3: Dataset summary

The datasets splits are exactly modelled after [Kipf and Welling, 2017,
Veličković et al., 2018]. Note that the train/val/test split is fixed and not
randomly sampled for each experiment. Not all graphs have labels for all nodes
(e.g Cora).

### Models

Now we summarize the hyperparameters for the Models:

#### Neural Nets

The FCN, GNN, S-GNN, GAT and GAT* are all Neural Networks. All but the S-GNN
have two layers, as added depth did not increase the performance of the
models. The Skip-GNN has three layers as the Skip-Connections only take effect
after a minimum of three layers. The FCN is a Neural Net just trained on the
Node features, i.e. a GNN with $I$ as the Adjacency Matrix. The models were
trained for 300 epochs without early stopping. The features were normalized
before training. All models used the Adam Optimizer with weight decay of
0.005. The GNN, S-GNN used a learning rate of 0.01 whereas the GAT and GAT*
used a learning of 0.005. Dropout of 0.5 was applied to the output of every
layer during training. In the case of GAT and GAT* dropout of 0.5 was also
applied to the Attention Adjacency Matrix. The Neural Nets were trained with
Crossentropy Loss for Classification and Mean-Squared Error for Regression.
The hyperparameters are borrowed from Kipf and Welling [2017], Veličković et
al. [2018] where they were determined on the validation sets. Contrary to the
mentioned papers we did no use early stopping. Regression was done similar as
above but without feature normalization and for FCN, GNN, Skip-GCN with a
learning rate of 0.1 without weight decay but with batch normalization after
each layer except the last layer and for GAT and GAT* with a Learning Rate of
0.01 and no Batch Normalization. The FCN for Regression had Sigmoid
nonlinearity instead of Relu, as it improved the performance from a negative
$R^{2}$-Score to a positive one.

#### Kernels and Gaussian Processes

The Kernels and GP were trained without feature normalization. The GP and
Kernel were fitted using the training set. We used the validation set to
perform a grid search for values between 0.001 and 10 to find the best
regularization parameters. Regularization for GP (sometimes referred to as
Noise Parameter) results in performing Kernel Ridge Regression which results
in adding $\lambda I$ to the Kernel/GP Covariance Matrix before inverting them
(see e.g. Rasmussen and Williams [2006] for connections between GP and
Kernels). $\sigma_{w}^{2}$ and $\sigma_{c}^{2}$ are set to one and
$\sigma_{b}^{2}$ is set to zeros for all Classification tasks. Regression was
done with $\sigma_{b}^{2}=0.1$ similar to the setup in Niu et al. [2023]. We
conduct additional experiments (see 4.5) to investigate the role of
$\sigma_{b}^{2}$ as it seems to have a crucial role in the performance for the
Regression tasks. In the case of GAT*-GP and GAT*-NTK the nonlinearity for the
Attention Matrix (e.g $\sigma_{1}$) was chosen to be the Identity Function.
$\sigma_{2}$ was the LeakyRelu with a slope of 0.2 for the negative slope. In
6 we compared different nonlinearities for the GAT*GP and GAT*NTK.
GAT*GP/GAT*NTK-LINEAR have no nonlinearity. GAT*GP/GAT*NTK-2 have two
nonlinearities $\sigma_{2}$ was the LeakyRelu as above and $\sigma_{1}$ is the
Error-function333https://en.wikipedia.org/wiki/Error_function. We can see that
adding two nonlinearities can improve the accuracy by 1%-2%. GAT*GP and
GAT*NTK in general performed very bad for Regression tasks with a negative
$R^{2}$-Squared Score.

### Evaluation

Due to the large memory and time requirements for GAT*GP and GAT*NTK we
“sparsified” all Graphs denoted with # by removing 90% of their edges using a
technique called Effective Resistence [Spielman and Srivastava, 2011]. For
details see 4.4). The experiments clearly show that the NTK and GP are
competitive with the Neural Net Counterpart even when the Neural Network is
not a Vanilla Neural Net trained using the MSE Loss with SGD and extensions
like Dropout turned of. In the case of FCNs it was shown that their NTK
counterpart had a significant performance gap of between 6% - 10% when
compared to their vanilla counterparts [Arora et al., 2019], let alone having
things like Dropout, Batch Normalization and so on. Batch Normalization can be
incorporated into the GP/NTK framework Yang [2020]. Most models seem to be
performing very close within each others performance without any one standing
out. The GNTK appears to be a strong choice, slightly outperforming the GNNGP
in Regression. In all cases a GP/NTK is able to achieve matching or even
better performance than their Neural Net Counterparts. The GAT Variants all
seem to do very poorly for Regression tasks with even negative $R^{2}$-Scores
for the GP & NTK counterparts. Overall using the Kernels and GP is prefereble
because it does not require tuning hyperparameters and the GNN are very
sensitive for hyperparameters (e.g. number of hidden nodes , see 2).

| Cora | Citeseer | Pubmed | Wiki
---|---|---|---|---
FCN | 0.61 | 0.59 | 0.73 | 0.72
GNN | 0.81 | 0.71 | 0.79 | 0.66
Skip-GNN | 0.81 | 0.71 | 0.79 | 0.75
GAT | 0.82 | 0.71 | 0.77 | 0.66
GAT* | 0.82 | 0.70 | 0.77 | 0.65
NNGP | 0.60 | 0.62 | 0.73 | 0.81
NTK | 0.58 | 0.62 | 0.72 | 0.81
GNNGP | 0.83 | 0.71 | 0.80 | 0.78
GNTK | 0.83 | 0.72 | 0.79 | 0.79
SGNNGP | 0.83 | 0.71 | 0.80 | 0.78
SGNTK | 0.80 | 0.72 | 0.79 | 0.78
GAT*GP | 0.79 | 0.71 | 0.73# | 0.78
GAT*NTK | 0.79 | 0.71 | 0.73# | 0.77

Table 4: Classification

| Chameleon | Squirrel | Crocodile
---|---|---|---
FCN | 0.52 | 0.39 | 0.75
GNN | 0.48 | 0.35 | 0.64
Skip-GNN | 0.38 | 0.31 | 0.58
GAT | 0.43 | 0.30 | 0.66
GAT* | 0.54 | 0.30 | 0.65
NNGP | 0.63 | 0.45 | 0.79
NTK | 0.67 | 0.48 | 0.80
GNNGP | 0.64 | 0.48 | 0.78
GNTK | 0.68 | 0.51 | 0.79
SGNNGP | 0.59 | 0.43 | 0.64
SGNTK | 0.57 | 0.46 | 0.55
GAT*GP | -12.14 | -8.6# | 16.94#
GAT*NTK | -8.75 | -8.2# | -17.69#

Table 5: Regression

| Cora | Citeseer | Wiki
---|---|---|---
GAT*GP-LINEAR | 0.79 | 0.72 | 0.74
GAT*NTK-LINEAR | 0.79 | 0.72 | 0.74
GAT*GP | 0.79 | 0.71 | 0.78
GAT*NTK | 0.79 | 0.71 | 0.77
GAT*GP-2 | 0.79 | 0.71 | 0.78
GAT*NTK-2 | 0.8 | 0.71 | 0.80
Table 6: Different GAT models with different nonlinearities.

###  4.3 Code & Environment

All Experiments were conducted on a AMD Ryzen 7 3800X 8-Core Processor (with
hyperthreading, so 16vCPUs) with 32GB Ram. Experiments with † were conducted
on an Intel(R) Xeon(R) Gold 6148 CPU @ 2.40GHz with 20 Cores (without
hyperthreading, so 20vCPUs) with 362GB of Ram. All Experiments were conducted
using the CPU. The measurements for GAT*GP and GAT*NTK Pubmed, Squirrel and
Crocodile are the datasets with 90% of edges removed via Effective Resistance.
The GAT*GP and GAT*NTK code is highly optimized, making use of the Python
Intel MKL Library which has an implementation of parallel Sparse Matrix
mulitplication whereas Pytorch and Scipy perform Sparse Matrix operations on
one core only. In depth explanation and code is available at
https://github.com/yCobanoglu/infinite-width-gnns.

| Cora/Citeseer/Wiki | Pubmed | Chameleon | Squirrel | Crocodile
---|---|---|---|---|---
Neural Nets | <1min | <2min | <2min | <3min | <3min
| NNGP,NTK,
---
GNNGP, GNTK
SGNN, SGNTK
<2s | 2min | 1.15min | <3min | <3min
| GAT*GP,
---
GAT*NTK
| 10min, 15min, 1h
---
<16GB Ram
| 25h,
---
60GB Ram†
| 4h,
---
32GB Ram†
| 1h,
---
32GB Ram†
| 1h,
---
32GB Ram†

###  4.4 Effective Resistance Spectral Graph Sparsification

Recall that the GAT*GP and GAT*NTK require calculating the expression:

$\displaystyle\psi(\Lambda^{l}):=\mathbb{E}\bigl{[}\sigma_{1}(v)\sigma_{1}(v^{T})\bigr{]}\text{
with
$v\sim\text{GP}\left(0,\sigma_{c}^{2}\gamma_{A}(\Lambda^{l-1})\right)\text{and
}\gamma_{A}(\Omega):=J_{A}\begin{pmatrix}\Omega&\Omega\\\ \Omega&\Omega\\\
\end{pmatrix}J_{A}^{T}$}$

and
$J_{A}=\operatorname{diag}(\operatorname{vec}(A))\operatorname{concat}\left((\mathbf{1}_{n}\otimes
I_{n}),(I_{n}\otimes\mathbf{1}_{n})\right)$ which comes from 3.7.
The expression
$\gamma_{A}(\Omega):=J_{A}\begin{pmatrix}\Lambda^{l}&\Lambda^{l}\\\
\Lambda^{l}&\Lambda^{l}\end{pmatrix}J_{A}^{T}$ will be
$\in\mathbb{R}^{n^{2}\times n^{2}}$ where $A\in\mathbb{R}^{n\times n}$. For
Pubmed this will be a sparse $400,000\times 400,000$ matrix. Calculating
$\psi(\Lambda^{l}):=\mathbb{E}\bigl{[}\sigma_{1}(v)\sigma_{1}(v^{T})\bigr{]}$
will again need multiple operations on the same matrix. Note that in the case
of $\sigma_{1}$ being the Identitiy Function
$\psi(\Lambda^{l})=\gamma_{A}(\Omega)$. To still incorporate $\sigma_{1}$ in
an efficient manner recall the definition of a two layer GAT Model:

$\displaystyle G^{1}=W^{1}X$ $\displaystyle
F^{2}=\sigma_{2}(G^{1}\sigma_{1}(A\odot C))\text{ with
}C_{ij}=c_{1}^{T}G^{1}_{\dot{i}}+c_{2}^{T}G^{1}_{\dot{j}}$

with A being the 0-1 Adjacency and with added self loops and $\sigma_{1}(0)=0$
(.e.g. Relu, Sigmoid), results in
$F^{2}=\sigma_{2}(G^{1}(A\odot\sigma_{1}(C)))$. The corresponding Kernel would
be

$\displaystyle\psi(\Lambda^{l}):=\gamma_{A}\biggl{(}\mathbb{E}\bigl{[}\sigma_{1}(v)\sigma_{1}(v^{T})\bigr{]}\biggr{)}\text{
with $v\sim\text{GP}\left(0,\sigma_{c}^{2}\Lambda^{l-1}\right)$}$

This way we $\mathbb{E}\bigl{[}\sigma_{1}(v)\sigma_{1}(v^{T})\bigr{]}$ will
now be much more efficient as the resulting matrix will be
$\in\mathbb{R}^{n\times n}$ instead $\in\mathbb{R}^{n^{2}\times n^{2}}$.
Calculating $\gamma_{A}(\Omega)$ for large Graphs/Matrices is still difficult
and that is why we used Spectral Graph Sparsification Methods, namely
Effective Resistance on PubMed, Squirrel and Crocodile for GAT*GP and GAT*NTK.
EffectiveResistence [Spielman and Srivastava, 2011] was successfully applied
for GNNs and GATs and one could show that it is possible to remove as much as
90% of the edges of a Graph without sacrifice much performance and improving
memory and runtime [Srinivasa et al., 2020]. Effective Resistance takes an
unweighted 0-1 Adjacency Matrix and returns a sparsified (i.e. Graph with less
edges) weighted Adjacency Matrix such that the Laplacians of these Adjacency
Matrices are close. In our use case we apply Effective Resistance on the 0-1
Adjacency Matrix and then replace each edge weight with the value one so it is
again a 0-1 Adjacency Matrix. This way we could improve speed especially for
Pubmed considering it took around 30 hours and 60GB Ram despite the fact that
90% of the Edges had been removed. The following tables demonstrate Effective
Resistance on GNNGP and GNTK Models. We run experiments with 50% and 90 % of
the Edges removed. There is a performance penalty for removing edges, but the
difference in Cora, Citeseer, and Pubmed between removing 90% or 50% is
negligible.

| Cora | Citeseer | Pubmed | Wiki | Chameleon | Squirrel | Crocodile
---|---|---|---|---|---|---|---
GNNGP | 0.83 | 0.71 | 0.80 | 0.78 | 0.64 | 0.48 | 0.78
GNTK | 0.83 | 0.72 | 0.79 | 0.79 | 0.68 | 0.51 | 0.79
GNNGP 0.5 | 0.77 | 0.66 | 0.75 | 0.70 | 0.52 | 0.4 | 0.45
GNTK 0.5 | 0.76 | 0.67 | 0.75 | 0.71 | 0.52 | 0.46 | 0.15
GNNGP 0.9 | 0.77 | 0.69 | 0.77 | 0.40 | 0.45 | 0.28 | 0.42
GNTK 0.9 | 0.78 | 0.69 | 0.77 | 0.40 | 0.45 | 0.27 | 0.38
Table 7: Performane with Graph Spectral Sparsification known as Effective
Resistance

###  4.5 Role of bias $\sigma_{b}^{2}$ for Regression

For the Regression experiments with GPs and Kernels we set
$\sigma_{b}^{2}=0.1$ and for the GNNs for Regression we added Batch
Normalization so we could reproduce the results from Niu et al. [2023]. We are
going to explore the Performance for having 1) Having no bias parameter for
the GNNs 2) Setting $\sigma_{b}^{2}=0$ for the GP and NTK with the Sigmoid
nonlinearity 3) Setting $\sigma_{b}^{2}=0$ for the GP and NTK with the Relu
nonlinearity 4) $\sigma_{b}^{2}=0$ for GNNGP and GNTK with the Relu
nonlinearity. For Classification trying different $\sigma_{b}^{2}$ or having
the models without bias term did not have the same effect as for Regression
(i.e. no large decrease in performance). For Regression, the bias term for the
Neural Nets as well as the $\sigma_{b}^{2}$ seems to play a crucial role and
by leaving it out the performance worsens in practically every example
(including negative $R^{2}$-Scores).

| Chameleon | Squirrel | Crocodile
---|---|---|---
FCN (No Bias) | 0.54 | 0.38 | 0.75
GNN (No Bias) | -0.13 | -1.51 | 0.17
NNGP (Sigmoid) ($\sigma_{b}=0$) | 0.46 | 0.40 | 0.75
NTK (Sigmoid) ($\sigma_{b}=0$) | 0.46 | 0.40 | 0.75
NNGP (Relu)($\sigma_{b}=0$) | -1.59 | -7.917 | 0.726
NTK (Relu) ($\sigma_{b}=0$) | -1.481 | -7.314 | 0.725
GNNGP ($\sigma_{b}=0$) | 0.175 | -0.817 | 0.299
GNN ($\sigma_{b}=0$) | 0.202 | -0.757 | 0.34
Table 8: Role of bias $\sigma_{b}^{2}$ for Regression

##  5 Conclusion

We derived new Kernel and Gaussian Processes by using their connection to
infinite Width Neural Networks. We could successfully show that their
performance is competitive with recent Graph Neural Networks architectures
makes them a valid alternative for Machine Learning tasks on Graph structured
data. Gaussian Processes and Kernels are easy to implement and allow for
uncertainty estimation. Unlike Graph Neural Networks, which are highly
sensitive to various hyperparameter settings, GP and NTK counterparts
practically require no hyperparameters. This makes them valuable for
establishing robust performance benchmarks across different tasks. We hope for
this work to serve as a source of inspiration for the development of
innovative Neural Network architectures and Kernel designs.

##  Appendix A Appendix

###  A.1 Fully-connected Deep Nets

We copied the definitions of the Graph Neural Network from the main section.

See 3.1

#### Derivatives

The derivatives will be necessary for the closed form of the NTK.
The derivative of $F(\theta,X)$ with respect $W^{l}$ and $b^{l}$ can be
derived using the chain rule.

$\displaystyle\frac{\partial\operatorname{vec}(F(\theta,X))}{\partial\operatorname{vec}(W^{l})}=\frac{\partial\operatorname{vec}(F^{L})}{\partial\operatorname{vec}(G^{L-1})}\frac{\partial\operatorname{vec}(G^{L-1})}{\partial\operatorname{vec}(F^{L-1)}}\cdots\frac{\partial\operatorname{vec}(F^{l+1})}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(W^{l})}$

Using

$\displaystyle\frac{\partial\operatorname{vec}(F^{h})}{\partial\operatorname{vec}(G^{h-1})}$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{h-1}}}(I_{n}\otimes W^{h})$
$\displaystyle\Sigma^{h}:=\frac{\partial\operatorname{vec}(G^{h})}{\partial\operatorname{vec}(F^{h})}$
$\displaystyle=\operatorname{diag}(\operatorname{vec}(\dot{\sigma}(F^{h}))$
$\displaystyle\frac{\partial\operatorname{vec}(F^{h})}{\partial\operatorname{vec}(W^{h})}$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{h-1}}}(G^{h-1^{T}}\otimes
I_{d_{h}})$ $\displaystyle\frac{\partial\operatorname{vec}(F^{h})}{\partial
b^{h}}$ $\displaystyle=\sigma_{b}(\mathbf{1}_{n}\otimes I_{d_{h}})$

Combining the derivatives with the chain rule the final expression is:

$\displaystyle\frac{\partial\operatorname{vec}(F(X))}{\partial\operatorname{vec}(W^{l})}$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{h-1}}}(I_{n}\otimes
W^{L})\Sigma^{L-1}\cdots\frac{\sigma_{w}}{\sqrt{d_{h-1}}}(I_{n}\otimes
W^{l})\Sigma^{l}\frac{\sigma_{w}}{\sqrt{d_{h-1}}}(G^{l-1^{T}}\otimes
I_{d_{h}})$ and similarly
$\displaystyle\frac{\partial\operatorname{vec}(F(X))}{\partial b^{l}}$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{h-1}}}(I_{n}\otimes
W^{L})\Sigma^{L-1}\cdots\frac{\sigma_{w}}{\sqrt{d_{h-1}}}(I_{n}\otimes
W^{l})\Sigma^{l}\sigma_{b}(\mathbf{1}_{n}\otimes I_{d_{h}})$

####  A.1.1 Gaussian Process (Theorem 3.1)

See 3.1

###### Proof.

The matrix $\mathrm{Cov}(\text{Y})_{IJ}\in\mathbb{R}^{d_{1}\times d_{1}}$ will
correspond to the matrix $\mathrm{Cov}(\text{Y}_{\cdot i},\text{Y}_{\cdot
j})$. And similarly $\mathbb{E}(Y)_{I}\in\mathbb{R}^{d_{1}}$ will be
$\mathbb{E}(Y_{\cdot i})$. We will first derive the $\mathbb{E}(x)$ and
$\mathrm{Cov}(x,x^{\prime})$ with respect to a single, respectively two
datasamples and then derive the Expectation and Covariance for the whole
dataset.
Base Case for single datasample, respectively two datasamples:

$\displaystyle\mathbb{E}(\text{Y})_{I}$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{0}}}W^{1}X_{\cdot
i}+\sigma_{b}b^{1}=0$ $\displaystyle\mathrm{Cov}(\text{Y})_{IJ}$
$\displaystyle=\mathbb{E}\biggl{[}\left(\frac{\sigma_{w}}{\sqrt{d_{0}}}W^{1}X_{\cdot
i}+\sigma_{b}b^{1}\right)\left(\frac{\sigma_{w}}{\sqrt{d_{0}}}W^{1}X_{\cdot
j}+\sigma_{b}b^{1}\right)^{T}\biggl{]}$
$\displaystyle=\frac{\sigma_{w}^{2}}{d_{0}}\mathbb{E}\biggl{[}W^{1}X_{\cdot
i}X_{\cdot
j}^{T}W^{1^{T}}\biggr{]}+\sigma^{2}_{b}\mathbb{E}\biggl{[}b^{1}b^{1^{T}}\biggr{]}$
$\displaystyle=\frac{\sigma_{w}^{2}}{d_{0}}I_{d_{1}}\left<X_{\cdot i},X_{\cdot
j}\right>+I_{d_{1}}\sigma^{2}_{b}$
$\displaystyle=I_{d_{1}}\left(\frac{\sigma_{w}^{2}}{d_{0}}\left<X_{\cdot
i},X_{\cdot j}\right>+\sigma^{2}_{b}\right)$ Base case for the complete
dataset: $\displaystyle\mathbb{E}(\operatorname{vec}(Y^{1}))$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{0}}}\operatorname{vec}(W^{1}X)+\sigma_{b}\operatorname{vec}(B^{1})=0$
$\displaystyle\mathrm{Cov}(\operatorname{vec}(Y^{1}))$
$\displaystyle=\mathbb{E}\biggl{[}\biggl{(}\frac{\sigma_{w}}{\sqrt{d_{0}}}\operatorname{vec}(W^{1}X)+\sigma_{b}\operatorname{vec}(B^{1}\biggr{)}\biggl{(}\frac{\sigma_{w}}{\sqrt{d_{0}}}\operatorname{vec}(W^{1}X)+\sigma_{b}\operatorname{vec}(B^{1}))^{T}\biggr{)}\biggr{]}$
$\displaystyle=\frac{\sigma_{w}^{2}}{d_{0}}\mathbb{E}\biggl{[}\operatorname{vec}(W^{1}X)\operatorname{vec}(W^{1}X)^{T}\biggr{]}+\sigma^{2}_{b}\mathbb{E}\biggl{[}\operatorname{vec}(B^{1})\operatorname{vec}(B^{1})^{T}\biggr{]}$
$\displaystyle=\frac{\sigma_{w}^{2}}{d_{0}}\mathbb{E}\biggl{[}(I_{n}\otimes
W^{1})\operatorname{vec}(X)\operatorname{vec}(X)^{T}(I_{n}\otimes
W^{1^{T}})\biggr{]}+\sigma^{2}_{b}(\mathds{1}_{n}\otimes I_{d_{1}})$
$\displaystyle=\biggl{(}\frac{\sigma^{2}_{w}}{d_{0}}X^{T}X+\sigma^{2}_{b}\biggr{)}\otimes
I_{d_{1}}$ The induction step for one, respectively two datasamples.
$\displaystyle\mathbb{E}(\text{Y}^{l+1})_{I}$ $\displaystyle=0$
$\displaystyle\mathrm{Cov}(\text{Y}^{l+1})_{IJ}$
$\displaystyle=\mathbb{E}\bigg{[}\biggl{(}\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l+1}G^{l}_{\cdot
i})+\sigma_{b}b^{l+1}\biggr{)}\biggl{(}\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l+1}\sigma(Y^{l}_{\cdot
i})+\sigma_{b}b^{l+1})\biggr{)}^{T}\biggr{]}$
$\displaystyle=\frac{\sigma_{w}^{2}}{d_{l}}\mathbb{E}\biggr{[}W^{l+1}\sigma(Y^{l}_{\cdot
i})\sigma(Y^{l}_{\cdot j})^{T}W^{l+1^{T}}\biggr{]}+\sigma^{2}_{b}I_{d_{l}}$
$\displaystyle\frac{\sigma_{w}^{2}}{d_{l}}\mathbb{E}(W^{l+1}$
$\displaystyle\sigma(Y^{l}_{\cdot i})\sigma(Y^{l}_{\cdot
j}W^{l+1^{T}})^{T})_{uv}=\frac{\sigma^{2}_{w}}{d_{l}}\operatorname{tr}(\sigma(Y^{l}_{\cdot
i})\sigma(Y^{l}_{\cdot j})^{T})\delta_{uv}$ (2.1)
$\displaystyle\delta_{uv}\frac{\sigma^{2}_{w}}{d_{l}}\sum_{n=1}^{d_{l}}\sigma(Y^{l}_{nj})\sigma(Y^{l}_{ni})\overset{\overset{P}{d_{l}\rightarrow\infty}}{\longrightarrow}\sigma^{2}_{w}\delta_{uv}\underset{s,t\sim
N(0,\biggl{(}\begin{smallmatrix}\Lambda^{l-1}_{ii}&\Lambda^{l-1}_{ij}\\\
\Lambda^{l-1}_{ji}&\Lambda^{l-1}_{jj}\end{smallmatrix}\biggr{)})}{\mathbb{E}}\bigl{[}\sigma(s)\sigma(t)\bigr{]}$
(2.2)

In (2.1) we have used the quadratic form for random variables. In (2.2) we
have used the fact that $Y^{l}_{ni}$ and $Y^{l}_{mi}$ with $n\neq m$ are
i.i.d. random variables. That also becomes apparent by observing that
$\mathrm{Cov}(Y^{l}_{\cdot i},Y^{l}_{\cdot j}$) is diagonal.
And finally for the whole dataset:

$\displaystyle\mathbb{E}(\operatorname{vec}(Y^{l+1}))$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{l}}}\operatorname{vec}(W^{l+1}G^{l})+\sigma_{b}\operatorname{vec}(B^{l+1})=0$
$\displaystyle\mathrm{Cov}(\operatorname{vec}(Y^{l+1}))$
$\displaystyle=\mathbb{E}\biggr{[}\biggl{(}\frac{\sigma_{w}}{\sqrt{d_{l}}}\operatorname{vec}(W^{l+1}G^{l})+\sigma_{b}\operatorname{vec}(B^{l+1}\biggl{)}\biggr{(}\frac{\sigma_{w}}{\sqrt{d_{l}}}\operatorname{vec}(W^{l+1}G^{l})+\sigma_{b}\operatorname{vec}(B^{l+1})^{T}\biggl{)}\biggr{]}$
$\displaystyle=\frac{\sigma_{w}^{2}}{d_{l}}\mathbb{E}\bigl{[}\operatorname{vec}(W^{l+1}G^{l})\operatorname{vec}(G^{l^{T}}W^{l+1^{T}}\bigl{]}+\sigma^{2}_{b}(\mathds{1}_{n}\otimes
I_{d_{l}})$
$\displaystyle=\frac{\sigma_{w}^{2}}{d_{l}}\mathbb{E}\bigl{[}(I_{n}\otimes
W^{l+1})\operatorname{vec}(G^{l})\operatorname{vec}(G^{l})^{T}(I_{n}\otimes
W^{l+1^{T}})\bigr{]}+\sigma^{2}_{b}(\mathds{1}_{n}\otimes I_{d_{l+1}})$ (2.2)
$\displaystyle\frac{\sigma_{w}^{2}}{d_{l}}\mathbb{E}\bigl{[}(I_{n}\otimes
W^{l+1})\operatorname{vec}(G^{l})\operatorname{vec}(G^{l})^{T}(I_{n}\otimes
W^{l+1^{T}})\bigr{]}+\sigma^{2}_{b}(\mathds{1}_{n}\otimes I_{d_{l}})$
$\displaystyle=\left(\sigma_{w}^{2}\begin{pmatrix}\mathbb{E}\bigl{[}\sigma(u_{1})\sigma(u_{1})\bigr{]}&\mathbb{E}\bigl{[}\sigma(u_{1})\sigma(u_{2})\bigr{]}\dots&\mathbb{E}\bigl{[}\sigma(u_{1})\sigma(u_{n})\bigr{]}\\\
\vdots&\ddots&\vdots\\\
\mathbb{E}\bigl{[}\sigma(u_{n})\sigma(u_{1})\bigr{]}&\dots&\mathbb{E}\bigl{[}\sigma(u_{n})\sigma(u_{n})\bigr{]}\end{pmatrix}+\sigma^{2}_{b}\right)\otimes
I_{d_{l+1}}$ $\displaystyle\text{ with }u\sim N(0,\Lambda^{L-1})$

In (2.2) we have used the property of the Kronecker Product, namely
$\operatorname{vec}(AXB)=(B^{T}\otimes A)\operatorname{vec}(X)$. ∎

####  A.1.2 Neural Tangent Kernel (Lemma A.1 and Theorem 3.1)

The following lemma describes how the output of a Fully-Connected Neural Net
trained with Gradient Descent with an infinitesimally small learning rate can
be interpreted as Kernel Regression with the Neural Tangent Kernel.

######  Lemma A.1 (From [Arora et al., 2019]).

Consider minimizing the squared loss $\ell(\theta)$ by Gradient Descent with
infinitesimally small learning
rate444https://en.wikipedia.org/wiki/Euler_method:
$\frac{d\theta(t)}{dt}=-\nabla\ell(\theta(t))$. Then the output of the Network
$F(\theta,X)$ evolves as:

$\displaystyle\frac{du(t)}{dt}$
$\displaystyle=-H(t)\cdot\operatorname{vec}(u(t)-Y)$ $\displaystyle\text{with
}u(t)$ $\displaystyle=F(\theta(t),X)$ $\displaystyle\text{and }H(t)$
$\displaystyle=\frac{\partial\operatorname{vec}(F(\theta(t),X)}{\partial\theta}\left(\frac{\partial\operatorname{vec}(F(\theta(t),X)}{\partial\theta}\right)^{T}$

###### Proof.

The parameters $\theta$ evolve according to the differential equation

$\displaystyle\frac{d\theta(t)}{dt}$
$\displaystyle=-\nabla\ell(\theta(t))=\left(\frac{\partial\operatorname{vec}(F(\theta(t),X)}{\partial\theta}\right)^{T}\operatorname{vec}(F(\theta(t),X)-Y)^{T}$
where $t>0$ is a continous time index. Using this equation, the evolution of
the Network output $F(\theta(l),X)$ can be written as
$\displaystyle\frac{dF(\theta(t),X}{dt}$
$\displaystyle=\frac{\partial\operatorname{vec}(F(\theta(t),X)}{\partial\theta}\left(\frac{\partial\operatorname{vec}(F(\theta(t),X)}{\partial\theta}\right)^{T}\operatorname{vec}(F(\theta(t),X)-Y)^{T}$
Rewriting it using $\emph{u}(t)=\operatorname{vec}(F(\theta(t),X))$
$\displaystyle\frac{d\emph{u}(t)}{dt}$
$\displaystyle=-\emph{H}(t)\cdot\operatorname{vec}(\emph{u}(t)-Y)$

∎

When the width of the network is allowed to go to infinity, it can be shown
that the matrix $H(t)$ remains constant during training i.e. equal to $H(0)$.
Moreover, under the random initialization of the parameters defined in 3.1,
the matrix $H(0)$ converges in probability to a certain deterministic Kernel
Matrix $H^{*}$ which is called the Neural Tangent Kernel $\Theta$ evaluated on
the training data. If $H(t)=H^{*}$ for all $t$, then equation becomes

$\displaystyle\frac{du(t)}{dt}$
$\displaystyle=-H^{*}\cdot\operatorname{vec}(u(t)-Y)$

which is identical to the dynamics of Kernel Regression under Gradient Glow,
for which at time $t\rightarrow\infty$ the final prediction function is

$\displaystyle F^{*}(X_{test})=H^{*}_{test,train}(H_{train,train}^{*})^{-1}y$

In the transductive setting $H_{train,train}^{*}$ implicitly accounts for
incorporating the test data during training. To calculate the closed form
expression for the NTK of a FCN of depth $l$ we have to simplify:

$\displaystyle\Theta^{l}=\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\theta}\left(\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\theta}\right)^{T}$

Using our model definition, this results in calculating

$\displaystyle\Theta^{L}=\sum_{h=1}^{H}\frac{\partial\operatorname{vec}(F^{L}(\theta,X))}{\partial\operatorname{vec}(W^{h})}\left(\frac{\partial\operatorname{vec}(F(\theta,X)}{\partial\operatorname{vec}(W^{h})}\right)^{T}+\frac{\partial\operatorname{vec}(F(\theta,X))}{\partial\operatorname{vec}(b^{h})}\left(\frac{\partial\operatorname{vec}(F^{L}(\theta,X)}{\partial\operatorname{vec}(b^{h})}\right)^{T}$
(3)

#### Neural Tangent Kernel (Theorem 3.2)

See 3.2

###### Proof.

Proof is by induction, similar to the NNGP derivation.
Base Case:

$\displaystyle\Theta^{1}$
$\displaystyle=\Lambda{{}^{1}}=\frac{\partial\operatorname{vec}(F^{1}(\theta,X))}{\partial\operatorname{vec}(W^{1})}\left(\frac{\partial\operatorname{vec}(F^{1}(\theta,X)}{\partial\operatorname{vec}(W^{1})}\right)^{T}+\frac{\partial\operatorname{vec}(F^{1}(\theta,X))}{\partial\operatorname{vec}(b^{1})}\left(\frac{\partial\operatorname{vec}(F^{1}(\theta,X)}{\partial\operatorname{vec}(b^{1})}\right)^{T}$
$\displaystyle=(\frac{\sigma^{2}_{w}}{d_{0}}X^{T}X+{\sigma^{2}_{b}})\otimes
I_{d_{1}}$ Induction Step: $\displaystyle\Theta^{l+1}$
$\displaystyle=\sum_{h=1}^{l+1}\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(W^{h})}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X)}{\partial\operatorname{vec}(W^{h})}\right)^{T}$
$\displaystyle=\underbrace{\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(W^{l+1})}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(W^{l+1})}\right)^{T}+\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(b^{l+1})}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(b^{l+1})}\right)^{T}}_{B}$
$\displaystyle+\underbrace{\sum_{h=1}^{l}\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(W^{h})}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(W^{h})}\right)^{T}+\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(b^{h})}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(b^{h})}\right)^{T}}_{\Gamma}$
$\displaystyle B$
$\displaystyle=\frac{\sigma^{2}_{w}}{d_{l}}(G^{l^{T}}G\otimes
I_{d_{l+1}})+\sigma^{2}_{b}(\mathds{1}_{n}\otimes
I_{d_{l+1}})=(\frac{\sigma^{2}_{w}}{d_{l}}G^{l^{T}}G^{l}+\sigma^{2}_{b})\otimes
I_{d_{l+1}}$
$\displaystyle(\frac{\sigma^{2}_{w}}{d_{l}}G^{l^{T}}G^{l})_{ij}=\frac{\sigma^{2}_{w}}{d_{l}}\sum_{m}^{d_{l}}G^{l}_{im}G^{l}_{jm}\overset{\overset{P}{d_{l}\rightarrow\infty}}{\longrightarrow}\sigma^{2}_{w}\underset{u,v\sim
N(0,\biggl{(}\begin{smallmatrix}\Lambda^{l-1}_{ii}&\Lambda^{l-1}_{ij}\\\
\Lambda^{l-1}_{ji}&\Lambda^{l-1}_{jj}\end{smallmatrix}\biggr{)})}{\mathbb{E}}\bigl{[}\sigma(u)\sigma(v)\bigr{]}$

Where we used the fact that the output of the previous layer goes to infinity
(so $d_{l}\rightarrow\infty$)

$\displaystyle\implies B=\Lambda^{L}\otimes I_{d_{l+1}}$ $\displaystyle\Gamma$
$\displaystyle=\sum_{h=1}^{l}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\operatorname{vec}(W^{l})}\right)\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\operatorname{vec}(W^{l})}\right)^{T}$
$\displaystyle+\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\operatorname{vec}(b^{l})}\right)\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\operatorname{vec}(b^{l})}\right)^{T}$
$\displaystyle=\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}(\Theta^{l}\otimes
I_{d_{l}})\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}\right)^{T}$
$\displaystyle=\frac{\sigma^{2_{w}}}{d_{l}}(I_{n}\otimes
W^{l+1})\Sigma^{l}(\Theta^{l}\otimes I_{d})\Sigma^{l}(I_{n}\otimes
W^{l+1^{T}})$ $\displaystyle T_{IJ}$
$\displaystyle=\left(\frac{\sigma_{w}^{2}}{d_{l}}(I_{n}\otimes
W^{l+1})\Sigma^{l}(\Theta^{l}\otimes I_{d})\Sigma^{l}(I_{n}\otimes
W^{l+1^{T}})\right)_{IJ}=\frac{\sigma_{w}^{2}}{d_{l}}W^{l+1}\Sigma^{l}_{II}\Theta^{l}_{ij}\Sigma^{l}_{JJ}W^{l+1^{T}}$
$\displaystyle=\Theta^{l}_{ij}\frac{\sigma_{w}^{2}}{d_{l}}W^{l+1}\Sigma^{l}_{II}\Sigma^{l}_{JJ}W^{l+1^{T}}$
$\displaystyle(\frac{\sigma_{w}^{2}}{d_{l}}W$
${}^{l+1}\Sigma^{l}_{II}\Sigma^{l}_{JJ}W^{l+1^{T}})_{uv}=\frac{\sigma_{w}^{2}}{d_{l}}\sum_{st}^{d_{l}}\Sigma^{l}_{II_{ss}}\Sigma^{l}_{JJ_{tt}}W_{us}W_{vt}\overset{\overset{P}{d_{l}\rightarrow\infty}}{\longrightarrow}\delta_{uv}\sigma^{2}_{w}\underset{s,t\sim
N(0,\biggl{(}\begin{smallmatrix}\Lambda^{l-1}_{ii}&\Lambda^{l-1}_{ij}\\\
\Lambda^{l-1}_{ji}&\Lambda^{l-1}_{jj}\\\
\end{smallmatrix}\biggr{)})}{\mathbb{E}}\bigl{[}\dot{\sigma}(s)\dot{\sigma}(t)\bigr{]}$

Convergence in probability follows from the Law of Large Numbers. The
righthandside follows from the definition of $\Sigma^{l}$ and the fact that
the output of layer $l-1$ in its infinite width is a Gaussian Process.

$\displaystyle\implies T$ $\displaystyle=(\Theta\odot\dot{\Lambda}^{L})\otimes
I_{d_{l+1}}$ $\displaystyle\implies\Theta^{l+1}$
$\displaystyle=B+\Gamma=\Lambda^{l}+\left(\dot{\Lambda}^{l}\odot\Theta^{l}\right)$

∎

###  A.2 NTK & GP for Graph Neural Network

We copied the definitions of the Graph Neural Network from the main section.

See 3.2

#### Derivatives

The derivative of $F(\theta,X)$ with respect to $W^{l}$ is

$\displaystyle\frac{\partial\operatorname{vec}(F(\theta,X))}{\partial\operatorname{vec}(W^{l})}=\frac{\partial\operatorname{vec}(F^{L})}{\partial\operatorname{vec}(G^{L-1})}\frac{\partial\operatorname{vec}(G^{L-1})}{\partial\operatorname{vec}(F^{L-1)}}\cdots\frac{\partial\operatorname{vec}(F^{l+1})}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(W^{l})}$

Using

$\displaystyle\frac{\partial\operatorname{vec}(F^{h})}{\partial\operatorname{vec}(G^{h-1})}$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{h-1}}}(A\otimes W^{h})$
$\displaystyle\Sigma^{h}:=\frac{\partial\operatorname{vec}(G^{h})}{\partial\operatorname{vec}(F^{h})}$
$\displaystyle=\operatorname{diag}(\operatorname{vec}(\dot{\sigma}(F^{h}))$
$\displaystyle\frac{\partial\operatorname{vec}(F^{h})}{\partial\operatorname{vec}(W^{h})}$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{h-1}}}(AG^{h-1^{T}}\otimes
I_{d_{h}})$ $\displaystyle\frac{\partial\operatorname{vec}(F^{h})}{\partial
b^{h}}$ $\displaystyle=\sigma_{b}(A\mathbf{1}_{n}\otimes I_{d_{h}})$

####  A.2.1 Gaussian Process (Theorem 3.3)

See 3.3

###### Proof.

Proof is by induction. We define $\text{Y}^{L}=F^{L}(X)$.

$\displaystyle\mathbb{E}(\operatorname{vec}(Y^{1}))$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{0}}}\operatorname{vec}\left(\biggl{(}\frac{\sigma_{w}}{\sqrt{d_{0}}}W^{1}X+\sigma_{b}B^{1}\biggr{)}A^{T}\right)=0$
$\displaystyle\mathrm{Cov}(\operatorname{vec}(Y^{1}))$
$\displaystyle=\mathrm{Cov}\bigl{[}(A\otimes
I_{d_{1}})\operatorname{vec}(\frac{\sigma_{w}}{\sqrt{d_{0}}}W^{1}X+\sigma_{b}B^{1})\bigr{]}$
$\displaystyle=(A\otimes
I_{d_{1}})\mathbb{E}\bigl{[}\operatorname{vec}(\frac{\sigma_{w}}{\sqrt{d_{0}}}W^{1}XA^{T}+\sigma_{b}B^{1})\bigr{]}(A^{T}\otimes
I_{d_{1}})$ $\displaystyle=(A\Lambda^{1}A^{T})\otimes I_{d_{1}}$

The Base Case is reduced to the Base Case of NNGP using a property of the
Kronecker Product, namely $(A\otimes B)(C\otimes D)=(AC\otimes BD)$.
Induction Step is again just an application of the Kronecker Property and
follows the NNGP proof in 3.1.

$\displaystyle\mathbb{E}(\operatorname{vec}(Y^{l+1}))$ $\displaystyle=0$
$\displaystyle\mathrm{Cov}(\operatorname{vec}(Y^{l+1}))$
$\displaystyle=(A\Lambda^{l+1}A^{T})\otimes I_{d_{l+1}}$

∎

####  A.2.2 Neural Tangent Kernel (Theorem 3.4)

See 3.4

###### Proof.

Proof is by induction, similar to the NNGP derivation.
Base Case:

$\displaystyle\Theta^{1}=\Lambda{{}^{1}}=\frac{\partial\operatorname{vec}(F^{1}(\theta,X))}{\partial\operatorname{vec}(W^{1})}\left(\frac{\partial\operatorname{vec}(F^{1}(\theta,X)}{\partial\operatorname{vec}(W^{1})}\right)^{T}+\frac{\partial\operatorname{vec}(F^{1}(\theta,X))}{\partial\operatorname{vec}(b^{1})}\left(\frac{\partial\operatorname{vec}(F^{1}(\theta,X)}{\partial\operatorname{vec}(b^{1})}\right)^{T}$
$\displaystyle=\bigl{(}A\bigl{(}\frac{\sigma^{2}_{w}}{d_{0}}X^{T}X+{\sigma^{2}_{b}}\bigr{)}A^{T}\bigr{)}\otimes
I_{d_{1}}$

Induction Step:

$\displaystyle\Theta^{l+1}$
$\displaystyle=\sum_{h=1}^{l+1}\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(W^{h})}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X)}{\partial\operatorname{vec}(W^{h})}\right)^{T}$
$\displaystyle=\underbrace{\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(W^{l+1})}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(W^{l+1})}\right)^{T}+\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(b^{l+1})}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(b^{l+1})}\right)^{T}}_{B}$
$\displaystyle+\underbrace{\sum_{h=1}^{l}\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(W^{h})}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(W^{h})}\right)^{T}+\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(b^{h})}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(b^{h})}\right)^{T}}_{\Gamma}$
$\displaystyle B$
$\displaystyle=\biggl{(}A\biggl{(}\frac{\sigma^{2}_{w}}{d_{l}}G^{l^{T}}G^{l}+\sigma^{2}_{b}\biggr{)}A^{T}\biggr{)}\otimes
I_{d_{l+1}}$

We can now proceed similar to the previous NTK derivations (see 3.2) and
therefore will skip the parts which stay the same.

$\displaystyle\implies B=A\left(\Lambda^{L}\otimes I_{d_{l+1}}\right)A^{T}$

$\displaystyle\Gamma$
$\displaystyle=\sum_{h=1}^{l}\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\operatorname{vec}(W^{l})}\right)\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\operatorname{vec}(W^{l})}\right)^{T}$
$\displaystyle+\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\operatorname{vec}(b^{l})}\right)\left(\frac{\partial\operatorname{vec}(F^{l+1}(\theta,X))}{\partial\operatorname{vec}(G^{l})}\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\operatorname{vec}(b^{l})}\right)^{T}$
$\displaystyle=\frac{\sigma^{2_{w}}}{d_{l}}(A\otimes
W^{l+1})\Sigma^{l}(\Theta^{l}\otimes I_{d})\Sigma^{l}(A^{T}\otimes
W^{l+1^{T}})$ $\displaystyle=\frac{\sigma^{2_{w}}}{d_{l}}(A\otimes
I_{d_{l}})(I_{n}\otimes W^{l+1})\Sigma^{l}(\Theta^{l}\otimes
I_{d})\Sigma^{l}(I_{n}\otimes W^{l+1^{T}}(A^{T}\otimes I_{d_{l}}))$

We reduced the proof to the NTK proof using property of the Kronecker Product
in the last line.

$\displaystyle\implies T=(A(\Theta\odot\dot{\Lambda}^{L})A^{T})\otimes
I_{d_{l+1}}$

∎

###  A.3 NTK & GP for Graph Neural Network with Skip-Concatenate Connections

The model definition is copied from Section 3.3 for the readers convenience.

See 3.3

The derivatives are similar to the Graph Neural Network derivatives (see A.2).
Only $\Sigma^{h}$ is different.

$\displaystyle\Sigma^{h}:=\frac{\partial\operatorname{vec}(G^{h})}{\partial\operatorname{vec}(F^{h})}=\begin{pmatrix}\operatorname{diag}(\operatorname{vec}\dot{\sigma}(F^{h}_{\cdot
1}))&0&0&\dots&0\\\ I_{d_{h}}&0&0&\dots&0\\\
0&\operatorname{diag}(\operatorname{vec}\dot{\sigma}(F^{h}_{\cdot
2}))&0&\dots&0\\\ 0&I_{d_{h}}&0&\dots\\\ 0&0&\ddots\\\ \vdots&\vdots&\ddots\\\
0&0&&\dots&\operatorname{diag}(\operatorname{vec}\dot{\sigma}(F^{h}_{\cdot
n}))\\\ 0&0&0&\dots&I_{d_{h}}\\\ \end{pmatrix}\in\mathbb{R}^{2d_{l}n\times
2d_{l}n}$ $\displaystyle\Sigma^{h}\text{ is block-diagonal, with each block
}\Sigma^{h}_{II}=\begin{pmatrix}\operatorname{diag}(\operatorname{vec}\dot{\sigma}(F^{h}_{\cdot
i}))\\\ I_{d_{h}}\end{pmatrix}$

####  A.3.1 Gaussian Process (Theorem 3.5)

See 3.5

###### Proof.

Prove is by induction. We define $\text{Y}^{L}=F^{L}(X)$. The Base Case
doesn’t change, so

$\displaystyle\mathbb{E}(\operatorname{vec}(Y^{1}))=0$
$\displaystyle\mathrm{Cov}(\operatorname{vec}(Y^{1}))=(A\Lambda^{1}A^{T})\otimes
I_{d_{1}}$ The Induction Step:
$\displaystyle\mathbb{E}(\operatorname{vec}(Y^{l+1}))=0$
$\displaystyle\mathrm{Cov}(\operatorname{vec}(Y^{l+1}))=\mathrm{Cov}\bigl{[}(A\otimes
I_{d_{l+1}})\operatorname{vec}(\frac{\sigma_{w}}{\sqrt{d_{0}}}W^{l+1}G^{l}A^{T}+\sigma_{b}B^{l+1})\bigr{]}$
$\displaystyle=(A\otimes
I_{d_{l+1}})\mathrm{Cov}\bigl{[}\operatorname{vec}(\frac{\sigma_{w}}{\sqrt{d_{0}}}W^{l+1}G^{l}+\sigma_{b}B^{1})\bigr{]}(A^{T}\otimes
I_{d_{l+1}})$ $\displaystyle=(A\otimes
I_{d_{l+1}})\left(\frac{\sigma_{w}^{2}}{d_{l}}\mathbb{E}\biggl{[}(I_{n}\otimes
W^{l+1})\operatorname{vec}(G^{l})\operatorname{vec}(G^{l})^{T}(I_{n}\otimes
W^{l+1^{T}})\biggr{]}+\sigma_{b}^{2}(\mathds{1}_{n}\otimes\mathbf{1}_{d_{l+1}})\right)(A^{T}\otimes
I_{d_{l+1}})$
$\displaystyle\frac{\sigma_{w}^{2}}{2d_{l}}\mathbb{E}\biggl{[}(I_{n}\otimes
W^{l+1})\operatorname{vec}(G^{l})\operatorname{vec}(G^{l})^{T}(I_{n}\otimes
W^{l+1^{T}})\biggr{]}_{IJ_{uv}}=\frac{\sigma_{w}^{2}}{2d_{l}}\mathbb{E}\biggl{[}W_{u}(\operatorname{vec}(G^{l})\operatorname{vec}(G^{l})^{T})_{IJ}W_{v}^{T}\biggr{]}$
$Z:=\left(\operatorname{vec}(G^{l})\operatorname{vec}(G^{l})^{T}\right)_{IJ}$
and $Z_{11}$ is the upper left block matrix of size $\mathbb{R}^{d_{l}\times
d_{l}}$. and $W^{l+1}_{u}=\biggl{[}\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{u},\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{u}\biggr{]}$ with $\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{u},\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{u}\in\mathbb{R}^{1\times d_{l}}$, so we split
$W^{l+1}_{u}$ into two parts, each of length $d_{l}$.
$\displaystyle\frac{\sigma_{w}^{2}}{2d_{l}}\mathbb{E}\biggl{[}W_{u}(\operatorname{vec}(G^{l})\operatorname{vec}(G^{l})^{T})_{IJ}W_{v}^{T}\biggr{]}$
$\displaystyle=\frac{\sigma_{w}^{2}}{2d_{l}}\mathbb{E}\biggl{[}\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{u}Z_{11}\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{v}+\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{u}Z_{12}\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{v}+\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{u}Z_{21}\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{v}+\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{u}Z_{22}\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{v}\biggr{]}$
$\displaystyle=\delta_{uv}\frac{\sigma_{w}^{2}}{2d_{l}}\mathbb{E}\biggl{[}\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{u}Z_{11}\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{v}+\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{u}Z_{22}\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{v}\biggr{]}$
$\displaystyle=\delta_{uv}\frac{\sigma_{w}^{2}}{2d_{l}}\left(\sum_{s}^{d_{l}}\sigma(Y^{l})_{is}\sigma(Y^{l})_{js}+\sum_{s}^{d_{l}}(Y^{l}_{is}Y^{l}_{js})\right)=\delta_{uv}\frac{\sigma_{w}^{2}}{2d_{l}}\left(\sum_{s}^{d_{l}}\sigma(Y^{l})_{is}\sigma(Y^{l})_{js}+(Y^{l}_{is}Y^{l}_{js})\right)$
$\displaystyle\overset{\overset{P}{d_{l}\rightarrow\infty}}{\longrightarrow}\delta_{uv}\frac{1}{2}\biggl{(}\underset{s,t\sim
N(0,\biggl{(}\begin{smallmatrix}\Lambda^{l-1}_{ii}&\Lambda^{l-1}_{ij}\\\
\Lambda^{l-1}_{ji}&\Lambda^{l-1}_{jj}\end{smallmatrix}\biggr{)})}{\mathbb{E}}\bigl{[}\sigma(s)\sigma(t)\bigr{]}+\mathbb{E}\bigl{[}st\bigr{]}\biggr{)}$

Convergence in probability follows from the Law of Large Numbers. The
righthandside follows from the definition of $\Sigma^{l}$ and the fact that
the output of layer $l-1$ is a from a Gaussian Process. ∎

####  A.3.2 Neural Tangent Kernel (Theorem 3.6)

See 3.6

###### Proof.

Proof is by Induction, similar to the NNGP derivation. The Base Case is just a
repetition of 3.4 as $F^{1}$ has no Skip-Concatenate Connections. We will skip
parts which are same as the NTK/ GNTK derivations. Induction Step:

$\displaystyle\Theta^{l+1}$ $\displaystyle=B+\Gamma$ $\displaystyle B$
$\displaystyle=\biggl{(}A\biggl{(}\frac{\sigma_{w}^{2}}{2d_{l}}G^{l^{T}}G^{l}+\sigma^{2}_{b}\mathds{1}_{n}\biggr{)}A^{T}\biggr{)}\otimes
I_{d_{l+1}}$ $\displaystyle\frac{\sigma_{w}^{2}}{2d_{l}}G^{l^{T}}G^{l}$
$\displaystyle\overset{\overset{P}{d_{l}\rightarrow\infty}}{\rightarrow}\sigma^{2}_{w}\begin{pmatrix}\frac{1}{2}\biggl{(}\mathbb{E}\bigl{[}\sigma(u_{1})\sigma(u_{1})\bigr{]}+\mathbb{E}\bigl{[}u_{1}u_{1}\bigr{]}\biggr{)}&\frac{1}{2}\biggl{(}\mathbb{E}\bigl{[}\sigma(u_{1})\sigma(u_{2})\bigr{]}+\mathbb{E}\bigl{[}u_{1}u_{2}\bigr{]}\biggr{)}\dots&\frac{1}{2}\biggl{(}\mathbb{E}\bigl{[}\sigma(u_{1})\sigma(u_{n})\bigr{]}+\mathbb{E}\bigl{[}u_{1}u_{n}\bigr{]}\biggr{)}\\\
\vdots&\ddots&\vdots\\\
\frac{1}{2}\biggl{(}\mathbb{E}\bigl{[}\sigma(u_{n})\sigma(u_{1})\bigr{]}+\mathbb{E}\bigl{[}u_{n}u_{1}\bigr{]}\biggr{)}&\dots&\frac{1}{2}\biggl{(}\mathbb{E}\bigl{[}\sigma(u_{n})\sigma(u_{n})\bigr{]}+\mathbb{E}\bigl{[}u_{n}u_{n}\bigr{]}\biggr{)}\end{pmatrix}$
$\displaystyle\implies B=\Lambda^{L}\otimes I_{d_{l+1}}$

$\displaystyle\Gamma=\frac{\sigma^{2_{w}}}{2d_{l}}(A\otimes
I_{d_{l}})(I_{n}\otimes W^{l+1})\Sigma^{l}(\Theta^{l}\otimes
I_{d})\Sigma^{l}(I_{n}\otimes W^{l+1^{T}})(A^{T}\otimes I_{d_{l}}))$
$\displaystyle\frac{\sigma^{2}_{w}}{2d_{l}}(I_{n}\otimes
W^{l+1})\Sigma^{l}(\Theta^{l}\otimes I_{d})\Sigma^{l}(I_{n}\otimes
W^{l+1^{T}})_{IJ_{uv}}=\Theta_{ij}\frac{\sigma^{2}_{w}}{2d_{l}}W^{l+1}_{u}\Sigma^{l}_{II}\Sigma^{l^{T}}_{JJ}(W^{l+1}_{v})^{T}$
$Z:=\left(\operatorname{vec}(G^{l})\operatorname{vec}(G^{l})^{T}\right)_{IJ}$
and $Z_{11}$ is the upper left block matrix of size $\mathbb{R}^{d_{l}\times
d_{l}}$. and $W^{l+1}_{u}=\biggl{[}\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{u},\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{u}\biggr{]}$ with $\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{u},\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{u}\in\mathbb{R}^{1\times d_{l}}$, so we split
$W^{l+1}_{u}$ into two parts, each of length $d_{l}$.
$\displaystyle=\Theta_{ij}\frac{\sigma_{w}^{2}}{2d_{l}}\left(\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{u}Z_{11}\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{v}+\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{u}Z_{12}\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{v}+\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{u}Z_{21}\overset{\scriptscriptstyle
1}{W}\vphantom{W}^{l+1}_{v}+\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{u}Z_{22}\overset{\scriptscriptstyle
2}{W}\vphantom{W}^{l+1}_{v}\right)$
$\displaystyle\overset{\overset{P}{d_{l}\rightarrow\infty}}{\longrightarrow}\delta_{uv}\Theta_{ij}\sigma_{w}^{2}\frac{1}{2}\biggl{(}\mathbb{E}\bigl{[}\dot{\sigma}(s)\dot{\sigma}(t)\bigr{]}+1\biggr{)}$

Which follows the same idea for the proof of the NTK. ∎

###  A.4 NTK & GP for Graph Attention Neural Network*

The model definition is copied from Section 3.3 for the readers convenience.
See 3.4

#### Derivatives

$\displaystyle\overset{\scriptscriptstyle 2}{\Sigma}\vphantom{\sigma}^{l}$
$\displaystyle:=\frac{\partial\operatorname{vec}(G^{l})}{\partial\operatorname{vec}(F^{l})}=\operatorname{diag}(\operatorname{vec}(\dot{\sigma}_{2}(F^{l})))$
$\displaystyle\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(W^{l})}$
$\displaystyle=\frac{\sigma_{w}}{\sqrt{d_{l-1}}}\left[F^{l1},\cdots,F^{lH}\right]\otimes
I_{d_{l}}$
$\displaystyle\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(\sigma_{1}(L^{l,h}))}$
$\displaystyle=I_{n}\otimes\left(\frac{\sigma_{w}}{\sqrt{d_{l-1}}}W^{l,h}G^{l-1}\right)$
$\displaystyle\overset{\scriptscriptstyle 1}{\Sigma}\vphantom{\sigma}^{l,h}$
$\displaystyle:=\frac{\partial\operatorname{vec}(\sigma_{1}(L^{l,h}))}{\partial\operatorname{vec}(L^{l,h})}=\operatorname{diag}(\operatorname{vec}(\dot{\sigma}_{1}(L^{l,h}))$
$\displaystyle\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}$
$\displaystyle=\frac{\sigma_{c}}{\sqrt{2d_{l-1}}}\hat{A}\operatorname{concat}((\mathbf{1}_{n}\otimes
G^{T}),(G^{T}\otimes\mathbf{1}_{n}))\text{ with
$\hat{A}:=\operatorname{diag}(\operatorname{vec}(A^{T})$}$ derived using
$\operatorname{vec}(L^{l,h})=\frac{\sigma_{c}}{\sqrt{2d_{l-1}}}\hat{A}\left((\mathbf{1}_{n}\otimes
G^{T})c_{1}^{l,h}+(G^{T}\otimes\mathbf{1}_{n}^{T})c_{2}^{l,h}\right)$
$\frac{\sigma_{c}}{\sqrt{2d_{l-1}}}\hat{A}\left((\mathbf{1}_{n}\otimes
G^{T}c_{1}^{l,h})+(G^{T}c_{2}^{l,h}\otimes\mathbf{1}_{n})\right)=\frac{\sigma_{c}}{\sqrt{2d_{l-1}}}\hat{A}\operatorname{concat}(\mathbf{1}_{n}\otimes
I_{n},I_{n}\otimes\mathbf{1}_{n})\operatorname{concat}(G,G)^{T}$
$\displaystyle\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}$
$\displaystyle=\frac{\sigma_{c}}{\sqrt{2d_{l-1}}}\hat{A}\left((\mathbf{1}_{n}\otimes(I_{n}\otimes
c_{1}^{l,h^{T}})+(I_{n}\otimes c_{2}^{l,h^{T}})\otimes\mathbf{1}_{n})\right)$
$\displaystyle\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(G^{l-1})}=$
$\displaystyle\frac{1}{\sqrt{H}}\sum_{h}^{H}\biggr{[}\left(I_{n}\otimes\left(\frac{\sigma_{w}}{\sqrt{d_{l-1}}}W^{l,h}G^{l-1}\right)\right)\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}+\left(\sigma_{1}(L^{l,h})^{T}\otimes\frac{\sigma_{w}}{\sqrt{d_{l-1}}}W^{l,h}\right)\biggl{]}$

#### Proof Strategy for GAT* GP & NTK

The proof of the GAT* Gaussian Process follows from [Hron et al., 2020,
Theorem 1] which is the Scaled Attention Theorem from [Yang, 2019]. Theorem 1/
Scaled Attention Theorem is based on [Yang, 2019, 2020, Mastertheorem] which
prooves that the Infinite Width Neural Network connections to GP and NTK hold
for a variety of Architectures. The authors of Hron et al. [2020] generalizes
Theorem 1 to a particular scaling, namely the $d^{-\frac{1}{2}}$ scaling for
Attention Neural Networks. This is made precise in Theorem 3 from the
aforementioned authors. Adapting Theorem 1 is enough to proof the GAT*
Gaussian Process derivation because the GAT* Model does not require the
$d^{-\frac{1}{2}}$ scaling. Contrary to the previous proofs in this work which
derived the infinite Width Limit for $d_{l-1}\rightarrow\infty$ layer after
layer, the proofs for the NTK and GP for the GAT* are conduted for
min$\\{H,d_{l-1}\\}\to\infty$ (i.e. the Attention Heads and Weight Widths go
to infinity simultaneously for each layer). Similar techniques have been used
by [de G. Matthews et al., 2018] to demonstrate that Infinite Width Neural
Nets are Gaussian Processes when all Widths go to infinity simultaneously.
Before we start we have show that our GAT* model meets all assumptions from
[Hron et al., 2020, Theorem 1/ Theorem 3]. We have to make sure that the
output of the GAT* model is bounded by a constant which is independant of
$H,d_{l-1}$. This will make it possible to use Lemma 32 from Hron et al.
[2020]. This way all assumptions of Theorem 3 will be met. To prove
boundedness of our GAT* Model it suffices to prove boundedness for the only
component that is different to the Attention Neural Network (defined in Hron
et al. [2020]) namely $L$. Boundedness of the Model then follows by induction
and Hölder Inequality (see [Hron et al., 2020, Lemma 32] which is based on de
G. Matthews et al. [2018]). Boundedness of $L$ follows by direct application
of of [de G. Matthews et al., 2018, Lemma 19]. In words: $L_{ij}$ is just an
inner product of a constant vector (the data) with a normally distributed
vector. This inner product can be bounded by a constant independent of the
size of the normally distributed vector. Each entry $L_{ij}$ is just the same
vector $c$ which will establish the bound on all of $L$ using the mentioned
Lemma 19. The proof of the NTK is conducted using similar techniques to the
NTK proof from [Hron et al., 2020].

####  A.4.1 Gaussian Process (Theorem 3.7)

######  Lemma A.2.

If the output of a GAT Layer $l-1$ is a GP, so
$\operatorname{vec}(F^{l-1})\sim GP(0,\Omega\otimes I_{d_{l-1}})$ for a fixed
$\Omega$ and the $d_{l-1}\to\infty$, then $\operatorname{vec}(L^{l})\sim
GP(0,\psi(\Omega))$, with

$\displaystyle\psi(\Omega):=\mathbb{E}\bigl{[}\sigma_{1}(u)\sigma_{1}(u^{T})\bigr{]}\text{
with $u\sim GP\bigl{(}0,\sigma_{c}J_{A}\begin{pmatrix}\Omega&\Omega\\\
\Omega&\Omega\\\ \end{pmatrix}J_{A}^{T}\otimes I_{d_{l-1}}\bigr{)})$ }$ and
$J_{A}:=\operatorname{diag}(\operatorname{vec}(A^{T})\operatorname{concat}((\mathbf{1}_{n}\otimes
I_{n}),(I_{n}\otimes\mathbf{1}_{n}))$

###### Proof.

We will demonstrate the proof for $d_{l-1}\rightarrow\infty$ sequentially for
each layer, utilizing Induction to conclude the proof. (The base case follows
from using the Definition of $L^{1}$). This will make the proof much simpler.
In the case of min$\\{d_{l-1}\\}\rightarrow\infty$, (so all Widths going to
infinity simultaneously) the proof can be conducted applying [Yang, 2019,
Mastertheorem/ Scaled Attention Neural Networks] or [Hron et al., 2020,
Theorem 1/ Theorem 3, Part I)]. The proof is conducted for $L^{l,h}$ so for
every head $h$ with corresponding $c^{l,h}$ but we will omit $h$ and write
$c^{l}$ instead $c^{l,h}$ and $L^{l}$ instead $L^{l}$.

$\displaystyle\mathbb{E}\bigl{[}L^{l}_{ij}\bigr{]}$ $\displaystyle=0$
$\displaystyle\mathbb{E}\bigl{[}L^{l}_{lm}L^{l}_{st}\bigr{]}$
$\displaystyle=\frac{\sigma_{c}^{2}}{2d_{l-1}}A_{lm}A_{st}\mathbb{E}\bigl{[}\left(c_{1}^{l^{T}}(G_{\cdot
l}+G_{\cdot m})+c_{2}^{l^{T}}(G_{\cdot l}+G_{\cdot
m})\right)+\left(c_{1}^{l^{T}}(G_{\cdot s}+G_{\cdot t})c_{2}^{l^{T}}(G_{\cdot
s}+G_{\cdot t})\right)\bigr{]}=$
$\displaystyle=\frac{\sigma_{c}^{2}}{2d_{l-1}}A_{lm}A_{st}\biggl{(}\mathbb{E}\bigl{[}c_{1}^{l^{T}}(G_{\cdot
l}+G_{\cdot m})c_{1}^{l^{T}}(G_{\cdot s}+G_{\cdot
t})\bigr{]}+\mathbb{E}\bigl{[}c_{1}^{l^{T}}(G_{\cdot l}+G_{\cdot
m})c_{2}^{l^{T}}(G_{\cdot s}+G_{\cdot t})\bigr{]}$
$\displaystyle+\mathbb{E}\bigl{[}c_{2}^{l^{T}}(G_{\cdot l}+G_{\cdot
m})c_{1}^{l^{T}}(G_{\cdot s}+G_{\cdot
t})\bigr{]}+\mathbb{E}\bigl{[}c_{2}^{l^{T}}(G_{\cdot l}+G_{\cdot
m})c_{2}^{l^{T}}G_{\cdot l}{s}+G_{\cdot t})\bigr{]}\biggr{)}$
$\displaystyle=\frac{\sigma_{c}^{2}}{2d_{l-1}}A_{lm}A_{st}\biggl{(}\mathbb{E}\bigl{[}c_{1}^{l^{T}}(G_{\cdot
l}+G_{\cdot m})c_{1}^{l^{T}}(G_{\cdot s}+G_{\cdot
t})\bigr{]}+\mathbb{E}\bigl{[}c_{2}^{l^{T}}(G_{\cdot l}+G_{\cdot
m})c_{2}^{l^{T}}G_{\cdot l}{s}+G_{\cdot t})\bigr{]}\biggr{)}$
$\displaystyle=\frac{\sigma_{c}^{2}}{2d_{l-1}}A_{lm}A_{st}\biggl{(}\mathbb{E}\bigl{[}\sum_{uv}c_{1u}^{l}c_{1v}^{l}G_{ul}G_{vs}\bigr{]}+\mathbb{E}\bigl{[}\sum_{uv}c_{1u}^{l}c_{1v}^{l}G_{ul}G_{vt}\bigr{]}+\mathbb{E}\bigl{[}\sum_{uv}c_{1u}^{l}c_{1v}^{l}G_{um}G_{vs}\bigr{]}+\mathbb{E}\bigl{[}\sum_{uv}c_{1u}^{l}c_{1v}^{l}G_{um}G_{vt}\bigr{]}$
$\displaystyle+\mathbb{E}\bigl{[}\sum_{uv}c_{2u}^{l}c_{2v}^{l}G_{ul}G_{vs}\bigr{]}+\mathbb{E}\bigl{[}\sum_{uv}c_{2u}^{l}c_{2v}^{l}G_{ul}G_{vt}\bigr{]}+\mathbb{E}\bigl{[}\sum_{uv}c_{2u}^{l}c_{2v}^{l}G_{um}G_{vs}\bigr{]}+\mathbb{E}\bigl{[}\sum_{uv}c_{2u}^{l}c_{2v}^{l}G_{um}G_{vt}\bigr{]}\biggr{)}$
$\overset{\text{Converges in probability for
$d_{l-1}\rightarrow\infty$}}{\longrightarrow}$
$\displaystyle\sigma_{c}^{2}A_{lm}A_{st}\biggl{(}\mathbb{E}\bigl{[}\sigma_{1}(u_{l})\sigma_{1}(u_{s})\bigr{]}+\mathbb{E}\bigl{[}\sigma_{1}(u_{l})\sigma_{1}(u_{t})\bigr{]}+\mathbb{E}\bigl{[}\sigma_{1}(u_{m})\sigma_{1}(u_{s})\bigr{]}+\mathbb{E}\bigl{[}\sigma_{1}(u_{m})\sigma_{1}(u_{t})\bigr{]}\biggr{)}$

with $u=\operatorname{vec}(F^{l-1})\sim GP(0,\Omega\otimes I_{d_{l-1}})$ ∎

See 3.7

###### Proof Sketch.

Theorem 3.3 can be derived by just applying [Hron et al., 2020, Part II)
Theorem 1 (which itself is from Yang [2020] or Part II) Theorem 3]. Notice
that for prooving Part II) Theorem 3) at no point is the actual Definition the
Attention Neural Networks used therefore the proves applies to our model
without any adaption.

$\displaystyle\mathbb{E}\bigl{[}\operatorname{vec}(F^{l})\bigr{]}$
$\displaystyle=0$
$\displaystyle\mathbb{E}\bigl{[}\operatorname{vec}(F^{l})\operatorname{vec}(F^{l})^{T}\bigr{]}$
$\displaystyle=\mathbb{E}\bigl{[}\left(\sigma_{1}(L^{l,h})\otimes\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h}\right)G^{l-1^{T}}G^{l-1}\left(\sigma_{1}(L^{l,h})\otimes\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h}\right)^{T}\bigr{]}$
for block indices $I,J$
$\displaystyle\mathbb{E}\bigl{[}\operatorname{vec}(F^{l})\operatorname{vec}(F^{l})^{T}\bigr{]}_{IJ}$
$\displaystyle=$
$\displaystyle\mathbb{E}\bigl{[}\frac{1}{H}\sum_{h,h^{\prime}}^{H}\sum_{ST}\left(\sigma_{1}(L^{l,h})\otimes
I_{d_{l}}\right)_{IS}$
$\displaystyle\left[\left(I_{n}\otimes\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h}\right)G^{l-1^{T}}G^{l-1}\left(I_{d_{l}}\otimes\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h^{T}}\right)\right]_{ST}\left(\sigma_{1}(L^{l,h})\otimes
I_{d_{l}}\right)_{TJ}\bigr{]}$
$\displaystyle=\mathbb{E}\bigl{[}\frac{1}{H}\sum_{h,h^{\prime}}^{H}\sum_{ST}\sigma_{1}(L^{l,h})_{is}\frac{\sigma_{w}^{2}}{d_{l}}W^{l,h}$
$\displaystyle(G^{l-1^{T}}G^{l-1})_{ST}W^{l,h^{\prime
T}}\sigma_{1}(L^{l,h^{\prime}})_{tj}\bigr{]}$ for indices $u,v$
$\displaystyle\mathbb{E}\bigl{[}\operatorname{vec}(F^{l})\operatorname{vec}(F^{l})^{T}\bigr{]}_{IJ_{uv}}$
$\displaystyle=\mathbb{E}\bigl{[}\frac{1}{H}\sum_{h,h^{\prime}}^{H}\sum_{ST}\sum_{lm}\sigma_{1}(L^{l,h})_{is}\sigma_{1}(L^{l,h^{\prime}})_{tj}\frac{\sigma_{w}^{2}}{d_{l}}W^{l,h}_{ul}W^{l,h^{\prime}}_{vm}(G^{l-1^{T}}G^{l-1})_{ST_{lm}}\bigr{]}$
$\displaystyle=\frac{1}{H}\sum_{h,h^{\prime}}^{H}\sum_{ST}\sum_{lm}\sigma_{1}(L^{l,h})_{is}\sigma_{1}(L^{l,h^{\prime}})_{tj}\mathbb{E}\bigl{[}\frac{\sigma_{w}^{2}}{d_{l}}W^{l,h}_{ul}W^{l,h^{\prime}}_{vm}(G^{l-1^{T}}G^{l-1})_{ST_{lm}}\bigr{]}$
Now by a hand wavy argument we first let $d_{l-1}\rightarrow\infty$ to show,
$\displaystyle\mathbb{E}\bigl{[}\frac{\sigma_{w}^{2}}{d_{l}}W^{l,h}_{ul}W^{l,h^{\prime}}_{vm}(G^{l-1^{T}}G^{l-1})_{ST_{lm}}\bigr{]}\overset{P}{\rightarrow}\sigma_{w}^{2}\Lambda^{l-1}_{ST_{lm}}$
and then $H\rightarrow\infty$ and by the Law of Large Numbers
$\displaystyle\frac{\sigma_{w}^{2}}{H}\sum_{h,h^{\prime}}^{H}\sum_{ST}\sum_{lm}\sigma_{1}(L^{l,h})_{is}\sigma_{1}(L^{l,h^{\prime}})_{tj}\Lambda_{ST_{lm}}\overset{P}{\rightarrow}\sigma_{w}^{2}\mathbb{E}\bigl{[}\sum_{ST}\sum_{lm}\sigma_{1}(L^{l,h})_{is}\sigma_{1}(L^{l,h^{\prime}})_{tj}\Lambda_{ST_{lm}}\bigr{]}$
the righthandside is nothing else than
$\displaystyle\sigma_{w}^{2}\mathbb{E}\bigl{[}\sum_{ST}\sum_{lm}\sigma_{1}(L^{l,h})_{is}\sigma_{1}(L^{l,h^{\prime}})_{tj}\Lambda_{ST_{lm}}\bigr{]}=\sigma_{w}^{2}\sum_{st}^{n}\mathbb{E}\bigl{[}\sigma_{1}(L^{l,h})_{is}\sigma_{1}(L^{(l,h^{\prime})})_{tj}\bigr{]}\Lambda^{l-1}_{st}=\sigma_{w}^{2}\sum_{st}^{n}\Lambda^{l-1}_{st}\psi(\Lambda^{l-1})_{IJ_{st}}$
$\displaystyle\implies\mathbb{E}\bigl{[}\operatorname{vec}(F^{l})\operatorname{vec}(F^{l})^{T}\bigr{]}\rightarrow\operatorname{\mathrm{batchm}}(\sigma_{w}^{2}\Lambda^{l-1},\psi(\Lambda^{l-1}))$

For a rigourous treatement and the case of
min$\\{H,d_{l-1}\\}\rightarrow\infty$ the proof can be concluded using [Yang,
2019, Mastertheorem] or [Hron et al., 2020, Theorem 3, Part II)]. ∎

####  A.4.2 Neural Tangent Kernel (Theorem 3.8)

See 3.8

###### Proof.

As a reminder the NTK of depth $l$ is

$\displaystyle\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\theta}\left(\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\theta}\right)^{T}$

for parameters $\theta$. We when the width of the hidden layers goes to
infinity this expression converges in probability to $\Theta^{l}\otimes
I_{d_{l}}$. Now to the proof, first realize that:

$\displaystyle\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\theta}\left(\frac{\partial\operatorname{vec}(F^{l}(\theta,X))}{\partial\theta}\right)^{T}=\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(W^{l})}\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(W^{l})}\right)^{T}+\frac{1}{H}\sum_{h}^{H}\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(c^{l,h})}\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(c^{l,h})}\right)^{T}$
$\displaystyle+\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(G^{l-1})}\frac{\partial\operatorname{vec}(G^{l-1})}{\partial\operatorname{vec}(F^{l-1})}\frac{\partial\operatorname{vec}(F^{l-1}(\theta,X))}{\partial\theta}\left(\frac{\partial\operatorname{vec}(F^{l-1}(\theta,X))}{\partial\theta}\right)^{T}\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(G^{l-1})}\frac{\partial\operatorname{vec}(G^{l-1})}{\partial\operatorname{vec}(F^{l-1})}\right)^{T}$

Each of the terms is simplified and probability in convergence is proven for
min$\\{d_{l-1},H\\}\to\infty$. ∎

######  Lemma A.3.

$\displaystyle\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(W^{l})}\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(W^{l})}\right)^{T}\overset{P}{\longrightarrow}\operatorname{\mathrm{batchm}}\left(\sigma_{w}^{2}\Lambda^{l-1},\psi(\Lambda^{l-1})\right)\otimes
I_{d_{l}}$

###### Proof.

$\displaystyle\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(W^{l})}\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(W^{l})}\right)^{T}=\frac{\sigma_{w}^{2}}{d_{l-1}}\left[F^{l1},...,F^{lH}\right]\left[F^{l1},...,F^{lH}\right]^{T}\otimes
I_{d_{l}}$
$\displaystyle\frac{\sigma_{w}^{2}}{Hd_{l-1}}\left(\left[F^{l1},...,F^{lH}\right]\left[F^{l1},...,F^{lH}\right]^{T}\right)=\sigma_{w}^{2}\sum_{h}^{H}\frac{1}{Hd_{l-1}}\sigma_{1}(L^{l,h})G^{l-1^{T}}G^{l-1}\sigma_{1}(L^{l,h})$
We are going to focus on elements $i,j$ and rewrite it
$\displaystyle\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(W^{l})}\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(W^{l})}\right)^{T}\right)_{ij}=\frac{\sigma_{w}^{2}}{H}\sum_{h}^{H}\sum_{l,s}^{n}\sigma_{1}(L^{l,h})_{is}\sigma_{1}(L^{l,h})_{tj}\frac{\left(G^{l-1^{T}}G^{l-1}\right)_{st}}{d_{l-1}}$
$\displaystyle\overset{P}{\longrightarrow}\sigma_{w}^{2}\sum_{st}^{n}\mathbb{E}\bigl{[}\sigma_{1}(L^{l,h})_{is}\sigma_{1}(L^{l,h})_{tj}\bigr{]}\Lambda^{l-1}_{st}=\sigma_{w}^{2}\sum_{st}^{n}\Lambda^{l-1}_{st}\psi(\Lambda^{l-1})_{IJ_{st}}$

To prove convergence in probability (last step). for for
min$\\{d_{l-1},H\\}\rightarrow\infty$ one can apply [Hron et al., 2020, Lemma
19] or [Yang, 2020, Mastertheorem]. ∎

######  Lemma A.4.

$\displaystyle\sum_{h}^{H}\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(c^{l,h})}\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(c^{l,h})}\right)^{T}\overset{P}{\longrightarrow}\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\Lambda^{l-1},\sigma_{c}^{2}\left(\gamma_{A}(\Lambda^{l-1})\odot\dot{\psi}(\Lambda^{l-1})\right)\right]\otimes
I_{d_{l}}$

###### Proof.

$\displaystyle\frac{1}{H}\sum_{h}^{H}\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(\sigma_{1}(L^{l,h}))}\frac{\partial\operatorname{vec}(\sigma_{1}(L^{l,h})}{\partial\operatorname{vec}(L^{l,h})}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\right)\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(\sigma_{1}(L^{l,h}))}\frac{\partial\operatorname{vec}(\sigma_{1}(L^{l,h})}{\partial\operatorname{vec}(L^{l,h})}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\right)^{T}=$
$\displaystyle\frac{1}{H}\sum_{h}^{H}\left(\left(I_{n}\otimes\frac{\sigma_{w}}{\sqrt{d_{l-1}}}W^{l,h}G^{l}\right)\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\left(\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\right)^{T}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}\left(I_{n}\otimes\frac{\sigma_{w}}{\sqrt{d_{l-1}}}G^{l^{T}}W^{l,h^{T}}\right)\right)$
Focusing on block indices $I,J$
$\displaystyle\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(c^{l,h})}\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(c^{l,h})}\right)^{T}\right)_{IJ}=\frac{\sigma_{w}^{2}}{Hd_{l-1}}\sum_{h}^{H}W^{l,h}G^{l}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II}\biggl{[}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\left(\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\right)^{T}\biggr{]}_{IJ}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{JJ}G^{l-1^{T}}W^{l,h^{T}}$ Focusing on
elements with indices $u,v$ of $I,J$
$\displaystyle\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(c^{l,h})}\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(c^{l,h})}\right)^{T}\right)_{IJ_{uv}}=\sigma^{2}_{w}\frac{1}{Hd_{l-1}}\sum_{h}^{H}\sum_{st}^{n}\biggr{[}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\left(\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\right)^{T}\biggl{]}_{IJ_{st}}\langle
W^{l,h}_{u},G^{l-1}_{\cdot s}\rangle\langle W^{l,h}_{v},G^{l-1}_{\cdot
t}\rangle\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II_{ss}}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{JJ_{tt}}$
$\displaystyle=\sigma^{2}_{w}\frac{1}{H}\sum_{h}^{H}\sum_{st}^{n}\biggr{[}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\left(\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\right)^{T}\biggl{]}_{IJ_{st}}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II_{ss}}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{JJ_{tt}}\frac{1}{d_{l-1}}\sum_{ab}^{d_{l-1}}W^{l,h}_{ua}W^{l,h}_{vb}G^{l-1}_{as}G^{l-1}_{bt}$
as a reminder
$\displaystyle\biggr{[}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\left(\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(c^{l,h})}\right)^{T}\biggl{]}_{IJ_{st}}=\frac{\sigma_{c}^{2}}{2d_{l-1}}\langle\hat{A}\operatorname{concat}((\mathbf{1}_{n}\otimes
G^{T}),(G^{T}\otimes\mathbf{1}_{n}))_{I_{s}},\hat{A}\operatorname{concat}((\mathbf{1}_{n}\otimes
G^{T}),(G^{T}\otimes\mathbf{1}_{n}))_{J_{t}}\rangle$
$\displaystyle=\sigma_{c}^{2}\hat{A}_{II_{ss}}\hat{A}_{JJ_{tt}}\frac{\langle
G_{\cdot I_{s}},G_{\cdot J_{t}}\rangle+\langle G_{\cdot I_{s}},G_{\cdot
J_{t}}\rangle}{2d_{l-1}}$
$\displaystyle=\sigma^{2}_{w}\sigma_{c}^{2}\frac{1}{H}\sum_{h}^{H}\sum_{st}^{n}\hat{A}_{II_{ss}}\hat{A}_{JJ_{tt}}\frac{\langle
G_{\cdot I_{s}},G_{\cdot J_{t}}\rangle+\langle G_{\cdot I_{s}},G_{\cdot
J_{t}}\rangle}{2d_{l-1}}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II_{ss}}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{JJ_{tt}}\frac{1}{d_{l-1}}\sum_{ab}^{d_{l-1}}W^{l,h}_{ua}W^{l,h}_{vb}G^{l-1}_{as}G^{l-1}_{bt}$
converging in probability for $\text{min}\\{d_{l-1},H\\}\rightarrow\infty$
$\displaystyle=\delta_{uv}\sigma^{2}_{w}\sum_{st}^{n}(J_{A}\begin{pmatrix}\Lambda^{l-1}&\Lambda^{l-1}\\\
\Lambda^{l-1}&\Lambda^{l-1}\\\
\end{pmatrix}J_{A}^{T})_{IJ_{st}}\dot{\psi}(\Lambda^{l-1})_{IJ_{st}}\dot{\Lambda}^{l-1}_{st}$
using our previously defined shorthand definition
$\gamma_{A}(\Omega):=J_{A}\begin{pmatrix}\Omega&\Omega\\\ \Omega&\Omega\\\
\end{pmatrix}J_{A}^{T}$ we end up with
$\displaystyle=\delta_{uv}\sigma^{2}_{w}\sum_{st}^{n}\gamma_{A}(\Lambda^{l-1})_{IJ_{st}}\dot{\psi}(\Lambda^{l-1})_{IJ_{st}}\Lambda^{l-1}_{st}$

Similar to the previous lemma to conclude convergence in probability for
$\text{min}\\{d_{l-1},H\\}\to\infty$ one can use [Hron et al., 2020, Lemma 21]
or [Yang, 2020, Master Theorem]. ∎

######  Lemma A.5.

$\displaystyle\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(G^{l-1})}\frac{\partial\operatorname{vec}(G^{l-1})}{\partial\operatorname{vec}(F^{l-1})}\left(\Theta^{l-1}\otimes
I_{d_{l-1}}\right)\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(G^{l-1})}\frac{\partial\operatorname{vec}(G^{l-1})}{\partial\operatorname{vec}(F^{l-1})}\right)^{T}$
$\displaystyle\overset{P}{\longrightarrow}$
$\displaystyle\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\Lambda^{l-1},\sigma^{2}_{c}\left(\gamma_{A}(\Theta^{l-1}\odot\dot{\Lambda}^{l-1})\odot\dot{\psi}(\Lambda^{l-1})\right)\right]+\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\left(\Theta^{l-1}\odot\dot{\Lambda}^{l-1}\right),\psi(\Lambda^{l-1})\right]$

###### Proof.

$\displaystyle\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(G^{l-1})}\frac{\partial\operatorname{vec}(G^{l-1})}{\partial\operatorname{vec}(F^{l-1})}\right)\left(\Theta^{l-1}\otimes
I_{d_{l-1}}\right)\left(\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(G^{l-1})}\frac{\partial\operatorname{vec}(G^{l-1})}{\partial\operatorname{vec}(F^{l-1})}\right)^{T}=$
$\displaystyle\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(G^{l-1})}\hat{\Theta}^{l}\frac{\partial\operatorname{vec}(F^{l})}{\partial\operatorname{vec}(G^{l-1})}^{T}$
$\hat{\Theta}^{l}_{IJ}:=\Theta^{l-1}_{ij}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h^{\prime}}_{JJ}$, similar to [Hron et al.,
2020, Section B2.2 Indirect Contributions]. Also note that for
$d_{l-1}\rightarrow\infty$,
$\hat{\Theta}^{l}\overset{P}{\rightarrow}(\Theta^{l-1}\odot\dot{\Lambda}^{l-1})\otimes
I_{d_{l-1}}$. (see for example [Yang, 2019, Master Theorem]). Now continuing
with the simplification.
$\displaystyle\frac{1}{H}\sum_{h,h^{\prime}}^{H}\biggr{[}\left(I_{n}\otimes\left(\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h}G^{l-1}\right)\right)\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}+\left(\sigma_{1}(L^{l,h})\otimes\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h}\right)\biggl{]}$
$\displaystyle\cdot\
\hat{\Theta}^{l}\biggr{[}\left(I_{n}\otimes\left(\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h^{\prime}}G^{l-1}\right)\right)\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h^{\prime}}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}+\left(\sigma_{1}(L^{l,h^{\prime}})\otimes\frac{\sigma_{w}}{\sqrt{d_{l-1}}}W^{l,h^{\prime}}\right)\biggl{]}^{T}$
$\displaystyle=\frac{1}{H}\sum_{h,h^{\prime}}^{H}\left(A^{l,h,h^{\prime}}+B^{l,h,h^{\prime}}+C^{l,h,h^{\prime}}+C^{l,h,h^{\prime
T}}\right)$

Now we will simplify this final expression using the following lemmas to
conclude this proof. ∎

######  Lemma A.6.

$\displaystyle\frac{1}{H}\sum_{h,h^{\prime}}^{H}A^{l,h,h^{\prime}}\overset{P}{\rightarrow}\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\Lambda^{l-1},\sigma^{2}_{c}\left(\gamma_{A}(\Theta^{l-1}\odot\dot{\Lambda}^{l-1})\odot\dot{\psi}(\Lambda^{l-1})\right)\right]\otimes
I_{d_{l}}$

###### Proof.

$\displaystyle
A^{l,h,h^{\prime}}=\biggl{[}\left(I_{n}\otimes\left(\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h}G^{l-1}\right)\right)\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\biggr{]}\hat{\Theta}^{l}\biggl{[}\left(I_{n}\otimes\left(\frac{\sigma_{w}}{\sqrt{d_{l-1}}}W^{l,h^{\prime}}G^{l-1}\right)\right)\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h^{\prime}}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\biggr{]}^{T}$
$\displaystyle=\left(I_{n}\otimes\left(\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h}G^{l-1}\right)\right)\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\hat{\Theta}^{l}\left(\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\right)^{T}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h^{\prime}}\left(I_{n}\otimes\left(\frac{\sigma_{w}}{\sqrt{d_{l-1}}}G^{l-1^{T}}W^{l,h^{\prime
T}}\right)\right)$ focusing on block indices $I,J$ $\displaystyle
A^{l,h,h^{\prime}}_{IJ}=\frac{\sigma_{w}^{2}}{d_{l-1}}W^{l,h}G^{l-1}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II}\left[\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\hat{\Theta}^{l}\left(\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\right)^{T}\right]_{IJ}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h^{\prime}}_{JJ}G^{l-1^{T}}W^{l,h^{\prime T}}$
$\displaystyle\left[\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\hat{\Theta}^{l}\left(\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\right)^{T}\right]_{IJ_{st}}=\frac{\sigma_{c}^{2}}{2d_{l-1}}\tilde{A}_{II_{ss}}\tilde{A}_{JJ_{tt}}\left(c_{1}^{T}\hat{\Theta}^{l}_{st}c_{1}+c_{1}^{T}\hat{\Theta}^{l}_{sJ}c_{2}+c_{2}^{T}\hat{\Theta}^{l}_{It}c_{1}+c_{2}^{T}\hat{\Theta}^{l}_{IJ}c_{2}\right)$
with $\hat{\Theta}^{l}_{st}\in\mathbb{R}^{d_{l-1}\times d_{l-1}}$.Focusing on
element indices $u,v$ $\displaystyle
A^{l,h,h^{\prime}}_{IJ_{uv}}=\frac{\sigma^{2}_{w}}{d_{l-1}}\sum_{st}\left[\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\hat{\Theta}^{l}\left(\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\right)^{T}\right]_{IJ_{st}}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II_{ss}}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h^{\prime}}_{JJ_{tt}}\langle
W_{u},G^{l-1}_{\cdot s}\rangle\langle W_{v},G^{l-1}_{\cdot t}\rangle$
$\displaystyle
A^{l,h,h^{\prime}}_{IJ_{uv}}=\frac{\sigma^{2}_{w}\sigma^{2}_{c}}{2d_{l-1}^{2}}\sum_{st}\tilde{A}_{II_{ss}}\tilde{A}_{JJ_{tt}}\left(c_{1}^{T}\hat{\Theta}^{l}_{st}c_{1}+c_{1}^{T}\hat{\Theta}^{l}_{sJ}c_{2}+c_{2}^{T}\hat{\Theta}^{l}_{It}c_{1}+c_{2}^{T}\hat{\Theta}^{l}_{IJ}c_{2}\right)\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II_{ss}}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h^{\prime}}_{JJ_{tt}}\langle
W_{u},G^{l-1}_{\cdot s}\rangle\langle W_{v},G^{l-1}_{\cdot t}\rangle$ follows
the previous ideas and the the fact that
$\hat{\Theta}^{l}\overset{P}{\rightarrow}(\Theta^{l-1}\odot\dot{\Lambda}^{l-1})\otimes
I_{d_{l-1}}$ as in A.5 Convergencence in probability for
$\text{min}\\{d_{l-1},H\\}\rightarrow\infty$
$\displaystyle\frac{1}{H}\sum_{h,h^{\prime}}A^{l,h,h^{\prime}}_{IJ_{uv}}\overset{P}{\longrightarrow}\delta_{uv}\delta_{hh^{\prime}}\sum_{st}\tilde{A}_{II_{ss}}\tilde{A}_{JJ_{tt}}\dot{\Lambda}^{l-1}_{IJ_{st}}\Theta^{l-1}_{st}\Theta^{l-1}_{ij}\Lambda^{l-1}_{st}$

which can be conducted using [Yang, 2020, Master Theorem] or [Hron et al.,
2020, Lemma 23]. ∎

######  Lemma A.7.

$\displaystyle\frac{1}{H}\sum_{h,h^{\prime}}^{H}B^{l,h,h^{\prime}}\overset{P}{\rightarrow}\operatorname{\mathrm{batchm}}\left[\sigma_{w}^{2}\left(\Theta^{l-1}\odot\dot{\Lambda}^{l-1}\right),\psi(\Lambda^{l-1})\right]\otimes
I_{d_{l-1}}$

###### Proof.

$\displaystyle
B^{l,h,h^{\prime}}=\left(\sigma_{1}(L^{l,h})\otimes\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h}\right)\hat{\Theta}^{l}\left(\sigma_{1}(L^{l,h^{\prime}})\otimes\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h^{\prime}}\right)^{T}$
$\displaystyle
B^{l,h,h^{\prime}}_{IJ}=\sum_{ST}\left(\sigma_{1}(L^{l,h})\otimes
I_{d_{l}}\right)_{IS}\left[\left(I_{n}\otimes\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h}\right)\hat{\Theta}^{l}\left(I_{d_{n}}\otimes\frac{\sigma_{w}}{\sqrt{d_{l}}}W^{l,h^{\prime
T}}\right)\right]_{ST}\left(\sigma_{1}(L^{l,h^{\prime}})\otimes
I_{d_{l}}\right)_{TJ}$ $\displaystyle
B^{l,h,h^{\prime}}_{IJ}=\sum_{ST}\sigma_{1}(L^{l,h})_{is}\frac{\sigma_{w}^{2}}{d_{l}}W^{l,h^{\prime}}\hat{\Theta}^{l}_{ST}W^{l,h^{\prime
T}}\sigma_{1}(L^{l,h^{\prime}})_{tj}$ finally proof in convergence
$\displaystyle\frac{1}{H}\sum_{h}^{H}B^{l,h,h^{\prime}}_{IJ}\overset{P}{\rightarrow}\sum_{st}^{n}\mathbb{E}\bigl{[}\sigma_{1}(L^{l,h})_{is}\sigma_{1}(L^{l,h^{\prime}})_{tj}\bigr{]}\Theta^{l-1}_{st}\dot{\Lambda}^{l-1}_{st}=\sum_{st}^{n}\psi(\Lambda^{l-1})_{IJ_{st}}\Theta^{l-1}_{st}\dot{\Lambda}^{l-1}_{st}$

To proof convergence in probability for min$\\{d_{l-1},H\\}\to\infty$ on can
use [Yang, 2020, Master Theorem] or [Hron et al., 2020, Lemma 22]. ∎

######  Lemma A.8.

$\displaystyle\frac{1}{H}\sum_{h,h^{\prime}}^{H}C^{l,h,h^{\prime}}\overset{P}{\rightarrow}0$

###### Proof.

$\displaystyle\frac{1}{H}\sum_{h,h^{\prime}}^{H}C^{l,h,h^{\prime}}=\frac{1}{H}\sum_{h,h^{\prime}}^{H}\left(I_{n}\otimes\left(\frac{\sigma_{w}}{\sqrt{2d_{l}}}W^{l,h}G^{l-1}\right)\right)\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\hat{\Theta}^{l}\left(\sigma_{1}(L^{l,h^{\prime}})\otimes\frac{\sigma_{w}}{\sqrt{d_{l-1}}}W^{l,h^{\prime}}\right)^{T}$
focusing on block indices $IJ$
$\displaystyle\frac{1}{H}\sum_{h,h^{\prime}}^{H}C^{l,h,h^{\prime}}_{IJ}=\frac{1}{H}\sum_{h,h^{\prime}}^{H}\frac{\sigma_{w}}{\sqrt{2d_{l}}}W^{l,h}G^{l-1}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II}\left(\frac{\partial\operatorname{vec}(L^{l,h})}{\partial\operatorname{vec}(G^{h-1})}\hat{\Theta}^{l}\right)_{I}\left((\sigma_{1}(L^{l,h^{\prime}})_{j})^{T}\otimes\frac{\sigma_{w}}{\sqrt{d_{l-1}}}W^{l,h^{\prime
T}}\right)$ focusing on indices $uv$
$\displaystyle\frac{1}{H}\sum_{h,h^{\prime}}^{H}C^{l,h,h^{\prime}}_{IJ_{uv}}=\frac{\sigma_{w}^{2}\sigma_{c}}{\sqrt{2}Hd_{l-1}^{\frac{3}{2}}}\sum_{h,h^{\prime}}^{H}\sum_{st}W_{u}^{l,h}G^{l-1}_{\cdot
s}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II_{ss}}\tilde{A}_{II_{ss}}(c_{1}^{T}\hat{\Theta}^{l}_{s}+c_{2}^{T}\hat{\Theta}^{l}_{I})\left((\sigma_{1}(L^{l,h^{\prime}})_{j})^{T}\otimes\frac{\sigma_{w}}{\sqrt{d_{l-1}}}(W^{l,h^{\prime}}_{v})^{T}\right)$
$\displaystyle=\frac{\sigma_{w}^{2}\sigma_{c}}{\sqrt{2}Hd_{l-1}^{\frac{3}{2}}}\sum_{h,h^{\prime}}^{H}\sum_{stz}\sigma_{1}(L^{l,h^{\prime}})_{[j,\lfloor
t\bmod n\rfloor+1]}W_{uz}^{l,h}G^{l-1}_{zs}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II_{ss}}\tilde{A}_{II_{ss}}(c_{1}^{T}\hat{\Theta}^{l}_{st}+c_{2}^{T}\hat{\Theta}^{l}_{It})W^{l,h^{\prime
T}}_{v}$ Define $\nu(t):=\lfloor t\bmod n\rfloor+1$
$\displaystyle\frac{\sigma_{w}^{2}\sigma_{c}}{\sqrt{2}Hd_{l-1}^{\frac{3}{2}}}\sum_{h,h^{\prime}}^{H}\sum_{stzlm}\sigma_{1}(L^{l,h^{\prime}})_{j\nu(j)}W_{uz}^{l,h}G^{l-1}_{zs}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h}_{II_{ss}}\tilde{A}_{II_{ss}}\left(c_{1l}W^{l,h^{\prime}}_{vm}\hat{\Theta}^{l}_{st_{lm}}+c_{2l}W^{l,h^{\prime}}_{vm}\hat{\Theta}^{l}_{It_{lm}}\right)$

Using Chebyshevs Inequality

$\displaystyle\mathbb{P}\left(|S-\mathbb{E}S|\geq\delta\right)\leq\frac{\mathbb{E}\bigl{[}S^{2}\bigr{]}-\mathbb{E}\bigl{[}S\bigr{]}^{2}}{\delta^{2}}$

we show that $\mathbb{E}\bigl{[}S^{2}\bigr{]}=\mathbb{E}\bigl{[}S^{2}\bigr{]}$
(and $\mathbb{E}\bigl{[}S\bigr{]}=0$) for min$\\{H,d_{l-1}\\}\to\infty$ to
finish the proof.
The cross terms where Expectation is taken of $c_{1}$ and $c_{2}$ are zero.
Defining
$\Gamma_{h_{1}h_{2}h^{\prime}_{1}h^{\prime}_{2}s_{1}s_{2}}:=\sigma_{1}(L^{l,h^{\prime}_{1}})_{j\nu(t_{1})}\sigma_{1}(L^{l,h^{\prime}_{2}})_{j\nu(t_{2})}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h_{1}}_{II_{s_{1}s_{1}}}\overset{\scriptscriptstyle
1}{\Sigma}\vphantom{\sigma}^{l,h_{2}}_{II_{s_{2}s_{2}}}(L^{l,h^{\prime}_{2}})_{j\nu(t_{2})}\tilde{A}_{II_{s_{1}s_{1}}}\tilde{A}_{II_{s_{2}s_{2}}}$

$\displaystyle\mathbb{E}\biggr{[}\bigl{(}\frac{1}{H}\sum_{h,h^{\prime}}^{H}C^{l,h,h^{\prime}}_{IJ_{uv}}\bigr{)}^{2}\biggl{]}=$
$\displaystyle\frac{\sigma_{w}^{4}\sigma_{c}^{2}}{2H^{2}d_{l-1}^{3}}\biggl{(}\mathbb{E}\biggl{[}\sum_{\begin{subarray}{c}h_{1}h_{2}\\\
h^{\prime}_{1}h^{\prime}_{2}\\\ s_{1}s_{2}\\\ t_{1}t_{2}\\\ z_{1}z_{2}\\\
l_{1}l_{2}\\\
m_{1}m_{2}\end{subarray}}\Gamma_{h_{1}h_{2}h^{\prime}_{1}h^{\prime}_{2}s_{1}s_{2}}W_{uz_{1}}^{l,h_{1}}G^{l-1}_{z_{1}s_{1}}W_{uz_{2}}^{l,h_{2}}G^{l-1}_{z_{2}s_{2}}c_{1l_{1}}W^{l,h^{\prime}_{1}}_{vm_{1}}\hat{\Theta}^{l}_{s_{1}t_{1_{l_{1}m_{1}}}}c_{1l_{2}}W^{l,h^{\prime}_{2}}_{vm_{2}}\hat{\Theta}^{l}_{s_{2}t_{2_{l_{2}m_{2}}}}\biggr{]}$
$\displaystyle+\mathbb{E}\biggl{[}\sum_{\begin{subarray}{c}h_{1}h_{2}\\\
h^{\prime}_{1}h^{\prime}_{2}\\\ s_{1}s_{2}\\\ t_{1}t_{2}\\\ z_{1}z_{2}\\\
l_{1}l_{2}\\\
m_{1}m_{2}\end{subarray}}\Gamma_{h_{1}h_{2}h^{\prime}_{1}h^{\prime}_{2}s_{1}s_{2}}W_{uz_{1}}^{l,h_{1}}G^{l-1}_{z_{1}s_{1}}W_{uz_{2}}^{l,h_{2}}G^{l-1}_{z_{2}s_{2}}c_{2l_{1}}W^{l,h^{\prime}_{1}}_{vm_{1}}\hat{\Theta}^{l}_{It_{1_{l_{1}m_{1}}}}c_{2l_{2}}W^{l,h^{\prime}_{2}}_{vm_{2}}\hat{\Theta}^{l}_{It_{2_{l_{2}m_{2}}}}\biggr{]}\biggl{)}$

By the boundedness of all components of $\Gamma$ (boundedness in the sense
that for growing min$\\{H,d_{l-1}\\}\rightarrow\infty$ the expression is
bounded by a constant not depending on $d_{l-1}$ or $H$) and Hölderlins
Inequality it follow that $\Gamma$ is bounded by a constant only depending
polynomially on X.

$\displaystyle\frac{\zeta\sigma_{w}^{4}\sigma_{c}^{2}}{2H^{2}d_{l-1}^{3}}\mathbb{E}\biggl{[}\sum_{\begin{subarray}{c}h_{1}h_{2}\\\
h^{\prime}_{1}h^{\prime}_{2}\\\ s_{1}s_{2}\\\ t_{1}t_{2}\\\ z_{1}z_{2}\\\
l_{1}l_{2}\\\
m_{1}m_{2}\end{subarray}}W_{uz_{1}}^{l,h_{1}}G^{l-1}_{z_{1}s_{1}}W_{uz_{2}}^{l,h_{2}}G^{l-1}_{z_{2}s_{2}}c_{1l_{1}}W^{l,h^{\prime}_{1}}_{vm_{1}}\hat{\Theta}^{l}_{s_{1}t_{1_{l_{1}m_{1}}}}c_{1l_{2}}W^{l,h^{\prime}_{2}}_{vm_{2}}\hat{\Theta}^{l}_{s_{2}t_{2_{l_{2}m_{2}}}}\biggr{]}$

Note that for
min$\\{d_{l-1},H\\}\rightarrow\infty,\hat{\Theta}^{l}_{IJ_{lm}}\overset{P}{\longrightarrow}0$
for $l\neq m$ (from Lemma A.5). Therefore

$\displaystyle\frac{\zeta\sigma_{w}^{4}\sigma_{c}^{2}}{2H^{2}d_{l-1}^{3}}\mathbb{E}\biggl{[}\sum_{\begin{subarray}{c}h_{1}h_{2}\\\
h^{\prime}_{1}h^{\prime}_{2}\\\ s_{1}s_{2}\\\ t_{1}t_{2}\\\ z_{1}z_{2}\\\ l\\\
m\end{subarray}}W_{uz_{1}}^{l,h_{1}}G^{l-1}_{z_{1}s_{1}}W_{uz_{2}}^{l,h_{2}}G^{l-1}_{z_{2}s_{2}}c_{1l}W^{l,h^{\prime}_{1}}_{vl}\hat{\Theta}^{l}_{s_{1}t_{1_{ll}}}c_{1m}W^{l,h^{\prime}_{2}}_{vm}\hat{\Theta}^{l}_{s_{2}t_{2_{mm}}}\biggr{]}$

The case $u\neq v$

$\displaystyle\frac{\zeta\sigma_{w}^{4}\sigma_{c}^{2}}{2H^{2}d_{l-1}^{3}}\mathbb{E}\biggl{[}\sum_{\begin{subarray}{c}h\\\
h^{\prime}\\\ s_{1}s_{2}\\\ t_{1}t_{2}\\\ z\\\
l\end{subarray}}W_{uz}^{l,h}G^{l-1}_{zs_{1}}W_{uz}^{l,h}G^{l-1}_{zs_{2}}c_{1l}c_{1l}W^{l,h^{\prime}}_{vl}W^{l,h^{\prime}}_{vl}\hat{\Theta}^{l}_{s_{1}t_{1_{ll}}}\hat{\Theta}^{l}_{s_{2}t_{2_{ll}}}\biggr{]}\overset{\text{min$\\{d_{l-1},H\\}\rightarrow\infty$}}{=}0$

for min$\\{d_{l-1},H\\}\rightarrow\infty$, $h,h^{\prime},z,l$ are the indices
that go to infinity, but ${H^{2}d_{l-1}^{3}}$ is growing faster than
$h,h^{\prime},z,l$ and therefore the expression is zero. The argument can be
repeated for the righthandside to conclude for the case $u\neq v$.
The case $u=v$

$\displaystyle\frac{\zeta\sigma_{w}^{4}\sigma_{c}^{2}}{2H^{2}d_{l-1}^{3}}\mathbb{E}\biggl{[}\sum_{\begin{subarray}{c}h_{1}h_{2}\\\
h^{\prime}_{1}h^{\prime}_{2}\\\ s_{1}s_{2}\\\ t_{1}t_{2}\\\ z_{1}z_{2}\\\ l\\\
m\end{subarray}}W_{uz_{1}}^{l,h_{1}}G^{l-1}_{z_{1}s_{1}}W_{uz_{2}}^{l,h_{2}}G^{l-1}_{z_{2}s_{2}}c_{1l}W^{l,h^{\prime}_{1}}_{ul}\hat{\Theta}^{l}_{s_{1}t_{1_{ll}}}c_{1m}W^{l,h^{\prime}_{2}}_{um}\hat{\Theta}^{l}_{s_{2}t_{2_{mm}}}\biggr{]}$
$\displaystyle=\frac{\zeta\sigma_{w}^{4}\sigma_{c}^{2}}{2H^{2}d_{l-1}^{3}}\mathbb{E}\biggl{[}\sum_{\begin{subarray}{c}h_{1}h_{2}\\\
h^{\prime}_{1}h^{\prime}_{2}\\\ s_{1}s_{2}\\\ t_{1}t_{2}\\\ z_{1}z_{2}\\\ l\\\
m\end{subarray}}W^{l,h^{\prime}_{1}}_{ul}W^{l,h^{\prime}_{2}}_{um}W_{uz_{1}}^{l,h_{1}}W_{uz_{2}}^{l,h_{2}}c_{1l}c_{1m}G^{l-1}_{z_{1}s_{1}}G^{l-1}_{z_{2}s_{2}}\hat{\Theta}^{l}_{s_{1}t_{1_{ll}}}\hat{\Theta}^{l}_{s_{2}t_{2_{mm}}}\biggr{]}$

The sum over $h_{1},h_{2},h^{\prime}_{1},h^{\prime}_{2}$ can be split over:

  1. 1.

$h^{\prime}_{1}=h^{\prime}_{2}$ and $h_{1}=h_{2}$ with $l=m$ and $z_{1}=z_{2}$

  2. 2.

$h^{\prime}_{1}=h_{1}$ and $h^{\prime}_{2}=h_{2}$ with $l=z_{1}$ and $m=z_{2}$

  3. 3.

$h^{\prime}_{1}=h_{2}$ and $h^{\prime}_{2}=h_{1}$ with $l=z_{2}$ and $m=z_{1}$

With each case being a sum of which four indices grow to infinity. And
therefore again the same argument holds. ∎

## References

  * Kipf and Welling [2017] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In International Conference on Learning Representations, 2017.  URL https://openreview.net/forum?id=SJU4ayYgl.
  * Veličković et al. [2018] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph attention networks.  In International Conference on Learning Representations, 2018.  URL https://openreview.net/forum?id=rJXMpikCZ.
  * Shi et al. [2021] Yunsheng Shi, Zhengjie Huang, shikun feng, Hui Zhong, Wenjin Wang, and Yu Sun.  Masked label prediction: Unified message passing model for semi-supervised classification, 2021.  URL https://openreview.net/forum?id=B9t708KMr9d.
  * Hamilton et al. [2017] William L. Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1024–1034, 2017.  URL https://proceedings.neurips.cc/paper/2017/hash/5dd9db5e033da9c6fb5ba83c7a7ebea9-Abstract.html.
  * Kipf and Welling [2016] Thomas N. Kipf and Max Welling.  Variational graph auto-encoders.  CoRR, abs/1611.07308, 2016.  URL http://arxiv.org/abs/1611.07308.