Research map / Architectures and efficiency / RNNs and normalization
On dimensionality of feature vectors in MPNNs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a simple proof that MPNNs with 1-dimensional feature vectors and any non-polynomial analytic activation match the 1-WL test, using linear independence over the rationals, and validates it experimentally with sigmoid MPNNs on random graphs.
Problem
Whether MPNNs need feature dimension growing with graph size (O(n) in Morris et al., O(log n) in Aamand et al.) to match the expressive power of the Weisfeiler-Leman test, and whether constant-dimensional continuous features suffice.
Approach
Replaces linear independence over the reals with linear independence over the rationals: encodes WL multisets as integer combinations of scalar features and uses a non-polynomial analytic activation with a single generic parameter gamma to keep the features rationally independent, yielding a simple, uniform 1-dimensional construction.
Key results
- For 50 random gamma values, 45 (Erdos-Renyi) and 44 (scale-free) achieved perfect WL simulation on all 300 graphs with sigmoid activation.
- Minimum precision bits needed for perfect simulation grows approximately as O(log n) in graph size, for n from 50 to 3000.
- The 1-dimensional construction extends to k-order non-folklore MPNNs for any k >= 2 with 1-dimensional features.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a one-dimensional MPNN with sigmoid activation and a shared random gamma | MPNN · Barabási-Albert random graphs (300 graphs) | gamma values perfectly simulating WL on all graphs: 45 | Helped |
| Use a one-dimensional MPNN with sigmoid activation and a shared random gamma | MPNN · Erdos-Renyi random graphs (300 graphs) | gamma values perfectly simulating WL on all graphs: 47 | Helped |
| Use smaller gamma values | 1D MPNN · Random Erdos-Renyi graphs | precision required for perfect simulation | Helped |
| Increase the number of precision bits | 1D MPNN · CORA and a 5000-node Erdos-Renyi graph | number of WL label classes recovered | Helped |
Surprising findings
- Nearly every randomly chosen gamma in (0,1) yields perfect WL simulation with a single scalar feature, suggesting the construction is generic rather than fine-tuned.
Limitations
- Core guarantee assumes exact real arithmetic with arbitrary precision; finite-precision experiments are needed to approximate it.
- Experiments are restricted to unlabeled graphs and only test simulation, not learning or generalization.
Experimental setup
Datasets: random Erdos-Renyi graphs random scale-free Barabasi-Albert graphs CORA
Benchmarks: CORA random Erdos-Renyi graphs (5000 nodes)
Metrics: fraction of graphs perfectly simulated by WL labeling number of WL classes vs precision bits minimum precision bits vs graph size
Baselines: Morris et al. (AAAI'19) Aamand et al. (NeurIPS'22) Amir et al. (NeurIPS'23)
Builds on: Morris et al. WL-GNN equivalence Aamand et al. randomized O(log n) construction Amir et al. one-dimensional MPNN result
Closest papers by meaning
- Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks (NeurIPS 2022 · similarity 0.86)
- WL meet VC (ICML 2023 · similarity 0.86)
- Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman (NeurIPS 2023 · similarity 0.86)
- On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters (ICLR 2024 · similarity 0.85)
- What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 2024 · similarity 0.84)
- Higher-Order Graphon Neural Networks: Approximation and Cut Distance (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.