Training-free Counterfactual Explanation for Temporal Graph Model Inference

Temporal graph neural networks (TGNN) extends graph neural networks (GNNs) and have demonstrated promising performance for dynamic and spatiotemporal network analysis. However, interpreting TGNN over dynamic graphs remains far less explored. This paper introduces TEMporal Graph eXplainer (TemGX), a training-free, model-agnostic, and query-able framework to help users interpret and understand TGNN-based graph analysis. TemGX discovers temporal subgraphs and their evolution that are responsible for inference results of interest, in terms of temporal counterfactual analysis. We introduce a class of explainability measures that integrate spatial-temporal influence and time decay model, to capture temporal influence contextualized by sliding windows. We formulate the explanation task as a constrained optimization problem, and present fast algorithms to discover explanations with guarantees on their temporal explainability. Our experimental study verifies the effectiveness and efficiency of TemGX for TGNN explanation, compared with state-of-the-art explainers. We also showcase how TemGX supports temporal queries for interpretable dynamic network analysis.