Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new method of estimating MAP solutions from a collective graphical model. 
main_review: The proposed method is very solid. Solving the MAP problem in the discrete space does not need approximating the log joint function as in continuous approximations.

The performance of the proposed method outperforms the baseline. 

The writing is generally clear. 

The work also has a few limitations. 
1. The proposed method only applies to a small scope of problems. With the few characterizations (CGM, path-graph, and small counts), the proposed method can only show strength in a small number of problems. 

2. The experiment on the real data uses true counts as the ground-truth, but this may not be correct. With the model specification in the experiment, true counts may not be the MAP solution. 

Small issues: 
Is it really useful to differentiate the three algorithms L, M, and R given their similarity? If so, can the authors put more analysis of how differences arise from the three configurations? 

I am not sure the two propositions make the writing clear. They are only analyses of the problem in focus. The notations are from the previous text, so the propositions do not stand by themselves. 

A little more insight into C-MCFP can assist the understanding. I have a rough idea that one can get a good solution with (even greedy) descending steps. But can you indicate the complexity here? 


limitations_and_societal_impact: No potential negative societal impact is detected.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a non-approximate method for solving MAP inference problem in collective graphical model (CGM). The paper uses difference of convex algorithm (DCA) strategy as a solver for the optimization problem since the objective function can be expressed as a sum of convex and concave function. The solution is obtained via minimization of a surrogate function that upper bounds the objective function. The technical details appear to be correct and the simulation results show the superiority of the proposed algorithm over its competitors. Further, a real world application involving car trajectories is performed to validate the performance of the proposed methodology.
main_review: The contribution appears to be technically correct and is a valid addition to the graphical model literature. Although the DCA has been used in other contexts its application to solve the MAP inference in CGM is novel. The algorithm also not too much worse compared to its competitors in terms of scalability. The paper is overall well-written although at some places (especially in the section where minimum cost flow algorithm was described) a bit more clarity would have been ideal. I have a couple of minor comments for the author(s)

- How does the choice of the surrogate function in DCA affect the MAP inference?

-How does one choose the value of M in the c-MCFP algorithm?

-Is there any practical guideline when to use the successive shortest path (SSP) or the capacity scaling (CS)?


******* Change after rebuttal **********

I am satisfied with the response from the author(s). The rebuttal has answered most of the queries related to the technical details of the paper. It also has also clarified some of the questions regarding the experiments with some additional results. I am keeping my previous score "Good paper, accept" unchanged.
limitations_and_societal_impact: Nothing as such.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider the problem of MAP estimate of count data given noisy count data. For example $X_1(t), X_2(t), \ldots, X_M(t)$ describe the location of an agent at time $t$, $N_i(t)$ is the number of agents at location $i$ at time $t$, and $Y_i(t)$ is a noisy estimate of $N_i(t)$. The goal is to estimate $N$ given $Y$. The noise distribution is assumed to be log-convex.

The authors develop an approach based on the difference of convex algorithm, which is an extension of the convex-concave procedure. They show that this procedure can monotonically improve a solution by repeatedly solving the minimum convex flow problem, which is known to be efficiently solvable.

The authors demonstrate that their approach improves over non-linear belief propagation with a continuous approximation of the discrete time problem.
main_review: Pros:

The paper uses several interesting techniques to solve the problem of MAP estimate of count data on path graphs. I found the application of DCA and the use of min-cost convex flow to be interesting. They are able to work with the discrete problem, rather than previous work which needed to do a continuous relaxation.

The paper is mostly clear, however the notation is somewhat dense. This can be improved by adding names to the key variables. For example, instead of just $M$ the authors can write "the number of samples $M$", $\mathcal{Q}$ can be "the convex term $\mathcal{Q}$", $\bar{\mathcal{R}}$ can be "the proxy concave term $\bar{\mathcal{R}}$", etc. This will give the reader a reminder of what the variable represents.

Cons:

The algorithm presented is a heuristic without much analysis. It can be seen as somewhat incremental over [12], which also uses DCA.

The authors could compare to prior work on the bird migration benchmark, as used in [12]. Additionally, the experiments considered are all small scale and can be solved in less than a second. Can larger experiments be completed? This should be possible, at least for the synthetic experiments.

Questions:

Where would the noise on the count data come from in practice? To me, it seems more likely that there is noise on the positions $X_j(t)$. The authors should 
limitations_and_societal_impact: This work can be used for population tracking. However I am not too concerned about this paper increasing the negative aspects of this, as there are already methods that can solve the problem considered.
review_title: null

Meta-review: The authors present a new algorithm for MAP inference in chain-structured Collective Graphical Models that uses flow techniques to solve the problem in discrete space, as opposed to previous works which use continuous relaxations. Three reviewers found the techniques to be correct and represent an advance over prior methods, with sufficient evidence presented to show the advantages of working in discrete space. The scores were 6, 6, 7. One reviewer raised their score after the author response. The meta-reviewer recommends accept. 
Decision: Accept (Poster)