Explaining Missing Data in Graphs: A Constraint-based Approach
Qi Song, Peng Lin, Hanchao Ma, Yinghui Wu · 2021
This paper introduces a constraint-based approach to clarify missing values in graphs. Our method capitalizes on a set Σ of graph data constraints. An explanation is a sequence of operational enforcement of Σ 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 Σ-explanation problem, which is to compute the optimal explanations with guarantees on the informativeness and conciseness. We show the problem is in Δ2Pfor established graph data constraints such as graph keys and graph association rules. We develop an efficient bidirectional algorithm to compute optimal explanations, without enforcing Σ 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.