Scalable Network Embedding with Approximate Equitable Partitions (online)

Il network embedding è una tecnica fondamentale per proiettare una rete in uno spazio a dimensione inferiore preservando le similarità tra i nodi. I network embedding tradizionali catturano principalmente la prossimità dei nodi, risultando efficaci per la community detection ma insufficienti per identificare i ruoli, ovvero i pattern di interazione oltre i vicinati locali. Per superare questo limite, introduciamo una tecnica di embedding semplice ed efficiente basata su varianti approssimate di partizioni eque. Il nostro approccio, chiamato ε-BE, introduce un parametro di tolleranza regolabile dall'utente che rilassa la condizione altrimenti rigorosa per le partizioni eque esatte, difficilmente riscontrabili nelle reti del mondo reale. Sfruttiamo una relazione tra partizioni eque e relazioni di equivalenza per catene di Markov ed equazioni differenziali ordinarie per sviluppare un algoritmo di raffinamento della partizione per calcolare una partizione equa approssimata in tempo polinomiale. Estendiamo questo framework a reti pesate e dirette, garantendo l'applicabilità a una classe più generale di grafi e colmando una lacuna nella letteratura dove sono presenti pochi approcci. Confrontiamo il nostro metodo con tecniche di embedding allo stato dell'arte su reti sintetiche e del mondo reale. Riportiamo prestazioni comparabili, se non superiori, per task di visualizzazione, classificazione, clustering e regressione con tempi di esecuzione ridotti, consentendo l'embedding di reti su larga scala che non potrebbero essere gestite efficientemente dalla maggior parte delle tecniche concorrenti. Questi risultati e la capacità di gestire reti pesate e dirette rendono il nostro approccio una valida alternativa per lo structural network embedding.