Aligning Multiple Knowledge Graphs in a Single Pass (2024)

Firstly, we augment the original KG data to add a virtual self-relation $r_{self}$ into the relation set $\mathcal{R}$, formally described as follows:

Then, for each entity, we add a virtual triple to describe that each entity $e_{i}$ has the self-relation $r_{self}$ between itself, which is added to the triple set as follows:

To facilitate the aggregation of the GNN encoder, for entity $e_{i}$, we define the set of its neighbor relation-entity tuples as follows:

Although the relations in KGs are usually directed, following most previous works, we treat them as bi-directed (or undirected). This is reasonable because the inverse of each relation is usually intuitive as well. For instance, for the triple $<$Obama, wife, Michelle$>$, we can also rewrite it as: $<$Michelle, husband, Obama$>$. Note that due to the addition of self-connection, entity $e_{i}$ will have a special neighbor relation-entity tuple: $<r_{self},e_{i}>\in\mathcal{N}_{i}$.

In a layer of our KG encoder, the output representation of entity $e_{i}$ is computed as follows:

where ${\mathbf{h}}_{j}$ is the neighbor entity $e_{j}$’s feature vector output by the previous layer, ${\mathbf{W}}_{k}$ is a relation-specific projection matrix, ${\alpha}_{i,k,j}$ is the attention coefficient for aggregation, and $\sigma$ is the non-linear activation function.

There are often thousands of relations in common KGs, and thus the relation-specific projection matrices ${\mathbf{W}}_{k},\forall r_{k}\in\mathcal{R}$ may introduce too many trainable parameters, risking overfitting. Therefore, following previous studies[24, 25], we leverage the relation embedding vector ${\mathbf{g}}_{k}$ to define its related projection matrix, as follows:

In this way, we no longer need to introduce additional parameters. In particular, the normalization constraint $\left\|{\mathbf{g}}_{k}\right\|_{2}=1$ is imposed, so that the orthogonality of ${\mathbf{W}}_{k}$ is naturally guaranteed since we can easily derive:

The orthogonality of ${\mathbf{W}}_{k}$ is proven to be very beneficial for EA task[24, 25].

The attention coefficient is computed as follows. Given a neighbor tuple $<r_{k},e_{j}>\in\mathcal{N}_{i}$ of entity $e_{i}$, we first compute the proximity among the head entity $e_{i}$, the relation $r_{k}$, and the tail entity $e_{i}$:

where ${\mathbf{a}}_{h}$, ${\mathbf{a}}_{r}$, and ${\mathbf{a}}_{t}$ are learnable parameter vectors for head entities, relations, and tail entities, respectively. Then, we compute the attention coefficient ${\alpha}_{i,k,j}$ by normalizing ${\beta}_{i,k,j}$ across all the elements of $\mathcal{N}_{i}$:

Note that by adding the self-relation $r_{self}$, each entity $e_{i}$ itself acts as one of its own neighbors (Cf. Eqs. (1, 2)). In addition, we use the attention mechanism to aggregate all the neighbors (Cf. Eqs. (4, 8)). Thus, as proven by[46], our encoder is able to automatically learn the importance of arbitrary hops of neighborhood information. This is more flexible than[24, 25], which directly concatenates all hops of neighborhood information.

In order to pull equivalent entities together in a unified embedding space, we adopt the following margin ranking loss as the training loss of our MultiEA model:

where $\mathcal{S}$ is the set of positive examples, i.e., ground-truth alignment labels, $\mathcal{S}^{\prime}$ is the set of negative examples, i.e., randomly generated false alignment labels, $d(\cdot)$ is a distance function, and $\lambda>0$ is a margin hyperparameter for separating positive and negative examples.

The negative examples in $\mathcal{S}^{\prime}$ are generated as follows. For each positive example $l=(e^{(1)},e^{(2)},...,e^{(m)},...,e^{(M)})\in\mathcal{S}$, we fix one entity and replace the other entities by randomly sampling from their corresponding KGs, formally described as follows:

where $\tilde{e}^{(m)}$ is randomly sampled entity from $\mathcal{E}^{(m)}$ to replace the original entity $e^{(m)}$. Here, $\eta$ is an integer, indicating that for each positive example, we generate $\eta$ groups of negative examples in this way. Thus, each positive example corresponds to $\eta\times M$ negative examples.

(1) Moving toward Mean.This strategy lets all the equivalent entities approach their mean, as illustrated in Figure2(a). We first compute the mean as follows:

Then, we sum the Euclidean distances between each entity embedding and the mean:

(2) Moving toward Anchor.In practice, the candidate KGs are usually unbalanced due to various realistic factors. For instance, on our constructed multi-lingual KG dataset DBP-4, the English KG contains many more triples than the other three KGs (Cf. TableI). Therefore, as shown in Figure2(b), we designate entities from KG DBP-4: en as anchor entities and let the equivalent entities from the other KGs approach these anchor entities. This idea is formally described as follows:

where $\mathbf{h}^{(a)}$ is embedding of the anchor entity¹¹1Note that when $\mathbf{h}^{(m)}$ is designated as anchor entity, then $\|\mathbf{h}^{(m)}-\mathbf{h}^{(a)}\|_{2}=0$..

(3) Moving toward Each Other.This strategy lets equivalent entities approach each other. As illustrated in Figure2(c), we minimize the distances between all possible pairs of equivalent entities, formally described as follows:

where $m_{1}$ and $m_{2}$ are in the set $\{1,2,...,m,...,M\}$.

After training the model, we can obtain the embeddings of the entities from all the KGs. Based on these embeddings, we can compute the similarity between any two entities that are from different KGs. For example, given entity $e_{i}^{(m_{1})}\in\mathcal{E}^{(m_{1})}$, and entity $e_{j}^{(m_{2})}\in\mathcal{E}^{(m_{2})}$, we compute the similarity between them as follows²²2Since entity embeddings are normalized, i.e., $\left\|{\mathbf{h}_{i}}\right\|_{2}=1,\forall i$, the computed similarities lie in the range $[0,1]$. Thus, we can compose high-order similarities by matrix product operation later.:

Thus, we can obtain a matrix ${\mathbf{S}}^{m_{1}-m_{2}}$ to describe the entity similarities between $\mathcal{G}^{(m_{1})}$ and $\mathcal{G}^{(m_{2})}$. However, Eq.(15) only captures the first-order similarity, which may not be sufficient since some higher-order similarity information is ignored. Therefore, in this work, we propose to further enhance the similarity matrix by incorporating higher-order similarities, which can be composed by matrix product operation. For example, if there are three KGs, $\mathcal{G}^{(m_{1})}$, $\mathcal{G}^{(m_{2})}$, and $\mathcal{G}^{(m_{3})}$, we can enhance the similarity matrix ${\mathbf{S}}^{m_{1}-m_{2}}$ as follows:

where $\gamma_{1}$ and $\gamma_{2}$ are hyperparameters to balance the two terms. They are real numbers in the range $[0,1]$ and satisfy $\gamma_{1}+\gamma_{2}=1$. Similarly, if there are four KGs, we can enhance ${\mathbf{S}}^{m_{1}-m_{2}}$ as follows:

where $\gamma_{1}$, $\gamma_{2}$, and $\gamma_{3}$ are hyperparameters in the range $[0,1]$ and satisfy $\gamma_{1}+\gamma_{2}+\gamma_{3}=1$.

Traditional pair-wise KG alignment methods generally use $Hits@K$ to evaluate the alignment performance. Specifically, given two KGs: $\mathcal{G}^{(l)}$ and $\mathcal{G}^{(r)}$, we first consider aligning $\mathcal{G}^{(r)}$ to $\mathcal{G}^{(l)}$, and define a temporary metric $l\_Hits@K$ to measure the proportion of the entities in $\mathcal{G}^{(l)}$ whose counterpart in $\mathcal{G}^{(r)}$ rank in top-K:

where $\mathbb{I}$ is the indicator function that outputs 1 if the input fact is true and $0$ otherwise. Then, we consider aligning $\mathcal{G}^{(l)}$ to $\mathcal{G}^{(r)}$, and similarly define a temporary metric $r\_Hits@K$ in the opposite direction. The final metric $Hits@K$ is computed as the average of the two temporary metrics:

Unfortunately, $Hits@K$ does not work for our task of multiple KG alignment. Hence, in the spirit of $Hits@K$, we define a novel evaluation metric. Given $M$ KGs: $\{\mathcal{G}^{(1)},\mathcal{G}^{(2)},...,\mathcal{G}^{(m)},...,\mathcal{G}^{($ where $M>2$, we treat each KG $\mathcal{G}^{(m)}$ as the target KG, and consider aligning the other $M-1$ KGs to it. First, we count the number of entities from $\mathcal{G}^{(m)}$ whose all $M-1$ counterparts from the other $M-1$ KGs rank in top-K, described as follows:

where $\widetilde{\mathbb{I}}(\cdot)$ is an indicator function that outputs $1$ if all the input entities rank in top-K, and $0$ otherwise. Then, a temporary metric $m\_Hits@K$ is defined to compute the proportion of:

The final metric is computed as the average of all the $M$ temporary metrics:

Obviously, our newly defined metric $M\text{-}Hits@K$ is more challenging than the traditional metric $Hits@K$ since the condition for counting a correct entity is much more strict. This can better reflect the model performance of aligning multiple KGs.

Regarding baselines, we select six representative supervised EA baselines that only leverage the structural information of candidate KGs, including two Trans-based EA methods (1), (2), and four GNN-based EA methods (3), (4), (5), (6). They are listed as follows:

1. (1)

   MTransE[11] is a Trans-based EA method that uses TransE[15] to encode entities of each KG in a separated embedding space;

2. (2)

   IPTransE[10] further uses PTransE[47] to encode KGs and propose an iterative alignment strategy;

3. (3)

   GCN-Align[16] is the first GNN-based EA method that uses GCN[30] to encode two KGs;

4. (4)

   NAEA[29] further uses GAT[48] to encode the structural information of KGs. Therefore, it learns entity embeddings by aggregating neighbor entities with different importance;

5. (5)

   KECG[28] also uses GAT[48] to encode KGs, and additionally restricts the projection matrix to be a diagonal matrix, reducing the number of parameters and computations;

6. (6)

   PSR[25] encodes KGs based on orthogonal projection matrix and attention aggregation like ours. Differently, (1) it dose not add self-connections, and (2) it directly concatenates all hops of neighborhood information.

1. (1)

   MultiEA+mean-infer;

2. (2)

   MultiEA+anchor-infer;

3. (3)

   MultiEA+each-infer;

4. (4)

   MultiEA+mean+infer;

5. (5)

   MultiEA+anchor+infer;

6. (6)

   MultiEA+each+infer.