一種基于多尺度特征和改進(jìn)采樣策略的異構(gòu)網(wǎng)絡(luò)對(duì)齊方法

任尊曉，王 莉

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

引 言

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

（1）聚類系數(shù)

網(wǎng)絡(luò)中的相似節(jié)點(diǎn)往往會(huì)與周?chē)従咏⑾嗨频挠H密關(guān)系，表現(xiàn)為節(jié)點(diǎn)與周?chē)従拥木奂潭?。因此，建立了?jié)點(diǎn)聚類系數(shù)C(u)作為節(jié)點(diǎn)的一種局部特征，即

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

節(jié)點(diǎn)的鄰居平均度表達(dá)了節(jié)點(diǎn)周?chē)従拥姆植肌Ｓ捎诠?jié)點(diǎn)鄰居的度值可能差別很大，進(jìn)行歸一化以消除度差異產(chǎn)生的影響，其計(jì)算公式為

（3）高階鄰居度

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

通過(guò)計(jì)算，得到相似度值。對(duì)于每個(gè)節(jié)點(diǎn)，選擇相似度最高的節(jié)點(diǎn)作為其對(duì)齊節(jié)點(diǎn)。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

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

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

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

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

3.2 基線模型

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

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

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

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

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

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

3.3 評(píng)價(jià)指標(biāo)

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

（1）準(zhǔn)確率

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

式中：count 表示模型預(yù)測(cè)正確的對(duì)齊節(jié)點(diǎn)對(duì)數(shù)，Gt表示真實(shí)對(duì)齊的節(jié)點(diǎn)對(duì)數(shù)。

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

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

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

（3）MRR

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

式中ranki為第i個(gè)節(jié)點(diǎn)在經(jīng)過(guò)排序后的對(duì)齊列表中的索引值，取其倒數(shù)作為該節(jié)點(diǎn)獲得的排序分?jǐn)?shù)。

3.4 超參設(shè)置

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

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

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

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

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

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

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

3.5 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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