PaperlayerView exact revision on arXiv

Source-linked AI summary

The Expressive Power of Random-Feature MPNNs Across Graph Sizes

Robert R. Nerem, Mitchell Black, Antonis Vasileiou, Christopher Morris, Yusu Wang

arXiv:2610.12809v1cs.LG

TL;DR

Existing analyses do not characterize random-feature MPNN limitations across graph sizes or under limited random bits. The paper develops a population-level framework using finite-color quantization and distinguishability, proving non-universality and incomparability with higher-order Weisfeiler–Leman methods while also giving finite-color constructions.

  • Problem

    Prior work establishes fixed-size universality for random-feature MPNNs but does not characterize size-uniform approximation or how expressivity depends on random bits and evaluations.

    Source: §1 · p. 1

  • Method

    The paper studies expected outputs of uniformly Lipschitz MPNNs, quantizes continuous random features into finite palettes, and connects approximation to finite-color distinguishability.

    Source: §2.2 · p. 4, §7 · p. 8

  • Results

    Uniformly Lipschitz random-feature MPNNs are not size-uniformly universal, and random-color MPNNs are incomparable with higher-order Weisfeiler–Leman methods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Finite colors retain size-uniform approximation power under the stated Lipschitz condition while making the roles of palette size and trial count explicit.

    Source: §7 · p. 8

    A broader characterization of distinguishable graph pairs remains open, and the approximation and learning analysis centers on averaging trials.

    Source: §7 · p. 8

Abstract

from arXiv · show

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.

1 INTRODUCTION

Continuous random features can break graph symmetries, but fixed-architecture models are not guaranteed to represent the same function across graph sizes. This section introduces a population-level framework to study size-uniform approximation and the discrete resources that govern random-feature MPNNs.

Motivation

  • Representing the same function across graph sizes is a prerequisite for size generalization, which seeks to maintain performance on graphs larger than those seen during training [19] [32] [34].The paper motivates this setting because trained models should handle larger graphs with fixed architecture, parameters, and precision.Source: §1 · p. 1

Framework

  • The framework studies invariant functions through expected outputs and characterizes how distinguishability depends on colors and independent evaluations.It uses WL-based combinatorial bounds to connect approximation with statistical graph distinguishability.Source: §1 · pp. 1–2
  • For uniformly Lipschitz MPNNs, continuous random features can be quantized to finitely many colors with arbitrarily small uniform error in expected output.The palette size can depend on the target, accuracy, and model, but not on graph size.Source: §1 · p. 2

Main results

  • Random-feature MPNNs are not size-uniformly universal, and their distinguishability is incomparable with higher-order Weisfeiler–Leman methods.On CFI graph families, the paper also quantifies a color–trial tradeoff; finite colors nevertheless support fixed-tree detection and a local MST task.Source: §1 · p. 2

Scalable computation and learning

  • Finite-color constructions cover color coding for fixed-tree subgraph detection and a local MST edge task, alongside sufficient conditions for size-uniform generalization from a suitable finite training set.The learning contribution builds on a randomized finite-cover argument.Source: §1 · p. 2

Expressivity results

  • The paper establishes strict color and trial hierarchies for statistical distinguishability by random-color WL and compares their tradeoff using CFI graphs.The CFI instances require at least s independent trials per graph for success probability at least 2/3 when q^10 log(3s) = Ω(n).Source: §1 · p. 2

2 FORMAL FRAMEWORK

The framework represents randomized MPNNs through their expected outputs and studies whether a fixed model approximates an invariant target across graph sizes. A graph-size-independent Lipschitz bound supports quantization and connects population approximation to finite-trial distinguishability.

2.1 Randomized MPNNs

  • A randomized MPNN assigns independent random features to vertices, and finite feature support defines random colors drawn from a palette.The model’s expected output is its population predictor, a deterministic graph invariant.Source: §2.1 · p. 3, §2.2 · p. 3

2.2 Size-uniform approximation

  • Size-uniform approximation requires one model to approximate the target uniformly over a graph class that may contain arbitrarily large graphs.Unlike fixed-size approximation, the predictor does not vary with graph size.Source: §2.2 · p. 4
  • Uniform Lipschitzness uses the maximum node-feature perturbation and a single output-sensitivity constant that applies to every graph.A perturbation of at most δ per initial feature changes the output by at most Lδ, independently of vertex count.Source: §2.2 · p. 4
  • Fixed-parameter ReLU MPNNs with mean, max, min, or order-normalized sum aggregation and mean pooling are uniformly Lipschitz; unnormalized sums also qualify on bounded-degree graph classes.This gives standard architectures the stability condition used by the quantization argument.Source: §2.2 · p. 4

2.3 Colors, trials, and distinguishability

  • A trial is one evaluation with an independent random initialization, and averaging any number of trials leaves the population predictor unchanged.Trials affect estimation rather than the function represented in expectation.Source: §2.3 · p. 4
  • A positive population gap between two graphs yields a finite-trial test whose required trial count depends on the gap and feature sensitivity, not graph size.The resulting distinguishability bounds can rule out approximation of targets that assign different values to the graph pair.Source: §2.3 · pp. 4–5
  • Random-color WL independently colors vertices in each trial and refines the coloring; its patterns contain enough information to determine the corresponding MPNN output.For uniform q-color initializations, its distinguishability limits also apply to random-color MPNNs, including tests beyond empirical means.Source: §2.3 · p. 4

3 EXPRESSIVITY BOUNDS

This section turns continuous random features into finite-color resources under uniform Lipschitzness, then uses finite-color distinguishability to bound size-uniform expressivity. It establishes non-universality and strict resource hierarchies, and shows random-color MPNNs and higher-order WL are incomparable.

3.1 From continuous features to random colors

  • Uniform Lipschitzness lets finite palettes approximate continuous random-feature outputs with arbitrarily small error uniformly over graph size, so the palette need not grow with graphs.The required palette may still depend on the target, accuracy, and model.Source: §3.1 · p. 5

3.2 Non-universality and trial lower bounds

  • CFI-based connected graph pairs of diameter 2 require exponentially many trials for fixed-palette random-color WL distinction, since monochromatic 2C3/C6 blocks hide their differences.These pairs support a graph invariant that uniformly Lipschitz random-feature MPNNs cannot approximate uniformly across graph sizes.Source: §3.2 · p. 5
  • Uniformly Lipschitz MPNNs with i.i.d. uniform features on [0, 1]^d are not size-uniform universal approximators, even on bounded-diameter or bounded-degree graphs.Source: §3.2 · p. 5

3.3 Colors and trials

  • Random-color WL has strict trial and palette hierarchies: two-color witnesses change distinguishability with one added trial, while palette witnesses separate q+1 colors from every palette up to q.Source: §3.3 · pp. 5–6

3.4 Comparison with Weisfeiler–Leman

  • For every k ≥ 2, a uniformly Lipschitz order-normalized-sum MPNN with two colors and one trial distinguishes some k-WL-indistinguishable pair.Attaching paths of length O(log n) lets independent binary colors identify original vertices with high probability.Source: §3.4 · p. 6
  • Conversely, for every fixed q and s, some 2-WL-distinguished pair is not statistically distinguishable by random-color WL with those resources.Together, the two separations establish incomparability with higher-order WL.Source: §3.4 · p. 6

4 ALGORITHMIC APPLICATIONS

Finite-color MPNNs support size-independent constructions for rooted tree detection and local MST-edge detection. Their resource bounds depend on task parameters rather than graph size.

4.1 Tree subgraph detection

  • Using k colors, O(k) layers, and hidden dimension exp(O(k)), a random-color MPNN detects non-induced rooted copies with no false positives and false-negative probability at most α.Source: §4.1 · p. 6
  • Taking the maximum over vertex outputs yields graph-level tree detection with the same guarantees; network and trial budgets depend on k and confidence, not graph size.Source: §4.1 · p. 6

4.2 Local MST edge detection

  • With probability at least 1 − α, the detector misses at most an ε fraction of A_k edges and falsely includes at most an ε fraction of other edges.Palette size, depth, and trial count depend on k, Λ, ε, and α, not graph size.Source: §4.2 · p. 7
  • The detector tests whether removing a candidate edge and heavier edges separates its endpoints with a small component, using reachable colors to compare the components.Source: §4.2 · p. 7
  • MPNNs with identical initial vertex features cannot compute A_k in general.Source: §4.2 · p. 7

5 LEARNABILITY OF RANDOMIZED GNNS

The section establishes a uniform learning guarantee for randomized MPNNs: sufficiently small sampled regularized error yields accurate mean predictions across the graph domain, with sampling controlled by coverage and concentration.

5 LEARNABILITY OF RANDOMIZED GNNS

  • For every accuracy and failure probability, a finite training set and tolerance suffice for the theorem’s guarantee.The theorem applies after drawing a sufficiently large number of independent initializations for each training graph.Source: §5 · p. 7
  • Sufficiently small sampled regularized error guarantees uniform approximation by the mean predictor, regardless of graph order.The required training-set size depends on the graph domain’s covering number at a radius set by desired accuracy and the target’s Lipschitz constant.Source: §5 · p. 7
  • Uniform Monte Carlo concentration makes the guarantee hold even when parameters are selected using the same sampled initializations.For a fixed test graph, averaging fresh independent initializations controls estimation error without retraining.Source: §5 · p. 7

6 EXPERIMENTS

The experiments examine finite-color MPNNs on bridge detection, rooted-tree detection, and inference-time quantization, reporting qualitative gains from larger palettes and more trials on the tree task.

Bridge prediction across graph sizes

  • With 16 trials, larger one-hot palettes improve bridge detection, while bridges with larger smaller-side components remain harder to identify.A constant-initialization max-aggregation MPNN has exactly 50% balanced accuracy; detection also generalizes to larger graphs with a fixed finite palette.Source: §6 · p. 8, Figure 2 · p. 8

Tree substructure detection: colors and trials

  • Increasing either palette size or trial count increases mean test accuracy for rooted balanced degree-three tree detection.The target is a root with three children, each with two leaves; constant initial features give identical vertex outputs on these 3-regular graphs.Source: §6 · p. 8, Figure 3 · p. 8

Inference-time quantization

  • The quantization experiment evaluates two values per random-feature coordinate without retraining on EXP and TRIANGLE.Table 1 reports inference-time performance, with means and standard errors across ten folds for EXP and ten single-trial feature draws of one trained model for TRIANGLE.Source: §6 · p. 8, Table 1 · p. 8

Experiments

  • On TRIANGLE, both tested models retain most predictive performance across 20- and 100-vertex test graphs after training on 20-vertex graphs.This experiment uses 20-vertex 3-regular training graphs and reports the comparison in Table 1.Source: §6 · p. 8

7 CONCLUSIONS

The conclusion frames finite random colors as an intermediate between anonymous message passing and continuous random features, while identifying broader characterization and additional algorithms as open directions.

7 CONCLUSIONS

  • For uniformly Lipschitz MPNNs, finite colors retain the size-uniform approximation power of continuous random features while making capabilities and limitations explicit.The framework clarifies the roles of palette size and trial count.Source: §7 · p. 8
  • A broader characterization of which graph pairs random-color MPNNs can distinguish remains open.The paper’s examples establish limitations and incomparability with k-WL.Source: §7 · p. 8
  • Identifying more algorithms implementable with graph-size-independent numbers of colors and trials is a next step.The paper also points to studying ways of combining trial information beyond averaging and expectations.Source: §7 · p. 8

AI USE STATEMENT

The supplied material includes an AI-use disclosure and appendix definitions and results on MPNN setup, uniform Lipschitzness, and finite-trial averaging.

AI USE STATEMENT

  • The authors report using generative AI tools across mathematical work, experiments, literature searches, and manuscript preparation, with assisted material reviewed and verified.Source: AI USE STATEMENT · p. 9

A.1 Graphs with random node features and graph statistics

  • A graph statistic is a scalar-valued graph invariant on a graph with random node features.Source: §A.1 · p. 12

A.2 Message-passing neural networks

  • The MPNN setup assumes parameter bounds shared across layers and models and independent of graph size, with a permutation-invariant graph-level readout.Source: §A.2 · p. 12

A.3 Population approximation

  • The appendix introduces the t-mean as a graph invariant associated with a graph statistic.Source: §A.3 · p. 13

A.4 Uniform Lipschitzness

  • Standard mean, order-normalized sum, max, and min aggregation yield a feature-Lipschitz bound independent of graph size; unnormalized sums are bounded for bounded-degree graphs.For uniformly Lipschitz MPNNs, the output distribution for each graph has diameter at most LDK.Source: §A.4 · p. 13

A.5 Empirical averaging

  • Population-level approximation by a uniformly Lipschitz model yields finite-trial high-probability approximation with a required trial count independent of graph size.The result follows by concentration for averages of independent initializations.Source: §A.5 · p. 14

A.6 Graph-pair reductions and statistical distinguishability

This section connects population-level graph-pair gaps to finite-trial testing and non-universality, and reduces size-uniform approximation with continuous random features to finite colors. It develops CFI parity pairs and shows how monochromatic block swaps can make random-color WL sample distributions identical, including for virtual-node graphs.

A.6 Graph-pair reductions and statistical distinguishability

  • A lower bound against all s-trial tests forces small population gaps, and uniformly bounded gaps on non-isomorphic pairs imply non-universality.For the empirical-mean test, Hoeffding’s inequality controls errors when same-graph means differ by zero and different-graph means by at least ∆, with outputs in an interval of length LDK.Source: §A.6 · p. 15

B.1 Quantization setup; B.2 Size-uniform quantization

  • Uniformly Lipschitz MPNNs can replace compactly supported continuous features with a finite palette while preserving the uniformly approximable graph invariants.A palette chosen from a δ-cover yields an error controlled by the Lipschitz constant and quantization radius; its size can depend on accuracy and feature space, but not graph size.Source: §B.1 · p. 15, §B.2 · p. 16

B.3 One-hot and vector color encodings

  • For fixed q and any color distribution, one-hot and injective vector color encodings have the same size-uniform approximation power.The encoding conversion can be implemented with finitely many nodewise layers and a graph-size-independent Lipschitz constant.Source: §B.3 · pp. 16–17

C INDISTINGUISHABILITY WITH RANDOM FEATURES USING CFI; C.1 Random-color WL

  • Random-color WL tests compare WL observations across independent coloring trials, include tests of random-color MPNN outputs, and the CFI construction makes their distributions exponentially close for fixed colors.The construction is presented as requiring exponentially many trials to distinguish certain graph pairs, extending beyond MPNNs to tests based on their WL patterns.Source: §C.1 · pp. 17–18, C INDISTINGUISHABILITY WITH RANDOM… · p. 17

C.2 The parity gadget

  • The CFI parity gadget permits endpoint swaps to extend to an automorphism exactly when the number of swaps is even.Thus the swap at the third distinguished pair is determined by the XOR of the first two swaps.Source: §C.2 · p. 18

C.3 The graph pair family

  • The graph-pair family composes parity gadgets in a binary tree, attaches distinct rooted blocks at input pairs, and yields connected graphs of maximum degree eight.Adding a virtual node gives diameter-two variants, providing the stated graph-size and diameter restrictions for the construction.Source: C INDISTINGUISHABILITY WITH RANDOM… · p. 17, §C.3 · pp. 18–19

C.4 Non-isomorphism

  • The marker leaf makes each constructed pair non-isomorphic, both before and after adding a virtual node.An isomorphism would force the root swap while the input attachments forbid input swaps, contradicting the parity constraint throughout the gadget tree.Source: §C.4 · pp. 19–20

C.5 Block erasure

  • At each input pair, block erasure uses the event that both attached six-vertex blocks are monochromatic; each block is monochromatic with probability q^-5.The two blocks in this event need not receive the same color.Source: §C.5 · p. 20
  • Under a coloring satisfying Bi, replacing the specified attachment blocks preserves corresponding vertex patterns at every round and the graph-level WL observations.The replaced blocks are monochromatic, and their vertices retain the same patterns by induction.Source: §C.5 · p. 20

C.6 One erased input hides the root

  • When at least one input block pair is erased (event B), G0 and G1 have identical random-color WL sample distributions, including their virtual-node versions.The equality is conditioned on B.Source: §C.6 · p. 20

C.7 Total variation and sample complexity

With a fixed palette, CFI graph pairs require exponentially many random-color WL trials to distinguish, yielding size-uniform non-universality on bounded-degree and bounded-diameter classes. The section also contrasts color and trial budgets and shows random colors separating graphs that uncolored 1-WL cannot distinguish.

C.7 Total variation and sample complexity

  • For fixed q and α, distinguishing the CFI pair requires exp(Ω(nk)) random-color WL trials, while its total-variation bound is exp(−Ω(k)).The same lower bound applies to the virtual-node pair, with its corresponding graph-size parameter.Source: §C.7 · pp. 21–22

C.8 Non-universality

  • Uniformly Lipschitz MPNNs are not size-uniform universal approximators for bounded graph invariants on connected graphs of maximum degree eight or graphs of diameter two.The proof transfers the fixed-color trial lower bound through uniform quantization.Source: §C.8 · p. 22

C.9 Colors and trials

  • Polynomially many colors suffice in a single trial, whereas any fixed palette requires exponentially many trials; the color count enters polynomially and the trial count logarithmically.This trade-off also holds for the virtual-node pair and thus for both bounded-degree and bounded-diameter settings.Source: §C.9 · pp. 22–23

D SEPARATION FROM UNCOLORED 1-WL

  • Two-color random-feature MPNNs separate arbitrarily large 1-WL-indistinguishable graphs with a population gap of 1/4 using depth three.The examples are disjoint unions of 2C3 and C6; their length-three return probabilities differ.Source: D SEPARATION FROM UNCOLORED 1-WL · p. 23

E INCOMPARABILITY WITH HIGHER-ORDER WL

Random-color MPNNs and higher-order WL are incomparable: random colors can distinguish some pairs that k-WL cannot, while 2-WL can distinguish pairs beyond any fixed color-and-trial budget. The construction attaches paths to CFI graphs so random binary features can identify original vertices.

E INCOMPARABILITY WITH HIGHER-ORDER WL

  • For every k ≥2, a uniformly 1-Lipschitz two-color MPNN with order-normalized sum aggregation distinguishes some k-WL-indistinguishable pair with one trial per graph and success probability greater than 2/3.The construction uses non-isomorphic k-WL-equivalent CFI graphs with paths attached to their vertices.Source: E INCOMPARABILITY WITH HIGHER-ORDER WL · p. 24
  • For every fixed q and s, some pair distinguished by 2-WL is not statistically (q, s, 1/3)-distinguishable by random-color WL, nor by a q-color MPNN with s trials.The result extends to every k-WL for k ≥2.Source: E INCOMPARABILITY WITH HIGHER-ORDER WL · pp. 24–25
  • Attaching paths of logarithmic length preserves k-WL equivalence, while independent binary features give original vertices identifiers that are unique with high probability.The MPNN collects these identifiers and uses them to reconstruct and recognize the graph.Source: E INCOMPARABILITY WITH HIGHER-ORDER WL · pp. 24–25

F SUBGRAPH ISOMORPHISM FOR TREES

The section adapts color coding to random-color MPNNs, implementing a dynamic program for colorful tree embeddings. With resources depending on the tree rather than graph size, repeated trials yield tree detectors with no false positives and controlled false negatives.

F SUBGRAPH ISOMORPHISM FOR TREES

  • Identical initial features cannot let a standard MPNN decide whether a graph contains a simple path of length three, as C6 and 2C3 are 1-WL indistinguishable.C6 contains such a path, whereas 2C3 does not.Source: F SUBGRAPH ISOMORPHISM FOR TREES · p. 25
  • A dynamic program tracks colorful embeddings by vertex, tree node, iteration, and color subset, and max-aggregation MPNNs implement its updates in O(k) layers.The final table entry is true exactly when a colorful copy of the tree is rooted at the vertex.Source: F SUBGRAPH ISOMORPHISM FOR TREES · pp. 25–27
  • One trial accepts a rooted tree copy only when it exists, and accepts with probability at least k!/k^k when a fixed copy exists.Independent trials reduce the false-negative probability to at most α.Source: F SUBGRAPH ISOMORPHISM FOR TREES · p. 27
  • Random-color MPNNs detect any fixed tree subgraph with resources independent of graph size, no false positives, and false-negative probability at most α.The construction uses k colors, O(k) layers, and hidden dimension exp(O(k)) for a tree with k vertices.Source: F SUBGRAPH ISOMORPHISM FOR TREES · p. 27
  • For every k, random-color MPNNs detect simple paths with k edges using k + 1 colors, O(k) layers, and hidden dimension exp(O(k)).The construction has no false positives, and independent trials achieve false-negative probability at most α.Source: F SUBGRAPH ISOMORPHISM FOR TREES · p. 28

G A LOCAL MST EDGE TASK

For the local MST edge task, the section characterizes qualifying edges by the components left after removing the candidate edge and heavier edges, then gives finite-color MPNNs for detecting them. It also proves a deterministic uncolored obstruction and strict hierarchies in the number of trials and colors.

G A LOCAL MST EDGE TASK

  • An edge qualifies for A_k exactly when its endpoints lie in different components after removing it and heavier edges, with at least one component having fewer than k vertices.When k is at least the graph size, this is the set of edges occurring in every MST, or every minimum spanning forest if disconnected.Source: G A LOCAL MST EDGE TASK · p. 28
  • Finite-color edge-output MPNNs approximate the local Kruskal edge set with error control, using colors, trials, and depth determined by k, ε, α, and Λ—not graph size.The randomized construction uses color-reachability information around the two endpoints; its error bounds apply to missed target edges and falsely accepted non-target edges.Source: G A LOCAL MST EDGE TASK · pp. 28, 30
  • For k > 5, a ten-vertex 3-regular graph with unit edge weights defeats deterministic uncolored MPNNs with identical initial features and symmetric edge decoders.Its unique bridge qualifies, while every other edge lies on a cycle, although message passing gives every edge the same decoder input.Source: G A LOCAL MST EDGE TASK · p. 30

H EXPRESSIVITY HIERARCHIES FOR COLORS AND TRIALS

  • For every s ≥ 2, two colors distinguish some graph pairs with s trials at failure probability 1/3, but not with s − 1 trials.In the construction, each trial either conceals graph identity or determines it exactly.Source: H EXPRESSIVITY HIERARCHIES FOR COLORS… · pp. 30–31
  • For any fixed trial count s, some graph pairs are distinguishable with q + 1 colors but not with any palette of at most q colors at failure probability 1/3.The construction tunes parameters so the optimal failure probability crosses 1/3 when one color is added.Source: H EXPRESSIVITY HIERARCHIES FOR COLORS… · p. 31

H.1 Construction of the graph class

This section constructs graph pairs and develops representation-space and Lipschitz tools for analyzing MPNNs, including their expected outputs under random initialization. It also characterizes two-batch failure probability and establishes uniform Monte Carlo approximation for these predictors.

H.1 Construction of the graph class

  • For prime ℓ≥7 and k≥3, the constructed H0 and H1 graphs are non-isomorphic; 1-WL distinguishes the blocks except when both are monochromatic in the same color.The full WL observation identifies structural roles and attached-block observations; endpoint swaps in the parity gadget extend to automorphisms exactly under its parity condition.Source: §H.1 · pp. 31–32

H.2 Erasure and the trial law

  • For q≥2, the WL observation identifies whether an input is erased: conditional laws agree on erasure and have disjoint supports otherwise, yielding a common component and two identity-specific components.For q=1, the two trial laws agree and ηℓ,k,1=0.Source: §H.2 · p. 33

H.3 Optimal failure probability

  • For two independent batches of s observations, the minimum worst-case failure probability is (1−a_s^2)/2, where a_s=1−(1−η)^s; if either batch fails to reveal identity, the optimal decision is a fair coin.For the constructed pair, η=ηℓ,k,q when q≥2, and η=0 when q=1.Source: §H.3 · p. 34

H.4 Strict hierarchies

  • The constructed non-isomorphic pairs give strict hierarchies: s trials per graph achieve failure at most 1/3 while s−1 do not, and q+1 colors achieve that threshold when q colors do not.The color result uses the monotonicity of ηℓ,k,r in palette size and chooses ℓ sufficiently large.Source: §H.4 · pp. 34–35

I.1 Metrics on measures and compact sets; I.2 Iterated representation spaces

  • The representation framework uses bounded-Lipschitz metrics for finite measures, probability measures, and iterated neighborhood measures, and Hausdorff metrics for compact neighborhood sets under max or min aggregation.Normalized-sum and mean representations use measures, while max and min representations use compact neighborhood sets.Source: §I.1 · p. 35, §I.2 · p. 35

I.3 Induced representations and pseudometrics

  • The induced rooted-graph distance is a pseudometric because distinct graphs can share a representation, and continuity of the representation maps makes their laws under random initialization well-defined.The graph-level pseudometric uses Wasserstein distance between representation laws.Source: §I.3 · p. 36

J.1 Compactness of Representation Spaces

  • If the initial feature space is compact, then the iterated representation spaces are compact, including the spaces of finite measures, probability measures, and compact neighborhood sets.Compactness of the measure spaces follows under the bounded-Lipschitz metric, and compactness of the neighborhood-set space follows under the Hausdorff metric.Source: §J.1 · p. 36

J.2 Lipschitzness of MPNNs

  • The structural representation contains all information required to compute node outputs, so Lipschitz bounds transfer directly to MPNNs under the induced pseudometric.For sum and mean aggregation, integration against the induced neighborhood measure recovers the corresponding hidden-state aggregation.Source: §J.2 · p. 37
  • For a fixed architecture, recursive layer bounds yield an explicit final-readout Lipschitz certificate whose constants do not depend on graph order.The boundedness and continuity result applies at every layer.Source: §J.2 · p. 38

K.1 Compactness of the probability-measure domain

  • Compactness of the underlying space makes its probability-measure space compact, while the representation-law subset is totally bounded.The subset need not itself be compact.Source: §K.1 · p. 39

K.2 Expected outputs and Lipschitzness

  • Averaging MPNN outputs preserves their Lipschitz certificate under Wasserstein distance, and the resulting expected predictor is invariant to vertex relabeling.The certificate is measured with W1 on probability measures and absolute value on scalar outputs.Source: §K.2 · p. 40

L UNIFORM MONTE CARLO APPROXIMATION

  • Proposition 49 provides a uniform sampling-deviation bound over the predictor class, and the same bound applies to regularized losses.The argument conditions on training graphs without requiring them to form a cover; initializations are independent across trials, while node representations within a trial may be dependent.Source: L UNIFORM MONTE CARLO APPROXIMATION · pp. 40–41

M PROOF OF LEARNABILITY GUARANTEE

The proof uses a finite net to reduce a uniform approximation guarantee to bounds at finitely many graphs. A triangle-inequality decomposition combines the model’s variation, its error on the net, and the target’s variation.

M PROOF OF LEARNABILITY GUARANTEE

  • A finite r-net is selected so every graph lies within distance r of a net graph.The proof uses total boundedness and the net to reduce the uniform guarantee to finitely many reference graphs.Source: M PROOF OF LEARNABILITY GUARANTEE · p. 41
  • The approximation error at any graph is bounded by model variation, error at its nearby net graph, and target variation.The proof applies the triangle inequality to these three terms.Source: M PROOF OF LEARNABILITY GUARANTEE · p. 41
  • The proof invokes a uniform Monte Carlo bound to obtain a high-probability event for samples satisfying Equation (105).The stated event has probability at least 1 − δ.Source: M PROOF OF LEARNABILITY GUARANTEE · p. 41

N EXPERIMENTAL DETAILS

The experiments examine bridge prediction, tree-substructure detection, and inference-time quantization under their stated data and evaluation settings. Results include bridge error alongside substantial false positives on neighboring bridge sizes, and close agreement with continuous inputs for palettes of at least four colors in the quantization sweep.

N.1 Bridge prediction

  • Bridge targets b ∈ {4, 5, 6} label only bridges whose removal leaves a smaller endpoint component of the target size; tests use n = 32, 128, and 512.Training and validation graphs use n = 16 and 32.Source: §N.1 · p. 42
  • At b = 6, q = 32, n = 512, balanced error is 6.41%, while side-5 and side-7 bridge FPRs are 70.5% and 92.8%, and precision is 13.5%.The learned detectors are motivated by the local MST construction but do not implement its algorithm.Source: §N.1 · p. 42, Table 4 · p. 43

N.2 Tree substructure detection

  • Tree detectors are evaluated on unseen 24-vertex graphs, and do not implement the exact color-coding dynamic program or require colorful witnesses.The fixed pattern is detected at a root exactly when its closed two-hop ball has ten vertices; Figure 3 reports mean node accuracy across five seeds.Source: §N.2 · pp. 42–43

N.3 Inference-time quantization

  • The exploratory TRIANGLE palette sweep shows close agreement with continuous inputs for q ≥ 4 and nonmonotonic behavior at smaller palettes.It evaluates one frozen model; the reported error bars reflect ten paired feature draws, not training-seed variability.Source: §N.3 · p. 44, Figure 7 · p. 45
Loading 2610.12809v1…