Scalable graph kernels

Abstract

Graph-structured data are becoming more and more abundant in many fields of science and engineering, such as social network analysis, molecular biology, chemistry, computer vision, or program verification. To exploit these data, one needs data analysis and machine learning methods that are able to efficiently handle large-scale graph data sets. Successfully applying machine learning and data analysis methods to graphs requires the ability to efficiently compare and represent graphs. Standard solutions to these problems are either NP-hard, not expressive enough, or difficult to adapt to a problem at hand.

Graph kernels have attracted considerable interest in the machine learning community in the last decade as a promising solution to the above-mentioned issues. Despite significant progress in the design and improvement of graph kernels in the past few years, existing graph kernels do not measure up to the current needs of machine learning on large, labeled graphs: Even the most efficient existing kernels need O(n^3) runtime to compare a pair of graphs with n nodes, or cannot take into account node and edge labels. Our primary goal in this thesis is the design of efficient and expressive kernels for machine learning on graphs.

We first focus on the design of generic graph kernels that can be applied to graphs with or without labels. Our main contributions to this end are the following:

First, we speed up the exact computation of graphlet kernels from O(n^k) to O(nd^{k-1}) for a pair of graphs, where n is the size of the graphs, k is the size of considered graphlets, and d is the maximum degree in the given graphs.

Second, we define a new kernel on graphs, the Weisfeiler-Lehman subtree kernel, which is the first graph kernel scaling linearly in the number of edges in the given graph set. In our experiments on benchmark graph data sets from chemoinformatics and bioinformatics, the Weisfeiler-Lehman subtree kernel gracefully scales up to large graphs, outperforms all existing graph kernels in speed, and yields highly competitive performance in graph classification.

Third, we generalize the Weisfeiler-Lehman subtree kernel to a family of kernels that includes many known graph kernels as special cases. This generalization enables existing graph kernels to take into account more information about the graph topology, and thereby become more expressive.

In the last part of this thesis, we present two examples of applications: Based on our previous contributions, we propose specialized node kernels for pixel classification in remote sensing images, and graph kernels for chemical shift prediction in structural bioinformatics. Our kernels make it possible for the first time to take advantage of the rich graph structure in these applications.

The Weisfeiler-Lehman kernels we propose here now allow graph kernels to scale to large, labeled graphs. They open the door to manifold applications of graph kernels in numerous domains which deal with graphs whose size and attributes could not be handled by graph kernels before.

Daten in Form von Graphen spielen in immer mehr Bereichen der Wissenschaft und der Wirtschaft eine Rolle, wie in der Analyse sozialer Netzwerke, in der Molekularbiologie, in der Chemie, in der Computervision und in der Programmverifikation. Um diese Daten zu nutzen, braucht man Methoden zur Datenanalyse und zum Maschinenlernen, die in der Lage sind, große Datenmengen effizient zu verarbeiten. Um die Algorithmen des Maschinenlernens erfolgreich auf Graphen anzuwenden, benötigt man Verfahren, um Graphen effizient vergleichen oder repräsentieren zu können. Standardlösungen für diese Probleme sind entweder NP-schwer, nicht expressiv genug, oder schwierig auf das jeweilige Problem anzuwenden.

Graphkerne haben im letzten Jahrzehnt im Bereich Maschinenlernen viel Aufmerksamkeit auf sich gezogen, da sie einen vielversprechenden Lösungsansatz für die obengenannten Probleme darstellen. Trotz signifikanter Fortschritte im Bereich der Graphkerne in den letzten Jahren reichen bekannte Graphkerne nicht für die gegenwärtigen Anforderungen im Maschinenlernen aus, wenn die zu untersuchenden Graphen sehr groß oder gelabelt sind. Selbst die effizientesten Kerne erfordern eine Laufzeit von O(n^3), um ein Paar Graphen mit n Knoten zu vergleichen oder um Knoten- und Kantenlabels zu berücksichtigen. Unser wichtigstes Ziel in dieser Dissertation ist daher die Entwicklung effizienter und expressiver Kerne für das Maschinenlernen auf Graphen.

Zuerst konzentrieren wir uns auf die Entwicklung allgemeiner Graphkerne, die auf Graphen mit oder ohne Labels angewendet werden können. Unsere Hauptbeiträge sind dabei die Folgenden:

Erstens beschleunigen wir die exakte Berechnung von Graphlet-Kernen von O(n^k) bis O(nd^{k-1}) für ein Paar Graphen, wobei n die Größe des Graphen ist, k die Größe der angewandten Graphlets, und d der maximale Grad der gegebenen Graphen.

Zweitens definieren wir einen neuen Kern für Graphen, den Weisfeiler-Lehman-Unterbaumkern, der der erste Graphkern ist, der linear in der Anzahl der Kanten in dem gegebenen Graphensatz skaliert. In unseren Experimenten auf Vergleichsdatensätzen aus der Chemoinformatik und der Bioinformatik skaliert der Weisfeiler-Lehman-Unterbaumkern bis zu großen Graphen und übertrifft alle bekannten Graphkerne an Geschwindigkeit mit vergleichbarer oder bessere Vorhersagegenauigkeit bei der Graphenklassifizierung.

Drittens verallgemeinen wir den Weisfeiler-Lehman-Unterbaumkern zu einer Kernfamilie, die viele bekannte Graphkerne als Spezialfälle beinhaltet. Diese Verallgemeinerung ermöglicht es bekannten Graphkerne, mehr Informationen über die Topologie der Graphen zu berücksichtigen.

Im letzten Teil dieser Dissertation präsentieren wir zwei Anwendungsbeispiele: Basierend auf den vorherigen Beiträgen schlagen wir spezialisierte Kerne für Pixelklassifizierung in Fernerkundungsbildern und Graphkerne für die Vorhersage von chemischen Verschiebungen in der strukturellen Bioinformatik vor. Unsere Kerne ermöglichen es erstmals, in diesen Anwendungen die reichhaltige Graphenstruktur beim Lernen zu nutzen.

Die Weisfeiler-Lehman-Kerne, die wir hier vorschlagen, ermöglichen es Graphkerne, auf große und gelabelte Graphen zu skalieren. Sie erlauben die Nutzung von Graphkernen in zahlreichen Anwendungsgebieten, die sich mit Graphen beschäftigen, dessen Größe und Labels mit bekannten Graphkernen vorher nicht verarbeitet werden konnten.