Capacity and Bias of Learned Geometric Embeddings for Directed Graphs
Year: 2022

Abstract:
A wide variety of machine learning tasks such as knowledge base completion, ontology alignment, and multi-label classification can benefit from incorporating into learning differentiable representations of graphs or taxonomies. While vectors in Euclidean space can theoretically represent any graph, much recent work shows that alternatives such as complex, hyperbolic, order, or box embeddings have geometric properties better suited to modeling real-world graphs. Experimentally these gains are seen only in lower dimensions, however, with performance benefits diminishing in higher dimensions. In this work, we introduce a novel variant of box embeddings that uses a learned smoothing parameter to achieve better representational capacity than vector models in low dimensions, while also avoiding performance saturation common to other geometric models in high dimensions. Further, we present theoretical results that prove box embeddings can represent any DAG. We perform rigorous empirical evaluations of vector, hyperbolic, and region-based geometric representations on several families of synthetic and realworld directed graphs. Analysis of these results exposes correlations between different families of graphs, graph characteristics, model size, and embedding geometries, providing useful insights into inductive biases of various differentiable graph representations.

heading: 1 Introduction
text: Embedding-based methods are a cornerstone of modern approaches to modeling graph data. Geometric embeddings, which represent elements using objects with richer geometric structure (such as boxes [60], cones [27, 58], discs [55], densities [2, 59], and elements of hyperbolic space [39, 40]) have recently been proposed as a powerful alternative to standard vector embedding models for representing asymmetric relationships. Modeling such asymmetric relationships is central to discovering embedded representations of directed graphs, such as DAG-structured taxonomies, where geometric embeddings have been shown empirically to be more effective [39, 58, 60].
The success of geometric embeddings largely rests on exploiting inherent biases intrinsic to the particular geometry chosen. The negative curvature of hyperbolic space, for example, provides an inductive bias which is believed to better model the exponential increase of nodes in trees [39, 61, 62]. Region-based representations, on the other hand, model directional edges via containment relationships [58, 60]. As containment is, itself, transitive, these models would seemingly have a natural bias toward representing transitive relationships. While previous work has empirically tested
⇤ Equal Contribution. † Now at Google.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
the generalization capability of these region-based geometric representations on directed graphs with missing edges [17, 27, 30, 58, 60] an understanding of their representational capability, both theoretically and experimentally, is lacking.
There are several notable open questions regarding geometric embeddings. First, previous work has observed that the performance benefits of geometric embeddings are most strongly observed in low dimensions, and are often diminished or negated by vector models in higher dimensions, raising the question of whether there exists a geometric embedding model which can utilize higher dimensions more effectively. Second, previous work has provided theoretical results for vector [4, 15] and hyperbolic [48, 49] models, but has not addressed what region-based embeddings, such as order and box embeddings, can represent, theoretically. Third, there is not an agreed upon convention for how to empirically analyze the bias and representational capacity of models without confounding factors such as optimization, hyperparameters, and generalization performance.
In this paper, we address each of these open questions. We introduce a novel box embedding model, extending the recently proposed Gumbel-box process [17] to learn from data a parametric model representing a continuous relaxation of box intersections. In this way, we can effectively rely on the structure of the graph to guide the fitting of the embedding model. Our model can trade-off between smoother, vector-like settings and more discrete, region-like settings, providing better performance across both lower and higher dimensionalities in a single model. We provide theoretical analysis of this approach as well as region-based approaches more generally. We lastly design a rigorous evaluation framework, which uses Bayesian hyperparameter optimization to fairly compare representational capacity independently from optimization details of each approach. This empirical framework allows us to characterize properties of graphs for which each method performs well.
In summary, our contributions are as follows:
Methodological Contributions (§3) We introduce a novel continuous relaxation of probabilistic box embeddings, where each node has an associated trained variance or temperature.
Theoretical Contributions (§4): We prove • Order Embeddings may produce cycles, even when pruning reverse edges (Proposition 2) • Probabilistic Order Embeddings (or Order Embeddings under `1 energy) always produce acyclic
graphs when pruning reverse edges (Theorem 1)
While it is known [60] that box embeddings also produce acyclic graphs when reverse edges are removed, we significantly strengthen this by proving
• Any DAG can be represented by Probabilistic Box Embeddings in O(( + 2) log |V |) dimensions, where is the maximum node degree, and |V | the number of nodes (Theorem 2) • This can be accomplished using O(D( +2) log2 |V |) bits of precision, where D is the max depth (Proposition 3)
Empirical Highlights (§6): We conduct a suite of experiments on synthetic and real-world graphs.1 We compare various vector, hyperbolic, cone, and box representations over a range of dimensions, using extensive Bayesian hyperparameter tuning, and find that
• Geometric embedding models perform better in low dimensions • Our model outperforms all other geometric embeddings in high dimensions • Our model always outperforms the state-of-the-art box embeddings when using equal dimensions • Hyperbolic models do particularly well on trees, but struggle with transitivity • Region-based embeddings perform particularly well on transitively-closed graphs

heading: 2 Background: Embedding Directed Graphs
text: Given a simple2 directed graph G with nodes and edges (V,E) we seek to represent the adjacency matrix, that is, a function f : V ⇥ V ! {0, 1} where f(i, j) = 1 if (i, j) 2 E and 0 otherwise. We parameterize the nodes, defining a function : V ! Rd, and define an energy function E : Rd ⇥ Rd ! R+ ,which models the negative log probability of edge existence. We can view
1Our code and data are available at https://github.com/iesl/geometric_graph_embedding. 2A simple directed graph has no multiple edges or self-loops, i.e. the adjacency matrix contains only 0s and
1s, with 0s on the diagonal. We remove self-loops from the learned representations.
the probabilities provided as a weighted graph, however in practice it is often necessary to make a hard decision on edge existence, which is done by choosing a (global) threshold ⌧ and binarizing the output, yielding an adjacency matrix Ai,j = E(i, j) < ⌧ .

heading: 2.1 Vectors
text: A straightforward approach to this problem would be to parameterize each node using a vector, however typical score functions for vectors (e.g., inner-product, distance) are symmetric, and thus would only be capable of embedding undirected graphs. Given a directed graph G, one can always first form an undirected graph G0 = (V 0, E0) with 2|V | nodes, where for each node i 2 V we associate two nodes iin, iout 2 V 0, and for each edge (i, j) 2 E we have an edge (iout, jin) 2 E0. We could embed this graph using symmetric score functions on vectors, for example
E(iout, jin) := log( ( (iout) · (jin))). (1)
Of course this can also be retracted to the original directed graph G, namely given a parameterization : V ! R2d we can define an energy function
ESIM(i, j) := log ✓ ✓ (i)T  0 I 0 0 (j) ◆◆ . (2)
More generally, for (learned) weights W 2 R2d⇥2d we can define a bilinear score function [37],
EBILINEAR(i, j) := log (i)TW (j) . (3)

heading: 2.2 Complex Vectors
text: The models discussed in §2.1 are often considered Euclidean vector embeddings, as they make use of the inner product and linear transformations on Euclidean space. Alternative spaces for representing nodes have been introduced, most notably complex space Cd [57], where the parametrization can be thought of as : V ! Cd with energy function
E(i, j) := log ⇣ ⇣ Re ⇣Pd k=1 (i)kwk (j)k ⌘⌘⌘
(4)
where w 2 Cd and Re projects to the real part. In order to compare this method to previous models, we can also think of this as parameterized by : V ! R2d, where (i)k := Re (i)k and (i)d+k := Im (j)k, in which case the energy function defined as
ECOMPLEX(i, j) := log (i)TW (j)
with W :=  diag(Rew) diag(Imw) diag(Imw) diag(Rew) (5)
is equivalent to (4).

heading: 2.3 Hyperbolic Vectors
text: While the use of bilinear products or complex vectors provide a naturally asymmetric scoring function, one might reasonably ask if there are spaces whose geometry lends itself to representing graphs. It is known, for example, that (undirected) trees can be embedded with arbitrarily low distortion into the Poincaré disk [49], which is not possible in Euclidean space even using an unbounded number of dimensions [31]. These statements are related to undirected graphs, and while the in/out parameterization approach taken in the SIM model could be applied here we would lose any geometric benefit, as the undirected graph G0 corresponding to a tree is not, itself, a tree. Nickel and Kiela [39] suggest that edge direction can be decided by use of the Euclidean norm, and define a score function for an edge (u, v) as score(u, v) = (1 + ↵(kuk kvk))d(u, v), (6) where d is the Poincaré distance and ↵ is a hyperparameter indicating the strength of the penalty for edge directions which violate the order of their norms. An inspection of this score function shows that it is very sensitive to the choice of ↵, which makes training unstable (see Appendix A).
Poincaré distance, in general, suffers from numeric stability issues which have been addressed in more recent work. Nickel and Kiela [40] consider the Lorentz model of hyperbolic space on the
hyperboloid, and Law et al. [28] demonstrates that squared Lorentzian distance on the hyperboloid has similar geometric properties to Poincaré distance, while also providing numerically stable gradients.
Using the notation of Law et al. [28], the hyperboloid is defined as
Hd, := {a = (a0, . . . , ad) 2 R+⇥Rd : kak2L = }, (7)
where > 0, kak2L = ha,aiL is the squared Lorentzian norm of a, and ha,biL is the Lorentzian inner product, and the squared Lorentzian distance d2L : Hd, ⇥Hd, ! R+ is defined as
d2L(a,b) := 2 2ha,biL, ha,biL := a0b0 + Pd i=1 aibi. (8)
Note that ha,biL  for a,b 2 Hd, , with equality if and only if a = b. We also make use of the bijection f : Rd ! Hd, , where f (x) := ⇣p kxkd + , x1, . . . , xd ⌘ 2 Hd, . Given some
parameterization : V ! Rd, we define a new hyperbolic energy function:
EHYPERBOLIC(i, j) := d 2 L(f (i), f (j)) + ↵ log(1 + exp(k (i)k k (j)k)), (9)
where the second term serves as a penalty on Euclidean norms to provide a measure of edge direction, i.e., edges should go from nodes with smaller Euclidean norm to larger. (See Appendix Figure 3)

heading: 2.4 Order Embeddings
text: An order embedding is a mapping between partially ordered sets which preserves the ordering [58]. This relates to our task, as there is a bijection between transitively-closed DAGs and posets. The Order Embedding (OE) model proposed in Vendrov et al. [58] represents elements using vectors in : V ! Rd+, where a partial order is provided via the reversed product order 3: x y ()Vd
k=1 xk yk. These representations can be thought of as infinite cones Cone(x) := {y : x y}, in which case x y if and only if Cone(x) ✓ Cone(y). We consider a model which uses the energy function introduced in Vendrov et al. [58], which provides a smooth penalty for cone containment:
EOE(i, j) := kmax(0, (i) (j))k2`2 . (10)

heading: 2.5 Hyperbolic Entailment Cones
text: Ganea et al. [20] extend the ideas of OE to hyperbolic space, modeling nodes as cones in hyperbolic space. This combines the increased capability of hyperbolic space to represent tree-like graphs with the asymmetry and inductive bias of region-based representations. To do so, the parameterization (i) is iterpreted as the apex of a cone in the Poincaré disk, Dd. Ganea et al. [21] define the following functions:
(x) = arcsin ✓ K
1 kxk2 kxk
◆ , ⌅(x, y) = arccos
hx, yi(1 + kxk2) kxk2(1 + kyk2)
kxk · kx yk p 1 + kxk2kyk2 2hx, yi
!
where (x) is the angle of the cone with apex x, and ⌅(x, y) is the angle between the half lines (xy and (0x. In alignment with our energy interpretation, the energy is given by
EHEC(i, j) := max(0, ( (i) ⌅( (i), (j))). (11)

heading: 2.6 Probabilistic Order Embeddings
text: Lai and Hockenmaier [27] extend OE with a probabilistic interpretation where the volume of the cone under the negative exponential measure represents a marginal probability, P (i) = exp ⇣ Pd k=1 (i)k ⌘ = R Cone( (i))e
z dz. The set of all cones are closed under intersection, i.e. Cone(x) \ Cone(y) = Cone(max(x,y)) where max is the coordinate-wise maximum, thus we can easily calculate the joint probability between elements as P (i, j) =
3As originally defined in Vendrov et al. [58] and Lai and Hockenmaier [27], the vector parameterization for OE and POE was restricted the positive orthant, Rd+, however in practice one can use Rd, as the energy is a function of the difference between vectors which is preserved under translation.
exp ⇣ Pd k=1 max( (i)k, (j)k)) ⌘ . The energy function is logP (i | j), which simplifies to
EPOE(i, j) := kmax(0, (i) (j))k`1 . (12) While seemingly a small difference to OE (10), the probabilistic semantics available to POE have ramifications on its ability to model DAGs, as we will discuss in §4.1.

heading: 2.7 Probabilistic Box Embeddings
text: Probabilistic box embeddings [60] represent elements with d-dimensional hyper-rectangles or boxes, dY
k=1
⇥ x k , x + k ⇤ = ⇥ x 1 , x + 1 ⇤ ⇥ · · ·⇥ ⇥ x d , x + d ⇤ ✓ Rd, (13)
where x k < x + k . Let Bd be the set of all such boxes, along with the empty set. In our notation, these parameters would be provided by : V ! R2d, however for notational convenience we will instead write Box : V ! Bd. As with cones, boxes are closed under intersection and their volumes can be interpreted as probabilities. Namely, by normalizing the space, we have
P (i) = Vol(Box(i)), P (i, j) = Vol(Box(i) \ Box(j)), P (i | j) = Vol(Box(i)\Box(j))Vol(Box(j)) .
Boxes which are disjoint or entirely contained in one another can present problems for learning algorithms, and thus for training box embeddings we use the approach introduced by Dasgupta et al. [17], wherein latent Gumbel noise is added to the box parameters and the previous volume calculation is approximated using a ratio of (analytically calculable and differentiable) expected box volumes, which results in the following energy function:
EBOX(i, j) := logE[Vol(Box(j))] logE[Vol(Box(i) \ Box(j))]. (14)

heading: 3 Probabilistic Box Embeddings with Learned Temperatures
text: In this section, we define our novel box embedding method. As box volume is calculated by taking a product over dimensions, it is sufficient to describe how the calculation is performed in one dimension. Given boxes [x , x+] and [y , y+], note that the volume of intersection is calculated as
Vol([x , x+] \ [y , y+]) = max(min(x+, y+) max(x , y ), 0) (15) The difficulty of training an objective involving hard min/max functions has been addressed previously [17, 30, 60], but for our purposes we will take a practical approach which is standard for deep learning and replace these hard max operators with a smooth approximation, namely
LogSumExp(x; t) = t log( P
i e xi/t) = LSEt(x), (16)
where t is the temperature parameter and LSEt(x) ! max(x) as t ! 0. Thus we can approximate
Vol([x , x+] \ [y , y+]) ⇡ LSEtV ( LSEtI ( x+, y+) LSEtI (x , y ), 0), (17) where we call tI the intersection temperature and tV the volume temperature, as this can be thought of as the composition of approximate intersection and volume functions,
ItI (x ±, y±) := [LSEtI (x , y ), LSEtI ( x , y )], VtV (x±) := LSEtV (x+ x , 0). (18) These temperature parameters may be tuned as global hyperparameters, or they may be trained. In our model, we propose to learn a distributed representation for these hyperparameters. Formally, our model parameterizes each node i via (i) 2 R4d, which we notionally decompose as
(i) =: [ (i) , (i)+, tI(i), tV (i)], (19)
where (i) is the min coordinate of a box, (i)+ the max coordinate, tI(i) the intersection temperature and tV (i) the volume temperature, each of which are vectors in Rd. We define the energy as
ET-BOX(i, j) := logV⌫( (j) ±) log V⌫(I⌧ ( (i)±, (j)±)) (20)
where ⌧ = (tI(i) + tV (j))/2 and ⌫ = (tV (i) + tV (j))/2. (In higher dimensions, the product over dimensions which results from the volume calculation amounts to summing (20) over dimensions.)

heading: 3.1 Connection to BOX
text: We note that the form of this approximation bears a striking similarity to that of the BOX model, which uses the approximation to expected volume derived in [17],
E ⇥ max min(X+, Y +) max(X , Y ), 0 ⇤
⇡ LSE ( LSE (µX , µY ) LSE (µX+ , µY ) 2 , 0) , where the µ values are the location parameters of the respective Gumbel distributions, the parameters are the variance, and is the Euler-Mascheroni constant which arises as a consequence of parameterization via the mode rather than the mean. In practice, [17] is trained by tuning separate (global) hyperparameters for intersection and volume, whereas in our model these temperatures are learned, using a per-node, per-dimension distributed representation. This similarity allows for some light comparisons and intuitions to be drawn from the latent random variable perspective provided by the GumbelBox model, for example we can interpret the learned temperatures tI(i) and tV (i) as capturing some sense of uncertainty related to min and max coordinates for the box representing node i. Our model thus represents each node with it’s own position, scale, and uncertainty, all of which are learned from data, whereas [17] has a fixed global level of uncertainty. The additional representational capacity of our model matches our intuition that some nodes will be best represented with more or less uncertainty than others, and that uncertainty should start high and generally decrease throughout training. Our intuition is borne out experimentally, where we observe that this allows far more flexibility of the model and, for a given embedding dimension d, is always preferable to tuning these temperatures as global hyperparameters (see §6.2).

heading: 4 Theoretical Analysis
text: In this section we explore each region-based model’s theoretical capability to represent a DAG. We consider the adjacency matrix which results from applying a global threshold ⌧ to the energy function, i.e. Ai,j = I[E(i, j)  ⌧ ]. In the following, let U be the set of all undirected graphs, G the set of all directed graphs and D the set of all DAGs. Given a directed graph G 2 G, we denote Gu 2 U the undirected graph such that {i, j} 2 Gu , (i, j) 2 G or (j, i) 2 G. In all cases, we will only consider simple graphs, that is graphs without multiple edges or self-loops, and remove such edges from the thresholded graph, i.e. set Ai,i = 0. We define GM(n, ⌧) ✓ G as the set of all graphs with adjacency matrices realizable as the thresholded energy function of model M. That is, G = (V,E) 2 GM(n, ⌧) if and only if there exists some setting of parameters : V ! Rn such that EM(i, j)  ⌧ () (i, j) 2 E. We also define GM(n) := S ⌧2R+ GM(n, ⌧)
and GM := S n2N GM(n).

heading: 4.1 Asymmetrization
text: An initial observation is that GM is not necessarily a subset of D. For example, it may be the case for some parameterization that EM(i, j)  ⌧ and EM(j, i)  ⌧ . We can address this issue with one additional constraint: let GASYMM ✓ G be the set of graphs G where edge (i, j) exists if and only if
EM(i, j)  ⌧ and EM(i, j) < EM(j, i). (21)
This approach was adopted in Vilnis et al. [60], where it was proved that GASYMM ✓ D for any model which uses conditional probabilities for the energy function. Proposition 1 (Vilnis et al. [60]). Suppose EM(i, j) = logP (Xi | Xj) for some probability distribution P over binary random variables {Xi}i2V , then GASYMM ✓ D.
For completeness, we include a version of this proof in Appendix B. The following is an immediate consequence. Corollary 1. The asymmetrization of Probabilistic Order Embeddings, which use energy function EPOE(i, j) = kmax(0, (i) (j))k`1 , will always yield a DAG, that is GASYMPOE ✓ D.
A direct proof of this fact is also provided in Appendix B. An interesting observation is that this same condition is not sufficient for all methods, in particular it does not apply to OE, despite the similarity in energy function:
Proposition 2. The asymmetrized adjacency matrix for order embeddings, with energy EOE(i, j) = kmax(0, (i) (j))k2`2 , may not yield an acyclic graph, i.e. GASYMOE 6✓ D.
The proof can be found in Appendix B.

heading: 4.2 Representational Capacity
text: The statements in the previous section discuss when it is possible to, for any parameters in a given model, extract a DAG by thresholding the energy function and asymmetrizing. The arguably more interesting question, however, is whether a given model can represent all DAGs, i.e. do we have D ✓ GM? Bhattacharjee and Dasgupta [4] refer to the SIM model as a similarity embedding, and prove that it can represent any graph, and by extension so can BILINEAR. Here we provide a proof that box embeddings can represent any DAG, i.e. D ✓ GBOX. The concept of boxicity of an undirected graph G = (V,E) 2 U was introduced by Roberts [45] as the minimum d for which there exists a parameterization Box : V ! Bd such that {i, j} 2 U if and only if Box(i) \ Box(j) 6= ;. Roberts [45] also proves that the boxicity of any graph is at most b|V |/2c. We leverage this result to prove the following. Theorem 2. Given any G = (V,E) 2 D, there exists a parameterization Box : V ! Bd and threshold ⌧ such that ET-BOX(i, j) < ⌧ if and only if (i, j) 2 E.
Proof Sketch We first obtain a boxicity representation for the undirected graph Gu = (Vu, Eu), for which i, j 2 Eu if (i, j) 2 E or (j, i) 2 E. In this representation, Box(i)\Box(j) 6= ; implies that either (i, j) 2 E or (j, i) 2 E, and thus we simply must adjust the marginal volumes to represent the correct direction without disrupting the existing overlaps. We can by extending into one more dimension, and assigning heights of the boxes in this new dimension in accordance with a topological sort. For full details, see the proof in Appendix C.
As our proof is constructive, existing boxicity algorithms can be extended to represent any directed graph in this manner, which also serves to provide dimensionality bounds. For example, Chandran et al. [14] provide a randomized algorithm to generate a boxicity representation of an undirected graph U = (V,E) in O(( + 2) log |V |) dimensions where is the maximum degree of U . We include a version of this randomized algorithm in Appendix E, where slight modifications were made to guarantee a positive box volume and avoid boxes touching each other but not overlapping.
These theoretical statements apply in the limit where the box temperatures ! 0, however the fact that the temperatures are trainable in T-BOX makes this setting feasible, and further is frequently observed empirically during training.

heading: 4.3 Precision
text: It is well known that representation results may trade-off dimensions for an increase in precision. For example, Kang and Müller [24] show that embedding an undirected graph using vectors in minimal dimension could require O(e|V |) bits. For this reason, we provide an upper bound on the required bits for the constructive proof. Proposition 3. Given G 2 D, there exists a box embedding of G in dimension O(( + 2) log |V |) requiring O(D( +2) log2 |V |) bits per box, where D  |V | is the depth of G, and the maximum degree.
Proof Sketch. We consider each dimension of the boxes in the construction for theorem 2. For all but the last dimension, we can use integer coordinates and preserve box overlaps. This is the boxicity representation, and thus requires d = O(( +2) log |V |) dimensions, thus the total precision required for these dimensions is O(( + 2) log2 |V |). For the last dimension, we can choose a threshold ⌧ = 2 dd log(2|V |)e. By construction, h(j) = ⌧k for some k = {0, . . . , D}, thus we conclude that this dimension requires O(Dd log |V |) bits. See Appendix F for a complete proof.

heading: 5 Objectives for Learning
text: We fit geometric embeddings by optimizing a binary cross entropy objective, interpreting the energy functions described in §2 and §3 as negative log probability of edge existence, and compare the F1
score using an optimal threshold. We sample minibatches of positive edges; for each positive edge we sample 128 (true) negative examples uniformly at random, and use a self-adversarial negative weight, as described in [54]. For EOE and EHEC, to remain consistent with the originals, we use the loss function as described in Vendrov et al. [58]. Additional details are provided in Appendix D.

heading: 6 Experiments
text: In this section, we empirically analyze the following questions:
• How well can each of the embedding models, fit with gradient descent, represent a given graph? • How does the model’s embedding dimensionality or number of parameters impact performance? • What characteristic properties of graphs are indicative of performance of the embedding models?
To test hypotheses regarding representational capacity and inductive biases, we evaluate on a wide variety of both synthetic and real-world graphs. To avoid optimization difficulties, all embedding models are extensively tuned using Bayesian hyperparameter optimization.

heading: 6.1 Experimental Setup
text: Graphs - Synthetic. We select five generative models of graphs to build synthetic datasets, aiming for diversity in the kinds of graphs used for evaluation. Each generative model has hyperparameters that control the particular structure of the generated graph. These include: Balanced Trees (branching factor b); the Nested Chinese Restaurant Process, [6] (normalized “new table” probability ↵), which is a non-parameteric tree structure with rich-get-richer properties; Price’s model [42] (num. connections for new node, m, probability of vertex receiving an edge, c), which simulates growth of citation networks with preferential attachment and is the directed version of the Barabási–Albert model [1]; Scale-Free Networks [7] (↵, , , in) exhibit a power-law degree distribution. We consider a directed scale-free model for which both the in- and out-degree distributions follow powerlaw distributions; Kronecker graphs [29] (initial seed matrix {a, b; c, d} and the Kronecker power k) are a generative model for graphs which provably exhibit many of the properties of real-world graphs. Please refer to Appendix G for more details.
Graphs - Real World. We also select the following real world graph datasets: WordNet (Animals) [34]. In our experiments, we took the subtree of “animal” which contains 4,017 nodes and 4,051 direct edges as well as the transitive closure (29,795 edges). Hierarchical Clustering. We run agglomerative clustering on the InceptionV3 [56] features from 213 ImageNet images [47]. Using the same features we also build and use a K-Nearest Neighbor Graph (using K=5).
Evaluation Metric for Representational Capacity. Representational capacity is a measure of reconstruction performance, not generalization. Given a graph G?, each model is fit on G? and predicts a graph Ĝ. We report the F1 measure between the edges of G? and Ĝ to measure performance.
Hyperparameter Optimization. To remove hyperparameters as confounding factors to the model’s performance (and inferred representational capacity), we perform extensive Bayesian hyperparameter optimization using W&B [5]. For each of the generative models, we consider a variety of settings for generating samples (see Appendix, Table 1). For each setting ✓ 2 ⇥, we sample 10 graphs G✓, and then run a dedicated hyperparameter search for each embedding method to maximize the expected performance over sampled graphs. Then for each G✓, we choose the best F1 achieved in the hyperparameter search and we report the average performance over all 10 sampled graphs from a type of generative model. In total we have 58 hyperparameter settings over these five types of graphs, which leads to 508 graph samples. For each real world graph, we also perform a hyperparameter search. In both cases we calculate F1 over the full adjacency matrix.
Model details. We empirically compare each of the geometric embeddings and energy functions described in Section 2: : ESIM, EBILINEAR, ECOMPLEX, EHYPERBOLIC, EOE, EPOE, EBOX, and the proposed learned-temperature box model ET-BOX. All models are tuned on learning rate, batch size, and weight of negative loss. We tune the margin for OE, ↵ and parameters in (9) for HYPERBOLIC, intersection and volume temperature for BOX, and the initialization of these temperatures for T-BOX. We check the training loss ten times per epoch, and apply early-stopping with a patience of just over 2 epochs (21 loss observations).

heading: 6.2 Results & Analysis
text: Figure 1 reports the mean (and for synthetic graphs, standard deviation) of F1 performance for each model on synthetic and real world graphs, with 8, 32, 128 parameters per node (not dimension).
Observation: Geometric embeddings excel over vectors in low dimensions. In the lowest dimensions, the BOX model achieves the highest average F1 on the datasets except the two tree-based datasets (nCRP and balanced trees without transitive closure). Hyperbolic is top performing on the tree-based datasets, consistent with previous work. Vector-based approaches perform significantly worse in lower dimensions. This is consistent with the intuition that vectors have flexible representation capacity but lack the inductive biases for better performance in lower dimensions. Further, the hyperbolic methods tend to struggle to on transitively closed graphs.
Observation: T-BOX out-performs other geometric models in higher dimensions The flexibility of the vector-based approaches (i.e. SIM, COMPLEX, BILINEAR) can more easily fit graphs with more parameters/higher dimensions. However, previous geometric embedding models do not observe as rapid a performance increase as we increase the dimension. In comparison, our proposed T-BOX can significantly improve the performance on larger dimensions and leads to best overall performance in both high and low dimension space.
Observation: T-BOX consistently improves BOX for fixed dimension. While T-BOX(/N/D) generally outperforms BOX, we observe that when there are 8 parameters per node T-BOX(/N/D) achieves lower F1 scores than BOX. With 8 parameters per node, the BOX has 4 dimensional boxes and the T-BOX(/N/D) has 2 dimensional boxes. The reduction to two dimensional boxes restricts the capacity. We subsequently analyze the performance of the models as a function of dimension (rather than number of parameters). In Figure 2, we verify that learning the temperature improves expressiveness by comparing BOX, T-BOX, T-BOX(/D), T-BOX(/N), T-BOX(/N/D) for various dimensionalities. Results indicate that a T-BOX(/N/D) always out-performs original BOX.
Observation: Relationship between Graph Characteristics & Model Performance. To get better insight about why certain graphs are easier/harder for methods to embed we calculate graph statistics, including sparsity; clustering coefficient; reciprocity (i.e. proportion of reverse edges); flow hierarchy (fraction of edges not in cycles). We are interested in understanding which graph properties are representable by which models. In Appendix I, we show parallel coordinate plots among different models and calculate Spearman correlation ⇢ between relative F1 and graph characteristics. These reveal that: box embeddings tend to prefer graphs with lower degree, lower clustering coefficient, higher flow hierarchy and lower reciprocity, indicating these geometric embeddings can better model directed graphs with less cycles and lower density.

heading: 7 Related Work
text: Our work intersects several related areas of machine learning including: distributed representations, probabilistic models of graphs, representations of graphs and knowledge-graph link prediction.
Geometric Embeddings. Using geometrically shaped embedded representations instead of simple vector-based models have considered Gaussian distributions [59], cones in both Euclidean [58] and hyperbolic space [20], and boxes [53]. Region-based embeddings whose representation can be assigned a volume under some finite measure can also be normalized to represent a probability distribution, as has been done with cones [27] and boxes [60]. Recent work also seeks to improve the learning capability of geometric embeddings. In the hyperbolic setting, new parameterizations which allow for more efficient Riemannian optimization [40] or alternative distance functions [28] have been proposed. For box embeddings, improvements to training have been introduced by smoothing the objective via convolution [30] or by using a latent noise model with a closed-form solution [17]. In this work, to fairly compare all methods, we take these recent improvements into account.
Representing Graphs. Embedded representations of graphs has also been widely studied [8, 11, 15, 23, 28, 32, 40, 38, 41, 57, 61, 63]. Embedding tree structures in hyperbolic space both algorithmically [48, 49] as well as multi-dimensional scaling [48]. Hyperbolic space has also been used in representing tree structured latent variables [33, 51] and for hierarchical clustering [12, 35]. Most similar to our work, Weber [61] analyzes the representational capacity of different geometries (Euclidean, hyperbolic, spherical) on undirected graphs, however this is concerned with the distortion of a graph, i.e., attempting to preserve distances between nodes, whereas our work investigates the ability of a graph to perform edge classification.
Knowledge Graph Embeddings. The representation of directed graphs and prediction of missing edges has been widely studied in the setting of completing missing information in knowledge graphs [8, 13, 22, 26, 36, 44, 52, 54, 64]. Many novel representations have been created for this purpose, such as complex [57] or quaternion [65] vector representations. The task setting differs from our work in various ways - the graph can be viewed as an multi-graph with labeled edges, and the objective is to recover missing edges - however one of the main goals of our work is to provide insight into the inductive biases present in the geometric embeddings which can be used for such a task.
Probabilistic Models. Probabilistic models has been studied for both graph generation and link prediction. Probabilistic generative models of graphs are widely studied to generate undirected graphs such as Erdos-Rényi [18], Barabási-Albert [3] and directed graphs such as Price’s Model [42], Kronecker [29] along with others [6, 9, 10, 16]. There are also Bayesian non-parametric models for link prediction in directed and relational graphs [19, 25, 46].

heading: 8 Conclusion
text: In this paper, we examine the representational capacity and inductive biases of learned representations of graphs. We theoretically and empirically analyze geometric embedding methods for modeling directed graphs. We prove theoretical statements about order embeddings, probabilistic order embeddings, and box embeddings. We propose a new box embedding model that learns temperatures which out-performs other geometric representations in low dimension and shows competitive performance with vector-based models in high dimension. We perform an empirical comparison of seven methods on both synthetic datasets and real world datasets. Our work describes meaningful theoretical foundations and empirical analysis of geometric representations of directed graphs.

heading: Acknowledgements
text: This work supported in part by the Center for Data Science and in part the Center for Intelligent Information Retrieval, and in part by the National Science Foundation under Grants No. 1763618, University of Southern California subcontract no. 123875727 under Office of Naval Research prime contract no. N660011924032, and in part by IBM Research AI through AI Horizons Network, and in part by the Chan Zuckerberg Initiative under the project “Scientific Knowledge Base Construction”. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Some of the work reported here was performed using high performance computing equipment obtained under a grant from the Collaborative R&D Fund managed by the Massachusetts Technology Collaborative. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect those of the sponsor.

Review summaries:
This paper analyses models for node embeddings of directed acyclic graphs (DAGs). It has 3 contributions:   i) it proposes a relatively straightforward extension of probabilistic box embeddings P-BOX [56], called t-BOX which is similar to the previous GumbleBox model [14], but has per-dimension and per-node intersection and volume temperature parameters (learnable) as opposed to just global parameters (as in GumbleBox). This extension is natural and the motivation is clear, but comes with the cost of doubling the number of parameters of the P-Box and GumbleBox models.  ii) theoretically, it extends the prior theory of [41] and [13] (which was analysing only undirected graphs) to work with DAGs and prove  that their t-Box model can represent any DAG (theorem 2, proof is an extension of [41]), giving an upper bound on number of dimensions and bits per box (proposition 3, proof is an extension of the result in [13]). Moreover, corollaries 1 and 2  are also the authors' contributions, being simple extensions of the result  in [56]. These theoretical results are important for understanding the representational capacity of existing DAG embedding models and I find this section nice and well written.  iii) Empirically, the authors evaluate the representational capacity (not generalization, just the "overfitting" ability) of several popular DAG embedding models on a variety of synthetic and real datasets. The choice of datasets is diverse and the empirical evaluation (e.g. removing the hyperparameters as confounding factors) is compelling, however, there are a few downsides that I will discuss below.

This work provides an empirical and theoretical foundation for the analysis of geometric representations of directed graphs. The paper introduces a novel box embedding model, extending the recent Gumbel-box process to learn a parametric model representing a continuous relaxation of box intersections. The model can trade-off between smoother, vector-like settings and more discrete, region-like settings, and provides better performance across a range of dimensionalities.  Directed graphs have received considerably less attention in the representation learning community than undirected graphs, making this paper particularly appealing. 

# A solid work on Geometric Embeddings  This paper discusses the properties of recent geometric embeddings for representing graphs and extends a new continuous relaxation of the probabilistic box embeddings. This paper is written is a clear way: the motivation and contribution are clear, and backed up by extensive experiments. Theoretical contributions, especially the precision bound for box embeddings, are presented in parallel with its methodological contribution. Based on these strengths, although there are some issues (discussed below), I give a clear accept of this paper.