그래프 신경망(GNN)의 성능을 높이는 데 쓰이는 위치 인코딩(Positional Encoding, PE)이 완전한 형태에서는 이론적으로 동등한 표현력을 지니지만, 실제로 널리 쓰이는 절단형(truncated) 변형은 계열에 따라 표현력이 근본적으로 달라진다는 연구 결과가 arxiv에 공개됐다. 스펙트럼 기반 PE와 보행 기반 PE는 완전한 형태에서 동등한 것으로 알려져 있었으나, 이 연구는 절단 후에는 해당 동등성이 더 이상 성립하지 않음을 이론적으로 증명했다.
위치 인코딩은 GNN의 표현력을 높이기 위해 그래프 구조 정보를 추가로 주입하는 방식이다. 라플라시안 고유공간(Laplacian eigenspaces)이나 유효 저항(effective resistance) 같은 스펙트럼 계열과, 인접 행렬의 다항식으로 구성되는 보행 기반 계열이 대표적이다. 완전한 형태의 두 계열은 1-WL 검정과 3-WL 검정 사이의 표현력을 갖고 이론적으로 동등하다고 알려져 있었다. 그러나 완전한 PE를 사용하려면 O(n³)의 시간·공간 복잡도가 필요하기 때문에, 실무에서는 첫 k개의 고유공간이나 인접 행렬의 k제곱까지만 사용하는 절단 변형이 일반적이다.
연구팀은 절단형 PE의 이론적 성질을 체계적으로 분석한 결과, 절단 후에는 여러 PE 계열 사이의 표현력이 근본적으로 달라진다는 사실을 밝혔다. 특히 절단된 스펙트럼 PE는 1-WL 검정을 넘지 못한다는 것을 부산물(corollary)로 보였다. 또한 k-조화 거리(k-harmonic distances)라는 스펙트럼 PE 계열을 분석해, 긴밀하게 연관된 절단형 PE 사이에서도 표현력 차이가 존재할 수 있음을 구체적으로 보였다. 실세계 데이터셋을 대상으로 한 실험에서는 단일 PE 계열만 사용하는 것보다 여러 절단형 PE를 혼합해 사용하는 방식이 더 나은 성능을 내는 것으로 확인됐다.
이 연구는 GNN 설계에서 위치 인코딩 선택이 이론적 동등성에만 근거해서는 충분하지 않다는 점을 시사한다. 실무에서는 절단 수준(k 값)과 PE 계열의 조합이 모델 성능에 직접적인 영향을 미친다는 점에서, 그래프 학습 시스템 설계 시 PE 선택에 더 세심한 주의가 필요하다는 것이 연구의 핵심 메시지다.
