A Simple Spectral Failure Mode for Graph Convolutional Networks
A Simple Spectral Failure Mode for Graph Convolutional Networks
复制标题
DOI：
10.1109/tpami.2021.3104733
复制
发表时间：
2020-10
影响因子：
23.6
通讯作者：
C. Priebe;Cencheng Shen;Ningyuan Huang;Tianyi Chen
中科院分区：
文献类型：
--
作者：
C. Priebe;Cencheng Shen;Ningyuan Huang;Tianyi Chen
神经网络在机器学习任务中取得了显著的成功。这最近已经扩展到使用神经网络的图形学习。然而，在了解它们如何以及何时表现良好方面，理论工作有限，特别是相对于谱嵌入等既定统计学习技术。在这篇简短的论文中，我们提出了一个简单的生成模型，其中无监督图卷积网络失败，而邻接谱嵌入成功。具体来说，无监督图卷积网络无法在某些近似规则的图中看到第一个特征向量之外，因此丢失了非前导特征向量中的推理信号。这一现象通过直观的插图和全面的模拟来证明。
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.