html
Note
Go to the end <sphx_glr_download_auto_examples_2.seeded_graph_matching_plot_seed_graph_match_jittor.py>
to download the full example code
sphx-glr-example-title
Seeded graph matching means some partial of the matching result is already known, and the known matching results are called "seeds". In this example, we show how to exploit such prior with pygmtools
.
Note
How to perform seeded graph matching is still an open research problem. In this example, we show a simple yet effective approach that works with pygmtools
.
Note
The following solvers are included in this example:
~pygmtools.classic_solvers.rrwm
(classic solver)~pygmtools.classic_solvers.ipfp
(classic solver)~pygmtools.classic_solvers.sm
(classic solver)~pygmtools.neural_solvers.ngm
(neural network solver)
import jittor as jt # jittor backend
import pygmtools as pygm
import matplotlib.pyplot as plt # for plotting
from matplotlib.patches import ConnectionPatch # for plotting matching result
import networkx as nx # for plotting graphs
pygm.set_backend('jittor') # set default backend for pygmtools
_ = jt.set_seed(1) # fix random seed
In this example, we assume the first three nodes are already aligned. Firstly, we generate the seed matching matrix:
Then we generate the isomorphic graphs:
X_gt = seed_mat.clone()
X_gt[jt.arange(num_seeds, num_nodes), jt.arange(num_seeds, num_nodes)[jt.randperm(num_nodes-num_seeds)]] = 1
A1 = jt.rand(num_nodes, num_nodes)
A1 = (A1 + A1.t() > 1.) * (A1 + A1.t()) / 2
A1[jt.arange(A1.shape[0]), jt.arange(A1.shape[0])] = 0
A2 = jt.matmul(jt.matmul(X_gt.t(), A1), X_gt)
n1 = jt.Var([num_nodes])
n2 = jt.Var([num_nodes])
The seed matching matrix:
/auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_jittor_001.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x7fda50d6abf0>
The blue lines denote the matching seeds.
plt.figure(figsize=(8, 4))
G1 = nx.from_numpy_array(A1.numpy())
G2 = nx.from_numpy_array(A2.numpy())
pos1 = nx.spring_layout(G1)
pos2 = nx.spring_layout(G2)
ax1 = plt.subplot(1, 2, 1)
plt.title('Graph 1')
nx.draw_networkx(G1, pos=pos1)
ax2 = plt.subplot(1, 2, 2)
plt.title('Graph 2')
nx.draw_networkx(G2, pos=pos2)
for i in range(num_seeds):
j = jt.argmax(seed_mat[i], dim=-1)[0].item()
con = ConnectionPatch(xyA=pos1[i], xyB=pos2[j], coordsA="data", coordsB="data",
axesA=ax1, axesB=ax2, color="blue")
plt.gca().add_artist(con)
/auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_jittor_002.png
Now these two graphs look dissimilar because they are not aligned. We then align these two graphs by graph matching.
We follow the formulation of Quadratic Assignment Problem (QAP):
where the first step is to build the affinity matrix (K). We firstly build a "standard" affinity matrix:
conn1, edge1 = pygm.utils.dense_to_sparse(A1)
conn2, edge2 = pygm.utils.dense_to_sparse(A2)
import functools
gaussian_aff = functools.partial(pygm.utils.gaussian_aff_fn, sigma=.1) # set affinity function
K = pygm.utils.build_aff_mat(None, edge1, conn1, None, edge2, conn2, n1, None, n2, None, edge_aff_fn=gaussian_aff)
The next step is to add the seed matching information as priors to the affinity matrix. The matching priors are treated as node affinities and the corresponding node affinity is added by 10 if there is an matching prior.
Note
The node affinity matrix is transposed because in the graph matching formulation followed by pygmtools
, vec
(X) means column vectorization. The node affinity should also be column-vectorized.
Visualization of the affinity matrix.
Note
In this example, the diagonal elements reflect the matching prior.
/auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_jittor_003.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x7fd947d39db0>
See ~pygmtools.classic_solvers.rrwm
for the API reference.
The output of RRWM is a soft matching matrix. The matching prior is well-preserved:
/auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_jittor_004.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x7fd94c637c70>
Hungarian algorithm is then adopted to reach a discrete matching matrix
Visualization of the discrete matching matrix:
/auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_jittor_005.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x7fd94c72ce80>
Draw the matching (green lines for correct matching, red lines for wrong matching, blue lines for seed matching):
plt.figure(figsize=(8, 4))
ax1 = plt.subplot(1, 2, 1)
plt.title('Graph 1')
nx.draw_networkx(G1, pos=pos1)
ax2 = plt.subplot(1, 2, 2)
plt.title('Graph 2')
nx.draw_networkx(G2, pos=pos2)
for i in range(num_nodes):
j = jt.argmax(X[i], dim=-1)[0].item()
if seed_mat[i, j] == 1:
line_color = "blue"
elif X_gt[i, j] == 1:
line_color = "green"
else:
line_color = "red"
con = ConnectionPatch(xyA=pos1[i], xyB=pos2[j], coordsA="data", coordsB="data",
axesA=ax1, axesB=ax2, color=line_color)
plt.gca().add_artist(con)
/auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_jittor_006.png
Align the nodes:
align_A2 = jt.matmul(jt.matmul(X, A2), X.t())
plt.figure(figsize=(8, 4))
ax1 = plt.subplot(1, 2, 1)
plt.title('Graph 1')
nx.draw_networkx(G1, pos=pos1)
ax2 = plt.subplot(1, 2, 2)
plt.title('Aligned Graph 2')
align_pos2 = {}
for i in range(num_nodes):
j = jt.argmax(X[i], dim=-1)[0].item()
align_pos2[j] = pos1[i]
if seed_mat[i, j] == 1:
line_color = "blue"
elif X_gt[i, j] == 1:
line_color = "green"
else:
line_color = "red"
con = ConnectionPatch(xyA=pos1[i], xyB=align_pos2[j], coordsA="data", coordsB="data",
axesA=ax1, axesB=ax2, color=line_color)
plt.gca().add_artist(con)
nx.draw_networkx(G2, pos=align_pos2)
/auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_jittor_007.png
Only the affinity matrix is modified to encode matching priors. Thus, other graph matching solvers are also available to handle this seeded graph matching setting.
See ~pygmtools.classic_solvers.ipfp
for the API reference.
Visualization of IPFP matching result:
/auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_jittor_008.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x7fda2c0f6080>
See ~pygmtools.classic_solvers.sm
for the API reference.
Visualization of SM matching result:
/auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_jittor_009.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x7fda3c98c250>
See ~pygmtools.neural_solvers.ngm
for the API reference.
Visualization of NGM matching result:
/auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_jittor_010.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x7fda3c840790>
sphx-glr-timing
Total running time of the script: (0 minutes 0.720 seconds)
html
Download Python source code: plot_seed_graph_match_jittor.py <plot_seed_graph_match_jittor.py>
Download Jupyter notebook: plot_seed_graph_match_jittor.ipynb <plot_seed_graph_match_jittor.ipynb>
html
sphx-glr-signature