The graph canonical labelling package nauty is widely regarded as one of the best (if not the best) around. Unfortunately, it’s quite a large package, and making a GPU version seems to be a highly nontrivial task.
In my research into algorithms for network motif detection, we often require an effective solution to the problem of, what I like to call, “canonically labelling a billion smalls graphs”. This should be a highly parallelisible problem, and therefore be suitable for the GPU architecture (although, there are issues of data transfer, memory usage, SIMD, etc., which I’m sweeping under the carpet).
This leads to the questions:
What other algorithms/packages are around that can perform graph canonical labelling?
For my purposes, it should ideally be lightweight and parallelisible, although, academic curiosity makes me interested in any alternatives. Note that these alternatives do not necessarily need to be faster than nauty.
Nauty has been well-established since well before I started in mathematics, so I’m not at all familiar with what people did before nauty came along.
There are a number of alternatives: