Über gültige optimale Zuordnungskerne und ihre Anwendungen in der Graphenklassifizierung

Der Erfolg von Kernmethoden hat den Entwurf neuer positiv semidefiniter Funktionen insbesondere für strukturierte Daten initiiert. Ein führendes Designparadigma dafür ist das Faltungs-Kern (convolution kernel), das strukturierte Objekte in ihre Teile zerlegt und über alle Teilkombinationen summiert. Im Gegensatz dazu werden Zuordnungs-Kerne (assignment kernels) aus einer optimalen Bijektion zwischen Teilen abgeleitet, was eine gültigere Ähnlichkeitsdefinition bieten kann. Allgemein jedoch liefern optimale Zuordnungen indefinite Funktionen, was deren Verwendung in Kernmethoden erschwert. Wir charakterisieren eine Klasse von Basis-Kernen, die verwendet werden, um Teile zu vergleichen und die positiv semidefinite optimale Zuordnungs-Kerne garantieren. Diese Basis-Kerne erzeugen Hierarchien, durch die die optimalen Zuordnungs-Kerne in linearer Zeit mittels Histogramm-Intersection berechnet werden können. Wir wenden diese Ergebnisse an, indem wir den Weisfeiler-Lehman optimalen Zuordnungs-Kern für Graphen entwickeln. Dieser liefert eine hohe Klassifikationsgenauigkeit auf weit verbreiteten Benchmark-Datensätzen und verbessert sich gegenüber dem ursprünglichen Weisfeiler-Lehman-Kern.