Re: Need Graph Isomorphism Algorithm De-bunked


fgrieu wrote:
Some thoughts later: unless I misunderstood the OP's algorithm,
it does not work. At least my variant does not work.
I found a counterexample. These two graphs are non-isomorhic,
but my algorithm fails to distinguish them.

0 1 0 0 0 1 0 1 1 0 0 0
1 0 1 0 0 0 1 0 1 0 0 0
0 1 0 1 0 0 1 1 0 0 0 0
0 0 1 0 1 0 0 0 0 0 1 1
0 0 0 1 0 1 0 0 0 1 0 1
1 0 0 0 1 0 0 0 0 1 1 0

The left is a ring of 6 vertices, the right is 2 independent
rings of 3 vertices. Problem is, the algorithm keeps
assigning the same value to all vertices in the two graphs.

The problem can occur even for fully connected graphs:
just complement the matrix except for the diagonal
and you get a fully-connected counterexample.

I retract all my previous posts in this thread.

Still I feel that the use of a crypto hash made insensitive
to order by sorting its input is a promizing technique
to recognize graph isomorphism.

François Grieu

I made one small addition to the algorithm since you posted your formal
version. I didn't think it was necessarily important, but I required
it to show that when two graphs are reported isomorphic by the
algorithm, that they will be. At each step, I also hash into the hash
at each vertex the iteration step number. In your small ring, values
coming back to the original node will have different hash values
because of this.

I ran the above graph through the latest code (now posted), and it
determines they are different. I have spent a couple more hours trying
to find small manually generated counter examples (which I feel do
exist), but haven't. Next, I'll run it on the hundreds of graphs from:

http://amalfi.dis.unina.it/graph

I've also added code to resolve the isomorphism when the graphs have
auto-morphisms. Now, if the code runs into a counter-example, and it
generates a bad isomorphism, it will report the error.

Hopefully, I can find a counter-example that way, though these graphs
all have one problem: they are trivially distinguishable.

I did find a troubling property of the hash propagation, which I think
is key to why it will fail for some graph. Let's say we're doing a
hash iteration from start node Ak. As the iteration progresses, hash
values influenced by Ak's unique hash value propagate through the
graph. The frontier of reached nodes describes a cut of the graph. If
this cut reaches a point where the sub-graph we've reached has
automorphisms between any two nodes in the cut, then the frontier hash
values will all be identical. At this point, if the nodes connected to
in the unreached portion of the graph by the cut form a subgraph of all
equal degree nodes, then the hash values will not propagate into the
rest of the graph in such a way as to cause nodes to be differentiated.

However, later, when we pick nodes reached by that cut to start from,
we do find the properties of the graph that differentiate these nodes.
This is why I haven't been able to find a counter-example by hand.

.

Relevant Pages

  • Re: (Probably flawed) Polynomial time Graph Isomorphism
    ... I pick a node in G1 to modify. ... I didn't describe the fix to the algorithm well at all. ... no initial difference in the hash values, ... values change throughout the graph and settle to unique values on each ...
    (comp.theory)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... The proof that isomorphic graphs give identical hash, ... We'll be running this version of the algorithm, ... [values of each node in sorted order ]. ... value'@the same for graph G'. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... which correctly differentiates all of the examples you've ... The proof that isomorphic graphs give identical hash, ... [values of each node in sorted order ]. ... note value'@the same for graph G'. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... an accidental hash collision, I think we can get rid of any ... The algorithm is stated for an undirected graph only ... a "result" bit string, initially empty. ... For each node, assign to longhash its value, followed ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... an accidental hash collision, I think we can get rid of any ... The algorithm is stated for an undirected graph only ... a "result" bit string, initially empty. ... For each node, assign to longhash its value, followed ...
    (sci.crypt)