Stability Properties of Graph Neural Networks
This addresses the robustness and performance of GNNs for applications like recommender systems and power outage prediction, providing theoretical insights into their superior behavior.
The paper analyzes how changes in graph topology affect Graph Neural Network (GNN) outputs, showing that GNNs with integral Lipschitz filters and nonlinearities achieve both stability to small topology changes and discriminative power for high-frequency information, unlike linear graph filters.
Graph neural networks (GNNs) have emerged as a powerful tool for nonlinear processing of graph signals, exhibiting success in recommender systems, power outage prediction, and motion planning, among others. GNNs consists of a cascade of layers, each of which applies a graph convolution, followed by a pointwise nonlinearity. In this work, we study the impact that changes in the underlying topology have on the output of the GNN. First, we show that GNNs are permutation equivariant, which implies that they effectively exploit internal symmetries of the underlying topology. Then, we prove that graph convolutions with integral Lipschitz filters, in combination with the frequency mixing effect of the corresponding nonlinearities, yields an architecture that is both stable to small changes in the underlying topology and discriminative of information located at high frequencies. These are two properties that cannot simultaneously hold when using only linear graph filters, which are either discriminative or stable, thus explaining the superior performance of GNNs.