Unsupervised Social Bot Detection via Structural Information Theory

Hao Peng, Jingyun Zhang, Xiang Huang, Zhifeng Hao, Angsheng Li, Zhengtao Yu, Philip S. Yu

TL;DR

UnDBot is a new unsupervised framework that detects social bots by analyzing the "essential structure" of social networks using structural information theory. By clustering users based on behavioral similarities rather than just direct interactions, it achieves high detection accuracy and provides clear, interpretable reasons for its classifications without requiring any labeled training data.

What Problem Does This Paper Address?

Social bots are increasingly sophisticated, often mimicking human behavior to spread misinformation or manipulate public opinion. Most current detection methods fall into two traps:

  1. The Labeling Bottleneck: Supervised models (like GNNs or Transformers) require massive amounts of labeled data, which is expensive to produce and quickly becomes obsolete as bot tactics evolve.
  2. The Black Box Problem: Deep learning models are often "black boxes," making it difficult for researchers to understand why an account was flagged as a bot.

Furthermore, bots have become experts at "camouflaging" themselves by interacting with real humans. Traditional graph-based methods that only look at direct links (follows, mentions) often fail to distinguish these "infiltrator" bots from genuine users.

Methods

The authors introduce UnDBot, which operates in three distinct phases:

  1. Multi-relational Graph Construction: Instead of just mapping who follows whom, UnDBot builds a graph where edges represent similarity in three key behaviors:
  2. Posting Type Distribution: The ratio of original tweets vs. retweets vs. comments.
  3. Posting Influence: The average engagement (likes, shares) a user receives.
  4. Follow-to-Follower Ratio: A classic indicator of automated "follow-back" schemes.
  5. User Community Division (Structural Entropy): The core innovation uses structural information theory. It treats the graph as a source of information and seeks to find an "encoding tree" that minimizes the graph's structural entropy. This process hierarchically clusters users into communities where members have the most "stable" and "certain" relationships with one another.
  6. Community Binary Classification: To decide if a cluster is "bot" or "human," the model calculates:
  7. Community Influence: Using a stationary distribution (via random walks) to see how central the community is.
  8. Community Cohesion: Using entropy to measure how tightly packed the behaviors are within the group.
  9. Bots typically form dense, highly cohesive clusters with specific influence patterns, which UnDBot identifies using a combined evaluation score.

Datasets

The researchers evaluated UnDBot on four real-world Twitter (X) datasets:

  • Cresci-2015 & Cresci-2017: Standard benchmarks containing a mix of benign users and various bot types (fake followers, social spambots).
  • Pronbots-2019 & Botwiki-2019: Originally bot-heavy datasets, which the authors augmented with additional human accounts and tweets to create a more realistic, imbalanced environment for testing.

Key Insights and Ideas

  • Behavioral Commonality over Direct Interaction: The "aha moment" is that bots might not follow each other, but they almost always act like each other. By building a graph based on behavioral similarity, the authors "force" bots into the same neighborhood, making them easier to isolate.
  • Structural Entropy as a "Natural" Clusterer: Unlike K-means, which requires you to guess the number of clusters ($K$), structural entropy naturally finds the most stable hierarchical division of the network based on its inherent information density.
  • Interpretability through Visualization: Because the model is based on an encoding tree, you can literally see the "branches" where bots diverge from humans. The paper provides heatmaps showing that bots tend to have very low posting influence and highly skewed posting types (e.g., only retweeting).

Key Results

UnDBot significantly outperformed ten representative unsupervised baselines:

  • Accuracy Gains: On the four datasets, UnDBot improved detection accuracy by 10.36% to 19.66% compared to traditional clustering (K-means) and by 1.37% to 3.13% over the best unsupervised graph embedding methods.
  • Stability: The model achieved high AUC scores (0.87 to 0.95) across all datasets, proving it remains effective even when the ratio of bots to humans is highly imbalanced.
  • Efficiency: Despite the complex math, UnDBot is efficient. For example, on the Cresci-2015 dataset, it ran in roughly 7 seconds, whereas some embedding-based baselines took hundreds or even thousands of seconds.

Limitations and Future Work

The authors note a few areas for improvement:

  • AI-Generated Content: As bots begin using Large Language Models (LLMs) to generate highly varied, human-like text, simple behavioral metrics like "Posting Type" might become less effective.
  • Feature Expansion: The current model relies on three primary behavioral metrics. Future versions could incorporate semantic features (the meaning of the tweets) or temporal features (the timing of posts) to catch even more "stealthy" bots.
  • Scalability: While efficient, the initial graph construction requires calculating similarities between user pairs, which could become a bottleneck for massive, billion-node social networks.

Summary updated

Abstract

Research on social bot detection plays a crucial role in maintaining the order and reliability of information dissemination while increasing trust in social interactions. The current mainstream social bot detection models rely on black-box neural network technology, e.g., Graph Neural Network, Transformer, etc., which lacks interpretability. In this work, we present UnDBot, a novel unsupervised, interpretable, yet effective and practical framework for detecting social bots. This framework is built upon structural information theory. We begin by designing three social relationship metrics that capture various aspects of social bot behaviors: Posting Type Distribution, Posting Influence, and Follow-to-follower Ratio. Three new relationships are utilized to construct a new, unified, and weighted social multi-relational graph, aiming to model the relevance of social user behaviors and discover long-distance correlations between users. Second, we introduce a novel method for optimizing heterogeneous structural entropy. This method involves the personalized aggregation of edge information from the social multi-relational graph to generate a two-dimensional encoding tree. The heterogeneous structural entropy facilitates decoding of the substantial structure of the social bots network and enables hierarchical clustering of social bots. Thirdly, a new community labeling method is presented to distinguish social bot communities by computing the user's stationary distribution, measuring user contributions to network structure, and counting the intensity of user aggregation within the community. Compared with ten representative social bot detection approaches, comprehensive experiments demonstrate the advantages of effectiveness and interpretability of UnDBot on four real social network datasets.
BibTeX
@article{peng2024unsupervised,
  author = {Hao Peng and Jingyun Zhang and Xiang Huang and Zhifeng Hao and Angsheng Li and Zhengtao Yu and Philip S. Yu},
  title = {{Unsupervised Social Bot Detection via Structural Information Theory}},
  journal = {ACM Trans. Information Systems},
  year = {2024},
  doi = {10.1145/3660522},
}

Loading related content...

Figure