论文标题
关于Weisfeiler-Lehman测试及其变体的简短教程
A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants
论文作者
论文摘要
图形神经网络旨在学习图形上的功能。通常，相关的目标函数在置换方面是不变的。因此，某些图神经网络体系结构的设计受到图形形态算法的启发。经典的Weisfeiler-Lehman算法（WL）是基于颜色改进的图形测试 - 与图神经网络的研究有关。 WL测试可以推广到高阶测试的层次结构，称为$ K $ -WL。该层次结构已用于表征图神经网络的表达力，并激发图形神经网络体系结构的设计。文献中出现了一些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.
