Research map / Graph learning / GNN architectures
Homomorphism Counts for Graph Neural Networks: All About That Basis
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.
Shows that injecting the homomorphism basis of a graph motif parameter into GNNs is strictly more expressive than injecting subgraph or homomorphism counts alone, at no extra computational cost, and validates this on ZINC, QM9, COLLAB and BREC.
Problem
GNNs cannot count graph patterns such as cycles, and it is unclear whether subgraph counts or homomorphism counts are the better features to inject for expressiveness; the paper asks which information strictly subsumes both.
Approach
Inject the homomorphism basis of a graph motif parameter (the homomorphism counts of all quotient graphs in its support, e.g. spasm of the pattern) rather than the parameter itself; the paper proves this is at least as expressive and strictly more expressive under mild conditions, including node-level (anchored) variants.
Key results
- On ZINC-12K, adding spasm^(C7) and C8 node-level counts reduces GIN's MAE from 0.294 to 0.146 (spasm-anchored), and BasePlanE from 0.124 to 0.100.
- On QM9, adding graph-level homomorphism counts of connected graphs up to 5 vertices plus C6 improves R-GCN on all 13 properties, e.g. alpha MAE 4.22 to 1.77 and U0 7.82 to 1.09.
- On BREC, PPGN with node-level homomorphism counts of connected graphs up to 5 vertices reaches 76.25% total, the reported state of the art, and distinguishes over twice as many regular graphs as PPGN (85.7% vs 35.7%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add node-level anchored homomorphism counts from spasm°(C7) ∪ spasm°(C8) | GAT, GCN, GIN, and BasePlanE · ZINC-12K | MAE: GAT: 0.457 ± 0.004 -> 0.147 ± 0.004; GCN: 0.417 ± 0.007 -> 0.165 ± 0.004; GIN: 0.294 ± 0.012 -> 0.146 ± 0.005; BasePlanE | Helped |
| Add graph-level Hom(Ωcon≤5 ∪ {C6}) features | R-GCN · QM9, all 13 properties | MAE | Helped |
| Add node-level homomorphism counts from the P6 basis | GCN and GAT · COLLAB | Hits@50: GCN: 46.13% -> 50.35%; GAT: 48.27% -> 51.62% | Helped |
| Encode Hom(spasm(P6)) counts with an MLP instead of positional encoding (ablation) | GAT · COLLAB | Hits@50 | Hurt |
| Use positional encoding for Hom(spasm(P6)) counts (ablation) | GAT · COLLAB | Hits@50 | Helped |
| Vary positional encoding dimension (ablation) | GAT with Hom(spasm(P6)) · COLLAB | Hits@50 | No clear effect |
| Add homomorphism counts of Ωcon≤5 | GIN and PPGN · BREC total | correctly distinguished graph-pair percentage: GIN + Hom: 69%; PPGN + Hom: 76.25%; PPGN: 58.2%; GSN: 63.5%; I²-GNN: 70.2% | Mixed |
Surprising findings
- On ZINC, GAT with spasm^ counts matches GIN, suggesting the homomorphism basis lifts GAT to 1-WL-level performance for this task.
- Injecting homomorphism counts through an MLP encoder degraded GAT performance on COLLAB with high variance, while a sinusoidal positional encoding improved it.
Limitations
- Expressiveness gain on ZINC was not reflected in performance for stronger models; the authors note additional expressiveness of spasm^ seemed irrelevant to the ZINC task.
- Homomorphism counts can span very large ranges in big graphs, and the encoding choice matters; the paper only partially addresses this with positional encoding.
- Experiments use mostly standard architectures without tuning; the authors note that combining with top-performing models is left for future work.
Experimental setup
Datasets: ZINC-12K QM9 COLLAB (OGB) BREC
Benchmarks: ZINC-12K QM9 COLLAB (OGB link prediction) BREC
Metrics: mean absolute error Hits@50 number of distinguished graph pairs (percentage)
Baselines: GAT GCN GIN BasePlanE R-GCN PPGN GSN I2-GNN 2-WL^4 (higher-order)
Builds on: subgraph GNNs (GSN) homomorphism expressivity (Dell et al.) graph motif parameters (Roberson / Curticapean et al.) PPGN BasePlanE
Closest papers by meaning
- Deep Homomorphism Networks (NeurIPS 2024 · similarity 0.92)
- Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.92)
- Homomorphism Counts as Structural Encodings for Graph Learning (ICLR 2025 · similarity 0.90)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.90)
- On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters (ICLR 2024 · similarity 0.90)
- Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning (NeurIPS 2024 · similarity 0.89)
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.