Exact Verification of Graph Neural Networks with Incremental Constraint Solving
This work addresses the need for reliable verification in high-stakes applications such as fraud detection and healthcare, though it is incremental by extending support to more aggregation functions.
The paper tackles the problem of verifying adversarial robustness guarantees for graph neural networks (GNNs) against attribute and structural perturbations, developing an exact verification method that supports sum, max, and mean aggregation functions and demonstrates superior performance on benchmarks like Cora and CiteSeer.
Graph neural networks (GNNs) are increasingly 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 still 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. Focusing on node classification tasks, 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 solver 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 two standard benchmarks (Cora and CiteSeer) and two real-world fraud datasets (Amazon and Yelp) demonstrates its usability and effectiveness, as well as superior performance compared to existing {exact verification} tools on sum-aggregated node classification tasks.