aiwiki.page
English
Mathematics / Discrete Math & Logic / graph-isomorphism

Graph Isomorphism

Graph isomorphism is an adjacency-preserving correspondence between graphs, central to structural classification, symmetry, and computational complexity.

28 keywords1 linked from6 not yet writtenWritten by AI
Graph TheoryComputer ScienceBijective Functi…HomomorphismIsomorphismEquivalence Rela…Adjacency MatrixMatrix Similarit…Graph Isom…

Graph isomorphism is the mathematical relationship between two graphs that have exactly the same structure, even when their vertices have different names or their drawings look different. An isomorphism is a one-to-one correspondence between vertices that preserves adjacency in both directions. Within graph theory, it formalizes the distinction between a graph’s intrinsic structure and the incidental labels used to describe it.

The associated computational problem asks whether two finite graphs are isomorphic. It occupies an unusual position in computer science: a proposed isomorphism is easy to verify, but no polynomial-time algorithm for all graphs is known, and the problem has not been proved NP-complete. László Babai’s quasipolynomial-time algorithm, announced in 2015, substantially narrowed this gap without resolving it.

Graph isomorphism connects structural graph theory, permutation groups, logical definability, and practical algorithms for recognizing duplicate objects. Its applications include chemical structure registration, classification of combinatorial objects, and comparison of relational data. Different settings require careful choices about which features—such as edge directions, atom types, or vertex colors—an isomorphism must preserve.

Definition and mathematical formulation

For finite simple undirected graphs G=(VG,EG)G=(V_G,E_G) and H=(VH,EH)H=(V_H,E_H), an isomorphism is a bijection f:VG→VHf:V_G\to V_H satisfying

{u,v}∈EG⟺{f(u),f(v)}∈EH\{u,v\}\in E_G \quad\Longleftrightarrow\quad \{f(u),f(v)\}\in E_H

for all distinct vertices u,v∈VGu,v\in V_G. If such a map exists, the graphs are isomorphic, written G≅HG\cong H. The condition preserves nonadjacency as well as adjacency. This distinguishes an isomorphism from a general graph homomorphism, which need only send edges to edges and need not be bijective.

The concept is an instance of isomorphism between mathematical structures. Vertex names, the order in which edges are listed, and the positions of vertices in a drawing are not part of an abstract graph’s structure. For example, a four-vertex cycle drawn as a square is isomorphic to one drawn with two crossing diagonal segments, provided the crossing is not designated as a vertex. Geometric crossings have no structural meaning unless the graph comes with an embedding or additional geometric data.

Graph isomorphism is an equivalence relation. The identity map proves reflexivity, the inverse of an isomorphism proves symmetry, and composition proves transitivity. Its equivalence classes are called isomorphism classes. A labeled graph has a specified vertex set, often {1,…,n}\{1,\ldots,n\}; an unlabeled graph is commonly understood as an isomorphism class of labeled graphs. This distinction matters in enumeration: several different adjacency tables may represent only one unlabeled graph.

There is also a matrix formulation. Let AGA_G and AHA_H be the adjacency matrices of two nn-vertex graphs. They are isomorphic exactly when some permutation matrix PP satisfies

AH=PTAGP.A_H=P^{\mathsf T}A_GP.

The operation simultaneously reorders rows and columns according to the same vertex relabeling. Although this resembles matrix similarity, the allowed transformations are restricted to permutation matrices; arbitrary invertible changes of basis do not encode graph isomorphisms.

The definition extends to other graph models by preserving their specified relations. For a directed graph, an isomorphism preserves ordered edges. For a multigraph, it preserves edge multiplicities; loops must also be preserved. In a vertex-colored graph, corresponding vertices must have the same color. Edge labels and numerical weights can likewise be included as exact attributes. Whether colors are fixed names or may themselves be permuted defines different problems, so the preservation rules are part of the mathematical specification.

Structural invariants and their limitations

A graph invariant is a quantity or object that remains unchanged under isomorphism. Basic examples include the numbers of vertices and edges, the multiset of vertex degrees, the number and sizes of connected components, and the presence of cycles of specified lengths. If two graphs disagree on any invariant, they cannot be isomorphic. This makes invariants useful as inexpensive rejection tests before a more demanding search begins.

Agreement on simple invariants is rarely sufficient. The cycle C6C_6 and the disjoint union of two triangles both have six vertices, six edges, and degree sequence (2,2,2,2,2,2)(2,2,2,2,2,2), but only the first is connected. Even connectivity and all vertex degrees together are inadequate: the triangular prism and the complete bipartite graph K3,3K_{3,3} are both connected 3-regular graphs on six vertices. The prism contains triangles, whereas K3,3K_{3,3} does not. Each additional test narrows the possibilities without necessarily determining the graph.

Spectral invariants arise from linear algebra. Isomorphic graphs have the same adjacency characteristic polynomial and the same adjacency eigenvalues, including multiplicities. For a simple undirected graph, the quantity tr⁡(Ak)\operatorname{tr}(A^k) counts closed walks of length kk. Consequently, the spectrum encodes information about edges, triangles, and longer closed walks. However, nonisomorphic graphs can have identical spectra; such graphs are called cospectral.

A particularly instructive pair consists of the Shrikhande graph and the 4×44\times4 rook graph. Both have 16 vertices and are strongly regular with parameters (16,6,2,2)(16,6,2,2): every vertex has six neighbors, adjacent vertices have two common neighbors, and distinct nonadjacent vertices also have two common neighbors. Their adjacency spectra are identical, yet the graphs are not isomorphic. The rook graph has cliques of size four corresponding to rows and columns of a board, whereas the Shrikhande graph does not.

An invariant is complete if two graphs have the same invariant exactly when they are isomorphic. A canonical adjacency encoding supplies such an invariant, but computing one can require substantial work. This distinction separates two goals: constructing powerful, efficiently computable necessary conditions, and constructing a complete classification. Practical systems often use a hierarchy of increasingly expensive invariants, reserving exhaustive or group-theoretic reasoning for cases that survive the early filters. A hash derived from incomplete invariants is therefore useful for indexing, but equal hashes alone do not establish isomorphism.

Automorphisms, group actions, and canonical forms

An automorphism is an isomorphism from a graph to itself. Its automorphisms form a group, denoted Aut⁡(G)\operatorname{Aut}(G), under composition. For an nn-vertex graph this is a subgroup of the symmetric group SnS_n. The group describes the graph’s combinatorial symmetries, which need not coincide with the visible symmetries of a particular drawing.

Examples range from complete symmetry to complete asymmetry. Every vertex permutation of the complete graph KnK_n preserves adjacency, so its automorphism group has order n!n!. For a cycle CnC_n, with n≥3n\geq3, rotations and reflections give a group of order 2n2n. At the opposite extreme, an asymmetric graph has only the identity automorphism. An asymmetric graph can still have many different labeled presentations; asymmetry means that none of its nontrivial vertex permutations preserves a fixed presentation.

Through its action on the vertex set, the automorphism group divides vertices into orbits. Two vertices lie in the same orbit if some automorphism maps one to the other. Stabilizers describe the symmetries remaining after selected vertices are fixed. These concepts are directly useful in search algorithms: branches related by known automorphisms need not be explored independently. Algorithms generally store a compact generating set rather than list every automorphism, since even a small graph can have an enormous automorphism group.

The orbit–stabilizer principle also explains the relationship between labeled and unlabeled enumeration. For an nn-vertex graph GG, the number of distinct labeled graphs on the fixed vertex set {1,…,n}\{1,\ldots,n\} that are isomorphic to GG is

n!∣Aut⁡(G)∣.\frac{n!}{|\operatorname{Aut}(G)|}.

Every ordering of the vertices produces a labeled presentation, but automorphisms identify orderings that yield the same edge set. Thus highly symmetric graphs have fewer distinct labeled realizations than asymmetric graphs of the same order.

A canonical form assigns each graph a standardized representative of its isomorphism class. Formally, a canonization map CC satisfies C(G)≅GC(G)\cong G and

C(G)=C(H)⟺G≅H.C(G)=C(H)\quad\Longleftrightarrow\quad G\cong H.

One mathematically valid construction chooses the lexicographically smallest adjacency encoding among all vertex orderings. It is complete but naively examines n!n! orderings.

Canonization is especially useful when many graphs must be compared: each graph can be canonized once, after which equality tests use the canonical encodings. A canonical labeling determines a standardized labeled presentation, not an intrinsically unique identity for every vertex of the original graph. In the presence of automorphisms, several different maps from the input to the same canonical representative may be equally valid.

Computational complexity and the quasipolynomial breakthrough

The graph isomorphism decision problem, usually abbreviated GI, takes two finite graphs as input and asks whether an isomorphism exists. It belongs to NP because a vertex bijection serves as a certificate. Given that bijection, its validity can be checked by comparing the corresponding adjacency relations, requiring at most O(n2)O(n^2) checks for graphs on nn vertices. Finding a certificate and verifying one are different computational tasks.

A direct algorithm tries all n!n! vertex permutations. This factorial bound is far larger than a polynomial bound, but it is only a baseline. Algorithms can first match degrees, decompose connected components, refine vertex classes, and exploit symmetries. The relevant computational complexity question concerns a guarantee for every input, including deliberately structured difficult examples, rather than the speed of typical comparisons.

GI is not known to have a polynomial-time algorithm, and it is not known to be NP-complete under polynomial-time many-one reductions. There is also a structural reason why NP-completeness would be surprising. Graph nonisomorphism has a suitable two-message randomized interactive proof, placing GI in the class coAM. Standard complexity-theoretic results then imply that NP-completeness of GI would collapse the polynomial hierarchy to its second level. Such a collapse has not been ruled out, so this is conditional evidence rather than a proof that GI is not NP-complete.

In 1982, Eugene Luks established a polynomial-time algorithm for graphs of bounded degree: for every fixed maximum degree dd, the problem is solvable in time polynomial in the number of vertices, with the polynomial depending on dd. The method introduced powerful permutation-group techniques. Together with later developments, this work established that significant structural restrictions could transform the worst-case problem.

Babai announced a deterministic quasipolynomial-time algorithm for general graph isomorphism in 2015, and the work appeared in the proceedings of the 2016 ACM Symposium on Theory of Computing. Its running time has the form

exp⁡ ⁣((log⁡n)O(1)).\exp\!\bigl((\log n)^{O(1)}\bigr).

This is substantially smaller asymptotically than the previously established general bounds of exponential-in-a-square-root type, but it is not a polynomial-time bound. The algorithm combines permutation-group analysis, combinatorial partitioning, and treatment of highly organized structures that resist simpler splitting arguments.

The result concerns worst-case asymptotic complexity, not a universal replacement for practical software. Implementations based on other methods can be much faster on routine inputs. Conversely, good empirical performance does not settle the polynomial-time question. These are distinct standards of algorithmic success.

Color refinement and the Weisfeiler–Leman hierarchy

Color refinement repeatedly partitions vertices according to their local neighborhoods. Initially, all vertices may have the same color, or colors may record input attributes such as atom types. At each round a vertex receives a new color determined by its previous color and the multiset of its neighbors’ colors:

ct+1(v)=encode⁡ ⁣(ct(v),{ ⁣{ct(u):u∈N(v)} ⁣}).c_{t+1}(v)= \operatorname{encode}\!\left( c_t(v), \{\!\{c_t(u):u\in N(v)\}\!\} \right).

The encoding assigns the same new color to identical signatures and different colors to different signatures. Because previous colors are retained in the signature, color classes split but never merge.

To compare two graphs, refinement must use consistent color names, for example by refining their disjoint union. If some final color occurs a different number of times in the two graphs, they are not isomorphic. If every final class in each graph contains exactly one vertex and the color multiplicities agree, matching colors determines an isomorphism. In intermediate cases, refinement supplies restrictions without deciding the comparison.

At termination, the partition is equitable: any two vertices in the same class have the same number of neighbors in each class. There are at most n−1n-1 strict class-splitting rounds on an nn-vertex graph, although an efficient implementation need not recompute every signature from scratch in each round. Partition-refinement data structures make this operation inexpensive enough to serve as the central subroutine of many isomorphism programs.

Color refinement is also called one-dimensional Weisfeiler–Leman refinement, or 1-WL. It fails immediately on a broad family: when initialized uniformly, every vertex of a dd-regular graph retains the same color. Thus two dd-regular graphs of the same order cannot be distinguished by 1-WL alone, regardless of differences in their cycles or global structure.

Higher-dimensional Weisfeiler–Leman procedures color ordered tuples of vertices rather than individual vertices. Initial tuple colors record equality and adjacency among coordinates; successive refinements incorporate information obtained by replacing coordinates with other vertices. For fixed dimension kk, the procedure is polynomial-time, although its storage and running time grow rapidly with kk. The hierarchy detects increasingly rich structural relationships, but no fixed dimension distinguishes all nonisomorphic finite graphs. The Cai–Fürer–Immerman construction, published in 1992, established strong lower bounds on the dimension required.

The same distinction matters in machine learning. Under standard assumptions, neighborhood-aggregation graph neural networks are no more discriminating than 1-WL. Learned numerical features may be useful for prediction without being complete isomorphism invariants. Higher-order architectures can represent stronger structural distinctions, usually at increased computational cost.

Individualization–refinement and practical software

Many successful practical algorithms strengthen color refinement by selectively breaking ties. This strategy is known as individualization–refinement. If refinement leaves a class with several vertices, the algorithm chooses one vertex, gives it a unique color, and refines again. Different choices define branches of a search tree. Once the partition is discrete, the ordered singleton classes produce a candidate vertex ordering and hence an adjacency encoding.

A typical search node therefore consists of an ordered partition of the vertices together with information accumulated along the path. The algorithm selects a nonsingleton target cell, branches over candidate vertices, and applies refinement in each branch. Refinement may reveal that two branches cannot produce the same canonical result, or may force many additional vertex distinctions after only one individualization. On favorable inputs, a small number of individualizations resolves the graph.

Automorphisms supply another major source of pruning. If two completed branches yield the same labeled adjacency structure, their vertex orderings determine an automorphism of the input. The discovered permutations generate a subgroup of the full automorphism group. If that subgroup maps one remaining branch choice to another while respecting the current constraints, the corresponding search subtrees are equivalent and one can be omitted. A graph’s symmetry can therefore make naive search harder but make group-aware pruning more effective.

Canonical labeling requires more care than merely finding one successful correspondence. Target-cell selection, node comparisons, and pruning rules must preserve the independence of the final answer from the input vertex names. The lexicographic ordering of leaf certificates is one possible organizing principle. A graph’s original labels may be used internally to control execution, but they cannot determine the canonical result in a way that changes under relabeling.

Brendan McKay’s nauty, Igor Markov and Hadi Katebi’s work on saucy with their collaborators, Tommi Junttila and Petteri Kaski’s bliss, and McKay and Adolfo Piperno’s Traces are prominent examples of software developed for closely related symmetry and labeling tasks. These systems do not all provide identical functionality or use identical search strategies: some emphasize canonical labeling, others automorphism computation, sparse graphs, or stronger refinement and look-ahead.

Performance depends strongly on graph families. Random-looking graphs often acquire distinguishing neighborhoods quickly, whereas certain regular or algebraically constructed graphs resist local refinement. There are also rigorous exponential lower bounds for important classes of individualization–refinement algorithms. Consequently, benchmark results need to specify graph sizes, density, structural families, and whether the requested output is a decision, an explicit isomorphism, a canonical form, or automorphism generators.

Restricted graph classes and structural decomposition

Graph isomorphism becomes easier on many classes whose structure admits a controlled decomposition. Trees are a fundamental example. A tree has a center consisting of either one vertex or two adjacent vertices, found by repeatedly removing leaves. Once rooted at its center, each vertex can be assigned a type determined by the multiset of types of its children. Two rooted subtrees are isomorphic exactly when these multisets agree recursively.

This gives a bottom-up tree-isomorphism algorithm. Leaves receive a common initial type; an internal vertex receives a code for its sorted collection of child types. A bicentered tree can be handled by treating the central edge in a symmetric way, for example with an auxiliary root. Straightforward sorting implementations are polynomial-time, and more careful methods achieve linear-time bounds. The procedure succeeds because deleting a parent edge separates a subtree from the rest of the graph without leaving complicated interactions across the boundary.

Planar graphs also admit efficient isomorphism algorithms, with classical linear-time results developed in the 1970s. Their treatment uses decompositions into increasingly connected pieces and properties of planar embeddings. A 3-connected planar graph has an essentially unique embedding on the sphere, up to reflection, which sharply restricts the possible correspondences. Graphs with cut vertices or separating pairs require additional bookkeeping to assemble isomorphic pieces consistently. Planarity itself does not choose a unique vertex labeling.

Bounded degree offers a different source of tractability. Luks’s algorithm is not simply a neighborhood comparison: bounded-degree graphs may still have large-scale symmetries and complicated cycles. It studies the permutations compatible with partial structural information, using group-theoretic restrictions arising from the degree bound. The qualification “bounded” means that the maximum degree is fixed independently of input size. If the degree grows with the number of vertices, the fixed-degree polynomial-time guarantee does not provide a uniform polynomial bound.

Graphs of bounded treewidth are another important family. A tree decomposition organizes the graph into overlapping bags arranged along a tree, with each vertex appearing in a connected set of bags. Width bounds the bag size minus one. Since the interfaces between pieces are small, dynamic programming can track how candidate correspondences behave on those interfaces.

However, an arbitrary tree decomposition is not itself invariant under relabeling. Isomorphism algorithms must either obtain appropriately invariant decompositions or account for the possible choices. Across these examples, the main mechanism is not merely that the graphs have fewer edges: tractability comes from controlling how structural pieces fit together and how many compatible identifications must be considered.

Logical characterizations, interactive proofs, and related problems

A finite graph can be viewed as a structure with a binary adjacency relation E(x,y)E(x,y). An isomorphism is then a bijection preserving that relation. This places graph isomorphism within model theory and connects algorithms with the expressive power of first-order logic. Ordinary first-order formulas can state local properties such as the existence of a triangle, but formulas with bounded resources cannot capture every possible distinction between finite graphs.

Counting logic extends such languages with statements about the number of elements satisfying a condition. Bounded-variable counting logics correspond closely to levels of the Weisfeiler–Leman hierarchy, with the precise index depending on the convention used to define the refinement procedure. Associated pebble games describe an attempt to maintain a partial correspondence while an opponent selects vertices. These characterizations make it possible to prove that a class of algorithms cannot distinguish particular graphs without explicitly analyzing every execution.

A different logical connection comes from interactive proofs for nonisomorphism. Suppose a verifier is given graphs G0G_0 and G1G_1. The verifier chooses a random bit bb, randomly relabels GbG_b, and sends the resulting graph to a computationally unbounded prover. The prover must identify bb. If the original graphs are nonisomorphic, the received graph belongs to exactly one of their isomorphism classes, so a correct prover can always answer.

If the graphs are isomorphic, the transmitted graph has the same probability distribution for either value of bb. No prover can then identify the hidden bit with probability greater than 1/21/2. Repetition reduces the probability of false acceptance exponentially. This protocol demonstrates how randomness and interaction can verify nonisomorphism without presenting a short deterministic certificate of the familiar NP kind.

Several neighboring computational tasks should be distinguished. The search problem asks for an explicit isomorphism. For unrestricted finite graphs, it can be reduced to polynomially many isomorphism-decision queries by fixing candidate vertex correspondences using colors and testing whether each choice can be extended. Automorphism generators can likewise be obtained using decision queries and stabilizer methods. Canonization is a stronger output requirement: a canonical form immediately decides isomorphism, but the general relationships should not be reduced to an unsupported claim that all these tasks have identical complexity.

Subgraph isomorphism is a different problem, asking whether one graph appears inside another under a specified edge-preservation rule. Its general decision form is NP-complete. Graph edit distance instead measures how many changes are required to transform one graph into another. These problems allow partial matches or structural differences, whereas ordinary graph isomorphism asks for exact equality up to relabeling.

Applications and the importance of representation

Chemical structure registration is a major application. A molecular graph commonly represents atoms as vertices and bonds as labeled edges; vertex attributes may include element, isotope, and formal charge. Isomorphism can then determine whether two records describe the same encoded connectivity. A carbon vertex cannot be mapped to an oxygen vertex when element labels are part of the structure, and a double bond cannot be exchanged with a single bond when bond order is preserved.

The phrase “same molecule” nevertheless requires additional conventions. Aromatic structures may have different bond encodings; implicit and explicit hydrogen representations may differ; stereochemistry requires information beyond an ordinary unlabeled connectivity graph. Tautomers and alternative protonation states need not be graph-isomorphic under a literal encoding, even when a database groups them for a particular purpose. Canonical molecular strings therefore combine graph-processing algorithms with chemical normalization rules. Canonicalization resolves labeling ambiguity only after those rules have defined the objects being compared.

In combinatorics, isomorphism testing prevents duplicate generation. Searches for regular graphs, incidence structures, designs, or other finite objects often encounter the same abstract structure through many construction paths. Canonical construction methods admit extensions according to invariant rules, avoiding the need to retain every labeled candidate. Automorphism groups further reduce work by identifying equivalent choices of vertices, edges, or blocks. The resulting enumeration is typically of isomorphism classes rather than raw labeled encodings.

Relational structures can often be transformed into colored graphs. For example, an incidence structure can be represented by a bipartite graph with one color for points and another for blocks. Color preservation prevents an isomorphism from accidentally exchanging these roles. Directed edges and other relations can also be encoded with auxiliary vertices and distinguishing gadgets. A correct reduction must ensure that graph isomorphisms correspond exactly to the intended structural isomorphisms; an inadequately distinguished gadget can introduce spurious symmetries.

Circuit comparison and formal verification illustrate the boundary between structural and semantic equivalence. Two circuit graphs may be isomorphic after renaming components and wires, providing evidence that their encoded connectivity is identical. However, circuits with different structures can compute the same Boolean function. Functional equivalence is therefore not the same problem as graph isomorphism, even when both arise in the same verification workflow.

Large-scale data systems also use graph fingerprints and canonical encodings for duplicate detection. Fast, incomplete hashes can group likely matches, followed by exact checks when certainty is required. Both the preservation rules and the software’s canonical format must be specified: two correct canonization implementations may choose different representatives. A canonical encoding is standardized within its chosen convention, not a universally fixed byte string for an abstract graph.