Mixed-curvature decision trees and random forests

We thank the reviewer for their careful attention, and are grateful for their favorable assessment of our “well-written, clear, convincing text”, our core idea being “novel and interesting,” and our method’s potential to be an “effective, interpretable tool.”

Relationship to signature selection and embedding generation.
We view signature selection and embedding generation as a complementary avenue of work and have tried to keep our discussion focused on classification and regression with existing embeddings. Nonetheless, as these are all parts of one process, we have tried to model simple but realistic end-to-end product manifold learning pipelines, starting e.g. from pairwise distances (for graph benchmarks) or feature tables.
Many other papers emphasize the first half of the pipeline—signature selection and embedding generation—and deemphasize approaches to classification and regression. Our work helps complete the picture by expanding and improving ways to use these embeddings once they are generated. We believe this division of focus allows for directed progress in each area and drives the overall field of non-Euclidean machine learning forward. We are optimistic that advances in either of these subproblems can be combined, e.g. by using mixed-curvature decision trees to analyze state-of-the-art product embeddings.

Algorithm 1 in main body.
We agree that it would be better to include Algorithm 1 in the main body of the paper. If accepted, we will use the extra page in the camera-ready to include this.

Signature selection.
We selected signatures as follows:

• For Gaussians on single manifolds, we try a range of curvatures; on product manifolds, we try signatures with curvatures in $\\{-1, 0, 1\\}$

• For graphs, we grid-search over signatures and use the one with the lowest embedding distortion

• For VAEs, we follow $1$

• For empirical datasets, the signature is determined by the specific problem.

Selecting a signature is combinatorially difficult because the number of components, and the dimensionality of each component, must be selected. Common heuristics for searching over signatures include:

• The curvature parameter can be learned smoothly in the range $$ -\infty, \infty $$ by using stenographically-projected manifolds, as in mixed-curvature VAE

• Signatures can be built up component by component according to a greedy algorithm, as in $4$

• Heuristic-guided Bayesian optimization $3$ is a more principled and sophisticated approach to this

• In general, embedding is reasonably fast; training VAEs is slower

Regarding our claim that “product manifolds are not able to represent all patterns in data,” the authors of $1$ make a theoretical claim about product manifold limitations, but provide no empirical examples. It is reasonable to speculate that complex graphs with heterogeneous curvature might fall into this category, in which case there is a pragmatic question to ask about fidelity-complexity tradeoffs in the choice of representation geometries.

Comparison to GCNs.
One way of using a graph’s adjacency matrix is to generate embeddings via metric learning, as in $2$ ; another is simply to use GCNs using some set of features. These are not mutually exclusive: in fact, generating metric embeddings is roughly comparable to pretraining a GCN on link prediction. A promising future direction of work could involve using our decision trees as lightweight, easily trainable, and modestly interpretable probes on representations learned by pretraining GCNs.

In general, our benchmarks did not generally favor GCNs even in situations where a known graph adjacency matrix was introduced; however, we appreciate that GCNs are in principle capable of substantially more complicated workflows than the ones that we benchmarked. We include the comment about tradeoffs to reflect the geometric deep learning community’s preference for GCNs on complex real-world tasks more than as a reflection of what we see in our own benchmarks: in particular, $\\kappa$-GCNs are never the best-performing method in our own Table 2.

References.

$1$ Borde and Kratsios (2023). Neural Snowflakes: Universal Latent Graph Inference via Trainable Latent Geometries.

$2$ Gu et al (2019). Learning Mixed-Curvature Representations in Product Spaces.

$3$ Borde et al (2023). Neural Latent Geometry Search: Product Manifold Inference via Gromov-Hausdorff-Informed Bayesian Optimization.

$4$ Tabaghi et al (2022). Linear Classifiers in Product Space Forms.

Thank the reviewer for their attention to our manuscript, and in particular for praising the strong performance of our method, the thoroughness of our benchmarks, and the “clear and convincing evidence” of our claims.

Motivation for a tree-based method and our contribution

Tree-based methods are extremely popular for Euclidean machine learning and have recently become popular in hyperbolic spaces as well $1,2$ . We believe tree-based methods can be promising as lightweight, simple, easy to train, and interpretable probes on top of learned neural representations or standalone classifiers/regressors in their own right. Additionally, we address a gap in the literature by providing a detailed survey of product space-valued datasets and predictors:

• We describe and benchmark an end-to-end product space ML pipeline
• We describe many variants of existing models (e.g. kappa-GCN regression) for the first time

We also note $3$ is a well-regarded paper that generalizes Euclidean/hyperbolic GCNs to all constant curvatures and product manifolds.

Theoretical justification for splits

We thank the reviewer for pointing out that our paper’s exposition on geodesic convexity (GC) and why it matters for classifiers is too short. We initially believed that it would suffice to defer to other papers describing linear classifiers in non-Euclidean spaces (e.g. $3$ , $4$ , and especially $1$ , which explicitly argues on behalf of GC). We agree a brief but explicit discussion of the geometry of linear splits and its relationship to GC is needed. If accepted, we will use our extra space to expand on this between Sections 2.1 and 2.2 as follows:

• $S \\subset \\mathcal{M}$ is geodesically convex if any $p, q \\in S$ implies the geodesic $\\gamma\_{p,q} \\subseteq S$. We take this for granted in Euclidean linear classifiers, as any separating hyperplane preserves this property. However, this is not automatically true in non-Euclidean spaces, which could be a source of misgeneralization for models $1,4$ .
• Building on $5$ Ch. 3.1, if $\\mathcal{M}$ is partitioned by GC $G$ into $A$ and $B$, then $A$ and $B$ are also GC. By contradiction, if $\\gamma\_{u,v}$ (where $u, v \\in A$) were to cross into $B$, it must take a path $A \\to G \\to B \\to G \\to A$. This implies the existence of $p, q \\in G$ such that $\\gamma\_{p,q}$ enters $B$, implying $\\gamma\_{p,q} \\nsubseteq G$, violating the GC property of $G$.

$6$ defines a linear split in product manifolds as l\_\\mathbf{w}^\\mathcal{P} \= \\operatorname{sign}(\\langle w\_\\mathbb{E}, x\_\\mathbb{E} + \\alpha\_\\mathbb{S} \\sin^{-1}( \\langle w\_\\mathbb{S}, x\_\\mathbb{S} \\rangle ) + \\alpha\_\\mathbb{H} \\sinh^{-1} ( \\langle w\_\\mathbb{H}, x\_\\mathbb{H} \\rangle\_\\mathcal{L} + b), where $w\_\\mathcal{M}$ means the restriction of $w \\in \\mathcal{P}$ to some submanifold $\\mathcal{M}$.

• Under our angular reformulation, $w$ is sparse in all but two dimensions lying in the same submanifold, with no bias term; thus, the split simplifies to \\langle w\_\\mathcal{M}, x\_\\mathcal{M} \rangle \= x\_0\\cos(\\theta) \- x\_d\\sin(\\theta), where $\\theta$ is our splitting angle, and $d$ is the dimension along which we split. By restricting our attention to two dimensions within a single component manifold at a time, our angular reformulation approach bypasses almost all the complexity of performing geodesic splits in product manifolds.

Clarifying experimental details

• We show means with 95% confidence intervals in our tables
• We use 10 trials for each experiment
• Seeds are shared across RFs for splitting, but each trial uses a different seed. For instance, in figure 3:
  • Seeds 0-9 are used for K=-4, 10-19 for K=-2, 20-29 for K=-1, etc

Low dimensionality

We benchmark lower-dimensional embeddings, as these are more challenging and rely more heavily on the classifier’s ability to match the geometry of the space. However, we agree that it is worth evaluating higher-dimensional datasets; therefore, consistent with $3$ we have benchmarked manifolds with 16 total dimensions at https://postimg.cc/MvR5R8Pp, which we will add to the Appendix.

Tangent vector space

• Thank you, we have fixed this.

Missing neural net benchmarks

Thank you for pointing this out, we have a full suite of benchmarks at https://postimg.cc/gallery/ZbfzMzR. We will add the full benchmarks to the Appendix in the camera-ready.

References:

$1$ Chlenski et al (2024). Fast Hyperboloid Decision Tree Algorithms.

$2$ Doorenbos et al (2024). Hyperbolic Random Forests.

$3$ Bachmann et al (2020). Constant Curvature Graph Convolutional Networks.

$4$ Cho et al (2018). Large-Margin Classification in Hyperbolic Space.

$5$ Urdiste (1994). Convex Functions and Optimization Methods on Riemannian Manifolds.

$6$ Tabaghi et al (2022). Linear Classifiers in Product Space Forms.

We thank the reviewer for their time and for acknowledging our “novel integration of mixed-curvature geometries into DTs/RFs” and its “potential for applications in hierarchical or graph-structured data,” and for praising its effectiveness in single-manifold settings.

Added benchmarks Per the reviewer’s suggestions, we have re-run our benchmarks:

• We have added ensembles of single-manifold trees, which generally underperform our method
• We have included F1-macro scores for classification
• For transparency, we include all neural models.

Accuracies, F1 scores, and MSEs can be found at https://postimg.cc/gallery/ZbfzMzR.

Clarifying benchmark assumptions

The reviewer suggests that Table 1 contradicts our performance claims. Table 1 shows that our method does well both in problems involving single-curvature and product manifolds; these are different problems, not different methods; therefore, they cannot be contrasted in this way. In particular, our benchmarking setup assumes a manifold is already given. For instance, given a dataset with signature H2 x E2 x S2, our only choices are:

• Coerce to E8 (Ambient models)
• Coerce to E6 (Tangent models)
• Coerce to one of {H2, E2, S2} per tree (single-manifold tree ensemble)
• Our method

Of the above, ours is the only method for training a decision tree without coercing to a different geometry.

For details about our selection of signatures, please refer to our discussion with 3Gbp, subheading “Signature selection.”

Comparison to single-manifold decision trees

We justify our choice not to use single-manifold trees in our paper:

Letting a single DT span all components—as opposed to an ensemble of DTs, each operating in a single component—allows the model to independently allocate its splits across components according to their relevance to the task at hand

Nonetheless, we agree it is better to verify. In our benchmarks, these ensembles tended to underperform other models, including ours. Furthermore, because designing an ensemble of single-manifold decision trees relies on the constant-curvature decision trees we describe in Sections 3.1–3.3, this method is still a novel contribution of this paper.

Theoretical justification

• For an elaboration on geodesic convexity and decision boundaries, please refer to our discussion with SX2z, subheading “Theoretical justification for splits.” In brief, we explain and commit to updating our manuscript with:
  • A definition of geodesic convexity
  • A proof sketch for why geodesic splits partition manifolds into geodesically convex subspaces
  • The equation for geodesic splits in product manifolds
  • Citations for each component manifold being split by homogeneous hyperplanes
  • An explicit connection between geodesic splits and our angular reformulation, clarifying that our splits are fully contained within one of the component manifolds, bypassing the complex interactions between component manifold geometries
  • A more explicit restatement of the relationship between this and the discussion of geodesic convexity in hyperbolic decision trees (HyperDT)
• Optimization details:
  • We modify CART, a greedy algorithm without optimality guarantees $1$ . The overall behavior of the algorithm is left intact. Moreover, constructing optimal DTs is known to be NP-hard $2$ .
• Tangent DTs/RFs:
  • We directly use the method used in $3$ : apply the log-map at the origin and then train Euclidean DTs/RFs on that. We highlight Section 4.3 for a description.
  • Eqs. 1 and 12 are necessary for extending the log map to product manifolds, enabling the use of tangent DTs/RFs

Clarifying writing

• We commit to rewriting the caption for Table 1 to make it clearer that the manifolds represent aspects of the problem, not of the approach used, to prevent future confusion
• We will consolidate Section 2 for clarity; more specific editing suggestions are greatly appreciated.
• Model details: detailed descriptions for Tangent DTs/RFs, as well as neural net benchmarks, can be found in Appendix E; we will expand Appendix E to be even more detailed.
• We will add the citations from our reply to SX2z.

Algorithm 1 curvature handling

Alg. 1 intentionally omits curvature handling because only the sign of the curvature (i.e. manifold type) is needed to compute midpoint angles under our formulation.

Clarifying Appendix C

The reviewer claims “Synthetic results show unclear performance trends / mixed performance; no ablation on manifold combinations” in Appendix C. However, Appendix C is actually a proof of equivalence for the Euclidean case. We request the reviewer clarify this statement.

References:

$1$ Hastie (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction.

$2$ Hyafil and Rivest (1976). Constructing Optimal Binary Decision Trees is NP-Complete.

$3$ Chlenski et al (2024). Fast Hyperboloid Decision Tree Algorithms.

We thank the reviewer for their favorable comments on our manuscript, including our “clear and convincing” claims, “good results,” and the “extra effort required to establish” performance on real-world benchmarks

Selection of benchmarks.
Our work makes the admittedly strong assumption that we are working with product manifold-valued data, and our method relies on having product manifold-valued inputs in hand. Although we have tried to create as broad a set of benchmarks as possible, we acknowledge that this can be a limitation of the product manifold approach to machine learning as a whole.

In our paper, we try to model what end-to-end approaches to machine learning on product manifolds might look like, including examples of how different types of datasets can be converted to product manifold coordinates. We hope that, in addition to supporting the value of mixed-curvature decision trees, our paper can serve as an instructive guide for researchers who are intrigued by product manifolds but aren't sure how these concepts apply to their own datasets. An additional advantage of product manifolds is they recover single-manifold and Euclidean geometry as special cases: thus, all single-manifold problems can trivially be viewed through the product manifold lens.

More generally, $1$ describes a method based on sectional curvature to determine whether a graph warrants a product space representation; in such cases, we would expect:

• Product-space representations to model the data substantially better (in terms of distortion, classification accuracy, etc) than single-manifold representations, and
• Our methods to be effective for classification/regression

We always welcome suggestions for any further benchmarks that can be formulated in terms of product manifolds, particularly those from application areas not included in our original manuscript.

Suggestions for applications.
Per the reviewer’s request, we also provide an incomplete list of some situations in which product manifold approaches can be helpful:

• Many non-Euclidean machine learning problems involve multiple manifolds. For instance, $2$ describes hyperbolic convolutional neural networks, in which each channel is hyperbolic. To combine representations in multiple channels, they propose a variant of vector concatenation that stays on the hyperboloid. An alternative way to view this would be that the channels form a product space of individual hyperbolic representations.
• Similarly, pairwise (or higher-order) interactions between data points with non-Euclidean representations can be recast in terms of product manifolds. An example of this is our reformulation of link prediction as binary classification on a product manifold of (outbound node, inbound node) pairs.
• To embed pairwise distances or other pairwise dissimilarities, one may use the coordinate learning method described in $1$ . This is a popular approach to embedding graphs, where heterogeneous curvature can make single constant-curvature manifolds inadequate. Our graph benchmarks follow this approach.
• To embed features without known pairwise distances, mixed-curvature VAEs can be useful, as in $3$ .
• We are particularly excited about biological applications of product manifolds, which have been a popular application area for hyperbolic deep learning $4$ , and where complicated latent structures can give rise to heterogeneous curvature. For instance, we follow $5$ in using mixed-curvature VAEs to embed single-cell transcriptomics data. We speculate that in such datasets, differentiation trajectories may embed in hyperbolic space, whereas periodic signals (e.g. those pertaining to the cell cycle) embed in hyperspherical space. Empirically, $5$ finds that single-cell data embeds better into product manifolds than single manifolds, and $6$ embeds pathway graphs in product manifolds.

References.

$1$ Gu et al (2019). Learning Mixed-Curvature Representations in Product Spaces.

$2$ Bdeir et al (2024). Fully Hyperbolic Convolutional Neural Networks for Computer Vision.

$3$ Skopek et al (2020). Mixed-curvature Variational Autoencoders.

$4$ Khan et al (2025). Hyperbolic Genome Embeddings.

$5$ Tabaghi et al (2022). Linear Classifiers in Product Space Forms.

$6$ McNeela et al (2023). Mixed-Curvature Representation Learning for Biological Pathway Graphs.