Year: 2020

Abstract:
Graph matching aims to establishing node-wise correspondence between two graphs, which is a classic combinatorial problem and in general NP-complete. Until very recently, deep graph matching methods start to resort to deep networks to achieve unprecedented matching accuracy. Along this direction, this paper makes two complementary contributions which can also be reused as plugin in existing works: i) a novel node and edge embedding strategy which stimulates the multihead strategy in attention models and allows the information in each channel to be merged independently. In contrast, only node embedding is accounted in previous works; ii) a general masking mechanism over the loss function is devised to improve the smoothness of objective learning for graph matching. Using Hungarian algorithm, it dynamically constructs a structured and sparsely connected layer, taking into account the most contributing matching pairs as hard attention. Our approach performs competitively, and can also improve state-of-the-art methods as plugin, regarding with matching accuracy on three public benchmarks.

heading: 1 INTRODUCTION
text: Without loss of generality, we consider the bijection problem for graph matching: given graph G1 and G2 of equal size n, graph matching seeks to find the one-vs-one node correspondence1:
max x
x>Kx s.t. Px = 1 (1)
where x = vec(X) ∈ {0, 1}n2 which is the column-wise vectorized form of the permutation matrix X that encodes the node-to-node correspondence between two graphs, and K ∈ Rn
2×n2 + is
the so-called affinity matrix2, respectively. Note P is a selection matrix encoding the one-to-one correspondence constraint. This problem is called Lawler’s QAP (Lawler, 1963) and has attracted enormous attention for its generally NP-complete (Hartmanis, 1982) challenge, as well as a wide spectrum of applications in computer vision, graphics, machine learning and operational research etc. In particular, Koopmans-Beckmann’s QAP (Loiola et al., 2007) with objective tr(X>F1XF2) is a special case of Eq. (1), which can be converted to Lawler’s QAP by K = F2⊗F1 and Fi refers to the weighted adjacency matrix. A series of solvers haven been developed to solve graph matching problem (Leordeanu & Hebert, 2005; Cho et al., 2010; Bernard et al., 2018; Yan et al., 2015; Yu et al., 2018). All these methods are based on deterministic optimization, which are conditioned with pre-defined affinity matrix and no learning paradigm is involved. This fact greatly limits the performance and broad application w.r.t. different problem settings considering its NP-hard nature.
Recently, the seminal work namely deep graph matching (DGM) (Zanfir & Sminchisescu, 2018) is proposed to exploit the high capacity of deep networks for graph matching, which achieves stateof-the-art performance. This is in contrast to some early works which incorporate learning strategy
1We assume graphs are of equal size for narrative simplicity. One can easily handle unbalanced graph size by adding dummy nodes as a common protocol in graph matching literature (Cho et al., 2010).
2Aia:jb typically encodes the affinity between pair (i, j) and (a, b) where node i, j ∈ G1 and a, b ∈ G2.
separately in local stages (Caetano et al., 2009; Cho et al., 2013). On the other hand, Graph Convolutional Networks (GCN) (Kipf & Welling, 2017) brings about new capability on tasks over graph-like data, as it naturally integrates the intrinsic graph structure in a general updating rule:
H(l+1) = σ ( ÂH(l)W(l) ) (2)
where Â is the normalized connectivity matrix. H(l) and W(l) are the features and weights at layer l, respectively. Node embedding is updated by aggregation from 1-neighboring nodes, which is akin to the convolution operator in CNN. By taking advantages of both DGM and GCN, Wang et al. (2019) and Zhang & Lee (2019) incorporate permutation loss instead of displacement loss in (Zanfir & Sminchisescu, 2018), with notable improvement across both synthetic and real data.
Note that Eq. (1) involves both node and edge information, which exactly correspond to the diagonal and off-diagonal elements in K, respectively. Edges can carry informative multi-dimensional attributes (namely weights) which are fundamental to graph matching. However existing embedding based graph matching methods (Wang et al., 2019; Xu et al., 2019) are focused on the explicit modeling of node level features, whereby the edges are only used as topological node connection for message passing in GCN. Besides, edge attributes are neither well modeled in the embedding-free model (Zanfir & Sminchisescu, 2018) since the edge information is derived from the concatenation of node features. To our best knowledge, there is no deep graph matching method explicitly incorporating edge attributes. In contrast, edge attributes e.g. length and orientation are widely used in traditional graph matching models (Cho et al., 2010; Yan et al., 2015; Yu et al., 2018) for constructing the affinity matrix K. Such a gap shall be filled in the deep graph matching pipeline.
Another important consideration refers to the design of loss function. There are mainly two forms in existing deep graph matching works: i) displacement loss (Zanfir & Sminchisescu, 2018) similar to the use in optical flow estimation (Ren et al., 2017); ii) the so-called permutation loss (Wang et al., 2019) involving iterative Sinkhorn procedure followed by a cross-entropy loss. Results in (Wang et al., 2019) show the latter is an effective improvement against the former regression based loss. However, we argue that the continuous Sinkhorn procedure (in training stage) is yet an unnatural approximation to Hungarian sampling (in testing stage) for discretization. If the network is equipped with a continuous loss function (e.g. cross-entropy), we argue that the training process will make a great “meaningless effort” to enforce some network output digits of the final matching matrix into binary and neglect the resting digits which might have notable impact on accuracy.
This paper strikes an endeavor on the above two gaps and makes the following main contributions:
i) We propose a new approach for edge embedding via channel-wise operation, namely channelindependent embedding (CIE). The hope is to effectively explore the edge attribute and simulate the multi-head strategy in attention models (Veličković et al., 2018) by decoupling the calculations parallel and orthogonal to channel direction. In fact, edge attribute information has not been considered in existing embedding based graph matching methods (Wang et al., 2019; Xu et al., 2019).
ii) We devise a new mechanism to adjust the loss function based on the Hungarian method which is widely used for linear assignment problem, as termed by Hungarian attention. It resorts to dynamically generating sparse matching mask according to Hungarian sampling during training, rather than approximating Hungarian sampling with a differentiable function. As such, the Hungarian attention introduces higher smoothness against traditional loss functions to ease the training.
iii) The empirical results on three public benchmarks shows that the two proposed techniques are orthogonal and beneficial to existing techniques. Specifically, on the one hand, our CIE module can effectively boost the accuracy by exploring the edge attributes which otherwise are not considered in state-of-the-art deep graph matching methods; on the other hand, our Hungarian attention mechanism also shows generality and it is complementary to existing graph matching loss.

heading: 2 RELATED WORKS
text: Graph embedding. To handle graph-like data, early works adopt recursive neural networks (RNNs) treating input as directed acyclic graphs (Sperduti & Starita, 1997; Frasconi et al., 1998). Gori et al. (2005); Scarselli et al. (2008) generalized early models to graph neural networks (GNNs) so as to be directly applied on cyclic, directed or undirected graphs. Li et al. (2016) further improved this line
of model by replacing standard RNNs with gated recurrent units (GRUs) (Cho et al., 2013). Inspired by the great success of convolutional neural networks (CNNs) (Simonyan & Zisserman, 2014; He et al., 2016), researchers have made tremendous effort on applying convolution operator to graphs (Bruna et al., 2014; Kipf & Welling, 2017; Gong & Cheng, 2019). Bruna et al. (2014) defined a convolution operator in Fourier domain which is obtained by performing eigen-decomposition on graph Laplacian. However, such convolution will affect the whole spatial domain once taking inverse Fourier transformation. This method was improved by Chebyshev expansion to approximate filters (Defferrard et al., 2016). Kipf & Welling (2017) propose a graph convolutional operator over 1-neighbor nodes derived from graph spectral theory, which is invariant to node permutation and achieved significant performance on semi-supervised learning tasks. There are series of works following GCN, such as GraphSAGE (Hamilton et al., 2017), GAT (Veličković et al., 2018) and MPNN (Gilmer et al., 2017). Refer to (Cai et al., 2018) for a more comprehensive survey.
While the aforementioned models are focused on learning node state/embedding, a parallel line of work seek to learn edge embedding by taking into account the information carried on edges (Li et al., 2016; Gilmer et al., 2017; Gong & Cheng, 2019). Edges are intrinsic portion of graphs, and thus edge embedding can be essential to reveal the relation among nodes. Gilmer et al. (2017) introduce a general embedding network incorporating edge information and node-edge information merging, and a serious of works fall into this framework e.g. Gated GNN (Li et al., 2016), Tensor GNN (Schütt et al., 2017) and EGNN (Gong & Cheng, 2019). An improved version is devised in Chen et al. (2019) by interpreting this framework as maximizing mutual information across layers.
Loss for combinatorial learning. For the relatively easy linear assignment problem, it has been known that Sinkhorn algorithm (Sinkhorn, 1964) is the approximate and differentiable version of Hungarian algorithm (Mena et al., 2017). The Sinkhorn Network (Adams & Zemel, 2011) is developed given known assignment cost, whereby doubly-stochastic regulation is performed on input non-negative square matrix. Patrini et al. (2018) devise the Sinkhorn AutoEncoder to minimize Wasserstein distance, and Emami & Ranka (2018) propose to learning a linear assignment solver via reinforcement learning. For permutation prediction, DeepPermNet (Santa Cruz et al., 2018) adopts the Sinkhorn layer on top of a deep convolutional network. However this method cannot be directly applied for graph matching as it is not invariant to input permutations which is conditioned on a predefined node permutation as reference. In particular, existing supervised methods on combinatorial learning are generally cross-entropy-based. Pointer Net (Vinyals et al., 2015) incorporates cross-entropy loss on learning heuristics for combinatorial problems. Milan et al. (2017) propose an objective-based loss, where the gradients are only updated if the objective improves after update.
Learning for graph matching. The early effort (Caetano et al., 2009) aims to incorporate learning to graph matching. The key is to learn a more effective affinity function with given correspondence as supervision. While the ability by only learning affinity is limited, Cho et al. (2013) propose a matching function learning paradigm using histogram-based attributes with Structured-SVM (Tsochantaridis et al., 2005). A recent work (Zanfir & Sminchisescu, 2018) is a breakthrough to introduce deep learning paradigm into graph matching task, which utilizes a neural network to learn the affinity function. The learning procedure is explicitly derived from the factorization of affinity matrix (Zhou & De la Torre, 2012), which makes the interpretation of the network behavior possible. However, the displacement loss in (Zanfir & Sminchisescu, 2018) measures the pixel-wise translation which is similar to optical-flow (Dosovitskiy et al., 2015), being essentially a regression task instead of combinaotiral optimization. Seeing this limitation, Wang et al. (2019) employ elementwise binary cross-entropy, termed as permutation loss. This loss has proved capable of capturing the combinatorial nature rather than pixel offset, and achieves improvement over displacement loss. Node embedding is also used in (Wang et al., 2019) to explore the structure information.

heading: 3 THE PROPOSED LEARNING APPROACH FOR GRAPH MATCHING

heading: 3.1 APPROACH OVERVIEW
text: An overall structure of our approach is illustrated in Fig. 1. In line with (Wang et al., 2019), we employ VGG16 (Simonyan & Zisserman, 2014) to extract features from input images and bi-linearly interpolate the features at key points (provided by datasets). We concatenate lower-level (Relu4 2) and higher-level (Relu5 1) features to incorporate local and contextual information. For an image with k key points, the feature is denoted as H ∈ Rk×d, where d is the feature dimension. Unless
otherwise specified, the adjacency matrix A ∈ Rk×k is consequentially constructed via Delaunay triangulation (Delaunay et al., 1934), which is a widely adopted strategy to produce sparsely connected graph. To introduce more rich edge information, we also generate k×k m-dimensional edge features E ∈ Rm×k×k. E can be initialized with some basic edge information (e.g. length and angle and other attributes) or a commutative function Eij = p(Hi,Hj) = p(Hj ,Hi) ∈ Rm, where Hi refers to the feature of node i. Note for directed graph, the commutative property is not required.
The features H and E, together with the adjacency A, are then fed into GNN module. Pairs of features are processed in a Siamese fashion (Bromley et al., 1994). Standard GCN’s message passing rule simply updates node embedding as shown in Eq. (2). In contrast, each GNN layer in our model computes a new pair of node and edge embeddings simultaneously:
H(l+1) = fi(H (l),E(l),A;W l0), E (l+1) = g(H(l),E(l),A;W l1) (3) where W l0 and W l 1 are the learnable parameters at layer l. The edge information is essential to provide structural feature enhancing graph matching. We initialize H(0) = H and E(0) = E in our setting. We will discuss the details of functions f and g in Sec. 3.2. Following state-of-the-art work (Wang et al., 2019), we also compute the cross-graph affinity followed by a column/row-wise softmax activation and a Sinkhorn layer (Adams & Zemel, 2011):
Mij = exp ( τH>(1)iΛH(2)j ) , S = Sinkhorn(M) (4)
Note here M ∈ Rk×k is the node-level similarity matrix encoding similarity between two graphs, differing from the edege-level affinity matrix K in Eq. 1. τ is the weighting parameter of similarity, Λ contains learnable parameters and H(1)i is the node i’s embedding from graph G1. The output S ∈ [0, 1]k×k,S1 = 1,S>1 = 1 is a so-called doubly-stochastic matrix. Here Sinkhorn(·) denotes the following update iteratively to project M into doubly stochastic polygon:
M(t+1) = M(t) − 1 n M(t)11> − 1 n 11>M(t) + 1 n2 11>M(t)11> − 1 n 11> (5)
The Sinkhorn layer is shown to be an approximation of Hungarian algorithm which produces discrete matching output (Kuhn, 1955). As there are only matrix multiplication and normalization operators involved in Sinkhorn layer, it is differentiable. In practice, Eq. (5) converges rapidly within 10 iterations for decades of nodes. Less iterations involved, more precise back-propagated gradients can be achieved. We employ a cross-graph node embedding strategy following (Wang et al., 2019):
H (l) (1) = fc
( cat(H
(l) (1),SH (l) (2)) ) , H (l) (2) = fc ( cat(H (l) (2),S >H (l) (2)) )
(6)
where fc is a network and cat(·, ·) is the concatenation operator. H(i) is the node feature of graph i. This procedure seeks to merge similar features from another graph into the node feature in current graph. It is similar to the feature transfer strategy in (Aberman et al., 2018) for sparse correspondence, which employs a feature merging method analogous to style transfer (Li et al., 2017).
As Sinkhorn layer does not necessarily output binary digits, we employ Hungarian algorithm (Kuhn, 1955) to discretize matching output S in testing. The testing differs from the training due to the Hungarian discretization. We introduce a novel attention-like mechanism termed as Hungarian attention, along with existing loss functions (will be detailed in Sec. 3.3). The final training loss is as follows, where SG andH correspond to binary true matching and Hungarian attention loss.
minH(S,SG) (7)

heading: 3.2 CHANNEL-INDEPENDENT EMBEDDING
text: We detail the updating rule in Eq. (3). We propose a method to merge edge features into node features and perform matching on nodes. Edge information acts an important role in modeling relational data, whereby such relation can be complex thus should be encoded with high-dimensional feature. To this end, Gilmer et al. (2017) introduce a general embedding layer, which takes node and edge features and outputs a message to node v, then fuses the message and the current embedding:
m(l)v = σ ( ∑ w∈Nv ft (Evw) H (l) w + W (l)H(l) ) , H(t+1)v = ut ( H(t)v ,m (l) v ) (8)
where Evw is the feature corresponding to edge (v, w). In the realization of Eq. (8) (Gilmer et al., 2017), m(l)v and H (l) v are fed to GRU (Cho et al., 2014) as a sequential input. There are several variants which take into account specific tasks (Li et al., 2016; Schütt et al., 2017; Chen et al., 2019). Among these, Li et al. (2016) generates a transformation matrix for each edge and Schütt et al. (2017) resorts to merge embedding via fully connected neural networks. While edge-wise merging is straightforward, the representation ability is also limited. On the other hand, fully connected merging strategy will result in high computational cost and instability for back-propagation. To address these issues, we propose to merge embedding in a channel-wise fashion, which is termed as Channel-Independent Embedding (CIE). Concretely, the updating rule is written as:
H(l+1)v = σ  ∑ w∈Nv ΓN ( W (l) 1 E (l) vw ◦W (l) 2 H (l) w ) ︸ ︷︷ ︸
channel-wise operator/function + σ (W(l)0 H(l)v ) (9) E(l+1)vw = σ ( W (l) 1 E (l) vw ) (10)
where ΓN(· ◦ ·) is a channel-wise operator/function (above the underbrace), and it performs calculation per-channel and the output channel dimension is the same as input. The second σ(·) term is the message a node passes to itself, which is necessary in keeping the node information contextually consistent through each CIE layer. In this fashion, CIE is thus a procedure to aggregate node and edge embedding in each channel independently, which requires the dimensions of node (W(l)2 H (l) w ) and edge (W(l)1 E (l) vw) representations to be equal. Similarly, we also propose an corresponding updating rule of edge embedding by substituting Eq. (10):
E(l+1)vw = σ ( ΓE ( W (l) 1 E (l) vw ◦ h ( H(l)v ,H (l) w ))) + σ ( W (l) 1 E (l) vw ) (11)
where h(·, ·) is commutative h(X,Y) = h(Y,X). Eq. (11) is supplementary to Eq. (9). Fig. 2 shows a schematic diagram of CIE layer, which is motivated from two perspectives. First, CIE is motivated by counterparts in CNN (Qiu et al., 2017; Tran et al., 2018) which decouple a 3D convolution into two 2D ones (e.g. a 3× 3× 3 convolution can be decomposed to a 1× 3× 3 and a 3 × 1 × 1 convolutions). In this sense, the number of parameters can be significantly reduced. As shown in Fig. 2, node and edge embedding is first manipulated along the channel direction via a linear layer, then operated via ΓN and ΓE orthogonal to the channel direction. Instead of merging node and edge as a whole, CIE layer decouples it into two operations. Second, CIE is also motivated by the triumph of multi-head structure (e.g. graph attention (Veličković et al., 2018)), the key of
which is to conduct unit calculation multiple times and concatenate the results. Multi-head proved effective to further improve the performance since it is capable of capturing information at different scales or aspects. Traditional neural node-edge message passing algorithms (Gilmer et al., 2017; Li et al., 2016; Schütt et al., 2017) typically produce a unified transformation matrix for all the channels. On the other hand, in Eq. (9) (10) and (11), one can consider that the basic operator in each channel is repeated d times in a multi-head fashion. The cross-channel information exchange, as signified in Eq. (9) (10) and (11), only happens before the channel-wise operator (i.e. weights W(l)i as the crosschannel matrices). The main difference between CIE and traditional multi-head approaches e.g. (Veličković et al., 2018) is that CIE assumes the channel-independence of two embedded features (node and edge), while traditional ones only take one input under head-independence assumption.

heading: 3.3 HUNGARIAN ATTENTION MECHANISM
text: For most graph matching algorithms, the output is in a continuous domain. Though there are some alternatives that deliver discrete solutions by adding more constraints or introducing numerical continuation (Zhou & De la Torre, 2012; Yu et al., 2018), the main line of methods is to incorporate a sampling procedure (e.g. winner-take-all and Hungarian). Among them, the Hungarian algorithm (Kuhn, 1955) is a widely adopted, for its efficiency and theoretical optimality.
However, the Hungarian algorithm incurs a gap between training (loss function) and testing stages (Hungarian sampling). We compare the permutation loss (Wang et al., 2019) for concrete analysis:
LCE = − ∑
i∈G1,j∈G2
( SGij log Sij + ( 1− SGij ) log (1− Sij) ) (12)
Note Eq. (12) is an element-wise version of binary cross-entropy. During training, this loss tends to drag the digits in S into binary format and is likely trapped to local optima. This is because this loss will back-propagate the gradients of training samples that are easy to learn in the early training stage. In later iterations, this loss is then hard to give up the digits that have become binary. In fact, the similar phenomenon is also investigated in the focal loss (Lin et al., 2017) in comparison to the traditional cross-entropy loss. During the testing stage, however, the Hungarian algorithm has no preference on the case if digits in S are close to 0− 1 or not. It binarizes S anyway. Therefore, the effort of Eq. (12) to drag S into binary might be meaningless.
This issue is likely to be solved by integrating Hungarian algorithm during the training stage. Unfortunately, Hungarian algorithm is undifferentiable and its behavior is difficult to mimic with a differentiable counterpart. In this paper, instead of finding a continuous approximation of Hungarian algorithm, we treat it as a black box and dynamically generate network structure (sparse link)
where the attention mechanism Atten is fulfilled by an element-wise “logic OR” function. Fig. 3 shows an example of Hungarian attention procedure, and Eq. (13) highlights the most contributing digit locations: positive digits P = S where Hungarian agrees with the ground-truth; negative digits Q = Hungarian(S) \ SG where Hungarian differs from ground-truth. While GT (positive digits) naturally points out the digits that must be considered, negative ones indicate the digits that most hinder the matching (most impeding ones among all mis-matchings). Thus we need only minimize the loss at Z, without considering the rest of digits. As we note that this mechanism only focuses on a small portion of the matching matrix which is analogous to producing hard attention, we term it Hungarian attention. Now that with the attention mask Z, the Hungarian attention loss becomes:
HCE = − ∑
i∈G1,j∈G2
Zij ( SGij log Sij + ( 1− SGij ) log (1− Sij) ) (14)
Note that Hungarian attention mechanism can also be applied to other loss functions once the matching score is calculated in an element-wise fashion. Our experiment also studies Hungarian attention loss when casted on focal loss (Lin et al., 2017) and a specifically designed margin loss.
Finally we give a brief qualitative analysis on why Hungarian attention can improve matching loss. As discrete graph matching problem is actually built upon Delta function over permutation vertices (1 at ground-truth matching and 0 otherwise) (Yu et al., 2018), learning of graph matching with permutation loss is actually to approximate such functions with continuous counterparts. Unfortunately, more precise approximation to Delta function will result in higher non-smoothness, as discussed in Yu et al. (2018). For highly non-smooth objective, the network is more likely trapped at local optima. Hungarian attention, however, focuses on a small portion of the output locations, thus does not care about if most of the output digits are in {0, 1}. In this sense, Hungarian attention allows moderate smoothness of the objective, thus optimizer with momentum is likely to avoid local optima.

heading: 4 EXPERIMENTS
text: Experiments are conducted on three benchmarks widely used for learning-based graph matching: CUB2011 dataset (Welinder et al., 2010) following the protocol in (Choy et al., 2016), Pascal VOC keypoint matching (Everingham et al., 2010; Bourdev & Malik, 2009) which is challenging and Willow Object Class dataset (Cho et al., 2013). Mean matching accuracy is adopted for evaluation:
Acc = 1
k ∑ i∈G1,j∈G2 AND ( Hungarian(S)ij ,S G ij ) (15)
The algorithm abbreviation is in the form “X-Y”, where “X” and “Y” refer to the network structure (e.g. CIE) and loss function (e.g. Hungarian attention loss), respectively. Specifically, D, P and H
correspond to displacement used in (Zanfir & Sminchisescu, 2018), permutation as adopted in (Wang et al., 2019) and Hungarian attention over permutation loss devised by this paper, respectively.
Peer methods. We compare our method with the following selected counterparts: 1) HARG (Cho et al., 2013). This shallow learning method is based on hand-crafted feature and Structured SVM; 2) GMN (Zanfir & Sminchisescu, 2018). This is a seminal work incorporating graph matching and deep learning, and the solver is upon spectral matching (Leordeanu & Hebert, 2005). While the loss of this method is displacement loss, we also report the results of GMN by replacing its loss with permutation loss (GMN-P); 3) PIA/PCA (Wang et al., 2019). PCA and PIA correspond to the algorithms with and without cross-graph node embedding, respectively. Readers are referred to Wang et al. (2019) for more details; We further replace the GNN layer in our framework with: 4) GAT (Veličković et al., 2018). Graph attention network is an attention mechanism on graphs, which reweights the embedding according to attention score; 5) EPN (Gong & Cheng, 2019). This method exploits multi-dimensional edge embedding and can further be applied on directed graphs. The edge dimension is set to 32 in our experiments. Finally, we term our network structure CIE for short. To investigate the capacity of edge embedding update, we also devise a version without edge embedding, in which connectivity is initialized as reciprocal of the edge length then normalized, rather than A. This model is called PCA+ since the node embedding strategy follows PCA.
Implementation details. As the node number of each graph might vary, we add dummy nodes for each graph pair such that the node number reaches the maximal graph size in a mini-batch in line with the protocol in (Wang et al., 2019). In either training or testing stages, these dummy nodes will not be updated or counted. The activation function in Eq. (9) (10) and (11) is set as Relu (Nair & Hinton, 2010) in all experiments. Specifically, the node and edge embedding is implemented by:
H (l+1) ·q = σ (( A ( W (l) 1 E (l) ) ·q )( W (l) 2 H (l) ) ·q ) + σ (( W (l) 0 H (l) ) ·q ) (16a)
E (l+1) ·q = σ (∣∣∣∣(W(l)0 H(l))·q (W(l)0 H(l))>·q ∣∣∣∣ E(l)·q )+ σ((W(l)1 E(l))·q ) (16b)
where and refer to element-wise product and pairwise difference, respectively. H·q is the qth channel of H. In CIE1 setting, only node-level merging Eq. (16a) is considered and the edge feature is updated as Eq. (10). In CIE2 setting, we also replace the edge update Eq. (11) with Eq. (16b). Note edge embedding is used in both CIE1 and CIE2 and note PCA-H can be regarded as the pure node embedding version of our approach. The edge feature is initiated as reciprocal of the edge length. For training, batch size is set to 8. We employ SGD optimizer (Bottou, 2010) with momentum 0.9. Two CIE layers are stacked after VGG16.
CUB2011 test CUB2011 consists of 11,788 images from 200 kinds of birds with 15 annotated parts. We randomly sample image pairs from the dataset following the implementation released by Choy et al. (2016). We do not use the pre-alignment of poses during testing, because their alignment result is not publicly available. Therefore, there exists significant variation in pose, articulation and appearance across images, in both training and testing phase. Images are cropped around bounding box and resized to 256 × 256 before fed into the network. Instead of evaluating the performance in a retrieval fashion (Zanfir & Sminchisescu, 2018), we directly evaluate the matching accuracy since the semantic key-points are pre-given. We test two settings: 1) intra-class. During training, we randomly sample images, with each pair sampled from the same category (out of 200 bird categories). In testing, 2,000 image pairs (100 pairs for each category) are sampled; 2) cross-class. We analogously sample image pairs without considering the category information and 5,000 randomly sampled image pairs are employed for testing. While the first setting is for a class-aware situation, the second setting is considered for testing the class-agnostic case. Results are shown in Table 3.
We see our method surpasses all the competing methods in terms of matching accuracy. Besides, almost all the selected algorithms can reach over 90% accuracy, indicating that this dataset contains mostly “easy” learning samples. In this case, the Hungarian attention can slightly improve the performance since easy gradients agree with descending trend of the loss on the whole dataset.
Pascal VOC test The Pascal VOC dataset with Key-point annotation (Bourdev & Malik, 2009) contains 7,020 training images and 1,682 testing images with 20 classes in total. To the best of our knowledge, this is the largest and most challenging dataset for graph matching in computer vision. Each image is cropped around its object bounding box and is resized to 256× 256. The node
Accuracy/loss vs. training epoch. We further show the typical training behavior of P-loss and Hloss on Pascal VOC dataset in Fig. 4. 30 epochs are involved in a whole training process. Accuracy is evaluated on testing samples after each epoch while loss is the average loss value within each epoch. In the early training stage, the loss of CIE1-P immediately drops. On the other hand, CIE1-H hesitates for several epochs to find the most effective descending direction. On the late stage, we observe that even though P-loss (Eq. (12)) calculates much more digits than H-loss (Eq. (14)), the loss values are opposite. This counter-intuitive fact strongly indicates that P-loss makes meaningless effort, which is not helpful to improve the performance, at late stage. The proposed H-loss, on the other hand, is capable of avoiding easy but meaningless gradients.
Effect of Hungarian attention mechanism. We also conduct experiments to show the improvement of Hungarian attention over several loss functions (with and without Hungarian attention): Hungarian attention is applied on Focal loss (Focal) (Lin et al., 2017) as:
Lfocal = { −αZij(1− Sij)γ log(Sij), SGij = 1 −(1− α)ZijSγij log(1− Sij), SGij = 0
(17)
where controlling parameters α = 0.75 and γ = 2 in our setting. We also design a margin loss (Margin) with Hungarian attention under a max-margin rule. Note we insert the Hungarian attention mask Zij into Eq. (17) and Eq. (18) based on the vanilla forms.
Lmargin = {
Zij ×max(1− Sij − β, 0), SGij = 1 Zij ×max(Sij − β, 0), SGij = 0
(18)
where we set the margin value β = 0.2. Loss of Eq. (18) is valid because after Softmax and Sinkhorn operations, Sij ∈ [0, 1]. We also show permutation loss (Perm) (Wang et al., 2019). Result can be found in Fig. 4 (b) whereby the average accuracy on Pascal VOC is reported. All the settings are under CIE1. For either loss, the proposed Hungarian attention can further enhance the accuracy, which is further visualized by a pair of matching results under P-loss and H-loss in Fig. 5.
Table 3: Accuracy (%) on CUB.
method intra-class cross-class GMN-D 89.6 89.9 GMN-P 90.4 90.8 GAT-P 93.2 93.4 PCA-P 92.9 93.5 PCA-H 93.7 93.5 CIE-P 94.1 93.8 CIE-H 94.4 94.2
Willow Object Class test We test the transfer ability on Willow Object Class (Cho et al., 2013). It contains 256 images3 of 5 categories in total, with three categories (face, duck and winebottle) collected from Caltech-256 and resting two (car and motorbike) from Pascal VOC 2007. This dataset is considered to have bias compared with Pascal VOC since images in the same category are with relatively fixed pose and background is much cleaner. We crop the object inside its bounding box and resize it to 256 × 256 as CNN input. While HARG is trained from scratch following the protocol in (Cho et al., 2013), all the resting counterparts are either directly pre-trained from the previous section or fine-tuned upon the pre-trained models. We term the method “X-V” or “X-W” to indicate pre-trained model on Pascal VOC or fine-tuned on Willow, respectively. CIE refers to CIE1-H for short. Results in Table 2 suggest that our method is competitive to state-of-the-art.

heading: 5 CONCLUSION
text: We have presented a novel and effective approach for learning based graph matching. On one hand, the novelty of our method partially lies in the development of the Hungarian attention, which intrinsically adapts the matching problem. It is further observed from the experiments that Hungarian attention can improve several matching-oriented loss functions, which might bring about potential for a series of combinatorial problems. On the other hand, we also devise the channel independent embedding (CIE) technique for deep graph matching, which decouples the basic merging operations and is shown robust in learning effective graph representation. Extensive experimental results on multiple matching benchmarks show the leading performance of our solver, and highlight the orthogonal contribution of the two proposed components on top of existing techniques.

heading: ACKNOWLEDGMENTS
text: Tianshu Yu and Baoxin Li were supported in part by a grant from ONR. Any opinions expressed in this material are those of the authors and do not necessarily reflect the views of ONR. Runzhong Wang and Junchi Yan were supported in part by NSFC 61972250 and U19B2035.
3The data size is too small to train a deep model. Hence we only evaluate the transfer ability on this dataset.

heading: A APPENDIX
text: A.1 SYNTHETIC TEST
Synthetic graphs are generated for training and testing following the protocol in (Cho et al., 2010). Specifically, Kpt keypoints are generated for a pair of graphs with a 1024-dimensional random feature for each node, which is sampled from uniform distribution U(−1, 1). Disturbance is also applied to graph pairs including: Gaussian node feature noise from N (0, σ2ft); random affine trans-
formation [ s cos θ −s sin θ tx s sin θ s cos θ ty
0 0 1
] with s ∼ U(0.8, 1.2), θ ∼ U(−60, 60), tx, ty ∼ U(−10, 10)
followed by Gaussian coordinate position noise N (0, σ2co). By default we assign Kpt = 25, σft = 1.5, σco = 5. Two graphs share the same structure. We generate 10 random distributions for each test. Results are shown in Fig. 6. The performance of PCA and CIE is reported. We see our method significantly outperformed PCA. It can further be noticed that Hungarian attention can help to achieve an even higher accuracy. Readers are referred to Wang et al. (2019) for some other results on synthetic test.
However, we also notice that the way to generate synthetic graphs is much different from the distribution of real-world data. For real-world data, on one hand, there is strong correlation on the
neighboring node features. This is the reason why the message passing from nearby node features works. However, the features of synthetic data are randomly generated and there is no correlation between neighboring node features. Therefore, message passing mechanism is not very effective to reveal the relation or pattern among local nodes for synthetic data. On the other hand, features of real-world data typically lie on a manifold embedded in high dimensional space, hence is low dimensional. However, randomly generated features will span the whole space and show no patterns.
Taking into account the aforementioned factors, we believe there is a demand for a novel strategy to generate more reasonable synthetic data. This can be one of the future works.
A.2 COMPARISON OF PASCAL VOC AND WILLOW
As we claim that Willow dataset is biased compared with Pascal VOC dataset, we qualitatively show some randomly selected examples in Fig. 7. We select several images with the same class “car” from both datasets. We also choose images with “bird” from Pascal VOC and “duck” from Willow since they somewhat share similar semantic information. We see in either case, Pascal VOC contains more variation and degradation compared with Willow in terms of pose, scale, appearance, etc. In general, Willow dataset is easier for algorithms to learn. While there is a significant performance gap of PCA over these two datasets, the performance of CIE on Willow without fine-tune (Table 2) is consistent to the performance on Pascal VOC (Table 1). As such, we infer the performance degradation of CIE on “duck” in Willow test (Table 2) is due to such bias. The pre-trained CIE on Pascal VOC tends to produce more stable and higher average accuracy on all types of images, rather than focusing on “easy-to-learn” samples by PCA. This is a different learning strategy from PCA.

Review summaries:
The authors proposed a new way to train graph siamese networks for the graph matching problem. The overall framework of this paper is somehow similar to [1] and [2], except for the final Hungarian attention module, which is the key contribution of this paper. In the current settings, the authors proved that using their Hungarian attention module, the performance can be improved. However, it would be better if the Hungarian attention can be applied to DGCNN in [1] and CMPNN in [2]. It would be good if the author can do an extra experiment to apply the Hungarian attention module to these two modules. Also, the authors may want to add some discussion about these two papers in the related works section (both papers do have published their codes).