Skip to content

Largest Mapping of Weighted Common Subgraph (LMWCS) Example

Download Notebook

The Largest Mapping of Weighted Common Subgraph (LMWCS) problem finds a maximum-weight mapping of nodes from a source graph G1 into a target graph G2. Each possible node pair (G1 node → G2 node) has an associated weight, and the goal is to find the injective mapping that maximizes the total weight.

This formulation uses a non-induced subgraph embedding: every edge in G1 must be preserved in G2, but G2 may contain additional edges between mapped nodes that do not exist in G1. As a result, a node that is isolated in G1 can be mapped to a high-degree node in G2, and the solution may look asymmetric when visualized.

Applications include molecular comparison and network alignment.

import getpass
import os

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

from luna_usecases.largest_mapping_of_weighted_common_subgraph import (
    LmwcsCollection,
    LmwcsData,
    LmwcsFormulation,
    LmwcsInstance,
)

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 small graphs (3 and 4 nodes) to find the best weighted node mapping.

adj1 = np.array(
    [
        [0, 1, 1],
        [1, 0, 1],
        [1, 1, 0],
    ]
)
adj2 = np.array(
    [
        [0, 1, 0, 1],
        [1, 0, 1, 0],
        [0, 1, 0, 1],
        [1, 0, 1, 0],
    ]
)
node_names_1 = ["X", "Y", "Z"]
node_names_2 = ["A", "B", "C", "D"]
mapping_weights = np.array(
    [
        [1.0, 1.0, 1.0, 1.0],
        [1.0, 2.5, 1.0, 1.0],
        [1.0, 1.0, 1.0, 2.5],
    ]
)
# Z->D or X-> B mappings are 2.5 times more "worth" than the others,
# but due to the structure of G2 the can not occur both.

data = LmwcsData.from_adjacency_matrices(
    adjacency_matrix_1=adj1,
    adjacency_matrix_2=adj2,
    node_names_1=node_names_1,
    node_names_2=node_names_2,
    mapping_weights=mapping_weights,
)
print(data.to_string())

LMWCS Data:
  Graph 1: 3 nodes, 3 edges
  Graph 2: 4 nodes, 4 edges
  Mapping weights: 3x4 matrix

Plot Data

Visualize both graphs.

data.plot()


<Axes: title={'center': 'LMWCS — G1: 3 nodes, G2: 4 nodes'}>
png

Create Formulation

Maximize the alignment weight of the node mapping between the two graphs.

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

Largest Mapping of Weighted Common Subgraph (LMWCS) Formulation:
  Embedding type: non-induced (G1 -> G2)
  Every edge in G1 must be preserved in G2, but G2 may have
  additional edges between mapped nodes that are absent in G1.
  G1 nodes: 3
  G2 nodes: 4
  G1 edges: 3

Decision Variables:
  x[i,j] in {0,1} for i = 0, ..., 2, j = 0, ..., 3
  x[i,j] = 1 if G1 node i is mapped to G2 node j
  Total: 12 binary variables

Objective:
  maximize sum_{i,j} w[i,j] * x[i,j]

Constraints:
  1. Each G1 node mapped at most once (3 constraints):
     sum_j x[i,j] <= 1  for all i = 0, ..., 2
  2. Each G2 node mapped at most once (4 constraints):
     sum_i x[i,j] <= 1  for all j = 0, ..., 3
  3. Non-induced edge consistency (12 constraints):
     x[i,j] + x[k,m] <= 1  for all edges (i,k) in G1, non-edges (j,m) in G2
     (G2 edges between mapped nodes without a G1 counterpart are allowed)

Create Instance

Combine data and formulation into a solvable instance.

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

Data:LMWCS Data:
  Graph 1: 3 nodes, 3 edges
  Graph 2: 4 nodes, 4 edges
  Mapping weights: 3x4 matrix
Formulation:Largest Mapping of Weighted Common Subgraph (LMWCS) Formulation:
  Embedding type: non-induced (G1 -> G2)
  Every edge in G1 must be preserved in G2, but G2 may have
  additional edges between mapped nodes that are absent in G1.
  G1 nodes: 3
  G2 nodes: 4
  G1 edges: 3

Decision Variables:
  x[i,j] in {0,1} for i = 0, ..., 2, j = 0, ..., 3
  x[i,j] = 1 if G1 node i is mapped to G2 node j
  Total: 12 binary variables

Objective:
  maximize sum_{i,j} w[i,j] * x[i,j]

Constraints:
  1. Each G1 node mapped at most once (3 constraints):
     sum_j x[i,j] <= 1  for all i = 0, ..., 2
  2. Each G2 node mapped at most once (4 constraints):
     sum_i x[i,j] <= 1  for all j = 0, ..., 3
  3. Non-induced edge consistency (12 constraints):
     x[i,j] + x[k,m] <= 1  for all edges (i,k) in G1, non-edges (j,m) in G2
     (G2 edges between mapped nodes without a G1 counterpart are allowed)

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













LMWCS Solution:
  Valid: True
  Mapping: Y→A, Z→D
  Total weight: 3.5000



Plot Solution


Visualize the optimal solution.


uc_solution.plot(data)



<Axes: title={'center': 'LMWCS — G1: 3 nodes, G2: 4 nodes, weight=3.50, valid=True'}>


png


Collections


Generate a benchmark collection of random instances for batch processing.


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



Model: largest_mapping_of_weighted_common_subgraph<largest_mapping_of_weighted_common_subgraph>
Maximize
  1.6505586311222298 * x_0_0 + 1.4129397764413683 * x_0_1
  + 0.6035769399586652 * x_0_2 + 0.5062003420650445 * x_1_0
  + 1.8867119505212668 * x_1_1 + 1.4149348729303632 * x_1_2
  + 1.9390062678609665 * x_2_0 + 0.8995298457518976 * x_2_1
  + 0.7780680225708749 * x_2_2
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