关于Weisfeiler-Lehman算法的话题（一）

作者简介：如算法“百晓生”，熟悉各类算法原理，典故，应用，背后八卦，心中有一本算法的“兵器谱”，又如算法“扫地僧”利用所在各公司的各种资源，或依托具体业务积累落地经验，或求教于业界大佬行业经验，或旁听于公司邀请的科学家。偶有所得，便欣然忘食。平生所爱，唯算法和剑法，情不知所起，一往而深。

前言：写着写着，发现不是一篇文章能说完的，先写个头吧。 这个话题，喜欢机器学习的人看见的是模型的学习能力，喜欢算法的人看见的是一个设计算法的框架，喜欢离散数学的人看见了代数方法的运用，喜欢纯数学的人可以深挖伽罗华理论。喜欢学术八卦的，可以看到苏联数学往事，以及和西方圈子的爱恨情仇。。。。。。。。。

之前有篇文章《被遗忘的苏联AI往事》在机器学习人工智能相关公众号中进行了广泛传播，尤其介绍了Boris Weisfeiler和Andrey Lehman，以及他们识别图同构与否的算法。其实他们一直没有被遗忘，尤其是最近几年图神经网络算法火了，图神经网络背后的学习能力是和图同构与否的识别问题是紧密相关的。笔者在实际面向业务的算法问题，以及和学术合作者的研究中，都遭遇了这个算法，尤其蕴含了很多非常有趣的现象和启发。

算法两位创始人

关于图神经网络和Weisfeiler-Lehman Test关系，可以看见不同Weisfeiler-Lehman Test测试学习能力等级以及对应的图神经网络类型。

来自Xavier Bresson讲义

被机器学习圈子熟知的WL算法形式（Weisfeiler-Lehman Graph Kernels Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, Karsten M. Borgwardt; 12(77):2539−2561, 2011），就是每个点都不断从邻居点获得标签，进行计算的过程。下面的例子是一维，一次迭代的。

最近笔者的一位学术合作者，和我争论，她觉得Weisfeiler-Lehman一开始的原始论文（A reduction of a graph to a canonical form and an algebra arising during this reduction ，1968）中没有出现树这个词，树结构只是后来的一种实现，觉得我用树结构来说明图神经网络的学习能力有问题。她的这个误解非常有代表性值得深入讨论。所谓鸳鸯绣出从君看，不把金针度与人。我们很多时候学习和看见的数学和算法结论都是一座大楼盖好了以后，把脚手架等辅助施工设施拆除的，也看不见原始图纸。而苏联数学家也往往自成一派，有自己的理论和表述体系，后来的人再用现代或是大众能接受的数学语言来表述。另外著名苏联数学家阿诺德也说过一种极端情况“在西方数学界，至今还是可以靠重写(或用现代术语改写)不为西方熟悉的俄罗斯数学著作或观点而获取名利。”当然这样的事情没有出现在Weisfeiler-Lehman算法身上,有趣的是他们后来都去了美国也成了美国数学家。后偶然间，笔者又回味了Donald Knuth著名的《计算机程序设计艺术》一书，开头就引用了Ada Lovelace的名言，“Many persons who are not conversant with mathematical studies imagine that because the business of[Babbage's Analytical Engine]is to give its results in numerical notation, the nature of its processes must consequently be arithmetical and numerical, rather than algebraical and analytical. This is an error. The engine can arrange and combine its numerical quantities exactly as if they were letters or any other general symbols; and in fact it might bring out its results in algebraical notation, were provisions made accordingly.” 核心意思就是很多人看见最早的计算机巴贝奇分析机结果是以数值的形式出现的，就误以为其过程也是数值和算法形式的，而不是代数和分析。这句话非常适合放在Weisfeiler-Lehman算法这件事情上，他们1968原始论文中用的代数和分析的语言。后来他们自己以及大家的工作，逐渐用图论，组合学和算法的语言来进行阐述，以至于一般人看见了原始论文反而不认识了。当然笔者也是非常惊叹，Ada Lovelace传奇的人生，作为拜伦的女儿，第一个程序员，那么早就洞察了这个现象，而Donald Knuth在《计算机程序设计艺术》第一卷第一章就引用了这段话，也显示了出了他立意之高，一览全局。看来任何一个认真的计算机科学家，都不能忘记了算法诞生过程中所蕴含的代数和分析。著名华尔街金融模型大佬Emanuel Derman在《My life as quant》一书中，说最早物理学家进入华尔街做宽客Quant一个原因是因为，计算机专业的人会写程序但只懂离散数学，不熟悉金融需要的连续数学。我想说这个锅，计算机专业本身不背。Ada Lovelace和Donald Knuth早就强调过，也在著作中体现着，不能只重视数值和算法的结果，也需要代数和分析的过程。当然随着图神经网络的火爆，大家发现了几何，拓扑，群论，代数，各种经典理论计算机科学算法，都开始在机器学习中发挥作用了。机器学习工程师和研究人员，也或多或少也要和这些东西打起交道了。只利用结果，享受数据和算力红利的时代也快过去了。（注：笔者在伦敦瞻仰过Ada故居，也发现过Knuth书中一个数值算法的进位错误获得过回复，多年来一直感谢祖师爷们赏饭）

首先我们看看原始的1968年Weisfeiler-Lehman论文《A reduction of a graph to a canonical form and an algebra arising during this reduction》，原文中主要使用矩阵和代数术语和方法，也是相对于以前的一些启发性算法，首先系统地使用代数工具, 并发明了新的代数量Celluar Algebra。针对有限的，允许重复边的图Γ，通过算法来获得一个图上新的不变量，称为带数量algebra A(Γ) 。同时研究这个algebra A(Γ) 和图的自同构群 Aut(Γ)。其实就是需要满足如果两个图是同构的，那么他们的这个代数量是一样的。这个不变量作为canonical form, 就是图上点对应的矩阵和点相关的canonical labelling, 对于不可比较的(canonical labeling一致）两个点a和b存在一个图上自同构的a到b关系。，引入新的变量矩阵X(Γ) ，这个变量矩阵是通过替换掉图的邻接矩阵中元素来获得，比如可以把原邻接矩阵的1替换为X，对角线替换为Y，0替换成Z。每次迭代是对于矩阵X(Γ)重构操作，同时获得一个新的点对应特征向量。同样特征向量的点分为一类，当分类不再发生变化时，得到稳定分拆，算法收敛。来最终获得canonical form. 当分拆不再变化的时候，实际上这个分拆就是图自同构群的所有轨道。 所以在这样一个代数框架下，就可以使用群论和代数的方法来定义和解决问题。

用现代图论语言来说原来论文中的方法，对图的点集V，获得有序的点对 V × V，(node_u,node_v)，将点对 V × V分拆为不同的颜色集合C1，C2，C3，... ,Cm-1, Cm. 每对 (node_u,node_v) 对应一个列表(i, βjk : 1 ≤ j, k ≤ m), βjk是node_w的数量满足(node_u, node_w) ∈ Cj and (node_w, node_v) ∈ Ck。然后我们对列表中元素按照字典顺序排序，不同的元素对应一个新的颜色，然后直到这个过程收敛。初始的时候，只有三种颜色，node_u和node_v有边的一个颜色, node_u和node_v没有边一个颜色，node_u和node_v相等一个颜色，也就是有边，无边，对角线元素对应一个颜色。所以大家可以看出原始的过程,近似于今天我们机器学习圈子说的二阶WL-Test. 二阶就是2-orbits 2轨道们。之前的一些算法都相当于构成1-orbits，WL是最早构成2-orbits. 当我们对轨道元素进行叠加时候，就是不断获得高阶WL-Test来获得更强的学习能力。

非常有意思的是在Boris Weisfeiler和Andrey Leman 1976年的专著《On construction and identification of graphs》中，开始尝试更加算法化的逼近和描述去解决图的同构问题，包括系统阐述深搜和广搜这样图上基本操作的作用。同时也完善了Celluar Algebra这个代数工具，简单来说，就是对于包含一个图邻接矩阵A的最小Celluar Algebra <<A>>来说，同构的图之间<<A>>也是同构的。这个Weisfeiler-Leman算法背后的代数终极原理。

作者列举了一些算法化例子：

算法1：邻居点求和的过程，初始权重都为1，每个点属于不同的标签，然后每次迭代不断求和，权重一样的点分到一个标签，当分区不再变化的时候，算法停止。

算法2：每个点的权重改成一个向量，向量的值对应邻居点中在相应类的个数。

然后可以扩展到边的情况，点和边一起的情况。

所以回过头来，我们了解了WL原始的思维，其中代数和分析内容后，我们这些算法工程师可以干什么呢?我觉得是我们找到了一个设计图上算法的框架。

第一步：对于每个点设置一个初始值，和一个特征向量

第二步：对于图设计使用一个邻接矩阵A

第三步：通过替换邻接矩阵元素为特定值来获得矩阵X

第四步：定义算法获得的代数量algebra(A) 需要满足的条件，例如同构问题，则是图A和图B同构(等价于, 充分条件，必要条件，充要条件）是 algebra(A) = algebra(B)

第五步：用代数语言定义图的收敛条件，例如同构问题，分拆结果是图自同构群的所有轨道。

第六步：设计每次迭代对矩阵X的具体操作过程，以及点的对应特征向量变化

第七步：用代数方法群论证明算法的正确性，分析算法的时间空间复杂度。

第八步：将第六步结果转化为一个message passing的算法过程，进行计算机程序化。

当然也可以根据自己的需要实现不同精度下的WL测试，比如笔者利用AWS AI Lab的Deep Graph Library(DGL)轻松实现，因为DGL封装了大量Message Passing计算和进行了底层优化。

在最近具体进行图神经网络研究的时候，针对同构判断入射成功率是与点几步以内的子图可能复杂度有关系这一事实，笔者意识到当不考虑点上特征，只从拓扑出发，按照一般GCN算法就是一阶WL Test思路，相当于rooted tree的潜在复杂度，是和子图中树的复杂度紧密相关。回忆起微软研究院快20年前请的Laszlo Lovász 等科学家们就在做图上同态的问题。所以我尝试搜索了下论文。发现最新的一些进展出现了2018年Holger Dell等人《 Lovász Meets Weisfeiler and Leman》这么浪漫名字的论文。

一些核心结论：

远早于Lovász 在微软时期，1968年他就证明了，如果我们用所有的图F到G建立同态关系，两个图G和H同构的充要条件就是Hom(F,G)和Hom(F,H)相等。而最新成果就是当我们限定F为不同的图类型时候，算出来的图同态判断条件对应于不同阶Weisfeiler-Leman Test. 当我们限定F为所有的树的时候，就等价于一阶Weisfeiler-Leman Test的区分图同构能力。

随着笔者成文的过程，发现这个主题非常博大精深，Weisfeiler-Leman Test现在被机器学习圈子熟知的只是很肤浅的一些组合算法实现，其实Weisfeiler-Leman 的工作蕴含了一个设计图上算法的框架，例如标签传播算法就可以用这个框架去重新定义，设计和分析。同时其诞生了一个新的代数组合学和群论工具 Celluar Algebra。同时笔者也是非常惊喜群论是可以用于算法分析的。后续有机会笔者会再对一些主题深入，例如图同构算法判断，图神经网络模型和图同构问题，Celluar Algebra等等。