总结 | 四篇图网络综述文章提出的Future Directions

文 | 全世界最乖巧的小猪

A Comprehensive survey on Graph Neural Networks

1. 网络加深(Go Deep)

深度学习的成功在于深度神经架构。例如在图像分类中,ResNet模型有152层。

然而,当涉及到图结构时,实验研究表明[147],随着层数的增加,模型性能显著下降。这可能是因为图卷积使得相邻结点的表示更加相似,因此理论上,在无限次卷积的情况下,所有结点的表示都将收敛到一个点。这就提出了一个问题,即网络加深对于学习图结构化数据是否仍然是一个好策略。

2. 感受野(Receptive Field)

结点的感受野是指包括中心结点及其相邻结点在内的一组结点。结点的邻居数遵循幂律分布。有些结点可能只有一个邻居,而其他结点可能有多达数千个邻居。虽然已经采用了抽样策略[24]、[26]、[27],但是如何选择一个具有代表性的结点感受野仍有待探索。

3. 可扩展性(Scalability)

大多数图神经网络不能很好地适用于大型图(large graph),其主要原因是在叠加多层图卷积时,一个结点的最终状态涉及到大量相邻结点的隐藏状态,导致反向传播的复杂性很高。虽然有几种方法试图通过快速采样[45]、[46]和子图训练[24]、[27]来提高模型效率,但它们的可扩展性仍不足以处理具有大型图的深层架构。

4. 动态与异构性(Dynamics and Heterogeneity)

目前大多数的图神经网络都是处理静态同构图。

静态:假设图结构是固定的。

同构:假设图中的结点和边来自单一来源(single source)。

然而,这两个假设在许多情况下并不现实。在社交网络中,新的人可以随时进入网络,现有的人也可以退出网络。在推荐系统中,产品可能有不同的类型,其中输入可能有不同的形式,如文本或图像。因此,应该开发新的方法来处理动态和异构的图结构。

参考文献:

[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)

由于图数据的结构千差万别,现有的方法无法处理所有这些数据。例如,大多数方法都集中在同构图上,而很少研究异构图,尤其是那些包含不同形式的图,如[120]。在有符号网络(signed networks)中,负边表示节点之间的冲突,它也具有独特的结构,并对现有的方法提出了额外的挑战[121]。表示两个以上对象之间复杂关系的超图[122]也未被研究。下一个重要的步骤是设计特定的深度学习模型来处理这些不同类型的图。

2. 动态图(Dynamic graphs)

现有的方法大多集中在静态图上。然而,许多真实的图形本质上是动态的,结点、边及其特征可以随着时间的推移而改变。例如,在社会网络中,人们可以建立新的社会关系,消除旧的关系,他们的爱好和职业等特征会随着时间的推移而改变。新用户可以加入网络,而旧用户可以离开。如何对动态图的演化特征进行建模,并支持逐步更新模型参数,这在很大程度上仍然是文献中的开放问题。一些初步的工作试图用图RNN架构来解决这个问题,结果还不错[95],[97]。

3. 可解释性(Interpretability)

由于图通常与其他学科相关,因此解释图的深度学习模型对于决策问题至关重要。例如,在医学或与疾病相关的问题中,可解释性对于将计算机实验转化为临床应用是非常重要的。然而,基于图的深度学习的可解释性比其他黑盒模型更具挑战性,因为图中的结点和边之间存在着高度互联(heavily interconnected)。

4. 组合性(Compositionality)

如前几节所示,许多现有的体系结构可以一起工作,例如使用GCN作为GAE或GRAPH RNN中的层。除了设计新的构建块之外,如何以原则性的方式组合这些架构也是一个有趣的未来方向。最近的一项工作,Graph Networks[9]迈出了第一步,重点是使用GNN和GCN的通用框架解决关系推理问题。

参考文献:

[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. 浅层结构(Shallow Structure)

传统的深度神经网络可以叠加数百层以获得更好的性能,因为深度神经网络的结构参数较多,大大提高了表达能力。然而,图神经网络往往是浅层的,大部分都不超过三层。叠加多个GCN层将导致过度平滑,也就是所有结点将收敛到相同的值。尽管一些研究人员已经设法解决了这个问题[52],[53],但它仍然是GNN的最大限制。设计真正的深度GNN是未来研究的一个令人兴奋的挑战,将对理解GNN做出巨大贡献。

2. 动态图(Dynamic Graphs)

另一个具有挑战性的问题是如何处理具有动态结构的图。静态图是稳定的,因此可以对其进行可行性建模,而动态图则引入了变化的结构。当边和结点出现或消失时,GNN不能自适应地改变。动态GNN正被积极研究,我们认为它是一个关于通用GNN稳定性和适应性的里程碑。

3. 非结构场景(Non-Structural Scenarios)

虽然我们已经讨论了GNN在非结构化场景中的应用,但是我们发现没有从原始数据生成图的最佳方法。在图像领域,一些工作利用CNN获取特征图,然后将它们上采样,形成超像素作为结点[56],而另一些工作则直接利用一些目标检测算法来获取目标结点。在文本域[17]中,一些工作使用句法树作为句法图,而其他工作则采用完全连接的图。因此,找到最佳的图形生成方法将提供更广泛的领域,GNN可以在这些领域做出贡献。

4. 可扩展性(Scalability)

如何在社交网络或推荐系统等网络规模的条件下应用嵌入方法,对于几乎所有的图嵌入算法来说都是一个致命的问题,GNN也不例外。扩展GNN很困难,因为许多核心步骤在大数据环境中计算消耗非常大。关于这种现象有几个例子:首先,图数据是非欧的,每个结点都有自己的邻域结构,因此不能应用批处理。然后,当有数百万个结点和边时,计算图拉普拉斯也是不可行的。此外,我们还需要指出,缩放(scaling)决定了算法是否能够应用于实际应用。有几项工作提出了解决这一问题的办法[105],我们正在密切关注这一进展。

参考文献:

[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. 如何得到准确的图结构作为图网络的输入

深度学习直接作用于原始感官数据(图像、文本),而如何将这些原始感官数据转化为准确的结构性表示(图结构),最好的方法目前还不得而知。有一种方法是使用全连接图,但这种表示可能无法准确地对应真实实体。另外,比起全连接图,很多情况下图结构是非常稀疏的,如何确定稀疏性?一些论文提出了解决方法[1,2,3,4],但还没有公认的唯一解决方法。这个问题一旦解决,就能打开更有效且灵活的推断算法的大门。

2. 如何在计算过程中适应性地修正图结构

如果一个物体分裂成多个,那么表示该物体的结点也应该分裂成多个结点, 同样,应该增加或移除边的连接,只保留有联系的物体之间的边。该如何保证这种适应性,一些研究也提出了它们的解决方案[3,4]。

3. 可解释性与可视化

人类认知作出了一个强有力的假设,即世界是由物体和关系组成的,由于图网络也作出了类似的假设,他们的行为往往更易于解释。图网络运作的实体和关系通常与人类理解的事物相对应,从而支持更可解释的分析和可视化[5]。进一步探讨图网络行为的可解释性是今后工作的一个有趣方向。

参考文献:

[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


本文总结

综合以上四篇综述文章,图网络的Future Directions主要包括:

1. 网络加深

2. 动态与异构图

3. 可扩展性(large graph)

4. 可解释性

5. 非结构性图构建

6. 组合性

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,312评论 5 473
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,578评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,337评论 0 333
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,134评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,161评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,303评论 1 280
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,761评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,421评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,609评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,450评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,504评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,194评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,760评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,836评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,066评论 1 257
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,612评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,178评论 2 341