CADDeLaG: Framework for distributed anomaly detection in large dense graph sequences

Aniruddha Basak, Kamalika Das, Ole J. MengshoelarXiv 2018 · arXiv

Introduction

In graph theory and network analysis, researchers often rely on the inherent sparsity of real-world networks—such as social media or the web—to apply computational optimizations. However, many critical domains, including climatology and financial modeling, generate "dense" graphs where every node potentially relates to every other node. For instance, a global climate dataset with 260,000 geolocations results in a fully connected graph with over 67 billion edges.

Standard analytical tools and traditional "ad-hoc sparsification" (which removes edges to save space) often fail in these scenarios. In climatology, the most vital relationships are frequently "teleconnections"—long-distance dependencies that are often the first to be discarded during sparsification. To address this, Basak et al. introduced CADDeLaG (Commute-time based Anomaly Detection in Dense LArger-than-memory Graphs), a distributed framework designed to process massive, dense graphs that exceed the memory capacity of individual nodes.

Methodology

CADDeLaG is built on Apache Spark and utilizes three primary technical pillars to achieve scalability without sacrificing the structural integrity of dense graphs:

  1. Spectral Sparsification via Random Projection: Rather than calculating exact distances, which is computationally prohibitive ($O(n^3)$), the framework uses random projections to map the graph into a lower-dimensional space. This preserves pairwise distances while significantly reducing the computational load.
  2. Refactored SDD Solver: The authors developed a distributed solver for Symmetric Diagonally Dominant (SDD) systems. By precomputing "chain products" of matrices, they reduced the iterative solving process to simple matrix-vector multiplications, which are significantly faster in a distributed environment.
  3. Shuffle-Free Matrix Multiplication: In standard distributed computing, the "shuffle storm"—the massive movement of data between worker nodes—is often the primary bottleneck. CADDeLaG avoids this by writing matrix blocks to a shared distributed file system (such as Lustre). Executors read only the specific blocks they need, eliminating the I/O overhead associated with traditional Spark BlockMatrix operations.

Experimental Evaluation

The framework was evaluated across three distinct datasets to test scalability and real-world utility:

  • Synthetic Data: Using Gaussian mixtures, the authors demonstrated that CADDeLaG achieves linear scaling even as the number of edges grows quadratically, successfully processing graphs with up to 500,000 nodes (approximately 125 billion potential edges).
  • 2016 US Election Donation Data: Analyzing FEC records with over 555,000 nodes, the framework identified a significant shift where donors moved from the Democratic party to "Others" in the months preceding the election—a relational trend missed by standard independent record analysis.
  • Worldwide Precipitation Data: Using 20 years of NCEP/NCAR global rainfall data, the framework processed a fully connected graph of 259,200 geolocations.

Key Insights and Results

The research highlights that the "Shuffle Storm" is a more significant barrier to scaling than raw calculation time. By adopting a shuffle-free architecture, CADDeLaG achieved peak efficiency when the number of workers matched the number of matrix blocks.

Furthermore, the study proves that traditional sparsification is dangerous for certain data types. For example, a standard 10-nearest-neighbor sparsification failed to detect the 1995 California floods in the climate dataset. Because CADDeLaG could process the entire dense graph, it successfully flagged the flood and the impact of Cyclone Geralda in Madagascar as top structural anomalies.

Conclusion and Future Work

CADDeLaG provides a robust solution for anomaly detection in massive dense graphs by reimagining distributed matrix operations. While the framework currently relies on high-performance shared storage (like Lustre over InfiniBand) for maximum efficiency, it represents a major step forward in analyzing datasets previously considered "un-scalable." Future research directions include extending this shuffle-free distributed framework to other graph tasks, such as community detection and clustering in larger-than-memory datasets.

Summary updated

BibTeX
@misc{basak2018caddelag,
  author = {Aniruddha Basak and Kamalika Das and Ole J. Mengshoel},
  title = {{CADDeLaG: Framework for distributed anomaly detection in large dense graph sequences}},
  year = {2018},
  eprint = {1802.05421},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.05421},
}
Figure