# 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, 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 matrices W 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 matrix

• ns – (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

• 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

Set verbose=True may help you tune the parameters.

Example for Pytorch backend:

>>> 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()
>>> matched / X_gt.sum()
tensor(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 = 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

# 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.)


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 paper gamgm2 to fit modern computing architectures like GPU.