Optimal Transport-Guided Adversarial Attacks on Graph Neural Network-Based Bot Detection

AI summary

Overview

Research area: Adversarial machine learning on graphs, specifically attacks against Graph Neural Network-based social bot detectors, using optimal transport (OT) theory.

Technical level: Advanced. The paper assumes familiarity with Graph Neural Networks, semi-supervised node classification, adversarial evasion attacks, and optimal transport / Sinkhorn algorithms.

Scope: The paper introduces BoCloak, a framework that uses entropic optimal transport over spatio-temporal neighborhood distributions to craft sparse, realistic edge edits and node injections that help bots evade GNN-based detection under real-world deployment constraints.

What This Paper Is About

GNN-based bot detectors perform well in controlled benchmarks, but real attackers face limits that classic graph attacks ignore: they can't rewire arbitrary users, force humans to follow back, or probe the whole graph. BoCloak reframes bot evasion as a geometry problem — it learns an optimal transport metric that separates human from bot neighborhoods, then transforms a bot's local neighborhood into something that looks human using a small number of plausible edge edits. The goal is to attack bot detectors realistically (black-box, budget-limited, temporally consistent) while remaining computationally lightweight.

Key Contributions

1. First use of optimal transport in social bot detection and adversarial attacks on GNNs. The authors recast evasion as aligning neighborhood distributions in a learned OT geometry rather than flipping individual edges.

2. A learnable, constraint-aware OT geometry. The ground cost between neighbor feature vectors is trained with a multi-term loss (BCE margin, sparsity, plausibility) so that decoded transport plans naturally yield sparse, socially realistic edits.

3. Strong evasion under both constrained and unconstrained settings. BoCloak achieves up to 80.13% higher attack success rates than leading baselines across three datasets and five detectors, while bypassing three defenses (GNNGuard, GRAND, RobustGCN).

4. Dramatic efficiency gains. The method uses up to 99.80% less GPU memory than PR-BCD and FGA, and runs up to 20× faster than Nettack and GOttack, all without gradient access or model-specific tuning.

Main Findings

• SOTA detectors are fragile. As shown in Figure 1, a single human follower can mislead a BotRGCN detector in 81.50% of cases — misclassified bots disproportionately have edges to human accounts, especially incoming follows.

• BoCloak dominates baselines. Across Cresci-15, TwiBot-22, and BotSim-24, BoCloak achieves attack success rates in the 88–99% range on constrained attacks, while Nettack, FGA, PR-BCD, and GOttack collapse to single-digit or low-double-digit success under the same constraints.

• Constrained attacks nearly match unconstrained ones. BoCloak's constrained success (e.g., 93.10% on GAT/Cresci-15) is only marginally lower than its unconstrained success (95.25%), unlike baselines that drop dramatically.

• Defenses are largely bypassed. GNNGuard, GRAND, and RobustGCN reduce BoCloak's success only modestly (usually within a few percentage points), whereas these defenses crush baseline attacks on constrained settings.

• Cross-dataset variation exists. On BotSim-24 with BotRGCN, BoCloak's success drops to around 52–58%, suggesting LLM-generated bots create harder evasion scenarios for some architectures.

• Efficiency is a headline result. OT distance computation depends only on local ego-neighborhood size (O(T·m·n) per Sinkhorn solve), not on the full graph size, enabling scaling to TwiBot-22 (1M nodes, 170M edges).

• Bot cloaks beat human cloaks. Using misclassified bots as templates works better than mimicking humans, because bots preserve engagement-oriented connections while still evading detection.

Methodology in Plain English

The core idea is to compare neighborhoods, not edges. Each account is represented as a probability distribution over the features of its neighbors, where each neighbor's weight combines a structural score (how informative the connection is) and a temporal score (how plausible the timing is). Bot and human neighborhoods form different clouds in this feature space.

BoCloak then learns a cost function — a neural embedding plus a positive-semidefinite matrix — such that transporting one neighborhood's mass to another is cheap if they behave similarly. Training uses three losses: a margin loss that pushes humans and bots apart, a sparsity loss that keeps transport plans concentrated, and a plausibility loss that discourages degree or timing violations.

To attack a target bot, BoCloak finds "cloak templates": bots near the decision boundary that the detector already misclassifies as human. It then solves a Sinkhorn optimal transport problem between the template's neighborhood and a nearby human's neighborhood, extracting the highest-mass correspondences as concrete edge edits. These edits obey hard constraints: a per-target edge budget, only edges incident to the target bot, no forced human-to-bot follow-backs, direction validity, and temporal consistency. The attacker operates black-box, using only the graph and labels, never model gradients or logits. Node injection is treated as editing where the target starts with no edges.

Why This Matters

Impact on research. The paper connects optimal transport to adversarial graph learning in a domain-grounded way, showing that geometry-aware attacks can be both more effective and orders of magnitude cheaper than gradient- or search-based methods. It also exposes how brittle current bot detectors are, which should push the community toward robustness benchmarks that include realistic constraints.

Real-world applications:

• Platform trust and safety teams can use BoCloak-style analyses to red-team their own detection pipelines before deployment.
• Adversarial robustness auditing of any GNN deployed on user-interaction graphs (recommendation, fraud, spam) — the OT framework is domain-agnostic.
• Reduced infrastructure cost for red-teaming. Because the attack needs no gradients and minimal GPU memory, smaller teams can run large-scale robustness tests.
• Synthetic bot simulation for defense training. Cloak templates provide realistic evasive bot samples for training more robust detectors.

Industry relevance. Large platforms (X, Meta, TikTok, Reddit) run GNN-adjacent detection at scale. A black-box, low-cost evasion method is directly relevant to threat modeling, and the paper's constraint formulation — no forced follow-backs, temporal plausibility — matches how real bot operators actually work.

Future Directions

• Adaptive defenses. The paper evaluates non-adaptive defenses; designing OT-aware defenses that anticipate distribution-matching attacks is a natural next step.

• LLM-driven bots. BotSim-24's lower BoCloak success rates on some architectures suggest that generative bots with richer profiles may need different transport geometries or feature encodings.

• Scalability beyond ego-neighborhoods. Extending the OT formulation to multi-hop or community-level constraints could broaden applicability, at the cost of larger transport problems.

• Certified robustness. The margin m(v) = d_hum(v) − d_bot(v) is a natural candidate for provable evasion certificates — quantifying how many edits are needed to flip a prediction.

Target Audience

This paper is aimed at adversarial machine learning researchers, GNN robustness practitioners, and trust-and-safety engineers working on social platform abuse detection. It also suits graduate students comfortable with optimal transport and graph neural networks who are interested in security applications. Readers without a background in Sinkhorn algorithms or semi-supervised node classification will need to consult the cited background works before the methodology section fully clicks.

Authors’ abstract

The rise of bot accounts on social media poses significant risks to public discourse. To address this threat, modern bot detectors increasingly rely on Graph Neural Networks (GNNs). However, the effectiveness of these GNN-based detectors in real-world settings remains poorly understood. In practice, attackers continuously adapt their strategies as well as must operate under domain-specific and temporal constraints, which can fundamentally limit the applicability of existing attack methods. As a result, there is a critical need for robust GNN-based bot detection methods under realistic, constraint-aware attack scenarios. To address this gap, we introduce BOCLOAK to systematically evaluate the robustness of GNN-based social bot detection via both edge editing and node injection adversarial attacks under realistic constraints. BOCLOAK constructs a probability measure over spatio-temporal neighbor features and learns an optimal transport geometry that separates human and bot behaviors. It then decodes transport plans into sparse, plausible edge edits that evade detection while obeying real-world constraints. We evaluate BOCLOAK across three social bot datasets, five state-of-the-art bot detectors, three adversarial defenses, and compare it against four leading graph adversarial attack baselines. BOCLOAK achieves up to 80.13% higher attack success rates while using 99.80% less GPU memory under realistic real-world constraints. Most importantly, BOCLOAK shows that optimal transport provides a lightweight, principled framework for bridging the gap between adversarial attacks and real-world bot detection.