Abstract
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