TL;DR
GALACTIC is the first unified, model-agnostic framework providing both local and global counterfactual explanations for unsupervised time-series clustering. By combining importance-guided gradient optimization with an information-theoretic selection strategy, it reveals the minimal, shape-preserving changes required to shift time-series data across cluster boundaries.
What Problem Does This Paper Address?
Time-series clustering is a vital tool for discovering patterns in complex temporal data, from financial market regimes to brain activity profiles. However, these pipelines are notoriously opaque. Because they often rely on complex, non-linear distance metrics (like Dynamic Time Warping) or multi-stage feature transformations, practitioners are left with cluster labels but no clear understanding of why a sequence belongs to a specific group, or how its behavior would need to change to transition to another.
Counterfactual Explanations (CEs) solve this in supervised learning by showing the minimal edits needed to flip a model's prediction. But translating CEs to unsupervised clustering introduces two major hurdles:
- No explicit labels: Clustering algorithms define boundaries implicitly over a data manifold, making direct gradient-based optimization difficult.
- The scaling problem: While you can generate a local counterfactual for a single sequence, distilling thousands of individual local edits into a concise, global summary that explains cluster transitions as a whole is a massive combinatorial challenge.
Methods
GALACTIC addresses these challenges using a two-level framework:
1. Local Counterfactuals (GALACTIC-L)
To bypass the lack of explicit cluster decision formulas, GALACTIC first trains a deep 1D convolutional residual network as a probabilistic surrogate classifier to mimic the black-box clustering assignments.
To ensure that the generated edits are realistic and preserve the original structure of the time series, GALACTIC-L uses an importance-guided perturbation strategy:
- Segmentation & Subgrouping: It breaks down the time series into contiguous segments using change-point detection and groups similar structural behaviors using K-medoids.
- Importance Masking: It runs a block-wise permutation analysis to identify which temporal segments most heavily influence cluster membership. This generates a binary mask ($w$).
- Hard Gradient Projection: Instead of adding a soft penalty to the loss function, GALACTIC applies this mask as a hard constraint directly to the gradient during optimization ($\nabla \leftarrow \nabla \mathcal{L} \odot w$). This restricts edits strictly to discriminative regions, leaving characteristic shapes intact.
2. Global Counterfactual Summaries (GALACTIC-G)
To scale these insights to the cluster level, GALACTIC extracts a concise set of global "perturbation patterns" (as illustrated conceptually in Figure 1):
- Candidate Pool Generation: It selects a representative subset of instances (prototypes and outliers) using the MMD-Critic algorithm to generate a high-quality pool of local counterfactuals.
- Minimum Description Length (MDL) Selection: Instead of manually tuning weights to balance explanation coverage (how many sequences flip clusters) versus complexity (how large/dense the edits are), GALACTIC frames global selection as an information-theoretic model selection problem. It searches for the smallest set of perturbations that yields the shortest joint description length of the model and data.
- Submodular Optimization: The authors prove that this MDL objective behaves as a monotone supermodular set function. This mathematical property allows them to implement a greedy selection algorithm that guarantees a $(1 - 1/e)$ approximation of the absolute optimal summary.
Datasets
The framework was extensively evaluated using 30 diverse datasets from the UCR Time-Series Archive, covering domains such as:
- Medical/ECG: ECG200, ECG5000, ECGFiveDays, TwoLeadECG
- Motion/Sensor: Car, InlineSkate, ItalyPowerDemand, ToeSegmentation2, Worms
- Device/Image: ACSF1, ArrowHead, Computers, FaceFour, Lightning7
The ground-truth classification labels from the archive were treated as the target cluster partitions to evaluate how well the framework uncovers latent boundaries.
Key Insights and Ideas
- Hard Constraints Over Soft Penalties: Forcing the gradient to zero in non-essential regions prevents the "leakage" of noise across the time series. This keeps edits highly localized compared to prior methods that rely on soft loss penalties.
- MDL Eliminates Hyperparameter Tuning: Global recourse methods usually suffer from incomparable Pareto fronts, forcing users to arbitrarily balance explanation size against accuracy. The MDL formulation elegantly unifies these competing goals into a single, parameter-free communication metric.
- Submodularity Guarantees Efficiency: Proving the submodularity of the MDL reduction means that a simple, fast greedy algorithm can be used to find global summaries with provable near-optimal quality, avoiding prohibitive brute-force searches.
Key Results
- Sparser Local Edits: GALACTIC-L consistently produced counterfactuals that altered significantly fewer segments (Average Changed Segments) and individual timesteps (Average Changed Timesteps) than state-of-the-art baselines like TSEvo and Glacier, while maintaining near-100% effectiveness.
- Drastic Speedups: GALACTIC-L achieved its results orders of magnitude faster than evolutionary algorithms (like TSEvo) and consistently outpaced other gradient-based approaches.
- Concise Global Summaries: GALACTIC-G variants significantly outperformed adapted global baselines (like GLOBE-CE* and Glacier-G*), providing higher population coverage with lower average flipping costs and cleaner, more interpretable global transition rules.
Limitations and Future Work
- Univariate Restriction: The current framework is designed strictly for univariate time series. The authors note that extending this formalism to multivariate settings is a key next step.
- Latent Confounders: The optimization does not currently account for underlying causal relationships between different time steps, which could be improved by integrating causal discovery mechanisms.
- Domain Generalization: While designed for time series, the authors suggest that the core MDL-based global selection framework could be adapted to tabular data domains for broader explainability applications.
Summary updated