<mark id="oztn4"></mark>
0
近年來，圖神經網絡掀起了將深度學習方法應用于圖數據分析的浪潮。不過其作為一門古老的認識世界的方法論，人們對于圖表征技術的研究從很早以前就開始了。
雖然現在深度神經網絡在物體識別、圖像分類和自然語言處理領域都取得了巨大的成功。然而，「設計出最優的神經網絡，學習并輸出任意的圖」仍然是一個熱門的研究課題。
本文是一篇出自倫敦大學學院的圖表征學習綜述，詳細介紹了圖核、卷積、圖神經網絡、圖嵌入、概率模型共五類圖表征學習方法的起源與發展，并對圖數據表征學習方法的最新進展和未來發展方向進行總結和討論。
將數據構造為圖的形式可以幫助我們以一種系統化的方式研究如何發掘復雜的關系和模式。例如，互聯網圖展示出了給定網頁間高頻鏈接的復雜結構；在自然語言處理領域中，人們有時以樹的形式表征文本，理解單詞之間的聯系，從而推斷出句子的意義。
然而，機器學習領域的研究主要關注于向量形式的表征，而真實世界中的數據并不能很輕易地被表征為向量。現實世界場景下復雜圖結構的例子包括：生物學網絡、計算機網絡、傳感器網絡、社交網絡、論文引用網絡、電力網絡和交通網絡。通過使用基于圖的表征，我們可以捕獲結構化數據的順序、拓撲、集合和其它關系特性。
神經網絡是通用的函數近似器。近年來的研究進展表明，深度學習模型已經在語音識別、目標識別與探測、自然語言處理等諸多領域中取得了巨大的成功。此外，在大型數據集、先進的計算處理能力，以及機器學習方法領域繁榮的新興研究等因素的作用極大地促進了深度學習研究。
需要指出的是，對于機器學習來說，神經網絡方法和非神經網絡方法的主要區別在于學習數據的表征。在機器學習術語中，我們會使用「特征」一詞，而在表征學習術語中，我們關心的是學習數據的最優表征，它有助于下游的機器學習任務。
學習「圖表征」背后的思想是：學習一類映射，這類映射將頂點、子圖或整體的圖嵌入到低維向量空間中的點上。然后，我們優化這些映射，使他們反映嵌入空間的幾何結構，學習到的嵌入可以被用作機器學習任務的向量化輸入。
需要注意的是，本文討論的是一些流行的使用基于圖表征的數據域，包括生物學數據、化學數據、網頁數據、文本數據、關系數據、社交媒體數據等。
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 函數。該過程通過優化下面的變分下界來學習：
此外，概率方法在分子數據表征、特征空間設計、圖生成等領域均有一系列進展（詳情請參閱原文）。
在圖表征學習領域中，一些新興的研究重點關注的是先驗分布中編碼圖數據、學習帶權圖的表征、學習時序圖的表征、學習時序模體的表征、解決非歐圖域的特定挑戰、解決使用有向圖的挑戰。與此同時，在開發新的概率方法來學習圖數據的表征方面，也還有進一步的發展空間。
本文對核方法、卷積方法、圖神經網絡方法、圖嵌入方法和概率方法等五種主要方法進行了鑒別、分組、調研和討論。雖然表征學習解決了自動地利用圖像、聲音和文本數據的信息，但并沒有一個通用的好方法來處理圖數據。從業人員可以將這篇綜述作為獲取關于最新進展的知識的路線圖，也可以作為指導進一步實驗的工具。 雷鋒網 雷鋒網 雷鋒網
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
