Skip to content

Induced Subgraph Isomorphism Example

Download Notebook

The Subgraph Isomorphism problem determines whether a smaller pattern graph can be found within a larger target graph. The induced variant requires preserving both edges and non-edges. It is NP-complete and used in pattern recognition and cheminformatics.

import getpass
import os

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

from luna_usecases.induced_subgraph_isomorphism import (
    InducedSubgraphIsomorphismCollection,
    InducedSubgraphIsomorphismData,
    InducedSubgraphIsomorphismFormulation,
    InducedSubgraphIsomorphismInstance,
)

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 a 3-node triangle pattern and a 5-node target graph. Induced means both edges and non-edges must match.

adj_pattern = np.array(
    [
        [0, 1, 0],
        [1, 0, 1],
        [0, 1, 0],
    ]
)

# Target:
# Nodes 0-2: clean path (valid induced)
# Nodes 3-5: triangle (extra edge breaks induced)
adj_target = np.array(
    [
        [0, 0, 1, 0, 0, 0],
        [0, 0, 1, 0, 0, 0],
        [1, 1, 0, 0, 0, 0],
        [0, 0, 0, 0, 1, 1],
        [0, 0, 0, 1, 0, 1],
        [0, 0, 0, 1, 1, 0],
    ]
)
node_names_pattern = ["P1", "P2", "P3"]
node_names_target = ["A", "B", "C", "D", "E", "F"]
data = InducedSubgraphIsomorphismData.from_adjacency_matrices(
    adjacency_matrix_pattern=adj_pattern,
    adjacency_matrix_target=adj_target,
    node_names_pattern=node_names_pattern,
    node_names_target=node_names_target,
)
print(data.to_string())

Induced Subgraph Isomorphism Data:
  Pattern: 3 nodes, 2 edges
  Target: 6 nodes, 5 edges

Plot Data

Visualize the pattern and target graphs.

data.plot()


(<Axes: title={'center': 'Pattern'}>, <Axes: title={'center': 'Target'}>)
png

Create Formulation

Find a mapping preserving both edges and non-edges between pattern and target.

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

Induced Subgraph Isomorphism Formulation (undirected graphs):
  Pattern nodes: 3, Target nodes: 6

Decision Variables:
  x[i,j] in {0,1} for all i, j
  Total: 18 binary variables

Objective:
  None (feasibility problem)

Constraints:
  1. Node assignment: 3
  2. Injectivity: 6
  3. Edge preservation: 40
  4. Non-edge preservation: 10

Create Instance

Combine data and formulation into a solvable instance.

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

Data:Induced Subgraph Isomorphism Data:
  Pattern: 3 nodes, 2 edges
  Target: 6 nodes, 5 edges
Formulation:Induced Subgraph Isomorphism Formulation (undirected graphs):
  Pattern nodes: 3, Target nodes: 6

Decision Variables:
  x[i,j] in {0,1} for all i, j
  Total: 18 binary variables

Objective:
  None (feasibility problem)

Constraints:
  1. Node assignment: 3
  2. Injectivity: 6
  3. Edge preservation: 40
  4. Non-edge preservation: 10

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')













Induced Subgraph Isomorphism Solution:
  Valid: True
  Mapping: {'P1': 'B', 'P2': 'C', 'P3': 'A'}



Plot Solution


Visualize the optimal solution.


uc_solution.plot(data)



<Axes: title={'center': 'Induced Subgraph Isomorphism — valid=True'}>


png


Collections


Generate a benchmark collection of random instances for batch processing.


collection = InducedSubgraphIsomorphismCollection.from_random(
    min_pattern=3,
    max_pattern=5,
    num_instances=2,
    seed=42,
)
model = collection.instances[0].formulate()
print(model)



Model: induced_subgraph_isomorphism<induced_subgraph_isomorphism>
Minimize

Subject To
  pattern_node_0: x_0_0 + x_0_1 + x_0_2 + x_0_3 + x_0_4 == 1
  pattern_node_1: x_1_0 + x_1_1 + x_1_2 + x_1_3 + x_1_4 == 1
  pattern_node_2: x_2_0 + x_2_1 + x_2_2 + x_2_3 + x_2_4 == 1
  target_node_0: x_0_0 + x_1_0 + x_2_0 <= 1
  target_node_1: x_0_1 + x_1_1 + x_2_1 <= 1
  target_node_2: x_0_2 + x_1_2 + x_2_2 <= 1
  target_node_3: x_0_3 + x_1_3 + x_2_3 <= 1
  target_node_4: x_0_4 + x_1_4 + x_2_4 <= 1
  edge_pres_0_1_0_3_1: x_0_0 + x_1_3 <= 1
  edge_pres_0_1_0_3_2: x_0_3 + x_1_0 <= 1
  edge_pres_0_1_0_4_1: x_0_0 + x_1_4 <= 1
  edge_pres_0_1_0_4_2: x_0_4 + x_1_0 <= 1
  edge_pres_0_1_2_3_1: x_0_2 + x_1_3 <= 1
  edge_pres_0_1_2_3_2: x_0_3 + x_1_2 <= 1
  edge_pres_0_1_2_4_1: x_0_2 + x_1_4 <= 1
  edge_pres_0_1_2_4_2: x_0_4 + x_1_2 <= 1
  edge_pres_0_1_3_4_1: x_0_3 + x_1_4 <= 1
  edge_pres_0_1_3_4_2: x_0_4 + x_1_3 <= 1
  edge_pres_0_2_0_3_1: x_0_0 + x_2_3 <= 1
  edge_pres_0_2_0_3_2: x_0_3 + x_2_0 <= 1
  edge_pres_0_2_0_4_1: x_0_0 + x_2_4 <= 1
  edge_pres_0_2_0_4_2: x_0_4 + x_2_0 <= 1
  edge_pres_0_2_2_3_1: x_0_2 + x_2_3 <= 1
  edge_pres_0_2_2_3_2: x_0_3 + x_2_2 <= 1
  edge_pres_0_2_2_4_1: x_0_2 + x_2_4 <= 1
  edge_pres_0_2_2_4_2: x_0_4 + x_2_2 <= 1
  edge_pres_0_2_3_4_1: x_0_3 + x_2_4 <= 1
  edge_pres_0_2_3_4_2: x_0_4 + x_2_3 <= 1
  edge_pres_1_2_0_3_1: x_1_0 + x_2_3 <= 1
  edge_pres_1_2_0_3_2: x_1_3 + x_2_0 <= 1
  edge_pres_1_2_0_4_1: x_1_0 + x_2_4 <= 1
  edge_pres_1_2_0_4_2: x_1_4 + x_2_0 <= 1
  edge_pres_1_2_2_3_1: x_1_2 + x_2_3 <= 1
  edge_pres_1_2_2_3_2: x_1_3 + x_2_2 <= 1
  edge_pres_1_2_2_4_1: x_1_2 + x_2_4 <= 1
  edge_pres_1_2_2_4_2: x_1_4 + x_2_2 <= 1
  edge_pres_1_2_3_4_1: x_1_3 + x_2_4 <= 1
  edge_pres_1_2_3_4_2: x_1_4 + x_2_3 <= 1
Binary
  x_0_0 x_0_1 x_0_2 x_0_3 x_0_4 x_1_0 x_1_1 x_1_2 x_1_3 x_1_4 x_2_0 x_2_1 x_2_2
  x_2_3 x_2_4