Conformità topologica esatta: generare grafi equivalenti rispetto alla persistenza

Abstract degli autori

L’omologia persistente riassume l’evoluzione topologica di un grafo mediante diagrammi di persistenza (PD). Generare grafi la cui topologia corrisponda a un descrittore obiettivo è sempre più importante, ma i modelli generativi esistenti che tengono conto della topologia si affidano a una regolarizzazione debole e producono grafi i cui PD possono essere solo approssimativamente simili. Avviamo uno studio sistematico del problema della generazione: produrre grafi che realizzino esattamente un PD obiettivo. Proponiamo due approcci guidati dai vincoli impliciti, locali e globali, imposti dal PD obiettivo. L’approccio locale costruisce iterativamente grafi equivalenti rispetto al PD basato sul grado, e dimostriamo che ogni grafo prodotto realizza il PD obiettivo e che ogni grafo equivalente rispetto al PD basato sul grado è raggiungibile. Tuttavia, come mostriamo in seguito, la generazione locale comporta necessariamente un compromesso tra la diversità dei campioni e la possibilità di raggiungere stati non ammissibili. Riformuliamo quindi la generazione come un problema globale di soddisfacimento dei vincoli, con una codifica completa risolvibile dai moderni solutori di programmazione a vincoli. Questo approccio è applicabile a qualsiasi schema di filtrazione basato sui vertici ed equivariante rispetto alle permutazioni ed è minimale nel caso della filtrazione basata sul grado. Esperimenti su quattro benchmark standard per la generazione di grafi confermano che entrambi i metodi realizzano esattamente il PD obiettivo. Nel loro insieme, i nostri metodi offrono un trattamento sistematico della generazione di grafi rigorosamente conformi ai vincoli topologici. Il codice è disponibile all’indirizzo https://github.com/Aalto-QuML/ExactCompliance.