本文要介紹的這一篇paper是ICML2016上一篇關(guān)于 CNN 在圖（graph）上的應(yīng)用。ICML 是機(jī)器學(xué)習(xí)方面的頂級(jí)會(huì)議，這篇文章--<< Learning CNNs for Graphs>>--所研究的內(nèi)容也具有非常好的理論和實(shí)用的價(jià)值。如果您對(duì)于圖的數(shù)據(jù)結(jié)構(gòu)并不是很熟悉建議您先參考本文末的相關(guān)基礎(chǔ)知識(shí)的介紹。

CNN已經(jīng)在計(jì)算機(jī)視覺(jué)（CV）以及自然語(yǔ)言處理等領(lǐng)域取得了state-of-art 的水平，其中的數(shù)據(jù)可以被稱(chēng)作是一種Euclidean Data，CNN正好能夠高效的處理這種數(shù)據(jù)結(jié)構(gòu)，探索出其中所存在的特征表示。

所謂的歐氏（歐幾里德）數(shù)據(jù)指的是類(lèi)似于grids, sequences… 這樣的數(shù)據(jù)，例如圖像就可以看作是2D的grid數(shù)據(jù)，語(yǔ)音信號(hào)就可以看作是1D的grid數(shù)據(jù)。但是現(xiàn)實(shí)的處理問(wèn)題當(dāng)中還存在大量的 Non-Euclidean Data，如社交多媒體網(wǎng)絡(luò)（Social Network）數(shù)據(jù)，化學(xué)成分（Chemical Compound）結(jié)構(gòu)數(shù)據(jù)，生物基因蛋白（Protein）數(shù)據(jù)以及知識(shí)圖譜（Knowledge Graphs）數(shù)據(jù)等等，這類(lèi)的數(shù)據(jù)屬于圖結(jié)構(gòu)的數(shù)據(jù)（Graph-structured Data）。CNN等神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)則并不能有效的處理這樣的數(shù)據(jù)。因此，這篇paper要解決的問(wèn)題就是如何使用CNN高效的處理圖結(jié)構(gòu)的數(shù)據(jù)。

本文所提出算法思想很簡(jiǎn)單，將一個(gè)圖結(jié)構(gòu)的數(shù)據(jù)轉(zhuǎn)化為CNN能夠高效處理的結(jié)構(gòu)。處理的過(guò)程主要分為兩個(gè)步驟：1.從圖結(jié)構(gòu)當(dāng)中選出具有代表性的nodes序列；2.對(duì)于選出的每一個(gè)node求出一個(gè)卷積的鄰域（neighborhood field）。接下來(lái)我們?cè)敿?xì)的介紹算法相關(guān)的細(xì)節(jié)。

本paper將圖像（image）看作是一種特殊的圖（graph），即一種的grid graph，每一個(gè)像素就是graph當(dāng)中的一個(gè)node。那么我猜想文章的motivation主要來(lái)自于想將CNN在圖像上的應(yīng)用generalize 到一般的graph上面。

那么我們首先來(lái)看一下CNN在Image當(dāng)中的應(yīng)用。如圖3所示，左圖表示的是一張圖像在一個(gè)神經(jīng)網(wǎng)絡(luò)層當(dāng)中的卷機(jī)操作過(guò)程。最底部的那一層是輸入的特征圖（或原圖），通過(guò)一個(gè)卷積（這里表示的是一個(gè)3*3的卷積核，也就是文章當(dāng)中的receptive filed=9）操作，輸出一張卷積后的特征圖。如圖3 的卷積操作，底層的9個(gè)像素被加權(quán)映射到上層的一個(gè)像素；再看圖3中的右圖，表示從graph的角度來(lái)看左圖底層的輸入數(shù)據(jù)。其中任意一個(gè)帶卷積的區(qū)域都可以看作是一個(gè)中心點(diǎn)的node以及它的領(lǐng)域的nodes集合，最終加權(quán)映射為一個(gè)值。因此，底部的輸入特征圖可以看作是：在一個(gè)方形的grid 圖當(dāng)中確定一些列的nodes來(lái)表示這個(gè)圖像并且構(gòu)建一個(gè)正則化的鄰域圖（而這個(gè)鄰域圖就是卷積核的區(qū)域，也就是感知野）。

按照這樣的方式來(lái)解釋?zhuān)敲慈鏿aper中Figure1所示，一張4*4大小的圖像，實(shí)際上可以表示為一個(gè)具有4個(gè)nodes（圖中的1，2，3，4）的圖（graph），其中每一個(gè)node還包括一個(gè)和卷積核一樣大小的鄰域（neighborhood filed）。那么，由此得到對(duì)于這種圖像（image）的卷積實(shí)際上就是對(duì)于這4個(gè)node組成的圖（graph）的領(lǐng)域的卷積。那么，對(duì)于一個(gè)一般性的graph數(shù)據(jù)，同樣的只需要選出其中的nodes，并且求解得到其相關(guān)的固定大?。ê途矸e核一樣大?。╊I(lǐng)域便可以使用CNN卷積得到圖的特征表示。

需要注意的是，圖4（b）當(dāng)中表示的是（a）當(dāng)中的一個(gè)node的鄰域，這個(gè)感知野按照空間位置從左到右，從上到下的順序映射為一個(gè)和卷積核一樣大小的vector，然后再進(jìn)行卷積。但是在一般的圖集當(dāng)中，不存在圖像當(dāng)中空間位置信息。這也是處理圖數(shù)據(jù)過(guò)程當(dāng)中要解決的一個(gè)問(wèn)題。

基于以上的描述paper當(dāng)中主要做了三個(gè)事情：1. 選出合適的nodes；2. 為每一個(gè)node建立一個(gè)鄰域；3. 建立graph表示到 vector表示的單一映射，保證具有相似的結(jié)構(gòu)特征的node可以被映射到vector當(dāng)中相近的位置。算法具體分為4個(gè)步驟：

1. 圖當(dāng)中頂點(diǎn)的選擇Node Sequence Selection

首先對(duì)于輸入的一個(gè)Graph，需要確定一個(gè)寬度w（定義于Algorithm 1），它表示也就是要選擇的nodes的個(gè)數(shù)。其實(shí)也就是感知野的個(gè)數(shù)（其實(shí)這里也就是表明，每次卷積一個(gè)node的感知野，卷積的stride= kernel size的）。那么具體如何進(jìn)行nodes的選擇勒？

實(shí)際上，paper當(dāng)中說(shuō)根據(jù)graph當(dāng)中的node的排序label進(jìn)行選擇，但是本文并沒(méi)有對(duì)如何排序有更多的介紹。主要采取的方法是：centrality，也就是中心化的方法，個(gè)人的理解為越處于中心位置的點(diǎn)越重要。這里的中心位置不是空間上的概念，應(yīng)該是度量一個(gè)點(diǎn)的關(guān)系中的重要性的概念，簡(jiǎn)單的舉例說(shuō)明。如圖5當(dāng)中的兩個(gè)圖實(shí)際上表示的是同一個(gè)圖，對(duì)其中紅色標(biāo)明的兩個(gè)不同的nodes我們來(lái)比較他們的中心位置關(guān)系。比較的過(guò)程當(dāng)中，我們計(jì)算該node和其余所有nodes的距離關(guān)系。我們假設(shè)相鄰的兩個(gè)node之間的距離都是1。

那么對(duì)于圖5當(dāng)中的左圖的紅色node，和它直接相連的node有4個(gè)，因此距離+4；再稍微遠(yuǎn)一點(diǎn)的也就是和它相鄰點(diǎn)相鄰的有3個(gè)，距離+6;依次再相鄰的有3個(gè)+9；最后還剩下一個(gè)最遠(yuǎn)的+4；因此我們知道該node的總的距離為23。同理我們得到右邊的node的距離為3+8+6+8=25。那么很明顯node的選擇的時(shí)候左邊的node會(huì)被先選出來(lái)。

當(dāng)然，這只是一種node的排序和選擇的方法，其存在的問(wèn)題也是非常明顯的。Paper并沒(méi)有在這次的工作當(dāng)中做詳細(xì)的說(shuō)明。

2. 找到Node的領(lǐng)域Neighborhood Assembly

接下來(lái)對(duì)選出來(lái)的每一個(gè)node確定一個(gè)感知野receptive filed以便進(jìn)行卷積操作。但是，在這之前，首先找到每一個(gè)node的鄰域區(qū)域（neighborhood filed），然后再?gòu)漠?dāng)中確定感知野當(dāng)中的nodes。假設(shè)感知野的大小為k，那么對(duì)于每一個(gè)Node很明顯都會(huì)存在兩種情況：鄰域nodes不夠k個(gè)，或者是鄰域點(diǎn)多了。這個(gè)將在下面的章節(jié)進(jìn)行講解。

如圖選出的是6個(gè)nodes，對(duì)于每一個(gè)node，首先找到其直接相鄰的nodes（被稱(chēng)作是1-neighborhood），如果還不夠再增加間接相鄰的nodes。那么對(duì)于1-neighborhood就已經(jīng)足夠的情況，先全部放在候選的區(qū)域當(dāng)中，在下一步當(dāng)中通過(guò)規(guī)范化來(lái)做最終的選擇。

3. 圖規(guī)范化過(guò)程Graph Normalization

假設(shè)上一步Neighborhood Assemble過(guò)程當(dāng)中一個(gè)node得到一個(gè)領(lǐng)域nodes總共有N個(gè)。那么N的個(gè)數(shù)可能和k不相等的。因此，normalize的過(guò)程就是要對(duì)他們打上排序標(biāo)簽進(jìn)行選擇，并且按照該順序映射到向量當(dāng)中。

如果這個(gè)node的鄰域nodes的個(gè)數(shù)不足的話，直接全部選上，不夠補(bǔ)上啞節(jié)點(diǎn)（dummy nodes），但還是需要排序；如果數(shù)目N超過(guò)則需要按著排序截?cái)嗪竺娴墓?jié)點(diǎn)。如圖7所示表示從選node到求解出receptive filed的整個(gè)過(guò)程。Normalize進(jìn)行排序之后就能夠映射到一個(gè)vector當(dāng)中了。因此，這一步最重要的是對(duì)nodes進(jìn)行排序。

如圖8所示，表示對(duì)任意一個(gè)node求解它的receptive filed的過(guò)程。這里的卷積核的大小為4，因此最終要選出來(lái)4個(gè)node，包括這個(gè)node本身。因此，需要給這些nodes打上標(biāo)簽（labeling）。當(dāng)然存在很多的方式，那么怎樣的打標(biāo)簽方式才是最好的呢？如圖7所示，其實(shí)從這7個(gè)nodes當(dāng)中選出4個(gè)nodes會(huì)形成一個(gè)含有4個(gè)nodes的graph的集合。作者認(rèn)為：在某種標(biāo)簽下，隨機(jī)從集合當(dāng)中選擇兩個(gè)圖，計(jì)算他們?cè)趘ector空間的圖的距離和在graph空間圖的距離的差異的期望，如果這個(gè)期望越小那么就表明這個(gè)標(biāo)簽越好！具體的表示如下：

得到最好的標(biāo)簽之后，就能夠按著順序?qū)ode映射到一個(gè)有序的vector當(dāng)中，也就得到了這個(gè)node的receptive field，如圖最右邊所示。

4. 卷積網(wǎng)絡(luò)結(jié)構(gòu)Convolutional Architecture

文章使用的是一個(gè)2層的卷積神經(jīng)網(wǎng)絡(luò)，將輸入轉(zhuǎn)化為一個(gè)向量vector之后便可以用來(lái)進(jìn)行卷積操作了。具體的操作如圖9所示。

首先最底層的灰色塊為網(wǎng)絡(luò)的輸入，每一個(gè)塊表示的是一個(gè)node的感知野（receptive field）區(qū)域，也是前面求解得到的4個(gè)nodes。其中an表示的是每一個(gè)node的數(shù)據(jù)中的一個(gè)維度（node如果是彩色圖像那就是3維；如果是文字，可能是一個(gè)詞向量……這里表明數(shù)據(jù)的維度為n）。粉色的表示卷積核，核的大小為4，但是寬度要和數(shù)據(jù)維度一樣。因此，和每一個(gè)node卷季后得到一個(gè)值。卷積的步長(zhǎng)（stride）為4，表明每一次卷積1個(gè)node，stride=4下一次剛好跨到下一個(gè)node。（備注：paper 中Figure1 當(dāng)中，（a）當(dāng)中的stride=1，但是轉(zhuǎn)化為（b）當(dāng)中的結(jié)構(gòu)后stride=9）。卷積核的個(gè)數(shù)為M，表明卷積后得到的特征圖的通道數(shù)為M，因此最終得到的結(jié)果為V1……VM，也就是圖的特征表示。有了它便可以進(jìn)行分類(lèi)或者是回歸的任務(wù)了。

基礎(chǔ)問(wèn)題：

圖的基本概念：主要有頂點(diǎn)和邊構(gòu)成，存在一個(gè)鄰接矩陣A，如果對(duì)其中的nodes進(jìn)行特征表示（Feat）的話如下右圖。

本文轉(zhuǎn)自雷鋒網(wǎng)，如需轉(zhuǎn)載請(qǐng)至雷鋒網(wǎng)官網(wǎng)申請(qǐng)授權(quán)。