경로 신경망: 표현력과 정확성이 뛰어난 그래프 신경망

그래프 신경망(GNNs)은 최근 그래프 구조 데이터를 활용한 학습에서 표준적인 접근 방식으로 자리 잡았다. 기존 연구들은 이러한 모델의 잠재력과 한계를 밝혀냈다. 그러나 최근 연구를 통해 표준 GNNs의 표현 능력이 제한됨이 입증되었다. 이러한 모델들은 비동형 그래프를 구분하는 데 있어 1차원 위스페일러-레만(1-WL) 알고리즘과 동등한 수준에 그친다. 본 논문에서는 노드로부터 시작하는 경로들을 집계함으로써 노드 표현을 업데이트하는 Path Neural Networks(PathNNs)를 제안한다. 우리는 단일 최단 경로, 모든 최단 경로, 길이가 K 이하인 모든 단순 경로를 집계하는 세 가지 서로 다른 PathNN 모델 변형을 도출한다. 이 중 두 가지 변형이 1-WL 알고리즘보다 엄격히 더 강력함을 증명하였으며, 이론적 결과를 실험적으로 검증하였다. 실험 결과, PathNNs는 1-WL 알고리즘이 구분하지 못하는 비동형 그래프 쌍을 구분할 수 있음을 확인하였고, 특히 가장 표현력이 뛰어난 PathNN 변형은 3-WL 알고리즘으로도 구분이 불가능한 그래프들까지 구분할 수 있었다. 다양한 PathNN 변형은 그래프 분류 및 그래프 회귀 데이터셋에서도 평가되었으며, 대부분의 경우 기존 기준 모델보다 우수한 성능을 보였다.