Capacity and Bias of Learned Geometric Embeddings for Directed Graphs
Authors: Michael Boratko
Dongxu Zhang
Nicholas Monath
Luke Vilnis
Kenneth L. Clarkson
Andrew McCallum
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph embeddings
representation learning
knowledge graphs
structured prediction

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 real-world directed graphs. Analysis of these results exposes correlations between different families of graphs, graph characteristics, model size, and embedding geometry, providing useful insights into the inductive biases of various differentiable graph representations.

Capacity and Bias of Learned Geometric Embeddings for Directed Graphs
Michael Boratko"', Dongxu Zhang Nicholas Monath 1.1, Luke Vilnist.,
Kenneth L. Clarkson", Andrew McCallum
University of Massachusetts Amherst
IBM Research
(mboratko, dongxuzhang, nmonath, luke, mccallum)@es umass edu klclarks@us.. ibm. com
Abstract
A wide variety of machine learning tasks such as knowledge base completion, ontology aligmment, and multi-label classification 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 modeling real-world graphs. Experimentally these gains are seen only in lower dimensions, however, with performance benefits diminishing in higher dimensions. In this work, introduce 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 real- world 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)
Introduction
Embedding-bartd -based methods comerstone of modern approaches modeling graph data. Geo- metric embeddings, which represent elements using objects with richer geometric structure (such as boxes (60) cones
58 discs [55], densities 59 and elements of hyperbolic space (39 40
have recently been proposed as powerful alternative to standard vector embedding models for repre- senting asymmetric relationships. Modeling such asymmetric relationships is central discovering embedded representations of directed graphs, such as DAG-structured taxonomies, where geometric
embeddings have been shown empirically be more effective B9 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 believed to better model the exponential increase of nodes in trees k9
61 62] region-based representations, on the other hand, model directional edges via containment relationships [58 50] As containment is, itself, transitive, these models would seemingly have natural bias toward representing transitive relationships. While previous work has empirically tested
Equal Contribution. Now at Google.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the generalization capability of these region-based geometric representations on directed graphs with missing edges [1
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 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 and hyperbolic 44 99 models, but has not addressed what region- based embeddings, such as order and box embeddings, can represent, theoretically. Third, there 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.
negated by vector models in higher dimensions,
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] learn from data parametric model representing a continuous relaxation of box intersections. In this way, we can effectively rely on the structure of the graph 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 a single model. We provide theoretical analysis of this approach as well as region- based approaches more generally. We lastly design rigorous evaluation framework, which uses Bayesian hyperparameter optimization 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.
fairly compare
In summary, our contributions are as follows:
Methodological Contributions ( We introduce a novel continuous relaxation of probabilistic box embeddings, where each node has an associated trained variance or temperature.
Theoretical Contributions
We prove
Order Embeddings may produce cycles, even when pruning reverse edges (Proposition 2 Probabilistic Order Embeddings (or Order Embeddings under e energy) always produce acyclic graphs when pruning reverse edges (Theorem
While it is known 660 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((A + 2) log [V]) dimensions, where A is the maximum node degree, and [V| the number of nodes (Theorem
This can be accomplished using O(D(A log" [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 | 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-arr box embeddings when using equal dimensions
Hyperbolic models do particularly well on trees, but struggle with transitivity
Region--aasse based embeddings perform particularly well on transitively-closed graphs
2 Background: Embedding Directed Graphs
Given Cimplteddrrected graph G with nodes and edges (V,E) we seek to represent the adjacency matrix, that is, function f V x + {0, 1} where s(i,j) = (i,j) E E and otherwise. We parameterize the nodes, defining a function & V - Rd. and define an energy function E. Rd x Rd + R4 which models the negative log probability of edge existence. We can view
I Our code and data are available at
AA simple directed graph has no multplee edges or self- Le. the adjacency matrix contains only Os and 1s, with Os 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 hard decision on edge existence, which is done by choosing a (global) threshold and binarizing the output, yielding an adjacency matrix Aij = F(i,j)
2.1 Vectors
straightforward approach 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 directed graph G, one can always first form undirected graph G" (V', F*) with 2|V| nodes, where for each node E V we associate two nodes lin: fout V", and for each edge (i. E have an edge Fin E F.. We could embed this graph using symmetric score functions vectors, for example
B = log(o( ((in))).
(1)
Of course this can also retracted to the original directed graph G, namely given a parameterization V 2d define energy function
EsiM (i. == log (o (a(00)))
0 / ob)))
(2)
More generally, for (learned) weights W E 2ddd we can define bilinear score function
ERH (i, = = -ooooog log (o
(3)
2.2 Complex Vectors
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 (5 where the parametrization can be thought as vp V Cd with energy function
= - log (o (Re (Et- (()) =(i,))=
(4)
where E Cd and Re projects to the real part. In order to compare this method to previous models, we can also think this as parameterized by Φ V V- Rd where d(t); == Re (t)x and <(i)a++ Im (f)),. in which case the energy function defined
diag Rew) diag (Im w)
diag [mm w) diag (Re w)
ECOMPLEX (i. log (a (d(i)TWo(i)) with W
(5)
is equivalent to
2.3 Hyperbolic Vectors
While the use 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. 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
using unbounded number dimensions GII These statements are related to undirected graphs, and while the in/out parameterization approach taken in the SIM model could be applied here would lose any geometric benefit, as the undirected graph G' corresponding to a tree not, itself, a tree. Nickel and Kiela [39 suggest that edge direction be decided by of the Euclidean norm, and define score function for an edge (u, v) as
score(u, v) -1 a<[|u]] - [[el))d v).
where dl is the Poincaré distance and is 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 the choice of o, which makes training unstable (see Appendix A).
Poincaré distance, 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 the

---

hyperboloid. and Law et al. similar geometric properties Poincaré distance, while also providing numerically stable gradients.
28 demonstrates that squared Lorentzian distance on the hyperboloid has
Using the notation of Law et al. 28 the hyperboloid is defined as
Hd. = {a (ao....,.u) Ud) E R4xR" ||ll = -3).
where 3 > 0, ||a| = (a. a c is the squared Lorenizian norm of a, and (a, b) is the Lorenizian inner product, and the squared Lorentzian distance d² HHd Hd,8 - R2+ is defined as
(a b) = 23 - -2(a, b)
(a, b) == aaoo + Ei a;b:-
Note that (a. 2) S -3 for a, b E 74d10, with equality if and only if a = b. We also make use of the bijection fa RR + Hd.0. where fa(x) = [V]x[| 3, Rdd E Hd. Given some parameterization Φ V + R2 we define new hyperbolic energy function:
EHYPERROLII (i = dfs fz. o o()) + a log(1 + exp(1l - ())())))) (9)
where the second term serves as a penalty on Fuclidean norms to provide a measure of edge direction, i... edges should go from nodes with smaller Euclidean norm to larger. (See Appendix Figure
2.4 Order Embeddings
An order embedding is a mapping between partially ordered sets which preserves the ordering 58 This relates to task, there is bijection between transitively-cloeed DAGs and posets. The Order Embedding (OE) model proposed in Vendrov et al. (58] represents elements using vectors in á V IR. where a partial order is provided via the reversed product order y e
Ak= TK 2 yk- These representations can be thought of as infinite cones Cone(x) == { x in which case function introduced in Vendrov et al. (58). which provides a smooth penalty for cone containment:
if and only if Cone(x) C Cone(y). We consider model which uses the energy
Eou (1, = |aax ((1) - .(f))|lB.
(10)
2.5 Hyperbolic Entailment Cones
Ganea et al. 20 extend the ideas of OE to hyperbolic space, modeling nodes 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- representations. To do so, the parameterization o()) is iterpreted as the apex of a cone in the Poincaré disk, Dd. Ganea et al. [21] define the following functions:
(xx) aresin [ (K--
(K--1l=1? ||=]32) |
(z, v) | 2 |1 11yl)
E(r,y) = arccos
||a||| |
v/l
/
- 1
2 v)
where (xx) is the angle of the cone with apex x, and E(x, y) is the angle between the half lines (zy and (Ox. In alignment with our energy interpretation, the energy is given by
EHEc(i,j) = max(0, (d((1) ((((),
(11)
2.6 Probabilistic Order Embeddings
Lai and Hockenmaier 27 extend OE with a probabilistic interpretation where the volume of the cone under the negative exponential measure represents marginal probability, P(i) exp (-
= f e dz. The set of all cones are closed under intersec- tion, Lee. Cone(x) n Conely) = Cone(max(x, y)) where max is the coordinate-wist max- imum, thus can easily calculate the joint probability between elements as P(i.j)
3 As originally defined in Vendrov et al. (88 and Lai and Hockenmaier (77). the vector parameterization for OE and POE was restricted the positive orthant, RL. however in practice one can use g as the energy is a function of the difference between vectors which is preserved under translation.

---

exp (-Ex- k== max(o(i) +()xa)) The energy function is - log P(i j), which simplifies to
EPor (i, max <(t) +
(12)
While seemingly small difference to OF (T)) the probabilistic semantics available to POE have ramifications on its ability to model DAGs, as we will discuss in $
2.7
Probabilistic Box Embeddings
Probabilistic box embeddings 660 represent elements with d-dimensional hyper-rectangles or boxes,
TE xx = [a] xx1' x x [ xx1 CR"
(13)
where dg < x Let Bd be the set of all such boxes, along with the empty set. In our notation, these parameters would be provided by & V R22, 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 probabilities. Namely, by normalizing the space, we have
P(i) Vol(Box()). P(i.j) Vol(Box(1) Box(j)), P(i j)
Vol(Box( (B)()))))))))))))) (ol(())())
Boxes which are disjoint or entirely contained one another can present problems for learning algorithms, and thus for training box embeddings use the approach introduced by Dasgupta et al. [17., wherein latent Gumbel noise is added the box parameters and the previous volume calculation is approximated using ratio of (analytically calculable and differentiable) expected box volumes, which results the following energy function:
Box (i, = log E [[[ol(Box(()) - log E. Volo( Box(j)))
(14)
3 Probabilistic Box Embeddings with Learned Temperatures
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 [xr x]+ and [y , v. note that the volume of intersection is calculated as
Vol((= x Tyr 1) max(min(2"" "aaaii(""""""""" .,++t*"++++++++" max(#" (oxxx=Ty7) .y.)).)))
(15)
The difficulty of training an objective involving hard min/max functions has been addressed previ- ously [17 30 60), but for purposes will take practical approach which is standard for deep learning and replace these hard max operators with a smooth approximation, namely
LogSumExp(xx: t) log ez./t) (x),
(16)
where is the temperature parameter and LSE, > max(x) (x) as 1 + 0. Thus we can approximate Vol([= x +I+ [yr +)+))= ss I.SE,,, (- L.FE, (-x+,-y") I.SE, (x . ),)),,
(17)
where we call tt the intersection temperature and tv the volume temperature, as this can be thought of as the composition of approximate intersection and volume functions,
I,, (x+ y+ = ILSE,, (x=, ..), LSE,, --x",,")1)
V (x+) LSE,, (x+ x x,,0 0).
(18)
These temperature parameters may be tuned as global hyperparameters. or they may be trained. In our model, we propose learn distributed representation for these hyperparameters. Formally, our model parameterizes each node via ((i) E Rdd, which we notionally decompose as
<(1) = [0(1) (0))+ tt),
(19)
where (bi)- is the min coordinate of box, ((i)+ the max coordinate, (r(i) the intersection tempera- ture and (i) the volume temperature, each of which are vectors in Rdd We define the energy as
E Box = log Vo( log V=(I-((0)) +())))
(20)
where - = + 4vx)))2 and v = (1) + (2)/22 (In higher dimensions, the product over dimensions which results from the volume calculation amounts to summing 20 over dimensions.)
5

---

3.1
Connection to Box
We note that the form of this approximation bears striking similarity to that of the Box model, which uses the approximation to expected volume derived in [17].
E max (min(X*, , -max X ..)
LSE3 (- LSE (1x : -y-) LSE 100))22))))) 27,0), 0),
where the y values are the location parameters of the respective Gumbel distributions, the 3 param- eters 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, [7] is trained by tuning separate (global) /8 hyperparameters for intersection and volume. whereas in model these temperatures learned, using a per-node, per-dimension distributed representation. This similarity allows for some light comparisons and intuitions be drawn from the latent random variable perspective provided by the GumbelBox model, for example we can interpret the learned temperatures ty (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 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 given embedding dimension d, is always preferable to tuning these temperatures as global hyperparameters (see $6.2
4 Theoretical Analysis
In this section we explore each region-based model's theoretical capability to represent DAG. We consider the adjacency matrix which results from applying global threshold to the energy function, i.e. A,,, J)) S r]. In the following, let 24 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 E Gg we denote G, E U the undirected graph such that {i,j} G, + (i.j) E Go (j,t) G. all cases, we will only consider simple graphs, that is graphs without multiple edges self-loops, and remove such edges from the thresholded graph, i.e. set A,, = O. We define Gm r) S g as the set of all graphs with adjacency matrices realizable as the thresholded energy function of model M. That is. G = E) E (n, r) if and only if there exists some setting of parameters á V R= such that Em(i,5) S and GM UnEN (n).
(i,5) E. We also define (n) = UPER, GM (n,,))
4.1 Asymmetrization
An initial observation is that 9M is not necessarily a subset of D. For example, it may be the case for some parameterization that (M, j) I and Em(j, i) S r. We can address this issue with one additional constraint: let gASYM C 9 be the set of graphs G where edge (i,j) exists and only if
E) S and Ei Esa ij.
(21)
This approach was adopted in Vilnis al. 600, where it was proved that GASYM C D for any model which uses conditional probabilities for the energy function.
Proposition (Vilnis et al. (60). Suppose EM(i,J) = - llg P(X, | distribution over binary random variables {Xi)vev, then g
Xý) some probability
gASYM C 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 [0000=||mxxxxx0 ||max((0, ((i) - +(j)) ee,, will always yield a DAG, that is GASY C D.
Epon(i.j. (i.j) =
A direct proof of this fact is also provided in Appendix B An interesting observation is that this same condition not sufficient for all methods, particular does not apply to OF, despite the similarity in energy function:

---

Proposition 2. The asymmetrized adjaceney matrix order embeddings, with energy Ei [|max(0, ((a) - <(j) (2, may not yield an acyclic graph, i.e. G g D.
The proof can be found Appendix
B
4.2 Representational Capacity
The statements in the previous section discuss when it is possible to, for any parameters in a given model, extract 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 9M Bhattacharjee and Dasgupta 44] refer the SIM model 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 C |BRxx
The concept of boxicity of an undirected graph G = EV E was introduced by Roberts 45 as the minimum for which there exists parameterization Box - Bd such that (i,s) E U if and only if Box(i) n Box(j) * Ø. Roberts [45] also proves that the boxicity of any graph is at most [IV]/2]. We leverage this result to prove the following.
Theorem 2. Given any G = (V, F) DD there exists parameterization Box V Bd and threshold r such that F (1, < T if and only (i.,) E F.
Proof Sketch We first obtain a boxicity representation for the undirected graph G2 (V,, E.), for which j. E E. (i. E E (j. E E. In this representation, Boz(i) Boz(j) * 0 implies that either (i,j) E or (j.o) () E 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. E provide a randomized algorithm to generate a boxicity representation of an undirected graph U (V, E') in O((A + 2) log [V]) dimensions where A is the maximum degree of U. We include 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 + O, however the fact that the temperatures are trainable in T-Box makes this setting feasible, and further is frequently observed empirically during training.
4.3 Precision
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(elVl) bits. For this reason, we provide an upper bound on the required bits for the constructive proof.
Proposition 3. Given G D, there exists box embedding of G in dimension O((A + 2) log [V]) requiring O(D(A+ log2 |Vl) bits per box, where D < |V| is the depth G, and A 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 integer coordinates and preserve box overlaps. This is the boxicity representation, and thus requires d = ((((0(((())) 22) log [V]) dimensions, thus the total precision required for these dimensions is O((A= + 2) log² [V])- For the last dimension, we can choose a threshold
7 2 ( By construction, h(j) = A for some k = {O..... D}. thus we conclude that this dimension requires O(Dd log [V) bits. See Appendix for complete proof.
5 Objectives for Learning
We fit geometric embeddings by optimizing a binary cross entropy objective, interpreting the energy functions described in 2 and S aas negative log probability of edge existence, and compare the F1
7

---

Figure I: Representational Capacity We plot the Fl score for each embedding method using 8, 32, and 128 parameters per node. TC indicates that the transitive closure is applied to the graph. /n and /d indicate box models have per node per dimension learned temperatures.
score using an optimal threshold. We sample minibatches of positive edges; for each positive edge sample 128 (true) negative examples uniformly random, and use self aiferarresaliall 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 al. [58] Additional details are provided in Appendix D
6 Experiments
In this section, we empirically analyze the following questions:
How well each of the embedding models, fit with gradient descent, represent given graph? How does the model's ' embedding dimensionality or number of parameters impact performance? What characteristic properties of graphs indicative of performance of the embedding models?
To test hypotheses regarding representational capacity and inductive biases, we evaluate on wide variety of both synthetic and real-world graphs. To avoid optimization difficulties, all embedding models are extensively tuned using Bayesian hyperparameter optimization.
6.1 Experimental Setup
Graphs - SSyttheic. We select five generative models of graphs to build synthetic datasets, aiming for diversity 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 a), which is a non-paraeeteric 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-Alhert model M Scale-Free Networks (7] (a, 3, 7, 6,n) exhibit a power-law degree distribution. We consider directed scale-free model for which both the in- and out-degree distributions follow power- law distributions; Kronecker graphs (29] (initial seed matrix (a, b; c, d} and the Kronecker power k) are 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) 351 our experiments, we took the subtree of "animal" which contains 4,017 nodes and 4,051 direct edges as well the transitive closure (29,795 edges). Hierarchical Clustering. We run agglomerative clustering on the Inception (5 features from 213 ImageNet images 47 Using the same features also build and use K-Nearest Neighbor Graph (using K=5).

---

Evaluation Metric for Representational Capacity. Representational capacity is measure of reconstruction performance, not generalization. Given a graph G", each model 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 variety of settings for generating samples (see Appendix, Table D For each setting 0 E θ, we sample 10 graphs Gg, and then run a dedicated hyperparameter search for each embedding method to maximize the expected performance over sampled graphs. Then for each Gg. we choose the best Fl 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 Fl over the full adjacency matrix.
Model details. We empirically compare each of the geometric embeddings and energy functions described in Section - EsIM. EBLLNNAR. ECOMPLEX. EHYPERBOLIC EOE, Erog. EBOx. and the proposed learned-tempae temperrture box model BT-Box. All models are tuned on learning rate, batch size, and weight of negative loss. We tune the margin y for OE, a and parameters in 2 for HYPERBOLIC. intersection and volume temperature for Box, and the initialization of these temperatures for T- 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).
6.2 Results& & Analysis
Figure 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).
Geometric embeddings excel over vectors in low dimensions. In the lowest dimen- sions, the BOX model achieves the highest average Fl 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 representa- tion 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:
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) gener- ally 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).
Figure 2 we verify that learning the temperature improves expressiveness by comparing Box, T- Box, T- T-BOX T-BOX(/N), T- T-BOX(/N/D) for various dimensionalities. Results indicate that a T- BOX((//DDDD always out-performs original Box.
Relationship between Graph Characteristics & Model Performance. To get better insight about why certain graphs are easier/harder for methods 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 ! we show parallel coordinate plots among different models and calculate Spearman correlation p between relative Fl 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.
Observation:

---

Poggete IN!
Ertt drari
Brohitaring
WinD STO IE
08
Bcs
Eibix (dleball
belcc 240
Bise Jh1
(NN0
par
dimertion
dimendion
Figure 2: Constant temperature vs Learning the temperature In this plot we compare perfor- mances between original Gumbel box and variations of T-Box under same dimension.
Related Work
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 [19]]. cones in both Euclidean [58] and hyperbolic space [20). and boxes [53]. Region- based embeddings whose representation can be assigned volume under some finite measure can also be normalized to represent probability distribution, as has been done with cones 27 and boxes 600 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 EIC or alternative distance functions [2]] have been proposed. For box embeddings, improvements training have been introduced by smoothing the objective via convolution (10 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.
Embedded representations of graphs has also been widely studied 61 633 Embedding tree structures in hyperbolic space 18 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) undirected graphs, however this is concerned with the distortion of graph, i.e., attempting to preserve distances between nodes, whereas our work investigates the ability of graph to perform edge classification.
Representing Graphs R I1
15
2
28
32
40
3
All 57
both algorithmically
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 4
55 64]. Many novel representations have been created for this purpose, 55 vector representations. The task setting differs from work in various ways the graph can be viewed as an multi trtti--grphhh with labeled edges, and the objective is to recover missing edges- however 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.
R 13 22
26
36
52
such as complex [57
quaternion
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 K and directed graphs such as Price's Model [42].
Kronecker 2 along with others 5
g 10 16] There are also Bayesian non-parametric models for
link prediction in directed and relational graphs
19
25 46
8 Conclusion
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 embed- dings, and box embeddings. We propose new box embedding model that learns temperatures which out-performs other geometric representations low dimension and shows competitive performance with vector-based models in high dimension. We perform an empirical comparison of seven meth- ods on both synthetic datasets and real world datasets. Our work describes meaningful theoretical foundations and empirical analysis of geometric representations of directed graphs.
10

---

Acknowledgements
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. 176361 18, University of Southern California subcontract no. 123875727 under Office of Naval Research prime contract no. N66001 1924032. 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 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.
References
[1] Réka Albert and Albert-L Lászó Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 2002.
[2] Ben Athiwaratkun and Andrew Gordon Wilson. Hierarchical density order embeddings. Inter- national Conference on Learning Representations (ICLR), 2018.
[3] Albert-Lászlo Barabási and Réka Albert. Emergence of scaling in random networks. Science, 1999.
[4] Robi Bhattacharjee and Sanjoy Dasgupta. What relations are reliably embeddable in euclidean space? Conference on Algorithmic Learning Theory (ALT), 2020.
[5] Lukas Biewald. Experiment tracking with weights and biases, 2020. URL https::/wwww wandb.com/
[6] David M Blei, Thomas L Griffiths, and Michael Jordan. The nested chinese restaurant process and bayesian nonparametric inference of topic hierarchies. Journal of the ACM (JACM), 2010.
[7] Béla Bollobás, Christian Borgs, Jennifer Chayes, and Oliver Riordan. Directed scale-free graphs. Symposium Discrete Algorithms (SODA), 2003.
[8] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems (NeurIPS), 2013.
[9] Diana Cai, Trevor Campbell, and Tamara Broderick. Edge-exchangeable graphs and sparsity. Advances in Neural Information Processing Systems (NeurIPS), 2016.
[10] François Caron and Emily B Fox. Sparse graphs using exchangeable random measures. Journal of the Royal Statistical Society. Series B, Statistical Methodology, 2017.
[11] Ines Chami, Sami Dou-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy, Machine learning graphs: A model and comprehensive taxonomy. arXiv preprint 2:X5::2005.03675 2020.
[12] Ines Chami, A. Gu, Vaggos Chatziafratis, and C. Ré. From trees to continuous embeddings and back: Hyperbolic hierarchical clustering. Advances in Neural Information Processing Systems (NeurlPS), 2020.
[13] Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low-dimensional hyperbolic knowledge graph embeddings. Association for Computational Linguistics (ACI., 2020.
[14] I.. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan. Geometric representation of graphs in low dimension using axis parallel boxes. Algorithmica,, 2008.
11

---

[15] Sudhanshu Chanpuriya. Cameron Musco, Konstantinos Sotiropoulos, and Charalampos Tsourakakis. Node embeddings and exact low-rank representations of complex networks. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[16] Harry Crane and Walter Dempsey. Edge exchangeable models for interaction networks. Journal of the American Statistical Association (JASA), 2018
[17] Shib Sankar Dasgupta, Michael Boratko, Dongxu Zhang, Luke Vilnis, Xiang Lorraine Li, and Andrew McCallum. Improving local identifiability in probabilistic box embeddings. Advances in Neural Information Processing Systems (NeurIPS), 2020.
[18] Paul Erdos and Alfréd Rényi. On the evolution of random graphs. Publications of the Mathe- matical Institute of the Hungarian Academy of Sciences, 1960.
[19] Xuhui Fan, Bin Li, and Scott Sisson. Rectangular bounding process. Advances in Neural Information Processing Systems (NeurIPS), 2018
[20] Octavian Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic neural networks, Advances in neural information processing systems (NeurIPS), 2018
[21] Octavian-Fugen Ganea, Gary Bécigneul, and Thomas Hofmann. Hyperbolic entailment cones for learning hierarchical embeddings. arXiv preprint arXiv: 1804.0884.. 2018.
[22] Matt Gardner and Tom Mitchell. Efficient and expressive knowledge base completion using subgraph feature extraction. Empirical Methods in Natural Language Processing (EMNLP), 2015.
[23] Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature repre- sentations in product spaces. International Conference on Learning Representations (ICLR), 2019.
[24] Ross J Kang and Tobias Müller. Sphere and dot product representations of graphs. Discrete & Computational Geometry, 47(3):548-566 2012.
[25] Charles Kemp, J. Tenenbaum, T. Griffiths, T. Yamada, and N. Ueda. Learning systems of concepts with an infinite relational model. Association for the Advancement of Artificial Intelligence (AAA/), 2006.
[26] Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. International Conference on Machine Learning (ICML), 2018
[27] Alice Lai and Julia Hockenmaier. Learning to predict denotational probabilities for modeling entailment. EACL, 2017.
[28] Marc Law, Renjie Liao, Jake Snell, and Richard Zemel. Lorentzian distance learning for hyperbolic representations. International Conference on Machine Learning (ICML), 2019.
[29] Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahra- mani. Kronecker graphs: an approach to modeling networks. Journal of Machine Learning Research (JMLR), 2010.
[30] Xiang Li, Luke Vilnis, Dongxu Zhang, Michael Boratko, and Andrew McCallum. Smooth- ing the geometry of probabilistic box embeddings. International Conference Learning Representations (ICLR), 2019.
[31] Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 1995.
[32] Aaron Lou, Isay Katsman, Qingxuan Jiang, Serge Belongie, Ser-Nam Lim, and Christopher De Sa. Differentiating through the fréchet mean. International Conference on Machine Learning (ICML), 2020.
[33] Emile Mathieu, Charline Le Lan, Chris J. Maddison, Ryota Tomioka, and Yee Whye Teh. Continuous hierarchical representations with poincaré variational auto-encoders. Advances in Neural Information Processing Systems (NeurIPS), 2019.
12

---

[34] George A Miller. WordNet: lexical database for English. Communications of the ACM, 1995.
[35] Nicholas Monath, Manzil Zaheer, Daniel Silva, Andrew McCallum, and Amr Ahmed. Gradient- based hierarchical clustering using continuous representations of trees in hyperbolic space. Conference on Knowledge Discovery & Data Mining (KDD), 2019.
[36] Arvind Neelakantan, Benjamin Roth, and Andrew McCallum. Compositional vector space models for knowledge base completion. Association for Computational Linguistics (ACL), 2015.
[37] Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. A three-way model for collective learning on multi-relational data. International Conference Machine Learning (ICMI.), 2011.
[38] Maximilian Nickel, Kevin Murphy, Volker Tresp. and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 2015.
[39] Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical represen- tations. Advances in Neural Information Processing Systems (NeurIPS), 2017.
[40] Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. International Conference on Machine Learning (ICML), 2018.
[41] Aleksandar Poleksic. Hyperbolic matrix factorization hints at the native space of biological systems. bioRxiv, 2020.
[42] Derek de Solla Price. A general theory of bibliometric and other cumulative advantage processes. Journal of the American society for Information science, 1976.
[43] Milos Radovanovic, Alexandros Nanopoulos, and Mirjana Ivanov. Hubs in space: Popular nearest neighbors in high-dimensional data. Journal of Machine Learning Research (JMLR), 2010.
[44] Sebastian Riedel, Limin Yao, Andrew McCallum, and Benjamin M Marlin. Relation extraction with matrix factorization and universal schemas. North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL), 2013.
[45] Fred S Roberts. On the boxicity and cubicity of graph. Recent progress in combinatorics, 1969.
[46] Daniel M. Roy and Yee Whye Teh. The mondrian process. Advancements in Neural Information Processing Systems (NeurIPS), 2008
[47] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 2015.
[48] Frederic Sala, Chris De Sa, Albert Gu, and Christopher Re. Representation tradeoffs for hyperbolic embeddings. International Conference Machine Learning (ICML), 2018.
[49] Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. International Symposium Graph Drawing, pages 355-366, 2011.
[50] Dominik Schnitzer, Arthur Flexer, Markus Schedl, and Gerhard Widmer. Local and global scaling reduce hubs in space. J. Mach. Learn. Res., (3(1):2871-290) October 2012.
[51] Ondrej Skopek, Octavian-Euge Eugen Ganea, and Gary Bécigneul. Mixed-curvature variational autoencoders. ICLR, 2020.
[52] Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Ng. Reasoning with neural tensor networks for knowledge base completion. Advances neural information processing systems (NeurIPS), 2013.
13

---

[53] Sandeep Subramanian and Soumen Chakrabarti. New embedded representations and evaluation protocols for inferring transitive relations. Special Interest Group on Information Retrieval (SIGIR), 2018.
[54] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embed- ding by relational rotation in complex space. International Conference on Learning Representa- tions (ICLR), 2019.
[55] Ryota Suzuki, Ryusuke Takahama, and Shun Onoda. Hyperbolic disk embeddings for directed acyclic graphs. International Conference on Machine Learning (ICML), 2019.
[56] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. Conference on computer vision and pattern recognition (CVPR), 2016.
[57] Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. International Conference on Machine Learning (ICML), 2016.
[58] Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. Order-embeddinns of images and language. International Conference on Learning Representations (ICLR), 2016.
[59] Luke Vilnis and Andrew McCallum. Word representations via gaussian embedding. Interna- tional Conference on Learning Representations (ICLR), 2015.
[60] Luke Vilnis, Xiang Li, Shikhar Murty, and Andrew McCallum. Probabilistic embedding of knowledge graphs with box lattice measures. Association for Computational Linguistics (ACL), 2018.
[61] Melanie Weber. Neighborhood growth determines geometric priors for relational representation learning. Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[62] Melanie Weber and Maximilian Nickel. Curvature and representation learning: Identifying embedding spaces for relational data. NeurlPS Relational Representation Learning, 2018.
[63] Canran Xu and Ming Wu. Learning feature interactions with lorentzian factorization machine. Association for the Advancement of Artificial Intelligence (AAAI), 2020.
[64] Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. International Conference Learning Representations (ICLR), 2015.
[65] Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embeddings. Advances in Neural Information Processing Systems (NeurIPS), 2019.
14


Reviews:
[{"review_id": "r83kG34Yk9R", "reviewer": "Reviewer_6Ekw", "summary": "# A solid work on Geometric Embeddings\n\nThis 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. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "This paper discusses the properties of recent geometric embeddings for representing graphs and extends a new continuous relaxation of the probabilistic box embeddings. I think this is a solid work what worth a clear acceptance. Yet I do want to point out certain issues and suggest further improvements: \n* Discussions on hyperbolic embeddings are just scratching the surface. Theoretical results are centered on box embeddings. I would suggest the authors to either give a more detailed discussion on hyperbolic embeddings, or shorten them. \n* The mechanism why axis-wise temperature gives better performance in high-dimensional scenarios is not discussed at all, which would be important to understand the source of performance gain (although all models are tuned with Bayesian hyperparameter search).\n* Given this paper is more about box embeddings, I would suggest to shorten discussions on complex and hyperbolic vectors (put them in the appendix) and make room for the experiments. In the experiments, more studies about why axis-wise temperature improves performance in high-dimensional scenarios should be conducted (Possibly to show more stable optimization / numerics, as these are the major challenges for the hyperbolic case). \n\nOther Minor Points:\n\n- For important theoretical results, their proofs should be sketched briefly (e.g.,  Thm 2)\n- I would encourage using simple language to explain what the theorem says intuitively. For example, for proposition 3, the authors may say box embeddings can represent graphs with exponentially large number of nodes (because of the log V term), but the connections should not be too dense (because of the linear $\\Delta$ term)\n- The math behind why POE always yield a DAG but OE does not should be briefly explained, my understanding is that the composition of $max(\\cdot)$ and L1 norm allows separation of variables while L2 norm does not\n- Important concepts in the theorems should be explained briefly (e.g., what does bits per box mean?)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The underlying mechanism why axis-wise temperature helps in the high-dimensional case is not studied. I would recommend the authors to at least give an intuitive explanation.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "W1pj24nApeI", "reviewer": "Reviewer_E4N8", "summary": "This paper analyses models for node embeddings of directed acyclic graphs (DAGs). It has 3 contributions: \n\ni) 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.\n\nii) 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.\n\niii) 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "======= Update after rebuttal ====\n\nI am increasing my score to 7. See discussion.\n\n=============================\n\n\nFirst, I will touch the main required parts of this section, but my detailed comments will be given afterwards.\n\n1) Originality:  I largely discussed this in the previous section. The t-BOX method is a straightforward extension of P-BOX. In its own is an incremental contribution, but given the other contributions of the paper, it is fair. Related work is missing important citations which would also be needed in the evaluation section (see below). \n\n2) Quality: largely discussed in the previous section.\n\n3) Clarity: paper is well written, with nice and detailed descriptions of methods, theory, experimental setups, etc.\n\n4) Significance: largely discussed in the previous section, but there are important points that I will add below.\n\n\nImportant drawbacks of this work:\n\n- empirical results (figure 1) do not show a clear advantage of the t-BOX models over previous BOX or other models. In the best case, it is comparable, but not clearly better. Fig 2 is showing more clear gains, but that is of course at the cost of doubling the number of parameters.\n\n- important prior work is missing both to be cited and to be compared empirically against: for example, it is mentioned that hyperbolic models struggle with transitivity and use an heuristic choice of the scoring function (eq 6). These issues were addressed by the work of hyperbolic entailment cones ([1,2,3]) which also address capacity difficulties of order embeddings.\n\n- looking at representational capacity (i.e. overfitting ability) is one facet of the problem, but for the community it is arguably equally or more important to understand the generalization capability of these models. Evaluating tasks like link-prediction was done in most of the prior work on DAG embeddings, and the lack of it in this paper is a weakness. This is especially important since the proposed t-BOX model does not seem to show clear cases where it clearly outperforms the BOX or the other models.\n\n- Many of the real datasets are relatively small (what are the stastistics of KNN and Imagenet-hac datasets?) and by \"small\" I mean that many of the models are already almost perfect with 32 parameters. As a consequence, it is quite hard to see how good these models really are in high dimensions as it is claimed in the abstract of the paper. Why not use larger datasets where the effect could be more visible, such as the full WordNet?\n\nAll in all, I would be happy to increase my score if: i) the authors would include at least one generalization experiment on a real dataset, ii) the authors would compare against hyperbolic entailment cones. Also, I would be glad to see at least one large real dataset where all the baseline models (excl. t-BOX but inc. P-BOX) are far from perfect in the 32 parameters case.\n\n\n[1] Hyperbolic Entailment Cones for Learning Hierarchical Embeddings, Ganea et al, 20`18\n\n[2] Inferring Concept Hierarchies from Text Corpora via Hyperbolic Embeddings, Le et al 2019\n\n[3] Hierarchical Image Classification using Entailment Cone Embeddings, Dhall et al, 2020\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes, they did", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Ep_Crl9gtmM", "reviewer": "Reviewer_YYhw", "summary": "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.\n\nDirected graphs have received considerably less attention in the representation learning community than undirected graphs, making this paper particularly appealing. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "(1) Extensive and meaningful experiments with new observations can inform the design of future algorithms. Insightful empirical analyses are a strong plus of the proposed work. Include error bars in Figure 2. \n\n(2) Description of the novel box embedding method in section 3 lacks some information. Please describe the complete algorithm using the algorithmic environment. What are the critical hyperparameters of the approach? How does the new approach scale with graph size? I couldn't find this information in the Appendix.\n\n(3) The authors treat the prediction of a directed edge from node i to j as a binary classification problem (in section 5). How are reverse edges predicted? Are those treated independently? The appropriate edge scoring function depends on the type of geometric model (e.g., Nickel and Kiela's [35] scoring function was designed for hyperbolic vectors). Would you mind clarifying and providing details for each method included in the benchmarking study? \n\n(4) The authors carry out a suite of experiments on synthetic and real-world graphs, comparing various vector, hyperbolic, cone, and box representations over a range of dimensions. That is great, but it also means that some aspects of the new model are not thoroughly evaluated (i.e., see point 2). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the work are described. This work does not seem to introduce any new potential for negative societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "None. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "9o_bIr7Dhxl", "reviewer": "Reviewer_TVmD", "summary": "The authors study geometric embeddings for directed graphs and propose a continuous relaxation of probabilistic box embeddings. They also analyze geometric embedding methods for modeling directed graphs by theoretical analysis and experiments.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Update After Rebuttal\n---\nI have carefully read the authors' responses. The explanation of why the trainable temperatures can help box embeddings avoid performance saturation in higher dimensions is reasonable. However, I still feel that there is a gap between the theoretical analysis and empirical implementations. In the further response, the authors provide a graph depicting the value of temperatures across all boxes as they are observed during training. It seems to me that many of the temperatures are far from zero, which violates the assumption in Theorem 2. In all, I recommend a weak accept for this paper.\n\n---\nOriginality\n---\nThe proposed box embedding model is a simple extension of that in [1], while the model in this paper allows learnable temperature parameters in the approximation of max operators. However, learning adaptive temperature parameters is not a new idea and it has been used in other scenarios, e.g., the computation of attention [2]. The authors may want to cite these papers and discuss the relationship between them and this work.\n\n[1] Shib Sankar Dasgupta, Michael Boratko, Dongxu Zhang, Luke Vilnis, Xiang Lorraine Li, and Andrew McCallum. Improving local identiﬁability in probabilistic box embeddings. NeurIPS, 2020.\n\n[2] Junyang Lin, Xu Sun, Xuancheng Ren, Muyu Li, and Qi Su. Learning When to Concentrate or Divert Attention: Self-Adaptive Attention Temperature for Neural Machine Translation. EMNLP 2018.\n\n\nQuality\n---\nMy major concerns about this paper are as follows.\n1. Why the proposed model can outperform existing box embedding models is unclear. The authors claim that their method avoids performance saturation common to other geometric models in high dimensions, but why?\n2. The authors claim that the learned temperatures capture uncertainty related to min and max coordinates for the box representing nodes. However, they did not clearly describe the exact meaning of uncertainty. Moreover, the authors may want to provide theoretical or experimental analysis to support the aforementioned claim.\n2. It seems that the theoretical analysis in Section 4 has no strong connection with the proposed model. Does the analysis provide any guidance in model designing, or provide theoretical explanations for the effectiveness of the model?\n\nClarity\n---\nOverall, this paper is well-written. However, some important details are missing, which may confuse the readers.\n1. What do capacity and bias mean? Though these two items appear frequently in the title, abstract, and introduction, the authors did not provide formal definitions for them.\n2. The authors may want to include all the related work in the main text instead of the appendix.\n3. I suggest the authors detail the objectives in Section 5, since it is critical for reproducing the results.\n\nSignificance\n---\nThis work outperforms the state-of-the-art geometric embedding models in some experimental settings. The authors perform standard theoretical and empirical analyses. \n\nOther Comments\n---\n1. Box embeddings are also applicable in tasks involved with multi-relational graphs, e.g., knowledge base completion [3], which is also mentioned in the abstract of this paper. The authors should discuss these works and conduct experiments on multi-relational data, if possible.\n\n[3] Ralph Abboud, İsmail İlkan Ceylan, Thomas Lukasiewicz, Tommaso Salvatori. BoxE: A Box Embedding Model for Knowledge Base Completion. NeurIPS 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The authors addressed the limitations and potential negative societal impact of their work in the checklist.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has reached a consensus in that the authors are offering several useful items to the study of embeddings, including a new method that balances between the flavors of two popular classes of existing embedding methods. This is a relatively practical area with many different proposed methods, so the authors approach—to bridge known gaps and provide useful theoretical and empirical insights—is welcome. The reviewers have very little variance between them; post clarifications by authors almost all the scores are identical. I also largely agree with the paper’s strengths. I’m positive about the contributions offered here.

Perhaps the main argument against acceptance, as also noted by several reviewers, is that the paper is a bit of a grab-bag in a sense, in that there’s some theoretical analysis of existing methods, the introduction of a new method, along with a large empirical study (not necessarily focused on just evaluating the proposed method). This is not a major problem, since all of these parts are useful, provide interesting insights that are likely to be helpful to practitioners, and the authors’ writing quality in weaving together these concepts is pretty good. The additional discussion period helped clarify a number of things here as well. 

I think the authors made a wise choice to study the basics and paint a fairly complete picture (e.g., the focus on representation quality rather than generalization, attempting to control all the factors involved in quality in the empirical results). This is a more well-grounded and scientific approach than is typically found in papers in this area.
Decision: Accept (Poster)