Agentic Graph Token Reasoning

기술 요약: 에이전틱 그래프 토큰 추론 (Agentic Graph Token Reasoning)

1. 문제 정의

그래프는 과학 및 산업 분야에서 보편적으로 존재하며, 노드에 풍부한 텍스트 속성(예: 논문 초록, 제품 설명, 단백질 주석)을 포함하는 경우가 많습니다. 대규모 언어 모델(LLM)은 이러한 텍스트 속성 그래프를 분석하는 데 유망한 가능성을 보여주었으나, 근본적인 불일치가 존재합니다: LLM은 언어로 학습되는 반면, 그래프 데이터는 구조적이라는 점입니다.

기존의 솔루션들은 그래프 인코더가 특정 "관점"(예: 노드의 $k$-hop 이웃)을 고정된 길이의 연속적 토큰 블록으로 압축하는 **그래프 토큰(graph tokens)**을 사용하여 이 간극을 메우려 시도합니다. 그러나 현재의 방식들은 **정적이고 단발적인 패러다임(static, single-shot paradigm)**이라는 한계를 가집니다:

• 사전 정의된 관점: 모델이 질문을 접하기 전에 그래프의 관점이 미리 결정됩니다 (예: 항상 2-hop 이웃을 인코딩).
• 수정 불가: 한 번 인코딩된 토큰은 추론 과정 중에도 결코 수정되지 않습니다.
• 비효율성: 이 방식은 "일률적인(one-size-fits-all)" 증거 수집 전략을 강요합니다. 쉬운 사례에는 불필요한 데이터가 과도하게 포함될 수 있고, 어려운 사례에는 충분한 증거가 부족할 수 있는데, 이는 모델이 중간 추론 단계에 따라 구체적인 구조적 정보를 요청할 수 없기 때문입니다.

핵심 과제는 LLM이 **단계별 에이전틱 추론(step-by-step agentic reasoning)**을 수행하도록 하는 것입니다. 즉, 증거 수집(그래프 토큰화)이 동적이고, 궤적에 의존하며, 모델 스스로의 필요에 의해 주도되도록 만드는 것입니다.

2. 방법론: 에이전틱 그래프 토큰 (AGT) 추론

저자들은 에이전틱 그래프 토큰(Agentic Graph Token, AGT) 추론을 제안하며, 이는 그래프 토큰화를 전처리 단계에서 추론 루프의 필수적인 부분으로 재구성합니다.

AGT 프레임워크

모델은 단일 순방향 패스(forward pass) 대신 다단계 루프로 작동합니다:

1. 컨텍스트 초기화: 모델은 그래프 $G$와 질문 $Q$로 시작합니다.
2. 액션 방출: 각 단계 $t$에서 모델은 사전 정의된 액션 공간(예: one_hop_token, cluster_token, retrieval_token)으로부터 이산적인 액션(action) $a_t$를 방출합니다. 이 액션은 그래프 관점 $GV_t$(예: 특정 노드의 3-hop 이웃)를 지정합니다.
3. 온디맨드 인코딩: 그래프 신경망(GNN) 인코더 $f_{GNN}$이 선택된 관점 $GV_t$를 고정된 크기의 소프트 토큰 블록 $Z^{AGT}_t$로 인코딩하도록 온디맨드(on demand) 방식으로 호출됩니다.
4. 컨텍스트 결합: 생성된 토큰 블록은 실행 중인 컨텍스트 $\tau_t$에 삽ale(splice)됩니다.
5. 반복: 모델은 업데이트된 컨텍스트(새로운 그래프 토큰 포함)를 읽고 다음 액션을 결정합니다. 이 과정은 종료 액션인 answer가 방출될 때까지 계속됩니다.

결정적으로, 모델이 읽는 그래프 토큰은 **궤적 의존적(trajectory-dependent)**입니다. 모델은 지금까지 수집된 증거를 바탕으로 무엇을 인코딩할지, 그리고 언제 할지를 스스로 결정합니다.

3단계 학습 파이프라인

이러한 행동을 이끌어내는 것은 쉽지 않습니다. 모델은 텍스트를 선호하여 그래프 토큰을 무시하는 경향이 있기 때문입니다. 저자들은 다음과 같은 3단계 학습 파이프라인을 사용합니다:

• 1단계: 자기 지도 학습 기반 읽기 (Grounding)

  • 목표: 자연어가 포함되지 않은 그래프 토큰 블록을 LLM이 해석하도록 가르칩니다.
  • 태스크:
    1. 텍스트 재구성: 노드의 토큰 블록이 주어졌을 때, 해당 노드의 제목과 초록을 재구성합니다.
    2. 마스크된 링크 예측: 노드의 토큰 블록과 후보 이웃이 주어졌을 때, 엣지가 존재하는지 예측합니다.
  • 결과: GNN 인코더의 출력 공간을 LLM의 임베딩 공간과 정렬하여, 모델이 토큰을 의미 있는 증거로 취급하도록 보장합니다.

• 2단계: 토큰 강건 궤적 SFT (Token-Robust Trajectory SFT)

  • 목표: 모델이 액션을 방출하고 일련의 토큰을 바탕으로 추론하도록 가르치는 동시에, 취약한 표면적 단서에 과도하게 의존하는 것을 방지합니다.
  • 메커니즘:
    1. 웜업(Warm-up): 합성된 궤적(액션 시퀀스 + 정답)에 대한 표준 지도 미세 조정(SFT)을 수행합니다.
    2. 일관성 정규화(Consistency Regularization): 모델을 두 가지 인코딩 쌍으로 학습시킵니다: "깨끗한" 관점과 "증강된" 관점(엣지가 누락되거나 토큰이 마스킹된 경우). KL 발산 손실을 통해 모델이 이러한 섭동(perturbation)에도 불구하고 일관된 응답을 생성하도록 강제합니다.
  • 결과: 모델이 표면적인 패턴이 아닌 그래프 토큰의 내용에 의존하도록 학습되어, 노이즈에 강건한 추론을 수행하게 됩니다.

• 3단계: 그래프-텍스트 일관성 선호 최적화 (IPO)

  • 목표: 모델이 (오해의 소지가 있을 수 있는) 노드의 텍스트에만 의존하지 않고, 그래프 구조에 기반하여 예측하도록 유도합니다.
  • 메커니즘: 다음과 같은 선호 쌍을 구성합니다:
    • 선호되는 경우 ($\tau^+$): 그래프 토큰과 노드 텍스트가 일치하여 정답으로 이어지는 궤적.
    • 선호되지 않는 경우 ($\tau^-$): 노드 텍스트가 다른 노드의 텍스트로 교체되어 그래프 토큰과 불일치하게 되어 오답으로 이어지는 궤적.
  • 최적화: 일관된 궤적의 확률을 불일한 궤적보다 높이기 위해 Identity Preference Optimization (IPO)를 사용합니다.
  • 결과: 모델은 텍스트와 충돌할 때 그래프 증거를 신뢰하도록 정책을 학습하며, 이를 통해 "텍스트 지름길(text shortcut)" 현상을 효과적으로 제거합니다.

3. 주요 기여

1. 에이전틱 그래프 토큰 프레임워크: 그래프 토큰화를 모델이 필요에 따라(단일 노드부터 클러스터까지) 동적으로 선택할 수 있도록 하여, 그래프 토큰화를 추론 루프에 직접 통합한 최초의 프레임워크입니다.
2. 3단계 학습 레시피: 자기 지도 학습 기반의 그라운딩, 일관성 정규화를 포함한 토큰 강건 궤적 SFT, 그리고 그래프-텍스트 선호 최적화로 구성된 새로운 파이프라인을 제시합니다.
3. 실험적 우위: 인용, 이커머스, 소셜 네트워크, 단백질 네트워크 등 7개 그래프 도메인에서 노드 분류 및 링크 예측 모두에 대해 기존의 정적 그래프 토큰 방식 및 텍스트 기반 에이전트 베이스라인을 능가하는 최첨단(SOTA) 성능을 입증했습니다.

4. 실험 결과

모델은 Qwen2.5-3B 및 7B 백본을 사용하여 10개의 텍스트 속성 그래프(예: OGBN-Arxiv, OGBN-Products, PubMed, STRING-db)에서 평가되었습니다.

• 도메인 내 성능: AGT 모델(3B)은 OGBN-Arxiv 노드 분류에서 **73.0%**의 정확도를 달eli(달성)하여, 강력한 AgentGL-3B 베이스라인(63.9%)보다 9.1포인트 높은 성능을 보였습니다. 또한 노드 분류에서 7개 도메인 중 6개에서, 링크 예측에서 6개 도메인에서 1위를 차지했습니다.
• 제로샷 전이(Zero-Shot Transfer): OGBN-Arxiv로만 학습된 모델을 미세 조정 없이 7개의 미학습 도메인에 테스트했습니다. 그 결과, 모든 베이스라인(예: PubMed에서 AgentGL은 39.8%인 반면 AGT는 82.0%)을 크게 앞질러 강력한 일반화 능력을 보여주었습니다.
• 절제 연구(Ablation Studies):
  • 일관성 정규화(2단계)를 제거했을 때 가장 큰 성능 저하가 발생했으며, 이는 강건한 토큰 읽기의 필요성을 확인시켜 줍니다.
  • 특정 액션(예: 이웃 토큰)을 제거하면 성능이 저하되어, 동적 액션 공간의 가치를 입증했습니다.
  • 매체 비교: 동일한 에이전틱 루프를 유지하면서 그래프 토큰을 언어화된 텍스트로 대체했을 때 제로샷 정확도가 29.3% 하락했습니다. 이는 에이전틱 루프뿐만 아니라 그래프 토큰 매체 자체가 텍스트 직렬화 과정에서 손실되는 압축된 구조적 신호를 보존함으로써 성능 향상의 핵심 동력임을 확인시켜 줍니다.
• 오류 분석: 모델은 텍스트만으로는 모호한 도전적인 저차수(low-degree) 노드에서 오류율을 크게 줄였으며, 이는 에이전틱 접근 방식이 누락된 구조적 증거를 효과적으로 수집함을 보여줍니다.

5. 의의 및 주장

본 논문은 LLM 기반의 그래프 분석을 정적, 단발적 패러다임에서 그래프 네이티브 에이전트 패러다임으로 진화시킨다고 주장합니다.

• 패러다임 전환: 그래프 토큰을 고정된 입력 패턴으로 취급하는 기존 방식과 달리, AGT는 모델이 추론 중에 호출하는 도구로 취급합니다. 이를 통해 모델은 특정 인스턴스의 난이도에 따라 증거(예: 노드의 텍스트 확인, 그 후 이웃 확인, 그 후 커뮤니티 확인)를 적응적으로 수집할 수 있습니다.
• 효율성 및 효과성: 텍스트 기반 에이전트가 겪는 컨텍스트 팽창 문제와 비교하여, 제한된 토큰 소비(액션당 고정 크기 블록)로 높은 정확도를 달성합니다.
• 그라운딩(Grounding): 학습 파이프라인은 모델이 그래프 구조와 텍스트 사이의 일관성에 기반하여 결정을 내리도록 명시적으로 강제하며, 이를 통해 잠재적으로 오해의 소지가 있는 노드 속성에만 의頼(의존)하는 것을 방지합니다.

요약하자면, 본 연구는 그래프 토큰을 수동적으로 받는 것이 아니라, LLM이 동적으로 "요청하고" "읽을" 수 있게 함으로써 그래프 구조 데이터에 대한 탁월한 추론 능력을 끌어낼 수 있음을 입증합니다.