Graph matching is the problem of finding a similarity between

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

s.Endika Bengoetxea
"Inexact Graph Matching Using Estimation of Distribution Algorithms"
Ph. D., 2002
Chapter 2:The graph matching problem
(retrieved June 28, 2017) Graphs are commonly used to encode structural information in many fields, including

computer vision Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...

and

pattern recognition Pattern recognition is the automated recognition of patterns and regularities in data. It has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphi ...

, and graph matching is an important tool in these areas. Endika Bengoetxea, Ph.D.
Abstract
/ref> In these areas it is commonly assumed that the comparison is between the ''data graph'' and the ''model graph''. The case of exact graph matching is known as the

graph isomorphism problem The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational compl ...

. The problem of exact matching of a graph to a part of another graph is called

subgraph isomorphism problem In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs ''G'' and ''H'' are given as input, and one must determine whether ''G'' contains a subgraph that is isomorphic to ''H''. Subgraph isomor ...

. Inexact graph matching refers to matching problems when exact matching is impossible, e.g., when the number of vertices in the two graphs are different. In this case it is required to find the best possible match. For example, in

image recognition Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...

applications, the results of

image segmentation In digital image processing and computer vision, image segmentation is the process of partitioning a digital image into multiple image segments, also known as image regions or image objects ( sets of pixels). The goal of segmentation is to simpl ...

image processing An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...

typically produces data graphs with the numbers of vertices much larger than in the model graphs data expected to match against. In the case of

attributed graph In computer science, an attributed graph grammar is a class of graph grammar that associates vertices with a set of attributes and rewrites with functions on attributes. In the algebraic approach to graph grammars, they are usually formulated using ...

s, even if the numbers of vertices and edges are the same, the matching still may be only inexact. Two categories of search methods are the ones based on identification of possible and impossible pairings of vertices between the two graphs and methods that formulate graph matching as an

optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...

Graph edit distance In mathematics and computer science, graph edit distance (GED) is a measure of similarity (or dissimilarity) between two graphs. The concept of graph edit distance was first formalized mathematically by Alberto Sanfeliu and King-Sun Fu in 1983. A ...

is one of

similarity measure In statistics and related fields, a similarity measure or similarity function or similarity metric is a real-valued function that quantifies the similarity between two objects. Although no single definition of a similarity exists, usually such meas ...

s suggested for graph matching.Horst Bunke, Xiaoyi Jang, "Graph Matching and Similarity", in: ''Intelligent Systems and Interfaces'', pp. 281-304 (2000) The class of algorithms is called error-tolerant graph matching.

References

Computational problems in graph theory {{Comp-sci-stub

See also

References