Motif-based filtrations for persistent homology: A framework for graph isomorphism and property prediction

1. Il Problema

Determinare se due grafi sono isomorfi (cioè strutturalmente identici) è un problema fondamentale con applicazioni critiche in chimica molecolare, analisi di reti sociali e biologia. Tuttavia, il problema dell'isomorfismo dei grafi rimane computazionalmente costoso, specialmente per grafi complessi o altamente regolari dove gli algoritmi classici (come il test di Weisfeiler-Leman) falliscono. Inoltre, esiste la necessità di estrarre informazioni strutturali significative dai grafi per compiti di previsione di proprietà (property prediction) e di analizzare la robustezza delle reti rispetto a piccole perturbazioni (come la rimozione o il reindirizzamento di archi).

2. Metodologia

Gli autori propongono un framework basato sulla Persistente Omologia (Persistent Homology), uno strumento dell'Analisi Topologica dei Dati (TDA), applicato a grafi attraverso nuove filtrazioni basate sui motivi (motif-based filtrations).

• Filtrazioni Basate sulla Densità dei Cicli: A differenza delle filtrazioni tradizionali basate sul grado dei nodi, sulla curvatura (es. Ollivier-Ricci) o sulla distanza (Vietoris-Rips), questo studio utilizza schemi di pesatura degli archi basati sulla densità di cicli senza corde (chordless cycles):
  • Triangoli ($eT$)
  • Quadrati senza corde ($eS$)
  • Pentagoni senza corde ($eP$)
  • Somma delle densità di questi cicli ($e\Sigma$).
• Costruzione del Complesso Simpliciale: Il grafo viene espanso in un complesso simpliciale (clique complex) fino a una certa dimensione $k$. Gli archi vengono pesati in base alla densità dei cicli in cui partecipano. I vertici e i simplici di ordine superiore ereditano i pesi dai loro facce (massimo valore).
• Diagrammi di Persistenza: Viene calcolata l'omologia persistente lungo la filtrazione definita dai pesi. I risultati sono riassunti in diagrammi di persistenza che catturano la nascita e la morte di caratteristiche topologiche (componenti connesse e cicli) a diverse scale.
• Metrica di Confronto: Per determinare l'isomorfismo, si calcola la distanza del collo di bottiglia (bottleneck distance) tra i diagrammi di persistenza di due grafi. Se la distanza è inferiore a una soglia di precisione ($10^{-8}$), i grafi sono considerati isomorfi.
• Valutazione: Il framework è stato testato su:
  • Isomorfismo: Grafi cubici, grafi di Cayley minimi, grafi fortemente regolari e il benchmark BREC.
  • Previsione di Proprietà: Utilizzo del dataset ogbg-molhiv per prevedere proprietà strutturali (raggio, diametro, girth, coefficiente di clustering, ecc.) tramite modelli di regressione Random Forest su immagini di persistenza.
  • Sensibilità: Analisi della risposta delle filtrazioni a perturbazioni strutturali (rimozione e reindirizzamento casuale degli archi) su modelli di grafi casuali (Erdős-Rényi, Barabási-Albert, Watts-Strogatz).

3. Contributi Chiave

• Introduzione di Filtrazioni a Densità di Cicli: L'articolo propone l'uso sistematico delle densità di triangoli, quadrati e pentagoni senza corde come parametri di filtrazione per l'omologia persistente, dimostrando che catturano informazioni strutturali a mesoscala spesso perse da altre metriche.
• Superiorità su Grafi Regolari: Dimostrazione che queste filtrazioni riescono a distinguere grafi non isomorfi in famiglie di grafi notoriamente difficili (come i grafi fortemente regolari) dove i metodi basati sul grado, sulla curvatura o sulla distanza falliscono, specialmente a bassi livelli di espansione dei cliques ($k=1$).
• Bilancio Efficienza-Potere Espressivo: Il metodo offre un potere espressivo superiore rispetto alle tecniche basate su graphlets (che sono computazionalmente proibitive) e superiore o paragonabile alle distanze basate su egonets, ma con un costo computazionale significativamente inferiore.
• Sensibilità Strutturale: Le filtrazioni basate sui cicli si rivelano estremamente sensibili a piccole perturbazioni topologiche, agendo come rilevatori precoci di cambiamenti nella connettività della rete.

4. Risultati Principali

• Isomorfismo dei Grafi:
  • La filtrazione somma ($e\Sigma$) e le singole densità di cicli ($eS, eP$) raggiungono tassi di successo del 100% nella distinzione di grafi fortemente regolari non isomorfi, superando nettamente le filtrazioni basate su curvatura (Ollivier-Ricci, Forman-Ricci) e grado.
  • Sul dataset BREC, le filtrazioni basate sui cicli mantengono prestazioni elevate e stabili su tutte le categorie di grafi (Basic, Regular, Extension, CFI), superando i metodi state-of-the-art come la distanza egonet e il test 3-WL in diverse configurazioni.
• Previsione di Proprietà:
  • Nei compiti di regressione sul dataset molecolare ogbg-molhiv, le filtrazioni basate sui cicli ($eS, eT, eP, e\Sigma$) ottengono i rank più bassi (migliori prestazioni) nella previsione di proprietà globali e locali come diametro, girth e coefficiente di clustering.
  • Questo indica che l'omologia persistente derivata da queste filtrazioni cattura informazioni strutturali intrinseche più ricche rispetto ad altre metriche.
• Analisi di Sensibilità:
  • Le filtrazioni basate sui cicli ($e\Sigma$) e sul coefficiente di clustering ($nC$) mostrano la massima sensibilità alla rimozione e al reindirizzamento degli archi.
  • A differenza delle filtrazioni basate sul grado ($nD$), che reagiscono gradualmente, le filtrazioni cicliche rilevano cambiamenti topologici anche con un numero molto ridotto di perturbazioni, indicando una forte dipendenza dalla ridondanza dei percorsi e dalla struttura locale.

5. Significato e Implicazioni

Questo lavoro stabilisce le filtrazioni basate sulla densità dei cicli come un framework efficace, interpretabile e computazionalmente trattabile per il confronto e la caratterizzazione dei grafi.

• Ponte tra TDA e Network Science: Colma il divario tra l'analisi topologica dei dati e la scienza delle reti, fornendo un metodo che sfrutta la geometria discreta dei grafi (cicli) per migliorare l'analisi topologica.
• Applicabilità Pratica: La capacità di distinguere grafi isomorfi complessi e di prevedere proprietà strutturali con alta precisione rende questo approccio promettente per applicazioni reali in chimica (identificazione di molecole), neuroscienze (analisi di connettomi) e analisi di reti sociali.
• Efficienza: Rispetto ai metodi basati su graphlets (che richiedono il conteggio di orbite complesse), l'approccio proposto è scalabile per reti reali sparse, offrendo un compromesso ottimale tra potere discriminativo e costo computazionale.

In sintesi, gli autori dimostrano che incorporare informazioni sui motivi locali (cicli senza corde) nella costruzione di filtrazioni per l'omologia persistente fornisce una rappresentazione dei grafi superiore per compiti di isomorfismo, apprendimento automatico su grafi e analisi di robustezza.