Minimizing Polarization and Disagreement in the Friedkin–Johnsen Model with Unknown Innate Opinions

1 Introduction

The synergetic effect of natural homophily and the algorithms employed by social media platforms, e.g., who-to-follow recommender systems and "feed" content rankers, largely constitutes the information diet of social media users, aligning it with their own opinions. This, together with the natural tendency to confirmation bias [Del Vicario et al., 2017], leads to the so-called "echo-chamber" effect [Quattrociocchi et al., 2016; Cinus et al., 2022], where individuals with similar mindsets reciprocally reinforce their pre-existing beliefs, which in turn leads to polarization [Nikolov et al., 2015; Pariser, 2011]. The rising awareness of the societal risks of extreme polarization driven by social media has spurred a great deal of research on algorithmic interventions aimed at mitigating these harmful effects [Hartman et al., 2022; Garimella et al., 2018; Aslay et al., 2018; Garimella et al., 2017; Tu et al., 2020]. While the bulk of this literature focuses on a static setting, a growing body of work takes into consideration the dynamic nature of the underlying opinionformation process [Musco et al., 2018; Cinus et al., 2023; Chen et al., 2018; Zhu et al., 2021; Xu et al., 2021], in particular adopting the widely used Friedkin-Johnsen (FJ) opinion-dynamics model [Friedkin and Johnsen, 1990].

Background and Related Work. In the FJ model, social media users are depicted as nodes in a network and social ties are represented by edges. Each individual has an innate opinion, which may differ from their expressed opinion on social media, due to various factors, such as social pressure or fear of judgement. The model operates through an iterative process where users adjust their expressed opinions by taking a weighted average of their own innate opinion and the expressed opinions of their connected peers. It is well known that the equilibrium state of expressed opinions has an analytic form based on the Laplacian of the network and the innate opinions [Musco et al., 2018]. Due to its linear algebraic nature, the model has inspired several optimization problems involving susceptibility [Abebe et al., 2021; Marumo et al., 2021], stubbornness [Xu et al., 2022], exposure timelines [Zhou et al., 2024], and adversarial attacks [Tu et al., 2023]. Additionally, the model has led to some generalizations such as randomized interactions [Fotakis et al., 2016], dynamic social pressure [Ferraioli and Ventre, 2017], and discrete opinion settings [Chierichetti et al., 2013; Auletta et al., 2016].

In the literature on optimization problems under the FJ model, the seminal work of [Musco et al., 2018] introduced the problem of minimizing the sum of polarization and dis-

by intervening the weights of edges, and designed a polynomial-time approximation scheme based on the convexity of the objective function. Specifically, they investigated two problems: the first problem requires to find a weighted undirected graph that optimizes the objective function, given a total edge-weight budget and without considering a specific input network, while the second aims to optimize users' innate opinions. Following up on this work, several modeling and intervention strategies have been explored [Chen et al., 2018; Abebe et al., 2021; Zhu et al., 2021; Cinus et al., 2023; Zhou et al., 2024; Xu et al., 2021].

Most relevant to our work, [Cinus et al., 2023] recently extended the problem of [Musco et al., 2018] to general directed networks, where the intervention is on the weights of out-going edges of each node, i.e., rebalancing the relative importance of the accounts that the user follows, so as to calibrate the frequency with which the contents produced by various accounts are shown in the social feed of the user.

Our Contributions. All of this body of work on opinion optimization under the FJ model assumes that the innate opinions of the nodes are all known and given as input. However, in practical scenarios, obtaining such information is a task inherently imprecise and expensive. For example, analyzing user opinions on a controversial topic (e.g., COVID-19 vaccination or Brexit) on a social media platform would require either large-scale surveys or extensive behavioral analysis (e.g., posts, reposts, and likes on platforms like X). Furthermore, even in scenarios in which one is able to reconstruct all the opinions, how the inherent error in such opinion reconstruction influences the performance in the opinion optimization task, has not been addressed in the literature.

In this paper, to fill this gap, we consider a series of opinion optimization problems without the full knowledge of innate opinions, and tackling the budgeted optimization problems, where we can query the innate opinions of only a limited number of nodes. As objective functions to be minimized, following [Chen et al., 2018; Musco et al., 2018; Zhu et al., 2021; Cinus et al., 2023], we consider polarization, disagreement, and the sum of the two in both directed and undirected networks, for a total of six different objectives. As an intervention mechanism, following [Cinus et al., 2023], we consider re-weighting the relative importance of the accounts that each user follows.

A crucial step our solution is to effectively reconstruct the innate opinions of nodes that we did not query. [Neumann et al., 2024] studies opinion estimation in the FJ model. Their estimation approach is not directly applicable to our set of opinion optimization problems, which require gradient descent methods [Musco et al., 2018; Cinus et al., 2023]. A (non-trivial) adaptation of their algorithm would require numerous evaluations of both the objective values and the gradients across different solutions, resulting in a significant computational cost. Finally, [Neumann et al., 2024] assumes to have access to an oracle for the expressed opinions (which we do not have) and consider only undirected networks, while we study the optimization problems also on directed graphs.

Roadmap. In §2, we provide the necessary background and introduce the six objective functions we consider. In §3, we propose a pipeline that integrates innate opinion reconstruction with opinion optimization and theoretically characterize the objectives in terms of convexity and Lipschitz continuity, deriving their solvability and an upper bound on optimization error based on opinion reconstruction error. In §4, we present methods for selecting nodes to query their innate opinions and reconstructing the opinions of unqueried nodes. For node selection, we use heuristics based on centrality measures. For opinion reconstruction, motivated by the strong homophily of innate opinions in real-world networks, we apply strategies including label propagation [Zhu and Ghahramani, 2002], graph neural networks [Kipf and Welling, 2017], and graph signal processing [Lorenzo et al., 2018]. Finally, in §5, we present experiments on synthetic and real-world datasets with up to 1.6 million edges. Our key finding is that opinions can be effectively optimized even with limited information about innate opinions, using appropriate combinations of node selection strategies and opinion reconstruction methods.

2 ProblemDefinition

In this section, we first revisit the Friedkin-Johnsen (FJ) model [Friedkin and Johnsen, 1990], followed by six objective functions from the literature, i.e., polarization, disagreement, and their combination, in directed networks [Cinus et al., 2023] and undirected networks [Musco et al., 2018; Chen et al., 2018; Xu et al., 2021]. Finally, we define the problem to be addressed in this paper.

Although the FJ model is typically presented in the undirected case, we here focus on the more general and interesting case of directed graphs, following the treatment of [Cinus et al., 2023]. We thus consider an edge-weighted directed graph G = (V↪ E), with n = ♣V ♣ nodes and m = ♣E♣ edges, where each node i → V corresponds to a user, and each directed edge (i↪ j) → E indicates that i "follows" j or, in other words, that j can influence the opinion of i. For each edge (i↪ j) → E, the edge weight aij quantifies the strength of influence that user j exerts on user i, for example, based on how frequently content produced by j appears in the social feed of i. We assume that aij > 0 if (i↪ j) → E and aij = 0 if (i↪ j) ◁→ E and we represent all the weights as a matrix A, i.e., A[i↪ j] = aij. In the FJ model, each node i → V has an innate opinion si about one topic, which may differ from their expressed opinion zi on social media about the same topic, due to various factors, such as social pressure or fear of judgement. The sets of innate and expressed opinions, for all nodes in the network, are represented by vectors s → Rn and z → Rn , respectively. The nodes update their expressed opinions, based on the expressed opinions of their neighbors and their own innate opinions. Specifically, for each node i → V , its expressed opinion zi at time t + 1 is given by the average of the expressed opinions of its neighbors at time t and its own innate opinion, weighted by the strength of their influence. If we denote by Dout the diagonal matrix whose i-th diagonal entry is the weighted out-degree of node i, i.e., Dout [i↪ i] = ∑j→V A[i↪ j], and by z(t) the vector of the expressed opinions at time t, the opinion-update rule can be written in matrix notation as

By iterating Eq. (1) and using the matrix convergence theorems [Burden et al., 2015, Theorem 7.17 and Lemma 7.18], we can find the equilibrium of the system, where the opinions of all nodes have converged to a steady state. Specifically, the equilibrium is given by

where L = Dout ↑ A is the Laplacian matrix of G [Cinus et al., 2023]. Eq. (2) shows that the equilibrium opinions depend only on the innate opinions and the structure of the social network.

Following the literature [Cinus et al., 2023], we assume that the adjacency matrix A of the directed graph G is rowstochastic, i.e., A1 = 1, where 1 denotes the all-ones vector. This assumption allows for a straightforward interpretation that the total amount of influence each node receives sums to 1. In this case, the Laplacian L is given by L = Dout ↑A = I ↑A. Thus, the equilibrium opinion is written as

Finally, as in the literature [Musco et al., 2018; Cinus et al., 2023], we assume that all opinions are mean-centered, i.e., ∑u→V z↓u = 0. We are now ready to introduce the six objective functions.

Definition 1 (Polarization for directed graphs (P-DIR)). The polarization for the equilibrium opinion vector z↓ is defined to be the deviation of the opinions of nodes from the average opinion [Musco et al., 2018]. As the opinions are meancentered, the polarization at the equilibrium is defined as ∑u→V z↓u 2 = z↓↔z↓ . Following [Cinus et al., 2023], the objective function of P-Dir is given by

Definition 2 (Disagreement for directed graphs (D-DIR)). Following [Cinus et al., 2023], the disagreement for the equilibrium opinion vector z↓ is defined to be the degree of difference of neighboring opinions on G given by ∑(u↪v)→E auv(z↓u ↑ z↓ v )2 = 1 2 z↓↔(I + Din ↑ 2A)z↓ , where Din is the in-degree counterpart of Dout . Then, the objective function of D-Dir is

Definition 3 (Polarization plus Disagreement for directed graphs (PD-DIR)). We define polarization plus disagreement as the sum of polarization (3) and disagreement (4), as in [Cinus et al., 2023]:

The Undirected Case. Next, we consider the undirected version of the three objective functions above. Undirected graphs are useful to model social networks in which each link represents a bidirectional "friendship" relation. The formalization used so far applies straightforwardly to the undirected case by considering any undirected edge ¶u↪ v♦ as the two directed edges (u↪ v) and (v↪ u). In the undirected case, we can use the symmetry of A and L to simplify the notation. Following [Musco et al., 2018], the objective functions for undirected graphs are then defined as follows:

Definition 4 (Polarization for undirected graphs (P-UNDIR)).

Definition 5 (Disagreement for undirected graphs (D-UNDIR)).

Definition 6 (Polarization plus Disagreement for undirected graphs (PD-UNDIR)).

2.1 Our Problem

Given a graph G and influence weights A along its edges, our goal is to adjust the edge weights A so as to minimize one of the six objective functions above. As discussed in Introduction, our intervention corresponds to re-weighting the relative importance of the accounts that each user follows, so as to calibrate the frequency with which the contents produced by various accounts are shown to the user. Earlier works have studied similar tasks on undirected [Chen et al., 2018; Musco et al., 2018] and directed graphs [Cinus et al., 2023]. However, the problem we consider is much more complex, as we assume that we have no prior knowledge of the innate opinions s, and instead, we are given a budget b → Z>0 that represents the number of nodes we can query their innate opinions. We assume that if we query the innate opinion sv for v → V , we can obtain the exact value of sv.

Following [Cinus et al., 2023], we restrict the feasible set of solutions to adjacency matrices where the set of edges is a subset of the edges in the input graph and the out-degree of each node is preserved. By doing so, we are asked to use only pre-existing links and preserve the total engagement of each user in the social network. Formally, given the adjacency matrix A for a directed graph G, we define the convex set of feasible solutions as follows:

In the case of undirected graphs, the feasible set is

where Ln is the set of Laplacians for graphs with n nodes. Here we adopt the approach of [Musco et al., 2018], where the weighted degree of the nodes is not necessarily preserved. We are now ready to define the problem.

Problem 1. We are given an edge-weighted directed (resp. undirected) graph G = (V↪ E) with the unknown innate opinion vector s → Rn . We are also given a budget b → Z>0. The goal is to find a new adjacency matrix A↓ → C(A) (resp. Laplacian L↓ → C(L)) that minimizes the specified objective function among Eqs. (3)-(5) (resp. Eps. (6)-(8)) defined for the unknown innate opinion vector s, under the assumption that we can query the innate opinions of at most b nodes.

3 Characterization

Given the complexity of our problem, we propose a framework based on three steps (which we will detail in Section 4): (1) select b nodes and observe their innate opinions, (2) reconstruct the innate opinions of all nodes, using the b observed opinions and the network structure, and (3) optimize the objective function with the reconstructed opinions.

In this section, to characterize the importance of steps (1) and (2), we quantify how the reconstruction error of innate opinions affects the final quality of solutions. The main result of our analysis is presented in Theorem 1, revealing how the reconstruction error together with the Lipschitz constant of the objective function bound the error of optimization. To complete the analysis, we then derive the Lipschitz constant of each objective function with respect to the opinion vectors. All proofs are deferred to the Supplementary Material 1 .

1 https://github.com/FedericoCinus/Query-MinPD

3.1 Hardness

First, we discuss the hardness of the node selection problem for opinion reconstruction and the non-convexity of most objectives. These results build a taxonomy of objective functions related to the FJ model, as summarized in Table 1.

Node Selection for Opinion Reconstruction. In general, selecting an optimal subset of nodes to query, which minimizes the error of some estimate, is a well-known problem in optimal design [Pukelsheim, 2006]. This involves choosing a subset of b sample locations to recover the unknown parameter s. When experiments are selected integrally, as in our problem, standard criteria such as A-optimal design, D-optimal design, and E-optimal design are known to be NP-hard, even in the simplest cases like linear experiments [Madan et al., 2019]. This implies the potential difficulty of node selection in our problem.

Non-Convexity of Objective Functions. We next state the non-convexity of our objectives, except for PD-UNDIR being convex, related to the solvability of the problems.

Proposition 1. The objectives (3)-(7) are not matrix-convex.

Proposition 2. The objective (8) is matrix-convex.

3.2 Error Analysis

Let s and ˆs be the true innate opinions and the reconstructed innate opinions, respectively. We define the reconstruction error of ˆs to be ↓s↑ˆs↓. In general, a function f on Rn is said to be K-Lipschitz continuous if there exists a constant K such that for all x↪ y in its domain, ♣f(x) ↑ f(y)♣ ↔ K↓x ↑ y↓, where the parameter K is called a Lipschitz constant. The following theorem shows how the reconstruction error together with the Lipschitz constant of the objective function bound the error of optimization.

Theorem 1. Let L↓ and ˆL be optimal solutions, which minimize f(s↪L) and f(ˆs↪L) in Eqs. (3)-(8), respectively, over the feasible set defined. Suppose that f is K-Lipschitz continuous with respect to the first argument. Then, it holds that f (s↪ ˆL) ↑ f (s↪ L↓ ) ↔ 2K↓s ↑ ˆs↓.

This implies the following multiplicative approximation:

Corollary 1. Under the assumptions of Theorem 1 together with f(s↪L↓ ) ↗= 0, it holds that

The right-hand-side represents an approximation ratio of ˆL with respect to the true innate opinions s. From Proposition 1, we know that most of the objectives are non-convex, and for those objectives, no exact algorithm is known in the literature. However, for the objective PD-UNDIR, we can apply Corollary 1, due to the convexity of the objective (Proposition 2).

Finally, we provide Lipschitz constants for each objective function in Eqs. (3)-(8). Along with Theorem 1 and Corollary 1, this establishes an upper bound on the optimization error associated with the reconstruction error.

Proposition 3. The objective functions in Eqs. (3)-(8) are Lipschitz continuous on the space Rn with the following Lipschitz constants: for P-DIR, K = 2; for D-DIR, K = 1 + !(G); for PD-DIR, K = 2 + !(G); for P-UNDIR, K = 2; for D-UNDIR, K = 2!(G); and for PD-UNDIR, K = 2; where !(G) is the maximum (in-)degree of G (directed or undirected).

The proof proceeds as follows: First, we derive the gradient of the objective function with respect to the opinion vector to express the Lipschitz constant in its infinitesimal form. Next, we relate the Lipschitz constant to the spectral norm of the gradient matrix, which can then be bounded.

4 Methods

Here, we outline the three steps of our proposed framework, with detailed explanations, pseudocodes, and time complexity analyses provided in the Supplementary Material.

4.1 Node Selection Strategies

To mitigate computational bottlenecks, we employ three heuristic approaches based on centrality measures, which select the top-b nodes with respect to the following: Degree Centrality, which represents the sum of a node's in-degree and out-degree; Closeness Centrality [Bavelas, 1950], which is inversely proportional to the total shortest path distances from a node to all others; and PageRank [Page et al., 1999] with a damping factor of 0.85.

As a baseline, we also include a random uniform strategy for node selection, which selects b nodes uniformly at random without leveraging any structural properties of the network.

4.2 Opinion ReconstructionMethods

Based on the innate opinions of the b selected nodes, we aim to reconstruct the innate opinions of the remaining nodes as accurately as possible. To this end, we consider three types of reconstruction methods: Label Propagation-based, GNNbased, and Graph Signal Processing-based algorithms.

Label Propagation (LP). We extended LP [Zhu and Ghahramani, 2002] to handle continuous values by initializing all node values to zero, setting selected nodes to their true values, and iteratively updating the remaining nodes to the average of their neighbors over a fixed number of iterations.

Graph Neural Networks (GNN). We use a GCN [Kipf and Welling, 2017] to reconstruct unknown opinions by propagating known opinions from selected nodes, initializing node features with these values (or zero if unavailable), and training with an MSE loss.

Graph Signal Processing (GSP). We use GSP to reconstruct opinions, assuming the graph signal f : V ↘ R (opinions in our case) is bandlimited and can be expressed as a linear combination of a limited number of the Laplacian eigenvectors. Using mild assumptions for perfect recovery and noise from [Lorenzo et al., 2018], we apply the best linear unbiased estimator (BLUE) [Winer et al., 1971] to infer opinions from sampled nodes.

4.3 Optimization

In directed graphs, the objective functions (3)-(5) are nonconvex, and no approximation algorithm is known in the literature. To address these computational challenges, we employ a constrained gradient-descent approach as in [Cinus et al., 2023]. In the case of undirected graphs, we formulated the problem with PD-UNDIR as a semidefinite programming (SDP) with CVX as in [Musco et al., 2018]. For the other objectives and constraint, we apply the projection steps in [Cinus et al., 2023]. We compute a local minimum, using the reconstructed opinions as input.

5 Experimental Evaluation

In this section, we asses our framework and the impact of the reconstruction error on solution quality, compared to the ground-truth opinions. We present experiments on 16 networks with up to 1.6 million edges, considering both real opinions and synthetic opinions generated with varying distributions and polarization levels. Dataset statistics are provided in Table 2. Additional experiments on opinion distribution variations, runtime analysis, sensitivity studies, and baselines comparison are provided in the Supplementary Material.

Evaluation. We evaluate the accuracy of an algorithm as follows. Let LALG and L↓ALG be the solutions obtained by the algorithm with the reconstructed innate opinions and the true innate opinions, respectively. Note that we can only compute LALG when the true innate opinions are unavailable, but L↓ALG is also computed in experiments for evaluation. Then the quality of solution is measured by f(s↪LALG) f(s↪L→ALG) , which we refer to as the multiplicative error. As the denominator is (even beyond) the best possible achievable by the algorithm, the multiplicative error can be interpreted as a measure of how far the solution's quality deviates from this benchmark. Therefore, the smaller the multiplicative error is, the better the solution's quality.

Reproducibility. Experimental settings are in the Supplementary Material. Our code is available at https://github.com/ FedericoCinus/Query-MinPD.

5.1 Results

Real-world Datasets (Directed Graphs). Results are presented in Table 3. We use the three real-world datasets from X, as shown in Table 2, and validate performance across the three objectives for directed graphs in Table 1. Our framework tests three reconstruction methodologies - LP, GNN, and GSP, from Section 4, using reconstructed opinions from b = 0▷2♣V ♣ selected nodes, with this choice validated in Figure 2. Nodes for opinion reconstruction were selected based on Degree Centrality. Other selections of node sizes and strategies are tested in subsequent experiments.

The results show that LP, despite being the most computationally efficient, consistently achieves the lowest errors across all objectives and datasets, with multiplicative errors ranging from 1.16 to 2.08. For the P-DIR objective, LP reduces the error by up to 1.13 compared to GSP, even though this strategy has been optimized for undirected graphs. For the D-DIR objective, the maximum difference between the multiplicative errors reduces to 0.65, but it is even greater than that in PD-DIR (with a maximum difference of 0.42). The general trend suggests that the D-DIR objective appears to be the most challenging to optimize, with a maximum multiplicative error exceeding 2. This could be due to a dependence between network size and the error bound, as indicated by Proposition 3, where the function f is shown to be Lipschitz continuous with a constant related to !(G).

Semi-Synthetic Datasets (Directed Graphs). Results are presented in Table 4. We consider the 8 real-world directed networks in Table 2 and a polarized opinion distribution that reflects community structures.

In general, our framework yields multiplicative errors below 2. The GNN reconstruction methodology consistently achieves multiplicative errors below this value. Nevertheless, LP, while the fastest method, provides the lowest multiplicative errors, except for "ciaodvd-trust" and "wiki talk ht" networks, where it consistently shows higher multiplicative errors across all three objectives. P-DIR, at this scale, consistently exhibits the highest errors across all methods and networks. The maximum multiplicative errors for the least performing methods in this objective function reach up to 2.74.

Similar trends are observed with uniformly distributed opinions (Table 8 in the Supplementary Material): LP outperforms the other methods except for "wiki talk ht" and "dnctemporal" networks.

Semi-Synthetic Datasets (Undirected Graphs). Results are presented in Table 5. We consider the 5 real-world undirected networks in Table 2 with a polarized opinion distribution that reflects community structures. Network sizes are limited to approximately 100 nodes to avoid the computational bottleneck inherent in the SDP approach for finding an optimal solution. We test the performance of our framework in minimization of PD-UNDIR. This problem is well-studied in the literature and includes a standard projection step onto the set of SD matrices [Musco et al., 2018]. For P-UNDIR and DUNDIR, no projection step is known in the literature.

Multiplicative errors show greater variability across different graphs in undirected settings compared to directed ones. This would be because the current optimization problem (PD-UNDIR minimization) allows the algorithm to find a global optimum, resulting in a relatively small value of the denominator in the multiplicative error calculation.

Bounds on the multiplicative error are presented as averages, following Corollary 1 and Proposition 3. These bounds are sensitive to the numerical value of the global minimum of the objective. When the minimum is quite small, it can lead to very large bounds that are not practically useful. This occurred in 2 out of 5 instances in our experiments, specifically with the "beach" and "mit" networks. As a result, the bounds are larger than the actual error, indicating that, in practice, the problem is less challenging than theoretically predicted, and a tighter bound likely exists at this graph size scale. The bounds on the optimization error are proportional to the reconstruction errors, meaning that better performance is closely linked to improved reconstruction accuracy. For instance, the GNN strategy consistently achieves lower multiplicative errors (up to 1.7 times lower) compared to the GSP method. The LP method is comparable to GNN, except for "football" network, where it outperforms the others with a multiplicative error below 2.

Effect of Node Selection Strategies. The results are presented in Table 6. We consider real-world datasets to compare different node selection strategies to select b = 0▷2♣V ♣ nodes for reconstruction with the LP method.

On average, PageRank proves to be the most effective strategy for selecting nodes, while Degree Centrality shows consistently strong performance compared to the random strategy. For P-DIR, using Degree Centrality and PageRank can reduce the multiplicative error by up to 0.2 and 0.24, respectively, compared to random selection. For D-DIR, using Degree Centrality can reduce the multiplicative error by up to 0.3 compared to random selection; 0.33 for PageRank. For PD-DIR, using Degree Centrality can reduce the multiplicative error by up to 0.12 compared to random selection; 0.15 for PageRank. Closeness Centrality yields comparable results, although it performs less consistently, particularly on the "Referendum" network. Results for real directed networks with synthetic opinions are presented in Table 10 in the Supplementary Material. These results are consistent, showing the superiority of Degree Centrality and PageRank, except for "ciaodvd trust" network where the random strategy outperforms the others. It is worth noting that selecting nodes uniformly at random tends to cover diverse parts of the network, and given the fact that the innate opinions in realworld networks have a strong homophily, the random strategy would be reasonable and sometimes better than sophisticated ones. Despite the strong performance of PageRank, Degree Centrality strikes a better balance among quality, consistency, and computational efficiency. As such, we use Degree Centrality as the default strategy in subsequent experiments.

Effect of Network Size. The results are depicted in Figure 1. We consider two synthetic directed networks with sizes ranging from 100 to 5,000 nodes. We create a polarized opinion distribution reflecting communities and test the capabilities of our framework using the LP strategy. We measure the performance in minimizing the three objectives, P-DIR, D-DIR, and PD-DIR, with respect to the number of nodes. We use Degree Centrality to select 20% of nodes in each instance for opinion reconstruction.

Except for D-DIR, multiplicative errors are generally constant, with higher volatility observed in the Barab´asi-Albert graph. At this range of network sizes, D-DIR shows an increasing error with respect to the number of nodes, followed by a plateau, suggesting that non-constant error is introduced by some network structures. These observations align with our upper bounds and underscore the importance of characterizing the inter-dependence between networks and the objectives. This is the first necessary step toward understanding the minimization of such known objectives in an unknown opinion setting, necessitating further analysis and experiments.

Effect of the number of selected nodes. The results are depicted in Figure 2. We consider the "Referendum" dataset to compare different node selection sizes, ranging from 100 up to the size of the network (2,479 nodes).

As expected, the multiplicative error in each objective decreases as the number of selected nodes increases, but different patterns emerge. D-DIR shows the slowest rate of decrease compared to the other objectives across reconstruction strategies. In particular, the GNN strategy exhibits a plateau in the error curve, while LP displays a monotonically decreasing behavior. This is why LP has been chosen as the main reconstruction strategy in other experiments, in addition to its computational efficiency. The significant drop in multiplicative errors occurs between 15-20% of the node size. The 20% threshold, indicated in black, represents the selected node size used in all other experiments. In GSP, the number of selected nodes is linked to the number of frequencies, which is always smaller than the number of selected nodes. A sensitivity analysis is presented in Figure 3 in the Supplementary Material.

6 Conclusions

This paper contributes to the literature on opinion optimization in social networks under the Friedkin-Johnsen (FJ) model, which assumes innate opinions are fully known. We address the novel problem of opinion optimization under a budget constraint, where the goal is to minimize polarization and/or disagreement by querying a limited number of nodes for their innate opinions. To tackle this, we propose a framework integrating node selection, opinion reconstruction, and optimization, systematically evaluating alternative strategies for each component and identifying the most effective approaches. Our results demonstrate the framework's practicality, achieving multiplicative errors consistently below 2 and as low as 1.1. Additionally, our error propagation analysis quantifies how reconstruction errors in innate opinions impact the quality of final solutions, offering guidelines for researchers and practitioners, particularly for objectives involving disagreement, whose bounds scale with network size.

Although our experiments scale to networks with up to 1.6 million edges, larger real-world networks require more scalable methods. Techniques like GraphSAGE [Hamilton et al., 2017] could address this challenge, while active learning strategies adapted to graph structures may improve node selection efficiency. Robustness in heterophilic networks, where dissimilar nodes connect, remains an open challenge, and developing heuristics for such cases is a key avenue for future work. From a theoretical perspective, tighter bounds leveraging network structures that constrain Laplacian eigenvalues could provide stronger guarantees for optimization performance. Finally, real-world deployment must account for platform-specific constraints, which can be addressed by adapting the solution space accordingly.

Ethics Statement

Societal Impact. Our work proposes a framework for opinion optimization under the Friedkin-Johnsen model to mitigate polarization while addressing the challenge of incomplete information. By leveraging the interplay between network structure, innate opinions, and opinion dynamics, this research contributes to efforts aimed at designing interventions that reduce polarization and promote healthier discourse in online environments.

Ethical Aspects. Although this work is grounded in theoretical models and analysis, it carries significant ethical implications. Our experiments are conducted using anonymized datasets to ensure that no personally identifiable information is used or exposed. Nonetheless, methods for inferring opinions inherently carry risks, such as enabling the targeting of individuals based on their inferred opinions. Furthermore, the framework and analysis presented here could, in principle, be repurposed to maximize polarization rather than mitigating it, simply by changing the sign of the objective function.

We acknowledge these risks and emphasize that our work aims to advance ethical and privacy-conscious machine learning. By prioritizing the minimization of polarization and promoting responsible approaches to opinion dynamics, we seek to contribute to societal challenges constructively. Balancing these potential harms, we hope our research sets an example for the development of fairer, more transparent, and ethically grounded interventions in opinion optimization.

Acknowledgments

The work of Yuko Kuroki is supported by Japan Science and Technology Agency (JST) Strategic Basic Research Programs PRESTO "R&D Process Innovation by AI and Robotics: Technical Foundations and Practical Applications" grant number JPMJPR24T2. The authors would like to thank the anonymous reviewers for their insightful comments and useful feedback.