0
近年來，圖神經(jīng)網(wǎng)絡掀起了將深度學習方法應用于圖數(shù)據(jù)分析的浪潮。不過其作為一門古老的認識世界的方法論，人們對于圖表征技術的研究從很早以前就開始了。
雖然現(xiàn)在深度神經(jīng)網(wǎng)絡在物體識別、圖像分類和自然語言處理領域都取得了巨大的成功。然而，「設計出最優(yōu)的神經(jīng)網(wǎng)絡，學習并輸出任意的圖」仍然是一個熱門的研究課題。
本文是一篇出自倫敦大學學院的圖表征學習綜述，詳細介紹了圖核、卷積、圖神經(jīng)網(wǎng)絡、圖嵌入、概率模型共五類圖表征學習方法的起源與發(fā)展，并對圖數(shù)據(jù)表征學習方法的最新進展和未來發(fā)展方向進行總結(jié)和討論。
將數(shù)據(jù)構(gòu)造為圖的形式可以幫助我們以一種系統(tǒng)化的方式研究如何發(fā)掘復雜的關系和模式。例如，互聯(lián)網(wǎng)圖展示出了給定網(wǎng)頁間高頻鏈接的復雜結(jié)構(gòu)；在自然語言處理領域中，人們有時以樹的形式表征文本，理解單詞之間的聯(lián)系，從而推斷出句子的意義。
然而，機器學習領域的研究主要關注于向量形式的表征，而真實世界中的數(shù)據(jù)并不能很輕易地被表征為向量?，F(xiàn)實世界場景下復雜圖結(jié)構(gòu)的例子包括：生物學網(wǎng)絡、計算機網(wǎng)絡、傳感器網(wǎng)絡、社交網(wǎng)絡、論文引用網(wǎng)絡、電力網(wǎng)絡和交通網(wǎng)絡。通過使用基于圖的表征，我們可以捕獲結(jié)構(gòu)化數(shù)據(jù)的順序、拓撲、集合和其它關系特性。
神經(jīng)網(wǎng)絡是通用的函數(shù)近似器。近年來的研究進展表明，深度學習模型已經(jīng)在語音識別、目標識別與探測、自然語言處理等諸多領域中取得了巨大的成功。此外，在大型數(shù)據(jù)集、先進的計算處理能力，以及機器學習方法領域繁榮的新興研究等因素的作用極大地促進了深度學習研究。
需要指出的是，對于機器學習來說，神經(jīng)網(wǎng)絡方法和非神經(jīng)網(wǎng)絡方法的主要區(qū)別在于學習數(shù)據(jù)的表征。在機器學習術語中，我們會使用「特征」一詞，而在表征學習術語中，我們關心的是學習數(shù)據(jù)的最優(yōu)表征，它有助于下游的機器學習任務。
學習「圖表征」背后的思想是：學習一類映射，這類映射將頂點、子圖或整體的圖嵌入到低維向量空間中的點上。然后，我們優(yōu)化這些映射，使他們反映嵌入空間的幾何結(jié)構(gòu)，學習到的嵌入可以被用作機器學習任務的向量化輸入。
需要注意的是，本文討論的是一些流行的使用基于圖表征的數(shù)據(jù)域，包括生物學數(shù)據(jù)、化學數(shù)據(jù)、網(wǎng)頁數(shù)據(jù)、文本數(shù)據(jù)、關系數(shù)據(jù)、社交媒體數(shù)據(jù)等。
2.1 相關概念
在這里，我們介紹圖理論術語，為接下來涉及圖數(shù)據(jù)的討論提供相關背景。圖是一個有序?qū)?/p>
(V,E)。頂點集合 V 滿足 n ≡ |V|，它代表圖的階。在相應的邊集 E(G) 中，e_ij 代表頂點 i 和 j 之間的邊。 我們使用符號 V(G) 和 E(G) 圖 G 的點集和邊集。
圖的類型：本文考慮的主要是簡單圖?！负唵螆D」的頂點之間僅僅通過一條邊相連。本文還將討論「無向圖、有向圖、帶權圖」：在「無向圖」中，每條邊被表征為一個無需對{v,w}；在「有向圖」中，邊則被表征為有序?qū)?；在「帶權圖」中，權值函數(shù) w:f→R 為每條邊賦予權值。
如果所有頂點對之間都存在路徑，那么該圖是「連通圖」。如果圖中的所有頂點有相同的度，那么我們有一個「正則圖」。如果每對頂點之間都存在一條邊，則該圖為「完全圖」。
度、游走、環(huán)、路徑、距離、高度、深度：
頂點 u 的「度」被表示為 deg(u)，它代表與 u 相連的邊數(shù)。
「游走」是一個由鄰接頂點及其相應的邊交替組成的序列，游走的長度由包含的邊數(shù)確定。我們有時將長度為 k 的游走中的頂點表示為序列 v_0,v_1,...,v_k。
如果 v_0 = v_k（即起點與終點相同），則該游走是一個「環(huán)」。
「路徑」表示每個頂點至多出現(xiàn)一次的游走。
兩個頂點時間的「距離」記作「dist(u,v)」，它被定義為兩點之間最短路徑的長度。
頂點的「高度」代表節(jié)點與各個葉子節(jié)點之間自頂向下的路徑中最長的一條路徑上的邊數(shù)。
頂點的「深度」是從該節(jié)點到樹的根節(jié)點的路徑上的邊數(shù)。
子圖：若 G_1 是圖 G 的子圖，則它的點集和邊集都是 G 的點集和邊集的子集。 「團」圖的一個完全子圖?！腑h(huán)」也是一種連通的子圖，其中每個頂點都恰好有兩個鄰點，不包含環(huán)的圖被稱為「森林」。一個連通的森林被稱為「樹」。「子森林」是一個無環(huán)子圖，「子樹」是一個連通的子森林。對于給定的頂點 v，它的鄰居節(jié)點的集合被表示為 N_v。
圖同構(gòu)：令 G = (V, E) 和 G′ = (V′, E′) 為兩個圖。若存在一個雙射函數(shù) f : V → V′，使得對于任意的 u, v ∈ V，我們有 G 中的 f(u) 和 f(v) 是鄰接的當且僅當 u 和 v 在 G′ 中鄰接，則 G 和 G′ 同構(gòu)。
解決圖同構(gòu)問題與機器學習緊密相關，它為發(fā)掘數(shù)據(jù)點之間的相似度提供了一種方法。然而，圖同構(gòu)是一個頗具挑戰(zhàn)的問題，目前還沒有多項式時間內(nèi)的算法能夠求解圖同構(gòu)問題。
求解圖匹配問題的早期算法提出使用「圖編輯距離」以及「拓撲描述子」。使用圖編輯距離涉及到對將圖 G1 轉(zhuǎn)化為 G2 的關鍵操作進行計數(shù)，從而提供分配成本的靈活性。然而，這種方法存在需為不同的操作以及子圖同構(gòu)的中間步驟選取最優(yōu)的代價函數(shù)的問題。使用將每個圖映射到一個特征向量上的拓撲描述子也存在在變換步驟中損失拓撲信息的問題。一種實際可行的替代方法是使用由可以在多項式時間內(nèi)計算出來的圖形成的子結(jié)構(gòu)，這通常被稱為「結(jié)構(gòu)袋」（bag-of-structures）方法。
2.2 圖的矩陣表征
2.2.1 矩陣的類型
我們需要使用矩陣形式的輸入表征來生成特征。這些矩陣包括：鄰接矩陣，度矩陣以及拉普拉斯矩陣。鄰接矩陣 A 將圖的整個拓撲結(jié)構(gòu)通過以下方式封裝在 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 計算出來。歸一化之后的拉普拉斯矩陣可以被寫作
，進一步得到
。
圖數(shù)據(jù)的常見用例包括：圖比較、圖分類、圖聚類、鏈接預測、圖壓縮、圖可視化。
圖比較：圖比較任務旨在通過映射 s : G × G → ? 確定兩圖之間的相似度。傳統(tǒng)的圖比較算法分為基于集合的、基于子圖的和基于核的算法。
圖分類：圖分類問題可以被分為兩類：一種是頂點分類問題，另一類是對于整個圖的分類問題。在整個圖的分類問題中，給定一個由圖組成的數(shù)據(jù)集 D，其中每個圖 G_i 可以被表征為 G_i = (V_i, E_i)，圖分類的目標是學習模型 f : D → Y，并將圖分類為一類或多類。通常，每個圖都有一個相應的類別標簽 Y = {1 . . . y}。
鏈接預測：以往，我們并不知道缺乏哪些鏈接或未來會形成哪些鏈接。從宏觀上說，鏈接預測任務旨在預測網(wǎng)絡結(jié)構(gòu)如何隨著現(xiàn)有的成員形成新的鏈接、斷開連接而演化。例如，在「蛋白質(zhì)-蛋白質(zhì)」交互網(wǎng)絡中，鏈接預測可以確定蛋白質(zhì)之間新的交互。給定一個網(wǎng)絡的圖 G = (V, E)，鏈接預測任務可以定義如下：假設 U 是一個一般性的集合，它包含 |V|(|V|-1)/2 個可能的鏈接，其中 |V| 表示集合中元素的個數(shù)。因此，鏈接預測任務的目的是在集合 U-E 中尋找鏈接。數(shù)據(jù)集被隨機劃分為兩個部分：E^T（訓練集）和 E^P（測試集）。「網(wǎng)絡增長預測」問題被認為是鏈接預測問題的延伸。在社交網(wǎng)絡分析領域，鏈接預測被用于預測用戶形成新的朋友關系的偏好，該過程導致了用戶社交網(wǎng)絡的增長。
圖聚類：在圖聚類問題中，邊的結(jié)構(gòu)起到了很重要的作用。圖的頂點會被分組到不同的聚類簇中，分組的原則為：在形成的簇內(nèi)部有許多邊，而簇之間的邊相對就少一些。主要有兩類圖聚類方法：圖內(nèi)聚類和圖間聚類方法。顧名思義，圖內(nèi)聚類方法將一個圖內(nèi)部的頂點劃分到不同的簇中，而圖間聚類方法則將一系列圖劃分到不同的聚類中。在生物學領域，圖聚類技術被應用在基因調(diào)控網(wǎng)絡、代謝網(wǎng)絡、神經(jīng)網(wǎng)絡和血液網(wǎng)絡中。在社交網(wǎng)絡中，聚類算法被用于社區(qū)發(fā)現(xiàn)任務。
其它用例：諸如網(wǎng)頁或社交網(wǎng)絡圖等典型的大規(guī)模圖包含超過十億條邊并且會迅速增長。從可計算性的角度來說，從大型圖中學習知識是一項非常巨大的挑戰(zhàn)。最近，圖壓縮和圖可視化為解決這一問題提供了動力。圖的壓縮表征會對其拓撲結(jié)構(gòu)進行編碼。構(gòu)建良好的圖表征是一種節(jié)省存儲空間的方法，人們研究出了多種壓縮方案提供各種各樣的圖表征。圖可視化顯式地向我們展示了頂點、社區(qū)或子圖之間的聯(lián)系。圖的可視化圖形可以展示出一些有趣的特性，使閱讀者可以從另一個角度研究網(wǎng)絡。然而，定制化、布局，以及生成動態(tài)變化的可視化結(jié)果等問題仍然有待進一步探索。
核方法是一類被廣泛使用的算法，它可以被應用于任意的數(shù)據(jù)結(jié)構(gòu)。在一些表征學習方法中，核方法也被用作構(gòu)建模塊。核函數(shù)是兩個向量在特征空間中的內(nèi)積，它將學習算法與實例獨立開來。這意味著學習算法僅僅依賴于實例之間的核值，而無需顯式的使用原始的數(shù)據(jù)表證。
令 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 是正定的，那么有：
核函數(shù)可以記作：
其中 φ(x) 為特征向量。
4.1 圖的核方法
學習結(jié)構(gòu)化數(shù)據(jù)的字典是一種興起于上世紀 90 年代的方法。在「結(jié)構(gòu)袋」（Bag-of-Structures
）方法中，每個數(shù)據(jù)點都被表征為一個給定圖的子結(jié)構(gòu)時衍生出的向量。使用結(jié)構(gòu)袋方法，每類核的特征表征都是固定的，每個維度對應于一類子結(jié)構(gòu)。這種方法會導致產(chǎn)生核空間有非常高的維度。令 G 為一個由圖組成的非空集合，則 k : G × G → R 被成為一個圖核，在這里 < φ(G), φ(G′) > 分別都是圖的特征向量。
現(xiàn)有的圖核方法是 R-卷積核的實例。R-卷積框架是對兩個結(jié)構(gòu)化對象進行分解后，構(gòu)建在圖對上的。論文「Convolution kernels on discrete structures」提出了將一個對象分解為原子化的子結(jié)構(gòu)的思路。每種新分解出的關系 R 都會產(chǎn)生一種新的圖核。
目前，有兩類基本的圖核學習方法：學習定義在圖上的核，以及學習定義在圖之間的核。Kondor 和 Lafferty 提出了學習圖上的核（單個圖上的頂點之間形成的圖）的想法。Gartner 提出了學習圖之間核的想法。在本文中，我們主要回顧三類使用了結(jié)構(gòu)袋方法的核：游走和路徑上的核、子樹上的核，以及子圖上的核。
4.1.1定義在游走和路徑上的核
隨機游走核由 Gartner 提出，其基礎是對基于由數(shù)據(jù)集 D 中的圖之間的節(jié)點序列形成的游走的子結(jié)構(gòu)進行計數(shù)。為了找到兩圖之間的公共游走，這里使用了一種由圖 G_1 和 G_2 中標注相同的頂點和邊構(gòu)成的積圖。其中，(p1,p2) 為隨機游走的起始概率，(q1, q2) 為停止概率。A_1, A_2 為 G_1 和 G_2 的鄰接矩陣。在直積圖 G 上的長度為 l 的公共游走可計算如下，其中 ?為克羅內(nèi)克積。
兩圖之間的隨機游走核可以被形式化定義如下：
其中，λ 為應用于長程游走的折算因子，它對所有長度不同的公共游走進行加權求和。隨機游走核可以被定義為一種更簡潔的形式：
最短路徑核是通過計算數(shù)據(jù)集 D 中所有長度為 n 的最短路徑 p 的對計算出來的。給定圖 G 和 G' 的最短路徑 p 和 p′， 最短路徑核是在邊上合理地選擇核，通過對 p 和 p′ 中的邊 E_p 和 E_p′ 組成的對進行加權求和得到的。
環(huán)模式核是通過對在 D 中出現(xiàn)的每個圖中出現(xiàn)的公共環(huán)進行計數(shù)得出的，其定義如下：
其中 φ(G) 為圖的特征向量。
4.1.2 定義在子樹上的核
由 Ramon 和 Gartner 提出的子樹核，是通過尋找數(shù)據(jù)集 D 中的每個圖中的公共子樹并對其進行比較而計算出來的。根據(jù)定義，圖 G 的子樹是由 G 中具有底層的樹結(jié)構(gòu)的不通頂點組成的連通子集。尋找數(shù)據(jù)集 D 中的圖之間公共的樹狀鄰居結(jié)構(gòu)相當于對相同的高度為 h 的子樹對進行計數(shù)。這樣做的好處是，我們得到了將圖的拓撲封裝起來的圖結(jié)構(gòu)的豐富表征。圖上的子樹核是定義在頂點上的子樹核的加和：
Weisfelier-Lehman 核（WL）是一種快速計算的子樹核。該核使用 WL 同構(gòu)性檢驗，它由以下步驟迭代式地組成：（1）確定多重集標簽（2）標簽壓縮（3）重新更新多重集標簽。在這里，h 為深度，l 為重新更新標注的函數(shù)，WL 定義如下：
4.1.3 定義在子圖上的核
子圖核的計算思路是：相似的圖往往具有相似的子圖，這些子圖可以被用于圖比較。連通的尺寸為 k 的非同構(gòu)子圖被稱為圖元核（graphlet）G_k = {g_1, g_2, g_3,...,g_(n_k)}，其中 n_k 是規(guī)模為 k 的圖元核的個數(shù)。令 φ(G_f) 為長度為 n_k 的歸一化向量，它的第 i 個元素是 G 中圖元核 g_i 出現(xiàn)的頻率，s_j 表示 G 中出現(xiàn)子圖 g_k 的次數(shù)。
圖元核核使用所有可能的 k 階連通子圖的計數(shù)向量的點積來計算兩圖之間的相似圖。
4.1.4 使用結(jié)構(gòu)袋方法存在的挑戰(zhàn)
對角優(yōu)勢：結(jié)構(gòu)袋方法遞歸地將結(jié)構(gòu)化目標分解為子結(jié)構(gòu)，但是這也帶來了各種各樣的挑戰(zhàn)。例如，其中一個挑戰(zhàn)就是「對角優(yōu)勢」問題，此時核矩陣接近于單位矩陣。當不同的子結(jié)構(gòu)被視為不同的特征時這一問題就會發(fā)生，而且隨著子結(jié)構(gòu)數(shù)量的增加，特征的集合也會變大。因此，給定的兩個圖包含相似子結(jié)構(gòu)的概率會減小。所以，某張圖與其自身的相似度比它與訓練集中其它圖的相似度要高得多。
子結(jié)構(gòu)稀疏&子結(jié)構(gòu)依賴：子結(jié)構(gòu)稀疏問題指的是，圖與圖之間只存在很少的共同子結(jié)構(gòu)。子結(jié)構(gòu)以來指的是，由于一個子圖可以在另一個子圖中找到，或者可以通過修改其他子圖的頂點和邊來得到，所以子圖不是獨立的。因此，通過這些子圖表征的特征自然而然地趨向于相似。最后，大多數(shù)圖核將各個子結(jié)構(gòu)視為獨立的特征，這不僅會增大數(shù)據(jù)集，還回導致特征趨同。因此，因此，經(jīng)常出現(xiàn)的子結(jié)構(gòu)，和那些經(jīng)常包含較低階子結(jié)構(gòu)的子結(jié)構(gòu)，往往對于出現(xiàn)指數(shù)貢獻更大。
五、學習圖表征
下面將介紹五類圖表征方法：核方法、卷及方法、圖神經(jīng)網(wǎng)絡方法、圖嵌入方法，以及概率方法。「圖表征」指的是通過神經(jīng)網(wǎng)絡計算方法學習到特征，每種學習到的表征都分別對圖的拓撲信息進行編碼。
5.1 核方法
近期的研究進展突出了神經(jīng)網(wǎng)絡和核方法之間的關系。例如，Cho 和 Saul 構(gòu)建了模仿神經(jīng)網(wǎng)絡的核方法，而 Marial 等人說明了卷積神經(jīng)網(wǎng)絡和核之間的關系。這里的核方法的特點是，引入神經(jīng)學習技術將核方法用于圖數(shù)據(jù)。
深度圖核（Deep graph kernels）：是將圖核與深度學習技術相結(jié)合的重要方法之一。他們試圖解決獲取子結(jié)構(gòu)之間有意義的語義的問題。結(jié)構(gòu)袋方法存在子結(jié)構(gòu)依賴、子結(jié)構(gòu)稀疏和對角優(yōu)勢的問題。作者通過引入維度為 |S| × |S| 的半正定的編碼矩陣 M 對子結(jié)構(gòu)之間的關系進行編碼來緩解這些問題，其中 |S| 為從訓練數(shù)據(jù)中提取出的子結(jié)構(gòu)字典的尺寸。這項工作是通過設計 M 來實現(xiàn)的，它考慮到了子結(jié)構(gòu)空間的相似度。
計算 M 的方式為：首先計算子結(jié)構(gòu)之間關系的「編輯距離」，接著使用概率化的自然語言模型學習子結(jié)構(gòu)的潛在表征。核的定義如下：
核神經(jīng)網(wǎng)絡：在「Deriving Neural Architectures from Sequence and Graph Kernels」論文中，作者使用核定義了結(jié)構(gòu)化的數(shù)據(jù)（例如序列和圖）從而得到神經(jīng)化的操作。他們設計了一種使用核內(nèi)積的新型架構(gòu)，將它嵌入到了一個循環(huán)神經(jīng)網(wǎng)絡中。該例闡釋了如何將圖核嵌入到神經(jīng)模塊中。給定考慮了特征向量 f_x 的隨機游走核，可以通過以下方式將核與神經(jīng)計算聯(lián)系起來：
其中，⊙ 是元素點積，N(v)代表圖中圍繞頂點 v 的鄰居，W 是權值矩，c_j[t] 和 h[t] 是激活前后的狀態(tài)。
5.2 卷積方法
CNN 架構(gòu)可以從具有底層的時空網(wǎng)格結(jié)構(gòu)的數(shù)據(jù)中提取表征，使它們適用于圖像、視頻以及語音數(shù)據(jù)。CNN 被設計用來通過提取出輸入數(shù)據(jù)的局部不變性質(zhì)在信號域上提取局部特征。
圖卷積：由于底層不規(guī)則的空間幾何信息（這種數(shù)據(jù)被稱為非歐數(shù)據(jù)），許多數(shù)據(jù)在它們底層的圖上都具有不規(guī)則的結(jié)構(gòu)。通常，在時序和圖像數(shù)據(jù)中我們找到的是點陣類型的底層結(jié)構(gòu)，而在諸如文本數(shù)據(jù)、傳感器數(shù)據(jù)、網(wǎng)格數(shù)據(jù)、社交網(wǎng)絡數(shù)據(jù)以及基因數(shù)據(jù)等數(shù)據(jù)中，我們找到的卻往往是不規(guī)則的底層結(jié)構(gòu)。為了給圖數(shù)據(jù)設計卷積網(wǎng)絡，我們需要使用一種相似的在不規(guī)則的圖數(shù)據(jù)域上有效的卷積運算符。
下面，我們介紹用來形式化定義圖卷積操作的相關概念。當我們考慮無向圖時，「圖信號」是一種函數(shù)映射 x : V → ?，它定義在圖的節(jié)點上，通過向量 x ∈ ?^N 來表征，其中向量 x 的第 n 個元素表示集合 V 中第 n 個頂點處的信號值。我們可以認為數(shù)據(jù)與圖的頂點綁定在一起，例如一個頂點可能代表「基因-基因」交互網(wǎng)絡中的單個基因。
對于一個 函數(shù) f、頻率 w 來說，典型的傅里葉為 f 和特征函數(shù) exp(2πiwt) 的內(nèi)積。
函數(shù) f : V → R 的圖傅里葉變換是 f 在圖拉普拉斯算子的特征函數(shù)上的擴展。對于半正定拉普拉斯矩陣 L ，其特征向量的標準正交集合為
，非負特征值為
，特征值分解可以寫作
，其中
，U 為傅里葉基。傅里葉變換將時域信號轉(zhuǎn)化為頻域信號。而空域信號 x 的圖傅里葉變換為
，由于 U 為正交基，則我們有
。卷積是通過一個積分定義的，它表示了給定一個函數(shù) g 在另一個函數(shù) f 上平移做內(nèi)積時重疊的量。 
圖上的卷積操作定義如下，其中 ⊙ 為元素內(nèi)積
在 CNN 中常常被用于圖像數(shù)據(jù)的離散卷積是定義在規(guī)則的 2D、3D 網(wǎng)格數(shù)據(jù)上的，因此不適用于圖數(shù)據(jù)域。對于圖這樣的不規(guī)則網(wǎng)格來說，我們需要定義局部的卷積核「譜域圖卷積」。譜域圖卷積利用了一個事實：卷積是傅里葉域上的乘法。對于信號 x 和濾波器 g_θ 來說，譜域卷積可以寫作：
其中 ，
，θ ∈R 是傅里葉系數(shù)向量。
5.2.1 空域和譜域方法
對于圖數(shù)據(jù)來說，有兩種主要的基于卷積的方法：空域方法和譜域方法。
空域方法的特點在于，在 CNN 中使用由圖數(shù)據(jù)環(huán)境下某個頂點的鄰居形成的局部感受野。我們將感受野構(gòu)建為對于一種直接的圖中距離的度量，給定一個頂點作為卷積核的中心，我們觀察在一定跳數(shù)范圍內(nèi)的頂點。譜域方法的特點在于，使用基于圖拉普拉斯分解的距離度量。
這兩種方法都需要仔細考慮，創(chuàng)建譜域卷積依賴于圖結(jié)構(gòu)。對于空域卷積來說，需要為圖數(shù)據(jù)創(chuàng)建具有平移不變性的卷積，還要為特定的問題解決確定頂點排序和鄰居節(jié)點順序的問題。CNN 的另一個缺點是，卷積操作只適用于假設圖域固定的頂點特征，但在許多情況下，圖可能是有噪聲的，一些圖是事先計算好的，這并不一定反映成員之間的真實關系。
5.2.2 空域方法
空域卷積：PATCHY-SAN（PS）中就用到了空域卷積方法。在這里，它被用來以一種有監(jiān)督的方式使用 CNN 學習圖的表征，從而以一種與經(jīng)典的 CNN 在圖像上的工作模式相類似的方式創(chuàng)建感受野。對于給定的圖 G，在一個區(qū)間的頂點序列選擇過程中，會指定一個頂點序列；而在鄰居聚合步驟中，會確定一些鄰居節(jié)點，從而創(chuàng)建感受野。因此，一個節(jié)點的感受野就是一個鄰居感受野。在創(chuàng)建了鄰居感受野后，需要實現(xiàn)一個歸一化的步驟，它本質(zhì)上是對頂點進行排序，從而在向量空間中為得到用于學習圖表征的圖特征創(chuàng)建了一個向量。
擴散卷積神經(jīng)網(wǎng)絡（Diffusion-convolutional neural networks）是另一種空域方法，它使用隨機游走選擇空域中相近的頂點，通過將第 i 個參數(shù) w_i 與轉(zhuǎn)移矩陣 P_i 的第 i 次冪相關聯(lián)來構(gòu)建卷積。
廣義卷積：論文「A generalization of convolutional neural networks to graphstructured data」對 CNN 進行了推廣，使模型能夠在尺寸不同的圖上生成卷積。該方法使用了一種空域方法選擇排序前 k 的鄰居，它是以一種圖上的基于隨機游走的轉(zhuǎn)移矩陣為基礎的。他們用 P 導出了 Q^k_ij，它計算出了在 k 步中從給定的頂點 x_i 到 x_j 的平均訪問次數(shù)。圖中頂點 x_i 處的卷積被表征為張量積 (M, N, d) → (M, N, p, d) 的形式，這個四維張量包含通過 Q^k 選擇出的每種特征排在前 p 的鄰居、M 個觀測數(shù)據(jù)、N 中特征，節(jié)點深度為 d。
模體 CNN：模體（Motif ）是一種小型的子圖模式，它表示了節(jié)點之間特定的連接模式。論文「Motif-based convolutional neural network on graphs」提出了一種基于模體的 CNN，他們定義了一些模體，從而創(chuàng)建了一個圍繞目標頂點的感受野。定義了頂點 v_i 處的模體卷積單元后，所有在局部通過這種模體相連的頂點的特征都會根據(jù)其各自的語義角色被加權。模體 CNN 使用了一種注意力機制來整合從各種模體中提取到的特征，從而進行半監(jiān)督學習。
5.2.3 譜域方法
「Spectral networks and locally connected networks on graphs」這項工作中提出了譜域網(wǎng)絡，并介紹了一種構(gòu)建連通的局部鄰居圖的技術。使用譜域網(wǎng)絡旨在通過圖傅里葉變換對卷積網(wǎng)絡進行推廣。在構(gòu)建譜域卷積的過程中，圖拉普拉斯矩陣的譜被用于推廣卷積操作。每一種構(gòu)建的譜域卷積都在 MINST 數(shù)據(jù)集的各種變體上進行了測試。
在論文「Deep convolutional networks on graph-structured data」中，作者使用譜域圖卷積核構(gòu)建了上述工作。他們訓練了一種圖卷積層，它在給定一個傅里葉矩陣 U、插值核 K、權值 w 的情況下，執(zhí)行前向和反向傳播。在前向和反向傳播過程中，任務相當于在圖上學習譜域卷積核。在第一種變體中，他們從下采樣的 MNIST 數(shù)據(jù)中提取坐標，通過拉普拉斯譜構(gòu)建卷積。在第二種變體中，MNIST 數(shù)據(jù)被投影到 3D 球面上。
廣義圖 CNN ：論文「Convolutional neural networks on graphs with fast localized spectral filtering」提出了一種徹底使用譜理論公式將 CNN 推廣到圖數(shù)據(jù)上的方法。在特征提取階段，作者進行了圖信號濾波和圖粗化處理。在圖濾波階段，根據(jù)譜公式，在半徑為 k 的球內(nèi)嚴格定義局部濾波器。在圖粗化階段，他們使用了一種快速的圖聚類軟件 Graclus。他們?yōu)橐粋€給定的無向圖計算了歸一化割和比例關聯(lián)，而無需任何的特征向量計算。當池化壓縮輸出時，需要定義有意義的圖鄰居。為了最好地實現(xiàn)這一目標，作者設計了一種二叉樹來組織頂點，該策略類似于構(gòu)建一個一維信號。
圖卷積網(wǎng)絡：論文「Semi-supervised classification with graph convolutional networks」提出了一種用于半監(jiān)督節(jié)點分類的圖卷積網(wǎng)絡（GCN）。他們使用了一個神經(jīng)網(wǎng)絡模型 f(X, A) 對圖結(jié)構(gòu)進行編碼，該模型使用了一種層與層之間的傳播規(guī)則，其中特征 X 是通過在鄰接矩陣 A 上使用流行的 WL 算法得到的。在這種情況下，考慮譜域卷積
其中，x 是每個頂點的信號，計算該信號的計算開銷是相當大的（尤其是在大型圖中）。g_θ 可以通過切比雪夫多項式近似得到：
論文「Modeling relational data with graph convolutional networks」提出了一種關系圖卷積網(wǎng)絡（R-GCN），它是對 GCN 的擴展，可以用于鏈接預測、預測事實、實體分類。該模型是由編碼器和解碼器組成，編碼器是一個生成實體的潛在表征的 R-GCN，解碼器是一個張量分解模型。
識別和注意力機制（GAT）：在論文「Beyond Grids: Learning Graph Representations for Visual Recognition」中，二維特征圖被轉(zhuǎn)化為了圖結(jié)構(gòu)，其中節(jié)點代表圖塊區(qū)域而邊則獲取到這些區(qū)域之間的關系。通過使用圖投影、圖卷積以及圖重投影等步驟，完成了圖結(jié)構(gòu)的上下文建模和識別。圖注意力網(wǎng)絡（Graph attention networks）使用基于注意力的架構(gòu)進行圖結(jié)構(gòu)數(shù)據(jù)的節(jié)點分類。在計算了每條邊重要性時，它只處理了每個關聯(lián)頂點的特征。之后，該模型被用于歸納學習，它可以被泛化到未曾見過的圖上。
5.3 圖神經(jīng)網(wǎng)絡
我們將基于圖的神經(jīng)網(wǎng)絡（GNN）定義為一種連接遵循 G(V,E) 結(jié)構(gòu)的框架。
圖神經(jīng)網(wǎng)絡（GNN）：這最早提出由圖結(jié)構(gòu)驅(qū)動的神經(jīng)網(wǎng)絡架構(gòu)的方法之一。給定其鄰居所包含的信息，每個頂點附有一個狀態(tài)向量 x_v，其中每個頂點包含頂點層次上的標簽信息 l_v。
GNN 中兩個主要的步驟是：（1）一個參數(shù)化的轉(zhuǎn)移方程 x_v = f_w(l_v, l_N(v))，它表明頂點 v、標簽 l_v、鄰居節(jié)點N(v)之間的依賴關系傳遞了學習到的頂點表征。（2）局部的輸出函數(shù) O_v = g_w(x_v, l_v) 將頂點表征映射到各個圖的標簽上。編碼網(wǎng)絡是通過將每個頂點的狀態(tài)存儲下來并且在激活時更新狀態(tài)構(gòu)建的。GNN 通過一種遞歸的方式學習，它使用一種循環(huán)關系獲取每個頂點 v 在歐氏空間中的嵌入 x_v。該模型是端到端可微的，它通過最小化二次代價函數(shù)學習參數(shù) w。
圖門控序列神經(jīng)網(wǎng)絡和門控圖變換網(wǎng)絡：圖門控序列神經(jīng)網(wǎng)絡（GGSNN）是一種 GNN 的變體，可以得到非序列輸出。該模型的一個典型的示例是：輸出邏輯公式。通過使用門控循環(huán)單元（GRU），GGSNN 展開了一個固定數(shù)目步驟的遞歸式?；跁r間的反向傳播算法（BPTT）被用來基于梯度。傳播模型與 GNN 思路相當，每個頂點的表征都是遵循一種遞歸關系更新的。輸出模型是針對每個頂點定義的可謂函數(shù)，它映射到一個輸出上。
論文「Learning graphical state transitions」提出使用門控圖變換神經(jīng)網(wǎng)絡（GGTNN），從而解決推理問題。這篇論文融合了諸如節(jié)點添加、節(jié)點狀態(tài)更新、信息傳播、信息聚合等大量的圖變換操作，從而解決自動問答和圖重構(gòu)任務。Battagalia等人對圖神經(jīng)網(wǎng)絡架構(gòu)進行了豐富的研究，討論了各種設計特性，包括消息傳遞神經(jīng)網(wǎng)絡、非本地神經(jīng)網(wǎng)絡以及各種圖神經(jīng)網(wǎng)絡變體。
5.4 圖嵌入方法
將圖嵌入到一個低維空間中涉及到一系列技術，這些技術將輸入圖變換到其分別的向量表征中，并通過一個應設函數(shù)將它映射到空間中的一點。
各種各樣的圖嵌入技術已經(jīng)被用于可視化、社區(qū)發(fā)現(xiàn)、無線設備定位、電網(wǎng)路由等任務中。圖嵌入技術重點關注保持鄰近性，從而使相同鄰域中的頂點在歐氏空間中鄰近。在過去，圖嵌入方法已經(jīng)被成功地用于獲取底層圖數(shù)據(jù)表征。
在 ISOMAP 中，他們使用了一個鄰域球面將圖數(shù)據(jù)轉(zhuǎn)化到一個圖中，使用迪杰斯特拉算法計算頂點之間的測地距離。另一種方法是多維標度法(MDS)，當它被應用于測地線距離矩陣時，得到的結(jié)果是一個重構(gòu)流形，它通常被用于定位復雜數(shù)據(jù)集中格式良好的流形。局部線性嵌入，被認為是 PCA的一種變體，它使用了最近鄰方法減少了數(shù)據(jù)的維度。
論文「Representation learning on graphs: Methods and applications」則介紹了將自編碼器應用于生成圖表征的方法。我們有一對編碼器解碼器框架得到一對嵌入 (z_i, z_j)，這樣一來我們在重構(gòu)框架上使用了如下所示的損失函數(shù) L：
大致的想法是，編碼器 ENC 將頂點映射到向量嵌入上，而解碼器 DEC 接受一組嵌入，并根據(jù)這些嵌入解碼出用戶指定的圖統(tǒng)計信息。大多數(shù)作者采用的一般工作流程設置是找到在圖上定義的相似度函數(shù)，然后是學習嵌入的成對編碼器-解碼器，L 是決定性能的損失函數(shù)。
將自然語言技術用于學習圖的節(jié)點和邊的表征是早期圖表征學習研究領域的主要范式。研究人員憑直覺提出了一個大膽的假設，對單詞編碼到一個 N 維空間中向量中（其中每個維度代表一些語義）的方法進行修改，以類似的方式學習圖表征，使每個向量編碼圖的拓撲信息。
此外，圖嵌入方法在基于游走的方法、基于子圖的嵌入方法、多模態(tài)數(shù)據(jù)圖的嵌入、歸納框架等方面取得的最新的進展包括：深度游走（DeepWalk）、Node2Vec、Grarep 、subgraph2vec、Visual Genome 等。
5.5 概率方法
學習圖數(shù)據(jù)表征的概率方法包括各種各樣的神經(jīng)生成式模型、基于梯度的最優(yōu)化方法以及神經(jīng)推理技術。潛變量建模涉及到對一個潛變量 z 和一個觀測到的變量 x 之間的關系通過一個相關的參數(shù) θ 建模。
在這里 p_θ(x, z) 是聯(lián)合分布，p(z) 是先驗分布， p_θ(x|z) 是似然函數(shù)。在貝葉斯模型中進行推理是通過對后驗概率 p(z|x) 進行調(diào)整實現(xiàn)的。在許多情況下，由于復雜的概率密度函數(shù)，計算后驗概率并不容易，因此需要近似推斷工具。變分方法包含一系列通過一個簡單的密度函數(shù)對復雜的密度函數(shù)做近似的方法，這種簡單的密度函數(shù)由一個新的近似后驗分布 q_θ(z|x) 表征。變分自編碼器是一類新的變分方法，它利用了神經(jīng)網(wǎng)絡的計算范式，使用反向傳播技術構(gòu)建了一類新的神經(jīng)生成式模型。這種生成的動作發(fā)生在將數(shù)據(jù)從潛在空間映射到觀察空間的過程中，這個映射是使用神經(jīng)網(wǎng)絡完成的。
圖 1：編碼器-解碼器潛變量模型的示意圖
變分圖自編碼器（Variational Graph Auto-Encoders）是一種學習圖表征的變分自編碼器方法。它將 GCN 作為了一個編碼器，并使用了內(nèi)積操作作為解碼器。模型推斷如下所示：
X 是使用 WL 算法得到的節(jié)點特征矩陣，A是鄰接矩陣，則我們有：
在這里，μ 和 σ 是通過 GCN(X,A) 賦值的參數(shù)。生成模型形如：
其中，σ(·) 為 logistic 函數(shù)。該過程通過優(yōu)化下面的變分下界來學習：
此外，概率方法在分子數(shù)據(jù)表征、特征空間設計、圖生成等領域均有一系列進展（詳情請參閱原文）。
在圖表征學習領域中，一些新興的研究重點關注的是先驗分布中編碼圖數(shù)據(jù)、學習帶權圖的表征、學習時序圖的表征、學習時序模體的表征、解決非歐圖域的特定挑戰(zhàn)、解決使用有向圖的挑戰(zhàn)。與此同時，在開發(fā)新的概率方法來學習圖數(shù)據(jù)的表征方面，也還有進一步的發(fā)展空間。
本文對核方法、卷積方法、圖神經(jīng)網(wǎng)絡方法、圖嵌入方法和概率方法等五種主要方法進行了鑒別、分組、調(diào)研和討論。雖然表征學習解決了自動地利用圖像、聲音和文本數(shù)據(jù)的信息，但并沒有一個通用的好方法來處理圖數(shù)據(jù)。從業(yè)人員可以將這篇綜述作為獲取關于最新進展的知識的路線圖，也可以作為指導進一步實驗的工具。 雷鋒網(wǎng) 雷鋒網(wǎng) 雷鋒網(wǎng)
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
