지식 그래프 (Knowledge Graphs, KGs)는 관계형 지식에 대한 풍부한 표현을 제공하지만, 그 불규칙한 구조로 인해 검색이 어렵습니다. 즉, 에고 그래프 (ego-graph) 확장이 급격히 증가하며, 밀집 임베딩 (dense embedding) 방식은 멀티홉 구성 쿼리 (multi-hop compositional queries) 처리에 어려움을 겪습니다. 기존의 에이전트 기반 그래프 탐색 방식은 표현력은 뛰어나지만, 대규모 검색을 수행하기에는 비용이 너무 많이 드는 경우가 많습니다. 우리는 반복적이고 저비용인 확장을 통해 지식 그래프 (KG) 구조를 명시적으로 활용하는 검색 프레임워크인 SeedER (Seed-and-Expand Retrieval)를 소개합니다. SeedER는 먼저 경량화된 밀집 검색 (dense retrieval) 및 엔티티 기반 검색 (entity-based retrieval)을 사용하여 핵심 노드의 소규모 집합을 시드 (seed)로 설정한 다음, 강화학습 (reinforcement learning)으로 학습된 그래프 인식 정책 (graph-aware policy)을 통해 이 집합을 선택적으로 확장합니다. 이러한 설계는 전역적 추론 (global reasoning)을 재사용 가능한 지역적 결정 (local decisions)으로 분해하여, 확장 비용을 엄격하게 제어하면서도 쿼리와 관련된 노드를 효율적으로 발견할 수 있게 합니다. 우리는 구성적 그래프 쿼리 (compositional graph queries)에 대한 밀집 검색 (dense retrieval)의 이론적 한계를 보여주며, 구성적 일반화 (compositional generalization) 및 그래프 제약 하의 서브모듈러 최적화 (graph-constrained submodular optimization) 관점 모두에서 SeedER의 이점을 입증합니다. 실험적으로 SeedER는 강력한 밀집 검색 및 그래프 증강 (graph-augmented) 베이스라인 모델들과 비교하여 소규모 후보 집합만으로도 재현율 (recall)을 실질적으로 향상시켰으며, 이를 통해 지식 집약적 추론 시스템을 위한 효과적인 1단계 검색기 (first-stage retriever)임을 증명했습니다.