Mixed-curvature decision trees and random forests

We appreciate the reviewer’s careful reading of our paper, recognition of our contributions, and detailed edits. In particular, we appreciate the reviewer’s excellent suggestions for relevant literature on mixed-curvature representations, which we have incorporated into our resubmission and which greatly improve our Related Work section.

In the interest of starting a dialogue early, we are posting our response even as we improve our paper, per the reviewer’s comments. We will further post here upon submitting updates to the paper.

We will respond to the remaining comments inline:

The proposed model may have applications in biology: which I believe is true and the authors mention in the introduction, but they do not really test it in the paper.

While we are excited about the applications of mixed-curvature embeddings (and, hopefully, our decision trees) to biological data, we think a full investigation into this application is out of scope for this paper. In our view, this is a methods paper proposing and evaluating a novel method for classification/regression on product manifold-valued data, and therefore we restrict ourselves to well-known datasets embedded using established methods from the literature. We believe this approach is more appropriate to ICLR as a venue, and well-suited for a paper introducing a novel method. An exploration of biological methods is best left for future work, in venues catering to a more biologically-inclined readership. However, we would like to emphasize that we intentionally included several biological datasets across various domains and data modalities in our benchmarks:

• Blood cell type classification (VAE experiments in Table 2)
• Lymphoma case versus control transcriptome classification (VAE experiments in Table 2)
• Allen Brain Atlas neuron spiking prediction (neurons 33 and 46) (Empirical experiments in Table 2)

It seems that the method suffers from similar issues to those discussed in: Neural Latent Geometry Search: Product Manifold Inference via Gromov-Hausdorff-Informed Bayesian Optimization. How does one select the product manifold signature? This should be discussed as part of the limitations. The paper mentioned above suggests using Bayesian optimization to select the signature, for instance.

We thank the reader for this comment, and would like to mention that we are also very interested in the question of signature estimation. We also thank the reader for pointing us to this very interesting paper, which we were not previously aware of. We agree that this work is relevant to the overall project of learning and using mixed-curvature embeddings, and we believe our work is complementary to it insofar as it can help practitioners make the most of high-quality embeddings in downstream tasks.

In our initial submission, we sought to deemphasize the question of signature selection on the grounds that we consider the problem of regression/classification/link prediction to be “downstream” of embedding generation. Since, we additionally have no reason to believe a priori that signature selection and overall embedding quality would systematically bias our evaluations in favor of any particular classifier, we use standard/basic methods from the literature to generate embeddings.

The reviewer is correct to point out that these points are treated implicitly in our paper. We will add a limitations section that makes our position explicit and refers interested readers to the signature estimation literature, and in particular to the reviewer’s suggested paper.

We thank the reviewer for their very positive feedback on the quality of our writing, visualization, and experiments, as well as acknowledging that our research constitutes a meaningful contribution to the literature. We respond to specific comments inline:

While the paper makes a solid contribution, in my understanding, it falls short in terms of significance and novelty. For instance, Section 3, which serves as the core of the proposed method, raises some concerns. Section 3.1 discusses Euclidean decision trees, which is straightforward. Section 3.2 builds on existing research. Although Section 3.3 may introduce a new perspective, the authors themselves describe it as “quite simple”. The choice of does not seem to involve a particularly non-trivial approach. Furthermore, Section 3.4 primarily combines elements from Sections 3.1 through 3.3. While the paper mentions the advantages of redefining decision tree learning through angular comparisons, it is difficult to claim that these benefits are especially significant.

We deliberately pursue algorithmic and mathematical simplicity in our paper, which proves essential for practical applications in non-Euclidean spaces. The proliferation of Riemannian manifold operations in conventional methods, and even the reliance on repeated sparse dot products in tools like HyperDT, are prohibitive for high-dimensional data.

The contributions extend beyond mere simplification. We introduce the first mixed-curvature decision tree, the first mixed-curvature regressor of any kind, and the first hyperspherical decision tree. This perspective is particularly relevant given the prevalence of hyperspherical data in modern machine learning (e.g. any L2-normalized datasets).

The work advances the field of mixed-curvature geometry in several concrete ways:

• It translates a well-known concept (decision trees) into the complicated domain of mixed-curvature embeddings without adding substantial complexity; in doing so, it expands the toolkit available for mixed-curvature data analysis
• It provides an angular formulation of decision tree splits that unifies decision trees of all curvatures
• It establishes a framework for pairwise tasks such as link prediction
• It provides reproducible benchmarks that establish performance baselines for future research

These advances, while building on existing foundations, represent meaningful progress in making non-Euclidean methods more accessible and practical for real-world applications.

Additionally, although the experiments are well-executed, the impact of the proposed method could be better highlighted by including a more diverse set of baselines for comparison. For example, it would be beneficial to compare the method against non-tree models or conventional decision trees applied to real-world data, such as traffic data, without considering manifold structures. Even if the technical novelty is limited, demonstrating significant experimental results would enhance the paper’s relevance to the machine learning community. However, the current experimental results do not sufficiently showcase the advantages of the proposed method.

We apologize for not clarifying that we already compare to conventional decision trees. We do this in two ways: using ambient coordinates (called “Ambient” in our benchmarks), and using tangent plane coordinates (“Tangent”). In the case of Empirical datasets, we sometimes have the option of also training decision trees on pre-transformation data, though the original feature space tends to be very small, as our embeddings are generated by processing datetime features according to cycles of varying periods. We did not include these benchmarks in our paper.

For transparency, we provide an example of such a benchmark here. On the traffic dataset, training a decision tree on the DateTime column without transformations yields an RMSE of 0.80, and breaking the DateTime column into day of week, hour, day of year, and minute columns without transforming yields an RMSE of 0.78. For reference, RMSEs for all regressors on the transformed data are in the 0.45-0.60 range.

I believe it would be helpful to clearly identify the technical differences between your proposed approach and previous research. As I reviewed your method, I struggled to find any significant technical novelty, as indicated in the Weaknesses section. If I have misunderstood something, please kindly let me know.

The technical novelty of our paper consists in presenting a novel perspective on decision trees, yielding a reformulation of the CART algorithm that covers all constant curvatures, recovers the known Euclidean and hyperbolic algorithm, and composes to product manifolds. In our benchmarks, we demonstrate the effectiveness of our approach.

We thank the reviewer for taking the time to review our work. We would like to start our response by respectfully clarifying an apparent misunderstanding with substantial implications for our paper’s significance.

Our key contribution is not to apply decision trees to constant-curvature manifolds (which, as the reviewer points out, has been done in hyperbolic space by HoroRF and HyperDT), but rather to provide the first extension of decision tree algorithms to product manifolds (and hyperspheres). This enables us to perform inference on data with heterogeneous curvature (which is typical of real-world data). While we take inspiration from some prior work in single-curvature manifolds, this is an application to a fundamentally different domain. As such, we believe our paper significantly expands what is possible for practitioners of non-Euclidean machine learning.

We reply to the rest of the reviewer’s concerns inline:

Novelty. The proposed algorithms appear to be a simple and direct extension of previous work [1,2], which integrates the notion of product space proposed by [1] with the HyperDT framework [2]. The method is somewhat incremental and lacks enough novelty.

To our knowledge, our work describes the first extension of decision trees to mixed-curvature spaces, the first formulation of decision trees for arbitrary manifolds of constant curvature, the first mixed-curvature regressor, and the first hyperspherical decision tree. It contributes a substantial new method to the literature on non-neural machine learning techniques in mixed-curvature manifolds (existing methods are only perceptrons and SVMs).

We also demonstrate how decision trees can be thought of and efficiently implemented through an angular reformulation, and how product manifolds can be used to think about pairwise tasks like edge prediction or empirical datasets like Fourier-transformed neural spiking signals.

Applicability. The framework's current restriction to constant-curvature manifolds presents a significant limitation. The applicability to more general scenarios, particularly stochastic-curvature manifolds, remains an open question that warrants investigation.

We are unclear on what is meant by “stochastic-curvature manifolds.” Our approach allows for different constant curvatures in different components, which can capture heterogeneous curvature in real-world datasets.

Comparison. The empirical validation would benefit from a comprehensive comparative analysis against contemporary approaches in the field. Notably absent are performance comparisons with state-of-the-art methods such as HORORF [3] and HyperDT [2].

It is not possible to compare our method to HoroRF and HyperDT, except in product manifolds with a single manifold with curvature -1. Aside from the details enumerated under the Novelty bullet point, our method (with no feature subsampling and timelike-spacelike projections only) coincides exactly with HyperDT for single hyperbolic manifolds (analogously, it coincides with Euclidean decision trees in a single manifold of curvature 0). As our contribution is specifically to perform machine learning on product manifolds, we do not consider HoroRF and HyperDT for benchmarks.

We thank the reviewer for their positive assessment of our paper: in particular, we appreciate their acknowledgment of the novelty of our ideas, the rigor and quality of our presentation, the thoroughness of our benchmarks, and the applicability of our approach to a wide range of domains. We respond to specific comments inline:

One of the main limitations of the proposed method is the computational complexity involved in extending decision trees (DTs) and random forests (RFs) to mixed-curvature product manifolds. The algorithm requires handling several costly geometric operations, such as exponential maps, parallel transport, and angle computations. The paper could be improved by including a detailed complexity analysis and discussing possible optimizations or approximations that might reduce computational overhead. In addition, given the need for complex manifold operations, the approach may struggle with datasets having millions of points or high-dimensional spaces. Including discussions about scalability and memory usage would strengthen the work.

We would like to emphasize that our core algorithm—the mixed-curvature decision tree and random forest—does not rely on manifold operations such as exponential/logarithmic maps or parallel transport. While it does involve angle computations as a preprocessing step, this is actually quite computationally cheap: for basis-aligned splits, it is $O(1)$ per dimension per datapoint (equivalent to e.g. normalizing the data). For each feature in each datapoint, we “project” via two lookups, then compute $\tan^{-1}(d_1 / d_2)$.

All of the costly/repetitive manifold operations either take place for generating embeddings, or as a preprocessing step for the tangent plane decision tree/random forest methods which represent a standard approach to applying Euclidean methods to manifold-valued data. We agree with the reviewer that reliance on computationally-expensive Riemannian methods is a limitation of existing embedding methods, and we have added a Limitations section to our Conclusion that makes note of this; we also believe that the issues the reviewer identifies contribute meaningfully to the relatively low performance of tangent plane decision trees and random forests.

We are adding a complexity analysis to the Appendix to lay out the computational complexity of different variants of our decision trees and contrast with other machine learning approaches. We believe we can make the case for our method more clearly this way, and it helps create a more nuanced discussion of the tradeoffs of hyperparameters such as the number of projections to use. We thank the reviewer for this suggestion.

The paper assumes that the underlying product manifolds have constant curvature components. This may not hold for many real-world datasets where curvature varies continuously or where the data distribution does not fit neatly into hyperbolic, spherical, or Euclidean categories. It could be helpful to discuss how deviations from this assumption impact performance and whether there are ways to relax or adapt this assumption.

The paper assumes that the underlying product manifolds have constant curvature components. This may not hold for many real-world datasets where curvature varies continuously or where the data distribution does not fit neatly into hyperbolic, spherical, or Euclidean categories. It could be helpful to discuss how deviations from this assumption impact performance and whether there are ways to relax or adapt this assumption.

Our primary motivation for exploring mixed-curvature embeddings is precisely that they model heterogeneous curvature in real-world datasets effectively. For instance, consider the simple example of a graph with a circular “backbone” and small trees radiating off of it (as illustrated in Figure 2 of Gu et al (2018) [1]). Such a structure cannot be adequately represented in just hyperbolic or just spherical geometry, nor does a planar embedding suffice. Just as the graph can be factorized apart into trees and cycles, the nodes of this graph can be embedded with low distortion into a product of a spherical and hyperbolic space. The key here is that embeddings do not have to vary uniformly across components: for instance, if some subset of your data has distances that behave elliptically, it could be that their hyperbolic components are all very close together—and therefore contribute very little to the distances—and vice versa.

In our view, product manifolds strike a pragmatic balance the simplicity of constant-curvature manifolds and the expressiveness of general manifolds. However, it is true that product manifolds also cannot embed arbitrary distance matrices with perfect precision, and we have added a discussion of this to the new Limitations section of our paper. We would like to highlight, however, that this nonetheless overcomes many of the representational issues of single manifolds for heterogeneously-curved data.

We thank the reviewer for their detailed and positive appraisal. Their insightful comments demonstrate a clear grasp of our paper's key concepts and contributions, validating their ability to evaluate our work despite their modest self-assessment. We do not find any major misunderstandings in this review, and reply to specific questions and comments inline:

Computational Time is not reported: the authors do not report the compute time that their proposed method requires compared to, say, kNN or the ambient space methods. My guess would be that their method might be a bit more computationally expensive than these. That would be fine though, I think the method is interesting and, even it were considerably more expensive than the other methods, it would still be a worthy contribution that could spark follow up works. I would however encourage the authors to report the time, so that anyone interested in the idea has a sense of the current computational complexity of the method.

We will report empirical computational times alongside a new section comparing the computational complexity of our algorithm to other benchmarked algorithms. In general, our methods are prototypes and therefore slower than well-optimized Scikit-Learn implementations, but asymptotically consistent with decision tree methods like Scikit-Learn decision trees and HyperDT. Our random forests are faster than HyperRF (by a constant factor) because we rely on a single preprocessing step rather than computing angles, sparse dot products, etc., at every iteration.

Motivation: why RF and DT?: To come back to the motivation of the paper, why should we consider RF and DT and not just go with neural networks, for which there have been extensions and can perform better than RF and DT? I could see RF and DT being better alternatives in the low sample regime, or easier/ faster to train. I don't think the authors compare with any NN based method, if Im not mistaken?

Indeed, we did not compare it to any NN-based method in our original draft. We are working on further benchmarks comparing to methods from the graph neural networks literature, which we will add to the Appendix by the end of the rebuttal period. In general, the reasons for preferring decision tree methods include:

• Sample-efficiency in low data regimes
• Appropriateness for mixed-curvature data with unknown graph topology (i.e. everything except the graph datasets in our benchmarks)
• Tractable decision boundaries: unlike neural networks, decision trees’ behavior on the entire data distribution is fully described by their split criteria, and does not require experimentation
• Interpretability: by exploring which component manifolds are most informative for an inference task (by seeing which features the tree splits on), we can determine which aspects of the problem are suited to which task.
• Complexity/speed (each GNN pass requires $O(n^2)$ edge operations, plus $O(n^2)$ space for storing the adjacency matrix, resulting in training and inference complexity of $O(n^2d)$. Our method, on the other hand, has the following complexities (assuming constant max depth is $h$, as we do in our experiments):
  • Training: $O(ndh)$
  • Inference: $O(h)$
• Does not rely on computationally unstable and expensive Riemannian optimization operations

Table 9: Comparison to neural networks on the single-curvature regression task

Table 10: comparison to neural networks on the multi-curvature regression task

Table 11: Comparison to neural baselines on graph node classification, regression, and link prediction tasks