論文題目：Knowledge Graph Alignment Network with Gated Multi-hop Neighborhood Aggregation
論文來源：AAAI 2020 南京大學，阿裡巴巴
論文連結：https://arxiv.org/abs/1911.08936
代碼連結：https://github.com/nju-websoft/AliNet
關鍵詞：知識圖譜，嵌入學習，實體對齊，GNN，注意力機制，門機制
文章目錄
- 1 摘要
- 2 引言
- 3 準備工作
-
- 3.1 GNN
- 3.2 知識圖譜的實體對齊
- 3.3 用于實體對齊的GNN
- 4 知識圖譜對齊網絡
-
- 4.1 Gated Multi-hop Neighborhood Aggregation
- 4.2 Attention for Distant Neighborhood
- 4.3 Contrastive Alignment Loss
- 4.4 Relation Semantics Modeling
- 4.5 實作細節
- 5 實驗
- 6 總結
- 參考文獻
1 摘要
本文研究的是知識圖譜的實體對齊問題。
由于GNN具有識别出同構子圖的能力，是以應用于許多基于嵌入的實體對齊方法。
然而在知識圖譜（KG）中，副本實體（counterpart entities）通常具有非同構的鄰居結構，導緻GNN為它們産生不同的表示。
為了解決這一問題，本文提出一個新的KG對齊網絡，稱為AliNet，旨在以端到端的方式緩解鄰居結構的非同構問題。
由于模式（schema）的異質性，副本實體的直接鄰居通常是不相似的。AliNet引入了遠距離的（distant）鄰居以擴充鄰居結構的重疊部分。還使用了注意力機制強調有幫助的遠距離鄰居并減少噪聲。然後使用門機制，對直接鄰居和遠距離鄰居的資訊進行聚合。
作者還提出了關系損失（relation loss）以改善實體的表示。
在5個實體對齊資料集上進行了實驗，并進行了消融實驗，證明了AliNet的有效性。
2 引言
（1）實體對齊
實體對齊是指從不同的KGs中找到指向真實世界中同一事物的實體。
近期，研究人員越來越關注于使用KG表示學習的方法來處理實體對齊問題，而不使用符号形式學習的方法。
表示學習指的是将KG編碼到向量空間中，實體的語義關系資訊可以通過嵌入操作學習到。嵌入操作有針對特定關系的translation，rotation等。
對于基于嵌入的實體對齊，通常使用實體嵌入間的距離來衡量實體間的相似性。
這種方法已經證明可以有效處理符号異質的問題，有助于單語言的和跨語言的實體對齊任務。
（2）GNN與實體對齊
GNN是可以對圖結構的資料進行表示學習的強有力的模型，通過疊代地聚合目标節點自身以及節點鄰居的表示以得到目标節點的表示。
近期有學者證明[1]GNN在識别同構的子圖方面，具有和WL test（Weisfeiler-Lehman）相同的能力。
這為利用GNN實作不同KGs之間的實體對齊提供了理論依據，因為相似的實體通常具有相似的鄰域。
已經有一些使用GNN進行基于嵌入的實體對齊的方法，并且取得了不錯的效果。
（3）現有的基于GNN的實體對齊模型的缺點
不同的KGs有着異質的模式，并且有的KG是不完全的，是以副本實體（counterpart entities）通常有着并不相似的鄰居結構，以圖 1為例。
圖 1中指向Kobe Bryant的兩個實體的鄰域是不一緻的，鄰居實體集合也是不同的。
有學者在基于BDpedia的基線資料集上進行了統計，結果表明大部分的對齊實體對都具有不同的鄰域實體。
由于要對齊的實體具有不同的鄰域結構，使用GNN就容易導緻為這些實體生成不同的表示。
即使假定兩個KGs是完全的，但由于模式的異質性，還是會使得副本實體具有不相似的鄰域結構。如圖 1中的United States of America，在Wikidata中是Kobe Bryant的一階鄰居，但在DBpedia中是Kobe Bryant的二階鄰居。
（4）作者提出
作者發現語義關聯的資訊可出現在副本實體的直接鄰居或遠距離鄰居中，于是提出AliNet将直接鄰居和遠距離鄰居的資訊進行聚合。
每層AliNet都有多個函數來聚合多跳内的鄰域資訊。
為了減少噪聲資訊，作者進一步使用了注意力機制用于遠距離鄰居資訊的聚合，以端到端的方式找到那些更重要的遠距離鄰居。
最終使用了門機制來組合多個聚合函數的輸出表示，以得到目前層的隐層表示。
還設計了關系損失以調整實體的表示，并使得AliNet可以捕獲到更特殊的結構資訊，例如三角形的關系結構。
3 準備工作
3.1 GNN
GNN的主要思想是遞歸地聚合鄰居的特征向量，以得到目标節點的表示。可使用不同的聚合政策對GNN進行各種變形。
（1）GCN
GNN的一個有名的變形就是Kipf等人提出的vanilla GCN。節點 i i i在第 l l l層的隐層表示定義為 h i ( l ) \mathbf{h}^{(l)}_i hi(l)，計算如下：
其中 N 1 ( ⋅ ) \mathcal{N}_1(\cdot) N1(⋅)表示給定實體的一階鄰居； W ( l ) \mathbf{W}^{(l)} W(l)是第 l l l層的權重矩陣； c i c_i ci是歸一化常數； σ ( ⋅ ) \sigma(\cdot) σ(⋅)是激活函數。
vanilla GCN對目标節點自身在上一層的表示和目前層其鄰居節點的表示進行mean pooling，來對目标節點進行編碼。
（2）R-GCN
傳統的GNN隻考慮圖中node-wise的連通性，忽視了邊的标簽，例如KG中的關系。R-GCN通過使用特定關系的權重矩陣對不同的鄰居進行區分，解決了這一問題。節點的隐層表示計算如下：
其中 W 0 ( l ) \mathbf{W}^{(l)}_0 W0(l)是節點自身的權重矩陣； W r ( l ) \mathbf{W}^{(l)}_r Wr(l)是用于有關系 r r r的鄰居 N r ( i ) \mathcal{N}_r(i) Nr(i)的權重矩陣； R \mathcal{R} R是關系集合； c i , r c_{i,r} ci,r用于歸一化。
3.2 知識圖譜的實體對齊
将給定的KG記為 G = ( E , R , T ) \mathcal{G} = (\mathcal{E}, \mathcal{R}, \mathcal{T}) G=(E,R,T)，三個元素分别表示實體集合、關系集合以及三元組集合，其中 T = E × R × E \mathcal{T}=\mathcal{E}\times \mathcal{R}\times \mathcal{E} T=E×R×E。
針對兩個KG間的實體對齊問題，先給定兩個KG： G 1 = ( E 1 , R 1 , T 1 ) \mathcal{G}_1 = (\mathcal{E}_1, \mathcal{R}_1, \mathcal{T}_1) G1=(E1,R1,T1)和 G 2 = ( E 2 , R 2 , T 2 ) \mathcal{G}_2 = (\mathcal{E}_2, \mathcal{R}_2, \mathcal{T}_2) G2=(E2,R2,T2)，然後給定部分預對齊的實體對 A + = { ( i , j ) ∈ E 1 × E 2 ∣ i ≡ j } \mathcal{A}^{+} = {\{(i, j) \in \mathcal{E}_1\times \mathcal{E}_2 | i\equiv j}\} A+={(i,j)∈E1×E2∣i≡j}，其中 ≡ \equiv ≡表示對齊關系。這一任務的目的是通過實體的嵌入，找到剩餘實體的對齊方式。
3.3 用于實體對齊的GNN
有GCN-Align, GMNN, MuGNN, RDGNN, AVR-GCN。
GCN-Align和GMNN是基于vanilla GCN設計的；RDGCN引入了對偶的關系圖以增強vanilla GCN；AVG-GCN使用類似TransE的特定關系的translation操作，對R-GCN進行了擴充。
在聚合之前，使用關系向量從尾實體translate成頭實體的表示。
作者認為這樣針對特定關系的translation和R-GCN需要訓練的參數量太大，計算成本高。而且上述模型均沒有考慮到KG結構的非同構問題。
MuGNN考慮到了KG的結構不完全性，并提出了一個兩步的操作：1）基于規則的KG補全；2）用于實體對齊的多通道GNN。但是學習到的規則依賴于關系對齊以緩解模式的異質性問題。
（1）Isomorphic structures are beneficial
若實體的鄰域是同構的，GNN将會為實體學習到相同的表示。
作者發現在某些情況下，若兩實體具有同構的鄰域結構和僅部分預對齊的鄰居表示，GNN也能構捕獲到要對齊的其他鄰域的相似性。圖 2給出了一個例子：
為了簡化我們考慮單層的GCN。通過最小化預對齊的實體間的歐式距離，我們可以使得預對齊的實體有相同的表示，例如 h a ( 0 ) = h a ′ ( 0 ) , h b ( 0 ) = h b ′ ( 0 ) , h d ( 0 ) = h d ′ ( 0 ) \mathbf{h}^{(0)}_a = \mathbf{h}^{(0)}_{a^{'}}, \mathbf{h}^{(0)}_b = \mathbf{h}^{(0)}_{b^{'}}, \mathbf{h}^{(0)}_d = \mathbf{h}^{(0)}_{d^{'}} ha(0)=ha′(0),hb(0)=hb′(0),hd(0)=hd′(0)，在理想情況下也有 h a ( 1 ) = h a ′ ( 1 ) , h b ( 1 ) = h b ′ ( 1 ) , h d ( 1 ) = h d ′ ( 1 ) \mathbf{h}^{(1)}_a = \mathbf{h}^{(1)}_{a^{'}}, \mathbf{h}^{(1)}_b = \mathbf{h}^{(1)}_{b^{'}}, \mathbf{h}^{(1)}_d = \mathbf{h}^{(1)}_{d^{'}} ha(1)=ha′(1),hb(1)=hb′(1),hd(1)=hd′(1)。
通過基于mean-pooling的聚合，有 h b ( 1 ) = σ ( W ( 1 ) ( h b ( 0 ) + h a ( 0 ) + h c ( 0 ) ) / 3 ) \mathbf{h}^{(1)}_b = \sigma(\mathbf{W}^{(1)} (\mathbf{h}^{(0)}_b + \mathbf{h}^{(0)}_a + \mathbf{h}^{(0)}_c)/3 ) hb(1)=σ(W(1)(hb(0)+ha(0)+hc(0))/3)和 h b ′ ( 1 ) = σ ( W ( 1 ) ( h b ′ ( 0 ) + h a ′ ( 0 ) + h c ′ ( 0 ) ) / 3 ) \mathbf{h}^{(1)}_{b^{'}} = \sigma(\mathbf{W}^{(1)} (\mathbf{h}^{(0)}_{b^{'}} + \mathbf{h}^{(0)}_{a^{'}} + \mathbf{h}^{(0)}_{c^{'}})/3 ) hb′(1)=σ(W(1)(hb′(0)+ha′(0)+hc′(0))/3)， h c ( 0 ) = h c ′ ( 0 ) \mathbf{h}^{(0)}_c = \mathbf{h}^{(0)}_{c^{'}} hc(0)=hc′(0)。最終副本實體會用相同的表示。
這就表示着，當給定部分預對齊的鄰居時，實體間的對齊資訊可以在不同的GNN層中以及不同的同構圖中進行傳播。
但是對于不同KG間的實體對齊，由于模式的異質性，讓KG有同構的結構是不可能的。**圖 2(ii)**就給出了非同構圖結構的例子，其中 c c c和 c ′ c^{'} c′由于它們的鄰域結構不同，将會得到不同的表示。
（2）隻有結構還不夠
傳統的GNN不能識别出特殊的子圖結構，例如三角形圖。**圖 2(iii)**展示了一個簡單的例子。
此例中使用mean-pooling聚合，由于4個實體有同構的鄰居結構，應該得到$\mathbf{h}^{(1)}_a = \mathbf{h}{(1)}_{a{’}} = \mathbf{h}^{(1)}_b = \mathbf{h}{(1)}_{b{’}} $。
但是實際上， a a a和 b b b在給定一個關系後是不同的實體，我們需要将關系納入考慮。
盡管R-GCN在聚合函數中考慮到了關系，但它仍依賴于關系對齊，以用于識别相似的實體。
從（2）式可知，R-GCN需要為每個關系學習到一個權重矩陣。如果兩個KG的關系沒有預先對齊，則R-GCN中針對特定關系的聚合函數将不能傳播實體的對齊資訊。
（3）Compensation with distant neighborhood and relations
不同KG的模式異質性通常會使得副本實體的直接鄰居和遠距離鄰居相混合。
為了減少鄰域結構中非同構性的影響，作者引入遠距離鄰居的資訊，例如圖 2 iv所示：
要對齊的兩個實體 a a a和 a ′ a^{'} a′的一階鄰居是不同的，隻包含兩對副本（counterpart）實體對 ( b , b ′ ) , ( c , c ′ ) (b, b^{'}), (c, c^{'}) (b,b′),(c,c′)。 a a a的一階鄰居 d d d實際上是 a ′ a^{'} a′的遠距離鄰居 d ′ d^{'} d′， a a a的遠距離鄰居 e , f e, f e,f可與 a ′ a^{'} a′的一階鄰居 e ′ , f ′ e^{'}, f^{'} e′,f′相對齊。
是以可以很容易地想到，如果我們能在聚合鄰居資訊以得到 a a a的表示時考慮到 e , f e, f e,f，在聚合鄰居資訊以得到 a ′ a^{'} a′的表示時考慮到 d ′ d^{'} d′，則GNN能學習到 a , a ′ a, a^{'} a,a′更相似的表示。
當然，不是所有的遠距離鄰居都是有幫助的，是以聚合時要使用注意力機制有所選擇。
為了進一步增強AliNet的表示能力，還在不引入關系向量的前提下，考慮到了關系語義資訊。
4 知識圖譜對齊網絡
在AliNet中，通過使用門機制控制 k k k跳内鄰居資訊的聚合，來學習得到實體的表示。
接下來以 k = 2 k=2 k=2為例，即聚合一階鄰居和二階鄰居資訊，實際中可以擴充到多跳。AliNet的網絡結構如圖 3所示。
4.1 Gated Multi-hop Neighborhood Aggregation
聚合一階鄰居資訊使用vanilla GCN，進行式（1）所示的計算即可。
但是不能隻聚合一階鄰居的資訊。雖然有 L L L層的GCN可以捕獲到實體的 L − h o p L-hop L−hop的鄰居資訊，但這樣一層一層地傳播是低效的。
對于2-hop鄰居的聚合，為了避免原始的GCN聚合在逐層傳播中帶來的噪聲，我們引入了注意力機制。将給定實體的2-hop内的鄰居集合表示為 N 2 ( ⋅ ) \mathcal{N}_2(\cdot) N2(⋅)。在第 l l l層聚合實體 i i i的2-hop鄰居，得到隐層表示 h i , 2 ( l ) \mathbf{h}^{(l)}_{i, 2} hi,2(l)計算如下：
其中 α i j ( l ) \alpha^{(l)}_{ij} αij(l)是對于實體 i i i和其鄰居 j j j的可學習的注意力權重。下一小節将介紹注意力權重的計算。
受神經網絡中跳躍連接配接（skip connections）的啟發，作者提出使用門機制以結合1-hop鄰居和2-hop鄰居。實體 i i i在第 l l l層的隐層表示 h i ( l ) \mathbf{h}^{(l)}_i hi(l)計算如下：
其中 g ( h i , 2 ( l ) ) = σ ( M h i , 2 ( l ) + b ) g(\mathbf{h}^{(l)}_{i, 2}) = \sigma(\mathbf{M}\mathbf{h}^{(l)}_{i, 2} + \mathbf{b}) g(hi,2(l))=σ(Mhi,2(l)+b)就像一個用來控制1-hop鄰居和2-hop鄰居相結合的門（gate）； M , b \mathbf{M}, \mathbf{b} M,b分别是權重矩陣和偏置向量。
4.2 Attention for Distant Neighborhood
和實體距離較遠的鄰居數量和其一階鄰居數成指數關系。當然不是每個遠距離鄰居都對中心實體産生貢獻，是以對于2-hop的鄰居聚合，我們計算實體間的注意力權重，以強調那些有用的鄰居。
GAT對每個注意力函數中的實體應用了一個共享的線性變換。然而，KG中的中心實體和其鄰居可能是非常不同的，這樣的共享變換會對差別它們帶來負面影響。
是以，作者使用了兩個矩陣 M 1 ( l ) , M 2 ( l ) \mathbf{M}^{(l)}_1, \mathbf{M}^{(l)}_2 M1(l),M2(l)分别用于中心實體和其鄰居的線性變換。
在第 l l l層，實體 i , j i, j i,j間的注意力權重 c i j l ∈ R c^{l}_{ij}\in \mathbb{R} cijl∈R計算如下：
使用softmax函數歸一化注意力權重，以使得不同實體間可進行比較：
4.3 Contrastive Alignment Loss
最小化contrastive alignment loss使得對齊實體的表示距離小，非對齊的實體表示間的距離大：
其中 A − \mathcal{A}^- A−是随機替換預對齊的2個實體中的一個得到的負樣本。 [ ⋅ ] + = m a x ( 0 , ⋅ ) [\cdot]_+ = max(0, \cdot) [⋅]+=max(0,⋅)。我們希望負樣本實體的表示之間的距離大于 λ \lambda λ。
已有的方法通常将最後一層的輸出當做實體最終的表示，但是由于每一層都對傳播對齊資訊有所貢獻，是以，作者使用了所有層的隐層表示，于是有：
其中 ⊕ \oplus ⊕表示拼接操作， n o r m ( ⋅ ) norm(\cdot) norm(⋅)是 L 2 L_2 L2正則化，以減少人為增加向量範數的繁瑣優化過程。
4.4 Relation Semantics Modeling
KG提供了實體間的語義關聯，我們要将關系事實中的語義資訊合并到實體模組化中。
如第3節中讨論的那樣，為了進行實體對齊，R-GCN需要兩個KG的結構高度相似或者關系是對齊的。作者借鑒了TransE中的translation assumption。為了避免參數過多，作者沒有引入針對特定關系的嵌入。關系 r r r的表示 r \mathbf{r} r，可以通過和它相關的實體嵌入得到：
其中 T r \mathcal{T}_r Tr是對于關系 r r r的subject-object實體對。
然後最小化如下的關系損失，其中 R \mathcal{R} R是兩個KG的關系的總集合。
4.5 實作細節
（1）目标函數
AliNet最終的目标函數是contrastive alignment loss和relation loss的組合，目的是将關系語義資訊整合到圖結構中：
（2）向k-hop鄰居的泛化
令 ρ 1 ( h i , 1 ( l ) , h i , 2 ( l ) ) \rho_1(\mathbf{h}^{(l)}_{i, 1}, \mathbf{h}^{(l)}_{i, 2}) ρ1(hi,1(l),hi,2(l))為1-hop和2-hop鄰居的結合，如式（4）。可使用 k − 1 k-1 k−1個門函數來遞歸地結合資訊：
（3）鄰居的增加
提出的gated multihop鄰居聚合以端到端的方式擴充了實體的直接鄰居。為了進一步實作此思想，作者提出了一個啟發式的方法在預對齊的實體間添加邊。特别地，如果 K G 1 KG_1 KG1中的兩個實體 i , j i, j i,j有一個邊，但是它們對應的實體 i ′ , j ′ i^{'}, j^{'} i′,j′在 K G 2 KG_2 KG2中沒有邊，我們就添加一個邊連接配接着兩個實體。目的是希望通過添加這樣的平衡邊，以緩解非同構的問題。
（4）對齊預測
一旦訓練AliNet，我們就可以基于cross-KG範圍内實體表示之間的最近鄰搜尋來預測實體對齊。
給定一個 K G 1 KG_1 KG1中要被對齊的源實體 i i i，它在 K G 2 KG_2 KG2中對應的副本實體為 i ′ = a r g m i n j ∈ E 2 π ( h i , h j ) i^{'} = argmin_{j \in \mathcal{E}_2} \pi(\mathbf{h}_i, \mathbf{h}_j) i′=argminj∈E2π(hi,hj)。其中 π ( ) \pi() π()是距離度量，例如歐式距離。我們使用結合的表示來衡量實體嵌入的距離。
5 實驗
1、資料集
2、對比方法
（1）最近的基于嵌入的實體對齊模型
MTransE, IPTransE, JAPE, AlignE, GCN-Align, SEA, RSN, MuGNN.
最近的一些基于GNN的模型，比如GMNN和RDGCN将實體的surface資訊納入考慮，由于本文隻依賴于結構的資訊，是以不和這些方法進行比較。
（2）AliNet的變形
- AliNet (w/o rel. loss)：不優化關系損失；
- AliNet (w/o rel. loss & augment.)：不使用關系損失和鄰居的增加。
（3）使用一些KG嵌入模型和GNN的變形作為baselines
1）KG嵌入模型：TransE, ConvE, RotatE
2）GNN：GCN, GAT, R-GCN
3、實驗結果
實體對齊實驗結果如表 1所示，AliNet在[email protected]和MRR上超越state-of-the-art。
6 總結
本文提出AliNet用于處理實體對齊任務，目的是緩解副本實體的鄰域結構不同構的問題。
AliNet通過在每一層使用門機制，捕獲到了多跳範圍内的鄰居資訊。還使用了注意力機制用于聚合多跳的鄰居資訊以減少噪聲。作者還提出了關系損失以增強AliNet的表達能力。
未來工作：将其他模态的副資訊（side information）納入考慮。
本文解決的是實體對齊問題，提出了AliNet。
（1）本文針對的問題
由于不同的KG模式不同，而且均有不完全性，要對齊的實體的鄰居通常不是同構的，是以使用GNN會為中心實體生成不同的嵌入表示，是以無法實作實體對齊。
（2）提出的方法
作者認為即使不同KG中副本實體間的鄰域不是同構的，但和實體有關的語義資訊會在一定範圍内的鄰域中出現。例如在某個KG中中心實體的一階鄰居，可能是另一個KG中相對應的實體的二階鄰居。
基于上述思想，作者将一階鄰居和遠距離鄰居的資訊聚合起來。以2-hop内的鄰居為例（即遠距離鄰居指的是二階鄰居），對AliNet的pipeline進行回顧：
首先，使用GCN的公式得到聚合一階鄰居後的隐層表示，然後再對2-hop内所有的鄰居資訊進行聚合。注意與聚合一階鄰居不同的是，聚合2-hop内所有鄰居時為每個鄰居都配置設定了一個注意力權重，以衡量不同鄰居的重要性，減少噪聲。
接着使用門機制，對上述操作得到的兩個隐層表示進行聚合，得到中心節點在該層網絡中的最終的隐層表示。
需要注意的是，并不是直接使用網絡最後一層輸出的隐層表示作為KG中實體的最終表示，而是對所有層的隐層表示都進行了利用，得到KG中實體最終的表示。
在損失方面還考慮到了KG中關系的語義資訊，引入了關系損失。
（3）引入注意力機制與GAT相比的不同
GAT在計算注意力權重時，對所有的實體共享一個線性變換。作者考慮到KG中中心實體和鄰居有着很大的不同，于是對中心實體和其鄰居使用了兩個不同的線性變換。
（4）思考
在引入關系損失的部分，關系的嵌入就是通過三元組中兩個實體的嵌入相減得到的（等式（9）），目标函數（等式（10））中還要最小化兩個實體的嵌入之差再減去關系的嵌入，這裡總感覺有點問題。但是實驗結果顯示優化關系損失後效果也确實提升了。
k-hop一般指的是k階子圖，也就是和中心節點距離小于等于k的鄰居節點們組成的子圖。對1-hop的鄰居進行了聚合，又對2-hop的鄰居進行聚合，是不是說一階鄰居被計算了兩次，感覺有點資訊的備援。沒看過代碼，可能是我想多了。
不足：沒有利用到三元組的語義資訊，生成的表示缺少區分性。IJCAI2020有一篇文章以此為動機，已經超越了此模型。
這裡的提到的文章忘記出處了[捂臉]，這句話應該是後來編輯上去的，忘記留下什麼記錄了，目前絲毫都想不起來了，甚至有點懷疑是不是編輯的時候搞錯文章了。看到的朋友先忽略吧，或者知道些什麼的朋友也歡迎評論留言。
參考文獻
[1] Morris, C.; Ritzert, M.; Fey, M.; Hamilton, W. L.; Lenssen, J. E.; Rattan, G.; and Grohe, M. 2019. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 4602–4609.