Skip to content

Latest commit

 

History

History
610 lines (307 loc) · 14.4 KB

plot_isomorphic_graphs_paddle.rst

File metadata and controls

610 lines (307 loc) · 14.4 KB
Raw

html

Note

Click here <sphx_glr_download_auto_examples_paddle_plot_isomorphic_graphs_paddle.py> to download the full example code

sphx-glr-example-title

Introduction: Matching Isomorphic Graphs

This example is an introduction to pygmtools which shows how to match isomorphic graphs. Isomorphic graphs mean 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:

  • ~pygmtools.classic_solvers.rrwm (classic solver)
  • ~pygmtools.classic_solvers.ipfp (classic solver)
  • ~pygmtools.classic_solvers.sm (classic solver)
  • ~pygmtools.neural_solvers.ngm (neural network solver)
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.BACKEND = 'paddle' # set default backend for pygmtools

paddle.device.set_device('cpu')
_ = paddle.seed(1) # fix random seed

sphx-glr-script-out

/Library/Frameworks/Python.framework/Versions/3.8/lib/python3.8/site-packages/setuptools/depends.py:2: DeprecationWarning: the imp module is deprecated in favour of importlib; see the module's documentation for alternative uses
  import imp

Generate two isomorphic graphs

num_nodes = 10
X_gt = paddle.zeros((num_nodes, num_nodes))
X_gt[paddle.arange(0, num_nodes, dtype=paddle.int64), paddle.randperm(num_nodes)] = 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])

Visualize the graphs

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)

/auto_examples/paddle/images/sphx_glr_plot_isomorphic_graphs_paddle_001.png

These two graphs look dissimilar because they are not aligned. We then align these two graphs by graph matching.

Build affinity matrix

To match isomorphic graphs by graph matching, we follow the formulation of Quadratic Assignment Problem (QAP):

$$\begin{aligned} &\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} \end{aligned}$$

where the first step is to build the affinity matrix (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 N2 × N2 elements because there are N2 edges in each graph.

Note

The diagonal elements of the affinity matrix are 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')

/auto_examples/paddle/images/sphx_glr_plot_isomorphic_graphs_paddle_002.png

sphx-glr-script-out

<matplotlib.image.AxesImage object at 0x7fa57dda32b0>

Solve graph matching problem by RRWM solver

See ~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')

/auto_examples/paddle/images/sphx_glr_plot_isomorphic_graphs_paddle_003.png

sphx-glr-script-out

<matplotlib.image.AxesImage object at 0x7fa57e0d6d30>

Get the discrete matching matrix

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()).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')

/auto_examples/paddle/images/sphx_glr_plot_isomorphic_graphs_paddle_004.png

sphx-glr-script-out

<matplotlib.image.AxesImage object at 0x7fa57dd7ef10>

Align the original graphs

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 = paddle.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] else "red")
    plt.gca().add_artist(con)

/auto_examples/paddle/images/sphx_glr_plot_isomorphic_graphs_paddle_005.png

Align the nodes:

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]
    con = ConnectionPatch(xyA=pos1[i], xyB=align_pos2[j], coordsA="data", coordsB="data",
                          axesA=ax1, axesB=ax2, color="green" if X_gt[i, j] else "red")
    plt.gca().add_artist(con)
nx.draw_networkx(G2, pos=align_pos2)

/auto_examples/paddle/images/sphx_glr_plot_isomorphic_graphs_paddle_006.png

Other solvers are also available

Classic IPFP solver

See ~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()).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')

/auto_examples/paddle/images/sphx_glr_plot_isomorphic_graphs_paddle_007.png

sphx-glr-script-out

<matplotlib.image.AxesImage object at 0x7fa57e6b6910>

Classic SM solver

See ~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()).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')

/auto_examples/paddle/images/sphx_glr_plot_isomorphic_graphs_paddle_008.png

sphx-glr-script-out

<matplotlib.image.AxesImage object at 0x7fa54e882820>

NGM neural network solver

See ~pygmtools.neural_solvers.ngm for the API reference.

with paddle.set_grad_enabled(False):
    X = pygm.ngm(K, n1, n2, pretrain='voc')
    X = pygm.hungarian(X)

sphx-glr-script-out

Downloading to /Users/guoziao/Library/Caches/pygmtools/ngm_voc_paddle.pdparams...

Downloading to /Users/guoziao/Library/Caches/pygmtools/ngm_voc_paddle.pdparams...
  0%|          | 0/14583 [00:00<?, ?it/s]    100%|##########| 14.2k/14.2k [00:00<00:00, 744kB/s]

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()).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')

/auto_examples/paddle/images/sphx_glr_plot_isomorphic_graphs_paddle_009.png

sphx-glr-script-out

<matplotlib.image.AxesImage object at 0x7fa54e755d90>

sphx-glr-timing

Total running time of the script: ( 0 minutes 15.571 seconds)

html

Download Python source code: plot_isomorphic_graphs_paddle.py <plot_isomorphic_graphs_paddle.py>

Download Jupyter notebook: plot_isomorphic_graphs_paddle.ipynb <plot_isomorphic_graphs_paddle.ipynb>

html