그래프 신경망의 설계 공간 확장을 위한 전통적인 Weisfeiler-Lehman 재고찰

메시지 패싱 신경망 (MPNNs)는 최근 몇 년 동안 그래프 신경망 (GNNs)의 가장 인기 있는 프레임워크로 부상하였습니다. 그러나, 이들의 표현력은 1차원 Weisfeiler-Lehman (1-WL) 테스트에 의해 제한됩니다. 일부 연구는 $k$-WL/FWL (Folklore WL)에서 영감을 받아 해당하는 신경망 버전을 설계하였습니다. 높은 표현력에도 불구하고, 이러한 연구 방향에는 심각한 한계가 있습니다. 특히, (1) $k$-WL/FWL은 최소 $O(n^k)$ 공간 복잡도를 요구하며, 이는 $k=3$일 때조차 큰 그래프에 대해 실용적이지 않습니다; (2) $k$-WL/FWL의 설계 공간은 유연성이 부족하여 조정 가능한 하이퍼파라미터가 $k$뿐입니다.첫 번째 한계를 해결하기 위해, $(k,t)$-FWL 확장을 제안합니다. 우리는 이론적으로 $(k,t)$-FWL에서 공간 복잡도를 $O(n^k)$ (어떠한 $k\geq 2$에 대해서도)로 고정하더라도 그래프 동형 문제를 해결할 수 있는 표현력 계층 구조를 구성할 수 있음을 증명하였습니다. 두 번째 문제를 해결하기 위해, 모든 노드 대신 임의의 등변 집합을 이웃으로 간주하는 $(k,t)$-FWL+를 제안합니다. 이를 통해 $k$-FWL의 설계 공간이 크게 확장되었습니다. 이러한 두 가지 수정을 결합하면 유연하고 강력한 프레임워크인 $(k,t)$-FWL+가 생성됩니다.우리는 $(k,t)$-FWL+가 기존 모델 대부분을 동등한 표현력으로 구현할 수 있음을 보여줍니다. 그런 다음, 실제로와 이론적으로 타당한 $(k,t)$-FWL+의 인스턴스인 Neighborhood$^2$-FWL (N$^2$-FWL)을 소개합니다. 우리는 N$^2$-FWL이 3-WL보다 약하지 않으며, 많은 부분 구조를 인코딩하면서도 단지 $O(n^2)$ 공간만 필요함을 증명하였습니다. 마지막으로, N$^2$-GNN이라는 이름의 N$^2$-FWL의 신경망 버전을 설계하고 다양한 작업에서 성능을 평가하였습니다.N$^2$-GNN은 ZINC-Subset 데이터셋에서 기록적인 결과 (0.059)를 달성하여 이전 최고 성과(SOTA)보다 10.6% 개선되었습니다. 또한, N$^2$-GNN은 모든 기존 고표현력 GNN 방법 중 BREC 데이터셋에서 새로운 최고 성과(SOTA) 결과 (71.8%)를 달성하였습니다.