GNN系列（二）：消息传递图神经网络

消息传递范式是一种聚合邻接节点信息来更新中心节点信息的范式，它将卷积算子推广到了不规则数据领域，实现了图与神经网络的连接。此范式包含三个步骤：(1)邻接节点信息变换、(2)邻接节点信息聚合到中心节点、(3)聚合信息变换。
下方图片展示了基于消息传递范式的生成节点表征的过程：

1. 在图的最右侧，B节点的邻接节点（A,C）的信息传递给了B，经过信息变换得到了B的嵌入，C、D节点同。
2. 在图的中右侧，A节点的邻接节点（B,C,D）的之前得到的节点嵌入传递给了节点A；在图的中左侧，聚合得到的信息经过信息变换得到了A节点新的嵌入。
3. 重复多次，我们可以得到每一个节点的经过多次信息变换的嵌入。这样的经过多次信息聚合与变换的节点嵌入就可以作为节点的表征，可以用于节点的分类。
   

Pytorch Geometric中的MessagePassing基类

Pytorch Geometric(PyG)提供了MessagePassing基类，它实现了消息传播的自动处理，继承该基类可使我们方便地构造消息传递图神经网络，我们只需定义函数$\varphi$，即message()函数，和函数$\gamma$，即update()函数，以及使用的消息聚合方案，即aggr="add"、aggr="mean"或aggr="max"。这些是在以下方法的帮助下完成的：

• MessagePassing(aggr="add", flow="source_to_target", node_dim=-2)：
  • aggr：定义要使用的聚合方案（“add”、"mean "或 “max”）；
  • flow：定义消息传递的流向（"source_to_target "或 “target_to_source”）；
  • node_dim：定义沿着哪个轴线传播。
• MessagePassing.propagate(edge_index, size=None, **kwargs)：
  • 开始传播消息的起始调用。它以edge_index（边的端点的索引）和flow（消息的流向）以及一些额外的数据为参数。
  • 请注意，propagate()不仅限于在形状为[N, N]的对称邻接矩阵中交换消息，还可以通过传递size=(N, M)作为额外参数。例如，在二部图的形状为[N, M]的一般稀疏分配矩阵中交换消息。
  • 如果设置size=None，则假定邻接矩阵是对称的。
  • 对于有两个独立的节点集合和索引集合的二部图，并且每个集合都持有自己的信息，我们可以传递一个元组参数，即x=(x_N, x_M)，来标记信息的区分。
• MessagePassing.message(...)：
  • 首先确定要给节点$i$传递消息的边的集合，如果flow="source_to_target"，则是$(j,i)\in \mathcal{E}$的边的集合；
  • 如果flow="target_to_source"，则是$(i,j)\in \mathcal{E}$的边的集合。
  • 接着为各条边创建要传递给节点$i$的消息，即实现$\varphi$函数。
  • MessagePassing.message(...)函数接受最初传递给MessagePassing.propagate(edge_index, size=None, **kwargs)函数的所有参数。
  • 此外，传递给propagate()的张量可以被映射到各自的节点$i$和$j$上，只需在变量名后面加上_i或_j。我们把$i$称为消息传递的目标中心节点，把$j$称为邻接节点。
• MessagePassing.aggregate(...)：
  • 将从源节点传递过来的消息聚合在目标节点上，一般可选的聚合方式有sum, mean和max。
• MessagePassing.message_and_aggregate(...)：
  • 在一些场景里，邻接节点信息变换和邻接节点信息聚合这两项操作可以融合在一起，那么我们可以在此函数里定义这两项操作，从而让程序运行更加高效。
• MessagePassing.update(aggr_out, ...):
  • 为每个节点$i\in \mathcal{V}$更新节点表征，即实现$\gamma$函数。该函数以聚合函数的输出为第一个参数，并接收所有传递给propagate()函数的参数。

继承MessagePassing类的GCNConv

GCNConv的数学定义为
x i ( k ) = ∑ j ∈ N ( i ) ∪ { i } 1 deg ⁡ ( i ) ⋅ deg ⁡ ( j ) ⋅ ( Θ ⋅ x j ( k − 1 ) ) , \mathbf{x}_i^{(k)} = \sum_{j \in \mathcal{N}(i) \cup \{ i \}} \frac{1}{\sqrt{\deg(i)} \cdot \sqrt{\deg(j)}} \cdot \left( \mathbf{\Theta} \cdot \mathbf{x}_j^{(k-1)} \right), xi(k)​=j∈N(i)∪{i}∑​deg(i) ​⋅deg(j) ​1​⋅(Θ⋅xj(k−1)​),
其中，相邻节点的特征首先通过权重矩阵$\mathbf{\Theta }$进行转换，然后按端点的度进行归一化处理，最后进行加总。这个公式可以分为以下几个步骤：

1. 向邻接矩阵添加自环边。
2. 线性转换节点特征矩阵。
3. 计算归一化系数。
4. 归一化$j$中的节点特征。
5. 将相邻节点特征相加（"求和 "聚合）。

步骤1-3通常是在消息传递发生之前计算的。步骤4-5可以使用MessagePassing基类轻松处理。
 
 
 
消息传递范式是实现图神经网络的一种通用范式。消息传递范式遵循“消息传播->消息聚合->消息更新”这一过程，实现将邻接节点的信息聚合到中心节点上。在PyG中，MessagePassing是所有基于消息传递范式的图神经网络的基类。MessagePassing类大大方便了图神经网络的构建，但由于其高度封装性，它也隐藏了很多的细节。

作业

1. 请总结MessagePassing类的运行流程以及继承MessagePassing类的规范。
2. 请继承MessagePassing类来自定义以下的图神经网络类，并进行测试：
   1. 第一个类，覆写message函数，要求该函数接收消息传递源节点属性x、目标节点度d。
   2. 第二个类，在第一个类的基础上，再覆写aggregate函数，要求不能调用super类的aggregate函数，并且不能直接复制super类的aggregate函数内容。
   3. 第三个类，在第二个类的基础上，再覆写update函数，要求对节点信息做一层线性变换。
   4. 第四个类，在第三个类的基础上，再覆写message_and_aggregate函数，要求在这一个函数中实现前面message函数和aggregate函数的功能。