A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants
A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants
复制标题
DOI：
10.1109/icassp39728.2021.9413523
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Ningyuan Huang;Soledad Villar
中科院分区：
文献类型：
--
作者：
Ningyuan Huang;Soledad Villar
图神经网络被设计为学习图上的函数。通常，相关目标函数相对于置换的动作是不变的。因此，图同构算法启发了一些图神经网络结构的设计，经典的Weisfeiler-Lehman算法（WL）--一种基于颜色细化的图同构测试算法--与图神经网络的研究相关。WL测试可以推广到高阶测试的层次结构，称为k-WL。这种层次结构被用来描述图神经网络的表达能力，并启发图神经网络架构的设计。这篇短文的目的是教学和实用：我们解释了WL和民间传说WL公式之间的差异，并指出了文献中现有的讨论。我们照亮的配方之间的差异，通过可视化的例子。
Graph neural networks are designed to learn functions on graphs. Typically, the relevant target functions are invariant with respect to actions by permutations. Therefore the design of some graph neural network architectures has been inspired by graph-isomorphism algorithms.The classical Weisfeiler-Lehman algorithm (WL)—a graph-isomorphism test based on color refinement—became relevant to the study of graph neural networks. The WL test can be generalized to a hierarchy of higher-order tests, known as k-WL. This hierarchy has been used to characterize the expressive power of graph neural networks, and to inspire the design of graph neural network architectures.A few variants of the WL hierarchy appear in the literature. The goal of this short note is pedagogical and practical: We explain the differences between the WL and folklore-WL formulations, with pointers to existing discussions in the literature. We illuminate the differences between the formulations by visualizing an example.