Self-Supervised Hyperboloid Representations from Logical Queries over Knowledge Graphs

Introduction

Knowledge Graphs (KGs) organize information as a set of entities connected by relations. Positive first-order existential (PFOE) queries such as translation, intersection, and union over these entities aid in effective information extraction from massive data (see Figure 1 for an example PFOE query). Efficient handling of such queries on KGs is of vital importance in a range of real-world application domains including search engines, dialogue systems, and recommendation models. However, the large size of KGs and high degrees of the nodes therein makes traversal for querying a computationally challenging or, in some cases, even an impossible task (Wang et al., 2017). One way to resolve this issue is to learn representations for the KG units (entities and relations) in a latent (generally Euclidean) space such that algebraic or logical operations can be applied to extract relevant entities. Robust representation learning of KG units has several real-world applications including KG information extraction (Hamilton et al., 2018), entity classification (Wilcke et al., 2020), and anomaly detection (Jia et al., 2018).

Earlier approaches to representation learning in KGs model entities and relations as vectors in the Euclidean space (Bordes et al., 2013; Nickel et al., 2016; Yang et al., 2015). This is suboptimal due to the constant size of a point’s answer space which does not capture the variations induced by different queries. Specifically, broad queries (Nike) should intuitively cover a larger region of the answer space compared to specific queries (Nike running shoes for men). In the recently proposed Query2Box model (Ren* et al., 2020), the authors demonstrated the effectiveness of complex geometries (such as hyper-rectangles) with varying offsets that control the size of an answer space according to a query’s complexity. However, such architectures lack the ability to capture hierarchical information that is prevalent in many KGs. Furthermore, previous representation learning methods in heterogeneous graphs (or KGs) (Lin et al., 2018; Zhang et al., 2020; Liu et al., 2020; Fu et al., 2020) solely focus on one-hop or multi-hop reasoning over relations. Such frameworks enable static and optimized computational graphs, but lead to poor retrieval from complex intersection and union queries. Dynamic computational graphs, which are able to modify their network architecture with a switch mechanism (discussed in Section 3.5) can significantly alleviate this problem.

Although Euclidean spaces have proven to be effective for representation learning in various domains (Bengio et al., 2013), several hierarchical datasets (including graph data) in the fields of network sciences and E-commerce taxonomies demonstrate a latent non-Euclidean anatomy (Bronstein et al., 2017). The introduction of hyperbolic algebraic operations (Ganea et al., 2018) have led to the proliferation of hyperbolic neural networks such as Hyperbolic-GCN (H-GCN) (Chami et al., 2019) and Hyperbolic Attention (HAT) networks (Gulcehre et al., 2019). These frameworks leverage the hyperbolic anatomy of hierarchical datasets and show a significant performance boost compared to their Euclidean counterparts. To the best of our knowledge, there is no existing work that (i) utilizes dynamic computational graphs on the hyperbolic space, (ii) applies complex hyperbolic geometries such as hyperboloids for representation learning. Additionally, the static computational graphs of H-GCN and HAT limit their learning capability to a single problem, generally, multi-hop (translation) reasoning. This severely limits their applicability to representation learning on KGs since translations can only utilize single entities. More complex intersections and unions not only use more entities, but are also more representative of real-world KG queries. While solving union and intersection queries is more challenging, they enable better representation learning (Bengio et al., 2012). Traversing over the entities in KGs facilitates an intuitive way of constructing a query-reasoning proxy task (refer Section 4.3) that enables representation learning of entities and relations. These representations, in a self-supervised framework, can further provide enriched features in downstream tasks with smaller annotated datasets (such as anomaly detection), thus alleviating the issue of data scarcity.

[Hyperbolic vectors and Hyperboloids]Visualization of hyperbolic vectors and hyperboloids in Poincaré ball space.

Motivated by the effectiveness of self-supervised learning and the need for non-Euclidean geometries in KGs, we formulate KG representation learning as a self-supervised query reasoning problem. We introduce Hyperboloid Embeddings (HypE), a self-supervised dynamic representation learning framework that utilizes PFOE queries to learn hyperboloid representations of KG units in a (non-Euclidean) Poincaré hyperball. Hyperboloids, unlike vectors in hyperbolic spaces, allow us to use dynamic sizes for KG representations. For e.g., in Figure 2(b), we can notice that different entities contain different number of children, and, thus learning a static vector representation is suboptimal. Hyperboloids learn an additional spatial parameter, limit (described in Section 3.4), that can model the varying entity sizes. Moreover, the dynamic nature of its computational graphs allows HypE to utilize different network layers to learn different types of operations, namely, translation, intersection, and union; and process varying number of input units depending on the learning operation. Our empirical studies include learning representations from large-scale KGs in e-commerce, web pages (DBPedia), and other widely used Knowledge bases (such as Freebase and NELL995); and evaluating the representations on the downstream task of anomaly detection. The major contributions of this paper are:

Formulate the KG representation learning problem as a self-supervised query reasoning problem to leverage PFOE queries.

Introduce Hyperboloid Embeddings (HypE), a self-supervised dynamic representation learning framework that learns hyperboloid representations of KG units in a Poincaré hyperball. This is motivated by the need for non-Euclidean geometries.

Perform an extensive set of empirical studies across diverse set of real-world datasets to evaluate the performance of HypE against several state-of-the-art baseline methods on the downstream task of Anomaly Detection.

Visualize the HypE embeddings to clearly interpret and comprehend the representation space.

The rest of the paper is organized as follows: Section 2 describes the related background. Section 3 formulates the representation learning problem, explains the non-Euclidean algebraic operations, and the proposed HypE model. In Section 4, we describe the real-world datasets, state-of-the-art baselines and performance metrics used to evaluate the HypE model. We demonstrate the performance results along with the visualization of HypE’s representations. Finally, Section 5 concludes the paper.

Related Work

In this section, we review different geometries utilized for learning representations and earlier works that are adopted for reasoning over Knowledge Graphs.

Previous approaches to representation learning, in the context of KG, aim to learn latent representations for entities and relations. Translational frameworks (Bordes et al., 2013; Nickel et al., 2011; Yang et al., 2015) model relations using translation between entity pairs. This limits the models to only handle translation-based queries. Graph Query Embedding (GQE) (Hamilton et al., 2018) overcame this limitation and provided a technique for leveraging intersection queries as deep sets (Zaheer et al., 2017) over different queries. Furthermore, Box Lattices (Vilnis et al., 2018), EMQL (Sun et al., 2020) and Query2Box (Ren* et al., 2020) proved the effectiveness of more complex geometries (hyper-rectangles) for queries. Word2Gauss (Vilnis and McCallum, 2015) is a popular NLP technique that learns Gaussian embeddings for words. DNGE (ulong Pei and Pechenizkiy, 2019) utilizes a dynamic network to learn Gaussian embeddings for entities in a graph. These Gaussian representations cannot be intuitively extended to KGs because they are not closed under more complex PFOE queries (intersection or union of Gaussians does not yield a Gaussian). Furthermore, they rely on properties of the Euclidean space to learn representations, which are proven ineffective at capturing the prevalent hierarchical features of a KG (Ganea et al., 2018).

One of the fundamental problems in KG is to aggregate the neighbor information of nodes while learning representations. Node embedding techniques such as Node2Vec (Grover and Leskovec, 2016) and DeepWalk (Perozzi et al., 2014) aggregate the neighbors’ features by modeling the node’s dependence on its neighbors. ChebNet (Defferrard et al., 2016) uses Chebyshev ploynomials and filters node features in the graph Fourier domain. GCN (Kipf and Welling, 2017) constrains the parameters of ChebNet to alleviate overfitting and shows improved performance. Graph-BERT (Zhang et al., 2020) and MAGNN (Fu et al., 2020) provide a self-supervised learning model utilizing the tasks of masking and metapath aggregation, respectively. In another line of research, Miller et al. (Miller et al., 2009) utilizes non-parametric Bayesian frameworks for link prediction on social networks. Zhu (Zhu, 2012) further improved the approach with a max-margin framework. KGAT (Wang et al., 2019a) is another popular approach that utilizes attention networks over entities and relations with a TransR (Lin et al., 2017) loss function to learn representations for user recommendation. These methods rely on relational properties and thus are effective in handling translational problems such as multi-hop reasoning. However, they are ineffective at handling more complex PFOE queries such as intersection and union.

Other popular multi-hop graph networks such as Graph Attention Network (GAT) (Veličković et al., 2018) and Graph Recurrent Network (GRN) (Song et al., 2018) have previously shown impressive results in reasoning-based QA tasks. However, hyperbolic flavors of these networks, H-GNN (Ganea et al., 2018), H-GCN (Chami et al., 2019; Chami et al., 2020) and H-GAT (Gulcehre et al., 2019) argue that hierarchical datasets follow the anatomy of hyperbolic space and show improved performance over their Euclidean counterparts. Nonetheless, these approaches are still limited by the constant answer space that does not consider the varying fluctuations of complex queries.

Self-supervised learning (Doersch and Zisserman, 2017; Jamaludin et al., 2017; Xu et al., 2019; Nagrani et al., 2020) utilizes large unannotated datasets to learn representations that can be fine-tuned to other tasks that have relatively smaller amount of annotated data. Traversing over the entities in KGs facilitates an intuitive way of constructing a query-reasoning proxy task (refer Section 4.3) that enables representation learning of entities and relations. These representations, in turn, are employed in downstream tasks with scarce datasets such as anomaly detection.

The proposed HypE model utilizes a self-supervised learning framework that leverages both simple and complex PFOE queries to learn hyperboloid (with varying limits) representations of KG units in a Poincaré ball to efficiently capture hierarchical information.

Proposed Framework

In this section, we first provide the standard method of querying knowledge graphs. Then, we set up the problem and describe the details of our model that learns representations of entities and relations from reasoning queries over Knowledge Graphs (KG).

KGs contain two primary units, namely, entities and relations. Entities are the basic information units that connect to each other by relation units. Heterogeneous graphs (Wang et al., 2019b; Zhang et al., 2019) can be considered as a special case of KGs where the relations serve as hierarchical connections with no inherent information. PFOE queries of translation (t), intersection ($\cap$) and union ($\cup$) serve as the primary means of querying these KGs. Translation queries utilize an entity $e$ and a relation $r$ to retrieve all entities that are connected to $e$ through $r$. An equivalent example of translation query for heterogeneous graphs is to retrieve all children of a node $e$ connected by a certain edge type $r$. Intersection and Union operate over multiple entities $E=\{e_{1},..,e_{n}\}$ and correspondingly retrieve the set of all entities that are connected to all $e_{i}\in E$ and any $e_{i}\in E$. For heterogeneous graphs, the equivalent is to retrieve nodes connected to all nodes $e_{i}\in E$ and any $e_{i}\in E$. An example of PFOE querying is given in Figure 3. The widely studied problem of multi-hop traversal (Fu et al., 2020) is a more specific case of translation queries, where multiple queries are chained in a series.

2. Problem Setup

We denote $KG=(E,R)$ as a set of entities $e_{i}\in E$ and relations $r_{ij}\in R~{}\ :~{}\ e_{i}\rightarrow e_{j}$ as Boolean functions that indicate whether a directed relation $r_{ij}$ holds between $e_{i}$ and $e_{j}$. Intersection ($\cap$) and Union ($\cup$) are positive first-order existential (PFOE) operations defined on a set of queries $q_{1},q_{2},....,q_{n}\in Q$:

3. Manifold Transformation Layer

Hierarchical structures intuitively demonstrate the latent characteristics of a hyperbolic space (Ganea et al., 2018). Thus, we utilize the Poincaré ball (Cannon et al., 1997) to model our representations.

3.2. Gyrovector Spaces

Algebraic operations such as addition and scalar product which are straightforward in the Euclidean space cannot be directly applied in hyperbolic space. Gyrovector spaces allow for the formalization of these operations in hyperbolic space.

Ganea et al. (Ganea et al., 2018) provide the gyrovector operations relevant to training neural networks. The gyrovector operations for Poincaré ball of radius $c$ are Möbius addition $(\oplus_{c})$, Möbius subtraction $(\ominus_{c})$, exponential map $(\exp_{x}^{c})$, logarithmic map $(\log_{x}^{c})$ and Möbius scalar product $(\odot_{c})$.

Here, $\coloneqq$ denotes assignment operation for Möbius operations. Also, the norm of $x,y$ can subsume the scaling factor $c$. Hence, in HypE, training can be done with a constant $c$ or trainable $c$. We empirically validate this assumption in our experiments (Section 4.4). Figure 4 shows an example of the manifold transformation from Euclidean space to a Poincaré ball of unit radius. HypE extends the operations to handle complex geometries, explained in Section 3.4.

4. Dynamic Reasoning Framework : HypE

[Horocycles and Hyperboloid]The first figure shows a horocycle which are parallel lines in hyperbolic space and the second figure shows that their intersection leads to a hyperboloid.

From the KG, we derive the following types of directed edge relations to build our dynamic computational graph for learning embeddings.

where $d_{out}$ represents the distance of the entity to limits of the hyperboloid and $d_{in}$ is the distance of the entity from the hyperboloid’s border to its center. $\gamma$ is a scalar weight (set to 0.5 in our experiments) and $\|x\|_{1}$ is the $L1$-norm of x.

This provides us with the translated hyperboloid with a new center and larger limit $(\text{lim}(r)\geq 0)$. A sample operation is illustrated in Figure 7(d)7(a).

Intersection ($\cap$): We model the intersection of a set of hyperboloid embeddings $Q_{\cap}=\{e_{1},e_{2},e_{3},...,e_{n}\}$ as $o_{\cap}$ and entity distance from the result entities $v_{\cap}\in V_{\cap}\subseteq E$ as $d_{\cap}$ where:

[four figures]The three figures show the three operations translation, intersection and union of hyperboloids. The fourth figure visualizes the hyperbolic distance.

Union ($\cup$): Unlike intersection, union operations are not closed under hyperboloids (union of hyperboloids is not a hyperboloid). Hence, the distance of entities from the union query space ($d_{\cup}$) is defined as the minimum distance from any hyperboloid in the union. For a set of hyperboloid embeddings $Q_{\cup}=\{e_{1},e_{2},e_{3},...,e_{n}\}$, union space is given by $o_{\cup}$ and distance from result entities $v_{\cup}\in V_{\cup}\subseteq E$ by $d_{\cup}$, where

Note that, since union is not closed under hyperboloids it cannot be applied before the other operations. We circumvent this problem by utilizing Disjunctive Normal Form (DNF) transformation (Ren* et al., 2020) on our logical queries. This allows us to push all the union operations to the end of our computational graph, thus maintaining validity for all PFOE queries. An outline of HypE’s training procedure is given in Algorithm 1.

5. Implementation Details

We implemented HypE in Pytorch (Paszke et al., 2019) on two Nvidia V100 GPUs with 16 GB VRAM. For gradient descent, the model is trained using Reimannian Adam optimizer (Becigneul and Ganea, 2019) with an initial learning rate of 0.0001 and standard $\beta$ values of 0.9 and 0.999. We utilize ReLU (Nair and Hinton, 2010) as the activation function. Also, we randomly selected 128 negative samples per positive sample in the training phase to learn better discriminative features. For our empirical studies, we learned hyperboloid embeddings of $2\times 400$ dimensions (d=400). Due to the conditionality (i.e., if conditions in Algorithm 1) in our computational graph, we employ a switch mechanism between the network layers (Fang et al., 2017; Looks et al., 2017). The switch mechanism receives an operator signal that defines the operation and accordingly connects/disconnects a layer from the framework. A disconnected switch blocks back-propagation of weight updates to the disconnected layers. This enables a concurrent use of all PFOE queries to update the entity and relation embeddings. For an input query $Q$ and resultant entities $V$, Algorithm 1 provides the pseudocode of our overall framework to learn representations of entities $E$ and relation $R$. The algorithm describes the three main operations, namely, translation (lines 1-1), intersection (lines 1-1), and union (lines 1-1) Implementation code: https://github.com/amazon-research/hyperbolic-embeddings.

Experimental Setup

This section describes the experimental setup that analyzes the performance of HypE on various problems. We aim to study the following research questions:

RQ1: For the task of reasoning over KGs, are hyperboloid embeddings better than the baselines at learning hierarchical relations?

RQ2: What is the contribution of individual components in the HypE model?

RQ3: Do the representations capture relevant data features for the downstream task of anomaly detection?

RQ4: Can hyperboloid embeddings leverage auxiliary semantic information from the entities?

RQ5: Can we comprehend the latent representational space obtained by the proposed HypE model?

We perform our experimental study on the following standard KG and hierarchical graph datasets:

FB15k (Bordes et al., 2013) contains knowledge base relation triples and textual mentions of Freebase entity pairs. This dataset contains a large number of simple test triples that can be obtained by inverting the training triples.

FB15k-237 (Toutanova et al., 2015) is a subset of FB15k where all the simple inversible relations are removed, so the models can learn and focus on more complex relations.

NELL995 (Carlson et al., 2010) is a KG dataset of relation triples constructed from the $995^{th}$ iteration of the Never-Ending Language Learning (NELL) system.

DBPedia Hierarchical Taxonomyhttps://www.kaggle.com/danofer/dbpedia-classes is a subset extracted from Wikipedia snapshot that provides multi-level hierarchical taxonomy over 342,782 articles (leaf-nodes).

E-commerce Product NetworkProprietary dataset is a subsampled product taxonomy from an e-commerce platform.

To be consistent with KG terms, for the hierarchical graph datasets (DBPedia and E-commerce) we consider all the intermediate and leaf nodes as entities and the edges between them as relations. Additionally, we consider two variants for encoding edges. First, all edges are considered identical ($|R|=1$) and second, where all edges are depth-encoded ($|R|=p$), where $p$ is maximum depth of the hierarchy ($p=3$ for DBPedia and $p=4$ for E-commerce dataset). For cross-validation and evaluation, we split the graph $KG$ into three parts: $KG_{train}$, $KG_{valid}$ and $KG_{test}$ in a $75:10:15$ ratio for our experiments. More details of the datasets are given in Table 1.

2. Baselines

We select our baselines based on the following two criteria:

The embedding geometries are closed under the intersection and translation operation, e.g., the translation or intersection of arc-aligned hyperboloids results in an arc-aligned hyperboloid.

The baseline can be intuitively extended to all PFOE queries over KG. This is necessary to have a fair comparison with HypE that can leverage all PFOE queries.

We adopt the following state-of-the-art baselines based on geometric diversity and our criterion to compare against HypE:

Graph Query Embedding (GQE) (Hamilton et al., 2018) embeds entities and relations as a vector embedding in the Euclidean space.

Knowledge Graph Attention Network (KGAT) (Wang et al., 2019a) embeds entities and relations as a vector embedding in the Euclidean space utilizing attention networks over entities and relations with a TransR loss (Lin et al., 2017) .

Hyperbolic Query Embeddings (HQE) (Ganea et al., 2018) utilizes manifold transformations (refer to Section 3.3) to represent entities and relations as a vector embedding in hyperbolic space.

Query2Box (Q2B) (Ren* et al., 2020) embeds entities and relations as axis-aligned hyper-rectangle or box embeddings in Euclidean space.

Some of the other possible baselines (Bordes et al., 2013; Nickel et al., 2011; Yang et al., 2015), solely, focus on the multi-hop (or translation) problem. They could not be naturally extended to other PFOE queries. Additionally, other geometric variants such as circular and Gaussian embeddings (ulong Pei and Pechenizkiy, 2019; Vilnis and McCallum, 2015) are not closed under intersection (intersection of Gaussians is not a Gaussian).

3. RQ1: Efficacy of the Query-Search space

To analyze the efficacy of the query space obtained from the HypE model, we compare it against the state-of-the-art baselines on the following reasoning query structures:

Single operator queries include multi-level translation (1t, 2t, and 3t) multi-entity intersection ($2\cap,3\cap$) and multi-entity union queries ($2\cup$). 1t, 2t, and 3t denote translation with 1, 2 and 3 consecutive relations, respectively. $2\cap$ and $2\cup$ stand for intersection and union over two entities, respectively. $3\cap$ represents intersection over three entities.

Compound queries contain multiple operators chained in series to get the final result. Our experiments analyze $\cap t$ (intersection-translation), $t\cap$ (translation-intersection) and $\cup t$ (union-translation).

The above queries are illustrated in Figure 8.

We extract the ground truth query-entity pairs by traversing the datasets (Ren* et al., 2020). The models are trained on queries from $KG_{train}$ and validated on $KG_{valid}$. The final evaluation metrics are calculated on $KG_{test}$. We utilize Euclidean norm and hyperbolic distance (given in Eq. (3)) to measure the distance between query embeddings and its resultant entities in Euclidean and hyperbolic spaces, respectively. The sorted query-entity distances are the ranked results for the given query.

Given a test query $q_{test}$, let the true ranked result entities be $E_{result}$ and model’s ranked output be $E_{output}=\{e_{o1},e_{o2},...,e_{on}\}$. The evaluation metrics used in our work are Hits@K and Mean Reciprocal Rank (MRR). The metrics are given by:

From the results in Table 2, we observe that, on average, HypE outperforms the current baselines in translation, single, and compound operator queries by 15%-67%, 4%-13%, and 7%-28%, respectively. The performance improvement linearly increases with higher query depth ($1t<2t<3t$). Furthermore, we notice that unique depth encoding ($|R|=d$) outperforms identical depth encoding ($|R|=1$) by 23% in DBPedia. Because of our subsampling strategy, the E-commerce Product Network is disjoint (i.e., there are several intermediate nodes that do not share children). Hence, the number of intersection queries are extremely low and insufficient for training HypE or baselines. However, we can still train the translation queries, and the results are shown in Table 3, where we report relative performance improvements with respect to the GQE baseline. For the sake of completeness, results on intersection and union queries are given in the Appendix C.

4. RQ2: Ablation Study

In this section, we empirically analyze the importance of different layers adopted in the HypE model. For this, we experiment with different variations of the center aggregation layer; Average (HypE-Avg), Attention (HypE) (refer to Eq. (6)) and Deepsets (HypE-DS) (refer to Eq. (7)). Furthermore, we test the exclusion of intersection and unions to comprehend their importance in the representation learning process. We adopt two variants of HypE; one trained on only 1t queries (HypE-Avg-1t) and the other trained on all translation queries (HypE-Avg-1,2,3t). Table 4 presents the performance metrics of different variants on the query processing task, averaged across all the datasets including the E-commerce dataset. The results are provided in Table 4.

Firstly, we observe that the exclusion of intersection and union queries results in a significant performance decrease by 25% (Avg-1,2,3t vs HypE). Furthermore, removing deeper queries such as 2t and 3t, also results in an additional decrease by 17% (Avg-1t vs Ag-1,2,3t). The tests on different aggregation layers prove that Attention is better than average and Deepsets by 23.5% and 14.5%, respectively. Additionally, we notice that employing a trainable curvature results in a slight performance improvement of 0.3%. However, given the incremental performance boost but significant increase in the number of parameters ($\sim$10K) that the trainable curvature adds to the framework, we ignore this component in the final HypE model.

As explained in Section 3.4, the final HypE model adopts a Poincaré ball manifold with non-trainable curvature, in addition to attention and Deepsets layer for center and limit aggregation, respectively. Additionally, HypE leverages all PFOE queries.

5. RQ3: Performance on Anomaly Detection

In this experiment, we utilize the entity and relation representations, trained on the DBPedia Hierarchical Taxonomy and E-commerce Product Network with query processing task, to identify products that might be anomalously categorized. We consider identifying the anomalous children by three levels of parents (i.e., taxonomy levels); $P_{1}$, $P_{2}$ and $P_{3}$. The motivating application is to categorize items that are potentially mis-categorized by sellers into the more relevant (correct) part of the product taxonomy.

[HypE visualization]The figure shows our datasets interpretation in the hyperbolic space. The figure how higher levels of hierarchy generally contain more samples and hence have spatially larger hyperboloids.

We construct a pseudo-tree, where all parent nodes are infused with 10% noise of randomly sampled anomalous leaf nodes from different parts of the dataset. The goal of the model is to learn representations from this pseudo-tree and identify anomalous leaf nodes of the immediate parent nodes. From the set of all intermediate nodes $KG_{P}$, given a parent $p\in KG_{P}$ and its originial set of children $C_{+}=children(p)$ and randomly sampled set of anomalous children $C_{-}=children\left(KG_{P}\setminus\{p\}\right)$, the aim here is to identify $c\in C_{-}$ from $C_{+}\cup C_{-}$. We use Precision, Recall and F1-score as the evaluation metrics for this experiment.

The results (given in Table 5 and Table 6) show that, although HypE has comparable performance to baselines at $P_{1}$, it outperforms the baselines by more than $5\%$ at $P_{2}$ and $P_{3}$. This demonstrates the robustness of HypE to noisy data and its capability of capturing relevant hierarchical features (as F1 on $P_{3}>P_{2}>P_{1}$) for downstream tasks. Furthermore, the specific task is critical in e-commerce search as irrelevant results impede a smooth user experience. Table 7 presents some qualitative examples from the E-commerce dataset.

6. RQ4: Leveraging Semantic Information

KGs generally also contain additional auxiliary information within the entities. In this section, we test the possibility of leveraging the semantic information in the DBPedia (article titles) and E-commerce (product titles) dataset to improve representations. We study two methods to connect HypE with FastText embeddings (Bojanowski et al., 2017) of the corresponding titles:

Semantic Initiation (SI) initiates the HypE’s entities with semantic embeddings and learns new HypE-SI embeddings with the query-processing task (given in Section 4.3).

Semantic Collaboration (SC) concatenates the HypE’s pre-trained entity representations with semantic embeddings.

We investigate the performance of these methods on the task of anomaly detection. The results of the experiments are given in Tables 5 and 6. The results demonstrate that HypE-SI shows no significant performance improvement over HypE. That is, a good semantic initialization of the vectors does not result in better representations. This is reasonable, since the semantic embeddings are learnt in the Euclidean space, and several transformations occur between the initialization and final representations. This also means that the learning framework is robust to initialization. We observe a performance improvement of $2\%-8\%$ in case of HypE-SC when compared to HypE. This suggests the ubiquity of HypE since hierarchical representations can be independently augmented with other auxiliary features to solve more complex tasks. From the examples given in Table 7, we can observe that HypE-SI is able to leverage semantic information from product title and category name to enrich HypE’s hierarchical information to produce better predictions. The additional semantic information is especially useful for product miscategorization. In the absence of semantic information, HypE will merely learn representations based on the noisy graph and will lose discriminative information between outliers and correct nodes.

7. RQ5: Visualization of the Poincaré ball

Figure 9(b) depicts the HypE representations in a Poincaré ball manifold. Notice that the density of nodes increases superlinearly from the center towards the circumference, which is analogous to the superlinear increase in the number of nodes from root to the leaves. Thus, HypE is able to learn a better distinction between different hierarchy levels, when compared to the Euclidean distance-based baselines, which conform to a linear increase. Furthermore, we observe that hyperboloid intersections in DBPedia Taxonomy (Figure 9(a)) capture entities with common parents. Also, the disjoint nature of E-commerce Product Networks (Figure 9(b)) is illustrated by disjoint non-intersecting hyperboloids in the latent space. In addition, we can also notice that the learnable limit parameter adjusts the size of hyperboloids to accommodate its varying number of leaf nodes. Thus, the complex geometry of HypE is able to improve its precision over vector baselines that, generally, utilize static thresholds over distance of the resultant entities from query points.

Conclusion

In this paper, we presented Hyperboloid Embeddings (HypE) model, a novel self-supervised learning framework that utilizes dynamic query-reasoning over KGs as a proxy task to learn representations of entities and relations in a hyperbolic space. We demonstrate the efficacy of a hyperbolic query-search space against state-of-the-art baselines over different datasets. Furthermore, we also show the effectiveness of hyperboloid representations in complex downstream tasks and study methods that can leverage node’s auxiliary information to enrich HypE features. Additionally, we analyze the contribution of HypE’s individual components through an ablation study. Finally, we present our hyperboloid representations in a 2-dimensional Poincaré ball for better comprehensibility.

References

Appendix A Hyperbolic vs Euclidean distances

To better analyze the impact of adopting hyperbolic space, we need to understand its distinction from the Euclidean space in handling hierarchy. For this, we study the intra-level and inter-level Euclidean and hyperbolic distance between entities at different levels of the dataset. Let us say $E_{p}$ is the set of entities at level $P_{p}$ in the E-commerce Product Networks dataset. For the analysis, we calculate two sets of distances; intra-level ($\Delta_{intra}$) and inter-level ($\Delta_{inter}$) distance as follows:

$\delta(.~{},~{}.)$ is replaced with Euclidean norm (on Query2Box representations) and hyperbolic distance ($d_{hyp}$ on HypE representations) to understand the difference between the hierarchical separation of entities in the two spaces.

In the $\Delta_{intra}$ results (depicted in Figure 10), we observe that, with increasing level of hierarchy the distance between entities at different levels remains constant in the case of Euclidean space and shows a clear decreasing trend for hyperbolic space. This indicates denser clustering of entities at the same level. Additionally, the $\Delta_{inter}$ results, illustrated in Figure 11, depict a linear increase in distance between inter-level entities in the Euclidean space and a superlinear growth in the hyperbolic space. This shows that hyperbolic space also learns clusters such that inter-level entities are farther apart compared to Euclidean space. This nature of inter-level discrimination and intra-level aggregation demonstrates the superior ability of hyperbolic spaces at capturing hierarchical features.

Appendix B Ablation Study: Finer results

The finer results, across all datasets, of our Ablation study, described in Section 4.4, are given in Tables 8 and 9. We observe that, on average over all types of reasoning queries, a combination of attention aggregation for centers and Deepsets aggregation for limits results in the best performance across all the datasets. Thus, we utilize this combination in our final model.

Appendix C E-commerce results

The intersection and union results on the e-commerce datasets, described in Section 4.3, are given in Table 10.