基于圖嵌入的社交賬號與知識圖譜實體對齊

郭 強，譚菊仙，劉家祝

(江南計算技術研究所，江蘇 無錫 214085)

0 引 言

隨著社交網絡的日益普及，微博、Twitter、Facebook等社交媒體成為人們傳播新事件、分享新知識的主要媒介。特別是知識圖譜中大量的人物、組織在社交網絡中都開設有賬號。社交媒體實時更新的信息可以幫助擴充知識圖譜內容，而知識圖譜在社交網絡分析中可以起到知識引導的作用[1]。社交媒體和知識圖譜互相融合對知識圖譜擴充與社交網絡分析等具有重要作用，而社交賬號與知識圖譜實體對齊是這兩類數據融合的關鍵問題。

以實體為中心的知識圖譜和以賬號為中心的社交網絡在數據上呈現出不同的特點。第一，知識圖譜的質量一般要求較高，YAGO具有95%的準確度[2]。而對于社交媒體來說，數據通常是嘈雜的，甚至存在虛假信息。第二，知識圖譜一般采用標準的、易于計算機訪問的數據結構。而對于社交媒體來說，數據主要呈現非結構化特征，多數受限于社交媒體平臺的API訪問限制。第三，社交媒體能夠提供實時的最新信息，而知識圖譜的更新一般滯后數小時到數月之間不等[3]。這種知識更新的滯后，限制了知識圖譜在實時性要求較高場景中的應用。這些特點給社交媒體和知識圖譜之間的數據融合帶來挑戰。

文中充分利用社交網絡和知識圖譜的結構特點，研究社交賬號與知識圖譜實體的對齊技術，將社交賬號與知識圖譜中的實體鏈接起來。與實體鏈接過程類似，社交賬號與知識圖譜實體也為兩個步驟[1]：候選實體集生成與目標實體選擇。以Twitter賬號與Wikidata實體對齊為例，圖1給出了一個對齊過程。

圖1 Twitter賬號與Wikidata對齊

在候選實體生成步驟中，綜合使用多種搜索策略，對搜索結果的實體類型進行過濾，只保留人物實體和組織實體。在目標實體選擇階段中，提出了一種新的方法：基于圖嵌入特征的算法，利用從社交媒體賬戶中提取的社交關系，通過知識搜索服務映射成知識圖譜的子圖，利用知識圖譜的圖嵌入特征來生成候選實體特征向量，然后通過感知機分類器來選擇目標實體。

1 相關工作

實體鏈接一般是指將文本中的實體提及(entity mention)鏈接到知識圖譜實體的過程[4]。文中研究的問題是將社交賬號鏈接到知識圖譜的實體，與通常的實體鏈接過程類似。Usbeck R等人[5]發布的AGDISTIS系統試圖挖掘知識圖譜中的子圖的節點主題一致性規律，完成批量的實體鏈接工作。在目標實體選擇階段他們采用HITS[6]或PageRank[7]算法，選取重要程度最高的實體為目標實體。AGDISTIS系統用于社交實體對齊存在一定局限性，主要原因在于AGDISTIS系統使用啟發式算法，沒有考慮圖節點的潛在語義特征。

社交賬號與知識圖譜實體的對齊問題近年來受到學者的關注。2017年Trendo大學的Nechaev Y等人[8]首次提出該問題，他們研究了Twitter賬號與DBpedia之間的鏈接問題，基于監督學習給出了初步解決方案并提出了SocialLink問題，指出跨社交網站的賬號鏈接是其中的難點和重點。文獻[9]提出了對SocialLink問題的改進，引入了Social Embedding的概念，與知識圖譜中的知識表示學習方法配合使用，以提高對齊的效果。

文獻[1]提出一個基于子圖相交的啟發式算法用于對齊社交賬號與知識圖譜實體，并利用Twitter數據與Wikidata數據構建了一個社交賬號與知識圖譜實體對齊數據集，在該數據集上實現了0.637的準確率。這個研究揭示了基于社交關系映射的知識圖譜子圖，在目標實體“附近”存在聚集特性，利用這一特性預測目標實體能夠取得了一定的準確率。然而這種啟發式算法沒有考慮實體的語義特征，特別是近年來知識圖譜表示學習取得較好進展[10]，實體的圖嵌入特征能夠表達實體的語義信息，對實體對齊具有十分重要的作用。文中采取文獻[1]的研究框架，探討實體的圖嵌入特征在實體對齊上的應用。

2 問題定義與方法

目的是針對給定的Twitter賬號t，在知識圖譜KG中找出對應的實體et。令集合C為賬號t在KG中生成的候選實體集，C={c1,c2,…,cn}，函數φ表示根據賬號t在知識圖譜KG中生成候選實體集，函數ψ表示計算候選實體ci為正確實體的概率。鏈接過程可以形式化地描述為如下兩個部分：

(a)候選實體集生成：C=φ(t,KG)。

2.1 候選實體集生成

在候選實體生成階段，主要對實體類型進行過濾。由于社交賬號對應的實體只能是人物或組織，對于知識圖譜搜索服務的返回結果，進行實體類型過濾，只保留人物和組織實體。為了使社交賬號對應的實體盡可能在返回結果中，使用文獻[1]中的用戶名策略、用戶名去符號策略、用戶名分割策略等三個搜索策略，對搜索結果取并集。算法描述過程如下：

算法1：候選實體生成算法getCandidates。

輸入：社交賬號t；

輸出：候選實體列表C。

步驟：

1.C←NULL

4. if fitDomain(c) then:

5.C=C∪c;

2.2 基于圖嵌入特征的實體對齊算法(Arep)

2.2.1 社交子圖生成

從獲取的數據中提取與目標賬號相關的社交賬號以組成社交子圖SGsub。具體來說，從目標賬號數據中提取關注(following)、提及(mention)、轉發(retweet)和引用(quote)中出現的賬號，定義目標賬號社交子圖實體集合為SGsub，那么提取過程可以形式化表述如下：

SGsub=SGfollowing∪SGmention∪SGretweet∪SGquote

(1)

其中，SGfollowing等子圖表示從目標賬號相關數據中提取出來的社交賬號集。由于某些賬號的粉絲數量巨大，且粉絲對實體對齊算法效果影響不明顯，在社交子圖中不考慮粉絲賬號。

2.2.2 結構投影子圖生成

社交子圖生成之后，根據每個社交賬號的候選實體，構建候選實體之間的知識圖譜子圖。特定賬號的社交子圖投影到知識圖圖譜子圖的過程見算法2。

算法過程描述如下：

算法2：結構投影算法。

輸入：目標賬號t；有關目標賬號t的爬取數據data；知識圖譜KG；

輸出：結構投影子圖KGsub。

步驟：

1.KGsub←φ

2.SGsub←GetSubSocialGraphFromSavedData(t,data)

3.RA←getRelateAccount(t,m)

4.FOR rai∈RA

5.CE←CE∪KGSearchService(rai,Tr,k,KG)

6.END FOR

7.KGsub=subgrpah(CE)

8.RETURN KGsub

2.2.3 圖嵌入特征構建

在知識表示學習領域，以TransE[11]為代表的翻譯模型在知識圖譜補全問題上取得較好的效果，能一定程度捕獲實體的語義信息，文中使用TransE模型的實體嵌入特征。結構投影子圖KGsub在結構上存在聚集特征[1]，文中充分利用這個特點來構造候選實體的特征向量。使用一種迭代刪除KGsub中離散實體，保留最“密集”處核心實體的算法。該算法每次迭代計算KGsub的質心，刪除一定數量離質心最遠的實體，最終保留特定個數核心實體。算法描述如下：

算法3：核心實體集生成算法。

輸入：投影子圖KGsub；實體嵌入特征列表W；離散實體刪除率p；核心實體保留數m。

輸出：核心實體集Score。

步驟：

1.Score←GetVectors(KGsub,W)

2.Ldistance←φ

3. LOOP

5. FORIiINScore

6.Ldistance←Ldistance∪EuclideanDistance(Icentroid,Ii)

7. END FOR

8.Ldistance←SortListByDistanceDesc(Ldistance)

9. IF |Score|×p>1 THEN

10.k←|Score|×p

11. ELSE

12.k←1

13. END IF

14.Score←RemoveTopKElement(Score,Ldistance,k)

15. IF |Score|≤mTHEN

16. BREAK

17. END IF

18.Ldistance←φ

19. END LOOP

20. RETURNScore

利用該算法得到的核心實體集Score，構造每個候選實體特征向量Ifeature如下：

(2)

其中，Ii∈Score，cj為候選實體的特征向量。知識表示學習工具OpenKE[12]使用TransE模型對wikidata全量數據進行了訓練，文中直接使用其訓練結果。

2.2.4 目標實體選擇

目標實體選擇以特征向量Ifeature為輸入，計算候選實體為目標實體的匹配值，最后根據這一組候選實體匹配值，選擇最終對齊實體。

在目標實體匹配值計算的設計中，為了能夠更好處理Ifeature這一類特征向量，引入多層感知機(MLP)模型[13]的神經網絡來計算匹配值。MLP模型在結構上是一個多層的全連接網絡，除了輸入層(input layer)和輸出層(output layer)外，中間還有若干隱層(hidden layer)，層與層之間全連接，隱層和輸出層存在激活函數。MLP模型采用梯度反向傳播算法訓練參數。

文中設計了一個單隱層的MLP模型，具體結構如圖2所示。

圖2 目標實體匹配值計算模型結構示意圖

其中，隱層的大小等于Ifeature的維數乘以一個給定的隱層大小系數σ，隱層激活函數為ReLU函數，輸出層大小等于1，輸出的結果即為目標實體匹配值，vscore∈[0,1]。損失函數采用均方差損失函數(MSELoss)，由于模型輸出大小為1，故損失函數公式如下：

LMSELoss=(Vscore-Vlabel)2

(3)

其中，Vlabel為訓練數據標簽值。訓練過程的反向傳播調整參數的過程使用了Adam[14]算法作為優化器。為了防止過擬合，模型采用L2正則化方法。

針對一個候選實體集C，計算每個候選實體的匹配值Vscore={v1,v2,…,vn}，n為候選實體個數，選擇分值最高的候選對象為目標實體。

3 實驗與分析

實體對齊旨在從候選實體集中選擇最有可能的實體作為目標實體，故最終的結果只有“成功”或“失敗”兩種結果。參考文獻[1]的評價方法，文中衡量方法性能的指標為準確率(Accuracy)。

3.1 對比算法

為了驗證基于圖嵌入特征的實體對齊算法(Arep)的有效性，引入了三種對比算法，分別是：標題匹配法、AGDISTIS[5]算法、子圖相交算法[1]。

3.1.1 標題匹配算法(Atitle)

標題匹配法以Twitter賬號用戶名與候選實體標題字符串的相似度為選擇標準，選擇第一個與Twitter賬號用戶名完全相同的候選實體為目標實體。

3.1.2 AGDISTIS算法(AHITS)

AGDISTIS算法對知識圖譜子圖進行深度為2的廣度優先搜索，從而生成新子圖，然后使用HITS算法計算新子圖的節點權威值，選取權威值最高的節點作為鏈接結果。

3.1.3 子圖相交算法(Asub)

文獻[1]在AGDISTIS算法的基礎上提出了子圖相交算法，它將候選實體進行深度為3的廣度優先搜索，為每個候選實體生成一個子圖，然后將社交賬號相關聯的賬號投影到知識圖譜生成目標子圖，計算目標子圖和候選實體子圖的交集，選擇交集元素最多的候選實體作為最終對齊結果。

3.2 實驗數據

文獻[1]通過Wikidata Query Service[15]，利用SPARQL[16]語言獲取了3 024條具有Twitter賬號的Wikidata實體，其中包含1 379個人物賬號，1 645個組織賬號。然后根據Twitter賬號名，利用網絡爬蟲技術，爬取相關賬號的基本信息、推文及關注賬號列表。為了保證能夠獲取較為可靠的社交關系，去除了推文總數在300條以下且關注總數在100以下的賬號，最終保留賬號2 281個，其中人物賬號1 086個，組織賬號1 195個。

為了進行實驗對比，根據文獻[1]的方法對數據集進行擴充，重新獲取15 962個Twitter賬號作為訓練集和驗證集，其中人物賬號10 256個，組織賬號5 706個，將文獻[1]中的2 281個賬號作為測試集。

3.3 目標實體選擇

基于圖嵌入特征的實體對齊算法涉及的主要超參數如下：

(a)核心實體保留數m。該參數表示核心實體集生成算法返回的核心實體集最終包含的實體個數，取值范圍[20,40,60,80,100]。

(b)隱層大小系數σ。該參數用于MLP模型根據輸入層確定隱層神經元個數的系數，σ∈(0,1]，取值范圍[0.2,0.4,0.6,0.8,1]。

為了選擇最優超參數，按照7∶1的比例將訓練數據集劃分為訓練集、驗證集，使用驗證集進行網格搜索，確定最優超參數組合，見表1。

表1 最優實驗參數組合

在測試數據集上，應用最優超參數組合進行性能評估，我們得到基于圖嵌入特征的實體對齊算法的最終實驗結果Arep。實驗數據集將按照數據類型分為人員、組織、綜合(人員+組織)分別進行實驗。實驗結果Arep與標題匹配算法、AGDISTIS算法、子圖相交算法進行對比，得到實驗結果見表2。

表2 基于圖嵌入特征的實體對齊算法實驗結果

從表2中可以看出，基于圖嵌入特征的實體對齊方法Arep在整個數據集上達到了最好的性能，相比于基于子圖相交的啟發式算法綜合準確率提升了32%。Arep算法的核心是以實體圖嵌入特征為基礎的目標實體匹配值計算模塊，它既能利用圖的聚集特點，又能夠利用實體的語義特征，在獲得更多標記數據的情況下，對齊方法的準確率可以進一步提升。

4 結束語

文中提出了一種將社交賬號與知識圖譜實體進行對齊的算法——基于圖嵌入特征的實體對齊算法(Arep)。通過將目標賬號的社交關系圖映射到知識圖譜中形成子圖，充分利用子圖存在聚集特征的特點，以核心實體集的表示學習向量為基礎構造特征向量，最終通過多層感知機來選擇目標實體。該研究表明了基于圖嵌入特征的實體對齊方法，能夠利用實體的語義特征，從而達到更好的實體對齊效果。該方法在測試數據集上實現了0.842的準確率。Arep算法所利用的社交媒體的社交關系圖以及知識圖譜的圖結構等信息，是普遍存在于社交媒體和知識圖譜中的，所以該對齊方法可以應用于其他的社交媒體和知識圖譜。

下一步的工作可以從兩個方面開展。首先是應用更為高效和準確的投影方法來生成投影子圖，將會有助于提高投影子圖的聚集特征。其次是擴充數據集，加入在知識圖譜中不存在對應實體的社交賬號用于擴展算法和評估算法的性能。