機器之心原創

作者：朱梓豪

編輯：Qing Lin

如果說 2019 年機器學習領域什麼方向最火，那麼必然有圖神經網絡的一席之地。其實早在很多年前，圖神經網絡就以圖嵌入、圖表示學習、網絡嵌入等别名呈現出來，其實所有的這些方法本質上都是作用在圖上的機器學習。本文将根據近兩年的綜述對圖網絡方法做一個總結，為初入圖世界的讀者提供一個總體的概覽。

本文作者朱梓豪為中科院信工所在讀碩士，主要研究方向為圖神經網絡、視覺問答、視覺對話等。

什麼是圖

圖是一種常見的數據結構，用于表示對象及其之間的關系。其中，對象又稱節點（node）或頂點（vertex），關系用邊（edge）來描述。在數學上一般用 G=(V,E,A,X) 來表示，其中 V={v1,v2……,vn} 是節點集合，E=e_ij 表示邊的集合，A 是大小為|V|×|V|的鄰接矩陣，用于表示節點之間的連接關系，如果 e_ij∈E，則 A_ij=1，X 是大小為|V|×d 的特征矩陣，X 的第 i 行 X_i:表示第 i 個節點的屬性特征，其中 d 是屬性的維度。

為何需要在圖上應用機器學習方法

圖一

node2vec 通過改變生成随機遊走序列的方式改進了 DeepWalk 算法。DeepWalk 是按照均勻分布随機選取随機遊走序列的下一個節點。node2vec 同時考慮了廣度優先搜索 (BFS) 和深度優先搜索 (DFS)。Grover 等發現，廣度優先搜索注重刻畫網絡中的局部特征，而深度優先搜索能更好地遍曆整個網絡，反映了節點間的同質性。特别地，node2vec 引入 search bias 函數來平衡這兩種采樣方式，通過參數 p 和 q 來調整下一步的跳轉概率。

其他基于随機遊走的方法還包括 Walklets、LsNet2vec、TriDNR、HARP、DDRW 等等。

基于神經網絡的圖嵌入（圖神經網絡）

還有一類方法是将神經網絡和圖結合起來的圖表示學習方法，也是最近一年來最火的方向之一，我們統稱為圖神經網絡。機器之心已經為其做過了全面的介紹，具體請參見：深度學習時代的圖模型，

清華發文綜述圖網絡、清華大學圖神經網絡綜述：模型與應用、圖神經網絡概述第三彈：來自 IEEE Fellow 的 GNN 綜述。主要将其分為圖卷積網絡、圖注意力網絡、圖生産網絡、圖時空網絡、圖自編碼器。又可以分為基于譜的方法和基于空間的方法。由于基于譜的方法需要分解矩陣特征向量，因此絕大多數新提出的方法都是基于空間，也就是如何傳播并聚合節點和邊的信息。圖像和文本本質上是有規則的格栅結構的圖，因此，很自然想到可以将已經在 CV、NLP 領域成功應用的模型拓展到圖上，如詞向量和圖卷積。最近，也出現了基于膠囊的圖神經網絡和基于圖像語義分割 U-Net 模型的 Graph U-Net。

注意力機制的在圖嵌入的應用

有一部分研究者将注意力 (attention) 機制引入到了圖神經網絡中。注意力機制的本質是從人類視覺注意力機制中獲得靈感。大緻是我們視覺在感知東西的時候，一般不會是一個場景從到頭看到尾全部都看，而是根據需求觀察特定的一部分。這意味着，當人們注意到某個目标或某個場景時，該目标内部以及該場景内每一處空間位置上的注意力分布是不一樣的。而且當我們發現一個場景經常在某部分出現自己想觀察的東西時，我們就會進行學習在将來再出現類似場景時把注意力放到該部分上。更通用的解釋就是，注意力機制是根據當前的某個狀态，從已有的大量信息中選擇性的關注部分信息的方法，其實就是一系列 注意力分配系數。

基于注意力機制的 GNN 的思想是在計算每個節點的表示的時候，首先計算其和鄰居節點之間的注意力系數，為重要的鄰居節點分配較大的權重，在聚合的過程中将不同的重要性分配給鄰域内不同的節點。

表 1 按照輸入、輸出、任務對近兩年發表的基于注意力機制的圖神經網絡模型進行彙總比較，下面對幾個具有代表性的模型進行概述，具體内容請參照論文《Attention Models in Graphs: A Survey》[9]。

Yoshua Bengio 的 MILA 團隊在 2018 年提出了圖注意力網絡 (Graph Attention Networks, GAT)[10]，論文中定義了 Graph attention 層，通過疊加不同的 attention 層，可以組成任意結構的圖神經網絡，其架構如圖所示，最終要的步驟就是計算節點 i 的鄰居節點對其的注意力系數$\alpha_{ij}$, 這裡還是用了多頭注意力機制，圖中不同的顔色代表不同的頭。

不同于 GAT 是節點分類，DAGCN[11] 用于圖分類任務。模型中包括兩個 attention 單元，一個是和 GAT 一樣，用于圖卷積得到節點的表示，另一個是基于 attention 的池化操作，得到整個圖的表示，然後将圖表示輸入到一個 MLP 得到整個圖的分類。作者認為，經典的 GCN 每一層都隻能捕獲第 k-hop 鄰域的結構信息，隻有最後一層的 H 被用下一步的預測，随着網絡層數的增多，會丢失大量的信息。作者提出的 attention 層的思想是不僅要依賴于第 k-hop 的結果, 還要從前面每一個 hop 捕獲有價值的信息。

綜合各種圖注意力網絡的論文來看，最主要的區别在于如何定義和實現注意力機制。第一類是學習 attention weights：

主要是通過 softmax 函數實現的，同時還需要一個基于節點屬性可訓練的計算節點 j 和節點 0 相關性的函數，例如 GAT 的實現方式為：

其中 W 是将節點屬性映射到隐空間的可訓練的參數矩陣，||表示串接。

第二類基于相似度的 attention，同樣，給定相應的屬性或特征，第二種注意力的學習方法與上面的方法類似，但有一個關鍵的區别是更多的注意力集中在具有更多相似隐藏表示或特征的節點上，這在文獻中也經常被稱為對齊。以 AGNN 中的公式為例：

其中 cos 來計算餘弦相似度，可以看到和上式非常相似。不同之處在于，模型顯式地為彼此相關的對象學習類似的隐藏嵌入，因為注意力是基于相似性或對齊的。

前兩種注意力主要集中在選擇相關信息以整合到目标對象的隐藏表示中，而第三種注意力的目的略有不同，叫做基于注意力的遊走。舉例來說，在一個輸入圖上執行一系列遊走，并使用 RNN 對訪問的節點信息進行編碼，從而構造一個子圖嵌入。RNN 的 t 時刻的隐藏狀态對 1 到 t 訪問的節點進行編碼。Attention 就是一個函數$f』(h_t)=r_{t 1}$, 輸入的是 t 時刻的隐藏狀态，輸出一個 rank vector，告訴我們下一步我們應該優先考慮哪種類型的節點。

框架

這裡簡單的介紹一下 Hamilton 在論文 [1] 中提出的一種圖嵌入 encoder-decoder 框架（如圖），可以将大多數的圖嵌入方法用這個框架來表示。在這個框架中，我們圍繞兩個關鍵的映射函數組織了各種方法：一個 encoder(它将每個節點映射到一個低維向量) 和一個 decoder(它從已知的嵌入中解碼關于圖的結構信息)。encoder-decoder 背後的直覺想法是這樣的:如果我們能從低位嵌入表示中學會解碼高維圖信息，如節點在圖中的全局位置或節點的局部鄰域結構，那麼原則上，這些嵌入應包含下遊機器學習任務所需的所有信息。

encoder 是一個函數：

将節點 i 映射到嵌入向量$z_i \in R^d$。decoder 是接受一組節點嵌入并從這些嵌入中解碼用戶指定的圖統計數據的函數。例如，decoder 可能根據節點的嵌入預測節點之間是否存在邊，或者可能預測圖中節點所屬的社區。原則上，有許多 decoder 都是可以使用的，但是在大多數工作中使用的是成對 decoder：

當我們将成對 decoder 應用于一對嵌入$(z_i,z_j)$時，我們得到了原始圖中$v_i$和$v_j$之間相似性的重構，目标就是最小化重構後的相似性和原圖中相似性的誤差：

其中其中 SG 是一個用戶定義的、在圖 G 上的的節點間相似性度量。換句話說，目标是優化 encoder-decoder 模型，可以從低維節點嵌入 z_i 和 z_j 中解碼出原始圖中 SG(v_i, v_j) 成對節點相似性。例如可以設 SG(v_i, v_j)=A_{ij}，如果節點相鄰則定義節點的相似度為 1，否則為 0。或者可以根據在圖 G 上的固定長度随機遊走 v_i 和 v_j 共線的概率來定義 SG。在實踐中，大多數方法通過最小化節點對集合 D 上的經驗損失 L 來實現重構目标：

優化了上述目标函數後，我們就可以使用經過訓練的 encoder 為節點生成嵌入，然後可以将其用作下遊機器學習任務的特征輸入。下表展示了常用圖嵌入方法的 encoder-decoder 框架描述。

總結

圖嵌入是指将圖中節點用低維稠密向量來表示，從一開始的基于矩陣分解的方法逐漸出現了基于随機遊走的方法，後來又演化出基于神經網絡的方法也是我們經常聽到的圖神經網絡。圖嵌入目前還面臨着一些挑戰，例如如何在超大規模圖上高效進行分析，如何應對真實世界中不斷變化的動态圖，如何對圖神經網絡的黑盒模型進行解釋，以及如何建模異質圖。目前在圖網絡領域也湧現出一些新的方向，例如如何針對圖網絡進行對抗攻擊使其模型性能大幅下降，相反的就是如何提高模型的魯棒性；如何将人工設計網絡架構轉變為由機器自動設計，這對應着網絡結構搜索問題（NAS），以及如何将圖網絡和計算機視覺、自然語言處理等方向結合起來。這些都是很有價值也有意思的方向，感興趣的讀者可以進行更深度的研究。

參考文獻：

[1] Hamilton, William L., Rex Ying, and Jure Leskovec. "Representation learning on graphs: Methods and applications." arXiv preprint arXiv:1709.05584 (2017).

[2] Goyal, Palash, and Emilio Ferrara. "Graph embedding techniques, applications, and performance: A survey." Knowledge-Based Systems 151 (2018): 78-94.

[3] Roweis, Sam T., and Lawrence K. Saul. "Nonlinear dimensionality reduction by locally linear embedding." science 290.5500 (2000): 2323-2326.

[4] Belkin, Mikhail, and Partha Niyogi. "Laplacian eigenmaps and spectral techniques for embedding and clustering." Advances in neural information processing systems. 2002.

[5] Shaw, Blake, and Tony Jebara. "Structure preserving embedding." Proceedings of the 26th Annual International Conference on Machine Learning. ACM, 2009.

[6] Cao, Shaosheng, Wei Lu, and Qiongkai Xu. "Grarep: Learning graph representations with global structural information." Proceedings of the 24th ACM international on conference on information and knowledge management. ACM, 2015.

[7] Perozzi, Bryan, Rami Al-Rfou, and Steven Skiena. "Deepwalk: Online learning of social representations." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.

[8] Grover, Aditya, and Jure Leskovec. "node2vec: Scalable feature learning for networks." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016.

[9] Lee, John Boaz, et al. "Attention models in graphs: A survey." arXiv preprint arXiv:1807.07984 (2018).

[10] Veličković, Petar, et al. "Graph attention networks." arXiv preprint arXiv:1710.10903 (2017).

[11] F.Chen,S.Pan,J.Jiang,H.Huo,G.Long,DAGCN:DualAttention

Graph Convolutional Networks, arXiv. cs.LG (2019).

,