difference between graph isomorphism and subgraph isomorphism
Posted by: maya
Date: June 20, 2018 09:14PM

Hello,

Does any one know the difference between graph isomorphism and subgraph isomorphism problems? and which one is used in frequent subgraph mining?

Regards,
Maya

Re: difference between graph isomorphism and subgraph isomorphism
Date: June 20, 2018 09:54PM

Those are mostly the same thing.

In simple words, two graphs are isomorphic if we map the edges and vertices of one graph to the other and they are equivalent.

Subgraph isomorphim checking is the same thing. But since you add the word "subgraph" it means that you are comparing subgraphs of a graph to check if these subgraphs are equivalent.

Yes, the idea of graph isomorphism is used in frequent subgraph mining to detect if equivalent graphs are found more than once, and eliminate these redundant graphs. And since a pattern in frequent subgraph mining is a subgraph, then you can say that it is subgraph isormorphism checking.

Edited 2 time(s). Last edit at 06/20/2018 09:57PM by webmasterphilfv.

Re: difference between graph isomorphism and subgraph isomorphism
Posted by: maya
Date: June 23, 2018 01:21AM

Thanks a lot for your clarification.

Regards,
Maya

Re: difference between graph isomorphism and subgraph isomorphism
Posted by: maya
Date: June 23, 2018 01:25AM

another question!

in two isomorphic graphs,should the mapped nodes and edges have the same names or not necessary? or the should have the same shape only?

Re: difference between graph isomorphism and subgraph isomorphism
Date: June 23, 2018 02:25AM

In frequent subgraph mining, you typically have edges and vertices that have names. For example, you could have a graph about a water molecule, and you would have two nodes that have the same label "Hydrogen" and one node with the label "Oxygen"

Hydrogen ---- Oxygen ----- Hydrogen

Now, when you check if two graphs are isomorphic, yes, you need to check that the structure match but also the names (labels). And if you have label on the edges, you also need to check the labels on the edges.

Re: difference between graph isomorphism and subgraph isomorphism
Posted by: maya
Date: June 25, 2018 08:05AM