Detailansicht
Comparison of neighborhood-encoding trees for graph kernels
Ariana Christine Fox
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Data Science
Betreuer*in
Nils Morten Kriege
DOI
10.25365/thesis.79680
URN
urn:nbn:at:at-ubw:1-23022.82331.446485-4
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Graphkerne erfreuen sich im Bereich des Graphenlernens wachsender Beliebtheit. Sie liefern ein kontinuierliches Ähnlichkeitsmaß zwischen Graphen, das bei Aufgaben wie der Klassifizierung nützlicher sein kann als traditionellere Graphenlernmethoden. In dieser Arbeit versuchen wir, die Klassifizierungsgenauigkeit und Laufzeit von drei wichtigen Graphkernen basierend auf der Weisfeiler-Leman-Farbverfeinerung zu verbessern: Weisfeiler-Leman Subtree, Weisfeiler-Leman Optimal Assignment und Generalized Weisfeiler-Leman. Wir modifizieren diese Kerne, indem wir die Weisfeiler-Leman-Farbverfeinerung durch die Kanonisierung zweier neuartiger Nachbarschaftskodierungsbäume ersetzen: des k-Redundant Neighborhood Trees und des Truncated ePath Trees. Durch experimentelle Auswertung einfacher molekularer Graphendatensätze und Netzwerkgraphendatensätze stellten wir fest, dass unsere neuen Kerne ähnliche Klassifizierungsgenauigkeiten und ähnliche oder deutlich langsamere Laufzeiten aufwiesen.
Abstract
(Englisch)
Graph kernels are an established method in the field of graph learning. They provide a continuous similarity measure between graphs that can be more useful in tasks like classification than more traditional graph learning methods. In this work, we attempt to improve the classification accuracy and runtime of three key graph kernels based on Weisfeiler-Leman color refinement: Weisfeiler-Leman Subtree, Weisfeiler-Leman Optimal Assignment, and Generalized Weisfeiler-Leman. We modify these kernels by replacing the Weisfeiler-Leman color refinement with the canonicalization of two novel neighborhood-encoding trees: the k-Redundant Neighborhood Tree and the Truncated ePath Tree. Through experimental evaluation on simple molecular graph datasets and network graph datasets, we found that our new kernels had similar classification accuracies and similar or significantly slower runtimes.
Schlagwörter
Schlagwörter
(Deutsch)
Graphkerne
Schlagwörter
(Englisch)
Graph Kernels
Autor*innen
Ariana Christine Fox
Haupttitel (Englisch)
Comparison of neighborhood-encoding trees for graph kernels
Publikationsjahr
2025
Umfangsangabe
ix, 44 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Nils Morten Kriege
Klassifikation
54 Informatik > 54.99 Informatik. Sonstiges
AC Nummer
AC17717699
Utheses ID
77892
Studienkennzahl
UA | 066 | 645 | |