圖神經網絡(GraphNeuralNetworks,GNN)綜述

本篇文章是我在2019年8月閱讀完論文“Wu, Zonghan , et al. "A Comprehensive Survey on Graph Neural Networks." (2019).“”后的翻譯與筆記，寫下這篇文章后不久便意外地轉換了研究方向，如今已不再研究深度學習，所以文中難免有紕漏之處，歡迎發現的知友在評論中指出并給予寶貴的修改意見。

目錄

一、什么是圖神經網絡

二、有哪些圖神經網絡

三、圖神經網絡的應用

在過去的幾年中，神經網絡的興起與應用成功推動了模式識別和數據挖掘的研究。許多曾經嚴重依賴于手工提取特征的機器學習任務（如目標檢測、機器翻譯和語音識別），如今都已被各種端到端的深度學習范式（例如卷積神經網絡（CNN）、長短期記憶（LSTM）和自動編碼器）徹底改變了。曾有學者將本次人工智能浪潮的興起歸因于三個條件，分別是：

盡管傳統的深度學習方法被應用在提取歐氏空間數據的特征方面取得了巨大的成功，但許多實際應用場景中的數據是從非歐式空間生成的，傳統的深度學習方法在處理非歐式空間數據上的表現卻仍難以使人滿意。例如，在電子商務中，一個基于圖（Graph）的學習系統能夠利用用戶和產品之間的交互來做出非常準確的推薦，但圖的復雜性使得現有的深度學習算法在處理時面臨著巨大的挑戰。這是因為圖是不規則的，每個圖都有一個大小可變的無序節點，圖中的每個節點都有不同數量的相鄰節點，導致一些重要的操作（例如卷積）在圖像（Image）上很容易計算，但不再適合直接用于圖。此外，現有深度學習算法的一個核心假設是數據樣本之間彼此獨立。然而，對于圖來說，情況并非如此，圖中的每個數據樣本（節點）都會有邊與圖中其他實數據樣本（節點）相關，這些信息可用于捕獲實例之間的相互依賴關系。

近年來，人們對深度學習方法在圖上的擴展越來越感興趣。在多方因素的成功推動下，研究人員借鑒了卷積網絡、循環網絡和深度自動編碼器的思想，定義和設計了用于處理圖數據的神經網絡結構，由此一個新的研究熱點——“圖神經網絡（Graph Neural Networks，GNN）”應運而生，本篇文章主要對圖神經網絡的研究現狀進行簡單的概述。

需要注意的是，圖神經網絡的研究與圖嵌入（對圖嵌入不了解的讀者可以參考我的這篇文章《圖嵌入綜述》）或網絡嵌入密切相關，圖嵌入或網絡嵌入是數據挖掘和機器學習界日益關注的另一個課題。圖嵌入旨在通過保留圖的網絡拓撲結構和節點內容信息，將圖中頂點表示為低維向量，以便使用簡單的機器學習算法（例如，支持向量機分類）進行處理。許多圖嵌入算法通常是無監督的算法，它們可以大致可以劃分為三個類別，即矩陣分解、隨機游走和深度學習方法。同時圖嵌入的深度學習方法也屬于圖神經網絡，包括基于圖自動編碼器的算法（如DNGR和SDNE）和無監督訓練的圖卷積神經網絡（如GraphSage）。下圖描述了圖嵌入和圖神經網絡在本文中的區別。

在本文中，我們將圖神經網絡劃分為五大類別，分別是：圖卷積網絡（Graph Convolution Networks，GCN）、 圖注意力網絡（Graph Attention Networks）、圖自編碼器（ Graph Autoencoders）、圖生成網絡（ Graph Generative Networks） 和圖時空網絡（Graph Spatial-temporal Networks）。

符號定義

1、圖卷積網絡（Graph Convolution Networks，GCN）

圖卷積網絡將卷積運算從傳統數據（例如圖像）推廣到圖數據。其核心思想是學習一個函數映射 ，通過該映射圖中的節點 可以聚合它自己的特征 與它的鄰居特征 （ ）來生成節點 的新表示。圖卷積網絡是許多復雜圖神經網絡模型的基礎，包括基于自動編碼器的模型、生成模型和時空網絡等。下圖直觀地展示了圖神經網絡學習節點表示的步驟。

GCN方法又可以分為兩大類，基于譜（spectral-based）和基于空間（spatial-based）。基于譜的方法從圖信號處理的角度引入濾波器來定義圖卷積，其中圖卷積操作被解釋為從圖信號中去除噪聲。基于空間的方法將圖卷積表示為從鄰域聚合特征信息，當圖卷積網絡的算法在節點層次運行時，圖池化模塊可以與圖卷積層交錯，將圖粗化為高級子結構。如下圖所示，這種架構設計可用于提取圖的各級表示和執行圖分類任務。

在下面，我們分別簡單介紹了基于譜的GCN和基于空間的GCN。

1.1 Spectral-based Graph Convolutional Networks

在大學里學過《數字信號處理》這門課程的朋友應該會記得，在這門課上我們通過引入傅里葉變換將時域信號轉換到頻域進行分析，進而我們完成一些我們在時域上無法完成的操作，基于譜的圖卷積網絡的核心思想正是來源于此。

在基于譜的圖神經網絡中，圖被假定為無向圖，無向圖的一種魯棒數學表示是正則化圖拉普拉斯矩陣，即

其中，A為圖的鄰接矩陣，D為對角矩陣且

正則化圖拉普拉斯矩陣具有實對稱半正定的性質。利用這個性質，正則化拉普拉斯矩陣可以分解為

，其中

U是由L的特征向量構成的矩陣， 是對角矩陣，對角線上的值為L的特征值。正則化拉普拉斯矩陣的特征向量構成了一組正交基。

在圖信號處理過程中，一個圖的信號

是一個由圖的各個節點組成的特征向量， 代表第i個節點。

對圖X的傅里葉變換由此被定義為

傅里葉反變換則為

其中 為傅里葉變換后的結果。

為了更好地理解圖的傅里葉變換，從它的定義我們可以看出，它確實將輸入的圖信號投影到正交空間，而這個正交空間的基（base）則是由正則化圖拉普拉斯的特征向量構成。

轉換后得到的信號 的元素是新空間中圖信號的坐標，因此原來的輸入信號可以表示為

這正是傅里葉反變換的結果。

現在我們可以來定義對輸入信號X的圖卷積操作了

其中， 是我們定義的濾波器； 表示Hadamard product。

假如我們定義這樣一個濾波器

那么我們的圖卷積操作可以簡化表示為

基于譜的圖卷積網絡都遵循這樣的模式，它們之間關鍵的不同點在于選擇的濾波器不同。

現有的基于譜的圖卷積網絡模型有以下這些：Spectral CNN、Chebyshev Spectral CNN (ChebNet)、Adaptive Graph Convolution Network (AGCN)

基于譜的圖卷積神經網絡方法的一個常見缺點是，它們需要將整個圖加載到內存中以執行圖卷積，這在處理大型圖時是不高效的。

1.2 Spatial-based Graph Convolutional Networks

基于空間的圖卷積神經網絡的思想主要源自于傳統卷積神經網絡對圖像的卷積運算，不同的是基于空間的圖卷積神經網絡是基于節點的空間關系來定義圖卷積的。

為了將圖像與圖關聯起來，可以將圖像視為圖的特殊形式，每個像素代表一個節點，如下圖a所示，每個像素直接連接到其附近的像素。通過一個3×3的窗口，每個節點的鄰域是其周圍的8個像素。這八個像素的位置表示一個節點的鄰居的順序。然后，通過對每個通道上的中心節點及其相鄰節點的像素值進行加權平均，對該3×3窗口應用一個濾波器。由于相鄰節點的特定順序，可以在不同的位置共享可訓練權重。同樣，對于一般的圖，基于空間的圖卷積將中心節點表示和相鄰節點表示進行聚合，以獲得該節點的新表示，如圖b所示。

一種共同的實踐是將多個圖卷積層疊加在一起。根據卷積層疊的不同方法，基于空間的GCN可以進一步分為兩類：recurrent-based和composition-based的空間GCN。recurrent-based的方法使用相同的圖卷積層來更新隱藏表示，composition-based的方法使用不同的圖卷積層來更新隱藏表示。下圖說明了這種差異。

1.3 Comparison Between Spectral and Spatial Models

作為最早的圖卷積網絡，基于譜的模型在許多與圖相關的分析任務中取得了令人印象深刻的結果。這些模型在圖信號處理方面有一定的理論基礎。通過設計新的圖信號濾波器，我們可以從理論上設計新的圖卷積網絡。然而，基于譜的模型有著一些難以克服的缺點，下面我們將從效率、通用性和靈活性三個方面來闡述。

在效率方面，基于譜的模型的計算成本隨著圖的大小而急劇增加，因為它們要么需要執行特征向量計算，要么同時處理整個圖，這使得它們很難適用于大型圖。基于空間的模型有潛力處理大型圖，因為它們通過聚集相鄰節點直接在圖域中執行卷積。計算可以在一批節點中執行，而不是在整個圖中執行。當相鄰節點數量增加時，可以引入采樣技術來提高效率。

在一般性方面，基于譜的模型假定一個固定的圖，使得它們很難在圖中添加新的節點。另一方面，基于空間的模型在每個節點本地執行圖卷積，可以輕松地在不同的位置和結構之間共享權重。

在靈活性方面，基于譜的模型僅限于在無向圖上工作，有向圖上的拉普拉斯矩陣沒有明確的定義，因此將基于譜的模型應用于有向圖的唯一方法是將有向圖轉換為無向圖。基于空間的模型更靈活地處理多源輸入，這些輸入可以合并到聚合函數中。因此，近年來空間模型越來越受到關注。

2、圖注意力網絡（Graph Attention Networks）

注意力機制如今已經被廣泛地應用到了基于序列的任務中，它的優點是能夠放大數據中最重要的部分的影響。這個特性已經被證明對許多任務有用，例如機器翻譯和自然語言理解。如今融入注意力機制的模型數量正在持續增加，圖神經網絡也受益于此，它在聚合過程中使用注意力，整合多個模型的輸出，并生成面向重要目標的隨機行走。在本節中，我們將討論注意力機制如何在圖結構數據中使用。

2.1 Graph Attention Network (GAT)

圖注意力網絡（GAT）是一種基于空間的圖卷積網絡，它的注意機制是在聚合特征信息時，將注意機制用于確定節點鄰域的權重。GAT的圖卷積運算定義為：

其中α（·）是一個注意力函數，它自適應地控制相鄰節點j對節點i的貢獻。為了學習不同子空間中的注意力權重，GAT還可以使用多注意力：

2.2 Gated Attention Network (GAAN)

門控注意力網絡（GAAN）還采用了多頭注意力機制來更新節點的隱藏狀態。然而，GAAN并沒有給每個head部分配相等的權重，而是引入了一種自注意機制，該機制為每個head計算不同的權重。更新規則定義為，

其中 是反饋神經網絡，而 是第k個注意力head的注意力權重

2.3 Graph Attention Model (GAM)

圖形注意力模型（GAM）提供了一個循環神經網絡模型，以解決圖形分類問題，通過自適應地訪問一個重要節點的序列來處理圖的信息。GAM模型被定義為

其中 是一個LSTM網絡，fs是一個step network，它會優先訪問當前節點 優先級高的鄰居并將它們的信息進行聚合。

除了在聚集特征信息時將注意力權重分配給不同的鄰居節點，還可以根據注意力權重將多個模型集合起來，以及使用注意力權重引導隨機行走。盡管GAT和GAAN在圖注意網絡的框架下進行了分類，但它們也可以同時被視為基于空間的圖形卷積網絡。GAT和GAAN的優勢在于，它們能夠自適應地學習鄰居的重要性權重。然而，計算成本和內存消耗隨著每對鄰居之間的注意權重的計算而迅速增加。

3、Graph Autoencoders

圖自動編碼器是一類圖嵌入方法，其目的是利用神經網絡結構將圖的頂點表示為低維向量。典型的解決方案是利用多層感知機作為編碼器來獲取節點嵌入，其中解碼器重建節點的鄰域統計信息，如positive pointwise mutual information （PPMI）或一階和二階近似值。最近，研究人員已經探索了將GCN作為編碼器的用途，將GCN與GAN結合起來，或將LSTM與GAN結合起來設計圖自動編碼器。我們將首先回顧基于GCN的AutoEncoder，然后總結這一類別中的其他變體。

目前基于GCN的自編碼器的方法主要有：Graph Autoencoder (GAE)和Adversarially Regularized Graph Autoencoder (ARGA)

圖自編碼器的其它變體有：

Network Representations with Adversarially Regularized Autoencoders (NetRA)

Deep Neural Networks for Graph Representations (DNGR)

Structural Deep Network Embedding (SDNE)

Deep Recursive Network Embedding (DRNE)

DNGR和SDNE學習僅給出拓撲結構的節點嵌入，而GAE、ARGA、NetRA、DRNE用于學習當拓撲信息和節點內容特征都存在時的節點嵌入。圖自動編碼器的一個挑戰是鄰接矩陣A的稀疏性，這使得解碼器的正條目數遠遠小于負條目數。為了解決這個問題，DNGR重構了一個更密集的矩陣，即PPMI矩陣，SDNE對鄰接矩陣的零項進行懲罰，GAE對鄰接矩陣中的項進行重加權，NetRA將圖線性化為序列。

4、Graph Generative Networks

圖生成網絡的目標是在給定一組觀察到的圖的情況下生成新的圖。圖生成網絡的許多方法都是特定于領域的。例如，在分子圖生成中，一些工作模擬了稱為SMILES的分子圖的字符串表示。在自然語言處理中，生成語義圖或知識圖通常以給定的句子為條件。最近，人們提出了幾種通用的方法。一些工作將生成過程作為節點和邊的交替形成因素，而另一些則采用生成對抗訓練。這類方法要么使用GCN作為構建基塊，要么使用不同的架構。

基于GCN的圖生成網絡主要有

Molecular Generative Adversarial Networks (MolGAN)：將relational GCN、改進的GAN和強化學習（RL）目標集成在一起，以生成具有所需屬性的圖。GAN由一個生成器和一個鑒別器組成，它們相互競爭以提高生成器的真實性。在MolGAN中，生成器試圖提出一個偽圖及其特征矩陣，而鑒別器的目標是區分偽樣本和經驗數據。此外，還引入了一個與鑒別器并行的獎勵網絡，以鼓勵生成的圖根據外部評價器具有某些屬性。

Deep Generative Models of Graphs (DGMG)：利用基于空間的圖卷積網絡來獲得現有圖的隱藏表示。生成節點和邊的決策過程是以整個圖的表示為基礎的。簡而言之，DGMG遞歸地在一個圖中產生一個節點，直到達到某個停止條件。在添加新節點后的每一步，DGMG都會反復決定是否向添加的節點添加邊，直到決策的判定結果變為假。如果決策為真，則評估將新添加節點連接到所有現有節點的概率分布，并從概率分布中抽取一個節點。將新節點及其邊添加到現有圖形后，DGMG將更新圖的表示。

其它架構的圖生成網絡主要有

GraphRNN：通過兩個層次的循環神經網絡的深度圖生成模型。圖層次的RNN每次向節點序列添加一個新節點，而邊層次RNN生成一個二進制序列，指示新添加的節點與序列中以前生成的節點之間的連接。為了將一個圖線性化為一系列節點來訓練圖層次的RNN，GraphRNN采用了廣度優先搜索（BFS）策略。為了建立訓練邊層次的RNN的二元序列模型，GraphRNN假定序列服從多元伯努利分布或條件伯努利分布。

NetGAN：Netgan將LSTM與Wasserstein-GAN結合在一起，使用基于隨機行走的方法生成圖形。GAN框架由兩個模塊組成，一個生成器和一個鑒別器。生成器盡最大努力在LSTM網絡中生成合理的隨機行走序列，而鑒別器則試圖區分偽造的隨機行走序列和真實的隨機行走序列。訓練完成后，對一組隨機行走中節點的共現矩陣進行正則化，我們可以得到一個新的圖。

5、Graph Spatial-Temporal Networks

圖時空網絡同時捕捉時空圖的時空相關性。時空圖具有全局圖結構，每個節點的輸入隨時間變化。例如，在交通網絡中，每個傳感器作為一個節點連續記錄某條道路的交通速度，其中交通網絡的邊由傳感器對之間的距離決定。圖形時空網絡的目標可以是預測未來的節點值或標簽，或者預測時空圖標簽。最近的研究僅僅探討了GCNs的使用，GCNs與RNN或CNN的結合，以及根據圖結構定制的循環體系結構。

目前圖時空網絡的模型主要有

Diffusion Convolutional Recurrent Neural Network (DCRNN)

CNN-GCN

Spatial Temporal GCN (ST-GCN)

Structural-RNN

1、Computer Vision

圖形神經網絡的最大應用領域之一是計算機視覺。研究人員在場景圖生成、點云分類與分割、動作識別等多個方面探索了利用圖結構的方法。

在場景圖生成中，對象之間的語義關系有助于理解視覺場景背后的語義含義。給定一幅圖像，場景圖生成模型檢測和識別對象，并預測對象對之間的語義關系。另一個應用程序通過生成給定場景圖的真實圖像來反轉該過程。自然語言可以被解析為語義圖，其中每個詞代表一個對象，這是一個有希望的解決方案，以合成給定的文本描述圖像。

在點云分類和分割中，點云是激光雷達掃描記錄的一組三維點。此任務的解決方案使激光雷達設備能夠看到周圍的環境，這通常有利于無人駕駛車輛。為了識別點云所描繪的物體，將點云轉換為k-最近鄰圖或疊加圖，并利用圖論進化網絡來探索拓撲結構。

在動作識別中，識別視頻中包含的人類動作有助于從機器方面更好地理解視頻內容。一組解決方案檢測視頻剪輯中人體關節的位置。由骨骼連接的人體關節自然形成圖表。給定人類關節位置的時間序列，應用時空神經網絡來學習人類行為模式。

此外，圖形神經網絡在計算機視覺中應用的可能方向也在不斷增加。這包括人-物交互、少鏡頭圖像分類、語義分割、視覺推理和問答等。

2、Recommender Systems

基于圖的推薦系統以項目和用戶為節點。通過利用項目與項目、用戶與用戶、用戶與項目之間的關系以及內容信息，基于圖的推薦系統能夠生成高質量的推薦。推薦系統的關鍵是評價一個項目對用戶的重要性。因此，可以將其轉換為一個鏈路預測問題。目標是預測用戶和項目之間丟失的鏈接。為了解決這個問題，有學者提出了一種基于GCN的圖形自動編碼器。還有學者結合GCN和RNN，來學習用戶對項目評分的隱藏步驟。

3、Traffic

交通擁堵已成為現代城市的一個熱點社會問題。準確預測交通網絡中的交通速度、交通量或道路密度，在路線規劃和流量控制中至關重要。有學者采用基于圖的時空神經網絡方法來解決這些問題。他們模型的輸入是一個時空圖。在這個時空圖中，節點由放置在道路上的傳感器表示，邊由閾值以上成對節點的距離表示，每個節點都包含一個時間序列作為特征。目標是預測一條道路在時間間隔內的平均速度。另一個有趣的應用是出租車需求預測。這有助于智能交通系統有效利用資源，節約能源。

4、Chemistry

在化學中，研究人員應用圖神經網絡研究分子的圖結構。在分子圖中，原子為圖中的節點，化學鍵為圖中的邊。節點分類、圖形分類和圖形生成是分子圖的三個主要任務，它們可以用來學習分子指紋、預測分子性質、推斷蛋白質結構、合成化合物。

5、Others

除了以上四個領域外，圖神經網絡還已被探索可以應用于其他問題，如程序驗證、程序推理、社會影響預測、對抗性攻擊預防、電子健康記錄建模、腦網絡、事件檢測和組合優化。