html
Note
Click here <sphx_glr_download_auto_examples_pytorch_plot_isomorphic_graphs.py>
to download the full example code
sphx-glr-example-title
This example is an introduction to pygmtools
which shows how to match isomorphic graphs. Isomorphic graphs means graphs whose structures are identical, but the node correspondence is unknown.
Note
The following solvers support QAP formulation, and 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 torch # pytorch 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.BACKEND = 'pytorch' # set default backend for pygmtools
_ = torch.manual_seed(1) # fix random seed
num_nodes = 10
X_gt = torch.zeros(num_nodes, num_nodes)
X_gt[torch.arange(0, num_nodes, dtype=torch.int64), torch.randperm(num_nodes)] = 1
A1 = torch.rand(num_nodes, num_nodes)
A1 = (A1 + A1.t() > 1.) * (A1 + A1.t()) / 2
torch.diagonal(A1)[:] = 0
A2 = torch.mm(torch.mm(X_gt.t(), A1), X_gt)
n1 = torch.tensor([num_nodes])
n2 = torch.tensor([num_nodes])
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)
plt.subplot(1, 2, 1)
plt.title('Graph 1')
nx.draw_networkx(G1, pos=pos1)
plt.subplot(1, 2, 2)
plt.title('Graph 2')
nx.draw_networkx(G2, pos=pos2)
/auto_examples/pytorch/images/sphx_glr_plot_isomorphic_graphs_001.png
These two graphs look dissimilar because they are not aligned. We then align these two graphs by graph matching.
To match isomorphic graphs by graph matching, we follow the formulation of Quadratic Assignment Problem (QAP):
where the first step is to build the affinity matrix (K)
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)
Visualization of the affinity matrix. For graph matching problem with N nodes, the affinity matrix has N2 × N2 elements because there are N2 edges in each graph.
Note
The diagonal elements of the affinity matrix is empty because there is no node features in this example.
/auto_examples/pytorch/images/sphx_glr_plot_isomorphic_graphs_002.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x00000221B6EDC850>
See ~pygmtools.classic_solvers.rrwm
for the API reference.
The output of RRWM is a soft matching matrix. Visualization:
/auto_examples/pytorch/images/sphx_glr_plot_isomorphic_graphs_003.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x00000221B7671910>
Hungarian algorithm is then adopted to reach a discrete matching matrix
Visualization of the discrete matching matrix:
/auto_examples/pytorch/images/sphx_glr_plot_isomorphic_graphs_004.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x00000221B785ED60>
Draw the matching (green lines for correct matching, red lines for wrong 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 = torch.argmax(X[i]).item()
con = ConnectionPatch(xyA=pos1[i], xyB=pos2[j], coordsA="data", coordsB="data",
axesA=ax1, axesB=ax2, color="green" if X_gt[i, j] else "red")
plt.gca().add_artist(con)
/auto_examples/pytorch/images/sphx_glr_plot_isomorphic_graphs_005.png
Align the nodes:
align_A2 = torch.mm(torch.mm(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 = torch.argmax(X[i]).item()
align_pos2[j] = pos1[i]
con = ConnectionPatch(xyA=pos1[i], xyB=align_pos2[j], coordsA="data", coordsB="data",
axesA=ax1, axesB=ax2, color="green" if X_gt[i, j] else "red")
plt.gca().add_artist(con)
nx.draw_networkx(G2, pos=align_pos2)
/auto_examples/pytorch/images/sphx_glr_plot_isomorphic_graphs_006.png
See ~pygmtools.classic_solvers.ipfp
for the API reference.
Visualization of IPFP matching result:
/auto_examples/pytorch/images/sphx_glr_plot_isomorphic_graphs_007.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x00000221B6597160>
See ~pygmtools.classic_solvers.sm
for the API reference.
Visualization of SM matching result:
/auto_examples/pytorch/images/sphx_glr_plot_isomorphic_graphs_008.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x00000221B663ED90>
See ~pygmtools.neural_solvers.ngm
for the API reference.
Visualization of NGM matching result:
/auto_examples/pytorch/images/sphx_glr_plot_isomorphic_graphs_009.png
sphx-glr-script-out
<matplotlib.image.AxesImage object at 0x00000221B7E39C70>
sphx-glr-timing
Total running time of the script: ( 0 minutes 2.854 seconds)
html
Download Python source code: plot_isomorphic_graphs.py <plot_isomorphic_graphs.py>
Download Jupyter notebook: plot_isomorphic_graphs.ipynb <plot_isomorphic_graphs.ipynb>
html
sphx-glr-signature