웨이스파일러 레만 계층을 벗어나기: 메시지 전달을 넘어서는 그래프 학습

우리는 그래프 학습을 위한 새로운 신경망 아키텍처인 CRaWl을 제안한다. 그래프 신경망(GNN)과 마찬가지로 CRaWl 계층은 그래프 상의 노드 특징을 업데이트하며, 이로 인해 GNN 계층과 자유롭게 조합하거나 교차 배치할 수 있다. 그러나 CRaWl은 메시지 전달 기반의 그래프 신경망과 본질적으로 다른 방식으로 작동한다. CRaWl 계층은 그래프 내에서 수행되는 무작위 보행(random walk) 경로상에 나타나는 부분그래프(subgraph)에 대해 1차원 컨볼루션(1D Convolution)을 활용하여 정보를 추출하고 집계함으로써 장거리 상호작용을 탐지하고 비국소적 특징(non-local features)을 계산한다. 본 연구의 이론적 기반으로, CRaWl의 표현 능력이 Weisfeiler-Leman 알고리즘과 비교할 수 없음을 보여주는 정리를 입증하였다. 즉, CRaWl로 표현 가능한 함수들이 존재하지만 GNN에서는 표현할 수 없는 경우가 있으며, 반대로 GNN에서 표현 가능한 함수가 CRaWl에서는 표현되지 않을 수도 있음을 의미한다. 이 결과는 Weisfeiler-Leman 계층 구조의 고차원 버전으로 확장되며, 고차원 GNN에도 해당된다. 실험적으로는, 다양한 그래프 분류 및 회귀 작업을 위한 벤치마크 데이터셋에서 CRaWl이 최신의 GNN 아키텍처들과 경쟁 가능한 성능을 보임을 입증하였다.