Adaptive Graph Refinement and Label Propagation with LLMs for Cost-Effective Entity Resolution

• URL: http://arxiv.org/abs/2605.25814v1
• Date: Mon, 25 May 2026 13:11:33 GMT
• Title: Adaptive Graph Refinement and Label Propagation with LLMs for Cost-Effective Entity Resolution
• Abstract summary: Dirty entity resolution (ER) identifies records referring to the same real-world entity from a single, messy dataset.<n>We propose Alper, a unified framework that integrates matching and clustering steps into an iterative probabilistic label propagation process.<n>Our experiments over eight benchmark datasets demonstrate that Alper is consistently superior to state-of-the-art cascaded pipelines.
• Score: 16.32872612569802
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dirty entity resolution (ER), which identifies records referring to the same real-world entity from a single, messy dataset, is a fundamental task in data management and mining. However, the dominant blocking-matching-clustering paradigm for ER suffers from critical flaws. Its cascaded, decoupled workflow essentially produces a static, sparse graph plagued by missing edges (due to blocking failures) and noisy links (due to matching errors), causing error propagation and yielding suboptimal clusters, particularly when rigid transitivity is imposed in the clustering. We contend that matching and clustering are fundamentally synergistic, both optimizing for the construction of an ideal entity graph. Building upon this insight, we propose Alper, a unified framework that integrates these steps into an iterative probabilistic label propagation process over a global, evolving graph. Unlike disjoint blocking, Alper refines the graph structure and labels dynamically by adaptively integrating "weak but cheap" signals from graph propagation with "strong but expensive" LLM-based pairwise queries. For higher cost-effectiveness, we formulate the signal selection as a constrained optimization problem maximizing cumulative marginal gain under a query budget, solved via our greedy algorithm with provable theoretical guarantees. Our extensive experiments over eight benchmark datasets demonstrate that Alper is consistently superior to state-of-the-art cascaded pipelines.

Related papers

• FedCIGAR: A Personalized Reconstruction Approach for Federated Graph-level Anomaly Detection [51.473064583839296]
  We propose a novel Federated graph-level anomaly detection approach with Cluster-adaptIve GAted Reconstruction (FedCIGAR)<n>Specifically, we design a reconstruction-based paradigm trained on normal graphs to avoid synthetic data. Furthermore, we introduce a client-side node contribution gating mechanism and a server-side sliding window-based clustering strategy to tackle data heterogeneity.
  arXiv  Detail & Related papers  (2026-05-10T09:03:54Z)
• Beyond Pairs: Your Language Model is Secretly Optimizing a Preference Graph [17.030746750590758]
  We propose a principled generalization of DPO that operates over directed acyclic preference graphs induced by rollout rankings.<n>GraphDPO encodes dominance relations as edges and optimize a graph-structured Plackett--Luce-inspired objective.<n> Experiments on reasoning and program tasks demonstrate superior performance, suggesting that graph-structured preference modeling is a scalable and robust alternative to pairwise and listwise alignment objectives.
  arXiv  Detail & Related papers  (2026-05-08T17:26:14Z)
• HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG [53.30561659838455]
  Large Language Models (LLMs) often struggle with inherent knowledge boundaries and hallucinations.<n>Retrieval-Augmented Generation (RAG) frequently overlooks structural interdependencies essential for multi-hop reasoning.<n>Help achieves competitive performance across multiple simple and multi-hop QA benchmarks and up to a 28.8$times$ speedup over leading Graph-based RAG baselines.
  arXiv  Detail & Related papers  (2026-02-24T14:05:29Z)
• Semi-supervised Instruction Tuning for Large Language Models on Text-Attributed Graphs [62.544129365882014]
  We propose a novel Semi-supervised Instruction Tuning pipeline for Graph Learning, named SIT-Graph.<n> SIT-Graph is model-agnostic and can be seamlessly integrated into any graph instruction tuning method that utilizes LLMs as the predictor.<n>Extensive experiments demonstrate that when incorporated into state-of-the-art graph instruction tuning methods, SIT-Graph significantly enhances their performance on text-attributed graph benchmarks.
  arXiv  Detail & Related papers  (2026-01-19T08:10:53Z)
• Youtu-GraphRAG: Vertically Unified Agents for Graph Retrieval-Augmented Complex Reasoning [32.78218766121055]
  Graph retrieval-augmented generation (GraphRAG) has effectively enhanced large language models in complex reasoning.<n>We propose a vertically unified agentic paradigm, Youtu-GraphRAG, to jointly connect the entire framework as an intricate integration.
  arXiv  Detail & Related papers  (2025-08-27T13:13:20Z)
• Exact and Heuristic Algorithms for Constrained Biclustering [0.0]
  Biclustering, also known as co-clustering or two-way clustering, simultaneously partitions the rows and columns of a data matrix to reveal submatrices with coherent patterns.<n>We study constrained biclustering with pairwise constraints, namely must-link and cannot-link constraints, which specify whether objects should belong to the same or different biclusters.
  arXiv  Detail & Related papers  (2025-08-07T15:29:22Z)
• Graph Structure Refinement with Energy-based Contrastive Learning [56.957793274727514]
  We introduce an unsupervised method based on a joint of generative training and discriminative training to learn graph structure and representation.<n>We propose an Energy-based Contrastive Learning (ECL) guided Graph Structure Refinement (GSR) framework, denoted as ECL-GSR.<n>ECL-GSR achieves faster training with fewer samples and memories against the leading baseline, highlighting its simplicity and efficiency in downstream tasks.
  arXiv  Detail & Related papers  (2024-12-20T04:05:09Z)
• Modularity aided consistent attributed graph clustering via coarsening [6.522020196906943]
  Graph clustering is an important unsupervised learning technique for partitioning graphs with attributes and detecting communities. We propose a loss function incorporating log-determinant, smoothness, and modularity components using a block majorization-minimization technique. Our algorithm seamlessly integrates graph neural networks (GNNs) and variational graph autoencoders (VGAEs) to learn enhanced node features and deliver exceptional clustering performance.
  arXiv  Detail & Related papers  (2024-07-09T10:42:19Z)
• Inaccurate Label Distribution Learning with Dependency Noise [52.08553913094809]
  We introduce the Dependent Noise-based Inaccurate Label Distribution Learning (DN-ILDL) framework to tackle the challenges posed by noise in label distribution learning. We show that DN-ILDL effectively addresses the ILDL problem and outperforms existing LDL methods.
  arXiv  Detail & Related papers  (2024-05-26T07:58:07Z)
• Graph-based hierarchical record clustering for unsupervised entity resolution [0.0]
  We build upon a state-of-the-art probabilistic framework named the Data Washing Machine (DWM) We introduce a graph-based hierarchical 2-step record clustering method (GDWM) that first identifies large, connected components or soft clusters in the matched record pairs. That is followed by breaking down the discovered soft clusters into more precise entity clusters in a hierarchical manner.
  arXiv  Detail & Related papers  (2021-12-12T21:58:07Z)
• Meta Clustering Learning for Large-scale Unsupervised Person Re-identification [124.54749810371986]
  We propose a "small data for big task" paradigm dubbed Meta Clustering Learning (MCL) MCL only pseudo-labels a subset of the entire unlabeled data via clustering to save computing for the first-phase training. Our method significantly saves computational cost while achieving a comparable or even better performance compared to prior works.
  arXiv  Detail & Related papers  (2021-11-19T04:10:18Z)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  We propose a simple yet effective meta-learning algorithm in semi-supervised learning. We find that the proposed algorithm performs favorably against state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-07-08T08:48:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.