PARIS: Probabilistic Alignment of Relations, Instances, and Schema

Fabian M. Suchanek; Serge Abiteboul; Pierre Senellart

Source-linked AI summary

PARIS: Probabilistic Alignment of Relations, Instances, and Schema

Fabian M. Suchanek, Serge Abiteboul, Pierre Senellart

arXiv:1111.7164v1Nov 30, 2011cs.DB

TL;DR

Ontology integration is difficult because independently designed ontologies contain complementary information but use different identifiers and require alignment of both instances and schemas. PARIS provides a probabilistic holistic algorithm that aligns instances, classes, and relations without parameter tuning. Experiments on real-world ontologies show that the approach works effectively in practice.

Problem
Independently designed ontologies contain complementary information but use different identifiers, while alignment must reconcile both instances and schemas.
Method
PARIS probabilistically aligns instances, classes, and relations together, using the interplay between schema alignment and instance matching without parameter tuning.
Results
Experiments on real-world ontologies show that PARIS works extremely well in practice.
Takeaways & Limitations
PARIS offers a holistic approach to automated alignment of RDFS ontologies without training data or parameter tuning.
Takeaways & Limitations
The iteration procedure lacks a proven theoretical fixpoint condition, although convergence was reached after a few iterations in the experiments.

Abstract

from arXiv · show

One of the main challenges that the Semantic Web faces is the integration of a growing number of independently designed ontologies. In this work, we present PARIS, an approach for the automatic alignment of ontologies. PARIS aligns not only instances, but also relations and classes. Alignments at the instance level cross-fertilize with alignments at the schema level. Thereby, our system provides a truly holistic solution to the problem of ontology alignment. The heart of the approach is probabilistic, i.e., we measure degrees of matchings based on probability estimates. This allows PARIS to run without any parameter tuning. We demonstrate the efficiency of the algorithm and its precision through extensive experiments. In particular, we obtain a precision of around 90% in experiments with some of the world's largest ontologies.

1. INTRODUCTION

PARIS addresses ontology integration by aligning instances and schemas together across independently designed ontologies. Its probabilistic, holistic algorithm is designed for large-scale use without parameter tuning and is evaluated on real-world ontologies.

Motivation: Independently designed ontologies contain complementary information but use different identifiers, making their knowledge difficult to combine.The Semantic Web goal is to interlink these isolated knowledge sources.
Motivation: Existing ontology alignment must reconcile both instances and schemas, including classes and relations.Modern ontologies combine rich schemas with millions of instances and assertions.
Approach: PARIS aligns related entity instances, classes, and relations while exploiting interplay between schema matching and instance matching.The intended outcome is automatic discovery and linking of identical entities across ontologies.
Approach: PARIS is probabilistic and requires neither training data nor parameter tuning.The contribution explicitly presents it as an algorithm for simultaneously aligning instances, classes, and relations.
Evaluation: The approach is evaluated through experiments on real-world ontologies to assess its validity.The paper states that the algorithm is implemented efficiently and does not require tuning.

2. RELATED WORK

Related work largely treats instance matching and schema alignment as separate problems. A small number of holistic systems address both, but PARIS differs in scope, input requirements, and alignment capabilities.

Instance matching: Record-linkage approaches focus on duplicate instances and generally omit ontology semantics, relations, and classes.Ontology matching additionally involves formal structures such as subclassOf taxonomies.
Schema alignment: Traditional schema-alignment methods use lexical, structural, or composite techniques but align classes without jointly matching relations and instances.Several methods derive class similarity from instance similarities, yet compute only class equivalence.
Instance matching: Most instance-matching research uses terminological, logical, declarative, clustering, numerical, or heuristic techniques.The literature also includes manual mapping rules and approaches that learn mappings from training data.
PARIS: PARIS aims to avoid manual input and training data while aligning instances, classes, and relations together.The comparison with ObjectCoref uses ontology-alignment evaluation datasets.
Holistic approaches: Only a few systems jointly align schemas and instances, and the cited RiMOM and iliads evaluations used small ontologies.RiMOM aligns classes but not subclassOf relationships, while PARIS is described as monolithic rather than a bundle of selectable heuristics.

3. PRELIMINARIES

The paper formalizes RDFS ontologies as resources, literals, properties, and statements, then introduces functionality to obtain alignment evidence from relations that are nearly one-to-one.

RDFS foundations: An RDFS ontology is a set of triples over resources, properties, and literals, with statements written as binary relations r(x, y).Resources identify real-world objects or concepts, while properties connect resources or literals.
RDFS foundations: RDFS distinguishes classes from instances, with rdf:type connecting an instance to a class.The paper assumes resources are partitioned into classes and instances.
RDFS foundations: Subclass and subproperty statements support inferred membership and relation entailments in the ontology's deductive closure.Instances of a subclass are also instances of its superclass, and subproperty facts imply superproperty facts.
Equivalence: Ontology alignment seeks equivalence across instances, classes, and relations, including differently named relations such as wasBornIn and birthPlace.The model assumes a single ontology does not contain equivalent resources, relations, or classes.
Functionality: Strict functions are too brittle for noisy, multi-valued real-world relations, motivating quasifunctions and the functionality measure.Functionality captures cases where most subjects have one or few related objects, such as livesIn or isCitizenOf.
Functionality: The paper defines global functionality as the harmonic mean of local functionalities and defines inverse functionality analogously.These measures provide relation-based evidence for deriving alignments.

4. PROBABILISTIC MODEL

PARIS estimates equivalence and subsumption probabilities from shared relation evidence, negative evidence, and matched instances. It then uses these estimates to align relations and classes across ontologies.

Instance equivalence: PARIS estimates instance-equivalence probabilities using shared relations, equivalent linked objects, and high inverse functionality.The logical evidence is transformed into a probability estimate, with equivalence probabilities recursively depending on other equivalences.
Instance equivalence: Negative evidence can lower an equivalence probability when a highly functional relation has no matching target.The paper combines positive and negative probability estimates multiplicatively.
Relation alignment: Relation alignment estimates whether one relation is a subrelation of another using matched relation pairs and probabilities of instance equivalence.The resulting probability is normalized over relation pairs with counterparts in the other ontology.
Assignments: Each instance receives multiple candidate matches with probability scores, while its highest-scoring candidate is its maximal assignment.Ties are broken arbitrarily so each instance has at most one maximal assignment.
Class alignment: PARIS computes class subsumption probabilities from the expected overlap of their instances rather than treating classes only as equivalent.The probability is proportional to the number of instances of c that are also instances of c′.
Class alignment: Class information is incorporated only after instance equivalences because differing hierarchy granularities and representations reduce its usefulness for instance matching.Some ontologies express properties with classes, while others express them with relations.

5. IMPLEMENTATION

PARIS implements ontology alignment through iterative probabilistic equivalence computations, with optimizations that reduce runtime while preserving the assessed outcomes. The implementation uses simple literal matching, minimal dataset-dependent tuning, and convergence-based stopping, subject to stated assumptions and an unproven fixpoint condition.

PARIS assumes no duplicate entities within one ontology and therefore evaluates equivalence only across the two input ontologies.
Instance and relation probabilities are iterated to convergence, after which class equivalences are computed from the final assignment.The initial relation-inclusion probabilities are bootstrapped with θ = 0.10, and subsequent rounds use computed values.
A theoretical condition guaranteeing that the iteration reaches a fixpoint has not been proved, although convergence was reached after a few iterations in the experiments.
O(nm^2e) replaces naïve O(n^2m) instance-equivalence computation by traversing statements and known equivalent instances.Here n is the number of instances, m the average statements per instance, and e the average equivalent instances per instance; typical values are m = 20 and e around 10.
Thresholding probabilities below θ, limiting evaluated pairs to 10,000, and retaining only maximal previous assignments reduce runtime by an order of magnitude with little effect on relation inclusion.
The implementation is heavily I/O-bound, and using an SSD reduced computation time on very large ontologies from days to hours.
Literal probabilities may incorporate application-specific similarity, conversions, or misspelling robustness, but the implementation uses normalized identical literals with probability 1 and otherwise 0.
The model has no dataset-dependent tuning parameters, although its initial θ and literal similarity functions remain implementation parameters.The experiments report that θ does not affect results, while the simple identity function performs well.

6. EXPERIMENTS

PARIS was evaluated on benchmark and large real-world ontology pairs, aligning instances, relations, and classes without training data. It achieved strong instance and relation results, while class alignment remained less reliable.

6.2 Benchmark Test: 91% F-measure on the second OAEI dataset exceeded ObjectCoref's 90% and other approaches' below-80% scores.PARIS required no training data, unlike ObjectCoref.
6.3 Design Alternatives: 100% precision and 70% recall resulted from replacing the literal equality measure with normalized string comparison.The modified measure increased precision but reduced recall.
6.4 Real-world Ontologies: 90% precision and 73% recall were achieved when matching shared yago and DBpedia instances; restricting to entities with more than 10 DBpedia facts raised them to 97% and 85%.The two ontologies shared 1.4 million entities.
6.4 Real-world Ontologies: 92% F-score improved over an rdfs:label baseline's 82% on the yago–IMDb instance alignment.The baseline achieved 97% precision but only 70% recall.
6.4 Real-world Ontologies: PARIS aligned 80% of IMDb and yago relations with 100% precision, while mapping half of IMDb classes to more general or equal yago classes.Class alignment performed less well in the reverse direction.
6.4 Real-world Ontologies: Across the experiments, instance and relation alignment worked very well, whereas class alignment still had room for improvement.The authors characterize the overall outcome as the first holistic alignment of instances, relations, and classes on some of the world's largest ontologies without prior knowledge, tuning, or training.

7. CONCLUSION

PARIS is a probabilistic, holistic algorithm that aligns instances, classes, and relations while modeling their interplay. Experiments show strong practical performance, but structural heterogeneity remains outside its current scope.

PARIS aligns instances, classes, and relations simultaneously across RDFS ontologies.Its probabilistic framework captures the interplay between schema alignment and instance matching.
The approach does not use training data or require parameter tuning.
Experiments show that PARIS works extremely well in practice.
PARIS aligns relations with completely different names because it does not use heuristics on relation names.The authors conjecture that traditional name heuristics could be incorporated into the model.
PARIS cannot currently handle structural heterogeneity between ontologies.This includes cases where one ontology represents an event as a relation while another represents it as an event entity.

A. GLOBAL FUNCTIONALITY

The paper considers several definitions of global functionality, comparing how each aggregates relation statistics. It chooses the harmonic mean because local functionalities are ratios and arithmetic averaging is less appropriate.

Alternative definitions: One candidate defines functionality as statements divided by pairs of statements sharing a source.This measure is volatile when a single source has many targets.
Alternative definitions: Another candidate divides the number of first arguments by the number of second arguments.For a complete people–dishes relation, this incorrectly assigns functionality n despite each person liking n dishes.
Alternative definitions: A further alternative averages local functionalities, but the paper does not specify the arithmetic aggregation in the supplied passage.
Chosen definition: The paper chooses the harmonic mean rather than the arithmetic mean to aggregate local functionalities.The authors characterize local functionalities as ratios and note that the global functionality is equivalent to the harmonic mean.
Chosen definition: The selected global functionality is defined as the number of first arguments per relationship instance.The paper states that this formulation is equivalent to the harmonic mean.

B. PROBABILISTIC MODELING

The probabilistic model translates logical alignment rules into probability assessments by recursively combining their components. Its estimates rely on independence and functionality assumptions that are acknowledged to be imperfect but useful approximations.

Rule-based model: The model represents equality using logical rules, including conditions involving relationships and high functionality.
Assumptions: The probability transformation assumes mutual independence among distinct model elements such as instance equivalence, functionality, and relationship inclusion.
Probability conversion: Logical rules are converted into probability assignments by recursively decomposing their premises with conjunction and disjunction identities.The supplied identities multiply conjunction probabilities and combine disjunctions through complements.
Probability conversion: Expected counts are used when the model must estimate quantities such as the number of entities satisfying a condition.
Assumptions: The computed values approximate equality probabilities when literal equality, functionality, and independence conditions hold.The paper states that these conditions are not fully true in practice, but the equations still provide useful approximations.

C. EQUIVALENCE OF SETS

The equivalence model compares sets of relation values probabilistically while accounting for relation functionality. Direct pairwise comparison remains quadratic, and relation characteristics determine how strongly shared or differing values support equivalence.

Set comparison: Comparing two instances checks every statement about one instance against every statement about the other when the relations match.This produces a quadratic number of comparisons.
Set comparison: Representing targets as sets does not remove the quadratic comparison burden because every element in one set may be equivalent to every element in the other.
Probabilistic equivalence: Shared values from highly inverse-functional relations provide stronger evidence of equivalence than shared values such as residence cities.Different birth dates support distinctness more strongly than different liked books, which may coexist for equivalent instances.
Probabilistic equivalence: The formulas act as a set-comparison measure with probabilistic equivalences that incorporates relation functionalities.The model can unify instances when they share the value of one highly inverse-functional relation.