重磅干貨，第一時(shí)間送達(dá)

因此，本文試圖沿著圖神經(jīng)網(wǎng)絡(luò)的歷史脈絡(luò)，從最早基于不動(dòng)點(diǎn)理論的圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Network， GNN)一步步講到當(dāng)前用得最火的圖卷積神經(jīng)網(wǎng)絡(luò)(Graph Convolutional Neural Network， GCN)， 期望通過本文帶給讀者一些靈感與啟示。

• 本文的提綱與敘述要點(diǎn)主要參考了2篇圖神經(jīng)網(wǎng)絡(luò)的Survey，分別是來自IEEE Fellow的A Comprehensive Survey on Graph Neural Networks[1] 以及來自清華大學(xué)朱文武老師組的Deep Learning on Graphs: A Survey[7]， 在這里向兩篇Survey的作者表示敬意。
• 同時(shí)，本文關(guān)于部分圖卷積神經(jīng)網(wǎng)絡(luò)的理解很多都是受到知乎問題[8]高贊答案的啟發(fā)，非常感謝他們的無私分享！
• 最后，本文還引用了一些來自互聯(lián)網(wǎng)的生動(dòng)形象的圖片，在這里也向這些圖片的作者表示感謝。本文中未注明出處的圖片均為筆者制作，如需轉(zhuǎn)載或引用請(qǐng)聯(lián)系本人。

在開始正文之前，筆者先帶大家回顧一下圖神經(jīng)網(wǎng)絡(luò)的發(fā)展歷史。不過，因?yàn)閳D神經(jīng)網(wǎng)絡(luò)的發(fā)展分支非常之多，筆者某些敘述可能并不全面，一家之言僅供各位讀者參考：

1. 圖神經(jīng)網(wǎng)絡(luò)的概念最早在2005年提出。2009年Franco博士在其論文 [2]中定義了圖神經(jīng)網(wǎng)絡(luò)的理論基礎(chǔ)，筆者呆會(huì)要講的第一種圖神經(jīng)網(wǎng)絡(luò)也是基于這篇論文。
2. 最早的GNN主要解決的還是如分子結(jié)構(gòu)分類等嚴(yán)格意義上的圖論問題。但實(shí)際上歐式空間(比如像圖像 Image)或者是序列(比如像文本 Text)，許多常見場景也都可以轉(zhuǎn)換成圖(Graph)，然后就能使用圖神經(jīng)網(wǎng)絡(luò)技術(shù)來建模。
3. 2009年后圖神經(jīng)網(wǎng)絡(luò)也陸續(xù)有一些相關(guān)研究，但沒有太大波瀾。直到2013年，在圖信號(hào)處理(Graph Signal Processing)的基礎(chǔ)上，Bruna(這位是LeCun的學(xué)生)在文獻(xiàn) [3]中首次提出圖上的基于頻域(Spectral-domain)和基于空域(Spatial-domain)的卷積神經(jīng)網(wǎng)絡(luò)。
4. 其后至今，學(xué)界提出了很多基于空域的圖卷積方式，也有不少學(xué)者試圖通過統(tǒng)一的框架將前人的工作統(tǒng)一起來。而基于頻域的工作相對(duì)較少，只受到部分學(xué)者的青睞。
5. 值得一提的是，圖神經(jīng)網(wǎng)絡(luò)與圖表示學(xué)習(xí)(Represent Learning for Graph)的發(fā)展歷程也驚人地相似。2014年，在word2vec [4]的啟發(fā)下，Perozzi等人提出了DeepWalk [5]，開啟了深度學(xué)習(xí)時(shí)代圖表示學(xué)習(xí)的大門。更有趣的是，就在幾乎一樣的時(shí)間，Bordes等人提出了大名鼎鼎的TransE [6]，為知識(shí)圖譜的分布式表示(Represent Learning for Knowledge Graph)奠定了基礎(chǔ)。

首先要澄清一點(diǎn)，除非特別指明，本文中所提到的圖均指圖論中的圖(Graph)。它是一種由若干個(gè)結(jié)點(diǎn)(Node)及連接兩個(gè)結(jié)點(diǎn)的邊(Edge)所構(gòu)成的圖形，用于刻畫不同結(jié)點(diǎn)之間的關(guān)系。下面是一個(gè)生動(dòng)的例子，圖片來自論文[7]:

最早的圖神經(jīng)網(wǎng)絡(luò)起源于Franco博士的論文[2], 它的理論基礎(chǔ)是不動(dòng)點(diǎn)理論。給定一張圖?，每個(gè)結(jié)點(diǎn)都有其自己的特征(feature), 本文中用表示結(jié)點(diǎn)v的特征；連接兩個(gè)結(jié)點(diǎn)的邊也有自己的特征，本文中用表示結(jié)點(diǎn)v與結(jié)點(diǎn)u之間邊的特征；GNN的學(xué)習(xí)目標(biāo)是獲得每個(gè)結(jié)點(diǎn)的圖感知的隱藏狀態(tài)?(state embedding)，這就意味著：對(duì)于每個(gè)節(jié)點(diǎn)，它的隱藏狀態(tài)包含了來自鄰居節(jié)點(diǎn)的信息。那么，如何讓每個(gè)結(jié)點(diǎn)都感知到圖上其他的結(jié)點(diǎn)呢？GNN通過迭代式更新所有結(jié)點(diǎn)的隱藏狀態(tài)來實(shí)現(xiàn)，在時(shí)刻，結(jié)點(diǎn)的隱藏狀態(tài)按照如下方式更新：

上面這個(gè)公式中的? 就是隱藏狀態(tài)的狀態(tài)更新函數(shù)，在論文中也被稱為局部轉(zhuǎn)移函數(shù)(local transaction function)。公式中的指的是與結(jié)點(diǎn)相鄰的邊的特征，指的是結(jié)點(diǎn)的鄰居結(jié)點(diǎn)的特征，則指鄰居結(jié)點(diǎn)在時(shí)刻的隱藏狀態(tài)。注意? 是對(duì)所有結(jié)點(diǎn)都成立的，是一個(gè)全局共享的函數(shù)。那么怎么把它跟深度學(xué)習(xí)結(jié)合在一起呢？聰明的讀者應(yīng)該想到了，那就是利用神經(jīng)網(wǎng)絡(luò)(Neural Network)來擬合這個(gè)復(fù)雜函數(shù)?。值得一提的是，雖然看起來? 的輸入是不定長參數(shù)，但在? 內(nèi)部我們可以先將不定長的參數(shù)通過一定操作變成一個(gè)固定的參數(shù)，比如說用所有隱藏狀態(tài)的加和來代表所有隱藏狀態(tài)。我們舉個(gè)例子來說明一下：

假設(shè)結(jié)點(diǎn)為中心結(jié)點(diǎn)，其隱藏狀態(tài)的更新函數(shù)如圖所示。這個(gè)更新公式表達(dá)的思想自然又貼切：不斷地利用當(dāng)前時(shí)刻鄰居結(jié)點(diǎn)的隱藏狀態(tài)作為部分輸入來生成下一時(shí)刻中心結(jié)點(diǎn)的隱藏狀態(tài)，直到每個(gè)結(jié)點(diǎn)的隱藏狀態(tài)變化幅度很小，整個(gè)圖的信息流動(dòng)趨于平穩(wěn)。至此，每個(gè)結(jié)點(diǎn)都“知曉”了其鄰居的信息。狀態(tài)更新公式僅描述了如何獲取每個(gè)結(jié)點(diǎn)的隱藏狀態(tài)，除它以外，我們還需要另外一個(gè)函數(shù)? 來描述如何適應(yīng)下游任務(wù)。舉個(gè)例子，給定一個(gè)社交網(wǎng)絡(luò)，一個(gè)可能的下游任務(wù)是判斷各個(gè)結(jié)點(diǎn)是否為水軍賬號(hào)。

在原論文中， 又被稱為局部輸出函數(shù)(local output function)，與? 類似， 也可以由一個(gè)神經(jīng)網(wǎng)絡(luò)來表達(dá)，它也是一個(gè)全局共享的函數(shù)。那么，整個(gè)流程可以用下面這張圖表達(dá)：

仔細(xì)觀察兩個(gè)時(shí)刻之間的連線，它與圖的連線密切相關(guān)。比如說在? 時(shí)刻，結(jié)點(diǎn) 1 的狀態(tài)接受來自結(jié)點(diǎn) 3 的上一時(shí)刻的隱藏狀態(tài)，因?yàn)榻Y(jié)點(diǎn) 1 與結(jié)點(diǎn) 3相鄰。直到? 時(shí)刻，各個(gè)結(jié)點(diǎn)隱藏狀態(tài)收斂，每個(gè)結(jié)點(diǎn)后面接一個(gè)? 即可得到該結(jié)點(diǎn)的輸出?。

對(duì)于不同的圖來說，收斂的時(shí)刻可能不同，因?yàn)槭諗渴峭ㄟ^兩個(gè)時(shí)刻-范數(shù)的差值是否小于某個(gè)閾值?來判定的，比如：

下面讓我們舉個(gè)實(shí)例來說明圖神經(jīng)網(wǎng)絡(luò)是如何應(yīng)用在實(shí)際場景中的，這個(gè)例子來源于論文[2]。假設(shè)我們現(xiàn)在有這樣一個(gè)任務(wù)，給定一個(gè)環(huán)烴化合物的分子結(jié)構(gòu)(包括原子類型，原子鍵等)，模型學(xué)習(xí)的目標(biāo)是判斷其是否有害。這是一個(gè)典型的二分類問題，一個(gè)練樣本如下圖所示：

由于化合物的分類實(shí)際上需要對(duì)整個(gè)圖進(jìn)行分類，在論文中，作者將化合物的根結(jié)點(diǎn)的表示作為整個(gè)圖的表示，如圖上紅色的結(jié)點(diǎn)所示。Atom feature 中包括了每個(gè)原子的類型(Oxygen, 氧原子)、原子自身的屬性(Atom Properties)、化合物的一些特征(Global Properties)等。把每個(gè)原子看作圖中的結(jié)點(diǎn)，原子鍵視作邊，一個(gè)分子(Molecule)就可以看作一張圖。在不斷迭代得到根結(jié)點(diǎn)氧原子收斂的隱藏狀態(tài)后，在上面接一個(gè)前饋神經(jīng)網(wǎng)絡(luò)作為輸出層(即函數(shù))，就可以對(duì)整個(gè)化合物進(jìn)行二分類了。

當(dāng)然，在同構(gòu)圖上根據(jù)策略選擇同一個(gè)根結(jié)點(diǎn)對(duì)結(jié)果也非常重要。但在這里我們不關(guān)注這部分細(xì)節(jié)，感興趣的讀者可以閱讀原文。

在本節(jié)的開頭我們就提到了，GNN的理論基礎(chǔ)是不動(dòng)點(diǎn)(the fixed point)理論，這里的不動(dòng)點(diǎn)理論專指巴拿赫不動(dòng)點(diǎn)定理(Banach's Fixed Point Theorem)。首先我們用? 表示若干個(gè)? 堆疊得到的一個(gè)函數(shù)，也稱為全局更新函數(shù)，那么圖上所有結(jié)點(diǎn)的狀態(tài)更新公式可以寫成：

不動(dòng)點(diǎn)定理指的就是，不論是什么，只要? 是個(gè)壓縮映射(contraction map)，經(jīng)過不斷迭代都會(huì)收斂到某一個(gè)固定的點(diǎn)，我們稱之為不動(dòng)點(diǎn)。那壓縮映射又是什么呢，一張圖可以解釋得明明白白：

上圖的實(shí)線箭頭就是指映射?, 任意兩個(gè)點(diǎn)? 在經(jīng)過? 這個(gè)映射后，分別變成了?。壓縮映射就是指，。也就是說，經(jīng)過? 變換后的新空間一定比原先的空間要小，原先的空間被壓縮了。想象這種壓縮的過程不斷進(jìn)行，最終就會(huì)把原空間中的所有點(diǎn)映射到一個(gè)點(diǎn)上。

那么肯定會(huì)有讀者心存疑問，既然? 是由神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)的，我們?cè)撊绾螌?shí)現(xiàn)它才能保證它是一個(gè)壓縮映射呢？我們下面來談?wù)? 的具體實(shí)現(xiàn)。

在具體實(shí)現(xiàn)中，? 其實(shí)通過一個(gè)簡單的前饋神經(jīng)網(wǎng)絡(luò)(Feed-forward Neural Network)即可實(shí)現(xiàn)。比如說，一種實(shí)現(xiàn)方法可以是把每個(gè)鄰居結(jié)點(diǎn)的特征、隱藏狀態(tài)、每條相連邊的特征以及結(jié)點(diǎn)本身的特征簡單拼接在一起，在經(jīng)過前饋神經(jīng)網(wǎng)絡(luò)后做一次簡單的加和。

那我們?nèi)绾伪ＷC? 是個(gè)壓縮映射呢，其實(shí)是通過限制? 對(duì)? 的偏導(dǎo)數(shù)矩陣的大小，這是通過一個(gè)對(duì)雅可比矩陣(Jacobian Matrix)的懲罰項(xiàng)(Penalty)來實(shí)現(xiàn)的。在代數(shù)中，有一個(gè)定理是:? 為壓縮映射的等價(jià)條件是? 的梯度/導(dǎo)數(shù)要小于1。這個(gè)等價(jià)定理可以從壓縮映射的形式化定義導(dǎo)出，我們這里使用? 表示? 在空間中的范數(shù)(norm)。范數(shù)是一個(gè)標(biāo)量，它是向量的長度或者模， 是? 在有限空間中坐標(biāo)的連續(xù)函數(shù)。這里把? 簡化成1維的，坐標(biāo)之間的差值可以看作向量在空間中的距離，根據(jù)壓縮映射的定義，可以導(dǎo)出：

推廣一下，即得到雅可比矩陣的罰項(xiàng)需要滿足其范數(shù)小于等于等價(jià)于壓縮映射的條件。根據(jù)拉格朗日乘子法，將有約束問題變成帶罰項(xiàng)的無約束優(yōu)化問題，訓(xùn)練的目標(biāo)可表示成如下形式：

其中是超參數(shù)，與其相乘的項(xiàng)即為雅可比矩陣的罰項(xiàng)。

上面我們花一定的篇幅搞懂了如何讓? 接近壓縮映射，下面我們來具體敘述一下圖神經(jīng)網(wǎng)絡(luò)中的損失? 是如何定義，以及模型是如何學(xué)習(xí)的。

仍然以社交網(wǎng)絡(luò)舉例，雖然每個(gè)結(jié)點(diǎn)都會(huì)有隱藏狀態(tài)以及輸出，但并不是每個(gè)結(jié)點(diǎn)都會(huì)有監(jiān)督信號(hào)(Supervision)。比如說，社交網(wǎng)絡(luò)中只有部分用戶被明確標(biāo)記了是否為水軍賬號(hào)，這就構(gòu)成了一個(gè)典型的結(jié)點(diǎn)二分類問題。

那么很自然地，模型的損失即通過這些有監(jiān)督信號(hào)的結(jié)點(diǎn)得到。假設(shè)監(jiān)督結(jié)點(diǎn)一共有? 個(gè)，模型損失可以形式化為：

那么，模型如何學(xué)習(xí)呢？根據(jù)前向傳播計(jì)算損失的過程，不難推出反向傳播計(jì)算梯度的過程。在前向傳播中，模型：

1. 調(diào)用? 若干次，比如?次，直到? 收斂。

2. 此時(shí)每個(gè)結(jié)點(diǎn)的隱藏狀態(tài)接近不動(dòng)點(diǎn)的解。

3. 對(duì)于有監(jiān)督信號(hào)的結(jié)點(diǎn)，將其隱藏狀態(tài)通過? 得到輸出，進(jìn)而算出模型的損失。

   根據(jù)上面的過程，在反向傳播時(shí)，我們可以直接求出? 和? 對(duì)最終的隱藏狀態(tài) ? 的梯度。然而，因?yàn)槟Ｐ瓦f歸調(diào)用了? 若干次，為計(jì)算? 和? 對(duì)最初的隱藏狀態(tài)? 的梯度，我們需要同樣遞歸式/迭代式地計(jì)算? 次梯度。最終得到的梯度即為? 和? 對(duì)? 的梯度，然后該梯度用于更新模型的參數(shù)。這個(gè)算法就是 Almeida-Pineda 算法[9]。之所以要求? 為壓縮映射，也是因?yàn)橹挥? 為壓縮映射時(shí)，AP 才能得到一個(gè)收斂的梯度。

相信熟悉 RNN/LSTM/GRU 等循環(huán)神經(jīng)網(wǎng)絡(luò)的同學(xué)看到這里會(huì)有一點(diǎn)小困惑，因?yàn)閳D神經(jīng)網(wǎng)絡(luò)不論是前向傳播的方式，還是反向傳播的優(yōu)化算法，與循環(huán)神經(jīng)網(wǎng)絡(luò)都有點(diǎn)相像。這并不是你的錯(cuò)覺，實(shí)際上，圖神經(jīng)網(wǎng)絡(luò)與到循環(huán)神經(jīng)網(wǎng)絡(luò)確實(shí)很相似。為了清楚地顯示出它們之間的不同，我們用一張圖片來解釋這兩者設(shè)計(jì)上的不同：

假設(shè)在GNN中存在三個(gè)結(jié)點(diǎn),,，相應(yīng)地，在RNN中有一個(gè)序列。筆者認(rèn)為，GNN與RNN的區(qū)別主要在于4點(diǎn)：

• GNN的基礎(chǔ)理論是不動(dòng)點(diǎn)理論，這就意味著GNN沿時(shí)間展開的長度是動(dòng)態(tài)的，是根據(jù)收斂條件確定的，而RNN沿時(shí)間展開的長度就等于序列本身的長度。
• GNN每次時(shí)間步的輸入都是所有結(jié)點(diǎn)? 的特征，而RNN每次時(shí)間步的輸入是該時(shí)刻對(duì)應(yīng)的輸入。同時(shí)，時(shí)間步之間的信息流也不相同，前者由邊決定，后者則由序列的讀入順序決定。
• GNN采用 AP 算法反向傳播優(yōu)化，而RNN使用BPTT(Back Propogation Through Time)優(yōu)化。前者對(duì)收斂性有要求，而后者對(duì)收斂性是沒有要求的。
• GNN循環(huán)調(diào)用? 的目標(biāo)是得到每個(gè)結(jié)點(diǎn)穩(wěn)定的隱藏狀態(tài)，所以只有在隱藏狀態(tài)收斂后才能輸出；而RNN的每個(gè)時(shí)間步上都可以輸出，比如語言模型。

不過鑒于初代GNN與RNN結(jié)構(gòu)上的相似性，一些文章中也喜歡把它稱之為 Recurrent-based GNN，也有一些文章會(huì)把它歸納到 Recurrent-based GCN中。之后讀者在了解 GCN后會(huì)理解為什么人們要如此命名。

初代GNN，也就是基于循環(huán)結(jié)構(gòu)的圖神經(jīng)網(wǎng)絡(luò)的核心是不動(dòng)點(diǎn)理論。它的核心觀點(diǎn)是通過結(jié)點(diǎn)信息的傳播使整張圖達(dá)到收斂，在其基礎(chǔ)上再進(jìn)行預(yù)測。收斂作為GNN的內(nèi)核，同樣局限了其更廣泛的使用，其中最突出的是兩個(gè)問題：

• GNN只將邊作為一種傳播手段，但并未區(qū)分不同邊的功能。雖然我們可以在特征構(gòu)造階段()為不同類型的邊賦予不同的特征，但相比于其他輸入，邊對(duì)結(jié)點(diǎn)隱藏狀態(tài)的影響實(shí)在有限。并且GNN沒有為邊設(shè)置獨(dú)立的可學(xué)習(xí)參數(shù)，也就意味著無法通過模型學(xué)習(xí)到邊的某些特性。
• 如果把GNN應(yīng)用在圖表示的場景中，使用不動(dòng)點(diǎn)理論并不合適。這主要是因?yàn)榛诓粍?dòng)點(diǎn)的收斂會(huì)導(dǎo)致結(jié)點(diǎn)之間的隱藏狀態(tài)間存在較多信息共享，從而導(dǎo)致結(jié)點(diǎn)的狀態(tài)太過光滑(Over Smooth)，并且屬于結(jié)點(diǎn)自身的特征信息匱乏(Less Informative)。

下面這張來自維基百科[13]的圖可以形象地解釋什么是 Over Smooth，其中我們把整個(gè)布局視作一張圖，每個(gè)像素點(diǎn)與其上下左右以及斜上下左右8個(gè)像素點(diǎn)相鄰，這決定了信息在圖上的流動(dòng)路徑。初始時(shí)，藍(lán)色表示沒有信息量，如果用向量的概念表達(dá)即為空向量；綠色，黃色與紅色各自有一部分信息量，表達(dá)為非空的特征向量。在圖上，信息主要從三塊有明顯特征的區(qū)域向其鄰接的像素點(diǎn)流動(dòng)。一開始不同像素點(diǎn)的區(qū)分非常明顯，但在向不動(dòng)點(diǎn)過渡的過程中，所有像素點(diǎn)都取向一致，最終整個(gè)系統(tǒng)形成均勻分布。這樣，雖然每個(gè)像素點(diǎn)都感知到了全局的信息，但我們無法根據(jù)它們最終的隱藏狀態(tài)區(qū)分它們。比如說，根據(jù)最終的狀態(tài)，我們是無法得知哪些像素點(diǎn)最開始時(shí)在綠色區(qū)域。

在這里筆者再多說幾句。事實(shí)上，上面這個(gè)圖與GNN中的信息流動(dòng)并不完全等價(jià)。從筆者來看，如果我們用物理模型來描述它，上面這個(gè)圖代表的是初始時(shí)有3個(gè)熱源在散發(fā)熱量，而后就讓它們自由演化；但實(shí)際上，GNN在每個(gè)時(shí)間步都會(huì)將結(jié)點(diǎn)的特征作為輸入來更新隱藏狀態(tài)，這就好像是放置了若干個(gè)永遠(yuǎn)不滅的熱源，熱源之間會(huì)有互相干擾，但最終不會(huì)完全一致。

我們上面細(xì)致比較了GNN與RNN，可以發(fā)現(xiàn)它們有諸多相通之處。那么，我們能不能直接用類似RNN的方法來定義GNN呢? 于是乎，門控圖神經(jīng)網(wǎng)絡(luò)(Gated Graph Neural Network, GGNN) [10]就出現(xiàn)了。雖然在這里它們看起來類似，但實(shí)際上，它們的區(qū)別非常大，其中最核心的不同即是門控神經(jīng)網(wǎng)絡(luò)不以不動(dòng)點(diǎn)理論為基礎(chǔ)。這意味著： 不再需要是一個(gè)壓縮映射；迭代不需要到收斂才能輸出，可以迭代固定步長；優(yōu)化算法也從 AP 算法轉(zhuǎn)向 BPTT.

與圖神經(jīng)網(wǎng)絡(luò)定義的范式一致，GGNN也有兩個(gè)過程：狀態(tài)更新與輸出。相比GNN而言，它主要的區(qū)別來源于狀態(tài)更新階段。具體地，GGNN參考了GRU的設(shè)計(jì)，把鄰居結(jié)點(diǎn)的信息視作輸入，結(jié)點(diǎn)本身的狀態(tài)視作隱藏狀態(tài)，其狀態(tài)更新函數(shù)如下:

如果讀者對(duì)GRU的更新公式熟悉的話，對(duì)上式應(yīng)該很好理解。仔細(xì)觀察上面這個(gè)公式，除了GRU式的設(shè)計(jì)外，GGNN還針對(duì)不同類型的邊引入了可學(xué)習(xí)的參數(shù)。每一種? 對(duì)應(yīng)一個(gè)?，這樣它就可以處理異構(gòu)圖。

但是，仔細(xì)對(duì)比GNN的GGNN的狀態(tài)更新公式，細(xì)心的讀者可能會(huì)發(fā)現(xiàn)：在GNN里需要作為輸入的結(jié)點(diǎn)特征? 沒有出現(xiàn)在GGNN的公式中! 但實(shí)際上，這些結(jié)點(diǎn)特征對(duì)我們的預(yù)測至關(guān)重要，因?yàn)樗攀歉鱾€(gè)結(jié)點(diǎn)的根本所在。

為了處理這個(gè)問題，GGNN將結(jié)點(diǎn)特征作為隱藏狀態(tài)初始化的一部分。那么重新回顧一下GGNN的流程，其實(shí)就是這樣：

• 用結(jié)點(diǎn)特征初始化各個(gè)結(jié)點(diǎn)的(部分)隱藏狀態(tài)。
• 對(duì)整張圖，按照上述狀態(tài)更新公式固定迭代若干步。
• 對(duì)部分有監(jiān)督信號(hào)的結(jié)點(diǎn)求得模型損失，利用BPTT算法反向傳播求得和GRU參數(shù)的梯度。

為了便于理解，我們舉個(gè)來自論文[10]的例子。比如說給定一張圖，開始結(jié)點(diǎn)?，對(duì)于任意一個(gè)結(jié)點(diǎn)?，模型判斷開始結(jié)點(diǎn)是否可以通過圖游走至該結(jié)點(diǎn)。同樣地，這也可以轉(zhuǎn)換成一個(gè)對(duì)結(jié)點(diǎn)的二分類問題，即可以到達(dá)和不能到達(dá)。下圖即描述了這樣的過程：

圖中的紅色結(jié)點(diǎn)即開始結(jié)點(diǎn)，綠色結(jié)點(diǎn)是我們希望判斷的結(jié)點(diǎn)，我們這里稱其為結(jié)束結(jié)點(diǎn)。那么相比于其他結(jié)點(diǎn)，這兩個(gè)結(jié)點(diǎn)具有一定特殊性。那我們就可以使用第1維為1來表示開始結(jié)點(diǎn)，第2維為1來表示結(jié)束結(jié)點(diǎn)。最后在對(duì)結(jié)束結(jié)點(diǎn)分類時(shí)，如果其隱藏狀態(tài)的第1維被賦予得到了一個(gè)非0的實(shí)數(shù)值，那意味著它可以到達(dá)。

從初始化的流程我們也可以看出GNN與GGNN的區(qū)別：GNN依賴于不動(dòng)點(diǎn)理論，所以每個(gè)結(jié)點(diǎn)的隱藏狀態(tài)即使使用隨機(jī)初始化都會(huì)收斂到不動(dòng)點(diǎn)；GGNN則不同，不同的初始化對(duì)GGNN最終的結(jié)果影響很大。

首先為不了解語義解析的讀者科普一下，語義解析的主要任務(wù)是將自然語言轉(zhuǎn)換成機(jī)器語言，在這里筆者特指的是SQL(結(jié)構(gòu)化查詢語言，Structured Query Language)，它就是大家所熟知的數(shù)據(jù)庫查詢語言。這個(gè)任務(wù)有什么用呢？它可以讓小白用戶也能從數(shù)據(jù)庫中獲得自己關(guān)心的數(shù)據(jù)。正是因?yàn)橛辛苏Z義解析，用戶不再需要學(xué)習(xí)SQL語言的語法，也不需要有編程基礎(chǔ)，可以直接通過自然語言來查詢數(shù)據(jù)庫。事實(shí)上，語義解析放到今天仍然是一個(gè)非常難的任務(wù)。除去自然語言與程序語言在語義表達(dá)上的差距外，很大一部分性能上的損失是因?yàn)槿蝿?wù)本身，或者叫SQL語言的語法太復(fù)雜。比如我們有兩張表格，一張是學(xué)生的學(xué)號(hào)與其性別，另一張表格記錄了每個(gè)學(xué)生選修的課程。那如果想知道有多少女生選修了某門課程，我們需要先將兩張表格聯(lián)合(JOIN)，再對(duì)結(jié)果進(jìn)行過濾(WHERE)，最后進(jìn)行聚合統(tǒng)計(jì)(COUNT)。這個(gè)問題在多表的場景中尤為突出，每張表格互相之間通過外鍵相互關(guān)聯(lián)。其實(shí)呢，如果我們把表格中的Header看作各個(gè)結(jié)點(diǎn)，表格內(nèi)的結(jié)點(diǎn)之間存在聯(lián)系，而外鍵可以視作一種特殊的邊，這樣就可以構(gòu)成一張圖，正如下圖中部所示：

論文[11]就是利用了表格這樣的特性，利用GGNN來解決多表問題。下面我們先介紹一下一般的語義解析方法，再介紹[11]是如何將圖跟語義解析系統(tǒng)聯(lián)系在一起的。就筆者知道的而言，目前絕大部分語義解析會(huì)遵循Seq2seq(序列到序列，Sequence to sequence)的框架，輸入是一個(gè)個(gè)自然語言單詞，輸出是一個(gè)個(gè)SQL單詞。但這樣的框架完全沒有考慮到表格對(duì)SQL輸出暗含的約束。比如說，在單個(gè)SELECT子句中，我們選擇的若干Header都要來自同一張表。再舉個(gè)例子，能夠JOIN的兩張表一定存在外鍵的聯(lián)系，就像我們剛剛舉的那個(gè)學(xué)生選課的例子一樣。

那么，GGNN該如何結(jié)合到傳統(tǒng)的語義解析方法中去呢？在論文[11]中，是通過三步來完成的：

1. 首先，通過表格建立對(duì)應(yīng)的Graph。再利用GGNN的方法計(jì)算每個(gè)Header的隱藏狀態(tài)。
2. 然后，在Seq2seq模型的編碼階段(Encoding)，用每個(gè)輸入的自然語言單詞的詞向量對(duì)表格所有Header的隱藏狀態(tài)算一個(gè)Attention，利用Attention作為權(quán)重得到了每個(gè)自然語言單詞的圖感知的表示。
3. 在解碼階段(Decoding)，如果輸出的是表格中的Header/Table這類詞，就用輸出的向量與表格所有Header/Table的隱藏狀態(tài)算一個(gè)分?jǐn)?shù)，這個(gè)分?jǐn)?shù)由提供的。實(shí)際上是一個(gè)全連接層，它的輸出實(shí)際上是SQL單詞與表格中各個(gè)Header/Table的聯(lián)系程度。為了讓SQL的每個(gè)輸出都與歷史的信息一致，每次輸出時(shí)都用之前輸出的Header/Table對(duì)候選集中的Header/Table打分，這樣就利用到了多表的信息。

最終該論文在多表上的效果也確實(shí)很好，下面放一個(gè)在Spider[12]數(shù)據(jù)集上的性能對(duì)比：

GGNN目前得到了廣泛的應(yīng)用，相比于GNN，其最大的區(qū)別在于不再以不動(dòng)點(diǎn)理論為基礎(chǔ)，雖然這意味著不再需要迭代收斂，但同時(shí)它也意味著GGNN的初始化很重要。從筆者閱讀過的文獻(xiàn)來看，GNN后的大部分工作都轉(zhuǎn)向了將GNN向傳統(tǒng)的RNN/CNN靠攏，可能的一大好處是這樣可以不斷吸收來自這兩個(gè)研究領(lǐng)域的改進(jìn)。但基于原始GNN的基于不動(dòng)點(diǎn)理論的工作非常少，至少在筆者看文獻(xiàn)綜述的時(shí)候并未發(fā)現(xiàn)很相關(guān)的工作。

但從另一個(gè)角度來看，雖然GNN與GGNN的理論不同，但從設(shè)計(jì)哲學(xué)上來看，它們都與循環(huán)神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)類似。

• 循環(huán)神經(jīng)網(wǎng)絡(luò)的好處在于能夠處理任意長的序列，但它的計(jì)算必須是串行計(jì)算若干個(gè)時(shí)間步，時(shí)間開銷不可忽略。所以，上面兩種基于循環(huán)的圖神經(jīng)網(wǎng)絡(luò)在更新隱藏狀態(tài)時(shí)不太高效。如果借鑒深度學(xué)習(xí)中堆疊多層的成功經(jīng)驗(yàn)，我們有足夠的理由相信，多層圖神經(jīng)網(wǎng)絡(luò)能達(dá)到同樣的效果。
• 基于循環(huán)的圖神經(jīng)網(wǎng)絡(luò)每次迭代時(shí)都共享同樣的參數(shù)，而多層神經(jīng)網(wǎng)絡(luò)每一層的參數(shù)不同，可以看成是一個(gè)層次化特征抽取(Hierarchical Feature Extraction)的方法。

在下一篇中，我們將介紹圖卷積神經(jīng)網(wǎng)絡(luò)。它擺脫了基于循環(huán)的方法，開始走向多層圖神經(jīng)網(wǎng)絡(luò)。在多層神經(jīng)網(wǎng)絡(luò)中，卷積神經(jīng)網(wǎng)絡(luò)(比如152層的ResNet)的大獲成功又驗(yàn)證了其在堆疊多層上訓(xùn)練的有效性，所以近幾年圖卷積神經(jīng)網(wǎng)絡(luò)成為研究熱點(diǎn)。

交流群

歡迎加入公眾號(hào)讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動(dòng)駕駛、計(jì)算攝影、檢測、分割、識(shí)別、醫(yī)學(xué)影像、GAN、算法競賽等微信群（以后會(huì)逐漸細(xì)分），請(qǐng)掃描下面微信號(hào)加群，備注：”昵稱+學(xué)校/公司+研究方向“，例如：”張三?+?上海交大?+?視覺SLAM“。請(qǐng)按照格式備注，否則不予通過。添加成功后會(huì)根據(jù)研究方向邀請(qǐng)進(jìn)入相關(guān)微信群。請(qǐng)勿在群內(nèi)發(fā)送廣告，否則會(huì)請(qǐng)出群，謝謝理解~