Improved Stability Bounds for Graph Convolutional Neural Networks Under Graph Perturbations

Graph convolutional neural networks (GCNNs) have emerged as powerful tools for processing signals or data supported by graphs. However, their effectiveness is compromised when perturbations exist in the graph structures. While previous research has studied the stability of GCNNs against such perturbations by analyzing the behavior of the graph convolutional filters, we found a significant discrepancy exists between the theoretical stability bounds and simulation outcomes. In this paper, we propose a novel approach to characterize the stability of GCNNs more accurately. Unlike existing methods that treat graph convolutional filters in each layer of a GCNN as separate SISO systems, our approach views them as a compact MIMO system. This perspective yields an improved stability characterization that aligns more closely with empirical observations and provides insights into designing GCNNs that are more resilient to graph perturbations. Numerical experiments on synthetic data confirm our theoretical findings and experiments on a movie recommendation problem demonstrate how it helps train stable GCNNs.