Weisfeiler 和 Leman 的循环：图形表示学习的新层次结构
内容提要
本文研究了图神经网络（GNN）及其与$1$-WL算法的比较，提出了$k$-维GNN，并证明其在社交网络和分子图像中的有效性。探讨了图同构、表达能力及应用，提出了$k$-阶不变GNN，在图分类中表现优异。同时，研究了Weisfeiler-Leman算法在子图匹配中的应用，提出了新的GNN框架$k$-FWL+，并展示了其在多个数据集上的优越性能。
延伸解读
从1-WL到k-WL：表达能力提升的路径
文章梳理了图神经网络与Weisfeiler-Leman算法对比的研究脉络。1-WL是衡量GNN表达能力的基准，但存在局限。通过提出k维GNN、k阶不变GNN等扩展，将WL层次结构引入GNN设计，使其能捕捉社交网络和分子图像中的高阶结构。这为理解GNN表达能力的边界提供了理论工具。
WL算法在子图匹配中的理论进展
文章介绍了Weisfeiler-Leman算法在子图模式匹配中的应用研究。对于k=1和k=2的情况，探究了满足k-WL不变性的子图模式，其发生次数也具有k-WL不变性，并得出了完整结论。此外，还有工作提出了子图计数问题的WL维度的多项式时间算法，回答了之前的开放问题。这些理论成果为子图级图学习任务奠定了基础。
k-FWL+框架与N2-GNN的实证优势
文章提到了一种新的GNN框架k-FWL+，它探索了表达能力和设计空间的灵活性。基于该框架设计的N2-GNN在ZINC-Subset和ZINC-Full数据集上取得了比之前最先进结果更好的性能。这表明理论上的表达能力提升可以转化为实际图学习任务中的性能改进，尤其是在分子图数据集上。
效率与泛化的平衡：d-DRFWL(2)与泛化条件
文章还涉及了效率与泛化的权衡。d-DRFWL(2) GNNs通过限制距离的节点对信息传递，避免了昂贵的子图提取，在计算3至6环等循环结构时效率最高。同时，有研究探讨了增强WL和消息传递GNN表达力与改善泛化能力之间的不明确关系，并提出了具有可证明泛化性质的变体。这提示读者，表达能力并非唯一目标，泛化性和计算效率同样关键。
Q&A
什么是$k$-维图神经网络（GNN）？
$k$-维GNN是一种扩展的图神经网络方法，旨在处理社交网络和分子图像等高阶结构。
Weisfeiler-Leman算法在图神经网络中有什么应用？
Weisfeiler-Leman算法用于衡量图神经网络的表达能力，并在子图匹配中具有重要应用。
文章中提到的$k$-FWL+框架有什么优势？
$k$-FWL+框架在多个数据集上表现优越，尤其是在ZINC-Subset和ZINC-Full数据集上。
图同构在图神经网络中有什么重要性？
图同构是图神经网络的核心概念，影响其表达能力和应用效果。
如何评估图神经网络的表达能力？
可以通过Weisfeiler-Leman测试等方法来评估图神经网络的表达能力。
文章中提到的N2-GNN模型有什么特点？
N2-GNN模型是基于$k$-FWL+框架设计的，显示出比之前最先进的结果更好的性能。
