🤖 machine learning

Universality and Approximation Rates of Graph Neural Networks with Random Features

本文确立了具有部分随机节点特征的消息传递图神经网络对于固定尺寸有向图上的置换不变及置换等变函数具有通用近似能力，同时也推导了基于网络复杂度的其近似率的理论上界。

原作者： Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

发布于 2026-07-30

📖 1 分钟阅读☕ 轻松阅读

原作者： Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

形状变换中的人群之谜

想象一下，你正试图教会一台计算机去理解世界，不是将其视为像素的网格或单词的列表，而是一个连接的网络。这就是**图神经网络（Graph Neural Networks, GNNs）**的领域，它是人工智能的一个分支，旨在处理类似于朋友关系网、分子结构或交通路线这类数据。在这些地图中，最重要的不仅仅是单个项目本身是什么，而是它如何与其邻居相连。

然而，这些计算机必须遵循一条棘手的规则：对称性。如果你有一群朋友并交换了他们的名字，这个群体仍然是同一个群体。一个优秀的图 AI 不应该在意谁坐在 A 椅或 B 椅上；它应该只关心谁在和谁说话的模式。这被称为置换不变性（针对整个群体）或置换等变性（针对个体）。问题在于，标准的 AI 模型对此表现很差。它们经常会被数据的输入顺序所迷惑，无法识别出两个看起来完全不同的名单实际上描述的是同一个社交圈。

为了解决这个问题，科学家们尝试给 AI 提供“随机噪声”或“随机 ID”来帮助它区分节点，就像给人群中的每个人贴上一个临时的、唯一的贴纸一样。但直到现在，我们还不完全清楚这种技巧是否能让 AI 变得足够聪明，从而学习任何可能的模式，或者是否存在学习复杂规则的能力上限。这篇论文深入探讨了这个问题，问道：“如果我们给这些读取图数据的计算机加上随机贴纸，它们能否完美地理解任何图结构？”

随机贴纸的魔力

本文的作者 Lukas Gonon、Thilo Meyer-Brandis 和 Nikras Weber 旨在证明，如果你给一种特定类型的图 AI——称为置换等变神经网络（Permutation-Equivariant Neural Network, PENN）——提供随机节点特征，它会变得极其强大。把 PENN 想象成一群试图在地图上破解谜团的侦探。通常，如果两个嫌疑人看起来一模一样且拥有相同的社交关系，侦探就无法区分他们。但如果你给每个嫌疑人贴上一个随机且唯一的贴纸（一个随机特征），侦探就能最终分辨出他们并破案。

该论文的主要发现是一个“通用”保证。作者证明，从数学上讲，如果你向这些 PENN 输入随机贴纸，它们可以以极高的概率逼近固定规模图上的任何可测函数。用通俗的话说：如果你想让 AI 学习关于一个网络的特定规则（比如预测哪个分子有毒或哪个金融网络存在风险），并且你提供了足够的随机贴纸，那么就存在一种 PENN 架构可以近乎完美地学习该规则。即使该规则非常杂乱或复杂，甚至即使数据在节点和边上附带了许多不同类型的特征，这一结论依然成立。

“好”到什么程度？

但论文并不仅仅是说“它有效”；它还告诉了你 AI 需要多大才能完成任务。作者研究了平滑且表现良好的函数（在数学上称为“ $k$ 次连续可微”，其中 $k \ge 2$ ）。他们推导出了逼近率的公式，这本质上是 AI 随着规模增大而学习速度的一个“限速”。

他们发现，当你要求更高的精度时，网络的深度（层数）只需要呈对数级增长。这是个好消息：如果你希望精度提高一倍，你不需要将大脑规模扩大一倍，只需要增加一点点深度。然而，连接数量（非零权重）会随着你对精度的需求呈多项式级增长。具体而言，复杂度随 $1/\epsilon$ 的幂次缩放，其中 $\epsilon$ 是你期望的误差范围。论文指出，这个幂次取决于你试图学习的规则的“平滑度”（ $k$ ）以及图的大小（ $N$ ）。本质上，对于非常复杂、锯齿状的规则或非常大的图，你需要更多的连接；但对于平滑的规则，AI 依然保持高效。

用于安全的“平均”技巧

论文中一个最有趣且具有实践意义的见解，解决了使用随机贴纸带来的副作用。因为贴纸是随机的，如果你运行一次 AI，它给出的答案可能与你使用不同贴纸运行第二次时的答案略有不同。这破坏了对称性规则：AI 可能会仅仅因为贴纸的变化而以不同的方式对待同一群朋友。

作者提出了一个聪明的解决方法：取平均值。如果你使用不同的随机贴纸多次运行 AI 并取结果的平均值，随机性就会抵消，AI 就会重新变得完全对称。他们证明了这种“平均”版本仍然保留了能够学习任何规则的超能力。这就像是请一群人来猜南瓜的重量；一个人可能会猜得很离谱，但如果你取一百个人的猜测平均值，你会得到一个非常准确的答案。论文表明，通过简单地进行几次运行，你就可以同时获得完美的对称性和完美的学习能力。

这对未来意味着什么

作者谨慎地指出，这是一个理论证明，而非针对特定数据集的模拟。他们在数学上证明了这些模型作为通用逼近器的潜力是存在的。他们明确排除了这样一种观点，即你需要构建复杂的定制化架构才能实现这一点；标准的 PENN 结构在辅以随机特征时就已经足够了。

他们还澄清，虽然随机特征在单次运行中打破了“完美对称”，但它们并没有打破“期望中的对称性”（即平均行为的对称性）。这表明在实践中，使用随机特征是一种稳健的策略。论文总结道，带有随机特征的 PENN 应该被视为图学习任务的一个强力的基准（baseline）。它们不仅仅是理论上的好奇产物；它们为构建既强大又灵活的图 AI 提供了具体的、有数学支撑的蓝图，使这些 AI 能够学习从化学分子到金融系统等各种网络中的复杂模式。

技术摘要：带有随机特征的图神经网络的普适性与逼近率

问题陈述

图神经网络（GNNs），特别是消息传递架构，在经验层面取得了显著成功，但也面临着表达能力的理论局限。标准的基于消息传递的 GNN 受限于 1-Weisfeiler–Leman (1-WL) 测试，这意味着它们无法区分某些非同构的图结构。虽然存在一些克服这些限制的策略（例如更高阶的架构或丰富节点特征），但目前缺乏严谨的理论结果来确立在引入随机特征后，特定且实用的 GNN 架构所具备的**普适逼近（universal approximation）**能力。此外，现有的普适性研究通常依赖于苛刻的假设，例如要求目标函数是连续的、定义域是紧致的，或者特征是有限维的，并且往往未能解决这些模型的逼近率（复杂度界限）问题。

方法论

作者研究了置换等变神经网络（Permutation-Equivariant Neural Networks, PENNs），这是一类泛化了许多流行消息传递架构（如 GCN、GIN、GraphSAGE、GAT）的 GNN。其核心方法论创新在于使用随机节点特征来增强标准节点特征。

架构定义： 论文将 PENNs 定义为由前馈神经网络（FNN）组件（ $\rho, \phi, \alpha, \psi$ ）组成的函数，这些组件负责聚合邻域信息和全局图属性。该结构涵盖了“聚合-组合-读出”（ACR）框架。
随机特征： 作者引入了随机节点特征 $R$ ，用以提供“有限且唯一的节点特征”。这意味着（以高概率或几乎处处）随机特征会为不同的节点分配不同的标识符，从而有效地打破了限制标准 GNN 的对称性。该框架同时兼容独立同分布（i.i.d.）的随机特征以及确定性的唯一标识符（或其随机排列）。
逼近框架： 本研究利用了经典的 FNN 普适逼近定理（例如 Leshno 等人，1993），但将其适配到了图领域。其核心见解是：如果节点特征是唯一的，那么任何置换等变函数都可以表示为作用于这些唯一特征的 FNN 的复合函数。
基于期望的等变性： 考虑到固定随机特征会破坏路径置换等变性（pathwise permutation equivariance），作者分析了期望意义下的置换等变性。他们提出通过对多个重采样的随机特征进行平均处理后的 PENN 来恢复等变性质，同时保留高表达能力。

核心贡献

1. 普适逼近定理

论文证明了增强了随机特征的 PENN 是有向图（具有固定大小及多维节点/边特征）上可测置换不变和置换等变函数的普适逼近器。

通用性： 与先前的工作（如 Abboud 等人，2020；Puny 等人，2020）不同，这一结果并不要求目标函数是连续的，也不假设特征空间是紧致或有限的。它适用于无界定义域上的可测函数。
具体架构： 作者指定了一个具体的架构（PENNs）来证明普适性，而非仅仅断言某种抽象架构的存在。
概率性： 只要随机特征能诱导出唯一的节点标识符，该逼近在任意高概率下均成立。

2. 逼近率与复杂度界限

对于定义在紧致定义域上的 $k$ 次连续可微函数（ $k \ge 2$ ），论文推导出了实现所需误差 $\varepsilon$ 的 PENN 组件复杂度的显式上界。

深度： 所需层数随 $1/\varepsilon$ 对数增长（ $O(\log(1/\varepsilon))$ ）。
宽度/权重： 非零权重的数量随 $1/\varepsilon$ 多项式增长，具体为 $O(\varepsilon^{-c/(k-1)})$ ，其中 $c$ 取决于图的维度（ $N, d, d'$ ）。
维度诅咒： 这些界限反映了关于图领域的某种维度诅咒形式，但对于具有更高正则性（ $k$ ）的函数，其严重程度得到了缓解。

3. 期望意义下的置换等变性

论文探讨了表达能力与对称性之间的权衡。虽然带有随机特征的单个 PENN 实现并非路径置换等变的，但作者证明了 PENN 的期望值（以图输入为条件）是置换等变的。此外，他们表明通过对有限数量的 i.i.d. 随机特征样本进行平均，可以在保持普适逼近性质的同时，提高向等变性的偏差。

结果

定理 9： 确立了对于任何可测置换等变函数 $f$ 以及任何 $\varepsilon, \delta > 0$ ，都存在一个带有随机特征的 PENN，使得逼近误差超过 $\varepsilon$ 的概率至多为 $\delta$ 。
定理 11： 提供了一个测度论版本的普适性结果，适用于图分布本身诱导出唯一节点特征的情况。
定理 16： 证明了平均化后的 PENN（使用 $M$ 个 i.i.d. 副本的随机特征）同样满足普适逼近性质，且误差概率受 $\delta$ 控制。
定理 18： 提供了定量逼近率。它证明了对于足够正则的函数，具有特定架构约束（深度和宽度）的 PENN 可以以高概率一致地逼近目标函数。其复杂度界限与标准前馈神经网络已知的界限相一致。

意义与主张

作者声称这项工作填补了 GNN 理论理解中的重大空白：

弥合理论与实践： 通过证明一种具体的、内存高效的架构（PENNs）而非抽象模型具有普适性，这些结果为在实际 GNN 应用中使用随机特征提供了理论基础。
现有结果的泛化： 通过放宽对连续性、紧致性和目标函数性质（可测 vs 连续）的假设，泛化了先前的普适性定理。
实践指导： 推导出的逼近率根据所需的精度和目标函数的正则性，为选择超参数（深度和宽度）提供了理论指导。
基准测试： 作者建议应将带有随机特征的 PENN 视为强大的基准模型，既可以作为最先进模型的竞争性替代方案，也可以作为验证其他架构能力的参考点。

论文得出结论，虽然随机特征可能会引入路径等变性的损失，但由此产生的模型具有卓越的表达能力，并且通过平均处理后仍能保留理想的对称性质，使其成为图学习中一种稳健的理论和实践工具。