Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching
Authors: Chang Liu
Zetian Jiang
Runzhong Wang
Lingxiao Huang
Pinyan Lu
Junchi Yan
Venue: ICLR 2023 poster (2023)
Keywords: Graph Matching
Reinforcement Learning
Quadratic Assignment
Affinity Regularization
Combinatorial Optimization.

Abstract: Graph matching (GM) has been a building block in various areas including computer vision and pattern recognition. Despite recent impressive progress, existing deep GM methods often have obvious difficulty in handling outliers, which are ubiquitous in practice. We propose a deep reinforcement learning based approach RGM, whose sequential node matching scheme naturally fits the strategy for selective inlier matching against outliers. A revocable action framework is devised to improve the agent's flexibility against the complex constrained GM. Moreover, we propose a quadratic approximation technique to regularize the affinity score, in the presence of outliers. As such, the agent can finish inlier matching timely when the affinity score stops growing, for which otherwise an additional parameter i.e. the number of inliers is needed to avoid matching outliers. In this paper, we focus on learning the back-end solver under the most general form of GM: the Lawler's QAP, whose input is the affinity matrix. Especially, our approach can also boost existing GM methods that use such input. Experiments on multiple real-world datasets demonstrate its performance regarding both accuracy and robustness.

Published as a conference paper at ICLR 2023
REVOCABLE DEEP REINFORCEMENT LEARNING WITH AFFINITY REGULARIZATION FOR OUTLIER-ROBUSE GRAPH MATCHING
Chang Liu', Zetian Jiang', Runzhong Wang Lingxiao Huang", Pinyan Lu Junchi Yan
MMoE Key Lab of Artificial Intelligence, Shanghai Jiao Tong University Shanghai Al Laboratory "State Key Laboratory of Novel Software Technology, Nanjing University
"Shanghai University of Finance and Economics Huawei TCS Lab
fonly-changer, maple.jzt, runzhong... wang, yww.yaan..n.....ae.e cdu.
Maanglingxiao1990881 com, 1u. ww.pinyanmmail..huuee www.auuwe.eeuueu.oooooomoom. PyTorch Code: https: http:///gg........aaaaaaaaaaaaaa
ABSTRACT
Graph matching (GM) has been building block in various areas including com- puter vision and pattern recognition. Despite recent impressive progress, existing deep GM methods often have obvious difficulty in handling outliers, which are ubiquitous in practice. We propose a deep reinforcement learning based approach RGM, whose sequential node matching scheme naturally fits the strategy for se- lective inlier matching against outliers. A revocable action framework is devised improve the agent's 's flexibility against the complex constrained GM. Moreover, we propose a quadratic approximation technique to regularize the affinity score, in the presence of outliers. As such, the agent can finish inlier matching timely when the affinity score stops growing, for which otherwise an additional parameter i.e. the number of inliers is needed to avoid matching outliers. In this paper, we focus on learning the back-end solver under the most general form of GM: the Lawler's s QAP, whose input is the affinity matrix. Especially, our approach can also boost existing GM methods that use such input. Experiments on multiple real-world datasets demonstrate its performance regarding both accuracy and robustness.
INTRODUCTION
Graph matching (GM) aims to find node correspondence between two multiple graphs. As standing and fundamental problem, GM spans wide applications in different areas including com- puter vision and pattern recognition. With the increasing computing resource, graph matching that involves the second-order edge affinity (in contrast to the linear assignment problem e.g. bipartite matching) becomes powerful and relatively affordable tool for solving the correspondence prob- lem with moderate size, and there is growing research in this area, especially with the introduction of deep learning in recent years (Zanfir ct al., 2018; Wang et al., 2019b).
GM can be formulated ment Problem (Lawler's QAP) (Lawler, 1963), which is known as NP-hard. Generally speaking, handling the graph matching problem involves two steps: extracting features from input images to formulate a QAP instance and solving that QAP instance via constrained optimization, namely front-end feature extractor and back-end solver, respectively. Impressive progress has been made for graph matching with the introduction of rich deep learning techniques. However, in existing deep GM works, the deep learning modules mainly applied the front-end, especially for visual im- ages using CNN for node feature learning (Zanfir et al., 2018) and GNN for structure embedding (Li al., 2019). Compared with learning free methods, learnable features have shown more effective- ness. Another advantage of using neural networks is that the graph structure information can be readily embedded into unary node features, as such the classic NPrhard QAP in fact can degener- ate into the linear assignment problem, which can be readily solved by existing back-end solvers
combinatorial optimization problem namely Lawler's Quadratic Assign-
"Correspondence author is Junchi Yan. The work was in part supported by National Key Research and De- velopment Program of China A010A700)))0000, National Natural Science Foundation of China (62222607), Shanghai Municipal Science and Technology Major Project (202157/)700102), and Huawei Technologies.

---

Published as a conference paper at ICLR 2023
in polynomial time. Perhaps for this reason, existing deep GM methods (Wang et al., 2019b; Fey et al., 2020a; Zhao et al., 2021; Gao et al., 2021) mostly focus on the front-end learning, basically ground truth. While the back-end solver is relatively little considered for learning in literature: the authors simply combine their front-end feature extractors with some traditional combinatorial solvers e.g. Sinkhorn (Cuturi, 2013), which means they hardly utilize deep learning to improve the back-end solvers.
by supervised learning using manually labeled node correspondence
Note that outliers in this paper refer to the common setting in literature (Yang et al., 2015): namely the spurious nodes that cannot find their correspondence in the opposite graph for matching, which are also ubiquitous in real-world matching scenarios. While inliers are those having correspon- dences. More specifically, we assume the most general and challenging case that outliers could exist in both two input graphs, which in contrast to the majority of works (Zanfir et al., 2018; Wang et al., 2021a) that assume there is at most one graph containing outliers. Though there is line of works for image matching effectively dismissing the outliers (Fischler & Bolles, 1981; Ma et al,, 2020), these works are basically based on specific pose and motion models in vision, which may not always be available for general GM tasks. Moreover, as mentioned above, existing deep GM works all supervised (or based on supervised learning modules), while in the real world, the labeling is costly and even almost impossible to obtain for large-scale QAP instances in practice.
Towards practical and robust graph matching learning, in the absence of labels and in the presence of outliers (in both input graphs), we propose a reinforcement learning (RI. method for graph matching namely RGM, especially for its most general QAP formulation. In particular, RL is conceptually well suited for its label-free nature and flexibility in finding the node correspondence by sequen- tial decision making, which provides a direct way of avoiding outlier over-matching by an early stopping. In contrast, in existing deep GM works, matching is performed in one shot which incurs coupling of the inliers and outliers, and it lacks an explicit way to distinguish outliers. Therefore, we specifically devise so-called revocable deep reinforcement learning framework to allow small mistakes over the matching procedure, and the current action revocable to research a better node correspondence based on up-to-date environment information. Our revocable framework is shown cost-effective and empirically outperforms the existing popular techniques for refining the local de- cision making e.g. Local Rewrite (Chen & Tian, 2019). Moreover, since the standard GM objective refers to maximizing the affinity score between matched nodes, it causes the over-matching issue i.e. the outliers are also incorporated for matching to increase the overall score. To address this issue, we propose to regularize the affinity score such that it discourages unwanted matchings by assigning negative score those pairs. Intuitively, the RL agent will naturally stop matching spurious out- liers as the objective score will otherwise decrease. With the help of the revocable framework and affinity regularization, our RGM shows promising performances in various experiments. For more clearance, we compare our RGM with most of the existing GM methods in Table 5. Due to the space limit, we place it in the appendix (A.1), where we add a more detailed discussion of the comparison of RGM and existing works. To sum up, the highlights and contributions of our work are:
1) We propose RGM that sequentially selects the node correspondences from two graphs, in contrast to the majority of existing works that obtain the whole matching in one shot. Accordingly, our approach can naturally handle the case for partial matching (due to outliers) by early stopping.
2) Specifically, we first devise revocable approach to select the possible node correspondence, whose mechanism is adapted to the unlabeled graph data with the affinity score as the reward. To the best of our knowledge, this is the first attempt to successfully adapt RL to graph matching.
3) For avoiding matching the outliers, we develop a regularization to the affinity score, making the solver no longer pursue to match as many nodes possible. To our best knowledge, this is also the first work for regularizing the affinity score to avoid over wer-matching among outliers.
4) On synthetic datasets, Willow Object dataset, Pascal VOC dataset, and QAPLIB datasets, RGM shows competitive performance compared with both rearning-free and learning-basee baselines. Note that RGM focuses on learning the back-end solver and hence it is orthogonal to many isting front-end feature learning based GM methods, which can further boost the front-end learning solvers' performance as shown in our experiments.
2

---

Published as a conference paper at ICLR 2023
2 RELATED WORKS
Graph matching, It aims to find the node correspondence by considering both the node features as well as the edge attributes, which is known as NP-hard in its general frrm (Loiola et al., 2007). Clas- sic methods mainly resort to different optimization heuristics e.g. random walk (Cho et al., 2010), spectral matching (Leordeanu & Hebert, 2005), path-following (Zhou & Torre, 2016), graduated assignment (Gold et al., 1996), to SDP relaxation (Schellewald Schnörr, 2005).
Deep learning of GM. Since the seminal work (Zanfir et al., 2018), deep neural networks have been devised for graph matching (Yan et al., 2020). Among the deep GM methods, we generally discuss two representative lines of research as follow. The first line of works (Wang et al., 2019b; Yu et al., 2020) apply CNNs or/and GNNs for learning the node and structure features. By using node embedding, the problem degrades into linear assignment that can be optimally solved by the Sinkhorn network (Cuturi, 2013) to fulfill double-stochasticity which is non-learnable Instead, another line of studies (Wang et al., 2020c) follow the general Lawler's QAP form exactly, and the problem becomes combinatorial selecting of nodes on the association graphs. Yet all the above models adopt supervised learning and there is little reported success using RL to solve GM despite their label-free advantage and popularity in solving other combinatorial problems.
Matching against outliers. Matching against outliers has been long standing task especially for vision, and seminal works date back to RANSAC (Fischler & Bolles, 1981). There are efforts (Tor- resani et al.. 2012: Yang et al., 2015; Yi al., 2018; Zhang et al., 2019; Liu et al., 2020) in exploring the specific problem structure and clues in terms of spatial and geometry coherence to achieve ro- bust matching. While we focus on the general setting of GM without using additional assumptions or parametric transform models, the relevant pair-wise graph matching works are relatively less crowded. Wang et al. (2019a) utilizes the strategy based on domain adaptation, which removes the outliers by data normalization module. A heuristic max-pooling strategy is developed in Cho et al. (2014) for dismissing excessive outliers. Wang et al. (2020a) proposes to suppress the matching of outliers by assigning zero- valuue vectors to the potential outliers. However, all the above methods are learning-free free and the trending learning- based solvers to our best knowledge, have not addressed the outlier problems explicitly except for adding dummy nodes (Wang et al., 2021a).
Reinforcement learning for combinatorial optimization. There is growing interest in using RL in solving combinatorial optimization problems (Bengio et al., 2021), such as traveling salesman problem (Khalil et al., 2017), vehicle routing problem (Nazari et al., 2018), job scheduling prob- lem (Chen & Tian, 2019), maximal common subgraph (Bai et al., 2021), The main challenges of these approaches are designing suitable problem representation and tuning reinforcement learning algorithms. For combinatorial optimization problems on single graph, pointer networks (Vinyals et al., 2015) and GNN (Kipf& & Welling, 2017) are the most widely used representations. However, for graph matching, there are two graphs for input and the agent needs to pick a node from each of the two graphs every step. To our best knowledge, GM has not been (successfully) addressed by RL.
PRELIMINARIES
In this paper, we mainly focus on two graph matching i.e. pairwise graph matching, which is also known as pairwise graph matching. Specifically, we consider a more difficult situation, where there are some outliers in both two graphs, and we want to match the similar inliers while ignoring outliers.
Given two weighted graphs G and G2, we aim to find the matching between their nodes such that the affinity score is maximized. We use V and 22 to represent the nodes of graph GD and G2. We suppose that | = n1. [2| = T22, and there can be outliers in G G², or both. E and E² denote the edge attributes of graph G and G The affinities of pairwise graph matching include the first order (node) affinities and the second order (edge) affinities. Generally, the graph matching problem can be regarded Lawler's Quadratic Assignment Problem (Lawler, 1963):
J(X)= = vX) T K vec(X),
s.t. X {0, 13 X1n, S In, X 1n, S 112
where X is the permutation matrix of which the element is 0 or 1, X(i,a) = denotes node in graph G! is matched with node a in graph G². The operator vec(.) means K E I is the affinity matrix. For node in G¹ and node a in G2 the node-to-node affinity is encoded by the diagonal element K K(ia, ia), while for edge ij in G and edge ab in G the edge- to-edge affinity is encoded by the off off-diagonal element K(ia, jb). Assuming i, a both start from 0,
cuuumm-vctoiizztion..
3

---

Published as a conference paper at ICLR 2023
Kic
Kaus
Kuah
Figure 1: Left: the association graph (G" on the top) can be derived from the raw input graphs ,G,.22 at the bottom). Right: the matching process of our RI. procedure: the blue vertices denote available vertices, the green vertices denote selected (matched) vertices, and the blurred vertices denote the unavailable vertices. The agent selects "la", "2b", and "3c" progressively on G
the index ia means x n2 + a. The objective is to maximize the sum of both first order and second order affinity score J(X given the affinity matrix K by finding an optimal permutation X.
Graph matching involves (at least) two input graphs. Instead of directly working on two individual graphs which can disclose raw data information and might be sensitive, in this paper, we first con- struct the association graph of the pairwise graphs as the input representation (Leordeanu & Hebert, 2005; Wang al., 2021a). Specifically, we construct an association graph G (V*, from the original pairwise graph G and G², with the help of the affinity matrix K. We merge each two nodes (2); va) E V x 22 as vertex Up E Vo. We can see that the association graph contains |V*| = 11 X n2 vertices' .here exists an edge for every two vertices as long as they do not contain the same node from the original pairwise graphs, so every vertex is comnected to (n1 1) x (n2 - -1) edges. There exist both vertex weights w((;)) and edge weights w (Upp 1ig) in the association graph, where the vertex and edge weights denote the first and second order affinities:
F(p.p) p) = w(pp) = ((ia, ia), where = ia
W 4) (Ppp vi)) = K(ia,jb), where ia, q =b
where the vertex index in the association graph G means a combination of the indices and a in the original pairwise graphs G¹ and G F, W "g*1nnx"17g are the weight matrices that contain the vertex weights and edge weights in the association graph, respectively. Fig. shows an example to construct the association graph from the input graphs. the association graph G", selecting a vertex p in the association graph equals to matching nodes and in the input graphs. Therefore, we can select a set of vertices U as we choose to match these nodes as the solution. Note that the set of vertices I in the association graph is equivalent to the permutation matrix X and can be easily converted, as long as the set does not violate the constraint in Eq.
APPROACH
4.1 REINFORCEMENT LEARNING FOR GRAPH MATCHING
We design our RGM based on Double Dueling DQN (D3QN) (Hasselt et al., 2016), as it is widely accepted (Sutton & Barto, 2018) that value based RL algorithms like D3QN can better handle the discrete case, which will be also verified in our ablation study. The pipeline of the training process of RRGM is described in Alg. 1. Details of the proposed method given in Appendix (A.2), includ- ing network structure (A.2.1), prioritized experience replay memory (A.2.2) and model updating algorithm (A.2.3). We show the design of state, action, and reward in RGM:
1) State. The state s is the current (partial) solution U" where U also a set vertices in the association graph, with [U'] S mén(n1, nz)) The size of U' increases from at the beginning, and finally partial solution U' becomes a complete solution U when the agent decides to stop the episode.
2) Action. The action a of reinforcement learning agent is to select vertex in the association graph and add it to the current solution U.. By the definition of graph matching, we can not match two nodes in G to one same node in G and vice versa. Therefore, our basic RL framework, we can only select the vertices in the available vertex set. Take Fig. 1 for an example, once we select the vertex "la", it means we have matched node "I" in G and node "a" in G², Then, we can not
For clarification, this paper uses "node" for the raw graphs and "vertex" for the association graph.
4

---

Published as a conference paper at ICLR 2023
Figure 2:
The different cases of our proposed revocable RGM in several situations.
match node "I" node "b" or "c" later, which means we can not select vertices "1b" or "Ic". Given partial solution U", the available vertices set V is written as;
V {v ( 0') 1, V E UUV VEV")
where Va is the vertices in the association graph, whose adjacency matrix (0 for no edge connected and for existing edge connected) is A. Eq. holds since two vertices are connected if they do not contain the same node from the input graphs. If vertex is connected to all vertices in U then it has no conflict. Given the available set, we mask all unavailable vertices in the association graph to make sure that the agent not select them, as illustrated by the blurred vertices in Fig. 1.
Then, the action is to pick node v from the available vertices set V: Wold "EV, Unews where Uold the old partial solution, and Unew the new partial solution after an action.
It is worth noting that, the requirement that the agent needs to select the vertex from the available set only exists in our basic RL framework. In our later proposed revocable RL framework, the agent can select any vertex without constraint.
3) Reward. We define the reward as the improvement of the objective score between the old partial solution and the new partial solution after executing an action.
4.2 THE REVOCABLE ACTION MECHAANISM
So far we have presented basic RL framework. such a vanilla form, it can not undo the actions that have been executed. In other words, the agent can not "regret", which means the agent has no chance to adjust if the agent makes a wrong decision and the error may accumulate until obtaining disastrous solution. To strike reasonable trade-off between efficiency and efficacy, develop mechanism to allow the agent to re-select the vertex on the association in one revocable step.
To allow the agent modify the decisions made before, design new revocable RL framework. We remove the available set used before, and the agent is free to choose any vertex, even it is in conflict. Then, we modify the strategy in our RL environment. If the environment receives new vertex from the agent's 's action that is in conflict with currently selected vertices, the environment will remove one or two vertices that are in conflict with the new coming vertex, and then add the new vertex to the current solution. Our proposed revocable RL framework is illustrated in Fig. 2.
As Fig. shows, the pipelines of our revocable RGM are little different from our basic framework. The available set in the basic RGM does not exist if the revocable mode is on. Pipeline (A) shows a simple situation that the agent matched the vertices directly without any reverse operation. In pipeline (B), we suppose the agent chooses the vertex "2c" for the second action, which is not good choice. When choosing the third action, the agent realizes that it made a mistake by selecting "2c", therefore, the agent chooses "2b" to fix this mistake. Then, this action is passed to the environment, and the environment reverts "2c" and selects "2b" instead. In other words, the agent can reverse "2c" "2b". In pipeline (C), show another revocable situation. Suppose that the agent selects "2c" and "3b" as its second and third actions, and acquires a complete matching solution. However, it turns out the matching solution ("la", "2c", and "3b") is not as good expected. To roll this
5

---

Published as a conference paper at ICLR 2023
66
64
(a) K
(b) K sese
(c) K
(d) K
Figure 3: Examples of the original affinity matrix and the regularized affinity matrix: (a) original
reg
affinity matrix K; (b)( regularized affinity matrix Kreg by quadratic approximation, with three different regularization functions, of which some values become negative.
situation back, the agent can select "2b" as the next action. By selecting "2b", the environment will release the vertices "2c" and "3b", and then select "2b". Finally, the agent chooses "3e" as the last action, and decides to end the episode with the matching solution ("la", "2b", and "3c").
Above all, our proposed revocable reinforcement learning framework allows the agent to make better decisions by giving the opportunity to turn the way back. From now on in the paper, the default setting of RGM contains the revocable action framework. For further discussion, especially the difference from other similar frameworks (especially the popular Local Rewrite (Chen & Tian, 2019) and ECO-DQN (Barrett et al., 2020)), please refer to the appendix(A.2.4).
4.3 WITLIER-ROBUST GRAPH MATCHINNG
For practical GM, outliers are common in both the input pairwise graphs. In general, the solution is supposed to contain only the inlier correspondences without outliers. However, most existing GM methods are designed match all keypoints whether they are inliers or outliers. This design is based on pursuing the highest objective score, and matching outliers also can increase the objective score to some extent. We believe that the outliers should not be matched in any sense. Therefore, we propose two strategies to guide the agent to match the inliers only and ignore the outliers.
4.3.1 INLIER COUNT INFORMATION EXPLORATION
Our first strategy is to inform the agent of the amount of common inliers. Similar input settings can also be found in learning-fie free outlier-robust GM methods (Yang et al., 2017; Wang et al., 2020a). Given the exact number of inliers n,, the sequential matching of RGM can be readily stopped when the size of the current solution JU'| = n4,, leaving the remaining 11 n, and n2 n, nodes as outliers.
4.3.2 AFFINITY REGULARIZATION VIA QUADRATIC APPROXIMATTION
Our second strategy is to regularize the affinity score (i.e. objective score). As mentioned before, existing GM methods tend to match all keypoints including outliers to make the affinity score as high as possible. Therefore, one straightforward idea is to regularize the affinity score which exerts penalization on mvee-ngg terms to balance the effect of the outliers.
In this paper, we propose to regularize the original affinity score that blindly adds up all the node/edge correspondence affinity values including the outliers. In other words, we aim to design an inlier-aware regularized affinity score denoted by Jreg( (X) to dismiss the effect of outliers in affinity score computing, as the affinity score from the inlier matching is more meaningful. Specifically, the regularization is devised function w.r.t. the number of matched keypoints in X, as denoted by f ([]vec(X)]]1), which is multiplied on the original affinity score as follows:
Jreg (X) = vec Kvec(X): ([Ivec(X)]l1)
In general, [[]]vec(X) shall become smaller when there are more matched keypoints to suppress spurious outliers. For the effectiivness, in this paper we choose the following three functions without loss of generality: (n) = (2
max(m1.n22 f2(n)) = 1+3n fa(n)
1tn
However, the above formula is unfriendly for learning in RGM as our core network GNN can only accept the form of the affinity matrix K namely the association graph as input, while the impact of [([]vec(X)) can not be delivered to the GNN. To fill this gap, in the following, we further pro- pose a technique to transform Eq. into a standard QAP formulation, and construct the regularized affinity matrix K Kreg as the input for the GNN, instead of the original affinity matrix K.
Recall the original score in Eq. and we further denote n. = ||vec (X)lI Eq. 4 can be rewritten as:
Jreg(2 (X) = vec(X) Xv) - J (1- f(n))) )) = vec(X) Kvec(X) - J gg(zz) (5)

---

Published as a conference paper at ICLR 2023
6.5 K2g
K71
621 See 121
3.0
(a) f1
3 3-maa my ma
(b) (2()
1+2
(c) fa(n))
3-moa(nn (ia)
+.n
Figure 4: The empirical relation between Fl and originalrregularized affinity scores. The affinity
score of the original affinity matrix is calculated by yec(XPred) Kvee(X
veo(X (vte(Xat) and affinity score of the
regularized affinity matrix is vec(X(
Kreg vec(X(rred) (at) Kreor)c(XXor)
The score of ground truth is constantly 1.
In the above formula, it worth noting that make the above formula quadratic one, introduce a quadratic function: g(n) = an² + bn + which is used to approximate the term g(n) ~ 1 - f(),, way of least square fitting determine the unknown coefficients a, b, Technically the fitting involves sampling n in a certain range according to the prior of matching problem at hand, e.g. (7, 9, 10, 11, 12]. Then, (()) can be expanded by: (KA (all-one matrix) and K g I) e
g(nx) E(i.)) ((K,)) Σ x(i,)) x(i,)) +
iik!
(6)
(e) (AVe + b. vec(X) Kgvec(X) +
=vec(X) (aKA + bk bKe)) +e
During the iteratively problem solving in RGM, we that J changes relatively slowly between two consecutive iterations, and thus we treat it as a constant during iteration. Based on this observa- tion, we then try approximately convert Jreg into QAP formulation follows:
KA Jreg (X) = vec(X) (K - aJ.K. + bJ KB)vec(X
which is friendly to GNN learning. Let Kreg = K - aJ K - bJ KB and Eq. 5 becomes:
X arg max vec(X) T Kvec(X)) (f(xx))f((llvee) f(llvec(X)]la) = arg max mex X) KecyVec(X
(8)
In this way, now can input the regularized affinity matrix K the GNN, better learn the impact of the regularization term f'( /([]vec(X)]l:) Fig. 3 shows the results of the regularized affinity matrix. Notably, some values in the regularized affinity Kreg become negative. Intuitively, the negative elements in the affinity matrix denote that the affinity score maximization reward may no longer pursue to match as many keypoints pairs as possible, which prevents the agent from picking up outliers to some extent. Besides, most traditional graph matching solvers (Cho et al., 2010; Egozi et al., 2013) assume the affinity matrix is non-negative, while our RGM has no such restriction.
Fig. 4 illustrates the effectiveness of regularized asfinity score, with three different regularization functions (m) We construct a set of permutation solutions by GM solver, and calculate the Fl score and affinity score of the original affinity matrix and regularized affinity matrix. As one can see, the affinity score of the original affinity matrix fluctuates lot with the increase of the Fl score. Besides, there are some cases where original affinity is larger than ground truth matching. In contrast, the regularized affinity score of the regularized affinity matrix is more stable and overall nearly positively correlates to the F1 score. It proves that the regularized affinity score is better optimization objective that is consistent with matching accuracy (F1 score).
This approximate optimization process be merged into our revocable framework as shown in Alg. 1. In the sequential decision making process, at every step when the agent needs to select the next vertex, we make an approximate optimization based on the current solution, and get the regularized affinity matrix Kreg- Then, we feed the regularized affinity matrix Kreg instead of the original affinity matrix K to the GNN. The above introduced regularization technique can be readily adopted in our sequential node matching scheme. In contrast, it is nontrivial for them to be integrated with existing deep GM methods which are mainly performed in one shot for the whole matching.
EXPERIMENTS
We perform experiments on the standard benchmarks including image datasets (synthetic image, Willow Object, Pascal VOC) as well pure combinatorial optimization instances (QAPLIB), as
7

---

Published as a conference paper at ICLR 2023
Table I: Average performance w.r.t F1 score and objective score (the higher the better) in the Willow Object dataset with respect to different numbers of randomly added outliers given the 10 inliers. "AR": affinity regularization, "IC": inlier count information, "w/o rev.": without the revocable.
Method
Obj
11
03
F1
Obj
14
Obi
0k
17
Obj
RRWM al. 2010)
73.00%
71.57%
0.6401
66.00%
0.7089
61.27%
0.7505
56.08%
0.2077
52.21%
0.6836
Learnngg free
GAGM (Gold al. 1996)
89.17%
0.3485
62.99%
0.7657
60.46%
0.7365
57.0015
0.7133
53.85%
0.6675
52.7155
0.5658
IPFP (Leordenn et 2009)
80.89%
0.9189
73.85%
0.8436
69.41%
0.5063
64.07%
0.7896
58.33%
0,7113
55.36%
0.6893
PSM (Ligod) et 2013)
84.33%
0.9047
71.35%
0.332
66.46%
0.7914
50.1716
0.7453
54,565%
0.6862
51.0615
0.6834
GNCCP (Liu et alll.
65.81%
0.9237
77.82%
0.8564
71.07%
0.8164
65.47%
0.7757
59.30%
0,7125
56.17%
0.6891
BPF (Wang 2018)
85.8916
78.15%
0.8566
71.26%
0.5131
63.74%
0.7736
59,47%
0.7119
56.31%
0
ZACR (Wing et al. 2020n)
81.71%
0.9121
74.68%
0,8652
67.98%
0.7824
63.77%
0.7514
57.73%
0.6997
54.75%
0.6821
GMN (Zanfir atal. 2018)
52.52%
72.35%
65.64%
56 56.64%
55.41%
51,958
Supervited
(Wang st.,, 2019b)
79.78%
34.01%
67.31%
59.4116
57.41%
52.31%
LCS (Wang al., 2020k)
86.27%
77.68%
70.49%
66.79%
59,529%
55.615
NGM (Wang 2021
51.2416
74.37%
68.31%
61,9311
56.87%
53.3216
BDGM (Rollnnk et al. 2020)
87.21%
99.84%
73.41%
69 09%
61.79%
58.07%
NGM v2 (Wang et ai, 2021aa
$6.8415
78.90%
73.23%
68,96 96.9616
00.52%
56.73%
RGM AR
35.6 53.63%
0.9664
80.025
0.9543
75.65%
0.928M
71.20%
0.9111
64.11%
0.8845
62. 10%
0.56M2
RGM IC
86 18%
0.9426
50.119%
0.9235
76.72%
0 0.5560
71.78%
0.8673
65.26%
0.8457
64.27%
0.8131
RGM AR
87.68%
0.9601
50.37%
77.57%
73.77%
0.8919
67.49%
0.8633
65.10%
0.8397
RGM AR wio rey.
84.97%
0.9239
78,9
0.8964
72. 19%
0.8702
69. 32%
0.8562
61.50%
0.8053
59.00%
0. 0.7900
RGM IC wis rev.
85.918
0.9111
79.10%
0.8735
72.4256
0.8360
62.07%
0.8173
62.76%
0.7737
61.07%
0.7431
wio rew.
0.8936
73.92%
0,8618
10.
0.8411
63.92%
0.7968
61.26%
0.7574
Table 2: Sensitivity test by using inexact inlier count ranging from 8 to 13, instead of the ground truth 10 on Willow Object. Experiments are conducted with 10 inliers and outliers.
igronnd trath)
Method
F1
City
F1
Gity
F1
Cbgy
F1
F1
O2gy
F1
Ooj
RPF (Wing ol., 20188
71.36%
0.8131
71.26%
0.8131
71 16%
0.8131
71.26%
0.8131
71.36%
0.8131
71.26%
0.813T
BRGM (Kalliik or N150
73:418
73.41%
73.4466
73.41%
75.416
7341%
RUM
033288
7543%%
0191388
75.659%
633388
15663%
003388
75.684
199288
78.084"
"19288"""
RGM IIC
70.789
0.3075
73.78%
0.8600
76.72%
0.8800
73.61%
0.913
71.40%
0,9433
66.969
0.9553
KGM -IC
71.9%%
0.8639
74.87%
0.8967
77.57%
0,9122
75.73%
0.9184
74.78%
0,9244
73.89%
0.9281
the latter is suited for back-end solver. Due to the page limit, the detailed experiment protocols are introduced in the appendix (A.3), including hyperparameter settings (A.3.1), evaluation metrics (A.3.2), compared methods (A.3.3), dataset settings (A.3.4), and the train/test protocols (A.3.5).
5.1 EXPERIMENTS ON WILLOW OBJECT DATASET WITH OUTLIERS
1) Performance over Different Amounts of Outliers. We conduct more experiments with respect to different amounts of outliers. In these experiments, the number of inliers is fixed at 10 while the number of outliers varies from 1 to 6. The experiment setup follows Jiang et al. (2021), and the evaluation is performed on all five categories. For the training and testing process, we follow the data split rate in BBGM (Rolinek et al., 2020) in all experiments. Table shows the performance of method and baselines in the average of all five classes the Willow Object dataset with respect to different amounts of outliers (from 1 to 6). For our methods at the bottom, "RGM + AR" denotes RGM with affinity regularization, "RGM IC" denotes RGM with inlier count information, and "RGM + AR. + IC" denotes RGM with both. For ablation, RGM without the revocable mechanism is shown the last three columns, denoted by "w/o rev.". Regularized affinity and inlier count information are two ways to handle the outliers introduced in Sec. 4.3, RGM reaches the best results over all five classes in this dataset, and gets 4% improvement in average compared to the best baseline BBGM. For the variants of our methods, "RGM + AR + IC" shows the best performance, while "RGM+ + AR" requires no extra information and still outperforms all the baselines.
2) Sensitivity to the Input of Inlier Count. Since in reality, the inlier count information might not be always accurate, we test our methods' robustness against the inexact number of inliers. We re- conduct experiments, of which each image contains 10 inliers and 3 outliers. We modify the inlier count info n, to (8- 13) instcad of ground truth 10, as the input to "RGM IC and "RGM + AR IC". The results in Table 2 show that the performances of these two methods tend to downgrade given incorrect information, as expected, but they can still outperform BBGM in cases when the information is only a little biased. Meanwhile, the regularized affinity matrix can also enhance the robustness. As a result, our RGM can still work well even the inlier count information is inaccurate.
5.2 EXPERIMENTS ON PASCAL VOC
Table 3 reports the results on the Pascal VOC. We also apply the train/test split rate mentioned in Sec. A.3.5. We show the average performance of every 20 classes in this dataset, and we can see that RGM outperforms all baselines on Pascal VOC. Specifically, the baselines on the left side are
8

---

Published as a conference paper at ICLR 2023
Table 3: Average performance over all classes on Pascal VOC. "w/ label" denotes requiring label.
RRWM
GAGM
IPFP
PSM
RGM
GMN
PCA
BRGM
NCM
NGM--2
NGM
NGM622
RGM
F1
48.55%
53.52%
41.948
53.72%
49.8%
54,70%
50.19%
35.306
64,805
08.30%
P9000
D4.101
80.00%
68.E5
SL38R
0lg
1.017
1019
1,017
1.099
1.018
1,200
1,940
1OI5
1011
w/ libel
Table 4: Performance gap with the optimal (%) (the lower the better) on QAPLIB, the mean/max/min gaps are reported for each class. The mean performance over all classes and the inference time (s)
per instance are reported. The number in the bracket is the size of instances in each category.
Terr/0
131-231
Mer116-150 (44
332
1001
(Png 113 -00
Excas
616
exc.
20.
rea
recin
Fause
31.0
1216
3001
3306
311
65.3
0.13
61.3
10.0
11
65:07
xawat
23.1
016.0
1346.3
3.0
20000
23.1
22.3
25.3
58.8
65:2
23.9
41.2
6138
31.3
NGM
204
23.5
RCM
1124
341.1
328
1413
13
201
159
16
253
12.
7.3
22 206
A6- 64
(36)
16.12- 64
0e 465
Avergg (12 64)
Tine per Lavaate
626
19.0
1000
191
Teat
3:44
1933
35.0
360
13.1
11.7
139
1813
549.5
NGM
05.5
41.4
25.2
33.
100.
172.6
167
562.1
27.5
30.2
10.
11.1
62.4
126.7
1532
X0M
382
361
168
83
112
1341
083
20.9
113
114
28
387
127
28
81
75
84
16.
1011
1337
label-free methods, which use the same input as RGM thus leading to fair comparison. In other words, the left side methods are the pure back-end solvers that pursue the highest objective score. We can see that our RGM reaches the highest objective score 1.040, which is clearly greater than 1. However, even with this high objective score, the matching accuracy of RGM is still unsatisfactory.
Then, we conduct experiments with methods on the right side that requires label as supervision, which means their backend-solvers are trained to reach the higher accuracy instead of the objective score. We combine our RGM with SOTA method NGM and NGM-v2, by using their well-trained model as the guidance of RGM for imitation learning. Then, we can find that RGM can boost the performance of original methods with the modified direction, which expands the usage of our RGM.
5.3 EXPERIMENTS ON QAPLIB DATASET
For QAPLIB (Burkard et al., 1997), we use the settings exactly the same as NGM. The results are shown in Table 4, where (1-64" denotes that the size of class "ese" varies from 16 to 64. The train-test split rate for this dataset is (1 1). We calculate the gap between the computed solution and the optimal, and report the average optimal gap (the lower the better). Besides, inference time per instance is listed in the last column. We compare with four existing solvers: SM (Leordeanu & Hebert, 2005), Sinkhorn-JA (Kushinsky et al., 2019), RRWM (Cho et al., 2010) and NGM (Wang et al., 2021a). Note that the NGM is the first that utilizes deep learning to solve QAP which is an emerging topic. shows that RGM outperforms all the baselines, including the latest solver NGM.
5.4 ADDITIONAL EXPERIMENTS
Here we list an index of those experiments in the appendix. If you are interested in several ex- periments listed below, please refer to Appendix. (A.4.1) Experiments the synthetic dataset: evaluating RGM on the synthetic images. (A.4.2) Experiments on the different categories of the Willow Object: results over five categories the Willow Object dataset. (A.4.3) Generalization test of RGM: generalization to different amounts of outliers, similar categories, and different classes of QAP instances. (A.4.4) Hyperparameter sensitivity study: testing the sensitivity of the hyper- parameters in RGM. (A.4.5) Seeded graph matching: graph matching with several initial seeds. (A.4.6) Revocable action v.s. Local Rewrite: comparison of RGM and popular Local Rewrite framework (Chen & Tian, 2019). (A.4.7) Alternative RL backbones: testing alternative RL back- bones instead of D3QN in RGM. (A.4.8) Limitation analysis of the inconsistency: analysis of the inconsistency between the affinity score and the F1 score in the aforementioned experiments.
6 CONCLUSION
We have presented a deep RL. based approach for graph matching, especially in the presence of outliers. The sequential decision scheme allows to natural select the inliers for matching and avoids matching outliers. To our best knowledge, is the first work for RL of graph matching which can be applied to its general QAP form. We further devise two techniques to improve the robustness. The first is the revocable action mechanism which is shown well suited to our complex constrained search procedure. The other is the affinity regularization based on parametric function fitting, which is shown can effectively refrain the agent from matching outliers when the number of inliers is unknown. Experiments on multiple real-world datasets show the cost-effectiveness of RGM.

---

Published as a conference paper at ICLR 2023
REFERENCES
Yunsheng Bai, Derek Xu, Yizhou Sun, and Wei Wang. Glsearch: Maximum common subgraph detection via learning search. In ICML. pp. 588-598, 2021.
Thomas Barrett, William Clements, Jakob Foerster, and Alex Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In AAAI, volume 34, pp. 3243-3250 2020.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: a methodological tour d'horizon. Eur. J. Oper. Res., 290:405 2021.
Lubomir Bourdev and Jitendra Malik. Poselets: Body part detectors trained using 3d human pose annotations. In ICCV, pp. 1365-1372, 2009.
R. Burkard, S. Karisch, and Rendl. Qaplib a quadratic assignment problem library. Journal of Global Optimization, 10:391-403, 1997.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. In NeurlPS, volume 32, 2019.
Minsu Cho, Jungmin Lee, and Kyoung Mu Lee. Reweighted random walks for graph matching. In ECCV, pp. 492-505. Springer, 2010.
Minsu Cho, Alahari Karteek, and Jean Ponce. Learning graphs to match. ICCV, pp. 25-32, 2013.
Minsu Cho, Jian Sun, Olivier Duchenne, and Jean Ponce. Finding matches haystack: A max- pooling strategy for graph matching in the presence of outliers. In CVPR, pp. 2083-2099 2014.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. NIPS, pp. 2292- 2300, 2013.
Hanjun Dai, B. Dai, and L. Song. Discriminative embeddings of latent variable models for structured data. In ICMI,, pp. 2702-2711. PMLR, 2016.
A. Egozi, Y. Keller, and H. Guterman. A probabilistic approach to spectral graph matching. JEEE Transactions Pattern Analysis and Machine Intelligence, 35:18-25 27, 2013.
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. In ICLR, 2020a.
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph
matching consensus. arXiv preprint arXiv:2001.09622 2020b.
Martin Fischler and Robert C Bolles. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24 (6):381-395, 1981.
Quankai Gao, Fudong Wang, Nan Xue, Jin-Gang Yu, and Gui-Song Xia. Deep graph matching under quadratic constraint. In CVPR, pp. 5069-5078, 2021.
Steven Gold, Anand Rangarajan, et al. graduated assignment algorithm for graph matching. JEEE Transactions Pattern Analysis and Machine Intelligence, 18:377-388, 1996.
H. V. Hasselt, A. Guez, and D. Silver. Deep reinforcement learning with double g-lannning. AAAI, volume 30, 2016.
Sergey Ivanov and Alexander D' D'yakooov. Modern deep reinforcement learning algorithms. arXiv preprint arXiv:1906. 10X.11006.10025, 2019.
Zetian Jiang, Tianzhe Wang, and Junchi Yan. Unifying offline and online multi-graph matching via finding shortest paths on supergraph. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43:3648-3661 2021.
Elias Boutros Khalil, H. Dai, Yuyu Zhang, B. Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. In NeurlPS, 2017.
10

---

Published as a conference paper at ICLR 2023
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. ICLR, 2017.
T. C. Koopmans and M. Beckmann. Assignment problems and the location economic activities. Econometrica, pp. 53-76, 1957.
Y. Kushinsky, Haggai Maron, Nadav Dym, and Y. Lipman. Sinkhorn algorithm for lifted assignment problems. SIAM J. Imaging Sci., 12:716-735 2019.
Eugene L. Lawler. The quadratic assignment problem. Management Science, 9:586-599, 1963.
Marius Leordeanu and Martial Hebert. A spectral technique for correspondence problems using pairwise constraints. ICCV, 2:1482-1489 Vol. 2, 2005.
Marius Leordeanu, Martial Hebert, and Rahul Sukthankar. An integer projected fixed point method for graph matching and map inference. In NIPS, volume 22, 2009.
Yujia Li, Chenjie Gu, T. Dullien, Oriol Vinyals, and P. Kohli. Graph matching networks for learning the similarity of graph structured objects. In ICML, pp. 3835- -3455. PMLR, 2019.
Chang Liu, Chenfei Lou, Runzhong Wang, Alan Yuhan Xi, Li Shen, and Junchi Yan. Deep neural network fusion via graph matching with applications to model ensemble and federated learning. In International Conference on Machine Learning, pp. 13857-13866 PMLR, 2022.
Weijie Liu, Chao Zhang, Jiahao Xie, Zebang Shen, Hui Qian, and Nenggan Zheng. Partial gromov- wasserstein learning for partial graph matching. arXiv preprint arXiv:2012.01252, 2020.
Zhi Yong Liu, Hong Qiao, and Lei Xu. An extended path following algorithm for graph-matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(7):1451-1456, 2012.
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, pp. 657-90, 2007.
Jiayi Ma, Xingyu Jiang, Aoxiang Fan, Junjun Jiang, and Junchi Yan. Image matching from hand- crafted to deep features: A survey. International Journal of Computer Vision, 129:23-79, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 132.5:13/ 2013.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In /CML, pp. 1928- 1937, 2016.
Mohammadreza Nazari, Afshin Oroojlooy. Lawrence Snyder, and Martin Takáe, Reinforcement learning for solving the vehicle routing problem. In NeurlPS, pp. 9839-9999988 9849, 2018.
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In ECCV, pp. 407- 424, 2020.
Tom Schaul, John Quan, Ioannis Antonoglou, and D. Silver. Prioritized experience replay. Comput- ing Research Repository, abs/151 15511.05552. 2016.
Christian Schellewald and Christoph Schnörr. Probabilistic subgraph matching based convex
relaxation. In International Workshop on Energy Minimization Methods CVPR, pp. 171-186, 2005.
John Schulman, Sergey Levine, Pieter Abbcel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In ICML, pp. 1889-1897, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: (000::077007777 2017.

---

Published as a conference paper at ICLR 2023
R. Sutton and A. Barto. Reinforcement learning: An introduction. IEEE Transactions on Neural Networks, 16:285-2866 2005.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Lorenzo Torresami, Vladimir Kolmogorov, and Carsten Rother. A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35()): 259-271, 2012.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In NeurIPS, pp. 2692-2700, 2015.
Fu-Dong Wang, Nan Xue, Yipeng Zhang, Gui-Song Xia, and Marcello Pelillo. A functional repre- sentation for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(111::737-22755 2019a.
Fudong Wang, Nan Xue, Jin-Gang Yu, and Gui-Song Xia. Zero-assignment constraint for graph matching with outliers. In CVPR, pp. 3033-3043 2020a.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. In ICCV, pp. 3056-3065, 2019b.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Graduated assignment for joint multi grati-
matching and clustering with application to unsupervised graph matching network learning. In NeurlPS, volume 33, pp. 19908-19919, 2020b.
Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's s quadratic assignment problem with extension to hypergraph and multiple-graph match- ing. IEEE Transactions on Pattern Analysis and Machine Intelligence, PP, 2021a.
Runzhong Wang, Tianqi Zhang, Tianshu Yu, Junchi Yan, and Xiaokang Yang. Combinatorial learn- ing of graph edit distance via dynamic embedding. In CVPR, pp. 5241-5250, 2021b.
Tao Wang, Haibin Ling, Congyan Lang, and Songhe Feng. Graph matching with adaptive and branching path following. IEEE Transactions on Pattern Analysis and Machine Intellignce, 40: 2853-2867, 2018
Tao Wang, He Liu, Yidong Li, Jin, Xiaohui Hou, and Haibin Ling. Learning combinatorial solver for graph matching. In CVPR, pp. 7568-7577, 2020c.
Ziyu Wang, T. Schaul, Matteo Hessel, H. V. Hasselt, Marc Lanctot, and N. D. Freitas. Dueling network architectures for deep reinforcement learning. In ICML, pp. 1995-2003. PMLR, 2016.
Ziyu Wang, V. Bapst, N. Heess, Mnih, R. Munos, K. Kavukcuoglu, and N. D. Freitas. Sample efficient actor-critic with experience replay. ICLR, abs/161 101224, 2017.
Junchi Yan, Minsu Cho, Hongyuan Zha, Xiaokang Yang, and Stephen M. Chu. Multi-graph match- ing via affinity optimization with graduated consistency regularization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38: 1242, 2016.
Junchi Yan, Shuang Yang, and Edwin Hancock. Learning graph matching and related combinatorial optimization problems. In IJCAI, pp. 4988-4888888 4996, 2020.
Xu Yang, Hong Qiao, and Zhi- Yong Liu. Outlier robust point correspondence based on gneep. Pattern Recognition Letters, 55:8-14, 2015.
Xu Yang, Hong Qiao, and Yhi-Yong Liu. An algorithm for finding the most similar given sized subgraphs two weighted graphs. IEEE Transactions on Neural Networks and Learning Systems, (9(7):3295-3300 2017.
Kwang Moo Yi, Eduard Trulls, Yuki Ono, Vincent Lepetit, Mathieu Salzmann, and Pascal Fua. Learning to find good correspondences. In CVPR, pp. 2666-2674, 2018.
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Learning deep graph matching with channel-independent embedding and hungarian attention. In ICLR, 2020.
12

---

Published as a conference paper at ICLR 2023
Andrei Zanfir, Christian Sminchisescu, al. Deep learning of graph matching. In CVPR, pp- 1684-2693, 2018.
Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert. Global alignment of protein-protein interaction networks by graph matching methods. Bioinformatics, 25(12):259-12277 2009.
Jiahui Zhang, Dawei Sun, Zixin Luo, Anbang Yao, Lei Zhou, Tianwei Shen, Yurong Chen, Long Quan, and Hongen Liao. Learning two-view correspondences and geometry using order-aware network. ICCV, pp. 1845-5854, 2019.
Kai Zhao, Shikui Tu, and Lei Xu. la-gm: A deep bidirectional learning method for graph matching. In AAAI, volume 35, pp. 1474-3482 2021.
Feng Zhou and F. D. L. Torre. Factorized graph matching. JEEE Transactions Patlern Analysis and Machine Intelligence.38. 38:1774-1789, 2016.
13

---

Published as a conference paper at ICLR 2023
Table 5: Representative deep GM works. KB's means Koopmans-Reckmann's QAP which is special form of Lawler's QAP. The appearance feature and structure feature are often modeled by CNN and by GNN, respectively. The affinity model often relatively simple by a Gaussian kernel or MLP.
QAP Feem
Leaning Componenus"
Mazchiu Procss
Leantig Photoct
Lawie's
KB'ss
Appasracce
Streetoro
Aftenty
Badi--rd Selver
One-shor
Segarnial
Sipervised
Self Selfssperviod Reinfocommet
Clantireral al, 2010
V
PCA (Wang 20100)
v
y
v
CIE ctu 2020)
v
SGM (Wing al, 2021a)
LCS
2020g
BBGM (Rutlndk 2020
8
8
5
V
GANN (Wang et al, 20200)
8
RGM (murs)
Remark: Despite the benefits of label-free and timely node correspondence generation, our RL module cannot be combined with front-end models for joint feature and solver learning, mentioned in Sec. 1: under the RL framework, at least by our presented reward based on the affinity objective score, it is impossible to jointly train the front-end models with the back-end solver. This is because the reward itself is a function w.r.f. the model parameters of the front end appearance and structure model e.g. CNN/GNN. While in the supervised NGM (Wang et al., 2021a), the ground truth node correspondences as used for loss are computationally irrelevant to the front-end modules thus joint learning feasible. Only NGM (Wang al., 202 2021a)/LCS (Wang et al., 2020c) (these concurrent works are essentially similar at core idea) and RGM can be directly applied to QAP given an input affinity matrix. See results in experiments on QAPLIB in Sec. 5.3.
A APPENDIX
A.1
DISCUSSION WITH EXISTING WORK
Instead of the Lawler's QAP, several GM works choose the Hoopmans-Beckmanti QAP (Koop- mans & Beckmann, 1957), which requires the explicit input of two graphs. We argue that such raw information may not always be available in practice e.g. for privacy. For graph matching, the most general form is Lawler's QAP (Lawler, 1963) whose input is the pairwise affinity matrix whereby the raw graph information is removed and the Koopmans-Beckmann' Beckmann's QAP is a special case for Lawler's ' QAP. There are also standing and widely adopted public benchmarks for Lawler's QAP e.g. QAPLIB (Burkard et al., 1997). For its generality and popularity, SOTA deep GM works (Wang et al., 2020c; 2021a; Rolínek et al., 2020) follow this line, whereby a GNN model is applied on the so-called association graph whose weighted adjacency matrix is the affinity matrix. This GNN model is trained for node embedding on the association graph, which selects the node correspon- dence via supervised learning in one shot. Since Lawler's QAP only requires the affinity matrix and keeps the node and edge information of user unknown, the privacy can be better retained than explicitly using the input graph as done in the Koopmans- -arrrannn--eekmnnn's 's QAP. Therefore, Lawler's s QAP has been adapted to several privacy-sensitive tasks, including model fusion (Liu et al., 2022), bioinformatics (Zaslavskiy et al., 2009), and text alignment (Fey et al., 2020b).
As mentioned in the paper, utilizing label-free revocable RL with affinity regularization for design- ing new back-end solver becomes a promising tool for pushing the frontier of graph matching research. However, here we emphasize our method is focused on the back-end part whose input is the affinity matrix, and our method cannot be combined with learnable CNN and GNN for input graph feature extraction and metric learning part, for joint differentiable front-back-end learning. The reason is that, as will be shown in our approach, the RL reward is parameterized by the front- end CNN/GNN/MLPP which makes end-to-end impossible. For the above reason, our RL solver is trained on the input affinity matrix, by fixing the parameters of the front-end models which can be pretrained via existing supervised methods (Wang et al., 2019b). Table compares existing works for their learning modules and techniques. This protocol is akin to the QAP learning part in (Wang et al., 2021a) which can also be regarded as the inherent limitation with RL. Fortunately, as will be shown in experiments, cially with a large ratio of outliers. Our two-stage training pipeline is also more efficient than joint learning, and thus suitable for our method RL is more costly than supervised learning.
method still can outperform end-to-end supervised methods, espe-
14

---

Published as a conference paper at ICLR 2023
Algorithm 1: Training algorithm for RGM. It also consists of revocable action (Sec. 4.2), inlier count information (Sec. 4.3.1), and affinity regularization (Sec. 4.3.2).
Input: Dataset D; step size vi exploration rate e; updating frequency c1, C2i inlier count ni; max round 7 max: early stop round Tes; reward penalty Tp-
Output: Well trained Q-value network fe.
for episode -- 0, I, 2, ... do
Sample pairwise graphs G G² from dataset D;
Construct the association graph G from G²G2, and get its affinity matrix K; Acquire the initialization state s of G";
for ind 6- 0, 2. .... Tmaz do
# Estimate Q-value:
if Affinity Regularization then Calc. K Kreg for regularization by Eq. 7;
Input Keeg and 8 to GNN Eq. 9; else
Input K and & to GNN in Eq. 9; Get Q from the Q-value network in Eq. 10;
12
14
# Choosing next action:
if Revocable Mechanism then
16
Set available vertices set V to the whole vertices V of the association graph G"; else
17
Calculate available vertices set V by Eq. 3;
With probability select random action a E V otherwise select arg m Q(s, a; fo):
21
Interacting with the environment:
8' _
23
Affinity Regularization then
r J(s'). f((s') - ((s f((s));
25
else
r J(s') Js):
26
if Revocable Mechanism then
28
r r
29
Store the transition (s, a, r, 8') M;
31
# Updating the neural networks: ent 4- cnt + 1;
cnt % C1 = then Calculate L(fo: M) by Eq. 12; Update fo t V M);
33
35
36
Update the transition priority in M; if ent % = 0 then Update fo- So f- Soi
38
39
# Transition:
41
S +- s':
if (Inlier Count and [s] = nı:) or (current best solution unchanged in Tes rounds) then break;
43
15

---

Published as a conference paper at ICLR 2023
A.2 DETAILS OF THE PROPOSED METHOD
The idea of RL. is to learn from the interactions between the agent and the environment (Sutton & Barto, 2005). The agent's s observation of the current environment is called state The agent chooses an action a given the current state by a specific policy. After the agent performs an ac- tion, the environment will transfer another state s'. Meanwhile, the environment will feedback to the agent with a reward r. This pipeline solves the problem progressively. For graph matching, "progressively" means to select the vertex in the association graph one by one. The environment is defined as a partial solution to the original combinatorial problem (Eq. 1) and equivalently the association graph, where the reward denotes the improvement of the objective function by matching new pair of nodes. The interactions between the agent and the environment are recorded as a tran- sition (s, a, r, s') into an experience replay memory M. After several episodes, the agent updates its networks ʃo according to the transitions sampled from M.
A.2.1 NETWORK STRUCTURE
1) State Representation Networks. To better represent the current state on the association graph, we choose graph neural networks (GNN) (Kipf & Welling, 2017) to compute its embedding. GNN extracts the vertex features based on their adjacent neighbors. To better use the edge weights in the association graph, we derive from the idea of struct2vee (Dai et al., 2016). our embedding net- works, the current solution, node weights, and edge weights of the association graph are considered. The embedding formula is:
E+ = ReLUU() + h2 + hg + h4)
A E
h X' OT, h2
02
(ni 1) -
(9)
A F 0J h4 (m) 1) -
E ReeLU -65)
h3
04
(mi (12
where E' E RRmingxd denotes the embedding in the 1-th iteration, with d as the hidden size. At every iteration, the embedding calculated by four hidden parts h1 h2, h3, h4 E Ruingxd 01 Re 82 Rdxd Og RR 04 Rddd and 0g E Rd are the weight matrices in the neural networks. t is the index of the iteration and the total number of the iterations is T. We set the initial embedding E" 0 and use ReLU as the activation function.
As for the hidden parts, each hidden part represents a kind of feature: h1 is to calculate the impact of current permutation matrix X' which is transformed from the current partial solution U". h is to take neighbor's s embedding into consideration, where A is the adjacency matrix of the association graph and divide (n1 - () - 1) is for average since every vertex has (n1 - 1) - 1) neighbors. hy calculates the average of neighbor's vertex weights, where F is the vertex weight matrix. h2 is designed to extract the features of adjacent edges, where W is the edge weight matrix. Please note that the core inputs of our GNN are the permutation matrix X and the affinity matrix K (A, F and W are derived from the affinity matrix K).
2) Q- Value Estimation Networks. The Q-learning based algorithms use (ss, a) to represent the value of taking action a in state s, as an expected value of the acquired reward after choosing this action. The agent picks the next action given the estimation of Q(s, a). The Q-value estimation network So takes the embedding of the current state as input and predicts the Q-value for each possible action. We adopt Dueling DQN ( (Wang et al., 2016) as our approximator to estimate the Q-value function. The architecture of our fo is:
h, hbs O7
h5- = Re
0b + bz),
+ b2,
n2
(10)
Σ ha
h.- he 0g + ba. Q hy + h,
71
where E is the final output of the embedding network by Eq. 9. h; Rnamadd is the hidden layer for embedding. h. E R is the hidden layer for the state function. h E Ramm is the hidden layer for the advantage function. 0g E dd 07 E Rd 0g Ed are the weights of the neural networks. by by. and by are the bias vectors. Q E R is the final output of our Q-value estimate network. It predicts the value of each action given the current state.
16

---

Published as a conference paper at ICLR 2023
The state function and advantage function are designed to separate the value of state and action. Specifically, the state function predicts the value of different states and the advantage predicts the value of each action given the particular state. The previous work (Wang et al., 2016) shows that this dueling architecture can better learn the impact of different actions. Besides, we force the sum of the output vector of the advantage function O by subtracting the mean of it, which makes the separation of the state value and advantage easier. We use Q(s, a; fo) to denote the estimated Q-value by fe when the agent takes action on state s.
A.2.2 EXPERIENCE REPLAY MEMORY
For sample efficiency, we maintain a prioritized experience replay memory M (Schaul et al., 2016) that stores the experience of the agent, defined as the transition (s;, ai ri, ri, s() (denoting state, action, reward, and state of next step respectively). As the training progresses, we add new transitions to M and remove old transitions. The agents will take samples from the experience replay memory to update their neural networks. We follow the idea of prioritized experience replay memory, which adds priority for each transition and higher priority denotes higher probabilities to be sampled:
(pr)
P(1) = Σソ(rz)
(11)
where P(i) is the probability and p; is the priority of the i-th transition. a is a hyperparameter. The calculation of ps is based the underfitting extent of the transition, and larger bias rate of the agent's 's Q-value estimation means relatively higher priority.
A.2.3 MODEL UPDATING
We follow Double DQN (Hasselt et al., 2016) to calculate the loss function and update the param- eters. We pick the next action a' by the current Q-value estimate network fe, but use the target Q-value estimate network fo to predict its value as Eq. 12 shows. The motivation of designing this
loss function is: the Q-value that is overestimated in one network will be mitigated to an extent in another network.
a' arg max Q(s',
(12)
Q(s, [(Jo; Es (rr (rr 705'', al; fo-) - a; fo) [o)"
where C(-) is the loss function to be optimized. fo is the current Q-value estimation network and fo the target Q-value estimation network. 8, a, s', a' stand for the state, action, reward, next state, and next action. The target network fe- shares the same architecture with fo and the parameters of fg- will be replaced by the parameters of fa every period. The design of such a target network is for keeping the target Q value remains unchanged for period of time, which reduces the correlation between the current Q value and the target one and improves the training stability.
A.2.4 FURTHER DISCUSSION OF THE REVOCABLE ACTION FRAMEWORK
Note that our revocable action mechanism requires most changes in our environment settings. There- fore, we design from the original environment are: the available set is gone; the agent can choose any vertex in the vertices Va of the association graph Go when the environment receives a vertex that is in conflict with the current partial solution, it releases the conflicted vertices and adds the new-coming vertex to the partial solution. The agent design is irrelevant to the basic the revocable environment, and the training process of the revocable framework almost remains the same, as Alg. 1 shows. While the revocable flexibility also brings some side effects, e.g. we can not adopt the acceleration tricks for GNN, such as dynamic embedding (Wang et al., 2021b), which can otherwise speedup the inference time.
RI. environment for the revocable action mechanism, and the main differences
As for the stopping rules for our revocable action mechanism, there are three stopping cases and the current best solution will be returned: 1) when the number of matched nodes equals to the given or estimated input inlier count; 2) no affinity score improvement is made (the current best solution remains the same) in Te. rounds where Tes is the given hyperparameter for early stopping; 3) the number of rounds reaches the preset max round parameter Tmaz- Besides, add a small reward penalty rp in each step to make the agent away from repeatedly taking an action and canceling it. The usage of the these parameters can be seen in Alg. 1.
17

---

Published as a conference paper at ICLR 2023
To our best knowledge, there are in general two existing techniques allowing revocable actions, at least for RL-based combinatorial optimization: Local Rewrite (Chen & Tian, 2019) and ECO- DQN (Barrett et al., 2020). Here we discuss our difference from these methods.
The local rewrite framework keeps improving the solution given as input by exchange the parts of it. However, the performance of the local rewrite highly relies on the input solution. In empirical tries, the efficiency and effectiveness of local rewrite are unsatisfactory, as will be shown in our experiments. The ECO-DQN framework does have a promising performance in the Maximum Cut problem, but it is inherently designed to work on this specific Maximum Cut problem, which only has fewer or no constraints, and is clearly impossible to adapt to the graph matching problem. Therefore, in this paper, we devise new revocable framework RGM to meet the characteristic of the graph matching problem, which is more friendly to graph with relatively more constraints. To verify the effectiveness of our proposed revocable framework, we compare it with the local rewrite framework our experiments Sec. A.4.6.
We believe our devised scheme for revocable action is suited to the setting when the graph size is moderate to afford such a costly scheme, while the constraints are relatively heavy and complex to make the revocable action necessary, whereby graph matching has become suited problem setting.
A.3 EXPERIMENTS PROTOCOL
We perform experiments on various benchmarks including image data as well as pure combinatorial optimization problem instances, as the latter is especially suited for our back-end solver. We eval- uate the robustness against outliers, as the (ground truth or estimated) number of inliers is given as hyperparameter. Whenever this information is known not, one can always apply our proposed regularization technique to improve its robustness against outlier. The experiments are conducted on Linux workstation with NVIDIA 2080Ti GPU and AMD Ryzen Threadripper 3970X 32-Core CPU with 128G RAM. Note that the graph size in our experiments is mostly more than 11 and the enumeration of all permutations is at the scale of more than 20 million which means exhaustive search is impossible on commodity computers.
A.3.1
HYPERPARAMETER SETTINGS
For the hyper parameters, we set 0.9 in Eq. 12, the target network update frequency as 40, the replay size as 100,000. For the greedy part, the greedy rate decays from 1.0 to 0.02 in 20,000 episodes. For the learning module, den size of our GNN is 128 and the number of layers T is 3. The hidden size of the Q value network is 64. For the affinity regularization module, the range of the data points used for approximation is S = [nz 2, n2 + 2].
set lc-5 as the learning rate and 64 the batch size. The hid-
A.3.2 EVALUATION METRICS
For testing, given the affinity matrix K, RGM predicts a permutation matrix X E {0, 1 transformed from its solution set Based on Xpred and ground truth X E {0, 1) (note that
Σ X equals the number of inliers, since the rows and columns of outliers are always zeros.). Two
evaluation metrics are used: objective affinity score, and Fl score:
Objective score vec(X!red) T K vec(Xpred)
(13)
vec(Xxt) K vee (oxr)
Σ (Xered X
Recall
(14)
Σ X
Σ (Xpred, * xxt)
Precision
(15)
Σ Xpred
2 Recall Precision
F1 score
(16)
Recall + Precision
where * denotes element-wise matrix multiplication. Note that the defined objective score here is agnostic to the presence of outliers, which is a common protocol used in existing works. Specifically, for a traditional affinity matrix as used in previous works, its elements are set non-negative, and thus the solver generally aims to match node correspondences as many possible.
We also conduct experiments on the well-known QAPLIB dataset. For the problem instances on DIB, the goal is to minimize the objective score. Besides, the ground truth solution is supposed
18

---

Published as a conference paper at ICLR 2023
unknown due to its NP-hard nature. Therefore, the gap between the score of the predicted so- lution and the optimal score provided in the benchmark which is continuously updated by uploaded new best solutions, as the metric:
Optimal gap v T K vec (x.eedd optimal
(17)
optimal
Note that in the QAP test, there no outlier issue, and our solver purely optimizes the objective score, by matching all the nodes.
A.3.3 COMPARED METHODS
As mentioned before, RGM falls in line with learning-free free graph matching back-end solvers that use the affinity matrix K. input, regardless K is obtained by learning- baasdng-bbaed methods or not. Both traditional methods and learning- based methods are compared:
GAGM (Gold et al., 1996) utilizes the graduated assignment technique with an annealing scheme, which can iteratively approximate the cost function by Taylor expansion.
RRWM (Cho al., 2010) proposes random walk view of the graph matching, with re-weighted jump on graph matching.
IFPF (Leordeanu et al., 2009) iteratively improves the solution via integer projection, given a tinuous or discrete solution.
PSM (Egozi al., 2013) improves the spectral matching by presenting probabilistic interpretation of the spectral relaxation scheme.
GNCCP (Liu et al., 2012) follows the convex-concave path-following scheme, with simpler form of the partial permutation matrix.
BPF (Wang al., 2018) designs branch switching technique to seek better paths at the singular points, to deal with the singular point issue in the previous path following strategy.
ZACR (Wang et al., 2020a) designs to suppress the matching of outliers by assigning zero-valee velu-v vectors to the potential outliers, which is the latest graph matching solver designated for outliers.
further compare RGM with current popular deep graph matching methods: GMN (Zanfir et al., 2018), PCA (Wang et al., 2019b), NGM (Wang et al., 2021a), LCS (Wang al., 2020c), BBGM (Rolínek al., 2020), which are the state-of-the-art deep graph matching methods, and more importantly, most of them are all open-sourced which are more convenient for fair comparison.
In particular,
A.3.4 DATASETS FOR EVALUATION
We briefly describe the used datasets, in line with the recent comprehensive evaluation for deep GM (Wang et al., 2021a).
Synthetic Dataset is created by random 2D coordinates nodes and their distances as edge features for graph matching. Specifically, one graph is randomly constructed which random noise is further added to generate the other graph for matching. The ground truth matching normally is set as the identity matrix.
Willow Object is collected from real images by Cho et al. (2013). It contains 256 images from 5 categories, and each category is represented with at least 40 images. All instances in the same class share 10 distinctive image keypoints whose correspondences are manually labeled as ground truth. For testing the performance of handling outliers, we add several random outliers to each image.
Pascal VOC (Bourdev & Malik, 2009) consists of 20 classes with keypoint labels natural images. The instances vary by scale, pose and illumination. The number of keypoints in each image ranges from 6 to 23.
QAPLIB (Burkard et al., 1997) contains 134 real-world QAP instances from 15 categories, e.g. planning hospital facility layout testing of self-testable sequential circuits. The problem size is defined as n, = n2 by Lawler's QAP We use 14 the 15 categories, the only one left "els", as there is only sample in this category.
19

---

Published as a conference paper at ICLR 2023
100
1.00
80
Objective Score
F1 Score (%)
60
0.95
40
REWH
RANS CACM IFF2
GAGM
[BF?
20
0
0.0
0.1
0.2
0.3
0.4
0.5
0.90
0.0
0.1
0.2
0.3
0.4
0.5
5g
6g
Figure 5: Performance comparison w.r.t Fl score and objective score (the higher the better) by increasing noise level on the synthetic dataset.
A.3.5 TRAINING TESTING PROTOCOLS
Due to the complexity in evaluation of learning-based graph matching methods and QAP solvers, here we elaborate the training and testing protocols in detail. We use the open-source version of the compared methods, and we tune or follow the hyperparameters set by the authors, to achieve the sound performance.
For the synthetic dataset, we use geometry features to construct the affinity matrix with the train-test. split rate (2 1) follows Jiang al. (2021).
For the natural image dataset Willow Object and Pascal VOC, we use the pretrained features by CNN and GNN from BBGM (Rolinek et al., 2020) via supervised learning on the training set, and use the pre-splited train/test set (8: 1) in line with BBGM as well. We input the learned affinity matrix to RGM and all learning-fret free methods?, to make the comparison with supervised methods as fair as possible.
For QAPLIB, there is no need for front-end feature extractors as the affinity matrix already given. The train-test split rate for RGM is (1 for each of the selected 14 categories, the smaller-size half of the instances to train RGM in that category. While for the peer method NGM (Wang et al., 2021a), due its model's nature, it does not split the train-test set in their QAPLIB experiments and test directly after training on the same set. In contrast, our RGM follows the basic protocol in RL, which splits the train-test set to make relatively fair comparison with the baselines.
choose
A.4 ADDITIONAL. EXPERIMENTS
A.4.1 EXPERIMENTS ON SYNTHETIC DATASET
We evaluate RGM on the synthetic graphs following the protocol of Wang et al. (2021a). The synthetic data test is relatively simple, and mainly to show the effectiveness of our back-end solver when the front-end information is limited as there is no visual data for CNN to learn. More outlier tests will given on the real data.
We first generate sets of random points in the 2D plane. The coordinates of these points sample from uniform distribution (0, 1) x (0, 1). First, we select sets of points as the set of ground truth points. Then, randomly scale their coordinates from U1(1 ōz, + 8z). The set of scaled points and the set of ground truth points are regarded as the pairwise graphs to matched. We set there 10 inliners without outlier, and the noise level 8, varies from 0 to 0.5. For the calculation of affinity matrix K, the node affinity is set by 0 and the edge affinity is set by the difference of edge
(fa-faa)²), where the fig the edge length of Egy. We generate 300 sets length: Kjn,jb cxp(- z
of scaled points for each ground truth sets and get 3,000 pairwise graphs. We split the data into the training and testing sets by the ratio of (2:
The results of the synthetic datasets shown in Fig. 5. Evaluations are performed in of the noise level 6g. We can see that RGM performs the best in terms of matching F1 score and objective score in all experiments.
ZZACR is exception which will be explained in Sec. A.4.2 in detail.
20

---

Published as a conference paper at ICLR 2023
Table 6: Performance comparison w.r. F1 score and objective score (the higher the better) in the Willow Object dataset, where "FI" and "Obj" are short for Fl score and objective score. All images contain 10 inliers and randomly generated outliers in both graphs. For our RGM, "RGM + AR" means RGM with affinity regularization, "RGM + IC" means RGM with inlier count information, and "RGM + AR IC" means RGM with both. We add the ablation study about RGM without the revocable mechanism in the last three column of the table, denoted by "w/o rev.".
Class
Duck
Fooe
Motasbike
Winchettle
Avcrage
Method
Fi
Ohj
F1
Ohj
F1
Obj
F1
Okg
F1
Ofg
F1
Otg
RRWM et 2010)
65.45%
0.3039
60.25%
0.7105
84.2115
0.9565
54.0415
0.7332
06.1915
0.7810
06.001
0.7989
GAGM (Gold et.l. 1996)
57,50%
0.7186
53.59%
0.6778
82.8716
0.9478
47.38%
0,6325
60.96%
0.7085
00.46%
0.7365
Learning free
IPFP (Loondion at all, 2009)
71 16%
0.8394
62.29%
0,7235
84 84.65%
0.9695
60.07%
0,7344
68.86%
0,7905
69.415
0.8063
PSM (Fgorri et 2013) 2013)
66 66.64%
0.5047
61.22%
0,7345
82.79%
0,9336
55.63%
0,7103
66.0214
0
66.46%
0.7914
GNCCP (Lin et al., 2012)
73.65%
0.5484
63.714
0,7459
84.38%
0,9628
62.20%
0,7314
71.43%
0.7966
71.07%
0.8164
BPF (Mang et al, 2018)
74.00%
0.5465
02.91%
0,7342
84.38%
0,9628
63.09%
0,7354
71.90%
0,7880
71,261
0.8131
ZACR (Wang al. 2020gg
66.27%
0.7899
61.67%
0
84.591
0,9531
59.2716
0,6881
68.10%
0.7937
67.98%
0.7824
GIN (7anfir 201 89
57 99999%
57.87%
86 66%
58. 18%
67,528
65 64%64%%
Supervised
PCA (Nlagg al., 2019h)
71. 1..00%
57.80%
86 12%
57.89%
65.74%
67.71%
LCS (Wang 2020e)
72.25%
61.500 61.90%
86 8.1
62.35%
69.1514
70.49%
NGM (Wing et all, 2021s)
68.77%
61.09%
86-5815
55.65%
69.48%
68.31%
BRCM (Rolinck al., 2020)
76 16%
63.62%
96.71%
60.00%
69.70%
73.41%
(Wing 202
78.76%
63.04%
71.19%
73.23%
75.14%5
63.40%
0,8932
97.0015
0.9671
65.8815
0.885N
73.731%
0.0236
75.701%
0.9258
80.601
1.5819
63.30%
0,8369
97.301
0.9538
68.001
0.8603
73.30%
0.8683
76.70%
0.8M60
IC
N1.65%
119389
66.57%
0,8685
97.80%
0.9538
67.30%
0.8639
74.53%
0.9061
77.57%
0.9122
AR wer
71.201
0.8066
56.48%
0.8302
96
0.9342
66.00%
0.8250
70.04%
0.8649
72.19%
0.8702
wew
70. 10%
0.8309
56.50%
0.7869
94.73%
0.9338
69. 1811
0.8103
71.57%
0.8183
72.425
0.8360
RCM IC wfa
72.69%
0,5880
90.58%
0.8181
96.91%
0.9338
69 115
0.8139
71.30%
0.8552
73.025
0.8618
A.4.2 PERFORMANCE ON THE WILLOWW OBJECT DATASET
Table shows the results over the five categories give three outliers. We compare our methods (bottom box) with the learning-free back-end solvers (top box) and the learning based deep graph matching methods (middle box). We use learning features extracted by BBGM (Rolinek al., 2020) to construct the affinity matrix, which is used as input for all learning- free back-end solvers and our methods. For other learning-basee baselines, we train and test them by their own pipelines directly, and they do not report their objective score because learning-based methods only care about the accuracy or Fl score. Since there are several outliers that should not be matched, the ground truth matching results only contain parts of the input keypoints (10 actually). Therefore, we use the Fl score instead of accuracy to test the performance.
One may attribute the advantage of "RGM + IC" and "RGM+ AR IC" to the use extra information of the inlier count which is a unique ability of our RL-based model compared to peer baselines. Yet "RGM- + AR" does not require the inlier count information input, and can still outperform all baselines in almost all settings.
We find a strange result that BPF (Wang et al., 2018) reaches the best performance rather than ZACR (Wang et al., 2020a), which is the latest GM solvers tailored for handling outliers. Per dis- cussion with the authors of ZACR, this is perhaps mainly due to few strong assumptions they made which is more suitable to the 50 images (30 cars and 20 motorbikes) they used for experi- ments in their paper, which may not always hold in other datasets including Willow Object. For example, ZACR requires edges linked by two inliers have clear higher similarities than the edges linked by inlier-outlier or outiier-oulier. Besides, by its inherent design. ZACR solves Koopmans- Beckmann's 's QAP instead of Lawler's 's QAP, and therefore has some difficulty utilizing the affinity matrix which is obtained by pretraining BBGM. Via the communication and discussion with the authors of ZACR, we have tried to modify their code including using the learned node and edge features inline with their model's intereface. Regrettably, the results in Table 6 and Table I are the best results we get.
The matching visualization is given in Fig. 6. We visualize the matching results of RGM on all five categories. We paint the inliers as green nodes and the outliers as blue nodes. In each pair of images, the green and red lines represent correct and incorrect predictions respectively. Since it is supposed to match all inliers and ignore the outliers, we can see that RGM barely matches the blue outliers and focuses on the green inliers.
21

---

Published as a conference paper at ICLR 2023
Dack 92
OLEC AAM
DLCE
LK 56
Dud X
Motest: 31
Nesabil 100
Molabio 8G
Verable 20
Neterslo 310
Figure 6: Visual illustration of the matching results by RGM the Willow Object dataset with 10 inliers (green), and 3 outliers (blue) which are randomly extracted from the images. Green and red lines represent correct and incorrect node matchings respectively. The correct solution is supposed to match all green inliers with green line, The subtitle of each figure shows the correct incorrect matching count out of the 10 inliers.
Texting Amounc of Outliers
2
5
Ontffess
90.8%
87.1%
78.5%
76.1%
68.1%
63.8%
60.9%
89.9%
87.7%
79.1%
75.9%
69.8%
65.1%
62.0%
89.8%
86,8%
80.4%
97.3%
71.2%
64.5%
64.8%
87.2%
73.6%
67.1%
63.9%
73,8%
86.4%
85.7%
78.5%
77.1%
72.9%
67.5%
64.7%
88.0%
85.6%
77.9%
76.3%
72.3%
66.1%
68.1%
Figure 7: Generalization test for number of outliers by F1 Score (t). Row and column indices denote the amount of outliers on training and testing set, respectively. The average F1 on all five classes in Willow Object is reported. For each testing set (column), the darker red the better.
A.4.3 GENERALIZATION
1) Generalization to different amounts of outliers. We carry additional experiments to test the generalization ability among different numbers of outliers. In this study, we train RGM on one certain number of outliers and test it on another setting. We conduct these experiments on Willow Object with 10 inliers and range of outliers from 6. The results are shown in Fig. 7, where for every testing case (column) darker red means better performance. We can see that our RGM can generalize well the different numbers of outliers, since the performance of RGM is promis- ing. Relatively speaking, training RGM with 2, 3, or 4 outliers can reach a better generalization performance, and training RGM with 3 outliers can reach the best.
2) Generalization among similar categories. Fig. 8 (a) shows the generalization ability of RGM among similar categories. We use one class for training and another class for testing. For every testing class (every column) the red is the darker the better. We can RGM generalizes well to different classes.
2) Generalization QAPLIB. Fig. 8(b) shows the generalization ability of RGM, which is trained on one class and tested on another. For every testing class (every column), the darker red means the low optimal gap, the better performance. It shows that RGM generalizes soundly to unseen instances with different problem sizes.
A.4.4 HYPERPARAMETER SENSITIVITY STUDY
We conduct the study on Willow Object with the same setting aforementioned experiments, where there are 10 inliers and 3 outliers in each image. We choose six hyperparameters: batch size, 7 ex- perience replay size, hidden size in GNN, hidden size in Q value network, and set the regularization function for affinity regularization by three function forms. The results in Fig. 9 show that RGM is not sensitive to hyperparameters in batch size, hidden size, and regularization function, since there
22

---

Published as a conference paper at ICLR 2023
Tiding
Ten20
Car
Bus
Chait
Sola
Dog
Cat
Train
TV
Tradinginttin
6mhh
13.3%
644
Chair
3300
4000%
$3.2%
48..%
37.2%
44.9%
37.48%
30.5%
36.%
1242%
6.7%
10t
11.8%
233%
11.%
18.5%
6.%
1550%
6.75
155%
1811%
Dog
17.8%
28.3%
Train
51.0%
6840%
30.3%
44.1%%
41.3%
52.9%
88.7%
83.0%
(a) Pascal VOC dataset
(b) QAPLIB dataset
Figure 8: Generalization test w.r.t (a) F1 score (t), (b) optimal gap (4). Row and column indices denote training and testing classes, respectively. For every testing class (column), the darker red the better.
78
78
78
76
76
76
72
72
72
70
0.8
5e3
Batch Size
Gamma
Replay Size
78
78
78
76
76
76
72
72
72
70
70
70
Hidden Size of GNN
Hidden Size of Network
Regularization Function
Figure 9: Hyperparameter sensitivity study for revocable deep reinforcement learning: the sults over different values of hyperparameters, The experiments are conducted on the Willow Object with 10 inliers and 3 outliers. The average Fl score (f) on all five classes reported.
100
100
90
90
F1 Score (%))
80
80
70
2
Number of Seeds
Number of Seeds
(a) Synthetic Dataset
(b) Willow Object Dataset
Figure 10: Case study: performance comparison w.r.t F] score (1) in terms of different numbers of initial matched seeds (i.e. node pairs).
only small fluctuations in Fl score. Here 7 is the hyperparameter in Eq. 12 as the rate for con- sidering current reward and long-term term reward, whose value cannot be too high too low. RGM performs badly when the replay size is too small for experience replay.
A.4.5 CASE STUDY: SEEDED GRAPH MATCHING
As aforementioned, the core of RGM is to learn the back-end decision making process for GM. Moreover, RGM can work flcxibly by utilizing additional information e.g. the initial seeds, which mean that several nodes in each of the original pairwise graphs is already matched by human or other information sources. In implementation, we only need to set the initial seeds as the first several actions, and then let RGM execute normally.
We conduct this case study on both the synthetic dataset and the Willow Object dataset, of which each image contains 10 inliers and 3 outliers. Fig. 10 shows that adding suitable initial seeds does
23

---

Published as a conference paper at ICLR 2023
Comparison with the local rewrite (LR) (Chen & Tian, 2019) boosting technique QAPLIB dataset w.r.t the optimal gap (the lower the better) and inference time in seconds, where "+LR" denotes using local rewrite given the output from the original methods, and "RGM w/o rev." denotes our method without the revocable mechanism as described in Sec. 4.2.
Table 7:
Time per
QAPLIB
instance
menn
min
max 1
SM (Leordeanu Hebert, 2005)
0.01
181.22%
46.93%
94%
+ LR
47.51
119.14%
44.21%
291.15%
RRWM (Cho et al., 2010)
0.15
169.50%
49.51
432.94%
+ LR
47.93
100.19%
46.25%
223.8499 84%
SK-JA (Kushinsky et al., 2019)
563.44
93.23%
9.03 %
497.915 %
LR
623.18
73.87%
9.03%
212.53%
NGM (Wang et al., 2021a)
15.72
62.35%
17.78%
129.75%
+ LR
69.57
54.41%
16.54%
117.36%
RGM w/o rev.
47.24
41.49%
12.58%
119.75%
+ I.R
96.45
39.70%
11.65%
109.47%
RGM
75.53
35.84 %
10.74%
101.13%
80.0
77.5
75.0
72.5
Scor
70.0
65.0
62.5
60.0
A2C
ACER
TRPO
PPO
DDQN
D3QN
Figure 11: Average Fl score (1) of different RL algorithms, on five classes of Willow Object with 10 inliers and outliers in both sides for matching.
Table 8: Quantile of objective and Fl score of the solutions found by RGM and RRWM on bus category Pascal VOC without outlier. The discrepancy of F1 score and objective score clear.
Objective range
(0.00, 0.99)
[0.99, 1.00)
= 1.00
(1.00, 1.50)
Proportion
38.4%
20.0%
11.9%
29.7%
RRWM
Fl score
42.1%
68.6%
100.0%
62.4%
Proportion
4.0%
11.6%
45.0%
39.4%
RGM
Fl
40.6%
61.2%
100.0%
56.5%
improve the performance, which can be useful when the matching can be conducted by manual annotation in the beginning.
A.4.6 ABLATION STUDY: REVOCABLE ACTION V.S. LOCAL REWRITE
We study the effectiveness of our revocable action scheme, by comparing it with the local rewrite (LR (Chen Tian, 2019)) under the same RL framework. LR is an influential mechanism in RL- based combinatorial optimization. It tries to improve given solution instead of generating one from scratch. To some extent, LR can also reverse the applied actions by its local rewrite mechanism and it is recognized state-of-the-an technique for improving RL.
We conduct comparative experiments on QAPLIB. We use LR to improve the solution given by the baselines and RGM without the revocable scheme (RGM w/o rev.), and compare the results with RGM. Table shows that our revocable framework RGM still performs the best compared to all boosted baselines. tums out LR does improve the original solutions, but its performance and efficiency is still below our revocable framework.
24

---

Published as a conference paper at ICLR 2023
A.4.7 ABLATION STUDY: USING ALTERNATIVE RL BACKBONES
In RGM, we adopt Double Dueling DQN (D3QN) with priority experience replay as our backbone, for which we perform ablation study against alternatives on Willow Object with 10 inliers and outliers. Fig. 11 shows the mean Fl score over five classes. We compare D3QN with popular backbones: A2C (Mnih et al., 2016), ACER (Wang et al., 2017), TRPO (Schulman et al., 2015), PPO (Schulman et al., 2017), the original DQN (Mnih et al., 2013), and Double DQN (Hasselt et al., 2016), D3QN outperforms all other algorithms in the Willow Object. We think that the main reason is that: graph matching methods (DQN, DDQN, D3QN) can be more suitable than the policy based methods, which is widely accepted (Sutton & Barto, 2005; Ivanov D yakonov, 2019; Sutton & Barto, 2018).
discrete decision making problem, where the value based
A.4.8 INCONSISTENCY BETWERN AFFINITY ORJECTIVE AND F1
Finally, we discuss a standing issue in graph matching and possibly also in other optimization tasks regardless the presence of outliers. The matching accuracy Fl score inconsistent with the value of objective function. In our analysis, the reason is probably that the objective function cannot perfectly model the ultimate goal, due limited modeling capacity and noise etc. For example, as shown in Table 8, when applying our RGM and RRWM (or any other method is fine from the different-quality solution sampling perspective) on the real image dataset Pascal VOC, the resulting quantile statistics about the objective score deliver important message: 39.4% sampled solutions by RGM can achieve an objective score even higher than one, which means these wrong solu- tions can even get higher score than the ground truth matching. Note that the front-end features CNN/GNN and affinity metric model are learned by the state-of-the-ar supervised model BBGM, however the learned affinity function seems still not perfectly fit with the Fl score. In fact, this mis- match issue relates to the front-end affinity learning and outlier dismissing, which is not the scope of the back-end solver as focused in this paper. As Table 8 shows, though there are 39.4% instances whose affinity scores are larger than 1, at the other 60.6% instances, our RGM can solve three- quarters of these instances perfectly. Compared RRWM, our RGM can solve more instances with the affinity score equals to or nears to one, and that's why our RGM can outperform RRWM and other baselines. Despite its impressive results achieved in our paper, it also suggests the limitation of RL-based solvers which pursuits the high objective score which can sometimes be biased. One possibly mitigation way is involving multiple graphs (Yan et al., 2016; Jiang et al., 2021) which we leave for future work.
25


Reviews:
[{"review_id": "vMipav0WHT", "reviewer": "Reviewer_bTMW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "This paper introduces a sequential node matching scheme for graph matching, via deep reinforcement learning.\n\nThe proposed scheme differs from the majority of existing works that obtain the whole matching in one shot.\n\nThe main effectiveness of the proposed method seems to lie in handling outliers.\n\nExperiments on both synthetic and real-world datasets show the effectiveness of the proposed method.\n\n", "summary_of_the_review": "Though it is novel to introduce deep reinforcement learning, the proposed method can only work for toy-scale graph matching and the comparison with respect to sinkhorn solver (padding slack row and column) is missing.", "strength_and_weaknesses": "[Strength]\n\n1. To the best of my knowledge, using deep reinforcement learning for graph matching is novel;\n2. Experimental results are good.\n\n[Weaknesses]\n\nI cannot find major weaknesses, and only have minor comments.\n\n1. The proposed method can only handle very small-scale graph matching problem (almost toy examples). It is very hard to extend the proposed method for large-scale graph matching (~2000 nodes for each graph).\n\nThe reason is that the number of vertices in the association graph would be 400 millions.\n\nProbably I should not blame authors for this limitation since there are some previous works on PASCAL VOC.\n\n2. It is partially true to say majority works (Zanfir et al., 2018; Wang et al., 2021a) that assume there is at most one graph\ncontaining outliers.  For example, using the sinkhorn solver with padded slack row and column would naturally solve matching when outlier s exist in both two graphs.\n\nI would expect authors to compare the proposed method with sinkhorn solver (padding slack row and column) in [Learning Feature Matching with Graph Neural Networks].\n\n3. If we remove the second order (edge) affinities, what is the performance of the proposed method?\n\n4. Please provide time comparisons of the proposed method with respect to state-of-the-art methods.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "nuM6WkZCnOt", "reviewer": "Reviewer_QGQe", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "This paper presents an approach for solving the quadratic assignment (QAP) graph matching problem, which matches nodes across two graphs and the matching quality is measured with the affinity of both the matched nodes as well as the matched edges.  The approach is a collection of smaller things, including (1) an RL formulation of the sequential decision process that matches one pair of nodes at each step; (2) a “revocable” mechanism that allows each step to overwrite previously matched pairs; (3) a regularized affinity score to handle outliers and (4) an approximation scheme to convert the regularized affinity score back into a QAP formulation.\n\nExperiments on synthetic tasks, key-point matching tasks in the computer vision domain and on the standard QAP instances from QAPLIB show that the proposed approach seems to be working well.", "summary_of_the_review": "I have reviewed this paper twice before for another venue, and it has improved a lot since then, with many of the reviewers’ suggestions incorporated in this submission.\n\nThis paper as it stands now has clear strengths and weaknesses, with a few novel ideas and experiments showing that this approach does outperform previous work quite consistently; on the other hand, scalability seems like a pressing issue that significantly affects the applicability of this approach.  Given the state of the current field of computer vision where key point matching can already handle orders of magnitude more keypoints than this proposed approach is capable of doing, I think this paper won’t have an immediate impact on the field.  But once the scalability problem is alleviated, or with a better matched application where the QAP formulation is really required, this approach could have a larger impact.\n\nOverall I’m neutral about the paper and wouldn’t mind either accepting or rejecting it.", "strength_and_weaknesses": "Strengths:\n* The paper is quite clear and easy to follow.\n* The “revocable” mechanism seems new.\n* The approximation of the non-QAP affinity score into a QAP formulation is interesting and could be a convenient and fairly general way to handle other types of optimization problems.\n* Experiment results show that the proposed approach reaches higher matching quality overall, compared to prior approaches.\n\nWeaknesses:\n* The most significant weakness is that the proposed approach and QAP formulation is very expensive, $O(n_1^2 n_2^2)$, which is $O(n^4)$ for comparable $n_1$ and $n_2$, for each step, and the proposed approach is fundamentally limited to do graph matching for very small graphs.  The largest graph considered in the experiment contains up to just 64 nodes, and I don’t see a clear way to scale this up to instances of significantly larger scale.  Therefore the applicability of this approach and formulation seems to be very limited.\n* The proposed solution contains a collection of smaller bits and the entire system has a fair amount of complexity to build.\n* Structure of the paper could be improved - introduction seems to be a bit too long, while many results have to be left in the appendix.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BVQ_XBVtx6R", "reviewer": "Reviewer_6KL8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "This paper introduced deep reinforcement learning into the study of graph matching to tackle the ubiquitous outliers in practical application. Traditional back-end solvers generate the matching result between graphs in a single forward propagation attempting to maximize affinity score. However, the blindly pursuing higher affinity score induces to involve outliers because all elements in the affinity matrix are positive in most cases. Therefore, graph matching is modelled as a sequential selection task on the association graph in this paper, where the agent is expected to early stop when inliers are all selected instead of selecting the left outliers. In order to make their methods robust and prevent the agent from selecting superfluous vertices, the authors propose two strategies:\n1. to hardcoding an exact number of inliers at which the agent stops as soon as it achieves,\n2. to updating a regularized affinity matrix where the score of overly selection is discounted.\nAdditionally, a simple yet effective revokable action mechanism is put forward to give the agent the opportunity to “regret” its past suboptimal decision. \nFinally, with all the aforementioned techniques, RGM shows competitive result on both image data and pure combinatorial optimization instances.", "summary_of_the_review": "This paper proposes a deep RL-based model for robust and unlabeled graph matching. Revokable action mechanism and affinity regularization is proposed to fit with the RL schema and further boost the robustness. Exhaustive experiments have been conducted to prove the effectiveness of their method. Additionally, a fact is observed that there does not exist a constant positive correlation between our target metric, F1 score, and the optimized metric, objective score, which has a potential inspiration for other researches for further study.", "strength_and_weaknesses": "Strength:\n1. Training of Reinforcement-based method proposed in this paper does not require labelled data which is costly and time-consuming in large-scale datasets.\n2. The proposed method is a back-end solver for the most general form of GM with Lawler’s QAP as the input, which means it’s a plug-and-play learning-based module for multiple front-end models.\n3. Extensive experiments are conducted to proffer a comprehensive analysis.\n\nWeakness:\n1. In “chr (12-25)” and “lipa (20-60)” column of Table 4, why the model SK-JA overperforms your proposed method so much?\n2. Can you provide some experimental results when the size of training set varies?\n3. As for formulae, Eq (7) has a wrong sign. And there exist several pieces that I am unable to understand. “F,W ∈ R^{n1×n2}” contradicts with Eq.2 above which indicates F and W are matrices of n1*n2 rows and n1*n2 columns instead of a matrix with n1 rows and n2 columns. In Eq. 9, h1 = X’ • θ1^T where X’ is a permutation matrix which is a 0-1 matrix with a shape of (n1, n2). But h1 is of the shape (n1*n2, ). So I wonder how it can be made. Still in Eq. 9, on the RHS of the calculation of h4, W is an edge weight matrix which is ought to be a matrix in R^{n1*n2 × n1*n2} according to the corrected  formula “F,W ∈ R^{n1×n2}”. However, “θ5 ∈ R^d” as is written in the paper. I cannot understand how these two matrices multiplied.\n4. Several grammar mistakes and typos are made in the paper, e.g., “learnable features are shown more expressive” (probably means “have shown”?), “a also”, “the our”, “treat is as a constant”, “Wwe”, etc.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster