Invariant-Based Diagnostics for Graph Benchmarks
作者: Richard von Moos, Mathieu Alain, Bastian Rieck
分类: cs.LG, math.CO
发布日期: 2026-05-07
💡 一句话要点
提出基于图不变性的诊断框架，评估图神经网络是否真正学习图结构。
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 图神经网络 图不变性 基准测试 结构学习 模型诊断
📋 核心要点
- 现有图神经网络基准测试难以区分节点特征和图结构对模型性能的贡献，阻碍了对模型结构学习能力的有效评估。
- 论文提出基于图不变性的诊断框架，利用排列不变的结构描述符来分析图结构的异质性，并预测模型性能。
- 实验表明，基于不变性的简单模型在多个数据集上表现优异，甚至超越了复杂的Transformer和消息传递模型。
📝 摘要（中文）
图基础模型的发展受到基准测试实践的阻碍，这些实践混淆了节点特征和图结构的贡献，使得难以判断模型是否真正从连接性中学习，甚至是否需要连接性。我们提出使用图不变性来解决这个问题，即排列不变、任务无关的结构描述符，作为图基准测试的诊断框架。我们证明了 (i) 不变性比标准 GNN 更具表达性，(ii) 不变性表征了基准数据集内部和跨数据集的结构异质性，(iii) 不变性预测多任务性能，以及 (iv) 简单的基于不变性的模型在 26 个数据集上与 Transformer 和消息传递基线模型相比具有竞争力，有时甚至超过它们。我们的结果表明，表达性不是预测性能的主要驱动因素，并且在结构重要的任务中，非训练的结构代理通常与训练的消息传递模型相匹配。因此，我们认为不变性基线应该成为评估任务是否需要结构以及模型是否能识别结构的基准，作为图基础模型的垫脚石。
🔬 方法详解
问题定义：现有图神经网络的基准测试方法，难以区分节点特征和图结构对模型性能的贡献。模型可能仅仅依赖节点特征，而没有真正学习到图的结构信息。这使得评估图神经网络的结构学习能力变得困难，也阻碍了图基础模型的发展。
核心思路：论文的核心思路是利用图不变性（graph invariants）作为诊断工具。图不变性是指那些在图的节点排列发生变化时保持不变的图的结构属性。通过分析图不变性，可以了解图的结构特征，并评估模型是否真正利用了这些结构信息。如果一个模型在图不变性已经能够很好地预测结果的情况下，仍然表现良好，那么可能意味着该模型并没有充分利用图的结构信息。
技术框架：该方法主要包含以下几个阶段：1) 计算图数据集的各种图不变性特征。2) 使用这些不变性特征来表征数据集的结构异质性。3) 建立基于不变性的预测模型，并评估其性能。4) 将基于不变性的模型与现有的图神经网络模型进行比较，以评估现有模型是否真正利用了图的结构信息。
关键创新：该论文的关键创新在于提出了使用图不变性作为图神经网络基准测试的诊断工具。与传统的评估方法不同，该方法能够更清晰地揭示模型是否真正学习了图的结构信息，而不仅仅是依赖节点特征。此外，论文还证明了图不变性在预测模型性能方面具有很强的能力，甚至可以与复杂的图神经网络模型相媲美。
关键设计：论文中使用了多种图不变性特征，包括节点度分布、聚类系数、最短路径长度等。基于不变性的预测模型可以使用简单的线性模型或更复杂的机器学习模型。关键在于选择合适的图不变性特征，并设计有效的预测模型，以充分利用这些特征的信息。
🖼️ 关键图片
📊 实验亮点
实验结果表明，基于图不变性的简单模型在26个数据集上与Transformer和消息传递基线模型相比具有竞争力，有时甚至超过它们。这表明，在某些任务中，图的结构信息比节点特征更重要，并且简单的结构代理可以与复杂的图神经网络模型相媲美。例如，在某些数据集上，基于不变性的模型达到了与GNN相当甚至更高的性能，而无需进行任何训练。
🎯 应用场景
该研究成果可应用于图神经网络的基准测试和模型选择，帮助研究人员更好地理解模型的结构学习能力，并选择更适合特定任务的模型。此外，该方法还可以用于图数据分析和特征工程，提取有用的图结构信息，为下游任务提供支持。未来，该方法有望推动图基础模型的发展，并促进图神经网络在各个领域的应用。
📄 摘要（原文）
Progress on graph foundation models is hindered by benchmark practices that conflate the contributions of node features and graph structure, making it hard to tell whether a model actually learns from connectivity, or whether it even needs to. We propose addressing this using graph invariants, i.e., permutation-invariant, task-agnostic structural descriptors that serve as a diagnostic framework for graph benchmarks. We show that (i) invariants are more expressive than standard GNNs, (ii) invariants characterize structural heterogeneity within and across benchmark datasets, (iii) invariants predict multi-task performance, and (iv) simple invariant-based models are competitive with, and sometimes exceed, transformer and message-passing baselines across 26 datasets. Our results suggest that expressivity is not the main driver of predictive performance, and that on tasks where structure matters, a non-trainable structural proxy often matches trained message-passing models. We thus posit that invariant baselines should become a standard for evaluating whether structure is required for a task and whether a model picks up on it, serving as a stepping stone towards graph foundation models.