그래프 신경망을 이용한 효율적인 위치 인코딩 학습

위치 인코딩(PEs)은 그래프 표현 학습에서 효과적으로 작동하기 위해 필수적이다. 왜냐하면 트랜스포머 아키텍처는 본질적으로 위치에 무관한 구조를 가지므로, PEs는 위치 인식 능력을 제공하며 그래프 신경망(GNNs)의 표현 능력을 향상시키기 때문이다. 그러나 그래프의 표준 노드 순서가 없고 그래프의 규모가 크기 때문에, 강력하고 효율적인 PEs를 설계하는 것은 큰 도전 과제이다. 본 연구에서는 그래프용 PEs가 충족해야 할 네 가지 핵심 특성—안정성, 표현력, 확장성, 일반성—을 규명하였다. 기존의 고유벡터 기반 PE 방법들은 이 네 가지 기준을 동시에 만족하는 데 어려움을 겪는다는 것을 발견하였다. 이러한 격차를 해소하기 위해, 우리는 그래프용 학습 가능한 PEs를 위한 새로운 프레임워크인 PEARL을 제안한다. 본 연구의 주요 통찰은 메시지 전달 기반 GNN이 고유벡터의 비선형 변환으로 작용한다는 점이며, 이를 바탕으로 강력하고 효율적인 PEs를 생성할 수 있는 GNN 아키텍처를 설계할 수 있다. 중요한 과제는 표현력이 뛰어나면서도 순열 불변성(permuation equivariance)을 유지할 수 있도록 노드 특징을 초기화하는 것이다. 이를 해결하기 위해 우리는 GNN을 무작위 노드 입력 또는 표준 기저 벡터로 초기화함으로써 메시지 전달 연산의 표현력을 극대화하고, 통계적 풀링 함수를 활용하여 순열 불변성을 유지한다. 분석 결과, PEARL은 고유벡터에 대한 불변 함수를 선형 복잡도로 근사함을 입증하였으며, 안정성과 높은 표현력을 엄밀히 보장한다. 실험 평가를 통해 PEARL은 고유벡터 기반 PE의 경량화된 버전보다 우수한 성능을 보였으며, 전체 고유벡터 기반 PE와 비슷한 성능을 달성하지만, 복잡도는 1~2개의 지수 차수만큼 낮다.