Sybil Detection using Graph Neural Networks

Source: arXiv:2409.08631 · Published 2024-09-13 · By Stuart Heeb, Andreas Plesner, Roger Wattenhofer

TL;DR

This paper asks whether graph neural networks can do structure-only Sybil detection better than the classic random-walk / belief-propagation family when the attacker adds many attack edges or uses targeted attachments. The core proposal, SYBILGAT, is a graph attention network that learns neighbor weights rather than treating all neighbors equally, with the motivation that Sybil edges should not influence every node in the same way. The paper is explicitly framed as a security setting: the model gets only graph structure plus a small labeled seed set of known honest and Sybil nodes, and it is evaluated under both synthetic and real social-network graphs.

The main result is that SYBILGAT is competitive or better than the strongest structure-only baselines, but its advantage depends a lot on graph type, depth, and attack pattern. On the Twitter graph, the best reported SYBILGAT variant reaches AUC 0.8489 versus 0.8022 for SYBILSCAR in the sampled-subgraph pretraining experiment. On other settings, especially highly connected real-region Facebook-based graphs, shallow models often win and deeper ones can collapse badly. The paper’s more interesting takeaway is not “GATs always win,” but rather that attention can help when the graph is sufficiently hard or heterogeneous, while depth can become a liability when the local neighborhood already contains strong signal or when the synthetic setup mismatches the architecture’s assumptions.

Key findings

• On the Twitter dataset in Experiment 1, SYBILGAT-L4 achieved AUC 0.8489 versus SYBILSCAR’s 0.8022, a +0.0467 absolute gain.
• On the Facebook-based synthesized graph in Experiment 1 with random attack edges, SYBILGAT-L2 reached AUC 0.7479 versus SYBILSCAR’s 0.6265, a +0.1214 gain.
• On the same Facebook-based Experiment 1 graph with targeted attack edges, SYBILGAT-L2 reached AUC 0.7739 versus SYBILSCAR’s 0.5029, a +0.2710 gain.
• In the fully synthesized power-law graphs of Experiment 1, SYBILGAT-L2 scored AUC 0.6219 on 10,000 nodes and 0.6237 on 50,000 nodes, while SYBILSCAR stayed at 0.5574 and 0.5565 respectively.
• In Experiment 2 (BA-BA, random attack edges), SYBILGAT-L8 achieved AUC 0.8589 versus SYBILSCAR’s 0.6740.
• In Experiment 2 (PL-FB, random attack edges), SYBILGAT-L2 achieved AUC 0.7682 versus SYBILSCAR’s 0.6458, but deeper variants degraded to 0.6105 (L4) and 0.4746 (L8).
• In Experiment 3 on the Facebook-based synthesized network, SYBILGAT-L2 reached AUC 0.7669 versus SYBILSCAR’s 0.6422, while SYBILGAT-L8 dropped to 0.4690, showing strong depth sensitivity.
• The paper reports five runs per experiment with seeds [42, 43, 44, 45, 46], and uses AUC as the primary metric throughout the main experiments.

Threat model

The adversary is a Sybil operator who controls malicious nodes in the graph and can create attack edges between Sybil and honest regions, either uniformly at random or in a targeted manner aimed at known honest nodes or their neighborhood. The attacker is assumed to know the graph structure they can influence and can choose cross-region attachment strategies, but the defender still has access to a small seed set of known honest and Sybil labels and to the full observed graph structure. The paper does not assume the attacker can manipulate the learning procedure directly, poison the labeled seed set arbitrarily, or use non-structural side channels; the evaluation is limited to structure-based detection under edge-placement attacks.

Methodology — deep read

Threat model and assumptions: the adversary is a Sybil attacker that can create malicious nodes and connect them to honest users through attack edges. The defender is allowed only structural information from the graph plus a small set of known labels; the paper explicitly avoids content, profile, or behavioral features. The social network is modeled as two regions, honest H and Sybil S, with cross-region attack edges E_T. The default label budget is small: 5% of each original class for training unless otherwise stated. The paper assumes undirected graphs for most experiments, even though the underlying Twitter data is directed, because much prior Sybil work evaluates undirected structure and because the authors want comparability.

Data provenance and splits: the paper uses one real labeled Twitter graph and one unlabeled Facebook graph from SNAP. Twitter is the main real-world dataset: 269,640 nodes and 6,818,501 edges, originally crawled from Twitter/X and later retroactively labeled by querying account status over time; the paper cites Lu et al. 2023 for processing. The Facebook graph has 4,039 nodes and 88,234 edges and is used as a real structural region for synthetic composition, not as a labeled evaluation target. Because fully labeled real Sybil datasets are scarce, the authors also synthesize social networks by combining honest and Sybil regions taken either from real graphs or from random graph generators. They use Forest Fire sampling (via little-ball-of-fur) to create subgraphs for pretraining. In the Twitter pretraining experiment, the sampled subgraph is 5% of the initial graph; for most other sampled-subgraph experiments it is 10%. For the Twitter graph, the known training labels are 11.2% of honest nodes and 10.9% of Sybil nodes, following Lu et al. 2023. Each experiment is repeated five times with seeds 42 through 46, and results are averaged.

Graph synthesis and attack construction: the paper builds two-region graphs by making the honest and Sybil regions internally dense and then adding attack edges between them. The synthetic region generators are Barabási–Albert (BA) with m=6, and power-law graphs (PL) with m=6, p=0.8. Attack edges are either random or targeted. Random placement chooses endpoints uniformly between H and S. Targeted placement uses a target set TH and TS; unless otherwise stated, TH is the known honest training set and TS is the full Sybil set, so the attacker preferentially connects Sybils to known honest nodes or nearby nodes. Targeted attacks are parameterized by p_T, the probability that an attack edge is targeted rather than random, and by a discrete distribution over hop distance from the target set, e.g. p=[1/4,1/4,1/2] in one experiment or p=[1/2,1/2] in another. The paper measures attack density as attack edges per Sybil. Concrete examples: in Experiment 1, the Facebook-based synthetic network is built with 20 random attack edges per Sybil, or with p_T=0.1 and distance PDF [1/4,1/4,1/2]; in the fully synthetic power-law setting it uses 8 random attack edges per Sybil; in Experiment 3 the targeted-attack setting uses p_T=0.2 and p=[1/2,1/2].

Architecture and algorithm: SYBILGAT is a multi-layer GATConv model implemented with torch-geometric. The input width can be 1 or 2; the authors found 1 channel, interpreted as a scalar “Sybil-ness” feature, was conceptually simpler and at least as effective. Hidden width and attention-head count were both set to 4 in the robust evaluation described in the paper. The model stacks GATConv layers: the first layer maps I inputs to H outputs with N heads; intermediate layers take H·N inputs and produce H outputs with N heads; the last layer maps H·N to O outputs with one head. Dropout of 0.5 is applied before each layer, tanh after each layer, and the final activation is sigmoid for one output channel or softmax for two. This is not a novel GAT operator; the novelty is the application of attention to Sybil detection plus the training/evaluation protocol under structural attack scenarios.

Training, thresholding, and evaluation: training uses Adam with binary cross entropy for one-output models and cross entropy for two-output models. The known labels are split into train and validation subsets; the paper states a default 0.8/0.2 split for training and an additional 0.9/0.1 split for inference/threshold estimation, but the exact interaction of these two splits is not fully clear from the text. Early stopping is based on validation loss with a configurable patience value, and the best validation checkpoint is used for testing. Before inference, a classification threshold is chosen using the validation subset of known nodes. The main metric is AUC, and the main baselines are SYBILRANK, SYBILBELIEF, and especially SYBILSCAR-D; the paper also evaluates SYBILRANK and SYBILBELIEF in the final robustness section. For SYBILSCAR, the authors reimplemented the matrix-form algorithm with sparse operations and say it matches the public C++ implementation up to numerical differences. One concrete end-to-end example is the Twitter sampled-subgraph experiment: they forest-fire sample a 5% subgraph, pretrain SYBILGAT on that subgraph using the known labels, stop early when validation loss stops improving, estimate a threshold from held-out known nodes, and then score the remaining graph only on the unseen nodes. The reported best model is SYBILGAT-L4 with AUC 0.8489.

Reproducibility and reporting: the paper provides dataset identities, graph sizes, attack-edge configurations, model depths, repeated-seed evaluation, and baseline implementation details, but the excerpt does not indicate a public code release or frozen model checkpoints. The appendix is said to contain full tables for all algorithms, but the provided text only exposes selected tables and the narrative around them. The text also leaves some implementation details underspecified, such as the exact optimizer hyperparameters, patience value, learning rate, number of epochs, and whether the train/validation split is stratified by class in every experiment. Those gaps matter because the observed performance swings with depth are large, especially on the Facebook-based graphs.

Technical innovations

• Applies Graph Attention Networks to structure-only Sybil detection, replacing uniform neighbor aggregation with learned neighbor weighting under attack-edge uncertainty.
• Introduces a pretraining-on-subgraph workflow for Sybil detection: train on a sampled or smaller synthetic graph, then transfer to a larger disjoint evaluation graph.
• Evaluates both random and targeted attack-edge placement with explicit hop-distance distributions, instead of only random cross-region edges as in much prior work.
• Shows that shallow GATs can outperform stronger structure-only baselines on large labeled Twitter data and some synthetic regimes, but deeper GATs can fail sharply on highly connected real-region graphs.

Datasets

• Twitter — 269,640 nodes, 6,818,501 edges — crawled Twitter graph processed/labeled by Lu et al. 2023; originally from Kwak et al. 2010
• Facebook — 4,039 nodes, 88,234 edges — SNAP; used as a structural region for synthetic social networks
• Forest Fire sampled Twitter subgraph — 5% of the Twitter graph for pretraining — sampled with little-ball-of-fur
• Forest Fire sampled synthetic subgraphs — 10% of initial graph for most experiments — generated from BA/PL or real-region graphs
• BA synthetic graphs — 2,000 or 20,000 nodes in pretraining experiments; 10,000 and 50,000 nodes in robustness experiments — networkx generator
• Power-law synthetic graphs — 2,000 or 20,000 nodes in pretraining experiments; 10,000 and 50,000 nodes in robustness experiments — networkx generator

Baselines vs proposed

• SYBILSCAR vs SYBILGAT-L4 on Twitter (Experiment 1): AUC = 0.8022 vs proposed: 0.8489
• SYBILSCAR vs SYBILGAT-L2 on Facebook synthetic, random attacks (Experiment 1): AUC = 0.6265 vs proposed: 0.7479
• SYBILSCAR vs SYBILGAT-L2 on Facebook synthetic, targeted attacks (Experiment 1): AUC = 0.5029 vs proposed: 0.7739
• SYBILSCAR vs SYBILGAT-L2 on fully synthesized 10,000-node PL graph (Experiment 1): AUC = 0.5574 vs proposed: 0.6219
• SYBILSCAR vs SYBILGAT-L2 on fully synthesized 50,000-node PL graph (Experiment 1): AUC = 0.5565 vs proposed: 0.6237
• SYBILSCAR vs SYBILGAT-L8 on BA-BA, random attacks (Experiment 2): AUC = 0.6740 vs proposed: 0.8589
• SYBILSCAR vs SYBILGAT-L2 on PL-FB, random attacks (Experiment 2): AUC = 0.6458 vs proposed: 0.7682
• SYBILSCAR vs SYBILGAT-L2 on Facebook-based synthetic network (Experiment 3): AUC = 0.6422 vs proposed: 0.7669

Limitations

• The strongest results are highly architecture- and dataset-dependent: deep SYBILGAT variants sometimes collapse below the baselines, especially on the Facebook-based synthetic graphs.
• The work relies heavily on synthetic social-network construction, which may not preserve all properties of real attacker behavior or real platform graph dynamics.
• Only structural information is used, so the method is intentionally blind to content, account metadata, timing, and other signals that are often available in practice.
• The excerpt does not specify key training hyperparameters such as learning rate, epoch count, or patience value, which makes exact replication harder.
• The train/validation/inference split description is somewhat ambiguous in the text, especially the interaction between the 0.8/0.2 and 0.9/0.1 splits.
• There is no adversarially adaptive attacker evaluation beyond the targeted-edge placement model; the paper does not show a closed-loop attacker that reacts to the learned detector.

Open questions / follow-ons

• How well does SYBILGAT hold up under adaptive attackers that optimize edge placement against the learned attention mechanism rather than using fixed random/targeted heuristics?
• Can the model be made more stable across graph regimes, for example by controlling over-smoothing/over-squashing or by using depth-adaptive normalization?
• Would training on multiple source graphs or multiple sampled subgraphs improve transfer to unseen real networks compared with single-subgraph pretraining?
• How sensitive are the results to label noise in the known honest/Sybil seed sets, which is a major issue in operational Sybil defense?

Why it matters for bot defense

For bot-defense practitioners, the paper is useful as a graph-only detection baseline: it shows that learned neighbor weighting can outperform classic propagation methods when bots/Sybils create many cross-community edges or when the graph is structurally noisy. The main practical lesson is not to assume that deeper message passing is better; on some network regimes, shallow attention models were materially stronger than deeper ones. That matters if you are building account-risk systems around social graphs, referral graphs, contact graphs, or invite graphs, because a simple propagation baseline may fail once attackers deliberately increase connectivity to blend into the honest region. At the same time, the paper’s dependence on synthetic evaluation and seed labels means an engineer should treat the reported gains as a starting point for validation, not as proof of deployment readiness. In a captcha or bot-defense stack, I would read SYBILGAT as a structure-only scoring component that could complement, not replace, content or behavioral signals when those signals are available and trustworthy.

Cite

@article{arxiv2409_08631,
  title={ Sybil Detection using Graph Neural Networks },
  author={ Stuart Heeb and Andreas Plesner and Roger Wattenhofer },
  journal={arXiv preprint arXiv:2409.08631},
  year={ 2024 },
  url={https://arxiv.org/abs/2409.08631}
}

Read the full paper

• arXiv:2409.08631 (abstract)
• arXiv:2409.08631 (PDF)