Universality and Approximation Rates of Graph Neural Networks with Random Features

AI 中文解读

核心亮点：研究者给图神经网络加入了“随机特征”，证明了这种方法能让模型拥有逼近任何复杂关系模式的强大能力，为AI处理网状结构数据打开了新天花板。通俗解读：图神经网络是一种专门分析“关系网”的AI，比如社交网络中的好友关系、分子中的原子连接。以前，它处理固定模式时表现不错，但遇到更复杂、不规则的网络关系就力不从心。这项新研究相当于给AI的每个节点悄悄加了一些随机数字，就像给网络“点了穴”，反而激发了它看穿所有可能关系的能力。科学家严格证明，只要配上合适的“随机特征”，这类神经网络就能无限逼近任何需要对称或交换视角的函数，而且计算复杂度和精度之间还有明确的数学关系。实际影响：这意味着未来推荐系统能更精准地猜你喜欢（比如从购物关系中发现隐藏关联），药物研发可以更高效地模拟分子结构，甚至交通预测也能更准地分析路网拥堵。普通用户可能感觉不到AI变强了，但背后处理图数据的应用会变得更聪明、更可靠。

arXiv:2607.26699v1 Announce Type: new Abstract: 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.