Research map / Graph learning / GNN architectures
Deep Homomorphism Networks
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 the deep homomorphism network (DHN), a GNN built from graph homomorphism layers that enumerate local pattern homomorphisms with non-linear feature transforms, and characterises its expressive power via homomorphism indistinguishability.
Problem
Existing GNNs either cannot detect subgraph patterns beyond trees (MPGNNs) or are too expensive on large graphs (k-WL / higher-order GNNs, subgraph GNNs); explicit pattern counting methods are non-deep and inefficient in expressive power.
Approach
Generalise graph homomorphism numbers to rooted graphs with features using learnable non-linear node-wise transforms, wrap them in a GNN layer, and stack layers deeply so that l layers capture homomorphism counts from exponentially many (2^O(l)) patterns generated by iterated rooted products of a base pattern set.
Key results
- DHN with cycle and clique patterns (C2K3:5) solves CSL, EXP and SR25 at 100%, 100% and 100% accuracy respectively, with 36k parameters versus 355k for N2-GNN.
- On ENZYMES, DHN variants reach about 63-64% accuracy versus 58.2% for PPGN, but below reported state of the art (~78%).
- On PROTEINS, DHN variants achieve about 76-78% accuracy, comparable to PPGN (77.2%) but below reported state of the art (~84%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use cycles of lengths 2 to 10 rather than cycles of lengths 2 to 4 (ablation) | DHN · EXP | accuracy (%): 50 -> 98 | Helped |
| Add a second layer with cycles of lengths 2 to 5 (ablation) | DHN–pC2:5q · EXP | accuracy (%): 81 -> 99 | Helped |
| Add clique patterns K3:5 (ablation) | DHN · SR25 | accuracy (%): 0 -> 100 | Helped |
| Use cycle patterns alone rather than clique patterns for the SR25 task (ablation) | DHN · SR25 | accuracy (%) | No clear effect |
Surprising findings
- Stacking a second homomorphism layer raises EXP accuracy from 81% (single layer C2:5) to 99%, showing depth helps expressivity.
- A single-layer DHN with cycles only (C2:10) reaches 98% on EXP but 0% on SR25, since SR25 is co-spectral and cycles cannot separate it.
Limitations
- Essentially a homomorphism extension of MPGNN, so it cannot capture arbitrarily long cycles.
- Not competitive on real-world graph classification benchmarks (ENZYMES, PROTEINS) against state-of-the-art engineered models.
- Pattern enumeration takes Omega(n^k) time on dense graphs, so it is unsuitable there.
Experimental setup
Datasets: CSL EXP SR25 ENZYMES PROTEINS
Benchmarks: CSL EXP SR25 ENZYMES PROTEINS
Metrics: accuracy
Baselines: MPNN (GIN) PPGN I2-GNN N2-GNN
Builds on: Weisfeiler-Lehman test generalised homomorphism number (Nguyen and Maehara) Barcelo et al. homomorphism node features GIN Paolino et al. cycle GNN
Closest papers by meaning
- Homomorphism Counts for Graph Neural Networks: All About That Basis (ICML 2024 · similarity 0.92)
- Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.90)
- Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness–Generalization Perspective (NeurIPS 2025 · similarity 0.89)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.89)
- Beyond Message Passing: Neural Graph Pattern Machine (ICML 2025 · similarity 0.89)
- What Is Missing For Graph Homophily? Disentangling Graph Homophily For Graph Neural Networks (NeurIPS 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.