Main | Articles

Deep Homomorphism Networks

@inproceedings{maehara2024deep,
  author={Takanori Maehara and Hoang NT},
  title={Deep homomorphism networks},
  booktitle={Proceedings of the 38th Annual Conference on Neural Information Processing Systems (NeurIPS'24), Vancouver, Canada, December 10--15, 2024},
  month={December},
  year={2024},
  url={https://proceedings.neurips.cc/paper_files/paper/2024/hash/65f54fdf62cd5614dc5715ae7ece4ef6-Abstract-Conference.html},
}

The problem

Real graphs are full of characteristic small structures: triangles in social networks, cliques in web graphs, benzene rings in molecules. Detecting them is the bread and butter of network science, so you would hope a graph neural network applied in those fields could see them too.

Message-passing GNNs cannot. Their expressive power is exactly that of the 1-dimensional Weisfeiler–Lehman test, and by a theorem of Dvořák, 1-WL distinguishes two graphs precisely when some tree has a different number of homomorphisms into them. Trees, and nothing else. A triangle is invisible.

The usual fix is to go higher-order — assign values to k-tuples of nodes — which buys you subgraphs of treewidth k at a cost of roughly n^k. On a large sparse graph that is not a trade you can make.

The idea

Instead of bolting pattern counts on as extra input features, make the pattern the unit of message passing.

Fix a small set of rooted patterns P — say a triangle, or cycles up to length 5, or cliques up to size 5. A graph homomorphism layer enumerates, for each node u, all homomorphisms from each pattern into the graph rooted at u. Along each such copy of the pattern it pushes the node features through a learned non-linear transform, one per pattern node, multiplies them together, and sums over all the copies. Stack these layers and you get a deep homomorphism network (DHN).

Message passing is the special case where P is just {a single node, a single edge}: homomorphisms from an edge rooted at u are exactly the neighbours of u, and the layer collapses to the familiar "transform your neighbours, sum them up". So DHN is not a competitor to message passing; it is message passing with a richer alphabet.

What depth buys you

The main theorem pins the expressive power down exactly. A P-DHN can distinguish two graphs if and only if they differ in homomorphism counts from the closure of P under iterated rooted products — the patterns you get by repeatedly gluing a base pattern onto a node of a pattern you already have.

That closure operation is the whole story of depth. Adding one layer means attaching base patterns at every node of every pattern you currently recognise. The paper's Figure 1 makes it concrete: a triangle layer followed by an edge layer detects a "spoon", a shape nobody put in the pattern set. Counting it out, an l-layer DHN counts homomorphisms from 2^O(l) distinct patterns — the expressive power of a GNN grows exponentially in the number of layers. It is rare to get a statement that clean about why deeper helps.

The theorem also turns out to be a useful measuring device. Several existing architectures are DHNs with a particular pattern set — a first layer of arbitrary patterns followed by message-passing layers, or a set of cycles, or the most expressive subgraph GNNs on bounded-degree graphs — so their expressive power follows as a corollary instead of a bespoke proof. Comparing two architectures reduces to comparing two families of graphs, which lets you import decades of graph theory: cycles up to length k, cliques up to size k, and all connected graphs on k nodes form a hierarchy with several genuine incomparabilities.

Does it run?

Computing homomorphism counts is W[1]-hard in general, so nothing is free. But the layer costs exactly what the counts cost, and the counts are cheap in the regimes network science actually lives in: patterns of bounded treewidth take n^(tw+1), bounded-degree hosts give linear time by brute force, and — the useful one — a bounded-degeneracy host with a pattern of bounded DAG-treewidth is also linear. Any pattern with no induced cycle longer than five qualifies.

There is a second, subtler property: a DHN is continuous in the Benjamini–Schramm topology, which means what it computes on a BFS-sampled subgraph approximates what it computes on the whole graph. That is size generalisation, and it is the reason the model is aimed at large graphs. It also explains a limitation honestly: biconnectivity is not a continuous property, so DHN cannot detect it — and any model that can must be discontinuous, and so may not size-generalise. That cuts both ways.

Numbers

On the standard expressivity benchmarks, a two-layer DHN over cycles and small cliques solves CSL, EXP and SR25 at 100% with 36k parameters, against 143k for I²-GNN and 355k for N²-GNN at the same accuracy. The depth story shows up empirically too: one layer of cycles up to length 5 gets 81% on EXP, and adding a single edge layer on top takes it to 99%.

On real graph classification (ENZYMES, PROTEINS) DHN is competitive with those larger models — better on ENZYMES — but short of heavily engineered state-of-the-art. The paper is upfront that this is a theory paper with promising experiments, not a leaderboard entry.

When not to use it

Two honest limitations. If your graphs are small enough that an n^k higher-order model is affordable, use one — that covers a lot of graph classification. And if your graphs are dense, pattern enumeration itself costs n^k and plain message passing is the better tool. DHN earns its keep on graphs that are large, sparse, and known to contain patterns you care about.