# 四、圖嵌入技術 在本節中，我們基于所使用的技術對圖嵌入方法進行分類。 通常，圖嵌入旨在在低維空間中表示圖，保留盡可能多的圖屬性信息。 不同圖嵌入算法之間的區別在于，它們如何定義要保留的圖屬性。 不同的算法對節點（邊、子結構、整圖）的相似性，以及如何在嵌入空間中保留它們，有不同的見解。 接下來，我們將介紹每種圖嵌入技術的見解，以及它們如何量化圖屬性并解決圖嵌入問題。 ## 矩陣分解 基于矩陣分解的圖嵌入，以矩陣的形式表示圖特性（例如，節點成對相似性）并對該矩陣進行分解來獲得節點嵌入[11]。 圖嵌入的開創性研究通常以這種方式解決圖嵌入問題。 在大多數情況下，輸入是由非關系高維數據特征構成的圖，如第 3.1.4 節中所介紹的。輸出是一組節點嵌入（Sec.3.2.1）。 因此，圖嵌入的問題可以被視為保持結構的降維問題，其假定輸入數據位于低維流形中。 有兩種類型的基于矩陣分解的圖嵌入。 一種是分解圖的拉普拉斯特征映射 ，另一種是直接分解節點鄰近矩陣 。 ### 圖的拉普拉斯算子 見解： 要保留的圖屬性可以解釋為成對節點的相似性。 因此，如果兩個具有較大相似性的節點相距很遠，則會施加較大的懲罰。 **表4：**基于圖的拉普拉斯特征映射的圖嵌入。 | GE算法 |  | 目標函數 | | --- | --- | --- | | MDS [74] |  歐氏距離  | 公式 2 | | Isomap [78] | KNN，  是沿著  到  最短路徑的邊權重之和 | 公式 2 | | LE [96] | KNN，  | 公式 2 | | LPP [97] | KNN，  | 公式 4 | | AgLPP [79] | 錨圖，  ，  ，  |  | | LGRM [98] | KNN，  |  | | ARE [88] | KNN，  ，  | `<6244>` | | SR [99] | KNN，   | `<6248>` | | HSL [87] |  ，其中  是歸一化的超圖的拉普拉斯算子 |  ，圣  | | MVU [100] | KNN，  ，圣  ，  和  ， | `<6255>` | | SLE [86] | KNN，  | `<6259>` | | MSHLRR [76] | 一般圖：KNN，  | 公式 2 | | | 超圖：  是一個夸張的重量  | | |  ，  | | [77] |  |  | | PUFS [75] | KNN，  | 公式 4 +（must 和 cannot 鏈接約束） | | RF-Semi-NMF-PCA [101] | KNN，  | 公式 2 +  （PCA）+  （k均值） | 基于以上見解，最優的嵌入  可以由以下目標函數[99]導出。  (1) 其中  是節點  和  之間的“定義的”相似性； 是圖的拉普拉斯。  是對角矩陣，其中 。  的值越大， 就更重要[97]。 約束  通常加于 Eq.1，來刪除嵌入中的任意縮放因子。 Eq.1 然后化簡為：  (2) 最優的  是特征問題  的最大特征值對應的特征向量。 上面的圖嵌入是漸進式的，因為它只能嵌入訓練集中存在的節點。 在實踐中，它可能還需要嵌入未在訓練中看到的新節點。 一種解決方案是設計線性函數  這樣只要提供了節點特征，就可以導出嵌入。 因此，對于歸納性的圖嵌入，Eq.1 變為在以下目標函數中找到最的 ：  (3) 與 Eq.2 相似，通過添加約束  ，公式 3 中的問題變成：  (4) 最優的  是  的解的最大特征值的特征向量。 現有研究的差異主要在于它們如何計算成對節點的相似性  ，以及它們是否使用線性函數  或不。 已經進行了一些嘗試[85,81]以使用一般框架總結現有的基于拉普拉斯特征圖的圖嵌入方法。 但他們的綜述只涵蓋了有限的工作量。 在表 4 中 ，我們總結了現有的基于拉普拉斯特征圖的圖嵌入研究，并比較了它們的  的計算方法，以及他們采用了什么樣的目標函數。 最初的研究 MDS [74]直接采用了兩個特征向量  和  之間的歐幾里德距離，作為 。公式 2 用于找到  的最佳嵌入。 MDS不考慮節點的鄰域，即，任何一對訓練實例都被認為是連接的。 后續研究（例如，[78,102,96,97]）通過首先從數據特征構建 k 最近鄰（KNN）圖來克服該問題。 每個節點僅與其前 k 個相似的鄰居連接。 之后，利用不同的方法來計算相似度矩陣 ，以便盡可能多地保留所需的圖屬性。 最近設計了一些更高級的模型。 例如，AgLPP [79]引入了錨圖，顯著提高早期矩陣分解模型 LPP 的效率。 LGRM [98]學習局部回歸模型來掌握圖結構，和樣本外數據外插值的全局回歸項。 最后，與以前的工作保留局部幾何不同，LSE [103]使用局部樣條回歸來保持全局幾何。 當輔助信息（例如，標簽，屬性）可用時，調整目標函數以保留更豐富的信息。 例如，[99]構造鄰接圖  和標記圖 。 目標函數由兩部分組成，一部分側重于保留數據集的局部幾何結構，如LPP [97]，另一部分試圖在標記的訓練數據上獲得具有最佳類的可分性的嵌入。 類似地，[88]也構造了兩個圖，即鄰接圖  編碼局部幾何結構，反饋關系圖  編碼用戶相關反饋中的成對關系。 RF-Semi-NMF-PCA [101]通過構建由三個部分組成的目標函數：PCA，k-means和圖的拉普拉斯正則化，同時考慮聚類，降維和圖嵌入。 其他一些工作認為  不能通過容易枚舉成對節點關系來構造。 相反，他們采用半定規劃（SDP）來學習  。 具體而言，SDP [104]的目的是找到一個內積矩陣，它最大化在圖中沒有連接的任何兩個輸入之間的成對距離，同時保留最近的鄰居距離。 MVU [100]構造這樣的矩陣，然后在習得的內積矩陣上應用MDS [74]。 [2]證明正則化LPP [97]相當于正則化SR [99]，如果  是對稱的，雙隨機的，PSD并且秩為  。 它構造了這種相似矩陣，從而有效地解決了類似LPP的問題。 **表5：**基于節點鄰近矩陣分解的圖嵌入。`O(*)`表示目標函數；例如，`O(SVM分類器)`表示SVM分類器的目標函數。 | GE算法 |  | 目標函數 | | --- | --- | --- | | [50] |  | 公式 5 | | SPE [105] | KNN，  ，約束為  | 公式 5 | | HOPE [106] | Katz 指數  ; 個性化的 Pagerank  | 公式 5 | | GraRep [21] |  ，其中  ，  | 公式 5 | | CMF [43] | PPMI | 公式 5 | | TADW [56] | PMI | 公式 5 和文本特征矩陣 | | [24] | `A` |  | | MMDW [48] | PMI | 公式 5 + `O(SVM分類器)` | | HSCA [57] | PMI | `O(MMDW)`+（ 一階鄰近度約束） | | MVE [107] | KNN，  | 公式 5 | | M-NMF [1] |  | 公式 5 + `O(社區檢測)` | | ULGE [2] |  ，其中  |  | | LLE [102] | KNN，  |  | | RESCAL [108] |  |  | | FONPE [109] | KNN，  |  ，約束為  | ### 節點鄰近矩陣分解 除了解決上述廣義特征值問題外，另一系列研究試圖直接分解節點鄰近矩陣。 見解： 使用矩陣分解可以在低維空間中近似節點鄰近度。 保持節點鄰近度的目標是最小化近似的損失。 給定節點鄰近矩陣  ，目標是：  (5) 其中  是節點嵌入，和  是上下文節點的嵌入[21]。 公式 5 旨在找到一個最優的秩為`d`的鄰近度矩陣`W`的近似（  是嵌入的維度）。 一種流行的解決方案是對  應用 SVD（奇異值分解）[110]。從形式上看，  (6) 其中  是按降序排序的奇異值，  和  是  的奇異向量 。 最佳嵌入使用最大的`d`個奇異值獲得 ，相應的奇異向量如下：  (7) 根據是否保留非對稱屬性，節點  的嵌入是  [21,50]，或  和  連接，即  [106]。 公式 5 存在其他解決方案，如正則化高斯矩陣分解[24]，低秩矩陣分解[56]，并加入其他正則化器來施加更多約束[48]。 我們總結了表 5 中所有基于節點鄰近度矩陣分解的圖嵌入。 總結：矩陣分解（MF）主要用于嵌入由非關系數據構建的圖（第 3.1.4 節），用于節點嵌入（第 3.2.1 節），這是圖的拉普拉斯特征映射問題的典型設定。 MF也用于嵌入同構圖[50,24]（第 3.1.1 節）。 ## 深度學習 深度學習（DL）在各種研究領域表現出色，如計算機視覺，語言建模等。基于DL的圖嵌入在圖上應用DL模型。 這些模型要么直接來自其他領域，要么是專門為嵌入圖數據設計的新神經網絡模型。 輸入是從圖中采樣的路徑或整個圖本身。 因此，我們基于是否采用隨機游走來從圖中采樣路徑，將基于DL的圖嵌入分為兩類。 ### 帶有隨機游走的基于 DL 的圖嵌入 見解： 通過最大化以自身嵌入為條件的，節點鄰域的觀測概率，可以在嵌入空間中保留圖中的二階鄰近度。 在第一類基于深度學習的圖嵌入中，圖被表示為從其采樣的一組隨機游走路徑。 然后將深度學習方法應用于用于圖嵌入的采樣路徑，保留路徑所承載的圖屬性。 鑒于上述見解，DeepWalk [17]采用神經語言模型（SkipGram）進行圖嵌入。 SkipGram [111]旨在最大化窗口內出現的單詞之間的共現概率  。 DeepWalk首先使用截斷的隨機游走，從輸入圖中采樣一組路徑（即，均勻地采樣最后訪問節點的鄰居，直到達到最大長度）。 從圖中采樣的每個路徑相當于來自語料庫的句子，其中節點相當于單詞。 然后將SkipGram應用于路徑，最大化節點鄰域的觀測概率，以自身嵌入為條件。 以這種方式，鄰域相似（二階鄰近度較大）的節點的嵌入相似。DeepWalk的目標函數如下：  (8) 其中  是窗口大小，它限制隨機游走上下文的大小。 SkipGram刪除了排序約束，并且 公式 8轉換為：  (9) 其中  使用softmax函數定義：  (10) 請注意，計算公式 10 是昂貴的，因為標準化因子（即，圖中每個節點的所有內積的總和），所以圖 10 的方法是不可行的。 通常有兩種解近似完全softmax的解決方案：分層softmax [112]和負采樣[112]。 分層softmax ：有為了效地解決中公式 10，構造二叉樹，其中節點被分配給葉子。 不像公式 10 那樣枚舉所有節點，僅需要求解從根到相應葉子的路徑。 優化問題變得最大化樹中特定路徑的概率。 假設到葉子  的路徑是一系列節點  ，其中`b0`為根，  。 公式 10 然后變成：  (11) 其中  是二分類器：。 表示 S 形函數。  是樹節點  的父節點的嵌入 。 分層softmax減少了SkipGram的時間復雜度，從  至 。 負采樣 ： 負采樣的關鍵思想是，使用邏輯回歸將目標節點與噪聲區分開來。 即，對于一個節點  ，我們想區分它的鄰居  來自其他節點。 噪音分布  用于繪制節點的負樣本  。公式 9 中的每個  然后計算為：  (12) 其中  是采樣的負節點數。  是一種噪聲分布，例如均勻分布（）。 具有負采樣的SkipGram的時間復雜度是 。 **表6：**帶有隨機游走路徑的基于深度學習的圖嵌入。 | GE算法 | 隨機游走方法 | 保留的鄰近度 | DL模型 | | --- | --- | --- | --- | | DeepWalk [17] | 截斷隨機游走 |  | SkipGram 和 分層 softmax（公式 11） | | [34] | 截斷隨機游走 |  （詞語-圖像） | 同上 | | GenVector [66] | 截斷隨機游走 |  （用戶 - 用戶和概念 - 概念） | 同上 | | 受限制的DeepWalk [25] | 邊權重采樣 |  | 同上 | | DDRW [47] | 截斷隨機游走 |  +分類一致性 | 同上 | | TriDNR [73] | 截斷隨機游走 |  （節點，單詞和標簽之間） | 同上 | | node2vec [28] | BFS + DFS |  | SkipGram 和負采樣（公式 12） | | UPP-SNE [113] | 截斷隨機游走 |  （用戶 - 用戶和個人資料 - 個人資料） | 同上 | | Planetoid [62] | 按標簽和結構對節點對進行采樣 |  +標簽標識 | 同上 | | NBNE [19] | 對節點的直接鄰居進行采樣 |  | 同上 | | DGK [93] | graphlet 核：隨機采樣[114] |  （通過graphlet） | SkipGram（公式11 - 12 ） | | metapath2vec [46] | 基于元路徑的隨機游走 |  | 異構 SkipGram | | ProxEmbed [44] | 截斷隨機游走 | 節點排名元組 | LSTM | | HSNL [29] | 截斷隨機游走 |  + QA排名元組 | LSTM | | RMNL [30] | 截斷隨機游走 |  +用戶問題質量排名 | LSTM | | DeepCas [63] | 基于馬爾可夫鏈的隨機游走 | 信息級聯序列 | GRU | | MRW-MN [36] | 截斷隨機游走 |  +跨模態特征差異 | DCNN + SkipGram | DeepWalk [17]的成功激發了許多后續研究，這些研究將深度學習模型（例如，SkipGram或長短期記憶（LSTM）[115]）應用于圖嵌入的采樣路徑。 我們在表 6中對它們進行了總結。 如表中所示，大多數研究遵循DeepWalk的想法，但改變隨機游戲的采樣方法（[25,28,62,62]）或要保留的鄰近度（定義 5和定義 6）的設定（[34,66,47,73,62]）。 [46]設計基于元路徑的隨機游走來處理異構圖和異構 SkipGram，它最大化了給定節點具有異構上下文的概率。 除了SkipGram之外，LSTM是圖嵌入中采用的另一種流行的深度學習模型。 請注意，SkipGram只能嵌入一個節點。 然而，有時我們可能需要將一系列節點嵌入為固定長度向量，例如，將句子（即，一系列單詞）表示為一個向量，就要在這種情況下采用LSTM來嵌入節點序列。 例如，[29]和[30]嵌入cQA站點中的問題/答案中的句子，[44]在兩個節點之間嵌入一系列節點，用于鄰近度嵌入。 在這些工作中優化排名損失函數，來保持訓練數據中的排名分數。 在[63]中，GRU [116]（即，類似于LSTM的遞歸神經網絡模型）用于嵌入信息級聯路徑。 #### 不帶隨機游走的基于 DL 的圖嵌入 見解： 多層學習架構是一種強大而有效的解決方案，可將圖編碼為低維空間。 第二類基于深度學習的圖嵌入方法直接在整個圖（或整個圖的鄰近矩陣）上應用深度模型。 以下是圖嵌入中使用的一些流行的深度學習模型。 自編碼器 ：自編碼器旨在最小化其編碼器輸入和解碼器輸出的重建誤差。 編碼器和解碼器都包含多個非線性函數。 編碼器將輸入數據映射到表示空間，并且解碼器將表示空間映射到重建空間。 采用自編碼器進行圖嵌入的思想，與鄰域保持方面的節點鄰近矩陣分解（Sec.4.1.2）相似。 具體而言，鄰接矩陣捕獲節點的鄰域。 如果我們將鄰接矩陣輸入到自編碼器，則重建過程將使具有相似鄰域的節點具有類似的嵌入。 深度神經網絡 ：作為一種流行的深度學習模型，卷積神經網絡（CNN）及其變體已廣泛應用于圖嵌入。 一方面，他們中的一些人直接使用為歐幾里德域設計的原始CNN模型，并重新格式化輸入圖以適應它。 例如，[55]使用圖標記，從圖中選擇固定長度的節點序列，然后使用 CNN 模型，組裝節點的鄰域來學習鄰域表示。 另一方面，一些其他工作試圖將深度神經模型推廣到非歐幾里德域（例如，圖）。 [117]在他們的綜述中總結了代表性研究。 通常，這些方法之間的差異在于，它們在圖上形成類似卷積的操作的方公式 一種方法是模擬卷積定理以定義譜域中的卷積 [118,119]。 另一種方法是將卷積視為空域中的鄰域匹配 [82,72,120]。 其他 ：還有一些其他類型的基于深度學習的圖嵌入方法。 例如，[35]提出了DUIF，它使用分層softmax作為前向傳播來最大化模塊性。 HNE [33]利用深度學習技術來捕獲異構成分之間的交互，例如，用于圖像的CNN和用于文本的FC層。 ProjE [40]設計了一個具有組合層和投影層的神經網絡。 它定義了知識圖嵌入的逐點損失（類似于多分類）和列表損失（即softmax回歸損失）。 我們在表 7 中總結了所有基于深度學習的圖嵌入方法（沒有隨機游走），并比較了它們使用的模型以及每個模型的輸入。 **表7：**基于深度學習的圖嵌入， 沒有隨機游走路徑。 | GE 算法 | 深度學習模型 | 模型輸入 | | --- | --- | --- | | SDNE [20] | 自編碼器 |  | | DNGR [23] | 堆疊去噪自編碼器 | PPMI | | SAE [22] | 稀疏自編碼器 |  | | [55] | CNN | 節點序列 | | SCNN [118] | 譜 CNN | 圖 | | [119] | 帶有光滑譜乘法器的譜 CNN | 圖 | | MoNet [80] | 混合模型網絡 | 圖 | | ChebNet [82] | 圖CNN又名ChebNet | 圖 | | GCN [72] | 圖卷積網絡 | 圖 | | GNN [120] | 圖神經網絡 | 圖 | | [121] | 自適應圖神經網絡 | 分子圖 | | GGS-NNs [122] | 自適應圖神經網絡 | 圖 | | HNE [33] | CNN + FC | 帶圖像和文本的圖 | | DUIF [35] | 分層深度模型 | 社會管理網絡 | | ProjE [40] | 神經網絡模型 | 知識圖 | | TIGraNet [123] | 圖卷積網絡 | 從圖像構造的圖 | 總結：由于它的威力和效率，深度學習已廣泛應用于圖嵌入。 在基于深度學習的圖嵌入方法中，已經觀察到三種類型的輸入圖（除了從非關系數據構建的圖（第 3.1.4 節））和所有四種類型的嵌入輸出。