本章主要内容：
本章主要学习GNN模型的表达能力expressive power，即将不同图数据表示为不同嵌入向量的能力。
我们主要考虑图中节点的局部邻居结构 local neighborhood structure 信息，GNN通过计算图 computational graph 捕获节点的局部邻居结构。
因此，GNN无法区分具有相同计算图的节点。
如果GNN能将具有不同计算图的节点区分开来（即形成一个单射rejective函数，不同计算图的节点被表示为不同的嵌入），则我们称该GNN具有强表达能力，即计算图中的信息得到了完全的保留。要实现这样的区分度，需要GNN的聚合函数是单射的。
已知聚合函数表达能力越强，GNN表达能力越强，单射聚合函数的GNN表达能力最强。我们设计具有最强表达能力的GNN模型：
邻居聚合过程可被抽象为一个输入为multi-set的函数。
均值池化（GCN）无法区分各类占比相同的multi-set，最大池化（GraphSAGE）无法区分具有相同的不同类的multi-set，因此都不单射，不够具有表达能力。
为了建立在信息传递message-passing框架下的最强GNN，我们需要设计multi-set上的单射邻居聚合函数。根据Xu et al. ICLR 20191 的定理，我们可以设计一个含 Φ 和 f 两个未知函数、并应用sum-pooling的函数来表示这样的单射函数，根据universal approximation theorem2 可知 Φ \PhiΦ 和 f ff 可以通过MLP拟合得到。从而建立 Graph Isomorphism Network (GIN) 模型。
GIN是WL graph kernel3 的神经网络版。GIN和WL graph kernel3 都可以区分大部分真实图。
在表达能力上，sum（multiset） > mean（distribution）> max（set）
1. How Expressive are Graph Neural Networks?
- 对GNN定义、聚合邻居信息思想的复习内容不赘。
- 本节课主要探讨，在已经提出GCN、GAT、GraphSAGE、design space等众多GNN模型的前提下，各种模型的表示能力（区分不同图结构的能力）如何？我们如何设计这样一种表示能力最强的模型？
- GNN模型实例
- GCN：mean-pool + Linear + ReLU non-linearity
- GraphSAGE（以最大池化为例）：MLP + max-pool
- 本课程中用节点颜色指代特征feature，同色即特征相同。
如图中举例图中所有节点的特征都相同（黄色）。
图上的信息分为结构信息和特征信息，因为特征相同，所以无法仅凭特征来区分节点了（如果特征全都不一样，只需要看特征向量就能将节点区分开了）。让所有特征相同可以更好看出GNN如何捕捉结构信息。
- 局部结构信息
我们感兴趣于量化节点的局部结构信息。
- 例子1：节点1和节点5，因其度数不同而具有不同的局部结构信息。
- 例子2：节点1和节点4，具有相同度数，但到其两跳邻居的信息上，可以区分两点：其邻居的度数不同。
- 例子3：节点1和节点2，具有相同的邻居结构，因为在图中是对称的。（不可区分）（无论多少跳邻居上，都具有相同的局部结构）（位置同构）
- 我们接下来就要分析GNN节点嵌入能否区分不同节点的局部邻居结构，在什么情况下会区分失败。
GNN通过计算图得到局部邻居结构。
- 计算图
- GNN每一层聚合邻居信息（节点嵌入），即通过其邻居得到的计算图产生节点嵌入。
- 节点1和节点2的计算图：
- 上图两个计算图本质上是一样的：GNN只能识别特征，不能识别ID
因为计算图相同，这两个节点将被嵌入到同一个表示向量（即在表示域重叠，GNN无法区分这两个节点）。
- 一般来说，不同的局部邻居会得到不同的计算图：
节点1和节点2由于计算图相同，所以GNN无法区分。理论上节点3、4、5由于计算图不同是可能由GNN区分开的。
表达能力最强的GNN能区分开任意计算图不同的节点。
- 计算图和对应节点的有根子树结构rooted subtree structure5相同，通过从根节点逐邻居展开计算图而得到。
- GNN节点嵌入捕获这个rooted subtree structures，表示能力最强的GNN模型将不同的rooted subtree结构映射到不同的节点嵌入中（图中表示为不同颜色）：
- 单射injective函数：将不同自变量映射为不同的因变量，这样可以完整保留输入数据中的信息
- 表示能力最强的GNN就应该单射地映射子树到节点嵌入（即不同的子树映射为不同的嵌入）
- 同深度的子树可以从叶节点到根节点迭代表示信息，来进行区分
- 如果GNN每一步聚合都可以保留全部邻居信息，那么所产生的节点嵌入就可以区分不同的有根子树，也就达成了GNN具有最强表示能力的效果。
- 所以表示能力最强的GNN就是每一步都使用单射邻居聚合函数（保留全部信息），把不同的邻居映射到不同的嵌入上。
- 总结
为得到节点嵌入，GNN使用计算图（以节点为根的子树），如果每层都使用单射的聚合函数，就可以达成区分不同子树的效果。
2. Designing the Most Powerful Graph Neural Network
- GNN的表示能力取决于其应用的邻居聚合函数。聚合函数表达能力越强，GNN表达能力越强，单射聚合函数的GNN表达能力最强。
接下来本课程将理论分析各聚合函数的表示能力。
- 邻居聚合过程可以被抽象为multi-set（一个元素可重复的集合，在此处指节点的邻居集合，元素为节点，节点特征可重复）上的函数。如图中以圆点集合作例，点同色指特征相同：
- 接下来我们分析GCN和GraphSAGE的聚合函数
- GCN：mean-pool
mean-pool + Linear + ReLU non-linearity
根据Xu et al. ICLR 20191 得到定理：GCN的聚合函数无法区分颜色占比相同的multi-set。
假设不同颜色的特征是独热编码特征，如图所示黄蓝二色特征：
GCN无法区分不同multi-set的一个实例：
- GraphSAGE：max-pool
MLP + max-pool
根据Xu et al. ICLR 20191 得到定理：GraphSAGE的聚合函数无法区分具有相同的不同颜色（即具有一样的多种颜色，或者不重复颜色组成的集合相同）
一个失败案例：假设上一层节点嵌入经过一个单射的MLP函数形成不同的独热编码向量，经逐元素最大池化后得到相同输出：
- 根据上文对GNN表示能力的分析，我们得出的主要结论takeaway9为：
- GNN的表示能力由其邻居聚合函数决定
- 邻居聚合是个multi-set上的函数，multi-set是一个元素可重复的集合
- GCN和GraphSAGE的聚合函数都不能区分某些基本的multi-set，因此都不单射，不够具有表达能力。
- 我们的目标是设计信息传递框架下表示能力最强的GNN，这要求我们设计出multi-set上的单射邻居聚合函数。
- 一个作为证明的直觉举例：
f 得到颜色的独热编码，对其求和就能得到输入multi-set的全部信息（每类对应向量的一个索引，每个索引的求和结果就对应该类的节点数量，就可以区分不同类任何个数的情况）
如图所示：
- GIN与WL graph kernel的关系
我们通过将GIN与WL graph kernel（获得图级别特征的传统方法）做关联，来全面了解GIN模型。
GIN可以说是WL graph kernel的神经网络版。
- GIN和WL graph kernel
GIN相当于可微神经网络版的WL graph kernel
GIN相较于WL graph kernel的优点在于：
- 节点嵌入是低维的，因此可以捕获到细粒度的节点相似性14
- GINConv的参数可被学习得到并应用于下流任务15
- GIN的表示能力
由于GIN与WL graph kernel之间的关系，二者的表示能力是相同的，也就是对于一样的图，要么二者都能区分，要么都不能区分。
在理论上和实践上，WL graph kernel都能区分现实世界的大部分图16，因此GIN也能区分现实世界的大部分图。
- 本节课总结
- 我们设计了一个可以建模单射的multi-set函数的神经网络
- 我们用这个神经网络来聚合邻居信息，得到GIN：表示能力最强的GNN模型
- 关键在于用element-wise sum pooling代替mean-/max-pooling
- GIN与WL graph kernel有关
- GIN和WL graph kernel都能区分现实世界的大部分图
- 各种池化方法的能力：
sum能区分整个multiset，mean只能区分不同的分布，max只能区分元素类型集合
- 增加GNN的表示能力
对于类似“节点处于不同环中”这种问题，GNN仍然无法区分（因为计算图相同）。解决方法可以是添加可区分节点的feature17，也可以使用reference node来区分相同计算图等。后续课程将会讲述具体做法。
