【GNN】task6-基于图神经网络的图表征学习方法
学习心得
-
这次学习了基于图同构网络（GIN）的图表征网络。为了得到图表征首先需要做节点表征，然后做图读出。GIN中节点表征的计算遵循WL Test算法中节点标签的更新方法，因此它的上界是WL Test算法。
在图读出中，我们对所有的节点表征（加权，如果用Attention的话）求和，这会造成节点分布信息的丢失。 -
为了研究图神经网络的表达力问题，产生一个重要模型——图同构模型，
Weisfeiler-Lehman测试就是检测两个图是否在拓扑结构上图同构的近似方法；该测试最大的特点是：对每个节点的子树的聚合函数采用的是单射（Injective）的散列函数。
——由该特点我们可以通过设计一个单射聚合聚合函数来设计与WL一样强大的图卷积网络（同时，图同构网络有强大的图区分能力，适合图分类任务）。 -
具体还要读相关论文，关注阿里算法大佬的知乎专栏（tql）：https://zhuanlan.zhihu.com/p/90645716
文章目录
引言
在此篇文章中我们将学习基于图神经网络的图表征学习方法，图表征学习要求根据节点属性、边和边的属性（如果有的话）生成一个向量作为图的表征，基于图表征我们可以做图的预测。基于图同构网络（Graph Isomorphism Network, GIN）的图表征网络是当前最经典的图表征学习网络，我们将以它为例，通过该网络的实现、项目实践和理论分析，三个层面来学习基于图神经网络的图表征学习方法。
提出图同构网络的论文：How Powerful are Graph Neural Networks?
一、基于图同构网络（GIN）的图表征网络的实现
基于图同构网络的图表征学习主要包含以下两个过程：
- 首先计算得到节点表征；
- 其次对图上各个节点的表征做图池化（Graph Pooling），或称为图读出（Graph Readout），得到图的表征（Graph Representation）。
自顶向下的学习顺序：GIN图表征—>节点表征
1.基于图同构网络的图表征模块（GINGraphRepr Module）
GIN图同构网络模型的构建
- 能实现判断图同构性的图神经网络需要满足，只在两个节点自身标签一样且它们的邻接节点一样时，图神经网络将这两个节点映射到相同的表征，即映射是单射性的。
- 可重复集合/多重集（Multisets）：元素可重复的集合，元素在集合中没有顺序关系 。一个节点的所有邻接节点是一个可重复集合，一个节点可以有重复的邻接节点，邻接节点没有顺序关系。因此GIN模型中生成节点表征的方法遵循WL Test算法更新节点标签的过程。
在生成节点的表征后仍需要执行图池化（或称为图读出）操作得到图表征，最简单的图读出操作是做求和。由于每一层的节点表征都可能是重要的，因此在图同构网络中，不同层的节点表征在求和后被拼接，其数学定义如下，
h G = CONCAT ( READOUT ( { h v ( k ) ∣ v ∈ G } ) ∣ k = 0 , 1 , ⋯ , K ) h_{G} = \text{CONCAT}(\text{READOUT}\left(\{h_{v}^{(k)}|v\in G\}\right)|k=0,1,\cdots, K) hG=CONCAT(READOUT({hv(k)∣v∈G})∣k=0,1,⋯,K)
采用拼接而不是相加的原因在于不同层节点的表征属于不同的特征空间。未做严格的证明，这样得到的图的表示与WL Subtree Kernel得到的图的表征是等价的。
图表征模块运行流程
（1）首先采用GINNodeEmbedding模块对图上每一个节点做节点嵌入（Node Embedding），得到节点表征；
（2）然后对节点表征做图池化得到图的表征；
（3）最后用一层线性变换对图表征转换为对图的预测。
代码实现如下：
import torch
from torch import nn
from torch_geometric.nn import global_add_pool, global_mean_pool, global_max_pool, GlobalAttention, Set2Set
from gin_node import GINNodeEmbedding
class GINGraphRepr(nn.Module):
def __init__(self, num_tasks=1, num_layers=5, emb_dim=300, residual=False, drop_ratio=0, JK="last", graph_pooling="sum"):
"""GIN Graph Pooling Module
Args:
num_tasks (int, optional): number of labels to be predicted. Defaults to 1 (控制了图表征的维度，dimension of graph representation).
num_tasks为图表征维度，默认1
num_layers (int, optional): GINConv层数，默认5
emb_dim (int, optional): dimension of node embedding. Defaults to 300.
emb_dim为节点表征的维度，默认为300
residual (bool, optional): adding residual connection or not. Defaults to False.
drop_ratio (float, optional): dropout rate. Defaults to 0.
JK (str, optional): 可选的值为"last"和"sum"。选"last"，只取最后一层的结点的嵌入，选"sum"对各层的结点的嵌入求和。Defaults to "last".
graph_pooling (str, optional): pooling method of node embedding. 可选的值为"sum"，"mean"，"max"，"attention"和"set2set"。 Defaults to "sum".
graph_pooling为图节点表征的池化方法
Out:
graph representation
"""
super(GINGraphPooling, self).__init__()
self.num_layers = num_layers
self.drop_ratio = drop_ratio
self.JK = JK
self.emb_dim = emb_dim
self.num_tasks = num_tasks
if self.num_layers < 2:
raise ValueError("Number of GNN layers must be greater than 1.")
# 用GINNodeEmbedding模块对图上每一个节点做节点嵌入，得到节点表征
self.gnn_node = GINNodeEmbedding(num_layers, emb_dim, JK=JK, drop_ratio=drop_ratio, residual=residual)
# 对节点表征做图池化得到图的表征
# Pooling function to generate whole-graph embeddings
if graph_pooling == "sum":
self.pool = global_add_pool
elif graph_pooling == "mean":
self.pool = global_mean_pool
elif graph_pooling == "max":
self.pool = global_max_pool
elif graph_pooling == "attention":
self.pool = GlobalAttention(gate_nn=nn.Sequential(
nn.Linear(emb_dim, emb_dim), nn.BatchNorm1d(emb_dim), nn.ReLU(), nn.Linear(emb_dim, 1)))
elif graph_pooling == "set2set":
self.pool = Set2Set(emb_dim, processing_steps=2)
else:
raise ValueError("Invalid graph pooling type.")
if graph_pooling == "set2set":
self.graph_pred_linear = nn.Linear(2*self.emb_dim, self.num_tasks)
else:
self.graph_pred_linear = nn.Linear(self.emb_dim, self.num_tasks)
def forward(self, batched_data):
h_node = self.gnn_node(batched_data)
h_graph = self.pool(h_node, batched_data.batch)
output = self.graph_pred_linear(h_graph)
if self.training:
return output
else:
# At inference time, relu is applied to output to ensure positivity
# 因为预测目标的取值范围就在 (0, 50] 内
return torch.clamp(output, min=0, max=50)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
可以看到可选的基于结点表征计算得到图表征的方法有：
- “sum”：
- 对节点表征求和；
- 使用模块
torch_geometric.nn.glob.global_add_pool。
- “mean”：
- 对节点表征求平均；
- 使用模块
torch_geometric.nn.glob.global_mean_pool。
- “max”：取节点表征的最大值。
- 对一个batch中所有节点计算节点表征各个维度的最大值；
- 使用模块
torch_geometric.nn.glob.global_max_pool。
- “attention”：
- 基于Attention对节点表征加权求和；
- 使用模块 torch_geometric.nn.glob.GlobalAttention；
- 来自论文 “Gated Graph Sequence Neural Networks” 。
- “set2set”:
- 另一种基于Attention对节点表征加权求和的方法；
- 使用模块 torch_geometric.nn.glob.Set2Set；
- 来自论文 “Order Matters: Sequence to sequence for sets”。
PyG中集成的所有的图池化的方法可见于Global Pooling Layers。
2.基于图同构网络的节点嵌入模块（GINNodeEmbedding Module）
此节点嵌入模块基于多层GINConv实现结点嵌入的计算。此处我们先忽略GINConv的实现。输入到此节点嵌入模块的节点属性为类别型向量，
（1）我们首先用AtomEncoder对其做嵌入得到第0层节点表征（稍后我们再对AtomEncoder做分析）。
（2）然后我们逐层计算节点表征，从第1层开始到第num_layers层，每一层节点表征的计算都以上一层的节点表征h_list[layer]、边edge_index和边的属性edge_attr为输入。
（3）需要注意的是，GINConv的层数越多，此节点嵌入模块的感受野（receptive field）越大，结点i的表征最远能捕获到结点i的距离为num_layers的邻接节点的信息。
import torch
from mol_encoder import AtomEncoder
from gin_conv import GINConv
import torch.nn.functional as F
# GNN to generate node embedding
class GINNodeEmbedding(torch.nn.Module):
"""
Output:
node representations
"""
def __init__(self, num_layers, emb_dim, drop_ratio=0.5, JK="last", residual=False):
"""GIN Node Embedding Module"""
super(GINNodeEmbedding, self).__init__()
self.num_layers = num_layers
self.drop_ratio = drop_ratio
self.JK = JK
# add residual connection or not
self.residual = residual
if self.num_layers < 2:
raise ValueError("Number of GNN layers must be greater than 1.")
self.atom_encoder = AtomEncoder(emb_dim)
# List of GNNs
self.convs = torch.nn.ModuleList()
self.batch_norms = torch.nn.ModuleList()
for layer in range(num_layers):
self.convs.append(GINConv(emb_dim))
self.batch_norms.append(torch.nn.BatchNorm1d(emb_dim))
def forward(self, batched_data):
x, edge_index, edge_attr = batched_data.x, batched_data.edge_index, batched_data.edge_attr
# computing input node embedding
h_list = [self.atom_encoder(x)] # 先将类别型原子属性转化为原子表征
for layer in range(self.num_layers):
h = self.convs[layer](h_list[layer], edge_index, edge_attr)
h = self.batch_norms[layer](h)
if layer == self.num_layers - 1:
# remove relu for the last layer
h = F.dropout(h, self.drop_ratio, training=self.training)
else:
h = F.dropout(F.relu(h), self.drop_ratio, training=self.training)
if self.residual:
h += h_list[layer]
h_list.append(h)
# Different implementations of Jk-concat
if self.JK == "last":
node_representation = h_list[-1]
elif self.JK == "sum":
node_representation = 0
for layer in range(self.num_layers + 1):
node_representation += h_list[layer]
return node_representation
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
接下来我们来学习图同构网络的关键组件GINConv。
3.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⎠⎞
PyG中已经实现了此模块，我们可以通过torch_geometric.nn.GINConv来使用PyG定义好的图同构卷积层，然而该实现不支持存在边属性的图。在这里我们自己自定义一个支持边属性的GINConv模块。
由于输入的边属性为类别型，因此我们需要先将类别型边属性转换为边表征。我们定义的GINConv模块遵循“消息传递、消息聚合、消息更新”这一过程。
- 这一过程随着
self.propagate()方法的调用开始执行，该函数接收edge_index,x,edge_attr此三个参数。edge_index是形状为[2,num_edges]的张量（tensor）。
def forward(self, x, edge_index, edge_attr):
# 先将类别型边属性转换为边表征
edge_embedding = self.bond_encoder(edge_attr)
out = self.mlp((1 + self.eps) *x + self.propagate(edge_index, x=x, edge_attr=edge_embedding))
return out
- 1
- 2
- 3
- 4
- 5
- 在消息传递过程中，此张量首先被按行拆分为
x_i和x_j张量，x_j表示了消息传递的源节点，x_i表示了消息传递的目标节点。 - 接着
message()方法被调用，此函数定义了从源节点传入到目标节点的消息，在这里要传递的消息是源节点表征与边表征之和的relu()的输出。我们在super(GINConv, self).__init__(aggr = "add")中定义了消息聚合方式为add，那么传入给任一个目标节点的所有消息被求和得到aggr_out，它还是目标节点的中间过程的信息。
def message(self, x_j, edge_attr):
return F.relu(x_j + edge_attr)
- 1
- 2
- 接着执行消息更新过程，我们的类
GINConv继承了MessagePassing类，因此update()函数被调用。然而我们希望对节点做消息更新中加入目标节点自身的消息，因此在update函数中我们只简单返回输入的aggr_out。
def update(self, aggr_out):
return aggr_out
- 1
- 2
- 然后在
forward函数中我们执行out = self.mlp((1 + self.eps) *x + self.propagate(edge_index, x=x, edge_attr=edge_embedding))实现消息的更新。
def forward(self, x, edge_index, edge_attr):
# 先将类别型边属性转换为边表征
edge_embedding = self.bond_encoder(edge_attr)
out = self.mlp((1 + self.eps) *x + self.propagate(edge_index, x=x, edge_attr=edge_embedding))
return out
- 1
- 2
- 3
- 4
- 5
流程图如下（如有错误，请多多指正~）
上面的完整代码：
import torch
from torch import nn
from torch_geometric.nn import MessagePassing
import torch.nn.functional as F
from ogb.graphproppred.mol_encoder import BondEncoder
### GIN convolution along the graph structure
class GINConv(MessagePassing):
def __init__(self, emb_dim):
'''
emb_dim (int): node embedding dimensionality
'''
super(GINConv, self).__init__(aggr = "add")
self.mlp = nn.Sequential(nn.Linear(emb_dim, emb_dim), nn.BatchNorm1d(emb_dim), nn.ReLU(), nn.Linear(emb_dim, emb_dim))
self.eps = nn.Parameter(torch.Tensor([0]))
self.bond_encoder = BondEncoder(emb_dim = emb_dim)
def forward(self, x, edge_index, edge_attr):
# 先将类别型边属性转换为边表征
edge_embedding = self.bond_encoder(edge_attr)
out = self.mlp((1 + self.eps) *x + self.propagate(edge_index, x=x, edge_attr=edge_embedding))
return out
def message(self, x_j, edge_attr):
return F.relu(x_j + edge_attr)
def update(self, aggr_out):
return aggr_out
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
4.AtomEncoder 与 BondEncoder
由于在当前的例子中，节点（原子）和边（化学键）的属性都为离散值，它们属于不同的空间，无法直接将它们融合在一起。通过嵌入（Embedding），我们可以将节点属性和边属性分别映射到一个新的空间，在这个新的空间中，我们就可以对节点和边进行信息融合。在GINConv中，message()函数中的x_j + edge_attr 操作执行了节点信息和边信息的融合。
接下来，我们通过下方的代码中的AtomEncoder类，来分析将节点属性映射到一个新的空间是如何实现的：
full_atom_feature_dims是一个链表list，存储了节点属性向量每一维可能取值的数量，即X[i]可能的取值一共有full_atom_feature_dims[i]种情况，X为节点属性；- 节点属性有多少维，那么就需要有多少个嵌入函数，通过调用
torch.nn.Embedding(dim, emb_dim)可以实例化一个嵌入函数； torch.nn.Embedding(dim, emb_dim)，第一个参数dim为被嵌入数据可能取值的数量，第一个参数emb_dim为要映射到的空间的维度。得到的嵌入函数接受一个大于0小于dim的数，输出一个维度为emb_dim的向量。嵌入函数也包含可训练参数，通过对神经网络的训练，嵌入函数的输出值能够表达不同输入值之间的相似性。- 在
forward()函数中，我们对不同属性值得到的不同嵌入向量进行了相加操作，实现了将节点的的不同属性融合在一起。
BondEncoder类与AtomEncoder类是类似的。
OGB简介：
Open Graph Benchmark (OGB) 是斯坦福大学的一个图深度学习的基准数据集。可以直接通过pip install ogb下载；在OGB数据集上，带虚拟节点的模型相对于原来的模型基本上都得到了不小的提升。
import torch
from ogb.utils.features import get_atom_feature_dims, get_bond_feature_dims
full_atom_feature_dims = get_atom_feature_dims()
full_bond_feature_dims = get_bond_feature_dims()
class AtomEncoder(torch.nn.Module):
def __init__(self, emb_dim):
super(AtomEncoder, self).__init__()
self.atom_embedding_list = torch.nn.ModuleList()
for i, dim in enumerate(full_atom_feature_dims):
emb = torch.nn.Embedding(dim, emb_dim)
torch.nn.init.xavier_uniform_(emb.weight.data)
self.atom_embedding_list.append(emb)
def forward(self, x):
x_embedding = 0在·
for i in range(x.shape[1]):
x_embedding += self.atom_embedding_list[i](x[:,i])
return x_embedding
class BondEncoder(torch.nn.Module):
def __init__(self, emb_dim):
super(BondEncoder, self).__init__()
self.bond_embedding_list = torch.nn.ModuleList()
for i, dim in enumerate(full_bond_feature_dims):
emb = torch.nn.Embedding(dim, emb_dim)
torch.nn.init.xavier_uniform_(emb.weight.data)
self.bond_embedding_list.append(emb)
def forward(self, edge_attr):
bond_embedding = 0
for i in range(edge_attr.shape[1]):
bond_embedding += self.bond_embedding_list[i](edge_attr[:,i])
return bond_embedding
if __name__ == '__main__':
# from loader import GraphClassificationPygDataset
# dataset = GraphClassificationPygDataset(name = 'tox21')
from ogb.graphproppred.dataset_pyg import PygGraphPropPredDataset
dataset = PygGraphPropPredDataset(name = 'ogbg-molhiv')
atom_enc = AtomEncoder(100)
bond_enc = BondEncoder(100)
print(atom_enc(dataset[0].x))
print(bond_enc(dataset[0].edge_attr))
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
上面的tox21数据集（药物分子的一个数据集https://tripod.nih.gov/tox21/challenge/data.jsp#）导入的loader好像有点问题，换用了ogbg-molhiv数据集并且用PygGraphPropPredDataset导入后代码运行结果如下，可以得到节点属性映射到一个新的空间后的节点属性。
Downloading http://snap.stanford.edu/ogb/data/graphproppred/csv_mol_download/hiv.zip
Downloaded 0.00 GB: 100%|████████████████████████████████████████████████████████████████| 3/3 [00:03<00:00, 1.01s/it]
Extracting dataset\hiv.zip
Processing...
Loading necessary files...
This might take a while.
25%|██████████████████▏ | 10223/41127 [00:00<00:00, 55068.97it/s]
Processing graphs...
100%|█████████████████████████████████████████████████████████████████████████| 41127/41127 [00:00<00:00, 65315.60it/s]
20%|██████████████▉ | 8282/41127 [00:00<00:00, 82582.23it/s]
Converting graphs into PyG objects...
100%|█████████████████████████████████████████████████████████████████████████| 41127/41127 [00:00<00:00, 46464.62it/s]
Saving...
Done!
tensor([[ 6.5439e-01, -8.1690e-01, 1.4390e-01, ..., -5.1183e-01,
7.9147e-01, -5.8364e-02],
[ 6.1138e-01, -7.0429e-01, -4.4907e-02, ..., -4.3347e-01,
7.7738e-01, -3.7608e-01],
[ 1.6390e-01, -2.4293e-01, 2.1663e-01, ..., -7.5048e-04,
6.4839e-01, 3.3260e-01],
...,
[ 6.1138e-01, -7.0429e-01, -4.4907e-02, ..., -4.3347e-01,
7.7738e-01, -3.7608e-01],
[ 6.5439e-01, -8.1690e-01, 1.4390e-01, ..., -5.1183e-01,
7.9147e-01, -5.8364e-02],
[ 8.3114e-01, -3.9946e-01, 1.2739e-01, ..., -3.1377e-01,
5.1153e-01, 5.1009e-01]], grad_fn=<AddBackward0>)
tensor([[-0.2277, 0.0363, 0.2976, ..., -0.1147, -0.0277, -0.2164],
[-0.2277, 0.0363, 0.2976, ..., -0.1147, -0.0277, -0.2164],
[-0.2277, 0.0363, 0.2976, ..., -0.1147, -0.0277, -0.2164],
...,
[-0.2277, 0.0363, 0.2976, ..., -0.1147, -0.0277, -0.2164],
[-0.2277, 0.0363, 0.2976, ..., -0.1147, -0.0277, -0.2164],
[-0.2277, 0.0363, 0.2976, ..., -0.1147, -0.0277, -0.2164]],
grad_fn=<AddBackward0>)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
二、How Powerful are Graph Neural Networks?
提出图同构网络的论文：How Powerful are Graph Neural Networks?
1.Motivation
新的图神经网络的设计大多基于经验性的直觉、启发式的方法和实验性的试错。人们对图神经网络的特性和局限性了解甚少，对图神经网络的表征能力学习的正式分析也很有限。
2.文章内容
- （理论上）图神经网络在区分图结构方面最高能达到与WL Test一样的能力。
- 确定了邻接节点聚合方法和图池化方法应具备的条件，在这些条件下，所产生的图神经网络能达到与WL Test一样的能力。
- 分析过去流行的图神经网络变体（如GCN和GraphSAGE）无法区分一些结构的图。
- 开发了一个简单的图神经网络模型–图同构网络（Graph Isomorphism Network, GIN），并证明其分辨同构图的能力和表示图的能力与WL Test相当。
3.背景：Weisfeiler-Lehman Test (WL Test)
（1）图同构性测试算法WL Test
背景介绍
两个图是同构的，意思是两个图拥有一样的拓扑结构，也就是说，我们可以通过重新标记节点从一个图转换到另外一个图。Weisfeiler-Lehman 图的同构性测试算法，简称WL Test，是一种用于测试两个图是否同构的算法。
WL Test 的一维形式，类似于图神经网络中的邻接节点聚合。WL Test
1）迭代地聚合节点及其邻接节点的标签，然后 2）将聚合的标签散列（hash）成新标签，该过程形式化为下方的公式，
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⎠⎞
符号： L u h L^{h}_{u} Luh表示节点 u u u的第 h h h次迭代的标签，第 0 0 0次迭代的标签为节点原始标签。
在迭代过程中，发现两个图之间的节点的标签不同时，就可以确定这两个图是非同构的。需要注意的是节点标签可能的取值只能是有限个数。
WL举例说明（以一维为栗子）
给定两个图 G G G和 G ′ G^{\prime} G′，每个节点拥有标签（实际中，一些图没有节点标签，我们可以以节点的度作为标签）。
Weisfeiler-Leman Test 算法通过重复执行以下给节点打标签的过程来实现图是否同构的判断：
第一步：聚合
聚合自身与邻接节点的标签得到一串字符串，自身标签与邻接节点的标签中间用,分隔，邻接节点的标签按升序排序。排序的原因在于要保证单射性，即保证输出的结果不因邻接节点的顺序改变而改变。
如下图就是，每个节点有个一个label（此处表示节点的度）。
如下图，做标签的扩展：做一阶BFS，即只遍历自己的邻居，比如在下图中G中原5号节点变成（5,234），这是因为原（5）节点的一阶邻居有2、3、4。
第二步：标签散列（哈希）
即标签压缩，将较长的字符串映射到一个简短的标签。
如下图，仅仅是把扩展标签映射成一个新标签，如5,234映射为13
注：怎样的聚合函数是一个单射函数？
什么是单射函数？
单射指不同的输入值一定会对应到不同的函数值。如果对于每一个y存在最多一个定义域内的x，有f(x)=y，则函数f被称为单射函数。
看一个栗子：
两个节点v1和v2，其中v1的邻接点是1个黄球和1个蓝球，v2的邻接点是2个邻接点是2个黄球和2个蓝球。最常用的聚合函数包含图卷积网络中所使用的均值聚合，以及GraphSAGE中常用的均值聚合或最大值聚合。
（1）如果使用均值聚合或者最大值聚合，聚合后v1的状态是（黄，蓝），而v2的状态也是（黄，蓝），显然它们把本应不同的2个节点映射到了同一个状态，这不满足单射的定义。
（2）如果使用求和函数，v1的状态是（黄，蓝），而v2的状态是（2×黄，2×蓝），也就分开了。
可以看出WL测试最大的特点是：对每个节点的子树的聚合函数采用的是单射（Injective）的散列函数。
第三步：给节点重新打上标签。
继续一开始的栗子，
第四步：数标签
如下图，在G网络中，含有1号标签2个，那么第一个数字就是1。这些标签的个数作为整个网络的新特征。
每重复一次以上的过程，就完成一次节点自身标签与邻接节点标签的聚合。
第五步：判断同构性
当出现两个图相同节点标签的出现次数不一致时，即可判断两个图不相似。如果上述的步骤重复一定的次数后，没有发现有相同节点标签的出现次数不一致的情况，那么我们无法判断两个图是否同构。
当两个节点的 h h h层的标签一样时，表示分别以这两个节点为根节点的WL子树是一致的。WL子树与普通子树不同，WL子树包含重复的节点。下图展示了一棵以1节点为根节点高为2的WL子树。
（2）WL Subtree Kernel图相似性评估（定量化）
此方法来自于Weisfeiler-Lehman Graph Kernels。
- WL测试不能保证对所有图都有效，特别是对于具有高度对称性的图，如链式图、完全图、环图和星图，它会判断错误。
- WL测试只能判断两个图的相似性，无法衡量图之间的相似性。要衡量两个图的相似性，我们用WL Subtree Kernel方法。
Weisfeiler-Lehman Graph Kernels 方法提出用WL子树核衡量图之间相似性。该方法使用WL Test不同迭代中的节点标签计数作为图的表征向量，它具有与WL Test相同的判别能力。在WL Test的第 k k k次迭代中，一个节点的标签代表了以该节点为根的高度为 k k k的子树结构。
该方法的思想是用WL Test算法得到节点的多层的标签，然后我们可以分别统计图中各类标签出现的次数，存于一个向量，这个向量可以作为图的表征。两个图的表征向量的内积，即可作为这两个图的相似性估计，内积越大表示相似性越高。
4.小结
大部分空域图神经网络的更新步骤，和WL测试非常类似。就像消息传递网络中归纳的框架，大部分基于空域的图神经网络都可以归结为2个步骤：聚合邻接点信息（aggregate），更新节点信息（combine）。 a v k = Aggregate ( { h u k − 1 : u ∈ N ( v ) } ) , h v k = Combine ( h v k − 1 , a v k ) a_{v}^{k}=\operatorname{Aggregate}\left(\left\{\boldsymbol{h}_{u}^{k-1}: u \in \mathcal{N}(v)\right\}\right), \boldsymbol{h}_{v}^{k}=\operatorname{Combine}\left(\boldsymbol{h}_{v}^{k-1}, \boldsymbol{a}_{v}^{k}\right) avk=Aggregate({huk−1:u∈N(v)}),hvk=Combine(hvk−1,avk)
与WL测试一样，在表达网络结果时，一个节点的表征会由该结点的父结点的子树信息聚合而成。
正如上面提到的栗子中（下图），均值聚合或者最大值聚合把栗子中的v1和v2两个节点映射到了同一个状态（错误），而如果使用求和函数则能正确分开两者状态。WL测试最大的特点是：对每个节点的子树的聚合函数采用的是单射（Injective）的散列函数。
——由该特点我们可以通过设计一个单射聚合聚合函数来设计与WL一样强大的图卷积网络（同时，图同构网络有强大的图区分能力，适合图分类任务）。
三、作业
请画出下方图片中的6号、3号和5号节点为根结点的从1层到3层的WL（ W e i s f e i l e r − L e m a n Weisfeiler-Leman Weisfeiler−Leman）子树（即高为3）。
四、论文相关
（1）《How Powerful are Graph Neural Networks？》 ICLR 2019
这篇主要基于Weisfeiler-Lehman(WL) test 视角理论分析了GNN，证明WL是GNN上限，并分析GCN和GraphSAGE等主流GNN在捕获图结构上的不足和特性。
（2）《Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks》AAAI-2019
文章在介绍相关方法时主要分成了两部分，包括后面的对比试验也是，文章将图领域内的方法分为两种：
（1）基于核的方法，例如基于随机游走或者最短距离内核的等等算法，其中，WL算法是属于基于核方法的一种方法。
（2）GNN系列的方法，比如Gated Graph Neural Networks，GraphSAGE， SplineCNN等等。
（3）《Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks》AAAI-2019
1.证实了GNN在非同构图区分上并不比WL算法强，并且在某种特定情况下，GNN与WL算法具有同等效力，所以也具有相同的问题
2.从K-WL算法受到启发提出了K-GNN模型，从粗细粒度方面能够更好的提取信息
3.实验证实了文章提出的higher-order GNN对于图分类和图回归都十分重要
REFERENCE
- 提出GlobalAttention的论文： “Gated Graph Sequence Neural Networks”
- 提出Set2Set的论文：“Order Matters: Sequence to sequence for sets”
- PyG中集成的所有的图池化的方法：Global Pooling Layers
- Weisfeiler-Lehman Test: Brendan L Douglas. The weisfeiler-lehman method and graph isomorphism testing. arXiv preprint arXiv:1101.5211, 2011.
- datawhale course：https://github.com/datawhalechina
- Weisfeiler-Lehman Graph Kernels
- ogb包的源码：https://github.com/snap-stanford/ogb
- cs224w（图机器学习）2021冬季课程学习笔记8 Colab 2
- 马腾飞《图神经网络-基础与前沿》
- How Powerful are Graph Neural Networks？论文解读
- https://blog.csdn.net/deep_revealer/article/details/110817023
文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。
原文链接：andyguo.blog.csdn.net/article/details/118403917
- 点赞
- 收藏
- 关注作者
评论（0）