On the Relationship Between Relevance and Conflict in Online Social Link Recommendations
Authors: Yanbang Wang
Jon Kleinberg
Venue: NeurIPS 2023 poster (2023)
Keywords: social networks
spectral analysis
link recommendation
polarization and conflict
TL;DR: We study the relationship between the goal of relevance and the goal of reducing online conflict in link recommendations.

Abstract: In an online social network, link recommendations are a way for users to discover relevant links to people they may know, thereby potentially increasing their engagement on the platform. However, the addition of links to a social network can also have an effect on the level of conflict in the network --- expressed in terms of polarization and disagreement. To date, however, we have very little understanding of how these two implications of link formation relate to each other: are the goals of high relevance and conflict reduction aligned, or are the links that users are most likely to accept fundamentally different from the ones with the greatest potential for reducing conflict? Here we provide the first analysis of this question, using the recently popular Friedkin-Johnsen model of opinion dynamics. We first present a surprising result on how link additions shift the level of opinion conflict, followed by explanation work that relates the amount of shift to structural features of the added links. We then characterize the gap in conflict reduction between the set of links achieving the largest reduction and the set of links achieving the highest relevance. The gap is measured on real-world data, based on instantiations of relevance defined by 13 link recommendation algorithms. We find that some, but not all, of the more accurate algorithms actually lead to better reduction of conflict. Our work suggests that social links recommended for increasing user engagement may not be as conflict-provoking as people might have thought.

On the Relationship Between Relevance and Conflict in Online Social Link Recommendations
Yanbang Wang Department of Computer Science Cornell University ywangdr@ eaanddrrcs..comll.eddu
Jon Kleinberg
Department of Computer Science
Cornell University kleinberg @ cornell.edu
Abstract
an online social network, link recommendations are a way for users to discover relevant links to people they may know, thereby potentially increasing their en- gagement on the platform. However, the addition of links to a social network can also have effect the level of conflict in the network expressed in terms of polarization and disagreement. To this date, however, we have very little under- standing of how these two implications of link formation relate each other: the goals of high relevance and conflict reduction aligned, or are the links that users are most likely accept fundamentally different from the ones with the greatest potential for reducing conflict? Here we provide the first analysis of this question, using the recently popular Friedkin-Johnsen model of opinion dynamics. We first present a surprising result on how link additions shift the level of opinion conflict, followed by explanation work that relates the amount of shift to structural features of the added links. We then characterize the gap in conflict reduction between the set of links achieving the largest reduction and the set of links achieving the highest relevance. The gap is measured on real-world data, based on instantiations of relevance defined by 13 link recommendation algorithms. We find that some, but not all, of the more accurate algorithms actually lead to better reduction of conflict. Our work suggests that social links recommended for increasing user engagement may not be conflict conflict-provoking people might have thought.
Introduction
Recent years have seen an explosion in the usage of social media and online social networks. In 2022, estimated 4.6 billion people worldwide used online social networks regularly (T]. Online social networks such as Facebook, Linkedln, and Twitter are transforming the society by enabling people to exchange opinions and knowledge
unprecedented rate and scale.
However, there are also significant concerns about the disruptive effects of social media, as people observe the growing level of polarization and disagreement in online communities. Conflicts arise over topics ranging from politics 3].. to entertainment 4 5) and healthcare (6. For our purposes in this paper, will adopt terminology from the social sciences in distinguishing between polarization and disagreement as follows: polarization will refer to how much people's 's opinions deviate from the average, and disagreement will refer to how much people directly connected to each other in the social network differ in their opinions.
Reducing polarization and disagreement can be a benefit both to individual users of these platforms, who would experience less conflict and stress, and potentially also to the platforms themselves, to the extent that too much contentiousness can make the platform unattractive users.
The root causes of increased polarization and disagreement have been the subject of much concern and debate. One popular idea is Eli Pariser's "filter bubble" theory (7). The theory attributes
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the intensification of online conflict to the recommendation algorithms deployed by providers for maximizing user engagement. It conjectures that a person becomes more biased and cognitively blinded because recommendation algorithms keep suggesting new connections and new pieces of content associated with similar-minde people, thus solidifying the person's 's pre-existing bias.
The "filter bubble" theory is influential, but the empirical evidence supporting it has been limited. For example. [8] conducted experiments of hypothesis testing on the effect of personalization on consumer fragmentation, concluding that there was not enough evidence to support the "filter bubble" theory: [9] also employed a data-driven method by examining the data from a movie recommender system and checked if users may gradually get exposed to more diverse content; [IO] surveyed a number of active twitter users and suggested that the offline habits of online users may actually play a more important role in creating "filter bubble". These empirical studies indicate that the magnitude of the "filter bubble" effect in social recommendation system may not be as significant as the theory's s popularity implies. However, more principled understandings caused
of the strength of "filter bubble" effect caused by social recommendations are missing from the picture.
This paper aims to explore theoretical evidence and principled characterizations of the relationship between relevance and conflict in online social link recommendations. We seek to understand how social links recommended for maximizing user engagement (i.e. relevance) may shape the polarization and disagreement (i.e. conffict) landscape of social network.
We note that the "filter bubble" theory essentially counter-poses two important aspects of social link recommendations: "relevance" and "reduction of conflict". The former has been well-studied as the classic problem of link prediction [1T-13]; the latter involves social accountability of link recommendations, and has received rapidly increasing attentions in recent years
15). 15). To date, however, there has been very little attempt to study the relationship between these two aspects, in contrast to the well-established paradigms to research the relationship between relevance and novelty 16 17 relevance and diversity 19]] relevance and serendipity [2022] in recommendations.
To theoretically analyze how opinions change in response to the addition of new links, it is necessary for us to choose base model that specifies the basic rules of (at least approximately) how opinions propagate in social networks. There are several options for this purpose, including the Friedkin-
Johnsen (FJ) model [22]. the Hegselmann- Krause (HK) model (23), the voter's model
[24). etc. In
this work, we choose the popular FJ model which will be formally introduced in Sec 2
reasons for the FJ model to be the most suitable base model for our analytical purpose. The first is its outstanding empirical validity and practicability: according to recent surveys (25 the FJ model is the only opinion dynamics model to date on which a sustained line of human-subject experiments has confirmed the model's predictions of opinion changes (22 35). The second reason the availability of necessary notions and definitions associated with the conffict measure: to our best knowledge, the FJ model is also the only opinion dynamics model upon which social tensions like polarization and disagreement have been rigorously defined [14), and widely accepted [1536 39 Therefore, it is most meaningful to conduct in-depth theoretical analysis based on the FJ model.
There
Proposed Questions. Three questions are central to our research of the relationship between relevance and minimization of opinion conflict (polarization and disagreement) in link recommendations:
What are the structural features of the links that can reduce conflict most effectively? Are the Q1.
features aligned with those of relevant links (i.e. links most likely to be accepted by users)?
Q2. What is the empirical degree of alignment between relevance and conflict minimization for various link recommendation algorithms executed on real-world data?
Q3. What are the limitations of our theoretical analysis?
Main Results.
For Q1, we first study the amount of change in opinion conflict (polarization + disagreement) caused by general link additions. We derive closed-form expressions for this, which reveal a perhaps surprising fact that purely adding social links can't 't increase opinion conflict. Because link additions essentially improves network connectivity, further present theorem that uses connectivity terms to characterize opinion conflict, leading to a conclusion aligned with the surprising fact.
To interpret the structural features of links that can reduce opinion conflict most effectively, we conduct series of explanation work on the closed-form expressions derived for conflict change. We manage to associate the expressions' components to various types of graph distances, which are

---

then summarized into two criteria for finding minfiictimiiiiiigggg links in social networks: (1) for single controversial topic, confiit-mmiimizing links should have both end nodes as close as possible in the network and their expressed opinions on that topic as different as possible; (2) for a random distribution of controversial topics, conflict-minimizing links should have both end nodes different "clusters" of the network while still remaining fairly well-connected with each other.
For Q2. we introduce a model-agnostic measure called conflict awareness to empirically evaluate recommendation model's ability of reducing conflict. We measure conflict awareness for many link recommendation algorithms on real-world social networks. We find that, some, but not all, of the more accurate recommendation algorithms have better ability to reduce conflict more effectively,
For Q3, discuss limitations of analyzing the change of opinion conflict using the FJ model, presented in the form of a paradox. The paradox indicates that reducing conflict on social networks by suggesting friend links could actually make people more stressful and upset about their social engagement. This leaves an interesting topic for future study.
2
Preliminaries
2.1 Social Network Model
We consider social network modeled by an undirected graph G = (V, E) where V is the set of nodes and E is the set of links. The adjacency matrix A (at)) is symmetric matrix with ai link e (i.j) é E. and as otherwise. In more general case ag can also be a non-negative scalar representing the strength of social interaction between i and j. The Laplacian matrix L is defined as L D A where D diag( (E)] Otg) (t..)=......Ivi) is the degree matrix. The incidence matrix B a |V| [E]] matrix whose all elements are zero except that for each link e (i.j) E E. Bue Bi: = =1 j interchangeable G' is undirected). Given a link e= (i,j), its edge (indicator) vector be is the column vector in B whose column index is e, (ba): = 1, (b.); -11.
Note that modeling a social network by an undirected graph does not restrict the social influence between two connected people to be symmetric in both directions. In the Friedkin-Johnsen model introduced below, the amount of influence carried by a link is normalized by the social presence (node degree). Symmetry is thus broken because the two destination nodes can have different degrees.
2.2 Friedkin-Johnsen Opinion Model
The Friedkin-Johnsen (FJ) model is one of the most popular models for studying opinion dynamics on social networks in recent years. Its basic assumption is that each person í has two opinions: an initial ("innate" (39) opinion s; that remains fixed, and an expressed opinion 2; that evolves by iteratively averaging i's initial opinion and its neighbors' expressed opinions at each time step:
8; + EjjoN, asy21
(0) =
(I+1)
1 EjeN, aij
where N; is the neighbors of node i; d.j is the interpersonal interaction strength: in the simplest form, it takes binary (0/1) values indicating whether i,J are friends with each other; more sophisticated rules for assigning continuous values also exist.
can be proved that the expressed opinions will eventually reach equilibrium, expressed in vector form: 2(()) = LL)-s,, where 2 2(*)) E RIV are the opinion vectors. For simplicity. this paper writes 2 in place (00) as the primary focus is the equilibrium state of 2. While expressed opinions guaranteed to reach equilibrium, they rarely reach global consensus. Previous studies [14]36] have extended 2, s, and their interplay with G into a plethora of measures to reflect various types of tension over the social network, among which the most important ones are:
Disagreement: D(G,s)= E(EJ)E aiy(2: 2 =T L)- L)-' =
L(I
=)== 55 (I+ 31+)) . Conflict: C(G,s) = D(G, PPG,s) s (I+
Polarization:
where the mean -M and zero-centered vector : = z 5; likewise for 5, In fact, all s on the M
right-hand-side above can replaced by ā and the equations still hold [1]. Again, for simplicity we follow the convention assume to be always zero-centered. The tilde accent is thus omitted.
3

---

2.3 Spanning Rooted Forest
A forest is an acyclic graph. A tree is a connected forest. A rooted tree is a tree with one marked node as its root. A rooted forest forest is a forest with one marked node in each of its component. In other words, a rooted forest is a union of disjoint rooted trees. Given graph G = E), its spanning rooted forest is rooted forest with node set V. Later in this paper, will use various counts of spanning rooted forests to help interpret mathematical quantities arising from our analysis.
Conflict Change Caused by Link Additions
3.1 Link Additions Help Reduce Conflict
We start by analyzing the effect of link additions on the conflict measure of social networks. The following theorem provides closed-form expressions of both conflict change and its expected value (over random distributions of initial opinions) caused by the addition of a new link. We assume the link have unit weight, but the result can be easily generalized to the case of continuous weights. Surprisingly, our theorem shows that both conflict change and its expected value are non-positive terms no matter which link is to be added.
Theorem 1. Given initial opinions and social network G = EV, with Laplacian matrix L, let G+e (V,Ev {e}) denote the new social network. The change of conflict of expressed opinions caused by adding is given by
(2, 22 D.rC C(G-e; -CC(,,) ( (L+ 50
The topology term L can be marginalized by considering initial opinions as independent samples from a random distribution with finite variance, i.e. 8; D(0, d²) iid. the expected conflict change can be expressed as:
021(1+ L)- A-c [C] FE-D(t.org(((Gee)))))-- C) 1+ bz (1+ -)- 00
The marginalization of L in expected conflict change allows us to focus on the effect of network structure when considering conflict change. It also reflects the fact that people may hold different initial opinions upon different controversial topics. We also computationally validate the theorem, especially to check that the conflict change caused by link additions is indeed non-positive. See Appendix for more details.
3.2 Network Connectivity Helps Contract Conflict
The addition of links always improves the connectivity of social network. Therefore, understand the effects of link additions on conflict, it also helps to examine what network connectivity implies about conflict in general. Here is an analysis that shows having opinions propagate on better- connected social network helps "contract" more conflict. The setup is as follows.
We create "control group" where the effect of idea exchange over social networks gets eliminated: imagine if the same group of people that get studied are instead totally disconnected with each other, their expressed opinions z would stay consistent with their initial opinions s since no pressure is felt from the outside; meanwhile, their disagreement term no longer exists because the term is defined only for connected people. Therefore, the conflict of this control group C(Go, s) would just be s' polarization of initial opinions; here Go (V, Ø). Corresponding to this control group is the "treatment group" where opinions propagate on the network, with conflict rate C(Go, 8) (I -)- We now compare the two groups and have the following conflict contraction theorem: Theorem 2. Given initial opinions s and social network G (V, F.) with Laplacian matrix I,, we can bound the ratio of conflict between the control and the treatment group:
C(Go, 8) 1+ dmmi lig 2
max (d4 + dd)+ Z C(G,s) 2 (L.j)E
(4)
where di, dj are degrees of nodes i, dmin is G's minimum node degree; ha is G's Cheeger constant.
Theorem shows the range the influence that a social network can have on public opinion conflict. Both bounds are expressed in relation to network connectivity measures. Remarkably, the lower

---

bound < 1 suggests that facilitating idea exchange almost always contracts conflict, and the range of contraction rate depends on the connectivity bottleneck dmin and hig. In general, larger hig- meaning a better-connected network with less bottleneck, leads to larger contraction rate more ideal case in terms of public benefit. See Appendix [ for computational validations of the theorem.
Interpreting Features of Conffict-Minimizing Links
Last section shows that recommending new links to people helps reduce opinion conflict in general. We now proceed to investigate how different links may reduce different amount of opinion conflict. A natural question in that regard is (Q1) how (i.e. reducing most conflict) of social links, especially in terms of their relationship with the relevance feature (i.e. the likelihood that users will accept and like the recommended link).
characterize the conflicting minimization feature
4.1 Contlict-Minimizing Links
Our characterization of conflict-minimizing links is extended from Theorem T A+cC
(I-L) 1b212, It is straightforward see that the numerator (z, 22)² is the difference between expressed opinions of node and j. The rest two terms, 6% + -e and (1 bel" can be interpreted by the following two theorems.
1+ (1+2))6 and [,] 1-b"
(a-=;))
Theorem 3. Given social network G and link (i.j) add, the term Dy + a rype of graph distance between nodes i. The distance can be interpreted by the following quantity:
(I+LL- -L- measures
D (T + L.) =N Ns;))
N is the total number of spanning rooted forests of G;
Nay the total number of spanning rooted forests of G, in which node x is the root of the tree to which æ belongs, and y belongs to a different tree than that x-rooted tree;
Together with the interpretation of (z; =2 Theorem gives the two criteria for finding conflict- minimizing links over fixed initial opinions s:
1. The two end nodes should be as close as possible in the network (so 1 1 6y" (I +D) is small);
2. Expressed opinions at the end nodes should be as different as possible (so (z, (25-2)) 2,)² is large);
Criterion is perhaps bit surprising one may think connecting two remote people should introduce more balanced perspectives to both of them. On the other hand, the two criteria still make much sense when viewed together: there must be something unusual about the network structure when two close friends with supposedly strong influence to each other actually hold very different opinions. The suggested
link be seen as correction to the network structure's 's unusualness.
Theorem 4. Given social network G (V, E) and a link = (i.j) to add, the term (I -) also measures a type of graph distance between nodes i and j. The distance can be interpreted by the following quantity:
L = 22 (Nsx
N2a
beV
where N and Nay follow the definitions in Theorem 3
Similar to Theorem 3 Theorem also explains o L by a type of graph distance. However, note that there is a subtle difference between the two types of distance. The subtlety is especially important to distinguish because [..]E.[C] is the ratio between the two terms.
Corollary 1. A.C can be completely expressed by counts of different types of spanning rooted forests as defined in Theorem 3
A E. Ec
My No:) Σ -N KeV
We use Corollary 1 to give intuitive interpretations of A E.C. First, notice that given a social network G, the number of G's spanning rooted forests / in the denominator a constant. Therefore. the competing terms in A., are NG, NNz and Ebev (Nax ~N According to Theorem
5

---

B
Simulation Results:
A
00.5
0
0.3
0.1
0
0.5
0.3
0.1
A
B
Both from eg. (a,,
C
0.3
0.3
0.3
0
C
[A, -0.06 0.0012
D
0.1
0.1
0.1
83
Ne 10
Block
Pcc 0.3
One from A, from both linked to C, e.g. (a, b,):
100
100
0.5
Pgs 0.5
[g[A,.C] -0.415 1 0.0015
020
No 10
bb
44
Pop
One from A, from B, both linked to D, egg. e = (ag, b2):
Visualization of the Network
Conceptual Illustration Network
[. 00.10 + 0.0015
Figure I: A barbell-like social network with cluster and bridge structures, generated from stochastic block model. Different groups of links have different structural features, producing different expected conflict change when added to network, shown in the right panel. The sample means and their 95%-intervals reported based repeated simulations. Note that this example gives special network for illustrative purpose, but our interpretations of Thrm and Cor apply to any networks.
Nay essentially measures the distance between and by counting z-rooted spanning forests that separate x and y into different components. Therefore, Niy +NJ emphasizes "local disconnectedness" between i and j. while Σ (Nas- - N5x))² emphasizes i and j's "global position gap" "global" means that and j's position is defined relative to (every node of) the entire network. The following example further illustrates their difference.
Example 1. Consider a random network generated from the stochastic block model with node partitions [NA. Ng.Nc.NN. diagram in Figure [ middle illustrates the network: A, B are the two main clusters with high link density (0.5); the other two clusters, C, D, much smaller and have lower link densities (0.1, 0.3) both internally and to A, B. Structurally speaking, C, D serve as two "bridges" between and B. Now consider adding links to three groups of previously disconnected node pairs defined as:
[100, 100, 10, 10] and block matrix shown in Figure [ left.. The
Group 1: both end nodes in Cluster A, e.g. (0z, 04)
* Group 2: one end node in Cluster A, one end node in cluster B, both linked to some other node(s) cluster C, e.g. (a1, bn)
Group 3: one end node in Cluster A, one end node in cluster B, both linked to some other node(s) in cluster D, e.g. b2)
Our simulation shows that Group introduce least conflict reduction on average in fact much less than the other two groups do. Since each pair of nodes Group 1 are from the same densely connected cluster, it means that the numerator term Σxev (Nsx - .Nr..² dominates [C). Therefore, we may conclude that general a link reduces more conflict if it involves two nodes that are globally distant. Comparing Group 2 and 3, we can further see that node pairs in Group 2 have stronger local connectivity than those in Group 3 ('bridge" has higher link densities than "bridge" D). The fact that Group 2 reduces more conflict average shows that stronger local connectivity actually positively contribute to conflict minimization.
We have now found the following two features of conflict-minimizigg minimiziin links, when initial opinions are sampled from distribution with finite variance:
1. Globally, both end nodes should belong to different clusters, that o²l L) is large;
2. Locally, both end nodes should be decently well-connected with each other, so that 1 (7
- is small.
4.2 Relating Conflict Minimization to Relevance
Relevant links are links that are likely to be accepted by users. Over the past two decades, relevant links have been extensively studied as the core subject of link prediction problem in many different contexts (11-13). We know that the relevance of social links has strong correlation with small graph distance between the two end nodes [12 45) Comparing this existing knowledge with our

---

characterizations of conflict-minimizee links, it is not hard to perceive that relevance and conflict minimization are not always incompatible with each other. Instead, they can have a decent degree of alignment in some cases.
5 Measuring the Degree of Alignment Between Relevance and Conflict Minimization on Real-World Data
Sec. Is analysis shows that the two features of relevance and conflict minimization are not strictly incompatible with each other. This section discusses how we can measure the two features' degree of alignment on real-world data.
5.1 Definition of Conflict Awareness
We start by formulating link additions: link addition function f is defined as: f(e; G,3): (V V) + [0, +oo), where the function parameters are given social network G = (V, E) and budget B for adding links. is defined on node pairs, subject the budget constraint ΣeeVrv f(e; G.
Among all possible link addition functions, there is a conflict-minimizing function (e; G. 3), which the function that reduces the most conflict under budget B. We use A,C and A y [C] to denote the conffict change and expected conflict change caused by applying f over the network G. The two terms are related by [ Sa ((s) 4 dg where p(s) the probability density function of s. We further use Ly to denote the Laplacian of the network formed by only the new links added by f. Definition Given a social network G, initial opinions s, and positivie budget B, the conffict awareness (CA) of a link addition function f(; G, (3) is defined by the conftict reduced by applying add links, divided by the best possible conflict reduction by applying f to add links:
CA(f) = -, 5.C.C
(8)
where
A,C = s (I+ s-s")"'-S
(9)
A
min
A,C
(10)
subject to
L C (Laplacian constraint)
(11)
Tr(I.)) s 23 (budget constraint)
(12)
+ T.y is the Laplacian matrix of the network after being modified by f. so the definition of 4,C is straightforward. A C is defined as the objective of an optimization problem, which essentially looks for the best network with total link weights 3 to be superimposed over the original network G.
The measure conflict awareness is useful for two reasons. First, CA essentially measures how "bad" any link recommendation algorithm is with regards to minimizing opinion conflict. By assigning f function that recommends relevant links, CA immediately becomes quantifier that shows how much mismatch exists between fsuugeested relevant links and conftict-mininizing links. Second, CA better measure than the pure conflict change A,C. This is because CA is normalized to [0, 1]. which allows meaningful comparisons across different social networks. We will see that this property becomes especially helpful in practice for characterizing link recommendation algorithm.
We can further show that CA also has a computationally desirable feature of being convex. Proposition 1. In Definition 7 A v.C is the objective of a convex optimization problem.
We can generalize Definition to expectation of conflict awareness over a distribution of initial opinions and prove its convexity. See Appendix B.6 for details.
5.2
Mcasuring Conflict Awareness on Real-Worke Social Networks
5.2.1
Motivations and Experimental Setup
We the measure of conflict awareness defined in Sec. 5.1 to empirically investigate two important questions on the relationship between relevance and conflict reduction in link recommendations:
What is the conflict awareness of some of the popular off-the-shelf link recommendation al- gorithms? High conflict awareness (e.g. close to 1.0) means that the algorithm is effective at reducing conflict, and low conflict awareness (e.g. less than 0.2) means the opposite.
7

---

Raddle (reg sampinng pinng rate-d)
Reddtt (neq sampling (ate-
The (neg samplnng rate-9)
Twitter Insq sampling rabe=
bata
besa
besa
Data
Figure 2: Measurement conflict awareness recall for 13 recommendation algorithms on samples of Reddit and Twitter social networks. The x-axis the vy pressiive that controls class imbalance in the test set.
Enegativ links
Does more accurate link recommendation algorithm have higher conflict awareness? If we observe that for most recommendation algorithms the answer is affirmative, means that relevance and conflict reduction are positively correlated; if we observe the opposite, it means relevance and conflict reduction are incompatible in practice.
Datasets. We use two real-world datasets: Reddit and Twitter, collected by 39 one of the pioneering works that conduct empirical studies on the model. See Appendix for more details on how the network data and the initial opinions are generated for the two datasets.
Baselines. We test three groups 13 different link recommendation methods.
Unsupervised distance- based measures: Personalized PageRank [46). Katz Index 47 Jaccard Index [48], Adamic Adar [49]. Common Neighbors (50). Preferential Attachment (50 Resource
Allocation [5T]. They are among the most classic methods for link recommendations, whose
distance-based heuristics underpin many deep-learning-baane based link recommendation methods.
Self-supervised graph learning: Logistic Regression (with Node [52] embeddings input node features), Graph Convolutional Neural Network (GCN) [33. Relational Graph Convolutional
Nerual Network (R-GCN) (54), Graph Transformer [55]. SuperGAT (56). The last three one are GNN-based methods that achieved previous state-of-ther -fe-----ttt-tttt on link prediction task.
Conflict minimization solver: This is to solve the convex optimization problem defined by -II they find optimal weights for links be added with the sole goal of minimizing the conflict. However, it is crucial to note that this solver has total ignorance of relevance, i.e. it can't tt differentiate positive and negative links apart. Therefore, may actually end up recommending many negative (i.e. invalid) links that have no effect on conflict.
Evaluation pipeline. For each dataset, we randomly sample 100 positive links from the edge set, and B- 77 negative links from all disconnected node pairs; the negative sampling rate e [1, 10] is hyperparameter. The positive links are then removed from the network to reserved for testing, together with the negative links. It is crucial to note that in this setting (and in the real world), only positive link can be added to the social network. positive weights), it can't be added to the network. The whole process is repeated for 10 times with different random seeds.
negative link gets recommended (i.e. assigned
All links in the original network have unit weights, although the recommender is allowed to assign continuous weights to new links. As there are 3 positive links, we require that the total recommended weights must sum up to B, which is enforced through linear scaling of f's output. See Appendix C.5
Evaluation metrics. Besides conflict awareness, also measure the recall and precision @ 10 of each link recommendation method as proxies for "relevance".
Reproducibility: Our code and data can be downloaded from here Other configurations of the numerical experiment can be found in Appendix C.4
5.2.2 Result Analysis
Fig2 shows the measurement results of both conflict awareness and recall rate for the link recommendation algorithms on the two datasets. The precision@ 10 measurement results are in Appendix C The y-axis is the negative sampling rate 7). The results allow us to make the following observations.

---

First, we observe that the conflict awareness can vary lot for different algorithms under different settings. For example. on Reddit's social network, R-GCN's conflict awareness can be as high as 0.95 with 1 = 1, while Jaccard Index's 's conflict awareness is mostly below 0.2.
Second, we examine the effect of тj. In principle, a larger yj means it is harder to identify positive links in the test set. For both networks, we can see that the conflict awareness of most algorithms drop as goes up, though the four GNN-based methods seem to be slightly less affected. Similar trends can be observed from the recall plots (b) and (d), where GNN-based algorithmss stay quite robust as the task gets increasingly harder. These observations suggests that the ability suggest "relevant" links can be crucial for maintaining good conflict awareness, especially when the recommendation task is hard.
Third, we have interesting observations the "Conffict Minimization" algorithm: both networks, this algorithm consistently produces the worst recall among all algorithms - barely usable from the perspective of relevance. However, although there are not many relevant links in its recommen- dation, the algorithm still has the best conflict awareness most of the time. among the algorithm's 's recommended links, the few ones that are actually relevant (positive) are highly effective reduce conflict. In that sense, we can still clearly see the there exists a certain amount of misalignment between "relevance" and "conflict reduction".
6 Limitation: the Paradox of Conflict and Happiness
We found a limitation in the long line of existing works analyzing opinion conflict based on the FJ model, which work also inherits from. The conflict measure we've discussed far may not reflect user's 's happiness in their social engagement. Originally proposed in the seminal work [57], the happiness measure (or equivalently the unhappiness) quantifies the amount of mental pressure felt by people in their social engagement, as the sum of two terms: the amount of disagreement with friends (i.e. our disagreement term), and the amount of opinion shift between initial opinions and expressed opinions, i.e. internal conflict, defined as
I(G,s) -1=- =
VEV
We use sG) to denote the unhappiness of peo- ple over a social network G and initial opinions Fig. 3 illlutraaees the relationship of important concepts in the FJ model we've discussed so far.
Polatization (u
Disagreement 2(-1) (uc.o)
Internal Confiic Pot 21 179
shows that the common term, disagreement, shared by both measures of polarization and dis- agreement. Therefore, it seems likely that when one measure changes (say conflict drops due to the addition of a new link), the other measure should change in the same direction. Surprisingly how- ever, this is not true. In fact, the following theorem shows the two measures to always change in op- posite directions when network structure changes!
shows
Conflie
Unhappiness
Figure 3: Relationship of the important concepts in the Friedkin- Johnsenn opinion model.
Theorem 5. Given initial opinions s and social network G= EV, we have the following conser- vation law about conffict and unhappiness (notice the RHS is independent of the graph structure):
C(G,s) + ((G s) ST
(13)
Theorem 5 reveals a paradox: reducing conflict by modifying the structure of a social network always comes at the expense of more unhappiness of people. To resolve this paradox goes beyond this paper's 's scope, but would be a very interesting topic to study in the future.
7 Conclusion
In this work, we analyzed the relationship between relevance and opinion conflict in online social link recommendations. We present multiple pieces of evidence challenging the view that the two objectives are totally incompatible link recommendations. For future work, would extremely interesting to study recommendation algorithms that can combine the two features. We also conjecture that rigorous bounds can be derived for the conflict awareness of some classical link recommendation methods such as Peronalized PageRank and Katz Index.

---

Acknowledgement
The authors thank Eva Tardos and Sigal Oren for their helpful feedback on this work. This work is supported in part by Simons Investigator Award, Vannevar Bush Faculty Fellowship, MURI grant I91 AFOSR grant 19955001----183. ARO grant W911NF19-1-0057, a Simons Collaboration grant, and grant from the MacArthur Foundation.
References
[1] S. Kemp, "Digital 2023: Global overview report datareportal - global digital insights." Jan 2023- colubal-overvee-reepa
2023. [Online]. Available:
[2] Barberá, "Social media, echo chambers, and political polarization," Social media and democ- racy: The state of the field, prospects for reform, vol. 34, 2020.
[3] P. Liu, K. Shivaram, A. Culotta, M. A. Shapiro, and M. Bilgic, "The interaction between political typology and filter bubbles in news recommendation algorithms," in Proceedings of the Web Conference 2021, 2021, pp. 3791-3801.
[4] S. Lawrence and G. Crawford, Digital football cultures: Fandom, identities and resistance. Routledge, 2018.
[5] L. Amendola, V. Marra, and M. Quartin, "The evolving perception of controversial movies," Palgrave Communications, vol. 1, no. 1, pp. 1-9, 2015.
[6] H. Holone, "The filter bubble and its effect on online personal health information," Croatian medical journal, vol. 57, no. 3, p. 298, 2016.
[7] E. Pariser, The filter bubble: How the new personalized web is changing what we read and how we think. Penguin, 2011.
[8] K. Hosanagar, D. Fleder, D. Lee, and Buja, "Will the global village fracture into tribes? recommender systems and their effects on consumer fragmentation," Management Science, vol. 60, no. 4, pp. 805-823, 2014.
[9] T. Nguyen, P.-M. Hui, M. Harper, Terveen, and J. Konstan, "Exploring the filter bubble: the effect of using recommender systems on content diversity," in Proceedings of the 23rd international conference on World wide web, 2014, pp. 677-686.
[10] C. Vaccari, A. Valeriani, P. Barberá, T. Jost, Nagler, and J. A. Tucker, "Of echo chambers and contrarian clubs: Exposure to political disagreement among german and italian users of twitter," Social media+ sociery, vol. 2, no. 3, p. 16664221,, 2016.
[11] M. A. Hasan and M. J. Zaki, "A survey of link prediction in social networks," Social network data analytics, pp. 243 225, 2011.
[12] D. Liben-Nowell and J. Kleinberg, "The link prediction problem for social networks." in Proceedings of the twelfth international conference on Information and knowledge management, 2003, pp. 556-559.
[13] N. N. Daud, S. H. Ab Hamid, M. Saadoon, F. Sahran, and N. B. Anuar, "Applications of link prediction in social networks: A review," Journal of Network and Computer Applications, vol.
166. p. 102716, 2020.
[14] C. Musco, C. Musco, and C. E. Tsourakakis, "Minimizing polarization and disagreement in social networks," in Proceedings of the 2018 world wide web conference, 2018, pp. 369-378.
[15] L. Zhu, Q. Bao, and Z. Zhang, "Minimizing polarization and disagreement in social networks via link recommendation." Advances in Neural Information Processing Systems, vol. 34, pp. 2072-201 2084, 2021.
[16] S. Vargas and P. Castells, "Rank and relevance in novelty and diversity metrics for recommender systems," " in Proceedings of the fifth ACM conference on Recommender systems, 2011, pp. 109-116.
[17] P. Zhao and D. L.. Lee, "How much novelty is relevant? it depends your curiosity." in Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, 2016, pp. 315-324.
10

---

[18] M. Kunaver and T. Požrl, "Diversity in recommender systems a survey," Knowledge-based systems, vol. 123, pp. 154-162, 2017.
[19] Sá, V. Queiroz Marinho, A. R. Magalhães. T. Lacerda, and Goncalves. "Diversity vs relevance: A practical multi-objecctve study in luxury fashion recommendations," in Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2022, pp. 2405-2400
[20] M. Ge, C. Delgado Batteddea.......d. and D. Jannach, "Beyond accuracy: evaluating recommender systems by coverage and serendipity," in Proceedings of the fourth ACM conference on Recom- mender systems,, 2010, pp. 257-260.
[21] L. Chen, Y. Yang, N. Wang. K. Yang, and Q. Yuan, "How serendipity improves user satisfaction with recommendations? large-scale user evaluation," in The world wide web conference, 2019, pp. 240-250.
[22] N. E. Friedkin and E. C. Johnsen, "Social influence and opinions," " Journal of Mathematical Sociology, vol. 15, no. 3-4, pp. 193-206, 1990.
[23] H. Rainer and U. Krause, "Opinion dynamics and bounded confidence: models, analysis and simulation," " Journal of Artifical Societies and Social Simulation, 2002.
[24] R. A. Holley and T. M. Liggett, "Ergodic theorems for weakly interacting infinite systems and the voter model," The annals of probability, pp. 643 643-663, 1975.
[25] O. Askarisichani, F. Bullo, N. E. Friedkin, and A. K. Singh, "Predictive models for human-ai nexus in group decision making," Annals of the New York Academy of Sciences, vol. 1514, no. 1,
pp. 70-81, 2022.
[26] N. E. Friedkin and K. S. Cook, "Peer group influence," Sociological Methods & Research, vol. 19, no. I, pp. 122-143, 1990.
[27] N. E. Friedkin and F. Bullo, "How truth wins in opinion dynamics along issue sequences," Proceedings of the National Acudemy of Sciences, vol. 114, no. 43, pp. 11 380-11 1 385, 2017.
[28] N. E. Friedkin, P. Jia, and F. Bullo, "A theory of the evolution of social power: Natural trajectories of interpersonal influence systems along issue sequences." Sociological Science vol. 3, pp. 444 472, 2016.
[29] N. E. Friedkin, A. V. Proskurnikov. R. Tempo, and S. E. Parsegov, "Network science on belief system dynamics under logic constraints," Science, vol. 354, no. 6310, pp. 321-326, 2016.
[30] N. E. Friedkin, A. V. Proskurnikov, W. Mei. and Bullo, "Mathematical structures in group decision-making on resource allocation distributions," Scientific reports, vol. 9, no. 1, 1377, 2019.
[31] N. E. Friedkin, A. V. Proskurnikov, and F. Bullo, "Group dynamics on multidimensional object threat appraisals," Social Networks, vol. 65, pp. 157-167, 2021.
[32] O. Askarisichani, E. Y. Huang, K. S. Sato, N. E. Friedkin, F. Bullo, and A. K. Singh, "Expertise and confidence explain how social influence evolves along intellective tasks," arXiv preprint arXiv:2011.0710 2020.
[33] W. Ye, F. Bullo, N. Friedkin, and A. K. Singh, "Modeling human-ai team decision making," " arXiv preprint arXiv:2201.08 222.2999, 2022.
[34] A. De. S. Bhattacharya, P. Bhattacharya, N. Ganguly, and S. Chakrabarti, "Learning linear the 23rd ACM International Conference Conference on Information and Knowledge Management, 2014, pp. 401-410.
influence model from transient opinion dynamics." in Proceedings the
[35] C. Bernardo, L. Wang, F. Vasca, Y. Hong, G. Shi, and C. Altafini, "Achieving consensus in multilateral international negotiations: The case study of the 2015 paris agreement on climate change," Science Advances, vol. 7, no. 51, p. cabg8068, 2021.
[36] X. Chen, J. Lijffijt, and T. De Bie, "Quantifying and minimizing risk of conflict in social networks," in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 1197-1205.
[37] J. Gaitonde, J. Kleinberg, and E. Tardos, "Adversarial perturbations of opinion dynamics in networks," in Proceedings of the s ACM Conference on Economics and Computation, 2020. pp. 471-472.
11

---

[38] M. Z. Racz and D. E. Rigobon, "Towards consensus: Reducing polarization by perturbing social networks." arXiv preprint arXiv:2206.0890 08996, 2022.
[39] U. Chitra and C. Musco, "Analyzing the impact of filter bubbles social network polarization." in Proceedings of the 13th International Conference on Web Search and Data Mining. 2020, pp. 115-123.
[40] T. Opsahl, "Triadic closure in two-mode networks: Redefining the global and local clustering coefficients," " Social networks, vol. 35, no. 2. pp. 159-167, 2013.
[41] Y. Wang. P. Li, C. Bai, V. Subrahmanian, and J. Leskovee, "Generie representation learning for dynamic social interaction," in Proc. 26th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining Workshop, 2020.
[42] Y. Wang, Y.-Y. Chang, Y. Liu, J. Leskovec, and P. Li, "Inductive representation learning in temporal networks via causal anonymous walks," arXiv preprint rrXiv:2101.059/ 2021.
[43] P. Li, Y. Wang, H. Wang, and J. Leskovee, "Distance encoding: Design provably more powerful neural networks for graph representation learning," " Advances in Neural Information Processing Systems, vol. 33, pp. 4465 2020.
[44] H. Yin, Y. Wang, and P. Li, "Revisiting graph neural networks and distance encoding from practical view," arXiv preprint arXiv:2011.12228 2020.
[45] Y. Wang, P. Li, C. Bai, and Leskovec, "Tedic: Neural modeling of behavioral patterns in dynamic social interaction networks," in Proceedings of the Web Conference 2021, 2021, pp. 693-705.
[46] B. Bahmani, A. Chowdhury, and A. Goel, "Fast incremental and personalized pagerank," arXiv preprint arXiv: 1000. 2880, 2010.
[47] L. Katz, "A new status index derived from sociometric analysis." Psychometrika, vol. 18, no. 1, pp. 39-43, 1953.
[48] G. Salton, "Introduction to modern information retrieval," McGraw-Hilll, 1983.
[49] L. A. Adamic and E. Adar, "Friends and neighbors the web," Social networks, vol. 25, no. 3,
pp. 211-230, 2003.
[50] M. E. Newman, "Clustering and preferential attachment in growing networks," " Physical review
E, vol. 64, no. 2, 025102, 2001.
[51] T. Zhou, L. Lü, and Y.-C. Zhang, "Predicting missing links via local information." " The European Physical Journal B, vol. 71, pp. 623 030, 2009.
[52] A. Grover and J. Leskovec, "node2vec: Scalable feature learning for networks," in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 2016, pp. 855-864.
[53] T. N. Kipf and M. Welling, "Semi-supervised classification with graph convolutional networks," arXiv preprint arXiv: (900009907 2016.
[54] M. Schlichtkrull, T. N. Kipf, P. Bloem, R. Van Den Berg, I. TitoN, and M. Welling, "Modeling relational data with graph convolutional networks," in The Semantic Web: 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, Proceedings 15. Springer, 2018, pp. 593-607.
[55] L. Rampášek, M. Galkin, V. P. Dwivedi, A. T. Luu, G. Wolf, and D. Beaini, "Recipe for general, powerful, scalable graph transformer," Advances in Neural Information Processing Systems, vol. 35, pp. 14 14501-14515, 2022.
[56] D. Kim and A. Oh, "How to find your friendly neighborhood: Graph attention design with self-supervision." " arXiv preprint arXiv:2204.0453
2022.
[57] D. Bindel, J. Kleinberg, and Oren, "How bad is forming your own opinion?" Games and Economic Behavior, vol. 92, pp. 248-265, 2015.
[58] M. S. Bartlett, "An inverse matrix adjustment arising in discriminant analysis," The Annals of Mathematical Statistics, vol. 22, no. 1, pp. 107-111, 1951.
[59] P. Chebotarev and E. Shamis, "Matrix-forest theorems," arXiv preprint math/0602575, 2006.
[60] W. Watkins, "Convex matrix functions," Proceedings of the American Mathematical Society, pp. 31-34, 1974.
12

---

[61] W. N. Anderson Jr and T. D. Morley, "Eigenvalues of the laplacian of graph." Linear and multilinear algebra, vol. 18, no. pp. 141-145, 1985.
[62] A. Hannak, E. Anderson, L. F. Barreut S. Lehmann, A. Mislove, and M. Riedewald, "Tweetin' in the rain: Exploring societal-scale effects of weather on mood," in Proceedings of the Interna- lional AAAI Conference Web and Social Media, vol. 6,
2012, pp. 479-482.
[63] J. W. Pennebaker, M. E. Francis, and R. J. Booth, "Linguistic inquiry and word count: Liwe 2001," Mahway: Lawrence Erlbaum Associates, vol. 71, no. 2001, p. 2001, 2001.
13

---

Appendix
A
Reproducibility
Our code and data can be LitenfliitBeeee Reeee-eeeeeeeeeee-iieeee
downloaded from
Neur
To mitigate this risk, suggest social platforms take more cautious steps when deciding reduce the exposure of one person's ss content feed to another, such as additional algorithmic check in background, as well as more security measures guard against the hacking of platform's 's administrative authority. Researchers are also encouraged to study network structures that are more robust to attacks of such kind, as well as defense measures to be taken when such attacks actually happen.
B Proofs
B.1 Proof of Theorem
Proof. Let I+fe denote the Laplacian matrix of the new social network after adding a new link e (i, To prove (2, we invoke the Sherman-Morrise Formula (58) for computing the inverse of rank-l update to an invertible matrix. Notice that G+ = L b.bb Therefore,
C(G+e: 8) - C(G,s)
3"(( G+e) - (T+ L))
=sT b.b+++++bb)+----
L)-
(I+ b,b, ( (1+
1 67 (T -.)
16 (1 L)
(1+ L)-Ibe
(z, (2)=)))²
1 69 (1 -)-bbe
L is positive semidefinite, (I L)-1 is also positive semidefinite. Therefore, 1 b2 L)- is (=)=2;)² positive, and so (1+ S O.
To prove Eq. we further note that
(1+
Be R,, [
1 65 (1 -be
6T (1++ -1s"
-)-
E.I
1 67 (I L)-1be
(T+ T.)- be
67 (I L)-1be be
1 1+b (T T.)-1be
021(T I.)- -bbbl
1+b7 (I (I+ -)-1be $ 0.
B.2 Proof of Theorem 3
Proof. Let = Lt and let matrix be the co-factor matrix of M, then (1+L)-1= |M| CC
Therefore, (Z'( -)-"b- IMI'' (C.s + CCj - Cij C Cj²). |M] is the determinant of matrix M. (59 presents result that |M] equals the total number of spanning rooted forests of G, and City equals the
total number of spanning rooted forests of G. which node J and y belong to the same tree rooted at a.
The theorem is proved by substituting this previous result back into M Cj -Cy -C,). D
14

---

B.3
Proof of Theorem
Proof.
o bblb =² Σ (IM Cix -
KeV
E (Cis Cyk)?
kEV
Since M symmetric, we have Ca+ Nix Ct Ni: = Ckk, Cyk+ + +N Cky + NNk Ckk. where CRa according to [59] is equal to the total number of spanning rooted forests where node & is at the root of the tree which & belongs. Joining the two equations, we have Ca Cjk: Nix jk Therefore.
o (((I =
O²N~2
E (UNx-Nip NNnx²²
RVV
B.4
Proof of Corollary
1
Proof.
The correctness quickly follows from substituting Equations into Equation
B.5 Proof of Proposition 1
Proof. To show that the objective is convex, we resort to the result in [60]. Example 9: x 1 is matrix convex the of all nonnegative invertible Hermitian matrices. Obviously / L L, is nonnegative, invertible and symmetric, so it is a matrix convex. Therefore, the objective is convex. Any convex combination Laplacians is still Lapalacian. The trace of any convex combination of of matrices cannot exceed the trace of any members. Therefore, the feasible region is also convex. O
B.6 Expected Confliet Awareness
Definition 2. Given social network G and a budget 3 0, the conftict awareness over Expectation (CAE) of a link addition function f(e; G.3) is likewise defined as:
[C
CAE(F) Ex.E.[]
(14)
where
A,E,[C] ( -((+L)))
(15)
B, = min T.
A,E,[C]
(16)
subject to
Ly L (Laplacian constraint)
(17)
Tr(L,) 28 (budget constraint)
(18)
The definition of A E.[[ above is consistent with that of ACC in Definition in the sense that they satisfy [, = /, P(s) A,C de
Proposition 2.
Proof. Let A be any square matrix of the same shape as L. Then ʃ. (()))) Asd, (Asss (p(s)sT(As)) d, = ((s))T((As)s") d, [{s(s)Tr(A(ss'' ))d, d, Tr(A ((s)ss ds)
Tr(A(o²I)) (AT. By substituting A (I L+ Ly) and (I+L)-+ into Eq. respectively, the proposition is proved.
Proposition 3. In Definition 2 E,] is also the objective of a convex optimization problem.
Proof. From the proof for Proposition 1 suffices to only show that the E, Equation 15
is convex in I, given other variables fixed. Notice that we mentioned A y [C] p(s) 4 d.. which p(s) 2 0, AyC can be viewed as function of T,g and 8, and is convex in I.f given to be further fixed. Therefore, the integral [C] is also convex in Ly-
15

---

B.7 Proof of Theorem 2
Proof. 0et X S S2 ... S An be eigenvalues of in ascending order; the eigen decomposition of L= UAU where A ([A1. and U is the corresponding orthornormal matrix satisfying UUT I. Notice that L)+ U((+A)-
C(Gu.s) C(G,s)
s
8 SUUTS 8
s" L1
STU AA-
let s' U. s, and further notice that since have assumed be zero-centered (see Sectior 2)
s = 1 = O. We can further rewrite:
c(Go. C(G,s)
TT (T +
Σ
Σ 8 2
(T++A)-1- A)-18'
Ei=1 (1 11)-11
Σi=2 (1 X; ) 12
It is not hard to see that
1 An C(Go, s)
s(G,s) 1 A2
For the upper bound, [6 shows that A, (ij (d: dj); ); for the lower bound, we know from Lemma A. of (38) that X₂ 2 &dmiingg where dmii is the minimum node degree in G; he is the Cheeger constant of G. Substituting these back into expression above, we have (ix)e.)) de
d,) c(Gg.))
+ dmmi 22 2 1.
C(G.s)
B.8 Proof of Theorem 5
Proof. Notice that C = 8T L)" = 1 = = s (I 1)-1)²
([-((++)-))s Therefore, C C++ s"'s which is a constant.
C
Experiments
C.1 Verifying the Direction of Conflict Change (Theorem
We computationally verify that opinion conflict always gets reduced when new link is added to the network. We use six datasets, including three synthetic networks and three real-world social networks. The synthetic networks are, a vadōs-Réény' Graph (n 100, 0.5), path graph (n = 100), a 10 by 10 2D-grid graph. The real-world networks are, the Karate club social network, Reddit, and Twitter (as introduced in Sec C.3). For each network, we compute the amount of conflict change caused by adding a link between every pair of disconnected node the graph, with each link replaced one time. Figure 4 shows the distributions of the amounts of conflict conflict for all the six datasets.
can see that they are on the negative side the axis. This result validates the negative sign in Theorem @ and demonstrates its broad applicability.
C.2 Verifying Conflict Contraction (Theorem
We start with an empty graph with N nodes. In each iteration, one edge is randomly added between two disconnected nodes; then compute the the lower bound, the upper bound, and the conflict contraction rate as given in Theorem The iterations stop when no pair of nodes are left disconnected (i.e. the graph is complete). We choose N = 20 in this experiment computing the Cheeger constant term is NP-hard.
Figure 5 plots the lower bounds, the lower bounds, the upper bounds, and the conflict contraction rates, with respect to the increasing numbers of edges the graph. We can see that the conflict contraction rates are indeed lying in between the two bounds. The gap exists because we cannot exhaust all the possible graphs on 20 nodes. Nevertheless, this experiment provides good piece of evidence that Theorem ii correct.
16

---

Erdös-Rényi Graph
Line Graph
Grid Graph
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
-.000040000033
0,0000
-0.25
-0.02
Karate
Reddit
Twitter
0.2
02
0.2
0.0
0.0
0.0
-0.020
-0.015
00.010
-0.005
0.000
-0
-0
-0.0000
-0.0006
-0.0004
-0. 0.0002 0.0000
1e-5
Figure 4: Computational validation for Theorem
Conflict Contration Rate
Bounds
35
30
10
125
Number of Edges
Figure 5: Computational validation for Theorem
C.3 Dataset and Preprocessing
Twitter. The dataset is extracted from number of tweets relevant the Delhi Assembly elections 2013. In the preprocessing, only the largest strongest-connecte component (SCC) gets retained, which contains 548 users and 3638 undirected edges; each edge represents pair follower and followee. The initial opinions (s) were mapped by sentiment analysis tool designed for Twitter 62) based on each user's first-hour tweets the record window.
Reddit. The dataset extracted from the subreddit of "Politics" between 07/2013 and 12/2013. Similar to Twitter, only the largest SCC is retained, containing 556 users and 8969 edges. An edge exists between two users both of them posted in the same subreddit other than "Politics" during the aforementioned time period. The initial opinions were mapped using the standard linguistic analytics tool LIWC (63
C.4 Configurations
We run all experiments on Intel Xeon Gold 6254 C 15GGH with 1.6TB Memory. out 13 methods being evaluated for the conflict awareness metric involve hyperparameter settings. They can also be found our code: we use alpha=0.5 for Katz; alpha=0.85 0.8 for Personalized PageRank; for node2vec, use 64 node embedding dimensions, context window 10, 2, 0.5; for GCN
17

---

and R-GCN, we use two layers with 32 as hidden dimensions, followed by 2-layer MLP with 16 hidden units; for SuperGAT, we use two layers with 64 as hidden dimensions; for Graph Transformer, we use two layers with 32 as hidden dimensions, and attention head number of 4.
C.5 Linear Scaling of the Output
To make sure that the weights of all recommended links sum up B, linearly scale each link recommendation algorithm's ' output by normalizing constant: Notice that each link recommendation algorithms essentially a scoring function on the links. For model its output weight wn (e)
of each recommended link follows the normalized form wp(e) (e) E. E. original score that model / assigns to link
5n(c) where sA (e) is the
C.6 Precision@ @ 10
Reddit (beta-20)
Reddit (neg sampling rate-9)
precison''s
precisionng
Aramiclear
Commontie
0.-
jeccard
Katz
nog sampling rate
Logabic ession node2ves
Contict Ninmzation
Pesona boo Pegetank
Preferental Attccmmnt
Ressurce Alacation
Twitter (beta=20)
Twitter (neg sampling rate=9)
GCN
R-GCN
Graphitarsfomee
SupercAl
0.8
prectiieeet
n.
precston181
20
neg sampling rate
beta
Figure 7: Precision @ 13 link recommendation algorithms on samples of Reddit (upper) and Twitter (lower) social network. These plots supplement the recall measurement in Fig, 2 as another proxy for "relevance".
D Broader Impacts
Our analysis reveals the types of social links that, when added to the social network, can most effectively reduce polarization and disagreement. While this result itself for a good cause, potential risk exists when one interprets it into the opposite direction: we now know certain types of links that, when removed from the social network, can most effectively increase polarization and disagreement. This could be abused by (authoritative) adversarial to increase polarization and disagreement by diminishing social ties among certain people, or even disconnecting them.
18


Reviews:
[{"review_id": "5DssuQHItJ", "reviewer": "Reviewer_tPqS", "summary": "Authors theoretically analyze the conflict in the social network under Friedkin-Johnsen model. Those theoretical analysis demonstrates that the addition of links reduces the conflict. In addition, the network meaning of links to minimize conflicts is presented with theoretical support. Finally, based on the conflict-aware score, authors analyze several existing link recommendation algorithms and show that the relevant link recommendation is not fully introducing conflicts.", "questions": "- In reality, relevance may affect the opinion formation. For example, in Eq (1), a_ij can be correlated with the relevance score. It would be great to see how Section 5 analysis is affected when we incorporate this.\n- Figure 2 shows downward plots in general. What would be the interpretation?", "limitations": "Authors address that the argument is under the FJ opinion formation model. Also, authors introduce the paradox of conflict and unhappiness, which cannot be analyzed by the manuscript.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Thorough analysis has been made with implying the insightful explanation on the social behaviors.\n- Well-defined conflict-related measurements enable the theoretical analysis as well as the empirical measurements from real-world algorithms and datasets.\n- Authors propose the conflict awareness that can represents the level of conflict that a given link recommendation algorithm introduces.", "weaknesses": "- The claim that the addition of links decreases the conflict is somehow obvious by the opinion formation design. By the mechanism that a give node's opinion is formed by smoothing neighbors' opinions, the addition of links implies more chances of smoothing more opinions.The given model does not have the mechanism of opinions going extreme such as taking the max votes from neighbors. It would be interesting to see if the similar results hold if the aggregation of neighbor opinions is different.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful feedback! \n\nQuestion 1:\n\nWe agree with the reviewer that relevance affects opinion formation: if a link has high relevance, it may likely boost opinion exchange between the two people connected by that link. The a_ij in Eq.1, defined in lines 111-113, can generalize to this case as it represents the strength of social influence. In fact, our evaluations in Sec.5 exactly use (scaled) relevance scores in recommendations to increment the values of a_ij’s. Please see Appendix D.4 for more details.\n \nQuestion 2:\n\n(Please also refer to Lines 342 -347 for detailed interpretations) This downward trend shows a degree of alignment between relevance and conflict detection in link recommendations, and here is why.\n\nThe negative sampling rate eta on the x-axis stands for the ratio between the number of negative (fake) links and the number of positive (real) links in our evaluation set. It can range from 1 to 9 in our setting. The larger the eta, the harder it is for a recommendation algorithm to successfully recommend a link that the user will like and accept. Notice that, if a user doesn’t want to accept a recommended link (in other words, the link is not relevant), then that link will have no effect in reducing conflict. Because social links can help reduce conflict as we’ve shown, being able to suggest more relevant links with a fixed budget will generally help reduce more conflict, and thus improve Conflict Awareness. Therefore, for each recommendation algorithm, as eta goes up:\n1.  it becomes harder to recommend links that users like to accept (i.e. relevant links),  so the recall rate goes down (the second and the fourth plot)\n2. the conflict awareness also has a downward trend (the first and the third plot)\n \n(Noted by another reviewer, we found that the four labels in the second plot of Figure 2 are misplaced. We have revised them. Please feel free to refer to the uploaded PDF for a better view.)\n"}, {"review_id": "rrDWosCLP5", "reviewer": "Reviewer_dCzc", "summary": "With the flourishing of online social media and social networks, the effects of polarization and disagreement brought about by link recommendation methods have become increasingly pronounced. Currently, a more widespread view is the filter bubble theory. But the empirical evidence to support him is limited, and there is a lack of detailed understanding of the strength that the filter bubble effect caused by social recommendations. To deal with these issues, this paper explores the theoretical evidence and principled features of relevance and conflict in online social link recommendation.\nFirst, the paper investigates the amount of change in opinion conflict caused by adding general links and concludes that purely adding social links does not increase opinion conflict, also it proposes two criteria for finding conflict-minimizing links in social networks; then the paper introduced Conflict awareness to evaluate the ability of a link recommendation model to reduce conflicts; finally, it discussed the limitations of the above theoretical analysis based on the FJ model.\n", "questions": "This paper analyzes the relationship between relevance and opinion conflict in online social link recommendation and offers a different view on its utterly incompatible perspective. This paper has the following problems:\n\n1. the title of 2.1 is more appropriately changed to Social Network Model;\n2. the text in Figure 2 should be labelled for the lines, but the second small figure in Figure 2 is confusingly labelled;\n3. The theoretical part of this paper is very rich, but the space of the experimental part is limited, the configuration of the experimental environment is not explained, and only the experiments on conflict awareness are given. Is it more persuasive to put Appendix D5 in the experimental part of the main text?\n4.In the conclusion of p241-243, does this distance refer to a specific distance calculation or does it refer generally to a universal distance (Are other distances applicable？).\n5. The formulae should be unified and standardized, and the formulae in limitations are not labelled.\n6. The number of references is too many, and the number of references in the last five years is few.\n", "limitations": "This paper adequately acknowledged the limitations, with a detailed description of the limitations", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strengths of this paper are the following:\n1. originality\nThis paper explores theoretical evidence and principled features of the effects of polarization and disagreement brought about by link recommendation algorithms in social networks. It also provides the first analysis of the question of whether the most likely accepted links in social networks are fundamentally different from those that reduce conflict by using the Friedkin-johnsen model of opinion dynamics. This paper is of good originality.\n2. quality\nThis paper has a clear research question, rich theoretical analysis, solid experiments, and analysis of the limitations of the method, which is of high quality.\n3. clarity\nThe paper is clear, logical and well organized.\n4. significance\nThis paper is the first to examine whether the most likely accepted links in social networks are different from those that reduce conflicts, and analyzes the relationship between relevance and opinion conflict in link recommendation, challenging the idea that the two are incompatible.\n", "weaknesses": "The theoretical analysis in this paper is rich, the experiments may be limited in space, and it is limited in presentation, but it is necessary to introduce the corresponding experimental detail and experimental settings, please increase the representation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful feedback!\n\nQuestion 1:\n\nWe will follow the reviewer’s advice to adjust the title of Sec.2.1 to “Social Network Model”\n \nQuestion 2:\n\nWe will follow the reviewer’s advice to relabel the lines for the second figure in Figure 2.\n \nQuestion 3 (and Weakness):\n\nThe distance term in Line 241-243 refers to the one being defined in Theorem 3, Eq. (5): conceptually speaking, it is a type of distance associated with the number of spanning rooted forests between every node in the graph and each of the two nodes of the link.\n \nWe will follow the reviewer’s advice to further increase the presence of experiments in the main text:\n\n1. We agree that Appendix D.5 can be moved to the main text.\n\n2. We will briefly introduce the result of Appendix D.1 and D.2 in the main text.\n \n3. Additional configurations of the experiments: We run all experiments on Intel Xeon Gold 6254 CPU@3.15GHz with 1.6TB Memory. 7 out of the 13 methods being evaluated for the conflict awareness metric involve hyperparameter settings. They can also be found in our submitted code: we use alpha=0.5 for Katz; alpha=0.85 for Personalized PageRank; for node2vec, we use 64 as node embedding dimensions, context_window=10, p=2, q=0.5; for GCN and R-GCN, we use two layers with 32 as hidden dimensions, followed by a 2-layer MLP with 16 hidden units; for SuperGAT, we use two layers with 64 as hidden dimensions; for Graph Transformer, we use two layers with 32 as hidden dimensions, and attention head number of 4.\n \n4. We can also provide more experiments if requested by the reviewer.\n \n\nQuestion 4:\n\nWe will follow the reviewer’s advice to further unify the formulae and label the one in the Limitations section.\n \nQuestion 5:\n\nWe will follow the reviewer’s advice to reduce the number of references and replace some of the old ones with their recent follow-up works. For example, we will reduce some references in line 71.\n"}, {"review_id": "VDxz7O50ak", "reviewer": "Reviewer_tBHa", "summary": "This paper motivates that previous works have studied the two important aspects providing relevance and reducing conflict mainly in isolation, thus aims to explore the relationship between them. The paper uses FJ model from opinion dynamics as base model to first derive a closed form expression for quantifying changes of conflict, which is then used to analyze the conflict reduction effect caused by link addition. Based on the analysis, the paper then characterizes the conflict-reducing links and how these align with relevant links. To put the analysis in practice, a metric termed conflict-awareness is proposed to quantify the alignment between relevance and conflict minimization. The proposed metric is applied to various link recommendation algorithms on two real-world social networks. The findings show that some more accurate algorithms are indeed better at reducing conflict.", "questions": "* How would the paper been positioned given the PNAS 2021 paper?\n* About the limitation of the proposed approach, I am wondering whether any observation can be made by dropping the equilibrium assumption of the Friedkin-Johnsen model? It would be interesting to analyze the conflict in the network form the time point of adding a link until the equilibrium is reached.\n* F&J model assumes the aggregated opinion would be assimilated internally, but in some cases when introducing two opinionated nodes to each other, backfire could happen. Would this type of effect complicates the analysis? or a more vague question, how would the proposed model align with the logged events / conflict proxy measures in real world data?", "limitations": "* The authors pointed out two constraints: a paradox that reducing conflict could potentially stress users, and the choice of using directed versus undirected graphs for studying opinion dynamics, both limitations arising from the use of the FJ model.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The idea of analyzing the trade-off between relevancy and conflict in link prediction using Friedkin-Johnsen model is interesting and new to my knowledge.\n* Design choices of the presented analysis are properly justified.\n* The paper is easy to follow.", "weaknesses": "* The main claim in abstract \"To this date, however, we have very little understanding of how these two implications of link formation relate to each other...\" is not fully justified. A 2021 PNAS paper titled \"Link recommendation algorithms and dynamics of polarization in online social networks\" also tackle the issue of polarization and conflict in online social networks, specifically exploring the role that link recommendation algorithms play. Without establish the link to this 2021 paper as well as the papers mentioned therein, the main claim appeals unconvincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful feedback!\n\nWeakness and Question 1:\n\nThe PNAS 2021 paper takes a simulation-based approach to study polarization change caused by social link substitutions (i.e. “rewiring” in their term). Our paper takes a theory-driven approach to study the change of social conflict (polarization + disagreement) caused by social link additions. Our paper is related in topic to this PNAS paper, but it differs from it in several crucial ways, as follows:\n\n1.  Subject of study. The PNAS paper focuses on polarization, while our paper studies [polarization + disagreement] as an integral proxy for social cost.\n\n2.  Methodology. The PNAS paper draws conclusions primarily based on computational simulations over a fixed number of social network samples. Our analysis is driven by theoretical analysis, which allows us to make claims that quantify over all networks, rather than just the networks in a set of simulation runs; our results are then supported by a number of computational experiments.\n\n3.  The belief about how a recommended link changes a social network. The PNAS paper makes the assumption that, for every new link about to be added, a (random) existing link must be deleted simultaneously, termed as “rewiring”. Our work adopts an approach that more closely matches link recommendation in practice, where clearly links can be added without another link correspondingly being deleted; a newly added link can (proportionally) diminish the weights of existing links in the neighborhood, but need not result in any deletions.\n\nPoint 2 is most prominent, since it means that the PNAS paper is not making any general claims about arbitrary networks that could then in principle be compared with ours.  For example, their work cannot guide the search for links that can reduce online conflict most effectively (and our Theorem 3 and Corollary 1 address this). They also cannot explain if the observed trend of conflict change caused by link recommendations applies universally, and why. This is also the main reason for our abstract to mention that we have limited knowledge about the relationship between relevance and conflict in online social recommendation. (We are happy to modulate this statement though if the reviewer wants to)\n \n \nQuestion 2:\n\nWe assume that the reviewer is primarily interested in theoretical insights into the pre-equilibrium states of the conflict measure. We acknowledge that this is an underexplored area with some technical challenges for theoretical analysis. In our uploaded one-page pdf, we provide a preliminary analysis that derives the pre-equilibrium conflict with regards to s, L and the number of iterations t. We note that the quadratic matrix takes the form of power iteration and maybe further simplified by being substituted by a polynomial of the eigenvalue matrix of the adjacency matrix. We conjecture that this expression will decrease if we add a new link to G, consistent with the conclusion of our Theorem 1. However, we acknowledge that at this point the full rigorous proof remains unclear to us.\n\n\nQuestion 3:\n\nRegarding the backfire effect:\n\nWe agree that the backfire effect is very interesting to analyze. In the current FJ model, the level of backfire is quantified by the disagreement term. The consequence of backfire can be interpreted differently by different people:\n\nIf one believes that backfire would have a repulsive effect on opinions, a recent 2021 paper “Opinion dynamics with backfire effect and biased assimilation” extends the FJ model to incorporate this effect. This extended FJ model shows that backfire can lead to polarization.\nIf one believes that backfire leads the two disagreeing people to simply closing up the channel of conversation, then this effect is captured by bounded confidence models such as the Hegselmann-Krause model.\n\nWe note that, due to great technical challenges in analyzing nonlinear dynamics, in either case of the above there is very limited follow-up work that provides principled insights into how “relevant” links added to the network may change the conflict. But we do agree that it would be extremely interesting to study in the future.\n \n\nRegarding FJ model’s empirical validity:\n\nAs the references presented in lines 69-71: to this date FJ model is the only opinion dynamics model on which a sustained line of human-subject experiments has confirmed the model’s predictions of opinion changes. For example, a 2017 PNAS paper [27], shows that a variation of FJ model helps accurately predict a total of 1,288 people’s opinion dynamics, and similarly by a Science paper in 2016 [29]. Another paper [35] in 2021 Science Advances further shows that the FJ model well fits to the data of 2015 Paris negotiation on climate change and helps identify key leadership parties. In conclusion, we believe that the FJ model, despite being simple, is a highly practical model to serve as the base model for analysis.\n"}, {"review_id": "o4X3gfMAGo", "reviewer": "Reviewer_4FjV", "summary": "The paper analyzes the relationship between relevance and opinion conflict/disagreement on online social media platforms, particularly in link recommendations. Using the Friedskin-Johnsen model that models opinion dynamics, the paper shows how link additions change online conflicts and characterize the gap in conflict reduction, depending on the reduced link recommendation. The paper evaluates their approach using real-world datasets, obtained from previous work, from Twitter and Reddit.", "questions": "1. Can the proposed approach be applied to directed graphs? If yes, what was the rationale for using undirected graphs in this work?\n2. Can the proposed approach be applied when considering that there is a separate entity (i.e., recommendation algorithm) responsible for the content delivery to users?\n", "limitations": "The authors have addressed some limitations of their work. However, I strongly encourage them to have a look at the weaknesses part of this review and expand their limitations part with the two points that are described.\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper focuses on an important and timely problem related to online polarization. I liked that the paper presents all the necessary background information about their models, as well as the assumptions that they made. Also, I believe that evaluating the proposed approach on multiple social networks and multiple recommendation algorithms makes the paper and its findings more robust. \n", "weaknesses": "I have a couple of concerns with this paper. First, the formulation of the social network as an undirected graph is not very representative of what is actually happening on popular social networks like Twitter. In reality, the social network is undirected, which raises the questions on how the presented results might change when considering the fact that the graph is undirected instead of directed. I suggest to the authors to expand their discussion on this point in the paper.\n\nPerhaps more importantly, the paper overlooks a substantial shift that happened in social media platforms. Recently, we are observing the use of AI recommendation systems that are used for recommending and delivering content to the end-users. That is, people are exposed to content mainly based on the recommendation algorithm and, to a lesser extent, to content that is coming from people that a user follows or are friends with (e.g., see “For You” algorithmic feeds in Twitter, TikTok, etc.) These recommendation algorithms are becoming an integral part of most popular social networks nowadays. Given this, I am wondering whether the proposed approach can even be applied on this use case or how the presented results change when considering that there is an algorithm that determines what each user sees. I suggest to the authors to discuss this aspect and whether the proposed approach can be leveraged to study the same problem under these considerations.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful feedback!\n\nWeakness 1 & Question 1:\n\nWe agree with the reviewer that there has long been a debate on whether directed graphs should be used instead. We also understand that a key concern of the reviewer is that undirected graphs may fail to capture the asymmetric social influence between two connected people, e.g. an internet celebrity and her follower, on Twitter.\n\nHere, we explain why we used undirected graphs in the context of FJ model, which also accounts for the existence of a long line of work on FJ model which has made the same choice as ours: In FJ model, an undirected link does not imply symmetric social influence in both directions. For each link, the amount of influence carried forward by that link is normalized by the “social presence” (degree) of the destination node. Symmetry is thus broken because the two destination nodes can have different degrees. Here is an example to further illustrate this:\n\nPerson A, who is an internet celebrity with 1M followers, is followed by person B, who is an ordinary person with 10 friends in total. Then:\n\n1.  A directed graph denotes this relationship as A --> B, meaning that the social influence primarily goes one-way from A to B.\n\n2.  An undirected graph in FJ model denotes this relationship as A --- B. However, according to Equation (1), the influence of B’s opinion on A’s has weight 1/11, and the influence of B’s on A’s has weight 1/1000001. Therefore, FJ model captures that A’s influence on B is 90909 times stronger than the B’s influence on A. In other words, the social influence still primarily goes from A to B.\n \nWe would be happy to follow the reviewer’s advice to expand Part II of our “Limitations” section (Sec. 6) by the additional discussions above.\n \nWeakness 2 & Question 2:\n\nYes, the proposed model can still be applied when considering content delivery to users. In fact, this is one of the main scenarios being covered by the FJ model, and we appreciate the reviewer for asking for clarification on this: FJ model defines a social link to be any media that carries social influence. This is a more general concept than the social links defined by a concrete relationship of “friend” or “following”. While being “a friend” with someone can certainly be modeled by a social link in the FJ model, being passively exposed to content from someone unknown (and potentially leave a comment below)because of the recommendation system can also be modeled by a social link. Tiktok’s “For You”, as mentioned by the reviewer, often recommends content from other unknown people, including internet influencers.\n\nIn an even more general sense,  the spirit of FJ model can extend to the case where the recommendation system only recommends news or polls — things that are not attached to any particular individuals.  A great example is the “What’s Happening” of Twitter, which primarily recommends trending tags. In this case, the influence of one person to another is passed on in a more implicit manner, due to the “co-views”: two people that view the same content essentially becomes more connected to each other because they are influenced by the same content, have a chance to read each other’s comments, and may even start a conversation. \n"}]

Author rebuttal:
Dear reviewers and meta-reviewer,

We sincerely appreciate all the reviewers for reading our work and for providing us with the great feedback! We have responded to each reviewer separately below. Our one-page pdf for rebuttal is also uploaded here. We very much look forward to engaging with all the reviewers in the discussion phase!

With all the best regards,

Authors of Paper 9519

Meta-review: The paper analyzes the relationship between relevance and conflict in online social link recommendations.
The paper shows that relevance and conflict reduction are not always incompatible, but also not always aligned, and proposes a measure of conflict awareness to evaluate the trade-off between them.

The reviewers found the paper to be clear and well-structured, and the analysis to be thorough.

The reviewers also provided multiple suggestions including discussing the limitations of the proposed approach and exploring other application to directed graphs and recommendation algorithms. The authors are encouraged to follow these suggestions to further improve the paper.
Decision: Accept (poster)