薛暉，孫偉祥

（1.東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 211189；2.計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室（東南大學(xué)），江蘇 南京 211189）

圖數(shù)據(jù)（Graph-Structured Data）作為一類用于描述實(shí)體（點(diǎn)）及實(shí)體之間關(guān)系（邊）的非歐氏數(shù)據(jù)（Non-Euclidean Data），廣泛存在于知識(shí)圖譜[1]、社交網(wǎng)絡(luò)[2]、計(jì)算機(jī)視覺[3]以及生物化學(xué)[4]等眾多交叉學(xué)科領(lǐng)域.圖數(shù)據(jù)的諸多復(fù)雜特性，例如結(jié)點(diǎn)的無序性與規(guī)?？勺冃?，給現(xiàn)有的機(jī)器學(xué)習(xí)算法帶來了巨大的挑戰(zhàn).幸運(yùn)的是，近年來，隨著深度學(xué)習(xí)和圖表示學(xué)習(xí)的興起，DeepWalk[5]、Node2Vec[6]以及圖卷積神經(jīng)網(wǎng)絡(luò)等算法[7]相繼被提出.特別是圖卷積神經(jīng)網(wǎng)絡(luò)算法，能夠?qū)D數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)特征和結(jié)點(diǎn)屬性高效地融合，從而學(xué)習(xí)得到高質(zhì)量的圖結(jié)點(diǎn)嵌入表示（Node Embeddings），使得機(jī)器學(xué)習(xí)算法對(duì)于復(fù)雜圖數(shù)據(jù)的分析和挖掘能力得到了顯著提升.目前，圖卷積神經(jīng)網(wǎng)絡(luò)算法已經(jīng)成為機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)之一.

圖分類（Graph Classification）作為一類重要的圖挖掘任務(wù)，旨在對(duì)不同類型的圖數(shù)據(jù)進(jìn)行分類預(yù)測(cè).與結(jié)點(diǎn)分類（Node Classification）等任務(wù)不同，圖分類預(yù)測(cè)的對(duì)象為整個(gè)的圖數(shù)據(jù).因此，當(dāng)圖神經(jīng)網(wǎng)絡(luò)被應(yīng)用于該任務(wù)時(shí)，需要對(duì)學(xué)習(xí)得到的結(jié)點(diǎn)嵌入向量進(jìn)行整合轉(zhuǎn)化，生成圖級(jí)別的表示向量（Graph-Level Representation）后才能用于后續(xù)的分類網(wǎng)絡(luò)[8-9].然而，在結(jié)點(diǎn)嵌入整合轉(zhuǎn)化生成圖表示向量的過程中，存在著以下三個(gè)難點(diǎn)：1）不同圖之間結(jié)點(diǎn)規(guī)模可能存在較大的差異，但整合轉(zhuǎn)化后得到圖表示向量維度大小必須統(tǒng)一；2）圖結(jié)點(diǎn)的順序是排列無關(guān)且無意義的，但整合轉(zhuǎn)化后得到圖表示向量的特征順序必須是有意義的；3）圖數(shù)據(jù)作為一種信息密集型數(shù)據(jù)，每個(gè)結(jié)點(diǎn)都可能代表著一個(gè)重要實(shí)體，因此結(jié)點(diǎn)嵌入中所蘊(yùn)含的結(jié)構(gòu)特征等信息應(yīng)當(dāng)在圖表示向量中盡可能保留.更具體地來講，前兩個(gè)難點(diǎn)主要是目前大多數(shù)分類算法對(duì)于輸入數(shù)據(jù)的特定要求所致，如感知機(jī)和神經(jīng)網(wǎng)絡(luò)等常用分類器，均要求輸入數(shù)據(jù)的特征尺寸大小必須固定，此外，這些分類器往往不具有處理數(shù)據(jù)特征排列不變性的能力，即它們對(duì)于輸入數(shù)據(jù)的特征排列順序有一定的要求.例如，對(duì)于圖像分類任務(wù)，當(dāng)圖像的特征順序，即像素順序被打亂后，分類器很可能無法對(duì)該圖像進(jìn)行正確分類.因此，具有明確意義的數(shù)據(jù)特征順序?qū)τ诜诸惼鞫杂兄陵P(guān)重要的意義.

對(duì)于圖分類任務(wù)而言，一個(gè)理想的特征順序應(yīng)當(dāng)是全局對(duì)齊的.即數(shù)據(jù)的每個(gè)特征維度都應(yīng)該對(duì)應(yīng)著特定的含義.這一想法是受圖像分類任務(wù)的啟發(fā)——該領(lǐng)域的研究者通常采用圖像切割和旋轉(zhuǎn)操作進(jìn)行數(shù)據(jù)增強(qiáng)[10]，以此期望模型學(xué)習(xí)得到一些不變性，例如平移不變性和旋轉(zhuǎn)不變性，以增強(qiáng)模型對(duì)于目標(biāo)物體的辨別（分類）能力.究其本質(zhì)，其需要數(shù)據(jù)增強(qiáng)的根本原因在于其目標(biāo)特征沒有全局對(duì)齊，導(dǎo)致存在特征平移和旋轉(zhuǎn)等現(xiàn)象.若假設(shè)目標(biāo)物體特征是全局對(duì)齊的，則這些不變性將沒有學(xué)習(xí)的必要，這會(huì)大大降低目標(biāo)檢測(cè)難度.同樣地，在圖分類任務(wù)中，特征不對(duì)齊的圖表示向量也勢(shì)必會(huì)引入特征平移和旋轉(zhuǎn)等問題，這將對(duì)下游的分類網(wǎng)絡(luò)提出更高的要求.例如，若分類網(wǎng)絡(luò)不具備對(duì)于特征平移不變性和排列不變性的良好學(xué)習(xí)能力，那么兩個(gè)相似圖結(jié)構(gòu)很可能會(huì)被誤認(rèn)為有較大的差異，從而產(chǎn)生分類誤判.

面對(duì)這些難點(diǎn)，一部分應(yīng)用于圖分類的網(wǎng)絡(luò)模型選擇犧牲掉圖表示向量的信息豐富度，通過簡(jiǎn)單地將所有結(jié)點(diǎn)嵌入進(jìn)行聚合壓縮（求和或平均）的方式，來保證所輸出圖表示向量的尺寸大小固定，以及避免特征順序的困擾[9，11-12].此外，還有一些模型對(duì)結(jié)點(diǎn)嵌入向量通過給定的規(guī)則排序后，固定地取前k個(gè)，然后將其拼接得到圖表示向量[13].此類方法可以通過調(diào)節(jié)超參數(shù)k 使得特征信息丟失減少，但是其得到的圖表示向量的特征順序僅是局部對(duì)齊的，無法避免特征平移等現(xiàn)象，且后續(xù)的分類網(wǎng)絡(luò)并不能保證完全學(xué)習(xí)到這些不變性.對(duì)于該方法而言，整體模型的分類性能將受到分類網(wǎng)絡(luò)對(duì)于平移不變性學(xué)習(xí)的嚴(yán)重制約.

為了避免現(xiàn)有模型的這些缺陷，本文提出了一個(gè)新穎的圖神經(jīng)網(wǎng)絡(luò)模型，即全局對(duì)齊圖卷積網(wǎng)絡(luò)（Globally Aligned Graph Convolutional Network，GAGCN），用于圖分類任務(wù).GAGCN 通過新穎的全局對(duì)齊層（Globally-Aligned Layer）的設(shè)計(jì)，使得模型能夠?qū)W習(xí)到全局特征語義對(duì)齊，且具有豐富結(jié)構(gòu)信息的圖表示向量，以此提高模型對(duì)圖分類任務(wù)的分類精度.具體地，GAGCN 對(duì)于圖分類任務(wù)的處理主要包含以下3 個(gè)步驟：1）圖卷積網(wǎng)絡(luò)學(xué)習(xí)得到圖數(shù)據(jù)的結(jié)點(diǎn)嵌入向量；2）通過對(duì)結(jié)點(diǎn)嵌入空間做切片，得到子圖（Subgraph）特征的近似分布，并以此生成特征順序全局對(duì)齊的圖表示向量；3）將圖表示向量送入分類網(wǎng)絡(luò)進(jìn)行分類預(yù)測(cè).在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，GAGCN 在圖分類任務(wù)上的表現(xiàn)要優(yōu)于各類比較算法，進(jìn)一步的消融實(shí)驗(yàn)和敏感性分析實(shí)驗(yàn)也驗(yàn)證了GAGCN 全局對(duì)齊策略的有效性以及魯棒性.

1 相關(guān)工作

1.1 圖核（Graph Kernel）

GAGCN 的主要思想是受兩類圖核方法所啟發(fā)，即WL-Subtree Kernel 算法[14]以及Graphlet Kernel算法[15].其中，WL-Subtree Kernel 通過Weisfeiler -Lehman 算法得到圖中以每個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹的特征集合后，通過比較兩個(gè)圖中子樹結(jié)構(gòu)特征的分布，計(jì)算得到兩個(gè)圖之間相似度.而Graphlet Kernel 算法則通過比較兩個(gè)圖數(shù)據(jù)的圖元分布來計(jì)算它們之間的相似性.受這兩個(gè)工作的啟發(fā)，本文提出通過構(gòu)造子圖特征的近似分布來對(duì)齊圖表示向量的特征順序，從而使得模型能夠更輕易地學(xué)習(xí)和衡量不同圖數(shù)據(jù)之間的相似性以及差異性.但與這兩個(gè)方法不同的是，GAGCN 是基于圖神經(jīng)網(wǎng)絡(luò)搭建的圖分類模型，因此具有更強(qiáng)的特征抽象能力和更高的可擴(kuò)展性.

1.2 圖卷積神經(jīng)網(wǎng)絡(luò)

受傳統(tǒng)卷積神經(jīng)網(wǎng)絡(luò)在圖像處理領(lǐng)域獲得巨大成功的激勵(lì)，許多研究者嘗試將卷積網(wǎng)絡(luò)引入圖領(lǐng)域，并提出了眾多圖卷積神經(jīng)網(wǎng)絡(luò)模型[16-19].總體來說，這些模型可以分為基于頻譜（Spectral-Based）的方法和基于空間（Spatial-Based）的方法兩大類.Xu等人[9]為大多數(shù)現(xiàn)有的圖神經(jīng)網(wǎng)絡(luò)抽象出了一個(gè)統(tǒng)一的架構(gòu).在該架構(gòu)中，第k 層圖卷積被描述為：

2 全局對(duì)齊圖卷積網(wǎng)絡(luò)

本文提出的全局對(duì)齊圖卷積網(wǎng)絡(luò)（GAGCN）遵循三段式架構(gòu)：首先，圖卷積層得到結(jié)點(diǎn)嵌入向量；其次，全局對(duì)齊層生成圖表示向量；最后，由分類網(wǎng)絡(luò)進(jìn)行分類預(yù)測(cè).

2.1 符號(hào)定義

關(guān)鍵符號(hào)及其含義如表1 所示.此外，本文還約定X∈Rn×d，其中矩陣X 第u 個(gè)行向量表示結(jié)點(diǎn)u的屬性表示第k 層圖卷積輸出的結(jié)點(diǎn)u 的嵌入向量，且向量維度為ck.Zk∈Rn×ck表示第k 層圖卷積網(wǎng)絡(luò)輸出的圖G 所有結(jié)點(diǎn)嵌入向量構(gòu)成的結(jié)點(diǎn)嵌入矩陣.

表1 關(guān)鍵符號(hào)定義Tab.1 Definition of key notations

2.2 圖卷積神經(jīng)層

GAGCN 定義新的圖卷積算法如下：

GAGCN 通過堆疊加深圖卷積層來提高模型對(duì)結(jié)點(diǎn)嵌入向量的學(xué)習(xí)能力.但值得注意的是，與傳統(tǒng)卷積神經(jīng)網(wǎng)絡(luò)模型類似，隨著卷積層數(shù)加深，每一個(gè)神經(jīng)單元的感受野也會(huì)不斷擴(kuò)增，故不同圖卷積層得到的結(jié)點(diǎn)嵌入實(shí)際上蘊(yùn)含結(jié)點(diǎn)周圍不同規(guī)模的子圖特征信息，即第一層得到一階鄰域子圖特征，第二層得到二階鄰域子圖特征等等，以此類推.然而，堆疊深度過深會(huì)使得深層卷積層所學(xué)習(xí)的所有結(jié)點(diǎn)嵌入向量產(chǎn)生趨同性，該現(xiàn)象被稱之為過渡平滑（Over－Smoothing）[7].因此，不宜采用過深的網(wǎng)絡(luò)結(jié)構(gòu)來學(xué)習(xí)結(jié)點(diǎn)嵌入表示.同時(shí)，這一點(diǎn)也表明，對(duì)于圖分類任務(wù)而言，需要綜合考慮各層的結(jié)點(diǎn)嵌入輸出，才能多方位地衡量圖數(shù)據(jù)中各個(gè)領(lǐng)域規(guī)模的子圖特征信息，以提高模型對(duì)圖數(shù)據(jù)整體的學(xué)習(xí)能力.

進(jìn)一步分析，圖卷積網(wǎng)絡(luò)作為Weisfeiler－Lehman 算法的一個(gè)“軟版本”（Soft Version）[13，24]，其學(xué)習(xí)得到的結(jié)點(diǎn)嵌入向量可以被認(rèn)為是“連續(xù)的色彩”（Continuous Color），而“色彩”在Weisfeiler－Lehman算法中被用來表示不同的子圖特征.因此，圖卷積層學(xué)習(xí)得到的結(jié)點(diǎn)嵌入本質(zhì)上也可以被看作是一種子圖特征的連續(xù)向量表示形式.此外，文獻(xiàn)[13]指出，圖卷積網(wǎng)絡(luò)可以將相似的結(jié)構(gòu)特征嵌入至距離相近的向量中進(jìn)行表達(dá).基于以上兩點(diǎn)，可以得到一個(gè)基本的論斷，即通過圖卷積網(wǎng)絡(luò)學(xué)習(xí)得到的距離相近的結(jié)點(diǎn)嵌入向量蘊(yùn)含著相似的子圖結(jié)構(gòu)信息.為進(jìn)一步驗(yàn)證本小節(jié)提出的圖卷積網(wǎng)絡(luò)是否符合該論斷，本文在Cora 和Citeseer 兩個(gè)常用的結(jié)點(diǎn)分類數(shù)據(jù)集上進(jìn)行了驗(yàn)證.該驗(yàn)證建立在這樣一個(gè)合理假設(shè)的基礎(chǔ)上，即兩個(gè)帶有相同標(biāo)簽的結(jié)點(diǎn)，其鄰域結(jié)點(diǎn)構(gòu)成的子圖的相似性，要大于兩個(gè)帶有不同標(biāo)簽的結(jié)點(diǎn).結(jié)點(diǎn)嵌入可視化結(jié)果如圖1 所示，圖中每個(gè)點(diǎn)代表一個(gè)結(jié)點(diǎn)嵌入，不同的橫坐標(biāo)代表不同的結(jié)點(diǎn)標(biāo)簽.從圖中可以清晰地看到，即使是將結(jié)點(diǎn)嵌入維度壓縮到了一維，帶有相同標(biāo)簽的結(jié)點(diǎn)嵌入仍然表現(xiàn)出了強(qiáng)聚類特征.因此，可以認(rèn)為本節(jié)提出的圖卷積網(wǎng)絡(luò)符合結(jié)點(diǎn)鄰域結(jié)構(gòu)越相似，學(xué)習(xí)得到的結(jié)點(diǎn)嵌入表示距離越相近這一特性.

圖1 一維結(jié)點(diǎn)嵌入可視化Fig.1 Visualization of node embeddings with 1－dimension

2.3 全局對(duì)齊層

圖卷積網(wǎng)絡(luò)得到結(jié)點(diǎn)嵌入表示向量后需要整合轉(zhuǎn)化為整個(gè)圖的向量表示，才能交由分類網(wǎng)絡(luò)進(jìn)行分類.前文提及了該過程的幾個(gè)難點(diǎn)所在，即如何保證圖表示向量在維度大小固定以及特征順序有意的前提下，盡可能地保留更多的結(jié)構(gòu)信息.為了解決這些問題，本文提出了全局對(duì)齊層（Globally－Aligned Layer），其通過構(gòu)建子圖特征的近似分布來全局對(duì)齊表示特征的語義，能夠有效地提高圖神經(jīng)網(wǎng)絡(luò)方法在圖分類任務(wù)上的性能.本小節(jié)將詳細(xì)介紹Globally－Aligned Layer 的原理與定義.

首先假定，在Globally－Aligned Layer 中能夠定義U∈Rk×r，其中U 的每一個(gè)行向量Ui表示特定類型子圖的特征，則U 能夠滿足特征全局對(duì)齊性的同時(shí)，還能夠反應(yīng)出子圖特征的分布信息.為了做到這一點(diǎn)，需要確切地給出Ui的具體定義.在2.2 節(jié)的討論中，可以發(fā)現(xiàn)式（1）與式（2）所定義的圖卷積網(wǎng)絡(luò)學(xué)習(xí)到的結(jié)點(diǎn)嵌入向量，實(shí)際上表示的是子圖的特征，且滿足距離越相近，所蘊(yùn)含的子圖信息越相似的性質(zhì).因此，可以通過統(tǒng)計(jì)結(jié)點(diǎn)嵌入向量的分布來間接統(tǒng)計(jì)子圖特征的近似分布.更具體地，通過將結(jié)點(diǎn)嵌入的表示空間 切分為κ 個(gè)不相交的空間切片，組成空間片段集合P，即P=P1∪P2…∪Pκ，且?i，j，Pi∪Pj=?.假設(shè)Pi內(nèi)的結(jié)點(diǎn)嵌入表示向量之間的距離較近，則這些向量可以被認(rèn)為表達(dá)的是一類相似的子圖結(jié)構(gòu).因此，若將Pi與Ui做一一對(duì)應(yīng)，則任意的Ui都將對(duì)應(yīng)一類子圖特征.通過這樣的定義，U 中每一個(gè)特征的語義都將是確切且對(duì)齊的.然而，如何對(duì)高維空間 進(jìn)行合理切分是一個(gè)較為困難的工作.受DGCNN 工作的啟發(fā)[13]，首先，Globally-Aligned Layer將最后一層圖卷積神經(jīng)網(wǎng)絡(luò)的通道數(shù)設(shè)為1，但與DGCNN 不同的是，Globally-Aligned Layer 還將最后一層卷積神經(jīng)網(wǎng)絡(luò)的輸入設(shè)置為所有前層結(jié)點(diǎn)嵌入向量的拼接，意義在于能夠結(jié)合多階鄰域信息進(jìn)行多層次的子圖信息綜合推斷.接著，將該層得到的結(jié)點(diǎn)嵌入通過值域有上下界的激活函數(shù)，例如tanh 等，進(jìn)行非線性激活，則其表示空間可以用[a，b]一維區(qū)間進(jìn)行表示，其中a 和b 分別為激活函數(shù)值域的上下界.最后，僅需對(duì)激活后的嵌入向量取值空間進(jìn)行簡(jiǎn)單的切分統(tǒng)計(jì)，得到結(jié)點(diǎn)嵌入的近似分布.最簡(jiǎn)單地，本文將該空間均勻切分為κ 段，第i 段用來表示Pi，且Ui被定義為：

從而得到U=[U1，U2，…，Uκ]T.此處ψ（·）表示將屬于Pi的所有結(jié)點(diǎn)嵌入進(jìn)行聚合.由于Pi內(nèi)的結(jié)點(diǎn)嵌入距離相近，故其所表達(dá)的子圖特征具有相似性，因此此處的聚合不會(huì)因?yàn)閴嚎s而造成特征信息的過度損失.

進(jìn)一步，為了將所有共l 層圖卷積網(wǎng)絡(luò)所習(xí)得的結(jié)點(diǎn)嵌入充分利用，對(duì)于?u∈V，定義

式中：hu表示將所有圖卷積層的輸出拼接.式（3）重寫為：

重寫后U∈Rk×r，其中為了增加圖表示向量的伸縮性，控制表示向量的維度，Globally-Aligned Layer 采用一個(gè)可學(xué)習(xí)的線性變換矩陣Ws∈Rr×m（m ＜r）來做最后的變換，得到最終的圖表示向量：

f（·）函數(shù)的意義為將輸入矩陣?yán)鞛橄蛄啃问?式（6）還可以被等價(jià)地看作對(duì)U 逐行做卷積核為1、步長(zhǎng)為1 且通道數(shù)為m 的一維卷積，故其不僅可以伸縮圖表示向量維度，還能夠起到歸納整合U 中每個(gè)行向量Ui所蘊(yùn)含的結(jié)構(gòu)特征信息的作用.

進(jìn)一步分析，根據(jù)R-Convolution 理論[25]，兩個(gè)圖之間的相似度被定義為：

式中：S 和S′分別為G 和G′的子圖結(jié)構(gòu)集合；δ（s·s′）=1 當(dāng)且僅當(dāng)s 和s′同構(gòu)或近似同構(gòu)，否則δ（s·s′）=0.該理論說明，通過對(duì)比兩個(gè)圖數(shù)據(jù)的子圖分布，可以計(jì)算得到它們近似同構(gòu)的子圖對(duì)數(shù)，進(jìn)而推斷出圖數(shù)據(jù)之間的相似性.事實(shí)上，許多圖分類算法都是基于該原理[14-15].因此，Globally-Aligned Layer 生成的圖表示向量所蘊(yùn)含的子圖特征分布信息，有助于模型挖掘圖數(shù)據(jù)之間內(nèi)在的結(jié)構(gòu)相似性，能夠以此對(duì)圖數(shù)據(jù)進(jìn)行更為合理的分類推斷.

2.4 分類網(wǎng)絡(luò)與損失函數(shù)

為了說明GAGCN 生成的圖表示向量不存在特征平移，且蘊(yùn)含信息易被挖掘，故GAGCN 采用單隱藏層的簡(jiǎn)單全連接網(wǎng)絡(luò)作為分類器.最后，SoftMax和交叉熵（Cross-Entropy）被用來計(jì)算分類損失.

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

本節(jié)共包含3 個(gè)實(shí)驗(yàn)：1）基準(zhǔn)實(shí)驗(yàn)通過將GAGCN 與多個(gè)主流圖分類算法在7 個(gè)常用圖數(shù)據(jù)集上進(jìn)行比較，來評(píng)價(jià)GAGCN 模型在圖分類任務(wù)上的整體表現(xiàn)；2）消融實(shí)驗(yàn)通過對(duì)全局對(duì)齊層的消融替換，來證明全局對(duì)齊層策略的有效性；3）參數(shù)敏感性分析實(shí)驗(yàn)用來進(jìn)一步驗(yàn)證GAGCN 的魯棒性.

本節(jié)所涉及的所有實(shí)驗(yàn)均基于Ubuntu Linux 16.04 操作系統(tǒng)，GAGCN 源碼使用PyTorch 和PyTorch-Geometric[26]學(xué)習(xí)框架實(shí)現(xiàn)，程序運(yùn)行時(shí)的硬件環(huán)境為i7-8700K CPU、32GB RAM 以及TITAN RTX GPU.

3.1 基準(zhǔn)實(shí)驗(yàn)

數(shù)據(jù)集.該實(shí)驗(yàn)共采用7 個(gè)常用圖分類數(shù)據(jù)集，涵蓋了生物、化學(xué)以及社交網(wǎng)絡(luò)三個(gè)研究領(lǐng)域：在PROTENS、DD 以及ENZYMES 這3 個(gè)數(shù)據(jù)集中，每個(gè)樣例都代表一個(gè)蛋白質(zhì)分子或酶分子；NCI-1 中不同樣例代表了不同的化學(xué)分子結(jié)構(gòu)；IMDB-B、IMDB-M 以及REDDIT-MULTI-12K（下文簡(jiǎn)寫為RED-M12K）則是由社交或關(guān)系網(wǎng)絡(luò)組成的圖數(shù)據(jù)集合.其中，生物、化學(xué)領(lǐng)域的4 個(gè)數(shù)據(jù)集中每個(gè)圖結(jié)點(diǎn)都帶有屬性；而社交網(wǎng)絡(luò)的3 個(gè)數(shù)據(jù)集則不帶有結(jié)點(diǎn)屬性，為了實(shí)驗(yàn)比較的公平性，GAGCN 參照其他對(duì)比算法，將結(jié)點(diǎn)的度數(shù)作為其屬性.數(shù)據(jù)集相關(guān)的其他幾個(gè)關(guān)鍵參數(shù)在表2 中有詳細(xì)的量化說明.

比對(duì)算法.該實(shí)驗(yàn)選取的對(duì)比算法包括2 個(gè)與GAGCN 相關(guān)的Graph Kernel 算法，以及5 個(gè)主流的基于深度學(xué)習(xí)的圖分類算法.具體介紹如下.

Graph Kernel 對(duì)比算法：即前文提及的WLSubtree Kernel 以及Graphlet Kernel 兩個(gè)算法.當(dāng)計(jì)算得到核矩陣之后，實(shí)驗(yàn)采用軟間隔支持向量機(jī)（CSVM）[27]對(duì)其進(jìn)行分類.該實(shí)驗(yàn)選取這2 個(gè)Graph Kernel 算法作為對(duì)比，主要是考慮到其與GAGCN 理論上的相似性，故存在比較的意義和價(jià)值.

基于深度學(xué)習(xí)的對(duì)比算法：

1）DGK[28][KDD，2015]，即Deep Graph Kernel.該方法通過CBOW 以及Skip-Gram 等模型學(xué)習(xí)得到子圖結(jié)構(gòu)之間的依賴性，從而提高經(jīng)典Graph Kernel 的分類性能.

2）DGCNN[13][AAAI，2018].該模型提出了Sort-Pooling 層，將結(jié)點(diǎn)嵌入按照其表示的子結(jié)構(gòu)來進(jìn)行排序，從而得到局部對(duì)齊的圖表示，最后通過卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行分類.

3）DiffPool[29][NeurIPS，2018].該算法實(shí)現(xiàn)了一個(gè)可微分的圖池化方法，幫助圖神經(jīng)網(wǎng)絡(luò)模型更好地處理圖分類任務(wù).

4）GIN[9][ICLR，2019].該模型主要探究了不同的圖卷積聚合算子對(duì)圖分類任務(wù)的影響.表2 中GIN-0 和GIN-?為GIN 模型的不同的實(shí)現(xiàn).

表2 基準(zhǔn)實(shí)驗(yàn)分類精度比較結(jié)果Tab.2 Comparison results of accuracies on the benchmark experiment %

5）CapsGNN[30][ICLR，2019].該算法將膠囊網(wǎng)絡(luò)（Capsule Networks）概念遷移至圖領(lǐng)域，提出了膠囊圖神經(jīng)網(wǎng)絡(luò)用于圖分類任務(wù).

GAGCN 架構(gòu)及參數(shù)設(shè)置：GAGCN 的整體架構(gòu)如圖2 所示.在該實(shí)驗(yàn)中，各模塊具體的參數(shù)設(shè)置如下：對(duì)于圖卷積模塊，其共包含6 層圖卷積，前5 層通道數(shù)設(shè)置為64，最后一層設(shè)置為1，并均使用tanh作為非線性激活函數(shù)，式（1）中的F（·）被設(shè)計(jì)為具有64 個(gè)隱藏神經(jīng)元的簡(jiǎn)單全連接網(wǎng)絡(luò)，且隱藏層采用ReLU 進(jìn)行非線性激活；對(duì)于全局對(duì)齊層，設(shè)超參數(shù)κ=50，m=32 即Ws∈R321×32；對(duì)于分類網(wǎng)絡(luò)，設(shè)其為具有128 個(gè)隱藏神經(jīng)單元的全連接網(wǎng)絡(luò)，為了降低過擬合的風(fēng)險(xiǎn)，在該隱藏層后采用了Dropout，且Dropout rate 為0.5.最后，SoftMax 和交叉熵被用來計(jì)算分類損失，整個(gè)模型可以做到端到端（End-to-End）訓(xùn)練以及分類預(yù)測(cè).此外，GAGCN 的訓(xùn)練采用帶有動(dòng)量的隨機(jī)梯度下降算法[31]，且動(dòng)量參數(shù)momentum 為0.9.對(duì)于不同的數(shù)據(jù)集，學(xué) 習(xí)率從{0.01，0.001}中進(jìn)行搜索，且用于小批次訓(xùn)練的超參數(shù)Bacth 為64.與對(duì)比算法相同[9，29]，實(shí)驗(yàn)使用Early－Stopping 技術(shù)，當(dāng)判斷損失函數(shù)不再下降，或精度不再提升時(shí)停止訓(xùn)練.

對(duì)比算法參數(shù)設(shè)置：對(duì)于WL－Subtree Kernel 算法，其迭代次數(shù)搜索范圍為 {1，2，3，4，5}；對(duì)于Graphlet Kernel 算法，為了保證其計(jì)算效率，圖元的結(jié)點(diǎn)規(guī)模被限定為3 個(gè)結(jié)點(diǎn)以內(nèi).當(dāng)C－SVM 進(jìn)行分類時(shí)，其軟間隔超參數(shù)C 在{10－3，10－2，…，102，103}中進(jìn)行搜索.這兩個(gè)算法運(yùn)行壞境為MATLAB，C－S 采用LIBSVM 庫實(shí)現(xiàn).對(duì)于5 個(gè)基于深度學(xué)習(xí)的對(duì)比算法，表2 報(bào)告了其原論文中的實(shí)驗(yàn)結(jié)果.如果在原論文中某些數(shù)據(jù)集的結(jié)果沒有被報(bào)告，則采用其官方源碼對(duì)其進(jìn)行補(bǔ)充實(shí)驗(yàn)，超參數(shù)設(shè)置遵循原論文和官方源碼中的指導(dǎo)規(guī)則進(jìn)行調(diào)整搜索.對(duì)DGK 而言，由于沒有找到可用官方源碼，故在DD 數(shù)據(jù)集上沒有參與比對(duì).所有對(duì)比算法，包括GAGCN，均使用十折交叉驗(yàn)證（10－Fold Cross－Validation）進(jìn)行實(shí)現(xiàn)，表2 中報(bào)告的分類精度為十折交叉驗(yàn)證精度的平均值.

由表2 可知，在7 個(gè)圖分類數(shù)據(jù)集上，GAGCN相較于表現(xiàn)最好的對(duì)比算法平均精度將近有2%的顯著提升.尤其在PROTEINS、IMDB－B、ENZYMES以及RED－M12K 幾個(gè)數(shù)據(jù)集上有1%～4%的提升.GAGCN 和DGCNN 都強(qiáng)調(diào)避免結(jié)構(gòu)信息的損失，提高圖表示向量的信息豐富度，但是由于DGCNN 只做到了特征局部對(duì)齊，而GAGCN 則是利用子圖特征分布做了全局對(duì)齊，同時(shí)使用了更為強(qiáng)大的圖卷積網(wǎng)絡(luò)，故在所有數(shù)據(jù)集上，GAGCN 均好于DGCNN.此外，GIN 的分類結(jié)果也不如GAGCN，GIN雖然使用了同樣強(qiáng)大的圖卷積網(wǎng)絡(luò)來做結(jié)點(diǎn)嵌入，但是卻采用了簡(jiǎn)單聚合的方法來學(xué)習(xí)圖表示向量，過度壓縮了結(jié)構(gòu)特征，造成信息損失，這一對(duì)比結(jié)果也進(jìn)一步證明了GAGCN 研究動(dòng)機(jī)的合理性.相較于DiffPool、CapsGNN 等其他主流的圖分類模型，GAGCN 也體現(xiàn)了非常高的競(jìng)爭(zhēng)力.與基于Graph Kernel 的兩個(gè)方法相比，盡管WL－Subtree Kernel 在NCI－1 數(shù)據(jù)集上取得了最好的結(jié)果，但GAGCN 在NCI－1 上的表現(xiàn)也同樣亮眼，并且在其他6 個(gè)數(shù)據(jù)集上的分類精度都顯著高于這兩個(gè)方法.值得注意的是，Graphlet Kernel 和GAGCN 雖然都是利用了子圖分布這一想法，但是結(jié)果卻相差較多，這也說明了圖神經(jīng)網(wǎng)絡(luò)模型在圖分類任務(wù)上的優(yōu)越性.

3.2 消融實(shí)驗(yàn)

為進(jìn)一步證明GAGCN 的關(guān)鍵貢獻(xiàn)，即全局對(duì)齊策略的有效性，本文針對(duì)Globally－Aligned Pooling進(jìn)行了消融實(shí)驗(yàn).該實(shí)驗(yàn)通過對(duì)GAGCN 架構(gòu)的Globally－Aligned Pooling 做替換，并測(cè)試替換后的模型在NCI－1、DD、PROTEINS、IMBD－B 以及ENZYMES等幾個(gè)數(shù)據(jù)集上的分類表現(xiàn)，來比較不同的圖表示向量生成策略對(duì)圖分類結(jié)果的影響.該實(shí)驗(yàn)共測(cè)試了5 種圖表示向量生成策略，包括兩種聚合策略（Sum－Pooling 和 Average－Pooling）、Sort－Pooling、Set2Set 以及本文提出的Globally－Aligned Pooling.對(duì)于Sort－Pooling 的超參數(shù)設(shè)置，實(shí)驗(yàn)遵循DGCNN 論文及其源碼的指導(dǎo)原則，并考慮到該策略對(duì)分類器的特殊要求，分類網(wǎng)絡(luò)同樣也與DGCNN 的設(shè)置保持相一致；對(duì)于Set2Set，其迭代次數(shù)在{1，2，3}中搜索最優(yōu)參數(shù)設(shè)置.

實(shí)驗(yàn)對(duì)比結(jié)果如圖3 所示，本文提出的Globally－Aligned Pooling 在這些數(shù)據(jù)集上都取得了最高的分類精度.再進(jìn)一步分析，可以看到Globally-Aligned Pooling 和Sort-Pooling，相較于聚合策略而言，分類精度較高，這一點(diǎn)證明了盡可能多地保留結(jié)構(gòu)信息確實(shí)有助于提高模型的分類表現(xiàn).而Globally-Aligned Pooling 和Sort-Pooling 兩者的比較結(jié)果也證明了全局對(duì)齊策略確實(shí)能夠幫助后續(xù)的分類網(wǎng)絡(luò)更好地利用和學(xué)習(xí)圖表示向量的特征，從而更容易幫助模型挖掘出一些有價(jià)值的信息，幫助分類網(wǎng)絡(luò)更好地進(jìn)行分類.此外，Set2Set 這類集合學(xué)習(xí)的策略由于其本質(zhì)上是基于聚合操作的一類加權(quán)求和策略，其權(quán)重的計(jì)算基于LSTM 和注意力機(jī)制，在引入這些額外的計(jì)算復(fù)雜度的同時(shí)其結(jié)果也沒有得到穩(wěn)定的提升.綜上所述，該消融實(shí)驗(yàn)證明一個(gè)優(yōu)秀的圖表示向量生成策略需要保留足夠豐富的特征信息，且全局對(duì)齊的特征順序能夠有效地提高圖神經(jīng)網(wǎng)絡(luò)在圖分類任務(wù)上的精度，進(jìn)一步證明了本文提出的全局對(duì)齊策略的有效性.

圖3 不同圖表示向量生成策略對(duì)分類結(jié)果的影響Fig.3 The influence of different graph-level representation vector generation strategies for classification accuracy

3.3 超參數(shù)κ 敏感性分析

κ 作為Global-Aligned Layer 的關(guān)鍵超參數(shù)，可能會(huì)對(duì)模型的預(yù)測(cè)結(jié)果產(chǎn)生關(guān)鍵性的影響.因此，為了評(píng)估κ 的參數(shù)取值敏感性，以及探究其有效的取值范圍，本文針對(duì)超參數(shù)κ 進(jìn)行了敏感性分析實(shí)驗(yàn).該實(shí)驗(yàn)設(shè)定κ 取值為{10，20，30，50，70，100，200}，其他超參數(shù)采用與3.1 節(jié)相同的設(shè)置.如圖4 所示，在DD 和PROTEINS 兩個(gè)數(shù)據(jù)集上，模型的分類精度呈現(xiàn)出一開始隨著κ 值的增加而提高的趨勢(shì)，這是因?yàn)楫?dāng)κ 值過小時(shí)，子圖特征近似分布粒度較粗，特征被壓縮較多，隨著取值不斷增大圖表示向量蘊(yùn)含越來越多的結(jié)構(gòu)細(xì)節(jié)信息，這有助于模型更加合理地進(jìn)行推斷預(yù)測(cè).然而，當(dāng)?shù)竭_(dá)一定閾值之后，分類精度出現(xiàn)輕微的下降，雖然趨勢(shì)不明顯，但也反應(yīng)出若取κ 值過高或會(huì)承擔(dān)一定過擬合的風(fēng)險(xiǎn).而在IMDB-B 數(shù)據(jù)集上，GAGCN 分類精度總體隨κ 值的增加而提高，但當(dāng)超過一定閾值后，這一增加的趨勢(shì)也變得不明顯.從該實(shí)驗(yàn)結(jié)果的分析中不難發(fā)現(xiàn)，κ值的取值會(huì)對(duì)結(jié)果產(chǎn)生一定的影響，但是總體來說，κ 并不是一個(gè)取值非常敏感的超參數(shù)，在這3 個(gè)數(shù)據(jù)集上，κ 取值范圍在50 左右時(shí)，可以認(rèn)為取得較為穩(wěn)定且不錯(cuò)的結(jié)果.

圖4 不同κ 值下的分類精度波動(dòng)Fig.4 The fluctuation for accuracies with the different κ

4 結(jié)論

針對(duì)現(xiàn)有圖神經(jīng)網(wǎng)絡(luò)生成圖級(jí)別表示向量時(shí)，存在的過度壓縮和特征平移等問題，本文提出了基于全局對(duì)齊策略的圖卷積網(wǎng)絡(luò)，即GAGCN，該網(wǎng)絡(luò)通過構(gòu)建子圖特征的近似分布來對(duì)齊圖表示向量的特征順序，在避免特征平移問題的同時(shí)，保留了更為豐富的結(jié)構(gòu)特征信息，且GAGCN 生成的圖表示向量中蘊(yùn)含的子圖特征分布信息，能夠幫助后續(xù)分類網(wǎng)絡(luò)更容易地挖掘數(shù)據(jù)間內(nèi)在的結(jié)構(gòu)相似性，從而提高模型在圖分類任務(wù)上的分類精度.