https://www.zhuanzhi.ai/paper/a904f0aa0762e65e1dd0b8b464df7168

圖是描述對(duì)象及其關(guān)系的重要數(shù)據(jù)表示形式，它們出現(xiàn)在各種各樣的現(xiàn)實(shí)場(chǎng)景中。圖生成是該領(lǐng)域的關(guān)鍵問題之一，它考慮的是學(xué)習(xí)給定圖的分布，生成更多新的圖。然而，由于其廣泛的應(yīng)用，具有豐富歷史的圖的生成模型傳統(tǒng)上是手工制作的，并且只能對(duì)圖的一些統(tǒng)計(jì)屬性建模。

最近在用于圖生成的深度生成模型方面的進(jìn)展是提高生成圖的保真度的重要一步，并為新類型的應(yīng)用鋪平了道路。本文對(duì)用于圖生成的深度生成模型領(lǐng)域的文獻(xiàn)進(jìn)行了廣泛的概述。首先，給出了面向圖生成的深度生成模型的形式化定義和初步知識(shí);其次，分別提出了用于無條件和條件圖生成的深度生成模型的分類;對(duì)各自已有的工作進(jìn)行了比較分析。在此之后，將概述此特定領(lǐng)域中的評(píng)估指標(biāo)。最后，總結(jié)了深度圖生成的應(yīng)用，并指出了五個(gè)有發(fā)展前景的研究方向。 

引言

圖在現(xiàn)實(shí)世界中無處不在，表示對(duì)象及其關(guān)系，如社會(huì)網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等。眾所周知，圖還具有復(fù)雜的結(jié)構(gòu)，其中包含豐富的底層值[1]。人們?cè)谶@方面做出了巨大的努力，產(chǎn)生了豐富的相關(guān)文獻(xiàn)和處理各種圖問題的方法。

這些工作可分為兩類:1)預(yù)測(cè)和分析給定圖的模式。2)學(xué)習(xí)給定圖的分布，生成更多新穎的圖。第一種類型涵蓋了許多研究領(lǐng)域，包括節(jié)點(diǎn)分類、圖分類和鏈接預(yù)測(cè)。在過去的幾十年里，在這個(gè)領(lǐng)域已經(jīng)做了大量的工作。與第一類問題相比，第二類問題與圖生成問題有關(guān)，這也是本文的重點(diǎn)。

圖生成包括建模和生成真實(shí)世界的圖的過程，它在幾個(gè)領(lǐng)域都有應(yīng)用，例如理解社交網(wǎng)絡(luò)[2]，[3]，[4]中的交互動(dòng)態(tài)，異常檢測(cè)[5]，蛋白質(zhì)結(jié)構(gòu)建模[6]，[7]，源代碼生成和翻譯[8]，[9]，語(yǔ)義解析[10]。由于其廣泛的應(yīng)用，圖的生成模型的發(fā)展有著豐富的歷史，產(chǎn)生了著名的模型，如隨機(jī)圖、小世界模型、隨機(jī)塊模型和貝葉斯網(wǎng)絡(luò)模型，這些模型基于先驗(yàn)結(jié)構(gòu)假設(shè)[11]生成圖。這些圖生成模型[12]、[13]、[14]旨在建模預(yù)先選擇的圖族，如隨機(jī)圖[15]、小世界網(wǎng)絡(luò)[16]和無標(biāo)度圖[12]。然而，由于其簡(jiǎn)單性和手工制作的性質(zhì)，這些隨機(jī)圖模型通常對(duì)復(fù)雜依賴的建模能力有限，只能對(duì)圖的一些統(tǒng)計(jì)屬性建模。

這些方法通常很適合預(yù)定義原則為之量身定制的屬性，但通常不能很好地適用于其他屬性。例如，接觸網(wǎng)絡(luò)模型可以擬合流感流行，但不能擬合動(dòng)態(tài)功能連接。然而，在許多領(lǐng)域，網(wǎng)絡(luò)的性質(zhì)和生成原理在很大程度上是未知的，如那些解釋大腦網(wǎng)絡(luò)中的精神疾病的機(jī)制，網(wǎng)絡(luò)攻擊和惡意軟件的傳播。對(duì)于另一個(gè)例子，Erdos-Renyi的圖沒有許多現(xiàn)實(shí)世界網(wǎng)絡(luò)中典型的重尾度分布。此外，先驗(yàn)假設(shè)的使用限制了這些傳統(tǒng)技術(shù)在更大規(guī)模的領(lǐng)域中探索更多的應(yīng)用，在這些領(lǐng)域中，圖的先驗(yàn)知識(shí)總是不可用。

考慮到傳統(tǒng)圖生成技術(shù)的局限性，一個(gè)關(guān)鍵的開放挑戰(zhàn)是開發(fā)可以從觀察到的圖集合中直接學(xué)習(xí)生成模型的方法，這是提高生成圖的保真度的重要一步。它為新類型的應(yīng)用鋪平了道路，如發(fā)現(xiàn)新的藥物[17]，[18]，和蛋白質(zhì)結(jié)構(gòu)建模[19]，[20]，[21]。深度生成模型的最新進(jìn)展，如變分自編碼器(VAE)[22]和生成對(duì)抗網(wǎng)絡(luò)(GAN)[23]，已被提出用于生成圖的許多深度學(xué)習(xí)模型，這些模型形式化了用于生成圖的深度生成模型的有前途的領(lǐng)域，這是本綜述的重點(diǎn)。

在深度圖生成方面已經(jīng)開展了各種先進(jìn)的工作，從一次性圖生成到順序圖生成過程，適應(yīng)了各種深度生成學(xué)習(xí)策略。這些方法旨在通過不同領(lǐng)域的工作解決上述挑戰(zhàn)中的一個(gè)或幾個(gè)，包括機(jī)器學(xué)習(xí)、生物信息學(xué)、人工智能、人類健康和社交網(wǎng)絡(luò)挖掘。但是，不同的研究領(lǐng)域開發(fā)的方法往往使用不同的詞匯，從不同的角度解決問題。

此外，缺乏標(biāo)準(zhǔn)和全面的評(píng)估程序來驗(yàn)證所開發(fā)的圖的深度生成模型。為此，本文對(duì)用于圖生成的深度生成模型進(jìn)行了系統(tǒng)的綜述。目的是幫助跨學(xué)科研究者選擇合適的技術(shù)來解決其應(yīng)用領(lǐng)域的問題，更重要的是幫助圖生成研究者理解圖生成的基本原理，并識(shí)別深度圖生成領(lǐng)域的開放研究機(jī)會(huì)。據(jù)我們所知，這是第一次對(duì)用于圖生成的深度生成模型的全面綜述。下面，我們總結(jié)了這次綜述的主要貢獻(xiàn):

本文提出一種用于圖生成的深度生成模型分類法，按問題設(shè)置和方法進(jìn)行分類。介紹了不同子類別之間的優(yōu)缺點(diǎn)和關(guān)系。對(duì)用于圖生成的深度生成模型以及基礎(chǔ)的深度生成模型進(jìn)行了詳細(xì)的描述、分析和比較。

• 我們總結(jié)和分類現(xiàn)有的評(píng)估程序和指標(biāo)，基準(zhǔn)數(shù)據(jù)集和對(duì)應(yīng)的圖生成任務(wù)的深度生成模型的結(jié)果。
• 我們介紹了圖深度生成模型的現(xiàn)有應(yīng)用領(lǐng)域，以及它們給這些應(yīng)用帶來的潛在好處和機(jī)會(huì)。
• 我們提出了用于圖生成的深度生成模型領(lǐng)域的幾個(gè)開放問題和有前途的未來研究方向。

用于圖生成的無條件深度生成模型

無條件深度圖生成的目的是通過深度生成模型從真實(shí)分布p(G)中抽樣的一組觀察到的真實(shí)圖來學(xué)習(xí)分布pmodel(G)。根據(jù)生成過程的風(fēng)格，我們可以將這些方法分為兩個(gè)主要分支:(1)順序生成:按順序依次生成節(jié)點(diǎn)和邊;(2)一次生成:根據(jù)矩陣表示建立一個(gè)概率圖模型，一次生成所有節(jié)點(diǎn)和邊。這兩種生成圖的方法各有優(yōu)缺點(diǎn)。順序生成雖然高效地執(zhí)行了前一種生成的局部決策，但在保持長(zhǎng)期依賴性方面存在困難。因此，圖的一些全局屬性(如無標(biāo)度屬性)很難包含進(jìn)去。此外，現(xiàn)有的關(guān)于序列生成的工作僅限于預(yù)先定義的序列的順序，從而留下了排列的作用。一次性生成方法可以通過多次迭代同步生成和細(xì)化整個(gè)圖(即節(jié)點(diǎn)和邊)，從而對(duì)圖的全局屬性進(jìn)行建模，但由于需要對(duì)節(jié)點(diǎn)之間的全局關(guān)系進(jìn)行集體建模，其時(shí)間復(fù)雜度通常超過O(N2)，因此大多數(shù)方法難以擴(kuò)展到大型圖。

用于圖生成的條件深度生成模型

條件深度圖生成的目標(biāo)是根據(jù)觀察到的一組現(xiàn)實(shí)圖G及其對(duì)應(yīng)的輔助信息(即條件y)學(xué)習(xí)條件分布pmodel(G|y)。輔助信息可以是類別標(biāo)簽、語(yǔ)義上下文、來自其他分布空間的圖等。與無條件深度圖生成相比，條件生成除了在生成圖方面的挑戰(zhàn)外，還需要考慮如何從給定條件中提取特征并將其整合到圖的生成中。

因此，為了系統(tǒng)地介紹現(xiàn)有的條件深度圖生成模型，我們主要描述這些方法如何處理?xiàng)l件。由于條件可以是任何形式的輔助信息，因此它們被分為三種類型，包括圖、序列和語(yǔ)義上下文，如圖1中分類法樹的黃色部分所示