Graph Neural Network-Inspired Kernels for Gaussian Processes in Semi-Supervised Learning
Authors: Zehao Niu
Mihai Anitescu
Jie Chen
Venue: ICLR 2023 poster (2023)
Keywords: graph neural network
Gaussian process
semi-supervised learning

Abstract: Gaussian processes (GPs) are an attractive class of machine learning models because of their simplicity and flexibility as building blocks of more complex Bayesian models. Meanwhile, graph neural networks (GNNs) emerged recently as a promising class of models for graph-structured data in semi-supervised learning and beyond. Their competitive performance is often attributed to a proper capturing of the graph inductive bias. In this work, we introduce this inductive bias into GPs to improve their predictive performance for graph-structured data. We show that a prominent example of GNNs, the graph convolutional network, is equivalent to some GP when its layers are infinitely wide; and we analyze the kernel universality and the limiting behavior in depth. We further present a programmable procedure to compose covariance kernels inspired by this equivalence and derive example kernels corresponding to several interesting members of the GNN family. We also propose a computationally efficient approximation of the covariance matrix for scalable posterior inference with large-scale data. We demonstrate that these graph-based kernels lead to competitive classification and regression performance, as well as advantages in computation time, compared with the respective GNNs.

Published as a conference paper at ICLR 2023
GRAPH NEURAL NETWORK-INSPIRED KERNELS FOR GAUSSIAN PROCESSES IN SEMI-SUPERVISED LEARN-
ING
Zehao Niu', Mihai Aniteseu 1.2
Jie Chen MIT-IBM Watson Al Lab IBM Research chenjie fecus.eeu.. imm com
University of Chicago, 2 *Argonne National Laboratory niuzehao@uchican .dd anitescuênes. anl gov
ABSTRACT
Gaussian processes (GPs) are an attractive class of machine learning models because of their simplicity and flexibility as building blocks of more complex Bayesian models. Mcanwhile, graph neural networks (GNNs) emerged recently as a promising class of models for graph-structurrd data semi-supervised learn- ing and beyond. Their competitive performance is often attributed to proper capturing of the graph inductive bias. this work, we introduce this inductive bias into GPs to improve their predictive performance for graph-structured data. We show that a prominent example of GNNs, the graph convolutional network, is equivalent to some GP when its layers are infinitely wide; and we analyze the kernel universality and the limiting behavior in depth. We further present a programmable procedure compose covariance kernels inspired by this equiva- lence and derive example kernels corresponding to several interesting members the GNN family. We also propose a computationally efficient approximation of the covariance matrix for scalable posterior inference with large-scale data. We demonstrate that these graph-bant based kernels lead to competitive classification and regression performance, as well as advantages in computation time, compared with the respective GNNs.
INTRODUCTION
Gaussian processes (GPs) (Rasmussen & Williams, 2006) are widely used in machine learning, uncertainty quantification, and global optimization. In the Bayesian setting, a GP serves as prior probability distribution over functions, characterized by mean (often treated zero for simplicity) and a covariance. Conditioned on observed data with a Gaussian likelihood, the random function admits a posterior distribution that is also Gaussian, whose mean is used for prediction and the variance serves as an uncertainty measure. The closed-form posterior allows for exact Bayesian inference, resulting in great attractiveness and wide usage of GPs.
The success of GPs in practice depends on two factors: the observations (training data) and the covariance kernel. We interested in semi-supervised learning, where only a small amount of data is labeled while a large amount of unlabeled data can be used together for training (Zhu) 2008). In recent years, graph neural networks (GNNs) (Zhou al. 2020 Wu al.) 202T) emerged promising class of models for this problem, when the labeled and unlabeled data are connected by graph. The graph structure becomes an important inductive bias that leads the success of GNNs.
This inductive bias inspires us to design GP model under limited observations, by building the graph structure into the covariance kernel.
An intimate relationship between neural networks and GPs is known: neural network with fully connected layers, equipped with a prior probability distribution on the weights and biases, converges to GP when each of its layers is infinitely wide (Lee et al. 2018 de G. Matthews et al. 2018). Such a result is owing to the central limit theorem (Neal 1994 William 1996) and the GP covariance
"To whom correspondence should be addressed.

---

Published as a conference paper at ICLR 2023
can be recursively computed if the weights (and biases) in each layer are iid Gaussian. Similar sults for other architectures, such as convolution layers and residual connections, were subsequently al. 2019).
established in the literature (Novak al. 2019 Garriga-Alons
One focus of this work is to establish similar relationship between GNNs and the limiting GPs. We will derive the covariance kernel that incorporates the graph inductive bias GNNs do. We start with one of the most widely studied GNNs, the graph convolutional network (GCN) (Kipf & Welling. 2017), and analyze the kernel universality well the limiting behavior when the depth also tends to infinity. We then derive covariance kernels from other GNNs by using a programmable procedure that corresponds every building block of a neural network kemnel operation.
Meanwhile, we design efficient computational procedures for posterior inference (i.e., regression and classification). GPs are notoriously difficult scale because of the cubic complexity with re- spect to the number of training data. Benchmark graph datasets used by the GNN literature may contain thousands or even millions of labeled nodes (Hu et al., 20200). The semi-supervised setting worsens the scenario, as the covariance matrix needs to be (recursively) evaluated in full because of the graph convolution operation. We propose a Nyström-like scheme to perform low-rank approx- imations and apply the approximation recursively on each layer, to yield a low-rank kernel matrix. Such a matrix can be computed scalably. We demonstrate through numerical experiments that the GP posterior inference is much faster than training GNN and subsequently performing predictions on the test set.
We summarize the contributions of this work follows:
1. We derive the GP as limit of the GCN when the layer widths tend to infinity and study the kernel universality and the limiting behavior in depth.
2. We propose computational procedure to compute low-rank approximation of the covariance matrix for practical and scalable posterior inference.
3. We present programmable procedure to compose covariance kemnlls and their approximations and show examples corresponding to several interesting members of the GNN family.
4. We conduct comprehensive experiments demonstrate that the GP model performs favorably compared to GNNs in prediction accuracy while being significantly faster in computation.
2 RELATED WORK
has long been observed that GPs are limits of standard neural networks with one hidden layer when the layer width tends to infinity (Neal 1994] Williams] 1996). Recently, renewed interests in the equivalence between GPs and neural networks were extended to deep neural networks (Lee) al., 2018) de G. Matthews et al.
2018) as well modern neural network architectures, such
2019). recurrent networks (Yang) 2019), and residual connec- tions (Garriga-Alonso et al. 2019). The term NNGP (neural network Gaussian process) henceforth emerged under the context of Bayesian deep learning. Besides the fact that an infinite neural network defines a kernel, the training of neural network by using gradient descent also defines kernel- -the neural tangent kernel (NTK)-thl that describes the evolution of the network (Jacot et al. 2018 Lec
as convolution layers (Novak et al.
al. 2019). Library supports Python were developed to automatically construct the NNGP and
NTK kernels based on programming the corresponding neural networks (Novak et al. 2020).
GNNs are neural networks that handle graph-structured data Zhou et al. 2020 Wu et al. 202
They are promising class of models for semi semi-supervised learning. Many GNNs use the message- passing scheme (Gilmer et al., 2017). where neighborhood information is aggregated to update the representation of the center node. Representative examples include GCN (Kipf & Welling 2017).
GraphSAGE (Hamilton et al., 2017), GAT' (Veličković et al. [2088), and GIN (Xu al.] 2019).
is found that the performance of GNNs degrades as they become deep; one approach to mitigating the problem is to insert residual/skip connections, as done by JumpingKnowledge (Xu et al. 2018).
APPNP (Gasteiger et al. 2019), and GCNII (Chen al., 2020).
GP inference is too costly, because it requires the inverse of the N dense kernel matrix. Scalable approaches include low-rank methods, such Nyström approximation (Drineas & Mahoney (005), random features (Rahimi & Recht, (007), and KISS-GP (Wilson & Nickisch] 2013); as well as multi-resolution [Katzfuss|201 and hierarchical methods (Chen et al. 2017 Chen & Stein 2021
2

---

Published as a conference paper at ICLR 2023
Prior efforts integrating graphs into GPs exist. Ng et al. (2018) define GP kernel by combing base kernel with the adjacency matrix; it is related to a special case of our kernels where the network has only one layer and the output admits robust-max likelihood for classification. Hu et al. (2020a) explore a similar route to us, by taking the limit of a GCN, but its exploration less comprehensive because it does not generalize to other GNNs and does not tackle the scalability challenge.
3 GRAPH CONVOLUTIONALL NETWORK AS A GAUSSIAN PROCESS
We start with a few notations used throughout this paper. Let an undirected graph be denoted by = (V.E) E) with N |V] nodes and M = |E| edges. For notational simplicity, we use A R to denote the original graph adjacency matrix or any modified/normalized version of it. Using di to denote the width of the 1-th layer, the layer architecture of GCN reads
x Φ = (AX'"11) + +(1)
(1)
where (I-1 E Nxd-11 and ( E R Nxd, are layer inputs and outputs, respectively; w Rdh-1xd and ((9) E Bixd: are the weights and the biases, respectively; and & is the ReLU activation function. The graph convolutional operator A is symmetric normalization of the graph adjacency matrix with self-loops added (Kipf & Welling 2017).
For ease of exposition, it will be useful to rewrite the matrix notation ①I in element-sums and products. To this end, for node æ, let 2/ (z)
(z) and 2,(") (z) denote the pre- and post-activation value the i-th coordinate in the 1-th layer, respectively. Particularly, an I--laer GCN, xx(0) (xr) the input feature vector and 2(L (2) the output vector. The layer architecture of GCN reads
d-1
1 (x)
(x)
W
(x)
Σ Amoii (o (v), NEV
x. (x) = -02) ((2)(())) (2)
3.1 LIMIT IN THE WIDTH
The following theorem states that when the weights and biases in each layer are iid zero-mean Gaussians, in the limit the layer width, the GCN output 212) is multi-output GP over the index æ.
Theorem 1. Assume d1,.... ........,.1.1 1 to be infinite in succession and let the bias and weight terms be independent with distributions
6 ~ ~(0, wh 00 1= I.,...,,
Then, for each i, the collection {z,0 (x)} over all graph nodes x follows the normal distribution N0, K()), where the covariance matrix K()) can be computed recursively by
c0 = Egg ( (ot (o)(= () )0(2 19)
1= 1= L,
(3)
k(+1)) =f + o ACO
1 --
(4)
All proofs of this paper are given in the appendix. Note that different from usual GP, which is random function defined over connected region of the Euclidean space, here 2(4) is defined over a discrete set of graph nodes. the usual use graph in machine learning, this set finite, such that the function distribution degenerates to multivariate distribution. In semi-supervised learning, the dimension of the distribution, N, is fixed when one conducts transductive learning; but will vary in the inductive setting because the graph will have nodes and edges. One special care of a graph-based GP over a usual GP is that the covariance matrix will need to be recomputed from scratch whenever the graph alters.
Theorem leaves out the base definition (()), whose entry denotes the covariance between two input nodes. The traditional literature uses the inner product (10) (x, x')
z'z' (Lee et al. 2018).
3

---

Published as a conference paper at ICLR 2023
but nothing prevents us using any positive-definite kernel alternatively use the squared exponential kernel (x, = exp - Σ
|
For example, could
2
Such flexibility in
essence performs an implicit feature transformation as preprocessing.
3.2 UNIVERSALITY
A covariance kernel is positive definite: hence, the Moorc-Aronszajn theorem (Aronszajn 1950) suggests that defines unique Hilbert space for which it is a reproducing kernel. If this space is dense, then the kernel is called universal. One can verify universality by checking if the kernel matrix is positive definite for any set of distinct points ! For the case of graphs, it suffices verify if the covariance matrix for all nodes is positive definite.
We do this job for the ReLU activation function. It is known that the kernel Ew (o(w x))(w- x')] admits a closed-form expression function of the angle between and x', hence named the arc-cosine kernel (Cho & Saul, (2009). We first establish the following lemma that states that the kernel is universal over half-space.
Lemma 2. The arc-cosine kernel is universal on the upper-hemisphere S
{or E RR ||a||| m 0} for all d= 2.
also known that the expectation in 3 is proportional the arc-cosine kernel up to a factor (KW(x, x: (.f,,axK(K) (x', (Lee et al. 2018 Therefore, we iteratively work on the post-activation covariance (3) and the pre-activation covariance 4 and show that the covariance kernel resulting
from the limiting GCN is universal, for any GCN with three or more layers.
Theorem 3. Assume A is irreducible and non-negative and ((0) does not contain two linearly dependent rows. Then, K()) is positive definite for all 2 3.
3.3 LIMIT IN THE DEPTH
The depth of neural network exhibits interesting behaviors. Deep learning tends to favor deep networks because of their empirically outstanding performance, exemplified by generations con- volutional networks for the ImageNet classification (Krizhevsky et al. 2012 Wortsman al. 2022); while graph neural networks are instrumental to be shallow because of the over-smoothing and over- squashing properties (Li et al. 2018: Topping et al. 2022]. For multi-layer perceptrons (networks with fully connected layers), several previous works have noted that the recurrence relation of the covariance kernel across layers leads convergence to a exed-point kernel, when the depth L + oo (see, e.g., Lee et al. (2018); ; in Appendix B.5 we elaborate this limit). In what follows, we offer the parallel analysis for GCN.
Theorem 4. Assume A is symmetric, irreducible, aperiodic, and non-negative with Perron- Frobenius eigenvalue X >>0 0. The following results hold as I
When of =0, Pmia (mia(((") / L, where Pmiu denotes the minimum correlation between any two nodes x and x!.
2. When o² < 2/ subsequence of KD converges to some matrix.
3. When o² > 2/ let a (o2)2/2)) then, K0/e - vuu where is an eigenvector corre- sponding to X.
A few remarks follow. The first case implies that the correlation matrix converges monotonously to a matrix of all ones. As a consequence, up to some scaling & that may depend on the scaled covariance matrix K(')/ck converges to a rank-1 matrix. The third case shares a similar result, with the limit explicitly spelled out, but note that the eigenvector may not be normalized. The second case is challenging to analyze. According to empirical verification, we speculate a stronger result- convergence of K (!!) to unique fixed point-may hold.
Herr, abuse the notation and x in place of (0) in the inner product. "Note the conventional confusion in terminology between functions and matrices: kernel function is positive definite (resp. strictly positive definite) if the corresponding kernel matrix is positive semi-definite (resp. positive definite) for any collection of distinct points.
4

---

Published as a conference paper at ICLR 2023
Table 1: Computational costs. M: number of edges; N: number of nodes; N2: number of training
nodes; N.: number of prediction nodes; Na: number of landmark nodes; L: number of layers.
Assume N₂ > Na. For posterior variance, assume only the diagonal is needed.
Time O(-)
Storage OC)
Computation of Q
LMN, + LNN + LN
NN, (No + N. N.
a
Posterior mean (6)
N,N. + No + Na
Posterior variance
N.N. + N& + No
(No + N.).Na
SCALABLE COMPUTATION THROUGH LOW-RANK APPROXIMATION
The computation of the covariance matrix K(L) through recursion 3 is the main computational bottleneck for GP posterior inference. We start the exposition with the mean prediction. We compute the posterior mean D= = k% (K(l)) and the prediction set, respectively; and e, called the nugget, is the noise variance of the training data. Let there be N, training nodes and N, prediction nodes. It is tempting to compute only the (Ng + N.) x N, submatrix (T(1) for the task, but the recursion requires the full ((L-1) at the presence of A, and hence all the full CCD's and 's'
hb + =I]= yo. where the subscripts b and * denote the training
To reduce the computational costs, we resort to a low-rank approximation of CO),, from which we easily see that ((++1) is also low-rank. Before deriving the approximation recursion, we note (again) that for the ReLU activation o, ((I) in is the arc-cosine kernel with closed-fon expression:
1
( (!)) x'
(sin ( zx0 + (IT -80) cos g(!) oxx
((9) 2x
K
where
arccos
2T
K ma
(5)
Hence, the main idea is that starting with low-rank approximation of K(t, compute an approxi- mation of CC) by using (5), and then obtain approximation of ((+1) based (4): then, repeat.
To derive the approximation, we use the subscript a to denote a set landmark nodes with cardi- nality Na. The Nyström approximation (Drineas & Mahoney 2005) of KT(0) is K: (x:00) ) - where the subscript denotes retaining all rows/columns. We rewrite this approximation in the Cholesky style as Q ())""" where ((9) K (0) - has size N Na. Proceed with in- duction. Let K'()) be approximated by k:()) Q()) where Q!") has size N x (Na + 1). We apply 5 compute an approximation C..).. namely O!!)) by using R.!.) Then, leads
Cholesky style approximation of ((++1).
R(+1) of + AAA AT = =aU+)
where ((++1) = [ on A 1 (1l) σblNxi] Clearly, ((++1) has size N x (Na+1) completing the induction.
In summary, K (4) is approximated by a rank- Vank-(N,, +1) matrix (4)) = Q(1) The computation of Q(4) is summarized in Algorithm Once it is formed, the posterior mean is computed as
(1)) (()) T. R ab (R( + e = Q!hh (Q
(1)T Q +el)
Q
(
Ub.
(6)
where note that the matrix to be inverted has size (N₂ + 1) x (N, + 1), which assumed to be significantly smaller than No x Ng. Similarly, the posterior variance is
R-(L) (R()) +cl)
=Q.. = (0%0
Q +el)
(L)
The computational costs of Q(L) and the posterior inference 6 summarized in Table 1
5

---

Published as a conference paper at ICLR 2023
Algorithm Computing K(L) (LL) Q()Q())
Require: Q such that ((0) Q())(()))
1: for = ..... L do
2: Compute R000 Q Q!!!T
3: Compute (
by 5 where (( (resp. K k()) entries are replaced by ( (resp. R
entries
4:
Compute Q(++1)
0 AC (1
(Cad)= σblNx1
5:
end for
Table 2: Neural network building blocks, kernel operations, and the low-rank counterpart.
Building block
Neural network
Kernel operation
Low-rank operation
Input
X + X
t C(U)
Q k Chol(C(O))
Bias term
X+ X
K + ofINNN
IQ øbINxi]
Weight term
X +- XW
K oiK
Q < σ
Mixed weight term
X +- X(al +B)
K (a² + Foa)
Q t Va² + +320000
Graph convolution
X t- AX
K + AKAT
Q t AQ
Activation
X+ o(X)
K + g(K)
Q t Chol(a(QQ"))
Independent addition
X XI X2
K Ki + K2
Q Q2)
COMPOSING GRAPH NEURAL SETWORK-INSPIREDD KERNELS
Theorem together with its proof, suggests that the covariance matrix of the limiting GP can be computed composable manner. Moreover, the derivation of Algorithm indicates that the low- rank approximation the covariance matrix can be similarly composed. Altogether, such a nice property allows one to easily derive the corresponding covariance matrix and its approximation for a new GNN architecture, like writing a program and obtaining a transformation of it automatically through operator overloading (Novak al. 2020):: the covariance matrix is transformation of the GNN and the composition of the former is in exactly the same manner and order as that of the latter. We call the covariance matrices programmable.
For example, we write a GCN layer as X < A + b,, where for notational simplicity, X denotes pre-activation rather than post-activation as in the earlier sections. The activation & on X results in transformation of the kernel matrix K into g g(K), defined as:
g(K) = C Ez~N((. ( (o(=))(=)*},
due to 3 Moreover, if K admits low-rank approximation QQ", then g(K) admits a low-rank approximation PPT where P = Chol(g(K)) with
Chol(C) C..
The next operation graph convolution convolution-mmltipliees A to the left of the post-activation. Correspond- ingly, the covariance matrix K transformed to AK and the low-rank approximation factor Q transformed AQ. Then, the operation-mmltiplyiinn the weight matrix W to the right-will transform to o² and Q to Q. Finally, adding the bias will transform K to K + o N and Q [Q ob TblNx1] Altogether, have obtained the following updates per layer:
GCN:
X AO(X)W +b
K + o AA(A()) of NNNN
Q - A Chol(g(QQ"))
o1INx1]
One may verify the K update against can be automatically derived based on the update of X.
and the Q update against Algorithm Both updates
We summarize the building blocks of a GNN and the corresponding kernel/oowrrnk operations in Table 2 The independent-addiitio building block is applicable to skip/residual connections. For

---

Published as a conference paper at ICLR 2023
example, here is the composition for the GCNII layer (Chen al. 2020 without bias term, where skip connection with (0) occurs:
GCNII: : X + (1 (1-a)A6(X) + + ((1- B3)
K (1- (1-a)² + +a²k((0) ((1 - 0)=
Q [1 (1-h))CChll(((00 aQ v(1 -1-13) 3)2 Boo..
For another example of the composability,, which we assume uses a 2-layer MIP after the neighborhood aggregation:
consider the popular GIN layer (Xu et al. 2019
GIN X - ol (AA(()) + b)W" +
K - B NNNN where B= Ag))Ag(K) + +o INNN
Q - [o (hol(g(PP)))
opINxi] where P = A Chol(g(QQ))) oglNx]]
Additionally, the updates for GraphSAGE layer (Hamilton et al. 2017) are given in Appendix C
EXPERIMENTS
In this section, we conduct a comprehensive set of experiments to evaluate the performance of the GP kernels derived by taking limits on the layer width of GCN and other GNNs. We demonstrate that these GPs are comparable with GNNs in prediction performance, while being significantly faster to compute. We also show that the low-rank version scales favorably, suitable for practical use.
The experiments are conducted on several benchmark datasets of varying sizes, covering both classification and regression. They include predicting the topic of scientific papers organized in a citation network (Cora, Citeseer, PubMed, and ArXiv); predicting the community of online posts based on comments (Reddit), and predicting the average daily traffic of Wikipedia pages using hyperlinks among them (Chameleon, Squirrel, and Crocodile). Details of the datasets (including sources and preprocessing) are given in Appendix D
Datasets.
Experiment environment, training details, and hyperparameters are given in Appendix D
Prediction Performance: GCN-based comparison. We first conduct the semi-supervised learning tasks on all datasets by using GCN and GPs with different kernels. These kernels include the one equivalent to the limiting GCN (GCNGP), usual squared-exponential kernel (RBF), and the GGP kernel proposed by Ng et al. (2018) Each of these kernels has a low-rank version (suffixed with -X). RBF-X and X the Nyström approximation, consistent with GCNGP-X.
GPs are by nature suitable for regression. For classification tasks, we use the one-hot representation of labels to set up multi-output regression. Then, take the coordinate with the largest output as the class prediction. Such an ad hoc treatment is widely used in the literature, as other more principled approaches (such as using the Laplace approximation the non- Gaussian posterior) are too time-consuming for large datasets, meanwhile producing no noticeable gain in accuracy.
Table summarizes the accuracy for classification and the coefficient of determination, R², for regression. Whenever randomness is involved, the performance is reported as an average over five sligtly
runs. The results of the two tasks show different patterns. For classification, GCNGP(-X) better than GCN and GGP(-X), while RBF(-X) is significantly worse than all others; moreover, the low-rank version is outperformed by using the full kernel matrix. On the other hand, for regression, GCNGP(-X) significantly outperforms GCN, RBF(-X), and GGP(-X); and the low-rank version becomes better. The less competitive performance of (BF(-X) is expected, as it does not leverage the graph inductive bias. It attractive that GCNGP (-X) is competitive with GCN.
Prediction Performance: Comparison with other GNNs. In addition to GCN, we conduct ex- periments with several popularly used GNN architectures (GCNII, GIN, and GraphSAGE) and GPs
We apply only the kernel but not the likelihood nor the variational inference used in Ng 2018), for reasons given in Appendix [
*GGP-X in our notation is the Nyström approximation of the GGP kemnel, different from technique under
the same Ng al. (20T8), which additionally the validation compute the prediction loss.

---

Published as a conference paper at ICLR 2023
Table 3:
Performance of GCNGP, in comparison with GCN and typical GP kernels. The Micro-F1
score is reported for classification tasks and R² is reported for regression tasks.
GCN
GCNGP
GCNGP-X
RBF
RBF-X
GGP
GGP-X
Cora
1.818310.0055
0,8280
0.7980
0,5860
0.5850
0.7850
0.74I0
Citeseer
0.6941=00007
0.7090
0.7080
0.6120
0.6090
0.7060
0.6470
PubMed
0.7649=0.0058
0.7960
0.7810
0.7360
0.7340
0.7820
0.7380
ArXiv
0.6990=10.0014
OOM
0.7011
OOM
0.5382
OOM
0.6527
Reddit
0.9330=+0.0006
OOM
0.9465=000000
OOM
0.5920
OOM
0.9058
Chameleon
0.5690=t0.3376
0.6720
0.6852
0.5554
0,5613
0,5280
0,5311
Squirrel
0.4243=+00099
0.4926
0.4998
0.3187
0.3185
0.2440
0.2251
Crocodile
0.6976.10.332
0.8002
0.8013
0.6643
0.6710
0.6952
0.6810
Table 4: Performance comparison (Micro-F1) between GNNs and the corresponding GP kernels.
PubMed
ArXiv
Reddit
architecture
GNN
GNNGP
GNN
GNNGP-X
GNN
GNNGP-X X
GCN
0.7649:1..00s
0.7960
0.6989
0,701 1000011
0,9330
0,9465 0.0003
GCNII
0.7058
0.7840
0.7008
0.6955
0.9482=0.0007
0.9500
GIN GraphSAGE
0,7406=10012
0.7690
0.0340
0.6652:20012
0.9398=000016
0.9428=0.000
0.7535
0.7900
0.60841100021
0.6962:200077
0.9628=20.007
0.9539
with the corresponding kernels. We test with the three largest datasets: PubMed, ArXiv, and Reddit, for the latter two of which low-rank version of the GPs is used for computational feasibility.
Table summarizes the results. The observations on other GNNs extend similarly those on the GCN. In particular, on PubMed the GPs noticeably improve over the corresponding GNNs, while on ArXiv and Reddit the two families perform rather similarly. An exception is GIN for ArXiv, which significantly underperforms the GP counterpart, well other GNNs. It may improve with an extensive hyperparameter tuning.
Running time. We compare the running time of the methods covered by Table Different from usual neural networks, the training and inference of GNNs do not decouple in full-batch training. Moreover, there is not a universally agreed split between the training and the inference steps in GPs. Hence, we compare the total time for each method.
Figure plots the timing results, normalized against the GCN time for of comparison. It sug- gests that GCNGP(-X) is generally faster than GCN. Note that the vertical axis is in the logarithmic scale. Hence, for some of the datasets, the speedup is even one to two orders of magnitude.
Scalability. For graphs, especially under the semi-supervised learning setting, the computational cost of GP is much more complex than that of a usual one (which can be simply described as "cubic in the training set size"). One sees in Table [ the many factors that determine the cost of our graph-based low-rank kernels. To explore the practicality of the proposed method, we use the timings gathered for Figure to obtain an empirical scaling with respect to the graph size, M + N.
Figure 2 fits the running times, plotted in the log-log scale, by using a straight line. We see that for neither GCN nor GCNGP(-X), the actual running time closely follows polynomial complexity. However, interestingly, the least-squares fittings lead to a slope approximately 1, which agrees with linear cost. Theoretically, only GCNGP-X and GCN are approximately linear with respect to M + N, while GCNGP is cubic.
Analysis on the depth. The performance of GCN deteriorates with more layers, known as the oversmoothing phenomenon. Adding residual/skip connections mitigates the problem, such as in GCNII. A natural question asks if the corresponding GP kernels behave similarly.
Figure shows that the trends of GCN and GCNII are indeed as expected. Interestingly, their GP counterparts both remain stable for depth L as large 12. Our depth analysis (Theorem 4 suggests that in the limit, the GPs may perform less well because the kernel matrix may degenerate to rank 1. This empirical result indicates that the drop in performance may have not started yet.
8

---

Published as a conference paper at ICLR 2023
10a
GCN GONGP GCNGP-X
10a
Time: (Propos Cionaaiionall to GCN)
GCNGP
GCNGP-X
Time (Seconds)
10-1
10a
10
Cora
CiteSeer
PubMed
arxiv
Reddit
chameleon
squireet
crecodle
10a
10a
10
107
Graph Size N
Figure 1: Timing comparison. For each dataset, the times are normalized against that of GCN.
Figure 2: Scaling of the running time with spect to the graph size, +
0.80
0.95
Computation Time
0.94
Teat Arturacy (GCN)
0.70
Test Accuracy (GENGP
10
0.93
8
nho (Seconds)
0.92
0.60
Teat
GCN
0.90
0.50
GONGP
0.89
GCNZ
GCN2GP
0.10
0.87
10
12
1/3200
1/1600 1/000 1/400 1/200 1/100 1/50
Number of Layers
Fraction of Landmark Nades
Figure 3: Performance of GNNs and GNNGPs
Figure 4: Performance GCNGP-X as number of landmark nodes increases, Dataset: Reddit.
as depth L increases. Dataset: Pubmed.
Analysis on the landmark set. The number of landmark nodes, N.. controls the approximation quality of the low-rank kernels and hence the prediciton accuracy. On the other hand, the compu- tational costs summarized in Table I indicate dependency on N, as high the third power. It is crucial to develop an empirical understanding of the accuracy-ting trade-off it incurs.
Figure cllearly shows that Na becomes larger, the running time increase is not linear, while the increase of accuracy diminishes as the landmark set approaches the training set. It is remarkable that landmark nodes already achieves accuracy surpassing that
using only 1/800 of the training of GCN, by using time that is only a tiny fraction of the time otherwise needed to gain an additional 1% increase in the accuracy.
CONCLUSIONS
We have presented a GP approach for semi-supervised learning on graph-structured data, where the covariance kernel incorporates a graph inductive bias by exploiting the relationship between GP and a GNN with infinitely wide layers. Similar to other neural networks priorly investigated, one can work out the equivalent GP (in particular, the covariance kernel) for GCN; and inspired by this equivalence, we formulate a procedure to compose covariance kernels corresponding to many other members the GNN family. Moreover, every building block in the procedure has a low- rank counterpart, which allows for building low-rank approximation of the covariance matrix that facilitates scalable posterior inference. We demonstrate the effectiveness the derived kernels used for semi-supervised learning and show their advantages in computation time GNNs.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
Mihai Anitescu was supported by the U.S. Department of Energy, Office of Science, Office of Ad- vanced Scientific Computing Research (ASCR) under Contract DE-ACO2-06CCH11347 Jie Chen acknowledges supports from the MIT-IBM Watson Al Lab.
REFERENCES
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68(3):337-404, 1950.
Jie Chen and Michael L. Stein. Linear-cost covariance functions for Gaussian random fields. Journal of the American Statistical Association, 2021.
Jie Chen, Haim Avron, and Vikas Sindhwani. Hierarchically compositional kernels for scalable nonparametric learning. Journal of Machine Learning Research, 18(66):1 2017.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, 2020.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In NIPS, 2009.
Alexander G. de Matthews, Jiri Hron, Mark Rowland, Richard E. Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. In ICLR, 2018.
Petros Drineas and Michael W. Mahoney. On the nystrom method for approximating a gram matrix for improved kernel-based learning. Journal of Machine Learning Research, 6(72):2153-2175, 2005.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning on Graphs and Manifolds, 2019.
Adrià Garriga-Alonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional net- works shallow Gaussian processes. In ICLR, 2019.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized PageRank. In ICLR, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
Jilin Hu, Jianbing Shen, Bin Yang, and Ling Shao. Infinitely wide graph convolutional networks: Semi-supervised learning via Gaussian processes. Preprint 122 2020a.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurIPS, 2020b.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In NeurlPS, 2018.
Matthias Katzfuss. A multi-resolution approximation for massive spatial datasets. Journal of the American Statistical Association, 12(517))201-214, 2017.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. ImageNet classification with deep convo- lutional neural networks. In NIPS, 2012.
10

---

Published as a conference paper at ICLR 2023
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as Gaussian processes. In ICLR, 2018.
Jachoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In NeurIPS, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018.
Radford M. Neal, Priors for infinite networks. Technical Report CRG-TR-94- University of Toronto, 1994.
Yin Cheng Ng, Nicolo Colombo, and Ricardo Silva. Bayesian semi-supervised learning with graph Gaussian processes. In NeurlPS, 2018.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A. Abo- lafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels Gaussian processes. In ICLR, 2019.
Roman Novak, Lechao Xiao, Jiri Hron, Jaehoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in Python. In ICLR, 2020.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-GCN: Geo- metric graph convolutional networks. In ICLR, 2020.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In NIPS, 2007.
Carl Edward Rasmussen and Christopher K. Williams. Gaussian Processes for Machine Learning.
The MIT Press, 2006.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2), 2021.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In ICLR, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Christopher Williams. Computing with infinite networks. In NIPS, 1996.
Andrew Gordon Wilson and Hannes Nickisch. Kernel interpolation for scalable structured Gaussian processes (KISS-GP). In JCMI,, 2015.
Mitchell Wortsman, Gabriel Ilharco, Samir Yitzhak Gadre, Rebecca Roelofs, Raphael Gontijo- Lopes, Ari S. Morcos, Hongseok Namkoong, Ali Farhadi, Yair Carmon, Simon Kornblith, and Ludwig Schmidt. Model soups: averaging weights of multiple fine-tuned models improves aceu- racy without increasing inference time. In /CML., 2022.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 32(1):4 2-44444444 2021.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanic Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? ICLR, 2019.
Greg Yang. Tensor programs I: Wide feedforward or recurrent neural networks any architecture Gaussian processes. In NeurlPS, 2019.

---

Published as a conference paper at ICLR 2023
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang. Changcheng Li, and Maosong Sun. Graph neural networks: review of methods and applications. Al Open, 1: 57-81, 2020.
Xiaojin Zhu, Semi-supervised learning literature survey. Technical Report TR1530, University of Wisconsin-Madison, 2008.
12

---

Published as a conference paper at ICLR 2023
A
CODE
Code is available at attpppss/gEEhbb..m//iiiieeeeeeep
B PROOFS AND ADDITIONAL THEOREMS
B.1 PROOF OF THEOREM !
We use mathematical induction. First, write the matrix form of (2) as follows:
y = ( W Nxd: xx d-1idi"
z
D +
A y!))
x() Nxd,
0 ((Z()) Xxd:
Nxd:
Nx1 1xd: NXN Nxdi
Assume each column of z(- is iid, then X(-1) 1) also has iid columns. Hence, yi (xx sum of iid terms and thus normal. Also, (v, (x1). .,," (Irw) are jointly multivariate normal, and identically distributed for different i; so they form GP.
Moreover, terms like
(I) and Ver (1) (x') with + i' are jointly Gaussian, with zero covariance:
d:-1 de-1
Cov(y! (z), (x)) = Σ Σ
0 Cov (w aj (x), w a (z') = 0.
5=1
Thus, they are independent, despite the fact that they may share the same X (1-1) terms. conclu- sion, each column of y an iid GP. Hence, each column of z is also an iid GP (0, (().
The covariance (00) can be computed recursively, Similar the case of a fully connected network, the covariance of y is
Bly (x)y; (2) (x')] = o Blr, (1-11))))) (2)x, ())))) (2') = o. 0 (x,))),
where
(a-")((z2')) -Eo-Voo.ku--n (z)) for any j.
In the matrix form, this is to say Cov(Y)!) = 0Z F(x x!! (((-1)" oZ ((1-)) Then, because
z = AV + INxIb (1) we obtain
R INNN + A - +
=o
o 1)
which concludes the proof.
B.2 PROOF OF LEMMA 2
We know that d(w 6(w-r) is the feature mapping of the arc-cosine kernel. It suffices to show for different Ti, ...,... Z' S, the o(w, 24)"s 's are linearly independent.
We prove this by contradiction. Assume there exist cl,,.., On not simultaneously zero, such that
colw x2) = 0. X
WLOG, we further assume that m is the smallest integer that satisfies 9 Let e1 (1, 0, ... ,0:: then x e1 > 0, Vx E S. Assume Fm minigism {at e > O. Then, for < i S m -
44 Fm
Fm Fm
Z; G1
Im
Therefore, there exists such that
Σ4 2m
Im Im
t <
1 1 m-1
Im C1
Let Fm tes; then
Jm 0,
w 24 < 0, 1 1 1 m m
Using we know em (w-x,) = 0; so c. = 0. Thus, ... ... Cn-1 and ((w-x)), ... -6w xm)) also satisfy (9) with smaller number m, which forms contradiction.
13

---

Published as a conference paper at ICLR 2023
B.3 PROOF OF THEOREM 3
From the recursive relation
we know ( is element-wise non-negative. Hence, (()) is element-wist non-negative, C is element-wise positive, and K ((2) is clement-wisc positive.
Assume the Cholesky decomposition K(2) LL" and denote L. (1, .,n"". Letr; ||///2
and 2, 4. Then, 21 Iel, and WLOG we assume 21 E1. Then for each 24, we know
4-4
K(2)
2, 61
T
and each ||l:||2 1. Therefore, E S is defined in Lemma
2
By the assumption that ((0) does not contain two linearly dependent rows, we know are K()) and ( Thus, no two 4ss are linearly dependent and hence z;'s are pairwise distinct. Using the universality of the arc-cosine kernel (Lemma 2). we know C12) = g(K(2)) is positive definite.
Hence, K(3) positive definite. An induction argument on the layer index completes the proof.
B.4 PROOF OF THEOREM
For covariance matrix K, denote its standard deviation and correlation by
(x(x) = K K(x, x),
K K(x, x") Px (x,xx)= = V (K( (I')) xx'
From the closed-form formula (5) for the arc-cosine kernel, we have
Pcus (I, x') (sin (0) (T ((()) cos (!)) 2,27
1 т
PKo (I, cos a.
We define the correlation mapping from Prtt Pou!
f cos 0 + (sin 0 + (Ir 0) cos 0), 0 [0, m).
We first establish a few properties of f. A pictorial illustration of f is given Figure
1.00
cosD #)coc8)
0.75
p+op
0.00
0.5
0.50
-1.00
-0.75
-0.50
-0.25
0.00
0.5
0.50
0.75
1.00
Figure 5: Correlation mapping f-
Lemma 5. The following facts hold.
1. is increasing and it is contraction mapping [-1, 1).
14

---

Published as a conference paper at ICLR 2023
2. f(p) 2 and the equality holds only when 1.
Proof. For part 1, denote cos 0 E [-1, Then,
(() (f(p) 00
-1 (π 8) sin
-1
[0.
Op
π
sin 0
π
Thus, f is increasing and it is a contraction mapping on [-1,
For part we know that f1) 1. Using the contraction mapping, we know f(p) 2 p for p [1 Clearly, the equality holds only when = 1.
After the correlation mapping f. we further consider the covariance mapping K C defined in (3) (and equivalently in ( We establish few properties below.
Lemma 6. For positive semi-definite matrices B, the the following facts hold.
1. .(B)
where D = diag(B) E IRN and f is elementwise.
2. g(B) > B and (g (B)) diagg [), where > means elementwise greater.
3. tr (Ag( (T) S 11 (B), where || is the spectral norm of matrix A.
Proof. For part 1, it is obvious according to 5
For part 2, using the properties of we straightforwardly obtain
g(B) = (DD "" =
For part 3, note that g(B) is positive semi-definite. Using von Neumann's trace inequality,
tr (Ag(B)A") = tr Ag()) S
= 1AAA Σ Ac(o(B)),
1m1
where the last term is equal to 11 || (1rrr (B). Now, we are ready to prove Theorem 4
Proof of Theorem part We focus on uniform convergence over all pairwise correlations. De-
note
Pmin (K) min pk (x (x) 1-1,1]. 2,2
To simplify notation, we temporarily let C C(O) Then,
K( (x,x) = o0 Σ Ana Alu
o Σ
A
2 Pmin (C). 2 Σ ((m))o((())))((
2,0'
Σ Ammo(()) (IArvoo(o))
Pmin (C) o
15

---

Published as a conference paper at ICLR 2023
Mcanwhile,
K (2. x) = 3 C(,,
2,84
0 Σ ((o)moo
Σ AAnoo(())
and similarly
K ( (d' x.) S a Σ Alwao(v))
Combining the above inequalities, we obtain
K K (I,,
(x,,
Pmin (Cn)) Ve,
(Ku+I)(I, (1'+
and thus
Pmin ( 2 Pmuin (C(1).
From the correlation mapping, we know
Pmin (C {pmin (00ni((K)))
Therefore, by the properties of f,
Pmin (K(+))) 2 [ (k()))(()))) 2 Pmin (K
Thus, Puain (K() / some Poo E 1-1, Because Poo f(px)), we conclude that Pro 1.
Proof of Theorem 4 part 2. Consider each h: K( + ((+1);
K (1+1) N,NN + AAA A = of + o Ag = =h(K()).
Let = = < 1. Using part Lemma 6
tr (k(+2)) tr (of tr (o (2AA(((()))))
Nož + oirr (Ag(K())AT)
< Not + t (K0)
No - (x())
Therefore, for sufficiently large 1
No + 1. tr (KW) <
Because each K(O) is positive semi-definite, we know K() is bounded. Thus, subsequence of (()) + some matrix.
Proof of Theorem 4 part 3. Define k! = K(W/et We have the following recursive relationship between x(0) and k (+1,
(1+1)
1 (o, + o2 )AA) c1+1
oi 1NNN + )
= a4t
Then,
ur (1(4))) ir غم 1NxN) + frr (AD(s())a²)
Not c++ + ir (n)())
<
16

---

Published as a conference paper at ICLR 2023
where the inequality results from part 3 of Lemma 8 Therefore, x()) is bounded.
Using the Perron-Frobeniqg theorem, we know the eigenspace V corresponding to is one- dimensional, and there exists E V such that ||e||2 1 and > 0. Then,
v ((+1)
of 1..vINN INNNU+ + o0 Ag(n:)) 2 2n g(x"")) 2 v. cL+1
Therefore, v² 10 has limit 0.
Let P Projv= = Projv = -I- vo=. Then PA = AP, |P = < X, and
(Po(n ur (B(N!!1) o² gf S 1ir (nt)) 200 = frr (Pr!)
Therefore,
tr (Pr((t))PT)
a PINXNPT) c++1
+ to (PAg(N!))AT pT)
= tr
No²
tr (PAPg(N"))) PT APPTT)
at1
No
+ 11111 (PO(N())PT)
a++1
No?
+ 2 PPx
911
Thus, (1( pT +
Combining the results, we have (00) + cvn..
B.5 RESULTS FOR MULTI-LAYER PERCEPTRONS
Theorem has parallel results for fully connected layers.
Theorem 7. Let A be the identity matrix. The following results hold as + c0.
of
1. When o and of O, then kD)) gINXN where 9 1 02//2
2 of
2. When 0 2, let a (22//)); then K0 -> veT where U2
+ k (x,
Proof of Theorem 7 part 1. Starting with the diagonal elements, we have
k(+t = of + a² k (1,(x, x).
2
Therefore, (x,x)) + -
02 //2
For the off-diagonal elements, we have
k(411 (2,2' = o +
2
a² ogn (z) (z')f (a
2
2 oh +
o²
2 o kgn (I) (x (x
of + 2
k(l) (x,2²).
2
Therefore,
(1++)((x))))) in K (1+ (z, x') 2 of +
a lim inf k-(1) (x, = lim inf K- (x, (0) 2 q.
2
Meanwhile,
limsup ((O) (I, x') < lim v (() = Thus, K00 (x,x²) q. In conclustion, K(0 NNNNN-
17

---

Published as a conference paper at ICLR 2023
Proof of Theorem 7 T 2, we have
part 2. Again, start with diagonal elements. Define k() K0//a. When
of 22 + (x,
( (x,
Therefore,
of
0 (I,
o /2) 1: (I,
+ K0 (x, 1) = -.
0. 2
1=0
For the off-diagonal elements, we have
(((1) (2,
oi + o aw (x)o (x')S (p (1,00(0;2)))
a-1
2 0,00 (2)o (x' P (x,
(x,x',
Thus, (x, x²) has limit c. Taking limits on both sides, we have
c= Ux / (c/(VV))))
which suggests that c = Var. conclustion, x0)) + vo.
C COMPOSING GRAPHSAGE
As before, X denotes pre-activation rather post activation. A GraphSAGE layer has two weight matrices, Wi and W2. Hence, we use two variance parameters dw, and Jwn, for them, respectively. For simplicity, we focus on the mean-aggregation version of GraphSAGE, where effectively the rald matrix. The updates are:
GraphSAGE:
X + 6(X) + Ao(X)W2
K + o g() - A
Q + W P
0 wuz APP where P Chol(g(QQ"))
Note that we do not use bias term. If it is desired, one can easily add it to the updates following the example of GCN.
D EXPERIMENT DETAILS
Datasets. A summary is given Table 5 The datasets ConnCiccser/RbMMM/RRRdiii, with pre- defined training/validation/ee
splits, downloaded from the PyTorch Geometric library (Fey & Lenssen 2019) and used as is. The dataset ArXiv comes from the Open Graph Benchmark (Hu come from MUSAE (Rozemberezki 2021). The training/validationneest splits the former two sets datasets come from Geom- (Pei al. 2020), in accordance with the PyTorch Geometric library. The split for Crocodile
al. 2020b). The datasets Chameleen/Squirre//Coooodd
ct al.
GCN
Table 5: Dataset summary. The edge column lists the number of directed edges.
Dataset
Task
Nodes
Edges
Features
Vrain/Val/Test Ratio
Cora
Classification
2,708
5,429
1,433
0.05/0. 18/0.37
Citeseer
Classification
3,327
4,732
3,703
0.04/0. 15/0.30
PubMed
Classification
19,717
44,338
500
0.003/0.025/0.05
ArXiv
Classification
169,343
1,166,243
128
0.54/0.18/0.24
Reddit
Classification
232,965
11,606.919
602
0.66/0.10/0..
Chameleon
Regression
2,277
36.101
3.132
0.48/0.32/0.20
Squirrel
Regression
5,201
217,073
3,148
0.48/0.32/0.20
Crocodile
Regression
11,631
180,020
13,183
0.48/0.32/0.20
18

---

Published as a conference paper at ICLR 2023
not available, so conduct random split with the same 0.48/0.32/0.20 proportion that used for Chameleon and Squirrel (Rozemberczzii et al. 2021).
Dataset preprocessing. For each graph, we treat the edges undirected and construct binary.
symmetric adjacent matrix A. Then, we apply the normalization proposed by Kipt & Welling (2017)
to define used in (T). Specifically, A = (IN + D)-1/3(1 + [ + D)-172 where D diag E, A, . For GraphSAGE and GGP, we instead use the row-normalized version A = (IN +
DTN' + 4). No feature preprocessing is done except running the GPs on ArXiv, for which we apply a centering on the input features.
Environment. All experiments are conducted on Nvidia Quadro GV100 GPU with 32GB of HBM2 memory. The code is written in Python 3.10.4 as distributed with Ubuntu 22.04 LTS. We use PyTorch 1.11,0 and PyTorch Geometric 2.1.0 with CUDA 11.3.
Training, For all datasets except Reddit, we train GCN using the Adam optimizer in full batch for 100 epochs. Reddit too large for GPU computation and hence we conduct mini-batch training (with batch size 10240) for 10 epochs.
Hyperparameters. For classification tasks in Table 3 the hyperparameters are set to σ = 0.0, Tw = 1.0, L = 2, hidden = 256, and dropput 0.5. GCN is trained with learning rate 0.01. For regression tasks, they are set to V0.1, o~ = 1.0, 7. 2, hidden 256, and dropput = 0.5. GCN is trained with learning rate v0.1
We choose (1)) to be the inner product kernel. The exception is when working with the low-rank versions, we apply PCA on the input features to ensure the number of features smaller than the number of landmark nodes.
For Table 4 GCNII uses 2-layer architecture and sets 0.1, X 0.5, 3 log( à + 1). GIN uses L and = 0.0. GraphSAGE uses 2-layer architecture and sets dw, = v0.1 for Reddit and ow, 0.0 for other datasets, and Ow, 1.0.
The nugget is chosen using a grid search over [10-3 10'].
For GCNGP-X, GNNGP-X and RBF-X, the landmark points chosen to be the training set for small datasets, while for large datasets (ArXiv and Reddit) the landmark points are a random 1/50 of the training set.
Kernels. For the RBF kernel,
K(x, x²) = exp(-7/lx- x' x')1)),
where y is chosen using a grid search over 110-2, 10 For the GGP kernel,
= AKoAT, No(x,,2') = (a x' t)d
where c 5.0, 3.0. Note that use only the kernel but not the robust-max likelihood nor the ELBO training proposed by Ng et al. (2018). because their code written in Python 2 is outdated and cannot be used. Note also that GGP-X in Ng et (2018)) has a different meaning training GGP by using additionally the 500 nodes in the validation set-whii we use GGP-X to denote the Nyström approximation GGP.
19


Reviews:
[{"review_id": "_OsrwFBmbM", "reviewer": "Reviewer_XBR8", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The goal of this study is to attack the semi-supervised learning problem for graph-structured data. The paper focus on bridging the gap between GNNs and the limiting GPs by deriving the covariance kernel that incorporates the graph inductive bias as GNNs do.  More specifically, the paper has shown that the GP can be derived as a limit of the GCN when the layer widths tend to infinity and demonstrated the kernel universality and the limiting behavior in depth. In addition, the paper also develops an efficient computational algorithm for posterior inference on large-scale data.", "summary_of_the_review": "See above", "strength_and_weaknesses": "Overall, the paper is well motivated. The use of a real data set is a huge strength of the paper. In particular, I would also like to commend the authors on the crystal clear exposition and writing throughout the paper. The proposed method and theory are clearly presented and easy to follow. \n\nMy main concern is the originality of establishing connection between GCNs and GPs. I have seen a number of previous studies which reached a similar conclusion. For example:\n- https://arxiv.org/pdf/1711.00165.pdf\n- https://arxiv.org/pdf/2002.12168.pdf\n- https://proceedings.neurips.cc/paper/2019/hash/5e69fda38cda2060819766569fd93aa5-Abstract.html\n\nIt would be better for the authors to clarify the differences and highlight their main theoretical & methodological contributions compared to the existing studies. Also, the low rank approximation for scalable computation hinges on the Nystrom approximation of matrix K, which is widely-used in the GP literature. Therefore, in my opinion, the algorithmic contributions are incremental (or limited).\n\nGiven that I believe the authors would need to effectively address the above questions and the totality and generality of the contributions to be not significant enough to warrant publication at this stage.\nI hope the authors may find these high-level comments helpful in thinking about the next steps for their paper. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "UEg9ZjM9We", "reviewer": "Reviewer_svk4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work, the graph neural network structure is integrated into the GP framework to construct a kernel function with graph structure, and the low-rank approximation method is used to deduce the efficient training and inference method of GP, aiming to improve the performance and efficiency of graph structure data classification and regression.", "summary_of_the_review": "A novel idea and implementation of combing GP and graph neural network.", "strength_and_weaknesses": "Strength:\n\n1. The idea is interesting and somewhat novel.\n2. The manuscript is clear and easy to read.\n3. The experiments validate the effectiveness of the proposed method.\n\nWeaknesses:\n\n1. Why does integrating graph neural network structure into GP framework improve the performance compared with GNN? In my opinion, one of the main advantages of GP is the use of kernel functions like RBF, which can approximate the nodes of infinite element network, and the kernel functions used here are still based on the inner product of mapping functions.\n\n2. The authors emphasize that the proposed method is suitable for semi-supervised scenarios, but does not give the reason and the specific algorithm of semi-supervised learning. If it is supervised learning, whether the proposed method still has the same advantage?\n\n3. Can the authors explain the trend of the curves in Figure 3?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ThWPxK-r4HP", "reviewer": "Reviewer_SNQW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper derives a GP model as a GCN with layer widths increased to infinity. To make the prediction more scalable, a low-rank approximation approach is proposed. Experiments are conducted to compare with other baseline models and show the GP model’s running time and scalability advantages.", "summary_of_the_review": "The idea of deriving a GP model for infinitely wide GCN is novel. Also, the GP model can be extended to a wide range of GNNs, which shows its generality.", "strength_and_weaknesses": "Strength:\n\n1. The designed GP covariance kernel is able to capture the geometry information of the graph.\n2. The runtime of the designed GP is much faster than standard GCN, especially using the low-rank version. Also, its performance on all datasets is better than GCN.\n3. For most of the operations in GNNs, operational counterparts for the GP exist. Therefore, the proposed GP model can be extended to many other GNNs.\n\nWeaknesses:\n\n1. It is interesting to see that GP versions of many SOTA GNNs achieve comparable performance with respect to their original models. However, this is only done in one dataset. It would be great if the authors can also have this comparison on other datasets in Table 4.\n\n\nQuestions:\n1. How is $d_0$ defined in $C^{(0)}$? \n2. For usual GPs, their hyperparameters (typically in the prior mean function and the covariance function) can be obtained by optimizing the log-marginal likelihood. In the proposed GP, how can these hyperparameters be optimized?\n3. Can the proposed GP model be extended to the GAT family?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CNkoR7KiRP", "reviewer": "Reviewer_okj8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper defines GCN-inspired kernels by deriving GP as the limit of GCN. The authors present some theoretical results such as universality and develop a scalable posterior inference method based on low-rank approximation of covariance matrix. The effectiveness of the proposed method is demonstrated using multiple bench mark datasets.", "summary_of_the_review": "Connection of GP and GCN is interesting. The proposed formulation is reasonable and the approximation method is beneficial. But discussion about related works (graph Gaussian processes) are missing. Then, my opinion is \"weak accept\" for now.", "strength_and_weaknesses": "S1. The authors derive GCN-inspired kernels by defining GP as the limit of GCN.\n\nS2. The theoretical guarantees such as universality are thoroughly discussed.\n\nS3. A practical inference algorithm is also presented, whose effectiveness is verified on real-world datasets.\n\nW1. There is no discussion of important related studies, graph Gaussian processes [R1]. Can you please explain in detail the relationship with the proposed method? Please add to the baseline method if necessary.\n\n[R1] Yin Cheng Ng et. al., Bayesian Semi-supervised Learning with Graph Gaussian Processes, NeurIPS, 2018.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster