基于局部優化的圖表示學習增強

唐正正 汪 洋 洪學海,3 班 艷 姚鐵錘 喬子越

1（中國科學院計算機網絡信息中心信息化發展戰略與評估中心 北京 100190）

2（中國科學院大學計算機科學與技術學院 北京 100049）

3（中國科學院計算技術研究所信息技術戰略研究中心 北京 100190）

（tangzhengzheng@cnic.cn）

網絡（圖）是日常生活和學術研究中廣泛存在的一種數據類型，如數據庫系統和邏輯編程（database systems and logic programming，DBLP）中的引文網絡[1]、微博用戶間的社交網絡和城市運輸的交通網絡等.由于網絡是非常重要的信息載體和表現形式，相關網絡應用算法不斷被提出，包括節點分類[2-4]、鏈接預測[5-7]、社區發現[8-10]和分子性質預測[11-12]等.各類算法中，網絡表示學習（network representation learning，NRL）近年來受到了廣泛的關注，它的目標是學習網絡節點的分布式實值表示.具體來說，NRL 通過解決一個優化目標將圖G中的每個節點v映射到一個潛在的d維向量空間，在低維表示中捕獲鄰接相似性和社區成員.學習到的節點表示還可以作為下游機器學習任務的初始特征.由于圖表示學習的簡單、高效和可擴展性，使得大規模網絡上的機器學習成為可能[13].

網絡表示學習通常需要將節點的上下文信息（即與它相連的鄰近節點信息）嵌入到節點表示中，然后通過最小化任一節點“生成”上下文節點的條件概率來學習節點的表示，最終使得節點與其上下文節點之間的表示在低維空間上的距離接近[13].然而，近年來的一些研究表明，由于上下文噪聲（類間邊）的存在使得圖表示學習在訓練過程中會不斷地將噪聲信息融入節點最終表示，這導致不同類節點在表示空間難以區分，不利于下游網絡任務的分析[14].

用于機器學習的圖數據一般包括拓撲結構和節點屬性2 種特征.研究者試圖通過原始圖特征降低網絡內部的噪聲邊比例，同時增加類內邊的比例.這會提高各類圖表示算法的表示效果或者是在模型訓練中減緩噪聲邊的影響.最近有3 類相關研究策略被提出：1）每一次訓練之前隨機刪除拓撲結構中的部分邊[15-16]；2）通過節點特征預訓練一個鏈接概率矩陣，基于連接概率矩陣增刪節點邊[17]；3）在算法訓練過程中通過特征相似性進行邊篩選[18].這些方法都使用了節點屬性信息，但無法應用到無特征網絡中.

本文針對無特征網絡設計了一組噪聲邊優化策略.通過優化策略可以刪除網絡中的噪聲邊，增加網絡中的類間邊，達到網絡表示學習的增強效果.本文從相關理論證明了優化策略的合理性，并在6 個公開圖數據集上進行節點分類、鏈接預測和社區發現任務實驗.實驗顯示，經過優化后的多個NRL 方法在3 個任務中的效果均有顯著增強，驗證了本文策略的有效性.本文最后還進行了超參敏感性分析，以驗證優化策略具有較好的魯棒性.

1 相關工作

圖表示學習能夠將圖數據轉化成低維稠密的向量化表示的方法有3 種，下面詳細介紹.

1）圖表示學習.較早的圖表示學習方法基于線性或非線性降維技術，經典的算法有LLE（locally linear embedding）[19]，LE（Laplacian eigenmap）[20]，SC（spectral clustering）[21]等.這些方法的共性是都需要對特定的關系矩陣進行特征向量求解.例如SC 通過計算關系矩陣的前k個特征向量或奇異向量得到k維的節點表示，其中關系矩陣一般是網絡的鄰接矩陣或者拉普拉斯矩陣.這類方法對于關系矩陣十分敏感，不同關系矩陣的評測結果差異很大[22].另外關系矩陣只包括1 階鄰接關系，對于大型網絡來說一般是稀疏的，通過降維分解后的表示往往不足以表達網絡結構[23].

針對這一問題，GraRep 算法[24]通過結合多階鄰接信息來增強網絡的表示效果，它將初始鄰接矩陣A進行行歸一化處理，行元素的值表示對應節點之間的1 階轉移概率.通過對不同階矩陣Ak歸一化處理表示對應節點之間的k階轉移概率，最后將不同階矩陣分解得到的特征拼接組成維度更高、表達能力更強的節點表示.具體融合多階鄰接信息的矩陣M構建形式如式（1）：

雖然GraRep 表示性能得到很大提升，但與早期基于矩陣分解的方法一樣，都具有復雜度高和計算耗時等缺陷，難以擴展到大型網絡的表示學習[22].DeepWalk 算法[25]將深度學習思想引入網絡表示學習，它通過在網絡中進行截斷隨機游走生成節點序列，然后使用NLP 領域中廣泛使用的Word2vec 思想，結合Skip-gram 的訓練方法，得到每個節點的嵌入表示.Node2vec[26]進一步擴展了DeepWalk 算法，它通過設置2 個超參p，q分別控制游走的方向，可以做到廣度優先搜索和深度優先搜索的隨機游走.DeepWalk 算法也用到了高階鄰接信息，融合多階鄰接信息的矩陣M構建形式如式（2）：

其中w表示隨機游走序列中的滑動窗口大小，在實際模型訓練中w表示實際可到達的最高階鄰居.

除了上述基于序列的圖嵌入方法外，研究者還探索將文本、標簽等元信息納入NRL 算法.TADW[27]在矩陣分解框架下考慮文本信息，MMDW[28]聯合優化最大邊際分類器和社區結構表征學習模型，學習到的表征不僅包含網絡結構，而且具有區分性.作為另一種半監督NRL 方法，GCN[29]和DDRW[30]被提出用于半監督圖表示學習.SDNE[5]采用深度神經模型進行圖表示學習.LINE[31]對頂點之間的1 階和2 階鄰接性進行建模，用于學習大規模網絡嵌入.

2）網絡降噪.由于網絡噪聲的存在，導致很多圖表示學習在訓練的過程中會出現過度平滑的現象[32].為了緩解網絡噪聲的影響，ResGCN[33]提出了一個圖的殘差學習框架，通過引入輸入層和輸出層之間的殘差連接（residual connection）大大緩解了過度平滑的問題.DropEdge[34]通過從輸入圖中隨機刪除一些邊，可以緩解過度平滑的影響.這2 種方法原則上延緩了過度平滑的出現，卻沒有添加新連接邊并從中獲益.ADAEDGE[17]使用類似去噪和預濾波的方法，在訓練迭代過程中根據預測，在具有相同（不同）標簽的節點之間添加（刪除）連接，并具有較高的置信度.同樣，BGCN[18]迭代訓練一個具有GCN 預測的同型混合隸屬度隨機塊模型，產生多個去噪圖，并由多個結果融合集成最終的表示.GAUG[35]通過預訓練一個連接概率矩陣，然后生成多個結構圖，通過多種邊連接組合共同學習網絡表示.以上降噪工作都是針對特征網絡進行研究提出的相關算法，無法適用于無特征網絡，由于無特征網絡的可用初始特征較少，通過簡單隨機的刪除邊可能會導致孤立節點的情況，優化效果往往適得其反.

3）隨機游走.隨機游走方法在網絡任務分析中是一種常用的技術手段.在節點嵌入算法中，DeepWalk[25]是近幾年最有影響力的方法.其主要思想是利用隨機游走對圖中的節點進行采樣，然后將節點之間的共現關系作為訓練樣本輸入Word2vec 中，學習節點的向量表示.Node2vec[27]在DeepWalk 的基礎上更進一步，它通過調整隨機游走的權重，使得圖嵌入結果在同質性和結構等價性之間進行權衡.SSDW[36]考慮到傳統網絡嵌入模型在隨機游走序列采樣過程中是無監督的，采用成對約束來指導隨機游走過程中的節點轉移概率.在預先獲得先驗信息的情況下，如果下一個節點與當前節點屬于同一個社區，則下一個節點的抽樣概率要增大；否則，應降低下一個節點的抽樣概率.另外，在社區發現算法中，Sharma 等人[37]提出的引入基于光譜偏置隨機游走的節點嵌入來源于對訪問節點周圍鄰域結構的感知.Zhang 等人[38]提出了一種基于有限隨機行走步數的層次團體檢測方法，利用核心節點的局部近似收斂而不是概率轉移矩陣的全局平滑收斂.Pons 等人[39]定義了頂點之間和頂點集之間的距離度量，這些度量有效捕獲了網絡中的社區結構.距離是根據隨機步行者在固定的步數中從一個頂點移動到另一個頂點的概率計算出來的；然后利用凝聚層次聚類技術對頂點進行分組.Fu 等人[40]根據一些社會原則提出了一種基于閾值隨機步行者的可擴展社區檢測方法（CD-TRandwalk），該方法使用隨機游走技術將有許多共同鄰居的頂點聚類到同一個社區.

2 預備工作

本節首先對研究問題做出定義及相關符號說明.然后，展示了網絡噪聲如何影響本文的研究.為了能夠提出合理的降低策略，本文對節點局部鄰接分布進行了假設研究.最后基于該假設，給出本文的研究動機，并證明該動機的合理性.

2.1 基本定義

2.2 節點對噪聲的敏感性

對于任意節點vi，我們定義了一個測量值，命名為邊純度（purity of edge，PE），記為Pe.Pe（i）值的大小反映了節點vi的 1 階鄰居中與節點vi同標簽的比例，具體定義為：

其中Pe（i）∈[0,1],N(i) 表示節點vi的 1 階鄰居集合.Li,Lj分別表示節點vi,vj的 類別標簽，⊕表示與或操作.

從直覺上看節點vi對 應的Pe（i）值越大，該節點經過圖表示學習后被正確分類的概率應該也會越大.為了驗證這個想法，我們在同一個公開數據集Wiki上分別使用DeepWalk，Node2vec，SNDE 這3 個圖表示學習算法進行了10 次的分類預測，10 次訓練設置完全相同，使用20%的數據量進行訓練，表示維度設置為128，其他參數都使用算法默認值，然后統計余下全部節點在10 次分類任務中被正確預測的次數.

為了更好地進行可視化對比，本文統一使用DeepWalk 算法學習的表示進行可視化展示.圖1（a）是根據節點PE 進行展示，圖1（b）～（d）分別對應3種NRL 算法的預測結果.可以清晰地觀察到，對于任意節點，Pe值越大，其在3 種算法中都會被多次甚至全部預測正確；反之，Pe值較小的節點在3 種NRL 算法中都較少，甚至沒有一次被正確預測.圖1（b）～（d）顯示的預測結果分布與圖1（a）Pe值分布保持一致.這佐證了我們的想法，通過Pe值可以直接了解節點周圍噪聲邊的比例，如果Pe值較小，表明節點周圍有更多的噪聲邊，在各種算法中，該節點的嵌入表示難以學習到有效的結構信息，分類的效果就會很差.

2.3 局部鄰接的分布特性

很多圖表示學習算法都對圖進行了拉普拉斯正則化處理，這一處理在各種算法中都被驗證給模型帶了積極的效果.圖拉普拉斯正則化被認為可以約束標簽與圖結構的一致性[41]，而這種處理方式建立在一個重要的假設-網絡的局部同質性，即連接的2 個節點趨向于相似和具有相同的標簽[32].基于這一網絡特性我們做出假設1，并對該假設進行了論證.

假設1.由于網絡的局部同質特性，任意節點在其2 階鄰居中發現同類節點的概率大于其在1 階鄰居中發現非同類節點的概率.

其中k+1為節點類別數目.令p2>q1化簡得到kα3>αβ2+(k-1)β3，如果網絡中只有2 類節點即k=1，不等式化簡為 α>β，顯然成立.證畢.

由于局部同質特性在節點任意連續的1 階、2 階鄰居間具有傳遞性，例如節點vi的連續1 階、2 階鄰居分別是vs,vf，而節點vs為 節點vf的1 階鄰居.所以對于k>1的 網絡，只需要考慮節點vi及其連續的1 階、2階鄰接節點.基于此，我們在真實數據集上通過隨機游走的方式統計所有節點及其連續1 階、2 階鄰接節點類別數目，具體情況如表1 所示.可以觀察到，在k>1的網絡中，由于局部同質特性，任意節點及其連續1 階、2 階鄰接3 個節點之間類別互不相同（2 階子圖內k>1）的占比很少，即2 階局部子圖滿足k≤1的情況占絕大部分，因此假設1 適用于大部分情況.

Table 1 Class Proportion Statistics for Any Node vi and Its Consecutive 1,2 Order Neighbors 表1 全網絡任意節點v i及其連續1,2 階鄰居類別數占比統計 %

2.4 本文研究動機

由于圖結構噪聲的存在，各種NRL 算法在訓練過程中融合學習了噪聲信息，使得節點表示間的邊界模糊，這阻礙了各種下游網絡任務的分析（本文任務是節點分類）.通過拓撲優化處理，可以增強節點最終的表示效果.在最好的情況下，優化策略能夠添加類內的（不存在的）鏈接，刪除噪聲邊的（存在的）鏈接，可以生成一個網絡Gidea，即只存在類內邊連接的網絡.

研究動機：給定一個理想網絡Gidea，在圖表示學習中添加高階鄰接信息，對于下游節點分類任務的作用將微不足道.考慮一個極端的場景，即所有可能的類內邊都存在和所有可能的類間邊都不存在.場景圖可以看作是c個全連通的組件，c是節點類別數，每個組件中的節點具有相同的標簽.在這種情況下，各種 NRL 方法在Gidea學習到的節點表示可以很容易地完成分類任務，具體理論證明如下：

證明.給定一個無向無權重網絡G=(V,E)，然后需要對此網絡的關系矩陣M進行分解，不同的NRL方法采用的矩陣類型雖然不同，但總的目標就是要找出2 個低維矩陣R∈R|V|×d,CT∈Rd×|V|，使得兩者內積接近M.這一步通常使用最小化范數 ||M-R·CT||來實現.假設G包含c個全連通分量，則有塊矩陣B：

其中Aii∈[1,c]表示某一社區內部的拓撲結構，c表示節點類別數，O表示對應維度零矩陣.

由于在理想圖之間不存在類間邊，并且鄰接矩陣的高維構建也只對塊矩陣操作，那么可以得到該網絡對應的多階鄰接矩陣M：

用特征方程結合矩陣初等行變換方法求矩陣的特征向量.首先根據關系式Ax=λx可寫出(λE-A)x=0，繼而寫出特征多項式 |λE-A|=0，具體形式為：

其中Ei是和Mi相 同維度的單位矩陣.可以直觀地看到理想圖情況下，針對多維鄰接矩陣特征向量的求解過程，每個塊矩陣是獨立不相關的，最終求解得到的多個特征向量也只與塊矩陣相關，對于降維后的節點表示F∈RN×d，形式為：

不同類節點的特征表示之間向量積都是零，完全獨立不相關，對于分類任務顯而易見.針對現實網絡數據中的噪聲連接，通過合理的降噪處理可以增加網絡類內連接以及減少類間連接，能夠減小噪聲圖與理想圖之間的差距.

3 局部邊優化處理

基于2.4 節的研究動機，本文提出“2 步驟”優化策略.首先，介紹了2 種用于計算節點之間鄰接相似性的計算方法.然后，給出利用相似性計算方法結合節點度數對網絡進行局部優化的策略.最后對優化策略進行邏輯梳理及復雜度分析.

3.1 鄰接相似值計算

1）局部鄰接相似計算.1 階鄰接相似是邊連接的成對頂點之間的局部相似，一般計算方法有鄰域重疊（neighborhood overlap，NO）、杰卡德系數（Jaccards’s coefficient，JC）、最小歸一化重疊（minimum normalized overlap，MNO）、余弦相似度（cosine similarity，CS），具體計算如表2 所示.然而，由于網絡的稀疏性，許多類內鏈接的缺失，1 階鄰接計算不足以表示節點之間的相似性.此外，NEU 算法[23]已經證明，在中心節點的局部子圖內，距離中心節點越遠的節點對于中心節點的影響越小.基于這種局部特性以及假設1，本文提出融合1 階、2 階鄰接結構信息的相似計算策略.對于任意節點vi和節點vj之間的相似性Sij計算為：

Table 2 Similarity Calculation Methods表2 相似計算方法

2）多階鄰接相似計算.通過本文的研究工作發現，融合高階鄰接結構信息的NRL 算法生成的節點表示能夠更準確表達出網絡結構的真實情況.然而，由于計算復雜度比較高，在大規模網絡中，精確計算高階鄰接Ak是低效的.為此，本文設計了另一種基于隨機游走的多階鄰接矩陣Mmulti計算策略.具體的計算策略分為2 個步驟：首先以網絡中的每一個節點vi為起點，進行w次長度為l的隨機游走，產生對應節點vi的 鄰近節點集Ne(i)，節點集大小等于w×l；然后遍歷Ne(i) 每個節點vi，并將對應轉移權重矩陣A?的行向量全部累加，進行標準化之后的行向量可以近似該節點游走到l階內任意鄰近節點的概率.具體計算為：

A?是 矯正之后的轉移權重矩陣，表示以節點vi為起點隨機游走任意一次到達節點vj的權重貢獻.

DeepWalk，Node2vec 等基于序列的表示學習算法，通過對游走序列進行節點對采集，構造出一個集合，然后在集合中隨機抽取節點對近似節點之間的相似值，但沒有顯式地保存各節點對之間的相似值.本文的方法可以顯式計算并保存中心節點與多階鄰居內全部節點之間的相似值.

3.2 局部優化策略

在多個圖表示學習算法中，一個重要的前提假設就是局部同質[42]，即相同標簽的節點更容易建立邊連接以及有連接邊的2 個節點具有類似的特征信息.然而，在現實網絡中，任意中心節點的局部鄰接內，一般都存在不同類別的鄰居.我們把這樣的邊稱作噪聲邊.由于噪聲邊的存在，學習到的節點表示會融合噪聲節點信息，這會增加下游如節點分類任務的難度.通過本文研究動機的理論證明可知，如果利用原始鄰接信息，能夠對網絡結構進行優化預處理工作，理想情況如圖2 所示.圖表示學習方法在優化之后的網絡結構中學習到的節點表示更容易被區分開來.

Fig.2 Optimal optimization effect of node local（secondorder）subgraph圖2 節點局部（2 階）子圖最佳優化效果

由于網絡數據具有天然的樹形結構[43]，所以理論上在任意節點為中心的子圖中，可以很容易地在高階鄰居中找到更多與中心節點同標簽的節點.通過計算每個節點之間的鄰接相似值來近似2 個節點之間屬于同類節點的概率，并且為了降低計算量，本文只對節點的局部子圖內鄰居（1 階、2 階鄰居）進行計算.首先計算中心節點vi與 其2 階子圖（本文特指2-ego network）中所有鄰居節點間的鄰接相似值；然后對相似值進行排序，為每個中心節點選取最大Top-K鄰接相似值對應的鄰近節點，并重新建立邊連接，其中K對應每個節點的度數.根據3.3 節和3.4 節的假設及理論證明，重構的邊連接更傾向于使用2 階鄰居中的同類節點替換1 階鄰居中的噪聲節點.通過對每一個節點的局部鄰接優化，達到網絡全局降噪的效果.

在實際的優化過程中我們發現，在節點vi的 度數Dii比較小的情況下，節點對鄰接結構過于敏感，采用局部鄰接相似相較于多階鄰接相似優化效果更好.如果節點度數較大時，局部噪聲邊的絕對值也會增加，通過隨機游走可以獲得更多高階同類鄰接信息，進行局部鄰近相似計算時可以很輕松地挑選出同類節點.因此最終的局部優化策略是：根據全局節點的平均度數，設定一個閾值 β，如果節點度數小于β，則根據局部鄰接矩陣進行優化，如果節點度大于β值，就使用多階鄰接矩陣進行邊優化，詳細過程如算法1.

算法1.拓撲優化算法.

3.3 優化框架流程圖與復雜度分析

我們對整個優化框架的邏輯進行了梳理，如圖3所示.具體來說，首先基于局部同質性進行了局部鄰接分布特性的推理證明；然后通過分析1 階鄰接與節點分類之間的關系得出本文的研究動機，并使用截斷隨機游走的方式獲取到高階鄰接的近似轉移矩陣S；最后通過計算任意節點與其2 階內鄰接節點之間的高階轉移相似性對該節點的1 階鄰接進行重構優化.

Fig.3 Flow chart of optimization framework圖3 優化框架流程圖

為了得到S，必須對于每個節點的高階鄰接進行采樣獲取矩陣M，這一步的時間復雜度為O(|V|×w×l).然后計算每個節點對之間的高階轉移相似距離，由于矩陣M是稀疏的，這一步的時間復雜度為O(|V|2).為每個節點選取最大Top-K鄰接時，只需獲取到最大K個節點即可，其時間復雜度為O(d×logw×l)，d是網絡所有節點的平均度數.因此，優化過程的總時間復雜度為O(|V|×w×l+|V|2+d×logw×l).

4 實 驗

4.1 實驗設置

4.1.1 數據集

本文使用6 個公開數據集，包括3 個航空交通網絡、2 個社會網絡和1 個引用網絡.Brazil，Europe，USA 是航空交通網絡數據集，數據集中的每個節點對應一個機場，邊表示機場之間存在商業航班[44].它們的分類標簽是根據航班或通過機場的人測量的活動水平來分配的.Wiki[45]是社交網絡數據集；Blogcatalog[46]是一個由博客作者提供的社會關系網絡數據集，標簽表示作者提供的主題類別，所有節點被劃分為6 個類.Citeseer[29]是一個研究論文引文網絡數據集，節點為出版物，邊緣為引文鏈接，所有節點被劃分為6 個區域.每個數據集具體的節點數、邊數、類別和平均度數統計見表3.

Table 3 The Statistics of the Datasets表3 各數據集的統計情況

4.1.2 基線方法

為了驗證優化策略的性能，將采用以下9 個基線算法進行實驗：

1）譜聚類（spectral clustering，SC）[21].它是一種矩陣分解算法，我們取圖G的標準化拉普拉斯矩陣頂部的d個特征向量作為節點的特征向量表示.

2）isomap[47].它是一種半監督圖卷積網絡模型，它通過從鄰居中聚合信息來學習.

3）圖因 式分解（graph factorization，GF）[48].它 的信息網絡可以用一個親和矩陣來表示，通過矩陣分解，可以用一個低維向量來表示每個頂點.圖因式分解通過隨機梯度下降優化，能夠處理大型網絡.它只適用于無向網絡.

4）局部線性嵌入（locally linear embedding，LLE）[19].它是一種半監督圖卷積網絡模型，通過從鄰居中聚合信息來學習.

5）DeepWalk[25].它是一種用于社交網絡嵌入的算法，只適用于具有二值邊緣的網絡.對于每個頂點，從頂點開始截斷隨機漫步用于獲取上下文信息.

6）LINE[31].它定義了損失函數來分別保持1 階或2 階的接近性.在優化損失函數之后，將這些表示連接起來.

7）Node2vec[26].它的思想同DeepWalk 一樣，生成隨機游走序列，對序列采樣得到的節點與其上下文組合，然后用處理詞向量的方法對這樣的組合建模得到網絡節點的表示.不過在生成隨機游走過程中做了一些創新.

8）SDNE[5].它使用一個自動編碼器結構來同時優化1 階和2 階相似度（LINE 是分別優化的），學習得到的向量表示能夠保留局部和全局結構，并且對稀疏網絡具有魯棒性.

9）Infwalk[49].它簡化了有限窗口長度T網絡PMI矩陣的已知表達式，并利用圖的偽逆推導出T→∞的矩陣表達式.該表達式加強了基于Skip-gram 的網絡嵌入方法和類光譜嵌入方法之間的聯系.

本文所有的實驗都是在一臺擁有4 個3.60 GHz Intel 內核和20 GB RAM 的Windows 機器上進行的.

4.1.3 評價指標

對于標簽分類任務，采用了Micro-F1 和Macro-F1 來評估算法性能.具體的，對于一個標簽a，分別用TP(a)，FP(a)，FN(a)表示預測為a的實例中的真陽性、假陽性和假陰性的數目.假設C是整個標簽集.定義為：

其中F1（a）是標簽a的F1-measure，Macro-F1 是 給每個類同等權重的度量，Micro-F1 是給每個實例同等權重的度量.

對于鏈接預測，本文使用平均精度（average precision，AP）和平均精度均值（mean average precision，MAP）來評估性能，計算方法為：

其中，precision@k表示返回實例相同的權重，V是節點集，index(j)為第j個頂點的排序索引，Ti(j)=1表 示節點vi與 節點vj有鏈接，Q為查詢集.

本文采用F-B 算法[50]對網絡進行社區劃分，用模塊度（modularity）[51]衡量社區劃分的效果，可以理解為社區內邊的權重減去所有與社區節點相連的邊的權重和，對無向圖理解為，社區內邊的度數減去社區內節點的總度數.具體定義為：

4.1.4 參數設置

在3 種矩陣分解算法中，搜索樣本的近鄰個數n_neighbors=5，降維后的維度n_components=30.DeepWalk，LINE，Node2vec，SDNE 算法表征維度設置為128，針對6 個數據集的分類任務訓練都使用了20%的數據，其他的參數設置是基于默認值或提出該方法的論文中指定的值.對于本文提出優化過程涉及到的3 個超參 β,w,l，我們采用網格搜索來選擇每個數據集的最佳超參，在局部邊優化中的閾值β=5，w∈{3,4,5}，l∈{5,6,…,9}.為了確保實驗結果能夠反映方法真實的性能，所有實驗都進行了10 次訓練預測，然后求得均值.

4.2 節點分類

本文分別在上述的6 種數據集進行了分類實驗，同時對比了網絡優化前后在9 種算法的分類結果，以上9 種算法包括了矩陣分解、隨機游走、深度學習三大類技術路線的圖嵌入方法，并且每一種都具有其技術路線的代表性.具體分類結果如表4 和表5所示.可以觀察到，經過優化之后的網絡數據在多個算法分類結果對應的Micro-F1，Macro-F1 值都得到了提升，尤其是在航空網絡中的Brazil 數據集中，Deep-Walk，LINE，Node2vec，SDNE 這4 種算法的Micro-F1值提升效果分別達到了23.11%，6.89%，14.93%，8.73%.在其他數據雖然也得到了提升，但是效果相對于3個航空網絡數據集的提升幅度相對較小.同樣的，以上4 種算法在Wiki 數據集的分類增強的Micro-F1 提升分別只有0.01%，1.01%，0.27%，1.58%.相較于其他2 類網絡數據，航空網絡中每個節點的標簽由機場的活動水平來分配，即此類網絡的節點標簽受其結構信息的影響更大，而社交網絡和引文網絡中的節點標簽與其節點自身的特征關系密切.通過分類結果可以看出，LSOS 優化策略更加適用于節點標簽與網絡結構密切類型的數據集.總體而言，本文提出的優化策略在3 類6 個數據上的9 個算法得到了不同程度的增強效果，驗明了本文所提LSOS 策略的有效性.

Table 4 Micro-F1 Value of Node Classification Before（After）Optimization for All Baselines表4 各基線算法優化前（后）節點分類的Micro-F1 值 %

通過改變不同的訓練比例，觀察分類結果，選取基線算法中的DeepWalk，LINE，Node2vec 這3 個典型的圖表示學習算法，在Brazil 和Europe 這2 個數據集上進行了分類Micro-F1 數值變化展示，如圖4 所示，En表示優化后的效果.對于Brazil 數據集，DeepWalk算法從開始隨著訓練比例增加對應的AP也相應提升，而到達60%之后AP反而降低了，這可能是參與訓練的節點比例過大導致算法模型訓練過擬合.3 種算法相較于優化前的結果在任意訓練比例的AP都有提升，而且具有同樣的增長規律，優化后的網絡表示效果相對于原始數據始終保持著明顯優勢.

為了驗證本文優化策略的穩定性，我們對比了與本文工作類似的優化算法NEU，該算法的本質是對其他圖嵌入算法最后的節點表示進行高階近似計算，達到表示增強的效果.而本文所提優化策略LSOS是通過結構優化達到表示增強.NEU 和LSOS 這2 種策略與具體的算法模型都沒有直接的關系.具體在Europe，USA，Wiki，Citeseer 這4 個數據集的分類任務對比了這2 種策略對于分類結果Micro-F1 值的增強效果.如圖5 所示，相較于NEU，本文所提LSOS 增強策略更加穩定，在4 個數據集中都具有積極效果，而NEU 雖然在Wiki 數據集上的整體效果好于LSOS，但在Europe 數據集反而帶來了負面效果.在Citeseer數據集中表現尤為明顯，從增強結果可以看到，NEU對于LINE 算法的增強顯著，而在DeepWalk 算法中居然得到了負效應，與此同時，LSOS 策略雖然在LINE 算法上沒有NEU 效果好，但對4 種算法都有積極影響，進一步驗證了LSOS 策略的穩定性與較好的適用性.

Fig.5 Comparison of NEU and LSOS enhancement effect（Micro-F1）圖5 NEU 與LSOS 增強效果對比（Micro-F1）

4.3 連接預測

本文對優化前后的連接進行了測試，結果如表6所示.由表6 可以看到，經過優化之后的網絡，在連接預測任務中對應的MAP和AP值，除了個別算法的數據集，總體表現都優于原始的數據集.我們可以觀察到連接預測結果降低的3 種算法都屬于矩陣分解類的圖嵌入算法，而基于隨機游走技術路線的2種算法幾乎都得到了提升.這可能是優化處理之后網絡社區成小簇團的形式導致矩陣分解類圖嵌入提取到的表征較少，而基于隨機游走類算法受此類原因影響較小.雖然進行了邊優化，但是還是存在噪聲邊，在預測指標計算中，噪聲邊也算作正類預測目標，并沒有限定為類內邊，由此產生了預測誤差.需要注意的是，連接預測任務是分別對優化前后的網絡進行連接預測，主要是想通過預測結果證明優化后的網絡結構能夠增強同類節點的鏈接性.

Table 6 Results of Link Prediction Before（After）Optimization for All Baselines表6 各基線算法優化前（后）鏈接預測的結果 %

4.4 可視化與社區發現

在可視化任務中，選取了Europe 和USA 數據集進行可視化，為了保持一致，全部使用DeepWalk 算法學習到的優化前后節點表示進行可視化展示.如圖6 所示，Europe 和USA 這2 個數據集的節點表示優化前同類節點分布比較分散，優化之后的同類節點分布明顯聚集.進一步對這2 個數據集優化前后的節點表示進行社區發現任務分析，具體結果如圖7所示，分圖題的括號中的2 項FB，modularity 分別為2 種社區劃分指標.使用FB 算法對Europe 節點表示優化前后分布劃分出3 個和8 個社區，而實際社區數為4 個，分析認為，優化之后的非同類節點之間連接邊減少，同類節點形成緊密的局部社團.相較于優化前社區之間重疊導致邊際模糊，優化后的結構更加容易區分.使用模塊度對優化后社區劃分進行評估，2 個數據集模塊度都得到提升，驗明了本文優化策略的有效性.

Fig.6 DeepWalk visualization before and after optimization圖6 優化前后DeepWalk 的可視化

Fig.7 The results of network community division before and after optimization圖7 優化前后網絡社區劃分的結果

4.5 有效性分析

本節分析多個基線方法都得到性能提升的原因.由于優化前后只對邊進行了操作，我們將關注點集中在優化前后連接邊的變化上.如圖8 所示，在Brazil，Europe，USA，Wiki 這4 個數據集上，分別基于NO，JC和本文相似計算策略優化前后的網絡邊統計情況.其中Pe≥ 5，表示該網絡中PE 值大于等于5 的節點數量占全部節點的比例；Interclass 表示該網絡中，類內邊數量占所有網絡邊總數的比例.通過圖8 可以看到，對比其他優化算法，經過本文策略優化后的4個數據集中，Pe≥ 5的節點比例和類內邊（Interclass）的比例都得到最佳提升.在Brazil 數據集的初始Pe≥ 5，節點比例等于40.75%，而通過NO，JC，LSOS 優化之后分別增至41.26%，38.23%，46.81%.初始Interclass 的比例等于69.78%，優化之后分別是71.43%，70.28%，74.72%.通過本文提出的相似計算方法相較于NO，JC這2 種傳統算法在優化之后的效果更加顯著，驗證了節點對應的高階轉移之間的相似性可以很好地反映節點之間的相似性.同樣的在其他3 類數據集中，LSOS 策略都取得了最佳效果.由于Pe≥ 5和Interclass這2 個指標都反映了數據集本身的一個社區分布情況，其對應的值越大說明網絡社區越明顯.本文認為優化策略提升了網絡自身結構，使其能夠更加適應不同的基線方法.

Fig.8 The results of using a variety of edge similarity indexes for optimization圖8 利用各種邊相似指標進行優化后的結果

為了清晰地展示優化前后的效果，我們使用karate 數據集進行了社區分布可視化，如圖9 所示，該網絡共有 34 個節點和78 條邊，其中34 個節點表示某空手道俱樂部的34 名成員，34 個節點分為2 個社區.優化之前2 個社區之間連接較多，邊界比較模糊導致社區劃分效果較差，該網絡對應的社區劃分模塊度等于0.35.具體的如節點30 號，初始的1 階鄰居包括{1，8，32，33}，其中{1，8}為非同類節點，通過結構優化重構之后，新的鄰居節點換成了{15，28，32，33}，全部都是同類節點.優化后的模塊度等于0.43，從圖9 可以看出明顯的社區邊界.

Fig.9 Community visualization effect before and after structural optimization of karate dataset圖9 karate 數據集結構優化前后社區可視化效果

5 結論

本文首先提出2 種新的鄰接相似矩陣構建方法，通過結合局部或者高階鄰接信息來近似計算2 個節點之間的結構相似性，基于此提出了一種2 階子圖內邊優化策略.然后通過大量的實驗驗證了優化策略的有效性.在6 個公開數據集上對比了多個最先進的算法模型.實驗結果顯示，經過優化之后的多個數據在節點分類、連接預測和社區發現任務中性能都得到了增強.本文的優化策略可以被用在不同的網絡分析任務中，與不同類型的數據集，既可以配合不同算法進行訓練，又可以作為一種網絡數據預處理.

作者貢獻聲明：唐正正提出了研究思路，完成實驗并撰寫論文初稿；汪洋和洪學海提出指導意見并修改論文；班艷審查論文；姚鐵錘參與論文修改與結果分析；喬子越對模型框架和實驗設計提出修改建議.