Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints Alan Gany
Bogdan Cautis
Silviu Maniu
Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG Grenoble, France [email protected]
Singapore Institute of Technology Singapore [email protected]
Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG Grenoble, France [email protected]
arXiv:2607.07089v1 [cs.LG] 8 Jul 2026
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. VLDB Workshop Reference Format: Alan Gany, Bogdan Cautis, and Silviu Maniu. Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints. VLDB 2026 Workshop: Applied AI for Database Systems and Applications (AIDB).
VLDB Workshop Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/alanganyDB/Structural-Adversarial-Attacks-on-RelationalDeep-Learning-under-Integrity-Constraints.git.
1
INTRODUCTION
Deep neural networks achieve strong predictive performance across many domains, yet they remain fragile: small, carefully crafted perturbations of their inputs can drastically alter their predictions, exposing these systems to malicious manipulation. Adversarial attacks, and in particular gradient-based ones, have been demonstrated on a wide range of data structures, including images, tabular data, graphs, and knowledge graphs. Attacks on dense inputs such as images are comparatively easy to formulate, whereas attacks on This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license.
sparse, discrete structures are substantially harder because of their combinatorial nature; gradient-based methods nonetheless remain effective in these settings. Relational databases store large volumes of structured, highvalue information, which makes them attractive targets. They have, however, remained largely outside the scope of adversarial machine learning, simply because few learning methods operated directly on relational data. Relational Deep Learning (RDL) changes this picture [10, 11, 20]. RDL encodes a multi-table database as a heterogeneous temporal graph in which each tuple becomes a node and each primary-key to foreign-key (PK–FK) dependency becomes a typed edge, and it trains a graph neural network end-to-end for a downstream prediction task. By turning the database itself into the model’s input, RDL also turns it into an attack surface. We study the adversarial robustness of this pipeline under a white-box threat model. The attacker knows how the graph is constructed from the schema and how the model is trained, and can therefore reproduce both, and reason about perturbations directly on the graph. The attacker cannot, however, edit the graph itself: the graph is a derived artifact, and the only actionable surface is the upstream database. Every perturbation must therefore be expressed as an edit to the database that leaves it consistent, i.e., that does not violate the integrity constraints of the schema. An illustration of this setting is provided in Figure 1. Within this setting, two attack directions can be distinguished: • Feature attacks, which target the heterogeneous feature representations derived from the database and assembled as tensor frames. Designing perturbations in this feature space is difficult due to the heterogeneous nature of relational attributes. • Structural attacks, which target the relational entity graph itself, through rewiring operations that remain valid, i.e., that preserve the integrity constraints of the database. We focus on the latter setting, and investigate whether gradientbased adversarial attacks can identify structural perturbations that degrade the predictions of relational deep learning systems. Concretely, we perturb PK–FK relationships while enforcing the integrity constraints of relational theory, namely uniqueness, inclusion, and functional dependencies. Each foreign key must reference a valid primary key and remain attached to exactly one parent tuple, and functional dependencies must hold throughout the perturbation. Because the graph topology is entirely induced by these dependencies, perturbing the database structure is equivalent to rewiring the induced graph; at the database level, such a rewiring reassigns a tuple to an incorrect but admissible foreign key, propagating semantic inconsistencies through the PK–FK structure.
theoretical guarantees on worst-case robustness under bounded perturbations.
( 𝒙1 ) ( 𝒙4 )
( 𝒙2 )
( 𝒙5 )
( 𝒙3 ) ( 𝒙6 )
Clean Relational database
Prediction Pois oned
( 𝒙7 )
Clean Entity graph
( 𝒙1 ) ( 𝒙2 ) ( 𝒙3 )
( 𝒙4 ) ( 𝒙5 )
( 𝒙6 ) ( 𝒙7 )
Perturbed Entity graph
Figure 1: Overview of the attack setting. A relational database is encoded into a heterogeneous entity graph following the RDL construction, where tuples become nodes and PK–FK dependencies become typed edges. The attacker rewires a small number of foreign-key edges while preserving the schema’s integrity constraints, so that every tuple keeps exactly one parent, producing a perturbed entity graph that, once passed through the trained GNN, degrades the downstream prediction. Rewired edges are shown in red, and the edges they replace are faded.
The resulting search problem is combinatorial. Each admissible edit must simultaneously satisfy the integrity constraints and respect a global perturbation budget, and the effect of edits is highly non-additive because message passing in the GNN couples them. Exhaustively evaluating all admissible rewiring combinations is therefore intractable, and the space grows with the number of eligible foreign keys and admissible destinations, which motivates the use of approximate search heuristics. Contributions. We investigate seven such heuristic strategies: two random sampling baselines and five gradient-guided variants. The gradient-based variants are derived from a prior work [26] which uses differentiable edge masks to estimate the sensitivity of the prediction loss to candidate rewirings and to guide selection. These designs follow approaches that have proven effective across a variety of combinatorial optimization problems [4, 6–8, 12, 16, 17, 24, 25, 27]. Empirically, gradient-based attacks consistently outperform random baselines on regression tasks. On classification tasks the picture is more nuanced: gains are smaller, which we attribute to low label-flip rates and the greater local stability of classification outputs under sparse perturbations.
2
RELATED WORK
Adversarial learning has been studied across a broad range of data modalities, progressively moving from i.i.d. data to structured and relational settings. Euclidean Data. Early works cast data poisoning as a bilevel optimization problem, enabling gradient-based and targeted manipulations of the training data [3, 14]. Complementarily, [22] provide
Graph-Structured Data. Adversarial attacks on graphs exploit structural dependencies rather than feature noise alone. Gradientbased methods perturb the adjacency matrix to degrade model performance [6, 7, 26], while more realistic settings consider constrained or black-box attacks, often framed as influence maximization [16, 17]. A complementary line of work studies how message passing propagates such perturbations and how to defend against it [12]. Knowledge Graphs and Tabular Data. In structured domains, attacks adapt to discrete and heterogeneous representations. For knowledge graphs, adversarial methods target triples through poisoning or adversarial training [4, 24, 25]. In tabular settings, attacks focus on label corruption and backdoor mechanisms under feature constraints [5, 23], with theoretical foundations in malicious noise models [15]. Relational Deep Learning. Recent work introduces Relational Deep Learning (RDL), which models multi-table databases as heterogeneous temporal graphs and enables end-to-end learning via GNNs [10]. Benchmarks such as RelBench show that this paradigm outperforms traditional feature engineering pipelines [11, 20], supported by modular frameworks for heterogeneous data encoding [13]. A growing body of work highlights its open challenges, including scalability, temporality, and heterogeneity [9]. Learning over Relational Databases. The database community has long studied machine learning directly over relational data, exploiting the schema to make learning efficient. Factorized and in-database learning train models over the join of multiple tables without materializing it, and notably exploit functional dependencies to reduce model dimensionality [2, 18, 21]; relational deep learning can be viewed as the GNN-based successor to this line, replacing closed-form aggregates with message passing. Integrity constraints—functional and inclusion dependencies, referential integrity—are foundational to relational theory [1], and a large body of work relies on them for data cleaning, where constraintbased repair detects and fixes violations to restore a consistent database [19]. Our attack is the adversarial counterpart of this process: rather than repairing inconsistencies, it searches for integritypreserving edits that keep the database consistent yet degrade the downstream model. Gap. Adversarial attacks are by now well understood in the Euclidean, graph, and tabular settings, but their extension to relational deep learning remains largely unexplored. Crucially, the techniques developed for generic graphs do not transfer directly: they assume that edges can be inserted or deleted freely, whereas in a relational database the topology is induced by the schema and every edit must preserve its integrity constraints. The admissible perturbations are therefore not arbitrary adjacency changes but integrity-preserving rewirings of foreign-key references, which is the setting we study in this work.
r1 & rev r1
rewired edge
r2 & rev r2 𝑧-score 𝑟 1 .. .
0.2
8
∇𝑆𝑟 1 ℓ
0.8
1
.. .
0
4
r1 rev r1 5
Initial relational entity graph
0.5
∇𝑆𝑟 2 ℓ
2
.. .
.. . .. .
New edge
𝑧-score 𝑟 2
.. .
-1
replaced edge
.. .
0 0.2
r2 rev r2 Raw gradients
.. .
Combined Z Score respecting constraints
New edge
Final relational entity graph
Figure 2: Gradient-guided constrained rewiring of a relational entity graph. For each relation 𝑟 we compute the gradient ∇𝑆𝑟 ℓ of the batch loss with respect to its adjacency and combine the forward and reverse contributions into a single candidate score. To make sensitivities comparable across relations, these scores are normalized per relation; the 𝑧-score is shown here as a representative scheme, with the full set of normalizations we consider summarized in Table 1. The highest-scoring admissible candidates—those respecting the schema’s integrity constraints—are selected as new edges and applied to the graph. Each selected rewiring replaces a single foreign-key edge by an admissible one (orange), leaving the degree-one constraint intact; the replaced edges are shown faded.
3
PRELIMINARIES
Representing Relations as Heterogeneous Entity Graphs. We follow the RelBench construction, which represents a relational database as a heterogeneous entity graph: each row of each table becomes a node, and each foreign-key dependency induces a typed edge (see Figure 1). The node set is not homogeneous. It is partitioned by table type, à V = 𝜏 ∈ T V𝜏 , where T is the set of table (node) types, V𝜏 is the à set of tuples (rows) of table 𝜏, and denotes a disjoint union. All nodes thus live in a common vertex set V but remain separated into semantically distinct subsets according to their table type. We define the heterogeneous graph as G = (V, {E𝑟 }𝑟 ∈ R ), where each relation type 𝑟 ∈ R carries its own edge set E𝑟 ⊆ Vsrc(𝑟 ) × Vdst(𝑟 ) . For a relation 𝑟 , the types src(𝑟 ) ∈ T and dst(𝑟 ) ∈ T denote the table at which the edge starts and the table at which it ends, respectively, so that (𝑖, 𝑗) ∈ E𝑟 means that tuple 𝑖 of type src(𝑟 ) is linked to tuple 𝑗 of type dst(𝑟 ). The connectivity of each relation 𝑟 is encoded by an adjacency matrix 𝑆𝑟 ∈ {0, 1}𝑛src(𝑟 ) ×𝑛dst(𝑟 ) , with 𝑛 src(𝑟 ) = |Vsrc(𝑟 ) | and 𝑛 dst(𝑟 ) = |Vdst(𝑟 ) |, whose entries satisfy (𝑆𝑟 )𝑖 𝑗 = 1 ⇐⇒ (𝑖, 𝑗) ∈ E𝑟 . A relational dependency is naturally directed: a foreign key points toward the referenced primary key. In practice (in RelBench and PyG implementations) each such dependency is duplicated into two edge types, so that message passing can propagate in both directions. Node Features. Each tuple carries tabular attributes (categorical, numerical, text, timestamp, etc.), which are independently embedded and merged into a single dense per-tuple representation following the tensor-frame paradigm: 𝑋 = {𝑋𝜏 }𝜏 ∈ T , with 𝑋𝜏 ∈ R | V𝜏 | ×𝑑𝜏 .
A heterogeneous GNN 𝑓𝜃 then predicts from both the features and the typed relations, 𝑦ˆ = 𝑓𝜃 (𝑋, {𝑆𝑟 }𝑟 ∈ R ).
4
CONSTRAINED ADVERSARIAL ATTACKS ON RELATIONAL GRAPHS 4.1 Preserving Foreign-Key Integrity Relational graph semantics and perturbation constraints. Foreignkey to primary-key (FK–PK) dependencies form the structural backbone of the relational graph: they connect tuples from different tables wherever the schema defines a referential constraint. The graph topology is therefore induced directly by the referential structure of the database. Each foreign-key tuple references exactly one parent tuple. Admissible attacks consequently cannot insert or delete edges freely; perturbations are restricted to rewiring operations, in which the parent referenced by a foreign key is replaced by another admissible primary-key node (and the symmetric reverse edge is updated accordingly), preserving the degree-one constraint. Formally, a perold ) by (𝑣 , 𝑣 new ), so at most one turbation replaces an edge (𝑣 FK, 𝑣 PK FK PK rewiring can be applied to a given FK node per attack step. Budget. Attacks are performed under a global perturbation budget 𝐵, the maximum number of rewiring operations allowed during a single attack. The budget is distributed across the relations of the heterogeneous graph, so that perturbations may affect several edge types while remaining sparse and semantically valid. Preserving functional dependencies. To keep the database consistent under perturbation, we distinguish between mutable and immutable dependencies. A dependency is said to be mutable if its
value can be modified by the attack while preserving database integrity. Mutable dependencies are further divided into two classes: coupled rewiring and local rewiring. In contrast, immutable dependencies cannot be modified because they encode entity identities or protected structural constraints. We describe them next. Local rewiring acts independently on a single FK–PK dependency: a foreign key is reassigned to another admissible parent while preserving referential integrity and all degree constraints imposed by the schema. Coupled rewiring concerns groups of foreign keys whose semantics are jointly constrained, where editing one dependency in isolation could yield an incoherent configuration. Such foreign keys must be perturbed simultaneously, as a single atomic operation. Immutable dependencies are globally sensitive or structurally critical relations whose modification could propagate large-scale inconsistencies through the database; these are excluded from the attack space. Overview of the threat model. In short, the proposed threat model seeks adversarial rewirings while preserving the integrity of the relational database. No tuples are inserted or removed; instead, the attack is restricted to modifying foreign-key references. These references are rewired such that their new values remain valid with respect to the corresponding attribute domains and integrity constraints. As a result, the size of the database remains unchanged throughout the attack.
4.2
Why We Need Heuristics
We first ask what it would cost to find the best possible attack. Let 𝐶 be the total number of legal rewiring candidates across all relations, assuming the full set of admissible FK–PK perturbations is known in advance. Under a budget 𝐵, the attacker must select 𝐵 of these candidates, and even in this simplified view the number of possible attacks already grows combinatorially as 𝐶𝐵 . This estimate still understates the true difficulty, because rewiring operations are not independent. Several relations encode the same information through forward and reverse edges, so a perturbation on one relation may constrain or invalidate perturbations on another; moreover, structurally coupled foreign keys must be modified jointly to preserve integrity. These dependencies add further combinatorial constraints, making the search for an optimal perturbation considerably harder than a plain subset-selection problem and motivating the use of approximate heuristics.
5 WHITE-BOX GRADIENT-BASED ATTACK 5.1 Attack Objective We assume a trained heterogeneous GNN 𝑦ˆ = 𝑓𝜃 (𝑋, {𝑆𝑟 }𝑟 ∈ R ), in which the node features 𝑋 are fixed and only the relational structures {𝑆𝑟 }𝑟 ∈ R may be modified. The attacker seeks perturbed relation matrices {𝑆e𝑟 }𝑟 ∈ R that worsen the prediction while respecting the edit budget and the integrity constraints introduced above: max ℓ B 𝑓𝜃 (𝑋, {𝑆e𝑟 }) B , 𝑦 B , { 𝑆e𝑟 }
where B is the mini-batch under consideration and ℓ B is the loss evaluated on its labels 𝑦 B . Unlike targeted attacks, no particular subset of nodes is singled out: the objective is to apply as few valid
structural edits as possible while maximally increasing the loss over the selected entities.
5.2
Attackable Model
The model. The original GNN is not directly amenable to structural attacks: its edge index matrices carry no gradient, since they are purely combinatorial representations of the graph structure. To recover a gradient signal over the relations, we define an alternative attackable model. The parameters of the pretrained GNN are transferred into this model and frozen, and differentiable edge weights are introduced for each relation, allowing gradients to flow through the graph structure during backpropagation. Masks and sparsity. Because the pipeline is implemented in PyTorch Geometric, graph structures are stored as sparse edge-index tensors, so gradients can only propagate through edges that already exist. To expose unseen rewiring candidates to the gradient, we augment the graph with a set of admissible candidate edges sampled under the semantic and structural constraints defined above: existing edges receive weight 1, candidate edges receive an initial weight of 0, and a differentiable mask over these weights lets gradients propagate through both the original topology and the candidate edges.
5.3
Gradient-Based Rewiring
First-order candidate scoring. The mask gives us, for each relation, a first-order signal: entries with large gradient magnitude are the structural edits to which the loss is most sensitive, which is exactly the direction a first-order (gradient-sign) attack would follow. We use this signal only to rank candidate rewirings; the formal firstorder derivation is given in Appendix A.1. Concretely, let 𝐺𝑟 = ∇𝑆𝑟 ℓbatch (𝑆𝑟 ) denote the gradient of the batch loss with respect to the direct relation 𝑟 , and let 𝐺𝑟 −1 = ∇𝑆𝑟 −1 ℓbatch (𝑆𝑟 −1 ) be the gradient of its reverse relation. Since each rewiring simultaneously modifies the forward FK→PK edge and its reverse edge, candidate sensitivity is measured by the combined score (𝐺𝑟 ) 𝑓 ,𝑝 + (𝐺𝑟 −1 )𝑝,𝑓 . For a source node 𝑓 , large positive values of this score indicate promising rewiring candidates. Exhaustively testing all destinations is too costly: with 𝑁 eligible source nodes and 𝐶 candidates per node, the prototype requires O (𝑁𝐶) forward passes, so we restrict the search to a small candidate set. Moreover, raw gradient magnitudes can vary substantially across source nodes and relations, making direct comparison difficult. To reduce this bias, we consider several normalization strategies applied to the combined forward–reverse sensitivity score. Their definitions and intended effects are summarized in Table 1. Candidate set. For each eligible source node 𝑓 with current parent 𝑝 old (𝑓 ), the set of admissible candidates for 𝑟 ∈ R is n o (𝑟 ) C𝑟 (𝑓 ) = 𝑝 ∈ Vdst(𝑟 ) : 𝑝 ≠ 𝑝 old (𝑓 ) .
Table 1: Gradient-based candidate scoring and normalization strategies. For all methods, 𝐺𝑟 and 𝐺𝑟 −1 denote the gradients associated with the forward and reverse relations, respectively, 𝜇𝑟 and 𝜎𝑟 denote the mean and standard deviation of candidate scores for relation 𝑟 , 𝑚𝑟 is the median, MAD𝑟 the median absolute deviation, and 𝑠𝑟min and 𝑠𝑟max the minimum and maximum candidate scores observed for relation 𝑟 . Method
Definition
Purpose
Raw Gradient
scoreraw ( 𝑓 , 𝑝 ) = (𝐺𝑟 ) 𝑓 ,𝑝 + (𝐺𝑟 −1 )𝑝,𝑓
Direct first-order sensitivity estimate. Preserves absolute gradient magnitude.
Z-score
score𝑧 ( 𝑓 , 𝑝 ) =
scoreraw ( 𝑓 , 𝑝 ) − 𝜇𝑟 𝜎𝑟 + 𝜀
Removes relation-specific scale effects using the mean and standard deviation.
Robust Z-score
score𝑟𝑧 ( 𝑓 , 𝑝 ) =
scoreraw ( 𝑓 , 𝑝 ) − 𝑚𝑟 MAD𝑟 + 𝜀
More robust to outliers and heavy-tailed gradient distributions.
scoreraw ( 𝑓 , 𝑝 ) − 𝑠𝑟min score𝑚𝑚 ( 𝑓 , 𝑝 ) = 𝑠𝑟max − 𝑠𝑟min + 𝜀
Min-Max
Given these candidates, we define two strategies for selecting both the edges to perturb and their new destinations; in both, perturbations are optimized jointly across all relations 𝑟 ∈ R. Direct global gradient selection. The first strategy ranks all admissible candidates C𝑟 (𝑓 ) (∀𝑟 ∈ R) by their first-order score score(𝑓 , 𝑝) and keeps the top-𝐵 globally: A★ = TopB𝑟 ∈ R, 𝑓 , 𝑝 ∈ C𝑟 ( 𝑓 ) score(𝑓 , 𝑝). This yields a fully gradient-driven attack with no explicit forward re-evaluation. Shortlist-based reranking. The second strategy adds an intermediate shortlist stage to reduce the number of explicit forward evaluations. For each source node 𝑓 and relation 𝑟 , only the top𝐾 gradient candidates are kept, focusing the search on the most promising destinations: C𝐾(𝑟 ) (𝑓 ) = TopK𝑝 ∈ C𝑟 ( 𝑓 ) (𝐺𝑟 ) 𝑓 ,𝑝 ,
𝐾 ≪ |C𝑟 (𝑓 )|,
Places all candidate scores on a common [0, 1] scale within each relation, facilitating comparisons across relations with different gradient ranges.
Note on the non-additivity of structural perturbations. The effect of structural perturbations is inherently non-additive: the impact of a rewiring on the loss can depend strongly on which other perturbations are applied simultaneously. Two edits that each increase the loss in isolation may, when combined, partially cancel or even reverse their joint effect on the prediction.
6 EXPERIMENTS 6.1 Experimental Setup All experiments were conducted on a CPU-only virtual machine with 96 cores and 396 GB of RAM. Our implementation builds on the Relational Deep Learning (RDL) framework of RelBench, itself implemented on top of PyTorch Geometric for heterogeneous graph learning.
6.2
Dataset
{𝑆𝑢 }𝑢 ∈ R\{𝑟,𝑟 −1 } ∪ 𝑆𝑟 ∪ 𝑆𝑟 −1 denotes the adjacency matrices obtained after replacing the edge (𝑟 ) (𝑓 , 𝑝 old (𝑓 )) by (𝑓 , 𝑝) in the direct relation 𝑟 , together with its sym-
We deliberately selected a dataset with a rich, highly structured relational schema rather than collections of a few isolated tables, so that we can study how adversarial perturbations propagate across relations. The attack evaluation reported below focuses on rel-f1, which contains multiple interconnected entity tables, interaction tables, foreign keys in different tables pointing to the same primary key (denoted as coupled), and hierarchical dependencies, making it representative of realistic relational systems. An overview of the dataset and its prediction tasks is given in Table 2, and the structural constraints and dependency-preserving policies enforced during rewiring are summarized in Table 3.
(𝑟 ) metric counterpart (𝑝 old (𝑓 ), 𝑓 ) ↦→ (𝑝, 𝑓 ) in the reverse relation 𝑟 −1 . The best local rewiring for node 𝑓 is
6.3
For each candidate 𝑝 ∈ C𝐾(𝑟 ) (𝑓 ) we then evaluate the exact loss variation induced by the rewiring, ( 𝑓 →𝑝 ) (𝑝→𝑓 ) Δℓ𝑟 (𝑓 , 𝑝) = ℓbatch {𝑆𝑢 }𝑢 ∈ R\{𝑟,𝑟 −1 } ∪ 𝑆𝑟 ∪ 𝑆𝑟 −1 − ℓbatch {𝑆𝑢 }𝑢 ∈ R , where ( 𝑓 →𝑝 )
𝑝𝑟★ (𝑓 ) ∈ arg
max (𝑟 )
(𝑝→𝑓 )
Δℓ𝑟 (𝑓 , 𝑝),
𝑝 ∈ C𝐾 ( 𝑓 )
and the locally optimal candidates are aggregated across relations and ranked by their achieved loss increase, keeping the top-𝐵: A★ = TopB𝑟 ∈ R, 𝑓 Δℓ𝑟 𝑓 , 𝑝𝑟★ (𝑓 ) . The final perturbation set thus satisfies the global budget while allowing coordinated changes across multiple relations.
Protocol
Model architecture. We use a heterogeneous GraphSAGE architecture with two message-passing layers. A shallow architecture is important in our setting: it limits both vanishing gradients (which would weaken the attack signal) and oversmoothing. All hidden representations use a channel dimension of 128 or 16, depending on the task (see Table 7 in the Appendix). For regression tasks the prediction head is left linear, while for classification we apply a softmax over the output logits. The attacked objective is task-dependent:
Table 2: Overview of the RelBench rel-f1 and prediction tasks considered in this work. Dataset
# Tables
rel-f1
9
# Rows
74,063
# Columns
# Tasks
Task name
Task type
4
driver-position qualifying-position driver-dnf driver-top3
Regression Regression Binary classification Binary classification
67
Table 3: Schema constraints and attack policies for the rel-f1 dataset. Relation / Foreign Key
Description
Constraint type
Mutable
Coupled with driverId, constructorId Coupled with raceId, constructorId Coupled with raceId, driverId Coupled with driverId, constructorId Coupled with raceId, constructorId Coupled with raceId, driverId
Yes
Formula 1 (rel-f1) results.raceId
Race participation result
results.driverId results.constructorId qualifying.raceId
Driver participation result Constructor participation result Qualifying session assignment
qualifying.driverId qualifying.constructorId
Driver qualifying participation Constructor qualifying participation Driver standings snapshot Driver standings snapshot Constructor standings snapshot Constructor standings snapshot Constructor race result Constructor race result Race → circuit assignment Core entity identifiers
standings.raceId standings.driverId constructor_standings.raceId constructor_standings.constructorId constructor_results.raceId constructor_results.constructorId races.circuitId drivers.driverId, constructors.constructorId, circuits.circuitId
Mean Absolute Error (MAE) for regression, and Binary or standard Cross-Entropy for classification, depending on the task. Mini-batch sampling. Each mini-batch is generated by temporal neighborhood sampling with at most 128 neighbors per hop and a batch size of 512. All reported attacks operate on a fixed mini-batch sampled from rel-f1; the trained model is frozen, so no parameter is updated during the attack and only the graph structure of the batch is modified. Perturbation budget. We focus on highly localized attacks under small budgets, i.e., adversarial rewiring that modifies between 1 and 100 edges. Attack strategies. We compare seven attack strategies that are extensions of the ones defined in Section 5. (1) Random. Admissible perturbations are sampled uniformly at random among all valid rewirings, while respecting the relational schema constraints. (2) Random + Exact. A set of admissible perturbations is first sampled uniformly at random. The sampled candidates are subsequently re-ranked through exact forward evaluation on the attacked model, and the perturbation producing the largest degradation is selected.
Coupled with driverId Coupled with raceId Coupled with constructorId Coupled with raceId Coupled with constructorId Coupled with raceId Structural FK (sensitive) Immutable PKs
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Restricted No
(3) Gradient. All admissible perturbations are scored using first-order sensitivity information obtained through backpropagation. Candidates are ranked according to their raw gradient-based scores and selected directly without additional evaluation. (4) Gradient + Exact. Gradient scores are first used to rank all admissible perturbations. The resulting candidates are then re-evaluated through exact forward passes on the attacked model, allowing us to assess how accurately the first-order approximation predicts the true attack effect. (5) Gradient + Z-score. Instead of using raw gradient scores, candidate perturbations are normalized using a per-relation Z-score transformation. This reduces the impact of scale differences across relations and encourages a more diverse selection of perturbations before applying the attack. (6) Gradient + Robust Z-score. Candidates are normalized using a robust Z-score based on the median and median absolute deviation (MAD). This strategy is less sensitive to heavy-tailed gradient distributions and outliers, providing a more stable ranking of perturbations across heterogeneous relations.
Gradient Exact Gradient Global Z Only Gradient Minmax Relation
Gradient Raw Only Gradient Robust Z Only
Random Random Exact
1.02
Attacked MAE
1.01 1.00 0.99 0.98 0.97 0.96 0
100
200
300
Budget
400
500
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 independently within each relation using min–max scaling, mapping the lowest gradient score to 0 and the highest to 1. The objective is to reduce the dominance of relations that naturally produce larger gradient magnitudes and to make perturbation scores comparable across relations.
6.4
Results
Attack effectiveness. The main results are reported in Table 4. The clearest trend appears on the regression tasks: gradient-based attacks raise the attacked MAE monotonically with the budget, while the random baselines leave the error essentially unchanged. On driver-position, for instance, the pure gradient attack increases the MAE from 3.155 at 𝐵=1 to 3.179 at 𝐵=100, whereas constrained random sampling stays flat around 3.144; the same pattern holds on qualifying-position (0.995 → 1.013 versus a flat 0.994). Importantly, these aggregate numbers are conditioned by the fact that some trained models are not perfectly fitted, which can dampen the apparent effect of the perturbations. For a better-fitted model, Figure 3 shows that the attack can induce a relative degradation of up to roughly 7% with respect to the clean value. This confirms that the first-order signal identifies structural edits to which the regression output is clearly sensitive, whereas random rewiring does not. On the classification tasks (driver-dnf, driver-top3) the effect is markedly smaller: even the strongest attacks reduce accuracy by only a couple of points (e.g. driver-dnf from 77.37 to 75.51), and the ranking between methods is noisier. We attribute this to a low label-flip rate: decision boundaries make classification outputs locally stable, so a small, integrity-preserving rewiring rarely changes the predicted class even when it perturbs the underlying logits. The occasional non-monotonic behavior of some classification rows
is consistent with the non-additivity of structural perturbations discussed earlier: edits that help individually may partially cancel once combined. Computational cost. Table 5 reports the average runtime of each attack strategy. Three distinct families of methods emerge. The first consists of purely random rewiring, which is extremely fast (≈ 0.1sec) but generally fails to generate perturbations strong enough to produce a measurable degradation compared to the clean baseline. The second family includes gradient-based methods without exact candidate re-evaluation. Depending on the normalization strategy, these attacks require between 45.8sec and 54.1sec, making them substantially more expensive than random rewiring, but also significantly more effective. The third family corresponds to methods that perform an exact re-evaluation of shortlisted candidates. These approaches are the most computationally demanding, with runtimes of 87.2sec for Gradient Exact and 91.8sec for Random Exact. Despite their additional computational cost, they do not provide a substantial improvement in attack effectiveness over the simpler gradient-based approaches. Overall, the results suggest that gradient-only attacks offer the best trade-off between computational cost and attack performance. They achieve most of the gains obtained by exact shortlist methods while requiring roughly half the runtime, making them a more attractive option in practice. Effect of adding normalization on attack diversity. We finally analyze how normalization affects the structure of the selected perturbations along two complementary dimensions. First, we measure whether the attack repeatedly rewires foreign keys toward the same target node or spreads its modifications across many distinct candidates. This is important because an attack that redirects hundreds of tuples toward a single entity would create an obvious anomaly and could easily be detected in a real database. Second, we measure how many relations are involved in the attack. If one relation systematically produces larger gradient magnitudes than the others, a global ranking may allocate most of the perturbation budget to that relation alone. Table 6 reports the number of distinct relations touched by the attack (𝑁 rel ) and the number of distinct target candidates involved in the selected perturbations (𝑁 cand ). Interestingly, all methods exhibit extremely large candidate diversity. Even the raw gradient attack selects 499.2 ± 1.8 distinct candidates for a budget of 500, meaning that almost every perturbation targets a different node. Similar values are observed for all normalization schemes (486–497 distinct candidates). This indicates that the attack is not driven by a small set of universally attractive target nodes. Instead, perturbations are naturally distributed across a large portion of the graph, which is arguably desirable from a stealth attack perspective since it avoids creating highly suspicious hub-like patterns. The main effect of normalization is therefore not on candidate diversity but on relation diversity. The raw gradient attack focuses on only 1.8 ± 1.3 relations on average, whereas the normalized variants spread the perturbation budget across most or all of the seven available relations (5.2–7.0 relations). One might expect such broader coverage to produce stronger attacks by exploiting a larger fraction of the relational schema. Surprisingly, Table 4 shows that this is not necessarily the case. Despite concentrating its budget on
Table 4: Performance under structural attacks on the rel-f1 dataset. For classification tasks (driver-dnf, driver-top3), results are reported as attacked accuracy (%) and lower values indicate stronger attacks. For regression tasks (driver-position, qualifying-position), results are reported as attacked MAE and higher values indicate stronger attacks. Best method for each budget is shown in bold, while the second best is underlined. Results are averaged over five independent random seeds. Task
Method
𝐵 =1
𝐵 = 25
𝐵 = 50
𝐵 = 75
𝐵 = 100
driver-dnf
Random Random + exact rerank Gradient raw Gradient z-score Gradient robust z-score Gradient + exact rerank
77.37 ± 0.58 76.34 ± 0.59 77.37 ± 0.58 77.37 ± 0.58 77.37 ± 0.58 77.37 ± 0.58
77.37 ± 0.58 76.24 ± 0.45 77.37 ± 0.58 77.37 ± 0.58 76.44 ± 0.73 77.37 ± 0.58
77.37 ± 0.58 76.24 ± 0.45 77.37 ± 0.58 76.44 ± 0.73 76.44 ± 0.73 76.44 ± 0.73
77.37 ± 0.58 76.24 ± 0.45 76.54 ± 0.86 75.51 ± 2.04 76.54 ± 0.86 75.51 ± 2.04
77.37 ± 0.58 76.24 ± 0.45 76.54 ± 0.86 75.51 ± 2.04 76.54 ± 0.86 75.51 ± 2.04
driver-top3
Random Random + exact rerank Gradient raw Gradient z-score Gradient robust z-score Gradient + exact rerank
77.63 ± 3.72 77.63 ± 3.72 77.63 ± 3.72 77.63 ± 3.72 77.63 ± 3.72 77.63 ± 3.72
77.63 ± 3.72 77.63 ± 3.72 76.97 ± 2.79 76.97 ± 2.79 76.97 ± 2.79 76.97 ± 2.79
77.53 ± 3.86 76.97 ± 2.79 76.97 ± 2.79 76.97 ± 2.79 77.53 ± 3.86 76.97 ± 2.79
77.53 ± 3.86 76.97 ± 2.79 76.97 ± 2.79 76.97 ± 2.79 77.53 ± 3.86 76.97 ± 2.79
77.53 ± 3.86 76.88 ± 2.90 76.32 ± 3.28 76.97 ± 2.79 77.53 ± 3.86 76.97 ± 2.79
driver-position
Random Random + exact rerank Gradient raw Gradient z-score Gradient robust z-score Gradient min-max relation Gradient + exact rerank
3.1448 ± 0.0101 3.1450 ± 0.0102 3.1552 ± 0.0119 3.1527 ± 0.0126 3.1552 ± 0.0118 3.1552 ± 0.0119 3.1528 ± 0.0126
3.1443 ± 0.0101 3.1448 ± 0.0103 3.1677 ± 0.0162 3.1662 ± 0.0114 3.1589 ± 0.0141 3.1611 ± 0.0120 3.1568 ± 0.0102
3.1443 ± 0.0101 3.1448 ± 0.0103 3.1744 ± 0.0210 3.1694 ± 0.0154 3.1606 ± 0.0164 3.1665 ± 0.0093 3.1568 ± 0.0102
3.1443 ± 0.0101 3.1448 ± 0.0103 3.1777 ± 0.0219 3.1735 ± 0.0171 3.1655 ± 0.0191 3.1666 ± 0.0112 3.1568 ± 0.0102
3.1443 ± 0.0101 3.1448 ± 0.0103 3.1791 ± 0.0233 3.1775 ± 0.0200 3.1671 ± 0.0190 3.1679 ± 0.0106 3.1568 ± 0.0102
qualifying-position
Random Random + exact rerank Gradient raw Gradient z-score Gradient robust z-score Gradient min-max relation Gradient + exact rerank
0.9941 ± 0.0531 0.9941 ± 0.0531 0.9949 ± 0.0527 0.9949 ± 0.0527 0.9951 ± 0.0530 0.9949 ± 0.0527 0.9953 ± 0.0533
0.9938 ± 0.0529 0.9940 ± 0.0530 1.0011 ± 0.0591 1.0019 ± 0.0591 0.9995 ± 0.0528 0.9985 ± 0.0533 0.9970 ± 0.0523
0.9935 ± 0.0529 0.9940 ± 0.0530 1.0074 ± 0.0699 1.0088 ± 0.0701 1.0006 ± 0.0527 0.9994 ± 0.0525 0.9970 ± 0.0523
0.9935 ± 0.0529 0.9940 ± 0.0530 1.0101 ± 0.0739 1.0101 ± 0.0708 1.0010 ± 0.0529 0.9991 ± 0.0513 0.9970 ± 0.0523
0.9935 ± 0.0529 0.9940 ± 0.0530 1.0127 ± 0.0781 1.0112 ± 0.0712 1.0013 ± 0.0529 0.9995 ± 0.0517 0.9970 ± 0.0523
Table 5: Computation time comparison of different attack strategies on the qualifying-position task. Reported values are mean runtime in seconds with standard deviation. Family
Attack type
Runtime (s)
Random
Random
0.10 ± 0.00
Gradient
Gradient Raw Only Gradient Global Z Only Gradient Robust Z Only Gradient MinMax Relation
45.77 ± 1.29 48.08 ± 1.97 53.77 ± 0.83 54.13 ± 1.41
Shortlist
Gradient Exact Random Exact
87.16 ± 5.27 91.82 ± 0.89
Table 6: Diversity analysis of attack candidate selection under different normalization strategies. 𝑁 rel denotes the number of distinct relations touched by the selected perturbations, while 𝑁 cand denotes the number of distinct candidate nodes involved. Dataset
Method
rel-f1 qualifying-position (7 relations)
Gradient + Z-score + Robust Z-score + Min-Max
7
relatively few relations, the raw gradient attack remains highly competitive and often achieves the strongest degradation of predictive performance. This suggests that, at least on qualifying-position, attack effectiveness is driven more by identifying a small number of highly influential relations than by uniformly perturbing the entire schema.
𝑁 rel
𝑁 cand
1.8 ± 1.3 5.2 ± 1.3 7.0 ± 0.0 7.0 ± 0.0
499.2 ± 1.8 486.2 ± 13.9 497.0 ± 4.0 493.4 ± 7.1
CONCLUSION
We studied the adversarial robustness of the relational deep learning pipeline, in which a database is encoded as a heterogeneous entity graph and a GNN is trained for downstream prediction. We formalized a white-box threat model in which the attacker reasons about the graph but can only act on the upstream database, through integrity-preserving rewirings of foreign-key references under a global budget. Within this constrained, combinatorial, search space we proposed gradient-guided heuristics that score candidate rewirings from the model’s first-order sensitivity, together
with a per-relation normalization that controls how perturbations spread across relations and targets. We investigate seven attack strategies, including two random baselines and five gradient-based attacks, and evaluate their effectiveness through a comprehensive robustness study. Our findings show that, on RelBench, gradient-based attacks consistently degrade regression tasks at a fraction of the cost of exact shortlist re-evaluation, while classification tasks prove more robust, which we trace to their low label-flip rate. Per-relation normalization redistributes the perturbation budget across more relations rather than making the attack stealthier: all variants, including the raw gradient, already spread their edits over hundreds of distinct targets, so none produces the suspicious hublike patterns that motivated normalization in the first place. This broader relational coverage does not translate into stronger attacks, and the concentrated raw-gradient variant remains competitive throughout. Together, these results show that the relational structure itself is an exploitable attack surface once a database is consumed by a learned model, especially for regression tasks, and that gradient-based heuristics are effective for navigating the combinatorial search space of adversarial perturbations. Our evaluation focuses on rel-f1, whose coupled, hierarchical schema exercises every class of admissible rewiring.
8
FUTURE WORK
Several directions remain open. First, our evaluation focuses on rel-f1; extending it to the broader RelBench suite is a natural next step that would test whether these findings hold across schemas of different size, connectivity, and task type. Second, attacks could target the feature space, i.e. tuple attributes that are neither primary nor foreign keys. This setting is considerably harder, especially for free-form text attributes, where the search space becomes semantic rather than purely combinatorial. Third, richer structural attack policies could be explored beyond the first-order rewiring considered here: reinforcement learning, genetic algorithms, or generative approaches may yield stronger perturbations while also enabling more realistic black-box attacks. Finally, targeted attacks are an important next step. Because the space of admissible rewirings is tightly constrained by database integrity rules, forcing the model toward a specific prediction outcome, for example promoting a chosen recommendation, is particularly challenging. Arguably, the inverse problem is of greater interest: how to design models that are robust to such perturbations. In other words, studies like ours do not necessarily have to be only adversarial. They can also be used to identify the weak points of the architecture and to design better models for deep learning on relational data.
REFERENCES [1] Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases. Addison-Wesley. [2] Mahmoud Abo Khamis, Hung Q. Ngo, XuanLong Nguyen, Dan Olteanu, and Maximilian Schleich. 2018. In-Database Learning with Sparse Tensors. In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS). ACM, 325–340. [3] Battista Biggio, Blaine Nelson, and Pavel Laskov. 2012. Poisoning attacks against support vector machines. arXiv preprint arXiv:1206.6389 (2012). [4] Liwei Cai and William Yang Wang. 2018. Kbgan: Adversarial learning for knowledge graph embeddings. In Proceedings of the 2018 conference of the North American chapter of the association for computational linguistics: human language
technologies, volume 1 (long papers). 1470–1480. [5] Xinglong Chang, Gillian Dobbie, and Jörg Wicker. 2023. Fast adversarial labelflipping attack on tabular data. arXiv preprint arXiv:2310.10744 (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 Transactions on Computational Social Systems 8, 1 (2020), 99–109. [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] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. 2018. Adversarial attack on graph structured data. In International conference on machine learning. PMLR, 1115–1124. [9] Vijay Prakash Dwivedi, Charilaos Kanatsoulis, Shenyang Huang, and Jure Leskovec. 2025. Relational deep learning: Challenges, foundations and nextgeneration architectures. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2. 5999–6009. [10] 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. In Forty-first International Conference on Machine Learning. [11] 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. In 3rd DATA-FM Workshop @ ICLR. [12] Yuxing Guo, Jianqing Liang, Kaixuan Yao, Zhihao Guo, and Jiye Liang. 2026. Graph Adversarial Defense via Hilbert-Schmidt Independence Criterion against Influence Maximization Attacks. In Proceedings of the ACM Web Conference 2026. 4565–4576. [13] 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). [14] Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru, and Bo Li. 2018. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. arXiv preprint arXiv:1804.00308 (2018). [15] Michael Kearns and Ming Li. 1988. Learning in the presence of malicious errors. In Proceedings of the twentieth annual ACM symposium on Theory of computing. 267–280. [16] Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. 2022. Adversarial attack on graph neural networks as an influence maximization problem. In Proceedings of the fifteenth ACM international conference on web search and data mining. 675–685. [17] Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. 2020. Towards more practical adversarial attacks on graph neural networks. Advances in neural information processing systems 33 (2020), 4756–4766. [18] Dan Olteanu and Maximilian Schleich. 2016. Factorized Databases. ACM SIGMOD Record 45, 2 (2016). [19] Theodoros Rekatsinas, Xu Chu, Ihab F. Ilyas, and Christopher Ré. 2017. HoloClean: Holistic Data Repairs with Probabilistic Inference. Proceedings of the VLDB Endowment 10, 11 (2017), 1190–1201. [20] 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 Systems 37 (2024), 21330–21341. [21] Maximilian Schleich, Dan Olteanu, and Radu Ciucanu. 2016. Learning Linear Regression Models over Factorized Joins. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD). ACM, 3–18. [22] Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. 2017. Certified defenses for data poisoning attacks. Advances in neural information processing systems 30 (2017). [23] Behrad Tajalli, Stefanos Koffas, and Stjepan Picek. 2025. CatBack: Universal Backdoor Attacks on Tabular Data via Categorical Encoding. arXiv preprint arXiv:2511.06072 (2025). [24] 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). [25] Tianzhe Zhao, Jiaoyan Chen, Yanchi Ru, Qika Lin, Yuxia Geng, and Jun Liu. 2024. Untargeted adversarial attack on knowledge graph embeddings. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval. 1701–1711. [26] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. 2018. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining. 2847–2856. [27] Daniel Zügner, Oliver Borchert, Amir Akbarnejad, and Stephan Günnemann. 2020. 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 under an ℓ∞ budget. We state and prove this direction here for completeness; in the discrete database setting it serves only to rank candidate rewirings, which are subsequently projected onto admissible, sparse edits. Proposition 1 (FGSM under an ℓ∞ constraint on relational GSOs). Let {𝑆𝑟 }𝑟 ∈ R be the family of graph shift operators, or adjacency matrices, associated with the relations of a relational graph, and let J ({𝑆𝑟 }𝑟 ∈ R ) denote the attack objective, for instance the loss of a trained model evaluated on the perturbed graph structure. We consider perturbations {Δ𝑟 }𝑟 ∈ R such that 𝑆𝑟′ = 𝑆𝑟 + Δ𝑟 ,
𝑟 ∈ R,
Table 7: Training and attack hyperparameters for the rel-f1 tasks. “Hidden” is the channel dimension and “# Cand.” the number of sampled admissible rewiring candidates per source node. Task
Type
Epochs
Layers
Hidden
# Cand.
driver-position qualifying-position driver-dnf driver-top3
Reg. Reg. Clf. Clf.
10 18 18 18
2 2 2 2
128 128 16 16
100 100 400 400
Fix one relation 𝑟 . Writing the Frobenius inner product entrywise, ∑︁ ⟨𝐺𝑟 , Δ𝑟 ⟩ = (𝐺𝑟 )𝑖 𝑗 (Δ𝑟 )𝑖 𝑗 . 𝑖,𝑗
Because ∥Δ𝑟 ∥ ∞ ≤ 𝜀𝑟 , each entry satisfies |(Δ𝑟 )𝑖 𝑗 | ≤ 𝜀𝑟 . Hence, for every coordinate (𝑖, 𝑗), (𝐺𝑟 )𝑖 𝑗 (Δ𝑟 )𝑖 𝑗 ≤ |(𝐺𝑟 )𝑖 𝑗 | |(Δ𝑟 )𝑖 𝑗 | ≤ 𝜀𝑟 |(𝐺𝑟 )𝑖 𝑗 |.
under the coordinate-wise constraint ∥Δ𝑟 ∥ ∞ ≤ 𝜀𝑟 ,
∀𝑟 ∈ R.
Assume that J is differentiable with respect to each 𝑆𝑟 . Then, using a first-order Taylor expansion around {𝑆𝑟 }𝑟 ∈ R , the perturbation maximizing the linearized objective solves ∑︁ max ∇𝑆𝑟 J, Δ𝑟 s.t. ∥Δ𝑟 ∥ ∞ ≤ 𝜀𝑟 ∀𝑟 ∈ R, {Δ𝑟 }𝑟 ∈R
𝑟 ∈R
and is given relation-wise by
𝑖,𝑗
This upper bound is attained by choosing each entry of Δ𝑟 with maximal magnitude and the same sign as the corresponding gradient entry, namely (Δ𝑟★)𝑖 𝑗 = 𝜀𝑟 sign (𝐺𝑟 )𝑖 𝑗 . Therefore
Δ𝑟★ = 𝜀𝑟 sign ∇𝑆𝑟 J ,
∀𝑟 ∈ R.
Equivalently, the first-order adversarial perturbation is obtained by moving each entry of each relation matrix in the sign direction of its gradient, with maximal amplitude allowed by the ℓ∞ budget. Proof. We start from the perturbed objective J ({𝑆𝑟 + Δ𝑟 }𝑟 ∈ R ).
𝑟 ∈R
! +𝑜
∑︁
Δ𝑟★ = 𝜀𝑟 sign(𝐺𝑟 ) = 𝜀𝑟 sign ∇𝑆𝑟 J . Since this holds independently for every relation 𝑟 ∈ R, the global maximizer of the linearized problem is Δ𝑟★ = 𝜀𝑟 sign ∇𝑆𝑟 J , ∀𝑟 ∈ R. This is precisely the FGSM-type perturbation on the family of relational graph shift operators. □
A.2
By first-order Taylor expansion around the reference point {𝑆𝑟 }𝑟 ∈ R , we obtain ∑︁ J ({𝑆𝑟 + Δ𝑟 }𝑟 ∈ R ) = J ({𝑆𝑟 }𝑟 ∈ R ) + ∇𝑆𝑟 J, Δ𝑟 ∥Δ𝑟 ∥ .
𝑟 ∈R
For sufficiently small perturbations, maximizing the perturbed objective is therefore approximated by maximizing the linear term ∑︁ ∇𝑆𝑟 J, Δ𝑟 𝑟 ∈R
under the constraints ∥Δ𝑟 ∥ ∞ ≤ 𝜀𝑟 . Since both the objective and the constraints are separable across relations, this optimization decomposes into independent subproblems: max ⟨𝐺𝑟 , Δ𝑟 ⟩ , where 𝐺𝑟 := ∇𝑆𝑟 J . ∥Δ𝑟 ∥ ∞ ≤𝜀𝑟
Summing over all coordinates yields ∑︁ ⟨𝐺𝑟 , Δ𝑟 ⟩ ≤ 𝜀𝑟 |(𝐺𝑟 )𝑖 𝑗 |.
Training and Attack Hyperparameters
We emphasize that the effectiveness of structural attacks is itself highly sensitive to the training configuration: the depth and width of the model, the number of training epochs, and the size of the sampled candidate pool all affect how much gradient signal is available and how stable the decision boundaries are. The settings below were chosen to obtain well-fit models without overfitting; in particular, regression tasks required a substantially larger hidden dimension than classification tasks. All models are heterogeneous GraphSAGE networks trained with the standard RelBench temporal train/validation/test split. Each experiment was repeated using five chosen seeds: {39, 40, 41, 42, 43}. The reported results correspond to the mean and standard deviation across these runs.