Reconciliation k-median: Clustering with Non-Polarized Representatives
Bruno Ordozgoiti Aristides Gionis


Reconciliation k-median]Reconciliation k-median: Clustering with Non-polarized Representatives



The work described in this paper was done while this author was a visitor at Aalto University.

  Department of Computer Systems 

    Universidad Politécnica de Madrid

bruno.ordozgoiti@upm.es



  Department of Computer Science 

   Aalto University
  

aristides.gionis@aalto.fi





  
We propose a new variant of the problem, 
where the objective function models not only the cost of assigning 
data points to cluster representatives, 
but also a penalty term for disagreement among the representatives. 
We motivate this novel problem by applications where we are interested in clustering 
data while avoiding selecting representatives that are too far from each other. 
For example, we may want to summarize a set of news sources, 
but avoid selecting ideologically-extreme articles in order to reduce polarization.






To solve the proposed formulation we adopt the local-search algorithm of Arya et al. <cit.>, 
We show that the algorithm provides a provable approximation guarantee, 
which becomes constant under an assumption on the number of points for each cluster.
We experimentally evaluate our problem formulation and proposed algorithm
on datasets inspired by the motivating applications. 
In particular, we experiment with data extracted from Twitter, the US Congress voting records, and popular news sources. 
The results show that our objective can lead to choosing less polarized groups
of representatives 
without significant loss in representation fidelity.









<ccs2012>
<concept>
<concept_id>10003752.10003809.10003636.10003812</concept_id>
<concept_desc>Theory of computation Facility location and clustering</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10003752.10003809.10003716.10011136</concept_id>
<concept_desc>Theory of computation Discrete optimization</concept_desc>
<concept_significance>500</concept_significance>
</concept>
<concept>
<concept_id>10010405.10010455.10010461</concept_id>
<concept_desc>Applied computing Sociology</concept_desc>
<concept_significance>300</concept_significance>
</concept>
</ccs2012>


[500]Theory of computation Facility location and clustering
[500]Theory of computation Discrete optimization
[300]Applied computing Sociology



[
    Aristides Gionis
    December 30, 2023
=====================





§ INTRODUCTION



Clustering is one of the most well-studied problems in data analysis
with numerous applications in 
pattern recognition <cit.>, 
image analysis <cit.>,
information retrieval <cit.>,
bioinformatics <cit.>, 
data compression <cit.>, 
and many more.
The problem asks to partition a given set of items into clusters, 
such that items in the same cluster are more similar to each other than to items in other clusters.
Often a representative item is selected in each cluster.
Mathematically, the clustering problem is formulated by
defining an objective function, which captures the clustering quality, 
and the goal is to optimize this objective. 
Typical clustering objectives include , facility location, k-means, k-center, 
and more <cit.>.





Consider the problem of summarizing a set of news articles on a given topic. 
A standard approach to this problem is clustering: 
design a distance function that captures similarity between the news articles
and apply a clustering algorithm on the resulting metric space.
Common clustering formulations, such as or k-means, 
can be used <cit.>.
The original set of input news articles can then be summarized
by the (small) set of cluster representatives. 
In some cases, however, we may be interested
in selecting cluster representatives that are not too far from each other.
For example, we may want to find 
a set of representative news articles
that are not too extreme
so that they can provide a basis for constructive deliberation.
This motivation is similar to recent proposals in the literature
that aim to reduce polarization in social media <cit.>
and balance the users' content consumption <cit.>.
In this work we are interested in developing computational methods for 
clustering data
in a way that the disagreement of the cluster representatives is minimized.


Another motivating example appears in the context of news consumption in social media,
where users are often trapped in so-called echo chambers —
where they interact only with similar-minded users and 
consume content that confirms their existing points of view <cit.>.  
To alleviate the risks of selective exposure to information 
and to situations where users do not hear the arguments of the opposing side, 
researchers have proposed ideas for reducing polarization and 
balancing the users' news diets <cit.>; 
several tools have also been devised to help users escape their filter bubbles <cit.>.
Another approach to alleviate the problem of echo chambers
is to present to users a selection of news items 
encompassing different view points. 
As in the case of committee election, 
we are interested in finding a set of representative news items, 
which are not too extreme, 
so that they can provide a basis for constructive deliberation.



Another motivating example appears in the context of electing a k-member committee 
to represent a set of individuals, 
such as the employees of an organization or the members of a political party. 


Assuming that all individuals have public opinions on a set of issues, 
clustering these individuals on an opinion-representation space
will give a committee that faithfully represents 
the set of individuals with respect to the issues under consideration. 
Despite providing a good representation of the basis, 
a committee elected with a clustering approach as the one described above
may fail to reach consensus and enact its mandate for a variety of reasons. 
One of them is potential heterogeneity within the committee members: 
each committee member may represent faithfully a segment of the basis,
but there is no provision that the committee members themselves 
are in reasonable accord with each other so as to be able to discuss effectively 
and avoid deadlocks in their decision making. 
Heterogeneity within elected members of an assembly is a widely acknowledged problem in politics —
for instance, division of representatives often results in paralysis in various left-wing political formations.
In this work we are interested in developing computational methods for electing committees, 
and other bodies of representatives, 
in a way that the disagreement of the elected members is minimized
while ensuring a faithful representation of the constituents.
Despite providing a good representation, however, 
a committee elected with a standard clustering approach 

may fail to reach consensus due to potential heterogeneity within the committee members.
Heterogeneity within elected members of an assembly is a widely acknowledged problem in politics —
for instance, division of representatives often results in paralysis in various left-wing political formations.[https://www.theguardian.com/commentisfree/2019/feb/19/podemos-spanish-politics]
As in the previous example, 
we are interested in electing a committee
in a way that the disagreement of the elected members is minimized
while ensuring a faithful representation of the constituents.

Motivated by the previous examples we introduce a new
formulation of the problem, 
where in addition to the objective we also 
seek to minimize disagreement between the cluster representatives. 
As it is customary, we consider a metric space (,), 
where  is a distance function for objects in .
We distinguish two subsets of , 
the set of facilities  and the set of clients .
The goal is to select a set of k facilities ⊆ 
— the cluster representatives —
so as to minimize the overall cost

    () =  
    ∑_∈min_∈{(,)} + 
    λ/2∑_∈∑_∈(,).

The first term is the same as in the standard , 
and expresses the cost of serving each client by its closest selected facility. 
The second term is the one introduced in this paper
and expresses disagreement between cluster representatives. 
The parameter λ determines the relative importance of the two terms.

Despite clustering being one of the most well-studied problems in statistical data analysis, 
and the numerous formulations and problem variants that have been studied in the literature, 
to our knowledge, the problem defined above has not been considered before.

As expected, the problem defined by optimizing Equation (<ref>) is -hard;

in fact optimizing each of the two terms separately is an -hard problem.



Given the hardness of the problem, it is compelling to consider algorithms with provable 
approximation guarantees. 
For the algorithm several approximation algorithms exist <cit.>.
A local-search algorithm, which is simple to implement and scalable to large datasets, 
has been proposed by Arya et al. <cit.>.
The algorithm starts with an arbitrary solution and considers a swap of p selected facilities
with p non-selected facilities; the swap is materialized if the cost improves, 
and the process continues until the cost cannot be improved. 
Arya et al. show that this 
algorithm achieves an approximation guarantee equal to 3+2/p, 
and the running time is (n^p).
In particular, for p=1, the algorithm gives an approximation guarantee equal to 5, 
while the running time is linear.

In this paper we show how to adapt the local-search algorithm of Arya et al. <cit.>
for the problem we consider and obtain an approximation guarantee (k) 
in the case F=C.
The proposed algorithm considers 1-facility swaps, i.e., p=1.
Furthermore, when the clusters of the obtained solution have equal size of
Ω(λ k), the approximation factor becomes 11, i.e., a constant. 
We complete the analysis of the proposed problem by deriving bounds on
the objective function.

Our contributions in this paper are summarized as follows.



  * We introduce the reconciliation k-median problem, 
a novel clustering problem formulation
where we aim to optimize the data representation cost
plus a term for agreement between the cluster representatives. 

  * We adapt the local-search algorithm of Arya et al. <cit.>
and obtain provable approximation guarantees for the proposed clustering problem.

  * We run experiments on datasets extracted from the Twitter social
network, US Congress voting records, and popular news sources. The results show that the proposed
objective can lead to the choice of less polarized groups of
representatives, as measured by a well-known method for ideology
estimation <cit.> and an objective estimate of the political leaning of news sources.


Erratum: A previous version of this paper incorrectly omitted some of the necessary assumptions. In particular, the statement of Theorem <ref> overlooked the requirement that the client and the facility sets be the same. On the other hand, an argument in the proof of Theorem <ref> required the cardinality of the clusters to be similar (and them being the same is sufficient). These details have been corrected in the present version. The proof of Theorem <ref>, which was omitted in the conference publication due to space constraints, is included here as well.


The rest of the paper is structured as follows.
In Section <ref> we present a brief overview to 
the literature that is most related to our work.
In Section <ref> we formally define the 
reconciliation k-median problem. 
In Section <ref> we present 
the local-search algorithm and state its approximability properties.
In Section <ref> we present our experimental evaluation, 
while Section <ref> is a short conclusion.
To improve readability, the hardness proof of the reconciliation problem
and the proof of the approximation guarantee of the local-search algorithm 
are presented in the Appendix. 





§ RELATED WORK



Data clustering is one of the most well-studied problems in data analysis,
with applications in a wide range of areas <cit.>.
Among the numerous formulations that have been proposed, 
in this paper we focus on the problem setting, 
which has been studied extensively in the theoretical computer-science literature. 
Charikar et al. <cit.> gave the first constant-factor
approximation algorithm for the problem, 
followed by improvements that relied on both
combinatorial and LP-based algorithms <cit.>. 
In this paper we build upon the local-search algorithm of Arya et al. <cit.>.
This is a simple-to-implement and scalable algorithm
that had been offering the best performance guarantee for over a decade.
The current best approximation guarantee is 2.67+ϵ, 
provided by the algorithm of Byrka et al. <cit.>,  
which optimizes a part of the algorithm of Li and Svensson <cit.>. 
However, the algorithm is not practical.

Variants of the k-median problem have also been considered, 
including the Euclidean k-median <cit.>,
capacitated k-median <cit.>, 
ordered k-median <cit.>, 
and more.
To our knowledge, however, this is the first work to study the problem of clustering
with a penalty on the disagreement of the cluster representatives.
Instead, researchers have studied the problem of 
selecting k points to maximize the sum of pairwise distances, 
i.e., the dispersion of the selected point set. 
Several constant-factor approximation algorithms have been proposed
for the maximum-dispersion problem <cit.>. 
However, the maximization makes the problem different 
and it is not clear how to adapt those algorithms in our setting.

One of our motivating applications 
is summarization of social-media content with the aim of reducing polarization 
and balancing the information content delivered to users. 
This is a relatively new research area that is receiving increasing interest <cit.>.
However, to the best of our knowledge, none of the proposed approaches uses a clustering formulation.

The second motivating application is election of committees and representatives. 
In some cases, election questions can also be formulated as voting problems.
Voting in general has been studied extensively in social sciences and economics literature. 
From the algorithmic perspective, researchers have studied questions about 
voting in social networks and concepts such as liquid and viscous democracy <cit.>.
In addition to being not directly related to our paper, this line of work 
does not directly model agreement between elected representatives.





§ PROBLEM FORMULATION





 §.§ Preliminaries
 

We formulate our problem in the general setting of metric facility location <cit.>. 
We consider a metric space (,) and two subsets ,⊆, 
not necessarily disjoint. 
The set represents facilities, 
and the set represents clients. 
A special case of interest is when clients and facilities
are defined over the same set, i.e., =.
In our discussion we consider the more general case that the sets of clients and facilities are disjoint.
The function : ×→ is a distance measure between pairs of points in .
When ∈ and ∈, 
the distance (,) represents the cost
of serving client with facility . 
The number of facilities is denoted by =|| and 
the number of clients by =||.

The goal is to open k facilities — i.e., choose k points in  — 
such that the cost of serving each client in  with the nearest selected facility is minimized. 
Given a set of facilities ⊆, with ||=k, 
and ∈, we use () 
to denote the set of clients served by facility  in the solution , that is, 
()={∈|=_∈(,)}. 
In the facility location formulation 
each facility has an associated cost, which is incurred if the facility is opened (selected).
The objective is to minimize the total cost of serving all clients plus the cost of 
opened facilities, while there is no restriction on the number of opened facilities.
When the cost of opening each facility is zero and it is required to open at most k facilities, 
the problem is known as .



 §.§ Reconciling cluster representatives
 

The problems described above, facility location and , 
are commonly used to find cluster representatives without regard to the relative position
of the representatives themselves. 
As discussed in the introduction, our goal is to modify the problem definition 
so as to find solutions in which the cluster representatives are close to each other. 
To achieve our goal we propose the following clustering variant, 
which we name reconciliation .

 []

Given a metric space (,), two sets ,⊆, 
k ∈, and a real number λ>0, find 
a set ⊆ with ||=k, so as to 
minimize the cost function

    () =  
    ∑_∈∑_∈()(,) + 
    λ/2∑_∈∑_∈(,).







In order to characterize the hardness of this problem, 
we analyze the two terms of the objective in isolation. 
The first term, which results from setting λ=0, 
is equivalent to the classical metric problem, 
shown to be -hard by Papadimitriou <cit.>. 
To analyze the second term, we define the following equivalent problem, 
which asks to find a subset of k points that minimize the sum of pairwise distances
in a metric space, i.e., minimum pairwise distances ().
[]


Given a metric space (,), a subset of objects in the metric space 
={_1, …, _n}⊆,
and a number k∈, with k < n, 
define a matrix ∈^n× n as 
_ij=(_i,_j) for all _i,_j ∈. 
The goal is to find a binary vector of dimension n that has exactly k coordinates equal to 1
and minimizes the form ^T. 
In other words, we want to find

    min     ^T , 
         ∈{0,1}^n  ^T=k.



The following lemma establishes that 
there exists no polynomial-time algorithm to find the exact solution
to the problem, unless =.
The proof is given in the Appendix.



Problem is -hard.





Lemma <ref> establishes that optimizing separately the second term of 
the objective function (<ref>) is an -hard problem.
Note, however, that the hardness of the two terms in Problem <ref> 
does not immediately imply the hardness of the overall problem. 
Consider, for instance, an objective of the form min_{ f() + (c-f()) }. 
Even though optimizing f can be an arbitrary -hard problem, the overall problem has a constant value,
and thus, it is trivial to optimize — there is nothing to be done. 
We now show that Problem <ref> is indeed -hard.



Problem is -hard.


Consider an instance of the problem, for a given set and a number k, 
and form an instance (,,k,λ) of the problem,  
where is any arbitrary set of clients with ∩=∅.  
Set 
(,)=1/2max_,∈{(,)}, 
for all ∈ and ∈. 
Note that the distance function is still a valid metric.
We have that ∑_∈min_∈(,) is constant
for any potential solution set ⊆,
which implies that optimizing is 
equivalent to optimizing .
Thus, from Lemma <ref> we obtain that is -hard.



I changed 
(,)=k^2max_,∈{(,)}	
to
(,)=1/2max_,∈{(,)}. 
I did not understand why k^2 was needed.





 §.§ Bounds on the objective
 

To complete the analysis of the problem we offer bounds on the objective,
which can be used to evaluate the quality of the solution obtained by any algorithm for the problem
at a given instance.
For this to be useful, the bounds need to be non-trivial and as close as possible to the optimal solution. 
We will first show how to obtain a lower bound on the second term of the objective, 
that is, ∑_,∈(,). 
We first introduce the following definition. 

 
Given two sequences of real numbers λ_1 ≥λ_2 ≥…≥λ_n and μ_1 ≥μ_2 ≥…≥μ_m,
with m<n, we say that the second sequence interlaces the first if  

    λ_i ≥μ_i ≥λ_n-m+i



We will employ the following result from Haemers <cit.>.



Let be a symmetric n× n matrix, and let be a principal submatrix of .
Then the eigenvalues of matrix interlace those of matrix .


We now state the following result.


Let be the pairwise distance matrix of facilities of an instance of problem.
Define matrix  so that _ij=√(_ij), that is, 
a matrix whose entries are the square roots of the entries of . Let λ_i() denote the i-th absolutely largest
eigenvalue of .
Then

    kλ_1() ≥∑_∈∑_∈(,) 
    ≥∑_i=n-k+1^n λ_i^2().



Recall that for any real symmetric matrix , 
_F^2=∑_iσ_i^2()=∑_iλ_i^2(). 
It is easily seen that if  is a binary vector with exactly k entries equal to 1, 
^T is equal to the sum of the entries of a k× k principal submatrix of , 
which is in turn equal to the squared Frobenius norm of the corresponding submatrix of . 
Combined with Lemma <ref>, this proves the lower bound.

The upper bound follows immediately from the variational characterization of the eigenvalues 
<cit.>.


A lower and upper bound on the first term of the objective can simply be given by 
∑_∈min_∈(,)
and
∑_∈max_∈(,),
respectively.
This is useful only for problem instances where the number of facilities is relatively small
compared to the number of clients.






§ THE LOCAL-SEARCH ALGORITHM



In this section we present the proposed algorithm for the problem
and state its properties. 
The algorithm uses the local-search strategy,  
proposed by Arya et al. <cit.>, 
but adapted for the objective function of . 
The algorithm starts with an arbitrary solution consisting of k selected facilities.
It then proceeds in iterations. 
In each iteration it considers whether it is possible to swap a selected facility
with a non-selected facility and obtain an improvement in the objective score. 
If such an improvement is possible, the corresponding swap is performed. 
The algorithm terminates when no such swap is possible.
At each point during its execution, 
the algorithm maintains a set of k clusters over the set of clients, and a selected facility for each cluster, 
defined by assigning each client to its closest selected facility. 
Pseudocode of this local-search procedure is given in Algorithm <ref>.




For the analysis 
we denote by ={_1,…,_k}⊆ 
the solution returned by , 
and ={_1,…,_k}⊆ 
an optimal solution. 
As mentioned before
we use the notation 
() to denote the set of clients that are assigned to facility in the solution , 
and 
() to denote the set of clients that are assigned to facility in the optimal solution . 

To analyze the performance of we follow the ideas of Arya et al. <cit.>.
The proofs are included in the Appendix.


A SKETCH OF THE PROOF IDEA HERE



As a result, in the case F=C, the algorithm yields a (λ k)-factor
approximation guarantee on the quality of the solution achieved. 




  
Let (,,k,λ) be an instance of the problem. 
Let be a solution returned by the algorithm, 
and let be an optimal solution. Then

    () ≤ 2(λ k+5) ().







Furthermore, we are able to improve the analysis 
and obtain an approximation guarantee that does not depend 
on the number of facilities k. 
For the improved result we need to make the mild assumption that
the number of clients in any cluster of the optimal solution and the solution
returned by the algorithm is Ω(λ k).
In particular, we have.


Let (,,k,λ) be an instance of the problem. 
Let be a solution returned by the algorithm, 
and let be an optimal solution.
Assume that 
|()| ≥⌈ 2λ⌉ k,
|()| ≥⌈ 2λ⌉ k
and
|()| = |()|
  for all ∈, ∈. 
Then

    () ≤max{11, 4λ} ().







Of particular interest is the case λ=1.


Let (F,C,k,1) be an instance of problem <ref>. Let
S={s_1, … s_k} be a solution output by algorithm
<ref> and let O={o_1, … o_k} be an optimal
solution. Assume |N_S(s)| ≥ 2k, |N_O(o)|≥ 2k
and |()| = |()|
for all ∈, ∈.
Then 

    (S) ≤ 11 (O)





The running time of the algorithm is ( k) per iteration. 
For most applications k is considered to be a constant. 
When the number of facilities is of the same order of magnitude with the number of clients , 
e.g., in the important special case =, 
the algorithm has quadratic complexity per iteration.
However, in many applications the number of facilities is significantly smaller than
the number of clients. Thus, we expect that the algorithm is very efficient in practice for those cases.

We also note that Arya et al. <cit.> show how to perform swaps of p facilities simultaneously
and obtain an improved performance guarantee at the expense of increased running time. 
In our case, the penalty term in our objective, 
which captures the disagreement among the cluster representatives, 
makes the analysis significantly more complex
and it is not clear how to use simultaneous swaps in order to 
achieve a similar quality-performance trade-off.
Thus, this direction is left for future work. 






§ EXPERIMENTAL EVALUATION



We perform experiments to assess the proposed concept of clustering with reconciliation of representatives, 
as well as the performance of the proposed algorithm.[Our implementation of the algorithm is available at <https://github.com/brunez/recon-kmedian-ls>]
Our objective is to evaluate by some objective measure 
whether the proposed problem formulation, as well as natural variations, 
can lead to a choice of representatives or sources that are more moderate, less polarizing and more likely 
to reach consensus.

To enrich the experimental setting and produce a more interesting set of empirical observations, we relax some of the requisites of our theoretical results. Namely, observe that in order to prove the approximation guarantees of the algorithm, we require that the distance function satisfy the properties of a metric, and that it be the same for facilities and clients. However, we believe that in practical scenarios, one might benefit from considering a wider set of options, especially if we consider the exploratory nature of clustering algorithms. Therefore, we measure dissimilarity between objects using functions that do not necessarily qualify as metrics, and we consider different ones for facilities and clients.

At a high level, our experimental methodology is as follows: 
We start with a dataset for which clients and facilities model a 
natural clustering problem and for which a distance function is available. 
For the facilities of the dataset we seek to obtain a polarity score π, 
which is independent of the distance function :
facilities with similar polarity scores π are more likely to agree. In addition, facilities with scores closer to the middle of the spectrum are less likely to disseminate extremist ideologies. 
We then apply our clustering algorithm with varying values of the parameters k and λ.
We are interested in answering the following questions:



  Q1.

How does the agreement between selected representatives or the polarization of information sources
(measured by the independent polarity score π) 
change as a function of λ? 
In other words, can we get more reconciled representatives or less extreme sources by increasing
the weight of the disagreement penalty term
(second term of the objective function (<ref>))?


  Q2.

How does the score change as a function of λ? 
In other words, can we find solutions with more reconciled representatives
but without significant loss in representation fidelity
(i.e., first term of the objective function (<ref>))?


  Q3.

What is the impact of the parameter k on both polarity score and score?





For our experimental evaluation we use the following datasets.[
The datasets are available at https://doi.org/10.5281/zenodo.2573954]

: The dataset, obtained by Lahoti et al. <cit.>,
consists of a set of politically active Twitter accounts. 
We remove stubs — i.e., accounts that follow only one account and have no followers — 
resulting in 3 302 362 accounts. 
Out of those we consider 500 popular ones — with at least 50 000 followers — 
as candidate facilities, that is, representatives. 
As remarked in the beginning of section <ref>, we can extend the proposed framework by considering different metrics for the two terms of the objective function. 
This corresponds to a practical setting where the agreeability of the selected representatives 
is measured differently than their affinity to their respective consituents. 
Specifically, for this dataset we consider the following distance functions.



  * Facility-Client:
We compute distances between facilities and clients
as the length of the shortest path between two Twitter 
accounts in the undirected follower Twitter graph.[The follower graph corresponds to a snapshot taken in July 2017.]


  * Facility-Facility:
To compute distances between facilities we use shortest-path distances, as before. 
We also use Euclidean distances on the spectral embedding with  components, 
as described by Belkin et al. <cit.>. 
We scale the resulting distance matrix so that the average of all entries is equal 
to that of the shortest-path distance matrix. 
This way we ensure that the magnitude of λ has an equivalent effect using the different metrics.



: We collect roll call voting records from the present US Congress 
using the public domain  API.[https://github.com/unitedstates/congress/wiki] 
We build a dataset where each row corresponds to a Congress representative 
and each column is a binary variable representing the issue being voted. 
Missing values are imputed using class-conditional means, 
where the classes we consider are the two parties: democrats and republicans. 
“Present” and “Not voting” votes are considered to be missing. 
We omit votes where all representatives are missing. 
We also omit representatives for whom we could not obtain an ideology estimate using the approach described below, 
or who missed too many votes. 
For this dataset, we use the Euclidean distance between the vectors
corresponding to each of the representatives. To make this experiment
closer to a plausible practical scenario, we restrict half of the
facilities to be democrats and the other half to be republicans. In
addition, clients are served by the closest facility of the same party.


:  We combined the domain-related data described in the work of Bakshy et al. <cit.> with the dataset. The set of facilities consisted of 469 domains hosting the news sources most often shared on the Facebook social network. The client set is comprised of 6 104 of the most politically active Twitter users. We consider two alternatives for computing the distances.



  * Mentions: Given a facility f and a client c, let n_cf be the number of times a tweet by c contains a link to f. Then d(f,c)=(n_cf + 1)^-1. To compute the pairwise distances between facilities we do the following. Consider two facilities, f and g. Let S_f (respectively S_g) be the set of clients that have tweeted a link to f (respectively g) at least once. 
We define W = ∑_c ∈ S_f∪ S_g ( log n_cf𝕀{c∈ S_f} + log n_cg𝕀{c∉ S_f} ), where 𝕀 is the indicator function. 
Then

    d(f,g) = 1-∑_c ∈ S_f∩ S_glog n_cf/W.

We define log 0=0. Since the objective function of (Equation (<ref>)) sums over all ordered pairs of facilities, this distance function is in effect symmetric when applied to our problem.
Note that this is akin to the Jaccard index for set similarity, but each element is weighted with a measure of its relevance.


  * Latent: We construct a matrix A such that A_ij is the number of times a tweet by user j contains a link to domain i. We compute the singular value decomposition A=UΣ V^T and extract the latent representation for both domains and users in the first 9 components (which account for 50% of the total Frobenius norm of A). If k=9, domain i is represented as U_i,:k and user j as V_i,:k. To compute both facility-facility and 
facility-client distances we take the Euclidean distances between the corresponding latent representations.


The characteristics of the datasets are summarized in Table <ref>.



For all datasets, in order to compute the objective of we take averages instead of the sums of distances. Note that this amounts to scaling both sums, so it is equivalent to setting λ to a particular value. The advantage of taking averages is that λ has an impact at small values, i.e., at “small” factors of 1.

Ground truth polarity scores (π). 
To measure the polarity scores of the facilities we employ different methods depending on the dataset.

In the case of and we use the approach described by Barberá <cit.>, 
which estimates the ideological leaning of a Twitter account as a real value. 
For , we use polarity scores collected at the same time as the follower graph (July 2017). 
For , we collected the ideological estimates in May 2018. 
Using this method and the proposed datasets, all the elicited polarity scores are between -3 and 3. 
We measure the polarity of the chosen representatives as follows. 
Given a solution ={_1, …, _k}, 
let π(_i) denote the estimated polarity of facility _i. 
We define the polarity of solution  as the sample standard deviation of the set 
{π(_1), …, π(_k)}.

For , we use the ideological leaning score associated to each domain as described in the work of Lahoti et al. <cit.>. These scores were computed roughly as the fraction of interactions (visits or shares) by conservative users, out of total interactions. We translated the scores so that they fall between -0.5 (left) and 0.5 (right). In this scenario, we are interested in choosing less polarized sources. We therefore measure the polarity of the chosen set as the ℓ-2 norm of the vector (π(_1), …, π(_k)).









Results on dataset.
We run the algorithm on the dataset setting the number of selected facilities to k=2,4,8 and 
λ=0,2^i/10 for i=1,…,6. 
For computing the pairwise distances between facilities we use either the shortest path metric 
or the spectral embedding with γ=k,10,100. 
Figure <ref> illustrates the results. 
We depict, as a function of λ, the polarity of the chosen representatives, 
measured as described above, along with the k-median cost of the solution — 
i.e., the first term of the objective function (<ref>).
We run the algorithm 40 times for each setting and report the average and standard deviation bands. 
We can see that increasing the value of λ leads to significantly less polarized representatives in various cases. 
The effect is most noticeable for larger values of k, and 
particularly consistent using the spectral embedding with 100 components. 
An interesting result on this dataset is that we can achieve significant decreases in polarity 
without incurring much additional k-median cost. That is, 
it is possible to elect a much more agreeable committee — with respect to the chosen polarity measure — 
without notable loss in representation fidelity.

Results on dataset.
We run the algorithm on the dataset, 
using the same configurations as for . 
Figure <ref> illustrates the results. 
Here, the decrease in polarity is only clear in the case k=2, for values of λ at least 0.8. 


It should be noted, however, that the voting data and the polarity scores come from completely different sources. 

It would therefore be interesting to carry out further experiments with these data.

Results on dataset.
We run the algorithm on the dataset, using the same configurations as for but considering k=16 as well, as in the case of news sources it is practical to consider larger sets. Figure <ref> shows the results, using the distance function defined in Equation (<ref>) (w-jaccard) and the latent representation (latent). We run each configuration 80 times and report average results and standard deviation bands. The reduction in polarity is noticeable, in particular using the latent representation with larger values of k. For very small sets of news sources (e.g., k=2) the method does not exhibit a reduction in polarity. In order to gain further insight on the impact of the penalty term, we report an example of the news sources that appear more frequently as λ increases. Specifically, we take a case where decrease in polarity is noticeable (latent, k=8, λ=0.8). We then collect the 16 sources that appear the most, and do the same for λ=0. The results are shown in Table <ref>. For each domain, we report the frequency (i.e., the fraction of times it was part of the solution out of the 80 runs), the ideological score and the number of times it was mentioned in the collected tweets.










Number of iterations.
Even though the time complexity of the local-search algorithm per iteration 
is not too high, a legitimate concern to be raised is the possibility that
it might require a large number of iterations to converge. 
Our observations, however, suggest that in practice a small number of
iterations — where by iteration we understand the inspection of all
candidate changes — are necessary. Table <ref> shows
the average and maximum number of iterations for the dataset. 






§ CONCLUSIONS



We have considered the problem clustering data
so as to optimize the total representation cost
plus an additive term to penalize disagreement among the chosen representatives.
The proposed problem, which we name reconciliation , 
has applications in summarizing data with non-polarized representatives, 
as well as in electing k-member committees that are more likely to reach consensus. 
We have shown the proposed problem to be -hard and derived bounds on the objective.
Inspired by the literature on related problems, we have analyzed a
local-search algorithm in this context and derived approximation guarantees, 
of factor (λ k) in the general setting, and constant under mild assumptions. 
Through experiments on real data coming from a social network and voting records, we have shown
empirically how the proposed formulation can lead to the choice of less polarized groups of
representatives, as measured by a well-known method for ideology estimation, as well as less ideologically-extreme sets of news sources. 
This work opens various enticing directions for future inquiry. 
First it would be interesting to determine whether the
approximation guarantees can be improved, as well as to attempt to
find tight examples to know the possible extent of said improvement.
Second, it would be interesting to perform further experiments on
similar and other datasets. It is particularly compelling to
improve our understanding of how different metrics can interact with known
methods for estimating polarization. 


Acknowledgements. This work was supported by
three Academy of Finland projects  (286211, 313927, and 317085), 
and the EC H2020 RIA project “SoBigData” (654024).



§ APPENDIX



 §.§ Hardness results

Here we prove Lemma <ref>, 
which is a key ingredient of the proof of hardness for . 
Before we proceed, we provide a definition of Densest k-subgraph, 
a well-known -hard optimization problem which we employ in our reduction.
(densest k-subgraph — )
 
Given a simple graph G=(V,E) with |V|=n and adjacency matrix A, 
and a number k∈ℕ with k < n, find 

    min_     ^T , 
         ∈{0,1}^n  ^T=k.



We can now prove the aforementioned lemma.


We proceed by reduction from Densest k-subgraph ().

Consider an instance of , G=(V,E), |V|=n with adjacency matrix A. We define a matrix Ã as follows:

    Ã_ij =  
        
          A_ij    (i,j) ∈ E 
    
          0     i=j 
    
          2    .

Notice that this matrix is symmetric, the diagonal (and nothing else) is zero, and since min_i≠ jÃ_ij=1 and max_i≠ jÃ_ij=2, for all i, j, and ℓ

    Ã_ij≤Ã_i,ℓ+Ã_ℓ,j.


We want to show that if

    =_∈{0,1}^n
    ^T =k^TÃ ,

then

    =_∈{0,1}^n
    ^T =k^TA .


We can write 

    ^T Ã =∑_i∑_jÃ_ij𝕀{x_i=x_j=1} = M+2N,

 where we have defined

    M=| {(i,j) | x_i=x_j=1 }∩ E |,    
     N=| {(i,j) | x_i=x_j=1 }∩E̅ |.

That is, M is the number of pairs in  with a corresponding edge in G, and N is the number of pairs in  without a corresponding edge in G. 

Similarly, 

    ^T A =∑_i∑_j A_ij𝕀{x_i=x_j=1} = M.




Furthermore, note that M+N=2k  2=k^2-k.

It follows that for all vectors ∈{0,1}^n, with ^T=k, it is

    ^T Ã  = -^T A  +2(k^2-k).


Since 2(k^2-k) is a constant, it follows that a vector ∈{0,1}^n, with  ^T=k,
minimizes ^T Ã (the objective)
if and only if it maximizes   ^T A (the objective).

Suppose  minimizes but it does not maximize . 
Then for some ', 

    '^T A ' > ^TA ,

which implies

    M'>M,

or

    '^TÃ ' = M'+2N' < M+2N = ^T Ã .

This contradicts the initial assumptions, hence if  minimizes ,  maximizes .




 §.§ Approximation guarantees

Given a set of clients C, a set of facilities F, and any subset of facilities S⊆ F, 
we employ the following notation:



  – f(S)=∑_x∈ Cd(x,s(x)), where s(x) is the facility in S assigned to client x∈ C;


  –  g(S)=1/2∑_x∈ S∑_y∈ Sd(x,y);


  –  (s) is the set of clients served by facility s in S.




  – f(S)=∑_x∈ Cd(x,s(x)), where s(x) is the facility assigned to client x.

  – g(S)=1/2∑_x∈ S∑_y∈ Sd(x,y)

  – (s) is the set of clients served by facility s in solution S.



We rely on the following crucial facts. First, a result from the work of Arya et al. <cit.>.

  
Let O be an optimal set of k facilities and  S an arbitrary set of k facilities. There exists a set of k pairs 
Σ = {(o_i,s_j)| i,j ∈ [k]}⊆ O× S  satisfying the following properties:


  * Every o∈ O is considered in exactly one pair.


  * Every s ∈ S is considered in at most two pairs.


  * We can choose the set of pairs Σ such that the following inequality holds:

    5f(O) - f(S) ≥∑_(o_i,s_j)∈Σ ( f(S-s_j+o_i) - f(S)  ).



  

Second, by definition of local optimality, 
for a locally optimal solution ={s_1, …, s_k} and an optimal solution ={o_1, …, o_k}, we have

    f(S-s_j+o_i) + λ g(S-s_j+o_i) ≥  f(S) + λ g(S),

for any i,j ∈ [k]. 

We now have the ingredients for the proof of Theorem <ref>, from Section <ref>.


Since  and -s_j+o_i differ in one facility only,
we have

    g(-s_j+o_i)-     g() 
        = 1/2∑_x ∈-s_j+o_i∑_y ∈-s_j+o_id(x,y) - 1/2∑_x ∈∑_y ∈d(x,y) 
        = ∑_s∈
     s≠ s_jd(o_i,s) - ∑_s ∈d(s,s_j).


We consider a set of pairs Σ satisfying the properties of lemma <ref>. Summing the above difference over all k pairs we get

    ∑_(o_i, s_j)∈Σ (g(    -s_j+o_i)- g()) 
        = ∑_(o_i, s_j)∈Σ (∑_s∈
     s≠ s_jd(o_i,s) - ∑_s ∈d(s,s_j)  ).


Therefore, summing inequality (<ref>) over all pairs in Σ we get

    ∑_(o_i,s_j)∈Σ ( f(-s_j+o_i) - f()  )
    
       +λ∑_(o_i, s_j)∈Σ∑_s∈
     s≠ s_jd(o_i,s) - λ∑_(o_i, s_j)∈Σ∑_s ∈d(s_j,s)≥ 0,


and using inequality (<ref>) and rearranging we obtain

    5f() + λ∑_(o_i, s_j)∈Σ∑_s∈
     s≠ s_jd(o_i,s) ≥ f() + λ∑_(o_i, s_j)∈Σ∑_s ∈d(s_j,s).



We consider this inequality, and modify it so that it becomes dependent only on factors of f(), g(), f(), g(). To accomplish this, we will consider the set of pairs Σ.

First, let us examine the following quantity:

    ∑_(o_i,s_j)∈Σ∑_s∈
     s≠ s_jd(o_i,s).


For each term d(o_i, s), s∈, (o_i,s_j)∈Σ, we consider three cases:


  * s∈. Then d(o_i,s) ≤ g().

  * s ∉ and s ∈ N_(o_i). Then d(o_i,s) ≤ f().

  * s ∉ and s ∉ N_(o_i). Then d(o_i, s) ≤ d(o_i, o_j) + d(o_j, s), where s∈ N_(o_j), and thus d(o_i,s) ≤ f() + g().

Now, consider the sum ∑_(o_i,s_j)∈Σ∑_s∈
 s≠ s_jd(o_i,s)
and observe that


  * for every i, o_i is in k-1 terms of the sum;

  * for every j, s_j is in at most k terms of the sum.


Thus, 

    ∑_(o_i,s_j)∈Σ∑_s∈
     s≠ s_jd(o_i,s) ≤  k(g() + f()).



  We now examine the quantity 

    ∑_(o_i,s_j)∈Σ∑_s ∈d(s_j,s).





In particular, we will show that

    2∑_(o_i, s_j)∈Σ∑_s ∈d(s_j,s) ≥ g().


We consider the set P⊆ of facilities in some swap, i.e.,
 P={
s∈ such that (o,s)∈Σ for some o∈
 }. 
For any facility  s∈ P, 
note that all the entries from g() that involve terms d(s,s') are present in
expression (<ref>), and so we can trivially bound them.

Thus, we can assume that k is even and |P|=k/2, that is, all
facilities in  either are in two swaps from Σ, or in no
swaps at all.
We number the facilities in P 1 through k/2, and the rest
k/2+1 through k.

We bound each term of g()
corresponding to facilities i,j not in P, i<j as

    d(i,j) ≤ d(i,j-i) + d(j-i,j).

Note we can bound all such terms this way, with each term in the upper
bound appearing at most twice, and being part of the sum in expression (<ref>). Thus, we get inequality (<ref>).



Now, consider inequality (<ref>), and apply inequalities (<ref>) and (<ref>). We obtain

    2(5f() + λ k(g() + f())) ≥ f() + λ g().





We consider inequality (<ref>), and modify it so that it becomes dependent only on factors of f(O), g(O), f(S), g(S). To accomplish this, we will consider the set of pairs Σ.

First, let us examine the following quantity:

    ∑_(o_i,s_j)∈Σ∑_s∈ S
     s≠ s_jd(o_i,s).


By the triangle inequality, we have that the sum corresponding to each pair (o_i,s_j)∈Σ is bounded as follows:

    ∑_s∈ S
     s≠  s_jd(o_i,s)    ≤∑_s∈ S
     s≠  s_jd(o_i,o_h_s) + d(o_h_s,x) + d(x,s),

where o_h_s is such that (o_h_s)∩(s)≠∅ and x ∈(o_h_s)∩(s). If (s)⊆(o_i), we consider  d(o_i,s) ≤ d(o_i,o_h_s) + d(o_i,x) + d(x,s), choosing o_h_s as described below.







For notational convenience, we define 

    σ(o_i)    = ∑_s∈ S
     s≠  s_j d(o_i,o_h_s) + d(o_h_s,x) + d(x,s),

for each (o_i,s_j)∈Σ —
note that each o_i appears exactly
once in the pairs in the set Σ, so the pair (o_i,s_j) is
uniquely determined by o_i.

We want to choose the entries of inequality (<ref>) such that


  - every term of the form d(o_i,o_h_s) appears at most twice; 

  - every term of the form d(o_h_s,x) appears once;  

  - every term of the form d(x,s) appears once. 
 

To achieve this, we need a set of replacements such that for each σ(o_i), the k-1 corresponding replacements contain k-1 distinct entries of the forms d(o_i,o_h_s), d(o_h_s, x), d(x, s). 


We define a function μ that maps each x∈ C to a pair (o_i,s_j)∈× 
such that x∈(s_j)∩(o_i).  
Since |(s_i)|≥ k,
  |(o_i)|≥ k and |(s)| =
|(o)| for all s∈, o ∈,  
we can choose a subset C̃⊆ C of k^2 points such that each s ∈
  S, as well as each o ∈ O, appears in k of the k^2 pairs
  associated to the chosen points.

We now argue that said choice is indeed possible.

Consider a bipartite multigraph, where the vertices of each partition
correspond to the facilities in S and O, respectively. We add an
edge between s and o for each client served by the two facilities
in the corresponding solution.

That we can pick these k^2 clients satisfactorily follows from the
fact that every regular bipartite multigraph is
1-factorable <cit.>.

We can now conclude that 


  - every element of the form d(o_i, o_j) can only appear either in σ(o_i) or in σ(o_j). Since for all σ(o_i), the entry d(o_i, o_j) is unique, each d(o_i, o_j) appears at most twice;

  - for any element of the form d(o, x), o∈ O, x is unique;

  - for any element of the form d(s, x), s∈ S, x is unique.


We have established the following inequality

    ∑_(o_i, s_j)∈Σ∑_s∈ S
     s≠  s_jd(o_i,s) ≤ 2g(O) + f(O) + f(S).


Considering each cluster in both S and O to have at least ⌈ 2λ⌉ k points, we can extend the result to account for λ. To do this, we repeat the above choice of clients ⌈ 2λ⌉ times  and obtain

    2λ∑_(o_i, s_j)∈Σ∑_s∈ S
     s≠  s_jd(o_i,s) ≤ 4λ g(O) + f(O) + f(S).

To see this, note that for every entry of the form d(o, x) or d(s, x), x can still be chosen to be unique. 



Now, consider inequality (<ref>) again. Multiplying it by 2 we get

    10f(O) + 2λ∑_(o_i, s_j)∈Σ∑_s∈ S
     s≠ s_jd(o_i,s) ≥ 2f(S) + 2λ∑_(o_i, s_j)∈Σ∑_s ∈ Sd(s_j,s).

By inequalities (<ref>) and (<ref>) we obtain the following:

    10f(O) + 4λ g(O) + f(O) + f(S) ≥ 2f(S) + λ g(S)
      
       ⇒  10f(O) + 4λ g(O) + f(O) ≥ f(S) + λ g(S)
      
       ⇒  11f(O) + 4λ g(O) ≥ f(S) + λ g(S).

Therefore, 

    max{11,4λ}cost(O) ≥  cost(S). *







ACM-Reference-Format



