ILG-3-GNN

新的 Weisfeiler--Leman 变体显示出增强的图同构测试能力

本文介绍了隐式线图高阶 Weisfeiler--Leman (ILG-k-WL)，一种通过操作源自端点关联的线图关系而不进行显式构建来分析图同构的方法。研究探讨了 k-WL 在线图上的表达能力与其根图之间的关系，发现对于 k=1,2，ILG-k-WL 不提供额外的区分能力。然而，对于 k=3，ILG-3-WL 表现出比标准 3-WL 更强的表达能力，这可以通过它区分 Shrikhande/rook 对等强正则对的能力来证明。