Adaptively Transforming Graph Matching
Fudong Wang Nan Xue Yipeng Zhang Xiang Bai Gui-Song Xia


 


Adaptively Transforming Graph Matching







Lastnames, Firstnames

F. Wang et al.



State Key Lab. LIESMARS, Wuhan University, China 

	{fudong-wang, xuenan, guisong.xia}@whu.edu.cn
School of Computer Science, Wuhan University, China

zyp91@whu.edu.cn


EIS, Huazhong University of Science and Technology, China

xbai@hust.edu.cn

Adaptively Transforming Graph Matching
    Fudong Wang1 Nan Xue1 Yipeng Zhang2 Xiang Bai3 Gui-Song Xia1corresponding author
    December 30, 2023
====================================================================================




Recently,  many graph matching methods that incorporate pairwise constraint and that can be formulated as a quadratic assignment problem (QAP) have been proposed.
Although these methods demonstrate promising results for the graph matching problem, they have high complexity in space or time. 
In this paper, we introduce an adaptively transforming graph matching (ATGM) method from the perspective of functional representation.
More precisely, under a transformation formulation, we aim to match two graphs by minimizing the discrepancy between the original graph and the transformed graph. With a linear representation map of the transformation, the pairwise edge attributes of graphs are explicitly represented by unary node attributes, which enables us to reduce the space and time complexity significantly. Due to an efficient Frank-Wolfe method-based optimization strategy, we can handle graphs with hundreds and thousands of nodes within an acceptable amount of time. 
Meanwhile, because transformation map can preserve graph structures, a domain adaptation-based strategy is proposed to remove the outliers.
The experimental results demonstrate that our proposed method outperforms the state-of-the-art graph matching algorithms.








§ INTRODUCTION

Graph matching is widely used in a wide range of computer vision and pattern recognition tasks <cit.> to find correspondence between two graph-structured feature sets.
The general idea behind graph matching solutions is to minimize objective functions composed of unary, pairwise <cit.> or higher-order <cit.> potentials to preserve the structure alignment between two graphs.



Under pairwise constraint, graph matching can be formulated as a quadratic assignment problem (QAP) <cit.>, which is NP-complete <cit.>, and only approximate solutions can be found in polynomial time.
Although the past decade has witnessed remarkable progress on graph matching <cit.>, there are still some challenges in computational complexity and matching performance.
For instance, a costly affinity matrix often needs to be computed or factorized <cit.>, which results in high space complexity–especially with large-scale complete graphs. 
Because of the combinatorial nature of QAP, the objective function is difficult to solve for obtaining binary solutions <cit.>.
Although with relaxation, the discrete constraint can be approximated by a continuous one that is easier to solve, this approach requires extra effort to achieve a global optimum or satisfy the binary constraint <cit.>.
Moreover, matching unequal-sized graphs often suffer from outliers <cit.>. Thus, it is of great interest to reduce the computational complexity and to be as robust as possible to outliers.

This paper introduces a method for graph matching from the perspective of functional representation.
The main idea is illustrated by a toy example in Fig. <ref>. 
Under this perspective, one graph is transformed into the space spanned by the second graph, and then, a desired correspondence can be reformulated as an optimal transformation map between graphs. 
To pursue such a  map, we construct two functionals to measure the discrepancy between graphs and minimize them with the Frank-Wolfe method <cit.>.
Using the transformation map, the pairwise edge attributes of graphs can be explicitly represented by node attributes, which enables us to significantly reduce the space and time complexity. We also propose a domain adaptation-based strategy to remove outliers leveraging the fact that transformation maps can preserve graph structures. 

Our work is distinguished in following aspects:

	
  - We present a new perspective for graph matching that explicitly represents the pairwise edge attributes of graphs using unary node attributes. Therefore,
	the space complexity is reduced in form from 𝐎(m^2n^2) to 𝐎(mn) and
	the objective function can be optimized efficiently with 𝐎(Tn^3) time complexity. Benefiting from this simplification, we can match large-scale graphs, even with complete graphs.
	
	
  - We propose a domain adaptation-based method for outlier removal using the transformation map. This technique can be used as a pre-processing step to improve graph matching algorithms.





§ RELATED WORK


Over the past few decades, both exact and inexact (error-tolerant) graph matching have been extensively studied to measure either (dis-)similarity <cit.> or find correspondence <cit.> between graphs. We focus on inexact graph matching to find correspondence as the work on exact graph matching and measuring similarity (e.g., graph edit distance) is beyond the scope of this paper. 

Many existing works of pairwise graph matching have addressed reducing the high computational complexity of the QAP formulation. In the path-following method proposed in <cit.>, the author rewrote the graph matching problem as an approximate least-squares problem on the set of permutation matrices. A factorization-based method <cit.> was proposed to factorize the affinity matrix with high space complexity into a Kronecker product of smaller matrices. An efficient sampling heuristic has been proposed in <cit.> to avoid the high space complexity of the affinity matrix. However, the methods in <cit.> suffer from huge time consumption in practice, and the ability to reduce space complexity of the works <cit.> is limited by complete graphs. As a comparison, our functional representation-based method can reduce the space complexity by two orders of magnitude with a lower time complexity and runs faster in practice.

Considering looking for global optimal solutions with binary property for graph matching, the approaches in <cit.> constructed objective functions in both convex and concave relaxations that were controlled by a continuation parameter. However, these approaches are often time consuming in reaching an ideal solution. Moreover, to ensure binary solutions, an integer-projected fixed point algorithm <cit.> solving a sequence of first-order Taylor approximations had been proposed, and the author of <cit.> took an adaptive and dynamic relaxation mechanism for optimization in the discrete domain directly. In our method, we separately construct non-convex and convex relaxations and obtain (nearly) binary solutions in a faster way with high matching accuracy.

In addition, several spectral matching methods <cit.> were introduced based on the rank-1 approximation of the affinity matrix. The graduated assignment method <cit.> iteratively solved a series of convex approximations of the objective. The decomposition-based works in <cit.> and <cit.> decomposed the original complex graphs and took decomposition of the matching constraints,respectively. Probability-based <cit.> and learning-based <cit.> methods gave further interpretations of the graph matching problem.  A random walk view <cit.> of the problem was introduced by simulating random walks with re-weighting jumps. A max-pooling based strategy has been also proposed in <cit.> to address the presence of outliers. These two works <cit.> are both robust to outliers due to their re-weighting procedure during iterations. In contrast, our proposed outlier-removal strategy removes the outliers by explicitly relying on the global structure of graphs, and it can be applied to other methods as a pre-processing step.




§ GENERAL GRAPH MATCHING


Given an undirected graph 𝒢_X={X,ℰ_X}
with m nodes X_i∈ X,  i=1,…, m, we denote each edge as X_i_1i_2≜(X_i_1,X_i_2)∈ℰ_X, where
ℰ_X is the edge set consisting of M edges.
Matching the two graphs 𝒢_X and 𝒢_Y, with m,n nodes and M,N edges, respectively, yields a binary correspondence 𝐏∈{0,1}^m× n,
such that P_ij=1 when the nodes X_i and Y_j are matched and P_ij=0 otherwise.

The graph matching problem is often solved by maximizing an objective function that measures the node and edge affinities between 𝒢_X and 𝒢_Y.
Under pairwise constraints, the objective function typically consists of a unary potential w_v(X_i,Y_j) and a pairwise potential w_e(X_i_1i_2,Y_j_1j_2), which measure the similarity between the nodes X_i and Y_j and the edges X_i_1i_2 and Y_j_1j_2, respectively.
These two types of similarities are usually integrated by an affinity matrix 𝐖∈ℝ^mn× mn, the diagonal element 𝐖_ij,ij of which corresponds to the unary potential w_v(X_i,Y_j) and the non-diagonal element 𝐖_i_1j_1,i_2j_2 of which corresponds to the pairwise potential w_e(X_i_1i_2,Y_j_1j_2).
Thus, the objective function for graph matching can be written as

    𝐏_v^T𝐖𝐏_v = ∑_P_ij=1w_v(X_i,X_j) + ∑_P_i_1j_1=1
    P_i_2j_2=1w_e(X_i_1i_2,Y_j_1j_2),

where 𝐏_v is the column-wise vectorized replica of 𝐏.

For graph matching under one-to-(at most)-one
constraints, the feasible field 𝒫 is composed of all (partial) permutation matrices (where m≤ n), i.e.

    𝒫≜{𝐏∈{0,1}^m× n; 𝐏𝐈_n=𝐈_m,𝐏^T𝐈_m≤𝐈_n},

where 𝐈_m is a m × 1 unit vector.
Then, the graph matching problem can be approached by finding the optimal assignment matrix 𝐏^* by maximizing

    max_𝐏∈𝒫 𝐏_v^T𝐖𝐏_v.


Eq.(<ref>) is the so-called (QAP), which is known to be NP-complete. Usually, an approximate solution of it can be found by relaxing the discrete feasible field 𝒫 into a continuous feasible filed 𝒫̂ as:

    𝒫̂≜{𝐏∈ [0,1]^m× n; 𝐏𝐈_n=𝐈_m,𝐏^T𝐈_m≤𝐈_n},

which is known as the doubly-stochastic relaxation.
Unfortunately, (1) the affinity matrix 𝐖 results in high space complexity–especially with complete graphs, and (2) achieving global optimal or binary solutions of Eq.(<ref>) is often highly time consuming.





§ ADAPTIVELY TRANSFORMING GRAPH MATCHING


This section presents our ATGM algorithm starting with a definition of the linear representation map of transformation from one graph to the space spanned by another graph. Basically, the transformation map models the correspondence between graphs. On this basis, we first measure the edge discrepancy between two graphs to derive the sub-optimal transformation map. Then, we incorporate the shifting vectors of the transformed nodes to obtain the final optimal transformation map. Finally, we address the unequal size cases in graph matching by proposing a domain adaptation-based outlier removal strategy.



 §.§ Linear representation of transformation

Given two undirected graphs 𝒢_X={X,ℰ_X } and 𝒢_Y={Y,ℰ_Y }, we formulate graph matching as transformation from node set X={X_i }_i=1^m to the space spanned by Y={Y_j }_j=1^n. Because X,Y are discrete sets, we first define the continuous space spanned by Y as 𝒞_Y=∑_i=1^n α_jY_j. Transformation 𝒯 from X to 𝒞_Y is defined as

    𝒯: X →𝒞_Y, X_i ↦𝒯(X_i).


According to linear algebra, 𝒯(X_i) can be represented as 𝒯(X_i)≜∑_j=1^n𝐏_ijY_j. Then, 𝐏∈ℝ^m× n is a linear representation (i.e., a transformation map) of 𝒯. By the constraint Eq.(<ref>) that 𝐏∈𝒫̂, each node 𝒯(X_i) lies in the convex hull of Y. Therefore, we redefine 𝒞_Y as the convex hull of Y for graph matching problem. Whenever 𝐏 reaches an extreme point of the feasible field 𝒫̂, it is a binary assignment matrix, and consequently, X_i is transformed to (i.e., matches) a Y_j' where 𝐏_ij' =1,𝐏_i,j≠ j'=0.

By this representation formulation, the transformed graph X̅≜𝒯(X)=𝐏Y is determined by specified 𝐏 and Y. The more 𝐏 is binary, the more X̅ is similar to Y. Therefore, we can replace 𝒢_Y by 𝒢_X̅ when we attempt to minimize the disagreement between 𝒢_X and 𝒢_Y by forcing 𝐏 to be binary. 
With notation X̅_i_1i_2≜(X̅_i_1,X̅_i_2), we construct the functional w.r.t. 𝐏 to measure disagreement between 𝒢_X and 𝒢_X̅ as

    𝔽(𝐏)=∑_(i,j)f_v(X_i,Y_j)P_ij + ∑_(i1,i_2) f_e(X_i_1i_2,X̅_i_1i_2),

where the unary potential f_v(X_i,Y_j) denotes the disagreement between nodes X_i and Y_j, and the pairwise potential f_e(X_i_1i_2,X̅_i_1i_2) denotes the discrepancy between
edge X_i_1i_2 and its transformed edge X̅_i_1i_2. Using this formulation, the costly affinity matrix 𝐖∈ℝ^mn× mn used in general graph matching is replaced by the node disagreement matrix { f_v(X_i,Y_j) }∈ℝ^m× n and the edge discrepancy matrix { f_e(X_i_1i_2,X̅_i_1i_2)}∈ℝ^m× m, which consequently reduces the space complexity from O(m^2 n^2) to O(mn).

To obtain a desired assignment matrix 𝐏^* given graphs 𝒢_X and 𝒢_Y, we can construct a specified functional 𝔽(𝐏) and minimize it to preserve the structure alignments between 𝒢_X and 𝒢_X̅ in a optimization-based way:

    𝐏^*∈argmin_𝐏∈𝒫̂𝔽(𝐏).


In the rest of this section, we introduce two functionals w.r.t. 𝐏 as our objective functions to model the pairwise graph matching problem.





 §.§ Edge discrepancy

In the case where graphs are embedded in Euclidean space ℝ^d, the function f_e mentioned above can be defined in some simple but effective forms to incorporate the edge length (or orientations),

    f_e(X_i_1i_2,X̅_i_1i_2) = (||X_i_1i_2||-||X̅_i_1i_2||)^2,

where ||X_i_1i_2|| is the l_2 norm of X_i_1i_2.

Thus, the pairwise potential of our first objective function is defined as,

    F_XY(𝐏)   =∑_(i_1,i_2)S_i_1i_2(||X_i_1i_2||-||X̅_i_1i_2||)^2, 
       =∑_(i_1i_2)S_i_1i_2( ||X̅_i_1i_2||^2-2||X_i_1i_2|| ||X̅_i_1i_2||)+c,

where c is a constant and S_i_1i_2 measures the weight of (||X_i_1i_2||-||X̅_i_1i_2||)^2 if we have priors. We denote 𝐒≜{ S_i_1i_2}∈ℝ^m× m.

The gradient of F_XY(𝐏) w.r.t. 𝐏 can be computed using the chain rule,

    ∇ F_XY(𝐏) = 2(𝐋_X+𝐋^*_X)(𝐏Y)Y^T,

where L_X=diag(SI_m)-S is the Laplacian of 𝒢_X, and 𝐋^*_X=diag(S^*I_m)-S^* with S_i_1i_2^*≜ S_i_1i_2||X_i_1i_2|| ||X̅_i_1i_2||^-1. To avoid numerical instabilities as in <cit.>, a small ϵ > 0 is added to ||X̅_i_1i_2||^-1, i.e., (||X̅_i_1i_2||+ϵ)^-1. Naturally, we can reconstruct F_XY(𝐏) by adding a unary potential such as ∑_ij f_v(X_i,Y_j)𝐏_ij + λ F_XY(𝐏).

Due to the non-convexity of F_XY(𝐏), its minimizer 𝐏^*∈𝒫̂, which is regarded as an optimal transformation map from 𝒢_X to 𝒢_X̅, often reaches a local minimum and is not binary; see Fig.<ref> (b) for illustration. Consequently, the transformed node X̅_i is usually not exactly equal to a Y_j'∈ Y, and there is often a shift between X̅_i and its correct match Y_σ_i. Fig.<ref> (a) displays this shift phenomena, where each X̅_i shifts from the correct match Y_σ_i to some degree.




 §.§ Node shifting

Benefiting from the property of F_XY(𝐏) that preserves the edge alignment between 𝒢_X and 𝒢_X̅, the shifting vectors of adjacent nodes have similar directions and norms, as shown in Fig.<ref> (a). Consequently, in order to reduce the node shifting from X̅_i to its correct match Y_σ_i, denoted by

    X̅_iY_σ_i=Y_σ_i-X̅_i,

we minimize the sum of the differences between adjacent shifting vectors, i.e.,

    G_X̅Y(𝐏)   =∑_(i_1i_2)S̅_i_1,i_2||(X̅̅̅_i_1-X̅_i_1)-(X̅̅̅_i_2-X̅_i_2)||_2^2
       =Tr((𝐏Y-X̅)^T𝐋_X̅(𝐏Y-X̅)),

where 𝐋_X̅ = diag(𝐒̅𝐈_m)-𝐒̅. We denote X̅̅̅=𝐏Y as the transformed nodes of X̅. In our method, the weight matrix 𝐒̅ is set to be positive and symmetric, therefore, 𝐋_X̅ is positive definite and G_X̅Y(𝐏) is convex.

Sparse regularization 
Because G_X̅Y(𝐏) is convex, its minimizer is often an inner point rather than an extreme point of the feasible field 𝒫̂. In order to approach a binary solution, we first add a sparse regularization term, i.e., the l_1 norm of 𝐏 to G_X̅Y(𝐏).
We denote D_ij≜ d(X̅_i,Y_j) as the distance between X̅_i and Y_j.
Benefiting from the solution of F_XY(𝐏), the norms of shifting vectors X̅_iY_σ_i are relatively small, and elements D_i,σ_i are much smaller than D_i,j≠σ_i, as shown in Fig.<ref> (f).
Thus, we also add a unary term 𝐃_X̅Y={ D_ij}∈ℝ^m× n to improve the sparsity of the minimizer.

Finally, G_X̅Y(𝐏) can be summarized as

    G_X̅Y(𝐏)=⟨𝐏,𝐃_X̅Y⟩ + λ_1 ||𝐏||_1^1+λ_2Tr((𝐏Y-X̅)^T𝐋_X̅(𝐏Y-X̅)),

where ⟨𝐏,𝐃_X̅Y⟩=∑_ij𝐏_ijD_ij. The gradient of G_X̅Y(𝐏) is then

    ∇ G_X̅Y(𝐏) =  𝐃_X̅Y + λ_1 + 2λ_2𝐋_X̅(𝐏Y-X̅)Y^T.

With this sparse regularization, the function G_X̅Y(𝐏) is always solved with a (nearly) binary solution, which significantly improves the matching accuracy. See Fig. <ref> (c) and (d) for examples.




 §.§ Outlier removal  via domain adaptation




Matching graphs 𝒢_X and 𝒢_Y of different sizes with m<n is more complicate. In this situation, the outliers occurring in graph 𝒢_Y usually affect the matching results. Thanks to the transformation map 𝐏^* achieved by minimizing F_XY(𝐏), the structure of 𝒢_X̅ is similar to that of 𝒢_X. In some sense, the operation X̅=𝐏^*Y can be seen as a domain adaptation <cit.> from the source domain X to the target domain Y. We propose a method to remove outliers adaptively by using the transformation map alternately minimized from F_XY(𝐏) and G_XY(𝐏), where G_XY(𝐏) is defined by replacing X̅ with X in the pairwise potential of G_X̅Y(𝐏):

    G_XY(𝐏)   =∑_(i_1,i_2)S_i_1i_2||(X̅_i_1-X_i_1)-(X̅_i_2-X_i_2)||_2^2
       =∑_(i_1,i_2)S_i_1i_2||(X_i_2-X_i_1)-(X̅_i_2-X̅_i_1)||_2^2,

which depicts the edge-vector differences between the original graph 𝒢_X and the transformed graph 𝒢_X̅.
The orientation of edge has also been used in many graph matching methods  <cit.> to construct the non-diagonal element of the affinity matrix as:

    𝐖_i_1j_1,i_2j_2=exp(-1/2(||X_i_1i_2||-||Y_j_1j_2||)^2-1/2(θ_i_1i_2-θ_j_1j_2)^2),

where θ_i_1i_2 is the angle between edge X_i_1i_2 and the horizontal line.

After minimizing F_XY(𝐏) or G_XY(𝐏), we obtain the transformed nodes X̅=𝐏^*Y. Consequently, 𝒢_X̅ has a structure similar to that of the original graph 𝒢_X and lies in the same coordinate system of 𝒢_Y with relatively small shifts. Then, we can remove outliers adaptively using a ratio test technique. Given two point sets X̅ and Y, we compute the Euclidean distance d_ij between all the pairs (X̅_i,Y_j).  For each node X̅_i, we find the closest node Y_j^* and remove all the nodes Y_j when d_ij>k· d_ij^* for a given k>0. If the number  of remaining nodes l is smaller than m, m-l nodes are selected from the removed nodes that are closer to X̅ and are added. The experimental results show that after several iterations of alternately minimizing F_XY(𝐏) and G_XY(𝐏) most outliers are removed (see Fig.<ref>). 

Our ATGM algorithm with outlier-removal is summarized in Algorithm <ref>.







§ NUMERICAL IMPLEMENTATION AND ANALYSIS

As presented above, we construct two objective functions, namely, a non-convex F_XY(𝐏) and a convex G_X̅Y(𝐏). 
Previous methods, e.g., <cit.>, relaxed their objective functions in both convex and concave forms as 𝐉_v and 𝐉_c, respectively, and solved a series of combined functions 𝐉_λ=λ𝐉_c + (1-λ)𝐉_v controlled by a parameter λ increasing from 0 to 1. In contrast, we solve our objective functions F_XY(𝐏) and G_X̅Y(𝐏) separately by the Frank-Wolfe (FW) method <cit.>, which is simple but efficient. 

Given that g is a convex and differentiable function, and given that 𝒫̂ is  a convex set, the FW method iterates the following steps until it converges:

    𝐏̃^(k+1)∈argmin_𝐏∈𝒫̂⟨∇ g(𝐏^(k)),𝐏⟩,
    
          𝐏^(k+1)=𝐏^(k) + α^(k)(𝐏̃^(k+1)-𝐏^(k)),

where α^(k) is the step size of the iteration k obtained by a line search procedure <cit.>, and ∇ g is computed using the Eq.(<ref>) and Eq.(<ref>).

In Eq.(<ref>), the minimizer 𝐏̃^(k+1)∈𝒫̂ is theoretically an extreme point of 𝒫̂ (so is binary). This means that 𝐏̃^(k+1)∈𝒫. Therefore, Eq.(<ref>) is a linear assignment problem (LAP) that can be efficiently solved by approaches such as the Hungarian <cit.>, LAPJV <cit.> algorithm. Moreover, since 𝐏̃^(k+1) is binary in each iteration, the final solution 𝐏^* is (nearly) binary after minimizing G_X̅Y(𝐏).

Convergence The FW method ensures an at least sublinear convergence rate <cit.>, which may result in large iterations for solving the non-convex function F_XY(𝐏). However, minimizing F_XY(𝐏) within 200 iterations is sufficient because its solution will be applied as the initialization for minimizing G_X̅Y(𝐏), which is strong convex and stronger convergence can be achieved. In our experiments, G_X̅Y(𝐏) always converges at a 10^-7 tolerance within k≤ 100 iterations. Compared to the path-following method that solves the two relaxed objective functions combined together in <cit.>, our optimization strategy is faster with higher matching accuracy.

Local optimal vs. global optimal The FW method can guarantee obtaining only a local optimum of the non-convex objective F_XY(𝐏). However, as discussed above, the local optimum for F_XY(𝐏) is applied as an initialization for solving the convex objective G_X̅Y(𝐏), which allows us to reach a global optimum.

Computational complexity For our method, the space complexity is 𝐎(mn), which is considerably smaller than the size 𝐎(m^2n^2) of most of other methods with complete graphs. The time complexity is 𝐎(Tn^3), where T is the number of iterations in the FW method. This complexity can be calculated as 𝐎(T(τ_f +τ_l) + τ_s ), where τ_s=𝐎(m^2) is the cost of the edge attribute matrices of 𝒢_X. In each iteration of the FW method, τ_f=𝐎(m^2n) is the cost to compute the gradient, function value and step size at 𝐏^(k), and τ_l=𝐎(n^3) is the cost to minimize Eq.(<ref>) using the Hungarian algorithms.



§ EXPERIMENTAL ANALYSIS

In this section, we evaluate our method ATGM on both synthetic data and real-world datasets. We compare our method with state-of-the-art methods including GA <cit.>, PM <cit.>, SM <cit.>, SMAC <cit.>, IPFP <cit.>, RRWM <cit.>, FGM <cit.> and MPM <cit.>. As suggested in  <cit.>, we use the solution of SM as the initialization for IPFP. Also, for FGM, we use the deformable graph matching method called FGM-D.

In all the experiments, to be able to apply unified parameters λ=1,λ_1=10^3, and λ_2=1, we normalize the node coordinates to [0,1] for our method. For the non-convex objective functions F_XY, we compute its unary term by using Shape Context <cit.>. For comparison, the average accuracy for each algorithm is reported. Our objective functions are different from those used by the compared methods, and thus, it does not make sense to  compare the objective scores or objective ratios.



 §.§ Results on synthetic data


We perform a comparative evaluation of ATGM on  synthesized random point sets following   <cit.>. The synthetic points of 𝒢_X and 𝒢_Y are constructed as follows: for the graph 𝒢_X, n_in  inlier points are randomly generated on ℝ^2 with the Gaussian distribution 𝒩(0,1). 
The graph 𝒢_Y with noise is generated by adding Gaussian noise 𝒩(0,σ^2) to each X_i∈ X to evaluate the robustness of the method to deformation noise. 
Graph 𝒢_Y with outliers is generated by adding n_out additional points on ℝ^2 with a Gaussian distribution 𝒩(0,1) to evaluate the robustness to outliers.

For the  compared methods, as in <cit.>, we set the edge affinity matrix 𝐖_i_1j_1,i_2j_2=exp(-(||X_i_1i_2||-||Y_j_1j_2||)^2/0.15) . We set 𝐒∈ℝ^m× m as S_i_1i_2=||X_i_1i_2||^-1  for F_XY(𝐏) an G_XY(𝐏) with fully connected 𝒢_X. For G_X̅Y(𝐏), our method performs a Delaunay triangulation on X to get its edge set ℰ̅_X, and then, ℰ̅_X is divided into two parts using k-means by considering the edge length (edges with longer lengths are abandoned). 


Memory efficiency
As analyzed in Sec.<ref>, the space complexity of our method is lower than that of compared methods.
In this experiment, we try to verify that ATGM can match graphs with low memory consumption while achieving better accuracy. 

Since the compared methods can achieve better accuracy with complete graphs, for fairness, we first applied all methods to complete graphs with a relative small size n_in=20.  We then enlarged the size to n_in=100 to test the advantages of ATGM in terms of memory efficiency. Due to the high space complexities of the other methods, we had to apply them to graphs with Delaunay triangulation. However, our method is able to use complete graphs due to its lower space complexity O(n^2).

As shown in Fig.<ref> (a) and (b), under the complete graph setting, our method achieves the highest average accuracy in the case with deformation noise and achieves competitive results in the case with outliers. 
For graphs of large size, our method outperforms all the other methods (shown in Fig.<ref> (c) and (d)). In contrast, using complete graphs with a large number of nodes with other methods is infeasible in practice. Except for PM <cit.>, all of the compared methods have to use  n_in^2(n_in+n_out)^2  units of memory , which will be extremely large for n_in=100, n_out≥ 100.  This requirement affects their application to graph matching in practice.
	



Running time To compare the time consumption of all methods, we tested them in both equal-size and unequal-size cases, namely, (1) n_in=10,20,...,100, n_out=0, σ = 0.2 and (2) n_in = 100, n_out = 10,20,...,100, σ = 0.05. Considering the effect of the number of edges on time consumption, in equal-size cases, we applied all methods to both complete and Delaunay triangulation-connected graphs. In unequal-size cases, we applied our method to complete graphs and the others to Delaunay triangulation-connected graphs so that ATGM took more edges than the others.

As shown in Fig.<ref> (a) and (b), where graphs are either complete or connected by Delaunay triangulation, our method takes an intermediate running time and achieves the highest average accuracy. As shown in Fig.<ref> (c), even though ATGM handles more edges than the other methods, it takes an acceptable time with the highest accuracy. Compared with GA, SM, PM, SMAC, and IPFP-S, which run faster, ATGM can achieve higher average accuracy. To match complete graphs, the methods RRWM, FGM, MPM can achieve competitive accuracy with ATGM. However, the time consumptions of them rapidly increase and becomes larger than that of ours.




Large-scale graph matching.
To test the efficiency of our method when applied to large-scale graphs, we carried out more challenging experiments by setting the number of inliers as n_in=100,300,500,1000 with deformation noise and outliers. The number of outliers was set to 20%,40%,...,100% of the number of inliers.

As reported in Tab.<ref>, ATGM is very robust to outliers and less robust to strong noise with larger graphs. Since the compared methods need to store affinity matrices with size of approximately n_in^2(n_in+n_out)^2, applying these methods to large-scale graphs with hundreds or thousands of nodes is infeasible. 




 §.§ Results on real-world datasets

We also perform comparative evaluations on real-world datasets, including the CMU House sequence[<http://vasc.ri.cmu.edu//idb/html/motion/house/index.html>] and the PASCAL Cars and Motorbikes pairs <cit.>, which are commonly used to evaluate graph matching algorithms.







The CMU House sequence consists of 111 frames of a synthetic house. Each image contains 30 feature points that are manually marked with known correspondences. In this experiment, we matched all the image pairs separated by 10, 20,.., 90 frames. The unequal-size cases are set as 20-vs-30 and 25-vs-30. For the compared methods, we set the edge-affinity to 𝐖_i_1j_1,i_2j_2=exp(-(||X_i_1i_2||-||Y_j_1j_2||)^2/2500) as the same as  <cit.>.

The PASCAL dataset for graph matching consists of 30 pairs of car images and 20 pairs of motorbike images. Each pair contains both inliers (approximately 30–60 feature points) with groundtruth labels and randomly marked outliers. In the unequal-size matching case, we added 5, 10, 15, 20 outliers to 𝒢_Y. For the compared methods, we set the edge affinity matrix as Eq.(<ref>) which was used in <cit.>.

Average accuracy 
For the CMU House sequence, as shown in Fig.<ref>, our method achieves a higher accuracy in both equal-size and unequal-size cases. Meanwhile, our method outperforms all the compared methods on the PASCAL datasets because our method can remove the outliers automatically. The results are shown in Fig.<ref>.

Effect of objective functions As we discussed in Sec.<ref>, the objective function G_X̅Y has effects on both the sparsity and matching accuracy. First, to evaluate the sparsity of 𝐏∈ [0,1]^m× n, we define an index S_r(𝐏)= ∑_i𝕀_(𝐏_ij≥ r)/m where 𝕀 is the indicator function. We evaluated S_r(𝐏) on the House sequence with r=0.9. As shown in Tab.<ref>, the optimal representation map 𝐏^* of G_X̅Y is (nearly) binary in all cases. Then, we evaluated the average accuracy in two cases: (1) minimizing F_XY only and (2) applying G_X̅Y after F_XY is minimized. As shown in Tab.<ref>, the average accuracy is highly improved especially in unequal-size cases due to G_X̅Y. This results shows that G_X̅Y can enhance the sparsity of the assignment matrix and reduce the node shifting.






Effectiveness on outlier removal Finally, our proposed outlier removal strategy is not restricted to our approach. It can be applied to any other method. To evaluate the generality of our outlier removal strategy, we applied it as a pre-processing step, and then executed the other methods with the pre-processed input. As shown in Tab.<ref>, the average accuracy of all the methods is improvement greatly, and almost all the methods improve their performance by more than 10%.



§ CONCLUSIONS

In this paper, we presented a new approach from a functional representation perspective for the graph matching problem by redefining the assignment matrix as a linear representation map. Our approach reduces both the space and time complexity significantly. Thus, our method is suitable for matching complete graphs with hundreds and thousands of nodes. In addition to the transformation map, we presented a domain adaptation-based method for outlier removal that improves the performance of all methods. In future work, we plan to study graph matching on more general manifolds (or metric spaces) and hyper-graph matching with lower computational complexity.



§ ACKNOWLEDGEMENT

This research is supported by projects of National Natural Science Foundation of China (NSFC) under the contracts No.61771350 and No.41501462. 







































 splncs04
 


























