## 一、引言 圖自然存在于各種各樣的現實世界場景中，例如，社交媒體網絡中的社交圖/擴散圖，研究領域中的引用圖，電子商務區中的用戶興趣圖，知識圖等。這些圖的分析提供了如何充分利用隱藏在圖中的信息，因此在過去的幾十年中受到了極大的關注。 有效的圖分析可以使許多應用受益，例如節點分類 [1]，節點聚類 [2]，節點檢索/推薦 [3]，鏈接預測 [4]等。例如，通過分析基于的構建圖。在社交網絡中的用戶交互（例如，在Twitter中轉發/評論/關注），我們可以對用戶進行分類，檢測社區，推薦朋友，并預測兩個用戶之間是否會發生交互。 盡管圖分析是實用且必不可少的，但是大多數現有的圖分析方法具有高計算和空間成本。 許多研究工作致力于有效地進行昂貴的圖分析。 示例包括分布式圖數據處理框架（例如，GraphX [5]，GraphLab [6]），新的節省空間的圖存儲，它可以加速 I/O 和計算成本[7]，等等。 除了上述策略之外，圖嵌入提供了一種有效的方法來解決圖分析問題。 具體而言，圖嵌入將圖轉換為保存圖信息的低維空間。 通過將圖表示為（或一組）低維向量，圖算法可以有效地計算。 存在不同類型的圖（例如，同構圖，異構圖，屬性圖等），因此圖嵌入的輸入在不同場景中變化。 圖嵌入的輸出是表示圖（或整個圖）的一部分的低維向量。 圖1展示了以不同粒度將圖嵌入2D空間的玩具示例。 即，根據不同的需要，我們可以將節點/邊/子結構/整圖表示為低維向量。 有關不同類型的圖嵌入輸入和輸出的更多詳細信息，請參見第3節。 在21世紀初期，圖嵌入算法主要是通過假設數據位于低維流形中，來減少非關系數據的高維度。 給定一組非關系高維數據特征，基于成對特征相似性構建相似性圖。 然后，圖中的每個節點被嵌入到低維空間中，其中連接的節點彼此更接近。4.1 節介紹了這一系列研究的例子。。 自2010年以來，隨著圖在各個領域的激增，圖嵌入的研究開始以圖作為輸入并利用輔助信息（如果有的話）來促進嵌入。 一方面，它們中的一些專注于將圖的一部分（例如，節點，邊，子結構）（圖1（b）- 1（d））表示為一個向量。 為了獲得這種嵌入，他們要么采用最先進的深度學習技術（第 4.2 節），要么設計一個目標函數來優化邊重建概率（第 4.3 節）。 另一方面，還有一些工作集中在將整個圖嵌入一個向量，用于圖級應用（圖 1（e））。 圖核（第 4.4 節）通常旨在滿足此需求。  **圖1：**將圖嵌入具有不同粒度的2D空間的玩具示例。 圖嵌入問題與兩個傳統的研究問題有關，即圖分析[8]和表示學習[9]。 特別是，圖嵌入旨在將圖示為低維向量，同時保留圖結構。 一方面，圖分析旨在從圖數據中挖掘有用信息。 另一方面，表示學習獲得數據表示，使得在構建分類器或其他預測變量時，更容易提取有用信息[9]。 圖嵌入在兩個問題上重疊，并側重于學習低維表示。 請注意，我們在此綜述中區分了圖學習和圖嵌入。 圖表示學習不要求學習的表示是低維的。 例如，[10]將每個節點表示為向量，其維數等于輸入圖中的節點數。 每個維度表示節點與圖中每個其他節點的測地距離。 將圖嵌入低維空間并非易事。 圖嵌入的挑戰取決于問題設定 ，包括嵌入輸入和嵌入輸出。 在本綜述中，我們將輸入圖分為四類，包括同構圖，異構圖，輔助信息 圖和非關系數據圖 。 不同類型的嵌入輸入攜帶不同的信息來保留在嵌入空間中，因此對圖嵌入的問題提出了不同的挑戰。 例如，當僅嵌入具有結構信息的圖時，節點之間的連接是要保留的目標。 但是，對于具有節點標簽或屬性信息的圖，輔助信息從其他視角提供圖屬性，因此在嵌入期間也可以考慮。 與給定和固定的嵌入輸入不同， 嵌入輸出是任務驅動的。 例如，最常見的嵌入輸出類型是節點嵌入，其將鄰近節點表示為類似向量。 節點嵌入可以使節點相關的任務受益，例如節點分類，節點聚類等。然而，在某些情況下，任務可能與圖的更高粒度有關，例如，節點對，子圖，整個圖。 因此，在嵌入輸出方面的第一個挑戰，是為感興趣的應用找到合適的嵌入輸出類型。 我們對四種類型的圖嵌入輸出進行了分類，包括節點嵌入，邊嵌入，混合嵌入和整圖嵌入 。 不同的輸出粒度對于“良好”嵌入具有不同的標準并且面臨不同的挑戰。 例如，良好的節點嵌入保持嵌入空間中的相鄰節點的相似性。 相反，良好的整圖嵌入將整個圖示為向量，從而保持圖級相似性。 在不同問題設定中面臨的挑戰的觀察中，我們通過基于問題設定和嵌入技術對圖嵌入文獻進行分類，提出了兩種圖嵌入工作的分類法。 這兩種分類法對應于圖嵌入中存在的挑戰以及現有研究如何應對這些挑戰。 特別是，我們首先介紹圖嵌入問題的不同設置以及每個設置中面臨的挑戰。 然后，我們描述現有研究如何在他們的工作中應對這些挑戰，包括他們的見解和技術解決方案。 請注意，雖然已經有了一些圖嵌入的綜述（[11,12,13]），但它們有以下兩個限制。 首先，他們通常只提出一種圖嵌入技術的分類。 他們都沒有從問題設定的角度分析圖嵌入工作，也沒有總結每個環境中的挑戰。 其次，現有的圖嵌入綜述僅涉及有限數量的相關工作。 例如，[11]主要介紹了十二種代表性的圖嵌入算法，[13]只關注知識圖嵌入。 此外，沒有分析每種圖嵌入技術背后的洞察力。 對現有圖嵌入工作的全面回顧，以及對每種嵌入技術的洞察力的高級抽象，可以促進該領域的未來研究。 下面，我們總結了本次綜述的主要貢獻。 我們提出了基于問題設定的圖嵌入分類法，并總結了每個環境中面臨的挑戰。 我們是第一個基于問題設定對圖嵌入工作進行分類的綜述，它為理解現有工作帶來了新的視角。 我們提供了圖嵌入技術的詳細分析。 與現有的圖嵌入綜述相比，我們不僅研究了更全面的圖嵌入工作集，而且還總結了每種技術背后的見解。 與簡單地列出過去如何解決圖嵌入相反，總結的見解回答了為什么可以以某種方式解決圖嵌入的問題。 這可以作為未來研究的深刻見解。 我們系統地對使用圖嵌入的應用進行分類，并將應用劃分為節點相關，邊相關和圖相關。 對于每個類別，我們提供詳細的應用場景作為參考。 我們建議了圖嵌入領域的四個有前途的未來研究方向，包括計算效率，問題設定，解決方案技術和應用。 對于每個方向，我們對其在當前工作中的缺點（不足）進行全面分析，并提出未來的研究方向。 本次綜述的其余部分安排如下。 在第二節中，我們介紹理解圖嵌入問題所需的基本概念的定義，然后提供圖嵌入的形式問題定義。 在接下來的兩節中，我們提供了兩種圖嵌入分類法，其中分類法結構如圖 2 所示。第 3 節基于問題設定比較了相關工作，并總結了每個設置中面臨的挑戰。 在第 4 節中，我們基于嵌入技術對文獻進行分類。抽象出每種技術背后的見解，并在最后提供不同技術的詳細比較。 之后在第 5 節中，我們將介紹圖嵌入的應用。 然后，我們在第六節中將討論中未來的四個研究方向，并在第七節結束本綜述。  **圖 2：**根據問題和技術的圖嵌入分類法。 ## 二、問題形式化 在本節中，我們首先介紹圖嵌入中基本概念的定義，然后提供圖嵌入問題的正式定義。 ### 符號和定義 本綜述中使用的符號的詳細說明見表 1 。 **表1：**本文中使用的符號。 | 符號 | 說明 | | | --- | --- | --- | |  | 集合的基數 | | |  =  | 帶有節點  和邊  的圖  | | |  =  | 圖  的子結構，其中  | | |  ，  | 節點  和連接  和  的邊  | | |  | 接鄰矩陣  | | |  | 矩陣 A 的第 i 行向量 | |  | 矩陣 A 的第 i 行第 j 列 | | |  ，  | 節點  類型和邊  的類型 | | |  ，  | 節點類型集和邊類型集 | | |  | 節點  的k個最近鄰居 | | |  | 特征矩陣，每行  是  的  維向量 | | |  ，  ，  | 節點  ，邊  和結構  的嵌入 | | |  | 嵌入的維度 | | | `<h, r, t>` | 知識圖三元組，具有頭部實體  ， | | | | 尾部實體  以及他們之間的關系  | |  ，  | 節點  和  之間的一階和二階鄰近度 | | |  | 信息級聯 | | |  | 擁有級聯  的級聯圖 | | 圖是  = ，其中  是一個節點， 是一個邊。 關聯節點類型的映射函數  和邊類型的映射函數 。  和  分別表示節點類型和邊類型的集合。 每個節點  屬于一種特定類型，即 。 同樣，對于 ，。 同構圖  =_  是一個圖，滿足 。 中的所有節點屬于單一類型，所有邊都屬于單一類型。 異構圖  =  是一個圖，滿足  和/或 。 知識圖  =  是一個有向圖，其節點是實體 ，邊是主體 - 屬性 - 客體三元組。形式為（ 頭部實體 ， 關系，尾部實體）的每個邊（表示為 ）表示關系  來自實體  到實體 。  是實體， 是關系。 在本綜述中，我們將  稱作知識圖三元組。 例如，在圖 3 中，有兩個三元組： 和 。 請注意，知識圖中的實體和關系通常具有不同的類型[14,15]。因此，知識圖可以被視為異構圖的實例。  **圖3：**知識圖的玩具示例。 通常采用以下鄰近度量來量化要在嵌入空間中保留的圖屬性。 一階鄰近度是僅由邊連接的節點之間的局部成對相似性。 它比較節點對之間的直接連接強度。 從形式上看， 節點  和節點  之間的一階鄰近度是邊  的權重，即 。 如果兩個節點由具有較大權重的邊連接，則它們更相似。 表示節點  和  之間的一階鄰近度， 我們有 。 讓  表示  和其他節點的一階鄰近度。 以圖 1（a）中的圖為例， 和  的一階鄰近度是邊的權重 ，表示為 。 記錄  和圖中的其他節點的邊的權重，即 。 二階鄰近度比較節點的鄰域結構的相似性。 兩個節點的鄰域越相似，它們之間的二階鄰近度越大。從形式上看， 節點  和 之間的二階鄰近度  是  的鄰居_ _ 和  的鄰居  的相似度。 再次，以圖[1（a）](#fig:ig)為例：  是  和  的相似度。 如前所述，  并且  。 讓我們考慮余弦相似度  和 。 我們可以看到  和  之間的鄰近度等于零， 和  沒有任何共同鄰居。  和  有一個共同的鄰居 ，因此他們的二階鄰近度  大于零。 可以同樣定義更高階的鄰近度 。 例如，節點  和  之間的 K 階鄰近度是  和  的相似度。 請注意，有時高階鄰近度也使用其他一些指標來定義，例如 Katz Index，Rooted PageRank，Adamic Adar 等[11]。 值得注意的是，在一些工作中，一階和二階鄰近度是基于兩個節點的聯合概率和條件概率憑經驗計算的。 更多細節將在 4.3.2 中討論。 圖嵌入：給定圖的輸入  = ，以及嵌入的預定義維度  （），圖嵌入的問題是，將  轉換為一個  維空間，其中盡可能保留圖屬性。可以使用諸如一階和更高階鄰近度來量化圖特性。每個圖都表示為  維向量（對于整圖）或一組  維向量，每個向量表示圖的一部分的嵌入（例如，節點，邊，子結構）。 圖1顯示了嵌入圖的玩具示例  。 給定一個輸入圖（圖[1（a）](#fig:ig) ），圖嵌入算法用于將節點（圖[1（b）](#fig:ne) ）/邊（圖[1（c）](#fig:ee) ），子結構（圖[1（d））](#fig:se) ）/整圖（圖[1（e）](#fig:we) ）轉換為2D向量（即2D空間中的點）。 在接下來的兩節中，我們分別基于問題設定和嵌入技術，對圖嵌入文獻進行分類，提供了兩種圖嵌入分類法。