Graph Isomorphism Example

Download Notebook

The Graph Isomorphism problem determines whether two graphs are structurally identical, i.e., there exists a bijection between their node sets that preserves edges. Its computational complexity is a major open question in theoretical computer science.

import getpass
import os

import numpy as np
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.graph_isomorphism import (
    GraphIsomorphismCollection,
    GraphIsomorphismData,
    GraphIsomorphismFormulation,
    GraphIsomorphismInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define two 4-node graphs that are structurally identical but with different node labels.

adj1 = np.array(
    [
        [0, 1, 1, 0, 0],
        [1, 0, 1, 1, 0],
        [1, 1, 0, 0, 1],
        [0, 1, 0, 0, 1],
        [0, 0, 1, 1, 0],
    ]
)
adj2 = np.array(
    [
        [0, 1, 0, 1, 1],
        [1, 0, 1, 0, 1],
        [0, 1, 0, 1, 0],
        [1, 0, 1, 0, 0],
        [1, 1, 0, 0, 0],
    ]
)

node_names_1 = [0, 1, 2, 3, 4]
node_names_2 = ["A", "B", "C", "D", "E"]
data = GraphIsomorphismData.from_adjacency_matrices(
    adjacency_matrix_1=adj1,
    adjacency_matrix_2=adj2,
    node_names_1=node_names_1,
    node_names_2=node_names_2,
)
print(data.to_string())

Graph Isomorphism Data:
  Graph 1: 5 nodes, 6 edges
  Graph 2: 5 nodes, 6 edges

Plot Data

Visualize both graphs side by side.

data.plot()

<Axes: title={'center': 'Graph 1'}>

Create Formulation

Set up a node mapping that preserves all edges between the two graphs.

formulation = GraphIsomorphismFormulation()
print(formulation.to_string(data))

Graph Isomorphism Formulation (undirected graphs):
  Graph 1 nodes: 5
  Graph 2 nodes: 5

Decision Variables:
  x[i,j] in {0,1} for all i, j
  x[i,j] = 1 if graph 1 node i maps to graph 2 node j
  Total: 25 binary variables

Objective:
  None (feasibility problem)

Constraints:
  1. Total mapping: 5, (sum_j x[i,j] == 1)
  2. Bijectivity: 5
  3. Edge preservation: 48
  4. Non-edge preservation: 48

Create Instance

Combine data and formulation into a solvable instance.

instance = GraphIsomorphismInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Graph Isomorphism Data:
  Graph 1: 5 nodes, 6 edges
  Graph 2: 5 nodes, 6 edges
Formulation:Graph Isomorphism Formulation (undirected graphs):
  Graph 1 nodes: 5
  Graph 2 nodes: 5

Decision Variables:
  x[i,j] in {0,1} for all i, j
  x[i,j] = 1 if graph 1 node i maps to graph 2 node j
  Total: 25 binary variables

Objective:
  None (feasibility problem)

Constraints:
  1. Total mapping: 5, (sum_j x[i,j] == 1)
  2. Bijectivity: 5
  3. Edge preservation: 48
  4. Non-edge preservation: 48

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

2026-05-29 11:33:36 INFO     Sleeping for 5.0 seconds. Waiting and checking a function in a loop.

2026-05-29 11:33:42 INFO     Sleeping for 10.0 seconds. Waiting and checking a function in a loop.

2026-05-29 11:33:53 INFO     Sleeping for 15.0 seconds. Waiting and checking a function in a loop.

Graph Isomorphism Solution:
  Valid: True
  Mapping:
    0 -> E
    1 -> A
    2 -> B
    3 -> D
    4 -> C

sol

Solution(samples=[[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0]], obj_values=[0], raw_energies=None, counts=[1], constraints=[{nonedge_pres_0_4_0_4: True, nonedge_pres_2_3_0_4: True, g1_node_4: True, nonedge_pres_2_3_1_2: True, nonedge_pres_2_3_3_0: True, edge_pres_0_1_3_4: True, edge_pres_0_1_3_1: True, nonedge_pres_0_3_1_4: True, nonedge_pres_2_3_4_0: True, edge_pres_1_3_3_1: True, edge_pres_2_4_0_2: True, nonedge_pres_1_4_4_0: True, edge_pres_1_3_2_4: True, edge_pres_0_2_4_2: True, nonedge_pres_0_4_1_2: True, g1_node_3: True, g2_node_2: True, edge_pres_1_3_4_2: True, edge_pres_0_1_1_3: True, edge_pres_1_3_0_2: True, edge_pres_2_4_2_4: True, nonedge_pres_0_3_2_3: True, nonedge_pres_1_4_3_0: True, nonedge_pres_1_4_1_2: True, nonedge_pres_0_3_3_2: True, edge_pres_1_2_4_3: True, nonedge_pres_2_3_4_1: True, g1_node_2: True, edge_pres_2_4_3_4: True, edge_pres_0_2_3_1: True, edge_pres_0_1_2_0: True, nonedge_pres_1_4_0_1: True, nonedge_pres_1_4_4_1: True, edge_pres_3_4_2_4: True, edge_pres_1_2_2_0: True, edge_pres_1_2_3_4: True, edge_pres_0_1_4_2: True, edge_pres_0_2_2_4: True, edge_pres_1_2_1_3: True, edge_pres_1_3_1_3: True, edge_pres_2_4_2_0: True, edge_pres_3_4_4_3: True, nonedge_pres_1_4_1_0: True, g2_node_0: True, nonedge_pres_0_3_1_0: True, nonedge_pres_0_3_4_1: True, nonedge_pres_1_4_0_4: True, edge_pres_0_2_0_2: True, edge_pres_1_3_3_4: True, edge_pres_0_2_2_0: True, nonedge_pres_1_4_2_3: True, nonedge_pres_2_3_1_4: True, nonedge_pres_2_3_2_3: True, edge_pres_2_4_3_1: True, nonedge_pres_1_4_1_4: True, nonedge_pres_2_3_2_1: True, edge_pres_2_4_1_3: True, edge_pres_0_2_3_4: True, g2_node_4: True, nonedge_pres_2_3_1_0: True, nonedge_pres_0_4_4_1: True, edge_pres_1_3_2_0: True, g2_node_1: True, g1_node_0: True, g2_node_3: True, nonedge_pres_0_4_0_1: True, nonedge_pres_1_4_3_2: True, nonedge_pres_2_3_3_2: True, edge_pres_0_1_2_4: True, edge_pres_2_4_4_2: True, edge_pres_3_4_3_1: True, nonedge_pres_0_4_4_0: True, nonedge_pres_0_4_2_1: True, nonedge_pres_1_4_2_1: True, edge_pres_1_2_2_4: True, edge_pres_3_4_2_0: True, nonedge_pres_1_4_0_3: True, nonedge_pres_2_3_0_3: True, nonedge_pres_0_3_2_1: True, edge_pres_1_2_3_1: True, edge_pres_0_1_4_3: True, edge_pres_1_3_4_3: True, edge_pres_3_4_3_4: True, nonedge_pres_0_3_3_0: True, nonedge_pres_0_4_1_0: True, nonedge_pres_0_4_3_2: True, nonedge_pres_0_3_0_1: True, nonedge_pres_0_3_4_0: True, g1_node_1: True, edge_pres_3_4_4_2: True, edge_pres_0_2_1_3: True, nonedge_pres_0_4_2_3: True, nonedge_pres_2_3_0_1: True, nonedge_pres_0_4_1_4: True, nonedge_pres_0_4_0_3: True, edge_pres_1_2_0_2: True, nonedge_pres_0_4_3_0: True, edge_pres_2_4_4_3: True, edge_pres_0_2_4_3: True, nonedge_pres_0_3_0_3: True, edge_pres_1_2_4_2: True, edge_pres_0_1_0_2: True, edge_pres_3_4_1_3: True, nonedge_pres_0_3_0_4: True, edge_pres_3_4_0_2: True, nonedge_pres_0_3_1_2: True}], variable_bounds=[[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]], feasible=[True], runtime=0.004899264, n_samples=1, variable_names=[x_1_4, x_0_2, x_2_0, x_4_0, x_0_3, x_1_2, x_4_2, x_2_3, x_4_1, x_3_4, x_4_4, x_2_4, x_3_1, x_1_3, x_0_4, x_0_0, x_2_1, x_1_1, x_4_3, x_3_0, x_3_3, x_1_0, x_3_2, x_0_1, x_2_2], sense=Minimize)

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

(<Axes: title={'center': 'Graph 1'}>, <Axes: title={'center': 'Graph 2'}>)

Collections

Generate a benchmark collection of random instances for batch processing.

collection = GraphIsomorphismCollection.from_random(
    min_nodes=3,
    max_nodes=5,
    num_instances=2,
    seed=42,
)
model = collection.instances[0].formulate()
print(model)

Model: graph_isomorphism<graph_isomorphism>
Minimize

Subject To
  g1_node_0: x_0_0 + x_0_1 + x_0_2 == 1
  g1_node_1: x_1_0 + x_1_1 + x_1_2 == 1
  g1_node_2: x_2_0 + x_2_1 + x_2_2 == 1
  g2_node_0: x_0_0 + x_1_0 + x_2_0 == 1
  g2_node_1: x_0_1 + x_1_1 + x_2_1 == 1
  g2_node_2: x_0_2 + x_1_2 + x_2_2 == 1
Binary
  x_0_0 x_0_1 x_0_2 x_1_0 x_1_1 x_1_2 x_2_0 x_2_1 x_2_2