大热下的 GNN 研究面临哪些“天花板”?未来的重点研究方向又在哪?

 人工智能技术     |      2020-05-15 16:08

作为脱胎于图论研究的热门研究领域,图神经网络(GNN)与经典的 WL 算法有诸多相似之处。众所周知,强大的 WL 算法对于聚合函数的单射性质有很强的要求,那么强大的 GNN 应该具备哪些性质呢?本文从对 WL 算法的分析入手,介绍了 GNN 的局限性,指出了未来可能的重点研究方向。

图 1:通往更强大的 GNN 的道路

对于图表征任务,我们有两种常用的范式:图核(Graph Kernel)和图神经网络(Graph Neural Network,GNN)。通常,图核基于图分解以一种无监督的方式创建图的嵌入。例如,我们可以计算一张图中三角形或更一般的三元组的个数,然后使用该计数结果来得到嵌入。众所周知,这是图元核(Graphlet Kernel)的一个实例。

图 2:以上所有图元的尺寸为 4。计算图中所有四元组的每种 图元 的个数可以得到一个 图元核。

这种范式主要的研究动机是:创建一种保持图之间同构关系的嵌入(即两张图是同构的,当且仅当与它们相对应的嵌入是相同的)。显然,如果有这样的嵌入,我们就可以解决图的同构问题。

而在当前看来,我们知道这个问题要比「P 问题」(存在多项式时间复杂度解法的问题)更难解决。然而,也存在诸如「Anonymous Walk Embeddings」(相关论文:https://arxiv.org/abs/1805.11921)这样保持了同构性的嵌入方法(当然,这是以计算时间为代价的)。

尽管如此,在这里本文想传达的主要信息是:人们曾经设计图核来解决图同构问题。如果嵌入能够将更多种类的图区分开来,那么嵌入就越好。曾经,这种原则被大家奉为圭臬。

图神经网络诞生后,这种原则产生了改变。除了解决图同构这一问题之外,我们可以试着解决任意给定的问题(例如,找到最短路径或者检测环结构)。这是十分有发展前景的,因为它让我们可以根据网络能够解决的问题来指导我们的网络设计。这听起来似乎很神奇:你可以直接训练你的网络,然后它就会为你找到合适的解,而不需要使用一些成熟的组合优化算法。

但我们也不禁要问:神经网络是通过随机梯度下降(SGD)搜索可行解的,它涉及许多其它的技术问题,如果你被困在了一个糟糕的局部最优点该怎么办?它如何才能解决任意的问题呢?事实上,图神经网络存在一些局限性,本文将在下面娓娓道来。


  • 共5页:
  • 上一页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 下一页