論文閱讀（26）Gated graph sequence neural networks

1. 論文相關(guān)

Published as a conference paper at ICLR 2016

2. 摘要

圖結(jié)構(gòu)數(shù)據(jù)經(jīng)常出現(xiàn)在化學(xué)、自然語(yǔ)言語(yǔ)義盯串、社會(huì)網(wǎng)絡(luò)和知識(shí)庫(kù)等領(lǐng)域氯檐。在這項(xiàng)工作中，我們研究了圖形結(jié)構(gòu)輸入的特征學(xué)習(xí)技術(shù)嘴脾。我們的出發(fā)點(diǎn)是之前在圖神經(jīng)網(wǎng)絡(luò)方面的工作（Scarselli等人男摧，2009），我們將其修改為使用門(mén)控循環(huán)單元（gated recurrent units）和現(xiàn)代優(yōu)化技術(shù)（modern optimization techniques）译打，然后擴(kuò)展到輸出序列（output sequences）耗拓。其結(jié)果是一類(lèi)靈活且廣泛有用的神經(jīng)網(wǎng)絡(luò)模型，當(dāng)問(wèn)題是圖結(jié)構(gòu)時(shí)奏司，相對(duì)于純基于序列的模型（例如LSTM）乔询，具有良好歸納偏差（favorable inductive biases）的工作模型。我們展示了一些簡(jiǎn)單的人工智能（bAbI）和圖算法學(xué)習(xí)任務(wù)的能力韵洋。然后竿刁，我們證明它在程序驗(yàn)證的問(wèn)題上達(dá)到了最先進(jìn)的性能，其中子圖需要描述為抽象的數(shù)據(jù)結(jié)構(gòu)搪缨。

2.2 主要貢獻(xiàn)

我們的主要貢獻(xiàn)是對(duì)輸出序列的圖神經(jīng)網(wǎng)絡(luò)的擴(kuò)展食拜。以前對(duì)圖形結(jié)構(gòu)輸入的特征學(xué)習(xí)的研究主要集中在產(chǎn)生單一輸出的模型上，例如圖形級(jí)分類(lèi)副编，但是許多圖形輸入的問(wèn)題都需要輸出序列负甸。示例包括圖上的路徑、具有所需屬性的圖節(jié)點(diǎn)的枚舉痹届，或與開(kāi)始和結(jié)束節(jié)點(diǎn)混合的全局分類(lèi)序列呻待。我們不知道現(xiàn)有的圖特征學(xué)習(xí)工作是否適合這個(gè)問(wèn)題。我們的激勵(lì)應(yīng)用程序來(lái)自程序驗(yàn)證队腐，需要輸出邏輯公式蚕捉，我們將其作為一個(gè)順序輸出問(wèn)題來(lái)制定。第二個(gè)貢獻(xiàn)是強(qiáng)調(diào)了圖神經(jīng)網(wǎng)絡(luò)（以及我們?cè)谶@里開(kāi)發(fā)的進(jìn)一步擴(kuò)展）是一類(lèi)廣泛有用的神經(jīng)網(wǎng)絡(luò)模型柴淘，適用于當(dāng)前該領(lǐng)域面臨的許多問(wèn)題迫淹。

2.3 設(shè)置

圖上的特征學(xué)習(xí)有兩種設(shè)置：（1）學(xué)習(xí)輸入圖的表示秘通；（2）在生成輸出序列的過(guò)程中學(xué)習(xí)內(nèi)部狀態(tài)的表示。這里千绪，（1）主要是通過(guò)之前對(duì)圖神經(jīng)網(wǎng)絡(luò)的研究來(lái)實(shí)現(xiàn)的（Scarselli等人充易，2009年）；我們對(duì)這個(gè)框架做了一些小的調(diào)整荸型，包括改變它以使用循環(huán)神經(jīng)網(wǎng)絡(luò)相關(guān)的現(xiàn)代實(shí)踐（modern practices）盹靴。（2）這一點(diǎn)很重要，因?yàn)槲覀兿Ｍ麍D結(jié)構(gòu)問(wèn)題的輸出不僅僅是單個(gè)分類(lèi)瑞妇。在這些情況下稿静，挑戰(zhàn)在于如何學(xué)習(xí)圖上編碼已經(jīng)生成的部分輸出序列（例如，如果輸出路徑辕狰，則為目前為止的路徑）以及仍然需要生成的部分輸出序列（例如改备，剩余路徑）的特征。我們將展示GNN框架如何適應(yīng)這些設(shè)置蔓倍，從而產(chǎn)生一種新的基于圖的神經(jīng)網(wǎng)絡(luò)模型悬钳，我們稱(chēng)之為門(mén)控圖序列神經(jīng)網(wǎng)絡(luò)（Gated Graph Sequence Neural Networks ，GGS-NNs）偶翅。

我們?cè)赽AbI任務(wù)的實(shí)驗(yàn)（Weston等人默勾，2015）和圖算法學(xué)習(xí)任務(wù)中說(shuō)明了這個(gè)通用模型的各個(gè)方面，這些任務(wù)說(shuō)明了模型的能力聚谁。然后我們提出一個(gè)應(yīng)用程序來(lái)驗(yàn)證計(jì)算機(jī)程序母剥。當(dāng)試圖證明諸如內(nèi)存安全（即程序中沒(méi)有空指針引用）之類(lèi)的屬性時(shí)，核心問(wèn)題是找到程序中使用的數(shù)據(jù)結(jié)構(gòu)的數(shù)學(xué)描述形导。遵循Brockschmidt等人（2015年）环疼，我們將其描述為一個(gè)機(jī)器學(xué)習(xí)問(wèn)題，我們將學(xué)習(xí)從一組表示內(nèi)存狀態(tài)的輸入圖映射到已實(shí)例化的數(shù)據(jù)結(jié)構(gòu)的邏輯描述朵耕。而B(niǎo)rockschmidt等人（2015）依靠大量的手工特征工程炫隶，我們證明該系統(tǒng)可以用GGS-NN代替，而無(wú)需任何精確度成本阎曹。

3. 圖神經(jīng)網(wǎng)絡(luò)

在本節(jié)中伪阶，我們回顧了圖形神經(jīng)網(wǎng)絡(luò)（Graph Neural Networks ，GNNs）（Gori等人芬膝，2005年；Scarselli等人形娇，2009年）锰霜，并介紹了將貫穿始終的符號(hào)和概念。

GNNs是根據(jù)圖結(jié)構(gòu)G=（V桐早，E）定義的通用神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)癣缅。節(jié)點(diǎn)v∈V從1厨剪，…，|V|取唯一值友存，邊是對(duì)e =（v祷膳，v'）∈V×V。我們將在這項(xiàng)工作中集中在有向圖上屡立，因此（v直晨，v'）表示有向邊v→v'，但我們注意到框架可以很容易地適應(yīng)無(wú)向圖膨俐；參見(jiàn)scarselli等人（2009）勇皇。節(jié)點(diǎn)v的節(jié)點(diǎn)向量（或節(jié)點(diǎn)表示或節(jié)點(diǎn)嵌入）用h_v∈R^D表示。圖也可以包含每個(gè)節(jié)點(diǎn)v的節(jié)點(diǎn)標(biāo)簽l_v∈\{1焚刺，…敛摘，L_V \}和每個(gè)邊的邊標(biāo)簽或邊類(lèi)型l_e∈\{1，…乳愉，L_E \}兄淫。當(dāng)S是一組節(jié)點(diǎn)時(shí)，我們將重載符號(hào)并讓h_S = \{ h_v | v \in S\};當(dāng)S是一組邊時(shí)蔓姚，我們將重載符號(hào)并讓l_S = \{l_e | e \in S\}捕虽。

函數(shù)IN(v) = \{v'|(v',v)\in E \}返回前一個(gè)節(jié)點(diǎn)(predecessor nodes) v',v'→v。
類(lèi)似地赂乐，OUT(v) = \{v'|(v,v’)\in E \}是一個(gè)后繼節(jié)點(diǎn)(successor nodes) v'的集合,邊v'→v薯鳍。節(jié)點(diǎn)v相鄰的所有節(jié)點(diǎn)的集合為NBR(v) =IN(v) \cup OUT(v)，節(jié)點(diǎn)v進(jìn)出的所有邊的集合為Co(v) = \{(v',v")\in E | v =v' \lor v= v"\} 挨措。

GNNs通過(guò)兩個(gè)步驟將圖映射到輸出挖滤。首先，有一個(gè)傳播步驟來(lái)計(jì)算每個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)表示浅役；第二斩松，輸出模型o_v = g(h_v，l_v)從節(jié)點(diǎn)表示和相應(yīng)的標(biāo)簽映射到每個(gè)節(jié)點(diǎn)v∈V的輸出o_v觉既。在符號(hào)g中惧盹，我們保留對(duì)參數(shù)的依賴(lài)性，并且我們將一直這樣做瞪讼。該系統(tǒng)具有端到端可微性钧椰，所有參數(shù)均采用基于梯度的優(yōu)化方法聯(lián)合學(xué)習(xí)。

3.1 傳播模型(PROPAGATION MODEL)

在這里符欠，迭代過(guò)程傳播節(jié)點(diǎn)表示(iterative procedure propagates node representations)嫡霞。初始節(jié)點(diǎn)表示h_v^{(1)}被設(shè)置為任意值，然后每個(gè)節(jié)點(diǎn)表示都會(huì)根據(jù)下面的循環(huán)進(jìn)行更新希柿，直到收斂诊沪，其中t表示時(shí)間步驟：

image.png

Scarselli等人（2009）討論了幾種變體养筒，包括位置圖形式（positional graph forms）、特定于節(jié)點(diǎn)的更新（node-specific updates）和相鄰節(jié)點(diǎn)的替代表示（alternative representations of neighborhoods）端姚。具體來(lái)說(shuō)晕粪，斯卡塞利等人（2009）建議分解f^*(·)為每個(gè)邊緣項(xiàng)的總和：

image.png

其中f(·)是h_{v'}的線性函數(shù)或神經(jīng)網(wǎng)絡(luò)。f的參數(shù)取決于標(biāo)簽的配置渐裸，例如在以下線性情況下巫湘，A和b是可學(xué)習(xí)的參數(shù)：

image.png

2.2 輸出模型與學(xué)習(xí)（OUTPUT MODEL AND LEARNING）

輸出模型是按節(jié)點(diǎn)定義的，是映射到輸出的可微分函數(shù)g(h_v,l_v)橄仆。這通常是線性或神經(jīng)網(wǎng)絡(luò)映射剩膘。斯卡塞利等人（2009）關(guān)注每個(gè)節(jié)點(diǎn)獨(dú)立的輸出，這些輸出通過(guò)映射最終節(jié)點(diǎn)表示h_v^{(T)}來(lái)實(shí)現(xiàn)盆顾，到每個(gè)節(jié)點(diǎn)v∈V的輸出o_v = g(h_v^{(T)}怠褐，l_v)。為了處理圖級(jí)分類(lèi)您宪，他們建議創(chuàng)建一個(gè)虛擬的“超級(jí)節(jié)點(diǎn)”(dummy “super node”)奈懒，通過(guò)一種特殊的邊連接到所有其他節(jié)點(diǎn)。因此宪巨，圖級(jí)回歸或分類(lèi)可以以與節(jié)點(diǎn)級(jí)回歸或分類(lèi)相同的方式處理磷杏。

學(xué)習(xí)是通過(guò)Almeida-Pineda算法（Almeida，1990捏卓；Pineda极祸，1987）完成的，該算法通過(guò)運(yùn)行傳播到收斂怠晴，然后根據(jù)收斂解計(jì)算梯度遥金。這樣做的好處是不需要存儲(chǔ)中間狀態(tài)來(lái)計(jì)算梯度。缺點(diǎn)是必須對(duì)參數(shù)進(jìn)行約束蒜田，以便傳播步驟是收縮圖稿械。這是為了確保收斂性，但可能會(huì)限制模型的表現(xiàn)力冲粤。當(dāng)f(·)是一個(gè)神經(jīng)網(wǎng)絡(luò)時(shí)美莫，鼓勵(lì)在網(wǎng)絡(luò)雅可比矩陣(network’s Jacobian)的1-范數(shù)上使用懲罰項(xiàng)。請(qǐng)參閱附錄A中的一個(gè)示例梯捕，該示例給出了收縮圖(contraction maps)在圖中長(zhǎng)范圍傳播信息時(shí)遇到困難的直覺(jué)厢呵。

4. 門(mén)控圖神經(jīng)網(wǎng)絡(luò)（GATED GRAPH NEURAL NETWORKS）

我們現(xiàn)在描述門(mén)控圖神經(jīng)網(wǎng)絡(luò)（Gated Graph Neural Networks ,GG-NNs），我們對(duì)GNN的改變傀顾，適用于非順序輸出襟铭。我們將在下一節(jié)中描述順序輸出。GNN的最大修改是，我們使用門(mén)控循環(huán)單位（Gated Recurrent Units）（Cho等人蝌矛，2014年），將循環(huán)展開(kāi)固定數(shù)量的步驟T错英，并通過(guò)時(shí)間進(jìn)行反向傳播入撒，以計(jì)算梯度。這比Almeida-Pineda算法需要更多的內(nèi)存椭岩，但它消除了約束參數(shù)以確保收斂的需要茅逮。我們還擴(kuò)展了底層表示和輸出模型。

4.1節(jié)點(diǎn)注釋(NODE ANNOTATIONS)

在GNNs中判哥，由于收縮映射(contraction map)約束確保固定點(diǎn)獨(dú)立于初始化献雅，因此在初始化節(jié)點(diǎn)表示中沒(méi)有點(diǎn)。GG-NNS不再是這樣塌计，它允許我們將節(jié)點(diǎn)標(biāo)簽作為額外的輸入挺身。為了區(qū)分這些作為輸入的節(jié)點(diǎn)標(biāo)簽和前面介紹的節(jié)點(diǎn)標(biāo)簽，我們將它們稱(chēng)為節(jié)點(diǎn)注釋?zhuān)⑹褂孟蛄?img class="math-inline" src="https://math.jianshu.com/math?formula=x" alt="x" mathimg="1">來(lái)表示這些注釋锌仅。

為了說(shuō)明如何使用節(jié)點(diǎn)注釋?zhuān)紤]一個(gè)訓(xùn)練圖神經(jīng)網(wǎng)絡(luò)的示例任務(wù)章钾，以預(yù)測(cè)是否可以從給定圖上的節(jié)點(diǎn)s到達(dá)節(jié)點(diǎn)t。對(duì)于此任務(wù)热芹，有兩個(gè)與問(wèn)題相關(guān)的特殊節(jié)點(diǎn)贱傀，s和t。為了將這些節(jié)點(diǎn)標(biāo)記為特殊節(jié)點(diǎn)伊脓，我們給它們一個(gè)初始注釋府寒。第一個(gè)節(jié)點(diǎn)s獲取注釋x_s=[1,0]^T，第二個(gè)節(jié)點(diǎn)t獲取注釋x_t=[0,1]^T报腔。所有其他節(jié)點(diǎn)v的初始注釋都設(shè)置為x_v=[1,0]^T株搔。直觀地說(shuō)，這將標(biāo)記s為第一個(gè)輸入?yún)?shù)和t為第二個(gè)輸入?yún)?shù)榄笙。然后邪狞，我們使用這些標(biāo)簽向量初始化節(jié)點(diǎn)狀態(tài)向量h_v^{(1)}，方法是將x_v復(fù)制到第一個(gè)維度并填充使用額外的0,允許大于注釋?zhuān)╝nnotation）大小的隱藏狀態(tài)茅撞。

在可達(dá)性示例中帆卓，傳播模型很容易學(xué)習(xí)將s節(jié)點(diǎn)注釋傳播到所有可從s中訪問(wèn)的節(jié)點(diǎn)，例如米丘，通過(guò)將與前向邊(forward edges)關(guān)聯(lián)的傳播矩陣（propagation matrix）在位置（0,0）設(shè)置為1剑令。這將導(dǎo)致沿前向邊復(fù)制節(jié)點(diǎn)表示的第一個(gè)維度。使用此參數(shù)設(shè)置拄查，傳播步驟將使所有可從s訪問(wèn)的節(jié)點(diǎn)的第一位節(jié)點(diǎn)表示設(shè)置為1吁津。然后，輸出步驟分類(lèi)器可以通過(guò)查看某個(gè)節(jié)點(diǎn)在其表示向量的前兩個(gè)維度中是否有非零條目，很容易地判斷該節(jié)點(diǎn)t是否可從s中訪問(wèn)碍脏。

4.2 傳播模型

傳播模型的基本循環(huán)是：（recurrence）

image.png

矩陣A \in R^{D|V|*2D|V|}決定了圖中的節(jié)點(diǎn)如何相互通信梭依。A中的稀疏結(jié)構(gòu)和參數(shù)連接(parameter tying)如圖1所示。稀疏結(jié)構(gòu)對(duì)應(yīng)于圖的邊典尾，每個(gè)子矩陣中的參數(shù)由邊的類(lèi)型和方向決定役拴。A_{v:} \in R^{D|V|*2D}是節(jié)點(diǎn)v對(duì)應(yīng)的A^{(out)}和A^{(in)}的兩列塊。 公式1是初始化步驟钾埂，它將節(jié)點(diǎn)注釋復(fù)制到隱藏狀態(tài)的第一個(gè)組件中河闰，并用零填充其余部分。公式2是通過(guò)傳入和傳出邊在圖的不同節(jié)點(diǎn)之間傳遞信息的步驟褥紫，這些邊的參數(shù)取決于邊的類(lèi)型和方向姜性。a_{v}^{(t)} \in R^{2D}包含從兩個(gè)方向的邊激活。其余的是類(lèi)似GRU的更新髓考，其中包含來(lái)自其他節(jié)點(diǎn)的信息部念，以及來(lái)自上一個(gè)時(shí)間步驟的信息，以更新每個(gè)節(jié)點(diǎn)的隱藏狀態(tài)氨菇。z和r是更新和重置門(mén)印机，\sigma (x) =1/(1+e^{-x})是邏輯sigmoid函數(shù)，并且\bigodot是元素乘法(element-wise multiplication)门驾。我們最初嘗試了一個(gè)普通的重復(fù)神經(jīng)網(wǎng)絡(luò)風(fēng)格的更新(vanilla recurrent neural network-style update)射赛，但在初步實(shí)驗(yàn)中，我們發(fā)現(xiàn)這種類(lèi)似GRU的傳播步驟更有效奶是。

image.png

4.3 輸出模型(OUTPUT MODELS)

我們希望在不同的情況下產(chǎn)生幾種類(lèi)型的一步輸出楣责。第一，GG-NNs通過(guò)為每個(gè)節(jié)點(diǎn)v \in V生成支持節(jié)點(diǎn)選擇任務(wù)o_v = g(h_v^{(T)}聂沙，x_v)輸出節(jié)點(diǎn)得分秆麸，并在節(jié)點(diǎn)得分上應(yīng)用Softmax。其次及汉，對(duì)于圖級(jí)輸出沮趣，我們將圖級(jí)表示向量定義為:

image.png

其中\sigma (i(h_v^{(T)}，x_v))充當(dāng)軟注意機(jī)制(soft attention mechanism)坷随，決定哪些節(jié)點(diǎn)與當(dāng)前圖級(jí)任務(wù)相關(guān)房铭。i和j是采用h_v^{(T)}和x_v連接的神經(jīng)網(wǎng)絡(luò)作為輸入和輸出實(shí)值向量。tanh函數(shù)也可以用標(biāo)識(shí)替換温眉。

5. 門(mén)控圖序列神經(jīng)網(wǎng)絡(luò)(GATED GRAPH SEQUENCE NEURAL NETWORKS)

在這里缸匪，我們描述門(mén)控圖序列神經(jīng)網(wǎng)絡(luò)（Gated Graph Sequence Neural Networks,GGS-NNs），其中幾個(gè)GG-NNs按順序操作以產(chǎn)生輸出序列o^{(1)}...o^{(K)}类溢。
對(duì)于k^{th}輸出步驟凌蔬，我們將節(jié)點(diǎn)注釋的矩陣表示為\chi ^{(k)} = [x_1^{(k)},...,x_{|V|}^{(k)} ]^T \in R^{|V|*L_V}。我們用兩個(gè)GG-NNs F_o^{(k)}和F_{\chi}^{(k)}：F_o^{(k)}來(lái)從\chi ^{(k)}預(yù)測(cè)o^{(k)}，F_{\chi}^{(k)}從\chi ^{(k)}預(yù)測(cè)\chi ^{(k+1)}砂心。

\chi ^{(k+1)}被視為從步驟k到k+1的狀態(tài)懈词。F_o^{(k)}和F_{\chi}^{(k)}這兩個(gè)都包含一個(gè)傳播模型和一個(gè)輸出模型。在傳播模型中辩诞，我們表示節(jié)點(diǎn)向量的矩陣 k^{th}輸出步驟的 t^{th}傳播步驟為H^{(k,t)} = [h_1^{(k,t)};...;H_{|V|}^{(k,t)}]^T \in R^{|V|*D}

和前面一樣钦睡，在步驟k中，我們?cè)O(shè)置了H^{(k,1)}通過(guò) 0-extending \chi ^{(k)} 的每一個(gè)節(jié)點(diǎn)躁倒。模型概述如圖2所示∪髯粒或者秧秉，F_o^{(k)}和F_{\chi}^{(k)}可以共享一個(gè)傳播模型，并且只具有單獨(dú)的輸出模型衰抑。這種簡(jiǎn)單的變種更容易訓(xùn)練和評(píng)估象迎，以及在許多情況下，可以達(dá)到與完整模型相同的性能水平呛踊。但在某些情況下砾淌，F_o^{(k)}和F_{\chi}^{(k)}理想的傳播行為不一樣，這個(gè)變種可能不太管用谭网。

我們引入了一個(gè)節(jié)點(diǎn)注釋輸出模型汪厨，用于從H^{(k,T)}預(yù)測(cè)\chi ^{(k+1)}。 每個(gè)節(jié)點(diǎn)的預(yù)測(cè)都是獨(dú)立地使用一個(gè)神經(jīng)網(wǎng)絡(luò)j(H_v^{(k,T)},x_v^{(k)})來(lái)完成的愉择，它將H_v^{(k,T)}和x_v^{(k)}的連接（concatenation）作為輸入劫乱，輸出一個(gè)實(shí)值分?jǐn)?shù)的向量：

image.png

訓(xùn)練GGS-NNs有兩種設(shè)置：指定所有中間注釋\chi ^{(k)}，或訓(xùn)練僅給定\chi ^{(k)}锥涕、圖和目標(biāo)序列的完整模型端到端衷戈。前者可以提高我們對(duì)特定中間信息（表示在節(jié)點(diǎn)的中間狀態(tài)）的領(lǐng)域知識(shí)的性能，而后者更一般层坠。我們都描述過(guò)殖妇。

帶有觀察到的注釋的序列輸出（Sequence outputs with observed annotations）
考慮到為一個(gè)圖進(jìn)行序列預(yù)測(cè)的任務(wù)，其中每個(gè)預(yù)測(cè)都只是圖的一部分破花。為了確保我們準(zhǔn)確地預(yù)測(cè)圖中每個(gè)部分的輸出一次谦趣，每個(gè)節(jié)點(diǎn)都有一個(gè)位就足夠了，表明到目前為止是否已經(jīng)“解釋”了該節(jié)點(diǎn)座每。在某些設(shè)置中蔚润，少量注釋足以捕獲輸出過(guò)程的狀態(tài)。在這種情況下尺栖，我們可能希望通過(guò)指示目標(biāo)中間注釋的標(biāo)簽將此信息直接輸入到模型中嫡纠。在某些情況下，這些注釋可能是足夠的，因?yàn)槲覀兛梢远x一個(gè)模型除盏，在給定注釋的情況下叉橱，在該模型中，GG-NNs是條件獨(dú)立的者蠕。

在這種情況下窃祝，在訓(xùn)練時(shí)，給出了注釋\chi ^{(k)}序列預(yù)測(cè)任務(wù)分解為單步預(yù)測(cè)任務(wù)踱侣，可以訓(xùn)練為單獨(dú)的GG-NNs。在測(cè)試時(shí)抡句，一個(gè)步驟中的預(yù)測(cè)注釋將用作下一個(gè)步驟的輸入探膊。這類(lèi)似于在完全觀察數(shù)據(jù)時(shí)訓(xùn)練定向圖形模型（training directed graphical models）。

序列輸出通常帶有潛在注釋?zhuān)⊿equence outputs with latent annotations）

更加一般化待榔，當(dāng)中間節(jié)點(diǎn)注釋\chi ^{(k)}在訓(xùn)練過(guò)程中不可用時(shí)逞壁，我們將其視為網(wǎng)絡(luò)中的隱藏單元，通過(guò)對(duì)整個(gè)序列進(jìn)行反向傳播锐锣，共同訓(xùn)練整個(gè)模型腌闯。

6. 解釋性應(yīng)用（EXPLANATORY APPLICATIONS）

在本節(jié)中，我們將給出具體說(shuō)明GGS-NNs用法的示例應(yīng)用程序雕憔。我們專(zhuān)注于選擇bAbI人工智能（AI）任務(wù)（Weston等人钠署，2015年）和兩個(gè)圖算法學(xué)習(xí)任務(wù)枢冤。

6.1 巴比任務(wù)（BABI TASKS）

BABI任務(wù)旨在測(cè)試人工智能系統(tǒng)應(yīng)該具備的推理能力（reasoning capabilities）。在BABI套件中，有20個(gè)任務(wù)測(cè)試推理的基本形式稍计，如演繹迹卢、歸納尉咕、計(jì)數(shù)和路徑查找莹弊。

我們定義了一個(gè)基本的轉(zhuǎn)換過(guò)程，將BABI任務(wù)映射到GG-NNs 或 GGS-NNs翁潘。我們使用發(fā)布的babi代碼中的--symbolic選項(xiàng)來(lái)獲取只涉及實(shí)體之間關(guān)系序列的故事趁冈，然后將其轉(zhuǎn)換為一個(gè)圖。每個(gè)實(shí)體都映射到一個(gè)節(jié)點(diǎn)拜马，并且每個(gè)關(guān)系都映射到一個(gè)邊渗勘，邊標(biāo)簽由該關(guān)系給出。整個(gè)故事(story)被消耗(consumed)并映射到一個(gè)圖俩莽。問(wèn)題在數(shù)據(jù)中以eval標(biāo)記旺坠，由問(wèn)題類(lèi)型（例如has_fear）和一些參數(shù)（例如一個(gè)或多個(gè)節(jié)點(diǎn)）組成。參數(shù)轉(zhuǎn)換為初始節(jié)點(diǎn)注釋?zhuān)渲械牡趇位是第i參數(shù)節(jié)點(diǎn)的注釋向量設(shè)置為1扮超。例如取刃，如果eval行是eval E>A true蹋肮，那么E將得到初始注釋x_E^{(1)} = [1,0]^T，A將得到x_A^{(1)} = [0,1]^T璧疗，以及所有其他節(jié)點(diǎn)v坯辩，x_v^{(1)} = [0,0]^T。問(wèn)題類(lèi)型為1（對(duì)于“>”）崩侠，輸出為類(lèi)1（對(duì)于“true”）漆魔。有些任務(wù)有多個(gè)問(wèn)題類(lèi)型，例如任務(wù)4却音，它有4個(gè)問(wèn)題類(lèi)型：E改抡、S、W系瓢、N阿纤。對(duì)于這些任務(wù)，我們只需為每個(gè)任務(wù)訓(xùn)練一個(gè)單獨(dú)的GGNN八拱。在任何實(shí)驗(yàn)中，我們都不會(huì)使用強(qiáng)監(jiān)督標(biāo)簽或給GGS-NNs任何中間注釋涯塔。

雖然很簡(jiǎn)單肌稻，但這種轉(zhuǎn)換并不能保存有關(guān)故事的所有信息（例如，它丟棄輸入的時(shí)間順序）匕荸，也不容易處理三元和更高階關(guān)系（例如爹谭，昨天約翰去花園(Yesterday John went to the garden)時(shí)不容易映射到簡(jiǎn)單的邊）。我們還強(qiáng)調(diào)榛搔，將一般自然語(yǔ)言映射為符號(hào)形式是一項(xiàng)非常重要的任務(wù)诺凡，[2]因此我們不能將這種方法直接應(yīng)用于任意自然語(yǔ)言。放寬這些限制是為了將來(lái)的工作践惑。

然而腹泌，即使有了這個(gè)簡(jiǎn)單的轉(zhuǎn)換，也有各種各樣的bAbI任務(wù)可以被定義尔觉，包括任務(wù)19（路徑查找）凉袱，這無(wú)疑是最困難的任務(wù)。我們提供基線來(lái)證明符號(hào)表示對(duì)RNN或LSTM沒(méi)有顯著的幫助侦铜，并且表明GGS-NNs通過(guò)少量的訓(xùn)練實(shí)例解決了這個(gè)問(wèn)題专甩。我們還開(kāi)發(fā)了兩個(gè)新的類(lèi)似bAbI的任務(wù)，包括在圖上輸出序列：最短路徑和一個(gè)簡(jiǎn)單形式的歐拉電路（在隨機(jī)連接的2-正則圖上）钉稍。這些實(shí)驗(yàn)的目的是為了說(shuō)明GGS-NNs在各種問(wèn)題上的能力涤躲。

image.png

在這里，前8行描述了事實(shí)贡未，GG-NN將使用這些事實(shí)構(gòu)建一個(gè)圖种樱。大寫(xiě)字母是節(jié)點(diǎn)蒙袍、is 和 has_fear被解釋為邊緣標(biāo)簽或邊緣類(lèi)型。最后4行是針對(duì)該輸入數(shù)據(jù)提出的4個(gè)問(wèn)題缸托。這些行中的has_fear被解釋為問(wèn)題類(lèi)型左敌。對(duì)于這個(gè)任務(wù)，在每個(gè)問(wèn)題中俐镐，只有一個(gè)節(jié)點(diǎn)是特殊的矫限，例如eval b has_fear中的b，我們將單個(gè)值1分配給這個(gè)特殊節(jié)點(diǎn)的注釋向量佩抹，將0分配給所有其他節(jié)點(diǎn)叼风。

對(duì)于RNN和LSTM，數(shù)據(jù)轉(zhuǎn)換為如下令牌序列：

image.png

其中n<id>是節(jié)點(diǎn)棍苹，e<id>是邊緣无宿，q<id>是問(wèn)題類(lèi)型，添加額外的標(biāo)記eol（行尾枢里，end-of-line）和ans（應(yīng)答）孽鸡，以便RNN&LSTM訪問(wèn)數(shù)據(jù)集中的完整信息。最后一個(gè)數(shù)字是類(lèi)標(biāo)簽栏豺。

image.png

在這里彬碱，前4行描述了邊，s奥洼、n巷疼、w、e（本例中沒(méi)出現(xiàn)e）都是不同的邊類(lèi)型灵奖。最后一行是路徑問(wèn)題嚼沿，答案是方向w，s的序列瓷患，因?yàn)閺腂到A的路徑是先向西到E骡尽，然后向南到A。問(wèn)題行中的s擅编，n爆阶，w，e被視為輸出類(lèi)沙咏。

更多訓(xùn)練細(xì)節(jié): 對(duì)于本節(jié)中的所有任務(wù)辨图，我們生成1000個(gè)訓(xùn)練示例和1000個(gè)測(cè)試示例，50個(gè)訓(xùn)練示例用于驗(yàn)證肢藐。在評(píng)估模型性能時(shí)故河，對(duì)于一個(gè)示例中包含多個(gè)問(wèn)題的所有BABI任務(wù)，對(duì)不同問(wèn)題的預(yù)測(cè)進(jìn)行獨(dú)立評(píng)估吆豹。由于數(shù)據(jù)集生成過(guò)程中存在隨機(jī)性鱼的，我們?yōu)槊總€(gè)任務(wù)生成了10個(gè)這樣的數(shù)據(jù)集理盆，并報(bào)告了10個(gè)數(shù)據(jù)集的評(píng)估性能的平均值和標(biāo)準(zhǔn)偏差(standard deviation)。

對(duì)于所有解釋性任務(wù)凑阶，我們從僅在50個(gè)訓(xùn)練示例訓(xùn)練不同的模型開(kāi)始猿规，逐漸將訓(xùn)練示例的數(shù)量增加到100、250宙橱、500和950（保留50個(gè)訓(xùn)練示例以供驗(yàn)證）姨俩，直到模型的測(cè)試精度達(dá)到95%或以上，Babi Standard Weston等人取得了成功（2015）师郑。對(duì)于每種方法环葵，我們報(bào)告了它需要達(dá)到95%精度的最小訓(xùn)練示例數(shù)，以及它達(dá)到的訓(xùn)練示例數(shù)的精度宝冕。在所有這些情況下张遭，我們將傳播過(guò)程展開(kāi)5個(gè)步驟。對(duì)于bAbI任務(wù)4地梨，15菊卷，16，18宝剖，19洁闰，我們使用了GG-NN和節(jié)點(diǎn)向量h_v^{(t)}的大小分別設(shè)為D=4，D=5诈闺，D=6渴庆，D=3铃芦，D=6雅镊。對(duì)于本節(jié)中的所有GGS-NNs，我們使用了F_o^{(k)}和F_{\chi}^{(k)}共享單個(gè)傳播模型的簡(jiǎn)單變體刃滓。對(duì)于最短路徑和歐拉電路任務(wù)(shortest path and Eulerian circuit tasks)仁烹，我們使用D = 20。所有模型都用Adam進(jìn)行了足夠長(zhǎng)的訓(xùn)練（Kingma&BA咧虎，2014年）卓缰，驗(yàn)證集用于選擇最佳模型來(lái)評(píng)估和避免過(guò)度擬合的模型。

6.1.1單步輸出（SINGLE STEP OUTPUTS）

我們選擇四個(gè)適合上述限制的BABI任務(wù)砰诵，需要單步輸出：4（兩個(gè)參數(shù)關(guān)系征唬，Two Argument Relations）、15（基本演繹茁彭，Basic Deduction）总寒、16（基本歸納，Basic Induction）和18（大小推理理肺，Size Reasoning）摄闸。對(duì)于任務(wù)4善镰、15和16，使用節(jié)點(diǎn)選擇GG-NN年枕。對(duì)于任務(wù)18炫欺，我們使用了graph level分類(lèi)版本。所有的GGNN網(wǎng)絡(luò)都包含不到600個(gè)參數(shù)[3]熏兄。

作為基線品洛，我們?cè)谠夹蛄行问降姆?hào)數(shù)據(jù)上訓(xùn)練RNN和LSTM模型。RNN和LSTM使用50維嵌入和50維隱藏層霍弹；它們預(yù)測(cè)序列末尾的單個(gè)輸出毫别，并將輸出視為分類(lèi)問(wèn)題，損失為交叉熵典格。RNN和LSTM分別包含約5K和30K參數(shù)岛宦。

測(cè)試結(jié)果見(jiàn)表1。對(duì)于所有任務(wù)耍缴，GG-NN僅使用50個(gè)訓(xùn)練示例即可達(dá)到完美的測(cè)試精度砾肺，而RNN/LSTM基線要么使用更多的訓(xùn)練示例（任務(wù)4），要么無(wú)法解決任務(wù)（任務(wù)15防嗡、16和18）变汪。

在表2中，我們進(jìn)一步分解了任務(wù)4基線的性能蚁趁，因?yàn)橛?xùn)練數(shù)據(jù)的數(shù)量不同裙盾。雖然RNN和LSTM幾乎都能完美地解決這一任務(wù)，但GGNN的數(shù)據(jù)量卻少得多他嫡，精度達(dá)到100%番官。


image.png
5.1.2 順序輸出（SEQUENTIAL OUTPUTS）

bAbI任務(wù)19（尋徑，Path Finding）可以說(shuō)是所有bAbI任務(wù)中最困難的任務(wù)（參見(jiàn)例如（Sukhbaatar等人钢属，2015年）徘熔，該任務(wù)報(bào)告了所有不使用強(qiáng)監(jiān)督的方法的精確度低于20%。我們將一個(gè)GGS-NN應(yīng)用于這個(gè)問(wèn)題淆党，再次應(yīng)用于數(shù)據(jù)的符號(hào)形式（因此結(jié)果與（Sukhbaatar等人酷师，2015）中的結(jié)果不可比較）。在每個(gè)輸出序列的末尾添加一個(gè)額外的“end”類(lèi)染乌；在測(cè)試時(shí)山孔，網(wǎng)絡(luò)將繼續(xù)進(jìn)行預(yù)測(cè)，直到預(yù)測(cè)“end”類(lèi)為止荷憋。

表3給出了此任務(wù)的結(jié)果台颠。RNN和LSTM都無(wú)法完成此任務(wù)。然而台谊，只有50個(gè)訓(xùn)練實(shí)例蓉媳，我們的GGS-NNs比RNN和LSTM獲得更好的測(cè)試精度譬挚。


image.png

5.2 學(xué)習(xí)圖算法（LEARNING GRAPH ALGORITHMS）

我們進(jìn)一步開(kāi)發(fā)了兩個(gè)新的基于圖上算法問(wèn)題的類(lèi)bAbI任務(wù)：最短路徑和歐拉電路。首先酪呻，我們生成隨機(jī)圖减宣，并生成一個(gè)列出圖中所有邊的故事。問(wèn)題來(lái)自于選擇兩個(gè)隨機(jī)節(jié)點(diǎn)A和B玩荠，請(qǐng)求連接兩個(gè)選定節(jié)點(diǎn)的最短路徑（表示為節(jié)點(diǎn)序列）漆腌。我們將數(shù)據(jù)生成限制為只生成長(zhǎng)度至少為2的從A到B的唯一最短路徑的問(wèn)題。對(duì)于歐拉電路阶冈，我們生成一個(gè)隨機(jī)的兩個(gè)正則（two-regular）連通圖和一個(gè)單獨(dú)的隨機(jī)分心圖（separate random distractor graph）闷尿。問(wèn)題給出兩個(gè)節(jié)點(diǎn)A和B并啟動(dòng)電路，然后問(wèn)題是返回給定子圖上的歐拉電路（再次表示為一系列節(jié)點(diǎn)）女坑，該子圖從A到B開(kāi)始填具。結(jié)果如表3所示。RNN和LSTM在這兩項(xiàng)任務(wù)上都失敗了匆骗，但GGS-NNs只學(xué)習(xí)使用50個(gè)訓(xùn)練示例做出完美的預(yù)測(cè)劳景。

6 用GGS-NNS進(jìn)行程序驗(yàn)證（PROGRAM VERIFICATION WITH GGS-NNS）

我們?cè)贕GS NNS上的工作是由程序驗(yàn)證中的實(shí)際應(yīng)用所推動(dòng)的。程序自動(dòng)驗(yàn)證的一個(gè)關(guān)鍵步驟是程序不變量的推導(dǎo)碉就，它近似于執(zhí)行過(guò)程中可達(dá)到的程序狀態(tài)集盟广。尋找數(shù)據(jù)結(jié)構(gòu)的不變量是一個(gè)開(kāi)放的問(wèn)題。例如瓮钥，考慮右邊的簡(jiǎn)單C函數(shù)筋量。

為了證明這個(gè)程序確實(shí)連接了兩個(gè)列表A和B，并且所有指針引用都是有效的碉熄，我們需要（在數(shù)學(xué)上）在循環(huán)的每次迭代中描述程序的堆桨武。為此，我們使用分離邏輯（O'hearn等人具被，2001玻募；Reynolds只损，2002）一姿，它使用歸納謂詞來(lái)描述抽象數(shù)據(jù)結(jié)構(gòu)。例如跃惫，列表

Segment被定義為ls（x叮叹，y）x=y v，n.ls（n爆存，y）x→7 val:v蛉顽，next:n，其中7→val:v先较，next:n表示指向一個(gè)內(nèi)存區(qū)域携冤，該區(qū)域包含一個(gè)具有val的結(jié)構(gòu)以及值依次為和的下一個(gè)字段悼粮。在布爾邏輯中，connective是一個(gè)與連詞曾棕，但它還要求其運(yùn)算符引用堆的“單獨(dú)”部分扣猫。因此，ls（cur null）意味著cur要么為空翘地，要么指向堆上的兩個(gè)值申尤，在這里由ls再次描述。公式t.ls（acur）ls（curnull）ls（b）是循環(huán)的不變量（即衙耕，在進(jìn)入循環(huán)時(shí)和每次迭代后保持不變）昧穿。使用它，我們可以證明沒(méi)有程序運(yùn)行會(huì)因?yàn)槿∠靡粋€(gè)未分配的內(nèi)存地址（這個(gè)屬性稱(chēng)為內(nèi)存安全）而失敗橙喘，并且該函數(shù)確實(shí)使用一個(gè)霍爾風(fēng)格的驗(yàn)證方案連接了兩個(gè)列表（霍爾时鸵，1969）。XXVn,V厅瞎，Nn,,t
這個(gè)過(guò)程中最困難的部分是提出描述數(shù)據(jù)結(jié)構(gòu)的公式寥枝，這就是我們建議使用機(jī)器學(xué)習(xí)的地方。給定一個(gè)程序磁奖，我們運(yùn)行它幾次囊拜，然后在相關(guān)的程序位置提取內(nèi)存狀態(tài)（以圖形表示；見(jiàn)下文）比搭，然后預(yù)測(cè)分離邏輯公式冠跷。靜態(tài)程序分析工具（例如（Piskac等人，2014））可以檢查候選公式是否足以證明所需的屬性（例如身诺，內(nèi)存安全）蜜托。
6.1形式化
將堆狀態(tài)表示為一個(gè)圖作為輸入，我們考慮了表示程序堆的有向霉赡、可能是循環(huán)圖橄务。這些圖可以從程序的內(nèi)存狀態(tài)自動(dòng)構(gòu)建。每個(gè)圖節(jié)點(diǎn)對(duì)應(yīng)于內(nèi)存中存儲(chǔ)一系列指針的地址（我們?cè)谶@項(xiàng)工作中忽略非指針值）穴亏。圖邊緣反映這些指針值蜂挪，即，有標(biāo)記為0嗓化，…棠涮，k的邊緣分別指向節(jié)點(diǎn)。節(jié)點(diǎn)的一個(gè)子集被標(biāo)記為對(duì)應(yīng)于程序變量刺覆。VV0严肪，…，vkVV0，…驳糯，vk
示例輸入圖在圖3中顯示為“輸入”篇梭。其中，節(jié)點(diǎn)ID（即內(nèi)存地址）顯示在節(jié)點(diǎn)中酝枢。邊緣標(biāo)簽對(duì)應(yīng)于程序中的特定字段很洋，例如，本例中的0對(duì)應(yīng)于上一節(jié)中示例函數(shù)中的下一個(gè)指針隧枫。對(duì)于二叉樹(shù)喉磁，還有兩種指向樹(shù)節(jié)點(diǎn)的左、右子級(jí)的指針類(lèi)型官脓。
輸出表示我們的目標(biāo)是用數(shù)學(xué)方法描述堆的形狀协怒。在我們的模型中，我們將自己局限于分離邏輯的語(yǔ)法限制版本卑笨，其中公式的形式為x1孕暇，…，xn.a1……am赤兴，其中每個(gè)原子式為ls（x妖滔，y）（從到的列表）、tree（x）（從中開(kāi)始的二進(jìn)制樹(shù)）或none（x）（在處沒(méi)有數(shù)據(jù)結(jié)構(gòu)）桶良。存在量詞用于為堆節(jié)點(diǎn)命名座舍，這些節(jié)點(diǎn)需要描述形狀，但不由程序變量標(biāo)記陨帆。例如曲秉，要描述“panhandle list”（以循環(huán)結(jié)尾的列表），需要命名循環(huán)中的第一個(gè)列表元素疲牵。在分離邏輯中承二，這可以表示為t.ls（x，t）ls（t纲爸，t）亥鸠。人工智能XYXX
我們可以為這個(gè)問(wèn)題生成合成（標(biāo)記）數(shù)據(jù)集。為此识啦，我們修復(fù)了一組謂詞负蚊，如ls和tree（擴(kuò)展可以考慮雙鏈接列表段、多樹(shù)）袁滥，以及它們的歸納定義盖桥。然后灾螃，我們使用一組給定的程序變量枚舉實(shí)例化謂詞的分離邏輯公式题翻。最后，對(duì)于每個(gè)公式，我們枚舉滿足該公式的堆圖嵌赠。結(jié)果是一個(gè)由堆圖對(duì)和我們的學(xué)習(xí)過(guò)程使用的關(guān)聯(lián)公式組成的數(shù)據(jù)集塑荒。...
6.2作為GGS-NNS的配方
從數(shù)據(jù)生成過(guò)程中很容易得到中間預(yù)測(cè)步驟的節(jié)點(diǎn)注釋。因此姜挺，我們用觀察到的注釋?zhuān)ㄔ谟?xùn)練時(shí)觀察到的齿税，而不是測(cè)試時(shí)觀察到的）來(lái)訓(xùn)練ggs-nn的變體，以從堆圖推斷公式炊豪。注意凌箕，也可以使用未觀察到的集氣站。-

神經(jīng)網(wǎng)絡(luò)變種和做端到端學(xué)習(xí)词渤。該過(guò)程將分離邏輯公式的生成分解為一系列步驟牵舱。我們首先決定是否聲明存在變量，如果是缺虐，選擇與變量對(duì)應(yīng)的節(jié)點(diǎn)芜壁。一旦聲明了存在主義，我們將遍歷所有變量名高氮，并生成一個(gè)分離邏輯公式慧妄，描述與當(dāng)前變量對(duì)應(yīng)的節(jié)點(diǎn)上的根數(shù)據(jù)結(jié)構(gòu)。
下面是預(yù)測(cè)分離邏輯公式的完整算法alg剪芍。1塞淹。我們使用三個(gè)顯式節(jié)點(diǎn)注釋?zhuān)疵ㄓ沙绦蜃兞繕?biāo)記的堆節(jié)點(diǎn)或聲明的存在量化變量）、活動(dòng)（參見(jiàn)算法）和解釋?zhuān)ǘ压?jié)點(diǎn)是已經(jīng)預(yù)測(cè)的數(shù)據(jù)結(jié)構(gòu)的一部分）罪裹。初始節(jié)點(diǎn)標(biāo)簽可以直接從輸入圖中計(jì)算出來(lái)：“isnamed”是打開(kāi)的窖铡，對(duì)于由程序變量標(biāo)記的節(jié)點(diǎn)，“active”和“is explained”總是關(guān)閉的（在第2行中完成）坊谁。算法中的注釋行使用gg-nn實(shí)現(xiàn)费彼，即alg。1是我們的ggs-nn模型的一個(gè)實(shí)例口芍。圖3顯示了算法運(yùn)行的開(kāi)始箍铲，其中每個(gè)步驟與算法的一行相關(guān)。
6.3模型設(shè)置詳細(xì)信息
我們使用完整的GGS-NN模型鬓椭，其中和f有單獨(dú)的傳播模型颠猴。對(duì)于ggs-nn管道中的所有g(shù)g-nn組件，我們將傳播過(guò)程展開(kāi)10個(gè)時(shí)間步驟小染。與步驟（?）相關(guān)的ggs nns（決定是否需要聲明更為存在量化的變量）和（）（確定需要聲明為存在量化的節(jié)點(diǎn)）使用=16維節(jié)點(diǎn)表示翘瓮。對(duì)于所有其他GGS-NN組件，使用=8裤翩。Adam（Kingma&BA资盅，2014）用于優(yōu)化，模型在20個(gè)圖形的小批量上進(jìn)行訓(xùn)練，并進(jìn)行優(yōu)化呵扛，直到訓(xùn)練誤差非常低每庆。對(duì)于圖級(jí)分類(lèi)任務(wù)，我們還人為地平衡了類(lèi)今穿，使每個(gè)小批量中每個(gè)類(lèi)的示例數(shù)相等缤灵。所有的GGS-NN組件包含的參數(shù)都小于5K，并且在訓(xùn)練過(guò)程中沒(méi)有觀察到過(guò)擬合蓝晒。X（k）DD
6.4批次預(yù)測(cè)詳情
在實(shí)踐中腮出，將給出一組堆圖作為輸入，并期望單個(gè)輸出公式描述所有輸入圖并與之一致芝薇。不同的堆圖可以是程序執(zhí)行過(guò)程中不同點(diǎn)的堆狀態(tài)快照利诺，也可以是具有不同輸入的同一程序的不同運(yùn)行。我們稱(chēng)之為“批量預(yù)測(cè)”設(shè)置剩燥，與本文描述的單圖預(yù)測(cè)相比慢逾。

為了進(jìn)行批處理預(yù)測(cè)，我們同時(shí)為每個(gè)圖運(yùn)行一個(gè)ggs-nn灭红。對(duì)于每一個(gè)預(yù)測(cè)步驟侣滩，該步驟中的所有g(shù)gs nns的輸出在一批圖中進(jìn)行聚合。
對(duì)于節(jié)點(diǎn)選擇輸出变擒，公共命名變量將不同圖形上的節(jié)點(diǎn)鏈接到一起君珠，這是在一批中聚合預(yù)測(cè)的關(guān)鍵。我們計(jì)算特定命名變量的得分娇斑，其中vg（t）映射變量名T對(duì)于圖中的節(jié)點(diǎn)策添，是已命名變量的輸出分?jǐn)?shù)T在圖表中。當(dāng)對(duì)所有使用as分?jǐn)?shù)的名稱(chēng)應(yīng)用SoftMax時(shí)毫缆，這相當(dāng)于計(jì)算（Toselect=t）=q（Toselect=vg（t））的模型唯竹。GOT磷G前列腺素
對(duì)于圖級(jí)分類(lèi)輸出，我們將一批圖中特定類(lèi)的分?jǐn)?shù)相加苦丁，或者等價(jià)地計(jì)算（class=k）=q（class=k）浸颓。節(jié)點(diǎn)注釋輸出會(huì)獨(dú)立地為每個(gè)圖更新，因?yàn)椴煌膱D具有完全不同的節(jié)點(diǎn)集旺拉。但是产上，當(dāng)算法嘗試更新一個(gè)命名變量的注釋時(shí)，所有圖中與該變量關(guān)聯(lián)的節(jié)點(diǎn)都會(huì)更新蛾狗。在培訓(xùn)過(guò)程中晋涣，中間步驟的所有標(biāo)簽都可以從數(shù)據(jù)生成過(guò)程中獲得，因此培訓(xùn)過(guò)程可以再次分解為單輸出單圖培訓(xùn)沉桌。磷G前列腺素
Brockschmidt等人討論了允許嵌套數(shù)據(jù)結(jié)構(gòu)（例如列表列表）的更復(fù)雜的方案谢鹊。（2015）算吩。我們還成功地將ggs-nn模型擴(kuò)展到了這個(gè)案例中。更多有關(guān)這方面的詳細(xì)信息撇贺，請(qǐng)參見(jiàn)附錄C赌莺。
6.5實(shí)驗(yàn)冰抢。
在本文中松嘶，我們生成了一個(gè)包含三個(gè)程序變量的327個(gè)公式的數(shù)據(jù)集，每個(gè)公式有498個(gè)圖挎扰，產(chǎn)生了大約160000個(gè)公式/堆圖組合翠订。為了進(jìn)行評(píng)估，我們使用對(duì)公式（即遵倦，測(cè)試集中的公式不在培訓(xùn)集中）的6:2:2分割尽超，將數(shù)據(jù)分割為培訓(xùn)、驗(yàn)證和測(cè)試集梧躺。我們通過(guò)測(cè)試時(shí)預(yù)測(cè)的公式是否在邏輯上等同于基本真理來(lái)衡量正確性似谁；通過(guò)規(guī)范化公式的名稱(chēng)和順序來(lái)近似等效，然后進(jìn)行精確的相等比較掠哥。
我們將我們基于GGS神經(jīng)網(wǎng)絡(luò)的模型與之前開(kāi)發(fā)的方法進(jìn)行了比較（Brockschmidt等人巩踏，2015）。早期的方法將每個(gè)預(yù)測(cè)步驟視為標(biāo)準(zhǔn)分類(lèi)续搀，并且需要復(fù)雜的塞琼、手動(dòng)的、特定于問(wèn)題的特征工程禁舷，以達(dá)到89.11%的精度彪杉。相比之下，我們的新模型在沒(méi)有特征工程和很少的領(lǐng)域知識(shí)的情況下進(jìn)行了培訓(xùn)牵咙，獲得了89.96%的準(zhǔn)確率派近。
我們的ggs-nn模型發(fā)現(xiàn)的一個(gè)示例堆圖和相應(yīng)的分離邏輯公式如圖4所示。此示例還涉及嵌套數(shù)據(jù)結(jié)構(gòu)和上一節(jié)中開(kāi)發(fā)的批處理擴(kuò)展洁桌。
我們還成功地在程序驗(yàn)證框架中使用了我們的新模型构哺，為定理證明器提供了所需的程序不變量，以證明插入排序等列表操作算法集合的正確性战坤。下表4列出了一組基準(zhǔn)列表操作程序和由GGS-NN模型發(fā)現(xiàn)的分離邏輯公式不變量曙强，并成功地在驗(yàn)證框架中使用，以證明相應(yīng)程序的正確性途茫。

當(dāng)前管道的進(jìn)一步擴(kuò)展已經(jīng)證明能夠成功地證明更復(fù)雜的程序碟嘴，如排序程序和各種其他列表操作程序。

8 相關(guān)工作

最密切相關(guān)的工作是GNN囊卜，我們已經(jīng)在上面詳細(xì)討論過(guò)娜扇。Micheli（2009）提出了另一個(gè)密切相關(guān)的模型错沃，主要在輸出模型上與GNN不同。GNN已應(yīng)用于多個(gè)領(lǐng)域（Gori等人雀瓢，2005年枢析；Di-Massa等人，2006年刃麸；Scarselli等人醒叁，2009年；Uwents等人泊业，2011年）把沼，但它們似乎并未在ICLR社區(qū)中廣泛使用。我們?cè)谶@里的部分目的是宣傳GNN作為一個(gè)有用和有趣的神經(jīng)網(wǎng)絡(luò)變體吁伺。

我們從GNN到GG NNS的適應(yīng)饮睬，到Domke（2011）和Stoyanov等人的工作，可以得出一個(gè)類(lèi)比篮奄。（2011）在結(jié)構(gòu)化預(yù)測(cè)設(shè)置中捆愁。其中信念傳播（必須運(yùn)行到接近收斂以獲得良好的梯度）被截?cái)嘈拍顐鞑ジ滤〈缓髮?duì)模型進(jìn)行訓(xùn)練窟却，使截?cái)嗟诠潭ǖ牡螖?shù)后產(chǎn)生良好的結(jié)果昼丑。同樣，遞歸神經(jīng)網(wǎng)絡(luò)（Goller&Kuchler间校，1996矾克；Socher等人，2011）被擴(kuò)展到樹(shù)LSTMS（Tai等人憔足，2015）類(lèi)似于我們?cè)贕G NNS中使用GRU更新胁附，而不是標(biāo)準(zhǔn)的GNN重復(fù)，目的是改善圖結(jié)構(gòu)中信息的長(zhǎng)期傳播滓彰。

本文所表達(dá)的將特定問(wèn)題的神經(jīng)網(wǎng)絡(luò)組裝成學(xué)習(xí)組件的一般思想有著悠久的歷史控妻，至少可以追溯到Hinton（1988）為預(yù)測(cè)人與人之間的關(guān)系而根據(jù)家族樹(shù)結(jié)構(gòu)組裝神經(jīng)網(wǎng)絡(luò)的工作。類(lèi)似的想法出現(xiàn)在Hammer&Jain（2004）和Bottou（2014）中揭绑。

圖形內(nèi)核（Shervashidze et al.弓候，2011；Kashima et al.他匪，2003）可用于具有圖形結(jié)構(gòu)輸入的各種基于內(nèi)核的學(xué)習(xí)任務(wù)菇存，但我們不知道學(xué)習(xí)內(nèi)核和輸出序列的工作。PeloZi等人邦蜜。（2014）通過(guò)在圖上隨機(jī)遍歷將圖轉(zhuǎn)換為序列依鸥，然后使用基于序列的方法學(xué)習(xí)節(jié)點(diǎn)嵌入。Sperduti&Starita（1997）將圖形映射到圖形向量悼沈，然后使用輸出神經(jīng)網(wǎng)絡(luò)進(jìn)行分類(lèi)贱迟。有幾個(gè)模型利用了圖結(jié)構(gòu)上節(jié)點(diǎn)表示的類(lèi)似傳播姐扮。布魯納等。（2013）將卷積推廣到圖結(jié)構(gòu)衣吠。他們的工作和GNN之間的區(qū)別類(lèi)似于卷積網(wǎng)絡(luò)和循環(huán)網(wǎng)絡(luò)之間的區(qū)別茶敏。Duvenaud等人（2015）還考慮對(duì)圖進(jìn)行卷積樣運(yùn)算，構(gòu)建一個(gè)成功的圖特征的可學(xué)習(xí)缚俏、可微變量惊搏。盧西等人。（2013）將任意無(wú)向圖轉(zhuǎn)換為具有不同方向的多個(gè)不同DAG袍榆，然后向每個(gè)根向內(nèi)傳播節(jié)點(diǎn)表示胀屿，訓(xùn)練一組模型塘揣。在上述所有問(wèn)題中包雀，重點(diǎn)都是一步到位的問(wèn)題。

GNN和我們的擴(kuò)展具有許多與指針網(wǎng)絡(luò)相同的理想屬性（Vinyals等人亲铡，2015年）；當(dāng)使用節(jié)點(diǎn)選擇輸出層時(shí)，可以選擇輸入節(jié)點(diǎn)作為輸出缨历。有兩個(gè)主要的區(qū)別：第一揪罕，在GNN中，圖結(jié)構(gòu)是顯式的吆鹤，這使得模型不那么一般厨疙，但可以提供更強(qiáng)的泛化能力；第二疑务，指針網(wǎng)絡(luò)要求每個(gè)節(jié)點(diǎn)都有屬性（例如沾凄，空間中的位置），而GNN可以表示僅由它們?cè)趫D中的位置定義的節(jié)點(diǎn)知允，這是M使它們?cè)诓煌木S度上更加通用撒蟀。

GGS nns與軟對(duì)準(zhǔn)和注意力模型有關(guān)（例如，Bahdanau等人（2014年）温鸽；Kumar等人（2015年）保屯；Sukhbaatar等人（2015））在兩個(gè)方面：第一，等式7中的圖表示使用上下文來(lái)關(guān)注哪些節(jié)點(diǎn)對(duì)當(dāng)前決策很重要涤垫；第二姑尺，程序驗(yàn)證示例中的節(jié)點(diǎn)注釋跟蹤到目前為止解釋過(guò)哪些節(jié)點(diǎn)，這為確保輸入中的每個(gè)節(jié)點(diǎn)用于產(chǎn)生輸出的序列蝠猬。

9 討論

9.1 正在學(xué)習(xí)什么切蟋？（What is being learned?）

考慮到GG-NNs正在學(xué)習(xí)的，這是有指導(dǎo)意義的吱雏。要做到這一點(diǎn)敦姻，我們可以在babi任務(wù)15如何通過(guò)邏輯公式來(lái)解決之間進(jìn)行類(lèi)比瘾境。舉個(gè)例子，假設(shè)有一個(gè)子集需要回答右邊的一個(gè)例子镰惦。

要進(jìn)行邏輯推理（logical reasoning）迷守，我們不僅需要對(duì)故事中的事實(shí)進(jìn)行邏輯編碼，還需要將背景世界知識(shí)編碼為推理規(guī)則旺入，例如 ：

image.png

我們對(duì)任務(wù)的編碼簡(jiǎn)化了將故事解析為圖形式兑凿，但它不提供任何背景知識(shí)。GG-NN模型可以看作是學(xué)習(xí)這一點(diǎn)茵瘾，結(jié)果存儲(chǔ)在神經(jīng)網(wǎng)絡(luò)權(quán)重中礼华。

9.2 討論：

本文的結(jié)果表明，在一系列問(wèn)題上拗秘，GGS NNS具有理想的誘導(dǎo)偏差圣絮，這些問(wèn)題具有一些內(nèi)在的圖結(jié)構(gòu)，我們相信在更多的情況下雕旨，GGS NNS將是有用的扮匠。然而，為了使其更廣泛地應(yīng)用凡涩，還需要克服一些限制棒搜。我們前面提到的兩個(gè)限制是babi任務(wù)轉(zhuǎn)換不包含輸入的時(shí)間順序或三元和更高階關(guān)系。我們可以想象解除這些限制的幾種可能性活箕，例如連接一系列的gg nns力麸，其中每個(gè)邊有一個(gè)gg nns，并將高階關(guān)系表示為因子圖育韩。更重要的挑戰(zhàn)是如何處理不太結(jié)構(gòu)化的輸入表示克蚂。例如，在babi任務(wù)中座慰，最好不要使用輸入的符號(hào)形式陨舱。一種可能的方法是在我們的GGS NNS中加入較少的結(jié)構(gòu)化輸入和潛在向量。然而版仔，需要實(shí)驗(yàn)來(lái)找到解決這些問(wèn)題的最佳方法游盲。

當(dāng)前的GGS NNS公式僅在所有事實(shí)都被消耗掉之后才指定一個(gè)問(wèn)題。這意味著網(wǎng)絡(luò)必須嘗試派生所見(jiàn)事實(shí)的所有后果蛮粮，并將所有相關(guān)信息存儲(chǔ)到節(jié)點(diǎn)表示中的節(jié)點(diǎn)益缎。這可能不理想；最好開(kāi)發(fā)將問(wèn)題作為初始輸入的方法然想，然后動(dòng)態(tài)地派生出回答問(wèn)題所需的事實(shí)莺奔。

我們對(duì)ggs-nns的進(jìn)一步應(yīng)用持樂(lè)觀態(tài)度。我們特別感興趣的是繼續(xù)開(kāi)發(fā)端到端的可學(xué)習(xí)系統(tǒng)变泄，該系統(tǒng)可以學(xué)習(xí)程序的語(yǔ)義特性令哟，可以學(xué)習(xí)更復(fù)雜的圖形算法恼琼，并將這些思想應(yīng)用于需要對(duì)知識(shí)庫(kù)和數(shù)據(jù)庫(kù)進(jìn)行推理的問(wèn)題。更一般地說(shuō)屏富，我們認(rèn)為這些圖神經(jīng)網(wǎng)絡(luò)代表著朝著一個(gè)模型邁進(jìn)的一步晴竞，該模型可以將結(jié)構(gòu)化表示與強(qiáng)大的深度學(xué)習(xí)算法相結(jié)合，目的是在學(xué)習(xí)和推斷如何推理和擴(kuò)展這些表示的同時(shí)狠半，利用已知的結(jié)構(gòu)噩死。

參考資料

[1] Graph-to-Sequence Learning using Gated Graph Neural Networks
[2] 論文筆記：GGNN (門(mén)控圖神經(jīng)網(wǎng)絡(luò)) 非常好，原理講的很詳細(xì)
[3] 《GATED GRAPH SEQUENCE NEURAL NETWORKS》結(jié)合代碼的論文閱讀筆記
[4] 【筆記】GATED GRAPH SEQUENCE NEURAL NETWORKS

[5] 深度學(xué)習(xí)基礎(chǔ)：RNN神年、LSTM和GRU
[6] GRU神經(jīng)網(wǎng)絡(luò)

代碼

[1] microsoft/gated-graph-neural-network-samples
[2] yujiali/ggnn
[3] calebmah/ggnn.pytorch

論文

[1] Gated graph sequence neural networks

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末已维，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子已日，更是在濱河造成了極大的恐慌垛耳，老刑警劉巖，帶你破解...
    沈念sama閱讀 221,576評(píng)論 6贊 515
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件捂敌，死亡現(xiàn)場(chǎng)離奇詭異艾扮，居然都是意外死亡既琴，警方通過(guò)查閱死者的電腦和手機(jī)占婉，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,515評(píng)論 3贊 399
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)甫恩，“玉大人逆济，你說(shuō)我怎么就攤上這事』腔” “怎么了奖慌？”我有些...
    開(kāi)封第一講書(shū)人閱讀 168,017評(píng)論 0贊 360
  • 道士緝兇錄：失蹤的賣(mài)姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長(zhǎng)松靡。 經(jīng)常有香客問(wèn)我简僧，道長(zhǎng)，這世上最難降的妖魔是什么雕欺？ 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 59,626評(píng)論 1贊 296
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任岛马，我火速辦了婚禮，結(jié)果婚禮上屠列，老公的妹妹穿的比我還像新娘啦逆。我一直安慰自己，他們只是感情好笛洛，可當(dāng)我...
    茶點(diǎn)故事閱讀 68,625評(píng)論 6贊 397
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布夏志。 她就那樣靜靜地躺著，像睡著了一般苛让。 火紅的嫁衣襯著肌膚如雪沟蔑。 梳的紋絲不亂的頭發(fā)上湿诊，一...
    開(kāi)封第一講書(shū)人閱讀 52,255評(píng)論 1贊 308
  • 城市分裂傳說(shuō)
    那天，我揣著相機(jī)與錄音瘦材，去河邊找鬼枫吧。 笑死，一個(gè)胖子當(dāng)著我的面吹牛宇色，可吹牛的內(nèi)容都是我干的九杂。 我是一名探鬼主播，決...
    沈念sama閱讀 40,825評(píng)論 3贊 421
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼宣蠕，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼例隆！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起抢蚀，我...
    開(kāi)封第一講書(shū)人閱讀 39,729評(píng)論 0贊 276
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤镀层，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后皿曲，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體唱逢，經(jīng)...
    沈念sama閱讀 46,271評(píng)論 1贊 320
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,363評(píng)論 3贊 340
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年屋休，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了坞古。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,498評(píng)論 1贊 352
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡劫樟，死狀恐怖痪枫，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情叠艳，我是刑警寧澤奶陈，帶...
    沈念sama閱讀 36,183評(píng)論 5贊 350
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站附较，受9級(jí)特大地震影響吃粒，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜拒课，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,867評(píng)論 3贊 333
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一徐勃、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧捕发，春花似錦疏旨、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,338評(píng)論 0贊 24
  • 一樁弒父案檐涝，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至，卻和暖如春谁榜，著一層夾襖步出監(jiān)牢的瞬間幅聘，已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,458評(píng)論 1贊 272
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工窃植， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留帝蒿，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 48,906評(píng)論 3贊 376
  • 代替公主和親
    正文 我出身青樓巷怜，卻偏偏與公主長(zhǎng)得像葛超，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子延塑，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,507評(píng)論 2贊 359

推薦閱讀更多精彩內(nèi)容