Parallel algorithms for anomalous subgraph detection

Published in Concurrency and Computation: Practice and Experience, 2016

Recommended citation: Bibtex

Jieyu Zhao, Jianxin Li, Baojian Zhou, Feng Chen, Paul Tomchik and Wuyang Ju


For the many application domains concerning entities and their connections, often their data can be formally represented as graphs and an important problem is detecting an anomalous subgraph within it. Numerous methods have been proposed to speed-up anomalous subgraph detection; however, each incurs non-trivial costs on detection accuracy. In this paper, we formulate the anomalous subgraph detection problem as the maximization of a non-parametric scan statistic and then approximate it to a submodular maximization problem. We propose two parallel algorithms: non-coordination anomalous subgraph detection (NCASD) and under-coordination anomalous subgraph detection (UCASD)for the anomalous subgraph detection. To the best of our knowledge, this paper is the first to solve this problem in parallel. NCASD emphasizes speed at the expense of approximation guarantees, while UCASD achieves a higher approximation factor through additional coordination controls and reduced parallelism. The experiments demonstrate the effectiveness and efficiency of our proposed approaches in a real-world application domain (water pollution detection), comparing them with five other state-of-the-art methods.


@article{zhao2017parallel, title={Parallel algorithms for anomalous subgraph detection}, author={Zhao, Jieyu and Li, Jianxin and Zhou, Baojian and Chen, Feng and Tomchik, Paul and Ju, Wuyang}, journal={Concurrency and Computation: Practice and Experience}, volume={29}, number={3}, year={2017}, publisher={Wiley Online Library} }