pygmtools.classic_solvers.sm¶
- pygmtools.classic_solvers.sm(K, n1=None, n2=None, n1max=None, n2max=None, x0=None, max_iter: int = 50, backend=None)[source]¶
Spectral Graph Matching solver for graph matching (QAP). This algorithm is also known as Power Iteration method, because it works by computing the leading eigenvector of the input affinity matrix by power iteration.
For each iteration,
\[\mathbf{v}_{k+1} = \mathbf{K} \mathbf{v}_k / ||\mathbf{K} \mathbf{v}_k||_2\]- Parameters
K – \((b\times n_1n_2 \times n_1n_2)\) the input affinity matrix, \(b\): batch size.
n1 – \((b)\) number of nodes in graph1 (optional if n1max is given, and all n1=n1max).
n2 – \((b)\) number of nodes in graph2 (optional if n2max is given, and all n2=n2max).
n1max – \((b)\) max number of nodes in graph1 (optional if n1 is given, and n1max=max(n1)).
n2max – \((b)\) max number of nodes in graph2 (optional if n2 is given, and n2max=max(n2)).
x0 – \((b\times n_1 \times n_2)\) an initial matching solution for warm-start. If not given, x0 will be randomly generated.
max_iter – (default: 50) max number of iterations. More iterations will help the solver to converge better, at the cost of increased inference time.
backend – (default:
pygmtools.BACKEND
variable) the backend for computation.
- Returns
\((b\times n_1 \times n_2)\) the solved doubly-stochastic matrix
Note
Either
n1
orn1max
should be specified because it cannot be inferred from the input tensor size. Same forn2
orn2max
.Note
We support batched instances with different number of nodes, therefore
n1
andn2
are required to specify the exact number of objects of each dimension in the batch. If not specified, we assume the batched matrices are not padded and all elements inn1
are equal, all inn2
are equal.Note
This function also supports non-batched input, by ignoring all batch dimensions in the input tensors.
Note
This solver is differentiable and supports gradient back-propagation.
Warning
The solver’s output is normalized with a squared sum of 1, which is in line with the original implementation. If a doubly-stochastic matrix is required, please call
sinkhorn()
after this. If a discrete permutation matrix is required, please callhungarian()
. Note that the Hungarian algorithm will truncate the gradient and the Sinkhorn algorithm will not.Numpy Example
>>> import numpy as np >>> import pygmtools as pygm >>> pygm.BACKEND = 'numpy' >>> np.random.seed(1) # Generate a batch of isomorphic graphs >>> batch_size = 10 >>> X_gt = np.zeros((batch_size, 4, 4)) >>> X_gt[:, np.arange(0, 4, dtype=np.int64), np.random.permutation(4)] = 1 >>> A1 = np.random.rand(batch_size, 4, 4) >>> A2 = np.matmul(np.matmul(X_gt.transpose((0, 2, 1)), A1), X_gt) >>> n1 = n2 = np.repeat([4], batch_size) # Build affinity matrix >>> conn1, edge1, ne1 = pygm.utils.dense_to_sparse(A1) >>> conn2, edge2, ne2 = 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) # Solve by SM. Note that X is normalized with a squared sum of 1 >>> X = pygm.sm(K, n1, n2) >>> (X ** 2).sum(axis=(1, 2)) array([1., 1., 1., 1., 1., 1., 1., 1., 1., 1.]) # Accuracy >>> (pygm.hungarian(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 a batch of isomorphic graphs >>> batch_size = 10 >>> X_gt = torch.zeros(batch_size, 4, 4) >>> X_gt[:, torch.arange(0, 4, dtype=torch.int64), torch.randperm(4)] = 1 >>> A1 = torch.rand(batch_size, 4, 4) >>> A2 = torch.bmm(torch.bmm(X_gt.transpose(1, 2), A1), X_gt) >>> n1 = n2 = torch.tensor([4] * batch_size) # Build affinity matrix >>> conn1, edge1, ne1 = pygm.utils.dense_to_sparse(A1) >>> conn2, edge2, ne2 = 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) # Solve by SM. Note that X is normalized with a squared sum of 1 >>> X = pygm.sm(K, n1, n2) >>> (X ** 2).sum(dim=(1, 2)) tensor([1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000]) # Accuracy >>> (pygm.hungarian(X) * X_gt).sum() / X_gt.sum() tensor(1.) # This solver supports gradient back-propogation >>> K = K.requires_grad_(True) >>> pygm.sm(K, n1, n2).sum().backward() >>> len(torch.nonzero(K.grad)) 2560
Paddle Example
>>> import paddle >>> import pygmtools as pygm >>> pygm.BACKEND = 'paddle' >>> _ = paddle.seed(1) # Generate a batch of isomorphic graphs >>> batch_size = 10 >>> X_gt = paddle.zeros((batch_size, 4, 4)) >>> X_gt[:, paddle.arange(0, 4, dtype=paddle.int64), paddle.randperm(4)] = 1 >>> A1 = paddle.rand((batch_size, 4, 4)) >>> A2 = paddle.bmm(paddle.bmm(X_gt.transpose((0, 2, 1)), A1), X_gt) >>> n1 = n2 = paddle.to_tensor([4] * batch_size) # Build affinity matrix >>> conn1, edge1, ne1 = pygm.utils.dense_to_sparse(A1) >>> conn2, edge2, ne2 = 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) # Solve by SM. Note that X is normalized with a squared sum of 1 >>> X = pygm.sm(K, n1, n2) >>> (X ** 2).sum(axis=(1, 2)) Tensor(shape=[10], dtype=float32, place=Place(cpu), stop_gradient=True, [1. , 1. , 0.99999994, 0.99999994, 1.00000012, 1. , 1.00000012, 1. , 1. , 0.99999994]) # Accuracy >>> (pygm.hungarian(X) * X_gt).sum() / X_gt.sum() Tensor(shape=[1], dtype=float32, place=Place(cpu), stop_gradient=True, [1.]) # This solver supports gradient back-propogation >>> K.stop_gradient = False >>> pygm.sm(K, n1, n2).sum().backward() >>> len(paddle.nonzero(K.grad)) 2560
Jittor Example
>>> import jittor as jt >>> import pygmtools as pygm >>> pygm.BACKEND = 'jittor' >>> _ = jt.seed(1) # Generate a batch of isomorphic graphs >>> batch_size = 10 >>> X_gt = jt.zeros((batch_size, 4, 4)) >>> X_gt[:, jt.arange(0, 4, dtype=jt.int64), jt.randperm(4)] = 1 >>> A1 = jt.rand(batch_size, 4, 4) >>> A2 = jt.bmm(jt.bmm(X_gt.transpose(1, 2), A1), X_gt) >>> n1 = n2 = jt.Var([4] * batch_size) # Build affinity matrix >>> conn1, edge1, ne1 = pygm.utils.dense_to_sparse(A1) >>> conn2, edge2, ne2 = 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) # Solve by SM. Note that X is normalized with a squared sum of 1 >>> X = pygm.sm(K, n1, n2) >>> (X ** 2).sum(dim=1).sum(dim=1) jt.Var([0.9999998 1. 0.9999999 1.0000001 1. 1. 0.9999999 0.99999994 1.0000001 1. ], dtype=float32) # Accuracy >>> (pygm.hungarian(X) * X_gt).sum() / X_gt.sum() jt.Var([1.], dtype=float32)
Note
If you find this graph matching solver useful for your research, please cite:
@inproceedings{sm, title={A spectral technique for correspondence problems using pairwise constraints}, author={Leordeanu, Marius and Hebert, Martial}, year={2005}, pages={1482-1489}, booktitle={International Conference on Computer Vision}, publisher={IEEE} }