Graphenkernel auf Basis linearer Muster: Theoretische und experimentelle Vergleiche

Graphkerne sind leistungsfähige Werkzeuge, um die Lücke zwischen maschinellem Lernen und datenbasierten Graphen zu überbrücken. Die meisten Graphkerne basieren auf der Zerlegung von Graphen in eine Menge von Mustern. Die Ähnlichkeit zweier Graphen ergibt sich dann aus der Ähnlichkeit entsprechender Muster. Kerne, die auf linearen Mustern basieren, bieten ein gutes Gleichgewicht zwischen Genauigkeitsleistung und rechnerischer Komplexität. In dieser Arbeit führen wir eine umfassende Untersuchung und Gegenüberstellung von Graphkernen basierend auf verschiedenen linearen Mustern durch, insbesondere auf Wegen (walks) und Pfaden (paths). Zunächst werden alle diese Kerne detailliert analysiert, einschließlich ihrer mathematischen Grundlagen, der Struktur der Muster und der rechnerischen Komplexität. Anschließend werden Experimente auf verschiedenen Benchmark-Datensätzen durchgeführt, die unterschiedliche Arten von Graphen aufweisen, darunter beschriftete und unbeschriftete Graphen, Graphen mit unterschiedlicher Anzahl von Knoten, unterschiedlichen durchschnittlichen Knotengraden sowie zyklische und azyklische Graphen. Schließlich werden für Aufgaben der Regression und Klassifikation die Leistungsfähigkeit und die rechnerische Komplexität der Kerne verglichen und analysiert, und es werden Empfehlungen zur Auswahl geeigneter Kerne in Abhängigkeit von der Art der Graphdatensätze formuliert. Diese Arbeit ermöglicht eine klare Abwägung der Stärken und Schwächen dieser Kerne. Eine Open-Source-Python-Bibliothek, die eine Implementierung aller diskutierten Kerne enthält, ist öffentlich auf GitHub verfügbar, wodurch die Verbreitung und Vereinfachung der Anwendung von Graphkernen in maschinellen Lernproblemen gefördert wird.