When relations in graphs should be trusted or ignored
When Is a Relation Worth Trusting? Manipulation Costs, Exposure, and the Trust Trap in Multi-Relational Graph Learning
Machine LearningArtificial IntelligenceCryptography and Security
Summary
Graphs used in computer learning often include many types of connections (relations), but not all of these connections are equally reliable. This paper studies when it is better to ignore certain relations rather than trust them, especially if an attacker can manipulate them at different costs. The authors show that focusing on certain relations while considering manipulation costs can protect against attacks better than other methods. They provide tools and practical ways to decide which relations to trust or harden, even without detailed cost information.
What this means in practice
- •For platform security teams: Identify which graph relations to strengthen against attacks using cost-aware exposure measures to improve detection robustness.
- •For data scientists in social networks: Select trustworthy relations in multi-relational graphs when training detectors to reduce vulnerability to adversarial manipulation.
Authors
Vincess Dongmo, Astride Melvin Fokam Ninyim
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.