그래프 신경망의 표현력을 서브그래프 동형성 카운팅을 통해 향상시키기

그래프 신경망(GNN)은 다양한 응용 분야에서 놀라운 성과를 거두었지만, 최근 연구들은 그들이 기반 그래프의 구조를 포착하는 데 있어 중요한 한계를 드러냈다. 기존 GNN의 표현 능력이 Weisfeiler-Leman(WL) 그래프 동형성 테스트에 의해 제한된다는 것이 입증되었으며, 이로 인해 그래프 부분 구조를 탐지하거나 세는 능력의 부재와 같은 입증된 제약을 물려받고 있다. 한편, 네트워크 과학 및 생물정보학 등에서 많은 실증적 증거가 부분 구조가 종종 하류 작업과 밀접한 관련이 있음을 보여주고 있다. 이러한 문제를 해결하기 위해 우리는 ‘그래프 부분 구조 네트워크’(Graph Substructure Networks, GSN)를 제안한다. 이는 부분 구조 인코딩을 기반으로 한 위상학적으로 인지 가능한 메시지 전달 방식을 채택한 아키텍처이다. 본 연구에서는 제안된 구조의 표현 능력을 이론적으로 분석하여, WL 테스트보다 엄격히 더 강력한 표현 능력을 지닌다는 것을 보이며, 보편성(universality)을 보장하는 충분조건을 제시한다. 특히, 우리는 WL 계층 구조에 얽매이려 하지 않으며, 이로 인해 기존 GNN들이 지닌 국소성(locality)과 선형 복잡도(linear network complexity)와 같은 매력적인 특성을 유지하면서도, 그래프 동형성의 어려운 사례들까지도 명확히 구분할 수 있다. 다양한 실제 환경(예: 분자 그래프 및 소셜 네트워크)에서 그래프 분류 및 회귀 과제에 대해 광범위한 실험 평가를 수행하였으며, 상태의 최고 성능(state-of-the-art)을 달성하였다. 코드는 공개되어 있으며, https://github.com/gbouritsas/graph-substructure-networks 에서 확인할 수 있다.