來源：圖與推薦公眾號

編輯：學姐帶你玩AI公眾號

圖神經網(wǎng)絡最新綜述論文

圖結構數(shù)據(jù)是現(xiàn)實生活中廣泛存在的一類數(shù)據(jù)形式。宏觀上的互聯(lián)網(wǎng)、知識圖譜、社交網(wǎng)絡數(shù)據(jù)，微觀上 的蛋白質、化合物分子等都可以用圖結構來建模和表示。由于圖結構數(shù)據(jù)的復雜性和異質性，對圖結構數(shù)據(jù)的分析和處理一直是研究界的難點和重點。

圖神經網(wǎng)絡(GraphNeuralNetwork,GNN)是近年來出現(xiàn)的一種利用深度學習直接對圖結構數(shù)據(jù)進行學習的框架，其優(yōu)異的性能引起了學者高度的關注和深入的探索.通過在圖中的節(jié)點和 邊上制定一定的策略，GNN 將圖結構數(shù)據(jù)轉化為規(guī)范而標準的表示，并輸入到多種不同的神經網(wǎng)絡中進行訓練，在節(jié)點分類、邊信息傳播和圖聚類等任務上取得優(yōu)良的效果.與其他圖學習算法相比較，GNN能夠學習到圖結構數(shù)據(jù)中的節(jié)點以及邊的內在規(guī)律和更加深層次的語義特征。由于具有對圖結構數(shù)據(jù)強大的非線性擬合能力,因此 在不同領域的圖相關問題上，GNN 都表現(xiàn)出更高的準確率和更好的魯棒性.?

本文在現(xiàn)有GNN研究的基礎上,首先 概述了GNN的出現(xiàn)歷程,并介紹了相關概念和定義。之后本文著重討論和對比了 GNN 中的各種算法框架，包括 核心思想、任務劃分、學習方式、優(yōu)缺點、適用范圍、實現(xiàn)成本等。此外,本文對GNN算法在多個不同領域下的應用 場景進行了詳細的闡述,將GNN與其他圖學習算法的優(yōu)缺點作了聯(lián)系和比較.針對存在的一些問題和挑戰(zhàn),本文勾畫了GNN的未來方向和發(fā)展趨勢,最后對全文進行了全面而細致的總結。

https://cjc.ict.ac.cn/online/onlinepaper/WB-2022121103627.pdf

引言

近年來, 深 度 學 習[1]在 多 個 領 域 取 得 明 顯 優(yōu) 異的效果,?特別是在計算機視覺、音頻識別以及自然語言處理三個方面取得突破性進展。深度學習通過建立人工神經網(wǎng)絡，對輸入的信息和數(shù)據(jù)逐層進行特征的提取和篩選，最終獲得分類和預測等任務的結果。相較于統(tǒng)計機器學習等淺層學習模式，深度學習所使用的神經網(wǎng)絡架構具有多個功能各異的復雜網(wǎng)絡層，其特征提取和識別的數(shù)量和質量顯著提高，并且能夠自底向上生成更加高級的特征表示。

這使得機器能夠獲得抽象概念, 具備 更 強 的 表 征 學 習 能 力[2].諸 如 多 層 感 知 機 (MultilayerPerceptron,MLP)[3]、卷 積 神 經 網(wǎng) 絡 (ConvolutionalNeuralNetwork,CNN)[4]、循 環(huán) 神 經網(wǎng)絡(RecurrentNeuralNetwork,RNN)[5]、生成 對 抗 網(wǎng) 絡 (Generative Adversarial Network,GAN)[6]和自編碼器(Auto-encoder,AE [7]等性能優(yōu) 異的神經網(wǎng)絡已經成為許多研究領域解決問題的通用網(wǎng)絡框架。

但是隨著研究的深入,研究人員發(fā)現(xiàn)深度學習 并不能適應和解決所有的情況和問題。在過去十多 年的發(fā)展中，深度學習取得的成就主要限定在了計 算機視覺、自然語言處理和音頻分析領域上.這些領 域上的數(shù)據(jù)和信息有著比較顯著的特點。文本、圖 像、音頻、視頻的數(shù)據(jù)格式在形式上有著統(tǒng)一而規(guī)整 的尺寸和維度,它們也被稱作歐式結構(Euclidean Structure)或者網(wǎng)格結構(GridStructure)數(shù)據(jù)。除此之外，現(xiàn)實生活中存在大量的非歐式結構的圖數(shù) 據(jù),例如互聯(lián)網(wǎng)、知識圖譜、社交網(wǎng)絡、蛋白質、化合 物分子等。

盡管深度學習在歐式結構數(shù)據(jù)上取得巨大的成功，但在圖結構數(shù)據(jù)上，基于神經網(wǎng)絡的深度學習表現(xiàn)得并不好。在圖結構數(shù)據(jù)中,節(jié)點與節(jié)點之間的邊連接可能是均勻分布的，也可能是不均勻的。節(jié)點與節(jié)點之間沒有嚴格意義上的先后順序。對于神經網(wǎng)絡的輸入端而言，這些數(shù)據(jù)沒有固定的輸入尺寸。

在數(shù)學表達上，這些數(shù)據(jù)與歐式結構數(shù)據(jù)相比，每一個區(qū)塊的特征矩陣維度都不是統(tǒng)一的,如圖1所示。由于無法使用統(tǒng)一規(guī)整的算子對數(shù)據(jù)編排，導致 CNN 等神經網(wǎng)絡不能再直接對其進行諸如卷 積和池化等操作，也就不再有局部連接、權值共享、 特征抽象等性質[8]。如何將 CNN 等深度學習算法 用于分析圖結構數(shù)據(jù)上成為一個有挑戰(zhàn)性和前沿性的課題。

近年來Gori等人[9]用 RNN 來壓縮節(jié)點信 息和學習圖節(jié)點標簽,首次提出圖神經網(wǎng)絡(Graph NeuralNetwork,GNN)這一概念。之后文獻[10]提出圖卷積網(wǎng)絡 (Graph Convolutional Network, GCN)，正式將 CNN 用于對圖結構數(shù)據(jù)建模。

GCN 通過整合中心節(jié)點和鄰居節(jié)點的特征和標簽信息，給出圖中每個節(jié)點的規(guī)整表達形式，并將其輸入到CNN 中。這樣一來 GCN 就能利用多尺度的信息，組合成更高層次的表達。其有效地利用了圖結構信 息和屬性信息，為深度學習中其他神經網(wǎng)絡遷移至 圖上提供了標準的范式。

在新的研究思路的基礎上, 各種 GNN 架構相繼被構造出來，在多個領域的圖結構數(shù)據(jù)中發(fā)揮了獨特的作用，并促進了圖相關的人工智能推理任務的發(fā)展。

本文針對近年來出現(xiàn)的 GNN 學習方法和研究現(xiàn)狀進行了系統(tǒng)的歸納和梳理,并對它們的主要思 想、改進以及局限性做了詳盡分析。目前已有 Xu等人[11]關于圖卷積神經網(wǎng)絡的綜述，本文在全面對比分析的基礎上，對目前主要的 GNN 算法進行了更加合理的分類和介紹。

除了圖卷積神經網(wǎng)絡,GNN主流算法還包括有圖自編碼器、圖生成網(wǎng)絡、圖循環(huán)網(wǎng)絡以及圖注意力網(wǎng)絡。本文對每類 GNN 算法都 給出了其定義和典型方法，將 GNN 中每種算法的機制、優(yōu)勢、缺點、適用范圍、實現(xiàn)成本等進行了提煉總結。在進行了相應的數(shù)據(jù)實驗基礎上，與其他基準 圖算法進行了比對。本文在第2節(jié)中給出關于 GNN 的基本概念和定義;在第3節(jié)分門別類的給出 GNN 的主要模型和算法;在第4節(jié)，對比和分析 GNN 與 網(wǎng)絡嵌入(NetworkEmbedding)以 及 圖 核 (Graph Kernel)方法的特性和優(yōu)勢.在第5節(jié)中,闡述目前 GNN 在多個領域圖數(shù)據(jù)上的具體應用;在第6節(jié)歸 納和總結現(xiàn)有 GNN 模型缺陷和不足，并對未來發(fā) 展方向和趨勢進行展望.最后在第7節(jié)對全文所述進行總結。

圖神經網(wǎng)絡模型

圖卷積網(wǎng)絡

圖卷積網(wǎng)絡 (GraphConvolutionalNetwork, GCN)進行卷積操作主要有兩種方法:

一種是基于譜分解,即譜分解圖卷積。另一種是基于節(jié)點空間變 換,即空間圖卷積。Bruna等人[10]第一次將卷積神經網(wǎng)路泛化到圖數(shù)據(jù)上,提出兩種并列的圖卷積模型———譜分解圖卷積和空間圖卷積。Bruna等人對 比分析了一般圖結構數(shù)據(jù)和網(wǎng)格數(shù)據(jù)共有的特點和 不同之處,綜合運用了空間圖卷積和譜分解處理圖 像聚類問題。下面本文對譜分解圖卷積和空間圖卷 積進行詳細的梳理和介紹。

圖自編碼器

在深度學習領域，自編碼器 (Auto-encoder, AE)是一類將輸入信息進行表征學習的人工神經網(wǎng) 絡.自編碼器一般包含編碼器和解碼器兩個部分,基于自編碼器的 GNN 被稱為圖自編碼器(GraphAuto-encoder,GAE),可以半監(jiān)督或者無監(jiān)督地學習 圖節(jié)點信息.如圖3所示

在圖自編碼器上,文獻[54]提出基于深度神經網(wǎng)絡的 表 示 模 型 (Deep NeuralNetworkforGraph Representations,DNGR)。DNGR 采用隨機游走模型(RandomSurfingModel)獲取圖結構信息,生成概率共現(xiàn)矩陣,并在概率共現(xiàn)矩陣的基礎上計算PPMI矩陣.在圖節(jié)點嵌入表示學習上,DNGR設計了一個疊加去噪自編碼器(StackedDenoisingAuto-encoder,SDA),輸入PPMI矩陣學習圖節(jié)點低維 表示,并且輸入的一部分會被隨機置零以提高模型的魯棒性。

DNGR的優(yōu)點在于能學習到有向圖中更多的結構信息,其生成的低維嵌入表示可以用于不 同的下游任務。但缺點是忽略了圖屬性信息,沒有將圖屬性和圖結構信息一并納入到模型框架中,因此圖結構的輕微變化就會影響節(jié)點表示的好壞。

針對節(jié)點內容信息的收集,Wang 等人[55]提出一種邊緣圖自編碼器 (Marginalized Graph Autoencoder, MGAE)算法。其在自編碼器中使用基于譜分解的圖卷積網(wǎng)絡層,整合節(jié)點屬性特征和圖結構信息,使得它們之間能進行數(shù)據(jù)交互。

MGAE堆疊多層圖形自編碼器,以建立一個深層次的架構來學習有效的節(jié)點表示。Wang等人認為在訓練中隨機噪聲引起 的干擾可能會提供更有效的輸出表示,因此會在節(jié)點 內容特征中動態(tài)地加入一些干擾項。通過將某些特征值置為零,獲得在大規(guī)模圖上學習的能力。MGAE構 建了優(yōu)化器以確保編碼的節(jié)點屬性信息和真實屬性 信息之間的誤差最小化。在得到每個節(jié)點的表示后, MGAE使用譜聚類算法得到圖聚類結果。

圖生成網(wǎng)絡

建模和生成圖是研究生物工程和社會科學網(wǎng)絡的基礎。圖生成網(wǎng)絡(GraphGenerativeNetwork, GGN)是一類用來生成圖數(shù)據(jù)的 GNN,其使用一定的規(guī)則對節(jié)點和邊進行重新組合,最終生成具有特 定屬性和要求的目標圖。然而，在圖上模擬復雜分 布,并從這些分布中有效地采樣是比較困難的。因為有些圖數(shù)據(jù)具有非唯一性、高維性質,圖中邊緣之間存在復雜的非局部依賴性。因此不能假設所有的圖數(shù)據(jù)都來自于同一個先驗分布,尤其是對于異質圖, 模型在識別過程中必須要具有平移不變性。因此GGN 著重用來解決這類問題和克服其中的難點。GGN 的輸入可以是節(jié)點或者邊向量，也可以是給定的圖嵌入表示，然后對采樣的數(shù)據(jù)學習后合成各種任務所需要的圖。

圖循環(huán)網(wǎng)絡

圖循環(huán)網(wǎng)絡(GraphRecurrentNetwork,GRN) 是最早出現(xiàn)的一種 GNN 模型。相較于其他的GNN 算法，GRN 通常將圖數(shù)據(jù)轉換為序列，在訓練的過程中序列會不斷地遞歸演進和變化。GRN模型一般 使用雙向循環(huán)神經網(wǎng)絡 (BidirectionalRNN,BiRNN)和長短期記憶網(wǎng)絡(LongShort-Term MemoryNetwork,LSTM)作為網(wǎng)絡架構。

圖注意力網(wǎng)絡

注意力機制可以讓一個神經網(wǎng)絡只關注任務學習所需要的信息，它能夠選擇特定的輸入[96]。在GNN中引入注意力機制可以讓神經網(wǎng)絡關注對任 務更加相關的節(jié)點和邊,提升訓練的有效性和測試的精度,由此形成圖注意力網(wǎng)絡(GraphAttention Network,GAT)。

圖神經網(wǎng)絡總結分析

通過前文的歸納和分析, 從總體上看, 圖神經網(wǎng)絡可以分為五類: 圖卷積網(wǎng)絡、圖自編碼器、圖生成網(wǎng)絡、圖循環(huán)網(wǎng)絡和圖注意力網(wǎng)絡。每種圖神經網(wǎng)絡 都有自己對圖結構數(shù)據(jù)處理的一套算法和體系,其 中的原理和適用的范圍也有一定差別。當然它們之 間不是相互孤立和排斥的,例如文獻[59,65]的圖自 編碼器中包含圖卷積層,文獻[91,95]的圖循環(huán)網(wǎng)絡為了圖序列學習更有效,也會加入注意力模塊。而圖注意力網(wǎng)絡也大多以其他圖神經網(wǎng)絡框架為基礎, 構建合適的節(jié)點、邊以及圖注意力網(wǎng)絡層。因此在實 際操作當中,需要根據(jù)圖的分布和特征信息,以及任 務的實際需求,選擇合適的圖神經網(wǎng)絡,來更加有效 地學習圖結構數(shù)據(jù)。 表7是 GNN 機制、優(yōu)點、缺點、 適用范圍及實現(xiàn)成本匯總表。

圖神經網(wǎng)絡應用

由于GNN能較好地學習圖結構數(shù)據(jù)的特征, 因此在許多圖相關的領域有著廣泛的應用。若按照 應用中圖的層次結構劃分,則大體可以分為節(jié)點、邊和圖層面。在節(jié)點層面,常見的有節(jié)點分類、節(jié)點聚合、節(jié)點表示學習。在邊層面,則有邊分類、邊聚類以 及鏈接預測。在圖層面,圖分類、圖生成、子圖劃分、 圖相似度分析等應用較為廣泛。按照圖的種類劃分, 可以分為引文網(wǎng)絡、社交網(wǎng)絡、交通網(wǎng)絡、圖像、化合 物分子結構、蛋白質網(wǎng)絡等。按照應用領域劃分,可 以分為自然語言處理、圖像處理、軌跡預測、物理化學和藥物醫(yī)學等。為了方便說明和闡述, 本文從GNN 的主要應用領域這一角度出發(fā),對近年來出現(xiàn) 的 GNN 應用實例進行分類歸納。

圖神經網(wǎng)絡未來研究方向

GNN 的核心在于規(guī)范化表示的圖結構數(shù)據(jù)并 用深度神經網(wǎng)絡進行學習。經過近些年的不斷發(fā)展, 通過大量數(shù)學證明和實驗分析后,GNN 在理論上和實踐上都被證實是對圖結構數(shù)據(jù)處理的一種有效方 法和框架。盡管 GNN 在各個領域的圖數(shù)據(jù)上取得 了不俗的表現(xiàn)和較好的普適性,但是GNN仍然存 在一定的不足和需要完善的地方。根據(jù)目前國內外的研究現(xiàn)狀,下面本文對 GNN 的一些制約因素和 未來發(fā)展方向進行探討。

網(wǎng)絡深度

在計算機視覺、自然語言處理和音頻處理中,神 經網(wǎng)絡的層數(shù)可以疊加多層.在一定范圍內,神經網(wǎng) 絡層數(shù)的增加可以更好地提取數(shù)據(jù)中的特征信息。例如深層殘差網(wǎng)絡 ResNet [150]可以達到152層。但是GNN的鄰居節(jié)點聚合中,隨著網(wǎng)絡層數(shù)的增加, 鄰居節(jié)點的階數(shù)會不斷擴張,導致中心節(jié)點聚合特 征數(shù)量成指數(shù)變多。這在大規(guī)模數(shù)據(jù)集上,尤其是節(jié) 點之間的邊連接數(shù)量較多時表現(xiàn)的非常明顯。隨之 而來的是訓練過程中計算復雜度的劇增,并可能導 致過擬合的現(xiàn)象發(fā)生.這也就意味著隨著層數(shù)的增加,GNN 模型性能會急劇下降。如果想要加深網(wǎng)絡 層數(shù),就必須限制每層節(jié)點數(shù)量。但是這也會使得特 征聚集的量變少,導致節(jié)點之間信息傳播受阻。如何 解決這一矛盾性問題是將來研究的重點之一。

動態(tài)性

就目前來看,現(xiàn)有的 GNN 大多處理的是靜態(tài)齊次圖。一方面,GNN 框架會假定圖結構是固定的; 另一方面,GNN 框架會假設圖中的節(jié)點和邊來自于單一源分布.然而,這兩個假設在許多情況下并不能 同時成立.在社交網(wǎng)絡中,新的人可以隨時進入網(wǎng)絡,并且現(xiàn)有的人也可以退出網(wǎng)絡.在推薦系統(tǒng)中, 產品可能有不同的類型,其輸入可能有不同的形式, 如文本或圖像。特別是在超大規(guī)模的圖中,節(jié)點的個 數(shù)和邊的個數(shù)可能有百萬、千萬乃至上億。尤其是隨 著數(shù)據(jù)的增加和改變,節(jié)點和邊的個數(shù)以及節(jié)點和邊的類型都可能發(fā)生動態(tài)的變化。在這些任務處理 中,圖的動態(tài)變化是不能忽視的。特別是在固定尺寸下，因為某個節(jié)點或者邊發(fā)生改變而重新學習整個圖將會使得代價十分昂貴。而大多數(shù)GNN對于大型圖具有很好的伸縮性。

其主要原因是當堆疊GNN的多個層時,節(jié)點的最終狀態(tài)涉及大量鄰居的隱藏狀態(tài),導致反向傳播的高復雜性。雖然目前有一 定的文獻[94-95,136-137]在研究圖的時空動態(tài)性,但是面對更大規(guī)模和更加復雜的動態(tài)異質圖數(shù)據(jù)時還不夠有效。因此如何對圖的動態(tài)性進行有效的適應是未 來的研究方向之一。

感受域

一個節(jié)點的感受域是指一組節(jié)點集合,包括中心節(jié)點及其鄰居節(jié)點。感受域大小是決定鄰居節(jié)點數(shù)量的關鍵參數(shù)。在大規(guī)模圖數(shù)據(jù)集中,平均每個節(jié)點周圍有多個鄰居節(jié)點存在。隨著網(wǎng)絡層數(shù)的增加, 鄰居節(jié)點會遞歸增加數(shù)目，感受域也隨之快速擴張。這可能會超過存儲空間的上限。

此外，一些節(jié)點可能只有一個鄰居，而另外節(jié)點可能有多達數(shù)千個鄰居。鄰居節(jié)點分布不均衡使得每個中心節(jié)點的感受域大小不一致。盡管可以通過添加“啞結點”和刪除鄰居 節(jié)點的方式保持數(shù)據(jù)大小和維度的一致，但是在特征的聚集和融合中不可避免的會有信息損失現(xiàn)象發(fā)生，而現(xiàn)有的采樣方法還不能完全解決該問題。

多網(wǎng)絡的融合

由于現(xiàn)實世界數(shù)據(jù)的復雜性,抽象出來的圖結構也會有很多的種類和變體。有向無向、異質非異 質、帶權不帶權等等，大部分的GNN僅能處理其中的某一種類型。而更普遍的情況是各種各樣的圖混 雜在一起,并且希望 GNN 能滿足諸如節(jié)點分類、圖分類、可視化、圖生成等多種任務需求。在這種復雜 的高強度的任務要求下，單一的神經網(wǎng)絡作用過于 有限。因此對于更加復雜的情況,有必要進行多網(wǎng)絡 融合。

目前比較主流的多網(wǎng)絡融合方式是GCN與其他GNN算法相結合。例如在節(jié)點屬性和圖拓撲結構信息的獲取上，GCN 明顯具有較高的性能和良 好的適應性，在節(jié)點分類問題上會表現(xiàn)良好.鑒于其 優(yōu)點,在 GAE中不乏部分模型使用 GCN 作為編碼器,取得較好的效果.但如果還需要進行鏈接預測、 節(jié)點生成或者圖生成，GCN 則有點力不從心了。

此時可以再增設一個 GGN，輸入GCN處理后的節(jié)點 嵌入向量,在GGN 內生成概率分布,完成生成式任務。如果圖在不斷地遞歸演進,形成了圖序列。則可以利用 GRN來處理,以攘括多個步驟下的圖信息。因此在GNN框架中構造不同用途的深度神經網(wǎng)絡,從不 同的側面來提取和整合數(shù)據(jù)的特征是十分有必要的。此外可以對諸如深度置信網(wǎng)絡 (DeepBeliefNetwork)[151]、Transformer [152]等神經網(wǎng)絡進行改造,將 其泛化和應用至圖結構數(shù)據(jù)學習上。

與網(wǎng)絡嵌入的結合

網(wǎng)絡嵌入可以將原始圖數(shù)據(jù)的高維稀疏矩陣轉變?yōu)榈途S度稠密的向量，這可以大幅度壓縮存儲空間，并提取有效的圖信息。一般圖節(jié)點的原始特征矩 陣是高維稀疏的，對于一個 N ×F 的特征矩陣,當 F 比較大時，所需要的存儲空間也相應的增加。如果矩陣比較稀疏,那么存儲效率也會比較低下。網(wǎng)絡嵌入則可以利用圖結構信息,生成低維連續(xù)的節(jié)點特 征表示,避免存儲空間浪費。

其次，由于生成的節(jié)點 嵌入表示包含了部分鄰居節(jié)點信息，所以中心節(jié)點 的感受域也可以相應的減少。對于多層圖卷積和需要迭代壓縮的 GNN 來說,一定程度上可以減少網(wǎng) 絡層數(shù)和迭代壓縮次數(shù)。

例如 Kipf等人[27]半監(jiān)督 GCN 復雜度為O(|E|FC),DeepWalk [110]的復雜 度為O(log(N))。

當邊連接比較密集并且節(jié)點特征 維度很大時,復雜度較高.如果對節(jié)點特征降維,使 得降維之后的維度 F' ? F ，這樣總體復雜度變?yōu)?O(log(N))+O(|E|F'C).盡管增加了網(wǎng)絡嵌入的計算時間，但是在圖卷積層可以大幅度降低計算開銷，這樣可以提高訓練的有效性以及降低計算復雜度。文獻[66,76,86]就使用隨機游走等網(wǎng)絡嵌入方法 來為GNN模型構建輸入序列，除此之外未來研究中也可以嘗試諸如 Node2vec [77]、LINE [153]等網(wǎng)絡 嵌入方法來對 GNN 的輸入端進行改進。

— 完 —

點個贊給學姐午飯加個大雞腿??~