DOE OSTI · 1821698
Explaining Missing Data in Graphs: A Constraint-based Approach
Abstract
Abstract: This paper introduces a constraint-based approach to clarify missing values in graphs. Our method capitalizes on a set S of graph data constraints. An explanation is a sequence of operational enforcement of S towards the recovery of interested yet missing data (e.g., attribute values, edges). We show that constraint-based approach helps us to understand not only why a value is missing, but also how to recover the missing value. We study S-explanation problem, which is to compute the optimal explanations with guarantees on the informativeness and conciseness. We show the problem is in ?P^2 for established graph data constraints such as graph keys and graph association rules. We develop an efficient bidirectional algorithm to compute optimal explanations, without enforcing S on the entire graph. We also show our algorithm can be easily extended to support graph refinement within limited time, and to explain missing answers. Using real-world graphs, we experimentally verify the effectiveness and efficiency of our algorithms.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Song, Qi, Lin, Peng, Ma, Hanchao, Wu, Yinghui. 2021-06-06. Explaining Missing Data in Graphs: A Constraint-based Approach. https://www.osti.gov/biblio/1821698
Cite the original work for its findings. Save a collection to share your selection of sources.