Discovery of Temporal Graph Functional Dependencies

Abstract

Real-world graphs are dynamic and evolve over time. Data quality in evolving graphs is essential to downstream decision making and fact checking. This work studies the discovery of Temporal Graph Functional Dependencies (TGFDs), a recently defined class of data quality rules for enforcing consistency over evolving graphs. TGFDs impose topological and attribute dependency constraints over a period of time. We define minimality and support for TGFDs and formalize the TGFD discovery problem. Defining TGFDs manually is a laborious task and requires domain expertise. Hence, we introduce TGFDMiner, a sequential algorithm that discovers minimal and frequent TGFDs. We define various optimizations for TGFDMiner that improve runtime.