본 논문은 그래프 신경망(GNNs)의 표현력에 대한 이론적 연구를, Weisfeiler-Lehman(WL) 테스트와의 정렬을 통해 이루어지는 기존 연구의 한계를 지적하며 시작합니다. 기존 연구는 주로 GNNs가 그래프 구조를 구별하는 능력에 초점을 맞추는 반면, 본 논문은 특정 함수 클래스를 계산하거나 근사하는 GNNs의 능력에 초점을 맞춥니다. 이를 위해 수정된 CONGEST 모델을 사용하여 GNNs의 표현력을 분석하는 새로운 틀을 제시합니다. 이 틀 안에서, 제한 없는 전처리 또는 외부에서 계산된 특징의 통합이 표현력을 향상시킨다는 주장이 문제를 야기할 수 있음을 보입니다. 또한 WL 테스트 한 번을 시뮬레이션하는 데 필요한 GNN의 용량(깊이 곱하기 너비)의 하한이 그래프 크기에 거의 선형적으로 증가한다는 것을 보임으로써, WL 테스트가 지역적으로 계산 가능하지 않고 메시지 전달 GNN과 일치하지 않음을 밝힙니다. 하지만 가상 노드와 에지의 효과를 계산 모델 관점에서 특징짓는 긍정적인 결과도 제시하며, 마지막으로 GNN 표현력에 대한 몇 가지 미해결 문제를 제시합니다.
