作者 | 朱梓豪
來源 | 機器之心
原文 | 從數據結構到算法：圖網絡方法初探

如果說 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 是屬性的維度。

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

圖是一種描述和建模復雜系統的通用語言，在真實世界中無處不在。例如，Facebook、 Twitter 等社交媒體構成了人類之間的社交網絡 (Social Network)；人體中的蛋白質分子構成了生物網絡 (Biological Network)；各種移動終端構成了通信網絡 (Communication Network)；智能硬件之間構成了物聯網 (Internet-of-Things) 、城市間的公路、鐵路、航線構成了運輸網絡 (Transportation Network) 等等。因此也催化出一系列在圖上進行數據挖掘的任務，如為用戶推薦感興趣的好友、判斷蛋白質結構、預測交通流量、檢測異常賬戶等等。但是真實圖的數據量龐大，動輒上億節點、而且內部拓撲結構復雜，很難將傳統的圖分析方法如最短路徑、DFS、BFS、PageRank 等算法應用到這些任務上。鑒于機器學習在圖像、文本領域的廣泛應用，一部分研究者嘗試將機器學習方法和圖數據結合起來，逐漸成為機器學習領域的一股熱潮。

網絡表示學習、圖嵌入的定義

俗話說「巧婦難為無米之炊」，再強大的機器學習算法也需要數據進行支持。在同樣的數據集和任務上，由于特征的不同，同一個算法的結果也可能會有天壤之別。由于特征的選擇對結果的決定性作用，很多數據挖掘方面的研究工作把重心放到了針對特定的數據由人工設計出有價值的特征上。

深度學習本質上是一種特征學習方法，其思想在于將原始數據通過非線性模型轉變為更高層次的特征表示，從而獲得更抽象的表達。與人工設計特征不同，深度學習會自動從數據中學習出特征表示，所以又稱為表示學習（Representation Learning）。如圖像分類，輸出的一張高維的圖片，經過一系列的卷積池化等操作，低層可以抽取出低級的特征（輪廓、顏色）、較深的層會根據低級特征學習到更高級的特征，然后變換成一個向量通過全連接層進行分類，這個向量就是輸入圖像的特征表示。

一個很自然的想法就是，既然直接在圖上直接應用機器學習方法比較困難，那么能否先將節點或邊用低維向量表示出來，然后在這些向量上應用已經很成熟的機器學習算法。這種將圖中節點嵌入到低維歐式空間中的方法就叫做圖嵌入（Graph Embedding）。

其實、圖嵌入、網絡嵌入、圖表示學習、網絡表示學習這些名詞指的的都是同一個概念。給定圖$G=(mathbf{V,E,A,X})$，圖嵌入需要學習從節點到向量的映射：$f:v_ito mathbf{y}_i in R^d$，其中$d<<|V|$，$f$需要盡可能的保留住節點的結構信息和屬性信息。

圖嵌入方法的分類

圖數據最大的特點在于節點之間存在著鏈接關系，這表明圖中節點之間并非完全獨立。除了節點間的鏈接關系，節點自身也可能含有信息，比如互聯網中網頁節點對應的文本信息，這些特性使得圖嵌入需要考慮很多的因素。從訓練所需的信息來看，一般有三種主要的信息源：圖結構、節點屬性和節點標簽，可基于此分成無監督圖嵌入和半監督圖嵌入；還有一種是根據輸入數據的不同進行劃分，比如按照邊的方向性、是否是異構網絡等性質。然而這兩種劃分依據并不合適，因為當前圖嵌入算法的主要區別在于算法類型，同一算法類型下的框架都是相似的，因此本文基于 Hamilton 等 [1] 和 Goyal 等 [2] 兩篇關于圖嵌入的綜述，將圖嵌入方法概括為基于矩陣分解的圖嵌入、基于隨機游走的圖嵌入、基于神經網絡的圖嵌入（即圖神經網絡）。

基于矩陣分解的圖嵌入

基于矩陣分解的方法是將節點間的關系用矩陣的形式加以表示，然后分解該矩陣以得到嵌入向量。通常用于表示節點關系的矩陣包括鄰接矩陣、拉普拉斯矩陣、節點轉移概率矩陣、節點屬性矩陣等。根據矩陣的性質不同適用于不同的分解策略。主要包括 Local Linear Embedding（LLE）[3]、Laplacian Eigenmaps[4]、SPE[5]、GraRep[6] 等。

LLE 算法其實是流形學習的一種，LLE 算法認為每一個數據點都可以由其鄰域節點的線性加權組合構造得到。降維到低維空間后，這種線性關系仍然得到保留。Laplacian Eigenmaps 和 LLE 有些相似，直觀思想是希望相互間有關系的點（在圖中相連的點）在降維后的空間中盡可能的靠近。為了使得輸入圖的嵌入是低維表示并且保留圖全局拓撲結構，Shaw 等 [5] 提出在歐式空間中嵌入圖的結構保留嵌入方法（SPE，Structure Preserving Embedding），學習由一組線性不等式約束的低秩核矩陣，用于捕獲輸入圖結構。SPE 在圖的可視化和無損壓縮方面獲得明顯改善，優于 Laplacian Eigenmaps 等方法。Cao 等 [6] 認為考慮節點之間的 k 階關系對把握網絡的全局特征非常重要，考慮越高階的關系，得到的網絡表示效果會越好。GraRep 通過 SVD 分解分別學習節點的 k 階表示，然后將其結合起來作為最終的表示，這樣可以很好地捕捉到遠距離節點之間的關系。

基于隨機游走的方法

隨機游走方法已經被用來近似圖的許多屬性，包括節點中心性和相似性等。當圖的規模特別大或者只能觀察到部分圖的時候，隨機游走就變得非常有用。有研究者提出了利用圖上隨機游走來獲取節點表示的嵌入技術，其中最著名的就是 DeepWalk[7] 和 node2vec[8]。

DeepWalk 是基于 word2vec 詞向量提出來的。word2vec 在訓練詞向量時，將語料作為輸入數據，而圖嵌入輸入的是整張圖，兩者看似沒有任何關聯。但是 DeepWalk 的作者發現，預料中詞語出現的次數與在圖上隨機游走節點被訪問到底的次數都服從冪律分布。因此 DeepWalk 把節點當做單詞，把隨機游走得到的節點序列當做句子，然后將其直接作為 word2vec 的輸入來得到節點的嵌入表示。其框架如圖 1 所示，首先采用隨機游走的方法產生標準的輸入序列，用 SkipGram 模型對序列建模得到節點的向量表示，然后使用分層 softmax 解決節點高維度輸出問題。DeepWalk 模型的提出為圖嵌入提出了一種新的研究思路，也算是引發了對圖嵌入研究的熱潮。

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 層，可以組成任意結構的圖神經網絡，其架構如圖所示，最終要的步驟就

不同于 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），以及如何將圖網絡和計算機視覺、自然語言處理等方向結合起來。這些都是很有價值也有意思的方向，感興趣的讀者可以進行更深度的研究。