一文輕鬆了解Graph Neural Networks

• 2020 年 3 月 4 日
• 筆記

作者：Joao Schapke 編譯: Congqing He

❝圖神經網絡有哪些應用領域？又有哪些圖神經網絡？這篇文章告訴你！ ❞

圖結構數據在各個領域都很常見，例如{分子、社會、引用、道路}網絡等，這些只是可以用圖表示的大量數據中的一小部分。隨着機器學習的進步，我們見證了在可用數據上應用智能算法的潛力。圖神經網絡是機器學習的一個分支，它以最有效的方式建立圖數據的神經網絡。

儘管ML在卷積網絡的計算機視覺領域取得了進展，但圖神經網絡(GNNs)面臨著一個更具挑戰性的問題，即處理圖的笨拙性質。與圖像和文本不同，圖形沒有一個定義良好的結構。一個圖的節點可能沒有或有多個連接，這些連接可以是定向的，也可以是無定向的。數據集中的圖形可能具有可變數量的節點和邊，無法正確地調整大小，它們可能是無環的、循環的、聯合的或不聯合的。總之，它使處理數據的過程更具挑戰性。

處理圖的一種簡單方法是連接節點，並建立一個更友好的結構化數據集，該數據集可以饋送到多層感知器（MLP）中，儘管這不是一種非常優雅的方法，但它可以提供良好的結果。儘管不足以處理多個可變大小和拓撲圖或大型圖，這些圖會嚴重增加輸入的維數。利用遞歸神經網絡(RNNs)將圖轉換為節點序列，可以處理可變大小的圖。但是，這種策略也是註定要失敗的，圖中最重要的信息之一就是它的結構，它在節點序列中不會留下任何痕迹。圖形數據需要更健壯的方法來處理它們的結構。

然而，由於處理圖的困難，以及卷積網絡的發展，使得GNN領域有了更多的研究和新的方法。卷積層具有一些有用的特性，例如:局部連通性，假設它們相鄰的像素高度相關。移位不變性，卷積會了解對象的特徵，儘管它們具有空間位置。它們還能夠在任何大小的圖像上進行卷積。所有這些都是圖神經網絡真正吸引人的功能，應該重視局部連通性，因為節點的鄰居與節點本身相關，因此它們應該是移位不變的，因為鄰居應該對卷積具有相同的含義。儘管在圖上所處的位置特殊，但它們也應與圖的大小無關。

這就產生了在圖數據中應用卷積的不同方法，主要分為基於譜的圖數據卷積和基於空間的圖數據卷積。

譜圖卷積

譜圖卷積(Spectral Graph Convolutions)是一種更有原則的卷積方法，它以信號預處理理論為基礎。

在不深入研究譜卷積背後的理論的情況下，已經證明空間域的卷積等於頻域的乘法(卷積定理)。同樣的定理也適用於圖，但是不是使用離散傅立葉變換矩陣作為基礎，而是使用圖拉普拉斯算子的特徵向量。

圖的拉普拉斯定義為:

其中I為單位矩陣，D為對角階矩陣，A為圖的鄰接矩陣。

頻譜卷積的主要限制是依賴於拉普拉斯矩陣的特徵向量，每個計算都需要拉普拉斯矩陣的特徵向量，反向傳播時需要的時間複雜度，特徵分解時需要的時間複雜度。

進一步的工作通過使用Chebyshev多項式和Cayley多項式逼近方程來減輕時間複雜度。

GCN（圖卷積網絡）對使用Chebyshev多項式的ChebNet網絡進行了進一步簡化。

空間圖卷積

空間卷積是圖卷積的一種更為寬鬆的形式，它是由GCN對之前的譜GNN進行簡化而得到普及。

空間卷積在節點上進行空間卷積的方式與常規卷積相似。卷積從像素本身(像素放置在與新像素相同位置的像素)和周圍像素生成新像素，空間圖卷積通過聚集一個節點和它的鄰居形成一個新節點來進行卷積。

下面通過圖片說明網格結構圖像中的正則卷積與空間圖卷積之間的區別。

單個節點的空間圖卷積可以定義為：

其中表示當前節點i,對於它的鄰接節點 ， 是節點的所有鄰居節點的集合

我們注意到這個卷積會將一個節點的局部信息聚合到一個新的節點中。從GCN的論文中我們有

和前面的方程相似，是一個應用於卷積的非線性激活函數。

是圖的鄰接矩陣加上單位矩陣，這將使每個節點與它的鄰居進行集合。

是一階對角矩陣。如果在第一個等式中注意到我們正在對節點i的所有鄰居求和，並且圖中的節點可以具有任意數量的鄰居，則應注意，我們必須對求和結果進行歸一化。乘以反對角矩陣即可。

這個簡單的操作是空間卷積的基礎。通過將其中的一些層與dropout層疊加，使用L2正則化並使用ReLU作為激活函數，使用Adam作為優化器，GCN能夠實現3節點分類基準的SOTA。

「注意，當前使用的事實上的方法是基於空間的卷積。這提供了一種更有效，更簡單的圖形卷積方法。」

Graph神經網絡可以處理各種各樣的問題，列舉一些問題，並給出如何解決的主要直覺：

• 節點預測: 是預測一個或多個圖中節點的值或標籤的任務。例如，在引文網絡中預測論文的主題。

這些任務可以簡單地通過應用上述卷積來解決。大多數基準測試採用半監督設置，其中數據集由單個圖組成，其中一些節點標籤用於訓練/驗證，另一些用於測試。

• 圖預測:，預測一個圖形的值或標籤。例如，預測特定分子的毒性。

這些任務通常通過應用兩個圖卷積層來聚合節點之間的信息，然後使用某種讀出操作將圖中的所有節點聚合成固定大小的表示形式，然後應用MLP模型來獲得最終結果。

讀取操作可以簡單地取所有節點上的average/ maxpooling。

• 圖生成: 生成圖形。例如，產生具有理想性質的新分子，如藥物相似性和合成可及性。

這些問題可以用圖自動編碼器來解決。

• 邊預測： 模擬到節點的預測，預測邊緣的值或標籤，例如預測知識庫中兩個實體是否相關。

預測邊一般採用圖卷積層來解決，雖然大多數數據集和論文都是針對節點預測的，但也有一些模型側重於邊預測，大多數節點預測模型可以推廣到邊預測。

更多的例子任務(以及基準和論文)可以在這裡找到(https://paperswithcode.com/area/graphs)。

進一步，我們探討了圖卷積網絡和GNNs的一些擴展。

時空圖神經網絡

GNNs還可以用來處理時間預測問題或處理時變數據的預測問題(如交通流量預測)。

時空圖數據以多個圖的形式出現，每個圖表示一個時間步長，圖的大小可能不同。

使用RNNs或CNNs處理序列圖有兩種主要的方法：

• RNN解決方案一般將圖卷積應用於節點級信息的聚合，將RNNs應用於時間級信息的聚合。
• CNN方法遵循相同的思想，通常將圖卷積應用於聚合節點，然後將一維卷積應用於時間級信息。

然後根據任務是否基於圖，將讀出操作應用於圖以生成單個輸出值。

卷積神經網絡的一個缺點是不能很好地處理非局部相關。

圖卷積僅考慮一階鄰居，儘管可以將多個卷積層堆疊在一起以從更大的鄰域中獲取信息，但是輸入圖的大小是任意的，因此無法正確調整大小，因此節點通常不會獲取圖的全局信息。

「Example」

下圖是預測交通流量：

該圖像包含幾個興趣點（POI），應該對其流量進行預測。這是非常適合時空GNN的任務，因為道路自然是圖形結構，並且所有區域信息（例如附近學校或公園的存在）都可以嵌入到圖形中。任務也與時間有關，流量會根據一天中的小時或一周中的一天而變化。

自然地，我們看到與預測有重要的局部相關性，交通流量取決於其附近的事物。而且我們還注意到非局部的，上下文的相關性。特別是，我們可以假設POI1和POI3的流量高度相關，因為兩個點都位於附近有醫院和遊樂園的學校。能夠識別這種上下文相關性應該可以改善模型的通用性。Geng等人(http://www-scf.usc.edu/~yaguang/papers/aaai19_multi_graph_convolution.pdf)提出的解決方案是測量興趣點之間的相似度，如果它們非常相似，則將考慮以下信息：

是一個矩陣，其作用與上面的GCN方程中的鄰接矩陣類似。

但是，這是一個特定於任務的問題，許多任務不具有非局部相關性，而在基於圖的任務中，這個問題通過讀取操作得到了緩解。

基於注意力機制的方法

新研究的另一個重要靈感來源是注意力機制的發展和端到端的注意力模型，這些模型在NLP的各種基準中都達到了最新水平。

注意力機制的方法已成功應用於許多圖卷積網絡，如GAT (https://arxiv.org/pdf/1710.10903.pdf) 和 GAAN (https://arxiv.org/pdf/1803.07294.pdf)。與標準圖卷積網絡（如GCN）不同，GCN在執行卷積時會向所有相鄰節點賦予相同的權重，而GAT引入了一種關注機制，該機制將不同的權重分配給節點的鄰居。

有趣的是，NLP中最初的Transformer模型也適用於處理圖數據，因此該模型被命名為Graph Transformer (https://arxiv.org/pdf/1911.07470.pdf)。

它被應用於圖到序列的任務(Graph-Sequence)，其中模型接收圖並輸出序列，該模型必須從抽象含義表示（AMR）圖中生成文本。解決任務的常用方法是為圖生成嵌入（主要是通過使用GNN），然後用其訓練NLP模型。

儘管圖卷積通常用於生成嵌入，但作者指出，這些在學習節點之間的遠距離關係方面存在困難。簡而言之，他們使用圖自動編碼器根據節點之間的最短距離創建圖的嵌入。

結論

與機器學習的其他每個領域類似，圖神經網絡是一個快速發展的領域。

但是與許多其他問題不同，GNN中的大多數問題都沒有完善的解決方案或作為即插即用求解器的高級模型體系結構。圖域中的問題肯定需要垂直思考，並且根據問題和數據，各種各樣的解決方案都可以產生出色的結果。來自kaggle比賽的一個例子為了預測分子在特定鍵中原子之間的相互作用力，第一個解決方案解決了端到端圖形轉換器的問題，而第二個到第四個解決方案利用圖手工製作了序列並使用了標準的NLP變形器其他方法使用了更通用的圖卷積神經網絡（例如GAT和GCN），或者使用了專門為處理該領域的數據而構建的GNN（例如SchNet）。這表明了領域內方法的異質性。

GNN內還有許多有趣的主題，此處未提及。一些未提及的主題：圖遞歸神經網絡，圖自動編碼器，圖對抗方法，圖強化學習。

參考文獻

A Comprehensive Survey on Graph Neural Networks — Zonghan Wu

Deep Learning on Graphs: A Survey — Ziwei Zhang

Graph Neural Networks: A Review of Methods and Applications — Jie Zhou, Ganqu Cui, Zhengyan Zhang