최근 Graph Transformer(GT)는 그래프 학습 알고리즘의 새로운 패러다임으로 부상하여, 이전에 널리 사용되던 메시지 전달 신경망(Message Passing Neural Network, MPNN)을 여러 벤치마크에서 뛰어넘는 성능을 보였다. 기존 연구(Kim 등, 2022)는 적절한 위치 임베딩(position embedding)을 도입할 경우 GT가 MPNN을 임의로 정밀하게 근사할 수 있음을 보여주었으며, 이는 GT가 MPNN만큼 최소한 강력하다는 것을 시사한다. 본 논문에서는 이러한 관계의 역방향을 탐구하며, 이론적으로 이해가 부족한 측면이 많은 일반적인 휴리스틱 기법인 가상 노드(Virtual Node, VN)를 갖춘 MPNN이 GT의 자기 주의(self-attention) 레이어를 임의로 근사할 수 있음을 보인다.구체적으로, 본 연구에서는 먼저 선형 트랜스포머의 한 유형인 Performer/선형 트랜스포머(Choromanski 등, 2020; Katharopoulos 등, 2020)에 대해 분석한 결과, 깊이 O(1), 폭 O(1)만을 갖는 MPNN + VN이 Performer/선형 트랜스포머의 자기 주의 레이어를 근사할 수 있음을 보였다. 다음으로, MPNN + VN과 DeepSets 간의 연결 고리를 활용하여, 폭이 O(n^d), 깊이가 O(1)인 MPNN + VN이 입력 특징 차원 d에 대해 자기 주의 레이어를 임의로 정밀하게 근사할 수 있음을 증명하였다. 마지막으로, 몇 가지 가정 하에서, 폭이 O(1), 깊이가 O(n)인 MPNN + VN이 GT의 자기 주의 레이어를 임의로 정밀하게 근사할 수 있는 명시적 구성법을 제시한다.실증적으로는, 본 연구는 다음과 같은 결과를 제시한다. 1) MPNN + VN은 놀라울 정도로 강력한 기준 모델(baseline)임을 보여주며, 최근 제안된 장거리 그래프 벤치마크(Long Range Graph Benchmark, LRGB) 데이터셋에서 GT를 초월하는 성능을 기록한다. 2) 다양한 OGB 데이터셋에서 초기 구현보다 개선된 성능을 보이며, MPNN + VN의 우수성을 입증한다. 3) 기후 모델링 작업에서 Linear Transformer 및 일반 MPNN보다 뛰어난 성능을 나타낸다.