A Simple Spectral Failure Mode for Graph Convolutional Networks
arXiv:2010.13152 · doi:10.1109/TPAMI.2021.3104733
Abstract
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.
References in corpus (10)
- Auto-Encoding Variational Bayes
- Graph Embedding Techniques, Applications, and Performance: A Survey
- Consistency of community detection in networks under degree-corrected stochastic block models
- Stability Properties of Graph Neural Networks
- Statistical inference on random dot product graphs: a survey
- ASGN: An Active Semi-supervised Graph Neural Network for Molecular Property Prediction
- A Survey on The Expressive Power of Graph Neural Networks
- On a 'Two Truths' Phenomenon in Spectral Graph Clustering
- Universally consistent vertex classification for latent positions graphs
- Consistency of adjacency spectral embedding for the mixed membership stochastic blockmodel