1.graph embedding（GE）

GE做的事情是將圖表示成為低維向量，類似與nlp將詞、句子等embedding。distributed representation的一體化過程，萬物皆可embedding。

• 將圖中的節點表示成低維、實值、稠密的向量形式，使得得到的向量形式可以在向量空間中具有表示以及推理的能力，這樣的向量可以用于下游的具體任務中。例如用戶社交網絡得到節點表示就是每個用戶的表示向量，再用于節點分類等；
• 將整個圖表示成低維、實值、稠密的向量形式，用來對整個圖結構進行分類；

在圖中最重要的兩個部分就是

• encoder：map到低維向量
• similarity function：如何度量相似度（什么樣的node的embedding應該相似？）

www-18有個很好的tutorial：Representation Learning on Networks[1]，可以參考

1.1.圖中學習的分類

• 歸納學習（Inductive Learning）：先從訓練樣本中學習到一定的模式，然后利用其對測試樣本進行預測（即首先從特殊到一般，然后再從一般到特殊），這類模型如常見的貝葉斯模型。在GAT中
• 轉導學習（Transductive Learning）：先觀察特定的訓練樣本，然后對特定的測試樣本做出預測（從特殊到特殊），這類模型如k近鄰、SVM等。在GAT中采用的是在Cora 數據集上優化網絡結構的超參數，應用到Citeseer 數據集

1.2.相似度度量方法

度量方式可以進行如下分類

• Adjacency-based Similarity：相鄰節點相似，能表征這兩個是否有連接

• Multi-hop Similarity：考慮k跳的neighbor

典型代表就是GraRep（Cao et al, 2015）和HOPE (Yan et al., 2016)了，一個考慮不同跳數分別訓練然后concatenate，一個考慮neighbor的重復程度。

• Random Walk Approaches：典型代表是deepwalk和node2vec，采用和nlp的相似方法，共現頻率來度量。
• GNN階段：neighborhood aggregation

neighborhood aggregate的方法可以對每個target node來刻畫以它為中心的計算圖，如

對于每一個node，都構成了一個計算圖，而且每個node的計算圖都有差別

我們可以看到GNN逐漸成形了，考慮簡單的aggregate方式可以表示成這個樣子

數學表示也十分清晰了，如下圖， 就是節點 的第 個時間步（或第 layer）的embedding

這就好家伙了，上圖中一些參數就可以generalize到一些unseen的點了，如下圖

這種能力稱之為inductive capability

早期邁向neural的過程借鑒了nlp的方法，如deepwalk[2]利用word2vec的方法，因為語料中詞語出現的次數與在圖上隨機游走節點被訪問到底的次數都服從冪律分布，采用隨機游走進行采樣出序列，然后按照word2vec的方法進行訓練。

word2vec出現在2013年，deepwalk 14年就出現了，緊隨其后。

后來來也出現了很多，如Line，node2vec，struc2vec，聽名字就知道，Line和node2vec是在描述圖像時刻畫節點的embedding，不過在游走的方式上進行探索，是DFS還是BFS還是both呢？到了struc2vec開始走節點空間結構的相似性這條路了。

其實這些已經跨入到neural的階段了，但是還用的比較初級，沒有專門為graph設計的neural的模型，探索階段。

2.Graph neural network

2.1.Graph convolutional network(GCN)[3][4]

2.1.1.引子：熱傳播模型

圖卷積是基于熱傳播模型，即兩個點之間熱傳播的速度和兩點之間溫度差值成正比，把這個熱傳播模型推廣到圖上就是信息傳播的速度關系[5]。

假設它當前的溫度為，在一個鏈條上的熱量傳播那么就有：

和單元的比熱容、質量有關是個常數。右邊第一項是下一個單元向本單元的熱量流入導致溫度升高，第二項是本單元向上一個單元的熱量流出導致溫度降低。這是一個二階差分，即二階導數。

而且是相同算子的二階導，在高緯空間中是所有非混合二階偏導數之和，稱為拉普拉斯算子。

其中 這個符號代表的是對各個坐標二階導數的加和，現在的主流寫法也可以寫作 。

在離散圖模型中是相似的，和鏈條熱傳播不同的是沒有了上一個和下一個單元，有的是該節點所有的鄰接節點（鄰接矩陣刻畫），所以同樣的方式刻畫為

其中 是這個圖的鄰接矩陣，即所有相鄰節點的流入流出關系加和構成了 這個節點溫度總的變化。

我們不妨用乘法分配律稍微對上式做一個推導：

即可以寫成這樣：

然后我們定義向量，那么就有：

其中被稱為度矩陣，只有對角線上有值，且這個值表示對應的頂點度的大小。整理整理，我們得到：

回顧剛才在連續歐氏空間的那個微分方程：

二者具有一樣的形式。這實際上是同一種變換在不同空間上的體現。 就是其中最簡單常用的圖上的拉普拉斯算子矩陣。

GCN的neighborhood aggregation

因為是熱傳播模型，流動的feature要流入每一個鄰接節點，所以加入了一個normalization，即節點的feature需要對所有neighbor取均值之后再進行流動。

2.1.2.熱傳播在graph上的求解：傅里葉變換

假設在圖中各個結點流動的東西不是熱量，而是特征（Feature），而是消息（Message），那么問題自然而然就被推廣到了GCN。所以GCN的實質是什么，是在一張Graph Network中特征（Feature）和消息（Message）中的流動和傳播。

由于很多東西在頻域上會更好解決，而且拉普拉斯矩陣與傅里葉不謀而合，所以頻域上解決的方案來做。先來推導下傅里葉變換和拉普拉斯算子的關系

關于傅里葉變換的理解，可參照我之前的博客[6]。所以，傅里葉變換就被推廣為時域信號與特定空間上拉普拉斯算子特征函數的積分。

理解下這個公式，實對稱矩陣的特征空間的所有基能夠張出整個線性空間且它們兩兩正交，所以無論是拉普拉斯算子 還是拉普拉斯矩陣 ，它們的特征空間是一個滿秩且基兩兩正交的空間，所以把歐氏空間的 推廣到圖空間的 的這一組特征向量。正是同一個關系（Message Passing），同一種變換，在不同空間下的體現。

現在我們已經得到了graph空間上的拉普拉斯算子 ，只需要對 求出其特征向量貌似就可以傅里葉變換了。等等，我們到底需要傅里葉變換干嘛？經過前面的鋪墊，傅里葉變換做了一個空間的變換，而這個空間里的卷積就非常絕-卷積定理卷積和乘積的變換。

在傳統的譜圖卷積下，由卷積定理：

函數卷積的傅里葉變換是函數傅里葉變換的乘積。具體分為時域卷積定理和頻域卷積定理，時域卷積定理即時域內的卷積對應頻域內的乘積；頻域卷積定理即頻域內的卷積對應時域內的乘積，兩者具有對偶關系。

時域卷積（時域內的卷積對應頻域內的乘積）如下：

為了更好理解，證明方法如下：

因此，卷積的傅里葉等于傅里葉的積。

做逆變換

所以現在傅里葉域做乘積，然后做傅里葉逆變換，等價于在原空間直接做卷積。

2.2.分析下graph neural中哪些東西可以做？

如以上分析，本質是圖上特征流動進行建模，然后利用傅里葉變換作為解決方案。

建模的方法還可以更加豐富，不一定流動速度非要和溫度查成正比，可以用更加復雜的模型，如神經網絡等來進行更加復雜的建模。

建模時也可以不是單純對相鄰節點的影響進行簡單的加和，在實際建模中，我們的Aggregate不一定是加和，可以把Aggregate推廣成各種操作例如Sum Pooling，例如LSTM，例如Attention

解決方案也是如此，不一定非要在傅里葉域做，傅里葉做的譜圖卷積，現在也可以直接在原空間域做卷積-Spatial Convolution，如DCNN[7]，GAT[8]等

2.3.損失函數

對于無監督的訓練，其實就和nlp的預訓練類似，訓練出embedding，訓練好之后再接下游任務。

對于有監督的訓練來說，如節點分類，一個比較簡單的方案就是對每個node的embedding接一個全連接層，就得到了一個損失函數

就是全連接層的權重。

3.GraphSAGE[9]：generalized aggregation方法

GCN是譜圖方法的代表，那么GraphSAGE就是非譜圖方法的代表。

如何進行更好的aggregate呢？

最后的這個黑盒里面可以裝的東西就多了，只要能把多個vector最后map到一個最終的vector就行

GraphSAGE則是將aggregate后的neighbor和本身的self-embedding這兩個concatenate到一起作為新的embedding，而不是傳統的把所有的embedding 加權求和，在原始論文中，作者提出這是一種很好的'skip connection'的方法。當然AGG也可以有很多變體，不一定非要是aggregate，也可以是pool，lstm等等。

4.Gated Graph Neural Networks[10]：go deeper with RNN

GCNs and GraphSAGE generally only 2-3 layers deep，因此對于每個node所構成的aggregate圖比較淺，如何走得更深呢？

可能會存在overfit或者梯度消失/爆炸，所以我們希望一個簡化可重用的模型，RNN！

每一層都使用相同的RNN單元，因為每個node 的neighbor的數量不同，所以先對所有neighbor做aggregate，我們稱之為“message”

就是節點v在step k的message

然后利用GRU對message和上一步狀態做處理得到新的狀態。

5.Graph level的embedding

直接把圖中所有node的embedding相加[11]

引入一個virtual node來代表graph，并用神經網絡進行訓練[12]

6.Graph attention network

利用attention在graph中動態確定和neighbor的權重，并利用mask只考慮鄰近的neighbor。

這篇文章用的attention與transfomer并不相同，只有一個突然formation matrix，而不是像attention中有q,k,v三個transformation

利用一個單層的全連接網絡來確定系數，將這兩個vector contatenate在一起輸入。然后進行softmax歸一化

即

同時還采用了multi-head attention的機制

得到歸一化的注意力系數后，使用歸一化的值計算對應特征的線性組合，作為每個頂點最后的輸出特征（最后可以加一個非線性層，σ）：

就是GAT輸出的節點i融合了鄰域信息的新特征

優點（摘自原文）

• 計算高效：self-attention層的操作可以在所有的邊上并行(所有邊上算出的注意力系數可以共享），輸出特征的計算可以在所有頂點上并行。沒有耗時的特征值分解。單個的GAT計算F ′個特征的時間復雜度可以壓縮至 （前面是算所有node的 的復雜度，后面是算所有邊注意力系數的），F是輸入的特征數，|V|和|E|是圖中頂點數和邊數。復雜度與Kipf & Welling, 2017的GCN差不多。multi-head 中單個head的計算完全獨立且可以并行化。
• 魯棒性更強：和GCN不同，本文的模型可以對同一個 neighborhood的node分配不同的重要性，使得模型的capacity大增。
• 注意力機制以一種共享的策略應用在圖的所有的邊上， 也是一種局部模型。在使用 GAT 時，無需訪問整個圖，而只需要訪問所關注節點的鄰節點即可，解決了之前提出的基于譜的方法的問題。因此這個方法有幾個影響：
• 圖不需要是無向的，可以處理有向圖（若 不存在，僅需忽略 即可）
• 可以直接應用到 inductive learning：包括在訓練過程中在完全未見過的圖上評估模型的任務上。
• GraphSAGE為每一個node都抽取一個固定尺寸的neighborhood，在計算的時候就不是所有的neighbor都能參與其中（不是所有都直接相連的neighbor都參與了aggregate嗎？）。此外，Hamilton的這個模型在使用基于LSTM的方法的時候假設了每個node的neighborhood的node一直存在著一個順序(RNN有輸入順序)。但是本文提出的方法就沒有這個問題，每次都可以將neighborhood所有的node都考慮進來，而且不需要事先假定一neighborhood的順序。

7.application example

如node classification和link prediction

在實際的運用中，可以運用在

• recommendation
• Computational biology
• Practical insights

8.彩蛋：卷積的含義

卷積又稱褶積，來源于數字信號的處理

卷積的形式可以分兩類：

連續形式：

離散形式：

先對g函數進行翻轉，然后再把g函數平移到n，然后滑動疊加，這就是卷積的過程。

我們可以考慮在原始的數字信號處理中，對于一個輸入信號 ，我們想要得到一個在特定時間下的輸出信號， 可以看成信號的衰減過程（單位沖擊響應函數）， 可以看成是想要得到輸出信號的時間。

比如以一天24h為例，我們希望得到一天結束時總的信號。在0時產生的信號 ，那么在24小時后衰減 ，在1時產生的信號為 ，那么這一天結束時衰減 ，以此類推，把每個時刻產生的信號以及到一天結尾時衰減程度相乘相加，就是所謂的卷積了，得到這一天結束時總的信號了。

那么對于圖片呢？

其實仍然是矩陣對應元素的相乘相加，只是矩陣 可以看成filter是翻轉了。

但是其實CNN中用的更確切應該稱為互關（co-relation），因為filter是沒有進行翻轉的，可以對比一下這兩者表達式的區別

co-relation:

convlution:

但是其實在CNN中不必那么嚴格的進行區分，學習一個翻轉前和翻轉后的filter并無不同，但是在數字信號處理中是不同的。

卷積擁有更多美好的性質，如交換律結合律等，在CNN中互關基本也都被稱為卷積了。而且當核對稱的時候，其實就完全一樣了。