Building Multiple Classifier Systems Using Linear Combinations of Reduced Graphs.

Despite great efforts done in research in the last decades, the classification of general graphs, i.e., graphs with unconstrained labeling and structure, remains a challenging task. Due to the inherent relational structure of graphs it is difficult, or even impossible, to apply standard pattern recognition methods to graphs to achieve high recognition accuracies. Common methods to solve the non-trivial problem of graph classification employ graph matching in conjunction with a distance-based classifier or a kernel machine. In the present paper, we address the specific task of graph classification by means of a novel framework that uses information acquired from a broad range of reduced graph subspaces. Our novel approach can be roughly divided into three successive steps. In the first step, differently reduced graphs are created out of the original graphs relying on node centrality measures. In the second step, we compute the graph edit distance between each reduced graph and all the other graphs of the corresponding graph subspace. Finally, we linearly combine the distances in the third step and feed them into a distance-based classifier to obtain the final classification result. On six graph data sets, we empirically confirm that the proposed multiple classifier system directly benefits from the combined distances computed in the various graph subspaces.

Approximate Graph Edit Distance in Quadratic Time.

Graph edit distance is one of the most flexible and general graph matching models available. The major drawback of graph edit distance, however, is its computational complexity that restricts its applicability to graphs of rather small size. Recently, the authors of the present paper introduced a general approximation framework for the graph edit distance problem. The basic idea of this specific algorithm is to first compute an optimal assignment of independent local graph structures (including substitutions, deletions, and insertions of nodes and edges). This optimal assignment is complete and consistent with respect to the involved nodes of both graphs and can thus be used to instantly derive an admissible (yet suboptimal) solution for the original graph edit distance problem in O(n3) time. For large scale graphs or graph sets, however, the cubic time complexity may still be too high. Therefore, we propose to use suboptimal algorithms with quadratic rather than cubic time for solving the basic assignment problem. In particular, the present paper introduces five different greedy assignment algorithms in the context of graph edit distance approximation. In an experimental evaluation, we show that these methods have great potential for further speeding up the computation of graph edit distance while the approximated distances remain sufficiently accurate for graph based pattern classification.

Novel kernels for error-tolerant graph classification.

One of the major difficulties in graph classification is the lack of mathematical structure in the space of graphs. The use of kernel machines allows us to overcome this fundamental limitation in an elegant manner by addressing the pattern recognition problem in an implicitly existing feature vector space instead of the original space of graphs. In this paper we propose three novel error-tolerant graph kernels -- a diffusion kernel, a convolution kernel, and a random walk kernel. The kernels are closely related to one of the most flexible graph matching methods, graph edit distance. Consequently, our kernels are applicable to virtually any kind of graph. They also show a high degree of robustness against various types of distortion. In an experimental evaluation involving the classification of line drawings, images, diatoms, fingerprints, and molecules, we demonstrate the superior performance of the proposed kernels in conjunction with support vector machines over a standard nearest-neighbor reference method and several other graph kernels including a standard random walk kernel.

Graph classification by means of Lipschitz embedding.

In pattern recognition and related fields, graph-based representations offer a versatile alternative to the widely used feature vectors. Therefore, an emerging trend of representing objects by graphs can be observed. This trend is intensified by the development of novel approaches in graph-based machine learning, such as graph kernels or graph-embedding techniques. These procedures overcome a major drawback of graphs, which consists of a serious lack of algorithms for classification. This paper is inspired by the idea of representing graphs through dissimilarities and extends our previous work to the more general setting of Lipschitz embeddings. In an experimental evaluation, we empirically confirm that classifiers that rely on the original graph distances can be outperformed by a classification system using the Lipschitz embedded graphs.