비음수 저항 곡률(Non Negative Resistance Curvature)을 이용한 라마누잔 그래프 리와이어링 (Ramanujan

그래프 신경망 (Graph Neural Networks, GNNs)은 에지 (edges)를 통해 정보를 반복적으로 전파하고 집계함으로써 그래프 구조 데이터 상에서 학습하기 위한 강력한 패러다임으로 등장했습니다. 그러나 전통적인 메시지 패싱 (message passing) 방식은 종종 오버스쿼싱 (over-squashing) 문제로 인해 어려움을 겪는데, 이는 기하급수적으로 큰 이웃 정보들이 고정된 차원의 임베딩 (embeddings)으로 압축되면서 효과적인 장거리 의존성 (long-range dependency) 학습을 방해하는 현상을 말합니다. 본 연구에서는 GNN의 위상학적 병목 현상 (topological bottlenecks)을 완화하기 위해 라마누잔 그래프 (Ramanujan graphs)를 활용하는 그래프 리와이어링 (graph rewiring) 전략인 라마누잔 전파 (Ramanujan Propagation)를 소개합니다. 우리는 먼저 적절하게 선택된 라마누잔 그래프가 비음수 저항 곡률 (non-negative resistance curvature)을 보장하며, 이것이 오버스쿼싱을 완화하고 효율적인 정보 흐름을 촉진한다는 점을 입증합니다. 이어서 우리는 원본 그래프의 국소적 연결성 (local connectivity)을 보존하면서 라마누잔 방식으로 리와이어링된 그래프를 구축하기 위한 알고리즘 프레임워크를 제안합니다. 실험을 통해 우리의 방법론이 9가지의 최첨단 (state-of-the-art) 리와이어링 기술보다 우수한 성능을 보임을 입증했습니다. 이러한 결과는 라마누잔 그래프가 GNN에서 확장 가능하고 위상 인지적인 (topology-aware) 메시지 패싱을 위한 엄격한 구조적 사전 정보 (structural prior)임을 확립합니다.