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.
After 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.
With 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.
Lastly, 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.
Strengths
The paper contains several, mostly theoretical strengths in my opinion:
1. 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.
2. 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.
3. 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.
4. 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:
1. 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?
2. 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.
My concerns regarding the experiments (mostly experiment 1) are:
1. 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.
2. 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.
3. 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?
4. 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.
5. 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?
6. 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?
Questions
Alongside the questions posed in the weaknesses above, I have a few additional questions:
1. 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.
2. 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.
3. 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.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
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.