本文要介紹的這一篇paper是ICML2016上一篇關于 CNN 在圖（graph）上的應用。ICML 是機器學習方面的頂級會議，這篇文章--<< Learning CNNs for Graphs>>--所研究的內容也具有非常好的理論和實用的價值。如果您對于圖的數據結構并不是很熟悉建議您先參考本文末的相關基礎知識的介紹。

CNN已經在計算機視覺（CV）以及自然語言處理等領域取得了state-of-art 的水平，其中的數據可以被稱作是一種Euclidean Data，CNN正好能夠高效的處理這種數據結構，探索出其中所存在的特征表示。

所謂的歐氏（歐幾里德）數據指的是類似于grids, sequences… 這樣的數據，例如圖像就可以看作是2D的grid數據，語音信號就可以看作是1D的grid數據。但是現實的處理問題當中還存在大量的 Non-Euclidean Data，如社交多媒體網絡（Social Network）數據，化學成分（Chemical Compound）結構數據，生物基因蛋白（Protein）數據以及知識圖譜（Knowledge Graphs）數據等等，這類的數據屬于圖結構的數據（Graph-structured Data）。CNN等神經網絡結構則并不能有效的處理這樣的數據。因此，這篇paper要解決的問題就是如何使用CNN高效的處理圖結構的數據。

本文所提出算法思想很簡單，將一個圖結構的數據轉化為CNN能夠高效處理的結構。處理的過程主要分為兩個步驟：1.從圖結構當中選出具有代表性的nodes序列；2.對于選出的每一個node求出一個卷積的鄰域（neighborhood field）。接下來我們詳細的介紹算法相關的細節。

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

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

按照這樣的方式來解釋，那么如paper中Figure1所示，一張4*4大小的圖像，實際上可以表示為一個具有4個nodes（圖中的1，2，3，4）的圖（graph），其中每一個node還包括一個和卷積核一樣大小的鄰域（neighborhood filed）。那么，由此得到對于這種圖像（image）的卷積實際上就是對于這4個node組成的圖（graph）的領域的卷積。那么，對于一個一般性的graph數據，同樣的只需要選出其中的nodes，并且求解得到其相關的固定大小（和卷積核一樣大小）領域便可以使用CNN卷積得到圖的特征表示。

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

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

1. 圖當中頂點的選擇Node Sequence Selection

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

實際上，paper當中說根據graph當中的node的排序label進行選擇，但是本文并沒有對如何排序有更多的介紹。主要采取的方法是：centrality，也就是中心化的方法，個人的理解為越處于中心位置的點越重要。這里的中心位置不是空間上的概念，應該是度量一個點的關系中的重要性的概念，簡單的舉例說明。如圖5當中的兩個圖實際上表示的是同一個圖，對其中紅色標明的兩個不同的nodes我們來比較他們的中心位置關系。比較的過程當中，我們計算該node和其余所有nodes的距離關系。我們假設相鄰的兩個node之間的距離都是1。

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

當然，這只是一種node的排序和選擇的方法，其存在的問題也是非常明顯的。Paper并沒有在這次的工作當中做詳細的說明。

2. 找到Node的領域Neighborhood Assembly

接下來對選出來的每一個node確定一個感知野receptive filed以便進行卷積操作。但是，在這之前，首先找到每一個node的鄰域區域（neighborhood filed），然后再從當中確定感知野當中的nodes。假設感知野的大小為k，那么對于每一個Node很明顯都會存在兩種情況：鄰域nodes不夠k個，或者是鄰域點多了。這個將在下面的章節進行講解。

如圖選出的是6個nodes，對于每一個node，首先找到其直接相鄰的nodes（被稱作是1-neighborhood），如果還不夠再增加間接相鄰的nodes。那么對于1-neighborhood就已經足夠的情況，先全部放在候選的區域當中，在下一步當中通過規范化來做最終的選擇。

3. 圖規范化過程Graph Normalization

假設上一步Neighborhood Assemble過程當中一個node得到一個領域nodes總共有N個。那么N的個數可能和k不相等的。因此，normalize的過程就是要對他們打上排序標簽進行選擇，并且按照該順序映射到向量當中。

如果這個node的鄰域nodes的個數不足的話，直接全部選上，不夠補上啞節點（dummy nodes），但還是需要排序；如果數目N超過則需要按著排序截斷后面的節點。如圖7所示表示從選node到求解出receptive filed的整個過程。Normalize進行排序之后就能夠映射到一個vector當中了。因此，這一步最重要的是對nodes進行排序。

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

得到最好的標簽之后，就能夠按著順序將node映射到一個有序的vector當中，也就得到了這個node的receptive field，如圖6最右邊所示。

4. 卷積網絡結構Convolutional Architecture

文章使用的是一個2層的卷積神經網絡，將輸入轉化為一個向量vector之后便可以用來進行卷積操作了。具體的操作如圖9所示。

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

基礎問題：

圖的基本概念：主要有頂點和邊構成，存在一個鄰接矩陣A，如果對其中的nodes進行特征表示（Feat）的話如下右圖。