Higher-Order Graphon Neural Networks: Approximation and Cut Distance

📄 arXiv: 2503.14338v3 📥 PDF

作者: Daniel Herbst, Stefanie Jegelka

分类: cs.LG

发布日期: 2025-03-18 (更新: 2025-05-18)

备注: 53 pages, 6 figures, 2 tables. ICLR 2025 camera ready

💡 一句话要点

提出不变Graphon网络(IWN)，用于高阶图神经网络的逼近和割距离研究。

🎯 匹配领域: 支柱五：交互与反应 (Interaction & Reaction)

关键词: 高阶图神经网络 Graphon 不变Graphon网络 图极限 规模迁移学习

📋 核心要点

  1. 现有GNN研究多集中于消息传递GNN，而忽略了更强大的高阶GNN，限制了模型表达能力。
  2. 本文提出不变Graphon网络(IWN)，通过限制IGN基，使其与Graphon空间几何结构对齐，提升模型表达能力。
  3. 证明了k阶IWN至少与k-WL测试一样强大，并在Lp距离上建立了Graphon信号的通用逼近结果。

📝 摘要（中文）

本文研究了高阶图神经网络(GNNs)的规模迁移性，利用图极限模型（如稠密图的Graphon）。不同于以往关注消息传递GNNs (MPNNs)的研究，本文侧重于更强大的高阶GNNs。首先，我们将Graphon的$k$-WL测试扩展到Graphon-信号空间，并引入信号加权同态密度作为关键工具。以不变图网络(IGNs)为例，我们将其推广到Graphon，提出了不变Graphon网络(IWNs)，它通过对应于有界线性算子的IGN基的子集来定义。即使使用这个受限的基，我们也证明了$k$阶IWNs至少与$k$-WL测试一样强大，并且建立了Graphon-信号在$L^p$距离上的通用逼近结果。这显著扩展了Cai & Wang (2022)的工作，表明IWNs（他们IGN-small的一个子集）在极限情况下有效地保留了与完整IGN基相同的表达能力。与他们的方法相比，我们的IWN蓝图也更好地与Graphon空间的几何结构对齐，例如，便于与MPNN进行比较。我们强调，虽然典型的高阶GNNs关于割距离是不连续的（这导致了它们的收敛性不足，并且与$k$-WL的定义内在相关），但可迁移性仍然是可以实现的。

🔬 方法详解

问题定义：现有高阶图神经网络在图极限（Graphon）上的研究不足，尤其是在保持模型表达能力的同时，如何保证模型在割距离上的连续性，从而实现更好的迁移性是一个挑战。传统高阶GNNs在割距离上不连续，导致收敛性问题，限制了其应用。

核心思路：本文的核心思路是将不变图网络(IGNs)推广到Graphon空间，提出不变Graphon网络(IWNs)。通过选择IGN基的一个子集，使其对应于有界线性算子，从而在保证模型表达能力的同时，更好地与Graphon空间的几何结构对齐，提高模型在割距离上的连续性。

技术框架：本文的技术框架主要包括以下几个部分：1) 将k-WL测试扩展到Graphon-信号空间；2) 引入信号加权同态密度作为关键工具；3) 定义不变Graphon网络(IWNs)，它是IGNs在Graphon上的推广，使用IGN基的一个子集；4) 证明IWNs的表达能力和通用逼近性质。

关键创新：本文的关键创新在于提出了不变Graphon网络(IWNs)，它通过限制IGN基，使其与Graphon空间的几何结构对齐。这种设计使得IWNs在保持高阶GNN表达能力的同时，提高了模型在割距离上的连续性，从而改善了模型的迁移性。与直接使用完整IGN基相比，IWNs更易于分析和比较，也更符合Graphon空间的特性。

关键设计：IWNs的关键设计在于选择合适的IGN基子集，使其对应于有界线性算子。具体来说，作者选择的基函数需要满足一定的线性性和有界性条件，以保证IWNs的连续性和逼近能力。此外，信号加权同态密度被用作分析IWNs表达能力的关键工具，通过分析不同信号加权同态密度之间的关系，可以推导出IWNs的表达能力上限。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文证明了k阶IWN至少与k-WL测试一样强大，并在Lp距离上建立了Graphon信号的通用逼近结果。这表明IWN在保持高阶GNN表达能力的同时，提高了模型在割距离上的连续性，从而改善了模型的迁移性。该结果显著扩展了Cai & Wang (2022)的工作，表明IWNs在极限情况下有效地保留了与完整IGN基相同的表达能力。

🎯 应用场景

该研究成果可应用于图神经网络的规模迁移学习，例如，在小规模图上训练的模型可以更好地泛化到大规模图上。此外，该方法还可以用于图分类、图回归等任务，尤其是在需要处理大规模图数据的场景下，具有重要的应用价值和潜力。未来，该研究可以进一步扩展到动态图、异构图等更复杂的图结构上。

📄 摘要（原文）

Graph limit models, like graphons for limits of dense graphs, have recently been used to study size transferability of graph neural networks (GNNs). While most literature focuses on message passing GNNs (MPNNs), in this work we attend to the more powerful higher-order GNNs. First, we extend the $k$-WL test for graphons (Böker, 2023) to the graphon-signal space and introduce signal-weighted homomorphism densities as a key tool. As an exemplary focus, we generalize Invariant Graph Networks (IGNs) to graphons, proposing Invariant Graphon Networks (IWNs) defined via a subset of the IGN basis corresponding to bounded linear operators. Even with this restricted basis, we show that IWNs of order $k$ are at least as powerful as the $k$-WL test, and we establish universal approximation results for graphon-signals in $L^p$ distances. This significantly extends the prior work of Cai & Wang (2022), showing that IWNs--a subset of their IGN-small--retain effectively the same expressivity as the full IGN basis in the limit. In contrast to their approach, our blueprint of IWNs also aligns better with the geometry of graphon space, for example facilitating comparability to MPNNs. We highlight that, while typical higher-order GNNs are discontinuous w.r.t. cut distance--which causes their lack of convergence and is inherently tied to the definition of $k$-WL--transferability remains achievable.