Technische Samenvatting: Structurele Preservatie en de Logische Expressiviteit van Graph Neural Networks

1. Probleemstelling

Hoewel er verbanden tussen Graph Neural Networks (GNN's) en logische formalismen zijn vastgesteld, leunt eerder werk grotendeels op het vastleggen van specifieke architecturale keuzes (bijv. aggregatie-, combinatie- en activatiefuncties) om beperkte klassen van GNN's te definiëren. Deze architectuurgestuurde karakterisatiesies koppelen specifieke GNN-varianten aan uitbreidingen van de eerste-orde logica (bijv. met teltermen of Presburger-kwantoren) of regelgebaseerde formalismen zoals Datalog.

Dit artikel adresseert de behoefte aan een semantisch kader dat de logische expressiviteit van GNN-klassen karakteriseert op basis van structurele preservatie-eigenschappen, in plaats van op specifieke syntactische beperkingen. In het bijzonder onderzoekt de auteur naar GNN-classifiers die behouden blijven onder drie verschillende structurele relaties:

1. Embeddings (extensies).
2. Injectieve homomorfismen.
3. Homomorfismen.

De kernuitdaging is om te bepalen welke fragmenten van logica corresponderen met deze preservatie-eigenschappen en om eindige representaties te bieden voor de klassen van grafen die zij definiëren, ondanks de oneindige natuur van graafstructuren.

2. Methodologie

De auteurs hanteren een semantisch perspectief geïnspireerd door de eindige modeltheorie, waarbij preservatietheorema's (zoals de van Benthem–Rosen- en Rossman-theorema's) worden aangepast aan de context van GNN's. De methodologie verloopt via drie hoofdfasen:

A. Localiteit en Unravelling

Door gebruik te maken van de inherente localiteit van GNN's (waarbij de output van een $L$-laags GNN alleen afhangt van de $L$-hop buurt), gebruiken de auteurs het concept van $L$-unravelling. Dit transformeert een gepunteerde graaf $(G, v)$ naar een gewortelde boom met een hoogte van maximaal $L$. Een cruciaal eigenschap die wordt vastgesteld, is dat GNN-classifiers invariant zijn onder deze transformatie: $N(G, v) = N(\text{Unr}_L(G, v))$. Dit maakt het mogelijk de analyse van GNN's te reduceren tot de analyse van boomstructuren.

B. Well-Quasi-Ordering (WQO) Resultaten

Om de oneindige verzameling mogelijke grafen te behandelen, introduceert het artikel een nieuw combinatorisch resultaat met betrekking tot well-quasi-orders (WQO).

• Theorem 4: De embedding-relatie op elke klasse van gewortelde bomen met een uniform begrensd hoogteconstant is een well-quasi-order.
• Corollary 5: Dit resultaat strekt zich uit naar injectieve homomorfismen en homomorfismen op bomen met een begrensde hoogte.
• Significantie: Omdat WQO's slechts een eindig aantal minimale elementen toelaten, kan elke klasse van bomen die invariant is onder unravelling en behouden blijft onder deze structurele relaties, worden gerepresenteerd door een eindige verzameling minimale bomen. Deze eindigheid is cruciaal voor het vaststellen van logische definieerbaarheid.

C. Preservatie-theorema's

Door de unravelling-invariantie te combineren met de WQO-resultaten, bewijzen de auteurs preservatie-theorema's die structurele eigenschappen koppelen aan de logische definieerbaarheid in fragmenten van Graded Modal Logic (GML):

• Klassen die behouden blijven onder embeddings corresponderen met Existential Graded Modal Logic ($\exists$GML).
• Klassen die behouden blijven onder injectieve homomorfismen corresponderen met Existential-Positive Graded Modal Logic ($\exists^+$GML).
• Klassen die behouden blijven onder homomorfismen corresponderen met Existential-Positive Modal Logic ($\exists^+$ML).

D. Syntactische Karakterisering

Het artikel complementeert deze semantische resultaten door specifieke GNN-architecturen te identificeren die deze expressiviteitsklassen realiseren. De auteurs definiëren:

• Monotone GNN's (MGNN's): GNN's met niet-dalende aggregatie- en combinatiefuncties.
• MAX-MGNN's: MGNN's die MAX als aggregatiefunctie gebruiken.
• Geaugmenteerde MGNN's: MGNN's voorafgegaan door een pointwise feature-transformatielaag.

3. Belangrijkste Bijdragen en Resultaten

Logische Karakterisaties

Het artikel stelt nauwe correspondenties vast tussen preservatie-eigenschappen en logische fragmenten (Theorem 7, Corollary 8):

• Embeddings $\iff$ $\exists$GML: GNN's die behouden blijven onder embeddings hebben dezelfde expressiviteit als $\exists$GML.
• Injectieve Homomorfismen $\iff$ $\exists^+$GML: GNN's die behouden blijven onder injectieve homomorfismen corresponderen met $\exists^+$GML.
• Homomorfismen $\iff$ $\exists^+$ML: GNN's die behouden blijven onder homomorfismen corresponderen met $\exists^+$ML.

Architecturale Realisaties

De auteurs demonstreren dat deze semantische klassen kunnen worden gevangen door specifieke architecturale restricties (Theorem 16):

• Geaugmenteerde MGNN's zijn equivalent in expressiviteit aan $\exists$GML.
• MGNN's zijn equivalent aan $\exists^+$GML.
• MAX-MGNN's zijn equivalent aan $\exists^+$ML.
• Geaugmenteerde MAX-MGNN's zijn equivalent aan $\exists$ML.

Positive-Weight GNN's

Een significante bevinding betreft positive-weight GNN's (waarbij parametermatrices niet-negatieve entries hebben). Het artikel toont aan dat elke GNN die behouden blijft onder injectieve homomorfismen (inclusief alle monotone GNN's) kan worden getransformeerd naar een equivalente positive-weight GNN. Dit impliceert dat de syntactische restrictie tot niet-negatieve gewichten niet restrictief is met betrekking tot de expressiviteit binnen deze klasse.

Expressiviteits-trade-offs

De resultaten onthullen een fundamentele trade-off:

• Sterkere preservatie-eigenschappen (bijv. homomorfismen) leiden tot eenvoudigere logische karakterisaties (bijv. $\exists^+$ML) maar tot verminderde expressieve kracht.
• Zwakkerere preservatie-eigenschappen (bijv. embeddings) staan rijkere logische fragmenten toe (bijv. $\exists$GML) die in staat zijn niet-monotone eigenschappen uit te drukken (zoals "node $v$ heeft niet label $A$"), maar zijn minder robuust tegen structurele transformaties.
• Specifiek kunnen MAX-MGNN's geen drempelgebaseerde condities uitdrukken (bijv. "ten minste $k$ buren") omdat MAX-aggregatie ongevoelig is voor multipliciteiten, terwijl MGNN's dergelijke condities wel kunnen uitdrukken maar niet in staat zijn tot niet-injectieve homomorfismen die knopen samenvoegen.

4. Betekenis en Reikwijdte

Het artikel beweert een semantisch kader te bieden voor de analyse van GNN-expressiviteit dat onafhankelijk is van specifieke architecturale keuzes, maar toch in staat is om architecturen te identificeren die deze grenzen bereiken. Door exacte correspondenties vast te stellen tussen structurele preservatie, logische fragmenten en GNN-architecturen, biedt het werk principiële instrumenten voor:

• Het analyseren van de expressiviteit van GNN's.
• Het mogelijk maken van symbolische methoden voor verificatie en uitlegbaarheid.
• Het begrijpen van de beperkingen van monotone en positive-weight GNN's.

De auteurs vermelden beperkingen: het kader richt zich op node classificatie (niet op graph-level predictie), gaat uit van lokale buurt gedrag (negerend van globale redeneermechanismen), beperkt zich tot drempelgebaseerde classifiers, en gaat uit van discrete node labels. Bovendien vangt de correspondentie het lokaal-begrensde gedrag van GNN's en houdt het geen rekening met eigenschappen buiten het begrensde unravelling-regime.

Het technische bijdrage van het nieuwe WQO-resultaat voor bomen met een begrensde hoogte wordt benadrukt als zijnde van onafhankelijk belang voor de studie van well-quasi-orders, verschillend van de toepassing ervan op GNN's.