用卷積神經網路處理 「圖」 結構數據應該怎麼辦？這篇文章告訴你答案

AI研習社按：本文作者彭偉，原文載於知乎專欄，AI研習社已獲授權。

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

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 個步驟：

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 圖當中的兩個 nodes

那麼對於圖 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 Neighborhood Assemble 結果

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

3. 圖規範化過程 Graph Normalization

假設上一步 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 最右邊所示。

4. 卷積網路結構 Convolutional Architecture

文章使用的是一個 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）的話如下右圖。

研習社特供福利ID：OKweiwu

TensorFlow & 神經網路演算法高級應用班

「TensorFlow & 神經網路演算法高級應用班」 開課啦！

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！