.. 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_paddle.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_paddle.py: ============================================= Paddle 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-46 .. code-block:: default import paddle # paddle 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 import warnings warnings.filterwarnings("ignore") pygm.set_backend('paddle') # set default backend for pygmtools paddle.device.set_device('cpu') _ = paddle.seed(1) # fix random seed .. GENERATED FROM PYTHON SOURCE LINES 47-52 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 52-58 .. code-block:: default num_nodes = 10 num_seeds = 3 seed_mat = paddle.zeros((num_nodes, num_nodes)) seed_mat[:num_seeds, :num_seeds] = paddle.eye(num_seeds) .. GENERATED FROM PYTHON SOURCE LINES 59-61 Then we generate the isomorphic graphs: .. GENERATED FROM PYTHON SOURCE LINES 61-70 .. code-block:: default X_gt = seed_mat.clone() X_gt[num_seeds+paddle.arange(0, num_nodes-num_seeds, dtype=paddle.int64), num_seeds+paddle.randperm(num_nodes-num_seeds)] = 1 A1 = paddle.rand((num_nodes, num_nodes)) A1 = (A1 + A1.t() > 1.) / 2 * (A1 + A1.t()) A1[paddle.arange(A1.shape[0]), paddle.arange(A1.shape[1])] = 0 # paddle.diagonal(A1)[:] = 0 A2 = paddle.mm(paddle.mm(X_gt.t(), A1), X_gt) n1 = paddle.to_tensor([num_nodes]) n2 = paddle.to_tensor([num_nodes]) .. GENERATED FROM PYTHON SOURCE LINES 71-75 Visualize the graphs and seeds ------------------------------- The seed matching matrix: .. GENERATED FROM PYTHON SOURCE LINES 75-79 .. code-block:: default plt.figure(figsize=(4, 4)) plt.title('Seed Matching Matrix') plt.imshow(seed_mat.numpy(), cmap='Blues') .. image-sg:: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_001.png :alt: Seed Matching Matrix :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 80-82 The blue lines denote the matching seeds. .. GENERATED FROM PYTHON SOURCE LINES 82-99 .. code-block:: default 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 = paddle.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_paddle_002.png :alt: Graph 1, Graph 2 :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_002.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 100-115 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 115-121 .. 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 122-131 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 131-133 .. code-block:: default K[paddle.arange(K.shape[0]), paddle.arange(K.shape[1])] += seed_mat.t().reshape((-1, )) * 10 # paddle.diagonal(K)[:] += seed_mat.t().reshape((-1, )) * 10 .. GENERATED FROM PYTHON SOURCE LINES 134-139 Visualization of the affinity matrix. .. note:: In this example, the diagonal elements reflect the matching prior. .. GENERATED FROM PYTHON SOURCE LINES 139-143 .. code-block:: default 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/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_003.png :alt: Affinity Matrix (size: 100$\times$100) :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_003.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 144-148 Solve graph matching problem by RRWM solver ------------------------------------------- See :func:`~pygmtools.classic_solvers.rrwm` for the API reference. .. GENERATED FROM PYTHON SOURCE LINES 148-150 .. code-block:: default X = pygm.rrwm(K, n1, n2) .. GENERATED FROM PYTHON SOURCE LINES 151-153 The output of RRWM is a soft matching matrix. The matching prior is well-preserved: .. GENERATED FROM PYTHON SOURCE LINES 153-161 .. code-block:: default 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/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_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_paddle_004.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 162-166 Get the discrete matching matrix --------------------------------- Hungarian algorithm is then adopted to reach a discrete matching matrix .. GENERATED FROM PYTHON SOURCE LINES 166-168 .. code-block:: default X = pygm.hungarian(X) .. GENERATED FROM PYTHON SOURCE LINES 169-171 Visualization of the discrete matching matrix: .. GENERATED FROM PYTHON SOURCE LINES 171-179 .. 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()).item():.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/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_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_paddle_005.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 180-185 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 185-204 .. 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 = paddle.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_paddle_006.png :alt: Graph 1, Graph 2 :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_006.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 205-207 Align the nodes: .. GENERATED FROM PYTHON SOURCE LINES 207-229 .. code-block:: default align_A2 = paddle.mm(paddle.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 = paddle.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_paddle_007.png :alt: Graph 1, Aligned Graph 2 :srcset: /auto_examples/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_007.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 230-239 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 239-241 .. code-block:: default X = pygm.ipfp(K, n1, n2) .. GENERATED FROM PYTHON SOURCE LINES 242-244 Visualization of IPFP matching result: .. GENERATED FROM PYTHON SOURCE LINES 244-252 .. 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()).item():.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/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_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_paddle_008.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 253-257 Classic SM solver ^^^^^^^^^^^^^^^^^^^^^ See :func:`~pygmtools.classic_solvers.sm` for the API reference. .. GENERATED FROM PYTHON SOURCE LINES 257-260 .. code-block:: default X = pygm.sm(K, n1, n2) X = pygm.hungarian(X) .. GENERATED FROM PYTHON SOURCE LINES 261-263 Visualization of SM matching result: .. GENERATED FROM PYTHON SOURCE LINES 263-271 .. 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()).item():.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/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_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_paddle_009.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 272-276 NGM neural network solver ^^^^^^^^^^^^^^^^^^^^^^^^^ See :func:`~pygmtools.neural_solvers.ngm` for the API reference. .. GENERATED FROM PYTHON SOURCE LINES 276-280 .. code-block:: default with paddle.set_grad_enabled(False): X = pygm.ngm(K, n1, n2, pretrain='voc') X = pygm.hungarian(X) .. GENERATED FROM PYTHON SOURCE LINES 281-283 Visualization of NGM matching result: .. GENERATED FROM PYTHON SOURCE LINES 283-290 .. 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()).item():.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/2.seeded_graph_matching/images/sphx_glr_plot_seed_graph_match_paddle_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_paddle_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.822 seconds) .. _sphx_glr_download_auto_examples_2.seeded_graph_matching_plot_seed_graph_match_paddle.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_paddle.py ` .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_seed_graph_match_paddle.ipynb ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_