A Faster Maximum Cardinality Matching Algorithm with Applications in Machine Learning
Authors: Nathaniel Lahn
Sharath Raghvendra
Jiacheng Ye
Venue: NeurIPS 2021 Poster (2021)
Keywords: bipartite matching
Wasserstein distance
Levy-Prokhorov distance
bottleneck matching
unit disc graph matching

Abstract: Maximum cardinality bipartite matching is an important graph optimization problem with several applications. For instance, maximum cardinality matching in a $\delta$-disc graph can be used in the computation of the bottleneck matching as well as the $\infty$-Wasserstein and the Lévy-Prokhorov distances between probability distributions. For any point sets $A, B \subset \mathbb{R}^2$, the $\delta$-disc graph is a bipartite graph formed by connecting every pair of points $(a,b) \in A\times B$ by an edge if the Euclidean distance between them is at most $\delta$. Using the classical Hopcroft-Karp algorithm, a maximum-cardinality matching on any $\delta$-disc graph can be found in $\tilde{O}(n^{3/2})$ time.~\footnote{We use $\tilde{O}(\cdot)$ to suppress poly-logarithmic terms in the complexity.} In this paper, we present a simplification of a recent algorithm (Lahn and Raghvendra, JoCG 2021) for the maximum cardinality matching problem and describe how a maximum cardinality matching in a $\delta$-disc graph can be computed asymptotically faster than $O(n^{3/2})$ time for any moderately dense point set. As applications, we show that if $A$ and $B$ are point sets drawn uniformly at random from a unit square, an exact bottleneck matching can be computed in $\tilde{O}(n^{4/3})$ time. On the other hand, experiments suggest that the Hopcroft-Karp algorithm seems to take roughly $\Theta (n^{3/2})$ time for this case. This translates to substantial improvements in execution time for larger inputs.

A Faster Maximum Cardinality Matching Algorithm with Applications in Machine Learning
Nathaniel Lahn"
Sharath Raghvendra Department of Computer Science Virginia Tech Blacksburg, VA 24061
School of Computing and Information Sciences Radford University
Radford, VA 24142
sharathrävt.edu
mlahn@radford.eem
Jiacheng Ye
Department of Computer Science Virginia Tech Blacksburg, VA 24061 yj cjc05130vt.cm edu
Abstract
Maximum cardinality bipartite matching is important graph optimization prob- lem with several applications. For instance, maximum cardinality matching in a 8-disc graph can used in the computation of the bottleneck matching as well as the co- Wossessesstnnn and the dévy-Prokhorov distances between probability distribu- tions. For any point sets A, C R22, the 8-disc graph is a bipartite graph formed by connecting every pair of points (a, b) E A x B by an edge if the Euclidean most Using the classical Hopcroft- Karp algorithm,
distance between them matching on any 5-disc graph can found in (n3/)2
a maximum-cardinalle time. In this paper, we present a simplification of recent algorithm (Lahn and Raghvendra, JoCG 2021) for the maximum cardinality matching problem and describe how maximum cardinality matching in a 8-disc graph can be computed asymptotically faster than (/23/2) time for any moderately dense point set. As applications, we show that if and are point sets drawn uniformly at random from unit square, an exact bottleneck matching can be computed in ((n//3) time. On the other hand, experiments suggest that the Hoperoft-Kary algorithm seems to take roughly (123/2 time for this case. This translates to substantial improvements execution time for larger inputs.
Introduction
Computing a maximum cardinality matching fundamental graph optimization problem. With origins in economics and logistics, matchings have found numerous applications. Computing popular distances between distributions, such as the Wasserstein distance as well the Lévy-Prokhorov distance, can be reduced to bipartite matching problem. In this paper, we consider the 8-disc graph matching which is the following:
Given two sets and of n. two dimensional points and a parameter 8 >> 0, a 5-dise graph G3 is bipartite graph obtained by connecting any pair of vertices (a, b) A B with edge provided that the Fuclidean distance between a and is at most 8, i.e., ||a bll < 5. Let m be the number of edges
Authorr ordered by last name. All authors contributed equally this work. We use Ö(-) to suppress poly- lol--toga terms in the complexity.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

in the graph Gs. A matching M is a set of vertex-disjonn edges in G3. In the 8-disc graph matching problem, we wish to compute a maximum cardinality matching in Gg, i.e., a matching that has the largest number of edges.
Any algorithm for computing 5-disc graph matching can also be used to compute bottleneck matching as well as the dévy-Prokhorov distance, both of which are defined next. Let M S A x B be any perfect matching of A and B, which is a matching where every vertex of A is matched, i.e., [M] = n. The edge of M with the largest Euclidean length is its bottleneck edge. The bottleneck matching is perfect matching M whose bottleneck edge length minimized. The Euclidean length of the bottleneck edge of M is the bottleneck distance between A and B.
Distances between distributions: Next, consider the case where A and B define discrete distri- butions PA and PB and let every point a E A (resp. b E B) carry a probability of 1/n, i.e., Pa(a) = 1/n (resp. Pb(b) 1/n). The so-Wasserstein distance between PA and Ps, de- noted by Wx (PA, PB), is simply the bottleneck distance between the point sets A and B. The Lévy-Prokhorov distance between PA and PB is defined as follows: For ε 0 and any sub- set X C A (resp. Y C B), let X
{b E B =a E X such that aa bll S $} (resp. Y {a E A 36 E Y such that ||a -bl bll < &)). Note that X S B and y S A. We say
that the Lévy-Prokeee Lévy-Prokhorov [34] distance ा TP is equal to the smallest value of e for which the following property true:
XA S A,PAA( S Px( PxxX)) + and, AY C B, =P(())))) +
here (x = Enex Pa(a) |X//n and PB(Y) Eser PB(() |Y//n. We can, therefore,
write this condition as
AA C X [x and VY C [
(I)
Determining if the exact bottleneck distance (equivalently simply finding the maximum cardinality matching M in Gg. It is easy to see that M is perfect if and only if the bottleneck distance is at most 6. Similarly, by applying Hall's theorem, one can show that x (P A, PB) I if and only if the maximum cardinality matching M in Gg has size of at least (1 (1-E)n. Thus, the 8-disc graph matching directly relates to computing oc- Wasserstein distance as well as the Léoy-Prok distance between probability distributions.
PB)) is S can be done by
Computing 8-dise graph matching: One can use any of-the-shelf matching algorithm [8] 31
33 [3 to compute a maximum cardinality matching in a 8-disc graph. For instance, using the well-known Hopcroft-Ka Karp algorithm will lead to an execution time of (mm//) on any 8-dise graph. The HK-Algorithm executes in phases. Each phase takes ((m) time, and, in the worst-case, the algorithm converges to a maximum matching in (vv)) phases. The best-known exact algorithm for computing the exact bottleneck matching combines geometric data structures with the HK- -K-algorihh in order to reduce the execution time of each phase from (m) to Ö(n). As a result, they obtain an exact bottleneck matching in (m23/2) time.
Inspired by a series of algorithms for weighted matching in graphs with small separators Lahn and Raghvendra (28) presented a weighted approach to the maximum cardinality matching problem. This LR algorithm identifies set of "edge separators' incident on w "boundary vertices". These edges are assigned weight of 1 and all other edges receive weight of O. A property satisfied by these separator vertices is that after their removal, every connected component in the graph has no more than vertices. Then, they present an algorithm to compute perfect matching in (m + m/w + mrw/n log time. As an application of their result, they show how to compute the bottleneck distance of any point sets A and B within multiplicative factor of (1 =) in ((no/3poly(1/e) time. The LR algorithm assigns dual weights vertices and is similar in style to the Muhn-MMunkee 24 and Gabow- Tarjan [1] algorithms. The dual weights on vertices play a vital role in the proofs of correctness and efficiency of the LR algorithm.
In this paper, we make the following contributions:
We remove the need to maintain dual weights in the L.R algorithm, resulting in significantly simpler algorithm.

---

Using this algorithm, we show how to find maximum cardinality matching in unit-disc graph G3 in time (//4/ where k is the maximum number of points of AUB contained in any dise of radius 8. Note that our algorithm is asymptotically faster than the classical Hopcroft-Kan Karp based algorithm when k = o(v).
Using our algorithm for ő-disc graph matching, we show how to compute the exact bottleneck distance between point sets A and B. When PA and PB are discrete distributions with each point having probability 1/n, the bottleneck distance can be used to compute the distances oo (PA, PB)) and (P PB). We are not aware of any previous polynomial time algorithms to compute the Lévy-Prokhone at random from a unit square, our algorithm for the exact bottleneck distance runs in (n4/3) time. All previous algorithms take (n1"/2) time.
distance. When A, B are chosen uniformly
We run experiments for the case where A and B are chosen uniformly at random from a unit square. Our experiments suggest that the Hoperoft- Karp algorithm on Gs takes ((n2/3) time. In contrast, our algorithm runs substantially faster and executes in Ö(n 4/3) time.
Note that, for the HK-algorithm, the upper bound of O(vr) phases is only in the worst-case. As noted by Motwani (32), the Hopcroft-Kann Karp algorithm converges, with high probability, to a maximum matching in Olog phases for expander graphs in general and Erdōs-Rényí random graphs in particular. Similarly, does the HK algorithm execute asymptotically fewer than vii iterations when used to compute bottleneck matchings? Interestingly, our experiments suggest that the answer to this question may be in the negative. Based on our experimental results, when A and B are drawn uniformly at random from a unit square and when 5 is set to the bottleneck distance, the number of phases seem to grow at the rate of S2( (n). Therefore, bottleneck matching on random point sets may represent natural hard instance for the HK-Algorithm. In this paper, we show how to overcome the ((13/2) barrier for uniformly distributed point sets by developing an (n4/33) time algorithm.
For any & > 0 and any point set AUB, B, the LR algorithm can also be used to compute a multiplicative time. This done by using
(1 + -pappooxxmattoon of the bottleneck matching in 0 poly//1pplll//a grid where the side-length of each cell is a function of E. The algorithm rounds every point to the closest cell center and finds a ô-disc graph matching using the LR algorithm. See Section 6 of (28) for details. One can also similar approach to compute multiplicative (1 =) approximation of the Lévy-Prokhorov distance. Replacing the original LR algorithm with our dual-free implementation leads to simpler approximation algorithms.
Applications: Wasserstein distance has found numerous applications in machine learning and computer vision 3 5 & IO, 14 36). Due to these applications, computing approximations of
Wasserstein distances has received substantial attention 12. 9 12
26 30 355. However, exact
algorithms (even for discrete distributions) have a relatively high execution time 15
24 39 The
Lévy-Prokhoron distance have been extensively studied for its theoretical properties II instance,
For
distance metrizes weak convergence However, a brute-force algorithm based on the definition of this metric will require a search on exponentially many possible subsets causing it to seldom be used in practice [16]. However, Hall's theorem to show that the computation of the Lévy- Sry--Prokhorov metric reduces to the 5-disc
any separable metric space [19].
use
graph matching problem and so, it is only as hard as computing the co- Wasserstein distance, at least for discrete distributions of the type PA and Pp described above.
In this paper, we provide exact algorithms for computing the co- Do-Wasserstein and the Lévy-Prokhorov distances for 2-dimensional discrete distributions. Our algorithms can be useful several scenarios. For instance, one can estimate Lévy-Prokhore distances between any two fixed-dimensional continu- ous distributions by simply computing the distances between samples drawn from these distributions. From the fact that the Proohoroooo distance metrizes weak convergence, for large enough samples we can get accurate distance estimates. Faster high-precision algorithms are critical in obtaining such estimates; see 6). For high dimensional discrete distributions, Wasserstein distance is sometimes estimated by embedding them into a lower dimensional space and computing high precision solution in this space. For example, see the sliced Wasserstein distance 22]
In the emerging area of topological data analysis, high dimensional point clouds are characterized by two-dimensional point sets called persistence diagrams where each point represents the so-called birth
and death times of a topological feature. Different high-dimensional point clouds can be compared by computing the bottleneck distance between the corresponding diagrams [1 22 [. This has
3

---

led to development of practical implementations of bottleneck matching algorithms [7 22 More recently, other Wasserstein distances between persistence diagrams have also been considered. See
for instance
25 40
The special case of computing bottleneck matching for point sets A and B that are drawn uniformly random from a unit square has also received considerable attention. For instance, it has been used in
the context of testing pseudo-random generators, average case analysis of bin packing algorithms [29]
and also in statistics for analyzing the Glivenko-Cantelli convergence of empirical measures [37]
5-disc graphs have other applications as well, including in the modeling of the topology of ad-hoc wireless networks (20).
2 Matching algorithms
In this section, we present and compare two algorithms for solving the maximum cardinality matching problem on an arbitrary graph: The Hopcroft- Karp (HK) algorithm [8. and the LR algorithm [28]. In section 2.1 we introduce the basic definitions used by most combinatorial matching algorithms and give an overview of the HK algorithm. In section 2.2
we present the LR algorithm, highlighting
the differences it has from the HK algorithm.
2.1 Preliminaries
Given any matching M, let AF and BF denote the vertices of A and respectively that are not matched in M. We refer to these vertices as free vertices. An alternating path P is a path that alternates between edges that are in the matching and those that are not in the matching. An augmenting path is an alternating path that starts and ends at a free vertex. We define the length of P as the number of edges in P.
We can augment a matching M along an augmenting path P by updating the matching to M < M @ P; where @ denotes the symmetric difference operator. It is easy to see that augmenting matching along an augmenting path P increases the size of the matching M by 1. Furthermore, it can be shown that G has no augmenting paths with respect to a matching M if and only if M has maximum cardinality. These observations are the basis of the following commonly-used approach for computing a maximum-cardinality matching: repeatedly compute an augmenting path / with respect to M and augment M along P until M has maximum cardinality. Since the largest possible matching has size at most n, any such algorithm will arrive a maximum-cardinality matching after augmentations. This is the approach used by the classical Ford Bord-Fulkerson and HK algorithms as well as the recent LR algorithm. However, the algorithms differ in the details of how these augmenting paths are found.
Given a matching M, the residual graph GM is a directed graph that assists in finding augmenting paths. The graph Gm contains the same set of vertices V as G. For any edge (a, 6) in G. if (a, b) E MM then we add an edge directed from edge directed from b to a to GM. Furthermore, we create a source vertex and a sink vertex t with the following additional edges. For each free vertex b E Br, we add an edge (s, b) directed from the source s to in GM and for each free vertex E Ap we add an edge from a to the sink t in GM- Note that, for the residual graph, we use (u, v) denote an edge directed from u to v. On the other hand, for the undirected graph G. we may use (u, v) and (v, u) interchangeably to represent the same edge between vertices u and v. Consider any directed path from 8 to the residual graph. Note that removing s and from P will result in an augmenting path. In the Ford-Fulkerson algorithm, single augmenting path can be found in (m) time using any common graph search algorithm such as breadth-firs search (BFS) depth-firs first search (DFS), leading to (mm) time algorithm. The HK and LR algorithms both improve upon this running time by finding potentially many augmenting paths in each iteration.
Residual graph:
to Gm. Otherwise, we add an
Initially, let M 0. The HK algorithm executes in phases. A phase is divided up into two stages. The first stage executes a BFS starting from s and identifies the length of the shortest path (path with the fewest edges) in GM from s to every other vertex in GM. Let b,, be the length of the shortest path from to and let e = l,. The algorithm then computes an admissible graph A consisting of all edges (u, v) in Gar such that (a) f,, and l, are at most & and (b) ly = E, 1. Note that these edges capture the set of all minimum-length augmenting paths in GMr. The second
HK algorithm:

---

stage iteratively conducts multiple partial DFSs that start from and terminate early if a path to t found. Following the termination of Sartial-DFS, all edges visited by it are removed from the residual graph. The algorithm proceeds to the next phase if a partial-DFS terminates without finding a path from to f. It can be shown that, in each phase, the HK algorithm finds a maximal set of vertex-disjoing shortest augmenting paths in GM- Each phase involves execution of single BFS and multiple partial DFSs. Since no two executions of DFS visit the same edge, the combined execution time of the multiple partial DFSs is bounded by ((m).
Hopcroft and Karp showed that the length of the shortest augmenting path increases by at least 1 after each phase. Therefore, after vn phases, the shortest augmenting path has length at least vn. Using this, they showed that there are no more than /n free vertices remaining, all of which can be matched by augmenting along an additional Olyn) augmenting paths. Thus, the total number of phases executed by the algorithm is (V))). Since each phase takes O(m) time, the total time taken by the algorithm is (n) Somewhat surprisingly, Hopcroft and Karp [18] also showed that the total length of all n augmenting paths, across all phases, only (n logn).
2.2 A simplified implementation of the LR algorithm
Recently, Lahn and Raghvendra presented an algorithm 28 to compute maximum cardinality matching. Their algorithm resembles the Kuhn-Munkres algorithm for weighted matching. this section, we present cleaner implementation of the LR algorithm. These simplifications result in closer resemblance to the HK algorithm. Unlike the LR algorithm, our algorithm does not maintain any dual weights. In the following, we describe and contrast our algorithm with the HK-algorithnn
Apart from a bipartite graph GVV, E), we are also given subset Ess S E of "separator edges" as input. For any separator edge (u, v) E Es, we denote the vertices u and v: as boundary vertices. Let B be the set of all boundary vertices. The analysis of the algorithm depends on w = [B] and another parameter that is defined next. Consider the graph GV, E Es). Let IP- = {PI,... ........ P.) be the set of connected components of G' and let V; and & be the set of vertices and edges of P, for all 1 < i S l. We refer to each P; in G' as a piece of the original graph G. Let = maxp,ep [V.). i.e., the size of the piece of G with the largest number of vertices.
Setting weights on the edges of the graph G and its residual graph Gyy: For any edge v)) E E, we assign a weight wo(u v). For any separator edge (u, v) E Es. we set wru, u) to For any other edge (u', e') E E \ Es. we set w(u', u') d') to O. Every edge (u, v) in the residual graph inherits the weight of the corresponding edge (u, v) in G(V, E). All edges incident on the source s and the sink in GA receive weight of O. For any path P. its weight is simply the sum of the weights of its edges.
Preprocessing: In the preprocessing step, our algorithm finds a maximum cardinality matching for each piece by applying the HK- HK-Algorithm. Let M be the union of these matchings computed across all pieces. At the end of this step, the difference M |M| is (w)), where M is the maximum cardinality matching in G. So, our algorithm has to find an additional (w) augmenting paths in order to compute a maximum cardinality matching.
The remaining (w) unmatched vertices are subsequently matched in phases. Like the HK algorithm, each phase of our algorithm consists of two stages. These stages somewhat resemble the stages of the HK algorithm. We highlight the differences in the description below.
Stage 1: In the first stage, our algorithm finds, for any vertex V, the minimum weight path from 8 to e in the residual graph GM using the weights .....). Note that, since every edge weight either 0 or 1, standard BFS implementation can be modified to support such a minimum-weight search algorithm in 0m) time by simply prioritizing edges of weight over edges of weight 1. We call this modified version of BFS. 0/1 BFS. For any vertex u E V. let by be the weight from s to in GM as computed by the 0/1 BFS and let é = l, Any edge (u, v) of G is admissible if lu,, ey < é and l f. + w(u, v). The admissible graph A is identical to GM. except it contains only admissible edges. Similar to the HK algorithm, it can be shown that the admissible graph A captures every minimum weight augmenting path.
The second stage of our algorithm finds a set of shortest augmenting paths (by weight). It does so by iteratively conducting Dartial-DFSs from until no augmenting path is found. Each partial-DFS immediately terminates if an augmenting path P is found. Let be the set of affected pieces, which are pieces that contain at least one edge of P. Unlike in the HK- HK-Algorithm, the
Stage 2:
5

---

matching M is immediately augmented along P and every edge visited by this partial-DFS that does not belong to an affected piece deleted. Note that any edge from an affected piece that was visited by this partial-DFS does not get deleted and could be revisited by a later partial-DFS. In other words, edges in an affected piece can be visited multiple times within the same phase.
Differences with HK algorithm: The main differences between our algorithm and the HK algorithm are:
(I) Our algorithm assigns weights of 0 and to the edges. No weights are assigned in the HK algorithm.
(2) Our algorithm has a preprocessing step that computes a maximum cardinality matching within each piece.
(3) In Stage 1, our algorithm executes a 0/1-BFS instead of the BFS executed by HK algorithm.
(4) In Stage of our algorithm, the partial-DFS reuses edges from affected pieces. As a result, in each phase, our algorithm may find augmenting paths that are not vertex-disjoint.
Differences (3) between HK algorithm and our algorithm do not impact the execution time of the algorithm by any more than a small constant factor. See Section F of the supplement for discussion on this. The critical difference between the two algorithms is (4). Unlike the HK algorithm, Stage 2 of our algorithm reuses edges from affected pieces and computes a set of augmenting paths that are not necessarily vertex-disjoint. This allows for computing many more augmenting paths within each phase.
As we show later, the total number of phases executed as well as the augmenting paths computed by our algorithm identical to those computed by the LR algorithm. Therefore, the analysis of Lahn and Raghvendra can be directly applied to our algorithm. They show that after each phase, the weight of the shortest augmenting path increases by least one. After v/ phases, they show that there are O(Vw) free vertices which can be matched using an additional O(Vw) phases. Thus the total number of phases can be bounded by (V))).
Edge revisits cause the execution time of a phase to increase. Note that an edge can be revisited only if it was inside affected piece when it was most recently visited. Lahn and Raghvendra show that the total number of affected pieces is ( logw) (a piece that is affected l times is counted & times in this sum). For graphs that admit recursive separators (such planar and graphs with excluded minors), they show that the number of edges for any piece can be bounded by O(mr/n) leading to an O mew log bound on the total number of revisits.
n
Theorem 1. Consider a graph G and set of separator edges. Suppose each piece has at most r Omm//n /n) edges. Our algorithm computes a maximum cardinality matching in O(m + myw- new log n) time.
For our algorithm, the assumption on upper bound on the number of edges within each piece can be eliminated when graphs, such as those considered in this paper, support a dynamic data structure D of the following form: D can store any subset A' C A of vertices and, given any query vertex b E B, it can return a vertex a E A' that minimizes the weight of the edge (b, a). Note that the weight of (b, a) will be 1 only if every edge from b to any vertex a' E A' has weight of 1. If no edge exists between and any vertex of A', then the data structure returns NULL. Suppose that D supports arbitrary insertions and deletions from A', as well as queries, each in ((n) time. Then, one can this data structure to dynamically maintain the set of unvisited nodes of A during a 0/1 BFS or DFS. Consequently, one can execute 0/1 BFS and DFS in time (nn)(n)). As result, the execution time of our algorithm can be improved to O (n) /F + n Vir + (w) log n). In contrast, using 'D to execute Hungarian Search inside the LR algorithm seems challenging.
Theorem 2. Given a graph G that supports dynamic nearest neighbor data structure with query and update time of (n),, a maximum cardinality matching can be computed by our algorithm in ((((n) (n + ny/w + rw l)). The HK algorithm computes maximum cardinality matching in (113/2((11) time.
Equivalency to original LR algorithm: The original algorithm maintains a dual weight y(v) for every vertex v E A U B at any point during the algorithm. For any edge (a, b) E (A x B) O E, the dual weights satisfy the following:

---

v(b) y(a) S wr b) y(a) vb) wla,b, b)
if (a, & M, if (a, E M.
Additionally, their algorithm maintains the invariants that all free vertices of BF have the same dual weight of Vmax = ma v(v) and all free vertices of A have the same dual weight of The slack s(a, b) of any edge (a. b) E (A x B) E is defined as follows: if (a, b) & M, then s(a,b) b) = w(a, b) y(b) + y(a); otherwise, b) E M and s(a, b) = O.
In the original LR algorithm, the first stage adjusts the dual weights so that there is least one zero-slack augmenting path in GM. The second stage takes the subgraph consisting of zero slack edges and repeatedly executes DFS from This DFS stops early if a path to I, i.e., an augmenting path, is found. After augmenting along path, all edges visited by the DFS are deleted, unless they were in an affected piece.
Note that the only fundamental difference between the original version of the LR algorithm and simplified version is the fact that we compute minimum-weigh augmenting paths while they compute zero-slack augmenting paths. The following lemma, whose proof appears in Section of the supplement, shows that the a zero slack path computed in the LR algorithm is also minimum weight path. It follows that the two versions of the algorithm are equivalent.
Lemma 1. During Stage of the LR algorithm, an augmenting path has zero slack if and only if it has minimum weight.
3 Applications
In this section, we show how our algorithm can be applied to efficiently compute a maximum cardinality matching on ô-disc graph, an optimal bottleneck matching, as well as the dévy-Prokhorov distance between distributions. All applications considered are for point sets A, B C IR2. For all applications, one can build data structure 'D from Theorem 2 with ((n) log ((1) n. by using
dynamic Fuclidean nearest neighbor data structure; see Section H.3 of the supplement for details
3.1 8-disc graph matching
Let P AU B. Let B(p) be a ball centered at with radius d. Consider k - maxpex? IB(p) n Pl i.e., k is the largest number of points of A U B inside any ball of radius d. We refer k as the 5-density of the point set P. We show that maximum cardinality matching in a 8-disc graph can be computed using our algorithm in (/44/3113) time. Thus, when the 8-density k = o( v)), our algorithm outperforms the HK algorithm.
Theorem 3. For any point set P AUU B and parameter 8 > 0, maximum cardinality matching in the d-disc graph defined on P can be computed in O(n4/3/1/3) time, where k is the 8-density of P.
This result also extends to the case where the points of A and B are independently and identically distributed random variables drawn from distributions PA and Pg respectively. We say that distribution P has 6-density of k if, for any ball Bpp) of radius 8, the probability that point drawn from P lies inside the ball is at most k/n.
Theorem 4. Let A, B be drawn iid from distributions PA and Pg respectively. For a parameter 5 > 0, maximum cardinality matching in the 8-dise graph defined on A B can be computed, with high probability, in O(n4/3g1/3) time, where k is the maximum of the 8-density PA and Pg.
Proof of Theorem 3 We show how set of separator edges can be generated so that w 0(2/3322/3) and O/n 1/3). From Theorem 2 and since nyF O(n//3/k //1/) n/w 0/44/3 and, rw O(n 4/333/3 the execution time of the LR algorithm can be bounded by 0144/311/3) Next, we describe how generate the separator edges Es-
We use a grid & to generate the separator edges. Any grid consists of a set of equispaced horizontal and vertical lines that partition 2 into cells. Each cell is square and any grid can be seen
7

---

set of these squares. Let (G) denote the side-length of any cell C' E G. We say that cell C' is non-empty if C + 0. Let 0- = /2/////22/// To generate our pieces, we choose grid G where the side-length of each cell set to L(G) 05. The separator edge set Es consists of all edges of the 8-disc graph that have their endpoints in different cells. All such edges are assigned weight of 1. Any edges whose endpoints are contained within the same cell of G are in E Eg and are assigned weight of O. Any point that has at least one separator edge incident on it becomes boundary vertex. To generate G, we check (()) possible vertical and horizontal shifts and pick the one that minimizes the number of boundary vertices. We provide the details of generating G in Section [f the supplement. Our choice of G guarantees that w O(n2/3/2/3 for any point set, independent of its d-density. We show this in Section B.2 of the supplement.
Bounding r: By this definition, the number of vertices of any piece is bounded by the maximum number of points that can lie inside any cell of C, i.e., max |C n Pl. Note that we can cover any cell of & with @(0²) balls of radius 0 each. Due to the d-density of P being k, each of these balls can contain at most k points and the total number of points inside any cell can be bounded by O(f%k) (n2/3 /1) as desired. In other words, O /k1/3).
The construction of the grid here will be identical to the one in the proof of Theorem B] Note also that the bound on w provided in that proof depends only on the construction of G and not on the 5-density of the point set. Therefore, the same bound continues to hold here as well. In Section of the supplement, we use the 5-density of PA and PB along with Chernoff's bound to prove that r (n2/33 /k2/3) points with high probability.
Proof of Theorem 4;
3.2 Bottleneck distance
In this section, we assume that A and B are points drawn uniformly at random from a unit square. From the work of Leighton and Shor 22), we know that, for appropriate constants Gmin and Cmax
the optimal bottleneck distance is at least 8min Smin log"/"((1 (n)) and at most δmax =
-max log 3/4 (x) /
vn
with very high probability (probability exceeding 1 - 1/n2 for some a (-ylogg)) Observe that the optimal bottleneck distance will be equal the length of some edge of A x B. As in the work of Efrat el al. [13), our algorithm will use a selection algorithm of Katz and Sharir [2] to find the jth smallest edge, 1 I j S n² in On 4/3 log" n.) time. Let d(j) be the length of the jth smallest edge returned by their algorithm. This allows us execute binary search over the edges of A x B, ordered by their length. Let Imin = 1 and Jmax = n²² We repeat the following process until Imax = -minn + 1: We choose j = L(gmax + 9min) /2] and find the jth smallest edge whose length is denoted by d(.). If d(()) 2 ōmax. we set Imax + j. If d(j) S 8min: we set Jmin + j. Otherwise, 8min S d(s) S maxx. and we find the maximum cardinality matching in a ô-disc graph where is set to d(j).. If we obtain perfect matching, we set Imax = j. Otherwise, the maximum matching is not perfect, and we set 9win = j. When the algorithm terminates. d(gmax) is the optimal bottleneck distance.
Analysis: The algorithm makes O(log n) many guesses. These guesses found by selection algorithm that runs in (nn log" n) time. For each guess j where 8min S d(j)) < 8max, we must d-disc graph, which takes O( time using
compute maximum-cardinalii matching the LR algorithm. Since, PAA) and PBB) are the uniform distribution, their d-density increases as increases. Therefore, the -ensityy of ((A) and P(B) will be upperbound on the d-density for any execution of the LR algorithm. The probability that any random point lies within any ball of radius ò is at most (26 which is O(log 3/2 (n)/n). Therefore, the 6 6 density of P(A) and (BB) is at most k- (llg2)/2(n)) Applying Theorem 4 gives the following:
Theorem S. Let A, B be drawn uniformly at random from unit square. An optimal bottleneck matching can be computed between A and B, with high probability, in Ó(1/13) time.
Practical considerations: The algorithm described uses two black-boxes that are impractical and have hidden high constants in the Big-O notation. (a) the algorithm relies on a dynamic nearest neighbor data structure, and, (b) the algorithm uses the selection algorithm of Katz and Sharir (21]. In Scction of the supplement, we address both (a) and (b) by presenting more practical alternatives.
8

---

3.3 Lévy-Prokhoroy distance
In this section, we show that we can use our algorithm for the 8-disc graph matching also compute the Lévy-Prokhoree distance.
We describe simple algorithm decide if (P PB) greater than at most E. We compute maximum cardinality matching M in an E-dise graph. Let Ap and Br be the free vertices with respect to M. Then, say that the distance is greater than if [A en. Otherwise, we say that the distance is at most e. Using a binary search similar to the one described in Section 3.2 we can determine the distance in Ön 4/3 (1//) time.
Proof via Hall's theorem: Given any bipartite graph G(A U B, E), for any set X C A, the neighborhood M(X) is the set of all vertices of that share an edge with at least one vertex of X. Thus, X is the neighborhood of X in an e-disc graph. The deficiency of graph with respect to A is ((A) = maxx CA X (x)). Hall's theorem says that a bipartite graph has a perfect matching if and only if the deficiency of the graph with respect to A is non-positive. Hall's theorem can be generalized to the following.
Lemma 2. For any bipartite graph G(AU B, E), where |A] = [B| n, and for any integer the deficiency with respect to A or B is k if and only if the maximum cardinality matching is of size
The proof of this generalization follows in a straightfforward way from the Hall's theorem. For the sake of completion, we provide this proof in Section E of the supplement. Next, we show that the algorithm described here correctly computes the Lévy-Prokhore distance.
Recollect that, algorithm returns the distance to be greater than if [Apl > we conclude that the deficiency of the graph is greater than En, i.e., there a set X S A such that Thus, Equation I does not hold and the distance is greater than
By Lemma 2
[X| [
Our algorithm returns a distance at most if | S en. In this case, from Lemma of the graph with respect to A is less than en, i.e., for every subset X C A, |X| X en. Note that |AF| = BBl S En and so an identical argument applies for as well. Thus, Equation holdd and the distance is at most E. We conclude that the algorithm terminates with the correct E.
2 the deficiency
Theorem 6. Let the point sets A and B, |A| B = n. describe two distributions PA and PB where each point has probability 1/n associated with it. The Lévy- Prokhorro distance (P PB)) can be computed in O(n2/3g1/3 time where is the ö-density of A U B.
4 Experimental results
In this section, we compare the performance of the HK and LR algorithms when applied to computing an exact bottleneck matching between equal-sized point sets A, B IR2 drawn uniformly at random from a unit square, where n |A| + B).
Experimental setup: For each value of n in {100, 1000, 5000, 10000, 50000, 100000, 500000, 1000000, 1500000), we execute 10 runs. For each run, we uniformly sample points from a unit square obtain the point sets A and B. Next, we compute bottleneck matching between A and B separately, using both the HK algorithm and our algorithm, and record performance metrics for both algorithms. We execute our experiments on server running CentOS Linux 7, with 12 Intel E5-2683v4 cores and 128GB of RAM
When guessing the bottleneck distance for each run, instead of enforcing that the number of guesses is Oloog n) it is sufficient in practice to continue the binary search on 8 until the relative error becomes less than sufficiently small value (see Section of the supplement). Both the HK-based algorithm and the LR-based algorithm use the same strategy for guessing the bottleneck distance in the experiments.
Experimental results: For each figure, the data presented for each value of n is averaged over all 10 runs. Error bars represent single standard deviation. Figure [ presents the actual running time of both algorithms, summed over all guesses of the bottleneck distance. For datasets with more than 10 points, our algorithm takes roughly half as much time as the HK algorithm and the gap seems
Our implementations of our algorithm and HK be found at http:///gttihb..om//maaaaaaal/lt

---

Rumning time (wecondhg)
7300
aciipen wato cred
5300
1332
2300
145
146
Figure I: A running time comparison between the HK algorithm and our algorithm. Left: Comparison of actual running time. Right: Comparison of total number edge visits.
sartml phoses
4.0-
115st gutsst
Phares
08 3.0 ppontss
13
1.4
166
points
Figure 2: Data for number of phases for the final bottleneck guess. Left: comparison of the number of phases for the HK algorithm and our algorithm. Right: vn divided by the number of phases executed by the HK algorithm.
to grow as the input size increases. However, the actual running times can be affected by several factors including the exact implementation details and execution environment. Therefore, focus on comparing metrics that are accurate independent of the exact implementation details. Recall that both algorithms combine variants of BFS and DFS compute augmenting paths. As result, the total number times edges are visited during each algorithm acts as an implementation-indeeeeer proxy of the running time. Figure shows the total number of edge visits for both algorithms. Note that this data seems to follow similar trend to the actual running times of the algorithms.
Next, summarize our observations that help account for this difference in performance of the two algorithms. For more details, see Section of the supplement. Recall that there are four main differences (1) (4) between the HK algorithm and our algorithm. As discussed in Section F of the supplement, differences (1) - (3) do not have any direct significant impact on the relative running times of the algorithms; the most significant difference is (4) Stage 2 of the algorithm reuses edges from affected pieces. This reuse of edges has two main effects on the efficiency of the algorithm. First, find that algorithm. Specifically, as the guess of the bottleneck distance approaches the actual bottleneck distance, our results suggest that the number of phases executed by the HK algorithm seems to grow at rate of @(v exhibiting its worst-case analysis. In contrast, the number of phases executed by our algorithm grows much slower rate (see Figure 2 This explains why the our algorithm runs faster than the HK algorithm. The second impact of allowing for edge revisits is that a single edge can be revisited, perhaps many times, during single phase. Despite this, the total number of edges visited by our algorithm is still significantly less than the total number of edges visited by the HK algorithm (see Figure Tb.
algorithm executes significantly fewer phases than the HK
5 Conclusion
We consider the maximum cardinality matching problem and present simplification of recent algorithm by Lahn and Raghvendra (28). In particular, we eliminate the need to maintain dual weights in their algorithm. This not only leads to a simpler algorithm but also results in new and improved exact algorithms for computing the d-dise graph matching, bottleneck matching, as well as the co- Wasserstein and the Lévy-Prokhorov distances, in low-density settings. We would like to conclude by stating the following open question: Can we design a parallel combinatorial algorithm to compute d-disc graph matching?
10

---

Acknowledgements We would like to acknowledge, Advanced Research Computing (ARC) at Virginia Tech, which provided us with the computational resources used run the experiments. Research presented in this paper was funded by NSF CCF-1909171, We would like to thank the anonymous reviewers for their useful feedback.
References
[1] A. Adcock, D. Rubin, and Carlsson, Classification of hepatic lesions using the matching metric, Computer vision and image understanding, 121 (2014), 36-42.
[2] Altschuler, J. Weed, and P. Rigollet, Near-linear time approximation algorithms for optimal transport via sinkhorn iteration, Neural Information Processing Systems, 2017, pp. 1961-1971.
[3] M. Arjovsky, S. Chintala, and L. Bottou, Wasserstein GAN, arXiv: [stat.ML), (2017).
[4] M. K. Asathulla, S. Khanna, N. Lahn, and S. Raghvendra, A faster algorithm for minimum-cost bipartite perfect matching in planar graphs, ACM Trans. Algorithms, 16 (2020). 2:1-2:30
[5] J.-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyré, Iterative bregman projections for regularized transportation problems, SIAM Journal Scientific Computing, 37 (2015), A1111-A1138,
[6] E. Bernton, P. E. Jacob, M. Gerber, and C. P. Robert, On parameter estimation with the Wasserstein distance, Information and Inference: Journal of the IMA, 8 (2019), 657-676.
[7] G. Beugnot, A. Genevay, K. Greenewald, and J. Solomon, Improving approximate optimal transport distances using quantization, arXiv preprint arXiv:2102.12731 (2021).
[8] J. Bigot, R. Gouet, T. Klein, A. López, et al., Geodesic PCA in the wasserstein space by convex PCA, Annales de l l'Institut Henri Poincaré, Probabilités et Statistiques, Vol. 53, Institut Henri Poincaré, 2017, pp. 1-26.
[9] J. Blanchet, A. Jambulapati, C. Kent, and A. Sidford, Towards optimal running times for optimal transport, arXiv: 1810007717 [es.DS], (2018).
[10] M. Cuturi and A. Doucet, Fast computation wasserstein barycenters, Internation Conference on Machine Learning, 2014, pp. 685-693.
[11] R. M. Dudley, Distances of probability measures and random variables, The Annals of Mathe- matical Statistics, 39 (1968), 1563-1572.
[12] Dvurechensky, A. Gasnikov, and A. Kroshnin, Computational optimal transport: Complexity by accelerated gradient descent is better than by sinkhorn's 's algorithm, International Conference on Machine Learning, 2018, pp. 1366-1375.
[13] A. Efrat, A. Itai, and M. J. Katz, Geometry helps in bottleneck matching and related problems, Algorithmica, 31 (2001), 1-28.
[14] R. Flamary, M. Cuturi, N. Courty, and A. Rakotomamonjy, Wasserstein discriminant analysis, Machine Learning, 107 (2018), 1923-1945.
[15] H. N. Gabow and R. E. Tarjan, Faster scaling algorithms for network problems, SIAM Journal on Computing, 18 (1989), 1013-1036.
[16] A. L.. Gibbs and F. E. Su, On choosing and bounding probability metrics, International statistical review, 70 (2002), 435.
[17] Godi, Bottleneck distance, in: GUDHI User and Reference Manual, GUDHI Editorial Board, 3.4.1 edition, 2021.
[18] Hopcroft and R. M. Karp., An 5/2 algorithm for maximum matchings bipartite graphs., SIAM Journal on Computing. 2 (1905), 1973-231.

---

[19] J. Huber, Robust Statistics, New York: John Wiley and Sons, 1981.
[20] M. L. Huson and A. Sen, Broadcast scheduling algorithms for radio networks, Proceedings of MILCOM'95 '95, Vol. 2, IEEE, 1995, pp. 647-651.
[21] M. Katz and M. Sharir, An expander- based approach to geometric optimization, SIAM Journal on Computing, 26 (1997), 1384-1408.
[22] M. Kerber, D. Morozov, and A. Nigmetov, Geometry helps to compare persistence diagrams, Journal of Experimental Algorithmics (JEA), 22 (2017), 1-20.
[23] S. Kolouri, K. Nadjahi, U. Simsekli, R. Badeau, and G. Rohde, Generalized sliced wasserstein distances, Advances in Neural Information Processing Systems (H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buu Buc, E. Fox, and Garnett, eds.), Vol. 32, Curran Associates, Inc., 2019.
[24] H. W. Kuhn, The hungarian method for the assignment problem, Naval Research Logistics Quarterly, (1955), 83-97.
[25] T. Lacombe, M. Cuturi, and S. Oudut, Large scale computation of means and clusters for persistence diagrams using optimal transport, Advances in Neural Information Processing Systems (S. Bengio, H. Wallach, H. Larochelle, Grauman, N. Cesa- Besa-Bianchi, and R. Garnett, eds.), Vol. 31, Curran Associates, Inc., 2018.
[26] N. Lahn, D. Mulchandani, and S. Raghvendra, A graph theoretic additive approximation of optimal transport, Advances in Neural Information Processing Systems 32, 2019, pp. 13813- 13823.
[27] N. Lahn and S. Raghvendra, A faster algorithm for minimum-cos cost bipartite matching in minor- free graphs, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 569-588.
[28] N. Lahn and S. Raghvendra, A weighted approach to the maximum cardinality bipartite matching problem with applications in geometric settings, Journal of Computational Geometry, (2021). Special Issue of Selected Papers from SoCG 2019.
[29] F. T. Leighton and P. W. Shor, Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms, Proceedings of the 18th Anmual ACM Symposium on Theory of Computing, ACM, 1986, pp. 91-103.
[30] T. Lin, N. Ho, and M. I. Jordan, On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms,
[cs.DS], (2019).
[31] A. Madry, Navigating central path with electrical flows: From flows to matchings, and back, 54th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 253-262.
[32] R. Motwani, Average-case analysis of algorithms for matchings and related problems, J. ACM,
41 (1994), 1329-1356.
[33] M. Mucha and P. Sankowski, Maximum matchings via gaussian elimination, 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp.
[34] Y. V. Prokhorov, Convergence of random processes and limit theorems in probability theory, Teor: Veroyatnost. i Primenen., (1956), 177-238. [English translation: Theory Probab. Appl. (1956), 157-214].
[35] K. Quanrud, Approximating optimal transport with linear programs, Symposium on Simplicity of Algorithms, Vol. 69, 2019, pp. 6:1-6:9.
[36] R. Sandler and M. Lindenbaum, Nonnegative matrix factorization with earth mover's distance metric for image analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, 33 (2011), 1590-1602.
[37] W. Shor and J. E. Yukich, Minimax Grid Matching and Empirical Measures, The Annals of Probability, 19 (1991), 1338 1348.
12

---

[38] V. Strassen, The existence of probability measures with given marginals, The Annals of Mathe- matical Statistics, 36 (1965). 423-4334
[39] van den Brand, Y. T. Lee, Y. P. Liu, T. Saranurak, A. Sidford, Z. Song, and D. Wang, Minimum cost flows, mdps, and -i-rereesioon in nearly linear time for dense instances, 2021.
[40] S. Vishwanath, K. Fukumizu, S. Kuriki, and B. K. Sriperumbudur, Robust persistence diagrams using reproducing kernels, Advances in Newral Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, eds.), Vol. 33, Curran Associates, Inc., 2020,
pp. 21900-21911.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Any limitations of the work should be apparent from the descriptions of the relevant problem statements that have been included.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] We are not aware of any potential negative societal impacts of this work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Ys]] Our paper does not involve human subjects sensitive data, and not aware of any relevant ethical concerns.
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Some proofs are included in the supplemental materials.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [N/A] Our experiments are focused on analyzing running times of algorithms, and are not concerned with training on data sets.
(c) Did you report error bars (c.g., with respect to the random seed after running ex- periments multiple times)? [Yes] For applicable charts, included error bars that represent a single standard deviation.
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] We do not use existing assets.
(b) Did you mention the license of the assets? [N/A] We do not use existing assets.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We include code in the supplemental materials.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We did not use existing data.
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] Our only input data consists of randomly generated geometric points.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "d7n0BNre6V8", "reviewer": "Reviewer_bfYJ", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThe 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?\n\nRegarding 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.\n\nThere some important typos that should be corrected and all of the formal details should be carefully proofread:\nLine 155: “free vertex a in B_F” should refer to “b” not “a”.\nLine 174: “n” should be “\\sqrt{n}”", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "[N/A]", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "Lro8QSGnqO", "reviewer": "Reviewer_HbxE", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nWhile 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", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The experiments feel lacking to me for several reasons:\n* 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.\n* the factor 4 gain over the HK baseline feels marginal, and doesn't show a clear asymptotic improvement", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "CVzfgHiwBBd", "reviewer": "Reviewer_oexc", "summary": "This paper has the following contributions about algos for max matching on graphs with recursive separators:\n\n1 simplifying the recent LR algo to not require dual weights\n\n2 showing how this algo can find maximum matchings asymptotically faster than the classic (HK) algo for disc graphs with low \"density\"\n\n3 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\n\n4 experiments that show the proposed algo is faster than HK for 2 uniform point clouds in [0,1]^2", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nMy 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.\n\nother comments:\n- The algo does not seem parallelizable due to BFS/DFS. This is critical for ML scale. Is parallelization possible?\n- 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.\n- Consider stating Levy-Prokhorov reduction in its own lemma since its of general interest.\n- Typos: L53 del->eps, L72 / -> *, L155: a->b, L181: V->E, L331 and Leighton, L406: of", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "ok", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)