Is There More Pattern in Knowledge Graph?
Exploring Proximity Pattern for Knowledge Graph Embedding

A knowledge graph is denoted by $\mathcal{G}=(\mathcal{E},\mathcal{R},\mathcal{F})$, where $\mathcal{E}$ and $\mathcal{R}$ represents the set of entities and relations, and $\mathcal{F}=\{(h_{i},r_{i},t_{i})\}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E}$ is the set of triple facts. Knowledge Graph Embedding (KGE) task tries to learn a function $\phi:\mathcal{E}\times\mathcal{R}\times\mathcal{E}\mapsto\mathbb{R}$ such that given a query $q=(h,r,?)$ and an entity $t$, the output score $\phi(q,t)\in\mathbb{R}$ measures the likelihood of $t$ being one of the answers of $q$.

During calculation, $\mathcal{E}$ and $\mathcal{R}$ will be represented as embedding matrix. Entity embedding matrix is formulated as $E\in\mathbb{R}^{n_{e}\times d}$, where $n_{e}$ denotes the number of entities, and $d\ll n_{e}$ is the dimension of embedding. For single entity $e_{i}$, we denote its corresponding vector as boldface form $\mathbf{e}_{i}\in\mathbb{R}^{d}$, which is the transposition of $i$-th row of $E$. Similarly, relation embedding matrix is denoted as $R\in\mathbb{R}^{n_{r}\times d}$, where $n_{r}$ is the number of relations and $\mathbf{r}_{i}$ the embedding vector of relation $r_{i}$.

The relation pattern describes how one entity is related to another by some explicit relation, which is represented by knowledge graph triples, and can be formally defined as:

According to Definition 5, the knowledge graph itself is the sparse embodiment of the relation pattern, hence to capture relation pattern in a global way, we introduce a relation-aware GNN model, which corresponds to $\mathrm{G}_{r}$ in figure 2.

For a single layer, the neighbor aggregation function is formulated as:

$$\mathbf{n}_{i}^{(l)}=\sum_{(e_{j},r_{j})\in\mathcal{N}_{i}}\alpha_{ij}^{(l)}\,\varphi(\mathbf{e}_{j}^{(l)},\mathbf{r}_{j})$$

(4)

$\mathcal{N}_{i}=\{(e_{j},r_{j})|(e_{j},r_{j},e_{i})\in\mathcal{F}\}$ denotes the relational neighbors of entity $e_{i}$, which are the neighbor entities associated with the connecting relation. $\mathbf{r}_{j}$ is the initial embedding of relation and remains invariable for every layer, which will be explained later. $\varphi(\mathbf{e},\mathbf{r})$ is the composition function to fuse the entity and relation information. The selection includes additive function: $\varphi(\mathbf{e},\mathbf{r})=\mathbf{e}+\mathbf{r}$; multiplication function: $\varphi(\mathbf{e},\mathbf{r})=\mathbf{e}*\mathbf{r}$, where $*$ denotes element-wise multiplication; Multilayer Perceptron: $\varphi(\mathbf{e},\mathbf{r})=\mathrm{MLP}([\mathbf{e}||\mathbf{r}])$, where $||$ is the vector concatenation operation. Here we choose additive function, which is the most computational effective one. $\alpha_{ij}^{(l)}$ is the weight for relational neighbor $(e_{j},r_{j})$, the discussion of different weight choices is placed in Appendix A.

Then we update the entity embedding by:

$$\mathbf{e}_{i}^{(l+1)}=\sigma(W_{r}^{(l)}\mathbf{n}_{i}^{(l)})+\mathbf{e}_{i}^{(l)}$$

(5)

$W_{r}^{(l)}\in\mathbb{R}^{d\times d}$ is the linear transformation matrix for relation pattern. After $L$ layers, we use the output entity embedding matrix $E^{(L)}$ as the final output of $\mathrm{G}_{r}$, denoted as $E_{r}$.

For equation 4, different from previous works (Vashishth et al. 2020b) where relations are also updated in each layer, we remain the relation embedding the same. Here we assume that relations serve as the translation operation between entities, and the operation itself should keep consistent effect in different layers.

In this section we will introduce our proposed CP-GNN framework to merge two patterns together and an end-to-end encoder-decoder training paradigm.

At encoding stage, as introduced in section 3.2 and 3.3, two GNNs are employed to capture the global semantic interactions within pattern, which denoted as $\mathrm{G}_{p}$ and $\mathrm{G}_{r}$. Then we stack two GNNs together to capture the deep semantic interactions across pattern. GNN $\mathrm{G}_{p}$ is put back to the $\mathrm{G}_{r}$, because we tend to serve proximity modeling as an enhancement of original knowledge graph embedding. After fusing into the proximity pattern, the encoder will obtain a more comprehensive knowledge embedding.

Given the initial entity and relation embedding matrix as $E\in\mathbb{R}^{n_{e}\times d}$ and $R\in\mathbb{R}^{n_{r}\times d}$, the encoder process follows:

	$\displaystyle E_{r}$	$\displaystyle=\mathrm{G}_{r}(E,R)$		(6)
	$\displaystyle E_{p}$	$\displaystyle=\mathrm{G}_{p}(E_{r})$		(7)

For relation embedding $R$, we transform it by an Multilayer Perceptron (MLP) to get the output embedding. The total output of the encoder can be described as:

	$\displaystyle E_{enc}$	$\displaystyle=E_{p}$		(8)
	$\displaystyle R_{enc}$	$\displaystyle=\mathrm{MLP}(R)$		(9)

In decoder module, we perform the task of Knowledge Graph Completion. The module takes the embedding pair of query $\mathbf{q}=(\mathbf{h},\mathbf{r})$ as input, and aims to measure the answer likelihood with regard to all the entities $\{\mathbf{e}_{1},...,\mathbf{e}_{n_{e}}\}$ of $E_{enc}$. Here we choose ConvE (Dettmers et al. 2018) as our decoder implementation, which uses 2D convolutional neural network to match query and answers. We refer readers to original paper for more details, and here we directly utilize the decoder function as:

$$\mathrm{ConvE}(\mathbf{q},E_{enc})=\mathbf{o}$$

(10)

$\mathbf{o}\in\mathbb{R}^{n_{e}}$ is the matching scores between query and all entities. Then we use binary cross entropy loss to measure the difference between model output $\mathbf{o}$ and target $\mathbf{t}\in\mathbb{R}^{n_{e}}$:

	$\displaystyle\mathcal{L}(\mathbf{o},\mathbf{t})=-\frac{1}{n_{e}}\sum_{i}^{n_{e}}\mathbf{t}[i]\cdot\log(\mathbf{o}[i])+$		(11)
	$\displaystyle(1-\mathbf{t}[i])\cdot\log(1-\mathbf{o}[i])$

$\mathbf{t}[i]$ and $\mathbf{o}[i]$ denote the $i$-th entry of the vector. Then Stochastic Gradient Descent (SGD) algorithm is applied to train model predictions approximating targets.

Our baselines are selected from three categories which are Translational Distance Models: TransE (Bordes et al. 2013), RotatE (Sun et al. 2019), PaiRE (Chao et al. 2021); Semantic Matching Models: DistMult (Yang et al. 2015), ComplEx (Trouillon et al. 2016), TuckER (Balazevic and Allen 2019), ConvE (Dettmers et al. 2018), InteractE (Vashishth et al. 2020a), ProcrustEs (Peng et al. 2021); GNN-based Models: R-GCN (Schlichtkrull et al. 2018), KBGAT (Nathani et al. 2019), SACN (Shang et al. 2019), A2N (Bansal et al. 2019), CompGCN (Vashishth et al. 2020b).

The experimental results are demonstrated in Table 2, where we can see that proposed CP-GNN model obtains state-of-the-art results compared to current methods. On FB15k-237 dataset, CP-GNN obtains best results using four of five metrics, and on WN18RR dataset CP-GNN also achieves best with MRR, H@1 and H@10 metrics. For the MRR metric, which is an important indicator to describe the general ranking performance, CP-GNN attains best results on both two datasets, showing the simultaneous modeling of two semantic patterns encodes a more comprehensive knowledge representation for downstream task. For H@k metrics, CP-GNN achieves best performance on five terms across two datasets. The only exception is H@3 on WN18RR, while the result is also competitive. This shows that CP-GNN maintains a high prediction accuracy for top ranking entities. For the MR metric, CP-GNN also gives a competitive performance. Note that for the models PaiRE (Chao et al. 2021) and KBGAT (Nathani et al. 2019) with the best MR reporting, their other metric outcomes are not so as outstanding, and CP-GNN still achieves the better overall performance.

In addition, we observe that CP-GNN shows a comparatively better performance on FB15k-237 dataset than WN18RR. We consider such performance differences are caused by the query complexity characteristics of two datasets. In FB15k-237, there are high rate of queries with multiple answers (also known as 1-N relations from triple view), which demands higher modeling capacity to capture latent relevancy among answers, i.e. proximity pattern. While in WN18RR most queries only satisfy one answer (also known as 1-1 relations), implying WN18RR is an easier dataset that traditional relation pattern is sufficient to some extent. This can also be proven from the consistently better performance on WN18RR relative to FB15k-237 across most models. We think that proximity pattern plays a more important role in complex query scenarios like in FB15k-237, which will be further discussed in section 5.2.

To evaluate the effect of proximity pattern for model performance on KGC task, we do the ablation study of removing the proximity pattern modeling module $\mathrm{G}_{p}$ in CP-GNN, and denote the remained architecture that only retains knowledge graph module $\mathrm{G}_{r}$ as CP-GNN (KG). Corresponding to the figure 2, after relation pattern modeling the obtained embedding $\mathrm{E}_{r}$ will be directly input into the decoder as $\mathrm{E}_{enc}$. The relation embedding $R$ and its transformation will remain unchanged. The comparison results on FB15k-237 test set are summarized in Table 3. We can observe the performance degeneration across all five metrics in CP-GNN (KG), which shows the limited capacity of only modeling relation pattern and the effectiveness of fusing into proximity pattern.

In this section, we will further probe into how does CP-GNN and CP-GNN (KG) perform in the subdivided data complexity scenarios. For each query-answer data, we decide its category based on its answer set size, which serves as an implication of modeling complexity. Intuitively, more answers need to simultaneously satisfy for one query, higher probability the conflicts may happen, which puts forward higher requirements for the model to capture the latent closeness relevancy among answer entities. In practice, for every $(h,r,t)$ we will count the satisfied entities in train set of query $(h,r,?)$ and $(?,r,t)$ as its two categories. We denote the category as N-type.

We divide N-type into six ranges: N$=$0, N$=$1, 1$<$N$<=$10, 10$<$N$<=$100, 100$<$N$<=$500, N$>$500, representing the different complexity level. The statistics of N-type data in FB15k-237 and WN18RR is summarized in table 4. We can see that in FB15k-237 the proportion of complex data is obviously larger, where 10$<$N$<=$100 is 0.27 and 100$<$n$<=$500 is 0.13, and the counterparts in WN18RR are 0.09 and 0.04 respectively. This corresponds to our analysis in section 4.2, that FB15k-237 is a harder dataset so most models reveal a worse performance compared to WN18RR dataset.

We demonstrate the MRR result of CP-GNN and CP-GNN (KG) on different N-type ranges in figure 4. We can observe that CP-GNN outperforms or competes CP-GNN (KG) in all scenarios, and when N$>$10 the improvements are especially evident. This shows that the proximity pattern can effectively boost the modeling capacity for complex data. We consider this is because through proximity pattern, the potential answer entities will be modeled more close to each other, and the model can easily utilize observed facts to infer out unknown answers, like what illustrated in figure 1.