pygmtools.multi_graph_solvers.cao

pygmtools.multi_graph_solvers.cao(K, x0=None, qap_solver=None, mode='accu', 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 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: 'accu') the operation mode of this algorithm. Options: 'accu', 'c', 'fast', 'pc', where 'accu' is equivalent to 'c' (accurate version) and 'fast' is equivalent to 'pc' (fast 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.

Example for Pytorch backend:

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

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}
}