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

arXiv:2601.02451v2 Announce Type: replace-cross 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{-}\gamma)^L$ collapse rate driven by the spectral gap $\gamma$. 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

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{-}\gamma)^L$ collapse rate driven by the spectral gap $\gamma$. 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 this https URL

Machine Learning (cs.LG); Artificial Intelligence (cs.AI)

arXiv:2601.02451 [cs.LG]

(or arXiv:2601.02451v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2601.02451 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

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

Related coverage