4
$\begingroup$

What are the conditions for two graphs to be in correspondence?

I know for isomorphic - Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic.

But how is isomorphic different from correspondence? does correspondence only means that number of vertices should be same?

I was reading this research paper when the author says "We assume that the connectivity relationship is symmetric, so the networks may be represented as symmetric weighted graphs.We also assume that the two graphs vertices are already in correspondence, and thus in this work do not address the graph-matching problem"

Source: David K. Hammond, Yaniv Gur, Chris R. Johnson, 2013 IEEE Global Conference on Signal and Information Processing, "Graph diffusion distance: A difference measure for weighted graphs based on the graph Laplacian exponential kernel" https://www.sci.utah.edu/publications/hammond13/Hammond_GlobalSIP2013.pdf

$\endgroup$
4
$\begingroup$

The question is: What does graph matching mean in this context? At the end of the quoted sentence is a citation to "Thirty Years Of Graph Matching In Pattern Recognition". That article says:

Graph matching is the process of finding a correspondence between the nodes and the edges of two graphs that satisfies some (more or less stringent) constraints ensuring that similar substructures in one graph are mapped to similar substructures in the other.

That's vague, so the article then breaks down graph matching into various concrete problems: graph isomorphism, subgraph isomorphism, monomorphism, homomorphism, maximum common subgraph, and inexact versions that minimize some cost.

Your article doesn't seem to be interested in such specifics. So to make a long story short, it's just a bijection from one vertex set to the other. In fact, this bijection isn't even made explicit; the rest of the article just assumes that the two graphs have the same vertex set.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.