그래프 동형 테스트와 GNN을 이용한 함수 근사의 등가성에 대해

그래프 신경망(GNNs)은 그래프 구조 데이터에서 많은 성공을 거두었습니다. 이에 따라 그들의 표현력에 대한 연구 관심이 점차 증가하고 있습니다. 한편에서는 GNNs의 그래프 상의 순열 불변 함수를 근사하는 능력을 연구하고 있으며, 다른 한편에서는 그래프 동형 검사로서의 GNNs의 표현력을 집중적으로 분석하고 있습니다. 우리의 연구는 이 두 관점을 연결하여 그들의 동등성을 증명합니다. 또한, 우리는 시그마 대수(sigma-algebra) 언어를 사용하여 이 두 관점을 모두 통합한 GNNs의 표현력 프레임워크를 개발하였습니다. 이를 통해 다양한 유형의 GNNs와 다른 그래프 동형 검사 방법들의 표현력을 비교하였습니다. 특히, 우리는 2차 불변 그래프 네트워크(second-order Invariant Graph Network)가 같은 차수를 가진 비동형인 정규 그래프를 구분하지 못함을 증명하였습니다. 그런 다음, 이를 확장하여 새로운 아키텍처인 Ring-GNN을 제안하였으며, 이 모델은 이러한 그래프들을 성공적으로 구분하며 실제 데이터셋에서 우수한 성능을 보여주었습니다.