Sintesi Tecnica: Preservazione Strutturale e l'Espressività Logica delle Reti Neurali a Grafo

1. Definizione del Problema

Sebbene siano stati stabiliti collegamenti tra le Reti Neurali a Grafo (GNN) e i formalismi logici, il lavoro precedente si è basato ampiamente sul fissare specifiche scelte architettoniche (ad esempio, funzioni di aggregazione, combinazione e attivazione) per definire classi di GNN ristrette. Queste caratterizzazioni basate sull'architettura collegano specifiche varianti di GNN a estensioni della logica del primo ordine (ad esempio, con termini di conteggio o quantificatori di Presburger) o a formalismi basati su regole come Datalog.

Questo articolo affronta la necessità di un framework semantico che caratterizzi l'espressività logica delle classi di GNN basandosi su proprietà di preservazione strutturale piuttosto che su specifici vincoli sintattici. Nello specifico, gli autori indagano classificatori GNN che sono preservati sotto tre distinte relazioni strutturali:

1. Embedding (estensioni).
2. Omoformismi iniettivi.
3. Omoformismi.

La sfida centrale è determinare quali frammenti di logica corrispondano a queste proprietà di preservazione e fornire rappresentazioni finite per le classi di grafi che esse definiscono, nonostante la natura infinita delle strutture di grafi.

2. Metodologia

Gli autori adottano una prospettiva semantica ispirata alla teoria dei modelli finiti, adattando i teoremi di preservazione (come i teoremi di van Benthem–Rosen e di Rossman) al contesto delle GNN. La metodologia procede attraverso tre fasi principali:

A. Località e Unravelling

Sfruttando la località intrinseca delle GNN (dove l'output di una GNN a $L$ strati dipende solo dal vicinato di distanza $L$), gli autori utilizzano il concetto di $L$-unravelling. Questo trasforma un grafo puntato $(G, v)$ in un albero radicato di altezza al massimo $L$. Una proprietà chiave stabilita è che i classificatori GNN sono invarianti rispetto a questa trasformazione: $N(G, v) = N(\text{Unr}_L(G, v))$. Ciò consente di ridurre l'analisi delle GNN all'analisi di strutture ad albero.

B. Risultati sulla Well-Quasi-Ordering (WQO)

Per gestire l'insieme infinito di possibili grafi, il documento introduce un nuovo risultato combinatorio riguardante le well-quasi-order (WQO).

• Teorema 4: La relazione di embedding su qualsiasi classe di alberi radicati con altezze uniformemente limitate da una costante fissa è una well-quasi-order.
• Corollario 5: Questo risultato si estende agli omoformismi iniettivi e agli omoformismi su alberi di altezza limitata.
• Significato: Poiché le WQO ammettono solo un numero finito di elementi minimi, qualsiasi classe di alberi invariante rispetto all'unravelling e preservata sotto queste relazioni strutturali può essere rappresentata da un insieme finito di alberi minimi. Questa finitezza è cruciale per stabilire la definibilità logica.

C. Teoremi di Preservazione

Combinando l'invarianza rispetto all'unravelling con i risultati WQO, gli autori dimostrano teoremi di preservazione che collegano le proprietà strutturali alla definibilità logica in frammenti della Logica Modale Graduata (GML):

• Le classi preservate sotto embedding corrispondono alla Logica Modale Graduata Esistenziale ($\exists$GML).
• Le classi preservate sotto omoformismi iniettivi corrispondono alla Logica Modale Graduata Esistenziale-Positiva ($\exists^+$GML).
• Le classi preservate sotto omoformismi corrispondono alla Logica Modale Esistenziale-Positiva ($\exists^+$ML).

D. Caratterizzazione Sintattica

L'articolo integra questi risultati semantici identificando specifiche architetture GNN che realizzano queste classi di espressività. Gli autori definiscono:

• GNN Monotoniche (MGNN): GNN con funzioni di aggregazione e combinazione non decrescenti.
• MAX-MGNN: MGNN che utilizzano MAX come funzione di aggregazione.
• MGNN Augmentate: MGNN precedute da uno strato di trasformazione delle caratteristiche pointwise.

3. Contributi Chiave e Risultati

Caratterizzazioni Logiche

Il documento stabilisce corrispondenze strette tra proprietà di preservazione e frammenti logici (Teorema 7, Corollario 8):

• Embedding $\iff$ $\exists$GML: Le GNN preservate sotto embedding hanno la stessa espressività di $\exists$GML.
• Omoformismi Iniettivi $\iff$ $\exists^+$GML: Le GNN preservate sotto omoformismi iniettivi corrispondono a $\exists^+$GML.
• Omoformismi $\iff$ $\exists^+$ML: Le GNN preservate sotto omoformismi corrispondono a $\exists^+$ML.

Realizzazioni Architetturali

Gli autori dimostrano che queste classi semantiche possono essere catturate da specifici vincoli architettonici (Teorema 16):

• Le MGNN Augmentate sono equivalenti in espressività a $\exists$GML.
• Le MGNN sono equivalenti a $\exists^+$GML.
• Le MAX-MGNN sono equivalenti a $\exists^+$ML.
• Le Augmented MAX-MGNN sono equivalenti a $\exists$ML.

GNN con Pesi Positivi

Una scoperta significativa riguarda le GNN con pesi positivi (dove le matrici dei parametri hanno voci non negative). Il documento mostra che qualsiasi GNN preservata sotto omoformismi iniettivi (incluse tutte le GNN monotone) può essere trasformata in una GNN equivalente a pesi positivi. Ciò implica che la restrizione sintattica ai pesi non negativi non è restrittiva riguardo all'espressività all'interno di questa classe.

Scambi di Espressività (Trade-offs)

I risultati rivelano un compromesso fondamentale:

• Proprietà di preservazione più forti (ad esempio, gli omoformismi) portano a caratterizzazioni logiche più semplici (ad esempio, $\exists^+$ML) ma a una ridotta potenza espressiva.
• Proprietà di preservazione più deboli (ad esempio, gli embedding) permettono frammenti logici più ricchi (ad esempio, $\exists$GML) capaci di esprimere proprietà non monotone (come "il nodo $v$ non ha l'etichetta $A$"), ma sono meno robuste alle trasformazioni strutturali.
• Nello specifico, le MAX-MGNN non possono esprimere condizioni basate su soglie (ad esempio, "almeno $k$ vicini") perché l'aggregazione MAX è insensibile alle molteplicità, mentre le MGNN possono esprimere tali condizioni ma non possono gestire omoformismi non iniettivi che fondono i nodi.

4. Significato e Ambito

L'articolo sostiene di fornire un framework semantico per analizzare l'espressività delle GNN che sia indipendente dalle specifiche scelte architettoniche, pur essendo capace di identificare le architetture che raggiungono tali limiti. Stabilendo corrispondenze esatte tra preservazione strutturale, frammenti logici e architetture GNN, il lavoro offre strumenti principi per:

• Analizzare l'espressività delle GNN.
• Abilitare metodi simbolici per la verifica e la spiegazione.
• Comprendere i limiti delle GNN monotone e a pesi positivi.

Gli autori segnalano alcune limitazioni: il framework si concentra sulla classificazione dei nodi (non sulla predizione a livello di grafo), assume un comportamento di vicinato locale (ignorando i meccanismi di ragionamento globale), si limita a classificatori basati su soglie e assume etichette di nodo discrete. Inoltre, la corrispondenza cattura il comportamento limitato dalla località delle GNN e non tiene conto di proprietà oltre il regime di unravelling limitato.

Il contributo tecnico del nuovo risultato WQO per alberi di altezza limitata è evidenziato come di interesse indipendente per lo studio delle well-quasi-order, distinto dalla sua applicazione alle GNN.