GeNI：一種面向節點分類的網絡表示學習方法

黃 亮 楊春明，2

（1.西南科技大學計算機科學與技術學院 四川綿陽 621010；2.四川省大數據與智能系統工程技術研究中心 四川綿陽 621010）

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

NRL主要通過學習節點的網絡拓撲結構獲取嵌入向量，目前已在鏈接預測中取得很好的效果，但在節點分類任務中效果不佳。如文獻［5］表明多種經典NRL方法在PPI，COOC等網絡上的鏈接預測任務的精度可達90%，而在節點分類任務上的最高精度值只有48%。節點的類別信息除了與網絡拓撲結構有關外，還與該節點在網絡中的重要程度、網絡所屬領域有較強的相關性。如社交網絡中，擁有相同興趣愛好的人們通常相互鏈接在一起。歐洲飛機航線網絡中，擁有相同活躍等級的機場卻可能在網絡的不同位置［6］。社交網絡傾向于通過節點局部特征信息得到相似的節點；航線網絡傾向于從節點的全局特征信息中獲得相似節點。目前的NRL方法主要采用隨機游走或遍歷的方式獲取節點序列，沒有考慮同一網絡中不同節點重要性的區別。

針對上述問題，文章提出了一種考慮節點重要性的用于節點分類的圖表示學習方法GeNI（Graph embedding based on node importance）。GeNI首先通過度、集聚系數等節點重要性指標對節點預分類以區分復雜網絡中不同結構類型的節點，然后將分類結果作為先驗知識，對結構類型不同的節點采用不同的帶偏游走策略獲得節點序列，并基于DeepWalk思想，將NRL問題轉化為詞嵌入問題。在多個公開數據集上的節點分類任務中對本文提出的方法進行了驗證。

1 網絡表示學習方法

網絡表示學習（NRL）又稱圖表示學習方法。圖表示學習方法通?？煞譃榛诰仃嚪纸狻㈦S機游走和深度學習的方法。

基于矩陣分解的方法以網絡結構信息為基礎構建矩陣作為模型輸入，通過對矩陣降維，得到低維的節點向量表示。如LLE（Locally linear embedding）［7］通過其鄰居節點的線性組合來近似得到節點表示；LE（Laplace eigenmaps）［8］通過平滑項方式，使原始空間中兩個相似節點在低維向量空間中有相近的表示；Graph factorization［9］通過在均方誤差基礎上添加一個L2正則項重建圖的鄰接矩陣，同時將時間復雜度控制在O（｜E｜）。

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

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

除了利用節點的結構特征信息，有學者提出使用節點屬性特征信息來學習圖嵌入。TADW方法［18］提出一個新的學習節點特征方法，通過加入節點文本特征信息，與結構特征相結合，共同學習圖嵌入；MMDW方法［19］充分利用網絡中節點的標簽信息，如維基百科網絡中，頂點可能被標記成物理、天文、人物等，并在TADW的基礎上加入SVM（Support vector machines），增強不同類別頂點向量的差異，提升網絡中節點分類效果。

矩陣分解方法簡單利用網絡的結構信息，定義節點向量表示；深度學習方法雖然可以更準確地學習節點的特征，但由于模型復雜度增加，導致時間復雜度高的缺點突出，這類方法在大型網絡中應用十分耗時；綜合節點結構與屬性特征的方法需要為節點定義相應的數據標簽，但在實際工作中，大量數據標簽往往具有較高的獲取條件；幾種經典基于隨機游走的圖表示方法中，DeepWalk對于所有應用場景，采用完全隨機的節點采集策略。實際情況中，不同網絡結構特征往往不完全相同，DeepWalk難以實現為不同網絡構建其特有的節點采集策略。Node2vec對其進行了優化，對于不同網絡可以定義對應的節點采集策略，但在結構復雜的大型網絡中，同一網絡的局部結構特征也存在較大差異，Node2vec忽略了這種差異，對于網絡中所有節點，采用相同節點采集策略對節點進行序列采集。但在節點分類任務中，對于同一網絡下不同結構類型的節點，采用對應的節點采集策略有利于更準確獲取與源節點緊密相關的序列，從而提升節點分類效果。因此，在節點采樣階段，需要區分網絡中不同結構類型的節點。

2 融合節點重要性的圖表示學習方法

2.1 GeNI模型定義

給定網絡G＝（V，E），網絡表示學習方法將網絡中每個節點vi分別映射為一個低維的特征向量?（vi）∈Rd，其中，d?｜V｜，且要求兩個相似的節點映射后的向量距離相近；否則，映射后的向量距離較遠。符號定義如表1所示。

表1 符號定義Table 1 Definition of symbols

令G＝（V，E）為給定網絡，f：V→Rd是從節點到其特征表示的映射函數。d是一個參數，用于指定特征表示的維數；f是大小為｜V｜×d的參數矩陣。對于每個源節點vi∈V，將NS（vi）∈V定義為通過鄰域采樣策略S生成的節點vi的網絡鄰域。

GeNI模型的優化目標是最大化鄰居節點出現的概率，如何定義鄰居節點非常重要，節點的采樣策略也直接影響鄰居節點的獲取。GeNI模型最大化節點vi鄰域NS（vi）的對數概率，起始目標函數如式（1）所示：

為使目標函數可解，引入條件獨立性和特征空間對稱性兩個標準假設。條件獨立性假設認為各個鄰居節點之間相互獨立，如式（2）所示：

特征空間對稱性認為節點與其鄰居節點在特征空間中的影響是相互的，故可將每個節點-鄰節點建模成一個個softmax單元，并將其特征信息以點乘方式實現參數化，如式（3）所示：

基于以上假設，優化后最終目標函數如式（4）所示：

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

對于大型網絡而言，Zvi計算成本較高，為降低計算成本，使用負采樣對其進行近似。

2.2 GeNI采樣策略

給定節點ui，根據設定的采樣策略生成（抽樣）它的鄰節點集合N（ui）。在已有算法中，廣度優先采樣（BFS：Breadth-first sampling）與深度優先采樣（DFS：Depth-first sampling）兩種采樣方法發揮了重要作用。BFS傾向于對周圍節點采樣，獲取節點的局部結構信息；DFS傾向于探索網絡的更深處，獲得網絡的全局結構信息。

Node2vec在節點采樣階段定義了一種基于二階隨機游走的采樣策略。在不同網絡中，該策略結合BFS和DFS捕捉網絡的局部和全局結構信息。但同一網絡下節點類別分布規律并不唯一。如圖1所示的網絡，節點顏色表示節點的類別，兩種不同顏色的箭頭表示節點1、節點2在隨機游走階段中的最優軌跡。從圖中可以發現節點1趨向于向周圍的節點游走，而節點2趨向于向網絡更深處游走，對于網絡中完全不同的節點分布情況，現有的圖表示學習方法大多難以有效解決這類問題。

圖1 節點1、節點2在隨機游走中的最優軌跡Fig.1 The optimal routes of nodes 1 and 2 in random walk

在Node2vec中，當模型想要以節點1的特征分布為標準設計游走策略時，節點2的游走路徑就可能變為如圖2（b）所示；當模型想要以節點2的特征分布為標準設計游走策略時，節點1的游走路徑就可能變為如圖2（a）所示。兩種情況都會造成網絡結構特征極大缺失。

圖2 節點1、節點2在隨機游走中可能的軌跡Fig.2 The possible routes of nodes 1 and 2 in random walk

由于網絡中節點的局部分布規律并不相同，導致單一采樣策略難以準確獲取與節點緊密聯系的節點序列。為豐富節點采樣方式，提高模型的靈活性，GeNI在采樣前統計節點重要性信息并結合預分類策略P對節點進行預處理：對于網絡中每一個節點，GeNI首先統計節點在網絡中的重要性特征，根據統計結果實現每一個節點的預分類，再對不同類別節點，設定不同采樣策略。以節點重要性指標“度”作為節點預分類標準設計了模型GeNI.De1和GeNI.De2；以“集聚系數”指標作為節點預分類標準設計了模型GeNI.Cl。3種模型的主要區別如下：（1）節點預處理階段時節點預分類標準不同。GeNI.De1和GeNI.De2以節點“度”作為預分類標準；GeNI.Cl以節點“集聚系數”作為預分類標準。（2）節點預分類的類別總數不同。GeNI.De1和GeNI.Cl將網絡中節點分為兩類，對不同類別節點采用不同的采集策略。為了探究同一網絡中更多采樣策略對節點序列獲取的影響，GeNI.De2將網絡中節點分為三類，對不同類別節點采用不同的采集策略。

2.3 節點重要性指標

2.3.1 度

節點度用來表示與該節點直接相鄰的鄰居數目［20］，網絡中任意節點i的度k（i）如式（6）所示：

節點度指標直接反映該節點一階鄰域的密集程度，同時也展示了該節點對鄰居節點的直接影響力。例如在社交網絡中，度值更大的節點擁有更大的影響力，周圍節點往往通過它來獲取相關信息。

2.3.2 集聚系數

節點度可以反應節點與周圍節點直接建立聯系的能力，但不能反應該節點鄰居之間的關系。實際上，節點鄰居之間建立的聯系越密集，節點鄰居與該節點同類別的可能性就越大［21］。集聚系數可以很好評估這種可能，它描述了網絡中節點鄰居之間互為鄰居的比例，具體表達如式（7）所示：

其中：k（i）表示節點的度；ei表示節點i與任意兩個鄰居之間形成三角形的個數，也就是節點鄰居相互連接的個數。通過這種方式，可以直觀反映出節點鄰居之間的相關程度。

2.4 隨機游走與搜索偏差

給定源節點vi，模擬一個長度為l的隨機游走。l是源節點vi對應節點序列的長度，是模型參數之一，取值與網絡規模、密度有關（通常在［10，20］之間進行選擇），恰當的l可提升最終嵌入向量的質量。ci表示在游走中的第i個節點，通過式（8）生成：

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

其中，dtx表示節點t和x上的最短路徑距離。同理，對于p2，q2組下節點根據參數p2，q2計算對應的轉移概率。

2.5 GeNI.De1算法

如2.2節所述，3種模型的算法實現只存在局部差異，考慮到模型偽代碼篇幅過長，本文僅給出具有代表性的GeNI.De1模型的偽代碼，GeNI.De1算法如表2所示。

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

GeNI.De1算法的輸入參數中，S1，S2是GeNI.De1模型中兩種采樣策略對應的轉移概率τ1，τ2歸一化后的結果。AttributeClassfication（）中J表示對網絡中節點“度”的統計匯總結果，用于模型預分類；預分類策略P在2.2節有詳細描述。主函數GetFeatures（）中子函數GeNIWalk（）在偽代碼函數2中定義；StochasticGradientDescent（）在2.1節中定義。

3 實驗及結果分析

為了驗證GeNI方法的實際效果，實驗在不同領域的公開數據集上進行驗證，并與多個圖表示學習方法進行對比。在所有模型上，首先利用無監督的方法學習圖嵌入，然后在節點分類任務上進行評估，通過分類效果判斷學習嵌入向量的質量。在節點分類任務中，為比較不同比例訓練數據對模型性能的影響，實驗分別選取30%～80%的數據集訓練分類器，然后在測試集上進行測試。實驗對每種情況重復10次，取其平均值作為最終的實驗結果。

3.1 實驗設定

實驗采用無監督方法學習圖嵌入，然后將嵌入向量應用在節點二分類或多分類任務中。實驗采用Logistic regression分類方法訓練分類器，并用microF1和macroF1兩個評測指標作為算法性能的評測標準。兩個評測指標具體表達式如下：

其中：i為類別總數；TPi表示類別i中樣本分類正確的樣本總數；FNi表示不屬于類別i的樣本被錯誤預測為類別i的樣本總數；FPi表示類別i中樣本分類錯誤的樣本總數；microF1i表示類別i下的microF1值。

3.1.1 數據集

實驗選定圖表示學習領域的4個公開數據集進行評測，這些數據集規模大小各異、來自多個不同領域，它們包括Europe-airports，Wiki，Node2vec PPI和Mashup PPI。實驗選定這4個數據集旨在驗證GeNI在不同領域不同規模網絡下節點分類任務的有效性。這些數據集中只包含節點的結構特征，不含屬性特征。各個數據集的詳細信息如表3所示。

表3 數據集的相關統計信息Table 3 Relevant statistics of dataset

Europe-airports：一個機場流量數據集，節點表示機場，邊代表兩個機場之間存在航班，標簽表示機場對應的活躍等級。

Wiki：一個單詞共現詞數據集，節點表示詞，邊代表兩個詞之間存在聯系，標簽為每個詞對應的詞性。數據集來自文獻［11］中Wiki數據集的一部分。

Node2vec PPI：一個具有功能注釋的蛋白質網絡子圖，節點代表蛋白質分子，邊代表蛋白質分子之間存在相互作用，標簽為蛋白質分子對應的功能注釋。數據集來自文獻［11］。

Mashup PPI：一個具有功能注釋的蛋白質網絡數據集，節點、邊和標簽的含義與Node2vec PPI數據集中相同，區別是數據集規模更大。數據集來自文獻［5］。

3.1.2 對比方法

實驗在節點標簽分類任務上進行評測，對于這項任務，采用以下4種方法作為對比方法，用以評價GeNI的有效性。

LINE（Large-scale information network embedding）：該方法研究了如何將結構信息從大型網絡嵌入到低維向量，通過學習節點之間的一階、二階鄰域相似度，可以應用在大型信息網絡中。

DeepWalk：該方法對于所有網絡場景，直接通過隨機采樣的策略來學習節點特征。

Node2vec：該方法在DeepWalk基礎上進行優化，引入了BFS和DFS兩個帶偏游走策略，更靈活地采集節點序列，學習節點特征。

SDNE：該方法從空間結構相似度的角度定義節點的相似度，用于捕捉一些場景中兩個不是近鄰的節點也可能擁有較高的相似性的同類別節點。

3.1.3 參數設定

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

3.2 基于節點“度”的圖表示學習方法

在網絡分析中，“度”是復雜網絡中評判節點重要性最直觀的指標。無向圖中節點“度”的定義可以簡單理解為節點鄰居的數目，一個節點度值越大，該節點在網絡中越重要。GeNI.De1與GeNI.De2模型正是以節點度作為預分類標準。為更清晰表述不同預分類標準對節點特征學習的影響，本節集中分析以節點“度”為預分類標準時的實驗結果，以“集聚系數”為分類標準的GeNI.Cl模型將在3.3節分析總結。

表4-表7報告了在Europe-airports，Mashup PPI，Node2vec PPI和Wiki數據集上的分類microF1值和macroF1（粗體表示所有方法中最好的）。實驗結果表明除了在Europe-airports上，GeNI.De1與GeNI.De2比所有基線方法效果要好。證明了在同一數據集中使用“度”作為預處理標準可以更有效地采集節點序列，進而提升下游節點分類效果。

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

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

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

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

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

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

3.3 基于集聚系數的圖表示學習方法

為了探究更多節點重要性指標對NRL的影響，提出了一種以集聚系數替代節點度的NRL方法GeNI.Cl。集聚系數是一個評判網絡中節點集結成團程度的指標。通過計算集聚系數，可以更準確地識別網絡中一些關鍵性節點。通過在Europe-airports，Wiki和Node2vec PPI數據集上進行節點分類任務實驗驗證GeNI.Cl方法的有效性。圖3為GeNI.Cl方法進行節點分類任務的效果圖。其中，橫坐標代表不同比例訓練集，縱坐標代表microF1和macroF1兩種評測指標。

圖3 GeNI.Cl在不同網絡上節點分類任務效果圖Fig.3 The comparison of node classification tasks of GeNI.Cl on different networks

從圖3所示的分類任務效果圖可以看出：（1）在不同數據集、不同訓練比例數據下GeNI.Cl的分類效果均優于Node2vec。在Europe-airports數據集中，不同比例訓練集下提升明顯。在Wiki和Node2vec PPI數據集中，訓練比例超過70%后分類效果提升明顯。實驗表明在節點分類任務中，以集聚系數作為預處理標準能夠更有效地學習節點特征信息。（2）3種數據集中，GeNI.Cl的整體分類效果優于GeNI.De1，在Europe-airports數據集中，GeNI.Cl的整體分類效果優于GeNI.De2。實驗表明在節點分類任務中，以集聚系數作為預處理標準能夠比以度作為預處理標準獲得更好的效果。

4 結論

通過將節點統計特征作為先驗知識，為統計特征不同的節點設計相應的游走策略，提出一種融合節點統計特征的圖表示學習方法GeNI。實驗結果表明，GeNI在不同領域、不同規模的網絡下進行節點分類任務的效果優于大部分對比方法，較其他方法表現出更好的適應能力。GeNI的高靈活性使其高效保留節點的網絡拓撲信息，從而提升圖嵌入質量。