Lernen mit Graphen: Kern- und neuronale Methoden

Abstract

Die vorliegende Arbeit befasst sich mit (überwachter) Graphklassifikation, d. h. mithilfe einer Menge von bereits klassifizierten Beispielgraphen wird ein Modell so trainiert, dass es die Klassen von bisher ungesehenen Graphen vorhersagen kann. Im ersten Teil dieser Arbeit stellen wir Kernmethoden für Graphen vor. Insbesondere stellen wir skalierbare Kerne vor, die mit kontinuierlichen Knoten und Kantenbeschriftungen umgehen können. Ferner stellen wir einen Graphkern vor, der globale Grapheigenschaften berücksichtigen kann, die von anderen Graphkernen nicht erfasst werden. Zu diesem Zweck schlagen wir eine lokale Version des k-dimensionalen Weisfeiler-Leman-Algorithmus vor, der eine bekannte Heuristik für das Graph-Isomorphie-Problem ist. Wir zeigen, dass unser lokaler Algorithmus mindestens die gleiche Mächtigkeit wie der ursprüngliche Algorithmus hat, wobei wir gleichzeitig die Spärlichkeit des zugrundeliegenden Graphen berücksichtigen und Overfitting verhindern. Anschließend stellen wir ein theoretisches Framework für die Analyse von Graphkernen vor, und zeigen, dass die meisten Kerne nicht in der Lage sind einfache graphentheoretische Eigenschaften zu unterscheiden. Der zweite Teil beschäftigt sich mit neuronalen Ansätzen zur Graphklassifikation und deren Verbindung zu Kern-Methoden. Wir zeigen, dass die Expressivität sogenannter Graph-Neural-Networks durch den 1-dimensionalen Weisfeiler-Leman-Algorithmus nach oben beschränkt werden kann.