Research map / Graph learning / GNN architectures
Homomorphism Counts as Structural Encodings for Graph Learning
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.
Proposes motif structural encoding (MoSE), which uses node-rooted homomorphism counts of pattern graphs as structural encodings for Graph Transformers, and shows it is more expressive than RWSE and improves GPS/GRIT on ZINC, QM9, PCQM4Mv2-subset and CIFAR10.
Problem
Structural and positional encodings for Graph Transformers lack theoretical expressivity understanding; RWSE, a popular molecular encoding, is weaker than 1-WL on some node pairs and is bounded by 2-WL.
Approach
Use node-rooted (optionally weighted) homomorphism counts from a chosen family of pattern graphs as a node encoding (MoSE). It generalizes RWSE (cycles with reciprocal-degree weights), is incomparable to the WL hierarchy in a controllable way, and can be chosen to match motif-based expressivity.
Key results
- GRIT+MoSE achieves 0.056 MAE on ZINC-12K, state of the art over GRIT+RRWP (0.059) and other baselines.
- GPS+MoSE reaches 73.50% accuracy on CIFAR10 vs 71.96% for GPS+RWSE, and 0.062 MAE on ZINC vs 0.070 for RWSE.
- GPS+MoSE achieves best MAE on 11 of 13 QM9 targets compared with GPS+RWSE.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace RWSE with MoSE in GPS | GPS · ZINC-12K | MAE: 0.069 ± 0.001 -> 0.062 ± 0.002 | Helped |
| Replace RWSE with MoSE in GRIT, omitting pairwise encodings | GRIT · ZINC-12K | MAE: 0.059 ± 0.002 -> 0.056 ± 0.001 | Helped |
| Replace RWSE with MoSE in GPS | GPS · PCQM4Mv2-subset | MAE: 0.1159 ± 0.0004 -> 0.1133 ± 0.0014 | Helped |
| Replace RWSE with MoSE in GPS | GPS · CIFAR10 | accuracy: 71.96 ± 0.40 -> 73.50 ± 0.44 | Helped |
| Replace RWSE with MoSE in GPS | GPS · QM9 molecular properties | MAE | Mixed |
| Replace RWSE with MoSE across model architectures | MLP-E, GIN-E, GIN-E+VN, GT-E, and GPS · ZINC-12K | MAE | Helped |
Surprising findings
- MLP+MoSE outperforms GT+RWSE and GT+LapPE on the synthetic fractional domination task.
- MLP+LapPE performs significantly worse than other configurations, suggesting self-attention is needed to exploit LapPE.
Limitations
- Relationship between MoSE and spectral methods is left open.
- The node-weighting parameter is not fully explored.
- Exact homomorphism counting complexity is O(|G|^tw(H)), so the pattern choice determines cost.
Experimental setup
Datasets: ZINC-12K PCQM4Mv2-subset CIFAR10 QM9 MNIST Peptides-func Peptides-struct
Benchmarks: ZINC-12K PCQM4Mv2-subset CIFAR10 QM9 synthetic fractional domination
Metrics: MAE accuracy
Baselines: LapPE RWSE PEG SignNet GRIT+RRWP GSN CIN Subgraphormer R-GIN R-SPN E-BasePlanE GIN-E
Builds on: GPS GRIT random-walk structural encoding Weisfeiler-Leman hierarchy homomorphism counts for MPNNs
Closest papers by meaning
- Simple Path Structural Encoding for Graph Transformers (ICML 2025 · similarity 0.90)
- Homomorphism Counts for Graph Neural Networks: All About That Basis (ICML 2024 · similarity 0.90)
- From Theory to Practice: Rethinking Green and Martin Kernels for Unleashing Graph Transformers (ICML 2025 · similarity 0.89)
- Positional Encoding meets Persistent Homology on Graphs (ICML 2025 · similarity 0.89)
- On the Stability of Expressive Positional Encodings for Graphs (ICLR 2024 · similarity 0.89)
- Graph Positional and Structural Encoder (ICML 2024 · similarity 0.88)
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.