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

郭 強(qiáng)，譚菊仙，劉家祝

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

0 引 言

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

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

文中充分利用社交網(wǎng)絡(luò)和知識圖譜的結(jié)構(gòu)特點(diǎn)，研究社交賬號與知識圖譜實(shí)體的對齊技術(shù)，將社交賬號與知識圖譜中的實(shí)體鏈接起來。與實(shí)體鏈接過程類似，社交賬號與知識圖譜實(shí)體也為兩個步驟[1]：候選實(shí)體集生成與目標(biāo)實(shí)體選擇。以Twitter賬號與Wikidata實(shí)體對齊為例，圖1給出了一個對齊過程。

圖1 Twitter賬號與Wikidata對齊

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

1 相關(guān)工作

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

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

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

2 問題定義與方法

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

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

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

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

算法1：候選實(shí)體生成算法getCandidates。

輸入：社交賬號t；

輸出：候選實(shí)體列表C。

步驟：

1.C←NULL

4. if fitDomain(c) then:

5.C=C∪c;

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

2.2.1 社交子圖生成

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

SGsub=SGfollowing∪SGmention∪SGretweet∪SGquote

(1)

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

2.2.2 結(jié)構(gòu)投影子圖生成

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

算法過程描述如下：

算法2：結(jié)構(gòu)投影算法。

輸入：目標(biāo)賬號t；有關(guān)目標(biāo)賬號t的爬取數(shù)據(jù)data；知識圖譜KG；

輸出：結(jié)構(gòu)投影子圖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 圖嵌入特征構(gòu)建

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

算法3：核心實(shí)體集生成算法。

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

輸出：核心實(shí)體集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

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

(2)

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

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

目標(biāo)實(shí)體選擇以特征向量Ifeature為輸入，計(jì)算候選實(shí)體為目標(biāo)實(shí)體的匹配值，最后根據(jù)這一組候選實(shí)體匹配值，選擇最終對齊實(shí)體。

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

文中設(shè)計(jì)了一個單隱層的MLP模型，具體結(jié)構(gòu)如圖2所示。

圖2 目標(biāo)實(shí)體匹配值計(jì)算模型結(jié)構(gòu)示意圖

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

LMSELoss=(Vscore-Vlabel)2

(3)

其中，Vlabel為訓(xùn)練數(shù)據(jù)標(biāo)簽值。訓(xùn)練過程的反向傳播調(diào)整參數(shù)的過程使用了Adam[14]算法作為優(yōu)化器。為了防止過擬合，模型采用L2正則化方法。

針對一個候選實(shí)體集C，計(jì)算每個候選實(shí)體的匹配值Vscore={v1,v2,…,vn}，n為候選實(shí)體個數(shù)，選擇分值最高的候選對象為目標(biāo)實(shí)體。

3 實(shí)驗(yàn)與分析

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

3.1 對比算法

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

3.1.1 標(biāo)題匹配算法(Atitle)

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

3.1.2 AGDISTIS算法(AHITS)

AGDISTIS算法對知識圖譜子圖進(jìn)行深度為2的廣度優(yōu)先搜索，從而生成新子圖，然后使用HITS算法計(jì)算新子圖的節(jié)點(diǎn)權(quán)威值，選取權(quán)威值最高的節(jié)點(diǎn)作為鏈接結(jié)果。

3.1.3 子圖相交算法(Asub)

文獻(xiàn)[1]在AGDISTIS算法的基礎(chǔ)上提出了子圖相交算法，它將候選實(shí)體進(jìn)行深度為3的廣度優(yōu)先搜索，為每個候選實(shí)體生成一個子圖，然后將社交賬號相關(guān)聯(lián)的賬號投影到知識圖譜生成目標(biāo)子圖，計(jì)算目標(biāo)子圖和候選實(shí)體子圖的交集，選擇交集元素最多的候選實(shí)體作為最終對齊結(jié)果。

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

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

為了進(jìn)行實(shí)驗(yàn)對比，根據(jù)文獻(xiàn)[1]的方法對數(shù)據(jù)集進(jìn)行擴(kuò)充，重新獲取15 962個Twitter賬號作為訓(xùn)練集和驗(yàn)證集，其中人物賬號10 256個，組織賬號5 706個，將文獻(xiàn)[1]中的2 281個賬號作為測試集。

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

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

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

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

為了選擇最優(yōu)超參數(shù)，按照7∶1的比例將訓(xùn)練數(shù)據(jù)集劃分為訓(xùn)練集、驗(yàn)證集，使用驗(yàn)證集進(jìn)行網(wǎng)格搜索，確定最優(yōu)超參數(shù)組合，見表1。

表1 最優(yōu)實(shí)驗(yàn)參數(shù)組合

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

表2 基于圖嵌入特征的實(shí)體對齊算法實(shí)驗(yàn)結(jié)果

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

4 結(jié)束語

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

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