초록
그래프 트랜스포머(GT)는 메시지 전달 그래프 신경망(GNN)보다 이론적으로 더 높은 표현력을 갖춘 유망한 아키텍처로 부상하고 있다. 그러나 전형적인 GT 모델은 최소한 2차 복잡도를 가지므로 대규모 그래프에 대한 확장성에 한계가 있다. 최근 몇 가지 선형 GT 모델이 제안되었지만, 여전히 여러 인기 있는 그래프 데이터셋에서 GNN의 성능에 미치지 못하며, 이는 실용적인 표현력에 대한 심각한 우려를 제기한다. GT의 표현력과 확장성 사이의 균형을 맞추기 위해, 선형 복잡도를 가지면서도 다항식 표현력을 갖춘 Polynormer라는 새로운 GT 모델을 제안한다. Polynormer는 입력 특징에 대해 고차 다항식을 학습하는 새로운 기본 모델을 기반으로 한다. 이 기본 모델이 순열 에퀴바리언트(permuation equivariant)가 되도록 하기 위해, 그래프의 구조 정보와 노드 특징을 별도로 통합함으로써 국소적 및 전역적 에퀴바리언트 어텐션 모델을 도입한다. 결과적으로 Polynormer는 선형적인 로컬-투-글로벌 어텐션 구조를 채택하여, 어텐션 점수에 의해 조절되는 계수를 갖는 고차 에퀴바리언트 다항식을 학습한다. Polynormer는 노드 수가 수백만에 달하는 대규모 그래프를 포함한 총 13개의 동질성 및 이질성 그래프 데이터셋에서 평가되었으며, 광범위한 실험 결과는 비선형 활성화 함수를 사용하지 않아도, 대부분의 데이터셋에서 최신 GNN 및 GT 기준 모델들을 상회함을 보여준다.