Unsupervised Social Bot Detection via Structural Information Theory

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

Abstract

Social bot detection is essential for maintaining the integrity of digital information dissemination and fostering trust in social interactions. Current state-of-the-art detection models often rely on supervised deep learning architectures, such as Graph Neural Networks (GNNs) or Transformers, which suffer from a lack of interpretability and a heavy reliance on expensive labeled data. This paper presents UnDBot, a novel unsupervised and interpretable framework for social bot detection based on structural information theory. UnDBot constructs a weighted multi-relational graph using three behavioral metrics: Posting Type Distribution, Posting Influence, and Follow-to-follower Ratio. By optimizing heterogeneous structural entropy, the framework generates a two-dimensional encoding tree to cluster users hierarchically. Finally, a community labeling method distinguishes bot clusters by analyzing stationary distributions and aggregation intensity. Experimental results across four real-world datasets demonstrate that UnDBot significantly outperforms existing unsupervised methods in both accuracy and efficiency.

Introduction

Social bots have evolved from simple automated scripts into sophisticated entities capable of mimicking human behavior to spread misinformation and manipulate public discourse. Detecting these bots is increasingly difficult due to two primary challenges: the Labeling Bottleneck and the Black Box Problem. Supervised models require massive, high-quality labeled datasets that are difficult to maintain as bot tactics evolve. Furthermore, deep learning models often fail to provide a clear rationale for their classifications, making it hard for researchers to trust or verify their outputs.

Moreover, modern bots employ "camouflage" techniques, interacting with genuine human accounts to blend into the social graph. Traditional detection methods that rely solely on direct interaction links (like follows or mentions) often struggle to isolate these infiltrators. UnDBot addresses these issues by shifting the focus from direct interactions to behavioral commonalities using structural information theory.

The UnDBot Framework

1. Multi-relational Graph Construction

Instead of a standard social graph, UnDBot builds a unified, weighted multi-relational graph where edges represent similarities in user behavior. Three specific metrics are utilized:

  • Posting Type Distribution: The proportion of original content, retweets, and comments.
  • Posting Influence: The average engagement (likes and shares) a user's posts generate.
  • Follow-to-follower Ratio: A metric capturing the automated "follow-back" strategies common in bot networks.

By mapping these behaviors, the framework identifies long-distance correlations between users who may not interact directly but exhibit identical behavioral patterns.

2. User Community Division via Structural Entropy

The core of UnDBot lies in the application of structural information theory. The framework treats the social graph as an information source and seeks to find an "encoding tree" that minimizes the graph's structural entropy. This process results in a hierarchical clustering of users into communities where relationships are most stable. Unlike traditional clustering algorithms like K-means, this method does not require a pre-defined number of clusters ($K$); it naturally discovers the inherent structure of the network.

3. Community Binary Classification

To distinguish between human and bot communities, UnDBot employs a labeling method based on three factors:

  • Community Influence: Calculated via a stationary distribution (random walks) to determine the cluster's centrality.
  • Community Cohesion: Measuring how tightly packed behaviors are within the group using entropy.
  • Aggregation Intensity: Identifying the density of user clusters.

Bots typically form highly cohesive, dense clusters with distinct influence signatures, allowing the model to flag them with high precision.

Experimental Evaluation

Datasets

The framework was evaluated on four Twitter (X) datasets:

  • Cresci-2015 & Cresci-2017: Standard benchmarks containing fake followers and social spambots.
  • Pronbots-2019 & Botwiki-2019: Bot-heavy datasets augmented with human accounts to simulate realistic, imbalanced social environments.

Performance Results

UnDBot demonstrated superior performance compared to ten representative unsupervised baselines:

  • Accuracy: The model improved detection accuracy by 10.36% to 19.66% over traditional clustering and by 1.37% to 3.13% over advanced unsupervised graph embedding methods.
  • Stability: UnDBot maintained high AUC scores (0.87 to 0.95) even in imbalanced datasets, proving its robustness against varying bot-to-human ratios.
  • Efficiency: The framework is computationally efficient. On the Cresci-2015 dataset, UnDBot completed its analysis in approximately 7 seconds, significantly faster than many embedding-based alternatives that required hundreds or thousands of seconds.

Conclusion and Future Work

UnDBot provides a practical, interpretable, and effective solution for unsupervised social bot detection. By leveraging structural entropy, it moves beyond the limitations of labeled data and black-box models.

Future research will focus on expanding the feature set to include temporal patterns (post timing) and semantic analysis of tweet content to counter bots utilizing Large Language Models (LLMs). Additionally, the team aims to optimize the initial graph construction phase to improve scalability 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},
}
Figure