arXiv:2503.14338cs.LG2025-03ICLR被引 5

提出图信号上的高阶图神经网络,实现对图极限的通用逼近。

Higher-Order Graphon Neural Networks: Approximation and Cut Distance

  • 基于图信号空间推广k-WL测试,引入加权同态密度作为核心工具
  • 所提IWN模型在k阶下至少等价于k-WL测试,且在Lp距离上具通用逼近性
  • 方法更契合图极限空间几何结构,适合研究图神经网络的规模迁移性

图极限模型(如稠密图的图论)近年来被用于研究图神经网络(GNN)的规模可转移性。尽管多数研究聚焦于消息传递型GNN(MPNN),本文关注更强的高阶GNN。首先,我们将k-WL测试(Böker, 2023)扩展至图论-信号空间,并引入信号加权同态密度作为关键工具。以不变图网络(IGN)为例,我们将其推广至图论,提出基于有界线性算子子集的不变图论网络(IWN)。即使使用受限基,k阶IWN至少等价于k-WL测试,且建立了在Lp距离下对图论-信号的通用逼近结果。该工作显著拓展了Cai & Wang(2022)的研究,表明IWN——其为IGN-small的子集——在极限下仍保持与全基相当的表达能力。相较前者,本方法更契合图论空间几何,便于与MPNN比较。我们指出,典型高阶GNN关于切距离不连续,导致收敛性缺失,这与k-WL定义密切相关;但可转移性依然可达。

原文摘要 · Abstract (English)

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.

图神经网络图极限高阶模型通用逼近

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。