· 摘要 ·
深度學習技術對歐式空間上的數據處理已經獲得了很大的成功，基於CNN或者RNN的方法能夠解決大多數場景下的圖像、文本任務。而另一類數據，非歐空間中的圖數據，其數據的複雜性對現有的機器學習算法提出了很大的挑戰。圖神經網絡是處理前述非歐空間數據的利器，目前在社交網絡分析、電商推薦、文本檢索等場景發揮著重要的作用。
本文將圍繞圖神經網絡的兩個典型方向：圖嵌入神經網絡及圖卷積神經網絡，通過對比不同時間點提出的圖神經網絡技術，簡要介紹圖神經網絡的發展歷程及其基本原理。
一、背景
圖神經網絡起初解決的都是諸如化合物分子結構分類等問題，面對的是嚴格意義上符合圖論中定義的圖類型的數據，即由若干頂點及頂點間的邊構成的非歐空間中的抽象網絡。
後來延伸到了歐式空間中，比如圖像或者是序列類型的文本數據，一些常見的如文本分類、圖片推薦等場景也可以轉換成圖，然後使用圖神經網絡技術來解決。來自論文[15]的插圖很好的體現了兩種數據的區別，如無特殊表明下文的圖均指圖論中定義的圖。
最早在2005年左右，圖神經網絡的概念就被提出來，直到2009年Franco在其論文[1]中定義了圖神經網絡的理論基礎。
2013年，Bruna在論文[2]中首次提出圖上的基於頻域和基於空域的卷積神經網絡，而後經過不斷的改進最終形成我們熟知的GCN。2014年，Perozzi等人提出了類似文本序列上word2vec[3]做法的DeepWalk[4]，在圖上優化頂點的分布式表達。在相近的時間點上，Bordes等人提出了在知識圖譜上訓練分布式表示的TransE[5]。
為了便於理解，後續將圖神經網絡簡單劃分為兩類進行介紹：圖嵌入方向、圖卷積網絡方向。圖嵌入神經網絡方面，簡要介紹了以DeepWalk為代表的，優化圖頂點間Embedding相似度的一類模型，而圖卷積神經網絡方向則更多介紹其基礎理論的推導過程。
二、圖嵌入網絡
圖嵌入技術一般通過特定的策略對圖中的頂點進行遊走採樣進而學習到圖中的頂點的相似性，可以看做是一種將圖的拓撲結構進行向量表示的方法。
然而現實世界中，圖中的頂點還包含若干的屬性信息，如社交網絡中的用戶畫像信息，引文網絡中的文本信息等，對於這類信息，基於圖嵌入的方法通常是將屬性特徵拼接到頂點向量中提供給後續任務使用。
1、DeepWalk
KDD 2014，DeepWalk[4]的思想類似Word2vec，利用圖中節點與節點間的共現關係，最終學習到節點的向量表示。
如上，在圖中的每個節點，基於深度優先（DFS）的隨機遊走採樣得到序列，將非歐空間中的拓撲圖結構映射到歐式空間中的序列。後面的就是常見的skip-gram方法，最大化共現概率，最終將圖中每個節點表示為一個稠密的向量。
下面是知乎基於這個方法的用戶聚類實驗結果：
▲ 知乎的用戶Embedding表示實踐
2、LINE
KDD 2015，LINE[6]與DeepWalk類似，都是基於鄰域相似訓練模型，最終也是使用稠密向量來表示圖中的節點。
不同的是，構造鄰域訓練樣本時，LINE可以認為是廣度優先（BFS）的。另外，對於頂點間的相似度，LINE提出了一種新的定義。
一階相似度，衡量的是兩個節點間的直連關係。若節點間存在連接，如上圖中節點6與節點7，則節點間的邊權
二階相似度，則是衡量兩個節點鄰居網絡結構相似的程度，如上圖中的節點5與節點6，兩者間不存在直連，但是其鄰居節點是大量重合的。LINE中對於每個節點維護了兩個向量，一個代表該節點本身，另一個是該節點作為其他節點的context時的表示向量，對於任意節點i，它的context實際上就是鄰居節點。
在這裡，定義節點i與其鄰居節點j間的context相似度為
3、Node2Vec
KDD 2016，Node2vec[7]可以認為是DeepWalk的一種擴展，結合了DFS和BFS的隨機遊走，可以把結構信息學習得更全面。
文中將節點在網絡中的呈現出的結構特徵劃分為兩種：①很多節點會聚集在一起，內部的連接遠比外部的連接多，稱之為社區，比如節點（u，s1，s2，s3，s4）；②網絡中兩個可能相聚很遠的點，在邊的連接上有著類似的特徵，比如節點（u，s6）。
假設要設計一個算法對網絡的表示進行學習，那麼必須滿足這兩點：①同一個社區內的節點表示相似，稱為同質性；②擁有類似結構特徵的節點表示相似，即結構相似性。
Node2Vec與DeepWalk的不同之處在於設計一套採樣的方法，通過跳轉概率對DFS和BFS的採樣方法進行調節，這樣就可以認為DeepWalk的隨機遊走是Node2Vec中採樣的一種特殊形式：
上圖中，對於一個隨機遊走，如果已經採樣了節點（t，v），那麼下一個要採樣的節點需要從集合
其中p為返回參數，q為出入參數；
對於返回參數p，假如取一個較大的值（p>max（q,1）），那麼採樣會儘量不往回走；如果取值較小（p<min（q,1）），那麼採樣會傾向於在起始點周圍轉來轉去；對於出入參數q，假如q>1，隨機遊走傾向於在起始點周圍的節點之間跑，反映節點的BFS特性；如果q<1，則傾向於往遠處跑，反映出DFS特性；當p=1，q=1時，即等同於DeepWalk中的隨機遊走。
下面是微信lookalike算法基於Node2Vec的實踐效果，社交相似度模型即Node2Vec，LIFT代表推薦廣告點擊量比值，提升2~3倍。
4、SDNE
KDD 2016，SDNE[8]可以認為是LINE的一種擴展，與LINE中的一階、二階相似度分開優化不同的是，在SDNE中藉助了自編碼器的結構同時對一階與二階相似度進行優化，也因此學習到的向量能夠兼顧局部和全局結構信息。
對於一階與二階相似度的聯合訓練，模型設計兩種方法：①一階相似度基於監督的方式訓練，保留局部信息；②二階相似度則用無監督的方式訓練，捕捉全局信息。需要注意上圖中的local與global應該互換，中間是Local代表局部信息，兩側才是Global。
可以看到，SDNE的模型是雙塔結構的，兩側輸入的是節點i與節點j的特徵，經過共享參數的多層MLP得到隱層向量
這裡自編碼器優化能夠理解為優化二階相似度，原因在於輸入
在阿里的湊單系統中，也有SDNE的應用：雙11預熱期間，在點擊和多樣性這兩個指標上，據公開表述說，點擊率提升了13%，做成實時化之後，在這個基礎上又提升了4%。內部多樣性指標直接翻了接近1倍。5、Struc2Vec
KDD 2017，Struc2Vec[9]與上述提到的模型不同，在一些場景中，兩個不是近鄰的頂點也可能擁有很高的相似性，而像上述基於相鄰節點構造一二階集合的模型無法捕捉到此類信息。
在這種場景下，Struc2Vec更傾向於捕捉那種節點間沒有直連邊，同時也不共享任何節點，但是兩個節點鄰居的空間結構相似的節點間信息，篇幅所限這裡不再展開。
6、EGES
阿里在KDD 2018上提出來的EGES[10]則是在DeepWalk的基礎上加入對冷啟動商品的處理，稱為side information。做法上對用戶的行為歷史構建商品圖，基於經驗對用戶歷史行為信息按小時進行分割，同時統計共現次數作為邊權以及後續的噪音去除等。
為了解決冷啟動問題增加的Side Informatio，在電商場景中可以指一個商品的類別、商店、價格等，例如，優衣庫（同一家店）的兩個連帽衫（同一類別）可能看起來很相似，喜歡尼康鏡頭的人也可能對佳能相機（類似類別和類似品牌）感興趣。這意味著具有相似邊信息的節點在空間上應該靠近。
左圖即為EGES的模型結構，其中
三、圖卷積網絡
圖卷積網絡與前面提到的圖嵌入方式不同，一般直接進行分類或者回歸。與一般的深度學習方法類似的，也可以使用圖嵌入的方式先進行預訓練，基於訓練好的節點向量再進行圖卷積神經網絡的優化。同樣的，圖卷積的方法很多時候也會附帶的產生節點的向量表示。
一般來說，圖卷積神經網絡分為兩大類，一種是譜圖卷積（Spectral），在傅立葉域進行卷積變換。另一種是非譜圖卷積（Non-Spectral），也叫空間域卷積，直接在圖上進行卷積。
1、Spectral CNN
在ICLR 2014上提出的Spectral CNN[2]，也稱為第一代的圖卷積網絡，最早提出將CNN擴展到圖上，直接處理圖類型的數據而不需要對圖類型的數據進行轉化。文章中，作者提出了兩種方式構建圖卷積神經網絡：空域構建（Spatial Construction）和頻域構建（Spectral Construction）。
在此之前，我們先回顧一下CNN的的特點，CNN一般作用在歐式空間上，具有：①權重共享，即同一個卷積核可以作用於不同的位置；②局部性，卷積核的大小一般遠小於輸入特徵的大小；③多尺度，層層堆疊的卷積核在減少參數量的同時獲得更大的感受野。
1）Spatial Construction
基於空域的方法主要實現了局部性和多尺度，但卷積核的權重並不能做到共享。假設存在有權無向圖
如上，我們定義節點
對上式擴展，假設節點特徵
其中
，
在CNN中，圖像卷積後可以通過pooling操作減少特徵尺寸，為後續的卷積操作擴大感受野，而在非歐的圖上，論文中基於圖的多尺度聚類實現了類似pooling的操作，感興趣的讀者可以直接看論文中的介紹，這裡就不展開了。
總結上述，在圖卷積層數為
其中
2）Spectral Construction
與基於空域的方法不同，直接在空域上進行卷積比較困難，因此基於頻域的方法則是根據卷積定理：在時域（空域）上的卷積，等於在頻域上相乘。這樣將圖轉化到另一個空間上來處理，即：
那麼，對於圖的卷積就可以通過構建拉普拉斯矩陣來找到一組傅立葉變換的基，從而將圖從空域轉到這組基所代表的頻域空間上進行計算：
如上圖，定義度數矩陣（Degree Matrix）：
，其中
鄰接矩陣（Adjacency Matrix）：
，即節點相連則為1，反之則為0；
那麼拉普拉斯矩陣可以用度數矩陣與鄰接矩陣來表示：
其中，特徵向量
由此，就可以根據這組傅立葉變換的基，將圖的卷積從空域轉到頻域：
（因為離散積分實質上是一種內積形式，定義到圖上的傅立葉變換就是對特徵向量的內積。）
上式中，
與前面類似的，加入激活函數後，第
將頻域的解法與空域解法對比，可以發現這裡的卷積核實現了參數共享，但是也存在另一個問題，頻域解法上的卷積核實際上不存在局部連接性，在第一層可以認為圖上的所有節點做了卷積加和。
2、ChebNet
第二代的圖卷積神經網絡一般被認為是在NIPS 2016提出來的ChebNet[11]。作者指出原始頻譜圖卷積的缺點：①圖卷積核不具有局部連接性；②圖卷積核的參數量與圖中節點數相同，參數量太大；③圖卷積涉及到特徵分解等運算，計算複雜度高，並針對這些問題提出了改進的方法。
對於原始的頻域卷積，假設無向圖
，其中
歸一化拉普拉斯矩陣可得：
，
對矩陣
其中為特徵向量，為特徵值，那麼圖上的卷積可以定義為：
，中間的符號代表哈達瑪積
因此，卷積核對特徵的圖卷積即為：
我們把上式寫成更加一般的形式：
到這裡可以發現，在深度學習中需要設計的就是函數
為了解決前面提到的問題，論文中首先用多項式展開
其中，
後面繼續使用切比雪夫多項式作近似，將計算複雜度降低至
其中
到這裡，就無需再做矩陣的特徵分解，最大特徵值也可以利用冪迭代法求出。另外切比雪夫多項式的運算實際上是固定的，可以在預處理中完成，極大的減少了計算複雜度。
3、GCN
ICLR 2017提出的第三代圖卷積神經網絡GCN[12]，也就是最常見的圖卷積神經網絡的形式，可以認為是對切比雪夫網絡的再近似。切比雪夫圖卷積可以表示為以下形式：
令多項式的階數
這樣實際上還存在兩個參數，即
由於
其中
推廣到多維的輸入特徵
其中
到這裡可以看到，論文中的GCN就是一階的切比雪夫卷積，但是參數量更少，複雜度低。卷積的感受野只覆蓋了一階鄰居，不過可以通過堆疊多層卷積來達到擴大感受野的效果。
最後論文中給出來一個非常有意思的數據，只用隨機初始化參數的GCN在實驗中就能表現出不錯的結果，相比較CNN如果不經過訓練基本得不到什麼有效特徵。
在上圖可以看到，不經訓練的節點embedidng特徵在空間中已經自動聚類了。
四、小結
本文將圖神經網絡技術簡單分為兩類：圖嵌入方法與圖卷積方法，分別介紹了兩種圖神經網絡技術的原理及應用。
圖嵌入神經網絡一般通過特定的策略遊走採樣，最終得到圖頂點間的相似性表達，在社交網絡的廣告推薦場景及電商的湊單場景都有典型的應用，如EGES等。
圖卷積神經網絡技術則更傾向於直接進行分類，本文著重介紹了圖卷積方法的發展及推導方法，工業上也有如Graphsage[13]、Pinsage[14]等方法處理圖片的推薦問題，最終也能以類似圖嵌入的方式得到頂點間的相似度。
參考文獻
[1]Scarselli, F.，Gori, M.，Ah Chung Tsoi，Hagenbuchner, M.，Monfardini, G.，2009，The Graph Neural Network Model
[2]Bruna, Joan，Zaremba, Wojciech，Szlam, Arthur，LeCun, Yann，2013，Spectral Networks and Locally Connected Networks on Graphs
[3]Le, Quoc V，Mikolov, Tomas，2014，Distributed Representations of Sentences and Documents
[4]Perozzi, Bryan，Al-Rfou, Rami，Skiena, Steven，2014，DeepWalk: Online Learning of Social Representations
[5]Antoine Bordes，Nicolas Usunier，Alberto Garcia-Duran，Jason Weston，Oksana Yakhnenko，2013，Translating Embeddings for Modeling Multi-relational Data
[6]Jian Tang，Meng Qu，Mingzhe Wang，Ming Zhang，Qiaozhu Mei，2015，LINE: Large-scale Information Network Embedding
[7]Aditya Grover，Jure Leskovec，2016，node2vec: Scalable Feature Learning for Networks
[8]Daixin Wang，Peng Cui，Wenwu Zhu，2016，Structural Deep Network Embedding
[9]Ribeiro, Leonardo F. R，Savarese, Pedro H. P，Figueiredo, Daniel R，2017，struc2vec: Learning Node Representations from Structural Identity
[10]Wang, Jizhe，Huang, Pipei，Zhao, Huan，Zhang, Zhibo，Zhao, Binqiang，Lee, Dik Lun，2018，Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba
[11]Michal Defferrard，Xavier Bresson，Pierre Vandergheynst，2016，Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
[12]Kipf, Thomas N.，Welling, Max，2017，Semi-Supervised Classification with Graph Convolutional Networks
[13]Hamilton, William L，Ying, Rex，Leskovec, Jure，2017，Inductive Representation Learning on Large Graphs
[14]Ying, Rex，He, Ruining，Chen, Kaifeng，Eksombatchai, Pong，Hamilton, William L，Leskovec, Jure，2018，Graph Convolutional Neural Networks for Web-Scale Recommender Systems
[15]Zhou, Jie，Cui, Ganqu，Zhang, Zhengyan，Yang, Cheng，Liu, Zhiyuan，Wang, Lifeng，Li, Changcheng，Sun, Maosong，2019，Graph Neural Networks: A Review of Methods and Applications