提出统一框架，让图神经网络在任意大小的稀疏与密集图上都可泛化并逼近任意函数。
A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation
- 基于图算子理论，构建覆盖所有图规模的紧凑度量空间。
- 证明了在该框架下图神经网络具有更强的通用逼近能力和泛化界。
- 适用于稀疏图分析，为复杂网络建模提供理论支持。
消息传递图神经网络（MPNN）的泛化与逼近能力通常通过定义输入图空间上的紧凑度量来研究，使得MPNN在此度量下等连续。现有分析分为两类：1）当度量空间包含无界尺寸的图时，理论仅适用于稠密图；2）研究稀疏图时，度量空间仅包含尺寸一致有界的图。本文提出统一方法，在所有尺寸的图（包括稀疏与稠密）构成的空间上定义紧凑度量，使MPNN等连续。由此导出比以往更强的通用逼近定理与泛化界。理论基础源自近年提出的图极限理论——图算子分析（graphop analysis），并加以拓展。
原文摘要 · Abstract (English)
Generalization and approximation capabilities of message passing graph neural networks (MPNNs) are often studied by defining a compact metric on a space of input graphs under which MPNNs are equicontinuous. Such analyses are of two varieties: 1) when the metric space includes graphs of unbounded sizes, the theory is only appropriate for dense graphs, and, 2) when studying sparse graphs, the metric space only includes graphs of uniformly bounded size. In this work, we present a unified approach, defining a compact metric on the space of graphs of all sizes, both sparse and dense, under which MPNNs are equicontinuous. This leads to more powerful universal approximation theorems and generalization bounds than previous works. The theory is based on, and extends, a recent approach to graph limit theory called graphop analysis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。