Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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. 

Evaluating a greedy step exactly required a matrix inversion, hence it is slow. The authors also offer a faster approximate solution using Johnson-Lindenstrauss lemma
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.

The faster approximate version is important to make the method practical. 

I am not sure if NeurIPS is the right venue for this work, but it is definitely very interesting
limitations_and_societal_impact: Not aware of negative societal impact
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

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.  

My 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.

Details:

Eval - 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.

None 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.

limitations_and_societal_impact: See above and below.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Strengths:
* Novel+interesting opinion dynamics problem
* Clean analysis of algorithms
* Empirical results are very good
* Writing is good for the most part

Weaknesses: 
* Writing in Section 6 could be clearer
* Could use better experimental baselines

Overall, 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.

I only have minor complaints; see below.

=======

* 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.

* 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.

* 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.

* 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.

* 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

* 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.

* Line 233: would be good to define what SDDM means

* Table 1: What is the k (number of edges added) here? Should be included somewhere, eg in table caption

**Nits/typos**:
* line 41: to greedy -> to a greedy
* line 161: “in the sequel” unsure what this means
* line 172: Similar idea -> A similar idea
* Supplement 1: Should say proof of 4.1, not 3.1
* Problem 1: I assume E and E_C are disjoint?
* Line 191: “by the following” -> “in the following”

* Line 8 of supplement: capitalize “when”
* Line 26 of supplement: L_{W + T} should be L_{W \cup T}
* Line 27 of supplement: how did you get the last inequality?
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
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. 

Some questions to the authors: 

1. 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). 

2. 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.  

3. Did you consider the case of directed graphs? The framework of Musco et al. does not seem to be directly applicable there. 


====
Post-rebuttal: I thank to the authors for their detailed response. I have upgraded my score. 
limitations_and_societal_impact: The work could potentially have a positive impact on mitigating issues from  echo chambers, and filter bubbles.
review_title: null

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)