CODEWITHSUNDEEP
algorithmgraphheuristicsisomorphism
Devaansh Samant
Devaansh Samant

Reputation: 51

Graph Isomorphism Heuristic Solutions

I'm trying to implement a heuristic solution to identify classes of isomorphic graphs from a given set of graphs. Currently I'm labeling each node with a multiset of the degrees of its neighbours (WL Algorithm).

This obviously produces false positives, for cases such as degree regular graphs. I was hoping to find another cheaply implementable (time and space constrained) heuristic that could cut across the corner cases of the WL Algorithm. Essentially I'm looking for a pair of easily implementable heuristics which between them give marginal false positives.

Which heuristic other than the WL algorithm should I be looking at?

Thanks!

Upvotes: 5

Views: 997

Answers (4)

estama
estama

Reputation: 81

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:

I've worked on the problem to find isomorphic graphs in a database of graphs (containing chemical compositions).

In brief, the algorithm creates a hash of a graph using the power iteration method. There might be false positive hash collisions but the probability of that is exceedingly small (i didn't had any such collisions with tens of thousands of graphs).

The way the algorithm works is this:

Do N (where N is the radius of the graph) iterations. On each iteration and for each node:

  • Sort the hashes 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 the direct neighbors of it. 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 in the internal hashes that you calculate for each node (and at each step).

There is more background here:

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

You can find the source code of it here:

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

Upvotes: 2

gilleain
gilleain

Reputation: 641

Another invariant that could be relatively cheap to calculate is the list of cycles that a vertex is part of. Of course, that requires finding the cycles in your graph, but there are many algorithms to do that.

Upvotes: 0

krjampani
krjampani

Reputation: 2982

Checkout the VF2 algorithm: http://www.researchgate.net/profile/Carlo_Sansone/publication/200034365_An_Improved_Algorithm_for_Matching_Large_Graphs/links/0912f50dc9cf0a98d4000000.pdf

There's a C++ library that implements VF2: http://mivia.unisa.it/datasets/graph-database/vflib/

A Comparison of VF2 with a few other algorithms: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.2640&rep=rep1&type=pdf

Upvotes: 1

Edward Doolittle
Edward Doolittle

Reputation: 4110

Maybe consider the least colored shortest path invariant discussed in this paper: http://www.academia.edu/5111652/A_new_refinement_procedure_for_graph_isomorphism_algorithms?

Upvotes: 0

Related Questions