AbstractsMathematics

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. 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…