Lune

ICML2021Top-tier venue

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 anomaly family\textit{anomaly family}. 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 biased\textit{biased} 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.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guarantees cites Weighted Flow Diffusion for Local Graph Clustering with Node Attributes: an Algorithm and Statistical Guarantees
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers3

  1. 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
  2. Weighted Flow Diffusion for Local Graph Clustering with Node Attributes: an Algorithm and Statistical GuaranteesShenghao Yang, Kimon FountoulakisICML 2023 · 6 citations
  3. Calibrated Nonparametric Scan Statistics for Anomalous Pattern Detection in GraphsChunpai Wang, Daniel B. Neill, Feng ChenAAAI 2022 · 3 citations

Related papers

  1. Anomaly Detection in Time Series: A Comprehensive EvaluationSebastian Schmidl, Phillip Wenig, Thorsten PapenbrockVLDB 2022 · 578 citations
  2. Towards a Unified Framework of Clustering-based Anomaly DetectionZeyu Fang, Ming Gu, Sheng Zhou, Jiawei Chen et al.ICML 2025
  3. Graph Mixture of Experts and Memory-augmented Routers for Multivariate Time Series Anomaly DetectionXiaoyu Huang, Weidong Chen, Bo Hu, Zhendong MaoAAAI 2025 · 22 citations
  4. Estimating the Contamination Factor's Distribution in Unsupervised Anomaly DetectionLorenzo Perini, Paul-Christian Bürkner, Arto KlamiICML 2023 · 27 citations
  5. Identifying Selection Bias from Observational DataDavid Kaltenpoth, Jilles VreekenAAAI 2023 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines