HOW POWERFUL ARE GRAPH NEURAL NETWORKS?(GIN)

GIN——Graph Isomorphism Network

normal message deliverer

related work

GraphSAGE(Inductive Representation Learning on Large Graphs)

突破传统基于矩阵分解的节点嵌入方式，GraphSAGE 通过采样和聚合节点局部邻域的特征信息来生成嵌入，同时学习节点邻域的拓扑结构和特征分布。这种方式避免为每个节点单独训练嵌入向量，提高了模型的泛化能力 。 

最大池化聚合器

逐元素最大池化：对邻居节点的每个特征维度独立取最大值，生成当前节点的新特征

平均池化聚合器

element-wise mean pooling：

文章中的一些理论和观点

作者提出并证明GNNs判别图同构的能力的上限是WL-test

其核心观点
"Our answer, in Theorem 3, is yes: if the neighbor aggregation and graph-level readout functions are injective, then the resulting GNN is as powerful as the WL test."

MEAN LEARNS DISTRIBUTIONS

Thus, the mean captures the distribution (proportions) of elements in a multiset, but not the exact multiset.

说明：基集一样的多重集由mean aggregator映射的分布是一样的

换句话说，假设不同的基集对应一种分布，那么mean可以区分这些不同的分布，但无法区分相同基集的不同多重集

回顾sum方法，我们就发现，sum可以区别不同的基集构成的多重集，和相同基集构成的多重集

题外话：这两个命题并不是等价的，它说明了相同基底多重集不能被区分，可事实上，不同基底的多重集也不一定能被区分。

那么mean的区分能力到底在哪里？这个是不确定的。

不过文章这个角度至少说明了在这个同基底多重集的判别下mean是弱的

MAX-POOLING LEARNS SETS WITH DISTINCT ELEMENTS

max的方法，区分能力进一步下降，但相应的其抗噪声能力却是较强的

文章指出“However, it may be suitable for tasks where it is important to identify representative elements or the “skeleton”, rather than to distinguish the exact structure or distribution.”

《识别骨干能力》

这一部分，作者目的在解释了其GIN网络在多重集上使用sum而非mean，max的原因

other aggregation

Attention(Graph attention networks), LSTM pooling(Inductive representation learning on large graphs)

GIN的构建

对于多重集只有sum方法是单射的，根据作者的理论只有aggregation和readout都是单射，才能使GNN的判别图同构的能力最强

Gin构建的核心思路

对应推论6，作者将节点label视为元素，节点自身label和其邻域label构成一个可数多重集。再以此基础上配合相应理论。

这里通过MLP模拟phi函数，epsilon是当前节点c的label权重超参数

然后就是readout

这篇文章的主要创新点在于

1. 结合多重集理论证明了在aggregation和readout单射情况判别能力能逼近WL-test.
2. 并基于上述论证，证明了sum aggregator是单射的.
3. 在readout步骤，通过线性运算获得终值而非mlp进一步保证单射性质.

代码待续...