Graph isomorphism and canonization via NautyGraphs.jl

[mxhbl]

Following the suggestion of @Krastanov, this PR adds NautyGraphs.jl as a weakdep, which makes it possible to use nauty for graph isomorphism and canonization.

Main Changes

• New function Graphs.Experimental.canonize!(g, alg) that permutes a graphs vertices into the canonical order defined by the algorithm alg. If two graphs g1 and g2 are isomorphic, g1 == g2 after canonization.
• NautyGraphsExt package extension, which implements canonize! and has_isomorph with NautyGraphs as a backend. Other isomorphism algorithms are currently not supported, and throw an error if called with alg=AlgNautyGraphs(). Vertex and edge relations are currently also not supported, but could in principle be implemented by cleverly transforming the input graph.
• Since canonize! permutes a graph's vertices in-place, I also implemented a function permute!(g::Graph, p) that performs the permutation.

Other Changes

• Calling any function in Graphs.Experimental with an algorithm that doesn't define an implementation method results in a stack overflow. Since the dispatch struct AlgNautyGraphs needs to be define inside the main Graphs module and not in the package extension, this would cause stack overflow errors if the user tries to call e.g. has_isomorph(g, h, AlgNautyGraphs()) without loading NautyGraphs first. I changed this to manually throw method errors in the fallback methods, which leads to nicer error messages for the user.

Tests?

I am not sure how to best test the isomorphism and canonization, both in Graphs.jl, but also in NautyGraphs.jl itself. Are there any standard test sets of graphs that are not too hard to check but also nontrivial? Should I test NautyGraphs against VF2?

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 62.31884% with 26 lines in your changes missing coverage. Please review.

Project coverage is 96.57%. Comparing base (12ac6ba) to head (f6135eb).

Files with missing lines	Patch %	Lines
ext/NautyGraphsExt.jl	25.71%	26 Missing :warning:

Additional details and impacted files

@@            Coverage Diff             @@
##           master     #418      +/-   ##
==========================================
- Coverage   97.31%   96.57%   -0.74%     
==========================================
  Files         117      120       +3     
  Lines        6956     7016      +60     
==========================================
+ Hits         6769     6776       +7     
- Misses        187      240      +53     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[simonschoelly]

NautyGraphs.jl is interesting, but before you put too much effort into this PR, I don't see what we gain by making an extension in Graphs.jl? NautyGraphs.jl depends on Graphs.jl, so we can just import the symbols there and create concrete implementations there?

[Krastanov]

NautyGraphs.jl depends on Graphs.jl, so we can just import the symbols there and create concrete implementations there?

You are right about not needing the extension itself, that is my fault for misleading @mxhbl . I did not catch that the dependency already existed, rather silly of me. Apologies for that! Either way, three points to specify though:

• AlgNautyGraphs existing in this repo would make discoverability much nicer
• Error hints provided here, about the need to import NautyGraphs would also make discoverability easier
• canonize! coming from Graphs and just being extended by NautyGraphs, as you mentioned, would simplify organization

[mxhbl]

You are right that the package extension is not required. But I do agree with @Krastanov that making canonize! a function in Graphs might be a nice addition. Especially if there are multiple algorithms that could do the canonization. I am not super familiar with VF2, but if there is a way to perform graph canonization with it I would be happy to implement a version of canonize! in Graphs that defaults to VF2 and can then be extended in NautyGraphs.

[simonschoelly]

You are right that the package extension is not required. But I do agree with @Krastanov that making canonize! a function in Graphs might be a nice addition. Especially if there are multiple algorithms that could do the canonization. I am not super familiar with VF2, but if there is a way to perform graph canonization with it I would be happy to implement a version of canonize! in Graphs that defaults to VF2 and can then be extended in NautyGraphs.

I actually asked myself the same question a few weeks ago - it looks like there is no such things for VF2 or any of its extensions such as VF2+, VF3. But these algorithms are basically just simple search algorithms that explore the tree of all possible matchings between two graphs and use some pruning heuristics to speed up the process.

The tools/algorithms listened in this survey are:

• nauty
• traces
• bliss
• saucy
• conauto

I did not have the time to look at them yet and see if one would be easy to implement here.

There is also this never result by László Babai - but it seems to be of theoretical nature only - and I am not even sure if the results there have been definitely confirmed.

[mxhbl]

Thanks for the list. I was also not able to find pre-made approaches to canonization with VF2 unfortunately.

It's my understanding that all of the algorithms you listed rely complex heuristics to achieve good performance and would take a lot of effort to reimplement here. E.g. nauty and traces each have >10,000 lines of code.

[Krastanov]

@mxhbl , would you be interested in setting up a bounty (for you, for a coworker, for a junior dev/student that you know or just someone from the community) in the style of this one https://github.com/JuliaGraphs/Graphs.jl/issues/448 (but for NautyGraphs.jl)

[mxhbl]

@Krastanov that sounds great, I'd be more than happy to help in any way I can. What exactly did you have in mind?

[Krastanov]

I think the following is a good list of requirements, but please feel free to suggest changes or other approaches. Some things might already be available:

• Graph(::NautyGraph) and NautyGraph(::Graph) should be fast and if the internal layout permits, creating non-copying constructors should be possible
• The basic Graphs API should be supported by NautyGraph, basically what is shown here https://juliagraphs.org/Graphs.jl/stable/core_functions/interface/
• after that is vetted, making sure that these functions "just work" https://juliagraphs.org/Graphs.jl/stable/core_functions/core/
• some documentation for the fact that NautyGraphs is available in a way the extends the capabilities of Graphs
• and lastly, introducing the interesting capabilities of nauty graphs. This has two components:
  • if there is a function Graphs.some_expensive_computation(::Graph) that is also implemented in nauty graphs, then a method for it should be defined in NautyGraphs some_expensive_computation(::Graph, NautyGraphs.NautyAlg())
  • if there is an interesting algorithm available in NautyGraphs but not available in Graphs, then an empty function declaration should be added to Graphs (together with a good error hint) and a method for that new function goes in NautyGraphs

The very last subpoint is something that will need to be approved by the community though, as it is an actual change to Graphs.

[Krastanov]

another thing to add to the list:

• use GraphsInterfaceChecker.jl in the test suite

[mxhbl]

Thats sounds great. I think a lot of the Graphs API should already be supported, but test and general polish are badly needed. This would also be a great opportunity to add support for nautys sparse graph format, which probably can be converted to and from a SimpleGraph without copies. I'd love to work on this and I think your review would be very beneficial! What is the standard way to manage/track the workflow with this kind of project? Should I open an issue in NautyGraphs?

[Krastanov]

We do not really have a standard workflow for this. How about the following: copy one of the existing bounties for the other libraries, flesh it out with the TODOs you and I listed here, post it on the Graphs.jl issue tracker, and if it is something that I can comfortably request from the sponsor, I will just mark it as a bounty and mark it as reserved for you.

[mxhbl]

I created an issue (#452) with the points we discussed. Let me know if it looks good to you!

[Krastanov]

great! Marked as a reserved bounty