Not Quite the Same: Identity Constraints for the Web of Linked Data

Gerard de MeloAAAI 2013 · DOI

Abstract

The owl:sameAs predicate is fundamental to the Semantic Web, yet it is frequently misused to link entities that are merely similar rather than identical. This paper introduces a formal framework to identify these "identity crises" by leveraging the internal naming consistency of major data hubs. By modeling the Web of Data as a graph and applying a graph-based optimization algorithm (minimum multicut), we automatically prune hundreds of thousands of incorrect links, restoring logical consistency to large-scale linked datasets.

Introduction: The Identity Crisis in Linked Data

In the ideal vision of Linked Data, different datasets are connected using the owl:sameAs property. According to formal logic—specifically Leibniz’s Law—if $x$ sameAs $y$, then every property true of $x$ must be true of $y$. However, in practice, data providers often use sameAs as a shorthand for "related to" or "very similar."

Figure 1: An example of an identity crisis where 'sameAs' links (weighted edges) bridge distinct entities like 'Paul' and 'Paula' through intermediate redirects.

This misuse creates a logical nightmare. For instance, if a brewery is linked to the class of beer bottles it produces, an automated system might conclude that a physical object is a person with a specific birth year and salary. Because the Semantic Web avoids the "Unique Name Assumption," it is difficult to detect when these links create false identities without a formal way to declare that two identifiers are definitely not the same.

Methodology: Distinctness Constraints and Graph Modeling

To address this, we propose a method to detect and fix errors using Distinctness Constraints based on the Quasi-Unique Name Assumption. While the entire Web does not follow a unique name rule, individual high-quality datasets (e.g., DBpedia, UniProt) generally do. If a single dataset contains two different identifiers, they should be treated as distinct.

We model the Web of Data as an undirected graph where nodes are URIs and edges are sameAs links. A violation occurs if a path exists between two nodes that a constraint dictates must be distinct. To resolve these, we solve the minimum multicut problem: removing the minimum number of edges to break all paths between distinct nodes. Since this is NP-hard, we utilize a Linear Program (LP) relaxation algorithm to find near-optimal cuts efficiently at a Web-scale.

Experimental Evaluation

The study evaluated two massive real-world collections:

  • BTC 2011: A crawl containing over 3.4 million sameAs links.
  • sameas.org: An equivalence service providing over 22 million sameAs links.

We focused on constraints from major hubs including DBpedia, DBLP, Freebase, GeoNames, MusicBrainz, and UniProt. The analysis revealed that identity is transitive, but errors are not; a single erroneous link between major hubs can merge massive, unrelated clusters of data.

Key Results and Insights

Our method identified over 500,000 URI pairs that violated identity constraints. By applying the LP relaxation algorithm, we automatically removed 280,086 incorrect edges. On average, removing a single "bad" edge resolved 1.85 constraint violations, demonstrating the algorithm's effectiveness at identifying the "weakest links" causing the most logical damage.

Beyond logical errors, many violations stemmed from "bad plumbing," such as incorrectly escaped titles or links to DBpedia entries that no longer exist due to Wikipedia page title changes.

Conclusion and Future Work

The prevalence of sameAs misuse suggests a need for more nuanced predicates like skos:closeMatch for relationships that do not imply strict identity. Future work will explore incorporating string similarity (comparing URI labels) as edge weights to further refine the pruning process. Currently, the method relies on internal dataset consistency; expanding this to detect errors between datasets without shared unique name policies remains a key challenge.

Summary updated

BibTeX
@inproceedings{melo2013not,
  author = {Gerard de Melo},
  title = {{Not Quite the Same: Identity Constraints for the Web of Linked Data}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8468},
}
Figure