mlsanityData to 14 Oct 2026

Exact Verification of Graph Neural Networks with Incremental Constraint Solving

arXiv 2508.09320 ↗First posted 12 Aug 2025cs.LG cs.AI cs.CRcited by 4

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) are increasingly often employed in high-stakes applications, such as fraud detection or healthcare, but are susceptible to adversarial attacks. A number of techniques have been proposed to provide adversarial robustness guarantees, but support for commonly used aggregation functions in message-passing GNNs is lacking. In this paper, we develop an exact (sound and complete) verification method for GNNs to compute guarantees against attribute and structural perturbations that involve edge addition or deletion, subject to budget constraints. Our method employs constraint solving with bound tightening, and iteratively solves a sequence of relaxed constraint satisfaction problems while relying on incremental solving capabilities of solvers to improve efficiency. We implement GNNev, a versatile exact verifier for message-passing neural networks, which supports three aggregation functions -- sum, max and mean -- with the latter two considered here for the first time. Extensive experimental evaluation of GNNev on real-world fraud datasets (Amazon and Yelp) and biochemical datasets (MUTAG and ENZYMES) demonstrates its usability and effectiveness, as well as superior performance on node classification and competitiveness on graph classification compared to existing exact verification tools on sum-aggregated GNNs.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 64 of its 91 references that are in the map. First posted on arXiv 12 Aug 2025.

Builds on

64 of 91 references.

References · 64

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Inductive Representation Learning on Large Graphscited by 6,320
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  6. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,340
  7. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  8. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  9. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 744
  10. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  11. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  12. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 445
38 more
  1. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 397
  2. 2018Adversarial Attack on Graph Structured Datacited by 301
  3. 2016Safety Verification of Deep Neural Networkscited by 263
  4. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  5. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 255
  6. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
  7. 2020GNNGuard: Defending Graph Neural Networks against Adversarial Attackscited by 195
  8. 2022Graph neural networks for materials science and chemistrycited by 182
  9. 2018Efficient Formal Safety Analysis of Neural Networkscited by 165
  10. 2020A Semi-supervised Graph Attentive Network for Financial Fraud Detectioncited by 151
  11. 2020Backdoor Attacks to Graph Neural Networkscited by 128
  12. 2019A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networkscited by 125
  13. 2013From Amateurs to Connoisseurs: Modeling the Evolution of User Expertise through Online Reviewscited by 108
  14. 2019Spatially-Aware Graph Neural Networks for Relational Behavior Forecasting from Sensor Datacited by 104
  15. 2021Robustness of Graph Neural Networks at Scalecited by 100
  16. 2019Graph Adversarial Training: Dynamically Regularizing Based on Graph Structurecited by 93
  17. 2021Graph Representation Learning in Biomedicinecited by 80
  18. 2020Robustness Verification for Transformerscited by 76
  19. 2020Verification of Deep Convolutional Neural Networks Using ImageStarscited by 75
  20. 2019A Restricted Black-box Adversarial Framework Towards Attacking Graph Embedding Modelscited by 68
  21. 2021TDGIA:Effective Injection Attacks on Graph Neural Networkscited by 67
  22. 2019Certifiable Robustness to Graph Perturbationscited by 62
  23. 2019Certifiable Robustness and Robust Training for Graph Convolutional Networkscited by 59
  24. 2020Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbationcited by 57
  25. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  26. 2019Understanding the Representation Power of Graph Neural Networks in Learning Graph Topologycited by 52
  27. 2018CNN-Cert: An Efficient Framework for Certifying Robustness of Convolutional Neural Networkscited by 50
  28. 2019Neural Network Branching for Neural Network Verificationcited by 45
  29. 2021Single Node Injection Attack against Graph Neural Networkscited by 45
  30. 2020Adversarial Attack on Large Scale Graphcited by 39
  31. 2019POPQORN: Quantifying Robustness of Recurrent Neural Networkscited by 37
  32. 2023Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directionscited by 28
  33. 2019Adversarial Training Methods for Network Embeddingcited by 26
  34. 2021A Hard Label Black-box Adversarial Attack Against Graph Neural Networkscited by 26
  35. 2023Some Might Say All You Need Is Sumcited by 21
  36. 2024Decidability of Graph Neural Networks via Logical Characterizationscited by 14
  37. 2020DiffRNN: Differential Verification of Recurrent Neural Networkscited by 12
  38. 2022Spectral Adversarial Training for Robust Graph Neural Networkcited by 12

50 most cited of 64 All 64 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2025Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testingcited by 0
  2. 2026Exploring Solver-Level Warmstarting for Neural Network Verificationcited by 0
  3. 2026NNV3: Expanding Neural Network Verification to New Architectures and Domainscited by 0
  4. 2026Reachability-Based Formal Verification of Graph Neural Networks with Node and Edge Featurescited by 0