Reconciliation k-median: Clustering with Non-polarized Representatives

Bruno Ordozgoiti, Aristides Gionis

TL;DR

This paper introduces "Reconciliation k-median," a novel clustering problem that aims to find representative data points while also minimizing the "disagreement" or ideological distance between these representatives. They adapt a local search algorithm to solve this problem, demonstrating that it can lead to less polarized clusters without significantly sacrificing data representation quality.

What Problem Does This Paper Address?

Clustering algorithms, like k-median, are widely used to summarize large datasets by identifying a small set of representative points. However, traditional k-median focuses solely on minimizing the cost of assigning data points to their nearest representative. This can lead to representatives that are very far apart from each other, which is undesirable in applications where consensus or a balanced perspective is crucial. For instance, when summarizing news articles on a topic, selecting representatives from extreme ends of the ideological spectrum might not foster constructive deliberation. Similarly, when electing a committee, members who are too ideologically distant might struggle to reach an agreement. This paper addresses the need for clustering methods that not only ensure good data representation but also promote agreement or reduce polarization among the chosen representatives.

Methods

The core contribution is the formulation of the "Reconciliation k-median" problem, which adds a penalty term to the standard k-median objective function. This penalty term directly penalizes the sum of distances between all pairs of selected representatives.

To solve this NP-hard problem, the authors adapt the local search algorithm proposed by Arya et al. [3] for the standard k-median problem. The adapted algorithm starts with a random set of k representatives and iteratively tries to improve the objective function by swapping a selected representative with a non-selected one. The key novelty lies in how the cost function is evaluated during these swaps, incorporating both the data representation cost and the new disagreement penalty.

The paper also provides theoretical analysis, proving that the adapted local search algorithm achieves approximation guarantees. Specifically, it offers an O(k) approximation guarantee in the general case and a constant factor guarantee under mild assumptions about cluster sizes.

Datasets

The authors evaluate their approach on three real-world datasets:

  • Twitter: A dataset of politically active Twitter accounts, where facilities (representatives) and clients (users) are derived from follower graphs.
  • Congress: Roll call voting records from the US Congress, where representatives are clustered based on their voting patterns. This dataset is specifically configured to have an equal number of Democrat and Republican representatives.
  • Domains: A dataset combining news sources shared on Facebook with politically active Twitter users. This dataset allows for exploring how to select less polarized news sources.

For distance calculations, they employ various metrics, including shortest path distances on graphs, spectral embeddings, and Euclidean distances on latent representations. Notably, they sometimes use different distance metrics for facility-client assignments and facility-facility disagreement, reflecting practical scenarios.

Key Insights and Ideas

  • The "Reconciliation" Objective: The introduction of a penalty for representative disagreement is a novel way to steer clustering towards more cohesive or less extreme groups.
  • Balancing Representation and Agreement: The experiments suggest that it's possible to significantly reduce the polarization of representatives without a substantial increase in the standard k-median cost, indicating a good trade-off.
  • Impact of the Penalty Parameter (λ): Increasing the weight (λ) of the disagreement penalty term generally leads to less polarized representatives, as expected.
  • Metric Choice Matters: The choice of distance metric can influence the effectiveness of the reconciliation objective, with spectral embeddings showing promising results on the Twitter dataset.
  • Practical Applicability: The algorithm is shown to converge in a reasonable number of iterations, suggesting its practical viability.

Key Results

  • Reduced Polarization: Experiments on Twitter and Domains datasets show that increasing λ leads to a noticeable decrease in the polarity of the chosen representatives, as measured by standard ideology estimation methods.
  • Approximation Guarantees: The proposed local search algorithm provides theoretical approximation guarantees for the Reconciliation k-median problem, with a constant factor guarantee under specific conditions.
  • Trade-off: For the Twitter dataset, significant decreases in polarity were achieved with only a marginal increase in the k-median cost, demonstrating the effectiveness of the reconciliation objective.
  • Dataset-Specific Behavior: The impact of λ on polarity reduction varies across datasets and configurations (e.g., k value, metric used). For instance, for small k on the Domains dataset, the method did not show a reduction in polarity.

Limitations and Future Work

  • Theoretical Assumptions: The theoretical approximation guarantees rely on specific assumptions about the distance metric being a true metric and the cluster sizes being sufficiently large. The experimental evaluation relaxes these assumptions to explore practical scenarios.
  • Computational Complexity: While the local search algorithm is scalable, its theoretical complexity per iteration can be high (O(nmk)). However, empirical results suggest practical convergence in few iterations.
  • Future Directions: The authors suggest improving approximation guarantees, exploring tighter bounds, and investigating how different metrics interact with polarization estimation methods. They also highlight the potential for using simultaneous swaps in the local search algorithm for better performance-time trade-offs.

Summary updated

BibTeX
@inproceedings{ordozgoiti2019reconciliation,
  author = {Bruno Ordozgoiti and Aristides Gionis},
  title = {{Reconciliation k-median: Clustering with Non-polarized Representatives}},
  booktitle = {The Web Conference},
  year = {2019},
  doi = {10.1145/3308558.3313475},
}

Loading related content...

Figure