基于改進圖注意機制的網絡嵌入方法研究及應用

韓津津，李智杰，李昌華，張 頡

(西安建筑科技大學 信息與控制工程學院，西安 710055)

0 引言

信息網絡是最為常見的一種信息載體和形式，隨著互聯網的不斷發展，各種應用場景下極為豐富的信息網絡數據已成為日常生活中不可或缺的一部分[1]。網絡數據結構可以自然地表達物體與物體間的聯系，用于對數據信息進行系統的建模。如社交媒體網絡中熱點話題的深度挖掘[2]、移動通信網絡中用戶群體的分類[3]以及論文推薦系統中引文網絡的劃分[4]等.在這些場景中，用戶、項目、分子和知識概念等現實實體被抽象為網絡中的節點，而實體之間的關系被建模為它們之間的鏈接[3]。基于網絡嵌入的表示學習研究旨在探索更好地分析復雜信息網絡中節點間的聯系，尋找解決信息網絡背景下的各種實際問題的普適方法，有效融合網絡結構與節點外部信息，形成更具區分性的網絡嵌入表示[6]。網絡嵌入的目的是將每個節點映射到一個低維向量空間，得到節點的低維向量表示。節點的表示向量可以應用到許多下游分析任務，如網絡節點分類[7]、可視化[8]等。為獲得有效的網絡嵌入并在實際任務中獲得更好的表現，需要充分利用圖的拓撲結構及節點特征中蘊含的豐富信息。

網絡數據信息特征挖掘首先需要面對的挑戰是如何恰當的表示網絡數據[9]。早期的網絡嵌入算法基于矩陣特征向量計算，利用相近節點其特征相似的思想，通過對矩陣分解來近似網絡嵌入中節點的特征向量表示，例如GraRep[10]、HOPE[11]等模型，但這種方式對于大規模的網絡嵌入是非常耗時的。隨機游走通過近似網絡節點中心性和相似性等屬性來獲得網絡嵌入表示，這針對大型網絡圖是有效的，典型的模型有DeepWalk[12]、node2vec[13]等。

圖神經網絡(GNN，graph neural network)[14]的研究解決了非歐氏空間結構網絡數據在經過傳統離散卷積的過程中無法保持平移不變形的局限性。利用實體之間的內在關系，為網絡嵌入學習開辟了一條獨特的道路。GNN通過聚合目標節點的鄰域來更新自身新的嵌入表示，大多數GNN變體將在其聚合器中分配將和之間的非參數化權重.例如傳統的圖卷積神經網絡(GCN，graph convolutional neural networks)[15]因其強大的迭代訓練模式和聚合信息的能力，能夠實現網絡嵌入中聚合一階鄰域信息近似的節點特征更新方式，但是訓練過程中由于共享相同的參數化權重，因此無法學習和區分目標節點及其鄰居之間的信息，然而考慮網絡中節點的不同貢獻在現實世界數據中是非常重要的，因為并非所有的邊都有相似的影響。一個自然的替代解決方案是使邊權重能夠訓練，以具有更好的表達能力。為了在聚合中分配可學習的權重，圖注意力網絡(GAT，graph attention network)[16]在進行鄰域聚合時，采用注意力機制為目標節點的鄰域節點分配不同的權重系數，以區分鄰居對目標節點的不同貢獻程度，以此來聚合網絡中的節點信息表征。盡管在GNN聚合器中加入注意力機制在各種任務上取得了令人滿意的性能，但是存在兩個局限性：首先，圖卷積過程中只能聚合中心節點的一階鄰域特征，無法獲得高階鄰域信息來擴大局部網絡結構的感受野，這將造成網絡嵌入表征局部節點劃分不明確的問題，其次，通過注意力機制篩選節點造成的問題是權重分配雖然將節點特征按照重要程度進行劃分，但是當下一層網絡訓練時會受到權重特征篩選的影響，無法將最原始的基數信息作為新一層的網絡訓練[17]，這些基數信息包含了網絡節點的屬性特征和局部結構信息，由于注意力權重，這些基數信息會被過濾掉一部分，這致使網絡嵌入表征學習過程會丟失掉初始信息，影響了對于網絡結構的判別能力。

為了解決這些問題，本文基于圖注意力機制為出發點，探索可解決的改進方案，提出了一種二階鄰域基數保留策略的圖注意力神經網絡模型(SNCR-GAT)，綜合考慮網絡嵌入中的多鄰域信息聚合以及模型訓練中的基數信息保留問題。本文的貢獻有以下3點：1)基于網絡節點鄰接矩陣的冪實現二階鄰域連通性，以擴大局部信息的收斂感受野來聚合二階鄰域信息；2)為了保證模型在訓練階段保留更多的基數信息，對注意力機制更新網絡節點特征的聚合函數進行了一些改進；以實現基數信息的保留；3)為驗證SNCR-GAT模型的網絡嵌入效果，我們在3個真實的網絡數據集Cora、Citeseer、Pumbed上進行了節點分類及可視化兩個實際應用實驗，相比較其它基準圖神經網絡模型具有更高的網絡嵌入效果。

1 相關工作

圖1 圖注意力信息特征聚合方式

節點特征聚合依賴于Attention對鄰域重要節點的選擇，在K階鄰域生成的鄰接矩陣中，對于每個節點xi，為了表現目標節點對待鄰域節點選擇的偏向不同，注意力機制α:RF′×F′→R是共享的，它為每個鄰域節點計算一個與目標節點的相關度值，這個值決定了該鄰域對中心節點的重要程度。計算方式如下：

(1)

(2)

注意力機制Attention是一種靜態非線性映射，基于單層結構實現的前饋神經網絡，能夠高效完成任意大小樣本集的訓練。節點間的注意系數αij∈R2F′作為網絡參數參與訓練，并使用LeakReLU作為非線性激活函數，其計算方式如下：

(3)

(4)

根據公式，對于節點i新的特征向量表示聚合方式是：先將所有鄰居節點特征向量hj與權重矩陣W進行線性求和，同時乘以注意力權重系數，最后將線性和進行激活做非線性轉換。

2 二階鄰域基數信息保留策略

2.1 二階鄰域節點信息聚合方案

為了深度挖掘網絡數據中局部結構特征，聚合更多的鄰域信息來生成有效的目標節點嵌入表示，采用了如圖2所示的二階鄰域信息聚合方案。

圖2 二階鄰域信息聚合

二鄰域信息聚合通過網絡節點鄰接矩陣的2次冪作為屏蔽矩陣實現2階鄰域的信息收斂，從各階鄰域提取局部結構特征，獲得節點的多個中間表示。通過增加鄰接矩陣的2次冪能夠實現目標節點與2階鄰居的連通性，獲取到2階鄰居的信息傳遞，通過鄰接矩陣得到目標節點2跳鄰域的邊連接，如下所示:

在一階鄰域鄰接矩陣A中，當兩個點之間存在一條邊時，矩陣中元素αij=1，不存在邊時αij=0，這表明從點vi出發走一跳到點vj有1條路徑。當對鄰接矩陣A平方之后，對角線元素αii表示了當前節點的度，并且跳數加一，每一個元素αij表示的是當前目標節點vi經過兩跳到達鄰居節點vj的路徑有多少，以節點vi→vj為例，經過兩跳可到達的路徑數為2，分別是v1→v4→v2和v1→v3→v2。因此可以說A2建立了以中心節點為目標的周圍二階鄰域的邊連接，由于節點之間是通過邊進行信息傳遞的，這樣的操作首先增加了圖的連通性，保障了目標節點更新新的節點過程中聚合更多的局部鄰域結構信息，對于目標節點，擴大了局部信息收斂的感受野，同時也提高了嵌入向量的有效性。

2.2 基數保留策略

為提高圖注意力模型在節點嵌入中的結構判別能力，保證在不改變注意力函數保持原來的注意機制學習能力的情況下，在式(4)目標節點特征聚合方式上優化了每一層網絡更新新的節點向量特征的輸出方式：

(5)

(6)

SNCR-GAT模型訓練過程如下：

輸入：網絡數據集Cora、Citeseer和Pumbed

處理：1)節點特征預處理(劃分節點特征和標簽信息);

2)應用稀疏矩陣存儲節點特征，劃分訓練集、驗證集和測試集;

3)構建二階信息收斂的鄰接矩陣。

訓練：1)初始化權重用于輸入特征的線性變化；

2)計算參數化權值向量并初始化；

3)線性變換節點特征；

4)利用公式(1)計算注意力系數；

5)Softmax歸一化鄰居節點特征；

6)根據基數保留策略公式(6)生成嵌入向量矩陣。

輸出：節點分類預測精度。

3 實驗與分析

3.1 數據集

為了驗證本文所提模型SNCR-GAT的實際效果，在3個引文網絡數據集Cora，Citeseer和Pumbed上進行實驗.每個數據集中的節點表示一篇論文，邊構成引用關系，數據集詳細信息見表1。

表1 數據集信息描述

3.2 實驗設置

實驗是基于半監督的訓練模式，主網絡采用兩層基于注意力機制的GCN，第一層用來學習節點的特征表示，利用12個多頭注意力端來平衡模型訓練，特征向量聚合后非線性激活采用LeakRelu函數.第二層網絡是數據節點分類層，通過softmax函數實現。

為了能夠找到適合模型性能的最好參數，在參考其它GNN模型的最優參數的同時也進行了自行調整，并且為了方便比較模型的實驗效果，采取控制單一變量的原則構建實驗所涉及對比的圖神經網絡模型，為了驗證改進模型在圖嵌入時的表現效果，對多個不同的標準數據集進行了訓練，測試以及驗證.實驗中初始網絡學習率為0.02，模型優化采用自適應的Adam[18]優化器，統一設置Dropout率為0.6，模型訓練迭代100次，經過測試隨著迭代次數的增加，結果會出現平滑現象，同時采用多頭注意力機制來增加模型訓練的穩定性,實驗環境配置見表2。

表2 實驗環境配置

3.3 節點分類應用實驗

3.3.1 模型對比

實驗結果將所提模型SNCR-GAT與其它基準方法生成的網絡嵌入進行比較，包括通過隨機游走生成節點序列學習網絡嵌入的DeepWalk、學習節點連續特征表示的node2vec、基于譜分解定義卷積操作的GCN、通過Attention生成不同權重的基準模型GAT。前面兩個方法都是通過中心節點沿邊游走，利用后續節點出現的概率保持節點的高度相似來生成節點特征表示。而基于神經網絡訓練的GCN和GAT則是利用迭代訓練聚合不同的鄰域信息來生成網絡節點嵌入。通過對比這幾個典型的基本算法在節點嵌入上的效果來表現SNCR-GAT的優勢。

3.3.2 結果與分析

為驗證SNCR-GAT模型相較于在網絡嵌入中的整體分類效果，與文獻[14]模型進行了對比實驗，同時為保證實驗結果的公平準確性，采用了十折交叉驗證[19]測試模型，將數據集分成10份，每一份都作為一次測試集來進行實驗，最終結果以10次結果均值為準。10次實驗結果對比如圖3所示.其中橫軸代表每一份測試集，縱軸表示分類精度(單位：%)。

圖3 十折交叉驗證節點分類精度對比

實驗結果表明，本文采用的二階鄰域基數保留策略在網絡嵌入上的效果的確優于基準GAT模型，分析其原因，SNCR-GAT在目標節點特征更新上能夠聚合更大范圍內的鄰域信息，保留更多的結構屬性。同時也減小了網絡訓練中受注意力系數篩選影響導致的部分早期基數信息的丟失，這為提高節點分類任務準確率方面的表現做出了極大的貢獻.總的實驗結果對比匯總在表3中。

表3 節點分類精確率對比

通過比較節點的分類精度，SNCR-GAT模型在總體上表現良好，在Cora、Citeseer、Pubmed三個數據集上的訓練準確率相比較原始的GAT網絡提升分別為：5.6、3.6和4.5。特別是Cora數據集上分類精度提升明顯。這也表明SNCR-GAT模型在圖嵌入過程中進行節點表示向量更新時的，有效的減少了信息丟失的問題，重要的是在基于二階鄰域的信息聚合方式對于當前節點更新新的向量表示提供了更廣泛的信息，基數保留信息聚合策略對于重要的鄰域信息選擇更可靠。

3.3.3 復雜度分析

SNCR-GAT在訓練階段首先會將節點的特征向量做一個維數F→F′的空間映射，其時間復雜度為O(|V|×F×F′)，|V|是網絡中節點數；另外注意力機制α(·)是將2F′維的特征向量映射為實數的過程，因此會產生O(|E|×F′)的計算復雜度，其中|E|是邊數。二階鄰域聚合過程是一個加權求和的過程，只涉及到一次鄰接矩陣的平方運算，同時基數保留的聚合函數做了一次特征向量的加法運算，均不存在高復雜度的乘法運算。采用二階鄰域基數保留策略能夠使模型在最少的epoch次數下收斂到最好的結果，綜合評價，SNCR-GAT模型在復雜度上也存在明顯的優勢。

3.3.4 階鄰域分析

為了證明二階鄰域信息收斂的有效性，在實驗中以逐步增長階數的方式測試采用不同階鄰域對模型整體的影響，隨著階數增加，利用節點分類實驗結果和算法模型訓練時間進行評估，同樣地，對每一階的測試中，模型運行10次，以平均準確率為作為最終結果。實驗在Cora數據集上測試，如圖4所示，為方便比較，將節點分類精確度曲線與時間曲線在同一圖上進行描述，橫軸代表鄰域階數k，縱軸代表時間(min)。

圖4 k階鄰域節點分類準確率對比

實驗結果表明，隨著鄰域階數的增加，實驗結果沒有受到太大的波動，反觀模型收斂時間在增加。分析其原因，考慮二階以上的鄰域信息收斂會致使SNCR-GAT模型可能會從不太相關的鄰居那里獲取大量信息，從而無法學習合適的節點表示，因此影響到網絡嵌入節點分類的精度，同時階數的增加，需要計算鄰接矩陣的次冪來增加圖的k跳連通性以傳遞信息，這會提高模型初期數據特征處理的計算復雜度，訓練時間會更長，不利于實驗的高效進行，因此基于二階鄰域下的基數信息保留方案是更有效的，在保證模型性能的條件下，控制時間復雜度在可行的范圍內是可取的。

3.4 網絡可視化應用實驗

對網絡嵌入效果的另一種評估方式是對學習到的網絡嵌入表示進行可視化展示。網絡嵌入向量作為d維空間的表示，無法直觀的根據向量特征進行評估模型的嵌入效果。我們以Cora數據集進行可視化展示來評估SNCR-GAT的網絡嵌入效果。對比模型選用了GCN，GAT這兩個同為聚合收斂的基準模型.首先將對比模型及我們的模型鎖所學習到的節點嵌入向量輸入到t分布隨機鄰域嵌入(t-SNE，t-distributed stochastic neighbor embedding)[20]模型中，t-SNE能夠通過降維的方式將網絡嵌入向量表示映射到指定維數空間中進行展示，為了能夠在分類可視化的基礎上更好的觀察網絡嵌入效果的層次結構劃分，我們在三維空間中實現了所有模型的可視化。

圖5展示了Cora數據集在不同模型學習到的網絡嵌入表示的三維可視化效果。其中每一個點在三維空間中都有一個坐標，以實現可視化。每一種類別標簽對應一種形狀，具有相同類別標簽的節點再二維空間中對應的點具有相同的形狀。對比GCN、GAT和SNCR-GAT在三維可視化上的節點分類效果，可以通過明顯的層次結構清楚的看到節點之間的類別劃分，同時在GCN的可視化任務中，不同類別的簇形成鮮明的對比，但是簇與簇之間的簇間距很小導致一些相鄰邊界之間的點劃入錯誤的類別中。比較明顯的是，SNCR-GAT在可視化任務上性能更好，表現出了清晰的類別和邊界距離感，錯分的節點也比較少。因此，可以認為SNCR-GAT在可視化任務上獲得了具有競爭性的結果。

圖5 Cora數據集t-SNE下的三維可視化

4 結束語

在本文中，為解決網絡嵌入節點分類不精確，網絡可視化層次結構劃分不清晰等問題，提出了基于二階鄰域基數信息保留策略的改進圖注意力機制模型SNCR-GAT。首先，通過目標節點的二階鄰域來增大局部感受野以獲得更多的網絡結構信息，其次，使用保留基數信息的聚合方式來避免GAT模型訓練中節點信息因權重篩選造成的原始特征丟失問題，以此來生成目標節點新的特征向量表示。最后實驗結果表明，與其它基線算法相比本文所改進方案本文展現了更好的優勢，這對于實際的智能應用是可行的，尤其是在節點分類中模型預測的高精確率更體現了本文方案的優越性以及穩定性。