Graph-Hist: Graph Classification from Latent Feature Histograms with Application to Bot Detection

Thomas Magelinski, David M. Beskow, Kathleen M. CarleyAAAI 2020 · DOI

Abstract

Graph-Hist is a novel end-to-end neural network architecture that classifies graphs by analyzing the distribution of their latent features through differentiable histograms. This approach is specifically designed to handle the large, sparse networks typical of social media, where traditional graph classification methods often struggle. By identifying artificial patterns in conversational structures, Graph-Hist sets a new state-of-the-art in detecting sophisticated Twitter bots.

Introduction: The Challenge of Large, Sparse Graphs

Most graph classification research relies on benchmark datasets consisting of small, dense graphs, such as protein structures. However, real-world social media graphs are typically massive and incredibly sparse. Existing models often struggle with the "variable size problem," where a variable number of nodes ($n$) must be transformed into a fixed-size vector ($k$). Common methods like "SortPool" can lose vital information or introduce noise. Furthermore, while classical network science emphasizes the distribution of local properties (like degree distribution), modern deep learning models have not fully integrated this "distributional" thinking into end-to-end differentiable architectures.

Methods: Differentiable Histograms

The authors introduce Graph-Hist, which shifts the focus from processing individual nodes to analyzing the "multi-channel histogram" of the graph's features.

The Graph-Hist architecture overview, illustrating the flow from graph Laplacian and features to differentiable histograms.

The architecture is composed of four key stages:

  1. Parallel Graph Convolutions: Instead of stacking layers, the model uses powers of the Graph Laplacian to aggregate features from $h$-hop neighborhoods simultaneously.
  2. Latent Feature Extraction: These multi-hop features are concatenated and passed through fully connected layers to capture non-linear relationships between dimensions.
  3. Differentiable Binning: To handle variable graph sizes, the model bins node features into a 1D histogram for each feature dimension. Crucially, this binning process is differentiable, allowing the model to optimize node embeddings specifically to improve classification accuracy.
  4. 1D-CNN Classifier: The resulting multi-channel histograms are treated like 1D images and processed by a modified LeNet-5 architecture to produce the final classification.

Key Results and Performance

The researchers evaluated Graph-Hist on standard benchmarks, social media datasets (Reddit), and a newly curated Twitter dataset containing nearly 15,000 conversational ego-networks.

Graph-Hist achieved state-of-the-art (SOTA) results on all three Reddit datasets, proving its effectiveness for sparse, large-scale social data. In the Twitter bot detection case study, Graph-Hist significantly outperformed specialized tools, achieving an F1 score of 0.740.

Comparative performance of Graph-Hist against existing bot detection models on the Twitter dataset.

Key Insights

  • Distributions Matter: In large-scale social networks, the overall statistical distribution of node behavior is more informative than the exact placement of single edges.
  • End-to-End Learning: Because Graph-Hist is end-to-end, the feature extraction layers learn how to represent nodes specifically so that their histograms become easy to classify.
  • Structural Artifacts: While sophisticated bots can mimic human text, it is much harder for them to fake the organic, messy structure of a human conversational network. Graph-Hist effectively identifies these structural "artifacts."

Conclusion and Future Work

Graph-Hist demonstrates that focusing on feature distributions rather than local connectivity is a powerful approach for classifying large-scale social networks. While the current model uses 1D histograms—which simplifies the relationship between different feature dimensions—it remains highly effective and generalizable. Future directions include exploring non-uniform binning and applying the model to detect other coordinated influence campaigns, such as "trolls" or propaganda networks.

Summary updated

BibTeX
@inproceedings{magelinski2020graph,
  author = {Thomas Magelinski and David M. Beskow and Kathleen M. Carley},
  title = {{Graph-Hist: Graph Classification from Latent Feature Histograms with Application to Bot Detection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.5956},
}
Figure