基于图神经网络的图表征学习方法
以图同构网络(Graph Isomorphism Network, GIN)为例学习基于图神经网络的图表征学习。图表征学习要求根据节点属性、边和边的属性（如果有的话）生成一个向量作为图的表征，基于图表征我们可以做图的预测。
基于图同构网络（GIN）的图表征网络的实现
- 计算得到节点表征；
- 对图上各个节点的表征做图池化（Graph Pooling），或称为图读出（Graph Readout），得到图的表征（Graph Representation）。
基于图同构网络的图表征模块（GINGraphRepr Module）
- 首先采用GINNodeEmbedding模块对图上每一个节点做节点嵌入（Node Embedding），得到节点表征；
- 然后对节点表征做图池化得到图的表征；
- 最后用一层线性变换对图表征转换为对图的预测。
可选的基于结点表征计算得到图表征的方法有：sum;mean;max;attention(基于Attention对节点表征加权求和);set2set(另一种基于Attention对节点表征加权求和的方法)
基于图同构网络的节点嵌入模块（GINNodeEmbedding Module）
- 首先用AtomEncoder对其做嵌入得到第0层节点表征。
- 然后我们逐层计算节点表征，从第1层开始到第num_layers层，每一层节点表征的计算都以上一层的节点表征h_list[layer]、边edge_index和边的属性edge_attr为输入。
GINConv–图同构卷积层
图同构卷积层的数学定义如下：
x
i
′
=
h
Θ
(
(
1
+
ϵ
)
⋅
x
i
+
∑
j
∈
N
(
i
)
x
j
)
\mathbf{x}^{\prime}_i = h_{\mathbf{\Theta}} \left( (1 + \epsilon) \cdot \mathbf{x}_i + \sum_{j \in \mathcal{N}(i)} \mathbf{x}_j \right)
xi′=hΘ⎝⎛(1+ϵ)⋅xi+j∈N(i)∑xj⎠⎞
文章的贡献及WL Test
- （理论上）图神经网络在区分图结构方面最高能达到与WL Test一样的能力。
- 确定了邻接节点聚合方法和图池化方法应具备的条件，在这些条件下，所产生的图神经网络能达到与WL Test一样的能力。
- 分析过去流行的图神经网络变体（如GCN和GraphSAGE）无法区分一些结构的图。
- 开发了一个简单的图神经网络模型–图同构网络（Graph Isomorphism Network, GIN），并证明其分辨同构图的能力和表示图的能力与WL Test相当。
Weisfeiler-Lehman Test (WL Test)
图同构测试：两个图是同构的，意思是两个图拥有一样的拓扑结构，也就是说，我们可以通过重新标记节点从一个图转换到另外一个图。Weisfeiler-Lehman 图的同构性测试算法，简称WL Test，是一种用于测试两个图是否同构的算法。
一维形式：
L
u
h
←
hash
(
L
u
h
−
1
+
∑
v
∈
N
(
U
)
L
v
h
−
1
)
L^{h}_{u} \leftarrow \operatorname{hash}\left(L^{h-1}_{u} + \sum_{v \in \mathcal{N}(U)} L^{h-1}_{v}\right)
Luh←hash⎝⎛Luh−1+v∈N(U)∑Lvh−1⎠⎞
- Weisfeiler-Leman Test 算法通过重复执行以下给节点打标签的过程来实现图是否同构的判断：
- 聚合自身与邻接节点的标签得到一串字符串，自身标签与邻接节点的标签中间用
,分隔，邻接节点的标签按升序排序。排序的原因在于要保证单射性，即保证输出的结果不因邻接节点的顺序改变而改变。 - 标签散列，即标签压缩，将较长的字符串映射到一个简短的标签。
- 给节点重新打上标签。
- 聚合自身与邻接节点的标签得到一串字符串，自身标签与邻接节点的标签中间用
作业
6,4,（3,5,6）
3,（2,4）,（1,3,5;3,5,6）
5,(1,2,4),(2,5;1,3,5;3,5,6)
参考资料：
https://github.com/datawhalechina/team-learning-nlp/tree