Median graph: A new exact algorithm using a distance based on the maximum common subgraph

Learning Graph Matching Substitution Weights Based on the Ground Truth Node Correspondence

In pattern recognition, it is usual to compare structured objects through attributed graphs in which nodes represent local parts and edges relations between them. Thus, each characteristic in the local parts is represented by different attributes on the nodes or edges. In this framework, the comparison between structured objects is performed through a distance between attributed graphs. If we want to correctly tune the distance and node correspondence between graphs, we need to add some weights on the node and edge attributes to gauge the importance of each local characteristic while defining the distance measure between graphs. In this paper, we present a method to learn the weights of each node and edge attribute such that the distance between the ground truth correspondence between graphs and the automatically obtained correspondence is minimized.

Speeding up Fast Bipartite Graph Matching Through a New Cost Matrix

Bipartite (BP) has been seen to be a fast and accurate suboptimal algorithm to solve the Error-Tolerant Graph Matching problem. Recently, Fast Bipartite (FBP) has been presented that obtains the same distance value and node labelings but in a reduced time. Both algorithms approximate the quadratic problem in a linear problem and they do it through a specific cost matrix. FBP imposes the Edit costs to be defined such as the Edit distance is a distance function. Originally, the Hungarian method was used but it has been seen the Jonker–Volgenant linear solver obtains similar results than the Hungarian method but with an important run time reduction. Nevertheless, this second solver has some convergence problems on some specific cost matrices. The aim of this paper is to define a new cost matrix such that the Jonker–Volgenant solver converges and the matching algorithm obtains the same distance value than the BP algorithm.

GRAPH MATCHING AND LEARNING IN PATTERN RECOGNITION IN THE LAST 10 YEARS

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.