Weisfeiler-Lehman Test

Weisfeiler-Lehman Test

算法

Weisfeiler-Lehman Test
Weisfeiler-Lehman Test

定义与定理

定义:

(1)图:
Weisfeiler-Lehman Test
(2)图序列:
Weisfeiler-Lehman Test
(3)第h次迭代的某个图核k的WL图核:
Weisfeiler-Lehman Test
{G0,…,Gh}和{G ’ 0,…,G 'h}分别为G和G '的Weisfeiler-Lehman序列

(4):某个字母出现的次数
Weisfeiler-Lehman Test
(5)WL图子核:
Weisfeiler-Lehman Test

定理:
(1)设基核k为图上任意正半定核。然后相应的Weisfeiler-Lehman Test也是正半定的。
(2)图G和G’的WL图子核可以在O(hm)的时间复杂度里计算出来
(3)Weisfeiler-Lehman Test

示例

Weisfeiler-Lehman Test
过程:
(1)将每个节点的邻居添加到节点的序列上
(2)将序列进行重新标号,将新出现的标号加入到原标号集合里
(3)最后一个图的序列是指:遍历每个标号在图上的出现次数
在迭代过程中如果出现两个图的序列集合不一致,即可推断出两个图不同构。

上一篇:如果Linux安装Redis编译make[1]: *** [server.o] Error 1 make[1]: Leaving directory `/other/redis-6.0.15/src‘


下一篇:如何指定运行时动态库.so的链接地址?-L, -Xlinker, -Wl,-rpath