摘要

基于1维Weisfeiler-Leman算法的图核及其相应的神经架构最近作为（监督）图学习的强大工具崭露头角。然而，由于这些算法的纯粹局部性质，它们可能会忽略给定数据中的关键模式，并且只能处理二元关系。为了应对这一问题，$k$-维Weisfeiler-Leman算法通过考虑定义在顶点集合上的$k$-元组，并定义这些顶点元组之间合适的邻接关系来解决。因此，该算法能够捕捉顶点之间的高阶交互作用。然而，该算法在机器学习环境中应用时存在扩展性和过拟合的问题。因此，设计同时具备表达能力、可扩展性和非过拟合性的WL（Weisfeiler-Leman）图学习方法仍然是一个重要的开放问题。本文中，我们提出了局部变体及其相应的神经架构，这些方法仅考虑原始邻域的一个子集，从而提高了可扩展性并减少了过拟合的风险。我们的算法之一在区分非同构图的能力方面严格高于原始算法。实验研究表明，无论是核方法还是神经架构，局部算法都显著减少了计算时间，并防止了过拟合现象的发生。核版本在多个基准数据集上的图分类任务中建立了新的最先进水平，而神经版本则在大规模分子回归任务中展示了令人鼓舞的性能。