Theoretical Investigation on Inductive Bias of Isolation Forest

Qin-Cheng Zheng, Shao-Qun Zhang, Shen-Huan Lyu, Yuan Jiang, Zhi-Hua Zhou
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:163944-163972, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-zheng26ag, title = {Theoretical Investigation on Inductive Bias of Isolation Forest}, author = {Zheng, Qin-Cheng and Zhang, Shao-Qun and Lyu, Shen-Huan and Jiang, Yuan and Zhou, Zhi-Hua}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {163944--163972}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/zheng26ag/zheng26ag.pdf}, url = {https://proceedings.mlr.press/v306/zheng26ag.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Theoretical Investigation on Inductive Bias of Isolation Forest %A Qin-Cheng Zheng %A Shao-Qun Zhang %A Shen-Huan Lyu %A Yuan Jiang %A Zhi-Hua Zhou %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-zheng26ag %I PMLR %P 163944--163972 %U https://proceedings.mlr.press/v306/zheng26ag.html %V 306 %X 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.
APA
Zheng, Q., Zhang, S., Lyu, S., Jiang, Y. & Zhou, Z.. (2026). Theoretical Investigation on Inductive Bias of Isolation Forest. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:163944-163972 Available from https://proceedings.mlr.press/v306/zheng26ag.html.

Related Material