一種基于深度學(xué)習(xí)的動態(tài)社交網(wǎng)絡(luò)用戶對齊方法

王飛揚，冀鵬欣，孫 笠，危 倩，李 根，張忠寶

（北京郵電大學(xué)計算機學(xué)院，北京 100876）

1 引言

近年來，隨著社交網(wǎng)絡(luò)的不斷涌現(xiàn)和普及，人們逐漸開始參與多個社交網(wǎng)絡(luò)平臺，享受多樣的社交服務(wù).社交網(wǎng)絡(luò)對齊問題應(yīng)運而生，即在不同的社交網(wǎng)絡(luò)中識別屬于同一自然人的社交賬戶.社交網(wǎng)絡(luò)對齊可以支持廣泛的應(yīng)用，如鏈接預(yù)測、異常檢測和跨域推薦等.總體而言，社交網(wǎng)絡(luò)的對齊為跨社交網(wǎng)絡(luò)的廣度學(xué)習(xí)鋪平了道路，越來越受到學(xué)術(shù)界和工業(yè)界的關(guān)注.大多現(xiàn)有的方法［1～18］研究的是靜態(tài)社交網(wǎng)絡(luò)間的對齊，它們僅考慮一個快照中的網(wǎng)絡(luò)特性.然而，社交網(wǎng)絡(luò)本質(zhì)上是高度動態(tài)，并且不斷發(fā)展的.DNA（Dynamic Network Alignment）［19］考慮了網(wǎng)絡(luò)拓撲結(jié)構(gòu)的動態(tài)演化，但忽略了同樣很有價值的屬性特征.事實上，一個人在社交網(wǎng)絡(luò)中會不斷地改變他的朋友列表并更新文本或位置，這種動態(tài)性揭示了靜態(tài)場景中被忽略的用戶的行為模式.在同一時段，不同社交網(wǎng)絡(luò)中的同一自然人往往會表現(xiàn)出相似的行為，根據(jù)行為出現(xiàn)的時期，本文可以把靜態(tài)網(wǎng)絡(luò)中難以區(qū)分的用戶區(qū)別開來.圖1 給出了一個動態(tài)網(wǎng)絡(luò)對齊與靜態(tài)網(wǎng)絡(luò)對齊的對比實例.不同顏色的圖表示不同的社交網(wǎng)絡(luò)，每個結(jié)點都是一個社交帳號.連接不同網(wǎng)絡(luò)間結(jié)點的垂直黑線表示結(jié)點之間的對應(yīng)關(guān)系，即a和a'是已知的對齊結(jié)點.靠近每個結(jié)點的虛線框表示該用戶的主題或關(guān)鍵字，展示了社交帳戶的屬性.箭頭展示了社交網(wǎng)絡(luò)隨時間的動態(tài)演化.僅考慮第一個快照，網(wǎng)絡(luò)A中的b，c和網(wǎng)絡(luò)B中的b'，c'行為均相同，靜態(tài)對齊方法無法區(qū)分網(wǎng)絡(luò)B中b和c的對齊結(jié)點.然而，在第二個快照中，b和c在結(jié)構(gòu)上表現(xiàn)不同.進一步地，它們在第三個快照中的屬性方面仍存在差異.同時，b的行為總是與b'相同，c和c'也一致.因此，本文可以非?？隙ǖ卣f，賬戶b和b'屬于同一自然人，而賬戶c和c'屬于另一自然人.靜態(tài)社交網(wǎng)絡(luò)是一個僅關(guān)注用戶在某一階段的結(jié)構(gòu)和屬性的快照，而動態(tài)社交網(wǎng)絡(luò)則是考慮整個時間軸上的信息，從而使用戶的行為模式更加清晰.通過捕獲用戶的動態(tài)行為模式，本文可以使個體的表示更加精確和有判別性，從而對實現(xiàn)對齊有所裨益.

圖1 利用結(jié)構(gòu)和屬性的動態(tài)社交網(wǎng)絡(luò)對齊樣例

上述觀察結(jié)果促使本文重新思考動態(tài)情境下的社交網(wǎng)絡(luò)對齊.然而，在利用社交網(wǎng)絡(luò)的動態(tài)性進行對齊方面仍然存在3個主要挑戰(zhàn).

（1）如何對每個用戶的動態(tài)模式進行建模？用戶的行為總是隨著動態(tài)社交網(wǎng)絡(luò)的演化而變化，因此用戶的動態(tài)模式是復(fù)雜的，而淺層模型由于其有限的表現(xiàn)形式很難捕捉到網(wǎng)絡(luò)的高度非線性的動態(tài)模式.

（2）如何有效融合結(jié)構(gòu)和屬性的動態(tài)性？社交網(wǎng)絡(luò)通常有兩個特性，即結(jié)構(gòu)和屬性.結(jié)構(gòu)描述了社交網(wǎng)絡(luò)用戶之間的關(guān)系，包含了用戶間社交互動的規(guī)律.屬性，例如名稱、文本和位置等，通常展示用戶的主題或偏好.因此，此挑戰(zhàn)的關(guān)鍵在于如何有效地融合結(jié)構(gòu)和屬性的動態(tài)性，以獲得全面的網(wǎng)絡(luò)嵌入表示.

（3）如何設(shè)計對齊算法？在靜態(tài)網(wǎng)絡(luò)中亦很難獲取一組具有相同使用者的賬號，更不用說在動態(tài)場景中了.此外，一個用戶很可能在不同的網(wǎng)絡(luò)中與不同的好友聯(lián)系，并在社交網(wǎng)絡(luò)中為了不同的目的做出不同的行為.缺乏標簽數(shù)據(jù)和網(wǎng)絡(luò)間普遍存在的差異性，使得這一問題更具挑戰(zhàn)性.

為了解決上述問題，本文設(shè)計了一個深度架構(gòu)來解決動態(tài)社交網(wǎng)絡(luò)對齊問題，稱為DeepDSA（Deep learning based Dynamic Social network Alignment method）.

在DeepDSA 中，本文提出了一種用于復(fù)雜動態(tài)性建模的深度神經(jīng)模型.用戶在不同快照上具有特定的特征，這些快照自然地形成一個時間序列.因此，本文提出了一個基于門控循環(huán)單元（Gated Recurrent Unit，GRU）的序列模型，分別用于對每個社交網(wǎng)絡(luò)的結(jié)構(gòu)和屬性的動態(tài)性進行建模.具體地說，本文設(shè)計了一個GRU 編碼器來對結(jié)構(gòu)或?qū)傩缘膭討B(tài)特征進行建模，并將每次的輸出反饋到解碼器中對結(jié)構(gòu)或?qū)傩赃M行預(yù)測.序列預(yù)測任務(wù)總是存在一個交叉依賴的問題，即當(dāng)前特征可能主要受間接的歷史而不是直接前繼的影響［20］.因此，針對這一問題，本文在神經(jīng)模型的核心部分設(shè)計了一個注意力機制，并將每個時間階段的隱藏狀態(tài)作為相應(yīng)的動態(tài)性表示.

對于第二個挑戰(zhàn)，本文通過分別保持每個社交網(wǎng)絡(luò)相同用戶結(jié)構(gòu)和屬性之間的相關(guān)性來融合此二元動態(tài)性.具體來說，首先將前一個問題得到的每個時間階段的結(jié)構(gòu)表示通過時間衰減效應(yīng)進行合并得到結(jié)構(gòu)嵌入表示，屬性特征亦然.然后，對于每個社交網(wǎng)絡(luò)，通過保持同一用戶的結(jié)構(gòu)和屬性之間的相關(guān)性，對每個用戶施加約束.結(jié)構(gòu)特征和屬性特征分別描述了用戶的不同部分，它們相互補充，使用戶更具可判別性.為了將結(jié)構(gòu)和屬性結(jié)合在一起，對每個用戶結(jié)構(gòu)和屬性的聯(lián)合概率進行最大似然估計.最后，將結(jié)構(gòu)嵌入和屬性嵌入結(jié)合起來，作為每個用戶的原始的綜合嵌入表示.

對于第三個挑戰(zhàn)，在子空間學(xué)習(xí)的啟發(fā)下，本文以半監(jiān)督的方式進行空間變換學(xué)習(xí)，并將每個網(wǎng)絡(luò)的原始嵌入投影到一個目標子空間中，在此子空間中每個自然人均有唯一的表達.由于普遍存在的網(wǎng)絡(luò)間差異性，直接在原始嵌入空間中進行相似性度量可能是不合適的.每一個特定的網(wǎng)絡(luò)都容易產(chǎn)生不同的偏移，每個用戶的本質(zhì)可能在原始空間中被隱藏.因此，空間轉(zhuǎn)換可以展現(xiàn)用戶的本質(zhì)，以便更好地對齊.具體地說，利用一個前饋神經(jīng)網(wǎng)絡(luò)來擬合變換，并利用部分的已知標簽用戶以半監(jiān)督的方式進行空間變換學(xué)習(xí).

本文所提出的DeepDSA 方法的優(yōu)點在于，它具有強大的非線性學(xué)習(xí)能力，能夠捕捉復(fù)雜的結(jié)構(gòu)和屬性的動態(tài)性，并對整體結(jié)構(gòu)進行統(tǒng)一優(yōu)化，以自然地對用戶的本質(zhì)特征進行建模.

為了評估所提出的DeepDSA 方法，本文首先通過構(gòu)建一系列網(wǎng)絡(luò)快照（通過收集的時間戳）來仿真現(xiàn)實世界中的動態(tài)社交網(wǎng)絡(luò).然后，本文在真實數(shù)據(jù)集上進行了廣泛的實驗，并證明了所提出的DeepDSA 方法的明顯優(yōu)勢.

本文的主要創(chuàng)新點如下：

（1）同時運用結(jié)構(gòu)和屬性特征，解決動態(tài)場景下社交網(wǎng)絡(luò)對齊問題；

（2）設(shè)計了一個統(tǒng)一的深度神經(jīng)結(jié)構(gòu)DeepDSA，提出了一個來捕捉用戶結(jié)構(gòu)和屬性的復(fù)雜動態(tài)性的深度神經(jīng)模型，從而實現(xiàn)社交網(wǎng)絡(luò)的對齊，并對整個框架聯(lián)合優(yōu)化學(xué)習(xí)；

（3）在真實數(shù)據(jù)集上進行了大量的實驗，實驗結(jié)果證明了所提出的DeepDSA方法存在明顯的優(yōu)越性.

2 相關(guān)工作與預(yù)備知識

2.1 相關(guān)工作

社交網(wǎng)絡(luò)用戶對齊問題，是指在不同的社交網(wǎng)絡(luò)中識別出屬于同一個人的社交賬號，由Zafarani 等人［14］提出.Zhang 等人［16］提出了基于能量的模型COSNET（Connecting Heterogeneous Social Networks），通過考慮本地和全局一致性來鏈接用戶身份.COSNET首先提取基于距離的輪廓特征和基于鄰域的網(wǎng)絡(luò)特征，然后使用聚合算法獲得局部一致性.Su 等人［7］設(shè)計了一個約束的雙重嵌入模型，將社交網(wǎng)絡(luò)的對齊問題轉(zhuǎn)化為一個統(tǒng)一的優(yōu)化問題，將多個社交網(wǎng)絡(luò)嵌入到一個公共的潛在空間中進行協(xié)調(diào).Mu 等人［21］提出“潛在用戶空間”的概念，以建模潛在真實用戶與其在各種社交平臺上觀察到的投影之間的關(guān)系，從而使真實用戶越相似，則其在潛在用戶空間中的畫像越接近.Man等人［6］采用基于嵌入的網(wǎng)絡(luò)特征將社交網(wǎng)絡(luò)結(jié)構(gòu)映射到低維空間，基于用戶身份的潛在特征提出了一種投影方法.Liu 等人［5］提出的IONE（Input-Output Network Embedding）方法提取基于嵌入的網(wǎng)絡(luò)特征，同時學(xué)習(xí)每個用戶的拓撲結(jié)構(gòu)，種子的對齊用戶對約束著社交關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)的上下文傳遞.Zhou 等人［3］提出了半監(jiān)督的端到端方法DeepLink，對網(wǎng)絡(luò)進行采樣，并學(xué)習(xí)將網(wǎng)絡(luò)節(jié)點編碼成矢量表示，以捕獲局部和全局網(wǎng)絡(luò)結(jié)構(gòu)，進而利用這些結(jié)構(gòu)通過深度神經(jīng)網(wǎng)絡(luò)對結(jié)點進行對齊.

幾乎所有現(xiàn)有方法均聚焦在靜態(tài)場景下的社交網(wǎng)絡(luò)用戶對齊而忽略了社交網(wǎng)絡(luò)固有的動態(tài)性.Sun 等人［19］嵌入了結(jié)構(gòu)的局部和全局動態(tài)性并提出了DNA方法，通過矩陣分解，提出了通過嵌入空間相互作用的統(tǒng)一優(yōu)化方法來構(gòu)造公共空間，并設(shè)計了交替優(yōu)化算法來逼近局部最優(yōu)，但是其忽略了同樣有價值的屬性動態(tài)性.

2.2 問題定義

在動態(tài)場景中，本文考慮帶有時間戳的社交網(wǎng)絡(luò)的結(jié)構(gòu)和屬性.如圖1 所示，本文將網(wǎng)絡(luò)分割成片，并在時域中構(gòu)造一系列的圖快照.每個快照都反映了當(dāng)前時間片中網(wǎng)絡(luò)的特征.把一個動態(tài)的社交網(wǎng)絡(luò)定義為G=(V，S，A)，其中，V={v1，v2，…，vn}，S={S1，S2，…，ST}和A={A1，A2，…，AT}，分別表示結(jié)點集、結(jié)構(gòu)集和屬性集.對于每個和分別是第i時間片中每個用戶的結(jié)構(gòu)特征矩陣和屬性特征矩陣.

考慮到兩個動態(tài)的社交網(wǎng)絡(luò)Gs和Gt，在不失一般性的前提下，已知兩個網(wǎng)絡(luò)間的部分對齊賬號作為標簽數(shù)據(jù).本文引入了一個對齊結(jié)點對的集合Pst={(vs，vt)|vs∈Vs，vt∈Vt}，其中每個對齊結(jié)點對(vs，vt)表示Gs中的賬號vs和Gt中的賬號vt在現(xiàn)實中屬于同一自然人.

本文總結(jié)了論文中的主要符號（見表1）并將研究問題正式定義如下.

表1 主要符號和定義

定義1動態(tài)社交網(wǎng)絡(luò)用戶對齊問題.給定兩個動態(tài)社交網(wǎng)絡(luò)，即源網(wǎng)絡(luò)Gs和目標網(wǎng)絡(luò)Gt以及一組已知對齊結(jié)點Pst，動態(tài)社交網(wǎng)絡(luò)對齊的問題旨在為每個社交賬戶找到兩個映射函數(shù)Φs和Φt，其將社交賬號映射至真實歸屬自然人，即Φs(vs)=Φt(vt)當(dāng)且僅當(dāng)(vs，vt)在Pst中存在.

2.3 門控循環(huán)單元

如圖2所示，門控循環(huán)單元（GRU）是循環(huán)神經(jīng)網(wǎng)絡(luò)（Recurrent Neural Networks，RNN）的另一個變體，與基本的長短期記憶網(wǎng)絡(luò)（Long Short-Term Memory networks，LSTM）相比，它能更好地將序列數(shù)據(jù)歷史的信息連接到本文的問題［22］中.GRU 將輸入和遺忘門耦合到更新門中，以避免長期依賴性問題.最后，它的輸出門（稱為重置門）只對塊輸入的循環(huán)連接進行門控.具體來說，本文將每個時間切片的結(jié)構(gòu)或?qū)傩蕴卣饕来屋斎隚RU 單元，并獲得相應(yīng)的輸出.GRU 單元在第t步的計算流程如下：

圖2 GRU細胞的內(nèi)部結(jié)構(gòu)

其中，xt是第t時刻的特征輸入，ht-1和ht是隱藏狀態(tài)同時也是上一步和當(dāng)前步驟的輸出，σ表示sigmoid 函數(shù)，⊙表示Hadamard 積.GRU 可以通過逐步地更新具有歷史和當(dāng)前特征的單元狀態(tài)，自然地對序列輸入進行建模并捕捉動態(tài)性.在每個步驟t中，細胞接收先前的隱藏狀態(tài)ht-1和當(dāng)前的輸入xt，以獲得當(dāng)前的輸出ht.重置門通過rt確定ht-1對新內(nèi)存的權(quán)重.另外，更新門通過zt確定ht-1到下一步的傳輸量是多少.

3 DeepDSA

如圖3 所示，為了解決動態(tài)社交網(wǎng)絡(luò)用戶對齊問題，本文提出DeepDSA 模型.首先，將動態(tài)網(wǎng)絡(luò)劃分為T個切片，分別構(gòu)造每個切片的結(jié)構(gòu)和屬性特征.其次，設(shè)計一個基于GRU 的序列模型，利用注意力機制分別對結(jié)構(gòu)和屬性的動態(tài)性進行建模.然后，對結(jié)構(gòu)和屬性進行融合，得到每個用戶的嵌入表示.最后，利用空間變換，將用戶嵌入由正交初始化矩陣Q控制的子空間中.

3.1 動態(tài)性建模

如圖3（a）所示，社交網(wǎng)絡(luò)中的一個結(jié)點，通常有兩種特征：結(jié)構(gòu)和屬性.結(jié)構(gòu)顯示用戶之間的鏈接.如果存在關(guān)注/被關(guān)注關(guān)系，則兩個用戶是鏈接的，這意味著他們彼此很接近.另外，屬性揭示了社交網(wǎng)絡(luò)的部分固有特征.特定于某個用戶，屬性特征的覆蓋范圍很廣，例如，名稱、文本和位置.此外，社交網(wǎng)絡(luò)的結(jié)構(gòu)和屬性都表現(xiàn)出高度的動態(tài)性，因為用戶總是在添加/刪除彼此之間的鏈接同時更新文本或位置，這會體現(xiàn)出有價值的附加信息，并且蘊含了靜態(tài)社交網(wǎng)絡(luò)中忽略的動態(tài)行為模式.因此，本文提出的模型旨在捕捉結(jié)構(gòu)和屬性的豐富動態(tài)性.

圖3 DeepDSA模型圖

本文首先將動態(tài)網(wǎng)絡(luò)劃分為T個切片，分別構(gòu)造每個切片的結(jié)構(gòu)特征和屬性特征.對于結(jié)構(gòu)特征，一個簡單而直接的方法是利用二進制鄰接矩陣，其中對于每個M∈Rn×n，i，j∈[1，n]，如果用戶i和用戶j之間存在鏈接，則元素Mi，j為1，否則為0.進一步地，利用Deep-Walk 中的隨機游走［23，24］來保持高階的臨近性.Deep-Walk已經(jīng)被證明實際上是一種近似特征矩陣Si的采樣方法：

對于屬性特征，本文使用用戶的文本并對文本進行矢量表示.本文中亦將位置名稱視為文本.一種直接的方法是詞袋（Bag Of Words，BOW）模型，但其表示效果通常很差，因為BOW 忽略了許多文本的表示信息，如單詞的順序.潛在狄利克雷分配（Latent Dirichlet Allocation，LDA）也是一種常見的主題建模技術(shù)（從文本中提取主題/關(guān)鍵詞），但它很難訓(xùn)練，且結(jié)果也很難評估.因此，本文采用Doc2vec［25］，一種無監(jiān)督的學(xué)習(xí)算法，它可以學(xué)習(xí)可變長度的文本片段（如句子和文檔）的矢量表示.具體來說，本文利用分布式詞袋（Distributed Bag Of Words version of Paragraph Vector，PVDBOW）算法，如圖4 所示，文本/文檔由內(nèi)容詞和位置詞組成，文本向量用于預(yù)測其自身的單詞.Doc2vec受到單詞表示學(xué)習(xí)方法的啟發(fā)，對于一個文本，它的向量表示被用來預(yù)測其自身的單詞.實際上，這意味著在每次梯度下降的迭代中，本文都會采樣一個文本窗口，然后從文本窗口中隨機抽取一個單詞，并在給定文本向量的情況下形成一個分類任務(wù)［25］.值得一提的是，本文總是會采樣到文本的位置詞，因為位置信息對于用戶畫像來說是非常簡明和決定性的特性.在每個時間片中，通過取每個用戶的文本向量的平均值來構(gòu)造特征矩陣A.

圖4 學(xué)習(xí)文本向量的框架

對于每個社交網(wǎng)絡(luò)，本文從結(jié)構(gòu)和屬性2個角度對網(wǎng)絡(luò)的動態(tài)性進行建模.由于結(jié)構(gòu)與屬性建模過程基本相同，本文僅以結(jié)構(gòu)動態(tài)性建模部分為例，屬性動態(tài)性建模過程同理可得.

如圖3（b）所示，在將動態(tài)網(wǎng)絡(luò)分割成T片后，構(gòu)造一組結(jié)構(gòu)特征S={S1，S2，…，ST}.對于i∈[1，T]和是Si的第m行，表示第i時間片上第m個用戶的特征.鑒于GRU 內(nèi)在的對序列的動態(tài)建模能力，本文使用GRU 編碼器來收集每個用戶m的序列特征，并保留相應(yīng)的輸出Hm=然后將Hm輸入到GRU 解碼器中，對結(jié)構(gòu)進行預(yù)測，即Sm可以由重構(gòu).其背后的依據(jù)在于，個人在社交網(wǎng)絡(luò)中的結(jié)構(gòu)演化是確定性的而不是隨機的，并且當(dāng)前的結(jié)構(gòu)受到歷史因素的影響［26，27］.此建模模型對于屬性特征同樣適用，依據(jù)在于用戶的主題或關(guān)鍵字總是平滑地發(fā)展并且歷史信息被用來動態(tài)地建模用戶畫像［28］.

此外，序列預(yù)測通常存在交叉依賴問題［20］.當(dāng)前的特征可能主要是受間接歷史而不是直接前繼歷史所影響.例如，社交網(wǎng)絡(luò)用戶可能在某個時間點結(jié)交新朋友并對某個新話題感興趣，這會受到其老朋友而不是最近結(jié)識的朋友的影響.因此，本文利用注意力機制來解決交叉依賴問題.在第i步，構(gòu)造ei替代hi作為特征，這是通過學(xué)習(xí)所有歷史信息的綜合效應(yīng)而獲得的：

其中，αi={αi，1，αi，2，…，αi，i}衡量當(dāng)前和歷史之間的聯(lián)系，而W是參數(shù)矩陣.序列預(yù)測約束了自動編碼器模型捕捉結(jié)構(gòu)的動態(tài)模式.

3.2 二元動態(tài)性融合

利用上述模型，本文分別捕獲了每個社交網(wǎng)絡(luò)結(jié)構(gòu)和屬性的動態(tài)性.然而，接下來關(guān)鍵的任務(wù)是要有效地融合這兩個方面的特征，以考慮互補信息，從而得到每個用戶的全面嵌入表示.

本文首先將序列模型捕捉到的動態(tài)性與時間衰減效應(yīng)相結(jié)合，分別構(gòu)造結(jié)構(gòu)（us）和屬性（ua）的嵌入表示.對于結(jié)構(gòu)嵌入，具體表示為

其中，時間最臨近的特征由于包含了更多的信息而獲得了更大的貢獻值.ua同理可得.

為了融合結(jié)構(gòu)和屬性，一個簡單的方法是直接拼接us和ua，但不能保證這兩種特性之間的一致性［30］.此外，本文期望通過有效地融合結(jié)構(gòu)信息和屬性信息，更準確地描述用戶，并強調(diào)用戶間的獨特性和差異，以服務(wù)于接下來的對齊任務(wù).因此，本文利用結(jié)構(gòu)和屬性之間的聯(lián)合概率，最大化同一用戶的兩種特征的似然概率.聯(lián)合概率和目標函數(shù)給定如下：

本文最大化同一用戶的對數(shù)似然，同時最小化不同用戶間的結(jié)構(gòu)-屬性的對數(shù)似然.抑制所有不同用戶間的對數(shù)似然會施加一個過于嚴格的約束，即具有高度臨近性的用戶會被疏離，并帶來大量的計算消耗.因此，本文采用負采樣［27］方法.根據(jù)結(jié)點的度分布，其中dv是v的度，抽樣到當(dāng)前為止從未與v有過鏈接的負采樣用戶.重寫目標函數(shù)如下：

其中，k是根據(jù)pn(v)抽樣的負采樣用戶數(shù).利用目標函數(shù)將us和ua連接起來，作為每個網(wǎng)絡(luò)中每個用戶的綜合嵌入u.

3.3 利用動態(tài)性對齊

對源網(wǎng)絡(luò)Gs和目標網(wǎng)絡(luò)Gt進行上述的動態(tài)嵌入表示后，一種簡單的方法是直接測量網(wǎng)絡(luò)間結(jié)點表示的相似度.該方法的實質(zhì)是將嵌入結(jié)點看作原始空間中的結(jié)點，并最小化屬于同一自然人的結(jié)點之間的距離.然而，一個人在社交網(wǎng)絡(luò)中出于不同的目的可能會有不同的行為.在一個網(wǎng)絡(luò)中，某項特征可能得到增強，但在另一個網(wǎng)絡(luò)中卻被隱藏.例如，一個人可能總是在源網(wǎng)絡(luò)中分享他對音樂的興趣，而在目標網(wǎng)絡(luò)中很少或從不分享音樂.此外，由于社交網(wǎng)絡(luò)的高度復(fù)雜性，某些特征信息可能會在整個空間中彌散.例如，有人在源網(wǎng)絡(luò)分享了他的長城之旅和他品嘗的餃子.同時期，他在目標網(wǎng)絡(luò)中關(guān)注了一個中國賬號，并分享了一段京劇.這些行為雖然不盡相同，但都顯示出他與中國有關(guān)，蘊含了潛在的相似性.網(wǎng)絡(luò)間普遍的差異使得直接的相似性度量變得困難和不可行.

如圖3（c）所示，為了解決這個問題，本文首先學(xué)習(xí)空間變換，將原始空間變換為目標子空間.然后將原始數(shù)據(jù)投影到目標子空間，利用部分監(jiān)督信息度量網(wǎng)絡(luò)結(jié)點間的相似性.具體地說，找到一個空間變換Q，并將各網(wǎng)絡(luò)的原始嵌入空間投影到一個公共的目標子空間中，在該子空間中，屬于同一自然人的賬號表示盡可能接近.因此，目標函數(shù)給定如下：

通過空間變換Q，本文減少了網(wǎng)絡(luò)間行為不同的特性的權(quán)重.此外，通過原始坐標基的復(fù)雜旋轉(zhuǎn)和融合，揭示了自然人與網(wǎng)絡(luò)平臺無關(guān)的真實特征，對實現(xiàn)對齊大有裨益.

3.4 總體目標

算法1 總結(jié)了DeepDSA 方法的總體流程.整個損失函數(shù)的定義如下：

其中，和Ltd分別表示源網(wǎng)絡(luò)和目標網(wǎng)絡(luò)的目標函數(shù)，如式（6）所示，并且相同的規(guī)則適用于式（10）所示的和.β和γ是控制權(quán)衡的超參數(shù).為了穩(wěn)定地訓(xùn)練，首先分別預(yù)訓(xùn)練Ld和Lf.然后利用Q進行正交初始化，以統(tǒng)一的方式學(xué)習(xí)整個框架.本文使用RMSProp（Root Mean Square Prop）優(yōu)化器優(yōu)化整個框架.

3.5 時間復(fù)雜度

假設(shè)源網(wǎng)絡(luò)和目標網(wǎng)絡(luò)的賬號個數(shù)為n，網(wǎng)絡(luò)分為T個時間片，嵌入維度為d.首先進行動態(tài)性建模，GRU細胞包含三個門，故編碼器的時間復(fù)雜度為O(3Tnd3)，解碼器相對于編碼器加入了注意力機制，故其時間復(fù)雜度為O(3Tnd3+T2nd).其次是二元動態(tài)性融合，其首先將動態(tài)性與時間衰減效應(yīng)相結(jié)合，然后計算聯(lián)合概率密度，同時進行k次負采樣，時間復(fù)雜度為O(Tnd2(1+k)).最后在子空間進行對齊，具體步驟為空間變換和縮小距離，其時間復(fù)雜度為O(nd3+2nd).省略常數(shù)后，總的時間復(fù)雜度為O(Tnd(T+d2+kd)).

4 實驗

4.1 數(shù)據(jù)集

本文的數(shù)據(jù)集基于經(jīng)典數(shù)據(jù)集Twitter-Foursquare數(shù)據(jù)集（TF）［3，5，7，31］和自采樣數(shù)據(jù)集豆瓣Online-Offline.Twitter和Foursquare 網(wǎng)絡(luò)分別有5 167和5 240 個賬號，2 858組已知的對齊結(jié)點對作為標簽數(shù)據(jù)，然而，TF數(shù)據(jù)集不包含動態(tài)特征，并且獲取同時具有動態(tài)信息和對齊信息的社交網(wǎng)絡(luò)數(shù)據(jù)并不是易事.本文以TF 用戶列表作為種子，對具有動態(tài)的結(jié)構(gòu)和屬性特征的賬號列表進行抓取.此外，為了驗證算法在大規(guī)模社交網(wǎng)絡(luò)中的有效性，本文還爬取了豆瓣社區(qū)網(wǎng)站.豆瓣用戶包括線上活動賬號（Online）和線下活動賬號（Offline），其中線上活動賬號34 737 個，線下活動賬號34 076 個，同時在線上和線下活動的賬號有33 158個，本文將豆瓣用戶間的關(guān)聯(lián)作為結(jié)構(gòu)信息，將豆瓣用戶的評論作為屬性信息.在收集數(shù)據(jù)的同時將數(shù)據(jù)產(chǎn)生的時間記錄下來作為時間戳.在構(gòu)建網(wǎng)絡(luò)快照時，根據(jù)時間戳把處于同一時段的數(shù)據(jù)放到同一個快照中，從而還原真實世界中動態(tài)的社交網(wǎng)絡(luò).例如，如果兩個用戶在某一時間段內(nèi)有聯(lián)系，則他們在對應(yīng)快照中存在著邊，最終這些邊構(gòu)成了快照中的結(jié)構(gòu)信息；同時，用戶在同一時間段內(nèi)的所有評論將生成快照中的屬性信息.數(shù)據(jù)集的統(tǒng)計信息見表2.

表2 數(shù)據(jù)集統(tǒng)計信息

4.2 實驗設(shè)置

對于所提出的DeepDSA 方法，本文以3 個月為間隔生成5個快照，并根據(jù)時間戳將信息分配到相應(yīng)的快照中.將式（2）中的結(jié)構(gòu)特征的階數(shù)和式（10）中的每個賬號的負樣本數(shù)目分別設(shè)置為4和5.使用學(xué)習(xí)率為0.001 的RMSProp 優(yōu)化器對整個框架進行優(yōu)化，式（13）中的超參數(shù)β和γ分別為0.5和1.將預(yù)訓(xùn)練迭代次數(shù)（算法1 中的第7 行）設(shè)置為1 000 以穩(wěn)定訓(xùn)練.使用一個正交初始化的一層10 個神經(jīng)元的前向神經(jīng)網(wǎng)絡(luò)作為空間變換器Q.本文選擇COSNET［16］，MASTER［7］，ULink［21］，PALE［6］，IONE［5］，DeepLink［3］和DNA［19］作為對比方法.所有對比方法的實驗設(shè)置都是在原始文獻的基礎(chǔ)上實現(xiàn)的.為了公平對比，所有對比方法的嵌入維度為128，DeepDSA 中結(jié)構(gòu)和屬性的嵌入維度均為64.

通過隨機刪除賬號生成不同的重疊率的數(shù)據(jù)集.重疊率λ用衡量，其中NS，NT和NF分別是標簽數(shù)據(jù)、Twitter用戶和Foursquare用戶的數(shù)量.

4.3 性能指標

本文使用2種主要指標.

?Precision@k：其由{success@k}求得，其中Ii{success@k}指示前k項的候選列表中是否存在（命中）真實對齊賬號，NA表示測試集中的標簽數(shù)據(jù)數(shù)目.

?MAP@k：其由求得，其中Ranki表示前k項的候選列表中存在真實對齊賬號的排名，NA的定義同Precision@k.MAP 以非線性方式突出強調(diào)了命中候選的排名.

指標值越高表示該方法的對齊效果越好.

4.4 實驗結(jié)果

本文重復(fù)每個實驗10 次并計算平均結(jié)果，實驗結(jié)果如下.

對齊效果.圖5 展示了50%重疊率的TF 數(shù)據(jù)集k值從1到30的比較結(jié)果，圖6展示了50%重疊率的豆瓣數(shù)據(jù)集k值從1 到100 的比較結(jié)果.可以發(fā)現(xiàn)，在TF 數(shù)據(jù)集k=30 時，DeepDSA 的精度接近80%，而其他方法的精度為30%～66%，這表示本文的方法比最好的對比方法精度仍提高了10%，在豆瓣數(shù)據(jù)集中同樣如此.圖7展示了TF 數(shù)據(jù)集k=5 時重疊率λ值從10 到50 的比較結(jié)果.在這些對比中，DeepDSA和DNA 在精度和MAP方面始終優(yōu)于其他比較方法，這是動態(tài)性作用的有力證明.所有的對比方法均存在對社交賬戶表示的局限性，不可避免地會丟失網(wǎng)絡(luò)動態(tài)中豐富的信息.Deep-DSA 構(gòu)造了一個目標子空間來建模潛在的真實自然人畫像，把不同社交賬戶映射在同一目標子空間中進行對齊，而其他方法，例如IONE 中的鏈接亦或PALE和DeepLink 中的映射，則無法顯示用于對齊的現(xiàn)實自然人的真實畫像.DeepDSA 以及MASTER和COSNET 在大多數(shù)情況下由于同時利用了結(jié)構(gòu)信息和屬性信息而表現(xiàn)得更好，而其他方法則僅利用了結(jié)構(gòu)（如IONE）或?qū)傩裕ㄈ鏤LINK）.此外，與傳統(tǒng)方法相比，DeepLink 由于具有深度模型的表示能力而表現(xiàn)得相對較好.需要強調(diào)的是，本文固定了圖5和圖6 中的λ值以及圖7 中的k值.在接下來的實驗中，仍采用λ和k的固定值.事實上，DeepDSA 在不同的設(shè)置下總是表現(xiàn)得更好.綜上所述，DeepDSA 在考慮動態(tài)性的基礎(chǔ)上，很好地對社交網(wǎng)絡(luò)的綜合信息進行了建模.

圖5 TF數(shù)據(jù)集不同k值下的實驗結(jié)果

圖6 豆瓣數(shù)據(jù)集不同k值下的實驗結(jié)果

圖7 TF數(shù)據(jù)集不同重疊率λ下的實驗結(jié)果

訓(xùn)練率的影響.圖8 展示了TF 數(shù)據(jù)集訓(xùn)練率η對對齊結(jié)果的影響.當(dāng)η的值從1%增加到3%時，Deep-DSA 的性能會顯著提高，隨后當(dāng)η超過3%時會飽和.在重疊率為50%的TF 數(shù)據(jù)集上，僅考慮少量的監(jiān)督信息，DeepDSA 在Precision和MAP 方面都表現(xiàn)得更好.此結(jié)果是符合期望的，因為在DeepDSA 中，動態(tài)性是以無監(jiān)督的方式編碼，也就是說，本文可以在沒有監(jiān)督的情況下獲得嵌入空間.另外，通過少量的標簽數(shù)據(jù)即可將原始嵌入空間進行對齊，學(xué)得空間變換.總之，實驗結(jié)果驗證了DeepDSA強大的學(xué)習(xí)能力.

圖8 TF數(shù)據(jù)集不同訓(xùn)練率η下的實驗結(jié)果

動態(tài)性的影響.圖5 展示了TF 數(shù)據(jù)集下DeepDSA采用5 個快照（間隔3 個月）的對齊效果.進一步，改變快照的時間頻率和數(shù)量來聚焦于社交網(wǎng)絡(luò)的動態(tài)特性，以研究動態(tài)特性如何影響網(wǎng)絡(luò)對齊.圖9 展示了DeepDSA 在各種動態(tài)網(wǎng)絡(luò)設(shè)置下的性能.當(dāng)快照的頻率或數(shù)量超過一定的閾值時，Precision和MAP 性能趨于飽和甚至下降.其關(guān)鍵在于，從結(jié)構(gòu)和屬性信息中提取的用戶動態(tài)行為模式具有高度的辨別能力，因為它主要與用戶跨社交網(wǎng)絡(luò)行為的動機和模式相關(guān)，這一論點在社會心理學(xué)研究中已得到了支撐［26］.例如，一個用戶通常會在幾周內(nèi)擴大或縮小一次他的朋友列表，而社交網(wǎng)絡(luò)可能會在幾個月內(nèi)揭示出這種行為.因此，當(dāng)快照的時間頻率與這種行為模式一致或者快照的數(shù)量足以捕獲該行為模式時，性能往往更好.然而，過于冗余的信息并不能進一步促進對齊，還可能引入噪聲，導(dǎo)致性能的下降.

圖9 TF數(shù)據(jù)集不同快照設(shè)置下的實驗結(jié)果

嵌入維度的影響.合適的嵌入維度對結(jié)果也有著不可或缺的影響.本文將維度從10升至300，并在圖10中展示了Precision和MAP.COSNET 在本圖中沒有被列出，因為其是在不對用戶進行嵌入表示的情況下實現(xiàn)的對齊.當(dāng)維度較低時，每種方法對這兩種度量的性能都是不理想的，并且隨著維度的增加而趨于上升.當(dāng)維度超過某個閾值時，性能開始下降.然而，其中Deep-DSA始終優(yōu)于所有對比方法.

圖10 TF數(shù)據(jù)集不同維度下的實驗結(jié)果

結(jié)構(gòu)、屬性和時間的影響.圖11 展示了結(jié)構(gòu)、屬性和時間3 個方面對用戶嵌入和用戶對齊產(chǎn)生的影響.DeepDSA模型的輸入包含n個切片以及各個切片的結(jié)構(gòu)特征和屬性特征，本文略微修改模型，分別去除模型輸入中的結(jié)構(gòu)信息、屬性信息以及時間信息（不按照時間進行切片），得到的結(jié)果如圖11所示.可以發(fā)現(xiàn)，包含結(jié)構(gòu)、屬性和時間信息的模型表現(xiàn)最好，沒有屬性信息的模型次之，沒有時間信息的模型表現(xiàn)中等，沒有結(jié)構(gòu)信息的模型表現(xiàn)最差.這同樣也暗合了圖6中各方法的實驗結(jié)果，DNA沒有屬性信息，其表現(xiàn)次于DeepDSA；MASTER和COSNET沒有時間信息，其表現(xiàn)中等；IONE和PALE只有結(jié)構(gòu)信息，表現(xiàn)較差；ULINK只有屬性信息，表現(xiàn)最差.

圖11 豆瓣數(shù)據(jù)集結(jié)構(gòu)、屬性和時間信息對實驗結(jié)果的影響

5 結(jié)論

本文同時利用結(jié)構(gòu)信息和屬性信息解決動態(tài)社交網(wǎng)絡(luò)對齊問題.事實上，社交網(wǎng)絡(luò)中的動態(tài)性蘊含了一種有很強判別性的模式，這對實現(xiàn)網(wǎng)絡(luò)對齊大有裨益.然而，在網(wǎng)絡(luò)中揭示這種動態(tài)模式是一個巨大的挑戰(zhàn).為了填補這一研究上的空白，本文設(shè)計了DeepDSA 方法來模擬社交網(wǎng)絡(luò)中的豐富動態(tài)性，利用結(jié)構(gòu)和屬性信息來實現(xiàn)網(wǎng)絡(luò)對齊.具體來說，在DeepDSA 方法中，為了捕捉網(wǎng)絡(luò)的動態(tài)特性，本文設(shè)計了一個深度神經(jīng)模型來嵌入和融合結(jié)構(gòu)動態(tài)性和屬性動態(tài)性，以獲得更精確的網(wǎng)絡(luò)表示.為了緩解網(wǎng)絡(luò)間普遍存在的差異性，本文學(xué)習(xí)了一個由少量監(jiān)督信息引導(dǎo)的空間變換，在目標子空間中屬于同一自然人的賬號彼此臨近.本文在真實的數(shù)據(jù)集上進行了大量的實驗，實驗結(jié)果表明DeepDSA明顯優(yōu)于現(xiàn)有的對齊方法.