A Simple Spectral Failure Mode for Graph Convolutional Networks

Neural networks have achieved remarkable successes in machine learning tasks. This has recently been extended to graph learning using neural networks. However, there is limited theoretical work in understanding how and when they perform well, especially relative to established statistical learning techniques such as spectral embedding. In this short paper, we present a simple generative model where unsupervised graph convolutional network fails, while the adjacency spectral embedding succeeds. Specifically, unsupervised graph convolutional network is unable to look beyond the first eigenvector in certain approximately regular graphs, thus missing inference signals in non-leading eigenvectors. The phenomenon is demonstrated by visual illustrations and comprehensive simulations.

1 Introduction

Graph embedding aims to learn a low-dimensional representation for each node in a given graph, on which subsequent inferences can be directly performed. Recently, graph neural networks have emerged an attractive graph embedding solution due to the representation power: they can learn nonlinear mappings from the graph space to the embedding space, while traditional methods such as matrix factorization are restricted to linear mappings [1]. On the other hand, powerful graph neural networks can fail if their architectures do not align with the downstream tasks [2].