グラフ同型問題

ここではJijSolverとJijModelingを用いて、グラフ同型問題を解く方法を説明します。 この問題は、Lucas, 2014, “Ising formulations of many NP problems” 9. Graph Isomorphisms でも触れられています。

グラフ同型問題とは

グラフ同型問題は、2つのグラフ\(G_1, G_2\)が同じ構造を持っているかどうかを判定する問題です。 すなわち、\(N\)個の頂点と辺が同じ数かつ、それらの頂点と辺が同じ配置かどうかを判定します。 詳しく見ていきましょう。 \(1, \dots, N\)のラベルが付けられた頂点を持つグラフ\(G=(V, E)\)に対し、\(N \times N\)の隣接行列\(A\)を次のように定めます。

\[\begin{split} A_{ij} \equiv \begin{cases} 1 & \text{if } (ij) \in E \\ 0 & \text{if } (ij) \notin E \end{cases} \end{split}\]

この辺集合\(E\)について、制約を考えていきましょう。

数理モデル

最初に、グラフ\(G_2\)内の頂点\(v\)がグラフ\(G_1\)の頂点\(i\)にマッピングされるとき1、そうでないとき0となるようなバイナリ変数\(x_{v, i}\)を導入しておきましょう。

制約 1: グラフ間のマッピングは全単射 (一対一対応) でなければならない

2つのグラフ間の全単射マッピングとは、2つのグラフの頂点間が一対一対応でなければならないという意味です。 すなわち、片方のグラフの各頂点は、もう片方のグラフにおける頂点とペアになる必要があります。

\[ \quad \sum_{i}x_{v,i} = 1 \quad (\forall v) \tag{1} \]

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

制約 2: 存在しないマッピング

\(G_1\)には存在しない辺が\(G_2\)に存在する、\(G_1\)に存在する辺が\(G_2\)に存在しない辺があるようなことは、避けなければなりません。

\[ \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} \]

JijModelingによるモデル化

次に、JijModelingを用いた実装を示します。 最初に、上述の数理モデルで必要な変数を定義します。

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)

ここでは、グラフ順序問題と同じ変数を用いています。

制約

次に、制約の式を実装しましょう。

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

Jupyter Notebook上で、実装した数理モデルを表示してみましょう。

problem

\[\begin{split}\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}\end{split}\]

インスタンスの準備

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}

用意したグラフを可視化すると、以下のようになります。

# 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()

JijSolverで解く

jijsolverを用いて、問題を解きましょう。

import jijsolver

interpreter = jm.Interpreter(instance_data)
instance = interpreter.eval_problem(problem)
solution = jijsolver.solve(instance, time_limit_sec=1.0)

解のチェック

最後に、得られた解をチェックしてみましょう。

df = solution.decision_variables
x_indices = df[df["value"]==1]["subscripts"].to_list()
vertices, orders = zip(*x_indices)
print(f'vertex: {vertices}')
print(f'orders: {orders}')

vertex: (0, 1, 2, 3)
orders: (3, 1, 2, 0)

期待通り、JijSolverにより2つのグラフが同型であることが示されました。