当前位置:   article > 正文

Weisfeiler-Lehman算法测试图同构_同构测试

同构测试

背景

Weisfeiler-Lehman算法(威斯费勒-莱曼算法)是测试图同构的经典算法之一,我在这儿记录一下它的实现原理,参考文章为Weisfeiler-Lehman Graph Kernels

伪代码

论文中的伪代码如下所示

假设要测试同构的两张图为G和G`,那么在结点v的第i次迭代里,算法都分别做了四步处理:标签复合集定义、复合集排序、标签压缩和重标签。

标签复合集定义

如果是第一次迭代, v的标签复合集里只有一个元素,就是v的标签。

如果不是第一次迭代,v的标签复合集元素就是v的所有邻居在上一轮迭代里,生成的标签。

复合集排序

首先,对复合集里的元素进行升序排序,并把排序好的元素拼接为一个字符串s;然后把v在上一轮迭代生成的标签作为前缀,添加到这个s里。

标签压缩

对两张图G和G`中所有结点的字符串s,进行升序排列;然后通过映射函数f,把每一个s映射成一个压缩标签,并且当且仅当s1 = s2时,生成的压缩标签才一样。

也是说,压缩标签类似于s的标识符,而映射函数f完全可以用计数函数来实现。其实只要能让s和压缩标签一一对应,前面的对s进行升序排列这一步就没必要做了。

重标签

将压缩标签作为结点v在两张图中的第i轮标签。

如果G和G`在这一轮生成的标签集不一样,那么这两张图就不是同构的,算法直接结束。

举例

以下面的图为例,图a到图d显示了威斯费勒-莱曼算法在G和G`上的第一轮迭代过程

图a是初始形态,结点的标签对应结点类型。

图b则是复合集的生成与排序拼接的结果。对于某个结点v,他的复合集是邻居在上一轮迭代生成的标签集。但是这里的上一轮迭代为初始化,那么邻居在上一轮迭代生成的标签就是邻居的初始标签(也就是结点类型)。因此,以图G为例,两个1号结点的复合集就都是{4},4号结点的复合集就是{1, 1, 3, 5}(要升序排列),其余以此类推。完成之后,把排序好的复合集中的元素,依次拼接成字符串s,然后把结点标签本身,作为前缀拼接到s前面。在G中,对于结点1,生成的s就是"1, 4";对于结点4,生成的s就是"4, 1135"。最后,用s替代结点v的标签。

图c则是标签压缩过程,把G和G`中所有的复合集按升序排列,并且按顺序依次标号。这里的排序规则是按元素数值的升序进行排列,因此{2, 3}在{1, 4}前面,{2, 4, 5}在{2, 3, 5}前面。由于经过上一轮迭代(初始迭代),图中已经出现了5类结点,那么这里的编号从6开始。

图d则是最后一步重排序,用生成的编号代替每个结点的复合集,得到结点在这一轮迭代中生成的新标签。

对于上面的两张图来说,第1轮生成的新标签集合就已经不一样了,因此他们俩是异构图。

时间复杂度

由于每一轮迭代主要处理的是排序,那么假设对于某个图G,每一次迭代可以生成的复合集中有m个元素,根据计数排序,迭代时间复杂度就是O(m)。每一轮生成的复合集的元素数量m是>=结点数n的,因为每个结点的复合集都至少包含自己的标签。

如果迭代次数为h,那么威斯费勒-莱曼算法计算复杂度就是O(hm)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/815052
推荐阅读
相关标签
  

闽ICP备14008679号