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

1（中國(guó)科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心信息化發(fā)展戰(zhàn)略與評(píng)估中心 北京 100190）

2（中國(guó)科學(xué)院大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 北京 100049）

3（中國(guó)科學(xué)院計(jì)算技術(shù)研究所信息技術(shù)戰(zhàn)略研究中心 北京 100190）

（tangzhengzheng@cnic.cn）

網(wǎng)絡(luò)（圖）是日常生活和學(xué)術(shù)研究中廣泛存在的一種數(shù)據(jù)類型，如數(shù)據(jù)庫(kù)系統(tǒng)和邏輯編程（database systems and logic programming，DBLP）中的引文網(wǎng)絡(luò)[1]、微博用戶間的社交網(wǎng)絡(luò)和城市運(yùn)輸?shù)慕煌ňW(wǎng)絡(luò)等.由于網(wǎng)絡(luò)是非常重要的信息載體和表現(xiàn)形式，相關(guān)網(wǎng)絡(luò)應(yīng)用算法不斷被提出，包括節(jié)點(diǎn)分類[2-4]、鏈接預(yù)測(cè)[5-7]、社區(qū)發(fā)現(xiàn)[8-10]和分子性質(zhì)預(yù)測(cè)[11-12]等.各類算法中，網(wǎng)絡(luò)表示學(xué)習(xí)（network representation learning，NRL）近年來(lái)受到了廣泛的關(guān)注，它的目標(biāo)是學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)的分布式實(shí)值表示.具體來(lái)說(shuō)，NRL 通過(guò)解決一個(gè)優(yōu)化目標(biāo)將圖G中的每個(gè)節(jié)點(diǎn)v映射到一個(gè)潛在的d維向量空間，在低維表示中捕獲鄰接相似性和社區(qū)成員.學(xué)習(xí)到的節(jié)點(diǎn)表示還可以作為下游機(jī)器學(xué)習(xí)任務(wù)的初始特征.由于圖表示學(xué)習(xí)的簡(jiǎn)單、高效和可擴(kuò)展性，使得大規(guī)模網(wǎng)絡(luò)上的機(jī)器學(xué)習(xí)成為可能[13].

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

用于機(jī)器學(xué)習(xí)的圖數(shù)據(jù)一般包括拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性2 種特征.研究者試圖通過(guò)原始圖特征降低網(wǎng)絡(luò)內(nèi)部的噪聲邊比例，同時(shí)增加類內(nèi)邊的比例.這會(huì)提高各類圖表示算法的表示效果或者是在模型訓(xùn)練中減緩噪聲邊的影響.最近有3 類相關(guān)研究策略被提出：1）每一次訓(xùn)練之前隨機(jī)刪除拓?fù)浣Y(jié)構(gòu)中的部分邊[15-16]；2）通過(guò)節(jié)點(diǎn)特征預(yù)訓(xùn)練一個(gè)鏈接概率矩陣，基于連接概率矩陣增刪節(jié)點(diǎn)邊[17]；3）在算法訓(xùn)練過(guò)程中通過(guò)特征相似性進(jìn)行邊篩選[18].這些方法都使用了節(jié)點(diǎn)屬性信息，但無(wú)法應(yīng)用到無(wú)特征網(wǎng)絡(luò)中.

本文針對(duì)無(wú)特征網(wǎng)絡(luò)設(shè)計(jì)了一組噪聲邊優(yōu)化策略.通過(guò)優(yōu)化策略可以刪除網(wǎng)絡(luò)中的噪聲邊，增加網(wǎng)絡(luò)中的類間邊，達(dá)到網(wǎng)絡(luò)表示學(xué)習(xí)的增強(qiáng)效果.本文從相關(guān)理論證明了優(yōu)化策略的合理性，并在6 個(gè)公開圖數(shù)據(jù)集上進(jìn)行節(jié)點(diǎn)分類、鏈接預(yù)測(cè)和社區(qū)發(fā)現(xiàn)任務(wù)實(shí)驗(yàn).實(shí)驗(yàn)顯示，經(jīng)過(guò)優(yōu)化后的多個(gè)NRL 方法在3 個(gè)任務(wù)中的效果均有顯著增強(qiáng)，驗(yàn)證了本文策略的有效性.本文最后還進(jìn)行了超參敏感性分析，以驗(yàn)證優(yōu)化策略具有較好的魯棒性.

1 相關(guān)工作

圖表示學(xué)習(xí)能夠?qū)D數(shù)據(jù)轉(zhuǎn)化成低維稠密的向量化表示的方法有3 種，下面詳細(xì)介紹.

1）圖表示學(xué)習(xí).較早的圖表示學(xué)習(xí)方法基于線性或非線性降維技術(shù)，經(jīng)典的算法有LLE（locally linear embedding）[19]，LE（Laplacian eigenmap）[20]，SC（spectral clustering）[21]等.這些方法的共性是都需要對(duì)特定的關(guān)系矩陣進(jìn)行特征向量求解.例如SC 通過(guò)計(jì)算關(guān)系矩陣的前k個(gè)特征向量或奇異向量得到k維的節(jié)點(diǎn)表示，其中關(guān)系矩陣一般是網(wǎng)絡(luò)的鄰接矩陣或者拉普拉斯矩陣.這類方法對(duì)于關(guān)系矩陣十分敏感，不同關(guān)系矩陣的評(píng)測(cè)結(jié)果差異很大[22].另外關(guān)系矩陣只包括1 階鄰接關(guān)系，對(duì)于大型網(wǎng)絡(luò)來(lái)說(shuō)一般是稀疏的，通過(guò)降維分解后的表示往往不足以表達(dá)網(wǎng)絡(luò)結(jié)構(gòu)[23].

針對(duì)這一問(wèn)題，GraRep 算法[24]通過(guò)結(jié)合多階鄰接信息來(lái)增強(qiáng)網(wǎng)絡(luò)的表示效果，它將初始鄰接矩陣A進(jìn)行行歸一化處理，行元素的值表示對(duì)應(yīng)節(jié)點(diǎn)之間的1 階轉(zhuǎn)移概率.通過(guò)對(duì)不同階矩陣Ak歸一化處理表示對(duì)應(yīng)節(jié)點(diǎn)之間的k階轉(zhuǎn)移概率，最后將不同階矩陣分解得到的特征拼接組成維度更高、表達(dá)能力更強(qiáng)的節(jié)點(diǎn)表示.具體融合多階鄰接信息的矩陣M構(gòu)建形式如式（1）：

雖然GraRep 表示性能得到很大提升，但與早期基于矩陣分解的方法一樣，都具有復(fù)雜度高和計(jì)算耗時(shí)等缺陷，難以擴(kuò)展到大型網(wǎng)絡(luò)的表示學(xué)習(xí)[22].DeepWalk 算法[25]將深度學(xué)習(xí)思想引入網(wǎng)絡(luò)表示學(xué)習(xí)，它通過(guò)在網(wǎng)絡(luò)中進(jìn)行截?cái)嚯S機(jī)游走生成節(jié)點(diǎn)序列，然后使用NLP 領(lǐng)域中廣泛使用的Word2vec 思想，結(jié)合Skip-gram 的訓(xùn)練方法，得到每個(gè)節(jié)點(diǎn)的嵌入表示.Node2vec[26]進(jìn)一步擴(kuò)展了DeepWalk 算法，它通過(guò)設(shè)置2 個(gè)超參p，q分別控制游走的方向，可以做到廣度優(yōu)先搜索和深度優(yōu)先搜索的隨機(jī)游走.DeepWalk 算法也用到了高階鄰接信息，融合多階鄰接信息的矩陣M構(gòu)建形式如式（2）：

其中w表示隨機(jī)游走序列中的滑動(dòng)窗口大小，在實(shí)際模型訓(xùn)練中w表示實(shí)際可到達(dá)的最高階鄰居.

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

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

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

2 預(yù)備工作

本節(jié)首先對(duì)研究問(wèn)題做出定義及相關(guān)符號(hào)說(shuō)明.然后，展示了網(wǎng)絡(luò)噪聲如何影響本文的研究.為了能夠提出合理的降低策略，本文對(duì)節(jié)點(diǎn)局部鄰接分布進(jìn)行了假設(shè)研究.最后基于該假設(shè)，給出本文的研究動(dòng)機(jī)，并證明該動(dòng)機(jī)的合理性.

2.1 基本定義

2.2 節(jié)點(diǎn)對(duì)噪聲的敏感性

對(duì)于任意節(jié)點(diǎn)vi，我們定義了一個(gè)測(cè)量值，命名為邊純度（purity of edge，PE），記為Pe.Pe（i）值的大小反映了節(jié)點(diǎn)vi的 1 階鄰居中與節(jié)點(diǎn)vi同標(biāo)簽的比例，具體定義為：

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

從直覺上看節(jié)點(diǎn)vi對(duì) 應(yīng)的Pe（i）值越大，該節(jié)點(diǎn)經(jīng)過(guò)圖表示學(xué)習(xí)后被正確分類的概率應(yīng)該也會(huì)越大.為了驗(yàn)證這個(gè)想法，我們?cè)谕粋€(gè)公開數(shù)據(jù)集Wiki上分別使用DeepWalk，Node2vec，SNDE 這3 個(gè)圖表示學(xué)習(xí)算法進(jìn)行了10 次的分類預(yù)測(cè)，10 次訓(xùn)練設(shè)置完全相同，使用20%的數(shù)據(jù)量進(jìn)行訓(xùn)練，表示維度設(shè)置為128，其他參數(shù)都使用算法默認(rèn)值，然后統(tǒng)計(jì)余下全部節(jié)點(diǎn)在10 次分類任務(wù)中被正確預(yù)測(cè)的次數(shù).

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

2.3 局部鄰接的分布特性

很多圖表示學(xué)習(xí)算法都對(duì)圖進(jìn)行了拉普拉斯正則化處理，這一處理在各種算法中都被驗(yàn)證給模型帶了積極的效果.圖拉普拉斯正則化被認(rèn)為可以約束標(biāo)簽與圖結(jié)構(gòu)的一致性[41]，而這種處理方式建立在一個(gè)重要的假設(shè)-網(wǎng)絡(luò)的局部同質(zhì)性，即連接的2 個(gè)節(jié)點(diǎn)趨向于相似和具有相同的標(biāo)簽[32].基于這一網(wǎng)絡(luò)特性我們做出假設(shè)1，并對(duì)該假設(shè)進(jìn)行了論證.

假設(shè)1.由于網(wǎng)絡(luò)的局部同質(zhì)特性，任意節(jié)點(diǎn)在其2 階鄰居中發(fā)現(xiàn)同類節(jié)點(diǎn)的概率大于其在1 階鄰居中發(fā)現(xiàn)非同類節(jié)點(diǎn)的概率.

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

由于局部同質(zhì)特性在節(jié)點(diǎn)任意連續(xù)的1 階、2 階鄰居間具有傳遞性，例如節(jié)點(diǎn)vi的連續(xù)1 階、2 階鄰居分別是vs,vf，而節(jié)點(diǎn)vs為 節(jié)點(diǎn)vf的1 階鄰居.所以對(duì)于k>1的 網(wǎng)絡(luò)，只需要考慮節(jié)點(diǎn)vi及其連續(xù)的1 階、2階鄰接節(jié)點(diǎn).基于此，我們?cè)谡鎸?shí)數(shù)據(jù)集上通過(guò)隨機(jī)游走的方式統(tǒng)計(jì)所有節(jié)點(diǎn)及其連續(xù)1 階、2 階鄰接節(jié)點(diǎn)類別數(shù)目，具體情況如表1 所示.可以觀察到，在k>1的網(wǎng)絡(luò)中，由于局部同質(zhì)特性，任意節(jié)點(diǎn)及其連續(xù)1 階、2 階鄰接3 個(gè)節(jié)點(diǎn)之間類別互不相同（2 階子圖內(nèi)k>1）的占比很少，即2 階局部子圖滿足k≤1的情況占絕大部分，因此假設(shè)1 適用于大部分情況.

Table 1 Class Proportion Statistics for Any Node vi and Its Consecutive 1,2 Order Neighbors 表1 全網(wǎng)絡(luò)任意節(jié)點(diǎn)v i及其連續(xù)1,2 階鄰居類別數(shù)占比統(tǒng)計(jì) %

2.4 本文研究動(dòng)機(jī)

由于圖結(jié)構(gòu)噪聲的存在，各種NRL 算法在訓(xùn)練過(guò)程中融合學(xué)習(xí)了噪聲信息，使得節(jié)點(diǎn)表示間的邊界模糊，這阻礙了各種下游網(wǎng)絡(luò)任務(wù)的分析（本文任務(wù)是節(jié)點(diǎn)分類）.通過(guò)拓?fù)鋬?yōu)化處理，可以增強(qiáng)節(jié)點(diǎn)最終的表示效果.在最好的情況下，優(yōu)化策略能夠添加類內(nèi)的（不存在的）鏈接，刪除噪聲邊的（存在的）鏈接，可以生成一個(gè)網(wǎng)絡(luò)Gidea，即只存在類內(nèi)邊連接的網(wǎng)絡(luò).

研究動(dòng)機(jī)：給定一個(gè)理想網(wǎng)絡(luò)Gidea，在圖表示學(xué)習(xí)中添加高階鄰接信息，對(duì)于下游節(jié)點(diǎn)分類任務(wù)的作用將微不足道.考慮一個(gè)極端的場(chǎng)景，即所有可能的類內(nèi)邊都存在和所有可能的類間邊都不存在.場(chǎng)景圖可以看作是c個(gè)全連通的組件，c是節(jié)點(diǎn)類別數(shù)，每個(gè)組件中的節(jié)點(diǎn)具有相同的標(biāo)簽.在這種情況下，各種 NRL 方法在Gidea學(xué)習(xí)到的節(jié)點(diǎn)表示可以很容易地完成分類任務(wù)，具體理論證明如下：

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

其中Aii∈[1,c]表示某一社區(qū)內(nèi)部的拓?fù)浣Y(jié)構(gòu)，c表示節(jié)點(diǎn)類別數(shù)，O表示對(duì)應(yīng)維度零矩陣.

由于在理想圖之間不存在類間邊，并且鄰接矩陣的高維構(gòu)建也只對(duì)塊矩陣操作，那么可以得到該網(wǎng)絡(luò)對(duì)應(yīng)的多階鄰接矩陣M：

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

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

不同類節(jié)點(diǎn)的特征表示之間向量積都是零，完全獨(dú)立不相關(guān)，對(duì)于分類任務(wù)顯而易見.針對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)數(shù)據(jù)中的噪聲連接，通過(guò)合理的降噪處理可以增加網(wǎng)絡(luò)類內(nèi)連接以及減少類間連接，能夠減小噪聲圖與理想圖之間的差距.

3 局部邊優(yōu)化處理

基于2.4 節(jié)的研究動(dòng)機(jī)，本文提出“2 步驟”優(yōu)化策略.首先，介紹了2 種用于計(jì)算節(jié)點(diǎn)之間鄰接相似性的計(jì)算方法.然后，給出利用相似性計(jì)算方法結(jié)合節(jié)點(diǎn)度數(shù)對(duì)網(wǎng)絡(luò)進(jìn)行局部?jī)?yōu)化的策略.最后對(duì)優(yōu)化策略進(jìn)行邏輯梳理及復(fù)雜度分析.

3.1 鄰接相似值計(jì)算

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

Table 2 Similarity Calculation Methods表2 相似計(jì)算方法

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

A?是 矯正之后的轉(zhuǎn)移權(quán)重矩陣，表示以節(jié)點(diǎn)vi為起點(diǎn)隨機(jī)游走任意一次到達(dá)節(jié)點(diǎn)vj的權(quán)重貢獻(xiàn).

DeepWalk，Node2vec 等基于序列的表示學(xué)習(xí)算法，通過(guò)對(duì)游走序列進(jìn)行節(jié)點(diǎn)對(duì)采集，構(gòu)造出一個(gè)集合，然后在集合中隨機(jī)抽取節(jié)點(diǎn)對(duì)近似節(jié)點(diǎn)之間的相似值，但沒有顯式地保存各節(jié)點(diǎn)對(duì)之間的相似值.本文的方法可以顯式計(jì)算并保存中心節(jié)點(diǎn)與多階鄰居內(nèi)全部節(jié)點(diǎn)之間的相似值.

3.2 局部?jī)?yōu)化策略

在多個(gè)圖表示學(xué)習(xí)算法中，一個(gè)重要的前提假設(shè)就是局部同質(zhì)[42]，即相同標(biāo)簽的節(jié)點(diǎn)更容易建立邊連接以及有連接邊的2 個(gè)節(jié)點(diǎn)具有類似的特征信息.然而，在現(xiàn)實(shí)網(wǎng)絡(luò)中，任意中心節(jié)點(diǎn)的局部鄰接內(nèi)，一般都存在不同類別的鄰居.我們把這樣的邊稱作噪聲邊.由于噪聲邊的存在，學(xué)習(xí)到的節(jié)點(diǎn)表示會(huì)融合噪聲節(jié)點(diǎn)信息，這會(huì)增加下游如節(jié)點(diǎn)分類任務(wù)的難度.通過(guò)本文研究動(dòng)機(jī)的理論證明可知，如果利用原始鄰接信息，能夠?qū)W(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行優(yōu)化預(yù)處理工作，理想情況如圖2 所示.圖表示學(xué)習(xí)方法在優(yōu)化之后的網(wǎng)絡(luò)結(jié)構(gòu)中學(xué)習(xí)到的節(jié)點(diǎn)表示更容易被區(qū)分開來(lái).

Fig.2 Optimal optimization effect of node local（secondorder）subgraph圖2 節(jié)點(diǎn)局部（2 階）子圖最佳優(yōu)化效果

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

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

算法1.拓?fù)鋬?yōu)化算法.

3.3 優(yōu)化框架流程圖與復(fù)雜度分析

我們對(duì)整個(gè)優(yōu)化框架的邏輯進(jìn)行了梳理，如圖3所示.具體來(lái)說(shuō)，首先基于局部同質(zhì)性進(jìn)行了局部鄰接分布特性的推理證明；然后通過(guò)分析1 階鄰接與節(jié)點(diǎn)分類之間的關(guān)系得出本文的研究動(dòng)機(jī)，并使用截?cái)嚯S機(jī)游走的方式獲取到高階鄰接的近似轉(zhuǎn)移矩陣S；最后通過(guò)計(jì)算任意節(jié)點(diǎn)與其2 階內(nèi)鄰接節(jié)點(diǎn)之間的高階轉(zhuǎn)移相似性對(duì)該節(jié)點(diǎn)的1 階鄰接進(jìn)行重構(gòu)優(yōu)化.

Fig.3 Flow chart of optimization framework圖3 優(yōu)化框架流程圖

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

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 數(shù)據(jù)集

本文使用6 個(gè)公開數(shù)據(jù)集，包括3 個(gè)航空交通網(wǎng)絡(luò)、2 個(gè)社會(huì)網(wǎng)絡(luò)和1 個(gè)引用網(wǎng)絡(luò).Brazil，Europe，USA 是航空交通網(wǎng)絡(luò)數(shù)據(jù)集，數(shù)據(jù)集中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)機(jī)場(chǎng)，邊表示機(jī)場(chǎng)之間存在商業(yè)航班[44].它們的分類標(biāo)簽是根據(jù)航班或通過(guò)機(jī)場(chǎng)的人測(cè)量的活動(dòng)水平來(lái)分配的.Wiki[45]是社交網(wǎng)絡(luò)數(shù)據(jù)集；Blogcatalog[46]是一個(gè)由博客作者提供的社會(huì)關(guān)系網(wǎng)絡(luò)數(shù)據(jù)集，標(biāo)簽表示作者提供的主題類別，所有節(jié)點(diǎn)被劃分為6 個(gè)類.Citeseer[29]是一個(gè)研究論文引文網(wǎng)絡(luò)數(shù)據(jù)集，節(jié)點(diǎn)為出版物，邊緣為引文鏈接，所有節(jié)點(diǎn)被劃分為6 個(gè)區(qū)域.每個(gè)數(shù)據(jù)集具體的節(jié)點(diǎn)數(shù)、邊數(shù)、類別和平均度數(shù)統(tǒng)計(jì)見表3.

Table 3 The Statistics of the Datasets表3 各數(shù)據(jù)集的統(tǒng)計(jì)情況

4.1.2 基線方法

為了驗(yàn)證優(yōu)化策略的性能，將采用以下9 個(gè)基線算法進(jìn)行實(shí)驗(yàn)：

1）譜聚類（spectral clustering，SC）[21].它是一種矩陣分解算法，我們?nèi)DG的標(biāo)準(zhǔn)化拉普拉斯矩陣頂部的d個(gè)特征向量作為節(jié)點(diǎn)的特征向量表示.

2）isomap[47].它是一種半監(jiān)督圖卷積網(wǎng)絡(luò)模型，它通過(guò)從鄰居中聚合信息來(lái)學(xué)習(xí).

3）圖因 式分解（graph factorization，GF）[48].它 的信息網(wǎng)絡(luò)可以用一個(gè)親和矩陣來(lái)表示，通過(guò)矩陣分解，可以用一個(gè)低維向量來(lái)表示每個(gè)頂點(diǎn).圖因式分解通過(guò)隨機(jī)梯度下降優(yōu)化，能夠處理大型網(wǎng)絡(luò).它只適用于無(wú)向網(wǎng)絡(luò).

4）局部線性嵌入（locally linear embedding，LLE）[19].它是一種半監(jiān)督圖卷積網(wǎng)絡(luò)模型，通過(guò)從鄰居中聚合信息來(lái)學(xué)習(xí).

5）DeepWalk[25].它是一種用于社交網(wǎng)絡(luò)嵌入的算法，只適用于具有二值邊緣的網(wǎng)絡(luò).對(duì)于每個(gè)頂點(diǎn)，從頂點(diǎn)開始截?cái)嚯S機(jī)漫步用于獲取上下文信息.

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

7）Node2vec[26].它的思想同DeepWalk 一樣，生成隨機(jī)游走序列，對(duì)序列采樣得到的節(jié)點(diǎn)與其上下文組合，然后用處理詞向量的方法對(duì)這樣的組合建模得到網(wǎng)絡(luò)節(jié)點(diǎn)的表示.不過(guò)在生成隨機(jī)游走過(guò)程中做了一些創(chuàng)新.

8）SDNE[5].它使用一個(gè)自動(dòng)編碼器結(jié)構(gòu)來(lái)同時(shí)優(yōu)化1 階和2 階相似度（LINE 是分別優(yōu)化的），學(xué)習(xí)得到的向量表示能夠保留局部和全局結(jié)構(gòu)，并且對(duì)稀疏網(wǎng)絡(luò)具有魯棒性.

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

本文所有的實(shí)驗(yàn)都是在一臺(tái)擁有4 個(gè)3.60 GHz Intel 內(nèi)核和20 GB RAM 的Windows 機(jī)器上進(jìn)行的.

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

對(duì)于標(biāo)簽分類任務(wù)，采用了Micro-F1 和Macro-F1 來(lái)評(píng)估算法性能.具體的，對(duì)于一個(gè)標(biāo)簽a，分別用TP(a)，F(xiàn)P(a)，F(xiàn)N(a)表示預(yù)測(cè)為a的實(shí)例中的真陽(yáng)性、假陽(yáng)性和假陰性的數(shù)目.假設(shè)C是整個(gè)標(biāo)簽集.定義為：

其中F1（a）是標(biāo)簽a的F1-measure，Macro-F1 是 給每個(gè)類同等權(quán)重的度量，Micro-F1 是給每個(gè)實(shí)例同等權(quán)重的度量.

對(duì)于鏈接預(yù)測(cè)，本文使用平均精度（average precision，AP）和平均精度均值（mean average precision，MAP）來(lái)評(píng)估性能，計(jì)算方法為：

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

本文采用F-B 算法[50]對(duì)網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，用模塊度（modularity）[51]衡量社區(qū)劃分的效果，可以理解為社區(qū)內(nèi)邊的權(quán)重減去所有與社區(qū)節(jié)點(diǎn)相連的邊的權(quán)重和，對(duì)無(wú)向圖理解為，社區(qū)內(nèi)邊的度數(shù)減去社區(qū)內(nèi)節(jié)點(diǎn)的總度數(shù).具體定義為：

4.1.4 參數(shù)設(shè)置

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

4.2 節(jié)點(diǎn)分類

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

Table 4 Micro-F1 Value of Node Classification Before（After）Optimization for All Baselines表4 各基線算法優(yōu)化前（后）節(jié)點(diǎn)分類的Micro-F1 值 %

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

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

Fig.5 Comparison of NEU and LSOS enhancement effect（Micro-F1）圖5 NEU 與LSOS 增強(qiáng)效果對(duì)比（Micro-F1）

4.3 連接預(yù)測(cè)

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

Table 6 Results of Link Prediction Before（After）Optimization for All Baselines表6 各基線算法優(yōu)化前（后）鏈接預(yù)測(cè)的結(jié)果 %

4.4 可視化與社區(qū)發(fā)現(xiàn)

在可視化任務(wù)中，選取了Europe 和USA 數(shù)據(jù)集進(jìn)行可視化，為了保持一致，全部使用DeepWalk 算法學(xué)習(xí)到的優(yōu)化前后節(jié)點(diǎn)表示進(jìn)行可視化展示.如圖6 所示，Europe 和USA 這2 個(gè)數(shù)據(jù)集的節(jié)點(diǎn)表示優(yōu)化前同類節(jié)點(diǎn)分布比較分散，優(yōu)化之后的同類節(jié)點(diǎn)分布明顯聚集.進(jìn)一步對(duì)這2 個(gè)數(shù)據(jù)集優(yōu)化前后的節(jié)點(diǎn)表示進(jìn)行社區(qū)發(fā)現(xiàn)任務(wù)分析，具體結(jié)果如圖7所示，分圖題的括號(hào)中的2 項(xiàng)FB，modularity 分別為2 種社區(qū)劃分指標(biāo).使用FB 算法對(duì)Europe 節(jié)點(diǎn)表示優(yōu)化前后分布劃分出3 個(gè)和8 個(gè)社區(qū)，而實(shí)際社區(qū)數(shù)為4 個(gè)，分析認(rèn)為，優(yōu)化之后的非同類節(jié)點(diǎn)之間連接邊減少，同類節(jié)點(diǎn)形成緊密的局部社團(tuán).相較于優(yōu)化前社區(qū)之間重疊導(dǎo)致邊際模糊，優(yōu)化后的結(jié)構(gòu)更加容易區(qū)分.使用模塊度對(duì)優(yōu)化后社區(qū)劃分進(jìn)行評(píng)估，2 個(gè)數(shù)據(jù)集模塊度都得到提升，驗(yàn)明了本文優(yōu)化策略的有效性.

Fig.6 DeepWalk visualization before and after optimization圖6 優(yōu)化前后DeepWalk 的可視化

Fig.7 The results of network community division before and after optimization圖7 優(yōu)化前后網(wǎng)絡(luò)社區(qū)劃分的結(jié)果

4.5 有效性分析

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

Fig.8 The results of using a variety of edge similarity indexes for optimization圖8 利用各種邊相似指標(biāo)進(jìn)行優(yōu)化后的結(jié)果

為了清晰地展示優(yōu)化前后的效果，我們使用karate 數(shù)據(jù)集進(jìn)行了社區(qū)分布可視化，如圖9 所示，該網(wǎng)絡(luò)共有 34 個(gè)節(jié)點(diǎn)和78 條邊，其中34 個(gè)節(jié)點(diǎn)表示某空手道俱樂(lè)部的34 名成員，34 個(gè)節(jié)點(diǎn)分為2 個(gè)社區(qū).優(yōu)化之前2 個(gè)社區(qū)之間連接較多，邊界比較模糊導(dǎo)致社區(qū)劃分效果較差，該網(wǎng)絡(luò)對(duì)應(yīng)的社區(qū)劃分模塊度等于0.35.具體的如節(jié)點(diǎn)30 號(hào)，初始的1 階鄰居包括{1，8，32，33}，其中{1，8}為非同類節(jié)點(diǎn)，通過(guò)結(jié)構(gòu)優(yōu)化重構(gòu)之后，新的鄰居節(jié)點(diǎn)換成了{(lán)15，28，32，33}，全部都是同類節(jié)點(diǎn).優(yōu)化后的模塊度等于0.43，從圖9 可以看出明顯的社區(qū)邊界.

Fig.9 Community visualization effect before and after structural optimization of karate dataset圖9 karate 數(shù)據(jù)集結(jié)構(gòu)優(yōu)化前后社區(qū)可視化效果

5 結(jié)論

本文首先提出2 種新的鄰接相似矩陣構(gòu)建方法，通過(guò)結(jié)合局部或者高階鄰接信息來(lái)近似計(jì)算2 個(gè)節(jié)點(diǎn)之間的結(jié)構(gòu)相似性，基于此提出了一種2 階子圖內(nèi)邊優(yōu)化策略.然后通過(guò)大量的實(shí)驗(yàn)驗(yàn)證了優(yōu)化策略的有效性.在6 個(gè)公開數(shù)據(jù)集上對(duì)比了多個(gè)最先進(jìn)的算法模型.實(shí)驗(yàn)結(jié)果顯示，經(jīng)過(guò)優(yōu)化之后的多個(gè)數(shù)據(jù)在節(jié)點(diǎn)分類、連接預(yù)測(cè)和社區(qū)發(fā)現(xiàn)任務(wù)中性能都得到了增強(qiáng).本文的優(yōu)化策略可以被用在不同的網(wǎng)絡(luò)分析任務(wù)中，與不同類型的數(shù)據(jù)集，既可以配合不同算法進(jìn)行訓(xùn)練，又可以作為一種網(wǎng)絡(luò)數(shù)據(jù)預(yù)處理.

作者貢獻(xiàn)聲明：唐正正提出了研究思路，完成實(shí)驗(yàn)并撰寫論文初稿；汪洋和洪學(xué)海提出指導(dǎo)意見并修改論文；班艷審查論文；姚鐵錘參與論文修改與結(jié)果分析；喬子越對(duì)模型框架和實(shí)驗(yàn)設(shè)計(jì)提出修改建議.