공간 메시지 패싱 그래프 신경망 (MPGNNs)은 그래프 구조화 데이터에서 학습을 위해 널리 사용되고 있습니다. 그러나 l-단계 MPGNNs의 주요 제한점은 노드의 l-홉 이웃으로 제한되는 "수용 영역"과 원격 노드 간 정보 교환이 오버스쿼싱(over-squashing)에 의해 제한된다는 것입니다. 이러한 제한점을 해결하기 위해, 우리는 공간적 및 스펙트럼적 매개변수화 그래프 필터를 시너지적으로 결합하는 새로운 모델링 패러다임인 공간-스펙트럼 그래프 신경망 (S$^2$GNNs)을 제안합니다. 주파수 영역에서 부분적으로 필터를 매개변수화함으로써 전역적이면서도 효율적인 정보 전달이 가능해집니다. 우리는 S$^2$GNNs가 오버스쿼싱을 극복하고 MPGNNs보다 엄밀히 더 좁은 근사 이론적 오차 경계를 제공함을 보여줍니다. 또한, 그래프 합성곱을 근본적으로 재고하면 새로운 설계 공간이 열립니다. 예를 들어, S$^2$GNNs는 1-Weisfeiler-Lehman (WL) 테스트보다 엄밀히 더 표현력이 높은 자유롭게 위치 인코딩을 허용합니다. 더욱이, 일반적인 S$^2$GNNs를 얻기 위해, 우리는 유향 그래프에 대한 스펙트럼적 매개변수화 필터를 제안합니다. S$^2$GNNs는 공간 MPGNNs, 그래프 트랜스포머, 그리고 그래프 리와이링보다 우수한 성능을 보이며, 예를 들어 펩타이드 장거리 벤치마크 작업에서 최신 시퀀스 모델링과 경쟁력을 갖추고 있습니다. 40 GB GPU에서는 S$^2$GNNs가 수백만 개의 노드까지 확장됩니다.