Fast Hyperboloid Decision Tree Algorithms
Authors: Philippe Chlenski
Ethan Turok
Antonio Khalil Moretti
Itsik Pe'er
Venue: ICLR 2024 poster (2024)
Keywords: hyperbolic space
random forest
decision tree
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: Decision trees and random forests with geodesic splits work well in hyperbolic space

Abstract: Hyperbolic geometry is gaining traction in machine learning due to its capacity to effectively capture hierarchical structures in real-world data. Hyperbolic spaces, where neighborhoods grow exponentially, offer substantial advantages and have consistently delivered state-of-the-art results across diverse applications. However, hyperbolic classifiers often grapple with computational challenges. Methods reliant on Riemannian optimization frequently exhibit sluggishness, stemming from the increased computational demands of operations on Riemannian manifolds. In response to these challenges, we present HyperDT, a novel extension of decision tree algorithms into hyperbolic space. Crucially, HyperDT eliminates the need for computationally intensive Riemannian optimization, numerically unstable exponential and logarithmic maps, or pairwise comparisons between points by leveraging inner products to adapt Euclidean decision tree algorithms to hyperbolic space. Our approach is conceptually straightforward and maintains constant-time decision complexity while mitigating the scalability issues inherent in high-dimensional Euclidean spaces. Building upon HyperDT, we introduce HyperRF, a hyperbolic random forest model. Extensive benchmarking across diverse datasets underscores the superior performance of these models, providing a swift, precise, accurate, and user-friendly toolkit for hyperbolic data analysis.

FAST HYPERBOLOID DECISION TREE ALGORITHMM
Philippe Chlenski," 1 Ethan Turok,' Antonio Moretti, 2 Itsik Pe'er!
CColumbia University BBarnard College
ABSTRACT
Hyperbolic geometry is gaining traction in machine learning due to its capacity to effectively capture hierarchical structures in real-world data. Hyperbolic spaces, where neighborhoods grow exponentially, offer substantial advantages and have consistently delivered state-of-the-art results across diverse applications. How- ever, hyperbolic classifiers often grapple with computational challenges. Methods reliant on Riemannian optimization frequently exhibit sluggishness, stemming from the increased computational demands of operations on Riemannian mani- folds. In response to these challenges, we present HYPERDD,, a novel extension of decision tree algorithms into hyperholic space. Crucially, EYyeRRDTeliminaan the need for computationally intensive Riemannian optimization, numerically un- stable exponential and logarithmic maps, or pairwise comparisons between points by leveraging inner products to adapt Euclidean decision tree algorithms to hy- perbolic space. Our approach is conceptually straightforward and maintains constant- time decision complexity while mitigating the scalability issues inherent in high-dimensional Euclidean spaces. Building upon HYPERDT we introduce HYPERRF, hyperbolic random forest model. Extensive benchmarking across diverse datasets underscores the superior performance of these models, providing swift, precise, accurate, and user-friendly toolkit for hyperbolic data analysis. Our code can found at https::///// http//gtttu///t cow http:///cc..ccceess///ppoooo.
INTRODUCTION
1.1 BACKGROUND: HYPERBOLIC EMBEDDINGS
The adoption of hyperbolic geometry for graph embeddings has sparked vibrant and rapidly grow- ing body of machine learning research (Sarkar 2012; Chamberlain et al.) 2017: Gu et al. 2019 Chami et al.) 2020 202I). This surge in interest is driven by the compelling advantages offered by hyperbolic spaces, particularly in capturing hierarchical and tree-like structures inherent in various real-world datasets. hyperbolic space, neighborhoods grow exponentially rather than polyno- mially, allowing for embeddings of exponentially growing systems such phylogenetic trees or concept hicrarchies. Hyperbolic embeddings have proven to be highly effective, showcasing state- of-the-art results across various applications including question answering (Tay et al.) (018),, node classification (Chami et al. 2020). and word embeddings (Tifrea et al., 2018). These achievements underscore the growing interest in classifiers that operate natively within hyperbolic spaces (Gul- cehre et al. 2018 Marconi et al. 2020 Doorenbos et al. (202)).
While hyperbolic classifiers leverage the curvature properties of hyperbolic geometry to make more nuanced and accurate predictions of hierarchical data, such techniques often face a dilemma. Meth- ods employing Riemannian optimization often exhibit sluggishness due to the increased computa- tional complexity associated with operations on Riemannian manifolds, which require intricate ge- ometric calculations. The sensitivity of Riemannian optimization to initialization and the presence of complex geometric constraints can further contribute to slower convergence. Other methods are consistent with hyperbolic geometry but incur time-complexity penalties associated with horosphere calculations (see, for example, Fan et al. (2023); Doorenbos al. (2023)). Others apply Euclidean methods to hyperbolic data transformed with logarithmic maps (Chami et al.) 2019 Chen et al, 2022) whitening techniques (Chami et al. 2021), directly hyperbolic coordinates (Jiang al.
2022 While effective, such methods can ignore the geometric structure of the data or introduce additional complexity the inference process, adversely affecting both speed and interpretability.

---

Do
222
22
0
22
Figure 1: Geodesic partitions in the hyperboloid model 2 (left) and poincare model I221 (right) into two halves (purple/yellow). In H geodesic can be expressed as the intersection of the hyperboloid with angled plane through the origin of the ambient space (transparent white). While these two representations equivalent these partitions can be expressed more compactly in H2.1
1.2 THE NEED FOR HYPERBOLID DECISION TREES AND PAPER CONTRIBUTIONS
Decision trees are workhorses of machine learning, favored for a variety of reasons, including:
Speed. Decision trees are relatively fast train, and efficient prediction makes them suit- able for real-time or near-real-tine applications.
Interpretability. Decision trees provide a highly interpretable model, unlike random forest methods that can be opaque regarding how features combine to form predictor.
Simplicity. Decision trees involve straightforward logic, making them easier to implement and explain than multilayered, highly parameterized network models.
The additional complexities introduced by hyperbolic geometry, which often necessitate intricate optimizations over Riemannian manifolds, introduce a disparity between the existing availability of efficient decision tree algorithms tailored such spaces and their potential transformative impact.
This paper introduces a novel approach to extend traditional Euclidean decision tree algorithms to hyperbolic space. This approach, called HYPERDT, is conceptually straightforward and main- tains constant-time decision complexity while mitigating the scalability issues inherent in high- dimensional Euclidean spaces. Building upon HYPERDT, introduce ensemble model called HYPERRF, which an extension random forests tailored for hyperbolic space. Our contributions in this work are summarized as follows:
1. We develop HYPERDT, novel extension of decision trees to data in hyperbolic space, e.g- learned hyperbolic embeddings. HYPERIT avoids computationally expensive Rieman- nian optimization, numerically unstable exponential or logarithmic maps, and quadratically scaling pairwise comparisons between all data points. Instead, we reframe decision trees in Euclidean space in terms of inner products, yielding natural extension to hyperbolic spaces of arbitrary negative curvature. Like other decision tree algorithms, HYPERDT repeatedly partitions the input space into decision areas, i.e. subspaces labeled with the majority class for the points in the training set for that region. However, because it uses geodesic submanifolds partition the space, HYPERDT is the first decision tree predictor whose decision areas maintain convexity and topological continuity for arbitrary partitions.
2. We generalize HYPER DT to random forests second algorithm which we refer to as HYPERRF. In select cases, HYPERRF demonstrates enhanced accuracy and reduced sus- ceptibility to overfitting when contrasted with HYPERDT.
3. We demonstrate state-of-the-art accuracy and speed of HYPERDT and HYPERRF on clas- sification problems compared to existing counterparts various datasets.
4. We provide a Python implementation of HyPERDT and HyPERRF for classification and regression following SCIKIT-LFARN API conventions (Pedregosa et al. 2011).
2

---

1.3
RELATED WORK
Several graph embedding methods have been proposed in the Poincaré disk (Nickel & Kiela 2017;
Chamberlain et al.) 2017), hyperboloid model (Nickel & Kiela 2018), and even in mixed-curvature products of manifolds (Gu et al.] 2019). De Sa et al. (2018) provides a thorough overview and comparison of graph embedding methods in terms of their metric distortions.
Hyperbolic embeddings have found diverse applications across domains, particularly in computa- tional biology and concept ontologies, both of which are structured by latent branching relation- ships. In biology, inheritance patterns are tree-like: at evolutionary scales, hyperbolic embeddings successfully model well-known phylogenetic trees (Hughes et al. 20044 Chami et al.) 2020 Diang et al. (022). Furthermore, Corso et al. (202I) learn faithful hyperbolic species embeddings directly from nucleotide sequences, bypassing phylogenetic tree construction. On shorter timescales, such as single-cell RNA sequencing data, where cell types evolve from progenitors, a tree-like like structure emerges once more. Ding & Regev/ (2021) showcased that variational autoencoders with a hyper- bolic latent space effectively capture the branching patterns of cells' developmental trajectories.
For concept ontologies like WordNet, hyperbolic embeddings effectively capture subelass relation- ships among nouns, improving link prediction accuracy (Ganea et al. 2018). Additionally, Tifrea eet al. (2018) showcase the utility of hyperbolic embeddings for unsupervised learning of latent hi- absent, a capability possibly underpinned by the hierarchical
erarchies when explicit ontologies nature of concepts within WordNet. Moreover, recent study by Desai et al.] (2023) unveils that text-image representations in hyperbolic space exhibit enhanced interpretability and structural orga- nization while maintaining performance excellence in standard multimodal benchmarks.
Machine learning on hyperbolic embeddings is an emerging and evolving research area. Cho et al. (2018) and (Fan et al. (023) have proposed approaches for adapting support vector machines to hy- perbolic space, which has proven useful in biological contexts (Agibetov al., (019). In the realm of neural methods, there have been developments such as hyperbolic attention networks (Gulcehre) al. 2018), fully hyperbolic neural networks Chen et al. (2222), and hyperbolic graph convolu- tional networks CCami et al.) 2202T). A recent contribution by Doorenbos et al. (2023) introduced HORORF, a variant of the random forest method that employs decision trees with horospherical node criteria. Our approach is most similar to Doorenbos et al. (202);; however, it differs in that utilizes geodesics as opposed to horospheres and does not require pairwise comparisons between data points, leading
algorithm that maintains constant time decision complexity.
Improving decision tree and random forest algorithms has also attracted considerable research at- tention, although except for HORORF, none of these methods are designed for use with hyperbolic emheddings. In particular, improvements like gradient boosting Chen & Guestrin (2016) and opti- mization based on branch-and-bound methods Lin al. (2022); McTavish al. (2022); |Mzumder et al. (2022) have been proposed to circumvent some of the suboptimal qualities of classic CART decision trees [reimmn (017), which uses greedy heuristic to select each split in the tree.
2 PRELIMINARY
2.1 HYPERBOLIC SPACES
Hyperbolic geometry, characterized by its constant negative curvature, can be represented by various models, including the hyperboloid (also known as the Lorentz Minkowski model), the Poincaré disk model, the Poincaré half-plane model, and the (Beltrami-)Klein model. We use the hyperboloid model due its simplicity expressing geodesics using plane geometry, which we exploit to de- fine our decision boundaries. While prior research in this field has predominantly centered on the Poincaré disk model, the straightforward conversion between Poincaré disk coordinates and hyper- boloid coordinates (See Section A. for details) allows for seamless integration of techniques across different hyperbolic representations, flexibility we leverage in our work.
The D-dimensional hyperboloid model is embedded inside an ambient (D + 1)-dimensional Minkowski space, a metric space equipped with the Minkowski inner product:
D
(x,x') = -00 + Σ xa
(1)
3

---

The above is equivalent adaptation of the Euclidean inner product, where the first term is negated. This distinguished first dimension, often termed the "timelike" dimension, earns its name due to its significance in the context of special relativity theory.
Let the hyperboloid have constant negative scalar curvature - -.. Inside the Minkowski space, points assumed to lie on H.D.K, the hyperboloid of dimension D and eurvature K:
H D.K {x E ER1+ (x,x)c
11/K, 20 0)
(2)
That is, the hyperboloid model assumes points lie on the surface of the upper sheet of two-sheeted hyperboloid embedded in Minkowski space (see Figure D.. The distance between two points on HI is
8(x, x') cosh - (x, xx)xxXX))//X3
This distance can be interpreted as the length of the geodesic, the shortest path on the manifold con- necting and z'. In the hyperboloid model, all geodesics are intersections of HP.K with respective 2D planes that pass through the origin of the Minkowski space.
2.2 DECISION TREE ALGORITHMS
The Classification and Regression Trees (CART) algorithm is a mainstay of machine learning, along- side extensions such random forests (Breiman 2001) and XGBoost (Chen & Guestrin 2016).
CART recursively partitions the feature space into increasingly homogenous subspaces by maxi-
mizing the information gain at each split S, IG(S). It measures improved homogeneity due to
splitting a dataset X into subsets X X of respective fractions I /
-
=
(4)
where C(-) is the impurity cost function of each set. Objective functions like Gini impurity, mean squared error (MSE), and entropy are popular choices for C(-). The tree iteratively constructed until further splits will constitute overfitting, A decision tree is often used as is make predictions. The Random Forest algorithm integrates predictions across ensembles of decision trees trained on randomly subsampled subsets of the training data using majority voting procedure.
3 HYPERBOLOID DECISION TREE ALGORITHMS
Extending CART to hyperbolic space involves several essential steps. First, outlined in Sec- tion 3.1, we express Euclidean decision boundaries in terms of inner products, providing the requi- site geometric intuition for hyperbolic decision trees. In Section we utilize these inner products to establish streamlined decision process based on geodesic submanifolds in hyperbolic space. 3.3 the selection of candidate hyperplanes, Section 3.4 presents closed-form equa- tions for decision boundaries, and Section 3.5 describes the Hyperbolic Random Forest extension HYPERRF.
3.1 FORMULATING DECISION TREES WITH INNER PRODUCTS
Traditionally, split is perceived as means ascertain whether the value of point x in given dimension d, is greater or lesser than a designated threshold, 0, namely,
S(x)
T( 0}
(5)
This decision boundary can also be thought of as the axis-parallel hyperplane æa = 0, and thus we rewrite the same split follows
S(x) = max(0, sign(x ndd) - -)),
(6)
where (dd is the one-hot base vector along dimension d, i.e. the normal vector of our decision hyperplane. Of course, Slis is the practical, (11) condition. The slower. O(D) Eq. 6ls instructive towards the hyperboloid generalization, and can still be computed in ((1) due sparsity of n(d).
4

---

3.2 EXTENSION TO THE HYPERBOLOID MODEL
We will now modify decision tree splits for hyperbolic space. Splitting a decision tree along stan- dard axis-aligned hyperplanes is inappropriate when all the datapoints lie on the hyperboloid: the intersection of an axis-aligned D+1 dimensional hyperplane with the hyperboloid HD.K in (D+1)- dimensional Minkowski space results D-dimensional hyperbola, which lacks any meaningful interpretation within the hyperboloid model. Euclidean CART generates such decision boundaries, but they are likely ill-suited to capture the geometry of hyperbolic space.
On the other hand, D-dimensional homogeneous hyperplanes, i.e. hyperplanes that contain the ori- gin, intersect H. as geodesic submanifolds. In 3D Minkowski space, geodesics between any {x,x'} C [H[2.1 lie on the intersection of H with some homogeneous 2D plane, as in Figure | In higher dimensions, homogeneous hyperplanes intersect D. as (D 1)-dimensional geodesic submanifolds, which likewise contain all geodesics between their elements. Partitions by homoge- neous hyperplanes maintain convexity and topological continuity: all pairs of points in a subspace reachable by shortest paths that stay completely within their own subspace.
Building upon the inner product formulation of splits Euclidean CART (Eq. ( we can substitute a set of geometrically appropriate decision boundaries without altering the rest of the CART frame- work. Specifically, we replace axis-paralled hyperplanes with homogeneous ones.
To maintain the dimension-by by-ionnn---diiiioonn character of Euclidean CART and enforce sparse normal vectors for efficient inner product calculations, we further restrict the number of decision boundary candidates to O x) by only considering rotations of the plane To = 0 along single other axis d. These hyperplanes are fully parameterized by d and the rotation angle 0, yielding corresponding normal vectors
ndd 0) := (mo- cos( 0, ..... 0, nd sin(O), 0....
They define hyperplanes that satisfy
To cos(0) - za sin (0) =
(8)
The sparsity of nnd 0) yields a compact (1) decision procedure:
S(z) sign (max (0, sin(f) cos(0)=x))
Notably, this procedure determines points' position relative to a geodesic decision boundary without computing the actual location of the geodesic on D. Because of this, is also curvature- -arauurr--gnosic..... Hyperbolic decision trees compose splits analogously to Euclidean CART: the same objective func- tions are applicable, and so is the consideration of a single candidate decision boundary per point per (space-like) dimension, resulting in identical asymptotic complexity.
3.3 CHOOSING CANDIDATE HYPERPLANES
In Euclidean CART, candidate thresholds are classically chosen among midpoints between succes- sive observed zz values in the data. The hyperbolic case is slightly more nuanced.
Each decision boundary for dimension is parameterized by an angle 6, instead of a coordinate value. Each point lies
plane of angle 0 tan (<zo/ra). The midpoint angle 9m between two angles 0, < 0g is defined in terms of points lying on the intersection of these hyperplanes with H... By setting all dimensions besides O and d to zero, we can solve for the angle corresponding to the point on D.K that is exactly equidistant to the points corresponding to angles 0,, 62:
cot (V VV=
if < π - 0₂
Om
(10)
cot- (V V
if > 0g
where V
sin (26,11 20 2ain +02) sin -1) See Appendix Section A.3 for full derivation.
3.4 PARAMETERIZING DECISION BOUNDARIES
Let P(0) be a decision hyperplane learned by HYPERDT (without loss of generality, assume d 1). We derive -losed-form equations for the geodesic submanifold where P(0) intersects HHP.K, When all other dimensions are 0, this occurs when
xo a00, K) sin( on a(0, K) cos(
(11)
5

---

Split depth:
Figure 2: Learned HYPERIT decision boundaries for 2, 3, 4, and 5-class mixtures of wrapped normal distributions visualized the Poincaré disk. All trees have maximum depth of 3 and forgo post-training pruning. In the visualization, regions are colored according to their predicted class labels while data points are colored according their true class labels.
where (0,0, K) :- V sec(20) K. Note that this is also the point on the intersection of P(0) and HD.K that is closest the origin. We use this to parameterize the entire geodesic submanifold G resulting from intersecting the plane with H.K.
v (sin(0), cos(O), 0,
(12)
n .... uy = 1, .... 0), 2 G (0, K) cosh(()) ax K) v sinh(()u2/VKK LEER
(13)
(14)
(0, cosh(t)v ( vd-1 E Gd- te R
(15)
For visualization, we use T projected the Poincaré disk p2.1, We recursively partition the space, plotting decision boundaries at each level and coloring the partitioned space by the majority class. 2 shows an example of such plot. See Appendix Section A.2 for a full derivation.
3.5 HYPERBOLOID RANDOM FORESTS
Analogously to the Euclidean case, creating a hyperboloid random forest is possible by training ensemble of hyperboloid decision trees on randomly resampled versions of the training data. For speed, we implement HYPERRF, a multithreaded version of hyperboloid random forests wherein each tree is trained as separate process.
4 CLASSIFICATION EXPERIMENTS
4.1 PERFORMANCE BENCHMARK BASELINES
For decision trees, we compare our method standard Euclidean decision trees as implemented in SCIKIT-LEARN (Pedregosa et al. 2011). Since we use the same parameters as the SCIKIT-LEARN decision and random forest classes, depth and number of points in a leaf node can be standardized. We additionally compare our random forest method to HORORF (Doorenbos
ensure that implementation details like maximum
2023), another ensemble classifier for hyperbolic data.
Since HORORF does not implement a single decision tree method, we modified its code to avoid resampling the training data when training single tree. We call this version HORODT.
For all predictors, we use trees with depth < 3 and 2 1 sample per leaf. For random forests, all methods use an ensemble 12 trees. We explore performance in D 4, 8, and 16 dimensions.
4.2 DATASETS
Synthetic Datasets. We create a hyperbolic mixture of Gaussians, the canonical synthetic dataset for classification benchmarks, following Cho et al, (0018). We use the wrapped normal distribution on the hyperboloid for each Gaussian described in Nagano al. (2019). We draw the means of each Gaussian component from a normal distribution in the tangent plane at the origin and project it onto the hyperboloid directly using exponential map. The timelike components of random

---

Gaussians may grow quite large in high dimensions, creating both numerical instability and trivially separable clusters. We thus shrink the covariance matrix D-fold. See Section A.4 for details.
NeuroSEED RNA Embeddings. NeuroSEED (Corso et al. 2021 method for embedding DNA sequences into (potentially hyperbolic) latent space by using a Siamese neural network with distance-preserring loss function. This method encodes DNA sequences directly into latent space without first constructing a phylogenetic tree-or, equivalently, it embeds a dense graph of pairwise edit distances. We trained 2, 4, and 16-dimensional Poincaré embeddings of the 1,262,987 16S ribosomal RNA sequences from the Greengenes database (McDonald et al. 2023), then filtered them to the 37,215 that have been identified in the American Gut Project McDonald et al.) (2018). This downsampling yields clinically relevant subset of all Prokaryote species. For the purposes of these benchmarks, however, we restricted ourselves to predicting the six most abundant phyla: Firmicutes, Proteobacteria, Bacteroidetes, Actinobacteria, Acidobacteria, and Plantomycetes.
Polblogs Graph Embeddings. We use Polblogs (Adamic & Glance 2005), a canonical dataset in the hyperbolic embeddings literature for graph embeddings. In the Polblogs dataset, nodes represent political blogs during the 2004 United States presidential election, and edges represent hyperlinks between blogs. Each blog is labeled according to its political affiliation, "liberal" or "conservative." We use the hyp11 (van Spengler et al.) 2023) Python implementation of the Nickel & Kiela (2017) method to compute 10 randomly initialized Poincaré disk embeddings in 2, 4, and 16 dimensions.
4.3 BENCHMARKING PROCEDURE
We benchmarked our method against Euclidean random forests as implemented in SCIKIT-LEARN, and against HORORF. Each predictor was run with the same settings, including dataset and random seed. HORORF and HORODT used Poincaré disk coordinates and all other modelsused hyperboloid model coordinates. Each dataset was converted the appropriate model of hyperbolic space for its predictor before training.
For Gaussian and NeuroSEED datasets, we drew 100, 200, 400, and 800 samples using the same five seeds. We recorded micro- and macro-averaged Fl scores, AUPRs, and run times under 5-fold cross-validation. cross-validation instances were seeded identically across predictors. We could not produce per-fold timing for HORORF, instead we recorded the time it took to run the full 5-fold cross-validation. For fairness, we timed the data loading scripts separately and subtracted these times from the reported HORORF times.
We conducted paired, two-tailed t-tests comparing each pair of predictors and marked significant differences in Table A full table of p-values is available in Section A.7 in the Appendix.
Benchmarks were conducted on an Ubuntu 22.04 machine equipped with an Intel Core i7-8700 CPU (6 cores, 3.20 GHz). NVIDIA GeForce GTX 1080 GPU with 11 GiB of VRAM, and 15 GiB of RAM. Storage was handled by a 2TB HDD and a 219GB SSD. Experiments were implemented using Python 3.1 accelerated by CUDA 11.4 with driver version 190.199.02
4.4 RESULTS
Classification Scores. The results of the classification benchmark are summarized in Table Out of 36 distinct dataset, dimension, and sample size combinations, HYPERDT had the highest score 28 times (one of which was a tie with SCIKIT-LEARN). We demonstrated statistically significant advantage over SCIKIT-LEARN decision trees cases, and over HoroRF in 27 cases. SCIKIT- LEARN statistically outperformed HYPERDT once, on the 8-dimensional Polblogs dataset.
Similarly, HYPERRF won 22 times, tying once each with SCIKIT-LFARN and HoroRF, and statis- tically outperforming SCIKIT-LEARN in 11 cases and HORORF in 13 cases. SCIKIT-LEARN sta- tistically outperformed HYPERRF in 4 cases, all on 8-dimensional NeuroSEED data, and HoroRF statistically outperformed HYPERRF in 2 cases, both 16-dimensional NeuroSEED data.
Overall, both HYPERDT and HYPERRF showed substantial advantages over comparable methods on the datasets and hyperparameters tested. In high dimensions, classifiers tended to converge to uniformly high performance. The best model for NeuroSEED embeddings varied by dimensionality, phenomenon that warrants further investigation.
7

---

Decision Trees SKLEARN
Random Forests
Data
D
HYPERDT
HORODT
HYPERRF
SKLEARN
HORORF
2
100
89.101
87.90
84.60
90.70
87.50
86.30
200
90.05
89.35
84.60
90.60
89.15
89.10
400
90.97t
89.53
85.55
91.32
89.00
88.88
800
91.88
90.14
85.75
91.99
89.33
89.45
4
100
98.701
97.70
93.60
98.40
97.90
97.90
200
98.75t7
98.10
95.80
98.85#1
97.90
98.05
Gaussian
400
99.25t
98.25
96.92
99.30
98.22
98.50
800
99.30
98.36
97.27
99.36
98.21
98.76
8
100
99.70'
99.60
97.70
99.70
99.50
99.10
200
99.65t
99.60
98.20
99.75
99.70
99.75
400
99.901
99.88
99.10
99.88
99.93
99.88
800
99.96
99.90
99.38
99.96
99.91
99.94
16
100
99.801
99.50
98.80
99.80
99.60
99.60
200
99.95
100.00
99.50
99.90
99.95
99.80
400
100.00
99.97
99.90
100.00
100.00
99.95
800
100.00
99.99
99.90
100.00
99.99
99.92
2
100
56.601
55.60
49.70
57.20
55.70
56.80
200
59.60
58.45
50.35
60.10
58.20
60.25
400
61.78t
61.00
50.62
61.58
59.47
59.33
800
61.69t
61.68
54.11
62.05
59.75
59.94
100
80.40
80.30
53,40
80.90
79.20
71.50
NewroSEED
200
83.60
83.701
52.70
84.45
82.00
70.40
400
83.88t
83.83
54.08
84.65
82.33
65.20
800
84.49
84.50
55.69
84.96#1
82.03
65.70
8
100
73.80
74.00
52.60
79.50
82.80
70.80
200
78.30
78.40
55.35
81.40
84.35*1
65.55
400
79.45
79.57t
52.30
82.42
86.40't
62.88
800
80.76!
80.76
50.55
82.03
86.34'1
$7.69
16
100
74.10
73.50
61.80
80.70
79.90
83.30
200
75.90
75.55
66.75
82.70
82.55
83.85
400
77.05
77.03
68.80
82.30
84.73
85.90"
800
79.21
79.221
69.59
82.44
84.44
85,49*
Polblogs
2
979
71.04
70.35
64.73
71.40
71.651
66.33
4
979
71.53t
70.83
62.38
72.31
72.10
68.53
8
979
74.02
74.85*1
61.58
74.87
75.361
63.60
16
979
75.06f
75.05t
63.70
76.36
76.801
69.12
Table Mean micro-Fl scores for classification benchmarks over 10 seeds and folds. The highest- scoring decision tree and random forests are bolded separately. means predictor beat HYPERRF, i means predictor beat HORORF, and $ means a predictor beat SCIKIT-LEARN, with < 0.05.
Runtime Analysis. In addition to accuracies, we report runtimes for each classifier on each task. particular, we are interested in the asymptotic behavior of our predictors as function of the num- ber of samples being considered. These runtimes plotted by dataset in Figure We demonstrate that our method, while slower than the SCIKIT-LEARN implementation by a constant factor, is al- ways faster than HORORF and grows linearly in runtime with the number of samples. In contrast, HORORF grows quadratically runtime as the number of samples increases. This is likely due to the additional complexity of learning horospherical decision boundaries using HoroSVM.
Because HORORF optimized for GPU, whereas HYPERRF is optimized for parallelism on CPU, exact runtime ratios be misleading and highly machine-dependent. Similarly, HYPERRF may
8

---

Gaussian
NeuroSEED
Polblogs
400
HyperRs HoroRF
HyperRF
Total runtime (s)
800
HoroRF
Total runtime (s)
RF
RF
300
Total runtime
600
40
200
400
20-
200
100
100
200
400
800
100
200
400
800
HyperRtF
HoroRF Classifier
RF
Number samples
Number samples
Figure 3: Time 5-fold cross- of the number points. Shaded regions are 95% confidence intervals. Split by dataset: (a) wrapped normal mixture, (b) NeurOSEED OTU embeddings, and (c) Polblogs embeddings.
cross- validation, averaged over 10 seeds for each classifier function
lack some optimizations found in SCIKIT-LEARN. Therefore, we emphasize the asymptotic aspect of this benchmark, which is agnostic to hardware details and constant-time optimizations.
The results of additional experiments can found in the Appendix. Section A.6. (.ttionnA6..] contains additional scaling benchmarks. Sections/A.6. A.6.3.....eteem. benchmarks to other hyperbolic classifiers and other models of hyperbolic geometry, respectively. Sections|A.6..4 and A.6.5 test performance on image and embeddings, respectively. Finally, Section A.tiionnAn...... tests the impact of ablating the midpoint computation described in Equation [0
Additional experiments
5 CONCLUSION
We have introduced HYPERDT, a novel formulation of decision tree algorithms tailored for hyper- bolic spaces. This approach leverages inner products to establish streamlined decision procedure via geodesic submanifolds. HYPERDT exhibits constant- time evaluation at each split and does not rely on Riemannian optimization nor pairwise point comparisons in training or prediction. We ex- tended this technique to random forests with HYPERRF, providing versatile tools for classification and regression tasks. HYPERDT more accurate than analogous methods in both Euclidean and hyperbolic spaces, while maintaining asymptotic complexity par with Euclidean decision trees.
The methodological innovation centers on selecting the appropriate decision boundary element to substitute for axis-paralle hyperplanes in the hyperbolic space context. Remarkably, homogeneous hyperplanes serve as highly effective building blocks, preserving continuity and convexity sub- spaces at each partition and deviating from traditional approaches by offering straightforward ex- pressions that avoid Riemannian optimization. The trick of using single-axis rotations of the base plane further simplifies and speeds up computation.
HYPERDT and HYPERRF stand out for their speed, simplicity, and stability. The hyperboloid model uses small, constant number simple trigonometric expressions at each decision tree node, thereby minimizing numerical instability concerns arising from floating-point issues. Finally, the alignment of hyperboloid geometry the tree-like structural features of hierarchy-oriented data manifests in single trees performing extraordinarily well, reducing the need for ensemble methods. Such single trees are faster to learn and use. More importantly, they offer full interpretability.
We offer an implementation adhering to standard SCIKIT-LEARN API conventions, ensuring case of use. Future research avenues can expand HYPERRF with popular features such as gradient boosting, optimization enhancements (e.g., pruning), and additional applications for classification and regres- sion within hyperbolic space. Additional optimizations can greatly improve both performance and usability e.g. through optimizing performance per the standards of SCIKIT-LEARN. Furthermore, new advanced decision tree methods such as Lin et al. (2022), McMaviss et al. (2022). and Mazumner et al. (2022), which are based axis-parallel hyperplanes but apply non- con-greedy optimizations multiple splits, can be reformulated terms dot trodpurs and applied to homogeneous hyper- planes instead.

---

ACKNOWLEDGMENTS
We acknowledge the support of the NSF Graduate Research Fellowship under grant no. DGE- 2036197 to Philippe Chlenski. We also thank Quentin Chu and Swati Negi for their early use and feedback on our software, which has been instrumental its development.
ETHICS STATEMENT
This paper aims to advance the field of Machine Learning, conscious of its potential societal impacts and committed to adhering to the ICLR Code of Ethics. Although research does directly tackle sensitive ethical issues and we identify no specific societal consequences requiring individual emphasis, recognize our work within the evolving landscape of machine learning ethics. Ac- knowledging that the ethical dimensions of machine learning are an area of ongoing exploration and debate, we commit engaging responsibly with these broader considerations and adhering to ICLR guidelines to address any emerging concerns.
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our work, have taken comprehensive steps detailed across paper, its appendices, and the supplemental GitHub repository. The main text delineates the method- ologies and experimental setups, with proofs and derivations of nontrivial mathematical insights in the Appendix. Our GitHub repository houses all of the code, data processing steps, and additional documentation that support the empirical results presented. The README file for our GitHub repo contains up-to-date detailed information on which files and notebooks reproduce which parts of the paper and links data that is not publically available.
REFERENCES
Lada A. Adamic and Natalie Glance. The political blogosphere and the 2004 U.S. election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, LinkKDD '05, pp. 36-43, New York, NY, USA, August 2005. Association for Computing Machinery. ISBN 978-1-59593-215-0, doi: 10.1144//33427111144277 URL /ttp:/:://ci..r//.....1.... 1134271 11322777
Asan Agibetov, Georg Dorffner, and Matthias Samwald. Using hyperbolic large-margin classifiers for biological link prediction. In Proceedings of the 5th Workshop Semantic Deep Learning (SemDeep-5), pp. 26-30, Macau, China, August 2019. Association for Computational Linguis-
tics. URL httpss: http:///aaaaaaaaaaaa www.llannooooyy..oooo org W1 9- 5805
Ahmad Bdeir, Kristian Schwethelm, and Niels Landwehr. Hyperbolic Geometry in Computer Vi- sion: A Novel Framework for Convolutional Neural Networks, March 2023, URL https:
1591 9v2
Lco Breiman. Random forests. Machine Learning, 45(1):5-322 October 2001. ISSN 1573-0565, doi: 10. 10.1023/A:010093444432 Utthttts::///oooorrp/p 1023/A: 01110000000000111100000000000000
Leo Breiman. Classification and Regression Trees. Routledge, New York, October 2017. ISBN
978-1-315-13947-8 doi: 10. 10.120/9981111519977.
Benjamin Paul Chamberlain, James Clough, and Marc Peter Deisenroth. Neural Embeddings of Graphs in Hyperbolic Space, May 2017. URL http:://aaxiv..or/aa//////0//// 1rXiv:1705.10 10359 [cs, stat].
Ines Chami, Rex Ying. Christopher Ré, and Jure Leskovec. Hyperbolic Graph Convolu- tional Neural Networks, October 2019. URL arXiv:1910.1 12933 [cs, stat].
Ines Chami, Albert Gu, Vaggos Chatziafratis, and Christopher Ré. From Trees to Continuous Embeddings and Back: Hyperbolic Hierarchical Clustering, October 2020. URL https:
//axxiv.org/ab/// 00402v
10

---

Ines Chami, Albert Gu, Dat Nguyen, and Christopher Ré. HoroPCA: Hyperbolic Dimensional- ity Reduction via Horospherical Projections, June 2021. URL http: http://aaxivv.oooo. abs/
2106. 03306 AxXiv:210.033360 [cs].
Tianqi Chen and Carlos Guestrin. XGBoost: Scalable Tree Boosting System. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785 7944, August 2016. doi: 10. 1114449993977222999955 URL attp:://rxxiy org/
abs/ 6603. 02754 AXXi:1603.022544 [es].
Weize Chen, Xu Han, Yankai Lin, Hexu Zhao, Zhiyuan Liu, Peng Li, Maosong Sun, and Jie Zhou. Fully Hyperbolic Neural Networks, March 2022. URL http:://axxiv..rr//bbbs.. 14686 arXiv:2105. 146.6 [cs].
Hyunghoon Cho, Benjamin DeMeo, Jian Peng, and Bonnie Berger. Large-Margin Classifi- cation in Hyperbolic Space, June 2018. URL arXiv:1806.0044 00633777077777 [cs, stat].
Gabriele Corso, Rex Ying, Michal Pándy, Petar Veličković, Jure Leskovee, and Pietro Liò. Neural Distance Embeddings for Biological Sequences, October 2021. URL http:://rxiv.orr/ abs/2109, 09740 arXiv:2109.09740 [cs, q-bio].
Christopher De Sa, Albert Gu, Christopher Ré, and Frederic Sala. Representation Tradeoffs for Hyperbolic Embeddings, April 2018. arXiv:1804.03329 [es, stat].
Karan Desai, Maximilian Nickel, Tanmay Rajpurohit, Justin Johnson, and Ramakrishna Vedantam. Vedanttm Hyperbolic Image-Texx Text Representations, June 2023. 09172
MxXiv22304009177 [cs].
Jiarui Ding and Aviv Regev. Deep generative model embedding of single-cell RNA-Seq pro- files on hyperspheres and hyperbolic spaces. Nature Communications, 12(1):2554, May 2021. URL https: / www nature. com/ Number: Publisher: Nature Publishing Group.
ISSN 2041-1723. doi: 10. 1063//441777--0222288858
Lars Doorenbos, Pablo Márquez-Neila, Raphael Sznitman, and Pascal Mettes. Hyperbolic Random
Forests, August 2023. URL http:://arx.v.orrg//b////22 13279 arXiv:2308. 13279 [cs].
Xiran Fan, Chun-Hao Yang, and Baba Vemuri. Horospherical Decision Boundaries for Large Margin Classification in Hyperbolic Space, June 2023. URL http: http://axxiv.org/e05
23C2.06801 arXiv:2302.06807 [cs, stat].
Christiane Fellbaum. WordNet. In Roberto Poli, Michael Healy, and Achilles Kameas (eds.), Theory and Applications of Ontology: Computer Applications, pp. 231-243. Springer Nether- lands. Dordrecht, 2010. ISBN 978-90-481-8844 doi: 10.1007/978-900 01777778-9--11-884---5555 URL
hEtps::/4oi.org//55 http:/101100/10000
Octavian-Bugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic Entailment Cones for Learning Hierarchical Embeddings, June 2018. URL URL http:://arriii..r//abbb////////t
01882 arXiv:1804.00 01180400882222. [cs, stat].
Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Re. Learning mixed-curvature representa- tions in products of model spaces. 2019.
Caglar Gulcehre, Misha Denil, Mateusz Malinowski. Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia, Victor Bapst, David Raposo, Adam Santoro, and Nando de Freitas. Hyperbolic Attention Networks, May 2018. URL httpt::::/wwi..orgg//o/o/// 10 [cs].
09786
Timothy Hughes, Young Hyun, and David A. Liberles. Visualising very large phylogenetic trees in three dimensional hyperbolic space. BMC Bioinformatics, 5(1) April 2004. ISSN 1471-2105. doi: 10.1186/1471-2105- URL ht..st:s:: /t/

---

Yueyu Jiang, Puoya Tabaghi, and Siavash Mirarab. Learning Hyperbolic Embedding for Phyloge- netic Tree Placement and Updates. Biology, 11(9):1256, September 2022. ISSN 2079-7737. doi: 10.3390/biology/ 1091256. URL https: /wwww//www///././////////.w..../ mcppi. 2ttmmm099--777111//22222
Number: 9 Publisher: Multidisciplinayy Digital Publishing Institute.
Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and Scalable Optimal Sparse Decision Trees, November 2022. URL http:://arxiv..rg//bbbb/////
08690 arXiv:2006.08690 [cs, stat].
Gian Maria Lorenzo Rosasco, and Carlo Ciliberto. Hyperbolic Manifold Regression, May 2005. 13885 arXiv:2005. [cs, stat].
2020. wtt.tttp:://r//...orr///////
Rahul Mazumder, Xiang Meng, and Haoyue Wang. Quant-BnB: A Scalable Branch-and-Bond -ound Method for Optimal Decision Trees with Continuous Features, June 2022. URL http://
arxiv.org/ wtt.:/rggg./////aaa 11844 arXiv:2206. 1 1144 [cs].
Daniel McDonald, Embriette Hyde, Justine W. Debelius, James T. Morton, Antonio Gonzalez, Gail Ackermann, Alexander A. Aksenov, Bahar Behsaz, Caitriona Brennan, Yingfeng Chen, Lind- say DeRight Goldasich, Pieter C. Dorrestein, Robert R. Dunn, Ashkaan K. Fahimipour, James Gaffney, Jack A. Gilbert, Grant Gogul, Jessica L. Green, Philip Hugenholtz, Greg Humphrey, Curtis Huttenhower. Matthew A. Jackson, Stefan Janssen, Dilip V. Jeste, Lingjing Jiang, Scott T. Kelley, Dan Knights, Tomasz Kosciolek, Joshua Ladau, Jeff Leach, Clarisse Marotz, Dmitry Meleshko, Alexey V. Melnik, Jessica Metcalf, Hosein Mohimani, Emmanuel Montassier, Jose Navas-Molina, Tanya T. Nguyen, Shyamal Peddada, Pavel Pevzner, Katherine S. Pollard, Gho- lamali Rahnavard, Adam Robbins-Pianka, Naseer Sangwan, Joshua Shorenstein, Larry Smarr, Se Jin Song, Timothy Spector, Austin D. Swafford, Varykina G. Thackray, Luke R. Thompson, Anupriya Tripathi, Yoshiki Vázquez-Baeza, Alison Vrbanac, Paul Wischmeyer, Elaine Wolfe, Qiyun Zhu, American Gut Consortium, and Rob Knight. American Gut: an Open Platform for Citizen Science Microbiome Research. mSystems, 3()):c00031-13 2018. ISSN 2379-5077 doi: 10.1 10.1128/mss 122////ystemss00000
Daniel McDonald, Yueyu Jiang, Metin Balaban, Kalen Cantrell, Qiyun Zhu, Antonio Gonzalez, James T. Morton, Giorgia Nicolaou, Donovan H. Parks, Søren M. Karst, Mads Albertsen, Philip Hugenholtz, Todd DeSantis, Se Jin Song, Andrew Bartko, Aki Havulinna, Pekka Jousilahti, Susan Cheng, Michael Inouye, Teemu Niiranen, Mohit Jain, Veikko Salomaa, Leo Lahti, Siavash Mirarab, and Rob Knight. Greengenes2 unifics microbial data in a single reference tree. Na- ture Biotechnology, pp. 1-4, July 2023. ISSN 1546-1696. doi: 10. (0008//41157-023-1111
1.
URL/https: /esttps://ww..... /ww. www.nntuur..cmmmm www.urree.comeeeeeee http://eee..errricees///1111/11/ ture Publishing Group.
023 01845- 1
Publisher: Na-
Hayden McTavish, Chudi Zhong, Reto Achermann, Ilias Karimalis. Jacques Chen, Cynthia Rudin, and Margo Seltzer. Fast Sparse Decision Tree Optimization via Reference Ensembles, July 2022. URL
2l1p/ 00798 arXiv:2112.00077 [es].
Nina Miolane, Johan Mathe, Claire Donnat, Mikael Jorda, and Xavier Pennec. geomstats: a Python Package for Riemannian Geometry in Machine Learning, May 2018. URL
org/abs/ 1805. 08308v2]
Yoshihiro Nagano, Shoichiro Yamaguchi, Yasuhiro Fujita, and Masanori Koyama. A Wrapped Normal Distribution on Hyperbolic Space for Beaadeett-Based Learning, May 2019. URL (RLhttp:
7/arxiv. wwtp:/s.//////./a 902. 02992 arXiv:1902.02992 [cs, stat].
Maximilian Nickel and Douwe Kiela. Poincar) ' Embeddings for Learning Hierarchical Represen- arXiv:1705.0080 [cs,
tations, May 2017. URL stat].
Maximilian Nickel and Douwe Kiela. Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry, July 2018. URL. http:://axii: www.ooggg/bb...... 80066 03417
arXiv:1806.03417 [cs, stat].
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vanderplas,
12

---

Alexandre Passos, David Coumaaeaa,, Matthieu Brucher, Matthieu Perrot, and Edouard Duch- esnay. Scikit-leam: Machine Learning in Python. Journal of Machine Learning Research, 12(85):2825 2830, 2011. ISSN 1533-7928. URL http:// http:://mm...igg//... wttpppppppppv////
pedregose aat.oosallahha. html
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning Transferable Visual Models From Natural Language Supervision, February 2021. URL B htttpp:/aarx....rr/aabsssss
03. C0020 arXiv:2103.0000 103,00020 [es].
Rik Sarkar. Low Distortion Delaunay Embedding of Trees Hyperbolic Plane.
Mare Van Kreveld and Bettina Speckmann (eds.), Graph Drawing, volume 7034, pp. 355355-360 355-366. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. ISBN 978-3-642-258772 978-3-642-25877
doi: 10.1007/978-33644-288333
34. URL http::/1 //1ink. spri nger. com 10mm/1..1000
978-3-642-25878-11 34, Series Title: Lecture Notes in Computer Science.
Yi Tay, Luu Anh Tuan, and Siu Cheung Hui. Hyperbolic Representation Learning for Fast and Efficient Neural Question Answering. In Proceedings of the Eleventh ACM International Conference Web Search and Data Mining, WSDM '18, pp. 583-591, New York, NY, USA, February 2018. Association for Computing Machinery. ISBN 978-1-4503-5588-- doi: 10.11455/1555552311 URL
org/ 1155/315965.
Alexandru Tifrea, Gary Béeigneul, and Octavian-Euger Ganea. Poincar)'e GloVe: Hyper- bolic Word Embeddings, November 2018. URL http:ttpp//rrtt.oorr///////00000 arXiv: vrXiv:1810.06546 [es].
Max van Spengler, Philipp Wirth, and Pascal Mettes. HypLL: The Hyperbolic Learning Library, August 2023, URL http: arxiv. org/ htar/bbs/22300 06154 arXiv:2306.06154 [cs].
06154
13

---

A APPENDIX
A.1 CONVERSION BETWEEN HYPERBOLOID AND POINCARÉ MODELS
Letting Xp be a point in P..K and XH be its equivalent in HD.K
H.
P VK + HHH,
(16)
1 |
THO = VK.
(17)
1 T
HH VK- 2xp
(18)
xp
A.2 GEODESIC SUBMANIFOLD DETAILS
In this section, we will give full parameterization of the geodesic submanifolds created by inter- secting the decision hyperplanes learned by HyPERDT and HYPERRF with HP.K We enumerate the basis vectors of our decision hyperplanes using a formalism conducive to the following steps, calculate scaling factor that ensures a basis vector reaches the surface of the manifold, construct 1-dimensional geodesic arc from the basis vectors of decision hyperplane, and finally recursively extend this are to higher dimensions, culminating in a full (D d-dmmensional geodesic submani- fold.
To reduce the complexity of notation necessitated by indexing over dimensions, we will assume without loss of generality that the decision hyperplane's normal vector is nonzero in dimensions 0 and We extend this convention to geodesic submanifolds by putting nonzero dimensions first: therefore, first parameterize an along dimension 2, then turn into 2- 2-dimensional subman- ifold along dimension 3, and so on. In general, a (d < D)-dimensional submanifold will be nonzero in the first d + ambient dimensions.
A.2.1 BASIS VECTORS OF DECISION HYPERPLANES
Let P(0) be D-dimensional decision hyperplane learned by HYPERDT. By our assumption above and Equation 7 the normal vector n11, 9) of ((0) nonzero only in dimensions and Therefore P(0) has D basis vectors:
v (sin cos( 0, ...) u (0, u .... 0), 2
(19)
(20)
The u vectors are standard basis vectors which are in dimension d and 0) elsewhere.
A.2.2 COMPUTING VECTOR SCALE
For what scaling factor a does o lie on the manifold? We know that ov will always be zero in dimensions 2 through D, effectively reducing this to simple 2-dimensional problem on 2
21
2 1/K
(21)
J 1/K + =
(22)
a² cos 2 (0) = 1/K + a² sin (0)
(23)
a² (coss2 sin (0)) = 1/K
(24)
-1
Ka² cos2(0) sin (0)
(25)
K -1
(26)
cos
(20)
sec(20)
(27)
K
14

---

The transition from Equation 25
Equation 26 26 is due the dluulle-nggh formula. See Figure for a visual demonstration that rescaling v by a works for the full range of 0 values in one dimension. To extend this insight to arbitrary angles and curvatures, define a( K) function
sec(20)
sec (0))
K)
(28)
K
Figure 4: Rescaling basis vector v = (sin(0), cos(O)) by a(0, 1) V- sec(20) produces point
on 11 for all 0 values between /4 and 3 3
Intersections hyperbola
6-
8
4-
2-
-7.5
-5.0
-2.5
0.0
7.5
X1
A.2.3 GEODESIC ARCS
As shown in Chami al. 2019 sinh(t)u" for any pair of vectors (u", v*) where
geodesic in H. can be characterized cosh(t)v" +
(u', u² u²)e c 1/K
(29)
(v", v²) 11KK
(30)
v=) =0
(31)
All u vectors described in Equation 20 being purely spacelike, satisfy Equation 29 if rescaled by factor of VK so that their norms 1/K. We arbitrarily choose u² / / in our paramteriza- tion. Since a00, K) K)v² lies on H. satisfies Equation 30) Since v and u are disjoint in their nonzero dimensions, they trivially satisfy Equation 31 for any scaling factors. Letting vary freely, the geodesic is given by
g. (0, K, () = cosh(t) a(0, K): v + sinh
(32)
(cosh(t) (f,, K) sfn( cosh(t) a(0, K) cos(()) sinh(t)/VK,, O,...) The full geodesic are over all possible values of / is given by
(33)
G (0, = (g (0, K,t) LER).
(34)
A.2.4 GEODESIC SUBMANIFOLDS
For didactic purposes, first extend the geodesic are G1 2-dimensional submanifold G2
15

---

Since any point in (0, K) is on HH..K, it has Minkowski norm -1/K and therefore satisfies Condition 30
u vectors sequentially to construct geodesics. Therefore, if Gd is d- dimensional, then all u for d + 2 d' S D, being unused in the construction of the geodesic, remain orthogonal to all v E G and continue to satisfy Condition [1 In partieular, u is the smallest unused d vector. Being spacelike, all ud' continue to satisfy Condition 29
By convention,
For our next geodesic, we apply Equation 32 recursively to any v E G (0, and u² /// /V//
3,,, cosh(t') sinh(("uu//VK K, = cosh((')g (0) sinh(")u
(35)
(36)
cosh((")(cosh(())) sinh(()u?) sinh sinh(")u%/VK
(37)
The geodesic submanifold created by intersecting the 3-plane with basis vectors {vo, u² uz) with HP. corresponds to the set of all values of g² for (t, E R?:
G2 (0, K) = (g (0,
(t,t) E R
(38)
Using the remaining u vectors in ascending order from d 3 to D, recursively parameter- ize the full geodesic submanifold resulting from intersecting P(0) with H.K
(O, K) (sinh(()u** d+1 /VK cosh(()v d-1 v G Gd-1(0, LER) R)
(39)
A.2.5 VISUALIZZTTION-SPECIII DETAILS
Visualization assumptions. The first step to plotting a learned decision boundary is to find closed form equations for the intersection between the hyperboloid and the plane. To this end, make a number of simplifying assumptions. First of all, we restrict ourselves to the hyperboloid 2 For decision tree visualization, hyperplanes can be inclined along dimensions or 2; therefore, cannot assume that our first dimension contains the split. Instead, we parameterize our plane as P(,, d). The details of geodesics are the same as Equation 34 but dimensions 1 and may be exchanged when = 2. We also assume that the plane actually intersects 2 meaning ' //4 < 8 < 3 /4.
Poincaré disk projection. Since 2 is actually 3-dimensional object for visualization pur- poses, it is easier to visualize as a point on the Poincaré disk I2.11 Thus, we convert coordinates in H to p22. using Equation 16 For geodesics,
sample 1,000 points uniformly from (-10, 10) and convert these: this is sufficient to draw a smooth are on p221
Subspace coloring. For better visualizations, it is also necessary to partition p2.1 that:
1. Decision boundaries only rendered in the correct subtrees. For instance, if boundary operates in the left subtree of a higher split, then should only be drawn in the half of p2.1 where the left subtree is actually active.
2. The space is partitioned fully by the leaves of the decision tree, and can therefore be colored according to the majority class each leaf node.
To do this, we recursively feed in a mask at each plotting iteration. This mask turns off plotting for inactive regions of the Poincaré disk. At the leaf level, every point on the Poincaré disk active in only one mask, and therefore can be used to plot majority classes.
A.3 MIDPOINT ANGLES
Now we consider how to find 0,.. the midpoint between two angles 01 and 6g. One option is to take the midpoint naively by taking the average of two angles:
81 + 02
mm,naive
(40)
2
16

---

If assume without loss of generality that sin(01) sin(O2) < 7/2 (i.e. 0g hits higher the hyperboloid than 81). then am will hit closer to 81. Instead, we want some function F(01, 02) = 8m E [0,, 02] such that 6(0), 8m.) 8(02, mm). To do this, we need to compute hyperbolic distances, so we use the pseudo- Euclidean metric in our ambient Minkowski space. In particular, we have the distance between two points defined as:
ò ou, v) cosh (esh-'(-a (- c)
(41)
cosh -1 (200000 =dydd)
(42)
In (z0g0 - Idfle + v (IOY00 Idyaa) 1
(43)
This assumes that all dimensions besides O and d are O, and fixes the point on the intersection be- tween H. and the decision hyperplane as the frame of reference for all distances. Using the definition of (f, K) in Equation 28 we can simplify the conditions under which on is an equidis- tant midpoint of 0, and 02:
8(0,, 0b) == cosh -1 (a(Ba: ()a(bb. K) cos(O, + 6b))
(44)
This distance function is quite nonlinear, as seen in Figure 5 which corroborates the inappro- priateness of simply taking the mean between two angles a midpoint. Instead, we set the distances 5(01,0m and 8(fm, 02) equal and simplify. For conciseness, we define the shorthand
on == a(nn, K):
cosh (a (a1an, am cos(O: (01 + 0m)) cosh - (am 02 cos(Om : 02))
(45)
01amm cos(01 (0 + 6m) am 02 cos (n, + 02)
(46)
01 cos(01 + mm) ar2 (6n + 02)
(47)
sec (20)
(os + mm) V- sec()00)
c0 + 02)
(48)
VK
VK
sec(20)) cos 2 (0) + 0m) sec(202) 2os2(0m, + 02)
(49)
cos2(0) + 0m) cos cos2(00n + +2)
(50)
cos cos(20))
cos(202)
cos(202) cos? 2 (0) + 0m) cos(20)) cos² (02 0m) cos((02)(cos((8)) co.) sin((()) sin (0.,)) (0.))))))))))) ))² cos(20) (cos cos(20))(cos(((( cos( - sin(Om))
(51)
(52)
cos(20)) (cos( co sin(0)))) cos(20))(cos(())) co sin())))²
(53)
This is quadratic equation in cf.. expressed as U co + W (0m) +U = 0. where:
U = cos(202) cos (0,) cos(20)) cos (02)
(2 (o)) - 1) (O)) (2 cos2(())) - clsc
(02) cos² (0,)
(54)
W = cos(202) 2 cos (0,) sin (0)) - cos(20)) c0s)(22) sin
cos(202) sin cos(20)) sin
sin(20] - 28²)
(55)
U = cos(282) sin2(()) - coss(2))sin) ( (1 - 2 sin (02)) sin (0.) (1 2in (ii)(())) sin?(0))
sin²(01) sin (02)
cos?( cos² (01):
(56)
17

---

Since U U simplify further and solve cot' (6.. 2V cot(fm) where:
sin 202)
V WW/2U 2(cos? (02) cos (01)
sin(20; 20²)
2(cos((3) + cos (cos)))cccos - cos( (01))
sin - -282)
cos #1 cos( 62-0 ) sin 61 1.0
sin 02 81
2
sin (28) - 282)
(57)
2 sin 01) sin(02 01)
The solutions for the quadratic equation are cot(Om) = V + v vV2 1; specifically, we have
01
1 = 02 if 0 < 02
1oo- (V + +V2 if 0 > 02 Om
cot (V -V22_
(58)
Figure 5: A plot of function 8(x/4 + .01,0) 0) as 0 varies from 7/4 4 to 3m /4. This plot reveals the nonlinearity of the angle distance function.
Distance function plot: 6(m/4 +. +001, 0)
01
3.0
Distance from
2.5
1//4
n/2 Second angle 0
3m/4
A.4 MIXTURE OF GAUSSTANS ON HYPERBOLIC MANIFOLDS
We modify the method put forward in Nagano et al. (019 to sample Gaussians in hyperbolic space. We briefly reiterate their method to sample single Gaussian in HH D.K.
1. Choose point y in P.K to be the mean of your Gaussian.
2. Sample X n samples from a Euclidean multivariate Gaussian with mean 0 and any covariance Σ in D dimensions.
3. Transform X into X', set of vectors in P. (the tangent plane of P. the origin), by appending 0 in the timelike dimension.
4. Use parallel transport from the origin to jr, turning X' into X", set of vectors in P.K.
5. Use the exponential map at j to map X" to X" a set points on the surface D.K
For each Gaussian in our mixture, we perform this exact procedure. We choose our set of Gaussian means by sampling vectors from (0, I) in the tangent plane and then exponentially mapping them directly to H in other words, we follow the above procedure but skip step (4) because not defined yet (or, equivalently, because μ the origin).
18

---

Additionally, each covariance matrix is generated by drawing D D-dimensional samples, C (O,, I), and then letting Σ CC The entire covariance matrix is optionally rescaled by user-set noise scalar a and divided by D. That is,
CC E Σ=a D
(59)
This procedure is repeated n times to yield n distinct covariance matrices.
Finally, class probabilities are determined by drawing values from UO0 1) and normalizing them by their sum. Each point in a sample is assigned a class that determines its μ and Σ. We implement this method using the geomstats package in Python (Miolane al. 2018), which supports vectorized versions of parallel transport and exponential maps with differing destinations.
A.5 EQUIVALENCE OF MINKOWSKI AND EUCLIDEAN DOT-PRODUCTS
Most papers on hyperbolic geometry use Minkowski products. For instance, implementing the sup- port vector machine objective in Cho al. (2018) relies Minkowski products, which are crucial for the optimization procedure they specify.
In our case, it is sufficient to use the more intuitive Euclidean formulation, even though, in practice, Minkowski space not equipped with Euclidean products. Intuitively, Euclidean inner products (dot-products) accurately capture whether point is to one side of plane another, which is all that is needed for a decision tree classifier. However, we show further that Euclidean dot-products for HYPERDT decision boundaries have an interpretation in terms of Minkowski products:
The sparse Euclidean dot-product we determined in Equation is::
5(x) sign (max (0, (sin(f)xx - cos(())zo))
(60)
And, since the Minkowski inner product is simply the Euclidean dot-product with the sign of the timelike dimension flipped, we can equivalently say
Minkwskkss sign (max (0, (sin(f)=a cos())
(61)
Any 0 in the Euclidean case, if substituted for -0 in the Minkowski case, will yield the same cos(O) and a negated sf). That is,
sin(f) x - cos(f)
(62)
sin( -0)zz + cos(-oosc =0) b
(63)
sin(f) xd + cos(f)
(64)
sin(f) cos(f)zz -b -b
(65)
(66)
That is, for any angle 8 yielding particular split S over dataset X, evaluating the split using Minkowski inner products with the angle -0 produces an equivalent split. The sets are exactly the same, but the sign of the dot-product is flipped.
A.6 ADDITIONAL EXPERIMENTS
A.6.1 SCALING
In Figure 3 we showed that HYPERDT runtime scales linearly with sample size- an improvement over the exponential scaling of HORORF. this section, we show how runtime scales with the number of data points, number of dimensions, maximum depth of decision trees, and total num- ber of estimators. Since we are not comparing to slower methods, we can extend our analysis to substantially more than the upper limit of 800 samples use in the main section of the paper.
Procedure. Unless noted otherwise, we test the runtime and Fl-micro accuracy of HYPERRE with maximum depth of 3 and 12 trees, consistent with the HYPERRF results in Table We restrict ourselves to Gaussian mixtures of five classes rather than two, since this more challenging classification task has greater range of Fi-micro scores. Unless noted otherwise, 1,000 points for 20 distinct trials, without cross-validation and using a test set size of 200 points.
generated
We carried out four distinct scaling experiments, recording runtime and accuracy varied:
19

---

1. The number of points generated from 100 to 3,000
2. The number of dimensions from 2 to 64
3. The total number of decision trees in a forest from to 30
4. The max depth of each decision tree from to 20
Additionally, for the final max depth experiment, we also tested SCIKIT-LEARN Euclidean random forests and HORORF, also using 12 predictors. For this portion of the experiment, restrict selves to 800 samples from a 2-dimensional, 2-class mixture Gaussians.
Results. Times and F1-micro scores for the four HYPERRF scaling experiments are shown in F This figure shows that runtime scales linearly with the number of samples, dimensions, and trees, with little effect on overall prediction accuracy. Interestingly, the runtime levels off rather than growing exponentially for the maximum depth experiment as one might expect given the 2 deyth splits the predictor is allowed to make. This is because the actually achieved depth tops out when the training set is perfectly divided into homogeneous subregions of the decision space, and further splits are not made. Additionally, F1-micro scores decline slightly with increasing tree depth, likely due to overfitting.
Since maximum depth is the only parameter with a particularly interesting relationship to prediction accuracy, explored it further in the context of the other predictors evaluated in the paper. In Figure we compare the F1-micro scores of HYPERRF, HORORF, and Euclidean random forests, and find that HYPERRF has a consistent advantage over other predictors at the same maximum depth; however, as maximum depth increases, this advantage becomes less prominent. This result speaks both the general ability of elaborate random forests model data from arbitrary probability distributions, and to the parsimony of HORODT -based methods in modeling hierarchical data.
Sample scaling
Dimersion scaling
0.7
Taining time (S)
000
Taining time (G)
12.5
0.6
3.5-
f1-micro
10.0
0.5
Fl-micoo
0.4
5.0
0.5-
0
300
1000
1500
2000
2500
3000
10
20
40
50
66
Number of samples
Number dimensions
Tree scaling
Max depth scaling
1.50-
1.50
0.8
Raihing time 83
1.25
1.00
Training time
1.00
Fimmcro
0.75
0.75
0.2
0.5
0.25
F1-nioro
10.0 depth
15.0
Number trees
Figure 6: Observed runtimes when varying: (a) number of samples, (b) dimensionality, (c) number of trees, and (d) maximum depth simulated Gaussian mixture classification problem. We observe linear scaling for (a), (b), and (c), and possibly sublinear scaling with maximum tree depth. Shaded regions represent 95% confidence intervals.
A.6.2 COMPARISON TO OTHER HYPERBOLIC CLASSIFIERS
In the main body of the paper, we restricted ourselves to classifiers based on decision trees and random forests. However, there number of other capable and powerful classifiers for use on hyperbolic data that warrant evaluation. this section, we evaluate hyperbolic support vector machines and logistic regression classifiers against some of our benchmarks.
20

---

Max depth accuracy scaling by classifier
1.000
hororf hrf
0.975
0.950
rf
F1-micro
0.925
0.900
0.875
0.850
0.825
0.800
6
7
9
Max depth
Figure 7: Fl-micro scores a Gaussian mixture classification problem with 2 classes, 2 dimen- sions, and 800 samples. Shaded regions represent 95% confidence intervals.
Procedure. We used the implementation of hyperbolic support vector machines provided by Ag-
ibetov et al. [ and the implementation of hyperbolic logistic regression provided by Bdeir al. 2023) For each trial, generated 800 points from gaussian mixture with 2 classes and evaluated it using the Fl-micro score under 5-fold cross validation. We did this for 10 trials total, in 4, 8, and 16 dimensions.
In addition to the hyperbolic support vector machine and logistic regression classifiers, we evaluated their Euclidean counterparts, which are implemented in SCIKIT-LEARN Pedregosa et al. (20IT). We only benchmark against HYPERDT, which is simpler and slightly less accurate than HYPERRF, for fairness.
Results. We report average F1-micro scores for each classifier in each dimension Table 2 Fol- lowing the conventions of the paper, we additionally mark statistically significant differences from HYPERDT with an asteristk. In total, HYPERDT was a statistically significant improvement over each classifier in at least one dimension, and was the best classifier in half the cases. This shows consistent advantage over the other classifiers, which we can expect to be further improved by use of HYPERRF.
Logistic Regression
Hyperbolic Logistic Regression
Hyperbolic Support Vector Classifier
Support Vector Classifier
HYPERDT
2
90.11*
88.65*
81.50*
80.96*
91.88
4
99.20
99.41
96.94*
85.56*
99.30
8
99.97
99.96
100.00
79.06*
99.96
16
99.99
100.00
98. 12
86.99*
100.00
Table 2: Micro-averaged F1 scores under 5-fold cross validation averaged over 10 seeds for each classifier and dimension. Bold indicates the best score for that dimension; asterisks indicate statis- tically significant difference from HYPERDT as determined by a paired f-test.
A.6.3 RANDOM FORESTS IN OTHER GEOMETRIES
While no representation of hyperbolic space is explicitly compatible with axis-aligned splits, it is worth exploring the possibility that other representations nonetheless lend themselves better treat- ment by decision tree or random forest classifiers than the hyperboloid model does; more specifi- cally, it is worth testing HYPERDT and HYPERRF against greater range of embeddings to ensure are making fair comparison.
httt::://itthbb.com////mmme//
http:://giithbbb.cm///mmeeeeee
21

---

Procedure. Analogously to other sections, restrict ourselves to 800 samples from 2-class mix- tures of Gaussians in 2, 4, 8, and 16 dimensions. We record Fl-micro scores under 5-fold cross- validation, averaged over 10 seeds. In this case, evaluated HYPERDT, HYPERRF, and scikit- learn implementations of Euclidean decision trees and random forests for each sample.
We converted each sample Euclidean, Hyperboloid, Klein disk, and Poincaré disk coordinates. To get Euclidean coordinates, we applied the logarithmic map to project points from HD, to the langent plane the origin.
Results. Table 3 shows comparison of HYPERIT and HYPERRF to each of these geometries. Both HYPERDT and HYPERRF show substantial, statistically significant advantages over their Eu- clidean counterparts when applied to the hyperboloid model, and this is the only consistent trend in the data. Only the Poincaré disk in two dimensions beat HYPERRF with statistical significance.
Interestingly, the Klein disk embeddings performed well (without statistical significance) in two and three dimensionalities for decision trees and random forests, respectively. This likely because geodesics in the Klein model are represented with straight lines, the axis-parallel splits used by Euclidean decision tree algorithms are also geodesic decision boundaries. This yet another point in support of geodesic decision boundaries yielding improved classification performance.
Dimensions
Model
Geometry
2
4
16
Decision Tree
Euclidean
91.86
99.15
99.94
99.97
Hyperboloid
90.16*
98.34*
99.91
99.99
Klein
91.89
99.29
99.96
99.99
Poincaré
91.85
99.30
99.96
100.00
HYPERDT
Hyperboloid
91.88
99.30
99.96
100.00
HYPERRF
Hyperboloid
91.91
99.42
99.96
100,00
Random Forest
Fuclidean
92.09
99.28
99.97
100.00
Hyperboloid
89.80*
98.40"
99.95
100.00
Klein
92.05
99.46
100.00
100.00
Poincaré 92.26
99.45
99.97
100.00
Table 3: F1-micro scores for Euclidean and hyperbolic random forests and decision trees when applied to variety of hyperholic coordinate systems. Bolded scores the best for that dimension; asterisks represent statistical significance.
A.6.4 HYPERBOLIC IMAGE EMBEDDINGS
CLIP is a contrastive deep learning model with a joint text-image embedding space (Radford et al., 2021 Recently, Desai al. 2023 developed MERU, modified version of CLIP which encodes images and text into H1220.11
They impose a hierarchical structure on image an text embeddings: since images are more specific than the sentences which describe them, they encourage image em- beddings to have larger values in dimension than their corresponding text embeddings. In this case, the root of the hyperboloid represents the most general possible concept. Learning this hierarchy, MERU matches outperforms CLIP on zero-shot text-to-imane and maage-to-text retrieval tasks. However, matches or underperforms CLIP on zero-shot image classification tasks.
Procedure. We hypothesized that MERU classification performance suffers because Desai et al. (003) used logistic regression classifier, designed for Euclidean, not hyperbolic, space. To test this, we perform zero-shot image classification on CIFAR-I0 on pretrained ViT S/16 MERU and CLIP image embeddings using Euclidean and hyperbolic random forests All forests used 10 esti- mators with maximum depth of 5.
We also experiment with partial and full image embeddings. CLIP passes an image throught an image-encoder, a linear projection layer, and then an L2 normalization layer (project to the unit hypersphere). Similarly, MERU passes image through an image-encoder, a linear projection
*Pretrained models
thub. wtt.t..cnn/aabbooeeeerrrr//eeeee
22

---

Embedding
Predictor
CLIP Accuracy
MERU Accuracy
Encoder
Baseline
89.60
89.70
Encoder
Logistic regression
87.60
90.15
Encoder
Random forest
82.00
86.05
Encoder + L.
Random forest
84.20
84.85
Encoder + LP map
Random forest
84.00
85.10
Encoder + LP map
HYPERRF
86.20
Table Per-class average accuracies on zero-shot CIFAR-IO classification benchmarks. HYPERRF and SCIKIT-LEARN benchmarks are new, with baseline accuracies taken from Table 7 Desai et al. (2023). LP stands for linear projection. Note that map means L2 normalization for CLIP and exponential map to the hyperboloid for MERU. HYPERRF can only be evaluated on MERU with linear projection and exponential map applied, since all other representations are Euclidean.
layer, and then an exponential map (project the hyperboloid), In their experiments, Desai et al. (2023) performed classification only on the image-encoder outputs, which lie in Euclidean space for both CLIP and MERU. However, this approach ignores (1) the information provided by the projection layer and cannot leverage (2) the hierarchical structure gained from projecting to the hyperboloid. We thus exeriment with embeddings with different combinations of layers.
The results of this experiment are summarized in Table alongside the reported accura- cies from the original paper. We do not report standard deviation because we use the same train/test split as Desai et al. (2023).
Results.
First, we find that Euclidean random forests perform better on MERU-encoded data than CLIP- encoded data. This suggests that, in a linear probing context, MERU representations actually are more separable with respect CIFAR-10 classes.
Additionally, we show that hyperboloid random forests on MERU encodings with linear projec- tion and exponential mapping to the hyperboloid outperform all other combinations of classifiers and embeddings. These findings both demonstrate that hyperbolic embeddings for image-text joint embeddings enhance zero-shot classification performance and that hyperbolic random forests out- perform their Euclidean counterparts in this embedding space.
HYPERRF outperforms Euclidean random forests, suggesting is the best forest-type classifier for this task. However, we fail to beat the benchmark value reported in Desai al. (2023) for logistic regression. We reproduce similar accuracies on our own implementation of logistic regression.
A.6.5 WORDNET EMBEDDINGS
Hyperbolic embeddings of Wordnet Fellbaum (2010) are another popular benchmark for hyperbolic classifiers. We extend analysis to WordNet classification tasks.
Procedure. We use the WordNet embeddings and labels provided in the Github repository for Doorenbos et al. 2023 These are split into binary classification tasks, where embeddings labeled according to whether or not they belong to a certain class of things (animal, group, mammal, and on), and multiclass classification tasks. For speed, downsample the WordNet embeddings to 1,000 randomly-sampled points without rebalancing the classes. The exact same sample is seen by all classifiers. Each classifier evaluated across 10 seeds using 5-fold vross-validation.
Results. The results for the WordNet experiment are shown in Table These results continue to be very favorable for HYPERDT and HYPERRF: HYPERDT beats Skleam and HORORF 8 times each, and HyPERRFbeats Sklearn 6 times and HORORF 8 times, all with statistical significance. No other models achieved statistically significant advantage against any other models.
23

---

Decision Trees
Random Forests
SCIKIT- LEARN
SCIKIT- LEARN
Data
HYPERDT
HORORF
HYPERRF
HORORF
Animal
98.88
98.69
96.02
98.97
98.16
96.22
Group
94.65#1
94.06
91.77
94.641
94.23
92.34
Mammal
99.86
99.33
98.92
99.87
99.19
98.92
Binary
Occupation
99.58
99.49
99.64
99.61
99.66
99.69
Rodent
99.83
99.78
99.79
99.81
99.85
99.85
Solid
99.11
98.72
98.55
99.13
98.50
98.45
Tree
98.90#1
98.59
98,46
99.01
98.68
98.63
Worker
98.69
98.36
98.57
98.73
98.58
98.57
Same level
98.10F1
97.33
96.98
98.31
96.91
96.71
Multi
Nested
89.44
87.74
77.19
89.72
89.22
86.36
Both
96.38
95.60
91.22
96.67
94.33
91.13
Table 5: Mean micro-F1 scores for classification benchmarks over 10 seeds and 5 folds. The highest- scoring decision tree and random forests are bolded separately. means predictor beat HYPERRF, i means predictor beat HORORF, and f means a predictor beat SCIKIT-LEARN, with < 0.05.
A.6.6 MIDPOINT ABLATION
Because the use of the midpoint formula laid out in Equation I0 was guided by intuition rather than actual performance, a worthwhile experiment is to check the effect that substituting this operation with the naive midpoint calculation has on the accuracy and efficiency of our algorithm.
Procedure. We test the effect of substituting the geodesic midpoint calculations with naive mid- point calculations across 10 seeds and a single train-test split. We check this for 100, 200, 400, and 800 points and 2, 4, 8, and 16 dimensions, recording total runtime and Fl-micro score on the held-out test set (20% of the sample).
Results. Figure g shows the results of the midpoint ablation study. Across almost all sample sizes and dimensions, substituting the naive midpoint computation resulted in a marked reduction in accuracy-although with the benefit of slight reduction in runtime. We believe that only is this eeouracy-performanee tradeoff favorable to the more complicated midpoint computation, it is also theoretically more justified (all things being equal, you should prefer place the decision boundary exactly in between two differing classes). Thus, we elect to keep the midpoint computation as it is.
A.7 STATISTICAL TESTING
For the benchmarks reported in Table I we provide statistical significance annotations. To test statistical significance, used two-tailed paired /-test comparing Fi scores 10 seeds and folds. Each combination of dataset, dimension, and sample size was tested separately. We used threshold of p 0.05 on this test determine statistical significance, and assigned the significance annotation to the predictor with the higher mean. We report full p-values in Table
24

---

Score
Time
F1-micro
Time (s)
0.6
0.5
midpoint
ablated
midpaint
ablated
Type
Type
Ablation effects by dimension, sample size
1.0
0.9
F1-micro
0.8
0.7
midpoint ablatee
200
4001
8000
2003
600)
100000
18. 2000
(8. 4003
18. 8000
(16, 2003
(16, 200)
(16. 4003
(16. 8003
(#Dimensions, #Samples)
Figure 8: Ablation results for midpoint angle computations.
25

---

DT vs
DT HoroRF
HoroRF vs HYPERDT
RF HYPERRF
RF vs
HoroRF vs
Dataset
D
n
HYPERDT
HoroRF
HYPERRF
2
100
.044
4.56e-03
.027
.368
3,92e-03
1.16e-03
200
.545
.053
5.88e-04
.60
1.39e-04
.092
400
4.75e-03
4.86e-03
6.10e-05
.867
6.71e-07
4.41e-05
800
1.52e-03
3.02e-04
1.05e-06
.600
1.14e-10
2.55e-07
100
.067
.358
8.29e-05
1.00
9.91e-06
.417
200
.036
6.50c-03
3,98c-05
.705
1.58c-07
.025
Gaussian
400
7.02c-03
5,43c-03
5.95c-03
.144
7.62c-07
4.90c-03
800
4.29e-03
6.03e-04
.034
.062
5.19e-05
2.80e-03
100
.709
.420
2.17e-03
.222
.233
.083
200
8211
.766
1.14--03
.766
9.18e-04
1.00
400
.785
.569
.012
.533
.011
1.00
800
.133
.103
2.41e-03
.598
3.83e-04
.598
100
2611
.400
.146
1.00
.032
.200
200
.322
.699
.011
.611
.028
.322
400
.322
.182
.159
.044
.159
800
.033
.096
2
100
.236
.160
.014
.577
2.37e-03
.824
200
.037
8.32c-03
1.14e-05
.138
1.54e-06
.912
400
.010
8.82e-06
6.84e-10
.894
9.78e-11
.048
800
.878
1.25e-08
1.77e-10
.807
2.86e-10
4.56e-03
100
.709
.055
3,45c-17
3.34e-05
3.30c-17
2.02e-07
NeuroSEED
200
.322
7.99e-05
2.57e-24
1.61e-11
3.05e-24
9.19e-15
400
.159
2.75e-05
2.53e-24
6.10e-21
2.86e-24
6.94e-23
800
.322
2.00c-10
1.12c-26
5.07c-20
1.22c-26
2.71e-24
100
.533
7.92c-03
2.65e-14
3.44e-10
2.47c-14
1.60e-05
200
.622
6.27e-04
3.62e-20
8.01e-20
1.82e-19
4.50e-15
400
.229
5.28e-08
4.62e-26
6.56e-32
8.02e-26
4.90e-27
800
1.00
6.99e-13
7.88c-37
9.02e-36
6.65e-37
1.65e-33
16
100
.322
.595
2.98e-07
.061
3.40e-08
.123
200
.279
.880
4.98c-07
.213
2.02e-07
.180
400
.569
2.00c-03
6,56e-08
.120
4.82c-08
1.47c-04
800
.659
1.26c-03
1.40e-14
.114
1.62e-14
2.57e-07
Polblogs
979
.118
.511
1.23e-05
2.38e-05
9.15e-07
4.50e-06
4 979
160
.696
2.05e-07
1.68e-03
6.26e-08
1.63e-03
979
.047
.301
1.11e-12
2.48e-10
1.87e-11
6.43e-10
16
979
.987
3022
2.34e-10
3.64e-09
8.29e-11
1.65e-07
Table 6: Paired t-test values for benchmarks 5 folds and 10 seeds. Missing values indicate that two sets of F, scores were identical. Statistically significant values are used to generate cell annotations in Table
26


Reviews:
[{"review_id": "GMIPBaXK4B", "reviewer": "Reviewer_ZUYY", "summary": "The paper presents an extension of standard decision trees to the data situated in hyperbolic spaces. Certain types of data are better modeled by sets of recursive splits (decision trees), and also currently there is a growing attention to data analysis in hyperbolic spaces, due to development of hyperbolic embedding models. While there was HoroRF, a way to recursively split data in hyperbolic space, the proposed approach uses a different spliting model that is much simpler to operate and train, and this finding contains a valuable theoretical insight. Practically it also outperforms previously available methods.", "questions": "- Considering the proposed method and HoroRF, we know two ways of splitting the hyperbolic space, which correspond to an inductive bias that we impose on the data. Are there any other inductive biases / splits that can be considered, but perhaps are currently infeasible or otherwise unsuitable?\n- Particularly, there is an inherent asymmetry of the hyperbolic space towards the center of the Poincare ball - and embeddings usually automatically (without being instructed to do so, during regular optimization) utilize this asymmetry to represent well the hierarchical data. Can we use this asymmetry in designing the splitting method?\n- Following from the previous question, consider the following baseline (should be worse than directly working in hyperbolic space, but better than the straightforward use of regular decision trees):\n-- Transform the data into the Poincare ball. After that, ignore the hyperbolic nature of the data (as in regular decision trees) and transform the data into spherical coordinate system. Now run the regular decision tree on such data.\n-- In this baseline the splits will be concentric spheres which are further split into spherical sectors and sub-sectors.\n-- Would be nice to see a comparison between proposed approach and some approach (such as suggested above) that lies in between the Hyperbolic Trees and Regular Decision Trees.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The paper significantly advances the sub-field of decision tree models for hyperbolic spaces by presenting a novel decision tree model, that produces the splits in a different way, compared to previous state of the art, and leads to asymptotically faster computation times and better practical evaluation.", "weaknesses": "What is lacking in my opinion is a theoretical analysis of different decision boundaries and their performance for certain kinds of data (certain kinds of distributions of the data, that we may consider natural in certain classes of problems). For example, in case of regular decision trees, it may be observed that tabular data (where regular decision trees are best performers) is usually situated on axis-parallel hyperplanes and is easily separated by similar axis-parallel splits (due to naturally repeating nature / distribution of the data in tables along some dimensions)\n\nThe paper contains an interesting (and possibly simple to further analyze) case of synthetic data in hyperbolic space consisting of a sample from a mixture of Gaussians. It was observed empirically, that proposed method consistently outperforms the previous HoroRF/HoroDT. Providing a theoretical analysis of why it is the case would fill in the gaps and justify a choice of the proposed subset among all possible decision boundaries in hyperbolic space.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NrncJRmjQw", "reviewer": "Reviewer_RLmq", "summary": "This paper proposes a decision tree algorithm: HYPERDT. It leverages inner products to adapt Euclidean decision tree algorithms to hyperbolic space by characterizing Euclidean decision tree algorithms in terms of inner products, offering a natural modification of these algorithms to hyperbolic space. This approach works for all negative curvatures and eliminates the necessity for pairwise comparisons between data points. HYPERDT eliminates the need for computationally intensive Riemannian optimization, numerically unstable exponential and logarithmic maps, or pairwise comparisons between points by leveraging inner products to adapt Euclidean decision tree algorithms to hyperbolic space.", "questions": "Please refer to Strengths and Weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Novelty: The paper introduces a novel approach to decision tree algorithms by extending them into hyperbolic space. This is a new and innovative idea that has not been explored extensively in the machine learning community.\n\n2. Performance: The authors demonstrate that hyperbolic decision trees and random forests can outperform their Euclidean counterparts in certain scenarios. This suggests that hyperbolic geometry has the potential to improve the performance of machine learning algorithms.\n\n3. Clarity: The paper is well-written and easy to understand, even for readers who are not familiar with hyperbolic geometry. The authors provide clear explanations of the concepts and algorithms presented in the paper.", "weaknesses": "However, I have the following concerns:\n1. All datasets seem to be better suited for the algorithm proposed by the authors. The authors do not provide the performance of the algorithm for other different types of datasets.\n2. How about the deeper tree (T>3 or even 7)? \n3. What is the scalability of the algorithm? The author only tested the datasets of samples within 1000 and dimensions within 16. \n4. There are many other new decision tree training algorithms proposed these years. What is the performance of HYPERDT when compared with other advanced decision tree algorithms? (e.g., [1], [2])\n\n[1] McTavish, H., Zhong, C., Achermann, R., Karimalis, I., Chen, J., Rudin, C., & Seltzer, M. (2022, June). Fast sparse decision tree optimization via reference ensembles. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 36, No. 9, pp. 9604-9613).\n\n[2] Lin, J., Zhong, C., Hu, D., Rudin, C., & Seltzer, M. (2020, November). Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning (pp. 6150-6160). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N7tTFGobfc", "reviewer": "Reviewer_71Gr", "summary": "The paper considers the task of creating decision tree models for hyperbolic data. To do so, the splitting rule for axis-aligned (parallel) splits is considered as the function of an inner product and thus a hyperplane. To translate decision trees to the hyperbolic geometry, the equivalent inner product and hyperplanes are used to define a hyperbolic decision boundary. This approach is utilized to create a random forest-style algorithm and is tested on various hyperbolic datasets.", "questions": "\"Parameterizing Decision Boundaries\"\n\nI find that the stated motivation and reasoning for Eq. (11) & (12) unclear. This further extends to the corresponding appendix sections:\n\n- Language in the description of Eq. (11) seems imprecise. \"... the hyperplane parameterized by $d$ and $\\theta$ will intersect $\\mathbb{H}^D$ at: [ Eq.(11)]\". This seems to suggest there is only one point of intersection. I assume that the point characterized by Eq (11) is the closest point to the origin in said intersection?\n- As a general suggestion, it may be useful to the reader to have both Eq. (7) and Eq. (11) in Figure 1.\n- In the set up of Appendix A.2, a vector $\\mathbf{u}$ is defined. It is unclear exactly what this is. From the combined definition in A.2.2 and Eq. (24), I believe that it is a unit vector pointing in a spacelike direction? What exact is its role?\n- I am unsure how you went from Eq. (24) to Eqs. (25-27). From what I am guessing, $\\mathbf{u}$ defines the direction of the intersecting geodesic, but I am unsure about the \"\\sinh\" parameterization given.\n- What is the connection between dimension $d'$ in Eq. (12) and the normal vector characeterization of Eq. (8/9)?\n\nOther questions:\n\n- Although the construction of the decision boundaries follows from their Euclidean axis-aligned counterparts, can the construction be generalized for any hyperplane (intersecting with the $\\mathbb{H}^D$)? How would this change generating the decision boundary? Especially due to fact that the assumption of letting dimension except for 0 and d being zero is used to generate the hyperplane characterization.\n- Following from the above, why is Eqs. (25-27) restricted to having the geodesic follow an axis $d'$?\n\nMinor:\n- Eq. (10), \"cos\" missing \"\\cos\"", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The visual presentation is very good. Figures 1 & 2 provide a nice intuition on how axis-align splits are generalized to the hyperbolic regime.\n- The simplicity of the approaches mechanism for lifting decision trees to hyperbolic geometry allows for an efficient alternative than prior baselines (further explored in the experimental setting).\n- Competitive empirical results showing its practicality.", "weaknesses": "- Some sections on parameterizing decision boundaries are unclear. (See questions below)\n- It maybe worth adding explicit clarification in the contributions that the data input for HyperDT are hyperbolic data / representations, ie, a separate embedding process is needed to apply such a model to Euclidean data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AItqozjjK7", "reviewer": "Reviewer_nNVW", "summary": "This paper presents a extension of traditional Euclidean decision tree algorithms to the hyperbolic space. The proposed method HyperDT is of constant-time decision complexity while mitigating the scalability issues of Euclidean decision tree. The paper further extends HyperDT to random forests tailored for hyperbolic space. The proposed methods HYPERDT and HYPERRF show state-of-the-art accuracy and speed on classification problems compared to existing counterparts on various datasets.", "questions": "Ref. Weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1) Extending decision tree to hyperbolic space is of great importance as both hyperbolic space and decision tree algorithm have their own advantages. \n\n2) The proposed method, compared with previous counterparts, maintains constant time decision complexity.\n\n3) A implementation adhering to standard SCIKIT-LEARN API conventions.\n\n4) The presentation and organization of the paper is overall good.", "weaknesses": "1) It is unclear why using geodesics as decision boundary is better than using horospheres as used in [1].\n\n2) Although the main goal is to generalzie decision tree to hyperbolic space, the paper lacks some comparisions agaist previous classification methods likes hyperbolic logistic regression and hyperbolic SVM. Without sush comparision, it is not clear whether the proposed hyperbolic decision tree has enough advantages compared with other classifiers. \n\n\n[1] Lars Doorenbos, et al. Hyperbolic random forests. Arxiv 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VUgzMLwtHF", "reviewer": "Reviewer_uhLf", "summary": "The paper introduces a novel extension of the Euclidean CART algorithm into the hyperbolic space, aptly named HyperDT. This extension involves a transformative shift from axis-aligned decision planes to geodesic submanifolds and replaces candidate thresholds with equidistance mid-angles. Notably, other components of HyperDT, including objective functions, remain consistent with the traditional CART framework. This adaptation allows HyperDT to achieve a similar asymptotic complexity as CART. Furthermore, the authors present another contribution in the form of HyperRF, a random forest model built upon the foundations of HyperDT. The paper showcases the good performance of these methods across a spectrum of datasets, including synthetic datasets like Gaussian mixtures, as well as real-world data sources such as biological sequences and graph embeddings. These empirical results underscore the effectiveness and versatility of the proposed techniques.", "questions": "1. In Section 3.2, the authors mentioned that the interpretation of axis-aligned hyperplanes within the hyperboloid model is unclear. Can the authors provide a more detailed explanation of why the use of axis-aligned hyperplanes lacks clarity in this context? I am considering that any geodesic could potentially be represented by two axis-aligned or oblique planes, making the use of axis-aligned planes reasonable.\n    \n2. Additionally, does the geodesic boundary offer advantages beyond classification scores and interpretation? One potential advantage I am considering is that geodesic trees may require fewer nodes compared to axis-aligned trees to achieve similar classification scores. Could the authors include metrics, such as the average number of nodes used in the experiments presented in Table 1, to support this claim?\n    \n3. For a more comprehensive evaluation, could the authors include additional comparison results? As mentioned in the weaknesses section, there are now several global optimization methods, such as [1], that have demonstrated superior performance compared to CART. It would be valuable to include a comparison with at least one of these methods to illustrate the superior performance of geodesic decision boundaries over axis-aligned boundaries.\n    \n4. Ablation experiments: The paper lacks ablation studies or experiments to justify the design choices made in the proposed methods, including the selection of candidate hyperplanes. Since the equidistance mid-angles in the proposed method do not have closed-form solutions and rely on numerical solvers, there may be concerns about the algorithm's efficiency. It would be informative to compare the performance and execution times of the equidistance mid-angles with those of naive mid-angles to assess the impact of these choices on the methods' performance and behavior.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The utilization of a CART-like structure in the proposed methods greatly enhances efficiency, a feature that has been substantiated through a comparison with previous works like HoroRF.\n    \n2. The paper excels in presenting a lucid and methodical derivation of the proposed techniques. It ingeniously adapts Euclidean decision tree algorithms to the hyperbolic space by leveraging inner products. Additionally, the paper offers insightful closed-form equations for the decision boundaries and provides an in-depth explanation of the candidate hyperplane selection process.\n    \n3. Another notable aspect of the paper is its commitment to practicality. The authors have thoughtfully offered a Python implementation of the methods, aligning with the conventions of the scikit-learn API. This effort to bridge theory and practical application enhances the paper's value and accessibility to the research community.", "weaknesses": "My primary concerns are related to the CART-like design employed in the paper. As CART is known for its top-down, greedy approach, it tends to yield suboptimal solutions [1]. It is essential to acknowledge that the proposed method may also encounter this suboptimal behavior due to its similarity to CART. For additional concerns, please refer to the questions section.\n\n[1] Mazumder, Rahul, Xiang Meng, and Haoyue Wang. \"Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features.\" *International Conference on Machine Learning*. PMLR, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)