融合鏈接預測相似度矩陣的屬性網絡嵌入算法

摘要：在屬性網絡中，與節點相關聯的屬性信息有助于提升網絡嵌入各種任務的性能，但網絡是一種圖狀結構，節點不僅包含屬性信息還隱含著豐富的結構信息。為了充分融合結構信息，首先通過定義節點的影響力特性、空間關系特征；然后根據鏈接預測領域基于相似度的定義構建相似度矩陣，將節點二元組中的關聯向量映射到相似度矩陣這一關系空間中，從而保留與節點相關的結構向量信息；再基于圖的拉普拉斯矩陣融合屬性信息和標簽特征，將上述三類信息集成到一個最優化框架中；最后，通過二階導數求局部最大值計算投影矩陣獲取節點的特征表示進行網絡嵌入。實驗結果表明，提出的算法能夠充分利用節點二元組的鄰接結構信息，相比于其他基準網絡嵌入算法，本模型在節點分類任務上取得了更好的結果。

關鍵詞：網絡嵌入；屬性網絡；表示學習；相似度；節點分類

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695（2022）04-021-1080-06

doi：10.19734/j.issn.1001-3695.2021.07.0377

Preserving link prediction similarity matrix for attribute network embedding

Wu Jiehua1，Gao Xueqin1，Wang Tao2

（1.Dept. of Computer Science amp; Engineering，Guangdong Polytechnic of Industry amp; Commerce，Guangzhou 510510，China；2.School of Computer Science，South China Normal University，Guangzhou 510631，China）

Abstract：In attribute network，the attribute information associated with nodes is essential to improve the performance of network embedding tasks.Nevertheless，network is a graph structure，in which nodes not only contain attribute information but also embrace the rich structural information.In order to make full use of the structural information，firstly，this paper defined influential node characteristics，spatial relationships，and constructed similarity matrix based on the definition of link prediction.Then it mapped correlation similarity vector associated with nodes in the binary group to the relationship space of the adjacency matrix，so as to maintain the node vector matrix structure information feature.Based on the definition of normalized graph Laplacian，it fused the attribute information and label feature and integrated the above three kinds of information into an optimization framework.Finally，it inferenced the projection matrix by calculating the local maximum value through a second order derivative.Experimental results indicate that the proposed algorithm can effectively utilize information of the adjacency structure with the binary group of nodes，and compared with other benchmark network embedding algorithms，it also can achieve better results on the node classification task.

Key words：network embedding；attribute network；representation learning；similarity matrix；node classification

真實世界中的實體與實體之間的關系可以表示為圖結構［1］，如社交網絡、交通網絡、生物醫學網絡、信息網絡、互聯網、神經網絡。針對圖結構，可以使用機器學習技術實現鏈接預測［2］、圖重構［3］、推薦［4］、節點分類［5］等圖挖掘任務。隨著深度學習技術的飛速發展，對信息網絡的嵌入（network embedding）［1］，也可稱為表示特征學習或表示學習（network representation learning）［6］成為近幾年數據挖掘領域新穎且熱門的研究方向。

在真實的網絡中，節點通常具有一系列的屬性，這些屬性組成與節點相關的向量。但是許多網絡的節點和鏈接的規模在千萬甚至億級以上，這使得在整個網絡上提取屬性特征并執行運算、推斷和分析十分困難，為此，相關研究提出了使用網絡嵌入技術來解決這一問題。網絡嵌入算法的中心思想是找到一種映射函數，將全局網絡結構信息（通常為全局高維向量空間矩陣）映射為低維向量矩陣［6］。網絡嵌入完成后，一方面由于特征維度的降低，學習后的特征利于計算存儲和實時運算［1］；另一方面，嵌入可以自動提取網絡特征，并將高維度結構投影到同一個低維空間中方便進行下游的圖分析任務［2］。例如廣告推薦［7］，有效樣本占總體數據的比重極小（畢竟只有很小一撥用戶會點擊推薦廣告并被模型捕獲），這使得獲取特征非常困難，通過嵌入技術便可分析已有的樣本信息，并推斷用戶可能點擊哪些廣告，從而提升推薦服務的準確度。

1相關工作

網絡嵌入問題一直是數據挖掘和機器學習領域熱門的研究方向，許多工作進行了廣泛且深入的研究。傳統意義上的網絡嵌入被看成是一個機器學習領域的特征降維過程，主要的方法包括主成分分析（principal component analysis，PCA）［8］和多維縮放（multidimensional scaling，MDS）［8］等。上述方法都可以理解成運用一個n×k（klt;lt;m）的特征矩陣來表示原始的n×m特征矩陣。

近年來，受到深度學習領域自動編碼器（auto-encoder）和詞嵌入（word-embedding）等自然語言處理思想［9］的啟發，研究者期望網絡嵌入在矩陣轉換的過程中能夠保留網絡的特征并使得轉換后的特征向量自帶節點信息，更加方便于后續的圖分析挖掘任務。由于基于深度學習的網絡嵌入技術的一個重要步驟是矩陣轉換，比較常見的算法均基于矩陣分解思想設計，并以此分為兩類：a）基于顯式矩陣分解的模型（如GraRep［10］和M-NMF［11］），該類算法首先對保持圖結構的鄰接矩陣進行預處理，然后對預處理后的矩陣進行分解得到圖的表示，但是沒有解決矩陣維度過大的問題，算法的改進和推廣受到限制［12］；b）基于隨機游走的算法是目前研究的主流，它雖然沒有顯式構建連接矩陣，但通過在網絡上隨機游走對訪問過程中的節點序列進行采樣并輸入到Skip-Gram［9］模型中，近似化為一種隱式連接矩陣分解過程。矩陣分解框架中，Perozzi是網絡嵌入這一問題的開拓者，他提出一個稱為DeepWalk［13］基于深度游走的學習算法。該算法根據word2vec［9］思想，把每一條在節點之間隨機游走訪問過的路徑表示成一個序列，通過定義一個時間窗口的上下文信息進行馬爾可夫假設，最后使用Skip-Gram訓練每一個節點的向量。在鏈接預測、網絡可視化等任務中展現出令人驚奇的效果。與DeepWalk使用深度優先搜索在圖中進行節點采樣不同，Tang等人［14］則提出采用寬度優先搜索方法LINE（large information network embedding），該算法通過定義一階相似性和二階相似性判斷圖的兩個節點之間的相似性，把一階訓練得到的嵌入表示和二階訓練得到的嵌入表示進行拼接。Grover等人［15］對DeepWalk的游走策略函數進行優化，提出了node2vec算法，設計了一個有偏差地選擇下一步隨機游走節點的函數，在眾多圖數據挖掘任務中取得了更好的效果。

然而，基于隨機游走的算法在游走過程中需要遍歷節點的鄰接區域，處理大規模網絡需要耗費巨大的內存開銷，且大多忽略了網絡中的噪聲信息，令所游走的樣本特征表示能力不夠、魯棒性差［12］。更重要的是，上述方法面向同質圖和簡單圖建模，忽略了在屬性網絡中隱藏的屬性信息，這使得上述算法的應用受到限制［16］。在屬性網絡中，網絡節點的原始屬性和網絡節點相關聯的屬性等特征會對網絡數據挖掘的各種任務性能產生影響［16］，例如在一個社交網絡中，節點表示用戶，用戶的興趣、點贊次數、回復次數、標簽關鍵字等信息是與該節點相關聯的屬性，組成了屬性向量。很明顯，如果平臺需要提升推薦服務的準確度，僅僅考慮用戶之間的信息是不夠的，還需要對屬性信息建模，因此，學習每個節點屬性信息對于理解屬性網絡嵌入至關重要［17］。

在基于顯式矩陣分解的屬性網絡嵌入問題上，Huang等人［18］提出了一個基于標簽通知的屬性網絡嵌入算法LANE（label attributed network embedding），LANE能在保持標簽信息相關性的前提下平穩地將標簽信息整合到屬性網絡嵌入中，在節點分類等任務中取得較好的效果；該作者還提出了一種加速的屬性網絡嵌入算法AANE（accelerated attributed network embedding）［19］，將復雜的建模和優化問題分解為許多子問題，使得聯合學習過程可以分布式進行，提高了運行效率；Yang等人［20］提出了BANE（binarized attributed network embedding），該算法定義了一個新的Weisfeiler-Lehman接近矩陣捕獲節點鏈接和屬性之間的數據依賴關系，通過聚合節點屬性和鏈接的信息從相鄰節點到給定目標節點的分層方式。盡管上述屬性網絡嵌入算法取得了不錯的效果，但是仍存在以下主要問題：屬性信息需要人工標注才能得到，不僅對領域知識的要求非常高，且標注過程需要清洗和處理，非常繁瑣；不同網絡的屬性是異質的，算法的擴展性不高，屬性和標簽的集成嵌入算法很難應用到其他的各個領域。更重要的是，LANE等算法嵌入的過程使用向量和計算節點的相似度，并沒有嘗試從網絡變化的角度捕捉節點之間的關系，從而使嵌入后的向量表示不能較好地反映網絡的結構信息。同時，反映網絡變化即節點之間連接關系產生的結構屬性有節點度、節點中心性、路徑、社區結構等，這些屬性如何影響嵌入性能也需要考慮。此外，研究人員還提出了GraphRNA［21］、FANE［22］、MAN ［23］等屬性網絡嵌入和表示算法，但該類算法基于游走策略，無法嵌入鏈接相似度矩陣，與本文提出方法的思路不一致，在此不再贅敘。

因此，結合鏈接相似度矩陣、屬性矩陣和標簽矩陣的特性，本文將鏈接預測的思想［24］應用到網絡嵌入問題中，提出了一個融合相似度矩陣和標簽特征的屬性網絡嵌入算法。主要思想是相鄰的節點產生鏈接的可能性越高，其嵌入后的特征表示能力越強。如圖1所示，給定一個屬性網絡的片段，算法的核心思想是將標簽矩陣Y平滑到屬性矩陣A中，建立面向節點分類問題中特征和節點類別的邏輯關聯。但由于這是一個圖結構，除了邏輯關聯還存在結構關聯。例如節點v1和v5存在鏈接關系且是同一類型，該關系又可以表示兩節點在結構上的關聯。因此，算法從局部節點、半局部/全局路徑、全局影響力節點等多維度［25］定義相似度矩陣M，從而使輸入的向量更能反映網絡的變化信息和節點之間的相似度。然后通過圖的拉普拉斯矩陣［26］分別對相似度信息、屬性信息進行向量矩陣轉換，將三類信息集成到一個最優化框架中，通過二階導數求局部最大值計算投影矩陣。

該方法的貢獻主要包括以下幾個方面：a）引入鏈接預測的思想定義和節點相關的結構向量信息，將節點二元組中的關聯向量映射到這一相似度矩陣的關系空間中；b）從局部、半局部/全局和全局三個維度定義相似度矩陣，可擴展性強；c）讓三類特征更有效地實現融合，構建網絡結構、屬性信息與標簽特征之間的關聯。在多個真實屬性網絡的對比實驗中驗證了本文提出算法的有效性，可以較好地完成節點分類任務。

2問題定義

根據通用的網絡嵌入［1］問題定義，矩陣A的轉置用AT表示；如果A是方塊矩陣，則A的跡記為Tr（A）；操作符運算‖·‖表向量的歐氏范數；I表示單位矩陣。

=（G，A）。其中G∈n×n是一個n×n的鄰接矩陣，Gij是圖的第i行第j列上的項，表示節點i到j的鏈接，如果兩點之間不存在鏈接，則定義為0；矩陣A∈n×m是所有n個節點的屬性信息集合，第i行ai表示節點i的m維屬性向量。G和A可以是二值矩陣（無權矩陣），也可以是實數矩陣（含權矩陣），每個節點都與表示所屬類別的標簽信息相關聯。Y∈n×k為一個二進制矩陣包含所有n個節點的標簽類別，其中k為標簽類別的個數。Yij=1表示節點i屬于j類，每個節點可以屬于一個或多個類別。

屬性網絡嵌入問題：給定一個與標簽信息Y相關聯的屬性網

，算法的目標是將每個節點i的高維屬性映射為一個連續的低維向量表示A∈n×m：

f：{

，Y}→H

其中：H表示嵌入網絡的低維向量空間。該映射應該盡可能與每個節點的特征向量產生關聯，這樣H在推進其他嵌入任務方面可以取得更好的表現。

3算法框架

3.1屬性網絡嵌入算法

屬性網絡是網絡中的節點或邊包含屬性信息的網絡，屬性可以是表示該節點、邊類型的特征。對屬性網絡的嵌入算法研究如何在屬性網絡嵌入時對屬性進行建模，即將標簽信息融入到結構信息中并改進節點的特征表示。要得到具備判別性的特征表示，算法需要面對兩個挑戰［18］：a）如何集成和節點關聯的高維度屬性的問題；b）解決屬性信息及其標簽特征的異質性問題。

LANE嘗試尋找兩個n×d維關聯矩陣來表示

中的節點，并保留網絡的結構信息和屬性，分別定義為S（G）和S（A），其中S（G）表示僅考慮節點的圖G的相似度矩陣，S（A）是考慮節點屬性信息A的相似度矩陣。

以鄰接矩陣G為例，首先定義該鄰接矩陣降維后保留鄰接信息的節點向量矩陣為U（G），ui和uj表示U（G）的第i行和第j行。根據矩陣相似度的定義，節點i和j如果具有相似的網絡結構，則s（G）ij較大，否則s（G）ij趨近于較小的值，可以使用向量的和積計算兩節點的關聯相似度為

s（G）ij=ui·uj‖ui‖·‖uj‖（1）

定義度矩陣D（G）是S（G）每一行在對角線上的和組成的對角線矩陣，其中每個值d（G）ii定義為d（G）ii=∑js（G）ij。

3.2網絡結構和標簽特征定義

具體來講，將式（1）應用到圖網絡時，最主要的運算集中在向量的和積作為計算兩節點的關聯相似度。然而對于圖形數據來說，衡量節點之間關聯相似度的因素并不僅僅取決于節點的鄰接信息特征，還包括了節點與節點之間鏈接產生的可能性、節點自身在圖結構中的重要性［27］（如社交網絡中的名人節點）、節點之間的空間關系（如六度空間理論、路徑關系）［28］以及節點之間連邊的特征［29］（如邊的距離、邊的流量等）。

如何更有效地計算節點之間關聯相似度來建立關系矩陣，鏈接預測技術給出了答案。在網絡分析領域，鏈接預測是其中一個重要的研究方向［25］。該技術的思想如圖2所示，即在給定網絡結構中預測未知鏈接（虛線）產生的可能性。在鏈接預測眾多研究子方向中，基于節點之間相關性的相似度算法由于原理清晰、實現簡便、運行效率高，受到廣泛的關注。相似度算法的思路是根據與潛在節點對相關聯的網絡結構信息，賦予節點對（相關性節點之間）一個相似度指標值，值越大，節點之間的相關性越高，產生鏈接的可能性也越高［30］。一種很自然的想法是能否使用鏈接預測思想建模相似度矩陣。

因此，算法采用相似度矩陣M替換鄰接矩陣G，擬引入鏈接預測問題中計算節點相似度的思想定義s（M）ij，在LANE模型中為以上幾種信息設計了簡潔而高效的相似度公式來表示圖數據的結構信息，并在計算節點對相關聯時引入其中的兩種結構編碼，由此將圖結構的其他重要信息應用到了屬性網絡的嵌入問題上。

由于節點之間的相似度定義非常多，不失一般性，本文選取了一個經典的基于鄰接節點邊數量信息的Adamic-Adar（AA）算法［31］和新近提出的基于節點自身在圖結構中的重要性的LeaderRank（LR）［32］定義相似度矩陣。該思路可以拓展到其他類型，如路徑相似度、基于隨機游走相似度和基于網絡全局結構相似度等算法中。

a）AA指標賦予共鄰節點不同的權重，即通過將每個共鄰節點度的對數值作為分母來區分不同共鄰節點的角色和貢獻，度大的共鄰節點貢獻小于度小的共鄰節點。公式如下：

s（M）ij=AA（i，j）=∑ω∈CN（i，j）1log|N（ω）|（2）

b）影響力節點識別（又稱關鍵節點識別）的核心是如何度量節點的影響力，一般來說定義為該節點與網絡中其他節點具備不同的信息傳播能力（重要性、顯著性），用網絡的屬性結構可以表示為度、局部中心性、核度、混合度和隨機游走等。LeaderRank（LR）是對經典的排序算法PageRank［33］的一種改進，它添加了一個基礎節點指向所有節點，保證每個節點的度均大于1。PageRank指標定義節點i在時間t的重要性gt（i）可表示為

gt（i）=γ+（1-γ）×∑Nm=1［amikm（1-σkm，0）+1Nσkm，0］gt-1（m）（3）

其中：γ是阻尼系數，表示一個節點隨機游走到另一個節點的概率，默認設置為γ=0.15；1-γ則表示隨機跳轉到其他節點的概率；km表示第m個節點的入度；N為網絡總節點數；ami表示節點i有一條路徑，取值為1，如不存在則取值為0；當km=0時，σkm，0=1。在PageRank的基礎上，LR依據在鄰接度低的節點訪問基礎節點的概率比鄰接度高的節點訪問基礎節點的概率要大，該指標在t時間的重要性gt（i）可表示為

gt（i）=∑N+1m=1amikmgt-1（m）（4）

因此，LR指標定義為

s（M）ij=LR（i，j）=∑ω∈CN（i，j）1gt（ω）（5）

3.3特征集成與優化

根據3.2節的定義，可以得到M的拉普拉斯矩陣（M）為

（M）=D（M）-12S（M）D（M）-12（6）

根據歸一化圖Laplacian［26］的定義和式（6）可以計算得到（A）和（Y）。以（M）為例，文獻［18，19］將節點屬性的目標函數嵌入問題表述為一個最大化問題，并通過目標函數對矩陣的幾何接近性建模，因此關于相似度矩陣M的目標函數為

max U（M）M=Tr（U（M）T（M）U（M））（7）

其中：U（M）TU（M）=I。類似地，保留屬性特征A的矩陣的（A）對應的目標函數為

A=Tr（U（A）T（A）U（A））（8）

LANE算法的核心是將所有節點的分類（標簽信息）轉為矩陣，將矩陣Y融合到屬性網絡中，形成網絡的向量表示H，然后通過矩陣H表示原始的網絡空間。在該處理步驟中，通過計算YYT來得到標簽信息的初始向量空間，并計算兩個標簽之間的相似度，進而形成標簽的相似度矩陣S（YY），但是由于標簽的類別不平衡，這就導致其相似矩陣S（YY）的排序存在問題，如果使用融合M和A作為拉普拉斯矩陣的話很有可能使其不可分解。因此需要利用學習到的屬性網絡的鄰近性對標簽信息進行平滑建模，即將具有相同標簽的節點包含到同一個簇中，并將其表示形式表述為YYT，因此（Y）對應的目標函數可以寫成

Y=Tr（U（Y）T（（YY） + U（M）U（M）T）U（Y））（9）

要將U（A）信息包含到U（M）中，利用投影矩陣的方差作為兩矩陣相關性的度量，并定義為

ρ1=Tr（U（A）TU（M）U（M）TU（A））（10）

同時，由于所有的潛在表示都受到相應的拉普拉斯的約束，文獻［34］指出將它們投射到一個新的空間H中，以獲得更多的自由度和靈活性更好的嵌入效果。方法是利用投影矩陣的方差作為其相關性的度量，將三種信息嵌入到U（M）、U（A）、U（Y）后，將這三者信息包含到H中，可得

ρ2=Tr（U（M）THHTU（M））（11）

ρ3=Tr（U（A）THHTU（A））（12）

ρ4=Tr（U（Y）THHTU（Y））（13）

結合式（10）～（13），最終的目標函數為最大化式（14）。

=（G+α1A+α1ρ1）+α2Y+ρ2+ρ3+ρ4（14）

利用梯度下降法令偏導為0可得到H，求導過程可以參考文獻［14］。

算法1融合相似度矩陣的屬性網絡嵌入算法

輸入：

，Y，d，δ。

輸出：H。

根據鏈接預測指標計算相似度矩陣M；

計算屬性矩陣S（A）和標簽矩陣S（YY）；

分別計算各矩陣的拉普拉斯矩陣（M）、（A）和（Y）；

初始化步驟t=1，U（A）=0，U（M）=0和H=0；

while（t-t-1）

更新U（M）U（A）和U（Y）；

更新H；

t=t+1；

end

3.4時間復雜度分析

算法1中，假設屬性網絡的節點數是n個，步驟a）的開銷是計算鏈接相似度矩陣，根據文獻，基于局部、半全局和全局結構的算法時間復雜度在O（n）～O（n2），部分基于隨機游走路徑的算法（如Katz［30］）最高達到O（n3）。從步驟b）～h）是將相似度矩陣融合到LANE中，其中步驟b）～d）僅僅是對矩陣的簡單處理，基本不需要開銷。步驟e）開始，算法在收斂之前需要少量的迭代，在每次迭代中需要進行四次特征分解［18］，計算n×n矩陣的前d個特征向量，許多標準迭代求解算法在最壞情況下的時間復雜度為O（dn2）。如果采用AA、CC等局部算法，計算相似度矩陣時間復雜度是O（n）；如果采用LeaderRank算法，時間復雜度可能達到O（dn2+n log n），如果采用MR等全局算法，時間復雜度可能達到O（dn2+n2）。由于dlt;lt;n，很容易得到算法1的總時間復雜度是O（n2）。

4實驗及分析

4.1實驗數據集和對比算法

實驗選取基準的屬性網絡數據集BlogCatalog［35］和Flickr［35］。BlogCatalog是一個社交博客網站，其中的節點表示用戶，鏈接表示用戶之間的關注關系。數據集使用博客描述中的關鍵詞作為與節點相關聯的屬性信息，用戶不同領域的興趣表示為每個用戶類別標簽。Flickr是一個圖片和視頻分享社交網站，節點表示用戶，鏈接表示用戶之間的互動關系。每個用戶感興趣的標記被視為其屬性信息，用戶加入的群組或者興趣小組設置為類別標簽。兩個數據集統計數據如表1所示。

實驗代碼使用MATLAB語言開發，采用16 GB的內存和Intel i7-10700 CPU的計算機運行程序。

本文選取基準的網絡嵌入算法和沒有結合網絡結構的屬性網絡嵌入算法進行對比。詳細介紹如下：a）DeepWalk，使用DFS隨機游走，并對訪問節點采樣，使用word2vec在采樣的序列學習圖中節點的向量算法；b）LINE，一個采用BFS構建一階和二階節點相似度的大規模信息網絡嵌入算法；c）LANE，結合屬性信息和標簽類別信息的網絡嵌入基準算法，默認表示維度d設置為100；d）

圖卷積神經網絡（graph convolutional network，GCN）［36］，設計了一種從圖數據中基于卷積神經網絡提取特征的方法；e）GraphSAGE［37］，一種改進GCN的直推式學習算法；f）GraphRNA，一種通過將協作游走機制AttriWalk和圖遞歸網絡GRN結合起來，可以在屬性網絡上更有效地學習節點表示的方法；g）LANE-AA和LANE-LR，本文提出的基于AA和LR相似度的LANE算法的改進版本。

4.2實驗設置和評估指標

實驗擬驗證不同嵌入對節點分類任務的有效性，該任務是根據從訓練數據中學習到的模型來預測一個新的節點屬于哪個類別。

采用機器學習領域經典的k折交叉驗證（k-fold cross validation）［38］法進行實驗，將節點的集合分為訓練集和測試集。在樣本量不充足的情況下，為了充分利用數據集對算法效果進行測試，將節點集隨機分為k組，每次將其中一個組作為測試集，剩下k-1個組作為訓練集進行訓練。k值設置為5，選用SVM分類器進行分類。micro-F1和macro-F1用于測量不均衡數據的精度，并兼顧了分類模型的精確率和召回率，實驗采用兩者的平均值F1-score評分報告節點分類性能：

F1-score=micro-F1+macro-F12（15）

4.3實驗結果和分析

表2給出了不同訓練集規模下與LANE算法對比的節點分類結果，其中訓練集比例分別設置為1/16、1/8、1/4、1/2和1，最優算法用黑體標注，次優結果用下畫線標注。可以明顯看出，所有算法的分類性能和訓練集規模呈線性關系，即隨著訓練集規模不斷擴大，各個算法分類性能逐漸提升，這樣的結果是符合機器學習領域分類任務的規律，即特征信息越多，分類準確度越高。更重要的是，LANE-AA和LANE-LR在兩個數據集中的平均預測準確度要比LANE高0.148%、0.450%和0.997%、3.269%，這一結果證明了本文提出的鏈接相似度矩陣定義是有效的，也表明要提升節點分類性能需要融合屬性矩陣，也需要定義相似度矩陣和引入標簽特征。

此外，實驗中整體表現最好的是LANE-LR模型，該指標在兩個數據集中的每一個訓練集比例下的分類準確度均比LANE要高。LANE-AA整體上優于 LANE但是比LANE-LR差，這是由于LANE-AA中的鏈接預測指標AA依據鄰接節點的度信息構建。這一方法和LANE類似，均是引入節點的鄰居結構計算相似度矩陣，因此在不少案例下尤其在Flickr數據集中，LANE的分類效果比LANE-AA好。

表3是將本文提出算法與新近提出的網絡嵌入或表示算法進行的對比實驗結果。與DeepWalk和LINE相比，明顯可以看出LANE-AA和LANE-LR的分類性準確度要高，如在兩個數據集中，不同規模下平均有12.436%、12.070%、10.531%、19.981%、27.820%、29.173%和12.564%、12.196%、11.741%、20.117%、27.964%、30.587%的增幅，這一結果歸結于DeepWalk和LINE并沒有對節點的屬性信息建模，僅僅將節點鄰接的隨機游走和一、二階信息作為特征進行嵌入。此外，可以看出本文提出的方法和GraphRNA差不多，比GCN和GraphSAGE要好。這是由于GCN和GraphSAGE并沒有利用屬性網絡中的屬性信息建模，而GraphRNA能夠在屬性網絡上實現聯合隨機游走，對屬性節點之間的相互作用進行建模，并采用遞歸神經網絡結構嵌入非線性關聯，取得與本文算法類似的分類性能。

實驗分析，圖3展示了LANE、LANE-AA和LANE-LR在BlogCatalog中對應不同特征維度的實驗結果，這里d設置為［80，90，100，110，120，130，140，150］。首先從結果可以看出，在大部分情況下，LANE-AA和LANE-LR的曲線均在LANE曲線的上方，這一結果再一次表明本文提出的方法不僅僅考慮了屬性信息，還融合了鏈接相似度矩陣，相比基準算法更能充分利用網絡的結構信息，同時在不同嵌入維度下均能很好的保留結構和屬性特征。對比LANE-AA和LANE-LR，在1/2和1/4訓練集比例有不同的效果，可能的原因是網絡的稀疏性引起AA和LR的差異性。圖4給出了BlogCatalog數據集下不同迭代次數下上述3個算法的性能。和表2、3，圖3的結果類似，LANE-AA和LANE-LR均能取得較優的分類效果。由于較多的迭代次數能獲取更加準確的求導信息，但是考慮到算法的時間復雜度，如果選擇過多的迭代次數，則需要額外的計算時間，根據實驗結果發現，過多的迭代次數對于嵌入效果并沒有顯著的提升，所以考慮到效率問題，應該在保證較高嵌入質量的前提下選擇較少的迭代次數，這里實驗選擇為5次。

為了驗證相似度矩陣的有效性和算法的可擴展性，實驗擬在節點影響力、路徑、全局矩陣等多個角度定義相似度矩陣M。其中用到的相似度定義分別基于聚類系數（cluster coefficient，CC）、節點和鏈接聚類（node and link clustering，NLC）、局部路徑（local path，LP）、疊加隨機游走（superposed random walk，SRW）、矩陣森林（matrix forest index，MFI）和矩陣補全（matrix completion，MR），各指標細節可以參考文獻［38］。各指標在兩個數據集上結合LANE的分類結果如圖5所示，其中第二個詞是相似度矩陣的定義，LANE-CC表示為LANE結合聚類系數指標。可觀察到如下結果：a）融入局部（半全局）信息構建的相似度矩陣的LANE-CC、LANE-NLC和LANE-LP算法表現普遍優于基準和LANE算法，這是由于上述方式對與節點屬性影響較大的相鄰信息以及標簽特征進行了聯合嵌入表示，顯著提高了在節點分類任務中的表現，同時，LANE-CC算法的F1-score均值在所有規模的訓練集上具有較為穩定且最高性能，以BlogCatalog數據集為例，LANE-CC平均比LANE高1.476%、0.378%、0.808%、0.454%和0.095%；b）LANE-SRW算法在1/16和1/8 數據集上優于LANE算法，在剩余三個數據集上結果均處于劣勢。與LANE相比，LANE-MFI和LANE-MR算法在所有比例下的結果均較差，分類效果不顯著；同時，LANE-SRW、LANE-MFI和LANE-MR平均預測準確度均低于LANE-CC、LANE-NLC和LANE-LP。通過以上分析得出，只要相似度矩陣定義選擇正確，所提算法的建模能力明顯優于基準的LANE算法。可以看出基于網絡局部指標定義相似度矩陣比全局相似度要優，原因在于：節點的屬性都是根據其鄰接信息構建，引入網絡的局部信息有助于在模型中進行融合；網絡是比較稀疏的，全局信息難以保持了原有數據集的局部結構。AA、LR、LANE、LANE_AA和LANE_LR等鏈接預測步驟和完整算法運行時間列于表4中。所有的算法不含讀取文件時間、劃分測試集和訓練集等初始化步驟的時間。可以看出AA的運行時間最短，LR的運行時間排第二，這與3.4節中展示的算法時間復雜度O（n）和O（n log n）一致。同時，由于LANE算法的時間復雜度是O（n2），在運行時間的量級上比AA和LR要大，而融入鏈接相似度矩陣的改進LANE算法的耗時時間和LANE相差不多，這一結果表明基于局部結構的鏈接相似度矩陣的計算不會影響LANE算法的整體效率。

5結束語

本文提出一種融合鏈接相似度矩陣的屬性網絡嵌入算法。其中，利用網絡分析領域的鏈接預測思想構建了相似度矩陣，有效地建立二元節點對之間的關聯，避免通過定義簡單的局部鄰接矩陣造成的網絡結構信息缺失問題，具有更強的通用性；同時，算法基于網絡局部、半全局和全局結構定義了多種類型的相似度矩陣，通過圖的拉普拉斯矩陣分別對相似度信息、屬性信息、標簽信息進行向量矩陣轉換，較好地適應了屬性網絡嵌入的應用場景。實驗證明，本文提出的方法在平均召回率上都有較好的效果。在后續的工作中，將本文的網絡嵌入方法擴展到多維度網絡、符號網絡或者動態網絡的應用場景中，以解決更廣泛的異構信息網絡的數據挖掘問題。

參考文獻：

［1］Cui Peng，Wang Xiao，Pei Jian，et al.A survey on network embedding［J］.IEEE Trans on Knowledge and Data Engineering，2019，31（5）：833-852.

［2］王星，王碩，陳吉，等.聯合圖注意力和卷積神經網絡的鏈接預測方法［J］.山西大學學報：自然科學版，2021，44（3）：462-470.（Wang Xing，Wang Shuo，Chen Ji， et al.Link prediction method by joint graph attention and convolutional neural networks［J］.Journal of Shanxi University：Natural Science Edition，2021，44（3）：462-470.）

［3］Peixoto T P.Network reconstruction and community detection from dynamics［J］.Physical Review Letters，2019，123（12）：128301.

［4］Zhang Xuejian，Zhao Zhongying，Li Chao，et al.An interpretable and scalable recommendation method based on network embedding［J］.IEEE Access，2019，7：9384-9394.

［5］Li Kangjie，Feng Yixiong，Gao Yicong，et al.Hierarchical graph attention networks for semi-supervised node classification［J］.Applied Intelligence，2020，50（10）：3441-3451.

［6］Zhang Daokun，Yin Jie，Zhu Xingquan，et al.Network representation learning：a survey［J］.IEEE Trans on Big Data，2020，6（1）：3-28.

［7］謝雨洋，馮栩，喻文健，等.基于隨機化矩陣分解的網絡嵌入方法［J］.計算機學報，2021，44（3）：447-461.（Xie Yuyang，Feng Xu，Yu Wenjian，et al.Learning network embedding with randomized matrix factorization［J］.Chinese Journal of Computers，2021，44（3）：447-461.）

［8］Chandrashekar G，Sahin F.A survey on feature selection methods［J］.Computers amp; Electrical Engineering，2014，40（1）：16-28.

［9］張克君，史泰猛，李偉男，等.基于統計語言模型改進的word2vec優化策略研究［J］.中文信息學報，2019，33（7）：11-19.（Zhang Kejun，Shi Taimeng，Li Weinan，et al.word2vec optimization strategy based on an improved statistical language model［J］.Journal of Chinese Information Processing，2019，33（7）：11-19.）

［10］Cao Shaosheng，Lu Wei，Xu Qiongkai.GraRep：learning graph representations with global structural information［C］//Proc of the 24th ACM International Conference on Information and Knowledge Management.New York：ACM Press，2015：891-900.

［11］Duan Zhen，Sun Xian，Zhao Shu，et al.Hierarchical community structure preserving approach for network embedding［J］.Information Sciences，2021，546（2）：1084-1096.

［12］涂存超，楊成，劉知遠，等.網絡表示學習綜述［J］.中國科學：信息科學，2017，47（8）：980-996.（Tu Cunchao，Yang Cheng，Liu Zhiyuan，et al.Network representation learning：an overview［J］.Science China：Information Sciences，2017，47（8）：980-996.）

［13］Perozzi B，Al-Rfou R，Skiena S.DeepWalk：online learning of social representations［C］//Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2014：701-710.

［14］Tang Jian，Qu Meng，Wang Mingzhe，et al.LINE：large-scale information network embedding［C］//Proc of the 24th International Confe-rence on World Wide Web.2015：1067-1077.

［15］Grover A，Leskovec J.node2vec：scalable feature learning for networks［C］//Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2016：855-864.

［16］Hou Chengbin，He Shan，Tang Ke.RoSANE：robust and scalable attributed network embedding for sparse networks［J］.Neurocompu-ting，2020，409（10）：231-243.

［17］Liao Lizi，He Xiangnan，Zhang Hanwang，et al.Attributed social network embedding［J］.IEEE Trans on Knowledge and Data Engineering，2018，30（12）：2257-2270.

［18］Huang Xiao，Li Jundong，Hu Xia.Label informed attributed network embedding［C］//Proc of the 10th ACM International Conference on Web Search and Data Mining.New York：ACM Press，2017：731-739.

［19］Huang Xiao，Li Jundong，Hu Xia.Accelerated attributed network embedding［C］//Proc of SIAM International Conference on Data Mining.Society for Industrial and Applied Mathematics.2017：633-641.

［20］Yang Hong，Pan Shirui，Zhang Peng，et al.Binarized attributed network embedding［C］//Proc of IEEE International Conference on Data Mining.Piscataway，NJ：IEEE Press，2018：1476-1481.

［21］Huang Xiao，Song Qingquan，Li Yuening，et al.Graph recurrent networks with attributed random walks［C］//Proc of the 25th ACM SIGKDD International Conference on Knowledge Discovery amp; Data Mining.New York：ACM Press，2019：732-740.

［22］Li Guanghua，Li Qiyan，Liu Jingqiao，et al.FANE：a fusion-based attributed network embedding framework［C］//Proc of Asia-Pacific Web and Web-Age Information Management Joint International Conference on Web and Big Data.Cham：Springer，2021：53-60.

［23］Liu Xingxing，Wang Kai，Wang Changdong，et al.Attention-based multi-proximity preserved attributed network embedding［C］//Proc of International Joint Conference on Neural Networks.Piscataway，NJ：IEEE Press，2021.

［24］康駐關，金福生，王國仁.基于Motif聚集系數與時序劃分的高階鏈接預測方法［J］.軟件學報，2021，32（3）：712-725.（Kang Zhuguan，Jin Fusheng，Wang Guoren.High-order link prediction method based on Motif aggregation coefficient and time series division［J］.Journal of Software，2021，32（3）：712-725.）

［25］Rossi A，Barbosa D，Firmani D，et al.Knowledge graph embedding for link prediction：a comparative analysis［J］.ACM Trans on Know-ledge Discovery from Data，2021，15（2）：article No.14.

［26］Spielman D A.Spectral graph theory and its applications［C］//Proc of the 48th Annual IEEE Symposium on Foundations of Computer Science.Piscataway，NJ：IEEE Press，2007：29-38.

［27］Ma Tinghuai，Liu Qin，Cao Jie，et al.LGIEM：global and local node influence based community detection［J］.Future Generation Compu-ter Systems，2020，105（4）：533-546.

［28］杜淑穎，丁世飛.基于六度分割理論的社交好友推薦算法研究［J］.南京理工大學學報，2019，43（4）：468-473.（Du Shuying，Ding Shifei.Research on recommendation algorithm of social friendsbased on six-degree segmentation theory［J］.Journal of Nanjing University of Science amp; Technology，2019，43（4）：468-473.）

［29］Even S，Tarjan R E.Network flow and testing graph connectivity［J］.SIAM Journal on Computing，1975，4（4）：507-518.

［30］Kumar A，Singh S S，Singh K，et al.Link prediction techniques，applications，and performance：a survey［J］.Physica A：Statistical Mechanics and Its Applications，2020，553（9）：124289.

［31］Zhou Tao，Lyu Linyuan，Zhang Yicheng.Predicting missing links via local information［J］.European Physical Journal B，2009，71（10）：623-630.

［32］Li Qian，Zhou Tao，Lyu Linyuan，et al.Identifying influential spreaders by weighted LeaderRank［J］.Physica A：Statistical Mechanics and Its Applications，2014，404（6）：47-55.

［33］Takai Y，Miyauchi A，Ikeda M，et al.Hypergraph clustering based on PageRank［C］//Proc of the 26th ACM SIGKDD International Confe-rence on Knowledge Discovery amp; Data Mining.New York：ACM Press，2020：1970-1978.

［34］Kumar A，Rai P，Daumé H.Co-regularized multi-view spectral clustering［C］//Proc of the 24th International Conference on Neural Information Processing Systems.Red Hook，NY：Curran Associates Inc.，2011：1413-1421.

［35］Li Jundong，Hu Xia，Tang Jiliang，et al.Unsupervised streaming feature selection in social media［C］//Proc of the 24th ACM International on Conference on Information and Knowledge Management.2015：1041-1050.

［36］Zhang Si，Tong Hanghang，Xu Jiejun，et al.Graph convolutional networks：a comprehensive review［J］.Computational Social Networks，2019，6（11）：article No 11.

［37］Hamilton W L，Ying R，Leskovec J.Inductive representation learning on large graphs［C］//Proc of the 31st International Conference on Neural Information Processing Systems.Red Hook，NY：Curran Associates Inc.，2017：1025-1035.

［38］Fushiki T.Estimation of prediction error by using K-fold cross-validation［J］.Statistics and Computing，2011，21（2）：137-146.

收稿日期：2021-07-18；修回日期：2021-10-02基金項目：廣東省自然科學基金資助項目（2020A1515011495）；廣州市基礎與應用基礎研究項目（202002030266）

作者簡介：伍杰華（1982-），男，教授，博士，主要研究方向為數據挖掘、社會網絡分析（kodakwu@126.com）；高學勤（1977-），男，高級工程師，碩士，主要研究方向為數據分析、特征選擇；王濤（1975-），男，副教授，博士，主要研究方向為人工智能．