作者 | 朱梓豪
來源 | 機(jī)器之心
原文 | 從數(shù)據(jù)結(jié)構(gòu)到算法：圖網(wǎng)絡(luò)方法初探

如果說 2019 年機(jī)器學(xué)習(xí)領(lǐng)域什么方向最火，那么必然有圖神經(jīng)網(wǎng)絡(luò)的一席之地。其實(shí)早在很多年前，圖神經(jīng)網(wǎng)絡(luò)就以圖嵌入、圖表示學(xué)習(xí)、網(wǎng)絡(luò)嵌入等別名呈現(xiàn)出來，其實(shí)所有的這些方法本質(zhì)上都是作用在圖上的機(jī)器學(xué)習(xí)。本文將根據(jù)近兩年的綜述對圖網(wǎng)絡(luò)方法做一個總結(jié)，為初入圖世界的讀者提供一個總體的概覽。

什么是圖

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

為何需要在圖上應(yīng)用機(jī)器學(xué)習(xí)方法

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

網(wǎng)絡(luò)表示學(xué)習(xí)、圖嵌入的定義

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

深度學(xué)習(xí)本質(zhì)上是一種特征學(xué)習(xí)方法，其思想在于將原始數(shù)據(jù)通過非線性模型轉(zhuǎn)變?yōu)楦邔哟蔚奶卣鞅硎?#xff0c;從而獲得更抽象的表達(dá)。與人工設(shè)計(jì)特征不同，深度學(xué)習(xí)會自動從數(shù)據(jù)中學(xué)習(xí)出特征表示，所以又稱為表示學(xué)習(xí)（Representation Learning）。如圖像分類，輸出的一張高維的圖片，經(jīng)過一系列的卷積池化等操作，低層可以抽取出低級的特征（輪廓、顏色）、較深的層會根據(jù)低級特征學(xué)習(xí)到更高級的特征，然后變換成一個向量通過全連接層進(jìn)行分類，這個向量就是輸入圖像的特征表示。

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

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

圖嵌入方法的分類

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

基于矩陣分解的圖嵌入

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

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

基于隨機(jī)游走的方法

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

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

node2vec 通過改變生成隨機(jī)游走序列的方式改進(jìn)了 DeepWalk 算法。DeepWalk 是按照均勻分布隨機(jī)選取隨機(jī)游走序列的下一個節(jié)點(diǎn)。node2vec 同時考慮了廣度優(yōu)先搜索 (BFS) 和深度優(yōu)先搜索 (DFS)。Grover 等發(fā)現(xiàn)，廣度優(yōu)先搜索注重刻畫網(wǎng)絡(luò)中的局部特征，而深度優(yōu)先搜索能更好地遍歷整個網(wǎng)絡(luò)，反映了節(jié)點(diǎn)間的同質(zhì)性。特別地，node2vec 引入 search bias 函數(shù)來平衡這兩種采樣方式，通過參數(shù) p 和 q 來調(diào)整下一步的跳轉(zhuǎn)概率。

其他基于隨機(jī)游走的方法還包括 Walklets、LsNet2vec、TriDNR、HARP、DDRW 等等。

基于神經(jīng)網(wǎng)絡(luò)的圖嵌入（圖神經(jīng)網(wǎng)絡(luò)）

還有一類方法是將神經(jīng)網(wǎng)絡(luò)和圖結(jié)合起來的圖表示學(xué)習(xí)方法，也是最近一年來最火的方向之一，我們統(tǒng)稱為圖神經(jīng)網(wǎng)絡(luò)。機(jī)器之心已經(jīng)為其做過了全面的介紹，具體請參見：深度學(xué)習(xí)時代的圖模型，清華發(fā)文綜述圖網(wǎng)絡(luò) 、清華大學(xué)圖神經(jīng)網(wǎng)絡(luò)綜述：模型與應(yīng)用、圖神經(jīng)網(wǎng)絡(luò)概述第三彈：來自 IEEE Fellow 的 GNN 綜述。主要將其分為圖卷積網(wǎng)絡(luò)、圖注意力網(wǎng)絡(luò)、圖生產(chǎn)網(wǎng)絡(luò)、圖時空網(wǎng)絡(luò)、圖自編碼器。又可以分為基于譜的方法和基于空間的方法。由于基于譜的方法需要分解矩陣特征向量，因此絕大多數(shù)新提出的方法都是基于空間，也就是如何傳播并聚合節(jié)點(diǎn)和邊的信息。圖像和文本本質(zhì)上是有規(guī)則的格柵結(jié)構(gòu)的圖，因此，很自然想到可以將已經(jīng)在 CV、NLP 領(lǐng)域成功應(yīng)用的模型拓展到圖上，如詞向量和圖卷積。最近，也出現(xiàn)了基于膠囊的圖神經(jīng)網(wǎng)絡(luò)和基于圖像語義分割 U-Net 模型的 Graph U-Net。

注意力機(jī)制的在圖嵌入的應(yīng)用

有一部分研究者將注意力 (attention) 機(jī)制引入到了圖神經(jīng)網(wǎng)絡(luò)中。注意力機(jī)制的本質(zhì)是從人類視覺注意力機(jī)制中獲得靈感。大致是我們視覺在感知東西的時候，一般不會是一個場景從到頭看到尾全部都看，而是根據(jù)需求觀察特定的一部分。這意味著，當(dāng)人們注意到某個目標(biāo)或某個場景時，該目標(biāo)內(nèi)部以及該場景內(nèi)每一處空間位置上的注意力分布是不一樣的。而且當(dāng)我們發(fā)現(xiàn)一個場景經(jīng)常在某部分出現(xiàn)自己想觀察的東西時，我們就會進(jìn)行學(xué)習(xí)在將來再出現(xiàn)類似場景時把注意力放到該部分上。更通用的解釋就是，注意力機(jī)制是根據(jù)當(dāng)前的某個狀態(tài)，從已有的大量信息中選擇性的關(guān)注部分信息的方法，其實(shí)就是一系列 注意力分配系數(shù)。

基于注意力機(jī)制的 GNN 的思想是在計(jì)算每個節(jié)點(diǎn)的表示的時候，首先計(jì)算其和鄰居節(jié)點(diǎn)之間的注意力系數(shù)，為重要的鄰居節(jié)點(diǎn)分配較大的權(quán)重，在聚合的過程中將不同的重要性分配給鄰域內(nèi)不同的節(jié)點(diǎn)。

表 1 按照輸入、輸出、任務(wù)對近兩年發(fā)表的基于注意力機(jī)制的圖神經(jīng)網(wǎng)絡(luò)模型進(jìn)行匯總比較，下面對幾個具有代表性的模型進(jìn)行概述，具體內(nèi)容請參照論文《Attention Models in Graphs: A Survey》[9]。

Yoshua Bengio 的 MILA 團(tuán)隊(duì)在 2018 年提出了圖注意力網(wǎng)絡(luò) (Graph Attention Networks, GAT)[10]，論文中定義了 Graph attention 層，通過疊加不同的 attention 層，可以組成任意結(jié)構(gòu)的圖神經(jīng)網(wǎng)絡(luò)，其架構(gòu)如圖所示，最終要的步驟就

不同于 GAT 是節(jié)點(diǎn)分類，DAGCN[11] 用于圖分類任務(wù)。模型中包括兩個 attention 單元，一個是和 GAT 一樣，用于圖卷積得到節(jié)點(diǎn)的表示，另一個是基于 attention 的池化操作，得到整個圖的表示，然后將圖表示輸入到一個 MLP 得到整個圖的分類。作者認(rèn)為，經(jīng)典的 GCN 每一層都只能捕獲第 k-hop 鄰域的結(jié)構(gòu)信息，只有最后一層的 H 被用下一步的預(yù)測，隨著網(wǎng)絡(luò)層數(shù)的增多，會丟失大量的信息。作者提出的 attention 層的思想是不僅要依賴于第 k-hop 的結(jié)果, 還要從前面每一個 hop 捕獲有價(jià)值的信息。

綜合各種圖注意力網(wǎng)絡(luò)的論文來看，最主要的區(qū)別在于如何定義和實(shí)現(xiàn)注意力機(jī)制。第一類是學(xué)習(xí) attention weights：

主要是通過 softmax 函數(shù)實(shí)現(xiàn)的，同時還需要一個基于節(jié)點(diǎn)屬性可訓(xùn)練的計(jì)算節(jié)點(diǎn) j 和節(jié)點(diǎn) 0 相關(guān)性的函數(shù)，例如 GAT 的實(shí)現(xiàn)方式為：

其中 W 是將節(jié)點(diǎn)屬性映射到隱空間的可訓(xùn)練的參數(shù)矩陣，||表示串接。

第二類基于相似度的 attention，同樣，給定相應(yīng)的屬性或特征，第二種注意力的學(xué)習(xí)方法與上面的方法類似，但有一個關(guān)鍵的區(qū)別是更多的注意力集中在具有更多相似隱藏表示或特征的節(jié)點(diǎn)上，這在文獻(xiàn)中也經(jīng)常被稱為對齊。以 AGNN 中的公式為例：

其中 cos 來計(jì)算余弦相似度，可以看到和上式非常相似。不同之處在于，模型顯式地為彼此相關(guān)的對象學(xué)習(xí)類似的隱藏嵌入，因?yàn)樽⒁饬κ腔谙嗨菩曰驅(qū)R的。

前兩種注意力主要集中在選擇相關(guān)信息以整合到目標(biāo)對象的隱藏表示中，而第三種注意力的目的略有不同，叫做基于注意力的游走。舉例來說，在一個輸入圖上執(zhí)行一系列游走，并使用 RNN 對訪問的節(jié)點(diǎn)信息進(jìn)行編碼，從而構(gòu)造一個子圖嵌入。RNN 的 t 時刻的隱藏狀態(tài)對 1 到 t 訪問的節(jié)點(diǎn)進(jìn)行編碼。Attention 就是一個函數(shù)$f』(h_t)=r_{t+1}$, 輸入的是 t 時刻的隱藏狀態(tài)，輸出一個 rank vector，告訴我們下一步我們應(yīng)該優(yōu)先考慮哪種類型的節(jié)點(diǎn)

框架

這里簡單的介紹一下 Hamilton 在論文 [1] 中提出的一種圖嵌入 encoder-decoder 框架（如圖），可以將大多數(shù)的圖嵌入方法用這個框架來表示。在這個框架中，我們圍繞兩個關(guān)鍵的映射函數(shù)組織了各種方法：一個 encoder(它將每個節(jié)點(diǎn)映射到一個低維向量) 和一個 decoder(它從已知的嵌入中解碼關(guān)于圖的結(jié)構(gòu)信息)。encoder-decoder 背后的直覺想法是這樣的:如果我們能從低位嵌入表示中學(xué)會解碼高維圖信息，如節(jié)點(diǎn)在圖中的全局位置或節(jié)點(diǎn)的局部鄰域結(jié)構(gòu)，那么原則上，這些嵌入應(yīng)包含下游機(jī)器學(xué)習(xí)任務(wù)所需的所有信息。

encoder 是一個函數(shù)：

將節(jié)點(diǎn) i 映射到嵌入向量$z_i in R^d$。decoder 是接受一組節(jié)點(diǎn)嵌入并從這些嵌入中解碼用戶指定的圖統(tǒng)計(jì)數(shù)據(jù)的函數(shù)。例如，decoder 可能根據(jù)節(jié)點(diǎn)的嵌入預(yù)測節(jié)點(diǎn)之間是否存在邊，或者可能預(yù)測圖中節(jié)點(diǎn)所屬的社區(qū)。原則上，有許多 decoder 都是可以使用的，但是在大多數(shù)工作中使用的是成對 decoder：

當(dāng)我們將成對 decoder 應(yīng)用于一對嵌入$(z_i,z_j)$時，我們得到了原始圖中$v_i$和$v_j$之間相似性的重構(gòu)，目標(biāo)就是最小化重構(gòu)后的相似性和原圖中相似性的誤差：

其中其中 SG 是一個用戶定義的、在圖 G 上的的節(jié)點(diǎn)間相似性度量。換句話說，目標(biāo)是優(yōu)化 encoder-decoder 模型，可以從低維節(jié)點(diǎn)嵌入 z_i 和 z_j 中解碼出原始圖中 SG(v_i, v_j) 成對節(jié)點(diǎn)相似性。例如可以設(shè) SG(v_i, v_j)=A_{ij}，如果節(jié)點(diǎn)相鄰則定義節(jié)點(diǎn)的相似度為 1，否則為 0。或者可以根據(jù)在圖 G 上的固定長度隨機(jī)游走 v_i 和 v_j 共線的概率來定義 SG。在實(shí)踐中，大多數(shù)方法通過最小化節(jié)點(diǎn)對集合 D 上的經(jīng)驗(yàn)損失 L 來實(shí)現(xiàn)重構(gòu)目標(biāo)：

優(yōu)化了上述目標(biāo)函數(shù)后，我們就可以使用經(jīng)過訓(xùn)練的 encoder 為節(jié)點(diǎn)生成嵌入，然后可以將其用作下游機(jī)器學(xué)習(xí)任務(wù)的特征輸入。下表展示了常用圖嵌入方法的 encoder-decoder 框架描述。

總結(jié)

圖嵌入是指將圖中節(jié)點(diǎn)用低維稠密向量來表示，從一開始的基于矩陣分解的方法逐漸出現(xiàn)了基于隨機(jī)游走的方法，后來又演化出基于神經(jīng)網(wǎng)絡(luò)的方法也是我們經(jīng)常聽到的圖神經(jīng)網(wǎng)絡(luò)。圖嵌入目前還面臨著一些挑戰(zhàn)，例如如何在超大規(guī)模圖上高效進(jìn)行分析，如何應(yīng)對真實(shí)世界中不斷變化的動態(tài)圖，如何對圖神經(jīng)網(wǎng)絡(luò)的黑盒模型進(jìn)行解釋，以及如何建模異質(zhì)圖。目前在圖網(wǎng)絡(luò)領(lǐng)域也涌現(xiàn)出一些新的方向，例如如何針對圖網(wǎng)絡(luò)進(jìn)行對抗攻擊使其模型性能大幅下降，相反的就是如何提高模型的魯棒性；如何將人工設(shè)計(jì)網(wǎng)絡(luò)架構(gòu)轉(zhuǎn)變?yōu)橛蓹C(jī)器自動設(shè)計(jì)，這對應(yīng)著網(wǎng)絡(luò)結(jié)構(gòu)搜索問題（NAS），以及如何將圖網(wǎng)絡(luò)和計(jì)算機(jī)視覺、自然語言處理等方向結(jié)合起來。這些都是很有價(jià)值也有意思的方向，感興趣的讀者可以進(jìn)行更深度的研究。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的特征图注意力_从数据结构到算法：图网络方法初探的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。