基于時序感知的動態知識圖譜補全方法

李鳳英，范偉豪

桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林 541004

知識圖譜是知識工程的最新產物，作為一種可存儲和計算的信息載體，在以知識驅動的人工智能領域有諸多實踐，如信息檢索[1]、推薦系統[2]、智能問答[3]。知識庫通過三元組(s,r,o)構成。每個三元組反映一個知識事件，該事件包含頭實體（subject）、尾實體（object）以及兩者間關系（relation）。這三者分別對應圖結構中的兩個節點及相連的有向邊。目前較大的百科知識庫如Freebase[4]、YAGO[5]、DBpedia[6]都來源于大量的網頁信息。然而這些知識圖譜并不完整，一部分原因是源數據所含的知識并不充分，另一部分則與提取實體和關系的算法能力有關[7-8]，在處理各類非結構化數據效果并不理想。不完善的數據會導致以知識驅動的應用效果下降，因此補全完善知識庫對于知識圖譜的利用十分必要。

知識圖譜補全（knowledge graph completion，KGC）是通過學習知識庫內在結構和相關語義信息，對實體間潛在的關系進行補全。相關研究通常給定一種刻畫實體關系相關性的建模理論，通過訓練得到實體向量和關系向量。實體間缺失的關系鏈接可通過計算實體和關系之間的相似性進行評估預測，從而達到補全的目的。

傳統KGC的研究工作是在三元組構成的靜態知識圖譜下對多關系建模。自TransE[9]方法的提出以來研究者們嘗試了多種建模方式：一部分工作是利用關系的語義特征，設計出滿足關系間多種性質的相似性理論，其性質涵蓋對稱性、反對稱性、自反性和組合性[10]；另一部分研究是利用了知識圖譜中的結構信息對實體關系建模，如基于關系路徑的方法[11]以及基于節點鄰域特征的方法[12]。

在知識應用過程中，歷史事件必須限定在特定時間才具有參考價值，即知識存在時效性。近年來出現了帶有時間標簽的動態知識圖譜（dynamic knowledge graph，DKG），也有部分研究人員稱作時序知識圖譜（temporal knowledge graph，TKG）。其基本單元是在三元組的基礎上加入時間信息（time）的四元組(s,r,o,t)。隨著事件的不斷演進，動態知識圖譜可以不斷更新，提供時間維度的知識內容，更具研究價值。圖1舉例了靜態和動態知識圖譜表示國家建交事實的異同。靜態知識圖譜疊加了所有歷史事實，通過圖譜結構能夠利用相對完整的全局信息。而動態知識圖譜則以演化的視角，展示事件的發展變化。從知識的利用角度，通過聚焦多個時間事實，動態知識庫相比靜態知識庫能夠反映出更加豐富的信息。

圖1 靜態知識庫和時序知識庫對比Fig.1 Comparison between static KG and dynamic KG

由于傳統KGC方法是面向三元組建模，其相似性評估計算僅涉及實體和關系，缺乏時間維度信息，因此并不適用于動態知識庫的補全。動態知識圖譜補全方法除了對實體關系建模，更重要的是在四元組相似性評估中充分利用時間特征。

目前該領域的部分工作是將時間特征內嵌于實體和關系之中。此類方法將不同時間看做彼此互不重疊的時間空間，通過將實體和關系映射在不同的時間超平面，將四元組轉化成三元組，以沿用傳統KGC方法對實體和關系進行相似性評估。然而在現有的動態知識庫中，關于時間信息的描述包含時間點、時間起止、時間段三種形式，且時間分布的稀疏程度影響映射效果。不規則的時間描述以及時間分布的稀疏性都限制了補全動態知識庫的實際效果。而其他面向動態知識圖譜的補全研究嘗試將時間維度進行獨立建模，將時間向量引入相似性評價過程。但實際上僅在代價函數中作為參數使用，并沒有充分考慮時間特征對于四元組更深層的含義。表1對比了現有補全方法在相似性理論和知識維度建模的差異。通過對比可知，適用于動態知識庫的補全方法應該具備能夠對知識各維信息實施建模，且必須利用時間特征以及充分體現時間維度與其他相關維度的深層聯系。

表1 用于知識圖譜的補全方法對比Table 1 Comparison of approaches for knowledge graph completion

為了解決四元組中時間維度利用不充分的問題，設計出的時序感知編碼器（temporal aware encoder，TAE）將四元組中的時間與其他實體和關系建模為規模相同的嵌入向量。TAE改進了圖卷積神經網絡[21]，利用注意力權重有側重地學習鄰域時序信息。同時設計的時序卷積解碼器（temporal convolutional decoder，TCD）用于對編碼后的時序四元組進行全局相似性評價。這樣的方式可以學習到更精確的時間維度特征，提升補全時序圖譜的性能。通過在ICEWS14、ICEWS05-15、Wikidata12k和YAGO11k數據集上的實驗，驗證了時序感知補全方法的有效性。對比相關研究性能指標，時序感知補全方法在鏈接預測表現較優。

1 相關工作

1.1 靜態知識圖譜補全方法

靜態知識圖譜補全研究重點在于如何刻畫實體與關系的相關性。根據知識來源、靜態知識圖譜可以分成百科類知識圖譜和垂直領域知識圖譜。百科類知識由于來源于大量網頁信息，關系數量相對較多。缺乏統一的內容規范，百科知識圖譜存在相對復雜的語義關系，表現于兩個實體同時存在多種關系。這要求補全方法能夠充分表示實體的多維特征。而垂直領域知識圖譜來源于行業專家編寫和鑒定的細分知識，事實內容描述簡潔，關系種類相對較少。大量的實體僅通過較少的關系聯系，這要求建模關系需要克服一對多和多對多的難點。

早期Bordes等人發現三元組中的實體和關系在向量空間中滿足幾何向量加的特點s+r≈o，設計出翻譯方法TransE[9]。Yang等人借鑒張量分解理論提出DistMult[13]方法。實體映射為低維向量后，再計算與每種關系的相似性。在二者開創性工作的基礎上，研究工作不斷改進完善。從關系語義角度出發，Sun等人分析了關系存在的多種性質，如對稱性、反對稱性、自反性和組合關系，利用歐拉恒等式，提出將實體和關系映射到復數向量空間，并將每個關系定義為頭實體到尾實體的旋轉。除此以外，知識圖譜的結構信息也被利用到多關系建模。PTransE[11]擴大了建模視野，對整條實體關系組成的路徑建模表示。R-GCN[22]將關系賦予不同的權重，通過圖卷積神經網絡實現鄰域特征學習表示，并采用DistMult作為解碼器進行相似性評估。

1.2 動態知識圖譜補全方法

動態知識圖譜補全研究對于時間維度知識的思考更多[23-24]，除了考慮靜態知識圖譜補全中的實體和關系，更需要注重時間維度的信息建模。相比“頭實體—關系—尾實體”的指向性聯系，時間信息是更加全局性的知識維度，能夠從更多角度解讀，有著更靈活的建模方式。按照時間信息的利用方式，現有動態補全方法可以分成時間內嵌補全方法和時間獨立補全方法。二者區別在于是否將時間維度同實體關系一樣表示學習得到特征向量。

時間內嵌補全方法是把時間信息內嵌于實體和關系中，僅建模實體關系。本質上該類方法是把四元組降維成三元組后使用靜態補全方法。Dasgupta等人把特定時間中的實體和關系看成一個靜態知識圖譜，提出的HyTE[16]方法將不同時間視作不同的時間超平面，四元組的實體和關系通過映射函數在某個超平面中得到三元組(Pt(s),Pt(r),Pt(o))表示，再利用翻譯思想補全。García-Durán等人將時間和關系合并成一個維度。合并后的文本序列通過LSTM計算得到含時間特征的關系rseq，由此將四元組轉化為帶有時間特征的三元組(s,rseq,o)，結合三元組建模思想，設計出TA-DistMult和TA-TransE[17]。Zhang等人通過注意力機制將時間信息融合進實體當中，同樣結合三元組建模思想，設計出ST-TransE、ST-DistMult和ST-ConvKB[18]。DySAT[25]方法同時關注圖結構和時間演進過程。按時間劃分的事件通過自注意力學習鄰域信息，再通過聯合注意力學習時間推演下的三元組相似性。

時間獨立補全方法則是學習四元組的四個維度向量表示，方法中相關計算引入時間向量。TTransE[19]延伸了TransE方法，將時間加入到實體關系在幾何向量空間中的運算f=|s+r+t-o|。相同地，TComplEx[20]延伸了Compl Ex[14]方法，將時間加入到復數域下進行張量計算以評估四元組相似性。TeLM[26]方法利用線性時間正則化器和多向量嵌入進行四元組張量分解評估相似性。

2 時序感知補全方法

現有對于動態知識圖譜的補全工作，大都將時間特征內化到實體和關系當中，僅對實體和關系建模，時間維度沒有得到建模表示。忽略了時間向量在下游任務中被利用的可能。與此同時適用于三元組的相似性理論并不能直觀地反映動態知識庫各維度信息的相關性。因此時序感知補全方法借鑒時間獨立補全方法中對于時間維度獨立建模，同實體和關系表示成規模相同的嵌入向量。根據表1中面向四元組的補全方法，TTransE[19]和TComplEx[20]雖然能夠對時間維度建模，但未能考慮到時間特征與實體和關系間的關聯性。因此時序感知補全方法在時間獨立建模外還將時間特征融合參與到其他維度，以更充分表示四元組各維度，達到更佳補全效果。

時序感知補全方法整體框架如圖2所示，包含時序感知編碼器（temporal aware encoder，TAE）和時序卷積解碼器（temporal convolutional decoder，TCD）。TAE改進了圖卷積神經網絡（graph convolutional network，GCN），將四元組中的各維度嵌入為規模相同的向量，每個節點通過改進的圖注意力機制[27]達到有側重地學習鄰域特征。TCD將所有四元組(s,r,o,t)在k維空間下嵌入表示為一個k×4的輸入矩陣，改進卷積神經網絡，采用1×4的不同卷積核來提取嵌入四元組的全局關系，從而評估四元組整體的相似性。

圖2 用于動態知識圖譜補全的時序感知方法整體框架Fig.2 Structure of temporal aware approach for dynamic knowledge graph completion

2.1 時序感知編碼器

動態知識圖譜定義為G=(E,R,T)，其中E={e1,e2,…,ea}、R={r1,r2,…,r b}和T={t1,t2,…,t c}分別為實體集合、關系集合以及時間集合。基本單元為四元組tp ijkm=(ei,r k,e j,t m)，表示在時間t m下，兩個相連的實體e i和e j，通過關系r k連接構成的事件。

TAE將時間維度同實體關系相同處理，建模為一個嵌入向量，即四元組的嵌入表示為x i、y k、x j以及t m。TAE借鑒了圖卷積神經網絡的特性，以充分學習動態知識庫中實體、關系以及時間三者間的交互特征。圖卷積神經網絡因其能夠匯聚鄰域節點特征到中心節點，已成功應用在各類圖表示學習任務中。而圖注意力網絡[24]將鄰域權重進一步改進為注意力值。相比無向圖，動態知識庫的圖結構中關系和時間維度有著獨特的含義，因此TAE改進了圖注意力網絡的特征學習過程，中心節點通過匯聚鄰域四元組特征進行表示學習。具體步驟如下：

如圖2所示，首先以同一中心節點s為頭實體的鄰域四元組劃分。將每個知識單元中頭實體s、關系r、尾實體o、時間t對應的向量x i、y k、x j以及t m，拼接成一個四元組矩陣。如公式（1）所示，得到該四元組的嵌入向量表示z ijkm：

其中，A為線性變換矩陣，用于降低四元組矩陣維度。

鄰域中不同四元組特征對于中心節點的影響并不相同。為了有側重地學習中心節點的鄰域特征，TAE將注意力值作為涉及的四元組對中心節點的貢獻程度。根據每個四元組嵌入向量，分別計算注意力值p ijkm：

其中，W為權重矩陣，LeakyReLU是選用的激活函數。為了調整注意力值的大小避免出現較大的差值，針對公式（2）計算的注意力值進行歸一化處理，得到四元組級注意力值為q ijkm：

其中，歸一化函數采用softmax，exp表示以e為底的指數次冪。N a表示鄰域四元組中尾實體集合，Nb表示鄰域四元組中包含的關系集合，N c表示鄰域四元組涉及的時間集合。公式（1）～（3）相關計算如圖3所示，經過上述步驟得到了四元組級注意力。

圖3 時序感知編碼器中四元組注意力計算過程Fig.3 Process of computing 4-tuple feature in TAE

結合注意力值，中心節點s通過匯聚鄰域四元組特征更新其嵌入向量x i，如圖2中“四元組級特征融合”所示。其鄰域四元組嵌入向量與歸一化后的注意力權重聚合后相加，如公式（4）通過激活函數得到更新后的嵌入向量x′i：

為了防止實體本身特征在迭代更新中丟失，TAE引入網絡層輸入，如公式（5）所示每次注意力學習到的鄰域信息與原實體向量共同更新實體矩陣X”：

其中，X表示實體向量組成的矩陣，X′為本次迭代更新的實體向量矩陣，B為線性變換矩陣用于匹配矩陣規模。經過多次迭代，實體矩陣學習到了時序知識庫的多維特征，為了保持輸出的規模相同，通過權重矩陣實現關系矩陣R′和時間矩陣T′的輸出：

其中，R表示關系向量組成的矩陣，W R為關系的權重矩陣，T表示時間向量組成的矩陣，W T為時間的權重矩陣。

訓練的優化目標采用TTransE[19]的思想，使用鉸鏈損失來優化TAE，單獨四元組損失為dist(tpijkm)=，全體四元組優化目標為：

其中，S為原知識庫存在的四元組集合，而S′為負采樣生成的四元組集合，目的是為了增加訓練樣本。S′是通過置換存在四元組的頭尾實體得到的污染的四元組。γ表示誤差邊界。

2.2 時序卷積解碼器

動態知識庫經TAE編碼后，中心實體通過聚合鄰域特征，捕獲了四元組中多個維度的特征。特別包含了表1提到的此類方法未能充分利用的時間維度特征。為了補全動態知識庫，需要評價四維信息的相似性。ConvKB[15]方法利用卷積神經網絡能夠在卷積核視野下對三元組相似性評估。設計的TCD改進了其網絡結構針對四元組相似性評估，如圖4所示。針對嵌入后規模為k×4的四元組作為輸入矩陣，卷積層采用多種規模為1×4的卷積核，從多個角度提取四元組特征。計算得到的特征向量通過矩陣轉換成數值來評價四元組的相似程度。TCD評分函數為：

圖4 時序卷積解碼器相似度評估過程Fig.4 Process of computing similarity in TCD

其中，ωm表示第m個卷積核，Ω表示超參數，*表示卷積操作，C為線性變換矩陣。

TCD采用軟邊界損失訓練網絡參數，同樣通過負采樣增加訓練樣本。損失函數如下：

其中，p的取值與tp i jkm的關系為：當tpijkm∈S時，p=1；當tp ijkm∈S′時，p=-1。

3 實驗及分析

為了驗證所提出的時序感知編碼器以及時序卷積解碼器的有效性，在4個公開的數據集上進行了鏈接預測實驗。在多項數據指標上觀測補全效果并給出相應分析。

3.1 數據集

綜合危機預警系統（ICEWS）是目前公開的最大動態知識庫。已有198個國家為該數據集提供自1995年至2018年的1 700多萬次政治事件。其主要來源于社交媒體和新聞媒體等。García-Durán等人將ICEWS劃分為多個子數據集。其中ICEWS14[17]記錄的是2014年內的政治事件，時間稠密。而ICEWS05-15[17]的時間跨度較長，從2005年至2015年近10年的政治事件。YAGO11k[16]是截取靜態數據集Freebase15k的實體，通過YAGO知識圖譜的實體對應，提取關系，最后根據yagoDateFacts中相關記錄提取時間信息。Wikidata12k[16]是從維基百科知識庫中提取的時序事件，但該數據集中增加了時間修飾語“occursSince”及“occurUntil”。數據集涉及實體關系和時間統計信息如表2所示。

表2 動態知識圖譜數據集信息統計Table 2 Statistics of dynamic knowledge graph datasets

3.2 評價指標

知識圖譜補全的測評任務為鏈接預測，它的目標是根據已知的節點和邊，得到新的邊（的權值/特征）。其評價指標有命中率（Hit@1/3/10）、平均排名（mean rank，MR）和平均倒數排名（mean reciprocal rank，MRR）。訓練集中對所有三元組訓練方法參數，測試集驗證真實三元組的排名情況，進行記錄統計。共有Ttest個測試集三元組，rank i表示打分后的排序名次，Hit@X、MR及MRR的計算如下：

其中，Hit@X表示真實三元組在前X中出現。

Hit@1得分高說明方法對原本的實體關系學習較好，在當前知識庫中命中率高，補全效果佳；Hit@10得分高說明實體關系學習潛在表現較好，在多個數據集上Hit@10較高分數則說明方法的泛化能力強；Hit@3介于Hit@1和Hit@10之間。方法的全局表現通過MR和MRR體現，與MR相比，MRR在遇到異常數據的情況下數值變化不大，即對個別異常數據不敏感，所以目前研究工作更多采用MRR評價補全方法的綜合表現。

3.3 實驗結果及分析

為了分別驗證時序感知編碼器（TAE）和時序卷積解碼器（TCD）對于動態知識圖譜補全的有效性，在四個公開的數據集上進行了鏈接預測實驗，結果如表3和表4所示。其中“TCD”的數據是僅采用時序卷積解碼器的補全效果，其輸入為隨機初始化的四元組向量；而“TAE+TCD”的數據則是聯合了時序感知編碼器和時序卷積解碼器的實驗效果，此處TCD的輸入是經TAE訓練得到的四元組向量。為了與相關動態知識圖譜補全研究分析，實驗中列舉了相關工作中提到的動態知識圖譜補全工作，其數據來源于TeLM[26]及ST-ConvKB[18]。在ICEWS14、ICEWS05-15、Wikidata12k和YAGO11k數據集上，僅TCD補全方法在Hit@3和Hit@10指標上超越了其他工作，說明僅TCD補全方法的泛化能力較強，能夠適用于不同動態知識圖譜補全。然而在MRR及Hit@1指標上，僅TCD補全方法未能超越相關工作，這是因為TCD雖然對四元組的各維度統一建模，但四元組內部的相互聯系并未充分利用。

表3 在ICEWS14和ICEWS05-15上的測試效果Table 3 Experimental results on ICEWS14 and ICEWS05-15

通過對比“TCD”和“TAE+TCD”的實驗數據，“TAE+TCD”方法在相同數據集下，MRR、Hit@1、Hit@3和Hit@10各項指標都有提升。這說明了TAE通過聚合四元組鄰域特征，捕獲了四元組內部信息，從而提升TCD的補全性能。這同時驗證了TAE作為編碼器的有效性。

在ICEWS14、Wikidata12k和YAGO11k數據集上“TAE+TCD”方法在MRR和Hit@1指標上均高于其他方法，在ICEWS05-15數據集的MRR得到次佳的結果，說明了提出的時序感知補全方法對于動態知識圖譜補全的有效的。然而在ICEWS05-15數據集的Hit@1指標上，同類時間獨立補全方法TeLM和TComplEx效果更好。根據表2的數據集統計信息，ICEWS05-15相比其他3個數據集，實體關系數量差別不大，但時間數量最多，這是因為數據來源時間跨度較大。在多時間建模問題上，TeLM方法通過設置時間約束，降低了時間信息建模的難度；而TComplEx方法對四元組的相關性計算是在復數域空間，相比實數域空間，能夠更充分表示時間特征。本方法雖然也對時間信息單獨建模，但提取多時間特征仍存在提升空間。

4 總結與展望

本文提出了用于動態知識圖譜補全的方法，由時序感知編碼器和時序卷積解碼器兩部分構成。本方法能夠對時間維度單獨建模，且充分考慮了時間維度與實體關系的相關性。通過鏈接預測實驗，分別驗證了時序感知編碼器以及時序卷積解碼器的有效性。與目前動態補全工作相比，時序感知補全方法在多項衡量指標上獲得提升，取得較好的動態知識圖譜補全效果。但在更復雜的動態知識庫中，提出的方法仍存有提升空間，未來將改進方法，以適用于補全多時間的動態知識圖譜。除了解決動態知識庫補全任務，時序感知編碼器也提供了將四元組建模思路。未來將嘗試融合本方法，適用于動態知識圖譜的推理及問答等應用。