Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints

• URL: http://arxiv.org/abs/2607.07089v1
• Date: Wed, 08 Jul 2026 07:23:09 GMT
• Title: Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints
• Abstract summary: Deep Deep Learning (DL) has become a standard methodology for machine learning on databases.<n>We study the adversarial robustness of this pipeline.<n>We consider a white-box attacker who knows how the graph is built and the model is trained, but can only act on the upstream database rewiring by foreign-key references.
• Score: 6.588918521735523
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• Defending against Model Extraction for GNNs with Model Reprogramming [57.82196268649236]
  Graph Neural Networks (GNNs) serve as the backbone for high-stakes applications in Machine-Learning-as-a-Service (ML)<n>Still, their black-box deployment exposes them to Model Extraction (ME) attacks.<n>Existing defenses suffer from a critical ''Euclidean bias''<n>We propose GraphRP, a proactive defense framework that repurposes Model Reprogramming for security.
  arXiv  Detail & Related papers  (2026-08-11T23:20:15Z)
• Beyond Homophily: Towards Generalized Graph Reconstruction Attack and Defense [80.28330585803133]
  Graph neural networks (GNNs) are widely deployed on computation data, yet they can leak sensitive or proprietary information about the training graph adjacency.<n>This work studies graph reconstruction attacks (GRA), a form of model inversion that reconstructs the training adjacency from a trained GNN.<n>We propose MC-GRA (+), which reconstructs the adjacency by optimizing a surrogate adjacency whose GNN-induced representations align with those of the target model.<n>On the defense side, we propose MC-GPB (+), which suppresses adjacency-dependent information throughout the representation chain
  arXiv  Detail & Related papers  (2026-06-06T09:29:27Z)
• GRASP: Geometry-aware Residual Alignment for Scalable Pretraining Data Attribution [5.770893169582546]
  This work reframes attribution as subset-level counterfactual utility prediction.<n>We introduce GRASP, an interaction-aware surrogate.<n>It decisively outperforms existing scalable baselines.
  arXiv  Detail & Related papers  (2026-06-05T04:17:50Z)
• RelPrism: A Multi-Faceted Pre-training Framework with Self-Generated Tasks for Relational Databases [49.47033473074821]
  We propose RelPrism, a multi-faceted self-supervised learning framework for RDBs.<n>RDB tasks often require multi-faceted information across different perspectives and granularities.<n>Our experiments show that RelPrism improves ROC-AUC by 4.15% for classification and reduces MAE by 10.75% for regression over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-05-22T05:19:58Z)
• Robust low-rank estimation with multiple binary responses using pairwise AUC loss [0.0]
  Multiple binary responses arise in many modern data-analytic problems.<n>Low-rank models offer a natural way to encode latent dependence across tasks.<n>Existing methods for binary data are largely likelihood-based and focus on pointwise classification.
  arXiv  Detail & Related papers  (2026-01-13T15:00:10Z)
• Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization [35.16750653336608]
  We introduce the likelihood ratio regularized quantile regression algorithm, which combines the pinball loss with a novel choice of regularization.<n>We show that the LR-QR method has coverage at the desired level in the target domain, up to a small error term.<n>Our experiments demonstrate that the LR-QR algorithm outperforms existing methods on high-dimensional prediction tasks.
  arXiv  Detail & Related papers  (2025-02-18T16:46:44Z)
• Provable Robustness of (Graph) Neural Networks Against Data Poisoning and Backdoor Attacks [50.87615167799367]
  We certify Graph Neural Networks (GNNs) against poisoning attacks, including backdoors, targeting the node features of a given graph.<n>Our framework provides fundamental insights into the role of graph structure and its connectivity on the worst-case behavior of convolution-based and PageRank-based GNNs.
  arXiv  Detail & Related papers  (2024-07-15T16:12:51Z)
• Graph Out-of-Distribution Generalization via Causal Intervention [69.70137479660113]
  We introduce a conceptually simple yet principled approach for training robust graph neural networks (GNNs) under node-level distribution shifts. Our method resorts to a new learning objective derived from causal inference that coordinates an environment estimator and a mixture-of-expert GNN predictor. Our model can effectively enhance generalization with various types of distribution shifts and yield up to 27.4% accuracy improvement over state-of-the-arts on graph OOD generalization benchmarks.
  arXiv  Detail & Related papers  (2024-02-18T07:49:22Z)
• Redundancy-Free Self-Supervised Relational Learning for Graph Clustering [13.176413653235311]
  We propose a novel self-supervised deep graph clustering method named Redundancy-Free Graph Clustering (R$2$FGC) It extracts the attribute- and structure-level relational information from both global and local views based on an autoencoder and a graph autoencoder. Our experiments are performed on widely used benchmark datasets to validate the superiority of our R$2$FGC over state-of-the-art baselines.
  arXiv  Detail & Related papers  (2023-09-09T06:18:50Z)
• Examining and Combating Spurious Features under Distribution Shift [94.31956965507085]
  We define and analyze robust and spurious representations using the information-theoretic concept of minimal sufficient statistics. We prove that even when there is only bias of the input distribution, models can still pick up spurious features from their training data. Inspired by our analysis, we demonstrate that group DRO can fail when groups do not directly account for various spurious correlations.
  arXiv  Detail & Related papers  (2021-06-14T05:39:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.