k階采樣和圖注意力網(wǎng)絡的知識圖譜表示模型

劉文杰，姚俊飛，陳 亮

1.南京信息工程大學 計算機學院，南京 210044

2.南京信息工程大學 數(shù)字取證教育部工程研究中心，南京 210044

知識圖譜可以收集世界中廣泛的知識，在知識問答[1]、關系預測[2]、智能搜索[3]等人工智能領域得到廣泛應用。但是，知識圖譜的符號化表示產(chǎn)生大量稀疏數(shù)據(jù)，導致計算效率低下。因此，許多研究者提出了基于深度學習的知識圖譜表示學習（KGE）模型[4]來減少稀疏數(shù)據(jù)，提高計算效率。知識圖譜表示學習的目的是將三元組映射到連續(xù)的低維向量空間，這對知識圖譜的推理、補全和應用具有重要意義[5]。

TransE[6]是一個典型的平移距離模型，用于對給定的有效三元組施加平移距離約束h+r≈t。該約束保證了頭實體和尾實體的向量表示可以用它們對應關系來解釋。而基于路徑的模型PTransE[7]通過建模頭尾實體間的關系路徑來解決TransE只考慮直接關系的局限性。與平移距離模型不同，語義匹配模型RESCAL[8]通過對應關系相關聯(lián)的矩陣來捕獲頭尾實體之間的特征交互。同時卷積神經(jīng)網(wǎng)絡由于卷積運算的高效率和有效性，在知識圖譜表示學習中表現(xiàn)出良好的性能而受到關注。其中，ConvE[9]將頭實體和關系拼接后的一維表示向量重構為二維矩陣，在計算事實得分時對矩陣進行二維卷積。

考慮到三元組中的實體不僅受到三元組本身的約束，還受到與之相連的鄰居實體的約束。因此許多可以聚合鄰居信息的基于圖神經(jīng)網(wǎng)絡（GNN）的模型被提出。R-GCN[10]是一個關系圖編碼器，它聚合了不同關系類型的鄰域實體特征。CompGCN[11]使用圖卷積網(wǎng)絡（GCN）[12]作為編碼器，并利用各種組合操作來學習實體和關系的向量表示。受到圖注意力網(wǎng)絡（GAT）[13]的啟發(fā)，KBAT[14]通過編碼器-解碼器架構在擴展圖注意力機制的基礎上學習實體向量表示。然而，這些模型僅依賴于中心實體的直接鄰居（一階鄰居），不能全面地捕捉高階鄰居的信息。如圖1所示，實線和虛線分別是直接關系和隱藏關系，黑色圓圈和灰色圓圈是間接相關的實體。當使用基于圖神經(jīng)網(wǎng)絡（GNN）的模型時，中心實體Renate只能直接從一階鄰居（Fishin，Justin，Mike）獲取信息。但二階實體Kim與Renate密切相關，因此不能直接融入Kim的信息。

圖1 局部關系子圖Fig.1 Illustration of local relational subgraph

針對以上問題，本文提出一種新穎的知識圖譜表示模型，該模型捕獲剪枝子圖中高階實體的特征來提高實體向量表示的性能。首先，通過k階采樣算法聚集剪枝子圖中的k階鄰域來得到中心實體的鄰居特征；然后利用圖注意力網(wǎng)絡來計算中心實體與其鄰居之間的注意力值。最后，使用ConvKB[15]來捕獲實體之間的全局關系和過渡特征。

本文的主要貢獻如下：

（1）通過k階采樣算法來獲取中心實體的剪枝子圖中的鄰居特征。

（2）基于圖注意力網(wǎng)絡，中心實體可以融合k階鄰域特征來提高其表示能力，同時使用ConvKB作為解碼器來分析三元組的全局特征，進一步實現(xiàn)實體和關系的精確表示。

（3）鏈接預測的實驗結果表明，提出的模型比目前最先進的模型更有效。

1 相關工作

知識圖譜表示通過向量化實現(xiàn)了實體和關系語義信息的準確描述。近年來，各種知識圖譜表示學習模型被提出。TransE[6]中的平移操作被定義為三元組中的頭實體通過關系連接尾實體，然后用一個評分函數(shù)來衡量每個三元組的合理性。然而，TransE在面對1-to-N、Nto-1和N-to-N關系時存在問題。因此，TransR[16]、TransD[17]和TransH[18]通過不同的實體投影策略來施加平移距離約束解決這些問題。同時這些模型只考慮到實體間的直接關系，忽略了實體間的關系路徑，所以基于路徑的表示學習模型被提出。PTransE[7]通過建模實體間的關系路徑來進行特征表示學習。RSNs[19]采用偏置隨機游走對期望路徑進行采樣，采用循環(huán)神經(jīng)網(wǎng)絡和殘差學習對其建模，由此來捕獲實體的長期關系依賴。

與平移距離模型相比，語義匹配模型更注重挖掘向量化實體和關系的潛在語義。RESCAL[8]通過對應于特定關系的矩陣來捕獲實體之間的交互。為了減少RESCAL中關系參數(shù)的數(shù)量，DistMul[20]通過將RESCAL的關系矩陣限制為對角矩陣來簡化它。為了建模非對稱關系，ComplEx[21]將DistMult擴展到復雜空間。HolE[22]使用循環(huán)相關操作來增加頭部和尾部實體之間的相互作用。此外，受卷積運算的啟發(fā)，ConvE[9]利用卷積層從頭部實體和關系組成的特征矩陣中提取特征。為了更加關注三元組的整體特征，ConvKB[15]將每個三元組表示為由三個特征向量組成的矩陣形式，然后使用多個卷積核生成不同的特征向量。

近年來，圖神經(jīng)網(wǎng)絡在知識圖譜學習中的應用引起了人們的興趣。R-GCN[10]是一種迭代編碼鄰域實體特征和自環(huán)表示的關系圖編碼器。CompGCN[11]利用了來自KGE技術的各種實體-關系組合操作，并根據(jù)關系的數(shù)量進行分級。當聚合來自不同鄰居實體的信息時，SACN[23]根據(jù)不同類型的關系分配不同的自學習權重。RELATT[24]利用兩個實體之間的關系來學習相鄰實體的重要性。KBAT[14]通過三元組注意力機制來捕捉實體和關系的特征。在KBAT的基礎上，R-GGAT[25]通過其多注意力機制選擇和過濾鄰域信息來學習實體嵌入。RGHAT[26]根據(jù)關系級注意力和實體級注意力，進一步區(qū)分相鄰實體的重要性。

然而，上述基于圖神經(jīng)網(wǎng)絡的模型僅聚合來自一階鄰居實體的信息，高階實體信息仍然大部分未使用，這無法使實體融合更多的隱藏信息。因此，提出了一種基于k階采樣算法和圖注意力網(wǎng)絡的KGE模型，實體利用k階采樣算法和圖注意力網(wǎng)絡來聚合剪枝子圖中高階鄰居的信息。

2 本文模型

在本章中，首先介紹本文其余部分使用的符號，然后概述本文的模型。最后，對所提出的模型進行了詳細說明。

2.1 符號定義

本文使用的主要符號定義及解釋如表1所示。

表1 符號定義及解釋Table 1 Notations and explanations

2.2 模型框架

模型的整體框架（編碼器-解碼器）如圖2所示，綠色圓圈代表實體的初始向量表示，黃色圓圈代表關系的初始向量表示，紫色圓圈代表最終實體向量表示，橙色圓圈代表最終關系向量表示。首先，使用TransE，初始化實體組向量表示E=[h1,h2,…,hn]，和關系組向量表示R=[r1,r2,…,rm]。然后，將知識圖譜輸入到Encoder中。其中，k階采樣算法用于獲得剪枝子圖中心實體的鄰居特征，其次使用圖注意力網(wǎng)絡來聚合中心實體的鄰居特征。此外，線性變換對關系R進行特征向量的更新。最后，ConvKB用作解碼器以捕獲三元組中實體和關系之間的全局特征。

圖2 編碼器-解碼器的端到端架構Fig.2 End-to-end architecture of Encoder-Decoder

2.3 編碼器

2.3.1 k階采樣算法

除了考慮所有一階實體對中心實體的影響外，還需要考慮高階實體。然而，高階鄰域實體的重要性隨著與中心實體的距離的增加而衰減。因此，k階采樣算法首先從中心實體的二階鄰域出發(fā)，隨機采樣高階實體形成剪枝子圖，然后再將剪枝子圖中的高階特征聚集起來形成該中心實體的鄰居特征。在算法1中描述了如何獲取中心實體的鄰居特征。

算法1k階采樣算法

考慮到知識圖譜中信息是由頭部實體向尾部實體傳播的，所以根據(jù)信息傳播方向相反的實體進行采樣形成剪枝子圖。如圖3所示，紅色圓圈代表中心實體，橙色圓圈代表一階實體，藍色圓圈代表二階采樣實體，紫色圓圈代表三階采樣實體，綠色圓圈代表第k階采樣實體。保留所有一階實體，并隨機采樣高階實體。采樣系數(shù)設為b，因此一階采樣Ni，二階采樣b個實體，三階采樣2b個實體，k階采樣(k-1)b個實體。如果Setkc中的實體數(shù)量NSetkc小于等于kb，則全部采樣。反之，則需要從Setkc中隨機抽取實體。為了防止在當前階的采樣實體和形成的剪枝子圖之間重復采樣，需要進行冗余處理，具體公式如下所示：

圖3 剪枝子圖的形成過程Fig.3 Process of forming pruned subgraph

因此經(jīng)過k階采樣后，中心實體ei的剪枝子圖S(i)被定義為：

由于剪枝子圖中實體的重要性隨著與中心實體的距離的增加而衰減，因此為每一階實體定義一個從0到1的折扣參數(shù)ρ。如圖4所示：在生成中心實體的某個鄰居實體j的特征向量時，需要將實體j的一階鄰居相加進行ρ2的打折，二階進行ρ3的打折，(k-1)階進行ρk的打折。鄰居實體特征fj定義如式（3）所示：

圖4 中心實體的某個鄰居特征向量形成過程Fig.4 Process of forming certain neighbor feature vector of central entity

其中，N(k-1)j表示實體j的一階或者高階鄰居，表示實體j的一階或者高階鄰居的特征向量，Wk表示每一階的線性變換矩陣。

2.3.2 基于圖注意力網(wǎng)絡的實體向量表示

如圖5所示，為了學習實體ei新的向量表示，必須考慮其鄰居的所有特征。每個鄰居特征的重要性用注意力值di,j表示，具體如下：

圖5 圖注意力機制Fig.5 Illustration of graph attention mechanism

其中，W1和a分別表示可學習的權重矩陣和單層前饋反饋網(wǎng)絡。最后使用Softmax函數(shù)對所有鄰居實體的注意力值做歸一化處理，歸一化后的注意力權重即為最后的注意力系數(shù)，如式（5）所示：

實體ei新的向量表示是由注意力系數(shù)進行加權求和得到，其聚合公式為：

其中，σ是激活函數(shù)，同時為了學習鄰居實體的更多特征信息，采用多頭注意力機制以獲得不同特征進行集成。首先通過使用M個獨立的注意力機制得到向量表示，然后取平均值。因此，該過程可以寫成：

為了學習新的關系向量表示，本文對初始的關系向量表示R執(zhí)行線性變換，WR∈?T×T′為權重矩陣，其中T代表轉換前的向量維度，T'代表轉換后的維度。為簡單起見，上述操作寫成：

然而在學習新的實體向量表示時，實體會丟失初始的結構特征信息。所以在最后得到的實體表示中添加經(jīng)過線性變換的初始實體向量來解決，如式（9）所示：

2.3.3 評分函數(shù)

其中，最大間隔參數(shù)γ表示在正確三元組和錯誤三元組之間的間隔修正。S是有效三元組的集合，S'表示無效三元組的集合。

2.4 解碼器

使用ConvKB作為解碼器，能夠根據(jù)編碼器編碼的實體特征來實現(xiàn)實體和關系的精確表示。如圖6所示，卷積層的目的是在每個維度上分析三元組的全局表示特征，以達到實體和關系的交互。具有多個特征映射的打分函數(shù)可以寫成：

圖6 解碼器的整體結構Fig.6 Overall structure of Decoder

其中，ωm表示第m個卷積核，Ω是使用的卷積核數(shù)量，?是一個卷積運算符，表示一個串聯(lián)運算符，W2∈?Ωk×1表示一個用來計算三元組最終得分的線性變換矩陣。通過使用soft-margin損失函數(shù)對解碼器進行訓練：

3 實驗

3.1 數(shù)據(jù)集

實驗采用了以下標準數(shù)據(jù)集。數(shù)據(jù)集的統(tǒng)計信息如表2所示。

表2 數(shù)據(jù)集的統(tǒng)計信息Table 2 Dataset statistics

（1）WN18RR[9]是從數(shù)據(jù)集WN18[6]中提取的，它包含11種關系類型和40 943個實體，是通過排除驗證集和測試集中出現(xiàn)的逆關系生成的。

（2）FB15k-237[27]由FB15k[28]衍生而來，F(xiàn)B15k-237由演員、電影、地點等三元組事實組成。與FB15k相比，F(xiàn)B15k-237去掉了冗余三元組，導致實體和關系表示學習比較困難。

（3）NELL-995[29]來源于NELL[30]，提供了農(nóng)產(chǎn)品、動物、書籍等三元組事實。

（4）Kinship[31]是一個關系型數(shù)據(jù)集，它匯集了兩個具有相同結構家族中的24個唯一名稱。

3.2 對比模型

下面的基線模型用于比較本文模型在上述標準數(shù)據(jù)集上鏈接預測任務的性能。

（1）TransE[6]使得頭部實體向量表示和關系向量表示的總和盡可能接近尾部實體向量表示。

（2）PTransE[7]在TransE的基礎之上擴展了頭尾實體間的關系路徑信息。

（3）RSNs[19]通過一種跳躍機制來加以區(qū)分路徑中的實體和關系，可以有效地捕獲知識圖譜中實體的長期關系依賴。

（4）DisMult[20]是一個語義匹配模型，旨在通過關系矩陣捕獲頭尾實體之間的交互。

（5）ComplEx[21]是將實體和關系的向量嵌入到復數(shù)空間中。

（6）ConvE[9]使用二維卷積操作來學習實體和關系的向量表示。

（7）R-GCN[10]通過為每個關系類型定義關系特定的權重矩陣來學習實體向量表示。

（8）KBAT[14]用于捕獲任何給定實體的鄰域中的實體和關系特征。

（9）CompGCN[11]通過考慮多個關系信息來學習實體和關系的向量表示。

3.3 實驗設置和評估指標

編碼器和解碼器分別進行訓練。首先訓練編碼器獲得知識圖譜中實體和關系的最佳向量表示，然后最佳的向量表示被用作解碼器的輸入，通過訓練解碼器來正確分析三元組的全局表示特征。編碼器和解碼器定義的主要超參數(shù)如表3所示。

表3 編碼器和解碼器的超參數(shù)Table 3 Training hyper-parameters of encoder and decoder for evaluated datasets

鏈接預測是對給定的一個正確三元組(ei,ro,ej)，在頭實體ei或尾實體ej缺失的情況下，通過在原實體集中隨機選擇頭尾實體補全。對于缺失的位置，模型計算出重組三元組的得分進行升序排序，以致正確三元組的排名會被記錄下來。

平均倒數(shù)排名MRR和命中率Hits@N是知識圖譜中常用的鏈接預測任務評價指標，如式（13）和式（14）所示。通過采用TransE[6]中的“Filter”方式來測試頭或尾實體的排名。MRR值大表明預測結果越好，Hits@N表示在N=1,3,10的情況下，頭尾實體正確預測進入前N名的比例。

其中，Tt是測試集的大小，I(?)是指示函數(shù)，而rankei和rankej表示預測過程中頭部實體ei和尾部實體ej的排名。

3.4 三元組分類結果和分析

三元組分類是一個二分類任務，用于判斷給定的三元組是否符合客觀事實。為保證測試數(shù)據(jù)的合理性，在生成負樣本三元組時，對所需替換的實體或者關系進行一定的限制來生成負樣本，使得負樣本難以區(qū)分。在分類過程中，通過比較三元組得分函數(shù)和給定閾值δ的大小來確定分類效果，如果得分比閾值低，則判定為正確三元組，反之為錯誤三元組。

三元組分類結果如表4所示，在WN18RR、FB15k-237、NELL-99這三個知識圖譜上的分類準確度更優(yōu)于其他模型，這說明使用k采樣算法和圖注意力網(wǎng)絡得到的向量能夠更有效地表示實體，使得實體的語義信息增強。然而在Kinship上的準確度低于KBAT和CompGCN，這是因為Kinship中實體的結構大都屬于稠密型，從一階鄰居融入的信息本來就很多，所以在融入k階實體信息時，會導致實體之間的向量表示有一定的相似性。

表4 三元組分類的評估結果Table 4 Evaluation results on triple classification 單位：%

3.5 鏈接預測結果和分析

表5和表6為數(shù)據(jù)集上的鏈接預測結果。結果清楚地表明，本文提出的模型在FB15k-237的四個指標、WN18RR的兩個指標、NELL-995的四個指標和Kinship的一個指標上顯著優(yōu)于基線結果。

表5 WN18RR和FB15k-237測試集的實驗結果Table 5 Experimental results on WN18RR and FB15k-237 test sets

表6 NELL-995和Kinship測試集的實驗結果Table 6 Experimental results on NELL-995 and Kinship test sets

在此，對實驗結果作了一些分析。

（1）在WN18RR上，模型在Hits@3和Hits@10上獲得了最好的得分。與KBAT相比，Hit@3從48.3%提高到48.8%，Hits@10從58.1%提高到59.2%。在Kinship上，模型在Hits@3上得分最高，但在其他3個指標MRR、Hits@1和Hits@10上不如KBAT。這是因為Kinship擁有104個實體和25個關系，其大部分實體的結構是稠密的，這將導致實體的向量表示有一定相似，從而鏈接預測的準確率下降。

（2）模型在FB15k-237和NELL-995上的所有指標都明顯優(yōu)于競爭對手。特別是，與KBAT相比，Hit@3在NELL-995上從56.4%提高到60.5%，Hits@1在NELL-995上從44.7%提高到49.2%。可以看出，模型可以有效地從高階實體中捕獲隱藏信息來增強實體的表示。

（3）模型在四個數(shù)據(jù)集上的評價指標基本都優(yōu)于基于路徑的表示模型。雖然基于路徑的表示模型突破了單個三元組的局限性，實現(xiàn)實體的長期關系依賴，但是本質上是捕獲的關系序列信息，并沒有捕獲更加豐富的高階實體信息。

（4）基于GCN的模型和基于GAT的模型通常比其他基線取得更好的結果。例如，KBAT和CompGCN在FB15k-237和NELL-995數(shù)據(jù)集上都有較好的結果。由于GCN的過平滑性，基于GAT的模型（KBAT和提出的模型）在鏈接預測方面通常比基于GCN的模型（RGCN和CompGCN）更有效。此外，可以看出提出的模型性能明顯優(yōu)于KBAT，清楚地證明了k階采樣算法和圖注意力網(wǎng)絡結合的有效性。

同時本文進一步討論階數(shù)k和采樣系數(shù)b的變化對模型效率的影響。為了獲得k和b對模型效率的影響，選取命中率在NELL-995數(shù)據(jù)集上進行實驗分析。首先，分析了k對模型效率的影響。在實驗中，選取k=1，2，…，6，采樣系數(shù)b設為5，實驗的命中率用公式（14）計算，結果如圖7（a）所示?？梢钥闯?，在本實驗中，鄰域的最優(yōu)階數(shù)k為4，也就是說低階(k<4)鄰域和高階(k>4)鄰域的效率都降低了。然后討論了采樣系數(shù)b的不同對模型命中率的影響。實驗中，k為4，b分別為3，4，…，9，實驗結果如圖7（b）所示。顯然，最佳性能是在b=5時實現(xiàn)的（即Hits@1為49.2%，Hits@3為60.5%，Hits@10為70.3%）。綜上所述，k和b對模型的效率有很大的影響，如何針對不同的數(shù)據(jù)集來選擇這兩個參數(shù)是模型成功的關鍵。

圖7 k階鄰域的詳細研究Fig.7 Detailed studies ofk-order neighborhood

4 結束語

本文提出了一種基于k階采樣算法和圖注意力網(wǎng)絡的KGE模型。通過引入k階采樣算法、圖注意力網(wǎng)絡和ConvKB，模型可以增強實體的向量表示來提高知識圖譜中推理和預測任務的準確性。實驗結果表明，該模型在鏈接預測方面的性能優(yōu)于現(xiàn)有模型。

需要注意的是，模型僅適用于知識圖譜中結構稀疏的實體。對于知識圖譜中結構稠密的實體，由于實體的鄰居數(shù)量較多，如果使用k階采樣算法來獲取鄰居的特征，會導致計算量的急劇增加以及實體的向量表示有一定的相似性。另外，k和b的選擇會顯著影響本文模型的命中率，所以如何根據(jù)知識圖譜中實體的稀疏性、稠密性選擇k和b，以及讓模型學會動態(tài)選擇實體該關注哪幾階的信息，這些都是未來的工作之一。