Stability of Graph Neural Networks to Relative Perturbations
Graph neural networks (GNNs), consisting of a cascade of layers applying a graph convolution followed by a pointwise nonlinearity, have become a powerful architecture to process signals supported on graphs. Graph convolutions (and thus, GNNs), rely heavily on knowledge of the graph for operation. However, in many practical cases the GSO is not known and needs to be estimated, or might change from training time to testing time. In this paper, we are set to study the effect that a change in the underlying graph topology that supports the signal has on the output of a GNN. We prove that graph convolutions with integral Lipschitz filters lead to GNNs whose output change is bounded by the size of the relative change in the topology. Furthermore, we leverage this result to show that the main reason for the success of GNNs is that they are stable architectures capable of discriminating features on high eigenvalues, which is a feat that cannot be achieved by linear graph filters (which are either stable or discriminative, but cannot be both). Finally, we comment on the use of this result to train GNNs with increased stability and run experiments on movie recommendation systems.
Code (0)
등록된 구현이 없습니다.
Tasks
Movie RecommendationRecommendation SystemsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Stability of Neural Networks on Manifolds to Relative Perturbations
Graph Neural Networks (GNNs) show impressive performance in many practical scenarios, which can be largely attributed to their stability properties. Empirically, GNNs can scale well on large size graphs, but this is cont…
Stability of Flow Models for Graph Signals
Generating signals on graphs requires permutation-equivariant models that exhibit stability with respect to relative structural perturbations. While favorable stability properties of Graph Neural Networks (GNNs) have bee…
Stability of Graph Convolutional Neural Networks to Stochastic Perturbations
Graph convolutional neural networks (GCNNs) are nonlinear processing tools to learn representations from network data. A key property of GCNNs is their stability to graph perturbations. Current analysis considers determi…
Limitless stability for Graph Convolutional Networks
This work establishes rigorous, novel and widely applicable stability guarantees and transferability bounds for graph convolutional networks -- without reference to any underlying limit object or statistical distribution…
On the Stability of Graph Convolutional Neural Networks: A Probabilistic Perspective
Graph convolutional neural networks (GCNNs) have emerged as powerful tools for analyzing graph-structured data, achieving remarkable success across diverse applications. However, the theoretical understanding of the stab…