Pivot-WFSM: Memory-Scalable Weighted Subgraph Mining by On-Demand Re-Matching

Sintesi Tecnica di Pivot-WFSM: Estrazione di Sottografi Pesati Scalabile in Memoria tramite Re-Matching On-Demand

Definizione del Problema
L'estrazione di sottografi frequenti pesati (WFSM) su database multigraffi transazionali richiede l'identificazione di pattern che soddisfino sia una soglia di frequenza (supporto) sia una soglia di peso. Gli algoritmi esistenti per questo scenario, tra cui JCZ-ATW, MaxW-gSpan, WFSM-MaxPWS, DewgSpan e FCSG-Miner, ereditano il framework canonico di gSpan. Un limite critico di questo framework è la strategia di memorizzazione degli embedding: ogni pattern attivo mantiene un elenco completo dei propri embedding (occorrenze) attraverso tutti i grafi del database per facilitare l'estensione incrementale. Sebbene questo approccio ammortizzi i costi di matching e offra velocità, causa una crescita combinatoria dell'uso di memoria di picco con il numero di embedding. Di conseguenza, lo store degli embedding esaurisce la memoria disponibile proprio nelle regioni di parametri che gli utenti richiedono maggiormente: soglie di supporto basse e database di grandi dimensioni. Il divario risiede nel fatto che determinare se un pattern è frequente richiede solo di sapere se esiste un embedding, non di memorizzare tutti gli embedding.

Metodologia: Pivot-WFSM
Il documento propone Pivot-WFSM, un algoritmo WFSM transazionale che elimina completamente lo store degli embedding. Invece di estendere gli embedding memorizzati, l'algoritmo esegue un re-matching on-demand.

1. Test di Esistenza On-Demand: Quando viene generato un pattern candidato, l'algoritmo non recupera un elenco pre-calcolato di embedding. Invece, testa l'esistenza di almeno un embedding valido in ciascun grafo ospite che ha supportato il pattern genitore. La ricerca si interrompe non appena viene trovato il primo embedding valido per un dato grafo ospite.
2. Matching Ancorato al Pivot: Per rendere efficiente il re-matching, l'algoritmo adotta una primitiva di matching ancorata al pivot adattata dalla letteratura sull'isomorfismo di sottografi.
   • Selezione del Pivot: Per ogni pattern candidato, viene selezionato un vertice pivot basato su proprietà strutturali intrinseche (es. grado più alto, etichette dei vicini distinte, eccentricità).
   • Filtraggio tramite Signature: Viene costruita una firma locale attorno al pivot. Prima di tentare un matching con un grafo ospite, i vertici dei dati vengono filtrati; vengono considerati come potenziali ancore solo quelli le cui firme locali "coprono" la firma del pivot del pattern. Si dimostra che questo filtro è una condizione necessaria, garantendo che nessun embedding valido venga scartato.
   • Espansione BFS: Il matching procede in ordine di Ricerca in Ampiezza (BFS) dal pivot, garantendo l'iniettività degli archi (cruciale per i multigraffi con archi paralleli) e i vincoli di peso.
3. Pruning Anti-Monotono: Sfruttando l'anti-monotonicità della misura di peso bottleneck-MIN, l'algoritmo esegue il re-matching dei candidati solo sul sottoinsieme di grafi ospiti che hanno supportato il pattern genitore, anziché sull'intero database.

Contributi Chiave

• Una Nuova Strategia di Valutazione: Il documento introduce una strategia di WFSM transazionale che memorizza zero embedding. Il supporto è determinato da test di esistenza on-demand piuttosto che dall'estensione di liste. Ciò riduce la complessità spaziale da $O(M + \sum_{g} \sum_{i} m_i(g))$ (dove $m_i(g)$ è il numero di embedding) a $O(M + \beta \cdot N + s)$, dove il termine di memoria è indipendente dal numero totale di embedding.
• Integrazione Algoritmica e Prove: Gli autori dimostrano come integrare un singolo matcher di isomorfismo di sottografi in un ciclo di mining. Forniscono prove formali che il filtro della firma del pivot è una condizione necessaria (Lemma 2) e che l'algoritmo complessivo è corretto e completo (Teorema 3), preservando l'iniettività degli archi richiesta per i multigraffi.
• Evidenza Empirica di Scalabilità: Il documento fornisce evidenza empirica che lo store degli embedding non riesce a completare il mining su dataset di grandi dimensioni (specificamente il database Yeast con 79.601 grafi) sotto limiti di memoria standard, mentre Pivot-WFSM completa il compito con un uso di memoria significativamente inferiore.

Risultati Sperimentali
Gli esperimenti sono stati condotti su quattro dataset molecolari standard (MUTAG, PTC-MR, NCI1, NCI109) e sul grande database Yeast, utilizzando due distribuzioni di peso (normale ed esponenziale negativa).

• Riduzione della Memoria: Pivot-WFSM riduce l'uso di picco dell'heap live da 12 a 68 volte rispetto al baseline dello store degli embedding. Sul database Yeast con un limite di heap di 8 GB, lo store degli embedding esaurisce la memoria, mentre Pivot-WFSM completa l'operazione con circa 1 GB.
• Prestazioni Temporali:
  • Nei regimi di soglia selettiva (soglie di supporto più elevate, meno pattern), Pivot-WFSM è da 2,5 a 10 volte più veloce rispetto allo store degli embedding perché evita l'overhead di costruzione e mantenimento di liste di embedding ingombranti.
  • Nei regimi a soglia molto bassa (numero massiccio di pattern), Pivot-WFSM è da 1,9 a 4,3 volte più lento a causa del costo dei ripetuti processi di matching, pur rimanendo l'unico metodo in grado di operare sotto stretti vincoli di memoria.
• Studi di Ablazione: I guadagni di prestazione sono attribuiti principalmente alla strategia di re-matching on-demand stessa. L'ancoraggio al pivot fornisce ulteriori accelerazioni su grafi di medie dimensioni, ma risulta neutro su grafi molto grandi.

Significatività e Rivendicazioni
Il documento sostiene che Pivot-WFSM cambi fondamentalmente il compromesso nell'estrazione di sottografi pesati da "memoria-per-velocità" a "tempo-per-memoria". Gli autori dichiarano esplicitamente che la novità non risiede in una nuova misura di peso o in un nuovo euristica di pruning, ma nella strategia di valutazione di rimozione dello store degli embedding.

La significatività risiede nel rendere possibile il mining su dataset e impostazioni di parametri dove l'approccio basato sullo store degli embedding è impraticabile a causa dell'esaurimento della memoria. Il documento non pretende di risolvere la natura NP-hard dell'isomorfismo di sottografi; sostiene invece che, per il problema specifico del mining transazionale, evitare la materializzazione di tutti gli embedding è un passo necessario per raggiungere la scalabilità. Gli autori riconoscono che nei regimi in cui il numero di pattern esplode, la penalità temporale del re-matching è un compromesso, ma essenziale per la fattibilità quando la memoria è il vincolo limitante.