【ICLR2019】图神经网络“理论在哪里“？希望这篇论文给你答案

2018 年 12 月 25 日 专知

【导读】近日ICLR 2019论文录用结果出来，专知团队关注到这一篇论文《How Powerful are Graph Neural Networks?》，并且最终的 Area Chair给出的意见是：对当前图神经网络方向有极好的理论贡献，录用为Oral。当前图神经网络是机器学习中一个越来越受欢迎的研究课题，这篇论文聚焦图神经网络的理论分析，很好地研究了一些新提出的变体的表征能力，也提出了根据WL test构建问题的框架，以及GIN体系结构的想法。

Metareview: Graph neural networks are an increasingly popular topic of research in machine learning, and this paper does a good job of studying the representational power of some newly proposed variants. The framing of the problem in terms of the WL test, and the proposal of the GIN architecture is a valuable contribution. Through the reviews and subsequent discussion, it looks like the issues surrounding Theorem 3 have been resolved, and therefore all of the reviewers now agree that this paper should be accepted. There may be some interesting followup work based on studying depth, as pointed out by reviewer 1, but this may not be an issue in GIN and is regardless a topic for future research.

Confidence: 4: The area chair is confident but not absolutely certain

Recommendation: Accept (Oral)

题目： How Powerful are Graph Neural Networks?

作者：Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Jegelka

【摘要】用于图的表示学习的图神经网络（GNN）广泛地遵循邻域聚合框架，其中通过递归地聚合和变换其相邻节点的特征向量来计算节点的表示向量。学者们已经提出了许多GNN的变体，并在节点分类和图分类任务上取得了最先进的结果。然而，尽管GNNs使图形表示学习发生了革命性的变化，但对于它们的表示属性和局限性的理解却很有限。在这里，我们提出了一个理论框架，用于分析GNN在捕获不同图形结构时的表达能力。我们的结果表征了一些流行的GNN变体的辨别能力，例如Graph Convolutional Networks和GraphSAGE，并表明他们无法学会区分某些简单的图结构。然后，我们开发了一个简单的体系结构，该体系结构被证明是GNN类中最具表现力的体系，并且与Weisfeiler-Lehman图同构测试一样强大。我们在一些图分类基准上实证验证了我们的理论发现，并证明我们的模型达到了最先进的性能。

参考链接：

https://openreview.net/forum?id=ryGs6iA5Km

请关注专知公众号（扫一扫最下面专知二维码，或者点击上方蓝色专知）

后台回复“PGNN” 就可以获取论文的下载链接~

图神经网络相关综述文章可以参见专知以前公众号内容：

清华大学孙茂松课题组:《图神经网络: 方法与应用》综述论文

清华大学朱文武课题组：《图深度学习》综述论文

引言

学者们已经提出了许多具有不同邻域聚合和图级聚合方案的图神经网络GNN变体。根据经验，这些GNN在许多任务中实现了最佳的性能，例如节点分类，链接预测和图分类。然而，新GNN的设计大多基于经验直觉、启发式和实验试错。关于GNN的性质和局限性的理论知识很少，并且对GNN表征能力的形式化分析也很有限。

在这里，论文提出了一个理论框架来分析GNN的表征能力。正式地描述了不同的GNN变体在学习表示和区分不同的图结构时是如何表达的。提出的框架受到GNN与Weisfeiler-Lehman（WL）graph isomorphism test（Weisfeiler＆Lehman，1968）之间密切联系的启发，这是一个用来区分一部分图类强有力的检测(Babai & Kucera, 1979)。与GNN类似，WL测试通过聚合其网络邻居的特征向量来迭代地更新给定节点的特征向量。使WL test如此强大的原因在于其内射(or 单射)聚合更新将不同的节点邻域映射到不同的特征向量。我们的主要观点是，如果GNN的聚合方案具有高度表达性并且可以模拟内射函数，那么GNN可以具有和WL test一样强大的判别力。

为了从数学上形式化上述观点，我们的框架首先将节点邻居的特征向量抽象为多集(multiset)，即可能包含重复元素的集合。然后， GNN中的邻居聚合可以被抽象为多集上的函数。我们严格研究多集函数的不同变体，并从理论上刻画了它们的判别能力，即不同聚合函数如何区分不同的多集合。多集函数越具有判别性，底层GNN的表征能力就越强大。

论文的主要成果总结如下：

证明了GNN在区分图结构方面的能力不会超过WL test。
在邻居汇聚和图池函数上建立条件，得到的GNN与WL test一样强大。
确定了不能用流行的GNN变体来区分的图结构，例如GCN (Kipf & Welling, 2017)和GraphSAGE (Hamilton et al.， 2017a)，精确地描述了基于GNN的模型能够捕捉的图结构类型。
开发了一个简单的神经结构——图同构网络（Graph Isomorphism Network, GIN），并表明它的判别/表征能力等于WL test的功效。

论文通过图分类数据集上的实验来验证提出的理论，其中GNN的表达能力对于捕获图结构至关重要。特别是，将GNN的性能与各种聚合函数进行比较。结果证实，最强大的GNN（图同构网络（GIN））具有很高的表示能力，因为它几乎完全适合训练数据，而较弱的GNN变体往往严重不适合训练数据。此外，表示性能更强大的GNN通过测试集精度优于其他GNN，并在许多图分类基准上实现最优异的性能。

附全文内容