Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: The authors address the problem of discrete keypoint matching. For an input pair of images, the task is to match the unannotated (but given as part of the input) keypoints. The main contribution is identifying the bottleneck of the current SOTA algorithm: a fixed connectivity construction given by Delauney triangulation. By replacing this with an end-to-end learnable algorithm, they outperform SOTA with a decent margin.

Contribution & significance: The topic of discrete keypoint matching has had a lot of progress in the last five years and is gaining attention even from more product-oriented branches of computer vision. The benchmarks used for evaluation (PASCAL-VOC, SPair71k) are, in fact, quite difficult, and even 2-3 points of progress require non-trivial effort. The core insight of improving this particular part of the pipeline is creative and novel. In these regards, the paper certainly meets the bar set for ICLR.

Experiments are conducted thoroughly and on multiple standard datasets. I appreciate the ablation study. Minor suggestions are below.

Weaknesses:

1) **Code**  For a mostly experimental paper, it is imperative to release code (as is also common in the line of work for keypoint matching). If the code was already uploaded, I would have given the paper a higher rating.

2) **Co-generative model** The authors for some reason insist on this interpretation of their architecture (it appears in boldface in the abstract). In practical terms, it means that a) one term of the loss function doesn't depend on ground truth b) a reparametrization trick is used. I do not think, this justifies making the co-generative a central point of the paper. In my eyes, it would simply help the paper if these remarks were removed.

3) **Relevance for wider ICLR community** Given the very specialized domain, the work would perhaps be a better fit for a conference fully focused on computer vision. Note that e.g. (Fey, ICLR 2020) included also NLP experiments and made a more general point about matching procedures. I am afraid that in the current form, this paper won't attract too wide ICLR audiences. Is there a way to demonstrate/make-a-plausible-case-for wider applicability?

4) **At times unclear writeup** It wasn't always easy to understand what exactly the authors mean. Both in natural language and in technical parts. In the technical parts, the authors use very heavy notation and produce multiple large formulas that on the other have very standard content (e.g.. eq 11 and 14). On a technical level, the tools applied to introducing differentiability are very standard.  But that is absolutely fine since the core contribution is **where** they are applied.  There is no need to "produce enough formulas" such as by rewriting standard ELBO arguments over much larger notation (as it is in Appendix A3).

5) **Qualitative analysis** This is a missed opportunity. High-quality images that clearly demonstrate where the advantage is coming from, could easily be a highlight of this paper and should certianly be present in the main text. The current analysis in the supplementary is quite short and the displayed images are tiny, very hard to understand and **in almost all cases do NOT show the difference between the baseline and the proposed method.** I can't stress enough how instructive it would be to insert a section where eg. only examples of tables are analyzed (since that's the class with maximum gain) and one can clearly see what the architecture does differently (without zooming to 400%). Some parts of the technical presentation could be shortened.

Minor remarks follow:
- line 4 - footnote: It only is without loss of generality when negative costs are allowed, otherwise the argmax is always a maximal matching and outliers are not ignored.
- line 4 (LaTeX): This symbol for real numbers is very non-standard
- Figure 1 is hard to navigate. I suggest just focusing on the topology and dropping the matchings.
- page 3 - summation itself is undifferentiable - this is more misleading than anything. The point of this section is that one can introduce soft edges instead of the hard edges.
- page 4 - consistency loss - This needs an example or a figure for an explanation.
- page 4 - with full linearization (Swoboda, 2007) - This work doesn't linearize anything as far as I know. It is a SOTA combinatorial QAP solver based on message passing and dual ascent.
- Eq 11, I don't see any reason to include this. it is just a trivial factorization with heavy notation.
- Page 7, Figure 3 has poor visual quality and a very tiny font.
review_title: Very good results on difficult benchmarks, write-up lacks clarity at times

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: Summary: The paper discusses the problem of graph matching (GM), which is the combinatorial (NP-hard) problem of finding a similarity between graphs, and has various applications in machine learning. More specifically, the paper proposes methods to leverage the power of deep networks to come up with an end-to-end framework that jointly learns a latent graph topology and perform GM, which they term as deep latent graph matching (DLGM).

Strengths: The proposed method seems justified. The authors both explore a novel direction for GM by actively learning latent topology.  They further propose both a deterministic optimization-based approach a generative way to learn effective graph topology for matching. Regarding the empirical results of the paper, the authors report that their methods achieve state-of-the-art performance on public benchmarks, in comparison against a few peer methods (in measures of both accuracy and F1-score). 
 Other than that, their claims appear to be correct, and so is the empirical methodology. Relation to prior work and differences are discussed.

Weaknesses/Comments: The paper was very difficult to follow (maybe it is due to the fact that I am not highly familiar with part of the field.  Nevertheless, I think that the organization of the paper can be improved).  I think there is a missing word in the second last sentence on page 2: For notational brevity, we assume d1 and d2 keep the same across convolutional
layers. Same dimensions maybe?
review_title: Novel method for graph matching using deep networks

final_score: rating: 6: Marginally above acceptance threshold
review_content: In this paper the authors propose a method for what they call Graph Matching, where the main contribution is to learn the connectivity matrix A, given the input features, and jointly learn the matching.

The paper is well written in general, and the contributions are clear. There are some "." and "," missing after equations.

This may be a matter of taste, but to me, graph matching (or the graph matching problem) refers to the problem of, given two graphs, finding the bijection between the set of vertices that minimices some distance. Usually, if A and B are the adjacency matrices of the two graphs, one tries to minimize $\|A-PBP^T\|_F$, over the set of permutation matrices.

Adding features to the vertices is a first extension of this problem, which I still consider a graph matching problem.
Now, if in the problem the inputs are a set of points in $\mathbb{R}^d$ and some features, and as part of the solution, one infers a possible adjacency matrix (or topology, as in the paper), then for me the term graph matching is misleading.

Unfortunately, I have no expertise in this latter problem, and therefore I just can say that the formulation seems correct, and the numerical results are promising.
review_title: Graph Matching, where the main contribution is to learn the connectivity matrix A, given the input features, and jointly learn the matching. To me, the use of "graph matching" is misleading 

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper deals with graph matching, where the latent topology of the two graphs is not fixed but estimated during the learning process.

The authors propose two algorithms, namely deterministic learning and generative learning, which both achieve state-of-the-art accuracy scores on several datasets.

I think that the approach developed in this paper can be of interest but its presentation makes it difficult to follow and understand.


First, it is implicit in the first part of the paper that it deals with topologies obtained from images.
The authors should explain what the graph topology models in the image and how it is obtained in the literature. They mention algorithm names (Delaunay triangulation and k-nearest neighbors, section 1), and that the construction is heuristic (page 3), but do not provide any clue on the (formal) definition of the topology. (I recall that the paper deals with estimation of the graph topology.)


In section 2, it is proposed to estimate both the topologies of the two graphs and their matching. In my opinion, the problem is not defined in a sufficient formal way so that the reader can exactly understand the rationale behind the methods.
I also think that, at this stage, the connection with how the topology is initially estimated in the literature would both help the reader to understand the optimization problem at stake, and highlight the originality of this piece of work.

I have the following (naive) question: isn't the optimal topology the one that does not allow any edges in the graph, since it should allow the greatest flexibility in the matching of the nodes? Of course, this solution is not of interest for the applications, but I do not see why it is excluded from the investigated approach.


The authors claim that optimizing eq. (13) is intractable and thus choose to maximize a lower bound through an EM-like algorithm. However, they do not prove the relation with the initial optimization problem. As is usually the case, does it allow for local optimization of (13)?


In the real data analysis, the methods are compared through their accuracy scores and not on the estimation of the latent topology. Of course, it is irrelevant at this place since the other algorithms do not estimate it. Nevertheless, it should be interesting to have a quantitative analysis of this output of the algorithm.


For all of these reasons, I think that this paper deserves to be significantly improved before being published.


More comments and questions:

+ The reader can not read and understand Figure 1 given on page 2 without reading the paper until page 7.

+ What is the normalized connectivity (page 3)?

+ The authors mention twice in the paper that there is only little work on "exploring graph topology learning / generation for deep graph matching" (introduction and conclusion) without any references explicitly related to this sentence. Are there papers that deal with the same strategy? I believe that the article should be clearer on that point. On this topic, I also think that the structure of the paper should be revised, with the section dedicated to related works (section 4) presented earlier.

+ The qualitative analysis presented in Appendix A.5 is very interesting and should be presented in the main document.


Typos:
Page 5: which in intractable

review_title: Approach of interest but very poor presentation

final_score: rating: 4: Ok but not good enough - rejection
review_content: In this paper, the authors argue that standalone representation learning is insufficient for the Graph Matching task and propose multiple novel approaches to address this via using a latent graph topology instead of a fixed one. Empirical results demonstrate the efficacy of their approach.

I was not completely convinced by the arguments made by the authors and their motivation. Overall the paper felt a little heuristic in nature and the presentation made it difficult to follow. Here are the major aspects which were unclear to me (refer below).

1) What is the primary motivation for the authors ? Why do the authors think using a latent graph topology is in general better than using a fixed topology ? Is it always true that using a fixed topology is undesirable or only in some cases only ? Some arguments/examples from the authors which can validate this using real-world settings would have helped. Irrespective of Graph Matching problem, Social Networks can be a good application for verifying this. Fake (due to noise) and real edges in connections/friendship network would be a good indicator for the authors' intuition i.e. the latent topology should be able to filter out the fake edges.

2) With regards to eqn. 1, is the condition Hz = 1 enough to ensure that each row and column sums to 1 ?

3) Why did the authors only consider absolute/boolean assignments (0/1) in the paper rather than partial assignments which can be more flexible i.e. soft assignments (0 <= z_i <= 1) such that each row and column sums to 1 ? Is there some specific reason for this ?

4) In section 2.4.1, the authors propose to use the straight-through operator for their rounding task. Did the authors try any other approaches ? How did the bias of the straight-through operator hamper their final optimization solution and by how much ?

5) With regards to eqn. 15 wherein the authors use an independence assumption, how much did the accuracy of their estimation suffer as a result to this quantitatively ?

6) The authors also mention that their deterministic learning approach is often more efficient while the generative learning method can be more accurate at the cost of additional overhead. Do the authors have results with regards to this overhead ? How significant is it and how does it compare to time complexity of the other state-of-the-art methods ? This is even more relevant given for many of the results, the improvement is only marginal compared to other competitors.

7) Based of the results, can the authors claim that improvement in the results over other competitors is due to the efficacy of their approach and the factuality of their arguments ? Could it be due to richness/complexity of their model/learning strategy ? 

8) What do the authors mean by "normalized connectivity" in section 2.1 ? Does it mean the augmented Adjacency matrix which contains self loops i.e. A_tilde = A + I ? 

9) Given the authors in their approach model the adjacency matrix, thus how does the authors' approach compare against traditional graph based modeling techniques i.e. Stochastic Block Model and Erdős–Rényi model for instance ? 

I would appreciate it if the authors made their code available for review/reproducing results. Additionally I felt the paper needed more analysis/discussion. Overall the presentation of the paper needs to improve significantly. 
review_title: Review

Meta-review: The paper proposes an interesting take on Graph Matching by posing the problem as learning the Topology through Graph Convolutional Networks.  There is consensus that the methods proposed are new but the impact is not clear.
One major point against the paper seems to be that Code is yet to be released.
Decision: Reject