| |
Reviews For Paper
| Paper ID |
1671 |
| Title |
Pairwise Matching through Max-Weight Bipartite Belief Propagation |
|
Masked Reviewer ID:
|
Assigned_Reviewer_1
|
|
Review:
|
|
| Question | |
| Paper Summary |
The paper proposes a block-coordinate descent algorithm for LP relaxation of the graph matching problem for feature matching. The proposed LP relaxation consists of the classical local polytope relaxation of the underlying pairwise graphical model plus the linear uniqueness constraints corresponding to the matching. By dualizing both the local polytope constraints and the uniqueness constraints one obtains two groups of dual variables - those called "messages" in MAP-inference (energy minimization) for graphical models and those corresponding to the uniqueness constraints ("matching-duals"). The overall block-coordinate optimization consists of alternating optimization w.r.t. the "messages" and "matching duals". Optimization w.r.t. "messages" itself is done in the coordinate descent fashion, in the MPLP-style algorithm. Optimization w.r.t. "matching duals" is done with hungarian matching algorithm.
The whole algorithm is used as a basis for a branch-and-bound scheme to obtain possibly good approximate or exact solutions.
|
| Paper Strengths. Please discuss the positive aspects of the paper. Be sure to comment on the paper's novelty, technical correctness, clarity and experimental evaluation. Notice that different papers may need different levels of evaluation: a theoretical paper may need no experiments, while a paper presenting a new approach to a known problem may require thorough comparisons to existing methods. Also, please make sure to justify your comments in great detail. For example, if you think the paper is novel, not only say so, but also explain in detail why you think this is the case. |
The proposed approach is theoretically sound and well-written. Though the paper is quite technical, it is easy to read and understand. The experimental evaluation is sufficiently reach to suggest that the method has a practical value and outperforms a number of state-of-the-art competitors at least on the considered datasets.
|
| Paper Weaknesses. Please discuss the negative aspects of the paper: lack of novelty or clarity, technical errors, insufficient experimental evaluation, etc. Justify your comments in great detail. If you think the paper is not novel, explain why and give a reference to prior work. Keep in mind that novelty can take a number of forms; a paper may be novel in terms of the method, the problem, the theory, analysis for an existing problem, or the empirical evaluation. If you think there is an error in the paper, explain in detail why it is an error. If you think the experimental evaluation is insufficient, remember that theoretical results/ideas are essential to CVPR and that a theoretical paper need not have experiments. It is *not* okay to reject a paper because it did not outperform other existing algorithms, especially if the theory is novel and interesting. It is not reasonable to ask for comparisons with unpublished, non peer reviewed papers (e.g. ArXiv) or papers published after the CVPR'16 deadline. |
1. Relation of the relaxation solver (the main proposed algorithm) and the branch-and-bound procedure must be described in more details: did you run the relaxation solver of each branching step to get the bound or you used the easily computable bound based on the already computed dual variables? In the second case, how the performance of the algorithm would change when one would use more iterations of the relaxation before the branch-and-bound stage? How tight is the proposed relaxation, in other words, how different is the solution delivered by the relaxation solver itself if it is run till convergence?
Please provide the plots which show how the evolving of the primal and dual values in time in comparison to the DD method, as the nearest competitor.
2. Convergence claim in line 511 is very sloppy: "By the fact that the dual objective is bounded from below by the true MAP value, Hungarian-
BP must converge." Only the weak convergence, of the dual value, is guaranteed by this fact. The dual variables themselves may not converge.
3. Minor corrections:
105: "in turn" -> "in its turn"
118: is f_ij^M a number? Please provide a strict mathematical definition (i.e. f_ij^M\in \mathcal{R}) - it simplifies reading for less involved readers.
eq. 3: remove double $\neq 0$
eq. 4: be more strict: l\in ??? i\in ??? in the second line.
|
| Preliminary Rating. This rating indicates to the area chair, to other reviewers, and to the authors, your current opinion on the paper. Please use 'Borderline' only if the author rebuttal and/or discussion might sway you in either direction. |
Strong Accept
|
| Preliminary Evaluation. Please explain to the AC, your fellow reviewers, and the authors your current opinion on the paper. This explanation may include how you weigh the importance of the various strengths and weaknesses you described above in Q1-Q3. Please summarize the key things you would like the authors to include in their rebuttals to facilitate your decision making. There is no need to summarize the paper. |
I find the paper both technically nice and practically important. The main thing, which bothers me is the relation of the proposed algorithm and the branch-and-bound procedure. Please clarify this issue, ideally with preliminary primal-dual convergence plots.
|
| New exciting ideas. CVPR’16 would like to draw attention to papers that explore highly innovative ideas, novel problems, and/or paradigm shifts in conventional theory and practice. Such papers may not be “complete” in the “traditional” manner in the sense that it may not be possible to have experimental results comparing other related efforts or that they may not have large, publicly available data sets to be used for performance comparison. However, we expect these papers to be visionary by nature. Should this paper be considered under “new exciting ideas”? |
No
|
| Reproducibility. Could the work be reproduced from the information in the paper? Are all important algorithmic or system details discussed adequately? |
The proposed algorithm is reproducible, to reproduce the used branch-and-bound procedure another paper must be checked. On the other side, the authors promise to publish their code.
|
| Confidence. Select: "Very Confident" to stress that you are absolutely sure about your conclusions (e.g., you are an expert who works in the paper's area), "Confident" to stress that you are mostly sure about your conclusions (e.g., you are not an expert but can distinguish good work from bad work in that area), and "Not Confident" to stress that that you feel some doubt about your conclusions. In the latter case, please provide details as confidential comments to PC/AC chairs (point 7.) |
Very Confident
|
|
Masked Reviewer ID:
|
Assigned_Reviewer_10
|
|
Review:
|
|
| Question | |
| Paper Summary |
The paper considers a formulation of pairwise feature matching as
discrete MAP inference (= energy minimization). The set of variables
is equal to the set of labels. The energy has usual unary and pairwise
terms (accounting for feature similarity), plus one (global)
constraint that enforces that each variable has a different label.
The main contribution is a novel LP relaxation of this energy
minimization. The relaxation for unary and pairwise terms is the usual
local polytope one. The uniqueness constraint is incorporated in a
clever way that allows for dual decomposition to the classical energy
minimization dual and maxweight bipartite matching (with only unary
similarities), which can be solved explicitly by the Hungarian
algorithm. The dual is maximized by (block-)coordinate ascent,
alternating between usual convex message passing updates and the
Hungarian algorithm.
|
| Paper Strengths. Please discuss the positive aspects of the paper. Be sure to comment on the paper's novelty, technical correctness, clarity and experimental evaluation. Notice that different papers may need different levels of evaluation: a theoretical paper may need no experiments, while a paper presenting a new approach to a known problem may require thorough comparisons to existing methods. Also, please make sure to justify your comments in great detail. For example, if you think the paper is novel, not only say so, but also explain in detail why you think this is the case. |
The idea is very elegant and natural. I like the paper.
The experiments are convincing.
|
| Paper Weaknesses. Please discuss the negative aspects of the paper: lack of novelty or clarity, technical errors, insufficient experimental evaluation, etc. Justify your comments in great detail. If you think the paper is not novel, explain why and give a reference to prior work. Keep in mind that novelty can take a number of forms; a paper may be novel in terms of the method, the problem, the theory, analysis for an existing problem, or the empirical evaluation. If you think there is an error in the paper, explain in detail why it is an error. If you think the experimental evaluation is insufficient, remember that theoretical results/ideas are essential to CVPR and that a theoretical paper need not have experiments. It is *not* okay to reject a paper because it did not outperform other existing algorithms, especially if the theory is novel and interesting. It is not reasonable to ask for comparisons with unpublished, non peer reviewed papers (e.g. ArXiv) or papers published after the CVPR'16 deadline. |
There is one technical inaccuracy: the paper does not prove that
Hungarian-BP converges (lines 512). In fact, algorithms like MPLP,
MSD, TRWS have never been proved to converge (in argument!). They are
specific forms of coordinate ascent on *nonsmooth* concave
function. First, monotonic improvement of the value does not imply
convergence in argument. Second, the dual value is not increased in
every update (some updates do not change it).
Though the presentation is clear, I have some objections regarding comparison with other works.
The LP formulation for pairwise energy minimization (i.e., without the
uniqueness constraint) is well-known today and it is well-known that
relaxation (4) is weaker than the local polytope one (6). Thus it is
somewhat dishonest to say (lines 191ff) "...we propose a new LP
relaxation for (1)...". The truth is that this is not any major
contribution of the paper, since it was only for historical reasons
why paper [28] considers the loose relaxation (4). The major idea of
the paper is elsewhere, namely the elegant dual decomposition.
The dual LP to the local polytope relaxation and coordinate ascent
(message) updates are also well-known today. There are several
existing formulations of the dual LP and message updates (MPLP, maxsum
diffusion, TRWS, ...). It would be helpful to discuss this in more
detail, saying which dual and which updates you are using. It would
then become clearer that some of the results that look original (such
as some theorems in section 3.3) are in fact known. You
mention works [25] and [12] but only in a nonspecific way - you do not cite any work in connection with the dual (8) (without added dual variables u,v) and
updates (14).
The approach is related to other works also as follows. Note that your problem is nothing else than energy minimization (MAP inference), though with a high-order term. But convex message passing has been formulated also for high-order (global) terms. E.g., this was done for maxsum diffusion in [Werner: Revisiting the Linear Programming Relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction, PAMI 2010]. Here (see section 6.3) message updates for high-order subproblems can take form of a algorithm. It was mentioned also in the dual decomposition formulation [Komodakis: MRF energy minimization and beyond via dual decomposition]. I wonder to what extent your decomposition can be understood in these terms.
|
| Preliminary Rating. This rating indicates to the area chair, to other reviewers, and to the authors, your current opinion on the paper. Please use 'Borderline' only if the author rebuttal and/or discussion might sway you in either direction. |
Weak Accept
|
| Preliminary Evaluation. Please explain to the AC, your fellow reviewers, and the authors your current opinion on the paper. This explanation may include how you weigh the importance of the various strengths and weaknesses you described above in Q1-Q3. Please summarize the key things you would like the authors to include in their rebuttals to facilitate your decision making. There is no need to summarize the paper. |
The new idea is crisp and useful. Experiments are exhaustive. There are weaknesses in presentation but they are only minor.
|
| New exciting ideas. CVPR’16 would like to draw attention to papers that explore highly innovative ideas, novel problems, and/or paradigm shifts in conventional theory and practice. Such papers may not be “complete” in the “traditional” manner in the sense that it may not be possible to have experimental results comparing other related efforts or that they may not have large, publicly available data sets to be used for performance comparison. However, we expect these papers to be visionary by nature. Should this paper be considered under “new exciting ideas”? |
No
|
| Reproducibility. Could the work be reproduced from the information in the paper? Are all important algorithmic or system details discussed adequately? |
Good. The code is promised to be made public after publishing.
|
| Confidence. Select: "Very Confident" to stress that you are absolutely sure about your conclusions (e.g., you are an expert who works in the paper's area), "Confident" to stress that you are mostly sure about your conclusions (e.g., you are not an expert but can distinguish good work from bad work in that area), and "Not Confident" to stress that that you feel some doubt about your conclusions. In the latter case, please provide details as confidential comments to PC/AC chairs (point 7.) |
Very Confident
|
|
Masked Reviewer ID:
|
Assigned_Reviewer_22
|
|
Review:
|
|
| Question | |
| Paper Summary |
The paper proposes a new and concise formulation of feature matching problems with unary and pairwise features. The task is formulated as a graphical model along with an additional global constraint, which ensures one-to-one matchings. The authors consider the standard LP relaxation of this task and show that the dual task can be solved by an interesting tailored version of block coordinate descent.
The authors show experimentally that the proposed method is superior to previous approaches as for instance spectral matching and graphical model approaches with weaker relaxations.
|
| Paper Strengths. Please discuss the positive aspects of the paper. Be sure to comment on the paper's novelty, technical correctness, clarity and experimental evaluation. Notice that different papers may need different levels of evaluation: a theoretical paper may need no experiments, while a paper presenting a new approach to a known problem may require thorough comparisons to existing methods. Also, please make sure to justify your comments in great detail. For example, if you think the paper is novel, not only say so, but also explain in detail why you think this is the case. |
The task formulation is concise, convincing and novel. Interestingly, the dual task of its LP relaxation admits an interesting tailored variant of block-wise coordinate descent. The optimisation sub-step w.r.t. to the dual variables which enforce the labelling to represent a permutation matrix, can be solved e.g. by Hungarian algorithm because it is equivalent to a weighted bipartite graph matching problem. The optimisation subtask w.r.t. to the re-parametrisation variables (a.k.a messages) is solved in standard way by belief propagation.
The presented experiments are sufficient and convincing. The paper is technically correct.
N.B. However, I have not checked all details of the proofs of propositions in sec. 3.3, which are delegated to supplementary material (Mainly because these are well known facts for the case of standard graphical models without global constraints).
|
| Paper Weaknesses. Please discuss the negative aspects of the paper: lack of novelty or clarity, technical errors, insufficient experimental evaluation, etc. Justify your comments in great detail. If you think the paper is not novel, explain why and give a reference to prior work. Keep in mind that novelty can take a number of forms; a paper may be novel in terms of the method, the problem, the theory, analysis for an existing problem, or the empirical evaluation. If you think there is an error in the paper, explain in detail why it is an error. If you think the experimental evaluation is insufficient, remember that theoretical results/ideas are essential to CVPR and that a theoretical paper need not have experiments. It is *not* okay to reject a paper because it did not outperform other existing algorithms, especially if the theory is novel and interesting. It is not reasonable to ask for comparisons with unpublished, non peer reviewed papers (e.g. ArXiv) or papers published after the CVPR'16 deadline. |
The main weakness of the paper is my view that it is somewhat overloaded with non relevant or well known details. To give a few examples:
(1) The author emphasize and even prove that the standard relaxation to the local marginal polytope is tighter then the relaxation used in [28]. But this is a well known fact.
(2) In Proposition 1, the authors also prove that the standard relaxation is tight if the graph is acyclic (for their case with the additional global constraint). But this follows immediately from the well known fact that it is tight for graphical models without global constraints (if the graph is acyclic). Moreover, it remains unclear to me, why and where this fact is relevant for the paper.
(3) As already mentioned above, the statements of the propositions presented in sec. 3.3 are well known for the case of standard graphical models without global constraints. And, the optimisation subtask w.r.t. the re-parametrisation variables is nothing but such a task. Less emphasise would be in my opinion better and improve the readability of the text.
|
| Preliminary Rating. This rating indicates to the area chair, to other reviewers, and to the authors, your current opinion on the paper. Please use 'Borderline' only if the author rebuttal and/or discussion might sway you in either direction. |
Weak Accept
|
| Preliminary Evaluation. Please explain to the AC, your fellow reviewers, and the authors your current opinion on the paper. This explanation may include how you weigh the importance of the various strengths and weaknesses you described above in Q1-Q3. Please summarize the key things you would like the authors to include in their rebuttals to facilitate your decision making. There is no need to summarize the paper. |
The paper is in my view a relevant contribution and is technically correct. However, I think that text itself puts somewhat too much emphasis to known or non relevant details. The authors could improve its readability putting more focus on the new and relevant parts of their contribution.
|
| New exciting ideas. CVPR’16 would like to draw attention to papers that explore highly innovative ideas, novel problems, and/or paradigm shifts in conventional theory and practice. Such papers may not be “complete” in the “traditional” manner in the sense that it may not be possible to have experimental results comparing other related efforts or that they may not have large, publicly available data sets to be used for performance comparison. However, we expect these papers to be visionary by nature. Should this paper be considered under “new exciting ideas”? |
No
|
| Reproducibility. Could the work be reproduced from the information in the paper? Are all important algorithmic or system details discussed adequately? |
The work can be reproduced from the information in the paper.
|
| Confidence. Select: "Very Confident" to stress that you are absolutely sure about your conclusions (e.g., you are an expert who works in the paper's area), "Confident" to stress that you are mostly sure about your conclusions (e.g., you are not an expert but can distinguish good work from bad work in that area), and "Not Confident" to stress that that you feel some doubt about your conclusions. In the latter case, please provide details as confidential comments to PC/AC chairs (point 7.) |
Very Confident
|
| |