SeedER: 효율적인 지식 그래프 검색을 위한 시드-확장-검색 기법
SeedER: Seed-Expand-Retrieve for Efficient Knowledge Graph Retrieval
한국어 초록
지식 그래프(KG)는 관계형 지식을 풍부하게 표현하지만, 불규칙한 구조로 인해 검색에 어려움이 따릅니다. 에고 그래프(ego-graph) 확장은 급격히 증가하며, 조밀한 임베딩(dense embedding) 방식은 다중 홉(multi-hop) 합성 쿼리 처리에 한계를 보입니다. 여러 접근 방식에서는 대규모 언어 모델(LLM) 에이전트를 활용해 KG를 탐색하고 후보 노드를 분석하여 다음 탐색 위치를 결정합니다. 이러한 접근법은 표현력이 뛰어나지만 상당한 계산 및 메모리 비용을 초래할 수 있습니다. 반면, 본 연구에서는 구조를 보강하고 이웃 인지 특성을 반영하더라도 그래프 노드에 대해 사전 계산된 조밀한 임베딩이 일련의 지식 그래프 쿼리에 답하기 위해 그래프 크기에 필적하는 임베딩 차원을 요구할 수 있음을 이론적으로 보입니다. 이러한 한계는 특정 조건에서 쿼리 적응형 임베딩을 통해 극복할 수 있으며, 이를 수행할 수 있는 그래프 신경망(GNN) 변형들이 존재합니다. 그러나 GNN으로 전체 그래프를 처리하는 것 역시 상당한 메모리와 계산 비용을 발생시킬 수 있으며, 각 노드가 쿼리에 답하는지 여부를 나타내는 조밀한 정답 라벨이 필요합니다. 앵커 노드 주변의 단순한 $k$-홉 선택 또한 문제가 될 수 있습니다. 작은 $k$는 탐색 가능한 노드를 제한하며, 3이나 4와 같은 작은 $k$ 값에서도 $k$-홉 서브그래프는 크게 증가할 수 있습니다. 본 연구에서는 메모리와 계산 부담이 훨씬 적고, 1단계 검색기(first-stage retriever)로서 추론 시 CPU에서 실행 가능하며, 학습 중 한 번에 소수의 노드에 대한 피드백만 필요로 하는 그래프 트랜스포머(Graph Transformer) 및 강화학습 기반의 새로운 접근 방식을 고안합니다. 우리는 이 방식이 KG에서 정보를 검색하기 위해 LLM을 파인튜닝하는 방식들과 견줄 만한 성능을 보임을 입증합니다. 본 연구의 방법을 SeedER(Seed-Expand-Retrieve)이라 부르며, 적은 계산 자원으로도 실행 가능한 1단계 검색기로 주로 활용될 수 있도록 자리매김합니다.
원문 초록
Knowledge graphs (KGs) offer a rich representation for relational knowledge, but their irregular structure makes retrieval challenging: ego-graph expansion grows rapidly, and dense embedding methods struggle with multi-hop compositional queries. Several approaches use LLM agents to explore the KG, analyze candidate nodes, and decide where to explore next. While expressive, these approaches can incur substantial computational and memory costs. On the other hand, we show theoretically that dense embeddings precomputed for graph nodes, even with augmented structure and neighborhood-aware features, can require embedding dimensions comparable to the size of the graph to answer families of knowledge graph queries. This limitation can be overcome with query-adaptive embeddings under certain conditions, and there are graph neural network (GNN) variants that can do so. However, processing the whole graph with a GNN can also incur substantial memory and computational costs, and it requires dense ground-truth labels indicating whether each node answers the query. Straightforward $k$-hop selection around anchor nodes can also be problematic: small $k$ limits the nodes we can see, and even with small $k$ values such as three and four, the $k$-hop subgraph can grow substantially. In this work, we devise a new approach using Graph Transformers and reinforcement learning that is much less demanding in memory and computation, can run on a CPU at inference time as a first-stage retriever, and requires feedback on only a small number of nodes at a time during training. We show that this method is competitive with methods that fine-tune LLMs to retrieve information from KGs. We call our method SeedER (Seed-Expand-Retrieve), and position it primarily as a first-stage retriever that can run with modest computational resources.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
FFM-CP: 퓨샷 계산병리학을 위한 비전-언어 기반 모델의 교차 백본 융합
FFM-CP: Cross-Backbone Fusion of Vision-Language Foundation Models for Few-Shot Computational Pathology
병리학 비전-언어 기반 모델은 질환과 과제에 따라 성능이 달라지며, 어떤 단일 모델도 일관되게 최고 성능을 내지 못한다. 전문가 병리 주석의 높은 비용은 과제별 적응에 사용할 수 있는 라벨 데이터를 제한하기도 한다. 상호 보완적인 사전학습 표현을 결합하는 것은 이러한 한계에 대한 잠재적 접근이지만, 소수의 라벨 예시로부터 효과적인 융합을 학습하는 것은 여전히 어렵다. 본 연구는 퓨샷 학습 설정에서 여러 병리학 비전-언어 모델을 결합하는 프레임워크인 Few-shot Fusion Foundation Models of Computational Pathology(FFM-CP)를 제안한다. 이 프레임워크는 먼저 대응하는 서포트 이미지로부터 추정한 폐형식(closed-form) 직교 프로크루스테스(Orthogonal Procrustes) 변환을 사용하여 이질적인 표현을 정렬한다. 이 정렬은 추가 정렬 네트워크를 학습하지 않고도 모델 내부 특징 기하를 보존한다. 정렬된 공간 안에서 통합 그래프는 서포트 이미지 특징과 시각·텍스트 클래스 프로토타입을 공동으로 정제함으로써 백본 간 정보 교환을 가능하게 한다. 이렇게 정제된 표현은 의미적 클래스 지식과 클래스 내 시각적 변이를 각각 포착하는 상호 보완적인 텍스트-프로토타입 분기와 케이스 검색(case-retrieval) 분기를 지원한다. 각 분기는 모든 순서화된 백본 쌍의 예측을 결합하는 방법을 학습하여, 한 모델로 인코딩된 쿼리가 다른 모델이 표현한 증거를 활용할 수 있게 한다. 우리는 6개의 조직병리학 데이터셋에서 클래스당 4, 8, 16샷 조건으로 3가지 백본 조합을 평가했다. FFM-CP는 54번 비교 중 50번에서 각 융합 집합의 개별 적응 멤버 중 가장 강한 모델보다 더 높은 평균 macro-F1을 달성했다. 이러한 결과는 주석이 제한될 때 상호 보완적인 사전학습 표현의 결합이 조직병리학 분류를 개선할 수 있음을 시사한다.
OmniSeek: 다중 턴 시청각 추론을 위한 네이티브 도구 통합
OmniSeek: Native Tool Integration for Multi-turn Audio-Visual Reasoning
본 논문에서는 옴니 대규모 언어 모델(Omni-LLM)을 네이티브 도구 사용 능력을 갖춘 능동적인 다중 턴(multi-turn) 추론 에이전트로 변환하는 에이전트 프레임워크인 OmniSeek을 제시합니다. 전체 시청각 시퀀스를 단일 순전파(forward pass)로 수동 처리하는 대신, OmniSeek은 증거 획득을 추론 과정의 일부로 만듭니다. 즉, 긴 컨텍스트 내에서 서로 다른 모달리티 전반의 희소하지만 결정적인 증거를 검색하기 위해 보거나 들을지 여부와 그 시간 윈도우를 동적으로 결정합니다. 반복적인 다중 턴 프로토콜을 통해 검색된 원시 오디오 또는 시각 세그먼트는 후속 추론을 지원하기 위해 컨텍스트에 다시 추가됩니다. 이러한 능력을 콜드 스타트하기 위해, 오디오 및 시각 증거가 인터리빙된 다중 홉 사고의 연쇄(Chain-of-Thought) 궤적 말뭉치인 OmniTraj-170K를 합성하는 데이터 엔진을 구축합니다. 먼저 이러한 궤적을 기반으로 모델을 지도 학습하여 다중 턴 도구 사용 행동을 주입한 다음, 검증 가능한 보상을 활용한 2단계 강화학습을 통해 정책을 추가로 최적화합니다. 또한, 두 모달리티 모두에 의존하는 성공적인 추론 궤적에 명시적으로 보상을 제공하여 단일 모달리티 지름길을 억제하는 시청각 필수성(Audio-Visual Necessity) 목표를 도입합니다. 광범위한 벤치마크에 걸친 광범위한 실험을 통해 OmniSeek이 적응형 교차 모달 증거 탐색을 학습하고 시청각 추론 성능을 일관되게 향상시킴을 입증합니다.
액추에이터 성능 저하 상황에서의 4족 보행 강화학습을 위한 고차 형태학적 프라이어
Higher-Order Morphology Priors for Quadruped Reinforcement Learning Under Actuator Degradation
액추에이터 성능 저하는 4족 보행을 관절들이 손실된 액추에이션을 보상해야 하는 협응(coordination) 문제로 만든다. 선행 연구들은 형태학을 인식하는 그래프 정책(morphology-aware graph policy)이 신체 교란(body perturbation) 상황에서 학습과 일반화를 향상시킨다고 제안한다. 본 연구는 고차(higher-order) 기계적 구조를 명시적으로 모델링함으로써 이러한 이점을 강화할 수 있는지를 묻는다. 우리는 Unitree Go1을 다리(limb) 및 몸체(body) 수준의 랭크-2 셀(rank-2 cell)을 갖는 셀 복합체(cell complex)로 표현하고, Hodge 기반 메시지 패싱(Hodge-based message passing)을 적용한다. 저하 상황에서의 학습 하에서, 노드-엣지-면 Hodge 액터(node-edge-face Hodge actor)는 보지 못한 액추에이터 저하에 대해 가장 높은 리턴(return)을 달성하며, 더 높은 생존율과 더 낮은 속도 추적 오차(velocity-tracking error)를 보인다. 이러한 결과는 고차 형태학이 액추에이터 저하 상황에서 전신 보상(whole-body compensation)을 위한 유용한 귀납적 바이어스(inductive bias)임을 뒷받침한다.
TAGGRAPH: 에이전트 지속 이력의 그래프 검색을 위한 태그 증강 그래프
TAGGRAPH: Tag-Augmented Graphs for Graph Retrieval of Agent Persistent Histories
장기 기억은 대규모 언어 모델(LLM) 에이전트(agent)가 과거의 상호작용을 기억하고 세션 전반에서 일관성을 유지할 수 있게 해 주지만, 메모리 시스템은 표현, 인덱싱, 검색, 평가 방식이 서로 달라 비교하기가 어렵습니다. 본 논문에서는 공유된 5W(육하원칙) 스타일의 대화형 메모리를 기반으로 하는 통제된 평가 프레임워크를 제시합니다. 국소적 그래프 구성은 공통의 기본 그래프를 순회하며, AdaptiveGraph는 시간순 엣지와 개인화된 페이지랭크(Personalized PageRank) 확산을 추가합니다. 또한 동일하게 추출된 노트에 대한 BM25와 원시 입력을 사용하는 외부 기준선인 OpenClaw를 평가합니다. 검색 순위는 메모리 설정에 따라 달라집니다. LongMemEval-S에서 AdaptiveGraph는 MRR 0.844로 가장 우수한 그래프 구성을 보였으나, BM25는 0.867, OpenClaw는 0.880에 달했습니다. ATANT Core에서는 국소적 그래프 순회가 확산 및 BM25보다 우수한 성능을 보인 반면, 스트레스 라운드에서는 BM25가 앞섰습니다. 테스트된 범위 내에서 LongMemEval-S의 크기를 줄여도 ATANT 확산 패널티가 재현되지 않았으나, 테스트된 가장 작은 저장소도 ATANT Core보다 여전히 컸기 때문에 저장소 크기 영향을 배제할 수 없습니다. 이 패널티는 관대한 콘텐츠 일치 기준 하에서도 지속되었습니다. 어휘 정규화(normalization)와 추출 품질은 그래프 검색에 실질적인 영향을 미치며, 상위 5위권 실패 사례에서는 추출 태그 누락이 흔하게 나타났습니다. 따라서 검색 전략은 메모리 설정과 함께, 그리고 강력한 어휘 기반 기준선과 대조하여 공동으로 평가되어야 합니다.
실패로부터의 학습: 소형 언어 모델 도구 사용 에이전트를 위한 이종 그래프 메모리
Learning from Failures: Heterogeneous Graph Memory for Small Language Model Tool-Using Agents
중소형 언어 모델(language model)은 도구 사용 에이전트(agent)를 위한 비용 효율적인 실행자 역할을 하여 로컬 및 대규모 배포에 매력적인 선택지입니다. 그러나 장기적(long-horizon)이고 상태를 유지하는(stateful) 환경에서 이러한 모델(model)들은 필수적인 관측 누락, 조기 쓰기 수행, 실패한 호출 반복, 행동 전제 조건 위반과 같은 구조적 오류를 자주 범합니다. 이러한 오류는 잘못된 상태 업데이트, 정책 위반, 그리고 많은 비용이 들거나 되돌릴 수 없는 결과로 이어질 수 있어, 신뢰할 수 있는 도구 실행이 핵심적인 배포 과제가 됩니다. 기존의 미세조정(fine-tuning) 접근 방식은 상당한 양의 데이터와 연산을 필요로 하며, 평면적 메모리(flat memory)는 인과적 맥락이나 안전성(safety) 조건을 보존하지 못한 채 실패한 행동을 검색할 수 있습니다. 본 논문에서는 과거의 성공과 실패를 도구 사용 에이전트를 위한 구조화된 외부 경험으로 변환하는, 경험 구조화 이종 그래프 기반 실패 인지 검색 프레임워크인 FRESH(Failure-aware Retrieval framework over Experience-Structured Heterogeneous graphs)를 제안합니다. FRESH는 태스크, 행동, 오류, 복구, 실행 조건 간의 의존성을 명시적으로 모델링함으로써, 동결된(frozen) 언어 모델이 신뢰할 수 있는 전략을 재사용하고, 반복되는 실패를 방지하며, 상태 기반 도구 상호작용에서 더 안전한 결정을 내릴 수 있도록 돕습니다. 여러 오픈소스 모델을 사용해 $\tau$-Bench 및 AppWorld에서 수행한 실험에 따르면, FRESH는 메모리가 없는 에이전트 및 대표적인 메모리 기반 베이스라인 대비 태스크 성공률과 도구 사용 신뢰성을 일관되게 향상시킵니다.
잡 샵 스케줄링을 위한 GNN 기반 강화학습에서의 커리큘럼 러닝
Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling
잡 샵 스케줄링 문제(job shop scheduling problem)는 까다로운 조합 최적화(combinatorial optimization) 문제이며, 최근 그래프 신경망(GNN)을 활용한 강화학습(RL) 접근법은 문제 인스턴스로부터 스케줄링 정책을 직접 학습하는 데 유망함을 보여주었다. 그러나 대규모 인스턴스에 대한 학습은 여전히 연산 비용이 많이 들고, 다양한 인스턴스 크기에 걸친 일반화는 여전히 어려운 과제로 남아 있다. 본 논문에서는 잡 샵 스케줄링 문제에서 그래프 신경망 기반 강화학습을 위한 커리큘럼 러닝(curriculum learning)을 연구하며, 세 가지 타깃 크기인 20 x 20, 25 x 25, 30 x 30에 대해 단일 크기 학습(single-size training)과 비교한다. 커리큘럼 환경에서는 정책을 먼저 더 작은 인스턴스에서 학습시킨 후 점진적으로 더 큰 타깃 크기에 적응시켜, 초기 단계에서 학습된 스케줄링 동작이 더 큰 인스턴스에서의 학습을 뒷받침하도록 한다. 모델은 모든 평가 크기에 걸친 일반화와 타깃 크기에 대한 특화(specialization)를 모두 고려하여, 최적성 갭(optimality gap)을 사용해 8 x 8부터 30 x 30까지의 미확인(unseen) 인스턴스에서 평가된다. 실험 결과에 따르면 커리큘럼 러닝은 실제 학습 소요 시간(wall-clock training time)을 일관되게 단축하며, 타깃 크기가 커질수록 그 이점이 더 커지는 것으로 나타났다. 가장 강력한 이점은 30 x 30에서 관찰되었는데, 커리큘럼 러닝은 모든 평가 크기에 걸친 평균 최적성 갭을 약 8.1%포인트 줄이고, 타깃 크기의 평균 최적성 갭을 약 8.6%포인트 줄였으며, 학습 시간을 약 50시간 절약했다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.