1.介紹

論文研究了gnn中的其他計算模塊，如跳過連接和池化操作。

Skip Connections（或 Shortcut
Connections），跳過連接，會跳過神經網絡中的某些層，并將一層的輸出作為下一層的輸入。

gnn分為四類:循環圖神經網絡、卷積圖神經網絡、圖自編碼器和時空圖神經網絡。

論文討論了異構圖、動態圖和組合優化的gnn

論文的貢獻是:提供了對現有圖神經網絡模型的詳細回顧。提出了一個通用的設計管道，并討論了每個模塊的變體。本文還介紹了GNN模型的理論研究和實證分析。我們對應用程序進行系統分類，將應用程序分為結構化場景和非結構化場景。我們針對每個場景給出了幾個主要的應用程序及其相應的方法。我們提出四個有待進一步研究的問題。我們對每個問題進行了深入的分析，并提出了未來的研究方向。

2.GNN模型設計的一般流程：

該流程包括四個步驟:(1)查找圖的結構，(2)確定圖的類型和比例，(3)設計損失函數，(4)使用計算模塊構建模型。

2.1查找圖結構

必須找出應用程序中的圖結構。通常有兩種場景:結構化場景和非結構化場景。在結構型場景中，圖形結構在分子、物理系統、知識圖等應用中是明確的。在非結構化場景中，圖是隱式的，因此我們必須首先從任務中構建圖，例如為文本構建一個完全連接的“單詞”圖，或為圖像構建一個場景圖。在我們得到這個圖之后，后面的設計過程試圖在這個特定的圖上找到一個最優的GNN模型。

2.2確定圖的類型和比例

在應用程序中獲得圖形后，我們必須找出圖形類型及其比例。具有復雜類型的圖可以提供關于節點及其連接的更多信息。圖表通常被分類為:

有向圖/無向圖：有向圖中的邊都是從一個節點指向另一個節點，這比無向圖提供了更多的信息。無向圖中的每條邊也可以看作是兩條有向邊。

同構圖/異構圖：同構圖中的節點和邊具有相同的類型，異構圖中的節點和邊具有不同的類型。節點和邊的類型在異構圖中起著重要的作用，需要進一步考慮。

靜態圖/動態圖：當圖的輸入特征或拓撲隨時間變化時，將圖視為動態圖。在動態圖中應該仔細考慮時間信息。

注意，這些類別是正交的，這意味著這些類型可以組合，例如，可以處理動態有向異構圖。還有一些其他的圖類型是為不同的任務設計的，比如超圖和符號圖。我們不會在這里列舉所有類型，但最重要的想法是考慮這些圖表提供的附加信息。一旦我們指定了圖形類型，在設計過程中應該進一步考慮這些圖形類型提供的附加信息。在圖的尺度上，對于小圖和“大”圖并沒有明確的分類標準。這個標準仍然隨著計算設備(例如gpu的速度和內存)的發展而變化。在本文中，當一個圖(空間復雜度isOen2T)的鄰接矩陣或圖拉普拉斯算子不能被設備存儲和處理時，我們將該圖視為一個大規模圖，然后考慮一些采樣方法。

2.3設計損失函數

在這一步中，我們需要根據我們的任務類型和訓練設置來設計損失函數。對于圖學習任務，通常有三種任務:

節點層數：任務以節點為中心，包括節點分類、節點回歸、節點聚類等。節點分類試圖將節點分類為幾個類，節點回歸預測每個節點的連續值。節點聚類的目的是將節點劃分為幾個不相交的組，相似的節點應該在同一組中。

邊層數：任務是邊緣分類和鏈接預測，這需要模型對邊緣類型進行分類或預測給定的兩個節點之間是否存在一條邊

圖層數：任務包括圖分類、圖回歸和圖匹配，所有這些都需要模型來學習圖的表示。

從監督的角度，我們也可以將圖學習任務分為三種不同的訓練設置:

監督環境：為訓練提供標記數據

半監督環境：為訓練提供了少量的標記節點和大量的未標記節點。在測試階段，轉導設置要求模型預測給定的未標記節點的標簽，而歸納設置提供來自相同分布的新的未標記節點來推斷。大多數節點和邊緣分類任務是半監督的。最近，wang和Leskovec(2020)以及rossi等人(2018)提出了一種混合的轉導-誘導方案，尋求通向混合環境的新途徑。

非監督環境：只提供未標記的數據供模型查找模式。節點聚類是典型的無監督學習任務。

通過任務類型和訓練設置，我們可以為任務設計一個特定的損失函數。例如，對于節點級半監督分類任務，交叉熵損失函數可以用于訓練集中標記的節點。

2.4使用計算模塊構建模型

最后，我們可以開始使用計算模塊構建模型。一些常用的計算模塊有:

傳播模塊：傳播模塊用于在節點之間傳播信息，從而聚合的信息既可以捕獲特征信息，也可以捕獲拓撲信息。在傳播模塊中，通常使用卷積算子和遞歸算子來聚合鄰居的信息，而跳過連接操作則用來從節點的歷史表示中收集信息，從而緩解過平滑問題

采樣模塊：當圖較大時，通常需要采樣模塊對圖進行傳播。采樣模塊通常與傳播模塊結合使用。

池化模塊：當我們需要高級子圖或圖的表示時，需要池模塊從節點中提取信息

利用這些計算模塊，通常將它們結合起來建立一個典型的GNN模型。圖的中間部分給出了GNN模型的典型結構。其中利用卷積算子、遞歸算子、采樣模塊和跳躍連接在每一層傳播信息，然后加入池化模塊提取高層信息。這些層通常是堆疊起來以獲得更好的表示。注意，這種架構可以推廣大多數GNN模型，但也有例外，例如，NDCN
(zan和Wang,
2020)結合了常微分方程系統(ode)和GNN。它可以被看作是一個連續時間的GNN模型，在連續時間內集成GNN層，而不通過一個離散的層數傳播。圖中顯示了通用設計管道的說明。

3.計算模塊的實例化

在本節中，我們將介紹三個計算模塊的現有實例化:傳播模塊、采樣模塊、和池化模塊。我們分別在3.1節、3.2節和3.3節中介紹了傳播模塊的三個子組件:卷積算子、遞歸算子和跳躍連接。然后在3.4節和3.5節中介紹了采樣模塊和池模塊。GNN模型的一般設計管道和計算模塊的概述如圖所示

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Vga46pqA-1638176337186)(media/cf6c624f2cbfe45a80388f36ee8c3c71.png)]

GNN模型的一般設計管道

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-XogT6oK8-1638176337190)(media/20fbc7992e7d7d79bcd5dacff7fe7029.png)]

計算模塊的概述

3.1傳播模塊-卷積算子

本節介紹的卷積算子是GNN模型中最常用的傳播算子。卷積算子的主要思想是將卷積從其他域推廣到圖域。這方面的進展通常分為光譜方法和空間方法。

3.1.1譜方法

譜方法使用圖的譜表示。這些方法在理論上基于圖信號處理(Shuman et al.，
2013)，并在譜域定義卷積算子。在譜方法中，首先通過圖的傅里葉變換f將圖信號變換到譜域，然后進行卷積運算。卷積后，結果信號用反圖傅里葉變換f
’ 1進行變換。這些轉換定義為:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-jFmEvjzr-1638176337192)(media/50892b9a0d95ed715a1abd8babf20312.png)]

這里是歸一化圖拉普拉斯特征向量的矩陣：（其中為N維單位向量）D是度矩陣，是圖的鄰接矩陣，歸一化圖拉普拉斯算子是實對稱正半正定的，所以它可以分解為
Λ是特征值的對角矩陣，基于卷積定理(Mallat, 1999)，將卷積運算定義為:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-wT4gajlR-1638176337195)(media/ee7393a65381a21fa2bcf3337f0b1de2.png)]

其中為光譜域的濾波器，如果我們簡化過濾器通過使用一個可學習的對角矩陣，然后我們有了光譜方法的基本函數：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-jPAFuAf5-1638176337197)(media/aee2a34825acc14d08f5c04807d632dc.png)]

接著介紹了幾種設計不同濾波器的典型光譜方法 。

光譜網絡：光譜網絡使用可學習對角矩陣作為濾波器，這是=diag(w),

是作為參數，然而，這種操作的計算效率很低，而且過濾器是非空間本地化的。Henaff等人(2015)試圖通過引入光滑系數參數化來實現光譜濾波器的空間局部化。

ChebNet：Hammond等人(2011)認為可以通過切比雪夫多項式上升到排序，Defferrard等(2016)基于這一理論提出了ChebNet。因此，這個運算可以寫成：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-2R6aldaZ-1638176337199)(media/a97e0d69d79f7231fef813fba3b8d51f.png)]

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-ONTYySV9-1638176337202)(media/20b5204605289825fadacc359eff1884.png)]表示L的最大特征值。的取值范圍是[-1,1],

是切比雪夫系數的向量。

切比雪夫多項式定義為當=1和=x

由于在拉普拉斯變換中是一個k階多項式，因此可以看出操作風險是局部化的。Defferrard等人(2016)使用這種k
- localized來定義卷積神經網絡，它可以消除計算拉普拉斯特征向量的需要。

Kipf簡化了Eq中的卷積運算，當K=1來緩解過擬合的問題，他們進一步假設，并將方程簡化成

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-w3Abxdzj-1638176337204)(media/36c1b2bb4f4cc945feee9c72764d3984.png)]

有兩個自由參數w0和w1。使用參數約束w=w0=-w1下，我們可以得到以下表達式:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-R8rt0GZj-1638176337207)(media/e1921297b1eb2220887c0c8f02679be5.png)]

GCN進一步引入了正則化技巧來解決Eq中的爆炸/消失梯度問題[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-O3AMfrjE-1638176337210)(media/275c13aae694bde7cbfd368b30aaae0c.png)]有[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-pQ5KmVka-1638176337212)(media/29fa95e19d8c42f9ce7579af01d0c0b3.png)]最后，GCN的緊湊型定義為:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-lhoS1ijG-1638176337214)(media/fe9b015c3222a8fa0a94f4f99fa42796.png)]

其中[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-PxPzpIV7-1638176337217)(media/a78072d662537ff495070257570fd89d.png)]是輸入矩陣，[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-3Oiq7WUw-1638176337219)(media/4b7f33ac2dccd2b743db17012fcd81de.png)]是參數，并且

是卷積矩陣，F和F’分別是輸入和輸出的尺寸，注意GCN也可以被視為一種空間方法，將在后面討論。

AGCN：所有這些模型都使用原始的圖結構來表示節點之間的關系。然而，不同節點之間可能存在隱式關系。自適應圖卷積網絡(Adaptive
Graph Convolution Network, AGCN)被提出學習底層關系(Li et al.，
2018a)。AGCN學習一個“殘差”圖拉普拉斯矩陣，并將其添加到原始拉普拉斯矩陣中。結果表明，該方法在幾種圖結構數據集上是有效的。

DGCN：雙重圖卷積網絡(DGCN) (Zhuang and Ma,
2018)被提出來聯合考慮圖的局部一致性和全局一致性。該算法使用兩個卷積網絡捕獲局部和全局一致性，并采用無監督損失對它們進行集成。第一個卷積網絡與式(7)相同，第二個網絡用正的PPMI
(point - twise mutual information)矩陣替換鄰接矩陣:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-cgnuBypT-1638176337222)(media/c1f40af14b2bedc92ce5b8bc81c0d775.png)]

其中Ap為PPMI矩陣，Dp為Ap的對角度矩陣

GWNN：圖小波神經網絡(GWNN) (Xu et al.，
2019a)采用圖小波變換代替圖傅立葉變換。它具有以下幾個優點:(1)無需矩陣分解即可快速得到圖小波;(2)圖小波是稀疏的和局域的，因此結果更好，更容易解釋。在半監督節點分類任務中，GWNN優于幾種譜方法。

ACGN和DGCN試圖從增廣圖拉普拉斯的角度改進了光譜方法，而GWNN代替了傅里葉變換。總之，光譜方法很好地基于理論，最近也提出了一些理論分析(見第7.1.1節)。然而，在上述幾乎所有的光譜方法中，學習的濾波器依賴于圖結構。也就是說，過濾器不能應用于具有不同結構的圖，而那些模型只能在圖任務的“轉換”設置下應用。

3.1.2基本空間的方法

空間方法基于圖拓撲直接在圖上定義卷積。空間方法的主要挑戰是定義不同大小的鄰域的卷積操作，并保持cnn的局部不變性。

Neural FPs：Neural FPs對不同程度的節點使用不同的權重矩陣:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-fB7zdkKV-1638176337223)(media/70398a434f41aa574c840ef04fda413c.png)]

其中 作為節點權重矩陣。該方法的主要缺點是不能應用于具有更多節點度的大規模圖

DCNN：擴散卷積神經網絡(DCNN) (Atwood and Towsley,
2016)使用過渡矩陣為節點定義鄰域。對于節點分類，圖中每個節點的擴散表示可以表示為:
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-onFzo47A-1638176337225)(media/82e19667e506605b941682aa515691f4.png)]

是輸入特征矩陣（F是維數）P*是一個N*K*N的張量，其中包含矩陣P的冪級數{P，P^2,…，P^k}并且P是圖鄰接矩陣A的度歸一化轉換矩陣，每個實體被轉換為擴散卷積表示，即K*F矩陣定義為???

PATCHY-SAN: PATCHY-SAN模型(Niepert et al.，
2016)精確地提取并規范化每個節點的鄰域。在傳統的卷積運算中，歸一化鄰域作為接收場。

LGCN: 可學習圖卷積網絡(LGCN) (Gao et al.，
2018a)也利用cnn作為聚合器。它對節點的鄰域矩陣進行最大池化，得到top-k個特征元素，然后應用一維CNN計算隱藏表示

可學習圖卷積網絡(LGCN) (Gao et al.，
2018a)也利用cnn作為聚合器。它對節點的鄰域矩陣進行最大池化，得到top-k個特征元素，然后應用一維CNN計算隱藏表示

GraphSAGE: GraphSAGE
(Hamilton等人，2017a)是一個通用的歸納框架，通過從節點的局部鄰域取樣和聚合特征來生成嵌入:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-3WGtuMLd-1638176337228)(media/9de2ceb873c5689b90efadebdf1ef581.png)]

GraphSAGE不使用完整的領域集，而是統一采樣固定大小的鄰居集來聚合信息。是聚合函數，GraphSAGE提出了三種聚合器:均值聚合器、LSTM聚合器和池化聚合器。帶有平均聚合器的GraphSAGE可以看作是GCN的歸納版本，而LSTM聚合器不是置換不變的，它需要指定節點的順序。

3.1.3引起空間的方法

注意機制已成功應用于許多序列任務，如機器翻譯(Bahdanau et al.， 2015;Gehring et
al.， 2017;Vaswani et al.， 2017)，機器閱讀(Cheng et al.，
2016)等。還有幾個模型試圖在圖上推廣注意操作符(Velickovic et al.，
2018;張等，2018c)。與前面提到的算子相比，基于注意的算子對鄰居分配了不同的權重，從而可以緩解噪聲，取得更好的效果。

GAT：圖表注意網絡(GAT) (Velickovic et al.，
2018)將注意機制整合到傳播步驟中。它通過關注它的鄰居來計算每個節點的隱藏狀態，遵循自我注意策略。節點的隱藏狀態可以通過以下方法獲得:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-ntdPMxF1-1638176337230)(media/a208e740e985dd1561ddfe078916baad.png)]

其中W是權矩陣與應用于每個節點的線性變換相關聯。
a是單層MLP的權向量，此外，GAT利用了vaswani等人(2017)使用的多頭注意來穩定學習過程。它使用獨立的注意力頭矩陣來計算隱藏狀態，然后連接它們的特征(或計算平均值)，導致以下兩種情況輸出的表示。

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-ZqxQJVic-1638176337232)(media/d6db65e9ae4db4ff73fa5e928ae643d6.png)]

這里是由第k次注意頭計算的歸一化注意系數。該注意結構具有以下幾個特點:(1)節點-鄰居對的計算是并行的，因此操作是高效的;(2)通過對相鄰節點指定任意權重，可以應用于不同度的圖節點;(3)易于應用于歸納學習問題。

GaAN：門控式注意網絡(GaAN) (Zhang et al.，
2018c)也使用了多頭注意機制。但是，它使用一種自我注意機制從不同的頭部收集信息，取代GAT的平均操作。

3.1.4空間方法的一般框架

除了空間方法的不同變體外，還提出了幾種通用框架，旨在將不同的模型整合到一個單一的框架中。Monti等人(2017)提出了混合模型網絡(MoNet)，它是定義在圖或流形上的幾種方法的一般空間框架。Gilmer
et al.(2017)提出了消息傳遞神經網絡(MPNN)，它使用消息傳遞函數統一多種變體。Wang
et al. (2018a)提出了非局部神經網絡(non-local neural network,
NLNN)，它結合了幾種“自我注意”式的方法(Hoshen, 2017;Vaswani et al.，
2017;Velickovic et al.，
2018)。Battaglia等(2018)提出了圖網絡(GN)。它定義了一個更通用的框架，用于學習節點級、邊級和圖級表示

MoNet: 混合模型網絡(MoNet)
(Monti等人，2017)是一個空間框架，試圖統一非歐幾里德域的模型，包括流形和gnn的cnn。在流形上的Geodesic
CNN (GCNN) (Masci等人，2015年)和各向異性CNN (ACNN)
(Boscaini等人，2016年)或圖上的GCN (Kipf和Welling, 2017年)和DCNN
(Atwood和Towsley,
2016年)可以作為莫奈的具體實例。在莫奈的作品中，流形上的每一點或圖上的每一個頂點(用v表示)都被認為是偽坐標系的原點。

與偽坐標uev;uT相關聯的neighborsu2Nvare。給定在圖(或流形上的點)的頂點上定義的兩個函數f,g，在MoNet中卷積算子定義為:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-14hU3x1X-1638176337235)(media/0d9051d4b1b82268ef442d2e0cb6131c.png)]

給定w1(u),w2(u)….wj(u)函數根據偽坐標為鄰居分配權重，因此為鄰居函數的聚合值，通過定義不同的u和w，MoNet可以實例化幾種方法。對于GCN，函數f,g將節點映射到他們的特征。[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-ElA7Nt1h-1638176337237)(media/624b8fee5a26a853bfe893abb3cc3a26.png)]

MPNN：消息傳遞神經網絡(MPNN) (Gilmer et al.，
2017)提取了幾個經典模型的一般特征。該模型包含兩個階段:消息傳遞階段和讀出階段。

在消息傳遞階段，模型首先使用消息函數，Mt來聚合消息。從鄰居并且使用更新函數來更新隱藏隱藏狀態

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-IlEfQiUV-1638176337239)(media/b635551cc67be73516dfef84080b37ea.png)]

給定表示無向邊(v,u)的特征，讀出階段使用讀出函數R計算出整個圖的特征向量:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-tVDU7EFG-1638176337241)(media/7c53877ccfd67b89ac44f1a360f40400.png)]

其中T表示總時間步長。消息函數Mt，頂點更新函數Ut和讀取函數R可能有不同的設置，因此，MPNN框架可以通過不同的函數設置實例化幾個不同的模型。不同模型的具體設置可以在(Gilmer
et al.， 2017)中找到。

MLNN：非局部神經網絡(NLNN)推廣并擴展了計算機視覺中經典的非局部平均操作(Buades et
al.，
2005)。非局部運算將一個位置上的隱藏狀態計算為所有可能位置上特征的加權和。可能的位置可以是在空間，時間或時空中。因此，NLNN可以被看作是不同“自我關注”風格方法的統一(Hoshen,
2017;Vaswani等人，2017;Velickovic等人，2018)。

非局部神經網絡(NLNN)推廣并擴展了計算機視覺中經典的非局部平均操作(Buades et al.，
2005)。非局部運算將一個位置上的隱藏狀態計算為所有可能位置上特征的加權和。可能的位置可以是在空間，時間或時空中。因此，NLNN可以被看作是不同“自我關注”風格方法的統一(Hoshen,
2017;Vaswani等人，2017;Velickovic等人，2018)。

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-OhF26T1v-1638176337243)(media/c51e520012a57ce7fd1e02181ad51387.png)]

其中u是所有可能位置的索引，計算v和u之間的范圍表示他們之間的關系。表示一個轉換，[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-atPUXa5B-1638176337245)(media/43acf8f928660bab2882ca0e0368cd96.png)]是一個歸一化因子。不同的NLNN變體可以通過不同的設置來定義，更多的細節可以在原始論文中找到(Buades
et al.， 2005)。

Graph NetWork ：圖網絡(GN) (Battaglia et al.，
2018)通過學習節點級、邊級和圖級表示，與其他框架相比，是一個更通用的框架。它可以統一許多變種，如MPNN,
NLNN，交互網絡(Battaglia等人，2016;Watters等人，2017)，神經物理引擎(Chang等人，2017)，CommNet
(Sukhbaatar Ferguset al.， 2016)， structure2vec
(Dai等人，2016;Khalil等人，2017)，

GN的核心計算單元稱為GN塊。一個GN塊定義了三個更新函數和三個聚合函數

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-ItBRcGht-1638176337247)(media/78c61e6a869c51ebd87e4ba676724349.png)]

給定是接收節點，是邊k的發送節點，。和分別是邊向量和節點向量的堆疊矩陣。通過接收節點v收集邊向量。u是圖形表示的全局屬性。φ和ρ函數可以有各種設置，而ρ函數必須不受輸入順序的影響，并且參數長度應該是可變的。

3.2傳播模塊-循環算子

循環法是這一研究領域的先驅。遞歸運算符和卷積運算符之間的主要區別是，卷積運算符中的層使用不同的權重，而在卷積運算符中的層使用不同的權重。遞歸算子的不同變體：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-th926UaG-1638176337248)(media/1ff4572f31ac1dd0373da0a385b536ae.png)]

遞歸運算符具有相同的權值。早期基于遞歸神經網絡的方法專注于處理有向無環圖(Sperduti和Starita,
1997;Frasconi等人，1998;Micheli等人，2004;Hammer等人，2004)。隨后，圖神經網絡(GNN)的概念在(Scarselli
et al.， 2009;Gori et al.，
2005)中首次提出，擴展了現有的神經網絡來處理更多的圖類型。為了與通用名稱區分，本文將該模型命名為gnnn。我們首先介紹了gnn及其后續的變種，它們需要隱藏狀態的收斂，然后我們討論了基于門機制的方法。

3.2.1基于融合的方法

在圖中，每個節點都是由其特征和相關節點自然定義的。GNN的目標是學習嵌入[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-zhm1H0yi-1638176337251)(media/cc3b62bc98aafa8fb0c6f4c5bffd2089.png)]的狀態，其中包含每個節點的鄰居和自身的信息。節點的狀態嵌入和維向量可以用來產生預測節點標簽的分布等輸出。則hvandovare的計算步驟定義為:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-r0wTCEzd-1638176337253)(media/c3ca274f598fb0ae70c4598a860a1380.png)]

其中[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-jaiwJ2sI-1638176337254)(media/86d591dbd0e6eb288b9174c4fbc36c7e.png)]分別是v的特征，它的邊的特征，v的鄰域節點的狀態和特征。這里有一個參數函數，叫做局部躍遷函數。它在所有節點之間共享，并根據輸入的鄰域更新節點狀態。G是描述如何產生輸出的局部輸出函數。注意，f和g都可以解釋為前饋神經網絡。設H、0、X和X分別是由所有狀態、所有輸出、所有特征和所有節點特征疊加而成的矩陣。然后我們得到一個緊湊形式為:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-2LY8mzS8-1638176337257)(media/0d6eee22404f43d9581e4c87a0abe5ef.png)]

其中，F全局轉換函數和全局輸出函數g分別是圖中所有節點和的堆疊版本。H的值是Eq.(20)的不動點，并且是唯一定義的，假設fis收縮映射。根據Banach不動點定理(Khamsi
and Kirk, 2011)的建議，gnnus采用以下經典迭代格式來計算狀態:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-IiTc1Byi-1638176337259)(media/2d1fd02c49faa85321a058401e03cb32.png)]

其中表示h的第t次迭代。動力系統Eq.(21)以指數速度收斂于任意初值的解。雖然實驗結果表明GNN是一種強大的結構數據建模架構，但仍然存在一些局限性:

gnn要求是一個限制模型能力的收縮映射。迭代更新節點的隱狀態到定點是低效的。如果我們專注于節點的表示而不是圖，那么就不適合使用不動點，因為在不動點中表示的分布在值上更平滑，對于區分每個節點來說信息更少。

GraphESN: 圖回聲狀態網絡(Graph echo state network, GraphESN) (Gallicchio and
Micheli, 2010)在圖上概括了回聲狀態網絡(回聲狀態網絡，ESN) (Jaeger,
2001)。它使用固定的壓縮編碼函數，只訓練一個讀出函數。儲層動力學的收縮性保證了收斂性。因此，GraphESN比GNN更高效

SEE: 隨機穩態嵌入(SSE) (Dai et al.，
2018a)也被提出來提高GNN的效率。SSE提出了一個包含兩個步驟的學習框架。在更新步驟中，通過參數化算子更新每個節點的嵌入，并將這些嵌入投影到穩態約束空間以滿足穩態條件。

LP-GNN: 隨機穩態嵌入(SSE) (Dai et al.，
2018a)也被提出來提高GNN的效率。SSE提出了一個包含兩個步驟的學習框架。在更新步驟中，通過參數化算子更新每個節點的嵌入，并將這些嵌入投影到穩態約束空間以滿足穩態條件。

3.2.2基于門的方法

有幾個研究試圖在傳播步驟中使用門機制，如GRU (Cho et al.， 2014)或LSTM
(Hochreiter and Schmidhuber,
1997)，以減少GNN的計算限制，改善信息在圖結構中的長期傳播。他們在沒有收斂性保證的情況下運行固定數量的訓練步驟。

GGNN：門控圖神經網絡(GGNN) (Li et al.，
2016)的提出是為了緩解GNN的局限性。它釋放了函數作為收縮映射的需求，并在傳播步驟中使用了Gate循環單位(GRU)。它還使用反向時間傳播(BPTT)來計算梯度。GGNN的計算步驟見表2

節點v優先聚合來自鄰居的消息。然后類似于gru的更新函數合并來自其他節點和前一個時間步的信息，以更新每個節點的隱藏狀態。[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-aolsnFRl-1638176337262)(media/00587612b7d34972324e3df993d91717.png)]收集節點v的鄰居信息。然而z和r是更新和重置門。通過基于樹或圖的傳播過程，lstm也以類似于GRU的方式使用。

樹LSTM：Tai通過基于樹或圖的傳播過程，lstm也以類似于GRU的方式使用。

N-ary
Tree-LSTM。它們也是我們之前提到的基于遞歸神經網絡模型的擴展。樹是圖的一種特殊情況，Tree-
lstm中的每個節點都從它的子節點收集信息。

與傳統LSTM中的單一遺忘門不同，tree
-LSTM單元為每個子節點包含一個忘記門。子和樹lstm的計算步驟如表2所示。

圖LSTM。兩種類型的tree - lstm可以很容易地適應圖。在(Zayats和Ostendorf,
2018)中的圖結構LSTM是一個例子，然后是樹LSTM應用于圖。然而，這是一個簡化的版本，因為圖中的每個節點最多有2條傳入邊(來自其父節點和同級節點)。Peng等(2017)提出了另一種基于關系抽取任務的圖LSTM的變體。(Peng
et al.， 2017)中的圖的邊有不同的標簽，因此Peng et
al.(2017)利用不同的權重矩陣來表示不同的標簽。InTable 2,mev;kTdenotes
nodevandk之間的邊標簽。Liang等人(2016)提出了一個Graph
LSTM網絡來解決語義對象解析任務。該算法采用置信驅動方案自適應地選擇起始節點，確定節點更新順序。它遵循將現有lstm一般化為圖結構數據的相同思想，但具有特定的更新順序，而上面提到的方法與節點的順序無關。S-LSTM。Zhang等(2018d)提出了句子LSTM
(S-LSTM)來改進文本編碼。它將文本轉換為圖，并利用graph
LSTM來學習表示。S-LSTM在許多自然語言處理問題中表現出較強的表示能力。

3.3 傳播模塊-跳過連接

許多應用程序將圖神經網絡層展開或堆疊，目的是為了獲得更好的結果，因為更多的層(即eklayers)使每個節點從鄰居處聚合更多的信息。然而，在許多實驗中發現，更深層次的模型并不能提高性能，甚至可能表現得更差。這主要是因為更多的層也可以從指數增長的擴展鄰居成員傳播噪聲信息。它還會導致過度平滑問題，因為當模型深入時，在聚合操作之后，節點往往具有類似的表示。因此，許多方法試圖添加“跳過連接”，使GNN模型更深入。在本小節中，我們將介紹三種跳躍連接的實例化。公路之下。Rahimi等人(2018年)提出了一個高速公路GCN，它使用類似于高速公路網絡的分層門(Zilly等人，2016年)。一個層的輸出和它的輸入加上門控權重:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-q3o7IYgn-1638176337265)(media/9d139204264fdcc272a6dd7d10e3d7cb.png)]

通過添加高速公路閘門，在(Rahimi et al.，
2018)中討論的特定問題中，性能在4層達到峰值。柱狀網絡(CLN) (Pham et al.，
2017)也利用了公路網絡。但是它有不同的函數來計算門權值。

JKN。Xu et
al.(2018)研究了鄰域聚集方案的性質和局限性。他們提出了跳躍知識網絡(JKN)，它可以學習自適應和結構感知的表示。JKN從最后一層的每個節點的所有中間表示(即“跳轉”到最后一層)中選擇，這使得模型根據需要適應每個節點的有效鄰域大小。Xu
et al.(2018)使用了三種方法:連接、最大池和lstm
-注意在實驗中聚集信息。JKN在社會、生物信息學和引文網絡的實驗中表現良好。它還可以與GCN、GraphSAGE和GAT等模型相結合，以提高性能。

DeepGCNs。Li等人(2019a)借鑒了ResNet (He et al.， 2016a,2016b)和DenseNet (Huang
et al.，
2017)的想法。ResGCN和DenseGCN通過結合殘余連接和密集連接來解決消失梯度和過平滑問題。具體來說，ResGCN和DenseGCN中節點的隱藏狀態可以計算為:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-25HuluXN-1638176337267)(media/aa91cf16adc42d9ac0dd58fe2ef54a86.png)]

在點云語義分割任務上進行了DeepGCNs實驗，在56層模型下取得了最好的結果。

3.4采樣模塊

GNN模型將來自前一層鄰居的每個節點的消息聚合在一起。直觀地說，如果我們跟蹤多個GNN層，支持鄰居的大小將隨著深度呈指數增長。緩解這種“鄰居爆炸”問題，一個有效而有效的方法是抽樣。另外，當我們處理大圖時，我們不能總是存儲和處理每個節點的所有鄰域信息，因此需要采樣模塊進行傳播。在本節中，我們將介紹三種圖抽樣模塊:節點抽樣、層抽樣和子圖抽樣。

3.4.1節點采樣

減少鄰近節點大小的一種直接方法是從每個節點的鄰域中選擇一個子集。GraphSAGE
(Hamilton et al.，
2017a)樣本固定了少量的鄰居，確保每個節點的鄰域大小為2到50。為了減少抽樣方差，Chen等人(2018a)利用節點的歷史激活作為控制變量，為GCN引入了基于控制變量的隨機逼近算法。這種方法限制了接收域在1-hop鄰居，并使用歷史隱藏狀態作為一個負擔得起的近似。PinSage
(Ying et al.，
2018a)提出了基于重要性的抽樣方法。該方法通過模擬從目標節點開始的隨機行走，選擇標準化訪問次數最高的T節點。

3.4.2 分層抽樣

分層抽樣不是對每個節點的鄰居進行抽樣，而是在每一層中保留一小組節點進行聚集，以控制擴展因子。FastGCN
(Chen et al.，
2018b)直接對每一層的接收場進行采樣。它使用重要性抽樣，其中重要節點更有可能被抽樣。與上述固定采樣方法相比，Huang等人(2018)引入了一個參數化和可訓練的采樣器，以前一層為條件進行分層采樣。此外，該自適應采樣器可以在優化采樣重要性的同時降低方差。LADIES
(Zou等人，2019)打算通過從節點的鄰居的并集生成樣本來緩解分層采樣中的稀疏性問題。

3.4.3子圖抽樣

而不是采樣節點和邊建立在整個圖，一個根本不同的方法是采樣多個子圖，并限制在這些子圖的鄰域搜索。ClusterGCN
(Chiang et al.， 2019)通過圖聚類算法對子圖進行采樣，而GraphSAINT (Zeng et al.，
2020)直接對節點或邊進行采樣，生成子圖。

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-rAS0JTCz-1638176337273)(media/9cbc0d4a360ba601ae8ad1996187a460.png)]

3.5池模塊

在計算機視覺領域，卷積層之后通常會有一個池化層，以獲得更多的通用特性。復雜而大規模的圖通常具有豐富的層次結構，這些層次結構對于節點級和圖級分類任務非常重要。與這些池層類似，很多工作都關注在圖上設計分層池層。在本節中，我們將介紹兩種池模塊:直接池模塊和分層池模塊。

3.5.1直接池模塊

直接池模塊直接從具有不同節點選擇策略的節點學習圖級表示。在某些變體中，這些模塊也稱為讀出函數。簡單的節點池。幾個模型使用了簡單的節點池方法。在這些模型中，節點的最大/平均/和/注意操作應用于節點特征得到全局圖表示。

Set2set：MPNN使用Set2set方法(Vinyals et al.，
2015a)作為讀出函數，得到圖的表示。Set2set是為了處理無序集[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-pHbWiAz8-1638176337275)(media/e02fadeffab0dcd205cf769114e20b02.png)]而設計的，并使用基于lstm的方法在預定義的步驟數之后生成順序不變表示。

SortPooling (Zhang et al.，
2018e)首先根據節點的結構角色對節點嵌入進行排序，然后將排序后的嵌入送入cnn中得到表示

3.5.2分層池模塊

前面提到的方法直接從節點學習圖表示，它們不研究圖結構的層次屬性。接下來，我們將討論遵循分層池模式和按層學習圖表示的方法。

圖粗化：
早期的方法通常是基于圖的粗化算法。首先采用光譜聚類算法，但由于特征分解步驟的問題，其效率較低。Graclus
(Dhillon et al.，
2007)提供了一種更快的節點聚類方式，它被應用為一個池化模塊。例如，ChebNet和MoNet使用Graclus合并節點對，并進一步添加額外的節點，以確保池化過程形成平衡二叉樹。

ECC：Edge-Conditioned Convolution (ECC) (Simonovsky and Komodakis,
2017)設計了遞歸降采樣操作的池化模塊。下采樣方法是根據拉普拉斯矩陣的最大特征向量的符號將圖分成兩個分量。

DiffPool：DiffPool (Ying et al.，
2018b)使用可學習的分層聚類模塊，通過在每一層訓練一個賦值矩陣:
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-X4uAbF2P-1638176337279)(media/b46d13bbe734a03690fee9c2d30cdca1.png)]

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-WWOJY64u-1638176337282)(media/f1825f3b94acdf9a68157a8729f23d65.png)]

Ht是節點在t層特征矩陣，At是t層的粗化鄰接矩陣，St表示一個節點在t層可以被一個粗化節點在t+1層分配的可能性

gPool：gPool (Gao and Ji,
2019)使用一個項目向量來學習每個節點的投影得分，并選擇得分最高的k的節點。與DiffPool相比，它在每一層使用向量而不是矩陣，從而降低了存儲復雜度。但投影過程沒有考慮圖的結構。

EigenPooling.：EigenPooling (Ma et al.，
2019a)設計的目的是聯合使用節點特征和局部結構。該方法利用局部圖傅里葉變換提取子圖信息，存在圖特征分解效率不高的問題。

SAGPool：SAGPool (Lee et al.，
2019)也被提出使用特征和拓撲共同學習圖表示。它采用基于自我注意的方法，具有合理的時間和空間復雜性。

4.考慮圖像類型和縮放的變量

在上面幾節中，我們假設圖形是最簡單的格式。然而，現實世界中的許多圖表是復雜的。在本小節中，我們將介紹試圖解決復雜圖類型挑戰的方法。這些變體的概述如圖4所示

4.1有向圖

第一種類型是有向圖。有向邊通常比無向邊包含更多的信息。例如，在一個知識圖中，頭部實體是尾部實體的父類，邊緣方向提供了關于部分順序的信息。與簡單地在卷積算子中采用非對稱鄰接矩陣不同，我們可以對邊的正方向和反方向進行不同的建模。

DGP (Kampffmeyer et al.， 2019)使用了兩種權重矩陣Wp和Wc用于正向和反向卷積

4.2異構體

圖的第二種變體是異構圖，其中節點和邊是多類型或多模態的。更具體地說在異構體[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-IyUdhO32-1638176337285)(media/0ad0ffe3874d51de7b4a0e84bb8c2ee1.png)]中，每個節點vi都與類型[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-AY9LptnD-1638176337292)(media/ec4e927309ecdad851b38432cecc792b.png)]有關聯，每個邊ej與類型[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-xw3pMnSN-1638176337294)(media/604450ea4b439b088be7bfa018346200.png)]有關聯。

4.2.1基于元路徑的推薦的方法

處理這種圖類型的大多數方法都利用了路徑的概念。元路徑是一種路徑方案，它決定了路徑各位置的節點類型，如[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-0MzF1LRS-1638176337296)(media/17d1e096c559ba95c6d193e5f4593d61.png)]，其中L為元路徑的長度。在訓練過程中，元路徑被實例化為節點序列。通過連接元路徑實例的兩個端點節點，元路徑可以獲取兩個可能不直接連接的節點的相似性。因此，可以將一個異構圖簡化為幾個同構圖，并在這些同構圖上應用圖學習算法。在早期的工作中，研究了基于元路徑的相似性搜索(Sun
et al.， 2011)。近年來，越來越多的GNN模型利用元路徑。HAN (Wang et al.，
2019a)首先對每個元路徑下的基于元路徑的鄰居進行圖注意，然后在所有元路徑方案下對節點的輸出嵌入使用語義注意來生成節點的最終表示。MAGNN
(Fu et al.，
2020)提出考慮元路徑中的中間節點。它首先使用神經模塊聚集沿元路徑的信息，然后在與節點相關的不同元路徑實例上執行注意，最后在不同元路徑方案上執行注意。GTN
(Yun et al.，
2019)提出了一種新的圖轉換層，它在學習節點表示的同時識別未連接節點之間的新連接。學習到的新連接可以連接彼此相距幾跳但緊密相關的節點，這些節點起到元路徑的作用。

4.2.2基于邊緣的方法

也有不使用元路徑的作品。這些工作通常使用不同的函數在采樣，聚集等方面的不同種類的鄰居和邊。HetGNN通過在采樣、特征編碼和聚合步驟中以不同的方式直接對待不同類型的鄰居，解決了這一挑戰。HGT
(Hu等，2020a)定義元關系為兩個相鄰節點的類型及其鏈接[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-0uGfkih5-1638176337298)(media/7a07086be7f4b9a8ba79283e8d185ad7.png)]它將不同的注意力權重矩陣分配給不同的元關系，使模型能夠考慮類型信息。

4.2.3關系圖的方法

一些圖的邊緣可能包含比類型更多的信息，或者類型的數量可能太大，給應用基于元路徑或元關系的方法帶來困難。我們將這類圖稱為關系圖(Schlichtkrull
et al.， 2018)，為了處理關系圖，G2S (Beck et
al.，2018)將原始圖轉換為二部圖，其中原始邊也成為節點，將一條原始邊分裂為兩條新邊，即在邊緣節點和開始/結束節點之間有兩條新邊。在此轉換之后，使用門控圖神經網絡和遞歸神經網絡將具有邊緣信息的圖轉換為句子。GGNN的聚合函數以節點的隱藏表示和關系作為輸入。另一種方法R-GCN
(Schlichtkrull et al.，
2018)不需要對原始圖形格式進行轉換。它為不同類型的邊的傳播分配了不同的權矩陣。然而，當關系的數量非常多時，模型中的參數數量就會激增。為此，引入了基-對角線分解和塊對角線分解兩種正則化方法來減少關系建模參數的數量。通過基礎分解，每個Wr的定義如下：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-kzkyaT6c-1638176337301)(media/877ed7bffa9d91ed63d3667f4323f973.png)]

這里每一個Wr是基變換的線性組合。

4.2.4多重圖的方法

在更復雜的場景中，圖中的一對節點可以與不同類型的多條邊關聯。通過在不同類型的邊下查看，圖可以形成多個層，其中每一層代表一種關系。因此，多重圖也可以稱為多視圖圖(multi-view
graph，多維圖)。例如，在YouTube中，兩個用戶之間可能有三種不同的關系:分享、訂閱、評論。邊類型并不是相互獨立的，因此簡單地將圖分割成具有一種邊類型的子圖可能不是一個最佳解決方案。mGCN
(Ma等人，2019b)介紹了GNN每一層節點的一般表示和特定尺寸表示。使用不同的投影矩陣從一般表示中投影特定于維度的表示，然后聚合以形成下一層的一般表示

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-AgAChXFg-1638176337305)(media/b961782d50a0d65421bf1765780395db.png)]

4.3動態圖

圖的另一種變體是動態圖，其中圖的結構，例如邊和節點的存在，會隨著時間不斷變化。為了將圖結構數據與時間序列數據一起建模，DCRNN
(Li et al.， 2018b)和STGCN (Yu et al.，
2018)首先通過gnn收集空間信息，然后將輸出輸入序列到序列模型(sequence- To
-sequence model)或rnn等序列模型。不同的是，Structural-RNN (Jain et al.，
2016)和ST-GCN (Yan et al.，
2018)同時收集空間和時間信息。他們使用時間連接擴展靜態圖結構，因此他們可以在擴展圖上應用傳統的gnn。同樣，DGNN
(Manessi et al.，
2020)將GCN中每個節點的輸出嵌入到單獨的lstm中。lstm的權值在每個節點之間共享。另一方面，EvolveGCN
(Pareja et al.，
2020)認為直接建模節點表示的動態將阻礙模型在節點集不斷變化的圖上的性能。因此，它沒有將節點特征作為RNN的輸入，而是將GCN的權值輸入到RNN，以捕獲圖交互的內在動態。最近的一項調查(Huang
et al.，
2020)根據鏈接持續時間將動態網絡劃分為若干類，并將現有模型按照其專業化程度進行分類。建立了動態圖模型的通用框架，并將現有模型納入該框架。

4.4其他圖類型

對于圖的其他變體，如超圖和簽名圖，也有一些模型被提出來解決這些挑戰。

4.4.1超圖

超圖可以用[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-3ZiESNdp-1638176337307)(media/ed2523289402803022c884a567199e13.png)]表示，其中邊e連接兩個或多個頂點，并賦值一個權重w。超圖的鄰接矩陣可以表示成

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-QTawBb9L-1638176337309)(media/8d11934370e932326afd214cef325139.png)]

HGNN (Feng et al.， 2019)提出超圖卷積來處理這些節點之間的高階交互:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Cs5u2S2h-1638176337312)(media/c93bc3ff3230e8ec92d5c304d18dda11.png)]

其中Dv;We;De;X是節點度矩陣、邊權矩陣、邊度矩陣和節點特征矩陣。

W是可學習參數。這個公式是用截斷的切比雪夫多項式逼近超圖拉普拉斯方程而得到的。

4.4.2符號圖

有符號圖是有符號邊的圖，即一條邊可以是正的也可以是負的。SGCN (Derr et al.，
2018)并沒有簡單地將負邊視為缺失邊或另一種類型的邊，而是利用平衡理論捕獲正邊和負邊之間的相互作用。從直覺上來說，平衡理論認為，朋友的朋友(正面優勢)也是我的朋友，敵人的敵人(負面優勢)也是我的朋友。這為SGCN模型的正負邊相互作用提供了理論基礎。

4.5大圖

正如我們在第 3.4
節中提到的，采樣算子通常用于處理大規模圖。除了采樣技術，還有縮放問題的其他方法。利用近似個性化
PageRank，

避免計算高階傳播矩陣。羅西等人。 (2020) 提出一種預計算圖的方法

用于有效訓練和推理的不同大小的卷積濾波器。基于 PageRank 的模型將多個 GCN
層壓縮為一個傳播層來緩解“鄰居爆炸”問題，因此是

高度可擴展和高效的。

5.不同訓練設置的變體

在本節中，我們將介紹不同訓練設置的變體。對于監督和半監督設置，提供標簽，使損失功能很容易設計這些標簽的樣品。對于無監督設置，沒有標記的樣本，因此損失函數應該依賴于圖本身提供的信息，例如輸入特征或圖拓撲。在本節中，我們主要介紹非監督訓練的變體，它們通常基于自動編碼器或對比學習的思想。我們提到的方法的概述如圖所示。5.

5.1圖自動編碼

在無監督圖表示學習中，自動編碼器(AE)已成為擴展到圖域的趨勢。Graph Auto-Encoder
(GAE) (Kipf和Welling,
2016)首先使用GCNs對圖中的節點進行編碼。然后用一個簡單的解碼器重建鄰接矩陣，根據原鄰接矩陣與重建矩陣的相似度計算損失:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-BJrpOctP-1638176337315)(media/233b139f629f7a2400d3855a84bcbf4a.png)]

Kipf和Welling(2016)也以變分的方式訓練GAE模型，該模型被命名為變分圖自動編碼器(VGAE)。

對抗正則化圖自編碼(ARGA)
(Pan等人，2018)采用生成式對抗網絡(GANs)來正則化基于gcn的圖自編碼，它可以學習更健壯的節點表示。

Wang et al. (2017)，Park et al.(2019)試圖重建特征矩陣，而不是恢復鄰接矩陣。MGAE
(Wang et al.，
2017)利用邊緣去噪自編碼器獲得魯棒的節點表示。為了構建對稱圖形自動編碼器，GALA
(Park et al.， 2019)提出了拉普拉斯銳化(Laplacian
sharpening，拉普拉斯平滑的逆操作)來解碼隱藏狀態。該機制緩解了GNN訓練中的過度平滑問題。與上述不同的是，AGE
(Cui et al.，
2020)認為恢復損失與下游任務不兼容。因此，他們將自適應學習應用于兩兩節點相似度的測量，并在節點聚類和鏈接預測方面實現了最先進的性能。

5.2對比學習

除了圖形自動編碼器，對比學習為無監督圖表示學習開辟了另一種途徑。Deep Graph
Infomax (DGI)
(Velickovic等人，2019)最大化了節點表示和圖表示之間的相互信息。Infograph (Sun et
al.，
2020)的目標是通過圖層表示和不同尺度(包括節點、邊和三角形)的子結構層表示之間的相互信息最大化來學習圖表示。多視圖(Hassani和Khasahmadi,
2020)對比了一階鄰接矩陣和圖擴散表示，在多個圖學習任務上實現了最先進的性能。

6.一個GNN的設計實例

在本節中，我們給出一個現有的GNN模型來說明設計過程。以異構圖預訓練任務為例，我們使用GPT-GNN
(Hu et al.， 2020b)作為模型來說明設計過程。

找到圖結構。本文主要研究了學術知識圖譜和推薦系統的應用。在學術知識圖譜中，圖譜結構是明確的。在推薦系統中，用戶、條目和評論可以看作節點，它們之間的交互可以看作邊，所以圖結構也易于構建。

指定圖形類型和比例。任務集中在異構圖上，因此節點和邊的類型應該被考慮并納入最終的模型中。由于學術圖和推薦圖包含數百萬個節點，因此模型需要進一步考慮效率問題。總之，該模型應該關注大規模異構圖。

設計功能損失。由于(Hu et al.，
2020b)中的下游任務都是節點級任務(如學術圖中的Paper-Field預測)，因此模型在預訓練步驟中需要學習節點表示。在預訓練步驟中，沒有可用的標記數據，所以一個自監督的圖生成任務是設計來學習節點的嵌入。在微調步驟中，根據每個任務的訓練數據對模型進行微調，從而應用每個任務的監督損失。

使用計算模塊建立模型。最后利用計算模塊建立模型。對于傳播模塊，作者使用了我們之前提到的卷積算子HGT
(Hu等人，2020a)。HGT將節點和邊的類型合并到模型的傳播步驟中，并在體系結構中添加了跳過連接。采樣模塊采用了專門設計的采樣方法HGSampling
(Hu et al.， 2020a)，這是LADIES的異構版本(Zou et al.，
2019)。由于模型關注的是學習節點表示，因此不需要池化模塊。HGT層被多層堆疊，以學習更好的節點嵌入。

7.GNN的分析

7.1理論方面

在這一節中，我們從各個角度總結了關于圖神經網絡的理論基礎和解釋的文獻。

7.1.1圖像信號處理

從頻譜的角度來看，GCNs在頻譜域對輸入特征進行卷積運算，這在理論上是進行圖信號處理的。

從圖信號處理的角度分析gnn的研究已有很多。Li等人(2018c)首先解決了圖神經網絡中的圖卷積問題，實際上是拉普拉斯平滑，它對特征矩陣進行平滑，使附近的節點具有類似的隱藏表示。拉普拉斯平滑反映了同質性假設，即相鄰節點應該是相似的。拉普拉斯矩陣作為輸入特征的低通濾波器。SGC
(Wu et al.，
2019b)進一步消除了權重矩陣和層之間的非線性，表明低通濾波器是gnn工作的原因

根據低通濾波的思想，Zhang等人(2019c)，Cui等人(2020)，NT和Maehara (NT和Maehara,
2019)，Chen等人(2020b)分析了不同的濾波器并提供了新的見解。為實現對所有特征值的低通濾波，AGC
(Zhang et al.， 2019c)根據頻率響應函數設計了一個graphfilterI’12l。AGE (Cui et
al.， 2020)進一步證明i ’ 1λ maxl濾波器可以得到更好的結果，其中λ
maxl為拉普拉斯矩陣的最大特征值。盡管有線性濾波器，GraphHeat
(Xu等人，2019a)利用熱核獲得更好的低通特性。

圖卷積主要是對輸入特征進行去噪處理，模型的性能很大程度上取決于特征矩陣中噪聲的大小。為了緩解過度平滑問題，Chen等人(2020b)提出了兩個度量指標來衡量節點表示的平滑性和GNN模型的過度平滑性。作者認為，信息噪聲比是超平滑的關鍵因素。

7.1.2概括

近年來，gnn的泛化能力也受到了人們的關注。Scarselli等人(2018)證明了有限類gnn的vc
-維。Garg et
al.(2020)基于Rademacher邊界進一步給出了更嚴格的神經網絡泛化邊界。Verma和Zhang(2019)分析了不同卷積濾波器的單層gnn的穩定性和泛化特性。作者認為，gnn的穩定性取決于濾波器的最大特征值。Knyazev
et
al.(2019)關注gnn中注意機制的泛化能力。他們的結論表明，注意有助于gnn概括為更大的和有噪聲的圖。

7.1.3表現度

關于gnn的表達率，Xu等人(2019b)和Morris等人(2019)表明GCNs和GraphSAGE的區別性低于Weisfeiler-Leman
(WL)檢驗，一種圖同構檢驗算法。Xu等人(2019a)也提出了GINs用于更有表現力的gnn。超越WL測試，Barcel!o等人(2019)討論了gnn是否可表示FOC2，一個片段一階邏輯。作者發現現有的gnn很難符合這種邏輯。對于學習圖的拓撲結構，Garg等人(2020)證明局部依賴的GNN變體不能學習全局圖的屬性，包括直徑、最大/最小循環或基序

Loukas(2020)和dehmamy等人(2019)認為，現有作品只考慮gnn具有無限層和單元時的表現力。他們的工作是研究有限深度和寬度的gnn的表示能力。ooono和Suzuki(2020)討論了隨著模型的深化，gnn的漸近行為，并將它們建模為動態系統

7.1.4不變性

由于圖中沒有節點順序，因此gnn的輸出嵌入應該是排列不變的或與輸入特征等變的。Maron等人(2019a)刻畫了排列不變或等變線性層來構建不變gnn。Maron等(2019b)進一步證明了通過高階張量化可以得到通用不變量gnn的結果。Keriven
Peyr
!E(2019)提供了一個替代證明，并將該結論推廣到等變情況。Chen等人(2019)建立了排列不變性和圖同構檢驗之間的聯系。為了證明它們的等價性，Chen等人(2019)利用sigma代數來描述gnn的表達性。

7.1.5可轉移性

gnn的一個確定性特征是參數化與圖相結合，這表明在性能保證的情況下跨圖傳輸的能力(所謂的可轉移性)。Levie等人(2019)研究了光譜圖濾波器的可轉移性，表明此類濾波器能夠在同一域的圖上轉移。Ruiz等人(2020)分析了GNN在石墨烯上的行為。Graphon指的是圖序列的極限，它也可以看作是稠密圖的生成器。作者的結論是，gnn可以在確定地從同一圖中以不同大小獲得的圖之間轉移。

7.1.6標簽效率

gnn的(半)監督學習需要大量的標記數據才能達到令人滿意的性能。本文從主動學習的角度對如何提高標簽效率進行了研究，即主動選擇信息節點由oracle進行標簽，以訓練gnn。Cai
et al.(2017)、Gao et al. (2018b)、Hu et al.
(2020c)等研究表明，通過選擇高程度節點和不確定節點等信息節點，可以顯著提高標簽效率

7.2經驗方面

除了理論分析外，還需要對gnn進行實證研究，以便更好地進行比較和評價。在這里，我們包括幾個實證研究的GNN評價和基準。

7.2.1評估

評估機器學習模型是研究的一個重要步驟。多年來，人們對實驗再現性和可復制性提出了擔憂。GNN模型是否有效，在何種程度上有效?模型的哪些部分對最終性能有貢獻?為了研究這些基本問題，迫切需要對公平評價策略進行研究。

在半監督節點分類任務中，Shchur等人(2018a)探索了GNN模型在相同的訓練策略和超參數調優下的表現。他們的研究得出結論，不同的數據集可以拆分導致不同的模型排名。此外，在適當的設置下，簡單模型可以優于復雜模型。Errica等人(2020)回顧了幾個圖表分類模型，并指出它們的比較不恰當。基于嚴格的評估，結構信息在圖分類中沒有得到充分的利用。You
et
al.(2020)討論了GNN模型的架構設計，如層數和聚合功能。通過大量的實驗，這項工作為各種任務的GNN指定提供了全面的指導方針

7.2.2基準

高質量和大規模的基準數據集，如ImageNet在機器學習研究中具有重要意義。然而在圖學習中，廣泛采用的基準是有問題的。例如，大多數節點分類數據集只包含3000到20000個節點，這與真實世界的圖相比很小。此外，各個研究的實驗方案不統一，這對文獻是有害的。為了緩解這一問題，Dwivedi等人(2020)和Hu等人(2020d)為圖學習提供了可擴展且可靠的基準。Dwivedi
et al.(2020)在多個領域和任務中構建中等規模的基準數據集，而OGB (Hu et al.，
2020d)提供大規模數據集。此外，這兩款作品都評估了當前的GNN模型，并提供排行榜供進一步比較。

8.應用

圖神經網絡已經在有監督、半監督、無監督和強化學習設置的廣泛領域中進行了探索。在本節中，我們通常將應用程序分組到兩個場景中:(1)結構化場景，其中數據具有顯式的關系結構。這些場景，一方面來自于科學研究，如圖挖掘，建模物理系統和化學系統。另一方面，它們來自于工業應用，如知識圖、交通網絡和推薦系統。(2)關系結構隱含或不存在的非結構化場景。這些場景通常包括圖像(計算機視覺)和文本(自然語言處理)，這是人工智能研究最活躍的兩個分支。這些應用程序的一個簡單示例是inFig。6.
注意，我們只列出了幾個有代表性的應用程序，而沒有提供完整的列表。應用程序的摘要可以在表3中找到。

8.1結構化場景

在接下來的小節中，我們將介紹gnn在結構化場景中的應用，在結構化場景中，數據自然地在圖結構中執行

8.1.1圖挖掘

第一個應用是解決圖挖掘中的基本任務。通常，圖挖掘算法用于識別下游任務的有用結構。傳統的圖挖掘挑戰包括頻繁子圖挖掘、圖匹配、圖分類、圖聚類等。雖然有了深度學習，一些下游任務無需圖挖掘作為中間步驟就可以直接解決，但其基本挑戰值得從gnn的角度進行研究。

圖匹配：第一個挑戰是圖匹配。傳統的圖匹配方法計算復雜度高。gnn的出現使研究人員能夠利用神經網絡捕捉圖的結構，從而為這個問題提供了另一種解決方案。Riba
et al.(2018)提出了一個siamese
MPNN模型來學習圖的編輯距離。siamese框架是兩個具有相同結構和權值共享的并行mpnn，其訓練目標是將編輯距離較小的一對圖嵌入到較近的潛在空間中。Li
et al.
(2019b)設計了類似的方法，同時在更真實的場景中進行實驗，如相似搜索在控制流圖中

圖聚類：圖聚類是根據圖的結構和/或節點屬性將圖的頂點分組成簇。在節點表示學習方面開展了各種工作(Zhang
et al.， 2019c)，節點表示可以傳遞到傳統的聚類算法。除了學習節點嵌入，圖池(Ying
et al.，
2018b)可以看作是一種聚類。最近，Tsitsulin等人(2020)直接針對聚類任務。他們研究了一種好的圖聚類方法的可取之處，并提出了優化譜模塊化的方法，這是一個非常有用的圖聚類指標。

8.1.2物理特性

模擬真實世界的物理系統是理解人類智能最基本的方面之一。物理系統可以建模為系統中的對象和對象之間成對的交互。物理系統的仿真需要模型學習系統的規律，并對系統的下一個狀態進行預測。通過將對象建模為節點，將成對交互建模為邊，系統可以簡化為圖形。例如，在粒子系統中，粒子可以通過多種相互作用進行相互作用，包括碰撞(Hoshen,
2017)、彈簧連接、電磁力(Kipf et al.，
2018)等，其中粒子被視為節點，相互作用被視為邊緣。另一個例子是機器人系統，它是由由關節連接的多個身體(如手臂、腿)組成的。體和關節可以分別看作節點和邊緣。模型需要根據系統的當前狀態和物理原理推斷出物體的下一個狀態。在圖神經網絡出現之前，works使用可用的神經塊處理系統的圖表示。交互網絡(Battaglia
et al.， 2016)利用MLP編碼圖的關聯矩陣。CommNet (Sukhbaatar Ferguset al.，
2016)使用節點先前表示和所有節點先前表示的平均值來執行節點更新。VAIN (Hoshen,
2017)進一步介紹了注意機制。VIN (Watters et al.， 2017)結合了cnn、rnn和IN
(Battaglia et al.，
2016)。gnn的出現讓我們能夠以一種簡化但有效的方式對物體、關系和物理進行基于gnn的推理。NRI
(Kipf et al.，
2018)以物體軌跡為輸入，推導出顯式交互圖，同時學習動態模型。從以前的軌跡中學習交互圖，并通過解碼交互圖生成軌跡預測。Sanchez等(2018)提出了一種基于圖網絡的模型，對機器人系統的身體和關節形成的圖進行編碼。他們將遺傳算法與強化學習相結合，進一步學習了系統的穩定控制策略。

8.1.3化學和生物學

分子指紋：分子指紋作為一種編碼分子結構的方式。最簡單的指紋可以是一個熱點向量，其中每個數字表示某個特定子結構的存在或不存在。這些指紋可以用于分子搜索，這是計算機輔助藥物設計的核心步驟。傳統的分子指紋是手工制作和固定的(例如，一個熱向量)。然而，分子可以很自然地看作圖形，原子是節點，化學鍵是邊。因此，將gnn應用于分子圖譜，可以獲得更好的指紋圖譜。Duvenaud等人(2015)提出了神經圖譜(neural
graphfingerprint)，該算法通過GCNs計算子結構特征向量并求和得到整體表示。Kearnes等人(2016)明確模擬原子和原子對獨立強調原子相互作用。它引入了邊緣表示，而不是聚合函數。

化學反應預測：化學反應產物預測是有機化學中的一個基本問題。圖形變換政策網絡(Do et
al.， 2019)對輸入分子進行編碼，生成一個包含節點對預測網絡和政策網絡的中間圖

蛋白質界面預測：蛋白質通過界面相互作用，界面是由每個參與蛋白質的氨基酸殘基組成的。蛋白質界面預測任務是確定特定殘基是否構成蛋白質的一部分。一般來說，單個殘基的預測依賴于相鄰的其他殘基。通過讓殘基為節點，蛋白質可以表示為圖，這可以利用基于gnn的機器學習算法。Fout等人(2017)提出了一種基于gcn的方法來學習配體和受體蛋白殘留表示，并將它們合并以進行兩兩分類。MR-GNN
(Xu et al.，
2019d)引入了一種多分辨率方法來提取和總結局部和全局特征，以更好地預測。

生物醫學工程：Rhee等(2018)利用蛋白質-蛋白質相互作用網絡(Protein-Protein
Interaction
Network)，利用圖卷積和關系網絡進行乳腺癌亞型分類。Zitnik等人(2018)也提出了一種基于gcn的多藥副作用預測模型。他們的工作是建立藥物和蛋白質相互作用網絡的模型，并分別處理不同類型的邊緣。

8.1.4知識網絡

知識圖(KG)表示現實世界的實體和實體對之間的關系事實的集合。它在問答、信息檢索、知識引導生成等方面有廣泛的應用。KGs的任務包括學習包含豐富語義的實體和關系的低維嵌入，預測實體之間的缺失鏈接，以及對知識圖進行多跳推理。有一條研究線將圖視為三元組的集合，并提出各種損失函數來區分正確的三元組和錯誤的三元組(Bordes
et al.，
2013)。另一條線利用了KG的圖形特性，并為各種任務使用基于gnn的方法。當把KG看作一個圖時，可以看作是一個異構圖。然而，與其他異構圖(如社交網絡)不同，邏輯關系比純圖結構更重要。R-GCN
(Schlichtkrull et al.，
2018)是第一個將gnn用于知識圖嵌入的著作。為了處理各種關系，R-GCN在消息傳遞步驟中提出了特定于關系的轉換。結構感知卷積網絡(Shang
et al.，
2019)結合了一個GCN編碼器和一個CNN解碼器，以更好地表示知識。一個更具挑戰性的設置是針對非知識庫實體的知識庫完成。OOKB實體在訓練集中是看不見的，但是直接連接到訓練集中觀察到的實體。OOKB實體的嵌入可以從觀察到的實體進行聚合。Hamaguchi
et
al.(2017)使用gnn來解決該問題，無論在標準KBC設置還是OOKB設置中都取得了令人滿意的性能。除了知識圖表示學習外，Wang等(2018b)利用GCN解決了跨語言知識圖對齊問題。該模型將不同語言的實體嵌入到一個統一的嵌入空間中，并根據嵌入相似度對其進行對齊。為了對大規模異構知識圖進行對齊，OAG
(Zhang et al.，
2019d)使用圖注意網絡對各種類型的實體進行建模。Xu等(2019c)將表示實體的子圖作為其周圍的子圖，將實體對齊問題轉化為圖匹配問題，然后通過圖匹配網絡解決。

8.1.5生成模型

現實世界圖形的生成模型因其重要的應用而受到重視，包括建模社會互動、發現新的化學結構和構建知識圖。由于深度學習方法對圖的隱式分布具有強大的學習能力，神經圖的研究出現了激增最近生成模型

NetGAN (Shchur et al.，
2018b)是最早建立神經圖生成模型的工作之一，該模型通過隨機漫步生成圖。它將圖生成問題轉化為步行生成問題，以特定圖的隨機步行為輸入，利用GAN架構訓練步行生成模型。生成的圖雖然保留了原始圖的重要拓撲性質，但在生成過程中節點數不會發生變化，與原始圖相同。GraphRNN
(You et al.，
2018b)通過逐步生成每個節點的鄰接向量，成功生成一個圖的鄰接矩陣，可以輸出節點數量不同的網絡。Li
et al.
(2018d)提出了一個順序生成邊和節點的模型，利用圖神經網絡提取當前圖的隱藏狀態，用于在順序生成過程中決定下一步的行動。GraphAF
(Shi et al.，
2020)也將圖生成作為一個順序決策過程。它結合了基于流的生成和自進位模型。在分子生成方面，在每一步生成后，它也利用現有的化學規則對生成的分子進行有效性檢查。

其他工作不是按順序生成圖，而是一次性生成圖的鄰接矩陣。MolGAN (De Cao and Kipf,
2018)利用排列不變鑒別器來解決鄰接矩陣中的節點變分問題。此外，它還應用了一個基于rl的獎勵網絡來優化所期望的化學性質。此外，Ma等人(2018)提出了約束變分自動編碼器，以確保生成的圖的語義有效性。而且，GCPN
(You等人，2018a)通過強化學習整合了特定領域的規則。GNF (Liu et al.，
2019)將歸一化流適應于圖形數據。歸一化流是一種生成模型，利用可逆映射將觀測數據轉換為潛在向量空間。利用逆矩陣將潛在矢量轉換回觀測數據作為生成過程。GNF結合了歸一化流和排列不變圖的自編碼器，以圖結構化數據作為輸入，并在測試時生成新的圖。石墨(Grover
et al.，
2019)將GNN集成到變分自編碼器中，將圖結構和特征編碼為潛在變量。更具體地說，它使用各向同性高斯作為潛變量，然后使用迭代細化策略對潛變量進行解碼。

8.1.6組合優化

圖上的組合優化問題是一組np困難問題，引起了各領域科學家的廣泛關注。一些具體的問題如旅行商問題(TSP)和最小生成樹問題(MST)都有不同的啟發式解。近年來，利用深度神經網絡來解決此類問題已成為研究的熱點，其中一些解決方案由于圖神經網絡具有圖的結構特點，進一步利用圖神經網絡來解決此類問題。Bello
et
al.(2017)首先提出了一種深度學習方法來解決TSP問題。他們的方法包括兩個部分:參數化獎勵的指針網絡(Vinyals
et al.， 2015b)和培訓的政策梯度(Sutton and Barto,
2018)模塊。這項工作已被證明與傳統方法具有可比性。然而，指針網絡是為文本等順序數據設計的，而順序不變編碼器更適合這種工作。Khalil
et al. (2017)，Kool et
al.(2019)通過加入圖神經網絡對上述方法進行了改進。前一項工作首先從structure2vec中獲取節點嵌入(Dai等人，2016)，然后將它們放入q學習模塊中進行決策。后者建立了一個基于注意力的編解碼系統。通過將強化學習模塊替換為基于注意力的解碼器，提高了訓練效率。這些工作取得了比以往算法更好的性能，證明了圖神經網絡的表示能力。更一般地說，Gasse等人(2019)代表了組合的狀態并利用GCN對其進行編碼。對于特定的組合優化問題，Nowak等(2018)關注于二次分配問題，即測量兩個圖的相似度。基于GNN的模型獨立學習每個圖的節點嵌入，并使用注意機制進行匹配。這種方法提供了有趣的良好性能，即使在標準的放松技術似乎受到影響的情況下。Zheng等(2020a)使用生成圖神經網絡來建模dag
-結構學習問題，這也是一個組合優化和np困難問題。NeuroSAT (Selsam et al.，
2019)學習了一個信息傳遞神經網絡來分類SAT問題的可滿足性。這證明了學習到的模型可以推廣到SAT的新分布以及其他可以轉化為SAT的問題。不同于以往試圖設計特定的GNN來解決組合問題，Sato等(2019)在這些問題上提供了GNN模型的理論分析。它建立了gnn和分布式局部算法之間的聯系，分布式局部算法是一組解決這些問題的經典圖上算法。此外，它論證了最強大的GNN能夠達到的最優解的最優逼近比。同時也證明了現有的大多數GNN模型都不能超過這個上界。此外，它還對節點特征進行著色，以提高近似率。

8.1.7交通網絡

流量狀態預測是一項具有挑戰性的任務，因為流量網絡是動態的，具有復雜的依賴性。Cui等人(2018b)結合gnn和lstm來捕獲空間和時間依賴。STGCN
(Yu et al.，
2018)利用空間和時間卷積層構造ST-Conv塊，并采用帶有瓶頸策略的剩余連接。Zheng et
al. (2020b)，Guo et al.(2019)都加入了注意機制，以更好地模擬時空相關性。

8.1.8推薦系統

用戶-物品交互預測是推薦中的經典問題之一。通過將交互過程建模為圖形，可以在該區域利用gnn。GC-MC
(van den Berg et al.，
2017)首先將GCN應用于用戶-物品評級圖中來學習用戶和物品嵌入。為了在網絡規模的場景中有效地采用gnn,
PinSage (Ying et al.，
2018a)對二部圖采用加權采樣策略構建計算圖，以減少重復計算。社交推薦試圖結合用戶的社交網絡來提高推薦性能。GraphRec
(Fan等人，2019年)從物品和用戶兩方面學習用戶嵌入。Wu等(2019c)超越了靜態的社會效應。他們試圖模擬同質性，并通過雙重注意影響效應。

8.1.9結構場景中的其他應用

由于圖結構數據的普遍性，gnn已經被應用到比我們前面介紹的更廣泛的任務中。我們非常簡單地列出了更多的場景。在金融市場中，gnn用于建模不同股票之間的相互作用，預測股票的未來趨勢(Matsunaga
et al.， 2019;Yang et al.， 2019;Chen et al.， 2018c;Li et al.，
2020)。Kim等人(2019)也通過將其定義為一個圖分類問題來預測市場指數的運動。在SDN
(Software-Defined Networks)中，gnn用于優化路由性能(Rusek et al.，
2019)。在抽象意義表示(Abstract Meaning Representation,
AMR)圖到文本生成任務中，Song等人(2018a)、Beck等人(2018)使用gnn對抽象意義的圖表示進行編碼。

8.2非結構場景

在本節中，我們將討論非結構化場景中的應用程序。一般來說，將gnn應用于非結構化網絡有兩種方法

場景:(1)結合其他領域的結構化信息來提高性能，例如利用知識圖信息來緩解圖像任務中的零射問題;(2)推斷或假設任務中的關系結構，然后應用模型解決在圖上定義的問題，如(Zhang
et al.，
2018d)中將文本模型化為圖的方法。常見的非結構場景包括圖像、文本和編程源代碼(Allamanis等人，2018;Li等人，2016)。然而，我們只對前兩個場景做了詳細的介紹。

8.2.1圖像

小樣本圖像分類：圖像分類是計算機視覺領域中一個非常基礎和重要的任務，備受關注，擁有ImageNet等著名數據集(Russakovsky
et al.，
2015)。近年來，零拍和少拍學習在圖像分類領域越來越受到人們的重視。InN-shot學習，為了對某些類中的測試數據樣本進行預測，在訓練集中提供相同類中的onlyNtraining樣本。因此，少射學習限制為小，零射要求為0。模型必須學會從有限的訓練數據中進行歸納，以便對測試數據做出新的預測。另一方面，圖神經網絡可以幫助圖像分類系統在這些具有挑戰性的場景。首先，知識圖可以作為額外信息來指導零鏡頭識別分類(Wang
et al.， 2018d;Kampffmeyer et al.，
2019)。Wang等人(2018d)使視覺分類器不僅從視覺輸入中學習，還從類別名稱的單詞嵌入以及它們與其他類別的關系中學習。開發了一個知識圖來幫助連接相關的類別，他們使用一個6層的GCN對知識圖進行編碼。由于超平滑效應發生在圖卷積結構變得深的時候，(Wang
et al.，
2018d)中使用的6層GCN將洗掉表示中很多有用的信息。為了解決平滑問題，Kampffmeyer等(2019)使用了一個具有更大鄰域的單層GCN，該GCN同時包含圖中的單跳節點和多跳節點。在已有分類器的基礎上，建立零射擊分類器是有效的。由于大多數知識圖具有較大的推理能力，Marino等(2017)根據目標檢測結果選擇一些相關實體構建子圖，并將GGNN應用于提取的圖中進行預測。此外，Lee
et al.
(2018b)也利用了類別之間的知識圖。進一步定義了類別之間的三種關系:上下級關系、正相關關系和負相關關系，并直接在圖中傳播關系標簽的置信度。除了知識圖外，數據集中圖像之間的相似性也有助于少鏡頭學習(Garcia
and Bruna,
2018)。Garcia和Bruna(2018)基于相似性構建加權的全連通圖像網絡，在圖中進行消息傳遞，實現少鏡頭識別。

視覺推理：計算機視覺系統通常需要結合空間和語義信息來進行推理。因此，為推理任務生成圖表是很自然的。一個典型的視覺推理任務是視覺問答(VQA)。在這個任務中，模型需要在給出問題的文本描述的情況下回答關于圖像的問題。通常，答案在于圖像中物體之間的空間關系。Teney
et
al.(2017)構建了一個圖像場景圖和一個問題句法圖。然后他們應用GGNN訓練嵌入以預測最終答案。盡管對象之間存在空間聯系，Norcliffebrown等人(2018)還是基于問題構建了關系圖。Wang
et al. (2018c)、Narasimhan et
al.(2018)利用知識圖可以進行更精細的關系探索和更可解釋的推理過程。視覺推理的其他應用包括目標檢測、交互檢測和區域分類。在目標檢測中(Hu
et al.， 2018;Gu et al.， 2018)， gnn用于計算RoI特征。在交互檢測(Qi et al.，
2018;Jain et al.， 2016)，

GNN是人與對象之間的消息傳遞工具。在區域分類中(Chen et al.， 2018d)，
gnn對連接區域和類的圖進行推理。

語義分割：語義分割是圖像理解的關鍵步驟。這里的任務是為圖像中的每一個像素分配一個唯一的標簽(或類別)，這可以被認為是一個密集分類問題。但是圖像中的區域往往不是網格狀的，需要非局部的信息，這導致了傳統CNN的失敗。一些作品利用圖結構數據來處理它。Liang等人(2016)利用Graph-LSTM對長期依賴和空間連接進行建模，以基于距離的超像素圖的形式構建圖，并利用LSTM對鄰域信息進行全局傳播。后續工作從編碼層次信息的角度對其進行了改進(Liang
et al.，
2017)。此外，3D語義分割(RGBD語義分割)和點云分類利用了更多的幾何信息，因此很難用2D
CNN進行建模。Qi等(2017b)構建k近鄰(KNN)圖，并使用3D
GNN作為傳播模型。在展開幾個步驟后，預測模型將每個節點的隱藏狀態作為輸入，并預測其語義標簽。Landrieu和Simonovsky(2018)針對點云分類任務中點太多的問題，通過構建超點圖并對其生成嵌入來解決大規模三維點云分割問題。Landrieu和Simonovsky(2018)利用GGNN和圖卷積對超級節點進行分類。Wang
et al.
(2018e)提出通過邊建模點的相互作用。它們通過輸入末端節點的坐標來計算邊緣表示向量。然后通過邊緣聚合更新節點嵌入。

8.2.2文本

圖神經網絡可以應用于多種基于文本的任務。它既可以應用于句子級任務(如文本分類)，也可以應用于單詞級任務(如序列標記)。下面我們列出了幾個主要的文本應用。

文本分類：文本分類是自然語言處理中的一個重要而經典的問題。傳統的文本分類使用詞袋特征。然而，將文本表示為單詞圖可以進一步捕獲非連續單詞和長距離單詞之間的語義(Peng
et al.， 2018)。Peng et al.(2018)使用基于graph-
cnn的深度學習模型首先將文本轉換為單詞圖，然后在(Niepert et al.，
2016)中使用圖卷積操作對單詞圖進行卷積。Zhang等(2018d)提出了句子LSTM對文本進行編碼。他們將整個句子視為一個單一的狀態，該狀態由單個單詞的次狀態和整個句子級別的狀態組成。他們使用全局句子級表示來完成分類任務。這些方法要么以單詞節點圖的形式查看文檔或句子。Yao等(2019)將文檔和單詞作為節點構建語料庫圖，利用Text
GCN學習單詞和文檔的嵌入。情感分類也可以看作是一個文本分類問題，Tree-LSTM方法由Tai
et al.， 2015提出。

序列標簽：

給定一個觀察到的變量序列(如單詞)，序列標記是為每個變量分配一個分類標簽。典型的任務包括POS-tagging，即根據詞性對句子中的單詞進行標記;以及命名實體識別(Named
Entity Recognition,
NER)，即預測句子中的每個單詞是否屬于命名實體的一部分。如果我們把序列中的每個變量看作一個節點，把依賴項看作邊，我們就可以利用gnn的隱藏狀態來完成任務。Zhang等(2018d)利用句子LSTM對序列進行標注。他們進行了pos標記和NER任務的實驗，并取得了良好的表現。語義角色標注是序列標注的另一項任務。Marcheggiani和Titov(2017)提出了一個句法GCN來解決這個問題。句法GCN操作于帶標記邊的直圖上，是GCN的一種特殊變體(Kipf和Welling,
2017)。它整合了邊緣門，讓模型調節個人的貢獻

依賴邊緣。利用句法依存樹上的句法GCNs作為句子編碼器來學習句子中單詞的潛在特征表示

神經網絡機器翻譯：

神經機器翻譯(neural machine translation,
NMT)是利用神經網絡將文本從源語言自動翻譯到目標語言。它通常被認為是一個序列對序列的任務。Transformer
(Vaswani et al.，
2017)引入了注意機制，并取代了最常用的循環或卷積層。事實上，Transformer假定單詞之間是完全連接的圖結構。其他的圖結構可以用gnn來探索。GNN的一個流行應用是將語法或語義信息整合到NMT任務中。Bastings等人(2017)在句法感知的NMT任務上使用句法GCN。Marcheggiani等人(2018)使用句法GCN整合了源句謂語-argument結構的信息(即語義-角色表示)，并比較了只整合句法信息、只整合語義信息以及兩者都整合的結果。Beck等(2018)在句法感知的NMT中利用GGNN。他們通過將邊轉換為額外的節點，將語法依賴圖轉換為名為Levi圖(Levi,
1942)的新結構，這樣邊標簽就可以表示為嵌入。

關系抽取：提取文本中實體之間的語義關系有助于擴展現有知識庫。傳統的方法是使用cnn或rnn學習實體的特征，并預測一對實體的關系類型。一種更復雜的方法是利用句子的依賴結構。可以構建一個文檔圖，其中節點表示單詞，邊表示各種依賴關系，如鄰接關系、句法依賴關系和語篇關系。Zhang等人(2018f)提出了一種針對關系提取的圖卷積網絡擴展，并將剪枝策略應用于輸入樹。跨句n元關系抽取檢測多句實體之間的關系。Peng等(2017)通過在文檔圖上應用圖LSTMs，探索了一個跨句關系提取的通用框架。Song等人(2018b)也使用了圖形狀態LSTM模型，并通過允許更多的并行來加快計算速度。

事件提取：

事件提取是識別文本中特定類型事件實例的一項重要信息提取任務。這總是通過識別事件觸發器并預測每個觸發器的參數來實現的。Nguyen和Grishman(2018)研究了基于依賴樹的卷積神經網絡(確切地說就是句法GCN)來執行事件檢測。Liu等(2018)提出了一種聯合多事件提取(joint
Multiple Events Extraction,
JMEE)框架，通過引入句法捷徑弧來增強信息流到基于注意的圖卷積網絡中，對圖信息建模，從而聯合提取多個事件觸發器和參數。

事實驗證：

事實驗證是一項要求模型提取證據來驗證給定主張的任務。然而，有些主張需要基于多個證據進行推理。提出了基于gnn的方法，如GEAR
(Zhou et al.， 2019)和KGAT (Liu et al.，
2020)，基于全連通證據圖進行證據聚合和推理。Zhong等(2020)利用語義角色標注信息構建了一個句子內圖，并取得了很好的效果。

文本的其他應用：

gnn還可以應用于文本上的許多其他任務。例如，gnn也用于問題回答和閱讀理解(Song et
al.， 2018c;De Cao et al.， 2019;Qiu et al.， 2019;Tu et al.， 2019;Ding et
al.， 2019)。另一個重要的方向是關系推理，提出了關系網絡(Santoro et al.，
2017)、交互網絡(Battaglia et al.， 2016)和遞歸關系網絡(Palm et al.，
2018)來解決基于文本的關系推理任務。

9.開放的問題

盡管gnn在不同的領域取得了巨大的成功，但它確實是值得注意的是，GNN模型并不足以為任何條件下的任何圖提供令人滿意的解。在本節中，我們列出了一些有待進一步研究的問題。

魯棒性：作為一類基于神經網絡的模型，gnn也容易受到對抗性攻擊。相對于只針對特征的圖像或文本的對抗性攻擊，針對圖的攻擊進一步考慮了結構信息。已經提出了一些工作來攻擊現有的圖模型(Zügner
et al.， 2018;Dai et al.， 2018b)，并提出了更魯棒的模型來防御(Zhu et al.，
2019)。我們參考(Sun et al.， 2018)進行全面回顧

可解釋性：可解釋性也是神經模型的一個重要研究方向。但gnn也是黑匣子，缺乏解釋。僅提出了幾種方法(Ying
et al.， 2019;Baldassarre和Azizpour,
2019)來生成GNN模型的實例級解釋。將GNN模型應用于具有可信解釋的真實應用程序是很重要的。與CV和NLP領域一樣，圖的可解釋性也是一個重要的研究方向

圖預訓練：基于神經網絡的模型需要大量的標記數據，而獲取大量的人標記數據的成本很高。提出了自監督的方法來指導模型從網站或知識庫中容易獲取的無標簽數據中學習。這些方法以預訓練的思想在CV和NLP領域取得了巨大的成功(Krizhevsky
et al.， 2012;Devlin et al.， 2019)。最近，有一些研究專注于圖的預訓練(Qiu et
al.， 2020;Hu et al.， 2020b,2020e;Zhang et al.，
2020)，但他們的問題設置不同，關注的方面也不同。該領域還存在許多有待研究的問題，如預訓練任務的設計、現有GNN模型在學習結構或特征信息方面的有效性等。

復雜的圖形結構：在現實應用中，圖結構是靈活而復雜的。各種工作被提出處理復雜的圖結構，如我們之前討論過的動態圖或異構圖。隨著互聯網上社交網絡的快速發展，必然會出現更多的問題、挑戰和應用場景，需要更強大的模型。

10.結論

在過去的幾年里，圖神經網絡已經成為圖領域機器學習任務中強大而實用的工具。這一進展歸功于表達能力、模型靈活性和訓練算法的進步。在這項研究中，我們對圖神經網絡進行了全面的回顧。對于GNN模型，我們根據計算模塊、圖類型和訓練類型介紹了它的變種。此外，我們還總結了幾個總體框架，并介紹了一些理論分析。在應用程序分類方面，我們將GNN應用程序分為結構化場景、非結構化場景和其他場景，并對每個場景中的應用程序進行詳細的回顧。最后，我們提出了圖神經網絡面臨的主要挑戰和未來的研究方向，包括魯棒性、可解釋性、預訓練和復雜結構建模。
2019)。我們參考(Sun et al.， 2018)進行全面回顧

可解釋性：可解釋性也是神經模型的一個重要研究方向。但gnn也是黑匣子，缺乏解釋。僅提出了幾種方法(Ying
et al.， 2019;Baldassarre和Azizpour,
2019)來生成GNN模型的實例級解釋。將GNN模型應用于具有可信解釋的真實應用程序是很重要的。與CV和NLP領域一樣，圖的可解釋性也是一個重要的研究方向

圖預訓練：基于神經網絡的模型需要大量的標記數據，而獲取大量的人標記數據的成本很高。提出了自監督的方法來指導模型從網站或知識庫中容易獲取的無標簽數據中學習。這些方法以預訓練的思想在CV和NLP領域取得了巨大的成功(Krizhevsky
et al.， 2012;Devlin et al.， 2019)。最近，有一些研究專注于圖的預訓練(Qiu et
al.， 2020;Hu et al.， 2020b,2020e;Zhang et al.，
2020)，但他們的問題設置不同，關注的方面也不同。該領域還存在許多有待研究的問題，如預訓練任務的設計、現有GNN模型在學習結構或特征信息方面的有效性等。

復雜的圖形結構：在現實應用中，圖結構是靈活而復雜的。各種工作被提出處理復雜的圖結構，如我們之前討論過的動態圖或異構圖。隨著互聯網上社交網絡的快速發展，必然會出現更多的問題、挑戰和應用場景，需要更強大的模型。

10.結論

在過去的幾年里，圖神經網絡已經成為圖領域機器學習任務中強大而實用的工具。這一進展歸功于表達能力、模型靈活性和訓練算法的進步。在這項研究中，我們對圖神經網絡進行了全面的回顧。對于GNN模型，我們根據計算模塊、圖類型和訓練類型介紹了它的變種。此外，我們還總結了幾個總體框架，并介紹了一些理論分析。在應用程序分類方面，我們將GNN應用程序分為結構化場景、非結構化場景和其他場景，并對每個場景中的應用程序進行詳細的回顧。最后，我們提出了圖神經網絡面臨的主要挑戰和未來的研究方向，包括魯棒性、可解釋性、預訓練和復雜結構建模。

總結

以上是生活随笔為你收集整理的《Graph neural networks A review of methods and applications》翻译的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。