  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.
