1.Weisfeiler-Lehman Algorithm

欢迎访问个人网络日志🌹🌹知行空间🌹🌹

Weisfeiler-Lehman Algorithm是美国的数学家Boris Weisfeiler在1968年发表的论文the reduction of a graph to a canonical form and an algebra arising during this reduction中提出的判断图同构(Graph Isomorphism)与否的算法。

1.图同构介绍

参考自维基百科

图同构描述的是图论中，两个图之间的完全等价关系。在图论的观点下，两个同构的图被当作同一个图来研究。

只有节点数目相同(即同阶)的两个图才有可能同构。

两个简单图$G$和$H$称为是同构的，当且仅当存在一个将$G$的节点$1,...,n$映射到$H$的节点$1,...,n$的一一对应$\sigma$ ，使得$G$中任意两个节点$i$和$j$相连接，当且仅当$H$中对应的两个节点${\sigma }_i$和${\sigma }_j$相连接。同构可记作$G\simeq H$。

一组彼此同构的图可称为同构图。

一幅图经常可以有多种不同的方式在纸上或屏幕上画出来，所以两个看起来很不同的图也可能是同构的。尤其当图的节点数比较大时，很难一眼从画出的图上判断它们是否同构。

2.Weisfeiler-Lehman Algorithm

第一部分介绍了什么是图同构，Weisfeiler-Lehman算法正是为了用来判断图是否同构的算法，因此也被称为Weisfeiler-Lehman Isomorphism Test,不过现在已经发现，单纯的通过该算法还不能够确保图同构。

图中的节点表示为$v_i$,边表示为$e_i$,节点的集合表示为$\mathcal{V}$，边的集合表示为$\mathcal{E}$，如此图可以表示为$\mathcal{G}=(\mathcal{V},\mathcal{E})$。

Weisfeiler-Lehman算法是通过进行多次迭代，然后判断节点上的标签值的个数是否一致来判断图是否同构。

算法中：

• $i$表示算法迭代的次数
• $n$表示第$n$个节点
• $L_{i,n}$表示节点$v_n$邻居节点标签的集合(multiset,A multiset is a set where elements may appear multiple times.)
• $C_{i,n}$表示算法每一次迭代中给每个节点赋予的标签值。$L_{i,n}$相同的节点$C_{i,n}$也相同。

算法步骤：

• 1)开始时初始化所有节点$C_{0,n}=1$
• 2)第$i$步，对于每个节点$n$,定义$L_{i,n}是由$i-1$步的$C_{i-1,m}$组成的‘multiset‘,$m$是节点$n$的所有邻居节点。
• 3)计算$C_{i,n}=hash(L_{i,n})$
• 4)统计每种标签值节点的个数，重复步骤2)和3)N步或算法收敛。

例如：

下图中Graph1和Graph2是同构的：

初始化：

对于iteration=1

对于iteration=2

对于iteration=3

到第3步可以看到两个图中都是有2个7，1个8，2个9， 因此，两个图是同构的。

3.后话

关于算法作者Boris Weisfeiler,是一个数学家，其本身是犹太人，出生在苏联，后转到美国，但是在1985年于智利神秘失踪，生死未卜。

欢迎访问个人网络日志🌹🌹知行空间🌹🌹

参考资料

• 1.https://davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/
• 2.https://en.wikipedia.org/wiki/Boris_Weisfeiler