Sintesi Tecnica: Potere di Separazione delle Reti Neurali Equivarianti

Definizione del Problema

L'espressività dei modelli di apprendimento automatico è spesso quantificata dalla loro universalità — la capacità di approssimare qualsiasi funzione all'interno di una specifica classe. Tuttavia, l'universalità delle reti neurali equivarianti (quelle che rispettano le simmetrie come permutazioni o rotazioni) è limitata dall'incapacità intrinseca della rete di distinguere tra input che sono equivalenti sotto il gruppo di simmetria. Questo limite crea un'interazione complessa tra la capacità di una rete di discriminare input distinti e le strutture invarianti/equivarianti che deve preservare.

Mentre la comunità dell'apprendimento su grafi ha studiato estensivamente il potere di separazione delle Graph Neural Networks (GNN) utilizzando il test di Weisfeiler-Leman (WL) e il conteggio degli omoformismi, questi strumenti combinatori presentano gravi limitazioni quando applicati a classi più ampie di modelli equivarianti, in particolare quelli che elaborano dati geometrici o utilizzano convoluzioni regolari. Manca una mancanza di strumenti analitici fini per caratterizzare l'insieme di input indistinguibili (la relazione di identificazione) per le reti neurali equivarianti generiche con attivazioni non polinomiali, rappresentazioni a dimensione finita e equivarianza per permutazione.

Metodologia

Il documento introduce un quadro teorico per caratterizzare il potere di separazione $\rho(\mathcal{N})$ di una famiglia di reti neurali equivarianti $\mathcal{N}$. Il potere di separazione è definito come la relazione di equivalenza che identifica coppie di input $(\alpha, \beta)$ tali che $f(\alpha) = f(\beta)$ per ogni $f \in \mathcal{N}$.

Il nucleo metodologico del contributo è il "Trucco della Rete Gemella" (Twin Network Trick), che trasforma il problema di identificare input indistinguibili in un problema dello zero locus. Costruendo una rete gemella $\hat{\eta}(\alpha, \beta) = \eta(\alpha) - \eta(\beta)$, gli autori riformulano la relazione di identificazione come la ricerca dell'insieme di punti mappati a zero dallo spazio della rete gemella.

Questa riduzione permette agli autori di applicare tecniche ricorsive derivate dalla teoria delle equazioni funzionali. Nello specifico, sfruttano risultati riguardanti equazioni funzionali lineari che coinvolgono funzioni continue non polinomiali (ad es., ReLU, sigmoid) per derivare una formula esplicita e ricorsiva per lo zero locus. Questa formula mette in relazione lo zero locus di una rete di profondità $d$ con gli zero locus di reti di profondità $d-1$, coinvolgendo unioni e intersezioni di specifici sottospazi definiti dall'architettura della rete e dai termini di bias.

L'analisi assume che:

1. Rappresentazioni di Permutazione: Le reti agiscono su spazi di funzioni a valori reali su insiemi finiti, equivarianti rispetto a gruppi finiti che agiscono come permutazioni.
2. Attivazioni Non Polinomiali: Le funzioni di attivazione sono continue e non polinomiali.
3. Bias Completo: Gli strati affini includono termini di bias subordinati alla partizione dell'orbita dello spazio di rappresentazione.

Contributi Chiave e Risultati

1. Caratterizzazione Completa degli Input Indistinguibili

Il documento fornisce una caratterizzazione completa dell'insieme di coppie di input identificati dalle reti con una data architettura.

• Teorema 1 (Teorema di Caratterizzazione): Stabilisce una formula ricorsiva per lo zero locus di uno spazio neurale. Questa formula decompone la relazione di identificazione in base alla profondità della rete, alle proprietà di attivazione e alla partizione dello spazio di rappresentazione indotta dai termini di bias.

2. Equivalenza delle Attivazioni Non Polinomiali

• Teorema 2: Dimostra che, per una data architettura, qualsiasi funzione di attivazione continua, reale, elemento per elemento e non polinomiale produce lo stesso potere di separazione. Di conseguenza, comuni attivazioni come ReLU, sigmoid e tanh sono equivalenti nella loro capacità di distinguere gli input e raggiungono tutte il massimo potere di separazione possibile per quella architettura. Le attivazioni polinomiali sono escluse da questa equivalenza.

3. Il Ruolo della Profondità

• Teorema 3: Dimostra che aumentare la profondità della rete migliora il potere di separazione solo fino a una specifica soglia di ripetizione. Oltre questa soglia, aggiungere ulteriori strati dello stesso tipo non migliora la capacità di distinguere gli input; il potere di separazione si stabilizza.
  • Per le reti a grafi $k$-invarianti (k-IGNs), questa soglia è proporzionale alla soglia del test $k$-WL.
  • Per le reti con rappresentazioni nascoste regolari, la stabilizzazione avviene dopo una sola ripetizione dello strato.

4. Indipendenza dalla Larghezza delle Caratteristiche Nascoste e dalle Caratteristiche Invarianti

• Teorema 4 & Remark 1: Mostra che il potere di separazione è indipendente dalla molteplicità dei blocchi nelle rappresentazioni nascoste. Nello specifico, aumentare la larghezza delle caratteristiche invarianti nascoste (ad es., la dimensione dello spazio delle caratteristiche nelle IGN) non migliora la capacità della rete di distinguere gli input. Il potere di separazione di una rete con rappresentazione nascosta $V \otimes \mathbb{R}^f$ è identico a quello di una rete con rappresentazione nascosta $V$.

5. Gerarchia dei Tipi di Rappresentazione

• Teorema 5: Stabilisce una gerarchia nel potere di separazione basata sul tipo di rappresentazione utilizzata negli strati. Il potere di separazione corrisponde all'ordinamento parziale dei sottogruppi del gruppo di simmetria.
  • Le rappresentazioni indotte da sottogruppi più piccoli (ad es., il sottogruppo banale $\{e\}$, corrispondente alla rappresentazione regolare) producono il potere di separazione massimo.
  • Le rappresentazioni indotte da sottogruppi più grandi (ad es., il gruppo $G$ stesso, corrispondente ai vettori invarianti) producono il potere di separazione minimo.
  • Ciò implica che l'uso di rappresentazioni regolari ($\mathbb{R}^G$) negli strati nascosti è sufficiente per raggiungere il massimo potere di separazione consentito dall'architettura.

Implicazioni per i Modelli Pratici

Gli autori applicano questi risultati generali a modelli pratici specifici:

• Reti Grafiche Invarianti (IGN): I risultati rafforzano le scoperte precedenti mostrando che le $k$-IGN corrispondono al potere di separazione del test $k$-WL indipendentemente dalle dimensioni delle caratteristiche nascoste. Ciò risolve la necessità di precedenti risultati che richiedevano larghezze di caratteristiche nascoste "grandi" per raggiungere l'universalità.
• CNN Circolari: Il potere di separazione delle Reti Neurali Convoluzionali Circolari è mostrato dipendere dalla dimensione del filtro. Nello specifico, le reti con supporti di filtro più ampi (che si avvicinano alla dimensione totale del gruppo) hanno un potere di separazione strettamente più fine rispetto a quelle con supporti più piccoli, formando una gerarchia rigorosa.

Significato e Rivendicazioni

Il documento sostiene di fornire una condizione necessaria per comprendere l'universalità delle reti neurali equivarianti. Caratterizzando precisamente la relazione di identificazione $\rho(\mathcal{N})$, gli autori consentono una classificazione degli iperparametri e delle scelte architettoniche in due categorie:

1. Determinanti per la Separazione: Scelte che influenzano direttamente l'insieme degli input distinguibili (ad es., tipo di attivazione, profondità fino a una soglia, tipo di rappresentazione). Queste influenzano significativamente sia la capacità di approssimazione che il costo computazionale.
2. Indipendenti dalla Separazione: Scelte che non influenzano l'insieme degli input distinguibili (ad es., larghezza delle caratteristiche nascoste, molteplicità dei blocchi). Queste possono influenzare l'approssimazione entro i vincoli del potere di separazione, ma non espandono la classe di input distinguibili.

Gli autori sottolineano che il loro quadro è limitato alle rappresentazioni di permutazione e alle attivazioni non polinomiali. Riconoscono che il loro approccio non si estende attualmente a modelli che utilizzano coefficienti di Clebsch-Gordan o approcci polinomiali, né affronta completamente i casi in cui i termini di bias sono assenti (sebbene possa fornire dei limiti in tali casi). Il lavoro funge da strumento teorico fondamentale per analizzare l'espressività dei modelli equivarianti oltre i vincoli combinatori dei test specifici per i grafi.