Preview

PDF, English - main document Download (3MB) | Terms of use

Abstract

For many applications, such as drug discovery, road network analysis, and image processing, it is critical to study spatial properties of objects in addition to object relationships. Geometric graphs provide a suitable modeling framework for such applications, where vertices are located in some 2D space. As a result, searching for similar objects is tackled by estimating the similarity of the structure of different graphs. In this case, inexact graph matching approaches are typically employed. However, computing the optimal solution to the graph matching problem is proved to be a very complex task. In addition to this, approximate approaches face many problems such as poor scalability with respect to graph size and less tolerance to changes in graph structure or labels.

In this thesis, we propose a framework to tackle the inexact graph matching problem for geometric graphs in 2D space. It consists of a pipeline of three components that we design to cope with the requirements of several application domains. The first component of our framework is an approach to estimate the similarity of vertices. It is based on the string edit distance and handles any labeling information assigned to the vertices and edges. Based on this, we build the second component of our framework. It consists of two algorithms to tackle the inexact graph matching problem. The first algorithm adopts a probabilistic scheme, where we propose a density function that estimates the probability of the correspondences between vertices of different graphs. Then, a match between the two graphs is computed utilizing the expectation maximization technique. The second graph matching algorithm follows a continuous optimization scheme to iteratively improve the match between two graphs. For this, we propose a vertex embedding approach so that the similarity of different vertices can be easily estimated by the Euclidean distance. The third component of our framework is a graph indexing structure, which helps to efficiently search a graph database for similar graphs. We propose several lower bound graph distances that are used to prune non-similar graphs and reduce the response time.

Using representative geometric graphs extracted from a variety of applications domains, such as chemoinformatics, character recognition, road network analysis, and image processing, we show that our approach outperforms existing graph matching approaches in terms of matching quality, classification accuracy, and runtime.

Translation of abstract (German)

Für viele Anwendungen wie beispielsweise die Arzneimittelforschung, Straßennetzwerkanalyse und Bildverarbeitung ist die Analyse räumlicher Eigenschaften von Objekten zusätzlich zu den Beziehungen zwischen den Objekten von zentraler Bedeutung. Für solche Anwendungen bieten geometrische Graphen einen geeigneten Modellierungsrahmen, in dem Knoten im zweidimensionalen Raum dargestellt werden. Hierdurch können Ähnlichkeiten zwischen Objekten durch die Abschätzung der Ähnlichkeiten ihrer Graphen bestimmt werden. Dafür werden typischerweise inexakte Graph-Matching-Verfahren verwendet. Allerdings wurde gezeigt, dass die Berechnung einer optimalen Lösungen für das Graph-Matching-Problem eine sehr komplexe Aufgabe darstellt. Außerdem sind die Skalierbarkeit in Bezug auf die Größe der Graphen und die Toleranz gegenüber Änderungen in der Graphstruktur weitere Schwächen inexakter Ansätze.

In dieser Arbeit stellen wir ein neues Framework vor, um das inexakte Graph-Matching-Problem für geometrische Graphen im zweidimensionalen Raum zu lösen. Dieses besteht aus einer dreiteiligen Pipeline, die wir so entworfen haben, dass die Anforderungen zahlreicher Anwendungsgebiete berücksichtigt werden. Die erste Komponente ist ein Ansatz zur Abschätzung von Knotenähnlichkeiten, die auf der String-Edit-Distance basiert und jegliche Knoten- und Kanteneigenschaften berücksichtigt. Darauf aufbauend besteht die zweite Komponente aus zwei Algorithmen zur Berechnung des Graph-Matching-Problems. Der erste Algorithmus basiert auf einer Wahrscheinlichkeitsschätzung, für die wir eine Dichtefunktion zur Berchnung der Übereinstimmungswahrscheinlichkeiten zwischen Knoten verschiedener Graphen entwickelt haben. Danach wird die Übereinstimmung zwischen zwei Graphen mithilfe von Expectation Maximization errechnet. Der zweite Graph-Matching-Algorithmus wendet dagegen ein kontinuierliches Optimierungsschema an, um die Übereinstimmungen iterativ zu verbessern. Hierfür schlagen wir einen Ansatz zur Einbettung der Konten vor, so dass die Ähnlichkeit verschiedener Knoten schlicht anhand der Euklidischen Distanz abgeschätzt werden kann. Die letzte Komponente des Frameworks bildet schließlich eine Graph-Indexstruktur, die das effiziente Durchsuchen einer Graphdatenbank nach ähnlichen Graphen ermöglicht. Zusätzlich stellen wir mehrere Graphabstandsfunktionen zum Ausschließen unähnlicher Graphen vor, um die Laufzeit zu optimieren.

Anhand einer repräsentativen Auswahl geometrischer Graphen aus unterschiedlichen Anwendungsbereichen zeigen wir, dass unser Ansatz bessere Ergebnisse bezüglich Matching-Qualität, Klassifikationsgenauigkeit und Laufzeit erzielt als existierende Ansätze.