Source-linked AI summary
The Surprising Power of Graph Neural Networks with Random Node Initialization
Ralph Abboud, İsmail İlkan Ceylan, Martin Grohe, Thomas Lukasiewicz
TL;DR
Standard MPNNs are limited by 1-WL, while higher-order GNNs achieve greater expressiveness at high computational cost. This paper analyzes random node initialization, proves universality for MPNNs with RNI, and evaluates the result empirically. The experiments support improved learning ability, with slower convergence and greater volatility in sparse settings.
Problem
Standard MPNNs cannot distinguish graphs beyond 1-WL, while higher-order GNNs that overcome this limitation are computationally demanding.
Method
The paper proves universality for MPNNs with RNI using logical characterization and order-invariant definability, then evaluates RNI on EXP and CEXP datasets.
Results
MPNNs with RNI are universal, preserve permutation invariance in expectation, and empirically improve learning ability while slowing convergence.
Takeaways & Limitations
RNI provides a practical route to combine expressive power with the efficiency of MPNNs, supporting performance comparable to higher-order GNNs.
Takeaways & Limitations
The universality theorem can require very large constructions, including for computationally hard functions, and its stated real-valued form extends to weighted graphs only for continuous functions.
Abstract
from arXiv · showhide
Graph neural networks (GNNs) are effective models for representation learning on relational data. However, standard GNNs are limited in their expressive power, as they cannot distinguish graphs beyond the capability of the Weisfeiler-Leman graph isomorphism heuristic. In order to break this expressiveness barrier, GNNs have been enhanced with random node initialization (RNI), where the idea is to train and run the models with randomized initial node features. In this work, we analyze the expressive power of GNNs with RNI, and prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties. This universality result holds even with partially randomized initial node features, and preserves the invariance properties of GNNs in expectation. We then empirically analyze the effect of RNI on GNNs, based on carefully constructed datasets. Our empirical findings support the superior performance of GNNs with RNI over standard GNNs.
1 Introduction
Standard message-passing GNNs are limited by 1-WL, while higher-order alternatives are costly. The paper proves that random node initialization makes MPNNs universal and evaluates this claim on datasets designed to test expressiveness.
- Motivation: Standard MPNNs cannot distinguish several non-isomorphic graph families because they are bounded by the 1-WL heuristic.Higher-order GNNs address this limitation but are computationally demanding, so MPNNs remain widely used.
- Main result: MPNNs with random node initialization are proved universal for functions on graphs of any fixed order.The proof combines a logical characterization of MPNN expressiveness with order-invariant definability.
- Main result: The universality result preserves permutation invariance in expectation while retaining the inductive bias of message-passing models.This contrasts with the expressiveness limit of deterministic MPNNs.
- Empirical evaluation: EXP and CEXP are designed to evaluate RNI when tasks require expressive power beyond 1-WL.CEXP combines 1-WL-distinguishable and higher-expressiveness cases, enabling evaluation in a more variable setting.
- Empirical findings: MPNNs with RNI closely match higher-order GNN performance, but improved performance comes with slower convergence.Partial randomization improves convergence and accuracy, while analogous sparser datasets show similar behavior with more volatility.
2 Graph Neural Networks
GNNs update node representations through invariant or equivariant message passing, but standard MPNNs have 1-WL-level expressiveness. Higher-order GNNs increase expressiveness by operating on node tuples or tensors, at substantially higher computational cost.
- GNN foundations: GNNs learn graph functions by iteratively updating node vectors through invariant or equivariant computational layers.Graph invariance means outputs are unchanged for isomorphic graphs, whereas equivariance tracks node permutations.
- Message passing: MPNNs aggregate neighboring messages to update node representations, then use final representations to compute target outputs.GCNs and GATs are prominent examples of MPNNs.
- Message passing: Standard MPNNs have the same expressive power as 1-WL and therefore cannot distinguish graphs that 1-WL fails to separate.The paper illustrates this with non-isomorphic graphs G and H that receive identical treatment under 1-WL.
- Message passing: Global readouts aggregate states across all nodes to address the inability of edge-based message passing to share information between disconnected components.The paper focuses on MPNNs with global readouts, called ACR-GNNs.
- Higher-order GNNs: Higher-order GNNs pass messages between node tuples or use higher-order tensors, but their memory requirements grow substantially with graph size.k-GNNs require O(|V|^k) memory, while invariant and equivariant networks can use tensor orders of O(|V|^2).
3 MPNNs with Random Node Initialization
The paper shows that random node initialization makes message-passing neural networks universal for invariant graph functions while preserving permutation invariance in expectation. The result extends to partial randomization, but universal constructions may be large.
- Invariance: RNI preserves MPNN permutation invariance in expectation despite making individual computations depend on both graph structure and random initialization.The randomized model is analyzed as a probabilistic approximation of an invariant function.
- Universality: RNI makes MPNNs universal, enabling approximation of every invariant real-valued function on graphs with at most n vertices.For all ϵ,δ > 0, an MPNN with RNI (ϵ,δ)-approximates the function.
- Proof strategy: The proof combines logical characterization of MPNNs with constructions that individualize graphs using randomized node embeddings.Individualized graphs are represented in two-variable counting logic, then extended from Boolean to real-valued functions.
- Implications: Universality holds with partial RNI, including only one randomized dimension, and the construction adapts to the descriptive complexity of the target function.The paper gives an embedding-dimensionality bound of O(n^2δ^-1) for distinguishing individual graphs.
- Scope: The universality theorem can yield very large constructions because it covers functions of arbitrary computational complexity, including hard-to-approximate problems.The authors therefore evaluate practical capacity empirically relative to higher-order GNNs.
4 Datasets for Expressiveness Evaluation
The authors construct EXP and CEXP to evaluate graph expressiveness directly, using instances that separate the capabilities of 1-WL, 2-WL, and randomized MPNNs. CEXP adds mixed-difficulty examples to test variable expressiveness requirements.
- EXP: EXP addresses the weakness of real-world benchmarks by containing graph pairs that standard MPNNs cannot distinguish but higher-order models can.Each pair is non-isomorphic, has different SAT outcomes, is 1-WL indistinguishable, and is 2-WL distinguishable.
- EXP: EXP graph pairs are built from planar core pairs whose satisfiability-determining substructures must be distinguished for good performance.The cores encode satisfiable and unsatisfiable propositional clauses while satisfying the required WL properties.
- CEXP: CEXP combines unmodified EXP pairs with corrupted pairs that become 1-WL distinguishable after adding a small number of edges.Half the data is labelled CORRUPT and half remains expressive-power-demanding EXP data.
- CEXP: Because CEXP preserves the same core structures while assigning different SAT values across EXP and CORRUPT, it creates a more challenging mixed learning task.
5 Experimental Evaluation
The experiments compare standard, randomized, partially randomized, and higher-order GNNs on EXP and CEXP. RNI substantially improves expressiveness with lower computational cost, while partial randomization improves mixed-data performance and RNI slows convergence.
- EXP performance: GCN-RNI exceeds 95% accuracy on EXP under all four tested randomization distributions, substantially surpassing the 50% standard-GNN baseline.The evaluation uses 600 graph pairs and 10-fold cross-validation.
- EXP performance: PPGN remains at or below random performance on EXP despite theoretical 2-WL expressiveness, whereas 3-GCN achieves near-perfect performance.The authors attribute PPGN’s difficulty to learning required power-sum polynomials and the dataset’s sample size and variability.
- Convergence: 3-GCN reaches optimal EXP performance in about 10 epochs, while every GCN-RNI model requires more than 100 epochs.The slower convergence is associated with learning from randomized rather than deterministic embeddings.
- Efficiency: For a 50-node graph, GCN-RNI uses 3,200 parameters versus 1,254,400 for 3-GCN while performing comparably and scaling more easily.
- Convergence: On CEXP, 3-GCN exceeds 90% accuracy within 25 epochs, whereas GCN-RNI models converge around 200 epochs and fully randomized variants perform worse than partial RNI.
- CEXP performance: On CEXP, partially randomized GCNs outperform fully randomized GCN-RNI because deterministic dimensions help with CORRUPT while randomized dimensions help with EXP.GCN-50%RNI achieves perfect performance on both subsets in the reported learning-curve comparison.
6 Related Work
Prior work established that RNI can extend MPNNs beyond 1-WL for fixed substructures and certain combinatorial problems, but its impact on arbitrary graph functions remained open. This paper proves universality and studies RNI in a harder SAT setting without relying on local structures.
- Prior work: RNI lets MPNNs distinguish some 1-WL-indistinguishable graph pairs through fixed local substructures.Earlier results also showed near-optimal approximation for specific combinatorial optimization problems.
- Open question: The precise effect of RNI on learning arbitrary functions over graphs was previously unresolved.
- This paper: The paper proves that MPNNs with RNI can learn arbitrary real-valued functions over graphs.The result is based on a logical characterization linking MPNN size to the descriptive complexity of the target function.
- Empirical study: The empirical study examines RNI on SAT, a challenging target that does not rely on local structures.
- Comparison: Unlike random pre-set color features, RNI does not predefine node-distinguishing features or a fixed underlying structure.RNI can yield potentially infinitely many representations for one graph.
7 Summary and Outlook
The paper finds that MPNNs with RNI are universal while preserving permutation invariance in expectation, and reports empirical gains alongside slower convergence. It identifies polynomial-function capture as future work.
- MPNNs with RNI are universal and preserve MPNN invariance in expectation.
- RNI improves learning ability empirically but slows convergence.
- The paper combines a theoretical result with practical insights to quantify RNI's effect on GNNs.
- Whether polynomial functions can be captured remains an open topic for future work.
A.1 Propositional Logic
This appendix introduces propositional logic terminology used to construct the datasets, including variables, literals, clauses, CNF formulas, assignments, and SAT.
- A literal is a variable or its negation, and a clause is a disjunction of literals.
- The width of a clause is its number of literals, and a k-CNF contains clauses of width at most k.
- An assignment maps propositional variables to False or True and satisfies a formula when the assignment makes it true.
- SAT asks whether a propositional formula has a satisfying assignment and is NP-complete.
A.2 Proof of Theorem 1
The proof establishes universality by representing individualized colored graphs and Boolean functions in two-variable counting logic, then using RNI to create individualized node features with high probability. The construction is expressive but can require very large state spaces.
- Boolean universality: For every invariant Boolean function on graphs with at most n vertices, an MPNN with RNI can approximate it within ε with probability at least 1−δ.
- Logical characterization: The proof uses counting logic C2, whose sentences can be approximated by MPNNs, and connects C2 expressiveness to 1-WL and MPNN indistinguishability.
- Graph identification: Individualized colored graphs have distinct color sets for every pair of vertices, enabling a C2 sentence to identify each graph up to isomorphism.
- Random individualization: RNI randomly initializes node states so that, with probability greater than 1−δ, the resulting node vectors are mutually distinct binary vectors encoding a coloring.
- Complexity: The resulting MPNNs can have prohibitively large state spaces, and Boolean-function approximators may still grow exponentially with n.
A.3 Details of Dataset Construction
The dataset construction uses planar instances designed to remain distinguishable by 2-WL, so GNNs with 2-WL expressive power can theoretically approximate their solutions. This theoretical approximability does not guarantee that such GNNs will learn EXP in practice.
- Planar instances are generated with additional constraints so that 2-WL can distinguish them.This makes them compatible with GNNs possessing 2-WL expressive power.
- GNNs with 2-WL expressive power can theoretically approximate solutions to the constructed planar instances.The result concerns existence of an appropriate approximation function, not demonstrated practical learning.
- The existence of an appropriate approximation function does not imply that these GNNs will solve EXP in practice.
Construction of EXP
EXP is built from planar SAT graph pairs whose cores are 1-WL indistinguishable but 2-WL distinguishable, then augmented with satisfiable planar noise. Extensions and experiments test how RNI behaves across expressiveness requirements, data sparsity, convergence, and activation choices.
- Core pair: EXP pairs an unsatisfiable formula with a satisfiable formula whose planar graph encodings are 1-WL indistinguishable but 2-WL distinguishable.The core pair uses variable chains and bridges to impose contrasting satisfiability constraints.
- Core pair: ϕ1 combines an increasing variable chain with Bridge(2n), while ϕ2 cuts the chain, reverses its second half, and retains the bridge.The construction makes ϕ1 unsatisfiable and ϕ2 satisfiable while preserving planarity.
- Planar component: A randomly generated satisfiable planar component is added identically to each core, increasing variability while preserving planarity, 1-WL indistinguishability, and the opposite SAT labels.The added component is generated from bipartite planar graphs, with bounded disjunction width and satisfiability filtering.