Generalization and Expressivity of Graph Neural Networks in Practice
Author
Lund, Sebastian
Term
4. term
Education
Publication year
2023
Pages
30
Abstract
This thesis examines how well message-passing graph neural networks (MPNNs) realize their theoretical expressivity and generalize in practice. Although theory links maximally expressive MPNNs, such as GIN, to the Weisfeiler–Lehman (WL) isomorphism test via injective aggregation, we find notable practical limitations. Through controlled experiments we test whether universal MPNNs can emulate WL steps, mimic weaker aggregation schemes on bounded-size graphs, and generalize on three simple logical node-classification tasks. The results show that universal MPNNs do not learn injective functions and fail to emulate even early WL iterations; they can imitate weaker MPNNs on bounded graphs, but MPNNs in general do not extrapolate well to larger graphs, and less expressive variants sometimes perform and generalize better. We then add structural information using the ESAN framework, which applies MPNNs to bags of subgraphs, and observe on two molecular datasets that models with weaker MPNN encoders can match or outperform those using universal encoders, including a mean-aggregation MPNN. Overall, the study highlights practical limits of universal MPNNs and recommends evaluating structural-information frameworks with a broader set of weaker MPNNs.
Dette speciale undersøger, hvor godt beskedpasserende grafneurale netværk (MPNN’er) realiserer deres teoretiske udtrykskraft og generaliserer i praksis. Selvom teorien knytter maksimalt udtryksstærke MPNN’er, som GIN, til Weisfeiler–Lehman-testen (WL) via injektive aggregationer, finder vi markante praktiske begrænsninger. Gennem kontrollerede eksperimenter tester vi, om universelle MPNN’er kan emulere WL-trin, efterligne svagere aggregationsskemaer på grafer af begrænset størrelse og generalisere på tre simple logiske nodeklassifikationsopgaver. Resultaterne viser, at universelle MPNN’er ikke lærer injektive funktioner og fejler i at emulere selv tidlige WL-iterationer; de kan efterligne svagere MPNN’er på begrænsede grafer, men MPNN’er generelt ekstrapolerer dårligt til større grafer, og mindre udtryksstærke varianter præsterer og generaliserer til tider bedre. Vi tilføjer dernæst strukturel information med ESAN-rammen, som anvender MPNN’er på sæt af delgrafer, og observerer på to molekylære datasæt, at modeller med svagere MPNN-enkodere kan matche eller overgå dem med universelle enkodere, herunder en middel-aggregerende MPNN. Samlet peger studiet på praktiske begrænsninger ved universelle MPNN’er og anbefaler, at rammer med strukturel information evalueres med et bredere sæt af svagere MPNN’er.
[This apstract has been generated with the help of AI directly from the project full text]