mlsanityData to 14 Oct 2026

Reachability-Based Formal Verification of Graph Neural Networks with Node and Edge Features

arXiv 2609.30079 ↗First posted 24 Sep 2026cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) have become a prominent approach for developing fast, topology-aware surrogates in electric power systems, supporting tasks such as power flow (PF) analysis, optimal power flow (OPF) estimation, and cascading failure analysis (CFA). Despite this growing use, formally verifying GNN-based models remains challenging, with existing methods limited in scope. We extend the neural network verification (NNV) framework to graph-structured inputs through GraphStar sets, a generalization of Star sets that captures uncertainty over both node and edge features. This extension enables the propagation of linear message-passing operations and the sound approximation of ReLU nonlinearities for GNN architectures, including graph convolutional network (GCN) and graph isomorphism network with edge features (GINE) layers. We evaluate GNNV across three power system tasks, PF, OPF, and CFA, on the IEEE-24, IEEE-39, and IEEE-118 test cases, as well as two standard graph classification benchmarks, ENZYMES and PROTEINS. Our results show that GNNV provides tighter robustness guarantees than CORA on graph classification models with ReLU-based activations and, for the first time, delivers edge-aware robustness guarantees for GINE-based PF and OPF models under joint node and edge perturbations.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 23 of its 43 references that are in the map. First posted on arXiv 24 Sep 2026.

Builds on

23 of 43 references.

References · 23

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  6. 2019Strategies for Pre-training Graph Neural Networkscited by 971
  7. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  8. 2020NNV: The Neural Network Verification Tool for Deep Neural Networks and Learning-Enabled Cyber-Physical Systemscited by 128
  9. 2020Transfer Learning of Graph Neural Networks with Ego-graph Information Maximizationcited by 93
  10. 2020Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbationcited by 57
  11. 2024The Fifth International Verification of Neural Networks Competition (VNN-COMP 2024): Summary and Resultscited by 43
  12. 2022The Third International Verification of Neural Networks Competition (VNN-COMP 2022): Summary and Resultscited by 39
11 more
  1. 2023The Fourth International Verification of Neural Networks Competition (VNN-COMP 2023): Summary and Resultscited by 38
  2. 2022Scalable Verification of GNN-based Job Schedulerscited by 19
  3. 2024PowerGraph: A power grid benchmark dataset for graph neural networkscited by 19
  4. 2022Neural Network Verification using Residual Reasoningcited by 18
  5. 2020Adversarial Immunization for Certifiable Robustness on Graphscited by 14
  6. 2022Reachability Analysis of a General Class of Neural Ordinary Differential Equationscited by 13
  7. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  8. 2022Fundamental Limits in Formal Verification of Message-Passing Neural Networkscited by 9
  9. 2024Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structurecited by 8
  10. 2022Spatial-Temporal Recurrent Graph Neural Networks for Fault Diagnostics in Power Distribution Systemscited by 7
  11. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4

Built on by

Not cited yet.