滕磊 李苑 李智星 胡峰

摘 要：針對(duì)目前跨社交網(wǎng)絡(luò)用戶(hù)對(duì)齊算法存在的網(wǎng)絡(luò)嵌入效果不佳、負(fù)采樣方法所生成負(fù)例質(zhì)量無(wú)法保證等問(wèn)題，提出一種基于知識(shí)圖嵌入的跨社交網(wǎng)絡(luò)用戶(hù)對(duì)齊（KGEUA）算法。在嵌入階段，利用部分已知的種子錨用戶(hù)對(duì)進(jìn)行正例擴(kuò)充，并提出Near_K負(fù)采樣方法生成負(fù)例，最后利用知識(shí)圖嵌入方法將兩個(gè)社交網(wǎng)絡(luò)嵌入到統(tǒng)一的低維向量空間中。在對(duì)齊階段，針對(duì)目前的用戶(hù)相似度度量方法進(jìn)行改進(jìn)，將提出的結(jié)構(gòu)相似度與傳統(tǒng)的余弦相似度結(jié)合共同度量用戶(hù)相似度，并提出基于自適應(yīng)閾值的貪心匹配方法對(duì)齊用戶(hù)，最后將新對(duì)齊的用戶(hù)對(duì)加入到訓(xùn)練集中以持續(xù)優(yōu)化向量空間。實(shí)驗(yàn)結(jié)果表明，提出的算法在TwitterFoursquare數(shù)據(jù)集上的hits@30值達(dá)到了67.7%，比用戶(hù)對(duì)齊現(xiàn)有最佳算法的結(jié)果高出3.3～34.8個(gè)百分點(diǎn)，顯著提升用戶(hù)對(duì)齊效果。

關(guān)鍵詞：用戶(hù)對(duì)齊;社交網(wǎng)絡(luò);網(wǎng)絡(luò)嵌入;負(fù)采樣;相似度度量

中圖分類(lèi)號(hào)： TP182

文獻(xiàn)標(biāo)志碼：A

Crosssocial network user alignment algorithm based on knowledge graph embedding

TENG Lei1，2， LI Yuan1，2， LI Zhixing1，2*， HU Feng1，2

1.College of Computer Science and Technology， Chongqing University of Posts and Telecommunications， Chongqing 400065， China;

2.Chongqing Key Laboratory of Computing Intelligence（Chongqing University of Posts and Telecommunications）， Chongqing 400065， China

Abstract：

Aiming at the poor network embedding performance of crosssocial network user alignment algorithm and the inability to guarantee the quality of negative samples generated by negative sampling method， a crosssocial network KGEUA （Knowledge Graph Embedding User Alignment） algorithm was proposed. In the embedding stage， some known anchor user pairs were used for the positive sample expansion， and theNear_Knegative sampling method was proposed to generate negative examples. Finally， the two social networks were embedded into a unified lowdimensional vector space with the knowledge graph embedding method. In the alignment stage， the existing user similarity measurement method was improved， the proposed structural similarity was combined with the traditional cosine similarity to measure the user similarity jointly， and an adaptive thresholdbased greedy matching method was proposed to align users. Finally， the newly aligned user pairs were added to the training set to continuously optimize the vector space. The experimental results show that the proposed algorithm has the hits@30 value of 67.7% on the TwitterFoursquare dataset， which is 3.3 to 34.8 percentage points higher than that of the stateoftheart algorithm， improving the user alignment performance effectively.

Key words：

user alignment; social network; network embedding; negative sampling; similarity measure

0?引言

近年來(lái)，互聯(lián)網(wǎng)的快速發(fā)展帶動(dòng)了在線(xiàn)社交網(wǎng)絡(luò)的發(fā)展，如Twitter、Foursquare等在線(xiàn)社交網(wǎng)絡(luò)平臺(tái)極大地豐富了人們的社交生活。例如，人們會(huì)在Twitter上更新每日動(dòng)態(tài)，同時(shí)在Instagram上分享照片并在Foursquare上分享他們的位置。人們?yōu)榱讼硎芨鱾€(gè)在線(xiàn)社交網(wǎng)絡(luò)的不同功能，通常會(huì)注冊(cè)多個(gè)社交網(wǎng)絡(luò)賬號(hào)[1]。根據(jù)2018年的統(tǒng)計(jì)數(shù)據(jù)顯示，互聯(lián)網(wǎng)用戶(hù)平均每人有8.5個(gè)不同的在線(xiàn)社交網(wǎng)絡(luò)賬戶(hù)[2]。

跨社交網(wǎng)絡(luò)用戶(hù)對(duì)齊的目標(biāo)是在不同的在線(xiàn)社交網(wǎng)絡(luò)中找到屬于現(xiàn)實(shí)世界中的同一用戶(hù)的不同賬號(hào)。這一研究在生活中擁有實(shí)際的意義，可以通過(guò)對(duì)齊用戶(hù)來(lái)為用戶(hù)提供更好的服務(wù)，例如朋友或商品推薦[3-4]。除此之外，通過(guò)對(duì)齊用戶(hù)還可以解決一些在單個(gè)社交網(wǎng)絡(luò)中無(wú)法解決的問(wèn)題，如冷啟動(dòng)問(wèn)題[5]。

目前，跨社交網(wǎng)絡(luò)用戶(hù)對(duì)齊的研究主要基于用戶(hù)信息或網(wǎng)絡(luò)結(jié)構(gòu)。在線(xiàn)社交網(wǎng)絡(luò)的用戶(hù)信息存在較大噪聲且用戶(hù)行為等信息獲取難度大，加大了用戶(hù)對(duì)齊的難度;而社交網(wǎng)絡(luò)結(jié)構(gòu)擁有獲取難度低、真實(shí)性高、很難進(jìn)行偽造[6]、網(wǎng)絡(luò)結(jié)構(gòu)中所隱含的信息豐富等特點(diǎn)，能為用戶(hù)對(duì)齊研究帶來(lái)出色且穩(wěn)定的對(duì)齊性能。

傳統(tǒng)的基于網(wǎng)絡(luò)結(jié)構(gòu)的用戶(hù)對(duì)齊算法通常將兩個(gè)社交網(wǎng)絡(luò)孤立看待，無(wú)法學(xué)習(xí)跨網(wǎng)絡(luò)的隱藏信息;雖然使用了負(fù)采樣方法提升嵌入空間質(zhì)量但現(xiàn)有負(fù)采樣方法存在無(wú)法保證負(fù)例質(zhì)量;忽略了用戶(hù)在網(wǎng)絡(luò)結(jié)構(gòu)上的相似性，最終導(dǎo)致對(duì)齊性能不佳。

本文的主要貢獻(xiàn)包含如下幾個(gè)方面：

1）使用社交網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行跨社交網(wǎng)絡(luò)用戶(hù)對(duì)齊，提出一種基于知識(shí)圖嵌入的跨社交網(wǎng)絡(luò)用戶(hù)對(duì)齊（Knowledge Graph Embedding User Alignment， KGEUA）算法，顯著提升了用戶(hù)對(duì)齊的性能。

2）提出Near_K（Nearest topK）負(fù)采樣方法，解決了傳統(tǒng)負(fù)采樣方法無(wú)法保證負(fù)例質(zhì)量的問(wèn)題。

3）探索用戶(hù)在網(wǎng)絡(luò)結(jié)構(gòu)上的相似性并提出結(jié)構(gòu)相似度用于度量用戶(hù)對(duì)之間的相似度。

4）提出基于自適應(yīng)閾值的貪心匹配方法，克服傳統(tǒng)靜態(tài)閾值方法存在的弊端，并利用迭代對(duì)齊的思想將訓(xùn)練過(guò)程中新對(duì)齊的用戶(hù)對(duì)加入訓(xùn)練集中以持續(xù)優(yōu)化嵌入空間。

1?相關(guān)工作

用戶(hù)對(duì)齊問(wèn)題也被稱(chēng)為錨鏈接預(yù)測(cè)[7]、用戶(hù)身份鏈接[8]。已有的用戶(hù)對(duì)齊的研究大致可分基于用戶(hù)信息與基于網(wǎng)絡(luò)結(jié)構(gòu)兩大類(lèi)。

基于用戶(hù)信息的方法主要是利用用戶(hù)信息如用戶(hù)名[9]、空間位置[10]、文本內(nèi)容[11-12]等信息進(jìn)行對(duì)齊。例如 Zafarani等[9]認(rèn)為用戶(hù)名背后隱藏著用戶(hù)名命名的行為特征，所以從多個(gè)角度建立用戶(hù)名命名行為特征模型來(lái)對(duì)齊用戶(hù)。但是，用戶(hù)可以在不同社交網(wǎng)絡(luò)設(shè)置不同的用戶(hù)名且用戶(hù)名可隨時(shí)更改，這就加大了用戶(hù)對(duì)齊的難度。用戶(hù)生成的文本內(nèi)容也常被用于用戶(hù)對(duì)齊，如 Goga等[11]將用戶(hù)生成文本內(nèi)容的時(shí)間、位置信息以及寫(xiě)作風(fēng)格相結(jié)合來(lái)進(jìn)行用戶(hù)對(duì)齊。但是由于社交網(wǎng)絡(luò)用戶(hù)信息的隱私性，所以這種方法通常存在數(shù)據(jù)獲取困難的問(wèn)題[6]。

通常，基于網(wǎng)絡(luò)結(jié)構(gòu)的用戶(hù)對(duì)齊方法采用網(wǎng)絡(luò)嵌入的方式進(jìn)行用戶(hù)對(duì)齊[13-18]，如： Tan等[13]定義了用戶(hù)之間的超邊，并將兩個(gè)網(wǎng)絡(luò)投影到同一個(gè)向量空間中，使得超邊中的節(jié)點(diǎn)在該空間中更接近; Liu等[14]提出IONE（InputOutput Network Embedding）模型來(lái)將兩個(gè)社交網(wǎng)絡(luò)嵌入到低維向量空間中進(jìn)行對(duì)齊;Liu等[15]提出基于注意力機(jī)制的ABNE（Attention Based Network Embedding）模型，在部分已對(duì)齊的用戶(hù)對(duì)上利用圖注意力機(jī)制學(xué)習(xí)權(quán)重再將兩個(gè)網(wǎng)絡(luò)分別嵌入低維向量空間中并學(xué)習(xí)一個(gè)對(duì)齊方法進(jìn)行對(duì)齊; Chu等[16]最近提出的CrossMNA（Crossnetwork embedding method for MultiNetwork Alignment）模型可用于多個(gè)網(wǎng)絡(luò)的用戶(hù)對(duì)齊和鏈接預(yù)測(cè)。

上述方法雖然對(duì)用戶(hù)對(duì)齊問(wèn)題的性能有所提升，但仍然存在以下三個(gè)問(wèn)題：

第一，目前基于網(wǎng)絡(luò)結(jié)構(gòu)嵌入的方法通常是將兩個(gè)網(wǎng)絡(luò)分別嵌入低維向量空間中，這種方法通常會(huì)造成網(wǎng)絡(luò)信息丟失且無(wú)法很好地挖掘兩個(gè)網(wǎng)絡(luò)間的隱藏信息。第二，傳統(tǒng)的負(fù)采樣方法是將網(wǎng)絡(luò)關(guān)系中的用戶(hù)隨機(jī)替換為其他用戶(hù)，該方法不能保證負(fù)例的質(zhì)量。第三，傳統(tǒng)的相似度計(jì)算方法可能存在多個(gè)用戶(hù)與一個(gè)用戶(hù)相似度均很高的情況，可能出現(xiàn)無(wú)法確定最優(yōu)對(duì)齊用戶(hù)的情況[19]。除此之外，傳統(tǒng)的用戶(hù)對(duì)齊算法在計(jì)算用戶(hù)對(duì)相似度時(shí)未考慮用戶(hù)在網(wǎng)絡(luò)結(jié)構(gòu)上的相似性;同時(shí)，用戶(hù)對(duì)的相似度會(huì)隨訓(xùn)練過(guò)程而改變，但相似度度閾值通常為固定值，可能引入噪聲或限制過(guò)嚴(yán)從而影響對(duì)齊性能。

針對(duì)以上問(wèn)題，本文提出了一種基于知識(shí)圖嵌入的跨社交網(wǎng)絡(luò)用戶(hù)對(duì)齊方法。該方法利用部分種子錨用戶(hù)對(duì)集合進(jìn)行正例擴(kuò)充，并結(jié)合Near_K負(fù)采樣方法生成高質(zhì)量負(fù)例，使用知識(shí)圖嵌入方法將兩個(gè)社交網(wǎng)絡(luò)嵌入到統(tǒng)一的低維向量空間，最后通過(guò)基于自適應(yīng)閾值的貪心匹配算法將新對(duì)齊的用戶(hù)對(duì)加入訓(xùn)練集持續(xù)優(yōu)化嵌入空間。

2?跨社交網(wǎng)絡(luò)用戶(hù)對(duì)齊算法

2.1?相關(guān)定義

本文使用大寫(xiě)字母表示集合，對(duì)應(yīng)的小寫(xiě)字母代表該集合中的元素，加粗的小寫(xiě)字母表示該元素的嵌入向量，加粗的大寫(xiě)字母代表矩陣。

定義1?定義社交網(wǎng)絡(luò)S=（V，E），其中V是社交網(wǎng)絡(luò)中的用戶(hù)集合，E={（vi， r， vj）|i， j=1，2，…，n，i≠j}是社交網(wǎng)絡(luò)中的邊集合，r表示社交網(wǎng)絡(luò)中的關(guān)系。

定義2?給定社交網(wǎng)絡(luò)S1=（V1，E1）、S2=（V2，E2）和部分已知的對(duì)齊的種子錨用戶(hù)對(duì)集合A={（a1，a2）|a1∈V1，a2∈V2}，其中（a1，a2）稱(chēng)為錨用戶(hù)對(duì)。跨社交網(wǎng)絡(luò)用戶(hù)對(duì)齊的目標(biāo)是利用A設(shè)計(jì)映射函數(shù)I（vi1， vj2）→{0，1}使得：

I（vi1，vj2）=1，vi1，vj2屬于同一用戶(hù)

0，vi1，vj2不屬于同一用戶(hù) （1）

在KGEUA中，將社交網(wǎng)絡(luò)S1，S2嵌入到統(tǒng)一的低維向量空間Θ。定義用戶(hù)vi1∈V1， vj2∈V2是錨用戶(hù)對(duì)的概率為：

P（vi1，vj2）=σ（sim（vi1，vj2））（2）

其中：σ（·）是sigmoid函數(shù)，sim（·）是相似度度量方法，則KGEUA的優(yōu)化目標(biāo)是找到最優(yōu)的嵌入空間Θ，即：

Θ=argmax∑vi1∈V1vj2∈V2I（vi1，vj2）P（vi1，vj2;

Θ^）（3）

2.2?基于Near_K負(fù)采樣與正例擴(kuò)充的網(wǎng)絡(luò)嵌入

為使得單個(gè)社交網(wǎng)絡(luò)的結(jié)構(gòu)在嵌入空間中仍盡量保存，本文利用TransE（Translating Embeddings）[20]將兩個(gè)社交網(wǎng)絡(luò)嵌入到統(tǒng)一的低維向量空間，同時(shí)提出Near_K負(fù)采樣方法提高負(fù)例質(zhì)量。此外，利用種子錨用戶(hù)對(duì)擴(kuò)充正例使得錨用戶(hù)對(duì)之間的距離盡可能地近，非錨用戶(hù)對(duì)之間的距離盡可能地遠(yuǎn)。

2.2.1Near_K負(fù)采樣

考慮如圖1的網(wǎng)絡(luò)結(jié)構(gòu)，為正例（v5， follow，v3）生成負(fù)例，傳統(tǒng)方法是在v6或v1中隨機(jī)選擇一個(gè)用戶(hù)生成負(fù)例，使其滿(mǎn)足（v5， follow，v6or1）E。但是因?yàn)閒ollow（v5）∩follow（v1）=， follow（v5）∩follow（v6）={4，3}，其中follow（·）代表用戶(hù)的關(guān)注集合，所以在嵌入空間Θ中，sim（v5，v6）>sim（v5，v1），負(fù)例b=（v5， follow，v6）比a=（v5， follow，v1）更不容易分辨，對(duì)于Θ的學(xué)習(xí)貢獻(xiàn)更大，因此質(zhì)量更高。

具體的，給定用戶(hù)vi，將其負(fù)采樣的候選集C縮小到與其相似度最大的k∈（0，n]個(gè)用戶(hù)組成的集合里，n表示網(wǎng)絡(luò)中有多少個(gè)用戶(hù)，即：

Cvi={vj|vj∈mink（sim（vi，vj）），

（vi，r，vj）E，k∈（0，n]}（4）

2.2.2?正例擴(kuò)充

通常，為了使得已知錨用戶(hù)對(duì)在嵌入空間中的距離更近，會(huì)利用參數(shù)共享的方式將錨用戶(hù)對(duì)在不同網(wǎng)絡(luò)中的向量標(biāo)識(shí)強(qiáng)制設(shè)置為相同，但這種方法并未保留任何非錨用戶(hù)對(duì)的信息，造成信息丟失。本文利用已知的種子錨用戶(hù)對(duì)集合A進(jìn)行正例擴(kuò)充克服該缺點(diǎn)。

具體的，給定一組種子錨用戶(hù)對(duì)（a1，a2）∈A，擴(kuò)充正例如下：

Eg={（a2，r1，vj1）|（a1，r1，vj1）∈E+1}∪

{（vi1，r1，a2）|（vi1，r1，a1）∈E+1}∪

{（a1，r2，vj2）|（a2，r2，vj2）∈E+2}∪

{（vi2，r2，a1）|（vi2，r2，a2）∈E+2}（5）

其中E+1和E+2分別表示S1和S2的正例集合。兩個(gè)社交網(wǎng)絡(luò)中的全部的正例集合為E+=E+1+E+2+Eg，緊接著為正例集合E+生成負(fù)例集合E-。

入空間學(xué)習(xí)

TransE是知識(shí)圖嵌入的流行方法，它將實(shí)體和關(guān)系映射到低維連續(xù)的向量空間并希望h+r≈t成立，其中h、r、t分別是頭實(shí)體、關(guān)系、尾實(shí)體的向量。本文將社交關(guān)系表示為e=（vi，r，vj），使用TransE將兩個(gè)網(wǎng)絡(luò)嵌入到統(tǒng)一的低維向量空間中，并利用如下評(píng)分函數(shù)來(lái)度量嵌入空間中社交關(guān)系的正確性：

S（e）=‖vi+r-vj‖22（6）

該評(píng)分函數(shù)希望正例的分?jǐn)?shù)盡可能地低，而負(fù)例的分?jǐn)?shù)盡可能地高。所以，本文通過(guò)如下目標(biāo)函數(shù)來(lái)優(yōu)化嵌入空間：

J=∑e+∈E+[S（e+）-λ1]++μ∑e-∈E-[λ2-S（e+）]+（7）

s.t.λ1>0，λ2>0，λ2λ1

其中[x]+=max（0，x）返回0和x中的最大值。λ1和λ2是兩個(gè)超參數(shù)，用于控制正負(fù)例的評(píng)分，μ是權(quán)重系數(shù)。本文使用Adagrad（Adaptive gradient algorithm）[21]作為優(yōu)化方法進(jìn)行優(yōu)化。

2.3?基于自適應(yīng)閾值的用戶(hù)對(duì)齊

得到兩個(gè)網(wǎng)絡(luò)的嵌入后，使用基于自適應(yīng)閾值的貪心匹配方法將訓(xùn)練過(guò)程中找到的錨用戶(hù)對(duì)迭代地加入到訓(xùn)練集中以提升性能。除此之外，本文將提出的結(jié)構(gòu)相似度與余弦相似度相結(jié)合作為相似度度量方法。

2.3.1?結(jié)構(gòu)相似度

兩個(gè)用戶(hù)所共有的朋友數(shù)量越多，其成為朋友的概率就越大[22]。類(lèi)似的，如果兩個(gè)用戶(hù)所共享的種子錨用戶(hù)對(duì)越多，其成為錨用戶(hù)對(duì)的可能性就越大。具體的，對(duì)于給定的用戶(hù)對(duì)（v1，v2），其共享的種子用戶(hù)為：

sharedseed={（a1，a2）∈A|（v1，r1，a1）∈E1，

（v2，r2，a2）∈E2}（8）

假設(shè)用戶(hù)v在網(wǎng)絡(luò)S中關(guān)注了種子錨用戶(hù)a，考慮如下兩種情況：

1）用戶(hù)a在網(wǎng)絡(luò)中共有2-000個(gè)關(guān)注者;

2）用戶(hù)a在網(wǎng)絡(luò)中只有用戶(hù)v一個(gè)關(guān)注者。

很明顯，第二種情況下，用戶(hù)v更有可能加入另一個(gè)網(wǎng)絡(luò)。由此可見(jiàn)，種子錨用戶(hù)對(duì)用戶(hù)的影響并不相同。

本文定義用戶(hù)對(duì)（v1，v2）的結(jié)構(gòu)相似度（structural similarity， ssim）如下：

ssim（v1，v2）=∑count（sharedseed）i=1im（v1，a1）+im（v2，a2）2（9）

其中：im（v，a）=related（v，a）related（a），related（a）表示與種子用戶(hù)a存在關(guān)系的用戶(hù)數(shù)量，related（v，a）表示種子用戶(hù)a與用戶(hù)v存在的關(guān)系的數(shù)量。

分別計(jì)算用戶(hù)對(duì)的余弦相似度與結(jié)構(gòu)相似度得到對(duì)應(yīng)的矩陣M1和M2，進(jìn)行加權(quán)求和得到用戶(hù)對(duì)之間的相似度矩陣：

M=α×M1+（1-α）×Mnorm2（10）

其中：Xnorm=X-min（X）max（X）-min（X），α∈[0，1]是用于調(diào)節(jié)余弦相似度與結(jié)構(gòu)相似度權(quán)重的超參數(shù)。

2.3.2?基于自適應(yīng)閾值的貪心匹配

在第k輪迭代中，相似度矩陣為Mk，候選錨用戶(hù)對(duì)集合為Qk，已配對(duì)用戶(hù)集合為Yk。通過(guò)貪心匹配選取候選錨用戶(hù)對(duì)過(guò)程如圖2所示：依次選擇最大相似度所對(duì)應(yīng)的用戶(hù)對(duì)（vi1，vj2），若vi1Ykandvj2Yk，則將（vi1，vj2）加入Qk，否則將其舍棄。

社交網(wǎng)絡(luò)錨用戶(hù)對(duì)數(shù)量很少，上述算法可能會(huì)將相似度很低的用戶(hù)對(duì)（如圖2中的（v11，v22））選為錨用戶(hù)對(duì)，在后續(xù)迭代訓(xùn)練中引入噪聲造成錯(cuò)誤傳遞。本文提出通過(guò)自適應(yīng)閾值（adaptive threshold）方法來(lái)篩選錨用戶(hù)對(duì)。

假設(shè)在第k輪訓(xùn)練中，種子錨用戶(hù)對(duì)集合A的最小相似度βk大于初始設(shè)定的閾值β，則將β替換為作為閾值繼續(xù)進(jìn)行訓(xùn)練。第k輪迭代時(shí)的基于自適應(yīng)閾值的貪心匹配算法如算法1所示。

算法1?基于自適應(yīng)閾值的貪心匹配。

輸入?用戶(hù)相似度矩陣Mp×q，初始閾值β，種子錨用戶(hù)對(duì)集合A最大相似度βk;

輸出?候選錨用戶(hù)對(duì)集合Qk。

程序前

1）

將Mp×q的相似度按從大到小排序得到集合T={（vi1，vj2，sim（vi1，vj2））}，i=1，2，…，p， j=1，2，…，q;

2）

初始化集合Yk

3）

for vi1，vj2，sim（vi1，vj2） inTdo

4）

if sim（vi1，vj2）<β then

5）

end for

6）

if βi>β then

7）

β=βi

8）

if vi1 not in Yk and vj2 not in Yk then

9）

將用戶(hù)對(duì)（vi1，vj2）加入Qk

10）

將用戶(hù)vi1和vj2加入Yk

11）

end for

12）

return Qk

程序后

2.3.3?迭代對(duì)齊

迭代對(duì)齊是指將第k輪迭代產(chǎn)生的候選錨用戶(hù)對(duì)集合Qk加入訓(xùn)練集A用于k+1輪訓(xùn)練。迭代對(duì)齊能利用新對(duì)齊的用戶(hù)對(duì)持續(xù)優(yōu)化嵌入空間，同時(shí)每次迭代新對(duì)齊錨用戶(hù)對(duì)只會(huì)參與下一次迭代，避免引發(fā)錯(cuò)誤傳遞導(dǎo)致對(duì)齊性能下降。

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

為驗(yàn)證本文所提出的用戶(hù)對(duì)齊算法的性能，在兩個(gè)真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)來(lái)自文獻(xiàn)[14]的文章。表1是兩個(gè)數(shù)據(jù)集的具體信息。

3.1?基準(zhǔn)算法

本文共選用如下基準(zhǔn)算法作比較：

MAG（Manifold Alignment on traditional Graphs）?是一種基于傳統(tǒng)圖的流形對(duì)齊方法。

MAH（Manifold Alignment on Hypergraph）[13]利用超圖來(lái)對(duì)高階關(guān)系進(jìn)行建模，通過(guò)對(duì)用戶(hù)所有可能的候選用戶(hù)進(jìn)行排序找到對(duì)齊用戶(hù)。

IONE[14]在IONE中，用戶(hù)節(jié)點(diǎn)用三個(gè)向量表示：節(jié)點(diǎn)向量、輸入向量和輸出向量。利用負(fù)采樣和約束來(lái)獲得用戶(hù)潛在空間，利用梯度下降法進(jìn)行訓(xùn)練。

ABNE[15]該方法是最新提出的基于注意力機(jī)制的用戶(hù)對(duì)齊算法。

CrossMNA[16]該方法是最新提出的基于嵌入的跨多網(wǎng)絡(luò)用戶(hù)對(duì)齊算法。

3.2?評(píng)價(jià)指標(biāo)與參數(shù)設(shè)置

本文使用常用的hits@N作為評(píng)價(jià)指標(biāo)：

hits@N=RightCount@N12+RightCount@N21TestAnchors×2

其中：RightCount@N表示測(cè)試集用戶(hù)預(yù)測(cè)得到的topN個(gè)用戶(hù)中正確的用戶(hù)數(shù)，下標(biāo)代表對(duì)齊方向。TestAnchors表示測(cè)試集的錨用戶(hù)對(duì)數(shù)。對(duì)于相同的N，hits@N越高代表越好的性能。

本文參數(shù)設(shè)置如下：負(fù)采樣的候選集參數(shù)K為100;用于控制正負(fù)例的間隔的兩個(gè)參數(shù)λ1=0.01、λ2=2;余弦相似度與結(jié)構(gòu)相似度的權(quán)重參數(shù)α為0.6，自適應(yīng)閾值的初始閾值β為0.75，嵌入空間維度為120。

3.3?實(shí)驗(yàn)結(jié)果與分析

3.3.1?對(duì)比算法結(jié)果分析

本文提出的KGEUA與各基準(zhǔn)算法的最優(yōu)hits@N如表2所示。實(shí)驗(yàn)結(jié)果顯示，本文的KGEUA相比其他五種算法在hits@N的效果上都更好。除此之外，本文還對(duì)各算法在不同參數(shù)設(shè)置情況下的性能進(jìn)行了分析，分析結(jié)果如圖3所示。

從圖3（a）可以看出，本文的KGEUA在不同的訓(xùn)練集比例下的hits@10都比其余基準(zhǔn)算法更好。從圖3（b）中可以發(fā)現(xiàn)，本文的KGEUA在hits@1～hits@30的性能上均優(yōu)于各基準(zhǔn)算法。IONE和ABNE雖然是基于網(wǎng)絡(luò)結(jié)構(gòu)嵌入，但卻是將兩個(gè)社交網(wǎng)絡(luò)孤立地看待，單獨(dú)嵌入到不同的向量空間中，再設(shè)計(jì)對(duì)齊算法進(jìn)行對(duì)齊，雖能通過(guò)種子錨用戶(hù)對(duì)向量空間進(jìn)行優(yōu)化，但損失了用戶(hù)對(duì)的網(wǎng)絡(luò)結(jié)構(gòu)上的相似性信息。而最新方法CrossMNA雖然考慮了網(wǎng)絡(luò)間的結(jié)構(gòu)與用戶(hù)的網(wǎng)絡(luò)內(nèi)結(jié)構(gòu)信息，能夠很好地應(yīng)對(duì)同一網(wǎng)絡(luò)下的多個(gè)不同子網(wǎng)絡(luò)的對(duì)齊問(wèn)題，但在不同的社交網(wǎng)絡(luò)間的效果并不好，且模型在生成負(fù)例時(shí)并未考慮負(fù)例的質(zhì)量，導(dǎo)致性能差。本文的KGEUA將兩個(gè)社交網(wǎng)絡(luò)嵌入到統(tǒng)一的低維空間中，再使用擴(kuò)充的正例與高質(zhì)量的負(fù)例優(yōu)化該嵌入空間，能夠很好地保持網(wǎng)絡(luò)結(jié)構(gòu)并學(xué)習(xí)隱藏信息。從圖3（c）中可以看到，本文的KGEUA在各個(gè)嵌入維度的效果都更好，且較小的嵌入維度就能很好地兼顧性能與復(fù)雜度。

3.3.2?算法有效性分析

為驗(yàn)證本文所提出的方法對(duì)用戶(hù)對(duì)齊性能的影響，對(duì)各方法的有效性分析如圖4所示。

為驗(yàn)證迭代對(duì)齊的效果，生成了KGEUA模型的兩個(gè)變體KGEUAiterative和KGEUAnoiterative分別表示使用迭代對(duì)齊和不使用迭代對(duì)齊，并繪制了性能對(duì)比圖如圖4（a）所示。通過(guò)計(jì)算得知，迭代對(duì)齊相比非迭代對(duì)齊在hits@30上提升了3.3個(gè)百分點(diǎn)。因?yàn)樵诿枯喌?，KGEUA會(huì)將新對(duì)齊的用戶(hù)對(duì)加入訓(xùn)練集在下一輪訓(xùn)練中優(yōu)化嵌入空間，既保證了嵌入空間的學(xué)習(xí)又防止錯(cuò)誤選擇帶來(lái)的誤差傳遞。從圖4（b）中可以看出，隨著候選集的擴(kuò)大效果對(duì)齊性能也相應(yīng)地受到影響。需要注意的是，圖4（b）中，K為0代表此時(shí)候選集為全體實(shí)體即隨機(jī)負(fù)采樣，可以看出本文提出的Near_K負(fù)采樣方法能有效提升負(fù)例的質(zhì)量從而提升對(duì)齊性能。

為驗(yàn)證本文提出的自適應(yīng)閾值的匹配方法的有效性，生成模型KGEUA的兩個(gè)變體：KGEUAstatic與KGEUAadaptive。兩個(gè)變體分別表示使用靜態(tài)閾值與使用自適應(yīng)閾值，結(jié)果如圖4（c）所示。當(dāng)采用本文所提出的自適應(yīng)閾值時(shí)對(duì)齊性能很明顯地比固定閾值的對(duì)齊性更好，是因?yàn)檫^(guò)小的靜態(tài)閾值對(duì)用戶(hù)對(duì)的篩選過(guò)于寬松，導(dǎo)致引入噪聲過(guò)多;過(guò)大的靜態(tài)閾值又過(guò)于嚴(yán)苛，導(dǎo)致無(wú)法選到更多的錨用戶(hù)對(duì)。本文提出的KGEUA能根據(jù)訓(xùn)練的進(jìn)行自適應(yīng)的調(diào)整閾值，克服了靜態(tài)閾值選擇不當(dāng)易對(duì)性能造成影響的弊端。

最后，由圖4（d）的結(jié)果看出，本文提出的將結(jié)構(gòu)相似度與余弦相似度相結(jié)合的方法確實(shí)能學(xué)習(xí)到用戶(hù)的結(jié)構(gòu)信息并有效提升用戶(hù)對(duì)齊的性能，其中csim表示使用余弦相似度，ssim表示使用結(jié)構(gòu)相似度，csim+ssim表示將兩者結(jié)合。

綜上所述，本文提出的KGEUA在真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集TwitterFoursquare上的對(duì)齊性能比基準(zhǔn)算法有顯著提升，驗(yàn)證了本文算法的有效性。

4?結(jié)語(yǔ)

本文提出一種基于知識(shí)圖嵌入的跨社交網(wǎng)絡(luò)用戶(hù)對(duì)齊算法。該算法利用知識(shí)圖嵌入方法將兩個(gè)社交網(wǎng)絡(luò)嵌入到統(tǒng)一的低維向量空間中，并提出Near_K負(fù)采樣方法與正例擴(kuò)充方法提高嵌入質(zhì)量。除此之外，提出基于自適應(yīng)閾值的貪心匹配方法減少引入的噪聲，同時(shí)迭代地將新對(duì)齊的用戶(hù)對(duì)加入到訓(xùn)練集中優(yōu)化向量空間。本文算法在真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集Twitter和Foursquare上實(shí)現(xiàn)用戶(hù)對(duì)齊，并取得了很好的效果。本文只針對(duì)了社交網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)信息，并未使用其余屬性信息。下一步工作是將網(wǎng)絡(luò)結(jié)構(gòu)中易獲取、真實(shí)度高的屬性信息加入到匹配過(guò)程中，優(yōu)化向量空間以提升對(duì)齊性能。

參考文獻(xiàn) （References）

[1]SUN Y， HAN J， YAN X， et al. Mining knowledge from interconnected data： a heterogeneous information network analysis approach[J]. Proceedings of the VLDB Endowment， 2012， 5（12）： 2022-2023.

[2]GlobalWebIndex. GlobalWebIndexs flagship report on the latest trends in social media[EB/OL].[2019-04-11]. https：//www.globalwebindex.com/hubfs/Downloads/SocialH22018report.pdf.

[3]CARMAGNOLA F， CENA F. User identification for crosssystem personalisation[J]. Information Sciences， 2009， 179（1/2）： 16-32.

[4]DENG Z， SANG J， XU C. Personalized video recommendation based oncrossplatform user modeling[C]// Proceedings of the 2013 IEEE International Conference on Multimedia and Expo. Piscataway： IEEE， 2013： 1-6.

[5]YAN M， SANG J， MEI T， et al. Friend transfer： Coldstart friend recommendation with crossplatform transfer learning of social knowledge[C]// Proceedings of the 2013 IEEE International Conference on Multimedia and Expo. Piscataway： IEEE， 2013： 1-6.

[6]楊奕卓， 于洪濤， 黃瑞陽(yáng)， 等. 基于融合表示學(xué)習(xí)的跨社交網(wǎng)絡(luò)用戶(hù)身份匹配[J]. 計(jì)算機(jī)工程， 2018， 44（9）： 45-51.（YANG Y Z， YU H T， HUANG R Y， et al. Crosssocial network user identity matching based on fusion representation learning[J]. Computer Engineering， 2018， 44（9）： 45-51.）

[7]KONG X， ZHANG J， YU P S. Inferring anchor links across multiple heterogeneous social networks[C]// Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. New York： ACM， 2013： 179-188.

[8]SHU K， WANG S， TANG J， et al. User identity linkage across online social networks： a review[J]. ACM SIGKDD Explorations Newsletter， 2017， 18（2）： 5-17.

[9]ZAFARANI R， LIU H. Connecting users across social media sites： a behavioralmodeling approach[C]// Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2013： 41-49.

[10]RIEDERER C， KIM Y， CHAINTREAU A， et al. Linking users across domains with location data： Theory and validation[C]// Proceedings of the 25th International Conference on World Wide Web. New York： ACM， 2016： 707-719.

[11]GOGA O， LEI H， PARTHASARATHI S H K， et al. Exploiting innocuous activity for correlating users across sites[C]// Proceedings of the 22nd International Conference on World Wide Web. New York： ACM， 2013： 447-458.

[12]NARAYANAN A， PASKOV H， GONG N Z， et al. On the feasibility of Internetscale author identification[C]// Proceedings of the 2012 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2012： 300-314.

[13]TAN S， GUAN Z， CAI D， et al. Mapping users across networks by manifold alignment on hypergraph[C]// Proceedings of the 28th AAAI Conference on Artificial Intelligence. Menlo Park， CA： AAAI Press， 2014： 159-165.

[14]LIU L， CHEUNG W K， LI X， et al. Aligning users across social networks using network embedding[C]// Proceedings of the 25th International Joint Conference on Artificial Intelligence. Menlo Park， CA： AAAI Press， 2016： 1774-1780.

[15]LIU L， ZHANG Y， FU S， et al. ABNE： an attention based network embedding for user alignment across social networks[J]. IEEE Access， 2019， 7： 23595-23605.

[16]CHU X， FAN X， YAO D， et al. Crossnetwork embedding for multinetwork alignment [C]// Proceedings of the 2019 International World Wide Web Conference. New York： ACM， 2019： 273-284.

[17]ZHANG J， PHILIP S Y. Integrated anchor and social link predictions across social networks[C]// Proceedings of the 24th International Joint Conference on Artificial Intelligence. Menlo Park， CA： AAAI Press， 2015： 2125-2132.

[18]ZHANG J， YU P S. PCT： partial coalignment of social networks[C]// Proceedings of the 25th International Conference on World Wide Web. New York： ACM， 2016：749-759.

[19]吳錚， 于洪濤， 黃瑞陽(yáng)， 等. 基于信息熵的跨社交網(wǎng)絡(luò)用戶(hù)身份識(shí)別方法[J]. 計(jì)算機(jī)應(yīng)用， 2017， 37（8）： 2374-2380.（WU Z， YU H T， HUANG R Y， et al. User identification across multiple social networks based on information entropy[J]. Journal of Computer Applications， 2017， 37（8）： 2374-2380.）

[20]BORDES A， USUNIER N， GARCIADURAN A， et al. Translating embeddings for modeling multirelational data[C]// Proceedings of the 27th Annual Conference on Neural Information Processing Systems. Cambridge， MA： MIT Press， 2013： 2787-2795.

[21]DUCHI J， HAZAN E， SINGER Y. Adaptive subgradient methods for online learning and stochastic optimization[J]. Journal of Machine Learning Research， 2011， 12： 2121-2159.

[22]ADAMIC L A， ADAR E. Friends and neighbors on the Web[J]. Social Networks， 2003， 25（3）： 211-230.

This work is partially supported by National Key Research and Development Program of China （2017YFB0802305）.

TENG Lei， born in 1995， M. S. candidate. His research interests include machine learning， data mining.

LI Yuan， born in 1992， M. S.. Her research interests include network security， deep learning.

LI Zhixing， born in 1985， Ph. D.， associate professor. His research interests include natural language processing， knowledge graph， data mining， machine learning.

HU Feng， born in 1985， Ph. D.， professor. His research interests include data mining， rough set， granular computing.