Feature-Context Consistency: Unsupervised Adversarial Detection with Drift Stability on Attributed Graphs

AI summary

Overview

Research area: Graph machine learning / adversarial detection on attributed graphs, combining energy-based models (Restricted Boltzmann Machines), unsupervised fraud and anomaly detection, and concept-drift robustness.

Technical level: Advanced. The paper pairs a closed-form detection score (Context Boost) with two worst-case theoretical guarantees (a separation theorem and a Wasserstein-Lipschitz drift bound) and evaluates on large attributed-graph benchmarks.

Scope: The paper proposes CB-RBM, a context-conditioned Gaussian-Bernoulli RBM whose Context Boost score detects injected adversarial nodes on attributed graphs with zero labels, while keeping its calibrated threshold stable under natural distributional drift.

What This Paper Is About

Detectors for fraud and abuse on attributed graphs face two compounding problems: adversarial entities are flagged late or never, so labels are missing exactly when detection matters most, and natural drift in user behavior and network topology slowly invalidates any decision boundary learned from a snapshot. The authors identify feature-context consistency — whether a node's own features align with the aggregated features of its neighbors — as a single structural signal that addresses both problems at once, because legitimate nodes develop correlated features and context through repeated interaction while freshly injected adversaries do not. They formalize this signal as the Context Boost score inside a Restricted Boltzmann Machine and validate it on Ethereum phishing and Reddit banned-user detection.

Key Contributions

1. Method. CB-RBM, a Gaussian-Bernoulli RBM extended with a GLU-gated context pathway that conditions the free energy on aggregated neighborhood features, plus the Context Boost (CB) score — the reduction in free energy attributable to context — as a label-free detection signal decomposable over hidden units in closed form.

2. Theoretical framework. Under five empirically verifiable assumptions, Theorem 1 proves a strict separation between the expected CB of legitimate and adversarial nodes, growing linearly in the number of hidden units n_h when the adversary's context stays far enough from legitimate neighborhood context; Theorem 2 and Corollary 2 prove a Wasserstein-Lipschitz bound on how far the CB distribution moves under natural drift, with Corollary 3 giving a worst-case horizon over which the legitimate mean stays above the midpoint threshold.

3. Detection boundary analysis. An effective adversarial correlation measure, ρ₁^eff, shows that CB detects absence of legitimate network context rather than feature deviation, characterizing what the signal fires on and delineating where it fails.

4. Empirical validation. With zero labels, CB-RBM achieves AUROC ≥ 0.96 on four attacks across XBlock (~153K Ethereum nodes) and Reddit (~11K nodes), and keeps FPR close to its calibrated 5% target under 20-step drift, outperforming supervised GNNs trained on hundreds of labels, unsupervised graph-anomaly baselines, and a standard RBM whose FPR rises to 89–100%.

Main Findings

• Separation on all four attack types. On XBlock, CB-RBM records AUROC / TPR@5%FPR of 99.9/100 (Isolated Injection), 99.9/100 (Feature Camouflage), 99.8/100 (Sybil) and 97.6/96.8 (Relation Camouflage). On Reddit it records 99.4/97.2, 99.6/98.2, 100/100 and 97.3/88.2 respectively. Across all four attacks on both datasets, CB-RBM maintains AUROC ≥ 96% and TPR@5%FPR ≥ 88% at zero labels.

• The standard RBM ablation collapses. Without the context pathway, Std-RBM falls to AUROC / TPR of 51.3/11.0 on XBlock Feature Camouflage and 52.4/4.3 on Reddit Feature Camouflage, and its FPR rises to 89–100% under drift.

• Supervised GNNs are undertrained in this regime. Despite a full label budget (932 / 166 labeled adversaries on XBlock / Reddit), the best Reddit supervised result is GAT at 67% TPR on Sybil, with GraphSAGE at 68.2/1.8 and GAT at 92.9/66.7 on Reddit Sybil.

• Unsupervised baselines do not transfer. CoLA drops from 84% to 17% TPR across datasets, and GAD-NR misses the self-consistent Sybil clique on XBlock entirely (0% TPR).

• Attack difficulty follows a measurable spectrum. Relation Camouflage — the only attack that links to real legitimate hubs — reaches the highest ρ₁^eff (0.51–0.64) and shows the steepest reduction of the squared separation gap, tracing a smooth monotonically decreasing curve against ρ₁^eff on both datasets, consistent with Theorem 1. Natural drift sits at ρ₁^eff ≈ 1 with a near-zero gap.

• Detection collapses past a camouflage threshold. The context-interpolation sweep drops detection below 50% once the camouflaging share exceeds α* ≈ 0.56 on XBlock and 0.58 on Reddit.

• Drift stability without retraining. CB-RBM maintains average Combined Score ≥ 0.87 at T=20 on both datasets. Reconstruction-based detectors collapse (DOMINANT drops to near zero on XBlock; GAE from 0.75 to 0.07 on Reddit). Supervised GNNs reach Combined Scores up to 0.84 (GraphSAGE) on XBlock but remain below 0.36 throughout on Reddit. At T=20 the strongest alternatives are GraphSAGE (0.84) and XGBGraph (0.81, with TPR 0.98 but drift FPR 17.8%) on XBlock and GAD-NR (0.63) on Reddit, against 0.94 and 0.88 for CB-RBM.

• Real temporal validation. Across five chronological XBlock windows from 2017 through 2018, with model, sign vector and threshold frozen on the earliest window, CB-RBM keeps legitimate-wallet FPR at or below 5%, reaching 3.1% by late 2018, and detects 100% of isolated injections built from real held-out phishing features. GAT and GraphSAGE detect 84–89% and 81%.

• Each ingredient is necessary. The RBM without context collapses under drift; the parameter-free signed-cosine score reaches only 0.17 and 0.57 Combined; Context-MLP reaches static AUROC of at least 0.95 on every Reddit attack yet raises 96% false alarms under drift.

• CB detects missing context, not feature deviation. Controlled decomposition shows legitimate features paired with random or absent context are flagged as reliably as adversarial features with random context (Combined ≥ 0.91), while legitimate features with legitimate context evade detection (Combined ≤ 0.11). An XBlock trace gives CB = 1046 for a median legitimate node, 952 after 20 drift steps, and 28 for an injected adversary.

• The certified tail bounds are loose but finite. The Chebyshev variance bound exceeds the measured Var[CB] by 8,300× on XBlock and 237,000× on Reddit, so detection is measured on full score distributions rather than predicted from the bounds. The drift bound is similarly conservative: observed CB shift at T=20 is smaller than the bound by 526× on XBlock and 4,540× on Reddit.

• Observed drift is mild but nonzero. At T=20, the empirical 95th percentile of legitimate scores shifts by 42.7 on XBlock and 3.4 on Reddit, while mean FPR at the frozen threshold reaches 6.1% and 7.1%.

• Assumption checks hold. The coherence parameter β₀ is 0.38 and 0.95 after training — 97 of 256 and 122 of 128 hidden units — against pre-training arcsine predictions of p₀ ≥ 0.30 on XBlock and 0.36 on Reddit.

• Stability across seeds. Over 3 seeds, CB-RBM's AUROC standard deviation is at most 0.1 points on XBlock and 1.2 on Reddit, and TPR at most 0.3 and 4.5 points. Over five seeds, the Combined Scores of XGBGraph, Graph Transformer, BWGNN and GDN vary with a standard deviation below 0.05.

Methodology in Plain English

The researchers start from an observation about how legitimate and fraudulent entities differ. A real wallet or user accumulates interactions over time, so its own attributes tend to line up statistically with the average attributes of its neighbors. An attacker can copy legitimate-looking features, but cannot control the features of the neighbors it links to. That asymmetry is the detection signal.

To turn it into a measurable score, the authors take a Restricted Boltzmann Machine — an energy-based model that learns what normal data looks like without any labels — and add a second input pathway for a node's neighborhood context, computed as the mean-pooled features of its neighbors with a per-dimension sign correction that flips anti-homophilic dimensions. A gating mechanism (a Gated Linear Unit) decides how much the context pathway contributes. The resulting Context Boost score is simply how much the neighborhood context reduces the model's free energy compared to using the node's features alone; because the feature-reconstruction term cancels in the subtraction, the score reflects only hidden-unit activation. Legitimate nodes score high, adversaries score near zero.

Training uses only a pool of assumed-legitimate nodes via Contrastive Divergence (CD-1), with no attack labels and no sparsity penalty. The detection threshold is set at the 95th percentile of the negated score on a held-out calibration slice of the same pool, giving a nominal 5% false-positive target.

For evaluation, the authors construct four injection attacks of increasing sophistication — Isolated Injection, Feature Camouflage, Sybil (a 50-node decoy clique with near-legitimate features), and Relation Camouflage (linking to the 10 highest-degree legitimate nodes) — and benchmark against six GADBench baselines, nine further detectors, and two ablations. Drift is simulated as a gradual random walk in feature space over 20 steps with context recomputed each step, plus a real chronological holdout across five XBlock windows from 2017 to 2018.

Why This Matters

The paper argues that what normally requires two separate engineering mechanisms — running without labels and staying calibrated under drift — here falls out of one structural regularity of the data. That is a notable simplification for practitioners, since the standard remedy for drift is periodic retraining, which loops back into the label-scarcity problem the retraining was meant to solve.

Real-world applications:

• Cryptocurrency fraud detection. The XBlock evaluation targets Ethereum phishing wallets, which the paper places in the context of $9.3 billion in cryptocurrency fraud in 2024, and demonstrates frozen-threshold detection of injections built from real held-out phishing features across 2017–2018 windows.

• Social platform abuse and ban evasion. The Reddit banned-user setting covers coordinated account abuse and platform manipulation, including Sybil-style attacks where attackers fabricate a clique of decoy accounts.

• E-commerce review fraud. YelpChi, evaluated in the appendix, represents coordinated fake-review rings, with Tolokers covering crowdsourcing anomalies in a third domain.

• Deployed systems with scarce labels. Any fraud team operating a model on a live graph where new accounts are not yet reported can apply the calibrated 5% threshold without retraining, since the paper's drift experiment keeps model, sign vector and threshold frozen.

Industry relevance: The detection pipeline runs at standard RBM cost — O(N · n_h · n_v) per epoch for training over N nodes and O(n_h · n_v) per node at inference — because the single-hop context is precomputed once and only closed-form free energies are evaluated. That makes the approach practical to deploy alongside or instead of supervised GNNs needing hundreds of labels.

Future Directions

• Quantile-level drift guarantees. Corollary 2 controls score quantiles on average but not the 95th percentile pointwise; Appendix I.2 measures this directly, and closing that gap is an open theoretical problem.

• Harder camouflage and adaptive adversaries. The paper shows detection drops below 50% once the camouflaging share exceeds roughly 0.56 (XBlock) and 0.58 (Reddit), and that an adversary acquiring genuine network connections eventually restores the correlation signal. White-box PGD is treated as a stress test in Appendix H, and training-time graph or label manipulation (topology poisoning, backdoor attacks) lies explicitly outside scope.

• Robustness to contaminated training pools. The assumed-legitimate pool is only assumed legitimate — Section 6.5 evaluates robustness to adversarial contamination, and refining that assumption is a natural extension.

• Refreshing the sign vector under corruption. The sign vector is fitted once from feature statistics alone and kept fixed; Appendix E.2 shows that re-estimating it on a new unlabeled window restores calibration after sign corruption, suggesting a cheap periodic maintenance procedure.

• Generalist and cross-graph transfer. The paper positions its shift as temporal drift within one deployed graph, distinct from generalist detectors like ARC, UNPrompt and AnomalyGFM that transfer across graphs, leaving cross-graph generalization open.

Target Audience

Researchers and graduate students working on graph anomaly detection, adversarial machine learning on graphs, and concept drift; practitioners building fraud, abuse or phishing detection systems on attributed graphs who lack timely labels; and readers interested in energy-based models and closed-form theoretical guarantees for unsupervised detection, particularly those who want to understand when a detection signal will and will not transfer across datasets.

Authors’ abstract

Adversarial detection on evolving attributed graphs faces two challenges: fraud labels arrive late or not at all, and natural distributional drift erodes any trained decision boundary. Modern detectors can reach strong detection rates when labels are available and the distribution is stationary; sustaining that quality without labels and under drift is the open problem. We identify feature-context consistency -- the alignment between a node's attributes and its aggregated neighborhood attributes -- as a single structural signal that addresses both. We formalize it as the Context Boost (CB) score within a Restricted Boltzmann Machine framework (CB-RBM) and prove two complementary worst-case guarantees: a strict separation between the expected CB of legitimate and adversarial nodes, with gap growing linearly in model capacity, whenever the adversary's context stays far enough from legitimate neighborhood context; and a Wasserstein-Lipschitz bound on how far the CB distribution moves under natural drift. We validate on XBlock Ethereum phishing (~153K nodes) and Reddit banned-user detection (~11K nodes), with two further datasets in the appendix spanning diverse domains. With zero labels, CB-RBM achieves AUROC >= 0.96 on four adversarial attacks and keeps FPR close to its calibrated 5% target under drift -- outperforming supervised GNNs (hundreds of labels), unsupervised graph-anomaly baselines, and a standard RBM whose FPR collapses to 89-100%. What typically requires separate mechanisms -- label-free operation and drift stability -- here follows from a single structural regularity of the data. Code: https://github.com/serval-uni-lu/CB-RBM.