Weisfeiler-Lehman Test
算法
定义与定理
定义:
(1)图:
(2)图序列:
(3)第h次迭代的某个图核k的WL图核:
{G0,…,Gh}和{G ’ 0,…,G 'h}分别为G和G '的Weisfeiler-Lehman序列
(4):某个字母出现的次数
(5)WL图子核:
定理:
(1)设基核k为图上任意正半定核。然后相应的也是正半定的。
(2)图G和G’的WL图子核可以在O(hm)的时间复杂度里计算出来
(3)
示例
过程:
(1)将每个节点的邻居添加到节点的序列上
(2)将序列进行重新标号,将新出现的标号加入到原标号集合里
(3)最后一个图的序列是指:遍历每个标号在图上的出现次数
在迭代过程中如果出现两个图的序列集合不一致,即可推断出两个图不同构。