一般框架
aggregate：一个节点如何把它的邻居节点聚合起来
combine：聚合的特征 a 怎么和上一层的特征 h combine
不同的GNN都可以归纳到这两个框架下来。
Aggregation-based GNNs 的Agg函数与Comb函数的设计一般都是靠经验和启发式信息。
- 怎么样的设计才能达到最好的表征能力？
- GNNs框架表征能力上限是什么？
解决问题思路
- 表征能力的评价标准：图同构
如果GNNs对图的嵌入能区分不同构的图，则有较强的表征能力。
图同构：具有相同节点数的G1和G2，若存在两图节点之间的一一映射，使得邻接矩阵不变，则同构。
- 图同构评价标准：WL test
WL test是一种判断是否同构的有效算法。 - GNNs 能否具有和WL test一样的表征能力？有的话，怎么设计达到和WL一样的水平？
理论框架
先验知识
- Countable feature space
- GNNs的聚合框架可以看作是multiset函数。
multiset：包含重复元素的集合。 -
聚合：
如果有两层聚合，无论是GCN还是WL test，以蓝色节点为例，先由其二阶邻居信息聚合得到一阶邻居节点信息，再由一阶邻居信息聚合得到自己。
WL test 是由单射函数（hash，不同输入得到不同输出）聚合
GNN 是由max pooling 或者 mean pooling来聚合（不是单射函数）
重要结论
- GNNs框架的表征能力上界是WL test
-
如果GNNs的聚合函数是定义在multiset上的单射函数，那么GNNs和WL的表征能力一样强。
无论是aggregation函数还是combine函数，还是readout函数，最好都是injective，能力才能最强。
-
具体设计
c是当前节点信息，X是邻居节点信息，可以找到一个函数 f(x),同时运用于当前节点和邻居节点，则agg和com合起来表示为h(c,X).
其中 φ和f函数都只说明了存在性，并没有给定具体形式，作者使用MLP拟合（具有泛化能力）。
\epsilno理论上只能是无理数（在实验中可以是0）， 这样能把节点和其邻居节点区分开。
分析其他GNN框架
- GCN是把邻居节点加和求平均，再经过一个MLP（乘W，送入Relu）
A. 这说明单层感知机会把不同的局部结构map到相同的emb，从而导致不能区分图；
B. 也说明单层感知机不具有万能拟合能力；
C. 就算能map到不同的emb，也有可能导致线性分类器失效（XOR）。 - mean 和 max pooling区分不出来某些网络结构。
但是采用mean和max pooing的框架（GCN、GraphSage）表现都很好，那么它们学到什么？
mean pooling 学到的是分布。
mean只能区分不同distribution的局部结构。
所以在下述情况中，mean也可以表现得很好：
（1）当任务和节点feature的分布相关，而与具体的局部结构无关时；
（2）当节点具有丰富的feature，很少重复时。
这就解释了为什么GCN在做节点分类时，效果很好，因为每个节点的特征很难重复。
max pooling 学到的是 underlying set。
max处理muliset时，只关心其对应的underlying set。所以 max既没有学到局部结构，也没有学到distribution。
当我们关心 representative element 或者 “skeleton”时， max会有好效果。
GIN
- 为什么没有做节点分类？
GIN框架关心的是如何表征图的拓扑结构信息，而节点分类结果与节点feature关系最大； - 本文给出了GNNs的上界，所以基于aggregation的GNNs已经有天花板，但是不能考虑连边的方向的和权重；
- 其他的聚合框架没有分析，比如LSTM-based 和 Attention-based；
- 如果节点的feature space是连续的，则该文的分析框架失效；
- 不同的任务关注的网络信息不同，有的只关心节点特征，有的只关心网络拓扑结构，本文给出了如何选择不同聚合函数的范式。
WL-test 几乎不损失信息
GNNs存在压缩表示，会损失信息。
图网络读书分享会18期总结
