Graph Tokenization for Bridging Graphs and Transformers

이 논문은 가역적 그래프 직렬화와 BPE 를 결합하여 그래프 구조를 시퀀스로 변환하는 토크나이저를 제안함으로써, 구조적 수정 없이도 BERT 와 같은 트랜스포머를 그래프 벤치마크에 적용해 기존 그래프 신경망 및 전용 트랜스포머보다 우수한 성능을 달성했습니다.

핵심

이 논문은 **"그래프 (연결된 데이터) 를 어떻게 하면 컴퓨터가 가장 잘 이해하는 '문장'으로 바꿀 수 있을까?"**라는 질문에 대한 획기적인 답을 제시합니다.

제목은 **<그래프 토큰화: 그래프와 트랜스포머 (Transformer) 를 잇는 다리>**입니다.

이 복잡한 내용을 일상적인 언어와 비유로 쉽게 설명해 드릴게요.

---

1. 문제: 왜 그래프는 컴퓨터가 읽기 힘든가요?

컴퓨터가 가장 잘하는 일 중 하나는 **책 (텍스트)**을 읽는 것입니다.

• 책 (텍스트): 글자가 줄줄이 이어져 있습니다. "A 가 B 를 만나고, B 가 C 를 만났다"처럼 순서가 명확합니다.
• 그래프 (데이터): 페이스북 친구 관계, 분자 구조, 지하철 노선도처럼 복잡하게 얽혀 있는 연결입니다. "누가 누구를 만났는지"는 알 수 있지만, "어떤 순서로 읽어야 할지" 정해진 규칙이 없습니다.

기존의 최신 AI(트랜스포머) 는 "줄글"을 읽는 데 특화되어 있어서, 이런 "얽힌 연결"을 직접 읽으려 하면 매우 혼란스러워합니다.

2. 해결책: 그래프를 '문장'으로 바꾸는 마법 (그래프 토큰화)

이 연구팀은 그래프를 AI 가 읽을 수 있는 **문장 (시퀀스)**으로 바꾸는 새로운 방법을 개발했습니다. 이를 **그래프 토큰화 (Graph Tokenization)**라고 부릅니다.

이 과정은 크게 두 단계로 나뉩니다.

1 단계: 그래프를 '줄글'로 펴기 (Serialization)

얽혀 있는 그래프를 한 줄로 펴야 합니다. 이때 중요한 것은 원래 모양을 망치지 않고 펴야 한다는 점입니다.

• 비유: 복잡한 미로 지도를 한 줄로 펴서 설명할 때, "여기서 왼쪽으로 가다가 오른쪽으로 꺾으면..."이라고 설명하는 것과 같습니다.
• 이 연구의 특징: 단순히 무작위로 걷는 게 아니라, **가장 자주 나오는 길 (빈도수)**을 먼저 선택하도록 지도를 그립니다. 그래야 나중에 AI 가 "아, 이 부분은 자주 나오는 중요한 길구나라"고 쉽게 이해할 수 있습니다.

2 단계: 자주 나오는 단어를 하나로 합치기 (BPE)

한 줄로 펴진 글자가 너무 길면 컴퓨터가 읽기 힘듭니다. 그래서 자주 나오는 단어 묶음을 하나의 기호로 합칩니다.

• 비유: 영어 단어 "The", "quick", "brown", "fox"가 자주 나오면, 이를 "The_quick_brown_fox"라는 하나의 새로운 단어로 만들어버리는 것입니다.
• 효과: 문장이 짧아지고, 컴퓨터가 중요한 패턴을 더 빠르게 찾아낼 수 있습니다.

3. 핵심 아이디어: "자주 나오는 구조를 찾아내라"

이 연구의 가장 큰 장점은 통계를 이용했다는 점입니다.

• 일반적인 방법은 그래프를 무작위로 줄글로 바꾸는데, 이렇게 하면 중요한 정보가 흩어집니다.
• 이 연구팀은 "이 그래프에서 어떤 구조 (예: 분자에서 자주 나오는 원자 결합) 가 가장 많이 나오는지" 먼저 세어봅니다.
• 그런 다음, 그 자주 나오는 구조가 문장 속에서 서로 붙어오도록 줄글을 만듭니다.
• 그 결과, AI 가 "자주 나오는 중요한 구조"를 하나의 의미 있는 단어로 인식하게 됩니다.

4. 결과: 왜 이것이 대단한가요?

이 방법을 사용하면 기존에 쓰던 거대 AI 모델 (BERT, GPT 등) 을 그대로 가져와서 그래프 데이터도 처리할 수 있게 됩니다.

• 기존 방식: 그래프 전용 AI 를 새로 만들어야 했고, 성능도 한계가 있었습니다.
• 이 연구: 그래프를 '문장'으로 바꾼 뒤, 이미 잘 훈련된 거대 AI 에게 먹이면 됩니다.
• 성과: 14 가지 다른 데이터 (약물 발견, 분자 구조, 소셜 네트워크 등) 에서 기존 최고의 AI 들보다 더 좋은 성적을 냈습니다.

5. 한 줄 요약

**"복잡하게 얽힌 그래프 데이터를, AI 가 가장 잘 읽는 '줄글'로 깔끔하게 정리하고, 자주 나오는 중요한 패턴을 '단어'로 압축해서, 기존에 쓰던 최고의 AI 모델들이 그래프도 완벽하게 이해하게 만든 방법"**입니다.

이 기술은 앞으로 새로운 약을 개발하거나, 복잡한 사회 현상을 분석할 때 AI 가 훨씬 더 똑똑하고 빠르게 일할 수 있는 길을 열어줍니다. 마치 복잡한 지하철 노선도를 한 줄의 지시문으로 바꿔, AI 가 "다음 역은 어디?"를 순식간에 찾아내게 한 것과 같습니다.

기술 요약

1. 문제 정의 (Problem)

대규모 사전 학습된 Transformer 모델 (LLM 등) 의 성공은 원시 입력을 이산적인 심볼 (토큰) 시퀀스로 변환하는 **토크나이저 (Tokenizer)**에 밀접하게 연관되어 있습니다. 그러나 이러한 모델을 그래프 구조 데이터에 적용하는 것은 다음과 같은 근본적인 어려움으로 인해 여전히 큰 도전 과제로 남아 있습니다.

• 구조적 차이: 텍스트는 선형적인 경로 그래프로 모델링될 수 있어 토큰 순서가 명확하지만, 일반적인 그래프는 분기 구조를 가지며 순열 불변성 (Permutation Invariance) 을 가집니다.
• 기존 방법의 한계:
  1. Graph Transformer: GNN 에 어텐션 메커니즘을 도입하여 그래프 전용 아키텍처를 설계하는 방식입니다. 이는 표준 시퀀스 모델 생태계와 단절되며, 그래프 특화 설계를 요구합니다.
  2. 임베딩 기반 접근: 그래프를 연속적인 임베딩으로 변환하여 Transformer 에 입력하는 방식입니다. 이는 정보 손실이나 불안정한 표현으로 이어져 성능 저하를 초래할 수 있습니다.
• 핵심 과제: 그래프의 위상적 구조와 레이블을 보존하면서, 이를 Transformer 이 처리할 수 있는 **이산적인 시퀀스 (Discrete Sequence)**로 변환하는 신뢰할 수 있는 토크나이저를 개발하는 것입니다.

2. 제안 방법론 (Methodology)

저자들은 **그래프 토크나이저 (GraphTokenizer)**라는 새로운 프레임워크를 제안합니다. 이는 **가역적 그래프 직렬화 (Reversible Graph Serialization)**와 **LLM 에서 널리 사용되는 Byte Pair Encoding (BPE)**을 결합한 방식입니다.

A. 구조 유도형 가역적 직렬화 (Structure-Guided Reversible Serialization)

그래프를 시퀀스로 변환할 때 정보 손실 없이 원래 그래프를 복원할 수 있어야 하며 (가역성), 동일한 그래프에 대해 항상 동일한 시퀀스를 생성해야 합니다 (결정론적). 이를 위해 다음과 같은 과정을 거칩니다.

1. 지역 패턴 통계 수집: 학습 데이터셋에서 노드 - 엣지 - 노드 (Node-Edge-Node) 형태의 기본 패턴 (예: $C-C$, $C=O$) 의 빈도수를 계산하여 전역 빈도 맵 $F$를 생성합니다.
2. 빈도 유도 오일러 회로 (Frequency-Guided Eulerian Circuit):
   • 기존 오일러 회로 알고리즘은 탐색 시 다음 엣지를 임의로 선택하여 비결정론적이었습니다.
   • 제안된 방법은 빈도 맵 $F$를 활용하여, 현재 노드에서 인접한 엣지 중 통계적으로 가장 빈번하게 나타나는 패턴을 가진 엣지를 우선적으로 선택하도록 유도합니다.
   • 이를 통해 자주 등장하는 하위 구조 (Substructures) 가 시퀀스 내에서 인접하게 배치되도록 하여, 후속 BPE 단계에서 의미 있는 토큰으로 병합될 확률을 높입니다.
   • 이 과정은 그래프의 모든 엣지를 방문하므로 가역적이며, 빈도 기반 규칙에 의해 결정론적입니다.

B. BPE 기반 어휘 학습 (Vocabulary Learning via BPE)

직렬화된 시퀀스 코퍼스에 LLM 의 토크나이저인 BPE를 적용합니다.

• BPE 는 가장 빈번하게 나타나는 인접 심볼 쌍을 반복적으로 병합하여 새로운 토큰을 생성합니다.
• 구조 유도 직렬화를 통해 통계적으로 중요한 그래프 하위 구조들이 시퀀스에서 인접하게 배치되므로, BPE 는 이를 자연스럽게 "의미 있는 그래프 토큰" (예: 특정 기능기, 고리 구조) 으로 학습합니다.
• 최종적으로 그래프는 Transformer 이 처리할 수 있는 이산 토큰 시퀀스로 변환됩니다.

C. 디코딩 (Decoding)

학습된 BPE 규칙과 역직렬화 함수를 사용하여 토큰 시퀀스를 원래 그래프 (동형까지) 로 복원할 수 있어, 완전한 가역성을 보장합니다.

3. 주요 기여 (Key Contributions)

1. 범용 그래프 토크나이저 프레임워크: 그래프 구조 인코딩과 모델 아키텍처를 분리하여, 아키텍처 수정 없이도 표준 Transformer (예: BERT, GTE) 를 그래프 데이터에 직접 적용할 수 있게 합니다.
2. 구조 유도 직렬화 (Structure-Guided Serialization): 그래프의 순열 불변성 문제를 해결하고, 빈번한 하위 구조가 BPE 에 의해 의미 있는 토큰으로 학습되도록 유도하는 결정론적 직렬화 알고리즘을 제안했습니다.
3. SOTA 성능 달성: 14 개의 다양한 벤치마크 (분자 그래프, 사회 네트워크, 생물학적 그래프 등) 에서 그래프 분류 및 회귀 태스크에 대해 기존 GNN 과 전문 Graph Transformer 를 능가하는 State-of-the-Art (SOTA) 성능을 달성했습니다.

4. 실험 결과 (Results)

• 성능: 14 개 벤치마크 데이터셋 (MolHIV, ZINC, QM9, COIL-DEL 등) 에서 제안된 방법 (GT+GTE) 은 GCN, GIN, GraphGPS, GraphMamba 등 기존 최첨단 모델들을 압도했습니다. 특히 MolHIV 에서 ROC-AUC 0.876 을 기록하여 기존 리더보드 기록을 크게 상회했습니다.
• 효율성:
  • BPE 를 적용함으로써 시퀀스 길이가 원래 직렬화 길이의 약 10% 수준으로 압축되었습니다 (약 10 배 압축).
  • 이로 인해 Transformer 의 계산 복잡도가 감소하여, 전용 Graph Transformer 나 GNN 보다 학습 속도가 크게 향상되었습니다 (예: ZINC 데이터셋에서 약 2.5 배 속도 향상).
• 해석 가능성: 학습된 BPE 어휘를 분석한 결과, 단순 원자 토큰이 아닌 기능기 (Functional Groups) 나 고리 구조와 같은 의미 있는 화학적 하위 구조들이 토큰으로 자동 발견되어 계층적 어휘를 형성함을 확인했습니다.
• 생성 능력: 디코더 전용 Transformer (GPT 스타일) 를 사용하여 그래프를autoregressive 방식으로 생성하는 실험 (MNIST 그리드 그래프) 을 통해, 제안된 토크나이저가 그래프 생성 태스크에도 유효함을 증명했습니다.

5. 의의 및 결론 (Significance)

이 연구는 그래프 구조 데이터와 시퀀스 모델 생태계 사이의 간극을 해소하는 중요한 이정표입니다.

• 아키텍처의 해체: 그래프 학습을 별도의 복잡한 GNN 설계가 아닌, 시퀀스 모델링 문제로 재정의함으로써, Transformer 의 빠른 발전 (더 긴 컨텍스트 윈도우, 효율적인 어텐션 메커니즘 등) 을 그래프 학습 분야로 직접 이전할 수 있는 길을 열었습니다.
• 범용성: 그래프 전용 모델이 아닌 오프더셸 (Off-the-shelf) Transformer 를 사용하여 SOTA 성능을 달성함으로써, 그래프 기반 Foundation Model 의 개발에 새로운 패러다임을 제시합니다.
• 미래 전망: 대규모 그래프 코퍼스를 통한 사전 학습 (Pre-training) 을 통해 도메인 간 일반화 (Cross-domain Generalization) 가 가능한 진정한 그래프 Foundation Model 의 가능성을 제시합니다.

요약하자면, 이 논문은 그래프를 "언어"처럼 토큰화하여 Transformer 이 자연스럽게 처리할 수 있게 함으로써, 그래프 학습의 성능과 효율성을 획기적으로 개선한 획기적인 방법론을 제시했습니다.