pygmtools.classic_solvers.astar

pygmtools.classic_solvers.astar(K, n1=None, n2=None, n1max=None, n2max=None, beam_width=0, backend=None)[source]

A* (A-star) solver for graph matching (Lawler’s QAP). The A* solver was originally proposed to solve the graph edit distance (GED) problem. It finds the optimal matching between two graphs (which is equivalent to an edit path between them) by priority search.

Here we implement the A* solver with Hungarian heuristic. See the following paper for more details: An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems

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

  • beam_width – (default: 0) Size of beam-search witdh (0 = no beam).

  • backend – (default: pygmtools.BACKEND variable) the backend for computation.

Returns

\((b\times n_1 \times n_2)\) the doubly-stochastic matching matrix

Warning

If beam_width==0, the algorithm will find the optimal solution, and it may take a very long time. You may set a beam_width to lower the size of the search tree, at the cost of losing the optimal guarantee.

Note

Graph matching problem (Lawler’s QAP) and graph edit distance problem are two sides of the same coin. If you want to transform your graph edit distance problem into Lawler’s QAP, first compute the edit cost of each node pairs and edge pairs, then place them to the right places to get a cost matrix. Finally, build the affinity matrix by \(-1\times\) cost matrix.

You can get your customized cost/affinity matrix by build_aff_mat().

Note

This function also supports non-batched input, by ignoring all batch dimensions in the input tensors.

PyTorch Example
>>> import torch
>>> import pygmtools as pygm
>>> pygm.set_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 = torch.tensor([4] * batch_size)
>>> 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 A*
>>> X = pygm.astar(K, n1, n2)
>>> X[0]
tensor([[0., 1., 0., 0.],
        [0., 0., 0., 1.],
        [0., 0., 1., 0.],
        [1., 0., 0., 0.]])

# Accuracy
>>> (X * X_gt).sum() / X_gt.sum()
tensor(1.)

# If beam_width=0, the solver will do an exhaustive search over the entire space and can be inefficient.
# Consider setting a non-zero beam width to make it more efficient, especially for larger-sized problems
>>> X = pygm.astar(K, n1, n2, beam_width=1)

# This function also supports non-batched input, by ignoring all batch dimensions in the input tensors.
>>> X_0 = pygm.astar(K[0], n1[0], n2[0])

>>> X_0.shape
torch.Size([4, 4])

# Accuracy
>>> (X_0 * X_gt[0]).sum() / X_gt[0].sum()
tensor(1.)

Note

If you find this graph matching solver useful in your research, please cite:

@inproceedings{astar,
  title={Speeding Up Graph Edit Distance Computation with a Bipartite Heuristic.},
  author={Riesen, Kaspar and Fankhauser, Stefan and Bunke, Horst},
  booktitle={Mining and Learning with Graphs},
  pages={21--24},
  year={2007}
}