SAGMAN: Stability Analysis of Graph Neural Networks on the Manifolds
This work addresses stability issues in GNNs for applications like recommendation systems, but it is incremental as it builds on existing spectral and probabilistic methods.
The authors tackled the problem of graph neural networks (GNNs) being sensitive to input changes by introducing SAGMAN, a spectral framework for analyzing GNN stability through distance distortions between input and output manifolds, with empirical evaluations showing it effectively assesses node stability under perturbations and aids in enhancing stability and adversarial attacks.
Modern graph neural networks (GNNs) can be sensitive to changes in the input graph structure and node features, potentially resulting in unpredictable behavior and degraded performance. In this work, we introduce a spectral framework known as SAGMAN for examining the stability of GNNs. This framework assesses the distance distortions that arise from the nonlinear mappings of GNNs between the input and output manifolds: when two nearby nodes on the input manifold are mapped (through a GNN model) to two distant ones on the output manifold, it implies a large distance distortion and thus a poor GNN stability. We propose a distance-preserving graph dimension reduction (GDR) approach that utilizes spectral graph embedding and probabilistic graphical models (PGMs) to create low-dimensional input/output graph-based manifolds for meaningful stability analysis. Our empirical evaluations show that SAGMAN effectively assesses the stability of each node when subjected to various edge or feature perturbations, offering a scalable approach for evaluating the stability of GNNs, extending to applications within recommendation systems. Furthermore, we illustrate its utility in downstream tasks, notably in enhancing GNN stability and facilitating adversarial targeted attacks.