scipy.optimize.quadratic_assignment¶

scipy.optimize.
quadratic_assignment
(A, B, method='faq', options=None)[source]¶ Approximates solution to the quadratic assignment problem and the graph matching problem.
Quadratic assignment solves problems of the following form:
\[\begin{split}\min_P & \ {\ \text{trace}(A^T P B P^T)}\\ \mbox{s.t. } & {P \ \epsilon \ \mathcal{P}}\\\end{split}\]where \(\mathcal{P}\) is the set of all permutation matrices, and \(A\) and \(B\) are square matrices.
Graph matching tries to maximize the same objective function. This algorithm can be thought of as finding the alignment of the nodes of two graphs that minimizes the number of induced edge disagreements, or, in the case of weighted graphs, the sum of squared edge weight differences.
Note that the quadratic assignment problem is NPhard. The results given here are approximations and are not guaranteed to be optimal.
 Parameters
 A2D array, square
The square matrix \(A\) in the objective function above.
 B2D array, square
The square matrix \(B\) in the objective function above.
 methodstr in {‘faq’, ‘2opt’} (default: ‘faq’)
The algorithm used to solve the problem. ‘faq’ (default) and ‘2opt’ are available.
 optionsdict, optional
A dictionary of solver options. All solvers support the following:
 maximizebool (default: False)
Maximizes the objective function if
True
. partial_match2D array of integers, optional (default: None)
Fixes part of the matching. Also known as a “seed” [2].
Each row of partial_match specifies a pair of matched nodes: node
partial_match[i, 0]
of A is matched to nodepartial_match[i, 1]
of B. The array has shape(m, 2)
, wherem
is not greater than the number of nodes, \(n\). rngint, RandomState, Generator or None, optional (default: None)
Accepts an integer as a seed for the random generator or a
RandomState
orGenerator
object. If None (default), uses globalnumpy.random
random state.
For methodspecific options, see
show_options('quadratic_assignment')
.
 Returns
 resOptimizeResult
OptimizeResult
containing the following fields. col_ind1D array
Column indices corresponding to the best permutation found of the nodes of B.
 funfloat
The objective value of the solution.
 nitint
The number of iterations performed during optimization.
Notes
The default method ‘faq’ uses the Fast Approximate QAP algorithm [1]; it typically offers the best combination of speed and accuracy. Method ‘2opt’ can be computationally expensive, but may be a useful alternative, or it can be used to refine the solution returned by another method.
References
 1
J.T. Vogelstein, J.M. Conroy, V. Lyzinski, L.J. Podrazik, S.G. Kratzer, E.T. Harley, D.E. Fishkind, R.J. Vogelstein, and C.E. Priebe, “Fast approximate quadratic programming for graph matching,” PLOS one, vol. 10, no. 4, p. e0121002, 2015, DOI:10.1371/journal.pone.0121002
 2
D. Fishkind, S. Adali, H. Patsolic, L. Meng, D. Singh, V. Lyzinski, C. Priebe, “Seeded graph matching”, Pattern Recognit. 87 (2019): 203215, DOI:10.1016/j.patcog.2018.09.014
 3
“2opt,” Wikipedia. https://en.wikipedia.org/wiki/2opt
Examples
>>> import numpy as np >>> from scipy.optimize import quadratic_assignment >>> A = np.array([[0, 80, 150, 170], [80, 0, 130, 100], ... [150, 130, 0, 120], [170, 100, 120, 0]]) >>> B = np.array([[0, 5, 2, 7], [0, 0, 3, 8], ... [0, 0, 0, 3], [0, 0, 0, 0]]) >>> res = quadratic_assignment(A, B) >>> print(res) col_ind: array([0, 3, 2, 1]) fun: 3260 nit: 9
The see the relationship between the returned
col_ind
andfun
, usecol_ind
to form the best permutation matrix found, then evaluate the objective function \(f(P) = trace(A^T P B P^T )\).>>> perm = res['col_ind'] >>> P = np.eye(len(A), dtype=int)[perm] >>> fun = np.trace(A.T @ P @ B @ P.T) >>> print(fun) 3260
Alternatively, to avoid constructing the permutation matrix explicitly, directly permute the rows and columns of the distance matrix.
>>> fun = np.trace(A.T @ B[perm][:, perm]) >>> print(fun) 3260
Although not guaranteed in general,
quadratic_assignment
happens to have found the globally optimal solution.>>> from itertools import permutations >>> perm_opt, fun_opt = None, np.inf >>> for perm in permutations([0, 1, 2, 3]): ... perm = np.array(perm) ... fun = np.trace(A.T @ B[perm][:, perm]) ... if fun < fun_opt: ... fun_opt, perm_opt = fun, perm >>> print(np.array_equal(perm_opt, res['col_ind'])) True
Here is an example for which the default method, ‘faq’, does not find the global optimum.
>>> A = np.array([[0, 5, 8, 6], [5, 0, 5, 1], ... [8, 5, 0, 2], [6, 1, 2, 0]]) >>> B = np.array([[0, 1, 8, 4], [1, 0, 5, 2], ... [8, 5, 0, 5], [4, 2, 5, 0]]) >>> res = quadratic_assignment(A, B) >>> print(res) col_ind: array([1, 0, 3, 2]) fun: 178 nit: 13
If accuracy is important, consider using ‘2opt’ to refine the solution.
>>> guess = np.array([np.arange(len(A)), res.col_ind]).T >>> res = quadratic_assignment(A, B, method="2opt", ... options = {'partial_guess': guess}) >>> print(res) col_ind: array([1, 2, 3, 0]) fun: 176 nit: 17