Simple Spectral Graph Convolution

Abstract

Graph Convolutional Networks (GCNs) have drawn significant attention and become leading methods for learning graph representations. The most GCNs suffer the performance loss when the depth of the model increases. Similarly to CNNs, without specially designed architectures, the performance of a network degrades quickly with increased depth. Some researchers argue that the required neighbourhood size and neural network depth are two completely orthogonal aspects of graph representation. Thus, several methods extend the neighbourhood by aggregating k-hop neighbourhoods of nodes while using shallow neural networks. However, these methods still encounter oversmoothing, high computation and storage costs. In this paper, we use a modified Markov Diffusion Kernel to derive a variant of GCN called Simple Spectral Graph Convolution (S2GC). Our spectral analysis shows that our simple spectral graph convolution used in S2GC is a trade-off of low-pass and high-pass filter which captures the global and local contexts of each node. We provide two theoretical claims which demonstrate that we can aggregate over a sequence of increasingly larger neighborhoods compared to competitors while limiting severe oversmoothing. Our experimental evaluation demonstrates that S2GC with a linear learner is competitive in text, node and graph classification tasks. Moreover, S2GC is comparable to other state-of-the-art methods for node clustering and community prediction tasks.