pygmtools.multi_graph_solvers.cao
- pygmtools.multi_graph_solvers.cao(K, x0=None, qap_solver=None, mode='time', max_iter=6, lambda_init=0.3, lambda_step=1.1, lambda_max=1.0, iter_boost=2, backend=None)[source]
Composition based Affinity Optimization (CAO) solver for multi-graph matching. This solver builds a supergraph for matching update to incorporate the two aspects by optimizing the affinity score, meanwhile gradually infusing the consistency.
Each update step 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\), and \(\lambda\) starts from a smaller number and gradually grows.
- Parameters
K – \((m\times m \times n^2 \times n^2)\) the input affinity matrix, where
K[i,j]
is the affinity matrix of graphi
and graphj
(\(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 graphi
and graphj
. 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 theclassic_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.max_iter – (default: 6) max number of iterations
lambda_init – (default: 0.3) initial value of \(\lambda\), with \(\lambda\in[0,1]\)
lambda_step – (default: 1.1) the increase step size of \(\lambda\), updated by
lambda = step * lambda
lambda_max – (default: 1.0) the max value of lambda
iter_boost – (default: 2) to boost the convergence of the CAO algorithm, \(\lambda\) will be forced to update every
iter_boost
iterations.backend – (default:
pygmtools.BACKEND
variable) the backend for computation.
- Returns
\((m\times m \times n \times n)\) the multi-graph matching result
Note
The input graphs must have the same number of nodes for this algorithm to work correctly.
Note
Multi-graph matching methods process all graphs at once and do not support the additional batch dimension. Please note that this behavior is different from two-graph matching solvers in
classic_solvers
.Numpy Example
>>> import numpy as np >>> import pygmtools as pygm >>> pygm.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.cao(K) >>> (X * X_gt).sum() / X_gt.sum() 1.0 # Use the IPFP solver for two-graph matching >>> ipfp_func = functools.partial(pygmtools.ipfp, n1max=4, n2max=4) >>> X = pygm.cao(K, qap_solver=ipfp_func) >>> (X * X_gt).sum() / X_gt.sum() 1.0 # Run the faster version of CAO algorithm >>> X = pygm.cao(K, mode='fast') >>> (X * X_gt).sum() / X_gt.sum() 1.0
Pytorch Example
>>> import torch >>> import pygmtools as pygm >>> pygm.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.cao(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.cao(K, qap_solver=ipfp_func) >>> (X * X_gt).sum() / X_gt.sum() tensor(1.) # Run the faster version of CAO algorithm >>> X = pygm.cao(K, mode='fast') >>> (X * X_gt).sum() / X_gt.sum() tensor(1.)
Paddle Example
>>> import paddle >>> import pygmtools as pygm >>> pygm.BACKEND = 'paddle' >>> _ = paddle.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 = paddle.stack(As_1, axis=0) >>> As_2 = paddle.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.cao(K) >>> (X * X_gt).sum() / X_gt.sum() Tensor(shape=[1], dtype=float32, place=Place(cpu), stop_gradient=True, [1.]) # Use the IPFP solver for two-graph matching >>> ipfp_func = functools.partial(pygm.ipfp, n1max=4, n2max=4) >>> X = pygm.cao(K, qap_solver=ipfp_func) >>> (X * X_gt).sum() / X_gt.sum() Tensor(shape=[1], dtype=float32, place=Place(cpu), stop_gradient=True, [1.]) # Run the faster version of CAO algorithm >>> X = pygm.cao(K, mode='fast') >>> (X * X_gt).sum() / X_gt.sum() Tensor(shape=[1], dtype=float32, place=Place(cpu), stop_gradient=True, [1.])
Jittor Example
>>> import jittor as jt >>> import pygmtools as pygm >>> pygm.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.cao(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.cao(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.cao(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{cao, title={Multi-graph matching via affinity optimization with graduated consistency regularization}, author={Yan, Junchi and Cho, Minsu and Zha, Hongyuan and Yang, Xiaokang and Chu, Stephen M}, journal={IEEE transactions on pattern analysis and machine intelligence}, volume={38}, number={6}, pages={1228--1242}, year={2015}, publisher={IEEE} }