Principled Graph Matching Algorithms for Integrating Multiple Data Sources
This paper explores combinatorial optimization for problems of max-weight graph matching on multi-partite graphs, which arise in integrating multiple data sources. Entity resolution-the data integration problem of performing noisy joins on structured data-typically proceeds by first hashing each record into zero or more blocks, scoring pairs of records that are co-blocked for similarity, and then matching pairs of sufficient similarity. In the most common case of matching two sources, it is often desirable for the final matching to be one-to-one (a record may be matched with at most one other); members of the database and statistical record linkage communities accomplish such matchings in the final stage by weighted bipartite graph matching on similarity scores. Such matchings are intuitively appealing: they leverage a natural global property of many real-world entity stores-that of being nearly deduped-and are known to provide significant improvements to precision and recall. Unfortunately unlike the bipartite case, exact max-weight matching on multi-partite graphs is known to be NP-hard. Our two-fold algorithmic contributions approximate multi-partite max-weight matching: our first algorithm borrows optimization techniques common to Bayesian probabilistic inference; our second is a greedy approximation algorithm. In addition to a theoretical guarantee on the latter, we present comparisons on a real-world ER problem from Bing significantly larger than typically found in the literature, publication data, and on a series of synthetic problems. Our results quantify significant improvements due to exploiting multiple sources, which are made possible by global one-to-one constraints linking otherwise independent matching sub-problems. We also discover that our algorithms are complementary: one being much more robust under noise, and the other being simple to implement and very fast to run.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationData IntegrationEntity ResolutionGraph MatchingSimilar Papers 제목 키워드 기반
Tensor Power Iteration for Multi-Graph Matching
Due to its wide range of applications, matching between two graphs has been extensively studied and remains an active topic. By contrast, it is still under-exploited on how to jointly match multiple graphs, partly due to…
Graph MatchingConsistent Multiple Graph Matching with Multi-layer Random Walks Synchronization
We address the correspondence search problem among multiple graphs with complex properties while considering the matching consistency. We describe each pair of graphs by combining multiple attributes, then jointly match …
Graph MatchingProvably Efficient Iterated CVaR Reinforcement Learning with Function Approximation and Human Feedback
Risk-sensitive reinforcement learning (RL) aims to optimize policies that balance the expected reward and risk. In this paper, we present a novel risk-sensitive RL framework that employs an Iterated Conditional Value-at-…
Decision MakingLEMMAreinforcement-learningReinforcement Learning (RL)Integrating 2D and 3D Digital Plant Information Towards Automatic Generation of Digital Twins
Ongoing standardization in Industry 4.0 supports tool vendor neutral representations of Piping and Instrumentation diagrams as well as 3D pipe routing. However, a complete digital plant model requires combining these two…
Graph MatchingMap matching when the map is wrong: Efficient vehicle tracking on- and off-road for map learning
Given a sequence of possibly sparse and noisy GPS traces and a map of the road network, map matching algorithms can infer the most accurate trajectory on the road network. However, if the road network is wrong (for examp…