Exact Verification of Graph Neural Networks with Incremental Constraint Solving
Authors:
- Minghao LiuMLMinghao Liu
- Chia-Hsuan LuCLChia-Hsuan Lu
- Marta KwiatkowskaMKMarta Kwiatkowska
Open Access
- 18 May 2026
- book chapter
- Published by Springer Nature
- p. 641-662
Abstract
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.Keywords
All Related Versions
This publication has 45 references indexed in Scilit:
- Graph Convolutional Network Robustness Verification Algorithm Based on Dual Approximation2024
- Financial fraud detection using graph neural networks: A systematic reviewExpert Systems with Applications, 2023
- Graph neural networks for materials science and chemistryCommunications Materials, 2022
- Graph representation learning in biomedicine and healthcareNature Biomedical Engineering, 2022
- Prediction of protein–protein interaction using graph neural networksScientific Reports, 2022
- DiffRNN: Differential Verification of Recurrent Neural Networks2021
- Verification of Deep Convolutional Neural Networks Using ImageStars2020
- Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks2017
- Safety Verification of Deep Neural Networks2017
- Verifying Integer Programming Results2017