Introduction
Anomaly detection is a critical task in domains ranging from financial fraud prevention to industrial equipment monitoring. Because anomalies are by definition rare and often novel, these systems typically operate in an unsupervised manner, relying on heuristics to distinguish outliers from normal behavior. However, the decision boundaries of unsupervised detectors are often ambiguous. For data points situated near these boundaries, a model's prediction may be no more reliable than a coin flip. In high-stakes environments, such uncertainty can erode user trust and lead to costly errors.
While "Learning to Reject" (L2R)—allowing a model to abstain from a prediction and defer to human expertise—is well-established in supervised learning, it presents a significant challenge in unsupervised settings. Without ground-truth labels, it is traditionally impossible to tune a rejection threshold or validate where a model is likely to fail. This paper introduces REJEX (Rejecting via ExCeeD), a novel framework that enables unsupervised anomaly detection with rejection by leveraging the stability of predictions as a proxy for confidence.
The REJEX Framework
The core innovation of REJEX is the use of the EXCEED stability metric to determine when a model should abstain. Rather than relying on the raw anomaly score, REJEX evaluates how consistent a prediction remains under slight perturbations of the training data. If a model's output for a specific test point flips easily when the training set is varied, the prediction is deemed unstable and the model rejects the instance.
Theoretical Foundation
The authors provide a finite-sample theoretical analysis of the EXCEED metric, demonstrating that the distribution of stability scores follows predictable mathematical patterns. This analysis allows for the implementation of a constant rejection threshold (defined as $\tau = 1 - \epsilon$). Unlike previous methods that require labeled validation sets to optimize thresholds, REJEX provides a "plug-and-play" solution that requires no labels. Furthermore, the framework offers mathematical guarantees on test-time rejection rates and provides an upper bound on the expected cost of errors, accounting for false positives, false negatives, and the cost of human intervention.
Computational Efficiency
REJEX is designed for practical scalability. Unlike ensemble-based or optimization-heavy rejection methods, REJEX maintains linear time complexity relative to the number of training samples. In empirical tests, it proved to be approximately 1,000 times faster than existing metric-based baselines, such as STABILITY, by avoiding expensive internal optimization loops.
Experimental Evaluation
To validate the effectiveness of REJEX, the authors conducted a comprehensive study across 34 benchmark datasets from the ADBench collection. These datasets span diverse sectors, including healthcare (disease diagnosis), finance (fraud detection), and industrial sensor data.
The framework was tested in conjunction with 12 different unsupervised anomaly detectors implemented via the PyOD library, including Isolation Forest, k-Nearest Neighbors (kNN), and Autoencoders. This broad evaluation ensures that the findings are detector-agnostic and applicable to various algorithmic approaches.
Key Results
- Cost Reduction: REJEX consistently achieved the lowest average cost per example compared to seven baseline methods, including "No Reject" and self-supervised approaches. Across various detectors, REJEX reduced relative costs by 5% to 19%.
- Superior Ranking: In head-to-head comparisons, REJEX secured the best average ranking across all 34 datasets for 9 out of the 12 detectors tested.
- Theoretical Alignment: A significant finding was the close alignment between experimental results and the theoretical upper bounds for rejection rates. This confirms that the mathematical guarantees provided by the authors are reliable for real-world deployment.
- The "Small Boundary" Insight: The research suggests that for most anomaly detectors, the zone of ambiguity near the decision boundary is relatively small. Most data points are classified with high stability, meaning that rejection is only necessary for a specific, narrow subset of ambiguous cases.
Limitations and Future Work
Despite its performance, REJEX has certain limitations. The method inherently produces a "strictly positive" rejection rate, meaning it will always identify some points for rejection. This may be a constraint for organizations with zero budget for human review. Additionally, the current cost model is coarse-grained; it assumes a general cost for errors rather than instance-specific costs (e.g., the varying financial impact of different fraud cases).
Future research may explore extending the REJEX framework to accommodate instance-specific costs or integrating it into active learning loops, where the samples rejected by the model are used to iteratively refine the detector's accuracy.
Conclusion
REJEX represents a significant step forward in making unsupervised anomaly detection more reliable and transparent. By shifting the focus from raw scores to prediction stability, it provides a mathematically grounded way for models to admit uncertainty. This "I don't know" capability allows for more efficient human-machine collaboration and reduces the overall cost of errors in critical diagnostic and monitoring tasks.
Summary updated