應(yīng)用

圖嵌入有益于各種圖分析應(yīng)用，因?yàn)橄蛄勘硎究梢栽跁r(shí)間和空間上高效處理。 在本節(jié)中，我們將圖嵌入的應(yīng)用分類為節(jié)點(diǎn)相關(guān)，邊相關(guān)和圖相關(guān)。

節(jié)點(diǎn)相關(guān)應(yīng)用

節(jié)點(diǎn)分類

節(jié)點(diǎn)分類是基于從標(biāo)記節(jié)點(diǎn)習(xí)得的規(guī)則，為圖中的每個(gè)節(jié)點(diǎn)分配類標(biāo)簽。 直觀地說，“相似”節(jié)點(diǎn)具有相同的標(biāo)簽。 它是圖嵌入文獻(xiàn)中討論的最常見的應(yīng)用之一。 通常，每個(gè)節(jié)點(diǎn)都嵌入為低維向量。 通過在用于訓(xùn)練的標(biāo)記節(jié)點(diǎn)嵌入集上應(yīng)用分類器來進(jìn)行節(jié)點(diǎn)分類。 示例分類器包括 SVM（[1,33,56,20,73,34,45,41,42,57,75,81,87,60]），邏輯回歸（[17,27,124,1,21]，[28,20,19,45,25,59]）和 k-最近鄰分類（[58,151]）。 然后，給定未標(biāo)記節(jié)點(diǎn)的嵌入，訓(xùn)練的分類器可以預(yù)測其類標(biāo)簽。 與首先是節(jié)點(diǎn)嵌入然后是節(jié)點(diǎn)分類的上述順序處理相比，其他一些工作（[62,72,47,48,80]）設(shè)計(jì)了一個(gè)統(tǒng)一的框架來聯(lián)合優(yōu)化圖嵌入和節(jié)點(diǎn)分類，它們學(xué)習(xí)特定于分類的每個(gè)節(jié)點(diǎn)的表示。

節(jié)點(diǎn)聚類

節(jié)點(diǎn)聚類旨在將類似節(jié)點(diǎn)組合在一起，以使同一組中的節(jié)點(diǎn)彼此更相似，而不是其他組中的節(jié)點(diǎn)。 作為無監(jiān)督算法，當(dāng)節(jié)點(diǎn)標(biāo)簽不可用時(shí)，它是適用的。 在將節(jié)點(diǎn)表示為向量之后，可以將傳統(tǒng)的聚類算法應(yīng)用于節(jié)點(diǎn)嵌入。 大多數(shù)現(xiàn)有工作[1,2,21,33,23,22,81]采用 k 均值作為聚類算法。 相比之下，[4]和[77]聯(lián)合優(yōu)化了一個(gè)目標(biāo)中的聚類和圖嵌入，來學(xué)習(xí)特定于聚類的節(jié)點(diǎn)表示。

節(jié)點(diǎn)推薦/檢索/排名

節(jié)點(diǎn)推薦的任務(wù)是，基于諸如相似性的某些標(biāo)準(zhǔn)[106,3,47,16,43,45]來推薦給定節(jié)點(diǎn)感興趣的前K個(gè)節(jié)點(diǎn)。 在現(xiàn)實(shí)世界的場景中，有各種類型的節(jié)點(diǎn)推薦，例如為研究人員推薦研究興趣[66]，為客戶推薦項(xiàng)目[3,71]，為社會(huì)網(wǎng)絡(luò)用戶推薦圖像[35]，為社交網(wǎng)絡(luò)用戶推薦朋友[3]，以及為查詢推薦文件[69]。 它在社區(qū)問答中也很受歡迎。 給出一個(gè)問題，他們預(yù)測用戶的相對排名（[31,30]）或答案（[32,29]）。 在鄰近搜索[44,39]中，它們對給定查詢節(jié)點(diǎn)（例如，“Bob”）和鄰近類別（例如，“同學(xué)”）的特定類型（例如，“用戶”）的節(jié)點(diǎn)進(jìn)行排名，例如，排名是Bob的同學(xué)的用戶。 并且有一些工作側(cè)重于跨模態(tài)檢索[33,36,99,34]，例如，基于關(guān)鍵詞的圖像/視頻搜索。

在知識圖嵌入中廣泛討論的特定應(yīng)用是實(shí)體排名[53,51,59,52,61]。 回想一下，知識圖由一組三元組組成 。 實(shí)體排名旨在對正確的缺失實(shí)體進(jìn)行排名，給定三元組中其他兩個(gè)成分，它們高于虛假實(shí)體。 例如，給定r和t，在所有候選實(shí)體，它返回真的h，或者給定r和h返回真的t。

邊相關(guān)應(yīng)用

接下來，我們介紹邊相關(guān)應(yīng)用，其中涉及邊或節(jié)點(diǎn)對。

鏈接預(yù)測

圖嵌入旨在表示具有低維向量的圖，但有趣的是它的輸出向量也可以幫助推斷圖結(jié)構(gòu)。 在實(shí)踐中，圖通常是不完整的; 例如，在社交網(wǎng)絡(luò)中，實(shí)際上彼此了解的兩個(gè)用戶之間可能缺少好友鏈接。 在圖嵌入中，期望低維向量保持不同的網(wǎng)絡(luò)鄰近度（例如，DeepWalk [17]，LINE [27]），以及不同的結(jié)構(gòu)相似度（例如，GCN [72]，struc2vec [145]）。 因此，這些向量編碼網(wǎng)絡(luò)結(jié)構(gòu)的豐富信息，并且它們可用于預(yù)測不完整圖中的缺失鏈接。 大多數(shù)圖嵌入驅(qū)動(dòng)的鏈接預(yù)測，都在同構(gòu)圖上[3,16,28,19]嘗試。 例如，[28]預(yù)測兩個(gè)用戶之間的好友關(guān)系。 處理異構(gòu)圖鏈接預(yù)測的圖嵌入工作相對較少。 例如，在異構(gòu)社交圖上，ProxEmbed [44]試圖根據(jù)其在圖上的連接路徑的嵌入，來預(yù)測兩個(gè)用戶之間某些語義類型（例如，同學(xué)）的缺失鏈接。 D2AGE [152]通過嵌入兩個(gè)用戶的連通有向無環(huán)圖結(jié)構(gòu)，解決了同樣的問題。

三元組分類

三元組分類[142,53,15,51,52,14,38,61]是知識圖的特定應(yīng)用。 它的目的是分類，沒見過的三元組 是否正確，即 和 的關(guān)系是否是 。

圖相關(guān)應(yīng)用

圖分類

圖分類將類標(biāo)簽分配給整圖。 當(dāng)圖是數(shù)據(jù)單位時(shí)，這很重要。 例如，在[50]中，每個(gè)圖是化學(xué)化合物，有機(jī)分子或蛋白質(zhì)結(jié)構(gòu)。 在大多數(shù)情況下，應(yīng)用整圖嵌入來計(jì)算圖層級相似度[93,55,54,49,95]。 最近，一些工作開始匹配節(jié)點(diǎn)嵌入和圖相似性[153,50]。 每個(gè)圖表示為一組節(jié)點(diǎn)嵌入向量。 基于兩組節(jié)點(diǎn)嵌入來比較圖。 [93]將圖分解為一組子結(jié)構(gòu)，然后將每個(gè)子結(jié)構(gòu)嵌入為向量，并通過子結(jié)構(gòu)相似性比較圖。

可視化

圖可視化在低維空間上生成圖的可視化[20,23,55,48,73,58]。 通常，出于可視化目的，所有節(jié)點(diǎn)都嵌入為2D向量，然后繪制在2D空間中，不同的顏色表示節(jié)點(diǎn)的類別。 它提供了生動(dòng)的演示，表明屬于同一類別的節(jié)點(diǎn)的嵌入是否彼此更緊密。

其它應(yīng)用

以上是一些在現(xiàn)有工作中經(jīng)常討論的一般應(yīng)用。 根據(jù)輸入圖中攜帶的信息，可能存在更具體的應(yīng)用。 以下是一些示例場景。

知識圖相關(guān)：[15]和[14]從大規(guī)模純文本中提取關(guān)系事實(shí)。 [62]從文本中提取醫(yī)學(xué)實(shí)體。 [69]將自然語言文本與知識圖中的實(shí)體聯(lián)系起來。 [92]側(cè)重于刪除知識圖中重復(fù)的等效實(shí)體。 [84]聯(lián)合嵌入實(shí)體提及，文本和實(shí)體類型，從其嘈雜的候選類型集中估計(jì)每個(gè)提及的真實(shí)類型路徑。 例如，“特朗普”的候選類型是“人，政治家，商人，藝術(shù)家，演員”。 對于提及“特朗普”的句子“共和黨總統(tǒng)候選人唐納德特朗普在洛克希爾的競選活動(dòng)中發(fā)言?！?#xff0c;只有“人，政治家”是正確的類型。

多媒體網(wǎng)絡(luò)相關(guān) ：[83]嵌入地理標(biāo)記社交媒體（GTSM）記錄“時(shí)間，地點(diǎn)，消息 ”，這使得他們能夠在給定其他兩個(gè)成分的情況下，從GTSM三元組中恢復(fù)丟失的成分。 它還可以對GTSM記錄進(jìn)行分類，例如，登記記錄是否與“食物”或“商店”相關(guān)。 [85]使用圖嵌入來減少人臉識別的數(shù)據(jù)維度。 [88]將圖像映射到一個(gè)語義流形，忠實(shí)地掌握用戶的偏好，來促進(jìn)基于內(nèi)容的圖像檢索。

信息傳播相關(guān)：[63]預(yù)測給定時(shí)間間隔后級聯(lián)大小的增量。 [64]預(yù)測傳播用戶，并通過嵌入社交互動(dòng)圖來識別領(lǐng)域?qū)＜摇?/p>

社交網(wǎng)絡(luò)對齊： [26]和[18]都學(xué)習(xí)節(jié)點(diǎn)嵌入，來對齊跨越不同的社交網(wǎng)絡(luò)的用戶，即，預(yù)測兩個(gè)不同社交網(wǎng)絡(luò)中的兩個(gè)用戶帳戶是否由同一用戶擁有。

圖像相關(guān)：一些工作嵌入由圖像構(gòu)建的圖，然后使用嵌入進(jìn)行圖像分類（[81,82]），圖像聚類[101]，圖像分割[154]，模式識別[80]等。

未來發(fā)展方向

在本節(jié)中，我們總結(jié)了圖嵌入領(lǐng)域的四個(gè)未來方向，包括計(jì)算效率，問題設(shè)定，技術(shù)和應(yīng)用場景。

計(jì)算。 采用幾何輸入（例如，圖）的深層架構(gòu)遭受低效率問題。 傳統(tǒng)的深度學(xué)習(xí)模型（為歐幾里得域設(shè)計(jì)）通過假設(shè)輸入數(shù)據(jù)在1D或2D網(wǎng)格上，利用現(xiàn)代GPU來優(yōu)化其效率。 但是，圖沒有這種網(wǎng)格結(jié)構(gòu)，因此為圖嵌入設(shè)計(jì)的深層架構(gòu)需要尋求替代解決方案來提高模型效率。 [117]建議可以采用為大規(guī)模圖處理開發(fā)的計(jì)算范式，來提高圖嵌入的深度學(xué)習(xí)模型的效率。

問題設(shè)定。 動(dòng)態(tài)圖是圖嵌入的一個(gè)有前途的設(shè)定。 圖并不總是靜態(tài)的，尤其是在現(xiàn)實(shí)生活場景中，例如Twitter中的社交圖，DBLP中的引文圖。 在圖結(jié)構(gòu)或節(jié)點(diǎn)/邊信息方面，圖可以是動(dòng)態(tài)的。 一方面，圖結(jié)構(gòu)可以隨時(shí)間演變，即，一些舊節(jié)點(diǎn)/邊消失時(shí)出現(xiàn)新節(jié)點(diǎn)/邊。 另一方面，節(jié)點(diǎn)/邊可以通過一些時(shí)變信息來描述。 現(xiàn)有圖嵌入主要側(cè)重于嵌入靜態(tài)圖，忽略了動(dòng)態(tài)圖嵌入的設(shè)定。 與靜態(tài)圖嵌入不同，動(dòng)態(tài)圖的技術(shù)需要是可擴(kuò)展的，并且最好是遞增的，以便有效地處理動(dòng)態(tài)變化。 這使得大多數(shù)現(xiàn)有的圖嵌入方法受到低效率問題的影響，不再適用。 如何在動(dòng)態(tài)域中設(shè)計(jì)有效的圖嵌入方法仍然是一個(gè)懸而未決的問題。

技術(shù)。 結(jié)構(gòu)感知對于基于邊重建的圖嵌入很重要。 當(dāng)前基于邊重建的圖嵌入方法主要僅基于邊，例如，一般圖中的一跳的鄰居，知識圖中的排名三元組<h, r, t>，和 cQA 圖中的 。 單個(gè)邊僅提供局部鄰域信息來計(jì)算一階和二階接近度。 省略了圖的全局結(jié)構(gòu)（例如，路徑，樹，子圖模式）。 直觀地說，子結(jié)構(gòu)包含比單個(gè)邊更豐富的信息。 一些工作嘗試探索知識圖嵌入中的路徑信息（[142,40,38,39]）。 然而，他們中的大多數(shù)使用深度學(xué)習(xí)模型（[142,38,40]），這些模型遭受前面討論的低效率問題。 如何設(shè)計(jì)可以利用圖結(jié)構(gòu)的表現(xiàn)力的非深度學(xué)習(xí)方法是一個(gè)問題。 [39]提供了一個(gè)示例解決方案。 它最小化成對和長程損失，來捕獲成對關(guān)系和實(shí)體之間的遠(yuǎn)程交互。 注意，除了列表/路徑結(jié)構(gòu)之外，還存在各種具有不同結(jié)構(gòu)信息的子結(jié)構(gòu)。 例如，SPE [155]試圖引入一個(gè)子圖增強(qiáng)路徑結(jié)構(gòu)，用于在異構(gòu)圖中嵌入兩個(gè)節(jié)點(diǎn)之間的接近度，并且它比語義搜索任務(wù)的簡單路徑嵌入表現(xiàn)出更好的性能。 通常，需要一種有效的結(jié)構(gòu)感知圖嵌入優(yōu)化解決方案以及子結(jié)構(gòu)采樣策略。

應(yīng)用。 圖嵌入已應(yīng)用于許多不同的應(yīng)用中。 考慮到它們之間的關(guān)系，這是學(xué)習(xí)數(shù)據(jù)表示的有效方法。 此外，它可以將來自不同源/平臺/視圖的數(shù)據(jù)實(shí)例轉(zhuǎn)換到一個(gè)公共空間，以便它們可以直接比較。 例如，[36,16,34]使用圖嵌入進(jìn)行跨模態(tài)檢索，例如基于內(nèi)容的圖像檢索，基于關(guān)鍵詞的圖像/視頻搜索。 使用圖嵌入進(jìn)行表示學(xué)習(xí)的優(yōu)點(diǎn)在于，訓(xùn)練數(shù)據(jù)實(shí)例的圖流形被保留在表示中，并且可以進(jìn)一步有益于后續(xù)應(yīng)用。 因此，圖嵌入可以使假設(shè)輸入數(shù)據(jù)實(shí)例與某些關(guān)系相關(guān)（即，通過某些鏈接連接）的任務(wù)受益。 探索受益于圖嵌入的應(yīng)用場景非常重要，因?yàn)樗鼜牟煌慕嵌葹閭鹘y(tǒng)問題提供了有效的解決方案。

結(jié)論

在本綜述中，我們對圖嵌入中的文獻(xiàn)進(jìn)行了全面的回顧。 我們?yōu)閳D嵌入問題提供了一個(gè)正式的定義，并介紹了一些基本概念。 更重要的是，我們提出了兩種圖嵌入分類法，分別基于問題設(shè)定和嵌入技術(shù)對現(xiàn)有工作進(jìn)行分類。 在問題設(shè)定分類中，我們介紹了四種嵌入輸入和四種嵌入輸出，并總結(jié)了每種設(shè)定所面臨的挑戰(zhàn)。 對于嵌入技術(shù)分類法，我們介紹了每個(gè)類別的工作，并根據(jù)它們的優(yōu)缺點(diǎn)進(jìn)行比較。 之后，我們總結(jié)了圖嵌入的應(yīng)用。 最后，在計(jì)算效率，問題設(shè)定，技術(shù)和應(yīng)用場景方面，我們建議了圖嵌入領(lǐng)域的四個(gè)有希望的未來研究方向。

總結(jié)

以上是生活随笔為你收集整理的图嵌入综述 (arxiv 1709.07604) 译文五、六、七的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。