REVIEW 4 major objections 7 minor 29 references
Rewiring foreign keys degrades graph-based database predictions, especially for regression
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · glm-5.2
2026-07-09 20:15 UTC pith:UMVZRJHC
load-bearing objection New attack surface for relational deep learning, but the gradient signal story is muddier than the paper claims the 4 major comments →
Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central discovery is that the foreign-key structure of a relational database, once it becomes the input graph for a graph neural network, is an exploitable attack surface: an attacker who rewires as few as one to one hundred foreign-key references while preserving all integrity constraints can measurably degrade regression predictions, and first-order gradient signals are sufficient to identify which rewirings to make without exhaustive search. The paper also discovers an asymmetry in robustness: regression outputs are sensitive to these structural edits while classification outputs are largely stable, and spreading perturbations across more relations does not help—the most concentrated,
What carries the argument
The key mechanism is a differentiable edge mask applied to a frozen pretrained GNN. Existing foreign-key edges receive mask weight 1, admissible candidate edges (valid rewiring targets sampled under schema constraints) receive weight 0, and backpropagation through these masks yields per-edge gradient scores. Each candidate rewiring modifies both a forward FK-to-PK edge and its reverse, so the combined sensitivity score sums the forward and reverse gradients. Candidates are then ranked globally or shortlisted and re-evaluated with exact forward passes. Normalization variants (z-score, robust z-score, min-max) adjust for cross-relation gradient scale differences. The integrity constraints—each
Load-bearing premise
The claim that gradient-based attacks consistently degrade regression predictions rests on a single dataset (rel-f1, a Formula 1 database), a single GNN architecture (two-layer GraphSAGE), and a single mini-batch per experiment. Whether the gradient signal reliably identifies high-impact rewirings across different schemas, deeper architectures, or differently trained models is untested, and the headline 7% degradation figure comes from a separately reported better-fit model,
What would settle it
If gradient-based rewiring attacks fail to degrade regression performance on a second RDL benchmark with a different schema structure, or if the attack's effectiveness collapses for deeper GNN architectures (e.g., four or more layers) where gradient signals vanish, the central claim of consistent gradient-guided attack effectiveness would not generalize. A direct falsifier would be finding that random rewiring matches gradient-guided attacks on any regression task in a broader benchmark suite.
If this is right
- Databases powering RDL pipelines may need integrity-constraint-aware anomaly detection that flags suspicious foreign-key reassignments, not just value-level data validation.
- The regression-versus-classification robustness gap suggests that RDL deployment risk assessments should weight task type heavily: regression-based predictions (e.g., position forecasting, revenue prediction) may be more vulnerable than classification-based ones.
- The finding that concentrated attacks on few relations match or beat broadly distributed ones implies that a small subset of foreign-key relationships may carry disproportionate influence on model output, making them natural candidates for monitoring or access control.
- The non-additivity of structural perturbations means that auditing individual foreign-key changes in isolation may miss compound attack effects that only emerge when multiple rewirings are applied simultaneously.
Where Pith is reading between the lines
- If the gradient signal remains informative for deeper architectures, the attack could be more devastating against production-grade models with more layers, where message passing amplifies structural perturbations; conversely, vanishing gradients in deeper models could weaken the gradient-guided heuristic, creating an architecture-dependent arms race between model depth and attack effectiveness.
- The integrity-preserving constraint is itself a form of stealth: because the perturbed database remains fully consistent, standard referential integrity checks would pass without flag, meaning that detection must rely on distributional or semantic anomaly detection rather than constraint violation checking.
- Extending to feature attacks—modifying non-key tuple attributes such as timestamps or free-form text—would move the attack from combinatorial rewiring to semantic perturbation, potentially requiring different search heuristics (e.g., embedding-space optimization) and opening a much larger attack surface.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the adversarial robustness of Relational Deep Learning (RDL), in which a relational database is encoded as a heterogeneous entity graph and a GNN is trained for downstream prediction. The authors formalize a white-box threat model in which an attacker can only rewire foreign-key references in the upstream database while preserving integrity constraints (FK validity, degree-one FK constraint, functional dependencies). They propose seven attack heuristics—two random baselines and five gradient-guided variants using differentiable edge masks—and evaluate them on the RelBench rel-f1 benchmark. The main finding is that gradient-based attacks consistently outperform random baselines on regression tasks (MAE increases monotonically with budget), while classification tasks are more robust due to low label-flip rates. The paper also analyzes how normalization affects the diversity of perturbations across relations and target nodes.
Significance. The paper addresses a timely and well-motivated problem: as RDL becomes a standard methodology for learning on relational databases, understanding its adversarial robustness is important. The threat model is well-formulated—restricting the attacker to integrity-preserving rewirings of foreign keys is a realistic and non-trivial constraint that distinguishes this work from generic graph adversarial attacks. The formalization of mutable/immutable dependencies and coupled/local rewiring (§4.1) is a useful contribution. The FGSM derivation in Appendix A.1 is standard but correctly applied. Code and data are made available, which is commendable. The finding that raw gradient attacks concentrate on few relations yet remain effective, while normalization spreads perturbations without improving attack strength, is an interesting empirical observation.
major comments (4)
- §6.4, Table 4 (qualifying-position and driver-position): The Gradient + exact rerank method—which uses gradient scores to shortlist candidates, then evaluates their true loss impact via forward passes—performs barely above random on qualifying-position (0.9970 vs Random 0.9935 at B=100, a difference of 0.0035, well within the ±0.05 standard deviation) and substantially below Gradient raw on driver-position (3.1568 vs 3.1791 at B=100). If gradient sensitivity were a reliable predictor of discrete rewiring impact, exact re-evaluation of top gradient candidates should improve or at least match raw gradient selection. The authors should address this discrepancy directly: does it indicate that the first-order gradient signal is a poor predictor of true loss impact for individual edges, and that the raw gradient method's advantage stems primarily from relation concentration rather than per-rew
- §6.4, Table 4: The paper claims gradient-based attacks 'consistently outperform random baselines on regression tasks.' However, several normalized gradient variants overlap with the random baseline within standard deviations on qualifying-position (Gradient robust z-score: 1.0013±0.0529 vs Random 0.9935±0.0529 at B=100; Gradient min-max: 0.9995±0.0517). The word 'consistently' should be qualified, or the claim should be restricted to the raw gradient method specifically, with the normalized variants acknowledged as not reliably beating random.
- §6.3 (Mini-batch sampling) and §6.4: All attacks operate on a single fixed mini-batch sampled from rel-f1. The paper's central empirical claim rests on this single batch, single dataset, and single architecture (2-layer GraphSAGE). The authors acknowledge this in §8, but the limitation should be discussed more prominently in the experimental section, and the claim in the abstract ('consistently outperform') should be tempered accordingly. At minimum, results on a second dataset or a second batch would substantially strengthen the contribution.
- §6.4: The ~7% relative degradation figure is reported for a 'better-fitted model' (Figure 3) separately from the main Table 4, where the degradation is much smaller (~1.1% for driver-position). The authors note that 'some trained models are not perfectly fitted, which can dampen the apparent effect.' This suggests the attack's effectiveness is conditional on model quality. The paper should either report results on well-fitted models in the main table or explicitly state that the reported degradation is sensitive to model fit, as this affects the generality of the central claim.
minor comments (7)
- Table 1: The 'Min-Max' method is listed in Table 1 but referred to as 'Gradient min-max relation' in Table 4 and 'Gradient MinMax Relation' in Table 5. Consistent naming would help.
- §4.1: The distinction between 'coupled rewiring' and 'local rewiring' is conceptually clear, but the precise mechanism for coupled rewiring (how multiple FKs are modified jointly) is not formally specified. A brief example or formal definition would improve reproducibility.
- Table 3: The 'races.circuitId' row is marked 'Restricted' under mutability, but the exact restriction policy (how many rewirings are allowed, or whether it is fully excluded) is not defined in the text.
- §5.2: The statement 'existing edges receive weight 1, candidate edges receive an initial weight of 0' should clarify whether the mask is a sigmoid, hard-concrete, or other parameterization, as this affects gradient flow.
- Figure 2: The figure is dense and the text labels are small. Enlarging the sub-panels or simplifying the annotation would help readability.
- §6.4: The phrase 'some trained models are not perfectly fitted' is vague. Specifying which models and their clean-task performance metrics would strengthen the discussion.
- The abstract states 'five gradient-guided variants,' but Table 4 lists four gradient variants plus Gradient + exact rerank (which is a hybrid). The counting should be reconciled.
Circularity Check
No circularity found; derivation is self-contained with standard FGSM first-order expansion and externally published prior work.
full rationale
The paper's derivation chain is self-contained and does not reduce to its inputs by construction. The core theoretical result (Proposition 1 in Appendix A.1) is a standard first-order Taylor expansion of the attack objective under an ℓ∞ budget, yielding the FGSM sign-perturbation direction. The proof is elementary and complete within the paper—it does not depend on any external or self-cited uniqueness theorem. The candidate scoring formula (Section 5.3) uses gradient magnitudes to rank rewiring candidates, which is a heuristic application of the first-order signal, not a claim that the ranking is derived from the outcome it predicts. The attack heuristics build on Nettack [26] (Zügner et al., 2018), which is independently published by different authors. The RelBench framework [10, 11, 20] is also external. No parameter is fitted to a subset of data and then presented as a prediction of that same data. The experimental results, while narrow (single dataset, single architecture), are empirical observations rather than definitions disguised as derivations. The skeptic's concern that Gradient + exact rerank underperforms raw gradient is a correctness/empirical-validity issue, not a circularity issue—it does not indicate that any claimed result is equivalent to its input by construction.
Axiom & Free-Parameter Ledger
free parameters (6)
- Perturbation budget B =
1-100 (main), up to 500 (Fig 3)
- Shortlist size K =
100 (regression), 400 (classification)
- GNN hidden dimension =
128 (regression), 16 (classification)
- Number of training epochs =
10-18
- Mini-batch size =
512
- Neighbors per hop =
128
axioms (5)
- domain assumption The attacker has white-box access to the trained model parameters and the graph construction pipeline.
- standard math The GNN's prediction loss is differentiable with respect to differentiable edge masks over the adjacency matrices.
- domain assumption First-order (gradient) sensitivity of the loss to edge mask perturbations correlates with the true loss change from discrete rewiring.
- domain assumption The rel-f1 dataset and its schema constraints are representative of realistic relational databases for RDL.
- ad hoc to paper A 2-layer GraphSAGE architecture is sufficient to study adversarial robustness of RDL.
invented entities (2)
-
Attackable model with differentiable edge masks
independent evidence
-
Coupled rewiring operations
independent evidence
read the original abstract
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.
Figures
Reference graph
Works this paper leans on
-
[1]
Serge Abiteboul, Richard Hull, and Victor Vianu. 1995.Foundations of Databases. Addison-Wesley
work page 1995
-
[2]
Ngo, XuanLong Nguyen, Dan Olteanu, and Maximilian Schleich
Mahmoud Abo Khamis, Hung Q. Ngo, XuanLong Nguyen, Dan Olteanu, and Maximilian Schleich. 2018. In-Database Learning with Sparse Tensors. InPro- ceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS). ACM, 325–340
work page 2018
-
[3]
Battista Biggio, Blaine Nelson, and Pavel Laskov. 2012. Poisoning attacks against support vector machines.arXiv preprint arXiv:1206.6389(2012)
work page internal anchor Pith review Pith/arXiv arXiv 2012
-
[4]
Liwei Cai and William Yang Wang. 2018. Kbgan: Adversarial learning for knowl- edge graph embeddings. InProceedings of the 2018 conference of the North Amer- ican chapter of the association for computational linguistics: human language technologies, volume 1 (long papers). 1470–1480
work page 2018
-
[5]
Xinglong Chang, Gillian Dobbie, and Jörg Wicker. 2023. Fast adversarial label- flipping attack on tabular data.arXiv preprint arXiv:2310.10744(2023)
work page internal anchor Pith review Pith/arXiv arXiv 2023
-
[6]
Jinyin Chen, Yixian Chen, Haibin Zheng, Shijing Shen, Shanqing Yu, Dan Zhang, and Qi Xuan. 2020. MGA: Momentum gradient attack on network.IEEE Trans- actions on Computational Social Systems8, 1 (2020), 99–109
work page 2020
-
[7]
Jinyin Chen, Yangyang Wu, Xuanheng Xu, Yixian Chen, Haibin Zheng, and Qi Xuan. 2018. Fast gradient attack on network embedding.arXiv preprint arXiv:1809.02797(2018)
work page internal anchor Pith review Pith/arXiv arXiv 2018
-
[8]
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song
-
[9]
InInternational conference on machine learning
Adversarial attack on graph structured data. InInternational conference on machine learning. PMLR, 1115–1124
-
[10]
Vijay Prakash Dwivedi, Charilaos Kanatsoulis, Shenyang Huang, and Jure Leskovec. 2025. Relational deep learning: Challenges, foundations and next- generation architectures. InProceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2. 5999–6009
work page 2025
-
[11]
Matthias Fey, Weihua Hu, Kexin Huang, Jan Eric Lenssen, Rishabh Ranjan, Joshua Robinson, Rex Ying, Jiaxuan You, and Jure Leskovec. 2024. Position: Relational deep learning-graph representation learning on relational databases. InForty-first International Conference on Machine Learning
work page 2024
-
[12]
Justin Gu, Rishabh Ranjan, Charilaos Kanatsoulis, Haiming Tang, Martin Jurkovic, Valter Hudovernik, Mark Znidar, Pranshu Chaturvedi, Parth Shroff, Fengyu Li, et al. 2026. RelBench v2: A Large-Scale Benchmark and Repository for Relational Data. In3rd DATA-FM Workshop @ ICLR
work page 2026
-
[13]
Yuxing Guo, Jianqing Liang, Kaixuan Yao, Zhihao Guo, and Jiye Liang. 2026. Graph Adversarial Defense via Hilbert-Schmidt Independence Criterion against Influence Maximization Attacks. InProceedings of the ACM Web Conference 2026. 4565–4576
work page 2026
-
[14]
Weihua Hu, Yiwen Yuan, Zecheng Zhang, Akihiro Nitta, Kaidi Cao, Vid Kocijan, Jinu Sunil, Jure Leskovec, and Matthias Fey. 2024. Pytorch frame: A modular framework for multi-modal tabular learning.arXiv preprint arXiv:2404.00776 (2024)
work page internal anchor Pith review Pith/arXiv arXiv 2024
-
[15]
Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li. 2018. Manipulating machine learning: Poisoning attacks and counter- measures for regression learning.arXiv preprint arXiv:1804.00308(2018)
work page internal anchor Pith review Pith/arXiv arXiv 2018
-
[16]
Michael Kearns and Ming Li. 1988. Learning in the presence of malicious errors. InProceedings of the twentieth annual ACM symposium on Theory of computing. 267–280
work page 1988
-
[17]
Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. 2022. Adversarial attack on graph neural networks as an influence maximization problem. InProceedings of the fifteenth ACM international conference on web search and data mining. 675–685
work page 2022
-
[18]
Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. 2020. Towards more practical adversarial attacks on graph neural networks.Advances in neural information processing systems33 (2020), 4756–4766
work page 2020
-
[19]
Dan Olteanu and Maximilian Schleich. 2016. Factorized Databases.ACM SIGMOD Record45, 2 (2016)
work page 2016
-
[20]
Theodoros Rekatsinas, Xu Chu, Ihab F. Ilyas, and Christopher Ré. 2017. Holo- Clean: Holistic Data Repairs with Probabilistic Inference.Proceedings of the VLDB Endowment10, 11 (2017), 1190–1201
work page 2017
-
[21]
Joshua Robinson, Rishabh Ranjan, Weihua Hu, Kexin Huang, Jiaqi Han, Alejandro Dobles, Matthias Fey, Jan E Lenssen, Yiwen Yuan, Zecheng Zhang, et al. 2024. Relbench: A benchmark for deep learning on relational databases.Advances in Neural Information Processing Systems37 (2024), 21330–21341
work page 2024
-
[22]
Maximilian Schleich, Dan Olteanu, and Radu Ciucanu. 2016. Learning Linear Regression Models over Factorized Joins. InProceedings of the 2016 International Conference on Management of Data (SIGMOD). ACM, 3–18
work page 2016
-
[23]
Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. 2017. Certified defenses for data poisoning attacks.Advances in neural information processing systems30 (2017)
work page 2017
- [24]
-
[25]
Hengtong Zhang, Tianhang Zheng, Jing Gao, Chenglin Miao, Lu Su, Yaliang Li, and Kui Ren. 2019. Data poisoning attack against knowledge graph embedding. arXiv preprint arXiv:1904.12052(2019)
work page internal anchor Pith review Pith/arXiv arXiv 2019
-
[26]
Tianzhe Zhao, Jiaoyan Chen, Yanchi Ru, Qika Lin, Yuxia Geng, and Jun Liu. 2024. Untargeted adversarial attack on knowledge graph embeddings. InProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval. 1701–1711
work page 2024
-
[27]
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. 2018. Adversarial attacks on neural networks for graph data. InProceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining. 2847–2856
work page 2018
-
[28]
Daniel Zügner, Oliver Borchert, Amir Akbarnejad, and Stephan Günnemann
-
[29]
Hidden” is the channel dimension and “# Cand
Adversarial attacks on graph neural networks: Perturbations and their patterns.ACM Transactions on Knowledge Discovery from Data (TKDD)14, 5 (2020), 1–31. A APPENDIX A.1 First-Order (FGSM-type) Rewiring Direction The candidate scoring used in the white-box attack is motivated by the first-order direction that maximizes the linearized attack objective unde...
work page 2020
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.