Quantifying and Reducing Bias in Maximum Likelihood Estimation of Structured Anomalies
Uthsav Chitra, Kimberly Ding, Jasper C. H. Lee, Benjamin J. Raphael
Abstract
Anomaly estimation, or the problem of finding a subset of a dataset that differs from the rest of the dataset, is a classic problem in machine learning and data mining. In both theoretical work and in applications, the anomaly is assumed to have a specific structure defined by membership in an . For example, in temporal data the anomaly family may be time intervals, while in network data the anomaly family may be connected subgraphs. The most prominent approach for anomaly estimation is to compute the Maximum Likelihood Estimator (MLE) of the anomaly. However, it was recently observed that for some anomaly families, the MLE is an asymptotically estimator of the anomaly. Here, we demonstrate that the bias of the MLE depends on the size of the anomaly family. We prove that if the number of sets in the anomaly family that contain the anomaly is sub-exponential, then the MLE is asymptotically unbiased. At the same time, we provide empirical evidence that the converse is also true: if the number of such sets is exponential, then the MLE is asymptotically biased. Our analysis unifies a number of earlier results on the bias of the MLE for specific anomaly families, including intervals, submatrices, and connected subgraphs. Next, we derive a new anomaly estimator using a mixture model, and we empirically demonstrate that our estimator is asymptotically unbiased regardless of the size of the anomaly family. We illustrate the benefits of our estimator on both simulated disease outbreak data and a real-world highway traffic dataset.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
3 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers3
- Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval GuaranteesZhuoping Zhou, Davoud Ataee Tarzanagh, Sima Didari, Wenjun Hu et al.ICLR 2026 · 6 citations
- Weighted Flow Diffusion for Local Graph Clustering with Node Attributes: an Algorithm and Statistical GuaranteesShenghao Yang, Kimon FountoulakisICML 2023 · 6 citations
- Calibrated Nonparametric Scan Statistics for Anomalous Pattern Detection in GraphsChunpai Wang, Daniel B. Neill, Feng ChenAAAI 2022 · 3 citations
Related papers
- Anomaly Detection in Time Series: A Comprehensive EvaluationSebastian Schmidl, Phillip Wenig, Thorsten PapenbrockVLDB 2022 · 578 citations
- Towards a Unified Framework of Clustering-based Anomaly DetectionZeyu Fang, Ming Gu, Sheng Zhou, Jiawei Chen et al.ICML 2025
- Graph Mixture of Experts and Memory-augmented Routers for Multivariate Time Series Anomaly DetectionXiaoyu Huang, Weidong Chen, Bo Hu, Zhendong MaoAAAI 2025 · 22 citations
- Estimating the Contamination Factor's Distribution in Unsupervised Anomaly DetectionLorenzo Perini, Paul-Christian Bürkner, Arto KlamiICML 2023 · 27 citations
- Identifying Selection Bias from Observational DataDavid Kaltenpoth, Jilles VreekenAAAI 2023 · 12 citations
