26년 1월 2주차 그래프 오마카세

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

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 (\mhc)~\citep{xie2025mhc}, recently proposed for Transformers, to graph neural networks. Our method, mHC-GNN, expands node representations across $n$ parallel streams and constrains stream-mixing matrices to the Birkhoff polytope via Sinkhorn-Knopp normalization. We prove that mHC-GNN exhibits exponentially slower over-smoothing (rate $(1-γ)^{L/n}$ vs.\ $(1-γ)^L$) and can distinguish graphs beyond 1-WL. Experiments on 10 datasets with 4 GNN architectures show consistent improvements. Depth experiments from 2 to 128 layers reveal that standard GNNs collapse to near-random performance beyond 16 layers, while mHC-GNN maintains over 74\% accuracy even at 128 layers, with improvements exceeding 50 percentage points at extreme depths. Ablations confirm that the manifold constraint is essential: removing it causes up to 82\% performance degradation. Code is available at \href{https://github.com/smlab-niser/mhc-gnn}{https://github.com/smlab-niser/mhc-gnn}

arXiv.orgSubhankar Mishra

GitHub - smlab-niser/mhc-gnn: mHC-GNN: Manifold-Constrained Hyper-Connections for Graph Neural Networks

mHC-GNN: Manifold-Constrained Hyper-Connections for Graph Neural Networks - smlab-niser/mhc-gnn

GitHubsmlab-niser

• 딥시크(DeepSeek)는 최근 DeepSeek-V3 등에서 싱크혼(Sinkhorn) 알고리즘을 활용해 MoE의 load balancing 문제를 혁신적으로 해결하며 AI 업계의 많은 관심을 받고 있습니다.
• 이번에 공개된 새로운 논문에서는 이 싱크혼의 마법을 모델의 근간인 잔차 연결(Residual Connection)로 확장합니다. 기존의 단일 경로 잔차 연결을 다중 경로로 확장하려는 시도인 Hyper-Connection은 성능 잠재력은 컸지만, 모델 규모가 커질수록 학습이 폭발적으로 불안정해지는 고질적인 문제가 있었습니다.
  • 어떻게 하면 신호 폭발 없이 모델의 정보 전달 통로를 더 넓고 복잡하게 만들 것인가? 라는 질문에, 딥시크의 해당 저자들은 mHC(Manifold-Constrained Hyper-Connections)를 제안하며, 거대 모델에서도 안정적으로 작동하는 정보의 고속도로를 구축하는 데 성공했습니다.
  • 기존 트랜스포머의 단일 통로를 기반하는 정보의 흐름을 여러 개의 병렬 통로로 확장하여 입체적으로 흐르게 만들었을 때, 연결이 복잡해지면 신호가 기하급수적으로 증폭되어 발산하는 등의 학습이 실패하게 됩니다. 다음을 버코프 폴리토프(Birkhoff Polytope)라는 확률 행렬의 집합 상의 매니폴드 공간 안에 가두고, 싱크혼 알고리즘을 통해 정규화시킴으로써 그래디언트 폭발 및 소멸 등의 학습 문제점을 해결하였습니다.

• 제가 가볍게 해당 논문의 이해를 위해 참고했던 해당 영상은 딥시크의 mHC 기술이 어떻게 기존 잔차 연결의 한계를 극복하고 대규모 모델의 안정성을 확보했는지 수학적 원리와 함께 시각적으로 설명해 주어 논문의 배경 이해에 큰 도움이 될 수 있습니다.
• 제목 그대로(Manifold-constrained hyper-connection), 매니폴드 상으로 제약시킨 복잡한 다중 연결 통로의 장점을 취하면서 향후 초거대 모델들이 기존의 병목 현상을 넘어 훨씬 더 복잡하고 강력한 구조로 진화할 것임을 예고합니다.

• 이번 주 오마카세로 전달해드리고자 하는 논문은 GNN의 고질적인 문제인 Over-smoothing와 1-WL Test 표현력 한계를 해결하기 위해 mHC를 통합하는 새로운 방식을 제안했습니다.
• 기존 GNN에서는 각 노드가 하나의 피처 벡터만 가졌습니다. mHC-GNN은 기존 mHC의 아이디어를 따라 이를 확장하여, 각 노드가 n개의 병렬 스트림을 가진 행렬로 데이터를 유지하게 합니다. 다음은 그래프 신경망의 레이어가 깊어질수록 하나의 통로로 정보가 합쳐지면서 업데이트 시 피처 벡터가 유사해져버리는 문제를 여러 개의 병렬 통로에 나누어 담음으로써 층이 깊어져도 정보가 섞여서 뭉개지는 현상을 방지합니다.
• 그리고 정보를 통합할 때, 순열에 불변한 Aggregation 함수 (e.g. sum)를 사용하여 업데이트하는 것이 아닌, 여러 통로로부터 흘러들어오는 정보 스트림 간의 믹싱과정을 거칩니다. 이때 업데이트 식은 잔차 경로와 메시지 전달 경로로 나뉩니다.
  • 본 논문의 수식 7과 같이 정의되어지는데, 여기에서 수학적으로 정의된 매니폴드 공간 내에 존재할 수 있도록 제약을 걸어주는 Stream mixing matrix (doubly stochastic, H^res) 연결 행렬이 핵심입니다.
• 마찬가지로 mHC의 학습 불안정성을 잡아주기 위한 핵심 수단으로위의 딥시크의 논문에서 하이퍼 커넥션의 불안정성을 해결한 방식과 동일한 논리를 활용합니다. 위에서 H^res 연결 행렬을 버코프 폴리토프 공간으로 사영시킨 후, 싱크혼 알고리즘을 통해 행렬의 행과 열의 합을 1로 강제함으로써, 신호의 에너지를 안정적으로 보존합니다. 그로부터 그래프 신경망 레이어를 매우 깊게 쌓아도 신호가 폭발하거나 사라지지 않고 안정적으로 전파됨을 아래의 실험을 통해 입증합니다.

초심층 GNN 학습 성공 (128층 레이어)

• 가장 놀라운 결과는 모델의 깊이 실험입니다. 표준 GNN의 경우 최대 16개 이상의 층을 쌓으면 성능이 급격히 하락하여 거의 무작위 수준으로 찍어버리는 나쁜 예측력을 보입니다. 하지만 mHC-GNN은 128층까지 쌓아도 벤치마크 데이터셋에서 안정적인 정확도를 유지했습니다. 어떠한 GNN 베이스라인에서도 동일하게 적용 가능하며, 특정 실험군에서는 표준 GNN 대비 최소 35%p 이상의 성능 향상을 기록했습니다.
• 또한 단일 경로가 아닌 n개의 다중 스트림을 통해 정보가 흐르기 때문에, 노드 간의 특징이 하나로 뭉쳐 구분이 안 되는 현상을 획기적으로 늦추는 현상을 통하여 이론적으로 mHC-GNN의 smoothing 속도가 일반 GNN보다 지수적으로 느리다는 것이 증명되었습니다.
• 전통적인 GNN은 그래프 구조를 구분하는 능력(1-WL Test)에 한계가 있었습니다. mHC-GNN은 다중 스트림과 매니폴드 제약 믹싱을 통해 1-WL 테스트로는 구분할 수 없는 복잡한 그래프 구조도 식별할 수 있음을 입증하며 표현력의 한계를 극복해 냈습니다.
• Ablation Study에서도, 싱크혼 알고리즘을 통한 매니폴드 제약을 제거했을 때 성능이 최대 82%까지 하락했습니다. 이는 단순히 통로를 넓히는것보다, 그 통로를 수학적으로 제약 걸어주는 것이 성능과 안정성의 핵심임을 보여줍니다.
• 마지막 섹션에서는 mHC-GNN이 가진 현재의 한계점과 이 연구가 지향하는 바를 정의하고 있습니다.
  • mHC-GNN은 그 자체로 최첨단 성능을 갱신하기 위해 설계된 특정 모델이라기보다, 기존의 모든 GNNs 아키텍처에 적용할 수 있는 일반적인 메커니즘임을 밝힙니다. 복잡한 그래프 트랜스포머 모델과 경쟁하는 것이 아니라, 이러한 모델들에 mHC 기술을 결합하여 성능을 더욱 향상시키는 보완적인 도구로 이해해야 함을 언급합니다.
  • 이종 그래프 벤치마크에서 H2GCN과 같은 특정 도메인 특화 모델들보다 절대적인 정확도가 낮을 수 있습니다. 이는 mHC-GNN이 범용적인 구조적 개선 아이디어에 집중했기 때문이며, 향후 특화된 Aggregation 방식이나 GPRGNN 같은 기법과 결합한다면 더 높은 성능을 낼 수 있는 잠재력이 있습니다.
  • 현재 연구에서는 모든 레이어에서 동일한 병렬 스트림 개수 n을 고정하여 사용합니다. 하지만 각 레이어마다 필요한 정보의 용량이 다를 수 있으므로, 레이어별로 n을 동적으로 선택하는 기능을 도입한다면 연산 효율성과 성능 사이의 균형을 더 잘 맞출 수 있을 것이라는 한계를 인정하고 있습니다.
• 가장 큰 성과는 LLM에서 사용되던 mHC 기법을 그래프 분야로 성공적으로 적용했다는 점입니다. 특히 이론적으로 증명된 매우 깊은 레이어 까지의 수렴 속도를 바탕으로, 기존 GNN으로는 불가능했던 128층 이상의 깊은 네트워크 학습이 가능하다는 점을 실증적으로 보여주었습니다.

• mHC-GNN 논문은 기존의 대표적인 DeepGNN 모델들(GCNII, DeeperGCN, JKNet 등) 연구들과 비교하여 이들이 가졌던 고질적인 한계를 수학적·구조적으로 해결했다는 점에서 매우 큰 의미를 갖습니다.
• 기존의 DeepGNN 연구들이 주로 초기 입력을 어떻게 잘 보존할 것인가 또는 정규화방식에 집중했다면, mHC-GNN은 정보 전달 통로의 구조적 확장과 학습 안정성을 위한 제약방법에 집중합니다.
  • 레이어를 깊게 쌓기 위해 잔차 연결 기법을 쓰지만, 연결을 복잡하게 만들려 하면 학습이 터져버립니다. 따라서 32~64층 이상에서 성능 하락이 시작되는 경우가 많았습니다. 반면 mHC-GNN은 128층에서도 성능 저하 없이 74% 이상의 높은 정확도를 유지했습니다.
  • 노드들이 비슷해지는 smoothing 속도가 일반 GNN은 레이어 개수에 비례해 빨라지지만, mHC-GNN은 스트림 수에 반비례하는 속도로 진행됩니다. 즉, 스트림을 늘릴수록 smoothing 시점을 지수적으로 늦출 수 있다는 것을 수학적으로 증명했습니다. 이는 기존 DeepGNN 연구들이 경험적으로만 접근했던 문제를 엄밀한 이론으로 정립한 것입니다.
• LLM의 mHC 기술이 GNN 분야에서도 성능과 안정성, 그리고 이론적 증명의 가능성을 모두 잡은 훌륭한 기여로 평가받을 수 있을 것으로 생각됩니다.

[Contact Info]

Gmail: jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn