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

劉家祝，郭 強(qiáng)，吳碧偉，曾明勇

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

0 引 言

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

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

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

圖1 Twitter賬號與Wikidata對齊

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

1 相關(guān)工作

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

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

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

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

2 問題定義與方法

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

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

2.1 候選實(shí)體集生成

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

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

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

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

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

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

表1 搜索策略示例

2.2 目標(biāo)實(shí)體選擇

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

2.2.1 標(biāo)題匹配算法

標(biāo)題匹配法以Twitter賬號用戶名與候選實(shí)體標(biāo)題字符串的相似度為選擇標(biāo)準(zhǔn)，選擇第一個與Twitter賬號用戶名完全相同的候選實(shí)體為目標(biāo)實(shí)體。

2.2.2 AGDISTIS算法

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

在該實(shí)驗(yàn)中，將目標(biāo)賬號中存在的社交關(guān)系視為上下文實(shí)體提及用于生成子圖。AGDISTIS方法生成子圖的過程，是提出子圖相交算法的基礎(chǔ)。

2.2.3 子圖相交算法

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

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

(1)

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

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

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次ρ操作即得到擴(kuò)展圖Gci。取每個擴(kuò)展圖Gci的頂點(diǎn)集Vci，令交集元素個數(shù)：

ici=|Vci∩CE|

(5)

算法過程描述如下：

算法：子圖相交算法。

輸入：目標(biāo)賬號t；候選實(shí)體集C；搜索結(jié)果保留數(shù)k；相關(guān)賬號保留數(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 實(shí)驗(yàn)與分析

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

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

評估將分為三個部分進(jìn)行。首先對候選實(shí)體集生成部分與目標(biāo)實(shí)體選擇部分分開評估，然后對總體方法進(jìn)行評估。

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

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

3.2 候選實(shí)體集生成

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

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

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

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

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

圖2 k取值與覆蓋率的關(guān)系

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

表4 搜索策略實(shí)驗(yàn)結(jié)果

3.3 目標(biāo)實(shí)體選擇

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

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

表5顯示了不同方法針對實(shí)驗(yàn)數(shù)據(jù)集中不同類型數(shù)據(jù)的準(zhǔn)確率?？梢钥闯觯訄D相交算法在針對人員類型賬號數(shù)據(jù)時，相對于其他兩種方法性能較好，但是對于組織類型賬號數(shù)據(jù)性能弱于AGDISTIS算法。這樣的差別在于，在知識圖譜中，組織類型的實(shí)體往往有多條相關(guān)的實(shí)體[18]。特別是對于Wikidata這類由社區(qū)眾籌維護(hù)的知識圖譜來說，針對某個組織往往存在多個實(shí)體。

表5 目標(biāo)實(shí)體選擇實(shí)驗(yàn)結(jié)果

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

表6 目標(biāo)實(shí)體與非目標(biāo)實(shí)體的平均ic值對比

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

3.4 總體方法

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

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

表7 總體方法實(shí)驗(yàn)結(jié)果

4 結(jié)束語

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

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

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

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

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