多关系图学习中的信任陷阱：操纵成本、暴露度与关系何时可信
When Is a Relation Worth Trusting? Manipulation Costs, Exposure, and the Trust Trap in Multi-Relational Graph Learning
AI 导读
arXiv 预print研究分析多关系图检测器在对抗操纵下何时该信任某条关系。理论证明，当部分节点被隔离在某关系上且攻击者无力打开门槛时，degree gating 严格优于任何选择或重加权；基于每节点暴露度上界的指标可在 16 例中的 15 例中选出加固后最能提升陷阱阈值的关系，优于信息量、成本或等编辑成本分析的至多 7 例。
正文 · 原文
Abstract:Multi-relational graph detectors learn from clean data how much to trust each relation, but an adversary pays a different price to manipulate each relation and each action; taking such costs as given, we ask when using a relation is worse than ignoring it. Our first main result proves that degree gating strictly beats every selection or reweighting of a relation when part of the population is isolated on it and the attacker cannot afford to open the gate, and that this window is sharp; on real graphs, validated gating gains exactly on the relations that meet these conditions and nowhere else. Our second shows that a per-node exposure bound, which extends to message passing, tells a platform which relation to harden: exposure per unit cost, computed without any attack, picks the relation whose hardening raises the exact trap threshold most in 15 of 16 cases, against at most 7 for informativeness, cheapness, or an analysis with equal edit costs. Supporting tools give exact worst cases for linear relational models, certified brackets for R-GCN and tree ensembles, and a finite-sample guarantee for adversarial validation, under which clean-trained graph detectors fall below their graph-free counterparts in 58 of 90 settings on six graphs. A selection protocol built on these results is never significantly worse than ignoring the graph; with at most four relations it mostly abstains, as validation alone would, and its cost-aware proposals help when relations are many, so far shown on synthetic graphs. Without cost information, the safe choice is to abstain.
| Comments: | Preprint. October 27, 2026 |
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Cryptography and Security (cs.CR) |
| Cite as: | arXiv:2610.37239 [cs.LG] |
| (or arXiv:2610.37239v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.37239 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Astride Melvin Fokam Ninyim [view email]
[v1]
Tue, 27 Oct 2026 13:43:56 UTC (861 KB)
来源：arXiv cs.AI · arxiv.org