Knowledge Graph Reasoning with Relational Digraph

Relational path (Definition 1) is a set of triples that are sequentially connected. The path-based methods learn to predict the triple $(e_{q},r_{q},e_{a})$ by a set of relational paths as local evidence. DeepPath (Xiong et al., 2017) learns to generate the relational path from $e_{q}$ to $e_{a}$ by reinforcement learning (RL). To improve the efficiency, MINERVA (Das et al., 2017) and M-walk (Shen et al., 2018) learn to generate multiple paths starting from $e_{q}$ by RL. The scores are indicated by the arrival frequency on different $e_{a}$’s. Due to the complex structure of KG, the reward is very sparse, making it hard to train the RL models (Chen et al., 2020). PathCon (Wang et al., 2021) samples all the paths connecting the two entities to predict the relation between them, which is expensive for the reasoning task $(e_{q},r_{q},e_{a})$.

Instead of directly using paths, the rule-based methods learn logical rules as a generalized form of relational paths. The logical rules are formed with the composition of a set of relations to infer a specific relation. This can provide better interpretation and can be transfered to unseen entities. The rules are learned by either the mining methods like RuleN (Meilicke et al., 2018), EM algorithm like RNNLogic (Qu et al., 2021), or end-to-end training, such as Neural LP (Yang et al., 2017) and DRUM (Sadeghian et al., 2019), to generate highly correlated relational paths between $e_{q}$ and $e_{a}$. The rules can provide logical interpretation and transfer to unseen entities. However, the rules only capture the sequential evidences, thus cannot learn more complex patterns such as the subgraph structures.

As mentioned in Section 1, the subgraphs can preserve richer information than the relational paths as more degree are allowed in the subgraph. GNN has shown strong power in modeling the graph structured data (Battaglia et al., 2018). This inspires recent works, such as R-GCN (Schlichtkrull et al., 2018), CompGCN (Vashishth et al., 2019), and KE-GCN (Yu et al., 2021), extending GNN on KG to aggregate the entities’ and relations’ representations under the message passing framework (Gilmer et al., 2017) as

which aggregates the message $\phi(\cdot,\!\cdot)$ on the $1$-hop neighbor edges $(e_{s},r,e_{o})\!\in\!\mathcal{F}$ of entity $e_{o}$ with dimension $d$. $\bm{W}^{\ell}\!\!\in\!\mathbb{R}^{d\times d}$ is a weighting matrix, $\delta$ is the activation function and $\bm{h}_{r}^{\ell}$ is the relation representation in the $\ell$-th layer. After $L$ layers’ aggregation, the representations $\bm{h}^{L}_{e}\!$ capturing the local structures of entities $e\!\in\!\mathcal{V}$ jointly work with a decoder scoring function to measure the triples. Since the message passing function (1) aggregates information of all the neighbors and is independent with the query, R-GCN and CompGCN cannot capture the explicit local evidence for specific queries and are not interpretable.

Instead of using all the neighborhoods, DPMPN (Xu et al., 2019) designs one GNN to aggregate the embeddings of entities, and another GNN to dynamically expand and prune the inference subgraph from the query entity $e_{q}$. A query-dependent attention is applied over the sampled entities for pruning. This approach shows interpretable reasoning process by the attention flow on the pruned subgraph, but still requires embeddings to guide the pruning, thus cannot be generalized to unseen entities. Besides, it cannot capture the explicit local evidence supporting a given query triple.

p-GAT (Harsha V. et al., 2020) and pLogicNet (Qu and Tang, 2019) jointly learns an embedding-based model and a Markov logic network (MLN) by variational-EM algorithm. The embedding model generates evidence for MLN to update and MLN expends the training data for embedding model to train. MLN brings the gap between embedding models and logic rules, but it requires a pre-defined set of rules for initialization and the training is expensive with the variational-EM algorithm.

Recently, GraIL (Teru et al., 2020) proposes to extract the enclosing subgraph $\mathcal{G}_{(e_{q},e_{a})}$ between the query entity $e_{q}$ and answer entity $e_{a}$. To learn the enclosing subgraph, the relational GNN (Schlichtkrull et al., 2018) with query-dependent attention is applied over the edges in $\mathcal{G}_{(e_{q},e_{a})}$ to control the importance of edges for different queries, but the learned attention weights are not interpretable (see Appendix B). After $L$ layers’ aggregation, the graph-level representations aggregate all the entities $e\in\mathcal{V}$ in the subgraph and are used to score the triple $(e_{q},r_{q},e_{a})$. Since the subgraphs need to be explicitly extracted and scored for different triples, the computation cost is very high.

In Algorithm 1, when evaluating $(e_{q},r_{q},e_{a})$ with different $e_{a}\!\in\!\mathcal{V}$ but the same query $(e_{q},r_{q},?)$, the neighboring edges $\hat{\mathcal{E}}_{e_{q}}^{\ell},\ell\!=\!1\!\dots\!L$ of $e_{q}$ are shared. We have the following observation:

Proposition 1 indicates that the $\ell$-th layer edges $\mathcal{E}_{e_{q},e_{a}|L}^{\ell}$ with different answer entities $e_{a}$ share the same set of edges in $\hat{\mathcal{E}}_{e_{q}}^{\ell}$. A common approach to save computation cost in overlapping sub-problems is dynamic programming. This has been used to aggregate node representations on large-scale graphs (Hamilton et al., 2017) or to propagate the question representation on KGs (Zhang et al., 2018). Inspired by the efficiency gained by dynamic programming, we recursively construct the r-digraph between $e_{q}$ and any entity $e_{o}$ as

Once the representations of $\mathcal{G}_{e_{q},e_{s}|\ell-1}$ for all the entities $e_{s}\in\mathcal{V}_{e_{q}}^{\ell-1}$ in the $\ell\!-\!1$-th layer are ready, we can encode $\mathcal{G}_{e_{q},e_{o}|\ell}$ by combining $\mathcal{G}_{e_{q},e_{s}|\ell-1}$ with the shared edges $(e_{s},r,e_{o})\!\in\!\hat{\mathcal{E}}_{e_{q}}^{\ell}$ in the $\ell$-th layer. Based on Proposition 1 and Eq.(2), we are motivated to recursively encode multiple r-digraphs with the shared edges in $\hat{\mathcal{E}}_{e_{q}}^{\ell}$ layer by layer. The full process is in Algorithm 2.

Initially, only $e_{q}$ is visible in $\mathcal{V}_{e_{q}}^{0}$. In the $\ell$-th layer, we collect the edges $\hat{\mathcal{E}}_{e_{q}}^{\ell}$ and entities $\mathcal{V}_{e_{q}}^{\ell}$ in step 3. Then, the message passing is constrained to obtain the representations for $e_{o}\!\in\!\mathcal{V}_{e_{q}}^{\ell}$ through the edges in ${\mathcal{E}}_{e_{q}}^{\ell}$. Finally, the representations $\bm{h}_{e_{a}}^{L}\!(e_{q},r_{q})$, encoding $\mathcal{G}_{e_{q},e_{a}|L}$ for all the entities $e_{a}\in\mathcal{V}$, are returned in step 7. The recursive encoding can be more efficient with shared edges in $\hat{\mathcal{E}}_{e_{q}}^{\ell}$ and fewer loops. It learns the same representations as Algorithm 1 as guaranteed by Proposition 2.

As the construction of $\mathcal{G}_{e_{q},e_{a}|L}$ is independent with the query relation $r_{q}$, how to encode $r_{q}$ is another problem to address. Given different triples sharing the same r-digraph, e.g. (Sam, starred, Spider-2) and (Sam, directed, Spider-2), the local evidence we use for reasoning is different. To capture the query-dependent knowledge from the r-digraphs and discover interpretable local evidence, we use the attention mechanism (Veličković et al., 2017) and encode $r_{q}$ into the attention weight to control the importance of different edges in $\mathcal{G}_{e_{q},e_{a}|L}$. The message passing function is specified as

where the attention weight $\alpha_{e_{s},r,e_{o}|r_{q}}^{\ell}$ on edge $(e_{s},r,e_{o})$ is

with $\bm{w}_{\alpha}^{\ell}\!\in\!\mathbb{R}^{d_{\alpha}}$, $\bm{W}_{\alpha}^{\ell}\!\in\!\mathbb{R}^{d_{\alpha}\times 3d}$, and $\oplus$ is the concatenation operator. Sigmoid function $\sigma$ is used rather than softmax attention (Veličković et al., 2017) to ensure multiple edges can be selected in the same neighborhood.

After $L$ layers’ aggregation by (3), the representations $\bm{h}_{e_{a}}^{L}\!(e_{q},r_{q})$ can encode essential information for scoring $(e_{q},r_{q},e_{a})$. Hence, we design a simple scoring function

with $\bm{w}\in\mathbb{R}^{d}$. We associate the multi-class log-loss (Lacroix et al., 2018) with each training triple $(e_{q},r_{q},e_{a})$, i.e.,

The first part in (6) is the score of the positive triple $(e_{q},r_{q},e_{a})$ in $\mathcal{T}_{\text{tra}}$, the set of training queries, and the second part contains the scores of all triples with the same query $(e_{q},r_{q},?)$. The model parameters $\bm{\Theta}=$ $\big{\{}\{\bm{W}^{\ell}\}$, $\{\bm{w}_{\alpha}^{\ell}\}$, $\{\bm{W}_{\alpha}^{\ell}\}$, $\{\bm{h}_{r}^{\ell}\}$, $\bm{w}\big{\}}$ are randomly initialized and are optimized by minimizing (6) with stochastic gradient descent (Kingma and Ba, 2014).

We provide Theorem 1 to show that if a set of relational paths are strongly correlated with the query triple, they can be identified by the attention weights in RED-GNN, thus being interpretable. This theorem is also empirically illustrated in Section 5.4.

In this part, we compare the inference complexity of different GNN-based methods. When reasoning on the query $(e_{q},r_{q},?)$, we need to evaluate $|\mathcal{V}|$ triples with the different answer entity $e\in\mathcal{V}$. We assume the average degree as $\bar{D}$ and average number of edges in each layer of r-digraph as $\bar{E}$.

• •

  RED-Simp (Algorithm 1). For construction, the main cost, which is $O\big{(}\min(\bar{D}^{L},|\mathcal{F}|L)\big{)}$ with the worst case cost $O(|\mathcal{F}|L)$, comes from extracting the neighborhoods of $e_{q}$ and $e_{a}$. Along with encoding, the total cost is $O\big{(}|\mathcal{V}|\cdot(\min(\bar{D}^{L},|\mathcal{F}|L)+d\bar{E}L)\big{)}$.

• •

  RED-GNN (Algorithm 2). Since the full computation is conducted on $\hat{\mathcal{E}}_{e_{q}}^{\ell}$ and $\mathcal{V}_{e_{q}}^{\ell}$, thus the cost is the number of edges times the dimension $d$, i.e. $O(d\cdot\min(\bar{D}^{L},|\mathcal{F}|L))$ and $d\ll|\mathcal{V}|$.

• •

  CompGCN. All the representations are aggregated in one pass with cost $O(d|\mathcal{F}|L)$. Then the scores for all the entities are computed with cost $O(|\mathcal{V}|d)$. The total cost is $O(d|\mathcal{F}|L+d|\mathcal{V}|)$.

• •

  DPMPN. Denote the dimension and layer in the non-attentive GNN as $d_{1},L_{1}$, the average sampled edges in the pruning procedure as $\bar{D}$. The main cost comes from the non-attentive GNN with cost $O(d_{1}|\mathcal{F}|L_{1})$. The cost on sampled subgraph is $O(d\bar{D}^{L})$. Thus, the total computation cost is $O(d_{1}|\mathcal{F}|L_{1}+d\bar{D}^{L})$.

• •

  GraIL. Denote $\bar{V}$ as the average number of entities in the subgraphs. The complexity in constructing the enclosing subgraph is $O(\bar{E}\log\bar{V})$ with $\bar{E}$ edges and $\bar{V}$ entities. The cost of the GNN module is $O(d\bar{E}L)$. Then the overall cost is $O\big{(}|\mathcal{V}|(\bar{E}\log{\bar{V}}+d\bar{E}L)\big{)}$.

In comparison, we have RED-GNN $\approx$ CompGCN $<$ DPMPN $<$ RED-Simp $<$ GraIL in terms of inference complexity. The empirical evaluation is provided in Section 5.3.

Inductive reasoning is a hot research topic (Hamilton et al., 2017; Sadeghian et al., 2019; Teru et al., 2020; Yang et al., 2017) as there are emerging new entities in the real-world applications, such as new users, new items and new concepts (Zhang and Chen, 2019). Being able to reason on unseen entities requires the model to capture the semantic and local evidence ignoring the identity of entities.

Transductive reasoning, also known as KG completion (Trouillon et al., 2017; Wang et al., 2017), is another general setting in the literature. It evaluates the models’ ability to learn the patterns on an incomplete KG.

We compare the complexity in terms of running time and parameter size of different methods in this part. We show the training time and the inference time on $\mathcal{T}_{\text{tst}}$ for each method in Figure 2(a), learning curves in Figure 2(b), and model parameters in Figure 2(c).

We visualize some exemplar learned r-digraphs by RED-GNN with $L\!=\!3$ on the Family and UMLS datasets. Given the triple $(e_{q},r_{q},e_{a})$, we remove the edges in $\mathcal{G}_{e_{q},e_{a}|L}$ whose attention weights are less than $0.5$, and extract the remaining parts. Figure 3(a) shows one triple that DRUM fails. As shown, inferring id-$1482$ as the son of id-$1480$ requires the knowledge that id-$1480$ is the only brother of the uncle id-$1432$ from the local structure. Figure 3(b) shows the example with the same $e_{q}$ and $e_{a}$ sharing the same digraph $\mathcal{G}_{e_{q},e_{a}|L}$. As shown, RED-GNN can learn distinctive structures for different query relations, which caters to Theorem 1. The examples in Figure 3 demonstrate that RED-GNN is interpretable. We provide more examples and the visualization algorithm in Appendix A.

Second, we replace Algorithm 2 in RED-GNN with the simple solution in Algorithm 1, i.e. RED-Simp. Due to the efficiency issue, the loss function (6), which requires to compute the scores over many negative triples, cannot be used. Hence, we use the margin ranking loss with one negative sample as in GraIL (Teru et al., 2020). As in Table 4, the performance of RED-Simp is weak than RED-GNN since the multi-class log loss is better than loss functions with negative sampling (Lacroix et al., 2018; Ruffinelli et al., 2020; Zhang et al., 2019b). RED-Simp still outperforms GraIL in Table 1 since the r-digraphs are better structures for reasoning. The running time of RED-Simp is in Figure 2(a) and 2(b). Algorithm 1 is much more expensive than Algorithm 2 but is cheaper than GraIL since GraIL needs the Dijkstra algorithm to label the entities.