Heuristic solutions of graph isomorphism

Question

I am trying to implement a heuristic solution for defining classes of isomorphic graphs from a given set of graphs. I am currently tagged for each node with a multiset of degrees of its neighbors (WL algorithm).

This obviously creates false positives for cases such as degree regular graphs. I was hoping to find another inexpensive realistic (temporal and spatial) heuristic that could cross the corner cases of the WL algorithm. In fact, I am looking for a pair of easily implementable heuristics that between them give marginal false positives.

What heuristics other than the WL algorithm should I look for?

Thank!

Answer 1

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

Answer 2

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

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

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

Answer 3

, , , . , , .

Answer 4

, k- -, . :

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

:

, ( ).

, , . -, ( ).

:

N ( N - ) . node:

• node
• node

node . node 2- . N- node N- . Powerhash N = graph_radius. node.

, node . , , . , , node ( ).

Here's more background:

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

Here you can find the source code:

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