Graph Matching Search Task

A graph matching search task is a graph search task that requires the identification of an independent edge set in a graph.

• AKA: GMT, Subgraph Matching, Subgraph Matching Task.
• Context:
  • Input: a Target Graph.
  • output: a Independent Edge Set.
  • It can range from being an Exact Graph Matching Task to being an Approximate Graph Matching Task (that includes a Graph Node Similarity Function and/or Graph Edge Similarity Function).
  • It can be solved by a Graph Matching System that implements of a Graph Matching Algorithm.
  • It can range from being a Bipartite Graph Matching Task to being a General Graph Matching Task.
  • …
• Example(s):
  • GMT({1/2,1/3,1/4,2/3,3/4,2/5,4/5,2/6,4/6},{A/B,A/C,A/D,A/E,B/C,C/D,D/E,B/F,D/F,B/G,F/G,E/G}) ⇒ Empty Set.
  • a Graph Isomorphism Task that requires a Graph Isomorphism Mapping.
  • …
• Counter-Example(s):
  • a Graph Record Matching Task.
  • a String Matching Task.
  • a Maximal Common Subgraph Task.
• See: Detection Task, Error-Tolerant Graph Matching.

---

---

References

2014

• (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Matching_(graph_theory) Retrieved:2014-8-22.
  • In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices.

2007

• (Neuhaus & Bunke, 2007) ⇒ Michel Neuhaus, and Horst Bunke. (2007). “Bridging the Gap Between Graph Edit Distance and Kernel Machines." Series in Machine Perception and Artificial Intelligence - Vol. 68

2004

• (Conte et al., 2004) ⇒ Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. (2004). “Thirty Years of Graph Matching in Pattern Recognition.” In: International Journal of Pattern Recognition and Artificial Intelligence, 18(3).

2001

• (Luo & Hancock, 2001) ⇒ Bin Luo and Edwin R. Hancock. (2001). “Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition.” In: IEEE Transactions on Pattern Analysis and Machine Intelligence, 23(10). doi:10.1109/34.954602
  • QUOTE: … we have cast the problem of graph matching into a maximum likelihood framework by constructing a mixture model over the set of hidden correspondences and adopting a Bernoulli model for the distribution of edge-matching errors. … When viewed from the perspective of recent work on matrix-based graph matching, the important contribution of this paper is to show how point-sets of different sizes can be matched using singular value decomposition.

---