Walk-and-Relate: A Random-Walk-based Algorithm for Representation Learning on Sparse Knowledge Graphs

Knowledge graph embedding (KGE) is a machine learning task of learning a low-dimensional representation of a knowledge graph’s entities and relations while preserving their semantic meaning. Leveraging their embedded representation, knowledge graphs (KGs) can be used for various applications such as link prediction, triple classification, entity recognition, clustering, and relation extraction (Ji et al., 2015; Abu-Salih et al., 2021). KGE differs from ordinary relation inference as the information in a knowledge graph is multi-relational and more complex to model and computationally expensive. Many models have been devoted to estimating KGE. Some translation-based embedding models, such as TransE (Bordes et al., 2013), TransH (Wang et al., 2014), TransR (Lin et al., 2015) and TransD (Ji et al., 2015) apply simple linear or bilinear operations to model the embeddings of entities and relations. DistMult (Yang et al., 2014) and ComplEx (Trouillon et al., 2016) design similarity scoring functions to learn semantic information. ConvE (Dettmers et al., 2018) and ConvKB (Nguyen et al., 2017) apply convolutional neural network to learn non-linear features.

In addition, there are approaches that tackle representation learning on homogeneous graphs, i.e., graphs with just one type of relation. Examples include DeepWalk (Perozzi et al., 2014) and node2vec (Grover and Leskovec, 2016). These approaches are based on random walks for embedding generation. For each node in the graph, these models generate a random path of connected nodes. The random path gives a sequence of nodes, and we can train models like Word2Vec (skip-gram) (Mikolov et al., 2013) to obtain the node embeddings. The approaches presented in this paper are motivated from these random-walk based embedding generation approaches.

Rule mining in KGs finds rules such as isMarried(a,b) $\implies$ staysTogether(a,b). Approaches like Inductive Logic Programming (ILP) and AMIE (Galárraga et al., 2013) are popular choices for learning such rules. AMIE is an improved version of a fuzzy Horn rule-mining algorithm based on inductive logic programming (ILP). It overcomes the difficulty of traditional rule-mining algorithms in generating negative evidence on the basis of the open-world assumption. However, the difficulty in finding such rules lies in the exponential size of the search space: every relation can potentially be combined with every other relation in a rule. To tackle this, several extensions of the AMIE have been proposed (Galárraga et al., 2015; Lajus et al., 2020).

One particular type of rule mining finds its use in the multi-hop reasoning. Multi-hop reasoning is the task of learning explicit inference patterns in a KG. For example, if the KG includes the facts such as b is a’s mother, c is b’s husband, we want to learn the following rule (pattern): isMother(a, b) $\And$ isHusband(b, c) $\implies$ isFather(a, c). Path-Ranking Algorithm (PRA) (Lao et al., 2011) is a popular algorithm for estimating such patterns in KGs. Lao et al. (2011) uses a soft inference procedure based on a combination of constrained, weighted, random walks through the knowledge base graph to infer rules for the KG. Their solution can learn to infer different target relations by tuning the weights associated with random walks that follow different paths through the graph, using a version of the PRA.Wang and Li (2015) proposes a rule learning approach RDF2Rules for RDF KGs. Rules are learned by finding frequent predicate cycles in RDF graphs. A new confidence measure is also proposed for evaluating the reliability of the mined rules.Barati et al. (2016) intro an approach called SWARM (Semantic Web Association Rule Mining) to mine semantic association rules from RDF KG. SWARM leverages the schema information to enrich the semantics of the rules. (Xiong et al., 2017) proposes a reinforcement learning framework to find reasoning paths in the KG. Unlike random walk-based models, the RL model allows to control the properties of the found paths. These effective paths can also be used as an alternative to PRA in many path-based reasoning methods.

Various approaches have been developed to augment the KG data. We summarize such approaches in this section. Wang et al. (2016) augments the KG data with a text corpus. Specifically, they introduce additional text-based information and performed joint model training by combining triplets from a knowledge graph with entity descriptions in text. Guo et al. (2016) proposed a method that embeds rules and triplets jointly. This method learns rules based on the TransE model and retrains the embeddings combined with rules. Zhang et al. (2019) proposed IterE, to alleviate the sparsity of entities in KG. In this framework, embeddings and rules are learned iteratively; the embeddings are learned from existing triplets, and new triplets are inferred from the rules that have been learned. Zhao et al. (2020) iteratively trains embeddings and discovers patterns between relations to construct new triplets. For example, the model can discover the pattern that $located\_in$ is the inverse relation of $has\_city$. If the KG contains the triplet $(seattle,located\_in,usa)$, then according to the discovered rules, the model can infer another triplet, $(usa,has\_city,seattle)$. Ho et al. (2018) iteratively extends rules induced from a KG by relying on feedback from a precomputed embedding model over the KG and external information sources including text corpora.Xie et al. (2016) adds entity-level information into the representation learning model by using an encoder. This approach can be used to create fused semantic vectors for entities at different levels to improve the representation effect. Krompaß et al. (2015) adds prior knowledge about the semantics of relation-types, extracted from the schema of the knowledge graph (type-constraints) or approximated through a local closed-world assumption, to the representation learning model. Only triplets that satisfy the type constraints are considered for modelling; thus, irrelevant or erroneous samples can be effectively filtered out to a certain extent.

We borrow ideas from the association rule mining literature (Agrawal et al., 1993) to measure the information conveyed through a metapath, which we call metapath-information. First, we define a association measure, denoted by $assc_{\mathfrak{m}_{i}\shortrightarrow\mathfrak{m}}$, that measures how often an edge with type $\mathfrak{m}_{i}$ is a part of an metapath instance of type $\mathfrak{m}_{i}$. Similar to the confidence measure used in the association rule mining, we define the $assc_{\mathfrak{m}_{i}\shortrightarrow\mathfrak{m}}$ as the fraction of edges of the type $\mathfrak{m}_{i}$ that are a part of the metapath instance for the metapath $\mathfrak{m}$. Formally, the definition is given as

where $n_{e}^{\mathfrak{m}}(\mathcal{G})$ denotes the distinct metapath instances of type $\mathfrak{m}$ that the edge $e$ is a part of in the graph $\mathcal{G}$. Next, we define the metapath-information of the metapath $\mathfrak{m}$ as the product of the association measures $assc_{\mathfrak{m}_{i}\shortrightarrow\mathfrak{m}}$ of each of its constituent relations $\mathfrak{m}_{i}:1\leq i\leq|\mathfrak{m}|$. Formally, we denote the metapath-information of $\mathfrak{m}$ as $z_{\mathfrak{m}}$ and calculate it as

Estimation of $z_{\mathfrak{m}}$ requires enumeration of all the metapath instances of $\mathfrak{m}$. Trivial enumerating these metapath instances would lead to a time and space complexity of the order of $O(|\mathcal{E}|^{|\mathfrak{m}|})$. The exponential complexity raises scalability concerns, and prohibits from estimating the metapath importance for graphs with large number of edges.

In this direction, we provide two heuristics to address the scalability problems. First, we provide an approach to prune the exploration space of the candidate metapaths, that leverages the downward-closure property of the metapath-information. Second, we provide an approach to estimate the metapath-information on a sampled graph.

For the augmentation triplets $(h,\mathfrak{m},t)$ to be used by the desired KG embedding approach that uses triplet scoring functions, we represent the metapath $\mathfrak{m}$ as a single relation in the KG. To address this, we mine rules of the form $\mathfrak{m}\shortrightarrow q$, using the standard notion of confidence used in the association rule mining. Specifically, we define the rule confidence (denoted by $conf_{\mathfrak{m}\shortrightarrow q}$) for the rule $\mathfrak{m}\shortrightarrow q$ as the fraction of node pairs $(h,t)$ such that the triplet $(h,q,t)$ exists given that the path $(h,\mathfrak{m},t)$ exists. Formally,

For a metapath $\mathfrak{m}$, we denote the $rulemap(\mathfrak{m})$ as the mapping that holds the key-value pairs [$q,conf_{\mathfrak{m}\shortrightarrow q}$]. Since we are only interested in high-confidence rules, we add a minimum threshold on the $conf_{\mathfrak{m}\shortrightarrow q}$ for [$q,conf_{\mathfrak{m}\shortrightarrow q}$] to be added to $rulemap(\mathfrak{m})$ (say, $0.5$).

Next, for each informative-metapath $\mathfrak{m}$, we map it to an individual relation with the following setup:

1. (i)

   If the $rulemap(\mathfrak{m})$ is non-empty, we sample a relation $q$ out of $rulemap(\mathfrak{m})$, with the sampling probability $conf_{\mathfrak{m}\shortrightarrow q}$. The sampling is done independently for each augmentation triplet $(h,\mathfrak{m},t)$ on course of the training.

2. (ii)

   If the $rulemap(\mathfrak{m})$ is empty, we simply introduce a new relation for the metapath $\mathfrak{m}$ in the KG.

If a metapath cannot be mapped to existing relations in the KG, we introduce a new relation describing the metapath in the KG. The increase in the number of unique relations would lead to rapid growth in number of parameters (relation embeddings). Specifically, the number of parameters rises exponentially (in terms of number of original relations in the graph) with the lengths of the considered metapaths. In practice this can easily lead to over-fitting on rare metapaths (which counters our primary goal of addressing data-sparsity). To address this problem, we propose various approaches to allow parameter sharing among the embeddings for the metapaths, thus limiting the number of unique parameters and allowing for better generalization.

Given the set of informative metapaths and associated rulemaps, we use random walks to generate instances of those metapaths on the graph. These instances are used to create augmentation triplets in the KG and are directly taken as input by any downstream KG-embedding model based on triplet scoring loss functions. The KG-embedding model, thus, has access to a larger pool of training data, effectively leading to higher-quality KG embeddings. For the KGE model to be aware of the metapath-information and rule-confidence, we use them as the edge-weight for the KGE model (edge-weights are used to scale the loss function for the corresponding triplets). Specifically, if we introduce a new relation for the metapath $\mathfrak{m}$, we use $z_{\mathfrak{m}}$ as the edge-weight for the augmented triplets added as a result of metapath instances belonging to $\mathfrak{m}$. Otherwise, we use $z_{\mathfrak{m}}\times conf_{\mathfrak{m}\shortrightarrow q}$ as the edge-weight for the augmented triplets, where the metapath $\mathfrak{m}$ is mapped to the relation $q$ with rule-confidence $conf_{\mathfrak{m}\shortrightarrow q}$. Algorithm 2 provides the pseudo-code for our algorithm Walk-and-Relate.

We used two standard benchmark datasets (WN18 and FB15K) to evaluate the performance of the proposed approaches and compare against the baselines. FB15k is derived from the Freebased Knowledge Graph (Bollacker et al., 2008), whereas WN18 was derived from WordNet (Miller, 1995). Table 2 shows various statistics for these datasets. Figure 1 shows the degree distribution of the two datasets. The degree distribution of FB15K is relatively more uniform (has low variance) as compared to WN18. For WN18, $\approx 60\%$ of the nodes have degree $\leq 5$, and $\approx 16\%$ of the nodes have degree $\leq 2$. In contrast, FB15k has $\approx 6\%$ of the nodes have degree $\leq 5$, and $\approx 2\%$ of the nodes have degree $\leq 2$. Both datasets and their training/validation/test splits were used as provided by the DGL-KE toolkit.

We use three standard ranking metrics (Lerer et al., 2019) widely used in literature for evaluating the KG embeddings: Hit$@k$ (for $k\in\{1,3,10\}$), Mean Rank (MR), and Mean Reciprocal Rank (MRR). For a positive triplet $i$, let $S_{i}$ be the list of triplets containing $i$ and its associated negative triplets ordered in a non-increasing score order, and let $rank_{i}$ be $i$th position in $S_{i}$. Given that, Hit$@k$ is the average number of times the positive triplet is among the $k$ highest ranked triplets; MR is the average rank of the positive instances, whereas MRR is the average reciprocal rank of the positive instances. Formally, these metrics are defined as

where $Q$ is the total number of positive triplets. Note that $Hit@k$ and MRR are between 0 and 1, whereas MR ranges from 1 to the $\sum_{i}^{Q}S_{i}$.

We choose two representative KG embedding approaches based on triplet-loss functions: TransE and Distmult. TransE is a translation-based model and allows to infer compositional patterns, while Distmult is a similarity scoring-based approach. For these two approaches, we evaluate the different triplet-augmentation and parameter-sharing approaches as described below:

1. (1)

   No augmentation: The models are trained on explicit triplets present in the graph, and thus, no augmentation is done.

2. (2)

   WAR - Only rules: To show the promise of proposed augmentation approaches over earlier approaches that only leverage rules of the form $\mathfrak{m}\shortrightarrow q$, we provide results on an augmentation exercise where we only add additional triplets based on mapping the metapaths to the existing relations in the graph (to mimic the prior approaches).

3. (3)

   WAR - Metapaths + No parameter sharing (WAR + MP): This approach performs augmentation with the discovered informative-metapaths, by introducing a new relation for each metapath, i.e, without any parameter sharing among the metapath (relation) embeddings.

4. (4)

   WAR - Metapaths + parameter sharing using model’s composition properties (WAR + MP + Model): This approach performs augmentation with the discovered informative-metapaths, and uses the relation embeddings to compute the metapath embeddings based on the underlying composition model. Note that this approach cannot be used for DistMult as it does not allow inference of the composition patterns.

5. (5)

   WAR - Metapaths + sequence modeling for metapath (WAR + MP + RNN): This approach performs augmentation with the discovered informative-metapaths, and uses RNN as the sequence model to aggregate the representations of the constituent relations into the representation of the metapath.

6. (6)

   WAR - Metapaths + basis decomposition (WAR + MP + Basis): This approach performs augmentation with the discovered informative-metapaths, and uses the linear combination of a common bases to estimate the embeddings of the metapaths.

We use metapaths of lengths upto three ($l_{max}=3$) to construct augmentation triplets for the WAR approach. All approaches use the mini-batch size of $1,024$ nodes to construct random walks. For both WN18 and FB15K, we use the metapath-information threshold of $0.2$ to prune the search space. We use the full graph to estimate informative metapaths for WN18 but sample $10\%$ edges for FB15K (given its size). To construct the rules, the rule-confidence threshold is set to $0.5$. We use random grid search to optimize for the embedding learning rate (between $[1.0,1e-1,1e-2,1e-3,1e-4,1e-5]$), RNN learning rate (when applicable, between $[1.0,1e-1,1e-2,1e-3,1e-4,1e-5]$), basis learning rate (when applicable, between $[1.0,1e-1,1e-2,1e-3,1e-4,1e-5]$) and regularization norm (between $[0,1e-10,1e-9,1e-8,1e-7,1e-6]$). We use different learning rates for embeddings, RNN parameters and basis parameters because RNN and basis parameters get dense updates, while embeddings get sparse updates. We use MRR as the primary metric and train the KGE models until the performance on the MRR metric does not increase in two successive epochs. All other hyperparameters are kept the same as provided by DGL-KE for each combination of triplet loss function (TransE and Distmult) and Dataset (WN18 and FB15K).