基于混合圖卷積網絡模型的節點分類方法*

范 敏，范曉波，胥小波，康英來

（中國電子科技網絡信息安全有限公司，四川 成都 610000）

0 引言

近年來，隨著互聯網和大數據的迅猛發展，圖結構成為廣泛應用的數據組織形式。例如，在社交和電商領域，大規模Web 系統產生的社交網絡數據、黑產團伙數據等；在網絡安全領域，各大安全產品可視化Web 界面中的資產關系圖、攻擊向量圖等。在這些圖數據中，節點表示單個用戶或者資產IP 的行為特征，邊表示用戶或者資產IP 之間的互聯關系。同時，雖然深度神經網絡[1]（Deep Neural Networks，DNN）在語音識別、圖像識別等機器學習問題中取得了很好的效果，但對于圖結構這種非歐式數據仍處于早期研究階段，其中語音和圖像分別可以看成是一種具有固定序列（1 維序列）和網格結構（2 維網格）的圖數據[2]。針對任意結構的圖數據，以低維實空間中的向量數據形式表示節點屬性和原始圖結構的機器學習方法就是圖表征學習[3]（Graph Representation Learning，GRL），常應用于節點分類、鏈路預測以及社群發現等任務。圖表征學習可以分為節點嵌入（Node Embedding）和圖神經網絡（Graph Neural Network）兩類方法。

第一類方法，節點嵌入。它以DeepWalk[4]、Node2Vec[5]、Struc2Vec[6]等模型為代表，僅考慮圖的空間結構信息。例如，DeepWalk 通過隨機深度游走的方式得到某個節點的鄰居序列點，以此序列點作為該節點的上下文，然后利用Skip-gram 的思路訓練得到該節點的特征向量。Node2Vec 是在DeepWalk 的隨機深度游走基礎上增加了隨機廣度游走信息序列。Struc2Vec 在保證原始圖的結構信息前提下，通過將原始圖映射為多層的圖結構，然后再進行帶偏置信息的隨機游走得到上下文序列，最后利用Skip-gram方法訓練得到節點的向量表征。此類方法僅僅使用了節點的標簽特征，對節點具有高維附加屬性的問題適用性較差。同時，由于沒有參數共享機制，參數量復雜度為O(|V|)，其中|V|為圖中節點的數量。隨著圖中節點數量的增加，參數量也會線性增加。

第二類方法，圖神經網絡。它以GCN[7]、GAT[8]、fastGCN[9]等模型為代表。它基于神經網絡結構，能有效克服節點嵌入方法無法表達具有高維附加屬性節點的問題，但是圖神經網絡的訓練是一個難點。因為隨著神經網絡層數的增加，訓練圖神經網絡不僅需要克服反向傳播[10]中梯度消失、大量權重矩陣參數帶來的過擬合等神經網絡模型固有的問題，還需要克服圖結構數據中存在的過渡平滑[11]（Over Smoothing）現象。過渡平滑是指應用多個圖卷積層（大于2 層）后節點特征趨于同一向量，導致幾乎無法區分的現象。這種現象最早在GCN 模型中被觀察到[12]，作用類似于低通濾波器[13]。為了解決圖神經網絡中的過渡平滑問題，有兩種典型方法。第一種，改變網絡連接架構。例如：Xu K 等人[14]提出跳躍知識網絡結構（Jump Knowledge Networks，JKN），利用跳躍連接為每個節點單獨選擇近鄰范圍，而不是固定數量的近鄰聚合，從而實現了更好的局部結構注意力表征；Gong S 等人[15]提出幾何原則連接結構（Geometrically Principled Connection，GPC），利用仿射殘差連接改善了傳統殘差連接，進而更加高效地學習到了特定的映射轉化矩陣。第二種，利用正則化技術。例如：Rong Y 等人[16]提出DropEdge 方法對圖中的邊進行隨機Dropout，生成隨機子圖，類似于隨機森林中的Bagging 思路，利用多樣性實現正則化的目的；Zhao L 等人[17]提出PairNorm 方法，將節點特征之間的成對距離進行歸一化；Zhou K 等人[18]提出NodeNorm 方法，將節點均值和方差歸一化，而這些歸一化技術通過阻止隱藏層節點之間或者節點特征之間的相關性學習降低了模型的平滑系數，防止了過度平滑。雖然上述的諸多方法通過各種方法和技巧使得訓練深層的圖神經網絡得以實現，緩解了過度平滑問題，但是通常并不能帶來性能的顯著提升，反而會使模型復雜，降低實際的預測速度。表1 來源于參考文獻[18]的表10～表12，每一類有15 個標簽數據。可以看出，隨著深度的增加，GCN-res（基線）的性能急劇下降，PairNorm和NodeNorm 表現一直良好。但是，深度的增加并沒有帶來模型性能的顯著提升，甚至可能帶來性能下降風險。例如：64 層NodeNorm 在CITESEER 測試數據集精度為67.49%，遜于2 層的GCN-res 的68.68%。

表1 CORA、CITESEER、CoauthorCS 測試數據集AUC

因此，本文從淺層網絡和改變網絡連接架構的角度出發，通過深入分析GCN 模型和GAT 模型的本質特征，結合圖中節點的相鄰相似性、結構相似性以及特征多樣性，基于集成學習（Ensemble Learning）[19]的思路，利用組合式平滑操作增加原始特征的多樣性，提出了混合圖卷積網絡模型（GCN Mixture Model，GCN-MM）。該模型一方面在GCN 模型中引入多個可學習的注意力矩陣，實現了對網絡結構中邊的重要性的刻畫；另一方面，在GAT 模型中引入一階切比雪夫多項式近似的譜圖（Spectral Graph）[20]卷積，實現了對圖網絡結構中先驗知識的保留，這樣在GAT 模型中只需較少的注意力矩陣就能實現和原始GAT 模型相當的精度，同時改善了計算復雜度。

本文具體章節內容安排如下：第1 節深入分析GCN 模型和GAT 模型的本質特征；第2 節基于第1 節的分析，詳細闡述提出的GCN-MM 的網絡結構和數學表達；第3 節是在公共數據集CORA、CITESEER、PUBMED 上進行對比實驗，并分析實驗結果；第4 節總結全文。

1 相關工作分析

一張有n個節點、m條邊的無向無環圖由節點V={v1,v2,…,vn}和邊E={e1,e2,…,em}的集合組成，其鄰接矩陣、度矩陣和正則化的拉普拉斯矩陣分別為：

在譜圖卷積中，圖上的卷積操作需要將拉普拉斯矩陣進行特征分解得到特征值和特征向量，定義如下：

式中，x表示每個節點的標量，U表示拉普拉斯矩陣分解后的特征向量，ψ表示特征值。特征分解屬于計算密集型，復雜度高，導致矩陣分解在實際應用中無法計算。此外，該卷積核是全局的卷積核，參數量隨著圖中節點數增加而增加，因此需要放松約束條件，利用空間采樣或者譜采樣方式近似拉普拉斯矩陣。例如，Donnat 等人[21]提出GraphWave 模型，利用Heat Kernel 來近似g(ψ)。

1.1 GCN 模型

GCN 模型通過引入切比雪夫多項式來近似g(ψ)，避免了矩陣分解，同時使用一階近似也就是局部卷積核，避免了卷積核參數巨大的問題。

切比雪夫多項式定義為：

式中，T1(x)=x，T0(x)=1。

GCN 模型引入一階切比雪夫多項式來近似g(ψ)，從文獻[7]推導得出近似函數：

兩層的圖卷積網絡為：

式中，W表示神經網絡的連接權重，W(1)表示第一層神經網絡的權重，W(2)表示第二層神經網絡的權重，ReLU 和softmax 表示非線性激活函數，A^是單層卷積操作，即：

通過引入一階切比雪夫多項式近似，使得從原先的全局卷積變為現在的局部卷積，即將距離中心節點1 跳的節點作為鄰居節點，如圖1 所示。每一次迭代，GCN 模型通過匯聚鄰居節點1 跳的信息，避免了每次迭代都需要重新計算并更新整個圖的卷積核參數，降低了計算復雜度。

圖1 GCN 模型

將式（8）進行可視化分解以便于理解，其模塊示意圖如圖2 所示，其中H表示神經網絡隱藏層向量。

1.2 GAT 模型

由于GCN模型假設圖中所有的邊重要性一樣，也就是認為節點之間的連接關系重要度一樣，因此在現實場景中是不合理的。文獻[8]提出的GAT 模型通過引入多個注意力矩陣來學習圖中相鄰節點之間的重要性，即針對任意節點xi和節點xj，GAT 模型首先學習它們之間的注意力權重矩陣。注意力矩陣的數學表達為：

圖2 GCN 模塊

式中：LeakyRelu 是非線性激活函數；||代表將節點xi和xj的隱藏層表示進行拼接，然后進行歸一化操作得到注意力權重矩陣，是非對稱矩陣。這種非對稱性對圖中節點的重要性進行了區分。

圖3 GAT 模型

雖然GAT 模型通過學習近鄰節點的權重實現了對近鄰的加權聚合，使得對噪音近鄰較為魯棒，也賦予了注意力機制模型一定的可解釋，但是因為引入了多個注意力權重矩陣也增加了模型的復雜度，導致計算比較耗時。

1.3 混合圖卷積網絡模型

本質上，GCN 模型是從譜域采樣的角度，利用一階切比雪夫多項式采樣來近似圖拉普拉斯矩陣，認為網絡中所有的邊的重要性是一致的，且每次只采樣節點1 跳的近鄰，是一種特殊形式的圖拉普拉斯平滑操作。結合圖2 和圖4 的模塊示意圖對比，多個注意力矩陣通過引入對邊的注意力矩陣來學習相鄰相似性和結構相似性，本質上可以理解為是在近似的圖拉普拉斯矩陣中進行局部重采樣（reweighed）的過程。神經網絡中卷積操作本質上是局部重采樣，而多種不同尺度的卷積核是一種多樣性特征抽取和表達。

2 提出GCN-MM 模型

2.1 GCN-MM 的網絡結構

為了提升GCN 模型預測的準確性，同時提升GAT 模型的收斂速度，本文從淺層網絡和改變網絡連接架構的角度出發，提出了基于混合圖卷積網絡模型（GCN-MM）的節點分類方法，結構如圖5 所示。

圖4 GAT 模塊

圖5 GCN-MM 模型

首先，輸入是一張無向連通圖的一階鄰接矩陣和特征矩陣，輸出是節點的分類標簽結果。其次，混合結構的第一層僅使用2 個注意力矩陣（文獻[8]的原GAT 模型使用了8 個注意力矩陣，2 層），第二層引入一階切比雪夫多項式近似的圖拉普拉斯矩陣和1 個注意力矩陣。最后，將第一層的輸出進行拼接輸入到第二層，而第二層的兩個輸出進行矩陣元素的點和操作作為最后的one-hot 分類結果。

在GCN 模型中，一張無向連通圖被表示為半正定的圖拉普拉斯矩陣，用于對圖的空間結構信息進行數學描述。圖卷積運算是對圖拉普拉斯矩陣進行一階近似。在GAT 模型中，圖信息通過注意力矩陣傳遞給網絡，而注意力矩陣刻畫的是節點和其鄰居節點的重要性關系，不是整張圖。因此，本文提出的混合圖卷積網絡模型結構主要包含GCN 模型中的一階切比雪夫多項式近似的圖拉普拉斯矩陣和GAT 模型中的多個注意力矩陣兩個部分。將以上兩部分進行混合連接，不僅能夠引入全局圖的結構相似性，而且能夠引入局部多樣性表達特征，從而減少模型參數，大幅提升了訓練速度，同時精度不受影響。

2.2 GCN-MM 的數學表達

從GCN-MM 混合模型結構中可以看出，該網絡結構為淺層結構，共有兩層。

第一層的數學表達式為：

式中，LeakyRelu 和elu 表示非線性激活函數。式（11）中，xi表示第i個節點的特征，W(1)表示第一層網絡的權重。式（12）中，表示第一層節點i和節點j之間的重要性系數。式（13）表示將重要性系數歸一化到0～1，形成非對稱注意力系數矩陣。式（14）表示利用兩個注意力系數矩陣對節點i的周圍鄰居j進行拼接運算，得到節點i的第一層隱藏層輸出。

第二層的數學表達式為：

式（18）表示引入一階切比雪夫多項式近似的譜圖卷積，實現了對圖網絡結構中先驗知識的保留。其中：A^ 是單層卷積操作，即式（9）；Wgcn表示GCN 模型學習的權重矩陣。

模型在訓練時采用多分類交叉熵誤差損失函數，公式為：

式中，tik表示樣本i屬于類別k的概率，yik表示模型對樣本i預測為屬于類別k的概率。整個神經網絡使用經典的誤差反向傳播算法（Error Back Propagation）進行訓練。

3 實驗與分析

3.1 公共數據集

CORA、CITESEER 和PUBMED 是3 個文獻引用網絡公共數據集。這3 個數據集的圖結構僅有一個連通分量，且都是直推學習（Transductive Learning）任務，詳細信息如表2 所示。其中，節點數量表示文檔數量，邊數量表示文檔之間的引用鏈接數量，特征數量表示文檔的詞匯特征，類別數量表示文檔的類別，訓練節點數量表示固定的訓練集，驗證節點數量表示固定的驗證集，測試節點數量表示固定的測試集，標簽率表示每個數據集中用于半監督任務訓練的節點占比。另外，數據集中的節點全部都有標簽，因此可以進行監督任務的學習。

表2 數據集介紹

3.2 對比方法

本文將所提出的GCN-MM 混合結構模型在3個公共數據集CORA、CITESEER、PUBMED 上分別進行監督任務和半監督任務的比較實驗。

文獻[7-8]的半監督任務精度評價指標采用AUC（即ROC 曲線下的面積）。文獻[9]提出的FASTGCN 模型通過將圖卷積操作看作在概率度量下的積分變換，采用蒙特卡洛方法估計積分進行訓練。它的監督任務評價指標采用Micro F1 Score（微觀F1 分數）。為了公平比較，本文在對應任務中也采用同樣的評價指標。速度評價指標采用訓練耗時。訓練耗時任務控制實驗在同一臺計算機設備（Intel（R） Xeon（R） CPU E5-2620 v3 @ 2.40GHz）中進行。

3.3 實驗設置

本文提出的混合結構模型分為兩層，輸入是鄰接矩陣A和特征矩陣X，輸出是對節點所屬類別概率的預測。第一層使用兩個可學習的注意力矩陣模塊，每一個矩陣模塊的輸出維度為8，因此進行Concatenate 后第一層的輸出是16 維的特征，后使用指數線性單元[22]（Exponential Linear Unit，ELU）作為非線性激活函數。第二層包括一個一階切比雪夫多項式近似的圖拉普拉斯矩陣和一個可學習的注意力矩陣，輸出的維度是類別個數，同時采用softmax 作為激活函數構建。為了防止過擬合，提高模型的泛化能力，在3 個數據集的實驗中均進行了10-folds 交叉驗證，同時依次采用了停止法（Early stopping）、L2 正則化以及Dropout[23]技術。

以CORA 數據集為例，本文提出GCN-MM 的具體網絡結構如圖6 所示。首先，將構建CORA 數據集的鄰接矩陣和特征矩陣作為輸入，鄰接矩陣的維度是2708，特征矩陣的維度是1433。通過第一層的兩個注意力系數矩陣后，輸出維度為16。將這16 維的特征進行Dropout 層后，分別輸入到第二層的一個注意力系數矩陣和近似的圖拉普拉斯矩陣進行學習映射。最后，將兩個映射輸出的預測結果進行按矩陣元素Add 操作作為最終的預測結果。CORA 數據集共有7 類，因此輸出的是7 維的one-hot 編碼格式的向量。該向量是對目標變量的預測。

圖6 Core 數據集的GCN-MM 結構

3.4 對比結果

對比結果主要分為兩部分，包括CORA 和PUBMED 兩個數據集的監督任務分類精度比較，以及CORA、CITESEER、PUBMED 這3 個數據集的半監督任務分類精度與訓練速度比較。

3.4.1 監督任務

在監督任務上，因為FASTGCN[9]在CORA 和PUBMED 數據集上進行了監督任務實驗，而論文GCN 模型和GAT 模型并沒有進行監督任務的實驗，所以在監督任務上與FASTGCN 中所給的數據進行比較。本文提出的模型監督任務的精度表現如表3所示。從表3 可以看出：在CORA 數據集的監督任務中，提出的模型Micro F1 Score 比原始的GCN 模型增加約1%，比GCN 模型的加速版FASTGCN 模型增加約3%；在PUBMED 數據集的監督任務中，提出的模型Micro F1 Score 比原始的GCN 模型增加約2%，比GCN模型的加速版FASTGCN模型增加約1%。

表3 監督任務微觀F1 分數比較

監督任務整體柱狀圖如圖7 所示。

圖7 監督任務直方圖比較

3.4.2 半監督任務

在半監督任務中，由于文獻[8]給出了GAT 模型在CORA、CITESEER 和PUBMED 這3 個公共數據集中和GCN 模型的對比，因此本文的半監督任務也在3 個數據集中進行對比。各個數據集的半監督任務標簽率如表2 所示，CORA 數據集標簽率是5.2%，CITESEER 數據集標簽率是3.6%，PUBMED數據集標簽率是0.3%。

為了保證實驗公平性，在比較訓練耗時的任務中，迭代次數（Epoch=2000）和停止法（Early stopping=100）兩個參數保持一致，則提出的模型半監督任務的訓練耗時表現如表4 所示，單位是秒，精度AUC 如表5 和圖8 所示。從表4 可以看出，在CORA、CITESEER 和PUBMED 這3 個公共數據集中，提出的模型在模型參數和訓練速度上介于GCN 和GAT 之間。因為GAT 在GCN 基礎上進行了邊的重新采樣，且原始論文中第一層GAT 利用8 個Head，因此模型參數量大、較耗時，而提出的模型只用了2 個Head。

表5 是半監督任務的精度AUC 分數表現對比情況。

表4 半監督任務訓練時間比較/s

表5 半監督任務AUC 比較

為了更清晰地進行對比，可以將表5 形成柱狀圖，如圖8 所示。

結合表4 和圖8 可以看出，GAT 模型訓練耗時大于3 天（259200 s），而提出的模型相比GAT 模型在減少模型參數和訓練耗時的前提下并沒有影響模型的精度。

圖8 半監督任務直方圖比較

4 結語

本文利用GCN 模型的全局特性和GAT 模型的局部特性，結合網絡節點的相鄰相似性、結構相似性以及特征多樣性表達3 個方面，提出了一種混合圖卷積網絡模型。該結構一方面引入GCN 模型中的一階切比雪夫多項式近似的圖拉普拉斯矩陣提高了運算速度，另一方面引入GAT 模型中的多注意力矩陣提高了分類精度，能有效克服純GCN 帶來的精度缺陷和純GAT 模型帶來的速度缺陷，減少可調整參數數量和訓練耗時，同時不影響模型精度。未來，在該框架下，網絡結構的設計還可融合更多的模型，如Graph-SAGE 模型，以提供新的多樣性表達而不必局限于本文所使用的兩種網絡結構，使模型具有更強的擴展性。