Deep learning on graphs : developing and understanding neural architectures for structured data

Tönshoff, Jan Martin; Grohe, Martin; Günnemann, Stephan

doi:44239

Deep learning on graphs : developing and understanding neural architectures for structured data

Tönshoff, Jan Martin^RWTH*

2024 & 2025

Verantwortlichkeitsangabevorgelegt von Jan Martin Tönshoff, Master of Science

ImpressumAachen : RWTH Aachen University 2024

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2024

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2025

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grohe, Martin (Thesis advisor)^RWTH* ; Günnemann, Stephan (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2024-11-04

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

Einrichtungen

Projekte

Inhaltliche Beschreibung (Schlagwörter)
graph learning (frei) ; graph neural networks (frei) ; machine learning (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Graph Neural Networks (GNNs) sind kürzlich als eine leistungsstarke Klasse von Deep-Learning-Architekturen entstanden, die direkt aus graphstrukturierten Daten lernen können. Diese Dissertation zielt darauf ab, sowohl praktische als auch theoretische Aspekte von GNNs zu untersuchen, wobei der Schwerpunkt darauf liegt, ihre Fähigkeiten zur Lösung anspruchsvoller Lernprobleme zu verstehen, neue Richtungen für das Design von GNN-Architekturen zu erkunden und die relativen Stärken und Schwächen von häufig verwendeten GNN-Modellen zu verstehen. In diesem Kontext präsentieren wir unsere primären Forschungsbeiträge: Erstens analysieren wir einen GNN-basierten Ansatz, um Heuristiken für Constraint Satisfaction Probleme (CSPs) durch eine allgemeine Graphkonstruktion und neuronale Architektur zu lernen. Wir zeigen, dass dieser Ansatz leistungsfähige Suchalgorithmen lernen kann, die eine überlegene Leistung im Vergleich zu früheren neuronalen Methoden erzielen und bei einer Reihe von komplexen kombinatorischen Problemen mit klassischen Algorithmen konkurrieren können. Zweitens untersuchen wir eine neuartige GNN-Architektur, die auf 1D-Faltungen und sequenziellen Featuren von Random Walks basiert. Wir analysieren die Ausdrucksstärke dieser Methode und beweisen, dass sie sich fundamental von der Weisfeiler-Leman-Hierarchie und der Ausdruckstärke vieler gängiger GNN-Architekturen unterscheidet. Das Modell erreicht starke empirische Ergebnisse für verschiedene Lernaufgaben und schlägt eine neue Richtung für das Design von GNN-Architekturen über das konventionelle Message-Passing hinaus vor. Drittens vergleichen wir die Fähigkeit häufig genutzter GNN-Modelle Graphstrukturen über lange Distanzen zu erfassen. Durch eine empirische Neuauswertung von häufig verwendeten Benchmark-Datensätzen zeigen wir, dass einfache GNNs, die auf Message-Passing basieren, deutlich besser abschneiden als zuvor berichtet. Weiter zeigt ein theoretischer Vergleich zwischen Graph Transformern und GNNs mit virtuellen Knoten, dass keine der beiden Architekturen die andere im Sinne der uniformen Expressivität übertrifft, was die Notwendigkeit hervorhebt, eine breite Palette von Architekturen für spezifische Lernprobleme in Betracht zu ziehen.

Graph Neural Networks (GNNs) have recently emerged as a powerful class of deep learning architectures that can directly learn from graph-structured data. Such data naturally occurs in a wide range of structurally rich learning domains, such as computational chemistry or social network analysis. This thesis aims to study both practical and theoretical aspects of GNNs, with a focus on understanding their capabilities for solving hard learning tasks, exploring new directions for GNN architecture design, and understanding the relative strengths and weaknesses of commonly used models. In this context, we present our main research contributions: Firstly, we propose a GNN-based approach for learning heuristics for Constraint Satisfaction Problems (CSPs) through a general graph representation and neural architecture. Using reinforcement learning, we show that this approach can learn powerful search algorithms, achieving superior performance compared to prior neural methods and being competitive with classical solvers on a range of complex combinatorial problems. Secondly, we examine a novel GNN architecture based on 1D convolutions on sequential features constructed from random walks. We analyze the expressivity of this approach and prove it to be incomparable to the Weisfeiler-Leman hierarchy and many common GNN architectures. The model is further shown to achieve strong empirical performance across various tasks, suggesting a new direction for GNN architecture design beyond traditional message passing. Thirdly, we compare popular GNNs in the context of capturing long-range dependencies in graphs. Through an empirical re-evaluation of commonly used benchmark datasets, we show that standard GNNs based on message passing perform better than previously reported. A theoretical comparison between Graph Transformers and GNNs with Virtual Nodes further shows that neither architecture subsumes the other in terms of uniform expressivity, highlighting the need to consider a wide range of architectures for specific learning tasks.

OpenAccess:
PDF
(additional files)