Learning deep graph matching with channel-independent embedding and Hungarian attention
Authors: Tianshu Yu
Runzhong Wang
Junchi Yan
Baoxin Li
Venue:  (2020)
Keywords: deep graph matching
edge embedding
combinatorial problem
Hungarian loss

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 multi-head 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.

Published as a conference paper at ICLR 2020
LEARNING DEEP GRAPH MATCHING VIA CHANNEL- INDEPENDENT EMBEDDING AND HUNGARIAN ATTEN- TION
Tianshu Yu', Runzhong Wang', Junchi Yan', Baoxin Li!
f "Arizona State University
*Shanghai Jiao Tong University ft itianshuy, www.in.......................... www.xii.i]@assu...m edu (runzhong.. wang, jas en
ABSTRACT
Graph matching aims to establishing node-wise correspondence between two graphs, which is classic combinatorial problem and in general NP-complete. Un- til 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) novel node and edge embedding strategy which stimulates the multi- head strategy in attention models and allows the information in each channel to merged independently. In contrast, only node embedding is accounted pre- vious works; ii) general masking mechanism over the loss function is devised to improve the smoothness of objective learning for graph matching. Using Hungar- ian algorithm, it dynamically constructs 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.
INTRODUCTION
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 correspondencd!"
max x
Kx s.t.
Px=
(1)
where xXc E (0, 13nd which is the column-wise vectorized form of the permutation ma- trix X that encodes the node-to-node correspondence between two graphs, and K E R R=²xx xx² is the so-called affinity matrix respectively. Note P is a selection matrix encoding the one-to-one correspondence constraint. This problem is called Lawler's 's QAP (Lawler 1963) and has attracted enormous attention for its generally NP-complete (Hartmanis) 1982) challenge, as well as wide spectrum of applications in computer vision, graphics. machine learning and operational research QAP (Loiola et al. 2007) with objective tr
etc. In particular, a special case of Eq. (I. which can be converted to Lawler's s QAP by K F2 & F2 and F; refers to the weighted adjacency matrix. A series of solvers haven been developed to solve graph match- ing problem (Leordeanu & Hebert 2005) Cho et al.] 2010) Bernard et al.) 2018 Yan et al.) 2015] conditioned
Poopmans-Beckmane
F FFXF2
Yu et al. 2018). All these methods are based deterministic optimization, which 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 & Sminchisescul 2018) is proposed exploit the high capacity of deep networks for graph matching, which achieves state- of-the-art art performance. This is in contrast to some early works which incorporate learning strategy
We assume graphs are equal size for narrative simplicity. One can easily handle unbalanced graph size by adding dummy nodes as common protocol in graph matching literature (Cho et al. (010). A ia:js typically encodes the affinity between pair (i) and ba,b) where node i, 9. and a, b E G2.

---

Published as a conference paper at ICLR 2020
separately in local stages (Cactano et al. 2009: Cho et al.
2013). On the other hand, Graph Convolu- tional Networks (GCN) (Kipf & Welling 2017 brings about new capability on tasks over graph like data, as it naturally integrates the intrinsic graph structure in general updating rule:
H
(AH"W())
where Å is the normalized connectivity matrix. H and W are the features and weights at layer I. 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, Waan et al. (2019) 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. involves both node and edge information, which exactly correspond to the diag- onal and off-diagonal elements in K, respectively. Edges can carry informative multi-dimensional attributes (namely weights) which are fundamental to graph matching. However existing embed- ding based graph matching methods (Wang et al. 2019 Xu et al. 2019) are focused 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 model (Zanfir & Sminchisescu, (018)) since the edge information is derived from the concatena- tion of node features. To our best knowledge, there 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., 2013] Yu et al., 2018) for constructing the affinity matrix K. Such a gap shall be filled in the deep graph matching pipeline.
neither well modeled in the emhedding-
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 (018) similar to the use in optical flow estimation (Ren al. 2017); ii) the so-called permutation loss (Wang al.) 2019) involving iterative Sinkhorn procedure followed by a cross-entropy loss. Results in (Wang) ct 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 unnatural approximation to Hungarian sampling (in testing stage) for discretization. If the network is equipped with continuous loss function (e.g. cross-entropy), we argue that the training process will make 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 accuracy.
This paper strikes an endeavor on the above two gaps and makes the following main contributions:
i) We propose new approach for edge embedding via channel-wise operation, namely channel- independent embedding (CIE). The hope is to effectively explore the edge attribute and simulate the multi-head strategy in attention models (Veličković al., 2018)) by decoupling the calculations parallel and orthogonal to channel direction. In fact, edge attribute information has not been consid- ered in existing embedding based graph matching methods (Wang 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 dynami- cally 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 consid- ered 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.
2 RELATED WORKS
Graph embedding. To handle graph-like data, early works adopt recursive neural networks (RNNs) treating input as directed acyclic graphs (Sperduti & Starita 1997, Frasconi 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 undirected graphs. Li et al. (2016) further improved this line
2

---

Published as a conference paper at ICLR 2020
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 convolution operator in Fourier domain which is obtained by performing iigen-dcommposition 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 (017)) propose 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 (Veličković 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 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 al.) 2016), Tensor GNN (Schütt et al. 2017) and EGNN (Gong& & Cheng, 2019). An improved version is devised in Chen
ct 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 el al.) 2017). The Sinkhorn Network (Adams & Zemel (01T)) is de- veloped given known assignment cost, whereby doubly-stochastie regulation performed on input non-negative square matrix. Paatrini 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 it is not invariant to input permutations which is conditioned on a predefined node permutation as reference. In particular, existing supervised methods on combi- natorial learning are generally pross-entropy-bite 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 correspon- dence as supervision. While the ability by only learning affinity is limited, Cho et al. (2013) pro- pose a matching function learning paradigm using histogram- basedd attributes with Structured-SVM (Tochantariiis 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 & Sminchisescul 2018) measures the pixel-wise transla- tion which is similar to optical-flow flow (Dosovitskiy et al., 2015), being essentially a regression task instead of combinaotiral optimization. Sceing this limitation, Wang et al. (2019) employ element- wise 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. (019) to explore the structure information.
3 THE PROPOSED LEARNING APPROACH FOR GRAPH MATCHING
3.1 APPROACH OVERVIEW
An overall structure of our approach is illustrated in Fig. In line with (Wang et al. 2019), we em- play 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) 2)) and ligeer-level (Relu5 1) features to incorporate local and contextual information. For an image with & key points, the feature is denoted H E R where d is the feature dimension. Unless
3

---

Published as a conference paper at ICLR 2020
CIE
CIE
uestliie beiding
Her oy
CNN
CIE
CIE
Figure 1: Architecture overview of the proposed deep graph matching networks that consist of the proposed channel-independent embedding and Hungarian attention layer over the loss function.
otherwise specified, the adjacency matrix A E R x is consequentially constructed via Delaunay triangulation (Delaunay et al. 1934), which is a widely adopted strategy to produce sparsely con- nected graph. To introduce more rich edge information, we also generate k m-ddmmensional edge features E E R=xxxx E' can be initialized with some basic edge information (e.g. length and angle and other attributes) or a commutative function E, = p(H;, H2) - , H,) E RTM where H; 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 ct al. 1994). Standard GCN's message passing rule simply updates node embedding as shown in Eq. (2) contrast, each GNN layer in our model computes new pair of node and edge embeddings simultaneously:
H(+1)) f. (H E A; W)), E(++1) g(H E A
(3)
where W/ and W1 are the learnable parameters layer 1. The edge information is essential to provide structural feature enhancing graph matching. We initialize H H and ( E in
our setting. We will discuss the details of functions f and g in Sec. 3.2 Following state-of-thed oof-the-art art work (Wang al. 2019), we also compute the cross-graph affinity followed by column/row-wise softmax activation and a Sinkhorn layer (Adams & Zemel 2011):
Mj = exp (T (HH()) (H)
S = Sinkhorn(M)
(4)
Note here M E R is the node-level similarity matrix encoding similarity between two graphs, differing from the edege-level affinity matrix K in Eq.
[ T is the weighting parameter of similarity.
A contains learnable parameters and H(1)s is the node i's embedding from graph G1. The output
S E [0, 1| S1 1, S 1 is so-called doubly-stochastic matrix. Here Sinkhorn(-) denotes
the following update iteratively to project M into doubly stochastic polygon:
( (()
I M 111TTTTT
1 11 T (()
(t)
11 n
11
--111 111T
(5)
n
n
The Sinkhorn layer 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, is differentiable. In practice, Eq. (5) converges rapidly within 10 iterations for decades of nodes. Less iterations involved, more precise back pack-propagated gradients can be achieved. We employ a cross cooss-graph node embedding strategy following (Wang et al. 2019):
H 0 (1) fo (cat(H(() SH (
fe f (cat(H(() (2), (TH))) (2))
(6)
where Sa is a network and cat(.,.) is the concatenation operator. ((6) 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 correspon- dence, 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 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 Sec. 3.3). The final training loss as follows, where SG and H correspond to binary true matching and Hungarian attention loss.
min HSS
4

---

Published as a conference paper at ICLR 2020
Linear
Tt. muchasress
(
Figure 2: Illustration of the proposed CIE layer for embedding based deep graph matching. The operation "Linear" refers to the linear mapping, c.g. H + -w H !!)
in Eq 9).
3.2 CHANNEL-INDEPENDERN EMBEDDING
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 relational data, whereby such relation can be complex thus should be encoded with high- digh-dimensional feature. To this end. Gilmer et al. (2017) introduce general embedding layer, which takes node and edge features and outputs a message to node v, then fuses the message and the current embedding:
important role in modeling
Σ WWEN
fe (Epw)) H WHOH)
((++) ut H m
m =a
where Evw is the feature corresponding to edge (v. w). In the realization of Eq. Gilmer et al, 2017 _ and H!!) are fed GRU (Cho et al., 2014) as sequential input. There are several variants which take into account specific tasks (Li et al. [0116] Schütt et al., 2017 Chen al. 2019). Among these, Li et al. (2016) generates a transformation matrix for each edge and Schüit et al. (2017) resorts 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 pack-propagation. To address these issues, we propose to merge embedding in a channel-wise fashion, which is termed as Channel-Indepeene Embedding (CTE). Concretely, the updating rule is written as:
(+1) =a
Σ WEN.
TN W E D
W H())
(1) +o (W!'H!)
(9)
chanoel-wise operator/function
E E(+1)
(w() (00
(
(10)
where I'(- .) is channel-wise operator/function (above the underbrace), and it performs calcu- lation per-channel and the output channel dimension the same as input. The second a(-) term is the message node passes 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 (!) H!"))
and edge (w(") E(!)) representations to be equal. Similarly, we also propose an corresponding up- dating rule of edge embedding by substituting Eq. (10):
E ((+1)
(F
E())
h
H
W
B
(11)
where .)(,,)) is commutative 1(X. Y) ,(Y, X). Eq.
11 is supplementary to Eq.
Fig. shows a schematic diagram of CIE layer, which motivated from two perspectives. First, Tran
CIE motivated by counterparts in CNN (Qiu et al. [0177; Tran et al. (2018) which decouple 3D convolution into two 2D ones (e.g. a x 3 x convolution can be decomposed to 1 3 and 3 x 1 X convolutions). In this sense, the number of parameters can be significantly reduced. As shown Fig. 2 node and edge embedding is first manipulated along the channel direction via linear layer, then operated via I' and D3 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 (Veličković al. 2018)). the key of
5

---

Published as a conference paper at ICLR 2020
similartty matrix
doubly-stoce stcchsttc matrit
pe momutt Boon mateio
14
SG
S-5
0.5
0.6
9.2
0.1
G2
0-
SJ
0.0
0.0
6:6
0.0
0M
0.0
2.5
64
6
1.2
0.7
1.0
Sinchers
9.3
0.9
6.8
0.
0.3
Hungarian
1.0
6.0
0.0
9.0
0.0
0.0
0.0
0.0
0.0
0.5
0
3.6
0.3
01
0.0
9.5
1.0
0.8
0.5
2.7
3.5
1.0
0.4
0.1
6.2
0.2
0:4
0.0
0.0
5.0
0.0
0.2
0.0
Attention Pooling
Hangurian Attentinn
outputt matrixx
attontion activation
ground truth matrix
0.0
0.0
0.0
0:4
0.3
0.0
3.0
0.3
0.0
10
5.0
0.0
0.
5.0
0.0
1:5
0.0
0.0
0.0
6.0
0.0
0.3
0.0
0.0
0.0
1.0
0.0
5.0
0.0
0.2
0.0
0.8
0.0
0.0
3.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
8.0
0.1
0.0
3.0
0.0
0.0
0.0
1.0
0.0
8.
5.0
0.0
0.5
10
0.0
Figure 3: A working example illustrating of our proposed Hungarian attention pipeline starting from similarity matrix. Sinkhorn algorithm solves similarity matrix into a doubly-stochastee matrix in differentiable way. A discrete permutation matrix is further obtained via Hungarian algorithm. Our proposed Hungarian attention, taking the ground truth matching matrix into account, focuses on "important" digits either labeled true or being mis-classified. The output matrix is obtained by attention pooling from doubly-stochastic matrix, where we compute loss on it.
which is conduct unit calculation multiple times and concatenate the results. Multi-hean proved effective to further improve the performance since it is capable of capturing information at different scales aspects. Traditional neural node-edge message passing algorithms (Gilmer et al.. 2017 et al. 2016 Schütt et al. 2017) typically produce a unified transformation matrix for all the channels. On the other hand, in Eq. (9 (TO) and ) one consider that the basic operator in each channel is repeated d times in multi head fashion. The cross-channe information exchange, as sigmified in
Eq. (9 10 and (11p. only happens before the channel-win wwse operator (i.e. weights w as the cross- channel matrices). The main difference between CIE and traditional multi-head approaches e.g. of two embedded features
VVeličković al. 2018)) is that CIE assumes the channel-independeen (node and edge), while traditional ones only take one input under head- read--ndepenndece assumption.
3.3 HUNGARIAN ATTENTION MECHANISM
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 con- tinuation (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 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. (019) for concrete analysis:
LCE --
Σ JE91JES2
(S S., + ST) log (1 - S.))
(12)
Note Eq. (12) is 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 back- propaaaae 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 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 1 or not. It binarizes anyway. Therefore, the effort of Eq. [12 drag S into binary might be meaningless.
This issue likely to be solved by integrating Hungarian algorithm during the training stage. Un- fortunately, Hungarian algorithm is undifferentiable and its behavior is difficult to mimic with differentiable counterpart. In this paper, instead of finding a continuous approximation of Hungar- ian algorithm, treat it black box and dynamically generate network structure (sparse link)

---

Published as a conference paper at ICLR 2020
Table 1: Accuracy on Pascal VOC (best in bold). White and gray background refer results on test-
ing and training, respectively. Compared methods include GMN (Zanfir & Sminchisescu 2018).
GAT (Veličković et al., 2018). EPN (Gong & Cheng 2019). PCA/PIA (Wang et al.12201)).
method acro bike bird boat bottle bus car cat chair cow table dog
horse
mbike person plant sheep sota train tv Ave
GMN-D 31.9
40.8
68.7 72.2 53.6 52.8 34.6 48.6 72.3
47.7
54.8
51.0
38.6
75.1
49.5
45.0
36.3
GMN-P
46. 58.2 45.9
70.6 76.446..2 61.7 35.5 53.7 58.9
57.5
56,9
49.3
34.1
77.5
57.1
53.6 83.2 57,9
GAT-P 60.5 60.9 51.8
79.0
70.9 62.7 70.1 39.7
63.9
66.2
63.8
65.8
62.8
39.5
82.0
66.9
50.1
78.5
90.3
63.6
GAT-H 47.2 61.6 53.3
79.7
70.1 65.3 70.5 38.4
64.7
62.9
65.1
66.2
62.5
41.1
78.8
67.1 61.6
814
91.0
EPN-P 65.2 62.2 52.7
77.8
63.4 69.6
62.8
63.6
64.6
61.9
39,9
80.5
45.5
77.6
63.2
PIA-D 19.7 57.7 58.6 47.2
74.0
62.1 66.6
33.6
61.7 65.4
58.0
67.1
58.9
41.9
77.7
64.7
50.5
81.8 89.9
41.- 55.8 60.9 51,9
75.0
75.8
65.2 33.3
65.9
62.8
62.7
67.7
62.1
42,9
80.2
64.3
59.5
82.7
90.1 63.0
PCA-P44.99 55.0 65.8 47.9
76.9
77.9
63.5
67.4
33.7
65.5
63.6
61.3
68.9
62.8
44.9
77.5
67.4
57.5
86.7
90.9 63.8
PCA-H 49.8 60.7 63.9
79.8
72.5
63.8
71,2 38.4
62.5
71.7
66.6
62.5
40.5
84.7
66.1
47.9
64.6
PCA+P 61.0 62.3 53.9
78.2
72.5
64.4
70.5
39.0
63.5
74.8
65.2
65.0
61.6
40.8
83.2
67.1 50.5
79.6
91.6
64.6
CIE;-P 65.5 68.0 57.0
81.
75.9
70.3
73.4
41.1
66.7
53.2
68.3
68.4
63.5
45.3
84,8
69.7
57.2
79.8
91.6
66.9
CHE,-H 51.2 68.4 69.5 57.3
82.5
73.5
69.5
74.0
40.3
67.8
60.0
69.7
70.3
65.1
44.7
86.9
70.7
57.3
84.2
92
67.4
CIE; 52.1 69.4 69.9 58.9
80.6
76.3
71.0
74.2
41.1
68.0
60.4
69.7
70.7
65.1
46.1
85.1
70.4
61.6
80.7
91.7
CIE, H 51.2 69.2 70.1 55.0
82.
72.8
69.0
74,2
39.6
68.8
71.8
70.0
71.8
66.8
44.8
85.2
69.9
65.4
85.2
92.4
68.9
PCA- 75.8 83.3
83.3 74.7 98.7 96.3 74.3 87.8
80.9
85.7
100.0
83.7
83.8
98.7
66.5
99.1
80.7
99.7
98.2
97.0
CPE; 56.5 84.0 73.5
91.5
81.1 67.8 76.8
72.2
98.0
73.6
77.9
46.1
94.8
72.7
93.6
93.7
91.6
76.2
-IE,-H 59.4 88.1 75.9 58.0 94.3 81.9 69.4 78.9
49.5
78.2
99.7
78.1
78.0
82.1
47.4
95.8
75.7
97.6
96.0
91.1
78.7
according to its output. Concretely, the sparse link is calculated as:
Z = AAten (Hungarian(S),S9) = PUQ
(13)
where the attention mechanism Atten is fulfilled by an element-wise "logic OR" function. Fig. shows an example of Hungarian attention procedure, and Eq. {I3) highlights the most contributing digit locations: positive digits P = S where Hungarian agrees with the ground-truth; negative digits Q = Hungarian(S) \ S 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;
HcF
Σ 8E91.EE9.
Zij (S) log S.j + (1 -I-S)) log (1 (1-S1)) Sig))
(14)
Note that Hungarian attention mechanism can also be applied to other loss functions once the match- ing score is calculated in an element-wise fashion. Our experiment also studies Hungarian attention
loss when casted on focal loss (Lin et al.) (017) 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 per- mutation loss is actually to approximate such functions with continuous counterparts. Unfortunately, more precise approximation to Delta function will result in higher non- mootsmootsssss, as discussed in Yu (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, 13. In this sense, Hungarian attention allows moderate smoothness of the objective, thus optimizer with momentum is likely to avoid local optima.
4 EXPERIMENTS
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-
Σ
AND (Hungarian(S)Jj, SG)
(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
7

---

Published as a conference paper at ICLR 2020
correspond to displacement used in (Zanfir& & Sminchisescu 2018 permutation as adopted in (Wang
it al. 2019) and Hungarian attention over permutation loss devised by this paper. respectively.
Peer methods. We compare method with the following selected counterparts: 1) HARG (Cho ct al. 2013). This shallow learning method is based on hand-crafted feature and Structured SVM; 2) GMN (Zanfir& & Sminchisescu 2018). This is seminal work incorporating graph matching and deep learning, and the solver is upon spectral matching (Leordeanu & Hebert, (005). 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-grapy node embedding, respectively. Readers are referred to Wang et al. a (2019) for more details; We further replace the GNN layer in our framework with: 4) GAT Vellckovic et al., 2018). Graph attention network an attention mechanism on graphs, which reweights the embedding according to attention score; 5) EPN (Gong & Cheng. 2019). This method exploits nulti-dimensional edge embedding and can further be applied on directed graphs. The edge dimension is set to 32 in 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., (019). In either training or testing stages, these dummy nodes will not be updated or counted. The activation function in Eq. (9) (IO) and (II) is set as Relu (Nair & Hinton 2010 in all experiments. Specifically, the node and edge embedding is implemented by:
H =a (A (W"EE B())
((A
(W!) 1 H())
W (1) H())
+o
(16a)
(1+1) E =0 (1(w6)) H θ (Wo HO)
E!!)
+ to
(w E
(16b)
where @ and @ refer to clement-wise product and pairwise difference, respectively. H.g is the gth channel of H. In CIE, setting, only node-level merging Eq. (I6a) is considered and the edge feature is updated as Eq. (T). In CIE₂ setting. we also replace the edge update Eq. (T1) with Eq. (6b).. Note edge embedding is used in both CIE, and CIE₂ 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 1 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. (016)) 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 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 cate- gories). 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 "casy" learning samples. In this case, the Hungarian attention can slightly improve the performance since easy gradients agree with descending trend of the loss the whole datasct.
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 vi- sion. Each image is cropped around its object bounding box and is resized to 256 256. The node
8

---

Published as a conference paper at ICLR 2020
0.7
Lo Hung
0.68
with Hunc
Aoci CIE,.P
Accuray
Acc: CIR,
Loos: .
Loss
Acuraay
CLE,
0.61
0.62
442-
Epoch
0.6
Focal
Margin
Perm
(a) Accuracy/loss vs, training epoch.
(b) Ablation study by Hungarian attention.
Figure 4: Performance study Pascal VOC. Note in (a) the loss is calculated on all matching digits for both -IE, and -IB,-H. Note around 10th epoch, the accuracy of CIE, almost reaches the highest, but the loss keeps descending until 30th epoch. This indicates that in most of the latter epochs, P-loss performs "meaningless" back- proo-propagttion to drag the output to binary. H-loss, by accommodating smoothness, can emphasize most contributing digits and achieves higher accuracy. size of this dataset varies from 6 to 23 and there are various scale, pose and illumination perturba- tions. Experimental results are summarized in Table 1 We see in either setting, CIE significantly outperforms all peer algorithms. Specifically, CIE, -H achieves the best performance and has 0.8% improvement w.r.t. average accuracy over -IE For each class, CHE, and CIE, carve up most of the top performance. We also note that CIE,-H has close performance on "table" compared with GMN-D. Since P-loss is naturally not robust D-loss symmetric objects, P-loss showed great degradation over D-loss on "table" (as discussed in (Wang et al., 2019)). However, with the help of Hungarian link, H-loss can maintain relatively high accuracy despite natural flaw of P-loss. This observation indicates that H-loss can focus on "difficult" examples. We also note that CIE, produces better results against CIEz, which implies that updating edge embedding less effective compared to a singleton node updating strategy. We can also see from Table that PCA-P has much higher performance on training samples than CHE,-H, which is the contrary of the result testing samples. This might indicate that PCA-P overfits the training samples.
Accuracy/loss vs. training epoch. We further show the typical training behavior P-loss and H- loss on Pascal VOC dataset in Fig. 4 30 epochs are involved in whole training process. Accuracy 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 CIE,-P immediately drops. On the other hand, CIE, 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-intuitiv fact strongly indicates that P-loss makes meaningless effort, which is not helpful improve the performance, at late stage. The proposed H-loss, on the other hand, is capable of avoiding easy but meaningless gradients.
Effeet of Hungarian attention mechanism. We also conduct experiments to show the improve- ment Hungarian attention over several loss functions (with and without Hungarian attention): Hungarian attention is applied on Focal loss (Focal) (Lin al. 2017)
aZ S;₂)) (Sgg)
SC =1 S =
Liocal
(17)
-1 - a Z), 1 S7 log(1 St)),
where controlling parameters 0.75 and = 2 in our setting. We also design 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.
Z X max [1 - S. - -,,0),
SG =1
Cynngiin
(18)
Zg x max Siz - 3,0).
SC =0
where we set the margin value 8 0.2. Loss of Eq. 18 is valid because after Softmax and
Sinkhorn operations, S.y E [0. 1]. We also show permutation loss (Perm) (Wag et al. 2019 Result can be found in Fig. (b) whereby the average accuracy Pascal VOC is reported. All the settings are under CIE,- For either loss, the proposed Hungarian attention can further enhance the accuracy, which is further visualized by pair of matching results under P-loss and H-loss in Fig.
9

---

Published as a conference paper at ICLR 2020
207
(a) Reference Image
P-loss: 7/10
H-loss: 8/10
Figure 5: Visualization of matching result: 10 key points in each image with 7 and correct matchings dispalyed, respectively. Different colors across images indicate node correspondence. The larger size of dot, the larger is the predicted value S (a) The reference image. (b) Result the target image from -IE,-P. (c) Result on the target image from -IE We see though H-loss ie. Hungarian attention loss outputs smaller predicted values, it delivers more accurate matching.
Table 2: Accuracy (%)
Willow Object.
Table 3: Accuracy (%) on CUB.
method
face
mbike
car
duck
whottle
method
intra-class
cross-class
HARG
91.2
44.4
58.4
55.2
66.6
GMN-D
89.6
89.9
GMN-V
98.1
65.0
72.9
74.3
70.5
GMN-P
90.4
90.8
GMN-W W
99.3
71.4
74.3
82.8
76.7
GAT-P
93.2
93.4
PCA-V
100.0
69.8
78.6
82.4
95.1
PCA-P
92.9
93.5
PCA-W W
100.0
76.7
84.0
93.5
96.9
PCA-H
93.7
93.5
CIE-V 99.9
71.5
75.4
73.2
97.6
CIE-P
94.1
93.8
CIE-W
100.0
90.0
82.2
81.2
97.6
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 image 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 with
considered to have bias compared with Pascal VOC since images in the same category relatively fixed pose and background is much cleaner. We crop the object inside its bounding box and resize it to 256 x 256 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 fine-tuned upon the pre-trained models. We term the method "X-V" "X-W" to indicate pre-trained model on Pascal VOC or fine-tuned on Willow, respectively. CIE refers to CIE,-H for short. Results in Table 2 suggest that our method is competitive state-of-the-arr,
5 CONCLUSION
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 in- trinsically adapts the matching problem. It is further observed from the experiments that Hungarian attention can improve several matchingg-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 opera- tions and is shown robust in learning effective graph representation. Extensive experimental results 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.
ACKNOWLEDGMENTS
Tianshu and Baoxin Li were supported 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.
"hhe data size too small train deep model. Hence we only evaluate the transfer ability this dataset.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Kfir Aberman, Jing Liao, Mingyi Shi, Dani Lischinski, Baoquan Chen, and Daniel Cohen-Or. Neural best-buddies: Sparse cross-domain correspondence. SIGGRAPH, 2018.
Ryan Prescott Adams and Richard S Zemel. Ranking via sinkhorn propagation. arXiv: 196. 2011.
Florian Bernard, Christian Theobalt, and Michael Moeller. Ds Tighter lifting-fiit fiting-free convex relax- ations for quadratic matching problems. CVPR, 2018.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In COMPSTAT. 2010.
Lubomir Bourdev and Jitendra Malik. Poselets: Body part detectors trained using 3d human pose annotations. In ICCV, 2009.
Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verifi- cation using "siamese" time delay neural network. In NIPS, 1994.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In ICLR, 2014.
Tibério S Caetano, Julian McAuley, Li Cheng, Quoc V Le, and Alex Smola. Learning graph matching. PAMI, 3166):0088-1058, 2009.
Hongyun Cai, Vincent Zheng, and Kevin Chen-Chuan Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. TKDE, 3009)1661-11677, 2018.
Pengfei Chen, Weiwen Liu, Chang-Yu Yu Hsieh, Guangyong Chen, and Shengyu Zhang. Utilizing edge features in graph neural networks via variational information maximization. arXiv preprint 1rXiv:1906.05483 2019.
Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint arXiv: /409. 1259, 2014.
Minsu Cho, Jungmin Lee, and Kyoung Mu Lee. Reweighted random walks for graph matching. In ECCV, 2010.
Minsu Cho, Karteek Alahari, and Jean Ponce. Learning graphs match. In CVPR, 2013.
Christopher B Choy, Jun Young Gwak, Silvio Savarese, and Manmohan Chandraker. Universal correspondence network. In NIPS, 2016.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In NIPS, 2016.
Boris Delaunay et al. Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7(793-800):1-2, 1934.
Alexey Dosovitskiy, Philipp Fischer, Eddy Ilg, Philip Hausser, Caner Hazirbas, Vladimir Golkov, Patrick Van Der Smagt, Daniel Cremers, and Thomas Brox. Flownet: Learning optical flow with convolutional networks. In ICCV, 2015.
Patrick Emami and Sanjay Ranka. urXiv:1805.07011 2018.
Learning permutations with sinkhorn policy gradient.
Mark Everingham, Lue Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman. The pascal visual object classes (voc) challenge. IJCV, 88(2):303 -388, 2010.
Paolo Frasconi, Marco Gori, and Alessandro Sperduti. A general framework for adaptive processing of data structures. TNN, 95):768-778, 1998.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In ICMI,,011

---

Published as a conference paper at ICLR 2020
Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In CVPR, 2019.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In IJCN,, 2005.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
Juris Hartmanis. Computers and intractability: a guide to the theory of np-completeness (michael garey and david s. johnson). Siam Review, 24(1):90, 1982.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR, 2016.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
Eugene I. Lawler. The quadratic assignment problem. Management science, 9(4):586-599 1963.
Marius Leordeanu and Martial Hebert. A spectral technique for correspondence problems using pairwise constraints. ICCV, 2005.
Yijun Li, Chen Fang, Jimei Yang, Zhaowen Wang, Xin Lu, and Ming-Hsuan Yang. Universal style
transfer via feature transforms. In NIPS, 2017.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In ICLR, 2016.
Tsung-Yi Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection. In ICCV, 2017.
Eliane Maria Loiola, Nair Maria Maia de Abreu, Paulo Oswaldo Boaventura-Netto, Peter Hahn, and Tania Querido. A survey for the quadratic assignment problem. European journal of operational research, 176(2)x657-690 2007.
Gonzalo Mena, David Belanger, Gonzalo Muñoz, and Jasper Snoek. Sinkhorn networks: Using optimal transport techniques learn permutations. NIPS Workshop in Optimal Transport and Machine Learning, 2017.
Anton Milan, Seyed Hamid Rezatofighi, Ravi Garg, Anthony R. Dick, and Ian D. Reid. Data-driven approximations to np-hard problems. In AAAI, 2017.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In ICML, 2010.
Giorgio Patrini, Marcello Carioni, Patrick Forre, Samarth Bhargav, Max Welling, Rianne van den Berg, Tim Genewein, and Frank Nielsen. Sinkhorn autoencoders. arXiv:1810001118, 2018.
Zhaofan Qiu, Ting Yao, and Tao Mei. Learning spatio-temporal representation with pseudo-3d residual networks. In ICCV, 2017.
Zhe Ren, Junchi Yan, Bingbing Ni, Bin Liu, Xiaokang Yang, and Hongyuan Zha. Unsupervised deep learning for optical flow estimation. In AAAI, 2017.
Rodrigo Santa Cruz, Basura Fernando, Anoop Cherian, and Stephen Gould. Visual permutation learning. TPAMI, 2018.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. TNN, 20(1):61-800 2008
Kristof T Schütt, Farhad Arbabzadah, Stefan Chmiela, Klaus R Müller, and Alexandre Tkatchenko. insights from deep tensor neural networks. Nature communications, 8:13890,
2017.
12

---

Published as a conference paper at ICLR 2020
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1rXiv:1409.1533 2014.
Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matri- ces. AoMS, 1964.
Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures. TNN, 8()):144-735, 1997.
Du Tran, Heng Wang. Lorenzo Torresani, Jamie Ray, Yann LeCun, and Manohar Paluri. A closer look at spatiotemporal convolutions for action recognition. CVPR, 2018.
Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, and Yasemin Altun. Large margin methods for structured and interdependent output variables. JMLR, 6(Sep):1453-1484 2005.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. In NIPS, 2015.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching, In ICCV, 2019.
P. Welinder, S. Branson, T. Mita, C. Wah, F. Schroff, S. Belongie, and P. Perona. Caltech- UCCD Birds 200. Technical Report ONS-TR-2010-00 California Institute of Technology, 2010.
Hongteng Xu, Dixin Luo, and Lawrence Carin. Gromov-wasserstenn learning for graph matching and node embedding. In ICML, 2019.
Junchi Yan, Chao Zhang, Hongyuan Zha, Wei Liu, Xiaokang Yang, and Stephen M Chu. Discrete hyper-graph matching. In CVPR, 2015.
Tianshu Yu, Junchi Yan, Yilin Wang, Wei Liu, and Baoxin Li. Generalizing graph matching beyond quadratic assignment model. In NIPS, 2018.
Andrei Zanfir and Cristian Sminchisescu. Deep learning of graph matching. In CVPR, 2018.
Zhen Zhang and Wee Sun Lee. Deep graphical feature learning for the feature matching problem. In ICCV, 2019.
Feng Zhou and Fernando De Torre. Factorized graph matching. In CVPR, 2012.
A APPENDIX
A.1 SYNTHETIC TEST
Synthetic graphs are generated for training and testing following the protocol in (Cho et al. 2010).
Specifically, Kpt keypoints generated for pair of graphs with a 1024-dinensional random feature for each node, which is sampled from uniform distribution 2 ( 1, 1). Disturbance is also (1-1,,
applied to graph pairs including: Gaussian node feature noise from (0, o.): random affine trans-
s cos A s ssin A
-ssin tx s f
formation
ty
with 1(0.8,1.2),0 U1 60), la by u(-10, 10)
followed by Gaussian coordinate position noise A/ a2)) By default we assign Kpt 25, a 1.5, 0o 5. Two graphs share the same structure. We generate 10 random distributions for each test. Results are shown in Fig. ( The performance 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.
PCA and CIE is reported. We see our
However, we also notice that the way to generate synthetic graphs is much different from the dis- tribution of real-world data. For real-world data, hand, there is strong correlation the
13

---

Published as a conference paper at ICLR 2020
PCA
+-CIE
-0 0--0
Accuracy
Accuaayy
3.8
1.5
06
Noise
Node size
Figure 6: Results on synthetic test where different loss functions are compared in ablative study.
neighboring node features. This is the reason why the message passing from nearby node features works. However, the features of synthetic data randomly generated and there is correlation between neighboring node features. Therefore, message passing mechanism not very effective to reveal the relation pattern among local nodes for synthetic data. On the other hand, features of real-world data typically lie on manifold embedded in high dimensional space, hence is low di- mensional, 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 novel strategy to generate more reasonable synthetic data. This be of the future works.
A.2 COMPARISON OF PASCAL VOC AND WILLOW
As claim that Willow dataset is biased compared with Pascal VOC dataset, 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, 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 ( consistent to the performance on Pascal VOC (Table As such, we infer the performance degradation of CIE on "duck" in Willow test (Table 2 is due 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-leamn" samples by PCA. This different learning strategy from PCA.
In general,
14

---

Published as a conference paper at ICLR 2020
(a) Car images from Pascal VOC
(b) Car images from Willow
(c) Bird images from Pascal VOC
(d) Duck images Willow
Figure 7: Image examples from Pascal VOC and Willow.
15


Reviews:
[{"review_id": "rkeFNhQucB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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). \n\nIn the current experiment settings, both visual and geometric feature is used. Is it possible for the module to only using geometric features as [1] and [2]?\n\n\n[1] Wang, Yue, and Justin M. Solomon. \"Deep Closest Point: Learning Representations for Point Cloud Registration.\", ICCV 2019,\n[2] Zhen Zhang, and Wee Sun Lee. \"Deep Graphical Feature Learning for the Feature Matching Problem.\", ICCV 2019\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "S1xDXRoc9r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work is expressed clearly and well written. \n\nThe authors propose a new method to learn graph matching. It contributes in two aspects: 1) a new edge embedding strategy and 2) Hungarian attention incorporating with the loss function. A set of experiments as well as ablation studies have been conducted to show the effectiveness of the method.\n\nHowever, my concerns are:\n1) Is the graph matching algorithms only applied in the field of image matching？How about other fields？\n2) And if not, is it more convincing to conduct more experiments across other related fields?\n3) It will be better to give algorithm complexity and parameter analysis with the state-of-the-art algorithms since many additional operations are added.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HkeJVOr0FH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the graph matching problem in the context of vision. Although I am familiar with the graph matching problem, I have much less experience regarding its application in vision. My understanding is that features are extracted from images and used to construct a graph. This graph is then passed through a GNN but there are steps which are unclear. In particular on page 5, 'm and H are fed to a GRU as a sequential input' but I do not see where this fit into the architecture. Similarly, I am a bit confused by equations (8) and (9) as there is a H^(t+1)_v in both equations. Does equation (9) make the function u_t explicit? Then what is \\Gamma_N and similarly what is \\Gamma_E in equation (11)?\nAs it is written, this paper seems more appropriate for a conference in vision. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed a new graph matching approach. The main contribution is a Hungarian attention mechanism, which dynamically generates links in computational graph. The resulting matching algorithm is tested on vision tasks.

The main concern of reviews is that the general matching algorithm is only tested on vision tasks. The authors partially addressed this problem by providing new experimental results with only geometric edge features. Other comments of Blind Review #2 are about some minor questions, which have also been answered by the authors.

Overall, this paper proposed a promising graph match approach and I tend to accept it. 

Decision: Accept (Poster)