arXiv：cs.LG· Robert R. Nerem, Mitchell Black, Antonis Vasileiou, Christopher Morris, Yusu Wang·· 11 小时前
随机特征 MPNN 跨图规模的表达能力研究
The Expressive Power of Random-Feature MPNNs Across Graph Sizes
AI 导读
研究提出一个群体级框架，用于分析随机特征消息传递神经网络（MPNN）的规模一致逼近能力，证明在初始特征具有与图规模无关的 Lipschitz 界时，连续随机特征可量化为有限颜色且误差任意小。
正文
Abstract:Continuous random node features increase the expressivity of message-passing neural networks (MPNNs), but existing theoretical analyses are not fine-grained enough to capture their limitations, particularly in approximating functions across graph sizes or under a fixed number of random bits. We develop a population-level framework for size-uniform approximation. For MPNNs with a graph-size-independent Lipschitz bound in their initial features, including standard mean, max, and order-normalized sum architectures, we show that continuous random features can be quantized to finitely many colors with arbitrarily small uniform error in expected output. This reduction lets us transfer limitations on finite-color distinguishability to limitations on size-uniform approximation with continuous random features. We use this framework to prove that these MPNNs are not size-uniformly universal, analyze the expressivity gains from colors and independent trials, and establish incomparability between random-color MPNNs and higher-order Weisfeiler-Leman methods. We also give finite-color MPNN constructions for tree subgraph isomorphism via color coding and a local MST task.
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.12809 [cs.LG] |
| (or arXiv:2610.12809v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.12809 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Robert Nerem [view email]
[v1]
Thu, 8 Oct 2026 23:38:47 UTC (114 KB)
来源：arXiv：cs.LG · arxiv.org