任尊曉，王 莉

（太原理工大學(xué)大數(shù)據(jù)學(xué)院，晉中 030600）

引 言

信息技術(shù)的快速發(fā)展提供了越來越多的服務(wù)平臺，用戶會在不同平臺上使用不同的服務(wù)內(nèi)容，產(chǎn)生了不同的數(shù)據(jù)信息。多平臺數(shù)據(jù)融通將會為提升服務(wù)質(zhì)量提供有利支撐。融合異構(gòu)網(wǎng)絡(luò)的首要問題是如何對齊不同平臺的對象，即異構(gòu)網(wǎng)絡(luò)對齊問題［1］。

實際應(yīng)用中，異構(gòu)網(wǎng)絡(luò)對齊往往首先選擇節(jié)點的屬性信息作為匹配依據(jù)。例如，社交網(wǎng)絡(luò)平臺或電商平臺中，節(jié)點屬性特征一般包括用戶名、性別、地域、簽名愛好等屬性信息。早期的網(wǎng)絡(luò)對齊研究中，一些研究者以用戶名為出發(fā)點，從詞匯的角度對其進行分析［2］，或?qū)牟煌W(wǎng)絡(luò)獲取的用戶名和用戶簡介抽取出來，采用Jaccard 相似度等方法計算文本字段的相似性來匹配用戶身份［3?6］。這類方法直觀簡單，但是出于隱私保護［7］等考慮，用戶名及一些自報道信息經(jīng)常缺失或具有偽裝、虛假等性質(zhì)，誤導(dǎo)判斷。因此，這種依靠節(jié)點屬性特征的方法對異構(gòu)網(wǎng)絡(luò)對齊問題解決有局限性。

節(jié)點間的關(guān)系結(jié)構(gòu)提供了節(jié)點對齊的新特征［8］。社交平臺上用戶間的行為關(guān)系往往是用戶真實意圖的反映，這種結(jié)構(gòu)信息為異構(gòu)網(wǎng)絡(luò)對齊提供了較為可信的計算依據(jù)。文獻［9?11］通過統(tǒng)計共享的好友數(shù)來計算節(jié)點之間的匹配度。有研究通過分析節(jié)點的公共鄰居集、Jaccard 系數(shù)等［12］鄰居特征來對齊節(jié)點，有利彌補了基于節(jié)點屬性特征的異構(gòu)網(wǎng)絡(luò)對齊的不足。但是，這類方法面臨一個嚴重挑戰(zhàn)，即網(wǎng)絡(luò)結(jié)構(gòu)對噪聲和結(jié)構(gòu)變化非常敏感，當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生細微變化時，節(jié)點對齊的性能往往會下降。

近年來，網(wǎng)絡(luò)表示學(xué)習(xí)的研究為表達網(wǎng)絡(luò)結(jié)構(gòu)的規(guī)則性帶來了新思路。網(wǎng)絡(luò)表示學(xué)習(xí)就是在保持原有網(wǎng)絡(luò)結(jié)構(gòu)特征的基礎(chǔ)上，將網(wǎng)絡(luò)映射到一個低維密集向量空間，同時降低節(jié)點表示對噪聲和網(wǎng)絡(luò)結(jié)構(gòu)變化的敏感性［6，9，13］。基于網(wǎng)絡(luò)表示學(xué)習(xí)的網(wǎng)絡(luò)對齊模型可分為有監(jiān)督模型和無監(jiān)督模型。監(jiān)督模型通常以錨節(jié)點（即事先已知的匹配節(jié)點集）為線索，建立機器學(xué)習(xí)模型得到節(jié)點表征。然而，事先已知的錨節(jié)點數(shù)量往往非常少，甚至幾乎沒有。近年來，一些無監(jiān)督的方法被提出，在沒有任何先驗知識的情況下建立網(wǎng)絡(luò)節(jié)點的表達，主要有兩種路線，基于機器學(xué)習(xí)的策略和基于矩陣分解的策略。在基于機器學(xué)習(xí)策略中，有研究提出了一種多級圖卷積框架，為了處理大規(guī)模的網(wǎng)絡(luò)，設(shè)計了一種空間協(xié)調(diào)機制，在基于網(wǎng)絡(luò)劃分的并行訓(xùn)練和跨不同社交網(wǎng)絡(luò)的賬戶匹配中對表征空間進行對齊［14］。有研究在全局結(jié)構(gòu)上利用節(jié)點的鄰居信息表示節(jié)點［15］，將節(jié)點向量映射到低維空間中，學(xué)習(xí)節(jié)點的潛在表示［16?17］。基于矩陣分解的方法利用矩陣分解得到節(jié)點表示，避免了隨機游走帶來的偏差和計算開銷大的問題。2018年，Heimann 等［15］提出了一種基于矩陣分解的模型REGAL，首先建立網(wǎng)絡(luò)結(jié)構(gòu)和屬性結(jié)合的節(jié)點相似度矩陣，然后采用隨機抽樣策略，選取少量地標(biāo)節(jié)點與所有節(jié)點建立關(guān)聯(lián)，以此來學(xué)習(xí)所有節(jié)點的表示。在多個數(shù)據(jù)集上的實驗表明了此模型的優(yōu)越性，但是，其特征設(shè)定的局限性和隨機抽樣策略所選取地標(biāo)節(jié)點的代表性在一定程度上影響了算法性能。

本文針對REGAL 模型進行了改進，提出一種多尺度特征抽取和采樣策略改進的異構(gòu)網(wǎng)絡(luò)對齊的無監(jiān)督模型。首先，提出一種不同尺度的節(jié)點特征表示，提取節(jié)點特征；然后利用node2vec［18］模型獲得網(wǎng)絡(luò)表征，在此基礎(chǔ)上，設(shè)計了一種基于節(jié)點重要性的地標(biāo)節(jié)點采樣策略選擇最重要的地標(biāo)節(jié)點，改進隨機抽樣策略；引入一種低秩矩陣近似方法進行矩陣分解，學(xué)習(xí)節(jié)點的表示；最后，根據(jù)節(jié)點表示的相似性對網(wǎng)絡(luò)進行對齊。主要貢獻如下：

（1）提出一種包含節(jié)點聚類系數(shù)、鄰居平均度和高階鄰居度的多尺度的網(wǎng)絡(luò)節(jié)點特征表示，增強節(jié)點表達，這3 個特征代表了節(jié)點在不同尺度下的結(jié)構(gòu)特性；

（2）提出一種基于節(jié)點結(jié)構(gòu)信息和重要程度的改進的地標(biāo)節(jié)點采樣策略；

（3）在多個不同領(lǐng)域、規(guī)模和稀疏度的數(shù)據(jù)集上進行實驗，結(jié)果表明本方法優(yōu)于其他基線算法。

1 相關(guān)工作

根據(jù)與本文技術(shù)的相關(guān)程度，主要對基于網(wǎng)絡(luò)表示的異構(gòu)網(wǎng)絡(luò)對齊方法的相關(guān)工作進行闡述。

基于網(wǎng)絡(luò)表示的方法的基本思想是將網(wǎng)絡(luò)中的節(jié)點映射到低維、稠密的向量空間中，達到同時保持網(wǎng)絡(luò)結(jié)構(gòu)規(guī)則性和降維的目標(biāo)，以此進行網(wǎng)絡(luò)對齊。通常，利用網(wǎng)絡(luò)表示方法學(xué)習(xí)到的表征能夠保持原始網(wǎng)絡(luò)結(jié)構(gòu)的特性，例如一階接近性和二階接近性［19］。一階接近性是指節(jié)點與它的一階近鄰之間的拓撲關(guān)系。在二階接近性中，每個節(jié)點扮演兩個角色，即節(jié)點本身和它作為其他節(jié)點的“上下文”角色。Yang 等［20］提出將頂點的文本特征引入到網(wǎng)絡(luò)表示學(xué)習(xí)中學(xué)習(xí)節(jié)點的潛在表征。Tan 等［6］將網(wǎng)絡(luò)映射到超圖上對高階關(guān)系進行建模，學(xué)習(xí)節(jié)點的潛在特征。Liu 等［13］利用網(wǎng)絡(luò)表示技術(shù)學(xué)習(xí)每個用戶作為關(guān)注者與被關(guān)注者的上下文特征，同時使用種子用戶對作為約束條件，去對齊未知身份的用戶對。Tong 等［21］利用網(wǎng)絡(luò)表示技術(shù)將原始網(wǎng)絡(luò)映射到一個低維的向量空間中，使用錨鏈的信息學(xué)習(xí)一個穩(wěn)定的跨網(wǎng)絡(luò)映射來進行錨鏈預(yù)測。這些研究重點關(guān)注了節(jié)點在局部結(jié)構(gòu)上的特性，忽略了節(jié)點在全局結(jié)構(gòu)中的信息。因此，一些研究從多結(jié)構(gòu)出發(fā)，探索節(jié)點的結(jié)構(gòu)特征。Grover 等［18］提出一種網(wǎng)絡(luò)節(jié)點表示方法node2vec，建立了一種兼顧深度和廣度隨機游走策略的節(jié)點嵌入方法，提高了網(wǎng)絡(luò)表示效果。Fu 等［16］考慮到節(jié)點的局部和全局信息，提出一種多粒度用戶身份對齊框架。這些方法均在異構(gòu)網(wǎng)絡(luò)對齊上取得了不錯的效果，但計算效率低?？紤]到這一問題，有研究采用矩陣分解方法推導(dǎo)節(jié)點的表征，而不必通過復(fù)雜的訓(xùn)練過程。通常，基于矩陣分解的網(wǎng)絡(luò)表示學(xué)習(xí)模型包含兩個步驟：（1）構(gòu)建一個表示節(jié)點之間關(guān)聯(lián)關(guān)系的矩陣，這個矩陣可以是表達節(jié)點間拓撲關(guān)系的鄰接矩陣，也可以是表示節(jié)點之間相似性的相似度矩陣；（2）在構(gòu)建的矩陣上進行矩陣分解，得到節(jié)點的潛在表征?；谶@一思想，Heimann 等［15］提出一種基于隱矩陣分解的網(wǎng)絡(luò)對齊方法，采用低秩矩陣近似法改進矩陣分解策略。首先建立一個結(jié)合屬性信息和全局結(jié)構(gòu)信息的節(jié)點相似度矩陣，然后通過隨機抽樣策略選取地標(biāo)節(jié)點，利用少量地標(biāo)節(jié)點與所有節(jié)點建立關(guān)聯(lián)，再利用矩陣分解推導(dǎo)出節(jié)點表示，降低了計算復(fù)雜度。但是，地標(biāo)節(jié)點的選取對低秩矩陣近似非常重要，其隨機選取地標(biāo)節(jié)點的策略使得計算結(jié)果準(zhǔn)確度無法得到保證。

2 一種無監(jiān)督的網(wǎng)絡(luò)對齊模型MU3S

問題定義 已知兩個無權(quán)無向圖G1(V1，E1)和G2(V2，E2)，其中V1和V2分別表示兩圖中的節(jié)點集，E1和E2分別表示兩圖中的邊集。V=V1∪V2，E=E1∪E2分別表示合并后的網(wǎng)絡(luò)G的節(jié)點集和邊集。異構(gòu)網(wǎng)絡(luò)對齊問題為推導(dǎo)出一個對齊矩陣simemb，其中simemb(u，v) 表示節(jié)點u∈V1和v∈V2之間的相似性。

本文提出一種基于多尺度特征和改進采樣策略的異構(gòu)網(wǎng)絡(luò)對齊方法（Aligning heterogeneous net?works by MUlti?scale features and improved sampling strategies，MU3S），通過設(shè)計不同尺度的節(jié)點結(jié)構(gòu)特征和基于節(jié)點重要性的地標(biāo)節(jié)點采樣策略來提高異構(gòu)網(wǎng)絡(luò)對齊能力。該模型主要分為網(wǎng)絡(luò)合并、多尺度特征提取、地標(biāo)節(jié)點采樣、相似矩陣構(gòu)建、網(wǎng)絡(luò)表示生成和異構(gòu)網(wǎng)絡(luò)對齊6 部分，框圖如圖1 所示。

圖1 MU3S 的概述Fig.1 Overview of MU3S

2.1 網(wǎng)絡(luò)合并

首先，將待對齊的兩個網(wǎng)絡(luò)合并為一個圖G，表示為鄰接矩陣A。然后基于此鄰接矩陣進行后續(xù)計算。 合并的方式為將分別具有鄰接矩陣A1和A2的圖組合成一個塊對角鄰接矩陣，組合方式為[A10；0A2]，其中A1和A2分別表示G1和G2的鄰接矩陣。

2.2 多尺度結(jié)構(gòu)特征提取

本文從節(jié)點的局部結(jié)構(gòu)和全局結(jié)構(gòu)兩種尺度出發(fā)，提出3 種結(jié)構(gòu)度量指標(biāo)作為節(jié)點的結(jié)構(gòu)特征。

（1）聚類系數(shù)

網(wǎng)絡(luò)中的相似節(jié)點往往會與周圍鄰居建立相似的親密關(guān)系，表現(xiàn)為節(jié)點與周圍鄰居的聚集程度。因此，建立了節(jié)點聚類系數(shù)C(u)作為節(jié)點的一種局部特征，即

式中：Nei(u)表示節(jié)點u的一階鄰居集合，e表示Nei(u)構(gòu)成的網(wǎng)絡(luò)中邊的數(shù)量。（2）鄰居平均度

節(jié)點的鄰居平均度表達了節(jié)點周圍鄰居的分布。由于節(jié)點鄰居的度值可能差別很大，進行歸一化以消除度差異產(chǎn)生的影響，其計算公式為

（3）高階鄰居度

本文建立了高階鄰居度以提取鄰居節(jié)點在全局結(jié)構(gòu)中的特征，其計算方法為

在所構(gòu)建的3 個特征中，聚類系數(shù)和鄰居平均度是針對節(jié)點局部特征的表示，稱之為小尺度特征；高階鄰居度計量了節(jié)點的全局信息，稱之為大尺度特征。將此3 個特征進行拼接，得到所有節(jié)點的初始特征表示R(u)，R(u)=(F1(u)，F(xiàn)2(u)，C(u))。

2.3 地標(biāo)節(jié)點采樣

為了降低計算復(fù)雜度，本文對節(jié)點建立基于地標(biāo)節(jié)點的表達。地標(biāo)節(jié)點是能夠表現(xiàn)出網(wǎng)絡(luò)結(jié)構(gòu)不同特征維度的標(biāo)準(zhǔn)節(jié)點，地標(biāo)節(jié)點選擇不同，節(jié)點表征效果也不同。REGAL 模型采用隨機策略選擇地標(biāo)節(jié)點。為了更好地獲得具有重要信息表達的節(jié)點表征，本文設(shè)計了一種基于節(jié)點嵌入和重要性的地標(biāo)節(jié)點選擇策略。首先，引入node2vec 方法［18］得到圖G的節(jié)點嵌入表示；然后，基于所設(shè)計的計算節(jié)點重要性的方法選取地標(biāo)節(jié)點。節(jié)點u的重要性評估計算方法為

式中：AG為通過node2vec 模型得到的網(wǎng)絡(luò)表征矩陣，表示節(jié)點u在向量空間中的大小。對所有節(jié)點按照重要性大小進行排序，選取排名前q的節(jié)點作為地標(biāo)節(jié)點。通常，其中t為采樣系數(shù)。

2.4 相似矩陣構(gòu)建

通過基于節(jié)點重要性的采樣策略篩選出地標(biāo)節(jié)點后，利用相似函數(shù)s(u，v)計算節(jié)點間的相似性，用于比較圖內(nèi)或圖間的節(jié)點。計算方法為

式中R(u)表示節(jié)點u的初始特征。通過計算，得到一個由G1和G2中節(jié)點之間的相似性組成的相似矩陣S。

2.5 網(wǎng)絡(luò)表示生成

本文借鑒相關(guān)文獻［15］，引入一種隱式矩陣分解方法進行網(wǎng)絡(luò)表示。利用相似矩陣S，找到矩陣Y和Z，使其滿足S≈YZT，其中Y是所求的節(jié)點表征矩陣?；诘椭染仃嚱品椒?，通過一個低秩矩陣近似表示相似矩陣S。的計算式為

式中：C為G中所有節(jié)點與q個地標(biāo)節(jié)點相比較得到的相似矩陣；W為從C中提取的q×q維的包含地標(biāo)節(jié)點間相似性的子矩陣，W+是它的逆矩陣。文獻［15］已經(jīng)表明，C與W+以及CT的乘積足以逼近相似矩陣S，并可以在不對因式分解的情況下獲得節(jié)點表征矩陣Y。

根據(jù)式（6），在子矩陣W+上執(zhí)行奇異值分解，可得

式中U和Σ是對W+執(zhí)行奇異值分解得到的兩個子矩陣。

上述方法在求解節(jié)點表征矩陣Y的過程中不需要計算完全相似矩陣S，只需計算所有節(jié)點與q個地標(biāo)節(jié)點之間的相似性，形成相似矩陣C，然后對子矩陣W+進行奇異值分解即可。這種結(jié)合低秩矩陣近似的矩陣分解方法降低了計算復(fù)雜度，最終可獲得網(wǎng)絡(luò)節(jié)點表征矩陣的近似矩陣。

2.6 網(wǎng)絡(luò)對齊

根據(jù)G1和G2的維度大小，將網(wǎng)絡(luò)表征近似矩陣劃分為，得到G1和G2各自對應(yīng)的節(jié)點表征矩陣。然后，使用歐幾里得距離計算節(jié)點表征之間的相似性構(gòu)建對齊矩陣，匹配兩個網(wǎng)絡(luò)中的節(jié)點。計算方法為和

通過計算，得到相似度值。對于每個節(jié)點，選擇相似度最高的節(jié)點作為其對齊節(jié)點。

3 實驗設(shè)計與結(jié)果分析

3.1 數(shù)據(jù)集和準(zhǔn)備工作

本文選取了社交網(wǎng)絡(luò)、生物醫(yī)學(xué)和論文庫3 種不同領(lǐng)域的數(shù)據(jù)集進行實驗。

（1）Arenas Email［15］：是一個社交網(wǎng)絡(luò)公共數(shù)據(jù)集，包含許多Email 信息。該數(shù)據(jù)集的規(guī)模較小，每條數(shù)據(jù)表示兩個用戶通過電子郵件進行通信所產(chǎn)生的關(guān)聯(lián)關(guān)系。

（2）PPI［15］：是描述蛋白質(zhì)之間相互作用的數(shù)據(jù)集。該數(shù)據(jù)集的規(guī)模中等，每條數(shù)據(jù)表示蛋白質(zhì)與蛋白質(zhì)之間相互作用關(guān)系。

（3）Arxiv［15］：一個收集了物理學(xué)、數(shù)學(xué)、計算機科學(xué)與生物學(xué)論文預(yù)印本的數(shù)據(jù)集。該數(shù)據(jù)集規(guī)模較大。借鑒相關(guān)文獻［15］的數(shù)據(jù)集處理方法，對每個真實網(wǎng)絡(luò)G1，利用它的鄰接矩陣A1，根據(jù)公式A2=PA1PT生成一個具有鄰接矩陣A2的新網(wǎng)絡(luò)G2，其中P為隨機生成的置換矩陣。在不斷開任何節(jié)點的情況下以0.01 的概率去掉網(wǎng)絡(luò)G2中的邊，將結(jié)構(gòu)噪音隨機添加到G2中。最后，將鄰接矩陣A1和A2以塊對角矩陣的形式合并，作為模型的輸入。 Arenas Email?2、PPI?2、Arxiv?2 都是通過 這種方式從Arenas Email?1、PPI?1、Arxiv?1構(gòu)建而來。數(shù)據(jù)集統(tǒng)計信息如表1 所示。

表1 數(shù)據(jù)集統(tǒng)計信息Table 1 Statistics of datasets

3.2 基線模型

為了驗證MU3S 模型的有效性，將其與5 種基線模型進行對比，其中包括3 種無監(jiān)督網(wǎng)絡(luò)對齊模型和兩種MU3S 模型的變體。

（1）IsoRank［22］：該模型對不同的物種關(guān)系建模構(gòu)建生物網(wǎng)絡(luò)，然后利用相似性得分將兩個網(wǎng)絡(luò)中可能具有關(guān)聯(lián)關(guān)系的節(jié)點進行匹配，最后通過提取一組得分高、相互一致的匹配來構(gòu)建網(wǎng)絡(luò)對齊的映射。

（2）FINAL［23］：該模型的思想是利用節(jié)點或邊的屬性信息來指導(dǎo)對齊過程，從最優(yōu)化角度，提出了一種基于對齊一致性原則的最優(yōu)化公式解決屬性網(wǎng)絡(luò)的節(jié)點對齊問題。

（3）REGAL［15］：該模型是一種基于網(wǎng)絡(luò)表征的圖對齊模型，它利用了表征學(xué)習(xí)的強大功能來匹配不同圖中的節(jié)點。其中，REGAL 模型設(shè)計了一個可移植的算法xNetMF 學(xué)習(xí)節(jié)點的潛在表征。

（4）MU3S?sample：它是本文模型MU3S 的一個變體，去除了不同尺度節(jié)點特征的改進，只保留了基于節(jié)點重要性的采樣策略的改進。

（5）MU3S?feature：它是本文模型MU3S 的另一個變體，去除了節(jié)點采樣策略的改進，只保留了多尺度特征的改進。

3.3 評價指標(biāo)

從兩種不同角度采用3 個評價指標(biāo)對模型進行評測。從預(yù)測的角度，采用準(zhǔn)確率和Top?k準(zhǔn)確率兩種指標(biāo)對模型進行評估；從排序的角度采用MRR 對模型進行評估。

（1）準(zhǔn)確率

準(zhǔn)確率是一個非常直觀的評價指標(biāo)，準(zhǔn)確率越高，則表示網(wǎng)絡(luò)對齊算法的性能越好。在網(wǎng)絡(luò)對齊問題中，準(zhǔn)確率被定義為預(yù)測正確的對齊節(jié)點對數(shù)除以真實對齊的節(jié)點對數(shù)，計算公式為

式中：count 表示模型預(yù)測正確的對齊節(jié)點對數(shù)，Gt表示真實對齊的節(jié)點對數(shù)。

（2）Top?k準(zhǔn)確率

準(zhǔn)確率Accuracy 屬于硬對齊，它要求節(jié)點之間的對齊是一對一的關(guān)系。為了不失一般性，本文還采用了軟對齊Top?k準(zhǔn)確率。Top?k準(zhǔn)確率表示與節(jié)點對齊的候選節(jié)點存在于前k個候選節(jié)點列表中。對于G1中的每一個節(jié)點，計算它與G2中任意節(jié)點間的相似性，并按照降序的方式依次排列，將排名前k的節(jié)點存儲在潛在匹配列表中。然后將潛在匹配列表的節(jié)點的索引依次與真實對齊節(jié)點對中的編號比較，只要有一個命中，就認為匹配成功，具體的計算過程為

需要注意的是，這種度量方法不適用于只尋找硬對齊的基線模型FINAL 和IsoRank。

（3）MRR

MRR 是推薦算法中常用的一種評估指標(biāo)，其含義是把標(biāo)準(zhǔn)答案在被評價系統(tǒng)給出的結(jié)果中的排序取倒數(shù)作為它的準(zhǔn)確度，再對所有的問題取平均。現(xiàn)將MRR 指標(biāo)應(yīng)用于異構(gòu)網(wǎng)絡(luò)對齊問題中，從排序的角度對模型的對齊質(zhì)量做出評估，計算公式為

式中ranki為第i個節(jié)點在經(jīng)過排序后的對齊列表中的索引值，取其倒數(shù)作為該節(jié)點獲得的排序分數(shù)。

3.4 超參設(shè)置

模型中涉及3 個重要超參，K，t和α，根據(jù)多次實驗后的效果和相關(guān)基線論文參數(shù)設(shè)置情況對超參進行了設(shè)定。

參數(shù)K表示鄰居的跳距，在不同數(shù)據(jù)集上進行實驗，結(jié)果如圖2 所示。可以看出，隨著K值的增加，高階鄰域?qū)?jié)點表示能力減弱。多次重復(fù)實驗顯示出，K值為2 時，模型的準(zhǔn)確率最高，因此本模型中K設(shè)定為2。

圖2 超參K 分析Fig.2 Analysis of hyper?parameter K

參數(shù)t表示地標(biāo)節(jié)點的采樣系數(shù)，它控制著地標(biāo)節(jié)點的數(shù)量。實驗結(jié)果如圖3 所示，隨著采樣節(jié)點數(shù)量的增加，模型的性能逐漸提高?？紤]到計算量的大小，t最終被設(shè)定為10。其中，地標(biāo)節(jié)點的數(shù)量為，MU3S 對地標(biāo)節(jié)點個數(shù)的設(shè)定與基模型REGAL 一致。

圖3 超參t 分析Fig.3 Analysis of hyper?parameter t

超參數(shù)α表示折扣系數(shù)，代表節(jié)點不同階鄰居的重要性，實驗結(jié)果如圖4 所示。對于Arenas Email 和PPI 兩個數(shù)據(jù)集，模型的準(zhǔn)確率在α設(shè)置為0.01 時最高，而在Arxiv 中，α設(shè)置為0.005 時準(zhǔn)確率最高。由于Arxiv 中α設(shè)置為0.005 和0.01 的結(jié)果差異不大，因此，將超參數(shù)α統(tǒng)一設(shè)定為0.01。

圖4 超參α 分析Fig.4 Analysis of hyper?parameter α

3.5 實驗結(jié)果分析

表2~4 的實驗結(jié)果表明，在3 種實驗指標(biāo)的衡量下，MU3S 與基線模型相比性能均為最優(yōu)。兩個變體模型的實驗結(jié)果進一步表明了多尺度特征抽取與基于節(jié)點重要性的采樣策略的有效性。

（1）網(wǎng)絡(luò)表示方法的有效性：從表2~4 的實驗結(jié)果可看出，4 種基于網(wǎng)絡(luò)表征的方法（RE?GAL，MU3S，MU3S?sample，MU3S?feature）的性能均優(yōu)于沒有使用網(wǎng)絡(luò)表征的FINAL 和IsoRank。這一結(jié)果表明，基于網(wǎng)絡(luò)表征的模型學(xué)習(xí)到的節(jié)點表征具有更強的表現(xiàn)力，能夠更好地完成網(wǎng)絡(luò)對齊任務(wù)。

表2 基線和MU3S 的準(zhǔn)確率Table 2 Accuracy of baseline and MU3S

（2）多尺度特征的有效性：MU3S 算法是在REGAL 算法的基礎(chǔ)上改進而來的。在保留REGAL 全局結(jié)構(gòu)特征的情況下，設(shè)計了聚類系數(shù)和鄰居平均度兩個特征，豐富了節(jié)點在局部結(jié)構(gòu)上的表達。從表2~4 的實驗結(jié)果可觀察到MU3S?feature 比REGAL 的表現(xiàn)更好，驗證了多尺度特征的構(gòu)建對異構(gòu)網(wǎng)絡(luò)對齊任務(wù)的有效性。

（3）采樣策略的有效性：MU3S?sample 首先將網(wǎng)絡(luò)輸入一個預(yù)訓(xùn)練好的node2vec 模型中獲得網(wǎng)絡(luò)表示。node2vec 采用了一種靈活的鄰域抽樣策略，經(jīng)過深度優(yōu)先和廣度優(yōu)先的隨機游走生成節(jié)點序列，使得到的節(jié)點表征蘊含了結(jié)構(gòu)信息。在此基礎(chǔ)上，設(shè)計了一種節(jié)點重要性評估計算方法，篩選出了蘊含著結(jié)構(gòu)信息的排名前q的地標(biāo)節(jié)點。從表2~4 可以看出，MU3S?sample 的性能優(yōu)于REGAL，驗證了本文提出的采樣策略的有效性。

表3 基線和MU3S 的Top?k accuracy 值Table 3 Top?k accuracy of baseline and MU3S

（4）結(jié)合多尺度特征和改進的采樣策略的有效性：表2~4 的實驗結(jié)果表明，MU3S 在3 個數(shù)據(jù)集上均取得了最佳性能。這一結(jié)果表明，多尺度特征的提取結(jié)合基于節(jié)點重要性的采樣策略能夠優(yōu)化模型，使學(xué)習(xí)到的節(jié)點表征更準(zhǔn)確，在異構(gòu)網(wǎng)絡(luò)對齊任務(wù)中表現(xiàn)更好。

表4 基線和MU3S 的MRR 值Table 4 MRR of baseline and MU3S

（5）模型的時間復(fù)雜度分析：假設(shè)兩個網(wǎng)絡(luò)均有n個節(jié)點，對MU3S 的時間復(fù)雜度展開分析。在多尺度特征提取階段，計算聚集系數(shù)的時間復(fù)雜度為O(n)，鄰居平均度的時間復(fù)雜度為O(n2)，高階鄰居度的時間復(fù)雜度為O(n3)，這一步的總時間復(fù)雜度為O(n6)。 篩選地標(biāo)節(jié)點所需的時間復(fù)雜度為O(nq)。 計算相似度矩陣的時間復(fù)雜度為O(nqb)。利用矩陣分解方法獲得節(jié)點表征的時間復(fù)雜度為O(nq2)。對齊兩個網(wǎng)絡(luò)中對應(yīng)節(jié)點的時間復(fù)雜度為O(n2)。與基模型REGAL 相比，MU3S 在特征提取階段和篩選地標(biāo)節(jié)點階段增加了時間復(fù)雜度，但獲得了更高的準(zhǔn)確率。

4 結(jié)束語

本文提出了一種無監(jiān)督的網(wǎng)絡(luò)對齊模型MU3S，首先從不同尺度提取節(jié)點的結(jié)構(gòu)特征，設(shè)計了一種基于節(jié)點重要性的采樣策略選擇地標(biāo)節(jié)點，建立了基于地標(biāo)節(jié)點的相似關(guān)系矩陣，利用低秩矩陣近似方法進行矩陣分解，得到節(jié)點表示，最后通過計算節(jié)點表示之間的相似性對齊網(wǎng)絡(luò)。在3 個不同領(lǐng)域的數(shù)據(jù)集上進行實驗，實驗結(jié)果表明，MU3S 模型在網(wǎng)絡(luò)對齊任務(wù)中具有比基線方法更優(yōu)的性能。

異構(gòu)網(wǎng)絡(luò)對齊是大數(shù)據(jù)研究領(lǐng)域中的一個重要問題，實際場景中，數(shù)據(jù)噪音、數(shù)據(jù)規(guī)模大等均使得該問題極為復(fù)雜，下一步將在網(wǎng)絡(luò)表示模型上和計算效率方面進行更為深入的研究。