In this work, we study the problem of stability of Graph Convolutional Neural Networks (GCNs) under random small perturbations in the underlying graph topology, i.e. under a limited number of insertions or deletions of edges. We derive a novel bound on the expected difference between the outputs of unperturbed and perturbed GCNs. The proposed bound explicitly depends on the magnitude of the perturbation of the eigenpairs of the Laplacian matrix, and the perturbation explicitly depends on which edges are inserted or deleted. Then, we provide a quantitative characterization of the effect of perturbing specific edges on the stability of the network. We leverage tools from small perturbation analysis to express the bounds in closed, albeit approximate, form, in order to enhance interpretability of the results, without the need to compute any perturbed shift operator. Finally, we numerically evaluate the effectiveness of the proposed bound.

本文研究了图卷积神经网络在图拓扑的随机小扰动下的稳定性问题，通过导出了一个新的界限，明确了未经扰动和经扰动图卷积神经网络输出之间的期望差异，该界限明确取决于拉普拉斯矩阵特征对的扰动程度以及插入或删除的边。在此基础上，我们定量地描述了特定边的扰动对网络稳定性的影响，并利用小扰动分析工具来以闭合但近似的形式表达界限，以提高结果的解释性，而无需计算任何扰动移位运算符。最后，我们对所提出的界限的有效性进行了数值评估。

图卷积神经网络的稳定性：小扰动分析视角