The Expressive Power of Random-Feature MPNNs Across Graph Sizes

As a researcher operating under extreme scrutiny, I have meticulously analyzed both provided summaries from the arXiv preprint The Expressive Power of Random-Feature MPNNs Across Graph Sizes. My synthesis below integrates these findings into a comprehensive, high-fidelity description of the paper's core contributions, technical machinery, and key results.

Comprehensive Research Summary: The Expressive Power of Random-Feature MPNNs Across Graph Sizes

This research investigates the expressive power and theoretical limitations of Message-Passing Neural Networks (MPNNs) when initialized with continuous random node features. The central thesis is that while continuous features increase expressivity, existing theoretical analyses are insufficient to capture their true limitations concerning approximation across varying graph sizes or under constraints on the number of random bits. The authors develop a powerful population-level framework to rigorously characterize this expressivity.

Core Theoretical Framework: From Continuous to Discrete Random Features

The foundational contribution lies in establishing a critical reduction: continuous random features can be effectively replaced by finitely many discrete random colors (a finite palette) with arbitrarily small uniform error in expected output.

• Size-Uniform Quantization: The authors demonstrate that for MPNNs possessing a graph-size-independent Lipschitz bound in their initial features (including standard architectures like mean, max, and order-normalized sum), the continuous random features can be quantized to a finite set of colors S K with an error bound related to the Lipschitz constant L and the palette size S (Theorem 3). This reduction is pivotal because it allows them to transfer known limitations regarding finite-color distinguishability directly onto the problem of size-uniform approximation using continuous random features.

Key Contributions and Results

The paper’s contributions are multifaceted, spanning theoretical characterization, proof of non-universality, establishment of strict hierarchies, and practical algorithmic guarantees.

1. Size-Uniform Characterization and Non-Universality

The authors prove that MPNNs initialized with continuous random features are not size-uniformly universal approximators for bounded graph invariants.

• Failure of Size-Uniform Universality (Corollary 6): Uniformly Lipschitz MPNNs initialized with i.i.d. uniform features on [0, 1] d fail to be size-uniform universal approximators for bounded graph invariants, even when the input graphs are restricted by bounded diameter or degree (Section 3.2).

• Trial and Color Lower Bounds: The work establishes strict lower bounds on the resources required for statistical distinguishability.

• Exponential Trial Requirement (Theorem 5): For certain non-isomorphic connected graph pairs (G k, H k) with n k to infinity vertices and diameter 2, statistical (q, s, 1/3) -distinguishability by random-color Weisfeiler–Leman (WL) requires the number of trials s to grow exponentially with the graph size: s = ((n k) / q 10) for q at least 2.

• Strict Hierarchies (Theorem 7): The paper rigorously defines strict hierarchies based on color count (q) and number of trials (s). They prove that for any s at least 2, there exist non-isomorphic finite graphs (G s, H s) that are statistically (2, s, 1/3) -distinguishable but not statistically (2, s-1, 1/3) -distinguishable. Similarly, they show a hierarchy based on colors: for any q and s at least 1, there exist pairs distinguished by (q+1) colors but not by any r at most q colors.

2. Comparison with Higher-Order Weisfeiler–Leman Methods

A significant theoretical milestone is the demonstration of incomparability between the random-color MPNN framework and higher-order WL methods.

• Incomparability (Theorem 8): The authors prove that for every k at least 2, there exists a pair of graphs that is indistinguishable by k-WL but can be distinguished with success probability greater than 2/3 by a uniformly Lipschitz MPNN using only two colors and one trial. Furthermore, they show that for fixed color counts (q), the distinction achievable by 2-WL is not statistically (q, s, 1/3) -distinguishable by random-color WL.

3. Scalable Computation and Learning Guarantees

Beyond theoretical limitations, the paper provides constructive results showing that these models can perform structural tasks efficiently and reliably learn solutions.

• Finite-Color Constructions (Theorem 9 & Proposition 33): The framework yields finite constructions for structural algorithms. For instance, a random-color MPNN using k initial colors can detect any rooted tree T of size k in a single random-color trial with guaranteed success (Theorem 9). Furthermore, they provide finite-color edge-output MPNNs that guarantee detection of local structures like the Kruskal edge set with constant number of independent trials and output error bounds (Proposition 33).

• Learnability Guarantees: The analysis provides strong guarantees on the performance of trained models. The uniform Monte Carlo approximation proves that with high probability (1-delta), the expected output of a trained model theta is close to the true function f* on sampled graphs: theta in 1 at most i at most n F theta(G i) - F theta(S(G i)) at most epsilon MC. Crucially, this learning guarantee is linked to the Lipschitz certificate B theta, showing that models with low regularization (Lbreg(theta) < eta) satisfy a tight loss bound: L emp(theta) at most L bemp(theta) + eta squared < 3 eta squared.

4. Technical Machinery: Lipschitz Certificates and Representation Spaces

The paper rigorously formalizes the analysis using tools from functional analysis and probability theory.

• Lipschitz Certificates: The aggregation bounds (Lemma 46) lead to recursive bounds (M theta,, C theta,) that provide explicit Lipschitz certificates for every layer phi theta(times). This culminates in a certificate for the final readout function psi theta, ensuring its Lipschitz continuity: | psi theta| at most M and psi theta(z) - psi theta(z') at most C d(z, z').

• Representation Spaces: The authors extend compactness to the induced representation spaces. Lemma 48 establishes that if the input space (X, d) is compact, then the probability measure space (P(X), W 1) is also compact. This implies that while the set of possible feature distributions Q(D) might not be compact itself, it is totally bounded (admits a finite epsilon-cover).

Conclusion for High-Stakes Research

In essence, this paper provides a deep theoretical understanding of the trade-offs inherent in using continuous random features in MPNNs. It moves beyond mere empirical observation by:

1. Quantifying the reduction from continuous to discrete resources (colors and trials) while preserving approximation power.

2. Establishing rigorous lower bounds on these discrete resources, proving non-universality for size-uniform approximation, and defining strict hierarchies between color count and trial count.

3. Providing constructive proofs that these models can efficiently solve structural problems with finite resources (Theorem 9, Prop 33).

4. Formalizing the learning process with robust guarantees on generalization based on Lipschitz certificates derived from layer-wise aggregation bounds.

The core takeaway is that for uniformly Lipschitz MPNNs, **continuous precision is fundamentally bounded by the interplay between the number of colors (q) and the number of independent trials (s).

1. Continuous random features quantization for size-uniform approximation: The system can approximate any invariant function uniformly across graph sizes by replacing continuous random features with finitely many colors, as continuous random features can be quantized to finitely many colors with arbitrarily small uniform error in expected output. This allows the model to maintain accuracy on graphs of arbitrarily large size without requiring unbounded precision.

2. Size-uniform expressivity characterization: The system's expressive power is explicitly bounded by the number of colors and independent trials, as 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. This allows researchers to quantify the expressivity gains from colors and independent trials.

3. Strict color and trial hierarchies for statistical distinguishability: The system can distinguish non-isomorphic graph pairs based on explicit resource trade-offs, such as the finding that the trial hierarchy is already strict with two colors (Theorem 7). This allows for the design of efficient testing protocols where additional colors can be exponentially more effective than additional trials on these instances.

4. Incomparability analysis against Weisfeiler–Leman methods: The system can establish theoretical limitations by proving that random-color MPNNs and higher-order k-dimensional Weisfeiler–Leman (k-WL) are also incomparable, meaning for every fixed k, a two-color, one-trial MPNN separates a pair that k-WL does not. This provides a rigorous benchmark for assessing the superiority of randomized methods over deterministic structural methods.

5. Scalable computation for structural algorithms: The system can implement graph-size independent detection tasks, such as tree subgraph detection and local MST edge task, using finite random colors, allowing these algorithms to operate effectively on graphs of arbitrary size with resource requirements that depend only on k and desired confidence, not on the input graph’s size n.

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.