Horospherical Decision Boundaries for Large Margin Classification in Hyperbolic Space
Authors: Xiran Fan
Chun-Hao Yang
Baba C. Vemuri
Venue: NeurIPS 2023 poster (2023)
Keywords: Large-margin clssifier
Hyperbolic space
Horosphere
SVM
Geodesically convex
Global optimility
Busemann function
TL;DR: Geodesically convex Large-margin classifier in hyperbolic space

Abstract: Hyperbolic spaces have been quite popular in the recent past for representing hierarchically organized data. Further, several classification algorithms for data in these spaces have been proposed in the literature. These algorithms mainly use either hyperplanes or geodesics for decision boundaries in a large margin classifiers setting leading to a non-convex optimization problem. In this paper, we propose a novel large margin classifier based on horospherical decision boundaries that leads to a geodesically convex optimization problem that can be optimized using any Riemannian gradient descent technique guaranteeing a globally optimal solution. We present several experiments depicting the competitive performance of our classifier in comparison to SOTA.

Horospherical Decision Boundaries for Large Margin Classification in Hyperbolic Space
Xiran Fan
Chun-Hao Yang
Department of Statistics University of Florida fanxiran@uf edu
Institute of Statistics and Data Science
National Taiwan University
chunhaoy@ntu.c edw.:/uttuuuuuuuue..mm edu.
Baba C. Vemuri
Department CISE
University of Florida vemur vemuri@ufl teufi.uffleee
Abstract
Hyperbolic spaces have been quite popular in the recent past for representing hierarchically organized data. Further, several classification algorithms for data in these spaces have been proposed in the literature. These algorithms mainly use either hyperplanes or geodesics for decision boundaries in a large margin classifiers setting leading to a non-convex optimization problem. In this paper, we propose novel large margin classifier based on horospherical decision boundaries that leads to geodesically convex optimization problem that can be optimized using any Riemannian gradient descent technique guaranteeing a globally optimal solution. We present several experiments depicting the competitive performance of our classifier comparison to SOTA.
1 Introduction
Hyperbolic space, a non-Euclidean space with constant negative curvature, has been shown [25, 23, 29, 24] to be effective for representing hierarchically organized data. For example, authors in [25] showed that a tree can be embedded in a hyperbolic space with arbitrarily small distortion. The main reason for this is that a hyperbolic space can be regarded volume of the space grows exponentially as one moves away from the center in hyperbolic space. This matches the growth pattern of the number of nodes in a tree which grows exponentially the depth the tree increases. Hyperbolic space embedding has been shown to be promising approach for representing data with (latent) hierarchical structure [23, 24, 29, 15].
continuous version of trees - the
Recently, representation of data in hyperbolic space for the fundamental tasks of unsupervised and supervised learning has been popularized in various contexts, e.g., dimensionality reduction [10, 13]. clustering [22], karge-margin classifier [12, 32, 11], regression [20], etc. Existing 'linear' classifiers in hyperbolic spaces are predominantly based geodesics i.e., using geodesics as decision boundaries. In [12], the decision boundary chosen to the intersection of the hyperboloid model and hyperplane in the ambient space, which in this case is the Minkowski space. Then, the support vector machine (SVM) in hyperbolic space is formulated as a nonconvex optimization problem. In [32], authors followed the same parameterization of the hyperbolic geodesic decision plane and provided a series algorithms to provably learn large margin classifiers in hyperbolic space. However, as pointed out by [11], the algorithm in [32] fails converge in practice. Authors in [11] used the Poincaré ball model and parameterized the geodesic decision plane as a hyperplane mapped using the exponential map from the tangent space some reference point. They first constructed convex hulls
for each data cluster in the hyperbolic space and the reference point is then chosen to be the midpoint
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

between different convex hulls. Then they apply Euclidean Perceptron/SVM algorithm to data lifted into the tangent space the aforementioned reference point. Although the optimization problem in the tangent space is convex, the procedure of the tangent space approximation introduces inaccuracies and distortions. Moreover, convex hull learning is highly unstable and their implementation is only applicable to the 2-dimensional hyperbolic space.
Finally, is worth mentioning that linear classification within hyperbolic space, which can be considered as the last layer, referred to as the hyperbolic logistic regression (LR), is fundamental component of hyperbolic neural networks (HNNs) [16, 27]. The calculation of logits in this layer is based on the distances between samples and the geodesic decision boundary. Notably, this hyperbolic LR employs a geodesic decision boundary but is not large-margin classifier.
1.1 Horospherical Decision Boundaries for Classification in Hyperbolic Sapce
Horospheres, which are the level sets of the Busemann function in hyperbolic spaces, are the analogs of Euclidean hyperplanes [4]. Horospheres (horocycles) are contained in the Poincaré ball (disk) and are tangential to the ball (disk) at an ideal point as shown in Figure I. A collec- tion of horospheres centered at the same ideal point are parallel to each other and the lengths of geodesic seg- ments between two horospheres are all equal, just as the lengths of line segments between parallel hyperplanes in Euclidean space are all equal. This property of horo- spheres was explored by [9] to develop a dimensionality reduction method for data in hyperbolic space. By using horospherical projection, they are able to preserve the dis- tance information in the original data. However, there is no literature on constructing a 'linear' classifier in hyper- bolic space using horospheres as the decision boundaries although the horospheres are the hyperbolic equivalent of Euclidean hyperplanes. Therefore, it is natural to consider the use of horospheres as decision boundaries for classifi- cation in hyperbolic spaces. In this work, we propose novel hyperbolic large-margin classifier using horospheres as decision boundaries in the Poincaré model. We term this classifier as a HoroSVM. The horospheres are well-defined in the Poincaré ball model. A toy example shown in Figure 2 demonstrates the advantage of horospherical decision boundaries over geodesic decision boundaries. As the tree-structured data grows in depth, leaf nodes are embedded closer to each other within subtree and among different subtrees. One of the classification problems in hyperbolic space is to determine whether node belongs to a chosen subtree given the embedding. For comparison purposes, the decision boundaries of HoroSVM (Figure 2(a)) and hyperboloid SVM [12] (Figure 2(b)) are shown in the figure. As evident, the horospherical decision boundary perfectly separates (the root node is excluded in training) the data while the geodesic decision boundary makes several mistakes on both positive and negative samples. We present novel formulation of the classification problem in the hyperbolic space as geodesically convex optimization problem on a Riemannian manifold. This optimization problem can be easily solved using any Riemannian gradient descent technique guaranteeing global optimality. Gradient-based optimizations for geodesically convex problems guaranteeing global optimal solutions are the topic of investigation in optimization literature and we refer the reader to [35] for detailed convergence analysis of several such optimization methods. Further, we empirically validate our method on several real and synthetic data sets.
Figure 1: A 2-d Poincaré disk model B and its boundary OIB S'_ Given an ideal point w E OB², the black lines and curves are hyperbolic geodesics starting (ending) at and the red circles are horo- cycles centered at w.
It should be noted that horosphere decision boundary has been used in some recent works [31, 28] in constructing HNNs. For example, authors in [31] proposed hyperbolic neuron models using the Busemann function as a generalization of the Euclidean inner product to extract horosphere features from data. Authors in [28] proposed a shallow fully-connected continuous network spanned by (hyperbolic) neurons, on noncompact symmetric space (including hyperbolic space) using the Helgason- -ourier transform. Authors in [33] produced Euclidean features from hyperbolic embed- dings via the eigenfunctions of the Laplace operator in the hyperbolic space where the eigenfunctions involve horosphere features. Note that none of the above works developed a large margin classifier using the horosphere decision boundary. To the best of our knowledge, our work is the first in the

---

Hacrydte BIE SANTIO
Guoduec Duttion
(a) Horospherical decision boundary
(b) Geodesic decision boundary
Figure 2: A balanced tree with depth 6 and spread embedded in 2-d Poincaré ball model using [15] depicted the figure. The orange plus node the root of a chosen subtree, the blue dots are positive samples (nodes of the subtree) and the red dots are negative samples. (a) depicts HoroSVM performance on the classification of positive and negative samples/nodes along with a zoomed-in version its right. (b) depicts the geodesic boundary from the competing method, Hyperboloid SVM [12], along with the zoomed-in version to its right.
literature to present convex optimization formulation of a large-margin classifier using horosphere decision boundary in a hyperbolic space.
The rest of this paper is organized as follows. In Section 2, we present some background on hyperbolic geometry pertinent the work presented here. In Section 3, we present our horospherical boundary- based classification methods. Experimental results are presented in Section 4 to demonstrate the advantage of our HoroSVM over competing hyperbolic classifiers. Finally, we conclude in Section
Background
In this section, review basic concepts of hyperbolic geometry including the generalization of the Euclidean hyperplane to the hyperbolic space namely, the horosphere.
2.1 Hyperbolic Space and the Poincaré Ball Model
There five isometric models of the hyperbolic space: the Poincaré ball model, the Lorentz model, the Klein model, the upper-half space model, and the Hemisphere model [7]. We choose the Poincaré Ball model in this paper it is easy to visualize and the Busemann function has nice closed-fome expression in this model. Note that the decision boundary choice in our work is the level-set the Busemann function namely, the horosphere.
An n-dimensional Poincaré Ball model, denoted by (BB", .9a), consists of all points in an open ball of radius 1, i.e., B {ær E R" ||ж=|| < 1}. and equipped with the Riemannian metric grs (x) 4(1 || - where ||-|| the Euclidean L2 norm, and ya the Euclidean metric.
The geodesic distance between points x, y BB" is (x. y) cosh (1 + 2
[| |
P2 bil
2.2 Horospheres
Geodesics, geodesic rays, and ideal points The shortest path that connects two points in the Poincaré Ball model called geodesic segment. geodesic ray is geodesic segment that can be infinitely extended in one direction. We call the endpoint at infinity of a geodesic ray an ideal point. For B ideal points form the boundary of the ball: "B" gn-1 {ar IR" ||ق||| 1), where gn-1 is the (n 1)-dimensional hypersphere. The hypersphere (Sn-1, .s) is Riemannian manifold equipped with the Riemannian metric gs = 4(1 + |= -2
Busemann function [6] Let " be an ideal point and 7o 10, 1 geodesic ray pointing w. The Busemann function is defined as
(x)
lim (d(rw t), x E.
(1)
1-000
3

---

In the Poincaré Ball model, Eq. (1) has closed form (ar) log
1- ||||" ( x
Horospheres [6] In B", a horosphere is a (n - 1) diimensional sphere that is internally tangent to O1R" at ideal point. For a given w OL"", the level sets of Busemann function (x) in the Poincaré ball model is a series of horospheres tangent at w. Horospheres are hyperbolic hyperplanes in the sense that the corresponding construction in Euclidean space gives hyperplane.
Given an ideal point E OB", the function defined by (w,z) : x H> (2) constant over horosphere tangent at w. Hence any horosphere can be parameterized with an ideal point w and an offset value b of the level set.
Let IT denote the set of horospheres of IB", A horosphere π E IT can be parameterized by 0 < E R
g"-1, and E R
pp (z E BB ["| z) b = 0}.
(2)
We will use π or æ. to represent horosphere different parameterizations hereafter.
3 Horospherical Boundary-based Classification
In this section, we present the key theoretical contributions of our work namely, horosphere based SVM classifier that involves formulating and solving a geodesically convex optimization problem. First, we present some preliminary facts and results about the horospheres. Then, we present the optimization problems for the horospherical perceptron and SVM along with analysis.
3.1 Point to Horosphere Distance
While the distance from the origin o to a horosphere has been known for decades [18] (Introduction 4.1, p.31), we present natural generalization of previous results by providing a closed-form expres- sion for measuring the hyperbolic distance from any arbitrary point x E" to given horosphere b- The following remark provides this result.
Proposition 3.1. Let na be horosphere. The hyperbolic distance of a point horosphere n is given by
B
de dz(2, mp.w.)) Iu(ws, x) bl
(3)
Notice that it shares similarity to the Euclidean distance of point to a hyperplane. Before presenting the proof for Proposition 3.1, we recall the following Fact 3.2 and Lemma 3.3 from [31].
Fact 3.2. Given an ideal point w and point IB", there is unique horosphere passing through x and tangent at w.
Lemma 3.3. [31] Let Ilw be the set of horocycles of B" tangent at w. Given A E E. let Th be the unique horosphere that passes through tanh(A/ (X/2) -w and tangent at w. Note that Ih UxeR (w) We have the following two results: (i) the hyperbolic lengths of geodesic (that pass through w) segments between T w and πI xa w are equal to \>1 >2l; (ii) (w,r)) = for any E x
Figure 3 shows a 2D Poincaré disk model BB² and its boundary $1 The point o is the origin of the disk, E B² is point, and E St is point at infinity (an ideal point). Two geodesics ending at the same w from and o respectively are shown in the figure (black solid line/curve). The circle T given horocycle tangent (red solid circle) at w. The hyperbolic distance dg (x. Tp.w.b) between æ and Tu. is identified as the distance between and ya where ya, is the projection of a to Th along the geodesic ending at w. Let nh (red dashed circle) the unique horocycle that passes through & and is tangent at w. Note that the lengths of all geodesic segments between two horocycles are the same. That is, dg (ax, (p..w,)) = dæ( y ) = dg (#o, yo). where æo. Yo are horocyclic projections [9] of x, y along π and Tp, respectively.
Note that the Euclidean inner product (w, +) is constant over hyperplane that perpendicular to given direction w.
Parameter μ included for simplicity in analysis later on (Eq 3, 12)

---

Proof of Proposition 3.1. Given point E B" and an ideal point E S"-1, let E Il be horosphere tangent at and x" E Il be the unique horosphere that passes through æ. Write (w, 3) = Az and then Zo = =tanh(da/2) consistency notation, we write nh as : A. Since the horosphere Ty.w.b can be reparameterized as A, where /t+ the hyperbolic distance from æ to Ty.eo, is the hyperbolic distance between Aa and n which is A> >1 |
w is the horospherical projection of z along T. For
(by Lemma 3.3). This completes the proof.
3.2 Horospherical Decision Boundaries
We consider classification problems in hyperbolic space of the following form: X' C B denotes the feature space and y = {=1} denotes the binary label space. following, denote the training set by S C X' x Y. The decision rule using a horosphere as its decision boundary can be written as the following function f X y where
the
fa: pr, w, b) sign (u(w, Z) b)
(4)
The positive samples are expected to lie inside a horo- sphere while the negative samples are expected lie out- side a horosphere. This is analogous to the linear decision boundary in Euclidean space and we will build horo- spherical perceptron and a horospherical SVM based on this decision boundary.
Figure 3: The relationship between
horocycles, geodesic, and the horocyclic projections in B
should be noted that in R" the hyperplane Ea,w.b = {2 E R [a(w x) - bb = where a e RR,b b E R. w E Sa-1 is the hyperplane Eo However, the horospheres Tw and Tw.-w.-b respectively represent two distinct horospheres, centered w and -w respectively. Let 11 (Tp.w.s E 616 > 0} and 11= {m E 11|6 < 0}. Thus, I1+ _1I C 11 and the radius of π E II+ is less than 1/2 and the radius of क E II is greater than 1/2. In most cases of classification in hyperbolic space, the positive samples are clustered near the boundaries. Hence, we restrict ourselves to finding horosphere т E II that separates data, instead of searching over II. Intuitively, looking for a 'small' horosphere that captures the positive samples. We are now ready to present the Horospherical Perceptron followed by the Horospherical SVM.
3.3 Horospherical Perceptron
The loss function for the proposed horospherical perceptron is given by
UH, w, by x. 3) max(0, -y (p(w, z)n b)), (H, E E S R+,
(5)
which is zero when the instance is classified correctly and is proportional to the signed distance of the instance from the horosphere when is misclassifidd. The empirical loss for given data set S is
L(n, w)
Σ (E.
((u,w,bs bx,,y)
(6)
Hence, the optimal horosphere is learned by solving the above optimization problem on the manifold R+ x 5m-1 x R.,i... n¹, "."", bb arg min L(u,, b) (1.
To further analyze this optimization problem, we first recall some facts about geodesic convexity. Definition 3.4. (Geodesically convex sets [30]. Let (M.g) be a Riemannian manifold. A set A M is said to be a geodesically convex set if, for any two points p. q E A, the geodesic Ypg that connects them is contained in A.
Definition 3.5. (Geodesically convex/concave functions [30]) Let C M be geodesically convex set. A function : A + R is said to be a geodesically convex function if, for any p. q A the composition f Ypg [0, 1] ~ IR is a convex function, where 7pg : [0, 1] - M is geodesic that
connects p.g. q. ff is said to be geodesically concave function if - ff a geodesically convex function.
5

---

Theorem 3.6. [30] Let A S M be geodesically corvex set. A function f: - R is geodesically convex if and only if its epigraph epi(f) =
S {) A R a convex set.
Now we present the main theoretical result of this paper.
Theorem 3.7. For given training data sample {ι. E S,0 < ||>|| < R < (the hyperbolic feature a neither lie on the center nor lie on the boundary), Ui, w. b; x, y) a geodesically convex
function IR x A x Bt and is geodesically concave function IR + x B x RR,, where
A U VESS Note that both A and B are geodesically conver sets.
y
v=VV
|
of C
0)
B B=
B-
T-LUES"
y
x V'v
|
0
c
CS
(8)
Proof. Let ((, w, b; æ, y) = max(0, -g(1, w, b; æ. y)) where g(u, w, b; x. y) = y. (u(w,, x). - b). Since max(0, -a) is convex function in R and g(.) is linear in j and b, only need to show that g()) as a function of w E g"-1, is geodesically convex (concave). Without loss of generality, let and 0. Also note that y is the label of data that takes values from f-1, which may flip the inequality. It suffices to validate results for the positive sample, i.e, y = 1.
With slight abuse of notation, let g(w; x) = 9(1, w 0; æz 1) = z)) In 1- ce
defined on
-- =
A = v E Sn-1 n | > o) c c Since In(-) is decreasing and convex, we only need to check
hww;; a:) = w - æ= is geodesically convex on A, i.e, check that the epigraph of h is a convex set.
Note that z" c0s( for E S where Ow <(w, w))
cpi(h) [(wcc] E A x R||lw x1 2 s c}
xJ
(w) c)
|||20|| (1 + || |,0|| - c)
||a|||
(9)
{ A x [d(c), 00)
ifc) <
=[w c) cos((w)) 2 d(c))
Aa [d(c), xo)
if >
where d(c) is a real number depending on and ||س||| and A. = {(w.c) c) cos(Ow) 2 d(c)) is the collection of unit vectors where the angle between the vectors given the data x is small i.e., restricted small region on the sphere. The last equality follows from the definition of A and Ag: if d(c) S
then (w cos( 2 d(c)) n A A. Similarly, if d(c) > 0, {w cos(Ow) 2 d(c) n A = (w E
sa-1 ((ss(0w)) 2 d(c)) = Adte)- Both A and A are geodesically convex sets and this completes
the proof.
The convex sets A, B are the hemispheres of S--1 separated by the hyperplane {z E R <R' 2 = 0} (the hyperplane has x as its normal vector) in its ambient space I Theorem 3.7 tells us that given one data sample (æx, y), the optimal value described Eq. (7) exists R+ x A x R+, and it is globally optimal. For collection of training samples S ( y: ) let A;
{ E Lees"=1/22
13:
a. > >0)
If the data are separable by horosphere, it follows that NW A is non-
empty and convex. Then the loss function given S is geodesically convex on IR+ x n A; x R+ and the global optimum can be obtained using any gradient- based optimization. Numerically, we apply a Riemannian gradient descent method on the entire space g+ Sn-1 x RR since g(,, w, b; x, y) is continuous.
3.4 Horospherical SVM
Given a horospherical decision boundary Tyuw, parameterized by w E SS- u E R+, and b E R, the margin 7 is the minimal distance from training samples S to the decision boundary:
inf y (u(w, x) b) {my)es"
(1, wo b) inf y f(x;; pu, b) du (ar, m..w,b) (s.
(10)
The maximum margin classifier can be obtained by solving the following optimization problem:
TH (,,,w,)) b) s.t. y (H(W, x)B b) 2 r
max b.ao,b
for all (x, y) E S.
(1I)

---

Theorem 3.8. The maximum margin classification problem in hyperbolic space with horosphere as its decision boundary described Eq. (11) is equivalent to the following optimization problem:
min k.w.bb
2/1²
s.t. y (n(w, b) 2 for all (a, v) E.S.
(12)
The proof is analogous to that in the Euclidean case [3]. Note that the margin is unchanged if we apply the following scale transformation; jl - ->>,/// /u/y and - b/7. We can also build soft-margin
horospherical SVM, dubbed HoroSVM, by minimizing the following loss function:
1 2d +
Me, w. b, v)
max(0, 1-11--10 ys (plw, 24)s b)). bb).
(13)
where C' is hyperparameter that controls the tradeoff between minimizing misclassification and maximizing margin.
It is easy to see that the same result as in Theorem 3.7 holds for the loss function in Eq. (13). That is, the loss function is geodesically convex function on one geodesically convex subset of the parameter space and geodesically concave function on the other geodesically convex subset of the parameter space. Recall that the idea behind proving that the loss function in the horospherical perceptron,
max(0, --))), where 9()) y- (n(w, æ)n b), is geodesically convex is based on the important fact that max (0, aa) a convex function a R. Similarly, the same idea applies to HoroSVM, where the hinge loss is used, and the loss function becomes 1/²²² + max(0, 1 g(-)). Note that max(0, a) is also convex function in E R and 1 is convex function in Jr, these facts complete the proof of the desired property for the HoroSVM, which is analogous to Theorem 3.7 for horospherical perceptron.
We can then apply any Riemannian gradient descent optimization methods for updating the parameters in HoroSVM since the problem is an optimization problem over product space of Riemannian manifolds, R x S x R We refer the readers to [5] and [1] for more details about optimization techniques Riemannian manifolds.
4 Experiments
In this section, we present several experimental results obtained from an application of our HoroSVM synthetic data as well as real data sets used in published literature. Our implementation is based on Pymanopt [19] using the Riemannian conjugate gradient method [26] on Intel(R) Xeon(R) CPU ES-26683 v3 @ 2.00GHz.
4.1 Network Data Set
Here, we follow the experimental setup in [12], and evaluate our MoroSVM over four real-world network data sets used by [8]: karate [34] (2 classes, 34 nodes polblogs [2] (2 classes, 1224
nodes ), polbooks (3 classes, 105 nodes) ), and football [17] (12 classes, 115 nodes )
The network data is embedded in 2D hyperbolic space using the method of [8]. Given the hyperbolic embeddings, we compare our HoroSVM with three other competing large margin classifiers: Eu- clidean SVM (even though it violates the hyperbolic geometry). hyperboloid SVM [12], and Poincaré SVM [11]. The absence of comparison with [32] in this experiment is due to two reasons. First, [32] aims to provide theoretical understanding of hyperbolic spaces in classification, focusing on "linearl"" separable data (data that can be separated by a geodesic). They do not address extensions to nonlinearly separable data, which limits their applicability to many practical datasets. Second, for datasets that are linearly separable in hyperbolic space, the approach in [32] aligns with the hyperboloid SVM when adversarial training is not applied in [32].
For multiclass classification, one-verses-rree strategy is applied. We conducted five-fold cross- validation on each data set, where we chose the hyperparameter C from {1,5, 10) during the cosssvalidation procedure. Note that a more extensive search space for C' may lead to potential performance improvements. The mean of the F1 score followed by the standard deviation over five
hhttp://www- Pattp://wwwppersonall. umich, wwt.///ej////eeettttaaaa
7

---

Table 1: Fl scores for node classification on network datasets. Boldface indicates best performance.
Methods
Karate
Polblogs
Polbooks
Football
Euclidean SVM
0.95 0.06
0.92 + 0.02
0.83 = 0.03
0.29 + 0.12
Hyperboloid SVM
0.95 0.06
0.92 0.01
0.83 = 0.03
0.30 + 0.14
Poincaré SVM
0.78 = 0.16
0.92 = 0.02
0.84 = 0.03
0.32 = 0.04
VV (Ours)
0.98 0.04
0.93 = 0.01
0.85 = 0.04
0.34 = 0.06
Table 2: Fl scores for subtree classification on four subtrees of WordNet. Boldface indicates the best performance on 2D embeddings of each dataset.
animal.n.01 3218/798
group.n.01 6649/1727
worker.n.01 861/254
mammal.n.0l
Methods
953/228
Hyperboloid SVM (D = 2)
0.53 0.07
0.52 + 0.01
0.54 + 0.04
0.39 0.03
Hyperbolic IR (I) = 2)
0.46 + 0.08
0.52 = 0.04
0.54 + 0.07
0.32 + 0.10
Hyperbolic LR (D = 5)
0.95 0.03
0.76 = 0.07
0.80 + 0.08
0.78 0.04
Hyperbolic LR (D 10)
0.96 + 0.01
0.86 = 0.05
0.84 + 0.04
0.94 + 0.04
Euclidean SVM (D 2)
0.39 + 0.01
0.39 0.00
0.32 + 0.02
0.20 + 0.01
Euclidean SVM (D = 5)
0.95 = 0.00
0.79 = 0.01
0.38 0.02
0.44 0.01
Buclidean SVM (D = 10)
0.97 0.00
0.91
0.00
0.46 0.04
0.72 + 0.05
HoroSVM (D 2)
0.57 0.07
0.65 0.01
0.62 = 0.01
0.42 0.01
MoroSVM (D =5)
0.93 0.01
0.88
0.00
0.82 + 0.04
0.88 + 0.01
HoroSVM (D = 10)
0.95 0.02
0.91 0.01
0.86 + 0.01
0.93 0.02
trials are summarized in Table 1. As evident from the table, our method yields the best results on all the data sets.
HoroSVM outperformed other methods on all four data sets. The data in karate are well-separated and thus both Euclidean SVM and hyperboloid SVM performed equally well. Our method outper- forms the others since the horospheres have several nice properties, the most important of which is that the Busemann function whose level sets the horospheres is convex function that guarantees global optimality in the optimization. Notice that the performance of Poincaré SVM on karate is inferior others by significant amount. The reason that the performance of Poincaré SVM is sensitive to the choice of the reference point. We demonstrate our performance gain on the remaining data sets, and our method is more consistent, compared Euclidean SVM and hyperboloid SVM, in terms of lower standard deviation, on football data set where data exhibit larger variance/spread.
4.2 Subtree Classification in WordNet
task of considerable interest in hyperbolic space classification problems is to determine whether a node belongs to given subtree in the hyperbolic embedding. We obtained hyperbolic embeddings in various dimensions using the approach in [15] for WordNet noun hierarchy (82,115 115 nodes). We consider four subtrees whose roots are the following synsets: ANIMAL. N. 01, GROUP. 01. WORKER. N. 01, and MAMMAL N. 01.
We split all nodes in subtree into positive training (80%) and test (20%) nodes and applied the same process the remaining WordNet nodes create negative training and test sets. The average F1 scores and the standard deviations over trials are shown in Table 2. The number of positive training/test samples of each data set are listed as well. We exclude Poincaré SVM from the comparisons in this task. The reason being, data are highly imbalanced in this task and the positive samples are clustered near the boundary. The reference point learned Poincaré SVM will close to the boundary where the tangent approximation of data at this reference point is highly distorted, as opposed to the original hyperbolic embeddings. It is therefore hard to locate a hyperplane in the
'nttps:/ wwwpettttiiiinnnnceeeeeeoee
8

---

langent space that separates the lifted (mapped) data. In addition, the learning of the reference point only applicable to 2D hyperbolic space.
As well known in the Fuclidean SVM literature, a vanilla (unweighted) implementation of SVM performs poorly on extremely imbalanced data, we observed the same behavior in training HoroSVM on this task. We preprocessed the data by downsampling the majority class of samples (the negative samples) train robust model. Note that our MoroSVM can be naturally extended a class/instance- weighted version by assigning a class/instance weight to the penalty term C' for each sample, allowing us to address more general imbalanced data. Since there is no protocol for dealing with unbalanced data in training a hyperboloid SVM, we presented the Euclidean SVM results using the same preprocessed data for reference. addition, we presented results of hyperbolic logistic regression (LR) [15], which is not a large-margin classifier on this task, where the imbalanced data is handled by sampling the equal number of negative and positive nodes in each mini-batch of size 16 during training.
Now, we highlight several results in Table 2. The superior performance of hyperboloid SVM over hyperbolic LR is expected, as both methods use geodesic decision boundaries but hyperboloid SVM aims to maximize the margin. However, the training of hyperboloid SVM is highly unstable as we mentioned earlier due to the non-convex optimization process. Euclidean SVM under-performs as it does not take into account the hyperbolic geometry. Our HoroSVM exhibits significant improvement in predicting words in a subtree, as evidenced by higher F1 scores across all the subtrees. The small number of nodes within subtree, compared the whole WordNet, causes the nodes to cluster near the boundary in their hyperbolic embeddings. Thus, horosphere is an ideally suited decision boundary (in comparison to the geodesic boundary in [12]) to isolate the subtree.
4.3 Synthetic Data with Noisy Labels
3.0
6.0
035
6:0
To demonstrate the robustness of our HoroSVM, we apply to synthetic data with noisy labels at varying levels/amounts of noise. Specifically, we generated 100 synthetic datasets by sampling from Gaus- sian mixture model defined on the Poincaré disk model as in [12]. The isotropic Gaus- sian distribution in hyperbolic space is re- ferred to as the Riemannian normal distri- bution, and we used the sampling method presented in [21]. For each dataset, we sampled two centroids from a zero-mean Riemannian normal distribution with a variance of 1.5. We then sampled 200 data points from unit-variate Riemannian normal distribution centered at each centroid, resulting in a dataset of 400 points classified into positive and negative classes. We split the dataset into training and test sets with 100 positive/negative samples in the training set and 100 positiveenegative samples in the test set. We then generated datasets with noisy labels at noise levels: v E {0, 0.05, 0.1, 0.5) by flipping the labels of proportion v) of the training (not test) samples, with an equal number of positive and negative samples flipped. The train/test average F1 scores of each method across all datasets varying noise levels are shown in Fig 4. We compared our HoroSVM with hyperboloid SVM, hyperbolic LR, and a two-layer HNN [15] (with a hidden dimension of 5). While all methods depict decreasing training Fl scores as the noise level increases, HoroSVM outperforms the others consistently throughout the training process. Hyperbolic LR and HNN exhibit the least resistance to label noise, with test Fl scores dropping (faster) with increasing noise level. Both hyperboloid SVM and HoroSVM demonstrate consistent performance across different noise levels, owing to the inherent robustness of taggemmargnn classifiers. However, the training of hyperboloid SVM is highly unstable resulting in its inferior performance. HoroSVM demonstrates its superiority in accuracy and robustness as evidenced the results. In addition, we present the average training times for each method on one dataset (200 samples) as follows: 6.57 seconds (Hyperboloid SVM), 3.98 seconds (Hyperholic LR), 9.06 seconds (HNN), and 3.73 seconds (HoroSVM)) Notably, HoroS VM stands out as the fastest.
1025
0.30
080
5-00
Figure 4: Training (left) and test (right) Fl scores of several methods on synthetic data with noisy labels at different noise levels.

---

Discussion and Conclusions
In this paper, we presented a novel large margin classifier, dubbed HoroSVM, whose decision boundaries are horospheres that are the level sets of Busemann function. We presented novel formulation leading to the optimization gradient-based method and guaranteeing globally optimal solution. We demonstrated superior to competitive performance of the HoroSVM over SOTA large margin classifiers
geodesically convex loss performed using Riemannian
In Euclidean space, kernel SVM is usually favored over the linear SVM due to its ability to cope with non-linearly separable data. In Hyperbolic space, the challenge lies developing valid positive definite kernels (see [14] for details on validity of kernels on Riemannian manifolds). The only reported work on KSVM in hyperbolic space that we are aware of is [12], which uses a kernel that violates the positive definiteness property of RKHS kerelss. Thus the problem of interest is primarily defining a valid family of kernels in hyperbolic space. We will address this in our future work.
Acknowledgements
This research was in part funded by the NSF grant IIS 1724174 and the NIH NINDS and NIA grant RFINS121099 to Vemuri.
References
[1] P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. In Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2009.
[2] Lada A Adamic and Natalie Glance. The political blogosphere and the 2004 us election: divided they blog. In Proceedings of the 3rd international workshop on Link discovery, pages 36-43, 2005.
[3] Christopher M Bishop and Nasser Nasrabadi. Pattern recognition and machine learning, volume 4. Springer, 2006.
[4] Roberto Bonola. Non-Euclidean geometry: A critical and historical study of its development. Courier Corporation, 1955.
[5] Nicolas Boumal. An introduction to optimization on smooth manifolds. Available online, May, 3, 2020.
[6] Martin R Bridson and André Haefliger. Metric spuces of non-positive curvature, volume 319, Springer Science & Business Media, 2013.
James W. Cannon, William J. Floyd, Richard Kenyon, and Walter R. Parry. Hyperbolic Geometry, volume 31. MSRI Publications, 1997.
[8] Benjamin Paul Chamberlain, James Clough, and Mare Peter Deisenroth. Neural embeddings of graphs in hyperbolic space. arXiv preprint 1705: 2017.
19] Ines Chami, Albert Gu, Dat P Nguyen, and Christopher Ré. Horopca: Hyperbolic dimensionality reduction via horospherical projections. International Conference on Machine Learning, pages 1419-1429. PMLR, 2021.
[10] Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. Advances in Neural Information Processing Systems, 32:4868-48799 2019.
[11] Eli Chien, Chao Pan, Puoya Tabaghi, and Olgica Milenkovie. Highly scalable and provably accurate classification in poincaré balls. 202 IEFE International Conference on Data Mining (ICDM), pages 61-70. IEEE, 2021.
[12] 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, pages 1832- 1840. PMLR, 2019.
[13] Xiran Fan, Chun-Har Yang, and Baba C Vemuri. Nested hyperbolic spaces for dimensionality reduction and hyperbolic nn design. In Proceedings of the IEEE/CVF Conference on Computer Vision and Patter Recognition, pages 356-365,20 2022.
10

---

[14] Aasa Feragen, Francois Lauze, and Soren Hauberg. Geodesic exponential kernels: When curvature and linearity conflict. In Proceedings of the IEEE conference computer vision and paltern recognition. pages 3032-3042, 2015.
[15] Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hierarchical embeddings. In International Conference Machine Learning, pages 1646-1655. PMLR. 2018.
[16] Octavian- Eugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks. Advances in Neural Information Processing Systems 31, pages $345-5355, 2019.
[17] Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceed- ings of the national academy of sciences, 99(12),7821-7822 2002.
[18] Sigurdur Helgason. Groups and geometric analysis: integral geometry, invariant differential operators. and spherical functions, volume 83. American Mathematical Society, 2022.
[19] Niklas Koep and Sebastian Weichwald, Pymanopt: A python toolbox for optimization manifolds using automatic diffcrentiation. Journal of Machine Learning Research, 17:1-5, 2016.
[20] Gian Marconi, Carlo Ciliberto, and Lorenzo Rosasco. Hyperbolic manifold regression. In International Conference on Artificial Intelligence and Statistics, pages 2570-2580. PMLR, 2020.
[21] Emile Mathicu. Charline le lan, chris j maddison, ryota tomioka, and yee whye tch. continuous hierarchical representations with poincaré variational auto-encoders. Advances in Neural Information Processing Systems, pages 22544-12555, 2019.
[22] Nicholas Monath, Manzil Zaheer, Daniel Silva, Andrew McCallum, and Amr Ahmed, Gradient-basse hierarchical clustering using continuous representations of trees in hyperbolic space. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 714-722, 2019.
[23] Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. Advances in neural information processing systems, 30:6338-6347, 2017.
[24] Frederic Sala, Chris De Sa, Albert Gu, and Christopher Ré. Representation tradeoff's for hyperbolic embeddings. In International conference on machine learning, pages 4460-4469. PMLR, 2018.
[25] Rik Sarkar. Low distortion delaunay embedding of trees hyperbolic plane. In International Symposium on Graph Drawing, pages 355-366. Springer. 2011.
[26] Hiroyuki Sato. Riemannian conjugate gradient methods: General framework and specific algorithms with convergence analyses. SIAM Journal on Optimization, 32(4):2690-2) 271 2022.
[27] Ryohei Shimizu, YUSUKE Mukuta, and Tatsuya Harada. Hyperbolic neural networks+++. In International Conference on Learning Representations, 2020.
[28] Sho Sonoda, Isao Ishikawa, and Masahiro Ikeda, Fully-connected network on noncompact symmetrie space and ridgelet transform based on helgason-fourier analysis. In International Conference on Machine Learning, pages 20405 20422. PMLR, 2022.
[29] Alexandru Tifrea, Gary Becigneul, and Octavian- BugrennnEuggnneee Ganea. Poincare glove: Hyperbolic word embed- dings. In International Conference on Learning Representations, 2018
[30] Constantin Udriste. Convex functions and optimization methods on Riemannian manifolds, volume 297.
Springer Science Business Media, 2013.
[31] Ming-X Xi Wang. Laplacian eigenspaces, horocycles and neuron models on hyperbolic spaces. 2021.
[32] Melanie Weber, Manzil Zaheer, Ankit Singh Rawat, Aditya Menon, and Sanjiv Kumar. Robust large- margin leamnigg in hyperbolic space. Advances in Neural Information Processing Systems, 33:17863-1777 17773, 2020.
[33] Tao Yu and Christopher De Sa. Hyla: Hyperbolic laplacian features for graph learning. arXiv preprint Xrviv2200..0 0,8444 2022.
[34] Wayne W Zachary. An information flow model for conflict and fission in small groups Journal of anthropolggiaal research, 33(4):452-473, 1977.
[35] Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Conference on Learning Theory, pages 1617-1638. PMLR, 2016.


Reviews:
[{"review_id": "ZFDstPVZ2B", "reviewer": "Reviewer_cEx8", "summary": "Based on recent successes with hyperbolic embeddings of data with a (latent) hierarchical structure, this paper proposes a new type of SVM in hyperbolic space. Their SVM, named HoroSVM, uses horospheres as decision boundaries and the authors derive a way to compute the distance of a point to such a horosphere. This makes the method different from other recently proposed hyperbolic SVMs, which use geodesic hyperplanes as decision boundaries. The authors argue that these horospheres are a more suitable generalization of hyperplanes than their geodesic-based counterparts and that, therefore, HoroSVM is likely to outperform the other methods.\n\nAfter introducing their method, the authors show that their loss function is geodesically convex with respect to the learnable parameters. As a result, they state that a global optimum to the optimization problem, that arises when using HoroSVM, can be found using gradient-based optimization methods. They further state that, while their method has this nice property, the other methods to which they compare do not. Therefore, HoroSVM should again yield better results.\n\nWith a series of three experiments, the authors attempt to empirically show the superiority of their method over geodesic hyperplane methods and Euclidean SVM. The first experiment aims to show the superior performance on the classification of hyperbolic embeddings of network data. The second experiment shows that HoroSVM is better than its competitors at predicting the subtree to which nodes belong within WordNet. The third and final experiment shows that their method is more robust than their competitors to noisy labels.\n\nLastly, based on their theoretical analysis and empirical results, the authors conclude that their method is more performant and robust than its competitors, while also alluding to future work with hyperbolic kernel SVMs.\n\n", "questions": "Alongside the questions posed in the weaknesses above, I have a few additional questions:\n\n1. Why are there both a mu and a b parameter in equation (2)? You only need 1 parameter here. Is it for notational simplicity later on? If so, a small note might help to clarify this for the reader. If not, removing this over-parameterization would also make the different versions of pi with subscripts a bit easier to follow.\n2. Theorem 3.7 tells us that, for a single sample, the loss function is geodesically convex w.r.t. the learnable parameters. Is this result strong enough to guarantee convergence to a global optimum in case of a collection of samples? Based on the discussion in the introduction I presume it is, but I think it would be nice to mention this for the reader.\n3. Why is the Poincaré inner product named an inner product? This name seems confusing to me as it suggests that it actually has the properties of an inner product, which it clearly cannot have. ", "limitations": "Yes, the authors point out that kernel SVMs are usually preferred over linear SVMs and indicate that they will work on this in the future. I think that the current work is still an important step in this direction.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The paper contains several, mostly theoretical strengths in my opinion:\n\n1. The paper derives a way to compute distances from points on the Poincaré ball to horospheres. While directly relevant to their HoroSVM method, this formulation is likely useful to any other method that implements these horospheres on the Poincaré ball, making it a nice contribution.\n2. The authors prove the geodesic convexity of their newly proposed loss function, resulting in a very strong statement about the possibility of finding a global optimum to their optimization problem. If it is indeed the case that the competitive hyperbolic methods do not have this property, then this is a very clear theoretical argument for the superiority of their method w.r.t. these other hyperbolic methods.\n3. In my opinion the paper introduces an interesting theoretical analysis of their method, which could by itself be useful as a tool for studying other methods in hyperbolic space or even on other Riemannian manifolds.\n4. The experiments show the superiority of their method with respect to their competitors both w.r.t. classification performance and noisy label robustness.", "weaknesses": "There are a few concerns that I have with this paper, which mostly have to do with the motivation for using horocycles over geodesic hyperplanes and with the setup of the experiments. Firstly, my concerns with the motivation for the use of horocycles are:\n\n1. There are multiple geometric definitions of hyperplanes possible and it is not clear which one is chosen here. However, it is stated that horocycles are the hyperbolic equivalent of Euclidean hyperplanes and that, therefore, horocycles are a natural choice for decision boundaries. This does not provide a clear motivation for choosing horocycles over geodesic hyperplanes. What is the geometric motivation for this choice and why should it lead to better results in practice?\n2. Figure 2 is supposed to provide a clear motivation for why horocycles are better as decision planes than geodesic hyperplanes, but the geodesic hyperplane example (on the right) seems poorly chosen to me. In fact, it seems very easy to find a hyperplane by hand that would lead to significantly better results than the hyperplane in the figure. What is going on here? Is this really a problem with geodesic hyperplanes or is it a problem with the optimization process. If the latter is the case, then this is still not a direct argument for using horocycles over geodesic hyperplanes.\n\n\nMy concerns regarding the experiments (mostly experiment 1) are:\n\n1. In the experiment from Subsection 4.1, it is unclear how the hyperbolic embeddings of the network data were generated. As the method for generating these embeddings is likely to affect the outcome of the experiment, it is difficult to judge its validity without a description hereof.\n2. Moreover, after the 5-fold cross-validation, the differences between the results obtained with the different methods are quite small for at least two of the datasets, especially compared to the standard deviation. This makes the experiment seem a bit weak as a motivation for using HoroSVM.\n3. Also, given that solving the optimization problem for HoroSVM leads to a global optimum, why do you not simply choose the optimal C? And in that case, would the standard deviation not simply be 0?\n4. What happens when you use a Euclidean embedding of the data and then Euclidean SVM? Even though the Euclidean embeddings would be distorted, it seems plausible to me that Euclidean SVM could obtain better results in such a setting. The current comparison does not seem completely fair to me.\n5. In the second experiment the embeddings are obtained through the application of hyperbolic entailment cones. However, there are some issues with this method and there is a method from the paper \"Representation Tradeoffs for Hyperbolic Embeddings\" by de Sa et al. which boasts greater performance than hyperbolic entailment cones. How do the results change if this method had been used to generate the embeddings?\n6. Lastly, in Table 2 the focus is put on the case of low dimension D = 2, where HoroSVM is significantly better. However, for this low dimension the performance of every method is rather low and for higher dimensions the difference in performance seems to fade. Is there a reason to still focus on low dimensions? What happens if the dimension is chosen even greater? Does the advantage of HoroSVM disappear completely?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer cEx8\n\nWe thank the reviewer for the valuable comments and questions. Please find our responses below:\n\n> 1. geometric motivation for horospheres\n\nOur motivation behind developing a classifier based on horosphere decision boundaries was to create a large-margin classifier in Hyperbolic space that mirrors the concept of the large-margin hyperplane-based classifier (linear SVM) in Euclidean space. In Euclidean space, hyperplanes can be conceptualized as infinite-radius spheres, with parallel ones sharing the same direction.\n\nHorospheres stand out as the optimal choice for hyperbolic hyperplanes where a horosphere can be viewed as the limit of spheres as their radii approach infinity [C1]. Horospheres with the same direction are parallel to each other.\n\nNote that earlier works, such as [12,33], have defined the concept of hyperplanes in hyperbolic space using the intersection of a hyperplane in Minkowski space and the hyperboloid model. This extrinsic approach to defining the analog of Euclidean hyperplanes in hyperbolic space doesn't maintain the essential characteristic of parallel hyperplanes having the same direction. \n\n\n> 2. Figure 2 ...\n\nWe used the hyperboloid SVM implementation provided by [12]. The choice of the geodesic hyperplane separator could be influenced by the optimization of the nonconvex loss function in the hyperboloid SVM. In contrast, our HoroSVM guarantees an optimal result.\n\nIn the specific case in Fig.2, different choices of geodesic (by hand) might lead to fewer misclassifications, but such a choice may not be the minimizer of the distance-based loss function used in hyperboloid SVM. In our work, the choice of horospheres is quite natural as explained in A1.\n\n> 3. how the hyperbolic embeddings of the network data were generated.\n\n> 5. ...choose the optimal C\n\nWe apologize for the lack of clarity in presenting details in Experiment 1. In this experiment, we followed the setup in [12] and evaluated our model on the network data embedded in hyperbolic space using the approach described in [8]. We tested 5 different embeddings of each network and report the mean and standard deviation across different embeddings for each dataset.\n\n> 4. differences are quite small\n\nThe comparable performance among all methods in Table 1 for the mentioned two cases could be attributed to the fact that these datasets were well-separated. Therefore, each method is expected to perform equally well in these cases. \n\n> 6. use a Euclidean embedding\n\nThe performances of Euclidean SVM on the Euclidean embedding of the data in experiment 1 are presented in [12], where Euclidean SVM performs poorly compared to hyperboloid SVM, even with high-dimensional Euclidean embeddings (d=25), e.g., for Karate, AUPR 0.5 (Euclidean) vs. 0.86 (hyperboloid SVM).\n\n> 7. embeddings in Experiment 2\n\nTo present a fair comparison with the same embedding scheme, we utilize the hyperbolic entailment cone method [15] used in hyperboloid SVM [12] and hyperbolic LR [16]. We would be happy to explore the performance of all the methods using the suggested embedding scheme by de Sa et al [24] in our future work. We have to admit that we could not find any direct comparison between the two embedding methods in the suggested reference [24] as well as in any follow-up work in this domain.\n\n> 8. focus on low dimension \n\nPlease refer to our response to Reviewer 38iz’s Q2\n\n> 9. parameter in Eq 2\n\n> 11. Poincare inner product\n\nWe apologize for the use of the potentially misleading term, inner product. A more appropriate presentation for it will be: given an ideal point $\\omega$, the function defined by $\\langle \\omega,x \\rangle_{B}:  x \\mapsto -b_{\\omega}(x)$ is constant over horosphere tangent at $\\omega$. Hence any horosphere can be parameterized with an ideal point $\\omega$ and an offset value $b$ of the level set. As for Eq 2, $\\mu$  is included for simplicity in analysis later on (Eq 3, 12). We will add a note as suggested in the revision.\n\n> 10.  in case of a collection of samples?\n\nYes, the result holds for a collection of data. We will revise line 224-227 as follows for clarification. \n\nFor a collection of training samples $S = \\lbrace (x_i, y_i)\\rbrace_{i=1}^N$, let $A_i =  \\lbrace \\nu \\in \\mathbb{S}^{n-1} | y_i \\cdot \\frac{x_i^T \\nu} {\\lVert x_i \\rVert} > 0   \\rbrace $. If the data are separable by a horosphere, it follows that $\\cap_{i=1}^N A_i$ is non-empty and convex. Then the loss function given S is geodesically convex on $\\mathbb{R}^{+} \\times \\cap_{i=1}^N A_i \\times\\mathbb{R}^{+}$ and the global optimum can be obtained using any gradient-based optimization."}, {"review_id": "z0yBUOdfEc", "reviewer": "Reviewer_yt6v", "summary": "The paper proposes a large margin classifier in hyperbolic space, Poincare ball models. To this end, horospherical decision boundaries (which are based on the Buseman function and are different level sets of the Busmann function at the ideal point) are used for the large-margin classifier. They also show that the formed classifier is convex and optimization can be performed using Riemannian gradient descent. They perform experiments on four datasets and compare the results with Euclidean Hyperboloid, Poincare, and Horo SVM.", "questions": "Why does not the paper compare the method with [33] in the experiments? \nLines 176- 184 are not very clear. How are the positive and negative $\\pi$ subsets of the same one? shouldn't they be on the opposite sides of the Poincare ball model? Why do the authors claim that the positive samples are clustered near the boundaries? \n\nWhat is the reference point in Poincare SVM? and why is it sensitive to the reference point? ", "limitations": "The paper discusses future work shortly in the conclusions. ", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a large margin classifier based on the horospheres. The research question is valid and the paper is well motivated, and well written. The paper also provides the proofs for the theoretical claims as well. Figures are also beneficial to understand, for example figure 2 is beneficial to compare the horocycle vs geodesic decision boundary. \n\nThe experiments also show the efficacy of the proposed approach specially on 2dimensional embedding space. Synthetic data with noisy labels is also an interesting experiment showing the robustness of the proposed approach and generally hyperbolic version to the noisy data.\n\nThe analysis on the performance on the experiments section is beneficial as well. \n", "weaknesses": "There is one main question about comparison with [33]. The paper generally is well written , there a few questions which I will add to the questions section. \n\nI would suggest the authors to do a proofreading. The paper discusses horosphere decision boundary in several different ways like horospheres decision boundary, horocycle decision boundary, and horospherical decision boundary. Using a fixed terminology throughout the paper can increase the comprehensiveness of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer yt6v\n\nWe thank the reviewer for the valuable comments and questions. Please find our responses below:\n\n> 1. comparison with [33]\n\nThe reason for the absence of comparison with Weber et al. [33] in our experiments are: \n\n\n(1). Weber et al. [33, Sec 6]  focus on theoretically understanding the benefits of hyperbolic spaces for classification, using experiments to illustrate the results derived for linear models and separable data. Extensions to non-separable data and non-linear models are not addressed in [33]. \n\n(2). For datasets that are separable in hyperbolic space, the approach in Weber et al. [33, Sec 6 & Fig 3] is aligned with the approach of hyperboloid SVM [12] under specific constraints namely, when the adversarial budget $\\alpha =  0$. Further elaboration on this point is provided below.\n\nIn [33], authors employ the same parameterization of the hyperbolic geodesic decision plane for classification in hyperbolic space as utilized in hyperboloid SVM [12]. It is shown theoretically in [33] that a hyperbolic perceptron employing such geodesic decision boundaries is guaranteed to converge on separable data using a gradient descent method. Subsequently, [33, Sec 3.2] demonstrates that by employing margin losses, such as the logistic or hinge loss, in the optimization process, a large-margin classifier can be effectively learned through gradient descent. It is noteworthy that this corresponds to hyperboloid SVM [12] when the hinge loss is applied.\n\nMoreover, [33] establishes a method to inject adversarial examples into the gradient-based loss minimization process, leading to an algorithm that efficiently learns a large-margin classifier. In this approach, the magnitude of the perturbation added to the original example is bounded by an adversarial budget $\\alpha$. When $\\alpha=0$, the method in [33] aligns with the one presented in [12].\n\nWhen dealing with real-world datasets where the assumption of data separability is scarcely fulfilled, the applicability of [33] becomes limited. For experiments on real data where the assumption that the data is separable is barely fulfilled, [33] is not applicable and we compare our method with [12]. Additionally, we will explore the adoption of an adversarial setting for our method in future work.\n\n> 2. proofreading\n\nWe highly appreciate your comments and will align the terminology accordingly in the revision.\n\n> 3. Lines 176- 184 are not very clear. \n\nIn Euclidean space, if $n$ is the normal vector of a hyperplane, $-n$ is also the normal vector of this hyperplane. In hyperbolic space, however, let $\\Pi_{\\omega}$ be the set of horospheres tangent at $\\omega$, then $\\Pi_{-\\omega}$ is the set of horospheres tangent at $-\\omega$, the antipodes of $\\omega$ on $\\partial\\mathbb{B}^n$. Note that $\\Pi_{\\omega} \\neq \\Pi_{-\\omega}$. For a given $\\omega$, $\\Pi^+$ is the collection of horospheres that are tangent at $\\omega$ and do not contain the origin (spheres with radius $<$ 0.5), while $\\Pi^-$ is the collection of horospheres that are tangent at $\\omega$ and contain the origin (spheres with radius $>$ 0.5). \n\nAs the volume grows exponentially in hyperbolic space, there is more space/volume as we approach the boundary and hence more data can be accommodated near the boundary. Hence, for a tree embedded in hyperbolic space, the leaf nodes within a subtree appear as a cluster near the boundary, and the clusters (representing different subtrees) are well separated from each other. Hence in the subtree classification task, we can properly assign the positive labels to a subtree of interest.\n\n> 4. reference point in Poincare SVM\n\nIn Poincare SVM [11], the reference point $p$ serves as the anchor point to which all data are lifted into the tangent space at $p$. The classification is performed in that tangent space. However, the data distortion varies across different tangent spaces, making the performance of Poincare SVM sensitive to the choice of the reference point.\n"}, {"review_id": "maG6I5cbrg", "reviewer": "Reviewer_1ZfQ", "summary": "This paper presented a novel large margin classifier, dubbed HoroSVM, whose decision boundaries are horospheres in hyperbolic space, and proved it’s a convex optimization problem.\nThis paper presented several experiments depicting the competitive performance of the classifier in comparison to SOTA.\n", "questions": "The method in this paper and the compared methods are basically based on SVM. Wouldn’t the result better if neural networks are applied to classify in hyperbolic space?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper presented a novel large margin classifier, dubbed HoroSVM, whose decision boundaries are horospheres in hyperbolic space. It’s innovative compared to the predecessors.\n2. This paper systematically and clearly explain the proof, which is easy to follow.\n", "weaknesses": "1. The experiments “Synthetic Data with noisy Labels” are over synthetic data, which is not convincing enough compared to apply random perturbations over real-world dataset\n2. The motivation of classification in hyperbolic space is explained inexplicit.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 1ZfQ\n\nWe thank the reviewer for the valuable comments and questions. Please find our responses below:\n\n> 1. random perturbations over real-world dataset\n\nThe noisy label experiment was conducted using synthetic data, which\nallows us to have full control over the level of noise injected in the labels. For the\nreal word dataset, we conducted additional noisy label experiments on two\nbinary-class network datasets used in Experiment 1 (karate and polblogs)\nwith a 20% noise level to demonstrate the robustness of our classifier. Our\nmethod performs the best as evidenced in the following table.\n\n| Dataset         | Karate | Karate-Corrupted | Polblogs | Corrupted-Polblogs |\n|-----------------|--------|------------------|----------|--------------------|\n| Euclidean SVM   | 0.95   | 0.90             | 0.92     | 0.91               |\n| Hyperboloid SVM | 0.95   | 0.76             | 0.92     | 0.87               |\n| Poincare SVM    | 0.78   | 0.70             | 0.92     | 0.77               |\n| HoroSVM         | 0.98   | 0.91             | 0.93     | 0.92               |\n\n\n> 2. The motivation of classification in hyperbolic space is explained inexplicit.\n\nHyperbolic spaces offer compact representation for hierarchical data, which provides a provable advantage over Euclidean spaces in terms of lower distortion. Classification naturally emerges as one of the standard downstream tasks for data represented in hyperbolic space A naive application of Euclidean methods to hyperbolic data (by regarding the data points to be in Cartesian coordinates) is inadequate, as it neglects the intrinsic geometry of the data. We then aim to design a classification algorithm in the hyperbolic space that respects the underlying hyperbolic geometry and achieves superior performance.\n\n\n> 3. The method in this paper and the compared methods are basically based on SVM.\n\nHyperbolic neural networks may yield higher classification accuracy by providing a holistic solution for classification tasks, encompassing the extraction of rich hyperbolic features from complex network structures and the subsequent application of hyperbolic logistic regression (LR) [16] for final predictions. Our primary focus within this study is not on competing at the feature extraction level – that is, not evaluating which method extracts superior features – but rather on identifying the method that excels as a 'linear' large-margin classifier in hyperbolic space. Moreover, HNNs are not large-margin classifiers and hence do not possess good generalization abilities. Large margin classifiers have a well-established theory and provide performance guarantees. We have provided a framework for such a theory in the hyperbolic space by providing a formulation for the optimization that is geodesically convex and is guaranteed a globally optimal solution similar to the Euclidean SVMs. Thus our comparison is specifically focused on the class of SVMs."}, {"review_id": "httuwvN7OO", "reviewer": "Reviewer_38iz", "summary": "This work studies the support vector machines for data with latent hierarchical relationships, which are represented in hyperbolic spaces. Similar to the linear SVM in Euclidean spaces, the SVM in hyperbolic spaces have been seen in the literature but they are challenging due to some issues such as non-convexity or algorithmic convergence. In this work, the authors explored the analogs between horospheres and Euclidean hyperplanes, and proposed to use geodesic segment (counterpart of the Euclidean distances) to define the margin for the SVM. A nice theory shows the resulting problem is convex so a stable algorithm is developed. Numerical studies demonstrate the superior performance over some competitors. ", "questions": "In Section 4.1, the hyperparameter C is selected from {1, 5, 10}. It might be helpful to comment on how sensitive this parameter is. The performance of a linear SVM is typically highly sensitive to this parameter, and the paper could potentially mislead readers by implying that a non-rigorous selection from only three candidate values would suffice for optimal performance.", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper is working on an integral question for classifying network data. It introduces an interesting idea of defining the SVM on horospheres and shows good performance on benchmark data. In general, the paper appears to be technically correct with sound theory for showing convexity. ", "weaknesses": "1. The authors may comment on the computational speed of the proposed algorithm, as it may outperform Hyperboloid SVM due to its convexity. \n2. From Table 2, it seems HoroSVM well outperforms the other classifiers when D = 2, and the advantage gets smaller when D is large. What is the performance of HoroSVM when D is larger?  Furthermore, it would be useful to discuss how D is chosen in real-world scenarios. \n3. The authors should also compare with the kernel SVM to see if the latent data structure can be implicitly handled by the kernel SVM.\n4. Most datasets chosen for the study display a significant imbalance. It would be interesting to see if it is possible to incorporate cost-sensitive weights into these observations. Doing so could mirror the approach taken by weighted SVM to tackle the imbalance issue.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer 38iz\n\nWe thank the reviewer for the valuable comments and questions. Please find our responses below:\n\n> 1. computational speed of the proposed algorithm\n\nThe complexity of our approach depends on the Riemannian gradient-based optimization technique that we chose to use. In [36], a comprehensive analysis of the complexity of first-order methods was presented. In our case, we use the Riemannian conjugate gradient method, whose algorithm and global convergence analyses are presented in [C2]. Hyperboloid SVM, where a non-convex optimization problem is solved using projected gradient descent, results in a potential local optimum. \n\nFurthermore, we will include the running time on our machine (specs. given in the paper) for each method in Experiment 3 as a reference to the time complexity in the revision. The average training time on our machine for each method on a dataset with 200 samples is as follows: 6.57s (hyperboloid SVM), 3.98s (hyperbolic LR), 9.06s (HNN), and 3.73s (HoroSVM). Notably, our HoroSVM stands out as the fastest. \n\n\n> 2. It seems HoroSVM well outperforms the other classifiers\nwhen D = 2, and the advantage gets smaller when D is large\n\nIt is well known that entangled data in low dimensions may be easier to separate by raising the dimensions. As evident in the  experiments, some of the competing methods yielded higher accuracy improvements with increasing dimensions compared to our HoroSVM. This is to be expected since HoroSVM performed the best in terms of classification accuracy for $D=2$ and hence there was not much room for further accuracy gain to be achieved by increasing dimensions in the HoroSVM case. The strength of the HoroSVM lies in the ability to achieve higher accuracy classification even in lower dimensions where data might be highly entangled. We focus on low dimensions since, as the dimension increases (from 10 to 200), the performance gain of hyperbolic embeddings of graphs is marginal, as empirically evaluated in [23]. Our superior performance in low dimensions is by virtue of the property of hyperbolic space being efficient in representing hierarchical data. Theoretical analysis of our method's generalization error as a function of dimension is an interesting problem and will be the focus of our future work.\n\n> 3. compare with the kernel SVM \n\nWe would like to point out that the only reason for our comparison with linear SVM in Euclidean space is primarily to show that ignoring the geometric structure of data space leads to poorer performance. We will include this reason in the revision. To perform a fair comparison with kernel SVM, one would have to develop a kernel version of SVM in hyperbolic space. We will explore this idea in future work.\n\n> 4. Most datasets chosen for the study display a significant imbalance.\n\nWe have indeed encountered sensitivity while training our HoroSVM on highly imbalanced datasets, similar to the challenges faced by Euclidean SVM. In this work, we used a downsampling strategy that will remove the imbalance at the cost of losing some data but, since the WordNet dataset contains a sufficient number of samples in the minority class, this doesn't significantly affect the classifier  performance. \n\nTo deal with more general imbalanced data, our HoroSVM can be naturally extended to a class/instance-weighted version by assigning a class/instance weight to the penalty term $C$ for each sample, just as it is done in Euclidean SVM.\n\nThe idea of extending our work to a cost-sensitive SVM, as explored in [C3] for Euclidean space, holds significant appeal and promise. We will investigate this direction in future research.\n\n> 5. the hyperparameter C is selected from 1, 5, 10. It might be helpful to comment on how sensitive this parameter is.\n\nThe choice of hyperparameter $C$ is crucial in HoroSVM as it is in linear SVM since it balances misclassification and margin maximization. As is standard in Euclidean SVM, we employ grid search to select the hyperparameter $C$ from a set of candidate values in our method. We acknowledge that this limited set of candidates might not fully explore the optimal range for $C$, and we will include this discussion in the revision. "}]

Author rebuttal:
# General response to all reviewers 
We would like to thank all reviewers for their valuable comments. We are particularly encouraged that they consider the proposed method innovative (1ZfQ), beneficial for future research (cEx8),  that the theoretical result is valid (cEx8, yt6v, 1ZfQ, 38iz), the superior performance in our experiments (cEx8, yt6v, 1ZfQ, 38iz), and that our paper is well-written (yt6v) and easy to follow (1ZfQ).

We have addressed the specific questions raised by each reviewer through separate responses.  Any inaccuracies in presentation or misuse of terminology will be thoroughly clarified in the revision. We value all the reviewers' suggestions for improving the clarity and organization of our work. Modifications according to those reviews will be reflected in the revision as well. We appreciate the insightful discussion about the future direction of this research and will incorporate this feedback appropriately in the conclusion section of the revision.

We appreciate the time and effort that the reviewers spent in assessing our work. We hope that our responses have addressed all reviewers' questions and concerns. Please let us know if there are further questions.

The references cited in the rebuttal use the same indexing as in the submitted paper.

***
References:

[8] Chamberlain et al. Neural embeddings of graphs in hyperbolic space. arXiv:1705.10359, 2017.

[11] Chein et al. Highly scalable and provably accurate classification in poincaré balls. ICDM 2021.

[12] Cho et al.  Large-margin classification in hyperbolic space. AISTATS  2019.

[15] Ganea et al. Hyperbolic entailment cones for learning hierarchical embeddings. ICML 2018.

[16] Ganea et al. Hyperbolic neural networks. NeurIPS 2019.

[23] Nickel and Kiela. Poincaré embeddings for learning hierarchical representations. NeurIPS 2017.

[24] Sala et al. Representation tradeoffs for hyperbolic embeddings. ICML, 2018.

[25] Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. In International Symposium on Graph Drawing, 2011.

[33] Weber et al. Robust large-margin learning in hyperbolic space. NeurIPS 2020.

[36] Zhang and Sra. First-order methods for geodesically convex optimization. COLT 2016.

***
Additional references in rebuttal:

[C1] Izumiya S. Horospherical geometry in the hyperbolic space. Noncommutativity and Singularities: Proceedings of French–Japanese symposia held at IHÉS in 2006. Mathematical Society of Japan, 2009, 55: 31-50.

[C2] Sato H. Riemannian conjugate gradient methods: General framework and specific algorithms with convergence analyses. SIAM Journal on Optimization, 2022, 32(4): 2690-2717.

[C3] Iranmehr A, Masnadi-Shirazi H, Vasconcelos N. Cost-sensitive support vector machines. Neurocomputing, 2019, 343: 50-64.

Meta-review: This paper received three ratings above the acceptance threshold and one below. The reviewer with the borderline reject rating had two concerns (experiment needed on real-world data with noise and motivation). Both were addressed by the authors. Overall, the reviewers find the HoroSVM formulation interesting, the theory solid, and the experiments in order. The AC therefore deems that the paper should be accepted.
Decision: Accept (poster)