1. 문제 정의 (Problem Statement)

기존 LLM 기반 에이전트 프레임워크 (RAG 등) 는 주로 비정형 텍스트에 의존하여 정보를 검색하고 추론합니다. 그러나 실제 세계의 많은 데이터 (논문 인용 네트워크, 소셜 플랫폼, 상업 생태계 등) 는 텍스트 속성 그래프 (Text-Attributed Graph, TAG) 형태로 존재하며, 의미는 텍스트 내용과 그래프 위상 (연결 구조) 의 상호작용에서 파생됩니다.

기존 접근법의 주요 한계는 다음과 같습니다:

• 정적 컨텍스트 의존성: 기존 GraphLLM 은 추론 시점에 그래프 정보를 한 번만 추출하여 고정된 컨텍스트로 사용합니다. 이는 적응형 탐색을 방해합니다.
• 구조적 의존성 무시: 기존 에이전트 검색은 어휘적 유사성 (lexical similarity) 에만 의존하여 그래프의 구조적 연결고리를 활용하지 못합니다.
• 복잡한 탐색 공간: 그래프에서 증거를 수집하는 것은 국소적 (local) 인 이웃과 전역적 (global) 인 패턴을 모두 고려해야 하는 조합적 공간 탐색 문제로, 불필요한 검색을 피하면서 최적의 경로를 찾는 것이 어렵습니다.

이에 본 논문은 AGL을 새로운 패러다임으로 제시하며, LLM 에이전트가 그래프를 자율적으로 탐색하고, 구조적 증거를 축적하며, 실시간 추론을 기반으로 탐색 경로를 정제하는 과정을 목표로 합니다.

2. 방법론 (Methodology)

AgentGL 은 강화학습 (RL) 을 기반으로 한 두 단계의 훈련 전략과 그래프 네이티브 도구를 활용합니다.

2.1 그래프 네이티브 검색 도구 (Graph-Native Search Tools)

에이전트가 그래프 구조를 탐색할 수 있도록 4 가지 핵심 도구를 제공합니다:

1. 1-hop/2-hop 이웃 검색 (Local): 특정 노드의 직접적인 이웃이나 2 단계 이웃을 탐색하여 국소적 위상 의존성을 파악합니다.
2. 구조적 중요도 검색 (Structure Salience Search): 페이지랭크 (PageRank) 점수를 기반으로 전역적으로 중요한 노드를 탐색합니다.
3. 그래프 밀집 검색 (Graph Dense Search): 임베딩 유사도를 기반으로 의미적으로 밀접하게 연결된 노드를 탐색합니다.

2.2 두 단계 강화학습 전략

AgentGL 은 **GNS 정책 부트스트래핑 (Policy Bootstrapping)**과 **검색 과사용 완화 (Mitigating Search Overuse)**의 두 단계를 거칩니다.

• 1 단계: GNS 정책 부트스트래핑 (Bootstrapping)

  • 목적: 에이전트가 그래프 탐색 도구를 효과적으로 사용하는 법을 학습하게 합니다.
  • 방법: 모든 도구를 고르게 사용하도록 유도하는 **커버리지 보상 (Coverage Reward, $r_{COV}$)**을 추가하여 에이전트가 다양한 탐색 전략을 시도하도록 합니다.
  • 알고리즘: GRPO (Group Relative Policy Optimization) 또는 REINFORCE++ 를 사용하여 정책 최적화를 수행합니다.

• 2 단계: 검색 과사용 완화 (Mitigating Search Overuse)

  • 목적: 불필요한 검색을 줄이고 효율성을 극대화합니다.
  • 핵심 기법: 검색 제약 사고 (Search-Constrained Thinking)
    • 후회적 종료 트리거 (Retrospective Termination Trigger): 각 검색 후 "현재 증거가 충분한지 다시 검토하라"는 프롬프트를 삽입하여 에이전트가 검색을 중단할지 결정하도록 유도합니다.
    • 인지 밀도 정규화 (Cognitive Density Regularization): 검색 횟수를 줄이는 대신, 획득한 정보를 깊이 있게 추론하도록 유도합니다. 짧은 추론 블록에 페널티를 부과하여 '적은 검색, 깊은 추론'을 장려합니다.
  • 보상 설계: 검색 커버리지 보상은 제거하고, 정확도 ($r_{ACC}$) 와 추론 밀도 ($r_{depth}$) 보상에 집중합니다.

2.3 그래프 조건부 커리큘럼 학습 (Graph-Conditioned Curriculum Learning, GCCL)

학습의 안정성을 높이기 위해 그래프의 고유한 특성을 활용하여 난이도별 학습 순서를 설계합니다.

• 노드 분류: 국소적 동질성 (homophily) 과 차수 (degree) 를 기반으로 난이도를 산정합니다. (쉬운 노드: 차수가 높고 동질성이 높은 허브 노드 → 어려운 노드: 이질적인 아웃라이어)
• 링크 예측: 노드 간 의미적 유사성과 레이블 일관성을 기반으로 난이도를 설정합니다.
• 효과: 쉬운 샘플부터 어려운 샘플로 점진적으로 학습하여 수렴 속도를 높이고 국소 최적해에 빠지는 것을 방지합니다.

3. 주요 기여 (Key Contributions)

1. AGL 패러다임 제안: 그래프 학습을 '위상 인식 탐색'과 'LLM 추론'이 교차하는 과정으로 재정의하여, 그래프 구조, 텍스트 의미, 에이전트 의사결정을 통합했습니다.
2. 최초의 RL 기반 AgentGL 프레임워크: 구조적 지각, 전략적 추론, 정책 학습을 시너지 있게 결합한 AgentGL 을 제안했습니다. 특히 단계별 보상 설계와 검색 제약 사고 기법을 통해 정확도와 효율성의 균형을 달성했습니다.
3. 성능 입증: 다양한 TAG 벤치마크와 LLM 백본 (Qwen 3B/7B) 에서 기존 GraphLLM 및 GraphRAG 베이스라인을 압도하는 성능을 보였습니다.

4. 실험 결과 (Results)

본 논문은 7 개의 TAG 데이터셋 (OGB-Arxiv, PubMed, Amazon, Reddit 등) 에서 노드 분류 (Node Classification) 와 링크 예측 (Link Prediction) 태스크를 수행하여 AgentGL 의 우수성을 입증했습니다.

• 성능 향상:
  • 노드 분류: 기존 최강 베이스라인 대비 **최대 17.5%**의 절대 정확도 향상.
  • 링크 예측: **최대 28.4%**의 절대 정확도 향상.
  • 제로샷 (Zero-shot) 전이 성능에서도 뛰어난 일반화 능력을 보였습니다.
• 효율성: 2 단계 훈련 전략을 통해 불필요한 검색 횟수를 약 17.5%~22% 감소시키면서도 정확도는 오히려 향상시켰습니다.
• 모델 스케일링: 백본 모델의 크기를 3B 에서 7B 로 확장할 때 성능이 일관되게 향상되었으며, 특히 제로샷 설정에서 큰 모델이 도구 사용 정책을 더 잘 학습함을 확인했습니다.

5. 의의 및 결론 (Significance)

AgentGL 은 LLM 이 정적 지식에 의존하는 것을 넘어, 동적이고 구조화된 환경에서 자율적으로 탐색하고 추론할 수 있는 능력을 부여합니다. 이는 다음과 같은 점에서 중요합니다:

• 구조적 추론의 자동화: 복잡한 관계형 데이터 (예: 학문적 인용, 소셜 네트워크, 추천 시스템) 에서 인간과 유사한 탐색 전략을 학습하여 더 정확한 의사결정을 가능하게 합니다.
• 효율적인 에이전트 설계: "무조건 많이 검색하는 것"이 아니라 "필요한 때에만 검색하고 깊이 추론하는 것"이 중요함을 보여주며, 에이전트 시스템의 비용 효율성을 높이는 새로운 방향을 제시합니다.
• 미래 연구 방향: 텍스트 속성 그래프를 넘어 멀티모달 그래프나 더 밀집된 그래프 구조로 확장할 수 있는 가능성을 열어주며, 에이전트 기반의 복잡한 그래프 추론 연구의 새로운 지평을 열었습니다.

결론적으로, AgentGL 은 LLM 이 그래프 구조를 이해하고 활용하는 방식을 근본적으로 변화시켜, 차세대 지능형 정보 검색 및 추론 시스템의 핵심 기술로 자리매김할 잠재력을 가지고 있습니다.