RIFT: Relative Isolation From Trees For Anomaly Detection

arXiv:2610.12244 · cs.LG · Submitted 2026-10-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "RIFT: Relative Isolation From Trees For Anomaly Detection".

Tom: The gist The proposed method RIFT introduces a deterministic anomaly detection method that generates a minimum spanning tree and scores each point by the sum of the apparent sizes of…

Jane: First, who's behind it and why it matters.

Paper summary: Tom: So we're looking at RIFT today, which stands for Relative Isolation From Trees For Anomaly Detection. This paper comes from Daniel Szalai and Gabor Horvath from Budapest University of Technology and Economics. It introduces this method as a deterministic way to find anomalies that works in higher dimensions too, unlike some other methods <ref:2610.12244#pg1>.

Jane: Right, so the main thing here is that they take something that worked for one dimension and try to make it work generally. They're building this method using a minimum spanning tree and scoring each point based on the sum of those tree edges as viewed from that point <ref:2610.12244#pg1>.

Lu: It’s interesting because they are taking the geometric interpretation of some closed-form expression for the infinite-forest limit in one dimension and translating that into a deterministic structure <ref:2610.12244#pg1>. This gives it a specific mathematical foundation beyond just being a heuristic.

Meng: But how does this actually compare to what we already have, like the Isolation Forest, which is the baseline they are comparing against? We need to know if this deterministic approach is really better in practice <ref:2610.12244#pg1>.

Tom: The paper claims that for one-dimensional data, RIFT recovers the closed-form infinite-forest limit exactly <ref:2610.12244#pg1>. And then, they argue that for higher dimensions, it gives you a parameter-free generalization that is deterministic and avoids those axis-parallel artifacts you see in the Isolation Forest <ref:2610.12244#pg1>.

Jane: That sounds like a big deal because those artifacts mean the method behaves differently depending on how you orient your data, which is something we often try to avoid in anomaly detection <ref:2610.12244#pg3>.

Lalam: I see the paper also proposes an ensemble variant for large datasets, which they call RIFT <ref:2610.12244#pg1>. This sounds like they are trying to make it more robust for massive amounts of data <ref:2610.12244#pg1>.

Tom: Exactly, and the ensemble variant is what really catches my eye because they say it exhibits significantly lower variance across random seeds compared to the Isolation Forest when you use the same ensemble size <ref:2610.12244#pg1>. That suggests it’s more stable than IF <ref:2610.12244#pg3>.

Jane: It means if you run this on a big dataset and get a slightly different score because of random sampling, the result stays much closer to the true anomaly score <ref:2610.12244#pg3>. That robustness is important when you’re not sure about the underlying data structure.

Paper summary: Lu: The geometric interpretation they use involves rewriting h-bar of xi as X k,k!=i dk over l k, which they interpret as the one-dimensional apparent size or visual angle of a segment dk observed from the target point xfour <ref:2610.12244#pg1>. It’s turning the complexity into something visual and spatial <ref:2610.12244#pg3>.

Meng: From an engineering standpoint, they propose three variants for implementation, including one that builds a complete graph where the weight is the squared Euclidean distance between points <ref:2610.12244#pg1>. That sounds computationally heavy if you have a huge number of data points <ref:2610.12244#pg3>.

Tom: Well, they address that with another variant, using a sparse k-nearest-neighbor graph to approximate the minimum spanning tree, which reduces the complexity from n squared down to n times k <ref:2610.12244#pg1>. That’s a practical way to handle the scale issue <ref:2610.12244#pg3>.

Jane: And they also have this ensemble approach using M independent Minimum Spanning Trees built from small random subsets of data instances psi and randomly selected feature subspaces Fj to compute the score h-bar of xi, Tj <ref:2610.12244#pg1>. That sounds like a lot of computational work, but they are trading that for variance reduction <ref:2610.12244#pg3>.

Lalam: Thinking about the culture aspect, if this method can provide a more stable and less artifact-prone way to detect anomalies in complex systems, it could help us build systems that are less susceptible to noise or unexpected variations <ref:2610.12244#pg3>. It moves detection away from simple pattern matching towards a more structural understanding of the data relationships.

Tom: So, we've heard that RIFT offers an exact solution in one dimension and a deterministic generalization in higher dimensions, while its ensemble version beats Isolation Forest on variance <ref:2610.12244#pg1>. The core idea is using the MST to score points based on their apparent size from that point <ref:2610.12244#pg3>.

Jane: And they emphasize that the MST formulation is inherently density-invariant, which means scaling up a cluster proportionally doesn't change the score because both the empty spaces and the perspective distances scale in a way that keeps the sum effectively unchanged <ref:2610.12244#pg1>. That’s a very strong property for real-world data <ref:2610.12244#pg3>.

Paper summary: Lu: It’s interesting to see how they derived the exact formula for the expected depth of point xi, H(i), which is given by that recursive process defined in Equation A6 <ref:2610.12244#pg1>. It shows a very specific mathematical structure behind this deterministic scoring <ref:2610.12244#pg3>.

Meng: What about the limitations they mention? They focus on point anomalies within multidimensional tabular data, assuming no underlying sequential or temporal structure among the independent samples <ref:2610.12244#pg3>. That means if your data has a strong time series component, this method might not be as effective as something designed for that structure <ref:2610.12244#pg3>.

Tom: So, to sum up what we've covered about the paper RIFT: Relative Isolation From Trees For Anomaly Detection, it’s a deterministic method built on MST construction and edge summation <ref:2610.12244#pg1>. It matches the accuracy of Isolation Forest but offers better stability in its ensemble variant <ref:2610.12244#pg3>.

Jane: And they've made it parameter-free for higher dimensions by replacing random partitioning with this deterministic tree structure <ref:2610.12244#pg1>. It really pushes the idea that you can get a solid score without tuning too many variables <ref:2610.12244#pg3>.

Lu: It suggests that moving from random recursive partitioning to a distance-based construction based on the MST is a powerful way to capture structure in data <ref:2610.12244#pg3>. It’s not just about finding outliers, it’s about understanding the connectivity of the entire dataset.

Tom: The authors are really showing that this approach works well on synthetic data and the ADBench benchmark, achieving accuracy comparable to IF <ref:2610.12244#pg3>. This is encouraging when you look at how many different methods exist for point anomaly detection <ref:2610.12244#pg3>.

Jane: So, when we think about what this means for the world, it’s that we have another option in the toolbox for finding anomalies in complex, high-dimensional datasets <ref:2610.12244#pg3>. It offers a deterministic alternative to methods that rely heavily on random splits <ref:2610.12244#pg3>.

Lu: The ensemble variant’s superior variance reduction, being an order of magnitude lower than IF at the same ensemble size, is a key finding <ref:2610.12244#pg3>. That stability is what makes it appealing for applications where you need reliable results without excessive hyperparameter tuning <ref:2610.12244#pg3>.

Meng: For practical deployment, the sparse k-nearest-neighbor approximation being O(n times k), as opposed to n squared, means it can actually run on larger datasets than the exact complete graph method <ref:2610.12244#pg3>. That’s a tangible benefit for engineers dealing with large streams of data <ref:2610.12244#pg3>.

Paper summary: Tom: It sounds like RIFT isn't just a theoretical exercise; it offers deterministic and robust scoring that can compete with established techniques like Isolation Forest in performance, especially when you look at the ensemble results <ref:2610.12244#pg3>.

Jane: So, to wrap up our look at RIFT: Relative Isolation From Trees For Anomaly Detection, it’s a deterministic method that uses Minimum Spanning Trees to score points based on their apparent size from that point <ref:2610.12244#pg1>. It provides a parameter-free generalization for higher dimensions and an ensemble variant with much lower variance than IF <ref:2610.12244#pg3>.

Lu: The implication is that we can replace some of the reliance on pervasive randomness in tree splitting with a more structured approach based on distance and connectivity within the data points themselves <ref:2610.12244#pg3>. This shifts the focus from random partitioning to structural relationships.

Meng: It gives us a deterministic path forward for anomaly detection that is less sensitive to the initial random sampling choices, which is something I can definitely see being valuable in production systems <ref:2610.12244#pg3>.

Tom: Right, so we’ve looked at RIFT today and its title, Relative Isolation From Trees For Anomaly Detection <ref:2610.12244#pg1>. It’s a method that finds anomalies by measuring their isolation relative to the structure of the data's minimum spanning tree <ref:2610.12244#pg3>.

Jane: And the idea is that this approach, especially with its ensemble setup, offers high accuracy while being much more robust against different random seeds than methods like Isolation Forest <ref:2610.12244#pg3>. It’s a deterministic scoring mechanism in higher dimensions <ref:2610.12244#pg3>.

Lu: The main thing is that it’s not just another black box; it has a clear geometric interpretation involving the apparent size of segments in the MST <ref:2610.12244#pg3>. That structural insight is what makes me excited about its potential for deeper analysis.

Meng: It’s a solid tool that an engineer can actually use, especially with the sparse approximation to keep complexity manageable <ref:2610.12244#pg3>. The ability to get deterministic results without needing lots of fine-tuning is also a big plus <ref:2610.12244#pg3>.

Tom: Yeah, so the core message from RIFT is that by using the MST, we replace random partitioning with something more structured and deterministic for anomaly scoring <ref:2610.12244#pg3>. It’s a solid step forward in how we tackle point anomaly detection in multidimensional tabular data <ref:2610.12244#pg3>.

Conclusion: Tom: So we’re wrapping up on RIFT, which stands for Relative Isolation From Trees For Anomaly Detection by Szalai and Horvath.

Jane: It basically takes something that works in one dimension and makes it work deterministically in higher dimensions using minimum spanning trees.

Lu: The main idea is replacing random recursive partitioning with a structure based on the minimum spanning tree to get a score that doesn't have those axis-parallel artifacts we see elsewhere.

Meng: So, what does this mean practically for someone building an AI system? Is it just another complex algorithm?

Lalam: It means we can move away from relying on pervasive randomness at every split point in the tree, which is a big deal for stability.

Tom: Exactly. And they show that their ensemble variant, the one using multiple trees built from different subsets, has much lower variance across random seeds than the Isolation Forest baseline when you use the same ensemble size.

Jane: So if you run this on a huge dataset and get a slightly different score just because of how the trees were sampled initially, that score stays much closer to the true anomaly score.

Lu: They also noted that the MST formulation is density-invariant, which means scaling up a cluster proportionally doesn't change the resulting sum because both the empty spaces and those perspective distances scale in a way that keeps it effective.

Meng: That density invariance is important for real-world data where clusters can be wildly different sizes and shapes.

Tom: Yeah, so when you look at the title of RIFT, Relative Isolation From Trees For Anomaly Detection, it really captures the essence of using tree structure to measure how isolated a point is relative to the rest of the data's connectivity.

Jane: And Szalai and Horvath have shown that this approach doesn't need you to manually tune tons of hyperparameters for a decent result in higher dimensions.

Lu: It suggests we can get a reliable scoring mechanism just by building this graph structure from the data itself, without needing those fine-tuning knobs.

Meng: So, if I’m looking at deploying something in production, this deterministic nature is appealing because I don't want unpredictable behavior based on random initial conditions.

Lalam: It gives us a way to build more predictable systems where anomaly detection behaves consistently across different runs.

Tom: And this leads us into the next part of the conversation about how these structural insights can influence how we design the AI models themselves.

M´ark D´aniel Szalai, G´abor Horv´ath

Department of Networked Systems and Services, Faculty of Electrical Engineering and Informatics, Budapest University of Technology and Economics

cs.LG

Submitted: 2026-10-08

Updated: 2026-10-08

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 86/100

The gist: The gist The proposed method RIFT introduces a deterministic anomaly detection method that generates a minimum spanning tree and scores each point by the sum of the apparent sizes of tree edges as

Key concepts

Isolation Forest (IF): A baseline method that detects anomalies by building isolation trees. These trees are grown from random subsets of data, and the anomaly score is based on the average path length required to isolate a point within these trees.
RIFT Geometric Interpretation: RIFT interprets its scoring mechanism geometrically. The sum of edge lengths is viewed as the 1D apparent size or visual angle of empty space between data points, which captures local sparsity and density in the data structure.
Minimum Spanning Tree (MST) Graph: The core idea involves constructing a graph where edge weights are based on squared distances between points. The MST is then traversed starting from the target point to define a deterministic structure for calculating anomaly scores, generalizing the 1D concept.
RIFT Ensemble Variant: This variant uses multiple independent MST constructions from random subsets of data and feature subspaces. This ensemble approach significantly reduces variance compared to Isolation Forest by limiting randomness only to initial sampling phases.

Summary

The gist The proposed method RIFT introduces a deterministic anomaly detection method that generates a minimum spanning tree and scores each point by the sum of the apparent sizes of tree edges as viewed from that point, which recovers the closed-form IF limit exactly for one-dimensional data and provides a parameter-free generalization in higher dimensions

Isolation Forest Baseline

The Isolation Forest (IF) is a widely used baseline for unsupervised anomaly detection. It operates by building t isolation trees, each grown from a random subsample X' of size ψ, where at each node, a feature index q is sampled uniformly at random and a split value p is sampled uniformly from [minx∈S x(q), maxx∈S x(q)]. The standard anomaly score is then defined as s(x, ψ) = 2-E[h(x)]/c(ψ), where E[h(x)] is the forest-average path length and c(ψ) is a normalization factor.

RIFT Geometric Interpretation

The core idea of RIFT generalizes the one-dimensional result by interpreting the summation geometrically as described in Equation 5, where h¯(xi) can be rewritten as h¯(xi) = Xk,k!=i dk/lk. Each term dk represents the length of the empty space between consecutive data points, capturing local sparsity, and lk represents the “line-of-sight” distance from the target point to a evaluated edge. Geometrically, this quotient is interpreted as the 1D apparent size (or 1D visual angle) of the segment dk as observed from x4.

RIFT Implementation Variants

The paper proposes three variants of the method to address scalability and robustness. First, an exact formulation built on a global MST constructs a complete graph G where weight(xi, xj) = xi - xj squared and then traverses the MST starting from the target point xt. Second, a scalable approximation uses a sparse k-nearest-neighbor (kNN) graph to approximate the MST, which reduces complexity from O(n 2) for a complete graph to O(kn) for a kNN graph. Third, an ensemble-based approach utilizes M independent Minimum Spanning Trees constructed from small random subsets of data instances ψ and randomly selected feature subspaces Fj to compute the isolation score h¯(xi, Tj).

Performance and Advantages

Experiments on synthetic data and the ADBench benchmark demonstrate that RIFT achieves accuracy comparable to IF. The proposed method is deterministic in its exact and approximate variants, while the ensemble variant exhibits significantly lower variance across random seeds compared to IF at the same ensemble size. Furthermore, the MST-based formulation is inherently density-invariant because scaling a cluster proportionally scales both local empty spaces (dk) and perspective distances (lk), leaving the resulting sum effectively unchanged.

Hyperparameter Influence

The performance of the ensemble approach is influenced by three hyperparameters: the ensemble size, the number of data samples per tree, and the feature bagging ratio. The results indicate that increasing the size of the ensemble provides a clear benefit in terms of variance reduction, and restricting trees to a significantly smaller sample size can improve accuracy on certain datasets by breaking apart dense anomaly clusters. Feature bagging is shown to have a substantial effect on performance, with its optimal setting depending on whether features are informative or noisy for a given dataset.

Conclusion

RIFT generalizes the 1D result to arbitrary dimensions by replacing random recursive partitioning with a deterministic, distance-based construction based on the Minimum Spanning Tree, resulting in a score that is free of axis-parallel artifacts. The ensemble variant offers high accuracy competitive with IF while providing superior robustness due to lower variance across random seeds.

How it works

The exact solution for the expected depth of point xi, H(i), is given by the explicit formula H(i) = X i-1 k=1 xk+1 - xk xi - xk + N X-1 k=i xk+1 - xkxk+1 - xi. This formula is derived through a recursive process defined in Equation (A6), which exploits the equality of terms in parentheses to yield the final expression H(i) = 1 + X i-1 j=l xj+1 − xj xi − xj - xl xu − xl + xu − xi xu - xl + uX-1 j=i xj+1 − xj+1 - xi xi - xl xu - xl [z]-1.

Key Findings

The proposed method is robust to varying density and clustered anomalies by construction, without requiring any hyperparameters. The ensemble approach limits randomness strictly to the initial instance and feature sampling phase of each tree, unlike IF which relies on pervasive randomness at every split. The RIFT ensemble achieves an order of magnitude lower relative standard deviation than the IF at the same ensemble size, indicating superior robustness in its scoring.

Evaluation Summary

On synthetic data and the ADBench benchmark suite, RIFT achieves accuracy competitive with IF. Consistent with the central observation of ADBench – that no single method dominates across all datasets – RIFT is not a universal winner, but it matches the strongest classical detectors while offering two distinct advantages: a fully deterministic variant, and an ensemble whose score variance across random seeds is an order of magnitude lower than that of IF at the same ensemble size. The detailed numerical results of the AUC comparison are summarized in Table 6.

Acknowledgement

The project supported by the Doctoral Excellence Fellowship Programme (DCEP) is funded by the National Research Development and Innovation Fund of the Ministry of Culture and Innovation and the Budapest University of Technology and Economics, under a grant agreement with the National Research, Development and Innovation Office.

References

[1] Chandola, V., Banerjee, A., Kumar, V.: Anomaly detection: A survey. ACM computing surveys (CSUR) 41(3), 1–58 (2009)

[2] Aggarwal, C.C.: Outlier Analysis, 2nd edn. Springer, Cham (2017)

[3] Hawkins, D.M.: Identification of Outliers vol. 11. Springer, Cham (1980)

[4] Hauskrecht, M., Batal, I., Valko, M., Visweswaran, S., Cooper, G.F., Clermont, G.: Outlier detection for patient monitoring and alerting. Journal of biomedical informatics 46(1), 47–55 (2013)

[5] Sommer, R., Paxson, V.: Outside the closed world: On using machine learning for network intrusion detection. In: 2010 IEEE Symposium on Security and Privacy, pp. 305–316 (2010). IEEE

[6] Fujimaki, R., Yairi, T., Machida, K.: An approach to spacecraft anomaly detection problem using kernel feature space. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 401–410 (2005)

[7] Gupta, M., Gao, J., Aggarwal, C.C., Han, J.: Outlier detection for temporal data: A survey. IEEE Transactions on Knowledge and data Engineering 26(9), 2250–2267 (2013)

[8] Akoglu, L., Tong, H., Koutra, D.: Graph based anomaly detection and description: a survey. Data mining and knowledge discovery 29(3), 626–688 (2015)

[9] He, S., Zhu, J., He, P., Lyu, M.R.: Experience report: System log analysis for anomaly detection. In: 2016 IEEE 27th International Symposium on Software Reliability Engineering (ISSRE), pp. 207–218 (2016). IEEE

[10] Goldstein, M., Uchida, S.: A comparative evaluation of unsupervised anomaly detection algorithms for multivariate data. PloS one 11(4), 0152173 (2016)

[11] Emmott, A.F., Das, S., Dietterich, T., Fern, A., Wong, W.-K.: Systematic construction of anomaly detection benchmarks from real data. In: Proceedings of the ACM SIGKDD Workshop on Outlier Detection and Description, pp. 16–21 (2013)

[12] Pimentel, M.A., Clifton, D.A., Clifton, L., Tarassenko, L.: A review of novelty detection.

Improvements for AI systems

Bold header: RIFT generalization to arbitrary dimensions

RIFT generalizes one-dimensional results by proposing a deterministic method based on a Minimum Spanning Tree (MST) constructed over Euclidean distances in higher dimensions, which is not a mere derivative of existing techniques, but a novel method that broadens the landscape of anomaly detection algorithms. This allows the system to detect anomalies in complex feature spaces without relying on random recursive partitioning.

Bold header: Robustness to varying density and clustered anomalies

The MST-based formulation provides a metric that is inherently density-invariant because the score is defined by a quotient of local empty spaces and perspective distances, allowing the algorithm to recognize that a point within a sparse cloud is topologically just as normal within its own local context as a point in a tightly packed core.

Bold header: Ensemble robustness for large datasets

The ensemble variant, RIFT-ensemble, mitigates variance by using sub-sampling and feature bagging, which prevents swamping and mitigates the curse of dimensionality, resulting in an anomaly score variance that is an order of magnitude lower than that of IF on both dataset collections.

Sources

Theoretical Investigation on Inductive Bias of Isolation Forest