Logo des Repositoriums
 
Konferenzbeitrag

Lernen mit Graphen: Kern- und neuronale Methoden

Vorschaubild nicht verfügbar

Volltext URI

Dokumententyp

Text/Conference Paper

Zusatzinformation

Datum

2020

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Gesellschaft für Informatik e.V.

Zusammenfassung

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.

Beschreibung

Morris, Christopher (2020): Lernen mit Graphen: Kern- und neuronale Methoden. Ausgezeichnete Informatikdissertationen 2019. Bonn: Gesellschaft für Informatik e.V.. ISBN: 978-3-88579-775-3. pp. 169-178. Schoss Dagstuhl, Deutschland. 17.-20. Mai 2020

Schlagwörter

Zitierform

DOI

Tags