# Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints

arXiv: https://arxiv.org/abs/2607.07089 · HTML: https://mlsanity.com/paper/2607.07089/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 22 references that are in the map.
- First posted on arXiv 8 Jul 2026.

## Builds on (most cited first, 13 of 13)

- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Adversarial Attack on Graph Structured Data](https://mlsanity.com/paper/1806.02371/) (2018)
- [Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning](https://mlsanity.com/paper/1804.00308/) (2018)
- [HoloClean: Holistic Data Repairs with Probabilistic Inference](https://mlsanity.com/paper/1702.00820/) (2017)
- [Towards More Practical Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2006.05057/) (2020)
- [Fast Gradient Attack on Network Embedding](https://mlsanity.com/paper/1809.02797/) (2018)
- [KBGAN: Adversarial Learning for Knowledge Graph Embeddings](https://mlsanity.com/paper/1711.04071/) (2017)
- [Data Poisoning Attack against Knowledge Graph Embedding](https://mlsanity.com/paper/1904.12052/) (2019)
- [PyTorch Frame: A Modular Framework for Multi-Modal Tabular Learning](https://mlsanity.com/paper/2404.00776/) (2024)
- [Relational Deep Learning: Challenges, Foundations and Next-Generation Architectures](https://mlsanity.com/paper/2506.16654/) (2025)
- [Adversarial Attack on Graph Neural Networks as An Influence Maximization Problem](https://mlsanity.com/paper/2106.10785/) (2021)
- [MGA: Momentum Gradient Attack on Network](https://mlsanity.com/paper/2002.11320/) (2020)
- [Fast Adversarial Label-Flipping Attack on Tabular Data](https://mlsanity.com/paper/2310.10744/) (2023)

## Abstract (arXiv)

Relational Deep Learning (RDL) has become a standard methodology for machine learning on relational databases: the database is encoded as a heterogeneous temporal graph in which tuples become nodes and primary-key to foreign-key (PK-FK) dependencies become typed edges, over which a graph neural network is trained for downstream prediction. We study the adversarial robustness of this pipeline. We consider a white-box attacker who knows how the graph is built and the model is trained, reasons about perturbations on the graph, but can only act on the upstream database, by rewiring foreign-key references while preserving the integrity constraints of the schema (foreign-key validity, the degree-one FK constraint, and functional dependencies). This restricts the attacker to a constrained, combinatorial set of admissible edits under a global perturbation budget, which is intractable to explore exhaustively and made non-additive by GNN message passing. We investigate seven attack heuristics - two random sampling baselines and five gradient-guided variants that exploit differentiable edge masks - and evaluate them on the RelBench rel-f1 benchmark. Gradient-based attacks consistently outperform random baselines on regression tasks, whereas gains on classification are smaller, which we attribute to low label-flip rates and greater local stability of classification outputs.