ICML論文 | 利用CNN來學習任意圖結構

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

論文摘要

許多重要問題可以劃歸到圖像數據學習框架里。我們針對學習卷積神經網絡提出了一個框架，可以適用于任何圖形。這些圖形可以是無向的，定向的，也可以是具有離散和連續節點和邊緣屬性。類似于基于圖形的卷積網絡，可以再本地化的可連接輸入區域上允許，我們提出了一種普遍方法，可以從圖形中提取本地化的可連接區域。使用既定的基準數據集，我們展示了帶有最先進圖形內核的學習功能表現，是具有競爭力的，同時，它們的計算效率也是非常高的。

一、概述

在這篇論文中，我們的目標是卷積神經網絡解決一大類基于圖形的學習問題。我們想到了以下兩個問題：

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

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

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

 

圖2. 建議架構的一個圖例通過一個圖形標記程序，從圖中選擇一個節點序列。對于序列中的一些節點，局部領域圖將會被拼裝且正則化。正則化的鄰域也將被用作感受域，并且和現有的卷積神經網絡組件進行整合。

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

圖1展示了卷積神經網絡識別圖像的局部連接感知域。

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

圖2展示了PATCHY-SAN結構。該結構在運用現有方式時有諸多優勢：

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

二、相關文獻

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

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

最近的論著拓展了卷積神經網絡的應用范圍，將它用在有別于低維度格網結構的拓撲學（Bruna等人，2014年；Henaff等人，2015年）。然而，所有這些方法都假定的是一個全球圖形結構，這即是說，不同輸入樣本的頂點是同一個匹配（Duvenaud等人，2015年），基于此在圖形上進行卷積類操作，開發某個圖形特征彼此不同的變量。

三、論文背景

我們在此簡要介紹了在卷積網絡和圖形理論方面所需的背景。

3.1. 卷積神經網絡

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

3.2. 圖形

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

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

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

四、任意圖形的學習卷積神經網絡

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

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

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

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

4.1. 節點序列選擇

 

算法1 SELNODESEQ: 選擇節點序列

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

4.2. 鄰域組裝

 

算法2：NEIGHASSEMB: 領域組裝

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

4.3. 圖像正則化

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

 

算法3：RECEPTIVEFIELD: 創建感受域

 

算法4：NORMALIZEGRAPH: 圖形正則化

對上一步組裝的鄰域進行正則化，就可以構建一個節點的感受域。如圖3所示，正則化賦予鄰域圖的節點一種順序，以便進行從無序圖形空間到線性順序向量空間的映射。基本設想是利用圖形標識過程，即使是兩個不同圖形的節點，只要節點在圖形內的結構角色相同，就將它們分配給對應鄰接矩陣相同的相對定位。為了實現這種設想，我們給優化圖形正則化的問題下了定義，旨在尋找相對給定圖形集合而言最適合的標識。

 

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

 .

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

對于優化正則問題的復雜性，我們得到以下結論：

推論1 優化圖形正則化是NP難題。

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

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

已知θ?` := 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，我們能以未經監督的方式，通過對相關估算的對比，比較不同的標識過程。在dA ≥ dG的前提下， 的估算值越小，絕對差越小。因此，我們可以簡單選擇 最小的標識。仍然以dA ≥ dG為前提舉例。編輯圖形距離和鄰接矩陣的漢明距離。最后要注意，所有上述演算結果都可以延用在有向圖上。

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

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

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

我們能按照下面的方法將PATCHY-SAN 結構關聯到卷積神經網絡上。

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

證據：有可能顯示出，如果一個輸入圖形是一個正方形網格，那么之后為頂點構建的1-WL正則化感受域將始終是一個按照獨特頂點順序，且有著獨特正方形網格圖形。

4.4. 卷積架構

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

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

五、復雜性和實現

 

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

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

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

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

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

六、實驗

我們進行了三種類型的實驗：一個運行分析，一個學習功能的定量（定性）分析，還有在基準數據集上的圖形內核比較。

6.1. 運行分析

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

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

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

6.2. 功能可視化

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

6.3. 圖形分類

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

 

表1: PATCHY-SAN架構數據集合屬性和準確度及時間結果（按秒），以及圖形內核的四種狀態。

 

表2：在社交圖形上的準確度比較結果

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

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

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

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

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

在社交圖形數據上，PATCHY-SAN 同樣具有很強的競爭力。相比于其他六個數據集合中的四個雙內核，它明顯更好，并且實現了其他數據集合的聯系。表2羅列了試驗的結果。

七、結論和未來工作

我們提出了一個學習圖形表現框架方法，當和卷積神經網絡連同協作時能發揮更大作用。它結合了兩個互補程序: (a) 選擇一個可以覆蓋圖形大部分區域的節點序列，以及(b) 對序列中的每個節點，生成本地標準化鄰域表現。實驗表明，這種方法在最先進的圖形內核狀態下是具有競爭力的。對于未來工作的方向，包括替代神經網絡結構的使用，比如循環神經網絡（RNN）；整合不同的感受域大小；結合受限玻爾茲曼機(RBM)和自編碼器進行訓練；以及基于該方法理念的統計關系模型。

Via PDF

雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。