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

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.

Thanks a lot for your clarification.

Regards,
Maya

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?

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.

Thanks a lot for your reply.