Learning on graphs with logic and neural networks

Ritzert, Martin; Grohe, Martin; Schweikardt, Nicole

doi:10.18154/RWTH-2021-09549

Learning on graphs with logic and neural networks = Lernen auf Graphen mit Logik und Neuronalen Netzen

Ritzert, Martin^RWTH*

2021

Verantwortlichkeitsangabevorgelegt von Martin Ritzert, Master of Science

ImpressumAachen : RWTH Aachen University 2021

Umfang1 Online-Ressource : Illustrationen, Diagramme

Dissertation, RWTH Aachen University, 2021

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grohe, Martin (Thesis advisor)^RWTH* ; Schweikardt, Nicole (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2021-09-23

Online
DOI: 10.18154/RWTH-2021-09549
URL: https://publications.rwth-aachen.de/record/833937/files/833937.pdf

Einrichtungen

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

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Auf Graphen zeigen wir starke Zusammenhänge zwischen Logik und maschinellem Lernen, sowohl theoretischer als auch praktischer Natur. Das Lernen von logischen Formeln auf unterschiedlichen Logiken und Graphenklassen wird anhand sublinearer Lernalgorithmen in einem theoretischen Rahmen präsentiert. Im gleichen Rahmenzeigen wir, dass das Lernen von Prädikatenlogik der ersten Stufe auf allgemeinen Graphen nicht effizient lösbar ist (unter der Annahme P != NP). Im Bereich neuronaler Netze zeigen wir dass sog. Graph Neural Networks (GNNs) und der eindimensionale Weisfeiler-Leman Algorithmus die gleichen Graphen unterscheiden können. Als Anwendung neuronaler Methoden präsentieren wir eine unüberwacht trainierbare, rekurrente Architektur für Constraint-Satisfaction-Probleme, eine Klasse kombinatorischer Probleme die auf Logik basiert. Auf unterschiedlichen Graphenklassen zeigen wir Lernalgorithmen zum Lernen von Formeln der Prädikatenlogik erster Stufe sowie der monadischen Prädikatenlogikzweiter Stufe, die – nötigenfalls nach linearer Indizierung – in sublinearer Zeit arbeiten. Der Rahmen für diese Lernalgorithmen wurde von Grohe und Turán (2004) eingeführt. Aus Informationstheoretischer Sicht ist das Lernen unterschiedlicher Logiken auf dünnen Graphen möglich, was impliziert, dass unsere Lernalgorithmen im PAC-Modellbeweisbar gut generalisieren. Wir ergänzen diese Resultate durch passende untere Laufzeitschranken und zeigen, dass auf allgemeinen Graphen das Lernen von Formeln erster Stufe nicht effizient lösbar ist, solange P != NP gilt. Im praktischen maschinellen Lernen auf Graphen dominieren GNNs die Bestenlisten, deshalb analysieren wir die Ausdrucksstärke von GNNs. Aus der Äquivalenz zwischen GNNs und dem eindimensionalen Weisfeiler-Leman Algorithmus, einer unvollständigen Heuristik für das Graphismorphieproblem, folgt, dass es Paare von Graphen gibt, die von GNNs nicht unterschieden werden können. Im Gegensatz dazu ist für feedforward-Netze bekannt, dass diese jede Funktion beliebig gut approximieren können. Um die beschränkte Ausdrucksstärke von GNNs zu umgehen, verallgemeinern wir GNNs zuk-GNNs basierend auf dem stärkeren k-dimensionalen Weisfeiler-Leman Algorithmus. Wir zeigen empirisch, dass neuronale Netze gut geeignet sind, kombinatorische Probleme zu approximieren indem wir ein rekurrentes GNN für die Maximisierungsvariante von Constraint-Satisfaction-Problemen präsentieren. Das GNN kann auf jedes Constraint-Satisfaction-Problem angewendet werden und wird unüberwacht, und damit ohne Zugriff auf optimale Lösungen der oft NP-schweren Probleme, darauf trainiert, möglichst viele Bedingungen der Probleminstanz zu erfüllen. Mit Experimenten an vier NP-vollständigen kombinatorischen Problemen zeigen wir, dass unser Ansatzbesser funktioniert als andere neuronale Ansätze, semidefinite Programmierung und für das Problem Maximum-2-SAT sogar eine aktuelle Heuristik überbietet.

In the domain of graphs we show strong connections between logic and machine learning in both theory and practice. In a purely theoretical framework we develop sublinear machine learning algorithms for supervised learning of logical formulas on various graph classes. Further we show that learning first-order logic on arbitrary graphs is intractable unless P = NP. At the intersection of theory and practice, we prove an equivalence between graph neural networks and the 1-dimensional Weisfeiler-Leman algorithm. As a practical application, we approximate combinatorial problems with recurrent graph neural networks. The proposed architecture is unsupervised and can be applied to all maximum constraint satisfaction problems. We provide learning algorithms for learning first-order and monadic second-order formulas on different graph classes that are sublinear or sublinear after a linear indexing phase. This is based on a general framework for machine learning of logical formulas on graphs introduced by Grohe and Turán (2004). From an information theoretic perspective, learning is possible for various types of logics on mostly sparse graph classes thus our learning algorithms provably generalize well under the probably approximately correct (PAC) framework. We complement those learnability results by proving matching lower bounds. Further, we show that learning first-order logic on arbitrary graphs is intractable under common complexity theoretic assumptions. In practical machine learning on graphs, neural architectures based on graph neural networks (GNNs) dominate the leaderboards. We analyze the expressiveness of GNNs by showing an equivalence to the 1-dimensional Weisfeiler-Leman algorithm (1-WL).1-WL is a heuristic from graph isomorphism testing which is also known as color refinement. Since it is unable to distinguish all graphs, the equivalence to GNNs shows that there are pairs of graphs which GNNs are unable to distinguish. This result stands in stark contrast to feedforward neural networks which can express every function if they are large enough. As a way to avoid this upper bound, we relax GNNs to k-GNNs based on the more powerful k-dimensional Weisfeiler-Leman algorithm. We empirically show that one can effectively use practical machine learning to approximate combinatorial problems specified by logic. We propose a recurrent GNN to approximate maximum constraint satisfaction problems which in logic correspond to positive primitive formulas, a fragment of first-order logic. This GNN can be applied to any constraint satisfaction problem and is trained unsupervised to satisfy as many constraints as possible. Unsupervised training means that we do not need to compute optimal solutions for the typically NP-hard problems. By experiments on four NP-complete combinatorial problems, we demonstrate that our architecture outperforms other neural approaches, semi-definite programming, and on the maximum-2-SAT problem also a state-of-the-art heuristic.

OpenAccess:
PDF
(additional files)