Jittor 后端示例：种子图匹配

种子图匹配意味着匹配结果的一部分已经已知，这些已知的匹配结果被称为“种子”。在这个例子中，我们展示了如何利用pygmtools来利用这种先验知识。

# Author: Runzhong Wang <runzhong.wang@sjtu.edu.cn>
#         Qi Liu <purewhite@sjtu.edu.cn>
#
# License: Mulan PSL v2 License

注意

如何进行种子图匹配仍然是一个开放的研究问题。在这个例子中，我们展示了一种简单但有效的方法，该方法与pygmtools一起使用。

注意

以下求解器包含在此示例中：

• rrwm() (经典求解器)

• ipfp() (经典求解器)

• sm() (经典求解器)

• ngm() (神经网络求解器)

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

生成两个同构图（带种子）

在这个例子中，我们假设前三个节点已经对齐。首先，我们生成种子匹配矩阵：

num_nodes = 10
num_seeds = 3
seed_mat = jt.zeros((num_nodes, num_nodes))
seed_mat[:num_seeds, :num_seeds] = jt.init.eye(num_seeds)

然后我们生成同构图：

X_gt = seed_mat.clone()

X_gt[jt.arange(num_seeds, num_nodes), jt.arange(num_seeds, num_nodes)[jt.randperm(num_nodes-num_seeds)]] = 1
A1 = jt.rand(num_nodes, num_nodes)
A1 = (A1 + A1.t() > 1.) * (A1 + A1.t()) / 2

A1[jt.arange(A1.shape[0]), jt.arange(A1.shape[0])] = 0
A2 = jt.matmul(jt.matmul(X_gt.t(), A1), X_gt)
n1 = jt.Var([num_nodes])
n2 = jt.Var([num_nodes])

可视化图形和种子

种子匹配矩阵：

plt.figure(figsize=(4, 4))
plt.title('Seed Matching Matrix')
plt.imshow(seed_mat.numpy(), cmap='Blues')

<matplotlib.image.AxesImage object at 0x7fda50d6abf0>

蓝色线条表示匹配的种子。

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 = jt.argmax(seed_mat[i], dim=-1)[0].item()
    con = ConnectionPatch(xyA=pos1[i], xyB=pos2[j], coordsA="data", coordsB="data",
                          axesA=ax1, axesB=ax2, color="blue")
    plt.gca().add_artist(con)

现在这两个图看起来不同，因为它们没有对齐。然后我们通过图匹配来对齐这两个图。

使用种子先验构建亲和矩阵

我们遵循二次分配问题（QAP）的公式：

\[\begin{split}&\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{split}\]

第一步是构建亲和矩阵（\(\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=.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)

下一步是将种子匹配信息作为先验添加到亲和矩阵中。匹配先验被视为节点亲和力，如果存在匹配先验，则相应的节点亲和力增加10。

注意

节点亲和矩阵被转置，因为在pygmtools所遵循的图匹配公式中， \(\texttt{vec}(\mathbf{X})\)表示列向量化。节点亲和也应该进行列向量化。

K += jt.diag(seed_mat.t().reshape(-1) * 10)

亲和矩阵的可视化。

注意

在这个例子中，对角线元素反映了匹配的先验。

plt.figure(figsize=(4, 4))
plt.title(f'Affinity Matrix (size: {K.shape[0]}$\\times${K.shape[1]})')
plt.imshow(K.numpy(), cmap='Blues')

<matplotlib.image.AxesImage object at 0x7fd947d39db0>

使用RRWM求解器解决图匹配问题

请参阅rrwm()以获取API参考。

X = pygm.rrwm(K, n1, n2)

RRWM 的输出是一个软匹配矩阵。匹配先验得到了很好的保留：

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

<matplotlib.image.AxesImage object at 0x7fd94c637c70>

获取离散匹配矩阵

然后采用匈牙利算法来达到一个离散的匹配矩阵

X = pygm.hungarian(X)

离散匹配矩阵的可视化：

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

<matplotlib.image.AxesImage object at 0x7fd94c72ce80>

对齐原始图形

绘制匹配（绿色线条表示正确匹配，红色线条表示错误匹配，蓝色线条表示种子匹配）：

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 = jt.argmax(X[i], dim=-1)[0].item()
    if seed_mat[i, j] == 1:
        line_color = "blue"
    elif X_gt[i, j] == 1:
        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)

对齐节点：

align_A2 = jt.matmul(jt.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 = jt.argmax(X[i], dim=-1)[0].item()
    align_pos2[j] = pos1[i]
    if seed_mat[i, j] == 1:
        line_color = "blue"
    elif X_gt[i, j] == 1:
        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)

其他求解器也可用

仅修改亲和矩阵以编码匹配先验。因此，其他图匹配求解器也可用于处理这种带种子的图匹配设置。

经典IPFP求解器

请参阅ipfp()以获取API参考。

X = pygm.ipfp(K, n1, n2)

IPFP匹配结果的可视化：

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.numpy(), cmap='Blues')
plt.subplot(1, 2, 2)
plt.title('Ground Truth Matching Matrix')
plt.imshow(X_gt.numpy(), cmap='Blues')

<matplotlib.image.AxesImage object at 0x7fda2c0f6080>

经典SM求解器

请参阅sm()以获取API参考。

X = pygm.sm(K, n1, n2)
X = pygm.hungarian(X)

SM匹配结果的可视化：

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.numpy(), cmap='Blues')
plt.subplot(1, 2, 2)
plt.title('Ground Truth Matching Matrix')
plt.imshow(X_gt.numpy(), cmap='Blues')

<matplotlib.image.AxesImage object at 0x7fda3c98c250>

NGM神经网络求解器

请参阅ngm()的API参考。

with jt.no_grad():
    X = pygm.ngm(K, n1, n2, pretrain='voc')
    X = pygm.hungarian(X)

NGM匹配结果的可视化：

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.numpy(), cmap='Blues')
plt.subplot(1, 2, 2)
plt.title('Ground Truth Matching Matrix')
plt.imshow(X_gt.numpy(), cmap='Blues')

<matplotlib.image.AxesImage object at 0x7fda3c840790>