Stability and Generalization of Graph Convolutional Neural Networks
Stability and Generalization of Graph Convolutional Neural Networks
复制标题
DOI：
10.1145/3292500.3330956
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Saurabh Verma;Zhi-Li Zhang
中科院分区：
文献类型：
--
作者：
Saurabh Verma;Zhi-Li Zhang
受1D和2D数据的卷积神经网络的启发，图形卷积神经网络（GCNN）已开发出用于图形数据的各种学习任务，并在现实世界数据集上显示出卓越的性能。尽管他们成功了，但仍缺乏GCNN模型的理论探索，例如它们的概括属性。在本文中，我们迈出了第一步，通过分析单层GCNN模型的稳定性并在半监视的图形学习设置中得出了对GCNN模型的更深入的理论理解。特别是，我们表明，GCNN模型的算法稳定性取决于其图形卷积滤波器的最大绝对特征值。此外，为了确保提供强大的概括保证所需的统一稳定性，最大的绝对特征值必须独立于图形大小。我们的结果提供了有关新的和改进的图形卷积过滤器设计的新见解，并保证了算法稳定性。我们评估了各种现实世界图数据集上的概括差距和稳定性，并表明经验结果确实支持我们的理论发现。据我们所知，我们是第一个在半监督环境中研究图形学习的稳定性界限的人，并为GCNN模型提供了概括。
Inspired by convolutional neural networks on 1D and 2D data, graph convolutional neural networks (GCNNs) have been developed for various learning tasks on graph data, and have shown superior performance on real-world datasets. Despite their success, there is a dearth of theoretical explorations of GCNN models such as their generalization properties. In this paper, we take a first step towards developing a deeper theoretical understanding of GCNN models by analyzing the stability of single-layer GCNN models and deriving their generalization guarantees in a semi-supervised graph learning setting. In particular, we show that the algorithmic stability of a GCNN model depends upon the largest absolute eigenvalue of its graph convolution filter. Moreover, to ensure the uniform stability needed to provide strong generalization guarantees, the largest absolute eigenvalue must be independent of the graph size. Our results shed new insights on the design of new & improved graph convolution filters with guaranteed algorithmic stability. We evaluate the generalization gap and stability on various real-world graph datasets and show that the empirical results indeed support our theoretical findings. To the best of our knowledge, we are the first to study stability bounds on graph learning in a semi-supervised setting and derive generalization bounds for GCNN models.