Theoretical Investigation on Inductive Bias of Isolation Forest

Isolation Forest (iForest) is one of the most widely used unsupervised anomaly detectors, owing to its efficiency and performance on large-scale tasks. Despite its broad applications, there is still a lack of theoretical understanding of iForest's empirical success. In this work, we study the inductive bias of iForest and examine when and to what extent it performs well. The main idea is to characterize the random growth process of iForest, in which both split dimensions and split values are selected randomly. We model the growth process of iForest as a random walk and derive the expected path length function, the outcome of iForest that determines the anomaly score, by analyzing the hitting time of the absorbing state. The infinite-sample size analysis reveals that, unlike $k$-Nearest Neighbor ($k$-NN), whose score reflects only the local density, the iForest path length combines the density and the centrality. Since central points naturally have larger path lengths, iForest is therefore less sensitive to central anomalies. Analyses of fixed datasets corroborate this finding and further show that iForest is more parameter-adaptive than $k$-NN. Our study provides a theoretical understanding of the effectiveness of iForest and establishes a foundation for further exploration.

Isolation Forest is a popular method for finding unusual data points, such as fraudulent transactions, network attacks, or abnormal medical records. It works by repeatedly splitting the data at random: points that can be separated quickly are treated as more anomalous. Although the method is widely used because it is fast and effective, it has not been fully clear why it works or what kinds of anomalies it is best at detecting. This paper studies the hidden preference, or inductive bias, of Isolation Forest. By viewing the random tree-building process as a random walk, the paper derives a precise formula for the expected path length used by the algorithm. The analysis shows that Isolation Forest does not rely only on local data density. It also depends on how central a point is within the overall data range. As a result, central anomalies may be harder for Isolation Forest to detect than boundary anomalies.