融合圖譜重構的時序知識圖譜推理

許智宏，張天潤，王利琴，董永峰

1.河北工業大學人工智能與數據科學學院，天津 300401

2.河北省大數據計算重點實驗室，天津 300401

3.河北省數據驅動工業智能工程研究中心，天津 300401

隨著大數據時代的到來、智能設備的廣泛普及以及5G 的迅速發展，社會進入了一個信息爆炸式增長的階段，大數據中存在著巨大的價值與潛力，這吸引了許多研究人員對其進行深入挖掘和分析[1]，知識圖譜應運而生。然而，知識圖譜構建面臨的突出問題之一是知識圖譜的不完整性，即知識圖譜中存在缺失的知識。知識圖譜的不完整性極大阻礙了知識圖譜在人工智能、大數據分析和挖掘、信息推薦和人機交互等領域的應用性能。因此，如何基于現有知識圖譜挖掘新知識，推理知識圖譜中缺失的實體或關系，已經成為智能信息處理、文本挖掘和信息抽取領域的重要且緊迫的研究問題[2-3]。

目前，大部分研究工作集中于靜態知識圖譜推理，靜態知識圖譜通過三元組表示，每個三元組反映一個事實，但是，現實世界中的事實不是靜止不變的，往往表現出復雜的時間動態性，例如，（美國，總統，特朗普）這一事實，在經過2020年美國總統選舉后失效。由此，引入時序知識圖譜，此類知識圖譜不僅包含了事件之間的共指、因果和時序等關系，還描述了事件之間的規律和演化模式，其基本單元是在三元組的基礎上加入時間信息后組成的四元組[4]。

本文任務是對時序知識圖譜進行推理，即根據過去發生的事件推斷未來將要發生的事件。事件的發生被表示為以過去事件為條件的概率分布。現有大部分時序知識圖譜推理模型將時序知識圖譜建模為靜態知識圖譜快照序列，在每個快照上仍采用靜態推理方法[5]，這種做法忽略了對知識圖譜局部時序特征的提取，無法細粒度地捕獲實體時序特征。同時，基于知識圖譜快照的推理模型在單個快照中獨立地處理事件，無法捕獲不同時間實體鄰域結構之間的交互。因此，基于靜態知識圖譜快照的方法不能有效挖掘實體鄰域潛在的時間信息。

針對以上問題，提出了基于圖譜重構的時序知識圖譜推理模型（graph reconstruction for temporal knowledge reasoning，GRTKR）。為了捕獲不同時間鄰域結構關系之間的交互，GRTKR 使用時間感知鄰域采樣器有側重地采樣實體鄰域節點。同時，為了克服基于知識圖譜快照的推理模型難以細粒度提取時序特征的缺點，GRTKR使用時序編碼器將四元組中的時間與實體一并映射為嵌入向量，鄰域特征聚合器對局部鄰居特征進行時間感知聚合。通過這樣的方式可以學習到更精確的時序特征，提升時序知識圖譜推理的性能。

1 相關工作

1.1 靜態知識圖譜推理

靜態知識圖譜推理是知識圖譜領域中的重要任務，其研究重點在于確定實體與關系之間的相關性。

翻譯模型將關系向量作為頭實體到尾實體的翻譯，早期Bordes 等人[6]根據三元組中頭尾實體表示向量的距離來估計三元組的真實性，提出了第一個基于翻譯的模型TransE，具有訓練速度快、易于實現等優點，但是不能解決多對一和一對多關系的問題。針對TransE的局限性，此后陸續涌現了一批Trans系列模型。其中TransH[7]不再嚴格要求三元組滿足三角閉包關系，只需滿足頭尾實體在關系平面上的投影在一條直線上即可，提高了推理的準確率。基于翻譯思想的模型由于運算操作簡單，參數量適中，學習效率高等優勢，成為了圖嵌入領域非常活躍的研究方向之一[8]。然而由于該類方法僅使實體和關系嵌入滿足當前三元組的約束，難以捕獲知識圖譜深層次的語義信息和多跳實體間結構特征，對于結構復雜的知識圖譜，推理準確率會受到影響。使得后續研究需要從表示空間、運算類型等方面對該類模型進行改進。

張量分解模型將知識圖譜表示為一個高維張量，通過張量分解為更小的矩陣從而完成知識推理任務。Yang 等人[9]就借鑒張量分解理論提出DistMult 方法，將實體映射為低維向量后，再計算與每種關系的相似性。ComplEx[10]則通過復值嵌入擴展DistMult，有效地對非對稱關系進行建模。此后，研究人員又提出了SimplE[11]，其利用關系的逆在三元組得分函數中加上了一個對稱項，為每個實體和關系分配兩個向量分別進行學習，在實驗中展現了良好的性能。相比基于翻譯模型，基于張量分解模型的思路是從建模整張圖譜的表示張量的角度來考慮，所以該類型的許多算法擁有充分表達知識圖譜的能力，然而這類模型的設計往往需要較高的數學基礎，因此相關研究工作少于基于翻譯模型的研究[8]。

神經網絡推理模型作為一種重要的機器學習算法，神經網絡基本上模仿人腦進行感知和認知，通過非線性變換將數據的特征分布從初始空間映射到另一個特征空間中[12]。原始圖神經網絡模型只針對無向無權圖，為了將其應用于知識圖譜，Schlichtkrull等人[13]提出R-GCN模型，為關系賦予不同的權重，通過圖卷積神經網絡實現局部鄰域信息聚合，采用DistMult作為解碼器進行相似性評估，由此，取得了比GCN更好的靜態知識圖譜推理效果。基于神經網絡的推理模型相較于其他推理模型復雜度更高，但是，具備更強的推理能力和泛化能力，對知識圖譜中實體及關系信息利用率更高，往往可以達到更好的推理效果。

1.2 基于嵌入的時序知識圖譜推理

基于嵌入的時序知識推理方法，在現有基于嵌入的靜態知識圖譜推理基礎上，引入時間信息的嵌入表示來實現時序知識圖譜推理，特點是將實體、關系及時間戳投影到向量空間得到對應的嵌入表示。Dasgupta等人[14]提出的HyTE 模型將知識圖譜按時間劃分為不同的超平面，將實體和關系映射到超平面上，再利用翻譯模型思想進行推理，既整合了時間維度信息，又通過超平面解決了實體間多關系難以推理的問題。Goel 等人[15]提出DE系列模型在靜態推理方法的基礎上將實體嵌入融入時間信息，利用循環神經網絡學習關系的時間感知表示，并使用DistMult 評分函數進行相似性評估，通過實驗證明了DE-TransE、DE-DistMult 和De-SimplE 等模型相比于靜態方法能夠充分挖掘潛在的時序特征，對于后續時序知識圖譜推理方法具有較重要的參考意義。TA-DistMult[16]將時間和關系合并成一個維度，合并后的文本序列通過LSTM計算得到含時間特征的關系，由此將四元組轉化為帶有時間特征的三元組，結合三元組評估函數進行推理。CyGNet[17]將復制機制首次應用在時序知識圖譜推理中，通過研究時間步中實體重復出現的潛在現象，結合復制和生成兩種推理模式，在學習推理未來事件時參考歷史中已知的事實，并通過實驗驗證了該推理方法的有效性。基于嵌入的時序知識圖譜推理模型通過擴展現有基于嵌入的靜態知識圖譜推理模型，利用時間嵌入表示來解決時序知識圖譜推理問題，然而，這些方法難以利用最近時間戳中的多跳結構信息和時間事實來增強預測性能，并且存在實體分布的時間稀疏性和可變性問題。

1.3 基于圖卷積神經網絡的時序知識圖譜推理

時序知識圖譜也能夠以圖結構形式進行建模，因此較多研究工作采用基于圖卷積神經網絡的時序知識圖譜推理框架。為了有效學習事件的時間信息以及圖譜中潛在的關系特征，Jin等人[18]在基于神經網絡的知識推理模型R-GCN 的基礎上提出了循環事件網絡RE-NET模型，一種用于對多關系知識圖譜的時間序列進行建模的自回歸體系結構，可以根據知識圖譜歷史的時間序列和全局的結構信息預測新發生的事件，進一步提高了時序知識圖譜推理的精度。DySAT[19]方法同時關注圖結構和時間演進過程。按時間劃分的事件通過自注意力學習鄰域信息，再通過聯合注意力學習時間推演下的三元組相似性。EvolveGCN[20]通過GCN 得到知識圖譜的結構特征，通過循環神經網絡捕獲知識圖譜的演化信息。此外，針對現有時序知識圖譜推理結果缺乏可靠性的問題，Han等人[21]提出了一種對未來事件進行鏈路預測的模型xERTE，該模型能夠對時序知識圖譜的相關子圖進行查詢，并對圖結構和時間上下文信息進行聯合建模，同時，該模型基于一種新的時間關聯注意機制，保留了時間多關系數據的因果性。圖卷積神經網絡作為一種有效的結構特征學習方法，通過消息傳遞框架捕獲相同時間戳下實體之間的結構依賴性，并通過圖神經網絡的堆疊捕獲序列信息。但是，對實體在時序知識圖譜中的時序信息捕獲不夠全面。

2 基于圖譜重構的時序推理模型

時序知識圖譜可以看作四元組(s,r,o,t)的集合G,定義時序知識圖譜中實體集合E以及一組關系集合R,其中s∈E表示頭實體，o∈E表示尾實體，r∈R表示關系，t表示時間。

使用靜態知識圖譜快照方式進行推理，模型只對相同時間戳下靜態知識圖譜快照進行學習并捕獲結構特征，再通過循環神經網絡捕獲時序信息，這樣無法充分利用時間上下文信息，難以捕獲隱含在實體間的時間與結構特征。因此，GRTKR在每次推理過程中，將靜態知識圖譜快照序列通過鄰域采樣器重構成推理圖，從而將結構和時間信息都集中到推理圖中，后續通過圖神經網絡的消息傳遞框架同時捕獲時序與結構特征。

圖譜重構的關鍵在于對待推理實體的時間鄰域進行采樣，以此來形成推理圖Ginf，其中，節點由四元組中“頭實體-時間戳”構成，即v=(s,t)，節點間的鏈接方向從具有較早時間戳的節點指向具有較晚時間戳的節點，這使得GRTKR能夠沿著整個時間軸搜索待推理實體的時間鄰域，以此利用整個時間上下文信息。

GRTKR模型分為四個部分：鄰域采樣器、時間編碼器、鄰域特征聚合器和多層感知機解碼器，模型架構圖如圖1所示。對于給出的查詢q=(sq,rq,?,tq)，GRTKR首先根據其時間鄰域構建一個推理圖Ginf，然后使用時間編碼器學習實體的時間感知表示，再通過鄰域特征聚合器捕獲實體鄰域內的時序特征與結構特征，最后使用多層感知機解碼器來計算每個候選實體成為預測答案的概率。本文只針對尾實體推理，由于為每個四元組都添加反關系，即添加(o,r-1,s,t)表示(s,r,o,t)，這樣就算只預測尾實體，也不會失去通用性。

圖1 GRTKR架構圖Fig.1 GRTKR overall architecture illustration

2.1 鄰域采樣器

不同時間范圍的信息表明了不同的關系趨勢，局部時間依賴表示短期的關系趨勢，而全局時間依賴表示長期的關系趨勢。不同范圍的時間信息發揮著不同的作用，不應一視同仁。例如，當事件（美國，拒絕經濟合作，中國，2018-07-07）發生時，“美國”和“中國”在不久的將來關系不太可能是積極的，“拒絕經濟合作”關系對于預測2018 年7 月后美國和中國之間的關系更為重要。所以歷史上事件發生時間越接近，它們之間的關系就越重要。

為了篩選歷史事件中對于查詢更重要的事件，增加時序特征對模型精度的影響，同時降低后續聚合操作的復雜性，受Han 等人[21]提出推理圖的啟發，引入鄰域采樣器，對(sq,tq)的時間鄰域進行采樣。

定義推理圖中節點v=(s,t) 的時間鄰域為Nv={(s′,t′)|t′＜t},v的鄰居定義為u∈Nv，如果u被采樣到，則將u添加到Ginf中。采樣可以是均勻的或者非均勻的，但由于事件的強時效性，在接近當前時間點采樣更多的邊更符合事實。故使用加權采樣策略，具體如公式（1）所示：

其中，t′與t′均小于t，同時為了防止采樣過多不太相關的鄰居，參考Han 等人[21]對鄰域采樣數的設置，鄰域采樣器通過超參數來限制采樣的最大數量，在3.4 節對該參數的靈敏度進行實驗分析。

2.2 時間編碼器

在時序知識圖譜中，圖的結構不再是靜止不變的，實體之間的關系會隨著時間的推移而變化，因此，實體特征會隨之發生變化。時間編碼器借鑒Goel等人提出的歷時實體嵌入（diachronic entity embedding）方法，即學習每個實體的時間感知嵌入表示，實體si∈E在時間t的嵌入表示由靜態低維向量和時序低維向量組成[15]。通過這種方式，能夠區分推理圖中來自相同實體s但時間不同的兩個節點(s,t1)與(s,t2)。時間感知實體嵌入表示如公式（2）所示：

與現有大多數方法只對圖中實體進行嵌入表示不同，GRTKR也對關系進行嵌入表示。對于推理圖中，節點之間關系r∈R，本文沿用Goel 等人[15]的假設，即關系表示具有時間不變性，關系嵌入表示如公式（3）所示：

其中，W0為關系嵌入矩陣，r表示關系的獨熱向量。

2.3 鄰域特征聚合器

鄰域特征聚合器受GraphSAGE[22]的啟發，通過對鄰域內信息進行聚合，從而得到實體的局部時序特征。鄰域特征聚合器的輸入是經過時序編碼器后的實體與關系的嵌入表示向量，然后，將關系特征融合到實體特征中，最后，通過GRU（gate recurrent unit）捕獲實體間隱含的時序特征。

2.3.1 特征融合

為了將關系加入到鄰域特征表示學習中，GRTKR將關系和節點嵌入向量組合起來進行聯合學習。同時，加入反向關系類型和自循環關系類型，這樣可以處理具有高度多關系數據特征的時序知識圖譜，并且不會引入過多參數。實體關系融合如公式（4）、（5）所示：

2.3.2 節點特征更新

為了捕獲隱式時序特征，GRTKR 將推理圖中鄰居節點按時間先后排序得到的特征序列作為GRU 的輸入，由此得到實體的隱式時序特征，隨后更新實體嵌入向量如公式（6）所示：

其中，W為可學習權重矩陣，hu,t表示推理圖中節點v的鄰域節點u在t時刻下的特征融合表示，σ采用ReLU作為激活函數。

2.4 多層感知機解碼器

為了對查詢(sq,rq,?,tq)進行推理預測，多層感知器（multilayer perceptron，MLP）解碼器將來自鄰域特征聚合器輸出的特征向量作為輸入，并通過softmax 函數做歸一化處理得到所有候選實體的概率，如公式（7）、（8）所示：

其中，Wm為可訓練權重參數，hv為經過聚合后的實體嵌入表示向量，er為關系嵌入向量，p(o|s,r,t)代表候選實體的概率，ot代表其中概率最大的實體，即最終的預測結果。

預測實體o可以視作一次多分類任務，每一類都對應一個實體。采用多分類的交叉熵損失函數，如公式（9）所示：

其中，G為訓練集中的事件集合，p(ok|s)為在已知頭實體、關系及時間的條件下實體ok作為尾實體的概率值。GRTKR的算法偽代碼如算法1所示。

算法1GRTKR推理偽代碼

輸入：推理圖Ginf，推理圖中的節點集合V，鄰域集合函數N(v)，實體靜態嵌入向量，關系嵌入向量er。

輸出：時序知識圖譜中的四元組缺失的尾實體。

3 實驗設計與結果分析

3.1 數據集

為了評估GRTKR模型在時序知識圖譜推理任務中的效果，主要使用了兩種公開的時序知識圖譜數據集：ICEWS[16]及YAGO11K[23]。ICEWS 是由BBN ACCENT事件編碼器自動從新聞文章中提取數據并加入時間信息生成的，ICEWS14 數據集包含2014 年1 月至2014 年12月中所有發生的事件，ICEWS05-15數據集包含2005年1月至2015年12月中所有發生的事件。YAGO是由德國馬普研究所研制的鏈接數據庫，主要集成了Wikipedia、WordNet 和GeoNames 三個來源的數據。YAGO11K 是截取其中帶有時間注釋的數據形成的數據集。以上數據集均為時序知識圖譜領域常用的公開數據集，具體的統計信息如表1 所示。其中訓練集、驗證集、測試集按照8∶1∶1的比例劃分。

表1 數據集信息統計Table 1 Information statistics of datasets

3.2 評價標準

在時序知識圖譜推理的過程中，推理模型會對候選實體評分并根據評分結果排序，目標實體在候選實體中的排名越靠前，則模型的推理效果越好。為了評估所提出模型的推理效果，使用MRR和Hits@1/3/10評價指標對模型進行評估。MRR（mean reciprocal rank）表示平均倒數排名，即對目標實體在候選實體中排名的倒數取平均，該指標可以體現模型的全局表現，因為對個別異常數據不敏感，所以目前研究工作更多采用MRR 評價模型的綜合表現。Hits@k表示推理結果命中前k的比例，計算如公式（10）、（11）所示：

式中，Dtest表示測試集中四元組的集合，T表示時序知識圖譜的時間戳總數，rank函數用于計算目標實體在候選實體中的排名。

3.3 對比實驗

為了充分評估所提出模型的推理準確率及性能表現，將所提出的模型與主流基線模型進行對比分析。對比模型包括TransE、DistMult、HyTE、TTransE、TA-DistMult、CyGNet、xERTE 以及DE-SimplE，其中TransE、DistMult是靜態知識圖譜推理模型，其余均為時序知識圖譜推理模型。

表2～表4給出了在三個數據集上的實驗結果，對比模型實驗結果來源于CyGNet[18]、xERTE[22]及DE-SimplE[16]。

表2 不同方法在ICEWS14數據集上實驗結果對比Table 2 Comparison of experimental results of different inference methods on ICEWS14 dataset 單位：%

表3 不同方法在ICEWS05-15數據集上結果對比Table 3 Comparison of experimental results of different inference methods on ICEWS05-15 dataset單位：%

由表2、表3 可知，GRTKR 在ICEWS 兩個數據集上均優于其他基線方法。在ICEWS14 數據集上MRR、Hits@1、Hits@3 和Hits@10 指標分別優于DE-SimplE約4、11、5、2個百分點。在ICEWS05-15數據集上MRR、Hits@1、Hits@3和Hits@10指標分別優于DE-SimplE約7、15、11、4個百分點。

由表4 可知，GRTKR 在YAGO 數據集上優于其他基線方法，MRR、Hits@3 和Hits@10 分別優于CyGNet約4、3、3個百分點。

綜合三個數據集的實驗結果可以看出，GRTKR 推理精度提升效果明顯，這是因為GRTKR 模型通過加權采樣來完成圖譜重構，同時，對實體進行顯式與隱式雙重時序特征提取，可以更細粒度地捕獲特征，從多個角度獲取實體的時序特征，使得提取到的時序特征更加豐富。DE-SimplE在三元組推理模型的基礎上，僅僅增加了一個歷時的實體嵌入函數對時間維度進行建模，該函數提供實體在任何時間點的特征，但其忽略了實體的局部結構中隱含的時序特征。而xERTE通過在實體鄰域內的迭代采樣和注意力機制來完成推理，這雖然可以捕獲鄰域內隱含的時序特征，但缺少對時間的顯式建模，導致捕獲的時序特征不夠豐富。通過觀察實驗結果，可以看出GRTKR 在ICEWS 的兩個數據集上的提升高于YAGO11K。這是因為YAGO11K 數據集的時間粒度是年，數據集中的關系大多是長期存在且穩定的，時序特性不強，而ICEWS數據集中的事實元組時間粒度為天，數據集中的關系大多是重復發生的、不穩定的、短期存在的。GRTKR 可以在時序特性更強的ICEWS 數據集捕獲更多的時序特征，以此來提高推理性能。

3.4 靈敏度實驗

為評估鄰域采樣器最大采樣數量對模型推理準確率的影響，本文在數據集ICEWS14 上將鄰域采樣器采樣數分別設置為{5，10，15，20，25}。觀察該參數對模型推理準確率的影響。實驗結果如圖2所示。

圖2 MRR與運行時間隨采樣數量的變化曲線Fig.2 Curves of MRR and Runtime over number of samples

由圖2 可知，當最大采樣數取值為15 時，MRR 為56.8%，并且隨著鄰域采樣數量的增加推理的準確率在不斷提升。但是，采樣數量設置為20 相較于15 沒有明顯的提升，運行時間反而增加了近34%。綜合以上分析，在實驗中設置采樣數量為15。

3.5 消融實驗

為了評估GRTKR 各個組成部分對性能的影響，將進行消融實驗，具體地，首先去除時間編碼器，直接使用實體的靜態嵌入向量作為鄰域特征聚合器的輸入。接下來，去除鄰域特征聚合器，直接將時間編碼器生成的嵌入向量輸入到解碼器，結果如表5所示。

表5 在ICEWS14、ICEWS05-15和YAGO11K數據集上的消融實驗Table 5 Ablation results on ICEWS14，ICEWS05-15 and YAGO11K datasets 單位：%

由表5 中數據可以看出，在去除時間編碼器后，ICEWS14、ICEWS05-15 和YAGO11K 數據集上的各項評價指標中均有所下降，這可以說明在鄰域特征聚合器之前增加時間編碼器能夠對推理圖中實體相同但時間不同的兩個節點加以區分，同時豐富節點特征，使后續鄰域特征聚合器能夠有效提取節點之間隱含的時序特征，有助于提升時序知識推理任務的準確率。接下來，在去除鄰域特征聚合器后，在三個數據集中的各項評價指標同樣有所下降，說明對鄰域內信息進行聚合，從而捕獲實體局部時序特征，在時序知識圖譜推理任務中十分重要。

消融實驗結果表明，GRTKR 的各個組成部分都對整體模型的性能起到了積極作用。模型對實體在時序知識圖譜中的信息進行充分挖掘，有效地解決實體在時序知識圖譜中的時間信息捕獲不夠全面的問題。本文提出的對現有方法的改進之處都能有效提升推理模型的性能。

4 結束語

本文提出了一種基于圖譜重構的時序知識圖譜推理模型，為表示同一實體在不同時間下包含不同的信息引入了基于歷時實體嵌入的時間編碼器，同時，觀察到在不同時間的每個事件也存在著不同強度的因果聯系，本文進一步設計了鄰域特征聚合器來學習的局部結構與時序信息，深度挖掘了實體在時序知識圖譜上的時序特征。實驗結果表明，本文方法提高了時序知識圖譜推理的性能。下一步的工作將致力于修剪GRTKR 模型，使其能夠在大規模時序知識圖譜中推理，除此之外，嘗試引入注意力機制，提高模型的可解釋性。