Search

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. [ABSTRACT FROM AUTHOR]

Approximation of graph edit distance in polynomial time enables us to compare large, arbitrarily labeled graphs for structural pattern recognition. In a recent approximation framework, bipartite graph matching (BP) has been proposed to reduce the problem of edit distance to a cubic-time linear sum assignment problem (LSAP) between local substructures. Following the same line of research, first attempts towards quadratic-time approximation have been made recently, including a lower bound based on Hausdorff matching (Hausdorff Edit Distance) and an upper bound based on greedy assignment (Greedy Edit Distance). In this paper, we compare the two approaches and derive a novel upper bound (BP2) which combines advantages of both. In an experimental evaluation on the IAM graph database repository, we demonstrate that the proposed quadratic-time methods perform equally well or, quite surprisingly, in some cases even better than the cubic-time method. [ABSTRACT FROM AUTHOR]

Due to their high representational power and flexibility, graphs have emerged as a widely used data structure for complex pattern representation. The advantages of graphs are, however, at the expense of a substantial increase of the computational complexity of the associated algorithms. For instance, exact graph similarity or distance can be computed in exponential time only. An algorithmic framework based on bipartite graph matching (allowing graph dissimilarity computation in cubic time) has been presented recently. However, this fast computation leads in general to some incorrect node assignments with respect to a globally optimal graph matching. In this paper we present a novel methodology for predicting which of the node assignments are actually incorrectly assigned by this approximation. To this end, a comprehensive set of features – which numerically characterize the assignments – is defined and extracted from the underlying graphs. These features are in turn used for training a statistical classifier, which can eventually be employed for predicting unseen assignments. The power and applicability of our novel approach is empirically verified on eight real world data sets. [ABSTRACT FROM AUTHOR]

• We propose a new data structure called matching-graph, that incorporates the similarity core of two graphs. • We present both, a distance based classifier and a graph embedding kernel based on the novel matching-graphs. • We confirm a significant improvement of classification algorithms that directly, or indirectly, use matching-graphs. [Display omitted] The increasing amount of data available and the rate at which it is collected leads to rapid developments of systems for intelligent information processing and pattern recognition. Often the underlying data is inherently complex, making it difficult to represent it by linear, vectorial data structures. This is where graphs offer a versatile alternative for formal data representation. Actually, quite an amount of graph-based methods for pattern recognition has been proposed. A considerable part of these methods rely on graph matching. In the present paper, we propose a novel encoding of specific graph matching information. The basic idea is to formalize the stable cores of individual classes of graphs – discovered during intra-class matchings – by means of so called matching-graphs. We evaluate the benefit of these matching-graphs by researching two classification approaches that rely on this novel data structure. The first approach is a distance based classifier focusing on the matching-graphs during dissimilarity computation. For the second approach, we propose to use sets of matching-graphs to embed input graphs into a vector space. The basic idea is to produce hundreds of matching-graphs first, and then represent each graph g as a vector that shows the occurrence of, or the distance to, each matching-graph. In a thorough experimental evaluation on seven real world data sets we empirically confirm that our novel approaches are able to improve the classification accuracy of systems that rely on comparable information as well as state-of-the-art methods. [ABSTRACT FROM AUTHOR]

The concept of graph edit distance (GED) is still one of the most flexible and powerful graph matching approaches available. Yet, exact computation of GED can be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, this approach considers local - rather than the global - structural properties of the graphs only, and thus GED derived from the optimal node assignment generally overestimates the true edit distance. Recently, it has been shown how the existing approximation framework can be exploited to additionally derive a lower bound of the exact edit distance without any additional computations. In this paper we make use of regression analysis in order to predict the exact GED using these two bounds. In an experimental evaluation on diverse graph data sets we empirically verify the gain of distance accuracy of the estimated GEDs compared to both bounds. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract: In recent years, the use of graph based object representation has gained popularity. Simultaneously, graph edit distance emerged as a powerful and flexible graph matching paradigm that can be used to address different tasks in pattern recognition, machine learning, and data mining. The key advantages of graph edit distance are its high degree of flexibility, which makes it applicable to any type of graph, and the fact that one can integrate domain specific knowledge about object similarity by means of specific edit cost functions. Its computational complexity, however, is exponential in the number of nodes of the involved graphs. Consequently, exact graph edit distance is feasible for graphs of rather small size only. In the present paper we introduce a novel algorithm which allows us to approximately, or suboptimally, compute edit distance in a substantially faster way. The proposed algorithm considers only local, rather than global, edge structure during the optimization process. In experiments on different datasets we demonstrate a substantial speed-up of our proposed method over two reference systems. Moreover, it is emprically verified that the accuracy of the suboptimal distance remains sufficiently accurate for various pattern recognition applications. [Copyright &y& Elsevier]

Due to the ability of graphs to represent properties of entities and binary relations at the same time, a growing interest in this representation formalism can be observed in various fields of pattern recognition. The availability of a distance measure is a basic requirement for pattern recognition. For graphs, graph edit distance is still one of the most popular distance measures. In the present paper we substantially improve the distance accuracy of a recent framework for the approximation of graph edit distance. The basic idea of our novel approach is to manipulate the initial assignment returned by the approximation algorithm such that the individual assignments are ordered according to their individual confidence. Next, the individual assignments are post processed in this specific order. In an experimental evaluation we show that the order of the assignments plays a crucial role for the resulting distance accuracy. Moreover, we empirically verify that our novel generalization is able to generate approximations which are very near to the exact edit distance (in contrast with the original framework). [ABSTRACT FROM AUTHOR]

• Combination of a structural and a statistical signature verification system. • The structural approach is based on an approximation of the graph edit distance. • The statistical approach is based on a convolutional neural network with triplet loss. • Combined approach improves significantly compared to individual approaches. • Excellent results on 4 public datasets despite being trained on synthetic data only. Offline signature verification is a challenging pattern recognition task where a writer model is inferred using only a small number of genuine signatures. A combination of complementary writer models can make it more difficult for an attacker to deceive the verification system. In this work, we propose to combine a recent structural approach based on graph edit distance with a statistical approach based on deep triplet networks. The combination of the structural and statistical models achieve significant improvements in performance on four publicly available benchmark datasets, highlighting their complementary perspectives. [ABSTRACT FROM AUTHOR]

Graph edit distance is a powerful and flexible method for error-tolerant graph matching. Yet it can only be calculated for small graphs in practice due to its exponential time complexity when considering unconstrained graphs. In this paper we propose a quadratic time approximation of graph edit distance based on Hausdorff matching. In a series of experiments we analyze the performance of the proposed Hausdorff edit distance in the context of graph classification and compare it with a cubic time algorithm based on the assignment problem. Investigated applications include nearest neighbor classification of graphs representing letter drawings, fingerprints, and molecular compounds as well as hidden Markov model classification of vector space embedded graphs representing handwriting. In many cases, a substantial speedup is achieved with only a minor loss in accuracy or, in one case, even with a gain in accuracy. Overall, the proposed Hausdorff edit distance shows a promising potential in terms of flexibility, efficiency, and accuracy. [ABSTRACT FROM AUTHOR]