Potere Espressivo delle GNN Studiato tramite Lettura Globale

Un nuovo preprint arXiv (2604.22870) indaga il potere espressivo delle reti neurali a grafo con messaggio-passaggio aggregate-combine-readout (ACR-GNN), concentrandosi sulle proprietà del primo ordine (FO). Gli autori mostrano che l'aggregazione somma e la lettura consentono alle GNN di catturare proprietà FO inesprimibili nella logica C2 sia su grafi diretti che non diretti, estendendo i risultati di Hauke e Wałęga (2026). Identificano anche due modi per ripristinare la caratterizzabilità rispetto a C2: limitare l'aggregazione locale senza restringere la lettura globale, o eseguire ACR-GNN su grafi di grado limitato ma dimensione illimitata.