Source-linked AI summary
Practical graph isomorphism, II
Brendan D. McKay, Adolfo Piperno
TL;DR
Graph isomorphism lacks a generally useful practical solution across graph classes, motivating comparison of specialized algorithms. The paper formalizes refinement-individualization, updates nauty, introduces Traces, and evaluates these programs against saucy, Bliss, and conauto. Traces leads on most difficult tested families, while nauty remains preferred for mass testing of small graphs, with limitations in refinement selection and preprocessing scope.
Problem
Graph isomorphism requires practical methods that can handle varied graph families, where direct testing is poorly suited to removing isomorphs from collections or retrieving graphs from databases.
Method
The paper describes and proves the refinement-individualization framework, details nauty and Traces, and compares them with saucy, Bliss, and conauto.
Results
Traces is the current leader on the majority of difficult graph classes tested, while nauty is preferred for mass testing of small graphs.
Takeaways & Limitations
The preferred program depends on graph class: Traces suits most difficult families, whereas nauty suits small-graph mass testing.
Takeaways & Limitations
Refinement strength trades partitioning power against cost, and choosing a partitioning function in nauty requires user skill.
Abstract
from arXiv · showhide
We report the current state of the graph isomorphism problem from the practical point of view. After describing the general principles of the refinement-individualization paradigm and proving its validity, we explain how it is implemented in several of the key programs. In particular, we bring the description of the best known program nauty up to date and describe an innovative approach called Traces that outperforms the competitors for many difficult graph classes. Detailed comparisons against saucy, Bliss and conauto are presented.
1. Introduction
Practical graph isomorphism centers on canonical labelling and the individualization-refinement paradigm. The paper updates nauty, introduces Traces, and compares several leading programs across graph families.
- Canonical labelling makes isomorphic graphs identical after relabelling, enabling sorting-based duplicate removal and database retrieval.
- The individualization-refinement paradigm fixes vertices and refines vertex partitions, forming the basis of the most successful practical algorithms.
- Nauty handled structurally regular graphs and graphs with large automorphism groups by using automorphisms to prune its search.
- Saucy used sparse data structures and later detected some automorphisms early, while Bliss added early-abort refinement operations for difficult graphs.
- Traces extends these developments with early-aborted refinement and a revised search-tree scan intended to improve efficiency on difficult graphs.
- The paper compares nauty, Traces, Bliss, saucy, and conauto across graph families, finding no universal fastest program.
2. Generic Algorithm
The generic algorithm combines ordered colourings, refinement, and individualization in a search tree to compute automorphism groups and canonical forms. Label-invariant refinement and tree traversal make the construction valid for graph isomorphism.
- 2.1. Colourings: A colouring partitions the vertex set into ordered cells, with a discrete colouring assigning each vertex a singleton cell.The ordering of colours matters when comparing colourings by refinement.
- 2.2. Refinement: Refinement produces a finer colouring, isolates individualized vertices, and remains compatible with relabelling by vertex permutations.These properties ensure the refinement process respects graph isomorphisms.
- 2.3. Search tree: The search tree branches by appending vertices from a selected non-singleton target cell, and its leaves are exactly the nodes whose derived colourings are discrete.Each sequence records individualized vertices while refinement determines the remaining colouring.
- 2.3. Search tree: Automorphisms map search-tree nodes and subtrees to corresponding nodes and subtrees, while the refined colouring identifies the point-wise stabilizer of the individualized sequence.This links tree symmetries directly to automorphism-group structure.
- 2.4. Automorphisms and canonical forms: A canonical form selects a maximizing leaf invariant and relabels the graph using its discrete refinement, yielding a unique representative of each isomorphism class.The resulting function satisfies isomorphism and label-invariance properties.
- 2.4. Automorphisms and canonical forms: The resulting search procedure can compute automorphism groups and canonical forms, but practical performance depends on pruning because the unpruned tree may be extremely large.The generated automorphisms and remaining leaves provide generators for the automorphism group.
3. Implementation strategies
The implementations of nauty and Traces combine equitable refinement, individualization, node invariants, pruning, and automorphism detection in different ways. Traces uses vector-valued traces and breadth-first tree generation, while nauty relies on integer invariants and depth-first search; nauty’s stronger refinements require user expertise, whereas Traces often avoids them.
- Core framework: Nauty and Traces are implementations of the generic graph-isomorphism algorithm based on colourings, refinement, individualization, search trees, invariants, and group actions.The refinement procedure produces equitable colourings, and the search tree supports computation of automorphism groups and canonical forms.
- Refinement: Equitable refinement repeatedly splits cells according to vertices’ numbers of edges to selected cells, producing a final equitable colouring.The algorithm removes a cell from the active sequence, distinguishes fragments by edge counts, and replaces the original cell with those fragments.
- Refinement: Individualization assigns a unique colour to a selected vertex, after which refinement is applied to the resulting colouring.The individualization function preserves earlier colour numbers, gives the selected vertex a unique colour, and increments later colours.
- Practical trade-offs: Nauty’s stronger partitioning functions can dramatically improve performance on difficult graph classes but require users to choose an appropriate function.Traces reduces dependence on such user expertise because partial trace comparisons often make stronger nauty refinements unnecessary.
- Practical trade-offs: Traces prefers large target cells to make the search tree less deep, while its heuristic chooses the first largest suitable non-singleton cell, falling back through ancestor target cells.This contrasts with recommendations for nauty that favor the first non-singleton cell or, in earlier work, the first smallest non-singleton cell.
- Search and invariants: Nauty uses integer-valued node invariants and depth-first search, whereas Traces uses vector-valued traces and breadth-first search guided by the strongest invariant values at each level.Traces records cell sizes and positions during refinement, allowing comparisons before a node’s refinement is complete; nauty’s basic depth-first approach is also used by Bliss and saucy.
- Search and invariants: Traces derives node-invariant information from refinement states and quotient-graph information, using compact data that usually retains the pruning power of full quotient matrices.Its trace is based primarily on the sizes and positions of cells as they are created, and only a fraction of refinement operations may be needed for difficult graph families.
- Automorphism detection: Automorphisms support pruning, with saucy detecting some mappings high in the tree and Traces heuristically extending fixed-vertex mappings to non-fixed vertices.Saucy can be very fast on graphs with many automorphisms moving few vertices; Traces generalizes this detection beyond identity mappings on non-trivial vertices.
4. Performance
The performance study compares nauty, Traces, saucy, Bliss, and conauto across graph families, measuring automorphism-group computation and canonical labelling under specified experimental conditions. The comparisons cover graphs ranging from easy to difficult, while some program capabilities and available implementations constrain the study.
- Experimental scope: The study compares nauty, Traces, saucy, Bliss, and conauto on graph families ranging from very easy to very difficult.The authors attempted to include graphs that were easy and difficult for each tested program.
- Test data: Most test graphs come from the Bliss collection, and the authors provide all test graphs through the nauty and Traces website.The supplied test set is therefore partly based on an existing benchmark collection and partly documented by the authors.
- Experimental conditions: The timings use single-threaded execution on a 2.66 GHz Intel i7 MacBook Pro, with random input relabelling and repeated runs for easy graphs.Processing times can depend substantially on initial labelling for some graph classes.
- Measured tasks: Automorphism-group computation and canonical labelling are evaluated separately, with canonical-labelling runs including automorphism-group computation.The first plot column concerns automorphism groups; the second concerns canonical labelling.
- Program configuration: The study uses nauty’s dense or sparse version consistently within each class and generally omits invariants, even when they would often help.This reflects the authors’ stated setup rather than a claim that invariants are ineffective.
- Scope boundaries: Saucy lacks a canonical-labelling option in the tested setup, while its newly released version 3.0 had an insufficiently tested saucy–Bliss amalgam for that task.The authors also excluded conauto’s graph-isomorphism testing because that task was outside the study’s scope.
- Scope boundaries: The comparisons exclude Stoichev’s program because the authors were technically unable to include it.The paper directs readers to the nauty and Traces website for further experiments and comments.
5. Conclusions
The paper updates nauty’s published description and introduces Traces, whose tree-scanning algorithm substantially improves processing power. Across the tested difficult graph classes, Traces leads most often, while nauty remains preferred for mass testing of small graphs and some component-based classes favor conauto and Bliss.
- Contributions: The paper brings nauty’s published description up to date and introduces the Traces program.These are the paper’s central program-level contributions.
- Contributions: Traces’ tree-scanning algorithm can have a remarkable effect on processing power.The conclusion identifies this algorithm as the source of the reported improvement.
- Comparative conclusions: Traces is the current leader on the majority of difficult graph classes tested, although no tested program performs best on every graph class.The conclusion presents this as a comparative result across the tested classes.
- Comparative conclusions: Nauty remains preferred for mass testing of small graphs.This is the paper’s stated practical distinction between Traces and nauty.
- Comparative conclusions: Conauto and Bliss have special code for non-disjoint unions of tripartite graphs, whereas nauty and Traces do not yet have such code.This is the stated exception involving disjoint or minimally overlapping components.