點(diǎn)擊上方 關(guān)注我們

聲明：本文轉(zhuǎn)自專知微信公眾號(hào)

圖是連接數(shù)據(jù)網(wǎng)絡(luò)結(jié)構(gòu)的一種常用表示形式。圖數(shù)據(jù)可以在廣泛的應(yīng)用領(lǐng)域中找到，如社會(huì)系統(tǒng)、生態(tài)系統(tǒng)、生物網(wǎng)絡(luò)、知識(shí)圖譜和信息系統(tǒng)。隨著人工智能技術(shù)的不斷滲透發(fā)展，圖學(xué)習(xí)(即對(duì)圖進(jìn)行機(jī)器學(xué)習(xí))越來(lái)越受到研究者和實(shí)踐者的關(guān)注。圖學(xué)習(xí)對(duì)許多任務(wù)都非常有效，如分類(lèi)，鏈接預(yù)測(cè)和匹配。圖學(xué)習(xí)方法通常是利用機(jī)器學(xué)習(xí)算法提取圖的相關(guān)特征。在這個(gè)綜述中，我們提出了一個(gè)關(guān)于圖學(xué)習(xí)最全面的概述。特別關(guān)注四類(lèi)現(xiàn)有的圖學(xué)習(xí)方法，包括圖信號(hào)處理、矩陣分解、隨機(jī)游走和深度學(xué)習(xí)。分別回顧了這些類(lèi)別下的主要模型和算法。我們研究了諸如文本、圖像、科學(xué)、知識(shí)圖譜和組合優(yōu)化等領(lǐng)域的圖學(xué)習(xí)應(yīng)用。此外，我們還討論了該領(lǐng)域幾個(gè)有前景的研究方向。

https:///pdf/2105.00696.pdf

（掃描二維碼，跳轉(zhuǎn)到論文地址）

真實(shí)的智能系統(tǒng)通常依賴于機(jī)器學(xué)習(xí)算法處理各種類(lèi)型的數(shù)據(jù)。盡管圖數(shù)據(jù)無(wú)處不在，但由于其固有的復(fù)雜性，給機(jī)器學(xué)習(xí)帶來(lái)了前所未有的挑戰(zhàn)。與文本、音頻和圖像不同，圖數(shù)據(jù)嵌入在一個(gè)不規(guī)則的領(lǐng)域，使得現(xiàn)有機(jī)器學(xué)習(xí)算法的一些基本操作不適用。許多圖學(xué)習(xí)模型和算法已經(jīng)被開(kāi)發(fā)出來(lái)解決這些挑戰(zhàn)。本文系統(tǒng)地綜述了目前最先進(jìn)的圖學(xué)習(xí)方法及其潛在的應(yīng)用。這篇論文有多種用途。首先，它作為不同領(lǐng)域(如社會(huì)計(jì)算、信息檢索、計(jì)算機(jī)視覺(jué)、生物信息學(xué)、經(jīng)濟(jì)學(xué)和電子商務(wù))的研究人員和從業(yè)者提供圖學(xué)習(xí)的快速參考。其次，它提供了對(duì)該領(lǐng)域的開(kāi)放研究領(lǐng)域的見(jiàn)解。第三，它的目的是激發(fā)新的研究思路和更多的興趣在圖學(xué)習(xí)。

圖，又稱網(wǎng)絡(luò)，可以從現(xiàn)實(shí)世界中豐富的實(shí)體之間的各種關(guān)系中提取。一些常見(jiàn)的圖表已經(jīng)被廣泛用于表達(dá)不同的關(guān)系，如社會(huì)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、專利網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、引文網(wǎng)絡(luò)和通信網(wǎng)絡(luò)[1]-[3]。圖通常由兩個(gè)集合定義，即頂點(diǎn)集和邊集。頂點(diǎn)表示圖形中的實(shí)體，而邊表示這些實(shí)體之間的關(guān)系。由于圖學(xué)習(xí)在數(shù)據(jù)挖掘、知識(shí)發(fā)現(xiàn)等領(lǐng)域的廣泛應(yīng)用，引起了人們的廣泛關(guān)注。由于圖利用了頂點(diǎn)[4]，[5]之間的本質(zhì)和相關(guān)關(guān)系，在捕獲復(fù)雜關(guān)系方面，圖學(xué)習(xí)方法變得越來(lái)越流行。例如，在微博網(wǎng)絡(luò)中，通過(guò)檢測(cè)信息級(jí)聯(lián)，可以跟蹤謠言的傳播軌跡。在生物網(wǎng)絡(luò)中，通過(guò)推測(cè)蛋白質(zhì)的相互作用可以發(fā)現(xiàn)治療疑難疾病的新方法。在交通網(wǎng)絡(luò)中，通過(guò)分析不同時(shí)間戳[6]的共現(xiàn)現(xiàn)象，可以預(yù)測(cè)人類(lèi)的移動(dòng)模式。對(duì)這些網(wǎng)絡(luò)的有效分析很大程度上取決于網(wǎng)絡(luò)的表示方式。

一般來(lái)說(shuō)，圖學(xué)習(xí)是指對(duì)圖進(jìn)行機(jī)器學(xué)習(xí)。圖學(xué)習(xí)方法將圖的特征映射到嵌入空間中具有相同維數(shù)的特征向量。圖學(xué)習(xí)模型或算法直接將圖數(shù)據(jù)轉(zhuǎn)換為圖學(xué)習(xí)體系結(jié)構(gòu)的輸出，而不將圖投影到低維空間。由于深度學(xué)習(xí)技術(shù)可以將圖數(shù)據(jù)編碼并表示為向量，所以大多數(shù)圖學(xué)習(xí)方法都是基于或從深度學(xué)習(xí)技術(shù)推廣而來(lái)的。圖學(xué)習(xí)的輸出向量在連續(xù)空間中。圖學(xué)習(xí)的目標(biāo)是提取圖的期望特征。因此，圖的表示可以很容易地用于下游任務(wù)，如節(jié)點(diǎn)分類(lèi)和鏈接預(yù)測(cè)，而無(wú)需顯式的嵌入過(guò)程。因此，圖學(xué)習(xí)是一種更強(qiáng)大、更有意義的圖分析技術(shù)。

在這篇綜述論文中，我們?cè)噲D以全面的方式檢驗(yàn)圖機(jī)器學(xué)習(xí)方法。如圖1所示，我們關(guān)注現(xiàn)有以下四類(lèi)方法:基于圖信號(hào)處理(GSP)的方法、基于矩陣分解的方法、基于隨機(jī)游走的方法和基于深度學(xué)習(xí)的方法。大致來(lái)說(shuō)，GSP處理圖的采樣和恢復(fù)，并從數(shù)據(jù)中學(xué)習(xí)拓?fù)浣Y(jié)構(gòu)。矩陣分解可分為圖拉普拉斯矩陣分解和頂點(diǎn)接近矩陣分解?；陔S機(jī)游動(dòng)的方法包括基于結(jié)構(gòu)的隨機(jī)游動(dòng)、基于結(jié)構(gòu)和節(jié)點(diǎn)信息的隨機(jī)游動(dòng)、異構(gòu)網(wǎng)絡(luò)中的隨機(jī)游動(dòng)和時(shí)變網(wǎng)絡(luò)中的隨機(jī)游動(dòng)?；谏疃葘W(xué)習(xí)的方法包括圖卷積網(wǎng)絡(luò)、圖注意力網(wǎng)絡(luò)、圖自編碼器、圖生成網(wǎng)絡(luò)和圖時(shí)空網(wǎng)絡(luò)?；旧?，這些方法/技術(shù)的模型架構(gòu)是不同的。本文對(duì)目前最先進(jìn)的圖學(xué)習(xí)技術(shù)進(jìn)行了廣泛的回顧。

傳統(tǒng)上，研究人員采用鄰接矩陣來(lái)表示一個(gè)圖，它只能捕捉相鄰兩個(gè)頂點(diǎn)之間的關(guān)系。然而，許多復(fù)雜和不規(guī)則的結(jié)構(gòu)不能被這種簡(jiǎn)單的表示捕獲。當(dāng)我們分析大規(guī)模網(wǎng)絡(luò)時(shí)，傳統(tǒng)的方法在計(jì)算上是昂貴的，并且很難在現(xiàn)實(shí)應(yīng)用中實(shí)現(xiàn)。因此，有效地表示這些網(wǎng)絡(luò)是解決[4]的首要問(wèn)題。近年來(lái)提出的網(wǎng)絡(luò)表示學(xué)習(xí)(NRL)可以學(xué)習(xí)低維表示[7]-[9]的網(wǎng)絡(luò)頂點(diǎn)潛在特征。當(dāng)新的表示被學(xué)習(xí)后，可以使用以前的機(jī)器學(xué)習(xí)方法來(lái)分析圖數(shù)據(jù)，并發(fā)現(xiàn)數(shù)據(jù)中隱藏的關(guān)系。

當(dāng)復(fù)雜網(wǎng)絡(luò)被嵌入到一個(gè)潛在的、低維的空間中時(shí)，結(jié)構(gòu)信息和頂點(diǎn)屬性可以被保留[4]。因此，網(wǎng)絡(luò)的頂點(diǎn)可以用低維向量表示。在以往的機(jī)器學(xué)習(xí)方法中，這些向量可以看作是輸入的特征。圖學(xué)習(xí)方法為新的表示空間中的圖分析鋪平了道路，許多圖分析任務(wù)，如鏈接預(yù)測(cè)、推薦和分類(lèi)，都可以有效地解決[10]，[11]。網(wǎng)絡(luò)的圖形化表現(xiàn)方式揭示了社會(huì)生活的各個(gè)方面，如交流模式、社區(qū)結(jié)構(gòu)和信息擴(kuò)散[12]，[13]。根據(jù)頂點(diǎn)、邊和子圖的屬性，可以將圖學(xué)習(xí)任務(wù)分為基于頂點(diǎn)、基于邊和基于子圖三類(lèi)。圖中頂點(diǎn)之間的關(guān)系可以用于分類(lèi)、風(fēng)險(xiǎn)識(shí)別、聚類(lèi)和社區(qū)檢測(cè)[14]。通過(guò)判斷圖中兩個(gè)頂點(diǎn)之間的邊的存在，我們可以進(jìn)行推薦和知識(shí)推理?；谧訄D[15]的分類(lèi)，該圖可用于聚合物分類(lèi)、三維可視化分類(lèi)等。對(duì)于GSP，設(shè)計(jì)合適的圖形采樣方法以保持原始圖形的特征，從而有效地恢復(fù)原始圖形[16]具有重要意義。在存在不完整數(shù)據(jù)[17]的情況下，可以使用圖恢復(fù)方法構(gòu)造原始圖。然后利用圖學(xué)習(xí)從圖數(shù)據(jù)中學(xué)習(xí)拓?fù)浣Y(jié)構(gòu)。綜上所述，利用圖學(xué)習(xí)可以解決傳統(tǒng)的圖分析方法[18]難以解決的以下挑戰(zhàn)。