Datawhale提供的课程链接：https://github.com/datawhalechina/team-learning-nlp/blob/master/GNN

一、引言

图表征学习要求在输入节点属性、边和边的属性（如果有的话）得到一个向量作为图的表征，基于图表征我们可以做图的预测。基于图同构网络（Graph Isomorphism Network,GIN）的图表征网络是当前最经典的图表征学习网络。

二、基于图同构网络（GIN）的图表征网络的实现

2.1 基于图同构网络的图表征学习的过程

1.首先计算得到节点表征

2.其次对图上各个节点的表征做图池化（Graph Pooling），或称为图读出（Graph Readout），得到图的表征（Graph Representation）

2.2 基于图同构网络的图表征模块（GINGraphRepr Module）

此模块首先采用GINNodeEmbedding模块对图上每一个节点做节点嵌入（Node Embedding），得到节点表征；然后对节点表征做图池化得到图的表征；最后用一层线性变换对图表征转换为对图的预测。代码实现如下:

图1

图2.基于节点表征计算得到图表征的方法

2.3 基于图同构网络的节点嵌入模块（GINNodeEmbedding Module）

此节点嵌入模块基于多层GINConv实现结点嵌入的计算。此处我们先忽略GINConv的实现。输入到此节点嵌入模块的节点属性为类别型向量，我们首先用AtomEncoder对其做嵌入得到第0层节点表征（稍后我们再对AtomEncoder做分析）。然后我们逐层计算节点表征，从第1层开始到第num_layers层，每一层节点表征的计算都以上一层的节点表征h_list[layer]、边edge_index和边的属性edge_attr为输入。需要注意的是，GINConv的层数越多，此节点嵌入模块的感受野（receptive field）越大，结点i的表征最远能捕获到结点i的距离为num_layers的邻接节点的信息。

图3

2.3 GINConv--图同构卷积层

PyG可以通过torch_geometric.nn.GINConv来使用PyG定义好的图同构卷积层，该实现不支持存在边属性的图。在这里自定义一个支持边属性的GINConv模块。

输入的边属性为类别型，需先将类别型边属性转换为边表征。定义的GINConv模块遵循“消息传递、消息聚合、消息更新”这一过程。

1.这一过程随着self.propagate()方法的调用开始执行，该函数接收edge_index, x, edge_attr此三个参数。接着message()方法被调用，在这里要传递的消息是源节点表征与边表征之和的relu()的输出。

2.在super(GINConv, self).init(aggr = "add")中定义了消息聚合方式为add，那么传入给任一个目标节点的所有消息被求和得到aggr_out，它还是目标节点的中间过程的信息。

3.接着执行消息更新过程，类GINConv继承了MessagePassing类，因此update()函数被调用。

我们希望对节点做消息更新中加入目标节点自身的消息，因此在update函数中只简单返回输入的aggr_out。然后在forward函数中，执行out = self.mlp((1 + self.eps) *x + self.propagate(edge_index, x=x, edge_attr=edge_embedding))实现消息的更新。

代码实现如下：

图4

2.4 AtomEncoder 与 BondEncoder

由于节点和边的属性都为离散值，它们属于不同的空间，无法直接将它们融合在一起。通过嵌入（Embedding），可以将节点属性和边属性分别映射到一个新的空间，在这个新的空间中，就可以对节点和边进行信息融合。在GINConv中，message()函数中的x_j + edge_attr 操作执行了节点信息和边信息的融合。

节点属性映射到一个新的空间是如何实现的?

1.full_atom_feature_dims 是一个链表list，存储了节点属性向量每一维可能取值的数量，即X[i] 可能的取值一共有full_atom_feature_dims[i]种情况，X为节点属性；

2.节点属性有多少维，那么就需要有多少个嵌入函数，通过调用torch.nn.Embedding(dim, emb_dim)可以实例化一个嵌入函数；

3.torch.nn.Embedding(dim, emb_dim)，第一个参数dim为被嵌入数据可能取值的数量，第一个参数emb_dim为要映射到的空间的维度。得到的嵌入函数接受一个大于0小于dim的数，输出一个维度为emb_dim的向量。嵌入函数也包含可训练参数，通过对神经网络的训练，嵌入函数的输出值能够表达不同输入值之间的相似性。

4.在forward()函数中，我们对不同属性值得到的不同嵌入向量进行相加操作，实现了将节点的的不同属性融合在一起。

图5

三、理论分析

3.1 动机

新的图神经网络的设计大多基于经验性的直觉、启发式的方法和实验性的试错。人们对图神经网络的特性和局限性了解甚少，对图神经网络的表征能力学习的正式分析也很有限。

3.2 贡献与结论

1. （理论上）图神经网络在区分图结构方面最高能达到与WL Test一样的能力。

2. 确定了邻接节点聚合方法和图池化方法的应具备的条件，在这些条件下，所产生的图神经网络能达到与WL Test一样的能力。

3. 分析出过去流行的图神经网络变体（如GCN和GraphSAGE）无法区分一些结构的图。

4. 开发了一个简单的图神经网络模型--图同构网络（Graph Isomorphism Network,GIN），并证明其分辨图的同构性的能力与表示图的能力与WL Test相当。

3.3 Weisfeiler-Lehman Test (WL Test)

3.3.1 图同构性测试

两个图是同构的，意思是两个图拥有一样的拓扑结构，也就是说，我们可以通过重新标记节点从一个图转换到另外一个图。Weisfeiler-Lehman 图的同构性测试算法，简称WL Test，是一种用于测试两个图是否同构的算法。

WL Test 的一维形式，类似于图神经网络中的邻接节点聚合。WL Test 1）迭代地聚合节点及其邻接节点的标签，然后2）将聚合的标签散列（hash）成新标签，该过程形式化为下方的公示：

图6

在迭代过程中，发现两个图之间的节点的标签不同时，就可以确定这两个图是非同构的。需要注意的是节点标签可能的取值只能是有限个数。

WL测试不能保证对所有图都有效，特别是对于具有高度对称性的图，如链式图、完全图、环图和星图，它会判断错误。

Weisfeiler-Lehman Graph Kernels 方法提出用WL子树核衡量图之间相似性。该方法使用WL Test不同迭代中的节点标签计数作为图的表征向量，它具有与WL Test相同的判别能力。直观地说，在WL Test的第 次迭代中，一个节点的标签代表了以该节点为根的高度为 的子树结构。

Weisfeiler-Leman Test 算法举例说明：

图7

给定两个图，每个节点拥有标签（实际中，一些图没有节点标签，我们可以以节点的度作为标签）。

Weisfeiler-Leman Test 算法通过重复执行以下给节点打标签的过程来实现图是否同构的判断：

1. 聚合自身与邻接节点的标签得到一串字符串，自身标签与邻接节点的标签中间用,分隔，邻接节点的标签按升序排序。排序的原因在于要保证单射性，即保证输出的结果不因邻接节点的顺序改变而改变。

图8

2. 标签散列，即标签压缩，将较长的字符串映射到一个简短的标签。

图9

3. 给节点重新打上标签。

图10

每重复一次以上的过程，就完成一次节点自身标签与邻接节点标签的聚合。当出现两个图相同节点标签的出现次数不一致时，即可判断两个图不相似。如果上述的步骤重复一定的次数后，没有发现有相同节点标签的出现次数不一致的情况，那么我们无法判断两个图是否同构。

3.3.2 图相似性评估

WL Test 算法的一点局限性是，它只能判断两个图的相似性，无法衡量图之间的相似性。要衡量两个图的相似性，我们用WL Subtree Kernel方法。该方法的思想是用WL Test算法得到节点的多层的标签，然后我们可以分别统计图中各类标签出现的次数，存于一个向量，这个向量可以作为图的表征。两个图的这样的向量的内积，即可作为这两个图的相似性的估计，内积越大表示相似性越高。

图11

3.4 图同构网络模型的构建

能实现判断图同构性的图神经网络需要满足，只在两个节点自身标签一样且它们的邻接节点一样时，图神经网络将这两个节点映射到相同的表征，即映射是单射性的。可重复集合（Multisets）指的是元素可重复的集合，元素在集合中没有顺序关系。 一个节点的所有邻接节点是一个可重复集合，一个节点可以有重复的邻接节点，邻接节点没有顺序关系。因此GIN模型中生成节点表征的方法遵循WL Test算法更新节点标签的过程。

在生成节点的表征后仍需要执行图池化（或称为图读出）操作得到图表征，最简单的图读出操作是做求和。由于每一层的节点表征都可能是重要的，因此在图同构网络中，不同层的节点表征在求和后被拼接，其数学定义如下：

图12

采用拼接而不是相加的原因在于不同层节点的表征属于不同的特征空间。未做严格的证明，这样得到的图的表示与WL Subtree Kernel得到的图的表征是等价的。