13
$\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.

Improve this question
$\endgroup$
6
  • 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
    Commented Jul 25, 2014 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
    Commented Jul 25, 2014 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
    Commented Jul 25, 2014 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
    Commented Jul 25, 2014 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
    Commented Jul 28, 2014 at 12:42

2 Answers 2

Reset to default
6
$\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.

Improve this answer
$\endgroup$
3
$\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

Improve this answer
$\endgroup$
13
  • $\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
    Commented Mar 21, 2017 at 14:38
  • 2
    $\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
    Commented Apr 30, 2017 at 20:47
  • 1
    $\begingroup$ I do understand the overall idea of the algorithm. The problem is you cannot "identify" a graph by the paths it contains. In some complicated graphs you can "cross edges" and get non-isomorphic graphs that look the same in terms of paths. I feel we're perhaps not progressing but it's hard for me to give more details in comments. I would suggest you to start a question so I could give more details and/or other users can answer. $\endgroup$
    – badroit
    Commented May 1, 2017 at 16:12
  • 1
    $\begingroup$ I found an example that will fail in your algorithm: Figure 2.4 here: users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf $\endgroup$
    – badroit
    Commented May 1, 2017 at 16:18
  • 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
    Commented May 2, 2017 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.