Shadow Cones: A Generalized Framework for Partial Order Embeddings

What do the shape and size of the light source and the size of embedding in the umbral cases imply in the context of partial order or semantics?

This is a very interesting question that we would like to explore with an additional experiment. Specifically, we modified our existing framework to learn source radius from data. Figure 3 and 4 of the supplementary rebuttal pdf show the learned embedding as well as light source radius. For the mammal dataset, the source radius quickly expands from its initial size, resulting in a converged radius that is very large compared to the distribution of learned embeddings. We think this might be a result of the connectivity of the underlying data. The mammal graph has only four disconnected components, and is thus highly interconnected. A large light source can cast large penumbral shadows, making it easier to model highly connected DAGs. In follow-up work, we would be interested in exploring whether different data can induce radius of different sizes, and quantify if there is a relation between source radius and graph connectivity.

How to select one of the 4 proposed methods depending on the situation?

In general, we recommend using shadow cones in the half-space model as there’s no $\epsilon$-hole issue compared to the Poincaré-ball model. If the goal is to represent partial order data with maximal accuracy as represented by the F1 score, then our experiments show Umbral-half-space to be the best method.

If there are requirements or potential benefits from geodesic convexity, we recommend using the Penumbral-half-space cone. For example, if one were to perform interpolations between nodes, then perhaps Penumbral-half-space is superior as it achieves a relatively high F1 score, and its cones are geodesically convex.

For multi-relation embeddings, where one desires to learn the sizes and positions of multiple light sources, each casting a different colored shadow, we recommend the Penumbral or Umbral-Poincaré-ball, because the half-space formulations restrict the size and position of the light source. In umbral-half-space, the light source is placed at infinity, while in penumbral-half-space, the light source is infinitely large. We discussed multi-relation embeddings in Appendix H.

We sincerely thank the reviewer for the thoughtful suggestions on a more representative title. We agree and plan to change our title in the updated manuscript to: Shadow Cones: Unveiling Partial Orders in Hyperbolic Space. We would like to refer the reviewer to our general response, where we explain the performance disparity between Penumbral-Poincaré-ball and entailment cones.

Claim on the Ease of Training

Our training routine is less complicated than that of the Entailment Cone, in the following two ways.

1. While the entailment cone uses pretrained 100-epoch embedding as initialization in order to avoid the $\epsilon$-hole issue in the Poincaré-ball, we simply use random initialization around the origin as a one-stage approach.
2. Our half-space based cones and embeddings have no $\epsilon$-hole issue at the origin, and need no extra steps to project the “stray” points out of the hole.

Relationship between convexity and performance

This is an interesting question. As discussed in Appendix H, future works, we don’t have a clear answer to it now. We expect geodesic convexity to be beneficial for certain types of data and the task objectives, which we would like to explore in follow-up works.

Challenges to learning representation in the half-space formulation There are always precision-related challenges in learning representations in any models of hyperbolic space. Such problems occur when the embedding is near the boundary of the model, i.e., $||x|| = 1$ in the Poincaré-ball model and $x_n=0$ in the Poincaré-half-space model. The limited precision of underlying floating-point computations (imprecision issue) can lead to unbounded error. Yet, the half-space model is already less prone to this issue compared to other models of hyperbolic space like the Poincaré-ball and Lorentz model, as studied in some previous work.

We would like to refer the reviewer to our general response for further comparisons with the box embedding baseline, the reason for the disparity between Penumbral-Poincaré-ball and entailment cones and other downstream tasks.

How the method could be used for real world graphs that are not (exactly) DAGs?

We propose shadow cones as a novel partial order embedding framework in hyperbolic space. Thus, we experiment on datasets with partial orders. Graphs that are not (exactly) DAGs deviate from the field of partial order embedding. For example, knowledge graphs, edge relations in KGs contain symmetric and other more complicated relations, which are not partial orders. Naively encoding them is likely to fail. It’s an interesting and growing area to embed general (not necessarily DAG) graphs within a partial order embedding framework. An example is embedding with minimal spanning trees. Such methods are beyond the scope of this paper.

How the method could be used for multiclass hierarchical problems?

We assume the reviewer is referring to multi-relation embeddings. This can be achieved using multiple light sources, with each light source casting shadows of one color that captures one type of relation. We briefly illustrated this idea in Appendix H. Multi-relation embedding is an exciting direction that we are interested in exploring in follow-up works.

Comparison with methods that do not rely on hyperbolic spaces

We would like to refer the reviewer to our general response, where we compare our proposed shadow cones against box-embeddings, which is a type of Euclidean embedding.

We thank the reviewer for pointing out the missing definition of $P$ (the set of positive relations) and $N$ (the set of negative relations), the error in section 3 paragraph 1, and after theorem 4.2. We will make sure to fix them in the updated manuscript.

Broader Contexts: We sincerely thank the reviewer for kindly suggesting broader literatures to contextualize our work within. We will incorporate discussions and comparisons with the suggested papers in section 2 of our updated manuscript.

Non-trivial downstream tasks: We would like to refer the reviewer to our general response section, where we discussed how cone-based attention could be used to improve the performance of attention models, and offer a simple classification task demonstrating how our partial order embedding captures meaningful structure in the mammal taxonomy data.

Question 3:

First we would like to remind the reviewer that all of our cone formulations are motivated by the same overarching idea: $u \preceq v$ if and only if the (penumbral or umbral) shadow cast by $v$ is a subset of the shadow cast by $u$. The shape of the object (single point, or ball with volume) is dictated by the physicality of different types of shadows, and is not an arbitrary choice. Penumbral shadow, which results from partial eclipse of a light source with volume, is produced by a point object.

On the other hand, Umbral shadow, which results from total eclipse of a point light source, is produced by an object with volume. In order to satisfy the definition of the subset relation of (umbral and penumbral) shadows, we need the ball around objects $y$ to be in the shadow in the umbral cone, but only need the point $y$ to be in the shadow for the penumbral cone.

The Umbral-half-space cone performs the best in general. The reason can be multi-folds, including loss function and optimization process. However, we attribute its main advantage to the infinite-height light source, and lack of $\epsilon$-hole at the origin.

Boundary computation and intuitive explanations why umbral cones are not geodesically convex

As illustrated in the last question, Penumbral shadow, which results from partial eclipse of a light source with volume, is produced by a point object. Therefore, the boundaries of penumbral shadow are geodesics passing through $u$ while being tangent to the light source. Note that the $\text{Penumbral Shadow}(v) \subset \text{Penumbral Shadow}(u)$ for any $v\in \text{Penumbral Shadow}(u)$, therefore, all possible children of $u$, i.e., penumbral cone of $u$ coincides with the penumbral shadow of $u$, with geodesics boundary described above.

On the other hand, Umbral shadow, which results from total eclipse of a point light source, is produced by an object with volume (a ball around $u$). Therefore, the boundary of umbral shadow is geodesics passing through the point light source, while being tangent to the ball around $u$. Now, let’s look at all possible children $v$ of $u$, i.e., umbral cone of $u$. Since the objects $u$ and $v$ have volumes, then for $u \preceq v$ to be true, it must be that $v$ and its ball are entirely immersed in $u$’s shadow. Otherwise, the portion of $v$’s ball outside of $u$’s shadow can cast shadows outside. In Figure 1 of the supplementary rebuttal pdf, we sketch a case where $v$’s center is in $u$’s shadow, but nevertheless $u \npreceq v$, because part of $v$’s ball is outside.

Hence, the boundary of umbral cones are the set of points equidistant from the umbral shadow, aka, hypercycles in hyperbolic space, a well-studied geometric object. In Euclidean space, the set of points equidistant from a straight line forms another, parallel straight line. In contrast, in hyperbolic space, the set of points equidistant from a geodesic do not necessarily form a geodesic, and is instead referred to as a hypercycle. In Figure 2 of the supplementary rebuttal pdf, we illustrate the non-convexity of umbral cones in Poincaré half-space. In green are the umbral cone boundaries, while in black are its convex hull - the minimum convex set - that contains the umbral cone. The boundaries of the convex hull are geodesics. We can see that the umbral cone is a strict subset of its convex hull, which means the umbral cone is not geodesically convex. We will include this illustration in the Appendix.

We thank the reviewer for pointing out the missing definition of $P$ (the set of positive relations) and $N$ (the set of negative relations). We also agree with the suggestion on further explanation of the experimental setup. We will make sure to clarify and explain them in the updated manuscript. We would also like to refer the reviewer to our general response section, where we compare our proposed shadow cones against box-embeddings, which is a type of Euclidean embedding.

Weakness 1: We kindly thank the reviewer for the suggestions on the descriptions. We will update the manuscript to explain all symbols in the figures.

Weakness 2: We believe the reviewer misunderstood our claim: shadow cones generalize hyperbolic entailment cones (Poincaré-ball based) to a broad class of formulations. The hyperbolic entailment cones are mathematically equivalent to a special case of shadow cones, namely, Penumbral-Poincaré-Ball. We understand that the reviewer might be puzzled by the performance difference of hyperbolic entailment cones and Penumbral-Poincaré-Ball, given that the two are mathematically equivalent. We would like to refer the reviewer to our explanation in the general responses.

Poincaré half-space based cones are another category of cones within the shadow cones, which are distinct from the Poincaré-Ball based formulations. We analyzed and discussed why Poincaré half-space based formulations perform better than Poincaré-Ball based formulations in section 5, page 9, [Discussion on the impact of $\epsilon$-hole].

Weakness 3: Different light sources in Penumbral and Umbral cones

We wanted to emphasize that whether the light source has volume is dictated by the physicality of different types of shadows, and is not an arbitrary choice. Penumbral shadow results from partial eclipse of the light source, and could only be produced by light source with volume. Umbral shadow, on the other hand, results from total eclipse of a point light source, and can be produced by both point-like light sources and objects with volume. When both the light source and objects have volume, a third type of shadow is produced - antumbral shadow, which we show in Appendix G to be mathematically equivalent to penumbral shadow formulations.

Experiments on a wider variety of datasets from different domains or those with different characteristics (like KG etc.)

We propose shadow cones as a novel partial order embedding framework in hyperbolic space. Thus, we experiment on datasets with partial orders. We augment our experiments with MCG and Hearst dataset beyond the standard Wordnet benchmark. Datasets from different domains or those with different characteristics are likely to deviate from the partial order embedding area. For example, knowledge graphs, edge relations in KGs contain symmetric and other more complicated relations, which are not partial orders. Naively encoding them is likely to fail. In fact, it’s an interesting and growing area of embedding general relations in a partial order embedding framework, for example, with minimal spanning tree. Hence, we only consider datasets with partial order relations and it’s beyond the scope of this paper to experiment on datasets and tasks from other domains.

We kindly thank the reviewer for suggesting further comparisons. We would like to refer the reviewer to our general response section, where we compare our proposed shadow cones against box-embeddings. We will update the captions of figures to improve the readability.

Reviewers SzVy, s6e6, and JBVb expressed interest in seeing downstream tasks where our proposed shadow cone framework can prove useful.

One promising application is mentioned in section 6: Tseng et al. 2023 (Coneheads: Hierarchy Aware Attention), proposes a shadow-cone based hyperbolic attention mechanism, which can be used as a drop-in replacement for dot-product attention in transformers. Cone attention associates two points by the depth of their lowest common ancestor in a hierarchy defined by hyperbolic shadow cones. Tseng et al. tested cone attention on various models and tasks, and demonstrated how shadow cone-based attention could improve task-level performance over dot product attention and other baselines.

Here, we would like to supplement with a simpler experiment that demonstrates how partial order embeddings capture meaningful structures in data. Given a shadow cone embedding of mammal taxonomy, we are interested in predicting the order of a species. For example, the order of American beaver is rodents, and the order of Bonobo is primates. To construct the classification task, we first find all the nodes in the mammal graph that represent order names. This yields 10 categories, including ungulate, rodent, cetacean, etc. Then, we identify all the species names as the leaf nodes with no outgoing links. Lastly, we predict the category of each species using a softmax probability distribution based on distance. Specifically, we measure the distance between the cone central axis of the species node and those of the 10 category nodes. In the Poincaré-half space model, this distance is simply:

d(x,y)=\frac{1}{\sqrt{k}}\text{arcosh}(1+\frac{||\bf{x}-\bf{y}||^2}{2x_n y_n}), \$$ where we $x_n$ and $y_n$ are both fixed to be 1. Therefore, this distance could also be thought of as the hyperbolic distance confined to the $x_n=1$ plane. We note that the shadow cone embedding optimizes for the entailment relations among nodes, and does not directly optimize this classification task and its loss. Yet a simple distance-based classification achieved an accuracy 94.8%. | model | accuracy | | -------------------- | -------- | | 5D umbral half-space | 94.80% | | 2D umbral half-space | 73.23% |