Rappresentazioni neurali implicite per problemi variazionali sui graphon

Abstract degli autori

Proponiamo un approccio esplorativo basato su reti neurali per i problemi variazionali sui graphon, ossia funzioni misurabili simmetriche $[0,1]^2 \to [0,1]$ che emergono come limiti di sequenze di grafi densi. Questi problemi sono centrali in due ambiti della letteratura matematica: la teoria estremale dei grafi, che studia l’ottimizzazione dei parametri dei grafi sotto determinati vincoli, spesso per grafi con un gran numero di vertici, e la teoria delle grandi deviazioni dei grafi casuali densi, che caratterizza la struttura degli eventi rari mediante l’ottimizzazione vincolata dei graphon. Rappresentiamo i graphon mediante reti neurali implicite e ottimizziamo le funzioni obiettivo mediante discesa del gradiente. Il nostro approccio combina tre elementi: un’architettura residua sinusoidale multiscala orientata verso graphon con transizioni nette e struttura a gradini; un risolutore integrato che impone un unico vincolo di densità empirica e le cui derivate sono calcolate mediante differenziazione implicita; e stimatori Monte Carlo che tengono conto delle simmetrie. Nei problemi di Turán generalizzati che in precedenza richiedevano un notevole impegno umano, il nostro approccio riscopre graphon ottimali già noti senza intervento umano. Applicato a casi ancora aperti, produce candidati ottimali, tra cui una famiglia di strutture estremali non segnalata in precedenza. Applicato ai problemi variazionali della teoria delle grandi deviazioni dei grafi casuali di Erdős--Rényi, l’approccio produce nuovi graphon candidati a essere ottimali nei regimi della coda superiore e della coda inferiore per diversi grafi-motivo; nel caso del grafo triangolare e del regime della coda superiore, questi candidati migliorano la migliore costruzione di riferimento nota di Lubetzky e Zhao. Le strutture individuate dal nostro approccio hanno inoltre portato a nuovi teoremi sui graphon ottimali per entrambe le famiglie di problemi.