如何在圖形生成過程中處理元素的對稱性和排序，并提供可能的解決方案

一般來說，圖形是基本的數(shù)據(jù)結(jié)構(gòu)，它在諸如知識圖、物理和社會交互、語言和化學(xué)等許多重要的實際領(lǐng)域中對關(guān)系結(jié)構(gòu)進行簡明地捕捉。在本文中，我們引入了一種強大的新方法，用于學(xué)習(xí)圖形中的生成式模型，既可以捕捉它們的結(jié)構(gòu)也可以捕捉到屬性。我們的方法使用圖形神經(jīng)網(wǎng)絡(luò)表示圖形節(jié)點和邊緣之間的概率依賴關(guān)系，并且原則上來說，可以學(xué)習(xí)任何任意圖形上的分布。經(jīng)過一系列實驗，我們的結(jié)果顯示，一旦經(jīng)過訓(xùn)練之后，我們的模型可以生成高質(zhì)量的合成圖和真實分子圖的樣本，無論是在無條件數(shù)據(jù)還是條件數(shù)據(jù)的情況下都是如此。與不使用圖形結(jié)構(gòu)表示的基線相比，我們的模型通常表現(xiàn)得更好。我們還探索了學(xué)習(xí)圖形生成式模型過程中所存在的關(guān)鍵性挑戰(zhàn)，例如，如何在圖形生成過程中處理元素的對稱性和排序，并提供可能的解決方案。可以這樣說，我們的研究是用于學(xué)習(xí)任意圖形上生成式模型的第一個方法，也是最為通用的方法，并且為從向量和序列式的知識表示，轉(zhuǎn)向更有表現(xiàn)力和更靈活的關(guān)系數(shù)據(jù)結(jié)構(gòu)，開辟了新的研究方向。

圖形是許多問題域中信息的本質(zhì)性表示。例如，知識圖表和社交網(wǎng)絡(luò)中的實體之間的關(guān)系可以很好地用圖形進行表示，而且它們也適用于對物理世界進行建模，例如，分子結(jié)構(gòu)以及物理系統(tǒng)中物體之間的交互。因此，捕捉特定圖形族系分布的能力在實際生活中有很多應(yīng)用。例如，從圖形模型中進行采樣可以致使發(fā)現(xiàn)新的配置，而這些配置所具有的全局屬性與藥物發(fā)現(xiàn)中所需要的是一樣的（Gómez-Bombarelli等人于2016年提出）。要想獲得自然語言句子中的圖形結(jié)構(gòu)語義表示（Kuhlmann和Oepen于2016年提出），需要具有能夠在圖上對（條件）分布進行建模的能力。圖形上的分布還可以為圖形模型的貝葉斯結(jié)構(gòu)學(xué)習(xí)提供先驗（Margaritis于2003年提出）。

生成過程中所采取步驟的描述

我們至少從兩個角度對圖形的概率模型進行了廣泛研究。一種方法是基于隨機圖形模型，將概率分配給大的圖形類型（Erdos和Rényi于1960年、Barabási和Albert于1999年提出）。這些都具有很強的獨立性假設(shè)，并且被設(shè)計成僅捕捉某些特定的圖形屬性，例如度數(shù)分布（degree distribution）和直徑。雖然這些方法已被證明在對社交網(wǎng)絡(luò)等領(lǐng)域進行建模時是有效的，但它們在更加豐富的結(jié)構(gòu)化領(lǐng)域上應(yīng)用還存在很大的挑戰(zhàn)，其中，細微的結(jié)構(gòu)差異在功能上可能是具有重要意義的，例如在化學(xué)中領(lǐng)域或自然語言中所表示的意義。

一個更具表現(xiàn)力但也更為脆弱的方法則是使用圖形語法，它將機制從形式語言理論中泛化到非序列結(jié)構(gòu)模型中（Rozenberg于1997年提出）。圖語法是重寫規(guī)則的系統(tǒng)，通過中間圖的一系列轉(zhuǎn)換遞增地導(dǎo)出輸出圖。雖然符號圖形語法（symbolic graph grammars）可以使用標(biāo)準(zhǔn)技術(shù)進行隨機化或加權(quán)（Droste和Gastin于2007年提出），但從可學(xué)習(xí)性的觀點來看，仍然存在兩個需要解決的問題。首先，從一組未經(jīng)注釋的圖形中引入語法是非常重要的，因為要想對可能用于構(gòu)建圖形的結(jié)構(gòu)構(gòu)建操作進行理解在算法上是很難進行的（Lautemann于1988年、Agui?aga等人于2016年提出）。其次，與線性輸出語法一樣，圖形語法在語言內(nèi)容和要排除內(nèi)容之間的區(qū)分上存在很大的困難，使得這種模型對于一些應(yīng)用程序來說是不適合應(yīng)用的，其中，它不適合將0概率分配給某些特定圖形。

圖形傳播過程的示意圖（左），節(jié)點選擇 fnodes模塊（右）

本文引入了一種新的、富有表現(xiàn)力的圖形模型，它不需要做任何結(jié)構(gòu)性假設(shè)，也避免了基于語法的技術(shù)的脆弱性。我們的模型以類似于圖形語法的方式生成圖形，其中在導(dǎo)出過程中，新結(jié)構(gòu)（特別是新節(jié)點或新邊緣）被添加到現(xiàn)有圖形中，并且該添加事件的概率取決于圖形導(dǎo)出的歷史記錄。為了在導(dǎo)出的每個步驟中對圖形進行表示，我們使用一個基于圖形結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)（圖形網(wǎng)絡(luò)）表示。最近，人們對于用于學(xué)習(xí)圖形表示和解決圖形預(yù)測問題的圖形網(wǎng)絡(luò)（graph nets）很感興趣。這些模型是根據(jù)所利用的圖形進行構(gòu)造的，并且以獨立于圖形大小的方式進行參數(shù)化，因此針對同構(gòu)圖形具有不變性，從而為我們的研究目的提供了一個很好的匹配。

在三組數(shù)據(jù)集中對圖形模型和LSTM模型進行訓(xùn)練的曲線

我們在生成具有某些常見拓撲性質(zhì)（例如：周期性）的隨機圖形，和以非條件或條件的方式生成分子圖形的任務(wù)中對我們的模型進行了評估。我們提出的模型在所有的實驗中都表現(xiàn)良好，并且比隨機圖形模型（random graph models）和長短期記憶網(wǎng)絡(luò)基線（LSTM baselines）獲得了更好的結(jié)果。

本文所提出的是能夠生成任意圖形的強大模型。然而，這些模型依然面臨著許多挑戰(zhàn)。在本文中，我們將討論未來會面臨的一些挑戰(zhàn)及可能的解決方案。

排序

節(jié)點和邊緣的排序?qū)τ趯W(xué)習(xí)和評估而言都很重要，在實驗中，我們總是使用預(yù)定義的分配方式排序。然而，通過將排序π視為潛在的變量來學(xué)習(xí)節(jié)點和邊緣的排序也許是可能的，這在未來將是一個有趣的探索方向。

長序列

圖形模型所使用的生成過程通常是一個長的決策序列，如果其他形式的圖形線性化是可用的（例如:SMILES），那么這樣的序列通常會縮短2-3倍。這對于圖形模型而言是一個很大的劣勢，這不僅難以獲得準(zhǔn)確的概率，還會使訓(xùn)練變得更加困難。為了緩解這一問題，我們可以調(diào)整圖形模型，以便使其與問題域進行更多地關(guān)聯(lián)，從而將多個決策步驟和循環(huán)轉(zhuǎn)為單個步驟。

可擴展性

可擴展性是對本文所提出的圖形生成模型的一個挑戰(zhàn)。圖形網(wǎng)絡(luò)使用固定的傳播步驟T來上傳圖形中的信息。然而，大的圖形往往需要使用大量的T來獲取足夠的信息，這會限制這些模型的可擴展性。為了解決這一問題，我們可以使用依次掃描邊緣的模型（Parisotto等人于2016年提出），或許采取一些由粗到精的生成方法。

訓(xùn)練難度

我們發(fā)現(xiàn)訓(xùn)練這樣的圖形模型要比訓(xùn)練典型的長短期記憶網(wǎng)絡(luò)模型更為困難，這些模型所要進行訓(xùn)練的序列一般比較長，并且模型結(jié)構(gòu)不斷變化還會導(dǎo)致訓(xùn)練不穩(wěn)定。降低學(xué)習(xí)速率可以解決很多不穩(wěn)定問題，但通過調(diào)整模型可以獲得更加令人滿意的解決方案。

本文中，我們提出了一個強大的深度生成模型，其能夠通過一個序列性過程生成任意形。我們在一些圖形生成問題中對它的屬性進行了研究。這一模型已經(jīng)展現(xiàn)出很大的潛力，并且與標(biāo)準(zhǔn)LSTM模型相比具有獨特的優(yōu)勢。我們希望我們的研究成果能夠促進這方面的進一步研究，進而獲得更好的圖形生成模型。