A Survey on Applications of Bipartite Graph Edit Distance
---
paper_title: GRAPH MATCHING AND LEARNING IN PATTERN RECOGNITION IN THE LAST 10 YEARS

paper_content:

In this paper, we examine the main advances registered in the last ten years in Pattern Recognition methodologies based on graph matching and related techniques, analyzing more than 180 papers; the aim is to provide a systematic framework presenting the recent history and the current developments. This is made by introducing a categorization of graph-based techniques and reporting, for each class, the main contributions and the most outstanding research results.
---
paper_title: THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION

paper_content:

A recent paper posed the question: "Graph Matching: What are we really talking about?". Far from providing a definite answer to that question, in this paper we will try to characterize the role that graphs play within the Pattern Recognition field. To this aim two taxonomies are presented and discussed. The first includes almost all the graph matching algorithms proposed from the late seventies, and describes the different classes of algorithms. The second taxonomy considers the types of common applications of graph-based techniques in the Pattern Recognition and Machine Vision field.
---
paper_title: Graph Kernels For Disease Outcome Prediction From Protein-Protein Interaction Networks

paper_content:

It is widely believed that comparing discrepancies in the protein-protein interaction (PPI) networks of individuals will become an important tool in understanding and preventing diseases. Currently PPI networks for individuals are not available, but gene expression data is becoming easier to obtain and allows us to represent individuals by a co-integrated gene expression/protein interaction network. Two major problems hamper the application of graph kernels ‐ state-of-the-art methods for whole-graph comparison ‐ to compare PPI networks. First, these methods do not scale to graphs of the size of a PPI network. Second, missing edges in these interaction networks are biologically relevant for detecting discrepancies, yet, these methods do not take this into account. In this article we present graph kernels for biological network comparison that are fast to compute and take into account missing interactions. We evaluate their practical performance on two datasets of co-integrated gene expression/PPI networks.
---
paper_title: A distance measure between attributed relational graphs for pattern recognition

paper_content:

A method to determine a distance measure between two nonhierarchical attributed relational graphs is presented. In order to apply this distance measure, the graphs are characterised by descriptive graph grammars (DGG). The proposed distance measure is based on the computation of the minimum number of modifications required to transform an input graph into the reference one. Specifically, the distance measure is defined as the cost of recognition of nodes plus the number of transformations which include node insertion, node deletion, branch insertion, branch deletion, node label substitution and branch label substitution. The major difference between the proposed distance measure and the other ones is the consideration of the cost of recognition of nodes in the distance computation. In order to do this, the principal features of the nodes are described by one or several cost functions which are used to compute the similarity between the input nodes and the reference ones. Finally, an application of this distance measure to the recognition of lower case handwritten English characters is presented.
---
paper_title: Graph Theoretic Techniques For Web Content Mining

paper_content:

Thank you very much for downloading graph theoretic techniques for web content mining. Maybe you have knowledge that, people have look hundreds times for their favorite books like this graph theoretic techniques for web content mining, but end up in harmful downloads. Rather than reading a good book with a cup of tea in the afternoon, instead they cope with some malicious bugs inside their computer.
---
paper_title: Inexact graph matching for structural pattern recognition

paper_content:

This paper is concerned with the inexact matching of attributed, relational graphs for structural pattern recognition. The matching procedure is based on a state space search utilizing heuristic information. Some experimental results are reported.
---
paper_title: Graph kernels for molecular structure-activity relationship analysis with support vector machines

paper_content:

The support vector machine algorithm together with graph kernel functions has recently been introduced to model structure−activity relationships (SAR) of molecules from their 2D structure, without the need for explicit molecular descriptor computation. We propose two extensions to this approach with the double goal to reduce the computational burden associated with the model and to enhance its predictive accuracy: description of the molecules by a Morgan index process and definition of a second-order Markov model for random walks on 2D structures. Experiments on two mutagenicity data sets validate the proposed extensions, making this approach a possible complementary alternative to other modeling strategies.
---
paper_title: Approximate graph edit distance computation by means of bipartite graph matching

paper_content:

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.
---
paper_title: Matching graphs with unique node labels

paper_content:

A special class of graphs is introduced in this paper. The graphs belonging to this class are characterised by the existence of unique node labels. A number of matching algorithms for graphs with unique node labels are developed. It is shown that problems such as graph isomorphism, subgraph isomorphism, maximum common subgraph (MCS) and graph edit distance (GED) have a computational complexity that is only quadratic in the number of nodes. Moreover, computing the median of a set of graphs is only linear in the cardinality of the set. In a series of experiments, it is demonstrated that the proposed algorithms run very fast in practice. The considered class makes the matching of large graphs, consisting of thousands of nodes, computationally tractable. We also discuss an application of the considered class of graphs and related matching algorithms to the classification and detection of abnormal events in computer networks.
---
paper_title: Approximate Graph Edit Distance in Quadratic Time

paper_content:

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 <inline-formula><tex-math notation="LaTeX">$O(n^3)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mn>3</mml:mn></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="riesen-ieq1-2478463.gif"/></alternatives></inline-formula> 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.
---
paper_title: Fast computation of Bipartite graph matching

paper_content:

Abstract We present a new algorithm to compute the Graph Edit Distance in a sub-optimal way. We demonstrate that the distance value is exactly the same than the one obtained by the algorithm called Bipartite but with a reduced run time. The only restriction we impose is that the edit costs have to be defined such that the Graph Edit Distance can be really defined as a distance function, that is, the cost of insertion plus deletion of nodes (or arcs) have to be lower or equal than the cost of substitution of nodes (or arcs). Empirical validation shows that higher is the order of the graphs, higher is the obtained Speed up.
---
paper_title: Improving bipartite graph edit distance approximation using various search strategies

paper_content:

Recently the authors of the present paper introduced an approximation framework for the graph edit distance problem. The basic idea of this approximation is to first build a square cost matrix C = ( c ij ) , where each entry cij 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. Since this approach considers local - rather than the global - structural properties of the graphs only, the graph edit distance derived from the optimal node assignment generally overestimates the true edit distance. The present paper pursues the idea of applying additional search strategies that build upon the initial assignment in order to reduce this overestimation. To this end, six different search strategies are investigated in this paper. In an exhaustive experimental evaluation on five real world graph data sets we empirically verify a substantial gain of distance accuracy by means of all search methods while run time remains remarkably low. HighlightsWe show how the well-known bipartite graph edit distance approximation can substantially be improved with respect to distance accuracy.To this end, we introduce and compare six different methodologies for extending the graph matching framework.We empirically verify a substantial gain of distance accuracy by means of all methods while run time remains remarkably low.The benefit of improved distance quality is also verified in a clustering application.
---
paper_title: Improved quadratic time approximation of graph edit distance by combining Hausdorff matching and greedy assignment

paper_content:

Review of recent quadratic-time approximations of graph edit distance.Novel upper bound based on bipartite assignment in quadratic time (BP2).Combines the principle of Hausdorff distance with bijective node substitutions.Evaluated empirically on the IAM graph database repository.Outperforms previous cubic-time approximation based on bipartite assignment (BP). 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.
---
paper_title: Approximate graph edit distance computation by means of bipartite graph matching

paper_content:

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.
---
paper_title: Approximate Graph Edit Distance Guided by Bipartite Matching of Bags of Walks

paper_content:

The definition of efficient similarity or dissimilarity measures between graphs is a key problem in structural pattern recognition. This problem is nicely addressed by the graph edit distance, which constitutes one of the most flexible graph dissimilarity measure in this field. Unfortunately, the computation of an exact graph edit distance is known to be exponential in the number of nodes. In the early beginning of this decade, an efficient heuristic based on a bipartite assignment algorithm has been proposed to find efficiently a suboptimal solution. This heuristic based on an optimal matching of nodes' neighborhood provides a good approximation of the exact edit distance for graphs with a large number of different labels and a high density. Unfortunately, this heuristic works poorly on unlabeled graphs or graphs with a poor diversity of neighborhoods. In this work we propose to extend this heuristic by considering a mapping of bags of walks centered on each node of both graphs.
---
paper_title: Estimating Graph Edit Distance Using Lower and Upper Bounds of Bipartite Approximations

paper_content:

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.
---
paper_title: Retrieval of Envelope Images Using Graph Matching

paper_content:

A graph matching approach is proposed to retrieve envelope images from a large image database. First, the graph representation of an envelop image is generated based on the image segmentation results, in which each node corresponds to one segmented region. The attributes of nodes and edges in the graph are described by characteristics of the envelope image. Second, a minimum weighted bipartite graph matching method is employed to compute the distance between two graphs. Finally, the whole retrieval system including two principal stages is presented, namely, rough matching and fine matching. The experiments on a database of envelope images captured from real-life mail pieces demonstrate that the proposed method achieves promising results.
---
paper_title: Graph-Based Shape Similarity of Petroglyphs

paper_content:

Petroglyphs can be found on rock panels all over the world. The possibilities of digital photography and more recently various 3D scanning methods opened a new stage for the documentation and analysis of petroglyphs. The existing work on petroglyph shape similarity has largely avoided the questions of articulation, merged petroglyphs and potentially missing parts of petroglyphs. We aim at contributing to close this gap by applying a novel petroglyph shape descriptor based on the skeletal graph. Our contribution is twofold: First, we provide a real-world dataset of petroglyph shapes. Second, we propose a graph-based shape descriptor for petroglyphs. Comprehensive evaluations show, that the combination of the proposed descriptor with existing ones improves the performance in petroglyph shape similarity modeling.
---
paper_title: Hand vein authentication using biometric graph matching

paper_content:

This study proposes an automatic dorsal hand vein verification system using a novel algorithm called biometric graph matching (BGM). The dorsal hand vein image is segmented using the K-means technique and the region of interest is extracted based on the morphological analysis operators and normalised using adaptive histogram equalisation. Veins are extracted using a maximum curvature algorithm. The locations and vascular connections between crossovers, bifurcations and terminations in a hand vein pattern define a hand vein graph. The matching performance of BGM for hand vein graphs is tested with two cost functions and compared with the matching performance of two standard point patterns matching algorithms, iterative closest point (ICP) and modified Hausdorff distance. Experiments are conducted on two public databases captured using far infrared and near infrared (NIR) cameras. BGM's matching performance is competitive with state-of-the-art algorithms on the databases despite using small and concise templates. For both databases, BGM performed at least as well as ICP. For the small sized graphs from the NIR database, BGM significantly outperformed point pattern matching. The size of the common subgraph of a pair of graphs is the most significant discriminating measure between genuine and imposter comparisons.
---
paper_title: Retina features based on vessel graph substructures

paper_content:

We represent the retina vessel pattern as a spatial relational graph, and match features using error-correcting graph matching. We study the distinctiveness of the nodes (branching and crossing points) compared with that of the edges and other substructures (nodes of degree k, paths of length k). On a training set from the VARIA database, we show that as well as nodes, three other types of graph sub-structure completely or almost completely separate genuine from imposter comparisons. We show that combining nodes and edges can improve the separation distance. We identify two retina graph statistics, the edge-to-node ratio and the variance of the degree distribution, that have low correlation with node match score.
---
paper_title: Retina Verification System Based on Biometric Graph Matching

paper_content:

This paper presents an automatic retina verification framework based on the biometric graph matching (BGM) algorithm. The retinal vasculature is extracted using a family of matched filters in the frequency domain and morphological operators. Then, retinal templates are defined as formal spatial graphs derived from the retinal vasculature. The BGM algorithm, a noisy graph matching algorithm, robust to translation, non-linear distortion, and small rotations, is used to compare retinal templates. The BGM algorithm uses graph topology to define three distance measures between a pair of graphs, two of which are new. A support vector machine (SVM) classifier is used to distinguish between genuine and imposter comparisons. Using single as well as multiple graph measures, the classifier achieves complete separation on a training set of images from the VARIA database (60% of the data), equaling the state-of-the-art for retina verification. Because the available data set is small, kernel density estimation (KDE) of the genuine and imposter score distributions of the training set are used to measure performance of the BGM algorithm. In the one dimensional case, the KDE model is validated with the testing set. A 0 EER on testing shows that the KDE model is a good fit for the empirical distribution. For the multiple graph measures, a novel combination of the SVM boundary and the KDE model is used to obtain a fair comparison with the KDE model for the single measure. A clear benefit in using multiple graph measures over a single measure to distinguish genuine and imposter comparisons is demonstrated by a drop in theoretical error of between 60% and more than two orders of magnitude.
---
paper_title: Graph-based fingerprint classification using orientation field in core area

paper_content:

In this paper, we present a graph-based fingerprint classification algorithm that deals with ones collected from touch scanners. A relational graph, which reflects distribution of ridge directions in an orientation field, is constructed with additional emphasis on the distribution of the ridges inside the core area that is defined to minimize external influences. For classification, a general edit distance scheme is employed to measure the similarity between the constructed graph and pre-trained graph models. Experimental results using a database in FVC2004 show that the proposed algorithm has higher classification accuracy than other structural approaches.
---
paper_title: Symbolic Learning vs. Graph Kernels: An Experimental Comparison in a Chemical Application

paper_content:

In this paper we present a quantitative comparison between two approaches, Graph Kernels and Symbolic Learning, within a classification scheme. The experimental case-study is the predictive toxicology evaluation, that is the inference of the toxic characteristics of chemical compounds from their structure. The results demonstrate that both approaches are comparable in terms of accuracy, but present pros and cons that are discussed in the last part of the paper.
---
paper_title: The Palm Vein Graph for Biometric Authentication

paper_content:

We introduce the Palm Vein Graph, a spatial graph representation of the palm vasculature, for use as biometric identifiers. The palm vein image captured from an infra red camera undergoes several image processing steps to be represented as a graph. After image enhancement and binarisation, the palm vein features are extracted from the skeleton using a novel two stage spur removal technique. The location of the features and the connections between them are used to define a Palm Vein Graph. Palm vein graphs are compared using the Biometric Graph Matching (BGM) Algorithm. We propose a graph registration algorithm that incorporates the length of the edges between graph vertices to improve the registration process. We introduce a technique called Graph Trimming that shrinks the compared graphs to achieve faster graph matching and improved performance. We introduce 10 graph topology-based measures for comparing palm vein graphs. Experiments are conducted on a public palm vein database for full and trimmed graphs. For the full graphs, one of the introduced measures, an edge-based similarity, gives a definite improvement in matching accuracies over other published results on the same database. Trimming graphs improves matching performance markedly, especially when the compared graphs had only a small common overlap area due to displacement. For the full graphs, when the edge-based measure was combined with one of three other topological features, we demonstrate an improvement in matching accuracy.
---
paper_title: A Hybrid Classification Model for Digital Pathology Using Structural and Statistical Pattern Recognition

paper_content:

Cancer causes deviations in the distribution of cells, leading to changes in biological structures that they form. Correct localization and characterization of these structures are crucial for accurate cancer diagnosis and grading. In this paper, we introduce an effective hybrid model that employs both structural and statistical pattern recognition techniques to locate and characterize the biological structures in a tissue image for tissue quantification. To this end, this hybrid model defines an attributed graph for a tissue image and a set of query graphs as a reference to the normal biological structure. It then locates key regions that are most similar to a normal biological structure by searching the query graphs over the entire tissue graph. Unlike conventional approaches, this hybrid model quantifies the located key regions with two different types of features extracted using structural and statistical techniques. The first type includes embedding of graph edit distances to the query graphs whereas the second one comprises textural features of the key regions. Working with colon tissue images, our experiments demonstrate that the proposed hybrid model leads to higher classification accuracies, compared against the conventional approaches that use only statistical techniques for tissue quantification.
---
paper_title: A Fast Matching Algorithm for Graph-Based Handwriting Recognition.

paper_content:

The recognition of unconstrained handwriting images is usually based on vectorial representation and statistical classification. Despite their high representational power, graphs are rarely used in this field due to a lack of efficient graph-based recognition methods. Recently, graph similarity features have been proposed to bridge the gap between structural representation and statistical classification by means of vector space embedding. This approach has shown a high performance in terms of accuracy but had shortcomings in terms of computational speed. The time complexity of the Hungarian algorithm that is used to approximate the edit distance between two handwriting graphs is demanding for a real-world scenario. In this paper, we propose a faster graph matching algorithm which is derived from the Hausdorff distance. On the historical Parzival database it is demonstrated that the proposed method achieves a speedup factor of 12.9 without significant loss in recognition accuracy.
---
paper_title: A Novel Graph Database for Handwritten Word Images

paper_content:

Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR). S+SSPR 2016: Structural, Syntactic, and Statistical Pattern Recognition pp. 553-563.
---
paper_title: Graph-Based Keyword Spotting in Historical Handwritten Documents

paper_content:

The amount of handwritten documents that is digitally available is rapidly increasing. However, we observe a certain lack of accessibility to these documents especially with respect to searching and browsing. This paper aims at closing this gap by means of a novel method for keyword spotting in ancient handwritten documents. The proposed system relies on a keypoint-based graph representation for individual words. Keypoints are characteristic points in a word image that are represented by nodes, while edges are employed to represent strokes between two keypoints. The basic task of keyword spotting is then conducted by a recent approximation algorithm for graph edit distance. The novel framework for graph-based keyword spotting is tested on the George Washington dataset on which a state-of-the-art reference system is clearly outperformed.
---
paper_title: Graph-based Natural Language Processing: Graph edit distance applied to the task of detecting plagiarism

paper_content:

The focus of this thesis is the exploration of graph-based similarity, in the context of natural language processing. The work is motivated by a need for richer representations of text. A graph edit distance algorithm was implemented, that calculates the difference between graphs. Sentences were represented by means of dependency graphs, which consist of words connected by dependencies. A dependency graph captures the syntactic structure of a sentence. The graph-based similarity approach was applied to the problem of detecting plagiarism, and was compared against state of the art systems. The key advantages of graph-based textual representations are mainly word order indifference and the ability to capture similarity between words, based on the sentence structure. The approach was compared against contributions made to the PAN plagiarism detection challenge at the CLEF 2011 conference, and would have achieved a 5th place out of 10 contestants. The evaluation results suggest that the approach can be applicable to the task of detecting plagiarism, but require some fine tuning on input parameters. The evaluation results demonstrated that dependency graphs are best represented by directed edges. The graph edit distance algorithm scored best with a combination of node and edge label matching. Different edit weights were applied, which increased performance. Keywords: Graph Edit Distance, Natural Language Processing, Dependency Graphs, Plagiarism Detection
---
paper_title: Visual summaries for graph collections

paper_content:

Graphs can be used to represent a variety of information, from molecular structures to biological pathways to computational workflows. With a growing volume of data represented as graphs, the problem of understanding and analyzing the variations in a collection of graphs is of increasing importance. We present an algorithm to compute a single summary graph that efficiently encodes an entire collection of graphs by finding and merging similar nodes and edges. Instead of only merging nodes and edges that are exactly the same, we use domain-specific comparison functions to collapse similar nodes and edges which allows us to generate more compact representations of the collection. In addition, we have developed methods that allow users to interactively control the display of these summary graphs. These interactions include the ability to highlight individual graphs in the summary, control the succinctness of the summary, and explicitly define when specific nodes should or should not be merged. We show that our approach to generating and interacting with graph summaries leads to a better understanding of a graph collection by allowing users to more easily identify common substructures and key differences between graphs.
---
paper_title: A Coarse-to-Fine Word Spotting Approach for Historical Handwritten Documents Based on Graph Embedding and Graph Edit Distance

paper_content:

Effective information retrieval on handwritten document images has always been a challenging task, especially historical ones. In the paper, we propose a coarse-to-fine handwritten word spotting approach based on graph representation. The presented model comprises both the topological and morphological signatures of the handwriting. Skeleton-based graphs with the Shape Context labelled vertexes are established for connected components. Each word image is represented as a sequence of graphs. Aiming at developing a practical and efficient word spotting approach for large-scale historical handwritten documents, a fast and coarse comparison is first applied to prune the regions that are not similar to the query based on the graph embedding methodology. Afterwards, the query and regions of interest are compared by graph edit distance based on the Dynamic Time Warping alignment. The proposed approach is evaluated on a public dataset containing 50 pages of historical marriage license records. The results show that the proposed approach achieves a compromise between efficiency and accuracy.
---
paper_title: Impact of Keypoint Detection on Graph-Based Characterization of Blood Vessels in Colonoscopy Videos

paper_content:

We explore the potential of the use of blood vessels as anatomical landmarks for developing image registration methods in colonoscopy images. An unequivocal representation of blood vessels could be used to guide follow-up methods to track lesions over different interventions. We propose a graph-based representation to characterize network structures, such as blood vessels, based on the use of intersections and endpoints. We present a study consisting of the assessment of the minimal performance a keypoint detector should achieve so that the structure can still be recognized. Experimental results prove that, even by achieving a loss of \(25\,\%\) of the keypoints, the descriptive power of the associated graphs to the vessel pattern is still high enough to recognize blood vessels.
---
paper_title: A Machine Learning Approach to SPARQL Query Performance Prediction

paper_content:

In this paper we address the problem of predicting SPARQL query performance. We use machine learning techniques to learn SPARQL query performance from previously executed queries. Traditional approaches for estimating SPARQL query cost are based on statistics about the underlying data. However, in many use-cases involving querying Linked Data, statistics about the underlying data are often missing. Our approach does not require any statistics about the underlying RDF data, which makes it ideal for the Linked Data scenario. We show how to model SPARQL queries as feature vectors, and use k-nearest neighbors regression and Support Vector Machine with the nu-SVR kernel to accurately predict SPARQL query execution time.
---
paper_title: A Local Adaptation of the Histogram Radon Transform Descriptor: An Application to a Shoe Print Dataset

paper_content:

In this paper we propose a shape recognition approach applied to a dataset composed of 512 shoeprints where shapes are strongly occluded. We provide a local adaptation of the HRT (Histogram Radon Transform) descriptor. A shoeprint is decomposed into its connect components and describes locally by the local HRT. Then, following this description, we find the best local matching between the connected components and the similarity between two images is defined as mean of local similarity measures.
---
paper_title: A graph matching based key point correspondence method for lunar surface images

paper_content:

Key point correspondence plays an important role in lunar surface image processing. Since lunar surface images often contain obvious illumination changes, noisy points and repetitive patterns, traditional appearance based algorithms may fail when local appearance descriptors become less distinctive. In this paper, we introduce a graph matching based algorithm to tackle this problem. First, by incorporating structural information, key point sets in lunar surface images are represented by graphs. Then key point correspondence is formulated as a specific graph matching problem which aims to find a specified number of best assignments, and effectively approximately solved. Finally, an outlier assignment elimination method is proposed based on the affine invariance assumption. Simulations on both benchmark datasets and lunar surface images witness the effectiveness of the proposed method.
---
paper_title: Graph-based matching of composite OWL-S services

paper_content:

Existing techniques for Web service discovery focus mainly on matching functional parameters of atomic services, such as inputs and outputs. However, one of the main advantages of Web services is that they are often composed into more complex processes to achieve a given goal. Applying such techniques in these cases, ignores the workflow structure of the composite process, and therefore may produce matches that are not very accurate. To overcome this limitation, we propose in this paper a graph-based method for matching composite services, that are semantically described as OWL-S processes. We propose a graph representation of composite OWL-S processes and we introduce a matching algorithm that performs comparisons not only at the level of individual components but also at the structural level, taking into consideration the control flow among the atomic components. We also report our preliminary results of our experimental evaluation.
---
paper_title: BinSlayer: accurate comparison of binary executables

paper_content:

As the volume of malware inexorably rises, comparison of binary code is of increasing importance to security analysts as a method of automatically classifying new malware samples; purportedly new examples of malware are frequently a simple evolution of existing code, whose differences stem only from a need to avoid detection. This paper presents a polynomial algorithm for calculating the differences between two binaries, obtained by fusing the well-known BinDiff algorithm with the Hungarian algorithm for bi-partite graph matching. This significantly improves the matching accuracy. Additionally a meaningful metric of similarity is calculated, based on graph edit distance, from which an informed comparison of the binaries can be made. The accuracy of this method over the standard approach is demonstrated.
---
paper_title: Malware detection based on hybrid signature behavior application programming interface call graph

paper_content:

Problem statement: A malware is a program that has malicious intent. Nowadays, malware ::: authors apply several sophisticated techniques such as packing and obfuscation to avoid malware ::: detection. That makes zero-day attacks and false positives the most challenging problems in the ::: malware detection field. Approach: In this study, the static and dynamic analysis techniques that are ::: used in malware detection are surveyed. Static analysis techniques, dynamic analysis techniques and ::: their combination including Signature-Based and Behaviour-Based techniques are discussed. Results: In addition, a new malware detection framework is proposed. Conclusion: The proposed framework ::: combines Signature-Based with Behaviour-Based using API graph system. The goal of the proposed ::: framework is to improve accuracy and scan process time for malware detection.
---
paper_title: A Novel Learning-Free Word Spotting Approach Based on Graph Representation

paper_content:

Effective information retrieval on handwritten documentimages has always been a challenging task. In this paper, we propose a novel handwritten word spotting approach based on graph representation. The presented model comprises both topological and morphological signatures of handwriting. Skeleton-based graphs with the Shape Context labelled vertexes are established for connected components. Each word image is represented as a sequence of graphs. In order to be robust to the handwriting variations, an exhaustive merging process based on DTW alignment result is introduced in the similarity measure between word images. With respect to the computation complexity, an approximate graph edit distance approach using bipartite matching is employed for graph matching. The experiments on the George Washington dataset and the marriage records from the Barcelona Cathedral dataset demonstrate that the proposed approach outperforms the state-of-the-art structural methods.
---
paper_title: Efficient retrieval of 3D building models using embeddings of attributed subgraphs

paper_content:

We present a novel method for retrieval and classification of 3D building models that is tailored to the specific requirements of architects. In contrast to common approaches our algorithm relies on the interior spatial arrangement of rooms instead of exterior geometric shape. We first represent the internal topological building structure by a Room Connectivity Graph (RCG). To enable fast and efficient retrieval and classification with RCGs, we transform the structured graph representation into a vector-based one by introducing a new concept of subgraph embeddings. We provide comprehensive experiments showing that the introduced subgraph embeddings yield superior performance compared to state-of-the-art graph retrieval approaches.
---
paper_title: Improved call graph comparison using simulated annealing

paper_content:

The amount of suspicious binary executables submitted to Anti-Virus (AV) companies are in the order of tens of thousands per day. Current hash-based signature methods are easy to deceive and are inefficient for identifying known malware that have undergone minor changes. Examining malware executables using their call graphs view is a suitable approach for overcoming the weaknesses of hash-based signatures. Unfortunately, many operations on graphs are of high computational complexity. One of these is the Graph Edit Distance (GED) between pairs of graphs, which seems a natural choice for static comparison of malware. We demonstrate how Simulated Annealing can be used to approximate the graph edit distance of call graphs, while outperforming previous approaches both in execution time and solution quality. Additionally, we experiment with opcode mnemonic vectors to reduce the problem size and examine how Simulated Annealing is affected.
---
paper_title: Semantics-Aware Android Malware Classification Using Weighted Contextual API Dependency Graphs

paper_content:

The drastic increase of Android malware has led to a strong interest in developing methods to automate the malware analysis process. Existing automated Android malware detection and classification methods fall into two general categories: 1) signature-based and 2) machine learning-based. Signature-based approaches can be easily evaded by bytecode-level transformation attacks. Prior learning-based works extract features from application syntax, rather than program semantics, and are also subject to evasion. In this paper, we propose a novel semantic-based approach that classifies Android malware via dependency graphs. To battle transformation attacks, we extract a weighted contextual API dependency graph as program semantics to construct feature sets. To fight against malware variants and zero-day malware, we introduce graph similarity metrics to uncover homogeneous application behaviors while tolerating minor implementation differences. We implement a prototype system, DroidSIFT, in 23 thousand lines of Java code. We evaluate our system using 2200 malware samples and 13500 benign samples. Experiments show that our signature detection can correctly label 93\% of malware instances; our anomaly detector is capable of detecting zero-day malware with a low false negative rate (2\%) and an acceptable false positive rate (5.15\%) for a vetting purpose.
---
paper_title: NAVIDOMASS: Structural-based Approaches Towards Handling Historical Documents

paper_content:

In the context of the NAVIDOMASS project, the problematic of this paper concerns the clustering of historical document images. We propose a structural-based framework to handle the ancient ornamental letters data-sets. The contribution, firstly, consists of examining the structural (i.e. graph) representation of the ornamental letters, secondly, the graph matching problem is applied to the resulted graph-based representations. In addition, a comparison between the structural (graphs) and statistical (generic Fourier descriptor) techniques is drawn.
---
paper_title: A Graph-based approach for Kite recognition

paper_content:

We propose a complete graph-based process for Kite recognition.We propose a geometric hierarchical graph matching solution to the problem of geometric graph matching.We also propose a benchmark of Kite graphs from real images.We experimentally evaluate our approach over both real and synthetic data sets. Display Omitted Kites are huge archaeological structures of stone visible from satellite images. Because of their important number and their wide geographical distribution, automatic recognition of these structures on images is an important step towards understanding these enigmatic remnants. This paper presents a complete identification tool relying on a graph representation of the Kites. As Kites are naturally represented by graphs, graph matching methods are thus the main building blocks in the Kite identification process. However, Kite graphs are disconnected geometric graphs for which traditional graph matching methods are useless. To address this issue, we propose a graph similarity measure adapted for Kite graphs. The proposed approach combines graph invariants with a geometric graph edit distance computation leading to an efficient Kite identification process. We analyze the time complexity of the proposed algorithms and conduct extensive experiments both on real and synthetic Kite graph data sets to attest the effectiveness of the approach. We also perform a set of experimentations on other data sets in order to show that the proposed approach is extensible and quite general.
---
paper_title: Two New Graph Kernels and Applications to Chemoinformatics

paper_content:

Chemoinformatics is a well established research field concerned with the discovery of molecule's properties through informational techniques. Computer science's research fields mainly concerned by the chemoinformatics field are machine learning and graph theory. From this point of view, graph kernels provide a nice framework combining machine learning techniques with graph theory. Such kernels prove their efficiency on several chemoinformatics problems. This paper presents two new graph kernels applied to regression and classification problems within the chemoinformatics field. The first kernel is based on the notion of edit distance while the second is based on sub trees enumeration. Several experiments show the complementary of both approaches.
---
paper_title: Supporting sketch-based retrieval from a library of reusable behaviours

paper_content:

Building the behaviour for non-player characters in a game is a complex collaborative task among AI designers and programmers. In this paper we present a visual authoring tool for game designers that supports behaviour reuse. We describe a visual editor, capable of storing, indexing, retrieving and reusing behaviours previously designed by AI programmers. One of the most notable features of our editor is its capability for sketch-based retrieval: searching in a repository for behaviours that are similar to the one the user is drawing, and making suggestions about how to complete it. As this process relies on graph behaviour comparison, in this paper, we describe different algorithms for graph comparison, and demonstrate, through empirical evaluation in a particular test domain, that we can provide structure-based similarity for graphs that preserves behaviour similarity and can be computed at reasonable cost.
---
paper_title: Graph Based Keyword Spotting in Medieval Slavic Documents – A Project Outline

paper_content:

The objective of the planned project is to adapt a recent graph matching framework developed by the applicant to the problem of keyword spotting. The overall question to be answered is whether or not graph based representation and especially graph matching techniques can be beneficially employed for keyword spotting. For testing this novel keyword spotting framework, the Miroslav Gospels will be used. Miroslav Gospels is a 362-page illuminated manuscript Gospel Book on parchment with very rich decorations, which was inscribed on UNESCO’s Memory of the World Register in recognition of its historical value. It is one of the oldest surviving documents written in Old Church Slavonic. We plan to make the extracted word graphs from the Miroslav Gospels publicly available for further developments in graph based keyword spotting.
---
paper_title: On-line Signature Verification Using Segment-to-Segment Graph Matching

paper_content:

This paper proposes a novel approach of on-line signature verification. Firstly, on-line signatures are partitioned into a series of segments, which are then represented by graphs. Four segmentation methods are taken into account. Secondly, graph matching techniques are adopted to compute edit distance between corresponding graphs, which measures the similarity of them. Finally, having been able to compare two signatures, limited genuine signatures are used to train user dependent classifiers for each user. Experiments are conducted to validate the effectiveness of the proposed method and promising results are achieved.
---
paper_title: Unsupervised word spotting using a graph representation based on invariants

paper_content:

We are currently working on the concept of an interactive word retrieval system for ancient document collection navigation, based on query composition for non-expert users. We have introduced a new notion: invariants, which are writing pieces automatically extracted from the old document collection. The invariants can be used in query making process in where the user selects and composes appropriate invariants to make the query. The invariants can be also used as descriptor to characterize word images. We introduced our unsupervised method for extracting invariants in our earlier paper. In this paper, we present a new structural word spotting system using a graph representation based on invariants as a descriptor. Through experiments, we conclude that our proposed system can adapt to different types of homogenous alphabetic languages documents (regardless of language/script, antiquity, handwritten or printed).
---
paper_title: Knowledge-based graph document modeling

paper_content:

We propose a graph-based semantic model for representing document content. Our method relies on the use of a semantic network, namely the DBpedia knowledge base, for acquiring fine-grained information about entities and their semantic relations, thus resulting in a knowledge-rich document model. We demonstrate the benefits of these semantic representations in two tasks: entity ranking and computing document semantic similarity. To this end, we couple DBpedia's structure with an information-theoretic measure of concept association, based on its explicit semantic relations, and compute semantic similarity using a Graph Edit Distance based measure, which finds the optimal matching between the documents' entities using the Hungarian method. Experimental results show that our general model outperforms baselines built on top of traditional methods, and achieves a performance close to that of highly specialized methods that have been tuned to these specific tasks.
---
paper_title: Handwritten word spotting by inexact matching of grapheme graphs

paper_content:

This paper presents a graph-based word spotting for handwritten documents. Contrary to most word spotting techniques, which use statistical representations, we propose a structural representation suitable to be robust to the inherent deformations of handwriting. Attributed graphs are constructed using a part-based approach. Graphemes extracted from shape convexities are used as stable units of handwriting, and are associated to graph nodes. Then, spatial relations between them determine graph edges. Spotting is defined in terms of an error-tolerant graph matching using bipartite-graph matching algorithm. To make the method usable in large datasets, a graph indexing approach that makes use of binary embeddings is used as preprocessing. Historical documents are used as experimental framework. The approach is comparable to statistical ones in terms of time and memory requirements, especially when dealing with large document collections.
---
paper_title: Retrieval of Envelope Images Using Graph Matching

paper_content:

A graph matching approach is proposed to retrieve envelope images from a large image database. First, the graph representation of an envelop image is generated based on the image segmentation results, in which each node corresponds to one segmented region. The attributes of nodes and edges in the graph are described by characteristics of the envelope image. Second, a minimum weighted bipartite graph matching method is employed to compute the distance between two graphs. Finally, the whole retrieval system including two principal stages is presented, namely, rough matching and fine matching. The experiments on a database of envelope images captured from real-life mail pieces demonstrate that the proposed method achieves promising results.
---
paper_title: Graph-Based Shape Similarity of Petroglyphs

paper_content:

Petroglyphs can be found on rock panels all over the world. The possibilities of digital photography and more recently various 3D scanning methods opened a new stage for the documentation and analysis of petroglyphs. The existing work on petroglyph shape similarity has largely avoided the questions of articulation, merged petroglyphs and potentially missing parts of petroglyphs. We aim at contributing to close this gap by applying a novel petroglyph shape descriptor based on the skeletal graph. Our contribution is twofold: First, we provide a real-world dataset of petroglyph shapes. Second, we propose a graph-based shape descriptor for petroglyphs. Comprehensive evaluations show, that the combination of the proposed descriptor with existing ones improves the performance in petroglyph shape similarity modeling.
---
paper_title: A Local Adaptation of the Histogram Radon Transform Descriptor: An Application to a Shoe Print Dataset

paper_content:

In this paper we propose a shape recognition approach applied to a dataset composed of 512 shoeprints where shapes are strongly occluded. We provide a local adaptation of the HRT (Histogram Radon Transform) descriptor. A shoeprint is decomposed into its connect components and describes locally by the local HRT. Then, following this description, we find the best local matching between the connected components and the similarity between two images is defined as mean of local similarity measures.
---
paper_title: A graph matching based key point correspondence method for lunar surface images

paper_content:

Key point correspondence plays an important role in lunar surface image processing. Since lunar surface images often contain obvious illumination changes, noisy points and repetitive patterns, traditional appearance based algorithms may fail when local appearance descriptors become less distinctive. In this paper, we introduce a graph matching based algorithm to tackle this problem. First, by incorporating structural information, key point sets in lunar surface images are represented by graphs. Then key point correspondence is formulated as a specific graph matching problem which aims to find a specified number of best assignments, and effectively approximately solved. Finally, an outlier assignment elimination method is proposed based on the affine invariance assumption. Simulations on both benchmark datasets and lunar surface images witness the effectiveness of the proposed method.
---
paper_title: Efficient retrieval of 3D building models using embeddings of attributed subgraphs

paper_content:

We present a novel method for retrieval and classification of 3D building models that is tailored to the specific requirements of architects. In contrast to common approaches our algorithm relies on the interior spatial arrangement of rooms instead of exterior geometric shape. We first represent the internal topological building structure by a Room Connectivity Graph (RCG). To enable fast and efficient retrieval and classification with RCGs, we transform the structured graph representation into a vector-based one by introducing a new concept of subgraph embeddings. We provide comprehensive experiments showing that the introduced subgraph embeddings yield superior performance compared to state-of-the-art graph retrieval approaches.
---
paper_title: A Graph-based approach for Kite recognition

paper_content:

We propose a complete graph-based process for Kite recognition.We propose a geometric hierarchical graph matching solution to the problem of geometric graph matching.We also propose a benchmark of Kite graphs from real images.We experimentally evaluate our approach over both real and synthetic data sets. Display Omitted Kites are huge archaeological structures of stone visible from satellite images. Because of their important number and their wide geographical distribution, automatic recognition of these structures on images is an important step towards understanding these enigmatic remnants. This paper presents a complete identification tool relying on a graph representation of the Kites. As Kites are naturally represented by graphs, graph matching methods are thus the main building blocks in the Kite identification process. However, Kite graphs are disconnected geometric graphs for which traditional graph matching methods are useless. To address this issue, we propose a graph similarity measure adapted for Kite graphs. The proposed approach combines graph invariants with a geometric graph edit distance computation leading to an efficient Kite identification process. We analyze the time complexity of the proposed algorithms and conduct extensive experiments both on real and synthetic Kite graph data sets to attest the effectiveness of the approach. We also perform a set of experimentations on other data sets in order to show that the proposed approach is extensible and quite general.
---
paper_title: A Fast Matching Algorithm for Graph-Based Handwriting Recognition.

paper_content:

The recognition of unconstrained handwriting images is usually based on vectorial representation and statistical classification. Despite their high representational power, graphs are rarely used in this field due to a lack of efficient graph-based recognition methods. Recently, graph similarity features have been proposed to bridge the gap between structural representation and statistical classification by means of vector space embedding. This approach has shown a high performance in terms of accuracy but had shortcomings in terms of computational speed. The time complexity of the Hungarian algorithm that is used to approximate the edit distance between two handwriting graphs is demanding for a real-world scenario. In this paper, we propose a faster graph matching algorithm which is derived from the Hausdorff distance. On the historical Parzival database it is demonstrated that the proposed method achieves a speedup factor of 12.9 without significant loss in recognition accuracy.
---
paper_title: A Novel Graph Database for Handwritten Word Images

paper_content:

Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR). S+SSPR 2016: Structural, Syntactic, and Statistical Pattern Recognition pp. 553-563.
---
paper_title: Graph-Based Keyword Spotting in Historical Handwritten Documents

paper_content:

The amount of handwritten documents that is digitally available is rapidly increasing. However, we observe a certain lack of accessibility to these documents especially with respect to searching and browsing. This paper aims at closing this gap by means of a novel method for keyword spotting in ancient handwritten documents. The proposed system relies on a keypoint-based graph representation for individual words. Keypoints are characteristic points in a word image that are represented by nodes, while edges are employed to represent strokes between two keypoints. The basic task of keyword spotting is then conducted by a recent approximation algorithm for graph edit distance. The novel framework for graph-based keyword spotting is tested on the George Washington dataset on which a state-of-the-art reference system is clearly outperformed.
---
paper_title: A Coarse-to-Fine Word Spotting Approach for Historical Handwritten Documents Based on Graph Embedding and Graph Edit Distance

paper_content:

Effective information retrieval on handwritten document images has always been a challenging task, especially historical ones. In the paper, we propose a coarse-to-fine handwritten word spotting approach based on graph representation. The presented model comprises both the topological and morphological signatures of the handwriting. Skeleton-based graphs with the Shape Context labelled vertexes are established for connected components. Each word image is represented as a sequence of graphs. Aiming at developing a practical and efficient word spotting approach for large-scale historical handwritten documents, a fast and coarse comparison is first applied to prune the regions that are not similar to the query based on the graph embedding methodology. Afterwards, the query and regions of interest are compared by graph edit distance based on the Dynamic Time Warping alignment. The proposed approach is evaluated on a public dataset containing 50 pages of historical marriage license records. The results show that the proposed approach achieves a compromise between efficiency and accuracy.
---
paper_title: A Novel Learning-Free Word Spotting Approach Based on Graph Representation

paper_content:

Effective information retrieval on handwritten documentimages has always been a challenging task. In this paper, we propose a novel handwritten word spotting approach based on graph representation. The presented model comprises both topological and morphological signatures of handwriting. Skeleton-based graphs with the Shape Context labelled vertexes are established for connected components. Each word image is represented as a sequence of graphs. In order to be robust to the handwriting variations, an exhaustive merging process based on DTW alignment result is introduced in the similarity measure between word images. With respect to the computation complexity, an approximate graph edit distance approach using bipartite matching is employed for graph matching. The experiments on the George Washington dataset and the marriage records from the Barcelona Cathedral dataset demonstrate that the proposed approach outperforms the state-of-the-art structural methods.
---
paper_title: NAVIDOMASS: Structural-based Approaches Towards Handling Historical Documents

paper_content:

In the context of the NAVIDOMASS project, the problematic of this paper concerns the clustering of historical document images. We propose a structural-based framework to handle the ancient ornamental letters data-sets. The contribution, firstly, consists of examining the structural (i.e. graph) representation of the ornamental letters, secondly, the graph matching problem is applied to the resulted graph-based representations. In addition, a comparison between the structural (graphs) and statistical (generic Fourier descriptor) techniques is drawn.
---
paper_title: Graph Based Keyword Spotting in Medieval Slavic Documents – A Project Outline

paper_content:

The objective of the planned project is to adapt a recent graph matching framework developed by the applicant to the problem of keyword spotting. The overall question to be answered is whether or not graph based representation and especially graph matching techniques can be beneficially employed for keyword spotting. For testing this novel keyword spotting framework, the Miroslav Gospels will be used. Miroslav Gospels is a 362-page illuminated manuscript Gospel Book on parchment with very rich decorations, which was inscribed on UNESCO’s Memory of the World Register in recognition of its historical value. It is one of the oldest surviving documents written in Old Church Slavonic. We plan to make the extracted word graphs from the Miroslav Gospels publicly available for further developments in graph based keyword spotting.
---
paper_title: Unsupervised word spotting using a graph representation based on invariants

paper_content:

We are currently working on the concept of an interactive word retrieval system for ancient document collection navigation, based on query composition for non-expert users. We have introduced a new notion: invariants, which are writing pieces automatically extracted from the old document collection. The invariants can be used in query making process in where the user selects and composes appropriate invariants to make the query. The invariants can be also used as descriptor to characterize word images. We introduced our unsupervised method for extracting invariants in our earlier paper. In this paper, we present a new structural word spotting system using a graph representation based on invariants as a descriptor. Through experiments, we conclude that our proposed system can adapt to different types of homogenous alphabetic languages documents (regardless of language/script, antiquity, handwritten or printed).
---
paper_title: Handwritten word spotting by inexact matching of grapheme graphs

paper_content:

This paper presents a graph-based word spotting for handwritten documents. Contrary to most word spotting techniques, which use statistical representations, we propose a structural representation suitable to be robust to the inherent deformations of handwriting. Attributed graphs are constructed using a part-based approach. Graphemes extracted from shape convexities are used as stable units of handwriting, and are associated to graph nodes. Then, spatial relations between them determine graph edges. Spotting is defined in terms of an error-tolerant graph matching using bipartite-graph matching algorithm. To make the method usable in large datasets, a graph indexing approach that makes use of binary embeddings is used as preprocessing. Historical documents are used as experimental framework. The approach is comparable to statistical ones in terms of time and memory requirements, especially when dealing with large document collections.
---
paper_title: Hand vein authentication using biometric graph matching

paper_content:

This study proposes an automatic dorsal hand vein verification system using a novel algorithm called biometric graph matching (BGM). The dorsal hand vein image is segmented using the K-means technique and the region of interest is extracted based on the morphological analysis operators and normalised using adaptive histogram equalisation. Veins are extracted using a maximum curvature algorithm. The locations and vascular connections between crossovers, bifurcations and terminations in a hand vein pattern define a hand vein graph. The matching performance of BGM for hand vein graphs is tested with two cost functions and compared with the matching performance of two standard point patterns matching algorithms, iterative closest point (ICP) and modified Hausdorff distance. Experiments are conducted on two public databases captured using far infrared and near infrared (NIR) cameras. BGM's matching performance is competitive with state-of-the-art algorithms on the databases despite using small and concise templates. For both databases, BGM performed at least as well as ICP. For the small sized graphs from the NIR database, BGM significantly outperformed point pattern matching. The size of the common subgraph of a pair of graphs is the most significant discriminating measure between genuine and imposter comparisons.
---
paper_title: Retina features based on vessel graph substructures

paper_content:

We represent the retina vessel pattern as a spatial relational graph, and match features using error-correcting graph matching. We study the distinctiveness of the nodes (branching and crossing points) compared with that of the edges and other substructures (nodes of degree k, paths of length k). On a training set from the VARIA database, we show that as well as nodes, three other types of graph sub-structure completely or almost completely separate genuine from imposter comparisons. We show that combining nodes and edges can improve the separation distance. We identify two retina graph statistics, the edge-to-node ratio and the variance of the degree distribution, that have low correlation with node match score.
---
paper_title: Retina Verification System Based on Biometric Graph Matching

paper_content:

This paper presents an automatic retina verification framework based on the biometric graph matching (BGM) algorithm. The retinal vasculature is extracted using a family of matched filters in the frequency domain and morphological operators. Then, retinal templates are defined as formal spatial graphs derived from the retinal vasculature. The BGM algorithm, a noisy graph matching algorithm, robust to translation, non-linear distortion, and small rotations, is used to compare retinal templates. The BGM algorithm uses graph topology to define three distance measures between a pair of graphs, two of which are new. A support vector machine (SVM) classifier is used to distinguish between genuine and imposter comparisons. Using single as well as multiple graph measures, the classifier achieves complete separation on a training set of images from the VARIA database (60% of the data), equaling the state-of-the-art for retina verification. Because the available data set is small, kernel density estimation (KDE) of the genuine and imposter score distributions of the training set are used to measure performance of the BGM algorithm. In the one dimensional case, the KDE model is validated with the testing set. A 0 EER on testing shows that the KDE model is a good fit for the empirical distribution. For the multiple graph measures, a novel combination of the SVM boundary and the KDE model is used to obtain a fair comparison with the KDE model for the single measure. A clear benefit in using multiple graph measures over a single measure to distinguish genuine and imposter comparisons is demonstrated by a drop in theoretical error of between 60% and more than two orders of magnitude.
---
paper_title: Graph-based fingerprint classification using orientation field in core area

paper_content:

In this paper, we present a graph-based fingerprint classification algorithm that deals with ones collected from touch scanners. A relational graph, which reflects distribution of ridge directions in an orientation field, is constructed with additional emphasis on the distribution of the ridges inside the core area that is defined to minimize external influences. For classification, a general edit distance scheme is employed to measure the similarity between the constructed graph and pre-trained graph models. Experimental results using a database in FVC2004 show that the proposed algorithm has higher classification accuracy than other structural approaches.
---
paper_title: The Palm Vein Graph for Biometric Authentication

paper_content:

We introduce the Palm Vein Graph, a spatial graph representation of the palm vasculature, for use as biometric identifiers. The palm vein image captured from an infra red camera undergoes several image processing steps to be represented as a graph. After image enhancement and binarisation, the palm vein features are extracted from the skeleton using a novel two stage spur removal technique. The location of the features and the connections between them are used to define a Palm Vein Graph. Palm vein graphs are compared using the Biometric Graph Matching (BGM) Algorithm. We propose a graph registration algorithm that incorporates the length of the edges between graph vertices to improve the registration process. We introduce a technique called Graph Trimming that shrinks the compared graphs to achieve faster graph matching and improved performance. We introduce 10 graph topology-based measures for comparing palm vein graphs. Experiments are conducted on a public palm vein database for full and trimmed graphs. For the full graphs, one of the introduced measures, an edge-based similarity, gives a definite improvement in matching accuracies over other published results on the same database. Trimming graphs improves matching performance markedly, especially when the compared graphs had only a small common overlap area due to displacement. For the full graphs, when the edge-based measure was combined with one of three other topological features, we demonstrate an improvement in matching accuracy.
---
paper_title: NAVIDOMASS: Structural-based Approaches Towards Handling Historical Documents

paper_content:

In the context of the NAVIDOMASS project, the problematic of this paper concerns the clustering of historical document images. We propose a structural-based framework to handle the ancient ornamental letters data-sets. The contribution, firstly, consists of examining the structural (i.e. graph) representation of the ornamental letters, secondly, the graph matching problem is applied to the resulted graph-based representations. In addition, a comparison between the structural (graphs) and statistical (generic Fourier descriptor) techniques is drawn.
---
paper_title: On-line Signature Verification Using Segment-to-Segment Graph Matching

paper_content:

This paper proposes a novel approach of on-line signature verification. Firstly, on-line signatures are partitioned into a series of segments, which are then represented by graphs. Four segmentation methods are taken into account. Secondly, graph matching techniques are adopted to compute edit distance between corresponding graphs, which measures the similarity of them. Finally, having been able to compare two signatures, limited genuine signatures are used to train user dependent classifiers for each user. Experiments are conducted to validate the effectiveness of the proposed method and promising results are achieved.
---
paper_title: Symbolic Learning vs. Graph Kernels: An Experimental Comparison in a Chemical Application

paper_content:

In this paper we present a quantitative comparison between two approaches, Graph Kernels and Symbolic Learning, within a classification scheme. The experimental case-study is the predictive toxicology evaluation, that is the inference of the toxic characteristics of chemical compounds from their structure. The results demonstrate that both approaches are comparable in terms of accuracy, but present pros and cons that are discussed in the last part of the paper.
---
paper_title: A Hybrid Classification Model for Digital Pathology Using Structural and Statistical Pattern Recognition

paper_content:

Cancer causes deviations in the distribution of cells, leading to changes in biological structures that they form. Correct localization and characterization of these structures are crucial for accurate cancer diagnosis and grading. In this paper, we introduce an effective hybrid model that employs both structural and statistical pattern recognition techniques to locate and characterize the biological structures in a tissue image for tissue quantification. To this end, this hybrid model defines an attributed graph for a tissue image and a set of query graphs as a reference to the normal biological structure. It then locates key regions that are most similar to a normal biological structure by searching the query graphs over the entire tissue graph. Unlike conventional approaches, this hybrid model quantifies the located key regions with two different types of features extracted using structural and statistical techniques. The first type includes embedding of graph edit distances to the query graphs whereas the second one comprises textural features of the key regions. Working with colon tissue images, our experiments demonstrate that the proposed hybrid model leads to higher classification accuracies, compared against the conventional approaches that use only statistical techniques for tissue quantification.
---
paper_title: Visual summaries for graph collections

paper_content:

Graphs can be used to represent a variety of information, from molecular structures to biological pathways to computational workflows. With a growing volume of data represented as graphs, the problem of understanding and analyzing the variations in a collection of graphs is of increasing importance. We present an algorithm to compute a single summary graph that efficiently encodes an entire collection of graphs by finding and merging similar nodes and edges. Instead of only merging nodes and edges that are exactly the same, we use domain-specific comparison functions to collapse similar nodes and edges which allows us to generate more compact representations of the collection. In addition, we have developed methods that allow users to interactively control the display of these summary graphs. These interactions include the ability to highlight individual graphs in the summary, control the succinctness of the summary, and explicitly define when specific nodes should or should not be merged. We show that our approach to generating and interacting with graph summaries leads to a better understanding of a graph collection by allowing users to more easily identify common substructures and key differences between graphs.
---
paper_title: Impact of Keypoint Detection on Graph-Based Characterization of Blood Vessels in Colonoscopy Videos

paper_content:

We explore the potential of the use of blood vessels as anatomical landmarks for developing image registration methods in colonoscopy images. An unequivocal representation of blood vessels could be used to guide follow-up methods to track lesions over different interventions. We propose a graph-based representation to characterize network structures, such as blood vessels, based on the use of intersections and endpoints. We present a study consisting of the assessment of the minimal performance a keypoint detector should achieve so that the structure can still be recognized. Experimental results prove that, even by achieving a loss of \(25\,\%\) of the keypoints, the descriptive power of the associated graphs to the vessel pattern is still high enough to recognize blood vessels.
---
paper_title: Two New Graph Kernels and Applications to Chemoinformatics

paper_content:

Chemoinformatics is a well established research field concerned with the discovery of molecule's properties through informational techniques. Computer science's research fields mainly concerned by the chemoinformatics field are machine learning and graph theory. From this point of view, graph kernels provide a nice framework combining machine learning techniques with graph theory. Such kernels prove their efficiency on several chemoinformatics problems. This paper presents two new graph kernels applied to regression and classification problems within the chemoinformatics field. The first kernel is based on the notion of edit distance while the second is based on sub trees enumeration. Several experiments show the complementary of both approaches.
---
paper_title: A Machine Learning Approach to SPARQL Query Performance Prediction

paper_content:

In this paper we address the problem of predicting SPARQL query performance. We use machine learning techniques to learn SPARQL query performance from previously executed queries. Traditional approaches for estimating SPARQL query cost are based on statistics about the underlying data. However, in many use-cases involving querying Linked Data, statistics about the underlying data are often missing. Our approach does not require any statistics about the underlying RDF data, which makes it ideal for the Linked Data scenario. We show how to model SPARQL queries as feature vectors, and use k-nearest neighbors regression and Support Vector Machine with the nu-SVR kernel to accurately predict SPARQL query execution time.
---
paper_title: Graph-based matching of composite OWL-S services

paper_content:

Existing techniques for Web service discovery focus mainly on matching functional parameters of atomic services, such as inputs and outputs. However, one of the main advantages of Web services is that they are often composed into more complex processes to achieve a given goal. Applying such techniques in these cases, ignores the workflow structure of the composite process, and therefore may produce matches that are not very accurate. To overcome this limitation, we propose in this paper a graph-based method for matching composite services, that are semantically described as OWL-S processes. We propose a graph representation of composite OWL-S processes and we introduce a matching algorithm that performs comparisons not only at the level of individual components but also at the structural level, taking into consideration the control flow among the atomic components. We also report our preliminary results of our experimental evaluation.
---
paper_title: Knowledge-based graph document modeling

paper_content:

We propose a graph-based semantic model for representing document content. Our method relies on the use of a semantic network, namely the DBpedia knowledge base, for acquiring fine-grained information about entities and their semantic relations, thus resulting in a knowledge-rich document model. We demonstrate the benefits of these semantic representations in two tasks: entity ranking and computing document semantic similarity. To this end, we couple DBpedia's structure with an information-theoretic measure of concept association, based on its explicit semantic relations, and compute semantic similarity using a Graph Edit Distance based measure, which finds the optimal matching between the documents' entities using the Hungarian method. Experimental results show that our general model outperforms baselines built on top of traditional methods, and achieves a performance close to that of highly specialized methods that have been tuned to these specific tasks.
---
paper_title: BinSlayer: accurate comparison of binary executables

paper_content:

As the volume of malware inexorably rises, comparison of binary code is of increasing importance to security analysts as a method of automatically classifying new malware samples; purportedly new examples of malware are frequently a simple evolution of existing code, whose differences stem only from a need to avoid detection. This paper presents a polynomial algorithm for calculating the differences between two binaries, obtained by fusing the well-known BinDiff algorithm with the Hungarian algorithm for bi-partite graph matching. This significantly improves the matching accuracy. Additionally a meaningful metric of similarity is calculated, based on graph edit distance, from which an informed comparison of the binaries can be made. The accuracy of this method over the standard approach is demonstrated.
---
paper_title: Malware detection based on hybrid signature behavior application programming interface call graph

paper_content:

Problem statement: A malware is a program that has malicious intent. Nowadays, malware ::: authors apply several sophisticated techniques such as packing and obfuscation to avoid malware ::: detection. That makes zero-day attacks and false positives the most challenging problems in the ::: malware detection field. Approach: In this study, the static and dynamic analysis techniques that are ::: used in malware detection are surveyed. Static analysis techniques, dynamic analysis techniques and ::: their combination including Signature-Based and Behaviour-Based techniques are discussed. Results: In addition, a new malware detection framework is proposed. Conclusion: The proposed framework ::: combines Signature-Based with Behaviour-Based using API graph system. The goal of the proposed ::: framework is to improve accuracy and scan process time for malware detection.
---
paper_title: Improved call graph comparison using simulated annealing

paper_content:

The amount of suspicious binary executables submitted to Anti-Virus (AV) companies are in the order of tens of thousands per day. Current hash-based signature methods are easy to deceive and are inefficient for identifying known malware that have undergone minor changes. Examining malware executables using their call graphs view is a suitable approach for overcoming the weaknesses of hash-based signatures. Unfortunately, many operations on graphs are of high computational complexity. One of these is the Graph Edit Distance (GED) between pairs of graphs, which seems a natural choice for static comparison of malware. We demonstrate how Simulated Annealing can be used to approximate the graph edit distance of call graphs, while outperforming previous approaches both in execution time and solution quality. Additionally, we experiment with opcode mnemonic vectors to reduce the problem size and examine how Simulated Annealing is affected.
---
paper_title: Semantics-Aware Android Malware Classification Using Weighted Contextual API Dependency Graphs

paper_content:

The drastic increase of Android malware has led to a strong interest in developing methods to automate the malware analysis process. Existing automated Android malware detection and classification methods fall into two general categories: 1) signature-based and 2) machine learning-based. Signature-based approaches can be easily evaded by bytecode-level transformation attacks. Prior learning-based works extract features from application syntax, rather than program semantics, and are also subject to evasion. In this paper, we propose a novel semantic-based approach that classifies Android malware via dependency graphs. To battle transformation attacks, we extract a weighted contextual API dependency graph as program semantics to construct feature sets. To fight against malware variants and zero-day malware, we introduce graph similarity metrics to uncover homogeneous application behaviors while tolerating minor implementation differences. We implement a prototype system, DroidSIFT, in 23 thousand lines of Java code. We evaluate our system using 2200 malware samples and 13500 benign samples. Experiments show that our signature detection can correctly label 93\% of malware instances; our anomaly detector is capable of detecting zero-day malware with a low false negative rate (2\%) and an acceptable false positive rate (5.15\%) for a vetting purpose.
---
paper_title: Graph-based Natural Language Processing: Graph edit distance applied to the task of detecting plagiarism

paper_content:

The focus of this thesis is the exploration of graph-based similarity, in the context of natural language processing. The work is motivated by a need for richer representations of text. A graph edit distance algorithm was implemented, that calculates the difference between graphs. Sentences were represented by means of dependency graphs, which consist of words connected by dependencies. A dependency graph captures the syntactic structure of a sentence. The graph-based similarity approach was applied to the problem of detecting plagiarism, and was compared against state of the art systems. The key advantages of graph-based textual representations are mainly word order indifference and the ability to capture similarity between words, based on the sentence structure. The approach was compared against contributions made to the PAN plagiarism detection challenge at the CLEF 2011 conference, and would have achieved a 5th place out of 10 contestants. The evaluation results suggest that the approach can be applicable to the task of detecting plagiarism, but require some fine tuning on input parameters. The evaluation results demonstrated that dependency graphs are best represented by directed edges. The graph edit distance algorithm scored best with a combination of node and edge label matching. Different edit weights were applied, which increased performance. Keywords: Graph Edit Distance, Natural Language Processing, Dependency Graphs, Plagiarism Detection
---
paper_title: Supporting sketch-based retrieval from a library of reusable behaviours

paper_content:

Building the behaviour for non-player characters in a game is a complex collaborative task among AI designers and programmers. In this paper we present a visual authoring tool for game designers that supports behaviour reuse. We describe a visual editor, capable of storing, indexing, retrieving and reusing behaviours previously designed by AI programmers. One of the most notable features of our editor is its capability for sketch-based retrieval: searching in a repository for behaviours that are similar to the one the user is drawing, and making suggestions about how to complete it. As this process relies on graph behaviour comparison, in this paper, we describe different algorithms for graph comparison, and demonstrate, through empirical evaluation in a particular test domain, that we can provide structure-based similarity for graphs that preserves behaviour similarity and can be computed at reasonable cost.
---

Title: A Survey on Applications of Bipartite Graph Edit Distance
Section 1: Introduction
Description 1: This section introduces the concept of bipartite graph edit distance and its relevance in various pattern recognition applications, highlighting its computational complexity and the evolution of an efficient approximation algorithm.

Section 2: Applications
Description 2: This section gives an overview of various fields where the bipartite graph edit distance framework has been applied, summarizing the two main categories of applications: methodological extensions of BP and its applications in different domains.

Section 3: Image Analysis
Description 3: This section discusses the application of bipartite graph edit distance in image analysis, detailing specific studies and methodologies used for representing 2D and 3D images as graphs to measure dissimilarities.

Section 4: Handwritten Document Analysis
Description 4: This section reviews the use of bipartite graph edit distance in the analysis of handwritten documents, focusing on techniques for recognizing handwriting, keyword spotting, and clustering of ancient manuscripts.

Section 5: Biometrics
Description 5: This section covers applications of bipartite graph edit distance in biometric systems, including user verification via retinal vessels, palm veins, fingerprint identification, person re-identification in video surveillance, and online signature verification.

Section 6: Bio-and Chemoinformatics
Description 6: This section highlights applications in bioinformatics and chemoinformatics, such as cancer detection in biological tissues, blood vessel analysis, and molecular property prediction using graph-based representations.

Section 7: Knowledge and Process Management
Description 7: This section describes how bipartite graph edit distance is used in knowledge and process management, covering applications in web services, business process retrieval, RDF ontology processing, and SPARQL query feature estimation.

Section 8: Malware Detection
Description 8: This section explores how the bipartite graph edit distance is used in detecting malware through comparisons of call graphs and API dependency graphs in various approaches.

Section 9: Other Applications
Description 9: This section reviews additional unique applications of bipartite graph edit distance, such as story retrieval, character behavior scripting in games, and plagiarism detection in programming and textual documents.

Section 10: Conclusion
Description 10: This section summarizes the survey findings, reviewing around 40 applications of the BP framework across various domains and discussing plans for future work that includes methodological extensions.