Graph-Kernel sind Ähnlichkeitsfunktionen für Graphen. Ein Kernel misst, wie ähnlich zwei Graphen sind, ohne sie explizit in einen Merkmalsvektor zu verwandeln — das ist die Kernel-Methode, die sich für maschinelles Lernen auf strukturierten Daten eignet. Statt eines neuronalen Netzes kommt ein Kernmodell wie eine Support Vector Machine zum Einsatz, das nur die paarweisen Ähnlichkeitswerte benötigt.
Idee: Ähnlichkeit statt Merkmalsvektor
Eine Funktion k(G1, G2) liefert eine reelle Zahl: groß, wenn die Graphen sich ähneln, klein, wenn sie verschieden sind. Formal entspricht sie einem Skalarprodukt in einem hochdimensionalen Merkmalsraum — der sogenannte Kernel-Trick erlaubt es, in diesem Raum zu arbeiten, ohne die Merkmale je zu berechnen. Der Parameter der Kernfunktion bestimmt, welche Eigenschaften als ähnlich gelten.
Bekannte Varianten
- Weisfeiler-Lehman-Kernel: nutzt die Farbverfeinerung des Weisfeiler-Lehman-Verfahrens und ist einer der erfolgreichsten Kernel auf Graphen.
- Random-Walk-Kernel: zählt gemeinsame Spaziergänge durch die Graphen und ist eng mit der Adjazenzmatrix verbunden.
- Graphlet-Kernel: vergleicht die Häufigkeit kleiner Teilgraphen (Graphlets) in beiden Graphen.
Anwendungen und Grenzen
Typische Einsätze: Molekülklassifikation in der Chemie, Proteinvergleiche in der Bioinformatik und die Analyse sozialer Netze. Der Preis der Flexibilität: Der Entwurf eines guten Kernels erfordert Fachwissen, und einige Varianten skalieren schlecht auf großen Graphen. Graph Neural Networks lernen solche Ähnlichkeitsfunktionen dagegen end-to-end aus Daten, indem sie Message Passing über Knoten und Kanten ausführen — der Graph-Kernel bleibt die klassische Alternative. Vom Graph-Isomorphie-Problem unterscheidet sich die Kernel-Frage grundsätzlich: Es geht nicht um strukturelle Gleichheit, sondern um graduelle Ähnlichkeit.