PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Isolation Forest for Anomaly Detection

Hongzuo Xu, Guansong Pang, Yijie Wang, Yongjun Wang

arXiv:2206.06602v4cs.LG

TL;DR

Linear isolation in iForest can miss hard anomalies and assign low scores to artefact regions, while existing extensions remain limited by linear partitions. DIF uses randomly initialized neural networks to create representation ensembles for subsequent random axis-parallel isolation. Across tabular, graph, and time-series datasets, experiments report significant improvements over isolation-based methods and deep-detector ensembles, while retaining scalability from iForest.

  • Problem

    iForest and its extensions remain limited in detecting hard anomalies and avoiding algorithmic bias because their isolation partitions are linear.

  • Method

    DIF maps data into random representation ensembles using casually initialized neural networks, then applies random axis-parallel cuts to obtain nonlinear partitions in the original space.

  • Results

    DIF significantly outperforms iForest, its extensions, and advanced deep anomaly-detector ensembles across tabular, graph, and time-series datasets, with desired scalability.

  • Takeaways & Limitations

    Random representations combined with random partition-based isolation provide a versatile approach for isolating hard anomalies across different data types.

  • Takeaways & Limitations

    Future work is needed for other challenging tasks, including abnormal-subset identification and multi-view data.

Abstract

from arXiv · show

Isolation forest (iForest) has been emerging as arguably the most popular anomaly detector in recent years due to its general effectiveness across different benchmarks and strong scalability. Nevertheless, its linear axis-parallel isolation method often leads to (i) failure in detecting hard anomalies that are difficult to isolate in high-dimensional/non-linear-separable data space, and (ii) notorious algorithmic bias that assigns unexpectedly lower anomaly scores to artefact regions. These issues contribute to high false negative errors. Several iForest extensions are introduced, but they essentially still employ shallow, linear data partition, restricting their power in isolating true anomalies. Therefore, this paper proposes deep isolation forest. We introduce a new representation scheme that utilises casually initialised neural networks to map original data into random representation ensembles, where random axis-parallel cuts are subsequently applied to perform the data partition. This representation scheme facilitates high freedom of the partition in the original data space (equivalent to non-linear partition on subspaces of varying sizes), encouraging a unique synergy between random representations and random partition-based isolation. Extensive experiments show that our model achieves significant improvement over state-of-the-art isolation-based methods and deep detectors on tabular, graph and time series datasets; our model also inherits desired scalability from iForest.

1 INTRODUCTION

The paper identifies hard-to-isolate anomalies and algorithmic bias as key limitations of linear isolation methods, then proposes DIF, which uses random neural representations before axis-parallel partitioning. Experiments across tabular, graph, and time-series datasets report improved detection, scalability, and robustness.

  • Problem: iForest can miss hard anomalies requiring joint feature combinations because each isolation operation considers only one feature.Ring-shaped normal samples can make anomalies indistinguishable from normal data in isolation depth.
  • Problem: iForest may assign low anomaly scores to artefact or “ghost” regions, causing possible anomalies to fall inside predicted normal areas.The paper links this bias to false negative errors.
  • Motivation: Existing iForest extensions improve splitting criteria but remain constrained by linear partitioning, limiting isolation on datasets requiring nonlinear partitions.The extensions use selective thresholds, dimensions, or hyper-planes, but their partitions remain linear.
  • Method: DIF maps original data into random representation spaces with casually initialized neural networks, then applies random axis-parallel cuts equivalent to nonlinear partitions in the original space.The representation ensemble introduces high partition freedom without network optimization or training.
  • Method: DIF adds CERE for scalable representation-ensemble construction and DEAS for anomaly scoring using quantitative deviation information from mapped representations.DEAS uses deviations from branching thresholds as indicators of local density and isolation difficulty.
  • Results: Extensive experiments show DIF significantly outperforms iForest and its extensions and advanced deep-detector ensembles across tabular, graph, and time-series datasets.The study also reports scalability on high-dimensional large-scale data, robustness to contamination, and support for ablation and synergy analyses.

2 RELATED WORK

Related work spans characteristic-based anomaly detection, isolation-forest extensions, scoring enhancements, and deep ensembles. The paper positions DIF as a representation-based ensemble that preserves diversity and computational efficiency through untrained networks.

  • Anomaly detection approaches: Anomaly detection research uses distance, density, clustering, probability, representation learning, reconstruction, and deviation-based approaches.Surveys and comparative studies organize these diverse methodological directions.
  • Isolation Forest: iForest identifies anomalies according to their isolating difficulty and is presented as a popular baseline with effective benchmark performance.Its appeal includes avoiding extra assumptions about data characteristics.
  • Isolation Forest extensions: iForest extensions modify branching through optimal or random hyper-planes, selective thresholds, and dimension choices, while remaining vulnerable to linear isolation limits.Scoring extensions also use path weighting, probability aggregation, or sparsity-based criteria.
  • Deep ensembles: Deep ensembles combine independently trained networks to improve prediction accuracy and provide uncertainty estimation, but their quality depends on member diversity and incurs greater computational cost.This motivates attention to diversity and efficiency in ensemble design.
  • Positioning of DIF: The paper’s neural-network integration maintains ensemble diversity and calculation efficiency because it requires only initialized networks.The authors suggest this may provide insights for deep-ensemble research.

3 PROBLEM STATEMENT AND NOTATIONS

The paper formulates anomaly detection as assigning abnormality scores to data objects and does not restrict the objects to a single data type.

  • Anomaly detection assigns each data object an abnormality score through a function f : D 7→R^N.
  • The framework covers multidimensional vectors, time series data, and graphs.
  • Table 1 summarises the paper’s main notations.

4 PRELIMINARIES: ISOLATION FOREST

iForest builds binary isolation trees using random feature-wise cuts and scores anomalies by their average path lengths, but its linear partitions and algorithmic bias limit detection.

  • iForest recursively partitions randomly subsampled data in binary trees until nodes contain one object or reach a depth limit.
  • Each split randomly selects one feature and a threshold, creating axis-parallel partitions.
  • Anomaly scores are based on the average traversed path length across the forest, with shorter paths indicating greater abnormality.
  • Existing linear isolation methods struggle with hard anomalies and generally suffer algorithmic bias from constraints in their isolation strategies.

5 DEEP ISOLATION FOREST

DIF maps data through randomly initialised neural networks into multiple representation spaces, then applies isolation trees there. CERE improves scalability, while DEAS enriches scoring with deviation information.

  • 5.1 Formulation of DIF: DIF constructs an ensemble of neural-network-derived representations and performs simple axis-parallel isolation in the resulting data spaces.
  • 5.1 Formulation of DIF: Each randomly initialised network maps original data into a new d-dimensional representation, with t iTrees assigned to each of r representations.
  • 5.2.1 CERE: CERE computes ensemble members simultaneously in mini-batches, making the ensemble process similar in time complexity to one neural-network feed-forward pass.
  • 5.2.1 CERE: CERE’s mini-batch process can require substantial memory; a 10,000-feature dataset uses about 3GB with r=50 and batch size b=64.
  • 5.2.2 DEAS: DEAS weights isolation difficulty using deviations between represented feature values and branching thresholds, which reflect local density in projected spaces.
  • 5.4 Computational Complexity: The representation process is linear in data size and dimensionality, while tree construction is linear in the ensemble size r×t under fixed typical J and n.
  • 5.3 Relationship with Existing Isolation Methods: DIF includes iForest and EIF as special cases when its representation network is a single linear layer.
  • 5.5.3 Synergy between Random Representations and Random Partition-based Isolation: Random representations diversify data spaces so that some spaces can make hard anomalies easier to isolate, supporting their emergence in averaged anomaly scores.

6 EXPERIMENTS

The experiments evaluate DIF across tabular, graph, and time-series anomaly detection tasks against isolation-based and deep ensemble competitors. They use AUC-ROC, AUC-PR, significance testing, and the Anomaly Isoability Index under stated implementation and computing settings.

  • Experimental Setup: DIF is evaluated on ten tabular, four graph, and four time-series datasets using publicly available real-world data.
  • Competing Methods: The comparison includes iForest extensions and ensemble versions of state-of-the-art deep anomaly detectors tailored to tabular, graph, and time-series data.
  • Implementation: DIF uses 50 random representations, six isolation trees per representation, and subsampling size 256, while IF-based competitors use 300 trees and subsampling size 256.
  • Computing Infrastructure: The implementation uses Python and runs on a workstation equipped with a Xeon Silver 4210R CPU, TITAN RTX GPU, and 64 GB RAM.
  • Evaluation: The experiments report AUC-ROC and AUC-PR, with paired Wilcoxon signed rank tests assessing DIF against each competitor.
  • Evaluation: The Anomaly Isoability Index measures the percentage of true anomalies effectively isolated in each representation space using random normal anchors and samples.

6.2 Effectiveness in Reducing False Negatives

DIF reduces false negatives relative to isolation-based methods and performs strongly against deep ensemble detectors. The reported advantages extend across tabular, graph, and time-series datasets, including a challenging ECG-w case.

  • Tabular Data: 61% average AUC-PR improvement over EIF and 144% over iForest are reported across ten tabular datasets.
  • Tabular Data: DIF significantly outperforms isolation-based methods at the 99% confidence level and is the best isolation-based detector on nine of ten tabular datasets for the reported metrics.
  • Tabular Data: DIF significantly outperforms deep ensemble-based methods by AUC-ROC at the 99% confidence level and leads on seven of ten datasets for both AUC-ROC and AUC-PR.
  • Graph Data and Time Series: DIF is the best performer on three of four graph and time-series datasets, including comparisons with data-type-specific deep detectors.
  • Graph Data and Time Series: On ECG-w, DIF is evaluated on a challenging wandering-baseline series alongside competitors using anomaly scores and highlighted anomalous heartbeats.

6.3 Scalability to High-dimensional, Large-scale Data

DIF retains favorable scalability on high-dimensional and large-scale synthetic tabular datasets. CPU results attribute the isolation methods’ scalability to subsampling, while GPU acceleration benefits deep ensembles.

  • Computing Platforms: The study reports training-time comparisons for DIF and deep ensemble methods on both CPU and GPU devices.
  • Experimental Design: The scalability tests vary dimensionality from 16 to 4,096 and dataset size from 1,000 to 256,000 objects.
  • CPU Scalability: On CPU, DIF and other isolation-based methods scale well with both dimensionality and data size compared with deep ensemble methods.
  • CPU Scalability: The reported CPU scalability is attributed to subsampling of both data samples and dimensions in isolation-based detectors.

6.4 Robustness w.r.t. Anomaly Contamination

As anomaly contamination increases, all evaluated detectors generally lose AUC-ROC performance. DIF nevertheless shows relatively clear superiority and stronger robustness on most datasets.

  • Experimental Design: The contamination experiment varies injected or removed anomalies from 0% to 10% in tabular training datasets.
  • Results: AUC-ROC generally decreases for all anomaly detectors as the training-set contamination ratio increases.
  • Results: DIF shows relatively clear superiority and stronger robustness on most datasets across contamination ratios.
  • Dataset-Specific Behavior: eREPEN shows an uptrend on Shuttle, where LeSiNN-based initial anomaly estimates may provide more positive examples as contamination increases.

6.5 Significance of the Synergy between Random Representations and Random Partition-based Isolation

The experiments examine whether random representations work synergistically with isolation-based scoring. DIF generally outperforms variants using optimised representations or alternative scoring methods, while performance depends on dataset characteristics.

  • Representation Scheme: DIF outperforms four optimised representation ensemble methods on five datasets and is highly competitive on the other five.Random representations improve AUC-ROC by 5%, 5%, 7%, and 15% over RDP-DIF, REPEN-DIF, DSVDD-DIF, and RECON-DIF, respectively.
  • Representation Scheme: Random representations provide diversity and randomness while maintaining stable expressiveness, supporting synergy with downstream isolation-based scoring.The paper identifies this combination as the main driving force behind DIF’s superior performance.
  • Representation Scheme: Optimised representations can have consistently good quality, but insufficient diversity can reduce the effectiveness of the ensemble framework.RECON-DIF isolates nearly 80% of true anomalies on Analysis, Backdoor, and DoS, yet its lack of diversity downgrades ensemble efficacy.
  • Representation Scheme: Optimisation can produce worse representations than random representations on R8, Cover, Pageblocks, and Thrombin.The paper suggests this may occur when assumptions underlying optimisation objectives, such as the one-class assumption, do not hold.
  • Scoring Strategy: DIF outperforms DIF-ECOD, DIF-KNN, and DIF-LOF on seven of ten datasets, with average AUC-ROC gains of 3%, 13%, and 25%.KNN and LOF require around 60 hours on the large-scale Cover and Fraud datasets.
  • Scoring Strategy: Alternative scoring methods can achieve better individual results on some datasets, but their integrated results are less effective or only slightly better than DIF’s.DIF exceeds 0.9 AUC-ROC on R8 even though the maximum individual score is around 0.7.
  • Scoring Strategy: DIF is inferior to its variants on Shuttle, where probability-, distance-, or density-based concepts may better identify anomalies.The paper cautions that these prior concepts may not work properly across all datasets.

6.6 Ablation Study on CERE and DEAS

The ablation study evaluates DEAS for detection effectiveness and CERE for training efficiency. DIF improves AUC-PR over the standard scoring ablation and substantially reduces training time through CERE.

  • DEAS: DIF significantly outperforms the w/o DEAS ablation at the 90% confidence interval and achieves approximately 11% AUC-PR improvement.w/o DEAS replaces DEAS with the standard iForest scoring function.
  • CERE: CERE reduces total training time across all ten datasets to approximately one-tenth of the w/o CERE variant.w/o CERE uses the conventional sequential ensemble process instead of GCERE.
  • CERE: The w/o CERE variant has AUC-ROC and AUC-PR results on par with DIF.Its results are omitted from the table because of space limitations.

7 CONCLUSIONS

The paper introduces DIF, which combines deep random representation ensembles with random partition-based isolation to expand the flexibility of isolation. Experiments report gains over isolation-based methods and deep anomaly-detector ensembles across multiple data types, while future work targets additional anomaly-detection tasks.

  • Conclusions: DIF uses casually initialised neural networks to create random representation ensembles, enabling versatile partitions through axis-parallel isolation in transformed spaces.The resulting partitions correspond to non-linear partitioning on subspaces of different sizes.
  • Conclusions: DIF is designed to improve isolation of hard anomalies, relax linear isolation constraints, and handle tabular, graph, and time-series data.The paper links these capabilities to the synergy between random representations and random partition-based isolation.
  • Conclusions: Extensive experiments show that DIF significantly outperforms iForest and its existing extensions and improves over ensembles of state-of-the-art deep anomaly detectors.The reported evaluations cover tabular, graph, and time-series datasets.
  • Future Work: Future work will develop scoring strategies and neural-network backbones for abnormal-subset identification and multi-view data.These are presented as additional challenging anomaly-detection tasks.
Loading 2206.06602v4…