論文作者：Mathias Niepert、Mohamed Ahmed、Konstantin Kutzkov NEC Labs Europe，海德爾堡，德國

論文摘要

許多重要問題可以劃歸到圖像數(shù)據(jù)學(xué)習(xí)框架里。我們針對學(xué)習(xí)卷積神經(jīng)網(wǎng)絡(luò)提出了一個框架，可以適用于任何圖形。這些圖形可以是無向的，定向的，也可以是具有離散和連續(xù)節(jié)點和邊緣屬性。類似于基于圖形的卷積網(wǎng)絡(luò)，可以再本地化的可連接輸入?yún)^(qū)域上允許，我們提出了一種普遍方法，可以從圖形中提取本地化的可連接區(qū)域。使用既定的基準(zhǔn)數(shù)據(jù)集，我們展示了帶有最先進(jìn)圖形內(nèi)核的學(xué)習(xí)功能表現(xiàn)，是具有競爭力的，同時，它們的計算效率也是非常高的。

一、概述

在這篇論文中，我們的目標(biāo)是卷積神經(jīng)網(wǎng)絡(luò)解決一大類基于圖形的學(xué)習(xí)問題。我們想到了以下兩個問題：

1. 給定一個圖形集合，學(xué)習(xí)一項功能，可以用于在未見圖形上進(jìn)行分類和回歸。任意兩個圖的節(jié)點不一定是對應(yīng)的。舉個例子，集合中的每一個圖形都可以“模型化”一種化合物，輸出也可以是一個功能，將未見組件定位到癌細(xì)胞的活性水平。 

2. 給定一個大圖，學(xué)習(xí)圖形表現(xiàn)，可以用來推斷看不見的圖形屬性，比如節(jié)點類型或是缺少的邊。我們提出了一個框架，用于學(xué)習(xí)定向和無向圖形類別的表現(xiàn)。這些圖形可以有多個離散和連續(xù)屬性的節(jié)點和邊，可能有多個類型的邊。和識別圖像的卷積神經(jīng)網(wǎng)絡(luò)類似，我們利用輸入的圖像構(gòu)建了局部連接的鄰域。這些鄰域構(gòu)建效率高，可以充當(dāng)卷積網(wǎng)絡(luò)的感知域，讓卷積網(wǎng)絡(luò)有成效地學(xué)習(xí)圖像特征。

圖1：一個3*3感受域的卷積神經(jīng)網(wǎng)絡(luò)。該域可以覆蓋圖形被移動，從左到右，從上到下，通過使用一個特定跨越（這里：1）和零填充（這里：0）(a).被感受域所讀取的值被轉(zhuǎn)化成一個現(xiàn)行層，并反饋送至一個卷積架構(gòu)(b). 被創(chuàng)建的感受域和感受域的形狀的節(jié)點序列完全由超參數(shù)決定。

 

圖2. 建議架構(gòu)的一個圖例通過一個圖形標(biāo)記程序，從圖中選擇一個節(jié)點序列。對于序列中的一些節(jié)點，局部領(lǐng)域圖將會被拼裝且正則化。正則化的鄰域也將被用作感受域，并且和現(xiàn)有的卷積神經(jīng)網(wǎng)絡(luò)組件進(jìn)行整合。

此處建議的方式根據(jù)卷積神經(jīng)網(wǎng)絡(luò)（CNN）識別圖像的理論（福島邦彥，1980年； Atlaset等人，1988年；LeCun等人，1998年、2015年)而設(shè)計，并將這些理論拓展應(yīng)用在任意圖上。

圖1展示了卷積神經(jīng)網(wǎng)絡(luò)識別圖像的局部連接感知域。

一個圖像可以表現(xiàn)為正方形格網(wǎng)的圖形，其節(jié)點就代表像素。現(xiàn)在，一個卷積神經(jīng)網(wǎng)絡(luò)可以被視為穿越一個節(jié)點序列（圖1（a）中的節(jié)點1到4，每個節(jié)點之間形成大小固定的鄰域圖（圖1（b）的3乘3格網(wǎng)））。鄰域圖可以充當(dāng)感知域，通過像素節(jié)點解讀特征值。由于像素的空間順序并不清晰，鄰域的圖從左到右、從上到下生成節(jié)點序列，這種序列的確定過程是獨特的。自然語言處理（NLP）的問題也同樣是獨一無二的，因為每個句子（及其句法樹）都決定了一些詞語的序列。然而，對多個圖形集合來說，某個特定問題的順序（空間、時間或是其他順序）是缺失的，圖形的節(jié)點并不對應(yīng)。在這種情況下，必須解決兩個問題：(i)確定鄰域產(chǎn)生的節(jié)點序列；(ii) 計算鄰域圖形的正則化，即一種從圖形特征轉(zhuǎn)換到矢量特征的獨特映射。每個輸入圖形首先確定鄰域生成的節(jié)點（及其順序）。在生成這些節(jié)點的鄰域里都能提取一個k節(jié)點，并進(jìn)行正則化。也就是說，以固定的線性順序，進(jìn)行空間的獨特映射。經(jīng)過正則化的鄰域可以成為某個考量節(jié)點的感受域。最終，卷積層和稠密層等特征學(xué)習(xí)組成部分與正則化的鄰域相結(jié)合，形成卷積神經(jīng)網(wǎng)絡(luò)的感受域。

圖2展示了PATCHY-SAN結(jié)構(gòu)。該結(jié)構(gòu)在運(yùn)用現(xiàn)有方式時有諸多優(yōu)勢：

首先，它效率很高，很容易并行，可以應(yīng)用于大圖形；第二，對于計算生物學(xué)和社交網(wǎng)絡(luò)分析等多個領(lǐng)域的應(yīng)用來說，可視化網(wǎng)絡(luò)主題非常重要（Milo等人, 2002），PATCHY-SAN支持特征可視化，那樣可以深入了解圖形結(jié)構(gòu)特征；第三，PATCHY-SAN并未創(chuàng)造另一個圖核，而是學(xué)習(xí)依靠應(yīng)用的特征，無需做特征工程的工作。我們的理論貢獻(xiàn)在于，界定圖形及其復(fù)雜性的正則化問題；提供一種比較方法，比較各種圖形集合的圖形標(biāo)記方式；顯示PATCHY-SAN歸納圖像卷積神經(jīng)網(wǎng)絡(luò)的結(jié)果。我們通過運(yùn)用標(biāo)準(zhǔn)的數(shù)據(jù)集展現(xiàn)出，和高級水平的圖核相比，經(jīng)過學(xué)習(xí)圖像的卷積神經(jīng)網(wǎng)絡(luò)不但有效，而且效率很高。

二、相關(guān)文獻(xiàn)

對圖核可以采用基于核的學(xué)習(xí)方法，如支持向量機(jī)（SVM）就可以直接處理圖形（Vishwanathan等人，2010年）。圖形之核最初的定義是，單個圖形所有節(jié)點的相似函數(shù)（Kondor 與Lafferty，2002年）。核按特征分兩大類，一類是偏差頻譜核，另一類是基于基元的核（Milo等人，2002年；Alon，2007年）。但由于子圖枚舉組合很復(fù)雜，基元圖核受到節(jié)點很少的子圖限制。圖核還有一類是簡稱WL的Weisfeiler-Lehman算法核（Shervashidze等人，2011年）?？墒荳L核只支持離散特征，對測試的訓(xùn)練樣本用有記憶的線性系統(tǒng)。PATCHY-SAN用WL核作為計算感受域時一個可能標(biāo)識的過程。深度圖核（Yanardag與Vishwanathan，2015年）和圖形不變特征核（Orsini等人，2015）比較圖的依據(jù)是子結(jié)構(gòu)的存在方式或者數(shù)量，如根據(jù)基元、子樹和其他圖形的不變特征（Haussler，1999年；Orsini等人，2015年）。PATCHY-SAN則是從圖形數(shù)據(jù)中學(xué)習(xí)子結(jié)構(gòu)，不受預(yù)先界定的主題限制。但所有圖核訓(xùn)練都很復(fù)雜，圖形數(shù)量至少有二次方變化（Shervashidze等人，2011年）。如果是大型圖形的問題，用這種方法需要付出很高代價。PATCHY-SAN用線性方式測量圖形數(shù)量。

圖形神經(jīng)網(wǎng)絡(luò)（GNN）（Scarselli等人，2009年）是通過圖形明確的一個遞歸神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。圖形神經(jīng)網(wǎng)絡(luò)運(yùn)用遞歸神經(jīng)網(wǎng)絡(luò)在圖形結(jié)構(gòu)上游走，這期間傳播節(jié)點表示，直至抵達(dá)一個固定點為止。然后，由此形成的節(jié)點表示會成為可以用于分類和回歸問題的特征。圖形神經(jīng)網(wǎng)絡(luò)僅支持離散的標(biāo)識，只要每次學(xué)習(xí)迭代的圖形都有邊和節(jié)點，就能在很多反向傳播操作中發(fā)揮作用。門控圖序列神經(jīng)網(wǎng)絡(luò)會改變圖形神經(jīng)網(wǎng)絡(luò)，以便利用門控遞歸單元（GRU）和輸出序列（Li等人，2015年）。

最近的論著拓展了卷積神經(jīng)網(wǎng)絡(luò)的應(yīng)用范圍，將它用在有別于低維度格網(wǎng)結(jié)構(gòu)的拓?fù)鋵W(xué)（Bruna等人，2014年；Henaff等人，2015年）。然而，所有這些方法都假定的是一個全球圖形結(jié)構(gòu)，這即是說，不同輸入樣本的頂點是同一個匹配（Duvenaud等人，2015年），基于此在圖形上進(jìn)行卷積類操作，開發(fā)某個圖形特征彼此不同的變量。

三、論文背景

我們在此簡要介紹了在卷積網(wǎng)絡(luò)和圖形理論方面所需的背景。

3.1. 卷積神經(jīng)網(wǎng)絡(luò)

根據(jù)早期論著顯示，動物大腦的視覺皮層生長著結(jié)構(gòu)復(fù)雜的細(xì)胞，它們負(fù)責(zé)監(jiān)測視域內(nèi)小局部域的光。卷積神經(jīng)網(wǎng)絡(luò)正是受到這些論著啟發(fā)而來（Hubel 與Wiesel，1968年）。卷積神經(jīng)網(wǎng)絡(luò)于上世紀(jì)80年代開創(chuàng)，現(xiàn)已用于解決圖像、演講、文本和藥物研發(fā)問題（阿特拉斯等人，1988；LeCun等人，1989年、1998年、2015年；Wallach等人，2015年）。卷積神經(jīng)網(wǎng)絡(luò)的前身是神經(jīng)認(rèn)知機(jī)（福島邦彥，1980年）。卷積神經(jīng)網(wǎng)絡(luò)通常由卷積層和稠密層組成。第一層卷積層的目的是，在輸入圖像的局部域內(nèi)發(fā)現(xiàn)共同模式后將其提取。卷積神經(jīng)網(wǎng)絡(luò)通過卷積過程學(xué)習(xí)輸入圖像的濾波，對圖像內(nèi)每個圖像定位進(jìn)行內(nèi)積運(yùn)算，輸出作為張量的結(jié)果。張量的深度就是濾波數(shù)量。

3.2. 圖形

假如圖形G是一個偶對，用公式可以表達(dá)為G= (V, E)，其中代表圖中頂點的V = {v1, ..., vn}，則代表圖中邊的E可以表達(dá)為E ? V × V。假設(shè)n是頂點的數(shù)目，m是邊的數(shù)目。每個圖形可以用一個大小為n ×n的鄰接矩陣A表示。如果有一條邊以頂點vi和頂點vj為端點，則A i,j = 1，否則Ai,j = 0。在這種情況下，我們可以稱頂點vi在A有一個定位i。而如果又是A i,j = 1，我們可以說vi和vj是鄰接的頂點。節(jié)點和邊的屬性都是有特性的，因為在一個圖形內(nèi)每個節(jié)點和邊都能獲取一個值。為了避免與圖論中的標(biāo)號概念混淆，我們用了屬性值這個術(shù)語，并沒有用標(biāo)識一說。鏈?zhǔn)菆D形中節(jié)點的序列，其中連續(xù)的節(jié)點剛好由一條邊連接起來。路是內(nèi)部節(jié)點互不相同的鏈。我們用公式d(u, v)代表u和v之間的距離，它也就代表著u和v之間最短路徑的長度。N1(v)代表一個節(jié)點的1-鄰域，也就是所有鄰接的節(jié)點。

標(biāo)識與節(jié)點劃分 PATCHY-SAN運(yùn)用圖形標(biāo)識讓節(jié)點形成順序。圖形標(biāo)識`表現(xiàn)為這樣一個函數(shù)： ` : V → S，其中V是頂點集合，S是一個有序的組合，比如一些實際數(shù)目和整數(shù)。圖形標(biāo)識過程會計算輸入圖的圖形標(biāo)識。在語境明確的時候，我們所說的標(biāo)識既是指圖形標(biāo)識，又是指計算圖形標(biāo)識的過程。一個排序（或著色）可以表達(dá)為這樣一個函數(shù)r : V → {1, ..., |V |}。僅限于`(u) > `(v)這種條件時，每個標(biāo)識都能導(dǎo)出一個排序，它可以用公式表達(dá)為r(u) < r(v)。如果圖形G的標(biāo)識是單射函數(shù)，它就能決定該圖形所有頂點的順序，以及G特有的鄰接矩陣A`(G)。在那個鄰接矩陣中，頂點v在A`(G)的定位是r(v) 。而且，每個圖形標(biāo)識都能導(dǎo)出一個頂點V上的節(jié)點劃分{V1, ..., Vn}，其中僅限于`(u) = `(v)這種條件時，它們的關(guān)系可以表達(dá)為公式u, v ∈ Vi。圖形標(biāo)識過程的實例是節(jié)點度，以及其他中心度的衡量指標(biāo)，都是網(wǎng)絡(luò)分析的常用指標(biāo)。例如，頂點v的中介中心度計算出穿越v的少數(shù)最短路徑。Weisfeiler-Lehman（WL）算法（Weisfeiler & Lehman，1968年；Douglas，2011年）是劃分某個圖形內(nèi)部頂點的一種過程。它也就是業(yè)內(nèi)所說的著色求精和樸素頂點分類。著色求精已經(jīng)引起WL研究人員極大的興趣，因為它能用來提高圖模型推理的速度（Kersting等人，2009年；2014年），還能用作計算圖核的方法（Shervashidze等人，2011年）。PATCHY-SAN應(yīng)用這些標(biāo)識過程和其他度量指標(biāo)（度、網(wǎng)頁排名、特征向量中心度等），讓圖形的節(jié)點形成一個順序，在依賴應(yīng)用的順序（時間、空間順序等）缺失時彌補(bǔ)空缺。

同構(gòu)與正則化 很多應(yīng)用程序域都存在判定兩個圖形是否同構(gòu)的計算問題。圖形同構(gòu)（GI）問題屬于NP（非確定性多項式問題），但尚未明確是P問題（能在多項式時間內(nèi)解決），還是NP難題。 在許多限制較緩和的情況下，GI屬于P問題。比如處理有界度的圖，GI就是P問題（Luks，1982年）。圖形G的正則化是有固定頂點順序的圖形G0，此圖與G同構(gòu)，體現(xiàn)了G的全部同構(gòu)類型。實際操作中，圖形正則化工具NAUTY展示了卓越的性能（McKay與Piperno，2014年）。

四、任意圖形的學(xué)習(xí)卷積神經(jīng)網(wǎng)絡(luò)

當(dāng)卷積神經(jīng)網(wǎng)絡(luò)用在圖像上時，一個感受域（一個方形格網(wǎng)）會以特定的幅度移動到每個圖像上方。感受域會讀取像素的特征值，每個頻道讀取一次，每個頻道會生成一批值。由于圖像的像素有隱性排列——空間順序，感受域總是從左到右、從上到下移動。而且，空間順序獨到地決定了每個感受域的節(jié)點，以及這些節(jié)點對向量空間表示的映射方式（見圖1（b））。因此，只有在像素的結(jié)構(gòu)角色（感受域內(nèi)的空間定位）相同時，用兩種不同感受域定位讀取的兩個像素的值才會分配給同一相對定位。

為展示卷積神經(jīng)網(wǎng)絡(luò)和PATCHY-SAN的聯(lián)系，我們將卷積神經(jīng)網(wǎng)絡(luò)框定在圖像上，以此辨認(rèn)在表現(xiàn)為方形格網(wǎng)圖的該圖像上有何節(jié)點序列，并以相同序列的各個節(jié)點構(gòu)建經(jīng)過正則化的鄰域圖——一個感受域。有的圖形集合缺失依賴應(yīng)用的節(jié)點順序，任意兩個圖形的節(jié)點位置也未能對準(zhǔn)。對這類圖形集合，我們需要判斷每個圖形(i)為創(chuàng)建鄰域的節(jié)點序列，以及(ii)一種從圖形表示到向量表示的獨特映射。在該向量表示中，那些在鄰域圖上結(jié)構(gòu)角色相同的節(jié)點定位也相同。

我們解決這些問題的對策是，運(yùn)用圖形標(biāo)識過程，將兩個不同圖形的節(jié)點分配給各自鄰接矩陣的同一相對定位，前提是這些節(jié)點在圖形內(nèi)的結(jié)構(gòu)角色相同。對給定的圖形集合，PATCHY-SAN（選擇組裝-正則化）對每個圖形都采用了以下步驟：(1)從圖形中挑選一個長度固定的節(jié)點序列；(2)對選中的序列，將其所有節(jié)點組裝為固定大小的鄰域；(3)將提取后的鄰域圖正則化；(4)對于由此得來的區(qū)域序列，通過卷積神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)鄰域表示。

接下來，我們會一一介紹解決上述問題的方法。

4.1. 節(jié)點序列選擇

 

算法1 SELNODESEQ: 選擇節(jié)點序列

選擇節(jié)點序列是面向各個輸入圖的辨識過程，其辨識的是構(gòu)建感受域的節(jié)點序列。算法1列舉了一個這樣的選擇過程。首先，根據(jù)給定的圖形標(biāo)識將輸入圖的頂點分類。接著，利用給定的卷積步長s遍歷，得到節(jié)點序列。對每個訪問過的節(jié)點，用算法3構(gòu)建感受域，直至感受域w全部構(gòu)建完畢。相對于選中的節(jié)點序列，卷積步長s決定了創(chuàng)建一個感受域時兩個連續(xù)節(jié)點的距離。如果節(jié)點的數(shù)目小于w，為了間隔考慮，該算法會構(gòu)建全零的感受域。挑選頂點序列可能有多種可選的方法。比如根據(jù)圖形標(biāo)識的值深度優(yōu)先遍歷輸入圖。我們將在今后的論文中探討這些方法。

4.2. 鄰域組裝

 

算法2：NEIGHASSEMB: 領(lǐng)域組裝

以上步驟辨識的每個節(jié)點都必須構(gòu)建一個感受域。算法3首先需要算法2組裝輸入節(jié)點的局部鄰域。鄰域的節(jié)點是感受域的候選集。算法2列舉鄰域組裝步驟。已知輸入一個節(jié)點v以及感受域的大小k，選擇過程會執(zhí)行廣度優(yōu)先搜索，以一個和節(jié)點v相距越來越遠(yuǎn)的距離探索頂點，并將這些頂點添加到一個N集上。如果集合的節(jié)點數(shù)目小于k，就會收集大部分新近添加到N的頂點1-鄰域，直到至少數(shù)目為k的頂點都已經(jīng)進(jìn)入N為止，或者直到再也沒有鄰域添加到N。請注意，在這種情況下，N的大小可能不等于k。

4.3. 圖像正則化

圖3：每個圖形都會執(zhí)行正則化，感應(yīng)到一個根節(jié)點v的鄰域上(紅色節(jié)點；節(jié)點顏色表示了到根節(jié)點的距離)。一個圖形標(biāo)簽用于對節(jié)點進(jìn)行評級，并創(chuàng)建正則化感受域，節(jié)點屬性之一的大小k (這里: k = 9) 和邊緣屬性之一的大小k × k 。正則化還包括過量節(jié)點和虛擬節(jié)點的填充。每個頂點（邊緣）屬性對應(yīng)一個帶有各自感受域的輸入通道。 

 

算法3：RECEPTIVEFIELD: 創(chuàng)建感受域

 

算法4：NORMALIZEGRAPH: 圖形正則化

對上一步組裝的鄰域進(jìn)行正則化，就可以構(gòu)建一個節(jié)點的感受域。如圖3所示，正則化賦予鄰域圖的節(jié)點一種順序，以便進(jìn)行從無序圖形空間到線性順序向量空間的映射?；驹O(shè)想是利用圖形標(biāo)識過程，即使是兩個不同圖形的節(jié)點，只要節(jié)點在圖形內(nèi)的結(jié)構(gòu)角色相同，就將它們分配給對應(yīng)鄰接矩陣相同的相對定位。為了實現(xiàn)這種設(shè)想，我們給優(yōu)化圖形正則化的問題下了定義，旨在尋找相對給定圖形集合而言最適合的標(biāo)識。

 

問題1（優(yōu)化圖形正則化）。在以下公式中，G是k個節(jié)點未標(biāo)識圖形的集合，l是一個單射圖形標(biāo)識過程，dG是有k個節(jié)點的圖形的距離度量，是k × k矩陣的距離度量，可以根據(jù)公式得出 。

 .

這里的問題可以歸結(jié)為，對于任意兩個從中隨機(jī)統(tǒng)一繪出的圖形，可以預(yù)計到圖形在向量空間的距離（有關(guān)基于l的鄰接矩陣），而圖形在圖形空間的距離又是最小的，找出一個圖形標(biāo)識過程l。優(yōu)化圖形正則化的問題是對典型的圖形規(guī)范化問題做一個總結(jié)。不過，典型標(biāo)識算法只針對同構(gòu)圖才有優(yōu)化效果，對那些可能相似但并非同構(gòu)的圖形，可能效果不佳。優(yōu)化正則化問題的預(yù)期值越低，標(biāo)識就能讓節(jié)點與相似的結(jié)構(gòu)角色匹配得越好。請注意，相似性是由dG決定的。

對于優(yōu)化正則問題的復(fù)雜性，我們得到以下結(jié)論：

推論1 優(yōu)化圖形正則化是NP難題。

證明方法：減少子圖同構(gòu)，PATCHY-SAN并未解決以上優(yōu)化問題，而是可能對比不同的圖形標(biāo)識方法，然后選擇對給定圖形集合而言最適合的方法。

推論2 在以下公式中，G是圖形集合，(G1, G0 1), ...,(GN , G0 N)是圖形對的序列，那些圖形來自G，是隨機(jī)且獨立的統(tǒng)一抽樣結(jié)果。

已知θ?` := PN i=1 dA A`(Gi), A`(G0 i) /N，并且θ` :=E G  dA A`(G), A`(G0) ? dG(G, G0) 。如果dA ≥ dG，只要θ`1 < θ`2，則EG[θ?`1] < EG[θ?`2]。

有了推論2，我們能以未經(jīng)監(jiān)督的方式，通過對相關(guān)估算的對比，比較不同的標(biāo)識過程。在dA ≥ dG的前提下， 的估算值越小，絕對差越小。因此，我們可以簡單選擇 最小的標(biāo)識。仍然以dA ≥ dG為前提舉例。編輯圖形距離和鄰接矩陣的漢明距離。最后要注意，所有上述演算結(jié)果都可以延用在有向圖上。

就本文主張的方法而言，其核心內(nèi)容就是圖形正則化問題，以及應(yīng)用局部圖形結(jié)構(gòu)正則化適合的圖形標(biāo)識過程。在PATCHY-SAN框架內(nèi)，我們進(jìn)行一個頂點v的鄰域圖正則化。頂點的標(biāo)識因此受限于v的圖形距離：對任意兩個頂點u和w，假如u比w更接近v，那么v的排名就始終高于w。這樣的界定能保證v始終排在第一位。在G中，一個頂點越靠近v，其在向量空間表示中的排名就越高。

大部分標(biāo)識方法都不是單射的，因此有必要打破同一標(biāo)識節(jié)點的聯(lián)系。為此，我們采用了NAUTY（McKay 與Piperno，2014年）。NAUTY將此前的節(jié)點劃分視為輸入，通過選擇按字典序最大的鄰接矩陣打破了現(xiàn)有的聯(lián)系。對有界度的圖來說，圖形同構(gòu)是在PTIME時刻（Luks，1982年）由于鄰域圖的大小恒定為k，此算法在多項式時間內(nèi)以原始圖大小運(yùn)行，平均線性時間為k（Babai等人，1980年）。我們的實驗證實，計算圖形鄰域的典型標(biāo)識增加的功耗微乎其微。

算法4列舉了正則化過程。如果輸入集U的大小超過k，該過程首先應(yīng)用在基于l的排名，以便選擇排名最高的那些k節(jié)點，并重新計算較小節(jié)點集的排名。如果U的大小不及k，該過程就增加不連通的偽節(jié)點。最后，它會導(dǎo)出頂點N的子圖，將以排名r作為此前著色的圖形規(guī)范化。

我們能按照下面的方法將PATCHY-SAN 結(jié)構(gòu)關(guān)聯(lián)到卷積神經(jīng)網(wǎng)絡(luò)上。

定理3. 給定一個圖形的像素序列。將 P大小為(2m – 1)2，幅度為s，沒有零填充，以及1-WL標(biāo)準(zhǔn)化感受域的ATCHY-SAN架構(gòu)應(yīng)用到上序列上，和大小為(2m – 1)，幅度為s，沒有零填充感受域的卷積神經(jīng)網(wǎng)絡(luò)第一層是一樣的。（相當(dāng)于固定序列感受域）

證據(jù)：有可能顯示出，如果一個輸入圖形是一個正方形網(wǎng)格，那么之后為頂點構(gòu)建的1-WL正則化感受域?qū)⑹冀K是一個按照獨特頂點順序，且有著獨特正方形網(wǎng)格圖形。

4.4. 卷積架構(gòu)

PATCHY-SAN能夠處理頂點和邊緣屬性（離散的和連續(xù)的）。設(shè)av是頂點屬性的數(shù)量，設(shè)ae是邊緣屬性的數(shù)量。對于每一個輸入圖形G，它都適用于頂點和邊緣，結(jié)果就是一個 (w, k, av) 和一個 (w, k, k, ae) 張量。這些可以被重塑到一個 (wk, av) 和一個(wk2, ae) 張量上。請注意，av 和ae 都是輸入渠道的數(shù)量。我們現(xiàn)在可以將大小設(shè)為k的跨越和感受域的1維卷積層應(yīng)用到第一個張量，把k2應(yīng)用到第二張量。其余的架構(gòu)可以被任意選擇。

我們可以使用合并層去整合分別代表節(jié)點和邊緣的卷積層。

五、復(fù)雜性和實現(xiàn)

 

圖4：在不同圖形上感受域的每秒處理速率

PATCHY-SAN創(chuàng)造感受域的算法效率非常高，而且也是原生并行化的，因為感受域是獨立生成的。我們可以展示以下漸近的最壞結(jié)果。

定理四.  把N設(shè)為圖形數(shù)量，把K設(shè)為感受域大小體積，把W設(shè)為寬度，還有O(f(n, m))函數(shù)化了為一個n個頂點和m個邊緣的圖形計算指定標(biāo)簽復(fù)雜度。對于計算N圖形的感受域來說，PATCHY-SAN有一個最差復(fù)雜度函數(shù)O(Nw(f(n, m) + nlog(n) + exp(k)))。

證明: 節(jié)點序列選擇需要每個輸入圖形的標(biāo)簽和k最高排名的節(jié)點檢索。對于正則化圖形補(bǔ)丁的創(chuàng)建，絕大多數(shù)計算工作都花費在了將標(biāo)簽過程應(yīng)用在一個大小可能比k大的鄰域上。將d設(shè)為輸入圖形G的最大度，將U設(shè)為由算法2返回的鄰域。我可以得到 |U| ≤ (k ? 2)d ≤ n. 函數(shù)exp(k)來自于在一個K節(jié)點圖形上最圖形正則化算法NAUTY最壞情況下的復(fù)雜度(Miyazaki, 1997)。

舉個例子，對于Weisfeiler-Lehman算法來說，它有一個O((n + m)log(n)) 復(fù)雜度 (Berkholz 等人, 2013)，還有常量w <n 和 k <n，PATCHY-SAN復(fù)雜度就是在N內(nèi)的線性化，以及在m和n中的非線性化。

六、實驗

我們進(jìn)行了三種類型的實驗：一個運(yùn)行分析，一個學(xué)習(xí)功能的定量（定性）分析，還有在基準(zhǔn)數(shù)據(jù)集上的圖形內(nèi)核比較。

6.1. 運(yùn)行分析

通過將PATCHY-SAN結(jié)構(gòu)應(yīng)用在真實世界的圖形中，我們評估了它的效率。目標(biāo)是對比感受域被生成的等級和最先進(jìn)的卷積神經(jīng)網(wǎng)絡(luò)表現(xiàn)的學(xué)習(xí)等級。所有輸入圖形都是Python模塊GRAPHTOOL1集合的一部分。對于一個指定圖形，通過利用標(biāo)準(zhǔn)化一維Weisfeiler-Lehman  (1-WL)算法，我們使用PATCHY-SAN結(jié)構(gòu)來計算所有節(jié)點的感受域(Douglas, 2011)。環(huán)面（torus）是一個帶有1萬個節(jié)點的周期性晶格；隨機(jī)（random）是一個帶有1萬個節(jié)點和一度分布P(k) ∝ 1/k and kmax = 3的隨機(jī)無向圖；電網(wǎng)（power）是一個美國地區(qū)電網(wǎng)拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)；polbooks是polbooks是關(guān)于2004年美國總統(tǒng)大選書籍的一個聯(lián)合購買網(wǎng)絡(luò)； 優(yōu)先（preferential）是一個優(yōu)先連接網(wǎng)絡(luò)模型，新加入的頂點有3度；astro-ph 是一個合著網(wǎng)絡(luò)，上面有很多來自提交天體物理論文預(yù)印本的平臺arvix的作者(Newman,2001);email-enron 是一個交流網(wǎng)絡(luò)是由近50萬封已發(fā)送的電子郵件生成的(Leskovec et al., 2009)。所有實驗都是在一個有64G RAM和2.8GHz獨立處理器的商用硬件上。

圖4描繪了感受域在每秒時間里是如何對每個輸入圖形進(jìn)行評級的。對于大小k = 5和k = 10的感受域，PATCHY-SAN 創(chuàng)建的域的評級速率超過1000/s，除了email-enron 的速率分別是600/s和320/s。 一個有2卷積和2致密層的卷積神經(jīng)網(wǎng)絡(luò)可以在同樣的機(jī)器上，以每秒200-400個訓(xùn)練樣子速率進(jìn)行學(xué)習(xí)。因此，感受域所產(chǎn)生的這個速率對于一個下游卷積神經(jīng)網(wǎng)絡(luò)而言完全足夠了。

圖5：受限玻爾茲曼機(jī)可視化功能可以和1維WL（大小為9的正則感受域），一個有線連接圖形（Barabasi & Albert ′ 1999, 左下），一個聯(lián)合采購政治書籍網(wǎng)絡(luò)(右上)，一個隨機(jī)圖形（右下）一起學(xué)習(xí)，這些帶有100個節(jié)點的圖形實例被描繪在左邊。一個功能可視化表現(xiàn)的權(quán)重（像素越暗，相應(yīng)的權(quán)重就會越高）和3個樣例圖形都取自受限玻爾茲曼機(jī)（通過設(shè)置除了隱藏節(jié)點相應(yīng)的全部功能為0）。在相鄰矩陣中，黃色節(jié)點已經(jīng)被有了位置1（建議看彩色圖形）

6.2. 功能可視化

可視化實驗的目標(biāo)，就是要定性調(diào)查無監(jiān)督特質(zhì)學(xué)習(xí)熱門模型，比如受限玻爾茲曼機(jī)(RBM) (Freund & Haussler, 1992) 是否能夠被整合到PATCHY-SAN 結(jié)構(gòu)里。對于每一個輸入圖形，我們已經(jīng)為所有階段生成了感受域，并把這些用于是受限玻爾茲曼機(jī)的輸入香。受限玻爾茲曼機(jī)有100個隱藏節(jié)點，結(jié)合對比分歧差異，它以0.01的學(xué)習(xí)速率被分成30個時期進(jìn)行訓(xùn)練。針對大小為9標(biāo)準(zhǔn)化感受域的1維Weisfeiler-Lehman算法(1-WL)，通過一個單層受限玻爾茲曼機(jī)，我們實現(xiàn)了功能可視化。值得注意的是，通過受限玻爾茲曼機(jī)學(xué)習(xí)的功能，相當(dāng)于感受域類型在發(fā)生。圖5描繪了部分功能和樣例，它們都是從四個不同圖形中抽取的。

6.3. 圖形分類

圖形分類是指將圖形分配到多個類型中的一個的問題。

 

表1: PATCHY-SAN架構(gòu)數(shù)據(jù)集合屬性和準(zhǔn)確度及時間結(jié)果（按秒），以及圖形內(nèi)核的四種狀態(tài)。

 

表2：在社交圖形上的準(zhǔn)確度比較結(jié)果

數(shù)據(jù)集。依靠先進(jìn)的圖形內(nèi)核，我們使用了六個標(biāo)準(zhǔn)基準(zhǔn)數(shù)據(jù)集來對于運(yùn)行時間和分類準(zhǔn)確度，它們分別是：MUTAG, PCT, NCI1, NCI109, PROTEIN, 以及D&D。 MUTAG (Debnath 等人, 1991) 是一個188硝基化合物數(shù)據(jù)集合，類別可以指出化合物對細(xì)菌的誘變效應(yīng)。PTC由344個化學(xué)化合物組成，類別可以指出雄性小白鼠和雌性小白虎的致癌性(Toivonen等人, 2003). NCI1和NCI109 是化學(xué)混合物，可以按照非小細(xì)胞肺癌和卵巢腫瘤細(xì)胞進(jìn)行篩選(Wale & Karypis, 2006). PROTEINS是一個圖形集合，節(jié)點是二級結(jié)構(gòu)元素，邊緣指示氨基酸序列里或是3D空間里的鄰域。Graphs可以按照酶或非酶被歸類。D&D是1178蛋白質(zhì)結(jié)構(gòu)的數(shù)據(jù)集(Dobson & Doig, 2003) ，可以按照酶和非酶被分類。

實驗設(shè)置. 我們比較了帶有最短路徑內(nèi)核（SP）的PATCHY-SAN結(jié)構(gòu)(Borgwardt & Kriegel, 2005)，隨機(jī)游走內(nèi)核 (RW) (Gaertner 等人., 2003)，圖形計數(shù)內(nèi)核 (GK) (Shervashidze 等人, 2009)，以及Weisfeiler-Lehman子樹內(nèi)核(WL) (Shervashidze 等人, 2011)。和之前的工作類似 (Yanardag & Vishwanathan, 2015), 我們把WL的高度參數(shù)設(shè)為2，GK的圖形體積大小設(shè)為7，然后從{10?6, 10?5, ..., 10?1}中為隨機(jī)游走內(nèi)核（RW）選擇選擇衰弱因子。我們利用LIB-SVM進(jìn)行了十倍交叉驗證(Chang &Lin, 2011)，使用九倍交叉驗證進(jìn)行培訓(xùn)，一倍用于測試，并且重復(fù)試驗了十次。我們匯報了平均預(yù)測準(zhǔn)確度和標(biāo)準(zhǔn)偏差。

對于PATCHY-SAN 結(jié)構(gòu)(也被稱為PSCN)來說，我們使用了1維WL正則化，一個寬度w等于節(jié)點平均值（見表1），感受域大小是k = 5和k = 10。對于試驗，我們只是有了節(jié)點屬性。此外，我們還在k=10的條件下進(jìn)行了試驗，我們使用了合并層(k = 10E),為節(jié)點和邊緣整合了感受域。為了做出一個較為公平的比較，我們使用了一個單一網(wǎng)絡(luò)架構(gòu)，它有兩個卷積層，一個致密隱藏層，以及針對所有試驗的softmax層。第一個卷積層有十六個輸出信道（特征映射）。第二個卷積層有八個輸出信道，一個大跨越到s = 1，域大小定為10。卷積層具有可調(diào)整的線性單元。致密層有128個可調(diào)整的線性單元，丟碼率為0.5。丟碼和神經(jīng)元的數(shù)量相對較少，需要避免過度擬合較小的數(shù)據(jù)集合。我們唯一優(yōu)化的超參數(shù)是針對迷你梯度下降算法RMSPROP的時期數(shù)量和批量大小，上面提到的所有這一切都是結(jié)合THEANO (Bergstra等人., 2010)和KERAS (Chollet, 2015)執(zhí)行的。同時在k = 10的批量處理中，我們還應(yīng)用了一個邏輯回歸（PSLR）分類器。

不僅如此，我們用同樣的設(shè)置2 在更大的社交圖形集合上進(jìn)行了實驗（每個集合最多有1.2萬個圖形，平均400個節(jié)點），根據(jù)之前圖形計數(shù)（GK）和深度圖形計數(shù)內(nèi)核（DGK）匯報的結(jié)果，我們和PATCHY-SAN進(jìn)行了比較(Yanardag & Vishwanathan, 2015)。我們使用了正則化節(jié)點度作為屬性，突出了其優(yōu)勢之一：它可以輕松地整合進(jìn)行連續(xù)功能。

結(jié)果. 表1列出了實驗結(jié)果。我們忽略了NCI109的結(jié)果，因為他們和NCI1的結(jié)果幾乎一模一樣。盡管使用了一個通用的卷積神經(jīng)網(wǎng)絡(luò)架構(gòu)，但是，現(xiàn)有圖形內(nèi)核的卷積神經(jīng)網(wǎng)絡(luò)的準(zhǔn)確度還是有很強(qiáng)競爭力的。在絕大多數(shù)情況下，一個感受域體積里的10個結(jié)果都被分到了最適合的類別里，分類準(zhǔn)確度也是最好的。相對較高的方差可以用小規(guī)模的基準(zhǔn)數(shù)據(jù)集合來解釋，事實上，卷積神經(jīng)網(wǎng)絡(luò)的超參數(shù)（時期和批量處理大小除外）無法調(diào)準(zhǔn)到個體數(shù)據(jù)集合。與圖形和文本數(shù)據(jù)的實驗相似，在處理大數(shù)據(jù)集合時，我們期望PATCHY-SAN能夠表現(xiàn)的比絕大多數(shù)大數(shù)據(jù)集合要更好。不僅如此，相比于絕大多數(shù)圖形內(nèi)核（WL），PATCHY-SAN的效率能夠提升2-8倍。對于海量圖形的數(shù)據(jù)集合，我們期待能夠獲得更加顯著的性能優(yōu)勢。中介度中心性正則化的結(jié)果，其實和運(yùn)行時間異常非常相似，大概只有10%的差異。邏輯回歸應(yīng)用在PATCHY-SAN的感受域上表現(xiàn)的不好，甚至更差，這說明PATCHY-SAN在和卷積神經(jīng)網(wǎng)絡(luò)一起使用的時候效果會很好，卷積神經(jīng)網(wǎng)絡(luò)可以學(xué)習(xí)非線性功能整合以及在各個感受域上分享權(quán)重。

在社交圖形數(shù)據(jù)上，PATCHY-SAN 同樣具有很強(qiáng)的競爭力。相比于其他六個數(shù)據(jù)集合中的四個雙內(nèi)核，它明顯更好，并且實現(xiàn)了其他數(shù)據(jù)集合的聯(lián)系。表2羅列了試驗的結(jié)果。

七、結(jié)論和未來工作

我們提出了一個學(xué)習(xí)圖形表現(xiàn)框架方法，當(dāng)和卷積神經(jīng)網(wǎng)絡(luò)連同協(xié)作時能發(fā)揮更大作用。它結(jié)合了兩個互補(bǔ)程序: (a) 選擇一個可以覆蓋圖形大部分區(qū)域的節(jié)點序列，以及(b) 對序列中的每個節(jié)點，生成本地標(biāo)準(zhǔn)化鄰域表現(xiàn)。實驗表明，這種方法在最先進(jìn)的圖形內(nèi)核狀態(tài)下是具有競爭力的。對于未來工作的方向，包括替代神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的使用，比如循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）；整合不同的感受域大?。唤Y(jié)合受限玻爾茲曼機(jī)(RBM)和自編碼器進(jìn)行訓(xùn)練；以及基于該方法理念的統(tǒng)計關(guān)系模型。

Via PDF

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。