FuSST: Behavioural-Graph Fusion and a Homophily Diagnostic for Sybil Detection

Abstract

Online social networks assume that each account corresponds to a unique person. A Sybil attack breaks that assumption: one adversary creates and controls many accounts at once. Together, these accounts can sway votes or inflate the reputation scores that a platform assumes come from distinct people. Two complementary signals for spotting them are the graph of connections between accounts and how an individual account behaves over time.

We propose FuSST, a lightweight detector that combines these two signals. It builds a structural graph of social connections and a behavioural graph that links accounts acting alike over time. It then marks a few accounts already known to be fake or genuine and spreads those labels across both graphs at once to classify the rest. We find that this propagation of labels across graphs only helps when the graph is homophilic, that is, when accounts of the same kind cluster together. Hence, we also add a test that predicts, before the detector runs, whether the structural graph will help at all.

We evaluate FuSST on five public benchmarks that range from strongly structured to almost structureless. We find that where homophily is present, FuSST reaches up to 0.995 AUC and outperforms either graph individually. For cases where homophily is absent, our proposed test correctly predicts that the graph cannot help. We also analyse the potential limitations of FuSST when compared against heavyweight detectors and note its reliance on activity timestamps.