MCbiF: Measuring Topological Autocorrelation in Multiscale Clusterings via 2-Parameter Persistent Homology

This paper introduces the Multiscale Clustering Bifiltration (MCbiF), a 2-parameter topological framework that encodes non-hierarchical multiscale clusterings to extract stable, interpretable features via multiparameter persistent homology, demonstrating superior performance in machine learning tasks and real-world applications compared to existing methods.

The Gist

The Big Picture: The "Shape" of Changing Groups

Imagine you are watching a flock of birds.

• At 9:00 AM: They are one big, loose cloud.
• At 9:15 AM: They split into three smaller flocks.
• At 9:30 AM: Two of those flocks merge, but a third one splits in half.
• At 9:45 AM: They all merge back into one giant cloud.

This is a multiscale clustering sequence. The birds are constantly grouping and regrouping.

Now, imagine you are a data scientist trying to understand this behavior.

• If the birds just split and never merged back (or merged and never split), it's a simple tree (like a family tree). We have great tools to analyze trees.
• But in the real world (like social networks, protein structures, or mouse colonies), groups often split, merge, cross over, and reorganize in messy, non-tree-like ways.

The Problem: Existing tools are like trying to measure a tangled ball of yarn with a ruler meant for straight lines. They can compare two snapshots (e.g., "How different is 9:15 from 9:30?"), but they miss the story of how the groups evolved over time. They miss the "topological autocorrelation"—how the shape of the groups remembers its past.

The Solution: The authors introduce MCBIF (Multiscale Clustering Bifiltration). Think of this as a 3D Time-Lapse Camera that doesn't just take pictures, but builds a mathematical sculpture of the entire history of the groups.

---

The Core Concept: The "Sandwich" of Time

To understand MCBIF, imagine you are looking at a sequence of partitions (groupings) over time.

1. The Standard View (1-Parameter): Usually, we look at a sequence from start to finish. It's like watching a movie from beginning to end.
2. The MCBIF View (2-Parameter): MCBIF asks two questions at once:
   • Start Time ($s$): When did we start watching?
   • End Time ($t$): When did we stop watching?

By varying both the start and end times, MCBIF creates a grid of possibilities. It asks: "If I look at the groupings between Tuesday and Thursday, what does the structure look like? What if I look at Wednesday to Friday?"

This creates a Bifiltration (a two-way filtration). It's like looking at a loaf of bread not just by slicing it from top to bottom, but also by slicing it from left to right, creating a grid of tiny cubes that capture every possible "slice of history."

---

The Magic Tool: "Persistent Homology" as a Detective

The paper uses a branch of math called Topological Data Analysis (TDA). Think of TDA as a detective that looks for holes and loops in data.

In the context of the bird flock (or mice, or social networks), the MCBIF tool looks for two specific types of "conflicts" or "glitches" in the story:

1. The "0-Dimensional Conflict" (The Missing Boss)

• The Metaphor: Imagine a company. In a perfect hierarchy, every employee reports to one boss, who reports to a CEO. It's a clean tree.
• The Glitch: What if Employee A reports to Boss X on Monday, but on Tuesday, Employee A reports to Boss Y, and Boss X and Boss Y don't talk to each other?
• The Result: There is no single "Boss" for the whole week. The chain of command is broken.
• MCBIF's Job: It counts these broken chains. If the groups are messy and don't have a clear "top" or "bottom" in a specific time window, MCBIF flags it as a 0-conflict. It measures how "non-hierarchical" the data is.

2. The "1-Dimensional Conflict" (The Impossible Loop)

• The Metaphor: Imagine a group of friends: Alice, Bob, and Charlie.
  • Alice and Bob are best friends (in the same group).
  • Bob and Charlie are best friends.
  • Charlie and Alice are best friends.
  • But... Alice and Charlie are never in the same group together at the same time.
• The Glitch: This creates a loop or a cycle in the social structure. It's a "hole" in the logic. If you try to draw this on a piece of paper without the lines crossing, you can't.
• MCBIF's Job: It counts these loops. These are 1-conflicts. They represent higher-order inconsistencies where the groups form a circle of relationships that can't be flattened into a simple tree.

---

The "Sankey Diagram" Upgrade

You might know Sankey diagrams. They are those flow charts where lines move from left to right, showing how things split and merge (like energy flow or website traffic).

• Old Sankey: Just shows lines crossing. If lines cross, it looks messy.
• MCBIF Sankey: The authors show that MCBIF is a higher-order Sankey diagram.
  • It doesn't just count how many lines cross.
  • It counts the loops formed by the crossings.
  • It tells you why the diagram is messy. Is it just a simple crossing? Or is it a complex, unresolvable loop?

---

Why Does This Matter? (The Experiments)

The authors tested this on two things:

1. Predicting Messiness (Regression):

   • Task: Can we predict how "crossed" a Sankey diagram will be just by looking at the data?
   • Result: Yes! The MCBIF features (the counts of 0-conflicts and 1-conflicts) were much better at predicting the messiness than standard methods. It's like being able to predict traffic jams by looking at the road layout, rather than just counting cars.

2. Sorting Data (Classification):

   • Task: Can we tell if a sequence of groups follows a logical order (like a ranking) or if it's chaotic?
   • Result: MCBIF was incredibly accurate (97% accuracy). Standard methods failed, essentially guessing randomly. MCBIF could "see" the hidden loops that made the data chaotic.

3. Real World: Wild Mice:

   • They applied this to real data of wild mice social groups over 9 weeks.
   • Finding: They found that at certain time scales, the mice groups were very stable and hierarchical (like a family). At other scales, the groups were chaotic and looping (like a party where everyone is swapping partners). MCBIF quantified exactly how chaotic the social life of the mice was.

---

Summary: The "Autocorrelation" of Shape

The paper's title mentions "Topological Autocorrelation."

• Autocorrelation usually means: "How much does today look like yesterday?"
• Topological Autocorrelation means: "How much does the shape of the groups today remember the shape of the groups yesterday?"

MCBIF is a new mathematical lens that lets us see not just what the groups are, but how they remember their past. It turns messy, non-hierarchical data into a clear map of conflicts and loops, allowing computers to understand complex, changing systems better than ever before.

In one sentence: MCBIF is a tool that turns the messy history of changing groups into a mathematical map of "loops" and "broken chains," helping us understand the hidden structure of complex, evolving data.

Technical Summary

1. Problem Definition

Many real-world datasets exhibit intrinsic multiscale structures where meaningful descriptions exist at different levels of coarseness (e.g., social groupings over time, topic modeling, single-cell data). Traditionally, these are modeled as hierarchical clusterings (dendrograms). However, many applications involve non-hierarchical sequences of partitions where clusters can split, merge, and recombine in complex ways that do not follow a strict refinement order (e.g., temporal clustering, diffusion-based clustering).

The Core Challenge:
Existing methods for comparing partitions (e.g., Adjusted Rand Index, Variation of Information, Conditional Entropy) are primarily pairwise and fail to capture higher-order inconsistencies or memory effects across a sequence. Furthermore, standard topological tools like ultrametrics and dendrograms are insufficient for non-hierarchical data because they rely on the triangle inequality and tree structures, which non-hierarchical sequences violate. The paper addresses the need for a complete, interpretable invariant to analyze and compare non-hierarchical, multi-resolution sequences of partitions.

2. Methodology: The Multiscale Clustering Bifiltration (MCbiF)

The authors introduce the Multiscale Clustering Bifiltration (MCbiF), a novel topological object that encodes the intersection patterns of clusters across a sequence of partitions $\theta$.

A. Mathematical Construction

Given a sequence of partitions $\theta: [t_1, \infty) \to \Pi_X$ (where $\Pi_X$ is the space of partitions of set $X$), the MCbiF is defined as a 2-parameter filtration of abstract simplicial complexes $K_{s,t}$:
$$K_{s,t} := \bigcup_{t_1 \le s \le r \le t} \bigcup_{C \in \theta(r)} \Delta_C$$

• Parameters: $s$ is the starting scale, and $t$ is the end scale (lag $t-s$).
• Structure: Each cluster $C$ in a partition $\theta(r)$ (where $r \in [s, t]$) is represented as a solid simplex $\Delta_C$. The complex $K_{s,t}$ is the union of all such simplices.
• Interpretation: A $k$-simplex exists in $K_{s,t}$ if $k+1$ elements have been assigned to the same cluster at least once within the time interval $[s, t]$.

B. Nerve-Based Construction

To improve computational efficiency, the authors propose a nerve-based MCbiF ($\tilde{M}$). Instead of using elements of $X$ as vertices, the vertices represent the clusters themselves. This construction is homotopy equivalent to the original MCbiF but significantly reduces dimensionality when the number of scales is smaller than the size of the largest cluster.

C. Topological Invariants: Multiparameter Persistent Homology (MPH)

The authors apply Multiparameter Persistent Homology to the MCbiF. They prove that the resulting persistence module is finitely presented and block-decomposable, ensuring algebraic stability.

• Hilbert Functions ($HF_k(s, t)$): The primary invariants used are the ranks of the homology groups $H_k(K_{s,t})$.
  • $HF_0(s, t)$: Counts connected components. It measures 0-conflicts (violations of the refinement order).
  • $HF_1(s, t)$: Counts 1-dimensional holes. It measures 1-conflicts (higher-order inconsistencies where cluster assignments form non-bounding cycles across scales).

D. Quantitative Measures

Two global, history-dependent metrics are derived from the Hilbert functions:

1. Average 0-Conflict ($\bar{c}_0$): Quantifies the lack of a maximal partition in a subposet (non-hierarchy).
2. Average 1-Conflict ($\bar{c}_1$): Quantifies higher-order inconsistencies (non-nestedness and cycle formation).

3. Key Contributions

1. Complete Invariant: The MCbiF is a complete invariant for non-hierarchical sequences of partitions. Unlike dendrograms or ultrametrics, it fully captures the structure of sequences where clusters split and merge non-monotonically.
2. Higher-Order Extension of Sankey Diagrams: The nerve-based MCbiF is interpreted as a higher-order extension of Sankey diagrams. While Sankey diagrams only capture pairwise intersections between consecutive layers, MCbiF captures higher-order intersections across multiple layers, detecting "crossings" that cannot be resolved by simple reordering.
3. Theoretical Characterization of Non-Hierarchy:
   • 0-Conflicts: Detected by $HF_0 < \min |\theta(r)|$. These indicate that no single partition in the interval refines all others.
   • 1-Conflicts: Detected by $HF_1 > 0$. These indicate that elements form a cycle of cluster assignments (e.g., $x \sim y$ at $t_1$, $y \sim z$ at $t_2$, $z \sim x$ at $t_3$) without a transitive resolution, violating the refinement order.
4. Connection to Existing Metrics:
   • The paper proves that 0-conflicts correspond to violations of the strong triangle inequality in the matrix of first-merge times (ultrametric property).
   • It shows that standard information-theoretic measures (Conditional Entropy) fail to detect 1-conflicts, as they only capture pairwise relationships.

4. Experimental Results

The authors evaluated MCbiF on regression and classification tasks using synthetic and real-world data.

A. Regression Task: Minimal Crossing Number of Sankey Diagrams

• Task: Predict the minimal crossing number ($\kappa_\theta$) of a Sankey diagram layout (an NP-complete problem).
• Data: Synthetic sequences of partitions ($N=5, 10$ elements, $M=20$ scales).
• Baselines: Raw label encoding, Sankey graphs (GCN), and pairwise metrics (ARI, MOD, Conditional Entropy).
• Results: Models trained on MCbiF Hilbert functions ($HF_0, HF_1$) significantly outperformed all baselines.
  • Combined $HF_0 + HF_1$ achieved $R^2 \approx 0.54$ (vs. $0.49$ for best baseline).
  • Even a simple Linear Regression (LR) on MCbiF features outperformed Graph Convolutional Networks (GCN) trained on Sankey graphs, highlighting the superior feature representation of MCbiF.

B. Classification Task: Order-Preserving Sequences

• Task: Classify whether a sequence of partitions is "order-preserving" (compatible with a total ordering on elements).
• Data: Synthetic sequences ($N=500, M=30$) with induced random swaps to break order-preservation.
• Results:
  • Baseline metrics (ARI, VI, MOD) and raw encodings performed at random chance ($\approx 50\%$ accuracy).
  • $HF_1$ alone achieved 97% accuracy.
  • This demonstrates that 1-conflicts are the specific topological signature of non-order-preserving sequences.

C. Real-World Application: Wild Mice Social Grouping

• Data: Temporal social network data of house mice over 9 weeks.
• Analysis: Applied MCbiF to sequences at different temporal resolutions ($\tau$).
• Findings:
  • Identified three distinct temporal regimes based on $\bar{c}_0$ and $\bar{c}_1$.
  • $\tau = 24h$ ($\tau_8$): Showed high hierarchy (low conflicts) but revealed a specific "hourglass" 1-conflict (a crossing in the Sankey diagram) predicted by $HF_1(1, 2) = 1$.
  • $\tau = 60s$ ($\tau_4$): Identified as the "sweet spot" with the strongest hierarchy and time reversibility (lowest Hilbert distance between forward and backward sequences).

5. Significance and Impact

• Beyond Pairwise Comparison: The paper moves the field beyond pairwise partition comparison, providing a rigorous framework for analyzing the temporal evolution and memory effects in clustering.
• Interpretability: The Hilbert functions serve as interpretable topological features. Unlike black-box representation learning, $HF_0$ and $HF_1$ directly quantify specific types of structural inconsistencies (refinement violations vs. higher-order cycles).
• Explainable AI (XAI): The ability of simple linear models to outperform complex deep learning models using MCbiF features underscores the value of topologically grounded features for explainable AI.
• General Applicability: The method is algorithm-agnostic and applicable to any sequence of partitions, making it a versatile tool for analyzing dynamic community structures in biology, sociology, and computer science.

In summary, MCbiF provides a mathematically rigorous, computationally efficient, and highly interpretable framework for quantifying the "topological autocorrelation" of multiscale data, successfully bridging the gap between algebraic topology and practical machine learning tasks involving non-hierarchical clusterings.