The Polynomial Counting Capabilities of Message Passing Neural Networks

Riepilogo Tecnico: Le Capacità di Conteggio Polinomiale delle Reti Neurali a Passaggio di Messaggi

Enunciato del Problema
Ricerche recenti hanno stabilito che le Reti Neurali a Passaggio di Messaggi (MPNN) possono esprimere proprietà logiche che coinvolgono il conteggio fino a una soglia o il soddisfacimento di vincoli aritmetici lineari, spesso caratterizzati utilizzando frammenti della logica del primo ordine con conteggio (FOC2) o estensioni con aritmetica intera lineare. Tuttavia, permane un divario nella comprensione della potenza espressiva delle MPNN riguardo ai vincoli di conteggio polinomiale (aritmetica non lineare), che sono rilevanti per tecniche avanzate di classificazione dei grafi come i kernel polinomiali. Questo articolo indaga le condizioni in cui le MPNN, in particolare quelle che utilizzano l'aggregazione media, possono riconoscere proprietà definite dalla Logica Modale di Peano (PML). La PML estende la Logica Modale Gradata permettendo vincoli polinomiali (ad esempio, $x_1^2 \cdot x_2 \leq x_3$) invece di quelli puramente lineari.

Metodologia
Gli autori impiegano un quadro formale per analizzare le capacità espressive delle MPNN confrontandole con frammenti della PML.

• Definizione del Modello: Lo studio si concentra sulle MPNN ($M_{mean}$) che utilizzano l'aggregazione media sia per le informazioni locali (vicinato) che globali (intero grafo). Gli autori considerano anche varianti ($M_{mean, x}$) che permettono aggregazioni aggiuntive di somma o massimo.
• Definizione della Logica: Definiscono la PML, dove le formule modali $\langle \pi_1, \dots, \pi_m \rangle \psi(x_1, \dots, x_m)(\phi_1, \dots, \phi_m)$ contano i nodi che soddisfano le sottoformule $\phi_i$ all'interno di specifici vicini (definiti dalle modalità $\pi \in \{id, E_{in}, E_{out}, \top\}$) e verificano se i conteggi soddisfano un vincolo aritmetico di Peano $\psi$.
• Quadro di Riconoscimento: Una MPNN è detta "riconoscere" una formula $\phi$ su una classe di grafi puntati se lo stato di output della rete per il nodo di focus $v$ è diverso da zero (specificamente $\geq c(|V|)$) se il grafo soddisfa $\phi$, e zero altrimenti. La certezza $c(|V|)$ è consentita di dipendere dalla dimensione del grafo.
• Strategia di Costruzione: Le prove coinvolgono la costruzione di architetture MPNN specifiche strato per strato. Queste costruzioni utilizzano "gadget" (combinazioni di neuroni ReLU) per eseguire operazioni aritmetiche (moltiplicazione, addizione, confronto) sui valori aggregati. Una sfida tecnica chiave affrontata è la gestione dei denominatori introdotti dall'aggregazione media (ad esempio, $1/|V|$ o $1/|neigh(v)|$) quando si valutano termini polinomiali di gradi variabili.

Principali Contributi e Risultati
L'articolo identifica specifiche assunzioni strutturali sui grafi di input che permettono alle MPNN medie di catturare proprietà di conteggio polinomiale. I risultati sono categorizzati in base alla profondità delle modalità (superficiale vs. annidata) e al tipo di modalità utilizzate (globali vs. locali).

1. Modalità Globali (Profondità Superficiale):

   • Vincoli Omogenei: Per formule che utilizzano solo la modalità globale ($\top$) e termini di Peano omogenei (nessun termine costante, stesso grado per tutti i monomi), le MPNN medie possono riconoscere la logica senza assunzioni aggiuntive sul grafo (Lemma 1).
   • Vincoli Polinomiali Generali: Per riconoscere vincoli polinomiali globali arbitrari (inclusi termini non omogenei e costanti), i grafi di input devono contenere un nodo contrassegnato (un nodo con un colore unico). Sotto questa assunzione, le MPNN medie possono allineare i denominatori a $|V|^k$ e riconoscere la logica (Teorema 1).

2. Modalità Locali (Profondità Superficiale):

   • Requisito di Regolarità: Per formule che utilizzano solo modalità locali ($E_{in}, E_{out}$), le MPNN medie richiedono che i grafi di input siano regolari (tutti i nodi hanno lo stesso grado in/out) e che il nodo di focus sia fortemente contrassegnato (contrassegnato e avente un auto-loop). Questo permette alla rete di normalizzare le dimensioni dei vicinati locali (Teorema 2).
   • Rilassamento della Regolarità: Se alla MPNN è consentito utilizzare aggregazioni di somma o massimo oltre alla media, l'assunzione di regolarità può essere rimossa. La rete può quindi riconoscere vincoli polinomiali locali su qualsiasi grafo in cui il focus è fortemente contrassegnato (Teorema 3).

3. Modalità Miste (Profondità Superficiale):

   • Quando si combinano modalità globali e locali, i risultati delle sezioni precedenti possono essere combinati. Le MPNN medie riconoscono queste formule su grafi regolari e fortemente contrassegnati (Teorema 4).
   • Con l'aggiunta di aggregazioni somma/massimo, l'assunzione di regolarità è nuovamente rimovibile (Teorema 5).

4. Modalità Annidate (Profondità Arbitraria):

   • Annidamento Globale: L'annidamento di modalità globali non aumenta la potenza espressiva oltre la profondità 1; possono essere appiattite (Proposizione 1).
   • Annidamento Locale: Per formule con modalità locali annidate, l'articolo introduce una classe di grafi chiamata $(T \circlearrowleft_\phi)^p_\bullet$. Queste sono strutture "simili ad alberi" in cui il focus è contrassegnato e la struttura del grafo garantisce tracce uniche per i nodi a distanze specifiche (evitando ambiguità nei conteggi dei vicinati).
   • Risultati: Le MPNN medie possono riconoscere la PML locale annidata su questi grafi simili ad alberi, regolari e fortemente contrassegnati (Teorema 6). Se sono consentite aggregazioni somma/massimo, il vincolo di regolarità è rimosso, permettendo il riconoscimento su grafi simili ad alberi, fortemente contrassegnati e generali (Teorema 7).

Significato e Affermazioni
L'articolo afferma di identificare le condizioni minime richieste affinché le MPNN generalizzino oltre l'aritmetica lineare fino al conteggio polinomiale.

• Generalizzazione Teorica: I risultati suggeriscono che le MPNN con aggregazione media possono generalizzare le tecniche utilizzate nella classificazione dei grafi che si basano su kernel polinomiali (ad esempio, SVM con kernel polinomiali), a condizione che i dati di input soddisfino specifiche proprietà strutturali (nodi contrassegnati, regolarità o somiglianza ad alberi).
• Ruolo dell'Aggregazione: Lo studio evidenzia che mentre l'aggregazione media è sufficiente per il conteggio polinomiale sotto assunzioni strutturali rigorose, l'inclusione di aggregazioni somma o massimo rilassa significativamente questi requisiti (rimuovendo specificamente la necessità di regolarità del grafo).
• Limitazioni: Gli autori affermano esplicitamente che senza queste assunzioni strutturali (nodi contrassegnati, regolarità o strutture simili ad alberi), le MPNN medie non possono esprimere tutti i vincoli polinomiali. Ad esempio, il Lemma 2 dimostra che le MPNN medie non possono distinguere tra certi grafi non regolari che soddisfano un semplice vincolo polinomiale.

L'articolo conclude che, sebbene le MPNN possiedano capacità di conteggio polinomiale, il loro realizzazione richiede scelte architetturali specifiche (aggiunta di somma/massimo) o specifiche pre-elaborazioni dei dati/assunzioni strutturali (contrassegnazione dei nodi, garanzia di regolarità o strutture simili ad alberi). Si suggerisce un lavoro futuro per esplorare combinazioni booleane arbitrarie di modalità e il confronto di conteggi a distanze diverse, che non sono attualmente coperti dal quadro PML utilizzato.