Over-Sampling Strategy in Feature Space for Graphs based Class-imbalanced Bot Detection

Shuhao Shi, Kai Qiao, Chen Chen, Jie Yang, Jian Chen 0025, Bin Yan

TL;DR

OS-GNN is a new framework that tackles the "needle in a haystack" problem of bot detection by over-sampling minority class samples directly in the feature space. By performing neighborhood aggregation before generating synthetic data, it eliminates the need to "fake" social connections (edges), leading to more accurate and efficient Graph Neural Network (GNN) classifiers.

What Problem Does This Paper Address?

Online Social Networks (OSNs) are crawling with bots, but in most datasets, bots are significantly outnumbered by human users. This class imbalance creates a major headache for Graph Neural Networks (GNNs). When a model sees 90% humans and 10% bots, it often takes the "lazy" path of predicting everyone is human to achieve high overall accuracy, while failing miserably at actually catching the bots.

Existing solutions like GraphSMOTE try to fix this by creating synthetic bot nodes and then trying to guess which other nodes they should be connected to (edge synthesis). However, predicting social relationships is incredibly complex; if the model generates "noisy" or unrealistic edges, it actually degrades the performance of the GNN. The authors of this paper set out to find a way to balance the data without the messy business of faking a social graph.

Methods

The authors propose OS-GNN (Over-Sampling Strategy in Feature Space). Instead of over-sampling the raw input data, they move the process further down the pipeline. The framework consists of four main steps:

  1. Neighbor Aggregator: The model uses a 2-hop neighborhood aggregation (standard GNN logic) to transform raw user features into embeddings that capture social context.
  2. Feature Concatenation: To ensure no original information is lost, they concatenate these neighborhood-aware embeddings with the original node features.
  3. Synthetic Node Generator: They apply the SMOTE (Synthetic Minority Over-sampling Technique) algorithm within this new feature space. This creates "virtual" bot nodes that already have the "essence" of their social neighborhood baked into their features.
  4. GNN Classifier: Finally, they train a classifier on this augmented set. Crucially, because the features already contain neighborhood information, they can use an identity matrix as the adjacency matrix for the synthetic nodes, bypassing the need to generate fake edges entirely.

Datasets

The framework was evaluated on three prominent Twitter bot detection benchmarks:

  • TwiBot-20: A large-scale, comprehensive benchmark.
  • MGTAB: A multi-relational dataset focused on account detection.
  • Cresci-15: A classic dataset used for identifying fake followers.

The authors noted that these datasets vary significantly in their imbalance ratios ($\rho$), with TwiBot-20 being particularly challenging.

Key Insights and Ideas

  • Edges are Implicit, Not Explicit: The "aha moment" here is realizing that if you aggregate neighborhood info first, the resulting feature vector represents a node's position in the graph. You don't need to draw a line between a synthetic node and its neighbors if the synthetic node's features already reflect those neighbors.
  • Noise Reduction: By avoiding edge synthesis, OS-GNN avoids the "hallucinated" connections that often lead to over-smoothing or misinformation in other graph over-sampling methods.
  • Plug-and-Play Architecture: The framework is "backbone-agnostic." The authors successfully tested it using GCN, GraphSAGE, and GAT as the underlying architectures, proving its versatility.

Key Results

The OS-GNN framework consistently outperformed "Vanilla" GNNs and other state-of-the-art rebalancing methods (like Focal Loss or GraphSMOTE) across all three datasets.

  • Balanced Accuracy (bAcc): On the highly imbalanced TwiBot-20 dataset, OS-GNN achieved a bAcc of 83.12% (using GCN), compared to just 68.29% for the vanilla model.
  • Minority Class Accuracy: The model showed a significant boost in the True Positive Rate (TPR), meaning it was much better at actually identifying bots rather than just being "generally accurate."
  • Efficiency: Because it skips the edge-generation step, the method is computationally leaner than previous graph-based over-sampling techniques.

Limitations and Future Work

The authors identified a few areas for further refinement:

  • Hyperparameter Sensitivity: The model is sensitive to $\lambda$, the parameter that controls the weight of synthetic samples in the loss function. If $\lambda$ is too high, the model overfits the synthetic data and loses performance on real human users.
  • Graph Dependency: On the Cresci-15 dataset, the improvements were less dramatic. The authors attribute this to the fact that edges in Cresci-15 are less informative for classification, suggesting that OS-GNN provides the most value in "graph-heavy" scenarios.
  • Future Directions: The paper suggests exploring more sophisticated ways to determine the over-sampling scale ($\omega$) and testing the framework on even more complex, multi-relational social graphs.

Summary updated

Abstract

The presence of a large number of bots in Online Social Networks (OSN) leads to undesirable social effects. Graph neural networks (GNNs) are effective in detecting bots as they utilize user interactions. However, class-imbalanced issues can affect bot detection performance. To address this, we propose an over-sampling strategy for GNNs (OS-GNN) that generates samples for the minority class without edge synthesis. First, node features are mapped to a feature space through neighborhood aggregation. Then, we generate samples for the minority class in the feature space. Finally, the augmented features are used to train the classifiers. This framework is general and can be easily extended into different GNN architectures. The proposed framework is evaluated using three real-world bot detection benchmark datasets, and it consistently exhibits superiority over the baselines.
BibTeX
@inproceedings{shi2024over,
  author = {Shuhao Shi and Kai Qiao and Chen Chen and Jie Yang and Jian Chen and Bin Yan},
  title = {{Over-Sampling Strategy in Feature Space for Graphs based Class-imbalanced Bot Detection}},
  booktitle = {The Web Conference},
  year = {2024},
  doi = {10.1145/3589335.3651544},
}

Loading related content...

Figure