結合平移關系嵌入和CNN的知識圖譜補全

陳新元，謝晟祎，陳慶強，劉 羽

(1. 閩江學院 計算機與控制工程學院，福建 福州 350100；2. 福州墨爾本理工職業學院 信息工程系，福建 福州 350100；3. 福建農業職業技術學院 實驗實訓中心，福建 福州 350300；4. 福建工程學院 信息科學與工程學院，福建 福州 350100；5. 福州墨爾本理工職業學院 現代教育技術中心，福建 福州 350100)

0 引言

知識庫(KB)[1]是有效事實三元組的集合，三元組由頭實體、關系和尾實體組成，表示為(h，r，t)，h和t分別對應頭、尾實體，r表示頭、尾實體之間的關系。知識庫廣泛應用于語義搜索引擎[2]、問題解答技術[3-4]、專家系統和社交網絡分析等領域[5]。然而，現有知識庫存在大量缺失事實，即三元組不完整，缺少實體或關系[6]。

知識圖譜補全[7]旨在解決上述問題，通過提取局部模式[8]或語義特征，用已知信息生成新的有效事實，經典模型如TransE[9]和ConvE[10]。實體之間的關系依照關系基數，可以分為一對一(1-to-1)、多對一(M-to-1)、一對多(1-to-M)和多對多(M-to-M)四種關系類別，簡單方法在1-to-1關系上往往就可獲得較好的建模結果，例如基于層次結構的概念樹和詞嵌入空間中矢量表示思想而設計的TransE模型；而對M-to-1，1-to-M和M-to-M等復雜關系，目前尚無統一的建模標準。

近期許多嵌入模型的研究通過貝葉斯擴展或張量/矩陣分解等方法[11]增強算法框架的表達能力，然而，表達能力的提高往往意味著更高的建模復雜度和計算開銷，并帶來一些諸如欠擬合(多個局部最小值)或過擬合等新問題。因此，部分算法，如TransH[12]嘗試在復雜性、性能和可伸縮性之間取得平衡，并在較大規模數據集上測試[13]；這類算法常使用不可信度評分衡量三元組的有效性。

本文提出的ATREC算法借鑒了TransE的向量平移思路，即若三元組(h，r，t)成立，其元素向量化的表示應符合： 將關系r嵌入頭實體h的結果接近尾實體t。為保留關系特征，在將原始三元組表示為k維矩陣的基礎上，將關系向量嵌入到頭實體和尾實體中，與原始表示拼接，生成6列k維的關系融合矩陣，使用參數較少的CNN提取特征并評分以驗證三元組有效性。將該算法在四個主流基準數據集上進行鏈路預測和三元組分類測試，并與其他主流算法進行比較。

本文第1節討論相關工作，第2節介紹ATREC算法，第3節介紹實驗并分析結果，第4節總結并提出未來的工作方向。

1 相關工作

基于矩陣嵌入的SE模型[14]使用以關系矩陣和頭、尾實體向量點積為參數的距離函數判定三元組的合理性，即若三元組成立，則在關系確定的子空間中，其頭部映射應接近尾部向量。然而矩陣投影的計算成本較高，模型訓練中常發生欠擬合或過擬合現象。

若確定范數約束，并舍棄相關度低的參數以展開歐幾里德距離公式，則神經張量模型(NTN)[15-16]可看作是TransE的特例。該模型使用雙線性張量算子，表達能力強，但參數更多，復雜度同樣較高。

TransE將標記邊對應的關系映射到嵌入向量，即若三元組成立，則公式vh+vr≈vt也成立，其中vh,vr,vt是實體和關系的嵌入向量。算法使用不相似度量d=||vh+vr-vt||p，計算取L1或L2范數時三元組的能量得分，在此基礎上設計基于間隔排序標準(margin-based ranking criterion)的損失函數，在迭代過程中不斷更新相關參數，優化模型性能；三元組的全局特征在向量同一維度的條目中得以保持。該算法結構簡單，效率較高，但也存在不足，如對復雜關系三元組的學習能力有限。

TransD[19]將投影矩陣分解為向量，從而簡化計算；TranSparse[20]則使用稀疏矩陣解決頭、尾實體分布不均衡的問題，同時降低計算開銷；但該類模型尚未形成統一標準。

此外，DistMult[21]和ComplEx[22]使用三重積計算三元組得分；Nguyen等[23]和Toutanova等[24]引入了近鄰混合/關系路徑，通過加權計算或矩陣乘法獲取上下文信息，優化模型的關系預測性能。也有研究使用了文本信息輔助等方法[25-31]。

近年來，在自然語言處理(NLP)[32]領域，最初設計用于計算機視覺的CNN大放光彩，因其參數和計算開銷遠少于全連接神經網絡。ConvE是最早將CNN應用于鏈路預測的算法，將vh、vr轉化并拼接后，作為卷積層輸入；過濾器提取特征映射張量后，將其向量化并與vt計算點積，得到三元組得分。ConvE提取局部特征的效率較高，但同一維度上的全局特征可能會丟失，影響模型補全性能。

ConvKB[33]使用k維嵌入統一表示所有實體和關系，即每個三元組都可以看作是一個k×3的矩陣；卷積層中尺寸為1×3的過濾器對矩陣每一行進行遍歷，提取全局關系，流程類似ConvE。然而，ConvKB仍然將實體和關系視為獨立的元素，忽略其緊密聯系，三元組完整性可能受損，導致關系隔離和特征丟失。

2 ATREC算法

知識圖譜中，三元組(h,r,t)表示包含語義信息的事實，其中h,t∈E，r∈P,E和P分別指代實體和關系的集合。模型設計的目的是找到合理的評分函數，判定三元組的合理性或不可信度。參考TransE設計，本文使用k表示實體和關系嵌入的維數，故原始三元組可以表示為矩陣A=[vh,vr,vt]∈k×3,Ai,:∈1×3表示A的第i行。本文創新點在于將關系特征集成到頭、尾實體的向量表示中，從而保證三元組的完整性，稱為關系融合(relation integration)，如式(1)所示。

其中，v′h是關系融合后的頭實體，vh是原始頭實體的k維向量表示，“·”表示點積運算，w1表示通過前饋神經網絡學習獲得的權重參數，vr為原始的k維關系，b1為偏置系數。尾實體計算方法相同。令v′r=v′t-v′h。 設計思路是將關系特征融入頭/尾實體中，從而使對應不同關系的同一實體的不同屬性得到完整表達，提高對具有復雜重數關系的三元組的分析能力。

TextCNN[32]使用六元組表示卷積網絡的輸入語句，參考其思路，本文將矩陣A擴展為6列k維矩陣A′，將原始三元組表示和關系融合后的三元組表示組合作為卷積層輸入，即A′=[vh,vr,vt,v′h,v′r,v′t]∈k×6

過濾器的尺寸和步長對特征提取和計算開銷影響較大，本文使用ω∈1×3提取同一維度嵌入向量的特征，步長為3，避免抽取無意義的局部特征，使用多個卷積核遍歷矩陣A′。 這樣在分別提取原始三元組和關系融合三元組的局部特征的同時，盡可能保留三元組同一維度的整體特征和語義相關性。特征映射vi表示如式(2)所示，g為非線性激活函數(如ReLU或sigmoid)，b2為偏置系數。令Ω和τ分別表示ω的卷積核集合和核數，即τ=|Ω|。 卷積層處理后，特征映射v=[v1,v2,…,vk]的規?？杀硎緸閗×2(×τ)。

評分函數f定義如式(3)所示，“*”表示卷積運算。非線性函數的參數通過關系融合和平移轉換得到。流程框架如圖1所示。

具體步驟如算法1所示，時間復雜度為O(nek+nrk)，接近TransE，在數據量較大時遠低于SE的O(nek+2nrk2)。

圖1 ATREC的卷積流程

算法1: ATREC的優化過程Input: KB g, entity set E, relation set P, embedding dimension k, batch size b, regularizer λ, pre-trained embeddings of en-tities and relations by TransE //輸入: 數據集和相關參數1Initialize variables for each vh,vr,vt //初始化實體/關系表示//Using a truncated normal distribution with init_filter_normal=True while using [0.1, 0.1, -0.1] with init_filter_normal = False2For each ω initialize with init_filter_normal //對應所有卷積核3 w←uniform(- 6 k×τ+1, 6 k×τ+1)//初始化權重4Fori=1, 2, …, n,n denotes the upper limit of epochs//對應每輪訓練的操作5 Forj=1, 2, …, gb+1//對應每批(batch)訓練的操作6 Batch←Sample(g,b)//從數據集中采樣該批的有效三元組7 IBatch=? //設置對應無效三元組集合為空 “I” short for invalid8 For each triplet in Batch//對應該批的所有有效三元組9 (h',r,t')←ISample() // 逐一生成無效樣本10 IBatch←IBatch∪(h',r,t')//將無效樣本加入該批的無效三元組集合11 Batch←Batch∪IBatch//合并有效三元組集合和無效三元組集合12 For each triplet∈Batch//對應該批的所有三元組13 fh,r,t =concatg(vh,vr,vt,v'h,v'r,v't *Ω) ·w2//逐一計分14 compute l(h,r,t) //取有效/無效系數15 LBatch=∑(h,r,t)∈Batchlog (1+exp (l(h,r,t)·f(h,r,t)))+λ2||w||22//計算梯度16 Update weight vector w and filters Ω w.r.t. LBatch //調整卷積核和權重

3 實驗與分析

本文使用4個基準數據集，FB15k-237、WN18RR、WN11和FB13進行鏈路預測和三元組驗證，將ATREC與其他主流算法比較，其中FB15k-237和WN18RR用于鏈路預測，WN11和FB13用于三元組驗證。根據Toutanova等[24]的研究，使用篩除了反向關系模式的FB15k-237和WN18RR防止算法高分漏洞； WN11和FB13則刪除測試集中頭、尾實體曾在訓練集中一起出現的三元組。數據集的統計信息如表1所示。

表1 數據集統計信息

3.1 鏈路預測

鏈路預測是在給定關系和頭/尾實體的條件下推測另一個實體，以對構成的三元組評分。實驗中使用MR(平均排名)、MRR(平均倒數排名)和Hits@10(排名在前10位的有效實體的比例)作為評估指標。MR越低越好，MRR和Hits@10的得分越高越好。將驗證數據集上Hits@10得分最高的模型在測試集中運行以獲取最終得分。

實驗中使用TransE進行實體和關系的嵌入初始化。最佳性能表現時，TransE的超參數初始化設置如下：k∈[50, 100]，學習率∈[1e-4, 5e-4]，L1或L2范數，margin γ∈[1, 3, 5, 7]。Hits@10得分在FB15k-237上，當k=100，學習率為5e-4，L1范數，γ= 1時得分最高；在WN18RR上，當k=50，γ= 5且其他參數相同時，得分最高。

CNN學習過程中，學習率設置為∈[1e-5, 1e-4, 5e-4]，批大小(batch size)∈[128, 256]，卷積核數τ∈[100, 200, 500]，輪數(epoch)∈[200, 500, 1 000]，λ= 0.001，使用算法1中描述的過濾器正態分布，Adam優化器，并將ReLU作為非線性激活函數。在FB15k-237上，當k=100， 學習率為5e-4，τ= 100，使用[0.1, 0.1, -0.1]的過濾器分布時Hits@10分數最高；WN18RR上，當k= 50，τ= 500，truncated分布，其他參數相同時分數最高，兩個數據集上批大小都為256，輪數= 200。

實驗結果如表2所示，FB15k-237上ATREC獲得了最佳的Hits@10結果，明顯優于其他算法，MRR得分也排第二；WN18RR上獲得了最高的Hits@10(略優于ConvKB)和MRR得分(和ConvE并列)，MR得分也排名第二，僅次于ConvKB。

表2 FB15k-237 and WN18RR上的鏈路預測結果①②

DistMult和ComplEx所使用的雙線性乘法運算擅長提取實體相似性特征，在稠密數據集WN18RR(每關系對應實體對數量較大)上表現較好，MRR接近最高分(ConvE)；但在稀疏數據集FB15k-237上，則難以提取足夠的信息優化實體表示，MRR和Hits@10都有明顯下滑。

ConvE在兩個數據集的幾乎所有指標上都表現出色(除了WN18RR上的MR得分)，說明對實體/關系向量的拼接和二維轉化有助于CNN提取局部模式和關系特征。

與雙線性模型相反，TransE模型的向量平移在稀疏數據集上能有效捕捉三元組的全局特征；但在稠密數據集上，特別在處理復雜關系類型時，M側的實體表示會趨近，甚至相同，在WN18RR上的MRR得分反映出了這一缺陷。

ConvKB結合了CNN和TransE的平移特性，在兩個數據集上的所有指標相比TransE都有提升，在FB15k-237上1項指標最優，2項指標第二；但卻沒有解決實體表示趨同的問題，因此在WN18RR的MRR指標上同樣表現出性能下滑。

在FB15k-237上，ATREC的MR得分略低于ConvE和ConvKB，但相差不大。MRR得分穩定，相對于DistMult和ComplEx優勢明顯，比ConvE和TransE也有一定提高，僅略低于ConvKB，說明模型結構保留的平移特性能有效提取全局特征。Hits@10得分上，ATREC得分最高，相比ConvKB提高了約10%，由于ATREC與ConvKB近似，都結合了CNN框架和平移特性，關鍵區別在于是否進行關系集成(即本文核心特色)，因此該結果說明關系屬性集成提取了更豐富的特征。由于DistMult在MR排名第一，因此未來的工作方向之一是將其思路集成到ATREC中。

MR得分容易受到單次排序結果的影響；在WN18RR上，ATREC的MR得分仍然較低，說明模型穩定性較好。MRR得分與ConvE相同，明顯高于TransE和ConvKB，說明集成關系屬性有助于防止實體趨同，提升模型在復雜關系上的表現。Hits@10上ATREC保持了最高得分，略優于ConvKB。

借鑒之前的模型[17,19-20],本文使用TransE生成的向量初始化實體/關系表達；而ConvKB的整體性能較好(除了WN18RR上的MRR得分)，且與ATREC類似，故將TransE和ConvKB用作進一步分析的基準。

為了確認ATREC在FB15k-237上的Hits@10得分提升源于更強的復雜關系處理能力，計算FB15k-237上4種關系類別的預測頭/尾實體的Hits@10得分，如圖2、圖3所示。在1-to-1關系中，無論是預測頭部還是尾部，TransE、ConvKB和ATREC的性能相仿；預測1-to-M類型的頭部和M-to-1類型的尾部，三者表現也接近，因為在上述任務中，都是單個或多個源實體指向單個目標實體，后者識別難度較小。在M-to-1和M-to-M類型的頭部預測，以及1-to-M和M-to-M類型的尾部預測這4種情況下，ATREC的得分均為最高，尤其在1-to-M類型的尾實體預測上，相比ConvKB得分高出一倍有余，說明ATREC的性能提升確實是因為提高了復雜關系的處理能力；換言之，關系集成能更有效地提取M側的角色特征，具有較好的泛化能力。

圖2 FB15k-237上針對四種類型關系的頭實體預測的前10命中率(Hits@10)

圖3 FB15k-237上針對四種類型關系的尾實體預測的前10命中率(Hits@10)

在WN18RR基礎上，將所有11種關系按其百分比升序排列(次縱軸+折線圖)，比較3種模型的Hits@10和MRR得分(仍為柱狀圖)，如圖4、圖5所示。TransE和ConvKB在其中3種復雜關系has_part (1-to-M)、member_meronym (1-to-M)和hypernym (M-to-1)上性能明顯下滑，說明該類關系是平移模型的短板(這3種關系占整體比例較高，導致了TransE和ConvKB的MRR總得分下降)；ATREC則保持相對穩定。這一現象與3種模型在FB15k-237上預測M-to-1類型的頭實體和1-to-M類型的尾實體的表現相符，再次驗證了ATREC的模型優勢。在similar_to、verb_group、also_see和derivationally_related_form這四種M-to-M關系上，由于存在大量對稱模式的三元組(學習難度較低)，3種模型的表現都較好。

3.2 三元組分類

三元組驗證引入閾值θ，將特定三元組得分與之相比以判定三元組是否有效。根據Socher等[16]，θ通過提高驗證數據集上的平均分類精度得出。實驗中嵌入初始化仍由TransE生成，無效三元組的生成方法也相同。

從相關研究中引用部分性能較好的模型結果進行比較；本文也自行實現并測試了TransE、ConvE和DistMult模型。對于TranSparse模型，“S”和“US”分別表示結構化和非結構化模式。TransE取得最優性能時的超參數設置如下： WN11上學習率為0.001，L1范數，γ= 7，k=50；FB13上學習率相同，L2范數，γ= 1，k=100。ConvE的embedding dropout取0.2，feature map dropout 取0.2，projection layer dropout 取0.4，k=200，批大小取128，學習率取0.001，label smoothing 取0.1。DistMult，維數k=100，輪數取200，學習率取0.001，L2范數，正則化系數0.0001。ATREC在WN11上當初始學習率為5e-4，k=50，卷積核數τ= 200，truncated分布時性能最優；在FB13上，k調整為100，學習率等其他參數不變。

分類準確率結果如表3所示，平均得分ConvKB最優，ATREC略低，與TransD持平，相較許多經典算法(NTN、ConvE和TransE等)具備一定優勢。

表3 分類準確率

NTN模型在稀疏數據集上容易過擬合，因此WN11上得分較低。ConvE在兩個數據集上的表現都一般，說明單純加強局部模式的識別存在一定局限性。DistMult在稠密數據集FB13上取得最高得分，在稀疏數據集WN11上則性能明顯下降，與之前實驗結果一致。平移模型TransE及其變種在該任務上表現普遍較好。ATREC在FB13上相比TransE和ConvKB都有提升，再次證明了使用關系集成而非雙線性乘法運算處理復雜關系的可行性；但在WN11上，ATREC得分與TransE持平，低于ConvKB，原因可能為： 盡管同時考慮復雜關系和平移特性有其優勢，但也增加了特征提取的不確定性。針對該假設的改進仍在計劃中。

由于NTN、ConvE和DistMult模型總體表現一般；TransD、TranSparse-S和TranSparse-US都利用TransE生成嵌入表示，可看作是TransE的擴展，性能也近似；ConvKB在該任務上表現最優；因此只使用TransE和ConvKB作為基準模型來進一步生成FB13上各種關系分類準確率的比較，結果如圖6所示。除institution和profession屬于M-to-M類型之外，其他關系都屬于M-to-1類型?？梢钥闯觯珹TREC在M-to-M關系上的優勢明顯，在M-to-1關系上性能也較穩定，且在所有7個關系上性能表現都優于TransE。

4 總結

在保留三元組完整性和處理復雜關系的問題上，現有基于嵌入表示的知識庫補全模型仍有瑕疵，如特征丟失、參數規模龐大等。因此本文提出ATREC，旨在將平移變換后的全局和局部特征在統一框架中表示并提取，同時使用CNN降低參數規模，減少計算開銷；主要創新點在于將關系特征融合到頭/尾實體中以應對復雜關系。鏈路預測和三元組分類驗證的實驗結果證明，ATREC算法的穩定性較好，相較主流模型有一定提高，特別是在處理FB15k-237和FB13數據集上復雜關系時優勢較明顯。我們未來的工作方向包括： 嘗試從基于邏輯規則的關系推理中獲得支持；通過集成關系路徑信息改善模型性能；將ATREC應用于行業數據處理和更大規模數據集分析等等。