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.

本文研究了图卷积神经网络在半监督学习环境下的算法稳定性及其一阶推论；通过分析单层GCNN模型的稳定性，导出其一般化保证，提出稳定性关于其卷积核最大绝对特征值的依赖规律，并说明产生保证所需的卷积核最大特征值与图大小无关，为设计保证的算法稳定性的新型及更好的卷积核提供新思路。最后在多个真实世界的图数据集上评估了实验结果，实验结果支持理论结果。

图卷积神经网络的稳定性和泛化性能