.. only:: html .. note:: :class: sphx-glr-download-link-note Click :ref:`here <sphx_glr_download_auto_examples_jittor_plot_isomorphic_graphs.py>` to download the full example code
.. rst-class:: 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.
# Author: Runzhong Wang <runzhong.wang@sjtu.edu.cn>
# Qi Liu <purewhite@sjtu.edu.cn>
#
# License: Mulan PSL v2 License
Note
The following solvers support QAP formulation, and are included in this example:
- :func:`~pygmtools.classic_solvers.rrwm` (classic solver)
- :func:`~pygmtools.classic_solvers.ipfp` (classic solver)
- :func:`~pygmtools.classic_solvers.sm` (classic solver)
- :func:`~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.BACKEND = 'jittor' # set default backend for pygmtools
_ = jt.set_seed(1) # fix random seed
jt.flags.use_cuda = jt.has_cuda
num_nodes = 10
X_gt = jt.zeros((num_nodes, num_nodes))
X_gt[jt.arange(0, num_nodes, dtype=jt.int64), jt.randperm(num_nodes)] = 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])
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)
.. image-sg:: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_001.png :alt: Graph 1, Graph 2 :srcset: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_001.png :class: sphx-glr-single-img
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):
&\max_{\mathbf{X}} \ \texttt{vec}(\mathbf{X})^\top \mathbf{K} \texttt{vec}(\mathbf{X})\\ s.t. \quad &\mathbf{X} \in \{0, 1\}^{n_1\times n_2}, \ \mathbf{X}\mathbf{1} = \mathbf{1}, \ \mathbf{X}^\top\mathbf{1} \leq \mathbf{1}
where the first step is to build the affinity matrix (\mathbf{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 N^2\times N^2 elements because there are N^2 edges in each graph.
Note
The diagonal elements of the affinity matrix is empty because there is no node features in this example.
plt.figure(figsize=(4, 4))
plt.title(f'Affinity Matrix (size: {K.shape[0]}$\\times${K.shape[1]})')
plt.imshow(K.numpy(), cmap='Blues')
.. image-sg:: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_002.png :alt: Affinity Matrix (size: 100$\times$100) :srcset: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_002.png :class: sphx-glr-single-img
.. rst-class:: sphx-glr-script-out .. code-block:: none <matplotlib.image.AxesImage object at 0x7f2e93e302e0>
See :func:`~pygmtools.classic_solvers.rrwm` for the API reference.
X = pygm.rrwm(K, n1, n2)
The output of RRWM is a soft matching matrix. Visualization:
plt.figure(figsize=(8, 4))
plt.subplot(1, 2, 1)
plt.title('RRWM Soft Matching Matrix')
plt.imshow(X.numpy(), cmap='Blues')
plt.subplot(1, 2, 2)
plt.title('Ground Truth Matching Matrix')
plt.imshow(X_gt.numpy(), cmap='Blues')
.. image-sg:: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_003.png :alt: RRWM Soft Matching Matrix, Ground Truth Matching Matrix :srcset: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_003.png :class: sphx-glr-single-img
.. rst-class:: sphx-glr-script-out .. code-block:: none <matplotlib.image.AxesImage object at 0x7f2e88161bb0>
Hungarian algorithm is then adopted to reach a discrete matching matrix
X = pygm.hungarian(X)
Visualization of the discrete matching matrix:
plt.figure(figsize=(8, 4))
plt.subplot(1, 2, 1)
plt.title(f'RRWM Matching Matrix (acc={(X * X_gt).sum()/ X_gt.sum():.2f})')
plt.imshow(X.numpy(), cmap='Blues')
plt.subplot(1, 2, 2)
plt.title('Ground Truth Matching Matrix')
plt.imshow(X_gt.numpy(), cmap='Blues')
.. image-sg:: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_004.png :alt: RRWM Matching Matrix (acc=1.00), Ground Truth Matching Matrix :srcset: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_004.png :class: sphx-glr-single-img
.. rst-class:: sphx-glr-script-out .. code-block:: none <matplotlib.image.AxesImage object at 0x7f2e87c940a0>
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 = jt.argmax(X[i], dim=-1)[0].item()
con = ConnectionPatch(xyA=pos1[i], xyB=pos2[j], coordsA="data", coordsB="data",
axesA=ax1, axesB=ax2, color="green" if X_gt[i, j] == 1 else "red")
plt.gca().add_artist(con)
.. image-sg:: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_005.png :alt: Graph 1, Graph 2 :srcset: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_005.png :class: sphx-glr-single-img
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]
con = ConnectionPatch(xyA=pos1[i], xyB=align_pos2[j], coordsA="data", coordsB="data",
axesA=ax1, axesB=ax2, color="green" if X_gt[i, j] == 1 else "red")
plt.gca().add_artist(con)
nx.draw_networkx(G2, pos=align_pos2)
.. image-sg:: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_006.png :alt: Graph 1, Aligned Graph 2 :srcset: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_006.png :class: sphx-glr-single-img
See :func:`~pygmtools.classic_solvers.ipfp` for the API reference.
X = pygm.ipfp(K, n1, n2)
Visualization of IPFP matching result:
plt.figure(figsize=(8, 4))
plt.subplot(1, 2, 1)
plt.title(f'IPFP Matching Matrix (acc={(X * X_gt).sum()/ X_gt.sum():.2f})')
plt.imshow(X.numpy(), cmap='Blues')
plt.subplot(1, 2, 2)
plt.title('Ground Truth Matching Matrix')
plt.imshow(X_gt.numpy(), cmap='Blues')
.. image-sg:: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_007.png :alt: IPFP Matching Matrix (acc=1.00), Ground Truth Matching Matrix :srcset: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_007.png :class: sphx-glr-single-img
.. rst-class:: sphx-glr-script-out .. code-block:: none <matplotlib.image.AxesImage object at 0x7f2e85c58460>
See :func:`~pygmtools.classic_solvers.sm` for the API reference.
X = pygm.sm(K, n1, n2)
X = pygm.hungarian(X)
Visualization of SM matching result:
plt.figure(figsize=(8, 4))
plt.subplot(1, 2, 1)
plt.title(f'SM Matching Matrix (acc={(X * X_gt).sum()/ X_gt.sum():.2f})')
plt.imshow(X.numpy(), cmap='Blues')
plt.subplot(1, 2, 2)
plt.title('Ground Truth Matching Matrix')
plt.imshow(X_gt.numpy(), cmap='Blues')
.. image-sg:: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_008.png :alt: SM Matching Matrix (acc=1.00), Ground Truth Matching Matrix :srcset: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_008.png :class: sphx-glr-single-img
.. rst-class:: sphx-glr-script-out .. code-block:: none <matplotlib.image.AxesImage object at 0x7f2e84f42e50>
See :func:`~pygmtools.neural_solvers.ngm` for the API reference.
with jt.no_grad():
X = pygm.ngm(K, n1, n2, pretrain='voc')
X = pygm.hungarian(X)
Visualization of NGM matching result:
plt.figure(figsize=(8, 4))
plt.subplot(1, 2, 1)
plt.title(f'NGM Matching Matrix (acc={(X * X_gt).sum()/ X_gt.sum():.2f})')
plt.imshow(X.numpy(), cmap='Blues')
plt.subplot(1, 2, 2)
plt.title('Ground Truth Matching Matrix')
plt.imshow(X_gt.numpy(), cmap='Blues')
.. image-sg:: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_009.png :alt: NGM Matching Matrix (acc=1.00), Ground Truth Matching Matrix :srcset: /auto_examples/jittor/images/sphx_glr_plot_isomorphic_graphs_009.png :class: sphx-glr-single-img
.. rst-class:: sphx-glr-script-out .. code-block:: none <matplotlib.image.AxesImage object at 0x7f2e87c2af70>
.. rst-class:: sphx-glr-timing **Total running time of the script:** ( 0 minutes 31.584 seconds)
.. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_isomorphic_graphs.py <plot_isomorphic_graphs.py>` .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_isomorphic_graphs.ipynb <plot_isomorphic_graphs.ipynb>`
.. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_