Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints

This paper investigates the adversarial robustness of Relational Deep Learning (RDL) systems. Unlike standard graph neural network (GNN) attacks that allow arbitrary edge insertions or deletions, this study focuses on a realistic white-box threat model where an attacker can only modify the upstream relational database. The core question is whether gradient-based heuristics can identify structural rewirings that degrade model performance while strictly adhering to the database's integrity constraints (e.g., foreign-key validity and functional dependencies).

The authors treat the relational database as a heterogeneous entity graph where tuples are nodes and primary-key to foreign-key (PK-FK) dependencies are edges. Because the graph topology is derived from the database schema, the attacker is restricted to "rewiring" operations—replacing an existing foreign-key reference with an admissible alternative. To overcome the combinatorial complexity of this search space, the authors introduce an "attackable model" that uses differentiable edge masks. This allows them to compute gradients of the loss function with respect to potential structural changes, which are then used to rank and select the most damaging, integrity-preserving rewirings.

The study evaluates seven attack heuristics—two random baselines and five gradient-guided variants—on the RelBench rel-f1 benchmark. The results demonstrate that gradient-based attacks are highly effective at identifying structural perturbations that increase the loss in regression tasks. However, the gains are more modest in classification settings. The authors attribute this discrepancy to the greater local stability of classification boundaries and the lower frequency of label flips when only sparse, constrained structural edits are applied.