곡률을 통한 그래프 상의 과도한 압축 및 병목 현상 이해

대부분의 그래프 신경망(GNN)은 입력 그래프 상에서 노드 특징을 전파하는 메시지 전달 패러다임을 사용한다. 최근 연구들은 장거리 상호작용에 의존하는 작업에서 메시지 전달의 효율성을 제한하는 요인으로, 멀리 떨어진 노드들로부터 흐르는 정보의 왜곡을 지적하였다. 이 현상은 '과도한 압축(over-squashing)'이라 불리며, $k$-호프 이웃의 수가 $k$에 따라 급격히 증가하는 그래프의 협소부( bottleneck)로 인해 휴리스틱적으로 설명되어 왔다. 본 연구에서는 GNN 내 과도한 압축 현상을 정밀하게 설명하고, 그래프의 협소부에서 이 현상이 어떻게 발생하는지 분석한다. 이를 위해 새로운 엣지 기반의 조합적 곡률(edge-based combinatorial curvature)을 제안하고, 음의 곡률을 가진 엣지가 과도한 압축 문제의 원인임을 증명한다. 또한 곡률 기반의 그래프 재구성 방법을 제안하고, 실험적으로 그 효과를 검증하였다.