Representing Joint Hierarchies with Box Embeddings
Year: 2020

Abstract:
Learning representations for hierarchical and multi-relational knowledge has emerged as an active area of research. Box Embeddings [Vilnis et al., 2018, Li et al., 2019] represent concepts with hyperrectangles in n-dimensional space and are shown to be capable of modeling tree-like structures efficiently by training on a large subset of the transitive closure of the WordNet hypernym graph. In this work, we evaluate the capability of box embeddings to learn the transitive closure of a tree-like hierarchical relation graph with far fewer edges from the transitive closure. Box embeddings are not restricted to tree-like structures, however, and we demonstrate this by modeling the WordNet meronym graph, where nodes may have multiple parents. We further propose a method for modeling multiple relations jointly in a single embedding space using box embeddings. In all cases, our proposed method outperforms or is at par with all other embedding methods.

heading: 1. Introduction
text: Hierarchical relations, particularly hypernymy, are inherently present in natural language and useful in many common tasks. For example, in SNLI the sentence “A soccer game with multiple males playing” can be understood to entail “Some men are playing a sport” via the hypernym relation between “soccer” and “sport”. Question answering and language modeling, in general, can benefit from understanding these relationships, as a word can often be replaced by its hypernym and still yield a valid sentence or provide supporting evidence to answer a question. Vector embedding methods, where an entity is associated with a vector in Rn, often use symmetric measures such as the dot product between these representations which cannot capture inherently asymmetric relations such as hypernymy.
In order to solve this problem, [Vendrov et al., 2016] introduced an asymmetric measure on vectors in the form of entailment cones in Rn+. [Vilnis et al., 2018, Li et al., 2019] generalized this notion to propose box embeddings which are hyperrectangles in Rn. We build upon this work by proposing a new regularization loss for the box embedding model. This provides a weak scale on the embedding space resulting a significant performance improvement.
In this work, we explore the extent to which the edges from the transitive closure are necessary to model the tree-like large tree-like graphs, e.g, WordNet’s hypernymy. We
∗. Equal Contribution
further explore the meronymy relation from WordNet, which differs qualitatively from the hypernymy graph in that it is not as tree-like, comprised of many connected components where some nodes have multiple parents while others have no parents. We not only achieve state-of-the-art performance with our box embedding based method over other baselines when 10, 25, and 50% of the transitive closure edges are supplied during training but, most importantly, we outperform other methods by a significant margin when the training is being restricted to the transitive reduction only (0% transitive closure edges).
Finally, we introduce a method of modeling these two relations in the same space by introducing two representations for each entity. Our method is not specific to box embeddings, but rather can be thought of as a graph augmentation procedure which is general enough to allow for modeling with all existing baselines. In this multi-relational embedding settings, we also compare against knowledge base completion baselines and demonstrate that box embeddings can outperform TransE [Bordes et al., 2013] and ComplEx [Trouillon et al., 2016] in this setting as well∗.

heading: 2. Related Work
text: Using distributed representations to capture semantic relationships amongst words/concepts has had a long history [Mikolov et al., 2013, Pennington et al., 2014]. However, due to the use of a symmetric distance metric, these models are incapable of representing the asymmetric relations like hypernymy. Recent works that address this issue can be broadly categorized into two approaches: (1) using point representations combined with an asymmetric distance measure, and (2) using region-based representations with a probabilistic interpretation.
While Nickel and Kiela [2017], Chamberlain et al. [2017] use points in n-dimensional hyperbolic space (Poincaré ball) to model tree-structured data, Vendrov et al. [2016] uses the asymmetric measure of the reverse product order on points in Euclidean space to perform the same task. Using the reverse product order amounts to associating with each entity a Euclidean cone with apex x, which is the set {y : ∧n i=1 yi ≥ xi}. Ganea et al. [2018] extend the hyperbolic point embeddings to entailment cones in hyperbolic space.
Another line of work uses distributions over points in space to learn representations for hierarchical data[Vilnis and McCallum, 2015, Muzellec and Cuturi, 2018]. Lai and Hockenmaier [2017] provide a probabilistic interpretation of order embeddings [Vendrov et al., 2016] by using the negative exponential measure or, equivalently, representing concepts as a cone in [0, 1]n. With this parameterization, the volume of a cone could be interpreted as the marginal (resp. joint) probability of the entity (resp. intersection) which it represents. This allowed for training and evaluation using conditional probabilities which mapped very naturally onto hypernym relations, eg. P (mammal|dog) = 1. However, representing entities probabilistic cones has a serious deficit – it cannot represent negative correlation, that the case when P (X|Y ) ≥ P (X). Box embeddings, introduced in Vilnis et al. [2018], solves this issue by introducing another vector, effectively associating each entity with an n-dimensional hyper-rectangle. Their method has been shown to effectively model hypernymy by training on a large subset of the transitive closure of the WordNet hypernym graph. In this work, we propose a regularization loss to further improve the performance of box embeddings.
∗. Source code and datasets used in the paper are available at https://github.com/iesl/Boxes_for_ Joint_hierarchy_AKBC_2020
We also present a modelling technique that extends the previously discussed methods to jointly model multiple hierarchical relations.

heading: 3. Method
text: We first present box embeddings as they were introduced in [Vilnis et al., 2018], briefly touch on the “soft” volume calculation presented in [Li et al., 2019], and then discuss some learning adaptations present in our version of the model.

heading: 3.1 Representation
text: The box-space [Vilnis et al., 2018] is the set of all n-dimensional hyperrectangles. Formally, if B = {[a, b] | a, b ∈ R, b ≥ a} is the set of all closed intervals of R, then an n-dimensional box-space is Bn. Just as in vector embedding models where each entity is represented by a vector in the euclidean space, in box-space each entity e is represented by a box αe ∈ Bn as shown in Figure 1. We parametrize a box using the minimum and maximum coordinates in each dimension, (αm, αM ), where αm, αM ∈ Rn and αm,i ≤ αM,i for each i ∈ {1, . . . , n}. Box embeddings provide a natural way to embed a partial order using containment.

heading: 3.2 Probabilistic Interpretation
text: In addition to the natural containment operation, we can consider the volume of boxes. If we normalize the space to have volume 1 (by dividing by the smallest containing box, say) the boxes can be interpreted as a parameterization of a joint probability distribution over binary random variables, where the marginal probability of a given entity is given by the volume of its box. Intersections of boxes yield either another box or the empty set, and in either case, we can compute the volume of the intersection as
Vol(α ∩ β) := ∏ max(min(αM,i, βM,i)−max(αm,i, βm,i), 0). (1)
We can interpret this volume as the joint probability for concepts α and β, and furthermore calculate (for example) †
Pr(α|β) = Vol(α ∩ β) Vol(β) . (2)
Vilnis et al. [2018] uses these conditional probabilities to model the hypernym graph of WordNet. For example, given an edge from Man to Person (indicating that a man is a person) we first convert this to a conditional probability between binary random variables, Pr(Person|Man) = 1, which is then trained using binary cross-entropy loss and stochastic gradient descent. Figure 2 shows the corresponding boxes capturing this edge.

heading: 3.3 Softplus Volume
text: Box embeddings that should overlap may become disjoint, either due to initialization or during training, and the currently described model has no training signal in this instance. Vilnis et al. [2018] made use of a surrogate loss function to handle this case, however Li et al. [2019] introduced a new method which replaces the ReLU from (1) with the softplus function, softplust(x) = t log(1 + e
x/t), which smoothed the loss landscape and resulted in easier training. The volume calculation under this approximation becomes
Vol(α ∩ β) := ∏
softplust(min(αM,i, βM,i)−max(αm,i, βm,i)). (3)
We note that (3) is always positive, which means all boxes “intersect” one another under this volume calculation. The temperature parameter t can be tuned, and as t→ 0 we recover the original box model. We will exclusively use this soft volume calculation when computing box volumes, and in our experiments, we always select the temperature based on dev set performance.

heading: 3.4 Absence of explicit probability labels and use of regularization
text: Previous work on box embeddings [Vilnis et al., 2018] uses pre-computed unary marginals Pr(A) and pairwise conditionals Pr(A | B) as labels while training the box embedding
†. Note that when calculating conditional probabilities it is not necessary to normalize the volume of the space to size 1.
model. These marginal probabilities were calculated using the graph structure - leaves were given marginal probability equal to 1/#nodes, and parents were assigned marginal probability equal to the sum of their children plus 1/#nodes. How “tight” the parent boxes are to their children can be seen as a form of regularization. In general, setting marginal probabilities can help to set a scale for the overall model.
For our model, however, we avoid pre-computing marginal probabilities and simply use the conditional probability targets with binary cross-entropy loss and augment it with an additional regularization loss which can be written as
L = N∑ i −yi log pi − (1− yi) log(1− pi) + Ne∑ j I[Vol(α(j))>τ ] Vol(α (j)) , (4)
N being the total number of examples (including the random negatives), Ne the total number of entities, yi the label, pi the conditional probability calculated using equation 2, and I the indicator function.
Without any global scale i.e., the marginal probabilities, we get poor training results, so we introduce this regularization measure by penalizing the size of boxes when they become greater than a fixed volume. This provides a weak scale to the boxes in the embedding space and results in significant performance improvement over unregularized training without the need to precompute unary marginals.

heading: 3.5 Modeling joint hierarchy
text: Inter-relational semantics implicit in multi-relational knowledge graphs can be used to learn coherent representations for the entities present in the graph. In particular, the relations
discussed in this work, i.e., the IsA and HasPart relations should obey the following rules.
IsA(a, b) ∧HasPart(b, c)⇒ HasPart(a, c) (5) IsA(a, b) ∧HasPart(c, a)⇒ HasPart(c, b) (6)
For instance, every Man IsA Person and every Person HasPart Eye. Hence, every Man HasPart Eye. Similarly, Eye IsA Organ and Person HasPart Eye implies Person HasPart Organ. Figure 4 shows the subgraph describing this example. The red edges and the dotted red edges are implied HasPart edges which might be missing in the original knowledge graph. We show that boxes can model these two relations in a single space by using two boxes per node while preserving the semantics described above.
For each node x we embed two boxes, one which represents “Things which are x” and one which represents “Things which have x as a part”. This is depicted in Figure 3, where the entity “Man” is represented by the green Man box and the red HasPart-Man box. The edges 3,4,5 and 7, in Figure 4 are captured by the inclusion of Man and Person boxes inside the HasPart-Eye and HasPart-Organ boxes, while the edges 1 and 2 are captured by the inclusion of Man inside the Person Box, and Eye inside the Organ box, respectively.
This form of modeling multiple relations using augmentation is not limited to the box embedding model. The main idea is to create a new graph with twice as many nodes and edges from the IsA hierarchy, with additional PartOf edges so as to make the semantics coherent. Any model capable of modeling a DAG can be evaluated on its ability to model this graph.

heading: 4. Experiments
text: In order to demonstrate the efficacy of the box embeddings model on hierarchical structured data, we evaluate on the hypernymy and meronymy relations of WordNet. Following the recent works of [Nickel and Kiela, 2017, Ganea et al., 2018], we train on the transitive reduction, using increasing amounts of edges from the transitive closure of those lexical relations. We pose the problem as a binary classification task on the unseen test edges which include the remaining edges from the transitive closure along with a fixed set of random negatives for the respective relations.
4.1 Datasets
1. Hypernymy (IsA) For hypernymy, we used the dataset from [Ganea et al., 2018]. The WordNet noun hypernymy dataset contains 82,114 nodes (omitting the root). The transitive reduction of the hypernymy hierarchy is used for training. Additionally, there are training datasets with 10%, 25%, and 50% of the transitive closure edges. For dev and test datasets, 10% of the edges (5% each) are sampled from the rest of the transitive closure. For each test and validation edge, a fixed set of negative samples of size 10 was generated.
Transitive Closure Transitive Reduction Validation (pos/neg)
Test (pos/neg)
Hypernym 84363 661127 28838/288380 28838/288380 Meronym 9678 30333 5164/51640 5164/51640

heading: 4.2 Baselines
text: We compared our model with the recent strong baseline models such as:
1. Order Embeddings [Vendrov et al., 2016]: As mentioned in the introduction, this method embeds entities as cones in R+d. Representationally, order embeddings are equivalent to box embeddings where the min coordinate is fixed to the origin, however, learning differs in that the objective function optimizes an order-violation penalty. (See [Vendrov et al., 2016] for more details.)
2. Poincaré Embeddings [Nickel and Kiela, 2017]: In this work, the authors learn embeddings in an n-dimensional Poincaré ball which naturally captures the tree-like structure via the constant negative curvature of hyperbolic geometry. This work uses
a symmetric distance function which is not ideal for asymmetric relational data, however. We use the same heuristics followed by [Ganea et al., 2018] to mitigate this problem.
3. Hyperbolic Entailment Cones [Ganea et al., 2018]: This work models hierarchical relations as partial orders defined using a family of nested geodesically convex cones in hyperbolic space.
4. TransE and ComplEx [Bordes et al., 2013, Trouillon et al., 2016]: The joint hierarchy can be also considered as multi-relational data with two relations. We use the most popular translational distance-based and matrix factorization based models, TransE and ComplEx respectively.
In order to show the effectiveness of the proposed regularisation, we include the performance of the vanilla box embeddings [Li et al., 2019] as well.

heading: 4.3 Training details
text: In all our experiments, we keep the embedding dimension as 10 for all the baseline models, while for our model we use embedding dimension as 5. This results in having 10 parameters per node and ensures a fair comparison. For the task of learning the joint hierarchy with multi-relation prediction models like TransE and ComplEx, we keep their embedding dimension as 20 to account for the doubling of parameters due to the introduction of two embeddings per node in Order embeddings, Poincaré embeddings, Hyperbolic entailment cones, and our model. The effect of increasing the embedding dimensions is reported in Appendix B‡.
We use the validation set to find the best threshold for the classification and obtain the F1 score on the test set using this threshold. Our best performing models have softbox temperature of between 0.2 and 0.5. We obtain the best learning rate for every model using random search and performance on the validation set§.

heading: 5. Results
text: The F1 scores for the hypernymy and meronymy predictions are presented in Table 2. We note that our box embedding method outperforms all baselines by a large margin in the single hierarchy settings. Particularly, in the transitive reduction (0%) setting for hypernymy, we achieve 40% relative improvement compared to the most competitive baseline (order embeddings). This demonstrates the capability of box embeddings to reconstruct the whole transitive closure graph given only the transitive reduction. We observe a similar trend when modeling meronymy. When transitive closure edges are added to the training data (10%, 25%, 50%), the gap between our method and the baselines closes, however, the former still remains superior.
In Table 3, we report the F1 scores for the test edges of the joint hierarchy, which are the composite edges created by the rules (7) mentioned in Section 4.1. We outper-
‡. The appendix is available at https://github.com/iesl/Boxes_for_Joint_hierarchy_AKBC_2020/ blob/master/supplementary_material/appendix.pdf §. We use Weights & Biases package to manage our experiments [Biewald, 2020].
form the multi-relation knowledge base embedding methods as well as hyperbolic models (Poincaré and hyperbolic entailment cones). While methods like TransE and ComplEx lack the inductive bias required to model such highly connected relations, the hyperbolic space methods struggle due to their inability to train very well. Order embeddings, on the other hand, slightly outperform our model, but the latter is essentially at par while also achieving superior performance on the task of modeling single hierarchy. The high performance of order embeddings on this task can be attributed to the “local” nature of the evaluation (we traverse only 2 steps up and down the hypernym graph by keeping m,n ∈ {1, 2} in eq. 7) which might not be exposing the representation limitations of order embeddings – something that is exposed while modeling the relations individually.

heading: 5.1 Qualitative analysis
text: In order to visualize the effect of using “soft” boxes, we train a 2-dimensional box embedding model on the hypernym relation of WordNet. Due to the softening of the boxes, the model does not require the dog.n.01 box to be completely contained inside the domestic animal.n.01 box to produce a high score for the edge between them. Figure 5 shows the visualization obtained by plotting the hard edges using the minimum and maximum coordinates of the softboxes. For the Joint Hierarchy model, we obtain similar visualizations which are given in Appendix A‡ .
In order to model a hierarchy, the embedding model has to accommodate the exponential growth in the number of nodes while moving down the hierarchy. The loss function for the box embedding model encourages the embedding of the head node to contain the embedding of the tail node. Hence the number of embeddings having low volume should be high. This intuition is confirmed by Figure 6.

heading: 6. Conclusion
text: In this paper we have explored the capability of box embeddings to model hierarchical data. We demonstrated that it provides superior performance compared to alternative methods and requires less of the transitive closure. We also demonstrated that boxes are capable of learning data which is less tree-like, and introduced a method of embedding a joint hierarchy in a single space by augmenting the graph. There are several promising directions which can be explored in future work. It would be of interest to expand the number of relations
which are modeled in a single box space and to extend the method to model non-transitive relations. Also, the knowledge encoded in these embeddings can be exploited by using them as a representation layer in neural network models for various downstream tasks like question answering, natural language inference, etc.

heading: Acknowledgement
text: This material is based upon work supported in part by the the Chan Zuckerberg Initiative under the project “Scientific Knowledge Base Construction”, and in part by the National Science Foundation under Grant No. IIS-1514053. 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. The work reported here was performed in part by the Center for Data Science and the Center for Intelligent Information Retrieval, and in part using high performance computing equipment obtained under a grant from the Collaborative R&D Fund managed by the Massachusetts Technology Collaborative.

Review summaries:
This paper studies the properties of box embedding from three aspects: 1) how many edges from the transitive closure are necessary for training the box embeddings; 2) can box embeddings be applied to graphs that are not tree-like; 3) how to model different relations in the same space. The author set up experiments using the IsA relation (Hypernymy) and HasPART relation (Meronymy)  in WordNet. The results show the effectiveness of box embedding, outperforming other embedding method including order embedding, Poincar´e embedding, hyperbolic entailment cones, TransE and ComplEx.