Flexible Infinite-Width Graph Convolutional Neural Networks
Authors: Ben Anson
Edward Milsom
Laurence Aitchison
Venue: Accepted by TMLR ()

Abstract: A common theoretical approach to understanding neural networks is to take an infinite-width limit, at which point the outputs become Gaussian process (GP) distributed. This is known as a neural network Gaussian process (NNGP). However, the NNGP kernel is fixed and tunable only through a small number of hyperparameters, thus eliminating the possibility of representation learning. This contrasts with finite-width NNs, which are often believed to perform well because they are able to flexibly learn representations for the task at hand. Thus in simplifying NNs to make them theoretically tractable, NNGPs may eliminate precisely what makes them work well (representation learning). This motivated us to understand whether representation learning is necessary in a range of node classification tasks on graphs. We develop a precise tool for this task, the graph convolutional deep kernel machine. This is very similar to an NNGP, in that it is an infinite width limit and uses kernels, but comes with a “knob” to control the amount of flexibility and hence representation learning. We found that representation learning gives noticeable performance improvements for heterophilous node classification tasks, but less so for homophilous node classification tasks.

Published in Transactions on Machine Learning Research (05/2025)
Flexible Infinite-Width Graph Convolutional Neural Net- works
Ben Anson
wmm.anson@bristol.com
School of Mathematics
University of Bristol Bristol, United Kingdom
Edward Milsom
School of Mathematics University of Bristol Bristol, United Kingdom
Laurence Aitchison
School of Computer Science Universily of Bristol Bristol, United Kingdom
Reviewed on OpenReview: https: openreview. net/ forum? id= Q2M4yijKKo
Abstract
A common theoretical approach to understanding neural networks is to take infinite- width limit, at which point the outputs become Gaussian process (GP) distributed. This is known as a neural network Gaussian process (NNGP). However, the NNGP kernel is fixed and tunable only through a small number of hyperparameters, thus eliminating the possibility of representation learning. This contrasts with finite-width NNs, which are often believed to perform well because they are able to flexibly learn representations for the task at hand. Thus, in simplifying NNs make them theoretically tractable, NNGPs may eliminate precisely what makes them work well (representation learning). This motivated us to understand whether representation learning is necessary in range of graph tasks. We develop a precise tool for this task, the graph convolutional deep kernel machine. This is very similar to an NNGP, in that an infinite width limit and uses kernels, but comes with a "knob" to control the amount of flexibility and hence representation learning. We found that reprosentation learning gives noticcable performance improvements for heterophilous node classification lasks, but less for homophilous node classification lasks.
1 Introduction
A fundamental theoretical method for analyzing neural networks involves taking infinite-width limit of randomly initialized network. In this setting, the outputs converge to Gaussian process (GP), and this
GP is known as neural network Gaussian process or NNGP (Neal 1996 Lee et al. 2018 Matthews et al. 2018). NNGPs have been used to study various different neural network architectures, ranging from fully- connected (Lee et al. 2018) lo convolutional (Novak el al. 2018
Garriga-Alonso el al. 2018 and graph
networks Walker & Glocker 2019 Niu et al. 2023)
However, it is important understand whether these NNGP results apply in practical neural network settings. One way of assessing the applicability of NNGP results is to look at performance. Specifically,

---

Published in Transactions on Machine Learning Research (05/2025)
if wnfihite-width NNGPs perform comparably with finite-width NNs, can reasonably claim that infinite- width NNGPs capture the "essence" of what makes finite-width NNs work so well. In contrast, if finite-width NNs perform better, that would indicate that NNGPs are missing something.
Why might NNGPs underperform relative to NNs? One key property of the infinite-width NNGP limit is that it eliminates representation learning: the kernel of the GP is fixed, and cannot be tuned except through a very small number of hyperparameters. This fixed kernel makes it straightforward to analyze the behaviour of networks in the NNGP limit. However, the clegant fixed kernel comes at cost. In particular, the top-layer representation/kesn /kennel is highly flexible in finite networks, and this flexibility is critical to the excellent performance of deep networks (Bengio et al. 2013 LeCun et al. 2015). This indicates that in some cases, the infinitewiddth NNGP limit can "throw the baby out with the bathwater": in trying to simplify the system to enable theoretical analysis, the NNGP limit can eliminate some of the most important properties of deep networks that lead to them performing well.
In the setting of convolutional networks for CIFAR-10, this is precisely what was found: namely, that infinite- width NNGPs underperform finite-width NNs (Adlam et al. 2023 Garriga-Aloae Alonso et al. 2018 Shankar et al., 2020), and it has been hypothesised that this difference arises due to the lack of representation learning in NNGP (Aitchison 2020: MacKay et al. 1998).
In this paper, we consider the question of NNGP performance in the Graph Convolutional Network (GCN) setting. Surprisingly, prior work has shown that the graph convolutional NNGP performs comparably to the GCN (Niu et al. 2023), perhaps suggesting that representation learning not important in graph settings.
However, our work indicates that this picture is incomplete. In particular, we show that while the graph convolutional NNGP is competitive some datasets, it is much worse than GCNs on other datasets. This would suggest a hypothesis that representation learning in graph tasks is dataset dependent, with some datasets needing representation learning, and others not.
Importantly, testing this hypothesis rigorously is difficult, as there are many differences between the infinite- width, fixed representation graph convolutional NNGP and the finite-width, flexible representation GCN, not just that the GCN has representation learning. Perhaps the best approach to testing the hypothesis would be to develop variant of the NNGP with representation lcarning, and to see how performance changed as we altered the amount of representation learning allowed by this new model. However, this is not possible with the traditional NNGP framework. Instead, we need to turn to recently developed deep kernel machines (DKMs) (Yang et al. 20233 Milsom et al. 2023). DKMs, like NNGPs, are obtained via an indinite-width limit, and in practice work entirely in terms of kernels. The key difference is that DKMs allow for representation learning, while NNGPs do not. Specifically, DKMs have a tunable parameter, V, which controls the degree of representation learning. For small values of v, DKM representations are highly flexible and learned from data. In contrast, V + oo, flexibility is climinated, and the DKM becomes equivalent to the NNGP. The graph convolutional DKM therefore forms precise tool for studying the need for representation learning in graph tasks.
Using the graph convolutional DKM, we examined the need for representation learning in a variely of graph tasks. Node classification tasks in particular exist on a spectrum from homophilous, where adjacent nodes in a graph tend to have similar labels, to heterophilous, where adjacent nodes tend to be dissimilar. We found that homophilous tasks tended not to require representation learning, while heterophilous tasks did require representation learning.
Concretely, our contributions are as follows:
We develop graph convolutional variant of deep kernel machines (Section 4
We propose two scalable inducing-poing point approximation schemes for the graph convolutional DKM (Section 4.2 Appendix B
We analyze the graph convolutional DKM in the linear setting, and provide a closed-form solution for the learned representations (Section 5
2

---

Published in Transactions on Machine Learning Research (05/2025)
By considering the performance of graph convolutional NNGPs relative to GCNs and by tuning in the graph convolutional DKM, we find that representation learning improves performance in heterophilous node classification tasks but not homophilous node classification tasks.
2
Related Work
Graph convolutional networks are a type of graph neural network (Scarselli et al., 2008 Kipf & Welling 2017
Bronstein et al. 2017 Velicković et al. 2017] originally introduced by Kipf & Welling (2017), motivated by a localised first-order approximation of spectral graph convolutions. They use the adjacency matrix aggregate information from node's neighbours at each layer of the neural network. When first published, graph convolutional networks outperformed existing approaches for semi-supervised node classification by significant margin.
Homophily, a measure of similarity between connected nodes in a graph, has been studied extensively in the context GNNs (Luan et al. 2024 Zhu et al. 2020: 2021 Maurya et al. 2021 Platonov et al. 2023), mostly
to point out that lack of homophily (meaning that connected nodes tend to be dissimilar) is detrimental performance in GNNs. Here, we examine an adjacent but different matter: the relationship between homophily and representation learning.
iufinite-widte neural networks were first considered in the 1990s (Naa 1996 Williams 1996) where they only considered shallow networks at initialisation. Cho & Saul (009) derived an equivalence between deep
ReLU networks and arccosine kernels. This was later generalises ised to arbitrary activation functions by Lee
ct al. 2018). who used Bayesian framework to show that any infinitely-wide deep neural network is
equivalent to a Gaussian process, which they dubbed the neural network Gaussian process (NNGP) (Lee
et al. 2020: 2018 Matthews et al.] 2018). The NNGP has since been extended, for example to accommodate
convolutions (Garriga-Alonso al. 2018 Novak et al. 2018), graph structure (Niu et al. 2023 Hu et al.
2020a and more (angg 2019).
Using similar infinite-width limit, but on SGD-trained networks rather than Bayesian networks, Jacot et al. (018) studied the dynamics of neural network training under gradient descent, deriving the neural tangent kernel (NTK), which describes the evolution the infnntt-width network over time. The NTK suffers from an analogous problem to the NNGP's lack of representation learning, since the NTK limit implies that the intermediate features do not evolve over time (Yang & Hu 2021 Bordelon & Pehlevan 2023) Vyas et al.) 2023). Alternative limits, such as the recent μ-P paramcterisation (Yang & Hul 2021 fix this problem by altering the scaling of parameters. However, the μ-P line of work only lells us that feature/ feeture/reprrsentaaio reepresentation learning will happen, not what the learned paaturesreopreenntaiion will be. In contrast the DKM framework gives us the exact learned representations.
Applying fixed kernel functions to graphs is a well explored endeavour (Shervashidze & Borgwardt 2009 Kashima al. 2003 Shervashidze et al. 2009). Kernels can be defined directly for graphs and applied in a shallow fashion, shallow kernel can be stacked (Achten et al., 2023), ; or kernels can be used as component of larger deep learning algorithm (Cosmo al. 2021 Yanardag & Vishwanathan 2015). Our work differs fundamentally in that kernels themselves are learned, rather than learning features and then applying fixed
kernel.
3 Background
We give background on deep Gaussian processes (DGPs), and how under an infinite-width limit they become neural network Gaussian processes (NNGPs). We review how modifying this infinite-width limit gives flexible DKMs, in contrast to NNGPs which have fixed kernels. We also give an overview of the graph convolutional network (GCN) and the graph convolutional NNGP. These ingredients allow us to define a DKM in the graph domain, so-called "graph convolutional DKM". in Section 4
3

---

Published in Transactions on Machine Learning Research (05/2025)
3.1 Neural Networks as Deep Gaussian Processes
Consider connecco NN with inputs X R Px*,, outputs/labels Y R and intermediate-lyeer features Ff E PxN, By P we refer to the number of datapoints, Mo and UL+1 the number of input and output features respectively. The width of cach layer is denoted NVz, where is fixed, and N allows us to scale the width of all layers simultaneously. We compute features at each layer using the previous layer via F = o(F'-)) where W N are the weights and & is the pointwise nonlinearity (e.g. RcLU). With Gaussian prior on the weights, W2J ~N(0, Ni-1 ). the conditional distribution of features is given by:
P(F F= II N (() O, K fentures (F"-1)), A=1
(1a)
ML+1
P(Y F4)
II x=1
Ny 0, K features (FL) o²1),
(1b)
where Kreatures (X)
N. ((X)((XX and the subscript À refers to the Äth feature/column, so that F' = (f) fg ... )- Eq. is equivalent to a Bayesian NN, but in the above form is usually called
a deep Gaussian process (DGP) (Damianou & Lawrence, 2013 Salimboni & Deiscnroth 2017), alboit with an unusual kernel. We can generalize Eq. (1) to allow alternative kernels Kfeatures() such as the squared exponential kernel.
3.2 Deep Gaussian Processes in Terms of Gram Matrices
For certain kernel functions (e.g. arccosine kernels (Cho & Saul 2009) and RBF), features are un- necessary, and inter-layer dependencies in DGP can be summarised entirely by Gram matrices G = N F (F")T E PxP. For these kernels, we are able to compute the kernel from the Gram matrix alone, and thus there function over Gram matrices K(.) PxP - PxP such that K Kiatures (F²) K(G We can therefore rewrite the DGP in Eq. [ as,
Nr P(F G II O
(2a)
A=1
PL41
P(Y G
II N(y O
(2b)
where inter-layer dependencies in Eq. 2 are expressed using only Gram matrices. We can remove features altogether, and reframe the model purely terms of Gram matrices (Aitchison al. 2021).
P(G' G G² = W(G G No),
(3a)
P(Y G II W,'':,,('"')+o''
(3b)
x=
where W(V,n) is the Wishart distribution with scale matrix V and degrees of freedom (Gupta & Nagar 2018
3.3 Wide Deep Gaussian Processes
Consider a deep ReLU network. Bayesian inference over weights/features is not tractable, but remarkably, there is a tractable closed form solution if we take an infinite width limit. To see this, first observe that we
For avoidance of doubt, Krestures()) (-) RPN,, RxP computes the kernel from the features, while K(-) RPP RPXP equivalently computes the same kernel from the corresponding Gram matrix.
4

---

Published in Transactions on Machine Learning Research (05/2025)
calculate the kernel non-linearity without features; ReLU kernels are equivalent to arccosine kernels:
Cho & Saul (0099) showed that in the limit No 00,
ReLU
= lim
N. "(F") (F"
Karccos G
(4)
No
Further, the arccosine kernel is easily computable,
Vo (sin Oij + (I ((i)) cos) 0zj), where 0z = Gj
Karcens G)
(5)
VG
Secondly, Gram matrices become deterministic in wide networks, since they can be understood as an average of IID features, G¹ = N. EX= ( By Eq. (T or Eq. 2 the expectation of G conditioned on the previous layer is,
- while the variance scales with 1/N2. Thus, as we take an infinite- width limit, Ni- co, the variance goes zero, and the prior over the Gram matrix at layer L, G becomes deterministic and concentrated at its expectation, K(G--1). Thus, the kernel at every layer is a fixed deterministic function of the inputs that can be computed recursively,
K networkk (F") oK.... 90 lXx).
(6)
2 times
No where 1 XX" the kernel for the inputs, and F X. Setting L, we see that Eq. ( holds true at the output layer, implying that the outputs of a NN or DGP are GP distributed with fixed kernel in the infinite-width limit. This is known as the neural network Gaussian process (NNGP) (Lee et al. 2018).
3.4 Deep Kernel Machines
The clean analytic form of the NNGP kernel (Eq. 6 unfortunately has a big weakness: it underperforms finite-width counterparts empirically in many tasks (Aitchison 2020 Pleiss & Cunninghami 2021). The NNGP kernel is fixed function of imputs, meaning that no representation learning can occur, and the kernel cannot be shaped by the output labels. This is a big problem, since representation learning is widely understood to be central to the success of modern deep learning systems.
DKMs (Yang et al. 2023: Milsom et al. 2023 are a solution to the lack of representation learning in infinite- width NNGPs. DKMs can still be understood as an infinite-width limit of a DGP /NN, but the limit altered to retain flexibility and allow learning of representations. In DKM, Gram matrices are treated as learned parameters, rather than random variables as in DGP NNGP. (Yang al. 2023) derive the following "DKM objective" for colyecconeeteed networks that can be optimized with respect to Gram matrices G',
L
C(G G = logP G - Σ DeD.L. (NrO, | [[
Here, the likelihood term P(Y G²) measures how well the final layer representation G² performs at the task. Under the derivation of Yang et al. (2023). P(Y G²) is a likelihood for Gaussian process distribution over the outputs with kernel k The KL divergence terms are measure of how much the Gram matrices G G..... ..... G deviate from the NNGP. This can be seen due to the fact that negative KL divergence is maximized exactly when the two distributions it is measuring are equal, i.c. G = K(G"-1). The DKM objective trades off the marginal likelihood against the KL divergence terms, with the KL terms acting as a regularizer towards the NNGP. The amount of regularization depends on the V; coefficients, and as we send 14 + oo, the DKM becomes equivalent to the standard infinite-width NNGP. As v becomes smaller, we allow more ficxibility the Gram representations. Thus, through vi, the DKM gives us a knob to tune the amount of representation learning allowed in our model.
3.5 Graph Convolutional Networks and their Wide counterparts
Kipf & Welling 2017) derived Graph Convolutional Networks (GCNs) by applying approximations spec- tral methods graphs. Tn GCN layer, adjacency matrix A P x P is used to convolve (or 'mixup')
5

---

Published in Transactions on Machine Learning Research (05/2025)
intermediate layer nodes. Mathematically, GCN post-activations given by H' o0 6(AH ) where Å is normalized version of A.
Similarly to Section 3.2 it is possible to construct an NNGP for the graph domain. The pre-activations F of graph convolution layer are F' = W Again, placing IID Gaussian prior over our weights NA ~ (O, NL,, the NNGP construction tells us that as we make the layers wide (Ne - oo), the pre- activations become GP distributed with kernel matrix K = E[{(( We show in Appendix C that this expoctation has closod-form,
K= A
where $'-1= B is the NNGP kernel of a fully connected network (e.g. the arccosine kernel in the case of a ReLU network). Using this kernel in the NNGP defined in Eq. 0 gives the graph convolutional NNGP recursion,
G = AK ÁK(ÁK( A A.))
(9)
GCNs and graph convolutional NNGPs can be applied easily to node classification problems, since features or nodes are modelled directly. They can also be used for graph classification by applying mean pooling the output layer.
In Sections and 6 we consider homophily in graphs and its effect graph convolutional NNGP performance.
By homophily, we refer to edge homophily h E [0, 1], which is calculated as the proportion of edges (j. k) E that are wetween nodes with the same class.
4 Methods
In Section we have seen how graph convolutional NNGP kernels can be calculated. We have also seen how DKMs add flexibility to fully-connected NNGPs. We now combine these two ideas to obtain a flexible infinite-width graph network the 'graph convolutional DKM' and develop an inducing point scheme to allow training on large datasels.
3
4.1 Graph Convolutional Deep Kernel Machines
The graph convolutional NNGP suffers from the "fixed representation" problem that plagues all NNGP models
kernel is a fixed transformation of the inputs, regardless the target labels. This means that there is little flexibility (apart from kernel hyperparaaetters) to learn suitable features for the task at hand. To solve this problem we develop the graph convolutional DKM, which has learnable kernel representations at each layer.
We arrive at graph convolutional DKM by considering the Gram matrices in DGP with graph mixups,
Nr P(F F Fー II
O, AK(G
(10)
A=
where G - No-1 - FF p
By taking the representation learning limit the graph convolutional DGP, we show in Appendix A that the posterior over Gram matrices is point distributed; in other words, the Gram matrices are deterministic. Moreover, the Gram matrices maximize the graph DKM objective,
C(G = log P G Σ DeL (N(O, IIN.,
(11)
The objective in Eq. 11] can be interpreted as a fully-connected DKM, but with a modified kernel. Again, just. as in Section 3.4 trade-off the likelihood with the KL. divergence terms. That is, we trade-off

---

Published in Transactions on Machine Learning Research (05/2025)
the suitability of the top-layer representation for explaining the labels Y versus divergence from the graph convolutional NNGP. When xo in the DKM objective (Eq. 7 we recover the NNGP, and similarly for the graph DKM objective taking M/ + gives us the graph convolutional NNGP. Decreasing the coefficients Vy decreases the importance of the KL divergence terms, giving Gram matrices flexibility to deviate from the graph convolutional NNGP. In our experiments, we treat. the be as knobs for controlling the amount of representation learning. By measuring performance for different ve, we are able to cleanly demonstrate the importance of learned representations in various tasks.
4.2 Inducing-por point schemes
In practice is computationally infcasible to optimize the Gram matrices G G'...., G in the graph DKM objective for anything but modestly sized datasets, due to quadratic memory costs of storing the Gram matrices G and the cubic time costs. The KL divergence terms, for example, are expensive because of matrix inversions and log determinants:
(W((G() ( AK(G
((T((AK("")))) G log (oxcde(((A(("")))))) P).
(12)
We resolve computational issues by developing an inducing point scheme and enabling linear scaling with dataset size. Specifically, we suppose that the graph nodes X E Rx can be summarized sufficiently well by smaller inducing set X; 1Rx',, where the size of the inducing set P, is fixed and chosen to be much smaller than the full set of nodes (so that P. < P). These inducing inputs form an initial Gram matrix that we call G Pn x E ERAP. We also have inducing Gram representations at each layer, Gh...., G with all of these inducing representations being learned. The inducing representations are propagated alongside training/test Gram representations G......, G so that,
G
(13)
The inducing and training/ test points interact via the similarity matrix G (G E R and G and G are predicted according to our inducing point scheme, in a similar way to how training/ter features are predicted in an inducing point GP. We refer readers to Algorithm | for computational details.
The form of the inducing Gram matrices depends on the choice of inducing point scheme. The modeller must make choice to how the inducing graph nodes interact with the training/ter nodes. Broadly, we either consider intra-domain inducing points, which belong to the same domain as the data, or inter-domain inducing points which do not. We consider one scheme of each lype: an intra-domain scheme that assumes adjacency information between inducing coins/nnoess and training test nodes, and an inducing scheme that treats the inducing points as unconnected nodes in a graph.
We 'comnect' the inducing nodes to each other with an inducing adjacency matrix Ag Rx and 'connect' the inducing nodes to the training/ /tsst nodes with the adjacency Ati E R.P.P. We assume that the adjacency between train/test points is provided in the dataset, which we denote An for consistency. The two schemes are characterized by,
(1) Lintra-domaii sampling random subset S = (si...., sp,} of nodes from the dataset and treating these as inducing points. The inducing adjacencies become (A (An) = A (Au)) = A Aj.si
(2) (inter-domain) treating inducing nodes as independent of all other nodes, such that A - A, = 0.
We give forward propagation rules for each inducing-point scheme, and an ELBO objective (which is used for optimizing the inducing points and replaces the full-rank objective function from Eq. 11] in Appendix B.2 The computational cost of the intra-domain scheme is slightly higher, due to having to store A₁i and A and perform matrix multiplications with them. However this cost negligible compared to storing and computing with the Gram matrices themselves, and further mitigated by the fact that the adjacencics are sparse.
7

---

Published in Transactions on Machine Learning Research (05/2025)
G²
G
Initialization
xx XX'NNin
YY /Nout YNut
1.0
analytic
0.5
trained
Figure Normalized Gram matrices for a 2-layer linear graph DKM, providing verification of Eq. 14 We use input data, labels, and adjacency from a randomly selected 100 datapoint subset of Cora, and set the adjacency to be Ao.s- The leftmost and rightmost kernels are the input and label kernels respectively. The middle two columns
the hidden Gram representations. The top row shows Gram matrices after Wishart initialization, the middle shows the analytic solution, and the bottom row shows the results after training from this initialization by gradient descent with Adam.
We empirically compare both schemes in Appendix G across several node classification dataset, finding that neither is definitively the best. However, for some datasets (e-g. Citeseer) the inter-domain scheme is markedly better. Given that intra-domain inducing points are not applicable in multi-graph setting, and that the inter-domain scheme has simpler implementation, the inter-domain is preferable overall.
5 Analysis of Representation Learning in Linear Graph Convolutional Deep Kernel Machines
Remarkably, is possible to study graph convolutional DKMs analytically the linear kernel case, which gives insight into representation learning in graphs. Specifically, if we use a linear kernel (K(G) G), set the regularization to (n for all E), show in Appendix D that the Gram matrix representations optimizing the graph convolutional DKM objective at each layer are given by,
Gº À A (A- LGG+IA À
A) -
(14)
Here G and G++1 are the input and output kernels respectively (and are assumed to be known). We provide numerical verification of Eq. [4] by comparing it to a solution obtained via gradient descent in Figure
To ensure that the normalized adjacency is invertible, we compute Eq. 14 using A, place of A, which interpolates with the identity matrix a paramcter À E [0, 1).
A = AK (1 A)Å.
(15)
8

---

Published in Transactions on Machine Learning Research (05/2025)
A-0.1
0.8
0.5
0.8
0.5
Figure 2: Final layer kernels for 2-layer linear graph convolutional DKMs (top row) and graph convolutional NNGPs (bottom row). The models are fit toy dataset with Gaussian random imputs and an Erdös- Rényi adjacency (50 nodes, and edge probability 0.1). The label kernel is shown in the right column. The remaining columns show the effect of varying A.
0.55
p- 10. CKA-0.51
1000. CKA-D.30
y CKA-D27
1.0
0.8
0.6
0.4
0.2
0.0
1, C5A-0
リ- 10. CKA-024
0-1000,
y- CKA-020
1.0
0.8
0.6
Roman
0.1
02
0.
Figure 3: Final layer kernels Cora and Roman Empire kernels for different regularizations v. The kernels are formed from 400 nodes sampled at random, and the 'true' label kernel is shown the rightmost column.
It is very natural to introduce this modified adjacency matrix in the graph setting, which incorporated by other prior work (Laan et al. 2020p. In particular, with À 0, the graph mixup/convolutin performs an equally weighted average over itself and all adjacent nodes. This can be problematic. For instance, consider a network consisting of two connected nodes. After a single graph mixup, the two nodes will have the same be desirable. To fix this issue, we can use 0, which implies that the graph
features, which is unlikely mixup is now a weighted average, with more weight on self-features. This fixes the issue with our simple example network with two nodes: the resulting features different even after graph mixup.
We sought to compare the linear graph convolutional DKM kernel to the linear graph convolutional NNGP kernel,
G = A
(16)
While is not practical to calculate Eq. (14) for large clttasets (due to the inversion of a large adjacency matrix), a comparison still possible with small datasots. We compare the two kernels on randomly generated an Erdös-Rént graph (Erdos Rényi 1963) dataset of 50 nodes (with Gaussian features), and insert edges between nodes with probability 0.1. Half of the nodes given positive label and the

---

Published in Transactions on Machine Learning Research (05/2025)
Cora (h=0.81)
Pubmed (h=0.8)
Reddit 0.76)
Citeseer (h=0.74)
Minesweeper (h- 0.68)
84
97
80
96
70-
78-
94
66-
76
79
92
64.
91-
74
62
76-
10
10:
Arxiv (h=0.65)
Tolokers (h=0.6)
Penn94 (h=0.47)
BlogCatalog (h=0.4)
Amazon Ratings (h=0.38)
72
75
70
80
46
65-
Val
60
78
76-
66
55
74
10
10:4
10a
10a
10
10a
Chameleon (h=0.22 0.24)
Flickr (h=0.22)
Squirrel (/=0.22)
Roman Empire (h=0.05)
60
54
55
60
55
45
Val
50
40
45
42
40
35
10-4
10a
10"1 10a
10-4
10a
10a
10:
16a
Figure 4: Validation accuracy at different regularization strengths (v) for each node classification dataset. The datasets are arranged by homophily ratio (denoted by h). The error bands denote +1 standard deviation in the validation accuracy over several random seeds. For cach subplot, we ensure the y-axis range is at least 8, so that the effect of v is comparable between dataset.
remainder negative label. We calculated the output layer kernels for À (0.1, 1}, and depict results in Figure 2 Note that the Erdós-Rényí adjacency is not homophilous, because an edge is equally likely between both nodes with the same class and with a different class.
We see Figure (bottom row) that none of the graph convolutional NNGP kernels are aligned to the output kernel, YY This bocause the graph convolutional NNGP kernel is deterministic function of the inputs and adjacency, and is not learned based on the labels, Y. In contrast, the DKM is well-aligned with the output (Figure top row). Note find that increasing À improves alignment of the graph convolutional
10

---

Published in Transactions on Machine Learning Research (05/2025)
DKM kernels to the output kernel. As À + 0, the adjacency matrix becomes singular, and it seems that this also involves a loss of representation learning, as the graph structure dominates the representation.
6 Experiments
In this section we investigate the effect of representation learning in graph networks by training graph convolutional DKMs on several datasets. We train on node classification datascts with varying homophily, as well as graph classification datasets. Our experiments show that representation learning helps to shape output kernels, and that datasets with lower homophily benefit more from representation learning than datasets with high homophily. We also compare the performance of graph convolutional DKMs to GCNs and graph convolutional NNGPs, and find that the extra flexibility afforded by the DKM framework closes the performance gap between graph convolutional NNGPs and GCNs.
In all experiments we use the ReLUU/rccossiee kernel non-linearity, and set the regularization such that it constant for all layers.
6.1 Deep Kernel Machines Allow Shaping of Kernel Representations
Similarly to the fully-connected DKM (Yang et al. 2023 Section 4.6), we demonstrate in Figure 3 that the graph convolutional DKM shapes final layer kernel representations towards the label kernel, YY We show aligmment both qualitatively via the top-layer kernels, and quantitatively with the Centered Kernel A Alignment (CKA) (Cortes et al. 2012) metrie. CKA is measured by,
CKA(KI, K2) KT K,)
(17)
where K1/2 are centered version of the kernels K 1/2 to be compared. Higher CKA values indicate greater similarity wetween representations, with CKA(K,, K2) E [0, 1].
For this experiment, we trained graph convolutional DKMs for different values v E {10", 10", 103, co on Cora and Roman Empire with the same random seed for 300 epochs. The models were trained using simple 2-layer architecture with no residual comnections or normallization/ceneerii layers, and we used The most suitable inducing point schome
normalized adjacency Ax=0.3 for the graph convolutions/mixnn was determined by a hyperparameter sweep over schemes for each dataset (see Section 6.2 and Appendix D for details). The kernels shown were obtained by taking the kernel representations of a randomly sampled 400 node subset of the last hidden layer, and the CKA similarity measure calculated the full final hidden layer kernel.
When & is or 10, we clearly see block-diagonal structure mirroring YYT indicating "kernel alignment." As y increases to 1000 or oo, flexibility decreases and the kernel alignment appears to become weaker, and is confirmed by the CKA statistics. Interestingly, this brcakdown seems to involve all outputs becoming correlated, which is indicative of the rank-collapse-like phenomenon described by Oono & Suzuki (2019).
6.2 Investigating the Relationship Between Homophily and Representation Learning
The graph convolutional NNGP kernel has a natural inductive bias for homophilous datasets; the graph convolutional NNGP pools representations from adjacent nodes, therefore in the extreme case that the connected components of the graph correspond to exactly the class labels, we expect its kernel to align with the labels. We expect the graph convolutional NNGP to be less effective for heterophilous datasets, because the graph structure is not informative for the labels. However, representation learning should help in the heterophilous case because we showed in Section 6.1 that increasing flexibility helps shape the kernel representations.
We test the effect of representation lcarning empirically, training graph convolutional DKMs on several node classification benchmark datasets that exhibit varied levels of homophily. The dataset statistics can be found in Table We trained with different regularization strengths, E (0, 10-2, 10-1, 100, 10 102, 103)
11

---

Published in Transactions on Machine Learning Research (05/2025)
Mean test accuracies (%) one standard deviation on node classification datasets. Datasets are sorted by homophily, with most homophilous datascts at the top. We provide results for graph convolutional DKMs (GCDKM), graph convolutional NNGPs (GCNNGP) and GCNs. The best accuracy for each dataset is bolded. For datasets with multiple splits, the standard deviation is calculated using the means over splits. In some instances, the best graph convolutional DKM had V = co, which is denoted by (+) (hence the sparse GCNNGP results are identical), and (f) denotes graph convolutional NNGP results from Niu et al. 2023
Table 1:
GCDKM
sparse GCNNGP
GCNNGP
GCN (no dropout)
GCN
Cora
81.1 0.2
80.8
82.8
80.6 10.6:222 0.2
81.1 + 0.3
Pubmed
09.8:0.22
7.2
79.61
79.4 0.2
79.5 0.1
Reddit
0.0
0.0
94.7 0.0f
95.3
95.8 0.1
Citeseer
+.47
7..7
69.51
71.7
71.7 0.2
Minesweeper
0.4
0.3
0.4
85.6 0.4
Arxiv
0.2
0.2
70.1 + 0.1
0.1
70.6 0.2
Tolokers
0.4
0.1
0.7
82.2 0.7
Penn94
0.2
0.3
81.2
81.5 + 1.8
BlogCatalog
0.5
0.5
0.6
94.1 = 0.6
Amazon Ratings
0.5
0.8
0.5
49.8 = 0.6
Flickr
85.7 0.6
212
2.0
82.6 0.7
Chamelcon
68.9
6.11
65.3
65.3 2.6
Squirrel
56.8 1.4
38.6 + 1.2
57.3 1.4
57.7 1.4
Roman Empire
7
73.6 0.3
79.9 = 0.5
82.8 0.5
Table 2: Average accuracies (%) + one standard deviation on graph classification datasots. Error bars
are not statistically significant. GCN accuracies soureed from Zhang et al. (2099 (*) and 2020 (i).
Yang et al.
GCDKM
sparse GCNNGP
GCN
Mutag
3.8
80.8 5.5
85.6 +: 5.81
NCI1
75.3
66.5 1.0
76.3 + 1.8*
NC1109
75.2
65.9
75.9 + 1.8*
Proteins
7.22
67.6
75.2 3.6*
Mutagenicity
7.71
7.17
79.8 1.6*
to control the amount of representation learning. We also trained with two inducing point schemes (detailed in Section 4.2 and for each dataset we selected the optimal scheme by calculating mean validation accuracy for each and scheme. We used a 2-layer architecture, with the adjacency renormalization described by Kipf & Welling (201)) and no residual connections or normalization layers.
Figure illustrates the empirical differences between NNGPs and DKMs, which we find be highly dataset- dependent. For homophilous datasets (see top row of Figure 4 like Cora, performance tends remain relatively stable are well-suited to these tasks. In contrast, heterophilous datasets such as Roman Empire benefit greatly from smaller и (i.c. increased ficxibility). This aligns with our thcoretical understanding, as DKMs converge to NNGPs in the limit μー oc. The lack of representation ation learning in NNGPs becomes particularly problematic for small h (bottom row), leading to dramatic declines in accuracy at least ~00% when comparing μ= 1 v= 1 This suggests that for heterophilous tasks, where standard architectural inductive biases are less appropriate, the graph convolutional DKM's ability to learn representations allows it to compensate, while the graph convolution NNGP's inability to do results in poor performance.
improve with larger v, suggesting that the standard architectural inductive biases
12

---

Published in Transactions on Machine Learning Research (05/2025)
6.3 Final Results
To assess overall performance of the graph convolutional DKM, we optimized hyperparameters for each dataset with a series of grid searches on a range of node and graph classification datasets. We kept the number of layors fixed at 2, and scarched over inducing scheme, V, architocture, kernel centering, and finally
the number of inducing points. The final test accuracies are shown in Table and Table 2 details of the datasets and the training procedure in the Appendix F.2
We provide
In Table 1 we see that the graph convolutional DKM performs similarly to the graph convolutional NNGP for homophilous node classification datasets, but less for heterophilous datasets. We also see that the graph convolutional DKM performs similarly to the GCN for most datasets, closing the performance gap between infinite-width and finite-width networks. We attribute the instances where the GCN outperforms the graph convolutional DKM to dropout, as test accuracy of the graph convolutional DKM is similar to the GCN without dropout. We also provide full-rank graph convolutional NNGP accuracies (where applicable) from Niu ct al. (2023). Their graph convolutional NNGP results are slightly different ours, most likely because ours is sparse model with learned inducing points, whereas theirs is treated like conventional GP.
In Table 2 we find that graph convolutional DKM performance is competitive with the GCN on graph classifications benchmarks, and uniformly better than the NNGP. The superior performance versus the NNGP is perhaps expected; the graph classification datasets are all molecule datasets, which tend to exhibit a mixture of homophily and heterophily (Ye et al. 2022 and thus the flexibility of the DKM ought to be very helpful.
Overall, find that the graph convolutional DKM closes the gap between the NNGP and the GCN, supporting the hypothesis that representation learning is the key element lacking from the NNGP. This appears to be true regardless of task (e.g., node classification or graph classification). Further, our results demonstrate that the NNGP is well-suited to homophilous tasks, thus explaining why it is possible to obtain strong NNGP performance on some benchmark graph tasks (Niu et al. 2023), despite NNGPs generally being considered inferior GCNs.
7 Limitations
The key limitations of graph convolutional DKMs, like kernel methods in general, is scaling to large dataset sizes due to the cubic cost of naive methods. While we implemented an inducing point scheme to circumvent this limitation, it may be possible to improve on these methods.
Our current analysis considers standard graph convolutional architectures. While it is theoretically possible to develop DKM extensions by "kernelizing' alternative graph architectures (Bo et al. 2021 Chien al. 2020; Velicković al.) 2017), these extensions are non-trivial and beyond the scope of this work. We speculate that such extensions would improve performance across all methods (graph convolutional DKM/NNGP, and GCN) by incorporating additional inductive biases. The impact might be most pronounced for NNGPs, which lack representation learning capabilities and thus rely more heavily on built-in inductive biases. In contrast, graph convolutional DKMs and GCNs can compensate for imperfect inductive biases through representation learning.
8 Conclusion and Discussion
By leveraging the DKM framework, have developed flexible variant of an infinite-witth graph convo- lutional network. The graph convolutional DKM provides hyperparameter that allows us to interpolate between a flexible kernel machine and the graph convolutional NNGP with fixed kernel. This feature of the DKM enabled us lo examine the importance of representation learning on graph node classification tasks, and show competitive performance on graph classification tasks. Remarkably, we found that some tasks benefit more from representation lcarning than others. This finding helps explain the fact that NNGPs have previously been shown to perform well on graph tasks, but not in other domains. Moreover, the fact that our graph DKM model performs similarly to GCN without dropout suggests that the kind of flexibility
13

---

Published in Transactions on Machine Learning Research (05/2025)
introduced by the DKM is the sensible kind, and may be used to advance kernel methods in the era of deep learning.
Despite using an inducing point scheme, computational cost of the graph convolutional DKMs is still rela- tively high. We expect that improving computational efficiency can help improve performance, as would allow for easier architecture exploration, and training of bigger models. We also expect that more careful optimization could boost performance even further since efficiency gains could enable larger models and longer training. However, leave these issues for future work.
14

---

Published in Transactions on Machine Learning Research (05/2025)
References
Sonny Achten, Francesco Tonin, Panagiotis Patrinos, and Johan AK Suykens. Semi-supervised classification with graph convolutional kernel machines. arXiv preprinl arXiv:2301 1376, 2023.
Ben Adlam, Jachoon Lee, Shreyas Padhy, Zachary Nado, and Jasper Snock. Kernel regression with infinite- width neural networks on millions of examples. arXi preprinl arXiv:2303.054 2023.
Laurence Aitchison. Why bigger is not always better: finite and infinite neural networks. In ICML, 2020.
Laurence Aitchison, Adam Yang, and Sebastian W Ober. Deep kernel processes. In International Conference on Machine Learning. PMLR, 2021.
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspec- tives. IEEE transactions on pottern analysis and machine intelligence, 35(8):1798 1828, 2013.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolu- tional networks. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 1050-9500330 -955,, 2021.
Blake Bordelon and Cengiz Pehlevan. Self-consistent dynamical field theory of kernel evolution in wide neural networks. Journal of Statistical Mechonics: Theory and Experiment, 2023(11):114099, 2023.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. Xie preprint OrXim:2006.0700 2020.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. Advances in neural information processing systems, 2009.
Corinna Cortes, Mchryar Mohri, and Afshin Rostamizadeh. Algorithms for learning kernels based on centered alignment. The Journal of Machine Learning Research, 13:795 828, 2012.
Luca Cosmo, Giorgia Minello, Michael Bronstein, Emanuele Rodolå, Luca Rossi, and Andrea Torsello. Graph kernel neural networks. arXiv preprint arXbv:2112.07496, 2021.
Andreas Damianou and Neil Lawrence. Deep gaussian processes. In Artificial Intelligence and Stalistics, 2013.
Paul Erdos and Alfréd Rényi. Asymmetric graphs. Acto Math. Acad. Sci. Hungar, 14(293-315):3, 1963.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Adrià Garriga-Alonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional networks shallow gaussian processes. orXiv preprint arXiv:1808.00 05587, 2018.
Arjun K Gupta and Daya K Nagar. Malria variale distributions. Chapman and Hall/ 2018.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. Advances in neural information processing systems, 2017.
Jilin Hu, Jianbing Shen, Bin Yang, and Ling Shao. Infinitely wide graph convolutional networks: semi- supervised learning via gaussian processes. arXiv preprint 1rXi::2002.12163 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. Advances in neural information processing systems, 33:22118 1221233, 2020b.
15

---

Published in Transactions on Machine Learning Research (05/2025)
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and generalization in neural networks. In NewrIPS, pp. 1880-8589 2018.
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the 20th international conference machine learning (ICML-03), pp. 2003.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. Inter- national Conference on Learning Representations, 2017.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521((553)):366 444, 2015.
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl- Dickstein. Deep neural networks as gaussian processes. arXiv preprint arv: 111: 711000165 2017.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jelfrey Pennington, and Jascha Sohl- Dickstein. Deep neural networks as gaussian processes. International Conference on Learning Represen- tations, 2018.
Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. Advances in Neural Information Processing Systems, 33:15156 15172, 2020.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning non-homophilous graphs: New benchmarks and strong simple methods. Advances in neural information processing systems, 34:20887 209002, 2021.
Sitao Luan, Mingde Zhao, Chenqing Hua, Xiao Wen Chang, and Doina Precup. Complete the missing half: Augmenting aggregation filtering with diversification for graph convolutional networks. orXiv preprint arXiv:2008.0S8 08844. 2020.
Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao-Wen Chang, Jie Fu, Jure Leskovee, and Doina Precup. When do graph neural networks help with node classification? investigating the homophily principle on node distinguishability. Advances in Neural Information Processing Systems, 36, 2024.
David JC MacKay et al. Introduction to gaussian processes. NATO ASI series F computer and systems sciences, 168:133-1666 1998.
Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard Turner, and Zoubin Ghahramani, Gaus- sian process behaviour in wide deep neural networks. ar preprint arXiv: 112711 2018.
Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Improving graph neural networks with simple archi- tecture design. orXiv preprint Xrx:::2105.019 0766444, 2021.
Edward Milsom, Ben Anson, and Laurence Aitchison. Convolutional deep kernel machines, 2023.
R. M. Neal. Bayesiun Learning for Newral Networks, Vol. 118 of Leclure Notes in Statistics. Springer- Verlay, 1996.
Zehao Niu, Mihai Anitescu, and Jie Chen. Graph neural network-inspired kernels for gaussian processes in semi-supervised learning. arXiv preprint ar arXiv:2302.05: 05828, 2023. In press.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohi-Dickstein. Bayesian deep convolutional networks with many channels gaussian processes. ar preprint orXiv:1810.05144 2018.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classifi- cation. arXiv preprint arXiw:1905.10944 2019.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. crit- ical look at the evaluation of gnns under heterophily: are we really making progress? orXiv preprint arXi::2302.118 116400 2023.
16

---

Published in Transactions on Machine Learning Research (05/2025)
Geoff Pleiss and John P Cunningham. The limitations of large width in neural networks: A deep gaussian process perspective. Advances in Neural Information Processing Systems, 34:3349-3333 3363, 2021.
Hugh Salimbeni and Mare Deisenroth. Doubly stochastic variational inference for deep gaussian processes. Aduances in neural information processing systems, 2017.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61 10006618000011 2008.
Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich-Keil, Jonathan Ragan-Kelley, Ludwig Schmidt, and Benjamin Recht. Neural kernels without tangents. In International conference on machine learning, pp. 8614 8123.. PMLR, 2020.
Nino Shervashidze and Karsten Borgwardt. Fast subtree kernels graphs. Advances in newral information processing systems, 22, 2009.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pp. 488 495, PMLR, 2009.
Petar Velicković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710. 10903, 2017.
Nikhil Vyas, Alexander Atanasov, Blake Bordelon, Depen Morwani, Sabarish Sainathan, and Cengiz Pehlevan. Feature-learning networks are consistent across widths at realistic scales. aiv preprint arXiv:2305.144 18411, 2023.
lan Walker and Ben Glocker. Graph convolutional gaussian processes. In International Conference Machine Learning, pp. 6495-6504. PMLR, 2019.
Christopher Williams. Computing with infinite networks. In M.C. Mozer, M. Jordan, and T. Petsche (eds.), Advances in Neural Information Processing Systems, volume 9. MIT Press, 1996. abbsscee0000sseccerr066775555-
URL https: http::///pooeecnn.nnoorrrreeeeee http:ppp...pppppeeffoe//////eeee fillss/paper//199///eee.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedinggs of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, 2015.
Adam X. Yang, Maxime Robeyns, Edward Milsom, Nandi Schoots, Ben Anson, and Laurence Aitchison. A thoory of representation lcarning in deep neural networks gives a deep genoralisation of kernel mothods.
International Conference on Machine Learning, 2023. In press.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint crXic:1902.04790 2019.
Greg Yang and Edward J. Hu. Tensor programs IV: feature learning in infinite-width neural networks. In ICML, volume 139 of Proceedings of Machine Learning Research, pp. 11727-11737. PMLR, 2021.
Yiding Yang, Zunlei Feng, Mingli Song, and Xinchao Wang. Factorizable graph convolutional networks. Advances Neural Information Processing Systems, 33:20286-20222 2020.
Wei Ye, Jiayi Yang, Sourav Medya, and Ambuj Singh. Incorporating heterophily into graph neural networks for graph classification. arXiv preprint arXiv:2203.070 076688 2022.
Zhen Zhang, Jiajun Bu, Martin Ester, Jianfeng Zhang, Chengwei Yao, Zhi Yu, and Can Wang. Hierarchical graph pooling with structure learning. arv preprint arXio:1911.05554, 2019.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-788 7804, 2020.
17

---

Published in Transactions on Machine Learning Research (05/2025)
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the A AAT conference on artificial intelligence, volume 35, pp. 11168 11176, 2021.
18

---

Published in Transactions on Machine Learning Research (05/2025)
A Full Rank Graph Convolutional Deep Kernel Machines
Here, we outline derivation for the graph convolutional DKM objective. We start with DGP with graph mixups,
Nr II A=1
P(F
N( O, AK fentures (F
(18)
where f are columns of features,
F' (f) ....N)))
(19)
We take P to be the number of datapoints, and N₂ the number of features at each layer E, so that F E PRNN
The log- pog-oottrror over Gram matrices G = ,, F (F")T is equivalent to,
logP(G",.... "P..."....,G' G² X, Y) P(Y G²) + log P(G G)
(20)
with GD the being a kernel formed from the inputs X. Following Section 3.2 we assume that Kisatures (.) is a
kernel function that can be calculated in terms of Gram matrices, i.e., 3 such that K(G') = Keaturre (F*).
Examples of suitable kernels are the arccosine kernel (Cho & Saul 2009) the squared exponential kernel.
Since Fe is multivariate Gaussian, G is Wishart distributed by its definition, and write down its log density,
log P(G' [G* NePf-1 log G
No 2 log A
"T((AKG" G az.
(21)
The constant ag is the normalizing constant, and we assume that is full rank. Yang et al. 20023 showed that a satisfies the following scaling law as we increase width: lim ae/Ne = const. Therefore if N₂- = Nve, follows that,
log P(G' /G = const + DRL (N GO) (1, AKG
lim N
(22)
The Bayesian representation learning limit Yang et al the hidden layers (this is unlike the usual NNGP limit (Lee et al. 2017) which only scales the intermediate
2023) dictates that scale the final layer alongside
layers). To do so, we duplicate the outputs so that there are N copies of the labels, i.e. Y -Y Since channels are assumed to be ii.d., we have,
P(Ý ( P(Y GMyN.
(23)
We now consider the posterior this network with wide hidden layers, wide outputs, and labels Y. Com- bining Eqs. 20
22 and 23 and letting N₂ = Nus, we have that the scaled og-possteror over Gram
matrices satisfies
Noc N P(G' ,...., G I
lim 1
Ply G²) + Σ V.DII.
const
= L ".G',...,G")
(24)
Finally, assuming that the features are sufficiently well-behaved, we note that the Gram matrices are deter- ministic in the limit + oo, since they are sum of i.i.d. terms,
No
Gº
No Σ ((T)T
= lim G = const.
(25)
A=1
19

---

Published in Transactions on Machine Learning Research (05/2025)
The consequence of Eq. 25 is that the limiting posterior of the Gram matrices is point distribution. But we know that the Gram matrices on which this point distribution is centered on should maximize the posterior, and hence the scaled logsposterior. Therefore, we seek to maximize Eq. (24). the scaled log-posterior. This is exactly the graph convolutional DKM objective we declared in Section up to an additive constant.
B Inducing Point Approximations
The graph convolutional DKM objective is difficult to optimize directly due to quadratic memory costs and cubic time complexity. To avoid these large costs, we use an inducing point approximation similar to the one described in (Yang et al. 2023). We review in this Appendix how to construct an inducing point objective in fully-connect setting, and then extend the graph setting.
B.1 An Inducing Point Objective
Sparse DKMs as derived by Yang et al. 2023 are inspired by the sparse DGP literature (Damianou &
Lawrence 2013 Salimbeni & Deisenroth 2017). In essence, we place an approximate posterior on a set of
sparse inducing poecing-points/e points/leaturee /eeatures and derive an objective to optimize these inducing points by finding a lower bound on the evidence with variational inference (VI). In this subsection we describe the procedure.
We introducing some inducing- points F. RRxN in addition to the 'real' tost/training features F E RRxNN at each layer in the following prior model,
F
F
(26a)
F
N₂
P(F
F
II
N(F O. K features (F)-1)),
(26b)
A=1
P(W) II (w 0,I). A=1
(26c)
P(Y K², W) II sote -IW)) -W)),,
(26d)
where KL is the kernel applied to the final hidden layer features FL, with K being the inducing/indducing sub-block and K being the training/ htrg://esttinucing sub-block. Eq. (26) is similar to the DGP in Eq. ①
but it has a different top-layer. The motivation for using the top-layer in Eq. (26) is efficiency; it is more efficient than a categorical GP under the paramotcrization described in Appondix
To perform variational inference, we place a Gaussian approximate posterior on the inducing hidden-layer features,
N Q(F = II ((((F)x; Gu),
(27)
A=1
and the following approximate posterior on the top-layer,
#2+1
Q(W) II N(WAi E).
(28)
Thus, G..,.., Gli, Mer4s and Σ are the variational parameters. We can write down the distribution of the test ttaining features conditional on the inducing feat ures using standard multivariate Gaussian rules,
P(F F F-11) N (F:: K,KK F. K.K Kn).
(29)
20

---

Published in Transactions on Machine Learning Research (05/2025)
where by Ki, Ku, and Ku refer inducing-inducing test/train-inducing and test test/train-test/ traainttsst/triin /train blocks respectively of ((F(-1). We use Eq. [29 to construct an approximate posterior over the test/ /raining
features. The prior at each layer is equivalent to,
P(F F1"1)) = P(F F. F P(F | 1)
(30)
and we select the full approximate posterior at each hidden layer to be
Q(F Fー = P(F F Q(F)).
(31)
This choice of approximate postcrior a classic one; the common term, P(F F F"-)), is going to lead cancellation in the ELBO. At the top layer, we use an i.i.d Gaussian approximate posterior for the weights W,
ML Q(W) II N(wx: E). A=1
(32)
Similarly to Eq. (33 in the full-rank derivation, we duplicate the entries in the top-layer N times and make an i.idd assumption, such that Y (Y.... Y) E RRNNNLL+1 and WWWW... W) E RRXNNL+ Note that both the prior and the approximate posterior factorize across layers, which allows us to simplify the ELBO,
P(Ý.X.F'
F", W)
ELBO = EQ
log
(33a)
Q(F
F'
W)
P(Ý, W F4)
P(F F(-1)]
EQ
log
Σ log
(33b)
Q(W)
Q(F4)
P(Ý, W K-)
P(F F
= =Eq log
EQ
log
(33c)
Q(W)
Q(F))
In the limit N - co, where N:- Nve, the covariances each layer, N₂ (F")", collapse to become equal to G It can be shown that the hidden-layer terms in the ELBO simplify,
P(F F
UKL (NCO, G() [1
log
(34)
Q(F()
Additionally, VN the term involving Y satisfies, K Q(W)
N log
1
E
P(Ý, W
Eq logp(( K², W) + log Q(W)
P(W)
(35a)
#4+11
Eqllog P(Y K w)]
Σ
DKL (N 2) || 1),
(35b)
which can casily be estimated by sampling W, since in the limit the kernel K' = K(G is constant.
We define the sparse DKM objective to be the limiting ELBO scaled by N-1,
lim ELBO = Luparse = Bollog P(Y K(G²), W) N N
2111
DKL. (N(1 E) || (((
(36)
Σ DeL (N(O,G)) |I [I
21

---

Published in Transactions on Machine Learning Research (05/2025)
Notice that the likelihood term in Eq. tells us that,
36 requires the full kernel. We calculate this recursively. Eq.
29
F = K, Ff + (Kt K 1
(37)
where is a matrix ii.d. standard Gaussian noise, and - K(G [Ki Kiti K Ku.. Therefore,
G = lim N₂ (F( K
(38)
G = lim N. Ni
(F) = Kit KK Kn + K.K K Kin.
(39)
B.2 Sparse Graph Convolutional Deep Kernel Machines
To use a graph convolutional DKM, we need to be able to compute the graph kernel G H> AK(G)A" with our inducing points. We already have adjacency information regarding the training/tesi nodes, but not the inducing nodes. Therefore we assume we have an adjacency between inducing points, As, as well as adjacency information between inducing points and training/ test points, Aic = A For notational consistency, we denote the adjacency of the data Au-
The graph convolutional kernel over Gram matricos when using an inducing scheme becomes
A Ait
Aii
Ait
KGo(G)=
K(G)
(40)
Ad
Au
Adi
Au
where K(G) "base kernel" (e.g. the arccosine kernel) applied to G. We derive this kernel for an graph convolutional NNGP concretely in Appendix C of the sparse DKM in Eq. 336 gives a sparse graph convolutional DKM objective,
Substituting this graph kernel into the intermediate layers
LGC-sparse
Ewwoloogg P(Y P(Y
K(G*), W)]
UL+1
Σ DKL. (M Σ) I)),
(41)
Σ DDL (N(O, || (NOO
Again, the Gramn matrices are calculated recursively in the forward pass with,
G Kü; G
(42)
G = Ktt - K,K, Ku + K,JK, K. KK,,
(43)
and we then apply the graph convolutional kernel Kec(-) G = =G G G G We considered two choices for Aū and Au/ An,An namely
(1) (intra-domain) using adjacency information from inducing points sampled from the training set,
(2) (inter-domann) treating inducing points as independent of other inducing points and the training/test points, Lee. A₁ = A, 0.
In the where the dataset is single graph, all nodes in the graph. In the case where the datasct contains several graphs, the graphs can be batched together. Naively, this would involve creating a single large adjacency matrix that describes adjacency information for graphs in the minibatch, but in practice this can be efficiently represented with a sparse tensor. The inter-domain scheme has the advantage that can be used for datasets with a single graph or multiple graphs, whereas the intra-domain scheme not expected to work when we change the graph batch (in the multi-graph case).
minibatch size of 1, and the 'minibatch' becomes
22

---

Published in Transactions on Machine Learning Research (05/2025)
C Graph Convolutional NNGP Kernel Derivations
We show how to derive the kerne/covariiacce expressions given in Eq. (40) (for the sparse inducing point case). Eq. ( (for the full-rank case) is the same, but with inducing points dropped.
We take the graph nodes to have adjacency information as described in Section 4.2 and Appendix B
graph convolutional NNGP, pre-activation features F, FÚ for the inducing and test/train blocks can be written in terms of the post-activations H H
F F
Ai
A Aut
W,
(44)
Ar
H
where W E R-N--1XM has i.i.d. Gaussian elements with mean zero and variance 1/Ne-1- Remember that each column À of Fe is ii.d., the covariance of F is,
Kn
K
E
(45a)
Ki
Ku
Aii
Ait
H
B(wAwS w
E
H
Ai
A
T
(45b)
Au
Au
H
H
Au
Au
Ai
Ait
Aii
Ait Au,
T
(45c)
Au
Att
N
H
H
A
This is the general form of the graph convolutional kernel. However, the activation function ReLU, i.e. (H" ((K--l), where 4(-) is arecos kernel
H RF", then in the limit Ne-1 + 20, N Cho & Saul 2009 and Kf-1 is the previous layer's ' kernel. This gives the recursive relation
K K
K
Ai
Ast Au
K K ti
Ai
Aic T
in K
(46)
K
Au
Au
Au
We call this kernel the graph convolutional kernel.
C.1 Sparse Graph Convolutional Deep Kernel Machine Algorithm
For completeness, we provide Algorithm to demonstrate node prediction with the sparse graph convolu- tional DKM. We discuss how to parameterize the learned inducing points for training in Appendix [ The algorithm can be modified for graph classification by adding a mean-pool layer immediately before sampling.
For the 'sample' step at the top-layer, we have two main options. The first, most conventional method, is to sample with a sparse GP (similar to Milsom et al. (2023)). The second, which the approach taken in this paper, is to sample weights W from the approximale posterior (Eq. 28 which in turn allows sampling logits by calculating K,,cho((K,) e x
23

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm Graph convolutional DKM node classification
Parameters: {uE}ē=I
Train/test inputs, train labels: X, Y,
Inducing and train/tess adjacencies: Au; Ati, Au
Inducing inputs and inducing Gram matrices: X,, {G L+1
Variational parameters for the output layer: -1 Muz
Initialize full Gram matrix G
X
X
G
G
X X,X!)
for fin (I....,L) do
Apply kernel non-linearity & and perform graph convolution G
Ka Knt)
+ As
An Att
))
(G
G G
(A
Au
T
Ku
Kut
Au
Au
Att
Propagate the test-test and test-inducing blocks
G K K G
G Kt K KR K G K₁
end for
Calculate output kernel Kn
Knt) Kü Ku
G
+
Perform prediction using a sparse GP (or alternative model) with outpul kernel
Y + sample P(Y Ki, Ku. K.,)
D form Solution for Linear Graph Convolutional Deep Kernel Machine
For some node regression problems with a linear kernel, K(G) G, are able to find an optimum for the DKM analytically. Assuming constant regularizer coefficient for each layer, 1, and no observation noise, the objective L for a lincar graph convolutional DKM is,
L+1
L(G (G.....,G))=
Σ
DKL(W G.) (1, AKG-))A))))
(47a)
L+1 Σ
const +
logl (AAGG-IA""
TT((AG " "'))
(47b)
2
A slight abuse of notation follows, in that superscripts & on G and Z' refer to values at the l'th layer, but elsewhere, superscripts for example on A refer to powers of Å, so that A A... A.
For objective Eq. (47 to make sense, we must assume that the normalized adjacency matrix, A, is invertible. In practice, Å may not be invertible, but we can resolve this by interpolating it with the identity,
Å AI + A)Å, X E (0, 1).
(48)
With this adjustment to the adjacency matrix, we can simplify the objective:
L+1
C(G) ...., G = const-
2 E "
(49)
From here, we drop the transposes because À and G are symmetric. We take gradients:
ØL ..... GL) θ
(50a)
8G a
2 -AAG e-1 - - -1(G))-1))
-
(50b)
24

---

Published in Transactions on Machine Learning Research (05/2025)
Then set those gradients to zero:
G'A (G - A-
(51)
For convenience, define, z' = (G then,
Eq. 51
z Az A -1
(52a)
= AZ A'
(52b)
(52c)
= A'-I'AA
(52d)
By the definition of z we have that,
Il z' = (G'A 1G -- (G))) (G)))
(53a)
G -G)
(53b)
Also, by Eq.
52d we have
II zz = (A 1 Å (A -442) ... (A'Z'A ('''''" 1=1
(54a)
A A A
(54b)
By setting f= L 1, and combining equations 53b and 54b
we can solve for Z
G G - (G)) - A 1 A
(55a)
z'= (Â- ++ À -1(+1)
(G)
(55b)
Matrix roots are not unique, but we calculate roots by performing eigendecomposition. Finally use this expression for z to obtain a relationship between the kernel representation at layer e, G", and the input and label kernels, Go and G 2++
G
- (AG
(56)
D.1 Validity of the Solution
Note that the solution given by Eq. 56 is only valid Gy is symmetric and positive definite. The latter property, positive definiteness, can be shown by the fact that G5 is a product of positive definite matrices. We show symmetricity with the following argument.
Let C (though not necessarily symmetric). Therefore we write C using its eigendecomposition, = VDV-!, where is the diagonal matrix of the eigenvalues of C. In particular, D 2 O. We write G in terms of V and D, and use the fact that GL+1, kernel matrix,
(AG)
Since C is the product of two symmetric PSD matrices, it is PSD
_ -AG"
(57a)
A "D''A'A
(57b)
VDV-1 " (AG'A))
(57c)
This allows to show that the powers of C have the following property,
C" = = (VDV VD
(A'
(58)
25

---

Published in Transactions on Machine Learning Research (05/2025)
4000
3000
loss
2000
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
train iter
Figure 5: Losses during SGD training of the linear DKM. The loss of the analytic solution is shown by the dashed red line.
In particular, we have
(59)
Therefore,
G = AG ----DDILLUI-- -A= (G+)T
(60)
(61)
(62)
(63)
as desired.
D.2 Experimental Confirmation of Linear Analytic Results
Figures and demonstrate an exact match between our closed-form solution (Eq. 56 and when optimizing with gradient descent. We selected a random 200 node subset of Cora and (a) calculated the Gram matrices in closed form, and (b) optimized linear 2-layer graph convolutional DKM with Adam for 10000 epochs. We used polynomial learning rate schedule, initialized at 0.1 and decaying with power 0.7.
Figure 1 visualizes the Gram matrix representations themselves, and can see an exact match between the closed-form and gradient descent solutions. Figure 5| shows that the training loss of the gradient descent solution approaches the loss of the analytic solution (that is, the value of the lincar graph convolutional DKM objective when plugging in the analytic solution).
E
Experimental Details
For final performance metrics, we benchmarked the graph convolutional DKM on 14 node classification datasets and graph classification datasets. We also benchmarked a graph convolutional NNGP and GCN on the same datascts to obtain a suitable basclincs. We describe details of the datascts and the experimental method below.
E.1 Dataset Descriptions
Here, we describe the datasets used in experiments qualitatively. The majority of the datasets we used for benchmarking were node classification datasets, where the task is to predict the labels of all nodes in single
26

---

Published in Transactions on Machine Learning Research (05/2025)
graph, given labels for only limited number of nodes. Cora, Citeseer, and Pubmed (Planctoid datasets) are all citation networks, where nodes represent scientific publications, and edges are citations between those publications; one-hot keyword encodings are provided as features, and the goal is to place documents into predefined categories. Chameleon and Squirrel are both Wikipedia networks on their respective topics, so that nodes correspond hot as in the citation networks, but represent the presence of relevant nouns, and the task is to categories pages based on their average daily traffic. Penn94 QLim et al.) 2021) is an online social network where nodes represent users, and edges represent social connections. The task is to predict the reported gender of the users. Flickr is social network where nodes represent users, and edges correspond to friendships among users. The labels represent the interest groups of the users. Blog Catalog is a network dataset with social relationships of bloggers from the BlogCatalog website, where nodes' attributes are constructed by the keywords of user profiles. The labels represent the topic categories provided by the authors. Several of the remaining datasots were introduced by Platonov et al. (2023): :
articles, and edges correspond to links between articles; features are again one-
Roman Empire is derived entirely from the Roman Empire article on Wikipedia. Nodes are words in the text, and the words are 'connected' if they are either adjacent in a sentence or if they are dependent on each other syntactically. Features are word embeddings, and the task is to label each word's syntactic role.
Tolokers dataset of workers from the Toloka platform. The nodes are workers, and nodes are connected if workers have worked the same task. Features are statistics about each worker, and the task is to predict if worker has been banned.
Minesweeper is a synthetic dataset. The graph has 10,000 nodes corresponding to the cells in the 100 by 100 grid the Mineswceper game. Nodes are connected if the associated cells are adjacent. Features are one-hot encoded numbers of neighbouring mines, plus extra feature for when the number of neighbouring mines is unknown. The task is predict which nodes are mines.
Amazon Ratings is graph where nodes Amazon products, and nodes connected if they are commonly purchased together. Features are text embeddings of the product descriptions. The task is to predict the average user rating.
The two remaining node classification datasets, Reddit and Arxiv, are the largest (roughly one order of magnitude larger than the next biggest). In the Reddit dataset (Hamilton et al. (017), the nodes are posts, the features GloVe embeddings of the posts, the labels represent subreddits, and posts are connected if user comments on both posts.
The Arxiv dataset (Hu et al. 2020b) is another citation network; nodes are computer science Arxiv papers, and papers are connected if one cites the other. Node features are Word2Voc embeddings of a paper's title and abstract, and the labels are subject areas.
We also perform experiments with graph classification datasets. The graph classification datasets all contain molecules. NCI1 and NCI109 both contain graphs of chemical compounds (nodes representing atoms, with nodes connected if there are chemical bonds between them), where the goal is to predict the effect of the compounds versus lung and ovarian cancer. Proteins is a dataset of proteins molecules, where the task is to classify as enzymes or non-enzymes. Mutag is a dataset of compounds, and the task is to predict mutagenicity on Salmonella typhimurium. Finally, Mutagenicity is a dataset of drug compounds, and the task is categorize into mutagen or non-mutagen.
E.2
Details of Training, Hyperparameter Selection and Final Benchmarking
E.2.1
Node classification datasets
For node classification datasots, we used train train/vlidatton/toss splits from the corch_geometris library (Fey Lenssen 2019 for most datasets; the exceptions were Arxiv and Reddit for which we adapted code
&
from
Niu et. al. 2023). For data preprocessing, we (a) normalized all adjacency matrices in Kipf &
27

---

Published in Transactions on Machine Learning Research (05/2025)
Welling 2017 and (b) scaled input features such that the associated linear kernel had entries in [-1, 1.e.
X
X
(64)
En X X
We found that this transformation helped avoid numerical errors when training the models, as it ensures G =x")'" has elements all on roughly the same scale.
To select graph DKM hyperparameters, we started with a base model analogous the GCN described by Kipf & Welling (2017), 1, but with extra Gram layer before the first kernel non-linearity. From this base model, we performed 4 sweeps to select (1) and inducing point scheme, (2) architecture, (3) centering
parameters, and finally (4) the number of inducing points. The sweeps were,
Sweep (1): (0, 00,0. 0,1, 10, 100, 1000, oo), scheme {inter, intra),
Sweep (2): arch E {kipf, kipf Ax, kipf A resid, platinov]. Here, kipf refers to the default architecture, +Ad means that Å, was used instead the usual renormalized adjacency matrix, tresid refers to the addition of residual blocks, and platinov refers to an architecture similar the one used in Platonov et al. (2023). The platinov architecture is similar to residual 2-layer GCN, but with two linear layers in each residual block.
Sweep (3) searched over centering no centering, and whether to include learned scale and bias parameter (described in Appendix F
Sweep (4): P. E {50, 100, 200, 4003.
We trained for 300/200 epochs in sweep (1), and in the remaining sweeps trained for 200/150 for the smaller/bigger datasets (where Arxiv and Reddit and the 'bigger' datasets). For the smaller datasets 'one epoch' mcans a single full-batch gradient descent step; for the bigger datasets it mcans two mini-batched gradient descent steps.
We had a numerical stability issue with Squirrel when selecting hyperparameters. To resolve this, we set arch=kipf, rather than using arch=platinov, which was the 'best' according to sweep (2).
We repeated the above sweeps, but with DKM regularization fixed to Gram layers) to obtain final performance metrics for sparse graph convolutional NNGP, To find suitable hyperparameters for the GCN, we used a single grid search starting with the base GCN model of Kipf & Welling (2077). We searched over width E {100, 200), dropout E 0.5), batchnorm E {yes, no), and row ron_normalization E {yes, arch E (kipf, platinov).
(equivalent. to removing
We used the Adam optimizer with a two-stage learning rate schedule for all training runs. We increase the learning rate linearly from 10-3 to 10-2 for the first quarter of the epochs, and after that cosine schedule with a minimum learning rate of 10-5, The models were written in Pytorch, and we trained cluster containing RTX 2080's, RTX 3090's and A100s.
E.2.2 Graph classification datasets
For graph classification datasets, constructed our cross-validation splits (10 splits), since default split was provided by grrrc__eometric. We adopted very similar approach for hyperparameter selection in Section E.2.1 The main differences being that we set scheme=inter (since an intra-domain indicing-point scheme is not applicable in the multi-graph setting), and we trained for 300 batches on all datasets.
To perform graph classification with node-level features/kernel of multiple graphs, we (a) stack graphs together in batches of 1024, and (b) perform mean aggregation over nodes in each graph at the top layer of the network, thus obtaining logits for each graph.
E.3 Dataset Statistics
We include dataset statistics for node classification datasets in Table and Table respectively.
28

---

Published in Transactions on Machine Learning Research (05/2025)
Table 3: Node classification dataset statistics.
Dataset
# nodes
# edges
Homophily ratio
# features
# classes
Roman Empire
22,662
32,927
0.05
300
18
Squirrel
5,201
198,353
0.22
2,089
5
Flickr
7,575
239,738
0.24
12,047
9
Chameleon
2,227
31,371
0.23
2,325
5
Amazon Ratings
24,492
93,050
0.38
300
5
Blog Catalog
5,196
171,743
0.40
8,189
6
Penn94
41,554
1,362,229
0.47
4,814
2
Tolokers
11,758
519,000
0.59
10
2
Arxiv
169,343
1,157,799
0.65
128
40
Minesweeper
10,000
39,402
0.68
7
2
Citeseer
3,327
4,552
0.74
3,703
6
Reddit
232,965
57,307,9M4 ,466
0.76
602
41
Pubmed
19,717
44,324
0.80
500
3
Cora
2,708
5,278
0.81
1,433
7
Table 4: Graph classification dataset statistics.
Dataset
# graphs
avg. # nodes
avg. # edges
# features
# classes
Proteins
1,113
39.1
72.8
5
2
NCT1
4,110
29.9
32.3
38
2
NC1109
4,127
29.7
32.1
39
2
Mutag
188
17.9
19.8
8
2
Mutagenicity
4,337
30.3
30.8
15
2
E.4 Details of the Other Experiments
For Figure and Figure 5 we trained linear graph convolutional DKM for 10,000 epochs on randomly selected 200 node subset of Cora.
For Figure we calculate the linear graph convolutional DKM kernels on randomly generated Erdös- Rényi graphs, with 50 nodes and edge probability 0.1. When calculating the kernels, we use Ax=0.5 for the graph mixup. The input kernels are standard Wishart samples with 50 degrees of freedom. The nodes are randomly assigned one of two classes, with an even split.
For Figure trained graph convolutional DKMs with the arc-cosine kernel non-linearity for 300 epochs, with regularization E {0, 1, 10, 1000), and Âx=o. for graph mixup. The kernel alignment (CKA) figures were computed using the full kernels, without any normalization.
For all of the Figures described above in this subsection, we used a simple 2-layer architecture, similar to Kipf & Welling (2017). All kernel plots are normalized ensure entries are betwoen [-1, 1].
Finally, to produce Figure used data from the first hyperparameter sweep.
29

---

Published in Transactions on Machine Learning Research (05/2025)
F Kernel Centering Layer
As part of our grid search, we considered adding 'kernel centering layer'. When enabled, the centering layer performs a centering similar to batchnorm,
1 (F.Ya (F,)ix
(F.)
(65)
P.
where K F.F. is the kernel to be centered. parameter y and bias parameter B,
Additionally, include the option of learning scale
(F+) (FF)) +
(66)
G Inducing-point ablations
Table shows validation accuracies for different inducing point schemes. We obtained these accuracics during Sweep (1), so that y has been tuned for each snducing-point scheme (but not other hyperparameters). We find that inter-domain is a better scheme overall, but intra-domain can be beneficial for a few datasets (most notably Penn94).
Table 5: Validation accuracies for the two inducing point scheme on a range of node classification datascts.
Inter-domain
Intra-domain
Cora
78.9 0.2
58.2 + 0.5
Pubmed
79.4 +: 0.4
74.4 + 1.6
Reddit
94.2 + 0.0
94.5 + 0.0
Citeseer
70.8 0.2
23.4 0.2
Minesweeper
0.2
80.1
Arxiv
69.6 0.1
70.2
Tolokers
79.9
80.5
Penn94
69.5
81.3
BlogCatalog
0.8
1.3
Amazon Ratings
46.3 0.3
17.8
Flickr
1.6
1.6
Chameleon
2.0
66.0
Squirrel
49.9 0.7
5.94
Roman Empire
51.2 + 0.7
0.8
Deep Graph Convolutional DKMs
We investigated how the graph convolutional DKM performs as we increase the number of layers, with results shown in Figure 6 Similarly the inducing point ablations (Section G). we show validation accuracies using settings found in Sweep (1), so that and inducing-point scheme have been tuned (but not other hyperparameters). We find that increasing depth tends not help performance (though it occassionally help in some cases, e.g. Citeseer). This finding is expected, since GCN also loses performance as depth is scaled (Oono & Suzuki 2019). Note that we encountered a numerical instability when running the Reddit depth experiment, so the relevant data points have been omitted (depth=6 and 8).
30

---

Published in Transactions on Machine Learning Research (05/2025)
Cora
Pubmed
Reddit
Citeseer
Minesweeper
80
100
86
76
96
82
74
82
80
94
80
VaI
92
76
90
74-
88
70
86
68
10
Arxiv
Tolokers
Penn94
BlogCatalog
Amazon Ratings
78
86
50
76
86
70-
84
84-
48
82
50-
47
70
80
80
46
78-
40
68
45
76
66
44
74
64
20
43
72
62
Chameleon
Flickr
Squirrel
Empire
70
60-
55
45
60
45
35
Vai
55
30
30
50
35
20
10
45
30
Depth
Depth
Depth
Depth
Figure 6: Validation accuracy al different depths for different node classification datasels. Error bands are + 1 standard deviation.
Parameterization of the Deep Kernel Machine
Even though the inducing point scheme significantly reduces the computational complexity of training a DKM, computing the objective and forward equations is still expensive and has the potential to be unstable. In particular, the KL regularization terms
DKL (V(OG)) II
1 P log (o + T((K(G+-))
(67)
2
31

---

Published in Transactions on Machine Learning Research (05/2025)
involve unpleasant inverse and log-determinant. When implementing convolutional DKMs, Milsom et al. (0023) performed these calculations naively, which necessitates the use of double precision to avoid stability issues. The use of double precision is inefficient.
We propose the following parameterization to avoid the log det, while still computing the regularization term exactly. At each layer, we learn the parameter L' = cholesky ( Due to the fact that L is lower triangular, the log determinant term can easily be computed as,
log dot ( ()- log logdet(LL') Σ log L.
(68)
The forward equations given by Yang et al. 2023 are
G Kúi K G
(69a)
G Kit - K K, K
(69b)
We suggest using the Nyström approximation K., s K Kir. to avoid computing Kü; Ki.. K. Addition- ally, we know that there exist F, and Ft such that
Kiit
G G
G G
F F.F F.F.)
FFF
i
(70)
Therefore the Gram forward equations (Fq.
69
with Nystrom approximation for Ku, are equivalent to
H
cholesky(K))
(7la)
F H,L
(71b)
F. K,
(71c)
Notably, the K. computation can be achieved using a triangular solve, since H; is lower triangular. The trade-off of propagating with Eq. (71 rather than the original scheme (Eq. 69 that in exchange for using the Nyström approximation we get (a) efficient objective computation avoiding log det, (b) a triangular solve
instead of cholesky solve, and (c) fewer matrix multiplies.
32


Reviews:
[{"review_id": "1IwpgRJ16x", "reviewer": "Reviewer_5xCQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Novel Framework: Introduces the graph convolutional DKM, a flexible infinite-width model that bridges the gap between fixed-kernel NNGPs and finite-width GCNs by enabling controlled representation learning via the parameter v.\n\n- Scalability: Proposes two inducing-point approximation schemes (intra- and inter-domain) to reduce computational costs, making the model feasible for large graphs.\n\n- Empirical Breadth: Evaluates performance across 11 datasets with varying homophily levels, demonstrating that representation learning is critical for heterophilous tasks and less so for homophilous ones.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces the graph convolutional deep kernel machine (DKM), a flexible variant of infinite-width graph convolutional networks that allows for representation learning through a tunable parameter v. The authors develop scalable inducing-point approximation schemes to make the model computationally feasible for large datasets and provide a closed-form solution for learned representations in the linear setting, offering theoretical insights. Empirically, they demonstrate that representation learning significantly improves performance in heterophilous node classification tasks (where connected nodes tend to have dissimilar labels) but has less impact on homophilous tasks (where connected nodes tend to have similar labels). The graph convolutional DKM performs comparably to finite-width graph convolutional networks (GCNs) on most datasets, bridging the gap between infinite-width and finite-width models. This work advances the understanding of representation learning in graph neural networks, particularly in heterophilous settings, and provides a scalable framework for applying infinite-width models to large-scale graph data.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Include a comparison to other infinite-width frameworks, such as the Neural Tangent Kernel (NTK) [1] and \\muP parameterized models, in the graph node classificaiton setting.\n\n- Explore Deeper Architectures: Investigate the performance of deeper architectures (e.g., 4-layer or 6-layer models) and the impact of residual connections on representation learning.\n\n- Ablation on Inducing-Point Schemes: Perform an ablation study to compare the two inducing-point schemes (intra- and inter-domain) in more detail, including their impact on performance and computational cost.\n\n- Clarify Limitations: Expand the discussion of limitations, particularly regarding computational cost and scalability, and suggest potential avenues for future work to address these issues.\n\n[1] Huang, W., Li, Y., Du, W., Yin, J., Da Xu, R.Y., Chen, L. and Zhang, M., 2021. Towards deepening graph neural networks: A GNTK-based optimization perspective. arXiv preprint arXiv:2103.03113.", "broader_impact_concerns": "This work advances the theoretical and practical understanding of infinite-width neural networks in graph-based learning, introducing a flexible framework that enhances representation learning. While we do not foresee direct ethical concerns, potential considerations include biases inherited from graph structures, computational efficiency, and interpretability of learned representations. Future work could explore fairness-aware learning, scalable kernel approximations, and improved explainability to further enhance the applicability of Graph Convolutional Deep Kernel Machines.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "amMiikdXC7", "reviewer": "Reviewer_tTD2", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strengths are as follows:\n\n* the rigorous derivations for NNGP and DKM.\n* Well-organized presentation, which is easy to follow.\n* A inducing-point scheme that can compute the graph convolution DKM with linear scaling in dataset size.\n\nThe weaknesses are as follows:\n\n* This paper only provides empirical results for NNGP and DKM in graph node classification tasks. All results are straightforwardly obtained via experiments. However, it lacks a detailed discussion and explanation for the empirical observations, especially why NNGP can be good for some particular tasks while DKM is good for other tasks. This requires preciser designs of the experiments or theoretical analysis.\n\n* This paper only studies node classification problems, while graph convolution networks are also widely used for graph classification problems. This direction should also be considered in the paper as kernel machines may perform different for different graph tasks.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper mainly studies the abilities of NNGP and graph convolutional DKM in graph node classification tasks. This paper first introduces how to formulate the NNGP and DKM based on graph convolutional network, and then performs empirical studies to evaluate their performance for various node classification tasks. This paper shows that the representation induced by DKM can be beneficial for heterophilous node classification, while the  performance improvement is marginal for homophilous node classification tasks.\n\nThe contributions are summarized as follows:\n\n* This paper provides a clean formula for the NNGP and DKM in graph convolution networks and build a framework for performing different trade-off between NNGP and DKM.\n* This paper empirically studies the benefit of representation learning in various graph tasks, and finds different patterns in heterophilous and homophilous node classification tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Add some theoretical analysis to better show the difference between DKM and NNGP for different tasks, at least for some simple tasks.\n* Add more experiments regarding the graph classification problems and identify the difference between DKM and NNGP.", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DTrdoWiqUn", "reviewer": "Reviewer_Qhdi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths \n\nModel Design: The introduction of graph convolutional DKMs extends neural network Gaussian processes (NNGPs) to graph convolutional networks (GCNs), which allows for tunable representation learning.\n\nEmpirical Analysis: The empirical evaluations demonstrate the efficacy of the proposed model, especially in heterophilic node classification tasks.\n\nThe related works are organized very well\n\n\n## Weaknesses and Questions\n\n1. Lack of contribution: as the authors state, equation (22) follows equation (14), the inducing point scheme follows [1]. What is the main contribution beyond the simple extension of the previous work? I hope the authors can emphasize and highlight it.\n2. The modified adjacency matrix defined in equation (26) is the same as the generalized lazy random walk matrix in [2].\n3. The propose method increases the complexity of hyperparameter selection.\n4. \"We see that more homophilous datasets like Cora tend to have stronger performance for larger ν\", This seems only correct for Cora, but not for other homophilic graphs. Even for those $h>0.65$, they do not have the similar curves. For the heterophilic graphs, it looks like that their curves share a certain pattern. However, it is recently found that only considering homophily/heterophily is not enough to analyze the behavior of graph models [3,4]. We should consider both label, structure and feature aspects [4].\n5. Can your study be extended from $\\hat{A}$ to other graph filters or learning techniques, e.g. high-pass filters [2,3] and negative message passing [5,6]? These methods are found to be effective for heterophily problem. (This is not a weakness, just a question)\n6. How does your proposed method compare with SOTA models, e.g. [3,5,6]?\n7. Since graph convolutional DKM doesn't show clear edge over baseline GCN in terms of prediction accuracy, could you please clarify the biggest advantage of your proposed methods in practice, e.g. faster training or efficient inference?\n8. Most of the heterophilic datasets you test on are not hard datasets [7]. I recommend to verify your model on more challenging heterophilic datasets, e.g. the malignant and ambiguous heterophilic datasets [7]. (This is not a weakness)\n\n[1] A theory of representation learning in deep neural networks gives a deep generalisation of kernel methods. International Conference on Machine Learning, 2023. In press.\n\n[2] Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks. InNeurIPS 2022 Workshop: New Frontiers in Graph Learning 2022 Nov 22.\n\n[3] Revisiting heterophily for graph neural networks. Advances in neural information processing systems. 2022 Dec 6;35:1362-75.\n\n[4] What is missing in homophily? disentangling graph homophily for graph neural networks[J]. arXiv preprint arXiv:2406.18854, 2024.\n\n[5] Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3950–3957, 2021.\n\n[6] Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.\n\n[7] The heterophilic graph learning handbook: Benchmarks, models, theoretical analysis, applications and challenges. arXiv preprint arXiv:2407.09618. 2024 Jul 12.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Development of Graph Convolutional DKMs: introduce a variant of deep kernel machines tailored for graph data, which allows for adjustable representation learning, overcoming the static nature of traditional NNGPs.\n\nEmpirical Evaluation: provide empirical evidence showing that representation learning significantly improves performance in heterophilic node classification tasks, highlighting the model's utility in scenarios where node labels are dissimilar to those of their neighbors​.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The technical introduction from page 3-6 is too long. I suggest the authors to move the main content, especially the formulas, to appendix and summarize the main idea within two pages.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces the graph convolutional deep kernel machine (DKM), an infinite-width model inspired by NNDP and GCN, to enhance representation learning. The authors develop scalable approximation schemes to make the model feasible for large datasets, and offer theoretical insights and closed-form solutions in linear settings. Empirical results show that representation learning significantly enhances performance in heterophilous node classification tasks, while having less impact on homophilous tasks, thereby advancing the understanding of representation learning in graph neural networks. While reviewers noted that the paper's novelty does not stand out significantly, they also agree that the proposed methods are solid and interesting.
Decision: Accept (poster)