Exact Verification of Graph Neural Networks with Incremental Constraint Solving

• URL: http://arxiv.org/abs/2508.09320v1
• Date: Tue, 12 Aug 2025 20:10:31 GMT
• Title: Exact Verification of Graph Neural Networks with Incremental Constraint Solving
• Authors: Minghao Liu, Chia-Hsuan Lu, Marta Kwiatkowska,
• Abstract summary: Graph neural networks (GNNs) are increasingly employed in high-stakes applications, such as fraud detection or healthcare, but are susceptible to adversarial attacks.<n>We develop an exact (sound and complete) verification method for GNNs to compute guarantees against attribute and structural perturbations.<n>We implement GNNev, a versatile solver for message-passing neural networks, which supports three aggregation functions, sum, max and mean.
• Score: 17.378319742808856
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion [73.85920403511706]
  We propose ScaleGNN, a novel framework that adaptively fuses multi-hop node features for scalable and effective graph learning.<n>We show that ScaleGNN consistently outperforms state-of-the-art GNNs in both predictive accuracy and computational efficiency.
  arXiv  Detail & Related papers  (2025-04-22T14:05:11Z)
• Using Subgraph GNNs for Node Classification:an Overlooked Potential Approach [13.947915030994851]
  SubGND (Subgraph GNN for NoDe) is a new subgraph-based classification framework for node classification.<n>We show that SubGND achieves performance comparable to or surpassing global message-passing GNNs.
  arXiv  Detail & Related papers  (2025-03-09T13:37:38Z)
• Grimm: A Plug-and-Play Perturbation Rectifier for Graph Neural Networks Defending against Poisoning Attacks [53.972077392749185]
  Recent studies have revealed the vulnerability of graph neural networks (GNNs) to adversarial poisoning attacks on node classification tasks.<n>Here we introduce Grimm, the first plug-and-play defense model.
  arXiv  Detail & Related papers  (2024-12-11T17:17:02Z)
• Verifying message-passing neural networks via topology-based bounds tightening [3.3267518043390205]
  We develop a computationally effective approach towards providing robust certificates for message-passing neural networks (MPNNs) Because our work builds on mixed-integer optimization, it encodes a wide variety of subproblems. We test on both node and graph classification problems and consider topological attacks that both add and remove edges.
  arXiv  Detail & Related papers  (2024-02-21T17:05:27Z)
• Graph Agent Network: Empowering Nodes with Inference Capabilities for Adversarial Resilience [50.460555688927826]
  We propose the Graph Agent Network (GAgN) to address the vulnerabilities of graph neural networks (GNNs)<n>GAgN is a graph-structured agent network in which each node is designed as an 1-hop-view agent.<n>Agents' limited view prevents malicious messages from propagating globally in GAgN, thereby resisting global-optimization-based secondary attacks.
  arXiv  Detail & Related papers  (2023-06-12T07:27:31Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  We study the OOD generalization of neural algorithmic reasoning tasks. The goal is to learn an algorithm from input-output pairs using deep neural networks.
  arXiv  Detail & Related papers  (2022-11-01T18:33:20Z)
• Scalable Verification of GNN-based Job Schedulers [16.7289491091472]
  Graph Neural Networks (GNNs) have been applied for scheduling jobs over achieving better performance than hand-crafted clusters. We develop GNN-Verify, the first general framework for verifying both single-step and multi-step properties of these schedulers.
  arXiv  Detail & Related papers  (2022-03-07T06:13:04Z)
• Robust Graph Neural Networks via Probabilistic Lipschitz Constraints [7.359962178534361]
  Graph neural networks (GNNs) have recently been demonstrated to perform well on a variety of network-based tasks. GNNs are susceptible to shifts and perturbations on their inputs, which can include both node attributes and graph structure.
  arXiv  Detail & Related papers  (2021-12-14T17:33:32Z)
• Neural Network Branch-and-Bound for Neural Network Verification [26.609606492971967]
  We propose a novel machine learning framework that can be used for designing an effective branching strategy. We learn two graph neural networks (GNNs) that both directly treat the network we want to verify as a graph input. We show that our GNN models generalize well to harder properties on larger unseen networks.
  arXiv  Detail & Related papers  (2021-07-27T14:42:57Z)
• A Biased Graph Neural Network Sampler with Near-Optimal Regret [57.70126763759996]
  Graph neural networks (GNN) have emerged as a vehicle for applying deep network architectures to graph and relational data. In this paper, we build upon existing work and treat GNN neighbor sampling as a multi-armed bandit problem. We introduce a newly-designed reward function that introduces some degree of bias designed to reduce variance and avoid unstable, possibly-unbounded payouts.
  arXiv  Detail & Related papers  (2021-03-01T15:55:58Z)
• Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
  Neural networks can learn complex, non- adversarial functions, and it is challenging to guarantee their correct behavior in safety-critical contexts. Many approaches exist to find failures in networks (e.g., adversarial examples), but these cannot guarantee the absence of failures. We propose an approach that integrates the optimization process into the verification procedure, achieving better performance than the naive approach.
  arXiv  Detail & Related papers  (2020-10-07T08:19:48Z)
• Alleviating the Inconsistency Problem of Applying Graph Neural Network to Fraud Detection [78.88163190021798]
  We introduce a new GNN framework, $mathsfGraphConsis$, to tackle the inconsistency problem. Empirical analysis on four datasets indicates the inconsistency problem is crucial in a fraud detection task. We also released a GNN-based fraud detection toolbox with implementations of SOTA models.
  arXiv  Detail & Related papers  (2020-05-01T21:43:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.