SAGMAN: Stability Analysis of Graph Neural Networks on the Manifolds

• URL: http://arxiv.org/abs/2402.08653v4
• Date: Wed, 09 Oct 2024 16:51:02 GMT
• Title: SAGMAN: Stability Analysis of Graph Neural Networks on the Manifolds
• Authors: Wuxinlin Cheng, Chenhui Deng, Ali Aghdaei, Zhiru Zhang, Zhuo Feng,
• Abstract summary: Modern graph neural networks (GNNs) can be sensitive to changes in the input graph structure and node features. We introduce a spectral framework known as SAGMAN for examining the stability of GNNs.
• Score: 11.839398175390548
• License:
• Abstract: 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.

Related papers

• Uncertainty in Graph Neural Networks: A Survey [50.63474656037679]
  Graph Neural Networks (GNNs) have been extensively used in various real-world applications. However, the predictive uncertainty of GNNs stemming from diverse sources can lead to unstable and erroneous predictions. This survey aims to provide a comprehensive overview of the GNNs from the perspective of uncertainty.
  arXiv  Detail & Related papers  (2024-03-11T21:54:52Z)
• Accurate and Scalable Estimation of Epistemic Uncertainty for Graph Neural Networks [40.95782849532316]
  We propose a novel training framework designed to improve intrinsic GNN uncertainty estimates. Our framework adapts the principle of centering data to graph data through novel graph anchoring strategies. Our work provides insights into uncertainty estimation for GNNs, and demonstrates the utility of G-$Delta$UQ in obtaining reliable estimates.
  arXiv  Detail & Related papers  (2024-01-07T00:58:33Z)
• Robust Node Representation Learning via Graph Variational Diffusion Networks [7.335425547621226]
  In recent years, compelling evidence has revealed that GNN-based node representation learning can be substantially deteriorated by perturbations in a graph structure. To learn robust node representation in the presence of perturbations, various works have been proposed to safeguard GNNs. We propose the Graph Variational Diffusion Network (GVDN), a new node encoder that effectively manipulates Gaussian noise to safeguard robustness on perturbed graphs.
  arXiv  Detail & Related papers  (2023-12-18T03:18:53Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  We propose DEGREE to provide a faithful explanation for GNN predictions. By decomposing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. We also design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods.
  arXiv  Detail & Related papers  (2023-05-22T10:29:52Z)
• EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks [51.42338058718487]
  Graph Neural Networks (GNNs) have received extensive research attention for their promising performance in graph machine learning. Existing approaches, such as GCN and GPRGNN, are not robust in the face of homophily changes on test graphs. We propose EvenNet, a spectral GNN corresponding to an even-polynomial graph filter.
  arXiv  Detail & Related papers  (2022-05-27T10:48:14Z)
• Graph Convolutional Neural Networks Sensitivity under Probabilistic Error Model [24.215504503548864]
  This paper proposes an analysis framework to investigate the sensitivity of GCNNs to probabilistic graph perturbations. Our study establishes tight expected GSO error bounds, which are explicitly linked to the error model parameters, and reveals a linear relationship between GSO perturbations and the resulting output differences. Experiments validate our theoretical derivations and the effectiveness of our approach.
  arXiv  Detail & Related papers  (2022-03-15T12:40:10Z)
• Stability of Neural Networks on Manifolds to Relative Perturbations [118.84154142918214]
  Graph Neural Networks (GNNs) show impressive performance in many practical scenarios. GNNs can scale well on large size graphs, but this is contradicted by the fact that existing stability bounds grow with the number of nodes.
  arXiv  Detail & Related papers  (2021-10-10T04:37:19Z)
• Training Stable Graph Neural Networks Through Constrained Learning [116.03137405192356]
  Graph Neural Networks (GNNs) rely on graph convolutions to learn features from network data. GNNs are stable to different types of perturbations of the underlying graph, a property that they inherit from graph filters. We propose a novel constrained learning approach by imposing a constraint on the stability condition of the GNN within a perturbation of choice.
  arXiv  Detail & Related papers  (2021-10-07T15:54:42Z)
• Stochastic Graph Neural Networks [123.39024384275054]
  Graph neural networks (GNNs) model nonlinear representations in graph data with applications in distributed agent coordination, control, and planning. Current GNN architectures assume ideal scenarios and ignore link fluctuations that occur due to environment, human factors, or external attacks. In these situations, the GNN fails to address its distributed task if the topological randomness is not considered accordingly.
  arXiv  Detail & Related papers  (2020-06-04T08:00:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.