Unsupervised Anomaly Detection in The Presence of Missing Values

Feng Xiao, Jicong FanNeurIPS 2024 · OpenReview

TL;DR

Standard anomaly detection fails when data is missing because imputation models—trained only on "normal" data—accidentally "fix" anomalies to look normal. This paper introduces ImAD, an end-to-end framework that jointly learns to impute and detect anomalies by generating "pseudo-abnormal" samples to teach the model what outliers look like, even when they are incomplete.

What Problem Does This Paper Address?

Anomaly detection (AD) is the art of finding the "needle in the haystack"—identifying rare, suspicious patterns in data. However, most AD algorithms assume the haystack is perfectly visible. In reality, data is often "holy": sensors fail, patients skip survey questions, or records are lost, leading to missing values. In fields like bioinformatics or recommendation systems, missingness can exceed 80%.

The common fix is a two-stage "impute-then-detect" pipeline: first, fill in the blanks using a tool like MissForest or GAIN, then run an AD model. The authors identify a fatal flaw here called imputation bias. Because unsupervised AD models are typically trained only on normal data, the imputation stage learns to fill in missing values in a way that makes every sample look as "normal" as possible. Consequently, an actual anomaly with missing values gets "corrected" into a normal-looking sample, allowing it to slip past the detector.

Recall comparison showing imputation bias.

As shown above, when missing data is imputed using standard methods, the recall of anomaly detection models drops significantly compared to when complete data is available, demonstrating how anomalies are "imputed away."

Methods

The authors propose ImAD (Imputation-integrated Anomaly Detection), an end-to-end approach that solves imputation and detection in a single optimization problem.

The architecture consists of three neural network modules:

  1. Imputer ($h$): Fills in missing values.
  2. Projector ($f$): Maps data into a low-dimensional latent space $Z$ where anomalies are easier to separate.
  3. Reconstructor ($g$): Maps latent points back to the original data space.

The Secret Sauce: Pseudo-Abnormal Samples To break the imputation bias, the model needs to see what anomalies look like during training. Since we don't have real labels, ImAD generates pseudo-abnormal samples.

  • It defines a "normal" region in the latent space (a small hyperball).
  • It samples "pseudo-abnormal" points from a surrounding "hypershell" (just outside the normal ball).
  • The Reconstructor maps these shell-points back to the original space to create synthetic outliers.

By training the Imputer on both the original (incomplete) normal data and these synthetic outliers, the model learns to recover missing values without blindly forcing every sample toward the "normal" distribution. The entire system is trained using a unified loss function that balances imputation accuracy, reconstruction quality, and the distance between normal and abnormal clusters in the latent space.

Datasets

The researchers evaluated ImAD on 11 real-world tabular datasets across various domains (cybersecurity, healthcare, biology):

  • Manually Corrupted Datasets: Adult, Botnet, KDD, Arrhythmia, Speech, Segerstolpe, and Usoskin. These were originally complete, allowing the authors to simulate different missingness mechanisms (MCAR, MAR, MNAR) at rates of 20% and 50%.
  • Inherently Missing Datasets: Titanic, MovieLens1M, Bladder, and Seq2-Heart. These datasets naturally contain missing values, providing a test for real-world robustness.

Key Insights and Ideas

  • The Generalization Gap: The core "aha" moment is realizing that an imputer is essentially a generative model. If it only sees "A," it will try to turn "B" into "A." In AD, this is a bug, not a feature.
  • Latent Space Geometry: By forcing normal data into a tight center and pseudo-anomalies into a surrounding shell, the model creates a "safety buffer." This geometric constraint helps the imputer maintain the "abnormal-ness" of outliers during the recovery process.
  • End-to-End Synergy: Imputation and detection are usually treated as separate chores. This paper shows they are mathematically coupled; better detection requires an imputer that respects outliers, and better imputation requires a model that understands the boundary of normality.

Key Results

ImAD consistently outperformed two-stage baselines (combinations of 3 imputation methods and 4 AD methods) across nearly all tests.

AUROC vs. Missing Rate for standard AD methods.
  • Robustness to Missing Rates: As illustrated in the charts above, standard anomaly detection methods see their accuracy (AUROC) plummet as the missing rate increases from 0% to 80%. In contrast, ImAD’s performance remains significantly more stable across varying missingness levels.
  • Performance: On the "Adult" dataset with 50% missing data, ImAD achieved an AUROC of ~71%, while the best two-stage baseline (MissForest + I-Forest) struggled at ~60%.
  • Recall Improvement: The authors specifically showed that ImAD significantly improves the recall of abnormal data, proving it successfully mitigates the bias that previously caused anomalies to be "imputed away."

Limitations and Future Work

While ImAD is a breakthrough for tabular data, the authors note a few areas for growth:

  • Data Modality: The current work focuses on tabular data. Extending this to high-dimensional images or complex time-series data (where missingness has temporal correlations) remains an open challenge.
  • Computational Complexity: The unified optimization involves Sinkhorn distances (for optimal transport) and multiple neural networks, which may be more computationally intensive than simple two-stage pipelines for extremely large datasets.
  • Hyperparameter Sensitivity: Like many deep learning models, performance can vary based on the choice of latent dimension and the radii of the hyperspheres, though the authors provide a sensitivity analysis to guide these choices.

Summary updated

Abstract

Anomaly detection methods typically require fully observed data for model training and inference and cannot handle incomplete data, while the missing data problem is pervasive in science and engineering, leading to challenges in many important applications such as abnormal user detection in recommendation systems and novel or anomalous cell detection in bioinformatics, where the missing rates can be higher than 30\% or even 80\%. In this work, first, we construct and evaluate a straightforward strategy, ''impute-then-detect'', via combining state-of-the-art imputation methods with unsupervised anomaly detection methods, where the training data are composed of normal samples only. We observe that such two-stage methods frequently yield imputation bias from normal data, namely, the imputation methods are inclined to make incomplete samples ''normal", where the fundamental reason is that the imputation models learned only on normal data and cannot generalize well to abnormal data in the inference stage. To address this challenge, we propose an end-to-end method that integrates data imputation with anomaly detection into a unified optimization problem. The proposed model learns to generate well-designed pseudo-abnormal samples to mitigate the imputation bias and ensure the discrimination ability of both the imputation and detection processes. Furthermore, we provide theoretical guarantees for the effectiveness of the proposed method, proving that the proposed method can correctly detect anomalies with high probability. Experimental results on datasets with manually constructed missing values and inherent missing values demonstrate that our proposed method effectively mitigates the imputation bias and surpasses the baseline methods significantly. The source code of our method is available at https://github.com/jicongfan/ImAD-Anomaly-Detection-With-Missing-Data.
BibTeX
@inproceedings{xiao2024unsupervised,
  author = {Feng Xiao and Jicong Fan},
  title = {{Unsupervised Anomaly Detection in The Presence of Missing Values}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=AoEeBqP8AD},
}
Figure