雙向數據增強圖卷積網絡

郭新超，張維玉，夏忠秀

(齊魯工業大學(山東省科學院) 計算機科學與技術學院，山東 濟南 250300)

0 引 言

隨著卷積神經網絡的發展，一些學者提出了圖卷積網絡[1，2](GCN)。GCN的發展促進了圖分析在現實世界任務中的應用，例如節點分類[3，4]、圖分類[5，6]、鏈接預測[7-9]和社區檢測[10]等。數據增強已被普遍用于提高機器學習模型的泛化能力，基于圖數據的增強仍然是一個具有挑戰性的問題，因為圖數據比傳統的數據更復雜，它由兩個具有不同屬性的特征組成：圖拓撲結構和節點屬性。

文獻[11，12]提出了增加或消除邊緣的不同策略，以提高GCN的健壯性。然而，這些增強方法僅限于修改圖中具有特征的節點的一部分，增加了用于訓練的數據量，但是這些修改可能會引入許多噪聲或者刪除了關鍵特征。在文獻[13]中提出了節點并行的數據增強方法，為不同的節點建立互不相同的增強空間，但是這種方法摒棄標簽傳播的特性，在標簽數據不足的情況下效果較差。

因此本文在改進自適應多通道圖卷積網絡模型[14]的基礎上提出了雙向數據增強圖卷積網絡(TDA-GCN)，在增強的過程中有效的對關鍵信息進行保護，通過一個圖熵系統計算圖中的信息量，在子圖熵改變最小情況下為區域內的每一個節點設計一個獨立的增強過程，通過兩個卷積模塊來提取相應的嵌入，然后用注意力機制來自動學習不同嵌入的權重，對它們進行自適應的融合，提高了模型的分類精確度。

1 相關工作

1.1 數據增強

數據增強在訓練深度學習模型中扮演著重要的角色，它只對輸入數據進行操作，而不改變模型結構，但顯著提高了性能。現有的數據增強的方法中，如文獻[11]是基于節點采樣的方法，它通過隨機刪除部分節點以及與丟棄節點相連的邊來對子圖進行小批量訓練；文獻[12]的作用類似于一個數據增強器，它以一定的比率從輸入圖中隨機刪除邊，形式上，它隨機強制鄰接矩陣A的一定比率的非零元素為零，從而生成子圖；文獻[15]增加二維形狀數據使用，標準的現成的卷積神經網絡模型訓練與新穎的數據增強技術結合取得了顯著的效果；文獻[16]是一種基于圖特征矩陣的擾動方法，它將某些節點的特征設為零向量；文獻[17]利用遷移學習，使用大規模數據集上的訓練模型的參數來訓練小規模的數據集，可以作為一種特殊的數據增強方法。上述方法雖然達到了增強效果，但是沒有一個相應的評判標準來衡量這種改變邊或節點的增強方法是否改變了關鍵信息。

1.2 標簽傳播

半監督節點分類起源基于圖的半監督學習，它通過探索圖的結構，充分利用有限的標簽數量，用已標記節點的標簽信息去預測未標記節點的標簽信息。通過節點之間的邊傳播標簽，邊上的權重越大，證明兩個節點越相似，所以標簽更容易進行傳播。因此，它們可以表示為最小化目標函數

φ(Y)=12∑i，jωij(yi-yj)2

(1)

式中：ωij是節點vi和vj之間的相似性。

但是，大多數基于圖的半監督學習算法忽略了網絡拓撲或節點特征。當節點特性被忽略時，像標簽傳播這樣的方法只利用網絡上的標簽傳播(拓撲信息)，即ωij=aij， 這是鄰接矩陣中的一個元素。其它方法在相似圖中傳播標簽，該相似圖是在沒有考慮拓撲信息的情況下由節點特征構造的。在相似圖中，ωij=exp(xi-xj22/σ2) 是使用它們的特征計算頂點vi和vj之間的相似性。圖中標簽的傳播過程可以看作是用給定的標記細化圖的結構。

1.3 圖卷積網絡(GCN)

圖神經網絡中的核心操作是鄰域傳播，信息通過某些確定性傳播規則從每個節點傳播到其鄰域。例如，GCN采用傳播規則X(l)=σ(AX(l-1)W(l))， 式中X(l)∈n×d(l)和X(l-1)∈n×d(l-1)是l層的輸出和輸入的節點表示矩陣，A^=- 12A^- 12，是對角節點度矩陣，式中=A+I是添加了自連接的鄰接矩陣，W(l)∈d(l-1)×d(l)是特定層的可訓練權重矩陣，σ是非線性激活函數，如ReLU。文獻[18]對近年來卷積神經網絡的發展進行了一個系統的概述，GCN通過傳播鄰居的表示并在此之后進行非線性變換來學習每個節點的表示。GCN最初應用于半監督分類，式中只有部分節點在圖中具有訓練標簽。通過傳播過程，標記節點的表示攜帶來自其通常未標記的鄰居的信息，因此訓練信號可以傳播到未標記的節點。圖卷積網絡的結構如圖1所示。

圖1 圖卷積神經網絡模型結構

2 方 法

2.1 概 述

本文提出的TDA-GCN方法的模型框架圖如圖2所示，主要分為4個步驟：①將圖分為節點特征圖和拓撲結構圖，其中節點特征圖由節點屬性的k近鄰圖生成；②在節點特征圖和拓撲結構圖上用改進的k-means算法選取一個子圖區域，根據區域內圖熵的變化，對節點特征圖和拓撲結構圖進行增強；③然后將增強后的圖與原來的圖共同作為輸入，通過卷積神經網絡提取不同的嵌入；④提取出的嵌入通過注意力機制進行自適應融合，得到最終的嵌入表示。

圖2 TDA-GCN模型框架

在本文的方法中，圖G=(A，X)， 式中A∈Rn×n是具有n個節點的對稱鄰接矩陣，X∈Rn×n是節點特征矩陣。具體來說，當節點i和j之間存在一條邊時，Aij=1， 否則，Aij=0， 假設圖中的每一個節點屬于一個C類。

2.2 基于圖熵的數據增強

與圖像數據增強[19]不同，圖形數據的非歐幾里得結構導致圖像數據的增強方法不能使用在圖形數據上。本文設計了一種數據增強模式，首先對圖中的節點進行聚類處理，把圖劃分為許多不同的子圖，具體方法是使用Canopy聚類算法對圖上的節點進行一個“粗”聚類，將相似的節點歸納進一個子圖中，經過計算得到若干子圖，各個子圖之間可以是重疊的，但不會存在某個對象不屬于任何子圖的情況，得到子圖的個數k和初始的聚類中心，并根據圖中節點數量去調整k值和聚類中心，然后再使用k-means對子圖進一步“細”聚類，把子圖的劃分標準更加細化，可以把這一階段看作數據增強的預處理。然后對子圖進行隨機的刪除或者增添邊，每次刪除或添加之前都選中一個節點，然后對其添加邊或者刪除相鄰邊，如圖3所示，如果是只有一條邊的節點則不刪除邊，即保證刪除邊后的圖仍為連通圖，得到的子圖稱為副子圖，然后用式(2)來分別計算該節點刪除邊后和添加邊后的副子圖的圖熵，用該子圖初始的圖熵作為評判標準，從副子圖中分別選取圖熵變化最小的副子圖來作為該子圖的增強子圖，然后作為一個增強后的圖

H1(X)=-∑|X|i=1p(xi)logp(xi)

(2)

式中：X是離散系統，-logp(xi) 表示xi∈X的發生概率p(xi) 的自信息，子圖的熵由H1(X) 定義。

為了從副子圖中篩選出想要的子圖，使用圖熵作為評定標準，但是這只體現在子圖上，也就是說是局部最優。用式(2)分別計算圖上的圖熵和增強后的圖的圖熵，以無增強的圖熵作為初始值，然后依次選擇副子圖熵變化最小的增強圖，計算它的圖熵，如式(3)

H2(X)=θH′(X)+(1-θ)H″(X)

(3)

式中：H′(X) 是增強后副子圖的熵，H″(X) 是增強后圖的熵，θ表示權重，以最小圖熵的增強圖作為一個輸入。這樣就得到了局部最優、全局最優的增強圖，它們共同作為數據增強的結果圖來作為輸入，用圖卷積網絡進行提取嵌入表示。

2.3 卷積區域

2.3.1 特定卷積

現有的多數的圖卷積操作遵循鄰域聚合(或消息傳遞)方式，通過傳播其鄰居的表示并在此之后應用轉換來學習節點表示。一般圖的第l層卷積可以描述為

a(l)i=PROPAGATION({x(l-1)i，{x(l-1)j|j∈Ni}})

(4)

x(l)i=TRANSFORMATION(l)(a(l)i)

(5)

式中：x(l)i為節點i在第l層的表示，x(0)i初始化為節點特征xi。 GCN[6]、GIN[20]、GAT[21]等大多數圖卷積都可以在該框架下通過不同的傳播和轉換機制得到。

為了提取節點特征圖里節點的信息，使用節點的特征矩陣X構建了一個k近鄰圖(kNN圖)Gf=(Af，X)， 式中Af是kNN圖的鄰接矩陣。具體來說，首先計算n個節點之間的相似矩陣M∈Rn×n， 選擇使用余弦相似度獲得的相似度矩陣M，然后為每個節點選擇前k個相似節點用來設置邊，最后得到鄰接矩陣Af。 式中xi和xj是節點i和j的特征向量：

余弦相似度

Mij=xi·xj|xi||xj|

(6)

然后，利用特征結構中的輸入圖 (Af，X)， 第l層輸出S(l)f可以表示為

S(l)f=ReLU(- 12ff- 12fS(l-1)fW(l)f)

(7)

式中：W(l)f是GCN第l層的權重矩陣，ReLU是激活函數，初始S(0)f=X，f=Af+If，f是f的對角矩陣，SF是最后一層輸出的嵌入表示。通過以上操作，就可以學習節點嵌入，它在特征結構中捕捉特定信息SF。

對于拓撲結構信息，有原始的輸入圖Gt=(At，Xt)， 式中At=A和Xt=X。 使用與相同的計算方式在拓撲結構上學習嵌入ST， 這樣，就在節點特征圖和拓撲結構圖上提取出特定信息。

2.3.2 通用卷積

特征結構信息和拓撲結構信息具有一定的相關性，節點分類任務可能與特征結構信息或拓撲結構信息以及它們的組合信息相關聯。現在已經提取了特定嵌入，還需提取相應的共同嵌入，通過一個參數共享的通用GCN來提取節點特征圖和拓撲結構圖的共同嵌入。

利用拓撲結構輸入圖G(At，X)， 第l層輸出S(l)ct可以用下所示

S(l)ct=ReLU(- 12ft- 12tS(l-1)ctW(l)c)

(8)

式中：W(l)c是第l層的權重矩陣，S(0)ct=X。 當利用通用卷積從特征圖 (Af，X) 中學習節點嵌入時，為了提取共享信息，為通用卷積的每個層共享相同的權重矩陣W(l)c， 如下所示

S(l)cf=ReLU(- 12ff- 12fS(l-1)cfW(l)c)

(9)

式中：S(l)cf是l層輸出嵌入，S(0)cf=X， 參數共享的權重矩陣可以從兩個結構中篩選出共享特征。根據不同的輸入圖，可以得到兩個輸出嵌入SCT和SCF， 這兩個結構的共同嵌入SC是

SC=λSCT+(1-λ)SCF

(10)

式中：SCT是通用卷積拓撲結構信息的嵌入表示，SCF是通用卷積特征結構信息的嵌入表示，λ參數表示權重。

2.4 注意力機制

通過以上的卷積操作，從節點特征圖和拓撲結構圖上提取出特定嵌入ST和SF以及共同的嵌入SC， 為了得到更精確的預測結果，通過注意力機制att來學習它們的重要性，相關的公式表示如下所示

(αt，αc，αf)=att(ST，SC，SF)

(11)

式中：(αt，αc，αf)∈n×1分別表示嵌入ST、SC、SF的n個節點的注意值。

對于變量i，ST的第i行的嵌入表示為SiT∈1×h， 首先對ST的第i行的嵌入進行非線性變換，然后通過激活函數與一個共享的注意向量q∈h′×1的轉置得到最后的注意值ωiT如下

ωiT=qT·tanh(W·(SiT)+b)

(12)

式中：W∈h′×h是權重矩陣，b∈h′×1是偏差向量。同樣地，可以使用式(12)獲得SC和SF中節點i的注意值ωiC和ωiF。 然后，使用softmax函數對注意值ωiT，ωiC，ωiF進行歸一化，以獲得最終權重

αiT=softmax(ωiT)=exp(ωiT)exp(ωiT)+exp(ωiC)+exp(ωiF)

(13)

式(13)中較大的αiT意味著相應的嵌入更重要。同樣求出αiC=softmax(ωiC)，αiF=softmax(ωiF) 的值。對訓練集上的n個節點，通過式(13)已經得到權重αt=[αiT]，αc=[αiC]，αf=[αiF]∈n×1， 表示αT=diag(αT)，αC=diag(αC)，αF=diag(αF)。 把以上3種權重和嵌入結合，得到最終的嵌入S

S=αT·ST+αC·SC+αF·SF

(14)

2.5 目標函數

把式(14)中的輸出嵌入S用于半監督分類，包括線性映射分類和柔性最大值激活函數分類。用Y^=[ic]∈n×C表示n個節點的類別預測，ic是節點i屬于類別C的概率。然后Y^可以用以下方式計算

Y^=softmax(W·S+b)

(15)

式中：softmax(x)=exp(x)/∑Cc=1exp(xc) 就是所有類的規格化公式。

假設訓練集是L，對于每個l∈L， 真實標簽是Yl， 預測標簽是Y^l。 在所有的訓練集數據上，節點分類的交叉熵損失表示為ηt式中

ηt=-∑l∈L∑Ci=1YlilnY^li

(16)

結合式(2)、式(3)，確定最終的目標函數為

η=ηt+βH(X)

(17)

式中：β是圖熵的超參數，H(X) 不同情況下分別表示H1(X) 或者H2(X)， 在標記數據的指導下，通過反向傳播對模型進行優化，學習節點嵌入分類。

3 實 驗

3.1 實驗數據集

數據集的具體信息見表1。

表1 數據集的統計數據

Citeseer：Citeseer是一個研究論文引用網絡，節點是出版物，邊是引用鏈接。節點屬性是論文的單詞包表示，所有節點分為6個區域。

BlogCatalog：它是一個社交網絡，博主和他們的社交關系來自BlogCatalog網站。節點屬性由用戶檔案的關鍵詞構造，標簽代表作者提供的主題類別，所有節點分為6類。

Flickr：Flickr是一個圖片和視頻托管網站，用戶通過照片和視頻的分享進行互動。它是一個節點代表用戶，邊代表其關系的社交網絡，所有的節點按照用戶的興趣群體分為9類。

3.2 實驗設置

操作系統：Ubuntu 16.04。軟件版本：Python 3.7，Pytorch1.1.0，GPU：GTX 1080，CPU：inter Xeon E5-2679 v4@2.50GHz。使用每類20標簽、40個標簽、60個標簽節點的訓練集進行訓練，使用10 000個節點用來進行測試，以獲得魯棒性更好的模型。這里的L/C是每個類的標記節點的數量，ACC是準確性，F1是F1宏觀評分。表2中是本文模型具體的參數值。

表2 模型參數值

3.3 對比方法

將本文的方法與現有方法進行了比較，其中包含網絡嵌入算法和基于圖神經網絡的方法。具體方法有以下：

GCN[2]是一個半監督圖卷積網絡模型，它通過聚集來自鄰居的信息來學習節點表示。

kNN-GCN為了對比，用特征矩陣計算出的稀疏k-近鄰圖代替傳統的拓撲圖作為GCN的輸入圖，表示為kNN-GCN。

GAT[21]是一種利用注意機制聚集節點特征的圖神經網絡模型。

MixHop[22]是一種基于GCN的方法，它將高階鄰居的特征表示混合在一個圖形卷積層中。

3.4 結果與分析

3.4.1 不同方法的實驗結果對比

本文對比了不同模型節點分類精確度的結果，見表3、表4。表3列出了準確性下(ACC)的對比結果，表4列出了宏觀評分(F1)下的對比結果。從圖中可以看出，GCN在3個數據集上的分類精確度都不是最優，在Citeseer數據集上不如GAT，其余數據集上不如kNN-GCN，但是經過增強后的GCN在3個數據集上都有不同程度的提升，并且超過了上述模型，驗證了數據增強方法的有效性。

表3 實驗結果(F1)

表4 實驗結果(ACC)

TDA-GCN在最終結果上優于GCN和kNN-GCN，說明TDA-GCN可以從原始圖中提取更多的有用信息，包括在拓撲結構和節點屬性信息，并通過注意力機制對這些信息進行有效利用，也驗證了注意力機制的有效性。

本文提出的TDA-GCN在所有的數據集中取得了最好的效果，準確性上，在BlogCatalog數據集上最大的提升效果達到了6.81%，在Flickr數據集上最大的提升效果達到了7.02%，在Citeseer數據集上提升了2.26%的效果，相比于對比方法，本文方法的提升效果較為明顯，也驗證了本文方法的有效性。

3.4.2 訓練次數分析

在圖4、圖5展示了BlogCatalog與Citeseer數據集在不同數量標簽下的迭代次數與分類精確度的訓練曲線圖，在前15次的迭代訓練中，所有曲線有一個快速的增長，隨著訓練次數的增加，所有曲線都趨于平穩，但是增強后的模型在整體上占有優勢。20標簽的曲線在3條增強曲線中處于最低的水平，并與其它兩條曲線相差較大，這說明了標簽數量對分類精確度的影響。但是，分析發現40標簽和60標簽曲線相差較小，這說明隨著訓練次數和標簽數量的增加，標簽數量的對結果的影響在縮小。

圖4 BlogCatalog數據集的訓練曲線

圖5 Citeseer數據集的訓練曲線

3.4.3 TDA-GCN與其變體對比分析

如圖6所示，在這部分比較了TDA-GCN與其變體在3個數據集上的表現，以驗證增強方法的有效性。

圖6 TDA-GCN與其變體在3個數據集上的結果

(1)TDA-GCN-Og：只用全局最優的增強圖；

(2)TDA-GCN-Sg：只用局部最優的增強圖。

從圖中的結果可以得出：在所有的數據集上，①TDA-GCN-Sg在所有數據集的增強效果不如TDA-GCN-Og，說明局部最優的增強效果過于單一，局部最優增強圖在圖中的權重占比較小；②TDA-GCN優于TDA-GCN-Og，但是差距不大，說明全局最優的增強圖已經接近最好的增強效果，在增強過程中全局最優增強占比較大；③TDA-GCN-Sg在所有數據集上優于GCN，說明了本文增強方法的有效性。

4 結束語

本文針對數據不足帶來的深度學習模型泛化性能較差問題，提出了雙向數據增強圖卷積網絡(TDA-GCN)，通過子圖增強法以及圖熵選取的子圖進行數據增強，不僅提取圖的節點屬性信息，而且也考慮拓撲結構上的信息，分別提取相應的嵌入表示，通過注意力機制融合生成最終的嵌入表示。這對訓練出來的圖卷積網絡魯棒性有一個顯著的提升，在3個數據集也取得了最好的結果。未來我們的工作會致力于節點屬性的數據增強，更好的節點屬性會有助于最終的分類工作。