We often query graphs for certain patterns, for example retrieving all patients and their friends. These queries are so called containment queries and find all subgraphs that match certain patterns in a graph. The subgraph pattern matching problem is NP-Complete. Two different subgraph pattern matching semantics are isomorphism and homomorphism.

An isomorphism from a graph $G$ to a graph $H$ is a bijective (one-to-one and onto) mapping $f\colon V(G)\to V(H)$ from the vertices of $G$ to the vertices of $H$ with the property

$$st \in E(G) \Longleftrightarrow f(s)f(t) \in E(H)$$

A homomorphism from a graph $G$ to a graph $H$ is a mapping $f\colon V(G)\to V(H)$ from the vertices of $G$ to the vertices of $H$ with the property

$$st \in E(G) \Longrightarrow f(s)f(t) \in E(H)$$

Under the isomorphism semantic two different query vertices or edges may not map to the same data vertices or edges. In the property graph model a distinction is sometimes made between node and edge isomorphism where the restriction only applies to vertices or edges respectively but not both. Homomorphism does not need to comply with such restriction and may therefor result in larger graphs.

Presence of noise and inconsistencies in data lead to the application of so called similaririty queries that find all subgraphs that approximately match or are contained by a query (Zhao et al. 2013). One measure of similarity is the graph edit distance which details the minimum number of modifications required to transform one graph into the other (Sanfeliu and Fu 1983). Graph edit distance allows for differences in both vertices and edges while being applicable to any type of graphs (Zhao et al. 2013). This makes graph edit distance a suitable measure of similarity for overcoming the limitations of containment queries in graphs of data affected by noise or inconsistencies.


Sanfeliu, Alberto, and King-Sun Fu. 1983. "A Distance Measure Between Attributed Relational Graphs for Pattern Recognition." IEEE Transactions on Systems, Man, and Cybernetics, no. 3: 353--62.

Zhao, Xiang, Chuan Xiao, Xuemin Lin, Wei Wang, and Yoshiharu Ishikawa. 2013. "Efficient Processing of Graph Similarity Queries with Edit Distance Constraints." The VLDB Journal---the International Journal on Very Large Data Bases 22 (6): 727--52.