pygmtools.classic_solvers.astar

pygmtools.classic_solvers.astar(feat1, feat2, A1, A2, n1=None, n2=None, channel=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

  • feat1 – \((b\times n_1 \times d)\) input feature of graph1

  • feat2 – \((b\times n_2 \times d)\) input feature of graph2

  • A1 – \((b\times n_1 \times n_1)\) input adjacency matrix of graph1

  • A2 – \((b\times n_2 \times n_2)\) input adjacency matrix of graph2

  • n1 – \((b)\) number of nodes in graph1. Optional if all equal to \(n_1\)

  • n2 – \((b)\) number of nodes in graph2. Optional if all equal to \(n_2\)

  • channel – (default: None) Channel size of the input layer. If given, it must match the feature dimension (d) of feat1, feat2. If not given, it will be defined by the feature dimension (d) of feat1, feat2. Ignored if the network object isgiven (ignored if network!=None)

  • 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.BACKEND = 'pytorch'
>>> _ = torch.manual_seed(1)

# Generate a batch of isomorphic graphs
>>> batch_size = 10
>>> nodes_num = 4
>>> channel = 36

>>> X_gt = torch.zeros(batch_size, nodes_num, nodes_num)
>>> X_gt[:, torch.arange(0, nodes_num, dtype=torch.int64), torch.randperm(nodes_num)] = 1
>>> A1 = 1. * (torch.rand(batch_size, nodes_num, nodes_num) > 0.5)
>>> torch.diagonal(A1, dim1=1, dim2=2)[:] = 0 # discard self-loop edges
>>> A2 = torch.bmm(torch.bmm(X_gt.transpose(1, 2), A1), X_gt)
>>> feat1 = torch.rand(batch_size, nodes_num, channel) - 0.5
>>> feat2 = torch.bmm(X_gt.transpose(1, 2), feat1)
>>> n1 = n2 = torch.tensor([nodes_num] * batch_size)

# Match by A* (load pretrained model)
>>> X = pygm.astar(feat1, feat2, A1, A2, n1, n2)
>>> (X * X_gt).sum() / X_gt.sum()# accuracy
tensor(1.)

# This function also supports non-batched input, by ignoring all batch dimensions in the input tensors.
>>> part_f1 = feat1[0]
>>> part_f2 = feat2[0]
>>> part_A1 = A1[0]
>>> part_A2 = A2[0]
>>> part_X_gt = X_gt[0]
>>> part_X = pygm.astar(part_f1, part_f2, part_A1, part_A2)

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

>>> (part_X * part_X_gt).sum() / part_X_gt.sum()# accuracy
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}
}