k-th Order Deep Homomorphism Networks

We develop a pattern-algebraic framework for higher-order graph neural networks by extending Deep Homomorphism Networks (DHN) from rooted patterns to $k$-labelled patterns. The framework captures GNN expressivity along two independent axes — skeleton complexity $k$, controlling global structures, and pattern vocabulary $\mathcal{P}$, capturing local structures. We then introduce auxiliary gluing ($⊛$), the pattern-algebraic counterpart of the $k$-FWL sift, and prove that this single additional operation lifts $k$-label expressive power to $(k+1)$ labels, yielding an algebraic proof of $(k+1)$-WL $\equiv$ $k$-FWL. Neuralising these operations gives $k$-DHN and $k$-FDHN, which recover $k$-GNN, PPGN, $\delta$-$k$-LWL, $r$-$\ell$WL, spectral invariant GNNs, and node-marking subgraph GNNs as special cases, with expressivity exactly characterised by the pattern closure of $(k,\mathcal{P})$. The framework also resolves open expressivity separation problems in the $\delta$-$k$-LWL and $r$-$\ell$WL hierarchies.