有经验的永州网站建设,网站制作用什么,wordpress导入有道笔记,wordpress搜站点网络中断note
基于图同构网络#xff08;GIN#xff09;的图表征网络。为了得到图表征首先需要做节点表征#xff0c;然后做图读出。GIN中节点表征的计算遵循WL Test算法中节点标签的更新方法#xff0c;因此它的上界是WL Test算法。 在图读出中#xff0c;我们对所有的节点表征GIN的图表征网络。为了得到图表征首先需要做节点表征然后做图读出。GIN中节点表征的计算遵循WL Test算法中节点标签的更新方法因此它的上界是WL Test算法。 在图读出中我们对所有的节点表征加权如果用Attention的话求和这会造成节点分布信息的丢失。为了研究图神经网络的表达力问题产生一个重要模型——图同构模型Weisfeiler-Lehman测试就是检测两个图是否在拓扑结构上图同构的近似方法该测试最大的特点是对每个节点的子树的聚合函数采用的是单射Injective的散列函数。 ——由该特点我们可以通过设计一个单射聚合聚合函数来设计与WL一样强大的图卷积网络同时图同构网络有强大的图区分能力适合图分类任务。 文章目录note零、Recap部分一、GIN图同构网络1.1 WL Graph Kernel1.2 基于图同构网络GIN的图表征网络的实现1.基于图同构网络的图表征模块GINGraphRepr Module图表征模块运行流程2.基于图同构网络的节点嵌入模块GINNodeEmbedding Module3.GINConv--图同构卷积层4.AtomEncoder 与 BondEncoder1.3 The power of pooling1.4 dgl中的GIN层代码二、Expressive of Power GNNs1.Motivation2.文章内容3.背景Weisfeiler-Lehman Test (WL Test)1图同构性测试算法WL Test背景介绍WL举例说明以一维为栗子第一步聚合第二步标签散列哈希注怎样的聚合函数是一个单射函数第三步给节点重新打上标签。第四步数标签第五步判断同构性2WL Subtree Kernel图相似性评估定量化4.小结三、General Tips附时间安排Reference零、Recap部分
一、GIN图同构网络
1.1 WL Graph Kernel
对节点颜色进行更新 c(k1)(v)HASH(c(k)(v),{c(k)(u)}u∈N(v))c^{(k1)}(v)\operatorname{HASH}\left(c^{(k)}(v),\left\{c^{(k)}(u)\right\}_{u \in N(v)}\right) c(k1)(v)HASH(c(k)(v),{c(k)(u)}u∈N(v))
1.2 基于图同构网络GIN的图表征网络的实现
基于图同构网络的图表征学习主要包含以下两个过程
首先计算得到节点表征其次对图上各个节点的表征做图池化Graph Pooling或称为图读出Graph Readout得到图的表征Graph Representation。
自顶向下的学习顺序GIN图表征—节点表征
1.基于图同构网络的图表征模块GINGraphRepr Module
GIN图同构网络模型的构建
能实现判断图同构性的图神经网络需要满足只在两个节点自身标签一样且它们的邻接节点一样时图神经网络将这两个节点映射到相同的表征即映射是单射性的。可重复集合/多重集Multisets元素可重复的集合元素在集合中没有顺序关系 。一个节点的所有邻接节点是一个可重复集合一个节点可以有重复的邻接节点邻接节点没有顺序关系。因此GIN模型中生成节点表征的方法遵循WL Test算法更新节点标签的过程。
在生成节点的表征后仍需要执行图池化或称为图读出操作得到图表征最简单的图读出操作是做求和。由于每一层的节点表征都可能是重要的因此在图同构网络中不同层的节点表征在求和后被拼接其数学定义如下 hGCONCAT(READOUT({hv(k)∣v∈G})∣k0,1,⋯,K)h_{G} \text{CONCAT}(\text{READOUT}\left(\{h_{v}^{(k)}|v\in G\}\right)|k0,1,\cdots, K) hGCONCAT(READOUT({hv(k)∣v∈G})∣k0,1,⋯,K) 采用拼接而不是相加的原因在于不同层节点的表征属于不同的特征空间。未做严格的证明这样得到的图的表示与WL Subtree Kernel得到的图的表征是等价的。
图表征模块运行流程
1首先采用GINNodeEmbedding模块对图上每一个节点做节点嵌入Node Embedding得到节点表征 2然后对节点表征做图池化得到图的表征 3最后用一层线性变换对图表征转换为对图的预测。
2.基于图同构网络的节点嵌入模块GINNodeEmbedding Module
此节点嵌入模块基于多层GINConv实现结点嵌入的计算。此处我们先忽略GINConv的实现。输入到此节点嵌入模块的节点属性为类别型向量
3.GINConv–图同构卷积层
图同构卷积层的数学定义如下 xi′hΘ((1ϵ)⋅xi∑j∈N(i)xj)\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ϵ)⋅xij∈N(i)∑xj
由于输入的边属性为类别型因此我们需要先将类别型边属性转换为边表征。我们定义的GINConv模块遵循“消息传递、消息聚合、消息更新”这一过程。
4.AtomEncoder 与 BondEncoder
由于在当前的例子中节点原子和边化学键的属性都为离散值它们属于不同的空间无法直接将它们融合在一起。通过嵌入Embedding我们可以将节点属性和边属性分别映射到一个新的空间在这个新的空间中我们就可以对节点和边进行信息融合。
1.3 The power of pooling
use element-wise sum pooling, instead of mean-/max-pooling
1.4 dgl中的GIN层代码
dgl的GINConv层在这里插入代码片
Torch Module for Graph Isomorphism Network layer
# pylint: disable no-member, arguments-differ, invalid-name
import torch as th
from torch import nnfrom .... import function as fn
from ....utils import expand_as_pairclass GINConv(nn.Module):def __init__(self,apply_func,aggregator_type,init_eps0,learn_epsFalse):super(GINConv, self).__init__()self.apply_func apply_funcself._aggregator_type aggregator_typeif aggregator_type sum:self._reducer fn.sumelif aggregator_type max:self._reducer fn.maxelif aggregator_type mean:self._reducer fn.meanelse:raise KeyError(Aggregator type {} not recognized..format(aggregator_type))# to specify whether eps is trainable or not.if learn_eps:self.eps th.nn.Parameter(th.FloatTensor([init_eps]))else:self.register_buffer(eps, th.FloatTensor([init_eps]))def forward(self, graph, feat, edge_weightNone):rDescription-----------Compute Graph Isomorphism Network layer.Parameters----------graph : DGLGraphThe graph.feat : torch.Tensor or pair of torch.TensorIf a torch.Tensor is given, the input feature of shape :math:(N, D_{in}) where:math:D_{in} is size of input feature, :math:N is the number of nodes.If a pair of torch.Tensor is given, the pair must contain two tensors of shape:math:(N_{in}, D_{in}) and :math:(N_{out}, D_{in}).If apply_func is not None, :math:D_{in} shouldfit the input dimensionality requirement of apply_func.edge_weight : torch.Tensor, optionalOptional tensor on the edge. If given, the convolution will weightwith regard to the message.Returns-------torch.TensorThe output feature of shape :math:(N, D_{out}) where:math:D_{out} is the output dimensionality of apply_func.If apply_func is None, :math:D_{out} should be the sameas input dimensionality.with graph.local_scope():aggregate_fn fn.copy_src(h, m)if edge_weight is not None:assert edge_weight.shape[0] graph.number_of_edges()graph.edata[_edge_weight] edge_weight# message functionaggregate_fn fn.u_mul_e(h, _edge_weight, m)feat_src, feat_dst expand_as_pair(feat, graph)graph.srcdata[h] feat_src# aggregate function: neighbor info self infograph.update_all(aggregate_fn, self._reducer(m, neigh))# self inforst (1 self.eps) * feat_dst graph.dstdata[neigh]if self.apply_func is not None:rst self.apply_func(rst)return rst二、Expressive of Power GNNs 提出图同构网络的论文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成新标签该过程形式化为下方的公式 Luh←hash(Luh−1∑v∈N(U)Lvh−1)L^{h}_{u} \leftarrow \operatorname{hash}\left(L^{h-1}_{u} \sum_{v \in \mathcal{N}(U)} L^{h-1}_{v}\right) Luh←hashLuh−1v∈N(U)∑Lvh−1 符号LuhL^{h}_{u}Luh表示节点uuu的第hhh次迭代的标签第000次迭代的标签为节点原始标签。
在迭代过程中发现两个图之间的节点的标签不同时就可以确定这两个图是非同构的。需要注意的是节点标签可能的取值只能是有限个数。
WL举例说明以一维为栗子
给定两个图GGG和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。这些标签的个数作为整个网络的新特征。 每重复一次以上的过程就完成一次节点自身标签与邻接节点标签的聚合。
第五步判断同构性
当出现两个图相同节点标签的出现次数不一致时即可判断两个图不相似。如果上述的步骤重复一定的次数后没有发现有相同节点标签的出现次数不一致的情况那么我们无法判断两个图是否同构。
当两个节点的hhh层的标签一样时表示分别以这两个节点为根节点的WL子树是一致的。WL子树与普通子树不同WL子树包含重复的节点。下图展示了一棵以1节点为根节点高为2的WL子树。 2WL Subtree Kernel图相似性评估定量化
此方法来自于Weisfeiler-Lehman Graph Kernels。
WL测试不能保证对所有图都有效特别是对于具有高度对称性的图如链式图、完全图、环图和星图它会判断错误。WL测试只能判断两个图的相似性无法衡量图之间的相似性。要衡量两个图的相似性我们用WL Subtree Kernel方法。
Weisfeiler-Lehman Graph Kernels 方法提出用WL子树核衡量图之间相似性。该方法使用WL Test不同迭代中的节点标签计数作为图的表征向量它具有与WL Test相同的判别能力。在WL Test的第kkk次迭代中一个节点的标签代表了以该节点为根的高度为kkk的子树结构。
该方法的思想是用WL Test算法得到节点的多层的标签然后我们可以分别统计图中各类标签出现的次数存于一个向量这个向量可以作为图的表征。两个图的表征向量的内积即可作为这两个图的相似性估计内积越大表示相似性越高。
4.小结
大部分空域图神经网络的更新步骤和WL测试非常类似。就像消息传递网络中归纳的框架大部分基于空域的图神经网络都可以归结为2个步骤聚合邻接点信息aggregate更新节点信息combine。avkAggregate({huk−1:u∈N(v)}),hvkCombine(hvk−1,avk)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)avkAggregate({huk−1:u∈N(v)}),hvkCombine(hvk−1,avk) 与WL测试一样在表达网络结果时一个节点的表征会由该结点的父结点的子树信息聚合而成。
正如上面提到的栗子中下图均值聚合或者最大值聚合把栗子中的v1和v2两个节点映射到了同一个状态错误而如果使用求和函数则能正确分开两者状态。WL测试最大的特点是对每个节点的子树的聚合函数采用的是单射Injective的散列函数。 ——由该特点我们可以通过设计一个单射聚合聚合函数来设计与WL一样强大的图卷积网络同时图同构网络有强大的图区分能力适合图分类任务。
三、General Tips 附时间安排
任务任务内容截止时间注意事项2月11日开始task1图机器学习导论2月14日周二完成task2图的表示和特征工程2月15、16日周四完成task3NetworkX工具包实践2月17、18日周六完成task4图嵌入表示2月19、20日周一完成task5deepwalk、Node2vec论文精读2月21、22、23、24日周五完成task6PageRank2月25、26日周日完成task7标签传播与节点分类2月27、28日周二完成task8图神经网络基础3月1、2日周四完成task9图神经网络的表示能力3月3日周五完成task10图卷积神经网络GCN3月4日周六task11图神经网络GraphSAGE3月5日周七task12图神经网络GAT3月6日周一
Reference
[2] CS224W官网https://web.stanford.edu/class/cs224w/index.html [3] https://github.com/TommyZihao/zihao_course/tree/main/CS224W [4] cs224w图机器学习2021冬季课程学习笔记11 Theory of Graph Neural Networks
