關注微信公衆号：人工智能前沿講習
重磅幹貨，第一時間送達
本篇文章是對論文“Wu Z , Pan S , Chen F , et al. A Comprehensive Survey on Graph Neural Networks[J]. 2019.“”的翻譯與筆記
目錄
一、什麼是圖神經網絡
二、有哪些圖神經網絡
三、圖神經網絡的應用
一、什麼是圖神經網絡？
在過去的幾年中，神經網絡的成功推動了模式識别和資料挖掘的研究。許多機器學習任務，如目标檢測、機器翻譯和語音識别，曾經嚴重依賴手工的特征工程來提取資訊特征集，最近被各種端到端的深度學習範式（例如卷積神經網絡（CNN）、長短期記憶（LSTM）和自動編碼器）徹底改變了。在許多領域中，深度學習的成功部分歸因于快速發展的計算資源（如GPU）和大量訓練資料的可用性，部分歸因于深度學習從歐氏空間資料中提取潛在表示的有效性。
盡管深度學習在歐氏空間中的資料方面取得了巨大的成功，但在許多實際的應用場景中的資料是從非歐式空間生成的，同樣需要進行有效的分析。例如，在電子商務中，一個基于圖的學習系統能夠利用使用者和産品之間的互動來做出非常準确的推薦。圖資料的複雜性對現有的機器學習算法提出了重大挑戰，這是因為圖資料是不規則的。每個圖都有一個大小可變的無序節點，圖中的每個節點都有不同數量的相鄰節點，導緻一些重要的操作（例如卷積）在圖像上很容易計算，但不再适合直接用于圖域。此外，現有機器學習算法的一個核心假設是執行個體彼此獨立。然而，對于圖資料來說，情況并非如此，圖中的每個執行個體（節點）通過一些複雜的連結資訊與其他執行個體（鄰居）相關，這些資訊可用于捕獲執行個體之間的互相依賴關系。
近年來，人們對深度學習方法在圖資料上的擴充越來越感興趣。在深度學習的成功推動下，研究人員借鑒了卷積網絡、循環網絡和深度自動編碼器的思想，定義和設計了用于處理圖資料的神經網絡結構，由此一個新的研究熱點——“圖神經網絡（Graph Neural Networks，GNN）”應運而生，本篇文章主要對圖神經網絡的研究現狀進行簡單的概述。
需要注意的是，圖神經網絡的研究與圖嵌入（對圖嵌入不了解的讀者可以參考我的這篇文章《圖嵌入綜述》）或網絡嵌入密切相關，圖嵌入或網絡嵌入是資料挖掘和機器學習界日益關注的另一個課題。圖嵌入旨在通過保留圖的網絡拓撲結構和節點内容資訊，将圖中頂點表示為低維向量空間，以便使用簡單的機器學習算法（例如，支援向量機分類）進行處理。許多圖嵌入算法通常是無監督的算法，它們可以大緻可以劃分為三個類别，即矩陣分解、随機遊走和深度學習方法。同時圖嵌入的深度學習方法也屬于圖神經網絡，包括基于圖自動編碼器的算法（如DNGR和SDNE）和無監督訓練的圖卷積神經網絡（如GraphSage）。下圖描述了圖嵌入和圖神經網絡在本文中的差別。
二、有哪些圖神經網絡？
在本文中，我們将圖神經網絡劃分為五大類别，分别是：圖卷積網絡（Graph Convolution Networks，GCN）、 圖注意力網絡（Graph Attention Networks）、圖自編碼器（ Graph Autoencoders）、圖生成網絡（ Graph Generative Networks） 和圖時空網絡（Graph Spatial-temporal Networks）。
符号定義 圖卷積網絡将卷積運算從傳統資料（例如圖像）推廣到圖資料。其核心思想是學習一個函數映射
，通過該映射圖中的節點
可以聚合它自己的特征
與它的鄰居特征
（
）來生成節點
的新表示。圖卷積網絡是許多複雜圖神經網絡模型的基礎，包括基于自動編碼器的模型、生成模型和時空網絡等。下圖直覺地展示了圖神經網絡學習節點表示的步驟。
GCN方法又可以分為兩大類，基于頻譜（spectral-based）和基于空間（spatial-based）。基于頻譜的方法從圖信号處理的角度引入濾波器來定義圖卷積，其中圖卷積操作被解釋為從圖信号中去除噪聲。基于空間的方法将圖卷積表示為從鄰域聚合特征資訊，當圖卷積網絡的算法在節點層次運作時，圖池化子產品可以與圖卷積層交錯，将圖粗化為進階子結構。如下圖所示，這種架構設計可用于提取圖的各級表示和執行圖分類任務。
在下面，我們分别簡單介紹了基于頻譜的GCN和基于空間的GCN。
1.1 Spectral-based Graph Convolutional Networks在大學裡學過《數字信号處理》這門課程的朋友應該會記得，在這門課上我們通過引入傅裡葉變換将時域信号轉換到頻域進行分析，進而我們完成一些我們在時域上無法完成的操作，基于頻譜的圖卷積網絡的核心思想正是來源于此。
在基于頻譜的圖神經網絡中，圖被假定為無向圖，無向圖的一種魯棒數學表示是正則化圖拉普拉斯矩陣，即
其中，A為圖的鄰接矩陣，D為對角矩陣且
正則化圖拉普拉斯矩陣具有實對稱半正定的性質。利用這個性質，正則化拉普拉斯矩陣可以分解為
，其中
U是由L的特征向量構成的矩陣，
是對角矩陣，對角線上的值為L的特征值。正則化拉普拉斯矩陣的特征向量構成了一組正交基。
在圖信号處理過程中，一個圖的信号
是一個由圖的各個節點組成的特征向量，
代表第i個節點。
對圖X的傅裡葉變換由此被定義為
傅裡葉反變換則為
其中
為傅裡葉變換後的結果。
為了更好地了解圖的傅裡葉變換，從它的定義我們可以看出，它确實将輸入圖信号投影到正交空間，在正交空間中，基由正則化圖拉普拉斯的特征向量構成。
轉換後得到的信号
的元素是新空間中圖信号的坐标，是以原來的輸入信号可以表示為
正是傅裡葉反變換的結果。
現在我們可以來定義對輸入信号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的方法使用不同的圖卷積層來更新隐藏表示。下圖說明了這種差異。
作為最早的圖卷積網絡，基于頻譜的模型在許多與圖相關的分析任務中取得了令人印象深刻的結果。這些模型在圖信号處理方面有一定的理論基礎。通過設計新的圖信号濾波器，我們可以從理論上設計新的圖卷積網絡。然而，基于頻譜的模型有幾個缺點。我們從效率、通用性和靈活性三個方面來說明這一點。
在效率方面，基于頻譜的模型的計算成本随着圖的大小而急劇增加，因為它們要麼需要執行特征向量計算，要麼同時處理整個圖，這使得它們很難适用于大型圖。基于空間的模型有潛力處理大型圖，因為它們通過聚集相鄰節點直接在圖域中執行卷積。計算可以在一批節點中執行，而不是在整個圖中執行。當相鄰節點數量增加時，可以引入采樣技術來提高效率。
在一般性方面，基于頻譜的模型假定一個固定的圖，使得它們很難在圖中添加新的節點。另一方面，基于空間的模型在每個節點本地執行圖卷積，可以輕松地在不同的位置和結構之間共享權重。
在靈活性方面，基于頻譜的模型僅限于在無向圖上工作，有向圖上的拉普拉斯矩陣沒有明确的定義，是以将基于頻譜的模型應用于有向圖的唯一方法是将有向圖轉換為無向圖。基于空間的模型更靈活地處理多源輸入，這些輸入可以合并到聚合函數中。是以，近年來空間模型越來越受到關注。
2、圖注意力網絡（Graph Attention Networks）注意力機制如今已經被廣泛地應用到了基于序列的任務中，它的優點是能夠放大資料中最重要的部分的影響。這個特性已經被證明對許多任務有用，例如機器翻譯和自然語言了解。如今融入注意力機制的模型數量正在持續增加，圖神經網絡也受益于此，它在聚合過程中使用注意力，整合多個模型的輸出，并生成面向重要目标的随機行走。在本節中，我們将讨論注意力機制如何在圖結構資料中使用。
2.1 Graph Attention Network (GAT)圖注意力網絡（GAT）是一種基于空間的圖卷積網絡，它的注意機制是在聚合特征資訊時，将注意機制用于确定節點鄰域的權重。GAT的圖卷積運算定義為：
其中α（·）是一個注意力函數，它自适應地控制相鄰節點j對節點i的貢獻。為了學習不同子空間中的注意力權重，GAT還可以使用多注意力：
門控注意力網絡（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除了以上四個領域外，圖神經網絡還已被探索可以應用于其他問題，如程式驗證、程式推理、社會影響預測、對抗性攻擊預防、電子健康記錄模組化、腦網絡、事件檢測群組合優化。
@蘇一