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

Firas Bayram, Maxime Cordy

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…