成人免费毛片网站,国产精品免费视频能看,在线免费视频一区二区

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

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

仔細觀察兩個時刻之間的連線，它與圖的連線密切相關。比如說在?T1?時刻，結點 1 的狀態接受來自結點 3 的上一時刻的隱藏狀態，因為結點 1 與結點 3相鄰。直到?Tn?時刻，各個結點隱藏狀態收斂，每個結點后面接一個?g?即可得到該結點的輸出o?。

實例:化合物分類

下面讓我們舉個實例來說明圖神經網絡是如何應用在實際場景中的，這個例子來源于論文[2]。假設我們現在有這樣一個任務，給定一個環烴化合物的分子結構(包括原子類型，原子鍵等)，模型學習的目標是判斷其是否有害。這是一個典型的二分類問題，一個訓練樣本如下圖所示：

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

當然，在同構圖上根據策略選擇同一個根結點對結果也非常重要。但在這里我們不關注這部分細節，感興趣的讀者可以閱讀原文。

不動點理論在本節的開頭我們就提到了，GNN的理論基礎是不動點(the fixed point)理論，這里的不動點理論專指巴拿赫不動點定理(Banach’s Fixed Point Theorem)。首先我們用?F?表示若干個?f?堆疊得到的一個函數，也稱為全局更新函數，那么圖上所有結點的狀態更新公式可以寫成：

那么肯定會有讀者心存疑問，既然f?是由神經網絡實現的，我們該如何實現它才能保證它是一個壓縮映射呢？我們下面來談談?f?的具體實現。

具體實現在具體實現中，f??其實通過一個簡單的前饋神經網絡(Feed-forward Neural Network)即可實現。比如說，一種實現方法可以是把每個鄰居結點的特征、隱藏狀態、每條相連邊的特征以及結點本身的特征簡單拼接在一起，在經過前饋神經網絡后做一次簡單的加和。

推廣一下，即得到雅可比矩陣的罰項需要滿足其范數小于等于c等價于壓縮映射的條件。根據拉格朗日乘子法，將有約束問題變成帶罰項的無約束優化問題，訓練的目標可表示成如下形式：

模型學習

上面我們花一定的篇幅搞懂了如何讓?f?接近壓縮映射，下面我們來具體敘述一下圖神經網絡中的損失?Loss?是如何定義，以及模型是如何學習的。

仍然以社交網絡舉例，雖然每個結點都會有隱藏狀態以及輸出，但并不是每個結點都會有監督信號(Supervision)。比如說，社交網絡中只有部分用戶被明確標記了是否為水軍賬號，這就構成了一個典型的結點二分類問題。

那么很自然地，模型的損失即通過這些有監督信號的結點得到。假設監督結點一共有?p?個，模型損失可以形式化為：

GNN與RNN

相信熟悉 RNN/LSTM/GRU 等循環神經網絡的同學看到這里會有一點小困惑，因為圖神經網絡不論是前向傳播的方式，還是反向傳播的優化算法，與循環神經網絡都有點相像。這并不是你的錯覺，實際上，圖神經網絡與到循環神經網絡確實很相似。為了清楚地顯示出它們之間的不同，我們用一張圖片來解釋這兩者設計上的不同：

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

GNN的局限

初代GNN，也就是基于循環結構的圖神經網絡的核心是不動點理論。它的核心觀點是通過結點信息的傳播使整張圖達到收斂，在其基礎上再進行預測。收斂作為GNN的內核，同樣局限了其更廣泛的使用，其中最突出的是兩個問題：

如果把GNN應用在圖表示的場景中，使用不動點理論并不合適。這主要是因為基于不動點的收斂會導致結點之間的隱藏狀態間存在較多信息共享，從而導致結點的狀態太過光滑(Over Smooth)，并且屬于結點自身的特征信息匱乏(Less Informative)。

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

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

門控圖神經網絡(Gated Graph Neural Network)

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

狀態更新與圖神經網絡定義的范式一致，GGNN也有兩個過程：狀態更新與輸出。相比GNN而言，它主要的區別來源于狀態更新階段。具體地，GGNN參考了GRU的設計，把鄰居結點的信息視作輸入，結點本身的狀態視作隱藏狀態，其狀態更新函數如下:

如果讀者對GRU的更新公式熟悉的話，對上式應該很好理解。仔細觀察上面這個公式，除了GRU式的設計外，GGNN還針對不同類型的邊引入了可學習的參數W。每一種edge?對應一個Wedge?，這樣它就可以處理異構圖。

但是，仔細對比GNN的GGNN的狀態更新公式，細心的讀者可能會發現：在GNN里需要作為輸入的結點特征?Xv?沒有出現在GGNN的公式中! 但實際上，這些結點特征對我們的預測至關重要，因為它才是各個結點的根本所在。

為了處理這個問題，GGNN將結點特征作為隱藏狀態初始化的一部分。那么重新回顧一下GGNN的流程，其實就是這樣：

實例1:到達判斷?為了便于理解，我們舉個來自論文[10]的例子。比如說給定一張圖G，開始結點?S，對于任意一個結點?E，模型判斷開始結點是否可以通過圖游走至該結點。同樣地，這也可以轉換成一個對結點的二分類問題，即可以到達和不能到達。下圖即描述了這樣的過程：

圖中的紅色結點即開始結點S，綠色結點是我們希望判斷的結點E，我們這里稱其為結束結點。那么相比于其他結點，這兩個結點具有一定特殊性。那我們就可以使用第1維為1來表示開始結點，第2維為1來表示結束結點。最后在對結束結點分類時，如果其隱藏狀態的第1維被賦予得到了一個非0的實數值，那意味著它可以到達。

從初始化的流程我們也可以看出GNN與GGNN的區別：GNN依賴于不動點理論，所以每個結點的隱藏狀態即使使用隨機初始化都會收斂到不動點；GGNN則不同，不同的初始化對GGNN最終的結果影響很大。

實例2:語義解析上面這個例子非常簡單形象地說明了GNN與GGNN的不同，由于筆者比較關注Semantic Parsing(語義解析)相關的工作，所以下面我們借用ACL 2019的一篇論文[11]來講一下GGNN在實際中如何使用，以及它適用于怎樣的場景。

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

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

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

首先，通過表格建立對應的Graph。再利用GGNN的方法計算每個Header的隱藏狀態。然后，在Seq2seq模型的編碼階段(Encoding)，用每個輸入的自然語言單詞的詞向量對表格所有Header的隱藏狀態算一個Attention，利用Attention作為權重得到了每個自然語言單詞的圖感知的表示。在解碼階段(Decoding)，如果輸出的是表格中的Header/Table這類詞，就用輸出的向量與表格所有Header/Table的隱藏狀態算一個分數，這個分數由F提供的。F實際上是一個全連接層，它的輸出實際上是SQL單詞與表格中各個Header/Table的聯系程度。為了讓SQL的每個輸出都與歷史的信息一致，每次輸出時都用之前輸出的Header/Table對候選集中的Header/Table打分，這樣就利用到了多表的信息。最終該論文在多表上的效果也確實很好，下面放一個在Spider[12]數據集上的性能對比：

GNN與GGNNGGNN目前得到了廣泛的應用，相比于GNN，其最大的區別在于不再以不動點理論為基礎，雖然這意味著不再需要迭代收斂，但同時它也意味著GGNN的初始化很重要。從筆者閱讀過的文獻來看，GNN后的大部分工作都轉向了將GNN向傳統的RNN/CNN靠攏，可能的一大好處是這樣可以不斷吸收來自這兩個研究領域的改進。但基于原始GNN的基于不動點理論的工作非常少，至少在筆者看文獻綜述的時候并未發現很相關的工作。

但從另一個角度來看，雖然GNN與GGNN的理論不同，但從設計哲學上來看，它們都與循環神經網絡的設計類似。

參考文獻

[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

[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

[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