.. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end <sphx_glr_download_auto_examples_3.discovering_subgraphs_plot_subgraphs_pytorch.py>` to download the full example code
.. rst-class:: sphx-glr-example-title
This example shows how to match a smaller graph to a subset of a larger graph.
# Author: Runzhong Wang <runzhong.wang@sjtu.edu.cn>
#
# License: Mulan PSL v2 License
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)
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.set_backend('pytorch') # set default backend for pygmtools
_ = torch.manual_seed(1) # fix random seed
num_nodes2 = 10
A2 = torch.rand(num_nodes2, num_nodes2)
A2 = (A2 + A2.t() > 1.) * (A2 + A2.t()) / 2
torch.diagonal(A2)[:] = 0
n2 = torch.tensor([num_nodes2])
num_nodes1 = 5
G2 = nx.from_numpy_array(A2.numpy())
pos2 = nx.spring_layout(G2)
pos2_t = torch.tensor([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 = torch.sum(torch.sum(torch.abs(pos2_t[selected].unsqueeze(1) - pos2_t[unselected].unsqueeze(0)), dim=-1), dim=0)
select_id = unselected[torch.argmin(dist).item()] # find the closest node from unselected
selected.append(select_id)
unselected.remove(select_id)
selected.sort()
A1 = A2[selected, :][:, selected]
X_gt = torch.eye(num_nodes2)[selected, :]
n1 = torch.tensor([num_nodes1])
.. rst-class:: sphx-glr-script-out .. code-block:: none /home/wzever/pygmtools/examples/3.discovering_subgraphs/plot_subgraphs_pytorch.py:52: UserWarning: Creating a tensor from a list of numpy.ndarrays is extremely slow. Please consider converting the list to a single numpy.ndarray with numpy.array() before converting to a tensor. (Triggered internally at ../torch/csrc/utils/tensor_new.cpp:210.) pos2_t = torch.tensor([pos2[_] for _ in range(num_nodes2)])
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_pytorch_001.png :alt: Subgraph 1, Graph 2 :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_001.png :class: sphx-glr-single-img
We then show how to automatically discover the matching by graph matching.
To match the larger graph and the smaller graph, 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=.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)
Visualization of the affinity matrix. For graph matching problem with N_1 and N_2 nodes, the affinity matrix has N_1N_2\times N_1N_2 elements because there are N_1^2 and 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.
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_pytorch_002.png :alt: Affinity Matrix (size: 50$\times$50) :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_002.png :class: sphx-glr-single-img
.. rst-class:: sphx-glr-script-out .. code-block:: none <matplotlib.image.AxesImage object at 0x7fd306a0c280>
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/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_003.png :alt: RRWM Soft Matching Matrix, Ground Truth Matching Matrix :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_003.png :class: sphx-glr-single-img
.. rst-class:: sphx-glr-script-out .. code-block:: none <matplotlib.image.AxesImage object at 0x7fd306ac0fa0>
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/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_004.png :alt: RRWM Matching Matrix (acc=1.00), Ground Truth Matching Matrix :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_004.png :class: sphx-glr-single-img
.. rst-class:: sphx-glr-script-out .. code-block:: none <matplotlib.image.AxesImage object at 0x7fd307ef1480>
Draw the matching:
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 = 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] == 1 else "red")
plt.gca().add_artist(con)
.. image-sg:: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_005.png :alt: RRWM Matching Result (acc=1.00), Subgraph 1, Graph 2 :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_005.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.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 = 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] == 1 else "red")
plt.gca().add_artist(con)
.. image-sg:: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_006.png :alt: IPFP Matching Result (acc=1.00), Subgraph 1, Graph 2 :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_006.png :class: sphx-glr-single-img
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.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 = 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] == 1 else "red")
plt.gca().add_artist(con)
.. image-sg:: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_007.png :alt: SM Matching Result (acc=1.00), Subgraph 1, Graph 2 :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_007.png :class: sphx-glr-single-img
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.
with torch.set_grad_enabled(False):
X = pygm.ngm(K, n1, n2, pretrain='voc')
X = pygm.hungarian(X)
Visualization of NGM matching result:
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 = 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] == 1 else "red")
plt.gca().add_artist(con)
.. image-sg:: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_008.png :alt: NGM Matching Result (acc=0.60), Subgraph 1, Graph 2 :srcset: /auto_examples/3.discovering_subgraphs/images/sphx_glr_plot_subgraphs_pytorch_008.png :class: sphx-glr-single-img
.. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.545 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_subgraphs_pytorch.py <plot_subgraphs_pytorch.py>` .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_subgraphs_pytorch.ipynb <plot_subgraphs_pytorch.ipynb>`
.. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_