论文标题
渐进的Weisfeiler-Leman：缓慢而稳定的胜利
Gradual Weisfeiler-Leman: Slow and Steady Wins the Race
论文作者
论文摘要
经典的Weisfeiler-Leman算法（又称颜色的细化）对于使用内核和神经网络的图形学习至关重要。该算法最初是用于图形同构测试的，迭代算法可完善顶点颜色。在许多数据集中，经过几次迭代后，可以达到稳定的着色，并且机器学习任务的最佳迭代数量通常更低。这表明颜色差异太快，定义了一个太粗糙的相似性。我们概括了颜色细化的概念，并提出了一个逐步邻里改进的框架，这使得收敛较慢，从而提供了更细粒度的细化层次结构和顶点相似性。我们通过聚类顶点邻域来分配新颜色，从而替换原始的注射颜色分配功能。我们的方法用于得出现有图形内核的新变体，并通过有关顶点相似性的最佳分配来近似图表编辑距离。我们表明，在这两个任务中，我们的方法的表现都超过了原始颜色的细化，而运行时间则适度提高了最新技术状态。
The classical Weisfeiler-Leman algorithm aka color refinement is fundamental for graph learning with kernels and neural networks. Originally developed for graph isomorphism testing, the algorithm iteratively refines vertex colors. On many datasets, the stable coloring is reached after a few iterations and the optimal number of iterations for machine learning tasks is typically even lower. This suggests that the colors diverge too fast, defining a similarity that is too coarse. We generalize the concept of color refinement and propose a framework for gradual neighborhood refinement, which allows a slower convergence to the stable coloring and thus provides a more fine-grained refinement hierarchy and vertex similarity. We assign new colors by clustering vertex neighborhoods, replacing the original injective color assignment function. Our approach is used to derive new variants of existing graph kernels and to approximate the graph edit distance via optimal assignments regarding vertex similarity. We show that in both tasks, our method outperforms the original color refinement with only a moderate increase in running time advancing the state of the art.
