Minimizing Polarization and Disagreement in Social Networks via Link Recommendation
Authors: Liwang Zhu
Qi Bao
Zhongzhi Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Opinion dynamics
social network
graph algorithm
discrete optimization

Abstract: Individual's opinions are fundamentally shaped  and evolved by their interactions with other people, and social phenomena such as disagreement and polarization are now tightly woven into daily life. The quantification and optimization of these concepts have been the subject of much recent research behind a wealth of high-impact data mining applications. In particular, researchers have addressed the question of how such concepts can be optimized by influencing the opinion of a small number of individuals or by designing the network from scratch.

Here, rather than  a “design-from-scratch” approach or altering the initial opinion, we study the optimization problem of recommending $k$ new links to minimize the sum of polarization and disagreement in a social network with $n$ nodes and $m$ edges.  We show that our objective function of this combinatorial optimization problem is not submodular, although it is monotone. We propose a simple greedy algorithm with a constant-factor approximation that  solves the problem in cubic running time, and we provide  theoretical analysis of the approximation guarantee for the algorithm. To overcome the computation challenge for large networks, we also provide a fast algorithm with computation complexity $\Otil (mk\eps^{-2})$ for any $\eps>0$,  where the $\Otil (\cdot)$ notation suppresses the ${\rm poly} (\log n)$ factors. Extensive experiments on real datasets demonstrate both the efficiency and effectiveness of our algorithms.

Minimizing Polarization and Disagreement in Social Networks via Link Recommendation
Liwang Zhu, Qi Bao, and Zhongzhi Zhang" Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai, China School of Computer Science, Fudan University, Shanghai 200433, China {19210240147, 20110240002, zhangzz) @ddann. cn
Abstract
Individual's opinions are fundamentally shaped and evolved by their interactions with other people, and social phenomena such as disagreement and polarization are now tightly woven into daily life. The quantification and optimization of these concepts have been the subject of much recent research behind a wealth high-impact data mining applications. In particular, researchers have addressed the question how such concepts can be optimized by influencing the opinion of a small number of individuals by designing the network from scratch.
Here, rather than "design-from- from--frrrmaach approach or altering the initial opinion, we study the optimization problem of recommending k new links to minimize the sum of polarization and disagreement in a social network with nodes and edges. We show that our objective function of this combinatorial optimization problem not submodular, although it is monotone. We propose a simple greedy algorithm with a constant-factor approximation that solves the problem in cubic running time, and we provide theoretical analysis of the approximation guarantee for the algorithm. To overcome the computation challenge for large networks, also provide fast algorithm with computation complexity O(mke for any > O, where the (.)) notation suppresses the poly n) factors. Extensive experiments on real datasets demonstrate both the efficiency and effectiveness of our algorithms.
Introduction
Social networks and social media play prominent part in the propagation, evolution, and formu- lation of opinions [32], leading to fundamental changes how humans share and shape opinions. Particularly, in recent years, the tremendous prevalence of online social media platforms produces various social phenomena, such as polarization and disagreement. The identification (48) and opti- mization (50) of these quantities are fundamental tasks behind a myriad of high-impact data mining applications, and thus have received considerable attention.
We focus the phenomena of disagreement and polarization. Disagreement [39] [6] characterizes how much acquaintances disagree in their opinions, globally across the network. Polarization B9 measures how equilibrium expressed opinions deviate from their average. However, existing recommender systems, trained on real-data, with the goal to increase user engagement may stop the user from being exposed diverse opinions and naturally end up creating "echo-chambers" In other words, the recommended links minimizing disagreement may lead to greater polarization [39] since connections between users with similar mindsets preferred for such systems. Yet, exposure to diverse content is necessary to obtain a complete picture about topic 27]. Thus, there is need
36 16
"Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

for a radically different approach to suggest links that decrease both disagreement and polarization, which motivates our work.
In this paper, we address the following optimization problem: given a social network with n. nodes and m edges, and an integer k, how to strategically recommend k links to the individuals so that the polarization and disagreement is minimized. We show that our objective function of this combinatorial optimization problem is not submodular, although it is monotone. To tackle the exponential computation complexity, we resort to greedy algorithm extended for non-submodular function [5] by iteratively adding the most promising edges. We propose simple greedy algorithm with a constant-factor approximation that solves the problem in cubic running time. To confront the computation challenge for large networks, we also provide fast algorithm with computation complexity Ō(mke ²) for any e > O, where e > 0 is the error parameter and the Ō(-) notation suppresses the poly(log n) factors. We confirm our theoretical and algorithmic performance by executing extensive experiments on various real networks, which show that our algorithms are efficient and effective, outperforming several other strategies of creating edges.
Omitted proofs and implementation are provided as supplementary material.
2
Related work
We review the related literature from the following three perspectives, including modeling opinion dynamics, optimization problems in opinion dynamics, and link recommendation strategies.
Modeling opinion dynamics. Opinion dynamics has been the subject of intense recent research to
model social learning processes in various disciplines [29] 19. These models capture the mecha- nisms and factors influencing opinion formulation, shedding light on understanding the whole process of opinion shaping and diverse phenomena taking place in social media. In the past decades, numer- ous relevant models have been proposed [40). among which the Friedkin-Johnsen (FJ) model (20 is one of the most popular models. After its establishment, the FJ model has been extended in a variety by incorporating different factors affecting opinion dynamics, such as peer pressure 42 susceptibility to persuasion [.] and opinion leader (25). Under the formalism of the FJ model or its variants, some relevant quantities, properties and explanations have been broadly studied, including the equilibrium expressed opinions [18 6 sufficient condition for the stability [1], the average initial opinion [8)) interpretations (24 and on.
of ways 29 28
Optimization problems in opinion dynamics. Recently, several optimization problems related to opinion dynamics have been formulated and studied for different objectives. For example, long line of work has been devoted to maximizing the overall opinion by using different strategies, such as identifying fixed number of individuals and setting their expressed opinions
[25), changing agent's internal opinions 449 47. as well as modifying individuals' susceptibility to persuasion ①
[46] studies the problem of allocating seed users opposing campaigns with a goal to maximize the expected number of users who are co-exposed to both campaigns. In additon, (23) studies the problem of balancing the information exposure. These studies have far-reaching implications in product marketing, public health campaigns, and political candidates. Another major and increas- ingly important focus of research optimizing some social phenomena, such as maximizing the diversity [35 37 minimizing conflict [12), disagreement [21]. and polarization (36). A recent work considers the problem of minimizing the sum of polarization and disagreement by changing the underlying network topology
[39]. Different from the flesign-from-seracch approach, we instead concentrate on edge recommendation, a practical incremental approach that suggests modifications to an existing network to achiever our goal. Moreover, our proposed algorithms differ significantly from existing ones, in spite of the fact that our objective function is identical to that in [39].
Link recommendation strategies. Our problem aims to optimize an objective via link recommenda- tion. Here, we review some instances of related edge recommendation problems. [ 43 17] improve the centrality of a node and (3] strategically fight opinion control in social networks. As for opinion dynamies, the operation of creating edges is actually convenient and practical, which is equivalent to making friendship between individuals. In (22). the edge addition strategy is explored on the endorsement graph, with an aim to reduce controversy, and it also takes account of the acceptable probability of the recommended edge. In (6), addition of edges is discussed in order to reduce the social cost, namely the lack of agreement. Finally, [12] exploits link recommendation strategy to reduce the risk of conflict. (27) considers link insertions to reduce structural bias which may trap
2

---

reader in "polarized" bubble with no access to other opinions. Our work is motivated in part by these studies, while we address new optimization problem, and present two new algorithms, with the faster one being nearly linear.
Preliminaries
In this section, we give a brief introduction to some essential concepts and tools, in order to facilitate the description of the studied problem and its related greedy algorithms.
Graph and Related Matrix. Let G = (V, E) be a connected undirected simple graph (network) edges. The adjacency relation of all nodes in G is encoded in its adjacency matrix = (a:z) nxn- nodes and j are adjacent by an edge e, then day = aj = 1; dzj djz = 0 otherwise. Let N₂ be the set of neighbours of node satisfying N; {ilti,}} E E). Then, the degree d of node is de = Dj= Oij JjEN, aij. and the diagonal degree matrix of G is
with [ nodes and E|
defined as D = diag(d, (d1 .2,...,d,))
The Laplacian matrix of G is defined to be == D A. There is also alternative construction of L by using the incidence matrix B E RI an m signed edge-node incidence matrix. The element bee. e E E and U V. of B is defined as follows: bee = 1 if node is the head of edge e, bew = -1 if node v is the tail of edge e, and beb = 0 otherwise. For edge E with two end nodes and j. the row vector of B corresponding e, denotes the i-th standard basis vector of appropriate dimension. Then the Laplacian matrix L of g can also be represented as B B, which indicates that L is symmetric and positive semidefinite. Moreover, the Laplacian matrix L of connected graph G has unique zero eigenvalue.
can be written as bij be e; ej where
Let < A S X2 S .... S An-1 be the nonzero eigenvalues of of a connected graph G. and u; be the corresponding orthonormal eigenvectors. Then, L has an eigendecomposition of form == UAUT = =E X.u,u, where A = diag (0, Aı, X2 An-1) and u, is the i-th column of matrix U. Let Amax and Amin be, respectively, the maximum and nonzero minimum eigenvalue of Then, Amax An-1 S 455, and Amin \ 1/n2 (4].
The forest matrix of graph doubly stochastic matrix [0] satisfying R1 and 1 1 1 where denotes the all-ones vector. For pair of nodes and j. their forest distance riy is defined as rty b.j.bb... obeying relation 0 S riy 2.
defined Ω (1 + L) 11 (Wrz) nxn 26 Matrix Q is
Greedy Algorithms for Non-Submodular Functions. For submodular maximization problems, the greedy algorithm has become prevalent choice for solving them with a guaranteed (1 1/e) approximation ratio. However, there a large class of important set functions optimization in network topology design fail to be submodular. To alleviate this issue, a generalized approximation ratio has been proved and further provides a performance guarantee for non-submodular functions based on two quantities: submodularity ratio and curvature a, which characterize how close these functions are from being sub- or supermodular (5).
For consistency, we first give the definitions of submodular ratio and curvature below. We use (W) def f(TUW) f(W) to denote the marginal benefit of the set T S X with respect the set W C.
Definition 3.1 (Submodular Ratio (5)) The submodular ratio of a nonnegative set function f is the largest y E IR, such that for any subset W.T C X, Eiewer (T) 2 7Pw (T).
Definition 3.2 (Curvature (5) The curvature of a nonnegative set function f is the smallest a E R. such that for any subset W.T X and any element j T, it follows that Pj (T N W) 2
(1 - (L-a)p,(T)
Notice that for a non-decreasing function f, follows that its submodular ratio 7 E [0, 1] and 7 = if and only if f is submodular function; and its curvature [0, and a = if and only if ʃ is supermodular function. Given those two quantities, the greedy algorithm enjoys a tight approximation guarantee of (1 - e77 for larger class of optimization problems [5].
3

---

Problem Formulation
In this section, briefly discuss the FJ model of opinion formation, well the definitions and measures for disagreement and polarization. Then we formally introduce the problem for optimizing the polaarizatonn-disggreemenn index in social network.
Friedkin-Johuss Model. The FJ model is one of the most popular models for opinion dynamics 20] In the FJ model, each node i V has two opinions: internal (or innate) opinion and the expressed opinion, both in the interval [0, 1]. The internal opinion for each node, denoted by 8,, remains unchanged. Let (t) be the expressed opinion of node at time which evolves as
81 + EjEN. aijzz(!) 2t+
(1)
+ 1+E JJEN, Oij
Let (81, .2,.... sn)
be the initial opinion vector. Let (21. 22. rium expressed opinion vector, which can be represented as z = Zs [6]
2n) T be the equilib-
In the FJ model, individuals interact with their acquaintances and exchange opinions whereas the opinions of nodes often not reach consensus, leading to disagreement, polarization and other important phenomena, which have been the subject of many recent works. In this paper, we study the disagreement and polarization using definitions given in (39]
For a graph G = EV) with expressed opinion vector its disagreement D(G) is defined as D Eu.jee (2:))) Let be the mean-centered equilibrium vector given by
111 x Then the polarization P(g) is defined as: P(g) Eiev . z We further introduce the Eitarizationddisagreemnn
(P-D) index, i.e., the objective we are concerned with. For a graph g = (V. E) with expressed opinion vector the ceariiatioondisagreemnn index I(g) is the sum of the polarization P(g) and disagreement D(g): I(g) P(g)= + D(g). Convenient matrix-vector expressions for the above quantities are provided by the following proposition [12 39 48).
Proposition 1 D(G). P(g) and [() can be conveniently expressed in terms of quadratic forms as N.LRs
D(g) = Lz = z
Lz = T
P(g) _ z = n
I(g) = Lz z [2..
Remark 1 In this paper, will generally assume that the internal opinions are mean-centered, that is, 8. Note that in such case, z will also be mean-centered. In fact, as will be shown in supplementary material, whether the opinions
mean-centered or not, the edges which select to augment the network are the same since the variation of our objective remains unchanged.
Formulation of Problem. Our problem is based on the following fact. For connected undirected network GVV E), if we augment the network by adding the edges in set T, which is subset of the candidate edge set Ec consisting of specified nonexistent edges, the P-D index of the new graph will not increase. In our subsequent analysis, we will use the following notation to improve readability of lemmas. We use g + T to denote the graph augmented by adding the edges in T, that is + T = (V, E T). To evaluate the variation of the P-D index when adding edges, we define an objective function on the edge set f E + R4 as
f(T) I I
in the sequel, we will use f(e) and g + c, respectively, to denote f(e]) and g + {e} for simplicity. The variation of the P-D index under the perturbation of single edge can be expressed by the following lemma.
Lemma 4.1 For candidate edge e E Ec connecting node u and e with row vector b. = eu, e one obtains
f(e) = 8 T2b.. b. Ss
(z, z, 2 0.
(3)
1 b._ 52b
1 Tuv
Lemma indicates that the addition of any nonexisting edge can reduce the P-D index. Then the following problem arises naturally: given candidate edge set Ec. how to optimally select

---

subset T of Ec subject to cardinality constraint, so that the polarization-disaeee disagreement index of the new graph is minimized. Such an optimization problem has been the subject of many recent papers [2 39 Yet we focus on edge recommendation rather than global structural results due to the following reasons: in practice, graph edits can typically be made only in small amounts, either because of budget constraints, or because of practical considerations. A similar idea was previously used in [2]. We now give a mathematical formulation of Problem I in a formal way as follows.
Problem 1 Given connected graph G = EV, an integer k, a candidate edge set Ee consisting of nonexistent edges, find a subset T C Ec with [T] = k, and add them to 9 forming a new graph G+T T = (V, T)), so that the polarization-disgrrennt TTG+T).
index I(g + T) is minimized. That is:
minimize TCEc, 12
(4)
SPGREEDY: Simple Greedy Algorithm
In this section, we first study the characterization of our problem, and then propose simple greedy algorithm, followed by some analysis in terms of the approximation guarantee.
Problem Characterization. We start with detailing the theoretic challenges of Problem [ The complexity of Problem comes along two dimensions--earcching for the best edge subset delivering the maximum of the objective, and assessing the impact of a given subset of edges upon the objective. The former is inherently a combinatorial problem, which is computationally infeasible to solve in a naïve brute-force manner while the latter involves cubic-time matrix inversion. To be specific, for each augmented edge set T coming from ((Ecl) possible subsets, need to compute the P-D index of the resultant graph, yielding an exponential complexity O((1Ecl) .n²).
k
To tackle the exponential complexity, we resort to a greedy heuristic. Firstly, the objective function is monotone respect to the edge set T. as we mentioned in Lemma 4.1 But, we show that, unlike in the case in other standard optimization settings, neither submodularity nor supermodularity holds for our objective function. We present above results in the following theorem.
The function f(T) defined above is non-submodular monotonically increasing function of the edge set T.
Theorem 5.1
Thanks to the empirical success of applying greedy strategy on a significantly larger class of non- submodular functions [5) in spite of the -on-submodularity of our objective f(T), the greedy algorithm can still become a proper choice for solving Problem discussed in the next subsection.
[ the details of which will be
Simple Greedy Algorithm. Our simple greedy algorithm, denoted as SPGREEDY, exploits the performance guarantee for non-submodular functions. The general approach is as follows. We will first assess candidate edges with respect to how much their addition to the network decreases the term I()). and then iteratively add the most promising edges to the network until budget is reached.
The augmented edge set T is initialized with an empty set. Then i edges are iteratively selected to the augmented edge set from set Ec \T. At each iteration of the greedy algorithm, the edge in candidate set is chosen that gives the largest marginal gain fe). The algorithm stops until & edges are selected to be added to T. The naive greedy algorithm takes time O(k: Ec|nE)) which is computationally intractable even for small-size networks. Actually, as shown in the proof of Lemma 4.1] with Ω already computed, we can view the addition of single edge e as a rank-1 update to the original matrix Ω2 which can be calculated in time O(n2) by using Sherman-Morrise formula 38 instead of inverting the matrix again in O(n") in each loop.
The above analysis leads to simple greedy algorithm SPGREEDY((, Ec, k, s), which is outlined in Algorithm| [] To begin with, this algorithm requires Onn²) time to compute the inverse of I + L, and then it performs in rounds, with each round mainly including two steps: computing f(e) (Line 4) in O(EEc|n) time, and updating Z2 (Line 8) in (n?) time. Thus, the total running time of Algorithm ] is O + +|EEol??) which is much faster than the naïve algorithm.
Approximation Guarantee. As we mentioned before, the performance of the greedy algorithm for non-submodular function can be evaluated by its submodularity ratio 7 and curvature a. Hence, we derive the bounds for these two quantitics of our Problem I
5

---

Algorithm 1: SPGREEDY (G, Ec, k)
Input A connected graph 9: a candidate edge set Ec; an integer k: Σ EEc: an initial opinion
vector s
Output A subset of C Eg and [T'] = =k
Initialize solution T =
2 Compute !
for i to do
Compute f(e) for each E Ec T
Select e, s.t. 6 + arg max,e Eo ET f(e) Update solution T + (eee Update the graph G + G(V, (U
Update 5 Ω 1+6 f2b.
return T
Lemma 5.1 Let (L) be the smallest non-zero eigenvalue of Laplacian matrix L for graph g, and
let (L=)( be the largest eigenvalue of Laplacian matrix LEc: for the augmented graph 9 + Ec.
Then, the submodularity ratio Y of set function f(T) I(g) I(g T) is bounded by 1 7 2
1+)1(L) 2
2
>
O, and its curvature a is bounded by < a S 1
(I+An-1(bEc)
(+)
<
Lemma 5.1] together with the approximation guarantee stated before, yields performance analysis for the greedy algorithm. As will be shown in the Experiment Section, the greedy algorithm has been shown perform very close the optimal solutions for our problem in the experimental aspect.
6 FASTGREEDY: Fast Greedy Algorithm
Compared with the naïve algorithm, computation time of Algorithm | is significantly reduced. However, it is still computationally unacceptable when employed on large networks with millions of vertices. In this section, we address this challenge by presenting an efficient approximation algorithm, solving the problem in time Omme
The step for solving Problem is to calculate the impact of each edge upon the objective i.e., (e). According to 33) to evaluate f'(),, we need estimate two terms R2b.b _ f2s and _ Rb.. We will show how to approximate these two quantities in nearly linear time using Johnson- Lindenstrauss (JL) Lemma (30 2 and Fast SDDM (symmetric, diagonally eisomaalyydominant M-matrix) Solvers[44]. Moreover, the results returned by our algorithm are demonstrated to provide proper approximations to f(c).
Lemma 6.1 (JL Lemma 30) Given fixed vectors U1, ........ Un E Rdd and real number > O. Let p be a positive integer such that p 24 log n/e2 and Rpxd a random matrix with each entry being 1/ v/ or - vp with identical probability Then, with probability at least 1 - 1/n, the following statement holds for any pair i and j. 1 1 i, $ n.
(1=
12 <
RR; Rv (1 + +c)lo u,112
Lemma 6.2 (Fast SDDM Solver 44
There is a nearly linear time solver y = SOLVE(S, b,
which takes an SDDM matrix S Saxp with m. nonzero entries, vector b E R.". and an error
S 61|s-i blis with high parameter 8 > 0, and returns a vector x E I2 satisfying ly S S
probability, where |yl| def V Sy. The solver runs in expected time Õ(m).
We first approximate the term b 12b. in the denominator of 3). which can be written b l2b b._ S(T LySbb. = b__ 2 I + B B lb. || 1l In this way, we have reduced the estimation of the denominator of (3) to the calculation of the quadratic form of BΩb 1| and ||2bbl] 2|2 in m and TR. To reduce the computation cost, we will apply the lemma to reduce the dimensions. Let Q pxm and P pxn be two random +1/ matrices where p will be decided later,

---

then we can simply project matrices BΩ and Ω onto low-dimensional subspace QBQ and PΩ, However, this still does help reduce the computation time, since direct computation of the above & norm involves matrix inversion, leading running time of O(n)). In order to avoid inverting matrix + L, we will utilize the fast SDDM linear system solvers to approximate the above two terms.
Let X QB, BR, QX, let X, SOLVE + L, (1)), satisfying |
c 22112
1 S 6, X r with 61 <
32n(n++1) 32 (1+e//22((+)) Making use of Lemmas 6.1 and 6.2
the term Q 1 can be efficiently approximated as stated in the following lemma.
Lemma 6.3 Given an undirected graph 9 = (V, E) with Laplacian matrix L, a parameters e (0,
then, the following relation holds:
(1 12
X b.
S X ball S $11 12 11
(5)
In similar way, let Y = P.Y Ω Y' = PY, let Y, SOLVE(I I + L, Y., .2) with 2/111=112)
52 S 32(x+1)v (1+e/12)(+)) Then, the following lemma holds, giving an efficient approximation to
Lemma 6.4 Given undirected graph (V, E) with Laplacian matrix L, parameter (0, 2) then, the following relation holds:
)²2 ) < Y bell s (1+
C 5
(6)
12
12
Having Lemma 6.3 satisfying
6.4 the term b Sbb. can be efficiently approximated by |Xb.ll Y b.12
(1 3 T66. S 1 + /. b. < (1 ( 32be.
E
+
We continue to approximate the numerator of f((), which can be written as | We will use the fast SDDM matrix solver again approximate this term.
Lemma 6.5 Given an undirected graph (V, E) with Laplacian matrix and forest matrix St parameter E (0, 1) and the internal opinion vector s let q SOLVE
(I I + L, 8, 6g), where
5y 9m2- Then, the following relation holds: ||911b.00 [1sss
Algorithm 2: COMP Ec, s,c)
Input A graph G; candidate edge set Ect initial opinion vector s; real number 0 S S 1/2
Output {(e,, (e))e Æc}
Set 52, according Lemmas 6.3 6.4 and 6.5
p [24 log n
Generate random Gaussian matrices Puxni Q Qpmm
Compute approximations to Iss, X X def for = to do
BΩ. and Ý Y def
f SOLVE(T + L, 6z)
X, < SOLVE( + L, X 51)
Ý. + SOLVE(I + L, Y ,, 52)
for each Ec
8T q9" 10 compute f(e) xb 8
11 return ((e, f(e)le E Ec}
Having considerably approximately computing each part of f(e), we are now able to propose an algo- rithm COMP approximating ((e) for every edge in the candidate set Eg based on Lemmas 6.3 6.4
and 6.5 The outline of algorithm COMP shown in Algorithm whose performance is given in
Theorem 6.1

---

Theorem 6.1 For 0 S < -/////1 1/2, the value f(e) returned by COMP satisfies If(e) - f(e) - ge with high probability.
to approximate f(e), we develop a fast greedy algorithm Overall, follows the greedy strategy (Algorithm[]) D. In detail, Algorithm pperforss k rounds (Lines 2-6). In each round, it takes time (mm to call COMP to compute the approximation of the marginal gain f(e), then iteratively select the element with the highest impact score and update. Therefore, the time complexity of Algorithm is O(mke
Exploiting Algorithm
FASTGREEDY (G, Ec, 8, k, in Algorithm 3 solve Problem |
Algorithm 3: FASTGREEDY((,, Ec, k,
Input A graph G: candidate edge set Ec; an initial opinion vector s; an integer a real number 0 S I 1/2
[Ec|
Output T:: a subset of Ee and [T']
Initialize solution T = 9
2 for i 1 do
fle)le E Ec \T} + COMP(G, Ec \ s,
Select s.t. 4 arg max eee
Update solution T T (c:
Update the graph G < g(V, E (ci))
return T
Experiments
In this section, present numerical results evaluate the performance of our two greedy algorithms SPGREEDY and FASTGREEDY. To this end, extensive experiments are designed and executed on real networks of various types and scales to validate the effectiveness and efficiency of our algorithms.
Datasets. The studied realistic networks are representatively selected from various domains, which are publicly available in the KONECT [3] and SNAP [3 For each network, we implement our experiments on its largest components. The characteristics the largest components for all networks are summarized in Table
Machine and reproducibility. All experiments were conducted on a machine equipped with 32G RAM and 4.2 GHz Intel 17-7700 CPU. All algorithms in our experiments are executed in Julia. In the SDDM solver SOLVE 44 the Julia implementation of which is available at https://githbb.
our algorithms, com//anspielman//aalaaaaass
Table 1: Running time and results for each dataset with k=50.
Network
m
Running
AZ
Ratio
SeGRREDY
FASTGREEDD
SEGREEDY
FASTGREEDY
GrQe
4,158
13.422
7.83
11.13
4.9906
4.9774
0.9962
USgrid
4,941
6,594
10.31
10.70
-7.3406
-7.2720
0.9906
Fno06992
5,094
7,515
10.91
8.98
4.0984
0.9897
Bespwr10
5,300
8,271
12.03
11.57
-60020
-,9820
0.9922
Reality
6,809
7,680
19.81
7,83
-57661
-5.7183
0.9885
Pogesttovermment
7,057
89,429
21.10
27.27
-2,75811
-2,7484
0.9961
WikiElee
Dmnla
7,393
25.569
23.50 33
15.70
4,9245
4,8988
0.9948
HepPh
11,204
117.619
$9.37
79.10
-.2728
-42641
0.9980
Anybcat
12,645
49,132
$1.86
44.11
-54685
-5,4800
0.990
Compano
0.9970
CondMat
21,363
91.286
319.86
101.95
-4,7719
-4,6599
0.9987
Gplus
23,628
39,194
416.24
42.99
-S,144
-5.2672
0.9911
Brightkite+
56.739
212.945
274.97
WikiTalk
397.34
Douban-
154,908
327.162
494.19
Citcscere
227,320
$14.134
1460.20
ToiloccFollows
404.719
713.319
1009.19
FourSquare+
IMDB-
896,305
3,782.447
9076.97
Soapu
1,14,890
2.987.624
6918.97

---

4200
Uniform
0.0
Naaier AdAdee Bdpe
Nusdor of Added Edge
Nasken dlAdie Bdge
Nasba Addi Edge
03501
Cdpe
Edpe
Exponential distribation
Power- law distribution
Figure I:
Optimization results of four methods for edge addition on datasets (a) Karate, (b) Dolphins, (c) Netscience and (d) Discasom with three initial opinion distributions for varying k.
Methods. The sets of k edges found with the following seven strategies. (1) Optimum: selecting
edge set (T) = k with minimum I(G + T) by exhaustive search. (2) Random: selecting k edges at
random. (3) Betweenness: selecting top-k edges with the highest betweenness 77]. (4) DegProduct:
selecting top-k edges with the largest product of two end end-points degrees. (5) DegSum: selecting
top-k edges with the largest sum of two end- end-poine aod-pooits degrees. (6)aasrrredyy; selecting top-k edges with maximum f(e) returned by algorithm FASTGREEDY. (7) SpGreedy: selecting top-k edges with maximum fe) returned by algorithm SPGREEDY
Opinions and evaluation metrics. We investigate three different distributions for the initial opin- ions: uniform distribution, exponential distribution, and power-law distribution. For the uniform distribution, the initial opinion of each node i is distributed uniformly in the range of [o, 1]. For latter two distributions, we use randht.py file in [4] to generate and normalize opinions to range of [0, 1] according to exponential distribution and power law with given slope. Note that there is always a node with internal opinion due to the normalization operation. The performance of all above-mentioned methods is evaluated by the impact of their selected edges the drop of the P-D index AI(G) = I(G T) - I(G), with a smaller AI(G) corresponding to an more effective method.
Results. We first evaluate the effectiveness of our algorithms, we execute experiments on four small realistic networks: Karate with 34 nodes and 78 edges. Dolphins with 62 nodes and 159 edges, Netscience with 379 nodes and 914 edges, and Diseasom with 516 nodes and 1188 edges. These networks are small, allowing add = 1,2,..., edges to augment the network from EEcl 30 candidate edges. For approximation algorithm FASTGREEDY, we set 0.3. Note that smaller corresponds to stronger approximation ratio but less efficiency. As shown in Figures [ for all three initial opinion distributions, the solutions returned by our two greedy algorithms and the optimum solution almost the same so that the three curves are overlapped, demonstrating that our greedy algorithms perform much better than the theoretical guarantee. In addition, both of our algorithms are much better than those returned by the random scheme.
compute the optimal set of edges. For each case, we
To further show the effectiveness of our algorithms, we proceed to compare the results of our methods with the baseline schemes on four relatively larger real-world networks: Yeast with 1458 nodes and 1948 edges, GridWorm with 3507 nodes and 6531 edges, Erdös992 with 5094 nodes and 7515 edges, and Reality with 6809 nodes and 7680 edges, for which it is almost impossible to get the optimal solutions by brute-force search. For each network, the performance of different methods for

---

Bags
Navday Adtin Nage
Polgs
Uniform distribution
4210
1.2
16
Namber AdSE
dddd
Narbor
10
15
Namber Addell toye
Namber of Acokel Zopo
Macher Ladded Elge
Nunsber of Added Edge
Exponential distribution
Power- law distribution
Figure 2: Optimization results for six methods of edge addition on datasets: (a) Yeast, (b) GridWorm, (c) Erdös992 and (d) Reality with three initial opinion distributions for varying k.
varying l and |Ecl = 10000 candidate edges are displayed in Figures 2 We can see that SPGREEDY achieves the best performance as expected, and the proposed FASTGRERDY (a): very close the SPGREEDY method, and (b): consistently outperforms all four alternative methods.
In Table we provide the results of rumning time and the drop of the P-D index AZ(G) returned by our two greedy algorithms. We observe that FASTGREEDY is significantly faster than SPGREEDY, especially for large networks, while both algorithms almost yield the same value on AI It is worth noting that SPGREEDY is not applicable to the last eight networks marked with "*" due to the limitations of time and memory. In comparison with SPGREEDY, FASTGREEDY approximately computes AZ(G) within several hours. Therefore, our algorithm FASTGREEDY achieves remarkable improvement efficiency and scalable to large networks with more than 106 nodes.
Conclusions
In this paper, considered the problem of minimizing the disagreement polarization index I(G) by strategically recommending & links. This problem belongs to the class of discrete optimization that has found vast applications in various domains. We showed the objective function is monotone but non-submodular. We then presented two greedy algorithms to solve the optimization problem: the former returns constant-factor approximation of the optimum solutions in time O(n)), while the latter runs in time Omkk -).. On the theoretic side, we provided analysis of the approximation guarantee for these two algorithms. On the experimental aspect, we performed extensive experiments on real-life networks, which demonstrate that both of our algorithms lead to almost optimal solutions, and consistently outperform several alternative baseline heuristics. Particularly, could yield good approximation solution quickly on networks with more than one million nodes within 2 hours, demonstrating excellent scalablity massive networks.
second algorithm
10

---

Acknowledgments and Disclosure of Funding
This work supported by the National Key R & D Program of China (No. 2018YFB1305100 the National Natural Science Foundation of China (Nos. U20B2051 and 61872093), Shanghai Municipal Science and Technology Major Project (Nos. 2018SHZDZX01 and 2021SHZDZX03), ZJ Lab, and Shanghai Center for Brain Science and Brain-Inspired Technology.
References
[1] Rediet Abebe, Jon Kleinberg, David Parkes, and Charalampos E Tsourakakis. Opinion dy- namics with varying susceptibility to persuasion. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1089-1098. ACM, 2018.
[2] Dimitris Achlioptas. Database-friendly random projections. In Proceedings of the 20th ACM JGGMOD-SIGACT-SIGAAK Symposium on Principles of Database Systems, pages 274-281. ACM, 2001.
[3] Victor Amelkin and Ambuj K Singh. Fighting opinion control in social networks via link recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 677-685, ACM, 2019.
[4] Brian DO Anderson and Mengbin Ye. Recent advances in the modelling and analysis of opinion dynamics influence networks. International Journal of Automation and Computing, (6(2):129-14)) 2019.
[5] Andrew An Bian, Joachim M Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guaran- tees for greedy maximization of non-submodular functions with applications. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 498-507. JMLR. org, 2017.
[6] David Bindel, Jon Kleinberg, and Sigal Oren. How bad is forming your own opinion? Games and Economic Behavior, 92:248-265, 2015.
[7] Ulrik Brandes. faster algorithm for betweenness centrality. Journal of Mathematical Sociology. 25(2):163-177 2001.
[8] TH Chan, Zhibin Liang, and Mauro Sozio. Revisiting opinion dynamics with varying suscepti- bility persuasion non-convex local search. In Proceedings of the 28th World Wide Web Conference, pages 173-183. ACM, 2019.
[9] Yu Chebotarev and F. V. Shamis. The matrix-forest theorem and measuring relations small social groups. Automation and Remote Control, 5809): 1997.
[10] P. Yu Chebotarev and E. V. Shamis. On proximity measures for graph vertices. Automation and Remote Control, 59(10):1443-14
1998.
[11] Pavel Chebotarev. Spanning forests and the golden ratio. Discrete Applied Mathematics, 156-5)8813-82,, 2008.
[12] Xi Chen, Jefrey Lijffijt, and Tijl De Bie. Quantifying and minimizing risk of conflict in social networks. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1197-1205. ACM, 2018.
[13] Uthsav Chitra and Christopher Musco. Analyzing the impact of filter bubbles on social network polarization. In Proceedings the 13th ACM International Conference Web Search and Data Mining, pages 115-123. ACM, 2020.
[14] Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. Power-law distributions in empirical data. SIAM Review, 51(4):661-703, 2009.
[15] Pierluigi Crescenzi, Gianlorenzo D' D'angelo, Lorenzo Severini, and Yllka Velaj. Greedily improving our own closeness centrality in network. ACM Transactions on Knowledge Discovery from Data, 11(1):9, 2016.

---

[16] Pranav Dandekar, Ashish Goel, and David T Lee. Biased assimilation, homophily, and the dynamies of polarization. Proceedings of the National Academy of Sciences, 110(15):5791- 5796, 2013.
[17] Gianlorenzo D' D'Angelo, Martin Olsen, and Lorenzo Severini. Coverage centrality maximization in undirected networks, In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pages 501-508. AAAI, 2019.
[18] Abhimanyu Das, Sreenivas Gollapudi, Rina Panigrahy, and Mahyar Salek. Debiasing social wisdom. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 500-508. ACM, 2013.
[19] Yucheng Dong, Min Zhan, Gang Kou, Zhaogang Ding, and Haiming Liang, A survey on the fusion process in opinion dynamies. Information Fusion, 43:57-65, 2018
[20] Noah E Friedkin and Eugene C Johnsen. Social influence and opinions. Journal of Mathematical Sociology. 15(3-4):193-25) 1990.
[21] J. Gaitonde, J. Kleinberg, and Éva Tardos. Adversarial perturbations of opinion dynamics in networks. In Proceedings of the 21 ACM Conference on Economics and Computation, pages 471-472. ACM, 2020.
[22] Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. Reducing controversy by connecting opposing views. In Proceedings of the 10th ACM Interna- tional Conference on Web Search and Data Mining, pages 81-90. ACM, 2017.
[23] Kiran Garimella, Aristides Gionis, Nikos Parotsidis, and Nikolaj Tatti. Balancing information exposure in social networks. In Proceedings of the 31 Conference on Neural Information Processing Systems, page 4666-4674. ACM, 2017.
[24] Javad Ghaderi and Rayadurgam Srikant. Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate. Automatica, 50(12):3209-32) -2111,9999,,,,, 2014.
[25] Aristides Gionis, Evimaria Terzi, and Panayiotis Tsaparas. Opinion maximization social networks. In Proceedings of the 13th SIAM International Conference on Data Mining, pages 387-395, 2013.
[26] VE Golender, VV Drboglav, and AB Rosenblit. Graph potentials method and its application for chemical information processing. Journal of Chemical Information and Computer Sciences, 2 14)::196-204, 1981.
[27] Shahrzad Haddadan, Cristina Menghini, Matteo Riondato, and Eli Upfal. Repbublik: Reducing polarized bubble radius with link insertions. In Proceedings the 14th ACM International Conference on Web Search and Data Mining, pages 139-147. ACM, 2021.
[28] Guang Hc, Wenbing Zhang, Jing Liu, and Haoyue Ruan. Opinion dynamics with the increasing peer pressure and prejudice on the signed graph. Nonlinear Dynamics, 99:1-13, 2020.
[29] Peng Jia, Anahita MirTabatabaei, Noah E Friedkin, and Francesco Bullo. Opinion dynamics and the evolution of social power in influence networks. SIAM Review, 57(3):667 -977,,399777777 2015.
[30] William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary Mathematics, 26: 189-206, 1984.
[31] Jérôme Kunegis. Konect: The koblenz network collection. In Proceedings of the 22th World Wide Web Conference, pages 1343-1350. ACM, 2013.
[32] Heidi Ledford. How facebook, twitter and other data troves are revolutionizing social science. Nature, 582(781):38888 -30, 2020.
[33] Jure Leskovee and Rok Sosič. SNAP: A general-purpose network analysis and graph-mining library, ACM Transactions on Intelligent Systems and Technology, 8(1):1, 2016.
[34] Huan Li and Aaron Schild. Spectral subspace sparsification. In Proceedings of the 59nd IEEE Annual Symposium Foundations of Computer Science, pages 385-396. IEEE, 2018.
12

---

[35] Erika Mackin and Stacy Patterson. Maximizing diversity of opinion in social networks. In Proceedings of the 59th American Control Conference, pages 3728-2736 IEEE, 2019.
[36] Antonis Matakos, Evimaria Terzi, and Panayiotis Tsaparas. Measuring and moderating opinion polarization in social networks. Data Mining and Knowledge Discovery, 31(5):1480-1505
2017.
[37] Antonis Matakos, Sijing Tu, and Aristides Gionis. Tell me something my friends do not know: Diversity maximization in social networks. Knowledge and Information Systems, 62(9):3697- 3726, 2020.
[38] Carl D Meyer, Jr. Generalized inversion of modified matrices. SIAM Journal on Applied Mathematics, 2453)315--33,, 1973.
[39] Cameron Musco, Christopher Musco, and Charalampos E Tsourakakis. Minimizing polarization and disagreement in social networks. In Proceedings of the 27th World Wide Web Conference, pages 369-378. ACM, 2018.
[40] Anton Proskumnikov and Roberto Tempo. A tutorial on modeling and analysis of dynamic social networks. part I. Annual Reviews in Control, 43:65-79, 2017.
[41] Chiara Ravazzi, Paolo Frasca, Roberto Tempo, and Hideaki Ishii. Ergodic randomized al- gorithms and dynamics over networks. IEEE Transactions on Control of Network Systems, 1(2):78-87, 2015.
[42] Justin Semonsen, Christopher Griffin, Anna Squicciarini, and Sarah Rajtmajer. Opinion dy- namics in the presence of increasing agreement pressure. IEEE Transactions on Cybernetics, 49(4):1270- 1278, 2019.
[43] Liren Shan, Yuhao Yi, and Zhongzhi Zhang. Improving information centrality of a node in complex networks by adding edges. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 3535-3541. AAAI, 2018.
[44] D. Spielman and S. Teng. Nearly linear time algorithms for preconditioning and solving sym- metric, diagonally dominant linear systems. SIAM Journal Matrix Analysis and Applications, 35(3):835 888, 2014.
[45] Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal of Computing, 1016):1913-1926, 2011.
[46] Sijing Tu, Cigdem Aslay, and Aristides Gionis. Co-exposure maximization in online social networks. In Proceedingy of the 34th Conference on Neural Information Processing Systems, pages 3232-3243. ACM, 2020.
[47] Pinghua Xu, Wenbin Hu, Jia Wu, and Weiwei Liu. Opinion maximization in social trust networks. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, pages 1251-1257. AAAI, 2020.
[48] Wanyue Xu, Qi Bao, and Zhongzhi Zhang. Fast evaluation for relevant quantities of opinion dynamics. In Proceedings of the 30th World Wide Web Conference, pages 2037-2045. ACM, 2021.
[49] Yuhao Yi, Timothy Castiglia, and Stacy Patterson. Shifting opinions in a social network through leader selection. JEEE Transactions on Control of Network Systems, 8(3):1166-11) 2021.
[50] Yuhao Yi and Stacy Patterson. Disagreement and polarization in two-party social networks. 53(2):2568-2575 2020.
13


Reviews:
[{"review_id": "lbKxj0dctz", "reviewer": "Reviewer_HjPc", "summary": "In this paper, the authors study an opinion dynamics problem using the Friedkin-Johnsen model, where one aims to minimize the polarization + disagreement by adding up to k edges. The authors derive a greedy algorithm for this problem and show that it has a constant factor approximation. They then derive a faster version of the greedy algorithm (but without a constant factor approximation) involving random matrix projections, JL, and fast SDDM solvers. Empirically, they show that their methods are close to optimal for small k, and that their fast greedy algorithm scales well to large networks.", "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": "Strengths:\n* Novel+interesting opinion dynamics problem\n* Clean analysis of algorithms\n* Empirical results are very good\n* Writing is good for the most part\n\nWeaknesses: \n* Writing in Section 6 could be clearer\n* Could use better experimental baselines\n\nOverall, I liked this paper and would like to see it accepted. The problem itself seems novel and interesting - similar to [36], but completely different type of analysis. The greedy algorithms flow quite naturally from the observation in Lemma 4.1, that P+D index goes down as you add more edges. (On a side note, this observation was not immediately obvious to me, e.g. if you have a barbell-like graph, with two dense clusters that are not that connected to each other, and you add edges between nodes in the same cluster - I would guess polarization goes up and disagreement goes down, but unclear what happens to P+D). The empirical results are also very impressive, showing that your fast algorithm can run on graphs with millions of nodes/edges.\n\nI only have minor complaints; see below.\n\n=======\n\n* Section 6: I find the X, X-bar, X-tilde notation (line 252) to be quite confusing. Seems easier to just write these formulas out directly without introducing X’s. In general this excess of notation makes Section 6 hard to read.\n\n* It should be made explicit that Algorithm 2 does not have any guarantees (eg constant factor approx) unlike Algorithm 1. The writing is a bit too slick, making it seem like Algorithm 2 has some global guarantees (eg by mentioning \\epsilon in the runtime) when it does not.\n\n* I find the baselines in the experiments a bit lacking since none of them use the innate opinions S. It would be good to add more baselines that use s.\n\n* Question: Do any results extend to convex combinations of polarization + disagreement? E.g. [36] notes that convex combinations P + rho*D of polarization and disagreement are generally not convex (except for when rho=1). I wonder if that affects Lemma 4.1 at all.\n\n* Line 221: I understand space is limited but it would be interesting to see the approximation guarantee for the naive greedy algorithm written out, since you say in line 223 that it is not satisfactory\n\n* Line 8 of SpGreedy: I find the interchanging of (I+L)^{-1} and \\Omega to be confusing notation since they are the same thing.  In general this is confusing notation throughout the paper.\n\n* Line 233: would be good to define what SDDM means\n\n* Table 1: What is the k (number of edges added) here? Should be included somewhere, eg in table caption\n\n**Nits/typos**:\n* line 41: to greedy -> to a greedy\n* line 161: “in the sequel” unsure what this means\n* line 172: Similar idea -> A similar idea\n* Supplement 1: Should say proof of 4.1, not 3.1\n* Problem 1: I assume E and E_C are disjoint?\n* Line 191: “by the following” -> “in the following”\n\n* Line 8 of supplement: capitalize “when”\n* Line 26 of supplement: L_{W + T} should be L_{W \\cup T}\n* Line 27 of supplement: how did you get the last inequality?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No, the potential negative societal impact of their work is not discussed. I would add at least one example of how this could be used negatively (eg manipulation by social networks)", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5.5"}, "extra_text": {}}, {"review_id": "eDuWYX3V3qr", "reviewer": "Reviewer_Ceon", "summary": "The paper studies the problem of recommending k links to a given graph G from a candidate pool of candidate links Ec. The goal is to minimize the index of disagreement-polarization as introduced by Musco et al. The authors prove that the objective is not submodular, but they analyze the performance of greedy, and provide a fast version based on random projections. They apply their methods on real-world data, with synthetic opinions. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "In this work the authors focus on recommending k links in order to minimize polarization and disagreement in social networks. Intuitively, in a recommender system links may connect nodes with similar opinions and thus have low disagreement but incur higher polarization, or nodes with totally different opinions and thus have low polarization but incur higher disagreement. The objective takes into account both terms, and aims to balance between the two.  Specifically, the authors rely on the framework of Musco et al. that assumes the Friedkin-Johnsen model of opinion dynamics and defines disagreement as the sum of the squared differences of opinions over all edges, whereas the polarization as the second moment of the opinions centered around 0. Both terms can be nicely expressed using the Laplacian. The authors consider the problem of   minimizing the sum of those terms over all possible recommendations/additions of k edges. The objective is monotone, a statement proved directly from applying the Sherman-Morisson formula.  Clearly, there is a straight-forward naive algorithm that checks all possible subsets of cardinality k among the set of possible recommendations Ec. This is infeasible in practice, and thus the authors study the performance of greedy. The authors prove that the resulting optimization problem is neither submodular nor supermodular, so the greedy algorithm is not guaranteed to provide an 1-1/e approximation ratio or an exact solution. They use the results of [5] to characterize the parameters of how “far” is the objective from being submodular, and provide some insights on how the greedy algorithm behaves; it depends on the graph G, and the graph formed by the possible recommendations that in principal can be the complement of G. The authors also leverage the ideas of Spielman-Srivastava from their work on spectral sparsifiers  that use random projections for fast effective resistance computations in order to speed up the greedy algorithm. Finally they implement their algorithm in Julia (code available in supplement), and test it on a variety of datasets. \n\nSome questions to the authors: \n\n1. Unfortunately the approximation guarantees are not easy to interpret. Perhaps you can use some classes of graphs with known spectral guarantees to derive some interesting corollaries (e.g., expander graphs, stochastic blockmodel). \n\n2. Unfortunately none of the datasets contains some true opinion dynamics. Therefore it would have been more interesting to see more distributions other than the uniform.  \n\n3. Did you consider the case of directed graphs? The framework of Musco et al. does not seem to be directly applicable there. \n\n\n====\nPost-rebuttal: I thank to the authors for their detailed response. I have upgraded my score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work could potentially have a positive impact on mitigating issues from  echo chambers, and filter bubbles. ", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "bTPge3Zrhl", "reviewer": "Reviewer_nZrq", "summary": "In this paper the authors propose the task of adding links to a social network to minimize notions of disagreement and polarization across the network.  In particular, they define disagreement across neighbors in the graph and polarization by the variance in expressed opinions of the nodes.  The paper then offers two approximate algorithms for greedily adding a fixed number of edges to the graph to minimize the sum of the disagreement and polarization.  They show that their algorithms are both theoretically and empirically tractable, outperform naive baselines, and in some cases close to optimal.\n", "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 does a nice job of clearly providing their problem formulation and demonstrating their ability to provide reasonably fast, approximate algorithms to solve these problems.  \n\nMy primary concern with the paper is with respect to its significance.  While I believe it is theoretically interesting, I worry that it is overly simplified of a model in ignoring any way of incorporating user preferences or a traditional recommender providing probability of the users being interested in connecting, as past work has done.  A discussion of how the research could be incorporated into more practical settings would be valuable.  That said, the theoretical result is still interesting and this may be unnecessary even if valuable.\n\nDetails:\n\nEval - initializing with uniformly random $s$ is particularly unrealistic, and I'd be curious how results are effected by other choices of $s$, e.g. correlation opinions with graph structure as in communities.\n\nNone of the baselines consider the opinions $s$?  They do show the effect of merely making the graph more dense but I'd think connecting individuals or clusters with very different opinions is critical.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above and below.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {"ethical_concerns": "The framing of polarization as defined here and making that a goal of social network design / recommendation raises some ethical concerns.  In particular, the framing seems to be one that is suitable for theoretical analysis, but it is not clear that merely decreasing variance of opinions is an ethically good definition of polarization to optimize or if networks should be taking such actions.  A more complete discussion of these limitations beyond the scope of the theory would be valuable.\n"}}, {"review_id": "6V8T7u9Lie", "reviewer": "Reviewer_9U5a", "summary": "The problem considered is adding links to a network to decrease the polarization+disagreement ratio. The proposed method is the greedy algorithm: adding links one-by-one to maximize the improvement. Showing approximation ratio based on the approximation result of [5] (in ICML'17, showing that the  polarization+disagreement  is close enough to being submodular. \n\nEvaluating a greedy step exactly required a matrix inversion, hence it is slow. The authors also offer a faster approximate solution using Johnson-Lindenstrauss lemma", "questions": "", "limitations": "", "rating": 7, "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": "I find the result showing that  polarization+disagreement  is close enough to being submodular to give guarantees for approximation interesting! I am a bit disappointed that all these details were pushed to supplemental material, including all proofs as well as even including the definition of curvature and submodularity ratio.\n\nThe faster approximate version is important to make the method practical. \n\nI am not sure if NeurIPS is the right venue for this work, but it is definitely very interesting", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not aware of negative societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1 hour"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Generally all reviews for this paper were positive -- they appreciated the algorithmic contribution -- showing that a greedy approach to link recommendation for minimizing polarization+disagreement gives a bounded approximation ratio, despite the fact that the polarization+disagreement is not submodular. There were significant concerns about practical impact/relevance of the work. Nevertheless, I am recommending acceptance.
Decision: Accept (Poster)