SUOD: Accelerating Large-Scale Unsupervised Heterogeneous Outlier Detection

Yue Zhao, Xiyang Hu, Cheng Cheng, Cong Wang, Changlin Wan, Wen Wang, Jianing Yang, Haoping Bai, Zheng Li, Cao Xiao, Yunlong Wang, Zhi Qiao, Jimeng Sun, Leman AkogluMLSys 2021 · OpenReview

TL;DR

This paper introduces SUOD, a novel framework designed to significantly accelerate the training and prediction of large-scale, unsupervised, and heterogeneous outlier detection models. By addressing challenges at the data, model, and execution levels, SUOD offers a comprehensive solution that maintains accuracy while drastically reducing computational costs, making advanced outlier detection more practical for real-world applications.

What Problem Does This Paper Address?

Outlier detection (OD) is crucial for identifying anomalies in various fields like fraud detection and intrusion detection. However, the lack of ground truth labels often necessitates building numerous diverse OD models (heterogeneous ensemble) to ensure robustness. Training and scoring with these large ensembles on high-dimensional datasets is computationally prohibitive, especially for complex, proximity-based algorithms that suffer from the "curse of dimensionality." Existing approaches often tackle only specific aspects of this scalability challenge, leaving a gap for a holistic and practical acceleration solution.

Methods

SUOD tackles the acceleration problem through three independent yet complementary modules:

  • Data Level: Random Projection (RP): For high-dimensional data, SUOD employs Johnson-Lindenstrauss (JL) projection to reduce dimensionality. This preserves pairwise distances, induces diversity among feature spaces for heterogeneous models, and is computationally more efficient than methods like PCA.
  • Model Level: Pseudo-Supervised Approximation (PSA): To speed up prediction for costly unsupervised OD models, SUOD trains fast supervised regressors (e.g., Random Forests) to approximate their outputs. This "distills" knowledge from complex models into simpler ones, using the unsupervised model's output as "pseudo ground truth."
  • Execution Level: Balanced Parallel Scheduling (BPS): For distributed environments, SUOD addresses taskload imbalance. It uses a cost predictor to forecast model execution times and then schedules tasks to ensure a nearly equal workload distribution among workers, preventing bottlenecks.

Datasets

The paper evaluates SUOD on over 20 benchmark datasets, including:

  • Cardio
  • MNIST
  • Satellite
  • Satimage-2
  • Shuttle
  • SpamSpace
  • Waveform

These datasets vary in size (number of samples) and dimensionality. The authors also mention a real-world deployment on a proprietary pharmacy claim dataset from IQVIA for fraudulent claim analysis.

Key Insights and Ideas

  • Holistic Approach is Key: The paper argues that accelerating large-scale heterogeneous OD requires addressing data compression, model approximation, and efficient distributed execution simultaneously.
  • Random Projection for Diversity: Beyond dimensionality reduction, the inherent randomness of JL projection can be a valuable source of heterogeneity for ensemble methods.
  • Pseudo-Supervised Learning for Efficiency: Distilling knowledge from slow unsupervised OD models into fast supervised ones is a viable and effective strategy for accelerating prediction without significant accuracy loss, particularly for proximity-based methods.
  • Cost-Aware Scheduling Matters: Simply distributing tasks evenly in a heterogeneous ensemble setting is inefficient. Forecasting model costs and balancing workloads is crucial for maximizing throughput in distributed environments.
  • Approximation Benefits Some Models More: While PSA is generally effective, some models (like ABOD) are more complex to approximate than others (like kNN or LOF), suggesting that model characteristics influence the success of this technique.

Key Results

  • Time Reduction: SUOD achieved significant time reductions across various experiments. For instance, the BPS module alone showed time reductions of over 40% on large datasets with multiple cores. The full SUOD framework demonstrated time reductions of up to 32.57% in fitting and 24.40% in prediction on a real-world IQVIA dataset.
  • Accuracy Preservation: The acceleration modules, particularly RP and PSA, generally maintained or even slightly improved prediction accuracy (measured by ROC and P@N) compared to baseline methods.
  • RP Effectiveness: JL projection methods (circulant and toeplitz) outperformed original methods and PCA in terms of both time cost and prediction accuracy on high-dimensional datasets.
  • PSA Performance: Pseudo-supervised approximators often outperformed original unsupervised models in prediction accuracy, especially for kNN, LOF, and akNN.
  • BPS Efficiency: The balanced parallel scheduling significantly reduced training time compared to generic scheduling, especially with more workers and larger datasets.

Limitations and Future Work

  • Model Suitability for PSA: The paper notes that not all OD algorithms are equally suited for PSA. Models with very coarse decision surfaces (like ABOD) may not benefit as much or could even see performance degradation.
  • Offline Learning Focus: SUOD is primarily designed for offline learning with stationary data assumptions, though extensions to online settings are mentioned as a possibility.
  • Future Work:
  • Demonstrate SUOD's effectiveness with more complex downstream combination models (e.g., LSCP, XGBOD).
  • Further explore and emphasize the interpretability benefits of PSA beyond feature importance.
  • Conduct more theoretical investigations into why PSA works well for certain models (e.g., proximity-based) but not others (e.g., linear models).
  • Integrate emerging automated OD techniques (like MetaOD) to further optimize model selection and acceleration.

Summary updated

BibTeX
@inproceedings{zhao2021suod,
  author = {Yue Zhao and Xiyang Hu and Cheng Cheng and Cong Wang and Changlin Wan and Wen Wang and Jianing Yang and Haoping Bai and Zheng Li and Cao Xiao and Yunlong Wang and Zhi Qiao and Jimeng Sun and Leman Akoglu},
  title = {{SUOD: Accelerating Large-Scale Unsupervised Heterogeneous Outlier Detection}},
  booktitle = {MLSys},
  year = {2021},
  url = {https://openreview.net/forum?id=Pe1gxFR240l},
}
Figure