Anomaly Detection by an Ensemble of  Random Pairs of Hyperspheres
Authors: Walid Durani
Collin Leiber
Khalid Durani
Claudia Plant
Christian Böhm
Venue: NeurIPS 2025 poster ()
Keywords: ensemble
isolation
anomaly detection
Primary area: general_machine_learning

Abstract: Anomaly detection is a crucial task in data mining, focusing on identifying data points that deviate significantly from the main patterns in the data. This paper introduces Anomaly Detection by an Ensemble of Random Pairs of Hyperspheres (ADERH), a new isolation-based technique leveraging two key observations: (i) anomalies are comparatively rare, and (ii) they typically deviate more strongly from general patterns than normal data points. Drawing on a delta-separation argument, ADERH constructs an ensemble of multi-scale hyperspheres built upon randomly paired data points to identify anomalies. To address inevitable overlaps between anomalous and normal regions in the feature space, ADERH integrates two complementary concepts: Pitch, which highlights points near hypersphere boundaries, and NDensity, which down-weights hyperspheres centered on sparse (and often anomalous) regions. By averaging these local, density-adjusted ``isolation'' indicators across many random subsets, ADERH yields robust anomaly scores that clearly separate normal from abnormal samples. Extensive experiments on diverse real-world datasets show that ADERH consistently outperforms state-of-the-art methods while maintaining linear runtime scalability and stable performance across varying hyperparameter settings.

Anomaly Detection by an Ensemble of Random Pairs of Hyperspheres
Walid Durani', Collin Leiber Khalid Durani", Claudia Plant Christian Böhm
'LU Munich, Munich Center for Machine Learning (MCML), Munich, Germany
Aalto University, Espoo, Finland
3 University of Helsinki, Helsinki, Finland *University of Innsbruck, Innsbruck, Austria
'Faculty of Computer Science, 'ds:UniVia University of Vienna, Vienna, Austria durani maanedbb.... iffi. 1mu de, collin. leiber@aalto fi, khalid, durani durani@uibk ac at claudia paaiiialplannunnnnn witiitnniiiii..iee arcie..c.att at, christian boehmdunivie ac.at
Abstract
Anomaly detection is a crucial task in data mining, focusing on identifying data points that deviate significantly from the main patterns in the data. This paper introduces Anomaly Detection by an Ensemble of Random Pairs of Hyperspheres (ADERH), new isolation-based technique leveraging two key observations: (i) anomalies are comparatively rare, and (ii) they typically deviate stronger from general patterns than normal data points. Drawing on 8-separation argument, ADERH constructs an ensemble of multi-scale scale hyperspheres built upon randomly paired data points identify anomalies. To address inevitable overlaps between anomalous and normal regions in the feature space, ADERH integrates two com- plementary concepts: Pitch, which highlights points near hypersphere boundaries, and NDensity, which down-weights hyperspheres centered on sparse (and often anomalous) regions. By averaging these local, cators across many random subsets, ADERH yields robust anomaly scores that clearly separate normal from abnormal samples. Extensive experiments on diverse real-world datasets show that ADERH consistently outperforms state-of-the-an methods while maintaining linear runtime scalability and stable performance across varying hyperparameter settings.
"isolation" indi-
1 Introduction
Anomaly detection is an essential tool data mining, as can uncover critical information Agrawal and Agrawal 2015). For instance, anomalies may indicate credit card fraud, analyze critical behavior in network applications, or assist in diagnosing rare medical conditions [John and Naaz, 2019 Tao al., 2018 Abuzaid 2020). In the of big data, where data volumes are rapidly increasing, is essential for anomaly detection methods to effectively and efficiently identify anomalies in
large datasets [Ahmed et al. 2017 Mansour al. 2023 Thudumu al., 2020). However, all
anomaly detection methods are suitable for larger datasets. Due to high runtime complexity. density- based methods like the Local Outlier Factor (LOF) [Breunig al. 2000) and deep bearning-based
approaches (Pang et al. 2021 have limited applicability.
colatiion-bsed methods on the other hand typically operate on data subsets, making them more effective for handling larger datasets [Xu 2017 Xiong et al. 2022 Examples of such algorithms include Isolation Forest (IForest) LLu
et al.
al. 2008 Efficient Anomaly Detection by Isolation Using Nearest Neighbour Ensemble (INNE)
[Bandaragoda et al. 2014), Extended Isolation Forest (EIF) [Haiii et al. 2019), or Deep Isolation
Forest (DIF) [Xu et al. [202a]]. These approaches utilize two essential properties that distinguish
anomalies from regular data points.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

RARITY:
Anomalies comprise only a small proportion of the dataset, i.e., most of the samples represent regular data points (Barnett et al. 1994 Aggarwal 2016].
DEVIATION: Anomalies differ significantly from the general patterns in a dataset, sug- gesting that they originate from different processes than regular samples [Hawkins 1980].
We formalize these properties with the d-separation assumption: normal samples form compact regions, while anomalies lie mainly beyond their boundaries (Section (..I. However, current isolation- based methods have certain limitations. IForest (Liu et al.] [2008] efficienlly detects anomalies via random partitioning. but its reliance on global, axis-aligned splits can miss complex or locally defined outliers. INNE [Bandaragoda et al. 2014) attempts to address this by utilizing hyperspheres to capture local patterns, but sensitive to the sample size and assigns equal weights to hyperspheres, which can limit its robustness (Bandaragoda et al. 2018).
We propose ADERH, a method that isolates anomalies using compact hyperspheres designed to minimize overlap with anomalies. Guided by the ò-separation prineiple-which assumes that anomalies lie beyond normal regions ADERH constructs small local subsets and pairs of points. By halving each pairwise distance, it forms compact hyperspheres that adapt to multiple scales and collectively cover diverse normal regions. thereby reducing overlap with anomalies and enhancing isolation precision. Since perfect d-separation may fail in practice, we refine each hypersphere s isolation signal with (i) Pitch, ratio-based distance measure accentuating boundary anomalies, and (ii) NDensity, which wwwnwseights hyperspheres in sparse (anomalous) regions. Finally, ADERH onsemble-averagee these local isolation signals, further reducing variance and enhancing robustness on rorldworld, heterogencous data.
In summary, we make the following contributions:
We present ADERH, a novel technique for assigning anomaly scores to data points by analyzing their position within multiple hyperspheres and the characteristics of these hyper- spheres.
Hyperspheres may still include anomalies near the boundary or span around anomalies, blurring distinctions between normal and abnormal data. To overcome this, ADERH intro- duces two components: NDensity, which down-weights hyperspheres in sparse (anomalous) regions, and Pitch, which emphasizes points near hypersphere boundaries.
Thus, ADERH more effectively distinguishes anomalies from normal samples, overcoming limitations that arise from relying solely on hypersphere- or distance-based methods.
ADERH delivers robust and stable anomaly scores across a wide range of hyperparameters, maintains high efficiency on large-scale datasets, and-through extensive experiments involving both default parameter settings and exhaustive grid searches- outperforms state- of-the-art anomaly detection methods.
2
Related work
Over the past few decades, anomaly detection has been extensively studied using various techniques such density, isolation, deep learning.
Isolation- based approaches assume that small fraction of the data consists of anomalies (RARITY) and that those have different attribute values than normal data points (DEVIATION). A prominent example the Isolation Forest (IForest) [Liu et al.) 2008), which recursively partitions the feature space by selecting random features and random split values; anomalies tend to have shorter paths from the root node. The Extended Isolation Forest (EIF) [Hariri et al. 2019) improves on IForest by using hyperplanes with randomly determined slopes for splitting, enhancing accuracy across diverse datasets. PIDForest [Gopalan et al. criterion (PIDScore) that quantifies the minimum density among all subcubes covering a data point. Deep Isolation Forest (DIF) [Xu et al. 2023a leverages a learned ensemble of random representations that produce non-linear partitions in the feature space.
2019] accelerates isolation while incorporating a density- based
Distance/Density- -baed approaches flag anomalies in sparse regions. The Local Outlier Factor (LOFF [Breunig et al. 20000 measures how much point's local density deviates from that of its neighbors, while the Connectivity- incorporating chaining distances to better handle linear data structures.
Outlier Factor (COF) [Tang et al.) 2002) refines LOF by

---

Boundary-basee approaches define boundary around normal data and classify points outside this region as anomalies. For instance, the One- Class Support Vector Machine (OCSVM) [Schölkopf et al. 2001 Bounsiar and Madden 2014), finds a hyperplane that maximally separates normal samples from the origin, treating any observation lying outside this boundary as anomalous.
Ensemble-basee approaches combine multiple anomaly detection methods to mitigate individual drawbacks and leverage their strengths, to enhance performance and robustness (Zimek et al. 2014 Cheng et al. 2019 Zhao et al. 2019a]. For instance, LODA (Pevný 2016) aggregates outputs from diverse weak detectors, using their collective decisions to identify anomalies. Similarly, LSCP (Zhao et al., 2019a] selects base detectors and determines a point's 's anomaly score by analyzing its local
data distribution and combining the detectors' outputs.
Deep learning- approaches have advanced rapidly, leveraging representation learning to compute anomaly scores on complex data (Wang al.) [019a Pang et al.] [021]. For example, DeepSVIDD (Ruff et al.] 2018) tries to embed data into a hypersphere, classifying points on the outside as anomalies. To prevent representation collapse, Deep Robust
Classification (DROCC) [Goyal et al. [0200 refines boundaries around normal samples by clustering them closer and using adversarial perturbations as hard negatives. Other methods emphasize collaboration or distance-based representations: A Deep Collaborative Autoencoder Approach for Anomaly Detection (RCA) [Liu al.) 2021] iteratively trains multiple autoencoders on low-error samples, exchanging these to enhance detection; Unsupervised Representation Learning by Predicting Random Distances (RDP) [Wang et al.] 2019b) uses a two-branch, weight-shared shared model map data into distance- preserving space for isolating anomalies. SLAD [Xu et al. 2023b) introduces a self-supervised "scale" concept for tabular data, learning global normal patterns and identifying anomalies via higher errors. Diffusion Modeling for Anomaly Detection (DTE) [Livernoche et al. (024) estimates how "diffused" an input is relative to the normal data manifold, enabling fast and accurate anomaly detection. UniCAD [Fang et al., [025] introduces unified probabilistic mixture model linking representation learning, clustering, and anomaly detection through an anomaly-aware likelihood function, yielding a theoretically grounded anomaly score.
Hy Hypersphere-based anomaly detection was first introduced through global hypersphere models designed to enclose normal data points [Kumar et al., [003] Tax and Duin, 2004]. MV-ERM and MV-SRM (Scott and Nowak 2005) reframe
volimu estimation as empirical risk minimization. M minimizes the region capturing an a-fraction of data under a penalized risk, while MV-SRM integrates the penalty into the objective for automatic complexity control. GEM (Hero 2006) formulated anomaly detection via geometric-entropy minimization, identifying subsets with minimal k--N or MST wiring length as minimum-entropp approximations. DTM (Gu et al. 2019) estimated local radii enclosing mass m,, with bagging reducing variance but retaining global-distanee distance dependence. INNE [Bandaragoda et al., 2014) used hypersphere ratios between point's enclosing radius and its nearest neighbor's s to score anomalies. Despite progress, most methods rely on a few large hyperspheres with limited local adaptivity, often failing near or on boundaries. In contrast, ADERH forms ensemble of compact hyperspheres from random pairs of points, each defining two half-radius spheres with varying radii. It integrates Pitch (boundary sensitivity) and NDensity (sparse-region down-weighting) to handle boundary and center anomalies. These choices ensure robust scalability- small subsets and simple distance checks suffice- and strong empirical performance, surpassing traditional and deep hypersphere methods with linear- time efficiency.
3 Anomaly Detection by an Ensemble of Random Pairs of Hyperspheres
Considering a dataset D C Rd containing m points drawn i.i.d. from a mixture distribution
P = Px + a) (0<a<1),
where Px captures the normal data and PA represents the anomalous data. Our goal is to define an anomaly scoring function I: R + RR that assigns higher scores I(xr) to anomalous points than to normal points. Building upon the fact that anomalies form small fraction of the data and exhibit distinctly different characteristics, we formalize these observations using 8-separation assumption.
3

---

3.1 5-Separation
Concretely, we assume that normal points cluster within small-radius neighborhoods, whereas anomalous points are located at least a distance 8 from any local cluster:
Assumption 3.1 (6-Separation). Let J be a finite, nonempty index set and let {py Jpe C Rd be a set of cluster centers. Let Pv and PA be probability measures on R Assume there exist radii 0 < 8 and small parameters 0 < e, < 1 such that:
1. Normal-Point Proximity, For x ~ PN.
Pr min ||= - pyl -y)ls00) 21-6 jEJ
2. Anomaly Exclusion. For PA.
Pr min JEJ
||2
Myll u) 2 21-2.
Since d > O. up to probabilities e and e', normal samples lie within distance o of some center, while anomalies lie at least a + 8 from every center.
This assumption reflects common anomaly-detection pattern in which normal data cluster around modes Py, and anomalies occupy sparser regions beyond distance 5. For example, credit-card fraud often lies outside the compact clusters formed by legitimate transactions. Although 6-separation need not hold exactly, requiring most normal points to lie within of some center and most anomalies to lie beyond + 5 suffices for our analysis (up to small e, E'). Similar local-separability assumptions appear in [Breunig et al. 2000 Ester et al. [996] BBandaragoda et al. 20188. Sections 3.3 describe how boundary- and density- based terms address partial violations of ò-separation.
Remark:
3.2 The ADERH algorithm
Building on RARITY and DEVIATION formalized by 5-separation, ADERH is designed to iso- late anomalies using multiple hyperspheres rather than a single fixed-radius sphere. Under ideal ò-separation, normal points lic within radius a,, and anomalies remain at least 8 away, making hy- perspheres around normal samples natural isolation mechanism. In practice, perfect separability rarely holds, so ADERH augments each hypersphere's 's isolation signal with Pitch (a ratio- basod distance) and NDensity (a density- based term) to handle anomalies that partially overlap with normal clusters. A single hypersphere is insufficient for multi-scale data, so ADERH creates an ensemble of hyperspheres at varying radii (see Appendix B). then averages their local anomaly scores. As Theorem 3.15 shows, this ensemble averaging reduces variance and robustly isolates anomalies even when strict d-separation violated. For this purpose, the procedure first creates a set of n subsets, where each subset contains w samples:
Definition 3.2 (Set of subsets). We sample n random subsets of size w from the dataset D:
SUBSETS(D, n, w) (Si....,s.).
where Visien S C D. |S sampling from the dataset ID with replacement.
= and w is an even number. The subsets S; are generated by uniform
The goal of ADERH is to create multiple hyperspheres of different radii in each subset S, so that dense areas are captured by smaller hyperspheres, and sparser areas by larger ones. This is achieved by random pairings through the partner function P, which naturally reflects local density in the hypersphere radii and, therefore, yields multi-scale coverage (see Appendix and
Definition 3.3 (Partner function P). The function P(x,S, assigns a random point y E S, a sample E St, where + y. Each partner is selected exactly once through uniform sampling. Formally, this can be expressed as (ax S,) x E S.) = S,. Note that y P(x, S.) + x P(y, S,) is not necessarily valid.
While allowing hyperspheres vary in radius helps capture local structures, this radius variability also risks producing oversized hyperspheres that can absorb anomalies, especially in heterogencous

---

data [Bandaragoda et al., 2014, Ruff et al. 2018]. To mitigate this, ADERH transforms each pair (x, v) into two hyperspheres one centered on and one on y-each using half the pairwise distance, i.e., 2 dist (x. v): as the radius. This halving avoids excessively large radii, reduces overall radius variance, and makes hypersphere sizes more uniform. We use the 2 factor principled trade-off' between coverage and exclusion, as discussed Appendix A
Motivating Hy Hypersphere Construction. ADERH aims isolate anomalies by combining multiple hyperspheres with diverse radii. By combining these compact hyperspheres into an ensemble, we reduce their overlap with anomalies, thereby boosting anomaly- -eetttnnttection performance. Below, formalize the construction of these hyperspheres, which collectively underpin our method's ability to separate anomalies from normal data.
Definition 3.4 (Hypersphere H). Given sample S; and its partner y P(x, S:), we create two distinct hyperspheres (x, S.) and H(y, St), where x and y are the respective centers. The radius of both hyperspheres is defined as:
R(H) = dist(rr v)
(3)
2
Further, we define the set of potential data points that hypersphere H covers as:
Xx {a| E Rd A dist(x, C(H)) I R(H)),
(4)
where the function C(H) returns the center of the hypersphere H. In this paper, we employ the Euclidean distance as the distance function -ist(..). The ADERH algorithm, however, remains valid for any metric space, as it relies solely on the fundamental properties of a metric.
For each subset S,, we create an ensemble of hyperspheres:
Definition 3.5 (Ensemble of hyperspheres E). Let S SUBSETS, then the ensemble of hyper- spheres & is:
E(S)) U H(P,,, #ES,
(5)
The definitions set so far could be sufficient in an ideal world, where all hyperspheres were created around normal data points and the hyperspheres are sufficiently small to exclude anomalies. However, real-world datasets often violate strict d-separation. Two key complications arise:
Anomaly Contamination: Some anomalies may fall inside hyperspheres centered on normal samples (Fig. []. Although these anomalies are technically covered, they typically appear near the hypersphere boundary rather than close to its center.
2. Anomaly Hyperspheres: Anomalies can also act hypersphere centers, forming low- density (or 'sparse") hyperspheres that cover few neighbors (Fig. 2
To handle these cases, we extend our hypersphere framework with two complementary measures Pitch (Section 3.3) and NDensity (Section 3.4.
3.3 Anomaly Contamination
Although 6-separation outlines a margin between normal and anomalous points, real data often violates this idealized boundary [Ruff et al. 2018 Breunig et al. 2000). allowing anomalies to appear near or within local clusters (Fig. [). Yet, on average, anomalies remain farther from hypersphere centers than normal points [Ruff al. 2018 To leverage this property, we use ratio- ratio-distance from the hypersphere center over its radius to distinguish anomalies from inliers. Concretely, for a hypersphere 7. created from subset S; SUBSETS, define Pitch as:
distance
Definition 3.6 (Pitch). The Pitch represents the adjusted distance between sample D and the center c = C(H) hypersphere H.
dist(zz.) R(7))
if (is S R(H). otherwise.
Pitch(x, 7))
(6)
1
5

---

The issue of Anomaly Contamination: Anomalies (black dots) can lie within hyperspheres centered on regular samples (green dots). However, as local anomalies are typically farther from regular samples than regular samples are from each other (DEVIATION), we apply Pitch to replace strict 6-separation with ratio-based isolation measure. This flags borderline anomalies near regular samples without requiring rigid margins.
Figure 1:
Figure The issue of Anomaly Hyperspheres: Hyperspheres typically form around regular samples (green dots), as anomalies are rare (RARITY). However, in some cases, anomalies (red dots) may generate hyperspheres. Note that hyperspheres around regular samples generally enclose more points, aligning with DEVIATION. The colors of the hypersphere indicate which points were paired to create the hypersphere.
As anomalies are characterized by larger distances the center of hypersphere than normal data points, the Pitch strengthens the differences between corresponding samples. Abnormal data points within the hypersphere should have large ratio dist(ar.) and therefore Pitch close to 1. In contrast, normal data points usually have significantly smaller Pitch.
R(H)
3.4 Anomaly Hyperspheres
The strategies proposed thus do not fully resolve the problem of hyperspheres centered around anomalous samples (Fig. 2). Since anomalies may exist within any random subset S, E SUBSETS, hyperspheres defined by these anomalies may lead to inaccurate anomaly scores, often misclassifying anomalies as normal. While the ensemble averaging across subsets mitigates their overall impact, individual subsets remain susceptible these anomaly-centers effects. This issue is exacerbated in larger subsets, where the probability of including at least one anomaly increases with subset size [ shown in:
[ D
Panomaly (x) ~
where [ and (D) denote the number of normal samples and the dataset size, respectively. The Pitch determined by hyperspheres defined by these anomalies would give inaccurate anomaly scores. Considering DEVIATION, we know that most data points are regular samples close to each other. Anomalies are characterized by an environment of lesser density and are further away from the remaining data. Thus, the data distribution within a hypersphere indicates hyperspheres centered around anomalies. For this purpose, ADERH introduces the concept of hypersphere density:
Definition 3.7 (Density of hypersphere). The density of hypersphere with associated region X (see Eq. 4) is defined as:
[x DD)
Density (H)
(8)
R(H)

---

As explained above, the greater the density of hypersphere, the more likely it is to be hypersphere centered around a normal sample. In contrast, a hypersphere built around an abnormal sample has a lower density. We normalize the densities by considering the density of the hypersphere with the highest density in (S.). Consequently, the maximum normalized density of hypersphere 1.
Definition 3,8 (NDensity of hypersphere). The normalized density of hypersphere is defined as:
Density(H()
NDensity(H,a) ee(s) Density(H(,)
3.5
Anomaly score
In the subsequent section, we detail the computation of the anomaly score. This score based on the ideas of Density and Pitch, addressing both Anomaly Contamination and Anomaly Hyperspheres. First, we define the weighted Pitch (WPitch), which combines the Pitch of sample with the NDensity of corresponding hypersphere.
Definition 3.9 (Weighted Pitch WPitch). The weighted Pitch, denoted as WPitch, of sample I concerning hypersphere H. E {()) is defined as:
(1 iDensity(H,,)) SH))
if = C(H),
WPitch(ar H,S.
(1 NDensity (onnsity(H,SS)) S.)) Pitch(r, H),
if E XHs otherwise.
(10)
where X are the data points within (Definition 3.4p. Note that, since NDensity and Pitch are within the range 00, 1J. WPitch is also constrained to the interval [0.
Weighted Pitch. Our anomaly scoring combines ratio-based boundary measure (Pitch) with normalized density (NDensity) to highlight points that are both near a hypersphere boundary and in sparse region. By adopting a multiplicative approach, high anomaly scores only occur when both boundary proximity (Pitch = 1) and hypersphere sparsity (1 NDensity ze 1) coincide, reducing the risk of overestimating anomalies in dense areas. contrast, an additive scheme may inflate scores whenever either signal is large. As shown in Appendix R the multiplicative form consistently achieves stronger precision and recall.
Lemma 3.10 (Sparse anomaly-centered hyperspheres). Let z PA be an anomaly with miny ||=
My 2 a + For a random subset S, C DD the following holds
NDensity (.)
Proof in Appendix D. Therefore, data points inside hyperspheres centered around anomalies are assigned higher WPitch compared to data points inside hyperspheres centered around regular samples. If' point is near the center of a hypersphere with high density, the weighted Pitch (WPitch) for that point will be low, strongly suggesting it is regular sample. Since data point x can be covered by multiple hyperspheres, it is necessary to identify the most relevant hypersphere for x, iee. the one where has the minimum WPitch. This leads to the definition of the set of hyperspheres containing x:
T(x, S,) = (H) H E E(S,) A E Xx).
(11)
From this, we compute the smallest cover (SC) as follows: Definition 3.11 (Smallest Cover SC), We define the most relevant hypersphere for sample x E D in (Sa) the smallest cover (SC), determined by:
(rgmmnn WPitch(a, H. S,),), if Tf Si) # 0, 0,
SC S₁)
(12)
otherwise.
Based on SC(r,, St), we define the base anomaly score F(x, Si), which quantifies the likelihood of data point being an anomaly. This score incorporates the position of x within the hypersphere and the hypersphere's is density.
7

---

Definition 3.12 (Base anomaly score F(x, S(),, The base anomaly score of data point with respect S; denoted by F(x, S,) and is defined as:
F(x, SC(,,
if SC S,) + 0,
1,
otherwise.
The base anomaly score F(z, Si) for a data point is bounded between 0 and 1.
Lemma 3.13 (Normal and anomaly base scores). Let x be typical normal point, i.e., x lies within distance of some cluster center μi let be typical anomaly, i.e., z is at least a + 6 from every center. Suppose we draw a random subset 'D of size w. Then, with high probability,
F)x,S) < F(2,S),
meaning x gets a significantly lower base anomaly score Ihan 2.
Proof in Appendix F A single hypersphere often proves inadequate for anomaly detection in high- dimensional or heterogeneous data [Bandaragoda et al.) 2014]: if its radius is too large, it may include borderline anomalies along with normal samples; if too small, it may miss broader structures. Moreover, representing the full data distribution with hypersphere biased anomaly scores. Instead, constructing an ensemble of hyperspheres provides multiple local characterizations at different scales, offering broader coverage and mitigating the shortcomings of any single hypersphere. This ensemble strategy also leverages variance reduction by averaging individual scores [Zimek et al., 2014), thereby diminishing noise and errors. Concretely, let F(r,, St) denote the base anomaly score of a point x derived from hyperspheres created within subset S, Since subsets focus different localities and potentially produce hyperspheres of varied radii, these base scores independent but not identically distributed i.d.. Based on this, we define the ensemble isolation score I as the average of the base anomaly scores across all subsets:
lead to high- variance or
Definition 3.14 (Ensemble Isolation Score Σ). The anomaly score of sample r E D is aggregated over all subsets S, SUBSETS as:
I(x)
1
Σ S,ESUBSETS
F(r,
(13)
where is the number of subsets. This ensemble- based approach minimizes the risk of anomaly scores being disproportionately influenced by any single hypersphere. The variance of the isolation score (I(x:) is bounded by:
1
Var(I(r)) <
(14)
4n
Additionally, the probability of large deviations from the expected isolation score decreases exponentially with the number of used hyperspheres
n
2
P P(I(() E[I())] 2 <) S 2exp
(15)
+
Proof in Appendix
Theorem 3.15 (Isolation Score Separates Normal and Anomalous Points). Let x. ~ Px lie within of some pý, and PA lie at least ô from every p.- In euch subset Si, define base scores F(x, Si) via the smallest cover. Then
T(x) = Ft, T(x)
1 - Sl) n 1=1
There exist constants KN such that, with high probability
B[[(x)] = KA E[I(2)).
Moreover. Var[[())] < am decreases + oo, making the separation robust.

---

Table 1: This table reports AUC-ROC results using default parameters. Best and second-best values are shown in bold and underlined, respectively. The "AVG Rank" row lists the mean rank (lower is better). The last row shows Wilcoxon signed-rank test p-values (a 0.05); "+" indicates cases where ADERH performs significantly better.
Desser
ABIRI
Fieess
BIF
L00
DeesVVD
OC3V14
LODA
5..D
DTC
UsCAD
Cyaligss
12001)
/011710
17
118770
339819
1.991111
1196110
134811
1189115
0228 18
205/015
10971
100
0194115
109700
139114
1000
10
218110
0700
0.67116
02000
03310
(30971
0.861
000
130000
059-18
1083725
109105
2549
032719
0488113
1528715
09075
10081111
033201
1040
36 1013
10
0148710
039778
33271
18
1398111
038100
0255110
07311
03009
ATT naller
139011
1.007175
0749775
170
0340100
33577111
33075
1198770
070775
-0007
0751770
10amm
1199111
11007111
109900
1967m
17771777
000
035870
0359711
1009715
122700
039705
039701
1330
1002700
AUSBGR
0738
054878
100200
220710 (15
09951100
1001:00
130700
1399110
1043 70
196000
1154157
Casa
129110
0.3810
627010
m
033191
0.47113)
009700
020700
0300::
Meak
12410
174
1148 18
199100
190.8
19910)
0799116
19610
176 175
4197700
0997770
3.5
735
547
The values marked with indicate that an error occurred during execution.
Proof in Appendix [-] Ensemble averaging over all hyperspheres S, E SUBSETS reduces variance and smooths out errors from any single, poorly placed hypersphere. Thus, ADERH computes a final isolation score I E [o, 1] for each point by averaging local anomaly scores, with anomalies typically scoring near 1 and normal samples near O. Enlarging the ensemble (n) further lowers variance and enhances detection reliability. An ablation study in Appendix CaapendixOaandd confirms that combining Pitch and NDensity effectively addresses partial violations of ò-separation.
4 Experiments
4.1 Experimental setup
We perform a stratified 70%/30% train-test split that preserves the anomaly ratio, and normalize all features to the (0, 1] range using a MinMaxScaler [Pedregosa et al. 2011]. Experiments are repeated on three stratified splits. For methods with intrinsic randomness, per split (15 runs total per sattaset-mehhoe while deterministic methods use 3 runs (one per split). Models are trained partition. We report AUC-ROC and AUC-PR [Davis and Goadrich 2006) as mean across runs. For the experiments, we applied default parameters following the respective publications, with ADERH's parameters detailed in Appendix [ We also conducted experiments using a comprehensive grid search (details in Appendix Q). Across datasets, ADERH compared to all competitors using paired Wilcoxon signed-rank test with Holm-Bonferroni correction at q=0.05 [McDonald] 2014)). Experimental details, including runs, seeds, and significance testing, are provided in Appendix K git
run 5 seeds {0, 1, 100, 1000}
the training partition and produce continuous anomaly scores on the test
Code is available at http://tthhb.cccm/a/aaaaa/00////
4.1.1 Real-world datasets
Tables [ and Appendix L present the AUC-ROC and AUC-PR results under default settings. No- tably, ADERH achieves first place in 11 datasets and second place in 6 for AUC-ROC (Table [[]. outperforming isolation-based methods (e.g., IFFoestt and deep anomaly detection methods (e.g.. DDDDSVDD, RCA, DIF). Compared to single-sphere or single-hyperplane strategies (e.g., DeeDSVDD, OCSVM), ADERH's ensemble of hyperspheres excels by incorporating each hypersphere's 'ss position and unique weight (WPitch). Unlike INNE, which relies solely on the ratio of two hyperspheres' radii, ADERH forms pairs of compact (half-radius) hyperspheres and augments their scores with Pitch and NDensity, enabling it to better highlight borderline anomalies and nown-weight sparse, moomaly-centerse hyperspheres, thereby producing more accurate anomaly scores. Further, while LOF relies on a fixed-size neighborhood, ADERH forms an ensemble of WPitch- spheres via random pairing, creating robust multi-scale coverage and yielding top AUC-ROC rank of 1.68 (on average). ADERH also excels in AUC-PR (Appendix D. with an average rank of 2.29. Wilcoxon signed-rant -aank tests confirm that ADERH significantly outperforms its competitors both AUC-ROC and AUC-PR.
hyper-

---

Table AUC-ROC (higher is better) comparing ADERH against classical covering methods GEM and DTM. Numbers in parentheses are per-row ranks; ties share the same rank.
Dataset
ADERH
GEM
DTM
Optdigits
0.775 (1)
0.378 (3)
0.770 (2)
Skin
0.788 (1)
0.613 (3)
0.784 (2)
Pendigits
0.962 (1)
0.714 (3)
0.960 (2)
AD) 1o-Tooothbrush
0.901 (2)
0.919 (1)
0.870 (3)
Wpbc
0.554 (1)
0.513 (3)
0.536 (2)
AD-Leather
0.991 (2)
0.991
0.992 (1)
Satimage-2
0.998 (1)
0.895 (2)
0.998 (1)
Backdoor
0.889 (1) 0.664 (3)
0.852 (2)
Waveform
0.768 (1) 0.708 (3)
0.743 (2)
Cardio 0.938 (1) 0.663 (3)
0.927 (2)
AD-Bottle 0.964 (1) 0.958 (3)
0.963 (2)
Celeba 0.732 (1) 0.570 (3)
0.714 (2)
Comparison with Classical Covering Methods (GEM, DTM) Table comparss ADERH with two classical covering baselines, GEM and DTM. ADERH attains the top performance per-dataset AUC-ROC the majority of datasets, reflecting the benefit of its multi-scale hypersphere coverage induced by random pairing and the multiplicative Pitch x NDensity score, which together sharpen separation between nominal and anomalous regions.
Cross-dataset stability. To quantify robustness (Table 3 we summarize the average standard deviation across all datasets for the main competing methods below (lower is better). ADERH achieves the lowest variability on both AUC-ROC and AUC-PR.
Table 3: Average standard deviation across datasets. Relative to INNE and IForest, ADERH indicates greater stability and consistency.
Method
Mean AUC-ROC std
Mean AUC-PR std
ADERH
0.0317 0.0133
INNE
0.0241
0.0515
IForest
0.0235
0.0417
5 Conclusion
this paper, we introduce ADERH, a novel isolation-based anomaly detection method that leverages the core characteristics of anomalies: RARITY and DEVIATION. By utilizing hyperspheres and the concepts of Pitch and NDensity. ADERH delivers precise and reliable anomaly scores. Exten- sive experiments demonstrate its superiority over state-of-the-ar methods across diverse datasets, consistently achieving higher AUC-ROC and AUC-PR scores than its competitors. Additionally, ADERH is robust parameter variations and scales linearly with dataset size, making it highly practical for large, high-dimensional datasets.
Limitations
Like other distance-based anomaly detectors (e.g., Isolation Forest, LOF), ADERH is affected by the curse of dimensionality, where distance concentration weakens inlier-outlier contrast. Through its integration of multi-scale hypersphere modeling, geometry- scoring, and density- aggregation, ADERH achieves strong performance on high-ddmensional benchmarks such as AD- Leather, To-oobbbru,,h, and Census. Nevertheless, dimensionality remains fundamental challenge; Appendix T discusses future directions toward dimensionality-avee -ware and gructure-preservee models.
10

---

References
Ali H Abuzaid. Identifying density- local outliers in medical multivariate circular data. Statistics in medicine, 39(21):2793-2777 27999 2020.
Charu C Aggarwal. An introduction to outlier analysis. Outlier analysis, pages 1-34. Springer, 2016.
Shikha Agrawal and Jitendra Agrawal. Survey on anomaly detection using data mining techniques. Procedia Computer Science, 10:700-713, 2015.
Mohiuddin Ahmed, Nazim Choudhury. and Shahadat Uddin. Anomaly detection on big data in financial markets. In Proceedings of the 2017 IEEF/ACM International Conference on Advances in Social Networks Analysis and Mining 2017, pages 998-1001, 2017.
Tharindu R Bandaragoda, Kai Ming Ting, David Albrecht, Fei Tony Liu, and Jonathan R Wells. Effi- cient anomaly detection by isolation using nearest neighbour ensemble. In 2014 IEEE International conference on data mining workshop, pages 698-705. IEEE, 2014.
Tharindu Bandaragoda, Kai Ming Ting, David Albrecht, Fei Tony Liu, Ye Zhu, and Jonathan Wells. Isolation-based anomaly detection using nearest-neighbor ensembles. Compulational Intelligence, 34(4):968-99) 998688999-70000 2018.
Vic Barnett, Toby Lewis, et al. Outliers in statistical data, volume 3. Wiley New York, 1994.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymp- totic Theory of Independence. Oxford University Press, Oxford, UK, 2013. ISBN 9780199535255.
Abdenour Bounsiar and Michael G Madden. One-class support vector machines revisited. In 2014 International Conference on Information Science Applications (ICISA), pages 1-4. IEEE, 2014.
Markus M Breunig, Hans-Peter Kriegel, Raymond T Ng, and Jörg Sander. Lof: identifying density- based local outliers. In Proceedings of the 2000 ACM SIGMOD international conference Management of data, pages 93-104, 2000.
Zhangyu Cheng, Chengming Zou, and Jianwei Dong. Outlier detection using isolation forest and local outlier factor. In Proceedings of the conference on research adaptive and convergent systems, pages 161-168, 2019.
Jesse Davis and Mark Goadrich. The relationship between precision-recall and roc curves. In Proceedings of the 23rd international conference on Machine learning, pages 233-240, 2006.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density- based algorithm for discovering clusters large spatial databases with noise. In kdd, volume 96, pages 226 231, 1996.
Zeyu Fang, Ming Gu, Sheng Zhou, Jiawei Chen, Qiaoyu Tan, Haishuai Wang, and Jiajun Bu. Towards unified framework of clustering based anomaly detection. In Forry-second International Confer- ence on Machine Learning, 2025. URL http:tttt///pprrriiieiee
Parikshit Gopalan, Vatsal Sharan, and Udi Wieder. Pidforest: anomaly detection via partial identifica- tion. Advances in Neural Information Processing Systems, 32, 2019.
Sachin Goyal, Aditi Raghunathan, Moksh Jain, Harsha Vardhan Simhadri, and Prateek Jain. Droce: Deep robust one-class classification. In International conference on machine learning, pages 3711-3721. PMLR, 2020.
Xiaoyi Gu, Leman Akoglu, and Alessandro Rinaldo. Statistical analysis of nearest neighbor methods for anomaly detection. Advances in Neural Information Processing Systems, 32, 2019.
Songqiao Han, Xiyang Hu, Hailiang Huang, Minqi Jiang, and Yue Zhao. Adbench: Anomaly detection benchmark. Advances in neural information processing systems, 35:32142-32159, 2022.
Sahand Hariri, Matias Carrasco Kind, and Robert Brunner. Extended isolation forest. IFFE transactions on knowledge and data engineering, 33(4):1479-1488 2019.

---

Douglas M Hawkins. Identification of outliers, volume 11. Springer, 1980.
Alfred Hero. Geometric entropy minimization (gem) for anomaly detection and localization. Advances in neural information processing systems, 19, 2006.
Hyder John and Sameena Naaz. Credit card fraud detection using local outlier factor and isolation forest. Int. J. Comput. Sci. Eng, 7(4):1060-1064 2019.
Piyush Kumar, Joseph SB Mitchell, and E Alper Yildirim. Approximate minimum enclosing balls in high dimensions using core-sets. Journal of Experimental Algorithmics (JEA), 8: 8:1-1, 2003.
Boyang Liu, Ding Wang, Kaixiang Lin, Pang-Ning Tan, and Jiayu Zhou. Rea: A deep collaborative autoencoder approach for anomaly detection. In IJCAI: proceedings of the conference, volume 2021, page 1505, 2021.
Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. 2008 eighth ieee international conference on data mining, pages 413-422. IEEE, 2008.
Victor Livernoche, Vineet Jain, Yashar Hezaveh, and Siamak Ravanbakhsh. On diffusion modeling for anomaly detection. In The Twelfth International Conference on Learning Representations, 2024. URLhatpss//oopeneeveeww.. www.:neeefooooo http://wwww....tttooooooooooded.
Romany Mansour, Sayed Abdel-Khalck, Inès Hilali-Jaghdam, Jamel Nebhen, Woong Cho, and Gyanendra Prasad Joshi. An intelligent outlier detection with machine learning empowered big data analytics for mobile edge computing. Cluster Computing, 26(1):71-83, 2023.
John H. McDonald. Wilcoxon signed-rank test. Handbook of biological Statistics, pages 186-189, 2014.
Guansong Pang, Chunhua Shen, Longbing Cao, and Anton Van Den Hengel. Deep learning for anomaly detection: review. ACM computing surveys (CSUR), 54(2):1-38, 2021.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathicu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Tomáš Pevný. Loda: Lightweight on-line detector of anomalies. Machine Learning, 102(2):275-304, 2016.
Lukas Ruff. Robert Vandermeulen, Nico Goernitz, Lucas Deecke, Shoaib Ahmed Siddiqui, Alexander Binder, Emmanuel Müller, and Marius Kloft. Deep one-class classification. International conference on machine learning, pages 4393 4402. PMLR, 2018
Bernhard Schölkopf, John C. Platt, John Shawe-Tayle Taylor, Alexander Smola, and Robert C. Williamson. Estimating the support of high-dimensional distribution. Neural Computation, 13 (7):1443-1471, 2001, doi: 10. (162//08999666175522299979
Clayton Scott and Robert Nowak. Learning minimum volume sets. Advances in neural information processing systems, 18, 2005.
Jian Tang, Zhixiang Chen, Ada Wai-Chee Fu, and David W Cheung. Enhancing effectiveness of outlier detections for low density patterns. In Pacific-Asia conference on knowledge discovery and data mining, pages 535-548. Springer, 2002.
Xiaoling Tao, Yang Peng, Feng Zhao, Peichao Zhao, and Yong Wang. A parallel algorithm for network traffic anomaly detection based on isolation forest. International Journal of Distributed Sensor Networks, 14(1
2018.
David MJ Tax and Robert PW Duin. Support vector data description. Machine learning. 54:45-66. 2004.
Srikanth Thudumu, Philip Branch, Jiong Jin, and Jugdutt Singh. comprehensive survey of anomaly detection techniques for high dimensional big data. Journal of big data, 7(1):42, 2020.
12

---

Hongzhi Wang, Mohamed Jaward Bah, and Mohamed Hammad. Progress in outlier detection techniques: survey, leee Access, 1:107964-108000) 2019a.
Hu Wang, Guansong Pang, Chunhua Shen, and Congbo Ma. Unsupervised representation learning by predicting random distances. arXiv preprint 1rXiv::912.121888 2019b.
Zhangming Xiong, Daofei Zhu, Dafang Liu, Shujing He, and Luo Zhao. Anomaly detection of metallurgical energy data based on iforest-ae. Applied Sciences, 12(19))9977, 2022.
Dong Xu, Yanjun Wang, Yulong Meng, and Ziying Zhang. An improved data anomaly detection method based on isolation forest. In 2017 10th international symposium on computational intelligence and design (ISCID), volume 2, pages 287-291. IEEE, 2017.
Hongzuo Xu, Guansong Pang, Yijie Wang, and Yongjun Wang. Deep isolation forest for anomaly detection. IEEE Transactions on Knowledge and Data Engineering, 35(12):12511-126) 2023a.
Hongzuo Xu, Yijie Wang, Juhui Wei, Songlei Jian, Yizhou Li, and Ning Liu. Fascinating supervisory signals and where to find them: Deep anomaly detection with scale learning. In International Conference on Machine Learning, pages 38655-3867, PMLR, 2023b.
Yue Zhao, Zain Nasrullah, Maciej K Hryniewicki, and Zheng Li. Lsep: Locally selective combination in parallel outlier ensembles. In Proceedings of the 2019 SIAM international conference on data mining, pages 585-593. SIAM, 2019a.
Yue Zhao, Zain Nasrullah, and Zheng Li. Pyod: A python toolbox for scalable outlier detection. Journal of machine learning research, 20(96): 2019b.
Arthur Zimek, Ricardo JGB Campello, and Jörg Sander. Ensembles for unsupervised outlier detection: challenges and research questions position paper. Acm Sigkdd Explorations Newsletter, 15(1): 11-22, 2014.
13

---

Appendix Section
Content
Appendix
Balanced shrinkage of pairwise distances
Appendix
Multi-Scale coverage and justification for random pairing hypersphere ensembles
Appendix
Analyzing the distribution of the radii of hyperspheres created by ADERH
Appendix
Proof of Lemma 3.10
Appendix
Variance reduction and error bounds for the ensemble anomaly score I
Appendix
Proof of Theorem 3.15
Appendix
Algorithmic details
Appendix
Parameter setting
Appendix
Robustness
Appendix
Datasets
ppendix
Experimental details
A ppendix
AUC-PR Results
ppendix
Runtime complexity
A ppendix
Runtime experiments
ppendix
Ablation study: different settings of ADERH
Appendix
Ensembling improves anomaly detection over any single subset Grid search experiment for isolation and non-isolation methods Ablation study: multiplicative vs, additive Fusion Limitations
Appendix
Appendix
Appendix
Appendix
Future work
Table 4: Structure of the appendix.
A Balanced shrinkage of pairwise distances
We present a mathematical argument indicating that among all scaling factors a E (0, 1], setting provides the best balance between (i) ensuring that hyperspheres remain compact enough to avoid covering anomalies, and (ii) retaining enough coverage to include normal points within the same local region. Our analysis assumes typical "ő-separation" setting where normal clusters have radius at most a, and anomalies lie beyond + ö from each cluster center.
ō-assumption: Assume each normal cluster has radius That is, any two normal points æ, in the same cluster satisfy
| - vll s 20,
since each lies within distance of the same center. Anomalies lie at least a + 8 away from every cluster center, with
Shrinking Factor E (0, 1]: Given pair (æ, y) of points, suppose we define a hypersphere with radius
|| v/l.
We compare different values of a (0, 1].
Lemma: coverage criterion for normal pairs
Lemma A.1. Let x. y be two normal points from the same cluster. with || lır-yl yl S 2o. If ||0 yl < a, then this hypersphere fully covers the local region of radius around one center. Equivalently.
=
yl
if || all < 2o. In particular, if 1 then
a ||
yl < whenever ||x yll 2o.
Sketch. Since || - y|1 < 2o, multiplying by (or any S 1 ensures the radius does not exceed a. Hence, normal points within that cluster remain inside near the hypersphere, supporting good coverage of normal data.
14

---

Lemma: exclusion criterion for anomalies
Lemma A.2. Let be an anomaly with distance at least a + 5 from every normal cluster center, and let be a normal point in some cluster. If = 2 8, then any hypersphere with radius strictly below 6 around will not include 2. In particular, if a || yll å for normal points 2, y, then distant anomaly remains outside that hypersphere.
Sketch. From the typical o-separation assumption, normal-anomali anomaly distances exceed ò. Thus, if the hypersphere radius at most ó, the anomaly cannot lie inside same hypersphere.
Balancing coverage exclusion
We want a || - y to be v for normal-norma pairs (to ensure good coverage), yet also S ô (or at least not too large) so that anomalies do not get unintentionally included. Setting 2 provides natural boundary:
1. 1 yl1 20 - -11 - yll S so normal points in the same cluster remain covered.
2. If || y/1 ~ 2( + 5), halving prevents the radius from reaching o + 6. Therefore, hypersphere centered on normal point is less likely to include anomalies that lie beyond a + 8.
By contrast, a < 2' we risk under- novericg normal points (the radius becomes too small, potentially splitting the cluster). If a > 1,, the radius can exceed a, enlarging hyperspheres such that anomalies may sneak inside.
1
Proposition A.3. Under the conditions of Lemmus A.7 and A.2 consider a E (0, 1] as a scaling factor for the pairwise distance || y/l. Setting ensures both:
1. Adequate local coverage of normal-normal pairs, since ail yll S whenever ||x yl 20,
2. Limited overshoot for larger distances, so that hyperspheres around normal points are less likely to include anomalies lying beyond + 5.
Thus, a provides balanced trade-off between cluster coveruge and anomaly exclusion, though not necessarily an optimal choice a formal sense.
Sketch. For a < 1, hyperspheres become smaller than a even when ||x - yll S 2o, under-covering normal regions. For a > 1. hyperspheres can exceed a, risking inclusion of anomalies. Thus a = the threshold guaranteeing cluster coverage without inflating radii enough merge anomalies.
Empirical evidence Our theoretical discussion is corroborated by the experimental results in 5 where
consistently demonstrates strong performance. The table compares ADERH scores across four scaling factors (0.25, 0.5, 0.75, and 1.00). Despite partial violations of striet ō-separation (e.g., overlapping clusters or varied cluster sizes), a J attains the best average rank, consistently striking a balance between sufficiently covering normal clusters limiting radius overshoot that includes anomalies. In practice, halving the pairwise distance still prevents hyperspheres from becoming too large and diluting their ability to isolate anomalies, reinforcing 1/2 as robust heuristic-evee even beyond the perfect d-separation setting.
Conclusion
Mathematically, halving the distance ||I yll avoids excessively large hyperspheres that might encompass anomalies, while still ensuring that two normal points within the same local cluster remain covered. Any fraction a sacrifices coverage of normal data, and any a Y raises the risk of anomaly inclusion. Hence emerges compromise for multi-scale isolation.
B Multi-Scale Coverage and Justification for random pairing
In this appendix, we provide a mathematically grounded rationale for using random pairwise distances as the basis for local structures (c.g., hyperspheres) in anomaly detection. We show how sampling
15

---

Table 5: The table shows the results for ADERH for different radius scalings (0.25, 0.5, 0.75, 1.00).
Dataset
ADERH
ADERH-0.25
ADERH-0.75
ADERH-1.00
Lymphography
1.000 (1)
1.000 (1)
1.000 (1)
0.833 (4)
Pendigits
0.309 (1)
0.305 (2)
0.294 (3)
0.291 (4)
AD-
0,840 (1)
0.783 (4)
0.826 (2)
0.786 (3)
Wpbc
0.261 (1)
0.258 (3)
0.260 (2)
0.255 (4)
AD-Leather
0.975 (1)
0.970 (3)
0.973 (2)
0.954 (4)
Backdoor
0.222 (2)
0.312 (1)
0.221 (3)
0.193 (4)
Cardio
0.588 (1)
0.532 (4)
0.586 (2)
0.554 (3)
AD-Bottle
0.940 (2)
0.914 (4)
0.943 (1)
0.928 (3)
Census
0.075 (2)
0.081 (1)
0.073 (3)
0.000
Musk 0.222 (2)
1.000 (1)
1.000 (1)
1.000 (1)
1.000 (1)
Glass
0.111
0.221 (3)
0.223 (1)
AVG Rank
1,36
2.55
2.09
3.18
pairs (X,Y) Y) at random from dataset naturally spans wide range of distances, thereby offering multi-scale coverage with minimal manual tuning.
Random pairwise distances
Let D C Rd be drawn from an unknown distribution P. Define two i.i.d random variables X, Y P. and consider the distance
D = ||x -YI-
Our goal is to approximate the distribution of D by randomly pairing points in small subsets of D. Concretely:
Subset Selection:
Choose small subset T C D of size
Random Partnering: For each x E T. select partner E T uniformly at random.
Distance Extraction: Record the distances ||x y|l- Repeating over multiple subsets yields
a set of pairwise distances approximating Fp, the distribution of ||X Y|I in the entire dataset.
Theoretical underpinnings
Lemma B.1 (Short Distances: Intra-Clusted Pairs), Let C Rd be a set of points with diameter a, meaning || vll S for all x,y E C. IfPr(X CC) 0, then
Pr(D 30)2d
Since X,y Y are i.d. Pr(X C, Y C) a². Pr(D I <a) 2 a².
Inside C, all distances are S a. Hence
Lemma B.2 (luter-cluster pairs). Let C1, C2 C R be disjoint sets with
A min
|| yll > 0, Pr(X E Cx)= an, Pr(X C2) = 02--
xeC,, SEC₂
Then
Pr(D > A) > 2ajaz.
Proof. Because (X, Y) are i.i.d.,
E YEC2) 0102,,
Pr(EEC2, Y 02001
The two events are disjoint and each guarantees || Y 2 A. Summing them yields the stated lower bound.
For any pair (X C1, Y E C2), the distance least > The probability of drawing such pair is 0202. Thus Pr(D > A) > 20 ag.
16

---

Multi-Scale coverage
Theorem B.3. Combining Lemmas B.1 and B.2 shows that if the data contains multiple clusters or distinct subregions, random pairs inevitably yield both small distances (within clusters) and large distances (across clusters). Thus, the distribution of D spans a continuum from local to global scales in proportion to the dataset's ' mixture structure. No single global radius needs to be chosen priori, as the data itself reveals numerous scales.
Benefits of random pairing
The use of random pairwise distances offers several key benefits in anomaly detection. First, provides data-driven, multi-scale representation, sampling pairs from the empirical distribu- tion of ||_ - Y| inherently captures both small (intra-cluster) and large (inter-cluster) distances. Consequently, need not pre-specify single global threshold neighborhood size, which is especially important in the presence of heterogeneous cluster densities. In addition, random pair- ing naturally accommodates multiple, possibly irregularly shaped clusters, since each subset-based pairing reflects local geometric structures without requiring exhaustive distance computations or fully global operations. Repeated sampling of these pairs further promotes broad coverage of the data distribution, ensuring that relevant scales-ranging from tight local neighborhoods to more expansive separations- are collectively included in the modeling. Practically, the process is also computationally simple, as each subset only requires points, and pairing them is straightforward; this avoids the expense of building full distance matrices on the entire dataset. Overall, random pairing thus integrates local adaptivity, multi-scale sensitivity, and computational efficiency in single procedure, making it both robust and scalable for real-world anomaly detection scenarios.
Empirical confirmation
In Appendix C we illustrate this behavior using real-world data. The distribution of distances ||X - YIl is often multi-modal. Small-distande peaks align with compact clusters, while heavy tails arise from inter-cluster distances or outliers, confirming the guarantees given in Lemmas A.1-A.2.
B.1 Concluding remarks
Random pairing of points is a simple yet powerful tool for capturing the full range of distances in dataset. This mechanism organically yields small distances in dense clusters and larger ones across sparser regions. We emphasize:
No single scale must be predetermined.
Multi-scale structure emerges directly from the distribution of X - Y||-
Cluster shapes and heterogeneity are naturally captured- crucial for effective anomaly detection.
C Analyzing the distribution of the radii of hyperspheres created by ADERH
Having established in Section that random pairing of points theoretically enables multi-scale cover- age, we now illustrate these claims with real-world data. Specifically, we examine the distribution of hypersphere radii generated by ADERH via randomly paired points. As shown in Figure 3 the resulting radii indeed cover a broad range, validating our theoretical analysis in three ways:
1. Small intra-cluster radii. In denser regions of the data, random pairs of nearby points produce hyperspheres with small radii, capturing fine-grained local neighborhoods.
2. Large inter-cluster radii. regions separating distinct clusters or featuring anomalies. random pairs tend to yield comparatively larger radii, thereby modeling more global scales.
3. Mixed scales in heterogeneous data. In practice, many real-world datasets exhibit multiple, potentially overlapping clusters of various densities. Our empirical results indicate that even a modest number of random subsets and pairings sufficient uncover hyperspheres at numerous scales simultancously.
17

---

Overall, these observations lend strong empirical support to the multi-scale coverage facilitated by our random pairing strategy. They also highlight how data-specific structure centturrrwwetterr is tight clusters, more diffuse distributions, or the presence of outliers-
arises in the empirical distribution of pairwise distances. Hence, without requiring explicit parameter tuning for a single global scale, our procedure effectively adapts to the intrinsic geometry of each dataset.
1.0
1.0
1.0
0.8
0.8
0.8
Density
0.6
Density
0.6
Density
0.6
0.2
0.2
0.2
0.0 0.00
0.25
0.50
0.75
1.00
0.0
0.00
0.25
0.50
0.75
1.00
0.0
0.00
0.25
0.50
0.75
1.00
Radius
Radius
Radius
Waveform
Vowels
Skin
1.0
1.0
Density
0.6
Density
0.6
0.6
Density
0.4
0.4
0.4
0.2
0.2
0.00
0.000
L.00
0.000
Radius
Radius
Radius
Mnist
Musk
Satimage-2
Figure 3:
The distribution of the radii of hyperspheres created by ADERH for each dataset (scaled to
[0, I).
18

---

D Proof for Lemma 3.10
Proof. Let be the dataset, and let S; S DD be (random) sample of size |Sy].
Separation assumption. By Definition
any anomaly 2 satisfies
dist(2, 2 + for every normal cluster center Mjj
Hence, the distance from 2 to the boundary of any o-radius normal cluster is at least ò.
Sparse coverage by anomaly-centered hyperspheres. Choose radius such that
yo with 8
Since yya < 6, any ball of radius r around an anomaly 2, i.e. the set
x || =1 s r)
does not intersect (or barely intersects) the normal clusters. Indeed, each normal cluster of radius is at least ô away from and 8 r > 0. Therefore,
{ { S. || =11
r) O with high probability.
Formally, by Chernoff or Hoeffding bounds, the probability that random sample of normal points places more than a negligible number of points inside {x : ||ı - z|| S r} decays exponentially in [S,]. Thus, the hypersphere Hzz) of radius around captures almost no normal points, making its density
Density(H(()). { D: |
2 $
0.
High coverage by normal-centered hyperspheres of similar radius. Next, consider a normal point y lying near its normal cluster center μyy with |yy My I a. For no (the same radius as above), the ball
{o: || vll r}
fully contains (or nearly contains) the o-radius cluster around μıj Consequently, there are many normal points in that ball, and hypersphere H'' of radius centered such a normal y will have substantially higher density:
Density (H²) > Density Density(H((z)).
Let (S,) denote the set of all hyperspheres of radius centered at points in S, Then
Density(H()
Density(H(())).
#/'E (S.)
Normalized density goes to zero. Define the normalized density of the anomaly-centered hyper- sphere by
Density(H(())
(Deensity(H(2))
maxHreeu(s.) Density(HH)
19

---

Since the density of M((2) is extremely small while there exist Normal-centered hyperspheres of radius r with significantly higher density, we conclude that
NDennityy((2)) 0.
Moreover, by standard concentration arguments (e.g. laws of large numbers for the fraction points in given region), this low-density phenomenon holds with high probability over the random choice of S, As |S,] + oc, the probability that any anomaly-centered sphere has more than negligible fraction of normal points converges to O. Therefore,
NDensity(H(2)) - 0
in probability (and typically exponentially fast in [S)). This completes the proof.
E Variance reduction and error bounds for the ensemble anomaly score I
To demonstrate variance reduction (proof for Eq. 14 for the ensemble isolation score, proceed in the following steps:
Lemma E.1 (Variance Bound for Individual Isolation Scores). For single subset S,, the variance of the base anomaly score F(x, S:) is bounded by:
(a) S
Proof. The base anomaly score F(x, S;) random variable bounded in the interval [0, 1]. For any random variable X with values in (a, b). the variance is bounded by:
(b-a)² a)
Var(X) S
Here, a 0 and = 1, so:
(1 0)
Var(F(x, <
Thus, the variance of the base anomaly score is bounded as claimed.
Lemma E.2 (Variance Reduction for Ensemble Isolation Score). Let the ensemble isolation score I(x) be the average of n independent base anomaly scores:
T(x) =
Si)
Then, the variance of [xx) satisfies:
Var(I(z)) <
4n
Proof. Let F; = F(x, for simplicity. The variance of the average of n independent random variables is given by:
1
1
Var
F
Var(F.).
n²
i=1
1=1
From Lemma E.1 we know that Var(F.) < for all i. Substituting this bound:
1
Var(1(x)) n 1=1
Var(F)) <
Simplify the summation:
1 1
Var(T(x)) <
n 4
4n
Thus, the variance of the ensemble isolation score is bounded by in stated in Eq. in the main paper.
D
20

---

Error Bound via Bernstein's Inequality Boucheron et al. [2013
Lemma E.3 (Error Bound). Define the average variance v² Ei Var(Fi), which satisfies
u² S 2: Then, for any >> O, the probability that (x) deviates from its expected value [[[(x)) by at least bounded by:
ne² 33
P P(((()) - E[]( 2 $ 2xxp
Proof. We apply Bernstein's 's inequality for independent random variables. Let F; be independent with mean b4 B[F,), variance vi Var(FF), and bounded range [0, 1]. The inequality states:
n
n²6²
P
Σ
(Fi 1e) 2 ne S 2exp
2 1/ + f
Substituting ((x) and scaling by :
ne
P P(T(()) B[T(x)] 2() 2exp
2v² + E
where - 1==1 os is the average variance. Using Lemma Substituting this bound:
E.1
we know vs s _ v² S
ne
P P(((()) - E[[(=)] 2 c) < 2exp
Therefore, the probability large deviations from the expected isolation score decreases exponentially with the number of hyperspheres stated in Eq. 15 in the main paper.
F Proof of Theorem 3.15
We prove that under the 5-separation assumption, normal point æ obtains small isolation score [(x), whereas a "typical" anomaly z obtains a large isolation score.
Proof. We break the proof into two parts: we first prove Lemma 3.13 then analyze the ensemble average over subsets.
Part A: Proof for Lemma 3.13
By the d-separation assumption (Definition 3.1 there exist radii o,, and small e, E (0, such that:
1. Normal-Point Proximity: With probability 2 1 - e over the draw of a normal point PN, there exists at least one center μ4 satisfying || U4 o.
2. Anomaly Exclusion: With probability 2 1 e over the draw of anomaly PA. have =| - H1ll 2 a + 8 for all j.
Let be the size of each sampled subset, and let {S be the i.i.d. subsets. Consider one such subset S. Denote by
E "event that S includes at least one normal point from each cluster,"
whereby "each cluster" we informally refer to each center by with nontrivial normal mass. More precisely, define C₁ := { x || M,l s a), and
ε = {S S S + Ø for all relevant j).
21

---

We can bound Pr(E) away from zero if w is large enough relative to the number of clusters (and using the fact that normal points constitute an a-fraction of the data). For instance, by the binomial bound, one gets
Pr(E) 2 1- do.
for some small ón- Below, we condition on & and also condition on the event that the chosen point Pv satisfies the normal-proximig property (probability 2 1 E) or that 2 ~ PA satisfies the anomaly-exclusic property (probability E').
A1. Normal points obtain small F
Fix normal point Suppose (i) æ lies within of some center Mjj, and (ii) the event & holds for S. Because S n C2 + Ø, there is at least one point E also within that same cluster. In fact:
If y is paired with another point y in the same cluster, the radius &lly y'1l S a. This hypersphere is dense and encloses x near its center, so Pitch(x) < 1 and NDensity 1. Hence, the weighted distance WPitch(4)) R O.
If y is instead paired with point outside the cluster, the resulting hypersphere might be larger. However, still typically sits closer the center than does any far-away anomaly, implying WPitch(r) remains relatively small compared to that of an anomaly.
Among all hyperspheres covering x, we select the "smallest cover," i.c. the one that minimizes WPitch(z). Thus
S)x = min WPitch(2, H) < 1.
H32
Formally, can show that, conditioned on & and the event || Myl S we have F(I, for some small < 1. Overall, the probability that Fix, S) I p is at least
(1 -) =) x (1 -6)) 2 1 - (5+
A2. Anomalies obtain large FF
Now fix an anomaly Suppose || UUll for all (probability 2 =²). Two cases arise:
1. not in S.
If a normal-centered hypersphere covers 2, that hypersphere has radius S a. Since = stands at distance 2 5 from the center, Pitch(=) Rs Otherwise, if is not covered, F(2, 8) by definition.
2. = in S.
A hypersphere centered on is sparse (few neighbors), thus NDensity & 0. Hence WPitch(2)) zs Pitch(z) ss 1.
both scenarios, no hypersphere yields WPitch < Consequently,
F(z,8) 2 7
for close to 1. The probability of this event is at least 1 e'. Thus, for typical anomaly F(2, S) = 1 occurs with probability 1
Part B: Ensemble averaging
Since the subsets S Sn are i.i.d. uniform samples, the probability that each & is high. Even if some subsets fail, the majority will cleanly separate normal points from anomalies. Formally:
Expected base score. Define
KN E[F(x.S) Py], RA E[F(2, S) Pal:
By the above arguments, AN < KA 1. Typically KN P 0 and KA 1.
22

---

Final isolation score. For each point z, define
((x) = 7 Σ F(),S)).
By linearity of expectation, E[((2) Pv] = KN and (x((x) x E PA] = KA. Hence KN < AA implies that normal points will, on average, have lower isolation scores than anomalies.
Variance and concentration. Each S(),S;) takes values in [0, so Var(F) S 4. By standard variance-addition or concentration bound (e.g.. Bernstein's inequality). the averaging over n subsets yields Var[7(*)] I 1 Thus, with high probability over the sampling of S, the isolation scores for normal points cluster around K and for anomalies around KA, creating clear separation as grows.
Conclusion: [(normal) = AN < KA R (anomally) with high probability,
G Algorithmic details
In general, ADERH separates anomalies from regular samples in two-step process (see Algo. TT.
Step I. In the first step, ADERH generates of subsets by performing uniform random sampling with replacement, denoted as SUBSETS(D, n, w) = ........,,, For each S; E SUBSETS and all elements x E S,, a random partner with y E S, is determined. Subsequently, two hyperspheres with the centers and y are formed. We consider an ensemble of hyperspheres with varying radii, where ADERH estimates key properties such as the density of each hypersphere under the empirical data distribution.
Step II. ADERH utilizes an ensemble of hyperspheres across all SUBSETS minimize variance and reduce deviations in the computed anomaly scores, enhancing robustness. For each data point and each subset S; E SUBSETS, the algorithm determines the smallest cover SC(x, S.). By considering the positions of the data points and the densities of the ensemble of hyperspheres, ADERH calculates the anomaly score based on the smallest covers across the different subsets. If data point consistently receives high anomaly scores from the ensemble of hyperspheres, it can be confidently identified as an anomaly.
H Parameter setting
In ADERH, we fix two principal parameters: (i) n. the number of random subsets (the ensemble size), and (ii) w, the size of each random subset. These choices mirror the logic behind Isolation Forest (IForest) Lif et al. 2008). which typically employs about 100-300 estimators (trees) and often uses up to 256 samples per tree. We adopt = 256 in similar spirit: increasing the ensemble size reduces variance (see Appendix but we observe diminishing returns beyond 200-300 subsets in practice (Fig. (b)..
Where FFoesst allocates 256 data points each tree, ADERH requires far fewer points per subset, and we set w = 18. The rationale is that ADERH does not rely on hierarchical splits but rather forms hyperspheres from pairs of points in these small subsets. Smaller subsets risk underrepresenting normal structure, while larger subsets incur higher contamination probability (since more anomalies might appear among the centers) and yield limited gains in AUC-ROC or AUC-PR (Fig. [4a.. Consequently, w = 18 balances computational efficiency with coverage of the underlying data patterns, allowing ADERH's hyperspheres to remain compact and centered around typical (normal) samples.
Competitor's parameter For competitors, we used the default parameter settings as specified in the respective papers (Table 7)
23

---

Algorithm 1: ADERH
input ddatasct: D.
# subsets: u.
subset size: w
output: containing the anomaly score samples /
At the beginning, all anonaly acores are initialized with
Z ==
// First, a subsete are geperated via randon sampling vith replacezent, vhere each subset containe w samples (Definition 3.2p.
initialize SURSETS(D, nJ
Eat
for S, SUBBEETS n.
E(S,) := for
// Generate the hyperspheres of the data point x and its randon partzer according to Dofimition 3.4
# M(a, S,) 77 Rypersphera with center
7 H(P(z, S.).S) // Hyperaphere with center P(z, S.)
Determine the density of the created hyperepheres (Definition 3.7
Density (P)) 1Xxm2
R(R)
Density(?k') ID)
BCR')
// Add the two hyperepheree to the ensemble (Definition 3.5 ((S,) = E(S,) (H,'H)
11
12
end
Normalize densities hyperepheres according Definition 3.8 for H E E(S) do
13
14
(Density(H.S)) mEEN)EEES (M,)
(ensit((N)
16
Eu Ea ((S)
17
end
18
((S))
Esn for D do
19
If the data point covered by at least one hypersphere 'H E ((S)), ) the isolation value is
evalusted according Definition [3.14 If the data point not covered by any hypersphere, then it receives the maximum value of 1.
20
T(y) :m T(y) S.)
21 end
end
Satimage
0.78
ROD-UU0
0.73
WBC
Lymphography
WDBC
025
025
MNIST-Stripe
AD-Leather
(a) Varying the sample size w (n 256)
=(b) Varying the number of subsets
Legend
18)
Figure 4: Stability comparison of ADERH by increasing the sample size and number of subsets n.
Grid search experiment In addition to the default settings, we conducted a grid search experiment further investigate performance by exploring various parameter configurations for both ADERH and the competitors (Appendix Q
I Robustness
In the following, we investigate the behavior ADERH with regard to parameter stability. In first experiment (Fig. 4), we increase the sample size w of a random subset S; (|S;) =w) As shown in Fig. 4a ADERH generally attains high AUC-ROC values across varying cardinalities w of the random subset S,. In the second experiment (Fig. 4b). we increase the number of subsets n. As

---

expected, slightly better values are achieved when the number of subsets increases. As increases, more estimates can be made, improving anomaly detection aceuracy. Moreover, these observations align with our findings on variance reduction. By increasing we effectively reduce the variance over base anomaly scores and increase robustness and, according to the Bernstein inequality, lead to tighter bounds and greater reliability in distinguishing anomalies.
J Datasets
Details regarding the used datasets are given in Table
Table 6: Statistics of the used datasets
Dataset
# Instances
# Dimensions
# Anomalies (%)
Optdigits
5216
64
150(0.0288)
Wbc
223
10(0.0448)
Lymphography
148
18
6(0.0405)
Celeba
202599
39
4547(0.0224)
Skin
245057
3
50859(0.2075)
Pendigits
6870
156(0.0227)
Wdbc
367
30
10(0.0272)
ADTootthbrush
10000
512
500(0.0500)
Wpbc
198
33
47(0.2374)
AD-Leather
10000
512
500(0.0500)
Satimage-2
5803
36
71(0.0122)
Backdoor
95329
196
2329(0.0244)
MNIST-C-Stripe
10000
512
500(0.0500)
Waveform
3443
21
100(0.0290)
Cardio
1831
21
176(0.0961)
AD-Bottle
10000
512
500(0.0500)
Census
299285
500
18568(0.0620)
Wine
129
13
10(0.0775)
Musk 3062
166
97(0.0317)
K
Experimental details
Experiments were conducted on an Intel Core 17-10700K, 3.8 GHz, 32 GB RAM, with runtime aver- aged over consecutive runs. Real-world datasets were sourced from the AdBenchmark repository Han et al. 2022], with MNIST-Variation and AD- Variation datasets derived using ResNet18 features pre-trained on ImageNet Han al. [022]. Table summarizes dataset statisties. Implementations were obtained from Zhao et al. 2019b Xu et al.
2023a
We now detail the common experimental procedures used across all experiments in this paper:
1. Datasets and Preprocessing. We consider D real-world datasets, each containing a mixture of normal and anomalous points. To maintain consistency, we normalize all datasets the range [0, 1] using the MinMaxXcaler Pedregosa et al. 2011] A summary of each dataset's statistics is provided in Table 6
2. Train/Test Splitting. We employ stratified split with 70% of the data for training and 30% for testing, ensuring that both splits maintain the same proportion of anomalies. This split is repeated three times with different random seeds; we report the average performance metrics (AUC-ROC and AUC-PR) across these three runs.
3. Evaluation Metrics. We adopt the AUC-ROC and AUC-PR Davis and Goadrich 2006 as our primary metrics, as they are widely used and provide stable comparisons for imbalanced datasets. We also conduct a paired Wilcoxon signed-rank test with Holm- Monfferrfrr correction McDonald (2014) to determine statistical significance.
4. Implementation Details. All methods (including ours) are implemented in Python, and we use the public repositories Zhao al. (2019b) Xu et al. [2023a] for baseline implementations
25

---

Table 7: Default parameter setting.
Algorithm
Description
Sct
ADERH
n
[256}
[18]
#estimators
[200]
INNE
#mazsamples
(8)
#estimators
100}
Isolation Forest
#mazsamples
256)
max maxfeatures
[1.0]
extensionlevel
[1]
EIF
#mazsamples
[256]
#estimators
[100}
#ensemble
[}
DIF
#estimalors
(100)
#mazsamples
[256)
maxdepth
10
PIDForest
#trees
(20)
# #smmlees
[256]
LOF
MinPts
[5]
epochs
[100)
DeepSVDD
batchsize
(32)
dropout
[0.2]
kernel
RBF]
degree
[3]
OCSVM
tol
[le {1e-3}
nu
[0.5]
epochs
[100]
batchsize
(64)
RCA
Ir
[le 33
repDim
128]
epochs
100
batchsize
64)
RDP
Ir
lle
pri_steps
(10)
#bins
10
LODA
#randomeuts
100
epochs
100
batchsize
128
SLAD
lr
lle }
n_slad_ensemble
200)
pubspace_pool__ size
50
26

---

Table 8: This table presents the results of all algorithms using the default parameters outlined in the original paper. Hereby, the best values are shown in bold, and the runner-up is underlined. The 'AVG Rank' row of the table lists the average rank achieved by all algorithms in the metric AUC-PR
Deauer
>D0RI
INND
Depeovon
RCA
OCSVM
LODA
SLAD
DTT:
UNGCAD
Cyslges
60:34
0.562
0400403)
0.809
0030100
6003(10)
0333..0
144811
11151155
017
0535
0:399.0
1266115
4.97755
0.12115
EMIETS
Cane
0.58 (4)
2899775
0818:20 281
6101475
0.011 (90
6636.73 (73
6985133
0.58.00
0930
038617
0356100
620 00
039718
039
110
125
0.21
607210
01097
0326.11
1030
1206165
1111700
0139111
0337781
0331111
0740175
078475
139
0766.00
0026-10
0.8.0
0.90118
039911
0.28
1003
96
0383700
0.292
(2)
0002
039
038979
0346
020
0009:30
0300795
07227111
102
(097704)
0204 03
10307725
0351111
1091
30
000500
0399
(2:5
0000
159
1092014
0339 11
0.2 (11
0.35120
107001555
"Marle
(175111
(6
0997/00
E99479
63317775
0000
EX0106
0.344:1
1007 30
029003
0223781 (01
0036
190
10097185
01430113
10051155
7323 15
Camaa
13311
0.497135
639029
234214
0387133
0092112
0099/00
0499 51
11005111
0001
6008117)
(73077)
1030
Vin
710.00
378055
020
0170000
m
020300
mm
1077
1771
130
1000110
socame
coupen
The values marked with iidicatte that an error occurred during execution.
where available. Where randomness involved, we run each method using five different random seeds [0, 1, 100, 1000] and average the metrics to ensure robustness.
and reporting our results, the best-performing method on each dataset is shown in bold, and the second-best is underlined. The "AVG Rank" row presents the mean rank of every algorithm, where lower rank denotes stronger performance overall. The last row shows p- p-values from the Wilcoxon signed-rank test (at 0.05) comparing our method (ADERH) to each reference approach. Here, plus sign "(+)" denotes that ADERH achieves a statistically significant improvement.
Performance tables Tables I 8 g
L Additional results AUC-PR
Below, we present the additional AUC-PR results for all evaluated methods under their default hyperparameter settings (Table 8 As in the main paper's AUC-ROC comparison, ADERH con- sistently achieves top rankings across most datasets in AUC-PR. Notably, ADERH attains the best AUC-PR scores on 7 datasets and second-best on 6, yielding the lowest average rank of 2.26 among all competing methods. These results underscore ADERH'S robust performance, particularly in un- balanced scenarios where the AUC-PR metric is more sensitive to class imbalance and rare anomalies. Similar to our AUC-ROC findings, the paired Wilcoxon signed-rank tests indicate that ADERH's improvements over baseline methods are statistically significant. By forming pairs of hyperspheres with diverse radii and integrating Pitch-based boundary detection alongside NDensity-dri -rriinn hyper- sphere weighting, ADERH consistently achieves superior precision-recats performance relative to both traditional isolation- based and deep-leaminn--base based anomaly detectors across a broad range of real-world datasets.
M Runtime complexity
As described in Section G the operation of ADERH consists of two distinct steps. The computational complexity associated with each step of ADERH is explained before these findings are summarized to determine the total runtime complexity of ADERH. Initially, the algorithm generates a set of subsamples SUBSETS(D, n, w) from dataset D, where the number of subsamples equals For each individual set S, E SUBSETS(D,, n, w), the cardinality is equal to w. A pair of hyperspheres is constructed for each element ww). In addition, the density must be determined for each of the hyperspheres. This operation has a (m) complexity regarding each hypersphere, where m = [D]. This results in a total complexity of O (2)mm)) m) for the first step. For every data point within D and each element in the collection Em = (E(S),.... ),)))) the algorithm identifies the smallest covering hypersphere (SC). Given that the size of & equals and each E(S.) E Enll contains 2w hyperspheres, finding SC for all data points across all hyperspheres has a computational complexity of O n w m). By neglecting the constant factors, obtain combined runtime complexity of O(nw m). This means that ADERH
S,. Thus, the generation of the hyperspheres has a complexity of
27

---

runtine in sec (lognnthmic scale)
runtme in see (loganthmmi soale)
ADREH
10
10
IForest
DIF
10
10"
PIDForest
10
10
LOF
DespSVDD
10
10
DCSVM
RCA
10
4k
8k
16k
number of datapoints
32k 64k 128k 256k 512k
10"
32
number dimensions
84
128
256
512
1k
LODA
RDP
(a) Increasing the # of data points (# dimensions (h) Increasing the # of dimensions (# datapoints 16)
Legend
4k)
Figure 5: Runtime experiment using dataset consisting of Gaussian distributed regions with uniformly distributed anomalies around the Gaussian regions.
has the same asymptotic behavior as, for example, INNE, As the runtime of ADERH scales linearly with m, and n, the method is efficient and well-suited for large datasets.
N Runtime evaluation
In this experiment, we analyze the scalability of ADERH and its competitors, particularly other isolation-basee -based approaches. For this purpose, we created Gaussian-distributee regions with uniformly distributed anomalies around them. The default parameter settings, as described in the respective papers, were used for all algorithms (Table 7). In the first experiment, the number of data points, denoted as m, is progressively increased while keeping the number of dimensions fixed at d = 16 (Fig. 5ah. The results demonstrate that the runtime of isolation-based based methods scales linearly increases. ADERH exhibits a similar asymptotic runtime behavior as INNE or IForest, but with a consistently higher runtime by constant factor (as discussed in Section M). LOF and deep learning- based anomaly detection methods show poor scalability and are, therefore, only partially suitable for large amounts of data. In the second experiment, the dimensions d of the data points increased with the number of samples fixed at m = 4k (Fig. 5b). In this case as well, ADERH demonstrates high scalability, performing comparably to other state-of-the-art approaches.
m
O Ablation study: different settings of ADERH
In this ablation study, we systematically compare the proposed method ADERH under three configu- rations. The first configuration, called ADERH [Only Pitch], uses only the distance-based ratio Pitch to quantify how close a point lies to the center of a hypersphere but omits the normalized density term NDensity. The second configuration, referred as ADERH [Full r, #1 Hypersphere], generates actly one hypersphere per pair (I. y) with radius dist(r, (r. y) rather than splitting it into two half-radius hyperspheres. The third configuration the default ADERH method described in the main text, which creates two smaller hyperspheres of radius 3 dist((x y) for each pair and incorporates both Pitch and NDensity. Table Pabble/comparee the AUC-ROC scores for all three settings. In most datasets, ADERH [Full r, #1 Hypersphere] yields the poorest performance because a single large-radius hypersphere often encompasses anomalies as well as normal points, obscuring their distinctions. By contrast, splitting a pairwise distance into two half-radius hyperspheres reduces the risk of covering outliers and lowers the overall variance hypersphere sizes, thereby improving separability. The omission of NDensity in ADERH [Only Pitch] also impairs performance, especially when anomalies themselves become hypersphere centers. Without weightigg sparse (anomalous) hyperspheres, anomaly scores can be inflated or misassigned. In contrast, the full ADERH method yields, on average, the highest AUC-ROC values, indicating that combining a ratio-based distance measure Pitch with density-aware weighting NDensity and forming two compact hyperspheres for each pair of data points is crucial for robust outlier isolation. Overall, these results confirm that both halving the radii by incorporating NDensity and Pitch are essential design choices in ADERH.
28

---

Pundigit:: Plach
Pandigit::: 11 11-Meeralty)
Pundigttc Pitch (1-RDesity)
Pendigits: (1 (L-MoersityPhch
demiity
dansity
denatty
anomaly score
anomaly score
unomaly score
unimall score
Vosels PPtich
Voueli: (L-Monnitt))
Vownls PRcck [1-4Deschy)
Wasile (1-40wschhyyPPPc
demity
deruity
demitty
anomaly score
anomaly score
anomaly score
anomaly score
Figure 6: Score distributions for normals anomalies. Panels show Pitch, 1- NDensity, and their additive vs. multiplicative combinations (all scores in [0, 1], identical axes within each dataset). Multiplicative fusion produces the lowest normal-anomia overlap and the most pronounced anomaly separation, aligning with our theoretical motivation and corroborating the aggregate ablation in Appendix Q-
0.1 Visual evidence for Pitch, NDensity, and multiplicative fusion
To make the roles of Pitch (boundary proximity) and NDensity (local sparsity) tangible, we visualize score distributions for normals vs. anomalies two representative datasets. Each row in Figure 6 comprises four panels: (i) Pitch, (ii) NDensity, (iii) the additive combination (1 NDensity)
Pitch, and (iv) the multiplicative combination (1 NDensity) Pitch.
Within each dataset, scores are scaled to [0, 1] and panels share identical axes to enable direct comparison. As expected, Pitch alone emphasizes Soundary-adjacent instances but can elevate scores in dense regions; 1 NDensity highlights sparse regions yet may pick up normal tails. The multiplicative fusion yields the smallest overlap between normal and anomalous distributions and the clearest right-shift of anomalies, indicating that high anomaly scores arise primarily when both boundary proximity and sparsity coincide.
P Ensembling improves anomaly detection over any single subset
Table compares the proposed ensemble ADERH score to the best single subser variant across a diverse set of 19 datasets spanning tabular and visual AD benchmarks. All results follow our standard reporting protocol: we report means across repeated runs and assess across-dataset differences using a paired Wilcoxon signed-rank test with Holm correction at a-0.55.
Summary of results. The ensemble outperforms the best single subset on all datasets (19/19 wins). Averaged over datasets, the overall advantage is statistically significant under the paired Wilcoxon test with Holm correction (a=0.05). These results substantiate our ensembling: averaging scores across randomly constructed subsets mitigates idiosyncratic failure modes of any single subset and stabilizes decision boundaries across data regimes. Empirically, we observe consistent rightward shifts of anomaly-score distributions and tighter normal-score concentrations for the ensemble relative to the best single subset, aligning with our theoretical analysis on variance control.
motivation for
29

---

Table 9: This table presents the AUC-ROC results of different configuration of ADERH.
Dataset
ADERH
ADERH [Only Pitch]
ADERH [Full r, # HHypersphere ]
Optdigits
0.775 (1)
0.671 (3)
0.775 (1)
Wbe
1,000 (1)
1,000 (1)
0.970 (3)
Lymphography
1,000 (1)
0.996 (3)
1.000 (1)
Celeba
0.732 (1)
0.709 (2)
0.691 (3)
Skin
0.788 (1)
0.781 (2)
0.759 (3)
Pendigits
0.962 (1)
0.960 (2)
0.959 (3)
Wdbe
0.981 (1)
0.981 (1)
0.952 (3)
Toothbbbrus
0.901 (1)
0.843 (3)
0.871 (2)
Wpbc
0.554 (1)
0.522 (3)
0.541 (2)
AD-Leather
0.991 (1)
0.980 (3)
0.985 (2)
Satimage-2
0.998 (1)
0.998 (1)
0.997 (3)
Backdoor
0.889 (2)
0.898 (1)
0.826 (3)
MNIST-C-Stripe
0.986 (1)
0.984 (2)
0.976 (3)
Shuttle
0.987 (1)
0.987 (1)
0.979 (3)
Waveform
0.768 (1)
0.752 (2)
0.701 (3)
Cardio
0.938 (1)
0.917 (3)
0.918 (2)
AD-Bottle
0.964 (2)
0.952 (3)
0.969 (1)
Census
0.628 (2)
0.637 (1)
0.623 (3)
Wine
0.839 (1)
0.659 (3)
0.822 (2)
Musk
1.000 (1)
1.000 (1)
1.000 (1)
AVG Rank
1.16
2.11
2.32
p-value
NA
0.00585620 (+)
0.00185912 (+)
Grid search experiment for isolation and non-isolation methods
In addition to the experiments reported in Section where we used default hyperparameters (see Appendix HD -w conducted a comprehensive hyperparameter grid search for the following isolation- based methods:
ADERH (proposed method): Varying both the ensemble size Nesti (100, 300) and
the random-subset size w E {8, 18, 24).
INNE Bandaragoda et al. 2014]: Varying the number of estimators Nesti E {100, 200, 300} and maximum sub-sample size
{8, 18, 24).
2008 Varying nesti Nesti E {100, 200, 300} and {128, 256, 300} max samples IForest et al. per tree.
PIDForest Gopalan et al. 2019]] Varying Nesti E {100, 200,300) and {128, 256, 300) samples per tree.
2019] Varying Resti E (100, 200,300) and {128, 256,300) 300} samples per EIF Hariri et al. tree.
LOF Breunig et al. 2000 Varying Naeighhor E (5, 10, 20, 30, 17,40,500 50).
LODA Pevný 2016: Varying n r_raddmenuusss E {50, 100, 200} and n_ m_bins E {5, 10, 25)
DeepSVDD Ruff et al. 20018: : Varying batchsize E (50, 100, 200). 12 reguulaar
{5, 10, 25} and dropoutrate E (0.2,0.4).
RDP Wang et al.
2019b]: Varying batchsize E {32, 64) and prt_stepp E {5, 10, 20, 30).
SLAD Xu et al.
2023b: Varying n_ensemble E [10, 20, 50} and subspace_pool secpppacceppoo_iiiee size e
{25, 50, 100).
As in Appendix K protocols
each hyperparameter configuration uses the same data splits and evaluation
30

---

Table 10: Ensemble vs. best single subset (AUC-ROC).
The ensemble improves performance on
every dataset.
Dataset
Ensemble ADERH
Best Single Subset
Optdigits
0.775
0.597
Whe
1.000
0.949
Lymphography
1.000
0.966
Celeba
0.732
0.631
Skin
0.788
0.577
Pendigits
0.962
0.814
Wdbe
0.981
0.915
AD-Toothbrush
0.901
0.802
Wpbc
0.554
0.495
AD-Leather
0.991
0.900
Satimage-2
0.998
0.974
Backdoor
0.889
0.804
MNIST-C-Stripe
0.986
0.917
Waveform
0.768
0.629
Cardio
0.938
0.820
AD-Bottle
0.964
0.881
Wine
0.839
0.697
Musk
1.000
0.855
Table 11: This table presents the optimal AUC-ROC results achieved under various parameter settings for ADERH, INNE, Ioorest, PIDForest, EIF, LOF, LODA, DeepSVDD, RDP, and SLADD.
DeepSVDD
Opedigits
0,777 (2)
0.849 (1)
0.744 (4)
0.500 (10)
0.737 (5)
0.571 (8)
0.776 (3)
0.670 (6)
0,502 (9)
0.603 (?)
Whe
1,000
0.913
1,000
0.994
1,000
0.997
1,000
0.911 (8)
0.958
0.778
hymphagrphy
0.689 (5)
(100(())
(384
(10)
D397 (9)
0388
(8)
Coleba
0.747 (2)
0.698 (4)
0.86 (0)
0.221 (3)
0.475
0.869 (7)
0.644 (8)
0.586 (9)
0.787 (1)
0333 (7
03673
0.721
Pendigis
0396 (1)
0355 (2)
0.94016)
(3954(23
0.363 (10)
0344764 (4)
0.599 (9)
0305 (8)
0.941 (5)
Wilhe
0,977
AD- Loothhrush
0.908 (3)
(4)1
(7)
0.500 (10)
(.
0000 (6)
0.266 (3)
0.299 (2)
0.77 (7)
0.939 (I)
Wpbe
0.551
0.315
0,493 (10)
0.320
(.512
0.53
0.34
0.620 (1)
0.520165
0.523 (5)
AD- Leather
0.993 (1)
0307 (9)
0.986 (3)
0.500
0.986 (3)
0385 (7)
(8)
0981 (5)
0979 (6)
0.988 (2)
Satimage-2
0.998
0.07 (2)
0.933 (4)
0,883
0.998
0X228
0.911
0.955 (10)
0.788 (7)
0.933 (8)
Backdoor
0.895 (2)
(8)
(,500
(0)
0,788
0.807
(4)
0.906 (1)
MINIS-C--urp
0.986 (1)
0365 (6)
0.97 (3)
0,500 (9)
0.978 (3)
0.476
0.69 (4)
0.742
0.900 (7)
0.968 (5)
(179
Wavelorm
0.115 (1)
0,742 (2)
(5719
0.616 (10)
(3734(3)
0X715 (6)
0.701 (7)
06619 (9)
0.661 (8)
0.722 (4)
Candio
0918
0.872
0.923
0.779
0.898
AL Bottle
0.966 (2)
0.936 (9)
0.939 (7)
0.500 (10)
0.951 (5)
03000 (4)
(.95((5)
0339 (8)
0.977 (1)
0.966 (2)
Census
0.638
0.178 (10)
0.809
0.81613)
0.638 (1)
0.335
0.329 (9)
0.555
0.609 (4)
0.587 (6)
0.753(9)
0.756
0.777 (2)
(5)
0,835 (4)
Musk
1,00 (1)
L000
L800
L100 (1)
1,000 (1)
0.430110)
0.986 (7)
0.783 18)
0.706 (9)
1,000 (1)
AVG Rank
1,84
5.68
4.63
7.26
7,00
p-value
NA
0wWKeTH 64
Results and discussion. Tables |1 show that ADERH consistently outperforms the other methods under their best-tuned configurations, achieving an average rank of 1.84 in AUC-ROC. Comparing these optimally tuned results to the cefaullt-parmeette results (Table shows that ADERH's per- formance advantage remains robust: even when the other isolation- methods (IForest, EIF, PIDForest, INNE) and non-isolation methods (LOF, LODA, DeepSVDD, SLAD) are fully tuned, they generally do not match ADERH's detection accuracy.
The key to ADERH's strong performance lies in its novel design:
Random pairing of points in each subset,
Halving the pairwise distance to form two compact hyperspheres (rather than one large one),
and combined distance- (Pitch) and density-based (NDensity) scoring mechanism.
31

---

Table 12: AUC-PR performance of Multiplicative ((1 NDensity) x Pitch) vs. Additive ((1
NDensity) + Pitch)
Dataset
Multiplicative
Additive
Optdigits
0.061 (2) 0.094 (1)
Wbc
1.000 (1)
0.080 (2)
Lymphography
1.000 (1)
0.144 (2)
Celeba
0.060 (1)
0.027 (2)
Skin
0.345 (2)
0.346 (1)
Pendigits
0.309 (1)
0.140 (2)
Wdbe
0.614 (1)
0.168 (2)
AD-Toothbrush
0.840 (1)
0.785 (2)
Wpbc
0.261 (2)
0.281 (1)
AD-Leather
0.975 (1)
0.885 (2)
Satimage-2
0.957 (1)
0.124 (2)
Backdoor
0.222 (1)
0.131 (2)
MNIST-C-Stripe
0.699 (1)
0.104 (2)
Waveform
0.144 (2)
0.235 (1)
Cardio
0.588 (1)
0.366 (2)
AD-Bottle
0.940 (1)
0.841 (2)
Census
0.075 (2)
0.094 (1)
Wine
0.262 (1)
0.226 (2)
Musk
1.000 (1)
0.996 (2)
AVG Rank
1.26
1.74
This approach reduces hypersphere overlap with anomalies, preserves coverage of normal clusters, and robustly distinguishes boundary anomalies. The results in Tables [I further confirm that even with grid-searched hyperparameters, the other isolation-based and non-isolation--asee methods do not replicate these advantages.
R
Ablation study: multiplicative vs. additive fusion
ADERH's anomaly scoring function (Definition) 3.9
incorporates core signals: (1) Pitch((r, H). ratio-based distance metric that increases for boundary points, and (2) NDensity which measures how densely populated the hypersphere Multiplying these signals as
(1 NDensity(H)) Pitch(a, H)
ensures that high final score occurs only when both the boundary cue (Pitch & 1) and the sparsity cue (1 NDensity z 1) are simultaneously strong. In contrast, an additive combination ((1 NDensity) + Pitch) may inflate scores when only one signal is large (e.g., if Pitch As but NDensity Rs 1 in a dense, likely normal region). By multiplying. contradictions are naturally suppressed, and each factor remains dimensionless in [0, 1), their product also comfortably stays in the interval [0, 1] without extra calibration.
Empirical findings. To validate this design choice, we performed an ablation study comparing the above muliiplicative variant with its additive counterpart, under the same experimental pipeline. Table 12 demonstrates that across most datasets, the multiplicative scheme ((1 NDensity) Pitch) achieves higher or comparable detection performance. While the additive combination occasionally shows slight improvements in few datasets, the average rank metric (1.26 vs. 1.74) clearly favors the multiplicative approach overall. These findings confirm that blending boundary and density cues mulriplicatively is better at suppressing anomalies dense regions while still highlighting borderline outliers. Therefore, we adopt the multiplicative form as the default scoring mechanism in our anomaly detection framework.
32

---

Limitations
While ADERH mitigates distance concentration through local hypersphere pairing, its effectiveness still depends on the stability of distance structures in figh-dimensional spaces. When intrinsic dimensionality is large, local neighborhoods become less informative, reducing the discriminative power of geometric cues. This limitation highlights the need for feature transformations that preserve local contrast and enhance separability complex data manifolds.
T
Future work
Since the distribution of anomalies plays an important role in anomaly detection, it would be interesting to explore how deep learning could transform the feature space of the data so that anomalies pushed even further away from normal data points in the first step Pang al. (202T). Subsequently, ADERH could leverage the transformed space to operate more effectively, potentially improving the accuracy of anomaly detection. Additionally, this approach could address challenges associated with high-dimensional data by mitigating the effects of the curse of dimensionality and improving the representation of underlying patterns in complex datasets.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly outline the main contributions (the introduction of an isolation- anomaly detection method using multiple compact hyper- spheres) and key theoretical/empprrcal claims (strong performance, linear-time scalability). These match both the theoretical arguments and the experimental evidence presented in the paper. The assumptions (e.g., d-separation) and scope (e.g., experiments on tabular/image- derived data) are also consistent with the final results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results It is fine to include aspirational goals as motivation long is clear that these goals are not attainable by the paper.
be expected to generalize other settings.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper devotes "Limitations" section to discussing potential constraints, such as possible iettanc-conncentratonn issues in very high dimensions. The text also addresses how these factors could affect performance and scalability.
Guidelines:
The answer NA means that the paper has no limitation, while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the
implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not to penalize honesty concerning limitations.
the paper. The authors should use their best
34

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper states all assumptions (e.g., d-separation) up front, and each main theoretical claim-such as the variance bound on the ensemble score, is accompanied by complete formal proofs in the appendix. The authors number and reference all lemmas and theorems consistently, offering intuitive sketches in the main text and full proofs in the supplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The paper provides all necessary details for reproducing its main experiments. Section Kicovers data preprocessing, stratified splits, evaluation metrics (AUC-ROC AUC- PR), random seeds, and parameter settings for ADERH and all baselines. The appendix further clarifies hyperparameter choices, data statistics, and runtime environments, enabling full replication of results.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution
specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
35

---

reproducible, they (c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All real-world datasets (e.g.. from AdBench Han et al. [2022]) are pub- licly available. public repository (attps://githhb, com/Walid10011 ADDRRH, git) includes the implementation, usage instructions, and scripts for ADERH and baselines. These resources comply with the conference's s reproducibility and code submission guide- lines.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips. //nips.cc/puliee wtt.cccppppllccc httppplccccidee//eeeeeeeeeeeeeee
sww.sssiicciiiiici for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
The paper and its appendix detail all experimental settings, including data splits (70-30 stratified), normalization, ADERH parameters, baseline hyperparameters, hardware, and random seeds. This ensures transparency and enables accurate replication.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
36

---

7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
The paper provides statistical testing via paired Wilcoxon signed-rank tests comparing the proposed method against baselines. The main tables I g report AUC-ROC and AUC-PR results, including p-values derived from these tests, highlighting whether the 0.05.
Justification:
improvements are statistically significant
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In appendix K the paper states the hardware environment used (an Intel Core i7, 32 GB RAM), well approximate runtime behaviors for the main experiments. The text and appendix discuss the scalability with data size and dimensionality. showing linear-time trends and providing typical run times the described hardware.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: ///p:r:///////ee// httppppc.cppppccttttcccccceeeee.
Answer: [Yes]
37

---

Justification: This research adheres to standard practices in anomaly detection, utilizing only publicly available datasets that do not contain personal or sensitive information. No human subjects were involved. The authors have reviewed the NeurIPS Code of Ethics and confirm that the work raises no concerns related to fairness, privacy, or data use. The methodology focuses exclusively on technical innovation, and all data sources are properly licensed and ethically appropriate. As such, the study complies with NeurIPS ethical guidelines.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is primarily theoretical in nature and has potential applications across various domains. As such, we do not anticipate it having a direct positive or negative impact on socially relevant issues.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [No]
The paper does not address safeguards for model or dataset release. This is due its focus on foundational algorithmic advances models or sensitive data. As the proposed method does not present inherent risks of misuse, specific precautions were not discussed.
Justification:
in anomaly detection, rather than high-risk
Guidelines:
The answer NA means that the paper poses such risks.
38

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
The paper cites all datasets used for testing, with proper attribution to the original creators. The authors also mention the use of pre-existing libraries and models, giving credit to the authors of the original codebases and providing clear citations. All licenses and terms of use for these resources are explicitly mentioned, and the authors adhere the copyright and usage conditions.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- ce-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not introduce new assets such as datasets, or models. It primarily focuses improving existing techniques in anomaly detection and validating them using publicly available datasets. Therefore, no new assets are provided or documented in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
39

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve any crowdsourcing or human subjects research. The work is computational and focuses the development and evaluation of anomaly detection algorithms using existing datasets, with no participant involvement.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
This work does not involve human subjects or crowdsourcing, and therefore does not require IRB approval. All experiments are conducted solely on publicly available datasets, with no human participation or personally identifiable information involved.
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of L.MMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: This research does not involve LLMs as any important, original, or non- standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
40


Reviews:
[{"review_id": "P6NVJsB2Vd", "reviewer": "Reviewer_TZiB", "summary": "This paper presents an anomaly detection method built on the concept of isolation. The approach constructs multiple hyperspheres using randomly selected pairs of samples and assigns anomaly scores based on each data point's position relative to the nearest hypersphere center and the hypersphere’s density characteristics.", "questions": "Please refer to Weaknesses.", "limitations": "Please refer to Weaknesses.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper is well organized.\n\n2. The theoretical analysis is comprehensive.\n\n**Weaknesses:**\n\n1. The experimental setup section lacks proper citations for the baseline methods. I recommend that the authors include full references for all baselines to ensure clarity and proper attribution.\n\n2. The paper lacks comparisons with recent state-of-the-art baselines. It only evaluates against methods published up to 2024, despite several relevant works from other conference, like ICLR 2025 and AAAI 2025, already being publicly available.\n\n3. Statistical results, such as mean and standard deviation over multiple runs, are not reported.\n\n4. There are no visualizations or additional evidence to support the authors’ claims, only experimental results are provided. For example:\n\n(1) Although Pitch is said to emphasize boundary anomalies and NDensity down-weights hyperspheres in sparse regions, the paper provides no visual comparisons of scores for normal vs. anomalous points to show these components work as intended.\n\n(2) A key claim is that random pairing naturally results in hyperspheres of varying radii (multi-scale coverage), but there is no histogram, distribution plot, or illustrative example to support this.\n\n(3) The use of a multiplicative combination of Pitch and NDensity is motivated in theory, but no score distribution plots, t-SNE projections, or spatial embeddings are shown to compare additive vs. multiplicative strategies.\n\n(4) The ensemble scoring mechanism is said to reduce variance and improve robustness, but this is supported only by theoretical bounds. There are no visualizations or comparisons of score distributions across subsets or before/after ensemble averaging.", "was_revised": true, "final_justification": "Most of my concerns have been well addressed. The only remaining uncertainty is that, according to the rebuttal policy, the authors promised to supplement the visualizations in the final version of the paper. I believe that including these visualizations would significantly enhance the quality of the manuscript.", "rebuttal": "We thank the reviewer for the valuable feedback.\n\n\n## Q1 - Proper Citations of Baseline Methods\n\nWe thank the reviewer for this indication. The section 'Experimental Setup' will be expanded to include full bibliographic details for every comparator.\n\n## Q2 - Recent state-of-the-art Baselines\n\nFollowing the reviewers’ request, we will incorporate UniCAD [1], one of the most recent publicly available anomaly detection methods (ICML 2025), into our comparison experiments. Since this experiment is extensive, we consider only a representative subset of datasets. Nevertheless, this selection is sufficient to capture and reflect the key trends and main findings. The results of those experiments, using the implementation and hyperparameters as referenced in the original paper, are shown in the table below. We see that ADERH achieves superior results in the majority of cases.  \nThis improvement is statistically significant under a paired Wilcoxon signed-rank test with Bonferroni–Holm correction at α = 0.05 (p-value < 0.05).  \nWe will release our updated codebase after the review process concludes, in accordance with the NeurIPS policy, which prohibits updates during the review phase.\n\n**Table: Extended AUC-ROC performance comparison between ADERH and UniCAD [1] across additional datasets.**\n\n| Dataset      | ADERH        | UniCAD [1]    |\n|--------------|--------------|---------------|\n| Optdigits    | **0.775 (1)** | _0.507 (2)_    |\n| Wbc          | **1.000 (1)** | _0.994 (2)_    |\n| Lymphography | **1.000 (1)** | _0.988 (2)_    |\n| Celeba       | _0.732 (2)_   | **0.810 (1)**  |\n| Skin         | **0.788 (1)** | _0.721 (2)_    |\n| Pendigits    | **0.962 (1)** | _0.944 (2)_    |\n| Wdbc         | **0.981 (1)** | _0.962 (2)_    |\n| Toothbrush   | **0.901 (1)** | _0.823 (2)_    |\n| Wpbc         | **0.554 (1)** | _0.525 (2)_    |\n| Leather      | **0.991 (1)** | _0.980 (2)_    |\n| Satimage-2   | **0.998 (1)** | **0.998 (1)**  |\n| Backdoor     | _0.889 (2)_   | **0.908 (1)**  |\n| Stripe       | **0.986 (1)** | _0.943 (2)_    |\n| Shuttle      | _0.987 (2)_   | **0.988 (1)**  |\n| Waveform     | **0.768 (1)** | _0.709 (2)_    |\n| Cardio       | **0.938 (1)** | _0.912 (2)_    |\n| Bottle       | **0.964 (1)** | _0.954 (2)_    |\n| Musk         | **1.000 (1)** | **1.000 (1)**  |\n\n---\n\n**[1]** Fang, Zeyu, et al. *\"Towards a Unified Framework of Clustering-based Anomaly Detection.\"* Forty-second International Conference on Machine Learning (ICML 2025).\n\n\n## Q3 - Reporting of Statistical Results\n\nIn our submission, Table 1 reports for each dataset the *mean* result of 15 runs for non-deterministic algorithms like ADERH (three splits with five seeds each) and three runs for deterministic algorithms. Also, the other Tables report the mean of all tested configurations. In the final version, we will mention this directly in the corresponding captions of the tables. We agree that including *standard deviations* (std) provides additional insight into the stability and robustness of each method. We will add all std values in the revised manuscript and believe these additions address the reviewer’s concern and strengthen the empirical rigor of our evaluation. For the main competing baselines — **ADERH**, **INNE**, and **IForest** — we report the average standard deviation across all datasets below:\n\n- **ADERH** — mean ROC-AUC std ≈ **0.0133**, mean AP std ≈ **0.0317**\n- **INNE** — mean ROC-AUC std ≈ **0.0241**, mean AP std ≈ **0.0515**\n- **IForest** — mean ROC-AUC std ≈ **0.0235**, mean AP std ≈ **0.0417**\n\nThese results show that **ADERH exhibits the lowest standard deviation**, suggesting it is the most stable and consistent method across various datasets.\n\n## Q4 - Missing Visualizations\n\n### Effect of Pitch and NDensity\n\nAppendix O presents a numerical ablation study (Table 7), where various design choices are individually analyzed, highlighting the overall advantage of the final ADERH configuration. This study demonstrates that each component contributes significantly to ADERH’s strong performance. To further support these findings, we will include additional figures in the revised version, which illustrate the score distributions before and after combining Pitch and NDensity.\n\n### Varying Radii through Random Pairing\n\nIndeed, a central claim of our approach is that random pairing of points naturally produces hyperspheres of varying radii, enabling adaptive coverage across multiple scales. To empirically substantiate this claim, we analyzed the hypersphere radii generated by ADERH using real-world data. This analysis appears in Appendix C, where Figure 3 presents histograms showing the distribution of hypersphere radii across six benchmark datasets. The histograms in Figure 3 reveal diverse and data-dependent radius distributions. In some cases (e.g., Satimage-2, Waveform), the radii are concentrated around smaller values, indicating large dense neighborhoods. In other cases (e.g., Skin, Musk), the distributions are more spread out or even multi-modal, reflecting the presence of both compact and sparse regions. These results offer direct empirical confirmation of our theoretical analysis in Section 3 and Appendix B, which shows that random pairing leads to both intra- and inter-cluster combinations. The net effect is that hyperspheres span a wide range of radii, without the need for manual scale selection.\n\n### Additive vs. Multiplicative Combination of Pitch and NDensity\n\nIn our submission, we address this question empirically in Appendix Q through a comprehensive ablation study. Here, we compare the performance of the multiplicative combination $\\((1 - \\text{NDensity}) \\cdot \\text{Pitch}\\)$ with the additive variant $\\((1 - \\text{NDensity}) + \\text{Pitch}\\)$ using 21 datasets and AUC-PR as the primary metric.\n\nThe results in Table 9 show that the multiplicative strategy consistently achieves better or comparable precision-recall performance, with a significantly lower average rank (1.29 versus 1.71). This supports our theoretical motivation: the multiplicative form yields high anomaly scores only when *both* boundary proximity and low local density are simultaneously present—i.e., anomalies that are both spatially isolated and lie near hypersphere boundaries. In contrast, the additive form can assign high scores when only one of these two conditions is met, leading to inflated anomaly scores in some dense regions. Nonetheless, we agree that complementary visualizations would make this distinction more tangible and interpretable. We will add visual examples showcasing the strengths of a multiplicative combination to Appendix Q in the revised version.\n\n### Ensemble Scoring Mechanism\n\nWe fully agree that demonstrating the robustness and variance reduction of the ensemble beyond theoretical bounds enhances the transparency and interpretability of our method. To address this, we will include a direct empirical comparison between the ensemble score and the top-performing single subset (Subset #1) across a diverse collection of datasets in the manuscript. The ensemble consistently yields higher AUC-ROC values than any individual subset, demonstrating its robustness and generalization benefits. The results confirm our theoretical claims and align with the intuition that averaging over multiple diverse scoring functions reduces sensitivity to idiosyncratic failure modes of individual subsets, thereby increasing robustness.\n\n\n\n**Suggestions**\n\nWe appreciate the helpful suggestions of the reviewer that have already led to additional numerical results. In addition, new figures will be added to the final manuscript to illustrate specific components of our methodology."}, {"review_id": "UDYOGwDbxL", "reviewer": "Reviewer_gbWb", "summary": "It is proposed to isolate anomalies using an ensemble of pairs of hyperspheres, randomly generated from a random subset of the dataset. The radius of these pairs of hyperspheres is half the distance between their centers. The spheres are then analyzed with respect to Pitch and (normalized) density to compute a score for this subset, which is then averaged over the ensemble. It is shown that, under the assumption that anomalies are far from cluster centers, this setup with assigns lower scores to anomalies with high probability, and this uncertainty decreases as the ensemble size increases. In experiments, it is shown that the proposed approach outperforms many existing methods on several popular benchmark datasets.", "questions": "- Please describe how/if assumption 3.1 is affected by the curse of dimensionality\n- As stated in line 184, how does ADERH capture heterogeneous distributions more effectively (...than what exactly)? Can you prove this statement? If not, I suggest removing it to enhance clarity.\n- Regarding equation (12), I am wondering how any data point can have $T(x,\\mathcal{S}_i)=\\emptyset$. Is it because $\\mathcal{S}_i\\subset X$ and the possibility that $x\\not\\in \\mathcal{S}_i$?\n\n\n\n**Improvement suggestions**\n\n- Line 32: It might be good to add Deep Isolation Forest to the list of related approaches\n- Line 34: Hawkins 1980 is not the best reference for this statement. You may want to use a different reference for rarity, e.g. Barnett and Lewis 1974, or Aggrawal 2017.\n- Line 41: This is a description of how Iforest works, not a weakness of Iforest.\n- Section 2 feels a bit too long. I would cut out some of the older approaches like LOF.\n- Line 130: The statement in brackets (\"...indicated by $0\\ll \\alpha$\") can be omitted, as well as (\"as evidenced by RARITY...\")\n- Assumption 3.1: $J$ is not defined. Also, please avoid vague language like *typical* in formal environments like assumptions, theorems etc.\n- Line 176: Radius variability was not described until this point, so this passage is confusing.\n- Theorem A.3 is strange. A lemma is not an assumption: A lemma is a statement that is true. The theorem does not really show that $\\alpha=\\frac{1}{2}$ is the best choice—it instead shows that two properties hold for this setting, but these properties do not imply optimality in any sense, especially not if the random pairing function is not used.\n- Figure 2 seems more confusing than helpful to me. I would suggest to remove it.\n- Lines 220-222: I think this argument is wrong. Each anomaly in $\\mathcal{S}_i$ will be the partner of exactly one point in $\\mathcal{S}_i$, and per the rarity argument this occurrence will only have a small effect on the entire ensemble.\n- Definition 3.7: I understand what you are trying to say, but symbol $X_\\mathcal{H}$ is only defined later in line 244.\n- Equation 9: Use $\\max$ instead of $max$, because the latter reads as $m\\cdot a \\cdot x$\n- Equation 10: The symbol $c_\\mathcal{H}$ is not defined.\n- Lemma 3.10: I understand where the proof is heading, but the notation needs to be improved. Please rephrase the lemma s.t. it is clear that $\\text{Ndensity}(\\mathcal{H}(z))$ converges to zero almost surely. Also, please don't use $\\ll $  here because the symbol is vague.\n- Lemma 3.13: I recommend to add the description \"informal\" in the main text and to restate the lemma more precisely in the appendix (avoiding $\\ll $ )", "limitations": "The description of ADERH's limitations is very brief—for a method consisting of several concepts (pitch, normalization, subsets, density, ...) there surely are additional limitations/drawbacks that should be mentioned to give an honest and complete picture of the proposed method", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The proposed method is original and makes sense. It is good that theoretical evidence is provided for the method, which considerably raises the technical quality of the manuscript—most new anomaly detection methods either don't provide theoretical evidence, or don't provide good experimental results, but this paper provides both. I believe the idea of using pairs of hyperspheres is somewhat interesting to the community, but not largely so. The descriptions are mostly clear, but can be improved (see suggestions).\n\nHowever, the paper is not without flaws. I have the impression that the authors somewhat oversell their method and attribute traits to it without providing any proof. For example, it is claimed that ADERH effectively captures heterogeneous distributions, but no proof is provided. The description of ADERH's limitations is very brief—for a method consisting of several concepts (pitch, normalization, subsets, density, ...) there surely are additional limitations/drawbacks that should be mentioned to give an honest and complete picture of the proposed method. Also, some of the formal statements are too imprecise, but this does not seem to affect the overall correctness of the approach.", "was_revised": true, "final_justification": "I think this paper is good because it proposes a new anomaly detection method and supports this method with sufficient theory. While the proofs are somewhat sloppy, this does not affect their overall correctness.\n\nMy remaining concern is that this method will not have a too large impact if published, but this is not a major concern. Hence, I have decided to keep my rating at weak accept.", "rebuttal": "We thank the reviewer for the helpful feedback.\n\n\n\n## Q1 - Curse of Dimensionality for Assumption 3.1\n\nAssumption 3.1 relies on the notion that normal points lie within radius $\\sigma$ of some local cluster center $\\mu_j$, while anomalies fall outside a margin $\\sigma + \\delta$. In low-dimensional settings, such a margin $\\delta$ offers a clean geometric separation between dense inlier regions and sparser outlier zones. However, this separation becomes fragile in high-dimensional regimes due to the well-known curse of dimensionality.\n\nSpecifically, for data vectors $x \\in \\mathbb{R}^d$ with independent, isotropic components, the Euclidean norm satisfies $\\|x\\|_2 \\approx \\sqrt{d}$ in expectation, with relatively small variance. As a consequence, both inter-point distances and intra-cluster radii naturally scale with $\\sqrt{d}$. Thus, in unscaled coordinates, the fixed gap $\\delta$ postulated in Assumption 3.1 effectively vanishes unless it, too, grows with $\\sqrt{d}$.\n\nNonetheless, the conceptual intent of Assumption 3.1 survives under a reinterpretation. Rather than demanding a fixed absolute margin $\\delta$, it is more appropriate to require a *relative* margin $\\tau = \\delta / \\sigma$—a dimensionless ratio reflecting how far anomalies lie from their nearest clusters, scaled by the local intra-cluster spread. This formulation is standard in robust statistics and aligns with Mahalanobis-distance-based interpretations, where each feature is normalized to unit variance. In this view, anomalies are required to lie outside a radius $(1 + \\tau)\\cdot \\sigma$, a condition that remains meaningful even in high-dimensional spaces.\n\nThe ADERH algorithm implicitly respects this scaling. Each hypersphere is defined by a randomly chosen pair of points, with radius $R = \\frac{1}{2}\\|x - y\\|$. Since distances themselves scale with $\\sqrt{d}$, the hypersphere radii adjust naturally to the ambient geometry. The *Pitch* term—computed as $\\mathrm{dist}(x, c)/R$—is invariant under uniform scaling of the space, and the *NDensity* term depends purely on counts rather than metric magnitudes. Therefore, the anomaly score produced by ADERH is unaffected by global distance inflation. Moreover, ensemble averaging across $n$ such hyperspheres reduces the variance of these scores by a factor of $1/(4n)$, preserving their discriminative power even when some hyperspheres are degraded by high-dimensional effects.\n\nIn conclusion, although the curse of dimensionality erodes the efficacy of fixed Euclidean margins, Assumption 3.1 remains valid when interpreted in relative terms. ADERH maintains its robustness under this reformulation, particularly when features are normalized such that $\\sigma \\approx 1$, allowing the parameters $\\delta$ and $\\tau$ to be treated interchangeably. Empirically, ADERH shows strong performance on high-dimensional datasets like Leather, Toothbrush, or Census.\n\n\nFor a quick sanity check, we generated a high-dimensional dataset with 100,000 features, consisting of clustered normal points and injected anomalies. On this data, **ADERH** achieves a perfect AUC-ROC of $1.00$.\n\nThe code for this is shown below:\n\n```python\n# High-dimensional anomaly dataset generation\nfrom sklearn.datasets import make_blobs\nimport numpy as np\n\nn_samples = 500\nn_features = 100000\nn_clusters = 3\nanomaly_fraction = 0.05\nn_anomalies = int(n_samples * anomaly_fraction)\nn_normals = n_samples - n_anomalies\n\n# Generate normal data (3 blobs)\nX_normal, _ = make_blobs(n_samples=n_normals,\n                         n_features=n_features,\n                         centers=n_clusters,\n                         cluster_std=5.0,\n                         random_state=42)\n\nmin_val = X_normal.min()\nmax_val = X_normal.max()\nX_anomaly = np.random.uniform(min_val, max_val, size=(n_anomalies, n_features))\n\n# Combine data\nX = np.vstack([X_normal, X_anomaly])\n\n# Labels: 0 = normal, 1 = anomaly\nY = np.hstack([np.zeros(n_normals), np.ones(n_anomalies)])\n```\n\n\n**Practical remark**. If the adverse effects of high dimensionality remain pronounced in a given dataset, one can first apply a dimension-aware feature transform—such as UMAP. These transforms mitigate distance concentration while approximately conserving relative cluster geometry. After this preprocessing step, ADERH is run in the transformed space: both its Pitch and (normalized) NDensity terms still operate on relative scales, so the theoretical guarantees and the $\\tau$-margin interpretation continue to hold.\n\n\n\n\n\n## Q2 - Capturing Heterogeneous Distributions\n\nBy *capturing heterogeneous distributions*, we mean that our approach is able to identify anomalies situated near structures with different characteristics, such as varying densities.\n\nWe can demonstrate the beneficial properties of **ADERH** empirically, for example. While we are not permitted to add new results to the anonymous GitHub repository during the rebuttal, we conducted additional evaluations on the *two moons* dataset from `sklearn`, modifying it to exhibit varying densities and injecting both local and global outliers.\n\nNormal points lie along a curved, non-convex manifold, intentionally violating the single-cluster (or single-blob) assumption underpinning classical boundary-based models such as the one-class SVM. This makes the dataset particularly well-suited for evaluating algorithms that must infer non-linear decision boundaries in complex, topologically non-trivial structures.\n\nWe evaluated **ADERH**, **INNE**, **IForest**, **DIF**, **LODA**, and **ECOD** on this dataset. On this challenging benchmark, **ADERH** achieves the best overall ranking. Competing methods, including **INNE** and **Isolation Forest**, rank lower, while even deep learning-based approaches such as **DIF** perform worse. These results highlight **ADERH**'s ability to model intricate data geometry and reject anomalies effectively.\n\n### Table: Performance on the `Two Moons` dataset with injected anomalies  \n**Ranked by ROC-AUC**\n\n| **Rank** | **Algorithm** | **ROC-AUC** |\n|---------:|---------------|-------------|\n| 1        | ADERH         | 0.940       |\n| 2        | DIF           | 0.925       |\n| 3        | IForest       | 0.895       |\n| 4        | INNE          | 0.878       |\n| 5        | OCSVM         | 0.858       |\n| 6        | ECOD          | 0.817       |\n| 7        | LODA          | 0.726       |\n\n\n\nThe code used to create the dataset is shown below:\n\n```python\n# Two Moons dataset with injected outliers\nfrom sklearn.datasets import make_moons\nimport numpy as np\n\nX, Y = make_moons(\n    n_samples=(1000, 300),\n    noise=0.05,\n    random_state=42\n)\n\noutliers = np.array([\n    [-0.5, -0.5],\n    [ 0.0,  0.7],\n    [-1.5,  0.8],\n    [ 1.5,  0.25],\n    [ 2.0,  1.0],\n    [ 1.0, -0.15],\n    [-1.0, -0.12]\n])\n\nX1 = np.vstack([X, outliers])\ny_full = np.hstack([\n    np.zeros(len(X)),\n    np.ones(len(outliers))\n])\n```\n\n## Q3 - Empty Set in Eq. 12\n\nYes, that is correct. Since the hyperspheres considered in Eq. 12 are created using a subset $S_i \\subset \\mathcal{D}$ and Eq. 12 is calculated for all points in the dataset $\\mathcal{D}$, there is no guarantee that all points $x \\in \\mathcal{D}$ will be covered by at least one hypersphere (this is in contrast to points $x \\in S_i$, which are guaranteed to be within at least one hypersphere). In practice, however, this situation does not occur very often, as the random pairing of points usually results in some hyperspheres with large radii and, therefore, almost complete coverage of the data space.\n\n## Improvement Suggestions and Limitations\n\nWe thank the reviewer for the many suggestions to improve our manuscript, and we incorporated those in the revised version:\n\n1. **Related work & refs.**\n   - **L32** – Added Deep iForest (DIF).\n   - **L34** – Replaced Hawkins with Barnett & Lewis 1974; Aggarwal 2017.\n\n2. **Text, notation, flow**\n   - **L41** – Split iForest description vs. weakness.  \n   - **§2** – Condensed; shortened LOF details.  \n   - **L130** – Dropped rarity parenthetical.  \n   - **Assump 3.1** – Defined $J$; removed “typical”.  \n   - **L176** – Added forward-ref to radius variability.  \n   - **Def 3.7** – Defined $X_{\\mathcal{H}}$ in Eq. 4, and we will make this clearer.  \n   - **Eq 9/10** – `\\max` fixed; $c_{\\mathcal{H}}$ typo should be $C(\\mathcal{H})$ as defined in L191.  \n   - **Fig 2** – We will improve this for clarity.\n\n3. **Theory & proofs**\n   - **A.3** – adjusted.  \n   - **Lemma 3.10** – Stated a.s. convergence; removed “$\\ll$”.  \n   - **L220–222** – Ensembling mitigates impact, but individual subsets remain vulnerable. We'll address this.  \n   - **Lemma 3.13** – adjusted.\n\nAlso, we will add more information regarding the limitations of ADERH."}, {"review_id": "D5fFJiJWkr", "reviewer": "Reviewer_MfCe", "summary": "The paper proposes a new isolation-based technique called ADERH by leveraging two key observations: (i) anomalies are comparatively rare, and (ii) they typically deviate stronger from general patterns than normal data points. ADERH  isolates anomalies using compact hyperspheres designed to minimize overlap with anomalies. The goal of ADERH is to create multiple hyperspheres of different radii in each subset Si, so that dense areas are captured by smaller hyperspheres, and sparser areas by larger ones.", "questions": "The norm in your distance metrics is l2 norm? What if your data does not lie on a manifold where Euclidean distance is not the metric space e.g. text data or other discrete data?\n\nWhat if your normal data does not cluster spherically but instead are shaped as curves e.g. half moons or donuts? A significant drawback of methods such as 1 class SVM is being unable to “draw” a smooth round boundary around the normal data.\n\nThese concepts of using multiple “blobs” (whether spherical or other shapes) to cover normal points and form densities is not new. How does your method compare to the ones listed below (which are not in the related work nor compared against)? These prior methods also use coverings to estimate densities where a point is anomalous if its score is large than normal points scores. And [2] does not reply on requiring the data to cluster / have density / be covered by a sphere as it creates these covering with K nearest neighbors giving it more freedom in the shape of the coverings. \n\n[1] C. Scott and R. Nowak, “Learning minimum volume sets,” Journal of Machine Learning Research, vol. 7, pp. 665–704, April 2006.\n\n[2] Hero, Alfred. \"Geometric entropy minimization (GEM) for anomaly detection and localization.\" Advances in neural information processing systems 19 (2006). \n\n[3] Gu, Xiaoyi, Leman Akoglu, and Alessandro Rinaldo. \"Statistical analysis of nearest neighbor methods for anomaly detection.\" Advances in Neural Information Processing Systems 32 (2019).\n\nA strong rebuttal of this last question would lead to a significant change in score as it would significantly improve the originality and significance of this paper.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n \nThe paper provides theoretically rigorous justification for why their method works. \n\nThey have good results shown in Table 1. \n\nWeaknesses\n \nThere is a lot of repetitive information in this paper. Some things like the Rarity, Deviation and using Pitch and NDensity to deal with real world data that doesn’t actually satisfy Rarity and Deviation, are repeated numerous times in the paper in slightly different ways. \n\nThe paper could be a lot more concise and a lot of the useful information in the appendix could be moved to the main paper. The paper spends almost 3 pages on the abstract, intro, contributions and related work where there is significant overlap in the information between the abstract and contributions, and between the intro and related work. It then spends another 2-3 pages on definitions, most of which are not significantly necessary for the main result in Theorem 3.15.\n\nSee questions, particularly the last question.", "was_revised": true, "final_justification": "The authors' response suitably answered my questions and compared against the methods that I mentioned. I also read the other reviews and rebuttals. I have updated my score accordingly as they have addressed the main novelty issue in my original review.", "rebuttal": "We thank the reviewer for the valuable feedback.\n\n## W1 - General Suggestions for Improvement\n\nWe thank the reviewer for the valuable suggestions for improvement and will reduce repetition—especially around concepts like Rarity and Deviation—by consolidating overlapping explanations. Introductory sections will be tightened to eliminate redundancy, and essential content from the Appendix will be integrated into the main text where it supports key results like Theorem 3.15.\n\n## Q1 - Choice of Norm\n\nDue to its convenience and common usage, the Euclidean ($\\ell_2$) distance was selected as the default norm in **ADERH**. However, all core steps rely only on the axioms of a metric, not on Euclidean geometry. Consequently, the algorithm and theory extend unchanged to any alternative metric. Complex data (e.g., images) is typically embedded into vector spaces with well-defined metrics. In our experiments, we used datasets such as Leather, Bottle, Toothbrush, and MNIST-Stripe, whose features were originally obtained using a ResNet18 feature extractor.\n\n## Q2 - Non-spherical Data Patterns\nUnlike OCSVM’s global boundary, ADERH uses local hyperspheres with Pitch and NDensity that may adapt to complex manifolds and avoid flagging anomalies as normals. On one synthetic two-moons dataset (with anomalies, density variation, and complex shape), ADERH achieves top results vs. multiple SOTA baselines.  Due to space constraints, we kindly refer the reviewer to our detailed response under Reviewer gbWb for a full discussion of this point.\n\n## Q3 - Differences to Studies Mentioned in the Review\n\nWe highlight key differences from ADERH to [1,2,3] in the revised Related Work and present new comparative experiments using the original evaluation protocol across multiple benchmark datasets.\n\n\n### MV‑ERM and MV‑SRM [1]\n\n**Main Ideas in MV‑ERM and MV‑SRM.**  \nThe framework described in [1] recasts minimum‑volume‑set estimation as an empirical‑risk‑minimisation task: MV‑ERM chooses, within a prescribed class of candidate regions, the set of smallest reference‑measure volume whose penalised empirical mass still reaches the target level $\\alpha$, which yields distribution‑free finite‑sample bounds and strong universal consistency; MV‑SRM embeds the same complexity penalty directly in the objective, so the optimiser simultaneously tunes structural complexity—e.g., histogram bandwidth or decision‑tree depth—to the data.\n\n**Difference to ADERH and MV‑ERM / MV‑SRM**  \n**ADERH** replaces the axis-aligned partitions of MV-ERM and MV-SRM with randomly centered, multi-scale hyperspheres, avoiding VC-dimension overhead and rigid geometry assumptions. Its anomaly score—based on boundary proximity and local sparsity—is continuous, variance-bounded by $1/(4n)$, and scales linearly with data size and dimension. This yields a parameter-light, geometry-adaptive alternative aligned with the minimum-volume principle, but free from explicit volume estimation.\n\n**[1]** C. Scott and R. Nowak, *“Learning minimum volume sets,”* *Journal of Machine Learning Research*, vol. 7, pp. 665–704, April 2006.\n\n---\n\n### GEM [2]\n\n**Main Ideas in Geometric Entropy Minimisation (GEM).**  \nGEM [2] casts anomaly detection as a minimal-wiring problem: it selects the $K = \\lfloor \\rho n \\rfloor$ points whose $k$-NN graph (or MST) has minimal total edge length, yielding the tightest subset covering mass $\\rho$ and converging to the distribution’s minimum-entropy set. At test time, a candidate is anomalous if inserting it increases total wiring more than any inlier, with the edge-length jump providing a calibrated score. GEM is scale-free and geometrically adaptive, but computationally heavy due to leave-one-out graph updates and sensitive to edge-length estimates.\n\n**Difference to ADERH and GEM**  \nGEM constructs global graphs and uses fixed neighborhoods, making it prone to dense-boundary false positives. **ADERH**, in contrast, avoids a global view and builds many twin hyperspheres from random point pairs and scores points via the product of *Pitch* (boundary ratio) and *NDensity* (inverse occupancy). Anomalies emerge only when both signals align, enabling robust separation under high dimensionality and heterogeneous cluster shapes, with no graph construction or tuning beyond $n$ and $\\omega$.\n\n**[2]** Hero, Alfred. *\"Geometric entropy minimization (GEM) for anomaly detection and localization.\"* *Advances in Neural Information Processing Systems* 19 (2006).\n\n---\n\n### DTM [3]\n\n**Main Ideas in Distance-to-a-Measure (DTM).**  \nIn DTM [3], a small probability window $m$ (or its discrete proxy $k = \\lceil m n \\rceil$) and a power parameter $q$ define, for every point $x$, the average radius $r_p(x)$ needed to enclose each mass level $p \\le m$, yielding the score:\n\n$$\nd_{P,m,q}(x) = \\left( \\frac{1}{m} \\int_0^m r_p(x)^q\\, dp \\right)^{1/q}\n$$\n\nSmall values indicate dense interior points, while large values suggest potential anomalies. The original paper analyses an unbagged estimator, yet the authors’ GitHub reproduces a baseline named aNNE that simply wraps DTM inside `scikit-learn`'s `BaggingRegressor`, training multiple DTM models on random subsamples and averaging their outputs—an ensemble trick that smooths variance but leaves the underlying DTM logic untouched.\n\n**Difference to ADERH and DTM**  \nWhile DTM and its bagged forms rely on global distance graphs, **ADERH** uses a purely local, randomized ensemble of hyperspheres to score points by edge proximity and sparsity. This avoids the instability of nearest-neighbor distances near dense boundaries, offering stable anomaly detection in high dimensions with fixed hyperparameters and no reliance on global structure.\n\n**[3]** Gu, Xiaoyi, Leman Akoglu, and Alessandro Rinaldo. *\"Statistical analysis of nearest neighbor methods for anomaly detection.\"* *Advances in Neural Information Processing Systems* 32 (2019).\n\n---\n\n### Experimental Results\n\nWe evaluate **ADERH**, GEM, and DTM under both default and optimized settings to assess detection performance and robustness.\n\n- ADERH:  \n  $n_{\\text{esti}} \\in \\{100, 200, 300\\}$  \n  $\\omega \\in \\{8, 18, 24\\}$\n\n- GEM (default $k = 5$):  \n  $k \\in \\{5, 10, 20, 30, 40, 50\\}$\n\n- DTM (default $n_{\\text{esti}} = 100$, subsample size = 256):  \n  Uses `scikit-learn`'s `BaggingRegressor` over DTM, per the protocol in [3]  \n  $n_{\\text{esti}} \\in \\{100, 200, 300\\}$  \n  Subsample size $\\in \\{128, 256, 300\\}$\n\nWe report AUC-ROC scores under both default and optimized settings. \nThe tables below present a representative subset of evaluated datasets due to space constraints. However, all datasets from the main paper were evaluated. Across the full benchmark, ADERH achieves the best average rank under both default (1.30 vs. 2.85 for GEM, 1.60 for DTM) and grid search settings (1.29 vs. 2.43 for GEM, 1.86 for DTM), confirming its consistent superiority.\nADERH consistently ranks top on most datasets and never performs the worst. Its robustness across configurations stems from its random pairing and multi-scale design, which adapts to varying data without relying on global heuristics like GEM. ADERH shows a statistically significant improvement over GEM and DTM under both default and grid search settings (paired Wilcoxon signed-rank test with Bonferroni-Holm correction; $p < 0.05$, $\\alpha = 0.05$). Its pair-and-halve strategy with density-weighted scoring enables scalable, multi-scale isolation with provable variance control. \n\n\n> We will release our updated codebase after the review process concludes, in accordance with the NeurIPS policy, which prohibits updates during the review phase.\n\n\n### Table: AUC-ROC performance under default setup  \n**Comparison between ADERH, GEM [2], and DTM [3]**  \n*Bold = best score (rank 1)\n\n| Dataset      | ADERH         | GEM [2]       | DTM [3]         |\n|--------------|---------------|---------------|-----------------|\n| Optdigits    | **0.775 (1)** | 0.378 (3)     | _0.770 (2)_     |\n| Skin         | **0.788 (1)** | 0.613 (3)     | _0.784 (2)_     |\n| Pendigits    | **0.962 (1)** | 0.714 (3)     | _0.960 (2)_     |\n| Toothbrush   | _0.901 (2)_   | **0.919 (1)** | 0.870 (3)       |\n| Wpbc         | **0.554 (1)** | 0.513 (3)     | _0.536 (2)_     |\n| Leather      | _0.991 (2)_   | _0.991 (2)_   | **0.992 (1)**   |\n| Satimage-2   | **0.998 (1)** | _0.895 (2)_   | **0.998 (1)**   |\n| Backdoor     | **0.889 (1)** | 0.664 (3)     | _0.852 (2)_     |\n| Shuttle      | _0.987 (2)_   | 0.628 (3)     | **0.989 (1)**   |\n| Waveform     | **0.768 (1)** | 0.708 (3)     | _0.743 (2)_     |\n| Cardio       | **0.938 (1)** | 0.663 (3)     | _0.927 (2)_     |\n| Bottle       | **0.964 (1)** | 0.958 (3)     | _0.963 (2)_     |\n| Celeba       | **0.732 (1)** | 0.570 (3)     | _0.714 (2)_     |\n\n\n---\n\n### Table: AUC-ROC performance with hyperparameter optimization; best result per method is reported.\n**Comparison between ADERH, GEM [2], and DTM [3]**  \n*Bold = best score (rank 1)\n\n| Dataset      | ADERH         | GEM [2]       | DTM [3]         |\n|--------------|---------------|---------------|-----------------|\n| Optdigits    | _0.777 (2)_   | 0.405 (3)     | **0.779 (1)**   |\n| Skin         | _0.788 (2)_   | 0.705 (3)     | **0.791 (1)**   |\n| Pendigits    | **0.963 (1)** | 0.836 (3)     | _0.962 (2)_     |\n| Toothbrush   | _0.905 (2)_   | **0.919 (1)** | 0.870 (3)       |\n| Wpbc         | **0.554 (1)** | _0.540 (2)_   | 0.536 (3)       |\n| Leather      | **0.993 (1)** | **0.993 (1)** | _0.992 (2)_     |\n| Satimage-2   | **0.998 (1)** | _0.995 (2)_   | **0.998 (1)**   |\n| Backdoor     | **0.895 (1)** | 0.717 (3)     | _0.863 (2)_     |\n| Shuttle      | _0.988 (2)_   | 0.688 (3)     | **0.989 (1)**   |\n| Waveform     | **0.815 (1)** | 0.730 (3)     | _0.746 (2)_     |\n| Cardio       | **0.945 (1)** | 0.889 (3)     | _0.932 (2)_     |\n| Bottle       | **0.966 (1)** | 0.962 (3)     | _0.963 (2)_     |\n| Celeba       | **0.747 (1)** | 0.592 (3)     | _0.721 (2)_     |"}, {"review_id": "zHSRZ7Fz5P", "reviewer": "Reviewer_nU8x", "summary": "The paper proposes ADERH (Anomaly Detection by an Ensemble of Random Pairs of Hyperspheres), an isolation-based anomaly detection method. The method isolates anomalies by randomly pairing data points in small subsets and constructing two hyperspheres using half of the pairwise distance as the radius. The core innovations of ADERH include: (1) creating diverse hyperspheres by randomly pairing samples in many small subsets, where the radii naturally reflect local density; (2) introducing the Pitch metric to quantify the normalized distance from points to hypersphere centers; (3) using NDensity to down-weight hyperspheres in sparse (anomalous) regions. Experiments on 22 benchmark datasets show that ADERH achieves the best AUC-ROC on 14 datasets with an average rank of 1.67, significantly outperforming existing methods.", "questions": "1. In Section 4.1 of the paper, why was the non-consecutive random seed combination [0,1,2,100,1000] chosen? Has this choice been validated? More importantly, for methods that don't involve randomness (such as LOF), were they also run on the same 3 data splits? How do you ensure that all methods are compared on exactly the same data splits?\n \n2. The “grid search” in Appendix P is actually just a limited sampling of parameter combinations (ADERH only tests 9 combinations), and the search space sizes vary greatly across different methods. Can you explain why different methods were allocated different search space sizes and provide the rationale for determining these parameter ranges? Could a more comprehensive hyperparameter optimization be performed? Or acknowledge the limitations of the current search? Also, can this limited search effectively support the conclusion that 'ADERH remains best even under optimal tuning'?\n \n3. While the paper cites variance bounds to support the choice of subset number n, this only shows that larger n leads to smaller variance, but doesn't prove that 256 is optimal. Additionally, the paper discusses the choices of subset number n and subset size ω separately, but lacks analysis of their interaction. Can the authors provide stronger theoretical support for determining optimal parameters? Theoretically, n×ω determines the total number of hyperspheres - is this product more important than individual n or ω? Or can the authors provide theoretical analysis on the joint optimization of n and ω?\n \n4. Although Figure 4 in Appendix H shows parameter stability, the test datasets vary drastically in scale, dimensions, and anomaly rates (as shown in the dataset details in Appendix J, Census has 299,285 samples while Lymphography has only 148), yet the same default parameters ω=18 and n=256 are used. Can the authors provide more detailed sensitivity analysis, including the magnitude of performance changes due to parameter variations on different datasets? Or can the authors explain the rationale for this uniform parameter setting and whether they considered providing parameter selection guidelines based on different data characteristics?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "1. The paper has a clear and reasonable motivation. The core ideas of isolation and isolation ensemble have been widely validated in anomaly detection. The ensemble of hyperspheres with radius halving and density adjustment is an interesting innovation. In particular, the idea of using local structural information (i.e., distances between paired points) to construct hyperspheres demonstrates certain novelty. \n\n2. The design of the two concepts, Pitch and NDensity, introduced in the paper is ingenious. Pitch effectively highlights anomalies near hypersphere boundaries through a ratio-based distance metric. NDensity appropriately reduces the influence of hyperspheres potentially centered on anomalies. The combination of these two complementary measures enables the method to effectively handle partial violations of δ-separation. \n \n3. The experimental evaluation uses a substantial number of benchmark datasets. Testing on 22 diverse datasets from different domains enhances the credibility of the results. The comparison includes various types of anomaly detection methods (isolation-based, deep learning-based, LOF, etc.), making the experimental comparison relatively comprehensive. \n \n4. The paper provides a theoretical analysis of the proposed method, particularly regarding δ-separation, variance bounds, and concentration inequalities. These theoretical results offer certain guarantees for the method's effectiveness and help readers understand why ADERH can effectively separate normal and anomalous samples.\n\nWeaknesses\n\n1. The experimental design description is confusing. For example, in Section 4.1, line 314 states \"Each experiment was repeated across three splits, with the average AUC-ROC and AUC-PR scores reported.\" However, in line 318 of the same section, it states \"For methods involving randomness (ADERH, INNE, IForest, EIF, PIDForest, DIF), we used seeds [0, 1, 2, 100, 1000] and reported the average AUC-ROC and AUC-PR.\" Furthermore, in Appendix K, it mentions \"This split is repeated three times with different random seeds; we report the average performance metrics across these three runs.\" This is confusing to me as a reader. Could you please clarify the complete experimental setup? How many independent runs were conducted in total for each method-dataset combination? Is it 3, 5, or 15? This directly affects the validity of the statistical tests.\n \n2. Although the authors acknowledge in Appendix R that real-world data rarely satisfies strict δ-separation, the theoretical analysis in this paper is primarily based on this idealized assumption, which may limit the method's applicability to complex data distributions.\n \n3. While the authors claim that the method is robust to hyperparameters, it still requires setting the number of subsets n and subset size ω. For different types of datasets, the optimal choice of these parameters may vary significantly.\n \n4. The proposed ADERH is conceptually quite similar to the existing INNE method, as both use hyperspheres. The main differences lie in the pairing strategy and weighting scheme.", "was_revised": true, "final_justification": "I have read the authors' rebuttal as well as other reviewers' comments. The authors have properly addressed most of my comments.", "rebuttal": "We sincerely thank the reviewer for their perceptive review.\n\n## W1 and Q1 - Experimental Design\n\nEach stochastic algorithm is executed using the random seeds ${0, 1, 2, 100, 1000}$—three consecutive PRNG states plus two distant ones—to probe robustness without excessive runtime. Furthermore, for every dataset, we pre-compute and cache three stratified 70/30 train–test splits using fixed split-seeds; these splits are reused verbatim by all methods.\n\nDeterministic models (e.g., LOF, ECOD) run once per split; stochastic ones run for all seed–split combinations, yielding 15 scores each. Unless noted, all ROC-AUC and AP values are averages over these runs: 3 for deterministic, 15 for stochastic approaches.\n\nTo verify seed-independence, we reran ADERH, INNE, IForest, and EIF with seeds ${0,1,2,3,4}$—results deviated only slightly from the canonical set. This confirms that our findings are robust to random seed choice, ensuring fair and reproducible comparisons.\n\n## W2 - Strict $\\delta$-separation\n\nEmpirically, **ADERH** is validated on several datasets—including large-scale benchmarks such as *Census* and high-dimensional feature embeddings like *MNIST-Stripe*—where it achieves strong AUC-ROC performance.\n\nFurthermore, our standard deviation analysis confirms that **ADERH** exhibits substantially lower output variance compared to other isolation-based anomaly detection methods, indicating superior stability (please see our response to Reviewer TZiB regarding Q3).\n\n## W3 - Optimal Choice of Parameters $n$ and $\\omega$\n\nPlease see our response in Q3 or Q4.\n\n## W4 - Comparison to INNE\n\nADERH is fundamentally novel, both in its *design philosophy* and *operational execution*.  \nUnlike traditional methods like INNE that rely on single-point statistics (e.g., radius ratios), ADERH introduces a synergistic dual-metric model capturing two orthogonal anomaly cues:\n\n- Geometric alignment via *Pitch*\n- Local sparsity via *NDensity*\n\n---\n\n## Core Innovations\n\n### 1. Multiplicative Dual-Factor Scoring\n\nRather than summing or tuning separate metrics, ADERH fuses *Pitch* and *NDensity* multiplicatively.  \nAnomalies only score high when *both* metrics indicate deviation, yielding precise, low-false-positive detection.  \nNo existing method fuses geometry and density in this way with such semantic clarity.\n\n$$\n\\text{ADERH-Score}(x) = \\text{Pitch}(x) \\cdot \\left(1 - \\text{NDensity}(x)\\right)\n$$\n\n---\n\n### 2. Adaptive Geometry via Pairwise Sphere Sampling\n\nADERH bypasses fixed-radius or $k$-NN constraints by randomly sampling point pairs within small subsets.  \nEach pair induces two adaptive spheres using half their distance. This enables local structure encoding without rigid thresholds, ideal for complex or nested geometries.\n\n---\n\n### 3. Built-in Robustness to Structural Anomalies\n\nADERH natively flags:\n\n- Edge anomalies, often missed by INNE, due to high *Pitch* ($\\approx 1$)\n- Sparse-center anomalies, undetectable by density-only methods, via low *NDensity*  \n  (as formalized in Lemma 3.10)\n\nThis is design-level robustness, not a post-hoc adjustment.\n\n---\n\n### 4. Empirical & Theoretical Superiority\n\n#### ADERH is not just conceptually superior—it outperforms INNE and others on 20+ datasets on AUC-ROC and AUC-AP.  \n#### Concretely, ADERH’s ROC-AUC std ≈ 0.0133 and AP std ≈ 0.0317, both much lower than INNE’s (≈ 0.0241 and ≈ 0.0515). This shows greater stability, validating ADERH's good performance.\n---\n\nNo prior method unifies **geometry-aware scoring**, **density sensitivity**, and **adaptive local structure** the way **ADERH** does.\n\n\n\n## Q2 - Limited Grid Search\n\nTo ensure fair comparisons, we equalized total compute (\\~9–12 evals/method), not per-axis grid granularity, accounting for varying hyperparameter dimensions and runtimes. Parameter ranges centered on author-recommended defaults from original papers or widely used libraries.\n\nSince unsupervised anomaly detection lacks labels, traditional tuning (e.g., CV) is infeasible and risks bias. As highlighted in \\[1] and \\[2], defaults are standard for consistency and scale. We followed this precedent to maintain parity.\n\nCrucially, we went further, conducting systematic grid searches for both isolation-based and deep learning baselines. Across 20+ benchmarks, our method ranked #1 on average under both realistic (defaults) and idealized (tuned) conditions.\n\nTo further solidify the evaluation, we extended the grid for isolation-based baselines from 9 to 25 configurations:\n\n- ADERH (proposed method): Varying the ensemble size  \n  $n_{\\mathrm{esti}} \\in \\{100, 150, 200, 300, 500\\}$  \n  and the random-subset size  \n  $\\omega \\in \\{8, 18, 24, 30, 36\\}$\n\n- INNE: Varying  \n  $n_{\\mathrm{esti}} \\in \\{100, 150, 200, 300, 500\\}$  \n  and max subsample size  \n  $\\{8, 18, 24, 30, 36\\}$\n\n- IForest: Varying  \n  $n_{\\mathrm{esti}} \\in \\{100, 150, 200, 300, 500\\}$  \n  and max samples per tree  \n  $\\{128, 200, 256, 300, 500\\}$\n\n- EIF: Same grid as IForest.\n\nWe evaluate a representative subset of datasets, sufficient to capture the main trends. The results validate the original findings: ADERH consistently outperforms isolation-based baselines, showing robustness across all parameter settings.\nEven with 25 optimized configurations, no baseline surpassed ADERH in multiple settings.\n\n---\n\n### Table: Performance comparison of four methods across various datasets  \n**Bold = best score (rank 1)**\n\n| Dataset      | ADERH            | INNE             | IForest          | EIF             |\n|--------------|------------------|------------------|------------------|------------------|\n| Optdigits    | _0.775 (2)_      | **0.849 (1)**    | 0.727 (4)        | 0.739 (3)        |\n| Wbc          | **1.000 (1)**    | 0.914 (4)        | **1.000 (1)**    | **1.000 (1)**    |\n| Pendigits    | **0.963 (1)**    | 0.940 (4)        | 0.954 (3)        | _0.956 (2)_      |\n| Wpbc         | **0.555 (1)**     | _0.526 (2)_       | 0.501 (4)         | 0.521 (3)     |\n| Stamps       | _0.880 (2)_       | 0.739 (4)         | **0.888 (1)**     | 0.879 (3)     |\n| Waveform     | **0.817 (1)**    | _0.746 (2)_      | 0.729 (4)        | 0.735 (3)        |\n| Cardio       | **0.945 (1)**    | 0.918 (4)        | 0.927 (3)        | _0.929 (2)_      |\n| Bottle       | **0.968 (1)**    | 0.936 (3)        | _0.950 (2)_      | 0.000 (4)        |\n| Vowels       | **0.968 (1)**    | _0.951 (2)_      | 0.788 (4)        | 0.825 (3)        |\n| Wine         | **0.883 (1)**    | _0.799 (2)_      | 0.741 (4)        | 0.786 (3)        |\n\n##  Q3 - Parameter Choices\nWith fixed compute $N_{\\text{hyp}} = n\\omega$ (ADERH scales linearly), risk is minimized by choosing $\\omega$ just large enough to cover all normal modes (typically low-teens) and allocating the rest to ensemble size $n$. This strategy balances contamination control with the variance bound established in the paper.\n\n### Variance\n\nFrom Equation 14, the ensemble variance satisfies:\n\n$$\n\\operatorname{Var}[I(x)] \\le \\frac{1}{4n}\n$$\n\nSubstituting $n = \\frac{N_{\\text{hyp}}}{\\omega}$ gives:\n\n$$\n\\frac{\\omega}{4N_{\\text{hyp}}}\n$$\n\nThis reveals that larger $\\omega$ **increases variance** by reducing the number of subsets available for averaging.\n\n---\n\n### Contamination Bias\n\nFor anomaly rate $\\rho \\ll 1$, the chance that a subset of size $\\omega$ includes at least one anomaly is:\n\n$$\np_{\\mathrm{cont}}(\\omega) = 1 - (1 - \\rho)^\\omega\n$$\n\nEach contaminated subset perturbs the score by at most $c \\le 1$ (since $\\text{WPitch} \\in [0,1]$), so the squared bias is bounded by:\n\n$$\nc^2 \\cdot p_{\\mathrm{cont}}(\\omega)^2\n$$\n\nFor small $\\rho\\omega$, this grows like $(\\rho\\omega)^2$ and eventually saturates—**worsening with larger $\\omega$**.\n\n---\n\n### Coverage\n\nA subset must sample at least one representative from each of the $k$ normal clusters or no hypersphere can be centered in that region. Coupon-collector tails give:\n\n$$\n\\Pr[\\text{miss a cluster}] \\le k e^{-\\frac{\\omega}{k}}\n$$\n\nTo guarantee failure probability below $\\delta$, it suffices that:\n\n$$\n\\omega \\ge k \\ln(k/\\delta)\n$$\n\n---\n\n### Mean-Squared Error (MSE) Proxy\n\nCombining the three pieces yields a proxy for mean-squared error:\n\n$$\n\\mathrm{MSE}(\\omega) \\le \\frac{\\omega}{4N_{\\text{hyp}}} + c^2\\left[1 - (1 - \\rho)^{\\omega}\\right]^2 + \\mathbf{1}_{\\{\\omega < k \\ln(k/\\delta)\\}}\n$$\n\n- The indicator drops to zero once $\\omega$ hits the coupon-collector threshold (i.e., enough to sample each cluster once).\n- Beyond this, **both error terms grow with $\\omega$**, so the optimal $\\omega$ is the smallest feasible.\n\nFeasibility isn't purely statistical: random pairing requires ~10–20 points per subset to ensure full cluster coverage and pairing diversity. This reflects a **contamination–variance tradeoff**:\n\n- First, using 256 subsets isn’t inherently optimal—it reflects a safe, low-contamination $\\omega$ under computational limits.\n- Second, $n\\omega$ isn’t decisive:  \n  - $n$ controls **variance**  \n  - $\\omega$ controls **bias**  \n  - Their **balance** ensures reliable isolation.\n\n## Q4 - Parameter Stability\nADERH demonstrates strong robustness and stability across diverse datasets, showing low standard deviations regardless of dimensionality or sample size (e.g., Pendigits: 0.004, Skin: 0.013). This aligns with its theoretical foundation, which is agnostic to data characteristics. Ensemble configurations consistently outperform single models, confirming the theoretical benefits of aggregation. Moreover, default parameters yield performance close to grid-searched optima, supporting the bias–variance prediction that ADERH operates in a flat region. Despite the unsupervised nature of anomaly detection, ADERH achieves state-of-the-art performance with minimal tuning.\n\n[1] Fang, Zeyu, et al. \"Towards a Unified Framework of Clustering-based Anomaly Detection.\" Forty-second International Conference on Machine Learning (ICML 2025).\n\n[2] Han, Songqiao, et al. \"Adbench: Anomaly detection benchmark.\" Advances in neural information processing systems 35 (2022)."}]

Author rebuttal:

Meta-review: The paper proposes a new anomaly detection algorithm. The idea behind the algorithm is that anomalous points are separated from normal points, while normal points cluster in small neighborhoods, anomalous points are far away from such local clusters. Based on this, the proposed algorithm draws hyperspheres around randomly chosen points to detect anomalous points. The approach is found to do well experimentally, and comes with theoretical analysis under certain separation assumption on the anomalies. The reviewers concerns were adequately address in the discussion phase. A suggestion to improve the paper is that it would be interesting to have more detailed experimental studies, including ablations to understand when and why the proposed method is better than previous techniques.
Decision: Accept (poster)