Graph Convolutional Kernel Machine versus Graph Convolutional Networks
Authors: Zhihao Wu
Zhao Zhang
Jicong Fan
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural network
kernel method

Abstract: Graph convolutional networks (GCN) with one or two hidden layers have been widely used in handling graph data that are prevalent in various disciplines. Many studies showed that the gain of making GCNs deeper is tiny or even negative. This implies that the complexity of graph data is often limited and shallow models are often sufficient to extract expressive features for various tasks such as node classification. Therefore, in this work, we present a framework called graph convolutional kernel machine (GCKM) for graph-based machine learning. GCKMs are built upon kernel functions integrated with graph convolution. An example is the graph convolutional kernel support vector machine (GCKSVM) for node classification, for which we analyze the generalization error bound and discuss the impact of the graph structure. Compared to GCNs, GCKMs require much less effort in architecture design, hyperparameter tuning, and optimization. More importantly, GCKMs are guaranteed to obtain globally optimal solutions and have strong generalization ability and high interpretability. GCKMs are composable, can be extended to large-scale data, and are applicable to various tasks (e.g., node or graph classification, clustering, feature extraction, dimensionality reduction). The numerical results on benchmark datasets show that, besides the aforementioned advantages, GCKMs have at least competitive accuracy compared to GCNs.

Graph Convolutional Kernel Machine versus Graph Convolutional Networks
Zhihao Wu', Zhao Zhang 1,2, Jiconn Fan 133-
Shenzhen Research Institute of Big Data, Shenzhen, China Hefei University of Technology, Hefei, China
The Chinese University of Hong Kong. Shenzhen, China
(zhihaowu199)) cszzhang)@gmaill com, fanjicong@cuhk. edu.
Abstract
Graph convolutional networks (GCN) with widely used in handling graph data that are prevalent in various disciplines. Many studies showed that the gain of making GCNs deeper is tiny or even negative. This implies that the complexity of graph data is often limited and shallow models are often sufficient to extract expressive features for various tasks such as node classification. Therefore, in this work, we present a framework called graph con- volutional kernel machine (GCKM)) graph-based based machine learning. GCKMs are built upon kernel functions integrated with graph convolution. An example is the graph convolutional kernel support vector machine (GCKSVM) for node classification, for which we analyze the generalization error bound and discuss the impact the graph structure. Compared GCNs, GCKMs require much less effort in architecture design, hyperparameter tuning. and optimization. More importantly. GCKMs are guaranteed to obtain globally optimal solutions and have strong generalization ability and high interpretability. GCKMs are composable, be extended to large-scale data, and are applicable to various tasks (e.g., node or graph classification, clustering, feature extraction, dimensionality reduction). The numerical results on benchmark datasets show that, besides the aforementioned advantages, GCKMs have least competitive accuracy compared to GCNs.
hidden layers have been
Introduction
Graph data prevalent in science and enginecring. In recent years, neural networks and deep learning methods have shown promising performance in handling various graph data. Graph Neural Networks (GNNs) have been developed into various basic frameworks, including famous GCN [Kipf and Welling 2017], GIN [Xu er al. 2019), GraphSAGE (Hamilton er al. 2017). GAT Velickovic et al.) 2018 etc. As of the most attractive GNN paradigms, GCN, the graph convolutional network Kipf and Welling, 2017), has gained widespread attention since it was
proposed. Many widely developed domains like machine learning [Chen al.] 2023b Cai el
al.
2022
Fan et al.) 2022) Fan 2022b), data mining [Chang el al.) [002]] Fan 2021 Wu el
al.
2022 computer vision Guan al. 2022 Cai and Fan] 2022; Wu al. 2023), etc., have
also made extensive use of numerous GCN variants. Despite the better performance compared
to classical graph methods (c.g., Walk [Perozzi al. 2014]. LINE [Tang et al.) 2015 and node2vector [Grover and Leskovecl 2016)), some recent studies have pointed out a few draw- backs GCNs [Wang et al.) 2020, Bo al. 202T, Wang al., 2023]. Perhaps the failure of deep GCNs is the most notorious one that severely restricted the further development of GCNs.
Correspon author: 'The source code is available at
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Containing both the self features and pair-wise relations of entities, graph is viewed as more complex non- -on-uucid data type, so there is natural and wide desire to construct deeper GCNs. Unfortunately, the performance of GCN decreases when stacking more graph convolutional layers. which is defined as the so-called over-smoothing issue [Li et al. 2018). For instance, even 7-layer GCN will in- evitably generate indistinguishable node embeddings and
100
-
GCN
JK
SGC
APPNT
Accuracy (%)
80-
60-
lead to over 30% accuracy degradation [Liu et al. 2020].
Recently, some methods modifying the basic structure of GCN have been proposed to handle the over- weo-shno issue and make GCN deeper [Xu et al., 2018 Klicpera el al. 2019: Yang al. 2022]. Indeed, most of them have successfully ly alleviated the over-smoothing issue. But it seems counter-intuitive that these elaborate deep GCNs, which stack dozens or even hundreds of layers, can only laboriously maintain the performance that 2-layer vanilla GCN achieves easily. We apply some GCNs to a node classification experiment on Cora following the settings of the original GCN, as shown in Figure ! APPNP (Klicpera et al.) 2019] and JKNet [Xu et al. 2018 are two well-known models that attempted to pass information from shallow layers to the final output but benefited very limited from the deep neural networks. These explorations raise a question:
20-
2
8
16
32 64
128
Numbers of layers/hops
Accuracy and standard devi- ations of deep GCNs, SGC, and GCN with diverse layer/hop numbers.
Figure 1:
Do we really need deep GCNs in common graph-based tasks?
Actually, there have also been some efforts paid to simplifying GCN, showing comparative effec- tiveness to vanilla GCN, like SGC (Wu et al. 2019), which removed nonlinearity and collapsed weight matrices to accelerate GCN, Impressively, y, it gained equal or even better performance on the benchmark graph datasets, which can partially be observed in Figure I Inspired by the success of SGC, some research moved further to decouple the graph convolution by individually performing an MLP (usually 2-layer) and several (can be hundreds) neighbor aggregations, called decoupled-style GCN [Nt and Machara 2019; Wang et al. [222]] All these works revealed that simple GCNs achieve encouraging performance
commonly used graph datasets such Cora, Citeseer, and Pubmed [Sen et al.) [2008) In these datasets, the numerical node features and the adjacency matrices are already discriminative, which means further feature extractions via neural networks do not improve the performance significantly.
However, SGC removes the nonlinearities of GCN and essentially becomes a linear classifier in terms of features given by neighbor aggregations, which may limit the possibility of extending to more complex tasks. In general, considering the limitations of the deep GCNs and SGC, can conclude that: ( the neighbor aggregation is essential for GCNs; 2 a simple feature mapping is helpful and sufficient but should be expressive enough. These two points well as the effectiveness of kernel methods in various machine learning problems [Cortes and Vapnik 1995 Schölkopf e aL. 1998a; Fan and Chow 2020; Fan af. [022)] Fan 2022a inspire to establish general and simple kernel-based framework, termed Graph Convolutional Kernel Machine (GCKM), for graph data. GCKM incorporates implicit feature mapping induced by kernels and neighbor aggregation
over graphs, providing a new paradigm for graph-based machine learning. The main contributions of this work are summarized as follows:
We propose a GCKM framework for graph-based learning. GCKM takes advantages of kernel learning and graph learning. Compared to GCNs, GCKMs have lower computational costs, higher interpretability, stronger theoretical guarantees, and stabler performances.
We provide generalization error bound for GCKM -bsedd node classification and prove that graph structure can tighten this bound, both theoretically and empirically.
We provide few variants of GCKM that are useful in various graph- based learning problems such as node clustering and node embedding.
We extend GCKMs to graph-level learning such as graph classification.
Comprehensive experiments demonstrate that the proposed GCKMs are as powerful as the state- of-the-art GCNs and significantly surpass several GCN-based methods on node semi-supervised classification and clustering tasks.
2

---

Notations Given an undirected attributed graph 9 = (V,E), where V and & are the vertex set and edge set, respectively, and [
the number of nodes. The node features are represented as matrix X [ X2 ................................ Xn] E Ruxm, where x, E R denotes the column feature vector of node ..,,.
i. And edges can be described by an adjacency matrix A E _=*x" where A.j = if there exists an edge connecting node and j. otherwise Aij = O. We use A, to denote the i-th row of A. We denote the self-looped adjacency matrix as A = A + I. The degree matrix corresponding to diagonal Å is denoted by D E IR**", where D. = 1 || denotes the Euclidean norm of vector. Let y: {0, 1] be the label vector of node and y = {y: Vi E L}, where L denotes the index set of labeled nodes. For node classification, the task is to learn a model fa(+) from X, A, and y to classify the unlabeled nodes.
2 Related Work
Vanilla and Deep GCNs. Kipf and Welling 2017 proposed GCN which further developed ChebyNet [Defferrard et al., [016]] and formulated an efficient and effective graph convolutional operation. Up to now, numerous studies have tried to explore and interpret GCN, and a widely applied description of GCN decoupled the graph convolution into the following two steps
(++1) AGGREGATE ({:::
H²)) AH!",
(++1) TRANSFORM (H ((+)) = (H*+
where H and (++1) are the input and output representations of the I-th layer. = A-D-!An AAD-
is the renormalized adjacency matrix and (-) is an activation function, e.g. ReLU(.). These two operations compose the layer-wise propagation of GCN, but plenty of research has revealed that constructing a GCN with more such layers would deteriorate the performance. Li et al. [2018) first pointed out the over-smoothing issue is the key point of this phenomenon, that is, repeatedly multiplying the input node features by adjacency matrix eventually makes them more and more similar, resulting in indistinguishable node embeddings. This view has been broadly acknowledged, and many studies have been conducted on how to solve the over-smoothing issue. APPNP [Klicpera el al. 2019] considered the relationship between GCN and PageRank to design new aggregation scheme, and improve the performance of deep GCN. JKNet [Xu et al. 2018 is another famous model for the same goal, which enabled each node to adaptively gain information from different hops of neighborhood. Nevertheless, different from the well-known deep CNNs, these approaches only alleviate the performance degradation but hardly benefit from the deep layers. More work on deep
GCNs can be found in [Chen et al., 2020 Sun et al. 2021 Chen er al. 2023a Xu et al.) 2023
Simplified GCNs. Although GCN put forward simple formula of forward propagation rule, its mechanisms have not been fully discussed and may contain redundant computation, which suggests simplified GCNs. Among these, SGC (Wu el al. 2019) removed the nonlinearity of GCN and only retained one learnable weight, so that built a faster model by precomputing the powers of the adjacency matrix. Ww et al. [2019] reported some interesting results that this intuitive way still achieve the powerful expressive ability of vanilla GCN even with a relatively small solution space. Following this work, some decoupled-style GCNs have been designed, which decouple the two processes in (T) and then only stack the aggregation step while reducing the transformations. For example, Nt and Maehara [209 claimed that graph structure only provided denoising approach and GCN and SGC only performed low-pass filtering on node features. They then proposed gfNN to improve SGC from the perspective of graph signal processing. [Luu al. (2020) hypothesized that the coupling of these two operations causes not only more computations but also the over- wee-ssmothinn issue, and introduced DAGNN by processing graph data via an MI.P separately before performing the neighbor aggregation. In light of DAGNN, Dong el al. (202)) further analyzed the mechanism of decoupled GCNs, concluding the effectiveness of this kind of simplifying approaches.
3 Graph Convolutional Kernel Machine
3.1 General Framework
GCN can be decoupled as two key steps: neighbor aggregation and feature transformation, as formulated in (I) The former is a fixed operation and only the feature transformation contains the
3

---

Input Graph
Graph Convolational Kemel Layers
D Downstream Tasks
Node Features X
Trerty
Node Chasdiaate
Kemel Machise
Nodk Chaserin
Adjaoney Mattix A
Gonghilaee foattte
Explictt Embboddnng
Crigh-eeval Choteitig
Neighbor ggregation
Feature Tranformation
Interfaces
Figure 2: Overview of the proposed Graph Convolutional Kernel Machine (GCKM).
learnable weights W and it has been discovered that stacking these two operations significantly damaged the performance. Therefore, some research has been dedicated to solving this problem and making GCN deeper, but to little avail. On the other hand, various simplified GCNs reduced the learnable parameters and are competitive to those deeper GCNs, and SGC even simplified the feature transformation one weight matrix without activation functions. In other words, despite the larger solution space provided by the nonlinearity and more Iearnable weights, improperly designed feature transformations may cause significant performance deterioration, while reduction of weights can lead to comparable power. Meanwhile, the representative SGC may be less expressive to cope with more complex data owing to linear classifier. So crucial present light model by exploring an effective well as efficient feature transformation approach.
Neighbor aggregation commonly regarded the pivotal component and makes the node rep- resentations more compact. Paired with feature map to low-dimensional space, it may lead to indistinguishable node representations between different classes. Thus, to guarantee discrimina- tive node representations, we propose to map node features to higher-dimensional space via transformation operation
TRANSFORM(X (X()
((x.)),,,,
where o: 1 - IR M feature mapping and M > m. Explicitly designing a @ usually costly especially when M is very large or even infinity. Instead, we can take advantage of kernels that can induce é implicitly. Let k x + R kernel function, we have
k(x, x') (Ø(x), o(x)) o(x) (xx)).
Thus can obtain a kernel matrix of X as
x(x1,x1)
1(x1,,,)) xn)
K
(4)
k(x,, x1)
k(Xn, xn)
There are many kernel functions available and each kernel function induces a specific feature map ø. For instance, the induced by a polynomial kernel k(x, x') (x x' + a) is b-order polynomial feature map; the e induced by Gaussian kernel (xxx, x') exp (-||x x2112/(202) is an infinity- order polynomial feature map, namely, M 0c.
We can alternatively perform the neighbor aggregation and the transformation ( and obtain layer-wise formulation of graph convolutional kernel machine follows
(I+) AGGREGATE (9; H OO
(++1) TRANSFORM(HEC) (H*+1) = oc) (H#+)),
where énn is the I-th implicit feature map induced by kernel k(0) and the corresponding kernel matrix is (1+1) (((+1)(((1)) Here the g-th power of À is adopted allow several times graph convolution. Formulation (5) can be easily extended to multi-layer cases, but H 1) is actually implicit and we calculate the kernel matrix K (I+1) directly in practice. It is necessary to discuss

---

the connection between K ((++)) and K and how to derive K layer by layer with only kernel matrices. Thus we will take the Gaussian kernel as an example, give the recursive formulation, and show how to derive the corresponding formulation in terms of kernel matrices. With Gaussian
kernel, we have Kjj
(-(++1)__ exp 20
(1, E [n] [n], where A 1 || (++)) h 11
is an element from A ((+1), which is squared distance matrix of H By series of derivations (deferred to Appendix A). we have
(++) dR 1, d. k(-))
- 2K(++1)
(6)
where K((+1)- Á (A9) and dR [K(ltt1) k formulation can be summarized as
R Thus the recursive
K(+1) = A'K(( (A
K [(++1) = exp
(-20
a++1) A
(o
Particularly, we define ( = XX_. Based on (7). GCKM with Gaussian kernels can be easily generalized to multi-layer cases. It is worth noting that similar compositions also apply other kernels such as polynomial kernel and Laplace kernel, which will not be detailed here.
After obtaining the kernel matrix ((4) from an L-layer GCKM, we can use Support Vector Machine (SVM) [Cortes and Vapnik, 1995] to perform node classification. Generally, SVM aims to solve
min
||w|] 12 +
E
s.t. De (x(x:), w) 2 1- Es. & 2 0, Vi = I....,n,
(8)
2
where y; (+1, -1} }} denotes the target label of training data and are the slack variables for the training data, and tp is a feature map. The Lagrangian dual problem is
Σ 4 1=1
1
ΣΣ
(C,9M,,((x,) 7((x,)
s.t. Σ c.lk - 0s. -.
A
max c
Invoking (LL)) into D. where (xx,) L
(T) we obtain the following optimization problem
of GCKM with L layers for node classification:
max Σ G
K 1=
s.t. cyy= 0, 05 -
(10)
1=1
For convenience, we call (TO) graph convolutional kernel SVM (GCKSVM). Compared to GCN which is nonconvex, GCKSVM is convex and hence we can find its global optimal solution easily. In addition, kernel methods often have higher interpretability than neural networks and stronger generalization guarantees. Compared to SGC which is linear classifier with respect to the final node representation, GCKSVM is nonlinear classifier and hence is expected to perform better when the data are not linearly separable. Further justification and discussion will be presented in Figure 3 and its related explanations.
3.2 Generalization Bounds of GCKSVM for Node Classification
We analyze the generalization ability of GCKSVM for node classification. Different from (Bartlett and Shawe- Shawe-Taylor 1999] Bartlett and Mendelson 2002; Grønlund et al., al., (020) that focuses on the primary problem of SVM, we focus on the dual problem, otherwise, the graph structure does not explicitly present in the bound.
Let è be the solution to (TO) and denote the corresponding as w, where we the Gaus- sian kernel for GCKSVM. Denote S be the set of training data drawn from some distribution D. Let Ls(č, k()) := Pr(((t))a)=ssl((pp Pr(p(x)).)) (sign((((( (y(xx, w)) + y) = -r(ocx) wD (v(p(()), w) s 0) be the expected test error. We have the following generalization error bound.
w) & 1] be the training error and (é, k()) :=
5

---

Theorem 1. Denote the index set of the support vectors as V = {i: 1 S n, ès + 0}. For any
0< < 1, it holds with probability at least 1 8 over set o samples S ~ D that
n Il + 1n(1/0)
n ln In(1/0)
s Ls((, < +0
K(1))
(11)
where 1) = Eiev & + Eiev EpEVtio Beg &&g Ki
Eiev EjEV Gdg &eg ke)k?/ S
121212 n
The proof for the theorem is in Appendix B In the theorem, K
exp
( ((()))))((((((()))))))))) bound and graph. Empirically (see Appendix (.6), find that given fixed X, the graph convolution reduces the number of support vectors | and has minor influence on the training error Ls (()), which eventually reduces the upper bound of test error. The fundamental reason is that incorporating the graph structure significantly improved the quality of the kernel matrix K(4), in which the overall within-class similarity becomes much larger than the between-class similarity. In other words, the kernel matrix becomes more discriminative, which can be verified by Figure
which shows the direct connection between the error
Note that the number of support vectors [V] in SVM is data-dependent and in order to theoretically show the influence of graph convolution on [V]. we have to make the following assumption:
Assumption 1. The aggregation step with graph G increases the inner product between the kernel feature maps of samples in the same class and reduces or does not change the inner product between the kernel feature maps of samples in different classes.
This is reasonable assumption because useful graph should make the samples from different classes more distinguishable or at least make the samples from the same class more similar.
Theorem Given graph 9 that satisfies Assumption ! let yp and Po be the kernel feature maps without and with aggregation graph G respectively. The corresponding negative La- grangian dual objectives (to minimize) are denoted as L(c) = 1 -2 Σi= 4;jjii - >i=1 Ci. where giy y())p(x;) T (xxx)) and Lg(c) = Σ Ej=1 Geo -E Co where dz + La(c) R((),
2
(xxx)))(xxx)))). (x())). We have (oN)))((,)
(12)
where R(c)= 2 0 a regularization term inducing sparsity in c.
The proof well as the details about R(c) are in Appendix C According to Theorem the aggregation step introduces an additional sparse regularization term R(c), which will make c sparser, or in other words, reduce the number of support vectors [V Considering both the theoretical and empirical results, we conclude that graph convolution leads to a tighter generalization error bound, which verifies the effectiveness of our GCKSVM. By the way, the interpretability of GCKSVM is higher than that of GCN, owing to the support vectors.
3.3 Extensions
Besides SVM, our method can be generalized to many other machine learning problems. We show a few examples of nove-level learning in the following context.
GCKM for Spectral Clustering (GCKSC) For node clustering, it is natural to perform spectral clustering [gg et al. 2001 Von Luxburg 2007] using the kernel matrix K(4) Instead of using the generally dense matrix K we retain only the largest values of each column to obtain sparse matrix K(L), which often yields better clustering performance.
GCKM for Principal Component Analysis (GCKPCA) It is straightforward to conduct Kernel PCA [Schölkopf er al. 1998b) using (T.,,, where the principal components can be used as the representations of the nodes of G. Please refer to Appendix F.5 for experiments.
We can also adapt GCKM to other learning models such as self-expeessive models Elhamifar and Vidal [2013], Fisher linear discriminant analysis Fisher 1936), canonical correlation analysis Hardoon al. 2004). etc.

---

Now we extend GCKM to graph-level learning. Suppose we have set of graphs G (91, .2,,.., GN3, where |Val ng. 9 1, ,. For each Gg. we use 7 to obtain K!² as well as the implicit node-level representations H. For each gg. we compute the implicit graph-level representation as the summation of node-level representations, i.e.
) (H
ing
g = 1.2...... ..
(13)
Then for any two graphs Gg. Gg,, we have
( 99'
Tu
4 1 H (H 1ny In, K K 90
Ing"
(14)
where K 98 E R X can be computed using graph-level kernel matrix as
5
recursively. Consequently, we can obtain
0
K
(2) n
K
(2) IN
1
0
x =
=xx(1] 99'
(15)
K NN
Luy
((L) has a high time complexity of N(N - 1)/2 and using (15) has a high Using (14) compute K - space complexity of ((()g) g= )) To reduce the cost, we can perform (15) on mini-batchs of G. We have the following result (proved in Appendix D)
Proposition 1. Suppose kLL) is Gaussian kernel with az co. Then (D) is positive definite.
X can be applied to various graph-level learning tasks such as graph classification and clustering.
3.4 Fast and Explicit Feature Transformation for GCKM
GCKMs can be stacked as multi-layer model and applied wide range of tasks by calculating the kernel matrix, and has the advantages of being fast, explainable, and requiring few parameters. Despite this, the time and space complexities of GCKM are O(n²), which limits the application to very large graph datasets. To tackle this issue, we consider approximating the kernel by
k(x,x') (Ø(x), o(x') R (x(x,, vxxx)),
(16)
where v²()) is a low-dimensional map using Random Fourier Feature (Rahimi and Recht 2007
The
following theorem provides the key foundation of this approximation method:
Theorem 3 (Bochner's theorem [Rudin| 1994)). A continuous kernel k(x, x') = k(x - x') on Imm is positive defmiit if and only if k()) the Fourier transform of non-negative measure.
Specifically, for Gaussian kernel, let pRAF(w) be a probability distribution and also the Fourier transforamtion of (ō). We first randomly sample (w("), ,.....pp ...,,!!) from the probability distribution PRBF(W) (w) .V (0, !). Subsequently the multi-layer GCKM with explicit feature transformation, called GCKM-E, the i-th sample is defined as 2;
(0)
((+1) thin (2, (111)) where
10(0 (z)
V cos(w] x ((+1) ,..., (2 sin( (
(17)
and z (1+1) and z 11-1) denote i-th columns vectors drawn from the transposes of Z (1) and Z (1+) = AzZ()
()) respectively. For detailed derivations, please refer to Appendix This approach allows
GCKM to flexibly choose the dimensions of explicit node representations when n very large.
4
Experiment
In this section, we evaluate GCKMs on several real-world graph datasets. Comparison experiments of both semi-supervised node classification and node clustering show GCKMs' accuracy and efficiency. Due to the space limitation, some important experimental results are deferred to Appendix F.2 (more types of datasets and large-scale dataset), Appendix F3 (over-smoothing problem), Appendix R4 (GCKM with various kernels) and Appendix F.5 GCKPCA visualization).

---

Table 1: Accuracy (mean% and standard %)viation% of all methods, note that the best results are highlighted in orange and the second-bes results are highlighted in blue.
Standard Split
Random Split
Cora
Citeseer
Pubmed
Cora
Citeseer
Pubmed
Chebyshev
75.0 (0.7)
63.8 (0.6)
74.7 (0.8)
76.1 (1.5)
63.4 (3.8)
75.4 (2.8)
GraphSAGE
76.9 (0.5)
63.3 (0.7)
74.8 (0.2)
76,3 (0.9)
63.2 (1.1)
73.9 (1.8
GAT
82.0 (0.5)
69.8 (0.4)
77.5 (0.2)
79.2 (1.4)
65.8 (2.9)
78.1 (1.7)
GCN
(0.7
70.5 (0.5)
78.4 (0.4)
80.6 (1.4)
69.1 (1.8)
(2.1)
SGC
81.3 (0.0)
68.4 (0.1)
78.6 (0.1)
79.6 (1.3)
(1.7)
76.6
APPNP
(0.6)
(0.8)
78.8 (1.3)
80.1 (1.8)
69.2 (2.1)
77.7
JKNet
(0.8)
(0.3)
80.1 (0.2)
78.0 (1.7)
(2.3)
(1.7
DAGNN
(1.I)
(..0
80.0 (1.0)
81.8 (1.2)
(1.4)
78.4
AdaGCN
(0.1
(9.4)
78.0
76.7 (1.8)
(1.2)
(1.3)
AMGCN
(0.4)
70.4 (0.2)
75.5 (0.9)
80.9 (1.2)
68.1 (1.4)
74.2 (2.1)
DefGCN
77.8
67.5 (1.7)
77.9 (0.6)
78.4 (2.3)
67.8 (2.6)
71.7
GCKSVM-E
(0.3)
72.4 (0.4)
79.1 (0.4)
80.8 (0.8)
68.5 (1.3)
79.2 (1.2)
GCKSVM
(0.0)
72.3 (0.0)
79.8 (0.0)
83.3 (0.8)
71.9 (1.0)
80.9 (0.5)
Datasets We employ three most widely adopted citation networks Cora, Citeseer, and Pubmed for evaluations, they are formed as unweighted and undirected graphs where each node represents paper and edges denote citations between papers. As for graph classification, IMDB-BINAL and AMDB-MULTY are movie collaboration datasets; COLLAB is a scientific collaboration dataset; MUTAG, PROTEINS, and PTC are three bioinformaties datasets. Details about these datasets and more datasets (e.g., social networks, paper networks and OGB-Arxiv) can be found in Appendix F.T
Compared Methods For node classification, two types of GNNs are selected: Chebyshev [Defferrard et al. 2016], GraphSAGE [Hamilton et al. [017], GAT [Velickovic et al. [0188, GCN [Kipf and
Welling [017]] and SGC [Wu el al. [d.[[011 [019 serve as classical baseline GNNs; APPNP [Klicpera
et al.) 2019). JKNet (Xu el al.) [0188, DAGNN [Li el al. 2020 AdaGCN (Sun el | [021].
AMGCN[Wang el al. 2020]. DefGCN [Park et al. 2022] are sfate-of-the-aar models, in particular
the former four ones are Deep GCNs. For node clustering, K-means and Spectral Clustering are two
traditional baseline methods and GAE and VGAE [Kipf and Welling [0166] are GCN-based bascline
DGI [Velickovic et al. 2019]. MVGRL [Hassani and Ahmadi 2020), GALA [Park et al. 2019 DFCN [Tu et al. 2021 and SC (Devvrit et al. 2022] are all state-of oftt--oftthe-an the-rrt GNN-based approaches. For graph classification, WL subtree kernel [Shervashidze et al.) 2011), AWL [Ivanov and Burnaev 2018
methods; ARGA, ARVGA [Pan et al. 2018
two baselines; DCNN [Atwood) and Towsley] 2016]. PATCHY-SAN (Niepert et al.) 2016) and DGCNN (Zhang et al. 2018 are three deep learning methods; GCN, GraphSAGE and GIN [Xu el al. 2019 are GNN-based methods.
Experimental Settings All the above methods are set as default following the original paper. We use a 2-layer GCKM for the experiments and the kernel is specified Gaussian kernel, more detailed settings of GCKM can be found in Appendix F.I In node classification, following vanilla GCN [Kipf and Welling 2017]. the nodes are split into three set: train set containing 20 samples per class, validation set and test set with 500 and 1, 000 samples respectively, and the standard fixed split is same (Yang al. 2 GCKM paired with kernel-based Spectral Clustering is leveraged for node clustering, which is described in Section 3.3 For graph classification task, we adopt the 1 10-fold
cross validation following the settings of GIN Xu et al. [2019].
Semi-supervised Node Classification The results are reported in Table I. where GCKSVM-E denotes GCKSVM with explicit features. Note that, we tune the hyperparameters of GCKSVM on the validation set and report the best performance. We have the following observations. 1) In the case of standard split, GCKSVM achieves decent performance and beats several GNNs including deep GCNs, even though it is a shallow model. Besides, owing to that GCKSVM can obtain globally optimal solutions, the standard deviations are zero. 2) In the case of random split, GCKSVM outperforms all GNNs on the three datasets and has the smallest standard deviations, showing higher stability. 3) Deep GCNs are not substantially better than, or even worse than baselines, which further validates that deepening is not essential in common graph- based tasks. 4) GCKSVM-E performs comparably to GCKSVM and other SOTA methods.
Decision Boundary To further explore the expressiveness, we illustrate the decision boundaries of SGC, APPNP, GCN, and the proposed GCKSVM in Figure 3 We generate a synthetic two-circle
8

---

Table Graph classification accuracy (mean% and standard deviation% of all methods, note that the best results are highlighted in orange and the second-bes results are highlighted in blue.
IMDB-B B
IMDB-M
COLLAB
MUTAG
PROTEINS
PTC
WL subtree
73.8 (3.9)
(3.8)
78.9 (1.9)
90.4 (5.7)
(3.0)
59.9 (4.3)
DCNN
49.1
33.5
52.1
67
61.3
56.6
PATCHYSAN
(2.2)
(2.8)
(2.6)
92.6 (4.2)
(2.8)
64.0)
DGCNN
70
47.8
73.7
85.8
75.5
58.6
AWL
(5.9
(3.6)
(1.9)
87.9 (9.8)
MLP
(3.7
(3.3)
79.2 (2.3)
84.0 (6.1)
76.0 (3.2)
66.6 (6.9)
GIN
(5.1
52.3 (2.8)
80.2 (1.9)
89.4 (5.6)
76.2 (2.8)
64.6 (7.0)
GCN
(3.4)
(3.8)
79.0 (1.8)
85.6
76.0 (3.2)
GraphSAGE
(5.3
50.9 (2.2)
(3.9)
63.9 (7.7)
GCKSVM
(2.4)
53,9 (2.8)
81.7 (1.5)
88.7 (7.6)
74.5 (3.9)
67.7 (5.4)
042
LX0
100
GCKSVM
0.26
ase
Circle
ACC: 62.6
ACC: 99.8
ACC: 89.8
ACC: 90.5
SGC
APPNE
126
GCKSVM.
108
Chameleon-2D
04
8.2
-02
-0.5
-022
ACC-493 48.7
-66
ACC: 67.8
-055
ACC 68.7
-635
ACC: 70.4
-075
SGC
APPNP
GCN
GCKSVM
075
475
6.75
835
Cora-2D
625
225
130
.100
-100
1.00
Figure 3: Decision boundary visualizations of SGC, APPNP, GCN, and GCKM on Circle (row 1). Chamelcon-2D (row 2) and Cora-2D (row 3), where Circle is a synthetic dataset and Chamelcon-2D and Cora-2D are two preprocessed real-world datasets.
dataset named Circle. also consider two real datasets, denoted by Cora-2D and Chameleon-22 where we select two classes of samples from the original datasets and map them to 2-D space using 1SNE [Van Maaten and Hinton 2008). We randomly labeled 200 samples for each dataset and constructed adjacency matrices by k-nearest neighbor algorithm, where the original graph structures are not used here. The details are described in Appendix F.I Cora-2D is the simplest case where the decision boundary is casy to construct, Circle is with clear but non-linear decision boundary, and Chameleon-2D is the most complex one.
We have the following conclusions. 1) Consistent with our previous discussion, the nonlinearity provided by SGC is low even if we increase the power of À to large value such as 50. Therefore, SGC performs poorly on Circle and Chameleon-29 where its decision boundaries are approximately linear. This is unexpected considering its performance the previous experiment. An explanation is that these commonly used graph datasets can be well classified linearly in high-dimension spaces, rather than these 2D spaces. 2) The deep model APPNP fits these datasets with similar boundaries as GCN, either simple or complex, revealing that existing deep GCNs may not provide more powerful expressiveness. 3) GCKSVM gains advantages the three other models, whose decision boundaries fit these datasets well, attributed to which GCKM explicitly maps the samples to high- dimensional space achieve better separability.
Graph Classification
The results of graph classification tasks are recorded in Table Compared to both classical baselines and GNNs, especially GIN designed for Graph-level tasks, GCKSVM shows

---

Table ACC, NMI, and ARI all methods, note the best results are highlighted orange and the second-best results are highlighted in blue.
Cora
Citeseer
Pubmed
ACC
NMI
ARI
ACC
NMT
ART
ACC
NMI
ARI
K-means
49.20
32.10
54.00
30,50
27.80
59.50
31.50
28.10
SC
36.70
12.60
3.10
23.80
5.50
1.00
$2.80
9.70
6.20
GAF
59.60
42.90
34.70
40.80
17.60
12,40
67.20
27.70
27.90
VGAE
50.20
32,90
25.40
46.70
26.00
20,50
63.00
22.90
21.30
ARGA
64.00
44.90
35.20
35.20
35.00
34.10
66.80
30.50
29.50
ARVGA
64.00
45,00
37.40
54.40
26.10
24.50
69.00
29.00
30.60
DGI
55.40
41.10
32.70
51.40
31,50
32.60
58.90
27.70
31.50
MVGRL
73.20
56.20
68.10
43.20
43,40
69.30
32.30
GALA
74.59
57.67
53.15
69.32
44.11
44.60
69.39
32.73
32.14
DFCN
64.07
48.24
39.17
69.50
43.90
45.50
69.32
32.19
31.55
GC
74.20
58.80
54.40
68.80
44.10
44.80
71.30
33.30
34,50
GCKSC
74.30
54.95
$2.89
71.27
43.57
46.51
71.31
0.008
0.80
0.80
0.006
0.60
0.60
0.002
0.20
0.20
0.000
0.00
(a) Adjacency Matri (36.7)
(b) Kemal Matrix (63.2)
(c) GCKM Matrix (74.3)
Figure 4: Visualizations of the adjacency matrix A9, kernel matrix [k(x,, x, ;)) and GCKM
matrix K (2) on Cora, with corresponding best-tuned clustering accuracy.
competitive power in graph classification. It worth noting that GCKSVM outperforms the GNNs in the two relatively large datasets IMDB-M and COLLAB.
Node Clustering The comparison of all node clustering methods is shown in Table
Similar to the results of node classification, GCKM is well extended to node clustering tasks and is competitive with the deep-learning-basee -baed models.
Cletysher GrpySAGE
JKNK
impressive that the vanilla GCN variants for clustering. GAE and VGAE both perform much worse than our GCKSC, demonstrating that GCKM can yield discriminative kernel matrix. This can also be observed in Figure 4 where the powered adjacency matrix, the kernel matrix calculated on node features, and the kernel matrix of GCKM are visualized.
Runtime (seconds)
DAGNN
GAT
AdaDON
GEN
AMGON
SCC
DeGGON
100
50
20
Time Costs Figure shows the runtime of all methods Pubmed. GCKSVM is much more efficient than all other methods except SGC.
Figure 5: Runtimes of all methods.
Conclusions
After analyzing the limitations of GCN, SGC and deep GCNs, we proposed a framework GCKM. GCKM integrated graph convolution with kernel learning and exhibited higher efficiency, inter- pretability, and stability. We extended GCKM to many graph-based machine-learning tasks, like node-level and graph-level classification and clustering. Experiments showed that GCKMs are, at least, as accurate as GCN and other SOTA GNNs. More importantly, compared to the representative simplified model SGC, GCKM is much more effective in handling non-linear data. One possible limitation of this work that we did not systematically test other kernel functions, though we have found that the Gaussian kernel is better than the polynomial for GCKM.
10

---

Acknowledgments
This work was partially supported by the National Natural Science Foundation of China under Grants No.6210621 I and No.62072151, the General Program damental Research, the research funding T001202 10002 of Shenzhen Research Institute of Big Data, the Guangdong Key Lab of Mathematical Foundations for Artificial Intelligence, Anhui Provincial Natural Science Fund for the Distinguished Young Scholars (2008085J30), Open Foundation of Yunnan Key Laboratory of Software Engineering (2023SE103) CCF-Baidu Open Fund and CA Huawei MindSpore Open Fund, and the funding UDF01001770 of The Chinese University of Hong Kong, Shenzhen.
000002003241000000000 of Shenzhen Fun-
References
James Atwood and Don Towsley. Diffusiinn-oonvllutionaa neural networks. In Advances in Neural Information Processing Systems, pages 1993-2001, 2016.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-433 2002.
Peter Bartlett and John Shawe-Tayler Generalization performance of support vector machines and other pattern classifiers. Advances in Kernel methods supporr vector learning, pages 43-54, 1999.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 3950-3957, 2021.
Jinyu Cai and Jicong Fan. Perturbation learning based anomaly detection. In Advances in Neural Information Processing Systems, 2022.
Jinyu Cai, Jicong Fan, Wenzhong Guo, Shiping Wang, Yunhe Zhang, and Zhao Zhang. Efficient deep embedded subspace clustering. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 21-30. IEEE, 2022.
Heng Chang, Yu Rong, Tingyang Xu, Yatao Bian, Shiji Zhou, Xin Wang, Junzhou Huang, and Wenwu Zhu. Not all low-pass filters robust in graph convolutional networks. In Advances in Neural Information Processing Systems, pages 250711 2021.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference Machine Learning, pages 1725-1735, 2020.
Zhaoliang Chen, Zhihao Wu, Zhenghong Lin, Shiping Wang, Claudia Plant, and Wenzhong Guo. Agnn: Alternating graph-regularizer arized neural networks to alleviate over-smoothing. IEEE Transac- tions on Neural Networks and Learning Systems, pages 1-13, 2023.
Zhaoliang Chen, Zhihao Wu, Shiping Wang, and Wenzhong Guo. Dual low-rank graph autoencoder for semantic and topologiaal networks. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, pages 4191-419 2023.
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. In Advances in Neural Information Processing Systems, pages 9936-9949, 2021.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20:273-297, 1995.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pages 3837-3845, 2016.
Fnu Devvrit, Aditya Sinha, Inderjit S. Dhillon, and Prateek Jain. S3GC: scalable self-supervised graph clustering. In Advances in Neural Information Processing Systems, 2022.
11

---

Hande Dong, Jiawei Chen, Fuli Feng, Xiangnan He, Shuxian Bi, Zhaolin Ding, and Peng Cui. On the equivalence decoupled graph convolution network and label propagation. In Proceedings of the Web Conference, pages 3651-3662, 2021.
Ehsan Elhamifar and René Vidal. Sparse subspace clustering: Algorithm, theory, and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35( (111)))27655 27)2227577781, 2013.
Jicong Fan and Tommy W. S. Chow. Exactly robust kernel principal component analysis. IEEE Transactions on Neural Networks and Learning Systems, 31(3)7749-76,, 2020.
Jicong Fan, Yiheng Tu, Zhao Zhang, Mingbo Zhao, and Haijun Zhang. simple approach to automated spectral clustering. In Advances in Neural Information Processing Systems, pages 9907-9921, 2022.
Jicong Fan. Large-scale subspace clustering via k-factorization. In Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 342-352, 2021.
Jicong Fan. Dynamic nonlinear matrix completion for time-varying data imputation. Proceedings of the AAAI Conference on Artificial Intelligence, (116))6687-6596,, Jun. 2022.
Jicong Fan. Multi-mode deep matrix and tensor factorization. In Proceedings the 10th International
Conference on Learning Representations, 2022.
Ronald A Fisher. The use of multiple measurements in taxonomic problems. Annals of Eugenics, 7(2):199-188, 1936.
Allan Grønlund, Lior Kamma, and Kasper Green Larsen. Near-tight margin- based generalization bounds for support vector machines. In Proceedings of the 37th International Conference Machine Learning, pages 3779-3788, 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 035-864,77 2016.
Yonghang Guan, Jun Zhang, Kuan Tian, Sen Yang, Pei Dong, Jinxi Xiang, Wei Yang, Junzhou Huang, Yuyao Zhang, and Xiao Han. Node-aligned graph convolutional network for whole-slide image representation and classification. In Proceedings of IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 18791-18800 2022.
Xiaojun Guo, Yifci Wang, Tianqi Du, and Yisen Wang. Contranorm: A contrastive learning perspective oversmoothing and beyond. In Proceedings of the I 11th International Conference on Learning Representations, 2023.
William L. Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1024-1034, 2017.
David Hardoon, Sandor Szedmak, and John Shawe-Taylor. Canonical correlation analysis: An
overview with application to learning methods. Neural Computation, 16(12)2639-2264, 2004.
Kaveh Hassani and Amir Hosein Khas Ahmadi. Contrastive multi-view representation learning on graphs. In Proceedings of the 37th International Conference on Machine Learning, pages 41 4116-4126, 2020.
Roger Horn and Charles R Johnson. Matrix analysis. Cambridge University Press, 2012.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. Proceedings of the 35th International Conference Machine Learning, pages 2191-2200 2018.
Bo Jiang, Chris Q. Ding, Bin Luo, and Jin Tang, Graph-laplacian PCA: closed-form solution and robustness. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3492-3498, 2013.
Thomas Kipf and Max Welling. Variational graph auto-eneoders. arXiv preprint arXiv: 1611.0730 2016.
12

---

Thomas N. Kipf and Max Welling. Semi-supprrvsed classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations. 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In Proceedings of the 7th International Conference on Learning Representations, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 3538-3545, 2018.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 338-348, 2020.
Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in Neural Information Processing Systems, 14, 2001.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In Proceedings of the 33rd International Conference on Machine Learning, pages 2014-2023, 2016.
Hoang Nt and Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: 1rX5x59905.09550, 2019.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang. Adversarially regularized graph autoencoder for graph embedding. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pages 6609-2615, 2018
Jiwoong Park, Minsik Lee, Hyung Jin Chang, Kyuewang Lee, and Jin Young Choi. Symmetric graph convolutional autoencoder for unsupervised graph representation learning. In Proceedings of IEEF/CVF International Conference on Computer Vision, pages 6518-6527, 6527, 2019.
Jinyoung Park, Sungdong Yoo, Jihwan Park, and Hyunwoo Kim. Deformable graph convolutional networks. In Proceedings of the 36th AAAI Conference on Arlificial Intelligence, pages 7949-7956. 2022.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 701-710, 2014.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systems, pages 1177-1184, 2007.
Walter Rudin. Fourier analysis on groups. Wiley Classics Library, 1994.
Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Nonlinear component analysis as kernel eigenvalue problem. Neural computation, 1295):129--,319 1998.
Bernhard Schölkopf, Alexander Smola, and Klaus-Rohert Müller. Nonlinear component analysis as kernel eigenvalue problem. Neural Computation, 1099:1129-1319, 1998.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification network data. Al magazine, 29(3):93-93, 2008
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12:2539- 2561, 2011.
Ke Sun, Zhanxing Zhu, and Zhouchen Lin. Adagen: Adaboosting graph convolutional networks into deep models. In Proceedings of the 9th International Conference Learning Representations, 2021.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. LINE: large-scale information network embedding. In Proceedings the Web Conference, pages 1067-1077, 2015.
13

---

Wenxuan Tu, Sihang Zhou, Xinwang Liu, Xifeng Guo, Zhiping Cai, En Zhu, and Jieren Cheng. Deep fusion clustering network. In 35th AAAI Conference on Artificial Intelligence, pages 2021.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(11), 2008.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proceedings of the 6th International Conference Learning Representations, 2018.
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In Proceedings of the 7th International Conference on Learning Representations, 2019.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17:395 416, 2007.
Xiao Wang, Meiqi Zhu, Deyu Bo, Peng Cui, Chuan Shi, and Jian Pei. AM-GCN: adaptive multi- channel graph convolutional networks. In Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1243-1253, 2020.
Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Dissecting the diffusion process in linear graph convolutional networks. In Advances in Neural Information Processing Systems, pages 5758-5769, 2021.
Shiping Wang, Zhihao Wu, Yuhong Chen, and Yong Chen. Beyond graph convolutional network: An interpretable regularizer-centered centered optimization framework. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, pages
2023.
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning, pages 6861-6871, 2019.
Zhebin Wu, Lin Shu, Ziyue Xu, Yaomin Chang, Chuan Chen, and Zibin Zheng. Robust tensor graph convolutional networks via T-SVD based graph augmentation. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2090-2099, 2022.
Zhihao Wu, Xincan Lin, Zhenghong Lin, Zhaoliang Chen, Yang Bai, and Shiping Wang. Interpretable graph convolutional network for multi-view semi-supervised learning. IEEE Transactions on Multimedia, pages 1-14, 2023.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, pages 44588, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In Proceedings of the 7th International Conference on Learning Representations, 2019.
Bingbing Xu, Bin Xie, and Huawei Shen. Towards deeper graph neural networks via layer-adaptive. In Proceedings of the Web Conference (WWW), pages 103-106, 2023.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on Machine Learning. pages 40 48,488222 2016.
Mingqi Yang, Yanming Shen, Rui Li, Heng Qi, Qiang Zhang, and Baocai Yin. new perspective on the effects of spectrum in graph neural networks. In Proceedings of the 39th International Conference on Machine Learning, pages 25261-25279, 2022.
Muhan Zhang. Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the 32nd AAAI Conference Artificial Intelligence, pages 1438-4445 2018
14

---

A Details about Recursive Formulations of GCKM
An L-layer GCKM node feature X can be written
H & (A9... 200) (A
(A ( (A*X) ...)........
(18)
Note that H(--1 is actually implicit and directly obtain the kernel matrix K(++))
H(+)) in practice. Now we show how to derive K(++1) only by kernel matrix K(), Take
A
the Gaussian kernel as an example, we have Kij k(( exp
2 (i.j) [n] [n], where
(I+1) is a squared-distanee matrix the rows of H1++1, To be more precise,
A (1+1) = =Ibb,- (1-1) 112
(19)
-h (4+ (h. ) 2h (k) + +h (
(20)
where h (((1) (a row vector) is the representation of the i-th node drawn from
H (1+1)_ HH A (H
(21)
Thus h (1+1) = (A) (H)). ) it follows from 19 that
A (1+1) -AA") -(A"),00-1) (H 1 -
(A 2(A"), ,(11)) (H (H")
+ (A9), ,011 01-11) (H (0)
((-1)) (A')
= =A²)), K (1) (A ((A)),K))) (A'), + (A'), 10)KK)1 (A9),.
(22)
where K. exp
I(A)) -(A-)) (A") HD11 (1,5) E [r|] [n]. Particularly, define
20
((O) = XXT. So K (1+1) can be obtained through K ((1) i.c.,
k(U+1) exp (A)):K(AAA)) 2(A 9) K (1)
(Aº) + (A'), (()))]
(23)
20 2
For convenience, letting ((++1)_ = Á²K() (1) (A9)T and dRwI1) = [K [K((+]) K
R
we can calculate ((++1) the following matrix form
dR + 1 K(+1) -2((++)
K ((-+1) exp
(24)
20
B Proof for Theorem
Proof. Since è is the optimal solution of the dual problem, the optimal solution w of the primary problem can be given by
w
(x,))
(25)
We have
1|
Σ
(x))((ss)
Σ (iNpp((s)
NEV
Σ &C; (x(x))
Tp((x)
REV jEV
Σ Σ Cadyyry k(1)
(26)
LEV JEV
(L)
Σ
Σ
KerK!! (L)
Σ Σ
&CcK!! (L)
1EV
SEV WE
NEV JEV.
Σ
Σ
Σ
': k
Σ Σ
NEV
NEV !.
iEV iEV JEV
15

---

On the other hand, we have
|
ΣΣ &e
iEV JEV jEV
Gy [ 1... :. [ lasev)
$ ||| ||.. Gy
.. [ 1...)
... .Illr lese
K kEEv ||, Σe &
(27)
iEV
|
||
n²
2 112
n²
Now use the following theorem, where the notations are little different from ours.
Theorem ((Gronlund et al. 2. Let E N+ and let O. Denote by X the ball of radius in Idd and let D be any distribution over X x {-1,1}. For every 8 >> 0, it holds with probability at least 1 - over set of n samples S ~ DD" that for every E R with wlle I 1 and every margin 0 > we have
Lo(w))= I (w) +0 (R/0)² Inn + lm(1/0)
(R/0)2 ln + In(1/8) (g(w))
+
According setting, have R and | since [x(x;)] K (b) and ((W,,p(x)) 2
1 <> [ (x)) 2 [
For convenience, let r || which was given by 27 Substituting these values into Theorem and changing the notations, obtain
n glnn + In(1/0)
n Iln + In(1/5) Ls K(1)
Co(c,K(ng < (((), +0
+
(28)
This finished the proof.
C Proof for Theorem 2
Proof. Here we recall the Lagrangian dual problem:
max Σ G
(0,,,,5((x, ,((x) s.t. Σ c.u = 0, 0S
(29)
2
1=1
1=
For s2, we define
L(c) =
Σ
4cj4i - Σ where g3 )(,)p(x;) ((xx).
(30)
2
im1
Similarly, for lgg. we let
1 a
Lo(c) = 2
Ci where of wiysf((x;)) (x((x))
(31)
Then we need to minimize L(c) and Cc(c) under the constraints E Cilli 0, 0 < < 2
According to the Assumption we have:
if samples and j are in the same class, (x(x)) (o(x:))TTgxx)))) > ((xx) T (x(xx) and yill = 1;
if samples and are in different classes, (x,) (o(xx) S p(xx) ((xx) and yıy, = -1
16

---

Therefore, the following equality holds:
Vig + Exj: Eij 2 0, v(4,)) E [m] [n]
(32)
For convenience, let E, miny Eg and min, &g We have
Lg(c) j=1
agyla +ay)
n
22
cijjis + L
Es
C;Cy
Σ
Ci
i=1 j=1
1=1
/=1
i=1
(33)
=L(c) + 2
Σ
E 2
Cj
j=1
2((c) [
Σ &clllc//ll1
where c/s = [ei,... Ci-1: Citl.... Cnl [T_ It is known that the nnorm || -| is a convex relaxation of the fn-norm /lo. i.e., the number of nonzero elements in vector. Denote R(c) == (<]lel]
E @cllc//lla). We R(c) is very similar to the elastic net regularization and is able to induce sparsity. Actually, if we let x min; |/c/slla have R(c) 2 (č]|c|í + + E &c)
(2||e]12 + dl)dia(())l)). where the second term is a weighted & f--norm and also induces sparisty.
D Proof for Proposition 1
Proof. Let
1 n
K
(L) 11
K
(L) IN
Q
=
K(L)_
K NN-
It is easy to show that Q is full-rank. Because k(L) is Gaussian kernel with 0 0o, ((4) is symmetric and always full-rank. It means ((.)) can be factorized as (L) =B B, where B is square and full-rank matrix. Denote BQQ follows that
(L) =PPP
(34)
Since full-rank, we conclude that K( is full-rank, which means K!( (L) is positive definite Horn and Johnson 2012).
E Detailed Derivations of GCKM-E
Theorem 2 (Bochner's theorem Rudin 1994 ). A continuous kernel k(x, = k(x - x') on Imm is positive definite if and only if k())
b)& is the Fourier transform of a non-negative measure.
With positive definite and shift- thift-invariant kernel kc(:.) (e.g. Gaussian kernel), the Bochner's theorem points out that the kernel function can be expanded with harmonic basis as
k(x; - x2) = [ p(w)e (x.: (x. (x.-x,) Enw Jow xx xi jw x,|,
(35)
where p(w) is probability distribution and also the Fourier transform of k(()). For real-valued kernel functions, "jي xie jo x; can be simplified by
jw x: x -j Xx cos (x, x,)
(36)
17

---

according to Euler's s formula. Then we can define function (-) with Sw (x; (x²) cos w (x: ; x,), so that it satisfies
B (aw (x) (xj)] Eew [eow xi =-w- x5] k(x; -x,)
(37)
Here simply adopt (x) cos(ww xx), sin (w)x)) Tx)] and the kernel function can be approxi-
mated by combining several drawn from distribution p(w).
Specifically, for Gaussian kernel, we first randomly sample (wi,w2,... wD from the probability distribution pReF (w) (0, JT). Subsequently the explicit feature transformation the i-th
sample x; is defined as
VD [cos[w] x:), cos((w sin(w] xx)
(x,)
(38)
On the basis of the above derivations, the multi-layer GCKM with explicit feature transformation can be similarly defined:
z (/( (AZ
(39)
where ((+1) the random Fourier features of input ( This approach allows GCKM flexibly choose explicit node representations or kernel matrix the interface, and the final representation can be low-dimensional and thus efficiently computed. By selecting a proper D, the convergence of this approximation and the expressive ability of the kernel can be simultaneously guaranteed.
F Detailed Experimental Settings and Results
Experimental Settings
Two types of graph datasets are employed in this paper. Each node-level dataset contains only graph where each node is a sample, while each graph is regarded as a sample in the graph-level datasets. Here list the key statistics of these datasets in Table 4 aonde4and33 5 and provide detailed deseriptions in the following.
Node-level Datasets
Cora citation network containing number of machine learning papers. Each node represents paper and the edges represent the citation relationships between papers. Node features are the bag-of-words representations of papers, and papers are divided into categories according to their domains.
Citeseer is also a well-known citation network with nodes, node features, and edges having the same meanings as Cora. Similarly, the papers are grouped into 6 classes.
Pubmed is citation network composed of 19, 717 scientific publications drawn from the PubMed database, which are classified into 3 categories and node features are also the oog-of-wordh representations.
ACM is paper network. Different from the above citation networks, the edges denote the co-author relationships between any two papers. Another difference that the node features are bag-of-words representations of papers' keywords.
CoraFull is a large version of the Cora dataset which has 19, 793 papers of 70 classes.
Chameleon a webpage network, which nodes are Wikipedia pages of certain topics and edges are the page-page hyperlinks. Some informative nouns in the pages extracted to node features and the nodes are organized in 5 categories based on the average monthly traffic of the corresponding web pages.
Actor is subgraph of the film annrector-atto--ie
network which only includes actors as nodes. An edge between two actors exists when they occur on the same Wikipedia page.
Squirrel is webpage network well, and all the settings are similar the Chameleon dataset.
UAI a webpage network that has been used to test GCN for community detection. Nodes represent web pages and each edge represents citation between pages.
18

---

Table 4: Dataset statistics.
Datasets
# Nodes
# Edges
Classes
# Features
Train/Val/Test
Data Type
Cora
2,708
5,429
7
1,433
140/500/1
1,00000//0000000000 ,000
Citation Network
Citeseer
3,327
4.732
6
3.703
120/500//1000
Citation Network
Pubmed
19,717
44,338
3
500
60/500/1.000
Citation Network
ACM
3,025
13,128
3
1,870
60/500/1,000 1,000
Paper Network
Chameleon
2,277
36,101
3
2.325
60/500/1,000
Webpage Network
CoraFull
19,793
65,311
70
8,710
1,400/500/1, ,000
Citation Network
Actor
7,600
15,009
5
932
100/500/1_000
Social Network
Squirrel
5,201
217.073
3
2,089
60/500/_1000
Webpuge Network
UAI
3,067
28,311
19
4,973
367/500/,1000
Webpage Network
Table 5: Dataset statisties.
IMDB-B
IMDB-M
COLLAB
MUTAG
PROTEINS
PTC
Nodes
1,000
1,500
5,000
188
1,113
344
Classes
2
2
Avg Nodes
74.5
17.9
39.1
25.5
Data type
Movic
Movic
Scientific
Bioinformatics
Bioinformatics
Bioinformatics
OGB-Arxiv dataset is a citation network with 169, 343 computer science arXiv papers, where each node is an arXiv paper and each edge indicates that a paper cites another paper. Each paper has a 128-dimensional feature vector, which is obtained by averaging embeddings of words in its title and abstract.
Graph-level Datasets
IMDB-BINARY and IMDB-MULTI are movie collaboration datasets, where each graph represents an ego-network for each actor/actress. Each node corresponds an actor/actress, and the edges represent the actors/actresses' co-occurrences in movie. Graphs are classified according the genre of the movies they come from.
COLLAB is scientific collaboration dataset, collected from three public collaboration datasets. Similar to the two datasets mentioned above, each graph is a self-network of differ- ent researchers, and these graphs classified by the domains to which their corresponding researchers belong.
MUTAG is bioinformatics dataset. 188 mutagenic aromatic and heteroaromatic nitro compounds with 7 labels compose this dataset.
PROTEINS a bioinformatics dataset where nodes denote secondary structure elements with 3 labels. An edge between any two nodes means they neighbors in the amino-acid sequence or 3D space.
PTC is bioinformatics dataset containing 344 chemical compounds that report carcino- genicity for male and female rats and it has 19 discrete labels.
For datasets ACM, Chameleon, CoraFull, Actor, Squirrel, and UAI, randomly split them into the train, validation, and test sets and fix them for all the compared methods. For graph-level datasets split, follow settings in [Xu et al. 2019
Then, we also briefly introduce the compared methods used in node-level tasks and graph-level tasks.
Node-level Compared Methods
Chebyshev (Deffrrardd al. 2016 generalizes the convolution operation to the non- Fuclidean space based on spectral graph theory, which leverages Chebyshev polynomial to design a localized graph convolutional filter.
GraphSAGE Hamilton el al.) 2017 is proposed to tackle the drawbacks of transductive GNNs. trains the aggregation function from each node's local neighborhood, and this function can be performed unseen nodes.
19

---

Table Node classification accuracy (mean% and standard deviation%) of all methods, note that the best results are highlighted in orange and the second- beoooddeettt results are highlightte in blue. GraphS encounters some eπrors on ACM and the corresponding result marked as
ACM
Chamelenn
CoraFull
Actor
Squirel
UAT
Chebyshey
82.8 (1.4)
35.6 (0.2)
57.2 (1.1)
(0.4)
(0.6)
49.7 (0.4)
GmahSAGE
44.0 (0.0)
59.9 (0.7)
(0.5
26.8 (0.2)
41.7 (1.4)
GAT
84.6 (0.5)
51.1 (1.0)
(0.4)
(0.7)
28.4 (0.6)
49.7
GCN
88.8 (0.5)
(1.8)
62.8 (0.4)
20.9 (0.9)
30.9
(1.1)
SGC
80.8 (2.7)
(1.1)
(2.2)
21.1 (1.3)
21.3
56.5 (3.5)
APPNP
88.2 (0.0)
(1.2)
(0.5)
22.6
27.1 (0.1)
62.3
JKNet
(0.6)
50.3
(2.6
(0.6)
(1.0)
45.6
DAGNN
(0.9)
(3.9
65.6 (0.3)
21.7
(2.7)
46,7 (12.4)
AdaGCN
88.7 (0.0)
43.8
63.8 (0.0)
(0.9)
25.7 (0.0)
47.3 (1.1)
AMGCN
(0.6)
31.3
(0.6
26.8 (0.7)
22.3
59.3 (3.8)
DelGON
86.9 (0.6)
49.5 (0.7)
(2.3)
(3.8)
28.4 (3.6)
56.4 (2.1)
GCKSVM
91.0 (0.0)
54.0 (0.0)
61.8 (0.0)
29.5 (0.0)
36.8 (0.0)
59.6 (0.0)
Table 7: Accuracy of several representative methods on large-scale dataset OGB-Arxiv, note that the best results highlighted in orange and the second-best results are highlighted in blue.
OGB-Arxiv
Nodes: 169,343
# Features: 128
# Edges: 1,166,243
# Classes: 40
Chebshev
GraphSAGE 69.8 (0.2)
GAT 70.2 (0.2)
GCN 69.5 (0.1)
SGC
APPNP
JKNet 69.8 (0.2)
GCKM-E
69.7 (0.2)
66.7 (0.0)
69.3 (0.1)
71.0 (0.0)
GAT [Velickovie al., 2018 classical spatial GNN equipping with self-attentional layers that adaptively learn different weights for edges.
GCN [Kipf and Welling 2017 one of the most popular GNNs recently. It truncates the Chebyshev polynomial to first order and proposes a simple and effective graph convolution.
SGC (Wu et al. 2019) further simplifics GCN by removing the nonlincarity and collapsing the learnable weights, as to build faster model and achieve competitive performance.
APPNP Klicpera et al. 2019] uses personalized Pagerank to improve vanilla GCN by solv- framework with initial residual connections.
ing the over-smoothing issue and derives
JKNet [uu et al.) 2018) establishes a jumping knowledge structure to combine representa- tions from various layers to stack deeper GNN.
DAGNN [Xu et al. 2023 decouples the neighbor aggregations and feature transformations to form a deeper GNN and further uses the attention mechanism to integrate the information from different depths.
AdaGCN [Sun er al. 2021 is also a deep GCN that considers the Adaboost strategy to fuse knowledge from distinct layers.
AMGCN [Wang et al. 20200 constructs a feature graph via k-NN algorithm and a multi- channel framework to enhance the vanilla GCN.
DefGCN |Park et al. 2022 improves the limitations of common GNNs with fixed graph
convolution and has deformable graph convolution that allows nodes adaptively capture long-range dependencies.
Graph-level Compared Methods
subtree kernel Shervashidze et al., (001T) is famous graph kernel, and AWL [Ivanov] and Burnaev 2018 is an approach for embedding entire graphs. Paired with SVM, they are selected two baselines.
DCNN (twood and Towsley 2016 PATCHY-SAN Niepert el al. 2016 and DGCNN
[Zhang el al. 2018] are three deep learning methods for graph classification, and their performance is reported as in the original paper.
20

---

90
Accuracy (%)
85
Layer
Hop
80
75
70
65
60
2
4
6
8
10
12
14
16
The Number of Layers/Hops
Figure 6: Accuracy of GCKSVM with varied layers/hops.
GCN, GraphSAGE, and GIN [Xu al. 2019 serve as GNN-based compared methods, and they are all set following (Xu el al. 2019). For the methods having different variants, we report their best performance.
Note that the settings of these graph-level methods are the same as Xu el al. 2019
Settings about Figure 1 We set the hidden dimensions as 32 for all hidden layers of GCN, APPNP, and JKNet, while SGC only has a learnable matrix W E R=*e where n is the number nodes and c is the number of classes, and the Icarning rate is selected in {1 x 10-2 10-3 10 10-4) and weight decay is selected (5 x 10-1, 5 x 10-5, x 10-9).
Settings of Boundary Visualization For better illustration, we conduct visualization experiment on the decision boundaries of SGC, APPNP, GCN, and GCKSVM. The purpose of this experiment to explore how the three methods perform on linear, non-linear, and more complex data. So we select classes of samples from Cora and Chameleon and map them to 2-D space by t-SNE. Besides, we generate a synthetic dataset (called Circle) consisting of noisy samples drawn from two concentric circles using Scikit-learn. For better boundary and performance, the numbers of layers are 2 and 8 for GCN and APPNP respectively, the hidden dimensions are 32, and the learning rate is set as 1 x 10-3 3 and weight decay is 10 for all models. SGC has only one learnable matrix and we set the power of adjacency 50 to show that the graph structure provide SGC with non- non-linearity but the non-linearity is very low.
F.2 Supplementary Experiments Node Classification
In this section, we evaluate GCKSVM more types of graph datasets. As reported in Table G can be seen that GCKSVM still has superior performance compared to the most state-of-the-ard GNNs. Furthermore, we also evaluate the proposed GCKM on the OGB dataset Arxiv with over 160k nodes. Table Aableeddemonttrall datasets. Although the complexity of GCKM is quadratic, we provide efficient variant GCKM-E Section (.4tion3..4jpe that leverages the random Fourier feature to explicitly derive a low-dimensional output instead of kernel matrix. With this output, downstream tasks, which is still more efficient than GNNs needing a lengthy training process.
that GCKM is still competitive with these GNNs on large-scale
apply fast linear methods (e.g. linear SVM) for
F.3 Experiments and Discussions on Over-smoothing Issue
Thanks for your insightful comment. We have supplemented an experiment on this issue, which revealed that GCKM can be deeper and alleviate the svoo-ingg issue. To be specific, two situations are considered in this experiment:
GCKM with fixed 2 layers and varied hops of neighbors per aggregation (g Eq. (40)
H Φ (A (1) (A (A)))).
(40)
GCKM with fixed 2 hops of neighbors per aggregation and varied layers
) 0 (A²x))
(41)
From Figure 6 have the following observations:
21

---

Table 8: Accuracy of GCKSVM with different kernel functions Cora, Citeseer, and Pubmed.
Cora
Citeseer
Pubmed
Polynomial
83.0
70.6
80.6
Sigmoid
79.7
69.2
75.6
Laplacian
82.2
70.5
79.0
Gaussian
82.4
72.3
79.8
Deep GCKM performs more stably than deep GCN.
GCKM's performance first improves then slightly decreases with increasing layers/hops
Particularly, GCKM with fixed layers performs better and decreases less.
known that over-smoothing is caused by the aggregation step, that is, multiplying À makes the representations of different nodes more and more indistinguishable. However, the analysis of over-smoothing does not consider activation functions and learnable weights, and it theoretically
exists when the power of Á tends to infinity [Li el al. 2018], which does not match the fact that GCN collapses with only 8 layers. A recent study of (Cong al. [021] has pointed out that the over-smoothing problem might be an artifact theoretical analysis and the failure of deep GNNs may not only be caused by the over-smoothing issue in the aggregation//eesage pasgggggpannngggg step.
Although GCKM and GCN share a familiar aggregation step, the main difference between them is the transformation step, namely, GCN uses linear layer to conduct explicit dimension reduction while GCKM employs implicit nigh-dimensional feature mapping. GCKM implicitly maps node features to high-dimensional (even infinite) space after aggregation, and there may exist an appropriate space where node representation can be distinguished.
contrast, a recent study of [Guo et al.) 2023) has found that the node representations processed by deep GCN would collapse to be low-rank and lose expressive power. The appropriate space can be found by tuning the hyperparameters of GCKM, however, the number of hyperparameters will increase when building deeper GCKM and it cin-cconu to search this space. That may be the reason why GCKM decreases slightly with too many layers and why fixing the number of layers improves the performance.
F.4 Experiments on Various Kernels
To solve the limitations we stated in the conclusion section. we provided complementary experiment on various kernel functions during the rebuttal process. Table records the results corresponding to 2nd order polynomial kernel, sigmoid kernel, and Laplacian kernel. All the kernel functions show decent performance and the Gaussian kernel performs the best. Note that, this experiment is conducted with GCKSVM, under the settings of node classification with standard split.
F,5 Experiments of GCKPCA
We added visualization experiment for GCKPCA. To be specific, we first map the node features to 2-D space by PCA, Graph-regularized PCA (GPCA) [Jiang el al.) 2013) and GCKPCA (row 1), then further try to map them to 32-D space and leverage t-SNE to obtain the 2-D results (row 2). Figure] 7 illustrates the comparison of mapping results of three methods. It can be observed that the subfigures of GCKPCA and GCKPCA + t-SNE both show the best separability between different classes, and GPCA performs slightly better than PCA.
F.6 Empirical Experiments regarding Theorem 1
Theorem demonstrated the connections between the generalization bound and graph structure, and experiments further provided the evidence. To verify the conclusion have made from Theorem I in the main paper, we report the training error and numbers of support vectors Table 9 In fact, we consider three cases:
Non Non-graph-connolution We replaced the affinity matrix À in GCKM with an identity matrix
In, which means the graph structure is not used.
22

---

-30
41
24
-2
-00
38
25
PCA
GPCA
GCKPCA
-50
(d) PCA ++SNE
GPCA +ESNE
GCKPCA +ESNE
Figure 7: Visualization of PCA, GPCA and GCKPCA.
Table 9: The values of the training error (TE) and the number of support vectors V/]. Note that À the regularization parameter of SVM, I, and 1 are n identity matrix and all-ones matrix respectively.
I,
Lxxe I
A
TE
[
TE
[V]
TE
|
0.01
0.50
0.20
40
Cora
10
0.00
0.50
32
0.00
30
50
0.00
72
0.50
32
0.00
24
100
0.00
72
0.50
32
0.00
24
1000
0.00
72
0.50
32
0.00
24
1
0.02
120
0.50
62
0.20
120
Cileseer
10
0.00
112
0.50
62
0.00
105
50
0.00
0.50
0.00
100
0.00
0.50
62
0.00
102
1000
0.00
111
0.50
62
0.00
102
= 1
0.12
1206
0.48
802
0.18
1366
Pubmed
10
0.05
755
0.48
802
0.10
755
50
0.02
617
0.48
794
0.07
571
100
0.01
0.48
0.07
508
1000
0.00
548
0.48
804
0.11
396
Strongly connected graph: À in GCKM replaced with I, 1axns which means every node is connected with all other nodes.
The normal GCKM.
We see that with fixed A, graph convolution significantly reduces the number of support vectors, which verifies the correctness of Theorem 2. Thus, according to Theorem 1, the upper bound (monotonically increasing with (V)) test enror can be tighter compared the one using a www.ggrraahhoootttiie kernel, which means that the test error is potentially smaller. So we can conclude that the graph structure significantly improves the quality of the kernel matrix.
23


Reviews:
[{"review_id": "G7TSmUhMvx", "reviewer": "Reviewer_dP1e", "summary": "This paper introduces a novel approach called the Graph Convolutional Kernel Machine (GCKM) for graph learning. Unlike other neural network-based frameworks, GCKM employs a graph kernel to replace the neighbor aggregation step, without any learnable parameters.\nThen the author build the features based on the graph kernel and then use SVM for classification tasks.\n\nIn general, I find the paper to be good and interesting, although it could benefit from additional experiments. I am somewhat surprised by the better performance of GCKSVM compared to GAT, considering that GAT defines the similarity of node features using learnable attention weights.", "questions": "The author discusses the issue of over-smoothing, and it raises the question of whether over-smoothing would occur when employing GCKSC with more layers. Specifically, is there a significant drop in performance when utilizing GCKSC with more than 2 layers?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Well written and clear explained\n2. good visualization (Figure 3) of the potential benefit of kernel methods: the Kernel methods offer greater interpretability compared to neural networks and provide stronger generalization guarantees.  In contrast to SGC, which functions as a linear classifier based on the final node representation, GCKSVM serves as a nonlinear classifier. Therefore, it is anticipated to outperform SGC in cases where the data is not linearly separable. \n3. Faster running time.", "weaknesses": "1. The performance is relatively underwhelming. Table 2 reveals that GCKSC achieves the best results in only 3 cases and the second-best results in 2 cases, whereas S3 GC outperforms with the best results in 3 cases and the second-best results in 3 cases.\n2. The performance reported in this paper appears to differ significantly from the results presented in the APPNP paper (https://arxiv.org/pdf/1810.05997v6.pdf). In the APPNP paper, they reported 85% accuracy on Cora and 75% accuracy on Citeseer. The substantial difference in performance raises questions about potential differences in the experimental settings between the two papers. If there are indeed differences in the experimental settings, it would be important to assess whether the conclusions drawn in this paper still hold when utilizing the experimental settings from the APPNP paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reply to Weakness 1:**\nBased on the analysis in our paper, GCKM aims to further build a simple paradigm for graph-oriented tasks.\nIt can be viewed as a further simplified baseline and its main competitors are GCN, GAE, VAGE and other simplified models, \nbut GCKMs have shown outstanding performance over not only baselines but also some SOTA methods.\nAnd we note that all the competitors are deep learning based methods and GCKMs are a series of kernel-based traditional methods.\nThus, besides the competitive performance, our models also have the following advantages:\n1. The model can achieve a **globally optimal solution** because the optimization problem is convex.\n2. The computation is **faster** because the model does not involve forward and backward propagation in the training and inference stages.\n3. The model has **higher interpretability** (e.g. the support vectors of GCKSVM form the decision boundary). \n4. The model has a **stronger theoretical guarantee** (the generalization error bound is almost tight).\n\nIn contrast, the optimizations of GNNs are nonconvex and it is very difficult or even impossible to obtain globally optimal solutions. Moreover, it is well known that the generalization bounds of neural networks are usually exponentially dependent on the network depth [1]. Last but not least, the decision process of neural networks has much lower interpretability.\n\n[1] Norm-based capacity control in neural networks. COLT 2015.\n\n**Reply to Weakness 2:** Thank you for pointing out this. Although the dataset names are the same, they are actually **different** datasets.\nThe original paper of APPNP adopted Citeseer with 2,110 nodes and Cora-ML with 2,810 nodes, while we use Citeseer with 3,327 nodes and Cora with 2,708 nodes following settings of vanilla GCN [1] (please refer to Table 1 in Appendix of our paper and Table 1 in APPNP paper), which is widely adopted in node classification methods [2, 3, 4]. There are also some recent works [3, 6, 7] that evaluated APPNP under this setting, and comparing with their results, we believe ours are fair and reasonable.\n\n[1] Semi-supervised classification with graph convolutional networks. ICLR 2017.\n\n[2] Simplifying graph convolutional networks. ICML 2019.\n\n[3] Dissecting the diffusion process in linear graph convolutional networks. NeurIPS 2021.\n\n[4] Beyond low-frequency information in graph convolutional networks. AAAI 2021.\n\n[5] Dropmessage: Unifying random dropping for graph neural networks. AAAI 2023.\n\n[6] Node-wise Diffusion for Scalable Graph Learning. WWW 2023.\n\n[7] Elastic graph neural networks. ICML 2021. \n\n**Reply to Question 1:** Thanks for your insightful comment. We have supplemented an experiment (**Figure 1 of the global rebuttal PDF file**) on this issue, which revealed that **GCKM can be deeper and alleviate the over-smoothing issue**. To be specific, two situations are considered in this experiment:\n\n1. GCKM with fixed 2 layers and varied hops of neighbors per aggregation ($q$ in Eq. (5)) \n   $$\n   \\begin{equation}\n   \\mathbf{H} = \\phi_{(1)}( \\hat{\\mathbf{A}}^{q} \\phi_{(0)}(\\hat{\\mathbf{A}}^{q} \\mathbf{X})).\n   \\end{equation}\n   $$\n\n2. GCKM with fixed 2 hops of neighbors per aggregation and varied layers\n   $$\n   \\begin{equation}\n   \\mathbf{H} = \\phi_{(l)}( \\hat{\\mathbf{A}}^{2} \\cdots \\phi_{(0)}(\\hat{\\mathbf{A}}^{2} \\mathbf{X})).\n   \\end{equation}\n   $$\n\nFrom **Figure 1 in the global rebuttal PDF file**, we have the following observations:\n\n1. Deep GCKM performs more stably than deep GCN.\n2. GCKM's performance first improves then slightly decreases with increasing layers/hops\n3. Particularly, GCKM with fixed layers performs better and decreases less.\n\nIt is known that over-smoothing is caused by the aggregation step, that is, multiplying $\\hat{\\mathbf{A}}$ makes the representations of different nodes more and more indistinguishable. However, the analysis of over-smoothing does not consider activation functions and learnable weights, and it theoretically exists when the power of $\\hat{\\mathbf{A}}$ tends to infinity [1], which does not match the fact that GCN collapses with only 8 layers. Recent studies [2, 3] have pointed out that over-smoothing problem might be an artifact of theoretical analysis and the failure of deep GNNs may not only cause by the over-smoothing issue in the aggregation/message-passing step.\n\nAlthough GCKM and GCN share a similar aggregation step, the main difference between them is the transformation step, namely, GCN uses a linear layer to conduct explicit dimension reduction while GCKM employs implicit high-dimensional feature mapping.\nGCKM implicitly maps node features to a high-dimensional (even infinite) space after aggregation, and there may exist an appropriate space where node representation can be distinguished. In contrast, recent studies [3] have found that the node representations processed by deep GCN would collapse to be low-rank and lose expressive power. The appropriate space can be found by tuning the hyperparameters of GCKM, however, the number of hyperparameters increases when building a deeper GCKM and makes it time-consuming to search for this space. That may be the reason why GCKM decreases slightly with too many layers and why fixing the number of layers improves the performance.\n\n[1] Deeper insights into graph convolutional networks for semi-supervised learning. AAAI 2018.\n\n[2] On provable benefits of depth in training graph convolutional networks. NeurIPS 2021.\n\n[3] Contranorm: A contrastive learning perspective on oversmoothing and beyond. ICLR2023."}, {"review_id": "jsrWwSzZyx", "reviewer": "Reviewer_nd8y", "summary": "This paper proposes a new support vector machine approach for graph learning called graph convolutional kernel machine. GCKM combines traditional kernel functions with graph convolution, and shows good performance in both node- and graph-level tasks. Generalization bound is also provided for the approach.", "questions": "1. How does the GCKM perform on larger datasets, e.g. open graph benchmark? Such the complexity of GCKM is quadratic, is it still more efficient than GNNs in those larger datasets?\n2. Why “graph structure significantly improved the quality of the kernel matrix” and how it affects the generalization bound?", "limitations": "See limitations in weakness section.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The proposed GCKM is simple yet effective. It is impressive that SVM-based approach can perform on par with deep GNN models in both node- and graph-level tasks.\n2. Generalization bound is provided for the proposed GCKM, which partially explains how graph structure in the construction of kernel function benefits generalization performance.\n3. Many variants are developed for applications in different scenarios.", "weaknesses": "1. Though many datasets and tasks are considered in the paper, all datasets are quite small with the largest one consisting of only 20k nodes. While the paper claims GCKM can be \"extended to large-scale data” by using low-rank approximation tricks, no experimental results on large datasets are provided. Additionally, I would also suggest the authors put some results in supplementary experiments to the main text as cora/citeseer/pubmed are somewhat outdated and insufficient to reflect the effectiveness of the proposed approach.\n2. The explanation of how the graph structure affects the generalization of GCKM is somewhat vague. Specifically, I am still confused of why “graph structure significantly improved the quality of the kernel matrix” and how it affects the generalization bound. \n3. Literature coverage could be improved. Some prior work have also analyzed how graph structure in the construction of kernel function affects generalization in graph [1] and node [2] tasks, and some others adopted kernel methods for graph learning e.g. [3,4], which are related to this work.\n4. As the authors stated in conclusion, we did not systematically test other kernel functions.\n\n[1] Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels, NeurIPS 2019  \n[2] Graph Neural Networks are Inherently Good Generalizers Insights by Bridging GNNs and MLPs, ICLR 2023  \n[3] Convolutional Kernel Networks for Graph-Structured Data, ICML 2020  \n[4] KerGNNs: Interpretable Graph Neural Networks with Graph Kernels, AAAI 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reply to Weakness 1/Question 1:**\nThanks for your constructive suggestions.\nWe have added a comparison experiment on the OGB dataset Arxiv with about 160k nodes. Table 1 (see the attached **PDF**) demonstrates that GCKM is still competitive with these GNNs on large-scale datasets. Although the complexity of GCKM is quadratic, we provide an efficient variant GCKM-E in Section 3.4 that leverages the random Fourier feature to explicitly derive a low-dimensional output instead of a kernel matrix. With this output, we can apply fast linear methods (e.g. linear SVM) for downstream tasks, which is still more efficient than GNNS needing a lengthy training process.\n\n**Reply to Weakness 2/Question 2:**\nThank you for the valuable comment. Theorem 1 theoretically demonstrated the connections between the generalization bound and graph structure, and experiments further provide the evidence.\nThe results are recorded in Table 4 of Appendix, here we intercept a part of the table in **Table 3 of the global rebuttal PDF file**. \n  \nWe considered the following three cases for a comprehensive comparison.\n1. **non-graph-convolution**  We replaced the affinity matrix $\\hat{\\mathbf{A}}$ in GCKM with an identity matrix $\\mathbf{I}_n$, which means the graph structure is not used.\n2. **strongly connected graph**  $\\ \\hat{\\mathbf{A}}$ in GCKM is replaced by $\\mathbf{I}\\_{n}-\\mathbf{1}\\_{n \\times n}$, which means every node is connected with all other nodes. \n3. **normal GCKM**\n  \nWith fixed $\\lambda$, graph convolution significantly reduces the number of support vectors and spectral norm on the kernel matrix of support vectors. \nAccording to Theorem 1, the upper bound (linear with $\\vert\\mathcal{V}\\vert$ and $\\big\\\\|[K^{(L)}\\_{ij}]\\_{i,j\\in\\mathcal{V}}\\big\\\\|\\_{\\text{spec}}$) of test error can be reduced compared to using a non-graph-convolution kernel.\nThus, we can conclude that the graph structure significantly improved the quality of the kernel matrix.\n\n**Reply to Weakness 3:**\nThank you for raising this problem. We have revised our manuscript, discussing the differences and citing these related research. \n\n**Reply to Weakness 4:**\nThank you for pointing out this limitation. We have provided a complementary experiment on various kernel functions in **Table 2 of the global rebuttal PDF file**, including 2nd order polynomial kernel, sigmoid kernel, and Laplacian kernel. \nAll the kernel functions show decent performance and the Gaussian kernel performs the best."}, {"review_id": "vh3OO55Imt", "reviewer": "Reviewer_YFNo", "summary": "This paper presents a kernel-based message-passing framework for graph convolutional networks called GCKM. The author demonstrated that GCKM is computationally efficient with stable performance on both node classification and graph classification tasks. Theoretical analyses of GCKM are provided.", "questions": "1. What is the memory requirement of GCKM, when compared to other methods?\n\n2. The over-smoothing problem in GCN or another type of GNN models is caused by stacking multiple message-passing layers, and eventually, every node shares similar embeddings. In Formula (5), a single GCKM layer is constructed by applying several times of graph convolution and using a pre-defined Gaussian kernel function as the ReadOut function. How does this architecture address the over-smoothing problem? \n\n", "limitations": "Not sure if the choice/design of kernel may cause any biases.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. GCKM modifies the general GNN by replacing the trainable parameters and non-linear activation functions with kernels (e.g., RBF Gaussian kernel). Classification is then done using well-established SVM. The proposed method significantly reduces the running time. \n2. Provide theoretical analyses. \n", "weaknesses": "1. In section 3.4, the author claims that their method can be applied to very large graph datasets. What does “large” mean? In experiments, only small graph datasets (Cora, Citeseer, and PubMed) were used. How about relatively large datasets like Reddit or OGB datasets?\n2. The value/insight of Theorem 1 is unclear. How can one use it to guide the design of GCKM models? How close is the theoretical bound to experimental observations? How can this address the challenges (like over-smoothing or improving model performances)?\n3. Previous work [1] already conducts extensive exploration on applying kernel methods on GNNs, the author needs to discuss or compare their method with it. \n4. The settings of the models used to produce Figures 1 and 2, e.g. the number of layers, and hidden dimensions, especially for the deep GCNs.\n5. Abstract claims \"GCKMs are guaranteed to obtain globally optimal solutions and have strong generalization ability and high interpretability.\" If true, should the GCKM produce the best results on all dataset? Interpretability need to be elaborated.\n\n[1] Chen, Dexiong, Laurent Jacob, and Julien Mairal. \"Convolutional kernel networks for graph-structured data.\" International Conference on Machine Learning. PMLR, 2020.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reply to Weakness 1:**\nThanks for your valuable suggestions.\nWe added a comparison experiment on OGB dataset Arxiv with about 160k nodes. Table 1 (in the attached **PDF**) demonstrates that GCKM is still competitive with these GNNs on large-scale dataset. Although the complexity of GCKM is quadratic, we provide an efficient variant GCKM-E in Section 3.4 that leverages the random Fourier feature to explicitly derive a low-dimensional output instead of a kernel matrix. With this output, we can apply fast linear methods (e.g. linear SVM) for downstream tasks, which is still more efficient than GNNS needing a lengthy training process.\n\n**Reply to Weakness 2:**\nThe theorem showed that the generalization error bound is linear with $\\vert\\mathcal{V}\\vert$ and $\\big\\\\|[K^{(L)}\\_{ij}]\\_{i,j\\in\\mathcal{V}}\\big\\\\|\\_{\\text{spec}}$. We showed in Table 4 of Appendix (or an intercepted part in **Table 3 of the global rebuttal PDF file**) that the graph convolution can reduce both $\\vert\\mathcal{V}\\vert$ and $\\big\\\\|[K^{(L)}\\_{ij}]\\_{i,j\\in\\mathcal{V}}\\big\\\\|\\_{\\text{spec}}$, and then lead to a tighter error bound. A tighter generalization error bound means that the test error is potentially smaller. In other words, graph convolution improves the model performance.\n\n**Reply to Weakness 3:**\nMany thanks for pointing out the reference [1] (GCKN). It is indeed an interesting paper. We have revised our manuscript and discussed this work. Here we mainly state the differences and our unique contributions:\n\n1. Motivated by the previous studies of \"graph kernel\" (computing the similarity between entire graphs) and GNNs, GCKN [1] focuses on graph-level tasks and aims to connect graph kernel and GNNs. Differently, our GCKM is motivated by the unsatisfactory performance of deep GNNs and the possibility of classical kernel machine learning.  GCKM is built upon kernels rather than neural networks. In other words, GCKM is a general framework that can be applied to both node-level tasks and graph-level tasks. It is parallel to GNNs.\n2. GCKN constructs a neural network via employing the graph kernels and shows decent performance on graph-level tasks, while GCKMs are a series of graph convolutional kernel based machine learning approaches and perform well on several downstream tasks. Nevertheless, due to the path kernel, GCKN can be time-consuming when the path lengths is long.\nGCKM has advantages like a globally optimal solution, faster computation, higher interpretability, and a stronger theoretical guarantee.\n3. We propose an efficient variant GCKM-E to explicitly compute the node representation and can also be easily extended.\n4. We provide theoretical and empirical analyses of the graph's influence on the test error bound.\n5. We now demonstrate that GCKM can perform well on large-scale OGB dataset and can be deeper and alleviate the so-called over-smoothing issue.\n\n[1] Convolutional kernel networks for graph-structured data. ICML 2020.\n\n**Reply to Weakness 4:**\nThank you for this valuable advice. Figure 2 is the flowchart of GCKM, maybe you mean Figure 3? For Figure 1, we set the hidden dimensions as $32$ for all hidden layers of GCN, APPNP, and JKNet, while SGC only has a learnable matrix $\\mathbf{W} \\in \\mathbb{R}^{n\\times c}$ where $n$ is the number of nodes and $c$ is the number of classes, and learning rate is selected in $\\{ 1 \\times 10^{-2}, 1 \\times 10^{-3}, 1 \\times 10^{-4}\\}$ and weight decay is selected in $\\{ 5 \\times 10^{-4}, 5 \\times 10^{-5}, 5 \\times 10^{-6}\\}$.\nFor Figure 3, the numbers of layers are $2$ and $8$ for GCN and APPNP respectively, the hidden dimensions are $32$, and the learning rate is set as $1 \\times 10^{-3}$ and weight decay is $5 \\times 10^{-5}$ for all models.\n\n**Reply to Weakness 5:**\nThank you for raising these. Actually, we claimed the following opinions and corresponding reasons:\n1. The model can achieve a globally optimal solution because the optimization problem is convex.\n2. Theorem 1 and the experiments demonstrate good generalization ability.\n3. The model has higher interpretability because the support vectors form the decision boundary.\n\nThese three statements about GCKM are the potential reasons for GCKMs' good performance. They do not mean that GCKMs should produce the best results on all datasets in comparison to other methods. Here the optimality means in terms of optimization, GCKM can obtain its optimal solution given the current architecture and hyperparameters on a specific dataset.\n\n**Reply to Question 1:**\nThe space complexity of GCKM and GCKM-E are $\\mathcal{O}(n^2)$ and $\\mathcal{O}((n+d)m)$ respectively, while a typical GNN, like GCN, requires $\\mathcal{O}((n+d')m)$, if the edges are sparse, where $n$ is the number of nodes, $m$, is the number of input feature dimension, $d$ and $d'$ are the hidden dimensions of GCKM-E and GNN respectively. Although GCKM has high memory requirement when the graph is large, we can use GCKM-E paired with a linear method (e.g. linear SVM) to reduce the complexity.\n\n**Reply to Question 2:**\nThanks for pointing out this. \nThe ReadOut function is only adopted in the graph-level variant, and the over-smoothing problem is mainly discussed in the context of node-level tasks, so we analyze this phenomenon on the node classification task.\nWe have supplemented an experiment on this issue in **Figure 1 of the global rebuttal PDF file**, which revealed that **GCKM can be deeper and alleviate the over-smoothing issue**.\nDue to the limitation of characters, **please refer to the Reply to Question 1 in response to Reviewer dP1e for detailed analyses.**\n\n**Reply to Limitation 1:**\nThank you for pointing out this limitation. We have provided a complementary experiment on various kernel functions in **Table 2 of the global rebuttal PDF file**, including 2nd order polynomial kernel, sigmoid kernel, and Laplacian kernel. All the kernel functions show decent performance and the Gaussian kernel performs the best.\n"}, {"review_id": "ISMA1wZk4x", "reviewer": "Reviewer_PZjL", "summary": "The paper presents a framework called graph convolutional kernel machine (GCKM) for graph-based machine learning. GCKMs are built upon kernel functions integrated with graph convolution. Within the framework of GCKM, the authors propose GCKSVM for node classification, GCKSC for node clustering, and extensions for graph-level learning. The experiments show that GCKMs have at least competitive accuracy compared to GCNs.", "questions": "1. In line 171, it is claimed “GCKM with Gaussian kernels can be easily generalized to multi-layer cases”. Could the authors provide a recursive or explicit formulation of deep GCKM? Is there a rule of thumb to determine the number of layers for deep GCKM?\n2. In line 204, the formulation “...has tiny influences on the training...and the spectral norm of $[K_{ij}^{(L)}]_{i,j\\in V}$...” is a little bit confusing. The matrix will become smaller if there are fewer support vectors and a smaller matrix usually has a smaller spectral norm.\n3. In Eq. (18) or Eq. (16), the graph-level feature is obtained as the sum of nodes’ features. Is there any explanation for this operation? How about using the mean or min/max of nodes’ features as graph feature?\n4. At the end of Section 3.4, I suggest the authors highlight the computational complexity in comparison to the implicit feature transformation method.\n5. In the first column of Figure 3, why are the decision boundaries of SGC in the second and third plots are not nonlinear?", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents a framework GCKM for graph-based machine learning. As far as I am concerned, this is a novel framework. Compared to GCNs, GCKMs are easier to train, are guaranteed to obtain globally optimal solutions, and have strong generalization ability. \n2. The authors provided generalization bound for GCKSVM, which justified the advantage of GCKSVM over KSVM.\n3. The authors provided GCKM extensions to node clustering, graph classification, etc. They also provided fast feature transformation for GCKM. \n4. The numerical evaluation are sufficient, which showed the proposed methods are at least as effective as GCNs.", "weaknesses": "Two minor issues are as follows.\n1. In Section 3.3, the extension GCKPCA hasn’t been evaluated. \n2. Some important results are in the supplement rather than the main paper. The authors may reorganize the paper and show the numerical justification for Theorem 1 and the experiment of graph-level learning in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Reply to Weakness 1:**\nThanks for your constructive advice. We have added a visualization experiment for GCKPCA, which is shown in the attached **PDF**.\nTo be specific, we first map the node features to 2-D space by PCA, Graph-regularized PCA (GPCA) [1, 2] and GCKPCA, then further try to map them to 32-D space and leverage t-SNE to obtain the 2-D results.\nFigure 2 illustrates the comparison of mapping results of three methods. It can be observed that the figures of GCKPCA and GCKPCA + t-SNE both show the best separability between different classes, and GPCA performs slightly better than PCA.\n\n[1] Zhang, Zhenyue, and Keke Zhao. Low-rank matrix approximation with manifold regularization. TPAMI 2012.\n\n[2] Jiang, Bo, et al. Graph-Laplacian PCA: Closed-form solution and robustness. CVPR 2013.\n\n**Reply to Weakness 2:**\nThanks for this helpful suggestion. We have adjusted our paper and will put these results on the additional page if accepted.\n\n**Reply to Question 1:**\nThank you for raising this. To obtain the kernel matrix, we have the following recursive formulation:\n$$\n\\begin{equation}\n{K}^{(l+1)}\\_{i,j} = \\exp\\left(\\frac{(\\hat{\\mathbf{A}}^{q})\\_{i} \\mathbf{K}^{(l)} (\\hat{\\mathbf{A}}^{q})^{\\top}\\_{i} - 2 (\\hat{\\mathbf{A}}^{q})_{i} \\mathbf{K}^{(l)} (\\hat{\\mathbf{A}}^{q})^{\\top}\\_{j} + (\\hat{\\mathbf{A}}^{q})\\_{j} \\mathbf{K}^{(l)} (\\hat{\\mathbf{A}}^{q})^{\\top}\\_{j}}{2\\sigma\\_{l+1}^{2}}\\right).\n\\end{equation}\n$$\n\nwhere we define $\\mathbf{K}^{(0)} = \\mathbf{X} \\mathbf{X}^{\\top}$ in particular. For convenience, it can also be rewritten in matrix form:\n\n$$\n\\begin{align}\n\\begin{cases}\n\\bar{\\mathbf{K}}^{(l+1)} = \\hat{\\mathbf{A}}^{q} \\mathbf{K}^{(l)} (\\hat{\\mathbf{A}}^{q})^{\\top}, \\\\\\\\\n\\mathbf{K}^{(l+1)}\n= \\exp\\left(-\\frac{\\mathbf{1}\\_{n}^{\\top} \\mathbf{d}\\_{\\bar{\\mathbf{K}}^{(l+1)}} + \\mathbf{d}\\_{\\bar{\\mathbf{K}}^{(l+1)}} \\mathbf{1}\\_{n} - 2 \\bar{\\mathbf{K}}^{(l+1)}}{2\\sigma^{2}\\_{l+1}}\\right),\n\\end{cases}\n\\end{align}\n$$\n\nwhere $\\mathbf{d}_ {\\bar{\\mathbf{K}}^{(l+1)}} = [\\bar{K}_ {11}^{(l+1)}, \\bar{K}_ {22}^{(l+1)}, \\ldots, \\bar{K}_ {nn}^{(l+1)}]$.\n\nWe have also provided an experiment discussing the depth of GCKM in Figure 1.\nIt shows that a 2-6 layer GCKM performs the best, attributed to which a deeper model requires more hyperparameters to be tuned.\nBesides, GCKM is not a neural network and thus benefits less from depth, and we can also increase the power of $\\hat{\\mathbf{A}}^{q}$ to reach more hops of neighborhood information in a layer.\n\n**Reply to Question 2:**\nSorry for the misleading formulation. We meant that for a fixed number of support vectors, the graph convolution has a small influence on the spectral norm. But in reality, the graph convolution operation reduced the number of support vectors and the matrix become smaller, which leads to a smaller spectral norm.\n\n**Reply to Question 3:**\nThank you for pointing out this. It is a widely adopted operator in graph-level tasks, which is called ReadOut function. All these min/max, mean, or sum of nodes' features are included in ReadOut functions, but [1] have proved that sum has a more powerful expressive ability over other ReadOut functions and we follow their setting to choose it. In practice, we also find that sum is better than other ReadOut functions.\n\n**Reply to Question 4:**\nThanks for your helpful comment, we have revised our manuscript and highlighted this.\n\n**Reply to Question 5:**\nActually, the decision boundaries of SGC are all nonlinear (because of the $\\hat{\\mathbf{A}}^q$) but approximately linear.\nThe key idea of SGC is removing nonlinearities and collapsing weight matrices, thus the forward computation is simply formulated as\n\n$$\n\\begin{equation}\n\\mathbf{Z} = \\hat{\\mathbf{A}}^{q} \\mathbf{X} \\mathbf{W}.\n\\end{equation}\n$$\n\nWith a single learnable weight matrix and without activation functions, SGC's decision boundaries are all approximately linear, and the graph convolution provides slight nonlinearity to SGC."}]

Author rebuttal:
We would like to thank the Senior Area Chairs/Area Chairs and all the Reviewers for handling our paper and providing constructive comments.
We have systematically and carefully replied to all the comments and revised our work based on comments from the reviewers. 
In addition, we have attached a PDF file including four experiments to support our response, and all these source codes can be provided if needed.
The following is the summary of mainly focused problems and our response:
1. **Deep GCKM and over-smoothing issue.** We have conducted experiments (**Figure 1 of the PDF file**) considering two situations and showed that GCKM can be deeper and alleviate the over-smoothing issue. Besides, we analyzed the possible reasons in the response.
2. **Performance and efficiency on large-scale datasets.** We have provided results on the OGB dataset Arixv with over 160k nodes (**Table 1 of the PDF file**), where GCKM is still competitive with other baseline and SOTA methods.
3. **Explanation of Theorem 1.** We have further explained Theorem 1 and put the corresponding experimental results in **Table 3 of the PDF file** (full table in Appendix). Theoretical and empirical results revealed that graph convolution in GCKM can improve the generalization bound.
4. **Experiments of GCKPCA.** The results are in Figure 2 of the attached PDF file. GCKPCA outperformed PCA and GPCA.

Besides these, we also evaluated GCKM with different kernel functions (**recorded in Table 2 of the PDF file**) and also further elaborated on the experimental settings, discussion with related work, the effectiveness of GCKM, etc.

Finally, many thanks to the positive assessments that encouraged us a lot:
1. R1: "Well written and clear explained; good visualization."
2. R2: "The proposed GCKM is simple yet effective; it is impressive."
3. R4: "This is a novel framework."

Meta-review: This paper introduces a new approach called the Graph Convolutional Kernel Machine (GCKM) for graph-based machine learning, which are built upon kernel functions integrated with graph convolution. Overall, the reviewers found the paper to be well-written, and they found the results to be both interesting and significant. However, they suggested that additional experiments could enhance the paper's quality. The authors are encouraged to consider the reviewers' feedback during the revision process.
Decision: Accept (poster)