圖卷積網絡 - 圖的深度學習
作者 | Francesco Casalegno
編譯 | VK
來源 | Towards Data Science
爲什麼是圖
圖是最通用的數據結構之一,由於其強大的表達能力。在許多領域,機器學習模型已被成功地用於提取和預測圖上數據的信息,對複雜元素及其關係進行建模。這裏一些例子。
-
Traffic patterns forecasting on road networks(https://arxiv.org/abs/1802.07007)
-
Inferring missing information in a Knowledge Graph(https://arxiv.org/abs/1706.05674)
-
Predicting protein interactions for drug discovery(https://papers.nips.cc/paper/2017/file/f507783927f2ec2737ba40afbd17efb5-Paper.pdf)
-
Recommender systems based on social networks data(https://arxiv.org/abs/1902.07243)
圖是最通用的數據結構之一,由於其強大的表達能力。在許多領域,機器學習模型已被成功地用於提取和預測圖上數據的信息,對複雜元素及其關係進行建模。這是一些例子。
-
Traffic patterns forecasting on road networks(https://arxiv.org/abs/1802.07007)
-
Inferring missing information in a Knowledge Graph(https://arxiv.org/abs/1706.05674)
-
Predicting protein interactions for drug discovery(https://papers.nips.cc/paper/2017/file/f507783927f2ec2737ba40afbd17efb5-Paper.pdf)
-
Recommender systems based on social networks data(https://arxiv.org/abs/1902.07243)
不幸的是,圖形數據是非結構化和非歐幾里德的,所以建立機器學習模型來解決這些任務並不是很明顯。一方面,節點之間的連接承載着重要的信息,另一方面,要想找到一種處理這種信息的方法也並非易事。
在這篇文章中,我們將看到如何使用圖卷積網絡(GCN)來解決這個問題,它將經典卷積神經網絡(CNN)推廣到圖結構數據的情況。這篇文章的主要來源是 Kipf et al.2016、Defferrard et al.2016(https://arxiv.org/abs/1609.02907)和 Hammond et al.2009(https://arxiv.org/abs/0912.3848)的工作。
爲什麼是卷積
卷積神經網絡(CNNs)在提取複雜特徵方面已經被證明是非常有效的,卷積層是目前許多深度學習模型的主幹。CNN 在任何維度的數據方面都取得了成功:
-
在 1D 中,處理音頻信號 - 例如用於聲音分類
-
在 2D 中,處理圖像 - 例如用於早期齲齒檢測
-
在 3D 技術中,處理掃描,例如核磁共振腦成像
cnn 之所以如此有效,是因爲它能夠學習一系列濾波器來提取越來越複雜的模式。特別地,這些卷積濾波器的特徵是其緊湊的,並且有平移不變的特性。
只要有一點創造性,我們就可以將這些相同的思想應用到圖數據上。與處理歐幾里德數據(1D、2D 或 3D)相比,問題更難的是,不規則圖上的平移是一個毫無意義的概念,因此我們需要找到另一種定義圖卷積的方法。
定義圖卷積
在歐幾里得定義域上,卷積是由平移函數的乘積來定義的。但是,正如我們所說的,在不規則圖上是沒有定義的,所以我們需要從不同的角度來看待這個概念。
關鍵的思想是使用傅里葉變換。在頻域中,由於卷積定理,兩個信號的 (未定義的) 卷積變成了它們的變換的 (定義良好的) 分量乘積。所以,我們需要知道如何計算一個函數在一個圖上的傅里葉變換,我們可以把卷積定義爲
這就引出了下一個問題:我們如何定義圖的傅里葉變換?
我們將通過類比經典的傅里葉變換來解決這個問題。我們來看看一個在實數上定義的函數。它的傅里葉變換是它在頻率項下的分解,通過將函數投影在正弦波的標準正交基上得到。事實上,這些波正是拉普拉斯函數的本徵函數
如果我們推廣這個觀點,我們可以把函數的傅里葉變換定義爲它在拉普拉斯特徵函數的正交基上的投影:
在圖論中,拉普拉斯矩陣定義爲 L=D-A,其中
-
D、 度矩陣是對角線矩陣,包含每個頂點的邊數;
-
A、 鄰接矩陣表示每對頂點是否通過邊連接。
假設圖中的邊是間接的 (定義可以推廣),則拉普拉斯矩陣 L 是一個實對稱正半定矩陣。因此存在一個對其進行對角化的標準正交矩陣 U,一個圖信號的圖傅里葉變換,用 N 個頂點的值的 N 維向量表示,可以定義爲其在這樣的基上的投影:
既然一張圖片勝過千言萬語,讓我們用具體的例子來看看這一切意味着什麼。如果我們取對應於規則二維網格的 Delauney 三角剖分的圖形,我們可以看到該圖形的傅里葉基完全對應於自由方形膜的振動模態。這是有道理的,因爲振動板的基本模態正是拉普拉斯函數的本徵函數。
如果我們使用隨機生成的圖,我們仍然可以通過觀察圖的正交傅里葉基,可以看到圖的振動模式。
既然我們知道了如何定義圖傅立葉變換,也知道了如何定義圖卷積,我們就可以理解圖卷積網絡的體系結構了!
全神經網絡的建立
所有用於圖像識別的卷積網絡的結構趨向於使用相同的結構。對於 VGG16 這樣的簡單網絡也是如此,但是對於 ResNet 這樣的複雜網絡也是如此。
-
通過一系列的局部卷積濾波器和池化層來提取 HxWxC 輸入圖像的特徵。
-
產生的特徵通道被映射到一個固定大小的向量,例如使用一個全局池層。
-
最後,使用幾個全連接的層來產生最終的分類輸出。
圖卷積網絡的結構遵循完全相同的結構!
對於 GCN,我們的輸入由以下元素表示:
-
NxC 向量 x,對於圖的 N 個節點中的每一個頂點,包含 C 個特徵
-
NxN 鄰接矩陣
爲了完全理解上面所示的體系結構,我們還需要澄清最後兩個概念:如何定義池層以及如何保證卷積濾波器具有緊湊性
對於池層,我們可以選擇任何一種在保持局部幾何結構的同時將節點集合合併在一起的圖聚類算法。鑑於最優圖聚類是一個 NP-hard 問題,在實際應用中採用了快速貪心近似。一個流行的選擇是 Graclus 多級聚類算法。
關於卷積濾波器的緊湊性,我們如何保證 GCN 的卷積層在局部工作?一般來說,輸入 x 由 g 過濾爲
然而,在沒有進一步假設的情況下,這種濾波器不具有緊支撐,而且學習ĝ(λ)的所有分量具有 O(N)複雜性。爲了解決這兩個問題,我們將使用 K 次多項式參數化:
這將學習複雜度降低到 O(K),因爲我們只需要學習θ_0,…,θ_{K-1}。和最重要的是, 它可以表明ĝ是 K-localized,
在正方形和不規則處進行緊湊濾波:
關於計算優化的最後觀察。計算濾波信號ĝ(L)x 的成本仍然高達 O(N^2),因爲乘法涉及 U。但是,通過用切比雪夫多項式表示多項式(具有非常方便的遞歸公式),可以將此成本降低到 O(EK)(其中 E 是邊數)。
結論
-
從知識圖到社交網絡,圖應用無處不在。
-
卷積神經網絡(CNNs)在許多領域都取得了成功,可以推廣到圖卷積網絡(GCNs)。
-
圖的卷積是通過圖的傅立葉變換來定義的。
-
圖傅里葉變換又被定義爲拉普拉斯特徵值的投影。
-
對於傳統的 cnn,GCN 由幾個卷積層和池層組成,用於特徵提取,然後是最後的完全連接層。
-
爲了確保卷積濾波器具有緊湊的支持,我們使用多項式參數化。切比雪夫多項式可以降低計算複雜度。
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/clO8H_xFeOlFkLCKiGOxDw