Learning on graphs with logic and neural networks

• Lernen auf Graphen mit Logik und Neuronalen Netzen

Ritzert, Martin; Grohe, Martin (Thesis advisor); Schweikardt, Nicole (Thesis advisor)

Aachen : RWTH Aachen University (2021)
Doktorarbeit

Dissertation, RWTH Aachen University, 2021

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.

Einrichtungen

• Graduiertenkolleg UnRAVeL [080060]
• Fachgruppe Informatik [120000]
• Lehrstuhl für Informatik 7 (Logik und Theorie diskreter Systeme) [122910]