🤖 machine learning

Understanding Truncated Positional Encodings for Graph Neural Networks

이 논문은 그래프 신경망에서 절단된 위치 인코딩(truncated positional encodings)을 사용하는 것의 이론적 및 경험적 함의를 조사하며, 이러한 절단이 서로 다른 인코딩 계열의 표현력을 근본적으로 변화시켜 스펙트럴 변형(spectral variants)을 1-WL 테스트보다 강하지 않게 만든다는 점을 밝히고, 여러 절단된 인코딩을 결합하는 것이 실제 데이터셋에서 단일 계열을 사용하는 것보다 성능이 뛰어남을 입증한다.

원저자: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

게시일 2026-06-12

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 로봇에게 도시의 레이아웃을 이해하도록 가르치고 있다고 상상해 보세요. 이 로봇은 **그래프 신경망(GNN)**이며, 도시는 **교차로(노드)**와 **도로(엣지)**로 이루어진 그래프입니다.

로봇이 일을 잘 해내기 위해서는 단순히 어떤 도로가 서로 연결되어 있는지에 대한 목록 그 이상이 필요합니다. 로봇에게는 **위치 인코딩(Positional Encodings, PEs)**이 필요합니다. PEs는 모든 교차로가 다른 교차로와 비교하여 어디에 위치하는지를 알려주는 "지도"나 "나침반"과 같습니다. 이 지도 없이 로봇은 눈을 감고 길을 걷는 사람과 같습니다. 바로 옆에 누가 있는지는 알지만, 자신이 도심 근처에 있는지 아니면 막다른 골목에 갇혀 있는지는 전혀 모르는 상태인 것이죠.

문제점: "완벽한" 지도는 너무 무겁다

완벽한 지도를 만드는 데는 두 가지 주요 방법이 있습니다:

스펙트럼 지도(The Spectral Map): 복잡한 수학(고윳값과 고유벡터)을 사용하여 도시의 "진동"이나 전역적인 형태를 파악합니다.
워크 지도(The Walk Map): 1단계, 2단계, 3단계 등... 한 지점에서 다른 지점까지 이동하는 방법이 얼마나 많은지를 계산합니다.

수학적으로, 만약 당신이 전체 지도(모든 단계, 모든 진동)를 사용한다면, 이 두 방법은 똑같이 강력합니다. 이들은 거의 모든 서로 다른 도시 레이아웃을 구별해 낼 수 있습니다.

하지만 함정이 있습니다: 거대한 도시를 위한 이 "완전한" 지도를 만드는 것은 엄청난 컴퓨터 연산 능력과 메모리를 소모합니다(구체적으로, 도시가 커질수록 기하급수적으로 어려워집니다). 이는 마치 세상의 모든 지도가 담긴 도서관을 배낭에 넣고 다니려는 것과 같습니다. 실생활에서 사용하기에는 너무 무겁습니다.

그래서 엔지니어들은 **절단된 위치 인코딩(Truncated Positional Encodings)**을 사용합니다. 전체 도서관 대신, 앞부분의 몇 개 장(chapter)만을 가져오는 것입니다.

절단된 스펙트럼(Truncated Spectral): 처음 몇 개의 "진동"(고유벡터)만을 사용합니다.
절단된 워크(Truncated Walk): 처음 몇 단계의 걷기(인접 행렬의 거듭제곱)만을 사용합니다.

여기서 논문이 던지는 핵심 질문은 이것입니다: 만약 우리가 이 지도의 끝부분을 잘라낸다면, 그것들이 여전히 동일하게 작동할 것인가?

거대한 발견: "자르는 것"이 모든 것을 바꾼다

저자들은 놀라운 답을 찾아냈습니다: 아니요, 더 이상 똑같이 작동하지 않습니다.

완전한 지도를 가지고 있을 때, 스펙트럼 방식과 워크 방식은 쌍둥이처럼 닮아 있습니다. 하지만 이를 *절단(truncate)*하면, 이들은 서로 다른 강점과 약점을 가진 매우 다른 형제 관계가 됩니다.

"절단된 스펙트럼"의 함정: 때때로, 단지 처음 몇 개의 진동만을 사용하는 것이 지도가 아예 없는 것보다 로봇에게 더 나쁜 결과를 초래하기도 합니다! 어떤 경우에는 절단된 스펙트럼 지도가 너무 약해서, 아주 단순한 "이웃 확인" 테스트(1-WL 테스트라고 불리는)조차도 쉽게 식별해 낼 수 있는 두 도시의 차이를 구분하지 못합니다.
"절단된 워크"의 함정: 반대로, 절단된 워크 지도가(몇 단계의 걷기만으로) 완전히 놓쳐버리지만, 절단된 스크펙트럼 지도는 즉시 잡아내는 도시 레이아웃들이 존재합니다.

비유하자면 이렇습니다: 어떤 사람을 식별한다고 상상해 보세요.

전체 스펙트럼 지도는 그 사람의 전체 DNA와 생애 기록을 아는 것과 같습니다.
절단된 스펙트럼 지도는 오직 그 사람의 키만 아는 것과 같습니다.
절단된 워크 지도는 집에서 식료품점까지 걸어가는 데 몇 걸음이 걸리는지만 아는 것과 같습니다.

만약 당신이 키(절단된 스펙트럼)만 안다면, 키가 같은 두 사람을 혼동할 수 있습니다. 만약 당신이 걷는 거리(절단된 워크)만 안다면, 집에서 가게까지 거리가 같은 두 사람을 혼동할 수 있습니다. 하지만 만약 당신이 둘 다 사용한다면, 훨씬 더 나은 그림을 얻을 수 있습니다.

새로운 영웅: "조화적 거리(Harmonic Distances)"

이 논문은 **k-조화적 거리(k-harmonic distances)**라는 새로운 계열의 지도를 소개합니다.

유효 저항(Effective Resistance)(일종의 1-조화적 거리)을 생각해보면, 이는 두 지점이 얼마나 "연결되어 있는지", 예를 들어 전기 흐름이 얼마나 발생하는지와 같은 것을 측정합니다.
논문은 바이하모닉 거리(Biharmonic distance)(2-조화적 거리)가 다른 것, 즉 한 거리(street)가 전체 도시에서 얼마나 "중심적"이거나 중요한지를 측정한다는 것을 보여줍니다.

저자들은 이 새로운 지도들이 강력하지만, 동시에 한계도 있다는 것을 증명했습니다. 만약 당신이 "저항" 지도만 사용한다면 "바이하모닉" 지도가 잡아내는 세부 사항을 놓칠 수 있고, 그 반대도 마찬가지입니다. 하지만 만약 당신이 충분히 많은 조화적 지도들을 사용한다면, 이 무거운 전체 지도의 성능을 재현할 수 있습니다.

실무적인 조언: "섞어서 사용하라(Mix and Match)"

단 하나의 절단된 지도만으로는 완벽할 수 없기에, 저자들은 엔지니어들을 위해 간단한 규칙을 제안합니다: 단 한 종류의 절단된 지도에만 의존하지 마십시오.

대신, 그것들을 함께 섞으십시오.

"워크" 지도의 몇 단계를 결합합니다.
"스펙트럼" 지도의 몇 가지 "진동"을 결합합니다.
"조화적" 거리 한두 개를 추가로 던져 넣습니다.

실험:
저자들은 실제 데이터셋(분자의 화학적 특성 예측 등)을 통해 이를 테스트했습니다.

한 종류의 절단된 지도만 사용하는 것은 괜찮았습니다.
하지만 서로 다른 종류의 절단된 지도를 혼합하여 사용하는 것이 훨씬 더 뛰어난 성능을 보였습니다.

이는 도시를 항해하는 것과 같습니다. 나침반(스펙트럼), 만보계(워크), 그리고 교통 흐름의 척도(조화적 거리)를 모두 갖추고 있는 것이, 단 하나에만 의존하는 것보다 훨씬 더 낫습니다.

요약

전체 지도는 실생활에서 너무 무겁기 때문에, 우리는 "절단된(truncated)" 버전을 사용합니다.
자르는 것은 평등함을 깨뜨립니다: 절단된 스펙트럼 지도와 절단된 워크 지도는 더 이상 동일하지 않으며, 서로 다른 사각지대를 가집니다.
어떤 절단은 지도 없이도 못한 것보다 못할 수 있습니다: 어떤 경우에 절단된 스펙트럼 지도는 매우 기본적인 테스트보다도 약합니다.
해결책: 하나만 고르지 마십시오. 최고의 성능을 내면서도 과도한 계산 비용을 피하려면 다양한 종류의 절단된 지도를 섞어서 사용하십시오.

기술 요약: 그래프 신경망을 위한 절단된 위치 인코딩(Truncated Positional Encodings)의 이해

문제 정의

그래프 신경망(GNN), 특히 메시지 패싱 신경망(MPNN)은 1-Weisfeiler-Lehman(1-WL) 테스트와 동등한 제약 조건으로 공식화되는 전역적 구조 정보 포착 능력의 근본적인 한계를 가지고 있습니다. 이를 극복하기 위해 그래프 트랜스포머(GT)와 강화된 GNN은 구조적 정보를 주입하기 위해 위치 인코딩(Positional Encodings, PEs)을 활용합니다. 두 가지 지배적인 PE 계열은 스펙트럼 인코딩(라플라시안 고유 공간에서 유도됨)과 워크 기반 인코딩(인접 행렬의 거듭제곱에서 유도됨)입니다.

이론적으로, 이들의 완전한 버전( $\Omega(n)$ 개의 고유벡터 또는 행렬 거듭제곱을 사용하는 경우)은 1-WL과 3-WL 사이에 위치하는 동일한 표현력(expressive power)을 가집니다. 그러나 이러한 완전한 인코딩을 계산하려면 $O(n^3)$ 의 시간 및 공간 복잡도가 필요하며, 이는 실제 응용 분야에서 매우 부담스럽습니다. 결과적으로, 실무자들은 절단된 변형(예: 처음 $k$ 개의 고유벡터 또는 처음 $k$ 개의 인접 행렬 거듭제곱)에 의존하게 됩니다. 절단된 PE의 이론적 특성, 표현력 및 비교 우위에 대한 연구는 여전히 미개척 영역으로 남아 있으며, 이는 이론적 보증과 실제 구현 사이의 간극을 만들어냅니다.

방법론

저자들은 이론적 분석과 경험적 검증을 통해 절단된 PE에 대한 체계적인 연구를 시작합니다.

이론적 프레임워크

본 논문은 표현력을 규명하기 위해 WL 계층 구조와 그 변형들을 활용합니다:

$\psi$ -WL 테스트: 노드 색상이 상대적 위치 인코딩(RPE) $\psi$ 를 사용하여 업데이트되는 WL 테스트의 변형입니다.
Sparse- $\psi$ -WL 테스트: $\psi$ 가 에지 특징(edge features)으로 사용되는 MPNN을 위한 확장입니다.
분석된 주요 계열:
1. 절단된 고유 공간 투영 ( $k$ -EP-WL): 라플라시안의 처음 $k$ 개 고유 공간 투영을 사용합니다.
2. 절단된 워크 인코딩 ( $k$ -Walk-WL): 인접 행렬의 처음 $k$ 개 거듭제곱을 사용합니다.
3. 유효 저항 (Effective Resistance, Resistance-WL): 특정 스펙트럼 거리(1-조화 거리)입니다.
4. $k$ -조화 거리 ( $k$ -Harmonic Distances): $H_k(u, v) = \sqrt{(1_u - 1_v)^T (L^+)^k (1_u - 1_v)}$ 로 정의되는 유효 저항의 일반화입니다.

저자들은 서로 다른 절단된 PE 및 WL 테스트 하에서 분리 가능성(separability) 또는 구별 불가능성(indistinguishability)을 증명하기 위해 특정 그래프 쌍(예: 경로 그래프와 완전 그래프의 곱, 또는 사이클과 서로 떨어진 사이클들의 합집합)을 구성합니다.

경험적 평가

실험은 세 가지 벤치마크에서 수행되었습니다:

BREC: 1-WL부터 4-WL까지 구별 불가능한 비동형 그래프들을 테스트함으로써 GNN의 "실현된 표현력(realized expressivity)"을 측정하도록 설계된 데이터셋입니다.
ZINC-12k: 분자의 용해도를 측정하는 그래프 회귀 벤치마크로, 절단된 PE를 혼합하는 것이 성능을 향상시킨다는 가설을 테스트하는 데 사용되었습니다.
ogbg-molhiv: HIV 억제 여부를 판별하는 이진 분류 벤치마크입니다.

저자들은 단일 계열 및 스펙트럼, 워크, $k$ -조화 인코딩의 다양한 조합을 포함한 다양한 절단된 PE를 사용하여 Graphormer-GD 아키텍처와 MPNN(GINE)을 평가했습니다.

주요 기여 및 결과

1. 절단된 형태에서의 표현력의 발산

본 논문은 완전한 스펙트럼 및 워크 인코딩은 동등하지만, 이들의 절단된 형태는 근본적으로 다르다는 것을 증명합니다:

절단된 스펙트럼 vs. 1-WL: 저자들은 절단된 고유 공간 투영( $k$ -EP-WL)이 1-WL 테스트보다 약할 수 있음을 보여줍니다. 구체적으로, 1-WL로는 구별 가능하지만 $k \in \Omega(n)$ 인 경우 $k$ -EP-WL로는 구별할 수 없는 그래프 쌍이 존재합니다 (정리 4.1).
절단된 워크 vs. 스펙트럼: 반대로, 단일 고유 공간 투영(1-EP-WL)으로는 구별 가능하지만 $\Omega(n)$ 크기의 워크 인코딩으로는 구별할 수 없는 그래프 쌍이 존재합니다 (정리 4.2).
시사점: 단일 절단된 PE 계열이 엄격하게 우월하다고 할 수 없습니다. 이들은 서로 다른 구조적 측면을 포착하며, 표준 WL 계층 구조와 비교 불가능할 수 있습니다.

2. 유효 저항의 한계

본 논문은 유효 저항(1-조화 거리)을 분석하고, 가중치 그래프에서 이것이 전체 고유 공간 투영이나 워크 인코딩보다 약한 PE임을 발견했습니다.

정리 4.3: Resistance-WL로는 구별할 수 없지만 Adjacency-WL(따라서 비가중치 그래프에서의 1-WL)로는 구별 가능한 가중치 그래프가 존재합니다.
따름정리 4.1: Resistance-WL은 그래프의 전체 스펙트럼을 인코딩하지 못하며, 이는 이전의 가설을 반박합니다.

3. 가교로서의 $k$ -조화 거리

저자들은 $k$ -조화 거리를 스펙트럼 인코딩과 다항식 인코딩 사이의 자연스러운 가교로 도입합니다.

완전성: $\Theta(n)$ 개의 $k$ -조화 거리를 연결하면 완전한 스펙트럼 또는 워크 인코딩과 동등한 표현력을 가진 인코딩을 얻습니다 (정리 4.6).
차별적 성능: 고정된 크기의 인코딩 내에서도 차이가 발생합니다. 예를 들어, 바이조화 거리(biharmonic distance, 2-조화)는 상수 번의 반복만으로 특정 트리 쌍을 구별할 수 있는 반면, 유효 저항(1-조화)은 $O(n)$ 번의 반복이 필요합니다 (정리 4.7).
강건성: 그러나 하나의 $k$ -조화 거리가 그래프 쌍을 구별한다면, 대부분의 다른 $k$ -조화 거리도 그들을 구별할 것입니다 (정리 4.8).

4. 경험적 발견: 혼합의 힘

BREC 결과: $k$ -조화 거리는 단일 채널의 낮은 오버헤드 인코딩과 경쟁력 있는 결과를 얻었으며, 종종 1-WL과 3-WL 사이의 그래프들에 대한 이론적 상한선과 일치하는 성능을 보였습니다.
ZINC 결과: 가장 중요한 발견은 서로 다른 계열의 PE를 혼합하는 것(예: 절단된 워크와 $k$ -조화의 결합)이 단일 계열보다 더 뛰어난 성능을 보인다는 점입니다. 절단된 워크와 $k$ -조화를 혼합한 모델은 ZINC-12k에서 가장 낮은 평균 절대 오차(MAE)를 달이트하며 단일 계열 베이스라인을 능가했습니다.
효율성: 본 논문은 빠른 라플라시안 솔버와 Johnson-Lindenstrauss 투영을 사용하여 $k$ -조화 거리를 $O(mk \cdot \text{poly}(\log n))$ 시간에 근사할 수 있어, 정확한 계산에 따르는 $O(n^3)$ 비용을 피할 수 있다고 언급합니다.

의의 및 주장

본 논문은 절단된 위치 인코딩을 단순히 완전한 인코딩의 근사치로 보는 관점에서 벗어나, 고유한 표현적 특성을 가진 **독립적인 설계 공간(design space)**으로 보는 관점으로 전환하며, 절단된 위치 인코딩에 대한 이론적 연구를 개시한다고 주장합니다.

이론적 통찰: 이 연구는 절단이 PE가 포착하는 정보를 근본적으로 변화시키며, 특정 사례에서 표준 WL 계층 구조와 비교 불가능하게 만든다는 것을 보여줍니다.
실무적 지침: 저자들은 절단된 인코딩을 사용할 때 서로 다른 계열의 PE를 혼합하라는 경험적 규칙을 제안합니다. 이 접근 방식은 계산 비용을 제어하면서도 상호 보완적인 구조적 단서를 포착합니다.
제한적 범위: 저자들은 그래프 동형성(graph isomorphism)이 원칙적인 대리 지표이기는 하지만, 실제 작업에는 동형성 테스트와 엄격하게 일치하지 않을 수 있는 다운스트림 신호(중심성, 모티프 등)가 포함될 수 있음을 인정합니다. 따라서 본 연구의 주요 기여는 모든 그래프 학습 작업에 대한 보편적인 해결책을 주장하는 것이 아니라, 체계적인 경험적 연구를 위한 이론적 토대와 시작점을 마련하는 데 있습니다.