  Data dependencies have been extended to graphs to characterize topological
and value constraints. Existing data dependencies are defined to capture
inconsistencies in static graphs. Nevertheless, inconsistencies may occur over
evolving graphs and only for certain time periods. The need for capturing such
inconsistencies in temporal graphs is evident in anomaly detection and
predictive dynamic network analysis. This paper introduces a class of data
dependencies called Temporal Graph Functional Dependencies (TGFDs). TGFDs
generalize functional dependencies to temporal graphs as a sequence of graph
snapshots that are induced by time intervals, and enforce both topological
constraints and attribute value dependencies that must be satisfied by these
snapshots. (1) We establish the complexity results for the satisfiability and
implication problems of TGFDs. (2) We propose a sound and complete
axiomatization system for TGFDs. (3) We also present efficient parallel
algorithms to detect inconsistencies in temporal graphs as violations of TGFDs.
The algorithm exploits data and temporal locality induced by time intervals,
and uses incremental pattern matching and load balancing strategies to enable
feasible error detection in large temporal graphs. Using real datasets, we
experimentally verify that our algorithms achieve lower runtimes compared to
existing baselines, while improving the accuracy over error detection using
existing graph data constraints, e.g., GFDs and GTARs with 55% and 74% gain in
F1-score, respectively.
