mlsanityData to 7 Oct 2026

Verifying message-passing neural networks via topology-based bounds tightening

arXiv 2402.13937 ↗First posted 21 Feb 2024math.OC cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

Since graph neural networks (GNNs) are often vulnerable to attack, we need to know when we can trust them. We develop a computationally effective approach towards providing robust certificates for message-passing neural networks (MPNNs) using a Rectified Linear Unit (ReLU) activation function. Because our work builds on mixed-integer optimization, it encodes a wide variety of subproblems, for example it admits (i) both adding and removing edges, (ii) both global and local budgets, and (iii) both topological perturbations and feature modifications. Our key technology, topology-based bounds tightening, uses graph structure to tighten bounds. We also experiment with aggressive bounds tightening to dynamically change the optimization constraints by tightening variable bounds. To demonstrate the effectiveness of these strategies, we implement an extension to the open-source branch-and-cut solver SCIP. We test on both node and graph classification problems and consider topological attacks that both add and remove edges.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 36 of its 54 references that are in the map. First posted on arXiv 21 Feb 2024.

Builds on

36 of 54 references.

References · 36

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  4. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  5. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  6. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  7. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  8. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
  9. 2018Adversarial Attack on Graph Structured Datacited by 300
  10. 2019Adversarial Attacks on Graph Neural Networks via Meta Learningcited by 261
  11. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  12. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
24 more
  1. 2017An approach to reachability analysis for feed-forward ReLU neural networkscited by 126
  2. 2018Strong mixed-integer programming formulations for trained neural networkscited by 115
  3. 2021Robustness of Graph Neural Networks at Scalecited by 100
  4. 2021PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximationscited by 77
  5. 2020Towards More Practical Adversarial Attacks on Graph Neural Networkscited by 76
  6. 2019Certifiable Robustness to Graph Perturbationscited by 62
  7. 2019Certifiable Robustness and Robust Training for Graph Convolutional Networkscited by 59
  8. 2020Certified Robustness of Graph Neural Networks against Adversarial Structural Perturbationcited by 57
  9. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56
  10. 2020Scalable Attack on Graph Data by Injecting Vicious Nodescited by 50
  11. 2020The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verificationcited by 50
  12. 2021Partition-based formulations for mixed-integer optimization of trained ReLU neural networkscited by 39
  13. 2022OMLT: Optimization & Machine Learning Toolkitcited by 34
  14. 2020PANE: scalable and effective attributed network embeddingcited by 23
  15. 2022Scalable Verification of GNN-based Job Schedulerscited by 18
  16. 2020Indirect Adversarial Attacks via Poisoning Neighbors for Graph Convolutional Networkscited by 16
  17. 2023Enabling Research through the SCIP Optimization Suite 8.0cited by 13
  18. 2022Fundamental Limits in Formal Verification of Message-Passing Neural Networkscited by 9
  19. 2023Mixed-Integer Optimisation of Graph Neural Networks for Computer-Aided Molecular Designcited by 9
  20. 2023PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programscited by 8
  21. 2023Augmenting optimization-based molecular design with graph neural networkscited by 6
  22. 2023Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networkscited by 6
  23. 2024Bound Tightening using Rolling-Horizon Decomposition for Neural Network Verificationcited by 6
  24. 2023Optimizing over trained GNNs via symmetry breakingcited by 5

Built on by

Cited by year (2026 to 7 Oct)

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

10 papers.

  1. 2024Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attackscited by 5
  2. 2024Exact Certification of (Graph) Neural Networks Against Label Poisoningcited by 5
  3. 2025Exact Verification of Graph Neural Networks with Incremental Constraint Solvingcited by 4
  4. 2025Global optimization of graph acquisition functions for neural architecture searchcited by 2
  5. 2025Bridging Efficiency and Safety: Formal Verification of Neural Networks with Early Exitscited by 1
  6. 2024Certifying Robustness of Graph Convolutional Networks for Node Perturbation with Polyhedra Abstract Interpretationcited by 0
  7. 2025Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogatecited by 0
  8. 2025Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testingcited by 0
  9. 2026NNV3: Expanding Neural Network Verification to New Architectures and Domainscited by 0
  10. 2026Reachability-Based Formal Verification of Graph Neural Networks with Node and Edge Featurescited by 0