← Back to all news
arXiv AI

When Is a Relation Worth Trusting? Manipulation Costs, Exposure, and the Trust Trap in Multi-Relational Graph Learning

The paper investigates when it is better to ignore a relation in multi-relational graph learning rather than use it, taking into account the varying manipulation costs an adversary faces. It shows that a degree‑gating strategy outperforms any selection or reweighting when a subset of the population is isolated on a relation and the attacker cannot open the gate, and that a per‑node exposure bound can identify which relation to harden. The authors provide theoretical guarantees, empirical validation on real and synthetic graphs, and a selection protocol that is never significantly worse than ignoring the graph.

Related stories

arXiv Machine Learning
Jul 9

Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints

arXiv:2607. 07089v1 Announce Type: new 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.

By Alan Gany, Bogdan Cautis, Silviu Maniu
benchmarkssafety
More like this →
Hugging Face Trending Papers
Jul 8

Structural Adversarial Attacks on Relational Deep Learning under Integrity Constraints

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.

benchmarkssafety
More like this →
arXiv AI
Sep 11

Kernel-Complexity Edge Sanitization for Training-Free Defense against Structural Graph Attacks

Kernel-Complexity Edge Sanitization (KCES) is a training‑free, model‑agnostic defense for Graph Neural Networks that identifies and removes edges with high Kernel‑Complexity (KC) scores, which are indicative of structural influence on the graph kernel complexity metric. KCES leverages a theoretical upper bound on GNN test error derived from the graph Gram matrix to compute edge‑specific KC scores, pruning edges that are empirically enriched with adversarial perturbations. The method is computationally efficient, scalable to large graphs, and consistently outperforms representative robust baselines across diverse attack settings without requiring retraining.

By Yaning Jia, Shenyang Deng, Yaoqing Yang, Chiyu Ma, Wenxuan Xu, Soroush Vosoughi
safety
More like this →
arXiv AI
Oct 1

Who Verifies the Graph? Misspecification Attacks on Causal Action Verification for Language Agents

The paper investigates how causal action verifiers, which guard language agents’ tool calls by checking identifiability against a committed action‑state graph, can be compromised through small graph misspecifications. By removing a single bidirected edge or reversing an arrowhead, the authors demonstrate that a verifier (CIVeX) that originally had zero false executions can suffer false execution rates up to 48.9%, with most of those executions being harmful and overall utility dropping dramatically. An additional attestation step that samples executions can detect these attacks with few false alarms, but it also leads to many wrongful rejections that reduce beneficial actions and incur significant experimental costs. whyItMatters":"The study shows that even minor errors in the verifier’s underlying graph can drastically undermine safety and performance, highlighting the need for robust auditing mechanisms."

By Fabio Rovai
agentsbenchmarkssafety
More like this →