表徵圖數據，絕不止圖神經網路一種方法

• 2020 年 7 月 13 日
• AI

近年來，圖神經網路掀起了將深度學習方法應用於圖數據分析的浪潮。不過其作為一門古老的認識世界的方法論，人們對於圖表徵技術的研究從很早以前就開始了。

雖然現在深度神經網路在物體識別、影像分類和自然語言處理領域都取得了巨大的成功。然而，「設計出最優的神經網路，學習並輸出任意的圖」仍然是一個熱門的研究課題。

本文是一篇出自倫敦大學學院的圖表徵學習綜述，詳細介紹了圖核、卷積、圖神經網路、圖嵌入、概率模型共五類圖表徵學習方法的起源與發展，並對圖數據表徵學習方法的最新進展和未來發展方向進行總結和討論。

一、引言

將數據構造為圖的形式可以幫助我們以一種系統化的方式研究如何發掘複雜的關係和模式。例如，互聯網圖展示出了給定網頁間高頻鏈接的複雜結構；在自然語言處理領域中，人們有時以樹的形式表徵文本，理解單詞之間的聯繫，從而推斷出句子的意義。

然而，機器學習領域的研究主要關注於向量形式的表徵，而真實世界中的數據並不能很輕易地被表徵為向量。現實世界場景下複雜圖結構的例子包括：生物學網路、電腦網路、感測器網路、社交網路、論文引用網路、電力網路和交通網路。通過使用基於圖的表徵，我們可以捕獲結構化數據的順序、拓撲、集合和其它關係特性。

神經網路是通用的函數近似器。近年來的研究進展表明，深度學習模型已經在語音識別、目標識別與探測、自然語言處理等諸多領域中取得了巨大的成功。此外，在大型數據集、先進的計算處理能力，以及機器學習方法領域繁榮的新興研究等因素的作用極大地促進了深度學習研究。

需要指出的是，對於機器學習來說，神經網路方法和非神經網路方法的主要區別在於學習數據的表徵。在機器學習術語中，我們會使用「特徵」一詞，而在表徵學習術語中，我們關心的是學習數據的最優表徵，它有助於下游的機器學習任務。

學習「圖表徵」背後的思想是：學習一類映射，這類映射將頂點、子圖或整體的圖嵌入到低維向量空間中的點上。然後，我們優化這些映射，使他們反映嵌入空間的幾何結構，學習到的嵌入可以被用作機器學習任務的向量化輸入。

需要注意的是，本文討論的是一些流行的使用基於圖表徵的數據域，包括生物學數據、化學數據、網頁數據、文本數據、關係數據、社交媒體數據等。

二、圖理論

2.1 相關概念

在這裡，我們介紹圖理論術語，為接下來涉及圖數據的討論提供相關背景。圖是一個有序對

(V,E)。頂點集合 V 滿足 n ≡ |V|，它代表圖的階。在相應的邊集 E(G) 中，e_ij 代表頂點 i 和 j 之間的邊。 我們使用符號 V(G) 和 E(G) 圖 G 的點集和邊集。

圖的類型：本文考慮的主要是簡單圖。「簡單圖」的頂點之間僅僅通過一條邊相連。本文還將討論「無向圖、有向圖、帶權圖」：在「無向圖」中，每條邊被表徵為一個無需對{v,w}；在「有向圖」中，邊則被表徵為有序對；在「帶權圖」中，權值函數 w:f→R 為每條邊賦予權值。

如果所有頂點對之間都存在路徑，那麼該圖是「連通圖」。如果圖中的所有頂點有相同的度，那麼我們有一個「正則圖」。如果每對頂點之間都存在一條邊，則該圖為「完全圖」。

度、遊走、環、路徑、距離、高度、深度：

• 頂點 u 的「度」被表示為 deg(u)，它代表與 u 相連的邊數。

• 「遊走」是一個由鄰接頂點及其相應的邊交替組成的序列，遊走的長度由包含的邊數確定。我們有時將長度為 k 的遊走中的頂點表示為序列 v_0,v_1,…,v_k。

• 如果 v_0 = v_k（即起點與終點相同），則該遊走是一個「環」。

• 「路徑」表示每個頂點至多出現一次的遊走。

• 兩個頂點時間的「距離」記作「dist(u,v)」，它被定義為兩點之間最短路徑的長度。

• 頂點的「高度」代表節點與各個葉子節點之間自頂向下的路徑中最長的一條路徑上的邊數。

• 頂點的「深度」是從該節點到樹的根節點的路徑上的邊數。 

子圖：若 G_1 是圖 G 的子圖，則它的點集和邊集都是 G 的點集和邊集的子集。 「團」圖的一個完全子圖。「環」也是一種連通的子圖，其中每個頂點都恰好有兩個鄰點，不包含環的圖被稱為「森林」。一個連通的森林被稱為「樹」。「子森林」是一個無環子圖，「子樹」是一個連通的子森林。對於給定的頂點 v，它的鄰居節點的集合被表示為 N_v。

圖同構：令 G = (V, E) 和 G′ = (V′, E′) 為兩個圖。若存在一個雙射函數 f : V → V′，使得對於任意的 u, v ∈ V，我們有 G 中的 f(u) 和 f(v) 是鄰接的當且僅當 u 和 v 在 G′ 中鄰接，則 G 和 G′ 同構。

解決圖同構問題與機器學習緊密相關，它為發掘數據點之間的相似度提供了一種方法。然而，圖同構是一個頗具挑戰的問題，目前還沒有多項式時間內的演算法能夠求解圖同構問題。

求解圖匹配問題的早期演算法提出使用「圖編輯距離」以及「拓撲描述子」。使用圖編輯距離涉及到對將圖 G1 轉化為 G2 的關鍵操作進行計數，從而提供分配成本的靈活性。然而，這種方法存在需為不同的操作以及子圖同構的中間步驟選取最優的代價函數的問題。使用將每個圖映射到一個特徵向量上的拓撲描述子也存在在變換步驟中損失拓撲資訊的問題。一種實際可行的替代方法是使用由可以在多項式時間內計算出來的圖形成的子結構，這通常被稱為「結構袋」（bag-of-structures）方法。

2.2 圖的矩陣表徵

2.2.1 矩陣的類型

我們需要使用矩陣形式的輸入表徵來生成特徵。這些矩陣包括：鄰接矩陣，度矩陣以及拉普拉斯矩陣。鄰接矩陣 A 將圖的整個拓撲結構通過以下方式封裝在 n*n 形式的矩陣中。

度矩陣 D_ii 是一個對角矩陣，其中 d_i 為頂點 i 的度。

對於一個無權圖來說，歸一化後的拉普拉斯矩陣 L 形如：

歸一化後的拉普拉斯矩陣 L 的譜分解定義如下：L 是一個對稱的半正定矩陣，可以寫作 L = ΦΛΦ^T，其中對角矩陣 λ = diag(λ_1, λ_2, λ_3,…,λ_|V|)，其元素為排序後的 L 的特徵值；而 Φ = (φ_1, φ_2,…,φ_|V|) 是由排序有的列特徵向量組成的矩陣。圖的「譜」研究的是鄰接矩陣的特徵值。

2.2.2 矩陣之間的關係

鄰接矩陣的歸一化形式為
       
      。圖的拉普拉斯矩陣也可以使用度矩陣和鄰接矩陣，通過公式 L=D-A 計算出來。歸一化之後的拉普拉斯矩陣可以被寫作
       
     ，進一步得到
       
     。

三、圖數據的用例

圖數據的常見用例包括：圖比較、圖分類、圖聚類、鏈接預測、圖壓縮、圖可視化。

圖比較：圖比較任務旨在通過映射 s : G × G → ℜ 確定兩圖之間的相似度。傳統的圖比較演算法分為基於集合的、基於子圖的和基於核的演算法。

圖分類：圖分類問題可以被分為兩類：一種是頂點分類問題，另一類是對於整個圖的分類問題。在整個圖的分類問題中，給定一個由圖組成的數據集 D，其中每個圖 G_i 可以被表徵為 G_i = (V_i, E_i)，圖分類的目標是學習模型 f : D → Y，並將圖分類為一類或多類。通常，每個圖都有一個相應的類別標籤 Y = {1 . . . y}。

鏈接預測：以往，我們並不知道缺乏哪些鏈接或未來會形成哪些鏈接。從宏觀上說，鏈接預測任務旨在預測網路結構如何隨著現有的成員形成新的鏈接、斷開連接而演化。例如，在「蛋白質-蛋白質」交互網路中，鏈接預測可以確定蛋白質之間新的交互。給定一個網路的圖  G = (V, E)，鏈接預測任務可以定義如下：假設 U 是一個一般性的集合，它包含 |V|(|V|-1)/2 個可能的鏈接，其中 |V| 表示集合中元素的個數。因此，鏈接預測任務的目的是在集合 U-E 中尋找鏈接。數據集被隨機劃分為兩個部分：E^T（訓練集）和 E^P（測試集）。「網路增長預測」問題被認為是鏈接預測問題的延伸。在社交網路分析領域，鏈接預測被用於預測用戶形成新的朋友關係的偏好，該過程導致了用戶社交網路的增長。

圖聚類：在圖聚類問題中，邊的結構起到了很重要的作用。圖的頂點會被分組到不同的聚類簇中，分組的原則為：在形成的簇內部有許多邊，而簇之間的邊相對就少一些。主要有兩類圖聚類方法：圖內聚類和圖間聚類方法。顧名思義，圖內聚類方法將一個圖內部的頂點劃分到不同的簇中，而圖間聚類方法則將一系列圖劃分到不同的聚類中。在生物學領域，圖聚類技術被應用在基因調控網路、代謝網路、神經網路和血液網路中。在社交網路中，聚類演算法被用於社區發現任務。

其它用例：諸如網頁或社交網路圖等典型的大規模圖包含超過十億條邊並且會迅速增長。從可計算性的角度來說，從大型圖中學習知識是一項非常巨大的挑戰。最近，圖壓縮和圖可視化為解決這一問題提供了動力。圖的壓縮表徵會對其拓撲結構進行編碼。構建良好的圖表徵是一種節省存儲空間的方法，人們研究出了多種壓縮方案提供各種各樣的圖表徵。圖可視化顯式地向我們展示了頂點、社區或子圖之間的聯繫。圖的可視化圖形可以展示出一些有趣的特性，使閱讀者可以從另一個角度研究網路。然而，訂製化、布局，以及生成動態變化的可視化結果等問題仍然有待進一步探索。

四、核方法

核方法是一類被廣泛使用的演算法，它可以被應用於任意的數據結構。在一些表徵學習方法中，核方法也被用作構建模組。核函數是兩個向量在特徵空間中的內積，它將學習演算法與實例獨立開來。這意味著學習演算法僅僅依賴於實例之間的核值，而無需顯式的使用原始的數據表證。

令 X 為一個非空集合，k : X × X → R，其中 × 代表集合乘積（笛卡爾積）。如果 k(x, y) = k(y, x) ，則核 k 是對稱的；若 x_1,…,x_n∈X（n ≥ 1），且由 k_ij = k(x_i, x_j) 定義的矩陣 k 是正定的，則 k 是正定的，那麼有：

核函數可以記作：

其中  φ(x) 為特徵向量。

4.1 圖的核方法

學習結構化數據的字典是一種興起於上世紀 90 年代的方法。在「結構袋」（Bag-of-Structures

）方法中，每個數據點都被表徵為一個給定圖的子結構時衍生出的向量。使用結構袋方法，每類核的特徵表徵都是固定的，每個維度對應於一類子結構。這種方法會導致產生核空間有非常高的維度。令 G 為一個由圖組成的非空集合，則 k : G × G → R 被成為一個圖核，在這裡  < φ(G), φ(G′) > 分別都是圖的特徵向量。

現有的圖核方法是 R-卷積核的實例。R-卷積框架是對兩個結構化對象進行分解後，構建在圖對上的。論文「Convolution kernels on discrete structures」提出了將一個對象分解為原子化的子結構的思路。每種新分解出的關係 R 都會產生一種新的圖核。

       
     目前，有兩類基本的圖核學習方法：學習定義在圖上的核，以及學習定義在圖之間的核。Kondor 和 Lafferty 提出了學習圖上的核（單個圖上的頂點之間形成的圖）的想法。Gartner 提出了學習圖之間核的想法。在本文中，我們主要回顧三類使用了結構袋方法的核：遊走和路徑上的核、子樹上的核，以及子圖上的核。

4.1.1定義在遊走和路徑上的核

隨機遊走核由 Gartner 提出，其基礎是對基於由數據集 D 中的圖之間的節點序列形成的遊走的子結構進行計數。為了找到兩圖之間的公共遊走，這裡使用了一種由圖 G_1 和 G_2 中標註相同的頂點和邊構成的積圖。其中，(p1,p2) 為隨機遊走的起始概率，(q1, q2) 為停止概率。A_1, A_2 為 G_1 和 G_2 的鄰接矩陣。在直積圖 G 上的長度為 l 的公共遊走可計算如下，其中 ⊗為克羅內克積。

兩圖之間的隨機遊走核可以被形式化定義如下：

其中，λ 為應用於長程遊走的折算因子，它對所有長度不同的公共遊走進行加權求和。隨機遊走核可以被定義為一種更簡潔的形式：

最短路徑核是通過計算數據集 D 中所有長度為 n 的最短路徑 p 的對計算出來的。給定圖 G 和 G’ 的最短路徑 p 和 p′， 最短路徑核是在邊上合理地選擇核，通過對  p 和 p′ 中的邊 E_p 和 E_p′ 組成的對進行加權求和得到的。

環模式核是通過對在 D 中出現的每個圖中出現的公共環進行計數得出的，其定義如下：

其中 φ(G) 為圖的特徵向量。

4.1.2 定義在子樹上的核

由 Ramon 和 Gartner 提出的子樹核，是通過尋找數據集 D 中的每個圖中的公共子樹並對其進行比較而計算出來的。根據定義，圖 G 的子樹是由 G 中具有底層的樹結構的不通頂點組成的連通子集。尋找數據集 D 中的圖之間公共的樹狀鄰居結構相當於對相同的高度為 h 的子樹對進行計數。這樣做的好處是，我們得到了將圖的拓撲封裝起來的圖結構的豐富表徵。圖上的子樹核是定義在頂點上的子樹核的加和：

Weisfelier-Lehman 核（WL）是一種快速計算的子樹核。該核使用 WL 同構性檢驗，它由以下步驟迭代式地組成：（1）確定多重集標籤（2）標籤壓縮（3）重新更新多重集標籤。在這裡，h 為深度，l 為重新更新標註的函數，WL 定義如下：

4.1.3 定義在子圖上的核

子圖核的計算思路是：相似的圖往往具有相似的子圖，這些子圖可以被用於圖比較。連通的尺寸為 k 的非同構子圖被稱為圖元核（graphlet）G_k = {g_1, g_2, g_3,…,g_(n_k)}，其中 n_k 是規模為 k 的圖元核的個數。令 φ(G_f) 為長度為 n_k 的歸一化向量，它的第 i 個元素是 G 中圖元核 g_i 出現的頻率，s_j 表示 G 中出現子圖 g_k 的次數。

圖元核核使用所有可能的 k 階連通子圖的計數向量的點積來計算兩圖之間的相似圖。

4.1.4 使用結構袋方法存在的挑戰

對角優勢：結構袋方法遞歸地將結構化目標分解為子結構，但是這也帶來了各種各樣的挑戰。例如，其中一個挑戰就是「對角優勢」問題，此時核矩陣接近於單位矩陣。當不同的子結構被視為不同的特徵時這一問題就會發生，而且隨著子結構數量的增加，特徵的集合也會變大。因此，給定的兩個圖包含相似子結構的概率會減小。所以，某張圖與其自身的相似度比它與訓練集中其它圖的相似度要高得多。

子結構稀疏&子結構依賴：子結構稀疏問題指的是，圖與圖之間只存在很少的共同子結構。子結構以來指的是，由於一個子圖可以在另一個子圖中找到，或者可以通過修改其他子圖的頂點和邊來得到，所以子圖不是獨立的。因此，通過這些子圖表徵的特徵自然而然地趨向於相似。最後，大多數圖核將各個子結構視為獨立的特徵，這不僅會增大數據集，還回導致特徵趨同。因此，因此，經常出現的子結構，和那些經常包含較低階子結構的子結構，往往對於出現指數貢獻更大。

五、學習圖表徵

下面將介紹五類圖表徵方法：核方法、卷及方法、圖神經網路方法、圖嵌入方法，以及概率方法。「圖表徵」指的是通過神經網路計算方法學習到特徵，每種學習到的表徵都分別對圖的拓撲資訊進行編碼。

5.1 核方法

近期的研究進展突出了神經網路和核方法之間的關係。例如，Cho 和 Saul 構建了模仿神經網路的核方法，而 Marial 等人說明了卷積神經網路和核之間的關係。這裡的核方法的特點是，引入神經學習技術將核方法用於圖數據。

深度圖核（Deep graph kernels）：是將圖核與深度學習技術相結合的重要方法之一。他們試圖解決獲取子結構之間有意義的語義的問題。結構袋方法存在子結構依賴、子結構稀疏和對角優勢的問題。作者通過引入維度為 |S| × |S| 的半正定的編碼矩陣 M 對子結構之間的關係進行編碼來緩解這些問題，其中 |S| 為從訓練數據中提取出的子結構字典的尺寸。這項工作是通過設計 M 來實現的，它考慮到了子結構空間的相似度。

計算 M 的方式為：首先計運算元結構之間關係的「編輯距離」，接著使用概率化的自然語言模型學習子結構的潛在表徵。核的定義如下：

核神經網路：在「Deriving Neural Architectures from Sequence and Graph Kernels」論文中，作者使用核定義了結構化的數據（例如序列和圖）從而得到神經化的操作。他們設計了一種使用核內積的新型架構，將它嵌入到了一個循環神經網路中。該例闡釋了如何將圖核嵌入到神經模組中。給定考慮了特徵向量 f_x 的隨機遊走核，可以通過以下方式將核與神經計算聯繫起來：

其中，⊙ 是元素點積，N(v)代表圖中圍繞頂點 v 的鄰居，W 是權值矩，c_j[t] 和 h[t] 是激活前後的狀態。

5.2 卷積方法

CNN 架構可以從具有底層的時空網格結構的數據中提取表徵，使它們適用於影像、影片以及語音數據。CNN 被設計用來通過提取出輸入數據的局部不變性質在訊號域上提取局部特徵。

圖卷積：由於底層不規則的空間幾何資訊（這種數據被稱為非歐數據），許多數據在它們底層的圖上都具有不規則的結構。通常，在時序和影像數據中我們找到的是點陣類型的底層結構，而在諸如文本數據、感測器數據、網格數據、社交網路數據以及基因數據等數據中，我們找到的卻往往是不規則的底層結構。為了給圖數據設計卷積網路，我們需要使用一種相似的在不規則的圖數據域上有效的卷積運算符。

下面，我們介紹用來形式化定義圖卷積操作的相關概念。當我們考慮無向圖時，「圖訊號」是一種函數映射 x : V → ℜ，它定義在圖的節點上，通過向量 x ∈ ℜ^N 來表徵，其中向量 x 的第 n 個元素表示集合 V 中第 n 個頂點處的訊號值。我們可以認為數據與圖的頂點綁定在一起，例如一個頂點可能代表「基因-基因」交互網路中的單個基因。

對於一個 函數 f、頻率 w 來說，典型的傅里葉為 f 和特徵函數 exp(2πiwt) 的內積。

函數 f : V → R 的圖傅里葉變換是 f 在圖拉普拉斯運算元的特徵函數上的擴展。對於半正定拉普拉斯矩陣 L ，其特徵向量的標準正交集合為
       
     ，非負特徵值為
       
     ，特徵值分解可以寫作
       
     ，其中
       
     ，U 為傅里葉基。傅里葉變換將時域訊號轉化為頻域訊號。而空域訊號 x 的圖傅里葉變換為
       
     ，由於 U 為正交基，則我們有
       
     。卷積是通過一個積分定義的，它表示了給定一個函數 g 在另一個函數 f 上平移做內積時重疊的量。       

圖上的卷積操作定義如下，其中 ⊙ 為元素內積

在 CNN 中常常被用於影像數據的離散卷積是定義在規則的 2D、3D 網格數據上的，因此不適用於圖數據域。對於圖這樣的不規則網格來說，我們需要定義局部的卷積核「譜域圖卷積」。譜域圖卷積利用了一個事實：卷積是傅里葉域上的乘法。對於訊號 x 和濾波器 g_θ 來說，譜域卷積可以寫作：

其中 ，
       
     ，θ ∈R 是傅里葉係數向量。

5.2.1 空域和譜域方法

對於圖數據來說，有兩種主要的基於卷積的方法：空域方法和譜域方法。

空域方法的特點在於，在 CNN 中使用由圖數據環境下某個頂點的鄰居形成的局部感受野。我們將感受野構建為對於一種直接的圖中距離的度量，給定一個頂點作為卷積核的中心，我們觀察在一定跳數範圍內的頂點。譜域方法的特點在於，使用基於圖拉普拉斯分解的距離度量。

這兩種方法都需要仔細考慮，創建譜域卷積依賴於圖結構。對於空域卷積來說，需要為圖數據創建具有平移不變性的卷積，還要為特定的問題解決確定頂點排序和鄰居節點順序的問題。CNN 的另一個缺點是，卷積操作只適用於假設圖域固定的頂點特徵，但在許多情況下，圖可能是有雜訊的，一些圖是事先計算好的，這並不一定反映成員之間的真實關係。

5.2.2 空域方法

空域卷積：PATCHY-SAN（PS）中就用到了空域卷積方法。在這裡，它被用來以一種有監督的方式使用 CNN 學習圖的表徵，從而以一種與經典的 CNN 在影像上的工作模式相類似的方式創建感受野。對於給定的圖 G，在一個區間的頂點序列選擇過程中，會指定一個頂點序列；而在鄰居聚合步驟中，會確定一些鄰居節點，從而創建感受野。因此，一個節點的感受野就是一個鄰居感受野。在創建了鄰居感受野後，需要實現一個歸一化的步驟，它本質上是對頂點進行排序，從而在向量空間中為得到用於學習圖表徵的圖特徵創建了一個向量。

擴散卷積神經網路（Diffusion-convolutional neural networks）是另一種空域方法，它使用隨機遊走選擇空域中相近的頂點，通過將第  i 個參數 w_i 與轉移矩陣 P_i 的第 i 次冪相關聯來構建卷積。

廣義卷積：論文「A generalization of convolutional neural networks to graphstructured data」對 CNN 進行了推廣，使模型能夠在尺寸不同的圖上生成卷積。該方法使用了一種空域方法選擇排序前 k 的鄰居，它是以一種圖上的基於隨機遊走的轉移矩陣為基礎的。他們用 P 導出了 Q^k_ij，它計算出了在 k 步中從給定的頂點 x_i 到 x_j 的平均訪問次數。圖中頂點 x_i 處的卷積被表徵為張量積 (M, N, d) → (M, N, p, d) 的形式，這個四維張量包含通過 Q^k 選擇出的每種特徵排在前 p 的鄰居、M 個觀測數據、N 中特徵，節點深度為 d。

模體 CNN：模體（Motif ）是一種小型的子圖模式，它表示了節點之間特定的連接模式。論文「Motif-based convolutional neural network on graphs」提出了一種基於模體的 CNN，他們定義了一些模體，從而創建了一個圍繞目標頂點的感受野。定義了頂點 v_i 處的模體卷積單元後，所有在局部通過這種模體相連的頂點的特徵都會根據其各自的語義角色被加權。模體 CNN 使用了一種注意力機制來整合從各種模體中提取到的特徵，從而進行半監督學習。

5.2.3 譜域方法

「Spectral networks and locally connected networks on graphs」這項工作中提出了譜域網路，並介紹了一種構建連通的局部鄰居圖的技術。使用譜域網路旨在通過圖傅里葉變換對卷積網路進行推廣。在構建譜域卷積的過程中，圖拉普拉斯矩陣的譜被用於推廣卷積操作。每一種構建的譜域卷積都在 MINST 數據集的各種變體上進行了測試。

在論文「Deep convolutional networks on graph-structured data」中，作者使用譜域圖卷積核構建了上述工作。他們訓練了一種圖卷積層，它在給定一個傅里葉矩陣 U、插值核 K、權值 w 的情況下，執行前向和反向傳播。在前向和反向傳播過程中，任務相當於在圖上學習譜域卷積核。在第一種變體中，他們從下取樣的 MNIST 數據中提取坐標，通過拉普拉斯譜構建卷積。在第二種變體中，MNIST 數據被投影到 3D 球面上。

廣義圖 CNN ：論文「Convolutional neural networks on graphs with fast localized spectral filtering」提出了一種徹底使用譜理論公式將 CNN 推廣到圖數據上的方法。在特徵提取階段，作者進行了圖訊號濾波和圖粗化處理。在圖濾波階段，根據譜公式，在半徑為 k 的球內嚴格定義局部濾波器。在圖粗化階段，他們使用了一種快速的圖聚類軟體 Graclus。他們為一個給定的無向圖計算了歸一化割和比例關聯，而無需任何的特徵向量計算。當池化壓縮輸出時，需要定義有意義的圖鄰居。為了最好地實現這一目標，作者設計了一種二叉樹來組織頂點，該策略類似於構建一個一維訊號。

圖卷積網路：論文「Semi-supervised classification with graph convolutional networks」提出了一種用於半監督節點分類的圖卷積網路（GCN）。他們使用了一個神經網路模型 f(X, A) 對圖結構進行編碼，該模型使用了一種層與層之間的傳播規則，其中特徵 X 是通過在鄰接矩陣 A 上使用流行的 WL 演算法得到的。在這種情況下，考慮譜域卷積

其中，x 是每個頂點的訊號，計算該訊號的計算開銷是相當大的（尤其是在大型圖中）。g_θ 可以通過切比雪夫多項式近似得到：

論文「Modeling relational data with graph convolutional networks」提出了一種關係圖卷積網路（R-GCN），它是對 GCN 的擴展，可以用於鏈接預測、預測事實、實體分類。該模型是由編碼器和解碼器組成，編碼器是一個生成實體的潛在表徵的 R-GCN，解碼器是一個張量分解模型。

識別和注意力機制（GAT）：在論文「Beyond Grids: Learning Graph Representations for Visual Recognition」中，二維特徵圖被轉化為了圖結構，其中節點代表圖塊區域而邊則獲取到這些區域之間的關係。通過使用圖投影、圖卷積以及圖重投影等步驟，完成了圖結構的上下文建模和識別。圖注意力網路（Graph attention networks）使用基於注意力的架構進行圖結構數據的節點分類。在計算了每條邊重要性時，它只處理了每個關聯頂點的特徵。之後，該模型被用于歸納學習，它可以被泛化到未曾見過的圖上。

5.3 圖神經網路

我們將基於圖的神經網路（GNN）定義為一種連接遵循 G(V,E) 結構的框架。

圖神經網路（GNN）：這最早提出由圖結構驅動的神經網路架構的方法之一。給定其鄰居所包含的資訊，每個頂點附有一個狀態向量 x_v，其中每個頂點包含頂點層次上的標籤資訊 l_v。

GNN 中兩個主要的步驟是：（1）一個參數化的轉移方程     x_v = f_w(l_v, l_N(v))，它表明頂點 v、標籤 l_v、鄰居節點N(v)之間的依賴關係傳遞了學習到的頂點表徵。（2）局部的輸出函數 O_v = g_w(x_v, l_v) 將頂點表徵映射到各個圖的標籤上。編碼網路是通過將每個頂點的狀態存儲下來並且在激活時更新狀態構建的。GNN 通過一種遞歸的方式學習，它使用一種循環關係獲取每個頂點 v 在歐氏空間中的嵌入 x_v。該模型是端到端可微的，它通過最小化二次代價函數學習參數 w。

圖門控序列神經網路和門控圖變換網路：圖門控序列神經網路（GGSNN）是一種 GNN 的變體，可以得到非序列輸出。該模型的一個典型的示例是：輸出邏輯公式。通過使用門控循環單元（GRU），GGSNN 展開了一個固定數目步驟的遞歸式。基於時間的反向傳播演算法（BPTT）被用來基於梯度。傳播模型與 GNN 思路相當，每個頂點的表徵都是遵循一種遞歸關係更新的。輸出模型是針對每個頂點定義的可謂函數，它映射到一個輸出上。

論文「Learning graphical state transitions」提出使用門控圖變換神經網路（GGTNN），從而解決推理問題。這篇論文融合了諸如節點添加、節點狀態更新、資訊傳播、資訊聚合等大量的圖變換操作，從而解決自動問答和圖重構任務。Battagalia等人對圖神經網路架構進行了豐富的研究，討論了各種設計特性，包括消息傳遞神經網路、非本地神經網路以及各種圖神經網路變體。

5.4 圖嵌入方法

將圖嵌入到一個低維空間中涉及到一系列技術，這些技術將輸入圖變換到其分別的向量表徵中，並通過一個應設函數將它映射到空間中的一點。

各種各樣的圖嵌入技術已經被用於可視化、社區發現、無線設備定位、電網路由等任務中。圖嵌入技術重點關注保持鄰近性，從而使相同鄰域中的頂點在歐氏空間中鄰近。在過去，圖嵌入方法已經被成功地用於獲取底層圖數據表徵。

在 ISOMAP 中，他們使用了一個鄰域球面將圖數據轉化到一個圖中，使用迪傑斯特拉演算法計算頂點之間的測地距離。另一種方法是多維標度法(MDS)，當它被應用於測地線距離矩陣時，得到的結果是一個重構流形，它通常被用於定位複雜數據集中格式良好的流形。局部線性嵌入，被認為是 PCA的一種變體，它使用了最近鄰方法減少了數據的維度。

論文「Representation learning on graphs: Methods and applications」則介紹了將自編碼器應用於生成圖表徵的方法。我們有一對編碼器解碼器框架得到一對嵌入 (z_i, z_j)，這樣一來我們在重構框架上使用了如下所示的損失函數 L：

大致的想法是，編碼器 ENC 將頂點映射到向量嵌入上，而解碼器 DEC 接受一組嵌入，並根據這些嵌入解碼出用戶指定的圖統計資訊。大多數作者採用的一般工作流程設置是找到在圖上定義的相似度函數，然後是學習嵌入的成對編碼器-解碼器，L 是決定性能的損失函數。

將自然語言技術用於學習圖的節點和邊的表徵是早期圖表徵學習研究領域的主要範式。研究人員憑直覺提出了一個大膽的假設，對單詞編碼到一個 N 維空間中向量中（其中每個維度代表一些語義）的方法進行修改，以類似的方式學習圖表徵，使每個向量編碼圖的拓撲資訊。

此外，圖嵌入方法在基於遊走的方法、基於子圖的嵌入方法、多模態數據圖的嵌入、歸納框架等方面取得的最新的進展包括：深度遊走（DeepWalk）、Node2Vec、Grarep 、subgraph2vec、Visual Genome 等。

5.5 概率方法

學習圖數據表徵的概率方法包括各種各樣的神經生成式模型、基於梯度的最優化方法以及神經推理技術。潛變數建模涉及到對一個潛變數 z 和一個觀測到的變數 x 之間的關係通過一個相關的參數 θ 建模。

在這裡 p_θ(x, z) 是聯合分布，p(z) 是先驗分布， p_θ(x|z) 是似然函數。在貝葉斯模型中進行推理是通過對後驗概率 p(z|x) 進行調整實現的。在許多情況下，由於複雜的概率密度函數，計算後驗概率並不容易，因此需要近似推斷工具。變分方法包含一系列通過一個簡單的密度函數對複雜的密度函數做近似的方法，這種簡單的密度函數由一個新的近似後驗分布 q_θ(z|x) 表徵。變分自編碼器是一類新的變分方法，它利用了神經網路的計算範式，使用反向傳播技術構建了一類新的神經生成式模型。這種生成的動作發生在將數據從潛在空間映射到觀察空間的過程中，這個映射是使用神經網路完成的。

圖 1：編碼器-解碼器潛變數模型的示意圖

變分圖自編碼器（Variational Graph Auto-Encoders）是一種學習圖表徵的變分自編碼器方法。它將 GCN 作為了一個編碼器，並使用了內積操作作為解碼器。模型推斷如下所示：

X 是使用 WL 演算法得到的節點特徵矩陣，A是鄰接矩陣，則我們有：

在這裡，µ 和 σ 是通過 GCN(X,A) 賦值的參數。生成模型形如：

其中，σ(·) 為 logistic 函數。該過程通過優化下面的變分下界來學習：

此外，概率方法在分子數據表徵、特徵空間設計、圖生成等領域均有一系列進展（詳情請參閱原文）。

六、未來的發展方向

在圖表徵學習領域中，一些新興的研究重點關注的是先驗分布中編碼圖數據、學習帶權圖的表徵、學習時序圖的表徵、學習時序模體的表徵、解決非歐圖域的特定挑戰、解決使用有向圖的挑戰。與此同時，在開發新的概率方法來學習圖數據的表徵方面，也還有進一步的發展空間。

本文對核方法、卷積方法、圖神經網路方法、圖嵌入方法和概率方法等五種主要方法進行了鑒別、分組、調研和討論。雖然表徵學習解決了自動地利用影像、聲音和文本數據的資訊，但並沒有一個通用的好方法來處理圖數據。從業人員可以將這篇綜述作為獲取關於最新進展的知識的路線圖，也可以作為指導進一步實驗的工具。 雷鋒網 雷鋒網 雷鋒網