知識圖譜實體對齊1：基於平移（translation）的方法
1 導引
在知識圖譜領域，最重要的任務之一就是實體對齊 [1]（entity alignment, EA）。實體對齊旨在從不同的知識圖譜中識別出表示同一個現實對象的實體。如下圖所示，知識圖譜\(\mathcal{G}_1\)和\(\mathcal{G}_2\)（都被虛線框起來）是采自兩個大型知識圖譜Wikida和DBpedia的小子集。圓角矩形框表示實體，方角矩形表示屬性值。圓角矩形之間的箭頭代表一個關係謂詞（relation predicate），而這就進一步形成了關係元組，如\(（\text{dbp}： \text{Victoria}， \text{country}， \text{dbp}：\text{Australia}）\)，一個圓角矩形和方角矩陣之間的箭頭表示一個屬性謂詞，而這形成一個屬性元組，比如\(（\text{dbp}：\text{Victoria}， \text{total\_area}, \text{237659 km}^2）\)。
我們可以看到同一個現實實體可能會在兩個不同知識圖譜中都有其表示（比如\(\text{Q36687}\)和\(\text{dbp:Victoria}\)）。這兩個知識圖譜擁有關於這個現實對象互補的信息，\(\mathcal{G}_1\)知識圖譜擁有關於其總理的信息，\(\mathcal{G}_2\)擁有其首都的信息。
如果我們能夠確定\(\mathcal{G}_1\)中的\(\text{Q36687}\)和\(\mathcal{G}_2\)中的\(\text{dbp：Victoria}\)指的是同一個現實世界的實體（也即\(\text{Q36687}\)和\(\text{dbp:Victoria}\)是對齊的實體），那麼我們所獲取的關於該實體的信息就可以大大增加。所謂\(\mathcal{G}_1\)和\(\mathcal{G}_2\) 之間的實體對齊任務即尋找這兩個知識圖譜中的所有對齊實體。在這個例子里，這裡有兩個對齊的實體\(\langle \text{Q36687, dbp:Victoria}\rangle\)和$ \langle Q408, dbp:Australia \rangle$。
形式化的說，我們將知識圖譜表示為\(\mathcal{G}=(\mathcal{E}, \mathcal{R}, \mathcal{T} )\)（為了簡單起見，本文暫不考慮屬性謂詞）。給定兩個知識圖譜\(\mathcal{G}_1=(\mathcal{E}_1,\mathcal{R}_1,\mathcal{T}_1)\)和\(\mathcal{G}_2=(\mathcal{E}_2,\mathcal{R}_2,\mathcal{T}_2)\)，知識圖譜對齊任務的目標為識別出所有的對齊實體對\((e_1,e_2), e_1\in \mathcal{E}_1, e_2\in\mathcal{E_2}\)，這裡\(e_1\)和\(e_2\)表示的是同一個真實世界的實體（即\(e_1\)和\(e_2\)是對齊的實體）。
一些過於傳統的知識圖譜實體對齊方法（如基於相似度的方法）我們就不再敘述了，目前主流的都是基於embedding的知識圖譜實體對齊方法。基於embedding的知識圖譜實體對齊框架如下：
可見基於embedding的知識圖譜實體對齊框架由三個部分組成：embedding模塊，alignment模塊，inference模塊。embedding模塊和對齊模塊可能會交替或共同訓練，這兩個模塊一起構成了知識圖譜實體對齊中的training模塊。
知識圖譜embedding模塊負責學習實體和關係的表徵（常常是低維的），也即它們的embeddings，常常會利用到一下四種信息：知識圖譜的結構（即原始知識圖譜數據中的關係元組），關係謂詞，屬性謂詞和數性值（屬性謂詞和屬性值本文暫不討論）。而其嵌入方法包括基於平移的（translation-based）和基於GNN的（GNN-based），這塊大家可以去閱讀知識圖譜嵌入的入門資料，此處不再贅述。
下面我們來看alignment模塊。由於embedding模塊獨立地學習知識圖譜的emebddings，這使得\(\mathcal{G}_1\)和\(\mathcal{G}_2\)的embeddings落入到不同的向量空間中。而alignment模塊旨在將兩個知識圖譜的embeddings統一（unify）到同樣的向量空間中，這樣就能夠識別出對齊的實體了，而這個統一操作也是知識圖譜對齊最大的挑戰。
這類似於NLP中對跨語言詞向量的對齊操作，即使用一個線性變換\(W\)將不同embedding空間中的向量投影到一個統一的embedding空間中[2]。
如上圖所示，(A)為兩個不同的詞向量分佈，紅色的英語單詞由\(X\)表示，藍色的意大利單詞由\(Y\)表示，我們想要進行翻譯/對齊（在意大利語裏面，gatto意為「cat」，profondo意為「deep」，felino意為「feline」，「auto」意為「car」）。每一個點代表詞向量空間中的一個單詞，點的大小和單詞在訓練語料中出現的頻率成正比。(B)意為學習一個旋轉矩陣\(W\)將兩個分佈大致地對齊。
在知識圖譜對齊的過程中經常會使用一個手工對齊好的實體或關係謂詞集合做為引子，我們把這個叫做種子對齊集合（seed alignments）。種子對齊集合將會被做為輸入特徵來訓練alignment模塊，最常用的方法就是使用一個對齊好的實體集合來做種子\(
\mathcal{S}=\left\{\left(e_1, e_2\right) \mid e_1 \in \mathcal{E}_1, e_2 \in \mathcal{E}_2, e_1 \equiv e_2\right\}
\)。這個種子集合由實體對\((e_1, e_2)\)組成，這裡\(e_1\)是\(\mathcal{E}_1\)中的實體，\(e_2\)是\(\mathcal{E}_2\)中的實體。種子集合被用來計算alignment模塊的損失函數以學習一個統一的向量空間，然後我們就能夠識別出更多潛在的對齊實體。一個典型的損失函數可以被定義如下的Hinge loss形式：
\]
這裡\(\gamma\)是間隔超參數。上面的損失函數被設計來最小化種子對齊集合\(\mathcal{S}\)中實體間的距離，最大化負例集合\(\mathcal{S}’\)中實體對\((e_1′, e_2,’)\)的距離，這裡的負樣本生成的手段為將種子實體對中的一個實體替換為隨機實體。這裡，實體對間的距離由\(f_{\text{align}}\)計算，這個函數被稱為alignment score function。
若按照所要對齊的知識圖譜的類型劃分，則可包括跨語言知識圖譜[3][4][5][6]、多視角實體相關信息知識圖譜[7][8]，和相似領域且存在信息重疊的知識圖譜[9][10]。
若按照對齊策略來劃分，則我們能夠將基於embedding的對齊方法進一步細分為基於平移（translation）的和基於GNN的兩類。這篇文章我們只介紹基於平移的，基於GNN的我們留在下一篇文章介紹。
2 基於平移(translation)的方法
2.1 MTransE
論文[3]是第一個被提出的基於平移的實體對齊模型。它的embedding模塊使用TransE將各個知識圖譜的實體與關係謂詞嵌入不同的embedding空間後。為了使這些embeddings都落入到一個統一的（unfied）空間，它的對齊模塊會最小化下列的alignment score function（對所有的種子元組集合）來進行實體與關係的對齊：
\]
這裡\(\mathcal{S}_t\)是來自\(\mathcal{G}_1\)和\(\mathcal{G}_2\)的種子元組集合（注意不同於之前的種子實體集合，除了實體之外還包括關係謂詞），\(f_{\text{align}}(tr_1,tr_2)\)是alignment score function。注意，不同於我們在前面的第一部分的知識圖譜對齊框架只計算實體的相似程度， 我們前面提到的alignment score function計算兩個元組\(tr_1(h_1, r_1, t_1)\in \mathcal{G}_1\) 和\(tr_2(h_1,r_1,t_1)\in \mathcal{G}_2\)的相似程度。為了計算align score，MTranseE有三種策略來進行跨知識圖譜轉換（cross-KG transition），包括基於距離的軸校準（distance-based axis calibration）和線性變換等。根據作者的實驗，基於線性變換的策略具有最佳的表現，該策略學習了一個從\(\mathcal{G}_1\)到\(\mathcal{G}_2\)的emebdding空間的線性變換，使用下列的score function：
f_{\operatorname{align}}\left(t r_1, t r_2\right)=&\left\|\boldsymbol{M}_{i j}^e \boldsymbol{h}_1-\boldsymbol{h}_2\right\|+\\
&\left\|\boldsymbol{M}_{i j}^r \boldsymbol{r}_1-\boldsymbol{r}_2\right\|+\left\|\boldsymbol{M}_{i j}^e \boldsymbol{t}_1-\boldsymbol{t}_2\right\|
\end{aligned}
\]
這裡\(\boldsymbol{M}_{i j}^e\)和\(\boldsymbol{M}_{i j}^r\)分別為作用於實體和關係embeddings的線性變換。最小化\(f_{\text{align}}\)會最小化變換之後的\(\mathcal{G}_1\)的實體/關係謂詞和\(\mathcal{G}_2\)的實體/關係謂詞之間的距離，使這兩個知識圖譜的embeddings落入到同一個向量空間。
2.2 IPTransE
在embedding模塊，IPTransE[10]首先用TransE的擴展PtransE獨立學習了\(\mathcal{G}_1\)和\(\mathcal{G}_2\)的embeddings。PTransE不同於TransE，它能夠考慮實體之間的路徑，從而對間接連接的實體建模（這裡的路徑由在它們之間形成平移的關係謂詞決定）。
在alignment模塊， IPTranseE也使用了多種策略完成在\(\mathcal{G}_1\)到\(\mathcal{G}_2\)的轉換，包括基於平移的，基於線性變換的和基於參數共享的。
基於平移的策略將平移的思想引入跨知識圖譜對齊領域，它將對齊視為一個來自\(\mathcal{G}_1\)的種子實體集合\(\mathcal{E}_1\)和來自\(\mathcal{G}_2\)的種子實體集合\(\mathcal{E}_2\)之間的特殊的關係謂詞\(r^{(\varepsilon_1\rightarrow \epsilon_2 )}\)。關於種子實體的alignment score function定義如下：
\]
這裡\(\bm{e}_1\)和\(\bm{e}_2\)是實體\(e_1\in\mathcal{E}_1\)和\(\mathcal{e}_2\in\mathcal{E}_2\)的emebddings。目標函數則是嵌入模塊PTransE的損失函數和對齊模塊的損失函數\(f_{\text{align}}\)的加權和。
而基於線性變換的策略則學習一個變換矩陣\(M^{\left(\mathcal{E}_1 \rightarrow \mathcal{E}_2\right)}\)，該矩陣使兩個對齊實體互相接近，其採用的alignment score function如下所示：
\]
而參數共享策略會迫使\(\bm{e}_1 = \bm{e}_2\)，這表示對齊的實體共享相同的embeddings，因此在兩個種子實體上計算\(f_{\text{align}}\)總是得到0，此時目標函數可以規約到PTranE的損失函數。共享策略展示了在三種策略中最佳的emebdding聯合學習效果。
在訓練過程中，IPTransE採用了bootstraping策略並有一軟一硬兩種策略來將新對齊的實體添加到種子對齊集合。在硬策略中（也是通常所使用的），將最新對齊的實體被直接加入到種子對齊集合中，而這可能導致錯誤的傳播；在軟策略中，新對齊的實體會被分配一個置信分數來緩解錯誤傳播。這裡的置信分數對應對齊實體之間的embedding距離，它將會做為損失項添加到目標函數中。
2.3 BootEA
BootEA[9]方法將實體對齊建模為一對一的分類問題，實體所關聯到的另一個實體被視為其標籤。它會從有標籤數據（seed entity alignments）和無標籤數據(predicated aligned entities)進行bootstrapping採樣迭代地學習分類器。它的embedding模塊採用TransE中的score function，此處不再贅述。不過不同於傳統的知識圖譜對齊方法，它的alignment模塊是一個一對一的分類器。該模塊使用在\(\mathcal{G}_1\)的實體分佈和\(\mathcal{G}_2\)的預測類分佈(即對齊實體）之間的交叉熵損失函數。所有在種子實體集合\(S\)中的實體對\(e_1\)、\(e_2\)會被代入到下列等式中計算交叉熵損失：
\]
合理\(\phi_{e_1}(\cdot)\)是一個計算\(e_1\)標籤分佈的函數。如果\(e_1\)被標註為\(e_2\)，標籤分佈\(\phi_{e_1}(\cdot)\)會將其所有概率質量聚集到\(e_2\)，即\(\phi_{e_1}{(e_2)}=1\)。如果\(e_1\)沒有被標註，則\(\phi_{e_1}(\cdot)\) 是均勻分佈。\(\pi(\cdot)\) 是一個給定\(e_1\in \mathcal{E}_1\)，從\(\mathcal{E}_2\)中預測對齊實體的分類器。BootEA的整體損失函數\(\mathcal{E} = \mathcal{L}_e + \beta_2\mathcal{L}_a\)，這裡\(\beta_2\)是一個平衡超參數，\(\mathcal{L}_e\)是embedding模塊的損失。
2.4 NAEA
NAEA[5]也將實體對齊形式化為了一個一對一分類問題，但是將基於平移的範式和基於GAT（Graph Attention Network， 圖注意力網絡）的範式進行了結合。具體來說，NAEA除了關係層次的信息之外還嵌入了鄰居層次的信息。其鄰居信息的嵌入是通過attention機制對其鄰居的emebddings進行聚合來完成的。這裡將其實體\(w\)在鄰居層次的表徵和在關係層面的表徵分別記為\(\text{Ne}(e)\)和\(\text{Nr}(r)\)。其alignment模塊和NAEA類似，也使用了\(\mathcal{G}_1\)實體分佈和\(\mathcal{G}_2\)實體分佈之間的交叉熵損失，如下圖所示：
\]
這裡\(\phi_{e_1}(e_2)\)和BootEA相似，不同之處在於其分類器\(\pi(e_j \vert e_i)\)定義如下：
\pi\left(e_j \mid e_i\right)=& \beta_3 \sigma\left(\operatorname{sim}\left(\operatorname{Ne}\left(e_i\right), \operatorname{Ne}\left(e_j\right)\right)\right) \\
&+\left(1-\beta_3\right) \sigma\left(\operatorname{sim}\left(\mathbf{e}_i, \mathbf{e}_j\right)\right)
\end{aligned}
\]
這裡\(\text{sim}(\cdot)\)是餘弦相似度，\(\beta_3\)是一個平衡超參數。
2.5 TransEdge
TransEdge[11]為了解決TransE的缺點，在embedding模塊中提出了考慮了關係環境（關係的頭節點和尾節點）的平移嵌入模型。舉個例子，
\(\text{director}\)在\((\text{Steve Jobs}, \text{director}, \text{Apple})\)和\((\text{James Cameron}, \text{director}, \text{Avator})\) 這兩個不同的關係元組中就擁有不同的含義，因此考慮關係的環境信息是值得的。這個模型將關係謂詞的環境embebddings(文章中稱之為edge embeddings)視為頭實體到尾實體的平移。
它的alignment模塊使用參數共享策略來統一兩個不同的知識圖譜，也即迫使在種子實體集合中的實體對擁有同樣的embedding。TransEdge使用bootstrapping策略迭代地選擇可能對齊的新實體加入（表示為\(
\mathcal{D}=\left\{\left(e_1, e_2\right) \in \mathcal{E}_1 \times \mathcal{E}_2 \mid \cos \left(\mathbf{e}_1, \mathbf{e}_2\right)>s\right\}
\), \(s\)為相似度閾值），但由於可能產生錯誤，故在每輪迭代中新加入的對齊實體並沒有使用參數共享處理。為了使新對齊的實體在emebdding空間中更接近，論文添加了一個基於新對齊實體集合\(\mathcal{D}\)中的emebdding距離的損失項：
\]
參考
[1] Zhang R, Trisedya B D, Li M, et al. A benchmark and comprehensive survey on knowledge graph entity alignment via representation learning[J]. The VLDB Journal, 2022: 1-26.
[2] Alexis Conneau, Guillaume Lample, Marc』Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. 2018. Word Translation Without Parallel Data. Proceedings of ICLR.
[3] Muhao Chen, Yingtao Tian, Mohan Yang, and Carlo Zaniolo. 2017. Multilingual Knowledge Graph Embeddings for Cross-lingual Knowledge Alignment. In Proceedings of IJCAI. 1511–1517.
[4] Wu Y, Liu X, Feng Y, Wang Z, Yan R, Zhao D (2019a) Relation-aware entity alignment for heterogeneous knowledge graphs. In: IJCAI 2019
[5] Zhu Q, Zhou X, Wu J, et al. Neighborhood-Aware Attentional Representation for Multilingual Knowledge Graphs[C]//IJCAI 2019: 1943-1949.
[6] Pei S, Yu L, Yu G, et al. Rea: Robust cross-lingual entity alignment between knowledge graphs[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020: 2175-2184.
[7] Cao Y, Liu Z, Li C, Liu Z, Li J, Chua TS (2019) Multi-channel graph neural network for entity alignment. In: ACL 2019
[8] Qingheng Zhang, Zequn Sun, Wei Hu, Muhao Chen, Lingbing Guo, and Yuzhong Qu. 2019. Multi-view knowledge graph embedding for entity alignment. In Proceedings of IJCAI. AAAI Press, 5429–5435.
[9] (2018) Bootstrapping entity alignment with knowledge graph embedding. In: IJCAI 2018
[10] Zhu H, Xie R, Liu Z, et al. Iterative entity alignment via knowledge embeddings[C]//Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 2017.
[11] Sun Z, Huang J, Hu W, et al. Transedge: Translating relation-contextualized embeddings for knowledge graphs[C]//International Semantic Web Conference. Springer, Cham, 2019: 612-629.
