The computation of the maximum common subgraph (MCS) is one of the most prevalent problems in graph based data science. However, state-of-the-art algorithms for exact MCS computation have exponential time complexity. Actually, finding the MCS of two general graphs is an NP-complete problem, and thus, the definition of an exact algorithm with polynomial time complexity is only possible if P = NP. In the present paper, we thoroughly compare a novel concept called matching-graph — which is basically defined as the stable core of pairs of graphs — to the MCS. In particular, we research whether these matching-graphs — computable in polynomial time — offer a viable approximation for the MCS. The contribution of this paper is twofold. First, we demonstrate that for specific graphs a matching-graph equals the maximum common edge subgraph and thus its size builds an upper bound of the size of the maximum common induced subgraph. Second, in an experimental evaluation on seven graph datasets, we empirically confirm that the proposed matching-graph computation outperforms existing MCS (approximation) algorithms in terms of both computation time and classification accuracy. • The matching-graph (MG) is a graph that captures the similarity core of two graphs. • We propose to use the MG to approximate the MCS in polynomial time. • Given graphs with labeled nodes and unlabeled edges, the approximation equals MCES. • We show that the MG can be successfully used in a distance-based classifier.

Computing dissimilarities between pairs of graphs is a common task in many pattern recognition applications. A widely used method to accomplish this task is graph edit distance (GED). However, computation of exact GED is challenging due to its exponential time complexity with respect to the size of the underlying graphs. The major contribution of the present paper is that we introduce a complementary – and much faster – method to compute dissimilarities between pairs of graphs. Our novel framework involves a compressor-based metric that is adapted to the graph domain. Basically, the compressor-based metric identifies regularities in compressed graphs and assigns smaller distances to pairs of graphs that are comparable and are thus assumed to belong to the same class. To assess the effectiveness of the proposed graph matching framework, we perform a series of evaluations on eleven real-world datasets. It turns out that the novel matching framework performs equally well as, or even better than, GED, yet with significantly lower computation time. • We propose a novel graph matching termed Normalized Graph Compression Distance (NGCD) • We introduce a pre-processing step for NGCD that improves the classification accuracy. • We conduct empirical evaluations on 11 datasets to assess the benefits of NGCD. • We find that our framework NGCD outperforms the widely used graph edit distance.

Switzerland is home to the sources of major European rivers. As the thermal regime of rivers is crucial for the environment, the Federal Office for the Environment has been collecting discharge and water temperature data at 81 river water stations for several decades. However, despite diligent collection 30% of the water temperature data is missing due to various reasons. These missing data are problematic in many ways – for instance, in predicting water temperatures based on different models. To tackle this problem, we propose to use LSTMs for water temperature imputing. In particular, we introduce three different scenarios – depending on the available input data – to impute possible data gaps. Then, we propose several methods for each scenario. For our empirical evaluation, we engineer a novel dataset (with ground truth) by artificially introducing gaps of sizes 2, 10, 30 and 60 days in the middle of 90-day sequences. A rather simple interpolation baseline achieves a competitive RM SE on gaps of two days. For larger gaps, however, this simple method clearly fails, and the novel, far more sophisticated models significantly outperform both interpolation and the current state of the art in this application.

A common method to solve the non-trivial task of classifying general graphs is to employ graph matching in conjunction with a distance-or similarity-based classifier.Unfortunately, optimal graph matching has a high computational complexity hindering its application on large graphs.In order to make matchings also feasible for larger graphs, it has been proposed to work on size-reduced graphs rather than on their original counterparts.In the present paper, we propose a novel method that is based on this idea to further reduce the processing time.In particular, we change the standard classification scheme into a two-step classification method.In the first step, we start with strongly reduced versions of the graphs -having a manageable amount of nodes -in order to prune as many graphs as possible.The second step -the actual classification -is then performed on the remaining graphs only (in their original size).We conduct experimental evaluations on five datasets to research the benefits and limitations of this novel two-step graph classification method.The main finding is that we can substantially speed up the graph matching while preserving satisfying classification accuracy.

Graph-based pattern recognition – in particular in conjunction with large graphs – is often computationally expensive. This hampers, or makes it at least challenging, to employ graph-based representations for real-world data. To address this issue, we propose a method for reducing the size of the underlying graphs to their most important substructures using spectral graph clustering. The proposed method partitions the nodes of the graphs into clusters and then merges each cluster into supernodes. The motivation of this procedure is to reduce the computational cost of any graph comparison algorithm while maintaining the accuracy of the final classification. To assess the benefits and limitations of our method, we conduct thorough experiments on nine real-world datasets with different levels of graph reductions. The classification is obtained by four different graph classifiers (viz. a KNN based on graph edit distance, two SVMs based on a shortest path graph and a Weisfeiler-Lehman graph kernel, as well as a graph neural network). The results indicate that we can reduce computation time by up to two orders of magnitude without substantially degrading the classification accuracy.

The development and research of graph-based matching techniques that are both computationally efficient and accurate is a pivotal task due to the rapid growth of data acquisition and the omnipresence of structural data.In the present paper, we propose a novel framework using information gained from diversely reduced graph spaces to improve the classification accuracy of a structural classifier.The basic idea consists of three subsequent steps.First, the original graphs are reduced to different size levels with the aid of node centrality measures.Second, we compute the distances between the reduced graphs in the corresponding graph subspaces.Finally, the distances are linearly combined and fed into a distance-based classifier to produce the final classification.On six graph datasets we empirically demonstrate that classifiers clearly benefit from the combined distances obtained in the graph subspaces.

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.

Due to fast developments in data acquisition, we observe rapidly increasing amounts of data available in diverse areas. Simultaneously, we observe that in many applications the underlying data is inherently complex, making graphs a very useful and adequate data structure for formal representation. A large amount of graph based methods for pattern recognition have been proposed. Many of these methods actually rely on graph matching. In the present paper a novel encoding of graph matching information is proposed. The idea of this encoding is to formalize the stable cores of specific classes by means of graphs. In an empirical evaluation we show that it can be highly beneficial to focus on these stable parts of graphs during graph classification.

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(n^3)$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.

In recent years, different approaches for handwriting recognition that are based on graph representations have been proposed (e.g. graph-based keyword spotting or signature verification). This trend is mostly due to the availability of novel fast graph matching algorithms, as well as the inherent flexibility and expressivity of graph data structures when compared to vectorial representations. That is, graphs are able to directly adapt their size and structure to the size and complexity of the respective handwritten entities. However, the vast majority of the proposed approaches match the graphs from a global perspective only. In the present paper, we propose to match the underlying graphs from different local perspectives and combine the resulting assignments by means of Dynamic Time Warping. Moreover, we show that the proposed approach can be readily combined with global matchings. In an experimental evaluation, we employ the novel method in a signature verification scenario on two widely used benchmark datasets. On both datasets, we empirically confirm that the proposed approach outperforms state-of-the-art methods with respect to both accuracy and runtime.

Scanned handwritten historical documents are often not well accessible due to the limited feasibility of automatic full transcriptions. Thus, Keyword Spotting (KWS) has been proposed as an alternative to retrieve arbitrary query words from this kind of documents. In the present paper, word images are represented by means of graphs. That is, a graph is used to represent the inherent topological characteristics of handwriting. The actual keyword spotting is then based on matching a query graph with all document graphs. In particular, we make use of a fast graph matching algorithm that considers the contextual substructure of nodes. The motivation for this inclusion of node context is to increase the overall KWS accuracy. In an experimental evaluation on four historical documents, we show that the proposed procedure clearly outperforms diverse other template-based reference systems. Moreover, our novel framework keeps up or even outperforms many state-of-the-art learning-based KWS approaches.

For handwritten signature verification, signature images are typically represented with fixed-sized feature vectors capturing local and global properties of the handwriting. Graph-based representations offer a promising alternative, as they are flexible in size and model the global structure of the handwriting. However, they are only rarely used for signature verification, which may be due to the high computational complexity involved when matching two graphs. In this paper, we take a closer look at two recently presented structural methods for handwriting analysis, for which efficient matching methods are available: keypoint graphs with approximate graph edit distance and inkball models. Inkball models, in particular, have never been used for signature verification before. We investigate both approaches individually and propose a combined verification system, which demonstrates an excellent performance on the MCYT and GPDS benchmark data sets when compared with the state of the art.

The vast majority of user authentication in digital applications is based on alphanumeric passwords. Yet, due to severe problems that might arise with this approach, various efforts have been made in the last decade to replace this authentication paradigm. One candidate for the prospective paradigm shift might be found in the field of graphical passwords. The present paper introduces a novel framework for user authentication based on freehand sketches. The basic idea is that during the registration phase a user draws an arbitrary sketch in a specific drawing canvas (rather than typing a password). Registered users can then be authenticated whenever they are able to reproduce their personal sketch with sufficient precision. The major challenge of such a system is twofold. First, it has to provide a certain degree of error-tolerance such that the authentication of genuine users can be smoothly accomplished. Second, the system should detect even subtle forgeries and reject possible intruders. The main contributions of this paper are as follows. First, we formally represent the underlying sketches by means of strings and present a general authentication algorithm that is based on structural pattern recognition. Second, we present a novel cost model that is particularly useful in conjunction with string matching. Third, by means of an exhaustive empirical investigation using both random and skilled forgeries (stemming from several hundreds of users) we empirically confirm the feasibility of this particular authentication framework in a real-world scenario.

Graphs provide a powerful representation formalism for handwritten signatures, capturing local properties as well as their relations. Yet, although introduced early for signature verification, only a few current systems rely on graph-based representations. A possible reason is the high computational complexity involved for matching two general graphs. In this paper, we introduce a novel structural approach to offline signature verification using an efficient cubic-time approximation of graph edit distance. We put forward several ways of creating, normalizing, and comparing signature graphs built from keypoints and investigate their performance on three benchmark datasets. The experiments demonstrate a promising performance of the proposed structural approach when compared with the state of the art.

Keyword Spotting (KWS) offers a convenient way to improve the accessibility to historical handwritten documents by retrieving search terms in scanned document images. The approach for KWS proposed in the present paper is based on segmented word images that are represented by means of different types of graphs. The actual keyword spotting is based on matching a query graph with a set of document graphs using the concept of graph edit distance. In particular, we propose to employ ensemble methods for KWS with graphs. That is, a query graph is not matched against one but several different graphs representing the same document word. Eventually, we use different strategies to combine these individual graph dissimilarities. In an experimental evaluation on two benchmark datasets, the proposed ensemble methods outperform the individual ensemble members as well as four state-of-the-art reference systems based on dynamic time warping.

This paper introduces a novel method of reducing the number of prototype patterns necessary for accurate recognition of temporal patterns. The nearest neighbor (NN) method is an effective tool in pattern recognition, but the downside is it can be computationally costly when using large quantities of data. To solve this problem, we propose a method of representing the temporal patterns by embedding dynamic time warping (DTW) distance based dissimilarities in vector space. Adaptive boosting (AdaBoost) is then applied for classifier training and feature selection to reduce the number of prototype patterns required for accurate recognition. With a data set of handwritten digits provided by the International Unipen Foundation (iUF), we successfully show that a large quantity of temporal data can be efficiently classified produce similar results to the established NN method while performing at a much smaller cost.

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.

One of the major tasks in many applications in the field of document analysis is the computation of dissimilarities between two or more objects from a given problem domain. Hence, employing graphs as representation formalism evokes the need for powerful, fast and flexible graph based dissimilarity models. Graph edit distance is powerful and applicable to any kind of graphs but suffers from its high computational complexity. Recently, however, a novel framework for graph edit distance approximation has been introduced. While the run time of this novel procedure is very convincing, the precision of the approximated graph distances is dissatisfying in some cases. The present paper introduces a generalized version of the existing approximation framework using an iterative bipartite procedure. With empirical investigations on three real world data sets we show that our extension substantially improves the accuracy of the approximations while the run time is increased only linearly with the number of additional iterations.

In recent years the authors of the present paper introduced a powerful approximation fra or the graph edit distance problem. The basic idea of this approximation is to build a square cost matrix C = (cj), where each entry reflects the cost of a node substitution, deletion or insertion plus the matching cost arising from the local edge structure. Based on C an optimal assignment of the nodes and their local structure can be established in polynomial time (using, for instance, the Hungarian algorithm). Since this approach considers the local -- rather than the global -- structural properties of the graphs only, the obtained graph edit distance value is suboptimal in the sense of overestimating the true edit distance in general. The present paper pursues the idea of including topological information in the node labels in order to increase the amount of structural information available during the initial assignment process. In an experimental evaluation on three real world data sets a reduction of the overestimation can be observed while the run time is only moderately increased compared to our original framework.

Graphs provide us with a flexible and powerful way to represent objects in various areas of computer science. One of the main drawbacks is, however, that many standard algorithms on graphs have a high computational complexity. The present paper considers the problem of graph isomorphism, i.e. checking two graphs for identity. A novel approach for the efficient computation of graph isomorphism is presented. The proposed algorithm is based on bipartite graph matching by means of an assignment algorithm. The algorithmic framework is suboptimal in the sense of possibly rejecting pairs of graphs without making a decision. As an advantage, however, it offers polynomial runtime. In experiments on diverse graph data sets we demonstrate substantial speedups of our proposed method over several standard procedures for graph isomorphism. Furthermore, although the computational framework for isomorphism is suboptimal, we show that the proposed algorithm rejects only very few pairs of graphs and otherwise returns correct results.

Automatic transcription of historical documents is vital for the creation of digital libraries. In this paper we propose graph similarity features as a novel descriptor for handwriting recognition in historical documents based on Hidden Markov Models. Using a structural graph-based representation of text images, a sequence of graph similarity features is extracted by means of dissimilarity embedding with respect to a set of character prototypes. On the medieval Parzival data set it is demonstrated that the proposed structural descriptor significantly outperforms two well-known statistical reference descriptors for single word recognition.

Simple weighted undirected graphs with a fixed number of vertices and fixed vertex orderings can be used to represent data and patterns in a wide variety of scientific and engineering domains. Classification of such graphs by existing graph matching methods perform rather poorly because they do not exploit their specificity. As an alternative, methods relying on vector-space embedding hold promising potential. We propose two such techniques that can be deployed as a front-end for any pattern recognition classifiers: one has low computational cost but generates high-dimensional spaces, while the other is more computationally demanding but can yield relatively low-dimensional vector space representations. We show experimental results on an fMRI brain state decoding task and discuss the shortfalls of graph edit distance for the type of graph under consideration.

Graphs provide us with a powerful and flexible representation formalism for pattern classification. Many classification algorithms have been proposed in the literature. However, the vast majority of these algorithms rely on vectorial data descriptions and cannot directly be applied to graphs. Recently, a growing interest in graph kernel methods can be observed. Graph kernels aim at bridging the gap between the high representational power and flexibility of graphs and the large amount of algorithms available for object representations in terms of feature vectors. In the present paper, we propose an approach transforming graphs into n-dimensional real vectors by means of prototype selection and graph edit distance computation. This approach allows one to build graph kernels in a straightforward way. It is not only applicable to graphs, but also to other kind of symbolic data in conjunction with any kind of dissimilarity measure. Thus it is characterized by a high degree of flexibility. With several experimental results, we prove the robustness and flexibility of our new method and show that our approach outperforms other graph classification methods on several graph data sets of diverse nature.

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.

Graphs are powerful data structures that have many attractive properties for object representation. However, some basic operations are difficult to define and implement, for instance, how to obtain a representative of a set of graphs. The median graph has been defined for that purpose, but existing algorithms are computationally complex and have a very limited applicability. In this paper we propose a new approach for the computation of the median graph based on graph embedding in vector spaces. Experiments on a real database containing large graphs show that we succeed to compute good approximations of the median graph. We have also applied the median graph to perform some basic classification tasks achieving reasonable good results.

In structural pattern recognition, a major drawback of graph based representation is the lack of algorithmic tools. To overcome this lack, we embed graphs in vector spaces by means of prototype selection and graph edit distance, thus making them available to all algorithms of statistical pattern recognition that operate on feature vectors. In previous work a similar procedure was applied. However, the only classifier used within this framework was support vector machine (SVM). In the present paper, we significantly extend the scope of the previous work and present an experimental study where, in addition to SVM, a number of other well established classifiers from statistical pattern recognition are used for graph classification. On a total of five different graph data sets of diverse nature it is demonstrated that the proposed graph embedding in conjunction with standard classifiers from statistical pattern recognition has great potential to outperform classification methods applied in the original graph domain.

The motivation of classifier ensembles is that errors of an individual classifier can often be compensated by the other ensemble members. In the present paper we introduce a general approach to building structural classifier ensembles, i.e. classifiers that make use of graphs as representation formalism and include strings and trees as special cases. The proposed methodology is based on graph embedding in real vector spaces by means of prototype selection. This selection is performed randomized eta times such that the procedure leads to eta different graph embeddings. Hence, a classifier can be trained for each embedding and the results of the individual classifiers can be combined in an appropriate way. In the present paper we take into account that not only the prototypes themselves but also their number has a critical impact on the classification accuracy in the resulting vector space. In several experimental results we make investigations on the classification accuracy of the resulting classifier ensembles and compare them with single classifier systems.