Degree gating outperforms any relation selection when attacker cannot afford to open the gate

The five-minute version

Degree gating outperforms any selection or reweighting of a relation when some nodes are isolated on that relation and the attacker cannot afford to open the gate, and a per-node exposure bound reliably identifies which relation to harden, succeeding in 15 of 16 cases. The paper validates these claims on a synthetic CSBM (N=6000) and five real-world graphs, showing that clean-trained graph detectors fall below graph-free baselines in 58 of 90 settings and that adversarial training does not eliminate the trust trap. Evidence is strong where the theoretical conditions hold, but the overall picture shows many scenarios where relations remain unsafe.

What they found 3

• Degree gating strictly beats selection and reweighting when part of the population is isolated and the attacker cannot open the gate

  “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”

• Exposure per-unit-cost identifies the best relation to harden in 15 of 16 cases

  “exposure per unit cost, computed without any attack, picks the relation whose hardening raises the exact trap threshold most in 15 of 16 cases”

• Clean-trained graph detectors fall below graph-free counterparts in many settings

  “clean-trained graph detectors fall below their graph-free counterparts in 58 of 90 settings on six graphs”

What undercuts it the paper’s own results

• clean-trained graph models fall below their graph-free counterparts in 58 of 90 (dataset, model, cell) combinations and lose up to .906 AUC
• adversarial training at the evaluated costs does not remove the trap

Stated limits 2

• All of this is conditional on specified costs: the paper studies selection under given cost scenarios, not real manipulation costs (Section C).
• Without cost information, the safe choice is to abstain.

What’s new here 4

• Degree gating is proven to strictly dominate selection and reweighting under isolation and cost constraints.
• A per-node exposure bound is introduced to rank relations for hardening without needing an attack.
• The CARS-D protocol combines theoretical candidates with adversarial validation to safely select or abstain from using relations.
• Certified AUC brackets for R-GCN and tree ensembles and a finite-sample guarantee for adversarial validation are provided.

Artifacts & methods 7

• degree gatingprimitive
• exposure boundtheory
• CARS-D protocolsystem
• R-GCNsystem
• relational logistic regressionprimitive
• contextual stochastic block model (CSBM)dataset
• real-world graphs (YelpChi, Amazon, etc.)dataset

Topics