随机特征 MPNN 在不同图规模下的表达能力

# 1Introduction
Source: [https://arxiv.org/html/2610.12809](https://arxiv.org/html/2610.12809)
The Expressive Power of Random\-Feature MPNNs Across Graph Sizes

Robert R\. Nerem1Mitchell Black111Work initiated while at University of California San Diego\.Antonis Vasileiou2Christopher Morris2Yusu Wang11University of California, San Diego2Rheinisch Westfälische Technische Hochschule Aachen

###### 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\.

## 1Introduction

Message\-passing graph neural networks \(MPNNs\)\[[25](https://arxiv.org/html/2610.12809#bib.bib25),[8](https://arxiv.org/html/2610.12809#bib.bib8)\]are widely used to learn functions on graphs, but their expressive power is limited by symmetries that message passing cannot break\[[31](https://arxiv.org/html/2610.12809#bib.bib31),[18](https://arxiv.org/html/2610.12809#bib.bib18)\]\. Random node features provide a powerful way to break these symmetries\[[6](https://arxiv.org/html/2610.12809#bib.bib6),[24](https://arxiv.org/html/2610.12809#bib.bib24),[1](https://arxiv.org/html/2610.12809#bib.bib1),[10](https://arxiv.org/html/2610.12809#bib.bib10)\]\. Specifically, continuous random features almost surely give every vertex a unique identifier, enabling universality at any fixed graph size\[[1](https://arxiv.org/html/2610.12809#bib.bib1)\]\. However, these constructions require unbounded precision as graphs grow and do not guarantee that a fixed model can approximate a target uniformly across graph sizes\. In practice, we want a trained model to handle larger graphs with a fixed architecture, parameters, and precision\. This motivates studying size\-uniform approximation, as well as how expressive power depends on the number of random bits per vertex\.

Representing the same function across graph sizes is a prerequisite for size generalization, which aims to maintain performance on graphs larger than those seen during training\[[34](https://arxiv.org/html/2610.12809#bib.bib34),[32](https://arxiv.org/html/2610.12809#bib.bib32),[19](https://arxiv.org/html/2610.12809#bib.bib19)\]\. This is essential for learned graph algorithms, particularly in combinatorial optimization, where larger instances may be too expensive to label for training\. Neural algorithmic reasoning pursues this goal through inductive biases that favor algorithmic behavior\[[28](https://arxiv.org/html/2610.12809#bib.bib28),[27](https://arxiv.org/html/2610.12809#bib.bib27)\]\. Such biases, however, cannot yield size generalization if the model class cannot represent a computation across graph sizes\. Recent work gives conditions for size\-generalization guarantees\[[19](https://arxiv.org/html/2610.12809#bib.bib19),[30](https://arxiv.org/html/2610.12809#bib.bib30)\]\. Related work studies uniform expressivity for graph transformers and virtual\-node MPNNs\[[22](https://arxiv.org/html/2610.12809#bib.bib22)\], universality for transformers over arbitrarily many context tokens\[[7](https://arxiv.org/html/2610.12809#bib.bib7)\], and any\-dimensional invariant universality\[[15](https://arxiv.org/html/2610.12809#bib.bib15),[33](https://arxiv.org/html/2610.12809#bib.bib33)\]\.

We ask which invariant graph functions a random\-feature MPNN can approximate uniformly across graph sizes\. To obtain deterministic predictions invariant under vertex relabeling, we consider the expected output over random initializations\. LetT:𝒢→ℝT\\colon\\mathcal\{G\}\\to\\mathbb\{R\}be an invariant target function, writeF¯​\(G\)≔𝔼⁡\[F^s​\(G\)\]\\overline\{F\}\(G\)\\coloneq\\mathbb\{E\}\[\\widehat\{F\}\_\{s\}\(G\)\]for the population predictor, and set𝒢N≔\{G∈𝒢:\|V⁡\(G\)\|=N\}\\mathcal\{G\}\_\{N\}\\coloneq\\\{G\\in\\mathcal\{G\}\\colon\|V\(G\)\|=N\\\}\.*Fixed\-size approximation*allows anNN\-dependent predictorFNF\_\{N\}withsupG∈𝒢N\|F¯N​\(G\)−T⁡\(G\)\|≤ε\\sup\_\{G\\in\\mathcal\{G\}\_\{N\}\}\|\\overline\{F\}\_\{N\}\(G\)\-T\(G\)\|\\leq\\varepsilonwhile*size\-uniform approximation*instead requires one predictorFF, independent ofNN, withsupG∈𝒢\|F¯​\(G\)−T⁡\(G\)\|≤ε\\sup\_\{G\\in\\mathcal\{G\}\}\|\\overline\{F\}\(G\)\-T\(G\)\|\\leq\\varepsilon\.

Previous work establishes universality for random\-feature MPNNs\[[1](https://arxiv.org/html/2610.12809#bib.bib1)\]and gives specific algorithmic constructions\[[24](https://arxiv.org/html/2610.12809#bib.bib24),[12](https://arxiv.org/html/2610.12809#bib.bib12)\], but does not characterize how expressive power depends on the number of random bits per node feature and the number of independent evaluations\. We develop a framework that quantifies these dependencies and identifies graph pairs that cannot be reliably distinguished with limited resources\. Building on expectation\-based analyses of randomized GNNs\[[13](https://arxiv.org/html/2610.12809#bib.bib13),[12](https://arxiv.org/html/2610.12809#bib.bib12),[11](https://arxiv.org/html/2610.12809#bib.bib11)\], we study the functions these models represent in expectation and estimate them by averaging independent evaluations\. This lets us use the same notions of approximation and distinguishability as for deterministic architectures\[[31](https://arxiv.org/html/2610.12809#bib.bib31),[18](https://arxiv.org/html/2610.12809#bib.bib18)\], while accounting for their statistical nature\. In particular, we develop WL\-based combinatorial bounds on distinguishability that translate into limitations on expected approximation\.

We study size\-uniform approximation for MPNNs with a size\-independent Lipschitz constant in the initial random features\. This covers mean, max, and order\-normalized sum aggregation, as well as unnormalized sums on bounded\-degree graphs, and matches the regime of the size\-generalization results of[Wittig et al\. \[30\]](https://arxiv.org/html/2610.12809#bib.bib30)\. It also prevents models from extracting increasingly detailed node identities from vanishing numerical differences\.

Random featuresFinite random colors𝝃v​∼i\.i\.d\.​ρK\\bm\{\\xi\}\_\{v\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}\\rho\_\{K\}QS​𝝃G∈SV⁡\(G\)Q\_\{S\}\\bm\{\\xi\}^\{G\}\\in S^\{V\(G\)\}feature spaceKKfinite paletteSSnodewise quantizationQSQ\_\{S\}‖𝝃G−QS​𝝃G‖in≤δ⁡\(S\)\\\|\\bm\{\\xi\}^\{G\}\-Q\_\{S\}\\bm\{\\xi\}^\{G\}\\\|\_\{\\mathrm\{in\}\}\\leq\\delta\(S\)same uniformlyLL\-Lipschitz MPNNFF\|F⁡\(G,𝝃G\)−F⁡\(G,QS​𝝃G\)\|≤L​δ​\(S\)\\displaystyle\\bigl\|F\(G,\\bm\{\\xi\}^\{G\}\)\-F\(G,Q\_\{S\}\\bm\{\\xi\}^\{G\}\)\\bigr\|\\leq L\\delta\(S\)take expectationsSize\-uniformpopulation boundsupG∈𝒢\|F¯​\(G\)−F¯S​\(G\)\|≤L​δ​\(S\)\\displaystyle\\sup\_\{G\\in\\mathcal\{G\}\}\\bigl\|\\overline\{F\}\(G\)\-\\overline\{F\}\_\{S\}\(G\)\\bigr\|\\leq L\\delta\(S\)\|S\|\|S\|colors,independent of graph size

Figure 1:Overview of our random\-feature MPNN framework\.Size\-uniform quantization with a finite paletteS⊂KS\\subset K\. Here\(QS​𝒙\)v=qS​\(𝒙v\)\(Q\_\{S\}\\bm\{x\}\)\_\{v\}=q\_\{S\}\(\\bm\{x\}\_\{v\}\),δ⁡\(S\)=sup𝒛∈K‖𝒛−qS​\(𝒛\)‖\\delta\(S\)=\\sup\_\{\\bm\{z\}\\in K\}\\\|\\bm\{z\}\-q\_\{S\}\(\\bm\{z\}\)\\\|, andF¯S​\(G\)=𝔼⁡\[F⁡\(G,QS​𝝃G\)\]\\overline\{F\}\_\{S\}\(G\)=\\mathbb\{E\}\[F\(G,Q\_\{S\}\\bm\{\\xi\}^\{G\}\)\]\. Both branches use the same MPNN and coupled initializations\.#### Our work

Our central reduction shows that, for uniformly Lipschitz MPNNs, continuous random features can be replaced by random features taking finitely many values \(which we call random colors drawn from a palette\), with arbitrarily small uniform error in expected output\. Hence, every invariant function approximable size\-uniformly by a finite\-dimensional continuous\-random\-feature MPNN is also size\-uniformly approximable by a random\-color MPNN\. The palette size may depend on the target, accuracy, and model, but not on graph size\. Continuous precision is thereby reduced to two discrete resources, the number of colorsqqand the number of independent trialsss; see[Figure1](https://arxiv.org/html/2610.12809#S1.F1)for an overview\.

Using CFI graph families\[[4](https://arxiv.org/html/2610.12809#bib.bib4)\], we construct an invariant target that no uniformly Lipschitz random\-feature MPNN can approximate uniformly across sizes, even on graphs of bounded diameter\. The correspondingnn\-vertex pairs are separated by*\(folklore\)22\-dimensional Weisfeiler–Leman*\(22\-WL\)\. A random\-color MPNN usingqqcolors requires at leastssindependent trials per graph to distinguish them with success probability at least2/32/3, whereq10​log⁡\(3​s\)=Ω⁡\(n\)q^\{10\}\\log\(3s\)=\\Omega\(n\)\. Thus, additional colors can be exponentially more effective than additional trials on these instances\. In addition, random\-color MPNNs and*higher\-orderkk\-dimensional Weisfeiler–Leman*\(kk\-WL\) are also incomparable, i\.e\., for every fixedkk, a two\-color, one\-trial MPNN separates a pair thatkk\-WL does not, while for every fixed palette and trial budget,22\-WL separates a pair that the random\-color model does not\.

Finite colors nevertheless support useful size\-uniform computations, including color coding for fixed\-tree subgraph detection\[[2](https://arxiv.org/html/2610.12809#bib.bib2)\]and a local MST edge task\. Building on[Wittig et al\. \[30\]](https://arxiv.org/html/2610.12809#bib.bib30), a randomized finite\-cover argument then links the represented function class to size\-generalization guarantees\.

#### Contributions

In summary, our main contributions are as follows\.

1. 1\.*Framework for randomized expressivity\.*We develop a population\-level framework for random\-feature MPNNs, allowing their expressive power to be studied through invariant function approximation, graph distinguishability, and comparisons with the Weisfeiler–Leman hierarchy \(Section[2](https://arxiv.org/html/2610.12809#S2)\)\.
2. 2\.*Size\-uniform characterization\.*We reduce continuous random features to discrete random features \(Theorem[3](https://arxiv.org/html/2610.12809#Thmtheorem3)and Corollary[4](https://arxiv.org/html/2610.12809#Thmtheorem4)\) and prove that random\-feature MPNNs are not size\-uniformly universal \(Corollary[6](https://arxiv.org/html/2610.12809#Thmtheorem6)\)\.
3. 3\.*Expressivity results\.*We establish strict color and trial hierarchies for statistical distinguishability by random\-color WL \(Theorem[7](https://arxiv.org/html/2610.12809#Thmtheorem7)\), quantify their tradeoff using CFI graphs \(Theorem[5](https://arxiv.org/html/2610.12809#Thmtheorem5)\), and prove incomparability with higher\-order Weisfeiler–Leman \(Theorem[8](https://arxiv.org/html/2610.12809#Thmtheorem8)\)\.
4. 4\.*Scalable computation and learning\.*We give finite\-color constructions for structural algorithms \(Theorem[9](https://arxiv.org/html/2610.12809#Thmtheorem9)and Proposition[10](https://arxiv.org/html/2610.12809#Thmtheorem10)\), and give sufficient conditions for size\-uniform generalization from a suitable finite training set \(Theorem[11](https://arxiv.org/html/2610.12809#Thmtheorem11)\)\.

#### Related work

Loukas\[[16](https://arxiv.org/html/2610.12809#bib.bib16)\]showed that MPNNs equipped with unique node identifiers, sufficiently expressive message and update functions, and sufficient depth and width can simulate arbitrary distributed computations and, in particular, are Turing complete\. Vignac et al\.\[[29](https://arxiv.org/html/2610.12809#bib.bib29)\]incorporated one\-hot node identifiers into an equivariant structural message\-passing architecture, making the resulting representation independent of the particular identifier assignment\.

Randomization offers another route to individualization\. Dasoulas et al\.\[[6](https://arxiv.org/html/2610.12809#bib.bib6)\]showed that random node colorings can break symmetries and substantially strengthen MPNNs, while Sato et al\.\[[24](https://arxiv.org/html/2610.12809#bib.bib24)\]demonstrated that random features enable MPNNs to simulate randomized local algorithms and improve approximation guarantees for combinatorial optimization problems\. Rosenbluth et al\.\[[21](https://arxiv.org/html/2610.12809#bib.bib21)\]showed that a recurrent GNN with random vertex features can simulate any polynomial\-time graph algorithm on connected graphs in polynomial time\. GNNs with random node initialization are universal approximators for invariant graph functions on fixed\-size graph domains\[[1](https://arxiv.org/html/2610.12809#bib.bib1),[9](https://arxiv.org/html/2610.12809#bib.bib9)\]\. Pellizzoni et al\.\[[20](https://arxiv.org/html/2610.12809#bib.bib20)\]subsequently analyzed both the expressivity and statistical sample complexity of node\-individualized GNNs, establishing more favorable sample\-complexity bounds for permutation\-equivariant individualization schemes\.[Kanatsoulis and Ribeiro \[13\]](https://arxiv.org/html/2610.12809#bib.bib13),[Kanatsoulis and Ribeiro \[12\]](https://arxiv.org/html/2610.12809#bib.bib12)proved that MPNNs with random features could compute graph properties that standard MPNNs could not, showing that random features can overcome the expressivity limitations of anonymous message passing\[[31](https://arxiv.org/html/2610.12809#bib.bib31)\]by acting as probabilistic node identifiers\. Their guarantees, however, primarily concern fixed\-size expressivity or approximation on bounded graph domains and do not characterize when symmetry breaking yields a scalable algorithmic representation that transfers across graph sizes\.

## 2Formal Framework

Here, we outline our framework for analyzing MPNNs with random node features\. We study the invariant function defined by a model’s expected output and ask whether a fixed model can approximate a target uniformly over graph sizes\. To control the precision required of the random features, we impose a graph\-size\-independent Lipschitz bound on the output with respect to the initial features\. We then connect population approximation to statistical graph distinguishability using finite color palettes and independent trials\.

### 2\.1Randomized MPNNs

Let𝒢\\mathcal\{G\}be a class of finite graphs and letK⊂ℝdK\\subset\\mathbb\{R\}^\{d\}be a compact node\-feature space equipped with a probability distributionρK\\rho\_\{K\}\.

A depth\-DDMPNN initializes𝒉G\(0\)​\(v\)≔𝒙v∈ℝd\\bm\{h\}\_\{G\}^\{\(0\)\}\(v\)\\coloneq\\bm\{x\}\_\{v\}\\in\\mathbb\{R\}^\{d\},d\>0d\>0, and updates its representations forℓ∈\{0,…,D−1\}\\ell\\in\\\{0,\\ldots,D\-1\\\}according to

𝒎G\(ℓ\)​\(v\)\\displaystyle\\bm\{m\}\_\{G\}^\{\(\\ell\)\}\(v\)≔𝖠𝖦𝖦ℓ⁡\(\{\{𝒉G\(ℓ\)​\(u\):u∈NG​\(v\)\}\}\),\\displaystyle\\coloneq\\operatorname\{\\mathsf\{AGG\}\}\_\{\\ell\}\\\!\\left\(\\\{\\\!\\\{\\bm\{h\}\_\{G\}^\{\(\\ell\)\}\(u\)\\colon u\\in N\_\{G\}\(v\)\\\}\\\!\\\}\\right\),𝒉G\(ℓ\+1\)​\(v\)\\displaystyle\\bm\{h\}\_\{G\}^\{\(\\ell\+1\)\}\(v\)≔σ⁡\(𝑾self\(ℓ\)​𝒉G\(ℓ\)​\(v\)\+𝑾agg\(ℓ\)​𝒎G\(ℓ\)​\(v\)\+𝒃\(ℓ\)\),\\displaystyle\\coloneq\\sigma\\\!\\left\(\\bm\{W\}\_\{\\mathrm\{self\}\}^\{\(\\ell\)\}\\bm\{h\}\_\{G\}^\{\(\\ell\)\}\(v\)\\right\.\\left\.\{\}\+\\bm\{W\}\_\{\\mathrm\{agg\}\}^\{\(\\ell\)\}\\bm\{m\}\_\{G\}^\{\(\\ell\)\}\(v\)\+\\bm\{b\}^\{\(\\ell\)\}\\right\),whereσ\\sigmais coordinate\-wise ReLU and𝒃\(ℓ\)\\bm\{b\}^\{\(\\ell\)\}is a bias shared by all vertices\. We consider mean, max, min, and order\-normalized sum aggregation; the detailed hypothesis classes are specified in[SectionA\.2](https://arxiv.org/html/2610.12809#A1.SS2)\. A graph\-level MPNN applies a permutation\-invariant readout function𝖱𝖤𝖠𝖣𝖮𝖴𝖳\\operatorname\{\\mathsf\{READOUT\}\}to the final node representations to produce a scalar outputF⁡\(G,𝒙\)F\(G,\\bm\{x\}\), where𝒙=\(𝒙v\)v∈V⁡\(G\)\\bm\{x\}=\(\\bm\{x\}\_\{v\}\)\_\{v\\in V\(G\)\}denotes the collection of initial node features\.

ForG∈𝒢G\\in\\mathcal\{G\}, a random initialization assigns each vertex an independent random feature drawn fromρK\\rho\_\{K\},

𝝃G=\(𝝃v\)v∈V⁡\(G\),𝝃v​∼i\.i\.d\.​ρK\.\\bm\{\\xi\}^\{G\}=\(\\bm\{\\xi\}\_\{v\}\)\_\{v\\in V\(G\)\},\\qquad\\bm\{\\xi\}\_\{v\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}\\rho\_\{K\}\.The resulting random\-feature MPNN has outputF⁡\(G,𝝃G\)F\(G,\\bm\{\\xi\}^\{G\}\)\. When the support ofρK\\rho\_\{K\}comprises finitely many points, we call the corresponding random features*random colors*to emphasize their discrete nature, and we refer to the support as the palette\. An MPNN with such an initialization is called arandom\-color MPNN\. The color distribution need not be uniform\. We consider graphs that are not given node attributes as input and are instead assigned random attributes\. It is straightforward to extend our setting to graphs with input node attributes that are concatenated with the random initialization\.

### 2\.2Size\-uniform approximation

A single initialization produces a random output\. Taking its expectation gives a deterministic graph invariant whose approximation power we can analyze\. For a graph\-level MPNNFFwith fixed parameters, we write its population predictor as

F¯​\(G\)≔𝔼⁡\[F⁡\(G,𝝃G\)\]\.\\overline\{F\}\(G\)\\coloneq\\mathbb\{E\}\[F\(G,\\bm\{\\xi\}^\{G\}\)\]\.Size\-uniform approximation requires a single model to achieve the desired accuracy throughout the graph domain, including on arbitrarily large graphs when these belong to the domain\.

###### Definition 1\(Size\-uniform approximation\)\.

For a graph class𝒢\\mathcal\{G\}and a graph invariantTT, a classℱ\\mathcal\{F\}of random\-feature MPNNs uniformly approximatesTTif, for everyε\>0\\varepsilon\>0, there exists a singleF∈ℱF\\in\\mathcal\{F\}with

supG∈𝒢\|F¯​\(G\)−T⁡\(G\)\|≤ε\.\\sup\_\{G\\in\\mathcal\{G\}\}\|\\overline\{F\}\(G\)\-T\(G\)\|\\leq\\varepsilon\.In particular, if𝒢\\mathcal\{G\}contains graphs of arbitrarily large size, we call this approximation*size\-uniform*\. The classℱ\\mathcal\{F\}is a*size\-uniform universal approximator for graph invariants*if𝒢\\mathcal\{G\}contains all finite graphs and it uniformly approximates every graph invariantT:𝒢→ℝT\\colon\\mathcal\{G\}\\to\\mathbb\{R\}\.

To replace continuous features by finitely many colors, we need small nodewise perturbations to have a controlled effect on the output even as graphs grow\. We therefore require a Lipschitz bound that is independent of graph size\. Specifically, fix a norm∥⋅∥\\\|\\cdot\\\|onℝd\\mathbb\{R\}^\{d\}and use the max\-over\-nodes input norm‖𝒙‖in≔maxv∈V⁡\(G\)⁡‖𝒙v‖\.\\\|\\bm\{x\}\\\|\_\{\\mathrm\{in\}\}\\coloneq\\max\_\{v\\in V\(G\)\}\\\|\\bm\{x\}\_\{v\}\\\|\.This norm measures the largest perturbation at any vertex\.

###### Definition 2\(Uniform Lipschitzness\)\.

An MPNNFFis uniformlyLL\-Lipschitz with respect to∥⋅∥in\\\|\\cdot\\\|\_\{\\mathrm\{in\}\}if, for every graphGGand all𝐱,𝐱′∈KV⁡\(G\)\\bm\{x\},\\bm\{x\}^\{\\prime\}\\in K^\{V\(G\)\},

\|F⁡\(G,𝒙\)−F⁡\(G,𝒙′\)\|≤L​‖𝒙−𝒙′‖in\.\|F\(G,\\bm\{x\}\)\-F\(G,\\bm\{x\}^\{\\prime\}\)\|\\leq L\\\|\\bm\{x\}\-\\bm\{x\}^\{\\prime\}\\\|\_\{\\mathrm\{in\}\}\.

The same constantLLapplies to every graph\. Consequently, perturbing each initial feature by at mostδ\\deltachanges the output by at mostL​δL\\delta, independently of the number of vertices\. This is the stability property used in our quantization argument\. The following lemma shows that it holds for several standard MPNN architectures\.

###### Lemma 1\(Uniform Lipschitzness of standard MPNNs\)\.

For fixed depth, widths, and parameters, ReLU MPNNs with mean, max, min, or order\-normalized sum aggregation and mean pooling are uniformly Lipschitz\. The same holds for unnormalized sum aggregation on graph classes of bounded degree\.

The proof is given in[SectionA\.4](https://arxiv.org/html/2610.12809#A1.SS4)\.

### 2\.3Colors, trials, and distinguishability

The population predictor describes the function represented in expectation\. We next ask how reliably finitely many evaluations can estimate this function and reveal differences between graphs\.

We refer to a single evaluation with an independent random initialization as a*trial*\. For an MPNNFF, drawssindependent initializations𝝃1G,…,𝝃sG\\bm\{\\xi\}\_\{1\}^\{G\},\\ldots,\\bm\{\\xi\}\_\{s\}^\{G\}and define

F^s​\(G\)≔1s​∑i=1sF⁡\(G,𝝃iG\)\.\\widehat\{F\}\_\{s\}\(G\)\\coloneq\\frac\{1\}\{s\}\\sum\_\{i=1\}^\{s\}F\(G,\\bm\{\\xi\}\_\{i\}^\{G\}\)\.\(1\)Then𝔼⁡\[F^s​\(G\)\]=F¯​\(G\)\\mathbb\{E\}\[\\widehat\{F\}\_\{s\}\(G\)\]=\\overline\{F\}\(G\)for everyss, so the number of trials affects estimation but not the represented population function\.

Graph\-pair distinguishability connects this estimation problem to expressivity: approximating a target that takes different values on two graphs requires separating their population outputs\. We measure this separation by the population gapgapF⁡\(G,H\)≔\|F¯​\(G\)−F¯​\(H\)\|\\operatorname\{gap\}\_\{F\}\(G,H\)\\coloneq\|\\overline\{F\}\(G\)\-\\overline\{F\}\(H\)\|\. WriteDK≔sup𝒖,𝒖′∈K‖𝒖−𝒖′‖D\_\{K\}\\coloneq\\sup\_\{\\bm\{u\},\\bm\{u\}^\{\\prime\}\\in K\}\\\|\\bm\{u\}\-\\bm\{u\}^\{\\prime\}\\\|for the diameter of the feature space\.

For inputsA,B∈\{G,H\}A,B\\in\\\{G,H\\\}, compute empirical meansF^s​\(A\)\\widehat\{F\}\_\{s\}\(A\)andF^s′​\(B\)\\widehat\{F\}^\{\\prime\}\_\{s\}\(B\)from two independent batches ofs∈ℕs\\in\\mathbb\{N\}trials, even whenA=BA=B\. For a marginΔ\>0\\Delta\>0, the test ofH0:A=BH\_\{0\}\\colon A=BagainstH1:A≠BH\_\{1\}\\colon A\\neq BrejectsH0H\_\{0\}when\|F^s​\(A\)−F^s′​\(B\)\|\>Δ/2\|\\widehat\{F\}\_\{s\}\(A\)\-\\widehat\{F\}^\{\\prime\}\_\{s\}\(B\)\|\>\\Delta/2\. The following proposition shows that a positive population gap can be detected with a number of trials that depends on the gap and the model’s feature sensitivity, but not on graph size\.

###### Proposition 2\(Population separation yields finite\-trial distinguishability\)\.

LetFFbe uniformlyLL\-Lipschitz, and fixG,H∈𝒢G,H\\in\\mathcal\{G\}withgapF⁡\(G,H\)≥Δ\>0\\operatorname\{gap\}\_\{F\}\(G,H\)\\geq\\Delta\>0\. For anyα∈\(0,1/2\)\\alpha\\in\(0,1/2\), the test above has probability of error at mostα\\alphafor everyA,B∈\{G,H\}A,B\\in\\\{G,H\\\}whenever the number of trials is greater than

8​L2​DK2Δ2​log⁡2α\.\\frac\{8L^\{2\}D\_\{K\}^\{2\}\}\{\\Delta^\{2\}\}\\log\\frac\{2\}\{\\alpha\}\.

The proof is given in[AppendixA](https://arxiv.org/html/2610.12809#A1)\.

To prove limitations on finite\-trial testing, we use*random\-color Weisfeiler–Leman*\(random WL\)\. Each trial independently colors the vertices and applies standard Weisfeiler–Leman refinement\. An arbitrary test then compares the resulting patterns across trials\. These patterns contain enough information to determine the output of an MPNN on the same colored graph\. Thus, for uniformqq\-color initializations, limitations of random\-color WL also apply to the corresponding random\-color MPNNs, including tests that use more than their empirical means\.

###### Definition 3\(Random\-color WL distinguishability\)\.

Letq,s∈ℕq,s\\in\\mathbb\{N\}andα∈\(0,1/2\)\\alpha\\in\(0,1/2\)\. A non\-isomorphic pairG,HG,His*statistically\(q,s,α\)\(q,s,\\alpha\)\-distinguishable by random\-color WL*if a randomized binary testψ\\psisatisfies

maxA,B∈\{G,H\}Pr\(ψ\(𝒁A,𝒁B′\)≠𝟏\{A≠B\}\)≤α,\\max\_\{A,B\\in\\\{G,H\\\}\}\\Pr\\\!\\left\(\\psi\(\\bm\{Z\}\_\{A\},\\bm\{Z\}^\{\\prime\}\_\{B\}\)\\neq\\mathbf\{1\}\\\{A\\neq B\\\}\\right\)\\leq\\alpha,where𝐙A,𝐙B′\\bm\{Z\}\_\{A\},\\bm\{Z\}^\{\\prime\}\_\{B\}are independent batches ofss11\-WL patterns from independent uniformqq\-colorings ofAAandBB, respectively\.

Here,qqcontrols the number of colors available within each trial, whilesscontrols the number of independent observations\. The full construction and statistical reductions are in[AppendicesA](https://arxiv.org/html/2610.12809#A1)and[6](https://arxiv.org/html/2610.12809#Thmdefinition6)\.

These notions complete the connection to function approximation\. By[Proposition2](https://arxiv.org/html/2610.12809#Thmtheorem2), a lower bound ruling out successful testing at a sufficiently large trial budget also rules out the corresponding population gap\. Such a bound limits how accurately the model can approximate a target that assigns different values to the two graphs\. We formalize the resulting obstruction to size\-uniform universality in[Corollary14](https://arxiv.org/html/2610.12809#Thmtheorem14)in Appendix[A\.6](https://arxiv.org/html/2610.12809#A1.SS6)\.

## 3Expressivity Bounds

We now analyze the expressive power of random\-feature MPNNs across graph sizes\. We first show that uniform Lipschitzness lets us replace continuous random features with finite random colors, and use this reduction to establish non\-universality\. We then prove strict color and trial hierarchies for statistical distinguishability and establish incomparability with higher\-order Weisfeiler–Leman methods\.

### 3\.1From continuous features to random colors

We begin by using uniform Lipschitzness to quantize random features with an error independent of graph size\. LetS⊂KS\\subset Kbe a finite palette and letqS:K→Sq\_\{S\}\\colon K\\to Sbe a quantization map taking every point inKKto its nearest point inSS, withδ⁡\(S\)≔sup𝒛∈K‖𝒛−qS​\(𝒛\)‖\\delta\(S\)\\coloneq\\sup\_\{\\bm\{z\}\\in K\}\\\|\\bm\{z\}\-q\_\{S\}\(\\bm\{z\}\)\\\|\. ApplyingqSq\_\{S\}to each node gives\(QS​𝒙\)v=qS​\(𝒙v\)\(Q\_\{S\}\\bm\{x\}\)\_\{v\}=q\_\{S\}\(\\bm\{x\}\_\{v\}\), and we consider the quantized population predictorF¯S​\(G\)≔𝔼⁡\[F⁡\(G,QS​𝝃G\)\]\\overline\{F\}\_\{S\}\(G\)\\coloneq\\mathbb\{E\}\[F\(G,Q\_\{S\}\\bm\{\\xi\}^\{G\}\)\]\.

###### Theorem 3\(Size\-uniform quantization\)\.

LetFFbe a uniformlyLL\-Lipschitz MPNN with random features supported on compactKK\. For every finite paletteS⊂KS\\subset K,

supG∈𝒢\|F¯S​\(G\)−F¯​\(G\)\|≤L​δ​\(S\)\.\\sup\_\{G\\in\\mathcal\{G\}\}\|\\overline\{F\}\_\{S\}\(G\)\-\\overline\{F\}\(G\)\|\\leq L\\delta\(S\)\.

The result follows as‖𝒙−QS​𝒙‖in≤δ⁡\(S\)\\\|\\bm\{x\}\-Q\_\{S\}\\bm\{x\}\\\|\_\{\\mathrm\{in\}\}\\leq\\delta\(S\)is independent of the number of nodes and Lipschitzness bounds the output change byL​δ​\(S\)L\\delta\(S\)\. Compactness ensures the existence of finite palettesSSwith arbitrarily smallδ⁡\(S\)\\delta\(S\)\. For a concrete example, consider uniform features on\[0,1\]d\[0,1\]^\{d\}\. Anmm\-level grid per coordinate gives quantization tomdm^\{d\}equally likely colors and quantization error at mostL​d/\(2​m\)L\\sqrt\{d\}/\(2m\)\.

###### Corollary 4\(Finite colors suffice\)\.

Every graph invariant size\-uniformly approximable by uniformly Lipschitz MPNNs with compactly supported random features is also size\-uniformly approximable by uniformly Lipschitz random\-color MPNNs\.

Intuitively, this corollary follows as a sufficiently fine palette preserves a model’s output up to arbitrarily small error\. Uniform Lipschitzness then ensures that this same palette remains sufficient as graphs grow\. The palette may need to become finer as we demand more accurate approximation, but it need not grow with graph size\.

In addition to palettes generated by quantization, we will also consider palettes that are one\-hot encodings of colors\. We show that these palettes have equivalent approximation power in[AppendixB](https://arxiv.org/html/2610.12809#A2)\.

### 3\.2Non\-universality and trial lower bounds

We now use quantization to establish limitations on size\-uniform approximation\. We construct a pair of non\-isomorphic graphs using Cai–Fürer–Immerman gadgets\[[4](https://arxiv.org/html/2610.12809#bib.bib4)\]that require an exponential number of trials to distinguish\.

###### Theorem 5\(Exponential trial requirement\)\.

There exist non\-isomorphic connected graph pairs\(Gk,Hk\)\(G\_\{k\},H\_\{k\}\), withnk→∞n\_\{k\}\\to\\inftyvertices and diameter 2, such that statistical\(q,s,1/3\)\(q,s,1/3\)\-distinguishability by random\-color WL requires

s=exp⁡\(Ω⁡\(nkq10\)\)s=\\exp\\\!\\left\(\\Omega\\\!\\left\(\\frac\{n\_\{k\}\}\{q^\{10\}\}\\right\)\\right\)forq≥2q\\geq 2\.

The pair\(Gk,Hk\)\(G\_\{k\},H\_\{k\}\)is built from many copies of the11\-WL\-indistinguishable pair2​C32C\_\{3\}andC6C\_\{6\}, connected by CFI gadgets so that hiding the distinction within any one pair also hides the distinction betweenGkG\_\{k\}andHkH\_\{k\}\. For a fixed palette, the2​C32C\_\{3\}andC6C\_\{6\}blocks in each pair are both monochromatic with constant probability, independently across pairs\. When this happens, WL cannot distinguish the2​C32C\_\{3\}andC6C\_\{6\}blocks\. The probability that a trial avoids all such events is then exponentially small in graph size, so exponentially many trials are required\. These graph pairs can be used to construct a graph invariant taking value11onGkG\_\{k\}and00onHkH\_\{k\}that uniformly Lipschitz random\-feature MPNNs cannot approximate uniformly over graph size\. This establishes their non\-universality\.

###### Corollary 6\(Failure of size\-uniform universality\)\.

Uniformly Lipschitz MPNNs with i\.i\.d\. uniform features on\[0,1\]d\[0,1\]^\{d\}are not size\-uniform universal approximators for bounded graph invariants, even for input graphs of bounded diameter or bounded degree\.

### 3\.3Colors and trials

The previous section gives an example where colors are exponentially more useful than trials; we now show that increasing either resource strictly increases statistical distinguishability\.

###### Theorem 7\(Strict color and trial hierarchies\)\.

For statistical distinguishability by random\-color WL as in[Definition3](https://arxiv.org/html/2610.12809#Thmdefinition3), the following hold\.

1. \(i\)*Trials\.*For every integers≥2s\\geq 2, there are non\-isomorphic finite graphsGs,HsG\_\{s\},H\_\{s\}that are statistically\(2,s,1/3\)\(2,s,1/3\)\-distinguishable but are not statistically\(2,s−1,1/3\)\(2,s\-1,1/3\)\-distinguishable\.
2. \(ii\)*Colors\.*For every pair of integersq,s≥1q,s\\geq 1, there are non\-isomorphic finite graphsGq,s,Hq,sG\_\{q,s\},H\_\{q,s\}that are statistically\(q\+1,s,1/3\)\(q\+1,s,1/3\)\-distinguishable but are not statistically\(r,s,1/3\)\(r,s,1/3\)\-distinguishable for any1≤r≤q1\\leq r\\leq q\.

The trial hierarchy is already strict with two colors\. Both statements follow from a common graph construction\. That is, a parity gadget combines pairs of cycle blocks so that a trial reveals the graph identity when every input pair has at least one nonmonochromatic block\. Otherwise, the conditional WL observation laws agree for the two graphs\. This yields an explicit revelation probability and an exact expression for the optimal testing error\. We then choose the graph parameters so that this error crosses1/31/3upon adding one trial or one color\. The full construction and proofs are given in[AppendixH](https://arxiv.org/html/2610.12809#A8)\.

### 3\.4Comparison with Weisfeiler–Leman

We now show that with fixed trials and palette size, random\-color MPNNs are incomparable withkk\-WL fork≥2k\\geq 2\.111We usekk\-WL to denote folklore WL \(kk\-FWL\), which is equivalent to oblivious\(k\+1\)\(k\+1\)\-WL fork≥2k\\geq 2; see[Morris et al\. \[17, Sections 3\.1–3\.2\]](https://arxiv.org/html/2610.12809#bib.bib17)\.

###### Theorem 8\(Incomparability with higher\-order WL\)\.

For everyk≥2k\\geq 2:

1. \(i\)There exists akk\-WL\-indistinguishable graph pair that is distinguished with success probability greater than2/32/3by a uniformly Lipschitz MPNN with order\-normalized sum aggregation, using two colors and one trial\.
2. \(ii\)For every fixedq,s≥1q,s\\geq 1, there exists a graph pair distinguished by22\-WL, and hence bykk\-WL, that is not statistically\(q,s,1/3\)\(q,s,1/3\)\-distinguishable by random\-color WL\.

For the first direction, start with annn\-vertex graph pair thatkk\-WL cannot distinguish\. Attach a path of the same length to every vertex, preservingkk\-WL indistinguishability\. The independent binary colors along each path, read in order from its attachment vertex, form an identifier for that original vertex\. If the paths have lengthO⁡\(log⁡n\)O\(\\log n\), then these identifiers are unique with high probability, and thus, 2 colors provide enough information to distinguish every original vertex\. An MPNN can collect these identifiers and use them to recognize the graph\. This example shows how random colors and graph structure can powerfully combine to distinguish vertices\.

For the reverse direction, consider the pair\(Gk,Hk\)\(G\_\{k\},H\_\{k\}\)from[Theorem5](https://arxiv.org/html/2610.12809#Thmtheorem5), which is constructed with CFI gadgets\. The22\-WL distinctions between the2​C32C\_\{3\}andC6C\_\{6\}blocks propagate through the parity tree, revealing which root endpoint carries the marker\. The exponential trial lower bound then rules out reliable distinction with any fixed palette and trial count on sufficiently large pairs\. The formal incomparability result appears in[AppendixE](https://arxiv.org/html/2610.12809#A5)\.

## 4Algorithmic Applications

Finite random colors also support algorithmic computations across graph sizes\. We give MPNN constructions for tree subgraph detection via color coding and a local MST edge task, with resource requirements independent of graph size\.

### 4\.1Tree subgraph detection

We adapt the color\-coding algorithm of[Alon et al\. \[2\]](https://arxiv.org/html/2610.12809#bib.bib2)to random\-color MPNNs\. Consider a graphGGwithnnvertices and a fixed rooted treeTTwithkkvertices\. Independently assign each vertex inGGa uniform color from\[k\]\[k\]\. A subgraph ofGGisomorphic toTTis called colorful if its vertices have distinct colors; each fixed copy is colorful with probabilityk\!/kkk\!/k^\{k\}\.[Alon et al\. \[2\]](https://arxiv.org/html/2610.12809#bib.bib2)give a dynamic program that searches for colorful copies ofTT, using colors to distinguish their vertices\. We show that an MPNN can implement this dynamic program with depth, width, and trial count independent ofnn\.

###### Theorem 9\(Rooted tree detection\)\.

LetTTbe a rooted tree withk≥1k\\geq 1vertices and letα∈\(0,1\)\\alpha\\in\(0,1\)\. There is a random\-color MPNN usingkkcolors,O⁡\(k\)O\(k\)layers, hidden dimensionexp⁡\(O⁡\(k\)\)\\exp\(O\(k\)\), max aggregation, and binary vertex outputs such that, for every graphGGand vertexv∈V⁡\(G\)v\\in V\(G\),

s=⌈kkk\!​log⁡1α⌉s=\\left\\lceil\\frac\{k^\{k\}\}\{k\!\}\\log\\frac\{1\}\{\\alpha\}\\right\\rceilindependent trials suffice to detect a non\-induced copy ofTTrooted atvvwith no false positives and false\-negative probability at mostα\\alpha\. The test atvvaccepts when its average binary output is positive\.

Taking the maximum over vertex outputs gives a graph\-level detector forTTwith the same resource bounds and error guarantees \([Corollary31](https://arxiv.org/html/2610.12809#Thmtheorem31)\)\. The network and trial budgets depend only onkkand desired confidence, not on the input graph’s sizenn\. A subcase is detecting simple paths onkkvertices\. The construction and proof appear in[Theorem30](https://arxiv.org/html/2610.12809#Thmtheorem30)\. Note that without colors, MPNNs with identical initial vertex featurescannotsolve this task in general\. For example,C6C\_\{6\}contains a simple four\-vertex path whereas2​C32C\_\{3\}does not, but these graphs are indistinguishable by11\-WL and hence indistinguishable by any MPNN with identical initial vertex features \([Proposition28](https://arxiv.org/html/2610.12809#Thmtheorem28)\)\.

### 4\.2Local MST edge detection

Next, we consider a task for detecting MST edges that requires only local information\. An edge belongs to every minimum spanning tree \(MST\) if and only if it is the unique minimum\-weight edge across some cut\. For a graph with uniform weights, this is exactly the set of bridge edges\. We analyze the set of such edges that unbalanced cuts can witness, so we need only local information to identify them\. Specifically, letG=\(V,E\)G=\(V,E\)be a simple graph with edge weightsw:E→Λw\\colon E\\to\\Lambdain a fixed finite ordered set\. WriteAk​\(G,w\)A\_\{k\}\(G,w\)for the edges that uniquely minimize a cut with fewer thankkvertices on one side of the cut\. We give an MPNN that detects such edges\. As this is an edge prediction task, we compute the output for each edge by applying a shared MLP, called the*edge decoder*, to the sum of its endpoint embeddings together with its edge weight\.

###### Proposition 10\(Size\-independent local MST edge detection\)\.

Fix an integerk≥2k\\geq 2, a finite weight setΛ\\Lambda, andε,α∈\(0,1\)\\varepsilon,\\alpha\\in\(0,1\)\. There is a max\-aggregation random\-color MPNN with an edge decoder such that, for every such graphGG, its outputA^⊆E\\widehat\{A\}\\subseteq Emisses at most anε\\varepsilonfraction ofAk​\(G,w\)A\_\{k\}\(G,w\)and incorrectly includes at most anε\\varepsilonfraction ofE∖Ak​\(G,w\)E\\setminus A\_\{k\}\(G,w\), with probability at least1−α1\-\\alpha\. Its palette size, depth, and number of independent trials depend only onk,Λ,ε,αk,\\Lambda,\\varepsilon,\\alpha, not on graph size\.

Our construction tests whether removing the candidate edge and all heavier edges leaves its endpoints in different components, with at least one component containing fewer thankkvertices\. Each endpoint collects the colors it can reach, allowing the network to recognize a small component and compare the two endpoints’ components\. With sufficiently many colors and trials, this controls both missed edges and false detections\. The construction and proof are given in[Proposition33](https://arxiv.org/html/2610.12809#Thmtheorem33)\. In contrast, we also show that MPNNs with identical initial vertex featurescannotcomputeAkA\_\{k\}in general \([Theorem34](https://arxiv.org/html/2610.12809#Thmtheorem34)\)\.

## 5Learnability of Randomized GNNs

We study the learnability of randomized MPNNs trained using averages over finitely many random node initializations\. We fix the depthDD, hidden dimensions, aggregation scheme, and initialization lawρK\\rho\_\{K\}on a compact feature spaceKK, subject to the weight and bias bounds in[SectionA\.2](https://arxiv.org/html/2610.12809#A1.SS2)\. We consider scalar graph\-level outputs with mean pooling and a linear readout\.

The graph pseudometricdDrandd\_\{D\}^\{\\mathrm\{rand\}\}compares the distributions of depth\-DDneighborhood representations under random node initialization and uniform vertex sampling\. It is the Wasserstein distance between these distributions, using a recursive metric reflecting the aggregation scheme; see[AppendixK](https://arxiv.org/html/2610.12809#A11)\. Distinct graphs may have distance zero if their representation distributions coincide\. The graph domain𝒢\\mathcal\{G\}is totally bounded under this pseudometric, and the mean predictorF¯θ​\(G\)≔𝔼⁡\[Fθ​\(G,𝝃G\)\]\\overline\{F\}\_\{\\theta\}\(G\)\\coloneq\\mathbb\{E\}\[F\_\{\\theta\}\(G,\\bm\{\\xi\}^\{G\}\)\], where𝝃G∼ρK⊗V⁡\(G\)\\bm\{\\xi\}^\{G\}\\sim\\rho\_\{K\}^\{\\otimes V\(G\)\}, satisfies

\|F¯θ​\(G\)−F¯θ​\(G′\)\|≤Bθ​dDrand​\(G,G′\)\.\|\\overline\{F\}\_\{\\theta\}\(G\)\-\\overline\{F\}\_\{\\theta\}\(G^\{\\prime\}\)\|\\leq B\_\{\\theta\}d\_\{D\}^\{\\mathrm\{rand\}\}\(G,G^\{\\prime\}\)\.Here,BθB\_\{\\theta\}is an explicit Lipschitz certificate computed from the network parameters; see[SectionJ\.2](https://arxiv.org/html/2610.12809#A10.SS2)\. These properties allow accuracy on a suitable finite training set to control approximation error throughout𝒢\\mathcal\{G\}\. Letf∗:𝒢→ℝf^\{\\ast\}\\colon\\mathcal\{G\}\\to\\mathbb\{R\}beB∗B\_\{\\ast\}\-Lipschitz underdDrandd\_\{D\}^\{\\mathrm\{rand\}\}\. For training graphsG1,…,GnG\_\{1\},\\ldots,G\_\{n\}andSSindependent initializations𝝃i,sGi∼ρK⊗V⁡\(Gi\)\\bm\{\\xi\}\_\{i,s\}^\{G\_\{i\}\}\\sim\\rho\_\{K\}^\{\\otimes V\(G\_\{i\}\)\}of each graph, define

F^θ,S​\(Gi\)≔1S​∑s=1SFθ​\(Gi,𝝃i,sGi\),ℒ^reg​\(θ\)≔1n​∑i=1n\|F^θ,S​\(Gi\)−f∗​\(Gi\)\|\+λ​\(Bθ−B∗\)\+,\\begin\{gathered\}\\widehat\{F\}\_\{\\theta,S\}\(G\_\{i\}\)\\coloneq\\frac\{1\}\{S\}\\sum\_\{s=1\}^\{S\}F\_\{\\theta\}\(G\_\{i\},\\bm\{\\xi\}\_\{i,s\}^\{G\_\{i\}\}\),\\\\ \\begin\{multlined\}\\widehat\{\\mathcal\{L\}\}\_\{\\mathrm\{reg\}\}\(\\theta\)\\coloneq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\|\\widehat\{F\}\_\{\\theta,S\}\(G\_\{i\}\)\-f^\{\\ast\}\(G\_\{i\}\)\|\+\\lambda\(B\_\{\\theta\}\-B\_\{\\ast\}\)\_\{\+\},\\end\{multlined\}\\end\{gathered\}whereλ\>0\\lambda\>0and\(a\)\+=max⁡\{a,0\}\(a\)\_\{\+\}=\\max\\\{a,0\\\}\.

###### Theorem 11\(Uniform generalization from Monte Carlo training\)\.

For everyε\>0\\varepsilon\>0andδ∈\(0,1\)\\delta\\in\(0,1\), there exist a finite training set\{G1,…,Gn\}⊆𝒢\\\{G\_\{1\},\\ldots,G\_\{n\}\\\}\\subseteq\\mathcal\{G\}and a toleranceη\>0\\eta\>0such that the following holds\. For any sufficiently largeSS, drawSSindependent initializations of each training graph fromρK⊗V⁡\(Gi\)\\rho\_\{K\}^\{\\otimes V\(G\_\{i\}\)\}\. Then, with probability at least1−δ1\-\\delta,

ℒ^reg​\(θ\)<η⟹supG∈𝒢\|F¯θ​\(G\)−f∗​\(G\)\|<ε\\widehat\{\\mathcal\{L\}\}\_\{\\mathrm\{reg\}\}\(\\theta\)<\\eta\\quad\\Longrightarrow\\quad\\sup\_\{G\\in\\mathcal\{G\}\}\|\\overline\{F\}\_\{\\theta\}\(G\)\-f^\{\\ast\}\(G\)\|<\\varepsilonsimultaneously for allθ∈Θ\\theta\\in\\Theta\.

Thus, sufficiently small sampled regularized error guarantees uniform approximation by the mean predictor, regardless of graph order\. The training\-set size is controlled by the graph domain’s covering number at a radius determined by the desired accuracy and the target’s Lipschitz constant\. Uniform Monte Carlo concentration makes the guarantee hold even when parameters are selected using the same sampled initializations\. For any fixed test graph, Monte Carlo concentration controls the error from averagingS′S^\{\\prime\}fresh independent initializations, without retraining\. The proof and an explicit sufficient sample size are given in[AppendicesM](https://arxiv.org/html/2610.12809#A13)and[L](https://arxiv.org/html/2610.12809#A12)\.

## 6Experiments

We perform a range of experiments to explore the role of random colors in expressivity and size generalization\.[AppendixN](https://arxiv.org/html/2610.12809#A14)gives additional details\.

#### Bridge prediction across graph sizes

We train random\-color MPNNs to identify bridge edges in unweighted Erdős–Rényi graphs with 16 or 32 vertices and test on 512\-vertex graphs\. Our local MST edge\-detection result \([Proposition10](https://arxiv.org/html/2610.12809#Thmtheorem10)\) motivates examining the sizebbof the smaller endpoint component after deleting a bridge\. We train separate models to detect bridges with exactlyb∈\{4,5,6\}b\\in\\\{4,5,6\\\}vertices on the smaller side, treating all other edges as negatives\. A standard MPNN with constant initialization and max aggregation assigns the same score to every edge, yielding exactly50%50\\%balanced accuracy for all three target sizes\. With 16 trials and a fixed training budget, increasing the number of one\-hot colors increases mean balanced test accuracy \([Figure2](https://arxiv.org/html/2610.12809#S6.F2)\)\. In particular, larger palettes improve detection, while bridges with larger smaller\-side components remain harder to identify\. Furthermore, detection generalizes to larger graphs using a fixed finite palette\.

Figure 2:Balanced test accuracy1−12​\(FNR\+FPR\)1\-\\tfrac\{1\}\{2\}\(\\operatorname\{FNR\}\+\\operatorname\{FPR\}\)for detecting bridges of smaller\-side sizebb\. Error bars show SE over five training seeds\.
#### Tree substructure detection: colors and trials

Motivated by our color\-coding construction \([Theorem9](https://arxiv.org/html/2610.12809#Thmtheorem9)\), we train models to detect the full balanced degree\-three tree of depth two—a root with three children, each with two leaves—as a non\-induced subgraph rooted at each vertex\. Training and test graphs are random 3\-regular graphs on 24 vertices and we vary the palette and trial count\. On these graphs, the target is equivalent to the vertex’s two\-hop neighborhood having the maximum possible size of 10\. We train using the maximum output across trials\. At test time, we sum predictions across trials and apply a threshold chosen on validation graphs\.

Increasing either the palette size or the number of trials increases mean test accuracy \([Figure3](https://arxiv.org/html/2610.12809#S6.F3)\)\. These results support our tree\-detection construction \([Theorem9](https://arxiv.org/html/2610.12809#Thmtheorem9)\): finite colors enable detection, whereas constant initial features give identical outputs at every vertex of these 3\-regular graphs\. The gains from both resources align with our color and trial hierarchies \([Theorem7](https://arxiv.org/html/2610.12809#Thmtheorem7)\)\.

![Refer to caption](https://arxiv.org/html/2610.12809v1/tree_detection_heatmap.png)Figure 3:Rooted tree detection with different numbers of colors and trials\. Cells show mean node test accuracy \(%\)±\\pmSE across five training seeds\.
#### Inference\-time quantization

Motivated by our quantization result \([Theorem3](https://arxiv.org/html/2610.12809#Thmtheorem3)\), we examine whether quantizing random features preserves predictive performance\. We replicate GCN\-RNI on EXP\[[1](https://arxiv.org/html/2610.12809#bib.bib1)\]and rGIN on TRIANGLE\[[24](https://arxiv.org/html/2610.12809#bib.bib24)\], then quantize their random features to two values per coordinate without retraining\. EXP classifies graph\-encoded Boolean formulas; we evaluate the 64\-coordinate baseline and a scalar variant\. On TRIANGLE, we predict triangle membership using 20\-vertex 3\-regular training graphs and 20\- and 100\-vertex test graphs\. Both models retain most of their predictive performance \([Table1](https://arxiv.org/html/2610.12809#S6.T1)\), supporting our message that finite palettes can preserve the expressive benefits of continuous random features, including under size generalization\.

Table 1:Inference\-time performance under quantization\. Mean±\\pmSE across ten folds for EXP, and ten single\-trial feature draws of one trained model for TRIANGLE\.

## 7Conclusions

We analyze random\-feature MPNNs through the vertex distinguishability provided by finite random colors\. This offers a natural intermediate between anonymous message passing and the use of continuous random features as unique vertex identifiers\. For uniformly Lipschitz MPNNs, finite colors retain the size\-uniform approximation power of continuous random features, while making the capabilities and limitations of random\-feature MPNNs explicit\. Our framework also makes the roles of palette size and trial count clear, laying a theoretical foundation for understanding how to use random features in practice\.

An important next step is to identify further algorithms that can be implemented using graph\-size\-independent numbers of colors and trials\. Although our examples establish limitations and incomparability withkk\-WL, a broader characterization of which graph pairs these models can distinguish remains open\. Our statistical testing framework permits arbitrary combinations of trials, but our approximation and learning analysis centers on averaging\. Studying other ways of combining trial information, beyond averaging and expectations, is another interesting direction, as aggregation across trials is an important architectural choice\.

## Acknowledgements

We thank Sanjoy Dasgupta for insightful discussions during the early stages of this work\.

YW, RRN, and MB are supported by NSF grant CCF\-2217058, and YW and RRN are additionally supported by NSF grants CCF\-2112665 and CCF\-2310411\. CM is partially funded by a DFG Emmy Noether grant \(468502433\), Israel ISF\-DFG Grant \(587125021\), and a RWTH Junior Principal Investigator Fellowship under Germany’s Excellence Strategy\. AV is supported by the German Research Foundation \(DFG\) within Research Training Group 2236/2 \(UnRAVeL\)\.

## AI use statement

We used generative AI tools to help refine and check our mathematical arguments, explore mathematical approaches, design and implement experiments, analyze results, and prepare figures\. We also used these tools for literature searches and to draft and revise the manuscript\. All material developed or modified with AI assistance was explicitly reviewed and verified by the authors\.

## Bibliography

- \[1\]\(2021\)The surprising power of graph neural networks with random node initialization\.InProceedings of the Thirtieth International Joint Conference on Artificial Intelligence \(IJCAI\-21\),pp\. 2112–2118\.External Links:[Document](https://dx.doi.org/10.24963/ijcai.2021/291)Cited by:[§N\.3](https://arxiv.org/html/2610.12809#A14.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px3.p2.1),[§1](https://arxiv.org/html/2610.12809#S1.p1.1),[§1](https://arxiv.org/html/2610.12809#S1.p4.1),[§6](https://arxiv.org/html/2610.12809#S6.SS0.SSS0.Px3.p1.1)\.
- \[2\]N\. Alon, R\. Yuster, and U\. Zwick\(1995\)Color\-coding\.Journal of the ACM42\(4\),pp\. 844–856\.External Links:[Document](https://dx.doi.org/10.1145/210332.210337)Cited by:[Appendix F](https://arxiv.org/html/2610.12809#A6.p1.1),[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px1.p3.1),[§4\.1](https://arxiv.org/html/2610.12809#S4.SS1.p1.1)\.
- \[3\]V\. I\. Bogachev\(2007\)Measure theory\.Springer\-Verlag,Berlin, Heidelberg\.External Links:[Document](https://dx.doi.org/10.1007/978-3-540-34514-5)Cited by:[§J\.1](https://arxiv.org/html/2610.12809#A10.SS1.p2.1.1)\.
- \[4\]J\. Cai, M\. Fürer, and N\. Immerman\(1992\)An optimal lower bound on the number of variables for graph identification\.Combinatorica12\(4\),pp\. 389–410\.External Links:[Document](https://dx.doi.org/10.1007/BF01305232)Cited by:[§C\.1](https://arxiv.org/html/2610.12809#A3.SS1.p4.1),[§C\.2](https://arxiv.org/html/2610.12809#A3.SS2.p3.1),[Appendix E](https://arxiv.org/html/2610.12809#A5.p2.1),[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px1.p2.1),[§3\.2](https://arxiv.org/html/2610.12809#S3.SS2.p1.1)\.
- \[5\]Y\. Chen, J\. Flum, and M\. Liu\(2025\)Some remarks on the uncolored versions of the original CFI\-graphs\.arXiv preprint arXiv:2507\.01459\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2507.01459)Cited by:[Appendix E](https://arxiv.org/html/2610.12809#A5.p2.1)\.
- \[6\]G\. Dasoulas, L\. Dos Santos, K\. Scaman, and A\. Virmaux\(2020\)Coloring graph neural networks for node disambiguation\.InProceedings of the Twenty\-Ninth International Joint Conference on Artificial Intelligence \(IJCAI\-20\),pp\. 2126–2132\.External Links:[Document](https://dx.doi.org/10.24963/ijcai.2020/294)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px3.p2.1),[§1](https://arxiv.org/html/2610.12809#S1.p1.1)\.
- \[7\]T\. Furuya, M\. V\. de Hoop, and G\. Peyré\(2025\)Transformers are universal in\-context learners\.InInternational Conference on Learning Representations,pp\. 80820–80845\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2025/hash/c9028f7874df04843e7bf435ee4cd3c3-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p2.1)\.
- \[8\]J\. Gilmer, S\. S\. Schoenholz, P\. F\. Riley, O\. Vinyals, and G\. E\. Dahl\(2017\)Neural message passing for quantum chemistry\.InProceedings of the 34th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.70,pp\. 1263–1272\.External Links:[Link](https://proceedings.mlr.press/v70/gilmer17a.html)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p1.1)\.
- \[9\]L\. Gonon, T\. Meyer\-Brandis, and N\. Weber\(2026\)Universality and approximation rates of graph neural networks with random features\.arXiv preprint arXiv:2607\.26699\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2607.26699)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px3.p2.1)\.
- \[10\]M\. Isaev, T\. Makai, B\. McKay, P\. Prałat, J\. Tan, and M\. Zhukovskii\(2026\)Canonical labelling of random regular graphs\.arXiv preprint arXiv:2602\.17567\.External Links:[Document](https://dx.doi.org/10.48550/arXiv.2602.17567)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p1.1)\.
- \[11\]C\. I\. Kanatsoulis, E\. Choi, S\. Jegelka, J\. Leskovec, and A\. Ribeiro\(2025\)Learning efficient positional encodings with graph neural networks\.InInternational Conference on Learning Representations,pp\. 36125–36152\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2025/hash/59883a1524bf58cf2dd86d0fc8d499e2-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p4.1)\.
- \[12\]C\. I\. Kanatsoulis and A\. Ribeiro\(2024\)Counting graph substructures with graph neural networks\.InInternational Conference on Learning Representations,pp\. 42023–42054\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2024/hash/b7b4a06644d0747c9482c4e25646a43f-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px3.p2.1),[§1](https://arxiv.org/html/2610.12809#S1.p4.1)\.
- \[13\]C\. I\. Kanatsoulis and A\. Ribeiro\(2024\)Graph neural networks are more powerful than we think\.InIEEE International Conference on Acoustics, Speech and Signal Processing \(ICASSP\),pp\. 7550–7554\.External Links:[Document](https://dx.doi.org/10.1109/ICASSP48485.2024.10447704)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px3.p2.1),[§1](https://arxiv.org/html/2610.12809#S1.p4.1)\.
- \[14\]A\. S\. Kechris\(1995\)Classical descriptive set theory\.Graduate Texts in Mathematics, Vol\.156,Springer,New York\.External Links:[Document](https://dx.doi.org/10.1007/978-1-4612-4190-4)Cited by:[§J\.1](https://arxiv.org/html/2610.12809#A10.SS1.p2.1.1)\.
- \[15\]E\. Levin, Y\. Ma, M\. Díaz, and S\. Villar\(2025\)On transferring transferability: towards a theory for size generalization\.InAdvances in Neural Information Processing Systems,Vol\.38,pp\. 67015–67083\.External Links:[Document](https://dx.doi.org/10.52202/085713-2247)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p2.1)\.
- \[16\]A\. Loukas\(2020\)What graph neural networks cannot learn: depth vs width\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=B1l2bp4YwS)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px3.p1.1)\.
- \[17\]C\. Morris, Y\. Lipman, H\. Maron, B\. Rieck, N\. M\. Kriege, M\. Grohe, M\. Fey, and K\. Borgwardt\(2023\)Weisfeiler and Leman go machine learning: the story so far\.Journal of Machine Learning Research24\(333\),pp\. 1–59\.External Links:[Link](https://jmlr.org/papers/v24/22-0240.html)Cited by:[footnote 1](https://arxiv.org/html/2610.12809#footnote1)\.
- \[18\]C\. Morris, M\. Ritzert, M\. Fey, W\. L\. Hamilton, J\. E\. Lenssen, G\. Rattan, and M\. Grohe\(2019\)Weisfeiler and Leman go neural: higher\-order graph neural networks\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.33,pp\. 4602–4609\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v33i01.33014602)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p1.1),[§1](https://arxiv.org/html/2610.12809#S1.p4.1)\.
- \[19\]R\. R\. Nerem, S\. Chen, S\. Dasgupta, and Y\. Wang\(2026\)Graph neural networks extrapolate out\-of\-distribution for shortest paths\.InProceedings of the Thirty\-Ninth Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.336,pp\. 5273–5331\.External Links:[Link](https://proceedings.mlr.press/v336/nerem26a.html)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p2.1)\.
- \[20\]P\. Pellizzoni, T\. H\. Schulz, D\. Chen, and K\. Borgwardt\(2024\)On the expressivity and sample complexity of node\-individualized graph neural networks\.InAdvances in Neural Information Processing Systems,Vol\.37,pp\. 120221–120251\.External Links:[Document](https://dx.doi.org/10.52202/079017-3821)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px3.p2.1)\.
- \[21\]E\. Rosenbluth and M\. Grohe\(2026\)Repetition makes perfect: recurrent graph neural networks match message passing limit\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.40,pp\. 25168–25175\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v40i30.39707)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px3.p2.1)\.
- \[22\]E\. Rosenbluth, J\. Tönshoff, M\. Ritzert, B\. Kisin, and M\. Grohe\(2024\)Distinguished in uniform: self\-attention vs\. virtual nodes\.InInternational Conference on Learning Representations,pp\. 17926–17946\.External Links:[Link](https://proceedings.iclr.cc/paper_files/paper/2024/hash/4dffa92bf101da4f9109dbf71651047c-Abstract-Conference.html)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p2.1)\.
- \[23\]W\. Rudin\(1976\)Principles of mathematical analysis\.Third edition,McGraw\-Hill\.Cited by:[§K\.1](https://arxiv.org/html/2610.12809#A11.SS1.p1.2.1),[Appendix L](https://arxiv.org/html/2610.12809#A12.p2.2)\.
- \[24\]R\. Sato, M\. Yamada, and H\. Kashima\(2021\)Random features strengthen graph neural networks\.InProceedings of the 2021 SIAM International Conference on Data Mining \(SDM\),pp\. 333–341\.External Links:[Document](https://dx.doi.org/10.1137/1.9781611976700.38)Cited by:[§N\.3](https://arxiv.org/html/2610.12809#A14.SS3.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px3.p2.1),[§1](https://arxiv.org/html/2610.12809#S1.p1.1),[§1](https://arxiv.org/html/2610.12809#S1.p4.1),[§6](https://arxiv.org/html/2610.12809#S6.SS0.SSS0.Px3.p1.1)\.
- \[25\]F\. Scarselli, M\. Gori, A\. C\. Tsoi, M\. Hagenbuchner, and G\. Monfardini\(2009\)The graph neural network model\.IEEE Transactions on Neural Networks20\(1\),pp\. 61–80\.External Links:[Document](https://dx.doi.org/10.1109/TNN.2008.2005605)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p1.1)\.
- \[26\]R\. Schneider\(2014\)Convex bodies: the Brunn–Minkowski theory\.Second edition,Encyclopedia of Mathematics and its Applications, Vol\.151,Cambridge University Press\.External Links:[Document](https://dx.doi.org/10.1017/CBO9781139003858)Cited by:[§J\.1](https://arxiv.org/html/2610.12809#A10.SS1.p2.1.1)\.
- \[27\]P\. Veličković, A\. P\. Badia, D\. Budden, R\. Pascanu, A\. Banino, M\. Dashevskiy, R\. Hadsell, and C\. Blundell\(2022\)The CLRS algorithmic reasoning benchmark\.InProceedings of the 39th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.162,pp\. 22084–22102\.External Links:[Link](https://proceedings.mlr.press/v162/velickovic22a.html)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p2.1)\.
- \[28\]P\. Veličković, R\. Ying, M\. Padovano, R\. Hadsell, and C\. Blundell\(2020\)Neural execution of graph algorithms\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=SkgKO0EtvS)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p2.1)\.
- \[29\]C\. Vignac, A\. Loukas, and P\. Frossard\(2020\)Building powerful and equivariant graph neural networks with structural message\-passing\.InAdvances in Neural Information Processing Systems,Vol\.33,pp\. 14143–14155\.External Links:[Link](https://proceedings.neurips.cc/paper/2020/hash/a32d7eeaae19821fd9ce317f3ce952a7-Abstract.html)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px3.p1.1)\.
- \[30\]S\. Wittig, A\. Vasileiou, R\. R\. Nerem, T\. Stoll, F\. Geerts, Y\. Wang, and C\. Morris\(2026\)Which algorithms can graph neural networks learn?\.InProceedings of the 43rd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.306,pp\. 135232–135307\.External Links:[Link](https://proceedings.mlr.press/v306/wittig26a.html)Cited by:[§J\.1](https://arxiv.org/html/2610.12809#A10.SS1.p2.1.1),[Appendix J](https://arxiv.org/html/2610.12809#A10.p1.1),[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px1.p3.1),[§1](https://arxiv.org/html/2610.12809#S1.p2.1),[§1](https://arxiv.org/html/2610.12809#S1.p5.1)\.
- \[31\]K\. Xu, W\. Hu, J\. Leskovec, and S\. Jegelka\(2019\)How powerful are graph neural networks?\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=ryGs6iA5Km)Cited by:[§C\.1](https://arxiv.org/html/2610.12809#A3.SS1.p3.1),[§1](https://arxiv.org/html/2610.12809#S1.SS0.SSS0.Px3.p2.1),[§1](https://arxiv.org/html/2610.12809#S1.p1.1),[§1](https://arxiv.org/html/2610.12809#S1.p4.1)\.
- \[32\]K\. Xu, M\. Zhang, J\. Li, S\. S\. Du, K\. Kawarabayashi, and S\. Jegelka\(2021\)How neural networks extrapolate: from feedforward to graph neural networks\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=UH-cmocLJC)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p2.1)\.
- \[33\]S\. Yao, E\. Levin, and M\. Díaz\(2026\)Any\-dimensional invariant universality\.InProceedings of the 43rd International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.306,pp\. 147489–147513\.External Links:[Link](https://proceedings.mlr.press/v306/yao26f.html)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p2.1)\.
- \[34\]G\. Yehudai, E\. Fetaya, E\. Meirom, G\. Chechik, and H\. Maron\(2021\)From local structures to size generalization in graph neural networks\.InProceedings of the 38th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.139,pp\. 11975–11986\.External Links:[Link](https://proceedings.mlr.press/v139/yehudai21a.html)Cited by:[§1](https://arxiv.org/html/2610.12809#S1.p2.1)\.

## Appendix AAdditional Framework Details

### A\.1Graphs with random node features and graph statistics

The graph with random node features is

𝑮𝝃≔\(G,\(𝝃v\)v∈V⁡\(G\)\),PG≔Law⁡\(𝑮𝝃\)\.\\bm\{G\}^\{\\bm\{\\xi\}\}\\coloneq\\bigl\(G,\(\\bm\{\\xi\}\_\{v\}\)\_\{v\\in V\(G\)\}\\bigr\),\\qquad P\_\{G\}\\coloneq\\operatorname\{Law\}\(\\bm\{G\}^\{\\bm\{\\xi\}\}\)\.\(2\)
Let𝒢K\\mathcal\{G\}\_\{K\}denote the resulting space of graphs with node features\. A*graph invariant*is a function on graphs that is permutation invariant \(unchanged by vertex relabeling\), and a*graph statistic*is a scalar\-valued graph invariant whose input is a graph with \(random\) node features\. For a graph statistictt,222We assume thatt⁡\(𝑮𝝃\)t\(\\bm\{G\}^\{\\bm\{\\xi\}\}\)is integrable for everyG∈𝒢G\\in\\mathcal\{G\}\.we refer to a single evaluation with initialization𝝃v​∼i\.i\.d\.​ρK\\bm\{\\xi\}\_\{v\}\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}\\rho\_\{K\}, as a*trial*, where the output and its law are

Zt​\(G\)≔t⁡\(𝑮𝝃\),PGt≔Law⁡\(Zt​\(G\)\)\.Z\_\{t\}\(G\)\\coloneq t\(\\bm\{G\}^\{\\bm\{\\xi\}\}\),\\qquad P\_\{G\}^\{t\}\\coloneq\\operatorname\{Law\}\(Z\_\{t\}\(G\)\)\.\(3\)

### A\.2Message\-passing neural networks

Let𝒢\\mathcal\{G\}be a class of graphs with node features and letV1\(𝒢\)≔\{\(G,v\):G∈𝒢,v∈V\(G\)\}V\_\{1\}\(\\mathcal\{G\}\)\\coloneq\\\{\(G,v\)\\colon G\\in\\mathcal\{G\},\\,v\\in V\(G\)\\\}\. A depth\-DDMPNN initializes𝒉G\(0\)​\(v\)=𝒙v\\bm\{h\}\_\{G\}^\{\(0\)\}\(v\)=\\bm\{x\}\_\{v\}, where𝒙v\\bm\{x\}\_\{v\}is the initial feature of nodevv, and updates its representations forℓ=0,…,D−1\\ell=0,\\ldots,D\-1according to

𝒎G\(ℓ\)​\(v\)\\displaystyle\\bm\{m\}\_\{G\}^\{\(\\ell\)\}\(v\)=𝖠𝖦𝖦ℓ⁡\(\{\{𝒉G\(ℓ\)​\(u\):u∈NG​\(v\)\}\}\),\\displaystyle=\\operatorname\{\\mathsf\{AGG\}\}\_\{\\ell\}\\\!\\left\(\\\{\\\!\\\{\\bm\{h\}\_\{G\}^\{\(\\ell\)\}\(u\)\\colon u\\in N\_\{G\}\(v\)\\\}\\\!\\\}\\right\),𝒉G\(ℓ\+1\)​\(v\)\\displaystyle\\bm\{h\}\_\{G\}^\{\(\\ell\+1\)\}\(v\)=UPDℓ⁡\(𝒉G\(ℓ\)​\(v\),𝒎G\(ℓ\)​\(v\)\)\.\\displaystyle=\\operatorname\{UPD\}\_\{\\ell\}\\\!\\left\(\\bm\{h\}\_\{G\}^\{\(\\ell\)\}\(v\),\\bm\{m\}\_\{G\}^\{\(\\ell\)\}\(v\)\\right\)\.
In this work, we specialize the update function to

𝒉G\(ℓ\+1\)​\(v\)=σ⁡\(𝑾self\(ℓ\)​𝒉G\(ℓ\)​\(v\)\+𝑾agg\(ℓ\)​𝒎G\(ℓ\)​\(v\)\+𝒃\(ℓ\)\),\\bm\{h\}\_\{G\}^\{\(\\ell\+1\)\}\(v\)=\\sigma\\\!\\left\(\\bm\{W\}\_\{\\mathrm\{self\}\}^\{\(\\ell\)\}\\bm\{h\}\_\{G\}^\{\(\\ell\)\}\(v\)\+\\bm\{W\}\_\{\\mathrm\{agg\}\}^\{\(\\ell\)\}\\bm\{m\}\_\{G\}^\{\(\\ell\)\}\(v\)\+\\bm\{b\}^\{\(\\ell\)\}\\right\),whereσ\\sigmais the coordinate\-wise ReLU activation function and𝒃\(ℓ\)∈ℝdℓ\+1\\bm\{b\}^\{\(\\ell\)\}\\in\\mathbb\{R\}^\{d\_\{\\ell\+1\}\}is a bias shared by all vertices\. We consider the following aggregation schemes:

𝒎G,sum¯\(ℓ\)​\(v\)\\displaystyle\\bm\{m\}\_\{G,\\overline\{\\mathrm\{sum\}\}\}^\{\(\\ell\)\}\(v\)=1\|V⁡\(G\)\|​∑u∈NG​\(v\)𝒉G\(ℓ\)​\(u\),\\displaystyle=\\frac\{1\}\{\|V\(G\)\|\}\\sum\_\{u\\in N\_\{G\}\(v\)\}\\bm\{h\}\_\{G\}^\{\(\\ell\)\}\(u\),𝒎G,mean\(ℓ\)​\(v\)\\displaystyle\\bm\{m\}\_\{G,\\mathrm\{mean\}\}^\{\(\\ell\)\}\(v\)=1\|NG​\(v\)\|​∑u∈NG​\(v\)𝒉G\(ℓ\)​\(u\),\\displaystyle=\\frac\{1\}\{\|N\_\{G\}\(v\)\|\}\\sum\_\{u\\in N\_\{G\}\(v\)\}\\bm\{h\}\_\{G\}^\{\(\\ell\)\}\(u\),and

𝒎G,max\(ℓ\)​\(v\)\\displaystyle\\bm\{m\}\_\{G,\\mathrm\{max\}\}^\{\(\\ell\)\}\(v\)=maxu∈NG​\(v\)⁡𝒉G\(ℓ\)​\(u\),\\displaystyle=\\max\_\{u\\in N\_\{G\}\(v\)\}\\bm\{h\}\_\{G\}^\{\(\\ell\)\}\(u\),𝒎G,min\(ℓ\)​\(v\)\\displaystyle\\bm\{m\}\_\{G,\\mathrm\{min\}\}^\{\(\\ell\)\}\(v\)=minu∈NG​\(v\)⁡𝒉G\(ℓ\)​\(u\),\\displaystyle=\\min\_\{u\\in N\_\{G\}\(v\)\}\\bm\{h\}\_\{G\}^\{\(\\ell\)\}\(u\),where the maximum and minimum are taken coordinate\-wise\.

Letθ∈Θ\\theta\\in\\Thetacollect the update and readout parameters, and letℋsum¯\(D\)\\mathcal\{H\}\_\{\\overline\{\\mathrm\{sum\}\}\}^\{\(D\)\},ℋmean\(D\)\\mathcal\{H\}\_\{\\mathrm\{mean\}\}^\{\(D\)\},ℋmax\(D\)\\mathcal\{H\}\_\{\\mathrm\{max\}\}^\{\(D\)\}, andℋmin\(D\)\\mathcal\{H\}\_\{\\mathrm\{min\}\}^\{\(D\)\}denote the corresponding classes of maps𝒉θ\(D\):V1​\(𝒢\)→ℝdD\\bm\{h\}\_\{\\theta\}^\{\(D\)\}\\colon V\_\{1\}\(\\mathcal\{G\}\)\\to\\mathbb\{R\}^\{d\_\{D\}\}\. The classℋmin\(D\)\\mathcal\{H\}\_\{\\mathrm\{min\}\}^\{\(D\)\}is defined analogously\. We assume throughout that

‖𝑾self\(ℓ\)‖2,‖𝑾agg\(ℓ\)‖2≤BW,‖𝒃\(ℓ\)‖2≤Bb\.\\left\\\|\\bm\{W\}\_\{\\mathrm\{self\}\}^\{\(\\ell\)\}\\right\\\|\_\{2\},\\,\\left\\\|\\bm\{W\}\_\{\\mathrm\{agg\}\}^\{\(\\ell\)\}\\right\\\|\_\{2\}\\leq B\_\{W\},\\qquad\\\|\\bm\{b\}^\{\(\\ell\)\}\\\|\_\{2\}\\leq B\_\{b\}\.The constantsBW,Bb<∞B\_\{W\},B\_\{b\}<\\inftyare shared across allθ∈Θ\\theta\\in\\Thetaand layers and are independent of graph size\. When a linear readout𝑾out\\bm\{W\}\_\{\\mathrm\{out\}\}is used, we also assume‖𝑾out‖2≤Bout\\\|\\bm\{W\}\_\{\\mathrm\{out\}\}\\\|\_\{2\}\\leq B\_\{\\mathrm\{out\}\}\.

The graph\-level output uses a permutation\-invariant readout chosen as part of the architecture:

Fθ​\(G,𝒙\)=𝖱𝖤𝖠𝖣𝖮𝖴𝖳θ⁡\(\{\{𝒉G\(D\)​\(v\):v∈V⁡\(G\)\}\}\)\.F\_\{\\theta\}\(G,\\bm\{x\}\)=\\operatorname\{\\mathsf\{READOUT\}\}\_\{\\theta\}\\\!\\left\(\\\{\\\!\\\{\\bm\{h\}\_\{G\}^\{\(D\)\}\(v\)\\colon v\\in V\(G\)\\\}\\\!\\\}\\right\)\.We writeF⁡\(G,𝒙\)F\(G,\\bm\{x\}\)for the network output, where𝒙=\(𝒙v\)v∈V⁡\(G\)\\bm\{x\}=\(\\bm\{x\}\_\{v\}\)\_\{v\\in V\(G\)\}denotes the initial node features\.

### A\.3Population approximation

For a graph statistictt, its*tt\-mean*is the graph invariant defined by

μt​\(G\)≔𝔼𝑮𝝃∼PG​\[t⁡\(𝑮𝝃\)\]\.\\mu\_\{t\}\(G\)\\coloneq\\mathbb\{E\}\_\{\\bm\{G\}^\{\\bm\{\\xi\}\}\\sim P\_\{G\}\}\[t\(\\bm\{G\}^\{\\bm\{\\xi\}\}\)\]\.\(4\)

### A\.4Uniform Lipschitzness

###### Proof of[Lemma1](https://arxiv.org/html/2610.12809#Thmtheorem1)\.

Take the coordinate maximum norm on each hidden space and the induced matrix norm∥⋅∥∞→∞\\\|\\cdot\\\|\_\{\\infty\\to\\infty\}\. For two initializations𝒙,𝒙′\\bm\{x\},\\bm\{x\}^\{\\prime\}of the same nonempty graph, write

eℓ≔maxv∈V⁡\(G\)⁡‖𝒉G\(ℓ\)​\(v,𝒙\)−𝒉G\(ℓ\)​\(v,𝒙′\)‖∞\.e\_\{\\ell\}\\coloneq\\max\_\{v\\in V\(G\)\}\\\|\\bm\{h\}\_\{G\}^\{\(\\ell\)\}\(v;\\bm\{x\}\)\-\\bm\{h\}\_\{G\}^\{\(\\ell\)\}\(v;\\bm\{x\}^\{\\prime\}\)\\\|\_\{\\infty\}\.\(5\)Mean and order\-normalized sum aggregation are nonexpansive in this max\-over\-nodes norm\. Coordinatewise max and min are also nonexpansive, since each coordinate changes by at mosteℓe\_\{\\ell\}\. For unnormalized sums on graphs of maximum degree at mostΔ\\Delta, the corresponding bound isΔ​eℓ\\Delta e\_\{\\ell\}\. Define empty neighborhood aggregates and the readout of the empty graph to be zero\.

LetAℓ=1A\_\{\\ell\}=1for the normalized, max, and min aggregations, andAℓ=ΔA\_\{\\ell\}=\\Deltafor unnormalized sums\. Since ReLU is nonexpansive and the biases cancel in differences, each update satisfies

eℓ\+1≤\(‖𝑾self\(ℓ\)‖∞→∞\+Aℓ​‖𝑾agg\(ℓ\)‖∞→∞\)​eℓ\.e\_\{\\ell\+1\}\\leq\\left\(\\\|\\bm\{W\}\_\{\\mathrm\{self\}\}^\{\(\\ell\)\}\\\|\_\{\\infty\\to\\infty\}\+A\_\{\\ell\}\\\|\\bm\{W\}\_\{\\mathrm\{agg\}\}^\{\(\\ell\)\}\\\|\_\{\\infty\\to\\infty\}\\right\)e\_\{\\ell\}\.\(6\)Mean pooling is nonexpansive\. Composing these bounds with the final linear map gives a feature\-Lipschitz constant

L∞=‖𝑾out‖∞→∞​∏ℓ=0D−1\(‖𝑾self\(ℓ\)‖∞→∞\+Aℓ​‖𝑾agg\(ℓ\)‖∞→∞\)\.L\_\{\\infty\}=\\\|\\bm\{W\}\_\{\\mathrm\{out\}\}\\\|\_\{\\infty\\to\\infty\}\\prod\_\{\\ell=0\}^\{D\-1\}\\left\(\\\|\\bm\{W\}\_\{\\mathrm\{self\}\}^\{\(\\ell\)\}\\\|\_\{\\infty\\to\\infty\}\+A\_\{\\ell\}\\\|\\bm\{W\}\_\{\\mathrm\{agg\}\}^\{\(\\ell\)\}\\\|\_\{\\infty\\to\\infty\}\\right\)\.\(7\)This constant is independent of graph size\. For any other fixed norm∥⋅∥\\\|\\cdot\\\|on the input space, chooseccsuch that‖𝒛‖∞≤c​‖𝒛‖\\\|\\bm\{z\}\\\|\_\{\\infty\}\\leq c\\\|\\bm\{z\}\\\|\. ThenL=c​L∞L=cL\_\{\\infty\}gives uniform Lipschitzness with respect to∥⋅∥in\\\|\\cdot\\\|\_\{\\mathrm\{in\}\}\. ∎

WriteDK≔sup𝒖,𝒖′∈K‖𝒖−𝒖′‖D\_\{K\}\\coloneq\\sup\_\{\\bm\{u\},\\bm\{u\}^\{\\prime\}\\in K\}\\\|\\bm\{u\}\-\\bm\{u\}^\{\\prime\}\\\|for the diameter of the feature space\. The input norm and uniform Lipschitzness are defined in[Definition2](https://arxiv.org/html/2610.12809#Thmdefinition2)\.

Uniform Lipschitzness immediately bounds the output diameter, independently of graph size\.

###### Lemma 12\(Uniform output diameter\)\.

LetFFbe a uniformlyLL\-Lipschitz MPNN\. Then, for every graphGG,ZF​\(G\)Z\_\{F\}\(G\)is supported on an interval of length at mostL​DKLD\_\{K\}\.

###### Proof\.

For any𝒙,𝒙′∈KV⁡\(G\)\\bm\{x\},\\bm\{x\}^\{\\prime\}\\in K^\{V\(G\)\}, every nodewise difference is at mostDKD\_\{K\}, so‖𝒙−𝒙′‖in≤DK\\\|\\bm\{x\}\-\\bm\{x\}^\{\\prime\}\\\|\_\{\\mathrm\{in\}\}\\leq D\_\{K\}\. UniformLL\-Lipschitzness then gives\|F⁡\(G,𝒙\)−F⁡\(G,𝒙′\)\|≤L​DK\|F\(G,\\bm\{x\}\)\-F\(G,\\bm\{x\}^\{\\prime\}\)\|\\leq LD\_\{K\}\. Thus the image of𝒙↦F⁡\(G,𝒙\)\\bm\{x\}\\mapsto F\(G,\\bm\{x\}\)has diameter at mostL​DKLD\_\{K\}, which proves the claim\. ∎

### A\.5Empirical averaging

In addition to analyzing the expressivity of the mean of random\-feature MPNNs, we also consider the complexity of finite\-sample estimation, which is required in practice\. To estimateμt​\(G\)\\mu\_\{t\}\(G\), drawssindependently initialized trialsX1,…,Xs∼PGX\_\{1\},\\ldots,X\_\{s\}\\sim P\_\{G\}and define

μ^t,s​\(G\)≔1s​∑i=1st⁡\(Xi\)\.\\widehat\{\\mu\}\_\{t,s\}\(G\)\\coloneq\\frac\{1\}\{s\}\\sum\_\{i=1\}^\{s\}t\(X\_\{i\}\)\.\(8\)For an MPNNFF, writeF^s=μ^F,s\\widehat\{F\}\_\{s\}=\\widehat\{\\mu\}\_\{F,s\}\. Then𝔼⁡\[F^s​\(G\)\]=F¯​\(G\)\\mathbb\{E\}\[\\widehat\{F\}\_\{s\}\(G\)\]=\\overline\{F\}\(G\)for everyss, so the number of trials affects estimation but not the represented population function\.

###### Definition 4\(Size\-uniform high\-probability approximation\)\.

For a graph invariantTT,ε≥0\\varepsilon\\geq 0,α∈\(0,1\)\\alpha\\in\(0,1\), ands∈ℕs\\in\\mathbb\{N\}, an MPNNFFsize\-uniformly approximatesTTwith errorε\\varepsilonand failure probability at mostα\\alphausingsstrials if

infG∈𝒢Pr⁡\(\|F^s​\(G\)−T⁡\(G\)\|≤ε\)≥1−α\.\\inf\_\{G\\in\\mathcal\{G\}\}\\Pr\\left\(\|\\widehat\{F\}\_\{s\}\(G\)\-T\(G\)\|\\leq\\varepsilon\\right\)\\geq 1\-\\alpha\.\(9\)

For theLL\-Lipschitz models we consider, population\-level approximation \(as in[Definition1](https://arxiv.org/html/2610.12809#Thmdefinition1)\) immediately gives a finite\-trial high\-probability approximation\. The key is that the required number of samples is constant for any fixed model, and in particular independent of graph size\.

###### Proposition 13\(Automatic finite\-trial bound\)\.

LetTTbe a graph invariant\. Forε\>0\\varepsilon\>0, suppose thatFFis uniformlyLL\-Lipschitz andsupG∈𝒢\|F¯​\(G\)−T⁡\(G\)\|≤ε/2\\sup\_\{G\\in\\mathcal\{G\}\}\|\\overline\{F\}\(G\)\-T\(G\)\|\\leq\\varepsilon/2\. Then, for anyα∈\(0,1\)\\alpha\\in\(0,1\), the invariantFFsize\-uniformly approximates the invariantTTwith errorε\\varepsilonand failure probability at mostα\\alphausing any number of trials satisfying

s≥2​L2​DK2ε2​log⁡2α\.s\\geq\\frac\{2L^\{2\}D\_\{K\}^\{2\}\}\{\\varepsilon^\{2\}\}\\log\\frac\{2\}\{\\alpha\}\.\(10\)

###### Proof\.

By[Lemma12](https://arxiv.org/html/2610.12809#Thmtheorem12), each of thessindependent trials averaged byF^s​\(G\)\\widehat\{F\}\_\{s\}\(G\)lies in an interval of length at mostL​DKLD\_\{K\}\. Hoeffding’s inequality therefore yields

Pr⁡\(\|F^s​\(G\)−F¯​\(G\)\|\>ε2\)\\displaystyle\\Pr\\left\(\|\\widehat\{F\}\_\{s\}\(G\)\-\\overline\{F\}\(G\)\|\>\\frac\{\\varepsilon\}\{2\}\\right\)\(11\)≤2​exp⁡\(−s​ε22​L2​DK2\)≤α\.\\displaystyle\\leq 2\\exp\\left\(\-\\frac\{s\\varepsilon^\{2\}\}\{2L^\{2\}D\_\{K\}^\{2\}\}\\right\)\\leq\\alpha\.Thus, with probability at least1−α1\-\\alpha,\|F^s​\(G\)−F¯​\(G\)\|≤ε/2\|\\widehat\{F\}\_\{s\}\(G\)\-\\overline\{F\}\(G\)\|\\leq\\varepsilon/2\. In this case, the triangle inequality and the population approximation hypothesis give

\|F^s​\(G\)−T​\(G\)\|\\displaystyle\|\\widehat\{F\}\_\{s\}\(G\)\-T\(G\)\|≤\|F^s​\(G\)−F¯​\(G\)\|\+\|F¯​\(G\)−T⁡\(G\)\|\\displaystyle\\leq\|\\widehat\{F\}\_\{s\}\(G\)\-\\overline\{F\}\(G\)\|\+\|\\overline\{F\}\(G\)\-T\(G\)\|\(12\)≤ε2\+ε2=ε\.\\displaystyle\\leq\\frac\{\\varepsilon\}\{2\}\+\\frac\{\\varepsilon\}\{2\}=\\varepsilon\.This bound is independent ofGGso taking the infimum over𝒢\\mathcal\{G\}completes the proof\. ∎

### A\.6Graph\-pair reductions and statistical distinguishability

We also consider whether random\-feature MPNNs distinguish graph pairs at the population level\. For an MPNNFF, define its population gap onG,H∈𝒢G,H\\in\\mathcal\{G\}by

gapF⁡\(G,H\)≔\|F¯​\(G\)−F¯​\(H\)\|\.\\operatorname\{gap\}\_\{F\}\(G,H\)\\coloneq\|\\overline\{F\}\(G\)\-\\overline\{F\}\(H\)\|\.\(13\)We say thatFFmean\-distinguishes the pair with marginΔ\\DeltaifgapF⁡\(G,H\)≥Δ\\operatorname\{gap\}\_\{F\}\(G,H\)\\geq\\Delta\.

We next connect the population gap to empirical isomorphism testing\. For a graph statistictt, anss\-trial test forG,HG,Hreceives two independent batches

𝒁A\\displaystyle\\bm\{Z\}\_\{A\}=\(Zt,1​\(A\),…,Zt,s​\(A\)\),\\displaystyle=\(Z\_\{t,1\}\(A\),\\ldots,Z\_\{t,s\}\(A\)\),\(14\)𝒁B\\displaystyle\\bm\{Z\}\_\{B\}=\(Zt,1​\(B\),…,Zt,s​\(B\)\),\\displaystyle=\(Z\_\{t,1\}\(B\),\\ldots,Z\_\{t,s\}\(B\)\),whereA,B∈\{G,H\}A,B\\in\\\{G,H\\\}and the entries of each batch are i\.i\.d\. with lawsPAtP\_\{A\}^\{t\}andPBtP\_\{B\}^\{t\}, respectively\. The test returns one when it declares that the batches came from different graphs\.

###### Definition 5\(Statistical distinguishability\)\.

Forα∈\(0,1/2\)\\alpha\\in\(0,1/2\), the pairG,HG,His statistically\(t,s,α\)\(t,s,\\alpha\)\-distinguishable if there is a testψ\\psisuch that

maxA,B∈\{G,H\}Pr\(ψ\(𝒁A,𝒁B\)≠𝟏\{A≠B\}\)≤α\.\\max\_\{A,B\\in\\\{G,H\\\}\}\\Pr\\left\(\\psi\(\\bm\{Z\}\_\{A\},\\bm\{Z\}\_\{B\}\)\\neq\\bm\{1\}\\\{A\\neq B\\\}\\right\)\\leq\\alpha\.\(15\)Thus the test must distinguish same from different in all four choices of\(A,B\)\(A,B\)\.

For observed batches𝒛,𝒛′∈ℝs\\bm\{z\},\\bm\{z\}^\{\\prime\}\\in\\mathbb\{R\}^\{s\}, consider the empirical\-mean test

φt,Δ,s\(𝒛,𝒛′\)≔𝟏\{\|1s∑i=1szi−1s∑i=1szi′\|\>Δ2\}\.\\varphi\_\{t,\\Delta,s\}\(\\bm\{z\},\\bm\{z\}^\{\\prime\}\)\\coloneq\\bm\{1\}\\left\\\{\\left\|\\frac\{1\}\{s\}\\sum\_\{i=1\}^\{s\}z\_\{i\}\-\\frac\{1\}\{s\}\\sum\_\{i=1\}^\{s\}z\_\{i\}^\{\\prime\}\\right\|\>\\frac\{\\Delta\}\{2\}\\right\\\}\.\(16\)
###### Proof of[Proposition2](https://arxiv.org/html/2610.12809#Thmtheorem2)\.

By[Lemma12](https://arxiv.org/html/2610.12809#Thmtheorem12), the outputs on each fixed graph lie in an interval of length at mostL​DKLD\_\{K\}\. Pairing the two batches, the empirical difference is therefore an average of independent variables with range length at most2​L​DK2LD\_\{K\}\. Its mean is zero whenA=BA=Band has absolute value at leastΔ\\DeltawhenA≠BA\\neq B\. An error requires a deviation of at leastΔ/2\\Delta/2, so Hoeffding’s inequality bounds every case by

2​exp⁡\(−s​Δ28​L2​DK2\)\.2\\exp\\left\(\-\\frac\{s\\Delta^\{2\}\}\{8L^\{2\}D\_\{K\}^\{2\}\}\\right\)\.\(17\)∎

Graph isomorphism testing will be particularly useful for bounding the power of random features\. Specifically, by contraposition, a lower bound against allss\-trial tests impliesgapF⁡\(G,H\)<Δ\\operatorname\{gap\}\_\{F\}\(G,H\)<\\Delta\. Finally, we can convert bounded population gap to non\-universality, in the function approximation framework\.

###### Corollary 14\(Non\-universality from graph pairs\)\.

Letℱ\\mathcal\{F\}be a class of random\-feature MPNNs\. Suppose that, for someβ<1\\beta<1, for everyF∈ℱF\\in\\mathcal\{F\}there exist non\-isomorphic graphsG,H∈𝒢G,H\\in\\mathcal\{G\}with

gapF⁡\(G,H\)≤β\.\\operatorname\{gap\}\_\{F\}\(G,H\)\\leq\\beta\.\(18\)Thenℱ\\mathcal\{F\}is not size\-uniformly universal\.

###### Proof\.

First, enumerate the isomorphism classes in𝒢\\mathcal\{G\}and consider the graph invariantT⋆:𝒢→ℕT\_\{\\star\}\\colon\\mathcal\{G\}\\to\\mathbb\{N\}that assigns each class its index\. If there is someFFthat approximatesT⋆T\_\{\\star\}uniformly with error strictly less than\(1−β\)/2\(1\-\\beta\)/2, thengapF⁡\(G,H\)\>β\\operatorname\{gap\}\_\{F\}\(G,H\)\>\\betaforGGandHHnon\-isomorphic, contradicting the hypothesis\. Henceℱ\\mathcal\{F\}does not size\-uniformly approximateT⋆T\_\{\\star\}\. ∎

## Appendix BQuantization for Size\-Uniform Function Approximation

### B\.1Quantization setup

For a finite nonempty paletteS⊂KS\\subset K, fix a quantization mapqS:K→Sq\_\{S\}\\colon K\\to Sand define its radius by

δ⁡\(S\)≔sup𝒛∈K‖𝒛−qS​\(𝒛\)‖\.\\delta\(S\)\\coloneq\\sup\_\{\\bm\{z\}\\in K\}\\\|\\bm\{z\}\-q\_\{S\}\(\\bm\{z\}\)\\\|\.\(19\)The corresponding nodewise quantization operator is\(QS​𝒙\)v≔qS​\(𝒙v\)\(Q\_\{S\}\\bm\{x\}\)\_\{v\}\\coloneq q\_\{S\}\(\\bm\{x\}\_\{v\}\)\. By construction,

‖𝒙−QS​𝒙‖in≤δ⁡\(S\)for every​𝒙∈KV⁡\(G\)\.\\\|\\bm\{x\}\-Q\_\{S\}\\bm\{x\}\\\|\_\{\\mathrm\{in\}\}\\leq\\delta\(S\)\\qquad\\text\{for every \}\\bm\{x\}\\in K^\{V\(G\)\}\.\(20\)Forδ\>0\\delta\>0, letNK​\(δ\)N\_\{K\}\(\\delta\)be the covering number ofKK\. SinceKKis compact, we may choose a paletteSδ⊂KS\_\{\\delta\}\\subset Kwith\|Sδ\|=NK​\(δ\)\|S\_\{\\delta\}\|=N\_\{K\}\(\\delta\)and takeqSδq\_\{S\_\{\\delta\}\}to be a nearest\-point map, so thatδ⁡\(Sδ\)≤δ\\delta\(S\_\{\\delta\}\)\\leq\\delta\. ThusQSδ​𝝃GQ\_\{S\_\{\\delta\}\}\\bm\{\\xi\}^\{G\}consists of i\.i\.d\. random colors drawn from a palette of sizeNK​\(δ\)N\_\{K\}\(\\delta\)\.

To make this concrete, takeK=\[0,1\]dK=\[0,1\]^\{d\}, and consider rounding to a uniform grid\. Form∈ℕm\\in\\mathbb\{N\}, let

Tm≔\{2​k−12​m:k=1,…,m\}⊂\[0,1\],Sm≔Tmd\.\\begin\{gathered\}T\_\{m\}\\coloneq\\left\\\{\\frac\{2k\-1\}\{2m\}\\colon k=1,\\ldots,m\\right\\\}\\subset\[0,1\],\\\\ S\_\{m\}\\coloneq T\_\{m\}^\{d\}\.\\end\{gathered\}\(21\)LetqSmq\_\{S\_\{m\}\}round each coordinate to the nearest point inSmS\_\{m\}, and abbreviateQm≔QSmQ\_\{m\}\\coloneq Q\_\{S\_\{m\}\}\. Let

κ≔sup\{‖𝒖‖:‖𝒖‖∞≤1\}\.\\kappa\\coloneq\\sup\\\{\\\|\\bm\{u\}\\\|\\colon\\\|\\bm\{u\}\\\|\_\{\\infty\}\\leq 1\\\}\.\(22\)Since rounding changes each coordinate by at most1/\(2​m\)1/\(2m\), we have

‖𝒙−Qm​𝒙‖in≤κ2​mfor every​𝒙∈\(\[0,1\]d\)V⁡\(G\)\.\\\|\\bm\{x\}\-Q\_\{m\}\\bm\{x\}\\\|\_\{\\mathrm\{in\}\}\\leq\\frac\{\\kappa\}\{2m\}\\qquad\\text\{for every \}\\bm\{x\}\\in\(\[0,1\]^\{d\}\)^\{V\(G\)\}\.\(23\)Consequently,

NK​\(κ2​m\)≤md\.N\_\{K\}\\left\(\\frac\{\\kappa\}\{2m\}\\right\)\\leq m^\{d\}\.\(24\)IfρK\\rho\_\{K\}is uniform, thenQm​𝝃GQ\_\{m\}\\bm\{\\xi\}^\{G\}is uniform on the paletteSmS\_\{m\}\. The random\-color WL results below use uniformly distributed colors\.

### B\.2Size\-uniform quantization

For an MPNNFFand a finite paletteS⊂KS\\subset K, define the population predictor obtained from the quantized features by

F¯S​\(G\)≔𝔼⁡\[F⁡\(G,QS​𝝃G\)\]\.\\overline\{F\}\_\{S\}\(G\)\\coloneq\\mathbb\{E\}\[F\(G,Q\_\{S\}\\bm\{\\xi\}^\{G\}\)\]\.\(25\)
###### Proposition 15\(Size\-uniform quantization\)\.

LetFFbe a uniformlyLL\-Lipschitz MPNN and letT:𝒢→ℝT\\colon\\mathcal\{G\}\\to\\mathbb\{R\}be a graph invariant\. Then, for every finite nonemptyS⊂KS\\subset K,

supG∈𝒢\|F¯S​\(G\)−T⁡\(G\)\|≤supG∈𝒢\|F¯​\(G\)−T⁡\(G\)\|\+L​δ​\(S\)\.\\sup\_\{G\\in\\mathcal\{G\}\}\|\\overline\{F\}\_\{S\}\(G\)\-T\(G\)\|\\leq\\sup\_\{G\\in\\mathcal\{G\}\}\|\\overline\{F\}\(G\)\-T\(G\)\|\+L\\delta\(S\)\.\(26\)

###### Proof\.

For every graphGG,

\|F¯S​\(G\)−F¯​\(G\)\|\\displaystyle\|\\overline\{F\}\_\{S\}\(G\)\-\\overline\{F\}\(G\)\|≤𝔼⁡\[\|F⁡\(G,QS​𝝃G\)−F⁡\(G,𝝃G\)\|\]\\displaystyle\\leq\\mathbb\{E\}\\bigl\[\|F\(G,Q\_\{S\}\\bm\{\\xi\}^\{G\}\)\-F\(G,\\bm\{\\xi\}^\{G\}\)\|\\bigr\]\(27\)≤L​δ​\(S\)\.\\displaystyle\\leq L\\delta\(S\)\.Taking the supremum over𝒢\\mathcal\{G\}and applying the triangle inequality completes the proof\. ∎

As a consequence, ifF¯\\overline\{F\}approximatesTTwith error at mostε/2\\varepsilon/2andL\>0L\>0, takingS=Sε/\(2​L\)S=S\_\{\\varepsilon/\(2L\)\}gives a predictor that usesNK​\(ε/\(2​L\)\)N\_\{K\}\(\\varepsilon/\(2L\)\)colors with error at mostε\\varepsilon\. For the midpoint grid on\[0,1\]d\[0,1\]^\{d\}, takingq=mdq=m^\{d\}gives the explicit rate

supG∈𝒢\|F¯Sm​\(G\)−T⁡\(G\)\|≤supG∈𝒢\|F¯​\(G\)−T⁡\(G\)\|\+L​κ2​q1/d\.\\sup\_\{G\\in\\mathcal\{G\}\}\|\\overline\{F\}\_\{S\_\{m\}\}\(G\)\-T\(G\)\|\\leq\\sup\_\{G\\in\\mathcal\{G\}\}\|\\overline\{F\}\(G\)\-T\(G\)\|\+\\frac\{L\\kappa\}\{2q^\{1/d\}\}\.\(28\)The palette size may depend on the target, accuracy, feature space, and Lipschitz constant, but not on graph size\.

Let𝒜\\mathcal\{A\}be the class of Lipschitz MPNNs with random node features supported onKK, and let𝒜color\\mathcal\{A\}\_\{\\mathrm\{color\}\}be the subclass of random\-color MPNNs as defined in[Section2](https://arxiv.org/html/2610.12809#S2)\.

###### Theorem 16\(Finite colors preserve the approximation class\)\.

The classes𝒜\\mathcal\{A\}and𝒜color\\mathcal\{A\}\_\{\\mathrm\{color\}\}uniformly approximate the same graph invariants\.

###### Proof\.

One direction follows from𝒜color⊆𝒜\\mathcal\{A\}\_\{\\mathrm\{color\}\}\\subseteq\\mathcal\{A\}\. For the other direction, suppose that𝒜\\mathcal\{A\}uniformly approximatesTT, and fixε\>0\\varepsilon\>0\. ChooseF∈𝒜F\\in\\mathcal\{A\}whose population predictor has error at mostε/2\\varepsilon/2, and letLLbe its uniform Lipschitz constant\. Choose a finite paletteSSsuch thatL​δ​\(S\)≤ε/2L\\delta\(S\)\\leq\\varepsilon/2\. Such a palette exists by compactness\. By[Proposition15](https://arxiv.org/html/2610.12809#Thmtheorem15), the quantized model belongs to𝒜color\\mathcal\{A\}\_\{\\mathrm\{color\}\}and approximatesTTwith error at mostε\\varepsilon\. ∎

### B\.3One\-hot and vector color encodings

The quantization reduction uses the vectors in a finite paletteS⊂KS\\subset Kas colors, while our later results use one\-hot vectors for simplicity\. We now compare these two representations\.

An encoding ofqqcolors in a feature spaceKKis an injectionc:\[q\]→Kc\\colon\[q\]\\to K\. The one\-hot encoding mapsiito the coordinate basis vector𝒆i∈ℝq\\bm\{e\}\_\{i\}\\in\\mathbb\{R\}^\{q\}\.

Letc~:\[q\]→K~\\widetilde\{c\}\\colon\[q\]\\to\\widetilde\{K\}be another encoding, and letϕ:K~→K\\phi\\colon\\widetilde\{K\}\\to KbeMM\-Lipschitz\. Define its conversion error as

η≔maxi∈\[q\]⁡‖ϕ⁡\(c~​\(i\)\)−c⁡\(i\)‖\.\\eta\\coloneq\\max\_\{i\\in\[q\]\}\\\|\\phi\(\\widetilde\{c\}\(i\)\)\-c\(i\)\\\|\.\(29\)For a coloringχ:V⁡\(G\)→\[q\]\\chi\\colon V\(G\)\\to\[q\], we can convert the encodings byc∘χ≔\(c⁡\(χv\)\)v∈V⁡\(G\)c\\circ\\chi\\coloneq\(c\(\\chi\_\{v\}\)\)\_\{v\\in V\(G\)\}\.

IfFFis uniformlyLL\-Lipschitz, then applyingϕ\\phinodewise beforeFFgives a uniformlyL​MLM\-Lipschitz model\. Moreover, for i\.i\.d\. colors drawn from any distribution on\[q\]\[q\], uniform Lipschitzness gives

supG∈𝒢\|𝔼​F​\(G,ϕ∘c~∘χ\)−𝔼​F​\(G,c∘χ\)\|≤L​η\.\\sup\_\{G\\in\\mathcal\{G\}\}\\bigl\|\\mathbb\{E\}F\(G,\\phi\\circ\\widetilde\{c\}\\circ\\chi\)\-\\mathbb\{E\}F\(G,c\\circ\\chi\)\\bigr\|\\leq L\\eta\.\(30\)
###### Proposition 17\(Encoding invariance\)\.

Fixqqand any distribution on\[q\]\[q\]\. Uniformly Lipschitz MPNNs using one\-hot colors and those using any injective vector encoding uniformly approximate the same graph invariants\.

###### Proof\.

For a fixed finite palette, a biased ReLU network can interpolate each of the assignments𝒆i↦c⁡\(i\)\\bm\{e\}\_\{i\}\\mapsto c\(i\)andc⁡\(i\)↦𝒆ic\(i\)\\mapsto\\bm\{e\}\_\{i\}exactly\. We implement the conversion using finitely many initial nodewise layers, setting𝑾agg\(ℓ\)=0\\bm\{W\}\_\{\\mathrm\{agg\}\}^\{\(\\ell\)\}=0in these layers\.333For signed target encodings, use a nonnegative shift and a constant coordinate, and absorb the shift into the first message\-passing layer\.Their depth, width, and weights may depend on the encodings, but not on graph size\. The conversion therefore has a graph\-size\-independent Lipschitz constant\. Composing it with the original MPNN gives the same output for every coloring\. The resulting population predictors are therefore identical, although their Lipschitz constants may differ by a factor that is independent of graph size\. ∎

TakingS=SδS=S\_\{\\delta\}andccto be a bijection from\[NK​\(δ\)\]\[N\_\{K\}\(\\delta\)\]ontoSδS\_\{\\delta\}shows that the vector colors produced by quantization and their one\-hot encodings have the same size\-uniform approximation power\.

## Appendix CIndistinguishability with Random Features Using CFI

In this section we introduce a family of graph pairs that requires an exponential number of trials in the graph size to distinguish with a fixed number of random colors\. Our construction applies beyond MPNNs to any test based on the WL patterns of these graphs\. The results of[Sections2](https://arxiv.org/html/2610.12809#S2)and[B](https://arxiv.org/html/2610.12809#A2)convert this trial lower bound into non\-universality of uniformly Lipschitz MPNNs with continuous random features for bounded graph invariants\. The construction gives this obstruction on connected graphs of maximum degree eight\. Adding a virtual node gives a second family of diameter two with the same trial lower bound, so non\-universality holds under either restriction separately\.

### C\.1Random\-color WL

We begin by defining random\-color WL, in which graph isomorphism testing is performed by comparing the WL patterns of two graphs over independent random coloring trials\. Forq∈ℕq\\in\\mathbb\{N\}, write\[q\]=\{1,…,q\}\[q\]=\\\{1,\\ldots,q\\\}\. For a coloringχ:V⁡\(G\)→\[q\]\\chi\\colon V\(G\)\\to\[q\], define the11\-WL pattern of a vertex recursively\. Set

π0G,χ​\(v\)≔χ⁡\(v\),\\pi\_\{0\}^\{G,\\chi\}\(v\)\\coloneq\\chi\(v\),\(31\)and, fort≥0t\\geq 0, let

πt\+1G,χ​\(v\)≔\(πtG,χ​\(v\),\{\{πtG,χ​\(u\):u∼v\}\}\)\.\\pi\_\{t\+1\}^\{G,\\chi\}\(v\)\\coloneq\\left\(\\pi\_\{t\}^\{G,\\chi\}\(v\),\\\{\\\!\\\{\\pi\_\{t\}^\{G,\\chi\}\(u\)\\colon u\\sim v\\\}\\\!\\\}\\right\)\.\(32\)Hereu∼vu\\sim vdenotes adjacency and\{\{⋅\}\}\\\{\\\!\\\{\\cdot\\\}\\\!\\\}denotes a multiset\. The complete11\-WL pattern ofvvis thenπG,χ​\(v\)≔\(πtG,χ​\(v\)\)t≥0\\pi^\{G,\\chi\}\(v\)\\coloneq\(\\pi\_\{t\}^\{G,\\chi\}\(v\)\)\_\{t\\geq 0\}\. The graph\-level observation is the unlabeled multiset

Π⁡\(G,χ\)≔\{\{πG,χ​\(v\):v∈V⁡\(G\)\}\}\.\\Pi\(G,\\chi\)\\coloneq\\\{\\\!\\\{\\pi^\{G,\\chi\}\(v\)\\colon v\\in V\(G\)\\\}\\\!\\\}\.\(33\)Sample a random coloringχG:V⁡\(G\)→\[q\]\\chi^\{G\}\\colon V\(G\)\\to\[q\]withχG​\(v\)​∼i\.i\.d\.​Unif⁡\(\[q\]\)\\chi^\{G\}\(v\)\\overset\{\\mathrm\{i\.i\.d\.\}\}\{\\sim\}\\operatorname\{Unif\}\(\[q\]\)and define

ZWL,q​\(G\)≔Π⁡\(G,χG\)\.Z\_\{\\mathrm\{WL\},q\}\(G\)\\coloneq\\Pi\(G,\\chi^\{G\}\)\.\(34\)We writePGWL,qP\_\{G\}^\{\\mathrm\{WL\},q\}for the law ofZWL,q​\(G\)Z\_\{\\mathrm\{WL\},q\}\(G\)\.

We use the same setting as[Definition5](https://arxiv.org/html/2610.12809#Thmdefinition5), with WL observations in place of scalar outputs\.

###### Definition 6\(Random\-color WL distinguishability\)\.

Forq,s∈ℕq,s\\in\\mathbb\{N\}andα∈\(0,1/2\)\\alpha\\in\(0,1/2\), a non\-isomorphic pairG,HG,His*statistically\(q,s,α\)\(q,s,\\alpha\)\-distinguishable by random\-color WL*if there is a binary\-valued, possibly randomized testψ\\psisatisfying the following\. For everyA,B∈\{G,H\}A,B\\in\\\{G,H\\\}, let

𝒁A\\displaystyle\\bm\{Z\}\_\{A\}=\(Z1​\(A\),…,Zs​\(A\)\),\\displaystyle=\(Z\_\{1\}\(A\),\\ldots,Z\_\{s\}\(A\)\),\(35\)𝒁B′\\displaystyle\\bm\{Z\}^\{\\prime\}\_\{B\}=\(Z1′​\(B\),…,Zs′​\(B\)\)\\displaystyle=\(Z^\{\\prime\}\_\{1\}\(B\),\\ldots,Z^\{\\prime\}\_\{s\}\(B\)\)be independent batches with i\.i\.d\. entries of lawsPAWL,qP\_\{A\}^\{\\mathrm\{WL\},q\}andPBWL,qP\_\{B\}^\{\\mathrm\{WL\},q\}, respectively\. Then

maxA,B∈\{G,H\}Pr\(ψ\(𝒁A,𝒁B′\)≠𝟏\{A≠B\}\)≤α\.\\max\_\{A,B\\in\\\{G,H\\\}\}\\Pr\\left\(\\psi\(\\bm\{Z\}\_\{A\},\\bm\{Z\}^\{\\prime\}\_\{B\}\)\\neq\\bm\{1\}\\\{A\\neq B\\\}\\right\)\\leq\\alpha\.\(36\)

The test may post\-process the complete WL observations arbitrarily and is not restricted to an empirical mean\. For a scalar\-output MPNNFFand a fixed color encodingc:\[q\]→Kc\\colon\[q\]\\to K, the observationZWL,q​\(G\)Z\_\{\\mathrm\{WL\},q\}\(G\)determines the network outputF⁡\(G,c∘χG\)F\(G,c\\circ\\chi^\{G\}\)by the standard11\-WL upper bound\[[31](https://arxiv.org/html/2610.12809#bib.bib31)\]\. Thus random\-color WL tests include all tests based on random\-color MPNN outputs\.

We now construct graph pairs whose random\-color WL distributions are exponentially close in total variation for any fixed number of colors\. The construction uses the parity gadget from[Cai et al\. \[4\]](https://arxiv.org/html/2610.12809#bib.bib4), which we refer to as the CFI gadget\. Letq≥2q\\geq 2denote the number of colors\.

### C\.2The parity gadget

The CFI gadget is designed to construct graphs whose isomorphism class depends on the parity of choices made across many local structures\.

The core gadget has three distinguished unordered vertex pairs

X=\(x0,x1\),Y=\(y0,y1\),Z=\(z0,z1\),X=\(x^\{0\},x^\{1\}\),\\qquad Y=\(y^\{0\},y^\{1\}\),\\qquad Z=\(z^\{0\},z^\{1\}\),\(37\)and four internal vertices

ga​b​c,\(a,b,c\)∈\{0,1\}3,a⊕b⊕c=0\.g\_\{abc\},\\qquad\(a,b,c\)\\in\\\{0,1\\\}^\{3\},\\qquad a\\oplus b\\oplus c=0\.\(38\)Here⊕\\oplusdenotes addition modulo two\. Each internal vertexga​b​cg\_\{abc\}is adjacent exactly to the three distinguished vertices

xa,yb,zc\.x^\{a\},\\quad y^\{b\},\\quad z^\{c\}\.\(39\)
x0\\scriptstyle x^\{0\}x1\\scriptstyle x^\{1\}y0\\scriptstyle y^\{0\}y1\\scriptstyle y^\{1\}z0\\scriptstyle z^\{0\}z1\\scriptstyle z^\{1\}Figure 4:The parity/CFI gadget\.The central property is that endpoint swaps extend to an automorphism over the entire gadget precisely when they have even parity\. Interpreting each swap as a bit flip, the third swap is therefore the XOR of the first two\. This is thek=3k=3case of Lemma 6\.1 of[Cai et al\. \[4\]](https://arxiv.org/html/2610.12809#bib.bib4)\.

###### Lemma 18\(Extension property of the parity gadget\)\.

LetsX,sY,sZ∈\{0,1\}s\_\{X\},s\_\{Y\},s\_\{Z\}\\in\\\{0,1\\\}, and letτ\\taube the permutation of the distinguished vertices that swaps the endpoints of pairXXifsX=1s\_\{X\}=1, swaps the endpoints of pairYYifsY=1s\_\{Y\}=1, and swaps the endpoints of pairZZifsZ=1s\_\{Z\}=1\.

Thenτ\\tauextends to an automorphism of the parity gadget if and only if

sX⊕sY⊕sZ=0\.s\_\{X\}\\oplus s\_\{Y\}\\oplus s\_\{Z\}=0\.\(40\)

### C\.3The graph pair family

We now compose the parity gadgets so that a parity choice made at any input pair can be transmitted to a single root pair\.

Fixk≥2k\\geq 2input vertex pairs

Xi=\(xi0,xi1\),i=1,…,k\.X\_\{i\}=\(x\_\{i\}^\{0\},x\_\{i\}^\{1\}\),\\qquad i=1,\\ldots,k\.\(41\)For eachii, attach two six\-vertex blocks to the input pair as follows\. Attachxi0x\_\{i\}^\{0\}to all six vertices of a copy of2​C32C\_\{3\}, and attachxi1x\_\{i\}^\{1\}to all six vertices of a copy ofC6C\_\{6\}\. Here2​C32C\_\{3\}is the disjoint union of two triangles andC6C\_\{6\}is a six\-cycle\. Thus the two sides of the input pair are non\-isomorphic as rooted attached blocks\.

Next, build a full binary tree of parity gadgets whose leaves are the input pairsX1,…,XkX\_\{1\},\\ldots,X\_\{k\}\. Each internal node of the tree is one copy of the parity gadget above\. We identify each child’s output pair with its parent’s input pair, matching superscripts\. The output of the tree is a final vertex pair

R=\(r0,r1\)\.R=\(r^\{0\},r^\{1\}\)\.\(42\)Finally, attach a marker leaf tor0r^\{0\}inG0G\_\{0\}and tor1r^\{1\}inG1G\_\{1\}\. We writeG0,k,G1,kG\_\{0,k\},G\_\{1,k\}when the dependence onkkmatters\. The2​k−12k\-1vertex pairs,k−1k\-1gadgets, attached blocks, and marker give

nk≔\|V⁡\(G0,k\)\|=\|V⁡\(G1,k\)\|=20​k−5\.n\_\{k\}\\coloneq\|V\(G\_\{0,k\}\)\|=\|V\(G\_\{1,k\}\)\|=20k\-5\.\(43\)Each input endpoint has degree eight, each intermediate endpoint has degree four, and every other vertex has degree at most three\. Thus both graphs are connected and have maximum degree eight\. The casek=4k=4is shown in[Figure5](https://arxiv.org/html/2610.12809#A3.F5)\.

Forj∈\{0,1\}j\\in\\\{0,1\\\}, letG^j,k\\widehat\{G\}\_\{j,k\}be obtained fromGj,kG\_\{j,k\}by adding a*virtual node*νj\\nu\_\{j\}adjacent to every original vertex, including the marker\. We omitkkwhen it is clear from context\. Then

n^k≔\|V⁡\(G^j,k\)\|=nk\+1=20​k−4\.\\widehat\{n\}\_\{k\}\\coloneq\|V\(\\widehat\{G\}\_\{j,k\}\)\|=n\_\{k\}\+1=20k\-4\.\(44\)The graphsG^j,k\\widehat\{G\}\_\{j,k\}have diameter two\. Their original vertices have degree at most nine, whileνj\\nu\_\{j\}has degreenkn\_\{k\}, so the virtual node is the unique vertex of degree greater than nine\. In random\-color WL, it receives an independent uniform color from the same palette as every other vertex\.

G0,4G\_\{0,4\}x10x\_\{1\}^\{0\}2​C32C\_\{3\}x11x\_\{1\}^\{1\}C6C\_\{6\}x20x\_\{2\}^\{0\}2​C32C\_\{3\}x21x\_\{2\}^\{1\}C6C\_\{6\}x30x\_\{3\}^\{0\}2​C32C\_\{3\}x31x\_\{3\}^\{1\}C6C\_\{6\}x40x\_\{4\}^\{0\}2​C32C\_\{3\}x41x\_\{4\}^\{1\}C6C\_\{6\}z10z\_\{1\}^\{0\}z11z\_\{1\}^\{1\}z20z\_\{2\}^\{0\}z21z\_\{2\}^\{1\}r0r^\{0\}r1r^\{1\}markerG1,4G\_\{1,4\}x10x\_\{1\}^\{0\}2​C32C\_\{3\}x11x\_\{1\}^\{1\}C6C\_\{6\}x20x\_\{2\}^\{0\}2​C32C\_\{3\}x21x\_\{2\}^\{1\}C6C\_\{6\}x30x\_\{3\}^\{0\}2​C32C\_\{3\}x31x\_\{3\}^\{1\}C6C\_\{6\}x40x\_\{4\}^\{0\}2​C32C\_\{3\}x41x\_\{4\}^\{1\}C6C\_\{6\}z10z\_\{1\}^\{0\}z11z\_\{1\}^\{1\}z20z\_\{2\}^\{0\}z21z\_\{2\}^\{1\}r0r^\{0\}r1r^\{1\}markerFigure 5:The CFI graph pair with four input pairs \(k=4k=4\)\. The intermediate pairs\(z10,z11\)\(z\_\{1\}^\{0\},z\_\{1\}^\{1\}\)and\(z20,z21\)\(z\_\{2\}^\{0\},z\_\{2\}^\{1\}\)are each shared by a child gadget and the root gadget\. Shading indicates vertex roles, not random colors\. The diameter\-two variants are obtained by adding one virtual node adjacent to every vertex shown in each graph\.
### C\.4Non\-isomorphism

We next verify that the graphsG0G\_\{0\}andG1G\_\{1\}, obtained by attaching the marker leaf tor0r^\{0\}andr1r^\{1\}, respectively, are non\-isomorphic\.

###### Lemma 19\.

The graphsG0G\_\{0\}andG1G\_\{1\}are not isomorphic\. The graphsG^0\\widehat\{G\}\_\{0\}andG^1\\widehat\{G\}\_\{1\}are also not isomorphic\.

###### Proof\.

Suppose thatγ:V⁡\(G0\)→V⁡\(G1\)\\gamma\\colon V\(G\_\{0\}\)\\to V\(G\_\{1\}\)is a graph isomorphism, and letmjm\_\{j\}be the marker leaf ofGjG\_\{j\}\. Since the marker and the unmarked root endpoint are the unique vertices of degrees one and two, respectively,γ⁡\(m0\)=m1\\gamma\(m\_\{0\}\)=m\_\{1\},γ⁡\(r0\)=r1\\gamma\(r^\{0\}\)=r^\{1\}, andγ⁡\(r1\)=r0\\gamma\(r^\{1\}\)=r^\{0\}\. The four internal vertices of the root gadget are precisely the neighbors ofr0r^\{0\}orr1r^\{1\}other than the marker\. Sinceγ\\gammapreserves adjacency and maps the root pair and marker to their counterparts, it maps this four\-vertex set inG0G\_\{0\}onto the corresponding set inG1G\_\{1\}\. The individual internal vertices may be permuted\.

For a gadget with output pairW=\(w0,w1\)W=\(w^\{0\},w^\{1\}\), letAAbe its set of four internal vertices\. Two distinct input verticesu,vu,vbelong to the same pair if and only ifN⁡\(u\)∩N⁡\(v\)∩A=∅N\(u\)\\cap N\(v\)\\cap A=\\varnothing, whereN⁡\(v\)N\(v\)denotes the neighborhood ofvv\. Sinceγ\\gammapreserves this condition, it maps input pairs to input pairs, possibly interchanging the two\. Such a pair is a leaf of the gadget tree exactly when its endpoints have degree eight\. Otherwise, the four internal vertices of its child gadget are the neighbors of its endpoints outsideAA\. Induction from the root therefore shows thatγ\\gammapreserves the pair–gadget tree, up to permutation of sibling subtrees\.

For each pairW=\(w0,w1\)W=\(w^\{0\},w^\{1\}\), letW′=\(u0,u1\)W^\{\\prime\}=\(u^\{0\},u^\{1\}\)be its image pair and definesW∈\{0,1\}s\_\{W\}\\in\\\{0,1\\\}by

γ⁡\(wb\)=ub⊕sW,b∈\{0,1\}\.\\gamma\(w^\{b\}\)=u^\{b\\oplus s\_\{W\}\},\\qquad b\\in\\\{0,1\\\}\.\(45\)Sinceγ\\gammaexchanges the root endpoints,sR=1s\_\{R\}=1\. At every input pairXiX\_\{i\}, the non\-isomorphic2​C32C\_\{3\}andC6C\_\{6\}attachments forcesXi=0s\_\{X\_\{i\}\}=0\. By[Lemma18](https://arxiv.org/html/2610.12809#Thmtheorem18), every gadget with input pairsX,YX,Yand output pairZZsatisfies

sZ=sX⊕sY\.s\_\{Z\}=s\_\{X\}\\oplus s\_\{Y\}\.\(46\)This relation is unchanged when we interchange the two input pairs\. We provesW=0s\_\{W\}=0for every pairWWby induction on the height of the subtree rooted atWW\. At height zero,WWis an input pairXiX\_\{i\}, for whichsXi=0s\_\{X\_\{i\}\}=0\. For the induction step, letZZbe the output pair of a gadget with input pairsX,YX,Y\. Their subtrees have smaller height, so the induction hypothesis givessX=sY=0s\_\{X\}=s\_\{Y\}=0\. HencesZ=sX⊕sY=0s\_\{Z\}=s\_\{X\}\\oplus s\_\{Y\}=0\. TakingW=RW=RgivessR=0s\_\{R\}=0, contradictingsR=1s\_\{R\}=1\.

Any isomorphism betweenG^0\\widehat\{G\}\_\{0\}andG^1\\widehat\{G\}\_\{1\}must mapν0\\nu\_\{0\}toν1\\nu\_\{1\}, since these are their unique vertices of degree greater than nine\. Deleting the virtual nodes would then give an isomorphism betweenG0G\_\{0\}andG1G\_\{1\}, which we have ruled out\. ∎

### C\.5Block erasure

We next identify an event under which the random coloring conceals the local difference between theC6C\_\{6\}and2​C32C\_\{3\}attachments at an input pair\. For each input pairXiX\_\{i\}, letBiB\_\{i\}be the event that both attached six\-vertex blocks are monochromatic\. The two blocks need not have the same color\.

Since a six\-vertex block is monochromatic with probabilityq−5q^\{\-5\}, we have

Pr⁡\(Bi\)=q−10\.\\Pr\(B\_\{i\}\)=q^\{\-10\}\.\(47\)
###### Lemma 20\(Block erasure\)\.

LetG∈\{G0,G1\}G\\in\\\{G\_\{0\},G\_\{1\}\\\}and letχ\\chibe a coloring for whichBiB\_\{i\}holds\. LetHHbe obtained fromGGby replacing the2​C32C\_\{3\}attachment atxi0x\_\{i\}^\{0\}withC6C\_\{6\}and theC6C\_\{6\}attachment atxi1x\_\{i\}^\{1\}with2​C32C\_\{3\}, on the same vertex sets and with all other edges unchanged\. Then

Π⁡\(G,χ\)=Π⁡\(H,χ\)\.\\Pi\(G,\\chi\)=\\Pi\(H,\\chi\)\.\(48\)

###### Proof\.

At round zero, corresponding vertices have the same color inGGandHH, and each replaced block is monochromatic\. Suppose that corresponding vertices have the same patterns at roundttand that all vertices within each replaced block share a pattern\. In both graphs, each block vertex has two neighbors within its block and one at the unchanged attachment endpoint\. Thus, at roundt\+1t\+1, corresponding block vertices have the same pattern, and all vertices within each block share a pattern\. All other vertices have unchanged neighborhoods, so their patterns also agree\. By induction, corresponding vertices have the same patterns at every round, and the graph\-level observations are equal\. ∎

### C\.6One erased input hides the root

The parity tree is designed so that concealing one input pair also conceals which root endpoint carries the marker leaf\.

LetB≔⋃i=1kBiB\\coloneq\\bigcup\_\{i=1\}^\{k\}B\_\{i\}be the event that at least one input block pair is erased\.

###### Lemma 21\.

Conditioned onBB, the random\-color WL sample distributions ofG0G\_\{0\}andG1G\_\{1\}are identical,

Law⁡\(ZWL,q​\(G0\)∣B\)=Law⁡\(ZWL,q​\(G1\)∣B\)\.\\operatorname\{Law\}\(Z\_\{\\mathrm\{WL\},q\}\(G\_\{0\}\)\\mid B\)=\\operatorname\{Law\}\(Z\_\{\\mathrm\{WL\},q\}\(G\_\{1\}\)\\mid B\)\.\(49\)The same equality holds withG^0\\widehat\{G\}\_\{0\}andG^1\\widehat\{G\}\_\{1\}in place ofG0G\_\{0\}andG1G\_\{1\}\.

###### Proof\.

OnBB, choose an erased input pairXiX\_\{i\}\. LetGcoreG\_\{\\mathrm\{core\}\}be the graph formed by the parity gadgets, without the attached blocks or marker\. We define an automorphismτi:V⁡\(Gcore\)→V⁡\(Gcore\)\\tau\_\{i\}\\colon V\(G\_\{\\mathrm\{core\}\}\)\\to V\(G\_\{\\mathrm\{core\}\}\)along the unique path fromXiX\_\{i\}toRRin the parity\-gadget tree\. For each pairW=\(w0,w1\)W=\(w^\{0\},w^\{1\}\), setsW=1s\_\{W\}=1ifWWlies on this path andsW=0s\_\{W\}=0otherwise, and define

τi​\(wb\)=wb⊕sW,b∈\{0,1\}\.\\tau\_\{i\}\(w^\{b\}\)=w^\{b\\oplus s\_\{W\}\},\\qquad b\\in\\\{0,1\\\}\.\(50\)Each gadget has either two incident pairs swapped or none, so its swap bits satisfysX⊕sY⊕sZ=0s\_\{X\}\\oplus s\_\{Y\}\\oplus s\_\{Z\}=0\. By[Lemma18](https://arxiv.org/html/2610.12809#Thmtheorem18), these swaps extend to a gadget automorphism\. Explicitly, on its internal vertices, set

τi​\(ga​b​c\)=ga⊕sX,b⊕sY,c⊕sZ\.\\tau\_\{i\}\(g\_\{abc\}\)=g\_\{a\\oplus s\_\{X\},\\,b\\oplus s\_\{Y\},\\,c\\oplus s\_\{Z\}\}\.\(51\)Since the gadget maps agree on shared pairs and the gadgets have disjoint internal vertex sets, these maps define an automorphismτi\\tau\_\{i\}ofGcoreG\_\{\\mathrm\{core\}\}\.

To extendτi\\tau\_\{i\}to a bijectionV⁡\(G0\)→V⁡\(G1\)V\(G\_\{0\}\)\\to V\(G\_\{1\}\), map the marker ofG0G\_\{0\}to that ofG1G\_\{1\}and fix all attached blocks except those atXiX\_\{i\}\. Exchange the two blocks atXiX\_\{i\}using a fixed bijection in one direction and its inverse in the other\. Sinceτi​\(rb\)=rb⊕1\\tau\_\{i\}\(r^\{b\}\)=r^\{b\\oplus 1\}, this extension preserves the marker edge\. The only edges it fails to preserve are within the exchanged2​C32C\_\{3\}andC6C\_\{6\}blocks\. For a coloringχ\\chisatisfyingBiB\_\{i\}, both blocks are monochromatic\. Thus[Lemma20](https://arxiv.org/html/2610.12809#Thmtheorem20)gives

Π⁡\(G0,χ\)=Π⁡\(G1,χ∘τi−1\)\.\\Pi\(G\_\{0\},\\chi\)=\\Pi\(G\_\{1\},\\chi\\circ\\tau\_\{i\}^\{\-1\}\)\.\(52\)Hereχ∘τi−1\\chi\\circ\\tau\_\{i\}^\{\-1\}assigns to each image vertex the color of its preimage\.

The coloring mapχ↦χ∘τi−1\\chi\\mapsto\\chi\\circ\\tau\_\{i\}^\{\-1\}preserves the set of erased input pairs\. If we use the same choice ofXiX\_\{i\}for each such set, this map is reversible and gives a bijection between the colorings satisfyingBB\. This bijection preserves their uniform conditional law\. Since matched colorings have identical WL observations, their laws agree conditioned onBB\.

For the virtual\-node graphs, extend each bijection by settingτi​\(ν0\)=ν1\\tau\_\{i\}\(\\nu\_\{0\}\)=\\nu\_\{1\}and carrying the color ofν0\\nu\_\{0\}toν1\\nu\_\{1\}\. This extension preserves all edges incident to the virtual node\. The only remaining discrepancies are within the two exchanged monochromatic blocks\. The induction in[Lemma20](https://arxiv.org/html/2610.12809#Thmtheorem20)still applies: each block vertex receives the additional pattern of the virtual node, and the two virtual nodes receive equal multisets of patterns from all original vertices\. Thus corresponding vertices have identical patterns at every round\. Since the virtual\-node color is independent ofBB, the extended coloring bijection also preserves the uniform conditional law\. ∎

### C\.7Total variation and sample complexity

We now convert the root\-hiding event into an upper bound on total variation and, subsequently, into a lower bound on the required number of trials\.

###### Proposition 22\(Upper bound on CFI total variation\)\.

The random\-color WL distributions ofG0G\_\{0\}andG1G\_\{1\}satisfy

TV⁡\(PG0WL,q,PG1WL,q\)≤\(1−q−10\)k\.\\operatorname\{TV\}\(P\_\{G\_\{0\}\}^\{\\mathrm\{WL\},q\},P\_\{G\_\{1\}\}^\{\\mathrm\{WL\},q\}\)\\leq\(1\-q^\{\-10\}\)^\{k\}\.\(53\)For fixedqq, this bound isexp⁡\(−Ω⁡\(k\)\)\\exp\(\-\\Omega\(k\)\)\. The same bound holds forG^0\\widehat\{G\}\_\{0\}andG^1\\widehat\{G\}\_\{1\}\.

###### Proof\.

By[Lemma21](https://arxiv.org/html/2610.12809#Thmtheorem21), the conditional laws onBBagree\. SinceBBhas the same probability in both graphs,

TV⁡\(PG0WL,q,PG1WL,q\)≤Pr⁡\(Bc\)\.\\operatorname\{TV\}\(P\_\{G\_\{0\}\}^\{\\mathrm\{WL\},q\},P\_\{G\_\{1\}\}^\{\\mathrm\{WL\},q\}\)\\leq\\Pr\(B^\{c\}\)\.\(54\)HereBcB^\{c\}denotes the complement ofBB, namely the event that no input block pair is erased\. The eventsBiB\_\{i\}are independent because they depend on disjoint attached blocks\. Therefore

Pr⁡\(Bc\)=∏i=1kPr⁡\(Bic\)=\(1−q−10\)k\.\\Pr\(B^\{c\}\)=\\prod\_\{i=1\}^\{k\}\\Pr\(B\_\{i\}^\{c\}\)=\(1\-q^\{\-10\}\)^\{k\}\.\(55\)The conditional\-law equality in[Lemma21](https://arxiv.org/html/2610.12809#Thmtheorem21)and the probabilities of the eventsBiB\_\{i\}are unchanged by adding the virtual node, so the same argument proves the bound forG^0,G^1\\widehat\{G\}\_\{0\},\\widehat\{G\}\_\{1\}\. ∎

###### Corollary 23\(Lower bound on the number of random\-color WL trials\)\.

Fixq≥2q\\geq 2andα∈\(0,1/2\)\\alpha\\in\(0,1/2\)\. If the pair\(G0,G1\)\(G\_\{0\},G\_\{1\}\)is statistically\(q,s,α\)\(q,s,\\alpha\)\-distinguishable by random\-color WL, then

s≥\(1−2​α\)​\(1−q−10\)−k\.s\\geq\(1\-2\\alpha\)\(1\-q^\{\-10\}\)^\{\-k\}\.\(56\)In particular, for fixedqqandα\\alpha, the required number of trials isexp⁡\(Ω⁡\(nk\)\)\\exp\(\\Omega\(n\_\{k\}\)\)\. The same lower bound holds for\(G^0,G^1\)\(\\widehat\{G\}\_\{0\},\\widehat\{G\}\_\{1\}\), withn^k\\widehat\{n\}\_\{k\}in place ofnkn\_\{k\}in the asymptotic statement\.

###### Proof\.

By[Proposition22](https://arxiv.org/html/2610.12809#Thmtheorem22)and subadditivity of total variation under products,ssindependent trials satisfy

TV⁡\(\(PG0WL,q\)⊗s,\(PG1WL,q\)⊗s\)≤s​\(1−q−10\)k\.\\operatorname\{TV\}\\\!\\left\(\(P\_\{G\_\{0\}\}^\{\\mathrm\{WL\},q\}\)^\{\\otimes s\},\(P\_\{G\_\{1\}\}^\{\\mathrm\{WL\},q\}\)^\{\\otimes s\}\\right\)\\leq s\(1\-q^\{\-10\}\)^\{k\}\.\(57\)HereP⊗QP\\otimes Qdenotes the joint law of independent draws fromPPandQQ, andP⊗sP^\{\\otimes s\}denotes the joint law ofssindependent draws fromPP\. LetPs≔\(PG0WL,q\)⊗sP\_\{s\}\\coloneq\(P\_\{G\_\{0\}\}^\{\\mathrm\{WL\},q\}\)^\{\\otimes s\}andQs≔\(PG1WL,q\)⊗sQ\_\{s\}\\coloneq\(P\_\{G\_\{1\}\}^\{\\mathrm\{WL\},q\}\)^\{\\otimes s\}\. A test with failure probability at mostα\\alphahas expected output at mostα\\alphaunderPs⊗PsP\_\{s\}\\otimes P\_\{s\}and at least1−α1\-\\alphaunderPs⊗QsP\_\{s\}\\otimes Q\_\{s\}\. Consequently,

1−2​α\\displaystyle 1\-2\\alpha≤TV⁡\(Ps⊗Ps,Ps⊗Qs\)\\displaystyle\\leq\\operatorname\{TV\}\(P\_\{s\}\\otimes P\_\{s\},P\_\{s\}\\otimes Q\_\{s\}\)\(58\)=TV⁡\(Ps,Qs\)\\displaystyle=\\operatorname\{TV\}\(P\_\{s\},Q\_\{s\}\)≤s​\(1−q−10\)k\.\\displaystyle\\leq s\(1\-q^\{\-10\}\)^\{k\}\.Rearranging gives the first claim\. The second follows fromnk=Θ⁡\(k\)n\_\{k\}=\\Theta\(k\)whenqqandα\\alphaare fixed\. For the virtual\-node pair, the same total\-variation bound applies andn^k=Θ⁡\(k\)\\widehat\{n\}\_\{k\}=\\Theta\(k\), giving the remaining claim\. ∎

### C\.8Non\-universality

We now use the trial lower bound to prove non\-universality for bounded graph invariants, separately on bounded\-degree graphs and bounded\-diameter graphs\.

###### Corollary 24\(Non\-universality from CFI pairs\)\.

The class of scalar\-output uniformly Lipschitz MPNNs with uniform initialization on\[0,1\]d\[0,1\]^\{d\}is not a size\-uniform universal approximator for bounded graph invariants on either of the following graph classes:

1. \(i\)connected graphs of maximum degree at most eight;
2. \(ii\)graphs of diameter two\.

###### Proof\.

Fix a uniformly Lipschitz modelFF\. By[Proposition15](https://arxiv.org/html/2610.12809#Thmtheorem15), choose a midpoint gridSmS\_\{m\}, withm≥2m\\geq 2, such that quantization changes each population mean by at most1/81/8, uniformly over graphs\. The quantized features are uniform on theq=mdq=m^\{d\}grid points\. The restriction ofFFtoSmS\_\{m\}remains uniformly Lipschitz\. By[Proposition2](https://arxiv.org/html/2610.12809#Thmtheorem2), a finite numberssof trials suffices to detect any quantized population gap of at least1/41/4with failure probability at most1/31/3\. These tests are also random\-color WL tests, and bothqqandssare independent of graph size\.

ChooseHj,k=Gj,kH\_\{j,k\}=G\_\{j,k\}for the first graph class andHj,k=G^j,kH\_\{j,k\}=\\widehat\{G\}\_\{j,k\}for the second\. For sufficiently largekk,[Corollary23](https://arxiv.org/html/2610.12809#Thmtheorem23)rules out statistical\(q,s,1/3\)\(q,s,1/3\)\-distinguishability of\(H0,k,H1,k\)\(H\_\{0,k\},H\_\{1,k\}\)\. The quantized population gap must therefore be less than1/41/4\. Including the two quantization errors givesgapF⁡\(H0,k,H1,k\)<1/2\\operatorname\{gap\}\_\{F\}\(H\_\{0,k\},H\_\{1,k\}\)<1/2\.

For the chosen graph class, define a bounded graph invariantTCFIT\_\{\\mathrm\{CFI\}\}to equal11on graphs isomorphic toH1,kH\_\{1,k\}for somek≥2k\\geq 2and00otherwise\. By[Lemma19](https://arxiv.org/html/2610.12809#Thmtheorem19)and the strictly increasing orders of each family, we haveTCFI​\(H0,k\)=0T\_\{\\mathrm\{CFI\}\}\(H\_\{0,k\}\)=0andTCFI​\(H1,k\)=1T\_\{\\mathrm\{CFI\}\}\(H\_\{1,k\}\)=1for everykk\. Uniform approximation toTCFIT\_\{\\mathrm\{CFI\}\}with error less than1/41/4would forcegapF⁡\(H0,k,H1,k\)\>1/2\\operatorname\{gap\}\_\{F\}\(H\_\{0,k\},H\_\{1,k\}\)\>1/2for everykk, contradicting the bound above\. Thus the model class fails to uniformly approximate a bounded graph invariant on each of the two graph classes\. ∎

### C\.9Colors and trials

The trial lower bound also quantifies the tradeoff between the number of colors and the number of trials\.

###### Corollary 25\(Colors and trials\)\.

Distinguishing the CFI pair\(G0,k,G1,k\)\(G\_\{0,k\},G\_\{1,k\}\)by random\-color WL with success probability at least2/32/3, usingq≥2q\\geq 2colors andsstrials per graph, requires

q10​log⁡\(3​s\)=Ω⁡\(nk\)\.q^\{10\}\\log\(3s\)=\\Omega\(n\_\{k\}\)\.\(59\)The same conclusion holds for\(G^0,k,G^1,k\)\(\\widehat\{G\}\_\{0,k\},\\widehat\{G\}\_\{1,k\}\)withn^k\\widehat\{n\}\_\{k\}in place ofnkn\_\{k\}\.

###### Proof\.

By[Corollary23](https://arxiv.org/html/2610.12809#Thmtheorem23)withα=1/3\\alpha=1/3,

log⁡\(3​s\)≥−k​log⁡\(1−q−10\)≥k​q−10\.\\log\(3s\)\\geq\-k\\log\(1\-q^\{\-10\}\)\\geq kq^\{\-10\}\.\(60\)Multiplying byq10q^\{10\}and usingnk=20​k−5n\_\{k\}=20k\-5proves the claim\. For the virtual\-node pair, the same trial lower bound andn^k=20​k−4\\widehat\{n\}\_\{k\}=20k\-4give the stated conclusion\. ∎

The number of colors enters this bound polynomially, whereas the number of trials enters only logarithmically\. Thus, compensating for a smaller color palette can require exponentially more trials\.

Conversely, one trial per graph withq=3​nk2q=3n\_\{k\}^\{2\}colors achieves success probability at least2/32/3\. By the union bound, both colorings are injective with probability at least1−2​\(nk2\)/q≥2/31\-2\\binom\{n\_\{k\}\}\{2\}/q\\geq 2/3\. On this event, one WL refinement determines each graph up to isomorphism\. Define the test to return zero if either coloring is not injective and otherwise compare the reconstructed graphs\. This test satisfies the required guarantee for everyA,B∈\{G0,k,G1,k\}A,B\\in\\\{G\_\{0,k\},G\_\{1,k\}\\\}\. Thus polynomially many colors suffice in a single trial, whereas any fixed number of colors requires exponentially many trials by[Corollary23](https://arxiv.org/html/2610.12809#Thmtheorem23)\. For the virtual\-node pair, the same injective\-coloring test usesq=3​n^k2q=3\\widehat\{n\}\_\{k\}^\{2\}colors\. Therefore this exponential separation holds both on graphs of maximum degree eight and, separately, on graphs of diameter two\.

## Appendix DSeparation from Uncolored 1\-WL

Now we show that random colors strictly increase expressive power over standard uncolored11\-WL\.

###### Proposition 26\(Random colors detect three\-step returns\)\.

For arbitrarily largenn, there arenn\-vertex graphsGn,HnG\_\{n\},H\_\{n\}that are11\-WL indistinguishable, but are separated by a depth\-33, uniformly Lipschitz random\-color MPNNFFusing two initial colors, withgapF⁡\(Gn,Hn\)=1/4\\operatorname\{gap\}\_\{F\}\(G\_\{n\},H\_\{n\}\)=1/4\.

###### Proof\.

For eachℓ≥1\\ell\\geq 1, setn=6​ℓn=6\\ell\. LetGnG\_\{n\}andHnH\_\{n\}be disjoint unions ofℓ\\ellcopies of2​C32C\_\{3\}andC6C\_\{6\}, respectively\. Both graphs are22\-regular onnnvertices, so uncolored11\-WL yields one color class of sizennat every round on both graphs\. Thus, the graphs are11\-WL indistinguishable\.

Define the normalized neighbor\-averaging operator𝑴G\\bm\{M\}\_\{G\}by

\(𝑴G​𝒙\)v≔1degG⁡\(v\)​∑u∼vxuif​degG⁡\(v\)\>0,\(\\bm\{M\}\_\{G\}\\bm\{x\}\)\_\{v\}\\coloneq\\frac\{1\}\{\\deg\_\{G\}\(v\)\}\\sum\_\{u\\sim v\}x\_\{u\}\\qquad\\text\{if \}\\deg\_\{G\}\(v\)\>0,\(61\)and set\(𝑴G​𝒙\)v=0\(\\bm\{M\}\_\{G\}\\bm\{x\}\)\_\{v\}=0at isolated vertices\. Write𝑴G3\\bm\{M\}\_\{G\}^\{3\}for three successive applications of this operator\. For initial features𝒙∈\[−1,1\]V⁡\(G\)\\bm\{x\}\\in\[\-1,1\]^\{V\(G\)\}, set

F⁡\(G,𝒙\)≔1\|V⁡\(G\)\|​∑v∈V⁡\(G\)\|xv\+\(𝑴G3​𝒙\)v\|\.F\(G,\\bm\{x\}\)\\coloneq\\frac\{1\}\{\|V\(G\)\|\}\\sum\_\{v\\in V\(G\)\}\\left\|x\_\{v\}\+\(\\bm\{M\}\_\{G\}^\{3\}\\bm\{x\}\)\_\{v\}\\right\|\.\(62\)The MPNN stores signed values through their positive and negative parts and performs normalized neighbor averaging\. In the third layer, it computes the absolute value using\|z\|=ReLU⁡\(z\)\+ReLU⁡\(−z\)\|z\|=\\operatorname\{ReLU\}\(z\)\+\\operatorname\{ReLU\}\(\-z\)\. Normalized averaging is nonexpansive in the max\-over\-nodes norm, and the final average does not introduce any dependence on\|V⁡\(G\)\|\|V\(G\)\|\. ThusFFis uniformly22\-Lipschitz\.

Let each vertex receive an independent uniform colorξv∈\{−1,1\}\\xi\_\{v\}\\in\\\{\-1,1\\\}\. The identity\|a\+b\|=1\+a​b\|a\+b\|=1\+abfora∈\{−1,1\}a\\in\\\{\-1,1\\\}andb∈\[−1,1\]b\\in\[\-1,1\]gives

F⁡\(G,𝝃G\)=1\+1\|V⁡\(G\)\|​∑v∈V⁡\(G\)ξv​\(𝑴G3​𝝃G\)v\.F\(G,\\bm\{\\xi\}^\{G\}\)=1\+\\frac\{1\}\{\|V\(G\)\|\}\\sum\_\{v\\in V\(G\)\}\\xi\_\{v\}\(\\bm\{M\}\_\{G\}^\{3\}\\bm\{\\xi\}^\{G\}\)\_\{v\}\.\(63\)LetrG​\(v\)r\_\{G\}\(v\)be the probability that a length\-33random walk fromvvreturns tovv\. The centered colors are independent with zero mean, so all terms withu≠vu\\neq vare zero in expectation, while𝔼​ξv2=1\\mathbb\{E\}\\xi\_\{v\}^\{2\}=1\. Therefore,

F¯​\(G\)=1\+1\|V⁡\(G\)\|​∑v∈V⁡\(G\)rG​\(v\)\.\\overline\{F\}\(G\)=1\+\\frac\{1\}\{\|V\(G\)\|\}\\sum\_\{v\\in V\(G\)\}r\_\{G\}\(v\)\.\(64\)On2​C32C\_\{3\}, this probability is1/41/4at every vertex, as the walk can go around its triangle in one of the two directions\. OnC6C\_\{6\}, it is00, sinceC6C\_\{6\}is bipartite and a walk of odd length cannot return to its starting vertex\. ThusF¯​\(Gn\)=5/4\\overline\{F\}\(G\_\{n\}\)=5/4andF¯​\(Hn\)=1\\overline\{F\}\(H\_\{n\}\)=1, givinggapF⁡\(Gn,Hn\)=1/4\\operatorname\{gap\}\_\{F\}\(G\_\{n\},H\_\{n\}\)=1/4\. ∎

By[Proposition2](https://arxiv.org/html/2610.12809#Thmtheorem2), this constant population gap yields statistical distinguishability using a constant number of trials\.

## Appendix EIncomparability with Higher\-Order WL

We now compare random\-color MPNNs with higher\-order WL, using statistical distinguishability as defined in[Definition6](https://arxiv.org/html/2610.12809#Thmdefinition6)\. Under the convention stated in the main text,kk\-WL colors orderedkk\-tuples of vertices\. Initially, a tuple’s color records equality and adjacency among its entries\. For an update, each vertexwwgives a list ofkkcolors: those of the tuples obtained by replacing the first entry byww, then the second, and so on\. The new color records the old color and the multiset of these lists over all verticesww\.

###### Theorem 27\(Incomparability with higher\-order WL\)\.

For everyk≥2k\\geq 2:

1. 1\.somekk\-WL\-indistinguishable pair is distinguished with success probability greater than2/32/3by a uniformly11\-Lipschitz two\-color MPNN with order\-normalized sum aggregation using one random\-color trial per graph;
2. 2\.for every fixedq,s≥1q,s\\geq 1, some pair distinguished by22\-WL, and hence bykk\-WL, is not statistically\(q,s,1/3\)\(q,s,1/3\)\-distinguishable by random\-color WL, and hence cannot be distinguished with the same guarantee by anyqq\-color MPNN usingsstrials\.

###### Proof\.

Random colors beatkk\-WL\.Choose connected, non\-isomorphic CFI graphsC0,C1C^\{0\},C^\{1\}onnnvertices, each of degree three, that arekk\-WL equivalent\[[4](https://arxiv.org/html/2610.12809#bib.bib4), Theorem 5\.2 and Corollary 6\.5\]\. Forget their colors; this preserveskk\-WL equivalence and non\-isomorphism\[[5](https://arxiv.org/html/2610.12809#bib.bib5), Corollary 7\.11\]\. Attach a pathv=v0,v1,…,vtv=v\_\{0\},v\_\{1\},\\ldots,v\_\{t\}to each original vertexvv, addingt=⌈log2⁡\(3​n2\)⌉t=\\lceil\\log\_\{2\}\(3n^\{2\}\)\\rceilnew vertices, and denote the resulting graphs byC^0,C^1\\widehat\{C\}^\{0\},\\widehat\{C\}^\{1\}, of orderN=n⁡\(t\+1\)N=n\(t\+1\)\. Each original vertex now has degree four, while the added vertices have degree one or two\. Any isomorphism between the new graphs would therefore map original vertices to original vertices, giving an isomorphism betweenC0C^\{0\}andC1C^\{1\}\. Thus the new graphs remain non\-isomorphic\.

We verify directly that attaching these paths also preserveskk\-WL equivalence\. Consider a tuple\(\(u1\)j1,…,\(uk\)jk\)\(\(u\_\{1\}\)\_\{j\_\{1\}\},\\ldots,\(u\_\{k\}\)\_\{j\_\{k\}\}\), whereuiu\_\{i\}is an original vertex andji∈\{0,…,t\}j\_\{i\}\\in\\\{0,\\ldots,t\\\}is a position on its attached path\. We claim that afterrriterations its color is determined by the path positions\(j1,…,jk\)\(j\_\{1\},\\ldots,j\_\{k\}\)and the color of\(u1,…,uk\)\(u\_\{1\},\\ldots,u\_\{k\}\)afterrriterations on the original graph\. Initially, the original tuple color records whichuiu\_\{i\}coincide and which are adjacent\. Together with the path positions, this determines equality and adjacency in the new tuple: edges either join consecutive positions on the same path or adjacent original vertices at position zero\.

For the induction step, every replacement vertex has the formwℓw\_\{\\ell\}\. Consider thekktuples obtained by replacing each entry in turn withwℓw\_\{\\ell\}\. By induction, their list of colors is determined by the corresponding list usingwwin the original graph, together with the path positions\. The next original WL color records its current color and the multiset of these lists over allww\. Repeating this for eachℓ∈\{0,…,t\}\\ell\\in\\\{0,\\ldots,t\\\}accounts for every replacement in the new graph, proving the claim\. Since the original graphs have identical tuple\-color counts at every iteration, the new graphs do too, for each choice of path positions\. HenceC^0\\widehat\{C\}^\{0\}andC^1\\widehat\{C\}^\{1\}remainkk\-WL equivalent\.

Independent uniform binary features give the original vertices independent uniform identifiers𝒛v=\(ξv1,…,ξvt\)\\bm\{z\}\_\{v\}=\(\\xi\_\{v\_\{1\}\},\\ldots,\\xi\_\{v\_\{t\}\}\), with

Pr⁡\{an identifier collision\}≤\(n2\)​2−t≤16\.\\Pr\\\{\\text\{an identifier collision\}\\\}\\leq\\binom\{n\}\{2\}2^\{\-t\}\\leq\\frac\{1\}\{6\}\.\(65\)We compute these identifiers directly with an order\-normalized sum MPNN\. Aggregating a constant\-one channel atuugivesdeg⁡\(u\)/N\\deg\(u\)/Non these graphs; multiplying by the fixed constantNNrecovers the degree\. We mark the degree\-one path tips and propagate this indicator to neighbors forttrounds, retaining previously reached vertices\. The vertexvjv\_\{j\}is first reached by this propagated indicator at roundt−jt\-j, so the first arrival time identifies its path position\. In particular, the original vertices are exactly those first reached at roundtt, so they can identify themselves\. Each vertexuuthen stores a binary matrixBu∈\{0,1\}2×tB\_\{u\}\\in\\\{0,1\\\}^\{2\\times t\}, whose\(i,j\)\(i,j\)entry indicates that colori∈\{0,1\}i\\in\\\{0,1\\\}has been observed at path positionjj\. Initialize all matrices to zero, then at each added vertex in positionjjwith colorii, set entry\(i,j\)\(i,j\)to one\. Fort−1t\-1rounds, each added vertex combines its own and its neighbors’ matrices entrywise by logical OR \(computed by summing and clipping at one\), while original vertices keep their matrices zero\. Every added vertex then learns its path’s complete matrix\. One further aggregation delivers this matrix to the original vertex through its unique path neighbor\. Its other neighbors are original vertices and contribute zero\. The matrix thus determines𝒛v\\bm\{z\}\_\{v\}\.

Next, original vertices exchange one\-hot encodings of their identifiers, with added vertices sending zero\. Each original vertex encodes its incident original edges in a matrix whose rows and columns are indexed by the2t2^\{t\}possible identifiers\. In the row indexed by its own identifier, it places a one in each column corresponding to a neighbor’s identifier; all other entries are zero\. Added vertices contribute zero matrices\. When identifiers are distinct, mean pooling followed by multiplication byNNgives the original graph’s adjacency matrix in these identifier coordinates\. Pooling the one\-hot identifiers alongside the matrices also gives the number of vertices with each identifier\. On the finite set of possible pooled inputs, a ReLU MLP can represent any function exactly\. We choose it to accept precisely whennndistinct identifiers occur, and the graph encoded on those identifiers is isomorphic toC0C^\{0\}\. A collision leaves fewer thannnoccupied identifiers and is rejected\. The resulting Boolean output satisfiesF⁡\(C^0\)=1F\(\\widehat\{C\}^\{0\}\)=1precisely on collision\-free inputs, andF⁡\(C^1\)=0F\(\\widehat\{C\}^\{1\}\)=0always\.

All the Boolean operations above have exact ReLU implementations\. The required neighbor sums are obtained by multiplying the order\-normalized sums by the fixed constantNN\.

By[Lemma1](https://arxiv.org/html/2610.12809#Thmtheorem1)and Lipschitzness of the fixed ReLU readout, this network has a finite size\-uniform Lipschitz boundLL\. Divide its output bymax⁡\{1,L\}\\max\\\{1,L\\\}to obtain a uniformly11\-Lipschitz network, without changing equality comparisons between outputs\. The architecture depends on the chosen pair; this is not a single size\-uniform recognition algorithm\. Writingp=Pr\{F\(C^0\)=1\}≥5/6p=\\Pr\\\{F\(\\widehat\{C\}^\{0\}\)=1\\\}\\geq 5/6for the unscaled output, declare the two inputs the same exactly when their independent single\-trial outputs agree\. The worst\-case success probability ismin⁡\{p2\+\(1−p\)2,1,p\}≥13/18\>2/3\\min\\\{p^\{2\}\+\(1\-p\)^\{2\},1,p\\\}\\geq 13/18\>2/3\.

22\-WL beats every fixed random\-color budget\.UseG0,m,G1,mG\_\{0,m\},G\_\{1,m\}from[AppendixC](https://arxiv.org/html/2610.12809#A3), withm=2hm=2^\{h\}input pairs and a perfect binary parity tree\. The marker is the unique degree\-one vertex, so22\-WL recognizes it\. LetQmQ\_\{m\}be the graph obtained by deleting the marker\. The pair colors reveal whether a replacement vertex is the marker, so22\-WL can recover its refinement onQmQ\_\{m\}by omitting this vertex from the updates\.

22\-WL distinguishes the attachments by their triangle counts: inQmQ\_\{m\}, each vertex of a2​C32C\_\{3\}attachment lies in three triangles, whereas each vertex of aC6C\_\{6\}attachment lies in two\. This separates the input endpointsxi0,xi1x\_\{i\}^\{0\},x\_\{i\}^\{1\}consistently in both graphs\. Once a gadget’s inputs are distinguished, its internal vertices count their superscript\-00input neighbors, so its output endpoints see the distinct count multisets\{2,0\}\\\{2,0\\\}and\{1,1\}\\\{1,1\\\}\. Since22\-WL refines ordinary color refinement, these distinctions propagate through successive parity gadgets up the tree, distinguishing the root endpointsr0,r1r^\{0\},r^\{1\}\. The marker’s attachment tor0r^\{0\}orr1r^\{1\}then distinguishes the two graphs\.

For fixedq≥2q\\geq 2ands≥1s\\geq 1, choosem=2hm=2^\{h\}large enough thats<13​\(1−q−10\)−ms<\\tfrac\{1\}\{3\}\(1\-q^\{\-10\}\)^\{\-m\}\. Then[Corollary23](https://arxiv.org/html/2610.12809#Thmtheorem23)rules out statistical\(q,s,1/3\)\(q,s,1/3\)\-distinguishability\. Forq=1q=1, every block pair is erased, so[Lemmas20](https://arxiv.org/html/2610.12809#Thmtheorem20)and[21](https://arxiv.org/html/2610.12809#Thmtheorem21)give identical11\-WL observations for every trial count\. The same indistinguishability bound extends to MPNNs\. ∎

## Appendix FSubgraph Isomorphism for Trees

We now adapt the color\-coding algorithm of[Alon et al\. \[2\]](https://arxiv.org/html/2610.12809#bib.bib2)to a random\-color MPNN\. Specifically, we show that for any rooted treeTTthere exists a random\-color MPNN that can decide at each vertexvvof a given graphGGif a copy ofTTis rooted atvv, using a number of layers, hidden dimension size, and number of trials independent of the size ofGG\. In this section, we use the MPNN architecture with coordinatewise max aggregation and binary vertex outputs\.

First we show that even graph\-level detection is impossible for standard MPNNs\.

###### Proposition 28\.

No MPNN with identical initial vertex features can decide whether an arbitrary graph contains a simple path of length three\.

###### Proof\.

The graphsC6C\_\{6\}and2​C32C\_\{3\}are both22\-regular on six vertices, so they are11\-WL indistinguishable and yield identical outputs under any such MPNN\. However,C6C\_\{6\}contains a simple path of length three, whereas2​C32C\_\{3\}does not\. ∎

LetG=\(V,E,χ\)G=\(V,E,\\chi\)be a colored graph withχ:V→\[k\]\\chi:V\\to\[k\]\. A set of verticesU⊆VU\\subseteq Vis*colorful*if all vertices inUUhave different colors\. For a graphHH, a*colorful subgraph embedding*is an injective edge\-preserving mapϕ:V⁡\(H\)→V⁡\(G\)\\phi\\colon V\(H\)\\to V\(G\)such thatim⁡ϕ\\im\\phiis colorful\. The embedded subgraph need not be an induced subgraph\.

LetT=\(V⁡\(T\),E⁡\(T\)\)T=\(V\(T\),E\(T\)\)be a rooted tree\. For a vertext∈V⁡\(T\)t\\in V\(T\), letTtT\_\{t\}denote the subtree ofTTwith roottt\.

###### Lemma 29\(Colorful tree subgraph isomorphism\)\.

LetTTbe a rooted tree withk≥1k\\geq 1vertices\. There is an MPNN that can determine, for each vertexvvof a colored graphG=\(V,E,χ\)G=\(V,E,\\chi\)withχ:V→\[k\]\\chi\\colon V\\to\[k\], whether there is a colorful subgraph embedding ofTTmapping its root tovv, with hidden dimensionexp⁡\(O⁡\(k\)\)\\exp\(O\(k\)\)andO⁡\(k\)O\(k\)message\-passing layers\.

###### Proof\.

We use a dynamic program to find colorful subgraph embeddings ofTT\. We first describe the dynamic program and prove its correctness\. We then show that this dynamic program can be implemented on an MPNN\.

Letrrbe the root ofTT\. The dynamic program iteratively adds edges to the graph using a post\-order traversal from the rootrr; whenever it visits a nonroot node, it adds the edge connecting that node to its parent\. At iterationi∈\{0,…,k−1\}i\\in\\\{0,\\ldots,k\-1\\\}, letT\(i\)T^\{\(i\)\}denote the spanning subgraph ofTTwith all edges added so far, and letTt\(i\)T^\{\(i\)\}\_\{t\}denote the subtree ofT\(i\)T^\{\(i\)\}at nodet∈V⁡\(T\)t\\in V\(T\), following edges away fromrr\. We use a dynamic programming tableDDwith entries corresponding toV⁡\(G\)×V⁡\(T\)×\{0,…,k−1\}×𝒫⁡\(\[k\]\)V\(G\)\\times V\(T\)\\times\\\{0,\\ldots,k\-1\\\}\\times\\mathcal\{P\}\(\[k\]\), where𝒫⁡\(\[k\]\)\\mathcal\{P\}\(\[k\]\)denotes the power set of\[k\]\[k\]\. The dynamic programming table will storeTrue\\True/False\\Falsecorresponding to

D⁡\[v,t,i,S\]=There is a colorful subgraph embeddingϕfrom the subtreeTt\(i\)toGsuch thatϕ⁡\(t\)=vandχ⁡\(im⁡ϕ\)=S\.\\begin\{gathered\}D\[v,\\,t,\\,i,\\,S\]=\\\\ \\begin\{aligned\} &\\text\{There is a colorful subgraph embedding $\\phi$\}\\\\ &\\text\{from the subtree $T^\{\(i\)\}\_\{t\}$ to $G$\}\\\\ &\\text\{such that $\\phi\(t\)=v$ and $\\chi\(\\im\\phi\)=S$\}\.\\end\{aligned\}\\end\{gathered\}\(66\)Clearly, there is a colorful embedding fromTTtoGGmappingrrtovvif and only ifD⁡\[v,r,k−1,\[k\]\]D\[v,r,k\-1,\[k\]\]isTrue\\True\.

The base case of the dynamic program consists of singleton trees\. For all verticesv∈V⁡\(G\)v\\in V\(G\)and nodest∈V⁡\(T\)t\\in V\(T\), we set the entryD⁡\[v,t,0,\{χ⁡\(v\)\}\]=TrueD\[v,t,0,\\\{\\chi\(v\)\\\}\]=\\Trueasttis the only node in the subtreeTt\(0\)T^\{\(0\)\}\_\{t\}\. All other entries at iteration zero areFalse\\False\.

Let\{a,p\}\\\{a,p\\\}be the edge added at iterationii, whereaais the child andppis the parent\. We only need to update the dynamic programming table entries corresponding topp, since the subtrees at all other nodes remain the same\.

D⁡\[v,p,i,S\]=\{Trueif​D​\[v,p,i−1,S′\]=Trueand​D​\[u,a,i−1,S′′\]=Truefor some neighbor​u​of​vand some decompositionS=S′⊔S′′\.Falseotherwise,\\begin\{gathered\}D\[v,\\,p,\\,i,\\,S\]=\\\\ \\begin\{cases\}\\True&\\begin\{aligned\} &\\text\{if \}D\[v,p,i\-1,S^\{\\prime\}\]=\\True\\\\ &\\text\{and \}D\[u,a,i\-1,S^\{\\prime\\prime\}\]=\\True\\\\ &\\text\{for some neighbor \}u\\text\{ of \}v\\\\ &\\text\{and some decomposition\}\\\\ &S=S^\{\\prime\}\\sqcup S^\{\\prime\\prime\}\.\\end\{aligned\}\\\\ \\False&\\text\{otherwise,\}\\end\{cases\}\\end\{gathered\}\(67\)where⊔\\sqcupdenotes disjoint union\. Fort≠pt\\neq p, setD⁡\[v,t,i,S\]=D⁡\[v,t,i−1,S\]D\[v,t,i,S\]=D\[v,t,i\-1,S\]\. As a sketch of why this is correct, observe that any colorful embeddingϕ\\phiofTp\(i\)T^\{\(i\)\}\_\{p\}withϕ⁡\(p\)=v\\phi\(p\)=vwill have to mapaato a neighboruuofvv, so it can be decomposed as embeddings ofTp\(i−1\)T^\{\(i\-1\)\}\_\{p\}andTa\(i−1\)T^\{\(i\-1\)\}\_\{a\}\. If we can guarantee embeddings of these trees rooted atvvanduuexist, and their images have disjoint color sets, then this implies they can be combined to an embedding ofTp\(i\)T^\{\(i\)\}\_\{p\}rooted atvv\(the images won’t share nodes as they have different colors\)\. Induction over the added edges proves correctness\.

We now argue that message passing can achieve this\. We initialize node features as one\-hot vectors inℝk\\mathbb\{R\}^\{k\}corresponding to node colorsχ⁡\(v\)\\chi\(v\)\. Our hidden vectors between iterations will be of sizek×2kk\\times 2^\{k\}; after iterationii, the node feature𝒉v\(i\)\\bm\{h\}^\{\(i\)\}\_\{v\}will correspond to the dynamic programming table entryD⁡\[v,⋅,i,⋅\]D\[v,\\cdot,i,\\cdot\]\. Accordingly, we index our node features by𝒉v\(i\)​\[t,S\]\\bm\{h\}\_\{v\}^\{\(i\)\}\[t,S\]fort∈V⁡\(T\)t\\in V\(T\)andS⊆\[k\]S\\subseteq\[k\]\. Our MPNN will then have𝒉v\(i\)​\[t,S\]=1\\bm\{h\}\_\{v\}^\{\(i\)\}\[t,S\]=1ifD⁡\[v,t,i,S\]=TrueD\[v,t,i,S\]=\\Trueand𝒉v\(i\)​\[t,S\]=0\\bm\{h\}\_\{v\}^\{\(i\)\}\[t,S\]=0otherwise\. Hereiiindexes dynamic\-programming iterations, each implemented by a constant number of MPNN layers\.

Initially, we apply a linear encoding layer that sets𝒉v\(0\)​\[t,\{χ⁡\(v\)\}\]=1\\bm\{h\}\_\{v\}^\{\(0\)\}\[t,\\\{\\chi\(v\)\\\}\]=1for all nodest∈V⁡\(T\)t\\in V\(T\), with all other entries zero\. Our message\-passing updates will be of the form

𝒎v\(i\)\\displaystyle\\bm\{m\}\_\{v\}^\{\(i\)\}=maxu∈NG​\(v\)⁡𝒉u\(i−1\),\\displaystyle=\\max\_\{u\\in N\_\{G\}\(v\)\}\\bm\{h\}\_\{u\}^\{\(i\-1\)\},\(68\)𝒉v\(i\)\\displaystyle\\bm\{h\}\_\{v\}^\{\(i\)\}=fi​\(𝒉v\(i−1\),𝒎v\(i\)\),\\displaystyle=f\_\{i\}\\left\(\\bm\{h\}\_\{v\}^\{\(i\-1\)\},\\bm\{m\}\_\{v\}^\{\(i\)\}\\right\),where the maximum is coordinatewise, andfif\_\{i\}is a ReLU MLP\. At isolated vertices, set𝒎v\(i\)=0\\bm\{m\}\_\{v\}^\{\(i\)\}=0\.

We will repeatedly make use of the fact that a two\-layer ReLU MLP can implement a threshold functionf⁡\(x\)=ReLU⁡\(x\)−ReLU⁡\(x−1\)f\(x\)=\\relu\(x\)\-\\relu\(x\-1\)with the property thatf⁡\(x\)=1f\(x\)=1forx≥1x\\geq 1andf⁡\(x\)=0f\(x\)=0forx≤0x\\leq 0\.

Each iteration will then correspond to adding an edge to the tree\. Max aggregation gives𝒎v\(i\)​\[a,S′′\]=1\\bm\{m\}\_\{v\}^\{\(i\)\}\[a,S^\{\\prime\\prime\}\]=1iffD⁡\[u,a,i−1,S′′\]=TrueD\[u,a,i\-1,S^\{\\prime\\prime\}\]=\\Truefor some neighboruuofvv\. For eachS⊆\[k\]S\\subseteq\[k\], we compute the update

fi​\(𝒉v\(i−1\),𝒎v\(i\)\)​\[p,S\]=f⁡\(∑S=S′⊔S′′ReLU⁡\(𝒉v\(i−1\)​\[p,S′\]CLOSECLOSEOPENOPEN\+𝒎v\(i\)​\[a,S′′\]−1\)\)\.\\begin\{multlined\}f\_\{i\}\\left\(\\bm\{h\}\_\{v\}^\{\(i\-1\)\},\\bm\{m\}\_\{v\}^\{\(i\)\}\\right\)\[p,S\]\\\\ =f\\\!\\Biggl\(\\sum\_\{S=S^\{\\prime\}\\sqcup S^\{\\prime\\prime\}\}\\relu\\\!\\Bigl\(\\bm\{h\}\_\{v\}^\{\(i\-1\)\}\[p,S^\{\\prime\}\]\\\\ \{\}\+\\bm\{m\}\_\{v\}^\{\(i\)\}\[a,S^\{\\prime\\prime\}\]\-1\\Bigr\)\\Biggr\)\.\\end\{multlined\}\(69\)Thus, this entry is 1 iff there existsS′⊔S′′=SS^\{\\prime\}\\sqcup S^\{\\prime\\prime\}=Ssuch thatD⁡\[v,p,i−1,S′\]D\[v,p,i\-1,S^\{\\prime\}\]andD⁡\[u,a,i−1,S′′\]D\[u,a,i\-1,S^\{\\prime\\prime\}\]are true for some neighboruuofvv\. This can be implemented by a three\-layer ReLU MLP with hidden dimensionO⁡\(k​4k\)O\(k4^\{k\}\)\. The first layer takes the sum of𝒉v\(i−1\)​\[p,S′\]\\bm\{h\}\_\{v\}^\{\(i\-1\)\}\[p,S^\{\\prime\}\]and𝒎v\(i\)​\[a,S′′\]\\bm\{m\}\_\{v\}^\{\(i\)\}\[a,S^\{\\prime\\prime\}\], subtracts 1, and applies ReLU, storing it in an intermediate feature\[p,S′,S′′\]\[p,S^\{\\prime\},S^\{\\prime\\prime\}\]\. This feature is 1 iff both inputs are 1\. The final two layers sum up over all choices ofS′⊔S′′=SS^\{\\prime\}\\sqcup S^\{\\prime\\prime\}=Sand take a threshold\. These two layers set neighbor weights to zero, and copy all entries fort≠pt\\neq punchanged through the self\-update\.

Afterk−1k\-1iterations, the vertex output𝒉v\(k−1\)​\[r,\[k\]\]\\bm\{h\}\_\{v\}^\{\(k\-1\)\}\[r,\[k\]\]is 1 iff a colorful copy ofTTis rooted atvv, and 0 otherwise\. Including initialization, the construction usesO⁡\(k\)O\(k\)layers and hidden dimensionO⁡\(k​4k\)=exp⁡\(O⁡\(k\)\)O\(k4^\{k\}\)=\\exp\(O\(k\)\), with parameters depending only onTT\. ∎

###### Theorem 30\(Random\-color MPNN for rooted tree detection\)\.

LetTTbe a rooted tree withk≥1k\\geq 1vertices\. There is a random\-color MPNN usingkkinitial colors, hidden dimensionexp⁡\(O⁡\(k\)\)\\exp\(O\(k\)\), andO⁡\(k\)O\(k\)message\-passing layers, using max aggregation and binary vertex outputs, with the following guarantee\. For every graphGGand vertexv∈V⁡\(G\)v\\in V\(G\), one random\-color trial accepts atvvonly ifGGcontains a copy ofTTrooted atvv\. If such a copy exists, then one trial accepts atvvwith probability at least

k\!kk\.\\frac\{k\!\}\{k^\{k\}\}\.\(70\)Consequently, for anyα∈\(0,1\)\\alpha\\in\(0,1\), running

s=⌈kkk\!​log⁡\(1/α\)⌉s=\\left\\lceil\\frac\{k^\{k\}\}\{k\!\}\\log\(1/\\alpha\)\\right\\rceil\(71\)independent trials and accepting atvvwhen its average binary output is positive \(equivalently, when any trial accepts atvv\) decides whetherGGcontains a copy ofTTrooted atvvwith false\-positive probability00and false\-negative probability at mostα\\alphafor eachvv\.

###### Proof\.

Use the colored MPNN from Lemma[29](https://arxiv.org/html/2610.12809#Thmtheorem29)with color set\[k\]\[k\]\. In one random\-color trial, each vertex ofGGreceives an independent uniform color from\[k\]\[k\], and the colored MPNN checks at eachvvfor a colorful copy ofTTrooted atvv\. If the trial accepts atvv, then the detected colorful copy is in particular an uncolored copy ofTTrooted atvv, so there are no false positives\.

Fixvvsuch thatGGcontains a copy ofTTrooted atvv, and fix one such copy\. Thekkvertices of this copy receive distinct colors with probabilityk\!/kkk\!/k^\{k\}\. On this event, the fixed copy is colorful, so the colored MPNN accepts atvv\. Thus one trial accepts atvvwith probability at leastk\!/kkk\!/k^\{k\}\. Forssindependent trials, the false\-negative probability atvvis at most

\(1−k\!kk\)s≤exp⁡\(−s​k\!kk\)≤α\.∎\\left\(1\-\\frac\{k\!\}\{k^\{k\}\}\\right\)^\{s\}\\leq\\exp\\left\(\-s\\frac\{k\!\}\{k^\{k\}\}\\right\)\\leq\\alpha\.\\qed\(72\)

Participation in any role follows by running all choices of the pattern root in parallel and taking the maximum at each vertex, with the same asymptotic resource bounds\.

###### Corollary 31\(Tree subgraph detection\)\.

For every treeTTandα∈\(0,1\)\\alpha\\in\(0,1\), max\-over\-nodes readout in[Theorem30](https://arxiv.org/html/2610.12809#Thmtheorem30)detects whether a graph contains a subgraph isomorphic toTT, with the same resource and trial bounds, no false positives, and false\-negative probability at mostα\\alpha\.

###### Proof\.

RootTTarbitrarily and take the maximum over vertex outputs in each trial\. A positive graph contains a fixed copy rooted at some vertex, whose miss probability is at mostα\\alpha; a negative graph has no positive vertex outputs\. For the empty graph, set the readout to zero\. ∎

###### Corollary 32\(Detecting simple paths\)\.

For everyk≥1k\\geq 1, there is a random\-color MPNN that detects whether a graph contains a simple path of lengthkk, meaning a path withkkedges andk\+1k\+1vertices, usingk\+1k\+1initial colors, hidden dimensionexp⁡\(O⁡\(k\)\)\\exp\(O\(k\)\), andO⁡\(k\)O\(k\)message\-passing layers\. One trial has no false positives and accepts with probability at least

\(k\+1\)\!\(k\+1\)k\+1\\frac\{\(k\+1\)\!\}\{\(k\+1\)^\{k\+1\}\}\(73\)whenever such a path exists\. Hence, for anyα∈\(0,1\)\\alpha\\in\(0,1\),

s=⌈\(k\+1\)k\+1\(k\+1\)\!​log⁡\(1/α\)⌉s=\\left\\lceil\\frac\{\(k\+1\)^\{k\+1\}\}\{\(k\+1\)\!\}\\log\(1/\\alpha\)\\right\\rceil\(74\)independent trials give false\-positive probability00and false\-negative probability at mostα\\alpha\.

###### Proof\.

Apply Corollary[31](https://arxiv.org/html/2610.12809#Thmtheorem31)to the path tree onk\+1k\+1vertices\. ∎

## Appendix GA Local MST Edge Task

We next consider a local task for computing MST edges\. LetG=\(V,E\)G=\(V,E\)be a simple graph with edge weightsw:E→Λw\\colon E\\to\\Lambda, whereΛ\\Lambdais a fixed finite ordered alphabet\. We aim to identify edges that uniquely minimize the weight across a cutS⊂VS\\subset Vwith\|S\|<k\|S\|<k\. Fork≥\|V\|k\\geq\|V\|, this is exactly the set of edges occurring in every MST \(or every minimum spanning forest ifGGis disconnected\)\.

An edge belongs to every MST if and only if it is the unique minimum\-weight edge crossing some cut\. The cut, however, may have many vertices on both sides\. We therefore consider a local version of this task, identifying only edges whose membership in every MST can be established by a cut with fewer thankkvertices on one side\.

Fix an integerk≥2k\\geq 2, and letδG​\(S\)\\delta\_\{G\}\(S\)denote the edges with exactly one endpoint inSS\. This constrained edge set is

Ak​\(G,w\)≔\{e∈E:∃S⊂V,\|S\|<k,e∈δG\(S\),w⁡\(e\)<w⁡\(f\)​for all​f∈δG​\(S\)∖\{e\}\}\.\\begin\{gathered\}A\_\{k\}\(G,w\)\\coloneq\\\\ \\left\\\{e\\in E\\colon\\;\\begin\{aligned\} &\\exists S\\subset V,\\ \|S\|<k,\\ e\\in\\delta\_\{G\}\(S\),\\\\ &w\(e\)<w\(f\)\\ \\text\{for all \}f\\in\\delta\_\{G\}\(S\)\\setminus\\\{e\\\}\\end\{aligned\}\\right\\\}\.\\end\{gathered\}\(75\)
To identify edges inAkA\_\{k\}, we look for a small component separated from the opposite endpoint after removing the candidate edge and all heavier edges\. Fore=u​ve=uv, define

De≔\(V,\{f∈E∖\{e\}:w⁡\(f\)≤w⁡\(e\)\}\),D\_\{e\}\\coloneq\(V,\\\{f\\in E\\setminus\\\{e\\\}\\colon w\(f\)\\leq w\(e\)\\\}\),\(76\)and letCe​\(v\)C\_\{e\}\(v\)denote the connected component ofvvinDeD\_\{e\}\. If the endpoints are separated,eeis uniquely lightest across the boundary of either component\. A component with fewer thankkvertices therefore gives the required cut\. Conversely, any qualifying setSScontains the component of its endpoint\. Hence,

e∈Ak\(G,w\)⟺Ce\(u\)≠Ce\(v\)andmin\{\|Ce\(u\)\|,\|Ce\(v\)\|\}<k\.e\\in A\_\{k\}\(G,w\)\\quad\\Longleftrightarrow\\quad C\_\{e\}\(u\)\\neq C\_\{e\}\(v\)\\ \\text\{and\}\\ \\min\\\{\|C\_\{e\}\(u\)\|,\|C\_\{e\}\(v\)\|\\\}<k\.\(77\)
We use the edge\-feature extension of message passing: messages may depend on the sender’s state and a fixed encoding of the edge weight\. Coordinatewise max aggregation and updates implement the filters below using the initial colors, which are retained in the node states\. The edge decoder is a shared ReLU MLP of the formd⁡\(𝒉u\+𝒉v,w⁡\(u​v\)\)d\(\\bm\{h\}\_\{u\}\+\\bm\{h\}\_\{v\},w\(uv\)\), where𝒉u,𝒉v\\bm\{h\}\_\{u\},\\bm\{h\}\_\{v\}are the final endpoint embeddings\. An empty maximum is taken to be zero\.

The next proposition shows that random colors allow a random color MPNN to compute this task for constantkk\.

###### Proposition 33\(Finite\-color local Kruskal edge detection\)\.

Fix an integerk≥2k\\geq 2, a finite ordered alphabetΛ\\Lambda, andε,α∈\(0,1\)\\varepsilon,\\alpha\\in\(0,1\)\. There is a finite\-color edge\-output MPNN, using a constant number of independent random\-color trials, such that for every weighted graphGGwith weights inΛ\\Lambda, the random outputA^⊆E⁡\(G\)\\widehat\{A\}\\subseteq E\(G\)satisfies

Pr⁡\{\|A^∩Ak\|≥\(1−ε\)​\|Ak\|and\|A^∖Ak\|≤ε​\|E∖Ak\|\}≥1−α\.\\Pr\\left\\\{\\begin\{gathered\}\|\\widehat\{A\}\\cap A\_\{k\}\|\\geq\(1\-\\varepsilon\)\|A\_\{k\}\|\\\\ \\text\{ and \}\\\\ \|\\widehat\{A\}\\setminus A\_\{k\}\|\\leq\\varepsilon\|E\\setminus A\_\{k\}\|\\end\{gathered\}\\right\\\}\\geq 1\-\\alpha\.\(78\)The number of colors, number of trials, and depth depend only onk,ε,αk,\\varepsilon,\\alpha, andΛ\\Lambda, not on\|V⁡\(G\)\|\|V\(G\)\|\.

###### Proof\.

Fixq≥2​kq\\geq 2k\. In one random trial, assign each vertex an independent uniform color

χ⁡\(v\)∈\[q\]≔\{1,…,q\}\.\\chi\(v\)\\in\[q\]\\coloneq\\\{1,\\ldots,q\\\}\.\(79\)For eachλ∈Λ\\lambda\\in\\Lambdaand1≤a≤b≤q1\\leq a\\leq b\\leq q, write

Dλ,a,b≔\(V,\{x​y∈E:w⁡\(x​y\)<λ​orw⁡\(x​y\)=λ,\{χ⁡\(x\),χ⁡\(y\)\}≠\{a,b\}\}\)\.\\begin\{gathered\}D\_\{\\lambda,a,b\}\\coloneq\\\\ \\left\(V,\\left\\\{xy\\in E\\colon\\;\\begin\{aligned\} &w\(xy\)<\\lambda\\ \\text\{or\}\\\\ &w\(xy\)=\\lambda,\\ \\\{\\chi\(x\),\\chi\(y\)\\\}\\neq\\\{a,b\\\}\\end\{aligned\}\\right\\\}\\right\)\.\\end\{gathered\}\(80\)Thus,Dλ,a,bD\_\{\\lambda,a,b\}retains edges of weight at mostλ\\lambda, except weight\-λ\\lambdaedges with endpoint colors\{a,b\}\\\{a,b\\\}\. An edgee=u​ve=uvselects the channelλ=w⁡\(e\)\\lambda=w\(e\)and\{a,b\}=\{χ⁡\(u\),χ⁡\(v\)\}\\\{a,b\\\}=\\\{\\chi\(u\),\\chi\(v\)\\\}\. This channel deletesee, but may also delete other edges with the same weight and endpoint colors\.

Runk−1k\-1message\-passing rounds in each channel, maintaining the finite state

Stλ,a,b​\(v\)⊆\[q\],S\_\{t\}^\{\\lambda,a,b\}\(v\)\\subseteq\[q\],\(81\)the set of colors seen within distance at mostttfromvvinDλ,a,bD\_\{\\lambda,a,b\}\. Initialize

S0λ,a,b​\(v\)=\{χ⁡\(v\)\},S\_\{0\}^\{\\lambda,a,b\}\(v\)=\\\{\\chi\(v\)\\\},\(82\)and update by

St\+1λ,a,b​\(v\)=Stλ,a,b​\(v\)∪⋃x∈NDλ,a,b​\(v\)Stλ,a,b​\(x\)\.S\_\{t\+1\}^\{\\lambda,a,b\}\(v\)=S\_\{t\}^\{\\lambda,a,b\}\(v\)\\cup\\bigcup\_\{x\\in N\_\{D\_\{\\lambda,a,b\}\}\(v\)\}S\_\{t\}^\{\\lambda,a,b\}\(x\)\.\(83\)We encode each color subset by its indicator vector\. The union update is then a coordinatewise OR, which we implement using max aggregation and fixed ReLU updates\. All channels are stored in the same node state\. To implement the filter, group incoming messages by the sender’s initial color and the edge weight, take coordinatewise maxima within each group, and select the groups allowed by the receiver’s initial color and the channel\. These selections are finite Boolean operations and can be implemented by fixed ReLU updates\. The number of channels depends only onqqandΛ\\Lambda, not on\|V⁡\(G\)\|\|V\(G\)\|\.

Afterk−1k\-1rounds, set

Σλ,a,b​\(v\)\\displaystyle\\Sigma\_\{\\lambda,a,b\}\(v\)≔Sk−1λ,a,b​\(v\),\\displaystyle\\coloneq S\_\{k\-1\}^\{\\lambda,a,b\}\(v\),\(84\)Mλ,a,b​\(v\)\\displaystyle M\_\{\\lambda,a,b\}\(v\)≔𝟏\{\|Σλ,a,b\(v\)\|<k\}\.\\displaystyle\\coloneq\\mathbf\{1\}\\\{\|\\Sigma\_\{\\lambda,a,b\}\(v\)\|<k\\\}\.For an edgee=u​ve=uv, the desired decision rule uses its selected channel and accepts in one trial if

\(Mλ,a,b​\(u\)∨Mλ,a,b​\(v\)\)andΣλ,a,b​\(u\)≠Σλ,a,b​\(v\)\.\\bigl\(M\_\{\\lambda,a,b\}\(u\)\\vee M\_\{\\lambda,a,b\}\(v\)\\bigr\)\\quad\\text\{and\}\\quad\\Sigma\_\{\\lambda,a,b\}\(u\)\\neq\\Sigma\_\{\\lambda,a,b\}\(v\)\.\(85\)To implement this rule from the sum of endpoint embeddings, retain the initial one\-hot color and allΣ\\Sigmaindicators andMMbits in each final node state\. The summed color coordinates determine the unordered endpoint colors, including the case of equal colors, and hence select the channel together withw⁡\(e\)w\(e\)\. The summedMMcoordinate is positive exactly when at least one endpoint hasM=1M=1\. The twoΣ\\Sigmasets differ exactly when some summed indicator coordinate equals one\. On inputs in\{0,1,2\}\\\{0,1,2\\\}, the ReLU function

r⁡\(x\)=ReLU⁡\(x\)−2​ReLU⁡\(x−1\)\+ReLU⁡\(x−2\)r\(x\)=\\relu\(x\)\-2\\relu\(x\-1\)\+\\relu\(x\-2\)is the indicator of this event\. Taking the Boolean OR over these coordinates and the conjunction with theMMcondition gives the decision rule\. Channel selection and these Boolean operations are exactly implementable by a fixed ReLU MLP applied to𝒉u\+𝒉v\\bm\{h\}\_\{u\}\+\\bm\{h\}\_\{v\}and the encoded edge weight\. Its width and depth depend only onq,k,Λq,k,\\Lambda\. The final network accepts an edge when the average of itsssindependent binary trial outputs is positive, equivalently when any trial accepts it\.

Fix an edgee=u​ve=uv\. For each endpointx∈\{u,v\}x\\in\\\{u,v\\\}, chooseWx=Ce​\(x\)W\_\{x\}=C\_\{e\}\(x\)if\|Ce​\(x\)\|<k\|C\_\{e\}\(x\)\|<k; otherwise, choose a connectedkk\-vertex setWx⊆Ce​\(x\)W\_\{x\}\\subseteq C\_\{e\}\(x\)containingxx\. SetW=Wu∪WvW=W\_\{u\}\\cup W\_\{v\}, so\|W\|≤2​k\|W\|\\leq 2k\. These sets depend onG,w,eG,w,e, not on the random colors\.

Suppose that the colors onWWare all distinct\. The selected channel is a subgraph ofDeD\_\{e\}, and it retains every edge ofDeD\_\{e\}with both endpoints inWW: the only vertices ofWWwith colorsχ⁡\(u\)\\chi\(u\)andχ⁡\(v\)\\chi\(v\)areuuandvv, andeeis already absent fromDeD\_\{e\}\. Here we use thatGGis simple\. If\|Ce​\(x\)\|<k\|C\_\{e\}\(x\)\|<k, the channel therefore preserves the whole component, soΣλ,a,b​\(x\)\\Sigma\_\{\\lambda,a,b\}\(x\)is its color set andMλ,a,b​\(x\)=1M\_\{\\lambda,a,b\}\(x\)=1\. If\|Ce​\(x\)\|≥k\|C\_\{e\}\(x\)\|\\geq k, the connected setWxW\_\{x\}lies within distance at mostk−1k\-1fromxxin the channel, so at leastkkdistinct colors are seen andMλ,a,b​\(x\)=0M\_\{\\lambda,a,b\}\(x\)=0\.

Consequently, if both endpoint components are large, the decoder rejects\. If they are the same small component, their color sets agree, and the decoder again rejects\. If they are different and at least one is small, their color sets differ: two small components have disjoint color sets, while a large component contributes at leastkkcolors\. Thus the decoder is correct whenever the colors onWWare distinct\. This event has probability at least

p∗​\(q\)≔\(q\)2​kq2​k,p\_\{\*\}\(q\)\\coloneq\\frac\{\(q\)\_\{2k\}\}\{q^\{2k\}\},\(86\)where\(q\)j≔q\(q−1\)⋯\(q−j\+1\)\(q\)\_\{j\}\\coloneq q\(q\-1\)\\cdots\(q\-j\+1\)denotes the falling factorial\. Therefore, afterssindependent trials, each target edge is missed with probability at most\(1−p∗​\(q\)\)s\(1\-p\_\{\*\}\(q\)\)^\{s\}, and each non\-target edge is falsely accepted with probability at mosts​\(1−p∗​\(q\)\)s\(1\-p\_\{\*\}\(q\)\)\.

Setη≔α​ε/2\\eta\\coloneq\\alpha\\varepsilon/2\. Chooseqqlarge enough thatp∗​\(q\)≥1/2p\_\{\*\}\(q\)\\geq 1/2, then choosessso that\(1−p∗​\(q\)\)s≤η\(1\-p\_\{\*\}\(q\)\)^\{s\}\\leq\\eta, and finally increaseqq, if necessary, so that

s⁡\(1−p∗​\(q\)\)≤η\.s\(1\-p\_\{\*\}\(q\)\)\\leq\\eta\.\(87\)Then each target edge is missed with probability at mostη\\eta, and each non\-target edge is falsely accepted with probability at mostη\\eta\. Markov’s inequality applied to the two error counts yields failure probability at mostα\\alpha\. If either edge class is empty, its error count is identically zero\. ∎

###### Theorem 34\(Deterministic obstruction for the local Kruskal task\)\.

LetΛ=\{0,1\}\\Lambda=\\\{0,1\\\}and letk\>5k\>5\. There is a connected weighted graph\(H,w\)\(H,w\)on ten vertices, with weights inΛ\\Lambda, such that no deterministic uncolored MPNN with identical initial vertex features and an edge\-weight\-aware symmetric edge decoder computesAk​\(H,w\)A\_\{k\}\(H,w\)\.

###### Proof\.

Take two disjoint copies ofK4K\_\{4\}, subdivide one edge in each copy, and join the two new subdivision vertices by an edgee∗e\_\{\*\}\([Figure6](https://arxiv.org/html/2610.12809#A7.F6)\)\. Give every edge weight11\.

Every vertex ofHHhas degree three\. Since the initial vertex features are identical and every edge has the same weight, induction on the message\-passing layers shows that all vertex states remain identical\. Thus, any symmetric edge decoder receives the same endpoint states and edge weight for every edge\.

However,e∗e\_\{\*\}is a bridge whose removal leaves two components of size5<k5<k, soe∗∈Ak​\(H,w\)e\_\{\*\}\\in A\_\{k\}\(H,w\)\. Every other edge lies on a cycle of weight\-11edges, so none uniquely minimizes any cut\. Consequently, no deterministic uncolored MPNN with an edge\-weight\-aware symmetric decoder computesAkA\_\{k\}on this graph\. ∎

5 vertices5 verticese∗e\_\{\*\}

Figure 6:Counterexample in[Theorem34](https://arxiv.org/html/2610.12809#Thmtheorem34)\. Every vertex has degree three and every edge has weight11\. The highlighted edgee∗e\_\{\*\}is the only bridge; deleting it leaves two five\-vertex components\. ThusAk​\(H,w\)=\{e∗\}A\_\{k\}\(H,w\)=\\\{e\_\{\*\}\\\}fork\>5k\>5\.

## Appendix HExpressivity Hierarchies for Colors and Trials

[Corollary25](https://arxiv.org/html/2610.12809#Thmtheorem25)shows that colors and trials can have very different quantitative effects\. We now show that increasing either resource strictly increases expressivity, i\.e\., the ability to distinguish non\-isomorphic graphs with high probability\. To do that, we use statistical\(q,s,α\)\(q,s,\\alpha\)\-distinguishability by random\-color WL as defined in[Definition6](https://arxiv.org/html/2610.12809#Thmdefinition6), i\.e\., a test receivesssindependent trials per graph withqquniform colors and has failure probability at mostα\\alphafor each of the four input pairs\.

Specifically, we show the two hierarchy results regarding the number of colors and trials, respectively:

###### Theorem 35\(Strict hierarchy in the number of trials\)\.

For every integers≥2s\\geq 2, there are non\-isomorphic finite graphsGs,HsG\_\{s\},H\_\{s\}that are\(2,s,1/3\)\(2,s,1/3\)\-distinguishable by random\-color WL, but are not statistically\(2,s−1,1/3\)\(2,s\-1,1/3\)\-distinguishable\.

Ignoring the last trial gives the corresponding non\-strict inclusion\. The theorem shows that two colors suffice, which is optimal\. For colors, we compare budgets of at mostqqcolors, i\.e\., the test may choose a uniform palette of sizer≤qr\\leq q, fixed across all its trials\.

###### Theorem 36\(Strict hierarchy in the number of colors\)\.

For every pair of integersq,s≥1q,s\\geq 1, there are non\-isomorphic finite graphsGq,s,Hq,sG\_\{q,s\},H\_\{q,s\}that are statistically\(q\+1,s,1/3\)\(q\+1,s,1/3\)\-distinguishable by random\-color WL, but are not statistically\(r,s,1/3\)\(r,s,1/3\)\-distinguishable for any1≤r≤q1\\leq r\\leq q\.

Hence, for every fixed number of trials, increasing the allowed palette size strictly enlarges the set of distinguishable graph pairs\. We prove both theorems using one graph class\. In each trial, the observation either conceals the graph identity or determines it exactly\. We then carefully choose the construction parameters so that the optimal failure probability crosses1/31/3when one trial or one color is added\.

### H\.1Construction of the graph class

Letℓ≥7\\ell\\geq 7be prime, and create the following disjoint union of cycles

Aℓ≔Cℓ,Bℓ≔C3⊔Cℓ−3\.A\_\{\\ell\}\\coloneq C\_\{\\ell\},\\qquad B\_\{\\ell\}\\coloneq C\_\{3\}\\sqcup C\_\{\\ell\-3\}\.\(88\)Both graphs are22\-regular onℓ\\ellvertices\. The following results show that11\-WL distinguishes them unless both graphs are monochromatic\.

###### Lemma 37\.

Two colored copies ofAℓA\_\{\\ell\}andBℓB\_\{\\ell\}are indistinguishable by11\-WL if and only if both are monochromatic in the same color\. If a root is added to each graph and joined to every block vertex, the resulting colored graphs are indistinguishable if and only if the blocks are monochromatic in the same color and the two roots have the same initial color\.

###### Proof\.

Suppose that the colored blocks are indistinguishable, and run color refinement on their disjoint union\. For each stable colorcc, letaca\_\{c\}be its multiplicity inAℓA\_\{\\ell\}and letbcb\_\{c\}be its multiplicity in the triangular component ofBℓB\_\{\\ell\}\. Every stable color occurring in either graph occurs in both\. Letmc​dm\_\{cd\}be the number of neighbors of colorddof a vertex of colorcc\.

The quotient on stable colors is connected becauseAℓA\_\{\\ell\}is connected\. A color occurring in the triangle brings all its neighboring colors into the triangle, sobc\>0b\_\{c\}\>0for every stable colorcc\. For distinct adjacent colors, counting edges gives

ac​mc​d\\displaystyle a\_\{c\}m\_\{cd\}=ad​md​c,\\displaystyle=a\_\{d\}m\_\{dc\},\(89\)bc​mc​d\\displaystyle b\_\{c\}m\_\{cd\}=bd​md​c\.\\displaystyle=b\_\{d\}m\_\{dc\}\.Hence, the fractionbc/acb\_\{c\}/a\_\{c\}is constant on the connected quotient\. Summing the multiplicities givesbc=3​ac/ℓb\_\{c\}=3a\_\{c\}/\\ell\. Sinceℓ\\ellis prime andℓ≥7\\ell\\geq 7, every positiveaca\_\{c\}is divisible byℓ\\ell\. As∑cac=ℓ\\sum\_\{c\}a\_\{c\}=\\ell, there is only one stable color\. Both blocks are therefore monochromatic in the same initial color\. Conversely, equally colored monochromatic22\-regular graphs of the same order have identical WL colors\.

In the rooted graphs, the roots have degreeℓ\\elland the block vertices have degree three\. Under indistinguishability, the two roots therefore have the same stable color\. Removing their common contribution from the block vertices’ neighbor multisets leaves the same argument\. The converse follows by a standard induction over the refinement rounds\. ∎

We next use these blocks to distinguish the endpoints of a parity gadget\. Fixk≥3k\\geq 3input pairsXi=\(xi0,xi1\)X\_\{i\}=\(x\_\{i\}^\{0\},x\_\{i\}^\{1\}\),i∈\[k\]i\\in\[k\], and a root pairR=\(r0,r1\)R=\(r^\{0\},r^\{1\}\)\. Add an edge within every pair\. For each inputii, attachAℓA\_\{\\ell\}toxi0x\_\{i\}^\{0\}andBℓB\_\{\\ell\}toxi1x\_\{i\}^\{1\}, joining each endpoint to every vertex of its block\. For𝒂∈\{0,1\}k\\bm\{a\}\\in\\\{0,1\\\}^\{k\}, write

par⁡\(𝒂\)≔a1⊕⋯⊕ak\.\\operatorname\{par\}\(\\bm\{a\}\)\\coloneq a\_\{1\}\\oplus\\cdots\\oplus a\_\{k\}\.Create one internal vertexg𝒂g\_\{\\bm\{a\}\}for each such vector, with neighborhood

N⁡\(g𝒂\)=\{x1a1,…,xkak,rpar⁡\(𝒂\)\}\.N\(g\_\{\\bm\{a\}\}\)=\\\{x\_\{1\}^\{a\_\{1\}\},\\ldots,x\_\{k\}^\{a\_\{k\}\},r^\{\\operatorname\{par\}\(\\bm\{a\}\)\}\\\}\.Finally, defineHb,ℓ,kH\_\{b,\\ell,k\}, forb∈\{0,1\}b\\in\\\{0,1\\\}, by attaching one marker leaf torbr^\{b\}\. Note that each graph has2​k​ℓ\+2​k\+2k\+32k\\ell\+2k\+2^\{k\}\+3vertices\. For fixedℓ,k\\ell,k, setHb≔Hb,ℓ,kH\_\{b\}\\coloneq H\_\{b,\\ell,k\}\.

The following results show that11\-WL can recover the structural role ofHbH\_\{b\}\.

###### Lemma 38\(Structural roles\)\.

The complete WL observation ofHbH\_\{b\}identifies the input endpoints, block vertices, internal vertices, root endpoints, and marker leaf\. For everyt≥0t\\geq 0, an input endpoint’s structure aftert\+2t\+2rounds determines thett\-round WL observation of its attached block in isolation\. The endpoint also identifies its pair partner through their pair edge\. These statements hold for every initial coloring\.

###### Proof\.

We first look at the vertex degrees of the different structural roles in the graphHbH\_\{b\}:

RoleDegreemarker leaf1block vertex3internal vertexk\+1unmarked root2k−1\+1marked root2k−1\+2input endpointℓ\+2k−1\+1\.\\begin\{array\}\[\]\{c\|c\}\\text\{Role\}&\\text\{Degree\}\\\\ \\hline\\cr\\text\{marker leaf\}&1\\\\ \\text\{block vertex\}&3\\\\ \\text\{internal vertex\}&k\+1\\\\ \\text\{unmarked root\}&2^\{k\-1\}\+1\\\\ \\text\{marked root\}&2^\{k\-1\}\+2\\\\ \\text\{input endpoint\}&\\ell\+2^\{k\-1\}\+1\.\\end\{array\}The degrees are distinct fork≥3k\\geq 3andℓ≥7\\ell\\geq 7, so one 1\-W​LWLround can identify such structures\. Each input endpoint has exactly one input\-endpoint neighbor \(i\.e\., the partner\), and, by construction, its block neighbors are precisely its neighbors of degree33\.

For a colored graph\(Hb,χ\)\(H\_\{b\},\\chi\), abbreviate its full structures byπt​\(v\)=πtHb,χ​\(v\)\\pi\_\{t\}\(v\)=\\pi\_\{t\}^\{H\_\{b\},\\chi\}\(v\)\. Letβt​\(v\)\\beta\_\{t\}\(v\)be the structure obtained by running11\-WL inside the block containing the vertexvv\. We prove by induction thatπt\+1​\(v\)\\pi\_\{t\+1\}\(v\)determinesβt​\(v\)\\beta\_\{t\}\(v\)for every block vertexvv\. The base case holds becauseβ0​\(v\)=χ​\(v\)\\beta\_\{0\}\(v\)=\\chi\(v\)\. The structureπt\+2​\(v\)\\pi\_\{t\+2\}\(v\)records its ownπt\+1\\pi\_\{t\+1\}structure and those of its neighbors\. Becauset\+1≥1t\+1\\geq 1, each neighbor pattern determines the neighbor’s degree\. Retaining exactly the neighbors of degree33and applying the induction hypothesis implies

βt\+1​\(v\)=\(CLOSE\\displaystyle\\beta\_\{t\+1\}\(v\)=\\bigl\(βt​\(v\),\\displaystyle\\beta\_\{t\}\(v\),\{\{βt\(u\):u∈N\(v\),deg\(u\)=3\}\}\)\.\\displaystyle\\\{\\\!\\\{\\beta\_\{t\}\(u\)\\colon u\\in N\(v\),\\ \\deg\(u\)=3\\\}\\\!\\\}\\bigr\)\.These are exactly the neighbors inside the block\. An input endpoint’sπt\+2\\pi\_\{t\+2\}pattern then gives the multiset ofβt\\beta\_\{t\}structures over every vertex of its attached block\. ∎

We now show that swapping the endpoints propagates through the gadget\.

###### Lemma 39\(Parity extension\)\.

Consider the parity gadget before adding the blocks and marker\. Swapping the endpoints ofXiX\_\{i\}whensi=1s\_\{i\}=1and ofRRwhensR=1s\_\{R\}=1extends to an automorphism of the gadget if and only if

sR=s1⊕⋯⊕sk\.s\_\{R\}=s\_\{1\}\\oplus\\cdots\\oplus s\_\{k\}\.

###### Proof\.

Let𝒔=\(s1,…,sk\)\\bm\{s\}=\(s\_\{1\},\\ldots,s\_\{k\}\); the input neighbors forceg𝒂g\_\{\\bm\{a\}\}to map tog𝒂⊕𝒔g\_\{\\bm\{a\}\\oplus\\bm\{s\}\}\. Its root edge is preserved exactly when

par⁡\(𝒂\)⊕sR\\displaystyle\\operatorname\{par\}\(\\bm\{a\}\)\\oplus s\_\{R\}=par⁡\(𝒂⊕𝒔\)\\displaystyle=\\operatorname\{par\}\(\\bm\{a\}\\oplus\\bm\{s\}\)=par⁡\(𝒂\)⊕par⁡\(𝒔\)\.\\displaystyle=\\operatorname\{par\}\(\\bm\{a\}\)\\oplus\\operatorname\{par\}\(\\bm\{s\}\)\.This is equivalent to the stated condition\. When it holds, the map preserves every edge\. Permuting input pairs also preserves the gadget and does not change this condition\. ∎

In addition, we can show that the graphsH0,ℓ,kH\_\{0,\\ell,k\}andH1,ℓ,kH\_\{1,\\ell,k\}are non\-isomorphic\.

###### Lemma 40\(Non\-isomorphism\)\.

For every primeℓ≥7\\ell\\geq 7andk≥3k\\geq 3, the graphsH0,ℓ,kH\_\{0,\\ell,k\}andH1,ℓ,kH\_\{1,\\ell,k\}are not isomorphic\.

###### Proof\.

An isomorphism must preserve the roles in[Lemma38](https://arxiv.org/html/2610.12809#Thmtheorem38)and map the marked rootr0r^\{0\}inH0H\_\{0\}tor1r^\{1\}inH1H\_\{1\}\. Moreover, an isomorphism also maps input\-pair edges to input\-pair edges and preserves the subgraph induced by each endpoint’s degree\-three neighbors\. SinceAℓA\_\{\\ell\}is connected andBℓB\_\{\\ell\}is disconnected, it cannot exchange the two endpoint types\. It may therefore permute input pairs but cannot swap their endpoints\. By[Lemma39](https://arxiv.org/html/2610.12809#Thmtheorem39), it cannot swap the root endpoints either, leading to a contradiction\. ∎

### H\.2Erasure and the trial law

In one trial, assign every vertex an independent uniform color from\[q\]\[q\]\. Hence, a block is monochromatic with probabilityq1−ℓq^\{1\-\\ell\}\. For inputii, letEiE\_\{i\}be the event that both attached blocks are monochromatic while their colors need not agree\. By the above, these events are independent and have probability

pℓ,q≔Pr⁡\(Ei\)=q2−2​ℓ\.p\_\{\\ell,q\}\\coloneq\\Pr\(E\_\{i\}\)=q^\{2\-2\\ell\}\.\(90\)Let

E≔⋃i=1kEi,D≔Ec,E\\coloneq\\bigcup\_\{i=1\}^\{k\}E\_\{i\},\\qquad D\\coloneq E^\{c\},\(91\)and

ηℓ,k,q≔Pr⁡\(D\)=\(1−pℓ,q\)k\.\\eta\_\{\\ell,k,q\}\\coloneq\\Pr\(D\)=\(1\-p\_\{\\ell,q\}\)^\{k\}\.\(92\)We call inputiierased whenEiE\_\{i\}occurs\. For fixedℓ,k,q\\ell,k,q, writePb=PHbWL,qP\_\{b\}=P\_\{H\_\{b\}\}^\{\\mathrm\{WL\},q\}for the probability law ofZWL,q​\(Hb\)Z\_\{\\mathrm\{WL\},q\}\(H\_\{b\}\)\.

###### Lemma 41\.

Forq≥2q\\geq 2, the conditional WL observation laws onEEagree, whereas the conditional laws onDDhave disjoint supports\. Moreover, the observation also determines whetherEEorDDoccurred\. Consequently, there are mutually singular probability lawsQ,Q0,Q1Q,Q\_\{0\},Q\_\{1\}such that, forb∈\{0,1\}b\\in\\\{0,1\\\},

Pb=\(1−ηℓ,k,q\)​Q\+ηℓ,k,q​Qb\.P\_\{b\}=\(1\-\\eta\_\{\\ell,k,q\}\)Q\+\\eta\_\{\\ell,k,q\}Q\_\{b\}\.\(93\)Forq=1q=1, the two trial laws agree andηℓ,k,1=0\\eta\_\{\\ell,k,1\}=0\.

###### Proof\.

We first show that one erased input hides the graph identity\. Fix a coloring ofH0H\_\{0\}inEE, and choose the least erased indexii\. On the same vertex sets, we replace the blockAℓA\_\{\\ell\}atxi0x\_\{i\}^\{0\}byBℓB\_\{\\ell\}and the blockBℓB\_\{\\ell\}atxi1x\_\{i\}^\{1\}byAℓA\_\{\\ell\}\. Therefore, each replaced block is monochromatic, hasℓ\\ellvertices, and is22\-regular internally\. At every refinement round, all vertices of such a block have the same structure, determined by two copies of its preceding structure and the structure of its endpoint\. A straightforward structural induction therefore shows that these replacements preserve the full WL observation\.

The resulting graph is isomorphic toH1H\_\{1\}, i\.e\., swap the endpoints ofXiX\_\{i\}andRR, sendg𝒂g\_\{\\bm\{a\}\}tog𝒂⊕𝒆ig\_\{\\bm\{a\}\\oplus\\bm\{e\}\_\{i\}\}, exchange the two blocks at inputii, and fix all other inputs and blocks\. Here𝒆i\\bm\{e\}\_\{i\}is the vector with its only nonzero coordinate atii\. We now map every vertex color along this isomorphism, including the colors on the internal vertices, endpoints, and marker\. We then choose the block bijections in inverse pairs\. This defines an involution between the two copies ofEE, i\.e\., it preserves every eventEjE\_\{j\}and hence the least erased index\. Also, all colorings have the same probability, so the map preserves the conditional uniform law onEE\. The coupled observations agree\. The least erased index is used only to define this map on labeled colorings, i\.e\., the observer need not recover it\.

Next, because the degree\-three neighbor patterns retain their initial colors, two WL rounds determine whether an endpoint’s own block is monochromatic\. In the first round, the same information about its unique input\-endpoint neighbor\. Thus the complete observation determines the existence of an erased input and hence the eventEE\.

It remains to recover the graph identity onDD\. The color partition on the disjoint union of two coloredℓ\\ell\-vertex blocks stabilizes within2​ℓ2\\ellrounds\. By[Lemma37](https://arxiv.org/html/2610.12809#Thmtheorem37), the2​ℓ2\\ell\-round observation therefore identifies the type of any nonmonochromatic block\. By[Lemma38](https://arxiv.org/html/2610.12809#Thmtheorem38), an endpoint’s full structure after2​ℓ\+22\\ell\+2rounds determines this observation\. OnDD, every input has at least one nonmonochromatic block\. Its type determines the endpoint’s superscript\. That is, if the other block is monochromatic, the pair edge gives its endpoint the complementary superscript\. Thus, after2​ℓ\+32\\ell\+3rounds, every input endpoint’s pattern determines its superscript, without recovering the input index\.

After one further round,g𝒂g\_\{\\bm\{a\}\}determines the number of its input neighbors with superscript one and hencepar⁡\(𝒂\)\\operatorname\{par\}\(\\bm\{a\}\)\. All internal neighbors ofrbr^\{b\}have paritybb\. Since degree identifies the marked root, its pattern after2​ℓ\+52\\ell\+5rounds determinesbb\. The two conditional supports onDDare therefore disjoint\. SinceEEis observable, they are also disjoint from the common conditional support onEE\. This gives the decomposition\. Whenq=1q=1, every input is erased, and the same coupling proves equality of the deterministic observations\. ∎

### H\.3Optimal failure probability

The decomposition makes the optimal error depend only on the probability that both batches reveal their graph identities\.

###### Proposition 42\.

Suppose that, forb∈\{0,1\}b\\in\\\{0,1\\\},

Pb=\(1−η\)​Q\+η​Qb,η∈\[0,1\],P\_\{b\}=\(1\-\\eta\)Q\+\\eta Q\_\{b\},\\qquad\\eta\\in\[0,1\],\(94\)whereQ,Q0,Q1Q,Q\_\{0\},Q\_\{1\}are mutually singular probability laws\. Among randomized tests using two independent batches ofssi\.i\.d\. observations, the smallest worst\-case failure probability for deciding whether their generating graph identities agree is

αs∗​\(η\)=12​\[1−\(1−\(1−η\)s\)2\]\.\\alpha\_\{s\}^\{\*\}\(\\eta\)=\\frac\{1\}\{2\}\\left\[1\-\\bigl\(1\-\(1\-\\eta\)^\{s\}\\bigr\)^\{2\}\\right\]\.\(95\)The worst case ranges over all four ordered choices from\{P0,P1\}\\\{P\_\{0\},P\_\{1\}\\\}, indexed by their graph identities\.

###### Proof\.

Mutual singularity makes the three alternativesQ,Q0,Q1Q,Q\_\{0\},Q\_\{1\}observable\. A batch reveals its identity if it contains an observation fromQ0Q\_\{0\}orQ1Q\_\{1\}, an event of probabilityas=1−\(1−η\)sa\_\{s\}=1\-\(1\-\\eta\)^\{s\}\. If both batches reveal their identities, compare them and answer correctly\. Otherwise, flip an independent fair coin\. This test has failure probability\(1−as2\)/2\(1\-a\_\{s\}^\{2\}\)/2in each of the four input cases\.

For the lower bound, put the uniform prior on the four ordered pairs of graph identities\. If a batch contains only observations fromQQ, its identity remains an independent uniform bit conditional on both observed batches\. Unless both identities are revealed, their equality therefore has conditional probability1/21/2\. Every test has average failure probability at least\(1−as2\)/2\(1\-a\_\{s\}^\{2\}\)/2under this prior, and its worst\-case failure probability is at least its average\. This proves optimality\. ∎

Setδ≔1−1/3\\delta\\coloneq 1\-1/\\sqrt\{3\}\. The proposition gives

αs∗​\(η\)≤13\\displaystyle\\alpha\_\{s\}^\{\*\}\(\\eta\)\\leq\\frac\{1\}\{3\}⟺\(1−η\)s≤δ\\displaystyle\\Longleftrightarrow\\quad\(1\-\\eta\)^\{s\}\\leq\\delta\(96\)⟺η≥1−δ1/s\.\\displaystyle\\Longleftrightarrow\\quad\\eta\\geq 1\-\\delta^\{1/s\}\.For the constructed pair, useη=ηℓ,k,q\\eta=\\eta\_\{\\ell,k,q\}whenq≥2q\\geq 2\. Forq=1q=1, the trial laws agree, so the optimal failure probability is1/21/2, also given by the formula atη=0\\eta=0\.

### H\.4Strict hierarchies

We are now ready to prove the two hierarchy results\. We begin by proving the hierarchy results on the number of trials\.

###### Proof of[Theorem35](https://arxiv.org/html/2610.12809#Thmtheorem35)\.

Fixs≥2s\\geq 2, and set

Ls≔1−δ1/s,Us≔1−δ1/\(s−1\)\.L\_\{s\}\\coloneq 1\-\\delta^\{1/s\},\\qquad U\_\{s\}\\coloneq 1\-\\delta^\{1/\(s\-1\)\}\.Then0<Ls<Us<10<L\_\{s\}<U\_\{s\}<1\. Choose a primeℓ≥7\\ell\\geq 7sufficiently large that, withp=pℓ,2=22−2​ℓp=p\_\{\\ell,2\}=2^\{2\-2\\ell\},

p≤1−LsUs,\(1−p\)2≥Us\.p\\leq 1\-\\frac\{L\_\{s\}\}\{U\_\{s\}\},\\qquad\(1\-p\)^\{2\}\\geq U\_\{s\}\.Letkkbe the smallest positive integer such that\(1−p\)k<Us\(1\-p\)^\{k\}<U\_\{s\}\. The second inequality ensuresk≥3k\\geq 3\. Minimality gives

Ls≤\(1−p\)​Us≤\(1−p\)k<Us\.L\_\{s\}\\leq\(1\-p\)U\_\{s\}\\leq\(1\-p\)^\{k\}<U\_\{s\}\.ThusLs≤ηℓ,k,2<UsL\_\{s\}\\leq\\eta\_\{\\ell,k,2\}<U\_\{s\}\. By[Equation96](https://arxiv.org/html/2610.12809#A8.E96),sstrials per graph achieve failure probability at most1/31/3, whereas every test withs−1s\-1trials has worst\-case failure probability greater than1/31/3\. TakeGs=H0,ℓ,kG\_\{s\}=H\_\{0,\\ell,k\}andHs=H1,ℓ,kH\_\{s\}=H\_\{1,\\ell,k\}\. By[Lemma40](https://arxiv.org/html/2610.12809#Thmtheorem40), they are non\-isomorphic, which gives the claim\. ∎

We now give the hierarchy results for the number of colors\.

###### Proof of[Theorem36](https://arxiv.org/html/2610.12809#Thmtheorem36)\.

Fixq,s≥1q,s\\geq 1, and set

τ≔1−δ1/s,c≔−log⁡τ\>0\.\\tau\\coloneq 1\-\\delta^\{1/s\},\\qquad c\\coloneq\-\\log\\tau\>0\.\(97\)For a primeℓ≥7\\ell\\geq 7, puta=2​ℓ−2a=2\\ell\-2and choose

k≔max⁡\{3,⌊c​qa⌋\+1\}\.k\\coloneq\\max\\\{3,\\lfloor cq^\{a\}\\rfloor\+1\\\}\.\(98\)Whenq≥2q\\geq 2, we havek​q−a\>ckq^\{\-a\}\>c, so

ηℓ,k,q\\displaystyle\\eta\_\{\\ell,k,q\}=\(1−q−a\)k\\displaystyle=\(1\-q^\{\-a\}\)^\{k\}\(99\)≤exp⁡\(−k​q−a\)<exp⁡\(−c\)=τ\.\\displaystyle\\leq\\exp\(\-kq^\{\-a\}\)<\\exp\(\-c\)=\\tau\.Forq=1q=1, the same strict inequality holds becauseηℓ,k,1=0\\eta\_\{\\ell,k,1\}=0\. Sinceηℓ,k,r\\eta\_\{\\ell,k,r\}is nondecreasing inrr, every palette sizer≤qr\\leq qgives optimal failure probability greater than1/31/3withsstrials per graph\.

On the other hand,k≤c​qa\+3k\\leq cq^\{a\}\+3, and Bernoulli’s inequality gives

ηℓ,k,q\+1\\displaystyle\\eta\_\{\\ell,k,q\+1\}≥1−k​\(q\+1\)−a\\displaystyle\\geq 1\-k\(q\+1\)^\{\-a\}\(100\)≥1−c​\(qq\+1\)a−3​\(q\+1\)−a\.\\displaystyle\\geq 1\-c\\left\(\\frac\{q\}\{q\+1\}\\right\)^\{a\}\-3\(q\+1\)^\{\-a\}\.Asℓ\\elltends to infinity through the primes, the last expression tends to one\. Chooseℓ\\ellsufficiently large that it exceedsτ\\tau\. By[Equation96](https://arxiv.org/html/2610.12809#A8.E96),q\+1q\+1colors andsstrials per graph then give failure probability at most1/31/3\. TakingGq,s=H0,ℓ,kG\_\{q,s\}=H\_\{0,\\ell,k\}andHq,s=H1,ℓ,kH\_\{q,s\}=H\_\{1,\\ell,k\}proves the claim\. ∎

## Appendix IRepresentation Spaces for Message\-Passing Networks

We fix an aggregation schemeα∈\{sum¯,mean,max,min\}\\alpha\\in\\\{\\overline\{\\mathrm\{sum\}\},\\mathrm\{mean\},\\mathrm\{max\},\\mathrm\{min\}\\\}\. All measures below are finite Borel measures\. Graphs are finite and nonempty; for mean, max, and min aggregation, we assume that every vertex has a nonempty neighborhood\.

### I\.1Metrics on measures and compact sets

Let\(X,d\)\(X,d\)be a compact metric space\. Writeℳ≤1​\(X\)\\mathcal\{M\}\_\{\\leq 1\}\(X\)for the nonnegative measures onXXwith total mass at most one, and𝒫⁡\(X\)\\mathcal\{P\}\(X\)for the probability measures onXX\. Forμ,ν∈ℳ≤1​\(X\)\\mu,\\nu\\in\\mathcal\{M\}\_\{\\leq 1\}\(X\), define the bounded\-Lipschitz metric

βd​\(μ,ν\)≔sup‖f‖∞≤1Lipd⁡\(f\)≤1\|∫Xf​𝑑μ−∫Xf​𝑑ν\|\.\\beta\_\{d\}\(\\mu,\\nu\)\\coloneq\\sup\_\{\\begin\{subarray\}\{c\}\\\|f\\\|\_\{\\infty\}\\leq 1\\\\ \\operatorname\{Lip\}\_\{d\}\(f\)\\leq 1\\end\{subarray\}\}\\left\|\\int\_\{X\}f\\,d\\mu\-\\int\_\{X\}f\\,d\\nu\\right\|\.\(101\)The bound on‖f‖∞\\\|f\\\|\_\{\\infty\}makes this expression finite even when the measures have different total masses\.

Let𝒦⁡\(X\)\\mathcal\{K\}\(X\)denote the collection of nonempty compact subsets ofXX\. Its Hausdorff metric is

Hd⁡\(A,B\)≔max⁡\{supa∈Ainfb∈Bd⁡\(a,b\),supb∈Binfa∈Ad⁡\(a,b\)\}\.\\operatorname\{H\}\_\{d\}\(A,B\)\\coloneq\\max\\left\\\{\\sup\_\{a\\in A\}\\inf\_\{b\\in B\}d\(a,b\),\\sup\_\{b\\in B\}\\inf\_\{a\\in A\}d\(a,b\)\\right\\\}\.\(102\)

### I\.2Iterated representation spaces

Set𝒳0=K\\mathcal\{X\}\_\{0\}=Kand𝖽0​\(𝒙,𝒚\)=‖𝒙−𝒚‖2\\mathsf\{d\}\_\{0\}\(\\bm\{x\},\\bm\{y\}\)=\\\|\\bm\{x\}\-\\bm\{y\}\\\|\_\{2\}\. Given\(𝒳ℓ,𝖽ℓ\)\(\\mathcal\{X\}\_\{\\ell\},\\mathsf\{d\}\_\{\\ell\}\), define the neighborhood space

𝒴ℓ=\{ℳ≤1​\(𝒳ℓ\),α=sum¯,𝒫⁡\(𝒳ℓ\),α=mean,𝒦⁡\(𝒳ℓ\),α∈\{max,min\},\\mathcal\{Y\}\_\{\\ell\}=\\begin\{cases\}\\mathcal\{M\}\_\{\\leq 1\}\(\\mathcal\{X\}\_\{\\ell\}\),&\\alpha=\\overline\{\\mathrm\{sum\}\},\\\\ \\mathcal\{P\}\(\\mathcal\{X\}\_\{\\ell\}\),&\\alpha=\\mathrm\{mean\},\\\\ \\mathcal\{K\}\(\\mathcal\{X\}\_\{\\ell\}\),&\\alpha\\in\\\{\\mathrm\{max\},\\mathrm\{min\}\\\},\\end\{cases\}equipped with

𝖾ℓ=\{β𝖽ℓ,α∈\{sum¯,mean\},H𝖽ℓ,α∈\{max,min\}\.\\mathsf\{e\}\_\{\\ell\}=\\begin\{cases\}\\beta\_\{\\mathsf\{d\}\_\{\\ell\}\},&\\alpha\\in\\\{\\overline\{\\mathrm\{sum\}\},\\mathrm\{mean\}\\\},\\\\ \\operatorname\{H\}\_\{\\mathsf\{d\}\_\{\\ell\}\},&\\alpha\\in\\\{\\mathrm\{max\},\\mathrm\{min\}\\\}\.\\end\{cases\}Define

𝒳ℓ\+1=𝒳ℓ×𝒴ℓ,𝖽ℓ\+1​\(\(z,ν\),\(z′,ν′\)\)=𝖽ℓ​\(z,z′\)\+𝖾ℓ​\(ν,ν′\)\.\\mathcal\{X\}\_\{\\ell\+1\}=\\mathcal\{X\}\_\{\\ell\}\\times\\mathcal\{Y\}\_\{\\ell\},\\qquad\\mathsf\{d\}\_\{\\ell\+1\}\\bigl\(\(z,\\nu\),\(z^\{\\prime\},\\nu^\{\\prime\}\)\\bigr\)=\\mathsf\{d\}\_\{\\ell\}\(z,z^\{\\prime\}\)\+\\mathsf\{e\}\_\{\\ell\}\(\\nu,\\nu^\{\\prime\}\)\.\(103\)
For normalized\-sum and mean aggregation, these are spaces of iterated degree measures: each representation records the initial feature together with measures on lower\-depth representations\. For max and min aggregation, we replace measures with compact neighborhood sets\.

### I\.3Induced representations and pseudometrics

For a graphGGwith initialization𝒙∈KV⁡\(G\)\\bm\{x\}\\in K^\{V\(G\)\}, setηG,v\(0\)​\(𝒙\)=𝒙v\\eta\_\{G,v\}^\{\(0\)\}\(\\bm\{x\}\)=\\bm\{x\}\_\{v\}and recursively define

ηG,v\(ℓ\+1\)​\(𝒙\)=\(ηG,v\(ℓ\)​\(𝒙\),νG,v\(ℓ\)​\(𝒙\)\),\\eta\_\{G,v\}^\{\(\\ell\+1\)\}\(\\bm\{x\}\)=\\bigl\(\\eta\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\),\\nu\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)\\bigr\),where

νG,v\(ℓ\)\(𝒙\)=\{1\|V⁡\(G\)\|​∑u∈NG​\(v\)δηG,u\(ℓ\)​\(𝒙\),α=sum¯,1\|NG​\(v\)\|​∑u∈NG​\(v\)δηG,u\(ℓ\)​\(𝒙\),α=mean,\{ηG,u\(ℓ\)​\(𝒙\):u∈NG​\(v\)\},α∈\{max,min\}\.\\nu\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)=\\begin\{cases\}\\displaystyle\\frac\{1\}\{\|V\(G\)\|\}\\sum\_\{u\\in N\_\{G\}\(v\)\}\\delta\_\{\\eta\_\{G,u\}^\{\(\\ell\)\}\(\\bm\{x\}\)\},&\\alpha=\\overline\{\\mathrm\{sum\}\},\\\\\[6\.0pt\] \\displaystyle\\frac\{1\}\{\|N\_\{G\}\(v\)\|\}\\sum\_\{u\\in N\_\{G\}\(v\)\}\\delta\_\{\\eta\_\{G,u\}^\{\(\\ell\)\}\(\\bm\{x\}\)\},&\\alpha=\\mathrm\{mean\},\\\\\[6\.0pt\] \\\{\\eta\_\{G,u\}^\{\(\\ell\)\}\(\\bm\{x\}\):u\\in N\_\{G\}\(v\)\\\},&\\alpha\\in\\\{\\mathrm\{max\},\\mathrm\{min\}\\\}\.\\end\{cases\}Hereδz\\delta\_\{z\}is the Dirac probability measure atzz\. The normalized\-sum measure has mass\|NG​\(v\)\|/\|V⁡\(G\)\|≤1\|N\_\{G\}\(v\)\|/\|V\(G\)\|\\leq 1, the mean measure has mass one, and the neighborhood sets are finite and nonempty\. ThusηG,v\(ℓ\)​\(𝒙\)∈𝒳ℓ\\eta\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)\\in\\mathcal\{X\}\_\{\\ell\}\.

The induced pseudometric on rooted attributed graphs is

dDnode​\(\(G,𝒙,v\),\(G′,𝒙′,v′\)\)≔𝖽D​\(ηG,v\(D\)​\(𝒙\),ηG′,v′\(D\)​\(𝒙′\)\)\.d\_\{D\}^\{\\mathrm\{node\}\}\\bigl\(\(G,\\bm\{x\},v\),\(G^\{\\prime\},\\bm\{x\}^\{\\prime\},v^\{\\prime\}\)\\bigr\)\\coloneq\\mathsf\{d\}\_\{D\}\\bigl\(\\eta\_\{G,v\}^\{\(D\)\}\(\\bm\{x\}\),\\eta\_\{G^\{\\prime\},v^\{\\prime\}\}^\{\(D\)\}\(\\bm\{x\}^\{\\prime\}\)\\bigr\)\.It is a pseudometric because distinct rooted attributed graphs may have identical representations\.

For graph\-level representations, define

RG,𝒙\(D\)≔1\|V⁡\(G\)\|​∑v∈V⁡\(G\)δηG,v\(D\)​\(𝒙\)∈𝒫⁡\(𝒳D\)\.R\_\{G,\\bm\{x\}\}^\{\(D\)\}\\coloneq\\frac\{1\}\{\|V\(G\)\|\}\\sum\_\{v\\in V\(G\)\}\\delta\_\{\\eta\_\{G,v\}^\{\(D\)\}\(\\bm\{x\}\)\}\\in\\mathcal\{P\}\(\\mathcal\{X\}\_\{D\}\)\.The induced graph\-level pseudometric is

dDgraph​\(\(G,𝒙\),\(G′,𝒙′\)\)≔W1​\(RG,𝒙\(D\),RG′,𝒙′\(D\)\),d\_\{D\}^\{\\mathrm\{graph\}\}\\bigl\(\(G,\\bm\{x\}\),\(G^\{\\prime\},\\bm\{x\}^\{\\prime\}\)\\bigr\)\\coloneq W\_\{1\}\\bigl\(R\_\{G,\\bm\{x\}\}^\{\(D\)\},R\_\{G^\{\\prime\},\\bm\{x\}^\{\\prime\}\}^\{\(D\)\}\\bigr\),where the Wasserstein distanceW1W\_\{1\}uses the ground metric𝖽D\\mathsf\{d\}\_\{D\}\.

The induced representation maps are continuous, hence Borel measurable, by induction on depth using the continuity of the finite measure and neighborhood\-set constructions\. So their laws under random initialization are well defined\.

## Appendix JCompactness of the Representation Spaces and Lipschitz Property

This section collects the compactness and Lipschitz properties of the deterministic representation framework used in our analysis\. We recall the relevant results and refer to[Wittig et al\. \[30\]](https://arxiv.org/html/2610.12809#bib.bib30)for the underlying arguments\. We develop the extension to random initialization in the next appendix\.

### J\.1Compactness of Representation Spaces

Compactness of the representation spaces follows inductively from compactness of the initial feature spaceKK; each successive space is a product of the preceding space and a space of neighborhood measures or compact sets\. The following lemma provides the compactness properties needed for this construction\.

###### Lemma 43\.

If\(X,d\)\(X,d\)is a compact metric space, thenℳ≤1​\(X\)\\mathcal\{M\}\_\{\\leq 1\}\(X\)and𝒫⁡\(X\)\\mathcal\{P\}\(X\)are compact underβd\\beta\_\{d\}, and𝒦⁡\(X\)\\mathcal\{K\}\(X\)is compact underHd\\operatorname\{H\}\_\{d\}\.

###### Proof\.

For complete proofs, see\[[30](https://arxiv.org/html/2610.12809#bib.bib30), Theorems 96 and 98\]\. For the spaces of measures, compactness follows from the compactness and metrizability of the weak∗topology together with the fact that the Kantorovich metricβd\\beta\_\{d\}metrizes this topology; see\[[14](https://arxiv.org/html/2610.12809#bib.bib14)\], Theorem 17\.22, and\[[3](https://arxiv.org/html/2610.12809#bib.bib3)\], Theorem 8\.3\.2\. For𝒦⁡\(X\)\\mathcal\{K\}\(X\), compactness with respect to the Hausdorff metricHd\\operatorname\{H\}\_\{d\}follows from the Blaschke selection theorem; see\[[26](https://arxiv.org/html/2610.12809#bib.bib26), Theorem 1\.8\.4\]\. ∎

###### Corollary 44\.

For everyℓ≥0\\ell\\geq 0,\(𝒳ℓ,𝖽ℓ\)\(\\mathcal\{X\}\_\{\\ell\},\\mathsf\{d\}\_\{\\ell\}\)is a compact metric space\.

### J\.2Lipschitzness of MPNNs

Setϕθ\(0\)​\(𝒛\)=𝒛\\phi\_\{\\theta\}^\{\(0\)\}\(\\bm\{z\}\)=\\bm\{z\}\. For\(z,ν\)∈𝒳ℓ\+1\(z,\\nu\)\\in\\mathcal\{X\}\_\{\\ell\+1\}, define

ϕθ\(ℓ\+1\)​\(z,ν\)=σ⁡\(𝑾self\(ℓ\)​ϕθ\(ℓ\)​\(z\)\+𝑾agg\(ℓ\)​𝒜θ\(ℓ\)​\(ν\)\+𝒃\(ℓ\)\),\\phi\_\{\\theta\}^\{\(\\ell\+1\)\}\(z,\\nu\)=\\sigma\\left\(\\bm\{W\}\_\{\\mathrm\{self\}\}^\{\(\\ell\)\}\\phi\_\{\\theta\}^\{\(\\ell\)\}\(z\)\+\\bm\{W\}\_\{\\mathrm\{agg\}\}^\{\(\\ell\)\}\\mathcal\{A\}\_\{\\theta\}^\{\(\\ell\)\}\(\\nu\)\+\\bm\{b\}^\{\(\\ell\)\}\\right\),where

𝒜θ\(ℓ\)​\(ν\)=\{∫ϕθ\(ℓ\)​\(y\)​dν​\(y\),α∈\{sum¯,mean\},maxy∈ν⁡ϕθ\(ℓ\)​\(y\),α=max,miny∈ν⁡ϕθ\(ℓ\)​\(y\),α=min\.\\mathcal\{A\}\_\{\\theta\}^\{\(\\ell\)\}\(\\nu\)=\\begin\{cases\}\\displaystyle\\int\\phi\_\{\\theta\}^\{\(\\ell\)\}\(y\)\\,d\\nu\(y\),&\\alpha\\in\\\{\\overline\{\\mathrm\{sum\}\},\\mathrm\{mean\}\\\},\\\\\[5\.0pt\] \\displaystyle\\max\_\{y\\in\\nu\}\\phi\_\{\\theta\}^\{\(\\ell\)\}\(y\),&\\alpha=\\mathrm\{max\},\\\\\[5\.0pt\] \\displaystyle\\min\_\{y\\in\\nu\}\\phi\_\{\\theta\}^\{\(\\ell\)\}\(y\),&\\alpha=\\mathrm\{min\}\.\\end\{cases\}The maximum and minimum are taken coordinate\-wise\.

The mapϕθ\(ℓ\)\\phi\_\{\\theta\}^\{\(\\ell\)\}realizes the MPNN on the structural representation space\. The following identity, obtained by induction onℓ\\ell, shows that the structural representation contains all information required to compute the node output\. Consequently, Lipschitz bounds forϕθ\(ℓ\)\\phi\_\{\\theta\}^\{\(\\ell\)\}transfer directly to the MPNN under the induced pseudometric\.

###### Lemma 45\.

For every initialization𝐱\\bm\{x\}, vertexvv, and depthℓ\\ell,

ϕθ\(ℓ\)​\(ηG,v\(ℓ\)​\(𝒙\)\)=𝒉θ,G\(ℓ\)​\(v,𝒙\)\.\\phi\_\{\\theta\}^\{\(\\ell\)\}\\bigl\(\\eta\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)\\bigr\)=\\bm\{h\}\_\{\\theta,G\}^\{\(\\ell\)\}\(v;\\bm\{x\}\)\.

###### Proof\.

We prove the result by induction onℓ\\ell\. Forℓ=0\\ell=0, we have

ϕθ\(0\)​\(ηG,v\(0\)​\(𝒙\)\)=ϕθ\(0\)​\(𝒙v\)=𝒙v=𝒉θ,G\(0\)​\(v,𝒙\)\.\\phi\_\{\\theta\}^\{\(0\)\}\\bigl\(\\eta\_\{G,v\}^\{\(0\)\}\(\\bm\{x\}\)\\bigr\)=\\phi\_\{\\theta\}^\{\(0\)\}\(\\bm\{x\}\_\{v\}\)=\\bm\{x\}\_\{v\}=\\bm\{h\}\_\{\\theta,G\}^\{\(0\)\}\(v;\\bm\{x\}\)\.Now suppose thatϕθ\(ℓ\)​\(ηG,u\(ℓ\)​\(𝒙\)\)=𝒉θ,G\(ℓ\)​\(u,𝒙\)\\phi\_\{\\theta\}^\{\(\\ell\)\}\\bigl\(\\eta\_\{G,u\}^\{\(\\ell\)\}\(\\bm\{x\}\)\\bigr\)=\\bm\{h\}\_\{\\theta,G\}^\{\(\\ell\)\}\(u;\\bm\{x\}\), for every vertexu∈V⁡\(G\)u\\in V\(G\)\. Forℓ\+1\\ell\+1, we writeηG,v\(ℓ\+1\)​\(𝒙\)=\(ηG,v\(ℓ\)​\(𝒙\),νG,v\(ℓ\)​\(𝒙\)\)\.\\eta\_\{G,v\}^\{\(\\ell\+1\)\}\(\\bm\{x\}\)=\\bigl\(\\eta\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\),\\nu\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)\\bigr\)\.Then, by definition ofϕθ\(ℓ\+1\)\\phi\_\{\\theta\}^\{\(\\ell\+1\)\},

ϕθ\(ℓ\+1\)​\(ηG,v\(ℓ\+1\)​\(𝒙\)\)\\displaystyle\\phi\_\{\\theta\}^\{\(\\ell\+1\)\}\\bigl\(\\eta\_\{G,v\}^\{\(\\ell\+1\)\}\(\\bm\{x\}\)\\bigr\)=σ⁡\(𝑾self\(ℓ\)​ϕθ\(ℓ\)​\(ηG,v\(ℓ\)​\(𝒙\)\)\+𝑾agg\(ℓ\)​𝒜θ\(ℓ\)​\(νG,v\(ℓ\)​\(𝒙\)\)\)\.\\displaystyle=\\sigma\\Bigl\(\\bm\{W\}\_\{\\mathrm\{self\}\}^\{\(\\ell\)\}\\phi\_\{\\theta\}^\{\(\\ell\)\}\\bigl\(\\eta\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)\\bigr\)\+\\bm\{W\}\_\{\\mathrm\{agg\}\}^\{\(\\ell\)\}\\mathcal\{A\}\_\{\\theta\}^\{\(\\ell\)\}\\bigl\(\\nu\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)\\bigr\)\\Bigr\)\.By the induction hypothesis, the first term inside the activation is

ϕθ\(ℓ\)​\(ηG,v\(ℓ\)​\(𝒙\)\)=𝒉θ,G\(ℓ\)​\(v,𝒙\)\.\\phi\_\{\\theta\}^\{\(\\ell\)\}\\bigl\(\\eta\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)\\bigr\)=\\bm\{h\}\_\{\\theta,G\}^\{\(\\ell\)\}\(v;\\bm\{x\}\)\.It remains to identify the aggregation term\. By construction ofνG,v\(ℓ\)​\(𝒙\)\\nu\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\), applying𝒜θ\(ℓ\)\\mathcal\{A\}\_\{\\theta\}^\{\(\\ell\)\}to this neighborhood representation recovers the corresponding aggregation of the depth\-ℓ\\ellhidden states\. Indeed, for the sum and mean cases, integration against the induced atomic measure gives the required weighted sum of

ϕθ\(ℓ\)​\(ηG,u\(ℓ\)​\(𝒙\)\),u∈NG​\(v\),\\phi\_\{\\theta\}^\{\(\\ell\)\}\\bigl\(\\eta\_\{G,u\}^\{\(\\ell\)\}\(\\bm\{x\}\)\\bigr\),\\qquad u\\in N\_\{G\}\(v\),which, by the induction hypothesis, equals the corresponding sum or mean of𝒉θ,G\(ℓ\)​\(u,𝒙\)\\bm\{h\}\_\{\\theta,G\}^\{\(\\ell\)\}\(u;\\bm\{x\}\)\. Forα=max\\alpha=\\mathrm\{max\},

𝒜θ\(ℓ\)​\(νG,v\(ℓ\)​\(𝒙\)\)\\displaystyle\\mathcal\{A\}\_\{\\theta\}^\{\(\\ell\)\}\\bigl\(\\nu\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)\\bigr\)=maxy∈νG,v\(ℓ\)​\(𝒙\)⁡ϕθ\(ℓ\)​\(y\)\\displaystyle=\\max\_\{y\\in\\nu\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)\}\\phi\_\{\\theta\}^\{\(\\ell\)\}\(y\)\\=maxu∈NG​\(v\)⁡𝒉θ,G\(ℓ\)​\(u,𝒙\),\\displaystyle=\\max\_\{u\\in N\_\{G\}\(v\)\}\\bm\{h\}\_\{\\theta,G\}^\{\(\\ell\)\}\(u;\\bm\{x\}\),and the same argument gives, forα=min\\alpha=\\mathrm\{min\},

𝒜θ\(ℓ\)​\(νG,v\(ℓ\)​\(𝒙\)\)=minu∈NG​\(v\)⁡𝒉θ,G\(ℓ\)​\(u,𝒙\),\\mathcal\{A\}\_\{\\theta\}^\{\(\\ell\)\}\\bigl\(\\nu\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)\\bigr\)=\\min\_\{u\\in N\_\{G\}\(v\)\}\\bm\{h\}\_\{\\theta,G\}^\{\(\\ell\)\}\(u;\\bm\{x\}\),with maxima and minima taken coordinate\-wise\. Thus, in every case,𝒜θ\(ℓ\)​\(νG,v\(ℓ\)​\(𝒙\)\)\\mathcal\{A\}\_\{\\theta\}^\{\(\\ell\)\}\(\\nu\_\{G,v\}^\{\(\\ell\)\}\(\\bm\{x\}\)\)is exactly the neighborhood aggregate appearing in the definition of the message\-passing update\. Hence

ϕθ\(ℓ\+1\)​\(ηG,v\(ℓ\+1\)​\(𝒙\)\)=𝒉θ,G\(ℓ\+1\)​\(v,𝒙\)\.\\phi\_\{\\theta\}^\{\(\\ell\+1\)\}\\bigl\(\\eta\_\{G,v\}^\{\(\\ell\+1\)\}\(\\bm\{x\}\)\\bigr\)=\\bm\{h\}\_\{\\theta,G\}^\{\(\\ell\+1\)\}\(v;\\bm\{x\}\)\.This completes the induction\. ∎

###### Lemma 46\.

Letg:X→ℝpg\\colon X\\to\\mathbb\{R\}^\{p\}satisfysupx‖g⁡\(x\)‖2≤M\\sup\_\{x\}\\\|g\(x\)\\\|\_\{2\}\\leq Mand‖g⁡\(x\)−g⁡\(y\)‖2≤C​d​\(x,y\)\\\|g\(x\)\-g\(y\)\\\|\_\{2\}\\leq Cd\(x,y\)\. Forμ,ν∈ℳ≤1​\(X\)\\mu,\\nu\\in\\mathcal\{M\}\_\{\\leq 1\}\(X\),

‖∫g​𝑑μ−∫g​𝑑ν‖2≤max⁡\{M,C\}​βd​\(μ,ν\),‖∫g​𝑑μ‖2≤M\.\\left\\\|\\int g\\,d\\mu\-\\int g\\,d\\nu\\right\\\|\_\{2\}\\leq\\max\\\{M,C\\\}\\beta\_\{d\}\(\\mu,\\nu\),\\qquad\\left\\\|\\int g\\,d\\mu\\right\\\|\_\{2\}\\leq M\.ForA,B∈𝒦⁡\(X\)A,B\\in\\mathcal\{K\}\(X\),

‖maxA⁡g−maxB⁡g‖2≤p​C​Hd⁡\(A,B\),‖maxA⁡g‖2≤p​M\.\\\|\\max\_\{A\}g\-\\max\_\{B\}g\\\|\_\{2\}\\leq\\sqrt\{p\}\\,C\\operatorname\{H\}\_\{d\}\(A,B\),\\qquad\\\|\\max\_\{A\}g\\\|\_\{2\}\\leq\\sqrt\{p\}\\,M\.The same bounds hold for minimum aggregation\.

###### Proof\.

For each unit vector𝒂∈ℝp\\bm\{a\}\\in\\mathbb\{R\}^\{p\}, the scalar function⟨𝒂,g⟩\\langle\\bm\{a\},g\\ranglehas uniform norm at mostMMand Lipschitz constant at mostCC\. After scaling bymax⁡\{M,C\}\\max\\\{M,C\\\}, it is an admissible test function in[Equation101](https://arxiv.org/html/2610.12809#A9.E101); the zero case is immediate\. Taking the supremum over unit vectors proves the first bound\. The second follows fromμ⁡\(X\)≤1\\mu\(X\)\\leq 1\.

For each coordinatejj, Hausdorff proximity gives

\|maxA⁡gj−maxB⁡gj\|≤C​Hd⁡\(A,B\)\.\|\\max\_\{A\}g\_\{j\}\-\\max\_\{B\}g\_\{j\}\|\\leq C\\operatorname\{H\}\_\{d\}\(A,B\)\.Summing the squared coordinate bounds yields the factorp\\sqrt\{p\}\. Since\|gj\|≤M\|g\_\{j\}\|\\leq M, each coordinate ofmaxA⁡g\\max\_\{A\}ghas absolute value at mostMM, proving its norm bound\. Replacingggby−g\-gproves the claims for minimum aggregation\. ∎

Combining these aggregation bounds with the11\-Lipschitz property of ReLU yields recursive bounds on the magnitude and Lipschitz constant of each layer\. We denote these bounds byMθ,ℓM\_\{\\theta,\\ell\}andCθ,ℓC\_\{\\theta,\\ell\}, respectively; the resulting recursions provide an explicit Lipschitz certificate for the final readout\. Write

aℓ=‖𝑾self\(ℓ\)‖2,bℓ=‖𝑾agg\(ℓ\)‖2,RK=max𝒙∈K⁡‖𝒙‖2\.a\_\{\\ell\}=\\\|\\bm\{W\}\_\{\\mathrm\{self\}\}^\{\(\\ell\)\}\\\|\_\{2\},\\qquad b\_\{\\ell\}=\\\|\\bm\{W\}\_\{\\mathrm\{agg\}\}^\{\(\\ell\)\}\\\|\_\{2\},\\qquad R\_\{K\}=\\max\_\{\\bm\{x\}\\in K\}\\\|\\bm\{x\}\\\|\_\{2\}\.InitializeMθ,0=RKM\_\{\\theta,0\}=R\_\{K\}andCθ,0=1C\_\{\\theta,0\}=1\. The bias contributes to the magnitude bound but cancels in differences of updates\. For normalized\-sum and mean aggregation, define

Mθ,ℓ\+1\\displaystyle M\_\{\\theta,\\ell\+1\}=\(aℓ\+bℓ\)​Mθ,ℓ\+‖𝒃\(ℓ\)‖2,\\displaystyle=\(a\_\{\\ell\}\+b\_\{\\ell\}\)M\_\{\\theta,\\ell\}\+\\\|\\bm\{b\}^\{\(\\ell\)\}\\\|\_\{2\},Cθ,ℓ\+1\\displaystyle C\_\{\\theta,\\ell\+1\}=max⁡\{aℓ​Cθ,ℓ,bℓ​max⁡\{Mθ,ℓ,Cθ,ℓ\}\}\.\\displaystyle=\\max\\left\\\{a\_\{\\ell\}C\_\{\\theta,\\ell\},b\_\{\\ell\}\\max\\\{M\_\{\\theta,\\ell\},C\_\{\\theta,\\ell\}\\\}\\right\\\}\.For max and min aggregation, define

Mθ,ℓ\+1\\displaystyle M\_\{\\theta,\\ell\+1\}=\(aℓ\+bℓ​dℓ\)​Mθ,ℓ\+‖𝒃\(ℓ\)‖2,\\displaystyle=\(a\_\{\\ell\}\+b\_\{\\ell\}\\sqrt\{d\_\{\\ell\}\}\)M\_\{\\theta,\\ell\}\+\\\|\\bm\{b\}^\{\(\\ell\)\}\\\|\_\{2\},Cθ,ℓ\+1\\displaystyle C\_\{\\theta,\\ell\+1\}=max⁡\{aℓ,bℓ​dℓ\}​Cθ,ℓ\.\\displaystyle=\\max\\\{a\_\{\\ell\},b\_\{\\ell\}\\sqrt\{d\_\{\\ell\}\}\\\}C\_\{\\theta,\\ell\}\.
###### Proposition 47\(Boundedness and Lipschitz continuity\)\.

For everyℓ\\ell,

supz∈𝒳ℓ‖ϕθ\(ℓ\)​\(z\)‖2≤Mθ,ℓ,‖ϕθ\(ℓ\)​\(z\)−ϕθ\(ℓ\)​\(z′\)‖2≤Cθ,ℓ​𝖽ℓ​\(z,z′\)\.\\sup\_\{z\\in\\mathcal\{X\}\_\{\\ell\}\}\\\|\\phi\_\{\\theta\}^\{\(\\ell\)\}\(z\)\\\|\_\{2\}\\leq M\_\{\\theta,\\ell\},\\qquad\\\|\\phi\_\{\\theta\}^\{\(\\ell\)\}\(z\)\-\\phi\_\{\\theta\}^\{\(\\ell\)\}\(z^\{\\prime\}\)\\\|\_\{2\}\\leq C\_\{\\theta,\\ell\}\\mathsf\{d\}\_\{\\ell\}\(z,z^\{\\prime\}\)\.Consequently,ψθ=𝐖out​ϕθ\(D\)\\psi\_\{\\theta\}=\\bm\{W\}\_\{\\mathrm\{out\}\}\\phi\_\{\\theta\}^\{\(D\)\}has Lipschitz certificateBθ≔‖𝐖out‖2​Cθ,DB\_\{\\theta\}\\coloneq\\\|\\bm\{W\}\_\{\\mathrm\{out\}\}\\\|\_\{2\}C\_\{\\theta,D\}\.

###### Proof\.

The statement trivially holds at depth zero\. Suppose it holds at depthℓ\\ell\. ReLU is11\-Lipschitz and satisfies‖σ⁡\(𝒚\)‖2≤‖𝒚‖2\\\|\\sigma\(\\bm\{y\}\)\\\|\_\{2\}\\leq\\\|\\bm\{y\}\\\|\_\{2\}\. Fors=\(z,ν\)s=\(z,\\nu\)ands′=\(z′,ν′\)s^\{\\prime\}=\(z^\{\\prime\},\\nu^\{\\prime\}\),

‖ϕθ\(ℓ\+1\)​\(s\)−ϕθ\(ℓ\+1\)​\(s′\)‖2\\displaystyle\\\|\\phi\_\{\\theta\}^\{\(\\ell\+1\)\}\(s\)\-\\phi\_\{\\theta\}^\{\(\\ell\+1\)\}\(s^\{\\prime\}\)\\\|\_\{2\}≤aℓ​Cθ,ℓ​𝖽ℓ​\(z,z′\)\\displaystyle\\leq a\_\{\\ell\}C\_\{\\theta,\\ell\}\\mathsf\{d\}\_\{\\ell\}\(z,z^\{\\prime\}\)\+bℓ​‖𝒜θ\(ℓ\)​\(ν\)−𝒜θ\(ℓ\)​\(ν′\)‖2\.\\displaystyle\\quad\+b\_\{\\ell\}\\\|\\mathcal\{A\}\_\{\\theta\}^\{\(\\ell\)\}\(\\nu\)\-\\mathcal\{A\}\_\{\\theta\}^\{\(\\ell\)\}\(\\nu^\{\\prime\}\)\\\|\_\{2\}\.Apply Lemma[46](https://arxiv.org/html/2610.12809#Thmtheorem46)to the second term\. The resulting coefficients of𝖽ℓ​\(z,z′\)\\mathsf\{d\}\_\{\\ell\}\(z,z^\{\\prime\}\)and𝖾ℓ​\(ν,ν′\)\\mathsf\{e\}\_\{\\ell\}\(\\nu,\\nu^\{\\prime\}\)are bounded byCθ,ℓ\+1C\_\{\\theta,\\ell\+1\}\. Their sum is therefore at mostCθ,ℓ\+1​𝖽ℓ\+1​\(s,s′\)C\_\{\\theta,\\ell\+1\}\\mathsf\{d\}\_\{\\ell\+1\}\(s,s^\{\\prime\}\)\. The norm estimates in the same lemma giveMθ,ℓ\+1M\_\{\\theta,\\ell\+1\}\. This completes the induction\. Composition with the linear readout gives the final assertions\. ∎

Sinceaℓ,bℓ≤BWa\_\{\\ell\},b\_\{\\ell\}\\leq B\_\{W\},‖𝒃\(ℓ\)‖2≤Bb\\\|\\bm\{b\}^\{\(\\ell\)\}\\\|\_\{2\}\\leq B\_\{b\},‖𝑾out‖2≤Bout\\\|\\bm\{W\}\_\{\\mathrm\{out\}\}\\\|\_\{2\}\\leq B\_\{\\mathrm\{out\}\}, and the architecture is fixed, these recursions yield uniform finite bounds

supθ∈ΘBθ≤B,supθ∈Θ‖ψθ‖∞≤M,\\sup\_\{\\theta\\in\\Theta\}B\_\{\\theta\}\\leq B,\\qquad\\sup\_\{\\theta\\in\\Theta\}\\\|\\psi\_\{\\theta\}\\\|\_\{\\infty\}\\leq M,\(104\)where we may chooseM≥1M\\geq 1\. The constants do not depend on graph order\.

## Appendix KRandomly Initialized Representations

We now extend the compactness and Lipschitz properties to representation laws induced by random node initialization\. The resulting domain is totally bounded under the Wasserstein distance and therefore admits finite covers at every positive scale\. Taking expectations of the MPNN outputs yields predictors on this domain that retain the deterministic Lipschitz certificates established above\.

### K\.1Compactness of the probability\-measure domain

###### Lemma 48\.

If\(X,d\)\(X,d\)is compact, then\(𝒫⁡\(X\),W1\)\(\\mathcal\{P\}\(X\),W\_\{1\}\)is compact\.

###### Proof\.

We assumeX≠∅X\\neq\\varnothing, since otherwise the claim is immediate\. By[Lemma43](https://arxiv.org/html/2610.12809#Thmtheorem43), every sequence in𝒫⁡\(X\)\\mathcal\{P\}\(X\)has a weakly convergent subsequence\. It remains to show that weak convergence implies convergence inW1W\_\{1\}\. Fixx0∈Xx\_\{0\}\\in Xand let

𝒯0=\{f:X→ℝ:Lipd\(f\)≤1,f\(x0\)=0\}\.\\mathcal\{T\}\_\{0\}=\\\{f\\colon X\\to\\mathbb\{R\}:\\operatorname\{Lip\}\_\{d\}\(f\)\\leq 1,\\ f\(x\_\{0\}\)=0\\\}\.The functions in𝒯0\\mathcal\{T\}\_\{0\}are uniformly bounded bydiam⁡\(X\)\\operatorname\{diam\}\(X\)and equicontinuous\. Since𝒯0\\mathcal\{T\}\_\{0\}is also closed under uniform convergence, it is compact in the uniform norm by Arzelà–Ascoli\[[23](https://arxiv.org/html/2610.12809#bib.bib23), Theorem 7\.25\]\. Now supposeμn\\mu\_\{n\}converges weakly toμ\\mu\. Givena\>0a\>0, choose a finiteaa\-net\{f1,…,fN\}\\\{f\_\{1\},\\ldots,f\_\{N\}\\\}of𝒯0\\mathcal\{T\}\_\{0\}\. Kantorovich–Rubinstein duality then gives

W1​\(μn,μ\)=supf∈𝒯0\|∫Xf​d​μn−∫Xf​𝑑μ\|≤max1≤j≤N⁡\|∫Xfj​d​μn−∫Xfj​𝑑μ\|\+2​a\.W\_\{1\}\(\\mu\_\{n\},\\mu\)=\\sup\_\{f\\in\\mathcal\{T\}\_\{0\}\}\\left\|\\int\_\{X\}f\\,d\\mu\_\{n\}\-\\int\_\{X\}f\\,d\\mu\\right\|\\leq\\max\_\{1\\leq j\\leq N\}\\left\|\\int\_\{X\}f\_\{j\}\\,d\\mu\_\{n\}\-\\int\_\{X\}f\_\{j\}\\,d\\mu\\right\|\+2a\.The maximum tends to zero by weak convergence, andaacan be chosen arbitrarily small\. HenceW1​\(μn,μ\)→0W\_\{1\}\(\\mu\_\{n\},\\mu\)\\to 0\. Every sequence therefore has aW1W\_\{1\}\-convergent subsequence, which proves compactness\. ∎

Applying this lemma to𝒳D\\mathcal\{X\}\_\{D\}shows that𝒫⁡\(𝒳D\)\\mathcal\{P\}\(\\mathcal\{X\}\_\{D\}\)is compact\. Its subset𝒬D\\mathcal\{Q\}\_\{D\}need not be compact, but it is totally bounded \(i\.e\., admits a finiteε\\varepsilon\-cover for everyε\>0\\varepsilon\>0\)\.

### K\.2Expected outputs and Lipschitzness

For𝝃G∼ρK⊗V⁡\(G\)\\bm\{\\xi\}^\{G\}\\sim\\rho\_\{K\}^\{\\otimes V\(G\)\}, define

QG,v\(D\)=Law⁡\(ηG,v\(D\)​\(𝝃G\)\),QG\(D\)=1\|V⁡\(G\)\|​∑vQG,v\(D\)\.Q\_\{G,v\}^\{\(D\)\}=\\operatorname\{Law\}\(\\eta\_\{G,v\}^\{\(D\)\}\(\\bm\{\\xi\}^\{G\}\)\),\\qquad Q\_\{G\}^\{\(D\)\}=\\frac\{1\}\{\|V\(G\)\|\}\\sum\_\{v\}Q\_\{G,v\}^\{\(D\)\}\.These laws are well defined by the measurability established in[SectionI\.3](https://arxiv.org/html/2610.12809#A9.SS3)\. Moreover,QG\(D\)Q\_\{G\}^\{\(D\)\}is the mean of the random measureRG,𝝃G\(D\)R\_\{G,\\bm\{\\xi\}^\{G\}\}^\{\(D\)\}, in the sense that

∫f​d​QG\(D\)=𝔼⁡\[∫f​d​RG,𝝃G\(D\)\]\\int f\\,dQ\_\{G\}^\{\(D\)\}=\\mathbb\{E\}\\left\[\\int f\\,dR\_\{G,\\bm\{\\xi\}^\{G\}\}^\{\(D\)\}\\right\]for every bounded measurableff\.

By[Lemma45](https://arxiv.org/html/2610.12809#Thmtheorem45),

Fθ​\(G,𝒙\)=∫ψθ​d​RG,𝒙\(D\)\.F\_\{\\theta\}\(G,\\bm\{x\}\)=\\int\\psi\_\{\\theta\}\\,dR\_\{G,\\bm\{x\}\}^\{\(D\)\}\.The boundedness ofψθ\\psi\_\{\\theta\}permits exchanging expectation and the finite vertex sum, giving

F¯θ​\(G\)=𝔼⁡\[Fθ​\(G,𝝃G\)\]=∫ψθ​d​QG\(D\)=ℱθ​\(QG\(D\)\)\.\\overline\{F\}\_\{\\theta\}\(G\)=\\mathbb\{E\}\[F\_\{\\theta\}\(G,\\bm\{\\xi\}^\{G\}\)\]=\\int\\psi\_\{\\theta\}\\,dQ\_\{G\}^\{\(D\)\}=\\mathcal\{F\}\_\{\\theta\}\(Q\_\{G\}^\{\(D\)\}\)\.
ForQ,Q′∈𝒫⁡\(𝒳D\)Q,Q^\{\\prime\}\\in\\mathcal\{P\}\(\\mathcal\{X\}\_\{D\}\)and any couplingπ∈Π⁡\(Q,Q′\)\\pi\\in\\Pi\(Q,Q^\{\\prime\}\),

\|ℱθ​\(Q\)−ℱθ​\(Q′\)\|\\displaystyle\|\\mathcal\{F\}\_\{\\theta\}\(Q\)\-\\mathcal\{F\}\_\{\\theta\}\(Q^\{\\prime\}\)\|=\|∫\(ψθ​\(z\)−ψθ​\(z′\)\)​𝑑π​\(z,z′\)\|\\displaystyle=\\left\|\\int\(\\psi\_\{\\theta\}\(z\)\-\\psi\_\{\\theta\}\(z^\{\\prime\}\)\)\\,d\\pi\(z,z^\{\\prime\}\)\\right\|≤Bθ​∫𝖽D​\(z,z′\)​𝑑π​\(z,z′\)\.\\displaystyle\\leq B\_\{\\theta\}\\int\\mathsf\{d\}\_\{D\}\(z,z^\{\\prime\}\)\\,d\\pi\(z,z^\{\\prime\}\)\.
Thus, averaging preserves the certificateBθB\_\{\\theta\}, with Lipschitz continuity now measured with respect toW1W\_\{1\}on probability measures and absolute value on scalar outputs\. The same argument gives

\|Fθ​\(G,𝒙\)−Fθ​\(G′,𝒙′\)\|≤Bθ​dDgraph​\(\(G,𝒙\),\(G′,𝒙′\)\)\.\|F\_\{\\theta\}\(G,\\bm\{x\}\)\-F\_\{\\theta\}\(G^\{\\prime\},\\bm\{x\}^\{\\prime\}\)\|\\leq B\_\{\\theta\}d\_\{D\}^\{\\mathrm\{graph\}\}\\bigl\(\(G,\\bm\{x\}\),\(G^\{\\prime\},\\bm\{x\}^\{\\prime\}\)\\bigr\)\.
On graphs without specified initializations, define

dDrand​\(G,G′\)≔W1​\(QG\(D\),QG′\(D\)\)\.d\_\{D\}^\{\\mathrm\{rand\}\}\(G,G^\{\\prime\}\)\\coloneq W\_\{1\}\(Q\_\{G\}^\{\(D\)\},Q\_\{G^\{\\prime\}\}^\{\(D\)\}\)\.This is a pseudometric, and

\|F¯θ​\(G\)−F¯θ​\(G′\)\|≤Bθ​dDrand​\(G,G′\)\.\|\\overline\{F\}\_\{\\theta\}\(G\)\-\\overline\{F\}\_\{\\theta\}\(G^\{\\prime\}\)\|\\leq B\_\{\\theta\}d\_\{D\}^\{\\mathrm\{rand\}\}\(G,G^\{\\prime\}\)\.Relabeling a graph permutes its node representations and preserves the i\.i\.d\. initialization law\. HenceQG\(D\)Q\_\{G\}^\{\(D\)\}andF¯θ​\(G\)\\overline\{F\}\_\{\\theta\}\(G\)are invariant under vertex relabeling\.

## Appendix LUniform Monte Carlo Approximation

Fix training graphsG1,…,GnG\_\{1\},\\ldots,G\_\{n\}and writeQi=QGi\(D\)Q\_\{i\}=Q\_\{G\_\{i\}\}^\{\(D\)\}\. For each graph, theSSinitializations are independent and have lawρK⊗V⁡\(Gi\)\\rho\_\{K\}^\{\\otimes V\(G\_\{i\}\)\}\. The following argument is conditional on the training graphs and does not require them to form a cover\. Dependence between node representations within an initialization is allowed\.

LetΨ=\{ψθ:θ∈Θ\}\\Psi=\\\{\\psi\_\{\\theta\}\\colon\\theta\\in\\Theta\\\}\. By[Equation104](https://arxiv.org/html/2610.12809#A10.E104),

supθ∈Θ‖ψθ‖∞≤M,supθ∈ΘLip𝖽D⁡\(ψθ\)≤B,\\sup\_\{\\theta\\in\\Theta\}\\\|\\psi\_\{\\theta\}\\\|\_\{\\infty\}\\leq M,\\qquad\\sup\_\{\\theta\\in\\Theta\}\\operatorname\{Lip\}\_\{\\mathsf\{d\}\_\{D\}\}\(\\psi\_\{\\theta\}\)\\leq B,whereM≥1M\\geq 1andB<∞B<\\inftydepend only on the fixed architecture, feature space, and weight and bias bounds\. Thus,Ψ\\Psiis uniformly bounded and equicontinuous on the compact space𝒳D\\mathcal\{X\}\_\{D\}\. Arzelà–Ascoli \(\[[23](https://arxiv.org/html/2610.12809#bib.bib23), Theorem 7\.25\]\) implies total boundedness in the uniform norm\. Fora\>0a\>0, let

NΨ\(a\)≔𝒩\(Ψ,∥⋅∥∞,a\),N\_\{\\Psi\}\(a\)\\coloneq\\mathcal\{N\}\(\\Psi,\\\|\\cdot\\\|\_\{\\infty\},a\),with covering centers chosen inΨ\\Psi\. The classΨ\\Psiis separable in the uniform norm, and the sampling deviation is continuous in this norm, so its supremum overΨ\\Psiis measurable\.

###### Proposition 49\(Uniform sampling bound\)\.

For everya,t\>0a,t\>0,

ℙ⁡\(supθ∈Θmax1≤i≤n⁡\|F^θ,S​\(Gi\)−F¯θ​\(Gi\)\|\>2​a\+t\)≤2​n​NΨ​\(a\)​exp⁡\(−S​t22​M2\)\.\\mathbb\{P\}\\left\(\\sup\_\{\\theta\\in\\Theta\}\\max\_\{1\\leq i\\leq n\}\|\\widehat\{F\}\_\{\\theta,S\}\(G\_\{i\}\)\-\\overline\{F\}\_\{\\theta\}\(G\_\{i\}\)\|\>2a\+t\\right\)\\leq 2nN\_\{\\Psi\}\(a\)\\exp\\left\(\-\\frac\{St^\{2\}\}\{2M^\{2\}\}\\right\)\.

###### Proof\.

Choose anaa\-netψ1,…,ψN\\psi\_\{1\},\\ldots,\\psi\_\{N\}ofΨ\\Psi, withN=NΨ​\(a\)N=N\_\{\\Psi\}\(a\), and define

Yi,s,j=1\|V⁡\(Gi\)\|​∑v∈V⁡\(Gi\)ψj​\(ηGi,v\(D\)​\(𝝃i,sGi\)\)\.Y\_\{i,s,j\}=\\frac\{1\}\{\|V\(G\_\{i\}\)\|\}\\sum\_\{v\\in V\(G\_\{i\}\)\}\\psi\_\{j\}\\bigl\(\\eta\_\{G\_\{i\},v\}^\{\(D\)\}\(\\bm\{\\xi\}\_\{i,s\}^\{G\_\{i\}\}\)\\bigr\)\.For fixedi,ji,j, these variables are independent overss, belong to\[−M,M\]\[\-M,M\], and satisfy

𝔼⁡\[Yi,s,j\]=∫ψj​d​Qi\.\\mathbb\{E\}\[Y\_\{i,s,j\}\]=\\int\\psi\_\{j\}\\,dQ\_\{i\}\.Hoeffding’s inequality gives

ℙ⁡\(\|1S​∑s=1SYi,s,j−∫ψj​d​Qi\|\>t\)≤2​exp⁡\(−S​t22​M2\)\.\\mathbb\{P\}\\left\(\\left\|\\frac\{1\}\{S\}\\sum\_\{s=1\}^\{S\}Y\_\{i,s,j\}\-\\int\\psi\_\{j\}\\,dQ\_\{i\}\\right\|\>t\\right\)\\leq 2\\exp\\left\(\-\\frac\{St^\{2\}\}\{2M^\{2\}\}\\right\)\.A union bound makes this estimate simultaneous over alli,ji,j, with failure probability at most2nNΨ\(a\)exp\(−St2/\(2M2\)\)2nN\_\{\\Psi\}\(a\)\\exp\(\-St^\{2\}/\(2M^\{2\}\)\)\.

For anyθ\\theta, choosejjsuch that‖ψθ−ψj‖∞≤a\\\|\\psi\_\{\\theta\}\-\\psi\_\{j\}\\\|\_\{\\infty\}\\leq a\. Replacingψθ\\psi\_\{\\theta\}byψj\\psi\_\{j\}changes its sampled graph\-level average by at mostaaand its expectation by at mostaa\. Hence, on the simultaneous event,

\|F^θ,S​\(Gi\)−F¯θ​\(Gi\)\|≤2​a\+t\|\\widehat\{F\}\_\{\\theta,S\}\(G\_\{i\}\)\-\\overline\{F\}\_\{\\theta\}\(G\_\{i\}\)\|\\leq 2a\+tfor everyθ\\thetaandii\. ∎

Takinga=εMC/4a=\\varepsilon\_\{\\mathrm\{MC\}\}/4andt=εMC/2t=\\varepsilon\_\{\\mathrm\{MC\}\}/2, a sufficient sample size is

S≥8​M2εMC2​log⁡\(2​n​NΨ​\(εMC/4\)δ\)\.S\\geq\\frac\{8M^\{2\}\}\{\\varepsilon\_\{\\mathrm\{MC\}\}^\{2\}\}\\log\\left\(\\frac\{2nN\_\{\\Psi\}\(\\varepsilon\_\{\\mathrm\{MC\}\}/4\)\}\{\\delta\}\\right\)\.\(105\)With probability at least1−δ1\-\\delta, this ensures

supθ∈Θmax1≤i≤n⁡\|F^θ,S​\(Gi\)−F¯θ​\(Gi\)\|≤εMC\.\\sup\_\{\\theta\\in\\Theta\}\\max\_\{1\\leq i\\leq n\}\|\\widehat\{F\}\_\{\\theta,S\}\(G\_\{i\}\)\-\\overline\{F\}\_\{\\theta\}\(G\_\{i\}\)\|\\leq\\varepsilon\_\{\\mathrm\{MC\}\}\.Since\|\|a−y\|−\|b−y\|\|≤\|a−b\|\\bigl\|\|a\-y\|\-\|b\-y\|\\bigr\|\\leq\|a\-b\|, averaging over the training graphs yields

ℙ⁡\(supθ∈Θ\|ℒ^emp​\(θ\)−ℒemp​\(θ\)\|≤εMC\)≥1−δ\.\\mathbb\{P\}\\left\(\\sup\_\{\\theta\\in\\Theta\}\|\\widehat\{\\mathcal\{L\}\}\_\{\\mathrm\{emp\}\}\(\\theta\)\-\\mathcal\{L\}\_\{\\mathrm\{emp\}\}\(\\theta\)\|\\leq\\varepsilon\_\{\\mathrm\{MC\}\}\\right\)\\geq 1\-\\delta\.\(106\)The same bound holds for the regularized losses because their regularizers coincide\.

## Appendix MProof of Learnability Guarantee

Below we prove[Theorem11](https://arxiv.org/html/2610.12809#Thmtheorem11)from the main paper\. For fixed training graphsG1,…,GnG\_\{1\},\\ldots,G\_\{n\}, we recall the definitions

ℒemp​\(θ\)≔1n​∑i=1n\|F¯θ​\(Gi\)−f∗​\(Gi\)\|,ℒreg​\(θ\)≔ℒemp​\(θ\)\+λ​\(Bθ−B∗\)\+\.\\mathcal\{L\}\_\{\\mathrm\{emp\}\}\(\\theta\)\\coloneq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\|\\overline\{F\}\_\{\\theta\}\(G\_\{i\}\)\-f^\{\\ast\}\(G\_\{i\}\)\|,\\qquad\\mathcal\{L\}\_\{\\mathrm\{reg\}\}\(\\theta\)\\coloneq\\mathcal\{L\}\_\{\\mathrm\{emp\}\}\(\\theta\)\+\\lambda\(B\_\{\\theta\}\-B\_\{\\ast\}\)\_\{\+\}\.We also write

ℒ^emp​\(θ\)≔1n​∑i=1n\|F^θ,S​\(Gi\)−f∗​\(Gi\)\|\.\\widehat\{\\mathcal\{L\}\}\_\{\\mathrm\{emp\}\}\(\\theta\)\\coloneq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\|\\widehat\{F\}\_\{\\theta,S\}\(G\_\{i\}\)\-f^\{\\ast\}\(G\_\{i\}\)\|\.Note thatℒ^reg\\widehat\{\\mathcal\{L\}\}\_\{\\mathrm\{reg\}\}andℒreg\\mathcal\{L\}\_\{\\mathrm\{reg\}\}use the same regularizer since the Lipschitz certificate only depends on the parameters of the MPNN and not on the initialization of node features\.

###### Proof\.

Fixε\>0\\varepsilon\>0andδ∈\(0,1\)\\delta\\in\(0,1\), and set

r=ε2​\(2​B∗\+1\)\.r=\\frac\{\\varepsilon\}\{2\(2B\_\{\\ast\}\+1\)\}\.By total boundedness of\(𝒢,dDrand\)\(\\mathcal\{G\},d\_\{D\}^\{\\mathrm\{rand\}\}\), choose a finiterr\-net\{G1,…,Gn\}⊆𝒢\\\{G\_\{1\},\\ldots,G\_\{n\}\\\}\\subseteq\\mathcal\{G\}\. For everyG∈𝒢G\\in\\mathcal\{G\}, there is an indexiisuch thatdDrand​\(G,Gi\)≤rd\_\{D\}^\{\\mathrm\{rand\}\}\(G,G\_\{i\}\)\\leq r\. The triangle inequality and the Lipschitz bounds give

\|F¯θ​\(G\)−f∗​\(G\)\|\\displaystyle\|\\overline\{F\}\_\{\\theta\}\(G\)\-f^\{\\ast\}\(G\)\|≤\|F¯θ​\(G\)−F¯θ​\(Gi\)\|\+\|F¯θ​\(Gi\)−f∗​\(Gi\)\|\+\|f∗​\(Gi\)−f∗​\(G\)\|\\displaystyle\\leq\|\\overline\{F\}\_\{\\theta\}\(G\)\-\\overline\{F\}\_\{\\theta\}\(G\_\{i\}\)\|\+\|\\overline\{F\}\_\{\\theta\}\(G\_\{i\}\)\-f^\{\\ast\}\(G\_\{i\}\)\|\+\|f^\{\\ast\}\(G\_\{i\}\)\-f^\{\\ast\}\(G\)\|≤\(Bθ\+B∗\)​r\+n​ℒemp​\(θ\)\.\\displaystyle\\leq\(B\_\{\\theta\}\+B\_\{\\ast\}\)r\+n\\mathcal\{L\}\_\{\\mathrm\{emp\}\}\(\\theta\)\.
Choose

η=min⁡\{λ,ε4​n\},εMC=η2\.\\eta=\\min\\left\\\{\\lambda,\\frac\{\\varepsilon\}\{4n\}\\right\\\},\\qquad\\varepsilon\_\{\\mathrm\{MC\}\}=\\frac\{\\eta\}\{2\}\.By the uniform Monte Carlo bound proved in[AppendixL](https://arxiv.org/html/2610.12809#A12), everySSsatisfying[Equation105](https://arxiv.org/html/2610.12809#A12.E105)gives an event of probability at least1−δ1\-\\deltaon which

supθ∈Θ\|ℒ^emp​\(θ\)−ℒemp​\(θ\)\|≤η2\.\\sup\_\{\\theta\\in\\Theta\}\|\\widehat\{\\mathcal\{L\}\}\_\{\\mathrm\{emp\}\}\(\\theta\)\-\\mathcal\{L\}\_\{\\mathrm\{emp\}\}\(\\theta\)\|\\leq\\frac\{\\eta\}\{2\}\.On this event, anyθ\\thetawithℒ^reg​\(θ\)<η\\widehat\{\\mathcal\{L\}\}\_\{\\mathrm\{reg\}\}\(\\theta\)<\\etasatisfies

ℒemp​\(θ\)≤ℒ^emp​\(θ\)\+η2<3​η2,Bθ≤B∗\+ηλ\.\\mathcal\{L\}\_\{\\mathrm\{emp\}\}\(\\theta\)\\leq\\widehat\{\\mathcal\{L\}\}\_\{\\mathrm\{emp\}\}\(\\theta\)\+\\frac\{\\eta\}\{2\}<\\frac\{3\\eta\}\{2\},\\qquad B\_\{\\theta\}\\leq B\_\{\\ast\}\+\\frac\{\\eta\}\{\\lambda\}\.Consequently,

supG∈𝒢\|F¯θ​\(G\)−f∗​\(G\)\|≤3​n​η2\+\(2​B∗\+ηλ\)​r≤3​ε8\+ε2<ε\.\\sup\_\{G\\in\\mathcal\{G\}\}\|\\overline\{F\}\_\{\\theta\}\(G\)\-f^\{\\ast\}\(G\)\|\\leq\\frac\{3n\\eta\}\{2\}\+\\left\(2B\_\{\\ast\}\+\\frac\{\\eta\}\{\\lambda\}\\right\)r\\leq\\frac\{3\\varepsilon\}\{8\}\+\\frac\{\\varepsilon\}\{2\}<\\varepsilon\.∎

## Appendix NExperimental details

#### Computing infrastructure\.

Experiments ran on a shared server using three NVIDIA RTX A6000 GPUs \(48 GB each\) and two AMD EPYC 7452 32\-core CPUs\. We used PyTorch 2\.9\.1 with CUDA 12\.8, running each training fit on a single GPU and independent fits in parallel\.

#### Asset licenses\.

The[GNN\-RNI repository](https://github.com/ralphabb/GNN-RNI/blob/43c69c06462d3a165ba2b532d76cbc045fc767d7/LICENSE)providing EXP includes a GNU GPLv3 license, with no separate dataset license stated\. The pinned[k\-gnn](https://github.com/chrsmrrs/k-gnn/tree/cde1f577fce0f3abb9ee9e5b0f8bc4ab43956e2e)and[random\-features \(TRIANGLE\)](https://github.com/joisino/random-features/tree/180e926edd601e10d4b115a0a1722fa7183f7f13)releases contain no explicit license statement\. Our reproduction scripts fetch third\-party code and data directly from these repositories\.

### N\.1Bridge prediction

#### Data and targets\.

We sample graphs fromG⁡\(n,1\.5/\(n−1\)\)G\(n,1\.5/\(n\-1\)\), allowing disconnected graphs\. Training and validation each contain equal numbers of graphs atn=16,32n=16,32; independent test splits usen∈\{32,128,512\}n\\in\\\{32,128,512\\\}\. For each targetb∈\{4,5,6\}b\\in\\\{4,5,6\\\}, an edge is positive exactly when it is a bridge whose removal leaves a smaller endpoint component of sizebb; every other edge is negative, including bridges of other sizes\. We retain every sampled graph and extend splits to obtain at least 1,000 training positives and 200 per evaluation split \([Table2](https://arxiv.org/html/2610.12809#A14.T2)\)\. All palettes and training seeds share the data for their target\.

Table 2:Bridge datasets: graph count / positive\-edge count\.
#### Model and training\.

Each trial assigns independent uniform colors fromq∈\{2,4,16,32\}q\\in\\\{2,4,16,32\\\}, encoded as one\-hot vectors padded to 32 coordinates for every palette\. The six\-layer, width\-32 ReLU MPNN uses max aggregation and a symmetric two\-layer edge head, with 22,305 trainable parameters in every condition\. Training averages 16 sigmoid\-probability trials before class\-balanced binary cross\-entropy over pooled edges\. We sample graphs uniformly with replacement in batches of eight and use Adam at10−310^\{\-3\}without weight decay for 100,000 updates, without early stopping\. We select checkpoints by lowest validation balanced error\. Each target and palette uses five training seeds, varying initialization, minibatches, and training colors\.

#### Evaluation and reporting\.

Test inference averages 16 fresh trials and thresholds at1/21/2; validation and test color streams are fixed and shared across fits\. FNR pools positive edges across test graphs, while FPR pools all negative edges, including wrong\-size bridges\.[Figure2](https://arxiv.org/html/2610.12809#S6.F2)reports balanced accuracy,100​\[1−\(FNR\+FPR\)/2\]100\[1\-\(\\mathrm\{FNR\}\+\\mathrm\{FPR\}\)/2\], and[Table3](https://arxiv.org/html/2610.12809#A14.T3)reports its complementary error\. Standard errors \(SEs\) equal the sample standard deviation across five training seeds divided by5\\sqrt\{5\}, conditional on the fixed dataset\.[Table4](https://arxiv.org/html/2610.12809#A14.T4)exposes confusion hidden by pooled balanced error: atb=6,q=32,n=512b=6,q=32,n=512, FPRs on side\-5 and side\-7 bridges are70\.5%70\.5\\%and92\.8%92\.8\\%, and precision is13\.5%13\.5\\%, despite6\.41%6\.41\\%balanced error\. The learned detectors are motivated by the local MST construction but do not implement its algorithm\.

Table 3:Exact\-side bridge detection: balanced test error \(%\), mean±\\pmSE across five training seeds\.Table 4:Neighboring\-side false\-positive rates and overall precision \(%\) atn=512n=512, averaged over five training seeds\. Bridges of sizesb−1b\-1andb\+1b\+1are negatives for targetbb; precision is the fraction of predicted positives with the correct label\.

### N\.2Tree substructure detection

#### Data and exact labels\.

The fixed ten\-vertex pattern has a root with three children and two leaves per child\. In a simple 3\-regular graph, it embeds as a non\-induced subgraph rooted atvvexactly when the closed two\-hop ball aroundvvhas ten vertices; edges between the six leaves are allowed\. We sample connected random 3\-regular graphs on 24 vertices, rejecting isomorphic duplicates within and across splits\. We use 256 training, 64 validation, and 1,000 test graphs, with 4,096, 1,024, and 16,000 selected root vertices, respectively, balanced exactly by label within each split\. Graphs are split before roots are selected; models receive full graphs, and all fits share the splits\. Evaluation tests unseen graphs of the same size\.

#### Model and training\.

We use two width\-32 residual ReLU message\-passing layers with max aggregation and a vertex MLP, without graph pooling\. Independent uniform one\-hot colors are projected to the hidden space; hidden widths are fixed, but the input projection grows with the palette\. We train all combinations ofq∈\{2,8,64\}q\\in\\\{2,8,64\\\}colors ands∈\{1,16,64\}s\\in\\\{1,16,64\\\}trials with five training seeds\. The models have 5,345, 5,537, and 7,329 trainable parameters forq=2,8,64q=2,8,64, respectively, independent of trial count\. Training uses binary cross\-entropy on each root’s maximum trial logit, fresh colors, and Adam at10−310^\{\-3\}without weight decay\. Each update samples 32 roots per class with replacement\. We allow up to 200,000 updates, stopping after 25,000 updates without improved validation max\-trial cross\-entropy, assessed every 250 updates\. We select the checkpoint minimizing this loss\.

#### Inference and reporting\.

Letzv\(r\)z\_\{v\}^\{\(r\)\}be the logit at vertexvvin trialrr, and letσ\\sigmadenote the sigmoid function\. At inference, we sum trial probabilities and predict

av=∑r=1sσ\(zv\(r\)\),y^v=𝟏\{av\>τ\}\.a\_\{v\}=\\sum\_\{r=1\}^\{s\}\\sigma\(z\_\{v\}^\{\(r\)\}\),\\qquad\\widehat\{y\}\_\{v\}=\\mathbf\{1\}\\\{a\_\{v\}\>\\tau\\\}\.Thus, a vertex is predicted to have the maximum two\-hop neighborhood size of ten exactly when its summed score exceeds the thresholdτ\\tau; otherwise it is predicted negative\. We chooseτ\\tauseparately for each trained model to minimize validation classification error and hold it fixed on the test set\. Evaluation color streams are fixed across training seeds\.[Figure3](https://arxiv.org/html/2610.12809#S6.F3)reports mean node accuracy±\\pmSE across five seeds on the fixed, balanced test set;[Table5](https://arxiv.org/html/2610.12809#A14.T5)retains individual errors, including the variation at\(q,s\)=\(8,64\)\(q,s\)=\(8,64\)\. These learned detectors do not implement the exact color\-coding dynamic program or require colorful witnesses\.

Table 5:Tree detection test error \(%\) for each training seed, withqqcolors andsstrials\. All models use the same 16,000 labeled roots on 1,000 unseen graphs\.

### N\.3Inference\-time quantization

#### EXP data and model\.

We use the released EXP dataset\[[1](https://arxiv.org/html/2610.12809#bib.bib1)\]: 1,200 graphs on 32–64 vertices, in 600 oppositely labeled,11\-WL\-indistinguishable pairs\. The released ten\-fold splits contain 972 training, 108 validation, and 120 test graphs per fold, with balanced labels and pairs kept together\. This is held\-out classification, not size extrapolation\. Our GCN\-RNI reimplementation uses eight width\-64 mean\-neighbor layers, separate root transforms, ELU, max graph pooling, and an MLP classifier\. Inputs are 64 independentUnif\[−1,1\)\\operatorname\{Unif\}\[\-1,1\)coordinates, or one followed by 63 zeros, keeping the architecture fixed at 72,354 trainable parameters\. Original vertex labels are not inputs\.

#### EXP training\.

We use Adam at5⋅10−45\\cdot 10^\{\-4\}, batches of 20, negative log\-likelihood, and 500 epochs, with one fresh feature draw per prediction and final checkpoints\. We follow the paper’s ELU rather than the released script’s tanh default, and use its Gaussian\-input learning rate because no separate uniform\-input rate is reported\.

#### TRIANGLE data and model\.

The released TRIANGLE data\[[24](https://arxiv.org/html/2610.12809#bib.bib24)\]contain 1,000 20\-vertex 3\-regular training graphs and 1,000 test graphs at each of 20 and 100 vertices\. Labels indicate triangle membership, with original class frequencies retained\. Following rGIN, we use four width\-64 layers with sum aggregation including the root, MLP updates, batch normalization, ReLU, and a vertex classifier, totaling 30,930 trainable parameters\. We replace its 100\-value random scalar with a fresh independentUnif⁡\[0,1\)\\operatorname\{Unif\}\[0,1\)scalar per vertex; no other vertex features are supplied\.

#### TRIANGLE training\.

We train one model for 17,500 Adam updates \(350 epochs\), with batches of 32 graphs and learning rate0\.010\.01, halved every 50 epochs\. We retain the upstream cross\-entropy on softmax outputs, weighted inversely by class frequency\. Training uses one trial per prediction; evaluation uses the final checkpoint without test\-based selection\.

#### Frozen\-model evaluation\.

Continuous and quantized conditions share feature draws and test graphs, with weights and batch\-normalization statistics fixed\. We average metrics from single\-trial predictions, not predictions across trials\. EXP quantizes each active coordinate to−1/2\-1/2or1/21/2according to its sign; each fold averages argmax classification accuracy over 50 draws\. We report mean accuracy and descriptive SE across ten fold means, whose training sets overlap\. TRIANGLE usesQq​\(u\)=\(⌊q​u⌋\+1/2\)/qQ\_\{q\}\(u\)=\(\\lfloor qu\\rfloor\+1/2\)/qand reports mean one\-versus\-rest ROC\-AUC over both classes\. Its mean and SE use ten paired feature draws of one trained model, not multiple training seeds\. Both SEs are sample SD divided by10\\sqrt\{10\}\. The exploratory palette sweep in[Figure7](https://arxiv.org/html/2610.12809#A14.F7)shows close agreement with continuous inputs forq≥4q\\geq 4, with nonmonotonic behavior at smaller palettes\.

Figure 7:TRIANGLE inference\-time quantization of one frozen rGIN trained with continuous features on 20\-vertex cubic graphs\. Test sets contain 1,000 graphs at each size\. Points and error bars show mean ROC\-AUC±\\pmSE across ten paired single\-trial feature draws; squares and dashed lines mark the continuous baseline\. The axis break omits 51–86% ROC\-AUC\. These error bars do not measure training\-seed variability\.###### Contents

1. [1Introduction](https://arxiv.org/html/2610.12809#S1)
2. [2Formal Framework](https://arxiv.org/html/2610.12809#S2)1. [2\.1Randomized MPNNs](https://arxiv.org/html/2610.12809#S2.SS1) 2. [2\.2Size\-uniform approximation](https://arxiv.org/html/2610.12809#S2.SS2) 3. [2\.3Colors, trials, and distinguishability](https://arxiv.org/html/2610.12809#S2.SS3)
3. [3Expressivity Bounds](https://arxiv.org/html/2610.12809#S3)1. [3\.1From continuous features to random colors](https://arxiv.org/html/2610.12809#S3.SS1) 2. [3\.2Non\-universality and trial lower bounds](https://arxiv.org/html/2610.12809#S3.SS2) 3. [3\.3Colors and trials](https://arxiv.org/html/2610.12809#S3.SS3) 4. [3\.4Comparison with Weisfeiler–Leman](https://arxiv.org/html/2610.12809#S3.SS4)
4. [4Algorithmic Applications](https://arxiv.org/html/2610.12809#S4)1. [4\.1Tree subgraph detection](https://arxiv.org/html/2610.12809#S4.SS1) 2. [4\.2Local MST edge detection](https://arxiv.org/html/2610.12809#S4.SS2)
5. [5Learnability of Randomized GNNs](https://arxiv.org/html/2610.12809#S5)
6. [6Experiments](https://arxiv.org/html/2610.12809#S6)
7. [7Conclusions](https://arxiv.org/html/2610.12809#S7)
8. [Bibliography](https://arxiv.org/html/2610.12809#bib)
9. [AAdditional Framework Details](https://arxiv.org/html/2610.12809#A1)1. [A\.1Graphs with random node features and graph statistics](https://arxiv.org/html/2610.12809#A1.SS1) 2. [A\.2Message\-passing neural networks](https://arxiv.org/html/2610.12809#A1.SS2) 3. [A\.3Population approximation](https://arxiv.org/html/2610.12809#A1.SS3) 4. [A\.4Uniform Lipschitzness](https://arxiv.org/html/2610.12809#A1.SS4) 5. [A\.5Empirical averaging](https://arxiv.org/html/2610.12809#A1.SS5) 6. [A\.6Graph\-pair reductions and statistical distinguishability](https://arxiv.org/html/2610.12809#A1.SS6)
10. [BQuantization for Size\-Uniform Function Approximation](https://arxiv.org/html/2610.12809#A2)1. [B\.1Quantization setup](https://arxiv.org/html/2610.12809#A2.SS1) 2. [B\.2Size\-uniform quantization](https://arxiv.org/html/2610.12809#A2.SS2) 3. [B\.3One\-hot and vector color encodings](https://arxiv.org/html/2610.12809#A2.SS3)
11. [CIndistinguishability with Random Features Using CFI](https://arxiv.org/html/2610.12809#A3)1. [C\.1Random\-color WL](https://arxiv.org/html/2610.12809#A3.SS1) 2. [C\.2The parity gadget](https://arxiv.org/html/2610.12809#A3.SS2) 3. [C\.3The graph pair family](https://arxiv.org/html/2610.12809#A3.SS3) 4. [C\.4Non\-isomorphism](https://arxiv.org/html/2610.12809#A3.SS4) 5. [C\.5Block erasure](https://arxiv.org/html/2610.12809#A3.SS5) 6. [C\.6One erased input hides the root](https://arxiv.org/html/2610.12809#A3.SS6) 7. [C\.7Total variation and sample complexity](https://arxiv.org/html/2610.12809#A3.SS7) 8. [C\.8Non\-universality](https://arxiv.org/html/2610.12809#A3.SS8) 9. [C\.9Colors and trials](https://arxiv.org/html/2610.12809#A3.SS9)
12. [DSeparation from Uncolored 1\-WL](https://arxiv.org/html/2610.12809#A4)
13. [EIncomparability with Higher\-Order WL](https://arxiv.org/html/2610.12809#A5)
14. [FSubgraph Isomorphism for Trees](https://arxiv.org/html/2610.12809#A6)
15. [GA Local MST Edge Task](https://arxiv.org/html/2610.12809#A7)
16. [HExpressivity Hierarchies for Colors and Trials](https://arxiv.org/html/2610.12809#A8)1. [H\.1Construction of the graph class](https://arxiv.org/html/2610.12809#A8.SS1) 2. [H\.2Erasure and the trial law](https://arxiv.org/html/2610.12809#A8.SS2) 3. [H\.3Optimal failure probability](https://arxiv.org/html/2610.12809#A8.SS3) 4. [H\.4Strict hierarchies](https://arxiv.org/html/2610.12809#A8.SS4)
17. [IRepresentation Spaces for Message\-Passing Networks](https://arxiv.org/html/2610.12809#A9)1. [I\.1Metrics on measures and compact sets](https://arxiv.org/html/2610.12809#A9.SS1) 2. [I\.2Iterated representation spaces](https://arxiv.org/html/2610.12809#A9.SS2) 3. [I\.3Induced representations and pseudometrics](https://arxiv.org/html/2610.12809#A9.SS3)
18. [JCompactness of the Representation Spaces and Lipschitz Property](https://arxiv.org/html/2610.12809#A10)1. [J\.1Compactness of Representation Spaces](https://arxiv.org/html/2610.12809#A10.SS1) 2. [J\.2Lipschitzness of MPNNs](https://arxiv.org/html/2610.12809#A10.SS2)
19. [KRandomly Initialized Representations](https://arxiv.org/html/2610.12809#A11)1. [K\.1Compactness of the probability\-measure domain](https://arxiv.org/html/2610.12809#A11.SS1) 2. [K\.2Expected outputs and Lipschitzness](https://arxiv.org/html/2610.12809#A11.SS2)
20. [LUniform Monte Carlo Approximation](https://arxiv.org/html/2610.12809#A12)
21. [MProof of Learnability Guarantee](https://arxiv.org/html/2610.12809#A13)
22. [NExperimental details](https://arxiv.org/html/2610.12809#A14)1. [N\.1Bridge prediction](https://arxiv.org/html/2610.12809#A14.SS1) 2. [N\.2Tree substructure detection](https://arxiv.org/html/2610.12809#A14.SS2) 3. [N\.3Inference\-time quantization](https://arxiv.org/html/2610.12809#A14.SS3)