초록
그래프 신경망(GNN)이 그래프 학습 분야에서 높은 성과를 거두고 있음에도 불구하고, 기존의 GNN은 1차 Weisfeiler-Leman 그래프 동형성 테스트 알고리즘(1-WL)의 표현력 한계를 넘어서기 어렵다. 이는 GNN의 전파 방식이 1-WL과 일관성을 유지하기 때문이다. 본 연구에서는 원본 그래프를 부분 그래프를 통해 더 쉽게 구분할 수 있다는 점에 착안하여, 이러한 문제를 해결하기 위한 새로운 신경망 프레임워크인 '서브구조 인지 그래프 신경망(SAGNN)'을 제안한다. 먼저, 원본 그래프에서 간선을 지속적이고 선택적으로 제거함으로써 얻을 수 있는 '컷 부분 그래프(Cut subgraph)'를 제안한다. 이후, 랜덤 워크 인코딩 방식을 확장하여 부분 그래프 내에서 루트 노드의 복귀 확률을 활용하여 구조적 정보를 포착하고, 이를 노드 특성으로 사용함으로써 GNN의 표현력을 향상시킨다. 이론적으로 본 프레임워크가 1-WL보다 더 강력하며, 구조 인지 능력에서 우수함을 입증하였다. 광범위한 실험을 통해 본 프레임워크의 효과성을 입증하였으며, 다양한 검증된 그래프 작업에서 최첨단 성능을 달성하였고, 3-WL에서 실패하는 그래프에서도 본 프레임워크를 탑재한 GNN이 완벽한 성능을 발휘하였다. 구체적으로, 기준 모델 대비 최대 83%의 성능 향상을 달성하였으며, 이전 최고 성능 방법 대비 32%의 성능 향상을 기록하였다.