.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "auto_examples/2.seeded_graph_matching/plot_seed_graph_match_numpy.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code .. rst-class:: sphx-glr-example-title .. _sphx_glr_auto_examples_2.seeded_graph_matching_plot_seed_graph_match_numpy.py: ============================================ Numpy Backend Example: Seeded Graph Matching ============================================ 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``. .. GENERATED FROM PYTHON SOURCE LINES 10-16 .. code-block:: default # Author: Runzhong Wang # Qi Liu # # License: Mulan PSL v2 License .. GENERATED FROM PYTHON SOURCE LINES 18-33 .. 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: * :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) .. GENERATED FROM PYTHON SOURCE LINES 33-41 .. code-block:: default import numpy as np # numpy 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('numpy') # set default backend for pygmtools np.random.seed(1) # fix random seed .. GENERATED FROM PYTHON SOURCE LINES 42-47 Generate two isomorphic graphs (with seeds) ------------------------------------------- In this example, we assume the first three nodes are already aligned. Firstly, we generate the seed matching matrix: .. GENERATED FROM PYTHON SOURCE LINES 47-52 .. code-block:: default num_nodes = 10 num_seeds = 3 seed_mat = np.zeros((num_nodes, num_nodes)) seed_mat[:num_seeds, :num_seeds] = np.eye(num_seeds) .. GENERATED FROM PYTHON SOURCE LINES 53-55 Then we generate the isomorphic graphs: .. GENERATED FROM PYTHON SOURCE LINES 55-64 .. code-block:: default X_gt = seed_mat.copy() X_gt[num_seeds:, num_seeds:][np.arange(0, num_nodes-num_seeds, dtype=np.int64), np.random.permutation(num_nodes-num_seeds)] = 1 A1 = np.random.rand(num_nodes, num_nodes) A1 = (A1 + A1.T > 1.) * (A1 + A1.T) / 2 np.fill_diagonal(A1, 0) A2 = np.matmul(np.matmul(X_gt.T, A1), X_gt) n1 = np.array([num_nodes]) n2 = np.array([num_nodes]) .. GENERATED FROM PYTHON SOURCE LINES 65-69 Visualize the graphs and seeds ------------------------------- The seed matching matrix: .. GENERATED FROM PYTHON SOURCE LINES 69-73 .. code-block:: default plt.figure(figsize=(4, 4)) plt.title('Seed Matching Matrix') plt.imshow(seed_mat, cmap='Blues') .. image-sg:: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_001.png :alt: Seed Matching Matrix :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 74-76 The blue lines denote the matching seeds. .. GENERATED FROM PYTHON SOURCE LINES 76-93 .. code-block:: default plt.figure(figsize=(8, 4)) G1 = nx.from_numpy_array(A1) G2 = nx.from_numpy_array(A2) 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 = np.argmax(seed_mat[i]).item() con = ConnectionPatch(xyA=pos1[i], xyB=pos2[j], coordsA="data", coordsB="data", axesA=ax1, axesB=ax2, color="blue") plt.gca().add_artist(con) .. image-sg:: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_002.png :alt: Graph 1, Graph 2 :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_002.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 94-109 Now these two graphs look dissimilar because they are not aligned. We then align these two graphs by graph matching. Build affinity matrix with seed prior -------------------------------------- We follow the formulation of Quadratic Assignment Problem (QAP): .. math:: &\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 (:math:`\mathbf{K}`). We firstly build a "standard" affinity matrix: .. GENERATED FROM PYTHON SOURCE LINES 109-115 .. code-block:: default 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) .. GENERATED FROM PYTHON SOURCE LINES 116-125 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``, :math:`\texttt{vec}(\mathbf{X})` means column vectorization. The node affinity should also be column- vectorized. .. GENERATED FROM PYTHON SOURCE LINES 125-127 .. code-block:: default np.fill_diagonal(K, np.diagonal(K) + seed_mat.T.reshape(-1) * 10) .. GENERATED FROM PYTHON SOURCE LINES 128-133 Visualization of the affinity matrix. .. note:: In this example, the diagonal elements reflect the matching prior. .. GENERATED FROM PYTHON SOURCE LINES 133-137 .. code-block:: default plt.figure(figsize=(4, 4)) plt.title(f'Affinity Matrix (size: {K.shape[0]}$\\times${K.shape[1]})') plt.imshow(K, cmap='Blues') .. image-sg:: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_003.png :alt: Affinity Matrix (size: 100$\times$100) :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_003.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 138-142 Solve graph matching problem by RRWM solver ------------------------------------------- See :func:`~pygmtools.classic_solvers.rrwm` for the API reference. .. GENERATED FROM PYTHON SOURCE LINES 142-144 .. code-block:: default X = pygm.rrwm(K, n1, n2) .. GENERATED FROM PYTHON SOURCE LINES 145-147 The output of RRWM is a soft matching matrix. The matching prior is well-preserved: .. GENERATED FROM PYTHON SOURCE LINES 147-155 .. code-block:: default plt.figure(figsize=(8, 4)) plt.subplot(1, 2, 1) plt.title('RRWM Soft Matching Matrix') plt.imshow(X, cmap='Blues') plt.subplot(1, 2, 2) plt.title('Ground Truth Matching Matrix') plt.imshow(X_gt, cmap='Blues') .. image-sg:: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_004.png :alt: RRWM Soft Matching Matrix, Ground Truth Matching Matrix :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_004.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 156-160 Get the discrete matching matrix --------------------------------- Hungarian algorithm is then adopted to reach a discrete matching matrix .. GENERATED FROM PYTHON SOURCE LINES 160-162 .. code-block:: default X = pygm.hungarian(X) .. GENERATED FROM PYTHON SOURCE LINES 163-165 Visualization of the discrete matching matrix: .. GENERATED FROM PYTHON SOURCE LINES 165-173 .. code-block:: default 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, cmap='Blues') plt.subplot(1, 2, 2) plt.title('Ground Truth Matching Matrix') plt.imshow(X_gt, cmap='Blues') .. image-sg:: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_005.png :alt: RRWM Matching Matrix (acc=1.00), Ground Truth Matching Matrix :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_005.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 174-179 Align the original graphs -------------------------- Draw the matching (green lines for correct matching, red lines for wrong matching, blue lines for seed matching): .. GENERATED FROM PYTHON SOURCE LINES 179-198 .. code-block:: default 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 = np.argmax(X[i]).item() if seed_mat[i, j]: line_color = "blue" elif X_gt[i, j]: 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) .. image-sg:: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_006.png :alt: Graph 1, Graph 2 :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_006.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 199-201 Align the nodes: .. GENERATED FROM PYTHON SOURCE LINES 201-223 .. code-block:: default align_A2 = np.matmul(np.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 = np.argmax(X[i]).item() align_pos2[j] = pos1[i] if seed_mat[i, j]: line_color = "blue" elif X_gt[i, j]: 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) .. image-sg:: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_007.png :alt: Graph 1, Aligned Graph 2 :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_007.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 224-233 Other solvers are also available --------------------------------- 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. Classic IPFP solver ^^^^^^^^^^^^^^^^^^^^^ See :func:`~pygmtools.classic_solvers.ipfp` for the API reference. .. GENERATED FROM PYTHON SOURCE LINES 233-235 .. code-block:: default X = pygm.ipfp(K, n1, n2) .. rst-class:: sphx-glr-script-out .. code-block:: none /home/wzever/pygmtools/pygmtools/numpy_backend.py:304: RuntimeWarning: invalid value encountered in divide t0 = alpha / beta .. GENERATED FROM PYTHON SOURCE LINES 236-238 Visualization of IPFP matching result: .. GENERATED FROM PYTHON SOURCE LINES 238-246 .. code-block:: default 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, cmap='Blues') plt.subplot(1, 2, 2) plt.title('Ground Truth Matching Matrix') plt.imshow(X_gt, cmap='Blues') .. image-sg:: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_008.png :alt: IPFP Matching Matrix (acc=1.00), Ground Truth Matching Matrix :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_008.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 247-251 Classic SM solver ^^^^^^^^^^^^^^^^^^^^^ See :func:`~pygmtools.classic_solvers.sm` for the API reference. .. GENERATED FROM PYTHON SOURCE LINES 251-254 .. code-block:: default X = pygm.sm(K, n1, n2) X = pygm.hungarian(X) .. GENERATED FROM PYTHON SOURCE LINES 255-257 Visualization of SM matching result: .. GENERATED FROM PYTHON SOURCE LINES 257-265 .. code-block:: default 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, cmap='Blues') plt.subplot(1, 2, 2) plt.title('Ground Truth Matching Matrix') plt.imshow(X_gt, cmap='Blues') .. image-sg:: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_009.png :alt: SM Matching Matrix (acc=1.00), Ground Truth Matching Matrix :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_009.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 266-270 NGM neural network solver ^^^^^^^^^^^^^^^^^^^^^^^^^ See :func:`~pygmtools.neural_solvers.ngm` for the API reference. .. GENERATED FROM PYTHON SOURCE LINES 270-273 .. code-block:: default X = pygm.ngm(K, n1, n2, pretrain='voc') X = pygm.hungarian(X) .. GENERATED FROM PYTHON SOURCE LINES 274-276 Visualization of NGM matching result: .. GENERATED FROM PYTHON SOURCE LINES 276-283 .. code-block:: default 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, cmap='Blues') plt.subplot(1, 2, 2) plt.title('Ground Truth Matching Matrix') plt.imshow(X_gt, cmap='Blues') .. image-sg:: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_010.png :alt: NGM Matching Matrix (acc=1.00), Ground Truth Matching Matrix :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_numpy_010.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.853 seconds) .. _sphx_glr_download_auto_examples_2.seeded_graph_matching_plot_seed_graph_match_numpy.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_seed_graph_match_numpy.py ` .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_seed_graph_match_numpy.ipynb ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_