Search

In this chapter we introduce hypergraphs as a generalisation of graphs for object representation in structural pattern recognition. We also propose extensions of algorithms for the matching and error-tolerant matching of graphs to the case of hypergraphs, including the edit distance of hypergraphs. In a series of experiments, we demonstrate the practical applicability of the proposed hypergraph matching algorithms and show some of the advantages of hypergraphs over conventional graphs. [ABSTRACT FROM AUTHOR]

In this paper we propose a quadratic programming approach to computing the edit distance of graphs. Whereas the standard edit distance is defined with respect to a minimum-cost edit path between graphs, we introduce the notion of fuzzy edit paths between graphs and provide a quadratic programming formulation for the minimization of fuzzy edit costs. Experiments on real-world graph data demonstrate that our proposed method is able to outperform the standard edit distance method in terms of recognition accuracy on two out of three data sets. [ABSTRACT FROM AUTHOR]

In the field of structural pattern recognition graphs constitute a very common and powerful way of representing patterns. In contrast to string representations, graphs allow us to describe relational information in the patterns under consideration. One of the main drawbacks of graph representations is that the computation of standard graph similarity measures is exponential in the number of involved nodes. Hence, such computations are feasible for rather small graphs only. One of the most flexible error-tolerant graph similarity measures is based on graph edit distance. In this paper we propose an approach for the efficient compuation of edit distance based on bipartite graph matching by means of Munkres' algorithm, sometimes referred to as the Hungarian algorithm. Our proposed algorithm runs in polynomial time, but provides only suboptimal edit distance results. The reason for its suboptimality is that implied edge operations are not considered during the process of finding the optimal node assignment. In experiments on semi-artificial and real data we demonstrate the speedup of our proposed method over a traditional tree search based algorithm for graph edit distance computation. Also we show that classification accuracy remains nearly unaffected. [ABSTRACT FROM AUTHOR]

Multiple classifier systems are a well proven and tested instrument for enhancing the recognition accuracy in statistical pattern recognition problems. However, there has been reported only little work on combining classifiers in structural pattern recognition. In this paper we describe a method for embedding strings into real vector spaces based on prototype selection, in order to gain several vectorial descriptions of the string data. We present methods for combining multiple classifiers trained on various vectorial data representations. As base classifiers we use nearest neighbor methods and support vector machine. In our experiments we demonstrate that this approach can be used to significantly improve the classification accuracy of string patterns. [ABSTRACT FROM AUTHOR]

A common way of expressing string similarity in structural pattern recognition is the edit distance. It allows one to apply the kNN rule in order to classify a set of strings. However, compared to the wide range of elaborated classifiers known from statistical pattern recognition, this is only a very basic method. In the present paper we propose a method for transforming strings into n-dimensional real vector spaces based on prototype selection. This allows us to subsequently classify the transformed strings with more sophisticated classifiers, such as support vector machine and other kernel based methods. In a number of experiments, we show that the recognition rate can be significantly improved by means of this procedure. [ABSTRACT FROM AUTHOR]

Random walk kernels in conjunction with Support Vector Machines are powerful methods for error-tolerant graph matching. Because of their local definition, however, the applicability of random walk kernels strongly depends on the characteristics of the underlying graph representation. In this paper, we describe a simple extension to the standard random walk kernel based on graph edit distance. The idea is to include global matching information in the local similarity evaluation of random walks in graphs. The proposed extension allows us to improve the performance of the random walk kernel significantly. We present an experimental evaluation of our method on three difficult graph datasets. [ABSTRACT FROM AUTHOR]

Graph edit distance is one of the most flexible mechanisms for error-tolerant graph matching. Its key advantage is that edit distance is applicable to unconstrained attributed graphs and can be tailored to a wide variety of applications by means of specific edit cost functions. Its computational complexity, however, is exponential in the number of vertices, which means that edit distance is feasible for small graphs only. In this paper, we propose two simple, but effective modifications of a standard edit distance algorithm that allow us to suboptimally compute edit distance in a faster way. In experiments on real data, we demonstrate the resulting speedup and show that classification accuracy is mostly not affected. The suboptimality of our methods mainly results in larger inter-class distances, while intra-class distances remain low, which makes the proposed methods very well applicable to distance-based graph classification. [ABSTRACT FROM AUTHOR]

The combination of multiple classifiers has been successful in improving classification accuracy in many pattern recognition problems. For graph matching, the fusion of classifiers is normally restricted to the decision level. In this paper we propose a novel fusion method for graph patterns. Our method detects common parts in graphs in an error-tolerant way using graph edit distance and constructs graphs representing the common parts only. In experiments, we demonstrate on two datasets that the method is able to improve the classification of graphs. [ABSTRACT FROM AUTHOR]

Structural pattern representations, especially graphs, have advantages over feature vectors. However, they also suffer from a number of disadvantages, for example, their high computational complexity. Moreover, we observe that in the field of statistical pattern recognition a number of powerful concepts emerged recently that have no equivalent counterpart in the domain of structural pattern recognition yet. Examples include multiple classifier systems and kernel methods. In this paper, we survey a number of recent developments that may be suitable to overcome some of the current limitations of graph based representations in pattern recognition. Keywords: structural pattern recognition, graph matching, graph edit distance, automatic learning of cost functions, graph kernel methods, multiple classifier systems, graph database retrieval. [ABSTRACT FROM AUTHOR]

In this paper we propose the use of a simple kernel function based on the graph edit distance. The kernel function allows us to apply a wide range of statistical algorithms to the problem of attributed graph matching. The function we describe is simple to compute and leads to several convenient interpretations of geometric properties of graphs in their implicit vector space representation. Although the function is not generally positive definite, we show in experiments on real-world data that the kernel approach may result in a significant improvement of the graph matching and classification performance using support vector machines and kernel principal component analysis. [ABSTRACT FROM AUTHOR]

In the present paper we address the fingerprint classification problem with a structural pattern recognition approach. Our main contribution is the definition of modified directional variance in orientation vector fields. The new directional variance allows us to extract regions from fingerprints that are relevant for the classification in the Henry scheme. After processing the regions of interest, the resulting structures are converted into attributed graphs. The classification is finally performed with an efficient graph edit distance algorithm. The performance of the proposed classification method is evaluated on the NIST-4 database of fingerprints. [ABSTRACT FROM AUTHOR]