Anomaly detection in the dynamics of web and social networks

Volodymyr Miz, Benjamin Ricaud, Kirell Benzi, Pierre Vandergheynst

Abstract

Modern web and social networks generate massive amounts of log data, including user activity, emails, and page views. Detecting anomalies—deviations from normal behavior—is challenging because these networks are both massive and constantly evolving. This paper introduces a scalable, unsupervised method for detecting anomalies in large, dynamic graphs by leveraging the Hopfield network model of associative memory. By treating a network as a memory that "records" bursts of activity, the authors identify and reconstruct localized spatio-temporal events from noisy or incomplete data.

Introduction

The authors identify a critical gap in existing research: most methods treat the spatial component (who is connected to whom) and the temporal component (when activity happens) independently. However, real-world anomalies are often "spatio-temporal events"—localized groups of connected nodes experiencing simultaneous bursts of activity. The challenge is to find these events in a way that is unsupervised, interpretable, and scales to millions of nodes.

Methodology

The proposed two-stage approach focuses on transforming a dynamic graph into an associative memory:

  1. Feature Extraction and Filtering: To handle massive datasets, the system first filters for "potential anomalies." A node is flagged only if it shows a sufficient number of "bursts" (activity exceeding a statistical threshold), drastically reducing the data volume for subsequent processing.
  2. Hopfield Network Learning: The core innovation involves adapting the Hebbian learning rule—"cells that fire together, wire together"—to the graph. If two connected nodes are active during the same time slice, the edge weight between them is strengthened.
Illustration of spatio-temporal events where connected nodes exhibit synchronized bursts of activity.

As illustrated in Figure 1, the resulting "learned" graph acts as a collective memory. Because it utilizes the Hopfield model, the system can perform a recall process. If provided with a partial or noisy pattern of activity, the network can iteratively converge to "recall" the full, clean event cluster. The algorithm is designed for distributed computing using a Pregel-like abstraction, making it suitable for web-scale data.

Experimental Evaluation

The researchers evaluated their method on two distinct types of dynamic networks:

  • Enron Email Dataset: A benchmark containing ~614,000 emails used to validate the method against known corporate events and ground truth anomalies.
  • Wikipedia Page Views: A larger dataset consisting of English Wikipedia articles and hourly visit counts. The hyperlink structure served as the base graph, with viewership as the dynamic attribute.
Detection of anomalous activity periods in the Enron email dataset corresponding to known corporate events.

Key Results

  • Enron Validation: The method successfully detected all four major anomalous periods previously reported in literature (Dec 1999, April, May, and August 2001), as shown in Figure 2. These spikes correlate directly with specific news reports and corporate milestones.
  • Wikipedia Discovery: The algorithm identified 172 distinct event clusters from a 7-month Wikipedia window. For example, it tracked the expansion of a "National Football League" cluster through the 2014-2015 season, peaking at Super Bowl XLIX.
  • Robustness and Recall: In experiments where 20% of the data was hidden, the Hopfield recall process successfully recovered the majority of the "forgotten" activity, demonstrating significant power for data recovery.

Discussion and Insights

Viewing a dynamic network as an artificial collective memory allows for the pruning of noise. The "learned" Wikipedia graph was significantly more modular than the original hyperlink graph. While the original graph is cluttered with high-degree "hub" pages (like "United States") that link to many unrelated topics, the Hopfield model prunes these away to reveal small, tightly-knit clusters representing specific real-world events.

Furthermore, the method produces contextual anomalies. Instead of a simple binary score, it generates a rich cluster of related entities, providing immediate context for why an anomaly is occurring.

Limitations and Future Work

The current implementation processes data in batch time-windows. Developing an "online" version for real-time streaming remains a goal for future work. Additionally, while the model is robust, it relies on hyperparameters like burst thresholds that may require domain-specific tuning. Future iterations may also incorporate edge directionality to better model information propagation.

Summary updated

BibTeX
@inproceedings{miz2019anomaly,
  author = {Volodymyr Miz and Benjamin Ricaud and Kirell Benzi and Pierre Vandergheynst},
  title = {{Anomaly detection in the dynamics of web and social networks}},
  booktitle = {The Web Conference},
  year = {2019},
  doi = {10.1145/3308558.3313541},
}
Figure