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.
