Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints

2026-07-09 · Source: cs.LG updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Cybersecurity & Data Privacy, Data Science & Analytics · Depth: Expert, extended

Summary

This research investigates structural adversarial attacks on Relational Deep Learning (RDL) pipelines, where databases are modeled as heterogeneous temporal graphs for GNN-based prediction. The study defines a white-box threat model where an attacker rewires foreign-key references in the upstream database, strictly adhering to integrity constraints and a global perturbation budget of 1 to 100 edges. Seven attack heuristics were explored, including two random baselines and five gradient-guided variants utilizing differentiable edge masks. Evaluated on the RelBench rel-f1 benchmark, gradient-based attacks consistently degraded regression task performance, increasing Mean Absolute Error (MAE) by up to 7% and outperforming random methods. Classification tasks showed smaller accuracy reductions (e.g., 77.37% to 75.51%), attributed to lower label-flip rates. Gradient-only attacks offered the best cost-effectiveness, running in 45.8-54.1 seconds compared to 0.1 seconds for random and 87.2-91.8 seconds for exact re-evaluation methods. All attacks exhibited high target diversity, spreading perturbations across hundreds of distinct nodes.

Key takeaway

For AI Security Engineers evaluating the robustness of Relational Deep Learning systems, you should prioritize testing structural adversarial attacks, especially on models performing regression tasks. Implement gradient-guided foreign-key rewiring attacks, as they prove significantly more effective than random perturbations and offer a strong cost-performance trade-off compared to exact re-evaluation methods. Be aware that classification models may exhibit higher inherent stability, requiring different attack strategies or defense mechanisms.

Key insights

Relational Deep Learning models are vulnerable to integrity-preserving structural attacks, particularly for regression tasks.

Principles

• Gradient-based methods effectively navigate combinatorial attack spaces.
• Classification models exhibit greater local stability against sparse structural perturbations.
• Attack effectiveness doesn't always correlate with perturbation diversity across relations.

Method

An attack method involves defining an "attackable" GNN model with differentiable edge weights, augmenting the graph with candidate edges, and using first-order gradient signals to score and rank integrity-preserving foreign-key rewirings under a budget.

In practice

• Implement gradient-guided FK rewiring to test RDL model robustness.
• Prioritize regression task models for adversarial robustness testing.
• Consider raw gradient attacks for efficiency and competitive performance.

Topics

• Relational Deep Learning
• Adversarial Attacks
• Graph Neural Networks
• Database Integrity
• Foreign-Key Rewiring
• RelBench

Code references

• alanganyDB/Structural-Adversarial-Attacks-on-Relational-Deep-Learning-under-Integrity-Constraints

Best for: Research Scientist, AI Scientist, AI Security Engineer, Machine Learning Engineer

Related on AIssential

• Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints — Relational Deep Learning models are susceptible to structural adversarial attacks that manipulate foreign-key references while maintaining database integrity.
• GJDNet: Robust Graph Neural Networks via Joint Disentangled Learning Against Adversarial Attacks — GJDNet enhances GNN robustness by jointly disentangling node representations and decision spaces against adversarial attacks.
• Beyond Homophily: Towards Generalized Graph Reconstruction Attack and Defense — GNNs are vulnerable to graph reconstruction attacks, but a Markov chain approximation can inform both stronger attacks and effective defenses.
• No More Guessing: a Verifiable Gradient Inversion Attack in Federated Learning — VGIA offers verifiable gradient inversion for tabular data, ensuring exact record reconstruction with certified correctness.
• Foundation Models for Structured Data — Applying transformer-style attention to databases viewed as graphs enables foundation models for structured data, overcoming manual feature engineering.
• Adversarial Rademacher Complexity of Deep Neural Networks — This paper establishes the first theoretical bound for Adversarial Rademacher Complexity in deep neural networks, linking robust generalization to weight norm.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.LG updates on arXiv.org.