Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper has the following contributions about algos for max matching on graphs with recursive separators:

1 simplifying the recent LR algo to not require dual weights

2 showing how this algo can find maximum matchings asymptotically faster than the classic (HK) algo for disc graphs with low "density"

3 showing how this algo for del-disc graphs can compute the bottleneck dist between point sets, and the Levy-Prokhorov distance efficiently, in low dim and when the measures are sufficiently spread out

4 experiments that show the proposed algo is faster than HK for 2 uniform point clouds in [0,1]^2
main_review: The contributions are solid and of interest to the TCS and comp geo communities. The observation that Levy-Prokhorov distance reduces to max matching in special graphs, while simple, is interesting to the stats and ML communities. The paper is also clearly written. 

My main concern is that in order to have impact in the NeurIPS community, the authors should describe specific ML applications where this new algo could be useful. In particular, because this algo is designed for exact solutions in very low dimension (since needs recursive separators). Many ML applications of these distances are in high d, and also there are faster algos if approx solutions are satisfactory (which is the case if the optimization error is smaller than the error from modeling/sampling empirical measures/etc), eg a trivial O(n + poly(1/eps)) time alg for +-eps approx to W_inf and thus also bottleneck and Levy-Prokhorov by simply eps-gridding. Certainly high-precision algos in low dimension are very important - but a discussion should be added to clarify when exactly this might be used.

other comments:
- The algo does not seem parallelizable due to BFS/DFS. This is critical for ML scale. Is parallelization possible?
- The algo only seems to apply to Wasserstein distances W_p when p=infty. Correct? This should be clarified in the abstract. Especially because the Wasserstein distances of interest are typically W_1 and W_2.
- Consider stating Levy-Prokhorov reduction in its own lemma since its of general interest.
- Typos: L53 del->eps, L72 / -> *, L155: a->b, L181: V->E, L331 and Leighton, L406: of
limitations_and_societal_impact: ok
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work applies a recent approach to maximum cardinality matching due to to Lahn and Raghvendra to a special case relevant to the machine learning community. Namely, they analyze the performance of this approach on delta-disc graphs in the service of computing popular distance metrics. Comparisons are made to the classic Hopcroft-Karp approach with empirical validation.
main_review: Overall, the paper provides good insights, but could be stronger. I am more familiar with related work in maximum cardinality matching and computational geometry than the distances addressed here. However, the paper makes some nice connections and appears to be a valuable contribution. In terms of originality, this is mainly a novel application and analysis of existing techniques. 

The main weaknesses are the limited experiments and lack of clarity around contributions. Given that experiments form a significant part of the validation, I would like to see a bit more. Is there a good reason why these experiments should be sufficient? Or is there a reason for not including more experiments?

Regarding clarity and contributions, the paper understandably restates a lot of prior work, but it is sometimes unclear what is and isn’t novel to this work. For example, it isn’t clear from the presentation whether Theorem 1 is due to this paper or prior work without a very careful reading and knowledge of that prior work. After rereading various sections a few times, I think I have a correct understanding of what is new in the paper. However, I would appreciate if the authors could clarify for me which portions of the paper they believe are the key novel contributions. I also feel the paper needs to be revised for clarity around this issue.

There some important typos that should be corrected and all of the formal details should be carefully proofread:
Line 155: “free vertex a in B_F” should refer to “b” not “a”.
Line 174: “n” should be “\sqrt{n}”
limitations_and_societal_impact: [N/A]
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper gives a fast and practical algorithm for computing approximate max cardinality matching in unit disc planar graphs. It's based on a recently improved bound that utilizes the (2-level) partition tree in more redundant manners. The implemented algorithm was tested on moderate datasets of around 10^6 vertices, and a performance gain by a factor of 4 or so was demonstrated.
main_review: On one hand, the LR algorithm is solid progress on a well known theoretical problem that also has direct connections with geometric optimal transport theory. On the other hand, the empirical studies only compares with their own baseline, and on random data that may or may not be representative of important cases of optimal transport. I also feel that such studies should be done in conjunction with various regularizers used in OT algorithms, as the gradients from those methods are what truly makes OT routines powerful.

While the gains of this method are not outstanding, they are definitely noticeable. I also thank the authors for clarifying several aspects of their setup, as well as runtime overheads that I didn't pick out on the first read. On the more theoretical side, I do believe extensions of these ideas can be quite important for OT based algorithms. So I feel the ideas here have potential, and this paper should be of interest to many working on OT algorithms
limitations_and_societal_impact: The experiments feel lacking to me for several reasons:
* the runtime of ~ 1000s on 12 cores for 10^6 points is only an order of magnitude off from generating the entire graph of all pairs of 10^6 points (on a single core one can check about 10^9 such pairs in a second). So the gains over even a naive n^2 algorithm feels minimal.
* the factor 4 gain over the HK baseline feels marginal, and doesn't show a clear asymptotic improvement
review_title: null

Meta-review: The reviewers consider the submission to have valuable contributions, and the ideas may help OT-based algorithms. There were some concerns about the presentation including:
1) the impact on the ML community is not clear;
2) the experiments are deficient: it is not clear that random point sets are in any way representative (e.g., they have a smaller value k, which may not be the case for a typical pointset).
The authors are encouraged to update the paper in accordance to the reviews/post-rebuttal comments.
Decision: Accept (Poster)