Deep Isolation Forest for Anomaly Detection

In plain words

Isolation forest finds unusual points by cutting the data at random and counting how few cuts it takes to leave a point alone. Odd points get cut off quickly. The catch is that each cut is straight and works on one column at a time. A point that is unusual only in a combination of columns, such as a point sitting inside a ring of normal points, is not cut off any faster than a normal point.

Deep Isolation Forest keeps the cutting game but changes the space first. It feeds the data through several neural networks that are never trained: they keep their random starting weights. Each network reshapes the data into a new space, and a straight cut in that new space becomes a curved cut in the original space. In some of these reshaped spaces the hidden outliers are easy to cut off, so the forest finds them there.

Each point gets a score from how quickly it is isolated across all these spaces, adjusted by how far it sits from the cuts that separated it. The same recipe is used for tables, graphs and time series; only the network changes.

TL;DR

Deep Isolation Forest (DIF) builds 50 random, untrained representations of the data, grows 6 isolation trees on each, and scores points by path depth times a deviation term. Author-reported, its average AUC-ROC and AUC-PR on ten tabular datasets (0.925 and 0.351) are above the isolation-based and deep-ensemble baselines in the paper. Relevant if you need an unsupervised detector with no training loop. Before reimplementing, read "Paper vs code": the released scoring differs from eq. 8, and inference standardises each representation with whatever batch is scored.

Problem

Isolation forest (iForest) isolates each point with random cuts on one feature at a time, so the path length to isolate a point reflects how alone it is along single axes §4. Two failures follow §1:

• Hard anomalies. Anomalies that only separate from normal data in combinations of features, such as a ring of normal points around a few anomalies, are isolated no faster than normal points. This gives false negatives §1 fig. 1.
• Algorithmic bias. Empty regions near normal data get unexpectedly low scores ("ghost regions"). The paper shows this on three 2-D synthetic sets §1 fig. 2.

Extensions such as SCIF, EIF and PID, and probabilistic split rules, still use linear partitions or heuristic axis choices, so the authors argue they keep both failures §1 §2.2. The method takes unlabelled data of any type: the problem is defined for vectors, time series and graphs alike §3. The released fit method ignores labels dif.py.

Method

DIF has two stages §5:

1. A random representation ensemble maps the data into r spaces of width d using networks whose weights are random and never trained §5.1 eq. 1.
2. t isolation trees are grown on each space, each on a random subsample of n points §5.1 alg. 1. A test point is mapped through the same networks and its path depth and deviation in every tree are combined §5.2.2 eq. 8 alg. 2. There are T = r × t trees in total §5.1.

The paper reports the ensemble as r separate networks eq. 1, but its efficient implementation (CERE) shares one base weight matrix and gives each member a pair of random vectors §5.2.1. For a layer with base weight W0 and member vectors p_i, q_i §5.2.1:

\mathbf{W}_i = \mathbf{W}_0 \circ (\bm{p}_i \bm{q}_i^\top) eq. 3

\mathbf{W}_i^\top \bm{x} = \mathbf{W}_0^\top (\bm{x} \circ \bm{p}_i) \circ \bm{q}_i eq. 4

Stacking the r members over a mini-batch of b points gives one batched computation (the paper's matrix form uses P_i = 1_b p_i^T and Q_i = 1_b q_i^T) §5.2.1 eq. 5. The whole ensemble is then one network with parameters Θ = {W_l, {p_(l,i)}, {q_(l,i)}} §5.2.1 eq. 6. Activations and layers without weight matrices are applied in the usual sequential way §5.2.1.

Splitting (alg. 1). Each node with more than one point and depth below J picks one dimension uniformly among the d representation dimensions and a split value uniformly between that dimension's minimum and maximum in the node. Values at or below the split go left, the rest go right alg. 1 §5.1. The paper takes J and n as typically 8 and 256 §5.4.1.

Scoring (alg. 2, eq. 7–8). For each tree, the point's path gives a depth |p| and a deviation g: the mean absolute gap between the point's value and the split threshold at each node on its path eq. 7. The score multiplies a normalised depth term by the mean deviation, and both are averaged over all trees eq. 8:

g(\bm{x}_u \mid \tau_i) = \frac{1}{|p(\bm{x}_u \mid \tau_i)|} \sum_{k \in p(\bm{x}_u \mid \tau_i)} \left| \bm{x}_u^{(j_k)} - \eta_k \right| eq. 7

\mathscr{F}_{\text{DEAS}}(\bm{o} \mid \mathcal{T}) = 2^{-\mathbb{E}_{\tau_i \in \mathcal{T}} \frac{|p(\bm{x}_u \mid \tau_i)|}{C(T)}} \times \mathbb{E}_{\tau_i \in \mathcal{T}}\big(g(\bm{x}_u \mid \tau_i)\big) eq. 8

The paper calls the first term the iForest depth score and the second the deviation score §5.2.2. C(T) is a normaliser that the paper does not define eq. 8; see Pitfalls. The generic score form is F(o | T) = Ω I(o | τ_i) with Ω an aggregation over trees eq. 2.

The following pseudocode gives the paper's method in our words. Where the released code differs, the line is marked and explained in "Paper vs code".

# Random representation ensemble, batched (CERE)  [§5.2.1] [eq. 3-5]
# Input:  batch (b, D); layers with base weight W0; r member vector pairs
# Output: r representations, each (b, d)

def represent_ensemble(batch, layers, r):
    # repeat the batch once per member  [§5.2.1] [eq. 5]
    hidden = tile(batch, times=r)                   # (r*b, D)
    for layer in layers:
        # scale inputs by member vector p_i  [§5.2.1] [eq. 4]
        hidden = hidden * layer.input_scale_per_row(r, b)
        # shared base weight, no bias  [§5.2.1] [eq. 3]
        hidden = hidden @ layer.base_weight         # (r*b, out)
        # scale outputs by member vector q_i  [§5.2.1] [eq. 3]
        hidden = hidden * layer.output_scale_per_row(r, b)
        # hidden layers use tanh; the last layer stays linear
        # [code: algorithms/net_torch.py#L78]
        if layer is not layers[-1]:
            hidden = tanh(hidden)
    # split back into r representations of width d  [§5.2.1] [eq. 5]
    return split(hidden, parts=r)

# Post-processing applied by the released code, not by the paper
# [code: algorithms/dif.py#L320-L323]

def standardise_representations(reps):
    # z-score each member over all rows passed in  [code: dif.py#L322]
    scaled = [standardise(rep) for rep in reps]
    # squash to (-1, 1) with tanh  [code: algorithms/dif.py#L323]
    return [tanh(rep) for rep in scaled]

# Build one isolation tree on a subsample  [alg. 1] [§5.1] [§5.4.1]
# Input:  points (m, d) from one representation; depth limit J
# Output: tree whose internal nodes hold a dimension and a split value

def build_tree(points, depth_limit):
    # stop at one point or when the depth limit is reached  [alg. 1]
    if len(points) <= 1 or depth_limit == 0:
        return leaf(size=len(points))
    # pick one dimension uniformly at random  [alg. 1] [§5.1]
    dim = random_index(points.shape[1])
    # pick a split uniformly between the min and max of that dimension
    # [alg. 1]
    low = min(points[:, dim])
    high = max(points[:, dim])
    threshold = uniform(low, high)
    # values at or below the split go left  [§5.1]
    left = points[points[:, dim] <= threshold]
    right = points[points[:, dim] > threshold]
    return node(dim, threshold,
                build_tree(left, depth_limit - 1),
                build_tree(right, depth_limit - 1))

# Fit the forest: t trees per representation  [alg. 1] [§5.1] [§6.1.3]
# Input:  data (N, D); r, t, subsample size n, depth limit J
# Output: list of r * t trees

def fit_forest(data, r, t, n, J):
    # r random representations; no gradient steps  [§5.1] [eq. 1]
    reps = represent_ensemble(data, layers, r)
    forest = []
    for rep in reps:
        for _ in range(t):
            # subsample n rows for this tree  [alg. 1] [§5.1]
            subset = sample_rows(rep, n)
            forest.append(build_tree(subset, J))
    return forest

# Deviation-enhanced anomaly score for one object  [§5.2.2] [eq. 7-8] [alg. 2]
# Input:  object x, forest, normaliser C
# Output: score (higher = more anomalous)

def deas_score(x, forest, normaliser):
    reps = represent_ensemble(x, layers, r)
    depths = []
    deviations = []
    for rep, tree in pair_trees_with_reps(forest, reps):
        # walk from the root to a leaf, keeping each split on the path
        # [alg. 2]
        path = walk(tree, rep)                  # list of (dim, threshold)
        # path length |p| counts the splits passed  [alg. 2] [eq. 8]
        depths.append(len(path))
        # mean gap between the point and each split on its path  [eq. 7]
        gaps = [abs(rep[dim] - thr) for dim, thr in path]
        deviations.append(mean(gaps))
    # depth term: 2 to the minus mean depth over C  [eq. 8]
    depth_term = 2 ** (-mean(depths) / normaliser)
    # paper: average over all trees, then multiply  [eq. 8]
    # code: multiply per representation, then average  [see Paper vs code]
    return depth_term * mean(deviations)

Hyperparameters

The paper fixes the ensemble sizes but not the networks. Values in the code are listed separately; the tabular runs in main.py use them.

Results

Author-reported. Ten tabular datasets tab. 2 §6.1.1; four graph sets derived from Tox21 (HSE, MMP, p53, PPAR) and four UCR time-series sets (Mars, Gait, ECG, ECG-w) §6.1.1. Metrics are AUC-ROC and AUC-PR, compared with the paired Wilcoxon signed-rank test §6.1.4. The paper does not state the number of runs.

Tabular, against isolation-based methods (mean over the ten sets) tab. 3:

The text gives relative AUC-PR gains of 61% over EIF, 186% over PID, 56% over LeSiNN and 144% over iForest §6.2.1. PID and EIF run out of memory on Thrombin, which has 139,352 features tab. 3 tab. 2.

Tabular, against deep ensembles tab. 4:

DIF is best on seven of ten datasets on both metrics §6.2.1. Exceptions in tab. 3 and tab. 4: AUC-PR on Fraud goes to LeSiNN (0.401 against 0.387), and eDSVDD is ahead on Cover in both metrics in tab. 4. The paper reports the AUC-ROC difference from the deep ensembles as significant at the 99% level §6.2.1.

Graph and time series tab. 5 (the "best other" columns were computed by the compiler from tab. 5; they are not in the paper):

The paper says DIF is best on three of four datasets in each of the graph and time-series groups §6.2.2. For these groups DIF uses the GIN and dilated-CNN structures of InfoGraph and TS2Vec with no optimisation step §6.2.2.

Ablations tab. 6 §6.6:

The authors report AUC-ROC and AUC-PR p-values of 0.07 and 0.03 for DIF against w/o DEAS tab. 6. Ablated AUC-ROC and AUC-PR are not reported for w/o CERE, since they match DIF's §6.6.

Synergy between representations and scoring §6.5: with DIF's random representations, average AUC-ROC is 5%, 5%, 7% and 15% higher than with the optimised representations of RDP, REPEN, DSVDD and RECON §6.5.1. With DIF's isolation score, it is 3%, 13% and 25% higher than with ECOD, KNN and LOF scores §6.5.2. The authors report that KNN and LOF took about 60 hours on Cover and Fraud §6.5.2.

Quality metric (used for the bottom panel of fig. 7):

AII = \mathop{\mathbf{P}}\limits_{\bm{a} \sim \mathcal{A}} \Big( \mathop{median}\limits_{\bm{n}_i \in \mathcal{N}} \Big\{ \frac{1}{|\mathcal{C}|} \sum_{\bm{n}_j \in \mathcal{C}} \omega(\bm{a} \mid \bm{n}_i, \bm{n}_j) \Big\} > 0 \Big) eq. 9

Here ω(a | n_i, n_j) = d(a, n_i) − d(n_j, n_j) as printed eq. 9 §6.1.4; see Pitfalls. The paper defines it as the share of true anomalies that are isolated in a given representation §6.1.4.

Robustness and scalability. Robustness is shown as AUC-ROC against contamination from 0% to 10% §6.4 fig. 6; the text calls DIF "relatively clear" in most sets, with no table of values §6.4. Scalability is shown on synthetic data with up to 4,096 features and 256,000 rows §6.3 fig. 5; the text says DIF is about two orders of magnitude faster than the deep ensembles §6.2.1, and no timing values appear in the text.

Paper vs code

Repository: github.com/xuhongzuo/deep-iforest, linked from the paper §6.1.3, owned by the first author, at code_commit above. Its LICENCE file is Apache 2.0. The README points to the DeepOD library, which also includes DIF; not assessed here.

• Final score aggregation differs. Code scores each representation separately, forming 2^(-mean depth / c) × mean deviation over its six trees, and then averages those products over representations dif.py dif.py dif.py. Eq. 8 instead takes the exponential of the mean depth and multiplies it by the mean deviation, both over all T trees §5.2.2 eq. 8. The two agree only when every representation gives the same depth and deviation terms.
• Depth includes a leaf-size correction. Code computes depth as the number of nodes on the path plus c(n_leaf) − 1, where n_leaf is the number of training points in the leaf. That is the usual iForest path length. The paper's |p| counts only the nodes on the path and has no correction dif.py §5.2.2 eq. 7.
• Normaliser. Code divides by c(max_samples_), the average path length for the subsample actually used, which is min(256, N) (scikit-learn stores this as max_samples_). The paper writes C(T) and does not define it dif.py eq. 8.
• Representations are standardised and squashed. Each member is z-scored over the rows passed in, then passed through tanh. Neither step is in the paper dif.py dif.py §5.2.1.
• Scoring standardises over the scored batch. Because the z-scoring runs on whichever rows are passed to decision_function, a point's score can depend on the batch it arrives in. Code also returns the cached training representations whenever a tabular call has the same number of rows as the training set, without checking the content dif.py.
• Concatenation skip connections. The CLI default turns on concat skip connections for the tabular MLP, so each hidden layer's output is concatenated with its input parser_utils.py parser_utils.py net_torch.py net_torch.py. The class default is no skip connection dif.py. The paper says nothing about skips.
• No bias terms and N(0, 1) weights in the tabular MLP. Linear layers have no bias, and every weight tensor is drawn from N(0, 1) net_torch.py net_torch.py dif.py.
• Batch-ensemble path only for tabular. The paper presents CERE as the method's implementation §5.2.1. Time-series and graph runs set new_ensemble_method to 0, so each member is a separate network main_ts.py main_graph.py dif.py.
• Graph encoder keeps BatchNorm in training mode. The GIN encoder has BatchNorm layers net_torch.py. The repository never calls .eval(), so BatchNorm normalises with batch statistics during scoring dif.py. The paper does not mention this.
• Time-series scores are point-adjusted. eval_ts returns only metrics computed after point adjustment, where each true anomaly segment takes its maximum score utils.py utils.py. The paper does not say whether its time-series numbers use point adjustment.
• Time-series first points are zero. The first 99 scores of each series are set to 0 before evaluation main_ts.py.
• Graph anomaly class. The anomaly class is the minority label in the test set main_graph.py. The paper calls them "abnormal graphs" without naming the class §6.1.1.
• Global random state. set_seed seeds NumPy, PyTorch and Python's random globally dif.py, so calling DIF changes the host program's random state.
• Trees come from scikit-learn. Trees are built by scikit-learn's IsolationForest with max_samples and random_state set; depth, feature selection and sampling use its defaults dif.py. Those defaults were not checked against any particular scikit-learn version.
• Tabular runs are in-sample. main.py fits on all rows, then scores the same rows, after min-max scaling fit on all rows main.py main.py utils.py.

No discrepancies found for the ensemble sizes (50, 6, 256) and batch size (64), which match the code defaults §6.1.3 config.py.

Pitfalls

• Score formula. Decide up front whether to implement eq. 8 or the released code; they differ in aggregation, depth correction and normaliser (see "Paper vs code"). With C(T) undefined, the normaliser is the largest unknown in eq. 8. The code's c(min(256, N)) changes with dataset size for datasets under 256 rows.
• Algorithm 2 needs node sizes. Algorithm 2 stops when a node holds one point or fewer, which needs the training pool size at each node. At scoring time this is not available unless it is stored. The released code uses the tree's leaf structure instead alg. 2 dif.py.
• Algorithm 2 indexing. Algorithm 2 updates k to the child before it adds |x − η_k| to β, so read literally it uses the child's split value. Eq. 7 and the code use the threshold of the node where the decision is made alg. 2 eq. 7.
• Batch dependence at inference. Standardisation is fit on the scored batch dif.py. Score a single point on its own and the result can differ from scoring it in a batch. Use the same fit set for all queries, or the same batch for comparisons.
• Cached representations. For tabular data, a decision_function call on any batch with the same row count as the training set returns scores computed from the training representations dif.py. This is a silent error if you score new data of the same size.
• Memory of the batched ensemble. The batched ensemble tiles each mini-batch r times, so b = 64 and r = 50 means 3,200 rows per forward pass net_torch.py (computed from the code). The paper's example is about 3 GB for 10,000 features at r = 50, b = 64 §5.2.1. Thrombin has 139,352 features tab. 2.
• Cost of tree building. The paper's bound for building the forest is O(2^(J-1) × n × r × t) §5.4.1. Its "linear in r × t" claim treats J and n as fixed, as the paper does.
• Runs and variance. The paper reports mean ± standard deviation but does not give the number of runs §6.1.4. The code runs once by default main.py.
• Time-series numbers. The paper does not say whether point adjustment was used for its time-series table, and the code reports only adjusted metrics utils.py. Re-run with unadjusted AUC before comparing.
• Graph BatchNorm. Graph scores depend on batch composition through BatchNorm, not only through the data net_torch.py.
• Eq. 9 as printed. In the source, the distance term is written d(n_j, n_j), which compares a point with itself; the other term is d(a, n_i). The intended second term is not stated, so check the published version before implementing AII eq. 9 §6.1.4.
• Unstated values. Hidden widths, activation, skip connections, representation width and weight distribution are not in the paper. The code's choices are listed in Hyperparameters; they are not verified against the paper's figures.
• Ensemble diversity. Optimised representations can be better on some datasets and worse on others §6.5.1; the paper argues the gain comes from diversity across random members §5.5.3. This is an argument from experiments on ten tabular sets, not a theorem.

Lineage

• Builds on: the isolation forest of Liu et al. (2008), whose path-length score DEAS extends §4 §5.4.2; the generalisation to hyperplanes in the Extended Isolation Forest of Hariri et al. (2019), which DIF is shown to generalise §5.4.2; the BatchEnsemble method of Wen et al. (2019), which CERE adapts §5.2.1.
• Compared against: iForest, EIF, PID and LeSiNN §6.1.2; ensembles of RDP, REPEN, DSVDD, RECON and GLocalKD, and TranAD for time series §6.1.2; InfoGraph and TS2Vec representations for the isolation baselines on graph and time-series data §6.1.3.
• Superseded by: not stated in the paper. The repository README points to the DeepOD library, which includes DIF; not assessed here.