pygmtools.multi_graph_solvers.mgm_floyd

pygmtools.multi_graph_solvers.mgm_floyd(K, x0=None, qap_solver=None, mode='time', param_lambda=0.2, backend=None)[source]

Multi-Graph Matching based on Floyd shortest path algorithm. A supergraph is considered by regarding each input graph as a node, and the matching between graphs are regraded as edges in the supergraph. Floyd algorithm is used to discover a shortest path on this supergraph for matching update.

The length of edges on the supergraph is described as follows:

$\arg \max_{k} (1-\lambda) J(\mathbf{X}_{ik} \mathbf{X}_{kj}) + \lambda C_p(\mathbf{X}_{ik} \mathbf{X}_{kj})$

where $$J(\mathbf{X}_{ik} \mathbf{X}_{kj})$$ is the objective score, and $$C_p(\mathbf{X}_{ik} \mathbf{X}_{kj})$$ measures a consistency score compared to other matchings. These two terms are balanced by $$\lambda$$.

Parameters
• K$$(m\times m \times n^2 \times n^2)$$ the input affinity matrix, where K[i,j] is the affinity matrix of graph i and graph j ($$m$$: number of nodes)

• x0 – (optional) $$(m\times m \times n \times n)$$ the initial two-graph matching result, where X[i,j] is the matching matrix result of graph i and graph j. If this argument is not given, qap_solver will be used to compute the two-graph matching result.

• qap_solver – (default: pygm.rrwm) a function object that accepts a batched affinity matrix and returns the matching matrices. It is suggested to use functools.partial and the QAP solvers provided in the classic_solvers module (see examples below).

• mode – (default: 'time') the operation mode of this algorithm. Options: 'time', 'memory', where 'time' is a time-efficient version and 'memory' is a memory-efficient version.

• param_lambda – (default: 0.3) value of $$\lambda$$, with $$\lambda\in[0,1]$$

• backend – (default: pygmtools.BACKEND variable) the backend for computation.

Returns

$$(m\times m \times n \times n)$$ the multi-graph matching result

Numpy Example
>>> import numpy as np
>>> import pygmtools as pygm
>>> pygm.set_backend('numpy')
>>> np.random.seed(1)

# Generate 10 isomorphic graphs
>>> graph_num = 10
>>> As, X_gt = pygm.utils.generate_isomorphic_graphs(node_num=4, graph_num=10)
>>> As_1, As_2 = [], []
>>> for i in range(graph_num):
...     for j in range(graph_num):
...         As_1.append(As[i])
...         As_2.append(As[j])
>>> As_1 = np.stack(As_1, axis=0)
>>> As_2 = np.stack(As_2, axis=0)

# Build affinity matrix
>>> conn1, edge1, ne1 = pygm.utils.dense_to_sparse(As_1)
>>> conn2, edge2, ne2 = pygm.utils.dense_to_sparse(As_2)
>>> 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, None, None, None, None, edge_aff_fn=gaussian_aff)
>>> K = K.reshape(graph_num, graph_num, 4*4, 4*4)
>>> K.shape
(10, 10, 16, 16)

# Solve the multi-matching problem
>>> X = pygm.mgm_floyd(K)
>>> (X * X_gt).sum() / X_gt.sum()
1.0

# Use the IPFP solver for two-graph matching
>>> ipfp_func = functools.partial(pygm.ipfp, n1max=4, n2max=4)
>>> X = pygm.mgm_floyd(K, qap_solver=ipfp_func)
>>> (X * X_gt).sum() / X_gt.sum()
1.0

# Run the faster version of CAO algorithm
>>> X = pygm.mgm_floyd(K, mode='fast')
>>> (X * X_gt).sum() / X_gt.sum()
1.0
Pytorch Example
>>> import torch
>>> import pygmtools as pygm
>>> pygm.set_backend('pytorch')
>>> _ = torch.manual_seed(1)

# Generate 10 isomorphic graphs
>>> graph_num = 10
>>> As, X_gt = pygm.utils.generate_isomorphic_graphs(node_num=4, graph_num=10)
>>> As_1, As_2 = [], []
>>> for i in range(graph_num):
...     for j in range(graph_num):
...         As_1.append(As[i])
...         As_2.append(As[j])
>>> As_1 = torch.stack(As_1, dim=0)
>>> As_2 = torch.stack(As_2, dim=0)

# Build affinity matrix
>>> conn1, edge1, ne1 = pygm.utils.dense_to_sparse(As_1)
>>> conn2, edge2, ne2 = pygm.utils.dense_to_sparse(As_2)
>>> 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, None, None, None, None, edge_aff_fn=gaussian_aff)
>>> K = K.reshape(graph_num, graph_num, 4*4, 4*4)
>>> K.shape
torch.Size([10, 10, 16, 16])

# Solve the multi-matching problem
>>> X = pygm.mgm_floyd(K)
>>> (X * X_gt).sum() / X_gt.sum()
tensor(1.)

# Use the IPFP solver for two-graph matching
>>> ipfp_func = functools.partial(pygm.ipfp, n1max=4, n2max=4)
>>> X = pygm.mgm_floyd(K, qap_solver=ipfp_func)
>>> (X * X_gt).sum() / X_gt.sum()
tensor(1.)

# Run the faster version of CAO algorithm
>>> X = pygm.mgm_floyd(K, mode='fast')
>>> (X * X_gt).sum() / X_gt.sum()
tensor(1.)
>>> import pygmtools as pygm

# Generate 10 isomorphic graphs
>>> graph_num = 10
>>> As, X_gt = pygm.utils.generate_isomorphic_graphs(node_num=4, graph_num=10)
>>> As_1, As_2 = [], []
>>> for i in range(graph_num):
...     for j in range(graph_num):
...         As_1.append(As[i])
...         As_2.append(As[j])

# Build affinity matrix
>>> conn1, edge1, ne1 = pygm.utils.dense_to_sparse(As_1)
>>> conn2, edge2, ne2 = pygm.utils.dense_to_sparse(As_2)
>>> 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, None, None, None, None, edge_aff_fn=gaussian_aff)
>>> K = K.reshape((graph_num, graph_num, 4*4, 4*4))
>>> K.shape
[10, 10, 16, 16]

# Solve the multi-matching problem
>>> X = pygm.mgm_floyd(K)
>>> (X * X_gt).sum() / X_gt.sum()

# Use the IPFP solver for two-graph matching
>>> ipfp_func = functools.partial(pygm.ipfp, n1max=4, n2max=4)
>>> X = pygm.mgm_floyd(K, qap_solver=ipfp_func)
>>> (X * X_gt).sum() / X_gt.sum()

# Run the faster version of CAO algorithm
>>> X = pygm.mgm_floyd(K, mode='fast')
>>> (X * X_gt).sum() / X_gt.sum()
Jittor Example
>>> import jittor as jt
>>> import pygmtools as pygm
>>> pygm.set_backend('jittor')
>>> _ = jt.seed(1)

# Generate 10 isomorphic graphs
>>> graph_num = 10
>>> As, X_gt = pygm.utils.generate_isomorphic_graphs(node_num=4, graph_num=10)
>>> As_1, As_2 = [], []
>>> for i in range(graph_num):
...    for j in range(graph_num):
...        As_1.append(As[i])
...        As_2.append(As[j])
>>> As_1 = jt.stack(As_1, dim=0)
>>> As_2 = jt.stack(As_2, dim=0)

# Build affinity matrix
>>> conn1, edge1, ne1 = pygm.utils.dense_to_sparse(As_1)
>>> conn2, edge2, ne2 = pygm.utils.dense_to_sparse(As_2)
>>> 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, None, None, None, None, edge_aff_fn=gaussian_aff)
>>> K = K.reshape(graph_num, graph_num, 4*4, 4*4)
>>> K.shape
[10,10,16,16,]

# Solve the multi-matching problem
>>> X = pygm.mgm_floyd(K, mode='memory')
>>> (X * X_gt).sum() / X_gt.sum()
jt.Var([1.], dtype=float32)

# Use the IPFP solver for two-graph matching
>>> ipfp_func = functools.partial(pygm.ipfp, n1max=4, n2max=4)
>>> X = pygm.mgm_floyd(K, qap_solver=ipfp_func, mode='memory')
>>> (X * X_gt).sum() / X_gt.sum()
jt.Var([1.], dtype=float32)

# Run the faster version of CAO algorithm
>>> X = pygm.mgm_floyd(K, mode='time')
>>> (X * X_gt).sum() / X_gt.sum()
jt.Var([1.], dtype=float32)

Note

If you find this graph matching solver useful in your research, please cite:

@article{mgm_floyd,
title={Unifying offline and online multi-graph matching via finding shortest paths on supergraph},
author={Jiang, Zetian and Wang, Tianzhe and Yan, Junchi},
journal={IEEE transactions on pattern analysis and machine intelligence},
volume={43},
number={10},
pages={3648--3663},
year={2020},
publisher={IEEE}
}