图神经网络随机特征的普适性与近似率

arXiv cs.LG 论文
graph-neural-networks random-features universality approximation-rates permutation-equivariance message-passing

摘要

本文证明，具有随机节点特征的图神经网络可以普适地近似有向图上的置换不变或等变函数，并为可微函数提供了近似率界限。

arXiv:2607.26699v1 公告类型：新 摘要：我们研究了具有随机节点特征的基于消息传递的图神经网络。随机节点特征在理论和实证上都被证明能增强图神经网络（GNNs）的表达能力。在此，我们建立了一个新的普适性结果，聚焦于置换等变神经网络（PENNs），这是一类由前馈神经网络组件构建的GNN，涵盖了许多著名的GNN架构。我们证明，结合部分随机节点特征，PENNs能够以任意高的概率近似任意定义在固定大小有向图上的可测置换不变或置换等变函数，这些图具有多维节点和边特征。对于$k$次连续可微函数，$k\geq 2$，我们还推导了近似率的上界，将PENN前馈组件的复杂度（以层深度和非零权重数量衡量）与所需的近似精度联系起来。
查看原文
查看缓存全文

缓存时间: 2026/07/30 10:00 

# 带随机特征的图神经网络的普适性与逼近率

来源：https://arxiv.org/abs/2607.26699  
查看 PDF（https://arxiv.org/pdf/2607.26699）

> 摘要：本文研究带有随机节点特征的消息传递图神经网络。随机节点特征已知能在理论和经验上增强图神经网络（GNN）的表达能力。我们建立了一个新的普适性结果，聚焦于排列等变神经网络（PENNs）——这是一类由前馈神经网络组件构建的GNN，涵盖了许多主流GNN架构。我们证明，结合部分随机节点特征的PENN能够以任意高概率逼近任意可测的排列不变或排列等变函数，这些函数定义在具有多维节点和边特征的固定大小有向图上。对于 $k$ 次连续可微函数，$k \geq 2$，我们还推导了逼近率的上界，该界将PENN前馈组件的复杂度（以层深和非零权重数量衡量）与期望逼近精度关联起来。

## 提交历史

来自：Niklas Weber [查看邮件（https://arxiv.org/show-email/b16baa18/2607.26699）] **[v1]**  
2026年7月29日星期三 09:46:07 UTC（72 KB）

相似文章

非均匀随机图中的保距嵌入

arXiv cs.LG

本文分析了非均匀随机图中的保距嵌入，提供了比经典最坏情况结果更紧的失真界，并引入了一种GNN增强变体，可从小型图中学习通用特征。

非线性算子及其导数的通用逼近

arXiv cs.LG

本文证明了在无限维空间中非线性算子及其导数的首个通用逼近定理，将经典结果扩展到DeepONet和PCA-Net等算子学习架构。

广义神经元

ML at Berkeley

本文探讨了深度学习中的通用近似定理，分析了使用 ReLU 激活函数时单个神经元和神经网络层的表示能力。

任意维度不变普适性

arXiv cs.LG

本文开发了一个系统框架，用于建立处理可变维度输入（例如，具有不同节点数的图）的机器学习模型的普适性。论文表明许多现有架构不具有普适性，并提出了简单的修改来恢复普适性。