PaperlayerView exact revision on arXiv

Source-linked AI summary

Large-Scale Collective Entity Matching

Vibhor Rastogi, Nilesh Dalvi, Minos Garofalakis

arXiv:1103.2410v1cs.DB

TL;DR

Collective entity-matching methods face poor scalability, limiting their use on large datasets. This paper scales generic matchers by running them on small entity neighborhoods and passing messages across runs. Experiments scale a state-of-the-art matcher to real-life datasets with little or no impact on accuracy.

  • Problem

    Collective entity matching methods face poor scalability because probabilistic inference over large entity-matching graphs is computationally infeasible for large datasets.

    Source: §1 · p. 1

  • Method

    The framework models any deterministic or probabilistic entity matcher as a black box, runs instances on small entity neighborhoods, and passes messages across runs.

    Source: §1 · pp. 1–2, §2.2 · p. 2

  • Results

    More than 58,000 references and around 1.3 million matching decisions were handled on real-life datasets with little or no impact on accuracy.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework is described as highly scalable and suitable for parallel implementation through neighborhood-level matcher runs and message passing.

    Source: §1 · p. 2

    The framework has no theoretical guarantees on completeness, though it is empirically complete on the datasets considered.

    Source: §2.2.1 · p. 4

Abstract

from arXiv · show

There have been several recent advancements in Machine Learning community on the Entity Matching (EM) problem. However, their lack of scalability has prevented them from being applied in practical settings on large real-life datasets. Towards this end, we propose a principled framework to scale any generic EM algorithm. Our technique consists of running multiple instances of the EM algorithm on small neighborhoods of the data and passing messages across neighborhoods to construct a global solution. We prove formal properties of our framework and experimentally demonstrate the effectiveness of our approach in scaling EM algorithms.

1. INTRODUCTION

Entity matching asks whether records refer to the same real-world object, but collective methods that use relational evidence are computationally infeasible on large datasets. The paper proposes a message-passing framework for scaling generic matchers and reports scaling an MLN matcher to real-life datasets with little or no accuracy impact.

1. INTRODUCTION

  • Collective EM methods use relational information to make matching decisions together and have been shown to outperform conventional pairwise methods in accuracy.Conventional approaches relied on attribute-similarity measures and ignored relational information.Source: §1 · p. 1
  • Collective EM methods face poor scalability because probabilistic inference over large entity-matching graphs is computationally infeasible on large datasets.Source: §1 · p. 1
  • The framework scales generic EM algorithms by running matcher instances on small entity subsets and passing messages between instances to approximate a run on the full dataset.Matchers are modeled as black boxes that take entities and evidence and return matches.Source: §1 · p. 1
  • The approach is designed to be scalable and parallelizable, and its formal analysis establishes soundness for a broad class of well-behaved matchers.Novel message-passing schemes are proposed for probabilistic matchers to improve recall without compromising soundness.Source: §1 · pp. 1–2
  • The framework scaled a state-of-the-art MLN collective matcher to more than 58,000 references and around 1.3 million matching decisions with little or no impact on accuracy.The experiments used real datasets.Source: §1 · p. 2

2. OVERVIEW

The overview illustrates how collective MLN matching uses relational evidence and motivates a framework that runs matchers on overlapping neighborhoods, then exchanges messages. For well-behaved matchers, both message-passing schemes are sound and consistent, with runtime linear in the number of neighborhoods; completeness is demonstrated empirically on the datasets considered.

2. OVERVIEW

  • The overview presents an MLN matcher as a collective model that uses weighted rules to score sets of possible matches.Rule weights have a probabilistic interpretation, and the matcher seeks the highest-scoring set.Source: §2 · p. 2, §2.1 · p. 2

2.1 The MLN Entity Matcher

  • In the MLN example, matching a pair can remain optimal as more entities are added, a property called monotonicity that the framework is designed to exploit.The matcher also considers collections of pairs whose combined score can increase even when individual pairs do not.Source: §2.1 · p. 2

2.2 Our Framework

  • The framework models a matcher as a black box and runs instances on neighborhoods, subsets in a cover that may group entities by relational closeness as well as similarity.The cover’s neighborhoods may overlap and together include all entities.Source: §2.2 · pp. 2–3
  • MMP combines correlated-match messages from overlapping neighborhoods to recover a chain of matches that neither neighborhood can produce alone.The example’s pairs must all be matched together to increase the overall score.Source: §2.2 · p. 3

2.2.1 Theoretical Properties

  • For a well-behaved entity matcher, both SMP and MMP are sound and consistent, with time complexity linear in the number of neighborhoods.The framework defines scalability assuming bounded neighborhood sizes.Source: §2.2.1 · p. 3
  • The framework has no theoretical completeness guarantee, though it is empirically complete on the datasets considered.Source: §2.2.1 · p. 4

3. BLACK-BOX ABSTRACTION

The framework models matchers as black boxes, with Type-I abstractions covering deterministic matchers and Type-II abstractions adding probabilistic techniques. It uses matcher properties to establish guarantees, including that supermodular Type-II matchers are monotone Type-I matchers.

3. BLACK-BOX ABSTRACTION

  • The framework defines Type-I as its general matcher abstraction and Type-II as a probabilistic specialization that enables additional techniques.A Type-II matcher also satisfies the Type-I idempotence axiom.Source: §3 · p. 4, §3.2 · p. 4

3.1 Type-I Matcher

  • Type-I matchers map entities and positive and negative evidence to matches, while allowing algorithms that ignore evidence to fit the same black-box abstraction.The framework assumes idempotence and monotonicity for its well-behaved matcher guarantees; non-monotone matchers can still be scaled, but without the theoretical soundness guarantee.Source: §3.1 · p. 4

3.2 Type-II Matcher

  • Type-II matchers assign a probability distribution to possible match sets and select a most-probable set, preferring the largest when probabilities tie.Positive and negative evidence can be incorporated by conditioning the distribution.Source: §3.2 · p. 4
  • Supermodular Type-II matchers are monotone Type-I matchers, connecting the probabilistic abstraction to a property used in the framework’s guarantees.Supermodularity is described as positive correlation among matches; exact inference methods for supermodular Markov Networks apply only to edge cliques and have super-linear complexity.Source: §3.2 · p. 4

4. COVERING

The framework divides entities into neighborhoods that cover the entity set and favors total covers, which preserve every relation tuple for matching. Neighborhoods can be expanded with boundary entities to form a total cover.

4. COVERING

  • A cover may fail to be total when a relation tuple, such as Coauthor(b1, c1), appears in none of its neighborhoods.The paper’s example contrasts a cover that omits that tuple with one that is a total cover.Source: §4 · p. 5
  • A total cover ensures every relation tuple is contained in at least one neighborhood, preventing tuples from being omitted from the matching process.A cover is a set of neighborhoods whose union is the full entity set; a total cover additionally covers the induced tuples of every relation.Source: §4 · p. 5
  • Expanding each neighborhood with entities that share a relation tuple with its members yields a total cover.The paper first constructs a total cover over Similar using Canopies, then adds boundaries for other relations; this can bring dissimilar entities and different entity types into one neighborhood.Source: §4 · p. 5

5. MESSAGE PASSING

The framework passes match information between neighborhoods using SMP for general matchers and MMP for probabilistic matchers. SMP has finite convergence, soundness, and order-independent output under its stated assumptions; MMP extends message passing with maximal messages and has guarantees for supermodular Type-II matchers.

5.1 Simple Message Passing Scheme (SMP)

  • SMP processes active neighborhoods using matches found so far and reactivates affected neighborhoods when new matches appear.It applies to any matcher; the algorithm terminates when no neighborhoods remain active.Source: §5 · p. 5, §5.1 · p. 5
  • SMP terminates, produces only matches from the full-data matcher, and returns the same output regardless of neighborhood evaluation order for well-behaved Type-I matchers.With bounded neighborhood size, its O(k^2 f(k)n) time bound is linear in the number of neighborhoods.Source: §5.1 · p. 5

5.2 Maximal Message Passing Scheme (MMP)

  • SMP can miss mutually dependent matches when each neighborhood’s matches require evidence from another, creating a cycle of unmet prerequisites.In the example, neither neighborhood can supply the evidence needed for the other to discover the three matches.Source: §5.2 · p. 5
  • MMP maintains active neighborhoods, matches, and maximal messages, computing new messages as neighborhoods are processed.The algorithm combines overlapping messages by replacing them with their unions before checking whether a message can be accepted as sound matches.Source: §5.2 · p. 6
  • MMP combines overlapping maximal messages and accepts a message as matches only when adding it does not reduce the probability of the current solution.A maximal message groups pairs that the matcher treats as either all matched or all unmatched; the probability check is the step requiring a probabilistic matcher.Source: §5.2 · pp. 5–6
  • For supermodular Type-II matchers, MMP guarantees convergence, soundness, and consistency, with O(k^4 f(k)n) time complexity.As with SMP, the time bound is linear in neighborhood count when neighborhood size is bounded; processing a neighborhood costs more than in SMP.Source: §5.2 · p. 6

6. EXPERIMENTS

The experiments evaluate message-passing schemes for MLN on HEPTH and DBLP, then test running time and parallel execution at larger scale. MMP approaches the whole-dataset MLN result on HEPTH, while message passing reduces runtime and scales to many neighborhoods.

6. EXPERIMENTS

  • The evaluation uses MLN on HEPTH and DBLP, with DBLP author names manually mutated to create noise and the original names serving as ground truth.HEPTH contains 58,515 author references; DBLP contains 50,195.Source: §6 · pp. 6–7

6.1 Accuracy of message passing schemes

  • On HEPTH, MMP is sound and has completeness 1 against UB, yielding the same output as holistic MLN; on DBLP its completeness is nearly 1.MMP's F1 also comes close to UB, whose recall is a provable upper bound but need not be attainable.Source: §6.1 · p. 7

6.2 Running Times

  • On HEPTH, SMP runs faster than NO-MP and MMP faster still because messages shrink active neighborhoods; DBLP shows similar behavior.Message-passing overhead is minimal, while smaller active neighborhoods reduce MLN inference work.Source: §6.2 · p. 8
  • MLN runtime grows exponentially with input and becomes prohibitive beyond 2,500 neighborhoods, while MMP runs linearly across all 13,000 HEPTH neighborhoods.MMP's curve has small jumps when larger neighborhoods are added.Source: §6.2 · p. 8

6.3 Parallelizing EM

  • On DBLP-BIG's 1,723,190 neighborhoods and 41,713,259 entity pairs, the 30-machine grid achieved around 11× speedup across all three message-passing variants.The reported speedup falls short of 30× because of grid-job overhead and uneven neighborhood assignment.Source: Table 1 · p. 8, §6.3 · p. 8

A. MONOTONICITY OF MATCHERS

The appendix identifies conditions under which matchers are monotone or supermodular, properties relevant to the framework's formal guarantees. It also distinguishes supported transitive closure from the transitivity rule itself.

A. MONOTONICITY OF MATCHERS

  • The framework assumes monotonicity as entities or evidence are added, but does not require it when relationships between existing entities are added.Iterative non-probabilistic matchers in and satisfy the stated monotonicity properties.Source: A. MONOTONICITY OF MATCHERS · p. 9
  • An MLN whose rules have only one Match term in the implicant is monotone and supermodular; the cited MLN variants meet this condition except those with the transitivity rule.The transitivity rule is non-monotone, so the framework gives no formal soundness guarantee for a matcher that includes it directly; applying transitive closure after iterations preserves monotonicity.Source: A. MONOTONICITY OF MATCHERS · p. 9
  • Dedupalog without negation and the transitivity constraint is monotone; negation alone does not necessarily break monotonicity, and all rules discussed in are monotone.A rule with negations can sometimes be rewritten equivalently without them.Source: A. MONOTONICITY OF MATCHERS · p. 9

B. DETAILS OF MLN AND RULES

The experimental matchers use author-name similarity and coauthor relations as evidence. MLN represents evidence with weighted rules, while RULES uses explicit rules with similarity-dependent coauthor requirements.

B. DETAILS OF MLN AND RULES

  • Both matchers use similarity, coauthor, and equals predicates, with Jaro-Winkler author-name similarity discretized to scores 1, 2, and 3.Score 3 is the highest possible similarity.Source: B. DETAILS OF MLN AND RULES · p. 9
  • MLN's learned weights make similarity scores 1 and 2 insufficient alone, score 3 positive evidence, and a matching coauthor pair additional positive evidence.The rules' weights are learned with Alchemy using training data.Source: B. DETAILS OF MLN AND RULES · p. 9
  • RULES matches score-3 pairs directly, requires one common coauthor for score 2 and two for score 1, then applies a 3-approximate algorithm before transitive closure.The rules are inspired by the learned MLN model and are evaluated without transitive closure before closure is applied at the end.Source: B. DETAILS OF MLN AND RULES · p. 9

C. EXPERIMENTS ON RULES MATCHER

The RULES experiments assess whether simple message passing (SMP) preserves matching quality and how it affects runtime. SMP matches the full run’s precision and recall on both datasets, while its runtime is not lower than NO-MP.

C. EXPERIMENTS ON RULES MATCHER

  • Because RULES is a Type-I matcher that does not generate probabilities, the experiments compare NO-MP and SMP rather than MMP.RULES was also run directly on the entire datasets, allowing soundness and completeness to be computed exactly.Source: C. EXPERIMENTS ON RULES MATCHER · pp. 9–10
  • SMP matched the full run’s precision and recall on both datasets, achieving completeness.Figure 4 reports precision, recall, and F1 for HEPTH and DBLP.Source: C. EXPERIMENTS ON RULES MATCHER · p. 10, Figure 4 · p. 10
  • SMP’s running time is not lower than NO-MP because neighborhood savings do not offset the cost of revisiting neighborhoods.RULES has linear complexity and is already fast enough to run on the full datasets.Source: C. EXPERIMENTS ON RULES MATCHER · p. 10

D. A BRIEF SURVEY OF ENTITY MATCHING TECHNIQUES

Entity matching methods range from pairwise attribute comparisons to collective models that exploit relationships among match decisions. The survey contrasts their matching capabilities and scalability, including the high inference cost of probabilistic collective methods and the limitations of existing blocking approaches.

Non-Relational Approaches

  • Attribute-based methods classify entity pairs using attribute-similarity scores, but cannot distinguish separate entities with the same name.The foundational approaches include Newcombe and Fellegi and Sunter, with later work on similarity measures such as approximate string matching.Source: D. A BRIEF SURVEY OF ENTITY MATCHING… · p. 10

Simple Relational Approaches

  • Simple relational methods add related entities’ attributes to pairwise similarity scores, helping disambiguation but risking confusion between distinct entities with similar names.Examples use coauthor and citation information.Source: D. A BRIEF SURVEY OF ENTITY MATCHING… · p. 10

Collective Approaches

  • Collective methods exploit dependencies among match decisions; iterative methods can face bootstrapping, while purely collective methods model interrelationships directly.Purely collective methods are described as current state-of-the-art in matching quality and include probabilistic models such as CRFs and Markov Logic Networks.Source: D. A BRIEF SURVEY OF ENTITY MATCHING… · p. 10
  • Probabilistic inference over large EM models has made state-of-the-art purely collective methods infeasible for large datasets.The survey identifies the high cost of probabilistic inference as the scalability obstacle.Source: D. A BRIEF SURVEY OF ENTITY MATCHING… · pp. 10–11

Scaling EM Algorithms

  • Blocking reduces pairwise matching complexity from O(n^2) to O(kn), but iterative blocking lacks formal quality guarantees and does not address probabilistic collective EM.Here k denotes average group size; blocks may overlap and may use multiple grouping criteria.Source: D. A BRIEF SURVEY OF ENTITY MATCHING… · p. 11

E.1 Simple Message Passing

For well-behaved Type-I matchers, SMP is guaranteed to terminate, remain sound, and produce an output independent of cover-evaluation order. The proof builds soundness by showing that each neighborhood’s matches preserve soundness when added to the accumulated message set.

E.1 Simple Message Passing

  • SMP terminates, produces only matches in E(E), and is invariant to the order in which covers are evaluated for any well-behaved Type-I matcher.These are the theorem’s convergence, soundness, and consistency guarantees.Source: §E.1 · p. 11
  • The convergence proof relies on the active-cover process strictly increasing M while M is bounded by |E × E|.Thus the algorithm must terminate after finitely many steps.Source: §E.1 · p. 11
  • Each neighborhood’s output remains sound when its input message set is sound, by matcher monotonicity and idempotence.The proposition establishes this property for MC = E(C, M+).Source: §E.1 · p. 11
  • Soundness of the accumulated message set follows by induction from the empty initial set, since each neighborhood adds only sound matches.The proposition supplies the preservation step for the induction.Source: §E.1 · p. 11

E.2 Maximal Message Passing

For supermodular Type-II matchers, MMP terminates with a sound output that is consistent across cover-evaluation orders. The proof relies on maximal messages and on adding only sound matches to the accumulated set.

E.2 Maximal Message Passing

  • MMP always terminates and, on termination, produces a sound output invariant to cover-evaluation order for supermodular Type-II matchers.Soundness means the output M+ is contained in E(E).Source: §E.2 · p. 11
  • COMPUTEMAXIMAL produces maximal messages for well-behaved Type-I matchers, sound evidence sets, and any neighborhood.The lemma establishes maximality for every message it produces.Source: §E.2 · p. 11
  • A two-element message is maximal when its pair is connected by an edge; larger connected components are handled by decomposing them into overlapping smaller components.The inductive step combines maximal messages from components sharing a node.Source: §E.2 · p. 11
  • The soundness argument for MMP depends on showing that the additional pairs it adds are sound, preserving soundness of M+ as in SMP.The proof identifies Step 7 as the extra update that must be checked.Source: §E.2 · p. 11
Loading 1103.2410v1…