鍵.png)
使用這些基本 REST API 最佳實(shí)踐構(gòu)建出色的 API
假設(shè)結(jié)點(diǎn)5為中心結(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ù)?g?來描述如何適應(yīng)下游任務(wù)。舉個(gè)例子，給定一個(gè)社交網(wǎng)絡(luò)，一個(gè)可能的下游任務(wù)是判斷各個(gè)結(jié)點(diǎn)是否為水軍賬號(hào)。
在原論文中，?g又被稱為局部輸出函數(shù)(local output function)，與?f?類似，g?也可以由一個(gè)神經(jīng)網(wǎng)絡(luò)來表達(dá)，它也是一個(gè)全局共享的函數(shù)。那么，整個(gè)流程可以用下面這張圖表達(dá)：
仔細(xì)觀察兩個(gè)時(shí)刻之間的連線，它與圖的連線密切相關(guān)。比如說在?T1?時(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相鄰。直到?Tn?時(shí)刻，各個(gè)結(jié)點(diǎn)隱藏狀態(tài)收斂，每個(gè)結(jié)點(diǎn)后面接一個(gè)?g?即可得到該結(jié)點(diǎn)的輸出o?。
下面讓我們舉個(gè)實(shí)例來說明圖神經(jīng)網(wǎng)絡(luò)是如何應(yīng)用在實(shí)際場(chǎng)景中的，這個(gè)例子來源于論文[2]。假設(shè)我們現(xiàn)在有這樣一個(gè)任務(wù)，給定一個(gè)環(huán)烴化合物的分子結(jié)構(gòu)(包括原子類型，原子鍵等)，模型學(xué)習(xí)的目標(biāo)是判斷其是否有害。這是一個(gè)典型的二分類問題，一個(gè)訓(xùn)練樣本如下圖所示：
由于化合物的分類實(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ò)作為輸出層(即g函數(shù))，就可以對(duì)整個(gè)化合物進(jìn)行二分類了。
當(dāng)然，在同構(gòu)圖上根據(jù)策略選擇同一個(gè)根結(jié)點(diǎn)對(duì)結(jié)果也非常重要。但在這里我們不關(guān)注這部分細(xì)節(jié)，感興趣的讀者可以閱讀原文。
不動(dòng)點(diǎn)理論 在本節(jié)的開頭我們就提到了，GNN的理論基礎(chǔ)是不動(dòng)點(diǎn)(the fixed point)理論，這里的不動(dòng)點(diǎn)理論專指巴拿赫不動(dòng)點(diǎn)定理(Banach’s Fixed Point Theorem)。首先我們用?F?表示若干個(gè)?f?堆疊得到的一個(gè)函數(shù)，也稱為全局更新函數(shù)，那么圖上所有結(jié)點(diǎn)的狀態(tài)更新公式可以寫成：
那么肯定會(huì)有讀者心存疑問，既然f?是由神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)的，我們?cè)撊绾螌?shí)現(xiàn)它才能保證它是一個(gè)壓縮映射呢？我們下面來談?wù)?f?的具體實(shí)現(xiàn)。
具體實(shí)現(xiàn) 在具體實(shí)現(xiàn)中，f??其實(shí)通過一個(gè)簡(jiǎn)單的前饋神經(jīng)網(wǎng)絡(luò)(Feed-forward Neural Network)即可實(shí)現(xiàn)。比如說，一種實(shí)現(xiàn)方法可以是把每個(gè)鄰居結(jié)點(diǎn)的特征、隱藏狀態(tài)、每條相連邊的特征以及結(jié)點(diǎn)本身的特征簡(jiǎn)單拼接在一起，在經(jīng)過前饋神經(jīng)網(wǎng)絡(luò)后做一次簡(jiǎn)單的加和。
推廣一下，即得到雅可比矩陣的罰項(xiàng)需要滿足其范數(shù)小于等于c等價(jià)于壓縮映射的條件。根據(jù)拉格朗日乘子法，將有約束問題變成帶罰項(xiàng)的無約束優(yōu)化問題，訓(xùn)練的目標(biāo)可表示成如下形式：
上面我們花一定的篇幅搞懂了如何讓?f?接近壓縮映射，下面我們來具體敘述一下圖神經(jīng)網(wǎng)絡(luò)中的損失?Loss?是如何定義，以及模型是如何學(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)一共有?p?個(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ì)上的不同：
不過鑒于初代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ù)測(cè)。收斂作為GNN的內(nèi)核，同樣局限了其更廣泛的使用，其中最突出的是兩個(gè)問題：
如果把GNN應(yīng)用在圖表示的場(chǎ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ǔ)。這意味著：?f不再需要是一個(gè)壓縮映射；迭代不需要到收斂才能輸出，可以迭代固定步長(zhǎng)；優(yōu)化算法也從 AP 算法轉(zhuǎn)向 BPTT。
狀態(tài)更新與圖神經(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ù)W。每一種edge?對(duì)應(yīng)一個(gè)Wedge?，這樣它就可以處理異構(gòu)圖。
但是，仔細(xì)對(duì)比GNN的GGNN的狀態(tài)更新公式，細(xì)心的讀者可能會(huì)發(fā)現(xiàn)：在GNN里需要作為輸入的結(jié)點(diǎn)特征?Xv?沒有出現(xiàn)在GGNN的公式中! 但實(shí)際上，這些結(jié)點(diǎn)特征對(duì)我們的預(yù)測(cè)至關(guān)重要，因?yàn)樗攀歉鱾€(gè)結(jié)點(diǎn)的根本所在。
為了處理這個(gè)問題，GGNN將結(jié)點(diǎn)特征作為隱藏狀態(tài)初始化的一部分。那么重新回顧一下GGNN的流程，其實(shí)就是這樣：
實(shí)例1:到達(dá)判斷?為了便于理解，我們舉個(gè)來自論文[10]的例子。比如說給定一張圖G，開始結(jié)點(diǎn)?S，對(duì)于任意一個(gè)結(jié)點(diǎn)?E，模型判斷開始結(jié)點(diǎn)是否可以通過圖游走至該結(jié)點(diǎn)。同樣地，這也可以轉(zhuǎn)換成一個(gè)對(duì)結(jié)點(diǎn)的二分類問題，即可以到達(dá)和不能到達(dá)。下圖即描述了這樣的過程：
圖中的紅色結(jié)點(diǎn)即開始結(jié)點(diǎn)S，綠色結(jié)點(diǎn)是我們希望判斷的結(jié)點(diǎn)E，我們這里稱其為結(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é)果影響很大。
實(shí)例2:語義解析上面這個(gè)例子非常簡(jiǎn)單形象地說明了GNN與GGNN的不同，由于筆者比較關(guān)注Semantic Parsing(語義解析)相關(guān)的工作，所以下面我們借用ACL 2019的一篇論文[11]來講一下GGNN在實(shí)際中如何使用，以及它適用于怎樣的場(chǎng)景。
首先為不了解語義解析的讀者科普一下，語義解析的主要任務(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è)問題在多表的場(chǎng)景中尤為突出，每張表格互相之間通過外鍵相互關(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]中，是通過三步來完成的：
首先，通過表格建立對(duì)應(yīng)的Graph。再利用GGNN的方法計(jì)算每個(gè)Header的隱藏狀態(tài)。然后，在Seq2seq模型的編碼階段(Encoding)，用每個(gè)輸入的自然語言單詞的詞向量對(duì)表格所有Header的隱藏狀態(tài)算一個(gè)Attention，利用Attention作為權(quán)重得到了每個(gè)自然語言單詞的圖感知的表示。在解碼階段(Decoding)，如果輸出的是表格中的Header/Table這類詞，就用輸出的向量與表格所有Header/Table的隱藏狀態(tài)算一個(gè)分?jǐn)?shù)，這個(gè)分?jǐn)?shù)由F提供的。F實(shí)際上是一個(gè)全連接層，它的輸出實(shí)際上是SQL單詞與表格中各個(gè)Header/Table的聯(lián)系程度。為了讓SQL的每個(gè)輸出都與歷史的信息一致，每次輸出時(shí)都用之前輸出的Header/Table對(duì)候選集中的Header/Table打分，這樣就利用到了多表的信息。最終該論文在多表上的效果也確實(shí)很好，下面放一個(gè)在Spider[12]數(shù)據(jù)集上的性能對(duì)比：
GNN與GGNNGGNN目前得到了廣泛的應(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ì)類似。
[1]. A Comprehensive Survey on Graph Neural Networks, https://arxiv.org/abs/1901.00596
[2]. The graph neural network model, https://persagen.com/files/misc/scarselli2009graph.pdf
[3]. Spectral networks and locally connected networks on graphs, https://arxiv.org/abs/1312.6203
[4]. Distributed Representations of Words and Phrases and their Compositionality, http://papers.nips.cc/paper/5021-distributed-representations-of-words-andphrases
[5]. DeepWalk: Online Learning of Social Representations, https://arxiv.org/abs/1403.6652
[6]. Translating Embeddings for Modeling Multi-relational Data, https://papers.nips.cc/paper/5071-translating-embeddings-for-modeling-multi-relational-data
[7]. Deep Learning on Graphs: A Survey, https://arxiv.org/abs/1812.04202
[8]. 如何理解Graph Convolutional Network（GCN）? https://www.zhihu.com/question/54504471
[9]. Almeida–Pineda recurrent backpropagation, https://www.wikiwand.com/en/Almeida%E2%80%93Pineda_recurrent_backpropagation
[10]. Gated graph sequence neural networks, https://arxiv.org/abs/1511.05493
[11]. Representing Schema Structure with Graph Neural Networks for Text-to-SQL Parsing, https://arxiv.org/abs/1905.06241
[12]. Spider1.0 Yale Semantic Parsing and Text-to-SQL Challenge, https://yale-lily.github.io/spider
[13]. https://www.wikiwand.com/en/Laplacian_matrix
文章轉(zhuǎn)自微信公眾號(hào)@算法進(jìn)階
對(duì)比大模型API的內(nèi)容創(chuàng)意新穎性、情感共鳴力、商業(yè)轉(zhuǎn)化潛力
一鍵對(duì)比試用API 限時(shí)免費(fèi)