任尊曉，王 莉

（太原理工大學大數據學院，晉中 030600）

引 言

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

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

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

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

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

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

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

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

1 相關工作

根據與本文技術的相關程度，主要對基于網絡表示的異構網絡對齊方法的相關工作進行闡述。

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

2 一種無監(jiān)督的網絡對齊模型MU3S

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

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

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

2.1 網絡合并

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

2.2 多尺度結構特征提取

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

（1）聚類系數

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

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

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

（3）高階鄰居度

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

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

2.3 地標節(jié)點采樣

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

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

2.4 相似矩陣構建

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

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

2.5 網絡表示生成

本文借鑒相關文獻［15］，引入一種隱式矩陣分解方法進行網絡表示。利用相似矩陣S，找到矩陣Y和Z，使其滿足S≈YZT，其中Y是所求的節(jié)點表征矩陣。基于低秩矩陣近似方法，通過一個低秩矩陣近似表示相似矩陣S。的計算式為

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

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

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

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

2.6 網絡對齊

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

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

3 實驗設計與結果分析

3.1 數據集和準備工作

本文選取了社交網絡、生物醫(yī)學和論文庫3 種不同領域的數據集進行實驗。

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

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

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

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

3.2 基線模型

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

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

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

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

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

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

3.3 評價指標

從兩種不同角度采用3 個評價指標對模型進行評測。從預測的角度，采用準確率和Top?k準確率兩種指標對模型進行評估；從排序的角度采用MRR 對模型進行評估。

（1）準確率

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

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

（2）Top?k準確率

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

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

（3）MRR

MRR 是推薦算法中常用的一種評估指標，其含義是把標準答案在被評價系統(tǒng)給出的結果中的排序取倒數作為它的準確度，再對所有的問題取平均?，F將MRR 指標應用于異構網絡對齊問題中，從排序的角度對模型的對齊質量做出評估，計算公式為

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

3.4 超參設置

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

參數K表示鄰居的跳距，在不同數據集上進行實驗，結果如圖2 所示?？梢钥闯?，隨著K值的增加，高階鄰域對節(jié)點表示能力減弱。多次重復實驗顯示出，K值為2 時，模型的準確率最高，因此本模型中K設定為2。

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

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

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

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

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

3.5 實驗結果分析

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

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

表2 基線和MU3S 的準確率Table 2 Accuracy of baseline and MU3S

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

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

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

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

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

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

4 結束語

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

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