AI Glossary / Computer vision and multimodal AI / Intermediate

Graph isomorphism

Definition

Graph isomorphism is a one-to-one correspondence between the vertices of two graphs that preserves their connections. Two graphs are isomorphic when they have the same structure after suitable relabeling, even if they are drawn differently or use different vertex names.

What it means

A graph describes entities through vertices and relationships through edges. The layout of a graph drawing is usually not part of its abstract structure. Moving the dots or renaming them does not change which entities are connected.

Isomorphism asks whether two complete connection patterns can be made identical by a consistent relabeling. For directed graphs, edge direction must also be preserved. If labels, types or weights are part of the intended comparison, the correspondence must respect the specified attribute rules.

This is stricter than saying two graphs look similar or share a few statistics. It is also different from checking whether a small pattern occurs inside a larger graph, which is a subgraph-matching question.

How it works

A candidate mapping assigns each vertex of one graph to a distinct vertex of the other. The test checks whether every connection, and absence of a connection where relevant, agrees under that mapping. Additional rules can check vertex and edge attributes.

Algorithms often begin with inexpensive necessary conditions, such as vertex counts, edge counts and degree information. If these disagree, the graphs cannot be isomorphic under the stated model. If they agree, further checking is still needed.

Search methods use structural constraints to reduce the number of possible mappings. Highly symmetric graphs can have several valid isomorphisms, so a returned correspondence need not be unique. The difficulty depends on the graph family and algorithm, not only on the number of vertices.

Three practical examples

1. Data deduplication: A system checks whether two small relationship structures are the same despite different internal identifiers.

2. Pattern analysis: A vision pipeline compares graph descriptions of shapes after defining which junction and edge attributes matter.

3. Software modeling: A team checks whether two dependency diagrams preserve the same structure after a naming change, while deciding whether dependency types must also match.

Think of it this way

Think of two railway maps with different station names and layouts. They describe the same abstract network if every station can be paired so that all track connections correspond.

The analogy ignores distances unless those are explicitly included as attributes. Two structurally identical networks can have very different geographic shapes, travel times or capacities.

Worked example

Graph A has vertices a, b and c, with edges a - b and b - c. Graph B has vertices 10, 20 and 30, with edges 10-30 and 30-20. Map a to 10, b to 30 and c to 20. Both edges are preserved, so these three-vertex paths are isomorphic.

Matching degrees alone is not always enough. A six-vertex cycle and two separate three-vertex cycles both have six vertices, six edges and degree 2 at every vertex. Yet they are not isomorphic because one graph is connected and the other has two components.

These examples use simple undirected graphs without attributes. Adding vertex types or directed edges changes what the mapping must preserve.

Illustrative case study

Fictional case: Alder Systems compares two exported workflow graphs after a database migration. Their identifiers differ, so direct record-by-record equality fails. A structural isomorphism test finds a correspondence between the nodes.

The team then checks task types and edge meanings, discovering that one relationship label changed during export. The graphs match as unlabeled structures but not under the application's full attribute rules. The migration review records that distinction instead of reporting an unconditional match. This scenario illustrates defining the comparison correctly, not a documented software incident.

Common misconceptions and mistakes

Identical drawings are not required. Isomorphism concerns structure, not the positions of vertices on a page.

Equal vertex counts, edge counts or degree sequences do not prove isomorphism. They are useful preliminary checks but can miss structural differences.

A library may ignore attributes unless the caller supplies appropriate matching rules. A positive result can therefore answer a narrower question than intended.

Graph isomorphism is not approximate similarity. If the task permits missing edges, noisy weights or partial correspondence, a more general matching formulation may be appropriate. Also, several valid relabellings can exist for a symmetric structure.

Business use

Isomorphism is useful when identifiers or drawings change but the relationship structure should remain equivalent. It can support duplicate detection, consistency checks and structured-data validation.

Write down exactly what must be preserved: direction, multiplicity, labels, weights and any tolerance rules. Test known positive and negative examples. Report whether the result establishes structural equivalence alone or equivalence of the richer attributed model used by the business.

People also ask

Does relabeling vertices change a graph's structure?

No, provided the connections are relabeled consistently. Isomorphism formalizes that equivalence.

Can two isomorphic graphs have different-looking layouts?

Yes. Layout coordinates are normally separate from abstract connectivity unless explicitly included in the comparison.

Does an isomorphism test find the same correspondence every time?

Not necessarily. Symmetry can allow several valid mappings, and implementation details can affect which is returned.

Check your understanding

Two graphs have the same number of vertices and the same degree sequence. Is that sufficient to declare them isomorphic?

Answer: No. Different connection patterns can share those statistics. A valid one-to-one mapping preserving the complete required structure is still needed, or an algorithm that establishes its existence.

Related terms

• Graph matching
• Subgraph isomorphism
• vertex relabelling
• adjacency matrix
• graph invariant
• automorphism
• attributed graph

Learn next

Relabel a small path or cycle and verify a mapping by checking every edge. Then compare the six-cycle with two triangles to see why degree statistics are insufficient. Finally, add labels and decide which ones your application requires an isomorphism to preserve.

More in Computer vision and multimodal AI

• Gradient reversal - Gradient reversal is an image-processing artifact in which a local brightness change reverses direction after processing: a region that originally became...
• Gram matrix - A Gram matrix records the pairwise inner products of a set of vectors.
• Graph cut optimization - Graph cut optimization solves certain labeling problems by constructing a weighted graph whose cuts correspond to candidate solutions.
• Graph-cut segmentation - Graph-cut segmentation divides an image into labeled regions by constructing a weighted graph and finding a cut that minimizes a defined cost.
• Graph kernel - A graph kernel is a function that compares two graphs in a way suitable for kernel-based learning, typically corresponding to an inner product between their...
• Graph partitioning - Graph partitioning divides a graph's vertices into groups according to a defined objective and constraints.

Sources

Primary documentation: NetworkX, is_isomorphic, https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.isomorphism.is_isomorphic.html . Its attribute-matching behaviour and stated algorithm reference were read. The path mapping and six-cycle comparison are original teaching examples; they do not assert a universal complexity bound or performance guarantee.

Previous: Graph Hashing Next: Graph kernel