k-th Order Deep Homomorphism Networks
@inproceedings{maehara2026k,
author={Takanori Maehara},
title={{k-th Order Deep Homomorphism Networks}},
booktitle={Proceedings of the 40th Annual Conference on Neural Information Processing Systems (NeurIPS'26), Sydney, Australia, December 6--12, 2026},
month={December},
year={2026},
}
k-th Order Deep Homomorphism Networks (k-DHN) is a generic construction of higher-order graph neural networks whose expressive power is specified in advance, in homomorphism terms: you pick a skeleton complexity k and a pattern vocabulary P, and the network's expressive power is exactly the homomorphism-distinguishing closure of the patterns those two generate. It is the direct successor of Deep Homomorphism Networks, and the latest in a line of my work connecting graph homomorphisms and graph neural networks that began with Graph Homomorphism Convolution.
Personal motivation
For me, this paper started with an unfinished question from DHN: what should its higher-order version look like?
DHN was a practically motivated paper. Running on large sparse graphs requires linear time, and k = 1 is the order that runs in linear time, so k = 1 is what people use — and the only case we did.
k ≥ 2 gives up linear time, which leaves it of mostly theoretical interest, so we did not pursue it. There was also a technical reason: we did not then know the natural higher-order extension of the rooted product, the operation DHN's layer is built from.
After publishing DHN, I came across Zhang et al.'s ICLR'24 paper, Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness. It measures GNN expressivity in homomorphism counts. It made two things clear to me. k ≥ 2 is mostly theoretical, but it is not without interest. DHN answers the inverse question: given the homomorphism expressive power you want, build a GNN that has it. That was enough to make me go back and close this line of work with a higher-order DHN.
Technical resolution
The technical blocker was resolved by Seppelt's An Algorithmic Meta Theorem for Homomorphism Indistinguishability, which analyses homomorphism indistinguishability in Courcelle's algebra of k-sourced graphs. Its two operations on k-labelled patterns, series composition and gluing, are the extension of the rooted product I had been missing: each has a recursive formula for homomorphism counts, so each neuralises into a layer.
Finding those two operations was essentially the whole of k-DHN: with them in place, most of the proofs generalise from DHN naturally. The more interesting part was its applicability. With the pattern vocabulary chosen suitably, k-DHN represents existing models — k-GNN, PPGN, the adjacency-initialised δ-k-LWL, spectral invariant GNNs — and that convinced me it was the right generalisation.
Extending the algebra
I did not stop there. In practice the folklore version of WL is the more commonly used one, so I wanted a folklore version of k-DHN as well — k-FDHN. My first attempt was to get FWL the way the other models come out, by choosing a pattern vocabulary. That does not work: the algebra itself has to be extended.
My understanding is that a GNN, or a WL test, is the dual of a pattern algebra. An identity of the form
hom(A patternOp B, _)
= hom(A, _) layerOp hom(B, _)
computes the homomorphism number of a composed pattern from the homomorphism numbers of its parts. The goal here was to invent a pattern operation whose homomorphism numbers compose by the folklore WL formula, the sift.
After several attempts I arrived at the operation I call auxiliary gluing,
or AuxGlue (⊛). It takes k patterns F_1, …, F_k, each carrying k labels. In
F_i, label i is renamed to a temporary label *; the operands are glued at
every label they share, * included; then * is forgotten, so its vertex
stays in the pattern but carries no label. Every ordinary label j survives on
the operands with i ≠ j, so the result is again a k-labelled pattern.
On homomorphism numbers it satisfies
hom(⊛(F_1, …, F_k), (G, u))
= Σ_{w ∈ V} Π_i hom(F_i, (G, u[i ← w])).
The right-hand side is the sift. The sum over all vertices w is what told us
the operation needed a vertex of its own: gluing at * creates it, and
forgetting * leaves it unlabelled. During the construction that vertex acts
as a (k+1)-th label, which is where the extra expressive power comes from;
afterwards it is an ordinary vertex of the pattern.
The lifting theorem
The mathematically difficult part was the lifting theorem. If I was going to
call something a folklore version, it ought to satisfy the generalisation of
(k+1)-WL ≡ k-FWL; recovering the sift formula alone did not settle that. For
the treewidth vocabulary it means showing that AuxGlue generates patterns of
treewidth k instead of stopping at k − 1.
Why it holds has a short intuition. A construction that follows a tree decomposition with bags of size k+1 would normally need k+1 labels; with AuxGlue, k labels suffice, because the auxiliary vertex stands for the one vertex of the bag that carries no label. The running intersection property is what makes that sound: the bags containing a vertex form a connected subtree, so a vertex that stops being tracked never needs tracking again, and the choice of which vertex is auxiliary survives as the construction proceeds.
Framework demonstration
The appendix is designed to demonstrate the pattern-algebraic framework established in the main body. The slogan is that analysing a model becomes analysing a pattern algebra: ask which patterns a given algebra generates. It works through several uses of that, including separations between model classes.
Among them: the adjacency-initialised δ-k-LWL and SLFWL(k) are each strictly weaker than k-FWL for every k ≥ 2, which settles cases of open problems posed by Morris et al. and Zhang et al.; node-marking subgraph GNNs get a matching 3-WL upper bound; and the bounded-cycle cactus class behind r-ℓWL is homomorphism-distinguishing closed, sharpening the lower bound of Paolino et al. The separations all run through a CFI-based recipe that reduces each proof to a finite F₂ case analysis.
Side notes
Three things in this paper were first attempts for me.
Burn. The machine-learning code is written in Rust, on the Burn framework. Research code of this kind is almost always Python on PyTorch, so Rust is an uncommon choice for it. k-DHN was a good fit for the attempt, because the work the model actually does is enumeration and homomorphism counting, which rewards a fast language. Rust is my usual language anyway; the framework was the new part.
AI assistance. This is the first manuscript where I used AI as a serious part of the work: tightening proofs, and supporting the experiments. On concrete tasks of that kind it worked very well. It had much more difficulty with the ambiguous ones — setting the research question, and judging what belongs in the manuscript.
Lean. The main theorems are formalised in Lean 4 against Mathlib, in
proofs/in the repository. This is where the AI assistance paid off: writing Lean by hand is slow, heavy work, and AI turned out to be good at it. What came back was a sharper view of my own proofs — the formalisation surfaced steps I had been relying on without writing them down, and some of those were false. Lean lets none of that through.