On the uniform expressivity of graph neural networks

Rosenbluth, Eran; Geerts, Floris; Grohe, Martin

doi:HT031393592

On the uniform expressivity of graph neural networks

Rosenbluth, Eran^RWTH*

2025 & 2026

Verantwortlichkeitsangabevorgelegt von Eran Rosenbluth, M. Sc.

ImpressumAachen : RWTH Aachen University 2025

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2025

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2026

Genehmigende Fakultät
Fak09

Hauptberichter/Gutachter
Grohe, Martin (Thesis advisor)^RWTH* ; Geerts, Floris (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2025-10-15

Online
DOI: 10.18154/RWTH-2025-11092
URL: https://publications.rwth-aachen.de/record/1024258/files/1024258.pdf

Einrichtungen

Lehrstuhl für Logik und Theorie diskreter Systeme (Informatik 7) (122910)

Projekte

Inhaltliche Beschreibung (Schlagwörter)
expressivity (frei) ; graph neural networks (frei) ; learning complexity (frei) ; learning on graphs (frei) ; machine learning (frei) ; theory of deep learning (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
The main subject of this work are certain parameterized algorithms, known as Graph Neural Networks, which operate on graphs. Specifically, we analyze what functions on graphs these algorithms can compute, or in other words, we analyze their expressivity.

The main subject of this work are certain parameterized algorithms, known as Graph Neural Networks, which operate on graphs. Specifically, we analyze what functions on graphs these algorithms can compute, or in other words, we analyze their expressivity.

OpenAccess:
PDF
(zusätzliche Dateien)