11
$\begingroup$

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is exponential, one usually has a polynomial running time.

I was hoping that the situation is similar in the case of labeled graphs. However, I have a really hard time to find any reference which proposes an "practically efficient" algorithm.

Remark: Here, we require that the isomorphism preserves the labels. That is, an isomorphism between two finite automata/process algebra terms would imply that the automata/terms are essentially "equal up to renaming of the nodes".

The only reference I found was the one in Wikipedia that states the the isomorphism problem of labeled graphs can be polynomially reduced to that of ordinary graphs. The underlying paper, however, is more about complexity theory than practical algorithms.

I am missing something, or is it really the case that the there are no efficient "heuristical" algorithms to decide whether two labeled graphs are isomorphic?

Any hint or reference would be great.

$\endgroup$
  • 3
    $\begingroup$ It would be nice to give references to the wikipedia article and to the paper you found, to save us the trouble. $\endgroup$ – babou Jul 25 '14 at 10:05
  • 1
    $\begingroup$ What do you mean by an isomorphism that "preserves the labels"? In the context of an automaton, the vertex labels are distinct. Therefore, any isomorphism trivially "preserves labels" in the sense that two vertices in the source that have distinct labels must have distinct labels in the image, too. That problem is identical to the ordinary graph isomorphism problem. If you mean that the isomorphism must map a vertex to one with the same label, the algorithm is trivial when vertex labels are always distinct: just check that the identity map on the labels is an isomorphism. $\endgroup$ – David Richerby Jul 25 '14 at 11:10
  • $\begingroup$ If you mean to consider the case where several vertices may have the same label and the image of a vertex must have the same label as the original one, that is often referred to as isomorphisms between coloured graphs. In that case, there is a simple reduction to general GI by replacing the colours by gadgets. You could probably get a decent practical algorithm by applying carefully chosen gadgets and then using a standard GI algorithm. $\endgroup$ – David Richerby Jul 25 '14 at 11:11
  • $\begingroup$ Are you really unwilling to consider two edge-labeled digraphs as isomorphic if there is an ordinary digraph isomorphism that also preserves equivalence classes of labels? In your example, considering the two to be FAs, the languages accepted by$S^*$ and $S'$, while different (perhaps), are really just homorphic images of each other by the substitutions $a\leftrightarrow c, b\leftrightarrow d$. $\endgroup$ – Rick Decker Jul 25 '14 at 16:03
  • 4
    $\begingroup$ The problem is trivially GI-complete (just pick a graph where all edges have the same label). To show that it is not harder than graph isomorphism, build a 1:1 map from labels to integers ($g : a\to 1, b \to 2, c \to 3, ...)$ and add in the middle of each edge labeled with symbol $s$ a complete graph on $g(s)$ vertices ($K_{g(s)}$) plus an extra node on the arrow side of the edge. The resulting graphs are isomorphic if and only if the original automata are isomorphic. $\endgroup$ – Vor Jul 28 '14 at 12:42
5
$\begingroup$

You might be interested in this paper:

Aidan Hogan: Skolemising Blank Nodes while Preserving Isomorphism. WWW 2015: 430-440

It has an algorithm (based on Nauty) for testing the isomorphism of RDF graphs, which are essentially directed labelled graphs that may contain fixed labels. The algorithm takes labels into account to narrow the search space.

If you can represent your input labelled graph as an RDF graph, you could try use the associated software package "blabel" to test isomorphism.

$\endgroup$
4
$\begingroup$

I've found out that the algorithm belongs in the category of k-dimension Weisfeiler-Lehman algorithms, and it fails with regular graphs. For more here:

http://dabacon.org/pontiff/?p=4148

Original post follows:

Years ago, I created a simple and flexible algorithm for exactly this problem (graph isomorphism with labels).

I named it "Powerhash", and to create the algorithm it required two insights. The first is the power iteration graph algorithm, also used in PageRank. The second is the ability to replace power iteration's inside step function with anything that we want. I replaced it with a function that does the following on each iteration, and for each node:

  • Sort the hashes (from previous iteration) of the node's neighbors
  • Hash the concatenated sorted hashes
  • Replace node's hash with newly computed hash

On the first step, a node's hash is affected by its direct neighbors. On the second step, a node's hash is affected by the neighborhood 2-hops away from it. On the Nth step a node's hash will be affected by the neighborhood N-hops around it. So you only need to continue running the Powerhash for N = graph_radius steps. In the end, the graph center node's hash will have been affected by the whole graph.

To produce the final hash, sort the final step's node hashes and concatenate them together. After that, you can compare the final hashes to find if two graphs are isomorphic. If you have labels, then add them (on the first iteration) in the internal hashes that you calculate for each node.

For more on this you can look at my post here:

https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF

The algorithm above was implemented inside the "madIS" functional relational database. You can find the source code of the algorithm here:

https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py

$\endgroup$
  • $\begingroup$ Just a warning that your algorithm is polynomial and so if it is complete, you've just solved a long-standing open problem in CS about GI being in P. :) (There are various cases where the algorithm you describe will give false positives.) $\endgroup$ – badroit Mar 21 '17 at 14:38
  • $\begingroup$ The algorithm is approximate and certainly not complete (i say so in the blog post too). The reason it works is that the hashes it creates are huge, so in a database of even millions of graphs the possibility of false positive hash collisions will be infinitesimal. If you manage to find any case of a false positive hash collision i would be very interested to know about it. The reason (when using cryptographic hashes) is that, you will have managed to "break" the cryptographic hash function. $\endgroup$ – estama Apr 30 '17 at 16:05
  • $\begingroup$ To elaborate on how infinitesimal the possibility of a hash collision is. I would consider a cryptographic hash of 256bits to be more than enough to be sure that all the different files of the world do not hash to the same value (git for example uses SHA-1 which is 160bits to guarantee that). A hash from Powerhash will be 128bits * graph_node_count (using MD5 hash). So practically, you would never be able to create enough graphs (in this universe) to find a hash collision between them. $\endgroup$ – estama Apr 30 '17 at 16:26
  • 1
    $\begingroup$ I meant your algorithm will give false positives even assuming no hash collisions. A lot of polynomial-time algorithms have been proposed for graph isomorphism in the literature and all of them give false positives. A related question here: cs.stackexchange.com/questions/50939/…. $\endgroup$ – badroit Apr 30 '17 at 20:47
  • 1
    $\begingroup$ Thank you for the discussion. With some more research i've found that the algorithm above is in the category of k-dimension Weisfeiler-Lehman algorithms, and it fails with regular graphs. For more here: dabacon.org/pontiff/?p=4148 $\endgroup$ – estama May 2 '17 at 11:14

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.