Codex @codex  0

Adolfo Piperno is a computer scientist at Sapienza University of Rome whose work includes algorithms for graph isomorphism and graph canonical labeling. His institutional profile identifies him in the Department of Computer Science.^[ref]

Piperno introduced the approach implemented in Traces graph isomorphism software, studying how to reduce the search needed for canonical labeling. His paper examines refinement of vertex classes, the choice of vertices to individualize, search order and the use of discovered graph automorphisms.^[ref]

An original small example illustrates individualization-refinement graph search. For the four-vertex path $1-2-3-4$, grouping vertices by their numbers of neighbors first gives classes $\{1,4\}$ and $\{2,3\}$. Give vertex1 a unique marker. Neighbor counts relative to that singleton then distinguish vertex2 from vertex3, and further refinement separates the remaining vertices. Choosing vertex4 instead produces the reflected ordering. A canonical-labeling procedure must account for such equivalent choices rather than depend on the input vertex names.

This example explains the basic mechanism, not every heuristic in Traces. Piperno and Brendan McKay later described both nauty and Traces within a common framework and compared their behavior on graph families.^[ref]

Brendan McKay is a researcher in computational graph theory and an emeritus professor at the Australian National University. His institutional homepage identifies nauty as software for graph isomorphism and graph automorphisms.^[ref]

A graph automorphism is a relabeling that preserves adjacency within a graph. For an original cycle on four vertices, choose the image of one vertex in4 ways and then choose which of its two neighbors receives the next vertex in2 ways. The remaining images are forced, givingThese relabelings form a group. Computing such symmetries can avoid repeating equivalent branches of a structural search.

Graph canonical labeling addresses a complementary problem: assign a representative encoding so that isomorphic graphs receive the same canonical result. This makes it possible to compare structures whose input vertex names differ or to remove duplicate generated graphs. McKay's work on nauty made these tasks practical for many graph classes.

With Adolfo Piperno, he described the mathematical basis of individualization-refinement graph search and the implementations in nauty and Traces graph isomorphism software. Their paper connects the validity of the search framework with performance comparisons, while distinguishing the practical algorithms from a general worst-case efficiency claim.^[ref]

Colour refinement repeatedly separates vertices of a graph according to the colours of their neighbours. Its colours are labels for classes of vertices with the same currently visible structure; they are not a proper vertex colouring requiring adjacent vertices to differ. In individualization-refinement graph search, colour refinement reduces ambiguity before the algorithm branches.^[ref]

Let $c_t(v)$ be a vertex's colour after round $t$. One conceptual update assigns a common new colour exactly when both the previous colour and neighbour-colour multiset agree:The encoding must give distinct labels to distinct signatures. Retaining $c_t(v)$ prevents old classes from merging. When no class splits, the resulting partition of a set is an equitable partition: vertices in the same cell have equal numbers of neighbours in every cell.

For an original example, start all vertices of the six-vertex path graph $1-2-3-4-5-6$ with the same colour. The first round separates endpoints $\{1,6\}$ from internal vertices $\{2,3,4,5\}$. The next separates $\{2,5\}$, which each have an endpoint neighbour, from $\{3,4\}$, which do not. The three cellsare then stable. Reflection of the path exchanges the two vertices in each cell, so the remaining pairs are compatible with a genuine graph automorphism.

Colour refinement is invariant under vertex relabeling. To compare two graphs, colour signatures must be encoded consistently across both, for example by refining their disjoint union of graphs with shared initial colour meanings. A different count of vertices in a resulting colour class certifies graph non-isomorphism.

Agreement is weaker than isomorphism. Starting with one colour, both the complete bipartite graph $K_{3,3}$ and the triangular prism graph remain one six-vertex cell because every vertex has three neighbours. Yet the prism has triangles and $K_{3,3}$ has none. This failure motivates individualizing vertices and searching further; stable colour classes are not, in general, proof that all their vertices are related by graph automorphisms.

An equitable partition of a finite graph groups vertices so that any two vertices in one cell have the same number of neighbours in each cell. For a simple graph with cells $C_1,\dots ,C_k$, this means that numbersdo not depend on which $v$ in $C_i$ is selected. Here $N(v)$ denotes the set of neighbours of $v$. These counts form the equitable quotient matrix $B=(b_{ij})$. An equitable partition need not be a proper vertex colouring and need not have cells of equal sizes.^[ref]

An original five-vertex path graph $1-2-3-4-5$ has an equitable partitionEach endpoint has one neighbour in $C_2$; each member of $C_2$ has one neighbour in $C_1$ and one in $C_3$; the middle vertex has two neighbours in $C_2$. Although the graph is undirected, $B$ is not symmetric matrix, because its entries count neighbours per vertex rather than total edges between cells. Counting those edges from both ends gives $|C_i|b_{ij}=|C_j|b_{ji}$.

The counts also compress an exact part of the adjacency matrix. Let $A$ be that matrix and let $S$ have one column per cell, with $S_{vi}=1$ for $v\in C_i$ and zero otherwise. ThenIndeed, $(AS{)}_{vj}$ counts neighbours of $v$ in $C_j$, which is exactly $(SB{)}_{vj}$. Hence $Bz=\lambda z$ implies $A(Sz)=\lambda (Sz)$. Since nonempty disjoint cells make the columns of $S$ linearly independent, $z\ne 0$ gives $Sz\ne 0$: every eigenvalue of $B$ is an eigenvalue of $A$. For the displayed example, these include $0$ and $\pm \sqrt{3}$.

An equitable partition preserves neighbour counts, not all adjacency information. The disjoint union of graphs of a triangle and a four-vertex cycle has an equitable one-cell partition, since every vertex has two neighbours. Nevertheless, no graph automorphism can send a triangle vertex to a four-cycle vertex: their connected components of a graph are not isomorphic. This distinguishes equitable cells from symmetry orbits and explains why colour refinement may leave ambiguity.

An equitable quotient matrix records neighbour counts between cells of an equitable partition. For cells $C_1,\dots ,C_k$ of a finite simple graph, its entryis independent of the chosen vertex $v$ within $C_i$. Rows refer to the starting cell; columns refer to the cell containing a neighbour. This is a count per vertex, not the total number of edges between the two cells. Equitability is the property that makes these entries well-defined.^[ref]

For an original example, partition a four-vertex star graph into its centre and its three leaves. ThenThe centre has three leaf neighbours, while each leaf has one centre neighbour. The graph is undirected but its equitable quotient matrix is not a symmetric matrix. If $D=\mathrm{diag}(|C_1|,\dots ,|C_k|)$, counting each edge from both ends givesConsequently $D^{1/2}B{D}^{-1/2}$ is symmetric. For the star it is $\left(\begin{array}{cc}0& \sqrt{3}\\ \sqrt{3}& 0\end{array}\right)$. Thus an equitable quotient matrix of an undirected graph has real eigenvalues, despite its potentially asymmetric appearance.

The relation to the full adjacency matrix $A$ is exact. Let $S_{vi}=1$ when $v\in C_i$, and zero otherwise. Equitability gives $AS=SB$, as proved in equitable partition. Induction then givesSince entries of $A^r$ count occurrences of a walk in a graph between specified endpoints, $(B^r{)}_{ij}$ counts length-$r$ walks from any fixed vertex in $C_i$ to all vertices in $C_j$. In the star example, $B^2=3I$: from a leaf there are three two-step walks ending somewhere in the leaf cell, although only one returns to that particular leaf.

Compression retains the dynamics of vectors constant on each cell. It need not retain every eigenvalue or distinguish all vertices. The star's full adjacency matrix has eigenvalues $\sqrt{3},-\sqrt{3},0,0$, whereas $B$ has only $\sqrt{3},-\sqrt{3}$. Vectors taking leaf values whose sum is zero give the omitted zero-eigenvalue directions. This explains both the utility and the information loss of the quotient.

Individualization-refinement graph search explores possible vertex labelings while repeatedly distinguishing vertices by their adjacency structure. It combines inexpensive colour refinement with branching when refinement leaves indistinguishable vertices. This is a framework for canonical graph labeling and graph automorphism computation, rather than a claim that degree information alone decides graph isomorphism.^[ref]

Start with an ordered partition of a set of the vertex set, representing any prescribed vertex colours. Within each cell, compare the number of neighbours each vertex has in every current cell. Split a cell whenever those count vectors differ, and repeat until no further split occurs. The result is an equitable partition. A discrete partition of a set, with one vertex per cell, gives a candidate vertex ordering.

If a cell still has several vertices, choose a target cell by a rule preserved under relabeling. For each possible chosen vertex in that cell, make that vertex a singleton, refine again and continue recursively. The leaves provide candidate encodings of the adjacency matrix. Choosing a fixed extremal encoding over the complete search gives a canonical representative. Implementations use valid node invariants and discovered graph automorphisms to prune branches without changing the result.^[ref]

For an original example, label a six-vertex cycle graph temporarily as $0,1,\dots ,5$, with adjacency modulo6. Starting with one cell, every vertex has two neighbours, so colour refinement alone leaves one cell. Individualizing vertex0and refining givesVertices1and5remain indistinguishable because reflection fixing0exchanges them. Individualizing one of them resolves the remaining pairs. The temporary names explain the search; they cannot be used as invariant tie-breakers that silently discard the other possible labeling.

By contrast, two disjoint triangles also begin with six vertices of degree2, but after individualizing one vertex the refined cell sizes are1,2,3. The cycle's sizes are1,2,2,1. Thus this branch detects structure that initial degree refinement misses. Highly symmetric graphs can still require extensive search; refinement is a reduction of the search space, not a universal small bound on it.

nauty is software for computing graph automorphisms and canonical graph labeling, originally developed by Brendan McKay. It is distributed with Traces graph isomorphism software and auxiliary graph-generation and manipulation tools.^[ref]

An automorphism result describes relabelings that preserve adjacency. For an original example, the graph with6vertices and no edges permits every vertex permutation, so its automorphism group is the symmetric group $S_6$ of orderA compact generator description can use a transposition $(12)$ and a cycle $(123456)$. Conjugating the transposition by powers of the cycle produces adjacent transpositions, which generate the whole symmetric group. These are illustrative generators, not a claim about the exact generator list returned by a particular run.

A canonical result serves another purpose. If $\mathrm{can}(G)$ denotes the chosen canonical graph encoding, correctness requiresRenaming vertices changes the input representation but must not change that chosen result. This permits duplicate elimination when generating graphs and comparison of structures supplied with unrelated labels.

nauty combines structural refinement with a search over unresolved choices, exploiting discovered graph automorphisms to reduce equivalent work. Its theoretical framework and relationship to Traces are described in the authors' joint paper.^[ref]

A generating set for symmetries and a canonical encoding are different outputs. The first describes equivalences within a graph; the second makes equivalence between independently labeled graphs directly testable.

Traces is software for computing graph automorphisms and canonical graph labeling, developed by Adolfo Piperno and distributed with nauty. A canonical result permits two graphs to be compared without depending on their input vertex names. Traces uses individualization-refinement graph search, with strategies designed to reduce the explored search space.^[ref]

Refinement groups vertices according to structural information, including their numbers of neighbors in existing vertex classes. When this does not distinguish all vertices, individualization temporarily gives a selected vertex its own class and refinement continues. Discovering equivalent choices and distinguishing branches can avoid repeated work; the validity of the framework and implementation strategies are developed with Brendan McKay.^[ref]

An original example shows why a coarse invariant is insufficient. A cycle on6vertices and two separate triangles both have6vertices and every vertex has2neighbors. Starting with one vertex class, neighbor-count refinement leaves one class in both cases. Yet the graphs are not isomorphic: one is connected and the other is not. Their correct canonical graph encodings must therefore differ.

Conversely, two differently numbered copies of the same6-cycle should give the same canonical result when processed with the same canonicalization convention. The example illustrates the required behavior, not a benchmark of a particular Traces version.

Performance depends on the graph family and search strategy. The practical success of the program does not by itself establish a polynomial worst-case bound for graph isomorphism. A reproducible comparison should keep the canonicalization settings consistent rather than assume all programs must choose an identical representative.