本文要介紹的這一篇paper是icml2016上一篇關于 cnn 在圖（graph）上的應用。icml 是機器學習方面的頂級會議，這篇文章--<< learning cnns for graphs>>--所研究的内容也具有非常好的理論和實用的價值。如果您對于圖的資料結構并不是很熟悉建議您先參考本文末的相關基礎知識的介紹。
cnn已經在計算機視覺（cv）以及自然語言處理等領域取得了state-of-art 的水準，其中的資料可以被稱作是一種euclidean data，cnn正好能夠高效的處理這種資料結構，探索出其中所存在的特征表示。
圖1 歐氏（歐幾裡德）資料（euclidean data）舉例
所謂的歐氏（歐幾裡德）資料指的是類似于grids, sequences… 這樣的資料，例如圖像就可以看作是2d的grid資料，語音信号就可以看作是1d的grid資料。但是現實的處理問題當中還存在大量的 non-euclidean data，如社交多媒體網絡（social network）資料，化學成分（chemical compound）結構資料，生物基因蛋白（protein）資料以及知識圖譜（knowledge graphs）資料等等，這類的資料屬于圖結構的資料（graph-structured data）。cnn等神經網絡結構則并不能有效的處理這樣的資料。是以，這篇paper要解決的問題就是如何使用cnn高效的處理圖結構的資料。
圖2 graph 資料舉例
本文所提出算法思想很簡單，将一個圖結構的資料轉化為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來表示這個圖像并且建構一個正則化的鄰域圖（而這個鄰域圖就是卷積核的區域，也就是感覺野）。
圖3 圖像的卷積操作
按照這樣的方式來解釋，那麼如paper中figure1所示，一張4*4大小的圖像，實際上可以表示為一個具有4個nodes（圖中的1，2，3，4）的圖（graph），其中每一個node還包括一個和卷積核一樣大小的鄰域（neighborhood filed）。那麼，由此得到對于這種圖像（image）的卷積實際上就是對于這4個node組成的圖（graph）的領域的卷積。那麼，對于一個一般性的graph資料，同樣的隻需要選出其中的nodes，并且求解得到其相關的固定大小（和卷積核一樣大小）領域便可以使用cnn卷積得到圖的特征表示。
圖4 paper中的figure1
需要注意的是，圖4（b）當中表示的是（a）當中的一個node的鄰域，這個感覺野按照空間位置從左到右，從上到下的順序映射為一個和卷積核一樣大小的vector，然後再進行卷積。但是在一般的圖集當中，不存在圖像當中空間位置資訊。這也是處理圖資料過程當中要解決的一個問題。
基于以上的描述paper當中主要做了三個事情：1. 選出合适的nodes；2. 為每一個node建立一個鄰域；3. 建立graph表示到 vector表示的單一映射，保證具有相似的結構特征的node可以被映射到vector當中相近的位置。算法具體分為4個步驟：
首先對于輸入的一個graph，需要确定一個寬度w（定義于algorithm 1），它表示也就是要選擇的nodes的個數。其實也就是感覺野的個數（其實這裡也就是表明，每次卷積一個node的感覺野，卷積的stride= kernel size的）。那麼具體如何進行nodes的選擇勒？
實際上，paper當中說根據graph當中的node的排序label進行選擇，但是本文并沒有對如何排序有更多的介紹。主要采取的方法是：centrality，也就是中心化的方法，個人的了解為越處于中心位置的點越重要。這裡的中心位置不是空間上的概念，應該是度量一個點的關系中的重要性的概念，簡單的舉例說明。如圖5當中的兩個圖實際上表示的是同一個圖，對其中紅色标明的兩個不同的nodes我們來比較他們的中心位置關系。比較的過程當中，我們計算該node和其餘所有nodes的距離關系。我們假設相鄰的兩個node之間的距離都是1。
圖5 圖當中的兩個nodes
那麼對于圖5當中的左圖的紅色node，和它直接相連的node有4個，是以距離+4；再稍微遠一點的也就是和它相鄰點相鄰的有3個，距離+6;依次再相鄰的有3個+9；最後還剩下一個最遠的+4；是以我們知道該node的總的距離為23。同理我們得到右邊的node的距離為3+8+6+8=25。那麼很明顯node的選擇的時候左邊的node會被先選出來。
當然，這隻是一種node的排序和選擇的方法，其存在的問題也是非常明顯的。paper并沒有在這次的工作當中做詳細的說明。
接下來對選出來的每一個node确定一個感覺野receptive filed以便進行卷積操作。但是，在這之前，首先找到每一個node的鄰域區域（neighborhood filed），然後再從當中确定感覺野當中的nodes。假設感覺野的大小為k，那麼對于每一個node很明顯都會存在兩種情況：鄰域nodes不夠k個，或者是鄰域點多了。這個将在下面的章節進行講解。
圖6 neighborhood assemble結果
如圖選出的是6個nodes，對于每一個node，首先找到其直接相鄰的nodes（被稱作是1-neighborhood），如果還不夠再增加間接相鄰的nodes。那麼對于1-neighborhood就已經足夠的情況，先全部放在候選的區域當中，在下一步當中通過規範化來做最終的選擇。
假設上一步neighborhood assemble過程當中一個node得到一個領域nodes總共有n個。那麼n的個數可能和k不相等的。是以，normalize的過程就是要對他們打上排序标簽進行選擇，并且按照該順序映射到向量當中。
圖7 求解node的receptive filed
如果這個node的鄰域nodes的個數不足的話，直接全部選上，不夠補上啞節點（dummy nodes），但還是需要排序；如果數目n超過則需要按着排序截斷後面的節點。如圖7所示表示從選node到求解出receptive filed的整個過程。normalize進行排序之後就能夠映射到一個vector當中了。是以，這一步最重要的是對nodes進行排序。
圖8 normalize 過程
如圖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最右邊所示。
文章使用的是一個2層的卷積神經網絡，将輸入轉化為一個向量vector之後便可以用來進行卷積操作了。具體的操作如圖9所示。
圖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）的話如下右圖。
====================================分割線================================
本文作者：ai研習社