초록
본 논문은 그래프 신경망(GNNs)의 일반화 성능을 향상시키기 위해, 도트 곱 주의 메커니즘(Vaswani 등, 2017)의 계산 및 메모리 효율적인 변형인 낮은 랭크 전역 주의(LRGA) 모듈을 통합하는 것을 제안한다. LRGA 모듈을 GNN에 도입함으로써 부여되는 일반화 성질을 이론적으로 정량화하기 위해, 특정한 표현력 있는 GNN 가족에 초점을 맞추어, LRGA 모듈을 추가함으로써 강력한 그래프 동형성 검사인 2-플로어 위스페일러-레만(2-FWL) 알고리즘과의 알고리즘 일치(algorithmic alignment)를 달성할 수 있음을 보여준다. 구체적으로 다음과 같은 내용을 제시한다: (i) 최근 제안된 무작위 그래프 신경망(RGNN) (Sato 등, 2020) 프레임워크를 고려하고, 이 모델이 확률적 의미에서 보편적(universal)임을 증명한다; (ii) LRGA를 갖춘 RGNN이 다항 커널을 통해 2-FWL 업데이트 단계와 일치함을 보이며; (iii) 무작위로 초기화된 두 층의 MLP를 사용하여 커널의 특징 맵(feature map)을 학습할 때의 샘플 복잡도(sample complexity)를 경계한다. 실용적인 관점에서 보면, 기존 GNN 레이어에 LRGA를 추가하는 것은 현재의 GNN 벤치마크에서 최첨단 성능을 달성한다. 마지막으로, 다양한 GNN 아키텍처에 LRGA를 도입함으로써 서로 다른 모델 간의 성능 차이를 종종 좁히는 현상을 관찰하였다.