mHC-GNN: Manifold-Constrained Hyper-Connections for Graph Neural Networks

Graph Neural Networks (GNNs) suffer from over-smoothing in deep architectures and expressiveness bounded by the 1-Weisfeiler-Leman (1-WL) test. We adapt Manifold-Constrained Hyper-Connections, recently proposed for Transformers, to graph neural networks. Our method, \mhcgnn{}, expands node representations across n parallel streams and constrains stream-mixing matrices to the Birkhoff polytope of doubly stochastic matrices via Sinkhorn-Knopp normalization. We prove that \mhcgnn{} mitigates over-smoothing via a layer-wise residual lower bound showing that node-pair differences decay at rate (1{-}\varepsilon)^L (where \varepsilon measures deviation of the mixing matrix from identity), far slower than the standard (1{-}γ)^L collapse rate driven by the spectral gap γ. This two-regime analysis, via the protected orthogonal subspace for L < n and the layer-wise contraction for L \geq n, provides architecture-agnostic rate guarantees absent from prior methods. With independent random stream initialization, \mhcgnn{} can distinguish graphs beyond 1-WL by maintaining stream diversity across layers via doubly stochastic mixing. Depth experiments spanning 2 to 128 layers reveal that standard GNNs collapse to near-random performance beyond 16 layers, while \mhcgnn{} maintains over 74% accuracy at 128 layers, with improvements exceeding 50 percentage points at extreme depths. Ablations confirm that manifold constraints are essential: removing them causes up to 82% performance degradation. Experiments on heterophilic graphs (roman-empire, penn94, genius) and expressiveness benchmarks (EXP) further validate the contribution. Code is available at https://github.com/smishra-lab/mhc-gnn