Resolving Temporal Graph Functional Dependency Violations

Abstract

Data is often riddled with errors and noise, from misspellings and missing values, that need to be dealt with to use the data effectively. This kind of preprocessing is very costly; an estimated cost to U.S. businesses of $3 trillion as reported in 2016 by Harvard Business Review. Temporal graphs are used to record changes in graph data, capturing both topological and attribute value constraints and relationships. As data values change, snapshots of temporal graphs may become inconsistent with respect to a set of graph quality constraints that impose topological and attribute value requirements. For example, monitoring patient drug dosages over time involves relationships between attributes such as a patient’s condition, treatment, symptoms and specific dosage values, while adhering to strict dosing requirements over specific time intervals.

This thesis studies the problem of resolving violations to a specific class of graph data quality rules called Temporal Graph Functional Dependencies (TGFDs). The thesis introduces a new algorithm called TGFD-Correct, that processes and groups all violations sharing the same antecedent values (with respect to the TGFD), and selects a single (consequent) value for each group that balances two objectives. First, fixing the data (with respect to the TGFD), and second, minimizing changes to the distribution of consequent values from a prespecified objective. As each group is being handled independently, the repair step can be run in parallel across many processor cores, making it fast enough for millions of records. Our method had a 3-point improvement over the best performing baseline that we tested from the literature, whilst maintaining a runtime footprint 17 times smaller. Taken together, the findings show that careful, distribution-aware cleaning of temporal graphs is possible, and demonstrates a path toward more flexible tools that can keep pace with ever-growing, time-stamped data.