時序知識圖譜的增量構建

張子辰，岳 昆，祁志衛，段 亮

云南大學 信息學院,昆明650500

近年來，知識圖譜（knowledge graph，KG）作為結構化的語義知識庫，用符號形式化的方式描述物理世界中的概念及其相互關系，成為了學界和業界的研究熱點。KG 構建是知識圖譜研究的關鍵，目前主要的構建方法先抽取非結構化數據中的實體和關系，然后以結構化的方式存儲和表示實體與實體間的相互關系。然而，隨著時間的推移，領域KG 的構建需要實時反映新的知識，例如，新知識可能來源于各種社交媒體中快速產生且不斷演化的數據，需要將其不斷添加到KG 中，進而反映隨時間推移知識庫的演化發展。因此，如何高效地將數據中蘊含的新知識添加到當前KG 中，完成時序KG 的增量構建，具有重要意義。上述開放世界背景下數據驅動的時序KG 增量構建，可以豐富現有KG 并實時地反映知識的演化更新，仍存在如下挑戰：

（1）由于數據中蘊含的新知識需要不斷更新到當前KG 中，而KG 作為一種高維、復雜的圖結構，需要一種能夠高效描述時序KG 并支持其增量構建的模型。

（2）添加合適的新知識，是完成時序KG 增量構建的關鍵，需要一種能夠度量新知識與當前KG 吻合程度的方法，作為評判能否添加的依據。

針對挑戰（1），現有的圖嵌入法大多通過TransE、TransH和TransD等基于知識表示的翻譯模型，將高維、復雜、異構的KG 嵌入到低維、統一、稠密的向量空間中，進而完成對現有KG 的構建和知識表示。另外，基于翻譯模型還衍生出許多其他表示學習模型，如TransH 在TransE 基礎上設計出新的翻譯模型TransAH，提高了訓練學習的效率和知識表達能力。文獻[11]提出一種改進的知識表示模型STransH，采用單層神經網絡的非線性操作來加強實體和關系的語義聯系，獲得了更優的效果，可用于大規模知識圖譜構建和推理等任務。但是，這些構建方法只針對現有KG 進行構建，對隨時序產生的新知識如何進行增量構建，仍有待進一步探索。

為了描述KG 中知識隨時間變化的相應更新，Goel 和Wang 等基于靜態KG 的嵌入模型對多關系事件構建時序KG。由于事件具有時效性，為了彌補在事件和時間關系方面覆蓋范圍和完整性方面的不足，文獻[14]融合了事件的時間信息，通過神經網絡對事件的上下文信息進行編碼，從而構建時序KG。Gottschalk 等基于時序KG 的特點構建了多語言、以事件為中心的時序知識圖譜EventKG。但是，上述構建方法主要針對現有事件的時序信息來構建KG，而如何將外部數據所蘊含的新知識不斷添加到KG 有待進一步探索。

對此，本文提出了一種數據驅動的時序KG 構建方法，實現時序KG 的增量構建。具體而言，給出時序KG 的定義，并基于TransH 提出了一種時序KG 建模方法，從而獲得時序KG 的嵌入向量。為了保證KG 嵌入到低維向量空間的損失最小，利用隨機梯度下降法（stochastic gradient descent，SGD），從而使增量構建的模型損失最小。

針對挑戰（2），目前大多數方法通過對KG 中實體間的關系或三元組中缺失的實體進行補全，即知識圖譜補全（knowledge graph completion，KGC）。其中，一些封閉世界下的KGC 方法，不考慮新增的實體關系，如基于路徑和規則預測實體間的新關系和基于元學習預測實體關系，使KG 更加完整。學者們還考慮到新增的外部知識，即開放世界下的KGC，如Socher 等提出了基于張量神經網絡（neural tensor network，NTN）的模型，用以推斷實體間的關系，通過訓練KG 中的三元組來抽取真實文本中實體間的關系，并補充到KG中。Shi等提出了ConMask模型，用于學習實體名稱的嵌入和部分文本描述，進而將外部實體連接到KG 上。上述方法主要針對三元組中的缺失實體或關系進行補全，而面對數據中所包含的大量且完整的新知識（即新三元組集合），仍有待進一步探索。

因此，本文的增量構建方法將把基于數據獲得的新知識（新三元組）添加到當前KG 中，進而完成KG 的增量構建。例如，一條少數民族新聞報道了“卡雀哇”節日，從中抽取出新的三元組如“（獨龍族，節日，卡雀哇）”、“（馬庫村，緊鄰，中緬邊境線）”和“（卡雀哇，活動，剽牛祭天）”等。可以看出三元組“（獨龍族，節日，卡雀哇）”與獨龍族相關，可將其增量更新到KG 中，過程如圖1 所示。

根據圖1 實例中新增三元組與當前KG 的關系，考慮以下兩個問題：（1）如何只添加與當前KG 有關的新知識。如實體“卡雀哇”與當前KG 中的“獨龍族”存在新的“節日”關系，而“馬庫村”沒有這一關系，因此“（馬庫村，緊鄰，中緬邊境線）”應該去除。（2）如何把與當前KG 間接關聯的三元組添加到KG中。如三元組“（獨龍族，節日，卡雀哇）”與當前KG相關聯，而“（卡雀哇，活動，剽牛祭天）”沒有這種關聯關系，但這兩個三元組之間相關，因此“（卡雀哇，活動，剽牛祭天）”也應添加到當前KG 中。

圖1 KG 添加新三元組實例Fig.1 Example of adding new triple to KG

為了直觀度量新三元組與當前KG 的吻合程度，本文采用激活函數將其轉化為一個權值，用此度量新三元組與當前KG 的最終吻合度。然后，為了添加與當前KG 具有間接關聯的新三元組，本文基于貪心策略提出了最優子集的提取算法，將最優新三元組集合添加到當前KG 中，完成時序KG 的增量構建。

最后，通過建立在Wikidata、CN-DBpedia 和Freebase 數據集上的實驗，與現有的KGC 方法進行比較，驗證了本文方法的高效性和有效性。

1 時序知識圖譜的增量構建

1.1 時序知識圖譜定義

時序KG 是由不同時刻下KG 組成的序列，把初始時刻的KG 記為，隨著時間的推移，增量變化如下：

其中，G(0 ≤≤)表示時刻的KG。

隨著時間推移，將數據中蘊含且符合G的新知識增量構建到G中，得到G，同時將新的實體關系添加到E和R中，進而得到E和R。該過程可表示為：

其中，Δ表示這個時段所產生的新知識，即新三元組集合。

1.2 增量構建

其中，P為集合中所有三元組包含實體的集合，P為集合中所有三元組包含關系的集合。

圖2 實體與關系向量空間Fig.2 Vector space of entity and relation

然后，將向量轉化到超平面上（記為d），那么嵌入帶來的損失表示為：

其中，為三元組集合，即正樣本集合；′是構造的負樣本三元組集合；[·]是一個正值函數。

為了使構建數據集較大時的損失最小，并提高構建效率，利用隨機梯度下降算法來獲取最小值。具體而言，每次隨機抽取出個正樣本（記為），然后為中每個三元組構造一個負樣本，再把這些正樣本和負樣本合并為一個集合（記為）。隨著梯度的下降，不斷迭代更新向量位置，從而得到損失最小的G的表示模型。上述思想見算法1。

從G構建G

隨機梯度下降計算過程中，每次選取個正樣本以及構造個負樣本，則采樣計算損失需要次。假設梯度下降迭代步數為次，即while 循環執行次，因此該算法的時間復雜度為(·)。

2 新三元組與當前KG 的吻合度計算

2.1 吻合度計算

為了保證時刻所添加的知識與G相吻合，本節提出吻合度計算模型，用于度量三元組與當前KG 的吻合程度。首先，從時刻所產生的新知識中抽取出三元組集合Δ，然后將Δ嵌入到G的向量空間中，并且從兩方面來度量吻合度：（1）模型吻合度，即三元組是否能夠與G的增量構建模型相吻合；（2）語義吻合度，即三元組能否與G的語義信息相吻合。

模型吻合度：由于G是通過時序KG 增量構建模型得到的，基于式（2）計算出(,,)∈Δ與G的模型吻合度：

其中，表示時刻，(,,)越接近0，吻合度越高。

語義吻合度：由于G中關系的數量遠遠小于實體的數量，分別計算每個實體∈E與(,,)∈Δ中、的余弦相似度，即度量其與G上節點的相似度及相似度的最大值，如式（5）所示：

在任意三元組(,,)中，若或與當前KG 中某個實體相似，則說明該實體與G的語義信息相吻合。具體而言，比較cos和cos，把其中較大值作為該三元組與G的語義吻合度，方法如下：

其中，若或與E中有相同的實體，則該三元組為目標三元組。

為了得到該三元組與G的吻合程度，用激活函數把兩個因素構造出一個特征向量，用來表征每個三元組的特點：

然后利用式（8）的激活函數將特征向量轉化為權值(,,)∈[0,1]，將其作為評判三元組與當前KG 的吻合度的依據。

其中，是一個非線性激活函數，和表示在訓練時可以調節的參數矩陣。(,,)越接近1，表明該三元組與G的吻合度越高。

2.2 提取最優三元組集合

不難發現，(,,)很小的三元組也可能與當前KG 中的知識相關。例如，待添加的三元組“（獨龍族，節日，卡雀哇）”和“（卡雀哇，活動，剽牛祭天）”，前者權值較高，但后者較低。若只設置閾值，后者可能不會添加到KG 中。因此，不僅要提取權值較大的三元組，還要找到那些權值不高但與當前KG 間接關聯的三元組，進而獲取集合Δ的最優子集和最大權值，即最終的目標函數。對此，本文提出基于貪心策略的提取最優子集合算法，使子集用最少的三元組來表征集合Δ。由于KG 中實體數往往大于關系數，把最優子集和Δ中的所有實體分別記為P和Δ，給出約束條件P≈Δ，使集合表征集合Δ。該問題描述如下：

其中，表示最優子集的最大權值。

對此，先找到集合Δ中權值大于閾值的三元組，將其添加到集合中，并更新集合P、權值，再從Δ中去除它。此外，為了找到那些權值不高但可以添加的三元組，先找到能夠與集合中任一三元組相連接的其他三元組放入一個候選集合，進而從中選擇權值最大者并添加到中。直至找不到能夠連接的其他三元組（即=?），返回最優子集和權值。具體步驟如算法2 所示。

提取最優子集

算法2 中，假設集合Δ包含個三元組，那么for 循環需要執行次。若候選集中有N個元素，則第二個while 循環的時間復雜度為(·N)。最壞情況下算法的時間復雜度為(·N)。

算法2 執行到第(1 ≤≤)步時，選擇的個三元組包含在最優解子集中。

令集合Δ為={,,…,s}。當=1 時，選擇集合中權值最大的元素。顯然，它是最優解子集中一個元素。否則，將這個權值最大的元素添加到中則會出現實體重疊，因此讓其與產生實體重疊的元素替換，可以得到一個更好的最優解，矛盾。假設前(1 ＜≤)步選擇的元素是最優解的一部分，則在進行第+1 步時，與其相連的元素中權值最大的元素一定包含在最優解中。否則，將該元素放入中會出現實體重疊，因此把產生實體重疊的元素替換為該元素，可以得到一個更好的最優解，矛盾。推廣到前步依然成立，則定理成立。

通過定理可知，算法2 的輸出為最優解，則通過最優子集合就能增量構建得到G，進而隨著時間推移，不斷提取最優三元組集合，從而實現時序KG 的增量構建。

3 實驗結果

3.1 數據集

為了模擬時序KG 的增量構建過程，將Wikidata（http://dumps.wikimedia.org/wikidatawiki/entities）、CNDBpedia（http://www.openkg.cn/dataset/cndbpedia）、Freebase（https://developers.google.com/freebase）作為測試數據集，并按照其發布時間來劃分三元組添加的順序。通過實驗測試本文提出的時序KG 增量構建方法的效率及有效性，同時與典型的KGC 方法進行實體預測結果比較。上述數據集中所包含的實體、關系和三元組個數的統計信息如表1 所示。

表1 數據集Table 1 Datasets

3.2 效率測試

與+1 時刻的數據集對應的KG 記為G，前一時刻的KG 記為G。使用本文方法，將從時刻到+1 時刻新增的三元組作為集合增量地構建至G中，進而得到G。

首先，針對添加不同數量集的三元組集合（新知識），在同一數據集下測試其執行時間，如圖3 所示：（1）增量計算的時間，即完成三元組吻合度計算和得到最優子集合的執行時間；（2）構建時間，即算法1 的執行時間。可以看出，在不同數據集下，隨著數量集的增加，執行時間也大幅上升，特別是在Freebase 下的平均增量構建時間約是Wikidata 下的13 倍。另外，對于不同數據集中添加相同數量的三元組，數據集越大，增量構建時間越長，在CN-DBpedia 與Wikidata 中共同添加10個三元組，前者的執行時間接近后者的兩倍。

圖3 不同數據集下的Gi 增量構建時間Fig.3 Execution time of incremental construction of Gi with different datasets

然后，測試了算法1 不同迭代次數、不同數據集情形下的構建時間，如圖4 所示。可以看出，模型構建時間隨著迭代次數增加而增加，其中三元組過億的Freebase 迭代1 000 次的時間相較于100 次增加了接近1.3 倍。

圖4 不同迭代次數下Gi+1 的構建時間Fig.4 Execution time of Gi+1 construction under different iteration times

3.3 有效性測試

為了驗證吻合度度量模型以及增量構建算法的有效性，使用準確率(Precision，)、召回率(Recall，)和1 值來評價提取結果，三個指標的計算方法如下：其中，為提取出能夠添加到G中的三元組個數；為能被檢索到的三元組個數，即進入過候選集的三元組個數；為所有需要添加的三元組個數。

首先，測試了算法2 中閾值對提取結果的影響，如圖5 所示。可以看出，隨著閾值的減小，準確率、召回率和1 值都有所上升。特別地，在數據集CN-DBpedia 中，當閾值從0.8 到0.7 時三個指標的上升幅度最大，都接近0.15。這是因為CN-DBpedia 中有一些孤立三元組且權值小于0.8，導致提取數量驟增，當閾值不超過0.7 時，結果較為穩定。

圖5 不同閾值下的提取結果Fig.5 Extraction results under different thresholds

另外，從Freebase 數據集中提取一定數量的三元組，記為FB50K。在該數據集下，與一些現有的KGC方法進行抽取效果的對比，測試了閾值的改變對提取結果的影響，如圖6 所示。

圖6 不同方法的提取結果Fig.6 Extraction results of different methods

可以看出，本文提出的增量構建方法的準確率、召回率和1 值均高于其他KGC 方法，尤其是在閾值為0.7 時，本文方法的準確率提升了0.06 以上，這是因為算法2 能夠顧及一些權值較低但與當前KG 相符的三元組，而其他KGC 方法無法提取出這些三元組。同時隨著閾值的上升，雖然提取到符合的三元組數量有所下降，但本文方法的三個指標仍然高于其他方法。

接著對Δ進行劃分，其中一部分三元組是與G相關聯，記作Δ={(,,)|∈E或∈E}；另一部分則與G無關聯，記作Δ={(,,)|?E且?E}，把Δ在Δ的占比記為(0 ≤≤1) 。然后，在不同數據集下測試了占比對提取結果的影響，如圖7 所示。可以看出，隨著無關三元組的減少，提取效果越來越好。從占比0.8 到0.5，其準確率大幅提升了接近0.3。

圖7 不同占比下的提取結果Fig.7 Extraction results under different proportions

為了得到盡可能好的數據提取結果，將閾值設為0.7，占比設為0.5，在同一數據集下測試提取結果的有效性，如表2 所示。可以看出，隨著新增三元組數量的增加，增量構建結果的準確性也有所上升。同時，也統計了不同數據集下G的增量構建后三元組、實體和關系新增的數量，如表3 所示。總之，若當前KG 與所添加的新知識相關度較高，則提取效果更好，可更好地豐富當前KG。

表2 不同數據集下的提取結果Table 2 Extraction results under different datasets

表3 不同數據集下的增量構建結果Table 3 Results of incremental construction under different datasets

3.4 實體預測

為了驗證本文方法對于KGC 任務的有效性，再從Freebase 數據集中提取一定數量的三元組，記為FB500K。在FB50K和該數據集下，與其他方法進行實體預測并對比預測結果。基于TransE、TransH和TransD算法，把新知識直接嵌入到模型中訓練，進而完成預測，分別記為TransE(OW)、TransH(OW)和TransD(OW)。

針對不同數據集，用平均排序（mean rank，MR）和HITS@50 來評價預測結果的有效性，MR 值越低，HITS@50 值越高，則說明結果更加準確，結果如表4所示。可以看出，本文方法的實體預測結果較好，因為其能夠過濾新知識中的部分無關信息（孤立三元組），使實體總數目相對于TransE(OW)較少，進而MR和HITS@50值較好。

表4 開放世界下實體預測結果Table 4 Open-world entity prediction results

然后，也在封閉世界下與其他KGC 方法進行實體預測，結果如表5 所示。可以看出，時序KG 增量構建方法整體優于其他方法。這是因為算法2 不僅能夠把權值較大的三元組添加進去，還能把自身權值較低，但與權值較大的三元組有關聯的三元組添加進去，使補全的結果較為全面。總體而言，相比開放世界和封閉世界下的KGC 方法，本文方法對于實體預測都具有一定優勢，驗證了本文方法的有效性。

表5 封閉世界下實體預測結果Table 5 Closed-world entity prediction results

4 結束語

本文提出了時序KG 的增量構建方法，通過構建吻合度計算模型和提取最優子集算法獲得最優三元組集合，并將該集合增量構建到KG 中。實驗結果表明，本文方法能夠有效地提取出較為吻合的三元組并增量構建到KG 中，但是在實體預測任務中存在對TransH 模型的依賴，導致預測結果不夠理想。因此，未來工作將考慮實體關系間的其他特征，更好地表征當前KG，進而改善增量構建模型，提升新知識增量構建的準確率。另外，擬將本文方法拓展到真實場景下，基于數據中蘊含的新知識對領域KG 進行增量構建。