1
$\begingroup$

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.

Figure 1

$\endgroup$
  • 3
    $\begingroup$ Note that recommendations for software to use are off-topic, here. Software Recommendations deals with that sort of thing. $\endgroup$ – David Richerby Sep 24 '16 at 9:39
  • 1
    $\begingroup$ Please define clearly what you mean "structurally similar" and "node mapping" and "matching". $\endgroup$ – Raphael Sep 25 '16 at 11:51
  • $\begingroup$ @Raphael Ok, I think I redefine the meaning in a rough manner. It is like a fuzzy matching. $\endgroup$ – WindChaser Sep 25 '16 at 20:28
  • $\begingroup$ 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? $\endgroup$ – Evil Sep 25 '16 at 20:52
  • $\begingroup$ @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. $\endgroup$ – WindChaser Sep 25 '16 at 21:25
3
$\begingroup$

You want to solve the problem of graph isomorphism (GI). GI is not known to be in P or NP-complete; that is, we do not know any efficient algorithms.

Many algorithms have been proposed for GI. None applies to all graphs and is always fast, but you may be able to find one that is sufficiently fast in your application.

In 2015, Babai proposed a quasi-polynomial algorithm for GI [1]. As far as I know, peer-reviewed is not yet completed; I also do not know if it is practically feasible. If correct, it is the most "efficient" algorithm known in terms of Landau-style complexity.


  1. Graph Isomorphism in Quasipolynomial Time by L. Babai (2015) [retraction note]
$\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.