Find Mapping Node in a Graph

Given two large directed graphs (may have loops and lonely nodes) A and B. They are structurally similar.

If we give a node in Graph A, how to find the corresponding one in Graph B?

Finally, we need to find all the node mappings.

Of course, there can be more than one possible mapping. We need to find the similarity (ranking) percentage.

How to design such an algorithm?

The graphs are Control-flow Graphs (Call Graph) extracted from program binaries. However, due to compiler difference (optimization, inline, etc.), the graphs can be a little different.

UPDATE:

To be more clear, as shown in the figure below, we also need to find the matching like B and B',B1' ("->" means a node match):

A -> A'

B -> (B' , B1')

C -> C'

D -> D'

E -> E'

F -> F'

As this is not a sub-graph matching, I cannot find good library APIs or algorithms.

• Note that recommendations for software to use are off-topic, here. Software Recommendations deals with that sort of thing. Sep 24 '16 at 9:39
• Please define clearly what you mean "structurally similar" and "node mapping" and "matching".
– Raphael
Sep 25 '16 at 11:51
• @Raphael Ok, I think I redefine the meaning in a rough manner. It is like a fuzzy matching. Sep 25 '16 at 20:28
• Does the corresponding nodes share label or this is for illustration only? I do not have a fully specified idea, but if you run DFS on both of them, merge nodes before disjunctions (B' with B1') and flag non-existent nodes (or just delete them), does the result's resemblance enough to determine the correct node?
– Evil
Sep 25 '16 at 20:52
• @Evil This is for illustration only, they do not have labels. What I need to find is which nodes can be merged according to the two graphs. The result could be a list of possible matches. For example, A->B->C could be merged as A->BC, or AB->C, or ABC, or not merged at all. The actual problem definition is hard to describe since it is basically fuzzy matching, not determined. But the graph is large and complex enough, so the matching accuracy could be non-trivial. Sep 25 '16 at 21:25