## 三、圖嵌入的問題設定 在本節中，我們從問題設定的角度比較現有的圖嵌入工作，其中包括嵌入輸入和嵌入輸出。 對于每個設定，我們首先介紹不同類型的圖嵌入輸入或輸出，然后總結每個設定最后面臨的挑戰。 我們從圖嵌入輸入開始。 由于圖嵌入設定由輸入和輸出組成，我們在介紹不同類型的輸入期間，使用節點嵌入作為嵌入輸出設定的示例。 原因在于盡管存在各種類型的嵌入輸出，但是大多數圖嵌入研究集中于節點嵌入，即，將節點嵌入到低維空間中，其中保持輸入圖中的節點相似性。 有關節點嵌入和其他類型嵌入輸出的更多詳細信息，請參見 3.2 節。 ### 圖嵌入輸入 圖嵌入的輸入是圖。 在本綜述中，我們將圖嵌入輸入分為四類：同構圖，異構圖，輔助信息圖和構造圖。 每種類型的圖對圖嵌入提出了不同的挑戰。 接下來，我們介紹這四種類型的輸入圖，并總結每種輸入設定所面臨的挑戰。 #### 同構圖  **圖4：**加權和有向圖的示例。 第一類輸入圖是同構圖（定義 2），其中節點和邊分別屬于單一類型。 同構圖可以進一步分類為加權（或定向）和無權（或無向）圖，如圖 4 所示的示例。 無向和無權的同構圖是最基本的圖嵌入輸入設定。 許多研究都在這種情況下進行，例如 [1,16,17,18,19]。 它們平等地處理所有節點和邊，因為只有輸入圖的基本結構信息可用。 直觀上，邊的權重和方向提供了圖的更多信息，并且有助于在嵌入空間中更準確地表示圖。 例如，在圖 4（a）中，  應該比  更接近 ，因為邊的權重  更高。 同樣在圖 4（b）中，  應該比  更接近 ，因為  和  在兩個方向相連。 上述信息在無權和無向圖中丟失。 注意到利用圖邊的權重和方向屬性的優點，圖嵌入社區開始探索加權和/或有向圖。 其中一些只關注一個圖屬性，即邊權重或邊方向。 一方面，[20,21,22,23,24,25] 考慮了加權圖 。 通過較高加權邊連接的節點彼此靠得更近。 但是，他們的工作仍局限于無向圖。 另一方面，一些工作在嵌入過程中區分邊的方向并且保持嵌入空間中的方向信息。 有向圖的一個例子是社交網絡圖，例如[26]。 每個用戶都有其他用戶的粉絲和關注關系。 但是，權重信息不適用于社交用戶鏈接。 最近，提出了一種更通用的圖嵌入算法，其中考慮了權重和方向屬性。 換句話說，這些算法（例如，[27,3,28]）可以處理有向和無向，以及加權和無權圖 。 挑戰： 如何捕獲圖中觀察到的連接模式的多樣性？ 由于在同構圖中只有結構信息可用，因此同構圖嵌入的挑戰在于，如何在嵌入期間保留輸入圖中觀察到的這些連通模式。 #### 異構圖 第二類輸入是異構圖（定義 3），主要存在于以下三種情形中。 基于社區的問答（cQA）網站。 cQA 是一種基于互聯網的眾包服務，使用戶能夠在網站上發布問題，然后由其他用戶回答[29]。 直觀上，cQA 圖中存在不同類型的節點，例如問題，答案，用戶。 現有的 cQA 圖嵌入方法在它們利用的鏈接方面彼此區分，如表 2 所示 ，其中  表示 由用戶`j`提供的問題`i`的答案`k`，比用戶`p`的答案`o`獲得更多的投票（即點贊）。 **表2：** cQA站點的圖嵌入算法 | GE算法 | 利用的鏈接 | | --- | --- | | [30] | 用戶 - 用戶，用戶 - 問題 | | [31] | 用戶 - 用戶，用戶 - 問題，問題 - 回答 | | [29] | 用戶 - 用戶，問題 - 回答，用戶 - 回答 | | [32] | 用戶的不對稱關注鏈接，有序的元組  | 多媒體網絡。 多媒體網絡是包含多媒體數據的網絡，例如圖像，文本等。例如，[33]和[34]都嵌入了包含兩種節點（圖像和文本）和三種鏈接（圖像 - 圖像，文本 - 文本，文本 - 圖像）的圖。 [35]使用用戶節點和圖像節點處理社交管理。 它利用用戶圖像鏈接將用戶和圖像嵌入到同一空間中，以便可以直接比較它們來進行圖像推薦。 在[36]中，考慮了包含圖像和文本查詢的點擊圖。 圖像 - 查詢邊表示給定查詢的圖像的點擊，其中點擊計數用作邊權重。 知識圖。 在知識圖（定義 4）中，實體（節點）和關系（邊）通常是不同類型的。 例如，在從Freebase [37]構建的電影相關知識圖中，實體的類型可以是“導演”，“演員”，“電影”等。關系的類型可以是“制作”，“導演”， “參演”。 已經投入了大量精力來嵌入知識圖（例如，[38,39,40]）。 我們將在 4.3.3 節中詳細介紹它們。。 其他異構圖也存在。 例如，[41]和[42]從事于移動數據圖，其中車站（s），角色（r）和公司（c）節點由三種類型的鏈接（ss，sr，sc）連接。 [43]嵌入了維基百科圖，具有三種類型的節點（實體（e），類別（c）和單詞（w））和三種類型的邊（ee，ec，ww）。 除了上面的圖之外，還有一些通用的異構圖，其中節點和邊的類型沒有明確定義 [44,45,46]。 挑戰： 如何探索不同類型對象之間的全局一致性，以及如何處理屬于不同類型的對象的不平衡（如果有的話）？ 在異構圖嵌入中將不同類型的對象（例如，節點，邊）嵌入到相同空間中。 如何探索它們之間的全局一致性是一個問題。 而且，不同類型的對象之間可能存在不平衡。 嵌入時應考慮此數據偏差。 #### 帶有輔助信息的圖 第三類輸入圖除了包含節點的結構關系外，還包含節點/邊/整圖的輔助信息（即  ）。 通常，表 3 中列出了五種不同類型的輔助信息。 **表3：圖**中不同類型的輔助信息的比較 | 輔助信息 | 描述 | | --- | --- | | 標簽 | 節點/邊的類別值，例如，類別信息 | | 屬性 | 節點/邊的類別或連續值，例如，屬性信息 | | 節點特性 | 節點的文本或圖像特性 | | 信息傳播 | 信息在圖中的傳播路徑 | | 知識庫 | 與知識概念相關的文本或事實 | 標簽 ：具有不同標簽的節點應嵌入到彼此遠離的位置。 為了實現這一點，[47]和[48]聯合優化嵌入目標函數和分類器函數。 [49]對具有不同標簽的節點之間的相似性進行了懲罰。 [50]在計算不同的圖核時考慮節點標簽和邊標簽。 [51]和[52]嵌入了知識圖，其中實體（節點）具有語義類別。 [53]嵌入了更復雜的知識圖，它的實體類別在層次結構中，例如，類別“書”具有兩個子類別“作者”和“編寫工作”。 屬性：與標簽相反，屬性值可以是離散的或連續的。 例如，[54]嵌入具有離散節點屬性值的圖（例如，分子中的原子序數）。 相反，[4]將節點屬性表示為連續的高維向量（例如，社交網絡中的用戶屬性特征）。 [55]處理節點和邊的離散和連續屬性。 節點特征：大多數節點特征是文本，它們作為每個節點的特征向量 [56,57] 或作為文檔 [58,59,60,61] 提供。 對于后者，文檔被進一步處理，來使用諸如詞袋 [58]，主題建模 [59,60] 或將“單詞”視為一種節點 [61] 的技術來提取特征向量。 其他類型的節點特征，例如圖像特征[33]也是可能的。 節點特征通過提供豐富的非結構化信息來增強圖嵌入表現，這在許多實際圖中都可用。 此外，它使歸納的圖嵌入成為可能[62]。 信息傳播 ： 信息傳播的一個例子是Twitter中的“轉推”。 在[63]中，給出了數據圖  ，一個級聯圖  為每個級聯構建  ，其中  是擁有  的節點， 是  兩端的邊。 然后他們嵌入了  來預測級聯大小的增量。 與之不同，[64]旨在嵌入用戶和內容信息，使得它們的嵌入之間的相似性表示擴散概率。 Topo-LSTM [65]認為級聯不僅僅是一個節點序列，而是一個用于嵌入的動態有向非循環圖。 知識庫：流行的知識庫包括維基百科[66]，Freebase [37]，YAGO [67]，DBpedia [68]等。以維基百科為例，概念是用戶提出的實體，文本是與之相關的文章。 [66]使用知識庫通過將每個社交網絡用戶，鏈接到一組給定的知識概念，來從社交網絡學習社交知識圖。 [69]表示實體空間中的查詢和文檔（由知識庫提供），以便學術搜索引擎可以理解查詢中研究概念的含義。 其他類型的輔助信息包括用戶登記數據（用戶 - 位置）[70]，用戶項目偏好排序列表[71]等。注意，輔助信息不僅限于一種類型。 例如，[62]和[72]同時考慮標簽和節點特征信息。 [73]利用節點內容和標簽來輔助圖嵌入過程。 挑戰： 如何整合豐富的非結構化信息，以便學習的嵌入既代表拓撲結構又代表輔助信息中的不同？ 除了圖結構信息之外，輔助信息還有助于定義節點相似性。 使用輔助信息嵌入圖的挑戰，是如何組合這兩個信息源以定義要保留的節點相似性。 #### 從非關系數據構造的圖 輸入圖的最后一類從未提供，而是通過不同策略從非關系輸入數據構造。 當假設輸入數據位于低維流形中時，通常會發生這種情況。 在大多數情況下，輸入是特征矩陣 ，其中每一行  是一個  維的特征向量，表示第  個訓練實例。相似度矩陣  是（  ，  ）使用之間的相似性，通過計算  構建的。 通常有兩種方法來從  構建圖 。 一種直接的方式是直接將  看做無形圖的鄰接矩陣  [74]。 然而，[74]基于歐幾里德距離，并且在計算  時不考慮相鄰節點。 如果  位于彎曲的流形上或附近，  和  之間的距離，在流形上方比歐幾里德距離大得多[12]。 為了解決這些問題，其他方法（例如，[75,76,77]）首先從  構造了一個 K 最近鄰（KNN）圖 ，并基于 KNN 圖估計鄰接矩陣  。 例如，Isomap [78] 在  中包含了測地距離。 它首先構造一個 KNN 圖  ，然后找到兩個節點之間的最短路徑作為它們之間的測地距離。[79] 降低 KNN 圖構建的成本（  ），構造一個了錨圖，在時間和空間消耗方面，其成本是 。 他們首先獲得一組簇中心作為虛擬錨點，并找到每個節點的 K 個最近的錨點，用于構建錨圖。 圖構造的另一種方式是基于節點的共現，在節點之間建立邊。 例如，為了促進與圖像相關的應用（例如，圖像分割，圖像分類），研究人員（例如，[80,81,82]）通過將像素視為節點并將像素之間的空間關系視為邊來從每個圖像構建圖。 [83]從GTMS記錄中提取三種類型的節點（位置，時間和消息），因此在這些節點之間形成六種類型的邊。 [84]使用實體提示，目標類型和文本特征作為節點來生成圖，并建立三種邊：提示-類型，提示-特征和類型-類型。 除了基于上述成對相似性和基于節點共現的方法之外，還針對不同目的設計了其他圖構建策略。 例如，[85]構造一個內在圖來捕獲類內緊致性，以及一個懲罰圖來表示類間可分性。 前者是通過將每個數據點與同一類的鄰居連接而構建的，而后者則連接不同類別的邊點。 [86]構造一個有符號的圖來利用標簽信息。 如果兩個節點屬于同一個類，則它們通過正邊連接，如果它們來自兩個類，則為負邊。 [87]將包含相同標簽的所有實例包含在一個超邊中，來捕獲它們的聯合相似性。 在[88]中，構建了兩個反饋圖，將相關的對聚集在一起，并在嵌入之后遠離不相關的對。 在正圖中，如果兩個節點是相關的，則連接它們。 在負圖中，僅當一個節點相關而另一個節點不相關時，才連接兩個節點。 挑戰： 如何構建一個圖來編碼實例之間的成對關系，以及如何在嵌入空間中保留生成的節點鄰近度矩陣？ 嵌入由非關系數據構建的圖所面臨的第一個挑戰是，如何計算非關系數據之間的關系并構建這樣的圖。 在構建圖之后，挑戰變得與其他輸入圖中的相同，即，如何在嵌入空間中保持所構造的圖的節點接近度。 ### 圖嵌入輸出 圖嵌入的輸出是表示圖（的一部分）的（一組）低維向量。 基于輸出粒度，我們將圖嵌入輸出分為四類，包括節點嵌入，邊嵌入，混合嵌入和整圖嵌入。 不同類型的嵌入有助于不同的應用。 與固定和給定的嵌入輸入不同，嵌入輸出是任務驅動的。 例如，節點嵌入可以使各種節點相關的圖分析任務受益。 通過將每個節點表示為向量，可以在時間和空間方面有效地執行諸如節點聚類，節點分類之類的節點相關任務。 但是，圖分析任務并不總是節點級別的。 在某些情況下，任務可能與圖的更高粒度有關，例如節點對，子圖，甚至整圖。 因此，嵌入輸出方面的第一個挑戰，是如何找到滿足特定應用任務需求的合適類型的嵌入輸出。 #### 節點嵌入 作為最常見的嵌入輸出設定，節點嵌入將每個節點表示為低維空間中的向量。 嵌入圖中“接近”的節點具有類似的向量表示。 各種圖嵌入方法之間的區別，在于它們如何定義兩個節點之間的“接近度”。 一階接近度（定義 5）和二階接近度（定義 6）是成對節點相似度計算的兩個通常采用的度量。 在某些工作中，也在一定程度上探索了高階接近度。 例如，[21] 在潛入中捕獲了  步（）鄰居關系。 [1]和[89]都認為屬于同一社區的兩個節點的嵌入更近。 挑戰： 如何在各種類型的輸入圖中定義成對節點接近度，以及如何在習得的嵌入中編碼接近度？ 節點嵌入的挑戰主要來自于在輸入圖中定義節點接近度。 在第 3.1 節中，我們詳細闡述了帶有不同類型的輸入圖的節點嵌入的挑戰。 接下來，我們將介紹其他類型的嵌入輸出以及這些輸出帶來的新挑戰。 #### 邊嵌入 與節點嵌入相反，邊嵌入旨在將邊表示為低維向量。 邊嵌入在以下兩種方案中很有用。 首先，知識圖嵌入（例如，[90,91,92]）學習節點和邊的嵌入。 每個邊都是三元組  （定義 4）。嵌入的學習是為了在嵌入空間中保存  和  之間的  ，以便在給定  的其他兩個成分的情況下，可以正確預測缺失的實體/關系 。 其次，一些工作（例如，[28,64]）將節點對嵌入為向量特征，使節點對與其他節點可比，或預測兩個節點之間的鏈接。 例如，[64]提出了一種內容社交影響特征來預測給定內容的用戶 - 用戶交互概率。 它將用戶對和內容嵌入到同一空間中。 [28]在節點嵌入上，使用自舉方法嵌入一對節點，以便于預測圖中兩個節點之間是否存在鏈接。 總之，邊嵌入有利于邊（/節點對）相關的圖分析，例如鏈接預測，知識圖實體/關系預測等。 挑戰： 如何定義邊級別的相似性，以及如何模擬邊的不對稱屬性（如果有的話）？ 邊的接近度與節點接近度不同，因為邊包含一對節點并且通常表示成對節點關系。 而且，與節點不同，邊可以是有向的。 這種不對稱屬性應該編碼在習得的表示中。 #### 混合嵌入 混合嵌入是不同類型的圖成分的組合的嵌入，例如，節點+邊（即子結構），節點+社區。 在大量工作中子結構嵌入已經得到了研究。 例如，[44] 嵌入了兩個可能很遠的節點之間的圖結構，來支持語義鄰近搜索。 [93]學習子圖（例如，graphlet）的嵌入，以便定義用于圖分類的圖核。 [94]利用知識庫來豐富有關答案的信息。 它將問題實體中的路徑和子圖嵌入到答案實體中。 與子圖嵌入相比，社區嵌入僅受到有限的關注。 [1]建議考慮用于節點嵌入的社區感知鄰近度，使得節點的嵌入類似于其社區的嵌入。 ComE [89]還聯合解決了節點嵌入，社區檢測和社區嵌入。 它不是將社區表示為向量，而是將每個社區嵌入定義為多元高斯分布，以便表示其成員節點的分布方式。 子結構或社區的嵌入也可以通過聚合單個節點和其中的邊嵌入來導出。 然而，這種“間接”方法沒有為表示結構而優化。 此外，節點嵌入和社區嵌入可以相互促進。 通過結合社區感知的高階鄰近度來學習更好的節點嵌入，而當生成更準確的節點嵌入時，可以檢測到更好的社區。 挑戰： 如何生成目標子結構以及如何在一個公共空間中嵌入不同類型的圖成分？ 與其他類型的嵌入輸出相比，沒有給出混合嵌入（例如，子圖，社區）的嵌入目標。 因此，第一個挑戰是如何生成這種嵌入目標結構。 此外，不同類型的目標（例如，社區，節點）可以同時嵌入一個公共空間中。 如何解決嵌入目標類型的異構性是一個問題。 #### 整圖嵌入 最后一種類型的輸出是通常針對小圖的整圖嵌入，例如蛋白質，分子等。在這種情況下，圖被表示為一個向量，并且兩個相似的圖的嵌入更接近。 整圖嵌入有助于圖分類任務，為計算圖相似性提供了一種簡單有效的解決方案 [55,49,95]。 為了在嵌入時間（效率）和保存信息的能力（表現力）之間建立折衷，[95]設計了一個分層的圖嵌入框架。 它認為準確理解整圖信息需要處理不同尺度的子結構。 形成圖金字塔，其中每個級別是不同比例的圖的匯總。 該圖在所有級別上嵌入，然后連接成一個向量。 [63]學習整個級聯圖的嵌入，然后訓練一個多層感知器來預測未來級聯圖的大小增量。 挑戰： 如何捕捉整圖的屬性，以及如何在表現力和效率之間進行權衡？ 整圖嵌入需要捕獲整圖的屬性，因此與其他類型的嵌入相比更耗時。 整圖嵌入的關鍵挑戰是，如何在習得的嵌入的表現力和嵌入算法的效率之間做出選擇。