Der Erfolg von Graph Neural Networks (GNNs) bei der Graphklassifizierung ist eng mit dem Weisfeiler-Lehman (1-WL)-Algorithmus verbunden. Durch die iterative Aggregation von Merkmalen benachbarter Knoten zu einem zentralen Knoten erhalten sowohl 1-WL als auch GNN eine Knotendarstellung, die einen wurzelbasierten Teilbaum um den zentralen Knoten kodiert. Diese wurzelbasierten Teilbaumdarstellungen werden dann in eine einzige Darstellung zusammengefasst, um den gesamten Graphen darzustellen. Allerdings sind wurzelbasierte Teilbäume in ihrer Ausdrucksstärke begrenzt, um nicht-baumartige Graphen darzustellen. Um dieses Problem zu lösen, schlagen wir Nested Graph Neural Networks (NGNNs) vor. NGNN repräsentiert einen Graphen mit wurzelbasierten Teilgraphen anstelle von wurzelbasierten Teilbäumen, sodass zwei Graphen, die viele identische Teilgraphen (anstatt Teilbäume) teilen, neigen, ähnliche Darstellungen zu haben. Der Schlüssel liegt darin, jede Knotendarstellung so zu gestalten, dass sie einen Teilgraphen um sie herum und nicht nur einen Teilbaum kodiert. Um dies zu erreichen, extrahiert NGNN einen lokalen Teilgraphen um jeden Knoten und wendet ein Basis-GNN auf jeden Teilgraph an, um eine Teilgraphdarstellung zu lernen. Die Darstellung des gesamten Graphen wird dann durch das Pooling dieser Teilgraphdarstellungen erzeugt. Wir führen eine strenge theoretische Analyse durch, die zeigt, dass NGNN streng mächtiger ist als 1-WL. Insbesondere haben wir bewiesen, dass NGNN fast alle r-regulären Graphen diskriminieren kann, während 1-WL immer versagt. Darüber hinaus führt NGNN im Gegensatz zu anderen leistungsfähigeren GNNs nur eine konstant höhere Zeitkomplexität als Standard-GNNs ein. NGNN ist ein Plug-and-Play-Framework, das mit verschiedenen Basis-GNNs kombiniert werden kann. Wir testeten NGNN mit unterschiedlichen Basis-GNNs auf mehreren Benchmark-Datensätzen. NGNN verbessert ihre Leistung gleichmäßig und zeigt hochwettbewerbsfähige Leistungen auf allen Datensätzen.