Shadow Cones: A Generalized Framework for Partial Order Embeddings
Authors: Tao Yu
Toni J.B. Liu
Albert Tseng
Christopher De Sa
Venue: ICLR 2024 poster (2024)
Keywords: partial order embedding
hyperbolic space
shadow cone
representation learning
entailment cone
hierarchy
Primary area: representation learning for computer vision, audio, language, and other modalities

Abstract: Hyperbolic space has proven to be well-suited for capturing hierarchical relations in data, such as trees and directed acyclic graphs. Prior work introduced the concept of entailment cones, which uses partial orders defined by nested cones in the Poincar\'e ball to model hierarchies. Here, we introduce the ``shadow cones" framework, a physics-inspired entailment cone construction. Specifically, we model partial orders as subset relations between shadows formed by a light source and opaque objects in hyperbolic space. The shadow cones framework generalizes entailment cones to a broad class of formulations and hyperbolic space models beyond the Poincar\'e ball. This results in clear advantages over existing constructions: for example, shadow cones possess better optimization properties over constructions limited to the Poincar\'e ball. Our experiments on datasets of various sizes and hierarchical structures show that shadow cones consistently and significantly outperform existing entailment cone constructions. These results indicate that shadow cones are an effective way to model partial orders in hyperbolic space, offering physically intuitive and novel insights about the nature of such structures.

Published as a conference paper at ICLR 2024
SHADOW CONES: A GENERALIZED FRAMEWORK FOR PARTIAL ORDER EMBEDDINGS
Tao Yu", Toni J.B. Liu", Albert Tseng, and Christopher De Sa Cornell University (ty367, j13499, at676, cmd353) @cornell.eeeeeee
ABSTRACT
Hyperbolic space has proven to be well-suited for capturing hierarchical relations in data, such as trees and directed acyclic graphs. Prior work introduced the concept of entailment cones, which uses partial orders defined by nested cones in the Poincaré ball to model hierarchies. Here, we introduce the "shadow cones" framework, a thysics-inspired entailment cone construction. Specifically, we model partial orders as subset relations between shadows formed by light source and opaque objects in hyperbolic space. The shadow cones framework generalizes entailment cones to broad class of formulations and hyperbolic space models beyond the Poincaré ball. This results in clear advantages over existing constructions: for example, shadow cones possess better optimization properties over constructions limited to the Poincaré ball. Our experiments on datasets of various sizes and hierarchical structures show that shadow cones consistently and significantly out- perform existing entailment cone constructions. These results indicate that shadow cones are an effective way to model partial orders in hyperbolic space, offering physically intuitive and novel insights about the nature of such structures.
INTRODUCTION
Modern machine learning methods favor continuous data representations, as such representations can be easily used in differentiable deep models. Yet real-world data is often discrete; for example, text is composed of characters and words, and graphs consist of nodes and edges. This gap has resulted in a wide variety of embedding methods that map discrete data into continuous spaces. Popular methods such as word2vec (Mikolov al. (013) and GloVe (Pennington al.. 2014) approach this problem by mapping into high-dimensional Fuclidean spaces, which capture complex relations between data by using many dimensions.
However, not all data can be well represented in Euclidean Space [Bronstein al. 2016 Sala et al. 2018). Hicrarchical and graphical data, such as biological phylogenetic trees and social networks, are more naturally modeled in hyperbolic space (Sarkar 2012 Sala et al. 2018). In hyperbolic space, the volume ball grows exponentially for large radius, which matches the number of nodes in tree; in contrast, this volume grows polynomially in Euclidean space (Yu & De Sa 2019). This volume advantage has made hyperbolic space popular for embedding hierarchical data, such as done in Ganea et al. (2018); [Balazevie al. (2019): Li et al. (2022): Bai al. (202T).
In this work, we focus on learning embeddings that capture partial orders on a set of data points X. In partial order, certain pairs of points u, v E X possess entailment relations. That is, if u, u an ancestor of v. Many hierarchical structures such as directed acyclic graphs (DAGs) can be expressed as partial orders, making partial orders popular tool to represent such structures with (Vendrov et al. 2015, Ganea et al.) (218).. Furthermore, since not all pairs u, v E X need to be comparable (hence "partial" nomer), partial orders are especially useful for graph prediction tasks, where multiple embeddings with different properties can exist for single partial order over a set.
We propose a novel and physically intuitive partial order embedding framework, which we call the "shadow cones" framework. Shadow cones use set of hyperbolic cones derived from shadows formed by light sources and opaque objects in hyperbolic space. Entailment relations between objects are
"quual contributions.

---

Published as a conference paper at ICLR 2024
x x32 y y
u 3 V
8
n, a
|| w
x y
Figure 1: Example of two sets of shadow cone embeddings in the Poincaré ball, and the partial relations it encodes. Marked in black are the encoded partial relations, while blue are the embeddings, w and æ, y. 2. Marked in red are the light source (S), and the dotted geodesics representing light rays. Shaded areas represent shadows. The symbol "Il" denotes negative relations between unrelated, incomparable elements.
modeled by subset relations between shadows, similar to how planets block each other out during solar eclipses. Shadow cones be seen generalization of existing approaches that hyperbolic cones to model partial orders ("entailment cones"), and are agnostic to choice of hyperbolic model. This results in better numerics and optimization properties, which allow shadow cones to empirically outperform existing entailment cone constructions on a wide variety of graph embedding tasks.
In the following sections, we present formal constructions of shadow cones in the Poincaré ball and half-plane. Our main contributions are that we:
Introduce the shadow cones framework to model partial order relations, and detail two self- contained formulations in two hyperbolic models, resulting in four embedding schemes.
Define differentiable energy function measure disagreement between ground truth partial orders in data and those induced by shadow cones.
Achieve state-of-the-art results on wide range of graph embedding tasks, lending both empirical and theoretical support the advantages of all four embedding schemes.
2 PRELIMINARIES AND RELATED WORK
First, we define some key concepts in hyperbolic geometry. Hyperbolic space H is the unique simply connected Riemannian manifold with constant negative curvature -ki, k: >> (Anderson) 20066) There exist multiple models H that are isometric to each other. This work uses two such models, the Poincaré ball and the Poincaré half-space:
The Poincaré ball is given by 2 = {x E R= ||~||| < 1/vRj. Distances on are defined as
k x
y|
ds(æ, y) = arcosh
1 1+ (1 kl
2) 1)
The Poincaré half-space is given by 2t = fx E R"; : En > 0}. Distances on Ut are defined as
[ || y/
dx( v)
arcosh
Vi
2I
Geodesics are Riemannian generalizations of Euclidean straight lines. They are defined smooth curves of locally minimal length connecting two points æ and y on a Riemannian manifold M. More concepts of hyperbolic geometry provided in Appendix A
We now review several approaches to embedding partial orders and other hierarchical relations in Euclidean and hyperbolic space. Order embeddings were first introduced by Vendrov et al. (2015) to model partial orders in Euclidean space. /Vendrvv et al. (2013) defined entailment relations as subset relations between axis-parte axis-parallel cones embedded points; that is, x iff the cone of C the cone
2

---

Published as a conference paper at ICLR 2024
of However, since all axis- axis-parallel cones eventually intersect, order embeddings are incapable of model nonoverlapping categories, such as "canine" and "feline" in a taxonomy. Since volumes in Euclidean space only increase polynomially, sets of infinite cones are prone to heavy intersections. This results in provably limited space for disjoint regions that are necessary to model negative relations (u v). More recently, Zhang et al. ) Boratko et al. (022)) proposed box embeddings in Euclidean space using subset relations between axis-parallel boxes, to represent entailment relations. Yet these methods are subject the drawbacks of Euclidean space, limiting their expressivity.
The "crowdedness" of Euclidean space places fundamental limits on its representation power for deep and wide hierarchical structures (Sala et al.) 2018). On the other hand, volumes in hyperbolic space grow exponentially, giving clear advantages for embedding hierarchies. Many works have explored the utility of hyperbolic embeddings for hierarchical data through likelihood scoring functions (Nicell & Kiela, 2017, 2018) Yu & De Sa. 2019)] (Chami et al. 2020). For example NNckel & Kiela (2017) used the following heuristic composed of norms and distances to rate the likelihood of Is-A relationships: score (Is-A(u, v)) -(1 + a(||v|| - Il uu, v). However, such approaches are limited, as they do not explicitly model partial orders and cannot easily recover learned hierarchies.
Ganea et al. (0188) introduced the concept of entailment cones, which models entailment relations by subset relations between cones rooted at points. Formally, an entailment cone at x E X, 62. is defined by mapping convex cone S from the tangent space M to HH using the exponential map G₂ = (S), c T.M- = H. Different choices of 5 give different sets of entailment cones for X. While emtailment cones offer strong empirical performance, they also suffer from initialization issues that hinder optimization. For example, the specific construction presented in Ganea et al. (0118) leaves s-hole at the origin of the Poincaré ball where cones are undefined, and care must be laken to ensure that embeddings do not land in the e-hole (Ganea et al. 2018). To mitigate this issue,
Ganea et al. (2018) initialize embeddings with pretrained embeddings from (Nickel & Kiela 2017).
However, this approach constrains the representational capacity of entailment cones and complicates performance analysis, as it deviates from being a self-contained framework.
Ganea's entailment cones are a special case of our "penumbral shadow cones" (section 3.2) in the Poincaré ball, and our framework provides an intuitive explanation of why this e-hole exists Additionally, our shadow cones framework allows for constructions that do not suffer from the e-hole problem: in Section 3.2 we will see that we can do this by instead defining penumbral cones in the Poincaré half-space and mapping the light source to infinity. Our experiments show that penumbral cones in the Poincaré half-space consistently outperform Ganea et al. (2018)'s 's strong baselines.
SHADOW CONES
The shadow cones framework defines entailment relations using shadows cast by a light source S from opaque objects representing embedded data points. The general idea is to geometrically represent the partial relation using subset relation between shadows: we say u = v when the "shadow cast" by a subset of the "shadow cast" by u. Note that this embedding scheme automatically satisfies the transitivity of partial relations since subset relations are inherently transitive. However, explicitly characterizing the subset relations between shadowed regions is complicated. introduce shadow cones which reduces region- region subset relations to point-region membership relations. Specifically,, v is in the shadow cone of u iff the shadow o C the shadow of u. (Figure[])
this section, we
We categorize shadow cones into two types of cones, depending and penumbral. In umbral cones, the light source S is a point and data points are represented by objects with volume. Conversely, in penumbral cones, S has volume while data points volumeless points. The exact shape of shadow cones depends on the shape and position of S and the objects associated with data points. In the following sections, we adopt S with shapes and positions that result in axially symmetric shadow cones. Given that hyperbolic space is endowed with continuous isometries capable of transforming non-axially symmetric placement of light sources into axially symmetric ones, our focus on symmetric cases greatly simplifies computations while at the same time do not lose any generality. We defer further discussions on isometries to Appendix D
the type of shadow used: umbral
'Specifically, it corresponds to the interior of the "light source" inside which shadows are cast (Remark)
3

---

Published as a conference paper at ICLR 2024
3.1
UMBRAL CONES
We provide constructions for umbral cones in the Poincaré ball and half-space models. In both constructions, embedded points are centers of associated hyperbolic balls of radius r. In both models, these hyperbolic balls correspond to Euclidean balls with shifted centers.
Definition Given a point light source S and points x, y E H. we say that y is in the radius-r umbral cone at x if for every point in the (hyperbolic) ball of radius r centered at y, every geodesic between u and S passes through the (hyperbolic) ball of radius centered at z.
This definition formalizes the notion that the ball centered at y is entirely in the shadow of the ball centered We provide several equivalent definitions of shadow cones in Appendix C with a detailed analysis. Fach resulting umbral cone is a subset of the umbral shadow, enclosed by equidistant curves (i.e., hypercycles) the boundaries of the umbral shadow. We detail umbral cones and the boundaries in the Poincaré half-space and ball model separately below.
Formulation 1: Umbral-half-space We illustrate the shape of um- bral cone when S is placed at F, = oo in the Poincaré half-space. Light travels along vertical ray geodesics in the direction e,, (0. 0, 11). The central axis of the cone induced by u is then Au {w11.-. ...., un- J.n ]n < In S un). In the Poincaré half- space model, the hyperbolic ball of u. is Euclidean ball with center
S
en
Cn (u....., 1, Un cosh v /r) and radius re Un sinh vkr, where - is the curvature of H. Thus, the shadow of u's ball is the region directly beneath its object, equivalently, the region within Euclidean distance Te from its central axis. Note that the umbral cone is subset of this shadow, as the entire ball of v needs to be in this shadow for v > u.
u
l
This umbral cone is better characterized by studying its boundary. Note the set of light paths tangent to the boundary of u's ball is (Z.,....,,,, -I.1. t) (z, 2 = r², t > 0}. Let / be such light path, then one boundary of the umbral cone is the curve equidistant to I, and passing through u (i.e., hypercycle with axis 1). Since is ray-geodesic, its equidistant curve is the Euclidean straight line through u and I's ideal point on the x, = O-hyperplane. Thus, the umbral cone of u is also a Euclidean cone with u as its apex and base on the xn O-hyperplane with Euclidean radius re. The Poincaré half-space is conformal, so the half aperture of this cone is on aretan (re/un, arctan sinh (Vkr), which is fixed across different u. This allows us to test if u 2 v by simply comparing the angle between v u and en.
Figure Umbral hallllhha---aa half-space em- heddings of partial relation u 3 v. Marked in red are light source at infinity (S), directions of light (e.)), and geodesic shadow bound- aries (I). Blue is the object, and green the shadow cones
br
We now discuss the bral cone when S is placed at the origin of the Poincaré ball model which emits light along the radii. The umbral cone is symmetric with central axis A {pu(1 1 S p < 1/(Vk) =]l))-
Formulation 2: Limbral-Poincarébbar
Again, we characterize the umbral cone by looking at its boundary. Let ( be a light path tangent to the boundary of u's associated ball. Assume iitersects with the boundary at two ideal points by. b where be is closer to u than by. The corresponding boundary of the umbral cone is the curve equidistant to 1, and passing through (i.e., hypercycle passing through with axis 1). This an are passing through three points: by. br, u. Thus, the related boundary of the umbral cone is the arc segment ub. (see Figure
be ball
Figure 3:
embeddings of relation u I u.
3.2 PENUMBRAL CONES
"Same notations and symbols apply to Figures 2-5.
"Again, fixing the light source the origin causes no loss of generality, for reasons discussed in the appendix.
4

---

Published as a conference paper at ICLR 2024
For penumbral cones, S is convex region, while embedded points are points of no volume. We define the penumbral shadow of u as the region delineated by geodesic rays tangent to the light source's boundary aS and passing through us Consequently, u I v iff is in the shadow of u.
Definition 2. Given a convex light source and points æ, y E HiI, we say that y is in the penumbral cone at x if the geodesic ray from y through x passes through S.
Bu
This definition formalizes the idea that z occludes some part of the light source as seen from y.
Figure 4: emheddings of relation u 3 u.
Poincaréébal
We adopt a hyper- bolic ball of radius r be the light source. We parameterize the cone in the Poincaré ball model, and without loss of generality (up to an isometry), we place the center of S at the origin. The penumbral cone in this case symmetric with central axis A
Formulation 3:
Let I be an are geodesic tangent to the light source's boundary as at w and passes through u. Then the penumbral cone induced by axially-symmetric, with one boundary being the segment of I starting from u. The half aperture of the penumbral cone with apex u can be derived by applying the hyperbolic laws of sines (Appendix A to the hyperbolic triangle ASwu, with /Swu //2. The half aperture is then:
sinh Ver 0_ = aresin
sinh v Vkdg(u.S)
To test the partial order of any u. v, we need to compute the angle of 2) between the cone central axis and the geodesic connecting u, v at u, i.e., π -OOv, which given by Ganea et al. (2018) as
(u, v) + 1 11 ||2 2 (1 + & ||001
s(v, u) = arccos
|| ||u m11 v + 2:2 ||/||
2 ||011² - 2k:(1,, (1, v)
One can test whether u = simply by comparing Φiv, u) with the half aperture On. Note that larger radius r leads to wider aperture O.., which implies larger numbers of children. In Appendix (H.2 we make r learnable parameter, and observe curious relation between the optimal radius and connectivity of the embedded dataset.
Formulation 4: ceuumbral-hall-spaee The penumbral shadow cone framework is very general and do not restrict the shape of the light source. Here we introduce one more formulation with the light source shaped as horospheres (Izumiya 2009). which are hyperbolic analogs of hyper- planes in Euclidean spaces. In the Poincaré half-space model, horosphere is either sphere tangent to the n,, 0- O-hyperplane at an ideal point, or a Euclidean hyper-plane parallel the z, 0- hyperplane. We use the latter as it induces symmetric shadows. In particular, we consider horospheres {(01, ... -n- vie V 3/ 0}. whose boundaries 0S are parallel to and with distance from the x, = O-hyperplane.
S
Consider a half-circle geodesic / tangent the horosphere light source, that passes through u and ends up at infinity. Then the bound- ary of the penumbral cone induced by u is the segment of / between t and infinity, that is, the Figure The central axis of the cone AMd. With some basic geom- etry, we derive the half aperture as 02 aresin (un/(VkevRR))
u
0- O-hyperplane. This is illustrated in
Similarly, we compute the angle d(v, u) between the cone central axis and the geodesic connecting u, v at u, i.e., the angle between log,( (v) and ea, where log is the logarithm map in the Poincaré half- space model, the formula of which is provided in Appendix
v
Figure 5: Penumbral-hai haatsss-a------cccccoo
3.3 SOME PROPERTIES OF SHADOW CONES
embeddings of relation a < v.
We discuss some key properties of shadow cones in this section.
5

---

Published as a conference paper at ICLR 2024
Table 1: Properties of four shadow cone formulations
Cone
Model
Form. #
Emb. Type
Convex?
Light Source
0g
Half-Space
1
Ball
No
Point at co
Fixed
Umbral
Poincaré Ball
2
Ball
No
Point at Origin
Varying
Poincaré Ball
3
Point Yes
Ball at Origin
Varying
Penumbral
Half-Space
4
Point
Yes
Horosphere
Varying
Theorem 3.1. The shadow cone partial orders are transitive, i.e., if 3 v and v 3 w. then u 3 w.
This theorem follows immediately from the fact that the shadow cone relation induced by the subset relation on shadows; rigorous proof of this theorem is provided in Appendix C The shadow cone framework is thus well-suited framework represent partial orders. In fact, shadow cones generalize entailment cones to broad class of formulations, and the existing entailment cones in Ganea et al. (2018) is special case of shadow cones, specifically, Formulation 3.
Theorem 3.2. Entailment cones (Ganea al.) 2018) are equivalent to Formulation 3, penumbral cones with a hypperbolic-ball-shuppp light source at the origin.
We prove this equivalence Appendix As discussed in Section 2 the g-hole problem of Ganea et al. (2018)'s is entailment cones is a serious limitation of the model. Here, we give an intuitive explanation this e-hole problem around the origin in the shadow cones framework.
Remark (Hole around the light source). The shadow not defined when the light source intersects with the point u (and its associated ball for umbral cones). We therefore require dy, > which results a hole of hyperbolic radius r centered S.
Umbral and penumbral cones also differ in many aspects that make them suitable for different purposes. For example,
Theorem 3.3. Penumbral cones are gendesically-convex while umbral cones are not due to the hypercycle boundary (Appendix B and C).
The half aperture of umbral cones are fixed for Vu E H. while that of penumbral cones become smaller as u approaches the O-hyperplane. We note that the hyperbolic radius and the level h in penumbral cones can be trainable parameters or even a function r(u) and /uu) in the space. However, in our main experiments, we treat them constants. A summary of these properties can be found in Table
Apart from umbral and penumbral shadows, there are also antumbral shadows, which are formed when both the light source and objects have volumes. The cones induced by antumbral shadows are mathematically equivalent to those induced by penumbral shadows, which we discuss in Appendix
4 OPTIMIZATION WITH SHADOW CONES
In this section, we use our shadow cones to design an algorithm for embedding partial relational data. Given a dataset containing partial orders between pairs of elements, we seek to learn an embedding of all elements, such that the shadow cone framework can be used to evaluate the encoded partial order, and infer missing partial orders from the dataset.
A key component in learning with shadow cones is a differentiable energy function, loss function, which quantifies both the confidence of correctly classified pair (u, v),, and the penalty associated with incorrectly classified pair (u, v'). We propose to use the hyperbolic distance between v and the shadow cone of u as energy function.
The shortest path from to the shadow cone induced by can be classified into two distinct cases: (1) if v is at higher "altitude" than u, i.e. the apex of the cone, then the shortest path to the cone is the geodesic from to the apex of the cone; (2) if is at the same "altitude" or lower than then the shortest path to the cone is the shortest geodesic from o to the cone's boundary. Figure 6 illustrates the two distances for the umbral-half-span formulation.

---

Published as a conference paper at ICLR 2024
u V/
u
Ep
u
altitude-O
E W
V1
Ey
E
W
Figure 7: A toy optimization example: u 3 v, u w. (Left) v a child of u, but wrongly initialized outside of u's cone. w is incomparable with u but is initialized inside the cone. (Right) The energy gra- dients pulls inside the cone, and pushes outside. Red denotes positive energy. and blue negative.
Figure 6: Shortest distances to u's cone in umbral- half-space, as computed differently for negative (21) and positive (v2) altitude points respectively.
To easily check which distance measure to use, we introduce a relative "altitude" function, Hu,, u). If (0, u) > O, then is at higher altitude than the apex of u s' cone, corresponding to case 1. Otherwise, we are in case 2. we present this relative altitude function along with the shortest distances the cone, using the mabral-half-ssace formulation. We leave the discussion of other cases, such as penumbral cones, and detailed derivations to Appendix
Define temperature ( E (w: u,) uh, sinh //r/////// En. then the relative altitude function of with respect u is H u) = v (1 ule cosh /kr. Theorem 4.2 (Shortest Distance to Umbral Cones), For umbral cones with temperature t and relative function is Vh. arsinh(t) r. Thus, the
Lemma 4.1 Clmbral-half-spee
altitude function H (v, u). the figneeddiitanncett-bouueee
shortest distance from v to the umbral cone induced by u
du(u, v) VI arsinh(t) +r if H( , u) S.
H u) > 0,
d(v Cone(u))
We note that the sign of distance-to-
serves as another way to test partial order of u.
To learn embeddings
geometrically meaningful manner, we introduce "shadow loss", which designed to draw child nodes v closer to the cones of their patent nodes u while simultaneously pushing away randomly sampled, negative child nodes v':
exp( (aax(EE(u,e 02))
C =
Σ log Eiw exp(max((1 Elu', 0)),
(1)
(u,D)EP
where P is the edge set of positive relations, N that of negative relations, and E(u. v) d(v, Cone(u)) is the two-case distance defined previously. In addition, this loss allows us to choose how far push negative samples away from the cone (distance ?1 O), and how deep pull pos- itive samples into the cone (distance 72 > O). Intuitively, positive samples shrink the embedding while negative ones dilate. In Figure 7 embedding for umbral-half halrrll-al--ppcee.
show how the distance-energies are used optimize a toy
Compared the max- max- margin energy used in previous works (Vendrov et 2015 Ganea 2018). namely L = ((,,)) E'u, v) (w' max(0, 7 E(u', v' v')), our distance-based shadow loss offers several advantages: (1) The learning dynamics are refined by considering the distance or depth of both wrongly and correctly classified points relative the cone. (2) We adopt the contrastive-
style loss proposed by (Nickel & Kiela 2017), which we demonstrate to be effective in Section 5
Our listance-based measure offers a more nuanced understanding of hierarchical relationships compared to the angle-based energy used in (Ganea et al. 2018):E(u, v) = max(0, Φ(v, u.) f.). where 0g, is the half aperture and Φ(v, u) is the angle between the geodesic wv and cone's central axis u. This angle-based energy lacks the ability to capture the depth confidence of the hierarchy. For example, all points v on the the cone's 's axis associated with u have Φ(v, u) = O. yet some may require further optimization to better reflect hierarchical depth. Additionally, the angle-base energy, when used with max- max-margin energy loss in (Ganea et al. 2018). leads to vanishing gradients for misclassified negative samples in the shadow cone (Ganea
2018 Our approach effectively avoids this issue.
7

---

Published as a conference paper at ICLR 2024
Table 2: Fl score (%) on mammal sub-graph with best numbers bolded
Dimension
Dimension = 5
Non-basic-edge
Percentage
0%
10%
25%
50%
90%
0%
10%
25%
50%
90%
GBC-box
23.4
25.0
23.7
43.1
48.2
35,8
60.1
66.8
83.8
97.6
VBC-box
20.1
26.1
31.0
33.3
34.7
30.9
43.1
58.6
74.9
69.3
Entailment Cone
54.4
61.0
71.0
66.5
73.1
56.3
81.0
84.1
83.6
82.9
Umbral-half-space
57.7
73.7
77.4
80.3
79.0
69.4
81.1
83.7
88.5
91.8
Peteral-Poincré--ae
44.6
58.9
60.5
65.3
63.6
62.4
67.4
81.4
81.9
92.2
Penumbral-hai sealf-ssacce
52.8
74.1
70.9
72.3
76.0
67.8
82.0
83.5
87.6
89.9
44.6
60.8
62.7
68.4
67.9
60.8
69.5
78.2
84.4
92.6
Table 3: Fl score (%) on WordNet noun, MCG, and Hearst with best numbers bolded
Dataset
Noun
MCG
Hearst
Non-basic-edge Percentage
0%
10%
25%
50%
0%
10%
25%
50%
0%
1%
2%
5%
Entailment
d=5
29.2
78.1
84.6
92.1
25.3
56.1
52.1
60.2
22.6
45.2
54.6
55.7
Cone
d=10
32.1
82,9
91.0
95.2
25.5
58.9
55.5
63.8
23.7
46.6
54,9
58.2
Umbral-
d=5
45,2
87.8
94.2
96.4
36.8
80.9
85.0
89.1
32.8
63.4
77.1
80.7
half-space
d=10
52,2
89,4
95.7
97.0
40.1
81.9
87.5
91.3
32.6
65.1
81.2
86.9
Penumbral-
d=5
44.6
82.6
86.2
88.3
35.0
78.6
81.1
85.3
26.8
62.8
72.3
78.8
half-space
d=10
51.7
84.1
88.3
89.8
37.6
81.9
85.3
89.2
28.4
54.4
68.1
79.3
EXPERIMENTS
This section showcases shadow cones' ability represent and infer hierarchical relations on four datasets (detailed statistics in Appendix Gp: MCG (Wang et al. 2015 5, Wu et al. 2012 Li et al. (017).
Hearst patterns (Hearst. 1992 Le al. 2019), WordNet Noun (Christiane 1998). and its Mammal
sub-graph, We consider only the Is-A type relations in these datasets.
Transitive reduction and transitive closure. MCG and Hearst are pruned until they are acyclic, as detailed in Appendix G We then compute their transitive reduction and closure (Aho et al. 1972). Transitive reduction reduces the graph to minimal set relations from which all other relations could be inferred. Consistent with (Ganea et al.) 2018), we refer to this minimal set as the "basic" edges. On the other hand, transitive closure encompasses all pairs of points connected via transitivity. Transitive reduction and closure respectively offer the most succinct and exhaustive representations of DAGs.
Training and testing. Non-basic edges can be inferred from the basic ones by transitivity, but the reverse is not true. Therefore, it is critical include all basic edges in the training sets. Consistent with (Ganea et al. 2018), we create training sets with varying levels of difficulty by progressively adding 1% to 90% of the non-basic edges. The remaining 10% of non- non-basic edges are evenly divided between the validation and test sets. Our main testing regime is to first train an embedding using collection of basic and non-basic edges, and then use it to predict unseen non- conbbasic edges. In we discuss other downstream tasks such as distance- based classification.
Appendix H
Initialization. The initial embeddings have been observed be important for training (Ganea et al. 2018). Following the convention established by (Nickel & Kiela 2017). we initialize our embeddings as uniform distribution around origin in [- in each dimension. Note the origin of the Poincaré salfespace model is (0, 0, 1/Vk).. In the Poincaré ball model, since embedded points and light sources can not overlap, we project the initialized embeddings away until they are at least of distance r (radius of hyperbolic ball) from the origin. We note that (Ganea et al., 2018) adopted a pretrained 100-epoch embedding from (Nickel & Kiela, 2017) initialization.
We benchmark against the entailment cones proposed in (Ganea et al., 2018) by following their original implementation with max-margin angle-based energy loss, which to our knowledge is state- of-the-art model using cone embeddings in hyperbolic space. For completion, we also compare with the latest box embeddings in Euclidean space: GBC-box and VBC-box (Zhang al. 2022 Boratko cet al. 202T). Table 2] summarizes all four shadow cone's performance on Mammal, which nearly outperform all previous methods, Fuclidean and Hyperbolie, in terms of generalization.
8

---

Published as a conference paper at ICLR 2024
placental
carnivore
canine
rodent
aquatic mainml
feline
primate
springer sparpe
monolreme
seal
whole
german shepherd
brown bat
old world beaver
mole
spider_ monkey
footed woodraa
Figure 8: Mammal Sub-graph Embeddings the 2D Umbral-Half Sapcpe Formulation. Black points represent the embedded nodes, while blue lines the basic edges between them.
Discussion on the impact of e-hole. We note that the Poincaré half-space formulations of shadow cones consistently outperform their Poincaré-bor ball counterparts. We attribute this difference to the initial embeddings prior to optimization. the Poincaré-ball model, due to the hole around the light source at the origin, the initial embeddings are randomly projected away onto the boundary of the hole, which can destroy the hicrarchical relationship between two objects by potentially pushing them to opposite directions. However, in contrast, shadow cones in the Poincaré half-space model do not suffer from this issue as the light source placed far away from the hyperbolic origin.
On large datasets (WordNet Noun, MCG, and Hearst), compare shadow cones in the Poincaré half-space against the baseline, as shown in Table 3] In all experiments, umbral- saal--haf--ppce cones consistently outperform the baselines and penumbral-half-spee centages. This is likely because conumbra-hhalf-peee does not. Finally, Figure 8 The points represent taxonomic names, with blue edges indicating basic relations. It's note- worthy that the learnt embedding naturally organizes points into clusters, roughly corresponding to families. The depth of points within these clusters may be interpreted as taxonomic ranks, such as the Canidae family to the German Shepherd species. Our code is available on github
cones for all non-basic-edge per- has a height limit while umbral-half-spac visualize one of our trained embeddings:
on Mammals, in
6 CONCLUSION AND FUTURE WORK
Hicrarchical structures pervade relational data. Effectively capturing such structures essential for various applications as it may reveal hidden patterns and dependencies within intricate datasets. We introduce the shadow cone framework, a physically inspired approach for defining partial orders hyperbolic space and general Riemannian manifolds. Empirical results show its superior representa- tion and generalization capabilities, outperforming leading entailment cones. Moreover, different shadow cones may be suitable for different data structures. For example, Penumbral -hatrrallal--ppcceee cones can have various apertures within the same embedding, and may be better suited to embed graphs with varying branching factors than umbral cones, which have fixed aperture.
The shadow cones framework also allows one capture multiple relation types within one embedding by using multiple light sources, with the shadows cast by each light source capturing one type of relation (Appendix D). This approach may enable more comprehensive representation of complex relational datasets.
Although our primary focus in this work is on learning embeddings directly from partial-order datasets, the shadow cone framework is versatile enough to implicitly learn latent hierarchical structures in data. For instance, a study by Tseng et al. (2023) enhances the performance of various transformer models by incorporating Shadow-cone-basee hyperbolic attention mechanism.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was funded by Professor Christopher De Sa's NSF award IIS-2008 102, NSF CAREER award 2046760 and a gift from Google.
REFERENCES
Alfred V. Aho, Michael R Garey, and Jeffrey D. Ullman. The transitive reduction of directed graph.
SIAM Journal on Computing, 1(2):131-17,, 1972.
James W Anderson. Hyperbolic geometry. Springer Science Business Media, 2006.
Yushi Bai, Zhitao Ying. Hongyu Ren, and Jure Leskovec. Modeling heterogeneous hierarchies with relation-specific hyperbolic cones. Advances in Neural Information Processing Systems, 34:12311 14:11 12327. 2021.
Ivana Balazevic, Carl Allen, and Timothy Hospedales. Advances in Neural Information Processing Systems, 32, 2019.
poincaré graph embeddings.
Michael Boratko, Dongxu Zhang, Nicholas Monath, Luke Vilnis, Kenneth L. Clarkson, and Andrew McCallum. Capacity and bias learned geometric embeddings for directed graphs. Advances in Neural Information Processing Systems, 14:13-44116436 2021.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond cuclidean data. CoRR, 0bs//6111.0099/ 2016. URL http://
Ines Chami, Adva Wolf, Da- Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low- dimensional hyperbolic knowledge graph embeddings. arXiv preprint 2Xiv:2005.00545 2020.
Fellbaum Christiane. Wordnet: an electronic lexical database. Computational Linguistics, pp. 292- 296, 1998.
Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hierarchical embeddings. In International Conference on Machine Learning, pp. 1646-1655. PMLR, 2018.
Marti A Hearst. Automatic acquisition of hyponyms from large text corpora. In COLING 1992 Volume 2: The 14th International Conference on Computational Linguistics, 1992.
Shyuichi Izumiya. Horospherical geometry in the hyperbolic space. In Noncommutativity and Singularities: Proceedings of French-Japanese symposia held at IHÉS in 2006, volume 55, pp. 31-50. Mathematical Society of Japan, 2009.
Matt Le. Stephen Roller, Lactitia Papaxanthos, Douwe Kiela, and Maximilian Nickel. Inferring concept hierarchies from text corpora via hyperbolic embeddings. arXiv preprint 4rXiv:1902.00913, 2019.
Liulei Li, Tianfei Zhou, Wenguan Wang, Jianwu Li, and Yi Yang. Deep hierarchical semantic segmentation. In Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition, pp. 1246-1257, 2022.
Xiang Li, Luke Vilnis, and Andrew McCallum. Improved representation learning for predicting commonsense ontologies. arXiv preprini arXiv: 2017.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representa- tions of words and phrases and their compositionality, 2013.
Maximillian Nickel and Douwe Kicla. Poincaré embeddings for learning hierarchical representations. Advances in neural information processing systems, 30, 2017.
Maximillian Nickel and Douwe Kicla. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In International conference on machine learning, pp. 3779-3788, PMLR, 2018.
10

---

Published as a conference paper at ICLR 2024
Jeffrey Pennington, Richard Socher, and Christopher Manning. GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 1532-1543, Doha, Qatar, October 2014. Association for Computational httpp/////.aaaecoooooo....ooo
Linguistics. doi: 10.31 10.3115/11/114-11 162.
Frederic Sala, Chris De Sa, Albert Gu, and Christopher Ré. Representation tradeoff's for hyperbolic embeddings. International conference on machine learning, pp. 4460 6460.4469. PMLR, 2018.
Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Pupers 19, pp. 355-366. Springer, 2012.
Alexandru Tifrea, Gary Bécigneul, and Octavian-Eugen Ganea. Poincar ('e glove: Hyperbolic word embeddings. arXiv preprint 181000664 2018.
Albert Tseng, Tao Yu, Toni J.B. Liu, and Christopher De Sa. Concheads: Hierarchy aware attention. arXiv preprint, 2023.
Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. Order-embeddings of images and language. arXiv preprint arXiv: 151 1.06361, 2015.
Zhongyuan Wang, Haixun Wang, Ji-Rong Wen, and Yanghua Xiao. An inference approach to basic level of categorization. In Proceedings of the 24th international conference on information and knowledge management, pp. 653-662, 2015.
Wentao Wu, Hongsong Li, Haixun Wang, and Kenny Q Zhu. Probase: A probabilistic taxonomy for text understanding. In Proceedings of the 2012 ACM SIGMOD international conference on management of data, pp. 481 1921,492222 2012.
Tao Yu and Christopher De Sa. Random laplacian features for learning with hyperbolic space. In International Conference on Learning Representations, 2023.
Tao Yu and Christopher M De Sa. Numerically accurate hyperbolic embeddings using tiling-based
models. Advances in Neural Information Processing Systems, 32, 2019.
Tao Yu and Christopher M De Sa. Representing hyperbolic space accurately using multi-component
floats. Advances in Neural Information Processing Systems, 34:15570-15581, 2021.
Tao Yu, Wentao Guo, Jianan Canal Li, Tiancheng Yuan, and Christopher De Sa. Htorch: Pytorch- based robust optimization hyperbolic space. GitHub Repository, 2023. URL https:/7
Dongxu Zhang, Michael Boratko, Cameron Musco, and Andrew McCallum. Modeling transitivity and cyclicity in directed graphs via binary code box embeddings. Advances in Neural Information Processing Systems, 35: 1058779999,9, 2022.

---

Published as a conference paper at ICLR 2024
A ADDITIONAL KEY CONCEPTS IN HYPERBOLIC GEOMETRY
The boundary of H. is the set of points infinitely far away from the Irigin.In the Poincaré ball, the boundary 8g is a sphere of radius 1/v at the "edge" of the ball. In the Poincaré half-space, the boundary S the O-hyperplane (rn, 0) and the point at infinity (r, = 00)
Hypercycles are curves equidistant from a geodesic axis 1. In the Poincaré ball, hypercycles of / are Euclidean circular ares that intersect the boundary at l's ideal points at non-right angles. In the Poincaré half space, if is a Euclidean semicircle, then the hypercycles of / are again Euclidean circular ares intersecting the boundary at I's ideal points at non-right angles. If / is a vertical ray, then hypereycles Euclidean rays that intersect I's ideal point at non-right angle.
The tangent space x on a manifold M = H. denoted M, is the first order vector space approximation of M tangent to MM æ. M is also the set of tangent vectors of all smooth paths E . through æ. Note that the Riemannian metrics defined above are metrics of the tangent space.
The notion of locally flat tangent space allows to define local distance metrics, JM (x), everywhere on a Riemannian manifold. (M(()) is termed Riemannian metric, and it is a positive-definite quadratie form that assigns an "infinitesimal distance" each tangent vector a point on the manifold.
The exponential map, expx maps a vector v E Ta HI to another point in Hi by traveling along the geodesic from in the direction of e. The logarithm map log (y) is its inverse.
Hyperbolic law of sines, like its Euclidean counterpart, relates the angles of any hyperbolic triangle to its geodesic side lengths:
sin A sin B sin C
sinha a sinh sinh
where A, B, and C' are the angles of a hyperbolic triangle, and a, b, and are the geodesic edges of the sides opposite these angles.
B SHADOW CONES' BOUNDARY CHARACTERIZATION
In this part, we explain intuitively the boundary computation of shadow cones and the reason why Umbral cones are not geodesically convex.
Penumbral shadow, which results from partial eclipse of a light source with volume, is produced by point object. Therefore, the boundaries of penumbral shadow are geodesics passing through u while being tangent to the light source. Note that the Penumbral Shadow(o) C Penumbral Shadow(u) for any v E Penumbral Shadow(1) (u). therefore, all possible children of i.e., penumbral cone of coincides with the penumbral shadow of u, with geodesics boundary described above.
S
u $ x
On the other hand, Umbral shadow, which results from total eclipse of a point light source, is produced by an object with volume 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 e' of u, i.e., umbral cone of u. Since the objects u and have volumes. then for u v to be true, must be that and its ball are entirely immersed in u's shadow. Otherwise, the portion of v's ball outside of w's shadow can cast shadows outside. In Fig 9 we sketch case where v's center is in u's shadow, but nevertheless u 1 v. because part of o's ball outside.
Figure 9: An example illustrating the necessity for v's ball to be entirely im- mersed in u's umbral shadow, order that 3 v. the marginal case shown here, u A even though the point v is in u's umbral shadow, This is because part of v's ball and corresponding bral shadow is outside of u's umbral shadow.
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 straight line forms another, parallel straight line. In contrast, in hyperbolic space, the set points equidistant from a geodesic do not necessarily form a geodesic, and is instead referred to hypercycle. In Fig T0 illustrate the non-convexity of umbral cones in Poincaré
12

---

Published as a conference paper at ICLR 2024
half-space. In green 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 strict subset of its convex hull, which means the umbral cone is not geodesically convex.
C PROOF OF TRANSITIVITY & GEODESIC CONVEXITY
In this section, we provide proofs to the transitivity of the partial orders induced by umbral and penumbral cones, together with the proof of penumbral cones' convexity. We first give several equivalent definitions to umbral and penumbral cones
S
en
1. u I v iff (and its ball) is in the shadow of u (and its ball).
2. if the shadow of (and its ball) is subset of the shadow of u (and its ball).
u
3. u 3 v if every geodesic between the light source and (and its ball) passes through u (or its ball).
Wherein, the parentheses refer to the umbral cone case, We will adopt the 3rd definition within this section.
Proof of transitivity. We start with the umbral cone case, sup- pose that æ 3 y and y 3 z, then every geodesic between S and y's ball passes through x's ball, and every geodesic be- tween S and 2's ball passes through y 's ball. Now consider any geodesic between S and z's ball, which must passes through the y's 's ball, but then it is also a geodesic between and y ball, which must pass through æ's ball, that is x: <
Figure 10: Umbral shadow cone (green) of in half-space model with light source S at infinity, where en is the propagation direction of lights. I (dot- ted red) denotes the boundary of um- bral shadow casted by u and its ball. Solid green lines denote the boundary of the umbral cone of u, while solid black lines delineate the geodesically convex hull of u's umbral cone. This figure shows that umbral cones are not geodesically convex, because they strict subsets of their geodesically con- vex hulls.
For penumbral cones, suppose that x 3 y and y z z. Consider the geodesic submanifold (isometric the hyperbolic plane) passing through æ, y and z. Since æ N y, then the geodesic from y through intersects the light source. Similarly, the geodesic from through intersects the light source. Denote these intersection points on the boundary of S as and b respectively, then consider the geodesic ray from passing through a, as passes through z, it either enters or exits the triangle Aaby. Since æ is on the line segment ya now, it can't be exiting the triangle, because is on the line segment zb, so was already outside the triangle. Therefore, it must be entering the triangle and it must exit the triangle at some point along one of the other sides.
Note that it can't I exit along the side yb, because is already on that line, and can't intersect the line twice, so it must exit along the side ab, but that side is entirely within the light source, because and b are on the light source and the light source is convex. therefore x 1
Worthy to mention, in the proof of penumbral cones, used the fact that S is convex, so is the intersection of S with any geodesic submanifold of dimension 2. In fact, we only need the intersection with any geodesic submanifold of dimension 2 to be connected, but convexity of S suffices.
Proof of geodesic convexity for penumbral cones. This can be proved following a similar pattern as last proof. Suppose that x Z y and x > z. Let ur be any point on the geodesic line segment yz, again we consider the geodesic submanifold passing through æ, y and z, which also passes through w. The geodesic from y through æ intersects the light source, so is the geodesic from z through æ. Denote these intersection points as a, b respectively. Now consider the geodesic from w through x, which is contained between geodesics xy and æz, so it will also contained at the other side of them, i.e., and æb. Also is one vertex of the triangle Labx, so the geodesic wa enters the triangle 2 abb then must exit the triangle at some point along one of its sides. Since wa intersects za and ab n. it can't exit along za and ab sides, because it can't intersect line
13

---

Published as a conference paper at ICLR 2024
twice. Therefore, it must exit along the side ab, which is entirely within the light source, because the
light source is convex. Therefore, we intersects with the light source at some point, i.c, w 2 æ.
D ISOMETRY MAPPING LIGHT SOURCE TO ORIGIN
For the Poincaré ball model, when the light source of shadow cones is in the space but not at the origin, we utilize the following isometry to map the light source to the origin.
Definition (Isometry Yu & De Sa. 2023 ) Let Inv(x) |||=||? then the map
2
Ts(x) S + (1 ||S|]²) Inv Inv((nv(x)) -S) an isometry of the Poncaré ball, which maps the origin O. i.c.
S. Since isometries preserve distance, geodesics and also equal distance curves (i.e., hypercycles), then both the umbral and penumbral cones are preserved under isometries. Therefore, when the light source S is not at the origin, we apply the isometry T's all embeddings, then the energy function can be computed accordingly as the light source at the origin case.
E EQUIVALENCE OF PENUMBRAL-POINCARÉ-- AND GANEA ET AL. (2018)'s S ENTAILMENT CONE CONSTRUCTION
Proof.
Ganea et al. 2018) defines the entailment cones in the Poincaré ball model (of curvature -1) as
| )
(u E B (6(,(, S arcsin K
|
where d(y, z) is the angle between the half-line (zy and (ox. On the other hand, Penumbral- cotiubbrrl--oicccr--be ball is defined as
{y B"Io(y, x) s 0. arcsin( sinh vlr sinh v Vkdalæ, O) }}
where -k is the curvature of the hyperbolic space. With
dn(x, O) arcosh 1 2k |0|1
|1
we get
sinh Vkr
sinh v Fer
k||==|3
0, arcsin
aresin
sinh arcosh
26 | 1- .
2
|||a||
Note Ganea (018)'s entailment cones were studied in le 1 case, then the penumbral-Poine Poinccréé ball cone when k 1 is
sinh
||0|| )}
ty B" [" s 02 = arcsin(
2
|
set K= sinh (since r is user-defined hyperparameter), the entailment reduces to penumbral- Poincaré-bal ball cone, a special case of shadow cones.
F MORE DETAILS ON SHORTEST HYPERBOLIC DISTANCE TO SHADOW CONES
F.1 UMBRAL-HALF-SPACC CONES
In the main paper, we provide the shortest hyperbolic distance to the umbral-half-space cone, here give detailed derivation of the formulas. We start by giving the logarithm map in the Poincaré
14

---

Published as a conference paper at ICLR 2024
half-space model Yuu & De Sa 2021 let log (y), then
Yn sinh (y/ I;)
In
0/ sinh
(cosh
Vn
where s vkda((,,) y).
Note that the hyperbolic ball of radius centered at u in Poincaré half-space corresponds to an Euclidean ball with center Cu (u1..... Mn-11 "x, cosh vkr) and radius r. u sinh v /rr where -k is the curvature of H.. Note that boundaries of the umbral cone induced by u are hypercycles with axis is, where belongs to the set of light paths that are tangent to the boundary of u 'ss ball: {(x),... .......n-......
In.1..) f)] Σ (z; u; = ra > 0}. In order to derive the signed hyperbolic distance from to the boundary of the umbral cone, it suffices to compute the signed distance of to such I since hypercycles are equal-distance curves.
Now we derive the shortest signed hyperbolic distance from to such an Let ur be a point on such that da(v I) dx (v, w), then clearly the geodesic from w through v is orthogonal to ( at w, i... (Ioguo (v)), that the geodesic from ur through v is a half-cincle-style geodesic with center on the O-hyperplane.
cosh Wn/U, Un, = da(v, I) da(v, w) arcosh (wn/vn)/vr /k. Note
Since it's orthogonal 7 (a vertial line), hence the center of the geodesic is in fact (W1,--- 1n 0), then we have
(w 02 +
by computing the radius to v and respectively. Meanwhile, we have the following ratio between coordinates:
W/ 02 04
Te
i== (4: 02)2
From both equations can derive that
w = n + (1
Fe
(v: uz)
>i=1 (v: -1;)²
n
Uys +
2
(v: u,)2 rr
Hence, the signed shortest distance from to the boundary Cone(u) is
1 Vk
r + V arcosh (wn/vm) = + arcosh (
1+(1
1
(
Σ (o
wz)2 - rr))2//0
Note that arcosh VI+ = arsinh(t), Vt 2 O, where the latter is desired signed distance, then let
t Σ (u: u,)= u, sinh Vkr
/Un
be a temperature function, derive the signed shortest distance from to the boundary Cone(u) is
arsinh(t).
In order to derive the relative altitude function of o respect to u, consider when the shortest geodesic from the boundary of Cone(u) (u) is attained u, which will be orthogonal to the boundary at u, using the property of half-circle-stlye geodesic, we have that
2 +
Σ (4: v, r2)2 =12 u n (1 sinh² Vir) u cosh? Vlr,
15

---

Published as a conference paper at ICLR 2024
that is, of + 2 u cosh Vkr. hence, natural choice of the relative altitude function is H u) o (1 (2) un cosh vkr. Then the shortest signed distance from Cone (x) is du(u, v) when (v, u) and arsinh(t)/ /V when H u) S O.
F.2 UMBRAL-POINCARE-BALLL CONES
Similarly for umbral- Poincaré-ball cone, have Lemma F.1 Simbral-Poincaree
Denote the angle between u, and B as the maximum angle spanned by the hyperbolic ball of radius r associated with u, then
TT
arcsin 2vkr ||
arccos
B = arcsin
||ll
sinh (Vkdn(us (u, 0))
Set the temperature as
2 |
t= sinh (Vkda(v, 01) sin(a 3) 1 [||
sin(a -8),
then the relative altitude function of with respect a is
(vv, u)
1
arcosh
cosh (Vkda((e v, O))
arcosh (cosh (v VVddgu, O)) cosh (Vkr))
Vk
+ 1
1
+ h: |00|
1 + 1: || arcosh cosh (Vkr) 1 - k ||
(costh
arcosh
Vk
1 +
1 - k ||01
V
In fact, boundaries of the umbral cone induced by u are hypercycles with axis Is, where / belongs to the set of light paths that are tangent to the boundary of u's ball. We compute the signed distance of to such a I in the Poincaré ball model, which is easier since the line Ou and are geodesics, where hyperbolic laws of sines can be applied.
Denote the angle between u, and B3 the maximum angle spanned by the hyperbolic ball of radius r associated with u, then
u
2 | 1
a = arccos
[ull
||a||*
B = arcsin
sinh (Vldg (u, 0))
aresin
| 2
where the equation of is a result of hyperbolic laws of sines. Again using the hyperbolic laws of sines, we derive the signed distance from v to as
da
arsinh (sinh (Vidg(e, sin(a B))
V
therefore, set the temperature
2 ||l||
i = sinh (Vhdn(0, 0)) sin(a - 3) 1- ||aa
sin(a - B),
then the signed shortest distance the boundary of Cone(u) is
arsinh(() +
In order to derive the relative altitude function, we consider the altitude of v, which is simply the projection of to I, using hyperbolic laws of cosines, we have
cosh (Vkdg(v, O)) = cosh [Vkdg(w,1) 1)) cosh (VkH(v)),
Similarly for the altitude of u. cosh (Vidua O)) cosh (v (Vied 1)) cosh (V)H((u)) cosh (VTr) cosh (Vi:H(u)).
16

---

Published as a conference paper at ICLR 2024
Table 4: Dataset Statistics
Mammal
Noun
MCG
Hearst
Depth
8
18
# of Nodes
1,179
12,114
22,665
35,545
of Components
4
2
657
2,133
# of Basic Relations
1,176
84,363
38,288
42,423
of All Relations
5,361
661,127
1,134,348
6,846,245
combining them togeterm, the relative altitude function H(v, u) H(v) H())
H(U, u)
1
arcosh
cosh (Vkdu O))
arcosh (cosh (v (Vkddau (u, O)) cosh ( (v vkr))
Vk
+I+t t
Vk
+ k: |01 vI +
(cosh cosh (Vkr) 1 + k: [126| ||
arcosh
arcosh
Vi
k ||
1 k ||
Then the shortest signed distance from v Cone(u) is da(u,,) when H Huv u) 0 and arsinh(t)/v when H(v, u) S O.
F.3 PENUMBRAL CONES
For penumbral cones, things are simpler since the boundary of penumbral cones are geodesics, where we can freely apply the hyperbolic laws of sines to hyperbolic triangles.
Theorem F.2 (Shortest Distance to Penumbral Cones). For penumbral cones, the temperature is defined as 60v, u) Ow where Φlv, u) is the angle between the cone central axis and the geodesic connecting u, v at u, On is half-aperture of the cone. The relative altitude function is ( u) - n/2, and the shortest distance from to the penumbral cone induced by
d(v, Cone(w)) = { (de(u,)) v)
H( u) > 0, if H u) $ O,
Vi arsinh (sinh (Vkdg (u, u)) sin
where the second formula represents the soaddddittacntt--baeee
We derive the relative altitude function first, note that H(v, u) when the geodesic from v through is orthogonal to one boundary of the cone at with simple geometry, the relative altitude function d by simply applying the
H Hw,, u) - क 2/2. We derive the hyperbolic laws of sines:
sinh Vkdu(u, v) sinh (kdu(v,1) sin (T/2)
sin f
vR. arsinh (sinh (v (vkda(u,, u)) sin In summary, the shortest distance from the penumbral cone induced by u is
then we get that (v, I) =
du (u, v)
if H(v u) > 0, if H( u) S 0,
d(n Co)e(u))
vk arsinh (sinh (Vkda(u, v)) sint)
where the second formula represents the signed-distance-to--buddaa
G TRAINING DETAILS
Data pre-processing and statistics. WordNet data are directly taken from (Ganea et al. 2018). which already DAG. MCG and Hearst are taken from (Wang et al. 2015 Wu et al. 20 2 and (Hearst 1992) respectively. Since these datasets are orders magnitudes larger than WordNet, we take the 50, 000 relations with the highest confidence score. We note that there numerous cycles
17

---

Published as a conference paper at ICLR 2024
even in the truncated MCG and Hearst graphs. To obtain DAGs from these graphs, we randomly remove 1 relation from a detected cycle until no more cycles are found. The resulting four DAGs have vastly different hierarchy structures. To roughly characterize these structures, we use longest path length as proxy for the depth of DAG and number of components (disconnected sub-graphs) as the width.
While the WordNet Noun and MCG datasets are trained with a maximum of 50% non-basic edges, we limit Hearst training to 5%. This due to Hearst's 's transitive closure being more than x0x larger than that of WordNet Noun, despite having comparable numbers of basic relations. We note that a data set's complexity is better reflected by the size of its basic edges than that of the transitive closure, as the latter scales quadratically with depth. For instance, although Hearst possesses only half as many basic relations as Noun, its transitive closure is tenfold larger. This can be attributed to its depth 56 compared to Noun's 's 18 and MCG's 31, Full data statistics can be found in Table 4
Negative sampling. Negative samples for testing: For each positive pair in the transitive closure (u, v)) we create 10 negative pairs by randomly selecting 5 nodes v'. and 5 nodes u' such that the corrupted pairs e²) and (u', 2) are not present in the transitive closure. As result, this 'true negative set' is ten times the size of the transitive closure. We choose negative set size equals 10 as result of following (Ganea et al. 2018).
Negative samples for training are generated in similar fashion: For each positive pair (u, v), randomly corrupt its edges to form 10 negative pairs (u, v') and (u', v). while ensuring that these negative pairs do not appear in the training set. We remark that since the training set is not the full transitive closure, these dynamically generated negative pairs are impure as they might include non- basic edges.
Burnin. Following Nickel & Kiela, 2017 2018), we adopt a burnin stage for 20 epochs at the beginning of training for better initialization, where smaller learning rate (burnin-multiplier 0.01 x) is used. After the burnin stage, the specified learning rate is then used (1 x).
Plyper-paramend and Optimization. On WordNet Noun and Mammal, we train shadow cones and entailment cones for 400 epochs, following (Ganea et al. 2018). On MCG and Hearst, we train shadow cones and entailment cones for 500 epochs since due to their increased hierarchy depth. A training batchsize of 16 is used for all datasets and models. We used the standard hyperbolic space of curvature -k, where k consistently for all experiments reported in the paper, though a general k value can also be used. For the margin parameters in shadow loss, we use 7/2 O consistently for all experiments. We tune ?1 and the learning rate in {0.01, 0.001, 0.0001). For umbral cones, we tune the source radius r in (0.01, 0.05, 0.1, 0.2, D. empirically = 0.05 during training gives the optimal performance when evaluated under slightly larger radius r 0.1. For penumbral-halt space cones, we tune the exponentiated height vize Vkh in {2,5, 5, 10, 20). where empirically 20 during training gives the optimal performance, which validates our assumption that the height of penumbral- half-space cones can limit its performance. Note that for shadow cones, when H(v u) > O, the shortest distance the cone is da v), which will only pull v to be close to u. apex of the shadow cone, but not pull into the shadow cone. To solve this issue, we use (1,',, 1) when Hvv u) > O. where u. is derived by pushing u into its shadow cone along the central axis for a distance "/- We set "33 = 0.0001 consistently for all shadow cones. We use HTorch (Yu et al. (2023) for optimization in various models of hyperbolic space. We use RiemannianSGD for Poincare half-space model, and RiemannianAdan for Poincaré ball model due to the ill-conditioned initialization results from the hole around the origin, where Riemannian offers a much faster convergence than RiemannianSGD.
Ease of Training. Our training routine is less complicated than that of the Entailment Cone (Ganea et al. 2018): 1) While the entailment cone uses pretrained 100-epoch embedding as initialization in order to avoid the e-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 h-hole issue at the origin, and need extra steps to project the "stray" points out of the hole.
18

---

Published as a conference paper at ICLR 2024
H ADDITIONAL EXPERIMENTS
H.1 DOWNSTREAM TASKS
One promising application is proposed in Tseng al. (023). attention mechanism, which can be used as drop-in replacement for dot- dot-product attention in transformers. Cone attention associates two points by the depth of their lowest common ancestor in hierarchy defined by hyperbolic shadow cones. [seng et al. (2023) 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.
shadow-cone based hyperbolic
We would also like to supplement with 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 a species. For example, the order of American beaver rodents, and the order of Bonobo is primates. To construct the classification task, 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 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) = arcosh(1 + ||X y13
Vk
22,
where we Ia and yn are both fixed to be 1. Therefore, this distance could also be thought of as the hyperbolic distance confined the F, 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 simple distance-based classification achieved an accuracy 94.80% with a 5D Umbral half-space cone and 73.23% with a 2D) Umbral half-space cone.
H.2 INTERPRETATION OF LIGHT SOURCE RADIUS
We modified our existing framework to learn light source radius from data. Fig 11 and 12 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 speculate that this might be a result of the connectivity of the underlying data: the mammal graph is highly interconnected, featuring only four disconnected components, large light source can cast large penumbral shadows, making it easier to model highly connected DAGs. 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.
19

---

Published as a conference paper at ICLR 2024
0.04
0.0075
ppem. peem_ whole
0.02
0.0050
prtmner
0.0025
placetta
0.00
0.0000
rodent
disklyfoohed
woodrot
-0.0025
canine
shephard
-0.02
0.0050
sprnger Sponic
-0.0075
-0,0100
0.035 0.036 0.037 0.038 0.039 0.040 0.041 0.042
-0.04
-0.02
0.00
0.02
0.04
Figure 12: zoomed-in view of leamned Mammal sub- graph embeddings with trainable light source radius, using Penumbral Piatraa--Ponccre-bba
Figure 11: A global view of learned Mammal subgraph embeddings with trainable light source radius, using Hauumbra--Poncare-bba
I ANTUMBRAL CONES
For completion, we discuss the third and final category of celestial shadows the antumbral shadows. Antumbral shadows occur under two necessary conditions: 1. The radius r of the object must be smaller than the radius R of the light source. 2. At least portion of the object must be located outside the light source. In Figure 13] we illustrate antumbral cone in the half-space setting, where shadows are generally not axially symmetric.
s
Let / geodesics tangent to the surface of the light source OS and the object Ou, such that u is between OS and the intersection u' of light paths. The antumbral shadow of u is then defined as the penumbral shadow of u'. Note that by construction, for any object with well-defined antumbal cone, it is always possible to find surrogate point u', whose penumbral shadow is identical the antumbral shadow of
u
u
Therefore, to encode relation u < u using antumbral shadows, it is equiv- alent to require their surrogate points satisfy u' o' in the penumbral cone formulation. This establishes an equivalence between the entailment relations of antumbral and penumbral formulations.
V
FUTURE WORKS
Figure 13: Antumbral
Cone in Half-space Geodesic Convexity Penumbral Cones. In our experiment thus far, penumbral cones have not demonstrated performance par with umbral cones in the half-space model, potentially due to their height limit and variable aperture. However, we would like to highlight a theoretical advantage unique penumbral cones geodesic convexity. Suppose U1 and U2 both within the penumbral cone of u, then the entire geodesic segment 8 U2 also resides within the penumbral cone. Such convexity lends itself more meaningful geometric operations, such as interpolation. We thus conjecture that penumbral embeddings are better suited for word2vec or Glo GloVe-style semantic analysis (Tifrea et al. 2018). Semantic analysis Euclidean spaces necessitates the comparison of vectors in Euclidean space, which is straightforward. However, comparing geodesics in general Riemannian manifolds requires careful approaches using methods such as exponential maps and parallel transport, which we defer to future works.
Downstream Tasks: Beyond the F1 Score. While all experiments this study are evaluated in terms of classification scores, the potential of hierarchy-aware embedding extends beyond entailment
20

---

Published as a conference paper at ICLR 2024
relation classifications. As pointed out in (Tseng al. 2023), can substantially enhance the performance of various attention networks by substituting their kernels with shadow-cone- based kernels that explicitly take into account the hierarchical relationships among data. In this vein, keen on exploring other downstream applications that utilize hierarchy-awan embedding beyond classification tasks, such media generation (images, text, sound) within guided by hyperbolic space embeddings.
Multi-relation Embeddings. If the objective develop meaningful embedding for down- stream tasks, rather than solely focusing on en- tailment classification for single type of rela- tion, then it is reasonable to enrich the same em- bedding simultaneously with various types of re- lations, such as entailment and causality. This be done while relaxing the classification curacy for each relation types. Our framework readily facilitates this, light sources, each casting shadows of a distinct color that captures different type of relation. An example is depicted in Fig 14 which is set in Euclidean space for simplicity.
u2
S
can utilize multiple
S
Figure 14: Multi-relation Embedding in Euclidean Space. Marked in purple and red are the two different light sources, and the respective shadow boundaries they cast.
21


Reviews:
[{"review_id": "gfz8JSFVdx", "reviewer": "Reviewer_6mLv", "summary": "The authors introduce the \"shadow cones\" framework for constructing entailment cones in hyperbolic space. Unlike prior work that utilized nested cones in the Poincaré ball, shadow cones model partial orders based on subset relations between shadows created by a light source and opaque objects.  This framework extends beyond the Poincaré ball, allowing for more diverse formulations and hyperbolic space models. Shadow cones offer advantages over existing constructions, particularly in terms of optimization properties. Experimental results demonstrate the consistent and significant outperformance of shadow cones compared to existing entailment cone constructions across datasets of varying sizes and hierarchical structures.", "questions": "see weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The introduction of shadow cones presents an innovative approach to defining entailment relations in hyperbolic space. Drawing inspiration from physical phenomena adds an intuitive and captivating aspect to the concept.\n\n2.  The authors provide a comprehensive mathematical formulation for shadow cones, enhancing the rigor of their work and enabling further exploration and development by other researchers in the field.\n\n3.  The experimental results across four datasets demonstrate the superior performance of the proposal compared to the current state-of-the-art methods.", "weaknesses": "1. While the authors tested their framework on four datasets, it would be beneficial to see how the framework performs on a wider variety of datasets, including those from different domains or those with different characteristics (like KG, recommender system datasets and so on). This would provide a more comprehensive evaluation of the framework's performance and versatility.\n\n2.The work builds on the entailment cone but a few partial order methods have been proposed and a thorough comparison or discussion is needed.\n\n3. Captions for the figures are brief and ambiguous, hindering their readability. \n\n\n[1]Capacity and Bias of Learned Geometric Embeddings for Directed Graphs.\n[2]Modeling Transitivity and Cyclicity in Directed Graphs via Binary Code Box Embeddings", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Rf4SoKDCS7", "reviewer": "Reviewer_Arvf", "summary": "This paper proposes a physically intuitive partial order embedding framework \"shadow cones\" that generalizes the well-known \"hyperbolic entailment cones\". Also, this framework generalizes to two different hyperbolic models, the Poincaré disk and Poincaré half-space. The experiments shows that the generalized \"shadow cones\" outperform the \"hyperbolic entailment cones\" baseline.", "questions": "Please see the weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-motivated and has a good connection to existing research.\n2. It considers two hyperbolic models, the Poincaré disk and the Poincaré half-space.\n3. The theoretical analysis provides nice properties of the proposed models.", "weaknesses": "1. Compared with the novel and interesting motivation, the description, especially the figures, lacks explanation, almost all the symbols in the figures are not mentioned in the captions or corresponding text.\n2. The experiment is not very supportive of the claim. For example, In the experiment, Poincaré ball based cones performed worse than Poincaré half-space based cones. While in the important baseline \"hyperbolic entailment cones\", the Poincaré ball is used, if the proposed cone generalizes \"hyperbolic entailment cone\", it should be as good as the \"hyperbolic entailment cone\".\n3. The use of different definitions for light source in the Penumbral cone and the Umbral cone is somewhat inconsistent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LmwGWEngQp", "reviewer": "Reviewer_SzVy", "summary": "This paper proposes the use of (light) cones to learn embeddings of posets in hyperbolic space. Specifically, the paper looks at two models depending whether the data or the light source has mass. The paper proves a variety of consistency results such the fact that inclusion of the cones form a poset.", "questions": "I have a few questions. \n\n1) In the loss function $P$ and $N$ haven't been defined. \n\n2) For the cones I do not understand the boundary computation. Could the authors please expand on that? I did not see anything in the appendix either. \n\n3) Why do we need the ball around $y$ to be in the shadow for $y$ to be in the umbral cone, but only need the point $y$ to be in the shadows for the penumbral cone? I see that the umbral method seems to perform the best. I imagine based on how the loss in formulated this pushes the point to the interior of the cone rather than leaving it on the boundary where we might have numerical issues. \n\n4) Could the authors provide intuition for why umbral cones are not geodetically convex? I believe in this regard calling them cones might be a bit confusing, because cones in Euclidean space are not only convex, but contains these geodesic rays. I would have thought the same is true for the hyperbolic ones. Hence was surprised when I saw this result.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The idea of using cones is quite interesting to me. The paper shows that it results in a loss at least at the optimal point that does preserve the partial order structure. Further, it does so in a way that gives coordinates from which we can extract the partial order. Hence I think this is quite interesting and quite novel. I think of these are strong strengths. \n\nThe paper is mostly easy to follow however there are a few details I would like added. Please see weaknesses and questions", "weaknesses": "1) The first weakness for me is the context for the work. I think some more discussion to related concepts such as DAG learning, which is learning DAGs from data [1,2,3], other hyperbolic hierarchical learning like hyperbolic tree learning, which is about learning trees to represent hyperbolic data or embed in hyperbolic apace [4,5], graph embeddings in hyperbolic space [6,7,8], and hyperbolic link prediction [9] would be great. \n\n2) I think the experimental setup could be further expanded upon. First, I think it should be clarified that we can do the link prediction without the embedding step (this would have a 100% accuracy) and then mention that you do the embedding step to understand the how well the embedding performs. As part of the experiment, it would be good to have a baseline for Euclidean poset embedding. However, I admit I do not know of one. Maybe on of the DAG learning papers has a baseline that could be used. \n\n3) Building on the above it would be good to show that such embeddings can be used other non-trivial down stream tasks and that such embeddings provide an advantage. \n\n[1] X. Zheng, B. Aragam, P.K. Ravikumar, and E.P. Xing. Dags with no tears: Continuous optimization for structure learning. In Advances in Neural Information Processing Systems 31, 2018.\\\n[2] Yu, Y., Gao, T., Yin, N., & Ji, Q. (2021, July). DAGs with no curl: An efficient DAG structure learning approach. In International Conference on Machine Learning (pp. 12156-12166). PMLR.\\\n[3] Lachapelle, S., Brouillard, P., Deleu, T., & Lacoste-Julien, S. (2019). Gradient-based neural dag learning. arXiv preprint arXiv:1906.02226.\n\n[4] Ittai Abraham, Mahesh Balakrishnan, Fabian Kuhn, Dahlia Malkhi, Venugopalan Ramasub- ramanian, and Kunal Talwar. Reconstructing Approximate Tree Metrics. In Proceedings of the Twenty-sixth Annual ACM Symposium on Principles of Distributed Computing, PODC ’07, pages 43–52, New York, NY, USA, 2007. ACM.\\\n[5] Sonthalia, R., & Gilbert, A. (2020). Tree! i am no tree! i am a low dimensional hyperbolic embedding. Advances in Neural Information Processing Systems, 33, 845-856.\n\n[6] Chamberlain, B. P., Clough, J., & Deisenroth, M. P. (2017). Neural embeddings of graphs in hyperbolic space. arXiv preprint arXiv:1705.10359.\\\n[7] T. Blasius, T. Friedrich, A. Krohmer, and S. Laue. Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. IEEE/ACM Transactions on Networking, 26(2):920–933, April 2018.\\\n[8] Kevin Verbeek and Subhash Suri. Metric Embedding, Hyperbolic Space, and Social Networks. Computational Geometry, 59:1 – 12, 2016.\n\n[9] Zhe Pan and Peng Wang. 2021. Hyperbolic Hierarchy-Aware Knowledge Graph Embedding for Link Prediction. In Findings of the Association for Computational Linguistics: EMNLP 2021, pages 2941–2948, Punta Cana, Dominican Republic. Association for Computational Linguistics.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Xu99DNicLL", "reviewer": "Reviewer_s6e6", "summary": "Hyperbolic space have been shown to be particularly well suited to encode the latent structure of complex objects such as trees or graphs. In particular, using random graphs with an hyperbolic latent space are known to exhibit properties often found in real world networks such a the small world phenomenon or the scale free property. \n\nIn this paper, the authors introduce the so-called shadow cones framework: a methodology that allows to define a partial order embedding of hierarchical data. The authors show that such framework can be particularly efficient to learn a latent embeddings of nodes for trees or more generally for DAGs. Their method extends to the concept of entailment cones previously introduced by Ganea. On three different datasets, the authors show that using their method to learn the hierarchical structure of partially observed DAGs can allow to infer unseen edges better than previous approaches.", "questions": "I thank the authors for their nice submission.\n\nApart for my questions presented in the previous section (i.e. use of the method for applications and comparison with methods not using hyperbolic spaces), I would be interested to know if the method could be used in more general settings. In particular:\n\n- How the method could be used for real world graphs that are not (exactly) DAGs?\n\n- How the method could be used for multiclass hierarchical problems?\n\nHere are some typos and additional comments: \n\n- In the loss function (cf. Eq(1)), if think N and P are not properly defined in the text.\n\n- At the end of the first paragraph of the introduction of Section 3, I think there is an error. Should the last sentence rather be \"Specifically, $v$ is in the shadow cone of $u$ iff $v \\subset$ the shadow of $u$.\" ?\n\n- After Theorem 4.2, I think the first \"their\" should be removed from the sentence \"which is\ndesigned to draw child nodes v closer to their the cones of their patent nodes\".", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- Hyperbolic spaces have been shown to be very promising latent space to model graph data. This paper is focused on DAGs and proposes a new framework to learn embedding for hierarchical data. \n\n- The authors did an excellent job in ensuring the comprehensibility of their method, notably by incorporating highly insightful illustrations.\n\n- As a by product, the paper provides a comprehensive overview of various approaches to incorporate 'shadows' for embedding points in hyperbolic space, employing the concepts of umbral and penumbral cones. This lucid exposition elucidates the source of the limitations observed in prior methods, particularly with regard to the $\\epsilon$ hole problem.", "weaknesses": "- I think the authors should better stress the concrete applications of their method. For example, are there applications related to structure learning?  \n\n- In my opinion, the authors should include in their comparison methods that do not rely on hyperbolic spaces (but rather on Euclidean ones for example or with manifold with positive curvature).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UgiR411s0b", "reviewer": "Reviewer_JBVb", "summary": "This paper considers the problem of learning representations to model hierarchical relationships using hyperbolic space. The authors introduce several formulations of *shadow cones*, a novel and unifying framework of physics inspired representations. Entailment relations are defined by the containment of shadows of the object representations given a fixed light source and boundary if hyperbolic space. The authors present two different shadow formulations each in two different hyperbolic spaces. A smooth loss function is introduced to train shadow cones in a stable manner, avoiding some of the training issues presented in prior work. The effectiveness of the presented method is shown on standard open source datasets.", "questions": "* What advantages might this method have over a different representation learning paradigm such as box embeddings (e.g. [1])?\n* Why is there such a big discrepancy in the results between Penumbral-Poincaré-ball and Entailment cones in Table 2? These formulations are mathematically equivalent, but perform quite differently in some cases. Is this attributable to the loss function or training procedure in some way?\n* What is the relationship between convexity and performance? The non-convex method seems to perform better. Why is this the case?\n* What are the potential challenges to learning representations in the half-space formulation?\n\n[1] Dasgupta S, Boratko M, Zhang D, Vilnis L, Li X, McCallum A. Improving local identifiability in probabilistic box embeddings. Advances in Neural Information Processing Systems, 2020", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The proposed approach is novel and well-motivated, avoiding many of the issues in prior work\n* The proposed representation formulation encapsulates previous approaches\n* The paper is well written and includes many intuitive figures and diagrams to illustrate the proposed approach\n* The empirical results demonstrate the efficacy of the proposed methodology on standard datasets for this task", "weaknesses": "* The paper uses quite a bit of space introducing all four formulations of shadow cones, leaving less space for additional empirical results\n* At the end of Section 4, the authors make claims about ease of training, but do not justify claims beyond just a statement by fiat. \n* The proposed approaches are only compared against a single baseline -- even though this is the supposed state of the art in hyperbolic representations it would be beneficial to see comparisons with other methods.\n* The empirical results are all demonstrated on the same singular type of task. It would benefit the paper to see experiments on different types of tasks such as collaborative filtering.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rHZk7T7yoQ", "reviewer": "Reviewer_irmp", "summary": "The author proposed physically-intuitive embedding method for partial order hierarchy. The method uses shadow cones, which generalize existing hyperbolic entailment cones. The author also constructed the algorithm to optimize the shadow cones.", "questions": "1. Why the experimental results by Entailment Cone and Penumbral-Poincaré-ball are different while they are equivalent according to Theorem 3.2?\n1. 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?\n1. How do we select one of the 4 proposed methods depending on the situation?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The paper provides novel multiple variants of the existing hyperbolic entailment cone method. The techniques provided for handling shadow cones are significant technical contributions in the area.\n1. The physics-inspired explanation, with plenty of intuitive figures, of the proposed method helps readers understand the proposed method's concept and algorithm. The explanation also provides another explanation of why existing hyperbolic entailment cones cannot be defined for a point around the center of the Poincare ball.\n1. Table 1 summarizes the proposed 4 methods well.", "weaknesses": "Overall, the paper is well-written as a technical report but has room for improvement in terms of scientific discussion or presentation.\n1. Although the light-source-shadow-based explanation is quite helpful in understanding WHAT the proposed methods are doing, but does not explain at all WHY they do so. Specifically, we do not see what 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. Also, readers do not see how we select one of the 4 proposed methods depending on the situation.\n1. Overall, the paper is written as a technical extension of the hyperbolic entailment cone method, but the current draft does not position the proposed method well in the context of the whole partial order embedding area. It is not an unacceptable way, but limits the readers. The authors might want to compare it with other methods such as Order embedding, Gaussian embedding, Box embedding, etc.\n1. The title of the paper lacks essential keywords and confuses readers. It should include the word \"shadow cone.\" Also, if possible, the words \"hierarchy\" or \"partial order\" could be included. Readers might think the phrase \"dark side\" indicates the surface of a hemisphere, rather than a shadow cone. Also, from the word \"moon,\" readers feel the impression that the embedding has a volume. However, this is not the case for the penumbral cone embedding. I am aware that we have many styles on which we title a paper, but, at least, we need to avoid confusing readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)