Skip to main content

Graph Isomorphisms problem

Here we show how to solve graph isomorphisms problem using JijZept and JijModeling. This problem is also mentioned in 9. Graph Isomorphisms on Lucas, 2014, "Ising formulations of many NP problems".

What is Graph Isomorphisms Problem?

Graph isomorphism is a concept that describes when two graphs G1G_1 and G2G_2 have the same structure, meaning that they have the same NN number of vertices and edges and that their vertices and edges are arranged in the same way. More carefully: identical graphs are any graph G=(V,E)G = (V, E) with vertices labeled as 1,,N1,\cdots,N and with an N×NN \times N adjacency matrix AA with

Aij{1if (ij)E0if (ij)EA_{ij} \equiv \begin{cases} 1 & \text{if } (ij) \in E \\ 0 & \text{if } (ij) \notin E \end{cases}

which contains all information about the edge set EE.

Mathematical Model

First, we introduce binary variables xv,ix_{v, i} which are 1 if vertex vv in G2G_2 gets mapped to vertex ii in G1G_1 and 0 otherwise.

Constraint 1: the map is bijective

A bijective map between two graphs is a one-to-one correspondence between the vertices of the two graphs, such that each vertex in one graph is paired with a unique vertex in the other graph.

ixv,i=1(v)(1)\quad \sum_{i}x_{v,i} = 1 \quad (\forall v) \tag{1}
vxv,i=1(i)(2)\quad \sum_{v}x_{v,i} = 1 \quad (\forall i) \tag{2}

Constraint 2: no bad mapping exists

An edge that is not in G1G_1 but is in G2G_2, or an edge that is in G1G_1 but is not in G2G_2 should not exist.

ijE1uvE2xu,ixv,j+ijE1uvE2xu,ixv,j=0(3)\quad \sum_{ij \notin E_1}\sum_{uv \in E_2} x_{u,i}x_{v,j}+\sum_{ij \in E_1}\sum_{uv \notin E_2} x_{u,i}x_{v,j} = 0\tag{3}

Modeling by JijModeling

Next, we show an implementation using JijModeling. We first define variables for the mathematical model described above.

import jijmodeling as jm

#define variables
V = jm.Placeholder('V') # number of vertices
E1 = jm.Placeholder('E1', ndim=2) # set of edges
E2 = jm.Placeholder('E2', ndim=2) # set of edges
E1_bar = jm.Placeholder('E1_bar', ndim=2)
E2_bar = jm.Placeholder('E2_bar', ndim=2)

x = jm.BinaryVar('x',shape=(V,V))
i = jm.Element('i', belong_to=(0, V))
j = jm.Element('j', belong_to=(0, V))
u = jm.Element('u', belong_to=(0, V))
v = jm.Element('v', belong_to=(0, V))
e1 = jm.Element('e1', belong_to=E1)
e2 = jm.Element('e2', belong_to=E2)
f1 = jm.Element('f1', belong_to=E1_bar)
f2 = jm.Element('f2', belong_to=E2_bar)

We use the same variables in the graph ordering problem.

Constraint

We implement the constraint equations.

# set problem
problem = jm.Problem('Graph Isomorphisms')
# set constraint
problem += jm.Constraint('const1-1', x[v, :].sum()==1, forall=v)
problem += jm.Constraint('const1-2', x[:, i].sum()==1, forall=i)
const2_1 = jm.sum([f1, e2], x[e2[0],f1[0]]*x[e2[1],f1[1]])
const2_2 = jm.sum([e1, f2], x[f2[0],e1[0]]*x[f2[1],e1[1]])
problem += jm.Constraint('const2', const2_1 + const2_2==0)

Let's display the implemented mathematical model in Jupyter Notebook.

problem

Problem:Graph Isomorphismsmin0s.t.const1-11=0V1xv,1=1v{0,,V1}const1-20=0V1x0,i=1i{0,,V1}const2f1E1bare2E2xe20,f10xe21,f11+e1E1f2E2barxf20,e10xf21,e11=0wherex2-dim binary variable\begin{array}{cccc}\text{Problem:} & \text{Graph Isomorphisms} & & \\& & \min \quad \displaystyle 0 & \\\text{{s.t.}} & & & \\ & \text{const1-1} & \displaystyle \sum_{\ast_{1} = 0}^{V - 1} x_{v, \ast_{1}} = 1 & \forall v \in \left\{0,\ldots,V - 1\right\} \\ & \text{const1-2} & \displaystyle \sum_{\ast_{0} = 0}^{V - 1} x_{\ast_{0}, i} = 1 & \forall i \in \left\{0,\ldots,V - 1\right\} \\ & \text{const2} & \displaystyle \sum_{f1 \in E1_bar} \sum_{e2 \in E2} x_{e2_{0}, f1_{0}} \cdot x_{e2_{1}, f1_{1}} + \sum_{e1 \in E1} \sum_{f2 \in E2_bar} x_{f2_{0}, e1_{0}} \cdot x_{f2_{1}, e1_{1}} = 0 & \\\text{{where}} & & & \\& x & 2\text{-dim binary variable}\\\end{array}

Prepare an instance

We prepare a graph using Networkx.

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt

# First graph
graph1 = [[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]]

# Second graph
graph2 = [[0, 0, 1, 1],
[0, 0, 1, 1],
[1, 1, 0, 0],
[1, 1, 0, 0]]

# Create networkx graphs from adjacency matrices
G1 = nx.from_numpy_array(np.array(graph1))
G2 = nx.from_numpy_array(np.array(graph2))

num_V = G1.number_of_nodes()

edges1 = G1.edges()
inst_E1 = [list(edge) for edge in edges1]

edges2 = G2.edges()
inst_E2 = [list(edge) for edge in edges2]

non_edges1 = list(nx.non_edges(G1))
inst_E1_bar = [list(non_edge) for non_edge in non_edges1]

non_edges2 = list(nx.non_edges(G2))
inst_E2_bar = [list(non_edge) for non_edge in non_edges2]

instance_data = {'V': num_V, 'E1': inst_E1, 'E2': inst_E2, 'E1_bar': inst_E1_bar, 'E2_bar': inst_E2_bar}

The input graphs are shown below.

# Create figure and subplots
fig, axs = plt.subplots(1, 2, figsize=(8, 4))

# Draw graphs
nx.draw(G1, ax=axs[0], with_labels=True)
axs[0].set_title("Graph 1")
nx.draw(G2, ax=axs[1], with_labels=True)
axs[1].set_title("Graph 2")

# Show the plot
plt.show()

png

Solve by JijZept's SA

We solve this problem using JijZept JijSASampler. We also use the parameter search function by setting search=True.

import jijzept as jz

# set sampler
sampler = jz.JijSASampler(config="../../../config.toml")
# solve problem
response = sampler.sample_model(problem, instance_data, multipliers={'const1-1': 0.3, 'const1-2': 0.3, 'const2': 0.3}, num_reads=100, search=True)

Check solution

In the end, we extract the lowest energy solution from the feasible solutions and check it.

# get sampleset
sampleset = response.get_sampleset()
# extract feasible samples
feasible_samples = sampleset.feasibles()
if len(feasible_samples) == 0:
print("No feasible sample found ...")
else:
# get feasible solution from samples
feasible_solution = feasible_samples[0].var_values["x"].values
# get vertex number and order
vertices, orders = zip(*feasible_solution)
print(f'vertex: {vertices}')
print(f'orders: {orders}')
(0, 3) (2, 0) (3, 2) (1, 1)
vertex: (0, 2, 3, 1)
orders: (3, 0, 2, 1)

As we expected, JijZept successfully shows that it is isomorphic.