從數(shù)據(jù)結(jié)構(gòu)到算法：圖網(wǎng)絡方法初探
2019-08-21 來源：raincent
如果說 2019 年機器學習領域什么方向最火，那么必然有圖神經(jīng)網(wǎng)絡的一席之地。其實早在很多年前，圖神經(jīng)網(wǎng)絡就以圖嵌入、圖表示學習、網(wǎng)絡嵌入等別名呈現(xiàn)出來，其實所有的這些方法本質(zhì)上都是作用在圖上的機器學習。本文將根據(jù)近兩年的綜述對圖網(wǎng)絡方法做一個總結(jié)，為初入圖世界的讀者提供一個總體的概覽。
本文作者朱梓豪為中科院信工所在讀碩士，主要研究方向為圖神經(jīng)網(wǎng)絡、視覺問答、視覺對話等。
什么是圖
圖是一種常見的數(shù)據(jù)結(jié)構(gòu)，用于表示對象及其之間的關系。其中，對象又稱節(jié)點(node)或頂點(vertex)，關系用邊(edge)來描述。在數(shù)學上一般用 G=(V,E,A,X) 來表示，其中 V={v1,v2……,vn} 是節(jié)點集合，E=e_ij 表示邊的集合，A 是大小為|V|×|V|的鄰接矩陣，用于表示節(jié)點之間的連接關系，如果 e_ij∈E，則 A_ij=1，X 是大小為|V|×d 的特征矩陣，X 的第 i 行 X_i:表示第 i 個節(jié)點的屬性特征，其中 d 是屬性的維度。
為何需要在圖上應用機器學習方法
圖是一種描述和建模復雜系統(tǒng)的通用語言，在真實世界中無處不在。例如，F(xiàn)acebook、 Twitter 等社交媒體構(gòu)成了人類之間的社交網(wǎng)絡 (Social Network);人體中的蛋白質(zhì)分子構(gòu)成了生物網(wǎng)絡 (Biological Network);各種移動終端構(gòu)成了通信網(wǎng)絡 (Communication Network);智能硬件之間構(gòu)成了物聯(lián)網(wǎng) (Internet-of-Things) 、城市間的公路、鐵路、航線構(gòu)成了運輸網(wǎng)絡 (Transportation Network) 等等。因此也催化出一系列在圖上進行數(shù)據(jù)挖掘的任務，如為用戶推薦感興趣的好友、判斷蛋白質(zhì)結(jié)構(gòu)、預測交通流量、檢測異常賬戶等等。但是真實圖的數(shù)據(jù)量龐大，動輒上億節(jié)點、而且內(nèi)部拓撲結(jié)構(gòu)復雜，很難將傳統(tǒng)的圖分析方法如最短路徑、DFS、BFS、PageRank 等算法應用到這些任務上。鑒于機器學習在圖像、文本領域的廣泛應用，一部分研究者嘗試將機器學習方法和圖數(shù)據(jù)結(jié)合起來，逐漸成為機器學習領域的一股熱潮。
網(wǎng)絡表示學習、圖嵌入的定義
俗話說「巧婦難為無米之炊」，再強大的機器學習算法也需要數(shù)據(jù)進行支持。在同樣的數(shù)據(jù)集和任務上，由于特征的不同，同一個算法的結(jié)果也可能會有天壤之別。由于特征的選擇對結(jié)果的決定性作用，很多數(shù)據(jù)挖掘方面的研究工作把重心放到了針對特定的數(shù)據(jù)由人工設計出有價值的特征上。
深度學習本質(zhì)上是一種特征學習方法，其思想在于將原始數(shù)據(jù)通過非線性模型轉(zhuǎn)變?yōu)楦邔哟蔚奶卣鞅硎�，從而獲得更抽象的表達。與人工設計特征不同，深度學習會自動從數(shù)據(jù)中學習出特征表示，所以又稱為表示學習(Representation Learning)。如圖像分類，輸出的一張高維的圖片，經(jīng)過一系列的卷積池化等操作，低層可以抽取出低級的特征(輪廓、顏色)、較深的層會根據(jù)低級特征學習到更高級的特征，然后變換成一個向量通過全連接層進行分類，這個向量就是輸入圖像的特征表示。
一個很自然的想法就是，既然直接在圖上直接應用機器學習方法比較困難，那么能否先將節(jié)點或邊用低維向量表示出來，然后在這些向量上應用已經(jīng)很成熟的機器學習算法。這種將圖中節(jié)點嵌入到低維歐式空間中的方法就叫做圖嵌入(Graph Embedding)。
其實、圖嵌入、網(wǎng)絡嵌入、圖表示學習、網(wǎng)絡表示學習這些名詞指的的都是同一個概念。給定圖$G=(\mathbf{V,E,A,X})$，圖嵌入需要學習從節(jié)點到向量的映射：$f:v_i\to \mathbf{y}_i \in R^d$，其中$d<<|V|$，$f$需要盡可能的保留住節(jié)點的結(jié)構(gòu)信息和屬性信息。
圖嵌入方法的分類
圖數(shù)據(jù)最大的特點在于節(jié)點之間存在著鏈接關系，這表明圖中節(jié)點之間并非完全獨立。除了節(jié)點間的鏈接關系，節(jié)點自身也可能含有信息，比如互聯(lián)網(wǎng)中網(wǎng)頁節(jié)點對應的文本信息，這些特性使得圖嵌入需要考慮很多的因素。從訓練所需的信息來看，一般有三種主要的信息源：圖結(jié)構(gòu)、節(jié)點屬性和節(jié)點標簽，可基于此分成無監(jiān)督圖嵌入和半監(jiān)督圖嵌入;還有一種是根據(jù)輸入數(shù)據(jù)的不同進行劃分，比如按照邊的方向性、是否是異構(gòu)網(wǎng)絡等性質(zhì)。然而這兩種劃分依據(jù)并不合適，因為當前圖嵌入算法的主要區(qū)別在于算法類型，同一算法類型下的框架都是相似的，因此本文基于 Hamilton 等 [1] 和 Goyal 等 [2] 兩篇關于圖嵌入的綜述，將圖嵌入方法概括為基于矩陣分解的圖嵌入、基于隨機游走的圖嵌入、基于神經(jīng)網(wǎng)絡的圖嵌入(即圖神經(jīng)網(wǎng)絡)。
基于矩陣分解的圖嵌入
基于矩陣分解的方法是將節(jié)點間的關系用矩陣的形式加以表示，然后分解該矩陣以得到嵌入向量。通常用于表示節(jié)點關系的矩陣包括鄰接矩陣、拉普拉斯矩陣、節(jié)點轉(zhuǎn)移概率矩陣、節(jié)點屬性矩陣等。根據(jù)矩陣的性質(zhì)不同適用于不同的分解策略。主要包括 Local Linear Embedding(LLE)[3]、Laplacian Eigenmaps[4]、SPE[5]、GraRep[6] 等。
LLE 算法其實是流形學習的一種，LLE 算法認為每一個數(shù)據(jù)點都可以由其鄰域節(jié)點的線性加權(quán)組合構(gòu)造得到。降維到低維空間后，這種線性關系仍然得到保留。Laplacian Eigenmaps 和 LLE 有些相似，直觀思想是希望相互間有關系的點(在圖中相連的點)在降維后的空間中盡可能的靠近。為了使得輸入圖的嵌入是低維表示并且保留圖全局拓撲結(jié)構(gòu)，Shaw 等 [5] 提出在歐式空間中嵌入圖的結(jié)構(gòu)保留嵌入方法(SPE，Structure Preserving Embedding)，學習由一組線性不等式約束的低秩核矩陣，用于捕獲輸入圖結(jié)構(gòu)。SPE 在圖的可視化和無損壓縮方面獲得明顯改善，優(yōu)于 Laplacian Eigenmaps 等方法。Cao 等 [6] 認為考慮節(jié)點之間的 k 階關系對把握網(wǎng)絡的全局特征非常重要，考慮越高階的關系，得到的網(wǎng)絡表示效果會越好。GraRep 通過 SVD 分解分別學習節(jié)點的 k 階表示，然后將其結(jié)合起來作為最終的表示，這樣可以很好地捕捉到遠距離節(jié)點之間的關系。
基于隨機游走的方法
隨機游走方法已經(jīng)被用來近似圖的許多屬性，包括節(jié)點中心性和相似性等。當圖的規(guī)模特別大或者只能觀察到部分圖的時候，隨機游走就變得非常有用。有研究者提出了利用圖上隨機游走來獲取節(jié)點表示的嵌入技術(shù)，其中最著名的就是 DeepWalk[7] 和 node2vec[8]。
DeepWalk 是基于 word2vec 詞向量提出來的。word2vec 在訓練詞向量時，將語料作為輸入數(shù)據(jù)，而圖嵌入輸入的是整張圖，兩者看似沒有任何關聯(lián)。但是 DeepWalk 的作者發(fā)現(xiàn)，預料中詞語出現(xiàn)的次數(shù)與在圖上隨機游走節(jié)點被訪問到底的次數(shù)都服從冪律分布。因此 DeepWalk 把節(jié)點當做單詞，把隨機游走得到的節(jié)點序列當做句子，然后將其直接作為 word2vec 的輸入來得到節(jié)點的嵌入表示。其框架如圖 1 所示，首先采用隨機游走的方法產(chǎn)生標準的輸入序列，用 SkipGram 模型對序列建模得到節(jié)點的向量表示，然后使用分層 softmax 解決節(jié)點高維度輸出問題。DeepWalk 模型的提出為圖嵌入提出了一種新的研究思路，也算是引發(fā)了對圖嵌入研究的熱潮。
其他基于隨機游走的方法還包括 Walklets、LsNet2vec、TriDNR、HARP、DDRW 等等。
基于神經(jīng)網(wǎng)絡的圖嵌入(圖神經(jīng)網(wǎng)絡)
還有一類方法是將神經(jīng)網(wǎng)絡和圖結(jié)合起來的圖表示學習方法，也是最近一年來最火的方向之一，我們統(tǒng)稱為圖神經(jīng)網(wǎng)絡。機器之心已經(jīng)為其做過了全面的介紹，具體請參見：深度學習時代的圖模型，清華發(fā)文綜述圖網(wǎng)絡 、清華大學圖神經(jīng)網(wǎng)絡綜述：模型與應用、圖神經(jīng)網(wǎng)絡概述第三彈：來自 IEEE Fellow 的 GNN 綜述。主要將其分為圖卷積網(wǎng)絡、圖注意力網(wǎng)絡、圖生產(chǎn)網(wǎng)絡、圖時空網(wǎng)絡、圖自編碼器。又可以分為基于譜的方法和基于空間的方法。由于基于譜的方法需要分解矩陣特征向量，因此絕大多數(shù)新提出的方法都是基于空間，也就是如何傳播并聚合節(jié)點和邊的信息。圖像和文本本質(zhì)上是有規(guī)則的格柵結(jié)構(gòu)的圖，因此，很自然想到可以將已經(jīng)在 CV、NLP 領域成功應用的模型拓展到圖上，如詞向量和圖卷積。最近，也出現(xiàn)了基于膠囊的圖神經(jīng)網(wǎng)絡和基于圖像語義分割 U-Net 模型的 Graph U-Net。
注意力機制的在圖嵌入的應用
有一部分研究者將注意力 (attention) 機制引入到了圖神經(jīng)網(wǎng)絡中。注意力機制的本質(zhì)是從人類視覺注意力機制中獲得靈感。大致是我們視覺在感知東西的時候，一般不會是一個場景從到頭看到尾全部都看，而是根據(jù)需求觀察特定的一部分。這意味著，當人們注意到某個目標或某個場景時，該目標內(nèi)部以及該場景內(nèi)每一處空間位置上的注意力分布是不一樣的。而且當我們發(fā)現(xiàn)一個場景經(jīng)常在某部分出現(xiàn)自己想觀察的東西時，我們就會進行學習在將來再出現(xiàn)類似場景時把注意力放到該部分上。更通用的解釋就是，注意力機制是根據(jù)當前的某個狀態(tài)，從已有的大量信息中選擇性的關注部分信息的方法，其實就是一系列注意力分配系數(shù)。
基于注意力機制的 GNN 的思想是在計算每個節(jié)點的表示的時候，首先計算其和鄰居節(jié)點之間的注意力系數(shù)，為重要的鄰居節(jié)點分配較大的權(quán)重，在聚合的過程中將不同的重要性分配給鄰域內(nèi)不同的節(jié)點。
表 1 按照輸入、輸出、任務對近兩年發(fā)表的基于注意力機制的圖神經(jīng)網(wǎng)絡模型進行匯總比較，下面對幾個具有代表性的模型進行概述，具體內(nèi)容請參照論文《Attention Models in Graphs: A Survey》[9]。
Yoshua Bengio 的 MILA 團隊在 2018 年提出了圖注意力網(wǎng)絡 (Graph Attention Networks, GAT)[10]，論文中定義了 Graph attention 層，通過疊加不同的 attention 層，可以組成任意結(jié)構(gòu)的圖神經(jīng)網(wǎng)絡，其架構(gòu)如圖所示，最終要的步驟就是計算節(jié)點 i 的鄰居節(jié)點對其的注意力系數(shù)$\alpha_{ij}$, 這里還是用了多頭注意力機制，圖中不同的顏色代表不同的頭。
不同于 GAT 是節(jié)點分類，DAGCN[11] 用于圖分類任務。模型中包括兩個 attention 單元，一個是和 GAT 一樣，用于圖卷積得到節(jié)點的表示，另一個是基于 attention 的池化操作，得到整個圖的表示，然后將圖表示輸入到一個 MLP 得到整個圖的分類。作者認為，經(jīng)典的 GCN 每一層都只能捕獲第 k-hop 鄰域的結(jié)構(gòu)信息，只有最后一層的 H 被用下一步的預測，隨著網(wǎng)絡層數(shù)的增多，會丟失大量的信息。作者提出的 attention 層的思想是不僅要依賴于第 k-hop 的結(jié)果, 還要從前面每一個 hop 捕獲有價值的信息。
綜合各種圖注意力網(wǎng)絡的論文來看，最主要的區(qū)別在于如何定義和實現(xiàn)注意力機制。第一類是學習 attention weights：
主要是通過 softmax 函數(shù)實現(xiàn)的，同時還需要一個基于節(jié)點屬性可訓練的計算節(jié)點 j 和節(jié)點 0 相關性的函數(shù)，例如 GAT 的實現(xiàn)方式為：
其中 W 是將節(jié)點屬性映射到隱空間的可訓練的參數(shù)矩陣，||表示串接。
第二類基于相似度的 attention，同樣，給定相應的屬性或特征，第二種注意力的學習方法與上面的方法類似，但有一個關鍵的區(qū)別是更多的注意力集中在具有更多相似隱藏表示或特征的節(jié)點上，這在文獻中也經(jīng)常被稱為對齊。以 AGNN 中的公式為例：
其中 cos 來計算余弦相似度，可以看到和上式非常相似。不同之處在于，模型顯式地為彼此相關的對象學習類似的隱藏嵌入，因為注意力是基于相似性或?qū)R的。
前兩種注意力主要集中在選擇相關信息以整合到目標對象的隱藏表示中，而第三種注意力的目的略有不同，叫做基于注意力的游走。舉例來說，在一個輸入圖上執(zhí)行一系列游走，并使用 RNN 對訪問的節(jié)點信息進行編碼，從而構(gòu)造一個子圖嵌入。RNN 的 t 時刻的隱藏狀態(tài)對 1 到 t 訪問的節(jié)點進行編碼。Attention 就是一個函數(shù)$f』(h_t)=r_{t+1}$, 輸入的是 t 時刻的隱藏狀態(tài)，輸出一個 rank vector，告訴我們下一步我們應該優(yōu)先考慮哪種類型的節(jié)點。
框架
這里簡單的介紹一下 Hamilton 在論文 [1] 中提出的一種圖嵌入 encoder-decoder 框架(如圖)，可以將大多數(shù)的圖嵌入方法用這個框架來表示。在這個框架中，我們圍繞兩個關鍵的映射函數(shù)組織了各種方法：一個 encoder(它將每個節(jié)點映射到一個低維向量) 和一個 decoder(它從已知的嵌入中解碼關于圖的結(jié)構(gòu)信息)。encoder-decoder 背后的直覺想法是這樣的:如果我們能從低位嵌入表示中學會解碼高維圖信息，如節(jié)點在圖中的全局位置或節(jié)點的局部鄰域結(jié)構(gòu)，那么原則上，這些嵌入應包含下游機器學習任務所需的所有信息。
encoder 是一個函數(shù)：
將節(jié)點 i 映射到嵌入向量$z_i \in R^d$。decoder 是接受一組節(jié)點嵌入并從這些嵌入中解碼用戶指定的圖統(tǒng)計數(shù)據(jù)的函數(shù)。例如，decoder 可能根據(jù)節(jié)點的嵌入預測節(jié)點之間是否存在邊，或者可能預測圖中節(jié)點所屬的社區(qū)。原則上，有許多 decoder 都是可以使用的，但是在大多數(shù)工作中使用的是成對 decoder：
當我們將成對 decoder 應用于一對嵌入$(z_i,z_j)$時，我們得到了原始圖中$v_i$和$v_j$之間相似性的重構(gòu)，目標就是最小化重構(gòu)后的相似性和原圖中相似性的誤差：
其中其中 SG 是一個用戶定義的、在圖 G 上的的節(jié)點間相似性度量。換句話說，目標是優(yōu)化 encoder-decoder 模型，可以從低維節(jié)點嵌入 z_i 和 z_j 中解碼出原始圖中 SG(v_i, v_j) 成對節(jié)點相似性。例如可以設 SG(v_i, v_j)=A_{ij}，如果節(jié)點相鄰則定義節(jié)點的相似度為 1，否則為 0�；蛘呖梢愿鶕�(jù)在圖 G 上的固定長度隨機游走 v_i 和 v_j 共線的概率來定義 SG。在實踐中，大多數(shù)方法通過最小化節(jié)點對集合 D 上的經(jīng)驗損失 L 來實現(xiàn)重構(gòu)目標：
優(yōu)化了上述目標函數(shù)后，我們就可以使用經(jīng)過訓練的 encoder 為節(jié)點生成嵌入，然后可以將其用作下游機器學習任務的特征輸入。下表展示了常用圖嵌入方法的 encoder-decoder 框架描述。
總結(jié)
圖嵌入是指將圖中節(jié)點用低維稠密向量來表示，從一開始的基于矩陣分解的方法逐漸出現(xiàn)了基于隨機游走的方法，后來又演化出基于神經(jīng)網(wǎng)絡的方法也是我們經(jīng)常聽到的圖神經(jīng)網(wǎng)絡。圖嵌入目前還面臨著一些挑戰(zhàn)，例如如何在超大規(guī)模圖上高效進行分析，如何應對真實世界中不斷變化的動態(tài)圖，如何對圖神經(jīng)網(wǎng)絡的黑盒模型進行解釋，以及如何建模異質(zhì)圖。目前在圖網(wǎng)絡領域也涌現(xiàn)出一些新的方向，例如如何針對圖網(wǎng)絡進行對抗攻擊使其模型性能大幅下降，相反的就是如何提高模型的魯棒性;如何將人工設計網(wǎng)絡架構(gòu)轉(zhuǎn)變?yōu)橛蓹C器自動設計，這對應著網(wǎng)絡結(jié)構(gòu)搜索問題(NAS)，以及如何將圖網(wǎng)絡和計算機視覺、自然語言處理等方向結(jié)合起來。這些都是很有價值也有意思的方向，感興趣的讀者可以進行更深度的研究。
參考文獻：
[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).
版權(quán)申明：本站文章部分自網(wǎng)絡，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。
