Explaining Temporal Graph Neural Network via Quantum-Inspired Evolutionary Algorithm

Abstract Temporal Graph Neural Network (TGNN) explanation has attracted increasing attention due to its applicability in dynamic scenarios such as recommendation systems. However, existing explanation methods for TGNNs face two key limitations: (1) computational inefficiency and (2) a restricted focus on either factual or counterfactual explanations, but not both. In this paper, we propose QIEA-TGX, an efficient and unified explanation algorithm based on a quantum-inspired evolutionary algorithm. QIEA-TGX effectively generates explanatory subgraphs that significantly influence TGNN predictions, without requiring additional model training or extensive inference. Experimental results on real-world datasets demonstrate that QIEA-TGX improves explanation fidelity by up to 31% while reducing computation time by up to 92% compared to state-of-the-art baselines.