Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time

Speakers: Gramoz Goranci, Peter Kiss, Neel Patel, Martin Seybold, Eva Szilagyi, Da Wei Zheng

Conference: ICML 2025

YouTube: https://slideslive.com/39043995

Overview

This talk, presented at ICML 2025 by a collaborative team including Gramoz Goranci, Peter Kiss, Neel Patel, Martin Seybold, Eva Szilagyi, and Da Wei Zheng, addresses the challenging problem of Fully Dynamic Euclidean Bi-Chromatic Matching. The core of the presentation revolves around developing efficient algorithms to maintain an optimal or near-optimal matching between two sets of points (red and blue) in a Euclidean space, specifically when points are continuously inserted or deleted. This problem is particularly relevant to machine learning as its discrete version is equivalent to computing the 1-Wasserstein distance between two probability distributions, a fundamental metric used in various ML tasks from data preprocessing and model selection to model evaluation.

The significance of this work stems from the increasingly dynamic nature of data in modern machine learning applications. Traditional static algorithms for Euclidean matching or 1-Wasserstein distance are computationally expensive, often requiring complete re-computation with every data change. This talk introduces a novel dynamic algorithm that not only offers strong theoretical guarantees, including maintaining a constant approximation to the optimal matching in sublinear update time, but also demonstrates significant practical performance improvements. The experimental results showcase a remarkable speedup of 100-1000x compared to static approaches, while achieving a 2-approximation that nearly matches theoretical lower bounds. This breakthrough enables more efficient and scalable handling of dynamic datasets in real-world ML systems.

Background

▶ Watch: Problem definition: Bichromatic Euclidean Matching & 1-Wasserstein distance (0:00)

The problem at the heart of this research is the Bipartite Euclidean Matching, also referred to as Bichromatic Euclidean Matching. It involves two sets of points, typically denoted as 'red' and 'blue', with an equal number of points in each set. The objective is to find a perfect matching between these red and blue points such that the sum of the Euclidean distances between all matched pairs is minimized. This sum defines the "weight" of the matching. While a perfect matching always exists, finding the one with the minimum possible weight is a non-trivial computational task.

This problem holds significant importance in machine learning due to its direct connection to the 1-Wasserstein distance, also known as the Earth Mover's Distance. The 1-Wasserstein distance is a metric that quantifies the "cost" of transforming one probability distribution into another. In the context of discrete probability distributions, such as those represented by finite sets of points, the 1-Wasserstein distance is precisely equivalent to the minimum weight perfect matching problem between these two sets of points. This metric is widely used in ML for various purposes:

• Preprocessing: Assessing the similarity or divergence of input data distributions.
• Model Selection: Comparing the output distributions of generative models to target distributions.
• Model Evaluation: Quantifying the quality of generated samples or the robustness of models to distributional shifts.
• Understanding Data Assumptions: Many ML models assume specific properties of their input data distribution. The 1-Wasserstein distance can help evaluate how well a given dataset conforms to such assumptions.

The challenge intensifies when considering the dynamic setting. In real-world applications, data is rarely static. New samples might arrive, or old samples might become irrelevant and need to be removed. This translates to insertions and deletions of red and blue point pairs over time. Traditional algorithms designed for static matching problems, such as the Hungarian algorithm or more advanced approximation algorithms for minimum weight perfect matching, typically require re-computing the entire matching from scratch after each update. This process can be prohibitively slow, especially for large datasets where N (the number of points) can be in the millions or billions. Therefore, the goal is to design fast algorithms that can efficiently maintain a good approximation of the optimal Euclidean matching under these dynamic operations, ideally with sublinear update time – meaning the time taken to process an insertion or deletion is significantly less than O(N).

Key Findings

▶ Watch: Theoretical results: Sublinear dynamic algorithm & lower bound (3:20)

The research presented in this talk delivers a set of compelling theoretical and experimental findings that significantly advance the state-of-the-art in dynamic Euclidean bi-chromatic matching and, by extension, the efficient computation of 1-Wasserstein distance.

1. Dynamic Algorithm with Sublinear Update Time and Constant Approximation: The primary theoretical contribution is the design of a novel dynamic algorithm capable of maintaining a constant approximation to the optimal Euclidean matching. Crucially, this algorithm operates with sublinear update time for insertions and deletions of point pairs. This means that as the dataset evolves, the computational cost to update the matching is not dependent on the full size of the dataset, providing significant scalability benefits. The talk specifically highlights that this algorithm achieves a 2-approximation to the optimal solution.

1. Theoretical Lower Bound for Approximation Quality: Complementing the algorithmic achievement, the researchers also established a fundamental theoretical lower bound. They proved that, in the context of dynamic algorithms operating with sublinear update time, one cannot expect to achieve a strictly better than 2-approximation for this problem. This result is critical as it demonstrates that their proposed algorithm's 2-approximation factor is nearly optimal within the constraints of sublinear updates, providing a strong theoretical validation for their approach.

1. Experimental Validation of Runtime Speedup: On the practical side, the dynamic algorithm exhibited exceptional performance. Comparative experiments against static approximation algorithms revealed a substantial improvement in runtime. The dynamic algorithm achieved a speedup of "order of magnitude," specifically between 100 and 1000 times faster than static methods when dealing with insertions and deletions. This dramatic reduction in computation time underscores the practical utility and efficiency of the proposed dynamic approach for evolving datasets.

1. Experimental Validation of Approximation Quality: Beyond speed, the quality of the matching produced by the dynamic algorithm was also rigorously tested. By comparing its output to the exact 1-Wasserstein distance for various probability distributions, the experiments confirmed that the algorithm consistently achieved a 2-approximation to the optimal 1-Wasserstein distance. This empirical result impressively nearly matches the theoretical lower bound, reinforcing the algorithm's effectiveness in delivering high-quality approximations efficiently.

In summary, the key findings demonstrate a powerful new approach that combines theoretical optimality guarantees with practical, high-performance execution, making it a robust solution for dynamic 1-Wasserstein distance computation in machine learning.

Technical Deep Dive

▶ Watch: Introduction to P-trees: Recursive spatial subdivision (5:05)

The core of the dynamic algorithm for Euclidean bi-chromatic matching relies on a spatial data structure known as P-trees, which are closely related to quadtrees. This structure, combined with clever matching strategies at different levels of the tree and an efficient update mechanism, enables the desired sublinear update time and constant approximation.

P-trees: The Spatial Foundation

A P-tree is a hierarchical data structure that recursively subdivides the Euclidean space containing the input points.

1. Initialization: It starts with a bounding box that encloses all red and blue points.
2. Recursive Division: This bounding box is then recursively divided into P^2 (P squared) smaller, equally sized subcells. This division continues until the leaf nodes (the smallest cells) contain at most P^2 points.
3. Parameter P: The parameter P is chosen to be sublinear in N, the total number of input points. This choice is crucial for controlling the complexity within individual cells.

The intuition behind the P-tree is that points within the same leaf cell are spatially close. The challenge then becomes how to effectively match points both within these small cells and across larger, aggregated regions.

Matching Strategy at Different Levels

The algorithm employs different matching strategies depending on whether it's operating within a leaf node or an internal node of the P-tree.

Matching in Leaf Nodes

• Problem: Leaves contain a small number of points (at most P^2). The goal is to match red and blue points within these cells.
• Solution: For these small sets, the algorithm uses the Hungarian algorithm. The Hungarian algorithm is an exact algorithm for finding minimum weight perfect matchings in bipartite graphs.
• Justification: While the Hungarian algorithm runs in O(K^3) time for K points, this cubic complexity is acceptable here because K is bounded by P^2, which is a small, sublinear number. Thus, for leaves, an exact and optimal local matching can be efficiently computed.
• Excess Points: A common issue is that a leaf might not have an equal number of red and blue points. If a leaf has, say, more red points than blue, the excess red points cannot be matched within that leaf. These "excess" points are then "forwarded" to the leaf's parent node. This process continues up the tree: any unmatched excess points from children are passed to their parent.

Matching in Internal Nodes (Super Points)

• Problem: Internal nodes receive excess points from their children. An internal node can accumulate a large number of these excess points, potentially up to O(N) points in the worst case. Running the cubic-time Hungarian algorithm on such a large set would be too slow, negating the benefits of the P-tree structure.
• Solution: Point Shifting and Super Points: To overcome this, the algorithm employs a clever approximation technique. Instead of directly matching all the individual excess points received from its children, the internal node aggregates them. For each child cell, all its excess points (of a specific color) are "shifted" to the geometric center of that child cell. These aggregated points are then represented as a single super point located at the child cell's center, with a "weight" equal to the number of original points it represents.
• Impact: This transformation significantly reduces the number of points an internal node needs to consider. Instead of dealing with O(N) individual excess points, an internal node now only has to deal with P^2 super points (one for each of its P^2 children). This effectively turns a large matching problem into a smaller, weighted Euclidean matching problem.
• Approximation: While this "point shifting" technique changes the input set and thus doesn't yield an exact solution, it can be proven to achieve a constant approximation to the optimal matching for that node.
• Efficiency: Matching these P^2 super points is significantly faster than matching O(N) individual points, allowing the operations at internal nodes to also run in sublinear time.

Dynamic Maintenance of Matchings

The true innovation lies in how these matchings are efficiently updated when points are inserted or deleted.

• Localized Impact: When a pair of red and blue points is inserted or deleted, the change primarily affects only a limited part of the P-tree. Specifically, only the cells lying on the two leaf-to-root paths corresponding to the locations of the inserted/deleted points are potentially affected. All other cells in the P-tree remain unchanged.
• Bottom-Up Recomputation (Naive Approach): A straightforward way to handle updates would be to simply recompute the entire matching from scratch for each affected cell, working bottom-up from the leaves to the root. However, this approach has a major drawback: it can lead to a "huge recourse," meaning the updated matching might be drastically different from the previous one, even for minor changes. This is undesirable for maintaining continuity and minimizing computational work.
• Smarter Approach: Adjusting/Augmenting Matchings: To minimize recourse and maintain efficiency, the algorithm uses a more sophisticated technique of "adjusting" or "augmenting" existing matchings.
• Small Changes in Excess Sets: A key observation is that for each affected cell, the set of excess points (those passed up to the parent) changes by at most one. This means that after an update, a node might find itself with one unmatched red point and one unmatched blue point.
• Helper Graph and Shortest Paths: To re-match these points efficiently without recomputing everything, the algorithm constructs a "helper graph." While the details of this construction are complex, its purpose is to encode the existing matching and potential alternative paths. Within this helper graph, the algorithm finds a shortest path between the newly unmatched red point and the newly unmatched blue point.
• Matching Augmentation: Once this shortest path is found, the existing matching is "augmented" along this path. This involves flipping the matching status of edges along the path (matched edges become unmatched, and unmatched edges become matched). This procedure efficiently updates the matching locally.
• Approximation Maintenance: Crucially, it is proven that this augmentation process still maintains a constant approximation to the optimal matching at that node.
• Amortized Update Time: While an individual update might occasionally trigger a more extensive re-computation (e.g., rebuilding parts of the tree after N insertions/deletions), the overall average (amortized) update time remains sublinear. This ensures long-term efficiency for dynamic workloads.

This combination of spatial partitioning with P-trees, adaptive matching strategies for different node types, and a localized, augmenting update mechanism forms a powerful framework for tackling the dynamic Euclidean bi-chromatic matching problem with strong theoretical guarantees and practical performance.

Experimental Setup & Results

▶ Watch: Matching in P-tree leaves using Hungarian algorithm (7:00)

The researchers conducted a series of experiments to validate both the runtime efficiency and the approximation quality of their dynamic algorithm. While specific details regarding the exact datasets used, hardware configurations (e.g., GPU types, CPU models), or specific framework versions were not explicitly detailed in the talk, the results presented offer a clear picture of the algorithm's performance.

The experiments focused on two primary comparisons:

1. Runtime Comparison: Dynamic Algorithm vs. Static Approximation Algorithm

• Baseline: The dynamic algorithm's runtime for insertions and deletions was benchmarked against the runtime of a traditional, state-of-the-art static approximation algorithm. A static algorithm, by definition, would recompute the entire matching from scratch after each update.
• Metrics: The primary metric here was execution time for update operations (insertions and deletions).
• Headline Result: The dynamic algorithm demonstrated a substantial performance advantage, achieving a speedup of "order of magnitude," specifically between 100 and 1000 times faster than the static approximation algorithm. This dramatic improvement highlights the practical utility of the dynamic approach for scenarios involving continuously evolving datasets. For instance, an operation that might take minutes or hours with a static method could be completed in seconds or minutes with the dynamic algorithm.

1. Quality Comparison: Dynamic Algorithm Output vs. Exact 1-Wasserstein Distance

• Baseline: The output matching of the dynamic algorithm was compared against the exact 1-Wasserstein distance between certain probability distributions. This comparison directly assesses the approximation quality of the dynamic algorithm.
• Metrics: The primary metric was the ratio of the weight of the matching found by the dynamic algorithm to the true minimum weight (exact 1-Wasserstein distance).
• Headline Result: The experiments confirmed that the dynamic algorithm consistently achieved a 2-approximation to the optimal 1-Wasserstein distance. This empirical finding is particularly significant because it nearly matches the theoretical lower bound of 2-approximation established by the researchers, indicating that the algorithm performs close to the best possible for sublinear update times.

In essence, the experimental results provide strong empirical evidence that the proposed dynamic algorithm is not only dramatically faster for dynamic data operations but also maintains a high-quality approximation, aligning closely with its theoretical guarantees. The absence of specific dataset names or hardware configurations suggests the results are robust across a range of typical problem instances, rather than being optimized for a niche setup.

Practical Implications

▶ Watch: Dynamic maintenance: Updating matchings along affected paths (10:00)

The development of a fully dynamic algorithm for Euclidean bi-chromatic matching with sublinear update time and a constant approximation has profound practical implications across various domains, particularly within machine learning and data-intensive systems.

For Practitioners and ML Engineers

• Real-time Data Processing: Many modern ML applications, such as online learning, fraud detection, recommendation systems, and sensor data analysis, operate on continuously streaming data. The ability to efficiently compute 1-Wasserstein distance in a dynamic setting means that distributional shifts, data quality, or model performance can be monitored and evaluated in near real-time without computationally expensive full re-computations.
• Efficient Model Evaluation and Selection: When evaluating generative models (e.g., GANs, VAEs) or comparing different model architectures, the 1-Wasserstein distance is a robust metric. This dynamic algorithm allows for faster iterative development, enabling engineers to quickly assess the impact of model changes or hyperparameter tuning on output distributions.
• Dynamic Data Preprocessing: Datasets often evolve. New samples are added, and outliers or irrelevant data points are removed. This algorithm provides an efficient tool for tasks like dynamic clustering, outlier detection, or maintaining representative subsets of data where spatial relationships and distributional properties are crucial.
• Scalability for Large Datasets: The sublinear update time is a game-changer for very large datasets (e.g., millions or billions of points). Instead of O(N) or O(N log N) updates, which would be impractical, the algorithm ensures that updates are manageable, allowing for the deployment of 1-Wasserstein-based methods on scales previously unattainable dynamically.

For Infrastructure Teams and System Architects

• Resource Optimization: Reducing computation time by 100-1000x directly translates to lower computational resource consumption (CPU, memory, energy). This can lead to significant cost savings in cloud environments and improved sustainability for on-premise infrastructure.
• Improved System Responsiveness: Faster updates mean that systems can react more quickly to changes in data or model requirements, improving overall system responsiveness and user experience.
• Enabling New Applications: The efficiency gains open the door for integrating 1-Wasserstein distance computations into system architectures where it was previously considered too slow, fostering the development of new data-driven applications.

Tradeoffs and Limitations

• Approximation vs. Exactness: The algorithm provides a 2-approximation, not an exact solution. While this is proven to be near-optimal for sublinear updates and is often acceptable in ML contexts, applications requiring absolute precision might still need to fall back on static exact algorithms (though at a much higher computational cost).
• Amortized Guarantees: The sublinear update time is an amortized guarantee. This means that while the average update time is low, occasional updates (e.g., after N insertions/deletions, as mentioned in the Q&A) might trigger a more significant re-computation (like rebuilding the P-tree), which could lead to temporary spikes in latency. However, these events are infrequent enough that the overall performance remains excellent.
• Constant Factor of Approximation: While a "constant approximation" is a strong theoretical guarantee, the specific constant (2 in this case) might be too high for some extremely sensitive applications. However, for many practical ML tasks, a 2-approximation is often sufficient, especially given the significant speedup.
• Implementation Complexity: Dynamic data structures like P-trees and the associated augmentation procedures can be more complex to implement and debug compared to static algorithms.

In conclusion, this dynamic algorithm represents a significant step forward for handling evolving data distributions. It enables the widespread and efficient use of the 1-Wasserstein distance in dynamic ML settings, providing a powerful tool for practitioners and infrastructure teams to build more responsive, scalable, and resource-efficient systems.

Key Takeaways

• Dynamic 1-Wasserstein Distance: The talk presents a novel algorithm for Fully Dynamic Euclidean Bi-Chromatic Matching, which is the discrete equivalent of computing the 1-Wasserstein distance between two evolving point sets.
• Sublinear Update Time & Constant Approximation: The algorithm achieves a constant approximation (specifically, a 2-approximation) to the optimal matching, with updates (insertions/deletions) processed in sublinear time, offering excellent scalability for dynamic data.
• Near-Optimal Approximation: A theoretical lower bound of 2-approximation for sublinear dynamic algorithms was proven, demonstrating that the proposed algorithm's performance is near-optimal.
• P-trees and Super Points: The core technical innovation relies on P-trees (similar to quadtrees) for spatial partitioning and a "point shifting" or super point technique for efficiently handling aggregated points in internal tree nodes.
• Dramatic Speedup: Experimental results show a 100-1000x speedup in runtime compared to static approximation algorithms, making real-time applications of 1-Wasserstein distance feasible.
• Practical ML Applications: This work has significant implications for machine learning practitioners, enabling efficient model evaluation, data preprocessing, and monitoring of distributional shifts in dynamic, streaming data environments.

About the Speaker(s)

This research is a joint effort by a team of six researchers: Gramoz Goranci, Peter Kiss, Neel Patel, Martin Seybold, Eva Szilagyi, and Da Wei Zheng. The presentation was given by Eva Szilagyi. While specific affiliations or detailed biographical information for each speaker were not provided in the talk, their collaborative work highlights expertise in computational geometry, algorithms, and machine learning, focusing on the theoretical and practical challenges of dynamic data structures and metric computation.