Graph Convolutional Kernel Machine versus Graph Convolutional Networks

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) 1 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. * Corresponding author. 1 The source code is available at https://github.com/ZhihaoWu99/GCKM . 37th Conference on Neural Information Processing Systems (NeurIPS 2023). • 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 a generalization error bound for GCKM-based node classification and prove that graph structure can tighten this bound, both theoretically and empirically. • We provide a 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 stateof-the-art GCNs and significantly surpass several GCN-based methods on node semi-supervised classification and clustering tasks.