Abstract
In the reconciliation $k$-median problem, we aim to cluster a set of data points by selecting $k$ cluster centers to minimize the sum of distances from data points to their nearest centers plus the sum of pairwise distances between the centers. This variant of the classic $k$-median problem is designed to find cluster centers that are not excessively distant from each other, which is particularly useful in applications like selecting representative committees for deliberation. Previously, only local-search-based algorithms with an $O(k)$ approximation factor were known. In this work, we demonstrate a connection between reconciliation $k$-median and a variant of the $k$-facility location problem. This connection allows us to develop the first constant-factor approximation algorithm for the problem. Furthermore, we introduce a sparsification scheme that reduces the number of potential cluster centers to $O(k)$, significantly accelerating the computation. Empirical evaluations show that our algorithms provide improved performance and stability compared to previous methods.
Introduction
Standard $k$-median clustering focuses on minimizing the "service cost"—the distance between data points and their assigned centers. However, in social and collaborative contexts, the relationship between the centers themselves is often just as important. For instance, when selecting a committee to represent diverse viewpoints, choosing extreme outliers can lead to polarization and gridlock.
The reconciliation $k$-median problem addresses this by adding a "disagreement cost" (the sum of pairwise distances between all chosen centers) to the objective function. The goal is to balance data representation with center reconciliation. Prior to this work, the state-of-the-art was a local-search heuristic with an $O(k)$ approximation guarantee, meaning the potential error scaled linearly with the number of clusters. This paper provides the first constant-factor guarantee, ensuring the error bound remains fixed regardless of $k$.
Methods
The proposed solution relies on three key innovations:
- The "Anchor" Reduction: The primary challenge is that the cost of selecting one center depends on all other centers. The authors overcome this by identifying an "anchor" facility—the 1-median of the optimal centers. By iterating through all possible facilities as potential anchors, the global disagreement cost can be decomposed into individual "opening costs" for each facility.
- Reduction to EXACT $k$-Facility Location: Using the anchor reduction, the problem is transformed into a variant of the $k$-facility location problem. The authors adapt linear programming (LP) rounding and local search techniques to ensure exactly $k$ facilities are opened while maintaining the approximation guarantee.
- Adaptive Sparsification: To handle large datasets where testing every potential anchor is infeasible, the authors developed a sparsification scheme based on adaptive sampling (similar to $k$-means++). This reduces the candidate set to $O(k)$ facilities while maintaining a near-optimal solution space.
Experimental Evaluation
The algorithms were evaluated on several real-world datasets:
- CONGRESS: Voting records from the 115th US Congress.
- WIKIELECTIONS: A 25-dimensional embedding of Wikipedia moderator election data.
- TWITTER: A large-scale follower network used to test the scalability of the sparsification method.
The experiments compared the new algorithm ($k$-UFL+LS) against the standard local search heuristic across varying values of $k$ and the reconciliation weight $\lambda$.
Key Results
The theoretical analysis proves a constant approximation ratio of $6.5 + \epsilon$. Empirically, the $k$-UFL+LS algorithm consistently outperformed standard local search, particularly as the problem complexity increased.
As shown in Figure 3, the cost ratio increases with both the number of clusters $k$ and the reconciliation weight $\lambda$, indicating that the new algorithm is more robust to high-polarization constraints. Furthermore, the sparsification method allowed for processing the large WikiElections dataset by considering only a few dozen candidate centers, achieving massive speedups with negligible loss in solution quality.
Conclusion
This work provides a significant theoretical and practical advancement for the reconciliation $k$-median problem. By reducing the problem to facility location and introducing effective sparsification, the authors offer a robust framework for balanced clustering. Future work may focus on further improving scalability for massive datasets and optimizing for specific metric spaces like Euclidean geometry.
Paper Citation: Joachim Spoerhase, Kamyar Khodamoradi, Benedikt Riegel, Bruno Ordozgoiti, Aristides Gionis. "A Constant-Factor Approximation Algorithm for Reconciliation $k$-Median." Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (AISTATS), 2023.
Summary updated