# Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic

arXiv: https://arxiv.org/abs/1312.3291 · HTML: https://mlsanity.com/paper/1312.3291/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Dec 2013.

## Built on by (most cited first, 7 of 7)

- [A Comprehensive Survey on Graph Anomaly Detection with Deep Learning](https://mlsanity.com/paper/2106.07178/) (2021)
- [DAGAD: Data Augmentation for Graph Anomaly Detection](https://mlsanity.com/paper/2210.09766/) (2022)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs](https://mlsanity.com/paper/2106.01529/) (2021)
- [Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees](https://mlsanity.com/paper/2605.18775/) (2026)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs](https://mlsanity.com/paper/2111.07394/) (2021)
- [The Lifecycle of a Statistical Model: Model Failure Detection, Identification, and Refitting](https://mlsanity.com/paper/2202.04166/) (2022)
- [Efficient Regression Models for Scan Statistics](https://mlsanity.com/paper/2608.22201/) (2026)

## Abstract (arXiv)

The detection of anomalous activity in graphs is a statistical problem that arises in many applications, such as network surveillance, disease outbreak detection, and activity monitoring in social networks. Beyond its wide applicability, graph structured anomaly detection serves as a case study in the difficulty of balancing computational complexity with statistical power. In this work, we develop from first principles the generalized likelihood ratio test for determining if there is a well connected region of activation over the vertices in the graph in Gaussian noise. Because this test is computationally infeasible, we provide a relaxation, called the Lovasz extended scan statistic (LESS) that uses submodularity to approximate the intractable generalized likelihood ratio. We demonstrate a connection between LESS and maximum a-posteriori inference in Markov random fields, which provides us with a poly-time algorithm for LESS. Using electrical network theory, we are able to control type 1 error for LESS and prove conditions under which LESS is risk consistent. Finally, we consider specific graph models, the torus, k-nearest neighbor graphs, and epsilon-random graphs. We show that on these graphs our results provide near-optimal performance by matching our results to known lower bounds.