GALACTIC: Global and Local Agnostic Counterfactuals for Time-series Clustering

This paper introduces GALACTIC, a unified framework that bridges local and global counterfactual explainability for unsupervised time-series clustering by generating minimal perturbations to cross cluster boundaries and employing a provably efficient submodular optimization algorithm to derive concise, non-redundant global summaries of these transitions.

The Gist

Imagine you have a massive library of thousands of different songs (time-series data). You want to organize them into genres like "Jazz," "Rock," and "Classical" without knowing the labels beforehand. You use a smart computer program to sort them. It works great, but there's a problem: nobody knows why a specific song ended up in the "Jazz" pile instead of the "Rock" pile.

The computer just says, "It's Jazz." But a human wants to know: "What if I changed the drum beat? Would it become Rock?" or "What is the one thing that makes this group of songs feel like Jazz?"

This paper introduces GALACTIC, a new tool that acts like a time-traveling music critic to answer those questions. It explains time-series data (like heartbeats, stock prices, or robot movements) in two ways: for individual items and for the whole group.

Here is how it works, using simple analogies:

1. The Problem: The "Black Box" Clustering

Think of your data as a giant bag of mixed-up marbles. You dump them into a machine that sorts them into red, blue, and green piles.

• The Issue: You can see the piles, but you don't know the machine's secret rule. Why did this specific marble go into the red pile?
• The Old Way: Previous tools tried to explain this by pointing at the whole marble and saying, "It's red because it's shiny." But that's vague. You need to know exactly which part of the marble to change to make it blue.

2. The Local Solution: The "What-If" Mirror

GALACTIC starts by looking at one single marble (one time-series instance).

• The Goal: It asks, "What is the smallest, easiest change I can make to this marble to move it to the Blue pile?"
• The Magic Trick (Structural Awareness): Imagine the marble is actually a long, flexible snake made of different colored segments.
  • Old tools would just randomly paint parts of the snake blue, even the parts that don't matter, making the snake look weird and unrealistic.
  • GALACTIC is smarter. It knows that for a "Jazz" song, the drums matter, but the background noise doesn't. It focuses its changes only on the critical parts (the drums). It leaves the rest of the snake alone.
  • Result: It gives you a "Counterfactual": "If you just changed the drum beat at second 10, this song would be Rock." It's a minimal, realistic edit.

3. The Global Solution: The "Summary Book"

Now, imagine you have 1,000 "Jazz" marbles. If you ask GALACTIC to explain all 1,000 of them individually, you get 1,000 different answers. That's too much information! It's like reading 1,000 different travel guides for the same city.

• The Goal: GALACTIC needs to summarize the entire group. It wants to find the top 3 or 4 rules that explain why most Jazz songs are Jazz.
• The Magic Trick (The MDL Principle): This is where the paper gets fancy with a concept called Minimum Description Length (MDL).
  • Think of MDL as a compression algorithm for explanations.
  • GALACTIC tries to find the shortest "story" that explains the most marbles.
  • If it finds a rule that explains 90% of the marbles with just one sentence, it picks that. If it needs 100 sentences to explain the last 10%, it might decide that's too much effort and stop.
  • It uses a mathematical guarantee (Submodularity) to ensure it finds the best summary without checking every single possibility (which would take forever).

4. Why is this better than the competition?

• Old Tools: They were like a blunt hammer. They would smash the whole marble to change its color, or they would give you a summary that was too long and confusing.
• GALACTIC: It's like a scalpel.
  • Locally: It cuts only the specific thread that holds the song in the "Jazz" category, leaving the rest of the song intact.
  • Globally: It writes a concise "Cliff's Notes" version of the genre, telling you the essential features that define the group, ignoring the noise.

The Big Picture

GALACTIC bridges the gap between "I know the computer sorted this" and "I understand why and how to change it."

• For a Doctor: "Your heart rate looks like 'Group A'. If you slow down the rhythm only during the night, it would look like 'Group B' (which is healthier)."
• For a Banker: "This stock pattern is 'Group A' (Risky). If you smooth out the spikes only on Tuesday mornings, it becomes 'Group B' (Safe)."

In short, GALACTIC turns a mysterious black box into a transparent, interactive guide that tells you exactly what to tweak to change the outcome, without breaking the reality of the data.

Technical Summary

1. Problem Definition

Time-series clustering is essential for discovering patterns in temporal data across domains like finance, healthcare, and robotics. However, these clusters are often "black boxes," leaving practitioners unable to understand why a specific time series belongs to a cluster or how it could be modified to transition to a different cluster.

Existing explainability methods face two main limitations:

1. Supervised Bias: Most Counterfactual Explanation (CE) methods are designed for supervised classification (label flipping) and do not address the unsupervised nature of clustering, where cluster boundaries are latent and defined by distance metrics (e.g., DTW) rather than explicit labels.
2. Lack of Global Synthesis: Current methods focus on local (instance-level) explanations. They fail to aggregate thousands of local counterfactuals into a concise, global summary that characterizes the structural transitions between entire clusters.

The Goal: To develop a unified, model-agnostic framework that generates both local (instance-specific) and global (cluster-level) counterfactual explanations for time-series clustering, ensuring the explanations are sparse, structurally coherent, and computationally efficient.

---

2. Methodology: The GALACTIC Framework

GALACTIC operates in two distinct phases: Local Generation and Global Selection.

A. Local Counterfactual Generation (Galactic-L)

The goal is to find a minimal perturbation $\delta$ for an instance $x$ such that the perturbed instance $x' = x + \delta$ is assigned to a different cluster.

1. Probabilistic Surrogate: Since many clustering algorithms (e.g., spectral clustering) lack an explicit out-of-sample mapping function, GALACTIC first trains a probabilistic surrogate classifier $g$ to approximate the cluster assignments of the original clustering algorithm.
2. Structural Segmentation & Subgrouping:
   • Time series are segmented into contiguous regions using change-point detection.
   • Instances within a cluster are further grouped into subgroups based on their segmentation patterns (using $K$-medoids on gap vectors) to capture internal cluster variability.
3. Importance-Guided Optimization:
   • Instead of penalizing changes in the loss function, GALACTIC uses a hard constraint mask derived from permutation analysis.
   • It calculates the importance of specific temporal segments by shuffling them and measuring the drop in surrogate accuracy.
   • The optimization gradient is projected onto these high-importance regions, ensuring perturbations only occur in discriminative temporal segments, preserving the global shape of the time series.
4. Target Selection: The framework identifies the "second possible" cluster (the one with the next-highest probability) as the target to ensure efficient transition paths.

B. Global Counterfactual Selection (Galactic-G)

The goal is to select a small, non-redundant set of perturbations that explain transitions for the majority of a cluster's population.

1. Candidate Pool Generation: Local counterfactuals are generated for a representative subset of instances (prototypes and criticisms) to form a candidate pool of perturbations $\Delta_k$.
2. Minimum Description Length (MDL) Formulation:
   • The selection problem is framed as an Information-Theoretic optimization.
   • The objective function $L(D, M) = L(M) + L(D|M)$ balances:
     • Model Complexity ($L(M)$): Penalizes the number of perturbations, their sparsity (number of changed timesteps), and magnitude.
     • Data Length ($L(D|M)$): Penalizes instances that remain uncovered (fail to flip clusters) by the selected set.
3. Submodularity & Greedy Selection:
   • The authors prove that the MDL objective is supermodular, meaning the reduction in description length (the gain) is a monotone submodular set function.
   • This theoretical property allows the use of a greedy selection algorithm with a provable $(1 - 1/e)$ approximation guarantee.
   • Hierarchical Refinement: To handle scalability, a hierarchical approach is proposed: first selecting perturbations for subgroups, then refining the selection at the cluster level. This drastically reduces computational complexity while maintaining high coverage.

---

3. Key Contributions

1. Unified Framework: The first framework to bridge local and global counterfactual explainability specifically for unsupervised time-series clustering.
2. Structural Constraints: Introduction of a gradient-based optimization method that uses subgroup-specific importance masks to ensure counterfactuals are sparse and preserve the temporal structure of the data.
3. MDL-Based Global Selection: A novel formulation of the global explanation problem using the Minimum Description Length principle. This resolves the multi-objective trade-off between coverage and complexity without requiring manual hyperparameter tuning.
4. Theoretical Guarantees: Proof that the MDL objective is supermodular, enabling efficient greedy algorithms with theoretical approximation bounds.
5. Adaptive Hierarchical Mechanism: A scalable selection strategy that adapts to the internal density and complexity of cluster subgroups.

---

4. Experimental Results

The framework was evaluated on 30 datasets from the UCR Time-Series Archive.

• Local Performance (Galactic-L):
  • Effectiveness: Outperformed baselines (k-NN, TSEvo, Glacier) in successfully flipping cluster assignments.
  • Sparsity: Produced significantly sparser explanations (fewer changed timesteps and segments) compared to evolutionary and gradient-based baselines.
  • Efficiency: Was orders of magnitude faster than evolutionary methods (TSEvo) and consistently faster than gradient-based methods (Glacier).
• Global Performance (Galactic-G):
  • Coverage vs. Cost: Achieved superior effectiveness-to-cost trade-offs compared to adapted baselines (GLOBE-CE*, Glacier-G*).
  • Interpretability: Generated concise summaries (small sets of perturbations) that covered large portions of the cluster population, whereas baselines often required large, incoherent sets of perturbations.
  • Scalability: The Hierarchical Greedy variant demonstrated high scalability, making it suitable for large datasets.

---

5. Significance and Impact

• Bridging the Gap: GALACTIC addresses a critical gap in Explainable AI (XAI) by moving beyond supervised classification to the unsupervised realm of clustering, where "ground truth" labels do not exist.
• Actionable Insights: By providing both local (how to change this specific series) and global (how to change any series in this cluster) explanations, it transforms clustering from a descriptive tool into a decision-support system.
• Theoretical Rigor: The application of MDL and submodularity theory provides a mathematically sound basis for selecting global explanations, avoiding the "black box" nature of heuristic selection methods.
• Practical Utility: The framework is model-agnostic, meaning it can be applied to any clustering algorithm (e.g., k-means, spectral, DTW-based) without requiring access to the internal logic of the clustering model.

In summary, GALACTIC offers a robust, theoretically grounded, and empirically superior approach to interpreting time-series clusters, enabling users to understand the "why" and "how" of cluster membership in complex temporal data.