Benchmarks

Here, you can find benchmarks comparing state-of-the-art solvers to dejavu.

Benchmark Suite #

We test 44 graph classes, comprised of almost all sets linked in the standard benchmark library. Specifically, we test all graph classes listed under bliss, conauto, saucy, random graphs, miscellaneous graphs, Dawar-Yeung graphs, as well as the shrunken multipedes. We solely left out very few sets for at least some brevity (e.g., slightly easier variants of shrunken multipedes).

We made the following additions to the benchmark suite, which we believe to be meaningful:

• mip17: practical graphs stemming from symmetry exploitation in mixed-integer solvers, provided by Marc Pfetsch and Christopher Hojny
• sat21: graphs stemming from SAT solving, preprocessed using unit and pure
• pace23: graphs from the pace challenge 2023 (twin width)
• groups128: some multiplication tables of groups of order 128, provided by Jendrik Brachter
• CFI and complete graphs: extended the sets with larger graphs

The benchmark graphs can either be found in 📖 Adolfo Piperno’s collection, or on our graph page. We configured dejavu with an error probability below 0.1%, but used a pseudo random number generator. More details on the precise benchmark setup can be found further below.

Results Summary #

We give a brief overview of the results of our benchmarks.

Fastest on Graph Class

First, taking the sum of all the runtimes of a graph class, dejavu is fastest on 32 classes, with Traces being fastest on 8, saucy on 3, and nauty on 1 (out of 44 total classes).

• dejavu 32
• Traces 8
• saucy 3

Competitive (within factor 2 of best) on Graph Class

We get a more refined picture if we define a solver to be competitive, if it finishes within a factor of two of the fastest solver. Considering this, dejavu is competitive on 39 classes, Traces on 22, saucy on 15, nauty on 11, and bliss on 3 (out of 44 total classes).

• dejavu 39
• Traces 22
• saucy 15
• nauty 11
• bliss 3

Timeouts

We ran all benchmarks with a time limit of 100 seconds. On all graph classes, dejavu posted the lowest number of timeouts achieved in the benchmarks (in the majority of classes the score was tied at 0, though). Summing over all the graphs in the benchmark suite, dejavu reported 31 timeouts, Traces reported 558, bliss reported 489, nauty reported 840, and saucy reported 557. We also remark that nauty and Traces ran out of memory on some graphs, wich we counted as a timeout. More details can be found in the table and figures shown below.

Results Table #

Below is a table summarizing our benchmark results for each graph class and solver. For each class we report its size, meaning the number of graphs contained in the class. Then, for each class and solver, report the sum of the runtimes of all the graphs in a class as t. If the solver did not solve a graph within the timelimit of 100 seconds, we classify the graph as a timeout. The number of timeouts can be found in the rows labeled t/o.

The best reported runtime and timeout for each graph class is signified in bold. If a solver finished within a factor of 2 of the best runtime for a given class, we report this as “competitive”, signified in italic. All runtimes are reported in seconds.

*Not randomly permuted, but in the original vertex order. We added this line to show that dejavu is able to solve all graphs of this class within the given timelimit, if graphs are not randomly permuted. Note that this unpermuted set is not included in the summary above (or below).

**We restricted this set to graphs below 1536 vertices, which suffices to timeout all the solvers (larger graphs will solely produce timeouts).

Plot for each Class #

Below are detailed plots for the tested benchmark classes. Click a plot to view in fullscreen.

Note that in all of the figures and for each solver, the instances were always sorted according to running time. We have another page that contains scatter plots, plotting graph size versus running time. However, in some of the sets, there is only a weak correspondence between graph size and difficulty of the graph. This is why in the plots below it is easier to tell which solver is faster – whereas in the other plots scaling with size is more apparent. Below, “spikes” at the end of the plots do not necessarily mean that the solvers start to scale much worse “at the end of the set”. Rather, this is often due to a few of the graphs (not necessarily the largest ones) posing some more difficulty to a solver in a certain run, often related to a specific random permutation of a graph.

Benchmark Setup #

Benchmarks were run on an Intel i7 9700K with 64GB of RAM on Ubuntu 20.04. All solvers ran on a single thread, with the full amount of RAM available (we did not run any benchmarks in parallel). All graphs were randomly permuted, but each solver was passed the same permuted version of the graph. The versions used are bliss 0.73, nauty/Traces 2.6R12, saucy 3.0, and dejavu 2.0preview1. We are aware that slightly newer versions of bliss and nauty are available. While we do not believe that these would considerably change the benchmark numbers, we will re-run the benchmark numbers in some time.

We configured dejavu with an error probability below 0.1%, but used a pseudo random number generator. Essentially, we used the default configuration of the solver. However, we did make one adjustment for the sake of fairness: we used an empty function as the hook (instead of a nullptr), in order to enforce that all generators are properly lifted back to the original graph. If a nullptr is passed instead, i.e., only the automorphism group size is computed, the solver will run faster on many of the graphs.