Hyperbolic Random Forests
Authors: Lars Doorenbos
Pablo Márquez Neila
Raphael Sznitman
Pascal Mettes
Venue: Accepted by TMLR ()

Abstract: Hyperbolic space is becoming a popular choice for representing data due to the hierarchical structure - whether implicit or explicit - of many real-world datasets. Along with it comes a need for algorithms capable of solving fundamental tasks, such as classification, in hyperbolic space.
Recently, multiple papers have investigated hyperbolic alternatives to hyperplane-based classifiers, such as logistic regression and SVMs. While effective, these approaches struggle with more complex hierarchical data. We, therefore, propose to generalize the well-known random forests to hyperbolic space.
We do this by redefining the notion of a split using horospheres. Since finding the globally optimal split is computationally intractable, we find candidate horospheres through a large-margin classifier. To make hyperbolic random forests work on multi-class data and imbalanced experiments, we furthermore outline new methods for combining classes based on the lowest common ancestor and class-balanced large-margin losses. Experiments on standard and new benchmarks show that our approach outperforms both conventional random forest algorithms and recent hyperbolic classifiers.

Published in Transactions on Machine Learning Research (05/2024)
Hyperbolic Random Forests
Lars Doorenbos University of Bern
lars.dooveeboss@hmiie..cc ch
Pablo Márquez-Neila University of Bern
pablo.marqqezz@umiee..d
Raphael Sznitman University of Bern
Pascal Mettes
p.s.m.medtes@uww..t
University of Amsterdam
Reviewed on OpenReview: https: // openreview. net/ forum? id=pjKcIzuXiR
Abstract
Hyperbolic space is becoming popular choice for representing data due to the hicrarchi- cal structure whether implicit or explicit of many real-world datasets. Along with comes a need for algorithms capable of solving fundamental tasks, such as classification, in hyperbolic space. Recently, multiple papers have investigated hyperbolic alternatives to eeperplane-baseee classifiers, such logistic regression and SVMs. While effective, these approaches struggle with more complex hicrarchical data. We, therefore, propose to gen- eralize the well-known random forests to hyperbolic space. We do this by redefining the notion of a split using horospheres. Since finding the globally optimal split is computa- tionally intractable, we find candidate horospheres through a large-margin classifier. To make hyporbolic random forests work on multi-class data and imbalanced experiments, we furthermore outline new methods for combining classes based on the lowest common ances- tor and class- balanced large-margin losses. Experiments standard and new benchmarks show that our approach outperforms both conventional random forest algorithms and recent. hyperbolic classifiers.
1
Introduction
Machine learning in hyperbolic space is gaining more and more attention, and hyperbolic representations of data have already found success in numerous domains, such as natural language processing (Nickel & Kiela Khrulkov et al. 2020 Ghadimi Atigh et al. 1, graphs (Chami et al.) 2019 Liu et al.) 2019 Sun et al. 2021b), recommender systems {Sun et al, 2021 and more. Hyperbolic space is a natural choice for data with a hierarchical structure due to the fact that the available space grows exponentially when moving away from the origin. Therefore, it can be seen
2017 Tai et al. 2022) computer vision (Ahmad & Lecue 2022
2021
as continuous version of a graph-theoretical tree (Nickel Kiela 2018).
With the rise of datasets embedded in hyperbolic space comes need for algorithms that can successfully operate them (Cho et al. 2019). As result, many methods specifically designed for hyperbolic space
have been proposed that tackle a variety of machine learning tasks, such as clustering (Monath et al. 2019
regression [Marconi et al.] 2020). and classification (Ganea et al. 2018b Chien et al. 2021 Cho et al.
2019
Pan et. al. 2023 Weber el. al. 2020
Current hyperbolic classification algorithms, such as hyperbolic support vector machines Fan et al. or hyperbolic logistic regression (Ganea et al., (2018)). have shown promising results, but still struggle with complex datasets. In Euclidean space, there is a long history of success of tree-based random forest algorithms
2023

---

Published in Transactions on Machine Learning Research (05/2024)
(a)
(b)
(c)
Figure 1: Motivation for hyperbolic random forests. Two splits of (a) an axis- Euclidean, (b) an oblique Euclidean, and (b) hyperbolic decision tree of depth two. The data is a continuous embedding of tree split into three nested classes. The inductive biases of linear decision boundaries are inappropriate for efficiently capturing the underlying geometry, and more splits are needed to be effective.
in this regard, and they remain among the most popular learning algorithms for many data types (Caruana & Niculescu-Mizil 2006 Fernández-Delgado et al. 2014). We argue that decision trees and, by extension, random forests are well-suited for hyperbolic space due to their shared hierarchical structure. Figure [ illustrates the need for classifier that fits the underlying geometry and the benefits of hyperbolic tree- based classifier. Euclidean hyperplane splits (Figure 1 (a/b)) are ineffective at capturing the structure of the data. In contrast, our hyperbolic splits (Figure [c)) are more appropriate, where the nested splits clearly show how the smallest green class is a subclass of the larger orange one.
Trec-basod algorithms are built by recursively applying a splitting function; hence, to generalize the concept of a tree-based classifier to hyperbolic space, we need define hyperbolic splitting function. For this purpose, we propose to horospheres, which share several desirable properties with the hyperplanes used in Euclidean trees. Due to combinatorial explosion, finding the optimal horosphere by enumeration is computationally intractable. We propose to tackle data splitting as a binary horosphere classification task. To deal with multiple classes in a hierarchically consistent. manner, we exlend our splitting operator using hyperclasses. We show how to obtain hyperclasses through clustering in hyperbolic space with the lowest common ancestor. We also outline a class balancin large-margin loss for dealing with long-tailed data.
We extensively evaluate our approach on canonical benchmarks from previous works on hyperbolic clas- sification. Additionally, we introduce three new multi-class classification experiments. We show that method is superior to both competing hyperbolic classifiers as well as their Euclidean counterparts in these settings. Summarized, our contributions are (1) generalization of random forests to hyperbolic space using horospheres, dubbed HoroRF, (2) two extensions to enable effective learning in multi-class and imbalanced settings, and (3) a thorough evaluation HoroRF, showing its advantago over other methods, both Euclidean and hyperbolic.
2
Related Work
2.1 Hyperbolic machine learning
Machine learning in hyperbolic space has gained traction due to its inherent hierarchical and compact nature. Foundational work showed that hyperbolic space is superior to Euclidcan space for embedding hicrarchies in a continuous space, allowing for embeddings with minimal distortion (Nickel & Kiela 2017 Ganea el al., 2018a). Empowered by these results, learning with hyperbolic embeddings has recently been successfully used for various problems. Chami et al. (2019) and Liu al. (2019) showed how to generalize graph networks hyperbolic space, while Tifrea al. (2019) showed the potential of hyperbolic word embeddings. In the visual domain, hyperbolic embeddings have been shown to improve image segmentation (Gaadii Atigh
2

---

Published in Transactions on Machine Learning Research (05/2024)
et al.
2022 zero-shot recognition Liu et al. 2020), image-text representation learning (Desai et al. 2028
and more. Hyperbolic embeddings have also been effective for biology (Klimovskaia et al. 2020) and in recommender systems (Sun et al. 2021a). We refer to recent surveys for more complete overview Peng
ct al.
2021 Yang et al.
2022 Mettes et al. 2023
For classification specifically, various traditional classífiers such as logistic regression (Ganea et al. 2018b),
neural networks (Ganea et al. 2018b Shimizu et al., 2021 van Spengler al., 2023), and support vector ma-
chines (SVM) (Cho et al., 2019 Fan et al. 2023 Fang et al. 2021 Weber et al. 2020 now have counterparts
in hyperbolic space. In this work, we strive to go beyond single hyperplane/ gyroplane decision boundaries
per class and bring random forests to hyperbolic space.
Our method is built on the concept of horospheres, which are the level sets of the Busemann function to ideal points. Ideal points have recently succeeded multiple areas, such as supervised classifica- tion (Ghadimi Atigh et al. (021)) and self-supervisod learning (Durrant & Lcontidis 2023). Horospheres, particular, have found applications in dimensionality reduction (Charni al.) 2021p. : as well as generalizing SVMs (an et al. 2023 and neural networks (Sonoda et al., 2022 to hyperbolic space, but are the first
to use them building blocks for random forests. Concurrent with our work, Chlenski et al. (2023) also propose hyperbolic random forest model where they rely on geodesics rather than horospheres and work in the hyperboloid model of hyperbolic space instead of the Poincaré disk model.
2.2 Random Forests
Random Forests remain a popular choice of classifier to this day due to their high performance, speed, and insensitivity to hyperparameters (Grinsztajn et al. (022). In their original paper (Breiman) 2001), two versions of random forests were proposed: one with axis-aligned splits based on a single feature and one with oblique splits based on linear combinations of features. While the optimal axis-aligned split can be found by exhaustive search, finding the optimal oblique split is NP-complete (Heath et al. 1993 As result, many works have developed heuristics to find good oblique splits in a reasonable time.
One line of work makes use of meta-heuristies such as hill climbing (Murthy et al. nealing Heaath et al. 1993,, or genetic algorithms (Cantá-Paz & Kamath, 2003). Other approaches train one or more binary classifiers at every node, choosing among the resulting hyperplancs to split the data. Examples include using linear discriminant analysis, ridge regression (Menze et al. 2011], or support vector machines (Do al.) 2210).. For multi-class cases, typically, heuristics are employed to partition them into two hyperclasses (Katuwal & Suganthan, 2018). We follow the binary classifier approach for our hyper- bolic random forests and introduce hyperclass heuristic specifically designed for hyperbolic space based hierarchical clustering Chami et al. 2020)
1993), simulated an-
3
Hyperbolic Random Forests
3.1 The Poincaré ball model
We follow the convention from previous works using horospheres (Chami et al. 2021 Fan et al. 2023 and
hyperbolic machine learning more broadly (Ganca et al.] 2018b Khrulkov et al. 2020 Chien al. 2021
Shimizu al. 2021) and make use of the Poincaré ball model of hyperbolic space. The Poincaré ball model
is defined by the metric space (B,, gB) for given negative curvature c, which we set to 1 throughout this work, where
BT = fx R": |||| < <1}
(1)
with || the standard Euclidean norm, and
d = |x
(2)
From here on, we will omit the curvature subscript for clarity. The distance between two points is given by
(1 + 2
||a
bl 2
dg(a, b) = arcosh
(1
(3)
11
bb
3

---

Published in Transactions on Machine Learning Research (05/2024)
which is the length of the geodesic connecting them. Extending geodesics to infinity in one direction leads to a point on the boundary of the Poincaré ball. These points on the boundary are known as ideal points. The set of all ideal points thus lies on the hypersphere S and they can be interpreted as directions in hyperbolic space (Chami et al. 2021
3.2 HoroRF
To generalize random forests to hyperbolic space, we require a way to split data points recursively for any number of classes, regardless of the class frequency distribution, into two partitions with low impurity. Euclidean space, this splitting function outputs hyperplanes to split the data. For hyperbolic random forests, we propose to use horospheres.
3.2.1 Formalization
Horospheres are the level sets of the Busemann function (Busemann 1955) which calculates the normalized distance to infinity in a given direction. It can be expressed in closed form in the Poincaré model:
B = log |w x
(4)
|x|
As a result, horospheres ww are parameterized by an ideal point w E Sn~1, and a distance to that point E R, which is the radius of the horosphere. Our goal to find the optimal horosphere Tw. that minimizes the impurity of the resulting partitions or, equivalently, maximizes the information gain. Consider node S with data {(x, w with x E B and y E Y. The optimal horosphere is given by
w arg max (S) - Lin Lout), Teech
where H an impurity measure, and Iin and lout give the impurity of the set of points inside and outside of the horosphere, respectively:
1nn Nn
11[x Bw)) < 6)),
N
Nout N
Tout
E (| 2 b)).
(6)
Here, Ni and Nout denote the number of samples inside and outside the horosphere. Similar to oblique decision trees in Fuclidean space, finding the globally optimal horosphere is computationally infeasible. As such, we need to find approximate solutions.
3.2.2 Finding approximate solutions
As is conventional in (oblique) decision tree literature (e.g., Do et. al. (2010); Menze et al. (2011 Katuwal et al. (2020)), we employ binary classifier at every node to find candidate solutions. We need hyperbolic classifier that will allow us find splits that fit the underlying geometry. Large margin classifiers based on horospheres guarantee globally optimal solution, bypassing hyperbolic hyperplane-based methods that fail to converge (Weber et al.
2020) are limited to two dimensions (Chien et al. 2021). Moreover, the state-of- HoroSVM, is based on horospheres and outperforms hyperbolic hyperplane-basse based
the-art hyperbolic SVM.
2023 For this reason, we build upon HoroSVM. For labeled dataset D = {(,, v1) H methods Fan et al.
with x; E T and yi
E
1, 1),,,, it optimizes the convex loss function
1 o; o;; = =²² + max (0, 1 - ye (uB (x,) 0))
l(u,
(7)
where
B (x) = loo - ||x||2
(8)
ww x x|
4

---

Published in Transactions on Machine Learning Research (05/2024)
Information gain: 0.07
Information gain: 0.13
NO WIRMI
NO WIR
(a)
(b)
Figure 2: Information gain from hierarchical splits. The best (a) one-versus-rest split and (b) split found with our hyperclass heuristic. We find splits with a higher information gain by considering splits where more than one class is seen as positive.
with M, E R+ and E Sm-1 The slack hyperparameter C' controls the trade-off between misclassification tolerance and margin size. Solving for HoroSVM thus results in the three parameters μt, and o. In order to transform these results into a horosphere Tw.h, we set b b= and use w directly.
We repeat the classification times a one-versus-rest setting, with K the number of classes, and compute the information gain for all resulting horospheres. We select the horosphere with the highest information gain to split. the data. We refer to this splitting procedure the HoroSplitter. While this base version of the HoroSplitter already achieves competitive results, it naturally has limited capacity to deal with imbalanced data, and the onr-versu--eest set-up limits its effectiveness in multi-class settings. Therefore, we introduce two additional components to the HoroSplitter that make it more appropriate specifically as a building block for hyperbolic decision trees.
3.2.3 Combining classes
The default HoroSplitter uses a one-versus-rest approach to deal with multi-class data. As result, it can only find one-versus-rest splits. Nonetheless, a horosphere split with a high information gain could have more than one class in cither partition. To find good splits with multiple classes while avoiding searching over all possible combinations, only the most promising combinations should be evaluated. For this, we design a heuristic that transforms the multi-class problem into a hierarchical set of binary problems by iteratively grouping classes into two hyperclasses based on their lowest common ancestor (LCA). Then, these binary combinations added to the pool of mne-versus-rest experiments and evaluated for their information gain.
Recall the connection of hyperbolic space to graph-theoretical trees. In tree, similar leaf nodes lie in a small subtree and have their LCA at a high depth. In contrast, dissimilar nodes will have their LCA close to the root of the tree. We exploit the analog of this property in hyperbolic space to cluster together the most similar classes first, as similar classes are likely to be capturable by a single horosphere.
We represent each cluster by its hyperbolic mean. As computing the average in the Poincaré model in- volves the computationally expensive Fréchet mean (Lou et. al. 2020), use the Einstein midpoint after transforming the data to Klein coordinates instead. Specifically, data is transformed into Klein space K with
2xB
Xg
(9)
1+
Xp
and we compute the average by for class y using
Σ [y)= 7/33;
by
(10)
ΣM Ni
5

---

Published in Transactions on Machine Learning Research (05/2024)
175
175
125
1.25
0.75
0.75
025
0.25
Figure 3: Importance of class balancing. The optimal solution on a binary classification problem found (left)) without and (right) with class-balancing. The left horosphere has large negative b and does not split the data. In contrast, the right horosphere has higher loss but positive information gain. Class labels are given by marker shape. The points and color bar are colored by loss; the background is colored by distance to the horosphere.
where /1 Afterward, the mean is transformed back to the Poincaré ball with
XK
XB
(11)
1+
1
x 2
We compute all pairwise similarities and iteratively group the two most similar classes together, where the similarity is based on the LCA of the means of the two classes. The LCA for two points in hyperbolic space
is the point that is closest to the origin on the geodesic between them (Chami et al. 2020). As a result, the distance of the LCA from the origin can be seen as a similarity measure. Given two means Φ and Φj, we can calculate their similarity by
sim Φ,) Saah -1
"VVR 12 +1 (V -R)
(12)
with
R= /
12 + 1
2 (osta))
)
(13)
2// cos(a)
and
| Φb 2 1)
b0b |(| = cos(())
= tan
(14)
(0)
where 0 is the angle between Φ and Φj. We repeat this until only two hyperclasses left, for K - 2 iterations total. As result, we only evaluate K + K 2 horospheres per node. We show example where evaluating hyperclasses is beneficial in Fig. 2
3.2.4 Imbalanced data
SVM-based methods are known to behave poorly on imbalanced data, and HoroSplitter is no exception. We address this by proposing class-balances version of the poroSplitter. Specifically, the problem comes from equation 7 finding an optimal solution that does not split the data and has an information gain of zero as a result. As an example, consider the binary problem in Figure 3 The optimal horosphere has its ideal point on the top of the Poincaré ball, a μ very close to 0 and very close to 1; a result of the loss, in the case of large imbalance, almost reducing to the degenerate form
N
Linbsllanced (1,, w, D
max(0, (0, 1 v.).
(15)

---

Published in Transactions on Machine Learning Research (05/2024)
We remedy this limitation by incorporating class-balancing into HoroSplitter's loss function (Cui et al, 2019h. We rewrite the loss function in equation 7
N
1 L(u, w. D) = +
1-8 Bmy
max(0, 1- y: (x:) - o)),
(16)
1=1
where My gives the number of training samples belonging to class y and is a hyperparameter. By adding more emphasis on the loss for samples of the minority class, we can find horospheres that split the dała even in imbalanced cases.
Training and inference We build horospherical decision trees (HoroDT) by repeatedly applying the HoroSplitter. This process is repeated until all nodes are pure, i.e. contain one class, or a stopping criterion is met. Example stopping criteria include stopping when a node reaches a certain number of samples or no split with an information gain higher than a threshold can be found. By combining multiple HoroDTs into an ensemble, we form horospherical Random Forest. (HoroRF). Each tree is trained on randomly sampled (with replacement) subset of the data, and subsample of the features is considered every split. Predictions are made by majority vote among the HoroDT's.
4 Experiments
4.1 Datasets
We evaluate HoroRF on two canonical hyperbolic classification benchmarks: WordNet subtree and network node classification (Cho et al.] 2019 Fan et al., 2023). Additionally, we introduce three new multi-class WordNet experiments, which will detail first.
Multi-class WordNet We propose three new multi-class WordNet experiments aimed at evaluating three distinct qualities. In the first experiment, the task is to classify samples into one of multiple subtrees with the same parent. In the second experiment, we pick nested subtrees, and samples must be classified into the smallest subtree they belong to. The third experiment combines the previous experiments with nested classes of multiple subtrees. Unlike previous benchmarks, these are difficult multi-class experiments on large, imbalanced datasets. We provide the full details of the experiments in the appendix. The datasets are split into train, validation, and test sets with a ratio of 60:20:20. A hyperparameter search is done on the validation set, and the macro-f1 score over three trials on the test set is reported.
WordNet We run binary classification experiments on the nouns of WordNet (Fellbaum 2010). embedded into hyperbolic space using hyperbolic entailment cones (Ganea et al. 2018a). The goal is to identify whether sample belongs to a semantic category (i.e., a subtree of the hyperbolic embeddings). Following (Fan ct al., 2023 , we split the data into 80% for training and 20% for testing and report the best results from grid search over three runs in AUPR. We find that three of the larger subtrees lypically used for these experiments (animal n. 01, group. n. 01, mammal. .n. 01) can be solved near-perfectly with random forests, both Euclidean and hyperbolic. Therefore, we add experiments on two additional subtrees, occupation n. 01 and rodent.. n. 01, which are smaller and more difficult subtrees for classification purposes.
Networks We node classification experiments on four network datasets embedded into hyperbolic space. These networks are (1) karate (Zachary 1977p network of 34 members of karate club split into two factions, (2) polblogs AAdaiic & Glance] 2005), a netw of 1224 hyperlinks in political blogs split into two communities, (3) football (Girvan & Newman 2002), a network of 115 colleges linked by football games split into 12 Icagues, and (4) polbooks a network of 105 books split into three affiliations.
We use the public embeddings provided by Cho et al. 2019 Fach dataset has five sets of embeddings obtained using the method of Chammerraiin al. (2017). Following previous work (Fan et al. 2023)), we run grid search with 5-fold stratified cross-vallle pross-validation and report the best average micro-fl score over five seeds, using a different embedding for each seed.
httt:://www-persoot/ ummchh.dd mejn/ mninn/netdtaa/

---

Published in Transactions on Machine Learning Research (05/2024)
4.2 Evaluation
Baselines We evaluate HoroRF against six baselines, split into two categories. The first set covers hy- perbolic classifier basclines, namely hyperbolic multiple logistic regression (HypMLR: Ganea et al. (2018b)) and the state-of-the-art hyperbolic SVM, HoroSVM (Fan et al., 2023). The second set of baselines comprises Euclidean counterparts of the hyperbolic classifiers, namely a linear SVM (LinSVM), an SVM with an RBF kernel (RBFSVM; (Cortes & Vapnik, [995)), ), an axis-aligned random forest (RF) (Breiman 2001 and an oblique random forest (ObIRF) with a similar sct-up to HoroRF. The ObIRF uses a cost- balanced linear SVM to find optimal splits (see e.g. (Do et al., 2010)). If the SVM fails to converge, il defaults to using the best axis-aligned split. It finds hyperclasses by iteratively merging the two classes with the closest means.
As is common practice (Cho al. 2019 Fan et al 2023), the Euclidean basclines are on the same embeddings as the hyperbolic methods, which we also find to perform better compared to mapping the embeddings back to Euclidean space first. Moreover, as the SVMs, HypMLR, and HoroSVM baselines are negatively affected by the class imbalance in the WordNet experiments, we report cost-balanced results on those benchmarks, where the loss is weighted inversely proportional to the class frequency.
Implementation Details We use 100 trees for all tree-based methods. We use the Gini impurity caleu- late the information gain. At every node, we sct C' to 2" where is randomly sampled from {-3, . 5). We stop splitting when node reaches a certain number of samples m. In the case of ties in information gain between possible splits, a random split is selected. If the HoroSplitter fails to converge, we choose the best horosphere from a small number of random ideal points. We set m and the class- bales-balnncing hyperparameter B via grid search. Further details are given in the appendix.
4.3 Results
WordNet The results for the WordNet subtree classification experiments are shown in Tab. [ The Euclidean SVMs are unable to handle the large imbalance in the datasets despite the loss re-weighting, The random forest approaches are better equipped to deal with this type of data. The results show that HoroRF outperforms the Euclidean tree-based methods in most cases. The differences are most pronounced in the hardest experiments, occupation and rodent, while we find the tree-based methods to perform similarly on the saturated experiments with close to perfect scores, i.e., animal, group, and mammal. Overall, HoroRF performs better than the well-known Euclidean SVMs and random forest approaches.
Compared to the hyperbolic classifiers, we find that both the hyperbolic MLR and SVM baselines struggle to deal with the imbalanced data, despite the loss re-weighting. Neither are able to match the performance of HoroRF. We arguc this is the case as real-world data cannot be distinguished with a single horosphere, but requires recursive horospherical separation as done in HoroRF. We conclude from the WordNet experiment that HorRF is a competitive classifier even in the binary setting.
Multi-class WordNet The results for the multi-class WordNet experiments are shown in Table 2 which paint a similar picture as the previous experiments. For the Euclidean methods, the outperform the SVMs, with ObIRF, on average, having a slight edge over the axis-aligned random forest. HoroRF outperforms the SVMs and axis-aligned RF in all three cases, and despite reaching an equal score in the first experiment, it outperforms ObIRF in the remaining two. Compared to the other hyperbolic classifiers, HoroRF reaches far higher performance on these complex imbalanced multi-class experiments, on which both HypMLR and HoroSVM struggle greatly.
methods
Our HoroRF outperforms the Euclidean methods in all cases, besides matching the SVMs on karate, showing that the choice of horospheres over hyperplanes results in better performance on data lying in hyperbolic space.
Networks The results on the network datasets are shown in Table 3
As for the hyperbolic methods, HypMLR is outclassod by both HoroRF and HoroSVM all cases except football. HoroSVM and HoroRF perform similarly in the binary experiments, with a slight edge for HoroRF polblogs. In contrast, for the multi-class experiments football and polbooks, HoroRF outelasses HoroSVM
8

---

Published in Transactions on Machine Learning Research (05/2024)
Animal
Group
Worker
Mammal
Tree
Solid
Occupation
Rodent
Enclidean
LinSVM
2.5=0.0
6.0+0.6
0.7+0.00
0.7+0.00
0.6++0.0
0.8++0.0
0.2+0.0
0.1+0.0
RBESVM
2.5=0.0
6.0.0.6
0.740.0
0.7.0.0
0.610.00
0.810.0
0.210.0
0.1:0.00
RF
98.6.10.2
96.610.4
70.013.1
99.310.3
75.812.0
92.51 1.2
59.811.
34.513.0
ObIRF
98.4+0.11
96.7 #0.3
73.3+1.3
98.8+0.3
76.2+3.2
92.9+1.7
65.0+2.4
38.2+0.9
Hyperbolic
HypMLR
3.2 #0.1
6.5 =0.0
1.2 #0.2
0.9 =0.0
1.3:0.8
1.0 #0.2
0.940.9
0.4 #0.4
HoroSVM
1..4+1.3
71.010.5
39.913.6
89.8+0.9
41.5+1..
63.710.9
13.0
13.612.0
HoroRF
98.5++0.2
96.6+0.4
73.4 1.7
99.3+0..4
76.6.t 3.8
93.5tt 1.3
65.6 1.5
39.0 2.4
Table Comparative evaluation on binary WordNet experiments. We follow the experimental protocol of Fan al. (2023) and report the mean and standard deviation of the AUPR over three runs. Underlined gives the best hyperbolic method, Bold denotes the best method overall. On aggregate across the experiments, HoroRF obtains the best performance.
Same level
Nested
Both
Euclidean
LinSVM
48.8 10.9
59.7 10.5
35.6 10.2
RBFSVM
80.0 #1.8
89.8 #1.1
70.8 #0.6
RF
89.710.7
91.710.3
81.511.5
ObRR
91.3++0.6
93.0+0.2
81.3+1.4
Hyperbolic
HypMLR
29.0 +4.5
57.6 #0.5
35.9 16.7
HoroSVM
50.2 +2.2
56.0 +0.7
35.2 +0.5
HoroRF
91.3110.3
93.311.11
81.9
Table 2: Comparative evaluation multi-class WordNet. We run grid search to determine the optimal configuration the validation set and report results over three trials in macro-fl score the test set. Underlined gives the best hyperbolic method, Bold denotes the best method overall. HoroRF performs best in all settings.
by 4.0 and 0.6 macro f-1, respectively, confirming the benefit of HoroRF over HoroSVM in more complex cases. Overall, we find that HoroRP is the most consistent and best-performing classifier across all benchmarks.
4.4 Ablations and Visualizations
Hierarchical Classification Hyperbolic methods have been proven successful when evaluated on wide
range of hierarchical lasks Cao et al. (2020); Ghadimi Atigh et al. 2021 Surís et al. (2021) Tifrea et al. (2019). Here, we aim to verify our hypothesis that random forests are well-suited for hyperbolic space by comparing HoroRF with other SOTA hyperbolic classifiers on hierarchical classification, with metrics explicitly designed to evaluate their success in capturing the hierarchy.
We evaluate the methods using CIFAR10 Krizhevsky al. (2009) and STL10 Coates al. 2011 using the CIFAR10 hicrarchy from Sebastian & Sebastian (2023) Note that STL10 has the same classes CIFAR10, with the only difference being the substitution of frog for monkey. As such, we maintain the hierarchy from Sebastian & Sebastian (2023) for STL10 but modify it. by removing frog and incorporating monkey into the mammal subtree.
We embed the images into 9-dimensional space by training a hyperbolic prototype ResNet-18 with prototypes uniformly distributed the hyperbole Kasarla et al. (2022) and train the classifiers on these 9-dimensional

---

Published in Transactions on Machine Learning Research (05/2024)
Binary
Multi-class
Karate
Polbooks
Football
Polblogs
Euclidean
LinSVM
95.4+22.3
92.4+0.3
33.245.1
85.5+0.9
RBFSVM
95.4+2.3
92.4+0.3
35.5+47
84.4+19
RF
94.343311
92.110.33
36.21449
85.112.1
ObIRF
94.8 12.2
92.1 10.3
36.7 12.7
84.4 113
Hyperbolic
HypMLR
93.143.4
90.9
40.242.5
81.5
HoroSVM
95.4+2.3
92.4+0.2
34.3+1.8
85.3+0.8
HoroRF
95.412.3
92.510.3
38.3118
86.11100
Table 3: Comparative evaluation on network datasets. We follow the experimental protocol of Fan
et al. (2023) and report the mean and standard deviation of the micro-fl score over five trials of f-fold stratified cross-validation. Underlined gives the best hyperbolic method, Bold denotes the best method overall. HoroRF obtains the best performance on aggregate over the datasets.
CIFAR10
STL10
Mis. Sev. (4)
HD@1 (4)
Mis. Sev. (1)
HD@1 (4)
HypMLR
60.8+1.7
10.2+0.0
54.2+2.8
22.4=0.3
HoroSVM
59.910.1
12.5+0.0
54.411.0
26.0=0.3
HorRR
58.2++0.3
9.9
53.4+:02
22.3++0.1
Table 4: Evaluating hyperbolic classifiers for hierarchical classification. We run grid search to determine the optimal configuration on the validation set and report the mean and standard deviation of the mistake severity and hierarchical distance@1 on the test set over three seeds. Bold denotes the best method. HoroRF performs best.
image features. We obtain hyperbolic embeddings for 3600 training, 900 validation, and 1000 test samples. To compare the classifiers, run grid search on the training set and select the optimal configuration based on validation performance. Then, we report the mistake severity and hierarchical distance@ 1 on the test set Garg et al. (2022). These metrics both use the LCA distance, computed by dividing the height of the LCA of the predicted and ground-truth class by the tree hoight. The mistake severity is the average of this distance for all misclassified samples, whereas the HD@1 computes the average distance for all the samples Karthik et al. (2021).
From the results in Tab. 4 HoroRF is the best hyperbolic method, confirming its ability to model the hierarchy effectively and the benefits of our generalization of random forests to hyperbolic space.
Ablating hyperclasses and balancing. We perform an ablation study to validate our choices on the football dataset. From Tab. 5 we find a large benefit in using our HoroSplitter to find splits instead of enumcrating all possible horospheres at axis-aligned idcal points. Furthermore, we show how both our hy- perclass and class-balancio balancinn additions improve upon the base HoroSplitter, and their combination enables to reach the best performance.
Visualization & synthetic evaluation We build a synthetic datasel following Ganea el al. (2018a) by creating a synthetic tree of depth six with a branching factor of four and embedding it into hyperbolic space with hyperbolic entailment cones. We then partition the nodes into five classes from two depths. Using this dataset, we visualize the splits HoroRF, HoroRF without hyperclasses class- bass-balanning, ObIRF on the hyperbolic embeddings, and ObIRF the Fuclidean embeddings in Fig. We additionally verify which
10

---

Published in Transactions on Machine Learning Research (05/2024)
Ideal Points
Hyper- classes
Class-
fl
balanced
Axis-aligned
x
x
9.9
HoroSplitter
x
X
35.7
HoroSplitter
X
v
36.5
HoroSplitter
x
37.4
HoroSplitter
/
38.3
Table 5: Ablating the HoroSplitter in HoroRP the football dataset. We follow the experimental protocol of Fan et al. (2023 and report the mean and standard deviation of the micro-fl score over five trials of 5-fold stratified cross-validation. Our splitting function, hyperclass-bsse aggregation, and class balancing are all important for effective hyperbolic random forests.
HoroRF
Base HoroRF
ODIRI
OBIRF
Figure 4: Visualizing HoroRF ObIRF splits. We show five splits for HoroRF, a basic version of HoroRF without caass-bal and hyperclasses, ObIRF on the original hyperbolic emboddings, and ObIRF after mapping the data to Euclidean space. The split with the highest impurity is chosen at every level to visualize the next level. Splitting in hyperbolic space with balanced and multi-level horospheres obtains good splits for hyperbolic classification.
method is the most successful at various depths in Tab. 6 where we find that HoroRF consistently reaches high performance and is especially effective with a single split.
Reducing runtime limitation HoroRE is its runtime on large datasets. While the HoroSplitter scales lincarly with the number of samples as HoroSVM has linear time complexity, is applied multiple times per node and repeated for every node. We designed and conducted two experiments showing how mitigate the computational time needed to obtain good results: reducing the number of trees and lowering
11

---

Published in Transactions on Machine Learning Research (05/2024)
Depth
2
3
10
No limit
ObIRF Euc
34.5+0.1
68.8+2.5
83.3#0000
99.3#0.0
98.9+0.0
ObIRF Hyp
33.6+0.7
65.6+1.3
83.2+0.3
99.1+0.00
98.9+0.0
Base HoroRF
60.8+0.0
67.8+4.9
83.6#116
99.1
99.1+0.3
HoroRF
63.113.2
67.415.1
85.5118
99.3.1.0
98.910.33
Table 6: Effect of tree depth on performance on the synthetic dataset. We run a grid search to determine the optimal configuration on the validation and report results over three trials in micro-fl score the Lest. set. Bold denotes the best method, underlined the second best. Splitting in hyperbolic space with balanced and multi-level horospheros consistently reaches high performance.
Micro-f2
Micre-fl
0P8
Micro-11
045
Timb 1st
Micro-11
Time Lst
0.1
58
Thes
Iterations
Figure 5: Analyzing ways to reduce the computational time of HoroRF on polbooks. In (a); we show that the optimal performance is already reached with around 20 trees. In (b), we show that by reducing the number of optimization iterations of HoroSVM, we can further reduce computational time while maintaining high performance.
the number of HoroSVM optimization iterations. From the results in Fig. 5 find that both the number of trees and HoroSVM optimization iterations can be greatly reduced without sacrificing performance. Lowering the number of HoroSVM iterations is logical way to reduce compulational time, are not interested in finding the exact optimal horosphere; solution close to it suffices for our purpose and might even benefit HoroRF due to the increased variation in splits.
5 Conclusion
We present HoroRF, random forest algorithm in hyperbolic space. HoroRF constructs its trees by re- peated application of the HoroSplitter, which finds horosphere-based splits with high information gain. We show the benefits of additional components aimed at improving performance imbalanced and multi- class datasets. Extensive experiments on two established and one newly introduced benchmark show its effectiveness over both existing hyperbolic classifiers as well as their Euclidean counterparts.
Further advances in hyperbolic classification can easily be incorporated into the framework, as HoroRF no way restricted to a single type of classifier. In future work, we aim to investigate the benefits of combining multiple types of splits, for example by including hyperbolic logistic regression to provide additional split options to include next to the horosphere splits. We furthermore expect that any improvement in optimiza- tion of HoroSVM as splitting operation, akin to hyper-optimized librarics for Euclidean SVMs (Chang & Lin 2011 will have direct benefits for HoroRF, especially when dealing with many classes.
References
Lada A Adamic and Natalic Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop Link discovery, pp. 36-43, 2005.
12

---

Published in Transactions on Machine Learning Research (05/2024)
Ola Ahmad and Freddy Lecue. Fisheyehdk: Hyperbolic deformable kernel learning for ultra-wide field-of- view image recognition. In Proceedings of the AAAT Conference on Arlificial Intelligence, volume 36, pp. 5968 5975, 2022.
Leo Breiman. Random forests. Machine learning, 45:5-32, 2001.
Herbert Busemann. The geometry of geodesics. Academic Press, 1955.
Shaofeng Cai, Kaiping Zheng, Gang Chen, HV Jagadish, Beng Chin Ooi, and Meihui Zhang, Arm-net: Adap- tive relation modeling network for structured data. In Proceedings of the 2021 International Conference on Manogement of Data, pp. 207-220, 2021.
Erick Cantú-Paz and Chandríka Kamath. Inducing oblique decision trees with evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 7(1):54 68, 2003.
Pengfei Cao, Yubo Chen, Kang Liu, Jun Zhao, Shengping Liu, and Weifeng Chong. Hypercore: Hyperbolic and co-graph representation for automatic icd coding. In Proceedings of the 58th Annual Meeting of the Association for Compulational Linguistics, pp. 3105 3114, 2020.
Rich Caruana and Alexandru Niculescu-Mizil. An empirical comparison of supervised learning algorithms.
In Proceedings of the 23dd international conference on Machine learning, pp. 161-168 2006.
Benjamin Paul Chamberlain, James Clough, and Marc Peter Deisenroth. Neural embeddings of graphs in hyperbolic space. ar preprint arXiv: 10359, 2017.
Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovee. Hyperbolic graph convolutional neural net- works. Advonces in neural information processing systems, 2019.
Ines Chami, Albert Gu, Vaggos Chalziafratis, and Christopher Ré. From trees to continuous embeddings and back: Hyperbolic hierarchical clustering. Advances in Neural Information Processing Systems, 33: 15065-15076, 2020.
Ines Chami, Albert Gu, Dat P Nguyen, and Christopher Ré. Horopca: Hyperbolic dimensionality reduction via horospherical projections. In International Conference on Machine Learning, pp. 1419 1429. PMLR, 2021.
Chih- Chih-Chung Chang and Chih-Jen Lin. Libsvm:: A library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
Eli Chien, Chao Pan, Puoya Tabaghi, and Olgica Milenkovie. Highly scalable and provably accurate clas- sification in poincaré balls. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 61-70. IEEE, 2021.
Philippe Chlenski, Ethan Turok, Antonio Moretti, and Itsik Pe'er. Fast hyperboloid decision tree algorithms. arXiv preprint arXiv:2310.138// 13841, 2023.
Hyunghoon Cho, Benjamin DeMeo, Jian Peng, and Bonnie Berger. Large-margin classification in hyperbolic space. In The 22nd international conference on artificial intelligence and statistics, pp. 1832-1840. PMLR, 2019.
Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 215-223. JMLR Workshop and Conference Procoedings, 2011.
Corinaa Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20:273 297, 1995.
Yin Cui, Menglin Jia, Tsung-Y Yi Lin, Yang Song, and Sorge Belongie. Class-balanced loss based on effec- tive number of samples. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9268 022799777 2019.
13

---

Published in Transactions on Machine Learning Research (05/2024)
Karan Desai, Maximilian Nickel, Tanmay Rajpurohit, Justin Johnson, and Shanmukha Ramakrishna Vedan- tam. Hyperbolic image-text representations. In International Conference on Machine Learning, 2023.
Thanh-Nghi Do, Philippe Lenca, Stéphane Lallich, and Nguyen-Khang Pham. Classifying very-high- dimensional data with random forests of oblique decision trees. Advances in knowledge discovery and management, pp. 39-55, 2010.
Aiden Durrant and Georgios Leontidis. Hmsn: Hyperbolic self-supervised learning by clustering with ideal prototypes. arXiv preprint Xit::2305.1092, 2023.
Xiran Fan, Chun-Hao Yang, and Baba Vemuri. Horocycle decision boundaries for large margin classification in hyperbolic space. areie preprint arXiv:2302.0680) 2023.
Pengfei Fang, Mehrtash Harandi, and Lars Petersson. Kernel methods in hyperbolic spaces. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 10665 10674, 2021.
Christiane Fellbaum. Princeton university: About wordnet, 2010.
Manuel Fernández-Delgaan Eva Cernadas, Senén Barro, and Dinani Amorim. Do we need hundreds of classifiers to solve real world classification problems? The journal of machine learning research, 15(1): 3133 3181, 2014.
Octavian Ganca, Gary Béeigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hicrar- chical embeddings. In International Conference on Machine Learning, pp. (656-1655. PMLR, 2018a.
Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. Advances in newral information processing systems, 31, 2018b.
Ashima Garg, Depanshu Sani, and Saket Anand. Learning hicrarchy aware features for reducing mistake severity. In European Conference on Computer Vision, pp. 252 267. Springer, 2022.
Mina Ghadimi Atigh, Martin Keller-Ressel, and Pascal Mettes. Hyperbolic busemann learning with ideal prototypes. Advances in Neural Information Processing Systems, 34:103-115, 115, 2021.
Mina Ghadimi Atigh, Julian Schoep, Erman Acar, Nanne Van Noord, and Pascal Mettes. Hyperbolic image segmentation. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2022.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 78812)778 2002.
Léo Grinsztajn, Edouard Oyallon, and Gaäl Varoquaux. Why do tree-based models still outperform deep learning on typical tabular data? Advances in Neural Information Processing Systems, 35:507 520, 2022.
David Heath, Simon Kasif, and Steven Salzberg, Induction of oblique decision trees. In IJCAI, volume 1993, pp. 1002 1007. Citeseer, 1993.
Shyamgopal Karthik, Ameya Prabhu, Puneet K Dokania, and Vineet Gandhi. No cost likelihood manipu- lation at test time for making better mistakes in deep networks. International Conference on Learning Representations, 2021.
Tejaswi Kasarla, Gertjan Burghouts, Max van Spengler, Elise van der Pol, Rita Cucchiara, and Pascal Mettes. Maximum class separation as inductive bias in one matrix. Advances in Neural Information Processing Systems, 35:19553 19566, 2022.
Rakesh Katuwal and Ponmuthurai Suganthan. Enhancing multi-class classification of random forest us- ing random vector functional neural network and oblique decision surfaces. In 2018 International Joint Conference Neural Networks, pp. 1-8. IEEE, 2018.
Rakesh Katuwal, Ponmuthurai Nagaratnam Suganthan, and Le Zhang, Heterogeneous oblique random forest. Pallern Recognition, 99:107078, 2020.
14

---

Published in Transactions on Machine Learning Research (05/2024)
Valentin Khrulkov, Leyla Mirvakhabova, Evgeniya Ustinova, Ivan Oseledets, and Victor Lempitsky. Hyper- bolic image embeddings. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 6418 6428, 2020.
Anna Klimovskaia, David Lopez-Paz, Léon Bottou, and Maximilian Nickel. Poincaré maps for analyzing complex hicrarchies in singlo-cell data. Nature communications, 11(1):2966, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. Advances in neural information processing systems, 2019.
Shaoteng Liu, Jingjing Chen, Liangmingg Pan, Chong- Wah Ngo, Tat- Chua, and Yu-Gang Jiang. Hy- perbolic visual embedding learning for zero-shot recognition. In Proceedings of the IEEE/CVF conference on compuler vision and pollern recognition, 2020.
Aaron Lou, Isay Katsman, Qingxuan Jiang, Serge Belongie, Ser-Nam Lim, and Christopher De Sa. Dilfer- entiating through the fréchet mean. In International Conference on Machine Learning, 2020.
Gian Marconi, Carlo Ciliberto, and Lorenzo Rosasco. Hyperbolic manifold regression. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2020.
Bjoern Н Menze, B Michael Kelm, Daniel N Splitthoff, Ullrich Koethe, and Fred A Hamprecht. On oblique random forests. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2011, Athens, Greece, September 5-9, 2011, Proceedings, Port II 22, pp. 453-469. Springer, 2011.
Pascal Mettes, Mina Ghadimi Atigh, Martin Ressel, Jeffrey Gu, and Serena Yeung. Hyperbolic deep learning in computer vision: A survey. arXiv preprint arXiv:2305.060 06611, 2023.
Nicholas Monath, Manzil Zaheer, Daniel Silva, Andrew McCallum, and Amr Ahmed. Gradient-based hierar- chical clustering using continuous representations of trees in hyperbolic space. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 714-722, 2019.
Sreerama K Murthy, Simon Kasif, Steven Salzberg, and Richard Beigel. Ocl: randomizod algorithm for building oblique decision trees. In Proceedings of AAAT, volume 93, pp. 322-327 Citeseer, 1993.
Maximillaan Nickel and Douwe Kiela. Poincaré embeddings for learning hicrarchical representations. In Advances in neural information processing systems, volume 30, 2017.
Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry, In International conference machine learning, 2018.
Chao Pan, Eli Chien, Puoya Tabaghi, Jianhao Peng, and Olgica Milenkovic. Provably accurate and scalable lincar classificrs hyperbolic spaces. Knowledge and Information Systems, pp. 1-34, 2023.
Wei Peng, Thomas Varanka, AbdeIrahman Mostafa, Henglin Shi, and Guoying Zhao. Hyperbolic deep neural networks: A survey. IEEE Transactions on pattern analysis and machine intelligence, 44(12)::0023-11044 2021.
Rinu Ann Sebastian and Anu Maria Sebastian. Leveraging semantic similarity to mitigate the severity of misclassification for safety critical applications. Multimedia Tools and Applications, 12(6):12615-122) 12633, 2023.
Ryohei Shimizu, Yusuke Mukuta, and Tatsuya Harada. Hyperbolic neural networks In International Conference Learning Representations, 2021.
Sho Sonoda, Isao Ishikawa, and Masahiro Ikoda. Fully-connected network on noncompact symmetric space and ridgelet transform based on helgason-fourier analysis. In International Conference Machine Learn- ing, pp. 1M405-20422 PMLR, 2022.
15

---

Published in Transactions on Machine Learning Research (05/2024)
Jianing Sun, Zhaoyue Cheng, Saba Zuberi, Felipe Pérez, and Maksims Volkovs. Hgef: Hyperbolic graph convolution networks for collaborative filtering. In Proceedings of the Web Conference 2021, 2021a.
Li Sun, Zhongbao Zhang, Jiawei Zhang, Feiyang Wang, Hao Peng. Sen Su, and S Yu Philip. Hyperbolic variational graph neural network for modeling dynamic graphs. In Proceedings of the AAAT Conference Artificial Intelligence, volume 35, pp. 4375-4383, 2021b.
Didac Surís, Ruoshi Liu, and Carl Vondrick. Learning the predictability the future. Proceedings of the IEEE/CVF Conference on Computer Vision and Pottern Recognition, pp. 12607-12617, 2021.
Chang- Yu Tai, Ming- Yao Li, and Lun-Wei Ku. Hyperbolic disentangled representation for fine-grained aspect extraction. In Proceedings of the AA Conference on Arlificial Intelligence, volume 36, pp. 11358 11366, 2022.
Alexandru Tifrea, Gary Béeigneul, and Octavian-Fugen Ganea. Poincaré glove: Hyperbolic word embed- dings. International Conference on Learning Representations, 2019.
Max van Spengler, Erwin Berkhout, and Pascal Mettes. Poincaré resnet. In International Conference on Computer Vision, 2023.
Melanie Weber, Manzil Zaheer, Ankit Singh Rawat, Aditya K Menon, and Sanjiv Kumar. Robust large- margin learning in hyperbolic space. Advances in Neural Information Processing Systems, 33:17863 17873, 2020.
Menglin Yang, Min Zhou, Zhihao Li, Jiahong Liu, Lujia Pan, Hui Xiong, and Irwin King. Hyperbolic graph neural networks: a review of methods and applications. orXiv preprint XXKu:2200.11852 2022.
Wayne W Zachary. An information flow model for conflict and fission in small groups. Journal of anthropo- logical research, 33(4):452-44 -4322 1977.
16


Reviews:
[{"review_id": "lHOE8wXMCw", "reviewer": "Reviewer_vu6A", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n- Implementing hierarchical splitting based on horospheres within a tree ensemble model represents a novel approach.\n- The proposal is carefully designed, amalgamating horoSVM outputs through tree structures. The consideration of class imbalance adds further value.\n- Visualizations greatly enhance comprehension of the method.\n\n### Weaknesses\n\n- In this paper, it is consistently assumed that datasets are embedded into hyperbolic space beforehand, and each classifier is applied to the embedded data. However, it is not reasonable to apply non-hyperbolic methods, such as the standard SVM and random forest, to such embedded data. Instead, they should be applied to raw datasets (or with some more appropriate preprocessing). For instance, I cannot understand why axis-aligned splitting and oblique splitting are applied to data points embedded into hyperbolic space in Figure 1. Similarly, in Figure 4, oblique splitting should be visualized in the original data space.\n- Regarding the aforementioned issue, I believe Euclidean methods should indeed be conducted on non-hyperbolic datasets as well. Although the authors mention that \"the Euclidean baselines are run on the same embeddings as the hyperbolic methods, which we also find to perform better compared to mapping the embeddings back to Euclidean space first\", it is crucial to present the full set of experimental results for a thorough evaluation.\n- I feel that employing only 100 trees for ensemble models might be somewhat limited. It would be beneficial to conduct experiments with varying numbers of trees, such as 10, 100, and 1000, to thoroughly explore the impact of the ensemble size on model performance.\n- Improving the presentation of the paper can indeed enhance its clarity. Here are some suggestions:\n\t- Ensure consistency in notation: Replace instances of $x$ with $\\mathbf{x}$, especially where $\\mathbf{x}$ denotes vectors or matrices. Consistency in notation helps maintain clarity and reduces confusion for readers.\n\t- Equation (7) should be written in one line to avoid ambiguity.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes splitting data points based on level-wise horospheres at each node of a tree in a tree ensemble model, with the assumption that data points are embedded into hyperbolic space beforehand. More specifically, the proposed method performs horoSVM, an existing hyperbolic SVM, at each node for splitting. The performance of the resulting ensemble model has been evaluated on real-world datasets embedded into hyperbolic space, comparing it with Euclidean and hyperbolic classifiers.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address the concerns outlined in the Weaknesses section above.", "broader_impact_concerns": "I do not have any concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LBeqLK4URN", "reviewer": "Reviewer_4Yct", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nThe paper is well-written and easy to understand. I found it enjoyable to read. The method proposed in the paper is intuitive and performs well in practice. The authors have taken care to address common issues found in real data, such as multiple classes and imbalanced data. \n\nThey have also conducted an ablation study to demonstrate the importance of each component. \n\nAdditionally, illustrations have been included in the paper to enhance its readability.\n\n\nWeaknesses\n\n\n\nComplexity or runtime analysis is lacking.\n\nThe evaluation is somewhat limited to datasets with expected hyperbolic structure. \n\nI would expect to see a more thorough evaluation using synthetic data with a known hyperbolic structure. The authors can demonstrate the approach's strengths and limitations compared to other baselines. Also, how does the method work on real-world tabular data?\n\n\nThe authors mention Chlenski et al.'s concurrent work on a similar problem but don’t compare it or explain the main differences between the two methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a method for generalizing random forests from Euclidean to Hyperbolic spaces. The main idea is to find candidate horospheres using a large-margin classifier. They extend the method to multiclass data by combining classes based on the lowest summon ancestor. To further handle imbalanced classes, they introduce a class-balanced large-margin loss. They perform several experiments demonstrating the merits of the new method compared to the existing hyperbolic method or Euclidean tree-based models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Requested changes and questions\n\nCan you expand on the metrics presented in Table 4? Those are not intuitive\n\nHow are the hyperparameters of all baselines tuned?\n\nIn the multiclass WorldNet how many splits do you create? One?\n\nOn World Net you write: “we split the data into 80% for training and 20% for testing and report the best results from a grid search over three runs in AUPR”\nSo, what standard deviation is reported?\n\nIn general, the evaluation seems different between each dataset, and it isn’t clear how model selection is performed without harming the performance evaluation of the cross-validation procedure [1].\n\n\nWhat are the limitations of the method? I don’t see this addressed in the paper.\n\nI would also expect to see a synthetic evaluation to evaluate the performance and limitations of the method in a controlled (hyperbolic) space.\n\n\nWhy is equation 16 broken into two lines? Won’t it fit in one line?\n\nSome basic details on the datasets are missing.", "broader_impact_concerns": "There are no specific concerns for ethical impications", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "c0JSo14S8p", "reviewer": "Reviewer_H8RP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The increased interest in hyperbolic representations of data structure and associated algorithms and models for their analysis places the paper in a relevant context. Furthermore, the intuitive connection between topology of hyperbolic space and hierarchical structure is clear and it is believable that hierarchical models (like decision trees) may be well poised to dominate in this area.\n\nOn the other hand, the paper lacks in convincing evidence that the proposed approach is very effective. The performance gains over other methods are marginal, and the number of repetitions of experiments is very few. The referenced work of Chlenski et al. (2023), which includes another RF model for hyperbolic space is also not included in these experiments, which is a major limitation. Furthermore it is unclear if the hyperparameter tuning has been done in an appropriate manner or not. \nOn the methodological side in terms of the model structure asopted, it isn't immediately clear that horospheres are the most natural partitioning functions to exploit the \"hierarchical\" structure of hyperbolic space. If my understanding of this is accurate then something like the intersection of a cone anchored at the origin with an origin centered sphere of radius < 1 seems far more natural. It is also not immediately clear how much novelty there is in the class merging heuristic, nor the weighting term included in the objective to accommodate class imbalance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper describes an implementation of a random forest classifier in hyperbolic space. The implementation seems to be based closely on the Euclidean oblique random forest (OblRF) with SVM of Do et al. 2010 (reference from the paper), but with the SVM component modified to the hyperbolic SVM. Some heuristic modifications on how to perform individual splits, such as aggregating classes and modifying the loss function to accommodate class imbalance are discussed.\n\nSome new and existing experimental set ups for hyperbolic data classification and associated performance comparisons are presented, showing some potential of the proposed approach.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Questions and requested changes:\n1. Is the class merging heuristic used in the paper novel, or at least very similar to something already in use? If not, please reference its origin.\n2. Were hyperparameters chosen to optimise test error, or were they selected by an appropriate data driven selection technique like cross validation (CV)? If the former, then I am of the opinion that the results are meaningless since they do not reflect what is realisable in practice, and I'd like to request results be reported from experiments where hyperparameters are selected using more principled approaches which do not rely on access to test error. Please also provide results from more than three replications since the improvements offered by the proposed approach are not very substantial and stronger evidence is needed to show the changes proposed are worthwhile.\n3. Since there is another recent implementation of random forests in hyperbolic space, referenced in the paper, please provide comparisons with this method as well as they seem arguably the most relevant.\n4. There are numerous typographical errors in the paper, some of which I will list below, along with some other minor points. Please proof-read before uploading a revision:\n- In reference to Fig 1. c), you refer to a \"subtree\". This is a bit of a leap for any reader not very clear on decision tree method estimation algorithms, I'd recommend something more descriptive of the figure itself.\n- In Fig 1. I would argue that in a) the linear model actually does a good job. Is the problem that it would need more splits to get to the green class? Please clarify.\n- In Eq. (4) the argument of B_w should be bold font. In addition, in the following sentence should w be in S^{n-1}?\n- In Eq. (6) the subscript in B_w should be bold font (or at least be consistent across the paper)\n- The alignment in Eq. (7) is rather unsightly.\n- Also in Eq. (7), why is there a bracket around B^{-1}_w(x)? The way it appears \\mu looks like it must be a function.\n- Below Eq. (8) C should be in math font.\n- \"Eq. equation 7\" shouldn't have both \"Eq.\" and \"equation\" (numerous instances of this)\n- In Eq. (16) should the \\beta^{n_y} not be for the specific class of instance i? Otherwise this term is the same for all i and does nothing.\n- Regarding the above, I would recommend not going into the rather rough explanation of the effect of class imbalance and just jump right to Eq. (16) and say the extra factor is to accommodate unbalanced classes.", "broader_impact_concerns": "Nothing immediately apparent to note", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers proposed Accept/Leaning Accept. Reviewers highlighted that the horospheres may not be the ideal partitioning functions, however the authors have adequately justified their decision.
Decision: Accept (poster)