PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Stationarity in Time Series: Discovering Causal Structures and Latent Regimes via Markov Blankets

Lei Zan, Charles K. Assaad, Emilie Devijver, Eric Gaussier

arXiv:2609.05150v1cs.LGcs.AI

TL;DR

The paper addresses causal discovery for time series whose causal structure changes across latent regimes rather than remaining stationary. RCBNB-MB jointly infers regimes and regime-specific causal graphs using Markov blankets, and experiments report accurate regime assignment on simulated data alongside validation on synthetic and real-world IT monitoring data.

  • Problem

    Time-series causal discovery often assumes a single stationary causal structure, although heterogeneous systems can contain multiple regimes with changing causal mechanisms.

  • Method

    RCBNB-MB treats regime assignment as a prediction task based on Markov blankets and simultaneously identifies regimes and reconstructs their causal graphs, including instantaneous connections.

  • Results

    RCBNB-MB achieved a Mean Error Rate of 1.27% with 2 regimes and 0.81% with 3 regimes, and was validated on synthetic and real-world IT monitoring data.

  • Takeaways & Limitations

    The approach provides a framework for uncovering regime-dependent causal structures in heterogeneous time series without treating causal relationships as time-consistent.

  • Takeaways & Limitations

    Experiments considered only linear relationships and time series with two or three regimes, while boundary timestamps remain difficult to assign correctly; consistent convergence to ground truth is not theoretically guaranteed.

Abstract

from arXiv · show

This paper introduces Regime-aware Constraint-Based and Noise-Based causal discovery with Markov Blankets (RCBNB-MB), a novel causal discovery algorithm for time series that relaxes the common assumption of a single, time-consistent causal structure. Time series are typically observed at discrete time points and often exhibit regime changes that challenge the assumption of a static causal structure, a limitation in many real-world dynamic systems. To address this challenge, RCBNB-MB identifies latent causal regimes, defined as subsets of time points within which a stable causal structure holds. The algorithm follows an iterative strategy that segments the time series into regimes and discovers the causal graph within each regime. By leveraging the Markov blanket rather than direct parents, RCBNB-MB gains robustness to errors in causal discovery and preserves predictive information. We provide theoretical guarantees for RCBNB-MB's ability to recover both regime transitions and causal graphs under reasonable assumptions. Furthermore, we validate its effectiveness through extensive experiments on simulated datasets with known ground truth and real-world IT monitoring data, where taking into account regime shifts is critical. Empirical results show that RCBNB-MB systematically outperforms baseline approaches in accurately detecting regime changes and their associated causal graphs, positioning it as a robust and versatile framework for non-stationary time series analysis.

1 Introduction

Time-series causal discovery often assumes stationary causal dependencies, although real systems can undergo regime shifts driven by unobserved factors. The paper proposes RCBNB-MB, which jointly infers regimes and regime-specific causal graphs using Markov blankets to improve robustness.

  • Causal discovery methods commonly assume causal dependencies remain constant, but regime shifts can change causal influences due to unobserved factors.
  • The paper frames regime assignment as a prediction task and uses Markov blankets instead of parent sets to reduce sensitivity to graph-estimation errors.A Markov blanket contains a variable’s parents, children, and spouses.
  • RCBNB-MB simultaneously identifies regimes and reconstructs regime-specific causal graphs, including instantaneous connections.
  • The method is empirically validated on synthetic and real-world IT monitoring data for uncovering regime-dependent causal structures.
  • The paper presents RCBNB-MB as a method for heterogeneous time series and organizes experiments around its causal model, algorithm, and evaluation.

2 Related work

Related work on non-stationary time series includes methods that infer regimes or causal structures under differing assumptions. The paper emphasizes settings without predefined contexts and the importance of handling changing causal relations and instantaneous connections.

  • Prior work studies causal discovery when temporal consistency is violated because causal relationships evolve across time or regimes.
  • Existing approaches may require predefined regime information, fixed causal order or skeletons, sequential periodic mechanisms, or i.i.d. data assumptions.
  • Figure 1 contrasts full-time and window causal graphs for two regimes, with the latent regime variable C_t requiring inference.
  • Several methods infer regimes using causal parents, while related approaches may omit instantaneous connections between observed time series.

3 Causal modeling for heterogeneous time series

The paper models heterogeneous multivariate time series with unobserved regime indicators that determine regime-specific causal structures. It assumes within-regime causal consistency while allowing instantaneous links and non-contiguous regimes.

  • Regime-based causal model: A hidden context variable C_t assigns each time point to one of r regimes and determines the regime-specific causal structure.The number of regimes is not assumed known through observed assignments; C_t directly influences all variables at time t.
  • Model assumption: The framework assumes that all hidden confounding among observed variables is captured by the regime context variables.
  • Within-regime stationarity: Within each regime, causal relationships are assumed invariant over time, allowing analysis through finite-window causal graphs rather than the full-time graph.The window length τ_max represents the maximum lag between direct causes and effects; invariance breaks at regime boundaries.
  • Regime-based causal model: A regime-based time series partitions observations into disjoint regimes with distinct window causal graphs.Distinct regimes must have different window causal graphs, G^k_w.
  • Causal structure: The model permits both lagged and instantaneous causal relations, with independent noise terms across variables and time.Regimes may span multiple non-adjacent intervals, so they need not correspond to single contiguous segments.

4 Causal discovery from heterogeneous time series

RCBNB-MB alternates between discovering regime-specific causal graphs and reassigning time points using Markov-blanket-based prediction. Its guarantees depend on causal-discovery and identifiability assumptions, while transition assignments and global convergence retain practical limitations.

  • Problem formulation: The causal-discovery task jointly reconstructs each regime’s causal graph and assigns every timestamp to its correct regime.
  • RCBNB-MB procedure: RCBNB-MB alternates graph estimation from current assignments with regime reassignment under newly estimated graphs.The number of regimes r is assumed known for the procedure described.
  • Causal graph discovery: CBNB combines constraint-based skeleton discovery and noise-based orientation to recover lagged and instantaneous causal edges.Lagged edges use temporal ordering, while remaining instantaneous edges are oriented using restricted noise-based estimation with lagged covariates.
  • Causal graph discovery: CBNB requires adjacency faithfulness and an identifiable functional model, under which it correctly recovers the regime-specific causal graph when regime assignments are correct.The result also assumes consistency throughout time and perfect conditional-independence tests.
  • Markov-blanket regime assignment: Regime assignment uses predictors based on each variable’s Markov blanket and selects the regime with the lowest overall prediction error.Ties are resolved using the smallest Markov blanket, with the criterion supported by a theoretical regime-assignment result.
  • RCBNB-MB procedure: The algorithm alternates CBNB graph estimation and Markov-blanket construction with constrained updates of the assignment vector.Each regime must contain at least N_l observations and the assignments allow at most N_c transitions.
  • Guarantees and limitations: Correct assignments allow Step 1 to recover true window graphs and Markov blankets as regime sample sizes grow, but transition assignments may be less accurate with limited past data.The transition effect is described as negligible when regime changes are sparse.
  • Guarantees and limitations: RCBNB-MB has no theoretical guarantee of consistent convergence to the ground truth, although experiments report outputs often close to ground truth in most cases.

5 Experiments

The experiments evaluate regime assignment and causal graph reconstruction on simulated and real-world IT monitoring data. RCBNB-MB generally achieves accurate regime detection and graph recovery, with Markov-blanket variants outperforming parent-based approaches.

  • Evaluation: The experiments measure regime-assignment accuracy with MER and causal graph reconstruction using oriented F1-score and normalized SHD.MER counts incorrectly assigned timestamps after resolving regime-label permutations; nSHD counts missing, spurious, and reversed instantaneous edges.
  • Simulated data: RCBNB-MB achieves MER values of 1.27% for two regimes and 0.81% for three regimes on simulated data.These correspond to approximately 8 misclassified timestamps out of 600 in the two-regime scenario; CASTOR exceeds 20%.
  • Simulated data: RCBNB-MB obtains the highest F1-scores, reaching 0.73 with two regimes and 0.66 with three regimes.The reported F1-scores summarize recovery of causal structures under the evaluated simulated conditions.
  • Simulated data: RCBNB-MB has the lowest nSHD in both scenarios, with values of 0.52 and 0.55, indicating graph structures closest to ground truth.Most competing methods obtain nSHD values close to or above 1.
  • Method comparison: Markov-blanket variants generally outperform parent-based variants because blankets include parents, children, and spouses, improving predictive information and reducing sign errors.The paper connects this predictive robustness to the reliability of the subsequent causal-discovery step.
  • Real-world data: On real IT monitoring data, RCBNB-MB detects the normal and abnormal regimes under two- and three-regime specifications, with a possible transitional boundary regime.The data contain eight one-minute time series and an expert-identified anomaly interval from timestamps 46,683 to 46,783.

6 Conclusion and Perspective

The paper presents RCBNB-MB as a method for discovering regime-dependent causal structures in heterogeneous time series. Empirical validation on synthetic and real-world IT monitoring data supports its effectiveness, while the authors identify important scope boundaries for future work.

  • Conclusion: RCBNB-MB treats regime assignment as a prediction task based on Markov blankets and recovers causal structures separately across regimes.The paper supports this design with theoretical and experimental arguments.
  • Conclusion: The method is empirically validated on synthetic and real-world IT monitoring data for uncovering regime-dependent causal structures.The conclusion states effectiveness within these evaluated settings.
  • Perspective: Experiments considered only linear relationships and time series with two or three distinct regimes.Nonlinear relationships and more than three regimes remain untested.
  • Perspective: Boundary timestamps are difficult to assign because information about the Markov blanket is lost at regime transitions.The authors identify improving boundary assignment as future work.

A Proof of Theorem 1

The paper’s algorithm iteratively estimates regime-specific causal graphs and updates regime assignments by minimizing an empirical risk objective. Within each regime, it uses Markov blankets to construct predictive representations before producing the final assignments and graphs.

  • Algorithm: RCBNB-MB initializes multiple segmentations and alternates between causal-graph estimation and regime-assignment updates.Assignments are updated by minimizing the empirical risk function subject to the stated constraints.
  • Algorithm: For each regime, CBNB estimates a window causal graph and the Markov blanket of every variable.The Markov blanket is the smallest variable set rendering a target conditionally independent of all others within the regime graph.
  • Algorithm: The procedure evaluates multiple initializations, retains their objective values, and selects the initialization with the minimum final loss.The selected assignment and regime-specific graphs are returned as the algorithm output.

C.1 Parameter Robustness

Sensitivity analysis varies initialization points, optimization iterations, and minimum regime size across 50 simulated datasets. Performance improves modestly with more initialization points or iterations, while remaining largely insensitive to minimum regime size.

  • Experimental design: The sensitivity analysis uses 50 simulated datasets with six variables and time series length 600.Each hyperparameter is varied independently while the other two remain fixed.
  • Initialization points: Increasing the number of initialization points gradually raises mean F1-score and lowers MER.The standard deviation remains approximately constant across the tested values of Ni.
  • Optimization iterations: Increasing the maximum number of optimization iterations produces a modest F1-score increase and generally decreases MER.MER shows a transient peak at No = 10 despite the overall declining trend.
  • Minimum regime size: Varying the minimum regime size from 6 to 30 leaves both F1-score and MER approximately flat.The parameter safeguards statistically well-posed regression and causal-discovery steps and prevents empty regimes.

C.2 Simulated Data with a Length of 1,200

On simulated series of length 1,200, RCBNB-MB detects regime changes accurately, reconstructs causal graphs well, and remains stable across repetitions.

  • RCBNB-MB achieves a MER of 0.14% in the 2-regime scenario and 0.64% in the 3-regime scenario.CASTOR exceeds 23% MER, indicating difficulty detecting regime changes.
  • RCBNB-MB maintains an F1-score of 0.71 in both the 2-regime and 3-regime scenarios.RCBNB-PA reaches 0.72 in the 2-regime scenario, while RPCMCI-PA scores around 0.58.
  • RCBNB-MB obtains the lowest nSHD, with 0.48 for 2 regimes and 0.55 for 3 regimes.These results indicate graph structures closest to the ground truth.
  • Most methods have variance around 0.01, while RPCMCI+ reaches up to 0.09 across repetitions.The results indicate generally stable performance, with greater variability for RPCMCI+.

C.4 Simulated Data with Unequal Regime Sizes

With unequal regime sizes, RCBNB-MB remains the strongest method for regime assignment and graph recovery, while longer series improve reconstruction accuracy and performance remains stable across repetitions.

  • RCBNB-MB achieves the best F1-scores in both scenarios, reaching 0.63 for 2 regimes and 0.59 for 3 regimes.F1-scores decrease slightly with three regimes and relative to equal regime sizes, but RCBNB-MB remains highest.
  • RCBNB-MB achieves the lowest nSHD for length-600 series, with 0.61 for 2 regimes and 0.67 for 3 regimes.The result indicates the most accurate structural recovery under unequal regime sizes.
  • For length-1,200 series, RCBNB-MB has MER of 0.63% and F1-scores of 0.66 and 0.65 for 2 and 3 regimes.The MER generally decreases with longer series, suggesting more information for regime assignment.
  • For length-1,200 series, RCBNB-MB obtains nSHD of 0.58 for 3 regimes and 0.56 for 2 regimes, tied with RPCMCI+-MB.Its nSHD decreases relative to length 600, suggesting improved graph reconstruction with longer series.
  • RCBNB-MB maintains nSHD variance between 0.02 and 0.03 across repetitions.F1-score variances are typically around 0.01, while RPCMCI+-based methods reach approximately 0.11.

C.5 Simulated Data with 15 Variables

In a higher-dimensional setting with 15 variables and unequal regime sizes, RCBNB-MB achieves the best overall graph-recovery performance and maintains low variability.

  • RCBNB-MB achieves the best F1-score under all conditions, with 0.49 total, 0.56 for lagged edges, and 0.45 for instantaneous edges.Absolute F1 levels are lower than in the six-variable setting, reflecting increased task difficulty.
  • RCBNB-MB achieves MER of 0.07%, while RPCMCI+-PA and CASTOR reach 39.16% and 54.44%, respectively.Within each method family, Markov-blanket variants have MER no higher than parent-only variants.
  • RCBNB-MB achieves the lowest nSHD, with 0.77, followed by RCBNB-PA at 0.79 and RPCMCI+-MB at 0.83.The results indicate graph structures closest to the ground truth in the higher-dimensional setting.

D Real data: some details

The real-data evaluation uses eight one-minute-sampled IT-monitoring series from EasyVista and compares methods implemented through publicly available Python libraries.

  • The dataset contains eight time series collected from an IT monitoring system at a one-minute sampling rate.The series capture activities including message ingestion, metric extraction, database insertion, Cassandra updates, and Elasticsearch writing.
  • The evaluated methods were implemented using publicly available Python libraries.The listed implementations include Causal-learn, CausalNex, Tigramite, NegControl, and CASTOR repositories.
Loading 2609.05150v1…