Graph Scan Statistics With Uncertainty

Authors

  • Jose Cadena Virginia Tech
  • Arinjoy Basak Virginia Tech
  • Anil Vullikanti Virginia Tech
  • Xinwei Deng Virginia Tech

DOI:

https://doi.org/10.1609/aaai.v32i1.11799

Keywords:

scan statistics, graph anomaly detection, uncertainty

Abstract

Scan statistics is one of the most popular approaches for anomaly detection in spatial and network data. In practice, there are numerous sources of uncertainty in the observed data. However, most prior works have overlooked such uncertainty, which can affect the accuracy and inferences of such methods. In this paper, we develop the first systematic approach to incorporating uncertainty in scan statistics. We study two formulations for robust scan statistics, one based on the sample average approximation and the other using a max-min objective. We show that uncertainty significantly increases the computational complexity of these problems. Rigorous algorithms and efficient heuristics for both formulations are developed with justification of theoretical bounds. We evaluate our proposed methods on synthetic and real datasets, and we observe that our methods give significant improvement in the detection power as well as optimization objective, relative to a baseline.

Downloads

Published

2018-04-29

How to Cite

Cadena, J., Basak, A., Vullikanti, A., & Deng, X. (2018). Graph Scan Statistics With Uncertainty. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11799