← Back to all news
arXiv Machine Learning

The Expressive Power of Random-Feature MPNNs Across Graph Sizes

The paper investigates how continuous random node features affect the expressivity of message‑passing neural networks (MPNNs). It introduces a population‑level framework for size‑uniform approximation, showing that continuous random features can be quantized to finitely many colors with negligible error, allowing transfer of finite‑color distinguishability limits to size‑uniform approximation. The authors prove that such MPNNs are not size‑uniformly universal, analyze expressivity gains from colors and independent trials, establish incomparability with higher‑order Weisfeiler‑Leman methods, and provide finite‑color MPNN constructions for tree subgraph isomorphism and a local minimum spanning tree task.

Related stories

arXiv Machine Learning
Jun 30

Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

arXiv:2603. 14846v3 Announce Type: replace Abstract: We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (MP-GNN) model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is super-exponential (in number of vertices).

By Eran Rosenbluth
More like this →
arXiv AI
Aug 25

Which Algorithms Can Graph Neural Networks Learn?

arXiv:2602.13106v2 Announce Type: replace-cross Abstract: In recent years, there has been growing interest in understanding neural architectures' ability to learn to execute discrete algorithms, a li...

By Solveig Wittig, Antonis Vasileiou, Robert R. Nerem, Timo Stoll, Floris Geerts, Yusu Wang, Christopher Morris
efficiency
More like this →
arXiv Statistics ML
Oct 2

Transferable Graph Metanetworks

Transferable Graph Metanetworks extend the graph metanetwork paradigm to predict properties of neural networks of varying widths. By enforcing invariance to width-dependent representations and continuity across similar functions, the proposed modifications enable robust size generalization, especially for networks trained under the maximal‑update parameterization (μP) up to 42× the training width. The authors provide empirical evidence across multiple tasks and theoretical guarantees in the infinite‑width limit, explaining both successes and limitations under different parameterizations.

By Yuxin Ma, Adir Dayan, Yam Eitan, Haggai Maron, Soledad Villar
More like this →
arXiv Statistics ML
Oct 28

Graph Representation Learning via Adaptive Expectile Aggregation

Graph Representation Learning via Adaptive Expectile Aggregation introduces ExpectileGCN, a graph neural network framework that learns an expectile level to adaptively aggregate neighborhood information beyond simple mean pooling. The method smoothly interpolates between minimum- and maximum-type behaviors, with mean aggregation as a special case, and employs a differentiable sigmoid‑based approximation for end‑to‑end training. The authors provide theoretical stability and generalization guarantees, analyze classification risk under heterophilic settings, and demonstrate improved performance and robustness on both homophilic and heterophilic benchmark graphs.

By Tianyi Zhu, Wei Lan
benchmarks
More like this →
arXiv Machine Learning
Jul 9

Any-Dimensional Learning by Sampling

arXiv:2607. 07680v1 Announce Type: cross Abstract: Many machine learning models are defined for inputs of different sizes, such as point clouds containing different numbers of points, sequences of tokens of different lengths, and graphs on different numbers of nodes.

By Eitan Levin, Venkat Chandrasekaran
llms
More like this →