Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing

• URL: http://arxiv.org/abs/2510.18591v1
• Date: Tue, 21 Oct 2025 12:45:51 GMT
• Title: Robustness Verification of Graph Neural Networks Via Lightweight Satisfiability Testing
• Authors: Chia-Hsuan Lu, Tony Tan, Michael Benedikt,
• Abstract summary: Graph neural networks (GNNs) are the predominant architecture for learning over graphs.<n>In this paper we evaluate our tool RobLight on a diverse set of GNN variants and datasets.
• Score: 1.9754011041953694
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks (GNNs) are the predominant architecture for learning over graphs. As with any machine learning model, and important issue is the detection of adversarial attacks, where an adversary can change the output with a small perturbation of the input. Techniques for solving the adversarial robustness problem - determining whether such an attack exists - were originally developed for image classification, but there are variants for many other machine learning architectures. In the case of graph learning, the attack model usually considers changes to the graph structure in addition to or instead of the numerical features of the input, and the state of the art techniques in the area proceed via reduction to constraint solving, working on top of powerful solvers, e.g. for mixed integer programming. We show that it is possible to improve on the state of the art in structural robustness by replacing the use of powerful solvers by calls to efficient partial solvers, which run in polynomial time but may be incomplete. We evaluate our tool RobLight on a diverse set of GNN variants and datasets.

Related papers

• Explainable Attention-Guided Stacked Graph Neural Networks for Malware Detection [2.6436521007616114]
  We propose a novel stacking ensemble framework for graph-based malware detection and explanation.<n>Our framework improves classification performance while providing insightful interpretations of malware behavior.
  arXiv  Detail & Related papers  (2025-08-13T13:33:02Z)
• NN-Former: Rethinking Graph Structure in Neural Architecture Representation [67.3378579108611]
  Graph Neural Networks (GNNs) and transformers have shown promising performance in representing neural architectures.<n>We show that sibling nodes are pivotal while overlooked in previous research.<n>Our approach consistently achieves promising performance in both accuracy and latency prediction.
  arXiv  Detail & Related papers  (2025-07-01T15:46:18Z)
• Unified Graph Networks (UGN): A Deep Neural Framework for Solving Graph Problems [0.5699788926464752]
  We propose a novel framework named emphUnified emphGraph emphNetwork (UGN) to solve graph problems.<n>UGN is based on graph convolutional neural networks (GCN) and 2-dimensional convolutional neural networks (Conv2D)
  arXiv  Detail & Related papers  (2025-02-11T12:03:18Z)
• GIF: A General Graph Unlearning Strategy via Influence Function [63.52038638220563]
  Graph Influence Function (GIF) is a model-agnostic unlearning method that can efficiently and accurately estimate parameter changes in response to a $epsilon$-mass perturbation in deleted data. We conduct extensive experiments on four representative GNN models and three benchmark datasets to justify GIF's superiority in terms of unlearning efficacy, model utility, and unlearning efficiency.
  arXiv  Detail & Related papers  (2023-04-06T03:02:54Z)
• Reliable Representations Make A Stronger Defender: Unsupervised Structure Refinement for Robust GNN [36.045702771828736]
  Graph Neural Networks (GNNs) have been successful on flourish tasks over graph data. Recent studies have shown that attackers can catastrophically degrade the performance of GNNs by maliciously modifying the graph structure. We propose an unsupervised pipeline, named STABLE, to optimize the graph structure.
  arXiv  Detail & Related papers  (2022-06-30T10:02:32Z)
• Neural combinatorial optimization beyond the TSP: Existing architectures under-represent graph structure [9.673093148930876]
  We analyze how and whether recent neural architectures can be applied to graph problems of practical importance. We show that augmenting the structural representation of problems with Distance is a promising step towards the still-ambitious goal of learning multi-purpose autonomous solvers.
  arXiv  Detail & Related papers  (2022-01-03T14:14:28Z)
• Software Vulnerability Detection via Deep Learning over Disaggregated Code Graph Representation [57.92972327649165]
  This work explores a deep learning approach to automatically learn the insecure patterns from code corpora. Because code naturally admits graph structures with parsing, we develop a novel graph neural network (GNN) to exploit both the semantic context and structural regularity of a program.
  arXiv  Detail & Related papers  (2021-09-07T21:24:36Z)
• GraphMI: Extracting Private Graph Data from Graph Neural Networks [59.05178231559796]
  We present textbfGraph textbfModel textbfInversion attack (GraphMI), which aims to extract private graph data of the training graph by inverting GNN. Specifically, we propose a projected gradient module to tackle the discreteness of graph edges while preserving the sparsity and smoothness of graph features. We design a graph auto-encoder module to efficiently exploit graph topology, node attributes, and target model parameters for edge inference.
  arXiv  Detail & Related papers  (2021-06-05T07:07:52Z)
• An Introduction to Robust Graph Convolutional Networks [71.68610791161355]
  We propose a novel Robust Graph Convolutional Neural Networks for possible erroneous single-view or multi-view data. By incorporating an extra layers via Autoencoders into traditional graph convolutional networks, we characterize and handle typical error models explicitly.
  arXiv  Detail & Related papers  (2021-03-27T04:47:59Z)
• Graphs for deep learning representations [1.0152838128195467]
  We introduce a graph formalism based on the recent advances in Graph Signal Processing (GSP) Namely, we use graphs to represent the latent spaces of deep neural networks. We showcase that this graph formalism allows us to answer various questions including: ensuring robustness, reducing the amount of arbitrary choices in the design of the learning process, improving to small generalizations added to the inputs, and reducing computational complexity.
  arXiv  Detail & Related papers  (2020-12-14T11:51:23Z)
• Information Obfuscation of Graph Neural Networks [96.8421624921384]
  We study the problem of protecting sensitive attributes by information obfuscation when learning with graph structured data. We propose a framework to locally filter out pre-determined sensitive attributes via adversarial training with the total variation and the Wasserstein distance.
  arXiv  Detail & Related papers  (2020-09-28T17:55:04Z)

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.