What equivalence relation does this algorithm produce for an cyclic directed graph with labeled edges?

Question

I have a directed graph, which can be cyclic, where each node contains a value.

Nodes are not labeled, and different nodes can contain the same value.

The outgoing edges of a node are ordered, or labeled, (1, 2, 3, ... N), where N is the number of outgoing edges from the node. (That is, it's a k-ary tree, if such a term can be used for a cyclic structure).

For each node in the graph, I produce a description of that node using the algorithm below. Nodes are considered the "same" (equivalent) if they end up having the same description.

My motivation is that I'd like to produce a hash value from the description which will be the same for nodes where their value and the subgraph reachable from the node are (recursively) the same... however, if the descriptions are the same, the hash will be the same, so we don't need to worry about the hash.

I describe the data structure reachable from the node in this simple way:

1. Number the nodes in the subgraph reachable from the node, which I can do in a specific order (such as breadth-first, ignoring nodes already numbered) because the outgoing edges of a node are labeled.

2. Describe the subgraph reachable from the node by listing the nodes in the subgraph in order by the assigned number, and for each node in the list include in the hash the node's value and for each outgoing edge for the node (in label order), include the number assigned to the tail node of the edge.

For example, for a tree with nodes containing values A, B, C, and D:

I calculate describe A by assigning 0, 1, 2, 3 to the nodes containing A, B, C, D, and describe the values and edges this way:

0: A [1 2 3]
1: B []
2: C [0]
3: D []

Note in particular the outgoing edges from the node containing "A" are ordered (B, C, D), which makes this a unique description of the subgraph (which it wouldn't be if edges were unordered).

And similarly, to calculate the description for C:

0: C [1]
1: A [2 0 3]
2: B []
3: D []

As another example:

both nodes get the same description, because the algorithm produces the same description when run for each node.

Now, I'm assuming I haven't just solved the isomorphism problem for labeled graphs ;-)

Thus I'm guessing this algorithm describes some special case of graph isomorphism easier to solve than the general problem... or, it's not a solution to graph isomorphism because we're comparing nodes not graphs... or the algorithm is flawed doesn't produce the result I think it does! :-)

But I don't know enough computer science to be able to tell which nodes exactly would be characterized as the "same" or "different" by this algorithm.

It might be that different nodes (different in the usual way that you'd typically characterize the isomorphism of labeled graphs) are nonetheless "close enough" for my purposes that I don't mind that they get the same description.

And, if this simple algorithm does produce the result I want, I'd be eager to know if a more efficient algorithm exists. But I can't ask that question without being able to specify what the simple algorithm does do.

Or, if I did understand what equivalence relation the algorithm produced, I might see that the algorithm was indeed flawed for my purposes.

Can you help?

Answer 1

For graph isomorphism, there are many heuristics that work in well in practice on most graphs. You could try adapting any of them to your setting.

Here's one example of a simple heuristic that might often work well in practice (but with no guarantees on worst-case performance). Let $f_0:V \to \mathbb{N}$ be the original values of the graph, so $f_0(v)$ is the value on vertex $v$. Now construct a new set of values $f_1:V \to \mathbb{N}$ from $f_0$, as follows. For each vertex $v$, apply your two-step algorithm to get a description for $f$ using breadth-first search---but crucially, stop the breadth-first search after depth 1. Take the resulting description, hash it with any hash function, and use the resulting hash as $f_1(v)$. You can do this again, and construct $f_2$ from $f_1$ (note that we are now ignoring the original values on the nodes, and using the values from $f_1$, when computing $f_2$), and then construct $f_3$ from $f_2$, and so on. Do this for a few steps, say 100 steps. Each iteration can be done in $O(n)$ time, so the total running time will be $O(n)$ to compute all of the values $f_{100}$.

Now we have a nice property: if $f_i(v_1) \ne f_i(v_2)$, then $v_1$ is not equivalent to $v_2$. Thus, if $f_{100}(v)$ is a singleton ($v$ is the only vertex with that value; i.e., there does not exist $w$ such that $f_{100}(v)=f_{100}(w)$), then there is no need to compute a full description for your $v$. We can apply your full algorithm to compute a full description for only the vertices $v$ whose value appears multiple times in $f_{100}$. Heuristically, for most graphs, there probably won't be many of them. Thus, you won't have to compute the full description for many vertices, and you might avoid quadratic running time.

There are degenerate graphs where this might fall apart, and where the running time becomes quadratic, but for "most" graphs, hopefully this won't happen.

Answer 2

I think the equivalence relation can be defined this way:

Two nodes are equal if they contain the same value, they have the same number of outgoing edges, and, recursively, the subgraphs reachable from the two nodes following the outgoing edges in order are equal.