PaperlayerView exact revision on arXiv

Source-linked AI summary

SiGMa: Simple Greedy Matching for Aligning Large Knowledge Bases

Simon Lacoste-Julien, Konstantina Palla, Alex Davies, Gjergji Kasneci, Thore Graepel, Zoubin Ghahramani

arXiv:1207.4525v1cs.AIcs.DBcs.IR

TL;DR

Aligning knowledge bases with millions of entities and facts remains difficult despite its value for unifying structured information. SiGMa uses greedy iterative propagation with graph structure and entity-property similarities, achieving over 95% precision in under two hours and higher benchmark F-measure than prior results.

  • Problem

    Efficiently identifying corresponding entities across large knowledge bases remains challenging, limiting automatic interlinking of complementary structured information.

  • Method

    SiGMa greedily propagates matches using relationship-graph structure and flexible entity-property similarity scores.

  • Results

    Over 95% precision in less than two hours, with a 50x speed-up over prior work; SiGMa also achieves higher F-measure on standard benchmarks.

  • Takeaways & Limitations

    SiGMa provides a scalable alignment approach that matches large knowledge bases efficiently while outperforming prior benchmark results in F-measure.

  • Takeaways & Limitations

    SiGMa cannot correct previous mistakes and assumes alignments are one-to-one.

Abstract

from arXiv · show

The Internet has enabled the creation of a growing number of large-scale knowledge bases in a variety of domains containing complementary information. Tools for automatically aligning these knowledge bases would make it possible to unify many sources of structured knowledge and answer complex queries. However, the efficient alignment of large-scale knowledge bases still poses a considerable challenge. Here, we present Simple Greedy Matching (SiGMa), a simple algorithm for aligning knowledge bases with millions of entities and facts. SiGMa is an iterative propagation algorithm which leverages both the structural information from the relationship graph as well as flexible similarity measures between entity properties in a greedy local search, thus making it scalable. Despite its greedy nature, our experiments indicate that SiGMa can efficiently match some of the world's largest knowledge bases with high precision. We provide additional experiments on benchmark datasets which demonstrate that SiGMa can outperform state-of-the-art approaches both in accuracy and efficiency.

1. INTRODUCTION

The paper addresses scalable alignment of large knowledge bases, where differing entity terminology and exponentially many possible matchings make automation difficult. It introduces SiGMa, a greedy, structurally informed algorithm and reports high-precision, efficient alignment results.

  • Motivation: Large knowledge bases contain overlapping and complementary information, motivating alignment to support information retrieval and question answering.
  • Challenge: Automated alignment is challenging because knowledge bases use different terms for entities and the matching space grows exponentially with entity count.
  • Method: SiGMa aligns knowledge bases with millions of entities and facts using seed matching, structural information, entity properties, local candidate proposals, and greedy decisions.
  • Contributions: SiGMa supports tailored scoring functions and tradeoffs between precision and recall and between computation and recall.
  • Results: Over 95% precision was achieved in less than two hours, representing a 50x speed-up over [26], while benchmark F-measure exceeded the best previously published results.

2. ALIGNING LARGE-SCALE KNOWLEDGE BASES · YAGO and IMDb

The paper formulates large-scale knowledge-base alignment as one-to-one instance matching over graph relationships and property values, motivated by combining YAGO and IMDb. It emphasizes scalable alternatives to quadratic pairwise matching and assumes partial alignments of relationships and properties.

  • YAGO and IMDb: YAGO is a large semantic knowledge base derived from Wikipedia, WordNet, and GeoNames.
  • YAGO and IMDb: IMDb is a large online database storing information about movies.
  • YAGO and IMDb: The two sources are represented as lists of triples without assuming richer ontology constructs, making the task instance matching.
  • YAGO and IMDb: The problem seeks a one-to-one partial mapping between semantically equivalent entities, given partial mappings between relationships and properties.
  • 2.2 Possible approaches: Standard ontology-matching methods often consider all entity pairs, causing quadratic scaling that cannot support millions of entities.
  • 2.2 Possible approaches: Graph-based formulations use mutually dependent neighbor alignments, but quadratic assignment is NP-hard and prior applications handled at most one hundred entities.
  • 2.3 Design choices and assumptions: SiGMa assumes the true alignment is mainly one-to-one and that partial alignments between corresponding relationships and properties are available.

3. THE SIGMA ALGORITHM

SiGMa greedily optimizes a quadratic matching objective that combines entity-property similarity with graph-neighborhood evidence. It iteratively expands a feasible partial matching using locally selected candidates, propagating information through compatible neighbors until a bound or score threshold stops the process.

  • Objective function: SiGMa represents one-to-one entity matching as a binary matrix and globally scores feasible matchings with a quadratic objective.Linear coefficients sij encode entity similarity, while quadratic coefficients wij,kl capture matching preferences induced by already matched entity pairs.
  • Stopping criterion: SiGMa terminates when the matching reaches the bound R or the latest match’s objective variation falls below a threshold, with threshold choice controlling precision and recall.The experiments report that a threshold of 0.25 correlates well with a point on the precision/recall tradeoff.
  • Greedy optimization: The algorithm starts from a good-quality partial match and repeatedly adds the feasible candidate pair that maximally increases the objective.Candidates are selected from a small set St, and previous decisions are never undone.
  • Graph propagation: Compatible neighbors encourage a candidate match when neighboring entities are connected by correspondingly matched relationships in the two knowledge bases.The neighborhood contribution counts, in a weighted fashion, currently matched compatible neighbor pairs.
  • Graph propagation: After matching i to j, SiGMa adds compatible-neighbor pairs as candidates, enabling information from new matches to propagate through the relationship graph.The score combines a static similarity term sij with a dynamic graph contribution δgij(y) that depends on the local neighborhood Nij.
  • Similarity functions: The modular similarity term can use efficiently computed similarity functions, including a weighted Jaccard measure over words that is robust to word re-ordering.The implementation emphasizes simplicity, and the Jaccard coefficient compares the intersection and union of word sets.

4. EXPERIMENTS

SiGMa was evaluated on large-scale knowledge-base pairs and OAEI benchmark datasets against established methods and exact-string baselines. Experiments also examined error types and the contributions of score-function components and graph information.

  • Experimental setup: Experiments evaluated SiGMa on large-scale knowledge bases and OAEI benchmark dataset pairs, using fixed parameters selected on YAGO-IMDb.The large-scale evaluation included YAGO-IMDb and Freebase-IMDb, while benchmarks supported comparisons with previously published methods.
  • Large-scale evaluation: Large-scale experiments compared SiGMa with PARIS and unambiguous exact-string matching despite SiGMa’s greedy, non-revising search.PARIS did not complete its first iteration within a week, so its YAGO-IMDb results used prediction files supplied by its authors.
  • Large-scale evaluation: About 2% of SiGMa’s predicted YAGO-IMDb pairs had no words in common, including spelling, language, character, and alternate-title variations.These pairs had zero string similarity and were difficult to match without graph information.
  • Benchmark evaluation: On benchmarks, SiGMa was compared with PARIS, RiMoM, Exact-string, and SiGMa-linear, which omits graph information.SiGMa significantly improved previous results without parameter tweaking; SiGMa-linear perfectly matched both Person and Restaurants datasets.
  • Benchmark evaluation: 89% Exact-string F-measure on Rexa-DBLP exceeded RiMoM’s 76%, while SiGMa-linear increased the result to 91%.Rexa-DBLP’s multiple-author and multiple-paper relationships provided richer structure for graph-based propagation.
  • Ablation analysis: Removing the static string-and-property score reduced maximum F-measure from 95% to about 80%, compared with 72% for Exact-string.On the top 5% of exact matches sorted by score, SiGMa achieved 99% precision, 87% recall, and 92% F-measure, demonstrating the contribution of graph information.

5. RELATED WORK

SiGMa is situated among scalable ontology matching, collective entity resolution, and relationship-graph propagation methods. PARIS is identified as the only ontology-matching approach applied to datasets of the size considered, while several related propagation approaches were not scalable at that scale.

  • Ontology matching: PARIS is the only ontology-matching approach identified as having been applied to datasets as large as those considered, solving the broader problem of matching instances, relationships, and classes.PARIS defines a normalized score between instance pairs representing how likely they are to match.
  • Collective entity resolution: SiGMa is related to collective entity resolution methods that greedily cluster entities using previous decisions and can theoretically support 1−1 matching constraints.The cited approach did not implement the 1−1 matching constraint.
  • Graph propagation: Relationship-graph information propagation has appeared in ontology matching and social-network alignment, but prior approaches were not scalable to the knowledge-base sizes considered.The social-network method pursued a different objective: aligning edges with similar weights across graphs.

6. CONCLUSION · APPENDIX

SiGMa is presented as a simple, scalable alignment algorithm that achieves strong benchmark accuracy and matches PARIS while being substantially faster on million-entity knowledge bases. Its limitations—non-correction of mistakes and restriction to 1-1 alignments—remain open areas for future work.

  • 6. CONCLUSION: SiGMa is a simple and scalable algorithm for aligning large-scale knowledge bases.Its approach is presented as suitable for knowledge bases containing millions of entities.
  • 6. CONCLUSION: SiGMa obtained a higher F-measure than the previously best published results on OAEI benchmark datasets.The comparison concerns the benchmark datasets used in the experiments.
  • 6. CONCLUSION: SiGMa matched PARIS’s performance while being 50x faster on large-scale knowledge bases of millions of entities.This comparison highlights the algorithm’s efficiency despite its simpler design.
  • 6. CONCLUSION: SiGMa makes greedy decisions and never backtracks to correct previous decisions.The experiments indicated that this non-corrective nature did not seem to be an issue.
  • 6. CONCLUSION: SiGMa cannot correct previous mistakes or handle alignments other than 1-1.Addressing these limitations scalably while preserving high accuracy is identified as future work.
  • 6. CONCLUSION: Pre-processing each knowledge base with de-duplication can make the 1-1 assumption more reasonable.The passage describes this as a powerful feature for mitigating the alignment restriction.
  • 6. CONCLUSION: The authors acknowledge Fabian Suchanek, Pierre Senellart, and Guillaume Obozinski for code sharing and discussions.The research was supported by Microsoft Research Ltd. and a Research in Paris fellowship.

A. PROPERTY SIMILARITY MEASURE · B. GRAPH NEIGHBOR WEIGHT

The implementation measures property similarity with a smoothed weighted Jaccard approach over property-value sets, while graph scoring uses configurable neighbor weights and independent per-knowledge-base normalization. These components support flexible literal comparisons and account for asymmetric neighborhood sizes across knowledge bases.

  • A. PROPERTY SIMILARITY MEASURE: The property similarity measure is a smoothed weighted Jaccard similarity over entities’ sets of properties and associated literal values.Property values receive IDF weights in the measure.
  • A. PROPERTY SIMILARITY MEASURE: The property-value weighting uses the number of entities in a knowledge base that have a value for a given property.The supplied definition identifies this quantity as Np.
  • A. PROPERTY SIMILARITY MEASURE: Property alignment pairs matched properties between the two entities’ property sets.The alignment is represented as M12 = {(a, b) : pa is matched to qb}.
  • A. PROPERTY SIMILARITY MEASURE: Literal similarity is flexible, using a [0, 1]-valued measure such as normalized numeric distance or string-edit distance.Examples include dates, years, and strings.
  • B. GRAPH NEIGHBOR WEIGHT: Graph weight wik controls how strongly a correctly matched neighbor k contributes to the score of a suggested pair containing i.The experiments consider both constant weights wik = 1 and weights varying inversely with the number of same-relationship-type neighbors of k.
  • B. GRAPH NEIGHBOR WEIGHT: Graph-score normalization is performed independently within each knowledge base, unlike the jointly normalized string and property similarities.This addresses asymmetric neighborhood sizes, with more information available for each movie in IMDb than in YAGO.

C. QUADRATIC ASSIGNMENT PROBLEM · D. PARAMETERS USED FOR SIGMA · E. ADDITIONAL PARAMETER

The section formulates knowledge-base alignment through a quadratic assignment problem and describes graph-weighting for candidate matches. The supplied passages do not provide substantive details about the parameters used for SiGMa or the additional parameter.

  • C. QUADRATIC ASSIGNMENT PROBLEM: The quadratic assignment problem seeks a bijection between facilities and locations that minimizes expected transport cost.The transport cost combines expected shipment volume between facilities with expected shipment cost between locations.
  • C. QUADRATIC ASSIGNMENT PROBLEM: Graph weights distribute each match’s contribution uniformly across its neighbors, giving greater weight to a movie match linked through a unique director than through one of two actors.The illustration assigns weight 1 to the unique-director pairing and weight 1/2 to each actor pairing.

EXPERIMENTS

The experiments section includes additional parameter experiments omitted from the main text for brevity.

  • Additional parameter experiments were conducted but omitted from the main text for brevity.

E.1 Exp. 5: Weighting schemes, smoothing and tradeoffs

SiGMa’s weighting variations had limited impact overall, with uniform string weights causing the largest decrease at under 1% F-measure. Varying smoothing and tradeoff parameters also kept performance within a 1% F-measure range around the chosen values.

  • Weighting schemes: Uniform graph weighting surprisingly achieved the best result compared with inverse-neighbor weighting.The graph component used either uniform weights or the inverse number-of-neighbors weight proposed in (12).
  • Weighting schemes: Uniform string weights instead of IDF scores produced the largest decrease, at less than 1% F-measure.The experiment compared uniform and IDF weighting for string and property components, and uniform versus inverse-neighbor weighting for the graph component.
  • Smoothing and tradeoffs: Changes of approximately 0.1–0.2 in tradeoff parameters left performance within a 1% F-measure range.The two tradeoff parameters were varied linearly around their chosen values.
  • Smoothing and tradeoffs: Changes of approximately 1.5 in smoothing parameters left performance within a 1% F-measure range.Three smoothing parameters, one for each score component, were varied linearly around their chosen values.

E.2 Exp. 6: Stopping threshold choice

Exp. 6 examines whether matching-pair scores track precision and recall changes to determine a stopping threshold. On YAGO-IMDb, precision starts to drop when the score falls below 0.35.

  • E.2 Exp. 6: Stopping threshold choice: Exp. 6 overlays SiGMa’s per-iteration precision/recall with the selected matching pair’s score to assess a possible stopping threshold.The experiment uses YAGO-IMDb predictions and marks when score thresholds 0.35 and 0.25 are reached.
  • E.2 Exp. 6: Stopping threshold choice: 0.35 is the score threshold below which precision starts to drop on the YAGO-IMDb dataset.Figure 5 shows score evolution in green alongside precision for the last 1k predictions with ground-truth information.
Loading 1207.4525v1…