在過去一年的文章中，我們討論了很多關於知識圖譜構建、結合NLP應用的方法。逐漸，這些算法開始深入到許多業務中的搜索、推薦工作中。很自然的做法是，為了契合各個業務的實際場景，我們會為每個業務方獨立出各自的知識圖譜，方便與業務方共同管理數據。隨著業務深入，很快會發現單個業務知識圖譜因為規模小，在文本語義理解類任務上非常受限，此時需要將多個知識圖譜進行融合，打通知識邊界。比如在丁香園的場景中，有問診、求職、電商、資訊、論壇等業務，背後使用同一套專業醫學知識，而各自業務線又有豐富的職位、商品、科研等數據，另外可以在 OpenKG 找到其他領域或常識類圖譜。融合之後不僅對相關NLP任務效果帶來不小的提升，為後續實現不同業務之間的導流和推薦也提供了想像力。
那麼，兩個（或多個）知識圖譜的融合是怎麼實現的呢？所謂融合，可以理解存在以下三種操作：1）實體詞在新的上下級位置上進行插入；2）不同圖譜中的同義實體詞完成合併；3）三元組關係隨著實體詞位置變化而動態調整
單看這些任務，類似的技術我們在《知識圖譜構建技術綜述與實踐》、《抽取獲得的知識圖譜三元組該如何質檢？》和《如何擴充知識圖譜中的同義詞》均有部分提及。本文我們來系統地看一下在不同階段，圖譜融合該採取什麼策略，以及相關的算法論文調研。
一.小規模知識圖譜如何進行圖譜融合業務圖譜建立初期，圖譜規模較小，基於知識表示的圖譜融合方法壁壘比較多，基本以人工為主力，那麼怎麼才能儘可能的減少人工成本呢？圖譜融合的最早做法是利用First-Word-First-Sense，在WordNet中找到OOV的適當位置。First-Word-First-Sense策略就是將新的概念連結到其定義中的第一個與其詞性相同，並源於WordNet中的同一gloss（術語詞彙表）分組的詞。這種方法在英文數據中適用性比較強，並且能得到比下面介紹的三種方法更好的效果，但這卻取決於我們的圖譜和WordNet的組織方式是否相同，即每個詞語都有一個義原，並有明確的詞性，每個概念標註了基於義原的定義以及詞性、情感傾向、例句。實際上並不是所有的圖譜都嚴格遵循語言學結構，因此對於領域圖譜First-Word-First-Sense方法並不適用。《VCU at Semeval-2016 Task 14: Evaluating similarity measures for semantic taxonomy enrichment》VCU系統設計了三種無監督融合方式。首先，通過詞性或實體類型進行候選集確定。其次，給每個候選集實體賦予一個分數，分數通過基於字典的相似性度量得到（分別使用Lesk，一階向量，二階向量三種方法進行分數計算）。最後，將得分最高的候選集分配給OOV；如果得分大於特定閾值，則標記為merge（這兩個詞是同義的），否則標記為attach，即OOV是synset的下位詞。Lesk度量通過計算兩個定義之間出現的一個或多個連續單詞的最長序列，來量化兩個術語之間的相關性，最終權重為序列長度的平方，目的是較長重疊賦予更大的權重。一階向量由候選集與新實體定義中關聯單詞出現的次數構成，利用餘弦相似性來量化相似程度。但缺點是向量矩陣過於稀疏。因此在二階向量度量中，為定義中的每個單詞創建一個向量，其中包含其在外部語料庫中共現的單詞，將詞向量平均值作為新實體和候選集的二階向量。VCU系統算是比較Naive，但有效的方法，尤其是對一些字面上和定義中具有上下級暗示的實體對，如：糖尿病，1型糖尿病。利用簡單的語義相似性度量，分數高的實體對質量也比較好。但不足也較明顯，首先在於閾值的設定，低於閾值即為下位詞，這將造成一些分數極低的噪音插入圖譜；其次在於定義中的多義實體的出現和特定的詞彙；最後，VCU系統其實並沒有充分的利用已有圖譜的結構。《TALN at SemEval-2016 Task 14: Semantic Taxonomy Enrichment Via Sense-Based Embeddings》TALN系統與VCU的輸入相同，均為新實體、詞性及其相關定義。VCU系統在新實體定義的使用上存在以下問題：新實體的定義可能沒有明確提到其最接近WordNet候選集，為解決這一問題，TALN在向量上採用了基於BabelNet的SENSEMBED模型，即更多地考慮句法，詞性，短語。首先對每個定義進行詞性標註和句法分析，生成一組名詞和動詞短語，然後利用詞和短語對定義進行向量空間表示。最後對候選詞排序，獲取最終結果。在父級候選部分，TALN通過深度優先遍歷WordNet，直到與新實體詞性相同的詞根為止，獲取新實體定義的語義解析樹中的詞根集，作為父級候選。設計了三種擴充父級候選方式：（2）以定義中的centroid sense進行擴充（1）確定定義的centroid sense之後，找到定義中哪個chunk最接近centroid sense，以此擴充。《MSejrKu at SemEval-2016 Task 14: Taxonomy Enrichment by Evidence Ranking》TALN雖在詞法，句法分析上進行了大量的改進，但仍沒有考慮實體消歧問題，並且依然採用簡單的相似度排序做法。MSejrKu系統嘗試了兩種算法，其一是使用Mate解析器對描述語句進行詞性和依賴性分析，獲得詞彙，句法特徵和Skip-Gram embeddings，作為二分類器（線性logistic回歸分類器和一個包含100個單位的單隱層非線性神經網絡分類器）特徵，進行新實體父級預測。方法二與以往研究都不同，TALN在父級候選部分做了詳細的數據分析，並依據分析結果設計模型。首先它定義了以下概念：（1）wc與sc：wc代表從某一句實體定義中篩選出的同義詞集；sc代表從所有實體定義中篩選出的同義詞集（2）g：同義詞集需要滿足條件g，即同義詞集中的所有詞根必須出現在新實體的定義中，並且新實體與同義詞在taxonomy上的路徑最短。路徑長度分別為δ(g, sc(t, g))，δ(g,wc(t, d, g))。通過統計發現，發現新實體與δ(g, sc(t, g))，實體定義與δ(g,wc(t, d, g))之間都服從Zipfian分布，並由此推斷優化每一個wc，即可得到最優化的sc。在具體的排序算法中，MSejrKu採用個性化Pagerank進行詞義消歧和排序操作，為解決訓練數據不足導致的模型泛化性不足問題，將pointwise轉化為pairwise，將排序問題作為逐點回歸或成對分類來處理，通過Gaussian kernel SVM確定每一句的候選父級wc，最後採用投票方式或Pagerank決定所有句子中的候選父級。二. 初具規模時的圖譜融合不難發現，當圖譜規模較小時，大多採用基於詞法句法，無法利用圖層次結構相關特徵。當圖譜規模達到一定規模，新實體融合主要依靠知識表示和圖結構相關特徵設計並改進模型。《Enriching Taxonomies With Functional Domain Knowledge》與上述論文不同，本文應用了大量的圖語義特徵和圖中心度量特徵，因此在語義理解上，會有明顯的提升。本文的主要挑戰是找到一個計算度量，它能夠代表圖譜中獨立於語言和領域的語義邏輯，將新概念插入到知識結構，不破壞之前網絡的語義完整性關係。算法面向已存在的概念框架和新的概念，學習了一個高維的詞向量。用於對比新概念和相鄰概念之間的相似度，來預測這種潛在的連結新舊概念之間的父子關係，為了解決這個挑戰，本文將高效圖論特徵和利用額外知識的語義相似度特徵進行結合。其中選取了大量的圖特徵和語義特徵：Katz相似度，RandomWalk Betweenness Centrality（如果想嘗試更多的中心度量特徵，可參考論文《Unsupervised graph-based topic labelling using dbpedia》)，PMI等訓練集的正例是圖譜中已經存在的概念的父級，反例是新概念通過KNN隨機獲得的父級。每一個概念取相同數量的正例和反例，模型採用LambdaMART，對每對候選父子級進行排序，最終判斷出最適合父子級的新實體和已有實體。不難發現，上一篇文章雖然使用了圖結構相關特徵，也獲取了語義子圖，但並沒有將重點放在上下級結構的學習上，同時在新實體的抽取方面也沒有做過多的研究。接下來的算法，不僅著重學習了圖譜中的父子級結構，同時也研究了如何找到符合目前圖譜結構的新實體。《Using Taxonomy Tree to Generalize a Fuzzy Thematic Cluster》本文基於已有圖譜結構，藉助模糊主題聚類算法（FADDIS），發現並概念化新發現的實體，通過最小化懲罰函數，找到新實體在圖譜中的位置。為什麼要選擇FADDIS算法：（1）Laplacian偽逆規範化（Lapin）：通過模擬熱分布實現相似數據轉換，從而使聚類結構更清晰；（2）可加性：相似值是多個隱藏主題的貢獻之和；（3）非完整性：集群不一定涵蓋所有可用的關鍵短語，因為文本集合可能有一些無關短語。懲罰函數主要由三個部分組成：head subjects， gaps，offshoots。其中head subjects代表模糊子集最終對應到圖譜中的中間節點（概念節點），gaps代表可以被插入的位置，offshoots代表應該在head subjects下但插入到錯誤未位置的葉子節點。通過Parsimonious Generalization of Fuzzy Sets算法，得到模糊子集H。通過對head subjects， gaps，offshoots最小化，將模糊子集正確的融合進已有圖譜，並保證圖譜結構的整體準確性。三. 兩個完整圖譜的融合—實體對齊兩個完整圖譜的融合其實本質上是不同領域實體詞之間的實體對齊，從而形成語義上的連結，是後續的不同業務之間推薦的基礎。
(一) String-Similarity-based Entity Alignment
基於字符串相似的實體對齊方法，大致分為兩種，一是與實體相關的語義字符串相似度，如定義，屬性。《RDF-AI: an Architecture for RDF Datasets Matching, Fusion and Interlink》RDF-AI實現了一個由預處理、匹配、融合、互連和後處理模塊組成的對齊框架，提出一種基於屬性的實體對匹配算法：基於序列對齊的模糊字符串匹配算法和詞義相似度算法。後者有兩種實現：基於WordNet的同義詞比較算法和基於SKOS的taxonomy相似算法（詳見https://www.w3.org/TR/2005/WD-swbp-skos-core-guide-20051102/），這兩種算法也可以結合使用。利用上述方法計算屬性匹配相似度，得到兩圖中所有可能對齊的屬性對，通過對屬性對相似度求和得到實體相似度。最終實體相似度最高者，被認為是一個實體。但缺點非常明顯，即存在WordNet和SKOS這樣的外部圖譜，並且屬性中的詞必須存在在外部圖譜中。《Limes: a time-efficient approach for large-scale link discovery on the web of data》LIMES基於三角不等距離逼近算法，推導距離的上下邊界條件，使用這些邊界條件來減少映射比較次數。被分割的空間內可以計算該區域中的每個實例與其他實例之間的相似度距離的精確近似。通過這些方法，可以在不犧牲精度的情況下有效地發現連結數據源之間的連結。LIMES在相似度距離計算上提供了多種方案，包括字符串，語義，向量，point-set等（詳見http://dice-group.github.io/LIMES/#/）。《Holistic Entity Matching Across Knowledge Graphs》也有一些研究使用圖形相似性來提高實體對齊性能。本文提出了一種基於Personalized PageRank的知識庫實例對齊算法（HolisticEM）。除了經典的Personalized PageRank，創新之處有兩點：（1）考慮了每個實體中，每個單詞對整個實體的語義貢獻程度，一個單詞的IDF得分越低，這個單詞共享的實體就越多，因此，這樣一個詞與其實體的區別越小。（2）Pairs Graph構建：首先通過計算基於IDF的實體屬性相似度選出種子對集合，其次，使用與種子對相連接實體，並將必要的新實體對和邊添加到Pairs Graph圖中，擴展原有種子對。這樣的種子對篩選方式要比n-hop方式獲取到該實體更多的語義信息。(二) Embedding-based Entity Alignment
基於字符串相似性的實體對齊，大多都局限在實體，定義，屬性的字符串描述上，無法對圖譜結構進行量化。基於知識表示的實體對齊方法不僅能夠學習已有結構中的潛在聯繫，同樣也能靈活添加更多語義特徵。《Entity Alignment between Knowledge Graphs Using Attribute Embeddings》不同於TranE和PTransE等模型，學習實體或者路徑，本文還考慮了圖譜中的實體屬性值，進一步豐富了實體的語義環境。算法分為三個部分：謂詞對齊、知識表示學習和實體對齊。基於嵌入的實體對齊要求兩個KG的嵌入（關係和實體嵌入）落在同一向量空間中。為了給關係嵌入提供一個統一的向量空間，我們基於謂詞相似度（即謂詞對齊）合併了兩個KG。謂詞對齊模塊查找部分相似的謂詞，並使用統一的命名方案重命名它們。基於這個統一的命名方案，將兩圖合併。然後，將合併後的圖分解為一組關係三元組和一組屬性三元組，用於表示學習。表示學習模塊使用結構表示學習和屬性表示學習，共同學習兩個KG的實體表示。使用關係三元組學習結構表示，而使用屬性三元組學習屬性嵌入。最初，來自G1和G2的實體結構表示屬於不同的向量空間，因為來自兩個KG的實體使用不同的命名方案表示。相反，從屬性三元組中學習到的屬性表示可以落在同一向量空間中。即使屬性來自不同的KG，但屬性字符串基本類似，因此可以從屬性字符串中學習字符表示。然後，利用屬性字符表示，將實體結構表示帶入同一向量空間中，使得實體嵌入能夠從兩個KGs中獲取實體間的相似性。《Iterative Entity Alignment via Joint Knowledge Embeddings》大多數現有的方法通常依賴於諸如維基百科之類的實體外部信息，並且需要大量的人工特徵來完成對齊。本文提出了一種基於聯合知識表示的實體對齊方法。算法分為三部分：知識表示，聯合表示，實體對齊迭代。知識表示部分採用了經典的TransE模型。而在聯合表示部分，為將不同KG的實體和關係映射到一個統一的低維語義空間，基於一組已對齊的實體子集，設計了三種模型：(1) 受到基於翻譯的KRL方法啟發，將對齊視為實體之間的一種特殊關係，在需要對齊的實體之間執行特定的翻譯模型來學習聯合表示。(2) 線性變換模型，即學習兩實體之間的線性變化矩陣。(3) 參數共享模型：利用變量之間依賴性的先驗知識替代正則化變量。最終通過實體迭代對齊方式，縮小聯合語義空間中的語義距離，提高實體對齊性能。《Collective Embedding-based Entity Alignment via Adaptive Features》以往研究中，基於知識表示的解決方案都是獨立的處理實體，而沒有考慮實體之間的相互依賴性。此外，大多數基於知識表示的實體對齊方法存在以下問題：（1）在表示層融合不同特徵，生成統一的實體表示，進行對齊，這可能會導致信息丟失。（2）在結果層使用手動調整的權重聚集特徵，這在特徵數量不斷增加的情況下並不實用。針對這些不足，本文提出了一個基於集合嵌入的自適應特徵融合實體對齊框架。首先使用三個具有代表性的特徵，即結構、語義和字符串，來捕捉異構KGs中實體之間不同方面的相似性。然後通過自適應特徵融合策略動態分配權重。最後，將實體對齊定義為待對齊實體之間的stable matching問題，(詳見論文《Secure stable matching at scale》)，並使用融合特徵矩陣構造偏好矩陣，採用延遲接受算法（deferred acceptance algorithm，詳見論文《Deferred acceptance algorithms: history, theory, practice, and open questions》）實現實體對齊。假設有三個源實體u1，u2，u3和三個目標實體v1，v2，v3。給定融合相似度矩陣M，其中實體對應行/列中的值表示其偏好（首選較大的值）。源實體按照偏好矩陣，依次向目標實體進行對齊。四. 總結文章分別介紹了在不同圖譜規模下，不同的圖譜融合算法，我們可以根據當下的數據情況進行選擇。當圖譜規模較小時，我們還是推薦上文介紹的小規模圖譜融合的方法，可解釋性高，算法簡單，同時可達到不錯的效果。當圖譜規模非常大時，圖譜自身就是一個可解釋性非常高的模型，此時採用層次聚類或知識表示抽象化圖譜結構，才能達到較好的效果。在實際應用中，需要根據不同的業務建立不同的圖譜，散落在各業務線的數據，永遠只是服務於自身業務，並不能發現業務之間的潛在聯繫。為了實現跨業務語義解析和推薦，圖譜融合是關鍵，需要根據不同業務的特點選擇不同的融合算法，複雜不一定是最好。從以上研究中可以看到，如何豐富並更好的抽象新實體的外部語義環境和其在圖譜中的關聯結構，依然是今後研究的重點。參考文獻
[1].《VCU at Semeval-2016 Task 14: Evaluating similarity measures for semantic taxonomy enrichment》
[2].《TALN at SemEval-2016 Task 14: Semantic Taxonomy Enrichment Via Sense-Based Embeddings》
[3].《MSejrKu at SemEval-2016 Task 14: Taxonomy Enrichment by Evidence Ranking》
[4].《Enriching Taxonomies With Functional Domain Knowledge》
[5].《Using Taxonomy Tree to Generalize a Fuzzy Thematic Cluster》
[6].《RDF-AI: an Architecture for RDF Datasets Matching, Fusion and Interlink》
[7].《Holistic Entity Matching Across Knowledge Graphs》
[8].《Entity Alignment between Knowledge Graphs Using Attribute Embeddings》
[9].《Iterative Entity Alignment via Joint Knowledge Embeddings》
[10].《Collective Embedding-based Entity Alignment via Adaptive Features》