Modularity maximization and community detection in complex networks through recursive and hierarchical annealing in the D-Wave Advantage quantum processing units

Sintesi Tecnica: Massimizzazione della Modularità e Rilevamento di Comunità tramite Recisione Gerarchica (Hierarchical Annealing) su D-Wave

Definizione del Problema
Il rilevamento di comunità in reti complesse è un problema fondamentale nella scienza delle reti, tipicamente formulato come massimizzazione dell'indice di modularità ($Q$). Questo compito di ottimizzazione è NP-hard. Sebbene esistano algoritmi euristici classici (ad esempio, Louvain, Leiden), essi non garantiscono l'ottimo globale. Il Quantum Annealing (QA) offre un potenziale percorso per risolvere tali problemi NP-hard trovando il minimo globale di un paesaggio energetico. Tuttavia, una barriera significativa all'applicazione del puro QA al rilevamento di comunità è la codifica del problema. Gli approcci standard spesso si affidano alla codifica "one-hot" per rappresentare $M$ comunità utilizzando $N \times M$ variabili binarie. Ciò richiede vincoli rigidi (assicurare che ogni nodo appartenga esattamente a una comunità), che vengono tipicamente imposti tramite moltiplicatori di Lagrange. La calibrazione dei pesi di penalità per questi moltiplicatori è empiricamente difficile e spesso richiede ipotesi specifiche per il problema, il che può oscurare il processo quantistico e limitarne la scalabilità. Inoltre, le esistenti soluzioni ibride quantistico-classiche spesso mancano di trasparenza riguardo alla divisione del lavoro tra i processori quantistici e classici.

Metodologia
Gli autori propongono un nuovo algoritmo, Hierarchical Annealing (Recisione Gerarchica), progettato per massimizzare la modularità utilizzando il puro annealing quantistico su QPU D-Wave Advantage senza l'uso della codifica one-hot o di moltiplicatori di Lagrange.

• Decomposizione Binaria Ricorsiva: Invece di assegnare i nodi a $M$ comunità simultaneamente, l'algoritmo suddivide ricorsivamente la rete. Inizia con l'intera rete come un'unica comunità e la suddivide iterativamente in due sottocomunità. Questo trasforma il problema in una sequenza di problemi di ottimizzazione binaria non vincolata.
• Formulazione QUBO:
  • Per reti non dirette, il guadagno di modularità derivante dalla divisione di una comunità $k$ in $k_1$ e $k_2$ viene mappato in un problema di Ottimizzazione Quadratica Non Vincolata Binaria (QUBO). La funzione di costo è derivata dalla matrice di modularità generalizzata $B^k$, dove l'obiettivo è minimizzare il cambiamento negativo della modularità ($p_k = -[Q(C_{k+1}) - Q(C_k)]$).
  • Per le reti dirette, gli autori affrontano l'asimmetria della matrice di modularità ottimizzando la combinazione lineare simmetrizzata $\frac{1}{2}(p_k + p_k^\top)$. Ciò assicura che il primo passo della gerarchia ottimizzi la funzione globale corretta e mantenga il formalismo QUBO senza termini lineari.
• Parametro di Risoluzione ($\gamma$): Il parametro di risoluzione, che controlla la scala delle comunità rilevate, è integrato direttamente nel calcolo della matrice di modularità generalizzata. L'algoritmo rimane formalmente indipendente da $\gamma$ per quanto riguarda la struttura di ottimizzazione, permettendogli di essere trattato come un parametro libero.
• Flusso di Esecuzione: Il processo è eseguito ricorsivamente (Algoritmo 1). Per ogni passaggio, viene calcolata una matrice di modularità generalizzata, viene costruita una QUBO e viene caricato un embedding di tipo clique da una cache. Il campionatore D-Wave esegue l'annealing binario per trovare la divisione ottimale. La ricorsione si interrompe quando una divisione non produce miglioramenti (il cambiamento della modularità è zero) o risulta in un insieme vuoto.
• Implementazione: Gli autori hanno sviluppato una libreria Python, Qommunity, che si interfaccia con l'ecosistema D-Wave. Hanno utilizzato il sistema Advantage (topologia Pegasus, grado 16) con strategie di forza della catena (chain strength) predefinite e voto a maggioranza per le catene interrotte.

Contributi Chiave

1. Pure Quantum Annealing senza Vincoli: Il lavoro dimostra una procedura sistematica per trovare gli ottimi globali per la massimizzazione della modularità utilizzando solo annealer puri, bypassando la necessità della codifica one-hot e la relativa difficoltà di calibrare i moltiplicatori di Lagrange.
2. Formalismo Generalizzato: Gli autori estendono il formalismo della massimizzazione della modularità per gestire reti non dirette, dirette e pesate all'interno di un quadro ricorsivo unificato.
3. Interpretabilità: A differenza dei solver ibridi "black-box", la natura ricorsiva dell'algoritmo produce un dendrogramma di suddivisioni intermedie. Ciò offre una visione interpretabile della gerarchia delle comunità, rivelando come la struttura della rete si dispiega ai diversi livelli di risoluzione.
4. Scalabilità ed Efficienza: Lo studio fornisce prove empiriche che questo approccio produce soluzioni almeno altrettanto ottimali degli algoritmi classici allo stato dell'arte (Louvain, Leiden), mantenendo tempi di calcolo trattabili.

Risultati

• Benchmarking: L'algoritmo è stato testato su varie topologie di rete, incluse reti Erdős-Rényi, Barabási-Albert, reti a cluster di legge di potenza (power-law clustered) e reti scale-free dirette.
  • In semplici catene a 3-clique e nella rete Zachary Karate Club, l'H. Annealing ha raggiunto punteggi di modularità identici o leggermente superiori a quelli di Louvain e Leiden.
  • Nei modelli a blocchi stocastici (SBM), il metodo ha recuperato con successo le comunità piantate attraverso vari parametri di mixing, competendo con i metodi di inferenza probabilistica.
  • Per le reti scale-free, l'algoritmo ha mostrato prestazioni robuste, spesso superando i controparti classici in termini di punteggi di modularità, specialmente quando erano presenti gerarchie intrinseche.
• Sensibilità alla Risoluzione: L'algoritmo è rimasto stabile attraverso diversi valori del parametro di risoluzione $\gamma$. Sebbene le prestazioni siano diminuite leggermente per valori estremi di $\gamma$ nelle reti dirette, sono rimaste competitive vicino a $\gamma=1$.
• Complessità Computazionale:
  • Il pre-processing classico (calcolo della matrice di modularità) scala come $O(n^2)$.
  • La complessità dell'albero ricorsivo è stimata in $O(n \log n)$ basandosi sul teorema di Akra-Bazzi, assumendo divisioni bilanciate.
  • Empiricamente, i tempi di accesso alla QPU sono scalati logaritmicamente con la dimensione della rete ($t \propto \ln N$), suggerendo uno scaling efficiente per la componente quantistica.
  • Il tempo di esecuzione totale è dominato dagli overhead di comunicazione e di accodamento piuttosto che dal tempo di esecuzione della QPU stessa.
• Applicazione nel Mondo Reale: Il metodo è stato applicato a una rete reale di connettività strutturale cerebrale (166 nodi). La struttura di comunità risultante e il dendrogramma sono stati altamente coerenti con quelli trovati da Louvain e Leiden, con differenze minori solo in bordi frontoparietali altamente interconnessi.

Significato e Rivendicazioni
Il documento posiziona questo lavoro come un "primo passo verso un uso pratico applicabile del puro quantum annealing". Gli autori affermano di aver colmato il divario tra la scienza delle reti e il calcolo quantistico dimostrando che il puro QA può risolvere problemi di rilevamento di comunità senza dipendere da soluzioni ibride "black-box" o dalla complessa calibrazione dei vincoli.

La significatività risiede in:

• Trasparenza: Fornire una soluzione ricorsiva interpretabile (dendrogrammi) piuttosto che una singola partizione piatta, il che è prezioso per scoprire gerarchie nascoste in sistemi complessi come le reti cerebrali.
• Fattibilità: Dimostrare che l'hardware quantistico attuale (D-Wave Advantage) può gestire compiti di rilevamento di comunità di dimensioni pratiche (fino a circa 166 nodi testati, limitati dalla topologia Pegasus) con prestazioni competitive.
• Spostamento Metodologico: Offrire un'alternativa valida alla codifica one-hot che evita la calibrazione empirica dei pesi di penalità, rendendo potenzialmente l'ottimizzazione quantistica più accessibile all'analisi delle reti.

Gli autori rimangono modesti, riconoscendo che il processo ricorsivo non garantisce l'ottimo globale (un limite condiviso da tutte le euristiche per questo problema NP-hard) e che la scalabilità verso reti molto grandi richiede attualmente solver ibridi o l'accesso locale alla QPU per mitigare gli overhead di comunicazione. Non rivendicano una superiorità universale rispetto ai metodi classici, ma sottolineano il potenziale del quantum annealing per fornire soluzioni significative e ugualmente ottimali in specifici contesti topologici.