.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "auto_examples/3.discovering_subgraphs/plot_subgraphs_jittor.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_3.discovering_subgraphs_plot_subgraphs_jittor.py: ============================================= Jittor Backend Example: Discovering Subgraphs ============================================= This example shows how to match a smaller graph to a subset of a larger graph. .. GENERATED FROM PYTHON SOURCE LINES 9-15 .. code-block:: default # Author: Runzhong Wang # Qi Liu # # License: Mulan PSL v2 License .. GENERATED FROM PYTHON SOURCE LINES 17-28 .. 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 28-36 .. code-block:: default 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 .. GENERATED FROM PYTHON SOURCE LINES 37-40 Generate the larger graph -------------------------- .. GENERATED FROM PYTHON SOURCE LINES 40-46 .. code-block:: default num_nodes2 = 10 A2 = jt.rand(num_nodes2, num_nodes2) A2 = (A2 + A2.t() > 1.) * (A2 + A2.t()) / 2 A2[jt.arange(A2.shape[0]), jt.arange(A2.shape[0])] = 0 n2 = jt.Var([num_nodes2]) .. GENERATED FROM PYTHON SOURCE LINES 47-50 Generate the smaller graph --------------------------- .. GENERATED FROM PYTHON SOURCE LINES 50-66 .. code-block:: default num_nodes1 = 5 G2 = nx.from_numpy_array(A2.numpy()) pos2 = nx.spring_layout(G2) pos2_t = jt.Var([pos2[_] for _ in range(num_nodes2)]) selected = [0] # build G1 as a cluster in visualization unselected = list(range(1, num_nodes2)) while len(selected) < num_nodes1: dist = jt.sum(jt.sum(jt.abs(pos2_t[selected].unsqueeze(1) - pos2_t[unselected].unsqueeze(0)), dim=-1), dim=0) select_id = unselected[jt.argmin(dist, dim=-1)[0].item()] # find the closest node from unselected selected.append(select_id) unselected.remove(select_id) selected.sort() A1 = A2[selected, :][:, selected] X_gt = jt.init.eye(num_nodes2)[selected, :] n1 = jt.Var([num_nodes1]) .. GENERATED FROM PYTHON SOURCE LINES 67-70 Visualize the graphs --------------------- .. GENERATED FROM PYTHON SOURCE LINES 70-83 .. code-block:: default G1 = nx.from_numpy_array(A1.numpy()) pos1 = {_: pos2[selected[_]] for _ in range(num_nodes1)} color1 = ['#FF5733' for _ in range(num_nodes1)] color2 = ['#FF5733' if _ in selected else '#1f78b4' for _ in range(num_nodes2)] plt.figure(figsize=(8, 4)) plt.subplot(1, 2, 1) plt.title('Subgraph 1') plt.gca().margins(0.4) nx.draw_networkx(G1, pos=pos1, node_color=color1) plt.subplot(1, 2, 2) plt.title('Graph 2') nx.draw_networkx(G2, pos=pos2, node_color=color2) .. image-sg:: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_001.png :alt: Subgraph 1, Graph 2 :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_001.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 84-97 We then show how to automatically discover the matching by graph matching. Build affinity matrix ---------------------- To match the larger graph and the smaller graph, 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}`) .. GENERATED FROM PYTHON SOURCE LINES 97-103 .. 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=.001) # 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 104-111 Visualization of the affinity matrix. For graph matching problem with :math:`N_1` and :math:`N_2` nodes, the affinity matrix has :math:`N_1N_2\times N_1N_2` elements because there are :math:`N_1^2` and :math:`N_2^2` edges in each graph, respectively. .. note:: The diagonal elements of the affinity matrix is empty because there is no node features in this example. .. GENERATED FROM PYTHON SOURCE LINES 111-115 .. 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/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_002.png :alt: Affinity Matrix (size: 50$\times$50) :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_002.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 116-120 Solve graph matching problem by RRWM solver ------------------------------------------- See :func:`~pygmtools.classic_solvers.rrwm` for the API reference. .. GENERATED FROM PYTHON SOURCE LINES 120-122 .. code-block:: default X = pygm.rrwm(K, n1, n2) .. GENERATED FROM PYTHON SOURCE LINES 123-125 The output of RRWM is a soft matching matrix. Visualization: .. GENERATED FROM PYTHON SOURCE LINES 125-133 .. 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/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_003.png :alt: RRWM Soft Matching Matrix, Ground Truth Matching Matrix :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_003.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 134-138 Get the discrete matching matrix --------------------------------- Hungarian algorithm is then adopted to reach a discrete matching matrix .. GENERATED FROM PYTHON SOURCE LINES 138-140 .. code-block:: default X = pygm.hungarian(X) .. GENERATED FROM PYTHON SOURCE LINES 141-143 Visualization of the discrete matching matrix: .. GENERATED FROM PYTHON SOURCE LINES 143-151 .. 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.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/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_004.png :alt: RRWM Matching Matrix (acc=1.00), Ground Truth Matching Matrix :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_004.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none .. GENERATED FROM PYTHON SOURCE LINES 152-156 Match the subgraph ------------------- Draw the matching: .. GENERATED FROM PYTHON SOURCE LINES 156-171 .. code-block:: default plt.figure(figsize=(8, 4)) plt.suptitle(f'RRWM Matching Result (acc={(X * X_gt).sum()/ X_gt.sum():.2f})') ax1 = plt.subplot(1, 2, 1) plt.title('Subgraph 1') plt.gca().margins(0.4) nx.draw_networkx(G1, pos=pos1, node_color=color1) ax2 = plt.subplot(1, 2, 2) plt.title('Graph 2') nx.draw_networkx(G2, pos=pos2, node_color=color2) for i in range(num_nodes1): 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/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_005.png :alt: RRWM Matching Result (acc=1.00), Subgraph 1, Graph 2 :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_005.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 172-179 Other solvers are also available --------------------------------- Classic IPFP solver ^^^^^^^^^^^^^^^^^^^^^ See :func:`~pygmtools.classic_solvers.ipfp` for the API reference. .. GENERATED FROM PYTHON SOURCE LINES 179-181 .. code-block:: default X = pygm.ipfp(K, n1, n2) .. GENERATED FROM PYTHON SOURCE LINES 182-184 Visualization of IPFP matching result: .. GENERATED FROM PYTHON SOURCE LINES 184-199 .. code-block:: default plt.figure(figsize=(8, 4)) plt.suptitle(f'IPFP Matching Result (acc={(X * X_gt).sum()/ X_gt.sum():.2f})') ax1 = plt.subplot(1, 2, 1) plt.title('Subgraph 1') plt.gca().margins(0.4) nx.draw_networkx(G1, pos=pos1, node_color=color1) ax2 = plt.subplot(1, 2, 2) plt.title('Graph 2') nx.draw_networkx(G2, pos=pos2, node_color=color2) for i in range(num_nodes1): 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/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_006.png :alt: IPFP Matching Result (acc=1.00), Subgraph 1, Graph 2 :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_006.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 200-204 Classic SM solver ^^^^^^^^^^^^^^^^^^^^^ See :func:`~pygmtools.classic_solvers.sm` for the API reference. .. GENERATED FROM PYTHON SOURCE LINES 204-207 .. code-block:: default X = pygm.sm(K, n1, n2) X = pygm.hungarian(X) .. GENERATED FROM PYTHON SOURCE LINES 208-210 Visualization of SM matching result: .. GENERATED FROM PYTHON SOURCE LINES 210-225 .. code-block:: default plt.figure(figsize=(8, 4)) plt.suptitle(f'SM Matching Result (acc={(X * X_gt).sum()/ X_gt.sum():.2f})') ax1 = plt.subplot(1, 2, 1) plt.title('Subgraph 1') plt.gca().margins(0.4) nx.draw_networkx(G1, pos=pos1, node_color=color1) ax2 = plt.subplot(1, 2, 2) plt.title('Graph 2') nx.draw_networkx(G2, pos=pos2, node_color=color2) for i in range(num_nodes1): 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/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_007.png :alt: SM Matching Result (acc=1.00), Subgraph 1, Graph 2 :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_007.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 226-235 NGM neural network solver ^^^^^^^^^^^^^^^^^^^^^^^^^ See :func:`~pygmtools.neural_solvers.ngm` for the API reference. .. note:: The NGM solvers are pretrained on a different problem setting, so their performance may seem inferior. To improve their performance, you may change the way of building affinity matrices, or try finetuning NGM on the new problem. .. GENERATED FROM PYTHON SOURCE LINES 235-239 .. code-block:: default with jt.no_grad(): X = pygm.ngm(K, n1, n2, pretrain='voc') X = pygm.hungarian(X) .. GENERATED FROM PYTHON SOURCE LINES 240-242 Visualization of NGM matching result: .. GENERATED FROM PYTHON SOURCE LINES 242-256 .. code-block:: default plt.figure(figsize=(8, 4)) plt.suptitle(f'NGM Matching Result (acc={(X * X_gt).sum()/ X_gt.sum():.2f})') ax1 = plt.subplot(1, 2, 1) plt.title('Subgraph 1') plt.gca().margins(0.4) nx.draw_networkx(G1, pos=pos1, node_color=color1) ax2 = plt.subplot(1, 2, 2) plt.title('Graph 2') nx.draw_networkx(G2, pos=pos2, node_color=color2) for i in range(num_nodes1): 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/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_008.png :alt: NGM Matching Result (acc=0.80), Subgraph 1, Graph 2 :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_jittor_008.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.601 seconds) .. _sphx_glr_download_auto_examples_3.discovering_subgraphs_plot_subgraphs_jittor.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_subgraphs_jittor.py ` .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_subgraphs_jittor.ipynb ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_