StaR: Stateful Dynamic-Graph Root Cause Analysis through Memory-Enhanced Causality Discovery

Identifying the root causes of anomalies in complex multivariate time series systems (e.g., microservices) is critical for maintaining service reliability. Although causal discovery-based approaches have gained traction, existing methods suffer largely from two fundamental limitations: they assume static causal relationships and process data in a stateless manner. In reality, modern systems exhibit dynamic topologies (e.g., due to version updates) and stateful failure patterns (e.g., slow memory leaks), where static and memoryless models fail to capture. To address these challenges, we propose StaR, a stateful RCA framework that reformulates the Granger causal discovery process by embedding Temporal Graph Networks as the underlying predictive engine. By introducing persistent memory states and dynamic message passing into the causal inference process, StaR effectively models evolving graph structures and captures long-term dependency patterns. Extensive experiments on nine datasets show that StaR consistently outperforms baselines, improving AC@1 from 0.028 to 0.920 on dynamic and stateful datasets, with strong gains on real-world datasets (0.381 to 0.752).