PaTeCon: A Pattern-Based Temporal Constraint Mining Method for Conflict Detection on Knowledge Graphs

Jianhao Chen, Junyang Ren, Wentao Ding, Yuzhong Qu

Introduction

As Knowledge Graphs (KGs) like Wikidata and Freebase expand, they increasingly incorporate temporal facts—triples that include specific time intervals (e.g., "David Beckham played for Real Madrid from 2003 to 2007"). However, this growth often leads to "temporal conflicts," where two facts cannot logically coexist, such as a person being born in two different cities or holding two mutually exclusive full-time positions simultaneously.

Traditionally, detecting these conflicts has relied on human experts manually writing logical constraints. This approach is labor-intensive, often lacks the necessary granularity to avoid false positives, and fails to generalize across different KG schemas. This paper introduces PaTeCon (Pattern-based Temporal Constraint mining), an automated method presented at AAAI-23 that discovers temporal constraints by mining structural patterns directly from KGs.

The PaTeCon Methodology

PaTeCon shifts the burden of rule creation from humans to an automated mining process. The system operates through several key stages:

  1. Structural Pattern Instantiation: The algorithm searches for two primary "shapes" or patterns within the graph to identify potential constraints:
  2. Pattern (a): A single subject linked to two different properties and objects (e.g., a person with two birthplaces).
  3. Pattern (b): Two connected subjects, each with their own temporal properties (e.g., a student and their advisor's educational history).
Structural patterns (a) and (b) used for temporal constraint instantiation.
  1. Temporal Predicate Attachment: For these patterns, the system evaluates five temporal relationships based on Allen’s Interval Algebra: start, finish, before, disjoint, and include.
  2. Statistical Filtering: The system calculates Support (frequency of the pattern) and Entity-level Confidence (the consistency of the constraint across all matching entities) to filter out noise.
  3. Uncertainty Handling: To manage the "fuzziness" of KG time data (e.g., facts listing only a year), PaTeCon utilizes a three-valued logic (Positive, Negative, Unknown) during confidence calculations.

Dynamic Refinement and Class Restrictions

A core innovation of PaTeCon is its Dynamic Refinement process. General rules often suffer from granularity issues; for example, a rule stating "an athlete cannot be a member of two sports teams at once" would incorrectly flag an athlete playing for both a professional club and their national team.

PaTeCon resolves this by automatically adding class restrictions. If a general rule shows mediocre confidence, the system drills down into the entity hierarchy. It might discover that a "disjoint" rule holds true only if both teams belong to the class "professional football club," thereby automatically resolving exceptions like national team memberships.

Applying class restrictions to resolve 'noisy' constraints in sports team memberships.

Experimental Evaluation

The authors evaluated PaTeCon on three datasets: WD50K (a standard Wikidata sample), WD27M (a large-scale Wikidata dataset with 27M facts), and FB37M (a Freebase dataset with 37M facts).

  • Precision: On WD50K, PaTeCon mined 13 constraints, all of which were rated as "Correct" by human annotators, outperforming manual rules which had a 25% error rate.
  • Conflict Detection: While manual rules often flag thousands of false positives due to lack of granularity, PaTeCon identified 971 high-precision conflicts on WD50K.
  • Scalability: On the massive WD27M dataset, the system mined 644 constraints and detected over 703,000 conflicts, demonstrating its effectiveness for industrial-scale KG maintenance.

Conclusion and Future Work

PaTeCon demonstrates that most useful temporal constraints can be captured using simple structural patterns and refined through class-level granularity. However, the current method is limited to interactions between one or two subjects and does not yet capture quantitative durations (e.g., the typical length of a PhD program). Future work may involve combining this statistical approach with Large Language Models (LLMs) to bridge the gap between structural mining and semantic understanding.

Summary updated

Abstract

Temporal facts, the facts for characterizing events that hold in specific time periods, are attracting rising attention in the knowledge graph (KG) research communities. In terms of quality management, the introduction of time restrictions brings new challenges to maintaining the temporal consistency of KGs and detecting potential temporal conflicts. Previous studies rely on manually enumerated temporal constraints to detect conflicts, which are labor-intensive and may have granularity issues. We start from the common pattern of temporal facts and constraints and propose a pattern-based temporal constraint mining method, PaTeCon. PaTeCon uses automatically determined graph patterns and their relevant statistical information over the given KG instead of human experts to generate time constraints. Specifically, PaTeCon dynamically attaches class restriction to candidate constraints according to their measuring scores.We evaluate PaTeCon on two large-scale datasets based on Wikidata and Freebase respectively. The experimental results show that pattern-based automatic constraint mining is powerful in generating valuable temporal constraints.
BibTeX
@inproceedings{chen2023patecon,
  author = {Jianhao Chen and Junyang Ren and Wentao Ding and Yuzhong Qu},
  title = {{PaTeCon: A Pattern-Based Temporal Constraint Mining Method for Conflict Detection on Knowledge Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i4.25533},
}
Figure