별에서 부분 그래프로: 국소 구조 인식으로 어떤 GNN도 향상시키기

메시지 전달 신경망(Message Passing Neural Networks, MPNN)은 그래프 신경망(Graph Neural Network, GNN)의 대표적인 형태로, 각 노드의 표현은 인접 노드들로부터 전달되는 표현(메시지)을 집계함으로써 재귀적으로 계산되며, 이는 별자리 형태의 패턴과 유사하다. MPNN는 효율성과 확장성 측면에서 매력적인 특성을 지니고 있으나, 그 표현력은 1차 위스페일러-레만 동형성 검사(1-WL)에 의해 상한선으로 제한된다. 이를 해결하기 위해 이전 연구들은 확장성과 때로는 일반화 성능을 희생하면서까지 높은 표현력을 갖춘 모델을 제안해왔다. 본 연구는 이러한 두 가지 접근 사이의 균형을 추구한다. 우리는 기존의 MPNN을 더 높은 표현력으로 향상시키는 일반적인 프레임워크를 제안하며, 확장성에 대한 부담은 최소화하면서도 실용적인 성능은 크게 향상시킨다. 이를 위해 MPNN의 국소적 집계 방식을 별자리 형태에서 일반적인 부분그래프 형태(k-에고넷 등)로 확장한다. 본 프레임워크에서는 각 노드의 표현이 단순히 인접 노드들만을 고려한 표현이 아니라, 해당 노드 주변의 유도 부분그래프(Induced Subgraph)의 인코딩을 통해 계산된다. 부분그래프 인코더로는 확장성 측면을 고려하여 주로 MPNN을 사용함으로써, 어떤 GNN 모델에도 적용 가능한 일반적인 래퍼(wrapper) 형태의 프레임워크를 설계하였다. 본 연구에서 제안하는 방법을 GNN-AK(GNN As Kernel)이라 명명한다. 이는 컨볼루션 신경망에서 커널을 GNN으로 대체함으로써, 컨볼루션 구조와 유사한 형태를 띠기 때문이다. 이론적으로, 본 프레임워크가 1-WL 및 2-WL보다 엄밀히 강력하며, 3-WL과 비할 바 없이 강력함을 입증하였다. 또한 성능을 유지하면서 메모리 사용량을 크게 줄이고 처리 속도를 향상시키는 부분그래프 샘플링 전략을 설계하였다. 제안한 방법은 여러 유명한 그래프 기반 머신러닝 과제에서 기존 최고 성능을 크게 상회하는 결과를 기록하였으며, 특히 ZINC 데이터셋에서 0.08의 MAE, CIFAR10에서 74.79%, PATTERN에서 86.887%의 정확도를 달성하였다.