Zero-Assignment Constraint for Graph Matching with Outliers
Fudong Wang Nan Xue Jin-Gang Yu Gui-Song Xia
cs.CV







Zero-Assignment Constraint for Graph Matching with Outliers
    Fudong Wang^1,
        Nan Xue^1,
        Jin-Gang Yu^2,
        Gui-Song Xia^1Corresponding author

^1Wuhan University, China

{fudong-wang, xuenan, guisong.xia}@whu.edu.cn

^2South China University of Technology, China

jingangyu@scut.edu.cn






    December 30, 2023
=============================================================================================================================================================================================================================================================





	Graph matching (GM), as a longstanding problem in computer vision and pattern recognition, still suffers from numerous cluttered outliers in practical applications. To address this issue, we present the zero-assignment constraint (ZAC) for approaching the graph matching problem in the presence of outliers. The underlying idea is to suppress the matchings of outliers by assigning zero-valued vectors to the potential outliers in the obtained optimal correspondence matrix. We provide elaborate theoretical analysis to the problem, , GM with ZAC, and figure out that the GM problem with and without outliers are intrinsically different, which enables us to put forward a sufficient condition to construct valid and reasonable objective function. Consequently, we design an efficient outlier-robust algorithm to significantly reduce the incorrect or redundant matchings caused by numerous outliers.
    Extensive experiments demonstrate that our method can achieve the state-of-the-art performance in terms of accuracy and efficiency, especially in the presence of numerous outliers.





§ INTRODUCTION

In many real applications of computer vision and pattern recognition, the feature sets of interest represented as graphs are usually cluttered with numerous outliers <cit.>, which often reduce the accuracy of GM. Although recent works on GM <cit.> can achieve satisfactory results for simple graphs that consist of only inliers or a few outliers, they still lack of ability to tolerate numerous outliers arising in complicated graphs. Empirically, the inliers in one graph are nodes that have highly-similar corresponding nodes in the other graph, while the outliers do not. Based on the empirical criterion, the aforementioned methods hope to match inliers to inliers correctly and force outliers to only match outliers. However, due to the complicated mutual relationships between inliers and outliers, they usually result in incorrect matchings between inliers or redundant matchings between outliers  (, Fig. <ref> (a)).




In this paper, we are motivated to address this challenge by introducing the zero-assignment constraint for outliers: unlike the previous methods that hope to match outliers only to outliers, it's more reasonable to suppress the matchings of outliers. Equivalently, we try to assign each potential outlier with a zero-valued vector (, the zero-assignment constraint for outliers) in the solution of our objective function (, the correspondence matrix in Fig. <ref> (b)). 

To make our idea more reasonable and practical, we try our efforts in two aspects. First, based on the zero-assignment constraint, we establish the theoretical bases including the formulation of inliers and outliers and the quantitative distinguishability between them, and then find out a sufficient condition such that the proposed objective function can only achieve its minimum at the ideal matching. Moreover, it also helps to demonstrate the intrinsic differences between GM with and without numerous outliers. Second, we propose an efficient GM algorithm consisting of fast optimization and explicit outlier identification. The optimization algorithm is modified based on the Frank-Wolfe method <cit.> combined with the k-cardinality linear assignment problem <cit.> and has low space and time complexity. And then, the zero-assignment vectors in the optimal solution of our objective function can be used to assign the nodes in two graphs with joint probabilities, which measure whether the nodes are inliers or outliers and help to identify and remove the potential outliers in practice.



Our main contributions are summarized as follows:

	
  - We establish the theoretical foundations for GM problem with outliers based on the zero-assignment constraint and elaborate quantitative analyses of inliers and outliers, on which bases we can theoretically put forward a sufficient condition to guide us how to construct valid and reasonable objective function.
	
	
  - We present an efficient GM algorithm with low space and time complexity by avoiding using the costly affinity matrix  and designing fast optimization algorithm. Combined with our outlier identification approach, we can achieve state-of-the-art performance for complicated graphs cluttered with numerous outliers.







§ RELATED WORK


Known to be NP-complete <cit.>, the GM problem can only be solved in polynomial time with approximate solutions. Over the past decades, a myriad of literature have been extensively studied (see <cit.> for surveys), we discuss the most related works in the following aspects.

Robustness to outliers. 
The dual decomposition approach <cit.> constructed a penalty potential in the objective function for unmatched features. The max-pooling-based method <cit.> was proposed to  avoid the adverse effect of false matches of outliers. A domain adaptation-based outlier-removal strategy proposed in <cit.> aimed to remove outliers as a pre-processing step. However, they directly rely on empirical criterions of outliers and can not deal with complicated situations. In our work, we both explain theoretical analyses of outliers and present an efficient outlier identification approach, by which we can achieve much better matching accuracy in complicated applications.

Interpretability for graph matching.
The probability-based works <cit.> formulated GM from the maximum-likelihood estimation perspective. A random walk view <cit.> was introduced by simulating random walks with re-weighting jumps for GM. Some machine learning-based works <cit.> went further to adjust attributes of graphs or improve the affinity matrix 𝐊 (in Eq. (<ref>)) based on priors learned from real data. A functional representation framework <cit.> was proposed to give geometric insights for both general and Euclidean GM. The pioneering works <cit.> presented an end-to-end deep learning framework for GM. Our work aims to establish the mathematical foundation for GM with outliers and enhance its theoretical rationality.


Computational efficiency.
Some existing works aimed to reduce the costly space complexity caused by 𝐊 in Eq. (<ref>). A typical work was the factorized graph matching <cit.>, which factorized 𝐊 as Kronecker product of several smaller matrices.  However, it is highly time-consuming in practice due to the verbose iterations during optimization. Some methods like the graduated assignment method <cit.> and the integer-projected fixed point algorithm <cit.> proposed specific fast approximations while ended with unsatisfactory matching results. As comparison, our method has low space and time complexity and achieves better trade-off between time consumption and matching accuracy.




§ GRAPH MATCHING WITH OUTLIERS

This section revisits the general formulation of GM and presents the theoretical foundation for GM with outliers.



 §.§ General formulation of graph matching

Given two attributed graphs  𝒢={𝒱,ℰ},𝒢'={𝒱',ℰ'}, where 𝒱={V_i}_i=1^m and 𝒱'={V'_a}_a=1^n represent the node sets (assume m≤ n), ℰ⊆𝒱×𝒱 and ℰ'⊆𝒱'×𝒱' denote the edge sets. Generally, for each graph, , 𝒢, the edges are represented by a (weighted) adjacency matrix ℰ∈ℝ^m× m, where ℰ_ij > 0 if there is an edge (V_i,V_j), and ℰ_ij=0 otherwise. In practice, graph 𝒢 is usually associated with node  attribute 𝐯_i∈ℝ^d_v of node V_i and edge attribute 𝐀_ij∈ℝ^d_e of edge ℰ_ij; the same to graph 𝒢'.

Solving GM problem is to find an optimal binary correspondence 𝐏∈{0,1}^m× n ,
where 𝐏_ia=1 when the nodes V_i∈𝒱 and V'_a∈𝒱' are matched, and 𝐏_ia=0 otherwise. To find such an optimal correspondence, GM methods generally minimize or maximize an objective function that measures the mutual (dis-)similarity between graphs.

As a typical Quadratic Assignment Problem (QAP), GM formulated as Lawler's QAP <cit.> has been favored to maximize the sum of node and edge similarities

    max_𝐏∈𝒫𝐏_v^T𝐊𝐏_v =
    	∑_i,a𝐏_ia𝐊_ia;ia + ∑_(i,j),(a,b)𝐏_ia𝐊_ij;ab𝐏_jb,
where 𝐏_v is the columnwise vectorized replica of 𝐏. The affinity matrix 𝐊∈ℝ^mn× mn has diagonal element 𝐊_ia;ia measuring the node affinity calculated with node attributes (𝐯_i,𝐯'_a) and non-diagonal element 𝐊_ia;jb measuring the edge affinity calculated with edge attributes (𝐀_ij,𝐁_ab).

Another famous formulation is Koopmans-Beckmann's QAP <cit.>, which maximizes a trace-form objective function measuring the node and edge similarities

    max_𝐏∈𝒫tr(𝐔^T𝐏)+λtr(ℰ𝐏ℰ'𝐏^T),
where {𝐔_ia}∈ℝ^m× n measures the node similarity between V_i and V'_a and λ≥ 0 is a weight. 








Generally, GM methods impose the one-to-(at most)-one constraint, , the feasible field 𝒫 can be defined as

    𝒫≜{𝐏∈{0,1}^m× n; 𝐏1=1,𝐏^T1≤1},
where 1 is a columnwise unit vector. In fact, Eq. (<ref>) means that both inliers and outliers are equally treated to find their correspondences. Some methods like <cit.> replace 𝐏1=1 by 𝐏1≤1 to relax the one-to-(at most)-one constraint. However, they still lack of intrinsic theoretical analyses for the numerous outliers arising in both graphs.






 §.§ Zero-assignment constraint for outliers


As stated previously in Sec. <ref>, we aim to only match inliers to inliers and suppress the matchings of outliers. To achieve our goal, we present the zero-assignment constraint for outliers in this section. Denoting the number of inliers in 𝒢' and 𝒢 as k (0<k≤ m≤ n), for better understanding, we first introduce some basic definitions in the following.


	Denote 𝒜={1,2,...,m} as the index set of nodes in graph 𝒢. The index sets of inliers and outliers of 𝒢 are respectively defined as,	
	
    𝒜_I    ≜{i∈{1,2,...,m};𝒱_i  is an inlier of 𝒢},
    𝒜_O    ≜{o∈{1,2,...,m};𝒱_o  is an outlier of 𝒢}.

	The index sets ℬ={1,2,...,n}, ℬ_I and ℬ_O are similarly defined for graph 𝒢'. Obviously, we have |𝒜_I|=|ℬ_I|=k. The inliers and outliers sets are complementary and disjoint.
	


	
    𝒜_I∪𝒜_O=𝒜,  𝒜_I∩𝒜_O=∅,
       ℬ_I∪ℬ_O=ℬ,  ℬ_I∩ℬ_O=∅.

	where ∅ denotes the empty set.


Next, we derive the zero-assignment constraint for outliers. Mathematically, the matching between 𝒢 and 𝒢' consisting of inliers and outliers can be defined by a partial permutation τ and a partial permutation matrix 𝐏 as follows.
 The partial permutation τ between 𝒢 and 𝒢' is defined as τ : 𝒜→ℬ,
	
    i↦ a=τ(i)∈ℬ_I  if  i∈𝒜_I; a=∅ if  i∈𝒜_O.

	 And the inverse of τ can also be defined as τ^-1 : ℬ→𝒜,
	 
    a↦ i=τ^-1(a)∈𝒜_I  if  a∈ℬ_I; i=∅ if  a∈ℬ_O.

 


Given τ, the matching (or correspondence) between 𝒢 and 𝒢' can be equivalently expressed by the partial permutation matrix 𝐏∈{0,1}^m× n compatible with τ as

 For 𝐏∈{0,1}^m× n compatible with τ,
	
		
  - One-to-one constraint for inliers: ∀ i∈𝒜_I,
	
    𝐏_i,a=τ(i)=1,𝐏_i,a≠τ(i)=0, a∈ℬ_I.

	
  - Zero-assignment constraint for outliers: 
	
    𝐏_i,:≡0^T, ∀ i∈𝒜_O  and 𝐏_:,a≡0, ∀ a∈ℬ_O.

	
where 𝐏_i,: (or 𝐏_:,a) is a row (or column) vector of 𝐏, and 0 is a columnwise zero vector.	



By this means, the feasible filed 𝒫_k can be redefined as

    {𝐏∈{0,1}^m× n; 𝐏1≤1,𝐏^T1≤1,1^T𝐏1=k}.
	
The explicit equation constraint 1^T𝐏1=k will be used to both present a proof for the rationality of our proposed objective function in Sec. <ref> and design an efficient optimization algorithm in Sec. <ref>.



 §.§ Consistency and distinguishability

Empirically, the GM methods assume that the unary and pairwise attributes of inlier i∈𝒜_I and edge (i,j)∈𝒜_I×𝒜_I are consistent with those of the ideal matchings a∈ℬ_I and (a,b)∈ℬ_I×ℬ_I, while the outliers are on the contrary. Based on this empirical criterion, we furthermore elaborate a quantitative consistency of inliers and distinguishability between inliers and outiers, on which bases the rationality of our objective function can be guaranteed. 

Denote {𝐃_ia}_ia as the dissimilarity between nodes V_i∈𝒱 and V_a'∈𝒱', {𝐀_ij}_ij and {𝐁_ab}_ab are the edge attributes of edges (V_i,V_j)∈ℰ and (V'_a,V'_b)∈ℰ'. Meanwhile, denote {τ^*,𝐏^*∈𝒫_k} as the ideal matching between 𝒢 and 𝒢'. Consequently, beyond the empirical criterion, we can induce the consistency of inliers and distinguishability between inliers and outliers by {τ^*,𝐏^*∈𝒫_k} as follows.

 Consistency between inliers.
	
	
  -Unary consistency: 
	∀ i∈𝒜_I,∀ a∈ℬ_I,
		
    𝐃_ia'=min{𝐃_ia,a∈ℬ}⇔ a'=τ^*(i),
       𝐃_i'a=min{𝐃_ia,i∈𝒜}⇔ i'=τ^*-1(a).

	
  -Pairwise consistency: 
	∀ i,j ∈𝒜_I,∀ a,b ∈ℬ_I,
		
    ||𝐀_ij-𝐁_a'b'||    = min{||𝐀_ij-𝐁_ab||,a,b∈ℬ}
       ⇔ a'=τ^*(i),b'=τ^*(j),
    
    			||𝐁_ab-𝐀_i'j'||    = min{||𝐁_ab-𝐀_ij||,i,j∈𝒜}
       ⇔ i'=τ^*-1(a),j'=τ^*-1(b).

	

 Distinguishability between inliers and outliers.
	
	
  -Unary distinguishability:
	∀ (i,a)∈𝒜_O×ℬ or 𝒜×ℬ_O,
	
    𝐃_ia≥max{𝐃_i'τ^*(i'),i'∈𝒜_I}.

	
  -Pairwise distinguishability:
	∀ (i,a),(j,b) ∈𝒜_O×ℬ or  𝒜×ℬ_O,
	
    ||𝐀_ij-𝐁_ab|| 
    	   ≥max{||𝐀_i'j'-𝐁_τ^*(i')τ^*(j')||
               ,i',j'∈𝒜_I},
    
    	||𝐁_ab-𝐀_ij|| 
    	   ≥max{||𝐁_a'b'-𝐀_τ^*-1(a')τ^*-1(b')||
               ,a',b'∈ℬ_I}.

	
where ||·|| is an Euclidean norm.

By this means, we present a quantitative mathematical criteria of the local characteristics and mutual relationships of inliers and outliers, which is more concise and clear than empirical criteria. More importantly, the propositions above inspires us how to construct a reasonable objective function and find out a sufficient condition for proving the rationality.



 §.§ Objective function with sufficient condition

A reasonable objective function F(𝐏) should satisfy two main properties: (1) preserve the unary and pairwise consistencies between the matched nodes (or edges) of two graphs and (2) achieve its optimum only at the ideal matching 𝐏^*. Overall, our objective function is defined as

    min_𝐏∈𝒫_k F(𝐏)=λ_1 F_u(𝐏)+λ_2F_p(𝐏),
where F_u(𝐏) and F_p(𝐏) are the unary and pairwise potentials. Precisely, we set F_u(𝐏)=∑_ia𝐃_ia𝐏_ia and

    F_p(𝐏)   ≜ F_p_1(𝐏) + F_p_2(𝐏)
       ≜∑_ijℰ_ij||𝐀_ij-∑_a,b𝐏_ia𝐁_ab𝐏_jb ||^2 
          +∑_abℰ'_ab||𝐁_ab-∑_i,j𝐏_ia𝐀_ij𝐏_jb||^2
       ≜||𝐀-𝐏𝐁𝐏^T ||_ℰ^2 + ||𝐁-𝐏^T𝐀𝐏||_ℰ'^2.


The property (1) is guaranteed since the minimization of F(𝐏) tends to find the minimizer 𝐏̂ that matches the nodes and edges in 𝒢 (or 𝒢') to the mostly-consistent nodes and edges in 𝒢' (or 𝒢). Next, we should make sure that it also satisfies the property (2). However, due to the cluttered outliers arising in both graphs, it may not hold for any arbitrarily given weighted adjacency matrices ℰ,ℰ' or edge attributes 𝐀,𝐁. Furthermore, we put forward a sufficient condition to support it. 

Sufficient condition for objective function. Assume that the weighted adjacency matrices ℰ,ℰ' and  edge attributes 𝐀,𝐁 satisfy that
	
    ℰ_i∈𝒜_I,j∈𝒜_I   ≥ℰ_i∈𝒜,j∈𝒜_O, ℰ_i∈𝒜_O,j∈𝒜,
    
    		||𝐀_i∈𝒜_I,j∈𝒜_I||
    		   ≥ ||𝐀_i∈𝒜,j∈𝒜_O||, ||𝐀_i∈𝒜_O,j∈𝒜||,

	and the same to ℰ' and 𝐁. Then, it's sufficient to prove that 
	
    ∀𝐏∈𝒫_k,  F(𝐏)≥ F(𝐏^*),
the equation holds if and only if  𝐏=𝐏^*.
	



 Due to the over-length of the entire proof, we give the details in our supplementary materials, which also demonstrate the intrinsic differences between GM on simple graphs and on complicated graphs.


Note that, the Eq. (<ref>) and (<ref>) tell us how to calculate proper {ℰ_ij}, {𝐀_ij} (or {ℰ'_ab}, {𝐁_ab}): we should compute ℰ_ij and 𝐀_ij to measure the similarities between the two end-nodes in edge (i,j) such that edges linked by two inliers have higher similarities than the edges linked by inlier-outlier or outlier-outlier. It will be followed and validated in the experiments section Sec. <ref>.



§ OUTLIER-ROBUST GRAPH MATCHING ALGORITHM


In this section, we propose an efficient algorithm to solve Eq. (<ref>) and then design an outlier identification approach.



 §.§ Optimization algorithm

Our optimization algorithm is based on the Frank-Wolfe method <cit.>, which is widely used for convex or non-convex optimization and achieve at least sub-linear convergence rate. Since it is a continuous line-search-based method, we should relax the discrete 𝒫_k into the continuous 𝒫̂_k by relaxing 𝐏_ia∈{0,1} into 𝐏_ia∈[0,1]. Given F(𝐏) is differentiable and 𝒫̂_k is convex, the Frank-Wolfe method iterates the following steps till it converges:

    𝐏̃^(t+1)   ∈argmin_𝐏∈𝒫̂_k≜⟨∇ F(𝐏^(t)),𝐏⟩,
    𝐏^(t+1)   =𝐏^(t) + α^(t)(𝐏̃^(t+1)-𝐏^(t)),
where ∇ F(𝐏^(t)) is the gradient of F(𝐏) at 𝐏^(t) and α^(t) is the step size obtained by exact or inexact line search <cit.>. 

Gradient computation. The gradient ∇ F(𝐏) can be efficiently calculated by matrix operations as follows,

    𝐖_1≜ 4||𝐏𝐁𝐏^T-𝐀||⊗sign(𝐏𝐁𝐏^T-𝐀)⊗ℰ,
       𝐖_2≜ 4||𝐏^T𝐀𝐏-𝐁||⊗sign(𝐏^T𝐀𝐏-𝐁)⊗ℰ',
       ∇ F(𝐏)=λ_1 𝐃 + λ_2 [𝐖_1𝐏𝐁^T+𝐀𝐏𝐖_2^T],
where ⊗ is the pointwise multiplication and sign(·) is the sign function.


The k-cardinality LAP. Eq. (<ref>) plays a key role of the optimization. It is a linear programming (LP) problem that can be solved by LP algorithms like interior point method <cit.>. However, such methods have costly time complexity O(m^3n^3/ln(mn)) <cit.>. Fortunately, one can prove that 𝐏̃^(t+1) is an extreme point <cit.> of 𝒫̂_k, thus, 𝐏̃^(t+1)∈𝒫_k. Therefore, Eq. (<ref>) boils down to a k-cardinality linear assignment problem (kLAP) <cit.>. We can adopt the approach <cit.> by which the kLAP is transformed into a standard LAP that can be efficiently solved by the Hungarian <cit.> or LAPJV <cit.> algorithm with much less time complexity O(n^3).

Regularization. Someone may doubt that the explicit equation constraint 1^T𝐏1=k in the feasible filed is too strong. We can replace it with an implicit regularization term (1^T𝐏1-k)^2 and obtain a new objective function as

    min_𝐏 F_r(𝐏,k)= F(𝐏)+λ_0(1^T𝐏1-k)^2.

We set λ_0=1 is this paper. To solve Eq. (<ref>), we can adopt the alternating optimization strategy: alternatively find the minimizer 𝐏̂ of Eq. (<ref>) by Frank-Wolfe method with fixed k and then update k=1^T𝐏̂1. Note that, in this case, Eq. (<ref>) is solved by LP algorithms (interior point method in this paper) rather than the kLAP solvers since the constraint 1^T𝐏1=k dose not hold during solving Eq. (<ref>).

Computational complexity. Since we do not use the affinity matrix 𝐊, the space complexity is only O(n^2). In optimization, each iteration takes time complexity O(n^3) to solve the k-LAP or O(m^3n^3/ln(mn)) to solve the LP, and O(m^2n+mn^2) to compute the values and gradients of objective function. We are advised to adopt the kLAP-based approach based on the experimental analyses in Sec. <ref>.









 §.§ Outlier identification and removal


After minimizing F(𝐏) or F_r(𝐏,k), we obtain an optimal correspondence matrix 𝐏̂ that has two advantages beneficial to outlier identification: (1) 𝐏̂ optimally preserves the structural alignments between the two matched graphs. (2) The nearly zero-valued vectors 𝐏̂_i,:≈0^T or 𝐏̂_:,a≈0 indicate that the node V_i∈𝒢 or V_a'∈𝒢' can be identified as outliers, as an example shown in Fig. <ref> (a).

An outlier removal approach is proposed based on this outlier identification criterion. Given 𝐏̂, we first calculate two vectors as 𝐏̂1={𝐏̂_i,:1}_i=1^m and 1^T𝐏̂={1^T𝐏̂_:,a}_a=1^n, whose components with smaller values are more likely to be outliers. Then, 𝐏̂1 and 1^T𝐏̂ form the 2-dimensional coordinates of coupled nodes {(V_i, V_a')}_i,a in the joint probability space, where the inliers and outliers can be significantly separated and clustered (, by k-means) into two classes, see an example in Fig. <ref> (b). Assume that m',n' nodes of the two graphs are clustered as inliers by the clustering step, if m'<k or n'<k, we pick out k-m' or k-n' nodes left with higher component values and put them back into inliers. If m'>k or n'>k, the nodes with component values less than 0.5 will also be chosen as outliers. We iteratively execute this outlier removal procedure and then refine the inliers of two graphs till the enumerations of inliers keep unchanged. At last, the optimal solution solved w.r.t the refined graphs is our final matching result.








§ EXPERIMENTAL ANALYSIS


In this section, we evaluate and compare our methods (denoted as ZAC w.r.t. Eq. (<ref>) and ZACR w.r.t Eq. (<ref>)) with state-of-the-art graph matching methods including GA <cit.>, RRWM <cit.>, MPM <cit.>, FGMD <cit.>, BPFG <cit.> and FRGM <cit.> on widely used complicated datasets in terms of matching accuracy and time consumption. The codes of the compared methods are downloaded from the author’s websites. Our code is available at <https://github.com/wangfudong/ZAC_GM>. For better evaluation of graph matching in the presence of outliers, we compute the commonly used indicators called recall =#{correct matching}/#{groundtruth matching}, precision =#{correct matching}/#{total matching} and F-measure=2recall·precision/recall+precision. 



 §.§ Results on PASCAL dataset
 


We first conducted experiments on graphs in PASCAL dataset <cit.>, which consists of 30 and 20 pairs of car and motorbike images (, Fig. <ref>), respectively. Each pair contains both inliers with known correspondence and randomly marked dozens of outliers. To generate graphs with outliers, we randomly selected 0, 4, ..., 20 outliers to both graphs, respectively. To generate the edges, our methods and FRGM applied complete graphs, while the others connected edges by Delaunay Triangulation, on which they achieved better performance than on complete graphs.

Similar with <cit.>, we set 𝐊_ia;ia=exp(-d(𝐯_i-𝐯_a')),
and 𝐊_ia;jb=exp(-1/2(|𝐄_ij-𝐄'_ab|+|Θ_ij-Θ'_ab|)), where 𝐯_i,𝐯_a' were shape context <cit.>, d(𝐯_i-𝐯_a') was the cost computed as χ^2 test statistic <cit.>, 𝐄_ij,𝐄_ab' were distance matrices between nodes, Θ_ij, Θ'_ab were the angles between the edges and the horizontal line. 
For our methods, we calculated 𝐃_ia=d(𝐯_i-𝐯_a') to measure the node dissimilarity. For the weighted adjacency matrices ℰ,ℰ' and edge attributes 𝐀_ij,𝐁_ab, in order to honor the proposition <ref>, we set ℰ=1⊘𝐄,ℰ'=1⊘𝐄' and 𝐀=exp(-𝐄^2/σ_1^2),𝐁=exp(-𝐄'^2/σ_2^2) with σ_1,σ_2 were the standard deviations of 𝐄,𝐄'. The weights in Eq. (<ref>) were λ_1=λ_2=1. 



First, we presented a statistical verification for proposition <ref>. For each graph pair with outliers, we randomly disturbed the ideal correspondences between inliers by forcing 0,1,...,20 inliers to be incorrectly matched. Then, we applied our optimization algorithm to minimize the objective function Eq. (<ref>) under the mismatching constraints. We reported the series of obtained minimum values of objective function in Fig. <ref>. It shows that, with increasing number of disturbed matchings of inliers, the minimum values of objective function become higher. Only with no mismatchings (, the ideal ground-truth 𝐏^*), the objective function achieves the lower limit of the series of minimum values. Namely, the proposition <ref> can be guaranteed with our settings and optimization algorithm in practical cases.








Next, we compared all the methods in terms of matching accuracy and time consumption. For overall comparisons, we set a series of numbers k=⌊ ratio·min{m,n}⌋ (ratio=0.3,0.35,...,1 such that k≥ 5 since m,n∈[15,75]) in feasible fields 𝒫̂_k for our method. And then, we also ran the compared methods with their soft-assignment matrix and evaluated their matching accuracy with the top k matchings. Note that, since the methods FGMD <cit.> and BPFG <cit.> only obtain binary correspondences, we can only compute their matching accuracy with top k=1·min{m,n} matchings. 


Fig. <ref> shows the highest average F-measure of all methods w.r.t the numbers of outliers. We can see that our methods ZAC and ZACR are more robust to outliers.  
Particularly, as shown in Fig. <ref>, with a wide range of ratio, our methods achieve much higher precision, which means that the proposed outlier identification and removal approach can efficiently reduce incorrect or redundant matchings. Tab. <ref> reports the average time consumption, our methods take acceptable and intermediate time. Since the regularization term in Eq. (<ref>) is more flexible than the equation constraint 1^T𝐏1=k, ZACR has a little higher accuracy than ZAC. However, as mentioned in Sec. <ref>, since ZAC solves kLAP while ZACR uses LP solver, ZAC runs much faster than ZACR. Overall, ZAC achieves better trade-off between matching accuracy and time consumption than ZACR.










 §.§ Results on VGG dataset
 

As the example shown in Fig. <ref>, graph pairs in PASCAL dataset are generated with similar shapes. Thus, the experiments above evaluate the performance of all the methods in terms of shape consistency. Furthermore, we conducted experiments on more practical dataset to evaluate all the GM methods with more complicated graphs under varying geometric or physical factors. 

We adopted the widely used VGG dataset[<http://www.robots.ox.ac.uk/ vgg/research/affine/>] that consists of 8 groups of images (with sizes near 1000×1000) and each group has 6 images with varying blurring, viewpoint, rotation, light, zoom and JPEG compression (see examples in supplementary material). For each group, there exist 5 affine matrices 𝐇_1s∈ℝ^3×3, s=2,...,6 that represent the ground-truth affine transformation from image 1 to images 2–6, respectively. We first formed graph pairs 𝒢,𝒢' between image 1 and images 2–6 in each group. Then, we utilized feature detector SIFT <cit.> to generate nodes of graphs. Note that, since the compared methods FGMD, BPFG and MPM were highly time consuming with large-scale complete graphs, we adjusted the threshold of SIFT such that the numbers of output features were around 100 and neglected repeated features. We computed the settings as the same as in PASCAL dataset except that {𝐯,𝐯_a'} were SIFT features and set λ_1=10,λ_2=1. 






An output matching result was evaluated as follows:  for each node V_i∈𝒢 matched with V'_a_i∈𝒢', we calculated its correct correspondence V'_σ_i=𝐇_1sV_i using the ground-truth affine matrix 𝐇_1s. Then, if the distance ||V'_a_i-V'_σ_i|| was less than 10 pixels, the matching between V_i and V'_a_i was accepted as a correct matching. We set k with varying ratio=0.1,0.15,...,1 for the evaluation of recall and precision. Moreover, we also evaluated our time consumption w.r.t the varying ratio, since the number of nodes in refined graphs obtained by our outlier identification and removal approach will be influenced by ratio. Note that, the time consumption of the other methods will not be affected by ratio since they match all the nodes in graphs.


As shown in Fig. <ref>, under the varying geometric or physical conditions, our methods ZAC and ZACR can achieve much higher recall and precision. Fig. <ref> (a) shows the overall average matching accuracy and time consumption w.r.t. varying ratio, our method ZAC and ZACR have much better matching accuracy within much less time consumption, even though on complicated graphs with numerous outliers and varying geometric or physical factors in practice.




 §.§ Deformable graph matching


Deformable graph matching (DGM) <cit.> is an important subproblem of GM, which focuses on incorporating rigid or non-rigid deformations between graphs. The main idea is to estimate both the correspondence 𝐏 and deformation parameters τ by minimizing the sum of residuals

    min_𝐏,τ J(𝐏,τ)=∑_i,a𝐏_ia||V'_a-τ(V_i)||^2 + λ_rΥ(τ),
where V_i,V'_a∈ℝ^d are the nodes in 𝒱,𝒱', and Υ(·) is a regularization term. Generally, the rigid or non-rigid deformation is parameterized as τ(𝒱)=s𝒱𝐑+t or τ(𝒱)=𝒱+𝐖𝐆. See <cit.> for more comprehensive reviews. 





















Finding correct correspondence 𝐏 plays the central role for solving Eq. (<ref>). Once 𝐏 is well-estimated, the geometric parameter τ can be solved with closed form <cit.>. In this section, we applied all the GM methods with k=0.5×min{m,n} to find 𝐏 and then computed τ. We iteratively executed this procedure till it converges. All the GM methods applied the same settings used in Sec. <ref> except that the node attributes 𝐯_i,𝐯'_a were shape context here.  


We adopted the widely used 2D shape templates in <cit.> for evaluation and comparison. We uniformly sampled 50% points of the shape template as inliers of 𝒢 and 𝒢'. And slight noises with uniform distribution U(0,0.01) were also added to 𝒢 and 𝒢'. 

In this section, we conducted two series of experiments on graphs with varying deformations and outliers. First, we measured the robustness of each algorithm to rotations in rigid deformation. We rotated 𝒢' with varying degrees in [-π,π] and then randomly added 10–50 outliers with Gaussian distribution N(0,0.5) to both 𝒢 and 𝒢'. Second, we evaluated the robustness to outliers. For the rigid deformation, we randomly rotated 𝒢' with degrees in [-0.1π,0.1π]. For the non-rigid deformation, we deformed 𝒢' following the settings in <cit.> by weight matrices 𝐖 with Gaussian distribution N(0,0.5). And then, we incrementally added {0%,20%,...,100%}·#inliers numbers of outliers with Gaussian distribution N(0,0.5) to 𝒢 and 𝒢'. See examples in Fig. <ref>. For all GM methods, we adopted the rotation-invariant shape context advised by <cit.> for rigid deformations. For evaluation, we computed the average error between the transformed inliers {τ(V_i)} and their ground-truth matching point {V'_δ_i}, , 1/#inliers∑_i||τ(V_i)-V'_δ_i||.

Fig. <ref> shows the average errors of all the methods w.r.t. varying rotations. We can see that our methods ZAC and ZACR can nearly perfectly recover and match all the  graphs across all the rotations. Fig. <ref> reports the average errors and time consumptions on graphs with rigid and nonrigid deformations. Our methods have much less average error than all the other methods and runs faster than most of them. Note that, we did not compare BPFG due to its extremely unacceptable time consumption (more than 5 hours to match only one pair of graphs) in this experiment.


For more comprehensive evaluation, we also compared with two efficient point registration algorithms GLS <cit.> and CPD <cit.>, which can address the deformable graph matching problem from the perspective of point registration. The comparison results are shown in Tab. <ref>, our methods ZAC and ZACR achieve comparable results with GLS and CPD for graphs without outliers, and have less average errors for complicated graphs with numerous outliers.























































































§ CONCLUSION

This paper presents the zero-assignment constraint to address the problem of graph matching in the presence of outliers. Beyond the empirical criterion, we propose both theoretical foundations and quantitative analyses for this problem, on which bases we are inspired to construct reasonable objective function and find out the sufficient condition for its rationality. Moreover, we propose an efficient algorithm consisting of fast optimization and outlier identification, which ensures us to handle complicated graphs with numerous cluttered outliers in practice and achieve state-of-the-art performance in terms of accuracy and efficiency. In future work, we will go further to consolidate the theoretical foundation of graph matching problem with outliers by extending the zero-assignment constraint to the famous QAP formulations of graph matching in Eq. (<ref>) and Eq. (<ref>).



§ ACKNOWLEDGEMENT

This work was supported by the National Natural Science Foundation of China under Grant 61771350 and Grant 61922065.

















ieee_fullname




[pages=1]1149-supp.pdf
[pages=2]1149-supp.pdf
[pages=3]1149-supp.pdf
[pages=4]1149-supp.pdf
[pages=5]1149-supp.pdf
[pages=6]1149-supp.pdf
[pages=7]1149-supp.pdf
[pages=8]1149-supp.pdf


