黃 亮 楊春明，2

（1.西南科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 四川綿陽(yáng) 621010；2.四川省大數(shù)據(jù)與智能系統(tǒng)工程技術(shù)研究中心 四川綿陽(yáng) 621010）

網(wǎng)絡(luò)表示學(xué)習(xí)（Network representation learning，NRL）又稱(chēng)圖表示學(xué)習(xí)方法，是一種將節(jié)點(diǎn)從高維、稀疏的網(wǎng)絡(luò)空間映射到稠密、低維的向量空間的方法，其基本假設(shè)是原始空間中相似的節(jié)點(diǎn)在低維嵌入空間中處于相近的位置?；诖思僭O(shè)，NRL得以用低維稠密的向量來(lái)表示該節(jié)點(diǎn)的特征信息，并用作下游機(jī)器學(xué)習(xí)任務(wù)的輸入，如節(jié)點(diǎn)分類(lèi)［1］、鏈接預(yù)測(cè)［2］、異常檢測(cè)［3］和個(gè)性化推薦［4］等，以減小下游任務(wù)的計(jì)算量。

NRL主要通過(guò)學(xué)習(xí)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)獲取嵌入向量，目前已在鏈接預(yù)測(cè)中取得很好的效果，但在節(jié)點(diǎn)分類(lèi)任務(wù)中效果不佳。如文獻(xiàn)［5］表明多種經(jīng)典N(xiāo)RL方法在PPI，COOC等網(wǎng)絡(luò)上的鏈接預(yù)測(cè)任務(wù)的精度可達(dá)90%，而在節(jié)點(diǎn)分類(lèi)任務(wù)上的最高精度值只有48%。節(jié)點(diǎn)的類(lèi)別信息除了與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有關(guān)外，還與該節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度、網(wǎng)絡(luò)所屬領(lǐng)域有較強(qiáng)的相關(guān)性。如社交網(wǎng)絡(luò)中，擁有相同興趣愛(ài)好的人們通常相互鏈接在一起。歐洲飛機(jī)航線網(wǎng)絡(luò)中，擁有相同活躍等級(jí)的機(jī)場(chǎng)卻可能在網(wǎng)絡(luò)的不同位置［6］。社交網(wǎng)絡(luò)傾向于通過(guò)節(jié)點(diǎn)局部特征信息得到相似的節(jié)點(diǎn)；航線網(wǎng)絡(luò)傾向于從節(jié)點(diǎn)的全局特征信息中獲得相似節(jié)點(diǎn)。目前的NRL方法主要采用隨機(jī)游走或遍歷的方式獲取節(jié)點(diǎn)序列，沒(méi)有考慮同一網(wǎng)絡(luò)中不同節(jié)點(diǎn)重要性的區(qū)別。

針對(duì)上述問(wèn)題，文章提出了一種考慮節(jié)點(diǎn)重要性的用于節(jié)點(diǎn)分類(lèi)的圖表示學(xué)習(xí)方法GeNI（Graph embedding based on node importance）。GeNI首先通過(guò)度、集聚系數(shù)等節(jié)點(diǎn)重要性指標(biāo)對(duì)節(jié)點(diǎn)預(yù)分類(lèi)以區(qū)分復(fù)雜網(wǎng)絡(luò)中不同結(jié)構(gòu)類(lèi)型的節(jié)點(diǎn)，然后將分類(lèi)結(jié)果作為先驗(yàn)知識(shí)，對(duì)結(jié)構(gòu)類(lèi)型不同的節(jié)點(diǎn)采用不同的帶偏游走策略獲得節(jié)點(diǎn)序列，并基于DeepWalk思想，將NRL問(wèn)題轉(zhuǎn)化為詞嵌入問(wèn)題。在多個(gè)公開(kāi)數(shù)據(jù)集上的節(jié)點(diǎn)分類(lèi)任務(wù)中對(duì)本文提出的方法進(jìn)行了驗(yàn)證。

1 網(wǎng)絡(luò)表示學(xué)習(xí)方法

網(wǎng)絡(luò)表示學(xué)習(xí)（NRL）又稱(chēng)圖表示學(xué)習(xí)方法。圖表示學(xué)習(xí)方法通常可分為基于矩陣分解、隨機(jī)游走和深度學(xué)習(xí)的方法。

基于矩陣分解的方法以網(wǎng)絡(luò)結(jié)構(gòu)信息為基礎(chǔ)構(gòu)建矩陣作為模型輸入，通過(guò)對(duì)矩陣降維，得到低維的節(jié)點(diǎn)向量表示。如LLE（Locally linear embedding）［7］通過(guò)其鄰居節(jié)點(diǎn)的線性組合來(lái)近似得到節(jié)點(diǎn)表示；LE（Laplace eigenmaps）［8］通過(guò)平滑項(xiàng)方式，使原始空間中兩個(gè)相似節(jié)點(diǎn)在低維向量空間中有相近的表示；Graph factorization［9］通過(guò)在均方誤差基礎(chǔ)上添加一個(gè)L2正則項(xiàng)重建圖的鄰接矩陣，同時(shí)將時(shí)間復(fù)雜度控制在O（｜E｜）。

基于隨機(jī)游走的方法首先通過(guò)遍歷網(wǎng)絡(luò)為節(jié)點(diǎn)構(gòu)建指定長(zhǎng)度的節(jié)點(diǎn)序列，再通過(guò)自然語(yǔ)言處理方法將節(jié)點(diǎn)序列看作一個(gè)個(gè)“句子”進(jìn)行訓(xùn)練，最終得到節(jié)點(diǎn)嵌入向量。DeepWalk從一個(gè)頂點(diǎn)出發(fā)，隨機(jī)移動(dòng)到一個(gè)鄰居節(jié)點(diǎn)，并將鄰居節(jié)點(diǎn)作為新的起始節(jié)點(diǎn)，如此循環(huán)若干步，得到一條游走路徑，作為該節(jié)點(diǎn)的“句子”，再用word2vec得到嵌入結(jié)果［10-11］。雖然DeepWalk在獲取節(jié)點(diǎn)序列過(guò)程中采用隨機(jī)方式獲取每一條節(jié)點(diǎn)，極大降低了模型復(fù)雜度，但隨機(jī)性較強(qiáng)使模型難以區(qū)分不同領(lǐng)域網(wǎng)絡(luò)之間的差異性，準(zhǔn)確做出應(yīng)對(duì)處理。為區(qū)分不同領(lǐng)域網(wǎng)絡(luò)之間的差異性，Node2vec［12］在節(jié)點(diǎn)序列采集階段引入深度優(yōu)先和廣度優(yōu)先搜索兩個(gè)概念。對(duì)于不同類(lèi)型網(wǎng)絡(luò)，Node2vec通過(guò)p，q兩個(gè)參數(shù)控制游走方向來(lái)獲取下一跳節(jié)點(diǎn)，得到指定長(zhǎng)度的節(jié)點(diǎn)序列，再通過(guò)skip-gram模型獲取節(jié)點(diǎn)對(duì)應(yīng)的嵌入向量［13］。

基于深度學(xué)習(xí)的方法采用復(fù)雜神經(jīng)網(wǎng)絡(luò)模型，具有強(qiáng)大的學(xué)習(xí)能力和廣泛的適應(yīng)性。SDNE方法［14］使用深度自動(dòng)編碼器來(lái)保持網(wǎng)絡(luò)一階和二階鄰近度，利用高度非線性函數(shù)獲得嵌入；DNGR方法［15］結(jié)合了隨機(jī)游走和深度自動(dòng)編碼器，使用隨機(jī)游走模型生成概率共現(xiàn)矩陣，將該矩陣轉(zhuǎn)化為PPMI（Positive pointwise mutual information）矩陣，輸入到自動(dòng)編碼器中得到嵌入。其中PPMI矩陣保證了自動(dòng)編碼器模型能夠獲取更高階的近似度；GCN方法［16-17］通過(guò)在圖上定義卷積算子降低了模型在大型稀疏網(wǎng)絡(luò)中的計(jì)算代價(jià)。模型迭代聚合了節(jié)點(diǎn)鄰域嵌入，使用前一次迭代中的嵌入表示該節(jié)點(diǎn)的全局鄰域。

除了利用節(jié)點(diǎn)的結(jié)構(gòu)特征信息，有學(xué)者提出使用節(jié)點(diǎn)屬性特征信息來(lái)學(xué)習(xí)圖嵌入。TADW方法［18］提出一個(gè)新的學(xué)習(xí)節(jié)點(diǎn)特征方法，通過(guò)加入節(jié)點(diǎn)文本特征信息，與結(jié)構(gòu)特征相結(jié)合，共同學(xué)習(xí)圖嵌入；MMDW方法［19］充分利用網(wǎng)絡(luò)中節(jié)點(diǎn)的標(biāo)簽信息，如維基百科網(wǎng)絡(luò)中，頂點(diǎn)可能被標(biāo)記成物理、天文、人物等，并在TADW的基礎(chǔ)上加入SVM（Support vector machines），增強(qiáng)不同類(lèi)別頂點(diǎn)向量的差異，提升網(wǎng)絡(luò)中節(jié)點(diǎn)分類(lèi)效果。

矩陣分解方法簡(jiǎn)單利用網(wǎng)絡(luò)的結(jié)構(gòu)信息，定義節(jié)點(diǎn)向量表示；深度學(xué)習(xí)方法雖然可以更準(zhǔn)確地學(xué)習(xí)節(jié)點(diǎn)的特征，但由于模型復(fù)雜度增加，導(dǎo)致時(shí)間復(fù)雜度高的缺點(diǎn)突出，這類(lèi)方法在大型網(wǎng)絡(luò)中應(yīng)用十分耗時(shí)；綜合節(jié)點(diǎn)結(jié)構(gòu)與屬性特征的方法需要為節(jié)點(diǎn)定義相應(yīng)的數(shù)據(jù)標(biāo)簽，但在實(shí)際工作中，大量數(shù)據(jù)標(biāo)簽往往具有較高的獲取條件；幾種經(jīng)典基于隨機(jī)游走的圖表示方法中，DeepWalk對(duì)于所有應(yīng)用場(chǎng)景，采用完全隨機(jī)的節(jié)點(diǎn)采集策略。實(shí)際情況中，不同網(wǎng)絡(luò)結(jié)構(gòu)特征往往不完全相同，DeepWalk難以實(shí)現(xiàn)為不同網(wǎng)絡(luò)構(gòu)建其特有的節(jié)點(diǎn)采集策略。Node2vec對(duì)其進(jìn)行了優(yōu)化，對(duì)于不同網(wǎng)絡(luò)可以定義對(duì)應(yīng)的節(jié)點(diǎn)采集策略，但在結(jié)構(gòu)復(fù)雜的大型網(wǎng)絡(luò)中，同一網(wǎng)絡(luò)的局部結(jié)構(gòu)特征也存在較大差異，Node2vec忽略了這種差異，對(duì)于網(wǎng)絡(luò)中所有節(jié)點(diǎn)，采用相同節(jié)點(diǎn)采集策略對(duì)節(jié)點(diǎn)進(jìn)行序列采集。但在節(jié)點(diǎn)分類(lèi)任務(wù)中，對(duì)于同一網(wǎng)絡(luò)下不同結(jié)構(gòu)類(lèi)型的節(jié)點(diǎn)，采用對(duì)應(yīng)的節(jié)點(diǎn)采集策略有利于更準(zhǔn)確獲取與源節(jié)點(diǎn)緊密相關(guān)的序列，從而提升節(jié)點(diǎn)分類(lèi)效果。因此，在節(jié)點(diǎn)采樣階段，需要區(qū)分網(wǎng)絡(luò)中不同結(jié)構(gòu)類(lèi)型的節(jié)點(diǎn)。

2 融合節(jié)點(diǎn)重要性的圖表示學(xué)習(xí)方法

2.1 GeNI模型定義

給定網(wǎng)絡(luò)G＝（V，E），網(wǎng)絡(luò)表示學(xué)習(xí)方法將網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)vi分別映射為一個(gè)低維的特征向量?（vi）∈Rd，其中，d?｜V｜，且要求兩個(gè)相似的節(jié)點(diǎn)映射后的向量距離相近；否則，映射后的向量距離較遠(yuǎn)。符號(hào)定義如表1所示。

表1 符號(hào)定義Table 1 Definition of symbols

令G＝（V，E）為給定網(wǎng)絡(luò)，f：V→Rd是從節(jié)點(diǎn)到其特征表示的映射函數(shù)。d是一個(gè)參數(shù)，用于指定特征表示的維數(shù)；f是大小為｜V｜×d的參數(shù)矩陣。對(duì)于每個(gè)源節(jié)點(diǎn)vi∈V，將NS（vi）∈V定義為通過(guò)鄰域采樣策略S生成的節(jié)點(diǎn)vi的網(wǎng)絡(luò)鄰域。

GeNI模型的優(yōu)化目標(biāo)是最大化鄰居節(jié)點(diǎn)出現(xiàn)的概率，如何定義鄰居節(jié)點(diǎn)非常重要，節(jié)點(diǎn)的采樣策略也直接影響鄰居節(jié)點(diǎn)的獲取。GeNI模型最大化節(jié)點(diǎn)vi鄰域NS（vi）的對(duì)數(shù)概率，起始目標(biāo)函數(shù)如式（1）所示：

為使目標(biāo)函數(shù)可解，引入條件獨(dú)立性和特征空間對(duì)稱(chēng)性?xún)蓚€(gè)標(biāo)準(zhǔn)假設(shè)。條件獨(dú)立性假設(shè)認(rèn)為各個(gè)鄰居節(jié)點(diǎn)之間相互獨(dú)立，如式（2）所示：

特征空間對(duì)稱(chēng)性認(rèn)為節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)在特征空間中的影響是相互的，故可將每個(gè)節(jié)點(diǎn)-鄰節(jié)點(diǎn)建模成一個(gè)個(gè)softmax單元，并將其特征信息以點(diǎn)乘方式實(shí)現(xiàn)參數(shù)化，如式（3）所示：

基于以上假設(shè)，優(yōu)化后最終目標(biāo)函數(shù)如式（4）所示：

其中，Zvi如式（5）所示：

對(duì)于大型網(wǎng)絡(luò)而言，Zvi計(jì)算成本較高，為降低計(jì)算成本，使用負(fù)采樣對(duì)其進(jìn)行近似。

2.2 GeNI采樣策略

給定節(jié)點(diǎn)ui，根據(jù)設(shè)定的采樣策略生成（抽樣）它的鄰節(jié)點(diǎn)集合N（ui）。在已有算法中，廣度優(yōu)先采樣（BFS：Breadth-first sampling）與深度優(yōu)先采樣（DFS：Depth-first sampling）兩種采樣方法發(fā)揮了重要作用。BFS傾向于對(duì)周?chē)?jié)點(diǎn)采樣，獲取節(jié)點(diǎn)的局部結(jié)構(gòu)信息；DFS傾向于探索網(wǎng)絡(luò)的更深處，獲得網(wǎng)絡(luò)的全局結(jié)構(gòu)信息。

Node2vec在節(jié)點(diǎn)采樣階段定義了一種基于二階隨機(jī)游走的采樣策略。在不同網(wǎng)絡(luò)中，該策略結(jié)合BFS和DFS捕捉網(wǎng)絡(luò)的局部和全局結(jié)構(gòu)信息。但同一網(wǎng)絡(luò)下節(jié)點(diǎn)類(lèi)別分布規(guī)律并不唯一。如圖1所示的網(wǎng)絡(luò)，節(jié)點(diǎn)顏色表示節(jié)點(diǎn)的類(lèi)別，兩種不同顏色的箭頭表示節(jié)點(diǎn)1、節(jié)點(diǎn)2在隨機(jī)游走階段中的最優(yōu)軌跡。從圖中可以發(fā)現(xiàn)節(jié)點(diǎn)1趨向于向周?chē)墓?jié)點(diǎn)游走，而節(jié)點(diǎn)2趨向于向網(wǎng)絡(luò)更深處游走，對(duì)于網(wǎng)絡(luò)中完全不同的節(jié)點(diǎn)分布情況，現(xiàn)有的圖表示學(xué)習(xí)方法大多難以有效解決這類(lèi)問(wèn)題。

圖1 節(jié)點(diǎn)1、節(jié)點(diǎn)2在隨機(jī)游走中的最優(yōu)軌跡Fig.1 The optimal routes of nodes 1 and 2 in random walk

在Node2vec中，當(dāng)模型想要以節(jié)點(diǎn)1的特征分布為標(biāo)準(zhǔn)設(shè)計(jì)游走策略時(shí)，節(jié)點(diǎn)2的游走路徑就可能變?yōu)槿鐖D2（b）所示；當(dāng)模型想要以節(jié)點(diǎn)2的特征分布為標(biāo)準(zhǔn)設(shè)計(jì)游走策略時(shí)，節(jié)點(diǎn)1的游走路徑就可能變?yōu)槿鐖D2（a）所示。兩種情況都會(huì)造成網(wǎng)絡(luò)結(jié)構(gòu)特征極大缺失。

圖2 節(jié)點(diǎn)1、節(jié)點(diǎn)2在隨機(jī)游走中可能的軌跡Fig.2 The possible routes of nodes 1 and 2 in random walk

由于網(wǎng)絡(luò)中節(jié)點(diǎn)的局部分布規(guī)律并不相同，導(dǎo)致單一采樣策略難以準(zhǔn)確獲取與節(jié)點(diǎn)緊密聯(lián)系的節(jié)點(diǎn)序列。為豐富節(jié)點(diǎn)采樣方式，提高模型的靈活性，GeNI在采樣前統(tǒng)計(jì)節(jié)點(diǎn)重要性信息并結(jié)合預(yù)分類(lèi)策略P對(duì)節(jié)點(diǎn)進(jìn)行預(yù)處理：對(duì)于網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)，GeNI首先統(tǒng)計(jì)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性特征，根據(jù)統(tǒng)計(jì)結(jié)果實(shí)現(xiàn)每一個(gè)節(jié)點(diǎn)的預(yù)分類(lèi)，再對(duì)不同類(lèi)別節(jié)點(diǎn)，設(shè)定不同采樣策略。以節(jié)點(diǎn)重要性指標(biāo)“度”作為節(jié)點(diǎn)預(yù)分類(lèi)標(biāo)準(zhǔn)設(shè)計(jì)了模型GeNI.De1和GeNI.De2；以“集聚系數(shù)”指標(biāo)作為節(jié)點(diǎn)預(yù)分類(lèi)標(biāo)準(zhǔn)設(shè)計(jì)了模型GeNI.Cl。3種模型的主要區(qū)別如下：（1）節(jié)點(diǎn)預(yù)處理階段時(shí)節(jié)點(diǎn)預(yù)分類(lèi)標(biāo)準(zhǔn)不同。GeNI.De1和GeNI.De2以節(jié)點(diǎn)“度”作為預(yù)分類(lèi)標(biāo)準(zhǔn)；GeNI.Cl以節(jié)點(diǎn)“集聚系數(shù)”作為預(yù)分類(lèi)標(biāo)準(zhǔn)。（2）節(jié)點(diǎn)預(yù)分類(lèi)的類(lèi)別總數(shù)不同。GeNI.De1和GeNI.Cl將網(wǎng)絡(luò)中節(jié)點(diǎn)分為兩類(lèi)，對(duì)不同類(lèi)別節(jié)點(diǎn)采用不同的采集策略。為了探究同一網(wǎng)絡(luò)中更多采樣策略對(duì)節(jié)點(diǎn)序列獲取的影響，GeNI.De2將網(wǎng)絡(luò)中節(jié)點(diǎn)分為三類(lèi)，對(duì)不同類(lèi)別節(jié)點(diǎn)采用不同的采集策略。

2.3 節(jié)點(diǎn)重要性指標(biāo)

2.3.1 度

節(jié)點(diǎn)度用來(lái)表示與該節(jié)點(diǎn)直接相鄰的鄰居數(shù)目［20］，網(wǎng)絡(luò)中任意節(jié)點(diǎn)i的度k（i）如式（6）所示：

節(jié)點(diǎn)度指標(biāo)直接反映該節(jié)點(diǎn)一階鄰域的密集程度，同時(shí)也展示了該節(jié)點(diǎn)對(duì)鄰居節(jié)點(diǎn)的直接影響力。例如在社交網(wǎng)絡(luò)中，度值更大的節(jié)點(diǎn)擁有更大的影響力，周?chē)?jié)點(diǎn)往往通過(guò)它來(lái)獲取相關(guān)信息。

2.3.2 集聚系數(shù)

節(jié)點(diǎn)度可以反應(yīng)節(jié)點(diǎn)與周?chē)?jié)點(diǎn)直接建立聯(lián)系的能力，但不能反應(yīng)該節(jié)點(diǎn)鄰居之間的關(guān)系。實(shí)際上，節(jié)點(diǎn)鄰居之間建立的聯(lián)系越密集，節(jié)點(diǎn)鄰居與該節(jié)點(diǎn)同類(lèi)別的可能性就越大［21］。集聚系數(shù)可以很好評(píng)估這種可能，它描述了網(wǎng)絡(luò)中節(jié)點(diǎn)鄰居之間互為鄰居的比例，具體表達(dá)如式（7）所示：

其中：k（i）表示節(jié)點(diǎn)的度；ei表示節(jié)點(diǎn)i與任意兩個(gè)鄰居之間形成三角形的個(gè)數(shù)，也就是節(jié)點(diǎn)鄰居相互連接的個(gè)數(shù)。通過(guò)這種方式，可以直觀反映出節(jié)點(diǎn)鄰居之間的相關(guān)程度。

2.4 隨機(jī)游走與搜索偏差

給定源節(jié)點(diǎn)vi，模擬一個(gè)長(zhǎng)度為l的隨機(jī)游走。l是源節(jié)點(diǎn)vi對(duì)應(yīng)節(jié)點(diǎn)序列的長(zhǎng)度，是模型參數(shù)之一，取值與網(wǎng)絡(luò)規(guī)模、密度有關(guān)（通常在［10，20］之間進(jìn)行選擇），恰當(dāng)?shù)膌可提升最終嵌入向量的質(zhì)量。ci表示在游走中的第i個(gè)節(jié)點(diǎn)，通過(guò)式（8）生成：

其中：τvx是未歸一化的節(jié)點(diǎn)v和x間的轉(zhuǎn)移概率；Z是歸一化常量。GeNI采用與Node2vec相近的帶偏隨機(jī)游走方法。GeNI定義了多個(gè)二階隨機(jī)游走。GeNI.De1與GeNI.Cl定義了兩種隨機(jī)游走方式，使用4個(gè)參數(shù)，p1，p2，q1，q2來(lái)指導(dǎo)隨機(jī)游走；而GeNI.De2定義了3種隨機(jī)游走方式，使用6個(gè)參數(shù)，p1，p2，p3，q1，q2，q3來(lái)指導(dǎo)隨機(jī)游走。GeNI.De1中p1，q1為一組節(jié)點(diǎn)的采樣策略參數(shù)；p2，q2為另一組節(jié)點(diǎn)的采樣策略參數(shù)，它們有著相同的定義：假設(shè)一個(gè)節(jié)點(diǎn)被分配到p1，q1所對(duì)應(yīng)的組，對(duì)該節(jié)點(diǎn)進(jìn)行采樣。節(jié)點(diǎn)穿過(guò)邊（t，v），停留在節(jié)點(diǎn)v上，下一步節(jié)點(diǎn)采集策略會(huì)計(jì)算該節(jié)點(diǎn)在v上的轉(zhuǎn)移概率τvx，設(shè)定未歸一化轉(zhuǎn)移概率為τ＝αp1q1（t，x）·wvx，其中αp1q1（t，x）的具體表示如式（9）所示：

其中，dtx表示節(jié)點(diǎn)t和x上的最短路徑距離。同理，對(duì)于p2，q2組下節(jié)點(diǎn)根據(jù)參數(shù)p2，q2計(jì)算對(duì)應(yīng)的轉(zhuǎn)移概率。

2.5 GeNI.De1算法

如2.2節(jié)所述，3種模型的算法實(shí)現(xiàn)只存在局部差異，考慮到模型偽代碼篇幅過(guò)長(zhǎng)，本文僅給出具有代表性的GeNI.De1模型的偽代碼，GeNI.De1算法如表2所示。

表2 GeNI.De1模型算法Table 2 GeNI.De1 model algorithm

GeNI.De1算法的輸入?yún)?shù)中，S1，S2是GeNI.De1模型中兩種采樣策略對(duì)應(yīng)的轉(zhuǎn)移概率τ1，τ2歸一化后的結(jié)果。AttributeClassfication（）中J表示對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)“度”的統(tǒng)計(jì)匯總結(jié)果，用于模型預(yù)分類(lèi)；預(yù)分類(lèi)策略P在2.2節(jié)有詳細(xì)描述。主函數(shù)GetFeatures（）中子函數(shù)GeNIWalk（）在偽代碼函數(shù)2中定義；StochasticGradientDescent（）在2.1節(jié)中定義。

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

為了驗(yàn)證GeNI方法的實(shí)際效果，實(shí)驗(yàn)在不同領(lǐng)域的公開(kāi)數(shù)據(jù)集上進(jìn)行驗(yàn)證，并與多個(gè)圖表示學(xué)習(xí)方法進(jìn)行對(duì)比。在所有模型上，首先利用無(wú)監(jiān)督的方法學(xué)習(xí)圖嵌入，然后在節(jié)點(diǎn)分類(lèi)任務(wù)上進(jìn)行評(píng)估，通過(guò)分類(lèi)效果判斷學(xué)習(xí)嵌入向量的質(zhì)量。在節(jié)點(diǎn)分類(lèi)任務(wù)中，為比較不同比例訓(xùn)練數(shù)據(jù)對(duì)模型性能的影響，實(shí)驗(yàn)分別選取30%～80%的數(shù)據(jù)集訓(xùn)練分類(lèi)器，然后在測(cè)試集上進(jìn)行測(cè)試。實(shí)驗(yàn)對(duì)每種情況重復(fù)10次，取其平均值作為最終的實(shí)驗(yàn)結(jié)果。

3.1 實(shí)驗(yàn)設(shè)定

實(shí)驗(yàn)采用無(wú)監(jiān)督方法學(xué)習(xí)圖嵌入，然后將嵌入向量應(yīng)用在節(jié)點(diǎn)二分類(lèi)或多分類(lèi)任務(wù)中。實(shí)驗(yàn)采用Logistic regression分類(lèi)方法訓(xùn)練分類(lèi)器，并用microF1和macroF1兩個(gè)評(píng)測(cè)指標(biāo)作為算法性能的評(píng)測(cè)標(biāo)準(zhǔn)。兩個(gè)評(píng)測(cè)指標(biāo)具體表達(dá)式如下：

其中：i為類(lèi)別總數(shù)；TPi表示類(lèi)別i中樣本分類(lèi)正確的樣本總數(shù)；FNi表示不屬于類(lèi)別i的樣本被錯(cuò)誤預(yù)測(cè)為類(lèi)別i的樣本總數(shù)；FPi表示類(lèi)別i中樣本分類(lèi)錯(cuò)誤的樣本總數(shù)；microF1i表示類(lèi)別i下的microF1值。

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

實(shí)驗(yàn)選定圖表示學(xué)習(xí)領(lǐng)域的4個(gè)公開(kāi)數(shù)據(jù)集進(jìn)行評(píng)測(cè)，這些數(shù)據(jù)集規(guī)模大小各異、來(lái)自多個(gè)不同領(lǐng)域，它們包括Europe-airports，Wiki，Node2vec PPI和Mashup PPI。實(shí)驗(yàn)選定這4個(gè)數(shù)據(jù)集旨在驗(yàn)證GeNI在不同領(lǐng)域不同規(guī)模網(wǎng)絡(luò)下節(jié)點(diǎn)分類(lèi)任務(wù)的有效性。這些數(shù)據(jù)集中只包含節(jié)點(diǎn)的結(jié)構(gòu)特征，不含屬性特征。各個(gè)數(shù)據(jù)集的詳細(xì)信息如表3所示。

表3 數(shù)據(jù)集的相關(guān)統(tǒng)計(jì)信息Table 3 Relevant statistics of dataset

Europe-airports：一個(gè)機(jī)場(chǎng)流量數(shù)據(jù)集，節(jié)點(diǎn)表示機(jī)場(chǎng)，邊代表兩個(gè)機(jī)場(chǎng)之間存在航班，標(biāo)簽表示機(jī)場(chǎng)對(duì)應(yīng)的活躍等級(jí)。

Wiki：一個(gè)單詞共現(xiàn)詞數(shù)據(jù)集，節(jié)點(diǎn)表示詞，邊代表兩個(gè)詞之間存在聯(lián)系，標(biāo)簽為每個(gè)詞對(duì)應(yīng)的詞性。數(shù)據(jù)集來(lái)自文獻(xiàn)［11］中Wiki數(shù)據(jù)集的一部分。

Node2vec PPI：一個(gè)具有功能注釋的蛋白質(zhì)網(wǎng)絡(luò)子圖，節(jié)點(diǎn)代表蛋白質(zhì)分子，邊代表蛋白質(zhì)分子之間存在相互作用，標(biāo)簽為蛋白質(zhì)分子對(duì)應(yīng)的功能注釋。數(shù)據(jù)集來(lái)自文獻(xiàn)［11］。

Mashup PPI：一個(gè)具有功能注釋的蛋白質(zhì)網(wǎng)絡(luò)數(shù)據(jù)集，節(jié)點(diǎn)、邊和標(biāo)簽的含義與Node2vec PPI數(shù)據(jù)集中相同，區(qū)別是數(shù)據(jù)集規(guī)模更大。數(shù)據(jù)集來(lái)自文獻(xiàn)［5］。

3.1.2 對(duì)比方法

實(shí)驗(yàn)在節(jié)點(diǎn)標(biāo)簽分類(lèi)任務(wù)上進(jìn)行評(píng)測(cè)，對(duì)于這項(xiàng)任務(wù)，采用以下4種方法作為對(duì)比方法，用以評(píng)價(jià)GeNI的有效性。

LINE（Large-scale information network embedding）：該方法研究了如何將結(jié)構(gòu)信息從大型網(wǎng)絡(luò)嵌入到低維向量，通過(guò)學(xué)習(xí)節(jié)點(diǎn)之間的一階、二階鄰域相似度，可以應(yīng)用在大型信息網(wǎng)絡(luò)中。

DeepWalk：該方法對(duì)于所有網(wǎng)絡(luò)場(chǎng)景，直接通過(guò)隨機(jī)采樣的策略來(lái)學(xué)習(xí)節(jié)點(diǎn)特征。

Node2vec：該方法在DeepWalk基礎(chǔ)上進(jìn)行優(yōu)化，引入了BFS和DFS兩個(gè)帶偏游走策略，更靈活地采集節(jié)點(diǎn)序列，學(xué)習(xí)節(jié)點(diǎn)特征。

SDNE：該方法從空間結(jié)構(gòu)相似度的角度定義節(jié)點(diǎn)的相似度，用于捕捉一些場(chǎng)景中兩個(gè)不是近鄰的節(jié)點(diǎn)也可能擁有較高的相似性的同類(lèi)別節(jié)點(diǎn)。

3.1.3 參數(shù)設(shè)定

為了確保實(shí)驗(yàn)結(jié)果的有效性，每種對(duì)比方法參數(shù)的設(shè)定均按照方法所在論文中提供的最優(yōu)參數(shù)進(jìn)行設(shè)定。詞向量維度均為d＝128。由于GeNI也需要參數(shù)控制節(jié)點(diǎn)采樣，為維持實(shí)驗(yàn)的公正性，參數(shù)設(shè)定范圍與Node2vec保持一致，均在｛0.25，0.5，1，2，4｝中選取參數(shù)設(shè)定。

3.2 基于節(jié)點(diǎn)“度”的圖表示學(xué)習(xí)方法

在網(wǎng)絡(luò)分析中，“度”是復(fù)雜網(wǎng)絡(luò)中評(píng)判節(jié)點(diǎn)重要性最直觀的指標(biāo)。無(wú)向圖中節(jié)點(diǎn)“度”的定義可以簡(jiǎn)單理解為節(jié)點(diǎn)鄰居的數(shù)目，一個(gè)節(jié)點(diǎn)度值越大，該節(jié)點(diǎn)在網(wǎng)絡(luò)中越重要。GeNI.De1與GeNI.De2模型正是以節(jié)點(diǎn)度作為預(yù)分類(lèi)標(biāo)準(zhǔn)。為更清晰表述不同預(yù)分類(lèi)標(biāo)準(zhǔn)對(duì)節(jié)點(diǎn)特征學(xué)習(xí)的影響，本節(jié)集中分析以節(jié)點(diǎn)“度”為預(yù)分類(lèi)標(biāo)準(zhǔn)時(shí)的實(shí)驗(yàn)結(jié)果，以“集聚系數(shù)”為分類(lèi)標(biāo)準(zhǔn)的GeNI.Cl模型將在3.3節(jié)分析總結(jié)。

表4-表7報(bào)告了在Europe-airports，Mashup PPI，Node2vec PPI和Wiki數(shù)據(jù)集上的分類(lèi)microF1值和macroF1（粗體表示所有方法中最好的）。實(shí)驗(yàn)結(jié)果表明除了在Europe-airports上，GeNI.De1與GeNI.De2比所有基線方法效果要好。證明了在同一數(shù)據(jù)集中使用“度”作為預(yù)處理標(biāo)準(zhǔn)可以更有效地采集節(jié)點(diǎn)序列，進(jìn)而提升下游節(jié)點(diǎn)分類(lèi)效果。

表4 在Europe-airports數(shù)據(jù)集上的micro F1和macro F1值（待續(xù)）Table 4 Micro F 1 and macro F 1 scores in Europe-airports dataset（to be continued）

表7 在Wiki數(shù)據(jù)集上的micro F1和macro F1值Table 7 Micro F1 and macro F 1 scores in Wiki dataset

續(xù)表4 在Europe-airports數(shù)據(jù)集上的micro F1和macro F1值Table 4 Micro F1 and macro F 1 scores in Europe-airports dataset（continued）

表5 在Mashup PPI數(shù)據(jù)集上的micro F1和macro F1值Table 5 Micro F1 and macro F 1 scores in Mashup PPI dataset

表6 在Node2vec PPI數(shù)據(jù)集上的micro F1和macro F1值Table 6 Micro F 1 and macro F 1 scores in Node2vec PPI dataset

從表4-表7中可以觀察到：（1）在所有數(shù)據(jù)集上，GeNI.De2較GeNI.De1整體表現(xiàn)出更好的效果，這是由于復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)本身的分布特征更加多樣，GeNI.De2可以更準(zhǔn)確地捕捉到同類(lèi)別的節(jié)點(diǎn)作為該節(jié)點(diǎn)的節(jié)點(diǎn)序列，以達(dá)到學(xué)習(xí)節(jié)點(diǎn)結(jié)構(gòu)特征的目的。（2）在Europe-airports數(shù)據(jù)集上，SDNE效果最優(yōu)，GeNI模型并沒(méi)有取得最好的分類(lèi)效果。這與網(wǎng)絡(luò)本身類(lèi)別分布相關(guān)，Europe-airports網(wǎng)絡(luò)主要以全局結(jié)構(gòu)特征作為類(lèi)別區(qū)分標(biāo)準(zhǔn)，SDNE更充分捕捉相關(guān)特征，因此擁有更好的分類(lèi)效果。GeNI雖然也能學(xué)習(xí)節(jié)點(diǎn)全局結(jié)構(gòu)特征，但為了保持與對(duì)比方法的一致性，將節(jié)點(diǎn)序列長(zhǎng)度控制在20，使得GeNI主要考慮局部結(jié)構(gòu)特征，但較Node2vec仍能表現(xiàn)出更好的分類(lèi)效果（表4）。（3）在Wiki和Node2vec PPI數(shù)據(jù)集上，GeNI.De2和GeNI.De1模型在不同比例訓(xùn)練集上較其他對(duì)比模型均表現(xiàn)出更好的分類(lèi)效果。當(dāng)訓(xùn)練集比例為80%時(shí)，GeNI.De2在Wiki數(shù)據(jù)集中比最好基線方法的macroF1值提升了1.6%；在Node2vec PPI數(shù)據(jù)集中比最好基線方法的macroF1值提升了0.7%。（4）在Mashup PPI數(shù)據(jù)集上，僅選取訓(xùn)練集比例為80%的情況進(jìn)行實(shí)驗(yàn)，這是由于實(shí)驗(yàn)在Europe-airports，Wiki，Node2vec PPI等數(shù)據(jù)集上已經(jīng)得出不同比例訓(xùn)練集時(shí)所對(duì)應(yīng)的結(jié)論。實(shí)驗(yàn)結(jié)果表明GeNI模型在大規(guī)模數(shù)據(jù)集上的分類(lèi)效果（節(jié)點(diǎn)數(shù)量萬(wàn)級(jí)，邊10萬(wàn)級(jí)）較基線模型仍有穩(wěn)定提升。

3.3 基于集聚系數(shù)的圖表示學(xué)習(xí)方法

為了探究更多節(jié)點(diǎn)重要性指標(biāo)對(duì)NRL的影響，提出了一種以集聚系數(shù)替代節(jié)點(diǎn)度的NRL方法GeNI.Cl。集聚系數(shù)是一個(gè)評(píng)判網(wǎng)絡(luò)中節(jié)點(diǎn)集結(jié)成團(tuán)程度的指標(biāo)。通過(guò)計(jì)算集聚系數(shù)，可以更準(zhǔn)確地識(shí)別網(wǎng)絡(luò)中一些關(guān)鍵性節(jié)點(diǎn)。通過(guò)在Europe-airports，Wiki和Node2vec PPI數(shù)據(jù)集上進(jìn)行節(jié)點(diǎn)分類(lèi)任務(wù)實(shí)驗(yàn)驗(yàn)證GeNI.Cl方法的有效性。圖3為GeNI.Cl方法進(jìn)行節(jié)點(diǎn)分類(lèi)任務(wù)的效果圖。其中，橫坐標(biāo)代表不同比例訓(xùn)練集，縱坐標(biāo)代表microF1和macroF1兩種評(píng)測(cè)指標(biāo)。

圖3 GeNI.Cl在不同網(wǎng)絡(luò)上節(jié)點(diǎn)分類(lèi)任務(wù)效果圖Fig.3 The comparison of node classification tasks of GeNI.Cl on different networks

從圖3所示的分類(lèi)任務(wù)效果圖可以看出：（1）在不同數(shù)據(jù)集、不同訓(xùn)練比例數(shù)據(jù)下GeNI.Cl的分類(lèi)效果均優(yōu)于Node2vec。在Europe-airports數(shù)據(jù)集中，不同比例訓(xùn)練集下提升明顯。在Wiki和Node2vec PPI數(shù)據(jù)集中，訓(xùn)練比例超過(guò)70%后分類(lèi)效果提升明顯。實(shí)驗(yàn)表明在節(jié)點(diǎn)分類(lèi)任務(wù)中，以集聚系數(shù)作為預(yù)處理標(biāo)準(zhǔn)能夠更有效地學(xué)習(xí)節(jié)點(diǎn)特征信息。（2）3種數(shù)據(jù)集中，GeNI.Cl的整體分類(lèi)效果優(yōu)于GeNI.De1，在Europe-airports數(shù)據(jù)集中，GeNI.Cl的整體分類(lèi)效果優(yōu)于GeNI.De2。實(shí)驗(yàn)表明在節(jié)點(diǎn)分類(lèi)任務(wù)中，以集聚系數(shù)作為預(yù)處理標(biāo)準(zhǔn)能夠比以度作為預(yù)處理標(biāo)準(zhǔn)獲得更好的效果。

4 結(jié)論

通過(guò)將節(jié)點(diǎn)統(tǒng)計(jì)特征作為先驗(yàn)知識(shí)，為統(tǒng)計(jì)特征不同的節(jié)點(diǎn)設(shè)計(jì)相應(yīng)的游走策略，提出一種融合節(jié)點(diǎn)統(tǒng)計(jì)特征的圖表示學(xué)習(xí)方法GeNI。實(shí)驗(yàn)結(jié)果表明，GeNI在不同領(lǐng)域、不同規(guī)模的網(wǎng)絡(luò)下進(jìn)行節(jié)點(diǎn)分類(lèi)任務(wù)的效果優(yōu)于大部分對(duì)比方法，較其他方法表現(xiàn)出更好的適應(yīng)能力。GeNI的高靈活性使其高效保留節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)湫畔?，從而提升圖嵌入質(zhì)量。