arXiv cs.AI· Vincess Dongmo, Astride Melvin Fokam Ninyim·· 13 小时前AI 评分24
多关系图学习中关系何时值得信任？操纵成本、暴露度与信任陷阱
When Is a Relation Worth Trusting? Manipulation Costs, Exposure, and the Trust Trap in Multi-Relational Graph Learning
AI 导读
研究提出多关系图检测器中的“信任陷阱”：当部分节点在某一关系上被孤立、攻击者又无力打开门控时，度门控严格优于对该关系的任何选择或重加权，且该窗口是紧的。每节点暴露度上界可指导平台选择加固哪条关系，按单位成本暴露度选出的关系在 16 个案例中有 15 个最能提升陷阱阈值。在六张图的 90 个设置中，干净训练的图检测器有 58 个不如无图基线；缺乏成本信息时，安全做法是弃用该关系。
正文 · 原文
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