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

요약

본 논문은 반복 그래프 신경망(RGNNs)의 세 가지 유형(수렴형, 출력-수렴형, 정지형)을 비교하고 이들 간의 표현력 관계를 분석합니다. 연구 결과, 비방향 그래프에서 수렴형 RGNN은 등급-이진관계 불변 정지형 RGNN과 동등한 표현력을 가지며, 이는 단항 2차 논리(MSO)로 표현 가능한 분류기보다 강력함을 보여줍니다. 또한, 전역 정지 분류기의 부재로 인한 비동기성 문제를 해결하기 위해 '신호등' 프로토콜을 제안하며, RGNN의 이론적 한계를 확장하고 기존 미해결 문제에 대한 해답을 제시합니다.

핵심 포인트

• RGNN은 메시지 전달을 특정 종료 조건까지 반복하여 표준 GNN을 확장하는 모델이다.
• 수렴형 RGNN과 정지형 RGNN 간에는 표현력의 동등성 관계가 존재하며, 이는 등급-이진관계 불변성을 통해 증명된다.
• 제안된 '신호등' 프로토콜은 전역 정지 분류기가 없을 때 발생하는 비동기화 문제를 해결하여 RGNN의 안정성과 성능을 향상시킨다.
• RGNN의 표현력은 단항 2차 논리(MSO)로 표현 가능한 분류기를 능가하며, 등급 모달 $\mu$-계산법($\mu$GML)까지 포괄할 수 있음을 이론적으로 입증했다.