잘린 위치 인코딩의 이론적 함정, GNN 표현력 재설계 요구

그래프 신경망(GNN)을 설계하는 연구자라면 한 번쯤 마주치는 딜레마가 있다. 이론적으로 강력한 위치 인코딩(Positional Encoding, PE)을 사용하고 싶지만, 완전한 형태로 계산하려면 그래프 노드 수의 세제곱에 비례하는 시간과 메모리가 필요하다. 수천, 수만 개의 노드를 가진 그래프를 다루는 현장에서 이 비용은 감당하기 어렵다. 그래서 실무자들은 타협안을 선택한다. 라플라시안의 고유공간 중 처음 k개만 사용하거나, 인접 행렬의 거듭제곱을 k번째까지만 계산하는 방식이다.

문제는 이 절삭이 단순한 근사에 그치지 않는다는 것이다. James Flora와 동료 연구자들이 2026년 6월 발표한 이 논문은 바로 그 지점을 파고든다. 절삭된 PE가 완전한 버전의 이론적 성질을 유지한다는 암묵적인 가정이 실제로는 성립하지 않음을 체계적으로 보여준다.

완전성의 환상: 두 인코딩 족의 이론적 동등성

GNN의 표현력을 논할 때 흔히 등장하는 기준은 바이섹칸-레만(Weisfeiler-Leman, WL) 그래프 동형 검사다. 1-WL 검사는 기본 메시지 패싱 GNN의 표현력 상한을 나타내고, 3-WL은 훨씬 정교한 구분 능력을 뜻한다. 완전한 형태의 스펙트럼 PE와 보행 기반 PE는 둘 다 1-WL보다 강하고 3-WL보다는 약한, 동일한 표현력 구간에 놓인다는 것이 기존 이론의 핵심이었다.

스펙트럼 PE의 대표적 예는 라플라시안의 고유벡터들이다. 그래프의 전역적인 기하 구조를 포착하는 이 벡터들은 두 노드가 위상적으로 얼마나 유사한지를 인코딩한다. 보행 기반 PE는 인접 행렬의 거듭제곱, 즉 노드 쌍 사이에 길이 k인 경로가 몇 개 있는지를 세는 방식이다. 완전한 버전은 모든 고유공간을 포함하거나 충분히 높은 차수까지 거듭제곱을 계산하기 때문에 그래프 구조 전체를 담아낼 수 있다.

연구진은 이 동등성이 '완전한' 버전에만 성립하는 조건부 명제임을 강조한다. 절삭이 가해지는 순간, 두 인코딩 족은 서로 다른 궤도를 걷기 시작한다.

절삭이 부수는 것들: 스펙트럼과 보행 기반의 분기

핵심 이론적 결과는 날카롭다. 절삭된 스펙트럼 PE, 즉 처음 k개의 고유공간만 사용하는 방식은 1-WL 검사보다 표현력이 강하지 않다. 완전한 버전이 가졌던 '1-WL 초과'의 능력이 절삭과 함께 사라진다. 이는 직관에 반하는 결과다. 연구자들은 흔히 k를 크게 설정하면 충분히 좋은 근사가 될 것이라고 여기지만, 표현력의 관점에서는 k의 크기와 무관하게 한계가 생긴다.

반면 절삭된 보행 기반 PE는 다르다. 인접 행렬의 k번째 거듭제곱까지만 사용하더라도, 이 인코딩은 여전히 1-WL보다 강한 구분 능력을 유지한다. 같은 '절삭'이라는 조작을 가해도 두 계열이 보이는 반응이 근본적으로 다른 것이다.

연구진은 이 차이를 더 세밀하게 탐구하기 위해 k-조화 거리(k-harmonic distances)라는 스펙트럼 PE 변종을 분석한다. 이 인코딩은 절삭된 라플라시안 고유공간과 밀접하게 연관되지만, 표현력 면에서는 미묘하게 다른 양상을 보인다. 같은 스펙트럼 계열 안에서도 세부적인 설계 선택이 절삭 이후의 표현력에 영향을 미친다는 것을 이 사례 연구는 보여준다. 이론적 동등성이라는 큰 우산 아래 있던 PE들이, 절삭이라는 칼 앞에서 제각각으로 쪼개지는 셈이다.

실험이 가리키는 방향: 혼합 전략의 우위

이론적 결과는 자연스럽게 한 가지 실용적 질문을 낳는다. 서로 다른 표현력을 가진 절삭 PE들을 조합하면 어떨까? 연구진은 실제 그래프 데이터셋에서 다양한 절삭 PE 조합을 실험한다. 결과는 명확하다. 단일 PE 계열에 의존하는 것보다 여러 종류의 절삭 PE를 혼합해서 사용하는 것이 일관되게 더 나은 성능을 보인다.

이 발견은 단순한 엔지니어링 팁 이상의 의미를 담고 있다. 서로 다른 절삭 PE는 각각 그래프의 다른 측면을 포착한다. 스펙트럼 PE가 놓치는 정보를 보행 기반 PE가 잡아낼 수 있고, 그 역도 마찬가지다. 완전한 버전에서는 이론적으로 교환 가능했던 두 계열이, 절삭 이후에는 서로 보완적인 관계로 재정의되는 것이다.

이 논문이 열어놓은 연구 방향은 GNN 설계의 실무 관행에 직접적인 함의를 갖는다. 어떤 PE를 쓸지 선택하는 문제는 '완전 버전의 이론적 동등성'이라는 편의적 가정 아래 가려져 있었다. 연구진의 작업은 이 가정을 걷어내고, 실제로 배포되는 절삭 형태에서의 표현력 차이를 명시적으로 다루어야 한다고 요구한다. 절삭의 종류와 방식이 GNN의 능력을 근본적으로 다르게 규정한다는 사실, 이제 이론이 그것을 확인해 준다.