AugSplicing: Synchronized Behavior Detection in Streaming Tensors


  • Jiabao Zhang University of Chinese Academy of Sciences; Institute of Computing Technology
  • Shenghua Liu Institute of Computing Technology, CAS, China
  • Wenting Hou Beijing InnovSharing Co.Ltd
  • Siddharth Bhatia National University of Singapore
  • Huawei Shen Institute of Computing Technology, Chinese Academy of Sciences
  • Wenjian Yu Tsinghua University
  • Xueqi Cheng Institute of Computing Technology, Chinese Academy of Sciences



Data Stream Mining


How can we track synchronized behavior in a stream of time-stamped tuples, such as mobile devices installing and uninstalling applications in the lockstep, to boost their ranks in the app store? We model such tuples as entries in a streaming tensor, which augments attribute sizes in its modes over time. Synchronized behavior tends to form dense blocks (i.e.~subtensors) in such a tensor, signaling anomalous behavior, or interesting communities. However, existing dense block detection methods are either based on a static tensor, or lack an efficient algorithm in a streaming setting. Therefore, we propose a fast streaming algorithm, AUGSPLICING, which can detect the top dense blocks by incrementally splicing the previous detection with the incoming ones in new tuples, avoiding re-runs over all the history data at every tracking time step. AUGSPLICING is based on a splicing condition that guides the algorithm (Section 4). Compared to the state-of-the-art methods, our method is (1) effective to detect fraudulent behavior in installing data of real-world apps and find a synchronized group of students with interesting features in campus Wi-Fi data; (2) robust with splicing theory for dense block detection; (3) streaming and faster than the existing streaming algorithm, with closely comparable accuracy.




How to Cite

Zhang, J., Liu, S., Hou, W., Bhatia, S., Shen, H., Yu, W., & Cheng, X. (2021). AugSplicing: Synchronized Behavior Detection in Streaming Tensors. Proceedings of the AAAI Conference on Artificial Intelligence, 35(5), 4653-4661.



AAAI Technical Track on Data Mining and Knowledge Management