《Geometric Deep Learning學習筆記》第二篇，在Graph上定義卷積操作，圖卷積網絡

徐土豆 2020-11-26 15:51 339 閱讀 4 贊 4 收藏 0 評論

我們曾在[1]中探討了歐幾里德結構數據（如圖像，音視頻，文本等）和非歐幾里德結構數據（如Graph和Manifold等）之間的不同點，在本文中，我們探討如何在非歐幾里德結構數據，特別是Graph數據上定義出卷積操作，以便于實現深度神經學習。本文轉載自徐飛翔的“《Geometric Deep Learning學習筆記》第二篇，在Graph上定義卷積操作，圖卷積網絡”

版權聲明：本文為博主原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。

非歐幾里德數據嵌入歐幾里德空間

我們提到過歐幾里德數據可以很容易嵌入到歐幾里德空間中，無論是樣本空間還是經過特征提取后的特征空間，這個特性可以方便后續的分類器設計。然后，遺憾的是，非歐幾里德數據因為天然地具有不固定的領域元素數量或者連接數量等，不能直觀地嵌入歐幾里德空間，并且也很難在Spatial上定義出卷積操作出來，而這個卷積操作，在歐幾里德數據上是很直觀可以定義出來的，如：

$(f⋆γ)(x)=∫_{ Ω} f(x−x ′ )γ(x ′ )dx ′ （1.1）$

因此我們后續要想辦法在非歐幾里德數據，比如常見的Graph數據上定義出卷積操作。在進一步探討之前，我們不妨先探討下什么叫做 嵌入到歐幾里德空間以及為什么要這樣做。一般來說，歐幾里德數據因為其排列整齊，天然可以嵌入到歐幾里德空間內，并且進行歐幾里德空間下定義的算子的度量，比如歐式距離等，然后可以進一步的進行樣本之間的距離計算以及分類聚類等更為高級的操作。然而，非歐數據不能直接嵌入到其中，需要用特定的方法才能嵌入到歐幾里德空間中，在Geometric Deep Learning中，這個特定方法就是指的是深度學習方法，整個框圖如：

Fig 1. 將非歐幾里德結構數據通過深度學習方法映射到歐幾里德結構的特征空間中。

有了這個操作，即便是對于元素排列不整齊的Graph或者Manifold，也可在歐幾里德空間進行樣本之間的距離度量了，而且，這個過程還往往伴隨著降維，減少計算量，方便可視化等優點。這個將會方便后續的分類器，聚類器等設計。

Graph Deep Learning

因為Graph數據是最為常見的非歐幾里德數據，我們這里以圖深度學習為例子。圖深度學習的任務目標可以分為幾種：

將有著不同拓撲結構，不同特征的圖分類為幾類。在這種情況是對整個Graph進行分類，每個Graph有一個標簽。
對一個Graph的所有節點node進行分類。這種情況相當于是文獻引用網絡中對文獻類型分類，社交網絡對用戶屬性分類，每個節點有一個標簽。
生成一個新的Graph。這個相當于是藥物分子的生成等。

Fig 2. 使用GNN去探索新的藥物分子。

其中，最為常見的是第一類型，我們對此進行詳細的任務定義如：

我們用 $\mathcal{G}=\{A, F\}$ 表示一個圖，其中 $A \in \{0,1\}^{n \times n}$ 是對于圖的鄰接矩陣[2]，而 $F \in \mathbb{R}^{n \times d}$ 是節點的特征矩陣，其中表示有個節點，表示每個節點有個特征。給定一個有標簽的樣本集:

$\mathcal{D} = \{(G_1, y_1), \cdots, (G_n, y_n)\}$ ，其中 $y_i \in \mathcal{Y}$ 是標簽有限集合，并且對應于 $G_i \in \mathcal{G}$ ，那么我們的學習目標就是學習到一個映射使得： $f: \mathcal{G} \rightarrow \mathcal{Y}$

在頻域定義卷積

我們之前談到在spatial域上難以直接定義graph的卷積操作，那么我們自然就想到如果能在頻域定義出來卷積，那也是不錯的，因此我們接下來想要探討怎么在頻域定義卷積。在此之前，我們需要了解下熱傳播模型的一點東西，因為圖中節點的信息傳遞，一般來說是通過鄰居節點進行傳遞的，這一點和物體將熱量從高到低的傳遞非常相似，可以對此建立和熱傳遞相似的模型。

在[3]的這篇回答中，作者對熱傳播和圖節點信息傳遞進行了非常精彩的闡述，并且引出了 拉普拉斯矩陣(Laplacian Matrix) 對于節點之間關系的描述作用，值得各位讀者參考。

總的來說，就是對拉普拉斯矩陣進行特征值分解，其每個特征向量可以看成是頻域中正交的正交基底，其對應的特征值可以看成是頻率，對拉普拉斯矩陣進行特征值分解的公式如下：

$ΔΦ _{k}=Φ _{k}Λ _{k}(2.1) $

其中 $\Delta$ 是拉普拉斯矩陣，而 $\mathbf{\Phi}_{k}$ 是前個拉普拉斯特征向量組成的矩陣，而 $\mathbf{\Lambda}_k$ 是由對應特征值組成的對角矩陣。我們接下來先暫時忘記這個(2.1)公式，我們要對整個圖的拓撲結構進行表示，那么通過鄰接矩陣A就可以很容易的表示出來，其中，無向圖的鄰接矩陣是對稱矩陣，而有向圖的鄰接矩陣則不一定，讓我們舉一個例子方便接下來的討論，如Fig 4所示，這是個無向圖的例子。其中我們之前談到的拉普拉斯矩陣可以用公式(2.2)

確定，其中D DD為度數矩陣，A AA為鄰接矩陣，整個過程如Fig 3.所示。

Fig 3. 一個圖結構數據的例子，其中有度數矩陣，鄰接矩陣和拉普拉斯矩陣。

總的來說，用拉普拉斯矩陣可以在某種程度上表示一個Graph的拓撲結構，這點和鄰接矩陣相似。

注意到我們有對拉普拉斯矩陣L LL的特征值分解：

其中 $U = [u_0, \cdots,u_{n-1}] \in \mathbb{R}^{n \times n}$ 為正交矩陣，其每一列都是特征向量，而

$\Lambda = \mathrm{diag}([\lambda_0, \cdots, \lambda_{n-1}]) \in \mathbb{R}^{n \times n }$ 是一個對角矩陣，其每個對角元素都是對應特征向量的特征值。對式子(2.3)進行變換，注意到正交矩陣的轉置等于其逆，我們有：

$L= UΛU^{−1} $

$= UΛU^{T}(2.4) $

因此，對于一個給定信號 $x \in \mathbb{R}^n$ 來說，其傅立葉變換可以定義為 $\hat{x} = U^{T} x\in \mathbb{R}^n$ ，其反傅立葉變換為 $x = U\hat{x}$ ，我們用符號 $*_{\mathcal{G}}$ 表示圖傅立葉變換。那么對于信號

和卷積核，我們有：

$x∗_{\mathcal{G}}y=U((U^{T} x)⊙(U^{T} y))(2.5)$

其中 $\odot$ 表示逐個元素的相乘。

那么對于一個卷積核 $( ⋅ ) g_{\theta}$ ，我們有：

$\begin{aligned} y &= g_{\theta}(L)(x) = g_{\theta}(U\Lambda U^{T})x = U g_{\theta}(\Lambda)U^{T}x \\ &\mathrm{where} \ \ g_{\theta}(\Lambda) = \mathrm{diag}(\theta) = \begin{bmatrix} \theta_1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & \theta_{n-1} \end{bmatrix} \end{aligned}(2.6)$

其中我們需要學習的參數就在 $\mathrm{diag}(\theta)$ 中，一共有個。

類似于一般歐幾里德結構數據的傅立葉變換，在圖傅立葉變換中，其每個基底（也就是特征向量）也可以可視化出來，如Fig 4所示:

Fig 4. 圖傅立葉變換的基底可視化，每個紅色區域的都是卷積核中心，可以類比為熱傳遞中的熱量中心。

Fig 5. manifold傅立葉變換的基底可視化，每個紅色區域的都是卷積核中心，可以類比為熱傳遞中的熱量中心，對于Manifold來說也有類似的性質。

ChebNet，切比雪夫網絡

上面介紹的網絡有兩個很大的問題：

它們不是在空間上具有局部性的，比如二維圖像的卷積網絡就具有局部性，也稱之為局部連接，某個輸出神經元只是和局部的輸入神經元直接相連接。這個操作有利于減少計算量，參數量和提高泛化能力。
計算復雜度為 $\mathcal{O}(n)$ ，和節點的數量成比例，不利于應用在大規模Graph上。
為了解決第一個問題，我們把 $g(\theta)$ 寫成：

$gθ (Λ)=\sum_{k=0}^{K}{\theta_{k}}\Lambda^{k}$ , $\in \mathbb{R}^{k}$

我們在圖論中知道有個結論：

若節點和節點的最短路徑 $d_{\mathcal{G}}(i,j) > K$ ，那么有 $(L^{K})_{i,j} = 0$ ，其中為拉普拉斯矩陣。

因此有：

$(gθ (L)δ_{ i })_{j}=(gθ (L))_{i,j} =\sum_{k}=θ_{k}( L^{k})_{i,j} (3.2) $

不難看出當，其中為預設的核大小時， $(L^k)_{i,j}=0$ ，因此式子(3.2)其實只有前項不為0，因此是具有K-局部性的，這樣我們就定義出了局部性，那么計算復雜度變成了 $\mathcal{O}(K)$ 。

注意到，在式子 $y=Ug_{\theta}(\Lambda)U^{T}$ 中，因為 $U \in \mathbb{R}^{n \times n}$ ，因此存在, 的矩陣相乘，其計算復雜度為 $\mathcal{O}(n^2)$ ，而且每次計算都要計算這個乘積，這個顯然不是我們想看到的。

一種解決方法就是把 $g_{\theta}(L)$ 參數化為一個可以從L LL遞歸地計算出來的多項式，用人話說就是可以k kk時刻的 $g_{\theta}(L)$ 可以由時刻的 $g_{\theta}(L)$ 簡單地通過多項式組合計算出來。在文章[5]中，使用了切比雪夫多項式展開作為這個近似的估計。該式子可表示為：

$Tk_{x}=2xT_{k-1}(x)−T_{k-2}(x), where$ $T_{0}=1,T_{1}=x(3.3)$

因此我們最后有：

$g\theta(\Lambda)=\sum_{k=0}^{k}\theta_{k}T_{k}(\tilde{\Lambda})(3.4)$

式子(3.4)仍然是和 $\Lambda$ 有關的值，我們希望直接和相關，以便于計算，因此繼續推導，有：

$g\theta(\Lambda)=\sum_{k=0}^{k}\theta_{k}\Lambda^{k}$

$Ug\theta(\Lambda)U^{T}=\sum_{k=0}^{k}\theta_{k}U\Lambda^{k}U^{T}(3.5)$

注意到是冪等矩陣，也就是有，因此繼續推導(3.5)有：

$U\Lambda^{k}U^{T}=(U\Lambda U^{T})^{k}=L^{k}$

$\Rightarrow Ug\theta(\Lambda)U^{T}=\sum_{k=0}^{k}\theta_{k}L^{k}(3.6)$

同樣的，采用切比雪夫多項式展開，有：

$g\theta(\Lambda)\approx\sum_{k=0}^{k}\theta_{k}T_{k}(\tilde{L})(3.7)$

因此，最后對于第個輸出的特征圖而言，我們有：

$y_{s,j}=\sum_{i-1}^{Fin} g\theta_{i,j}(L)x_{s,i} \in \mathbb{R}^{n}(3.8)$

其中 $x_{s,i}$ 是輸入的特征圖，表示第個樣本。因此我們一共有 $F_{in} \times F_{out}$ 個向量，每個向量中有個參數，因為 $\theta_{i,j} \in \mathbb{R}^{K}$ ，最后一共有 $F_{in} \times F_{out} \times K$ 個可訓練參數。其中的 $g_{\theta_{i,j}}(L)$ 是采用了切比雪夫多項式展開，因此可以遞歸運算，以減少運算復雜度。

ChebNet一階近似

根據我們之前的討論，階的可以表示為：

$y=Ug\theta(\Lambda)U^{T}x=\sum_{k=0}^{K}\theta_{k}U\Lambda^{k}U^{T}x(4.1)$

我們從網絡的設計中知道，的卷積核在足夠多的的層數的疊加后，有足夠的層次信息可以提供足夠大的感知野[6]。因此，也許對于的一階近似就足夠了，因此我們將，有：

$yK=1=\theta_{0}x+\theta_{1}L_{x}=\theta(D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x(4.2)$

在式子(4.2)中，我們假設了 $\theta_0 = -\theta_1$ ?以進一步減少參數量，而且對拉普拉斯矩陣進行了歸一化，這個歸一化操作我們接下來會繼續討論，這里暫且給出歸一化的公式為：

$L=I_{n}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}(4.3)$

其中，是度數矩陣， $D_{i,i} = \sum{j} A_{i,j}$ 。

另外，為了增加節點自身的連接（這個我們以后繼續講解），我們通常會對鄰接矩陣A AA進行變化，有：

$\tilde{A}=A+I_{n}$

$\tilde{D }_{i,i}=\sum_{j}\tilde{A}_{i,j}(4.4)$

因此最終有ChebNet的一階近似結果為：

$g\theta\ast\mathcal{G}x=\theta(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}})x(4.5)$

對(4.5)進行矩陣表達并且加入激活函數 $\sigma(\cdot)$ ，有 Graph Convolution Network(GCN) 的表達[7]，如：

$H^{(l+1)}=\delta(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}H^{(l)} W^{(l)} )(4.6)$

其中的 $H^{(l)}$ 是層的特征圖， $W^{(l)}$ 是層的可學習參數。其中激活函數一般選擇，即是 $\sigma(x) = \max(0,x)$ 。

本篇文章就此結束，我們在下一篇文章將會繼續介紹GCN在空間域上的理解，即是基于消息傳遞（Message Passing）中的解釋，并且會舉出一些例子來方便理解。

該系列其他文章

《學習geometric deep learning筆記系列》第一篇，Non-Euclidean Structure Data之我見
《Geometric Deep Learning學習筆記》第三篇，GCN的空間域理解，Message Passing以及其含義

Reference

[1].https://blog.csdn.net/LoseInVain/article/details/88373506

[2].https://en.wikipedia.org/wiki/Adjacency_matrix[

3].https://www.zhihu.com/question/54504471/answer/630639025

[4].https://blog.csdn.net/wang15061955806/article/details/50902351

[5]. Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering[C]//Advances in neural information processing systems. 2016: 3844-3852.

[6]. Simonyan K, Zisserman A. Very deep convolutional networks for large-scale image recognition[J]. arXiv preprint arXiv:1409.1556, 2014.

[7]. Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016.

聲明：本內容為作者獨立觀點，不代表電子星球立場。未經允許不得轉載。授權事宜與稿件投訴，請聯系：editor@netbroad.com

覺得內容不錯的朋友，別忘了一鍵三連哦！

贊 4

關注 52

成為作者賺取收益

下一篇：《Geometric Deep Learning學習筆記》第三篇，GCN的空間域理解，Message Passing以及其含義

全部留言

0/200

成為第一個和作者交流的人吧

99久久全国免费观看_国产一区二区三区四区五区VM_久久www人成免费看片中文_国产高清在线a视频大全_深夜福利www_日韩一级成人av

《Geometric Deep Learning學習筆記》第二篇， 在Graph上定義卷積操作，圖卷積網絡

非歐幾里德數據 嵌入 歐幾里德空間