# nonnegative_orthogonal_graph_matching__f104dcdd.pdf

Nonnegative Orthogonal Graph Matching

Bo Jiang,1 Jin Tang,1 Chris Ding,2,1 Bin Luo1

1School of Computer Science and Technology, Anhui University, Hefei, 230601, China 2CSE Department, University of Texas at Arlington, Arlington, TX 76019, USA jiangbo@ahu.edu.cn, ahhftang@gmail.com, chqding@uta.edu, luobin@ahu.edu.cn

Graph matching problem that incorporates pair-wise constraints can be formulated as Quadratic Assignment Problem (QAP). The optimal solution of QAP is discrete and combinational, which makes QAP problem NP-hard. Thus, many algorithms have been proposed to ﬁnd approximate solutions. In this paper, we propose a new algorithm, called Nonnegative Orthogonal Graph Matching (NOGM), for QAP matching problem. NOGM is motivated by our new observation that the discrete mapping constraint of QAP can be equivalently encoded by a nonnegative orthogonal constraint which is much easier to implement computationally. Based on this observation, we develop an effective multiplicative update algorithm to solve NOGM and thus can ﬁnd an effective approximate solution for QAP problem. Comparing with many traditional continuous methods which usually obtain continuous solutions and should be further discretized, NOGM can obtain a sparse solution and thus incorporates the desirable discrete constraint naturally in its optimization. Promising experimental results demonstrate beneﬁts of NOGM algorithm.

Introduction

Many problems of interest in computer vision and machine learning area can be formulated as a problem of ﬁnding consistent correspondences between two sets of features. This problem can usually be formulated and solved by graph matching model. From optimization aspect, previous approaches have formulated graph matching as a Quadratic Assignment Problem (QAP). It is known that the optimal solution of QAP matching problem should satisfy both discrete and mapping (one-toone or one-to-many) constraints simultaneously. This combinatorial constraints make QAP problem NP-hard. Thus many algorithms have been proposed to ﬁnd approximate solutions for graph matching problem (Enqvist, Josephon, and Kahl 2009; Leordeanu, Hebert, and Sukthankar 2009; Zhou and la Torre 2012; van Wyk and van Wyk 2004; Zaslavskiy, Bach, and Vert 2009; Liu, Qiao, and Xu 2012; Zhang et al. 2016; Adamczewski, Suh, and Lee 2015). Among them, one kind of popular methods is to use continuous optimization techniques (Gold and A 1996; Leordeanu

Copyright c 2017, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

and Hebert 2005; Cour, Srinivasan, and Shi 2006; Enqvist, Josephon, and Kahl 2009; Choi and Kweon 2009; Cho, Lee, and Lee 2010). These methods generally ﬁrst develop an approximate continuous problem for QAP by relaxing its discrete mapping constraint and then ﬁnd the optimal solution for this continuous problem. At last, they use some discretization techniques to obtain the ﬁnal permutation solution (Cho, Lee, and Lee 2010; Leordeanu and Hebert 2005). One drawback of these continuous algorithms is that the discrete constraint of QAP matching problem is entirely ignored and thus need to be further discretized to obtain a discrete solution for the problem. Obviously, this post-discretization step is independent of QAP matching objective and thus leads to weak local optimal solution (Jiang et al. 2017; Zhou and la Torre 2012). In additional to continuous algorithm, Leordeanu and Hebert (Leordeanu, Hebert, and Sukthankar 2009) also propose an iterative matching method (IPFP) which optimizes the QAP in the discrete domain and thus ﬁnds a discrete solution strictly in the optimization process. In this paper, we focus on continuous optimization methods. This paper proposes a new algorithm, called Nonnegative Orthogonal Graph Matching (NOGM), for QAP problem. NOGM is based on our new observation that the discrete mapping constraint of QAP can be equivalently encoded by a nonnegative orthogonal constraint. This motivates us to develop a multiplicative update algorithm to ﬁnd an effective solution for QAP. Comparing with many traditional continuous methods which usually obtain continuous solutions and need to be further discretized, NOGM can generate a sparse solution for the problem and thus better incorporates the desirable discrete constraint in its optimization. To the best of our knowledge, this nonnegative orthogonal constraint has not been studied or emphasized in QAP problem. Promising experimental results demonstrate the beneﬁts and effectiveness of the proposed NOGM method.

Problem Formulation and Related Works Assume that two graphs to be matched are GD = (V D, ED) and GM = (V M, EM) where V represents a set of nodes and E denotes edges. The graph matching problem, in its most recent and general from, can be formulated as Quadratic Assignment Problem (QAP) problem, i.e., ﬁnding the indicator matrix X {0, 1}n n where

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

n = |GD| = |GM|1 that maximizes the following quadratic score function (Leordeanu, Hebert, and Sukthankar 2009; Cho, Lee, and Lee 2010),

l=1 Wij,kl Xij Xkl = vec (X)TW vec (X)

s.t. X1 = 1, XT1 = 1, Xij {0, 1}. (1)

where Wij,kl measures how similar the pair of nodes (vi, vk) GD is with the pair of their corresponding nodes (vj, vl) GM in both local appearance and pair-wise geometry. The two-way afﬁne constraints ensure the one-to-one matching between nodes of graph GD and GM (Cho, Lee, and Lee 2010; Gold and A 1996). The above QAP problem (Eq.(1)) with the discrete constraint is NP-hard. Thus relaxation models and algorithms are required to ﬁnd approximate solutions (Conte et al. 2004; Zhou and la Torre 2012; Leordeanu and Hebert 2005; Cour, Srinivasan, and Shi 2006). Here, we brieﬂy review some most related relaxation works. Spectral Matching (SM): Leordeanu et al. (Leordeanu and Hebert 2005) proposed to solve the following relaxation problem,

max X vec (X)TW vec (X) (2)

s.t. vec (X)T vec (X) = 1. (3)

One main advantage of SM relaxation is that it has a global closed-form solution which is the leading eigenvector of W. Balanced Graph Matching: Cour et al. (Cour, Srinivasan, and Shi 2006) presented a tighter relaxation by further incorporating the afﬁne mapping constraint into SM relaxation (SMAC),

max X vec (X)TW vec (X) (4)

s.t. Ax = b, x Tx = 1, (5)

where x = vec (X). Similar to SM, SMAC also has a closedform eigenvector solution. However, the optimal solution is not necessarily nonnegative in SMAC. A and b are deﬁned to make constraint Ax = b represent the doubly stochastic constraint. Re-weighted Random Walk Matching (RRWM): Cho et al (Cho, Lee, and Lee 2010) introduced a probabilistic algorithm to interpret and ﬁnd a local optimal solution for the following general relaxation model, i.e., solving the matching problem in the doubly (sub-)stochastic domain,

max X vec (X)TW vec (X) (6)

s.t. X1 = 1, XT1 = 1, Xij 0. (7)

Many other algorithms, such as graduated assignment (GA) (Gold and A 1996), POCS (van Wyk and van Wyk 2004) etc, have also been developed to solve this problem.

1Here, we focus on equal size graph matching. For the graphs with different sizes, one can transform it to equal size problem by adding dummy nodes to the smaller graph.

The optimal solutions generated by the above methods are usually continuous and thus should be abruptly discretized to obtain the ﬁnal discrete solutions. This discretization step is independent of original graph matching objective and thus usually leads to weak local optimum for the original problem. This is one main drawback of these methods.

Nonnegative Orthogonal Graph Matching

In this section, we show that the discrete mapping constraint of Eq.(1) can be equivalently encoded by a nonnegative orthogonal constraint. This can be seen as follows. Using orthogonal constraint, the above QAP problem (Eq.(1)) can be equivalently formulated as,

max X vec (X)TW vec (X) (8)

s.t. XXT = I, Xij {0, 1}.

Similar to constraint of Eq.(1), the orthogonal constraint here is used to encode the one-to-one mapping between two graphs. The discrete constraint in this problem is also combinational and thus difﬁcult to implement computationally. One natural relaxation to this problem is to replace the discrete constraint Xij {0, 1} with nonnegative constraint and solve the following approximate problem, i.e.,

max X vec (X)TW vec (X) (9)

s.t. XXT = I, Xij 0.

We call it as Nonnegative Orthogonal Graph Matching (NOGM). We show that NOGM is equivalent to Eq.(8).

Proposition 1 For any matrix X, X Rn n, if X is nonnegative orthogonal, i.e., XXT = I, Xij 0, then X is a permutation matrix.

Proof. (1) Under the nonnegative constraint Xij 0, the orthogonal constraint XXT = I indicates that each row Xi of solution matrix X has only one non-zero element. (2) The orthogonal constraint XXT = I also enforces Xi XT i = 1, which indicates that the only one non-zero element in each row Xi should be equal to 1. Thus, Xij {0, 1}. Remark. Comparing with discrete constraint in original problem Eq.(8), the nonnegative constraint in NOGM (Eq.(9)) is much easier to implement computationally. To the best of our knowledge, this particular observation has not been explored before. Our aim in the following is to derive an effective multiplicative algorithm to solve NOGM problem approximately and thus can obtain an approximate solution for QAP problem.

Optimization

Recently, multiplicative update algorithms have been widely adopted in many optimization problems with nonnegative constraint (Li et al. 2007; Lee and Seung 2001; Ding, Li, and Jordan 2010; 2008; Jiang et al. 2015; Ding et al. 2006; Chen, Wang, and Zhang 2007). Inspired by these works, in this section we propose develop a new multiplicative update algorithm to solve the proposed NOGM problem.

Update algorithm

Starting from an initial matrix solution X(0), the proposed algorithm iteratively updates a current solution X(t) as follows,

X(t+1) ij = X(t) ij K(t) ij (ΔX(t))ij

where the multiplicatives Δ is computed as

2(K(t)X(t)T + X(t)K(t)T), (11)

and K(t) is the matrix form of the vector (W vec (X(t))), i.e., K(t) = mat (W vec (X(t))). The iteration starts with an initial X(0) and is repeated until convergence. Since both K(t) and Δ are nonnegative (because W is a real nonnegative symmetric matrix for the matching problem), thus the nonnegativity of X(t) is always guaranteed.

Theoretical analysis Theorem 1 Under the update rule of Eq.(10), the convergence solution satisﬁes the ﬁrst-order Karush-Kuhn-Tucker (KKT) optimality condition.

Proof. The Lagrangian function is

L(X) = vec (X)TW vec (X) Tr Δ(XXT I). (12)

Note that, since XXT I is symmetric, thus Δ is symmetric, i.e., Δ = ΔT. Thus,

L Xij = 2 (K ΔX)ij . (13)

where K is the matrix form of the vector (W vec (X)), i.e., K = mat (W vec (X)). This leads to the following KKT complementary slackness condition,

L Xij Xij = 2 (K ΔX)ij Xij = 0. (14)

Because XXT = I, summing over index j, we can obtain the diagonal elements of the Lagrangian multipliers Δ as,

(KXT)ii = (ΔXXT)ii = Δii (15)

In order to obtain the off-diagonal elements of Δ, we ignore the nonnegative constraint of X temporarily and set,

Xij = 0. (16)

Thus, we have

Δij = (KXT)ij, (i = j). (17)

Integrating Eq.(15) and Eq.(17), we have a closed form solution for the Lagrangian multipliers Δ as

Δ = KXT. (18)

Since Δ is symmetric, thus we further set Δ = 1

2(KXT + XKT). Clearly, the ﬁxed points of the update rule Eq.(10)

satisfy (K ΔX)ij X2 ij = 0, which is identical to Eq.(14). Remark. It is noted that in Eq.(18), the off-diagonal elements of the Lagrangian multipliers Δij, (i = j) are computed approximately. Therefore, the converged solution X does not satisfy the orthogonal constraint (XXT = I) strictly. In other words, update algorithm Eq.(10) generally returns an approximate solution for the proposed NOGM problem (Eq.(9)). However, although approximately, X can still satisfy the orthogonal constraint (XXT = I) strongly in the nonnegative domain and thus closes to a discrete solution. This is one important beneﬁt of the proposed update algorithm and will be further illustrated in the following section in detail. The convergence of our algorithm is guaranteed by the following theorem. Theorem 2 Under the update rule of Eq.(10), the Lagrangian function L(X) of Eq.(12) is monotonically increasing. Proof. We use the auxiliary function approach (Ding, Li, and Jordan 2010; Lee and Seung 2001). An auxiliary function function Z(X, X ) of Lagrangian function L(X) satisﬁes following,

Z(X, X) = L(X), Z(X, X ) L(X). (19)

X(t+1) = arg max X Z(X, X(t)). (20)

Then by construction, we have

L(X(t)) = Z(X(t), X(t)) Z(X(t+1), X(t)) L(X(t+1)). (21) This proves that L(X(t)) is monotonically increasing. In the following, we ﬁrst give an appropriate auxiliary function and then ﬁnd the global maximum of the auxiliary function. We rewrite Eq.(12) as

kl Wij,kl Xij Xkl Tr Δ(XXT I) (22)

We can show that one auxiliary function of L(X) can be deﬁned as

kl Wij,kl X ij X kl(1 + log Xij Xkl

X ij X kl ) (23)

(ΔX )ij X2 ij X ij .

Using the inequality z 1 + log z and setting Z = Xij Xkl

X ij X kl , the ﬁrst term of Eq.(23) is a lower bound of the ﬁrst term in Eq.(22). Also, for any positive matrices A, B, S and S with A and B symmetric, the following inequality always holds (Ding, Li, and Jordan 2010; 2008),

(AS B)ij S2 ij S ij Tr(STASB) = Tr(SBSTA). (24)

Using this equality, we can see that the second term in Eq.(23) is a lower bound of the second term in Eq.(22). Thus, Z(X, X) is an auxiliary function of L(X). According to Eq.(20), we need to ﬁnd the global maximum of Z(X, X ) for X. The gradient is

Xij = 2 (W vec (X ))ij X ij Xij (ΔX )ij Xij

Note that WT = W and the second derivative is

Xij Xkl = W vec (X )

ij X ij X2 ij + (ΔX )ij

where δuv is deﬁned as

δuv = 1 if u = v 0 otherwise. (27)

Therefore, Z(X, X ) is a concave function in X and has a unique global maximum. The global optimum can be obtained by setting the ﬁrst derivative to zero, i.e.,

ij (ΔX )ij . (28)

Therefore, we obtain the update rule in Eq.(10) by setting X(t+1) = X and X(t) = X .

Figure 1: (a) Image corner points; (b) ground truth solution (permutation matrix); (c) solution matrix X(t) across different iterations with different initializations (top: start from uniform solution; middle: start from SM solution; bottom: start from RRWM solution). Note that as the iteration increases, X(t) approximates the ground truth permutation matrix more and more closely

Figure 2: Objective function, sparsity and orthogonality of the solution vector X(t) across the iterations with different initializations under the update Eq.(10)

Orthogonality and Approximate Discrete

As discussed before, the above multiplicative update algorithm can generate an approximate solution for NOGM problem. Here, we show experimentally that although the algorithm solves NOGM problem approximately, it can still return a desired nonnegative (approximate) orthogonal and thus sparse solution for this QAP problem. This is one important beneﬁt of the proposed algorithm. Figure 1(c) shows the solution X(t) across different iterations under the update rule Eq.(10) with three different initializations on matching two graphs generated from CMU image corner points (Figure 1(a)). The feature points and their geometric relationships correspond to the nodes and edges of the graph (see Experimental section in detail). Intuitively, we note that regardless of initialization, as the iteration increases, X(t) becomes more and more sparse and approximates the ground truth (permutation matrix, Figure 1(b)) more and more closely. For further illustration, we use two measurements, namely orthogonality and sparsity. For any matrix A, the orthogonality is computed as follows. First, compute the normalized matrix N = D 1/2AATD 1/2, where D = diag(AAT). Thus, we have diag(N) = I. Then, we compute the orthogonality of matrix A as follows,

Orthogonality(A) = 1 u(N)

where u(N) denotes the average value of the off-diagonal elements in N. For any matrix A, the sparsity measures the percentage of zero (close-to-zero) elements in A. Figure 2 shows the objective, sparsity and orthogonality of the solution X(t) across different iterations under the update algorithm Eq.(10). Here, we can observe the following: (1) Regardless of initialization, the objective of X(t) increases and converges after some iterations, which demonstrates the convergence of the proposed update algorithm, as discussed in Theorem 2. (2) The orthogonality of the solution X(t) increases and almost converges to an orthogonal (permutation) matrix at convergence. It clearly indicates the strong ability of the approximate algorithm to maintain the orthogonal constraint in the nonnegative domain, although this orthogonal constraint has been partly relaxed in the algorithm, as shown in Theorem 1. (3) The solution X(t) becomes more and more sparse and converges to a desired approximate discrete solution.

Figure 3: Comparison of graph matching results on synthetic point matching with deformation noise

Experiments In order to evaluate the practicality of the proposed NOGM matching method, we have applied it to several matching tasks including synthetic graph matching, feature point matching across image sequences and feature matching on real images. Our method has been compared with some recent state-of-the-art relaxation models and algorithms including SM (Leordeanu and Hebert 2005), IPFP (Leordeanu, Hebert, and Sukthankar 2009), SMAC (Cour, Srinivasan, and Shi 2006) and RRWM (Cho, Lee, and Lee 2010). We implemented IPFP with two versions: (1) IPFPU, that is initialized by the uniform solution; (2) IPFP-S that is initialized by SM. These compared methods generally have the similar computational complexity and are most related with our NOGM algorithm.

Synthetic data In this section, we evaluated our NOGM algorithm on random graph matching problems. Following the experimental setting (Cho, Lee, and Lee 2010), we ﬁrst generated two graphs GM and GD. Both of them contain nin nodes. To evaluate the robustness of the our method w.r.t outlier nodes. Here, we added nout outlier nodes in both GM and GD. For each pair of nodes, the edge is randomly generated according to the edge density ρ [0, 1], and the attribute of the edge in GD is assigned with a random value r M ij distributed uniformly as r M ij U[0, 1]. The corresponding edge r D ij in GD was perturbed by adding a random Gaussian noise σ to r M ij . Here, σ controls the level of

deformation noise. The afﬁnity matrix W is computed by

Wij,kl = exp( r D ik r M jl 2 F σr ), where scaling factor σr has been set to 0.025 in this experiment. For each noise level σ or nout, we have generated 100 random graph pairs and then computed the average performances including matching accuracy, objective score, sparsity and orthogonality. Figure 3 summarizes the comparison results. It is noted that: (1) NOGM algorithm can always generate an approximate orthogonal and sparse solution for QAP matching problem, which demonstrates the ability of NOGM to maintain the discrete mapping constraint in its optimization. (2) NOGM generally performs better than other methods, which demonstrates the effectiveness and beneﬁts of NOGM.

Image sequence matching

We perform feature matching on CMU and YORK image sequences (Cho, Lee, and Lee 2010; Caetano et al. 2009; Luo, Wilson, and Hancock 2003). For each CMU hotel image, 30 landmark points have been manually marked with known correspondences. We have matched all images spaced by different frames and computed the average performances. For each image in YORK sequence, 40 landmark points have been manually marked with known correspondences. We have matched all images spaced by different computed the average performances per separation gap. For each pair of images in these two sequences, we have ﬁrst generated two graphs GM, GD with the nodes representing the landmark points and the edges denoting the relationship (Euclidean distance) between nodes. Figure 4 summa-

Figure 4: Comparison results across on CMU and YOKR image sequences. Top: CMU sequence; Bottom: YORK sequence

rizes results. We can observe that: (1) NOGM always generates approximate orthogonal and sparse solutions, which further demonstrates the sparse property of NOGM solution. (2) In CMU image dataset, as the separation exceeds 75, RRWM as well as IPFP, SM and SMAC generally break down, while our NOGM still keeps the desirable matching results. It suggests the robustness of NOGM algorithm. (3) In YORK image dataset, NOGM consistently outperforms other compared relaxation methods, indicating the effectiveness of NOGM .

Real-world image matching

In this section, we tested our method on some real-world image feature matching tasks. Our ﬁrst evaluation is conducted on the image pairs selected from Caltech-101 and MSRC datasets (Cho, Lee, and Lee 2010). Following the experimental setting (Cho, Lee, and Lee 2010), the candidate correspondences have been generated using the MSER detector and SIFT feature descriptors. Our second evaluation is performed on the image pairs (20 pairs) selected from Zurich Building Image Database (Zu Bud) (Ng and Kingsbury 2010). Feature points and candidate correspondences have been detected and generated using the SIFT descriptor (Ng and Kingsbury 2010). Using the distance of SIFT descriptor, each feature in ﬁrst image can match to the 8 closest features in the second image. The ground truths (correct matches) have been manually labeled for each image pair. For all image pairs in these two datasets, the average performances including true positive and false positive are computed. The comparison results are summarized in Figure 5, and some examples are shown in Figure 5. From Figure 5, we can note that NOGM algorithm returns higher true positive and lower false positive value than other comparison methods. It shows the effectiveness of the proposed NOGM method on real-world image matching tasks.

Figure 5: Matching results on the Caltech-101-MSRC and Zu Bud datasets. Correct matches are marked by yellow lines, false matches by red lines

Conclusion NOGM aims to solve QAP problem in nonnegative orthogonal domain. NOGM can generate an optimal sparse solution for QAP problem. Promising experimental results show the effectiveness of the proposed method, which further suggests that searching for an approximate optimal solution under the nonnegative orthogonal constraint may be more important or essential for optimizing QAP problem. In our future, we will explore some more effective algorithms to solve the proposed NOGM problem.

Acknowledgments This work was supported by the National Key Basic Research Program of China (973 Program) (2015CB351705); National Nature Science Foundation of China (61602001,61671018,61472002); Natural Science Foundation of Anhui Higher Education Institutions of China (KJ2016A020); Co-Innovation Center for Information Supply & Assurance Technology, Anhui University; the Open Projects Program of National Laboratory of Pattern Recognition.

References Adamczewski, K.; Suh, Y.; and Lee, K. M. 2015. Discrete tabu search for graph matching. In IEEE International Conference on Computer Vision, 109 117. Caetano, T. S.; Mc Auley, J. J.; Cheng, L.; Le, Q. V.; and Smola, A. J. 2009. Learning graph matching. PAMI 31(6):1048 1058. Chen, G.; Wang, F.; and Zhang, C. 2007. Collaborative ﬁltering using orthogonal nonnegative matrix tri-factorization. In ICDM Workshops, 303 308. Cho, M.; Lee, J.; and Lee, K. M. 2010. Reweighted random walks for graph matching. In ECCV, 492 505. Choi, O., and Kweon, I. S. 2009. Robust feature point matching by preserving local geometric consistency. CVIU 113(6):726 742. Conte, D.; Foggia, P.; Sansone, C.; and Vento, M. 2004. Thirty years of graph matching in pattern recognition. IJPRAI 18(3):265 298. Cour, M.; Srinivasan, P.; and Shi, J. 2006. Balanced graph matching. In NIPS, 313 320. Ding, C.; Li, T.; Peng, W.; and Park, H. 2006. Orthogonal nonnegative matrix t-factorizations for clustering. In KDD, 126 135. Ding, C.; Li, T.; and Jordan, M. I. 2008. Nonnegative matrix factorization for combinatorial optimization: Spectral clustering, graph matching and clique ﬁnding. In ICDM, 183 192. Ding, C.; Li, T.; and Jordan, M. I. 2010. Convex and seminonnegative matrix factorization. PAMI 32(1):45 55. Enqvist, O.; Josephon, K.; and Kahl, F. 2009. Optimal correspondences from pairwise constraints. In ICCV, 1295 1302. Gold, S., and A, R. 1996. A graduated assignment algorithm for graph matching. PAMI 18(4):377 388.

Jiang, B.; Tang, J.; Ding, C.; and Luo, B. 2015. A local sparse model for matching problem. In AAAI, 3790 3796. Jiang, B.; Tang, J.; Cao, X.; and Luo, B. 2017. Lagrangian relaxation graph matching. Pattern Recognition 61:255 265. Lee, D. D., and Seung, H. S. 2001. Algorithms for nonnegative matrix factorization. In NIPS, 556 562. Leordeanu, M., and Hebert, M. 2005. A spectral technique for correspondence problem using pairwise constraints. In ICCV, 1482 1489. Leordeanu, M.; Hebert, M.; and Sukthankar, R. 2009. An integer projected ﬁxed point method for graph macthing and map inference. In NIPS, 1114 1122. Li, H.; Adali, T.; Wang, W.; Emge, D.; and Cichocki, A. 2007. Non-negative matrix factorization with orthogonality constraints and its applications to reman spectroscopy. Journal of VLSI Signal Processing 48:83 97. Liu, Z. Y.; Qiao, H.; and Xu, L. 2012. An extended path following algorithm for graph matching problem. PAMI 34(7):1451 1456. Luo, B.; Wilson, R. C.; and Hancock, E. R. 2003. Spectal embedding of graphs. Pattern Recognition 36(10):2213 2230. Ng, E. S., and Kingsbury, N. G. 2010. Matching of interest point groups with pairwise spatial constraints. In ICIP, 2693 2696. van Wyk, B. J., and van Wyk, M. A. 2004. A pocs-based graph matching algorithm. PAMI 16(11):1526 1530. Zaslavskiy, M.; Bach, F.; and Vert, J. P. 2009. A path following algorithm for the graph matching problem. PAMI 31(12):2227 2242. Zhang, Z.; Shi, Q.; Mcauley, J.; Wei, W.; Zhang, Y.; and Hengel, A. V. D. 2016. Pairwise matching through maxweight bipartite belief propagation. In IEEE Conference on Computer Vision and Pattern Recognition. Zhou, F., and la Torre, F. D. 2012. Factorized graph matching. In CVPR, 127 134.