ViT/MLP-Mixer의 그래프에 대한 일반화

그래프 신경망(GNNs)은 그래프 표현 학습 분야에서 큰 잠재력을 보여왔다. 기존의 GNN은 여러 층을 겹쳐서 전역 그래프 영역에 정보를 전파하는 국소적 메시지 전달 메커니즘을 정의한다. 그러나 이 패러다임은 과도한 압축(over-squashing)과 장거리 의존성의 부족이라는 두 가지 주요한 한계를 가지고 있으며, 이를 극복하기 위해 글로벌 어텐션을 사용할 수는 있지만 계산 비용이 제곱 복잡도로 급격히 증가하게 된다. 본 연구에서는 컴퓨터 비전 분야에서 제안된 ViT/MLP-Mixer 아키텍처를 활용하여 이러한 구조적 한계를 극복하는 대안적 접근법을 제안한다. 우리는 새로운 종류의 GNN, 즉 Graph ViT/MLP-Mixer를 도입하며, 이는 세 가지 핵심 특성을 갖는다. 첫째, Long Range Graph Benchmark 및 TreeNeighbourMatch 데이터셋에서의 실험을 통해 장거리 의존성을 효과적으로 포착하고 과도한 압축 문제를 완화함을 입증하였다. 둘째, 노드 및 엣지 수에 대해 선형 복잡도를 가지며, 관련된 그래프 트랜스포머 및 표현력 있는 GNN 모델들을 능가하는 뛰어난 속도 및 메모리 효율성을 제공한다. 셋째, 그래프 동형성 측면에서 높은 표현력을 보이며, 최소한 3-WL 비동형 그래프를 구별할 수 있다. 제안한 아키텍처는 4개의 시뮬레이션 데이터셋과 7개의 실제 세계 벤치마크에서 검증되었으며, 모든 경우에서 매우 경쟁력 있는 성능을 보였다. 소스 코드는 재현성을 위해 다음 링크에서 제공된다: \url{https://github.com/XiaoxinHe/Graph-ViT-MLPMixer}.