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

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