阅读笔记|GIN（图神经网络有多强大? HOW POWERFUL ARE GRAPH NEURALNET WORKS）架构|人工智能|神经网络

论文： HOW POWERFUL ARE GRAPH NEURALNET WORKShttps://arxiv.org/abs/1810.00826v1
来源：ICLR 2019
代码： GitHub - weihua916/powerful-gnns: How Powerful are Graph Neural Networks?

【阅读笔记|GIN（图神经网络有多强大? HOW POWERFUL ARE GRAPH NEURALNET WORKS）】内容：从理论上证明了邻域聚合（或称消息传递）的GNN变体的表达能力的严格上限（WL同构检验），同时设计了一个此框架下，最强大的GNN，即GIN

1 邻域聚合/消息传递框架

文章图片
对每一个节点，首先从领域聚合消息，然后用其更新自身的节点嵌入

2 如何评价GNN

评价标准：图同构
- 定义：具有相同节点数的G1和G2，若存在两图节点之间的一一映射，使得邻接矩阵不变，则同构
- 如果一个GNN可以将不同构的图映射到不同的嵌入中，那么该GNN有较强的表征能力
图同构的一个启发式算法：WL test 什么是Weisfeiler-Lehman(WL)算法和WL Test？ - 知乎
- 文章图片
- 文章证明了，当满足适当的条件下，GNN可以达到WL的能力，即GNN的表达能力上限为WL

3 GNN的上限以及如何达到上限为什么上限是WL

文章图片
文章图片
- 再来看看GNN和WL两个公式，我们发现，他们实际上十分相像，因而有了进行比较的念头
文章图片

上图说明了GNN和WL test的相同点和区别
相同：两跳聚合的时候，都是先由其二阶邻居信息聚合得到一阶邻居节点信息，再由一阶邻居信息聚合得到自己
不同：WL test 是由哈希函数聚合，GNN 是由max pooling 或者 mean pooling来聚合
- 哈希函数是单射函数，因而可以保证不同构的图映射到不同的嵌入中，但是max和mean pool并不是单射

可以保证单射的GNN聚合方法：SUM

文章图片
- 从表达能力上说，sum>mean>max，sum可以区分多集（即拥有重复元素的集合）；mean可以区分不同的分布，而max只能区分底层集合
文章图片
- 上图表示了三种不同的情况
  - （a）:MEAN和MAX都失效了，因为周围节点的底层集合（{蓝}）是相同的，分布（全蓝）是相同的
  - （b）:MAX失效，MEAN有效，因为底层集合（{绿，红}）相同，但分布（左右两图红蓝出现的概率）不同
  - （c）:MEAN和MAX都失效，因为底层集合（{绿，红}）和分布（左右两图红蓝出现的概率）都相同
- 但是，如果使用sum函数的话，这三种情况都是何以区分的
  - （a）：2蓝和 3蓝
  - （b）：1红1绿和 2红1绿
  - （c）：1红1绿和 2红2绿
那为什么采用Mean的GCN和采用Max的GraphSAGE这么有效呢？
- 因为很多时候，我们的数据集没有那么严苛
- 当数据集中没有多集的时候，max就已经够用了；当多集的分布不同的时候，mean也够用了