비용 효율적인 개체 해상도(Entity Resolution)를 위한 LLM 기반의 적응형 그래프 정제 및 레이블 전파

단일하고 지저분한 데이터셋에서 동일한 실제 세계의 개체(entity)를 참조하는 레코드를 식별하는 더티 개체 해상도(Dirty Entity Resolution, ER)는 데이터 관리 및 마이닝의 근본적인 작업입니다. 그러나 ER을 위한 지배적인 블로킹-매칭-클러스터링(blocking-matching-clustering) 패러다임은 심각한 결함을 가지고 있습니다. 이들의 계층적이고 분리된 워크플로우는 본질적으로 누락된 에지(blocking 실패로 인한)와 노이즈가 섞인 링크(매칭 오류로 인한)로 인해 발생하는 정적이고 희소한 그래프를 생성하며, 이는 오류 전파를 일으키고 특히 클러스터링에서 엄격한 추이성(transitivity)이 부과될 때 최적화되지 않은 클러스터를 생성하게 만듭니다. 우리는 매칭(matching)과 클러스터링(clustering)이 이상적인 개체 그래프(entity graph) 구축을 위해 모두 최적화되는 근본적으로 시너지 효과를 내는 관계라고 주장합니다. 이러한 통찰을 바탕으로, 우리는 이러한 단계들을 전역적이고 진화하는 그래프 상의 반복적인 확률적 레이블 전파(probabilistic label propagation) 프로세스로 통합하는 단일 프레임워크인 Alper를 제안합니다. 분리된 블로킹(blocking)과 달리, Alper는 그래프 전파로부터 얻은 "약하지만 저렴한" 신호와 LLM 기반의 "강력하지만 비용이 많이 드는" 쌍별 쿼리(pairwise queries)를 적응적으로 통합함으로써 그래프 구조와 레이블을 동적으로 정제합니다. 더 높은 비용 효율성을 위해, 우리는 신호 선택을 쿼리 예산 내에서 누적 한계 이득(cumulative marginal gain)을 최대화하는 제약 조건이 있는 최적화 문제로 공식화하였으며, 이를 이론적 보장이 가능한 탐욕 알고리즘(greedy algorithm)을 통해 해결합니다. 8개의 벤치마크 데이터셋에 대한 광범위한 실험을 통해 Alper가 최신 계층적 파이프라인(cascaded pipelines)보다 일관되게 우수함을 입증하였습니다.