CKGConv: General Graph Convolution with Continuous Kernels
This addresses the challenge of defining general convolution operators for graphs, which is important for machine learning on irregular data structures, though it appears incremental as it builds upon existing graph convolution and transformer methods.
The authors tackled the problem of inflexible and non-unified graph convolution definitions by proposing CKGConv, a general framework using continuous kernels from pseudo-coordinates, which matches graph transformers in expressiveness and outperforms existing graph convolutional networks on various datasets.
The existing definitions of graph convolution, either from spatial or spectral perspectives, are inflexible and not unified. Defining a general convolution operator in the graph domain is challenging due to the lack of canonical coordinates, the presence of irregular structures, and the properties of graph symmetries. In this work, we propose a novel and general graph convolution framework by parameterizing the kernels as continuous functions of pseudo-coordinates derived via graph positional encoding. We name this Continuous Kernel Graph Convolution (CKGConv). Theoretically, we demonstrate that CKGConv is flexible and expressive. CKGConv encompasses many existing graph convolutions, and exhibits a stronger expressiveness, as powerful as graph transformers in terms of distinguishing non-isomorphic graphs. Empirically, we show that CKGConv-based Networks outperform existing graph convolutional networks and perform comparably to the best graph transformers across a variety of graph datasets. The code and models are publicly available at https://github.com/networkslab/CKGConv.