《Graph Neural Networks: A Review of Methods and Applications》閱讀筆記

本文是對文獻 《Graph Neural Networks: A Review of Methods and Applications》 的内容總結，詳細内容請參照原文。

引言

大量的學習任務都要求能處理包含豐富的元素間關聯關系的圖資料，例如實體系統模組化、疾病分類以及文本和圖像等非結構資料的學習等。圖形神經網絡（GNNs）是一種連接配接模型，通過圖形節點之間的消息傳遞捕獲圖形的依賴性。

圖（Graph）是一種對一組對象（node）及其關系（edge）進行模組化的資料結構。由于圖結構的強大表示能力，近年來用機器學習分析圖形的研究越來越受到關注，例如社會科學中的社交網絡，自然科學中的實體系統和蛋白質互動網絡，以及知識圖譜和許多研究領域都可以用圖結構來進行表示。由于圖神經網絡（GNN）的高性能和高可解釋性，該方法已經被廣泛應用與圖分析當中。

圖神經網絡的起源

GNN 的第一個動機源于卷積神經網絡（CNN）。CNN 具有提取多尺度局部空間，并将它們組合來建構高層次表示的能力，這導緻了幾乎所有機器學習領域的突破，并開啟了深度學習的新時代。然而，CNN 隻能對規則的歐幾裡得資料進行處理，如圖像（2D 網格）和文本（1D 序列），這些結構也可以看作是圖結構的特例。通過對 CNN 和圖結構的深入了解，可以發現 CNN 中的局部連接配接、共享權重和多層網絡同樣可以應用于圖結構中。是以，一種直覺的想法是直接将 CNN 泛化到圖結構中。但是如 Fig. 1 所示，對于局部卷積濾波器和彙集算子的定義是十分困難的，這嚴重阻礙了 CNN 從歐幾裡德域到非歐幾裡德域的轉換。

GNN 的另一個動機源于對圖嵌入（graph embedding）的研究，該研究主要是用來學習圖節點，邊或子圖的低維表示。在圖形分析領域，傳統的機器學習方法通常依賴于手工設計的特征，并且受到其不靈活性和高成本的限制。基于表示學習和詞嵌入的思想，第一個基于表示學習的圖嵌入方法 DeepWalk 通過應用 SkipGram 模型來生成随機遊走序列，類似的方法還有 node2vec，LINE 和 TADW 。然後，這些方法有兩個嚴重的缺點：（1）在 encoder 中，節點之間沒有共享參數，這導緻計算效率低下，因為這意味着參數的數量随着節點的數量線性增長；（2）直接嵌入方法缺乏泛化能力，這意味着它們無法處理動态圖形或推廣到新圖形。

基于 CNN 和 graph embedding，圖神經網絡（GNN）被提出來集體聚合來自圖結構的資訊。該方法可以模拟由元素及其依賴性組成的輸入和輸出。此外，圖神經網絡還可以使用 RNN 核心同時對圖上的擴散過程進行模組化。

圖神經網絡的優點

圖神經網絡值得研究的根本原因如下：

1. CNN 和 RNN 這樣的标準神經網絡無法處理沒有自然節點順序的不規則圖資料，而 GNN 在每個節點上分别傳播，忽略了節點的輸入順序。即，GNS 的輸出對于節點的輸入順序是不變的。
2. 圖中的邊表示了兩個節點之間的依賴關系的資訊。在标準的神經網絡中，這些依賴資訊隻是作為節點的特征。然後，GNN 可以通過圖形結構進行傳播，而不是将其作為特征的一部分。通常，GNN 通過其鄰域的狀态的權重和來更新節點的隐藏狀态。
3. 推理是進階人工智能的一個非常重要的研究課題，人腦中的推理過程幾乎都是基于從日常經驗中提取的圖形。标準神經網絡已經顯示出通過學習資料分布來生成合成圖像和文檔的能力，同時它們仍然無法從大型實驗資料中學習推理圖。然而，GNN 探索從場景圖檔和故事文檔等非結構性資料生成圖形，這可以成為進一步進階 AI 的強大神經模型。

模型

在圖中，每個節點由其特征和其它相關的節點來自然定義。GNN 的目的就是為每個節點學習到一個包含其所有的鄰居的資訊的狀态嵌入向量 \(h_v\in R^s\) 。狀态嵌入向量 \(h_v\) 是節點 \(v\) 的

s-dimension

向量，并且可以用來生成一個輸出 \(o_v\)，輸出可以是節點的标簽等。令 \(f(\cdot)\) 表示參數函數，也成為局部轉移函數，由所有的節點共享，并且根據輸入的鄰居來對節點狀态進行更新。令 \(g(\cdot)\) 表示局部輸出函數，描述了輸出是如何産生的。則，\(h_v\) 和 \(o_v\) 可以定義為如下形式：

\[h_v=f(x_v,x_{co[v]},h_{ne[v]},x_{ne[v]})\tag{1}\]

\[o_v=g(h_v,x_v)\tag{2}\]

其中，\(x_v\) 表示節點 \(v\) 的特征，\(x_{co[v]}\) 表示與節點 \(v\) 關聯的邊的特征，\(h_{ne[v]}\) 表示節點 \(v\) 的鄰居的狀态，\(x_{ne[v]}\) 表示節點 \(v\) 的鄰居的特征。

令 \(H\)，\(O\)，\(X\) 和 \(X_N\) 分别表示通過堆疊所有的狀态，所有的輸出，所有的特征和所有的節點特征而得到的向量，則可以将上述公式進一步表示為：

\[H=F(H,X)\tag{3}\]

\[O=G(H,X_N)\tag{4}\]

其中，\(F\) 和 \(G\) 分别稱為全局轉移函數和全局輸出函數，是圖中針對所有節點的 \(f\) 和 \(g\) 的堆疊版本。通過 Banach 的不動點理論，GNN 使用如下的疊代方式來計算狀态：

\[H^{t+1}=F(H^t,X)\tag{5}\]

其中，\(H^t\) 表示 \(H\) 的第 t 次疊代。對于任意的初始值 \(H^0\)，公式（5）能通過快速收斂來得到公式（3）的解。注意，\(f(\cdot)\) 和 \(g(\cdot)\) 的描述的計算可以用前饋神經網絡來解決。

通過上述的定義，我們建構了 GNN 的基本架構，下一步是要解決的是如何來學習 \(f(\cdot)\) 和 \(g(\cdot)\) 的參數。通過利用用于監督學習的目标資訊，可以将損失函數定義為如下形式：

\[loss=\sum_{i=1}^p{(t_i-o_i)}\tag{6}\]

其中，\(p\) 表示監督節點的數目，\(t_i\) 和 \(o_i\) 分别表示節點的真實值和預測值。損失函數的學習基于梯度下降政策，由以下步驟組成：

1. 利用公式（1）對狀态 \(h_v^t\) 疊代更新，直到到達接近公式（3）的定點解的時刻 \(T\)，即 \(H^T\approx H\)；
2. 通過損失函數計算權重參數 \(W\) 的梯度；
3. 根據上一步計算得到的梯度更新權重參數 \(W\)。

限制

雖然實驗結果表明 GNN 是一種用于模組化結構資料的強大架構，但原始 GNN 仍然存在一些局限性。

1. 對于固定點來疊代更新節點的隐藏狀态是十分低效的。如果放寬固定點的假設，可以設計一個多層 GNN 來獲得節點及其鄰域的穩定表示。
2. GNN 在疊代中使用相同的參數，而大多數流行的神經網絡在不同的層中使用不同的參數來進行分層特征提取。此外，節點隐藏狀态的更新是一個順序過程，可以利用 RNN 核心，如 GRU 和 LSTM，來進一步優化。
3. 存在一些邊緣（edges）的資訊特征無法在原始 GNN 中有效模組化。例如，知識圖中的邊緣具有關系類型，并且通過不同邊緣的消息傳播應根據其類型而不同。此外，如何學習邊緣的隐藏狀态也是一個重要問題。
4. 如果我們專注于節點的表示而不是圖形，則不适合使用固定點，因為固定點中的表示分布将在值上非常平滑并且用于區分每個節點的資訊量較少。

圖神經網絡的變體

主要是從圖類型、傳播類型和訓練方法三個方面來對圖神經網絡的一些變體進行探讨。

圖類型（Graph Type）

在原始的 GNN 中，輸入的圖形包括帶有标簽資訊的節點和無向的邊，這是一種最簡單的圖形式。但在現實生活中，存在多種圖的變體，主要包括有向圖、異構圖和帶有邊資訊的圖。

有向圖：即圖中的邊是存在方向的。有向邊可以帶來比無向邊更多的資訊。

異構圖：即圖中存在多種類型的節點。處理異構圖的最簡單方法是将每個節點的類型轉換為與原始特征連接配接的 one-hot 特征向量。

帶有邊資訊的圖：即圖中的每條邊也存在權重或類型等資訊。這種類型的圖有兩種解決辦法，一種是将圖形轉化為二部圖，原始邊也作為節點，并将其分割成兩條新的邊，分别連接配接原始邊的兩端節點；第二種方法是調整不同的權重矩陣，以便在不同類型的邊緣上傳播。

傳播類型（Propagation Type）

對于擷取節點或者邊的隐藏狀态，神經網絡中的傳播步驟和輸出步驟至關重要。在傳播步驟方面的改進主要有卷積、注意力機制、門機制和跳躍連接配接（skip connection），而在輸出步驟通常遵循簡單的前饋神經網絡設定。

卷積。Graph Convolutional Network（GCN）希望将卷積操作應用在圖結構資料上，主要分為 Spectral Method 和 Spatial Method（Non-spectral Method）兩類。Spectral Method 希望使用譜分解的方法，應用圖的拉普拉斯矩陣分解進行節點的資訊收集。Spatial Method 直接使用圖的拓撲結構，根據圖的鄰居資訊進行資訊收集。

注意力機制。Graph Attention Network 緻力于将注意力機制應用在圖中的資訊收集階段。

門機制。這些變體将門機制應用于節點更新階段。Gated graph neural network 将 GRU 機制應用于節點更新。很多工作緻力于将 LSTM 應用于不同類型的圖上，根據具體情境的不同，可以分為 Tree LSTM、Graph LSTM 和 Sentence LSTM 等。

殘差連接配接。注意到堆疊多層圖神經網絡可能引起資訊平滑的問題，很多工作将殘差機制應用于圖神經網絡中，文中介紹了 Highway GNN 和 Jump Knowledge Network 兩種不同的處理方式

訓練方法（Training Method）

原始圖卷積神經網絡在訓練和優化方法中具有若幹缺點。例如，GCN 需要完整的圖拉普拉斯算子，這對于大圖來說是計算成本十分高。而且，層 \(L\) 的節點的嵌入是通過層 \(L-1\) 的所有該節點的鄰居來進行計算的。是以，單個節點的感覺域相對于層數呈指數增長，單個節點的計算梯度成本很高。最後，GCN 針對固定圖形進行獨立訓練，缺乏歸納學習的能力。

該方面的改進主要是提出了以下方法：

W. L. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” NIPS 2017, pp. 1024–1034, 2017.

J. Chen, T. Ma, and C. Xiao, “Fastgcn: fast learning with graph convolutional networks via importance sampling,” arXiv preprint arXiv:1801.10247, 2018.

W. Huang, T. Zhang, Y. Rong, and J. Huang, “Adaptive sampling towards fast graph representation learning,” in NeurIPS 2018, 2018, pp. 4563–4572.

J. Chen, J. Zhu, and L. Song, “Stochastic training of graph convolutional networks with variance reduction.” in ICML 2018, 2018, pp. 941–949.

Q. Li, Z. Han, and X.-M. Wu, “Deeper insights into graph convolutional networks for semi-supervised learning,” arXiv preprint arXiv:1801.07606, 2018.

通用架構

除了提出圖神經網絡的不同變體之外，一些研究人員從神經網絡的架構入手，提出了一些通用架構，旨在将不同模型內建到一個單一架構中。主要包括

Message Passing Neural Networks

（MPNN）、

Non-local Neural Networks

（NLNN）以及

Graph Network

（GN）等。

Message Passing Neural Networks

針對圖結構的監督學習架構，MPNN1 架構抽象了幾種最流行的圖形結構資料模型（如圖卷積中的光譜方法和非光譜方法，門控神經網絡，互動網絡，分子圖卷積，深度張量神經網絡等）之間的共性，

Non-local Neural Networks

NLNN2 利用深度學習捕捉長範圍的依賴關系，這是對非局部平均運算 3 的一種泛化，非局部運算通過計算對所有位置的特征的權重和來得到目前位置的影響，此處的位置集合可以是空間、時間或者時空。

Graph Networks

GN4 被提出來泛化和擴充多種圖神經網絡，以及 MPNN 和 NLNN 方法。本文主要介紹了圖的定義、GN block、核心 GN 計算單元、計算步驟和基本設計原則。詳細的内容擴充會另外寫到專門針對該文獻的閱讀筆記當中。

應用

圖形神經網絡已經在監督，半監督，無監督和強化學習設定的廣泛問題領域中進行了探索，這裡僅列舉了一些代表性的應用。

開放性問題

盡管 GNN 在不同領域取得了巨大成功，但值得注意的是，GNN 模型不足以在任何條件下為任何圖形提供令人滿意的解決方案。在本節中，我們将陳述一些開放性問題以供進一步研究。

淺層結構（Shallow Structure）

傳統的深度神經網絡可以堆疊數百層以獲得更好的性能，因為更深的結構具有更多的參數，進而能夠顯著提高表示能力。而圖神經網絡通常都很淺，大多數不超過三層。正如 5 中的實驗所示，堆疊多個 GCN 層将導緻過度平滑，也就是說，所有頂點将收斂到相同的值。盡管一些研究人員設法解決了這個問題6，7，但它仍然是 GNN 的最大限制。設計真正的深度 GNN 對于未來的研究來說是一個令人興奮的挑戰，并将對了解 GNN 做出相當大的貢獻。

動态圖結構（Dynamic Graphs）

另一個具有挑戰性的問題是如何處理具有動态結構的圖形。靜态圖是穩定的，是以可以容易地模組化，而動态圖則引入變化的結構。當邊和節點出現或消失時，GNN 無法自适應地更改。

動态 GNN 正在積極研究中，我們認為它是一般 GNN 的穩定性和适應性的重要裡程碑。

非結構性場景（Non-Structural Scenarios）

雖然我們已經讨論了 GNN 在非結構場景中的應用，但我們發現沒有最佳方法可以從原始資料生成圖形。是以，找到最佳圖形生成方法将提供 GNN 可以做出貢獻的更廣泛的領域。

可伸縮性（Scalability）

如何在社交網絡或推薦系統等網絡規模條件下應用嵌入方法對于幾乎所有圖形嵌入算法來說都是一個緻命的問題，而 GNN 也不例外。擴充 GNN 很困難，因為許多核心步驟在大資料環境中的計算成本都十分高。

總結

在過去的幾年中，圖形神經網絡已成為圖域中機器學習任務的強大而實用的工具。這一進展歸功于表達能力，模型靈活性和訓練算法的進步。在本次調查中，我們對圖神經網絡進行了全面的分析。對于 GNN 模型，我們引入了按圖類型，傳播類型和訓練類型分類的變體。此外，我們還總結了幾個統一表示不同變體的一般架構。在應用程式分類方面，我們将 GNN 應用程式劃分為結構場景，非結構場景和其他場景，然後對每個場景中的應用程式進行詳細介紹。最後，我們提出了四個開放性問題，指出了圖神經網絡的主要挑戰和未來研究方向，包括模型深度，可擴充性，處理動态圖和非結構場景的能力。

參考文獻

1. Neural message passing for quantum chemistry↩
2. Non-local neural networks↩
3. A non-local algorithm for image denoising↩
4. Relational inductive biases, deep learning, and graph networks↩
5. Deeper insights into graph convolutional networks for semi-supervised learning↩
6. Deeper insights into graph convolutional networks for semi-supervised learning↩
7. Gated graph sequence neural networks↩

轉載于:https://www.cnblogs.com/ydcode/p/11050417.html