随机节点特征提升图神经网络表达力，可逼近任意图函数。
Universality and Approximation Rates of Graph Neural Networks with Random Features
- 用随机节点特征增强消息传递GNN的表达能力
- 对光滑函数，推导出逼近误差上界与网络复杂度关系
- 适用于需高表达力的图学习任务，如分子性质预测
我们研究了具有随机节点特征的消息传递图神经网络。随机节点特征已被证明在理论和实证上都能提升图神经网络（GNN）的表达力。本文建立了一个新的通用性结果，聚焦于置换等变神经网络（PENNs），这类GNN由前馈神经网络组件构成，包含许多主流GNN架构。我们证明，结合部分随机节点特征的PENNs，能够以概率任意逼近任意可测的置换不变或置换等变函数，定义在具有多维节点和边特征的固定大小有向图上。对于k次连续可微函数（k≥2），我们还推导出逼近速率的上界，将PENN前馈组件的复杂度（层深与非零权重数）与期望逼近精度关联起来。
原文摘要 · Abstract (English)
We investigate message-passing graph neural networks with random node features. Random node features are known to enhance the expressiveness of graph neural networks (GNNs) both theoretically and empirically. Here, we establish a novel universality result focusing on permutation-equivariant neural networks (PENNs), a class of GNNs built from feedforward neural network components that subsumes many prominent GNN architectures. We show that PENNs, combined with partially random node features, can approximate arbitrarily well in probability any measurable permutation-invariant or permutation-equivariant function on directed graphs of fixed size with multidimensional node and edge features. For $k$-times continuously differentiable functions, $k\geq 2$, we also derive upper bounds on the approximation rates, relating the complexity of the feedforward components of a PENN in terms of layer depth and number of nonzero weights to the desired approximation accuracy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。