pygmtools.multi_graph_solvers.gamgm
- pygmtools.multi_graph_solvers.gamgm(A, W, ns=None, n_univ=None, U0=None, sk_init_tau=0.5, sk_min_tau=0.1, sk_gamma=0.8, sk_iter=20, max_iter=100, param_lambda=1.0, converge_thresh=1e-05, outlier_thresh=-1, bb_smooth=0.1, verbose=False, backend=None)[source]
Graduated Assignment-based multi-graph matching solver. Graduated assignment is a classic approach for hard assignment problems like graph matching, based on graduated annealing of Sinkhorn’s temperature \(\tau\) to enforce the matching constraint.
The objective score is described as
\[\max_{\mathbf{X}_{i,j}, i,j\in [m]} \ \sum_{i,j\in [m]} \left( \lambda \ \mathrm{tr}(\mathbf{X}_{ij}^\top \mathbf{A}_{i} \mathbf{X}_{ij} \mathbf{A}_{j}) + \mathrm{tr}(\mathbf{X}_{ij}^\top \mathbf{W}_{ij})\right)\]Once the algorithm converges at a fixed \(\tau\) value, \(\tau\) shrinks as:
\[\tau = \tau \times \gamma\]and the iteration continues. At last, Hungarian algorithm is applied to ensure the result is a permutation matrix.
Note
This algorithm is based on the Koopmans-Beckmann’s QAP formulation and you should input the adjacency matrices
A
and node-wise similarity matricesW
instead of the affinity matrices.- Parameters
A – \((m\times n \times n)\) the adjacency matrix (\(m\): number of nodes). The graphs may have different number of nodes (specified by the
ns
argument).W – \((m\times m \times n \times n)\) the node-wise similarity matrix, where
W[i,j]
is the similarity matrixns – (optional) \((m)\) the number of nodes. If not given, it will be inferred based on the size of
A
.n_univ – (optional) the size of the universe node set. If not given, it will be the largest number of nodes.
U0 – (optional) the initial multi-graph matching result. If not given, it will be randomly initialized.
sk_init_tau – (default: 0.05) initial value of \(\tau\) for Sinkhorn algorithm
sk_min_tau – (default: 1.0e-3) minimal value of \(\tau\) for Sinkhorn algorithm
sk_gamma – (default: 0.8) the shrinking parameter of \(\tau\): \(\tau = \tau \times \gamma\)
sk_iter – (default: 200) max number of iterations for Sinkhorn algorithm
max_iter – (default: 1000) max number of iterations for graduated assignment
param_lambda – (default: 1) the weight \(\lambda\) of the quadratic term
converge_thresh – (default: 1e-5) if the Frobenius norm of the change of U is smaller than this, the iteration is stopped.
outlier_thresh – (default: -1) if > 0, pairs with node+edge similarity score smaller than this threshold will be discarded. This threshold is designed to handle outliers.
bb_smooth – (default: 0.1) the black-box differentiation smoothing parameter.
verbose – (default: False) print verbose information for parameter tuning
backend – (default:
pygmtools.BACKEND
variable) the backend for computation.
- Returns
the multi-graph matching result (a
MultiMatchingResult
object)
Note
In PyTorch and Jittor backends, this function is differentiable through the black-box trick. See the following paper for details:
Vlastelica M, Paulus A., Differentiation of Blackbox Combinatorial Solvers, ICLR 2020
If you want to disable this differentiable feature, please detach the input tensors from the computational graph.
Note
Setting
verbose=True
may help you tune the parameters.Numpy Example
>>> import numpy as np >>> import pygmtools as pygm >>> import itertools >>> import time >>> pygm.BACKEND = 'numpy' >>> np.random.seed(1) # Generate 10 isomorphic graphs >>> graph_num = 10 >>> As, X_gt, Fs = pygm.utils.generate_isomorphic_graphs(node_num=4, graph_num=10, node_feat_dim=20) # Compute node-wise similarity by inner-product and Sinkhorn >>> W = np.matmul(np.expand_dims(Fs,axis=1), np.expand_dims(Fs.swapaxes(1, 2),axis=0)) >>> W = pygm.sinkhorn(W.reshape(graph_num ** 2, 4, 4)).reshape(graph_num, graph_num, 4, 4) # Solve the multi-matching problem >>> X = pygm.gamgm(As, W) >>> matched = 0 for i, j in itertools.product(range(graph_num), repeat=2): ... matched += (X[i,j] * X_gt[i,j]).sum() >>> acc = matched / X_gt.sum() >>> acc 1.0 # This function supports graphs with different nodes (also known as partial matching) # In the following we ignore the last node from the last 5 graphs >>> ns = np.array([4, 4, 4, 4, 4, 3, 3, 3, 3, 3], dtype='i4') >>> for i in range(graph_num): ... As[i, ns[i]:, :] = 0 ... As[i, :, ns[i]:] = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... X_gt[i, j, ns[i]:, :] = 0 ... X_gt[i, j, :, ns[j]:] = 0 ... W[i, j, ns[i]:, :] = 0 ... W[i, j, :, ns[j]:] = 0 # Partial matching is challenging and the following parameters are carefully tuned >>> X = pygm.gamgm(As, W, ns, n_univ=4, sk_init_tau=.1, sk_min_tau=0.01, param_lambda=0.3) # Check the partial matching result >>> matched = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... matched += (X[i,j] * X_gt[i, j, :ns[i], :ns[j]]).sum() >>> matched / X_gt.sum() 1.0
Pytorch Example
>>> import torch >>> import pygmtools as pygm >>> import itertools >>> import time >>> pygm.BACKEND = 'pytorch' >>> _ = torch.manual_seed(1) # Generate 10 isomorphic graphs >>> graph_num = 10 >>> As, X_gt, Fs = pygm.utils.generate_isomorphic_graphs(node_num=4, graph_num=10, node_feat_dim=20) # Compute node-wise similarity by inner-product and Sinkhorn >>> W = torch.matmul(Fs.unsqueeze(1), Fs.transpose(1, 2).unsqueeze(0)) >>> W = pygm.sinkhorn(W.reshape(graph_num ** 2, 4, 4)).reshape(graph_num, graph_num, 4, 4) # Solve the multi-matching problem >>> X = pygm.gamgm(As, W) >>> matched = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... matched += (X[i,j] * X_gt[i,j]).sum() >>> acc = matched / X_gt.sum() >>> acc tensor(1.) # This function is differentiable by the black-box trick >>> W.requires_grad_(True) # tell PyTorch to track the gradients >>> X = pygm.gamgm(As, W) >>> matched = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... matched += (X[i,j] * X_gt[i,j]).sum() >>> acc = matched / X_gt.sum() # Backward pass via black-box trick >>> acc.backward() >>> torch.sum(W.grad != 0) tensor(128) # This function supports graphs with different nodes (also known as partial matching) # In the following we ignore the last node from the last 5 graphs >>> ns = torch.tensor([4, 4, 4, 4, 4, 3, 3, 3, 3, 3], dtype=torch.int) >>> for i in range(graph_num): ... As[i, ns[i]:, :] = 0 ... As[i, :, ns[i]:] = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... X_gt[i, j, ns[i]:, :] = 0 ... X_gt[i, j, :, ns[j]:] = 0 ... W[i, j, ns[i]:, :] = 0 ... W[i, j, :, ns[j]:] = 0 >>> W = W.detach() # detach tensor if gradient is not needed # Partial matching is challenging and the following parameters are carefully tuned >>> X = pygm.gamgm(As, W, ns, n_univ=4, sk_init_tau=.1, sk_min_tau=0.01, param_lambda=0.3) # Check the partial matching result >>> matched = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... matched += (X[i,j] * X_gt[i, j, :ns[i], :ns[j]]).sum() >>> matched / X_gt.sum() tensor(1.)
Paddle Example
>>> import paddle >>> import pygmtools as pygm >>> import itertools >>> import time >>> pygm.BACKEND = 'paddle' >>> _ = paddle.seed(1) # Generate 10 isomorphic graphs >>> graph_num = 10 >>> As, X_gt, Fs = pygm.utils.generate_isomorphic_graphs(node_num=4, graph_num=10, node_feat_dim=20) # Compute node-wise similarity by inner-product and Sinkhorn >>> W = paddle.matmul(Fs.unsqueeze(1), Fs.transpose((0, 2, 1)).unsqueeze(0)) >>> W = pygm.sinkhorn(W.reshape((graph_num ** 2, 4, 4))).reshape((graph_num, graph_num, 4, 4)) # Solve the multi-matching problem >>> X = pygm.gamgm(As, W) >>> matched = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... matched += (X[i,j] * X_gt[i,j]).sum() >>> acc = matched / X_gt.sum() >>> acc Tensor(shape=[1], dtype=float32, place=Place(cpu), stop_gradient=True, [1.]) # This function supports graphs with different nodes (also known as partial matching) # In the following we ignore the last node from the last 5 graphs >>> ns = paddle.to_tensor([4, 4, 4, 4, 4, 3, 3, 3, 3, 3], dtype=paddle.int32) >>> for i in range(graph_num): ... As[i, ns[i]:, :] = 0 ... As[i, :, ns[i]:] = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... X_gt[i, j, ns[i]:, :] = 0 ... X_gt[i, j, :, ns[j]:] = 0 ... W[i, j, ns[i]:, :] = 0 ... W[i, j, :, ns[j]:] = 0 >>> W = W.detach() # detach tensor if gradient is not needed # Partial matching is challenging and the following parameters are carefully tuned >>> X = pygm.gamgm(As, W, ns, n_univ=4, sk_init_tau=.1, sk_min_tau=0.01, param_lambda=0.3) # Check the partial matching result >>> matched = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... matched += (X[i,j] * X_gt[i, j, :ns[i], :ns[j]]).sum() >>> matched / X_gt.sum() Tensor(shape=[1], dtype=float32, place=Place(cpu), stop_gradient=True, [0.88424438])
Jittor Example
>>> import jittor as jt >>> import pygmtools as pygm >>> import itertools >>> import time >>> pygm.BACKEND = 'jittor' # Generate 10 isomorphic graphs >>> graph_num = 10 >>> As, X_gt, Fs = pygm.utils.generate_isomorphic_graphs(node_num=4, graph_num=10, node_feat_dim=20) # Compute node-wise similarity by inner-product and Sinkhorn >>> W = jt.matmul(Fs.unsqueeze(1), Fs.transpose(1, 2).unsqueeze(0)) >>> W = pygm.sinkhorn(W.reshape(graph_num ** 2, 4, 4)).reshape(graph_num, graph_num, 4, 4) # Solve the multi-matching problem >>> X = pygm.gamgm(As, W) >>> matched = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... matched += (X[i,j] * X_gt[i,j]).sum() >>> acc = matched / X_gt.sum() >>> acc jt.Var([1.], dtype=float32) # This function supports graphs with different nodes (also known as partial matching) # In the following we ignore the last node from the last 3 graphs >>> ns = [4, 4, 4, 4, 4, 3, 3, 3, 3, 3] >>> for i in range(graph_num): ... As[i, ns[i]:, :] = 0 ... As[i, :, ns[i]:] = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... X_gt[i, j, ns[i]:, :] = 0 ... X_gt[i, j, :, ns[j]:] = 0 ... W[i, j, ns[i]:, :] = 0 ... W[i, j, :, ns[j]:] = 0 >>> ns = jt.int32(ns) >>> W = W.detach() # detach tensor if gradient is not needed # Partial matching is challenging and the following parameters are carefully tuned >>> X = pygm.gamgm(As, W, ns, n_univ=4, sk_init_tau=.1, sk_min_tau=0.01, param_lambda=0.3) # Check the partial matching result >>> matched = 0 >>> for i, j in itertools.product(range(graph_num), repeat=2): ... matched += (X[i,j] * X_gt[i, j, :ns[i].item(), :ns[j].item()]).sum() >>> matched / X_gt.sum() jt.Var([1.], dtype=float32)
Note
If you find this graph matching solver useful in your research, please cite:
@article{gamgm1, title={Graduated assignment algorithm for multiple graph matching based on a common labeling}, author={Sol{\'e}-Ribalta, Albert and Serratosa, Francesc}, journal={International Journal of Pattern Recognition and Artificial Intelligence}, volume={27}, number={01}, pages={1350001}, year={2013}, publisher={World Scientific} } @article{gamgm2, title={Graduated assignment for joint multi-graph matching and clustering with application to unsupervised graph matching network learning}, author={Wang, Runzhong and Yan, Junchi and Yang, Xiaokang}, journal={Advances in Neural Information Processing Systems}, volume={33}, pages={19908--19919}, year={2020} }
This algorithm is originally proposed by paper
gamgm1
, and further improved by papergamgm2
to fit modern computing architectures like GPU.