초록
그래프 신경망 (GNNs)은 그래프의 표현 학습을 위한 효과적인 프레임워크입니다. GNNs는 이웃 집합 방식을 따르며, 노드의 표현 벡터는 그 노드와 인접한 노드들의 표현 벡터를 재귀적으로 집합하고 변환하여 계산됩니다. 많은 GNN 변형 모델들이 제안되어 노드 및 그래프 분류 작업에서 최고 수준의 결과를 달성하였습니다. 그러나, GNNs가 그래프 표현 학습을 혁신함에도 불구하고, 그들의 표현 특성과 한계에 대한 이해는 아직 제한적입니다. 본 연구에서는 다양한 그래프 구조를 포착하는 GNNs의 표현 능력을 분석하기 위한 이론적 프레임워크를 제시합니다. 우리의 결과는 Graph Convolutional Networks와 GraphSAGE와 같은 인기 있는 GNN 변형 모델들의 판별력 특성을 설명하며, 이러한 모델들이 특정 간단한 그래프 구조를 구분할 수 없다는 점을 보여줍니다. 그런 다음, 이론적으로 가장 표현력이 뛰어난 GNN 클래스 중 하나인 아키텍처를 개발하였으며, 이 아키텍처는 Weisfeiler-Lehman 그래프 동형 테스트만큼 강력하다는 것을 증명하였습니다. 우리는 여러 그래프 분류 벤치마크에서 우리의 이론적 발견을 경험적으로 검증하였으며, 모델이 최고 수준의 성능을 달성함을 입증하였습니다.