圖神經網絡概述第三彈：來自IEEE Fellow的GNN綜述

本文來源：機器之心編譯 作者：Zonghan Wu

圖神經網絡（GNN）熱度持續上升，之前我們曾介紹了清華兩篇綜述論文，參見：深度學習時代的圖模型，清華發文綜述圖網絡，和清華大學圖神經網絡綜述：模型與應用。最近，IEEEFellow、SeniorMember和MemberZonghanWu等人又貢獻了一篇圖神經網絡綜述文章。這篇文章介紹了GNN的背景知識、發展歷史、分類與框架、應用等，詳細介紹了各種模型與方法，包括公式、模型圖示、算法等，希望對大家有所幫助。

引言

深度網絡的最新進展推進了模式識別和數據挖掘領域的研究。目標檢測、機器翻譯、語音識別等許多機器學習任務曾高度依賴手工特征工程來提取信息特征集合，但多種端到端深度學習方式（即卷積神經網絡、長短期記憶網絡和自編碼器）改變了這種狀況。深度學習在多個領域的成功主要歸功于計算資源的快速發展（如GPU）、大量訓練數據的收集，還有深度學習從歐幾里得數據（如圖像、文本和視頻）中提取潛在表征的有效性。例如CNN可以利用平移不變性、局部連通性和圖像數據語意合成性，從而提取出與整個數據集共享的局部有意義的特征，用于各種圖像分析任務。

盡管深度學習已經在歐幾里得數據中取得了很大的成功，但從非歐幾里得域生成的數據已經取得更廣泛的應用，它們需要有效分析。例如，在電子商務領域，一個基于圖的學習系統能夠利用用戶和產品之間的交互以實現高度精準的推薦。在化學領域，分子被建模為圖，新藥研發需要測定其生物活性。在論文引用網絡中，論文之間通過引用關系互相連接，需要將它們分成不同的類別。

圖數據的復雜性對現有機器學習算法提出了重大挑戰，因為圖數據是不規則的。每張圖大小不同、節點無序，一張圖中的每個節點都有不同數目的鄰近節點，使得一些在圖像中容易計算的重要運算（如卷積）不能再直接應用于圖。此外，現有機器學習算法的核心假設是實例彼此獨立。然而，圖數據中的每個實例都與周圍的其它實例相關，含有一些復雜的連接信息，用于捕獲數據之間的依賴關系，包括引用、朋友關系和相互作用。

最近，越來越多的研究開始將深度學習方法應用到圖數據領域。受到深度學習領域進展的驅動，研究人員在設計圖神經網絡的架構時借鑒了卷積網絡、循環網絡和深度自編碼器的思想。為了應對圖數據的復雜性，重要運算的泛化和定義在過去幾年中迅速發展。例如，圖1展示了受標準2D卷積啟發得到的圖卷積。本文旨在對這些方法進行全面概述，受眾包括想要進入這一快速發展領域的研究人員和想要對比圖神經網絡算法的專家。

圖1：2D卷積 vs.圖卷積

圖神經網絡簡史

圖神經網絡的概念首先由Gori等人（2005）[16]提出，并由Scarselli等人（2009）[17]進一步闡明。這些早期的研究以迭代的方式通過循環神經架構傳播鄰近信息來學習目標節點的表示，直到達到穩定的固定點。該過程所需計算量龐大，而近來也有許多研究致力于解決這個難題。在本文中，圖神經網絡代表的是所有用于圖數據的深度學習方法。

受到卷積網絡在計算機視覺領域所獲巨大成功的激勵，近來出現了很多為圖數據重新定義卷積概念的方法。這些方法屬于圖卷積網絡（GCN）的范疇。Bruna等人（2013）提出了關于圖卷積網絡的第一項重要研究，他們基于譜圖論（spectralgraphtheory）開發了一種圖卷積的變體。自此，基于譜的圖卷積網絡不斷改進、拓展、進階。由于譜方法通常同時處理整個圖，并且難以并行或擴展到大圖上，基于空間的圖卷積網絡開始快速發展。這些方法通過聚集近鄰節點的信息，直接在圖結構上執行卷積。結合采樣策略，計算可以在一個批量的節點而不是整個圖中執行，這種做法有望提高效率。

除了圖卷積網絡，近幾年還開發出了很多替代的圖神經網絡。這些方法包括圖注意力網絡（GAT）、圖自編碼器、圖生成網絡以及圖時空網絡。關于這些方法的分類細節詳見第三章。

圖神經網絡相關研究。Bronstein等人用符號幾何深度學習概述了非歐幾里得領域的深度學習方法，包括圖和流形。雖然這是對圖卷積網絡的第一次回顧，但這一項研究遺漏了幾個基于空間的重要方法，包括[15],[19],[24],[26],[27],[28]，這些方法更新了最新的基準。此外，這項調查沒有囊括很多新開發的架構，這些架構的重要性不亞于圖卷積網絡。

對于另一項研究，Battaglia等人[29]將圖網絡定位為從關系數據中學習的構建塊，并在統一的框架下回顧了部分圖神經網絡。然而，他們整體的框架是高度抽象的，失去了每種方法在原論文中的見解。Lee等人[30]對圖注意力模型（一種圖神經網絡）進行了部分調查。最近，Zhang等人[31]提出了一項關于圖深度學習的最新調查，卻忽略了對圖生成網絡和圖時空網絡的研究?？傊?，現有的研究沒有一個對圖神經網絡進行全面的回顧，只覆蓋了部分圖卷積神經網絡且檢查的研究有限，因此遺漏了圖神經網絡替代方法的最新進展，如圖生成網絡和圖時空網絡。

圖神經網絡vs.網絡嵌入。對圖神經網絡的研究與圖嵌入或網絡嵌入緊密相關，這也是數據挖掘和機器學習社區日益關注的一個話題[32][33][34][35],[36],[37]。網絡嵌入旨在通過保留網絡拓撲架構和節點內容信息，將網絡頂點表示到低維向量空間中，以使任何后續的圖分析任務（如分類、聚類和推薦）都可以通過使用簡單的現成學習機算法（如用于分類的支持向量機）輕松執行。許多網絡嵌入算法都是無監督算法，它們大致可分為三組[32]，即矩陣分解[38],[39]、隨機游走[40]和深度學習方法。用于網絡嵌入的深度學習方法同時還屬于圖神經網絡，包括基于圖自編碼器的算法（如DNGR[41]和SDNE[42]）和具有無監督訓練的圖卷積神經網絡（如GraphSage[24]）。圖2描述了本文中網絡嵌入和圖神經網絡的區別。

圖2：網絡嵌入vs圖神經網絡。

本文作出的貢獻如下：

新的分類體系：考慮到深度學習在圖數據上的研究與日俱增，我們提出了圖神經網絡（GNN）的新分類體系。在這種分類體系下，GNN被分成了5個類別：圖卷積網絡、圖注意力網絡、圖自編碼器、圖生成網絡和圖時空網絡。我們確定了圖神經網絡和網絡嵌入之間的區別，并在不同的圖神經網絡架構之間建立了聯系。

全面的概述：這個綜述提供了在圖數據上的現代深度學習技術的全面概述。對每一種類型的圖神經網絡，我們提供了表征算法的細節描述，并做了必要的對比和對應算法的總結。

豐富的資源：這篇綜述提供了圖神經網絡的豐富資源，其中包括當前最佳算法、基準數據集、開源代碼和實踐應用。這篇綜述可以作為理解、使用和開發不同實際應用的深度學習方法的實踐指南。

未來方向：這篇綜述還強調了已有算法的當前限制，指出了這個快速發展領域未來的可能方向。

論文：AComprehensiveSurveyonGraphNeuralNetworks

論文鏈接：https://arxiv.org/pdf/1901.00596v1.pdf

摘要：近年來，從圖像分類到視頻處理再到語音識別和自然語言處理，深度學習已經變革了多項機器學習任務。這些任務中的數據通常表示在歐幾里得空間中。然而，越來越多的應用使用非歐幾里得域生成的數據，并將它們表示為具有復雜關系和相互依賴關系的圖。雖然圖數據的復雜性對現有機器學習算法提出了重大挑戰，但最近許多研究開始將深度學習方法擴展到圖數據。

本文綜述了數據挖掘和機器學習領域中的圖神經網絡（GNN），并按照新的方法對圖神經網絡的最新進展進行了分類。在關注圖卷積網絡的同時，他們還回顧了最近開發的其他架構，例如圖注意力網絡、圖自編碼器，圖生成網絡以及圖時空網絡等。我們還進一步討論了圖神經網絡在多個領域的應用并總結了不同學習任務現有算法的開源代碼及基準。最后，我們提出了這一快速發展領域的研究方向。

2.定義

在這一節，我們提供基礎圖概念的定義。為了方便查詢，我們在表1總結了常用的符號。

表1：常用符號。

3.分類與框架

這一部分內容給出了圖神經網絡的分類方法。我們考慮到了所有能與神經架構組合成圖神經網絡的可微圖模型，把圖神經網絡最終分類為：圖卷積網絡、圖注意力網絡、圖自編碼器、圖生成網絡和圖時空網絡。這些網絡中，圖卷積網絡在捕捉架構依存關系上扮演著核心角色。如下圖3所示，屬于其他類別的方法部分使用圖卷積網絡作為基礎。表2總結了每個類別的代表性方法。

圖3：圖神經網絡分類

表2：圖神經網絡代表性論文

下圖4展示了圖卷積網絡節點表征學習的過程。

圖4：有多層GCN層的圖卷積網絡變體。通過從鄰域聚合特征信息，一個GCN層把每個節點的隱藏表征進行壓縮。在特征聚合之后，非線性置換被應用到生成的輸出上。通過多層堆疊，每個節點的最終隱藏表征從后續鄰域獲得信息。

下圖5展示了多個建立在GCN上的圖神經網絡模型。

圖5：建立在GCN上的不同圖神經網絡模型。

下圖展示了圖卷積網絡和圖注意力網絡在聚合鄰近節點信息方面的區別。

3.2框架

表3：圖卷積網絡的總結。Node-level輸出與節點回歸和分類任務相關，Edge-level輸出與邊分類和鏈接預測任務相關，Graph-level輸出與圖分類任務相關。

端到端訓練框架。圖卷積網絡可以以（半）監督或純無監督的方式在端到端學習框架中訓練，依賴于學習任務和可用的標簽信息。

節點級分類的半監督學習。給定部分節點被標記的單個網絡，圖卷積網絡可以學習到一個魯棒的模型，高效識別未標記節點的類別標簽[14]。為此，可以通過堆疊一系列的圖卷積層和softmax層來建立端到端框架進行多類別分類。

圖級分類的監督學習。給定一個圖數據集，圖級分類旨在預測整個圖的類別標簽[55],[56],[74],[75]。這一任務的端到端學習可以利用一個結合了圖卷積層和池化步驟的框架實現[55],[56]。

圖嵌入的無監督學習。如果圖中無可用類別標簽，我們可以在一個端到端框架中以完全無監督的方式學習圖嵌入。這些算法通過兩種方式利用邊級（edge-level）信息。一種簡單的方法是采用自編碼器框架，其中編碼器使用圖卷積層將圖嵌進潛在表征中，然后使用解碼器重構圖結構[59],[61]。另一種方法是利用負采樣方法，采樣一部分節點對作為負對（negativepair），而圖中已有的節點作為正對（positivepair）。然后在卷積層之后應用logistic回歸層，以用于端到端學習[24]。

4.圖卷積網絡

這一章概覽圖卷積網絡（GCN），這是很多復雜圖神經網絡模型的基礎。GCN方法分為兩類，分別基于譜和空間?；谧V的方法通過從圖信號處理的角度引入濾波器來定義圖卷積，其中圖卷積運算被解釋為從圖信號中去除噪聲[76]?；诳臻g的方法將圖卷積表征為聚合來自近鄰的特征信息。雖然GCN在節點級別上運行，但是圖池化模塊可以與GCN層交替，將圖粗?；癁楦呒壸咏Y構。如圖5a所示，這種架構設計可用于提取圖級表征、執行圖分類任務。下文會分別介紹、基于空間的GCN和圖池化模塊。

基于譜的GCN部分介紹了其背景、方法等，這些方法包括SpectralCNN、ChebyshevSpectralCNN(ChebNet)、FirstorderofChebNet(1stChebNet)和AdaptiveGraphConvolutionNetwork(AGCN)。

基于空間的GCN分為兩類：Recurrent-basedSpatialGCN和CompositionBasedSpatialGCN。前者包括圖神經網絡（GraphNeuralNetworks，GNN）、門控圖神經網絡（GatedGraphNeuralNetworks，GGNN）和StochasticSteady-stateEmbedding(SSE)。后者涉及了：MessagePassingNeuralNetworks(MPNN)、GraphSage。此外，這部分還介紹了這兩大類之外的空間GCN變體，包括DiffusionConvolutionNeuralNetworks(DCNN)、PATCHY-SAN、Large-scaleGraphConvolutionNetworks(LGCN)、MixtureModelNetwork(MoNet)。

SSE算法。

這一章還從效率、通用性和靈活性方面，對比了基于譜的GCN和基于空間的GCN，認為基于空間的GCN更具優勢，也因此吸引了更多研究興趣。

5圖卷積網絡之外的模型

這部分概述了圖卷積網絡之外的其他圖神經網絡，包括圖注意力神經網絡、圖自編碼器、圖生成模型和圖時空網絡。下表總結了每個類別下的主要方法。

表4：圖卷積網絡之外的其他圖神經網絡概覽。該表根據網絡的輸入、輸出、目標任務和是否基于GCN總結了每種網絡下的多種方法。輸入列代表每種方法適合分布式圖(A)、有向圖(D)還是時空圖(S)。

5.1圖注意力網絡

注意力機制幾乎成為序列任務中的標配。它的價值在于能夠聚焦于對象最重要的部分。該機制被證明在多項任務中有用，如機器翻譯和自然語言理解。由于注意力機制的模型容量越來越大，圖神經網絡在聚合信息、集成多個模型的輸出、生成重要性導向的隨機游走時，可以從注意力機制中獲益良多。

這部分介紹了圖注意力網絡的多種方法，包括圖注意力網絡（GraphAttentionNetwork，GAT）、門控注意力網絡（GatedAttentionNetwork，GAAN）、圖注意力模型（GraphAttentionModel，GAM）、注意力游走（AttentionWalks）。

注意力機制對圖神經網絡的貢獻有三部分，即在聚合特征信息時向不同近鄰分配注意力權重、根據注意力權重集成多個模型，以及使用注意力權重引導隨機游走。盡管我們把GAT和GAAN分類為圖注意力網絡的兩種方法，但是它們都可以作為基于空間的卷積網絡。二者的優勢是它們可以適應性地學習近鄰的重要性權重（如圖6所示）。但是，由于我們必須計算每對近鄰之間的注意力權重，因此計算成本和內存消耗會快速增長。

5.2圖自編碼器

圖自編碼器是一類網絡嵌入方法，旨在通過神經網絡架構將網絡頂點表征到低維向量空間。典型的解決方案是使用多層感知機作為編碼器來獲取節點嵌入，解碼器重建節點的近鄰統計，如正逐點互信息（positivepointwisemutualinformation，PPMI）或一階、二階接近度（proximities）[42]。最近，研究人員嘗試在設計圖自編碼器時用GCN作為編碼器、結合GCN和GAN，或者結合LSTM和GAN。

這部分介紹了基于GCN的自編碼器和其他變體?；贕CN的自編碼器部分介紹了：圖自編碼器（GraphAuto-encoder，GAE）、對抗正則化圖自編碼器（AdversariallyRegularizedGraphAutoencoder，ARGA）。其他變體包括：具備對抗正則化自編碼器的網絡表征（NetworkRepresentationswithAdversariallyRegularizedAutoencoders，NetRA）、用于圖表征的深度神經網絡（DeepNeuralNetworksforGraphRepresentations，DNGR）、結構化深度網絡嵌入（StructuralDeepNetworkEmbedding，SDNE）、深度遞歸網絡嵌入（DeepRecursiveNetworkEmbedding，DRNE）。

DNGR和SDNE僅基于拓撲結構學習節點嵌入，而GAE、ARGA、NetRA和DRNE需要基于拓撲信息和節點內容特征學習節點嵌入。圖自編碼器的一個挑戰是鄰接矩陣的稀疏性，會導致解碼器正條目（positiveentry）的數量遠遠少于負條目。為了解決這個問題，DNGR重建了一個較稠密的矩陣——PPMI矩陣，SDNE對鄰接矩陣的零條目進行懲罰，GAE重新調整鄰接矩陣中項的權重，NetRA將圖線性化為序列。

5.3圖生成網絡

圖生成網絡的目標是基于一組可觀察圖來生成圖。其中的很多方法都是領域特定的。例如，在分子圖生成方面，一些研究將分子圖的表征建模為字符串SMILES[94],[95],[96],[97]。在自然語言處理中，生成語義圖或知識圖通常需要一個給定的句子[98],[99]。最近，研究人員又提出了多個通用方法。一些研究將生成過程看成節點或邊的形成[64],[65]，而另一些則使用生成對抗訓練[66],[67]。該領域的方法要么使用GCN作為構造塊，要么使用不同的架構。

這部分介紹了基于GCN的圖生成網絡和其他圖生成網絡。前者包括：分子生成對抗網絡（MolecularGenerativeAdversarialNetworks，MolGAN）和深度圖生成模型（DeepGenerativeModelsofGraphs，DGMG）；后者涉及GraphRNN（通過兩級循環神經網絡使用深度圖生成模型）和NetGAN（結合LSTM和WassersteinGAN從基于隨機游走的方法中生成圖）。

圖9：MolGAN框架圖示。

5.4圖時空網絡

圖時空網絡同時捕捉時空圖的時間和空間依賴。時空圖具備全局圖結構，每個節點的輸入隨著時間而改變。例如在交通網絡中，使用每個傳感器作為節點來連續記錄某條道路的交通流動速度，其中交通網絡的邊由傳感器對之間的距離決定。圖時空網絡的目標是預測未來節點值或標簽，或預測時空圖標簽。近期研究探索了僅使用GCN、結合GCN和RNN或CNN，以及專用于圖結構的循環架構。

這部分介紹了基于GCN的圖時空網絡和其他圖時空網絡。前者包括：DiffusionConvolutionalRecurrentNeuralNetwork(DCRNN)、CNN-GCN、時空GCN（SpatialTemporalGCN，ST-GCN）。其他方法有Structural-RNN，一種循環結構化框架。

DCRNN的優勢是能夠處理長期依賴，因為它具備循環網絡架構。盡管CNN-GCN比DCRNN簡單一些，但CNN-GCN能夠更高效地處理時空圖，這要歸功于1DCNN的快速實現。時空GCN將時間流作為圖的邊，這導致鄰接矩陣的大小呈平方增長。一方面，它增加了圖卷積層的計算成本。另一方面，要捕捉長期依賴，圖卷積層必須多次堆疊。StructuralRNN在同一個語義組內共享相同的RNN，從而改善了模型效率，但是StructuralRNN需要人類先驗知識來分割語義組。

6應用

圖神經網絡應用廣泛。下面將首先介紹在文獻中頻繁使用的基準數據集。接著將報告各種方法在四種常用數據集上的基準性能，并列出可用的圖神經網絡開源實現。最后，我們將介紹圖神經網絡在各個領域的實際應用案例。

6.1數據集

表5：常用數據集總結。

6.2基準和開源實現

表6：各種方法在四種最常用數據集上的基準性能。以上列出的方法都使用相同的訓練、驗證和測試數據集進行評估。

表7：開源實現概覽。

6.3實際應用案例

本文按領域介紹了GNN的應用，包括計算機視覺、推薦系統、交通、化學等。

7未來方向

加深網絡。深度學習的成功在于深度神經架構。例如在圖像分類中，模型ResNet具有152層。但在圖網絡中，實證研究表明，隨著網絡層數增加，模型性能急劇下降[147]。根據論文[147]，這是由于圖卷積的影響，因為它本質上推動相鄰節點的表示更加接近彼此，所以理論上，通過無限次卷積，所有節點的表示將收斂到一個點。這導致了一個問題：加深網絡是否仍然是學習圖結構數據的好策略？

感受野。節點的感受野是指一組節點，包括中心節點和其近鄰節點。節點的近鄰（節點）數量遵循冪律分布。有些節點可能只有一個近鄰，而有些節點卻有數千個近鄰。盡管采用了采樣策略[24],[26],[27]，但如何選擇節點的代表性感受野仍然有待探索。

可擴展性。大部分圖神經網絡并不能很好地擴展到大型圖上。主要原因是當堆疊一個圖卷積的多層時，節點的最終狀態涉及其大量近鄰節點的隱藏狀態，導致反向傳播變得非常復雜。雖然有些方法試圖通過快速采樣和子圖訓練來提升模型效率[24],[27]，但它們仍無法擴展到大型圖的深度架構上。

動態性和異質性。大多數當前的圖神經網絡都處理靜態同質圖。一方面，假設圖架構是固定的。另一方面，假設圖的節點和邊來自同一個來源。然而，這兩個假設在很多情況下是不現實的。在社交網絡中，一個新人可能會隨時加入，而之前就存在的人也可能退出該社交網絡。在推薦系統中，產品可能具有不同的類型，而其輸出形式也可能不同，也許是文本，也許是圖像。因此，應當開發新方法來處理動態和異質圖結構。