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

Il paper introduce il Multiscale Clustering Bifiltration (MCbiF), un invariante completo basato sull'omologia persistente a due parametri che codifica le strutture di clustering non gerarchiche attraverso le loro intersezioni topologiche, permettendo di estrarre caratteristiche interpretabili che superano i metodi esistenti nelle applicazioni di machine learning e nell'analisi di dati reali come i gruppi sociali dei topi selvatici.

L'essenziale

Il Titolo: Misurare il "Caos Ordinato" dei Gruppi nel Tempo

Immagina di avere un gruppo di amici che si riuniscono ogni giorno per fare attività diverse.

• Lunedì: Si dividono in 3 gruppi per giocare a calcio.
• Martedì: Si dividono in 5 gruppi per cucinare.
• Mercoledì: Si dividono di nuovo in 4 gruppi, ma questa volta le persone si mescolano in modo diverso rispetto a martedì.

Spesso, quando analizziamo questi gruppi, pensiamo che ci sia una "scala" fissa: come un albero genealogico dove i rami si dividono ma non si ricombinano mai (un dendrogramma). Ma nella vita reale, le cose sono più caotiche: i gruppi si fondono, si dividono, e le persone saltano da un gruppo all'altro in modi che non seguono una regola rigida. Questo è un sequenza di partizioni non gerarchica.

Il problema è: come possiamo misurare e confrontare queste sequenze caotiche? Come facciamo a dire se due gruppi di amici si comportano in modo "simile" o "diverso" nel tempo, anche se i loro schemi di amicizia sono complessi?

Gli autori di questo paper (Juni Schindler e Mauricio Barahona) hanno creato un nuovo strumento matematico chiamato MCBIF (Multiscale Clustering Bifiltration).

---

1. La Metafora del "Sankey Diagram" (Il Diagramma a Flusso)

Per capire cosa fa MCBIF, immagina prima un Sankey Diagram.
È quel tipo di grafico che vedi spesso per mostrare i flussi energetici o le migrazioni: hai delle barre a sinistra (i gruppi di partenza) e delle barre a destra (i gruppi di arrivo), collegate da nastri che mostrano chi va dove.

• Il problema: Se i gruppi cambiano in modo semplice (tutti vanno da A a B), il diagramma è pulito. Ma se le persone si mescolano in modo incrociato (A va a B e C, B va a C e D, ecc.), i nastri si incrociano creando un "groviglio" o un "nodo" (in inglese crossing).
• L'idea: MCBIF non guarda solo i nastri, ma guarda la struttura topologica (la forma) di questi grovigli. È come se prendessimo quel diagramma e lo trasformassimo in un oggetto 3D fatto di gomma e fili, per vedere quanti "buchi" o "nodi" ci sono dentro.

2. Cosa fa esattamente MCBIF? (La "Fotografia" a 2 Parametri)

Il metodo tradizionale guarda solo "quanto tempo è passato" (1 parametro). MCBIF guarda due cose contemporaneamente:

1. Da dove partiamo? (Il punto di partenza, $s$).
2. Quanto guardiamo avanti? (La durata o "lag", $t-s$).

Immagina di avere una macchina fotografica a doppio obiettivo:

• Un obiettivo ti dice: "Se guardiamo il gruppo dal giorno 1 al giorno 10, quanti pezzi distinti ci sono?"
• L'altro obiettivo ti dice: "Se guardiamo dal giorno 5 al giorno 15, quanti pezzi distinti ci sono?"

Mettendo insieme tutte queste foto, MCBIF costruisce una mappa completa di come i gruppi si sovrappongono nel tempo.

3. I Due Tipi di "Errori" che MCBIF Rileva

Il paper dice che MCBIF misura due tipi di "incoerenze" (o conflitti) nei gruppi:

A. Il Conflitto di Livello 0 (Il "Chi comanda?")

Immagina di avere tre amici: Alice, Bob e Carlo.

• Lunedì: Alice e Bob sono amici.
• Martedì: Bob e Carlo sono amici.
• Mercoledì: Alice e Carlo sono amici.

Se fosse un sistema gerarchico perfetto, se Alice è con Bob e Bob con Carlo, allora Alice dovrebbe essere "connessa" a Carlo in modo coerente. Ma se il sistema non è gerarchico, potresti avere situazioni in cui non c'è un "capogruppo" unico che riassume tutto.

• Cosa fa MCBIF: Conta quanti "pezzi" (componenti connessi) rimangono separati quando provi a unire tutto. Se il numero di pezzi è diverso da quello che ti aspetteresti in un sistema ordinato, MCBIF suona l'allarme: "Ehi, qui c'è un conflitto di livello 0! Non c'è un ordine chiaro".

B. Il Conflitto di Livello 1 (Il "Groviglio" o il "Buco")

Torniamo ad Alice, Bob e Carlo.
Se Alice è con Bob, Bob con Carlo, e Carlo con Alice, ma nessuno di loro è mai stato insieme a tutti e tre contemporaneamente in un unico gruppo, si crea un "anello" o un "buco" nella struttura.

• Metafora: Immagina di disegnare un triangolo con i fili. Se i fili si incrociano e formano un anello che non può essere "appiattito" (non può essere riempito), hai un "buco" topologico.
• Cosa fa MCBIF: Conta quanti di questi "buchi" o "anelli" ci sono. Questo è molto potente perché i metodi vecchi (che guardano solo coppie di persone) non riescono a vedere questi anelli complessi. MCBIF vede l'intera rete e dice: "C'è un buco qui!".

4. Perché è utile? (Gli Esperimenti)

Gli autori hanno testato il loro metodo su due cose:

1. Disegnare diagrammi puliti: Hanno usato MCBIF per prevedere quanto sarebbe stato "disordinato" un diagramma Sankey (quanti nastri si sarebbero incrociati). Risultato: MCBIF ha fatto un lavoro migliore di qualsiasi altro metodo, anche delle reti neurali complesse. È come se MCBIF avesse un "senso estetico" matematico per l'ordine.
2. Ordinare le preferenze: Hanno usato MCBIF per capire se una sequenza di gruppi seguiva una logica ordinata (come una lista di preferenze) o se era caotica. MCBIF ha indovinato quasi sempre, mentre gli altri metodi hanno fallito.

5. L'Applicazione Reale: I Topi Selvatici

Per concludere, hanno applicato MCBIF a dati reali: i gruppi sociali di topi selvatici osservati per 9 settimane.

• Hanno scoperto che a certe velocità di osservazione (ad esempio, guardando ogni ora), i topi formano gruppi molto stabili e ordinati (pochi "buchi").
• A velocità diverse (guardando ogni minuto), i gruppi sembrano caotici e si mescolano in modo disordinato (molti "buchi" e conflitti).

Questo aiuta gli scienziati a capire a quale "velocità" la natura mostra la sua vera struttura sociale.

In Sintesi

MCBIF è come un detective topologico che entra nella stanza dei gruppi (che siano amici, topi o documenti) e non si chiede solo "chi è con chi", ma "come si intrecciano le relazioni nel tempo".

• Se i gruppi sono ordinati come un albero, MCBIF vede una struttura pulita.
• Se i gruppi sono caotici e si mescolano in modi strani, MCBIF conta i "nodi" e i "buchi" invisibili agli altri metodi.

È uno strumento potente perché trasforma il caos dei dati in numeri chiari (chiamati funzioni di Hilbert) che le macchine possono usare per imparare e fare previsioni migliori, rendendo l'intelligenza artificiale più intelligente e comprensibile.

Sommario tecnico

1. Il Problema

Molti dataset reali possiedono una struttura intrinseca multiscala, dove descrizioni significative emergono a diversi livelli di granularità (es. mobilità urbana, comunità sociali, gruppi tematici di documenti, dati single-cell). Tradizionalmente, queste strutture sono state analizzate tramite clustering gerarchico (rappresentato da dendrogrammi), dove le partizioni seguono una sequenza di raffinamenti o aggregazioni.

Tuttavia, in molte applicazioni reali (come il clustering temporale, la modellazione di argomenti o metodi basati su diffusione), le sequenze di partizioni sono multiscala ma non gerarchiche. In questi casi, i cluster possono dividersi, fondersi e ri-dividersi in modi complessi che violano l'ordine di raffinamento.
Il problema centrale affrontato è: come analizzare e confrontare sequenze di partizioni non gerarchiche parametrizzate da una scala $t$, tenendo conto degli effetti di memoria e delle inconsistenze di ordine superiore tra i cluster? I metodi esistenti (come l'indice Rand, l'entropia condizionale o le metriche ultrametriche) si limitano a confronti a coppie o non riescono a catturare le inconsistenze topologiche globali.

2. Metodologia: MCbiF e Omologia Persistente Multi-parametro

Gli autori introducono il Multiscale Clustering Bifiltration (MCbiF), un nuovo oggetto matematico basato sulla Topological Data Analysis (TDA).

• Definizione di MCbiF: Dato una sequenza di partizioni $\theta: [t_1, \infty) \to \Pi_X$, l'MCbiF è una bifiltrazione (filtrazione a due parametri) di complessi simpliciali astratti, denotata come $M = (K_{s,t})_{t_1 \le s \le t}$.

  • I parametri sono: $s$ (scala di partenza) e $t$ (scala di arrivo).
  • Il complesso $K_{s,t}$ è l'unione di tutti i simplex solidi generati dai cluster presenti nelle partizioni nell'intervallo $[s, t]$. Un $k$-simplex esiste se i suoi vertici appartengono allo stesso cluster in almeno una partizione all'interno dell'intervallo.
  • Questa costruzione codifica i pattern di intersezione dei cluster attraverso tutte le scale, catturando l'autocorrelazione topologica della sequenza.

• Omologia Persistente Multi-parametro (MPH): Applicando l'omologia persistente multi-parametro all'MCbiF, gli autori ottengono un modulo di persistenza che è:

  • Finitamente presentato.
  • Decomponibile in blocchi (block-decomposable).
  • Stabile rispetto a piccole perturbazioni.

• Invarianti Chiave (Funzioni di Hilbert): Poiché la decomposizione completa in barcode per MPH è complessa, gli autori utilizzano le Funzioni di Hilbert $HF_k(s, t)$ come invarianti stabili e interpretabili.

  • $HF_0(s, t)$: Conta il numero di componenti connesse. Rileva violazioni dell'ordine di raffinamento (conflitti di ordine 0). Se $HF_0(s, t) < \min_{r \in [s,t]} |\theta(r)|$, indica che non esiste una partizione massima nell'intervallo, segnalando una non-gerarchicità.
  • $HF_1(s, t)$: Conta il numero di buchi 1-dimensionali (cicli non bordanti). Rileva inconsistenze di ordine superiore (conflitti di ordine 1) tra assegnazioni di cluster attraverso scale diverse. Un ciclo non bordante indica che un insieme di elementi forma un ciclo di appartenenza che non può essere risolto all'interno dell'intervallo considerato.

• Interpretazione come Sankey Diagram: L'MCbiF può essere visto come una generalizzazione di ordine superiore dei diagrammi di Sankey. Mentre un diagramma di Sankey standard mostra solo intersezioni a coppie tra partizioni consecutive, l'MCbiF cattura intersezioni di ordine superiore tra sottosequenze. I conflitti rilevati da $HF_1$ corrispondono a incroci inevitabili nella visualizzazione del diagramma di Sankey.

3. Contributi Chiave

1. Invariante Completo: L'MCbiF è un invariante completo per sequenze di partizioni (non necessariamente gerarchiche), catturando la struttura topologica completa della sequenza.
2. Teoria dei Conflitti: Definizione rigorosa di conflitti 0 (mancanza di gerarchia/ordine di raffinamento) e conflitti 1 (inconsistenze di ordine superiore/cicli topologici). Gli autori dimostrano teoricamente come questi conflitti violino le proprietà delle metriche ultrametriche e dell'entropia condizionale.
3. Costruzione Efficiente: Introduzione di una costruzione basata sul "Nerve" (Nerve-based MCbiF) che è computazionalmente più efficiente quando il numero di scale è inferiore alla dimensione dei cluster, mantenendo l'equivalenza omotopica con la costruzione originale.
4. Feature Map per ML: Le funzioni di Hilbert $HF_0$ e $HF_1$ sono proposte come mappe di feature topologiche interpretabili per compiti di machine learning.

4. Risultati Sperimentali

Gli autori hanno validato il metodo su tre task principali:

• Task di Regressione (Minimizzazione degli incroci di Sankey):

  • Obiettivo: Prevedere il numero minimo di incroci ($\kappa_\theta$) necessari per disporre un diagramma di Sankey.
  • Risultati: I modelli addestrati sulle feature MCbiF ($HF_0$ e $HF_1$) hanno superato significativamente sia le feature di baseline (ARI, VI, MOD) sia i metodi di representation learning (GCN su grafi Sankey, MLP su encoding grezzo).
  • Significato: Dimostra che l'MCbiF cattura meglio le proprietà globali e le complessità di incrocio rispetto alle metriche a coppie o alle rappresentazioni grezze.

• Task di Classificazione (Sequenze che preservano l'ordine):

  • Obiettivo: Distinguere se una sequenza di partizioni è compatibile con un ordinamento totale degli elementi (order-preserving).
  • Risultati: La feature $HF_1$ ha raggiunto un'accuratezza del 97%, mentre le metriche di baseline e l'encoding grezzo hanno fallito (performando come classificatori casuali).
  • Significato: Dimostra la sensibilità unica dell'MCbiF nel rilevare inconsistenze di ordine superiore che rompono la preservazione dell'ordine.

• Applicazione a Dati Reali (Gruppi sociali di topi selvatici):

  • Dati: Sequenze temporali di partizioni derivate da dati di contatto di topi (Mus musculus) su 9 settimane.
  • Risultati: L'MCbiF ha identificato tre regimi temporali distinti in base alla risoluzione temporale ($\tau$).
    • Bassa risoluzione ($\tau_2$): Struttura altamente non gerarchica (alti conflitti 0 e 1).
    • Alta risoluzione ($\tau_8$): Struttura più stabile e gerarchica.
    • Risoluzione intermedia ($\tau_4$): "Sweet spot" con la massima gerarchia e reversibilità temporale (assenza di conflitti 1).
  • Significato: Il metodo ha permesso di quantificare la stabilità dei gruppi sociali e la reversibilità temporale dei flussi di interazione, fornendo insight biologici non ottenibili con metodi tradizionali.

5. Significato e Implicazioni

Il lavoro di Schindler e Barahona rappresenta un avanzamento significativo nell'analisi di dati multiscala non gerarchici:

• Oltre la Gerarchia: Fornisce un quadro teorico solido per analizzare strutture di dati che non possono essere rappresentate da alberi o dendrogrammi.
• Interpretabilità: A differenza delle "black box" del deep learning, le feature di MCbiF hanno un significato topologico chiaro (numero di componenti, buchi, conflitti di ordine), rendendole ideali per l'AI spiegabile (XAI).
• Generalità: Il metodo è indipendente dall'algoritmo di clustering utilizzato per generare le partizioni e può essere applicato a qualsiasi sequenza di partizioni.
• Potere Predittivo: Dimostra che l'incorporazione di informazioni topologiche di ordine superiore (tramite l'omologia persistente multi-parametro) migliora le prestazioni predittive rispetto alle metriche statistiche standard e ai metodi di apprendimento rappresentazionale su dati grezzi.

In sintesi, l'MCbiF trasforma la complessità delle sequenze di partizioni non gerarchiche in invarianti topologici stabili e interpretabili, aprendo nuove strade per l'analisi di dati dinamici e multiscala in campi che vanno dalla biologia alle scienze sociali.