Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

Experiments 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.
strength_and_weaknesses: Strengths:
* The paper is quite clear and easy to follow.
* The “revocable” mechanism seems new.
* 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.
* Experiment results show that the proposed approach reaches higher matching quality overall, compared to prior approaches.

Weaknesses:
* 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.
* The proposed solution contains a collection of smaller bits and the entire system has a fair amount of complexity to build.
* 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.
clarity,_quality,_novelty_and_reproducibility: Clarity:
I found the paper to be quite clear and easy to follow.

Quality:
In my opinion, the proposed approach is sound and the experiment results are reasonable and supports the proposed approach.

Novelty:
As discussed in “strengths”, I think the “revocable” mechanism and the approximation of non-QAP affinity score into a QAP formulation are interesting and novel.  The RL formulation and the regularized QAP formulation are more standard.

Reproducibility:
The paper contains a reasonable level of details with an extensive appendix, which are good for reproducibility.  On the other hand the system contains a fair amount of complexity, which makes it harder to reproduce and apply in general.
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.

This 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.

Overall I’m neutral about the paper and wouldn’t mind either accepting or rejecting it.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper introduces a sequential node matching scheme for graph matching, via deep reinforcement learning.

The proposed scheme differs from the majority of existing works that obtain the whole matching in one shot.

The main effectiveness of the proposed method seems to lie in handling outliers.

Experiments on both synthetic and real-world datasets show the effectiveness of the proposed method.


strength_and_weaknesses: [Strength]

1. To the best of my knowledge, using deep reinforcement learning for graph matching is novel;
2. Experimental results are good.

[Weaknesses]

I cannot find major weaknesses, and only have minor comments.

1. 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).

The reason is that the number of vertices in the association graph would be 400 millions.

Probably I should not blame authors for this limitation since there are some previous works on PASCAL VOC.

2. It is partially true to say majority works (Zanfir et al., 2018; Wang et al., 2021a) that assume there is at most one graph
containing 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.

I would expect authors to compare the proposed method with sinkhorn solver (padding slack row and column) in [Learning Feature Matching with Graph Neural Networks].

3. If we remove the second order (edge) affinities, what is the performance of the proposed method?

4. Please provide time comparisons of the proposed method with respect to state-of-the-art methods.

clarity,_quality,_novelty_and_reproducibility: [Clarity]: Neutral
[Quality]: Good
[Novelty ]: Good
[Reproducibility]: Fair
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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:
1. to hardcoding an exact number of inliers at which the agent stops as soon as it achieves,
2. to updating a regularized affinity matrix where the score of overly selection is discounted.
Additionally, a simple yet effective revokable action mechanism is put forward to give the agent the opportunity to “regret” its past suboptimal decision. 
Finally, with all the aforementioned techniques, RGM shows competitive result on both image data and pure combinatorial optimization instances.
strength_and_weaknesses: Strength:
1. Training of Reinforcement-based method proposed in this paper does not require labelled data which is costly and time-consuming in large-scale datasets.
2. 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.
3. Extensive experiments are conducted to proffer a comprehensive analysis.

Weakness:
1. In “chr (12-25)” and “lipa (20-60)” column of Table 4, why the model SK-JA overperforms your proposed method so much?
2. Can you provide some experimental results when the size of training set varies?
3. 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.
4. 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.
clarity,_quality,_novelty_and_reproducibility: In general, the elaboration and formulation is clear so that a broad range of readers can grasp the general idea of the paper. However, several typos are expected to be revised and some detailed formulae need to be better enunciated. This is a novel work that first utilizes reinforcement learning in the back-end solver of graph matching. By regarding GM as a sequential selection task, the model shows robustness for outliers even in the absence of label. Details in the appendix provides a promising reproducibility for this work.
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents a sequential decision process for solving the quadratic assignment problem (QAP).  The model is learned with RL, and a “revocable” mechanism is introduced to allow each step of the process to overwrite the decisions made previously.

Overall reviewers are on the accept side, and acknowledge that the proposed RL for QAP approach is novel, and the experiment results are good.

A couple reviewers raised the scalability issue, which is the biggest issue of this paper and the QAP formulation in general.  The authors should probably think more about the practical usability of this approach, and whether the trade-off between a more expressive but much more expensive QAP formulation and a less expressive but way more efficient matching formulation is worthwhile, and if so in which applications this is really worth doing.
justification_for_why_not_higher_score: Scalability is a major issue that prevents the results of this paper from being widely applicable and having a large impact.
justification_for_why_not_lower_score: Some ideas of the paper is new and experiment results are good.

Reviewers overall favor acceptance.
Decision: Accept: poster