## 基于邊重構的優化問題 總體見解： 基于節點嵌入建立的邊應盡可能與輸入圖中的邊相似。 第三類圖嵌入技術通過最大化邊重建概率，或最小化邊重建損失，來直接優化基于邊重建的目標函數。 后者進一步分為基于距離的損失和基于邊距的排名損失。 接下來，我們逐一介紹這三種類型。 ### 最大化邊重建概率 見解： 良好的節點嵌入最大化了在圖中觀察到的邊的生成概率。 良好的節點嵌入應該能夠重新建立原始輸入圖中的邊。 這可以通過使用節點嵌入最大化所有觀察到的邊（即，節點成對接近）的生成概率來實現。 節點對  和  之間的直接邊，表示它們的一階鄰近度 ，可以使用嵌入來計算  和  的聯合概率：  (13) 上述一階鄰近度存在于圖中的任何一對連接節點之間。 為了學習嵌入，我們最大化了在圖中觀察這些鄰域的對數似然。 然后將目標函數定義為：  (14) 同樣， 和  的二階鄰近度是條件概率  由  使用  和  生成：  (15) 它可以被解釋為在圖中隨機游走的概率，它開始于  結束于 。 因此圖嵌入目標函數是：  (16) 其中  是從圖中采樣的路徑中， 的集合。即來自每個采樣路徑的兩個端節點。 這模擬了二階鄰近度，作為從  到  的隨機游走的概率。 ### 最小化基于距離的損失 見解： 基于節點嵌入計算的節點鄰近度，應盡可能接近基于觀察到的邊計算的節點鄰近度。 具體來說，可以基于節點嵌入來計算節點鄰近度，或者可以基于觀察到的邊憑經驗計算節點鄰近度。 最小化兩種類型的鄰近度之間的差異，保持了相應的鄰近度。 對于一階鄰近度，可以使用公式 13 中定義的節點嵌入來計算它。 經驗概率是  ，其中  是邊  的權重。 和  兩者之間的距離越小，就能保持更好的一階鄰近度。 使用KL-散度作為距離函數來計算  和  間的差異，并且省略了一些常量，在圖嵌入中保留一階鄰近度的目標函數是：  (17) 同樣， 和  的二階鄰近度是由節點  生成的條件概率 （公式 15）。  的經驗概率計算為 ，其中  是節點的出度（無向圖的情況中是度） 。與公式 10 相似，計算公式 15 非常昂貴。 再次將負采樣用于近似計算來提高效率。 通過最小化  和  之間的 KL 差異，保持二階鄰近度的目標函數是：  (18) **表8：**基于邊重建的圖嵌入。  是指公式 14，16~19 之一。例如 ， （word-label）是指 公式 18，帶有單詞節點和標簽節點。  表示節點  的類型。 | GE算法 | 目標 | 鄰近度階數 | | --- | --- | --- | | PALE [18] |  （節點，節點） | 1 | | NRCL [4] |  （節點，鄰居節點）+  （屬性損失） | | PTE [124] |  （單詞，單詞）+  （單詞，文檔）+  （單詞，標簽） | | | APP [3] |  （節點，節點）） | | | GraphEmbed [83] |  （單詞，單詞）+  （單詞，時間）+  （單詞，位置）+  （時間，地點）+  （位置，位置）+  （時間，時間） | 2 | | [41,42] |  （車站，公司），  （車站，角色），  （目的地，出發地） | | PLE [84] |  （提示，類型）+  （提示，特性）+  （類型，類型） | | IONE [26] |  （節點，節點）+  （錨對齊） | | HEBE [45] |  （節點，超邊中的其他節點） | | GAKE [38] |  （節點，鄰居上下文）+  （節點，路徑上下文）+  （節點，邊上下文） | | CSIF [64] |  （用戶對，擴散內容） | | ESR [69] |  （實體，作者）+  （實體，實體）+  （實體，單詞）+  （實體，場地） | | LINE [27] |  （節點，節點）+  （節點，節點）） | | EBPR [71] |  （AUC 排名）+  （節點，節點）+  （節點，節點上下文） | 1 和 2 | | [94] |  （問題，答案） | 1，2 和 更高 | ### 最小化基于邊距的排名損失 在基于邊距的排名損失優化中，輸入圖的邊指代節點對之間的相關性。 圖中的一些節點通常與一組相關節點相關聯。 例如，在cQA網站中，一組答案被標記為與給定問題相關。 對損失的見解是直截了當的。 見解： 節點的嵌入更類似于相關節點的嵌入，而不是任何其他不相關節點的嵌入。  表示節點  和  的相似性得分，  表示與  相關的節點集，  表示不相關的節點集。 基于邊距的排名損失定義為：  (19) 其中  是邊距。 減少損失排名，可以促進  和  之間的巨大邊距，從而保證  的嵌入更接近其相關節點而不是任何其他不相關節點。 在表 8 中 ，我們基于其目標函數和保留的節點鄰近度，總結了基于邊重建的現有圖嵌入方法。 通常，大多數方法使用上述目標函數之一（公式 14，16~19）。 [71]優化 AUC 排名損失，這是基于邊距的排名損失的替代損失（公式 19 ）。 請注意，當在圖嵌入期間同時優化另一個任務時，該任務特定的目標將被納入總體目標中。 例如，[26]旨在對齊兩個圖。 因此，網絡對齊的目標函數與 （公式 18）一起優化。 值得注意的是，大多數現有知識圖嵌入方法選擇優化基于邊距的排名損失。 回想一下知識圖  由三元組  組成，表示頭部實體  通過關系  鏈接到尾部實體 。 嵌入  可以解釋為，保留真正三元組的排名  ，優于  中不存在的假的三元組 。 特別是在知識圖嵌入中，類似于公式 19 的 ，能量函數  為三元組  而設計。 這兩個函數之間略有不同。 表示節點嵌入  和  之間的相似性得分，而  是嵌入  和  在關系  方面的距離得分。 的一個例子是 ，其中關系表示為嵌入空間中的變換 [91]。 的其他選項總結在表 9 中。 因此，對于知識圖嵌入，公式 19 變為：  (20) 其中  是輸入知識圖中的三元組。 現有的知識圖嵌入方法主要是在他們的工作中優化公式 20。它們之間的區別在于  的定義，如表 9 所示。 知識圖嵌入相關工作的更多細節，已在 [13] 中進行了詳細的回顧。 **表9：**使用基于邊距的排名損失的知識圖嵌入。 | GE算法 | 能量函數  | | --- | --- | | TransE [91] |  | | TKRL [53] |  | | TransR [15] |  | | CTransR [15] |  | | TransH [14] |  | | SePLi [39] |  | | TransD [125] |  | | TranSparse [126] |  | | m-TransH [127] |  | | DKRL [128] |  | | ManifoldE [129] | 球面：  | | | 超平面：  | | |  是希爾伯特空間的映射函數 | | TransA [130] |  | | puTransE [43] |  | | KGE-LDA [60] |  | | SE [90] |  | | SME [92]線性 |  | | SME [92]雙線性 |  | | SSP [59] | ， | | NTN [131] |  | | HOLE [132] |  ，其中  是環形相關度 | | MTransE [133] |  | 請注意，一些研究聯合優化排名損失（公式式20 ）和其他目標來保留更多信息。 例如，SSP [59]使用公式 20 聯合優化了主題模型的丟失，將文本節點描述用于嵌入。 [133]對單語關系進行分類，并使用線性變換來學習實體和關系的跨語言對齊。 還存在一些工作，為三元組  定義匹配度分數而不是能量函數。 例如，[134]定義了雙線性分數函數  它增加了常態約束和交換約束，在嵌入之間加入類比結構。 ComplEx [135]將嵌入擴展到復數域并將  的實部定義為得分。 總結：基于邊重建的優化適用于大多數圖嵌入設定。 據我們所知，只有非關系數據（第 3.1.4 節）和整圖嵌入（第 3.2.4 節）尚未嘗試過。 原因是重建手動構造的邊不像其他圖那樣直觀。 此外，由于該技術側重于直接觀察到的局部邊，因此不適合于整圖嵌入。 ## 圖核 見解： 整個圖結構可以表示為一個向量，包含從中分解的基本子結構的數量。 圖核是 R-convolution 核的一個實例[136]，它是定義離散復合對象上的核的通用方法，通過遞歸地將結構化對象分解為“原子”子結構，并比較它們的所有對[93]。 圖核將每個圖示為向量，并且使用兩個向量的內積來比較兩個圖。 圖核中通常定義了三種類型的“原子”子結構。 Graphlet。graphlet 是一個大小為 K 的感應的和非同構子圖 [93]。 假設圖  被分解為一組 graphlet 。然后  嵌入為標準化計數的`d`維向量（表示為 ）。 該  的維度  是  中 Graphlet  的出現頻率。 子樹模式。 在此核中，圖被分解為其子樹模式。 一個例子是 Weisfeiler-Lehman 子樹[49]。 特別是，在標記圖（即，具有離散節點標簽的圖）上進行重新標記的迭代過程。 在每次迭代中，基于節點及其鄰居的標簽生成多集標簽。 新生成的多集標簽是一個壓縮標簽，表示子樹模式，然后用于下一次迭代。 基于圖同構的 Weisfeiler-Lehman 檢驗，計算圖中標簽的出現等同于計算相應的子樹結構。 假設  在圖上執行重新標記的迭代  。 它的嵌入  包含  塊。 該  中的維度  第一塊  是頻率  -th標簽被分配給一個節點  第二次迭代。 隨機游走 。 在第三種類型的圖核中，圖被分解為隨機游走或路徑，并表示為隨機游走的出現次數[137]或其中的路徑[138]。 以路徑為例，假設圖  被分解成  個最短路徑。將第`i`個路徑表示為三元組 ，其中  和  是起始節點和結束節點的標簽，  是路徑的長度。 然后  表示為`d`維向量 ，其中第`i`個維度是  中第`i`個三元組的頻率。 簡介：圖核專為整圖嵌入（Sec.3.2.4）而設計，因為它捕獲整個圖的全局屬性。 輸入圖的類型通常是同構圖（第 3.1.1 節）[93]或帶有輔助信息的圖（第 3.1.3 節）[49]。 ## 生成模型 生成模型可以通過規定輸入特征和類標簽的聯合分布來定義，以一組參數為條件[139]。 一個例子是 Latent Dirichlet Allocation（LDA），其中文檔被解釋為主題上的分布，主題是單詞上的分布[140]。 采用生成模型進行圖嵌入有以下兩種方法。 ### 潛在語義空間中的圖嵌入 見解： 節點嵌入到潛在的語義空間中，節點之間的距離解釋了觀察到的圖結構。 第一種基于生成模型的圖嵌入方法，直接在潛在空間中嵌入圖。 每個節點表示為潛在變量的向量。 換句話說，它將觀察到的圖視為由模型生成的。 例如，在LDA中，文檔嵌入在“主題”空間中，其中具有相似單詞的文檔具有類似的主題向量表示。 [70]設計了類似LDA的模型來嵌入基于位置的社交網絡（LBSN）圖。 具體來說，輸入是位置（文檔），每個位置包含訪問該位置的一組用戶（單詞）。 由于某些活動（主題），用戶訪問相同的位置（單詞出現在同一文檔中）。 然后，模型被設計為將位置表示為活動的分布，其中每個活動具有對用戶的吸引力分布。 因此，用戶和位置都表示為“活動”空間中的向量。 ### 包含潛在語義的圖嵌入 見解： 圖中接近且具有相似語義的節點的嵌入應該更緊密。 可以通過生成模型，從節點描述中檢測節點語義。 在這一系列方法中，潛在語義用于利用輔助節點信息進行圖嵌入。 嵌入不僅由圖結構信息決定，而且由從其他節點信息源發現的潛在語義決定。 例如，[58]提出了一個統一的框架，它共同集成了主題建模和圖嵌入。 其原理是如果嵌入空間中兩個節點接近，它們也具有相似的主題分布。 設計從嵌入空間到主題語義空間的映射函數，以便關聯兩個空間。 [141]提出了一種生成模型（貝葉斯非參數無限混合嵌入模型），以解決知識圖嵌入中的多關系語義問題。 它發現了關系的潛在語義，并利用混合關系組件進行嵌入。 [59]從知識圖三元組和實體和關系的文本描述中嵌入知識圖。 它使用主題建模來學習文本的語義表示，并將三元組嵌入限制在語義子空間中。 上述兩種方法的區別在于嵌入空間是第一種方式的潛在空間。相反，在第二種方式中，潛在空間用于整合來自不同來源的信息，并有助于將圖嵌入到另一個空間。 簡介：生成模型可用于節點嵌入（Sec.3.2.1）[70]和邊嵌入（Sec.3.2.2）[141]。 在考慮節點語義時，輸入圖通常是異構圖（第 3.1.2 節）[70]或帶有輔助信息的圖（第 3.1.3 節）[59]。 ## 混合技術和其它 有時在一項研究中結合了多種技術。 例如，[4]通過最小化基于邊的排序損失來學習基于邊的嵌入（第 4.3 節），并通過矩陣分解來學習基于屬性的嵌入（第 4.1 節）。 [51]優化基于邊距的排名損失（第 4.3 節），基于矩陣分解的損失（第 4.1 節）作為正則化項。 [32]使用LSTM（第 4.2節）來學習cQAs的句子的嵌入，以及基于邊際的排名損失（第[4.3](#sec:ml)節）來結合好友關系。 [142]采用CBOW / SkipGram（第 4.2 節）進行知識圖實體嵌入，然后通過最小化基于邊際的排名損失來微調嵌入（第 4.3 節）。 [61]使用word2vec（第 4.2 節）嵌入文本上下文和TransH（第 4.3 節）嵌入實體/關系，以便在知識圖嵌入中利用豐富的上下文信息。 [143]利用知識庫中的異構信息來提高推薦效果。 它使用TransR（第 4.3 節）進行網絡嵌入，并使用自編碼器進行文本和視覺嵌入（第 4.2 節）。 最后，提出了一個生成框架（第 4.5 節），結合協同過濾與項目的語義表示。 除了引入的五類技術之外，還存在其他方法。 [95]提出了根據原型圖距離的圖的嵌入。 [16]首先使用成對最短路徑距離嵌入一些標志性節點。 然后嵌入其他節點，使得它們到標志性子集的距離盡可能接近真實的最短路徑。 [4]聯合優化基于鏈接的損失（最大化節點的鄰居而不是非鄰居的觀測似然）和基于屬性的損失（基于基于鏈接的表示學習線性投影）。 KR-EAR [144]將知識圖中的關系區分為基于屬性和基于關系的關系。 它構造了一個關系三元編碼器（TransE，TransR）來嵌入實體和關系之間的相關性，以及一個屬性三元編碼器來嵌入實體和屬性之間的相關性。 Struct2vec [145]根據用于節點嵌入的分層指標，來考慮節點的結構性標識。 [146]通過近似高階鄰近矩陣提供快速嵌入方法。 ## 總結 我們現在總結并比較表10中所有五類圖嵌入技術的優缺點。 **表10：**圖嵌入技術的比較。 | 類別 | 子類別 | 優點 | 缺點 | | --- | --- | --- | --- | | 矩陣分解 | 圖拉普拉斯算子 | 考慮全局節點鄰近度 | 大量的時間和空間開銷 | | | 節點鄰近矩陣分解 | | | 深度學習 | 帶有隨機游走 | 有效而強大， | a）僅考慮路徑中的局部上下文 | | | | b）難以發現最優采樣策略 | | | 沒有隨機游走 | | 高計算開銷 | | 邊重構 | 最大化邊重建概率 | | 僅使用觀察到的局部信息來優化 | | | 最小化基于距離的損失 | 相對有效的的訓練 | 例如邊（一跳的鄰居） | | | 最小化基于邊距的排名損失 | | 或者排序節點對 | | 圖核 | 基于graphlet | 有效，只計算所需的原子子結構 | a）子結構不是獨立的 | | | 基于子樹模式 | | b）嵌入維度指數性增長 | | | 基于隨機游走 | | | 生成模型 | 在潛在的空間中嵌入圖 | 可解釋的嵌入 | a）難以證明分布的選擇 | | | 將潛在語義合并到圖嵌入中 | 自然地利用多個信息源 | b）需要大量訓練數據 | 基于矩陣分解的圖嵌入，基于全局成對相似性的統計量學習表示。 因此，它可以勝過某些任務中基于深度學習的圖嵌入（涉及隨機游走），因為后者依賴于單獨的局部上下文窗口 [147,148]。 然而，鄰近度矩陣構造或矩陣的特征分解時間和空間開銷大[149]，使得矩陣分解效率低且對于大圖不可擴展。 深度學習（DL）已經在不同的圖嵌入方法中顯示出有希望的結果。 我們認為DL適合于圖嵌入，因為它能夠自動識別復雜圖結構中的有用表示。 例如，具有隨機游走的DL（例如，DeepWalk [17]，node2vec [28]，metapath2vec [46]）可以通過圖上的采樣路徑自動利用鄰域結構。 沒有隨機游走的DL可以模擬同構圖中可變大小的子圖結構（例如，GCN [72]，struc2vec [145]，GraphSAGE [150]），或者異構圖中類型靈活的節點之間的豐富交互（例如，HNE [33]，TransE [91]，ProxEmbed [44]），變為有用的表示。 另一方面，DL也有其局限性。 對于具有隨機游走的DL，它通常觀測同一路徑中的節點的局部鄰居，從而忽略全局結構信息。 此外，很難找到“最優采樣策略”，因為嵌入和路徑采樣不是在統一框架中聯合優化的。 對于沒有隨機游走的DL，計算成本通常很高。 傳統的深度學習架構假設輸入數據在1D或2D網格上，來利用GPU [117]。 然而，圖沒有這樣的網格結構，因此需要不同的解決方案來提高效率[117]。 基于邊重建的圖嵌入，基于觀察到的邊或排序三元組來優化目標函數。 與前兩類圖嵌入相比，它更有效。 然而，使用直接觀察到的局部信息來訓練這一系列方法，因此所獲得的嵌入缺乏對全局圖結構的認識。 基于圖核的圖嵌入將圖轉換為單個向量，以便于圖級別的分析任務，例如圖分類。 它比其他類別的技術更有效，因為它只需要在圖中枚舉所需的原子子結構。 然而，這種“基于結構袋”的方法有兩個局限[93]。 首先，子結構不是獨立的。 例如，大小為`k+1`的 graphlet 可以從大小為`k` graphlet 的派生，通過添加新節點和一些邊。 這意味著圖表示中存在冗余信息。 其次，當子結構的大小增加時，嵌入維度通常呈指數增長，導致嵌入中的稀疏問題。 基于生成模型的圖嵌入可以自然地在統一模型中利用來自不同源（例如，圖結構，節點屬性）的信息。 直接將圖嵌入到潛在語義空間中，會生成可以使用語義解釋的嵌入。 但是使用某些分布對觀察進行建模的假設很難證明是正確的。 此外，生成方法需要大量的訓練數據來估計適合數據的適當模型。 因此，它可能不適用于小圖或少量圖。