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

劉家祝，郭 強，吳碧偉，曾明勇

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

0 引 言

隨著互聯(lián)網(wǎng)基礎設施的完善和移動互聯(lián)網(wǎng)設備的普及，社交媒體越來越深入社會生活的方方面面。特別是對于公眾人物和組織，社交媒體是他們與外界保持信息流通的重要媒介。社交媒體的數(shù)據(jù)具有實時性高，非結(jié)構(gòu)化等特點。知識圖譜的概念是由Google公司在2012年提出[1]，是一種揭示實體之間關系的語義網(wǎng)絡，可以對現(xiàn)實世界的事物及其相互關系進行形式化描述。知識圖譜的數(shù)據(jù)具有實時性較差[2]、準確度高[3]等特點。

社交媒體和知識圖譜互相利用對方數(shù)據(jù)的特點，將對知識圖譜擴充與社交網(wǎng)絡分析等領域產(chǎn)生積極的促進作用，而社交賬號與知識圖譜實體對齊是聯(lián)通二者的橋梁。文中研究的目的在于將社交賬號當作一種實體，利用社交賬號相關信息和知識圖譜實體相關知識，研究社交賬號與知識圖譜實體的鏈接技術，將社交賬號與知識圖譜中正確的實體鏈接起來。

為了對齊賬號與實體，提出的方法分為兩個步驟：候選實體集生成與目標實體選擇。圖1給出了一個對齊過程的示例。

圖1 Twitter賬號與Wikidata對齊

在候選實體生成步驟中，利用知識庫提供的搜索服務，在不同的搜索策略下構(gòu)建候選實體集。在目標實體選擇步驟中，提出了一種子圖相交算法，旨在利用從社交媒體賬戶中提取的社交關系，通過搜索服務映射到知識圖譜中，形成知識圖譜的子圖，利用子圖存在的相關特性來選擇目標實體。

1 相關工作

社交賬號與知識圖譜實體的對齊問題是近年來在知識圖譜研究領域的熱點問題。2017年Trendo大學的Nechaev Y等人[4]首次提出該問題，他們研究了Twitter賬號與DBpedia之間的鏈接問題，基于監(jiān)督學習給出了初步解決方案并提出了SocialLink問題，指出跨社交網(wǎng)站的賬號鏈接是其中的難點和重點。文獻[5]提出了對SocialLink問題的改進，引入了Social Embedding的概念，與知識圖譜中的RDF graph embedding方法配合使用，以提高對齊問題的評估指標。

實體鏈接是指將文本中的實體提及(entity mention)鏈向知識圖譜實體的過程[6]。文獻[7]研究了不同策略在候選實體集構(gòu)建過程中的作用。文中研究的問題是將社交賬號鏈向知識圖譜實體，故實體鏈接問題在實體鏈接研究框架、實體鏈接步驟及各階段所采用的技術方法等方面[8]對本課題具有較強的參考意義。

Usbeck R等人[9]發(fā)布的AGDISTIS系統(tǒng)試圖利用構(gòu)建知識圖譜中的子圖的方式，完成批量的實體鏈接工作。在目標實體選擇階段，他們采用HITS(hyperlink-induced topic search)[10]或PageRank[11]算法，選取重要程度最高的實體為目標實體。AGDISTIS系統(tǒng)在本課題的數(shù)據(jù)集上取得了0.537左右的準確率。鏈接效果不理想的原因在于HITS算法依賴于子圖中候選實體節(jié)點的入度，但這一特征在Wikidata實體中不明顯。該系統(tǒng)的子圖構(gòu)建方法對本課題具有一定的參考價值。

由于社交媒體通常嚴密防范網(wǎng)絡爬蟲，同時提供的API也有嚴格的限制[12]，獲取社交賬號的社交關系并不容易。文獻[13]收集了一個小規(guī)模的社交圖數(shù)據(jù)集，并證明它可以有效地改善社交賬號對齊的結(jié)果。知識圖譜中的實體通常包含指向其他實體的鏈接，這些實體可以被看作一種社交關系圖。

2 問題定義與方法

文中研究的目的是針對給定的Twitter賬號t，在知識圖譜KG中找出對應的實體et，這里的知識圖譜特指Wikidata[14]。令集合C為賬號t在KG中生成的候選實體集，C={c1,c2,…,cn}，函數(shù)φ為根據(jù)賬號t在知識圖譜KG中生成的候選實體集，函數(shù)ψ為計算候選實體ci為正確實體的可能性，鏈接過程可以形式化地描述為如下兩個部分：

(1)候選實體集生成：C=φ(t,KG,Tr)，其中Tr為搜索策略集。

2.1 候選實體集生成

為了能夠正確地將Twitter賬號與知識圖譜實體對齊，首先需要根據(jù)賬號信息生成包含正確命名實體的候選實體集C。這里利用Wikidata提供的搜索服務生成候選實體集。

Wikidata搜索頁面提供關鍵詞搜索服務，能夠?qū)嶓w條目的標題和內(nèi)容進行搜索。使用搜索頁面生成候選實體集的關鍵在于提供合理的搜索關鍵詞：既能生成包含目標實體的候選實體集，又能減少候選實體集實體數(shù)量。根據(jù)這一目的，測試了三種搜索策略：

用戶名策略(Suser)：使用Twitter賬號的用戶名。用戶名為社交網(wǎng)絡用戶自行設置的字符串，可以更改或重復，國內(nèi)社交媒體一般稱為“昵稱”。這個策略中使用原始的用戶名作為搜索關鍵詞。

用戶名去符號策略(Sremove)：由于用戶名為用戶自行設置的字符串，用戶名中可能包含標點符號或者圖像符號。這個策略將除空格與文字字符以外的所有符號去掉。

用戶名分割策略(Ssplit)：這個策略以策略Sremove中產(chǎn)生的字符串為基礎，以空格為分割符，將用戶名分割為多個不同的搜索關鍵詞，將多個關鍵詞的搜索結(jié)果合并以產(chǎn)生候選實體集。

表1給出了一個搜索策略的示例。對于這些策略，可以將多個策略聯(lián)合使用，即對于某個目標賬號，將多條策略生成的多個候選實體集取并集，生成最終候選實體集。這里沒有使用Twitter賬號中更多的信息構(gòu)造搜索策略，如描述、推文等，因為Wikidata的搜索服務對于長字符串的處理并不理想。最后對每一次搜索服務的返回結(jié)果取前k個，構(gòu)成最終候選實體集。

表1 搜索策略示例

2.2 目標實體選擇

在產(chǎn)生候選實體集以后，需要采用一定的方法計算候選實體為目標實體的可能性，選擇最有可能的候選實體作為目標實體。這里對三種算法進行實驗，分別為標題匹配算法、AGDISTIS算法、子圖相交算法。

2.2.1 標題匹配算法

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

2.2.2 AGDISTIS算法

AGDISTIS算法[9]是一種基于圖的實體鏈接方法。該方法利用目標實體提及(entity mention)與上下文中的實體提及，在知識圖譜中生成有向子圖，以HITS(hyperlink-induced topic search)[10]或PageRank[11]算法計算圖中頂點的重要程度，選擇重要程度最高的頂點作為預測的目標實體。

在該實驗中，將目標賬號中存在的社交關系視為上下文實體提及用于生成子圖。AGDISTIS方法生成子圖的過程，是提出子圖相交算法的基礎。

2.2.3 子圖相交算法

文中在AGDISTIS算法[9]的基礎上提出了子圖相交算法。AGDISTIS算法在目標實體選擇階段使用的HITS[10]或PageRank[11]算法，其權(quán)值的計算依賴于候選實體節(jié)點的入度。但是在知識圖譜的結(jié)構(gòu)中，發(fā)現(xiàn)大量的候選實體入度為0，進而導致權(quán)值計算結(jié)果為0。基于這樣的觀察，引入了基于子圖相交來衡量節(jié)點重要程度的算法。

首先從給定社交賬號t的社交關系中涉及的相關賬號生成擴展實體集CE，CE中的元素為知識圖譜中的實體條目。這里提取了Twitter頁面中出現(xiàn)的轉(zhuǎn)發(fā)(retweet)、提及(mention)、引用(quote)以及關注(following)中的用戶作為賬號t的相關賬號集RA={ra0,ra1,…,ran}，取RA的前m個賬戶生成CE：

(1)

針對候選實體集C中的每個實體ci，生成一個搜索深度為d的擴展圖Gci。在這里將知識圖譜KG認為是一個有向圖GKG=(VKG,EKG)，其中，頂點V是KG中的實體，邊E為KG中的關系，那么x,y∈V,(x,y)∈E??p:(x,p,y)為KG中的一個RDF三元組。

擴展圖Gci的建立從初始化G0=(V0,E0)開始，其中V0為{ci}，E0為空，然后采用廣度優(yōu)先搜索擴展G0。定義擴展操作為ρ，第i步擴展結(jié)果為Gi=(Vi,Ei),i=1,2,…,d,擴展過程為：

Gi+1=ρ(Gi)=(Vi+1,Ei+1)

(2)

Vi+1=Vi∪{y:?x∈Vi∧(x,y)∈EKG}

(3)

Ei+1={(x,y)∈EKG:x,y∈Vi+1}

(4)

對G0執(zhí)行d次ρ操作即得到擴展圖Gci。取每個擴展圖Gci的頂點集Vci，令交集元素個數(shù)：

ici=|Vci∩CE|

(5)

算法過程描述如下：

算法：子圖相交算法。

輸入：目標賬號t；候選實體集C；搜索結(jié)果保留數(shù)k；相關賬號保留數(shù)m；圖搜索深度d；知識圖譜KG；搜索策略集Tr；

步驟：

1.CE←?

2.RA←getRelateAccount(t,m)

3.FORrai∈RA

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

5.END FOR

7.ic←0

8.FORci∈C

9.G←breadthFirstSearch(ci,d,KG)

10.V←getVertexesFromGraph(G)

11.tc←|V∩CE|

12.IF tc≥ic THEN

14.ic←tc

15.END IF

16.END FOR

3 實驗與分析

無論是社交網(wǎng)絡分析還是基于知識圖譜的實體鏈接工作，先前的研究者們已經(jīng)發(fā)布了大量的數(shù)據(jù)集用于研究和測試。文中研究內(nèi)容為Twitter賬號與Wikidata[14]知識圖譜實體的對齊工作，無法直接使用這些先前發(fā)布的數(shù)據(jù)集。因此將使用自行構(gòu)造的數(shù)據(jù)集對文中方法進行測試和評估。

實體對齊旨在從候選實體集中選擇最有可能的實體作為目標實體，故最終的結(jié)果只有“成功”或“失敗”兩種結(jié)果。因此，文中衡量算法性能的指標為準確率(Accuracy)。在2.2.1中提到的標題匹配算法將作為本次實驗的基準算法。這個算法實際上是利用Wikidata自身搜索服務來實現(xiàn)Twitter賬號實體的對齊。

評估將分為三個部分進行。首先對候選實體集生成部分與目標實體選擇部分分開評估，然后對總體方法進行評估。

3.1 實驗數(shù)據(jù)

針對文中提出的研究工作，需要一批特殊的Twitter賬號，這些賬號在Wikidata中存在相應的實體。同時需要這些Twitter賬號的基本信息，如賬號名、昵稱等。由于文中方法主要從Twitter用戶的社交關系入手，所以Twitter賬號發(fā)表的推文以及關注的賬號也是需要的信息。

文中研究所涉及的知識圖譜Wikidata由維基媒體德國分會首先提出[14]。為了完成數(shù)據(jù)集的構(gòu)造，首先通過Wikidata Query Service，利用SPARQL[15]語言獲取了3 024條具有Twitter賬號的Wikidata實體，其中包含1 379個人物賬號，1 645個組織賬號。

獲取的結(jié)果格式如表2所示，其中Item為Wikidata中的實體鏈接，ItemLable為Wikidata中的實體標簽，Twitter為實體所對應的Twitter賬號名。根據(jù)Twitter賬號名，利用網(wǎng)絡爬蟲技術[16-17]，爬取相關賬號的基本信息、推文及關注賬號列表。

表2 Wikidata Query Service結(jié)果示例

為了保證能夠獲取較為可靠的社交關系，去除了推文總數(shù)在300條以下且關注總數(shù)在100以下的賬號，最終保留賬號2 281個，其中人物賬號1 086個，組織賬號1 195個。表3列出了推文和關注相關的統(tǒng)計信息，平均推文數(shù)6 129.63條，關注賬號數(shù)2 937.66個。

表3 Twitter賬號數(shù)據(jù)統(tǒng)計

3.2 候選實體集生成

在實驗數(shù)據(jù)集上對搜索策略逐條進行評估。評估針對Twitter賬號類型按照人員、組織和綜合(人員+組織)分為三大類。評估的指標為：

(1)候選實體集大小均值(average number of candidate entities，ACE)：候選實體集元素個數(shù)的平均數(shù)量。

(2)非空率(non-empty rate，NER)：候選實體集不為空的比率。

(3)覆蓋率(coverage rate，CR)：在候選實體集中包含目標實體的比率。

在評估候選實體集生成性能之前，需要確定搜索結(jié)果保留數(shù)k。圖2描述了三種搜索策略在測試數(shù)據(jù)集上的性能表現(xiàn)。為了保證目標實體覆蓋率與候選實體集大小之間的平衡，最終選擇k=5。

圖2 k取值與覆蓋率的關系

表4顯示了針對不同搜索策略的實驗結(jié)果。可以看出Sremove相對于Suser雖然去除了非文字符號，但是性能并沒有提升。Ssplit對于單個Twitter賬號來說增加了搜索次數(shù)，提高了候選實體集非空率(NER)，但是字符分割帶來的語義破壞，影響了目標實體覆蓋率(CR)。最終選擇使用Suser策略。

表4 搜索策略實驗結(jié)果

3.3 目標實體選擇

目標實體選擇部分的評估將在包含正確目標實體的候選實體集中進行，候選實體集的生成策略采用Suser。將對三種方法在實驗數(shù)據(jù)集上的準確率進行計算，三種方法分別為：標題匹配算法(Atitle)、AGDISTIS算法[9](AHITS)和子圖相交算法(Asubg)。

AGDISTIS算法在構(gòu)建子圖時使用的寬度優(yōu)先搜索深度(d)為2[9]。子圖相交算法在構(gòu)建子圖時，基于子圖規(guī)模與算法運行時間的平衡，選擇寬度優(yōu)先搜索深度(d)為3；保留了爬取數(shù)據(jù)中所有的相關賬號，平均個數(shù)為311.788。

表5顯示了不同方法針對實驗數(shù)據(jù)集中不同類型數(shù)據(jù)的準確率。可以看出，子圖相交算法在針對人員類型賬號數(shù)據(jù)時，相對于其他兩種方法性能較好，但是對于組織類型賬號數(shù)據(jù)性能弱于AGDISTIS算法。這樣的差別在于，在知識圖譜中，組織類型的實體往往有多條相關的實體[18]。特別是對于Wikidata這類由社區(qū)眾籌維護的知識圖譜來說，針對某個組織往往存在多個實體。

表5 目標實體選擇實驗結(jié)果

子圖相交算法使用相交子圖的頂點個數(shù)—ic值作為目標實體的選擇依據(jù)。這一簡單的指標在實驗中取得了最高0.94的準確率。表6顯示了目標實體與非目標實體之間平均相交子圖頂點數(shù)值(ic)上的對比。

表6 目標實體與非目標實體的平均ic值對比

從表6可以看出，目標實體與非目標實體在平均ic值上具有較大的差異。這充分顯示了社交賬號中的社交關系映射到知識圖譜中形成的子圖，在結(jié)構(gòu)上呈現(xiàn)出了聚集的特性，在正確的候選實體附近較為“稠密”，ic值為描述這一結(jié)構(gòu)特性較為直觀的指標。

3.4 總體方法

總體評估針對整個數(shù)據(jù)集，對于候選實體集為空的數(shù)據(jù)將標記為對齊失敗。表7顯示了三種方法的總體評估結(jié)果。

從表中可以看出，總體性能相對目標實體選擇部分有很大下降，這主要是由候選實體集生成部分目標實體覆蓋率(HTVC)引起的。對于未包含正確實體的候選實體集，目標實體選擇算法是無法找到正確對齊實體的。總體性能特點與目標實體選擇部分類似，組織類型數(shù)據(jù)對齊正確率較低，子圖相交算法取得了最好的綜合性能。

表7 總體方法實驗結(jié)果

4 結(jié)束語

提出了一種將社交賬號與知識圖譜實體進行對齊的算法—子圖相交算法。算法通過將目標賬號的社交關系圖映射到知識圖譜中形成子圖，以衡量候選實體所在子圖位置的實體聚集程度，來選擇目標實體。該研究揭示了基于社交關系映射的知識圖譜子圖，在目標實體“附近”存在聚集特性，利用這一特性預測目標實體取得了較高的準確率。

通過Wikidata提供的搜索服務構(gòu)建了用于測試和評估的對齊數(shù)據(jù)集，文中方法在該數(shù)據(jù)集上實現(xiàn)了0.637的準確率。

子圖相交算法所利用的社交媒體的社交關系圖以及知識圖譜的圖結(jié)構(gòu)等信息，是普遍存在于社交媒體和知識圖譜中的。所以該對齊方法可以應用于其他的社交媒體和知識圖譜。

下一步的工作可以從三個方面開展。首先是增加方法對不存在目標實體的空鏈接(NIL)項的處理功能，可以考慮引入更多的特征，采用機器學習方法，設計一個基于監(jiān)督方法的實體對齊系統(tǒng)。

其次是將映射子圖的聚集特性應用于更多的領域，例如其他社交媒體的實體鏈接、社群分析、話題識別等方面。最后是擴充數(shù)據(jù)集，添加更多職業(yè)和類別的賬號，同時加入NIL類賬號用于機器學習算法的訓練和測試。