Graph canonization¶
The problem of computing a canonical labeled representative shared by every graph in an isomorphism class.
Core Idea¶
Graph canonization is the computational task of assigning every finite graph a canonical labeled representative of its isomorphism class. A canonization function C must return a graph isomorphic to its input and satisfy C(G)=C(H) exactly when G and H are isomorphic. Equivalently, it may output a canonical vertex ordering whose relabeled adjacency representation is invariant under the input's arbitrary names. This is a complete invariant, not merely a heuristic fingerprint that sometimes collides. Canonization immediately decides graph isomorphism by comparing canonical forms, and it supports database deduplication, chemical identifiers, symmetry handling, memoization, and enumeration without repeated isomorphic.
Scope of Application¶
-
Graph isomorphism testing. Canonical forms reduce equality up to relabeling to exact comparison.
-
Chemical identifiers. Molecular graphs receive reproducible serializations when atom, bond, charge, and stereochemical labels are declared structural.
-
Database deduplication. Isomorphic network records can be detected independently of ingestion-specific identifiers.
-
Symmetry-aware memoization. Algorithms reuse results across equivalent states after canonical representation.
-
Exhaustive enumeration. Canonical augmentation or filtering prevents duplicate unlabeled objects.
Clarity¶
Graph canonization requires a deterministic representative shared exactly by all and only isomorphic graphs. This is stronger than producing a hash, a useful fingerprint, or an arbitrary relabeling; collisions among nonisomorphic graphs invalidate a purported complete canonical form. The term separates decision of isomorphism from construction of a canonical labeling while exposing their close relation. The sharper algorithmic question is how refinement, branching, and automorphism handling break symmetry reproducibly without depending on the input's original vertex names.
Manages Complexity¶
Graph canonization compresses every labeling of an unlabeled finite graph to one canonical representative. The analyst computes a partition refinement, branches only on unresolved symmetry, and uses automorphism information to prune equivalent choices. Once canonical form exists, isomorphism testing becomes exact equality and databases can deduplicate without pairwise comparisons among all prior graphs. Easy asymmetric and hard highly symmetric branches explain algorithmic behavior. This compression also supports enumeration and memoization: an entire isomorphism class shares one key, while the requirement of collision-free equivalence distinguishes canonization from heuristic hashing.
Abstract Reasoning¶
Relabeling move. Treat vertex names as incidental and search the graph's isomorphism class for a uniquely selected labeled representative. Partition move. Refine vertices by invariant neighborhoods and branch only where symmetries leave ambiguity. Equivalence move. Compare canonical forms to decide graph isomorphism and recover an isomorphism when they agree. Symmetry move. Use automorphisms to avoid exploring relabelings that are structurally redundant. Boundary move. Canonization is stronger than computing an invariant that merely distinguishes some graphs, and a canonical output depends on a fixed deterministic convention even though it represents label-independent structure.
Knowledge Transfer¶
Within the home domain. Graph canonization transfers across isomorphism testing, chemical structure databases, combinatorics, network deduplication, and symbolic computation whenever an unlabeled graph is mapped deterministically to one labeled representative of its isomorphism class. Relabeling, automorphisms, partitions, invariants, and canonical output retain formal roles. Beyond the home domain (C — algorithmic instrument). It applies literally to any graph class with a specified canonization procedure. Its boundary is exact: a hash or invariant that sometimes collides is not a canonical form, implementation conventions must be fixed, and canonization does not establish semantic equivalence beyond graph isomorphism.
Relationships to Other Abstractions¶
Current abstraction Graph canonization Domain-specific
Parents (1) — more general patterns this builds on
-
Graph canonization presupposes Canonical Form Prime
Graph canonization structurally presupposes Canonical Form rather than being a subtype of it.
Hierarchy path (1) — routes to 1 parentless root
- Graph canonization → Canonical Form → Equivalence Relation
Neighborhood in Abstraction Space¶
Graph canonization sits in a moderately populated region (56th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Graph Structures & Combinatorial Objects (44 abstractions)
Nearest neighbors
- Friendly-index set — 0.87
- Graph Sphericity — 0.86
- Modular product of graphs — 0.86
- List coloring — 0.85
- Planarity — 0.85
Computed from structural-signature embeddings · 2026-10-08