graph canonization
**Graph Canonization (Canonical Labeling)** is the **process of computing a unique, deterministic string or matrix representation for a graph such that two graphs receive identical canonical forms if and only if they are isomorphic** — solving the fundamental problem of graph identification: given a graph that can be drawn in $N!$ different ways (one for each node permutation), computing a single standardized representation that is independent of the arbitrary node ordering.
**What Is Graph Canonization?**
- **Definition**: A canonical form is a function $ ext{canon}: mathcal{G} o Sigma^*$ that maps graphs to strings with the guarantee: $ ext{canon}(G_1) = ext{canon}(G_2) iff G_1 cong G_2$ (isomorphic). This means every graph has exactly one canonical representation, and isomorphic graphs always receive the same representation, regardless of how their nodes were originally labeled or ordered.
- **Node Ordering Problem**: A graph with $N$ nodes can be represented by $N!$ different adjacency matrices — one for each permutation of the node labels. Without canonization, checking whether a new graph is already in a database requires comparing it against all $N!$ possible representations of each stored graph. Canonical forms reduce this to a single string comparison per stored graph.
- **Canonical Labeling Algorithms**: The standard approach computes a canonical node ordering — a unique permutation $pi^*$ such that the adjacency matrix $A_{pi^*}$ is the lexicographically smallest (or largest) among all $N!$ permutations. The canonical form is then the adjacency matrix under this ordering, serialized to a string.
**Why Graph Canonization Matters**
- **Graph Database Deduplication**: Storing millions of graphs (molecules, circuits, chemical compounds) without duplicates requires a canonical form for $O(1)$ lookup. Without canonization, inserting a new graph requires an isomorphism test against every existing graph — $O(M)$ comparisons for $M$ stored graphs. With canonization, it requires a single hash table lookup on the canonical string.
- **Molecular Representation (SMILES/InChI)**: Canonical SMILES and InChI are canonical string representations for molecular graphs used universally in chemistry. Every molecule receives a unique canonical SMILES string regardless of how the atom numbering was assigned, enabling exact molecular lookup in databases with billions of compounds.
- **Graph Hashing**: Canonical forms enable graph hashing — mapping each graph to a fixed-size hash that can be used for deduplication, indexing, and retrieval. This is essential for large-scale graph mining, where millions of candidate subgraphs must be checked for novelty against previously discovered patterns.
- **GNN Evaluation**: When evaluating GNN generalization, researchers need to ensure that training and test graphs do not contain isomorphic duplicates. Canonical forms provide the definitive deduplication criterion — two graphs are duplicates if and only if their canonical forms match.
**Canonization Tools and Complexity**
| Tool/Algorithm | Approach | Practical Performance |
|---------------|----------|---------------------|
| **nauty (McKay)** | Automorphism group computation | Gold standard, handles > 10,000 nodes |
| **Traces (McKay & Piperno)** | Improved nauty with better heuristics | Faster on sparse graphs |
| **bliss** | Automorphism-based with pruning | Efficient for sparse structured graphs |
| **Canonical SMILES** | String linearization for molecules | Industry standard for chemical databases |
| **InChI** | IUPAC canonical molecular identifier | International chemical identifier standard |
**Graph Canonization** is **unique naming** — computing a single, deterministic identity card for every graph that resolves ambiguity from arbitrary node labeling, enabling exact graph lookup, deduplication, and comparison at the speed of string matching rather than the cost of isomorphism testing.