【斯坦福CS224W】图神经网络理论，77页ppt

图机器学习讲述关于《图神经网络理论》最新课程。

图网络(GNNs)的新变体层出不穷，但是却鲜有对图网络框架的理论分析。Kipf在2017年提出的GCN中，曾从图上的谱分析的角度给出了GCN的理论基础；近期也有日本研究者从图信号处理的角度，表明GNNs只是一个低频滤波器(arxiv.org/abs/1905.09550)。而本文尝试从图同构的角度出发，以Weisfeiler-Lehman Isomorphism Test (WL test)为基础，给出了GNNs表征能力的精彩理论分析，具体的贡献总结如下：

作者表明，在区别不同图结构时，GNNs最多只能取得和 WL test 一样效果，即，GNNs表征能力的上限是WL test；

作者也给出了构建GNNs的条件，满足这些条件后，GNNs的表征能力和 WL test一样强；

给出了GCN和GraphSAGE等传统图网络框架不能区分的网络结构；

建立了一个简单的框架GIN，并在理论上证明了其表征能力和 WL test一样强。

总结起来，全文需要回答两个关键性的问题：

• GNNs表征能力的上限是什么？
• 怎样的GNNs 框架设计才能达到最好的表征能力？