Fast Computation and Optimization for Opinion-Based Quantities of Friedkin-Johnsen Model
Authors: Haoxin Sun
Yubo Sun
Xiaotian Zhou
Zhongzhi Zhang
Venue: NeurIPS 2025 poster ()
Keywords: forest matrix
fast algorithm
FJ model
opinion dynamics，optimization problems
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We develop sublinear-time algorithms for computing and optimizing opinion-based quantities in the FJ model using partial rooted forest sampling.

Abstract: In this paper, we address the problem of fast computation and optimization of opinion-based quantities in the Friedkin–Johnsen (FJ) model. We first introduce the concept of partial rooted forests and present an efficient algorithm for computing these quantities using this method. Furthermore, we study two optimization problems in the FJ model: the Opinion Minimization Problem and the Polarization and Disagreement Minimization Problem. For both problems, we propose fast algorithms based on partial rooted forest sampling. Our methods reduce the time complexity from linear to sublinear. Extensive experiments on real-world networks demonstrate that our algorithms are both accurate and efficient, outperforming state-of-the-art methods and scaling effectively to large-scale networks.

Fast Computation and Optimization for Opinion-Based Quantities of Friedkin-Johnsen Model
Haoxin Sun, Yubo Sun, Xiaofian Zhou, Zhongzhi Zhang"
College of Computer Science and Artificial Intelligence
Fudan University (23110240089, 201000909999090011900999090900 fudan. edu. {20210240043, zhangzz)
Abstract
In this paper, we address the problem of fast computation and optimization opinion-based quantities in the Friedkin-Johnsen (FJ) model. We first introduce the concept of partial rooted forests, based on which we present an efficient algo- rithm for computing relevant quantities using this method. Furthermore, two optimization problems in the FJ model: the Opinion Minimization Problem and the Polarization and Disagreement Minimization Problem. For both problems, we propose fast algorithms based on partial rooted forest samplings. Our methods reduce the time complexity from linear sublinear. Extensive experiments on real-world networks demonstrate that our algorithms are both accurate and effi- cient, outperforming sftte-of-the-r methods and scaling effectively to large-scale networks.
study
1 Introduction
Online social networks and social media have become integral to our daily lives, fundamentally altering how individuals communicate, exchange, and form opinions 33 21 studies suggest that, unlike traditional forms of communication, online interactions in the digital have profoundly impacted human behavior, facilitating the widespread, critical, and complex propagation of information [40]. To better understand the mechanisms driving opinion formation and dissemination, various mathematical frameworks for opinion dynamics have been developed [27] 41 17 6). Among these models, the Friedkin-Johnsse (FJ) model [19] stands out as one of the most widely used, with applications spanning multiple fields [ 20 For instance, a modified FJ model was recently used to study the Paris Agreement negotiations, revealing key factors behind the achieved consensus g
48
50)
59
44
Recent
The fundamental concept in opinion dynamics the opinion itself, which serves as the basis for many opinion-based quantities that have garnered significant attention. Among these quantities the overall opinion, which reflects public sentiment on specific issues, and various social phenomena such as polarization, disagreement, and conflict. Given the importance of these opinion-based quantities, key challenge is how to effectively compute and optimize them. A Laplacian solver-based approach for computing these quantities was proposed in [52] [54] followed by sampling-bas algorithm to accelerate the computation process [39]. For the optimization of opinion-based quantities, range of methods has been introduced, including matrix inversion (24), vector projection [56] 59], eigencentralities [5). convex optimization (38). and sampling techniques [44]. Although many effective methods have been proposed for computing and optimizing opinion- based quantities in
the FJ model, they are often limited to specific problems or suffer from high time complexity. Consequently, a unified framework to efficiently address both computation and optimization of opinion-based based quantities in the FJ model is imperative.
"Corresooniigg author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In this paper, we propose several algorithms to compute and optimize the opinion-bant quantities.
Our main contributions are as follows:
We introduce the concept of partial rooted forests and, based on which we propose a fast sampling- based algorithm for computing opinion-basee quantities. Our methods effectively capture the essential structural information of the graph, ensuring both efficiency and accuracy.
We address two optimization problems in the FJ model: minimizing a weighted average of expressed opinions, and reducing polarization and disagreement via edge addition. For both problems, we design fast algorithms based on partial rooted forest samplings, reducing the time complexity from linear to sublinear.
We conduct extensive experiments algorithms demonstrate both high accuracy and efficiency compared to state-of-the-art methods and are scalable to large networks.
variety of real- weal-world networks, which shows that
2 Related Work
Mathematical modeling plays crucial role in understanding opinion dynamics, and numerous models have been proposed over the years to capture various aspects of opinion formation [27 41 17 6
Among these, the Friedkin-Johnsen (FJ) model [19] stands out foundational model, building upon and extending the DeGroot model [16] Given its theoretical importance and practical applications,
the FJ model has garnered significant attention since its introduction. A sufficient stability condition for the FJ model was derived in [42). and the model's average innate opinion was characterized
in 15]. Additionally, the vector of expressed opinions equilibrium Further interpretations and insights into the FJ model have also been provided 23
formulated in [15] [0]
The sum of opinions has attracted significant attention, with various research groups addressing the optimization problem of maximizing overall opinion through leader selection [55] 26 57 or link
recommendation 56 58 based on the DeGroot model. In the case of the FJ model, node-based
strategies have been proposed over the past decade to optimize the sum of opinions on unsigned graphs, including modifications to initial opinions B the expression of opinions [24 44 and
sensitivity to persuasion 22 I (6). Our solution for optimizing the average expressed opinion in the FJ model is both more efficient and effective compared the state-of-the-art approach presented in [4
The explosive growth of social media and online social networks has given rise several social phenomena, including polarization 33]33]44 4), disagreement (38), filter bubbles [7],,, conflicts [14],
and controversies []4]. In response to these challenges, research has evolved in various directions,
with fast algorithms being developed to efficiently compute these quantities (52 54 33) Some studies have focused identifying groups of users with open attitude toward opposing information 22
18
aiming to connect users with differing opinions order to mitigate the filter bubble effect [47
59
38
60
In this paper, study the problem of computing opinion- based quantities in
the FJ model
39
52 and two optimization problems in the FJ model [44] 59]. Our proposed
algorithms demonstrated greater efficiency and effectiveness compared the state-of-the-ard methods
in 39
59
3 Preliminaries
3.1 Graph and Laplacian Matrix
Let (V, E) denote an unweighted simple undirected graph, which consists of |V| nodes and m = [ edges. An edge (U,, ) E E indicates the edge between node Y; and node vy. In what follows, 1/ and i are used interchangeably
confusion. The structure of graph G = (V, E)) is captured by its adjacency matrix A = (azz)ax. where aiz = ajz if there is an edge between node e and node vy and 0 otherwise. The degree d, of node i is defined by d, = Σe= aij. The diagonal degree matrix representing the degrees of graph G is D diag (d, d2,.... dn), and the Laplacian matrix is L = D A. For any given node i, N; denotes the set of its neighbors, meaning N; = (j (i,1) F.). path from node en to ny is sequence of alternating nodes and edges U1,(U1, 02), " Uj-1, (U/-1, Uz), ey where each node is
represent node v, if incurring

---

unique and every edges connects to 14+1. A loop is a path plus an edge from the ending node to the starting node.
3.2 Friedkin-Johnsen Model
The Friedkin-Johnsen (FJ) model [19] is widely used framework for modeling opinion evolution and formation. In the FJ model applied
graph G (V, E), each node (or agent) i E V is characterized by two types of opinions: an internal opinion 8; and an expressed opinion z; (1) at time t. The internal opinion 8; E [0, 1] reflects the inherent stance of node on particular topic. Throughout the opinion evolution process, the internal opinion 8; remains fixed, while the expressed opinion (t) evolves at time 1 as 2t +
(st + ΣjEN,
+1++/i+ Qty).
Let 8 = ($1, $2. ,,,)" ST)T denote the vector of internal opinions. and let x(t) (21 (t); (2))), ... ; = denote the vector of expressed opinions at time t. According to 10] as approaches infinity, (t) converges an equilibrium vector
(21, 22: ,²x) satisfying
2 == (I + -)-1. Define Ω = (I + L) = (Wij) (n referred to as the forest matrix [2 K The forest matrix Ω is doubly stochastic for undirected graphs, with all its components in the interval [0, 1]. Furthermore, for each column, the diagonal elements are greater than the off-diagonal elements, that is 0 S wy < WH 1 for any pair of different nodes and j. and the diagonal element wi of matrix Si satisfies T+d. S Wii 2+d
The forest matrix Ω serves as the fundamental matrix of the FJ model for opinion dynamics [24] For every node E V, its expressed opinion is given by
2
Σj= WiyS5s convex combination of the internal opinions for all nodes.
Partial Rooted Forest Samplings for Estimating the Forest Matrix
The forest matrix 52 is the fundamental matrix of the FJ model and plays key role in its computation and optimization. Existing methods [4]] 46 44 rely on generating rooted spanning forests over the entire graph, requiring ((I)) time. We propose local approach, called partial rooted forest samplings, as a natural extension of previous methods by using absorbing random walks. It avoids full-graph traversal and offers improved efficiency and scalability.
4.1 Absorbing Random Walk
The forest matrix is doubly stochastic for undirected graphs. We initiate random walk from node i and assume the walk is currently at node & E V. At node k. the walk has a probability of I-d; to stop, and with probability 1 I+d, it moves to a randomly selected neighbor node k. the walk eventually stops at node q, we say that the walk has been absorbed by q. In this context, Wi represents the probability that walk starting node i will eventually be absorbed at node j.
To formally explain this, we expand the forest matrix an infinite series. Define P (1+
then the forest matrix has the following form: Ω = (I - [I--(-- D)- -I D)
PT- + D)-1 = Etzo p*[I+ D)-1 Here, the i, j-h entry of p* represents the probability that walk starting at takes exactly l steps to reach j. Multiplying this by I+d; gives the probability that the walk takes steps and is then absorbed at j. j.Then wij can be expressed as Wiy e, Se, = Σa e,T i V, and perform the absorbing random walk several times. Using the probabilistic interpretation of the forest matrix, where whj represents the probability of a random walk starting at node i and being absorbed node j. establishes the expected time complexity of the absorbing random walk:
e, = I+d; Σt20 e. p'ee,, ej. Choose an initial node
estimate the i-th row of the forest matrix. The following lemma
Lemma 4.1 For an undirected graph G = (V, and its related forest matrix Z the expected length of absorbing random walk starting at node i is Σラ= Widdz. If the initial node is chosen randomly, the expected length of the random walk to absorption -
2m
Proof. Let denote the expected length of an absorbing random walk starting at node i, and define the vector 1 = (I,, ,T,) For any i E V, the relationship between I; and its neighbors is given by 4 = 1 (1 + d, ESENt 14). Rewriting this in matrix form, we have I = (I + D) D1
3

---

(I + D At. Solving this equation yields 1 = ΩD11 Thus, for each i E V, the expected length 4 -4= W.ddy. j. If the initial node is chosen uniformly at random, the expected length of the random walk is = : E.=4 4 : - Eن= "ind, : Ei=( Whydd; = d, where the property Σ Wig 1 in undirected graphs is used. O
By Lemma 4.1, we can estimate z by performing absorbing random walks from each node in V multiple times. However, this method requires iterating over all nodes, which is computationally inefficient.
4.2 Partial Rooted Forest Sampling
In this subsection, we introduce a sampling method for constructing a partial rooted forest, which significantly reduces sampling time. We first define the concept of a partial rooted forest. In an undirected graph G = (V, E), rooted tree of G is connected subgraph without cycle, where one node set to be the root, An isolated node is considered as a tree with the root being itself. A partial rooted forest e (Va, E&) is a subgraph of G. where all connected components are rooted trees. The root set R(Ø) of ø is defined as the collection of root nodes from all rooted trees in Φ. Since each node in Ve belongs to a specific rooted tree, we define function r (i) V6 + ((Ø)) mapping node to the root of its corresponding rooted tree. If (i) = j. then j E R(Ø), and both i and j belong to the same rooted tree in Φ
Next, we describe the procedure for generating a partial rooted forest using loop-erased absorbing random walk. This involves the loop-erasure technique, which eliminates loops from random walk in chronological order [32]3]] 31.. By applying this technique, we can utilize the paths generated by the absorbing random walk instead of discarding them. The procedure is as follows:
(i) Initialization: Let S {Vi......0p 0p C V be a set of p 2 2 nodes. Initialize o = Es)
(0, 0) and set the indicator = 1.
(ii) Performing absorbing Random Walk: Sclect the first node u = E. Perform an absorbing random walk starting from u. Suppose that the walk is currently at a node & & Va, and the walk is absorbed with probability 1 with probability 1 , node & Vg, it is immediately absorbed.
1+d,, If the node is absorbed at k. k is marked as a root node. Otherwise, T+d the walk moves uniformly chosen neighbor of k. If the walk reaches
(iii) Loop Erasure: Let P. represent the trajectory of the walk from node u to its absorption point. Apply the loop-erasure technique to Pa, to obtain a simple path P.. Add the nodes and edges from Pa to Va and Eg,, respectively.
(iv) Iteration: If i < p. increment i by and repeat step (ii). Otherwise, terminate the process and return the partial rooted forest Φ.
The procedure is detailed in Algorithm PFS (Partial Rooted Forest Sampling); due to space constraints, the pseudocode is provided in the appendix.
The following theorem establishes the expected time complexity of the Partial Rooted Forest Sampling (PFS) algorithm. The time complexity is O(rpl), where r is ratio dependent on the graph structure, with an upper bound d. In real-world web and social networks, the average degree is typically Olog n) or constant 49 53). Furthermore, our experimental results demonstrate that r is consistently smaller than d. These observations collectively indicate the efficiency of our algorithm in practical scenarios.
Theorem 4.2 For an undirected graph G = (V, E) and a set of p nodes S C V, the expected time complexity of Algorithm PFS is Orppl), where is the rutio of the expected number of nodes in partial rooted forest & E L 10 p. and is the number of samples. r satisfies relation S S d if we randomly sample the set S from V. Algorithm PFS is more efficient than performing absorbing random walks individually for each node in S.
The algorithm repeats the sampling process times and outputs list of partial rooted forests. To establish the expected time complexity, consider single partial rooted forest e in the list L., Let q = rp represent the expected number of nodes in Φ. We will show that the expected time complexity for generating & is Ogg).
Proof.

---

First, we extend the partial rooted forest & to a complete spanning rooted forest ø' by executing the procedure described in lines 4-16 of Algorithm 4 for the remaining nodes in V \ Va- According to 44] the expected time complexity of sampling the complete rooted forest ø' is ((n). Furthermore, Wilson [51] demonstrates that the order of node processing does not affect the generation of spanning rooted forest. Hence, the partial rooted forest & can be viewed as subgraph of one complete rooted forest 6'.
Next, we analyze the expected time complexity of generating the partial rooted forest Φ. Marchel 33
shows that the expected absorption time for each node rooted forest is ws: + dz). Sun 44
refines this result, proving that wis( (1 + d;) v 2(1+d.)
I 2, which ((1).
2+4;
Therefore, the expected time complexity for sampling a single partial rooted forest e is ( leading to total expected time complexity of (ql) for the algorithm.
To give a rough estimation of r, if we sample randomly from V. an upper bound of r is (d) according to Lemma [.1] Moreover, Algorithm retains retains only the necessary branches in the forest
for each node. The sampling process terminates as soon as the walk reaches a node already in Vg. making it more efficient than performing absorbing random walks for all nodes in S individually, as described in Subsection
Fast Sampling Method for Opinion-Based Quantities in FJ Model
5.1 Definitions of Opinion-Basee Based Quantities
The FJ model includes several important quantities for analyzing the properties of social groups. Below, we provide a concise overview of these measures, following prior works [38 37 52).
Consider an undirected graph = EV. Disagreement D(G) is a measure the difference in opinions between neighbors, calculated as D(G)= = Σ Ee.eEE (2; - 2,)² =T Lz. Polarization P(g)
reflects how far individual opinions deviate from the average-expressed opinion. Using the vector
= 2 x 1 1. polarization is defined as P(g) = E 2)² z² Σ. Internal conflict (G) quantifies the discrepancy between the expressed opinions z and the initial opinions s. given by (G) = Eiev (2: 0,)² =z L z. Controversy C'()) represents the overall magnitude of expressed
opinions C(g) Eiev o T z. Dissgreement-controverrsy DC(G) is a combined measure
capturing both disagreement and controversy DC( = D(g) + C(g) = Σiey 8:2; = STz..
5.2 Estimating Opinion-Based Quantities
In this subsection, we present sampling- based algorithm for QE (Opinion- Based Quantities Estimation). The algorithm leverages the partial rooted forest samplings method to estimate the opinion-based quantities efficiently. We first provide a lemma to show that the map between the nodes in S to its root nodes in the partial rooted forest can be used to estimate the opinion- based quantities.
Lemma 5.1 For undirected graph G (V, E), set of nodes S C V, and internal opinion vectors (si,...,, .S)) , let & be the partial rooted forest generated by Algorithm PFS For node i E S. let (1) denote the root node of i in 6. Then, the estimator &n = E/= I(ra()) 8j is an unbiased estimator of 24-
Lemma 5.1 shows that the estimator 2, is unbiased for 24 By applying the partial rooted forest samplings method, we can estimate the opinion-based quantities in the FJ opinion dynamics model, and we now give the pseudocode for the sampling-basee based algorithm.
Algorithm| PF-QE (Partial Rooted Forest Method for QE provides the pseudocode for estimating the opinion-based quantities in the FJ opinion dynamics model. The algorithm leverages the partial quantities efficiently. Instead of estimating all nodes in V. algorithm focuses on a set of nodes S with y nodes, and samples I partial rooted forests. Now we provide a theorem, showing the parameters p and [ for given error tolerance.
rooted forest samplings method to estimate the opinion-
Theorem 5.2 For an undirected graph G = (V, F.) and internal opinion vectors (81,.... ........ 8n) if we choose p O log })), I = 0 log { and node set S is randomly sampled from V, then
5

---

Algorithm 1: PF-QU(G, L)
Input :Graph G (V, E),, node set S for, Up). internal opinion 8 (51, ;p)
Output :Estimates of opinion-based quantities
Sample list L of / partial rooted forests
2 Initialize gg +- (a p-dimensional vector for storing 2, for each U/ E S)
for k 1 to do
Φ < [.kk] for i <- to do r ro(s))
[ + [ + Sr:
7 2g +- 2, -
- Es|i] +
DC + - 1 D DC -
8 is = - ss|i]. P - 23) 1 - -;)²
return D, P. DC
Algorithm estimates the opinion-based quantities (g), P(g), I(g), C(9), and DC(9) within an absolute error of ne with probability at least 1 - 6. The total time complexity of Algorithm 7 (rrp)).
Partial Forest Sampling Techniques for Optimization Problems in FJ model
6.1 Opinion Minimization Problem
Problem [Opinion Minimization Problem (OpMin)) Given an undirected graph G E), a parameter vector (c1,.... , .Ca) where G [0, 1), integer k n, and an C of k nodes, and set their internal + 422 is minimized. That is,
iternal opinion vecter s, we aim to find the set H
opinions 0, so that the function f(c, H) 1
H = arg f(c,U). UEV.U
(1)
Our formulation of Problem generalizes the setting in (44. Specifically, when c for all i E V, reduces to the average-expressed opinion minimization problem studied [44). To address this problem efficiently, we propose fast algorithm based partial rooted forest samplings, which reduces the time complexity from ((I) to Orpll).
Recall that 2 = Σn Wij We can rewrite the objective function as f(c, = _ >i O.7 (amg))8.. Define % = 1 -i=ı Gawly then the objec- tive function can be rewritten as f(c, H) E TySj. In this case, the objective function is linear with respect to the internal opinions sj. To solve OpMin, we need find the set H of nodes with the smallest 7J values.
(I L)- is the equilibrium vector of the expressed opinions. Then
1 + ビド= Wijsy + -
n
In 44). the authors use the forest sampling method to solve the problem. However, the algorithm needs to perform a random walk process across all nodes in the graph, which is computationally expensive. To overcome this, propose efficient method using the partial rooted forest samplings. The key to solving OpMin lies in estimating the Y = 1 > Guiy for all nodes in the graph. Suppose that choose a of p nodes S randomly from V. and sample partial rooted forest Φb Then, define the estimator (5()) = - Eies 0s CsT (r)()==}-- We sample partial rooted forests
d1, " di, and estimate the 7, values using 35 = 1 (ox)) We detail the algorithm for solving OpMin in Algorithm 2
Algorithm 2 PF-OPMIN(Pariaal Rooted Forest Method for OpMin) provides the pseudocode for solving OpMin. The algorithm leverages the partial rooted forest samplings method estimate the Y values efficiently. By sampling partial rooted forests, we estimate the "ý values using the estimator
9j. The algorithm then selects the k nodes with the smallest 733 values the optimal set il

---

Algorithm 2: PF-OPMIN(G, S, c,l,k)
Input :Graph G (V, E), node set S fur, Up). parameter vector (cI, ,,,)"
number of forests number nodes
Output :Optimal set /7
Initialize 7 < 0, H + V. Sample list L of partial rooted forests
for t f-1 to I do
3
Φ f L[t]
for + p pd do
L j - roúi),
bb1 + 761 + Cv, cu,/pp
6 for i +- 1 to k do
L j arg ma Molse. HUD
8 return
Consider undirected graph 9 (V, E) and parameter vector (c1, Cn) where each ca is constant. By setting the parameters p O ( log and / = node set S through random sampling from V. Algorithm can solve OpMin within an absolute error d
10000 (+ log f). and selecting the
of kc, with probability at least 1-5. Specifically, the approximation satisfies f(c. H H(, H) I kc. This result follows proof strategy analogous to that of Theoreem [5.2 and Theorem 5.5 in 44 where r is the ratio of the expected number of nodes partial rooted forest á E L to p. Our algorithm runs in (rpll) time and outperforms the state-of-the-an method [44), which requires (In)) time. Since p & n and, as shown in the experimental section, the empirical results on real-world networks indicate that < 15, our approach improves the time complexity from linear to sublinear.
6.2 Polarization and Disagreement Minimization problem
In this subsection, we consider the Polarization and Disagreement Minimization Problem proposed
in (59). The problem focuses on selecting set of edges not present in the original graph minimize the sum of polarization and disagreement. We define the P-D index as I(G) = D(G) + P(g)
Ωz and denote the augmented graph as G + T = (V, EUT). The problem is formally described follows:
Problem 2 (Polarization and Disagreement Minimization Problem (PDMin)) Given undirected graph G = (V, E) and candidate edge set Ec C (2) E, the goal is to select a subset T C Eg of & n edges to add to the graph, such that the P-D index of the new graph is minimized. Define the objective function as f(T) = I(G) I(G + +T), and find
T
arg max TCBe, [T|=k
f(T).
(2)
In [59], the authors show that the problem is combinatorial in nature and propose a greedy algorithm to solve it. They prove that for candidate edge Ec connecting nodes and v, with vector
b. e, e.. the marginal gain is given by f(e) = 1+b
52b 6 as [zm=z.1² Itre. 2 0, where Tu. is the forest distance between nodes and v, defined as Tuo St A greedy algorithm computes the marginal gain for each candidate edge in Ec, selects the one with the largest gain, and repeats this process k times to obtain the final set T.
We set the sample node set for partial rooted forests to be the set of all nodes that appear in the candidate edge set Ec. that is, S U {i,j). Then, we generate / partial rooted forests {Ø1.-... Φ1) and use them to estimate the marginal gain f(e) for each candidate edge e Ec. The detailed procedure is presented in Algorithm PF-PDMIN(Partiall Rooted Forest Method for
PDMin). For any candidate edge if we set / = O L log (f(e) f(e) < is guaranteed to hold with probability at least
by applying Hoeffding' 's inequality (25). In [59], the authors use
the Johnson-Lindenan Lindenstrauss Lemma (28) and a fast Laplacian solver 43 to approximate the marginal
7

---

Algorithm 3: PF-PDMINGG, Ec. k)
Input :Graph G = (V, E), candidate edge set Ec, internal opinion vector $ = (81, 1. ;n))
number of forests number of edges
Output :Selected edge set f
Initialize T f 0, - U (1.j}
for t 4- 1 to k do
Sample partial rooted forests (Ø1,..., O1 on node foreach (u, v) E Ec T do
Initialize 2n 5- 0, 2u f- 0, Fwo +
for i 4- to do
Fa - ra (e.(()) (u),
To t re (w),,,, Tn t- Eu + tr. t- 8r.
Fov t Fuv + (u=rat (u=rc} (u=ro) - (u=ra}
Zu t La/l, 20 t 20/1, Par Fuoll, f(u,u) + (Zu - -z,)² /20)2/11 Fuv)
(u', v*) arg max (EN
T - (U(((",)")) E+ BU((W,,'',, V VUVUfu"'")
11
12
return T
gain, resulting in an overall time complexity of ((mk). In contrast, we leverage partial rooted forest samplings to reduce the time complexity to Orr(Eo|kl).
Experiments
In this section, conduct extensive experiments various real-life networks in order to evaluate the performance of our algorithms, in terms of accuracy and efficiency. Our source code is publicly available on htttts///iithuut www.coo//caaa// com/HaoxinSunge
Datasets and Equipment. The datasets for chosen real networks are accessed publicly through Our experiments cover varied selection of real-world networks, and the specifics of these datasets are outlined in Table All experiments are carried out using the Julia programming language within computational environment equipped with 2.5 GHz Intel v5-2682v4 CPU and 256GB primary memory.
KONECT [29] and SNAP (3).
Table Statistics of the datasets used in the experiments, including the number of nodes, number of edges, average degree, and the parameter r, which denotes the ratio of the average number of nodes partial rooted forest.
Network
Nodes
Edges
Delicious
536, 108
1,365,961
5.1
2.4
Youtube
1,134,890
2,987,624
5.3
2.4
Pokee
1,632,803
22,301.964
27.3
9.0
Orkut 3,072,441
117,184,899
76.3
13.6
Livejournal 7,489.073
112,305,407
30.0
3.3
Twitter
41,652,230
1,202,513,046
57.7
7.7
Baselines. For the FJ quantitics estimation problem, we compare our proposed algorithms with the LapSolver (52) and Lazy (39]. For OpMin, compare algorithm with the forest sampling method FAST For PDMin, we compare our proposed algorithms with the greedy algorithm
FASTGREEDY
559
7.1
Estimation for Relevant Quantities
In this subsection, we evaluate the performance our proposed algorithms for estimating relevant quantities for FJ model real-world networks. We compare our algorithms with LapSolver [52)

---

Table 2: Time complexity of our algorithms and baselines for three problems with parameter settings.
QF
OpMin
PDmin
Settings
PF-QE
(rrp))
PF-OPMIN
((rpl)
PF-PDMIN FASTGREEDY
Orkk||Eol
r << 15, 10", 10*
LazyWalk (r'pl")
FAST
(tt))
O(mk)
1' = 4 x 10 = 600
LapSolver (mm) EXACT
Õ(m)
= 50, |Ecl 10*
and LazyWalk [39 LapSolver achieves high accuracy [2 with a 10-6 relative error and is treated as the ground truth. Following the setting in [39], we set the number of samples to 10, 000 and vary the sampling parameters to compare the running time and mean relative error of the expressed opinions computed by PF-QE and Lazy Laly The results shown in Figure [ Both PF-QE and Lazy Walk are sampling- based algorithms and are parallelized using threads. Each experiment is repeated 10 times, and the average results reported.
Mean Relative Error (x10
PF-QF: : 500 al= 1000 a == 1500
LazyWalk: @ y= 2000, s 300 r= 4000, = 600
a 6000, 900
1.6
1.7
1.2
1.2
1.3
1.3
0.8
0.8
0.9
0.9
(a) Delicous
Youtube
(c) Pokec
(d) Orkut
(c) Livejournal
Running Time(s)
Figure 1: Comparison of mean relative error for 2, and running time under varying parameters for PF-QE and Lazy Walk. Internal opinions are generated using the uniform distribution.
From Figure we observe that the PF-QE curves consistently lie below and to the left of those for LazyWalk, indicating that PF-QE achieves better accuracy and lower running time. Based this observation, we fix = 1000 for PF-QE, and for Lazy Walk, we use 4,000 walks with 600 steps, following the configuration in [39] For other quantities, maintain 8-thread parallelization, repeat each experiment 10 times, and present the averaged results in Table
Table 3: Mcan relative errors and rumning time for three algorithms on six networks. Internal opinions are generated using the uniform distribution.
Time(s)
Reletive Error in %
Network
Lazy Walk C
PF-QE
LapSolver
LazyWalk Walk
PF-QE
DC
DC
Delicious
7.2
3.1
2.2
0.90
0.48
0.83 0.42 3.58
1.38
0.42 0.55 0.32
4.05
Youtube
9.6
4.1
2.4
1.03
0.75
0.21
0.33 3.52
0.95
0.73
0.22
0.31 4.19
Pokec
49.8
39.5
5.3
1.83
0.93
0.25
0.50
11.01
2.01
0.96
0.21
0.51 10.63
Orkut 291.9
142.2
9.9
3.97
0.62
5.43
2.71
34.77
2.98
0.72
0.23
0.47
13.67
Livejournal
Twitter 186.8
67.6
6.9
1.37
0.85
0.31
0.61
8.36
1.30
0.90
0.30
0.52 8.17
160.6
32.3
The results show that our algorithms achieve relative errors below 1.5% for average expressed opinion and below 4% for P, I, C. and DC.. Errors for D are higher due its dependence on both DC and C, amplifying estimation errors. PF runs faster than both LapSolver and LazyWalk while maintaining competitive accuracy. For the Twitter network, LapSolver cannot process the data due to time and memory constraints, whereas our algorithm handles it efficiently, running approximately five times faster than LalkWalk.
7.2 Optimization Problems
In this subsection, we evaluate the performance of our proposed algorithms for solving the FJ optimization problems OpMin and PDMin on real-world networks. We set 1000, 10000.

---

and l = 50 for our algorithms. Since our algorithms are sampling baged, we repeat each experiment 10 times and report the average results to ensure robustness and consistency.
Table 4: Running time and effectiveness of OPMIN (in terms opinion decline 8) and PDMIN (in terms of P-D index decline 8).
OpMin FAST
PDMin
Network
PF-OPMIN
EXACT
PF-PDMIN
FASTGREEDY
time
0
time
time
0
time
6
time
Delicious
-6.21
12.4
-6.79
5.9
-7.80
160.3
-5.69
862.3
-5.63
Youtube
3.7
-6.56
33.2
-6.48
4.6
-7.79
154.3
-6.46
1814.3
-6.42
Pokec
6.3
-4.17
79.4
-4.13
60.2
-4.98
494.1
-3.18
18656
-3.17
Orkut
10.3
-1.88
163.1
-1.79
310.5
-2.43
774.2
-5.23
Livejournal
8.1
-6.56
296.8
-6.44
214.7
-7.12
436.5
-4.62
Twitter
33.7
625.0
2531
For OpMin, compare our algorithm with the FAST forest sampling method 44) To ensure fair comparison, we set number of forests 44 to 1000, consistent with our experimental setup, and execute both algorithms in parallel using 8 threads. The EXACT algorithm, which uses the Laplacian solver, serves as the baseline method. Table reports the running time and the average expressed opinion decline 0 after setting the internal opinions of 50 nodes to zero, comparing three methods: PF-OPMIN, FAST, and EXACT. The results show that our proposed algorithm, PF-OPMIN, achieves comparable
better effectiveness than FAST, while being significantly more efficient. For instance, on the LiveJournal network, PF-OPMIN is approximately 37 times faster than FAST, while also achieving slightly larger opinion decline.
For the PDMin problem, we compare our proposed algorithm PF-PDMIN with the FASTGREEDY Lemma 28 and a fast Laplacian solver [43
method (59], which utilizes the Johnson-Lindenstraan In our experiments, we follow the parameter setting [59]. setting the size of the candidate edge set Ee to 10 And use 20 iterations for the JL lemma. For method,
fix k = 50 and = 1000. Table summarizes the running time and the reduction in polarization and disagreement, denoted by 5, for both methods. The results demonstrate that PF-PDMIN is substantially more efficient and consistently achieves better performance than FASTGREEDY. For instance, on the algorithm achieves more than 35x speedup while also yielding greater decline the polarization ciattionnddaarremmentt index. Furthermore, FASTGREEDY fails to seale to the three largest networks due time and memory constraints, whereas method remains both efficient and scalable.
Pokec network,
8 Conclusions
In this paper, we proposed several algorithms to compute and optimize opinion- based metrics for the Friedkin-Johnsen (FJ) model. We first introduced the concept of partial rooted forests and presented an efficient algorithm for computing several opinion-based quantities. Our proposed algorithms, PF-OPMIN and PF-PDMIN, reduce the time complexity from linear to sublinear compared to state- of-the-art methods. Extensive experiments on real-world networks demonstrate that our algorithms are both accurate and efficient, outperforming state-of-the-arr methods and scaling effectively to large networks with over 20 million nodes.
Currently, our framework has limitations in handling optimization problems where the objective involves nonlinear terms such as squared components (c.g.. 2/ in the marginal gain). In future work, we plan extend our methods support broader class of opinion optimization problems under the FJ model.
Acknowledgements
This work was supported by the National Natural Science Foundation of China (Nos. 62372112).
10

---

References
[1] Redict Abebe, T-H HUBERT Chan, Jon Kleinberg, Zhibin Liang, David Parkes, Mauro Sozio, and Charalampos E Tsourakakis. Opinion dynamics optimization by varying susceptibility to persuasion via non-convex local search. ACM Transactions on Knowledge Discovery from Data, 16(2):1-34, 2021.
[2] Rediet Abebe, Jon Kleinberg, David Parkes, and Charalampos E Tsourakakis. Opinion dy- namics with varying susceptibility to persuasion. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1089-1098) ACM, 2018.
[3] A. M. Ahmadinejad. S. Dehghani, M. T. Hajiaghayi, H. Mahini, and S. Yazdanbod. Forming external behaviors by leveraging internal opinions. In Proceedings of 2015 IEEE Conference on Computer Communications, pages 2728-2734 IEEE, 2015.
[4] Victor Amelkin, Petko Bogdanov, and Ambuj K Singh. A distance measure for the analysis of polar opinion dynamics in social networks. ACM Trans. Knowl. Discov. Data, 13(4):1334, 2019.
[5] Victor Amelkin and Ambuj Singh. Fighting opinion control in social networks via link recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 677-685. ACM, 2019.
[6] Brian DO Anderson and Mengbin Ye. Recent advances in the modelling and analysis of opinion dynamics influence networks. International Journal of Automation and Computing, 16(2):129-149) 2019.
[7] Prithu Banerjee, Wei Chen, and Laks VS Lakshmanan. Mitigating filter bubbles under a competitive diffusion model. Proc. ACM Manag. Data, 1(2):1-26, 2023.
[8] Carmela Bernardo, Lingfei Wang, Francesco Vasca, Yiguang Hong, Guodong Shi, and Claudio Altafini. Achieving consensus in multilateral international negotiations: The case study of the 2015 paris agreement on climate change. Science Advances, 7(5 reabbg8888 2021.
[9] Arnb Bhattacharyya and Yuichi Yoshida. Property Testing: Problems and Techniques. Springer Nature, 2022.
[10] David Bindel, Jon Kleinberg, and Sigal Oren. How bad is forming your own opinion? Games and Economic Behavior, 92:248-265, 2015.
[11] T-H. Hubert Chan, Zhibin Liang, and Mauro Sozio. Revisiting opinion dynamics with varying susceptibility to persuasion via non-convex local search. In Proceedings of the 2019 World Wide Web Conference, pages 173-183. ACM, 2019.
[12] P. Yu Chebotarev and E. V. Shamis. The matrix theorem and measuring relations in small social groups. Automation and Remote Control, 1505 1997.
[13] P. Yu Chebotarev and E. V. Shamis. On proximity measures for graph vertices. Automation and Remote Control, 59(10):1443 1459, 1998.
[14] Xi Chen, Jefrey Lijffijt, and Tijl De Bie. Quantifying and minimizing risk of conflict in social networks. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 197--1205. ACM, 2018
[15] Abhimanyu Das, Sreenivas Gollapudi, Rina Panigrahy, and Mahyar Salek. Debiasing social wisdom. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 500-508. ACM, 2013.
[16] Morris H. Degroot. Reaching consensus. Journal of the American Statistical Association, 69(345):118-122 121, 1974.
[17] Yucheng Dong, Min Zhan, Gang Kou, Zhaogang Ding, and Haiming Liang. A survey on the fusion process in opinion dynamics. Information Fusion, 43:57-65, 2018.

---

[18] Golnoosh Farnad, Behrouz Babaki, and Michel Gendreau. A unifying framework for faimess- aware influence maximization. Companion proceedings of the web conference 2020, pages 714-722, 2020.
[19] Noah E Friedkin and Eugene C Johnsen. Social influence and opinions. Journal of Mathematical Sociology, 15(3-4):193-4 193-206, 1990.
[20] Noah Friedkin, Anton Proskurnikov, Roberto Tempo, and Sergey E Parsegov. Network science on belief system dynamics under logic constraints. Science, 354(6310):321-326, 2016.
[21] Kiran Garimella, Aristides Gionis, Nikos Parotsidis, and Nikolaj Tatti. Balancing informa- tion exposure social networks. In Proceedings of the 31st Annual Conference on Neural Information Processing Systems, 2017.
[22] Shay Gershtein, Tova Milo, Brit Youngmann, and Gal Zeevi. Im balanced: influence maximiza- tion under balance constraints. In Proceedings of the 27th ACM international conference on information and knowledge management, pages 1919-1922, 2018.
[23] Javad Ghaderi and Rayadurgam Srikant. Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate. Automatica, 50(12):320-33155 2014.
[24] Aristides Gionis, Evimaria Terzi, and Panayiotis Tsaparas. Opinion maximization in social networks. In Proceedings of the 2013 SIAM International Conference on Data Mining, pages 387-395, SIAM, 2013.
[25] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pages 409-426, 1994.
[26] David Scott Hunter and Tauhid Zaman. Optimizing opinions with stubborn agents. Operations Research, 219-2117777
[27] Peng Jia, Anahita MirTabatabaei, Noah E Friedkin, and Francesco Bullo. Opinion dynamics and the evolution of social power in influence networks. SIAM Review, 57(3)3667337, 2015.
[28] William B Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26(189-206):1, 1984.
[29] Jérôme Kunegis. Konect: the koblenz network collection. In Proceedings of the 22nd Interna- tional Conference on World Wide Web, pages 1343-1350, 2013.
[30] Laks VS Lakshmanan. On a quest for combating filter bubbles and misinformation. In Proc. 2022 Int. Conf. Manag. Data, pages 2-2, 2022.
[31] Lawler and F. Gregory. A self-avoiding random walk. Duke Mathematical Journal, 47(3):655- 693, 1980.
[32] Gregory Francis Lawler. A self-avoiding random walk. PhD thesis, Princeton University, 1979.
[33] Heidi Ledford. How facebook, twitter and other data troves are revolutionizing social science. Nature, 582(7812))3228
2020.
[34] Jure Leskovec and Rok Sosič. Snap: A general-purpose network analysis and graph-mining library. ACM Transactions on Intelligent Systems and Technology, 8(1):1-20, 2016.
[35] Philippe Marchal. Loop-crased random walks, spanning trees and hamiltonian cycles. Electronic Communications in Probability, 5:39-50, 2000.
[36] Naoki Marumo, Atsushi Miyauchi, Akiko Takeda, and Akira Tanaka. projected gradient method for opinion optimization with limited changes of susceptibility to persuasion. In Pro- ceedings of the 30th ACM International Conference on Information Knowledge Management, pages 1274 1274-128, 2021.
[37] Antonis Matakos, Evimaria Terzi, and Panayiotis Tsaparas. Measuring and moderating opinion polarization in social networks. Data Mining and Knowledge Discovery, 11850155 2017.
12

---

[38] Cameron Musco, Christopher Musco, and Charalampos E T'ourakakiss. Minimizing polarization and disagreement in social networks. In Proceedings of the 2018 World Wide Web Conference. pages 369-378. International World Wide Web Conferences Steering Committee, 2018.
[39] Stefan Neumann, Yinhao Dong, and Pan Peng. Sublinear-time opinion estimation in the Friedkin-Johnsen model. In Proceedings of the ACM on Web Conference 2024, pages 2563- 2571, 2024.
[40] Daniele Notarmuzi, Claudio Castellano, Alessandro Flammini, Dario Mazzilli, and Filippo Radicchi. Universality, criticality and complexity of information propagation in social media. Nature Communications, 13:1308, 2022.
[41] Anton V Proskurnikov and Roberto Tempo. A tutorial on modeling and analysis of dynamic social networks. Part I. Annual Reviews in Control, 43:65-79, 2017.
[42] Chiara Ravazzi, Paolo Frasca, Roberto Tempo, and Hideaki Ishii. Ergodic randomized al- gorithms and dynamics over networks. IEEE Transactions on Control of Network Systems, 122):78-87,20)
[43] Daniel A Spielman and Shang- Hua Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Anal. Appl., 35(3):835-885, 2014.
[44] Haoxin Sun and Zhongzhi Zhang. Opinion optimization in directed social networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 4623-4632, 2023.
[45] Haoxin Sun and Zhongzhi Zhang. Efficient computation for diagonal of forest matrix via suriance-reduced forest sampling. In Proceedings of the ACM on Web Conference 2024, pages 992-802,220 2024.
[46] Haoxin Sun, Xiaotian Zhou, and Zhongzhi Zhang. Fast computation for the forest matrix of an evolving graph. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2755-2764, 2024.
[47] Antonela Tommasel, Juan Manuel Rodriguez, and Daniela Godoy. I want to break free! recommending friends from outside the echo chamber. In Proc. 15th ACM Conf. Recomm. Syst., pages 23-33, 2021.
[48] Sijing Tu, Cigdem Aslay, and Aristides Gionis. Co-exposure maximization in online social networks. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems, pages 2232-3243, 2020.
[49] Sibo Wang, Renchi Yang, Xiaokui Xiao, Zhewei Wei, and Yin Yang. Fora: simple and effective approximate single-source personalized pagerank. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 505-514, 2017.
[50] Yanbang Wang and Jon Kleinberg. On the relationship between relevance and conflict in online social link recommendations. Proceedings the 37th Annual Conference on Neural Information Processing Systems, pages 36708-36725, 2023.
the
[51] David Bruce Wilson. Generating random spanning trees more quickly than the cover time, In Proceedings of the Twenty-Eight Annual ACM Symposium on Theory of Computing, pages 296-303, 1996.
[52] Wanyue Xu, Qi Bao, and Zhongzhi Zhang. Fast evaluation for relevant quantities of opinion dynamics. In Proceedings of The Web Conference. pages 2037-2045. ACM, 2021.
[53] Wanyue Xu, Yibin Sheng, Zuobai Zhang, Haibin Kan, and Zhongzhi Zhang, Power-law graphs have minimal scaling of kemeny constant for random walks. In Proceedings of the Web Conference 2020, pages 46-56, 2020.
[54] Wanyue Xu, Liwang Zhu, Jiale Guan, Zuobai Zhang, and Zhongzhi Zhang. Effects of stub- bornness on opinion dynamics. Proceedings of the 31 ACM International Conference on Information & Knowledge Management, pages 2321-2332 2022.
13

---

[55] Yuhao Yi, Timothy Castiglia, and Stacy Patterson. Shifting opinions in a social network through leader selection. IEEE Transactions on Control of Network Systems, 86)::111-1127, 2021.
[56] Xiaotian Zhou and Zhongzhi Zhang. Maximizing influence of leaders in social networks. In Proceedings of the 27th ACM SIGKDD International Conference Knowledge Discovery & ACM, 2021.
Data Mining, pages
[57] Xiaotian Zhou and Zhongzhi Zhang. Opinion maximization in social networks via leader selection. In Proceedings of the ACM Web Conference 2023, pages 133-142, 2023.
[58] Xiaotian Zhou, Liwang Zhu, Wei Li, and Zhongzhi Zhang, A sublinear time algorithm for opinion optimization in directed social networks via edge recommendation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3593 3602, 2023.
[59] Liwang Zhu, Qi Bao, and Zhongzhi Zhang. Minimizing polarization and disagreement in social networks via link recommendation. In Proceedings of the 35th Conference on Neural Information Processing Systems, pages 2072-2084, 2021.
[60] Liwang Zhu and Zhongzhi Zhang. A hearay-linearr time algorithm for minimizing risk of conflict in social networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2648-2656 2022.
14

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly state the contributions and scope of our proposed algorithm, including both theoretical and experimental results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the work in Conclusions.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification: All theoretical results have clearly stated assumptions, and complete proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All information required to reproduce the main results provided Section Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
16

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide open access to the code at anonymous link: beetps://gitin HtwHHHaxxinnnnn9//Fa This URL is included in the submission, and the data used in our experiments are all publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
ssioooliccyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The full details can be found in Section Experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: We show the standard deviation in the APPENDIX.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The details can be found in Section Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: This work fully complies with the NeurIPS Code of Ethics. All datasets are publicly available with proper attribution, and the code is released via an anonymous repository. No human subjects sensitive data were involved.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [No]
Justification: This paper does not explicitly discuss societal impacts. However, the problems addressed in our work are based on previously published formulations (59 presented at NeurlPS 2021, and our focus is improving algorithmic efficiency.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
18

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper does not involve the release of high-risk data or models such as pretrained language models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All existing assets (datasets and code) are publicly available with proper citations in Section Experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The source code is released at [bttgpe//ggtuubb..c/oooox///////
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/model as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve any crowdsoureing, human subject research. All experiments conducted on publicly available datasets.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This work does not involve any human subject research, personal data collec- tion, or activities requiring IRB approval.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core methodology of this work does not involve any use of large language models (LLMs) as original non-standard component. LLMs were not employed in algorithm design, experiments, or analysis.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
hwt.eeerrppsccoooeeeeeeeeeeeeeee /
21

---

A APPENDIX
A.1 Pseudocode of Algorithm PFS
Algorithm 4: PFS(G.S.1)
Input :Graph G = (V, E), node set S = [1r,.... :........ppp. Uph. number of samples
Output :Partial rooted forest list L
L [+]]]
for k to do
Va < 0, Eg < 0
for to po do
< 2/ Pa t 1-11.c 11lcttu
while True do if c E Va then
break
else
10
if random() < I+d then
11
Pa 6 Pa U [c}
mark as root node break
13
14
else
next f- random choice from No
16
Pa - U {c, (c, nert))
C next
Pu Apply loop-erasure to Pu
18
19
Ve + Vo nodes P.
20
Fs < Es Uedges in P.
21
Add 6 = (Va, Es) to L
22
return L
A.2 Proof of Lemma
Proof. Since 2i
2j=1 j=1 Wij the proof is reduced to showing E [[[+r(((==)]]== waj. Consider the
proof of Theorem 4.2 and extend the partial rooted forest øi complete rooted forest ø In
and ø', we have (i) = (i) directly, since the nodes in di are a subset of the nodes in Φ'. Using
the Matrix Forest Theorem 212 13.
have (r)((rr((0=)))) wkj- Thus, (T)(
wij. and
the estimator 2, unbiased.
A.3 Hoeffding's inequality
Lemma A.1 (Hoeffding's inequality (25)) Let F1, T.. In be independent random variables
satisfying a S xz S bofor all 1,2,... n. Let x E1 Zt. Then for any e >> 0. P((
[(x) 2 <) S 2 exp (66--a)))
21c²
A.4 Proof of Theorem 5.2
Proof. Hoeffding's inequality, presented in Lemma A.1 serves as a powerful tool for estimating the required sample size to achieve a desired eтror guarantee. This inequality has been widely applied various studies, such as 44 39 Utilizing (.1ma|5.1]a alongsidd Hoeffding's 's inequality, selecting I 0= 0 / log 1) ensures that the estimated value E; deviates from the true value by at most an absolute error of 6, with probability at least 8, for any node i E V. Furthermore, according to Lemma 2.2 in Section 6 in [9) by choosing p O log ! and setting S -' .pp).
22

---

we can guarantee that the sum Eies 24 approximates Σiev within an absolute error of ne, with probability at least 1 - 8. It is important to note that E [0, 11, by setting / = O + log $) and p ( log }). the opinion-based measures D(g), P(G), [(),, C(g), and DC(G) can be estimated within an absolute error of ne, with probability at least 6.
A.5 Further Experiment Results
In this subsection, report the standard deviations for two algorithms across five networks in Table and provide further experimental results based on the exponential distribution in Table and Table
Table 5: Standard Deviation for two algorithms on five networks. Internal opinions are generated using the uniform distribution.
Standard Deviation in %
Network
Lazy Walk
PF-QE
P
C
DC
D
P
C
DC
D
Delicious
0.12
6.33
6.94
2.73
4.15
3.59
0.14
7.27
7.02
2.86
4.20
3.67
Youtube
0.006
0.93
0.70
0.13
0.27
2.18
0.009
0.98
0.73
0.17
0.30
2.04
Pokec
0.006
1.91
0.43
0.10
0.15
4.83
0.01
1.88
0.43
0.08
0.12
5.06
Orkut
0.02
4.02
0.91
0.16
0.71
44.83
0.02
3.32
0.92
0.25
0.47
24.17
Livejournal
0.006
1.15
0.55
0.14
0.33
4.84
0.05
1.17
0.59
0.43
0.36
4.60
Table 6: Mean relative errors and running times for three algorithms six networks. Internal opinions are generated using the exponential distribution.
Time(s)
Reletive Error in %
Network
Lazy Walk
PF-QE
LapSolver Lazy Walk PF-QE
2
P
DC
D
2
P
I
C
DC
D
Delicious
6.6
2.3
2.1
2.50
2.79
3.09
1.66
1.17
3.81
2.41
1.96
3.05
0.79
1.10
3.75
Youtube 9.6
4.4
2.6
1.90
3.25
2.93
0.78
1.41
6.32
2.36
3.33
2.89
0.77
1,38
6.49
Pokec
48.5
42.7
5.4
3.35
3.72
2.89
0.48
1.32
10.91
2.50
3.64
2.72
0.43
1.30
10.85
Orkut
320.8
153.2
9.7
2.92
8.00
1.95
5.29
2.06
76.66
2.51
12.54
1.97
0.41
1.02
25.67
Livejournal
239.5
70.7
6.6
2.44
3.22
2.87
1.82
1.24
5.06
2.40
3.10
2.89
1.38
1.50
5.11
Twitter
168.6
34.9
Table 7: Standard Deviation for two algorithms on five networks. Internal opinions are generated using the exponential distribution.
Standard Deviation in %
Network
Lazy Walk
PF-QE
P
C'
DC
D
P
1
C
DC
D
Delicious
0.008
1.49
2.15
0.59
0.87
3.07
0.01
1.37
2.12
0.57
0.89
3.00
Youtube
0.01
2.06
2.36
1.02
1.58
4.58
0.02
1.97
2.32
0.99
1.52
4.50
Pokec
0.01
3.29
1.95
0.33
0.87
8.12
0.02
3.24
1.87
0.34
0.883
7.63
Orkut
0.02
6.37
1.18
0.30
1.31
27.45
0.02
7.66
1.10
0.26
0.84
21.37
Livejournal
0.009
2.86
2.38
0.81
1.30
5.25
0.05
2.88
2.38
1.02
1.29
3.95
23


Reviews:
[{"review_id": "Qq3zeG7GY8", "reviewer": "Reviewer_poCz", "summary": "This paper proposes Partial Rooted Forest Sampling (PFS), a fast sublinear-time method for estimating key quantities in the Friedkin-Johnsen opinion dynamics model. By using loop-erased absorbing random walks to construct partial rooted forests, the method enables efficient, unbiased approximation of the forest matrix and related opinion metrics. It also supports fast optimization for tasks like reducing overall opinion or polarization, outperforming prior methods on large-scale real-world networks.", "questions": "Your algorithm’s performance depends critically on the graph-dependent ratio r, which is shown empirically to be small. Could you elaborate on which structural properties of graphs influence r, and how it behaves on different types like expanders or grid graphs?\n\nAlgorithm 1 samples S randomly, while Algorithm 3 uses endpoints of candidate edges, suggesting that smarter sampling could help. Could a more strategic selection of S, such as high-degree or central nodes, reduce the number of samples p or forests l needed for accurate estimation?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\nThe PFS method is a novel and elegant idea that localizes sampling to relevant graph regions, reducing complexity from linear to sublinear and enabling practical analysis of massive networks. The paper is theoretically solid with clear proofs, and the experiments show dramatic speedups and superior scalability compared to strong baselines. Besides, the paper is exceptionally well-written, with clear explanations, consistent notation, and well-designed visuals that effectively support its claims.\n\n\nWeaknesses:\nThe method’s efficiency relies on a parameter r that depends on the graph structure. Although empirical results show r is small in practice, a deeper theoretical analysis of how graph properties affect r would enhance understanding and applicability.\nThe paper briefly mentions limitations only in the conclusion. Including a dedicated \"Limitations\" section with discussion on issues like variance in Disagreement estimation and nonlinear objectives would improve transparency and completeness.", "was_revised": false, "final_justification": "", "rebuttal": "**Response to Reviewer poCz:**\n\nThank you for your time and helpful comments. Below is a summary of our response to your concerns.\n\n\n**Response to Weakness and Question 1:**\n\nAs shown in Lemma 4.1, the parameter $r$ is upper bounded by the average degree $\\bar{d}$, but in practice we find that $r$ is often much smaller, depending on the structural properties of the graph. To better understand what influences $r$, we evaluated it on several graph families with diverse characteristics. The table below reports the observed values:\n\n| Graph Type            | Nodes  | Avg Degree ($\\bar{d}$) | Observed $r$ |\n| --------------------- | ------- | ---------------------- | ------------ |\n| Grid (500×500)        | 250,000 | 3.992                  | 3.49         |\n| 15-Regular Graph      | 100,000 | 15.000                 | 3.69         |\n| Barabási–Albert Graph | 100,000 | 19.998                 | 3.04         |\n\nThese results show that $r$ remains small across a variety of graph types, including structured, regular, and scale-free graphs. We will elaborate further on this point in the revised version. Thank you again for the helpful suggestion.\n\n**Response to Question 2:**\n\nIn Algorithm 1, the subset $S$ is sampled randomly because the proof of Theorem 5.2 relies on the randomness of $S$ to guarantee unbiasedness and concentration. In contrast, in Algorithm 3, we set $S$ to be the endpoints of candidate edges, since we are only interested in the opinions of those specific nodes.\n\nThank you for the insightful suggestion. We will include a discussion on how a more strategic selection of $S$, such as using high-degree or central nodes, might affect the performance of downstream tasks like PDMin in our revised version."}, {"review_id": "3EH8MzLmo6", "reviewer": "Reviewer_tebe", "summary": "The paper provides a cost-efficient way to compute and optimize opinion-based quantities in the Friedkin–Johnsen (FJ) social-influence model. Central to these tasks is the forest matrix $\\Omega$, which has connections to absorbing random walks. The authors present a method for approximating the final opinions $z$ in FJ model by providing a sampling method. Building on Wilson's loop‑erased random‑walk sampler, they introduce Partial Forest Sampling (PFS), a local algorithm that generates only the few forest components needed for a given query. Unbiasedness and Hoeffding-type error bounds guarantee that averaging over all sampled forests yields accurate estimates of node opinions, polarization, and disagreement.\n\nLeveraging the same sampler, the paper presents two optimization algorithms: OPMIN, which selects $k$ internal opinions to minimize overall deviation from truth, and PDMIN, which adds up to $k$ edges to minimize polarization and disagreement index, which is convex in nature. Both achieve sub-linear expected runtimes and come with provable approximation guarantees, and it's a good asymptotic improvement over earlier approaches.", "questions": "Can you provide some insights if this can also be employed in approximately measuring polarization index which is non-convex in nature?", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1) Sublinear time algorithms\n\n2)  Practical scalability across various datasets\n\nOverall the paper is a well‑written contribution that combines sound theory with convincing large‑scale experiments. \n\nWeakness:\n\n1) Maybe I missed it but the choice of $r$ is not very clear from the text. Can the authors elaborate on it?", "was_revised": true, "final_justification": "I am keeping my score. While the proposed algorithms are built on an interesting observation, their efficiency and scalability remain noteworthy.", "rebuttal": "**Response to Reviewer tebe:**\n\nThank you for your time and helpful comments. Below is a summary of our response to your concerns.\n\n\n**Response to Weakness:**\n\nThe parameter $r$ is determined by the structure of the graph. As shown in Lemma 4.1, its maximum value is bounded by the average degree $\\bar{d}$. In practice, for real-world social networks (as reported in Table 4), we observe that $r < 15$ across all datasets. Furthermore, we conducted additional experiments on structured, regular, and scale-free graphs, consistently finding that $r$ remains small in all cases.\n\n| Graph Type            | Nodes  | Avg Degree ($\\bar{d}$) | Observed $r$ |\n| --------------------- | ------- | ---------------------- | ------------ |\n| Grid (500×500)        | 250,000 | 3.992                  | 3.49         |\n| 15-Regular Graph      | 100,000 | 15.000                 | 3.69         |\n| Barabási–Albert Graph | 100,000 | 19.998                 | 3.04         |\n\n**Response to Question:**\n\nAs shown in Table 2, our method provides accurate estimates of the polarization index $P$ in sublinear time, with relative error below 3%. Therefore, if an optimization problem is formulated based on polarization or a related non-convex index, our framework can still be used to estimate the objective efficiently. Extending the optimization aspect to non-convex formulations is a promising direction for future work."}, {"review_id": "JB6ko9SPXo", "reviewer": "Reviewer_NDbc", "summary": "This paper studies algorithms for efficiently computing the “final expressed opinions” in the standard Friedkin-Johnson (FJ) model of opinion dynamics. For a social network with Laplacian L, these opinions are equal to z = (L+I)^-1 s, where s is a vector of n “innate” opinions. The authors are specifically interested in computing some function of the opinions, like their inner product with a vector (with the all ones vector would give the average), their second moment z^Tz, and various other quantities related to “polarization and disagreement” of the final opinions. To do so, they adapt an approach based on random spanning forests from prior work. In particular, a natural approach to estimating a *single entry* is to write (L+I)^-1 as a power series in involving the random walk matrix D^-1A, exactly as is done when computing PageRank or personalized PageRank. The conclusion is that the i,j entry of  (L+I)^-1 is exactly equal to the chance that a random walk with absorption probability 1/1+d_k at node k that starts at i lands exactly on j. Thus, we can estimate entries in the ith row of (L+I)^-1 by running a bunch of random walks with this absorption probability, and seeing the percentage of times we land on various j. Recent work proposes and alternative approach based on the “Matrix Forest Theorem” which basically says that the probability an absorbing walk goes from j to i is also proportional to the probability i and j land in the same connected component if we construct a random spanning forest of G. \n\nThe authors observation is that, if we want to estimate a quantity like c^Tz for some vector v, we can subsample a set of indices, S, and return a Monte Carlo estimate. Accordingly, instead of building an *entire* random spanning forest for G, we should only build the part necessary to see what components nodes of S land in. This can be done easily by “early stopping” standard iterative algorithms for constructing random forests. The analysis of the result is thus straightforward (see Section A.3, A.4, A.5, A.6). Everything follows from prior work + Hoeffding’s inequality. \n\nThe authors show their methods can be used as subroutines to solve various optimization problems involving functions of the expressed opinions and compare the accuracy and runtime of their methods to prior work. There wasn’t sufficient discussion of the methods compared to — for example, it wasn’t clear to me what algorithm “LazyWalk” implements — however, it seems like the authors at least beat this baseline. At least in the main body also didn’t see to be a direct comparison to the “FAST” method (based on constructing a full random spanning forest), expect for on the downstream optimization problems. It would be helpful if the authors could comment on this, or provide results for FAST e.g. in Table 2.", "questions": "Mix of questions and small comments below. Don't feel the need to respond to everything: \n\n- when discussing the prior work in Section 4, what is “l” when you say prior methods require O(ln) time?\n- is “absorbing random walk” (e.g., as in Lemma 4.1) ever formally defined? At the beginning of Section 4.1 you define what it means for a walk to “absorb” at q, but not what it means to “be absorbing”.\n- The transition from Section 4 to 5 could use work. At the end of 4, it’s not clear why Algorithm PFS is useful, or why we should care about it. In Theorem 4.2, what does it mean to be “more efficient than performing absorbing random walks for eahc node S”? At this point, the algorithm and the proposed alternative output different things — a partially rooted forest vs a bunch of walks. More efficient for what task or by what measure?\n- Theorem 5.2 doesn’t seem scale invariant to me as stated. It implicitly depends on the assumption that s in [0,1], which was stated at some point, but not emphasized. I would remind the reader directly in the statement of Theorem 5.2. \n- It would be helpful to clarify how Theorem 5.2 compares with what would be obtained with independent random walk samples. To me this would be a more meaningful comparison than what is currently in Theorem 4.2.\n- It feels like to estimate something like z^Tz we should be able to randomly seleclt 1/epsilon^2 entries, and also get relative error to each entry with roughly 1/epsilon^2 walks. Average length is bar{d} so is the main imrpovement going from r to bar{d}?\n- Could you add more details on the “average expressed minimm opinion problem”? In the *undirected setting* (I believe the settin of this work), I think it is well-known that the mean of z is equal to a weighted mean of s (entries weighted by degree). It seems like is should be straightforward to solve the problem — set the opinions to 0 for the k nodes with highest product of initial opinion and degree. The cited paper [44] handles the directed case, which is maybe more interesting? If the problem is only interesting in your setting when c is not the all ones vector, I think this is worth pointing out. It might also be helpful to clarify why vectors c are natural besides all ones. \n- Some more discussion of what the baseline methods are in the experiments section would be helpful. E.g, what is te Lazy walk method?\n- Does Lemma 5.1 require S to random? This isnt’ stated. Also, is it fine if Algorithm PFS is run on the elements of S in any order? I.e., the order doesn’t need to be random?", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 2, "significance": 2, "originality": 1, "strengths_and_weaknesses": "+ Interesting problem that has been of recent interest. \n+ Reasonable algorithm that might very well be the \"right\" algorithm for the problem of estimating functions of the expressed opinions z. \n\n- I don't see any technical lift of previous work -- unless I misunderstood, the main result amounts to an observation that you can early stop an algorithm proposed in prior work if you only care about estimating entries of z for a subset of nodes. This is a nice observation, but I think more would be required to elevate it to publication level. \n- I found the writing informal and unclear at points. For example, the first theorem stated in the paper (Theorem 4.2)  is imprecise -- it is not clear in what way the partial random forest method can be directly compared to the efficiency of independent walk sampling, and the proof of the theorem doesn't make any such comparison.", "was_revised": true, "final_justification": "I raised my score by one because the authors addressed questions about comparisons with other methods, and how the $r$ dependence in their bounds compares with prior results depending on the average degree,  $\\bar{d}$. Adding this discussion to the paper as well as the additional experiments will strengthen the work. However, I continue to be concerned about the relationship to [44] -- the authors methods is an easy modification of that work (add early stopping), which limits the novelty of this work.", "rebuttal": "**Response to Reviewer sTM8:**\n\nThank you for your time and helpful comments. Below is a summary of our response to your concerns.\n\n\n**Response to Weakness 1:**\n\nWe focus on three problems related to the FJ model: (1) estimation of opinion-based quantities, (2) opinion minimization (OpMin), and (3) polarization and disagreement minimization (PDMin). SOTA algorithms for these three problems are different. For FJ estimation, we compare our proposed algorithm with LapSolver \\[52] and LazyWalk \\[39]. For OpMin, we compare with the forest sampling method FAST \\[44]. For PDMin, we compare with the greedy algorithm FASTGREEDY \\[59], which is based on a fast Laplacian solver. The time complexities of these algorithms are summarized in Table 1. Since these three problems have different properties, knowing a subset of entries of \\$z\\$ is not sufficient to solve them. Each problem requires a different SOTA method, and our work is the first to provide a unified framework to solve all these FJ-based problems in sublinear time.\n\nIn our paper, we propose the concept of absorbing random walk (Section 4.1), which inspires the design of our partial rooted forest sampling method. The complete rooted forest \\[44] is a special case of our method. In Theorem 5.2, we prove that it is not necessary to sample over all nodes to obtain accurate estimates of FJ opinion-based quantities. A similar idea of reducing sampling time appears in the empirical Bernstein bound \\[\\*].\n\n\\[\\*] Audibert, Jean-Yves, Munos, Rémi, and Szepesvári, Csaba. Tuning bandit algorithms in stochastic environments. International conference on algorithmic learning theory 2007.\n\n**Response to Weakness 2 and Question 3:**\n\nIf we want to estimate one row of the forest matrix, absorbing random walk works well. If we want to estimate the entire forest matrix, then complete rooted forest is appropriate. However, if we only need the opinions of a small subset of nodes, our method is significantly more efficient than either running complete rooted forest or running absorbing random walk separately for each node. This is because our partial rooted forest reuses tree branches (lines 146-157), while repeated absorbing random walks discard prior computations and restart from scratch each time. We discuss this in the proof of Theorem 4.2 (lines 510–514), and we will provide more explanation in the revised version for clarity.\n \n**Response to Question 1 and Question 2:**\n\nIn Section 4, \\$l\\$ denotes the number of samples used in forest-based sampling methods. We will make this explicit in the revised version. Regarding the term “absorbing random walk,” we use it to refer to a random walk that follows the transition rules specified in lines 110–114 until it is absorbed at a designated node. We will revise Section 4.1 to include a precise definition and improve clarity. Thank you for the careful observation.\n\n**Response to Question 4 and Question 5:**\n\nWe mention in line 90 that $s \\in [0,1]$ and will restate this in Theorem 5.2 to remind the reader. Thank you for the helpful suggestion. We propose the concept of absorbing random walk, which motivates the design of our partial rooted forest sampling method. In Theorem 4.2, we show that partial rooted forest sampling is more efficient than running absorbing random walks separately for each node. Therefore, Theorem 5.2 and the subsequent analysis focus on the partial rooted forest method.\n \n**Response to Question 6:**\n\nThe transition from the absorbing random walk formulation to the partial rooted forest indeed improves the sampling complexity from $\\bar{d}$ to $ r$. However, the key point is that the SOTA algorithms for the three FJ-related problems (estimation, OpMin, PDMin) are all different. For example, in the case of PDMin, prior work relies on Laplacian solvers, whereas our method achieves a speedup of approximately 40× in Pokec in Table 3 while obtaining comparable solution quality.  \n\n**Response to Question 7:**\n\nIn the undirected setting, the problem formulation in [44] becomes trivial since the mean of $z$ equals the degree-weighted mean of $s$. To address this, we introduce the weighting vector $c$, which generalizes the problem and makes it meaningful even in the undirected case. Importantly, our framework and the proposed partial rooted forest sampling method are applicable to directed graphs, and the estimator remains unbiased for the forest matrix in both directed and undirected settings. In this paper, we focus on undirected graphs because many FJ-related quantities, and the problem PDMin are defined and studied primarily in the undirected setting. Additionally, Laplacian solvers, which are used in the SOTA baselines for PDMin do not generalize to the directed case.  We will add more discussions on this point in the revised version. \n\n**Response to Question 8 and Question 9:**\n\nLazyWalk \\[39] is the SOTA algorithm for estimating FJ opinion-based quantities. It performs multiple lazy random walks to estimate expressed opinions. We will add more discussions of baseline methods in the experimental section to make this clearer.\n\nRegarding Lemma 5.1, the subset $S$ is assumed to be randomly selected, and we will make this assumption explicit in the revised version. As for Algorithm PFS, the order of nodes in $S$ does not affect the result; it can be executed in any order.\n\n**Additional Response:**\n\nThe three FJ-related problems we address—estimation, OpMin, and PDMin—each have different SOTA baselines. Among them, only OpMin uses a forest-based method (FAST) as the baseline. Nonetheless, for completeness, we also applied the full rooted forest construction to the estimation task and report its runtime in Table 2 below:\n\n| Network     | Algorithm           | Time  | P      | I      | C      | DC     | D      |\n|-------------|---------------------|-------|--------|--------|--------|--------|--------|\n| Delicious   | PF-QE | 2.2   | 1.38   | 0.42   | 0.55   | 0.32   | 4.05   |\n|             | Full Forest         | 4.1   | 4.57   | 2.01   | 0.28   | 0.68   | 1.96   |\n| Youtube     | PF-QE               | 2.4   | 0.95   | 0.73   | 0.22   | 0.31   | 4.19   |\n|             | Full Forest         | 8.5   | 4.14   | 1.93   | 0.48   | 0.11   | 5.84   |\n| Pokec       | PF-QE               | 5.3   | 2.01   | 0.96   | 0.21   | 0.51   | 10.63  |\n|             | Full Forest         | 26.4  | 3.12   | 1.23   | 0.73   | 0.20   | 16.3   |\n| Orkut       | PF-QE               | 9.9   | 2.98   | 0.72   | 0.23   | 0.47   | 13.67  |\n|             | Full Forest         | 66.8  | 2.81   | 1.06   | 0.75   | 0.20   | 18.8   |\n| Livejournal | PF-QE               | 6.9   | 1.30   | 0.90   | 0.30   | 0.52   | 8.17   |\n|             | Full Forest         | 58.2  | 3.51   | 1.45   | 1.41   | 0.55   | 15.9   |\n\nWe sample 100 full forests and record the runtime and relative error. As shown in the table, our partial forest (PF) method is consistently faster than the full forest (FF) method, while also achieving better estimation accuracy.\n\nThank you again for your insightful suggestions."}, {"review_id": "oy4Gc1NB1b", "reviewer": "Reviewer_Q3ZZ", "summary": "This paper proposes an efficient algorithm for computing the quantities in FJ model and applies the quantities estimation to the Opinion Minimization Problem and the Polarization and Disagreement Minimization Problem.", "questions": "Questions\n\n1. In the experiments, for OpMin problem, the paper compares with FAST; for PDMin, the paper compares with FASTGREEDY. In the related work, the authors refer to many other recent baselines, which should be compared.\n\n2. The experiments report Relative Error in the tables. In the greedy algorithms, the estimation error might lead to choosing different nodes or edges. Since the problems are usually not submodular, small estimation error could lead to completely different final results. It is better to present the final performance for OpMin and PDMin.\n\n3. Some important references are missing, for example,\n\nSijing Tu and Stefan Neumann. A Viral Marketing-Based Model For Opinion Dynamics in Online Social Networks. WWW 2022.\n\nRandom-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation, TKDE, 2007.\n\n4. Small typos, e.g., “Reletive Error”->” Relative”", "limitations": "Please see the weakness of the questions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe motivation of partial rooted forests and the quantities estimation is clear.\n\n2.\tThe paper provides a solid analysis of the performance guarantee.\n\nWeaknesses:\n\n1. The sampling based method is an extension of existing method. The existing method is sufficient to scale large graphs, which may limit the scope of readers.\n\n2. The quantities estimation has been investigated previously and the method seems an application of the absorbing random walk, which limits the technical novelty.", "was_revised": true, "final_justification": "The authors have addressed my concerns. I slightly increase the score.", "rebuttal": "**Response to Reviewer Q3ZZ:**\n\nThank you for your time and helpful comments. Below is a summary of our response to your concerns.\n\n\n**Response to Weakness 1:**\n\nWe address three distinct problems related to the FJ model: (1) estimation of opinion-based quantities, (2) opinion minimization (OpMin), and (3) polarization and disagreement minimization (PDMin). Existing SOTA algorithms are tailored to each of these problems individually. In contrast, our work is the first to propose a unified framework capable of solving all three problems in sublinear time.\n\nFurthermore, for the most challenging case—PDMin, which is NP-hard—our method scales to very large graphs, including the Twitter dataset with over 40 million nodes. In contrast, the SOTA baseline FastGreedy fails to run on such large-scale data due to memory and runtime limitations. On other datasets, our method also demonstrates significant efficiency gains. For example, on Pokec (as shown in Table 3), our method achieves a speedup of approximately 40× compared to prior Laplacian solver-based methods, while maintaining comparable solution quality.\n\n**Response to Weakness 2:**\n\nIn our paper, we introduce the concept of absorbing random walk (Section 4.1), which to our knowledge is the first formalization of this idea in the context of FJ models. It inspires the design of our partial rooted forest sampling method, where the complete rooted forest \\[44] is a special case. When only a small subset of nodes is of interest, our method is significantly more efficient than either computing the full rooted forest or running absorbing random walks separately for each node, as shown in Theorem 4.2 (lines 510–514). Based on this, we develop a unified and scalable framework to solve three distinct FJ-related problems, each with different prior SOTA solutions.\n\n\n**Response to Question 1:**\n\nFor FJ estimation, we compare our proposed algorithm with LapSolver \\[52] and LazyWalk \\[39]. For OpMin, we use the forest-based sampling method FAST \\[44] as the baseline. For PDMin, we compare with FASTGREEDY \\[59], a greedy algorithm based on a fast Laplacian solver. These baselines represent the current SOTA for the respective problems.\n\nAlthough many recent works have studied the FJ model, they do not directly address the three specific problems considered in our paper. Therefore, they are not suitable for comparison in our experimental setup. We hope for your understanding.\n\n\n**Response to Question 2:**\n\nIn Table 2, for the estimation of opinion-based quantities, we report the relative error. For downstream tasks—OpMin and PDMin—we report the final performance in Table 3, measured by the decrease in opinion values and the P-D index, respectively. We will clarify this distinction more clearly in the revised version.\n\n**Response to Question 3 and Question 4:**\n\nWe will add the two missing references in the revised version. We will also thoroughly check the entire paper and correct all typos. Thank you for your careful reading.\n\nThank you again for your insightful suggestions."}]

Author rebuttal:

Meta-review: This work studies the problem of efficient estimation of opinion-based quantities as well as optimization of opinion-based objectives (minimizing the weighted average final expressed opinion and reducing disagreement between nodes) on social networks under the well-studied Friedkin-Johnsen model. The authors extend existing algorithms using what they refer to as a partial rooted forest sampling approach based on results from [44, 45, 46] in their references. Effectively, their method stops the method from [44] early, thereby avoiding full graph traversal and reducing the time complexity from linear to sublinear. 

The reviewers agree that the main contributions of this work provide an interesting and elegant observation about existing methods discussed in the papers above. However, the reviewers also expressed numerous concerns about technical novelty since the presented algorithms are a natural extension of the existing ones. Of course, extensions can make a meaningful and interesting contribution, but such papers benefit from providing substantially more empirical insights across a broader family of real-world networks, more robustness results (e.g., around the parameter r which is crucial to their methods performance), a more extensive direct comparison with existing methods and natural baselines, and other technical extensions of the problem such as non-linear objectives as the authors mention. The additional results presented in the rebuttal phase helped mitigate some of these concerns, but some concerns remain. We encourage the authors to incorporate to detailed feedback from the reviewers.
Decision: Accept (poster)