Abstract
How can we detect fraudulent lockstep behavior in large-scale multi-aspect data (i.e., tensors)? Can we detect it when data are too large to fit in memory or even on a disk? Past studies have shown that dense subtensors in real-world tensors (e.g., social media, Wikipedia, TCP dumps, etc.) signal anomalous or fraudulent behavior such as retweet boosting, bot activities, and network attacks. Thus, various approaches, including tensor decomposition and search, have been proposed for detecting dense subtensors rapidly and accurately. However, existing methods have low accuracy, or they assume that tensors are small enough to fit in main memory, which is unrealistic in many real-world applications such as social media and web. To overcome these limitations, we propose D-CUBE, a disk-based dense-subtensor detection method, which also can run in a distributed manner across multiple machines. Compared to state-of-the-art methods, D-CUBE is (1) Memory Efficient: requires up to 1,561X less memory and handles 1,000X larger data (2.6TB), (2) Fast: up to 7X faster due to its near-linear scalability, (3) Provably Accurate: gives a guarantee on the densities of the detected subtensors, and (4) Effective: spotted network attacks from TCP dumps and synchronized behavior in rating data most accurately.
Introduction: The Challenge of Lockstep Behavior
In the world of "Big Data," many interesting phenomena appear as lockstep behavior. For example, a group of bots might all retweet the same set of accounts at the same time, or a network attack might involve a cluster of IPs flooding specific ports. Mathematically, these are represented as tensors (multi-dimensional arrays). Finding these suspicious groups is equivalent to finding "dense subtensors."
Modern datasets (social media, web logs) are often "Tera-scale," meaning they are far too large to fit in a computer's main memory (RAM). Existing algorithms either assume the data fits in RAM, sacrifice accuracy for speed, or require excessive disk I/O, making them impractical for real-world applications.
The D-CUBE Algorithm
To overcome these limitations, we introduce D-CUBE, an "out-of-core" (disk-based) algorithm that identifies dense regions without needing to load the entire dataset into memory. D-CUBE is designed to work where data is read and written sequentially (the W-Stream model), which is much faster for disk-based storage than random access.
Key Innovations:
- Massive Greedy Removal: Traditional greedy algorithms remove one "attribute value" (e.g., one user or one IP) at a time. D-CUBE uses a threshold parameter ($\theta$) to remove multiple values simultaneously in a single pass over the data, drastically reducing disk I/O.
- Distributed Processing: D-CUBE can run in a distributed manner using the MapReduce (Hadoop) framework, allowing it to scale across clusters of machines.
- Selection Policies: It offers two ways to choose which dimensions to prune: Maximum Cardinality (providing a mathematical guarantee on accuracy) and Maximum Density (often performing better in practice).
Experimental Evaluation
The researchers evaluated D-CUBE on a diverse array of real-world datasets, including rating data (Yelp, Netflix), Wikipedia revision histories, and TCP dumps for network intrusion detection. They also tested scalability using synthetic tensors up to 2.6 TB (100 billion entries).
Key Results:
- Scalability: D-CUBE successfully handled a 2.6 TB tensor. Competitors like M-Zoom ran out of memory on datasets larger than 21 GB.
- Memory Efficiency: It required up to 1,561x less memory than the next best competitor. Unlike previous methods, D-CUBE’s memory requirement only grows with the number of distinct attribute values, not the total number of data points.
- Speed: It was up to 7x faster than state-of-the-art in-memory algorithms due to its near-linear scalability and optimized disk access.
- Effectiveness: In network intrusion tests (DARPA/AirForce), D-CUBE achieved the highest accuracy in distinguishing attacks from normal traffic.
Conclusion and Future Work
D-CUBE provides a robust solution for mining dense subtensors in massive datasets that exceed RAM capacity. While it currently assumes that metadata (distinct attribute values) can fit in memory, future work could extend this to handle even larger metadata sets or adapt the algorithm for real-time streaming data.
Summary updated