文章目錄

• 1 簡介
  • 1.1 GNN簡史
  • 1.2 GNN的相關(guān)研究
  • 1.3 GNN vs 網(wǎng)絡(luò)嵌入
  • 1.4 文章的創(chuàng)新性
• 2 基本的圖概念的定義
• 3 GNN分類和框架
  • 3.1 GNNs分類
  • 3.2 框架
• 4 圖卷積網(wǎng)絡(luò)
  • 4.1 基于圖譜的GCN
    • 4.1.1 圖信號處理
    • 4.1.2 基于譜的GCN方法
    • 4.1.3 總結(jié)
  • 4.2 基于空間的GCN
    • 4.2.1 基于循環(huán)的空間GCNs
    • 4.2.2 基于組合的空間GCNs
    • 4.2.3 空間GCNs的其他變體
    • 4.2.4 總結(jié)
  • 4.3 圖池模塊
  • 4.4 基于光譜和空間的GCNs的對比
• 5 超GCNs架構(gòu)
  • 5.1 圖注意力網(wǎng)絡(luò)
    • 5.1.1 GAN方法
    • 5.1.2 總括
  • 5.2 圖自編碼
    • 5.2.1 基于GCN的自編碼器
    • 5.2.2 圖自編碼的其他變體
    • 5.2.3 總結(jié)
  • 5.3 圖生成網(wǎng)絡(luò)（GGN）
    • 5.3.1基于GCN的圖生成網(wǎng)絡(luò)
    • 5.3.2 GGN的其他變體
    • 5.3.3 總結(jié)
  • 5.4 圖時空網(wǎng)絡(luò)
    • 5.4.1 基于GCN的圖時空網(wǎng)絡(luò)
    • 5.4.2 其他變體
    • 5.4.3 總結(jié)
• 6 應(yīng)用
  • 6.1 基準數(shù)據(jù)集
  • 6.2 開源項目
  • 6.3 實際應(yīng)用
    • 6.3.1計算機視覺
    • 6.3.2推薦系統(tǒng)
    • 6.3.3交通
    • 6.3.4生物化學
    • 6.3.5其他
• 7 未來發(fā)展方向
  • 7.1 Go Deep
  • 7.2 Receptive Filed
  • 7.3 Scalability
  • 7.4 Dynamics and Heterogeneity
• 8 總括

??近年來，深度學習徹底改變了很多機器學習任務(wù)，從圖像分類，視頻處理到語音識別，自然語言處理等，但是通常來說，這些任務(wù)的數(shù)據(jù)都是歐式數(shù)據(jù)?，F(xiàn)實中，很多數(shù)據(jù)都是非線性的，不是歐式數(shù)據(jù)，因此被表示為數(shù)據(jù)之間復雜關(guān)系和相互依賴的圖結(jié)構(gòu)。
??圖數(shù)據(jù)的復雜性給現(xiàn)有的機器學習算法帶來了重大挑戰(zhàn)。最近，出現(xiàn)了許多關(guān)于擴展圖數(shù)據(jù)的深度學習方法的研究。本文對圖神經(jīng)網(wǎng)絡(luò)（GNNs）在數(shù)據(jù)挖掘和機器學習方面的應(yīng)用做了全面概述。
??提出一種新的分類方法對GNNs各種方法進行分類。著眼于圖卷積網(wǎng)絡(luò)(GCN),回顧了一些最近提出來的新的架構(gòu)，包括Graph attention networks（圖注意力網(wǎng)絡(luò)），Graph autoencoders（圖自編碼），Graph generative networks（圖生成網(wǎng)絡(luò)）以及Graph spatial-temporal networks（圖時空網(wǎng)絡(luò)）。
??另外，進一步討論了圖神經(jīng)網(wǎng)絡(luò)在各個領(lǐng)域的應(yīng)用，總結(jié)了現(xiàn)有算法在不同任務(wù)中的開源代碼，并提出了領(lǐng)域的潛在研究方向。

?

1 簡介

??神經(jīng)網(wǎng)絡(luò)近期的成功推動了模式識別和數(shù)據(jù)挖掘的研究，許多機器學習任務(wù)，例如目標檢測，機器翻譯，語音識別，曾經(jīng)都嚴重依賴棘手的特征工程提取數(shù)據(jù)集的特征，現(xiàn)在已經(jīng)被端到端的學習模式徹底改變，也就是卷積神經(jīng)網(wǎng)絡(luò)（CNN），長短時記憶網(wǎng)絡(luò)（LSTM），和自編碼（AE）。深度學習在許多領(lǐng)域的成功部分歸功于快速發(fā)展的計算資源(如GPU)和大量訓練數(shù)據(jù)，部分歸功于深度學習從歐氏數(shù)據(jù)(如圖像、文本和視頻)中提取有效的數(shù)據(jù)表示。以圖像分析為例，圖像為歐式空間的規(guī)則表示，CNN能夠利用圖像數(shù)據(jù)的平移不變性，局部連結(jié)性和組合性，也就是CNN能夠為各種圖像分析任務(wù)提取整個數(shù)據(jù)集共享的局部特征。
??深度學習在歐式數(shù)據(jù)上取得了巨大的成功，但是，越來越多的應(yīng)用需要對非歐式數(shù)據(jù)進行分析。例如，在電子商務(wù)中，一個基于圖的學習系統(tǒng)能夠利用用戶與商品之間的交互做出非常準確的推薦；在化學中，需要識別被建模為圖結(jié)構(gòu)的分子的生物活性以發(fā)現(xiàn)新的藥物；在引文網(wǎng)絡(luò)中，論文需要通過被引用的關(guān)系相互連接，然后通過挖掘關(guān)系被分成不同的組。圖數(shù)據(jù)不規(guī)則，每個圖的無序節(jié)點大小是可變的，且每個結(jié)點有不同數(shù)量的鄰居結(jié)點，因此一些重要的操作如卷積能夠在圖像數(shù)據(jù)上輕易計算，但是不適用于圖數(shù)據(jù)，可見圖數(shù)據(jù)的復雜性給現(xiàn)有的機器學習算法帶來了巨大的挑戰(zhàn) 。此外，現(xiàn)有的機器學習算法假設(shè)數(shù)據(jù)之間是相互獨立的，但是，圖數(shù)據(jù)中每個結(jié)點都通過一些復雜的連接信息與其他鄰居相關(guān)，這些連接信息用于捕獲數(shù)據(jù)之間的相互依賴關(guān)系，包括，引用，關(guān)系，交互。
??近年來，人們對擴展基于圖數(shù)據(jù)的深度學習越來越感興趣。在深度學習的驅(qū)動下，研究人員借鑒CNN,LSTM,深度AE的思想設(shè)計了圖神經(jīng)網(wǎng)路的架構(gòu)。為了處理復雜的圖數(shù)據(jù)，在過去幾年中，對重要算子的泛化和定義發(fā)展越來越快。例如，圖1說明了圖卷積算子是如何受標準2-D卷積算子的啟發(fā)的。本文對圖神經(jīng)網(wǎng)絡(luò)進行了一個全面的概述。

圖 1 2-D卷積和圖卷積

?

1.1 GNN簡史

??圖神經(jīng)網(wǎng)絡(luò)的表示法最早在Gori等(2005)[16]中提出，在Scarselli等(2009)[17]中進一步闡述。這些早期的研究通過迭代的方式，利用循環(huán)神經(jīng)結(jié)構(gòu)傳播鄰居信息，直到達到一個穩(wěn)定的不動點，來學習目標節(jié)點的表示。這些過程計算代價大，因此很多研究在克服這些困難[18],[19].本文推廣圖神經(jīng)網(wǎng)絡(luò)術(shù)語表示所有的針對圖數(shù)據(jù)的深度學習方法。
??受CNN在計算機視覺領(lǐng)域巨大成功的啟發(fā)，很多方法致力于重新定義卷積算子，這些方法都屬于圖卷積網(wǎng)絡(luò)（GCN）。Bruna et al.(2013)首次基于譜圖理論[20]設(shè)計了一種圖卷積的變體，自此，基于譜圖的卷積網(wǎng)絡(luò)[12]、[14]、[21]、[22]、[23]的改進、擴展和逼近越來越多。但是譜圖方法一般同時處理整個圖，而且難以并行處理或縮放，所以近年來基于空間的圖卷積[24], [25], [26], [27]發(fā)展越來越快。這些方法通過聚集節(jié)點信息直接在圖域進行卷積。結(jié)合抽樣策略，計算可以在批節(jié)點而不是整個圖[24]，[27]上進行，能夠減少計算復雜度。
??近年來，除了圖形卷積網(wǎng)絡(luò)外，還出現(xiàn)了許多新的圖形神經(jīng)網(wǎng)絡(luò)。這些方法包括圖注意網(wǎng)絡(luò)(GAN)、圖的自動編碼器(GAE)、圖的生成網(wǎng)絡(luò)(GGN)和圖時空網(wǎng)絡(luò)(GSTN)。

1.2 GNN的相關(guān)研究

??相關(guān)的GNN綜述很少，Bronstein et al.[8]使用幾何深度學習的符號，概述了非歐式域的深度學習方法，包括圖形和流形。因為是先驅(qū)性工作，所以漏掉了幾個重要的基于空間的方法，包括[15]、[19]、[24]、[26]、[27]、[28]。此外，本研究未涵蓋一些新開發(fā)的架構(gòu)，而這些架構(gòu)對于GCN同樣重要。本文對圖注意網(wǎng)絡(luò)(GAN)、圖的自動編碼器(GAE)、圖的生成網(wǎng)絡(luò)(GGN)和圖時空網(wǎng)絡(luò)(GSTN)等學習范式進行了綜合評述。?Battaglia等人[29]將位置圖網(wǎng)絡(luò)作為構(gòu)建塊學習關(guān)系數(shù)據(jù)，使用統(tǒng)一的框架對部分神經(jīng)網(wǎng)絡(luò)做了回顧。但是，這個泛化的網(wǎng)絡(luò)高度抽象，對原始論文中的方法闡述不足。Lee等人[30]對GNN的分支GAT部分進行了總結(jié)。最近，張[31]等對GNN做了一個最近的研究，但是缺少對GGN和GSTN的研究。綜上，現(xiàn)有GNN方面的綜述都不完整。

1.3 GNN vs 網(wǎng)絡(luò)嵌入

??GNN的研究與圖嵌入或網(wǎng)絡(luò)嵌入密切相關(guān)，是數(shù)據(jù)挖掘和機器學習[32],[33],[34],[35],[36],[37]日益關(guān)注的另一個課題。網(wǎng)絡(luò)嵌入致力于在一個低維向量空間進行網(wǎng)絡(luò)節(jié)點表示，同時保護網(wǎng)絡(luò)拓撲結(jié)構(gòu)和節(jié)點的信息，便于后續(xù)的圖像分析任務(wù)，包括分類，聚類，推薦等，能夠使用簡單現(xiàn)成的機器學習算法（例如，使用SVM分類）。許多網(wǎng)絡(luò)嵌入算法都是典型的無監(jiān)督算法，它們可以大致分為三種類型[32]，即，矩陣分解[38]、[39]、隨機游走[40]、深度學習?；谏疃葘W習的網(wǎng)絡(luò)嵌入屬于GNN，包括圖自編碼算法，基于無監(jiān)督訓練的圖卷積神經(jīng)網(wǎng)絡(luò)。圖2描述了網(wǎng)絡(luò)嵌入和GNN的區(qū)別。

?圖2 網(wǎng)絡(luò)嵌入 VS GNN ??????圖3 GNN分類

?

1.4 文章的創(chuàng)新性

新的分類方法
提出新的GNN算法分類，分為五種類型GCN,GAN,GAE,GGN,GSTN。同時文章分析了網(wǎng)絡(luò)嵌入和GNN的區(qū)別，并展示了GNN架構(gòu)之間的聯(lián)系。

綜合性調(diào)研
對每種具有代表性的算法進行詳細的描述，并進行相應(yīng)的比較和總結(jié)，是目前為止最詳細的概述。

豐富的資源
提供了豐富的GNN資源，包括最先進的算法，基準數(shù)據(jù)集，公開源碼，實際應(yīng)用。

未來方向
對現(xiàn)有算法的局限性進行了研究，并提出該領(lǐng)域可能的發(fā)展方向。

2 基本的圖概念的定義

本文中和GNN有關(guān)的符號定義如下：

符號含義符號含義

|??|	集合大小	eijeij?	邊
⊙⊙	元素乘	X∈RN×DX∈RN×D	圖的特征矩陣
ATAT	矩陣A的轉(zhuǎn)置	x∈RNx∈RN	D=1，特征向量
[A,B][A,B]	矩陣連接	NN	節(jié)點的數(shù)量NN=|VV|
GG	圖	MM	邊的數(shù)量MM=|EE|
VV	圖上點的集合	DD	節(jié)點向量的維度
vivi?	點	TT	centered
N(v)N(v)	點vv的鄰居節(jié)點	EE	圖的邊集合

圖：圖G=(V,E,A)G=(V,E,A),其中VV節(jié)點集合，EE邊集合，AA鄰接矩陣。vi∈Vvi?∈V描述一個點，eij=(vi,vj)∈Eeij?=(vi?,vj?)∈E描述兩個節(jié)點之間的邊，AA是一個N×NN×N的矩陣，其中Aij={wijifeij=(vi,vj)∈E0ifeij?EAij?={wij?ifeij?=(vi?,vj?)∈E0ifeij?∈/?E?連接一個節(jié)點的邊是一個節(jié)點的度，degree(vi)=∑Aidegree(vi?)=∑Ai?。
圖與節(jié)點屬性XX關(guān)聯(lián)，X∈RN×DX∈RN×D是一個特征矩陣，且Xi∈RDXi?∈RD表示節(jié)點vivi?的特征向量。當D=1D=1時，X∈RNX∈RN表示圖的特征向量。
有向圖：
有向圖中所有邊都是從一個節(jié)點指向另一個節(jié)點。對于有向圖，Aij≠AjiAij??=Aji。無向圖是所有邊都無方向的圖。對于無向圖，Aij=AjiAij=Aji。
時空圖：時空圖是一種特征矩陣XX隨時間變化的圖，G=(V,E,A,X)G=(V,E,A,X)，其中X∈RT×N×DX∈RT×N×D，TT是時間步長。

3 GNN分類和框架

??本節(jié)介紹文章對GNN分類的方法，將任何可微分模型（包含了神經(jīng)結(jié)構(gòu)）作為GNN。將GNN分為五種類型GCN,GAN,GAE,GGN,GSTN。其中GCN在捕獲結(jié)構(gòu)依賴性方面起到了重要作用，如圖3所示，其他的方法都部分利用了GCN作為構(gòu)建模型的塊。表2總結(jié)了每一類方法的代表性方法。
?????????????????????????表2 GNN分類的代表性方法

分類	?	文獻
GCN	Spectral-based	[12], [14], [20], [21], [22], [23], [43]
	Spatial-based	[13], [17], [18], [19], [24], [25], [26], [27], [44], [45] [46], [47], [48], [49], [50], [51], [52], [53], [54]
	Polling Modeles	[12], [21], [55], [56]
GAT	?	[15], [28], [57], [58]
GAE	?	[41], [42], [59], [60], [61], [62], [63]
GGN	?	[64], [65], [66], [67], [68]
GSTN	?	[69], [70], [71], [72], [73]

3.1 GNNs分類

GCNs：GCNs將傳統(tǒng)數(shù)據(jù)的卷積算子泛化到圖數(shù)據(jù)，這個算法的關(guān)鍵是學習一個函數(shù)ff，能夠結(jié)合vivi?鄰居節(jié)點的特征XjXj?和其本身特征XiXi?生成vivi?的新表示，j∈N(vi)j∈N(vi?)。圖4展示了GCNs的節(jié)點表示學習。圖5展示了一些基于GCN的圖神經(jīng)網(wǎng)絡(luò)模型。

圖5 基于GCN構(gòu)建的不同網(wǎng)絡(luò)

?

GAN：GAN與GCN類似，致力于尋找一個聚合函數(shù)，融合圖中相鄰的節(jié)點，隨機游動和候選模型，學習一種新的表示。關(guān)鍵區(qū)別是：GAN使用注意力機制為更重要的節(jié)點，步或者模型分配更大的權(quán)重，權(quán)重個網(wǎng)絡(luò)一起學習。圖6展示了GCN和GAN在聚合鄰居節(jié)點信息時候的不同。

圖6 GCN和GAN的不同 ????????圖7 基于循環(huán)和基于組合的GCN
(GCN邊的權(quán)重是一個固定的值，GAN是通過端到端的網(wǎng)絡(luò)結(jié)構(gòu)學習，因此重要的點權(quán)重更大)

?

GAE：GAE是一種無監(jiān)督學習框架，通過編碼器學習一種低維點向量，然后通過解碼器重構(gòu)圖數(shù)據(jù)。GAE是一種常用的學習圖嵌入的方法，既適用于無屬性信息[41]、[42]的普通圖，還適用于是有屬性圖[61]、[62]。對于普通的圖，大多數(shù)算法直接預先得到一個鄰接矩陣，或者構(gòu)建一個信息豐富的矩陣，也就是點對互信息矩陣，或者鄰接矩陣填充自編碼模型，并捕獲一階和二階信息[42]。對于屬性圖，圖自編碼模型利用GCN[14]作為一個構(gòu)建塊用于編碼，并且通過鏈路預測解碼器[59],[61]重構(gòu)結(jié)構(gòu)信息。
GGN：GGN旨在從數(shù)據(jù)中生成可信的信息，生成給定圖經(jīng)驗分布的圖從根本上來說是具有挑戰(zhàn)性的，主要因為圖是復雜的數(shù)據(jù)結(jié)構(gòu)。為了解決這個問題，研究員探索了將交替形成節(jié)點和邊作為生成過程的因素，并借助[66],[67]作為訓練過程。GGN一個很有前途的應(yīng)用領(lǐng)域是化合物合成。在化學圖中，視原子為節(jié)點，化學鍵為邊，任務(wù)是發(fā)現(xiàn)具有一定化學和物理性質(zhì)的可合成的新分子。
GSTN：GSTN從時空圖中學習不可見的模式，在交通預測和人類活動預測等應(yīng)用中越來越重要。例如，底層道路交通網(wǎng)絡(luò)是一個自然圖，其中每個關(guān)鍵位置是一個節(jié)點，它的交通數(shù)據(jù)是被連續(xù)監(jiān)測的。通過建立有效的GSTN，能夠準確預測整個交通的系統(tǒng)的交通狀態(tài)[70],[71]。GSTN的核心觀點是，同時考慮空間依賴性和時間依賴性。目前很多方法使用GCNs捕獲依賴性，同時使用RNN[70],或者CNN[71]建模時間依賴關(guān)系。

3.2 框架

??GNN，尤其是GCN，通過用譜圖理論和空間局部性重新定義圖卷積，試圖在圖數(shù)據(jù)上重復CNN的成功。使用圖結(jié)構(gòu)和節(jié)點信息作為輸入，GCN的輸出能夠利用以下的一種機制用于不同的圖分析任務(wù)：

• Node-level輸出用于點回歸和分類任務(wù)。圖卷積模型直接給定節(jié)點的潛在表示，然后一個多層感知機或者softmax層用作GCN最后一層。
• Edge-level輸出與邊分類和鏈路預測任務(wù)相關(guān)。為了預測一條邊的便簽或者連接強度，附加函數(shù)從圖卷積模型中提取兩個節(jié)點的潛在表示作為輸入。
• Graph-level輸出和圖分類任務(wù)相關(guān)，池化模塊用于粗話一個圖為子圖或者對節(jié)點表示求和/求平均，以獲得圖級別上的緊湊表示。

??表3列出了主要GCNs方法的輸入和輸出。特別對每種方法的GCN層和最后一層之間的輸出機制進行了總結(jié)。輸出機制可能涉及幾個池化操作，建在后面討論。
??????????????????表3 GCN 總結(jié)

分類	方法	輸入（是否允許邊特征）	輸出	輸出機制
				中間層	最終層
Spectral-based	Spectral CNN(2014)[20]	N	Graph-level	cluster+max_pooling	softmax?
	ChebNet(2016)[12]	N	Graph-level	efficient pooling?	mlp +softmax
	1stChebNet (2017) [14]	N	Node-level	activation function	softmax?
	AGCN (2018) [22]	N	Graph-level	max_pooling?	sum pooling
Spatial-based	GNN (2009) [17]	Y	Node-level	~	mlp +softmax
			Graph-level	~	add a dummy super node
	GGNNs (2015) [18]	N	Node-level	~	mlp /softmax
			Graph-level	~	sum pooling
	SSE (2018) [19]	N	Node-level	~	softmax?
	MPNN (2017) [13]	Y	Node-level	~	softmax?
			Graph-level	~	sum pooling
	GraphSage (2017) [24]	N	Node-level	activation function	softmax?
	DCNN (2016) [44]	Y	Node-level	activation function	softmax?
			Graph-level	~	mean pooling
	PATCHY-SAN (2016) [26]	Y	Graph-level	~	mlp +softmax
	LGCN (2018) [27]	N	Node-level	skip connections	mlp +softmax

端到端訓練框架：GCN可以在端到端學習框架中進行(半)監(jiān)督或無監(jiān)督的訓練，取決于學習任務(wù)和標簽信息的可用性。

• node-level 半監(jiān)督分類。給定一個部分節(jié)點被標記而其他節(jié)點未標記的網(wǎng)絡(luò)，GCN可以學習一個魯棒的模型，有效地識別未標記節(jié)點[14]的類標簽。為此，可以構(gòu)建一個端到端的多分類框架，通過疊加幾個圖形卷積層，緊跟著一個softmax層。
• graph-level 監(jiān)督分類。給定一個圖數(shù)據(jù)集，圖級分類旨在預測整個圖[55]，[56]，[74]，[75]的類標簽(s)，端到端學習框架，通過結(jié)合GCN和池化過程[55,56]實現(xiàn)。具體的，通過GCN獲得每個圖里每個節(jié)點固定維數(shù)的特征表示，然后，通過池化求圖中所有節(jié)點的表示向量的和，以得到整個圖的表示。最后，加上多層感知機和softmax層，可以構(gòu)造一個端到端的圖分類。圖5（a）展示了這樣一個過程。
• 無監(jiān)督圖嵌入。圖中沒有標簽數(shù)據(jù)的時候，可以在端到端的框架中以無監(jiān)督的方式學習一種圖嵌入。這些算法以兩種方式利用邊級信息。一種簡單的：利用自編碼框架，編碼器利用GCN將圖嵌入到潛在的表示中，解碼器利用潛在的表示重構(gòu)圖結(jié)構(gòu)[59,61]。另一種方式：利用負采樣方法，抽取一部分節(jié)點對作為負對，圖中剩余的節(jié)點對作為正對，之后利用邏輯回歸層，形成一個端到端的學習框架[24]。

4 圖卷積網(wǎng)絡(luò)

??GCNs分為兩類：spectral-based 和spatial-based，Spectral-based方法從圖信號處理的角度[76]引入濾波器來定義圖卷積，此使圖卷積被解釋為從圖信號中去除噪聲。Spatial-based的方法將圖卷積表示為來自鄰居節(jié)點的特征信息的結(jié)合。GCNs在節(jié)點級作用時，圖池化模塊可以與GCN交錯定義，將圖粗話為高水平子結(jié)構(gòu)。如圖5（a）所示，這樣一個結(jié)構(gòu)設(shè)計能夠提取圖水平的表示并用于圖分類任務(wù)。

4.1 基于圖譜的GCN

??基于譜的方法在圖信號處理中具有堅實的基礎(chǔ)[76]。首先介紹圖信號處理的基本知識，然后回顧spectral-based GCNs的代表性成果。

4.1.1 圖信號處理

??歸一化圖拉普拉斯矩陣時一個圖的一種魯棒的數(shù)據(jù)表示，記為:L=In?D?12AD?12L=In??D?21?AD?21?,其中AA是圖的鄰接矩陣，DD時一個節(jié)點度矩陣，記錄每個節(jié)點的度，Dii=∑j(Aij)Dii?=∑j?(Aij?)，歸一化拉普拉斯矩陣具有實對稱半正定的性質(zhì)。因此LL能夠被分解為L=UΛUTL=UΛUT,其中Unexpected text node: ' 'U=[u0?,u1?,?,un?1?]∈RN×N是根據(jù)特征值排序的特征向量組成的矩陣，ΛΛ是特征值的對角矩陣，Λii=λiΛii?=λi?.圖拉普拉斯矩陣的特征向量構(gòu)成一個正交的空間，即UTU=IUTU=I。在圖信號處理中，圖信號x∈RNx∈RN是圖中第ii個節(jié)點xixi?的特征向量,信號xx的圖傅里葉變換定義為F(X)=UTxF(X)=UTx,逆傅里葉變換為F?1(x?)=Ux?F?1(x)=Ux,x?x表示圖傅里葉變換對信號xx的輸出。從定義中可以看到，圖拉普拉斯確實將圖輸入信號投影到正交空間，該正交空間的基根據(jù)LL的特征向量構(gòu)成。變換后的信號x?x的元素表示新空間中圖的坐標，因此，輸入信號能夠被表示為x=∑ix?iuix=∑i?xi?ui?，實際上是圖信號的逆傅里葉變換。因此，輸入信號xx用g∈RNg∈RN濾波的圖卷積為：x?Gg=F?1(F(x)⊙F(g))=U(UTx⊙UTg)x?Gg=F?1(F(x)⊙F(g))=U(UTx⊙UTg)其中⊙⊙表示Hadamard乘積,也就是點乘，矩陣的對應(yīng)元素想乘。如果定義一個濾波器gθ=diag(UTg)gθ?=diag(UTg)，圖卷積就簡化為x?Ggθ=UgθUTxx?Ggθ?=Ugθ?UTx??基于譜的GCN都遵循這個定義，不同的是濾波器gθgθ?的選擇不同。

4.1.2 基于譜的GCN方法

譜CNN：Bruna等人，[20]中第一次提出譜卷積神經(jīng)網(wǎng)絡(luò)。假設(shè)濾波器gθ=Θki,jgθ?=Θi,jk?是一個可學習參數(shù)的集合，并且假設(shè)圖信號是多維的，圖卷積層頂定義為：Unexpected text node: ' 'X:,jk+1?=σ(i=1∑fk?1??UΘi,jk?UTX:,ik?)(j=1,2,?,fk?)其中Xk∈RN×fk?1Xk∈RN×fk?1?是輸入圖信號，NN是節(jié)點數(shù)量，fk?1fk?1?是輸入通道的數(shù)量，fkfk?是輸出通道的數(shù)量，Θki,jΘi,jk?是一個可學習參數(shù)的對角矩陣，σσ是一個線性變換。
Chebyshev譜CNN（ChebNet）：Defferrard等人[12]中提出ChebNet，定義特征向量對角矩陣的切比雪夫多項式為濾波器，也就是gθ=∑Ki=1θiTk(Λ?)gθ?=∑i=1K?θi?Tk?(Λ)，Λ?=2Λ/λmax?INΛ=2Λ/λmax??IN?。切比雪夫多項式遞歸定義為：Tk(x)=axTk?1(x)?Tk?2(x)Tk?(x)=axTk?1?(x)?Tk?2?(x),其中T0(x)=1,T1(x)=xT0?(x)=1,T1?(x)=x。信號xx的卷積為：x?Ggθ=U(∑Ki=1)θiTk(Λ?)UTx=∑Ki=1θiTi(L?)xx?Ggθ?=U(i=1∑K?)θi?Tk?(Λ)UTx=i=1∑K?θi?Ti?(L)x其中L?=2L/λmax?INL=2L/λmax??IN?。
??從上式中，ChebNet避免計算圖傅里葉的基，將計算復雜度從O(N3)O(N3)將到O(KM)O(KM).由于Ti(L?)Ti?(L)是L?L的ii階多項式，所以Ti(L?)xTi?(L)x作用于每個節(jié)點的局部，所以ChebNet濾波器在空間是局部化的。
一階ChebNet（1stChebNet）[效果很好]:Kipf等人，[14]引入了一種一階近似ChebNet。假設(shè)K=1,λmax=2K=1,λmax?=2,上式簡化為：x?Ggθ=θ0x?θ1D?12AD?12xx?Ggθ?=θ0?x?θ1?D?21?AD?21?x為了抑制參數(shù)數(shù)量防止過擬合，1stChebNet假設(shè)θ=θ0=?θ1θ=θ0?=?θ1?,圖卷積的定義就變?yōu)?#xff1a;x?Ggθ=θ(In+D?12AD?12)xx?Ggθ?=θ(In?+D?21?AD?21?)x為了融合多維圖輸入信號，1stChebNet對上式進行修正提出了圖卷積層：Xk+1=A?XkΘXk+1=AXkΘ其中A?=IN+D?12AD?12A=IN?+D?21?AD?21?。
??1stChebNet CGN也是空間局部化 的，彌補了譜方法和空間方法的差距。輸出的每一行表示一個節(jié)點的潛在表示，通過節(jié)點自身和鄰居節(jié)點的加權(quán)聚合計算得到，其中權(quán)重是A?A的特定行獲得。1stChebNet的主要缺點是在批訓練時，隨著1stChebNet層數(shù)的增加，計算消耗成指數(shù)增加。最后一層的每一個節(jié)點都必須遞歸的在以前層中擴展他的鄰域。Chen et al.[45]假設(shè)方程7中重新調(diào)整的鄰接矩陣A?A來自抽樣分布。這樣就可以使用蒙特卡洛和方差約減技術(shù)加速訓練過程。
Chen et al.[46]通過鄰域采樣和原來的隱藏表示將GCN的感受野縮小到任意小尺度。Huang et al.[54]提出了一種自適應(yīng)分層抽樣方法來加速1stChebNet的訓練，其中低層的抽樣以高層的抽樣為條件（？）。該方法也適用于顯式方差約簡。
自適應(yīng)GCN(AGCN)：為了探索圖拉普拉斯矩陣為指明的隱藏結(jié)構(gòu)，Li等人[22]提出了自適應(yīng)圖卷積網(wǎng)絡(luò)(AGCN)。AGCN利用所謂的殘差圖來擴充圖，殘差圖是通過計算節(jié)點對的距離來構(gòu)造的。盡管AGCN能夠捕獲互補關(guān)系信息，但是以O(shè)(N2)O(N2)的計算量為代價。

4.1.3 總結(jié)

??譜CNN[20]依賴于拉普拉斯矩陣的特征分解。主要有三個問題：首先，對圖的任何擾動都會導致特征基的變化。其次，學習的過濾器依賴于不同領(lǐng)域，這意味著它們不能應(yīng)用于具有不同結(jié)構(gòu)的圖。第三，特征分解需要O(N3)O(N3)計算和O(N2)O(N2)內(nèi)存。由ChebNet[12]和1stChebNet[14]定義的過濾器具有空間局部性，學習到的權(quán)重可以在圖中的不同位置共享。然而，譜方法的一個常見缺點是需要將整個圖加載到內(nèi)存中進行圖卷積，這在處理大圖時效率不高。

4.2 基于空間的GCN

??根據(jù)傳統(tǒng)CNN在圖像上卷積操作了，基于空間的GNN基于一個節(jié)點的空間關(guān)系定義圖卷積算子。將圖像看作特殊圖形式，每個像素代表一個節(jié)點，如圖1（a）所示，每個像素與附近的像素直接相連，如果用一個3××?3窗口取塊，每個節(jié)點的鄰居節(jié)點就是其周圍的八個像素，將濾波器作用于3××?3塊，則每個通道中心像素的值就是3××?3塊內(nèi)像素的加權(quán)平均值。由于相鄰結(jié)點有固定的順序，所以可訓練權(quán)重能夠在不同的局部空間共享。如圖1（b）所示，對于一般圖結(jié)構(gòu)，中心結(jié)點的表示也是根據(jù)其鄰居結(jié)點的聚合結(jié)果表示。為了探索結(jié)點感受野的深度和寬度，通常疊加多個GCL（圖卷積層），根據(jù)疊加方法的不同，將基于空間的GCN分成兩個類別，基于循環(huán)和基于組合的GCNs。基于循環(huán)的GCN使用一個相同的GCL個更新隱含表示，基于組合GCN則使用不同的GCL更新隱含表示。圖7展示了這種不同。

4.2.1 基于循環(huán)的空間GCNs

??基于遞歸的方法的主要思想是遞歸地更新節(jié)點的潛在表示，直到達到穩(wěn)定的不動點。通過對循環(huán)函數(shù)[17]施加約束、使用門循環(huán)單元架構(gòu)[18]、異步和隨機更新節(jié)點潛在表示[19]來實現(xiàn)。
GNNs：GNNs作為最早研究圖神經(jīng)網(wǎng)絡(luò)的方法，通過遞歸地個更新結(jié)點潛在表示直到收斂來實現(xiàn)。換句話說，從傳播的角度來說，每個結(jié)點與鄰居結(jié)點交換信息，直到信息均衡。GNNs的圖卷積算子定義為（8），能夠處理異構(gòu)圖形：htv=f(Iv,Ico[v],ht?1ne,Ine[v])hvt?=f(Iv?,Ico?[v],hnet?1?,Ine?[v])??其中IvIv?是結(jié)點vv的標簽屬性，Ico[v]Ico?[v]表示結(jié)點vv相關(guān)邊的標簽屬性，htne[v]hnet?[v]表示結(jié)點vv的鄰居結(jié)點在tt步的隱含表示，Ine[v]Ine?[v]表示節(jié)點vv鄰居節(jié)點的標簽屬性。
??為了確保收斂，遞歸函數(shù)f(?)f(?)必須是一個壓縮映射，映射后能夠縮小兩點之間的距離。當f(?)f(?)為神經(jīng)網(wǎng)絡(luò)時，對參數(shù)的雅可比矩陣必須加罰項。GNNs采用almeda - pineda算法[77]、[78]對模型進行訓練。其核心思想是運行傳播過程以達到不動點，然后執(zhí)行給定收斂解的反向過程。
門控GNN（GGNNs）：GGNNs采用門控遞歸單元(GRU)[79]作為遞歸函數(shù)，將遞歸減少到固定步數(shù)。GGNNs的空間圖卷積定義為：htv=GRU(ht?1v,∑u∈N(v)Whtu)hvt?=GRU(hvt?1?,u∈N(v)∑?Whut?)??與GNNs不同，GGNNs使用時間反向傳播(BPTT)來學習參數(shù),不需要約束參數(shù)確保收斂。但是BPTT訓練帶了時間和內(nèi)存效率的損失。對于大型圖來說，問題尤其嚴重，因為GGNNs需要在所有節(jié)點上多次運行遞歸函數(shù)，需要將所有節(jié)點的中間狀態(tài)存儲在內(nèi)存中。
隨機穩(wěn)態(tài)嵌入(SSE):為了提高學習效率，SSE算法[19]以異步方式隨機更新節(jié)點潛在表示。如算法1所示，SSE遞歸估計節(jié)點潛在表示，并使用隨機取樣的批數(shù)據(jù)更新參數(shù)。為確保收斂到穩(wěn)態(tài)，SSE的遞歸函數(shù)定義為歷史狀態(tài)和新狀態(tài)的加權(quán)平均：htv=(1?α)ht?1v+αW1σ(W2[xv,∑u∈N(v)[ht?1u,xu]])hvt?=(1?α)hvt?1?+αW1?σ(W2?[xv?,u∈N(v)∑?[hut?1?,xu?]])??雖然將鄰域信息加起來隱式地考慮了節(jié)點的度，但是求和的這種測度是否影響了算法的穩(wěn)定性仍然值得探究。
算法一?隨機不動點迭代學習[19]

• 初始化參數(shù){h0v}v∈V{hv0?}v∈V?
• for k=1 to?KK?do
• ??for t=1 to T do
• ????從節(jié)點集合VV中取nn個樣本
• ????利用公式htv=(1?α)ht?1v+αW1σ(W2[xv,∑u∈N(v)[ht?1u,xu]])hvt?=(1?α)hvt?1?+αW1?σ(W2?[xv?,∑u∈N(v)?[hut?1?,xu?]])更新nn個節(jié)點的隱層表示
• ??end
• ??for p=1 to P do
• ????從標記樣本集合VV中取mm個樣本
• ?? 根據(jù)上面公式反向傳播梯度建立正向模型
• ??end
• end

4.2.2 基于組合的空間GCNs

基于組合的方法通過疊加多個圖的卷積層來更新節(jié)點的表示。
消息傳遞神經(jīng)網(wǎng)絡(luò)(MPNNs):Gilmer等人將現(xiàn)有的[12]、[14]、[18]、[20]、[53]、[80]、[81]等幾個圖卷積網(wǎng)絡(luò)歸納為一個統(tǒng)一的框架，稱為消息傳遞神經(jīng)網(wǎng)絡(luò)(MPNNs)。MPNNs由兩個階段組成，消息傳遞階段和讀出階段。消息傳遞階段實際上是，運行T步基于空間的圖卷積，卷積算子由消息函數(shù)Mt(?)Mt?(?)和更新函數(shù)Ut(?)Ut?(?)定義：htv=Ut(ht?1v,∑w∈N(v)Mt(ht?1v,ht?1w,evw))hvt?=Ut?(hvt?1?,w∈N(v)∑?Mt?(hvt?1?,hwt?1?,evw?))??讀出階段實際上是一個池操作，根據(jù)每個節(jié)點隱含表示生成整個圖的表示。y?=R(hTv∣v∈G)y?=R(hvT?∣v∈G)??通過輸出函數(shù)R(?)R(?)生成輸出y?y?，可以用于graph-level（圖級）任務(wù)。通過假設(shè)不同形式的Ut(?)Ut?(?)Mt(?)Mt?(?)，作者提出了一些其他的GCN。
GraphSage:GraphSage[24]引入聚合函數(shù)的概念定義圖形卷積。聚合函數(shù)本質(zhì)上是聚合節(jié)點的鄰域信息，需要滿足對節(jié)點順序的排列保持不變，例如均值函數(shù)，求和函數(shù)，最大值函數(shù)都對節(jié)點的順序沒有要求。圖的卷積運算定義為:htv=σ(Wt?aggregatek(ht?1v,?u∈N(v)))hvt?=σ(Wt?aggregatek?(hvt?1?,?u∈N(v)))??GraphSage沒有更新所有節(jié)點上的狀態(tài)，而是提出了一種批處理訓練算法，提高了大型圖的可伸縮性。GraphSage的學習過程分為三個步驟。首先，對一個節(jié)點的K-眺鄰居節(jié)點取樣，然后，通過聚合其鄰居節(jié)的信息表示中心節(jié)點的最終狀態(tài)，最后，利用中心節(jié)點的最終狀態(tài)做預測和誤差反向傳播。如圖8所示k-hop,從中心節(jié)點跳幾步到達的頂點

圖8 GraphSage [24]的學習過程

?

??假設(shè)在第tthtth-hop取樣的鄰居個數(shù)是stst?，GraphSage一個batch的 時間復雜度是O(∏Tt=1st)O(∏t=1T?st?).因此隨著tt的增加計算量呈指數(shù)增加，這限制了GraphSage朝深入的框架發(fā)展。但是實踐中，作者發(fā)現(xiàn)t=2t=2已經(jīng)能夠獲得很高的性能。

4.2.3 空間GCNs的其他變體

擴散卷積神經(jīng)網(wǎng)絡(luò)(DCNN): DCNN[44]提出了一種封裝了圖擴散過程的圖卷積網(wǎng)絡(luò)。將輸入與轉(zhuǎn)移概率矩陣的冪級數(shù)進行獨立卷積，得到一個隱藏節(jié)點表示。DCNN的擴散卷積運算可以表示為Zmi,j,:=f(Wj,:⊙Pmi,j,:Xmi,:)Zi,j,:m?=f(Wj,:?⊙Pi,j,:m?Xi,:m?)Zmi,j,:Zi,j,:m?表示圖mm中節(jié)點ii的j?hopj?hop因隱層表示，Pmi,j,:Pi,j,:m?表示圖mm的j?hopj?hop轉(zhuǎn)移概率矩陣，Xmi,:)Xi,:m?)是圖mm中節(jié)點ii的輸入特征。其中Zm∈RNm×H×FZm∈RNm?×H×FW∈RH×FW∈RH×FPm∈RNm×H×NmPm∈RNm?×H×Nm?Xm∈RNm×FXm∈RNm?×F。
??盡管通過更高階的轉(zhuǎn)移矩陣覆蓋更大的感受野，DCNN模型需要O(N2mH)O(Nm2?H)的內(nèi)存，當用在大圖上的時候會引發(fā)服務(wù)問題。
PATCHY-SAN：PATCHY-SAN[26]使用標準CNN來解決圖像分類任務(wù)。為此，它將圖結(jié)構(gòu)化數(shù)據(jù)轉(zhuǎn)換為網(wǎng)格結(jié)構(gòu)數(shù)據(jù)。首先，它使用圖標記過程為每個圖形選擇固定數(shù)量的節(jié)點。圖標記過程本質(zhì)上是為圖中每個節(jié)點排序，排序可以根據(jù)節(jié)點度，中心，WeisfeilerLehman顏色[82]，[83]等。然后PATCHY-SAN根據(jù)上述圖標記結(jié)果為每個節(jié)點選擇和排序固定數(shù)量的鄰居節(jié)點。最后，固定大小的網(wǎng)格數(shù)據(jù)形成以后，PATCHY-SAN利用標準CNN學習圖的隱層表示。GCNs中利用標準CNN能過保持平移不變性，僅依賴于排序函數(shù)。因此，節(jié)點選擇和排序的標準至關(guān)重要。PATCHY-SAN中，排序是基于圖標記的，但是圖標及值考慮了圖結(jié)構(gòu)，忽略了節(jié)點的特征信息。
大規(guī)模圖卷積網(wǎng)絡(luò)(LGCN)：LGCN[27]提出了一種基于節(jié)點特征信息的排序方法。LGCN使用標準的CNN生成node-level(節(jié)點級)輸出。對于每個節(jié)點，LGCN集成其鄰居節(jié)點的特征矩陣，并沿著特征矩陣的每一列進行排序，排序后的特征矩陣的前k行作為目標節(jié)點的輸入網(wǎng)格數(shù)據(jù)。最后LGCN對合成輸入進行1D-CNN得到目標節(jié)點的隱藏輸入。PATCHY-SAN中得到圖標記需要復雜的預處理，但是LGCN不需要，所以更高效。LGCN提出一個子圖訓練策略以適應(yīng)于大規(guī)模圖場景，做法是將采樣的小圖作為mini-batch。
混合模型網(wǎng)絡(luò)(MoNet)：MoNet[25]用非歐式距離領(lǐng)域的卷積結(jié)構(gòu)統(tǒng)一了標準CNN。因為一些基于空間的方法在整合鄰居節(jié)點信息的時候忽略了節(jié)點與其鄰居節(jié)點之間的相對位置，所以MoNet引入了偽坐標和權(quán)值函數(shù)，從而使節(jié)點鄰居的權(quán)重取決于節(jié)點和鄰居節(jié)點的相對位置，也就是偽坐標。在這樣一個框架下，從MoNet推廣了一些基于流形的方法，可以看作MoNet的特例，如測地線CNN(GCNN)[84]，各向異性CNN(ACNN)[85]，樣條CNN[86]，以及對于圖形GCN [14]， DCNN[44]等。但是這些MoNet框架下的方法都是固定的權(quán)重函數(shù)，因此MoNet提出了一種具有可學習參數(shù)的高斯核函數(shù)自由調(diào)整權(quán)重函數(shù)。

4.2.4 總結(jié)

??基于空間的方法通過聚合鄰居的特征信息來定義圖卷積。根據(jù)圖卷積層的不同疊加方式，將空間法分為遞歸法和合成法兩大類?；谶f歸的方法致力于獲得節(jié)點的穩(wěn)定狀態(tài)，基于組合的方法致力于合并更高階的鄰域信息。訓練過程中，兩大類的每一層都需要更新所有節(jié)點的隱層狀態(tài)。因為要在內(nèi)存中保存所有的中間狀態(tài)，因此效率不高。為了解決這個問題，提出了一些訓練方法，包括基于組合的方法中的組圖訓練，如GraphSage[24]，基于遞歸方法的隨機異步訓練，如SSE[19]。

4.3 圖池模塊

??將CNN推廣到圖結(jié)構(gòu)數(shù)據(jù)的時候，圖池化模塊也至關(guān)重要，對graph-level（圖級）分類任務(wù)[55], [56], [87]來說尤其重要。Xu等[88]認為在區(qū)分圖結(jié)構(gòu)方面池輔助的GCN和Weisfeiler-Lehman測試[82]一樣強大。與CNN中的池化層一樣，GCN的圖池化模塊也能夠?qū)υ继卣鲾?shù)據(jù)進行下采樣，容易降低方差和計算復雜度。由于池窗口中計算均值/最大值/求和的速度很快，因此均值/最大值/求和池是實現(xiàn)此功能最原始、最有效的方法。Unexpected text node: ' 'hG?=mean/max/sum(h1T?,h2T?,?,hnT?)??Henaff等人[21]證明在一開始使用簡單的max/mean池化對于降低圖域的維度非常重要，并且能夠緩解圖傅里葉變換的巨大復雜度開銷。
??Defferrard等人在他們的方法ChebNet[12]中優(yōu)化了最大/最小池化并提出了一種有效的池化策略。首先對輸入圖進行如圖5（a）所示的粗化過程處理，然后將輸入圖的頂點和粗化后的圖進行轉(zhuǎn)換為一個平衡二叉樹，在最粗的層次上對節(jié)點任意地排序，然后將這個排序傳播到平衡二叉樹的較低層次，最后會在最細的層次上產(chǎn)生一個規(guī)則的排序。對重新排列的1D信號進行池化比對原始信號池化更高效。
??Zhang等人提出了一種DGCNN[55]框架，同樣對重新排列為有意義順序的頂點進行池化，與上述池化策略類似，叫SortPooling。不同的是，DCGNN根據(jù)節(jié)點在圖中的結(jié)構(gòu)角色（結(jié)構(gòu)特點）進行分類。將圖空間卷積得到的無序節(jié)點特征看作連續(xù)的WL colors[82]，以此進行節(jié)點排序。除此之外，還會將圖特征向量或截斷或擴展到固定圖大小k。如果n>kn>k,則將最后k?nk?n行刪除，反之，如果n&lt;kn<k，則在最后k?nk?n行補0.這種方法通過解決一個有挑戰(zhàn)性的底層圖結(jié)構(gòu)任務(wù)，也就是排列不變，增強了圖池化，從而提高了GCNs的性能。
??最近提出的DIFFPOOL[56]池化模塊能夠生成圖的層次表示，并且在端到端的模式種能夠與CNNs和各種GNNs結(jié)構(gòu)結(jié)合。DIFFPOOL不像其他粗化方法一樣對一個圖種的節(jié)點進行簡單的聚類，而是在一組輸入圖種提供一種通用的方法對節(jié)點進行層次化池化。通過學習ll層上的簇分配矩陣SS實現(xiàn)，S(l)∈Rn1×n1+1S(l)∈Rn1?×n1?+1。兩個包含輸入簇節(jié)點特征X(l)X(l)和粗化鄰接矩陣A(l)A(l)的獨立的GNN用來生成分配矩陣S(l)S(l)和嵌入矩陣Z(l)Z(l)：Z(l)=GNNl,embed(A(l),X(l))S(l)=softmax(GNNl,pool(A(l),X(l)))Z(l)=GNNl,embed?(A(l),X(l))S(l)=softmax(GNNl,pool?(A(l),X(l)))??任何標準的GNN模型都能夠?qū)崿F(xiàn)上述兩個公式，每個GNN模型處理相同的輸入數(shù)據(jù)，但是因為在框架的作用不同，所以有不同的參數(shù)。GNNl,embedGNNl,embed?生成新的嵌入，GNNl,poolGNNl,pool?生成輸入節(jié)點分配到nl+1nl+1?簇的概率。softmax函數(shù)對上述第二個公式按行操作，這樣，S(l)S(l)的每一行為ll層的nlnl?節(jié)點（或簇），S(l)S(l)每一列的對應(yīng)下一層的一個nlnl?。一旦確定了Z(l)Z(l)S(l)S(l)，池化操作定義如下：X(l+1)=S(l)TZ(l)∈Rnl+1×dA(l+1)=S(l)TA(l)S(l)∈Rnl+1×nl+1X(l+1)=S(l)TZ(l)∈Rnl+1?×dA(l+1)=S(l)TA(l)S(l)∈Rnl+1?×nl+1???第一個公式根據(jù)簇分配矩陣S(l)S(l)聚合嵌入Z(l)Z(l)，以計算nl+1nl+1?簇的嵌入。節(jié)點表示作為初始簇嵌入。第二個公式，將A(l)A(l)作為輸入，生成粗化鄰接矩陣，表示簇之間的連接強度。
??總的來說，DIFFPOOL利用兩個GNN重新定義了圖池化模型對節(jié)點進行聚類。所有的GCN模型都能夠與DIFFPOOL結(jié)合，不僅能夠提高性能，而且能夠加速卷積過程。

4.4 基于光譜和空間的GCNs的對比

??基于光譜的模型作為針對圖數(shù)據(jù)最早期的卷積網(wǎng)絡(luò)在很多圖相關(guān)的分析任務(wù)種取得了非常好的效果，這種模型最吸引人的地方在于在圖信號處理領(lǐng)域奠定了一個理論基礎(chǔ)。通過涉及新的圖信號濾波器[23]，能夠理論地涉及新的GCNs。但是，從效率，通用性和靈活性三個方面來說，基于光譜的方法有一些缺點。
??效率基于光譜的方法的計算量會隨著圖的大小急劇增加，因為模型需要同時計算特征向量[20]或者同時處理大圖，這就使得模型很難對大圖進行并行處理或縮放?；诳臻g的圖方法由于直接對圖域的鄰居節(jié)點進行聚合，所以有潛力處理大圖，方法是對一個batch數(shù)據(jù)計算而不是在整個圖上計算。如果鄰居節(jié)點的數(shù)量增加，能夠通過采樣技術(shù)[24,27]提高效率。
??通用性基于光譜的圖方法假設(shè)圖是固定的，因此對新的或者不同的圖泛化性能很差。基于空間的方法在每個節(jié)點上進行局部圖卷積，權(quán)值可以很容易地在不同地位置和結(jié)構(gòu)之間共享。
??靈活性基于譜的模型只適用于無向圖，譜方法用于有向圖的唯一方法是u將有向圖轉(zhuǎn)換為無向圖，因為沒有有向圖的拉普拉斯矩陣明確的定義。基于空間的模型可以將輸入合并到聚合函數(shù)中(如[13]、[17]、[51]、[52]、[53])，所以在處理多源輸入像是邊特征邊方向上更靈活。
??因此，近年來，基于空間的方法更受關(guān)注。

5 超GCNs架構(gòu)

??在這一節(jié)中，將對其他的圖神經(jīng)網(wǎng)絡(luò)，包括圖注意神經(jīng)網(wǎng)絡(luò)、圖自動編碼器、圖生成網(wǎng)絡(luò)和圖時空網(wǎng)絡(luò)進行回顧。表4總結(jié)了每個類別的主要方法。

5.1 圖注意力網(wǎng)絡(luò)

??注意力機制成為基于序列的任務(wù)的標準[90]，其優(yōu)點是能夠集中注意目標最重要的部分，在很多應(yīng)用，如機器翻譯，自然語言理解等都已經(jīng)證明注意力機制的有效性。由于注意力機制模型容量的增加，圖神經(jīng)網(wǎng)絡(luò)也因此受益，它可以在聚合過程中使用注意力，集成多個模型的輸出，并生成面向重要性的隨機游走。本節(jié)將討論如何在圖結(jié)構(gòu)數(shù)據(jù)中使用注意力機制。

5.1.1 GAN方法

圖注意網(wǎng)絡(luò)(GAT):?GAT理解
??上述關(guān)于GT的鏈接自認比較清楚。圖注意網(wǎng)絡(luò)(GAT)[15]是一種基于空間的圖卷積網(wǎng)絡(luò)，在聚合節(jié)點的鄰居信息的時候使用注意力機制確定每個鄰居節(jié)點對中心節(jié)點的重要性，也就是權(quán)重。定義如下：hti=σ(∑j∈Niα(ht?1i,ht?1j)Wt?1ht?1j)hit?=σ(j∈Ni?∑?α(hit?1?,hjt?1?)Wt?1hjt?1?)??其中α(?)α(?)表示注意力函數(shù)，能夠自動控制鄰居節(jié)點jj對中心節(jié)點的ii的貢獻。為了學習不同子空間的注意力信息，GAT 使用多頭注意力方式，并使用∥∥concat方式對不同注意力節(jié)點進行整合。hti=∥Kk=1σ(∑j∈Niαk(ht?1i,ht?1j)Wt?1kht?1j)hit?=∥k=1K?σ(j∈Ni?∑?αk?(hit?1?,hjt?1?)Wkt?1?hjt?1?)門控注意網(wǎng)絡(luò)（GAAN）：GAAN也利用多頭注意力的方式更新節(jié)點的隱層狀態(tài)。與GAT為各種注意力設(shè)置相同的權(quán)重進行整合的方式不同，GAAN引入自注意機制對每一個head(頭)，也就是每一種注意力，計算不同的權(quán)重，規(guī)則如下:hti=?o(xi⊕∥Kk=1gki∑j∈Niαk(ht?1i,ht?1j)?v(ht?1j))hit?=?o?(xi?⊕∥k=1K?gik?j∈Ni?∑?αk?(hit?1?,hjt?1?)?v?(hjt?1?))其中?o(?)?o?(?),?v(?)?v?(?)表示前饋神經(jīng)網(wǎng)絡(luò)，gkigik?表示第kk個注意力頭的權(quán)重。
圖注意模型(GAM)：GAM提出一種遞歸神經(jīng)網(wǎng)絡(luò)解決圖分類問題，通過自適應(yīng)訪問重要節(jié)點序列處理圖中信息豐富的部分。定義如下ht=fh(fs(rt?1,vt?1,g;θs),ht?1;θh)ht?=fh?(fs?(rt?1?,vt?1?,g;θs?),ht?1?;θh?)其中fh(?)fh?(?)是一個LSTM網(wǎng)絡(luò)，fsfs?是一個從當前節(jié)點vt?1vt?1?到他的一個鄰居節(jié)點ctct?的階躍網(wǎng)絡(luò),鄰居節(jié)點優(yōu)先考慮策略網(wǎng)絡(luò)生成的vt?1vt?1?中級別較高的類型rt=fr(ht;θr)rt?=fr?(ht?;θr?)其中rtrt?是表示節(jié)點重要性的隨機排序向量，需要以高度優(yōu)先進一步探討。htht?包含節(jié)點從圖探索中聚合的歷史信息，用來對圖標簽進行預測。
注意力游走[58]：注意力游走通過隨機游走學習節(jié)點嵌入。不用于使用固定先驗的深度游走（DeepWalk）不同，注意利用游走對可微注意力權(quán)重的共生矩陣進行分解：E[D]=P?(0)∑Ck=1ak(P)kE[D]=P(0)k=1∑C?ak?(P)k其中DD表示共生矩陣，P?(0)P(0)表示初始位置矩陣，PP表示概率轉(zhuǎn)移矩陣。

5.1.2 總括

??注意力機制對GNN的貢獻分為三個方面，在聚合特征信息的時候?qū)Σ煌泥従庸?jié)點分配不同的權(quán)值，根據(jù)注意力權(quán)重集成多個模型，使用注意力權(quán)重指導隨機游走。盡管將GAT[15]和GAAN[28]歸為圖的注意網(wǎng)絡(luò)的范疇，它們也同時是基于空間的GCN。GAT[15]和GAAN[28]的優(yōu)點是可以自適應(yīng)學習鄰居的重要性權(quán)重，如圖6所示。但是，由于必須計算每對鄰居之間的注意力權(quán)重，計算成本和內(nèi)存消耗迅速增加。

5.2 圖自編碼

??網(wǎng)絡(luò)嵌入致力于使用神經(jīng)網(wǎng)絡(luò)架構(gòu)將網(wǎng)絡(luò)頂點在低維向量空間進行表示，圖自編碼是網(wǎng)絡(luò)嵌入的一種類型。典型做法是利用多層感知機作為編碼器，獲得節(jié)點嵌入，然后解碼器據(jù)此重構(gòu)節(jié)點的鄰域統(tǒng)計信息，如正點態(tài)互信息(positive pointwise mutual information, PPMI)[41]或一階和二階近似[42]。近期，研究員探索將GCN[14]作為編碼器,設(shè)計圖自編碼器的時候或結(jié)合HCN與GAN[91]，或結(jié)合GAN與LSTM[7]。首先回顧基于GCN的自編碼器，然后總結(jié)該分類的其他變體。

5.2.1 基于GCN的自編碼器

圖自編碼(GAE)：GAE最早將GCN[14]整合到圖自編碼框架。編碼器定義為：Z=GCN(X,A)Z=GCN(X,A)解碼器定義為：A?=σ(ZZT)A=σ(ZZT)GAE的框架在圖5b展示?？梢杂米兎值姆绞接柧欸AE，也就是最小化變分下界LL：L=Eq(Z∣X,A)[logp(A∣Z)]?KL[q(Z∣X,A)∥p(Z)]L=Eq(Z∣X,A)?[logp?(A∣Z)]?KL[q(Z∣X,A)∥p(Z)]

對抗正則化圖自編碼器(ARGA)[16]：ARGA利用GANs的訓練方案[91]正則化圖自編碼器。其中，編碼器用節(jié)點的特征編碼其結(jié)構(gòu)信息，也就是GCN中的隱層表示，然后解碼器從編碼器的輸出中重構(gòu)鄰接矩陣。GANs在訓練生成模型的時候在生成和判別模型之間進行一個最小-最大博弈。生成器盡可能生成真實的“偽樣本”，而判別器則盡可能從真實樣本中識別”偽樣本“。GAN幫助ARGA正則化節(jié)點學習到的隱藏表示遵循先驗分布。具體來說，編碼器像生成器，盡可能使學習的節(jié)點的隱藏表示與真實的先驗分布難以區(qū)分，解碼器，可以看作判別器，盡可能識別所有的隱藏節(jié)點表示，無論節(jié)點隱藏是從編碼器生成的還是從一個真實的先驗分布得到的。

5.2.2 圖自編碼的其他變體

對抗正則化自編碼器網(wǎng)絡(luò)表示(NetRA)[62]：NetRA是與ARGA思想相似的一種圖自編碼框架，也是通過對抗訓練正則化節(jié)點隱藏表示遵循一種先驗分布。這種方法采用序列-序列結(jié)構(gòu)[92]恢復從隨機游走種取樣的節(jié)點序列，而不是重構(gòu)鄰接矩陣。
**圖表示深度神經(jīng)網(wǎng)絡(luò)(DNGR)[41]**通過堆疊去噪自編碼[93]重構(gòu)點態(tài)互信息矩陣（PPMI）。當圖被隨機游走序列化后，PPMI矩陣本質(zhì)上捕獲節(jié)點的共存信息。形式上，PPMI矩陣定義為：PPMIv1,v2=max(log(count(v1,v2)?∣D∣count(v1)count(v2)),0)PPMIv1?,v2??=max(log(count(v1?)count(v2?)count(v1?,v2?)?∣D∣?),0)其中∣D∣=∑v1,v2count(v1,v2)∣D∣=∑v1?,v2??count(v1?,v2?)，且v1,v2∈Vv1?,v2?∈V。堆疊的去噪自編碼能夠?qū)W習數(shù)據(jù)中潛在的高度非線性規(guī)律。與傳統(tǒng)的神經(jīng)自編碼器不同，它通過將輸入項隨機切換到零來增加輸入的噪聲。當存在缺失值時，學習到的隱式表示更具有魯棒性。
結(jié)構(gòu)深度網(wǎng)絡(luò)嵌入(SDNE)[42]:SDNE通過堆疊自編碼器，同時保留節(jié)點的一階和二階近似。一階近似定義為，節(jié)點和鄰居節(jié)點隱含表示之間的距離，一階近似表示的目標是，盡可能導出鄰接節(jié)點的表示。具體地，一階損失函數(shù)L1stL1st?定義為：L1st=∑ni,j=1Ai,j∥h(k)i?h(k)j∥2L1st?=i,j=1∑n?Ai,j?∥hi(k)??hj(k)?∥2二階近似定義為，節(jié)點輸入和其重構(gòu)輸入之間的距離，其中節(jié)點輸入是鄰接矩陣中節(jié)點對應(yīng)的行。二階近似的目標是保留一個節(jié)點的鄰居信息，具體地，二階近似的損失函數(shù)定義為：L2nd=∑ni=1∥(x?i?xi)⊙bi∥2L2nd?=i=1∑n?∥(xi??xi?)⊙bi?∥2向量bibi?對非零元素的懲罰多余零元素，因為輸入是高度稀疏化的。具體地：bij={1ifAi,j=0β>0ifAi,j=1bij?={1ifAi,j?=0β>0ifAi,j?=1?總體上，目標函數(shù)定義為L=L2nd+αL1st+λLregL=L2nd?+αL1st?+λLreg?其中LregLreg?是L2L2?正則項。
深度遞歸網(wǎng)絡(luò)嵌入 DRNE)[63]?直接重構(gòu)節(jié)點的隱含狀態(tài)而不是重構(gòu)整個圖的統(tǒng)計信息。DRNE使用聚合函數(shù)作為編碼器，損失函數(shù)為：L=∑v∈V∥hv?aggregate(huy∣u∈N(v))∥2(33)L=v∈V∑?∥hv??aggregate(hu?y∣u∈N(v))∥2(33)DRNE的創(chuàng)新之處在于選擇LSTRM作為聚合函數(shù)，其中鄰居序列按照節(jié)點度排列。

5.2.3 總結(jié)

??這些方法都學習節(jié)點嵌入，但是DNGR和SDNE只給定拓撲結(jié)構(gòu)，而GAE、ARGA、NetRA和DRNE不僅給定拓撲結(jié)構(gòu)而且給定節(jié)點內(nèi)容特性。圖自編碼的一個挑戰(zhàn)是鄰接矩陣的稀疏性，使解碼器的正項數(shù)遠少于負項數(shù)。為了解決這個問題，DNGR重構(gòu)了一個更緊密的矩陣即PPMI矩陣，SDNE對鄰接矩陣的零項進行了懲罰，GAE對鄰接矩陣中的項進行了加權(quán)，NetRA將圖線性化為序列。

5.3 圖生成網(wǎng)絡(luò)（GGN）

??圖生成網(wǎng)絡(luò)（GGN）的目標是，在給定一組觀察到的圖的前提下生成圖。很多圖生成方法是與特定領(lǐng)域相關(guān)的，例如，分子圖生成，一些方法是對分子圖進行字符串表示建模，叫做SMILES[94,95,96,97]，自然語言處理，以給定的句子[98,99]為條件生成語義圖或者知識圖。最近，提出了一些統(tǒng)一的生成方法，一些方法將生成過程看作交替生成節(jié)點和邊[64,65]，其他的方法利用生成對抗訓練[66,67]。GGN中的方法或者利用GCN作為構(gòu)建塊，或者使用不同的架構(gòu)。

5.3.1基于GCN的圖生成網(wǎng)絡(luò)

分子生成對抗網(wǎng)絡(luò)(MolGAN)[66]?MolGAN集成了關(guān)系GCN[100],增強GAN[101]和強化學習(RL)目標，生成期望屬性的圖。GAN包含一個生成器和一個判別器，兩者相互競爭以提高生成器的準確性。在MolGAN中，生成器嘗試生成一個“偽圖”包括他的特征矩陣，判別器則要區(qū)分偽樣本和經(jīng)驗數(shù)據(jù)。另外，與判別器并行，引入一個獎勵網(wǎng)絡(luò)，根據(jù)外部評價器，生成具有一定特性的圖。MolGAN框架如圖9所示：

?

圖的深度生成模型(DGMG)[65]?利用基于空間的圖的GCN來獲取現(xiàn)有圖的隱藏表示。生成節(jié)點和邊緣的決策過程取決于生成的圖的表示形式。簡單地說，DGMG遞歸地為一個生成圖生成節(jié)點，直到到達一個停止標準。在加入新節(jié)點后的每一步，DGMG重復判斷是否在加入的點之間加入邊，直到?jīng)Q策變?yōu)閒alse。如果決策為true,估計新加入的節(jié)點到每個現(xiàn)有節(jié)點連接的概率分布，并從概率分布中抽取一個節(jié)點作為樣本。當新的節(jié)點和連接加入到現(xiàn)有圖中以后，DGMG再一次更新圖表示。

5.3.2 GGN的其他變體

GraphRNN[64]?利用兩級循環(huán)神經(jīng)網(wǎng)絡(luò)開發(fā)深度圖生成模型。圖級RNN每次向節(jié)點序列添加一個新的節(jié)點，而邊級RNN生成二進制序列，表示新加入的節(jié)點與序列中之前生成的節(jié)點之間的連接。GraphRNN采用廣度優(yōu)先遍歷（BFS）策略，將圖線性化成節(jié)點序列，便于訓練圖級RNN。GraphRNN采用多變量伯努利分布或者條件伯努利分布建模二進制序列，訓練邊級RNN。
NetGAN[67]?NetGAN將LSTM[7]與Wasserstein GAN[102]結(jié)合，從一種基于隨機游走的方法生成圖形。GAN包含生成器和判別器兩個模型，生成器從一個LSTM盡最大可能生成似是而非的隨機游走，判別器從正確的隨機游走中盡可能區(qū)分偽隨機游走。訓練之后，通過對隨機游走集合中節(jié)點共生矩陣進行歸一化，得到一個新的圖。

5.3.3 總結(jié)

??對生成的圖進行評估仍然是一個難題。與人工合成圖像或者音頻不同，他們能夠直接被人類專家評估，生成的圖的質(zhì)量很難直觀檢測。MolGAN和DGMG利用外部知識來評估生成分子圖的有效性。GraphRNN和NetGAN通過圖統(tǒng)計信息(如節(jié)點度)評估生成的圖形。DGMG和GraphRNN依次生成節(jié)點和邊緣，MolGAN和NetGAN同時生成節(jié)點和邊緣。根據(jù)[68]，前一種方法的缺點是當圖變大時，對長序列建模是不現(xiàn)實的。后一種方法的挑戰(zhàn)是很難控制圖的全局屬性。最近一種方法[68]采用變分自編碼器通過生成鄰接矩陣來生成圖形，引入懲罰項來解決有效性約束。然而，由于具有nn個節(jié)點的圖的輸出空間為n2n2，這些方法都不能擴展到大型圖。

5.4 圖時空網(wǎng)絡(luò)

??圖時空網(wǎng)絡(luò)同時捕獲時空圖的時空依賴性。時空圖具有全局圖結(jié)構(gòu)，每個節(jié)點的輸入隨時間變化。例如，在交通網(wǎng)絡(luò)中，將每個傳感器作為一個節(jié)點，連續(xù)記錄某條道路的交通速度，其中交通網(wǎng)絡(luò)的邊由傳感器對之間的距離決定。圖時空網(wǎng)絡(luò)的目標是預測未來的節(jié)點值或標簽，或預測時空圖標簽。最近的研究探索了單獨使用GCNs[72]，結(jié)GCNs與RNN[70]或CNN[71]，以及一種為圖結(jié)構(gòu)定制的循環(huán)架構(gòu)[73]。下面將介紹這些方法。

5.4.1 基于GCN的圖時空網(wǎng)絡(luò)

擴散卷積遞歸神經(jīng)網(wǎng)絡(luò)(DCRNN)[70]?DCRNN引入擴散卷積作為圖卷積捕獲空間依賴性，用結(jié)合門控循環(huán)單元（GRU）[79]的序列-序列架構(gòu)[92]捕獲時間依賴性。
??擴散卷積對具有前向和后向的截斷擴散過程進行建模。形式上，擴散卷積定義為：X:,p?Gf(θ)=∑K?1k=0(θk1(D?1OA))k+θk2(D?1IAT)k)X:,pX:,p?G?f(θ)=k=0∑K?1?(θk1?(DO?1?A))k+θk2?(DI?1?AT)k)X:,p?其中DODO?是出度矩陣，DIDI?是入度矩陣。為了實現(xiàn)多輸入輸出通道，DCRNN提出了一種擴散卷積層，定義是如下Z:,q=σ(∑Pp=1X:,p?Gf(Θq,p,:,:))Z:,q?=σ(p=1∑P?X:,p?G?f(Θq,p,:,:?))其中，X∈RN×QX∈RN×Q,Z∈RN×QZ∈RN×Q,Θ∈RQ×P×K×2Θ∈RQ×P×K×2,QQ是輸出通道數(shù)量，PP是輸入通道數(shù)量。
??為了捕獲時間依賴性，DCRNN使用擴散卷積層對GRU的輸入進行處理，這樣循環(huán)單元同時獲得上一時刻的歷史信息，和圖卷積中的鄰域信息。DCRNN中改進的GRU叫做擴散卷積門控循環(huán)單元（DCGRU）：r(t)=sigmoid(Θr?G[X(t),H(t?1)]+br)u(t)=sigmoid(Θu?G[X(t),H(t?1)]+bu)C(t)=sigmoid(ΘC?G[X(t),(r(t)⊙H(t?1))+br)H(t)]=u(t)odotH(t?1)+(1?u(t))⊙C(t)r(t)=sigmoid(Θr?G?[X(t),H(t?1)]+br?)u(t)=sigmoid(Θu?G?[X(t),H(t?1)]+bu?)C(t)=sigmoid(ΘC?G?[X(t),(r(t)⊙H(t?1))+br?)H(t)]=u(t)odotH(t?1)+(1?u(t))⊙C(t)為了滿足多步預測的需要，DCGRN采用序列-序列結(jié)構(gòu)[92],其中循環(huán)單元由DCGRU代替。
CNN-GCN[71]?1D-CNN與GCN交織學習時空數(shù)據(jù)。對于一個輸入張量X∈RT×N×DX∈RT×N×D,1D-CNN層沿時間軸滑過X[:,i:]X[:,i:]?聚合每個節(jié)點的時間信息，同時GCN層在每個時間步作用于X[i,:,:]X[i,:,:]?聚合空間信息。輸出層是線性轉(zhuǎn)換，生成每個節(jié)點的預測。CNN-GCN框架在圖5?中展示。
時空GCN (ST-GCN)[72]?ST-GCN將時間流擴展為圖邊，因此能夠使用統(tǒng)一的GCN模型提取時空信息。ST-GCN定義了一個標簽函數(shù)，根據(jù)兩個相關(guān)節(jié)點的距離為圖的每條邊分配一個標簽。這樣，鄰接矩陣就可以表示為KK個鄰接矩陣的和，其中KK是標簽的個數(shù)。然后ST-GCN對每個KK鄰接矩陣使用不同權(quán)重的GCN[14]，然后求和。fout=∑jΛ?12jAjΛ?12jfinWjfout?=j∑?Λj?21??Aj?Λj?21??fin?Wj?

5.4.2 其他變體

Structural-RNN?Jain等[73]提出了一個名為Structural-RNN的遞歸結(jié)構(gòu)框架，主要目標是在每個時間步驟預測節(jié)點標簽。Structural-RNN由兩種RNN組成，即nodeRNN和edgeRNN。每個節(jié)點和邊的時間信息分別通過nodeRNN和edgeRNN。由于為不同節(jié)點和邊假設(shè)不同的RNN會顯著增加模型復雜度，所以取而代之，將節(jié)點和邊分割成語義組。例如，一個人-對象交互的圖包含兩組節(jié)點，人節(jié)點和對象節(jié)點，三組邊，人-人邊，人-對象邊，對象-對象邊。統(tǒng)一語義組的節(jié)點或者邊共享相同的RNN。將edgeRNN的輸出作為nodeRNN的輸入，以合并空間信息。

5.4.3 總結(jié)

??DCRNN由于利用了循環(huán)網(wǎng)絡(luò)架構(gòu)能夠處理長時間依賴關(guān)系。雖然CNN-GCN比DCRNN簡單，但是由于他首先實現(xiàn)了1D-CNN，所以在處理時空圖上更加高效。ST-GCN將時間流作為圖的邊，使鄰接矩陣的大小呈二次增長。一方面，增加了圖卷積層的計算成本。另一方面，為了捕獲長期依賴關(guān)系，圖卷積層必須多次疊加。Structural-RNN通過在相同的語義組共享相同的RNN提高了模型的有效性。但是，需要人類先驗知識來劃分語義組。

6 應(yīng)用

??GNN有廣泛的應(yīng)用。首先總結(jié)了文獻中頻繁使用的基準數(shù)據(jù)集，然后總結(jié)了四個常用數(shù)據(jù)集上的基準性能以及GNN的開源實現(xiàn)，最后，總結(jié)了GNN在各個領(lǐng)域的實際應(yīng)用。

6.1 基準數(shù)據(jù)集

??作者總結(jié)了該文章涉及的文獻中每個數(shù)據(jù)集使用的頻率，并在表5中展示了至少出現(xiàn)兩次的數(shù)據(jù)集。

分類	數(shù)據(jù)集	來源	#圖	#節(jié)點	#邊	#特征	#標簽	引文
引文網(wǎng)絡(luò)	Cora	[103]	1	2708	5429	1433	7	[14], [15], [23], [27], [45] [44], [46], [49], [58], [59],[61], [104]
	Citeseer	[103]	1	3327	4732	3703	6	[14], [15], [27], [46], [49] [58], [59], [61
	Pubmed	[103]	1	19717	44338	500	3	[14], [15], [27], [44], [45] [48], [49], [59], [61], [67]
	DBLP	dblp.uni-trier.de [105](aminer.org/citation)	1	—	—	—	—	[62], [67], [104], [106]
社交網(wǎng)絡(luò)	BlogCatalog	[107]	1	10312	333983	—	39	[42], [48], [62], [108]
	Reddit	[24]	1	232965	11606919	602	41	[24], [28], [45], [46]
	Epinions	www.epinions.com	1	—	—	—	—	[50], [106]
生物化學圖	PPI	[109]	24	56944	818716	50	121	[15], [19], [24], [27], [28] [46], [48], [62]
	NCI-1	[110]	4100	—	—	37	2	[26], [44], [47], [52], [57]
	NCI-109	[110]	4127	—	—	38	2	[26], [44], [52]
	MUTAG	[111]	188	—	—	7	2	[26], [44], [52]
	D&D	[112]	1178	—	—	—	2	[26], [47], [52]
	QM9	[113]	133885	—	—	—	13	[13], [66]
	tox21	tripod.nih.gov/tox21/challenge/	12707	—	—	—	12	[22], [53]
無結(jié)構(gòu)圖	MNIST	yann.lecun.com/exdb/mnist/	70000	—	—	—	10	[12], [20], [23], [52]
	Wikipedia	www.mattmahoney.net/dc/textdata	1	4777	184812	—	40	[62], [108]
	20NEWS	[114]	1	18846	—	—	20	[12], [41]
其他	METR-LA	[115]	—	—	—	—	—	[28], [70]
	Movie-Lens1M	[116]grouplens.org/datasets/	1	10000	1 Millinoi	—	—	[23], [108]
	Nell	[117]	1	65755	266144	61278	210	[14], [46], [49]

引文網(wǎng)絡(luò)：包括文章，作者及其關(guān)系，關(guān)系可以是引文，作者，共同作者。盡管引文網(wǎng)絡(luò)是有向圖，但是在評估關(guān)于節(jié)點分類，鏈接預測和節(jié)點聚類任務(wù)的模型性能時，通常被視為無向圖。引文網(wǎng)絡(luò)有三個流行的數(shù)據(jù)集，Cora，Citeseer和Pubmed。Cora包含2708個機器學習出版物，分為7個類。Citeseer包含3327篇科學論文，分為6個類。Cora，Citeseer中的每一篇論文都由獨熱向量表示，獨熱向量表示字典中的單詞是否被引用。Pubmed包含19717個與糖尿病相關(guān)的出版物，每一篇文章由逆文本頻率表示（IF-IDF）。此外，DBLP是一個有數(shù)百萬篇文章和作者的引文數(shù)據(jù)集，這些文章和作者都是從計算機科學書目中收集而來。可以在https://dblp.uni-trier.de上找到DBLP的原始數(shù)據(jù)集。 DBLP引文網(wǎng)絡(luò)的處理版本由https://aminer.org/citation持續(xù)更新。
社交網(wǎng)絡(luò)?數(shù)據(jù)根據(jù)在線服務(wù)如BlogCatalog，Reddit和Epinions等中的用戶交互形成。BlogCatalog是一個由博主和他們的社會關(guān)系形成的社交網(wǎng)絡(luò)。博主的標簽代表了他們的個人興趣。Reddit數(shù)據(jù)集是由Reddit論壇收集的帖子形成的無向圖。如果兩個如果包含同一個用戶的評論，這兩個帖子就會形成鏈接。每個帖子含有一個表示其所屬社區(qū)的標簽。Epinions數(shù)據(jù)集是從在線產(chǎn)品評論網(wǎng)站收集的多關(guān)系圖，其中評論者可以具有多種關(guān)系類型，例如信任，不信任，共同審查和共同評級。
化學/生物圖?化學分子和化合物可以用化學圖表示，原子作為節(jié)點，化學鍵作為邊緣。此類圖通常用于評估圖分類性能。 NCI-1和NCI-9數(shù)據(jù)集分別含有4100和4127種化合物，標記它們是否具有阻礙人癌細胞生長的活性。 MUTAG數(shù)據(jù)集包含188種硝基化合物，標記為是芳香族還是雜芳香族。 D＆D數(shù)據(jù)集包含1178個蛋白質(zhì)結(jié)構(gòu)，標記它們是酶還是非酶。 QM9數(shù)據(jù)集包含133885個分子，標簽是13種化學特性。 Tox21數(shù)據(jù)集包含12707種化合物，分為12種毒性。另一個重要的數(shù)據(jù)集是蛋白質(zhì) - 蛋白質(zhì)相互作用網(wǎng)絡(luò)（PPI）。它包含24個生物圖，其中節(jié)點表示蛋白質(zhì)，邊緣表示蛋白質(zhì)之間的相互作用。在PPI中，圖與人體組織關(guān)聯(lián)，節(jié)點標簽表示生物狀態(tài)。
非結(jié)構(gòu)化圖?為了測試GNN對非結(jié)構(gòu)化數(shù)據(jù)的泛化能力，k最近鄰圖（kNN圖）已被廣泛使用。 MNIST數(shù)據(jù)集包含70000張尺寸為28×28的圖像，并有十類數(shù)字。將MNIST圖像轉(zhuǎn)換為圖的典型方法是，基于其像素位置構(gòu)造8-NN圖形。Wikipedia數(shù)據(jù)集是從維基百科轉(zhuǎn)儲的前一百萬字節(jié)中提取的單詞共生網(wǎng)絡(luò)。單詞標簽代表詞性（POS）標簽。 20-NewsGroup數(shù)據(jù)集包含大約20,000個新聞組（NG）文本文檔，有20種新聞類型。通過將每個文檔表示為節(jié)點，并使用節(jié)點之間的相似性作為邊緣權(quán)重來構(gòu)造20-NewsGroup的圖。
其他?還有其他幾個值得一提的數(shù)據(jù)集。 METR-LA是從洛杉磯高速公路收集的交通數(shù)據(jù)集。來自MovieLens網(wǎng)站的MovieLens-1M數(shù)據(jù)集，包含由6k用戶提供的100萬項目評級。它是推薦系統(tǒng)的基準數(shù)據(jù)集。 NELL數(shù)據(jù)集是從Never-Ending Language Learning項目獲得的知識圖。它由涉及兩個實體及其關(guān)系的三元組組成。

6.2 開源項目

??在表5中列出的數(shù)據(jù)集中，Cora，Pubmed，Citeseer和PPI是最常用的數(shù)據(jù)集。在測試GCN在節(jié)點分類任務(wù)上的性能的時候，經(jīng)常在這些數(shù)據(jù)集上比較。圖6展示了這四個數(shù)據(jù)集的基準性能，其中所有的數(shù)據(jù)集使用標準數(shù)據(jù)分割。開源實現(xiàn)有助于深度學習研究中的基線實驗。如果沒有公開源代碼，由于存在大量超參數(shù)，就會很難達到文獻中提到的結(jié)果。表7展示4-5節(jié)種涉及的GNN模型的開源實現(xiàn)。值得注意的是，Fey等人 [86]在PyTorch發(fā)布了一個名為PyTorch Geometric 3的幾何學習庫，它實現(xiàn)了幾個圖形神經(jīng)網(wǎng)絡(luò)，包括ChebNet [12]，1stChebNet [14]，GraphSage [24]，MPNNs [13]，GAT [15]和SplineCNN [86] ]。最近發(fā)布的深度圖庫（DGL）4提高了許多GNN的快速實現(xiàn)，通過在流行深度學習平臺上，如PyTorch和MXNet等，提供一系列函數(shù)實現(xiàn)。
表6 對四個最常用數(shù)據(jù)集的性能進行基準測試

方法CoraCiteseerPubmedPPI

1stChebnet (2016) [14]	81.5	70.3	79.0	-
GraphSage (2017) [24]	-	-	-	61.2
GAT (2017) [15]	83.0±±?0.7	72.5±±?0.7	79.0±±?0.3	97.3±±?0.2
Cayleynets (2017) [23]	81.9±±?0.7	-	-	-
StoGCN (2018) [46]	82.0±±?0.8	70.9±±?0.2	79.0±±?0.4	07.9±±?0.04
DualGCN (2018) [49]	83.5	72.6	80.0	-
GAAN (2018) [28]	-	-	-	98.71±±?0.02
GraphInfoMax (2018) [118]	82.3±±?0.6	71.8±±?0.7	76.8±±?0.6	63.8±±?0.2
GeniePath (2018) [48]	-	-	78.5	97.9
LGCN (2018) [27]	83.3±±?0.5	73.0±±?0.6	79.5±±?0.2	77.2±±?0.2
SSE (2018) [19]]	-	-	-	83.6

表7 開源實現(xiàn)

模型框架GitHub鏈接

ChebNet (2016) [12]	tensorflow	https://github.com/mdeff/cnn_graph
1stChebNet (2017) [14]	tensorflow	https://github.com/tkipf/gcn
GGNNs (2015) [18]	lua	https://github.com/yujiali/ggnn
SSE (2018) [19]	C	https://github.com/Hanjun-Dai/steady_state_embedding
GraphSage (2017) [24]	tensorflow	https://github.com/williamleif/GraphSAGE
LGCN (2018) [27]	tensorflow	https://github.com/divelab/lgcn/
SplineCNN (2018) [86]	pytorch	https://github.com/rusty1s/pytorch_geometric
GAT (2017) [15]	tensorflow	https://github.com/PetarV-/GAT
GAE (2016) [59]	tensorflow	https://github.com/limaosen0/Variational-Graph-Auto-Encoders
ARGA (2018) [61]	tensorflow	https://github.com/Ruiqi-Hu/ARGA
DNGR (2016) [41]	matlab	https://github.com/ShelsonCao/DNGR
SDNE (2016) [42]	python	https://github.com/suanrong/SDNE
DRNE (2016) [63]	tensorflow	https://github.com/tadpole/DRNE
GraphRNN (2018) [64]	tensorflow	https://github.com/snap-stanford/GraphRNN
DCRNN (2018) [70]	tensorflow	https://github.com/liyaguang/DCRNN
CNN-GCN (2017) [71]	tensorflow	https://github.com/VeritasYin/STGCN_IJCAI-18
ST-GC(2018)[72]	pytorch	https://github.com/yysijie/st-gcn
Structural RNN (2016) [73]	theano	https://github.com/asheshjain399/RNNexp

6.3 實際應(yīng)用

??GNN在不同的任務(wù)和領(lǐng)域中有廣泛的應(yīng)用。盡管每類GNN針對一些通用任務(wù)都是具體化的，包括節(jié)點分類，節(jié)點表示學習，圖分類，圖生成和時空預測，GNN仍然可以應(yīng)用于節(jié)點聚類，鏈接預測[119]和圖分區(qū)[120]。本節(jié)主要根據(jù)它們所屬的一般領(lǐng)域介紹實際應(yīng)用。

6.3.1計算機視覺

??GNN的最大應(yīng)用領(lǐng)域之一是計算機視覺。研究人員在場景圖生成，點云分類和分割，動作識別以及許多其他方向中利用圖結(jié)構(gòu)來實現(xiàn)進行了探索。
??在場景圖生成中，目標之間的語義關(guān)系有助于理解視覺場景背后的語義。給定圖像，場景圖生成模型檢測和識別目標并預測目標對之間的語義關(guān)系[121]，[122]，[123]。另一個應(yīng)用是在給定場景圖的情況下生成逼真的圖像[124]，與上述過程相反。由于自然語言可以被解析為語義圖，其中每個單詞代表一個對象，因此在給定文本描述的情況下合成圖像是一種很有前途。
??在點云分類和分割中，點云是由LiDAR掃描記錄的一組3D點。該任務(wù)的解決方案使LiDAR設(shè)備能夠看到周圍環(huán)境，通常對無人駕駛有益。為了識別由點云描繪的物體，[125]，[126]，[127]，將點云轉(zhuǎn)換為k-最近鄰圖或超點圖，并使用GCN來探索拓撲結(jié)構(gòu)。
??在動作識別中，識別視頻中包含的人體動作有助于從機器方面更好地理解視頻內(nèi)容。一種解決方案是檢測視頻剪輯中人體關(guān)節(jié)的位置。由骨架鏈接的人體關(guān)節(jié)自然形成圖，給定人類關(guān)節(jié)位置的時間序列，[72]，[73]應(yīng)用時空神經(jīng)網(wǎng)絡(luò)來學習人類行為模式。
??此外，在計算機視覺中應(yīng)用GNN的可能方向的數(shù)量仍在增長。包括小樣本圖像分類[128]，[129]，語義分割[130]，[131]，視覺推理[132]和問答QA系統(tǒng)[133]。

6.3.2推薦系統(tǒng)

??基于圖的推薦系統(tǒng)將條目和用戶作為節(jié)點。通過利用條目和條目，用戶和用戶，用戶和條目以及內(nèi)容信息之間的關(guān)系，基于圖形的推薦系統(tǒng)能夠提供高質(zhì)量的推薦。推薦系統(tǒng)的關(guān)鍵是將條目的重要性評分給用戶，可以被轉(zhuǎn)換為鏈接預測問題，目標是預測用戶和條目之間缺失的鏈接。為了解決這個問題，范等人 [9]和Ying等人 [11]提出一個基于GCN的圖自編碼器。 Monti等人 [10]結(jié)合GCN和RNN來學習產(chǎn)生已知評級的基礎(chǔ)過程。

6.3.3交通

??交通擁堵已成為現(xiàn)代城市的熱門社會問題。準確預測交通網(wǎng)絡(luò)中的交通速度，交通量或道路密度對于路線規(guī)劃和流量控制至關(guān)重要。 [28]，[70]，[71]，[134]采用的是與時空神經(jīng)網(wǎng)絡(luò)結(jié)合的圖方法。模型輸入是時空圖，節(jié)點表示放置在道路上的傳感器，邊緣表示成對節(jié)點的距離高于閾值，并且每個節(jié)點包含時間序列作為特征。目標是在一個時間間隔內(nèi)預測道路的平均速度。另一個有趣的應(yīng)用是出租車需求預測，能夠幫助智能交通系統(tǒng)有效利用資源，有效節(jié)約能源。根據(jù)歷史出租車需求，位置信息，天氣數(shù)據(jù)和事件特征，Yao等人[135]結(jié)合LSTM，CNN和由LINE [136]訓練的節(jié)點嵌入，形成每個位置的聯(lián)合表示，以預測在一個時間間隔內(nèi)該位置所需的出租車數(shù)量。

6.3.4生物化學

??在化學領(lǐng)域，研究人員應(yīng)用GNN來研究分子的圖形結(jié)構(gòu)。在分子圖中，節(jié)點表示原子，邊表示化學鍵。節(jié)點分類，圖分類和圖生成是分子圖的三個主要任務(wù)，能夠?qū)W習分子指紋[53]，[80]，預測分子特性[13]，推斷蛋白質(zhì)界面[137]，并合成化學品化合物[65]，[66]，[138]。

6.3.5其他

??初步探索將GNN應(yīng)用于其他問題，如程序驗證[18]，程序推理[139]，社會影響預測[140]，對抗性攻擊預防[141]，電子健康記錄建模[142]，[ 143]，事件檢測[144]和組合優(yōu)化[145]。

7 未來發(fā)展方向

??盡管已經(jīng)證明了GNN在學習圖數(shù)據(jù)方面的能力，但由于圖的復雜性，仍然存在挑戰(zhàn)。在本節(jié)中，我們提供了圖神經(jīng)網(wǎng)絡(luò)的四個未來方向。

7.1 Go Deep

??深度學習的成功在于深層神經(jīng)架構(gòu)。例如，在圖像分類中，杰出的ResNet [146]的具有152個層。然而，當談到圖時，實驗研究表明，隨著層數(shù)的增加，模型性能急劇下降[147]。根據(jù)[147]，這是由于圖卷積推動了相鄰節(jié)點的表示更接近，因此理論上，無限次卷積，所有節(jié)點的表示將收斂到單個點。這就涉及一個問題，在學習圖結(jié)構(gòu)數(shù)據(jù)的時候，更深的網(wǎng)絡(luò)是否是一個好的策略。

7.2 Receptive Filed

??節(jié)點的感受野是指包括中心節(jié)點及其鄰居的一組節(jié)點。節(jié)點的鄰居數(shù)量遵循冪律分布。一些節(jié)點可能只有一個鄰居，而其他節(jié)點可能有多達幾千個鄰居。雖然[24]，[26]，[27]采用了采樣策略，但如何選擇節(jié)點的代表性感受野仍有待探索。

7.3 Scalability

??大多數(shù)GNN不能很好地適應(yīng)大型圖。其主要原因是當堆疊多個GCN時，節(jié)點的最終狀態(tài)涉及其大量鄰居的隱藏狀態(tài)，導致反向傳播的高復雜性。雖然有幾種方法試圖通過快速采樣[45]，[46]和子圖訓練[24]，[27]來提高模型效率，但它們?nèi)匀徊痪哂凶銐虻目蓴U展性來處理具有大圖的深層架構(gòu)。

7.4 Dynamics and Heterogeneity

??大多數(shù)當前的圖神經(jīng)網(wǎng)絡(luò)都采用靜態(tài)齊次圖來處理。一方面，假設(shè)圖結(jié)構(gòu)是固定的。另一方面，假設(shè)圖中的節(jié)點和邊緣來自單個源。然而，在許多情況下，這兩個假設(shè)是不現(xiàn)實的。在社交網(wǎng)絡(luò)中，新人可以在任何時間進入網(wǎng)絡(luò)，并且現(xiàn)有人也可以退出網(wǎng)絡(luò)。在推薦系統(tǒng)中，產(chǎn)品可以具有不同的類型，其輸入可以具有不同的形式，例如文本或圖像。因此，應(yīng)該開發(fā)新的方法來處理動態(tài)和異構(gòu)圖結(jié)構(gòu)。

8 總括

??在本次調(diào)查中，我們對GNN進行了全面的概述。 我們提供了一種分類法，將圖神經(jīng)網(wǎng)絡(luò)分為五類：圖卷積網(wǎng)絡(luò)，圖注意網(wǎng)絡(luò)，圖自編碼器，圖生成網(wǎng)絡(luò)和圖時空網(wǎng)絡(luò)。 我們對類內(nèi)或類之間的方法進行全面的回顧，比較和總結(jié)。 然后我們介紹了圖神經(jīng)網(wǎng)絡(luò)的廣泛應(yīng)用。 總結(jié)了圖神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)集，開源代碼和基準。 最后，我們提出了圖形神經(jīng)網(wǎng)絡(luò)的四個未來方向。

總結(jié)

以上是生活随笔為你收集整理的图神经网络综述的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。