mlsanityData to 7 Oct 2026

Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structure

arXiv 2404.15065 ↗First posted 23 Apr 2024cs.LG cs.AIcited by 8

Not on the map. Why?

Abstract (arXiv)

Graph neural networks are becoming increasingly popular in the field of machine learning due to their unique ability to process data structured in graphs. They have also been applied in safety-critical environments where perturbations inherently occur. However, these perturbations require us to formally verify neural networks before their deployment in safety-critical environments as neural networks are prone to adversarial attacks. While there exists research on the formal verification of neural networks, there is no work verifying the robustness of generic graph convolutional network architectures with uncertainty in the node features and in the graph structure over multiple message-passing steps. This work addresses this research gap by explicitly preserving the non-convex dependencies of all elements in the underlying computations through reachability analysis with (matrix) polynomial zonotopes. We demonstrate our approach on three popular benchmark datasets.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 28 of its 67 references that are in the map. First posted on arXiv 23 Apr 2024.

Builds on

28 of 67 references.

References · 28

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  3. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  4. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  5. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  6. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  7. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  8. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
  9. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  10. 2020Graph Structure Learning for Robust Graph Neural Networkscited by 368
  11. 2018Adversarial Attack on Graph Structured Datacited by 300
  12. 2016Safety Verification of Deep Neural Networkscited by 262
16 more
  1. 2019Branch and Bound for Piecewise Linear Neural Network Verificationcited by 138
  2. 2022Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boundcited by 92
  3. 2017Output Reachable Set Estimation and Verification for Multi-Layer Neural Networkscited by 79
  4. 2021PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximationscited by 77
  5. 2019Certifiable Robustness to Graph Perturbationscited by 62
  6. 2019Certifiable Robustness and Robust Training for Graph Convolutional Networkscited by 59
  7. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  8. 2021POLAR: A Polynomial Arithmetic Framework for Verifying Neural-Network Controlled Systemscited by 38
  9. 2023The Fourth International Verification of Neural Networks Competition (VNN-COMP 2023): Summary and Resultscited by 38
  10. 2020Certified Robustness of Community Detection against Adversarial Structural Perturbation via Randomized Smoothingcited by 29
  11. 2019JuliaReach: a Toolbox for Set-Based Reachabilitycited by 28
  12. 2022Open- and Closed-Loop Neural Network Verification using Polynomial Zonotopescited by 24
  13. 2022Scalable Verification of GNN-based Job Schedulerscited by 18
  14. 2019Sparse Polynomial Zonotopes: A Novel Set Representation for Reachability Analysiscited by 14
  15. 2022Fundamental Limits in Formal Verification of Message-Passing Neural Networkscited by 9
  16. 2020Debona: Decoupled Boundary Network Analysis for Tighter Bounds and Faster Adversarial Robustness Proofscited by 8

Built on by

Cited by year (2026 to 7 Oct)

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

8 papers.

  1. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4
  2. 2025Bridging Efficiency and Safety: Formal Verification of Neural Networks with Early Exitscited by 1
  3. 2025Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testingcited by 0
  4. 2026Perception with Guarantees: Certified Pose Estimation via Reachability Analysiscited by 0
  5. 2026Talking with Verifiers: Automatic Specification Generation for Neural Network Verificationcited by 0
  6. 2026Formally Verifying Analog Neural Networks Under Process Variations Using Polynomial Zonotopescited by 0
  7. 2026NNV3: Expanding Neural Network Verification to New Architectures and Domainscited by 0
  8. 2026Reachability-Based Formal Verification of Graph Neural Networks with Node and Edge Featurescited by 0