기술 요약: 토큰화에서 길을 잃다: 트랜스포머를 위한 그래프 토큰화의 근본적 트레이드오프

문제 제기

트랜스포머는 그래프 학습을 위한 강력한 아키텍처로 부상했으나, 그래프 구조 데이터에 이를 적용하려면 선행 단계인 토큰화가 필요하다. 시퀀스나 그리드와 달리 그래프는 고유한 연속 입력 형식이 부재하다. 따라서 어떤 구조적 정보가 입력 계층에서 모델에 노출될지 결정하기 위해 그래프-토큰 매핑을 선택해야 한다.

스펙트럴, 랜덤 워크, 인접 행렬 등 다양한 토큰화 전략이 존재하지만, 이들은 종종 경험적 설계 선택이나 전처리 세부 사항으로 취급된다. 본 논문은 토큰화 선택이 트랜스포머의 표현력 (expressivity) 에 있어 근본적인 구성 요소라고 주장한다. 다루는 핵심 문제는 서로 다른 토큰화 방식이 상호 교환 가능한지, 아니면 그래프 작업 해결에 필요한 깊이와 구조적 정보 복원 능력과 관련하여 서로 다른 계산 체제를 유발하는지 여부이다.

방법론

저자들은 그래프 토큰화를 계산 모델의 필수 부분으로 형식화하여, 유한한 깊이 ($L$), 너비 ($m$), 정밀도 ($p$) 를 가진 트랜스포머의 표현력을 세 가지 주요 토큰화 계열 하에서 분석한다:

1. 인접 행렬 토큰화 (Adjacency Tokenization): 각 노드의 인접 행렬 행을 통해 노드의 국소 연결성을 인코딩한다. 이는 손실 없으나 국소 구조만 노출한다.
2. 스펙트럴 (라플라시안) 토큰화 (Spectral (Laplacian) Tokenization): 그래프 라플라시안 ($L = D - A$) 의 고유값 분해에서 토큰을 유도한다. 이는 전역 위상적 특성을 포착하지만 치환 공변성 (permutation-equivariant) 을 가진다.
3. 랜덤 워크 토큰화 (Random-Walk Tokenization): 길이 $1$부터$t(n)$까지의 랜덤 워크 복귀 확률을 인코딩한다. 이는 확산 패턴을 포착하지만 본질적으로 손실적이다.

방법론은 복잡도 이론적 분석과 통제된 실험을 결합한다.

• 이론적 분석: 저자들은 그래프 작업을 복잡도 클래스 (예: $TC^0$, $NC^1$, $L$) 에 매핑하여 하한과 불가능성 결과를 수립한다. 유한한 깊이의 제약과 토큰 표현의 수학적 성질 (예: 조건수, 정보 손실) 을 고려하여 $k$-닫힌-walk 탐지, 연결성, 삼각형 카운팅, 평면성 등 특정 작업이 서로 다른 토큰화 하에서 어떻게 동작하는지 분석한다.
• 실증적 검증: 실험은 합성 작업 (깊이 분리 검증) 과 실제 세계 벤치마크 (GraphBench, Open Graph Benchmark, ZINC) 에서 수행된다. 연구는 각 토큰화의 전체 및 단축 버전을 사용하는 트랜스포머를 평가하고, DeepSet 및 GIN 베이스라인과 성능을 비교한다.

주요 기여

1. 계산 제약으로서의 토큰화 형식화

본 논문은 입력 표현이 유한한 깊이에서 트랜스포머의 표현력을 어떻게 제약하는지 형식화한다. 토큰화가 단순한 특징 공학 단계가 아니라 모델이 접근할 수 있는 구조적 종속성을 결정한다는 것을 입증한다.

2. 토큰화 간의 깊이 분리

저자들은 동일한 그래프 계산이 토큰화에 따라 매우 다른 깊이를 요구할 수 있음을 증명한다:

• 랜덤 워크 vs 인접 행렬: $k$-닫힌-walk 탐지는 랜덤 워크 토큰화에서는 통계가 명시적이므로 $O(1)$ 깊이로 해결 가능하지만, 인접 행렬 토큰화에서는 $\Omega(\log k)$ 깊이가 필요하다. 이는 치환군 $S_5$의 단어 문제 ($NC^1$-완전 문제) 를 그래프 위상으로 축소하여 증명되었으며, 상수 깊이 트랜스포머 ($TC^0$) 가 인접 행렬 토큰이 요구하는 순차적 경로 탐색을 시뮬레이션할 수 없음을 보여준다.
• 인접 행렬 vs 스펙트럴: 전역 그래프 연결성 해결은 인접 행렬 토큰화에서는 $\Omega(\log n)$ 깊이가 필요하지만, 스펙트럴 토큰화에서는 $O(1)$ 깊이로 해결된다.

3. 본질적 한계와 손실성

• 랜덤 워크는 증명적으로 손실적임: 걷기 길이에 관계없이 랜덤 워크 토큰화는 그래프 평면성을 결정할 수 없다. 저자들은 Godsil-McKay (GM) 스위칭을 사용하여 동일한 랜덤 워크 분포를 가진 평면 및 비평면 그래프를 구성하여, 어떤 트랜스포머의 깊이와 너비로도 위상적 구분을 복원할 수 없음을 증명한다.
• 스펙트럴 단축은 취약함: 라플라시안 스펙트럼을 단축하는 것 (심지어 단일 고유값만이라도) 은 삼각형 카운팅을 불가능하게 만들 수 있다. 저자들은 대칭 노드 간에 간선을 추가하면 고유값 하나만 변함을 보여주며, 이 고유값이 단축되면 트랜스포머가 그래프를 구별할 수 없음을 입증한다.
• 인접 행렬 단축: 인접 행렬 토큰의 차원을 단축 (랜덤 프로젝션을 통해) 하는 것은 삼각형 카운팅과 같은 작업을 해결할 능력을 파괴한다. 이는 통신 복잡도 하한 (Set Disjointness) 을 통해 증명된다.

4. 국소 작업을 위한 스펙트럴 토큰화의 조건 불량성

스펙트럴 토큰화는 전역 위상을 포착하지만, 엣지 예측과 같은 국소 작업에는 수학적으로 조건이 불량하다. 본 논문은 전역 스펙트럼에서 국소 엣지를 디코딩하는 데 필요한 매개변수 노름이 최대 차수 ($d_{max}$) 에 비례하여 하한을 유도한다. 이는 모델이 Softmax 포화 (소멸하는 기울기) 를 겪거나 폭발적인 가중치를 요구하여 최적화가 어려워지는 트레이드오프를 강제한다.

5. 제한된 깊이에서의 변환 불가능성

본 논문은 제한된 깊이에서 토큰화 계열 간 변환이 일반적으로 불가능함을 수립한다.

• 트랜스포머는 인접 행렬 토큰을 랜덤 워크 통계로 효율적으로 변환할 수 없다 ($\Omega(\log k)$ 깊이 필요).
• 트랜스포머는 정보 손실로 인해 랜덤 워크 토큰에서 완전한 인접 행렬 또는 라플라시안 표현을 복원할 수 없다.
• 전역 (스펙트럴) 과 국소 (인접 행렬) 뷰 간 변환은 심각한 계산 병목 현상이나 최적화 불안정성을 초래한다.

결과

이론적 발견:

• 깊이 분리: 실증적 검증은 스펙트럴 토큰화가 모든 그래프 크기에서 $L=1$로 연결성 작업을 해결하는 반면, 인접 행렬 토큰화는 더 큰 그래프 ($n \ge 128$) 에서 우연 수준으로 무너짐을 확인한다.
• 복원 한계: 인접 행렬 토큰에서 랜덤 워크 복귀 확률을 예측하도록 트랜스포머를 훈련할 때, 오차는 걷기 길이 $k$에 따라 증가하며, 이는 $\Omega(\log k)$ 깊이 요구사항과 일치한다.
• 평면성: 랜덤 워크 토큰을 사용하는 모델은 깊이가 증가하더라도 평면과 비평면 그래프를 구별하지 못하여 이론적 불가능성 결과를 확인한다.

실증적 발견:

• 작업 의존성: 단일 토큰화가 지배적이지 않다.
  • 국소 작업: 명시적 국소 제약에 지배되는 작업 (예: 최대 클릭, 위상적 순서) 에는 인접 행렬 토큰화가 가장 잘 수행된다.
  • 전역 작업: 전역 기하학에 의존하는 작업 (예: Tox21 분자 속성 예측) 에는 스펙트럴 (라플라시안) 토큰화가 가장 잘 수행된다.
  • 결합 접근법: 상호 보완적인 토큰화 (인접 행렬 + 스펙트럴 + 랜덤 워크) 를 결합하는 것이 종종 최상의 성능을 내며, 모델이 서로 다른 구조적 신호를 활용할 수 있게 한다.
• 단축 효과: 단축된 토큰화는 일반적으로 성능을 저하시키며, 특히 정확한 구조 복원이 필요한 작업 (예: 삼각형 카운팅) 에서 두드러지는데, 이는 단축의 이론적 "취약성"을 검증한다.

중요성과 주장

본 논문은 그래프 토큰화가 전처리 세부 사항이 아닌 근본적인 트레이드오프라고 주장한다. 토큰화 선택은 트랜스포머가 받는 그래프의 "시점"을 결정하므로, 유한한 깊이에서 모델이 표현할 수 있는 구조적 종속성 클래스를 제약한다.

저자들이 강조한 주요 교훈은 다음과 같다:

1. 비교환성: 인접 행렬, 스펙트럴, 랜덤 워크 토큰화는 상호 교환 가능하지 않으며, 서로 다른 깊이 체제와 표현력 한계를 유발한다.
2. 본질적 한계: 특정 토큰화는 증명된 맹점을 가진다 (예: 랜덤 워크는 평면성을 볼 수 없음; 스펙트럴은 국소 엣지에 조건이 불량함).
3. 변환 장벽: 초기 토큰화가 불리하다면 트랜스포머는 단순히 이러한 표현 간 변환을 효율적으로 "학습"할 수 없다; 이러한 격차를 메우기 위해 필요한 깊이는 prohibitive(부적절할 정도로 큼) 일 수 있다.
4. 실용적 함의: 최적의 토큰화는 하류 작업의 구조적 성격에 달려 있다. 상호 보완적인 뷰를 결합하는 것은 단일 표현의 한계를 극복하는 강력한 전략이다.

저자들은 분석이 노드 수준 토큰화에 초점을 맞추고 있지만, 그 발견은 더 넓은 원칙을 시사한다고 결론지었다: 입력 표현은 그래프 학습에서 복잡성의 핵심 축이며, 향후 연구는 최적화 과제와 엣지 수준 토큰화를 탐구해야 한다.