在從圖(Graph)到圖卷積(Graph Convolution): 漫談圖神經網絡 (一)中，我們簡單介紹了基于循環圖神經網絡的兩種重要模型，在本篇中，我們將著大量筆墨介紹圖卷積神經網絡中的卷積操作。接下來，我們將首先介紹一下圖卷積神經網絡的大概框架，借此說明它與基于循環的圖神經網絡的區別。接著，我們將從頭開始為讀者介紹卷積的基本概念，以及其在物理模型中的涵義。最后，我們將詳細地介紹兩種不同的卷積操作，分別為空域卷積和時域卷積，與其對應的經典模型。讀者不需有任何信號處理方面的基礎，傅里葉變換等概念都會在本文中詳細介紹。

>>>>

從圖(Graph)到圖卷積(Graph Convolution)：漫談圖 神經?絡模型 (?)

圖卷積緣起

在開始正式介紹圖卷積之前，我們先花一點篇幅探討一個問題：為什么研究者們要設計圖卷積操作，傳統的卷積不能直接用在圖上嗎？ 要理解這個問題，我們首先要理解能夠應用傳統卷積的圖像(歐式空間)與圖(非歐空間)的區別。如果把圖像中的每個像素點視作一個結點，如下圖左側所示，一張圖片就可以看作一個非常稠密的圖；下圖右側則是一個普通的圖。陰影部分代表卷積核，左側是一個傳統的卷積核，右側則是一個圖卷積核。卷積代表的含義我們會在后文詳細敘述，這里讀者可以將其理解為在局部范圍內的特征抽取方法。

GGNN語義解析實例

仔細觀察兩個圖的結構，我們可以發現它們之間有2點非常不一樣：

• 在圖像為代表的歐式空間中，結點的鄰居數量都是固定的。比如說綠色結點的鄰居始終是8個(邊緣上的點可以做Padding填充)。但在圖這種非歐空間中，結點有多少鄰居并不固定。目前綠色結點的鄰居結點有2個，但其他結點也會有5個鄰居的情況。

• 歐式空間中的卷積操作實際上是用固定大小可學習的卷積核來抽取像素的特征，比如這里就是抽取綠色結點對應像素及其相鄰像素點的特征。但是因為圖里的鄰居結點不固定，所以傳統的卷積核不能直接用于抽取圖上結點的特征。

真正的難點聚焦于鄰居結點數量不固定上。那么，研究者如何解決這個問題呢？其實說來也很簡單，目前主流的研究從2條路來解決這件事：

• 提出一種方式把非歐空間的圖轉換成歐式空間。

• 找出一種可處理變長鄰居結點的卷積核在圖上抽取特征。

這兩條實際上也是后續圖卷積神經網絡的設計原則，圖卷積的本質是想找到適用于圖的可學習卷積核。

圖卷積框架(Framework)

上面說了圖卷積的核心特征，下面我們先來一窺圖卷積神經網絡的全貌。如下圖所示，輸入的是整張圖，在Convolution Layer 1里，對每個結點的鄰居都進行一次卷積操作，并用卷積的結果更新該結點；然后經過激活函數如ReLU，然后再過一層卷積層Convolution Layer 2與一詞激活函數；反復上述過程，直到層數達到預期深度。與GNN類似，圖卷積神經網絡也有一個局部輸出函數，用于將結點的狀態(包括隱藏狀態與結點特征)轉換成任務相關的標簽，比如水軍賬號分類，本文中筆者稱這種任務為Node-Level的任務；也有一些任務是對整張圖進行分類的，比如化合物分類，本文中筆者稱這種任務為Graph-Level的任務。卷積操作關心每個結點的隱藏狀態如何更新，而對于Graph-Level的任務，它們會在卷積層后加入更多操作。本篇博客主要關心如何在圖上做卷積，至于如何從結點信息得到整張圖的表示，我們將在下一篇系列博客中講述。

圖卷積神經網絡全貌

多說一句，GCN與GNN乍看好像還挺像的。為了不讓讀者誤解，在這里我們澄清一下它們根本上的不同：GCN是多層堆疊，比如上圖中的Layer 1和Layer 2的參數是不同的；GNN是迭代求解，可以看作每一層Layer參數是共享的。

卷積(Convolution)

正如我們在上篇博客的開頭說到的，圖卷積神經網絡主要有兩類，一類是基于空域的，另一類則是基于頻域的。通俗點解釋，空域可以類比到直接在圖片的像素點上進行卷積，而頻域可以類比到對圖片進行傅里葉變換后，再進行卷積。傅里葉變換的概念我們先按下不講，我們先對兩類方法的代表模型做個大概介紹。

基于空域卷積的方法直接將卷積操作定義在每個結點的連接關系上，它跟傳統的卷積神經網絡中的卷積更相似一些。在這個類別中比較有代表性的方法有 Message Passing Neural Networks(MPNN)[1], GraphSage[2], Diffusion Convolution Neural Networks(DCNN)[3], PATCHY-SAN[4]等。

基于頻域卷積的方法則從圖信號處理起家，包括 Spectral CNN[5], Cheybyshev Spectral CNN(ChebNet)[6], 和 First order of ChebNet(1stChebNet)[7]等。

在介紹這些具體的模型前，先讓我們從不同的角度來回顧一下卷積的概念，重新思考一下卷積的本質。

基礎概念

由維基百科的介紹我們可以得知，卷積是一種定義在兩個函數(跟)上的數學操作，旨在產生一個新的函數。那么和的卷積就可以寫成，數學定義如下：

實例:擲骰子問題

光看數學定義可能會覺得非常抽象，下面我們舉一個擲骰子的問題，該實例參考了知乎問題"如何通俗易懂地解釋卷積"[8]的回答。

想象我們現在有兩個骰子，兩個骰子分別是跟，表示骰子向上一面為數字的概率。同時拋擲這兩個骰子1次，它們正面朝上數字和為4的概率是多少呢？相信讀者很快就能想出它包含了三種情況，分別是：

• 向上為1， 向上為3；

• 向上為2， 向上為2；

• 向上為3， 向上為1；

最后這三種情況出現的概率和即問題的答案，如果寫成公式，就是?。可以形象地繪制成下圖：

卷積基本概念

如果稍微擴展一點，比如說我們認為? 或者? 等是可以取到的，只是它們的值為0而已。那么該公式可以寫成。仔細觀察，這其實就是卷積。如果將它寫成內積的形式，卷積其實就是?。這么一看，是不是就對卷積的名字理解更深刻了呢? 所謂卷積，其實就是把一個函數卷(翻)過來，然后與另一個函數求內積。

對應到不同方面，卷積可以有不同的解釋： 既可以看作我們在深度學習里常說的核(Kernel)，也可以對應到信號處理中的濾波器(Filter)。而? 可以是我們所說的機器學習中的特征(Feature)，也可以是信號處理中的信號(Signal)。f和g的卷積?就可以看作是對的加權求和。下面動圖就分別對應深度學習中卷積操作的過程[9][10]。

深度學習中的卷積

空域卷積(Spatial Convolution)

介紹完卷積的基礎概念后，我們先來介紹下空域卷積(Spatial Convolution)。從設計理念上看，空域卷積與深度學習中的卷積的應用方式類似，其核心在于聚合鄰居結點的信息。比如說，一種最簡單的無參卷積方式可以是：將所有直連鄰居結點的隱藏狀態加和，來更新當前結點的隱藏狀態。

最簡單的空域卷積

這里非參式的卷積只是為了舉一個簡單易懂的例子，實際上圖卷積在建模時需要的都是帶參數、可學習的卷積核。

消息傳遞網絡(Message Passing Neural Network)

消息傳遞網絡(MPNN)[1] 是由Google科學家提出的一種模型。嚴格意義上講，MPNN不是一種具體的模型，而是一種空域卷積的形式化框架。它將空域卷積分解為兩個過程：消息傳遞與狀態更新操作，分別由和函數完成。將結點的特征作為其隱藏狀態的初始態后，空域卷積對隱藏狀態的更新由如下公式表示：

其中代表圖卷積的第層，上式的物理意義是：收到來自每個鄰居的的消息后，每個結點如何更新自己的狀態。

如果讀者還記得GGNN的話，可能會覺得這個公式與GGNN的公式很像。實際上，它們是截然不同的兩種方式：GCN中通過級聯的層捕捉鄰居的消息，GNN通過級聯的時間來捕捉鄰居的消息；前者層與層之間的參數不同，后者可以視作層與層之間共享參數。MPNN的示意圖如下[11]：

MPNN網絡模型

圖采樣與聚合(Graph Sample and Aggregate)

MPNN很好地概括了空域卷積的過程，但定義在這個框架下的所有模型都有一個共同的缺陷：卷積操作針對的對象是整張圖，也就意味著要將所有結點放入內存/顯存中，才能進行卷積操作。但對實際場景中的大規模圖而言，整個圖上的卷積操作并不現實。GraphSage[2]提出的動機之一就是解決這個問題。從該方法的名字我們也能看出，區別于傳統的全圖卷積，GraphSage利用采樣(Sample)部分結點的方式進行學習。當然，即使不需要整張圖同時卷積，GraphSage仍然需要聚合鄰居結點的信息，即論文中定義的aggregate的操作。這種操作類似于MPNN中的消息傳遞過程。

GraphSage采樣過程

具體地，GraphSage中的采樣過程分為三步:

在圖中隨機采樣若干個結點，結點數為傳統任務中的batch_size。對于每個結點，隨機選擇固定數目的鄰居結點(這里鄰居不一定是一階鄰居，也可以是二階鄰居)構成進行卷積操作的圖。

將鄰居結點的信息通過函數聚合起來更新剛才采樣的結點。

計算采樣結點處的損失。如果是無監督任務，我們希望圖上鄰居結點的編碼相似；如果是監督任務，即可根據具體結點的任務標簽計算損失。

最終，GraphSage的狀態更新公式如下：

GraphSage的設計重點就放在了函數的設計上。它可以是不帶參數的,?, 也可以是帶參數的如等神經網絡。核心的原則仍然是，它需要可以處理變長的數據。在本系列博客的第三篇筆者會介紹卷積神經網絡中針對圖任務的ReadOut操作，函數的設計與其有異曲同工之妙，此處就不展開敘述了。

圖結構序列化(PATCHY-SAN)

我們之前曾提到卷積神經網絡不能應用在圖結構上是因為圖是非歐式空間，所以大部分算法都沿著找到適用于圖的卷積核這個思路來走。而 PATCHY-SAN 算法 [4] 另辟蹊徑，它將圖結構轉換成了序列結構，然后直接利用卷積神經網絡在轉化成的序列結構上做卷積。由于 PATCHY-SAN在其論文中主要用于圖的分類任務，我們下面的計算過程也主要針對圖分類問題(例如，判斷某個社群的職業)。

那么，圖結構轉換成序列結構最主要的挑戰在何處呢，如果簡單的話，為什么以前的工作沒有嘗試把圖轉成序列結構呢？就筆者個人的觀點來看，這種序列轉換要保持圖結構的兩個特點：1. 同構的性質。2. 鄰居結點的連接關系。對于前者而言，意味著當我們把圖上結點的標號隨機打亂，得到的仍應是一樣的序列。簡單來說就是，同構圖產生的序列應當相似，甚至一樣；對于后者，則意味著我們要保持鄰居結點與目標結點的距離關系，如在圖中的三階鄰居在序列中不應該成為一階鄰居等。

PATCHY-SAN 通過以下三個步驟來解決這兩個問題：

結點選擇(Node Squenece Selection)。該過程旨在與通過一些人為定義的規則(如度大的結點分數很高，鄰居的度大時分數較高等)為每個結點指定一個在圖中的排序。在完成排序后，取出前? 個結點作為整個圖的代表。

鄰居結點構造(Neighborhood graph construction)。在完成結點排序后，以第1步選擇的結點為中心，得到它們的鄰居(這里的鄰居可以是第一階鄰居，也可以是二階鄰居)結點，就構成了? 個團。根據第1步得到的結點排序對每個團中的鄰居結點進行排序，再取前? 個鄰居結點按照順序排列，即組成? 個有序的團。

圖規范化(Graph Noermalization)。按照每個團中的結點順序可將所有團轉換成固定長度的序列()，再將它們按照中心結點的排序從前到后依次拼接，即可得到一個長度為? 的代表整張圖的序列。這樣，我們就可以直接使用帶1D的卷積神經網絡對該序列建模，比如圖分類(可類比文本序列分類)。值得注意的一點是，在第1步和第2步中，如果取不到? 或? 個結點時，要使用空結點作填充(padding)。

一個形象的流程圖如下所示，圖源自論文[4]。

Pathcy-san framework

下圖可能可以幫助讀者更好地理解這種算法，圖來自[12]。整個流程自底向上：首先根據自定義規則對圖里的結點進行排序，然后選擇前6個結點，即圖中的 1至6；接著我們把這些結點

Patchy-san 具體樣例

頻域卷積(Spectral Convolution)

空域卷積非常直觀地借鑒了圖像里的卷積操作，但據筆者的了解，它缺乏一定的理論基礎。而頻域卷積則不同，相比于空域卷積而言，它主要利用的是圖傅里葉變換(Graph Fourier Transform)實現卷積。簡單來講，它利用圖的拉普拉斯矩陣(Laplacian matrix)導出其頻域上的的拉普拉斯算子，再類比頻域上的歐式空間中的卷積，導出圖卷積的公式。雖然公式的形式與空域卷積非常相似，但頻域卷積的推導過程卻有些艱深晦澀。接下來我們將攻克這部分看起來很難的數學公式，主要涉及到傅里葉變換(Fourier Transform)和拉普拉斯算子(Laplacian operator)。即使讀者沒有學過任何相關知識也不要緊，筆者將盡可能用形象的描述解釋每個公式的涵義，讓讀者能感悟這些公式的美妙之處。

前置內容

如上所述，在本小節，我們將介紹兩個主要的知識點：傅里葉變換與拉普拉斯算子。在介紹之前，我們先拋出兩個問題：1. 什么是傅里葉變換; 2. 如何將傅里葉變換擴展到圖結構上。這兩個問題是前置內容部分要解決的核心問題，讀者可帶著這兩個問題，完成下面內容的閱讀。

傅里葉變換(Fourier Transform)

借用維基百科的說法，**傅里葉變換(Fourier Transform, FT)**會將一個在空域(或時域)上定義的函數分解成頻域上的若干頻率成分。換句話說，傅里葉變換可以將一個函數從空域變到頻域。先拋開傅里葉變換的數學公式不談，用? 來表示傅里葉變換的話，我們先講一個很重要的恒等式：

這里的指的是傅里葉逆變換，是哈達瑪乘積，指的是兩個矩陣(或向量)的逐點乘積(Element-wise Multiplication)。仔細觀察上面這個公式，它的直觀含義可以用一句話來概括：空(時)域卷積等于頻域乘積。簡單來說就是，如果要算? 與? 的卷積，可以先將它們通過傅里葉變換變換到頻域中，將兩個函數在頻域中相乘，然后再通過傅里葉逆變換轉換出來，就可以得到? 與? 的卷積結果。下面的動圖形象地展示了傅里葉變換的過程，這里我們把函數? 傅里葉變換后的結果寫作?.

傅里葉變換的示例

那傅里葉變換能干啥呢，有一個簡單的應用是給圖像去除一些規律噪點。比如說下面這個例子，原圖來自知乎 [13]。

在傅里葉變換前，圖像上有一些規律的條紋，直接在原圖上去掉條紋有點困難，但我們可以將圖片通過傅里葉變換變到頻譜圖中，頻譜圖中那些規律的點就是原圖中的背景條紋。

傅里葉變換的示例

只要在頻譜圖中擦除這些點，就可以將背景條紋去掉，得到下圖右側的結果。

傅里葉變換的示例

除了可以用來分離噪聲點與正常點，傅里葉變換還憑借上面的恒等式，在加速卷積運算方面有很大的潛力，**快速傅里葉變換(Fast Fourier Transform)**也是由此而生。實際上呢，現在大家最常用的卷積神經網絡，完全可以搭配傅里葉變換。下面這張圖就表示了一個普通的卷積神經網絡如何與傅里葉變換搭配，其中的 IFFT 即 快速傅里葉變換的逆變換(Inverse Fast Fourier Transform：

傅里葉變換的示例

其實筆者在初識傅里葉變換時很好奇，既然FFT可以加速卷積神經網絡，為什么現在的卷積神經網絡不用呢? 在經過一些搜索與思考后，筆者將自己得到的結論拋磚引玉供讀者參考：我們現在的卷積神經網絡的核都很小，常見的都如1，3，5之類，卷積操作的時間開銷本來就不大。如果要搭配FFT，還需要做傅里葉變換與逆變換，時間開銷并不一定會減小。

說了這么半天，傅里葉變換的公式是什么樣呢？實際上，經過傅里葉變換后的結果就如下所示，其中?(虛數單位)，t是任意實數。

感興趣的同學可以深入研究一下傅里葉變換這一套，我們這里關心的實際上是?的物理意義，它是圖上類比構造傅里葉變換的關鍵。這個式子實際上是拉普拉斯算子的廣義特征函數。

拉普拉斯算子(Laplacian operator) 的物理意義是空間二階導，準確定義是：標量梯度場中的散度，一般可用于描述物理量的流入流出。比如說在二維空間中的溫度傳播規律，一般可以用拉普拉斯算子來描述。

為什么是特征函數呢，我們這里根據拉普拉斯算子的定義來稍微推導一下。眾所周知，特征向量需要滿足的定義式是：對于矩陣，其特征向量滿足的條件應是矩陣與特征向量做乘法的結果，與特征向量乘標量的結果一樣，即滿足如下等式。

稍微推導一下即可知道，拉普拉斯算子作用在確實滿足以上特征向量的定義:

這里是求導符號，是二階導。

實際上，再仔細觀察傅里葉變換的式子，它本質上是將函數映射到了以為基向量的空間中。

圖上的傅里葉變換

終于講到我們本節的重點內容了，上面我們絮絮叨叨地鋪墊了很多傅里葉變換的知識，主要是為了將傅里葉變換類比到圖上。那么問題來了:在圖上，我們去哪找拉普拉斯算子? 與?呢？

聰明的研究者們找到了圖的拉普拉斯矩陣(L)及其特征向量()，作為上述兩者的替代品。至此，形成了圖上傅里葉變換的生態系統。拉普拉斯矩陣，實際上是度矩陣(D)減去鄰接矩陣(A)?，如下圖所示，圖源自[14].

拉普拉斯矩陣

頻域卷積的前提條件是圖必須是無向圖，那么就是對稱矩陣。所以它可以按照如下公式分解:

那么，根據上面卷積與傅里葉結合的變換公式，圖上頻域卷積的公式便可以寫成?。如果在整個圖的個結點上一起做卷積，就可以得到整張圖上的卷積如下：

讓我們重新審視一下歐式空間上的卷積和圖上的卷積，即可明白圖上的卷積與傳統的卷積其實非常相似，這里? 都是特征函數， 都是卷積核：

如果把? 整體看作可學習的卷積核，這里我們把它寫作?。最終圖上的卷積公式即是：

接下來我們要介紹的圖上頻域卷積的工作，都是在的基礎上做文章。

頻域卷積網絡(Spectral CNN)

我們上面推導的這個? 就是首個提出的頻域卷積神經網絡的卷積核[15]。假設層的隱藏狀態為，類似地，第層為。頻域卷積層的狀態更新計算公式如下：

仔細觀察上式，可以發現一層卷積層參數有?個。這里的其實可以類比全連接神經網絡中的權重，為了方便讀者理解，筆者做了下面的示意圖：

示意圖

切比雪夫網絡(ChebNet)

基本的頻域卷積網絡要計算拉普拉斯矩陣所有的特征值和特征向量，計算量巨大。在論文[16]中提出了切比雪夫網絡，它應用**切比雪夫多項式(Chebyshev polynomials)**來加速特征矩陣的求解。假設切比雪夫多項式的第k項是?, 頻域卷積核的計算方式如下：

切比雪夫多項式是以遞歸方式定義的一系列正交多項式序列。

那么 怎么來呢，可以由切比雪夫多項式的定義得來:，遞推式的前兩項為以及。的作用是讓特征向量矩陣歸一化到之間。

參考文獻

[1]. Neural Message Passing for Quantum Chemistry, https://arxiv.org/abs/1704.01212

[2]. Inductive Representation Learning on Large Graphs, https://arxiv.org/abs/1706.02216

[3]. Diffusion-Convolutional Neural Networks, https://arxiv.org/abs/1511.02136

[4]. Learning Convolutional Neural Networks for Graphs, https://arxiv.org/pdf/1605.05273

[5]. Spectral Networks and Locally Connected Networks on Graphs, https://arxiv.org/abs/1312.6203

[6]. Convolutional neural networks on graphs with fast localized spectral filtering, https://papers.nips.cc/paper/6081-convolutional-neural-networks-on-graphs-with-fast-localized-spectral-filtering

[7]. Semi-Supervised Classification with Graph Convolutional Networks, https://arxiv.org/pdf/1609.02907

[8]. 如何通俗易懂地解釋卷積, https://www.zhihu.com/question/22298352

[9]. https://en.wikipedia.org/wiki/Convolution

[10]. https://mlnotebook.github.io/post/CNN1/

[11]. http://snap.stanford.edu/proj/embeddings-www

[12]. https://zhuanlan.zhihu.com/p/37840709

[13]. https://www.zhihu.com/question/20460630/answer/105888045

[14]. https://en.wikipedia.org/wiki/Laplacian_matrix

[15]. Spectral Networks and Locally Connected Networks on Graphs, https://arxiv.org/abs/1312.6203

[16]. Convolutional neural networks on graphs with fast localized spectral filtering, https://arxiv.org/abs/1606.09375

—THE END—

編輯?∑Gemini

來源：SivilTaram

文章推薦

?最全數學各個分支簡介

?十大中國數學之最

?數學和編程

?機器學習中需要了解的 5 種采樣方法

?北大讀博手記：怎樣完成自己的博士生涯？非常具有指導性！

?施一公：為什么要獨立思考、為什么要尊重科學？

總結

以上是生活随笔為你收集整理的从图(Graph)到图卷积(Graph Convolution)：漫谈图神经网络 (二)的全部內容，希望文章能夠幫你解決所遇到的問題。

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