Matching¶
Graph Matching¶

class
graspologic.match.
GraphMatch
(n_init=1, init='barycenter', max_iter=30, shuffle_input=True, eps=0.1, gmp=True, padding='adopted')[source]¶ This class solves the Graph Matching Problem and the Quadratic Assignment Problem (QAP) through an implementation of the Fast Approximate QAP Algorithm (FAQ) (these two problems are the same up to a sign change) [1].
This algorithm can be thought of as finding an alignment of the vertices of two graphs which minimizes the number of induced edge disagreements, or, in the case of weighted graphs, the sum of squared differences of edge weight disagreements. The option to add seeds (known vertex correspondence between some nodes) is also available [2].
Parameters: n_init : int, positive (default = 1)
Number of random initializations of the starting permutation matrix that the FAQ algorithm will undergo.
n_init
automatically set to 1 ifinit_method
= 'barycenter'init : string (default = 'barycenter') or 2darray
The initial position chosen
If 2darray, init must be \(m' x m'\), where \(m' = n  m\), and it must be doubly stochastic: each of its rows and columns must sum to 1.
"barycenter" : the noninformative “flat doubly stochastic matrix,” \(J=1 \times 1^T /n\) , i.e the barycenter of the feasible region
"rand" : some random point near \(J, (J+K)/2\), where K is some random doubly stochastic matrix
max_iter : int, positive (default = 30)
Integer specifying the max number of FrankeWolfe iterations. FAQ typically converges with modest number of iterations.
shuffle_input : bool (default = True)
Gives users the option to shuffle the nodes of A matrix to avoid results from inputs that were already matched.
eps : float (default = 0.1)
A positive, threshold stopping criteria such that FW continues to iterate while Frobenius norm of \((P_{i}P_{i+1}) > \text{eps}\)
gmp : bool (default = True)
Gives users the option to solve QAP rather than the Graph Matching Problem (GMP). This is accomplished through trivial negation of the objective function.
padding : string (default = 'adopted')
Allows user to specify padding scheme if A and B are not of equal size. Say that A and B have \(n_1\) and \(n_2\) nodes, respectively, and \(n_1 < n_2\).
"adopted" : matches A to the best fitting induced subgraph of B. Reduces the affinity between isolated vertices added to A through padding and lowdensity subgraphs of B.
"naive" : matches A to the best fitting subgraph of B.
Attributes: perm_inds_ : array, size (n,) where n is the number of vertices in the fitted graphs.
The indices of the optimal permutation (with the fixed seeds given) on the nodes of B, to best minimize the objective function \(f(P) = \text{trace}(A^T PBP^T )\).
score_ : float
The objective function value of for the optimal permutation found.
n_iter_ : int
Number of FrankWolfe iterations run. If
n_init > 1
,n_iter_
reflects the number of iterations performed at the initialization returned.References
[Refcf056df51c1] 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. [Refcf056df51c2] D. Fishkind, S. Adali, H. Patsolic, L. Meng, D. Singh, V. Lyzinski, C. Priebe, Seeded graph matching, Pattern Recognit. 87 (2019) 203–215 
fit
(self, A, B, seeds_A=[], seeds_B=[])[source]¶ Fits the model with two assigned adjacency matrices
Parameters: A : 2darray, square
A square adjacency matrix
B : 2darray, square
A square adjacency matrix
seeds_A : 1darray, shape (m , 1) where m <= number of nodes (default = [])
An array where each entry is an index of a node in
A
.seeds_B : 1darray, shape (m , 1) where m <= number of nodes (default = [])
An array where each entry is an index of a node in B The elements of
seeds_A
andseeds_B
are vertices which are known to be matched, that is,seeds_A[i]
is matched to vertexseeds_B[i]
.Returns:  self : returns an instance of self

get_params
(self, deep=True)¶ Get parameters for this estimator.
Parameters: deep : bool, default=True
If True, will return the parameters for this estimator and contained subobjects that are estimators.
Returns: params : mapping of string to any
Parameter names mapped to their values.

set_params
(self, **params)¶ Set the parameters of this estimator.
The method works on simple estimators as well as on nested objects (such as pipelines). The latter have parameters of the form
<component>__<parameter>
so that it's possible to update each component of a nested object.Parameters: **params : dict
Estimator parameters.
Returns: self : object
Estimator instance.

fit_predict
(self, A, B, seeds_A=[], seeds_B=[])[source]¶ Fits the model with two assigned adjacency matrices, returning optimal permutation indices
Parameters: A : 2darray, square
A square adjacency matrix
B : 2darray, square
A square adjacency matrix
seeds_A : 1darray, shape (m , 1) where m <= number of nodes (default = [])
An array where each entry is an index of a node in
A
.seeds_B : 1darray, shape (m , 1) where m <= number of nodes (default = [])
An array where each entry is an index of a node in
B
The elements ofseeds_A
andseeds_B
are vertices which are known to be matched, that is,seeds_A[i]
is matched to vertexseeds_B[i]
.Returns: perm_inds_ : 1d array, some shuffling of [0, n_vert)
The optimal permutation indices to minimize the objective function
