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

📄 arXiv: 2610.37239v1 📥 PDF

作者: Vincess Dongmo, Astride Melvin Fokam Ninyim

分类: cs.LG, cs.AI, cs.CR

发布日期: 2026-10-27

备注: Preprint. October 27, 2026

💡 一句话要点

提出多关系图学习中的信任陷阱解决方案

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 多关系图学习 信任机制 攻击防范 度门控 曝光成本 网络安全 社交网络分析

📋 核心要点

  1. 现有的多关系图学习方法在面对攻击时，难以有效评估和选择信任的关系，导致潜在的信任陷阱。
  2. 论文提出了一种基于度门控的选择机制，能够在特定条件下优于传统的选择或重加权方法，确保更高的安全性。
  3. 实验结果显示，基于曝光成本的选择协议在16个案例中有15个成功提高了阈值，且在58个设置中，清洁训练的图检测器表现不如图无关的对比方法。

📝 摘要（中文）

多关系图检测器从干净数据中学习如何信任每个关系，但攻击者对每个关系和每个动作的操控成本不同。本文首先证明，当部分群体在某个关系上孤立且攻击者无法打开门时，度门控严格优于任何选择或重加权关系。其次，提出的每节点曝光界限扩展到消息传递，帮助平台选择需要加固的关系。实验表明，基于这些结果的选择协议在大多数情况下表现优于忽略图结构，尤其在关系较多时更为有效。

🔬 方法详解

问题定义：本文旨在解决多关系图学习中，如何在攻击者操控成本不同的情况下评估和选择信任的关系。现有方法在面对复杂的攻击场景时，往往无法有效判断哪些关系值得信任，导致信任陷阱的出现。

核心思路：论文提出了一种基于度门控的选择机制，能够在特定条件下优于传统的选择或重加权方法。通过分析攻击者的操控成本，确定在何种情况下使用某个关系的风险高于忽略它的风险，从而提高系统的安全性。

技术框架：整体架构包括数据输入、关系选择、度门控机制和结果输出四个主要模块。首先，系统接收多关系图数据，然后通过度门控机制评估每个关系的信任度，最后输出选择的关系和相应的安全性评估。

关键创新：最重要的技术创新点在于度门控机制的引入，它能够在特定条件下有效隔离攻击者，确保选择的关系在安全性上优于其他方法。与现有方法相比，度门控提供了一种更为精确的信任评估方式。

关键设计：在设计中，采用了每节点曝光界限的计算方法，结合消息传递机制，确保在没有攻击的情况下也能有效评估关系的安全性。此外，论文还提供了线性关系模型的最坏情况分析和R-GCN及树集成的认证区间。

📊 实验亮点

实验结果显示，基于曝光成本的选择协议在15个案例中成功提高了阈值，且在58个设置中，清洁训练的图检测器表现不如图无关的对比方法，验证了所提方法的有效性和优势。

🎯 应用场景

该研究的潜在应用领域包括社交网络分析、金融欺诈检测和网络安全等。通过提高多关系图学习的安全性，能够有效防范针对图结构的攻击，提升系统的整体鲁棒性和信任度，具有重要的实际价值和未来影响。

📄 摘要（原文）

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.