Higher-order dissimilarity measures for hypergraph comparison

1. Il Problema

Negli ultimi anni, le reti con interazioni di ordine superiore (oltre le semplici coppie di nodi) sono emerse come strumenti fondamentali per modellare sistemi complessi, come reazioni chimiche, interazioni sociali e dinamiche ecologiche. Tuttavia, confrontare questi sistemi rimane una sfida aperta.
Le misure di similarità tradizionali, progettate per le reti pairwise (dove i link connettono solo due nodi), falliscono nel catturare le caratteristiche salienti degli ipergrafi. Un approccio ingenuo consiste nel proiettare l'ipergrafo su una rete pairwise (sostituendo ogni iperlato con un clique completo), ma questa operazione elimina la struttura di ordine superiore, portando a una perdita significativa di informazioni strutturali e rendendo indistinguibili sistemi diversi che condividono la stessa proiezione. Attualmente, mancano metodi principiali ed efficaci per quantificare la dissimilarità tra ipergrafi preservando le loro proprietà intrinseche.

2. Metodologia

Gli autori introducono due nuove misure di dissimilarità specifiche per gli ipergrafi, progettate per essere applicate a coppie di ipergrafi arbitrari (anche di dimensioni diverse) senza richiedere una corrispondenza tra i nodi:

A. Hyper NetSimile (HNS)

Questa misura è una generalizzazione di NetSimile, adattata per considerare le interazioni multi-nodo.

• Approccio: Centrato sul nodo (node-centric).
• Meccanismo: Assegna a ogni ipergrafo un vettore di firma basato sulle distribuzioni di 7 caratteristiche locali calcolate per ogni nodo $i$:
  1. Numero di vicini.
  2. Ipergrado (numero di iperlati a cui appartiene).
  3. Dimensione media degli iperlati contenenti $i$.
  4. Deviazione standard della dimensione degli iperlati contenenti $i$.
  5. Numero medio di vicini dei vicini di $i$.
  6. Ipergrado medio dei vicini di $i$.
  7. Numero di nodi a distanza due da $i$ (dimensione dell'ego-net).
• Calcolo: Per ogni distribuzione, si calcolano media, mediana e deviazione standard, creando un vettore di lunghezza 21. La dissimilarità tra due ipergrafi è la distanza di Canberra normalizzata tra i loro vettori di firma.
• Nota: Le misure di asimmetria (skewness) e curtosi sono state escluse perché peggioravano le prestazioni.

B. Hyperedge Portrait Divergence (HPD)

Questa misura è una generalizzazione del Portrait Divergence, adattata per considerare la struttura globale e le proprietà diffusive.

• Approccio: Centrato sull'iperlato (hyperedge-centric).
• Meccanismo: Definisce un "ritratto" dell'ipergrafo come un tensore $\Gamma$ a quattro indici $(m, n, l, k)$, dove:
  • $m, n$: dimensioni (cardinalità) degli iperlati.
  • $l$: distanza tra due iperlati (definita come il numero di passi nella catena di iperlati adiacenti che si sovrappongono).
  • $k$: numero di iperlati di dimensione $n$ a distanza $l$ da un iperlato di dimensione $m$.
• Calcolo: Il tensore viene normalizzato per ottenere una distribuzione di probabilità $P(m, n, l, k)$. La dissimilarità tra due ipergrafi è la divergenza di Jensen-Shannon tra le loro distribuzioni $P$. Questo approccio cattura statistiche su tutte le scale di lunghezza e le dimensioni degli iperlati.

3. Risultati Chiave

Gli autori hanno validato le metriche attraverso diversi esperimenti su dati sintetici ed empirici:

• Distinzione di Proiezioni Identiche: In casi in cui due ipergrafi diversi hanno la stessa proiezione pairwise (rete di clique), le metriche tradizionali (NS, PD) danno dissimilarità zero. Al contrario, HNS e HPD rilevano correttamente le differenze strutturali di ordine superiore, mostrando una dissimilarità crescente man mano che si altera la struttura originale.
• Clustering di Modelli Generativi: Su 300 ipergrafi sintetici generati da tre modelli (Erdős-Rényi, Configuration Model, Watts-Strogatz), HNS e HPD hanno ottenuto un Rand Index (RI) di 1.0, separando perfettamente le istanze dei diversi modelli. Le metriche pairwise (in particolare PD) hanno fallito nel distinguere alcuni modelli (es. Configuration vs Watts-Strogatz).
• Robustezza ai Parametri: Quando si varia la dimensione massima degli iperlati ($M$) mantenendo costante la densità della proiezione pairwise, solo le metriche di ordine superiore riescono a distinguere le istanze, dimostrando sensibilità alla diversità delle dimensioni delle interazioni.
• Randomizzazione: Applicando tre metodi di randomizzazione (Shuffling casuale, proporzionale e preservante il grado) a dati reali (interazioni faccia-a-faccia in un ospedale), HNS e HPD hanno mostrato la capacità migliore di raggruppare le istanze in base al metodo di randomizzazione utilizzato, superando le metriche pairwise.
• Dati Empirici Reali: Il clustering di ipergrafi reali (interazioni faccia-a-faccia, collaborazioni scientifiche, interazioni online, comitati politici) mostra che le metriche di ordine superiore raggruppano i dati in modo più coerente con il contesto di origine rispetto alle proiezioni pairwise. Ad esempio, riescono a separare chiaramente le interazioni faccia-a-faccia dalle interazioni online e politiche, mentre le metriche pairwise tendono a mescolarle.

4. Contributi Principali

1. Nuove Metriche: Introduzione di HNS e HPD come strumenti specifici per il confronto di ipergrafi che non richiedono allineamento dei nodi e gestiscono dimensioni diverse.
2. Dimostrazione della Necessità: Prove empiriche che le proiezioni pairwise perdono informazioni critiche, rendendo insufficienti le metriche tradizionali per sistemi con interazioni di gruppo.
3. Versatilità: Le metriche sono applicabili sia a dati sintetici che a dati empirici complessi, offrendo una visione sia locale (HNS) che globale/diffusiva (HPD).
4. Analisi di Complessità: Fornitura di un'analisi della complessità computazionale (HPD è $O(E + N(\langle k^2 \rangle - \langle k \rangle))$), indicando che, sebbene più costosa di HNS, è fattibile su laptop standard per sistemi di dimensioni moderate, con possibili approssimazioni per sistemi molto grandi.

5. Significato e Impatto

Questo lavoro sottolinea l'importanza cruciale di considerare le interazioni di ordine superiore non solo per la dinamica dei sistemi, ma anche come firma strutturale per la classificazione e l'identificazione dei sistemi.
Le metriche proposte offrono strumenti pratici per:

• Validazione di Modelli: Verificare se i dati sintetici generati mimano fedelmente le proprietà strutturali dei dati empirici.
• Ricostruzione di Reti: Valutare la qualità dei metodi che ricostruiscono ipergrafi da serie temporali o osservazioni parziali.
• Analisi di Sistemi Dinamici: Estendere l'analisi degli stati temporali a sistemi meglio descritti da ipergrafi temporali piuttosto che da reti temporali.

In sintesi, lo studio fornisce un quadro metodologico solido per caratterizzare e confrontare la complessità strutturale dei sistemi reali, superando i limiti delle rappresentazioni basate sulle coppie.