Parallel algorithms for anomalous subgraph detection

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.