Pith. sign in

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 →

arxiv 2607.07089 v1 pith:UMVZRJHC submitted 2026-07-08 cs.LG cs.DB

Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints

classification cs.LG cs.DB
keywords adversarial attacksrelational deep learninggraph neural networksforeign-key rewiringintegrity constraintsstructural perturbationswhite-box attacksgraph robustness
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Relational Deep Learning (RDL) is a pipeline that turns a multi-table relational database into a heterogeneous graph—each row becomes a node and each foreign-key relationship becomes a typed edge—and then trains a graph neural network on that graph for prediction tasks. This paper asks whether an attacker who can modify the database but must keep it consistent (every foreign key still points to a valid primary key, every tuple keeps exactly one parent, functional dependencies still hold) can degrade the model's predictions by rewiring a small number of foreign-key references. Because the graph topology is entirely induced by the database schema, any such rewiring simultaneously changes the graph structure, but the space of valid rewirings is combinatorial and the effect of multiple edits is non-additive because message passing in the GNN couples them. The paper proposes gradient-guided heuristics: a differentiable edge mask is added to the frozen pretrained model, gradients of the loss with respect to these masks are computed, and candidate rewirings are ranked by their combined forward-and-reverse gradient sensitivity, optionally with per-relation normalization. On the rel-f1 Formula 1 benchmark, gradient-based attacks consistently increase mean absolute error on regression tasks as the perturbation budget grows (up to roughly 7% relative degradation on a well-fit model), while random rewiring leaves error essentially flat. Classification tasks prove more robust: even the strongest attacks reduce accuracy by only a couple of points, which the authors attribute to low label-flip rates and the local stability of decision boundaries under sparse perturbations. A key secondary finding is that per-relation normalization spreads the attack budget across more relations but does not improve attack strength—the concentrated raw-gradient attack, which touches only one or two relations, remains competitive.

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.

Watch this falsifier — get emailed when new claim-graph text bears on it.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 7 minor

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)
  1. §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
  2. §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.
  3. §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.
  4. §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)
  1. 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.
  2. §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.
  3. 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.
  4. §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.
  5. Figure 2: The figure is dense and the text labels are small. Enlarging the sub-panels or simplifying the annotation would help readability.
  6. §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.
  7. 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

0 steps flagged

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

6 free parameters · 5 axioms · 2 invented entities

The paper relies on standard mathematical machinery (FGSM, differentiable masks) and domain-specific assumptions about the threat model and dataset representativeness. No new physical entities or unverified mathematical axioms are introduced. The main risk is the heuristic assumption that gradient sensitivity predicts discrete rewiring impact, which is empirically supported but not guaranteed.

free parameters (6)
  • Perturbation budget B = 1-100 (main), up to 500 (Fig 3)
    The number of allowed rewiring operations; swept as an independent variable, not fitted.
  • Shortlist size K = 100 (regression), 400 (classification)
    Number of gradient candidates per source node kept before exact re-evaluation; chosen by hand (Table 7).
  • GNN hidden dimension = 128 (regression), 16 (classification)
    Channel dimension, chosen for model fit (Table 7, §A.2).
  • Number of training epochs = 10-18
    Selected per task to avoid overfitting (Table 7).
  • Mini-batch size = 512
    Fixed sampling parameter (§6.3).
  • Neighbors per hop = 128
    Temporal neighborhood sampling parameter (§6.3).
axioms (5)
  • domain assumption The attacker has white-box access to the trained model parameters and the graph construction pipeline.
    Stated in §1 and §5.1; the attacker can reproduce the graph and model. This is a standard but strong threat model assumption.
  • standard math The GNN's prediction loss is differentiable with respect to differentiable edge masks over the adjacency matrices.
    Used in §5.2 to define the attackable model; standard for GNNs with continuous edge weights.
  • domain assumption First-order (gradient) sensitivity of the loss to edge mask perturbations correlates with the true loss change from discrete rewiring.
    This is the core heuristic assumption (§5.3). The paper provides empirical evidence (Table 4) but no theoretical guarantee; the non-additivity discussion (§5.3) acknowledges it can fail.
  • domain assumption The rel-f1 dataset and its schema constraints are representative of realistic relational databases for RDL.
    Stated in §6.2; the dataset has coupled FKs and hierarchical dependencies. Generalization to other schemas is untested (§8).
  • ad hoc to paper A 2-layer GraphSAGE architecture is sufficient to study adversarial robustness of RDL.
    Chosen to limit vanishing gradients and oversmoothing (§6.3). Deeper architectures might behave differently under attack.
invented entities (2)
  • Attackable model with differentiable edge masks independent evidence
    purpose: Enables gradient flow through graph structure for candidate scoring
    This is a standard technique from [26]; the paper provides code and the construction is reproducible. Not a new physical entity but a methodological construct.
  • Coupled rewiring operations independent evidence
    purpose: Groups of FKs that must be perturbed simultaneously to preserve integrity
    Defined by the schema structure of rel-f1 (Table 3); the coupling is a property of the dataset, not invented by the paper.

pith-pipeline@v1.1.0-glm · 19683 in / 3333 out tokens · 255493 ms · 2026-07-09T20:15:48.542801+00:00 · methodology

0 comments
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

Figures reproduced from arXiv: 2607.07089 by Alan Gany, Bogdan Cautis, Silviu Maniu.

Figure 1
Figure 1. Figure 1: Overview of the attack setting. A relational database [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Gradient-guided constrained rewiring of a relational entity graph. For each relation [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Attacked MAE on the qualifying-position task of the rel-f1 dataset as a function of the attack budget (1–500 edge perturbations). Higher values correspond to stronger attacks. Results are reported for random seed 41. (7) Gradient + Min-Max. Candidates are normalized indepen￾dently within each relation using min–max scaling, map￾ping the lowest gradient score to 0 and the highest to 1. The objective is to r… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · 6 internal anchors

  1. [1]

    1995.Foundations of Databases

    Serge Abiteboul, Richard Hull, and Victor Vianu. 1995.Foundations of Databases. Addison-Wesley

  2. [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

  3. [3]

    Battista Biggio, Blaine Nelson, and Pavel Laskov. 2012. Poisoning attacks against support vector machines.arXiv preprint arXiv:1206.6389(2012)

  4. [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

  5. [5]

    Xinglong Chang, Gillian Dobbie, and Jörg Wicker. 2023. Fast adversarial label- flipping attack on tabular data.arXiv preprint arXiv:2310.10744(2023)

  6. [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

  7. [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)

  8. [8]

    Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song

  9. [9]

    InInternational conference on machine learning

    Adversarial attack on graph structured data. InInternational conference on machine learning. PMLR, 1115–1124

  10. [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

  11. [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

  12. [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

  13. [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

  14. [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)

  15. [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)

  16. [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

  17. [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

  18. [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

  19. [19]

    Dan Olteanu and Maximilian Schleich. 2016. Factorized Databases.ACM SIGMOD Record45, 2 (2016)

  20. [20]

    Ilyas, and Christopher Ré

    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

  21. [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

  22. [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

  23. [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)

  24. [24]

    Behrad Tajalli, Stefanos Koffas, and Stjepan Picek. 2025. CatBack: Universal Backdoor Attacks on Tabular Data via Categorical Encoding.arXiv preprint arXiv:2511.06072(2025)

  25. [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)

  26. [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

  27. [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

  28. [28]

    Daniel Zügner, Oliver Borchert, Amir Akbarnejad, and Stephan Günnemann

  29. [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...