반복 그래프 신경망에서 정지 vs 수렴에 관한 연구

반복 그래프 신경망 (Recurrent Graph Neural Networks, RGNNs) 은 메시지 전달을 특정 종료 조건이 충족될 때까지 반복함으로써 표준 GNN 을 확장합니다. 문헌에는 다양한 RGNN 모델이 제안되었습니다. 본 논문에서는 세 가지 모델을 연구합니다: 모든 정점 표현이 안정화되어야 하는 수렴형 RGNN(converging RGNNs), 오직 출력 분류만 안정화되어야 하는 출력-수렴형 RGNN(output-converging RGNNs), 그리고 정점당 정지 분류기가 언제 멈추는지 결정하는 정지형 RGNN(halting RGNNs)입니다. 우리는 이 모델들 간의 표현력 관계를 규명합니다: 비방향 그래프에서 수렴형 RGNN 은 등급-이진관계 불변 정지형 RGNN(graded-bisimulation-invariant halting RGNNs) 과 동등한 표현력을 가지며, 출력-수렴형 RGNN 은 적어도 그와 같은 표현력을 가집니다. 정지형 RGNN 에 대한 기존 결과와 결합하면, 단항 2 차 논리 (monadic second-order logic, MSO) 로 표현 가능한 분류기에 비해 수렴형 RGNN 은 등급 모달 $μ$-계산법 ($μ$GML) 을 정확히 표현하고, 출력-수렴형 RGNN 은 적어도 $μ$GML 을 표현함을 보여줍니다. 이러한 결과는 ReLU 네트워크와 합 집계(sum aggregation) 로 제한하더라도 성립합니다. 주요 기술적 과제는 전역 정지 분류기가 없는 상황에서 정점들이 서로 다른 시점에 지역적으로 정지 결정을 내리면서 동기화 손실 (desynchronisation) 을 초래할 수 있으므로, 이를 해결하기 위해 정점들이 이러한 비동기성을 극복하고 조정할 수 있도록 하는 '신호등' (traffic-light) 프로토콜을 개발하는 것입니다. 우리의 결과는 Bollen et al. (2025) 의 미해결 문제를 해결하며, Pflueger et al. (2024) 의 RGNN 모델이 수렴이 보장되더라도 완전한 $μ$GML 표현력을 유지함을 보여줍니다.