文 | 全世界最乖巧的小豬

A Comprehensive survey on Graph Neural Networks

1. 網(wǎng)絡(luò)加深（Go Deep）

深度學(xué)習(xí)的成功在于深度神經(jīng)架構(gòu)奔则。例如在圖像分類中，ResNet模型有152層。

然而释牺，當(dāng)涉及到圖結(jié)構(gòu)時(shí)睛琳，實(shí)驗(yàn)研究表明[147]盹愚，隨著層數(shù)的增加飞醉，模型性能顯著下降奈懒。這可能是因?yàn)閳D卷積使得相鄰結(jié)點(diǎn)的表示更加相似芍躏，因此理論上邪乍，在無限次卷積的情況下，所有結(jié)點(diǎn)的表示都將收斂到一個(gè)點(diǎn)对竣。這就提出了一個(gè)問題庇楞，即網(wǎng)絡(luò)加深對(duì)于學(xué)習(xí)圖結(jié)構(gòu)化數(shù)據(jù)是否仍然是一個(gè)好策略。

2. 感受野（Receptive Field）

結(jié)點(diǎn)的感受野是指包括中心結(jié)點(diǎn)及其相鄰結(jié)點(diǎn)在內(nèi)的一組結(jié)點(diǎn)否纬。結(jié)點(diǎn)的鄰居數(shù)遵循冪律分布吕晌。有些結(jié)點(diǎn)可能只有一個(gè)鄰居，而其他結(jié)點(diǎn)可能有多達(dá)數(shù)千個(gè)鄰居临燃。雖然已經(jīng)采用了抽樣策略[24]睛驳、[26]烙心、[27]，但是如何選擇一個(gè)具有代表性的結(jié)點(diǎn)感受野仍有待探索乏沸。

3. 可擴(kuò)展性（Scalability）

大多數(shù)圖神經(jīng)網(wǎng)絡(luò)不能很好地適用于大型圖（large graph）淫茵，其主要原因是在疊加多層圖卷積時(shí)，一個(gè)結(jié)點(diǎn)的最終狀態(tài)涉及到大量相鄰結(jié)點(diǎn)的隱藏狀態(tài)蹬跃，導(dǎo)致反向傳播的復(fù)雜性很高匙瘪。雖然有幾種方法試圖通過快速采樣[45]、[46]和子圖訓(xùn)練[24]蝶缀、[27]來提高模型效率丹喻，但它們的可擴(kuò)展性仍不足以處理具有大型圖的深層架構(gòu)。

4. 動(dòng)態(tài)與異構(gòu)性（Dynamics and Heterogeneity）

目前大多數(shù)的圖神經(jīng)網(wǎng)絡(luò)都是處理靜態(tài)同構(gòu)圖扼劈。

靜態(tài)：假設(shè)圖結(jié)構(gòu)是固定的驻啤。

同構(gòu)：假設(shè)圖中的結(jié)點(diǎn)和邊來自單一來源（single source）。

然而荐吵，這兩個(gè)假設(shè)在許多情況下并不現(xiàn)實(shí)骑冗。在社交網(wǎng)絡(luò)中，新的人可以隨時(shí)進(jìn)入網(wǎng)絡(luò)先煎，現(xiàn)有的人也可以退出網(wǎng)絡(luò)贼涩。在推薦系統(tǒng)中，產(chǎn)品可能有不同的類型薯蝎，其中輸入可能有不同的形式遥倦，如文本或圖像。因此占锯，應(yīng)該開發(fā)新的方法來處理動(dòng)態(tài)和異構(gòu)的圖結(jié)構(gòu)袒哥。

參考文獻(xiàn)：

[147]?Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning

[24] Inductive representation learning on large graphs

[26] Learning convolutional neural networks for graphs

[27] Large-scale learnable graph convolutional networks

[45]?Fastgcn: fast learning with graph convolutional networks via importance sampling

[46]?Stochastic training of graph convolutional networks with variance reduction

Deep Learning on Graphs: A Survey

1. 不同類型的圖（Different types of graphs）

由于圖數(shù)據(jù)的結(jié)構(gòu)千差萬別，現(xiàn)有的方法無法處理所有這些數(shù)據(jù)消略。例如堡称，大多數(shù)方法都集中在同構(gòu)圖上，而很少研究異構(gòu)圖艺演，尤其是那些包含不同形式的圖却紧，如[120]。在有符號(hào)網(wǎng)絡(luò)（signed networks）中胎撤，負(fù)邊表示節(jié)點(diǎn)之間的沖突晓殊，它也具有獨(dú)特的結(jié)構(gòu)，并對(duì)現(xiàn)有的方法提出了額外的挑戰(zhàn)[121]伤提。表示兩個(gè)以上對(duì)象之間復(fù)雜關(guān)系的超圖[122]也未被研究巫俺。下一個(gè)重要的步驟是設(shè)計(jì)特定的深度學(xué)習(xí)模型來處理這些不同類型的圖。

2. 動(dòng)態(tài)圖（Dynamic graphs）

現(xiàn)有的方法大多集中在靜態(tài)圖上肿男。然而识藤，許多真實(shí)的圖形本質(zhì)上是動(dòng)態(tài)的砚著，結(jié)點(diǎn)、邊及其特征可以隨著時(shí)間的推移而改變痴昧。例如，在社會(huì)網(wǎng)絡(luò)中冠王，人們可以建立新的社會(huì)關(guān)系赶撰，消除舊的關(guān)系，他們的愛好和職業(yè)等特征會(huì)隨著時(shí)間的推移而改變柱彻。新用戶可以加入網(wǎng)絡(luò)豪娜，而舊用戶可以離開。如何對(duì)動(dòng)態(tài)圖的演化特征進(jìn)行建模哟楷，并支持逐步更新模型參數(shù)瘤载，這在很大程度上仍然是文獻(xiàn)中的開放問題。一些初步的工作試圖用圖RNN架構(gòu)來解決這個(gè)問題卖擅，結(jié)果還不錯(cuò)[95]鸣奔，[97]。

3. 可解釋性（Interpretability）

由于圖通常與其他學(xué)科相關(guān)惩阶，因此解釋圖的深度學(xué)習(xí)模型對(duì)于決策問題至關(guān)重要挎狸。例如，在醫(yī)學(xué)或與疾病相關(guān)的問題中断楷，可解釋性對(duì)于將計(jì)算機(jī)實(shí)驗(yàn)轉(zhuǎn)化為臨床應(yīng)用是非常重要的锨匆。然而，基于圖的深度學(xué)習(xí)的可解釋性比其他黑盒模型更具挑戰(zhàn)性冬筒，因?yàn)閳D中的結(jié)點(diǎn)和邊之間存在著高度互聯(lián)（heavily interconnected）恐锣。

4. 組合性（Compositionality）

如前幾節(jié)所示，許多現(xiàn)有的體系結(jié)構(gòu)可以一起工作舞痰，例如使用GCN作為GAE或GRAPH RNN中的層土榴。除了設(shè)計(jì)新的構(gòu)建塊之外，如何以原則性的方式組合這些架構(gòu)也是一個(gè)有趣的未來方向匀奏。最近的一項(xiàng)工作鞭衩，Graph Networks[9]邁出了第一步，重點(diǎn)是使用GNN和GCN的通用框架解決關(guān)系推理問題娃善。

參考文獻(xiàn)：

[120]?Heterogeneous network embedding via deep architectures

[121]?Signed graph convolutional network

[122]?Structural deep embedding for hyper-networks

[95]?Dynamic graph neural networks

[97]?Dynamic graph convolutional networks

[9]?Relational inductive biases, deep learning, and graph networks

Graph Neural Networks: A Review of Methods and Applications

1. 淺層結(jié)構(gòu)（Shallow Structure）

傳統(tǒng)的深度神經(jīng)網(wǎng)絡(luò)可以疊加數(shù)百層以獲得更好的性能论衍，因?yàn)樯疃壬窠?jīng)網(wǎng)絡(luò)的結(jié)構(gòu)參數(shù)較多，大大提高了表達(dá)能力聚磺。然而坯台，圖神經(jīng)網(wǎng)絡(luò)往往是淺層的，大部分都不超過三層瘫寝。疊加多個(gè)GCN層將導(dǎo)致過度平滑蜒蕾，也就是所有結(jié)點(diǎn)將收斂到相同的值稠炬。盡管一些研究人員已經(jīng)設(shè)法解決了這個(gè)問題[52]，[53]咪啡，但它仍然是GNN的最大限制首启。設(shè)計(jì)真正的深度GNN是未來研究的一個(gè)令人興奮的挑戰(zhàn)，將對(duì)理解GNN做出巨大貢獻(xiàn)撤摸。

2. 動(dòng)態(tài)圖（Dynamic Graphs）

另一個(gè)具有挑戰(zhàn)性的問題是如何處理具有動(dòng)態(tài)結(jié)構(gòu)的圖毅桃。靜態(tài)圖是穩(wěn)定的，因此可以對(duì)其進(jìn)行可行性建模准夷，而動(dòng)態(tài)圖則引入了變化的結(jié)構(gòu)钥飞。當(dāng)邊和結(jié)點(diǎn)出現(xiàn)或消失時(shí)，GNN不能自適應(yīng)地改變衫嵌。動(dòng)態(tài)GNN正被積極研究读宙，我們認(rèn)為它是一個(gè)關(guān)于通用GNN穩(wěn)定性和適應(yīng)性的里程碑。

3. 非結(jié)構(gòu)場(chǎng)景（Non-Structural Scenarios）

雖然我們已經(jīng)討論了GNN在非結(jié)構(gòu)化場(chǎng)景中的應(yīng)用楔绞，但是我們發(fā)現(xiàn)沒有從原始數(shù)據(jù)生成圖的最佳方法结闸。在圖像領(lǐng)域，一些工作利用CNN獲取特征圖墓律，然后將它們上采樣膀估，形成超像素作為結(jié)點(diǎn)[56]，而另一些工作則直接利用一些目標(biāo)檢測(cè)算法來獲取目標(biāo)結(jié)點(diǎn)耻讽。在文本域[17]中察纯，一些工作使用句法樹作為句法圖，而其他工作則采用完全連接的圖针肥。因此饼记，找到最佳的圖形生成方法將提供更廣泛的領(lǐng)域，GNN可以在這些領(lǐng)域做出貢獻(xiàn)慰枕。

4. 可擴(kuò)展性（Scalability）

如何在社交網(wǎng)絡(luò)或推薦系統(tǒng)等網(wǎng)絡(luò)規(guī)模的條件下應(yīng)用嵌入方法具则，對(duì)于幾乎所有的圖嵌入算法來說都是一個(gè)致命的問題，GNN也不例外具帮。擴(kuò)展GNN很困難博肋，因?yàn)樵S多核心步驟在大數(shù)據(jù)環(huán)境中計(jì)算消耗非常大。關(guān)于這種現(xiàn)象有幾個(gè)例子：首先蜂厅，圖數(shù)據(jù)是非歐的匪凡，每個(gè)結(jié)點(diǎn)都有自己的鄰域結(jié)構(gòu)，因此不能應(yīng)用批處理掘猿。然后病游，當(dāng)有數(shù)百萬個(gè)結(jié)點(diǎn)和邊時(shí)，計(jì)算圖拉普拉斯也是不可行的稠通。此外衬衬，我們還需要指出买猖，縮放（scaling）決定了算法是否能夠應(yīng)用于實(shí)際應(yīng)用。有幾項(xiàng)工作提出了解決這一問題的辦法[105]滋尉，我們正在密切關(guān)注這一進(jìn)展玉控。

參考文獻(xiàn)：

[52]?Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning

[53]?Gated graph sequence neural networks

[56]?Semantic object parsing with graph LSTM

[17]?Iterative visual reasoning beyond convolutions

[105]?Graph convolutional neural networks for web-scale recommender systems

Relational inductive biases, deep learning, and graph networks

1. 如何得到準(zhǔn)確的圖結(jié)構(gòu)作為圖網(wǎng)絡(luò)的輸入

深度學(xué)習(xí)直接作用于原始感官數(shù)據(jù)(圖像、文本)兼砖，而如何將這些原始感官數(shù)據(jù)轉(zhuǎn)化為準(zhǔn)確的結(jié)構(gòu)性表示(圖結(jié)構(gòu))奸远，最好的方法目前還不得而知。有一種方法是使用全連接圖讽挟，但這種表示可能無法準(zhǔn)確地對(duì)應(yīng)真實(shí)實(shí)體。另外丸冕，比起全連接圖耽梅，很多情況下圖結(jié)構(gòu)是非常稀疏的，如何確定稀疏性胖烛？一些論文提出了解決方法[1,2,3,4]眼姐，但還沒有公認(rèn)的唯一解決方法。這個(gè)問題一旦解決佩番，就能打開更有效且靈活的推斷算法的大門众旗。

2. 如何在計(jì)算過程中適應(yīng)性地修正圖結(jié)構(gòu)

如果一個(gè)物體分裂成多個(gè)，那么表示該物體的結(jié)點(diǎn)也應(yīng)該分裂成多個(gè)結(jié)點(diǎn)趟畏， 同樣贡歧，應(yīng)該增加或移除邊的連接，只保留有聯(lián)系的物體之間的邊赋秀。該如何保證這種適應(yīng)性利朵，一些研究也提出了它們的解決方案[3,4]。

3. 可解釋性與可視化

人類認(rèn)知作出了一個(gè)強(qiáng)有力的假設(shè)猎莲，即世界是由物體和關(guān)系組成的绍弟，由于圖網(wǎng)絡(luò)也作出了類似的假設(shè)，他們的行為往往更易于解釋著洼。圖網(wǎng)絡(luò)運(yùn)作的實(shí)體和關(guān)系通常與人類理解的事物相對(duì)應(yīng)樟遣，從而支持更可解釋的分析和可視化[5]。進(jìn)一步探討圖網(wǎng)絡(luò)行為的可解釋性是今后工作的一個(gè)有趣方向身笤。

參考文獻(xiàn)：

[1] Visual interaction networks: Learning a physics simulator from video

[2] Relational neural expectation maximization: Unsupervised discovery of objects and their interactions

[3] Learning deep generative models of graphs

[4] Neural relational inference for interacting systems

[5] Learning a sat solver from single-bit supervision

本文總結(jié)

綜合以上四篇綜述文章豹悬，圖網(wǎng)絡(luò)的Future Directions主要包括：

1. 網(wǎng)絡(luò)加深

2. 動(dòng)態(tài)與異構(gòu)圖

3. 可擴(kuò)展性（large graph）

4. 可解釋性

5. 非結(jié)構(gòu)性圖構(gòu)建

6. 組合性