<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 四、圖嵌入技術 在本節中,我們基于所使用的技術對圖嵌入方法進行分類。 通常,圖嵌入旨在在低維空間中表示圖,保留盡可能多的圖屬性信息。 不同圖嵌入算法之間的區別在于,它們如何定義要保留的圖屬性。 不同的算法對節點(邊、子結構、整圖)的相似性,以及如何在嵌入空間中保留它們,有不同的見解。 接下來,我們將介紹每種圖嵌入技術的見解,以及它們如何量化圖屬性并解決圖嵌入問題。 ## 矩陣分解 基于矩陣分解的圖嵌入,以矩陣的形式表示圖特性(例如,節點成對相似性)并對該矩陣進行分解來獲得節點嵌入[11]。 圖嵌入的開創性研究通常以這種方式解決圖嵌入問題。 在大多數情況下,輸入是由非關系高維數據特征構成的圖,如第 3.1.4 節中所介紹的。輸出是一組節點嵌入(Sec.3.2.1)。 因此,圖嵌入的問題可以被視為保持結構的降維問題,其假定輸入數據位于低維流形中。 有兩種類型的基于矩陣分解的圖嵌入。 一種是分解圖的拉普拉斯特征映射 ,另一種是直接分解節點鄰近矩陣 。 ### 圖的拉普拉斯算子 見解: 要保留的圖屬性可以解釋為成對節點的相似性。 因此,如果兩個具有較大相似性的節點相距很遠,則會施加較大的懲罰。 **表4:**基于圖的拉普拉斯特征映射的圖嵌入。 | GE算法 | ![](https://img.kancloud.cn/5e/88/5e88ead495352c252fc0f925364a7657_24x14.png) | 目標函數 | | --- | --- | --- | | MDS [74] | ![](https://img.kancloud.cn/23/d0/23d0261e61810b3151191df9bfacbd3b_47x30.png) 歐氏距離 ![](https://img.kancloud.cn/bd/60/bd60c64ad8c518de47a1474be17f5c32_62x32.png) | 公式 2 | | Isomap [78] | KNN, ![](https://img.kancloud.cn/2e/b1/2eb1a2ad70196e53c4243c6170cd74ff_31x30.png) 是沿著 ![](https://img.kancloud.cn/07/40/0740edb420c2cc4fd3da7398d2deb689_17x31.png) 到 ![](https://img.kancloud.cn/99/ca/99ca1db217ecc34711addcbc6a025696_19x31.png) 最短路徑的邊權重之和 | 公式 2 | | LE [96] | KNN, ![](https://img.kancloud.cn/dc/16/dc1630509c514fe44f9f7ceb3d1d82e5_153x44.png) | 公式 2 | | LPP [97] | KNN, ![](https://img.kancloud.cn/38/1a/381a48e30dd7a0be673a5879ac08f966_153x44.png) | 公式 4 | | AgLPP [79] | 錨圖, ![](https://img.kancloud.cn/53/57/5357782fa352f98bbc7f333b11898580_105x17.png) , ![](https://img.kancloud.cn/db/23/db2356660d1b67f3575676f88917921d_93x31.png) , ![](https://img.kancloud.cn/9e/96/9e9638721f1da2052ec55b93e64d61e5_136x40.png) | ![](https://img.kancloud.cn/6c/e2/6ce2a17e1301e0dd99005d914f5a2068_161x41.png) | | LGRM [98] | KNN, ![](https://img.kancloud.cn/dc/16/dc1630509c514fe44f9f7ceb3d1d82e5_153x44.png) | ![](https://img.kancloud.cn/35/a1/35a1614a6fa7f8335068a4101648d673_183x46.png) | | ARE [88] | KNN, ![](https://img.kancloud.cn/42/1a/421aad02e8433ef300ea2c7c9992a1b3_157x44.png) , ![](https://img.kancloud.cn/fb/69/fb69b79b173d3ec12833226fbbc3aac5_268x81.png) | `<6244>` | | SR [99] | KNN, ![](https://img.kancloud.cn/85/73/85736e1a764889678e729684c1982ca6_204x81.png) ![](https://img.kancloud.cn/3f/e8/3fe86fe8886bb4d7766be4189e9f4fa7_272x63.png) | `<6248>` | | HSL [87] | ![](https://img.kancloud.cn/a5/e6/a5e63709faeece3d027435df675ef7c5_75x30.png) ,其中 ![](https://img.kancloud.cn/98/6a/986a10141d389488092a1aba26ca46c3_15x14.png) 是歸一化的超圖的拉普拉斯算子 | ![](https://img.kancloud.cn/a0/bc/a0bc36ef18146361466f54354ad76763_201x35.png) ,圣 ![](https://img.kancloud.cn/b8/94/b894a384aed88e92f2e0f4d5d961ee3a_106x35.png) | | MVU [100] | KNN, ![](https://img.kancloud.cn/41/aa/41aa8206ffb7545d68981a86d1091fc0_150x32.png) ,圣 ![](https://img.kancloud.cn/36/a2/36a2484206d633c519dd2c6538798b1d_51x30.png) , ![](https://img.kancloud.cn/25/4c/254c3efd400df717dc5dca1c5154c357_90x31.png) 和 ![](https://img.kancloud.cn/b2/73/b2731a938960889aa96fc9a51762dbd5_33x30.png) , | `<6255>` | | SLE [86] | KNN, ![](https://img.kancloud.cn/b8/78/b878432482fbbd078d471e75b202c7a9_263x63.png) | `<6259>` | | MSHLRR [76] | 一般圖:KNN, ![](https://img.kancloud.cn/eb/69/eb69cebeed4c8f0ca5f09dc95e18ce01_60x30.png) | 公式 2 | | | 超圖: ![](https://img.kancloud.cn/8e/00/8e00aa345f3aba31a196adea1955c0e3_42x32.png) 是一個夸張的重量 ![](https://img.kancloud.cn/47/28/4728f90fb1a1e9e2c93bca8c7e1df59b_13x17.png) | | | ![](https://img.kancloud.cn/34/b6/34b6b1d63de2738f0d825e3f83eb8584_186x63.png) , ![](https://img.kancloud.cn/5e/c7/5ec77fd5905b2498ae67eb7dceb54616_143x32.png) | | [77] | ![](https://img.kancloud.cn/df/15/df154afe5c643daa7df4b5a4c4107b4a_324x64.png) | ![](https://img.kancloud.cn/bd/f6/bdf6c8afb8173f6ebc00a586ac1a2ddc_283x43.png) | | PUFS [75] | KNN, ![](https://img.kancloud.cn/1d/e4/1de4f32514f91131a7a792c58de8ca6e_166x44.png) | 公式 4 +(must 和 cannot 鏈接約束) | | RF-Semi-NMF-PCA [101] | KNN, ![](https://img.kancloud.cn/eb/69/eb69cebeed4c8f0ca5f09dc95e18ce01_60x30.png) | 公式 2 + ![](https://img.kancloud.cn/b4/63/b4636a53741812a77d097d6ae690d6df_17x15.png) (PCA)+ ![](https://img.kancloud.cn/b4/63/b4636a53741812a77d097d6ae690d6df_17x15.png) (k均值) | 基于以上見解,最優的嵌入 ![](https://img.kancloud.cn/ba/60/ba60e8da949bf5de597576c93217cfa5_13x31.png) 可以由以下目標函數[99]導出。 ![](https://img.kancloud.cn/f9/e9/f9e90b9ca402df032f2200a38fdabe8d_349x40.png) (1) 其中 ![](https://img.kancloud.cn/2e/b1/2eb1a2ad70196e53c4243c6170cd74ff_31x30.png) 是節點 ![](https://img.kancloud.cn/07/40/0740edb420c2cc4fd3da7398d2deb689_17x31.png) 和 ![](https://img.kancloud.cn/99/ca/99ca1db217ecc34711addcbc6a025696_19x31.png) 之間的“定義的”相似性;![](https://img.kancloud.cn/b8/95/b89502f53029b0d57cbc5160f31b6188_76x30.png) 是圖的拉普拉斯。 ![](https://img.kancloud.cn/c1/1b/c11be425218481db75d2743198b5e450_18x14.png) 是對角矩陣,其中 ![](https://img.kancloud.cn/fd/dd/fddd08cde4586079724c9d73fa17a72b_114x31.png)。 ![](https://img.kancloud.cn/fb/5e/fb5ec439ffbe0ce75efe9d68864f872e_27x30.png) 的值越大,![](https://img.kancloud.cn/7e/e4/7ee443153fbc64825deddfa561048c6b_17x31.png) 就更重要[97]。 約束 ![](https://img.kancloud.cn/31/76/31762872c07bc5dcccd8fd2f7a017fad_74x35.png) 通常加于 Eq.1,來刪除嵌入中的任意縮放因子。 Eq.1 然后化簡為: ![](https://img.kancloud.cn/29/da/29da565bae6332d92fc6e11cd4439564_406x56.png) (2) 最優的 ![](https://img.kancloud.cn/ba/60/ba60e8da949bf5de597576c93217cfa5_13x31.png) 是特征問題 ![](https://img.kancloud.cn/bc/17/bc175cdc323357bb88d3dada94363a9a_82x30.png) 的最大特征值對應的特征向量。 上面的圖嵌入是漸進式的,因為它只能嵌入訓練集中存在的節點。 在實踐中,它可能還需要嵌入未在訓練中看到的新節點。 一種解決方案是設計線性函數 ![](https://img.kancloud.cn/3f/d9/3fd9f3783fb5a0858cf8ca21866c66b9_67x35.png) 這樣只要提供了節點特征,就可以導出嵌入。 因此,對于歸納性的圖嵌入,Eq.1 變為在以下目標函數中找到最的 ![](https://img.kancloud.cn/88/87/8887d6387a6eea05f61ce15300cfa569_13x17.png): ![](https://img.kancloud.cn/06/16/0616f24107f3b4c682deb13b0a7a7cff_404x43.png) (3) 與 Eq.2 相似,通過添加約束 ![](https://img.kancloud.cn/11/53/11533af07b7ce452f0c9f0015f487105_113x17.png) ,公式 3 中的問題變成: ![](https://img.kancloud.cn/e2/b9/e2b9b875cd7c67e842287db3a05f0cb9_343x56.png) (4) 最優的 ![](https://img.kancloud.cn/88/87/8887d6387a6eea05f61ce15300cfa569_13x17.png) 是 ![](https://img.kancloud.cn/0e/2f/0e2fafc72f83af90e24544f8503f9993_160x17.png) 的解的最大特征值的特征向量。 現有研究的差異主要在于它們如何計算成對節點的相似性 ![](https://img.kancloud.cn/2e/b1/2eb1a2ad70196e53c4243c6170cd74ff_31x30.png) ,以及它們是否使用線性函數 ![](https://img.kancloud.cn/3f/d9/3fd9f3783fb5a0858cf8ca21866c66b9_67x35.png) 或不。 已經進行了一些嘗試[85,81]以使用一般框架總結現有的基于拉普拉斯特征圖的圖嵌入方法。 但他們的綜述只涵蓋了有限的工作量。 在表 4 中 ,我們總結了現有的基于拉普拉斯特征圖的圖嵌入研究,并比較了它們的 ![](https://img.kancloud.cn/56/57/56571fc001c18aa9a087836fe41bcb8f_22x15.png) 的計算方法,以及他們采用了什么樣的目標函數。 最初的研究 MDS [74]直接采用了兩個特征向量 ![](https://img.kancloud.cn/41/bd/41bd77c4fbd53cee500f6a1baeb6d436_23x30.png) 和 ![](https://img.kancloud.cn/84/93/8493016386e3155ec250f8bfbe1d2651_24x30.png) 之間的歐幾里德距離,作為 ![](https://img.kancloud.cn/2e/b1/2eb1a2ad70196e53c4243c6170cd74ff_31x30.png)。公式 2 用于找到 ![](https://img.kancloud.cn/ba/60/ba60e8da949bf5de597576c93217cfa5_13x31.png) 的最佳嵌入。 MDS不考慮節點的鄰域,即,任何一對訓練實例都被認為是連接的。 后續研究(例如,[78,102,96,97])通過首先從數據特征構建 k 最近鄰(KNN)圖來克服該問題。 每個節點僅與其前 k 個相似的鄰居連接。 之后,利用不同的方法來計算相似度矩陣 ![](https://img.kancloud.cn/56/57/56571fc001c18aa9a087836fe41bcb8f_22x15.png),以便盡可能多地保留所需的圖屬性。 最近設計了一些更高級的模型。 例如,AgLPP [79]引入了錨圖,顯著提高早期矩陣分解模型 LPP 的效率。 LGRM [98]學習局部回歸模型來掌握圖結構,和樣本外數據外插值的全局回歸項。 最后,與以前的工作保留局部幾何不同,LSE [103]使用局部樣條回歸來保持全局幾何。 當輔助信息(例如,標簽,屬性)可用時,調整目標函數以保留更豐富的信息。 例如,[99]構造鄰接圖 ![](https://img.kancloud.cn/56/57/56571fc001c18aa9a087836fe41bcb8f_22x15.png) 和標記圖 ![](https://img.kancloud.cn/84/56/8456a5f77e84dfb4c7305fe22091f858_40x17.png)。 目標函數由兩部分組成,一部分側重于保留數據集的局部幾何結構,如LPP [97],另一部分試圖在標記的訓練數據上獲得具有最佳類的可分性的嵌入。 類似地,[88]也構造了兩個圖,即鄰接圖 ![](https://img.kancloud.cn/56/57/56571fc001c18aa9a087836fe41bcb8f_22x15.png) 編碼局部幾何結構,反饋關系圖 ![](https://img.kancloud.cn/84/ac/84ac08b460e1a5ce5227e275ae4716ce_52x17.png) 編碼用戶相關反饋中的成對關系。 RF-Semi-NMF-PCA [101]通過構建由三個部分組成的目標函數:PCA,k-means和圖的拉普拉斯正則化,同時考慮聚類,降維和圖嵌入。 其他一些工作認為 ![](https://img.kancloud.cn/56/57/56571fc001c18aa9a087836fe41bcb8f_22x15.png) 不能通過容易枚舉成對節點關系來構造。 相反,他們采用半定規劃(SDP)來學習 ![](https://img.kancloud.cn/56/57/56571fc001c18aa9a087836fe41bcb8f_22x15.png) 。 具體而言,SDP [104]的目的是找到一個內積矩陣,它最大化在圖中沒有連接的任何兩個輸入之間的成對距離,同時保留最近的鄰居距離。 MVU [100]構造這樣的矩陣,然后在習得的內積矩陣上應用MDS [74]。 [2]證明正則化LPP [97]相當于正則化SR [99],如果 ![](https://img.kancloud.cn/56/57/56571fc001c18aa9a087836fe41bcb8f_22x15.png) 是對稱的,雙隨機的,PSD并且秩為 ![](https://img.kancloud.cn/ef/38/ef3882369e8ef4e2a173ed228a7b8679_12x31.png) 。 它構造了這種相似矩陣,從而有效地解決了類似LPP的問題。 **表5:**基于節點鄰近矩陣分解的圖嵌入。`O(*)`表示目標函數;例如,`O(SVM分類器)`表示SVM分類器的目標函數。 | GE算法 | ![](https://img.kancloud.cn/5e/88/5e88ead495352c252fc0f925364a7657_24x14.png) | 目標函數 | | --- | --- | --- | | [50] | ![](https://img.kancloud.cn/27/6b/276b9fa9eebbcdfa18f723aaf942077f_167x63.png) | 公式 5 | | SPE [105] | KNN, ![](https://img.kancloud.cn/ec/14/ec14990a8ec545fb1f6520c5083ef8d1_162x38.png) ,約束為 ![](https://img.kancloud.cn/df/0a/df0a67f2c4694b056134df4e88a0be0b_213x38.png) | 公式 5 | | HOPE [106] | Katz 指數 ![](https://img.kancloud.cn/b3/37/b337afb3d8aba35b8e169b750e3d58ea_142x34.png) ; 個性化的 Pagerank ![](https://img.kancloud.cn/f3/01/f3015bb9227545c1c6673d0d2a0e4949_171x34.png) | 公式 5 | | GraRep [21] | ![](https://img.kancloud.cn/1a/87/1a872b3c90ebbe2d880e257c41aa4d08_203x50.png) ,其中 ![](https://img.kancloud.cn/da/11/da115ac68caa7c2cab632cbb921da89d_79x19.png) , ![](https://img.kancloud.cn/ea/fc/eafc1274840fb7ba8d61cd3019120914_171x63.png) | 公式 5 | | CMF [43] | PPMI | 公式 5 | | TADW [56] | PMI | 公式 5 和文本特征矩陣 | | [24] | `A` | ![](https://img.kancloud.cn/5b/da/5bda863d40941f555a2bb1471aa515fb_371x40.png) | | MMDW [48] | PMI | 公式 5 + `O(SVM分類器)` | | HSCA [57] | PMI | `O(MMDW)`+( 一階鄰近度約束) | | MVE [107] | KNN, ![](https://img.kancloud.cn/d5/fe/d5fe50d90147a516e787d1be2110ea67_342x40.png) | 公式 5 | | M-NMF [1] | ![](https://img.kancloud.cn/33/bd/33bd701743635e8620e80c4691bece64_119x36.png) | 公式 5 + `O(社區檢測)` | | ULGE [2] | ![](https://img.kancloud.cn/a0/43/a0437d0054eecc51d2b64b30a49b2338_107x17.png) ,其中 ![](https://img.kancloud.cn/65/17/6517ba43103c3842f6f9d5525505c157_345x48.png) | ![](https://img.kancloud.cn/e7/a7/e7a7062b3bd1a7b1c948b1f9d2c51f36_256x35.png) | | LLE [102] | KNN, ![](https://img.kancloud.cn/19/c9/19c9e27711ba6db336df1f92dd33241a_261x34.png) | ![](https://img.kancloud.cn/76/f9/76f9dd0a79773e027b78a36b37e8f56f_241x34.png) | | RESCAL [108] | ![](https://img.kancloud.cn/94/7c/947ca21da06ecde2c9a57aacf226cd5a_214x63.png) | ![](https://img.kancloud.cn/66/59/6659953197c891b476ece82a3ae114c7_341x39.png) | | FONPE [109] | KNN, ![](https://img.kancloud.cn/19/c9/19c9e27711ba6db336df1f92dd33241a_261x34.png) | ![](https://img.kancloud.cn/a7/88/a788d944d538fe026b5160cfa3baa37a_256x35.png) ,約束為 ![](https://img.kancloud.cn/86/bf/86bf69394cfc3ebd287d8d2a685a87a8_67x16.png) | ### 節點鄰近矩陣分解 除了解決上述廣義特征值問題外,另一系列研究試圖直接分解節點鄰近矩陣。 見解: 使用矩陣分解可以在低維空間中近似節點鄰近度。 保持節點鄰近度的目標是最小化近似的損失。 給定節點鄰近矩陣 ![](https://img.kancloud.cn/56/57/56571fc001c18aa9a087836fe41bcb8f_22x15.png) ,目標是: ![](https://img.kancloud.cn/3c/67/3c676d13cfff210904bb1ebf03f3370f_133x37.png) (5) 其中 ![](https://img.kancloud.cn/11/12/111213b4801b626726c839ffb7e17914_83x36.png) 是節點嵌入,和 ![](https://img.kancloud.cn/00/ec/00ec71b1e40af9050c2f71788cf3b281_89x36.png) 是上下文節點的嵌入[21]。 公式 5 旨在找到一個最優的秩為`d`的鄰近度矩陣`W`的近似( ![](https://img.kancloud.cn/a9/5a/a95a6b70fecd0e89d85d2fb1e3942ce7_13x15.png) 是嵌入的維度)。 一種流行的解決方案是對 ![](https://img.kancloud.cn/56/57/56571fc001c18aa9a087836fe41bcb8f_22x15.png) 應用 SVD(奇異值分解)[110]。從形式上看, ![](https://img.kancloud.cn/65/e9/65e9b930152b0a746cd64d92077f6381_257x41.png) (6) 其中 ![](https://img.kancloud.cn/d1/ed/d1edf80c0b2f11a5a2c8cae62100d49a_125x32.png) 是按降序排序的奇異值, ![](https://img.kancloud.cn/ad/f0/adf0c044315fc674f35c112608334c79_19x31.png) 和 ![](https://img.kancloud.cn/2c/42/2c42cc62df2c1920015991cf8626f591_20x31.png) 是 ![](https://img.kancloud.cn/02/0a/020a2f0bb718bb7d1574543f8622d391_19x31.png) 的奇異向量 。 最佳嵌入使用最大的`d`個奇異值獲得 ![](https://img.kancloud.cn/a9/5a/a95a6b70fecd0e89d85d2fb1e3942ce7_13x15.png),相應的奇異向量如下: ![](https://img.kancloud.cn/07/4a/074a28593f6fa781863635b29253278a_183x57.png) (7) 根據是否保留非對稱屬性,節點 ![](https://img.kancloud.cn/4e/a2/4ea21ae287e2c9238a3fde1912e6e391_10x17.png) 的嵌入是 ![](https://img.kancloud.cn/4d/f9/4df92aa29caf245757a1bb39b8294f72_53x30.png) [21,50],或 ![](https://img.kancloud.cn/d9/34/d934506a2471d3532ed500847c1f5808_19x30.png) 和 ![](https://img.kancloud.cn/84/6c/846cd083f9e414cd984ab8b0caae1bc1_24x30.png) 連接,即 ![](https://img.kancloud.cn/94/92/949202a94864b7029def8e5faeaf73c7_88x32.png) [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]旨在最大化窗口內出現的單詞之間的共現概率 ![](https://img.kancloud.cn/29/ec/29ece1a506bc7ad1c8cd4c0af2432db4_16x17.png) 。 DeepWalk首先使用截斷的隨機游走,從輸入圖中采樣一組路徑(即,均勻地采樣最后訪問節點的鄰居,直到達到最大長度)。 從圖中采樣的每個路徑相當于來自語料庫的句子,其中節點相當于單詞。 然后將SkipGram應用于路徑,最大化節點鄰域的觀測概率,以自身嵌入為條件。 以這種方式,鄰域相似(二階鄰近度較大)的節點的嵌入相似。DeepWalk的目標函數如下: ![](https://img.kancloud.cn/07/a8/07a8f407048c124e971f4786c847b847_348x32.png) (8) 其中 ![](https://img.kancloud.cn/29/ec/29ece1a506bc7ad1c8cd4c0af2432db4_16x17.png) 是窗口大小,它限制隨機游走上下文的大小。 SkipGram刪除了排序約束,并且 公式 8轉換為: ![](https://img.kancloud.cn/4a/3b/4a3b71fea21a4f65e363867769fe571d_229x32.png) (9) 其中 ![](https://img.kancloud.cn/32/0f/320f603fedb68f0df9e0b655d174b2f6_75x32.png) 使用softmax函數定義: ![](https://img.kancloud.cn/2c/2a/2c2aaf3cfa1e3af263316b529d11efd2_197x49.png) (10) 請注意,計算公式 10 是昂貴的,因為標準化因子(即,圖中每個節點的所有內積的總和),所以圖 10 的方法是不可行的。 通常有兩種解近似完全softmax的解決方案:分層softmax [112]和負采樣[112]。 分層softmax :有為了效地解決中公式 10,構造二叉樹,其中節點被分配給葉子。 不像公式 10 那樣枚舉所有節點,僅需要求解從根到相應葉子的路徑。 優化問題變得最大化樹中特定路徑的概率。 假設到葉子 ![](https://img.kancloud.cn/07/40/0740edb420c2cc4fd3da7398d2deb689_17x31.png) 的路徑是一系列節點 ![](https://img.kancloud.cn/7d/e4/7de42c96c4459faf7a615d320f21f2e6_142x32.png) ,其中`b0`為根, ![](https://img.kancloud.cn/f2/99/f29989716114cd90507d2d97746b888c_91x30.png) 。 公式 10 然后變成: ![](https://img.kancloud.cn/2d/04/2d04cf14f5166bf04ec73240b9733bba_218x41.png) (11) 其中 ![](https://img.kancloud.cn/ba/5e/ba5ec16ecde41773d1b6b70d2d23e43e_42x32.png) 是二分類器:![](https://img.kancloud.cn/ba/d6/bad6018d7954be6edd8b9b918c7dbee8_135x35.png)。![](https://img.kancloud.cn/62/82/6282c0fde70c6bd51ffcfbdfadc7e209_31x32.png) 表示 S 形函數。 ![](https://img.kancloud.cn/a5/5e/a55ea1d5e341cd427b2c70a34c9db9e7_24x31.png) 是樹節點 ![](https://img.kancloud.cn/9d/2a/9d2a5e070753fd2ce46466ae26790aab_17x30.png) 的父節點的嵌入 。 分層softmax減少了SkipGram的時間復雜度,從 ![](https://img.kancloud.cn/38/fe/38feb9f0630a52d4f1b8c4f5db4c49dc_59x34.png) 至 ![](https://img.kancloud.cn/c1/68/c168051a795c12104d1f34ebbab09943_106x32.png)。 負采樣 : 負采樣的關鍵思想是,使用邏輯回歸將目標節點與噪聲區分開來。 即,對于一個節點 ![](https://img.kancloud.cn/07/40/0740edb420c2cc4fd3da7398d2deb689_17x31.png) ,我們想區分它的鄰居 ![](https://img.kancloud.cn/17/38/173804ef8a7d49f7fd36c9220d24c58c_33x31.png) 來自其他節點。 噪音分布 ![](https://img.kancloud.cn/0e/55/0e5569b471cbd1bc27a5e822421ff063_49x32.png) 用于繪制節點的負樣本 ![](https://img.kancloud.cn/07/40/0740edb420c2cc4fd3da7398d2deb689_17x31.png) 。公式 9 中的每個 ![](https://img.kancloud.cn/65/48/65481fb323e4acf2e69e05f6297271f6_99x32.png) 然后計算為: ![](https://img.kancloud.cn/14/e7/14e73238e095c7a98f71845ff5704b53_306x40.png) (12) 其中 ![](https://img.kancloud.cn/4a/7a/4a7a44ac24686130f1d84b7a322b8a63_19x14.png) 是采樣的負節點數。 ![](https://img.kancloud.cn/0e/55/0e5569b471cbd1bc27a5e822421ff063_49x32.png) 是一種噪聲分布,例如均勻分布(![](https://img.kancloud.cn/62/37/6237027ddadc0ae5a4fe686f94fc17bd_153x35.png))。 具有負采樣的SkipGram的時間復雜度是 ![](https://img.kancloud.cn/02/ad/02ad58457c2f50da45aff5347b53e04d_66x32.png)。 **表6:**帶有隨機游走路徑的基于深度學習的圖嵌入。 | GE算法 | 隨機游走方法 | 保留的鄰近度 | DL模型 | | --- | --- | --- | --- | | DeepWalk [17] | 截斷隨機游走 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) | SkipGram 和 分層 softmax(公式 11) | | [34] | 截斷隨機游走 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) (詞語-圖像) | 同上 | | GenVector [66] | 截斷隨機游走 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) (用戶 - 用戶和概念 - 概念) | 同上 | | 受限制的DeepWalk [25] | 邊權重采樣 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) | 同上 | | DDRW [47] | 截斷隨機游走 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) +分類一致性 | 同上 | | TriDNR [73] | 截斷隨機游走 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) (節點,單詞和標簽之間) | 同上 | | node2vec [28] | BFS + DFS | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) | SkipGram 和負采樣(公式 12) | | UPP-SNE [113] | 截斷隨機游走 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) (用戶 - 用戶和個人資料 - 個人資料) | 同上 | | Planetoid [62] | 按標簽和結構對節點對進行采樣 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) +標簽標識 | 同上 | | NBNE [19] | 對節點的直接鄰居進行采樣 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) | 同上 | | DGK [93] | graphlet 核:隨機采樣[114] | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) (通過graphlet) | SkipGram(公式11 - 12 ) | | metapath2vec [46] | 基于元路徑的隨機游走 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) | 異構 SkipGram | | ProxEmbed [44] | 截斷隨機游走 | 節點排名元組 | LSTM | | HSNL [29] | 截斷隨機游走 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) + QA排名元組 | LSTM | | RMNL [30] | 截斷隨機游走 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) +用戶問題質量排名 | LSTM | | DeepCas [63] | 基于馬爾可夫鏈的隨機游走 | 信息級聯序列 | GRU | | MRW-MN [36] | 截斷隨機游走 | ![](https://img.kancloud.cn/7f/87/7f8715b55c689f1e12288845a5742881_28x20.png) +跨模態特征差異 | 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] | 自編碼器 | ![](https://img.kancloud.cn/3b/94/3b94b10cba58d2b1112c3aade1f84643_16x14.png) | | DNGR [23] | 堆疊去噪自編碼器 | PPMI | | SAE [22] | 稀疏自編碼器 | ![](https://img.kancloud.cn/df/a5/dfa5504848dff9528e6cd1ad9a9efe8a_47x16.png) | | [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 節))和所有四種類型的嵌入輸出。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看