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