PaperlayerView exact revision on arXiv

Source-linked AI summary

RIFT: Relative Isolation From Trees For Anomaly Detection

Mark Daniel Szalai, Gabor Horvath

arXiv:2610.12244v1cs.LG

TL;DR

Supervised anomaly detection requires labeled data and can overfit known anomaly patterns, missing novel outliers. RIFT scores points using a minimum spanning tree; its accuracy is competitive with Isolation Forest, and its ensemble has lower variance across random seeds.

  • Problem

    Supervised anomaly detection requires substantial labeled data and can overfit known anomaly patterns, making it blind to novel outliers.

    Source: §1 · p. 2

  • Method

    RIFT represents data with a Euclidean minimum spanning tree and scores each point by the apparent sizes of tree edges viewed from it.

    Source: §4.1 · p. 6, §6 · p. 21

  • Results

    RIFT achieves accuracy competitive with Isolation Forest on synthetic data and ADBench, while its ensemble's score variance across random seeds is an order of magnitude lower at the same ensemble size.

    Source: §6 · p. 21

  • Takeaways & Limitations

    In one dimension RIFT recovers the infinite-tree Isolation Forest output; in higher dimensions its deterministic score avoids IF's axis-parallel artifacts.

    Source: §6 · p. 21

    Exact MST construction's computational and memory demands limit its application to moderate-sized datasets, and a single global MST becomes impractical for N ≫10^4.

    Source: §4.2 · p. 7, §4.3 · p. 7

Abstract

from arXiv · show

Isolation Forest (IF) is a widely used baseline for unsupervised anomaly detection. Recent studies provide a closed-form expression for the infinite-forest limit for one-dimensional data. Inspired by the geometric interpretation of this formula, we introduce RIFT (Relative Isolation From Trees), a deterministic anomaly detection method that generates the minimum spanning tree and scores each point by the sum of the apparent sizes of tree edges as viewed from that point. For one-dimensional data, the RIFT score recovers the closed-form IF limit exactly. In higher dimensions, it provides a parameter-free generalization that is deterministic, robust to varying density and clustered anomalies and avoids the axis-parallel artifacts of IF. We further propose an ensemble variant for large datasets. Experiments on synthetic data and the ADBench benchmark demonstrate that the accuracy is comparable to IF, while the ensemble variant exhibits significantly lower variance across random seeds.

1 Introduction

The paper addresses unsupervised point-anomaly detection in tabular data, where labeled training data may be impractical and supervised models can miss novel outliers. It introduces a deterministic geometric method related to Isolation Forest that matches IF’s infinite-tree limit in one dimension.

1 Introduction

  • Anomalies can be either errors to remove or valuable signals of disease, cyberattacks, or equipment malfunctions.Source: §1 · p. 2
  • RIFT targets point anomalies in multidimensional tabular data without assuming sequential or temporal structure among samples.Source: §1 · p. 2
  • Supervised anomaly detection requires labeled training data and can overfit known anomaly patterns, leaving novel outliers undetected.The proposed method is strictly unsupervised and uses intrinsic data properties without pre-labeled training data.Source: §1 · p. 2
  • In one dimension, the method exactly matches Isolation Forest’s infinite-tree result; in higher dimensions, it uses deterministic geometric distances instead of random recursive partitioning.Source: §1 · p. 2
  • The paper evaluates its approach on synthetic data and ADBench against widely used anomaly detectors.Source: §1 · p. 2

2 Related work

Related methods span different assumptions about subspaces, boundaries, neighborhoods, density, distributions, and ensembles. RIFT is closest to geometric distance-based detectors but derives its score from a minimum spanning tree rather than random partitions or explicit density models.

2 Related work

  • PCA detects outliers through reconstruction error or distance to a low-dimensional subspace, while One-Class SVM encloses the bulk of data with a decision boundary.Source: §2 · p. 3
  • KNN uses neighbor distances, LOF compares local densities, and CBLOF scores points by cluster size or distance from large clusters.Source: §2 · p. 3
  • HBOS uses per-feature histograms, while COPOD and ECOD use copulas or empirical cumulative distribution functions for parameter-light scoring.Source: §2 · p. 3
  • IF uses random recursive partitioning, while LODA combines random projections with histograms; RIFT instead derives its score from a possibly approximated MST.Source: §2 · p. 3

3 Isolation Forest

Isolation Forest scores points by how readily random recursive partitioning isolates them. For one-dimensional data, its expected depth has an exact spacing-based expression, but extending that solution to higher dimensions is not straightforward.

3.1 The basic algorithm

  • Isolation Forest builds trees by randomly selecting a feature and split value, then recursively partitioning sampled data until leaves or a depth limit are reached.Source: §3.1 · pp. 3–4
  • The forest averages each point’s path length and normalizes it by an unsuccessful binary-search-tree path length; shorter expected paths yield higher anomaly scores.Source: §3.1 · p. 4

3.2 Explicit solution for one-dimensional data

  • For ordered one-dimensional data, the infinite-tree expected path length has an exact expression in terms of adjacent spacings, allowing the anomaly score to be computed from sample geometry.Source: §3.2 · p. 4
  • The one-dimensional expression does not extend trivially: higher-dimensional expected depth depends on the full point configuration, and the state space grows rapidly with dimension.Source: §3.2 · pp. 4–5

4 Description of the proposed method

RIFT turns the one-dimensional geometric interpretation of Isolation Forest into an MST-based score that sums edges’ apparent sizes from each point. It extends this construction to higher dimensions and offers an ensemble variant for larger datasets.

4.1 Concept of the algorithm

  • RIFT generalizes the 1D apparent-size sum to higher dimensions by using a Euclidean minimum spanning tree as the data’s topological backbone.Source: §4.1 · pp. 5–6
  • In 1D, the MST score exactly recovers the closed-form solution, while its edge-to-distance quotient is density-invariant.Source: §4.1 · pp. 6–7

4.2 The exact solution using MST

  • The exact method builds the MST once and traverses it from each sample; its construction cost and memory needs limit it to moderate datasets.Source: §4.2 · p. 7

4.3 Using MST approximations

  • For larger datasets, RIFT approximates the MST on a sparse kNN graph, increasing k until connected; duplicates can force large k, so it uses unique samples and maps duplicates back.Source: §4.3 · pp. 7–8

4.4 Ensemble-based implementation

  • The ensemble builds independent trees from random instance subsets and feature subspaces, then scores each target by attaching it to each tree and averaging its apparent-edge-size scores.Source: §4.4 · pp. 8–9
  • Sub-sampling and feature bagging reduce computational overhead and address masking, swamping, and noisy dimensions; the forest also has lower score variance than Isolation Forest.Source: §4.4 · p. 9

5 Numerical study

The numerical study evaluates RIFT on synthetic data and ADBench, including comparisons with Isolation Forest and tests of the ensemble’s behavior. RIFT performs strongly across synthetic anomaly patterns, while the ADBench results show competitive accuracy alongside a variance and runtime trade-off.

5 Numerical study

  • The numerical experiments use median/MAD robust scaling on unique data points because Euclidean-distance-based RIFT is sensitive to feature scaling and extreme outliers.Source: §5 · p. 10

5.1 Anomaly heatmaps with synthetic data

  • Across synthetic anomaly regimes, Isolation Forest and RIFT achieve high ROC AUC, while LOF/KNN and HBOS/ECOD show opposing strengths across datasets.The three datasets represent Gaussian blobs, varying density, and a tight anomaly cluster.Source: §5.1 · p. 11
  • RIFT produces a smooth anomaly surface without the axis-parallel artifacts of Isolation Forest and HBOS or the radial artifacts of LOF.The heatmaps also show KNN assigning normal scores too quickly to anomalies near a cluster.Source: §5.1 · p. 12

5.2 Evaluation of the ensemble based approach

  • With more than 100 trees, ensemble variance approaches zero; few-tree configurations have AUC close to much larger forests, and the ensemble generally approximates exact MST performance more efficiently.On the satellite dataset, however, the ensemble performed significantly worse than exact RIFT, possibly because small subsamples miss the global manifold.Source: §5.2 · p. 14
  • Feature bagging has a substantial effect on performance and variance: high ratios suit datasets with informative features, while mammography and mnist score best at 0.6 and 0.2, respectively.The authors report feature bagging as the hyperparameter with the most pronounced effect on increasing result variance.Source: §5.2 · p. 16

5.3 Evaluation on the ADBench datasets

  • For datasets exceeding 20,000 instances or 500 features, PCA, OCSVM, KNN, LOF, and exact RIFT were omitted because they could not finish within a reasonable timeframe.Source: §5.3 · p. 17
  • 0.7634 versus 0.7632: RIFT ensemble and Isolation Forest have statistically indistinguishable mean AUC on the full ADBench collection; their relative standard deviations are 0.0014 versus 0.0212.On smaller datasets, Isolation Forest has a marginal mean AUC lead: 0.7561 versus 0.7526 for RIFT exact and 0.7518 for RIFT ensemble.Source: §5.3 · pp. 17, 19, Table 8 · p. 19
  • RIFT ensemble is slower than Isolation Forest, especially on high-dimensional datasets, but reducing the tree count from 256 to 4 cuts runtime by nearly two orders of magnitude with minimal AUC loss.The RIFT ensemble is 10–30 times slower on InternetAds, census, and backdoor, and 2–4 times slower on http, smtp, and skin.Source: §5.3 · pp. 19, 21

6 Conclusions

RIFT derives an anomaly score from Euclidean minimum-spanning-tree edge sizes, exactly recovering the infinite-tree Isolation Forest result in one dimension. Across synthetic data and ADBench, its accuracy is competitive with IF, with deterministic variants and an ensemble whose seed-to-seed score variance is an order of magnitude lower.

6 Conclusions

  • RIFT scores each point by summing the apparent sizes of Euclidean minimum-spanning-tree edges, exactly matching the infinite-tree IF output in one dimension.In higher dimensions, its deterministic distance-based construction replaces IF's random recursive partitioning and avoids density dependence and axis-parallel artifacts.Source: §6 · p. 21
  • RIFT offers a global-MST exact method, a k-nearest-neighbor-graph approximation, and a sub-sampled ensemble with feature bagging.The exact and approximate variants are deterministic; the ensemble trades determinism for scalability and robustness, with randomness confined to instance and feature sampling.Source: §6 · p. 21
  • On synthetic data and ADBench, RIFT achieves accuracy competitive with IF while offering deterministic scoring and an ensemble with an order-of-magnitude lower seed variance.The lower variance is reported for the ensemble at the same ensemble size as IF.Source: §6 · p. 21

Appendix A The derivation of the explicit solution of the 1D Isolation Forest

The appendix derives the expected path length of a one-dimensional isolation-tree sample under distinct ordered values, full-sample trees, and uniform split selection. It sets up a recursion by conditioning on the first split, then verifies the explicit solution algebraically.

Appendix A

  • The derivation assumes distinct, ordered sample values, trees grown on all samples without a height limit, and split values drawn uniformly within each node's range.Under these conditions, the appendix defines H(i) as the forest-averaged expected path length in the infinite-tree limit.Source: Appendix A · p. 24
  • Conditioning on the first split expresses the expected path length recursively for a subset x_ℓ through x_u containing x_i.The split contributes one path-length unit; interval probabilities weight the remaining subproblem, with zero path length at the singleton boundary.Source: Appendix A · p. 24
  • The appendix states an explicit formula for H(i) and verifies the proposed expression by substitution into the recursion and swapping the sums.Since H(i) equals H_1,N(i), the resulting identity establishes the theorem for the full sample.Source: Appendix A · p. 25

Related papers

Loading 2610.12244v1…