Pith. sign in

REVIEW 4 minor 16 references

Universality and Approximation Rates of Graph Neural Networks with Random Features

T0 review · 0 major / 4 minor · reviewed 2026-07-30 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Message-passing networks with random node features can approximate any measurable permutation-equivariant or invariant function on fixed-size directed graphs.

desk verdict Clean, broader universality theorem for PENNs with random features plus rates; fixed-N scope is explicit and the proofs hold inside it. read the letter →

arxiv 2607.26699 v1 pith:5TDM332S submitted 2026-07-29 cs.LG stat.ML

Lukas Gonon , Thilo Meyer-Brandis , Niklas Weber This is my paper
classification cs.LGstat.ML
keywords graphneuralnetworkedgefeatureuniversalapproximationraterandompermutationequivariancemessagepassing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Standard message-passing graph networks cannot tell certain non-isomorphic graphs apart, because each node only sees its local neighborhood. This paper shows that a broad family of such networks, called permutation-equivariant neural networks (PENNs), becomes universal once node features are partly replaced by random features that almost surely give every node a unique label. With those features, a PENN can approximate any measurable permutation-equivariant or invariant target on directed graphs of fixed size, with multi-dimensional node and edge features, to any accuracy with arbitrarily high probability. For smooth targets the same construction also supplies explicit upper bounds: the depth of the feedforward pieces grows only logarithmically with the desired accuracy, while the number of nonzero weights grows like a power of one over the error. The result covers many popular architectures and suggests that simple random-feature message passing is already a strong baseline for graph learning.

What carries the argument

The PENN message-passing template (four feedforward maps ρ, ϕ, α, ψ that combine local and global sums) together with the representation theorem that every measurable equivariant map equals such a composition on any set of graphs that already has finite unique node features; random features then place the input into that set with high probability, after which ordinary feedforward universality finishes the argument.

What would settle it

Exhibit a measurable permutation-equivariant function on fixed-size directed graphs, and a distribution of random features that still supplies unique node IDs with high probability, such that no choice of the four feedforward maps can drive the failure probability below a fixed positive constant.

Watch

Extended reading notes

Core claim

PENNs built from ordinary feedforward networks, when their node features are concatenated with random features that supply finite unique node identifiers with high probability, can approximate any measurable permutation-equivariant (or invariant) function on the space of directed graphs of fixed size N with multi-dimensional node and edge features, arbitrarily well in probability. For C^k targets with k ≥ 2 the same networks also achieve concrete approximation rates that bound layer depth and number of nonzero weights in terms of the error tolerance.

Load-bearing premise

The number of nodes N is fixed in advance, and the random features must succeed in giving every node a distinct finite identifier; if either fails, the reduction to ordinary neural-network approximation does not go through.

Editorial extensions

If this is right

  • Many common message-passing layers (GCN, GIN, SAGE, GAT, NNConv, GraphConv) inherit the same universality once random features are added.
  • Averaging a PENN over several independent draws of the random features remains universal while restoring equivariance in expectation, offering a practical regularizer against overfitting to the random IDs.
  • For smooth targets the required network depth scales only as log(1/ε), so depth need not explode with accuracy.
  • The weight-count bound still suffers a polynomial curse of dimensionality in the feature dimensions, but the exponent improves with higher smoothness k.
  • PENNs with random features become a theoretically justified baseline against which higher-order or more expensive GNN architectures can be compared.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the proof never uses more than 1-hop neighborhoods, the same rates should extend immediately to multi-layer compositions of PENNs without changing the asymptotic dependence on ε.
  • The fixed-N assumption suggests a natural next question: whether a uniform-in-N architecture family can be obtained by letting the ID alphabet and the hidden widths grow slowly with N.
  • The almost-sure version that uses fixed unique identifiers (rather than i.i.d. noise) may be preferable in settings such as financial networks where node identities are already known and stable.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper proves that permutation-equivariant neural networks (PENNs)—message-passing GNNs whose aggregate/combine/readout blocks are feedforward nets—augmented with random node features that supply finite unique IDs with high probability, are universal approximators in probability of any measurable permutation-equivariant (or invariant) map on directed graphs of fixed size N with multi-dimensional node and edge features (Theorem 9, Corollary 14). The same holds for averages over i.i.d. copies of the random features (Theorem 16), which restores equivariance in expectation. For C^k targets (k≥2) on the unit cube the authors further give explicit upper bounds on the depth and number of nonzero weights of the FNN components needed to achieve uniform error ε with probability 1-δ (Theorem 18). The argument reduces the problem, via a measurable encoding of the whole graph into fixed-size tensors indexed by a measurable ID map (Proposition 20), to classical FNN universality in probability and known ReLU approximation rates.

Significance. The result substantially strengthens existing random-feature universality statements (Abboud et al., Puny et al.) by treating measurable rather than continuous targets, directed graphs, multi-dimensional node and edge features, both equivariant and invariant maps, and a concrete architecture class that already covers GCN, GIN, GAT, SAGE, etc. The quantitative rates and the averaged-model construction that mitigates the loss of pathwise equivariance are new and practically relevant. Within the stated fixed-N setting the proofs are complete and self-contained; the paper therefore supplies a clean theoretical baseline for random-feature message-passing models.

minor comments (4)
  1. [§5, Remark 38] The dependence of the rate constants c1,c2 on N,d,d′,δ (Remark 38 and Eq. (30)) is left somewhat opaque; a short explicit display of the leading-order scaling in N would help readers assess the curse of dimensionality.
  2. [Appendix D] Appendix D illustrations are helpful but the captions are lengthy; a single sentence stating the precise claim each figure supports would improve readability.
  3. A few typographical inconsistencies appear (e.g., “F eatures”, spacing around | | concatenation). A light copy-edit pass would remove them.
  4. [§3.1] The paper cites the authors’ own 2026 SIAM J. Financial Math. work for the PENN definition; a one-sentence reminder of how Definition 1 differs from the earlier version would aid readers who have not seen that paper.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: standard reduction from unique IDs through message-passing representation to classical FNN universality

full rationale

The load-bearing chain is: (i) random features that disambiguate nodes w.h.p. (Def. 3, Lem. 6); (ii) Prop. 20, proved in full here, constructs measurable ρ,α,ϕ,ψ so that any measurable equivariant f equals a fixed message-passing form on any set with finite unique node features; (iii) Prop. 21 invokes classical FNN universality in probability (external: Biagini et al., Leshno/Cybenko/Hornik) to replace those maps by networks; (iv) Thm. 9 combines (i)–(iii). Rate bounds (Thm. 18) likewise smooth indicators (Lem. 33), bound derivatives independently of f (Prop. 35), and apply external ReLU rates (Gühring et al.). Self-citations (Gonon et al. 2026) only supply the PENN architecture definition and motivation; Prop. 20 extends their earlier representation but is self-contained. No fitted parameters, no prediction-equals-fit loop, no uniqueness theorem imported as external fact, no ansatz smuggled by citation. Fixed-N and disambiguating-h hypotheses are stated explicitly, not hidden. Derivation is independent of its inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

The result rests on classical FNN universal approximation and modern ReLU rate theorems, the definition of PENNs as a message-passing template, and the modeling choice that random features supply finite unique node IDs with high probability on a fixed-N domain. No free parameters are fitted. Invented entities are architectural definitions, not physical postulates.

assumptions (5)
  • standard math Feedforward nets with nonconstant bounded activations approximate measurable functions in probability (Prop. 24 / Biagini et al.; classical Cybenko–Hornik–Leshno line).
    Used in Prop. 21 to replace measurable ρ,α,ϕ,ψ by FNNs inside the PENN template.
  • standard math ReLU networks achieve the Gühring et al. (2020) approximation rates in W^{s,p} for Sobolev balls on (0,1)^d (Prop. 29 / Cor. 31).
    Load-bearing for the depth and weight bounds in Theorem 18 and Prop. 37.
  • domain assumption Target functions are permutation-equivariant or invariant; graphs have fixed node count N and no self-loops; features may be multi-dimensional.
    Stated in §2; fixed N is essential for the finite-ID encoding and for rates on D^{[0,1]}_{N,d,d′}.
  • domain assumption Random features provide finite unique node features almost surely or with high probability (Def. 3), e.g. i.i.d. Uniform[0,1] (Lemma 6) or deterministic unique IDs.
    Necessary for Prop. 20’s reconstruction; without disambiguation the 1-WL barrier remains.
  • ad hoc to paper PENN message-passing form (Def. 1) with FNN components ρ,ϕ,α,ψ is the architecture class under study and subsumes common MP layers (Remark 2).
    Architecture choice from Herzig/Gonon et al.; universality is proved for this class, not for arbitrary GNNs.
invented entities (2)
  • PENN (permutation-equivariant neural network) template independent evidence
    purpose: Concrete GNN class with two neighborhood aggregations plus global readout built from FNNs, for which universality and rates are proved.
    Named architecture extending Herzig et al. / Gonon et al.; not a physical entity. Independent evidence is definitional coverage of GCN, GIN, GAT, etc. in Remark 2.
  • Finite unique node features (Defs. 3–5) independent evidence
    purpose: Abstract condition on random or deterministic IDs that enables the Prop. 20 representation.
    Unifies i.i.d. random features and unique node identifiers under one measurable condition used throughout.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Universality and Approximation Rates of Graph Neural Networks with Random Features." pith.science (2026). https://pith.science/paper/5TDM332S

@misc{pith2026260726699,
  author       = {Pith},
  title        = {Pith review of: Universality and Approximation Rates of Graph Neural Networks with Random Features},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5TDM332S}},
  note         = {Machine review of arXiv:2607.26699}
}
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.

Figures

Figures reproduced from arXiv: 2607.26699 by the authors.

Figure 1
Figure 1. Two non-isomorphic graphs that cannot be distinguished by message-passing (AC) graph neural networks because all nodes of type a and all nodes of type b are “tree-like equivalent”. Therefore, starting with identical node features ra, rb ∈ R d , all nodes of type a (and all nodes of type b) can never end up with different node labels by means of traditional message-passing. structure (each type-a node is connected to… view at source ↗
Figure 2
Figure 2. Two pairs of graphs that highlight the necessity of additional expressive power via global readout functions or random node features. r2 r3 r4 r5 r1 r6 r2 r3 r4 r5 r1 r6 (a) The graphs from [PITH_FULL_IMAGE:figures/full_fig_p053_2.png] view at source ↗
Figure 3
Figure 3. Assigning random features to the nodes ensures that the neighborhoods for the nodes in the graphs from [PITH_FULL_IMAGE:figures/full_fig_p053_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

16 extracted references · 1 canonical work pages

  1. [1]

    The sur- prising power of graph neural networks with random node initialization.arXiv preprint arXiv:2010.01179,

    Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The sur- prising power of graph neural networks with random node initialization.arXiv preprint arXiv:2010.01179,

    arXiv 2010

  2. [10]

    What graph neural networks cannot learn: depth vs width.arXiv preprint arXiv:1907.03199,

    Andreas Loukas. What graph neural networks cannot learn: depth vs width.arXiv preprint arXiv:1907.03199,

    arXiv 1907

  3. [12]

    Global attention improves graph networks generalization.arXiv preprint arXiv:2006.07846,

    Omri Puny, Heli Ben-Hamu, and Yaron Lipman. Global attention improves graph networks generalization.arXiv preprint arXiv:2006.07846,

    arXiv 2006

  4. [14]

    Graph attention networks.arXiv preprint arXiv:1710.10903,

    Petar Veliˇ ckovi´ c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks.arXiv preprint arXiv:1710.10903,

    arXiv

  5. [16]

    How powerful are graph neural networks?arXiv preprint arXiv:1810.00826,

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?arXiv preprint arXiv:1810.00826,

    arXiv

  6. [1989]

    Coloring graph neural networks for node disambiguation.arXiv preprint arXiv:1912.06058,

    George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation.arXiv preprint arXiv:1912.06058,

    arXiv 1912

  7. [1993]

    Relational inductive biases, deep learning, and graph networks.arXiv preprint arXiv:1806.01261,

    Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks.arXiv preprint arXiv:1806.01261,

    arXiv

  8. [2011]

    Graph positional and structural encoder

    Semih Cant¨ urk, Renming Liu, Olivier Lapointe-Gagn´ e, Vincent L´ etourneau, Guy Wolf, Dominique Beaini, and Ladislav Ramp´ aˇ sek. Graph positional and structural encoder. arXiv preprint arXiv:2307.07107,

    arXiv

Show all 16 references
  1. [2013]

    Invariant and equiv- ariant graph networks.arXiv preprint arXiv:1812.09902,

    Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equiv- ariant graph networks.arXiv preprint arXiv:1812.09902,

    arXiv

  2. [2017]

    Temporal-aware graph neural network for credit risk prediction

    Daixin Wang, Zhiqiang Zhang, Jun Zhou, Peng Cui, Jingli Fang, Quanhui Jia, Yanming Fang, and Yuan Qi. Temporal-aware graph neural network for credit risk prediction. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 702–710. SIAM, 2021a. Jian...

    2021 arXiv

  3. [2018]

    On the utilization of unique node identifiers in graph neural networks

    Maya Bechler-Speicher, Moshe Eliasof, Carola-Bibiane Sch¨ onlieb, Ran Gilad-Bachrach, and Amir Globerson. On the utilization of unique node identifiers in graph neural networks. arXiv preprint arXiv:2411.02271,

    arXiv

  4. [2019]

    Semi-supervised classification with graph convolutional networks.arXiv preprint arXiv:1609.02907,

    Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks.arXiv preprint arXiv:1609.02907,

    arXiv

  5. [2020]

    The logical expressiveness of graph neural networks

    Pablo Barcel´ o, Egor V Kostylev, Mikael Monet, Jorge P´ erez, Juan Reutter, and Juan- Pablo Silva. The logical expressiveness of graph neural networks. In8th International Conference on Learning Representations (ICLR 2020),

    2020

  6. [2023]

    Fast graph representation learning with pytorch geo- metric.arXiv preprint arXiv:1903.02428,

    Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geo- metric.arXiv preprint arXiv:1903.02428,

    1903 arXiv

  7. [2024]

    Random features strengthen graph neural networks

    Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. InProceedings of the 2021 SIAM international conference on data mining (SDM), pages 333–341. SIAM,

    2021

  8. [2026]

    URLhttps://doi.org/10.1137/24M1697402

    doi: 10.1137/24M1697402. URLhttps://doi.org/10.1137/24M1697402. Ingo G¨ uhring, Gitta Kutyniok, and Philipp Petersen. Error bounds for approximations with deep relu neural networks in w s, p norms.Analysis and Applications, 18(05):803–859,

    doi

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.