Opinion Maximization in Social Networks by Modifying Internal Opinions
Authors: Gengyu Wang
Runze Zhang
Zhongzhi Zhang
Venue: NeurIPS 2025 poster ()
Keywords: Opinion dynamics
social network
multi-agent system
graph algorithm
Primary area: optimization

Abstract: Public opinion governance in social networks is critical for public health campaigns, political elections, and commercial marketing. In this paper, we addresse the problem of maximizing overall opinion in social networks by strategically modifying the internal opinions of key nodes. Traditional matrix inversion methods suffer from prohibitively high computational costs, prompting us to propose two efficient sampling-based algorithms. Furthermore, we develop a deterministic asynchronous algorithm that exactly identifies the optimal set of nodes through asynchronous update operations and progressive refinement, ensuring both efficiency and precision. Extensive experiments on real-world datasets demonstrate that our methods outperform baseline approaches. Notably, our asynchronous algorithm delivers exceptional efficiency and accuracy across all scenarios, even in networks with tens of millions of nodes.

Opinion Maximization in Social Networks by Modifying Internal Opinions
Gengyu Wang, Runze Zhang, Zhongzhi Zhang
College of Computer Science and Artificial Intelligence Fudan University
fgywang24, rzzhang24)8m. H0m. fudan. edu. en, zhangzz&funda edu.
Abstract
Public opinion governance in social networks is critical for public health cam- paigns, political elections, and commercial marketing. this paper, we addresse the problem of maximizing overall opinion in social networks by strategically modifying the internal opinions of a fixed number of nodes. Traditional matrix inversion methods suffer from prohibitively high computational costs, prompting to propose two efficient sampling-buse based algorithms. Furthermore, we develop a de- terministic asynchronous algorithm that exactly identifies the optimal set of nodes through asynchronous update operations and progressive refinement, ensuring both efficiency and precision. Extensive experiments real-world datasets demonstrate that our methods outperform baseline approaches. Notably, our asynchronous algorithm delivers exceptional efficiency and accuracy across all scenarios, in networks with tens millions of nodes.
Introduction
Online social networks have fundamentally transformed the dissemination, evolution, and formation of opinions, serving as a powerful catalyst for accelerating and amplifying modern perspectives [I] Compared traditional communication methods, they facilitate faster, broader, and more decen- tralized information exchange, thereby enhancing the universality, criticality, and complexity of information propagation (2). Within this intricate interplay between network structure and human behavior, the concept of overall opinion emerges as a key quantitative metric, representing the focal point of public sentiment contentious issues [3. This quantified equilibrium of public opinion has been applied in fields such as commercial marketing, political elections, and public health campaigns.
The optimization of overall opinions has garnered significant attention in recent times. Various methods have been explored to optimize collective opinions, including modifying resistance coef- ficients 6), adjusting expressed opinions [7], and altering network structures [8] 9]. Meanwhile, research 10 has highlighted the significant correlation between node topological positions and the evolution of global opinions, revealing that changes in the internal opinions of nodes have nonlinear amplification effect on opinion propagation. This provides the possibility of optimizing public opinion at low cost by modifying the internal opinions of key nodes.
In this paper, we address the following optimization problem: given social network with n nodes and edges (whether directed or undirected), along with an integer k how the nodes and modify their internal opinions to maximize the overall opinion? Existing exact solution methods require time complexity of Onn²), rendering them impractical for large-scale networks. We propose two sampling approaches to approximate the solution, but these approaches face the challenge of balancing between extensive sampling requirements and accuracy. Inspired
strategically identify
Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

by the random walk interpretation, we further introduce asynchronous update algorithm that exactly identifies the optimal of nodes through asynchronous update operations and progressive refinement. We conducted extensive experiments on various real-world networks to evaluate algorithm performance. The experimental results demonstrate that all three proposed algorithms significantly outperform baseline methods in terms of effectiveness. Moreover, our asynchronous algorithm exhibits both high efficiency and exact precision, while maintaining excellent scalability for networks with tens of millions of nodes.
2 Related Work
We review the related literature from the following two perspectives, including modeling opinion dynamics and optimization problems in opinion dynamics.
Opinion Dynamics Models. Opinion dynamics has been the subject of intense recent research to model social learning processes in various disciplines [T] These models capture the mechanisms and factors influencing opinion formulation, shedding light on understanding the whole process of opinion shaping and diverse phenomena taking place in social media. In the past decades, numer- ous relevant models have been proposed [1418). Among various existing models, the DeGroot model [99 and the Friedkin-Johnson (FJ) model [20] are two popular ones. After their establishment, the DeGroot model and the FJ model have been extended in a variety of ways [1] 21 8 [2 4J, by incorporating different factors affecting opinion dynamics, such as peer pressure [23], susceptibility to persuasion 4 (), and opinion leader (7). Under the formalism of these models, some relevant
21
quantities, properties and explanations have been broadly studied, including the equilibrium ex-
pressed opinions [6), sufficient condition for the stability [27]. the average internal opinion (24).
interpretations 28 225, and so on.
Optimization Problems in Opinion Dynamics. Recently, several optimization problems related to opinion dynamics have been formulated and studied for different objectives. For example, a long line of work has been devoted to maximizing the overall opinion by using diffferent strategies, such as identifying a fixed number of individuals and setting their expressed opinions to [7]. changing agent's s initial opinions
(29 g 30), well as modifying individuals' susceptibility to persuasion (46). [3I] studies the problem of allocating seed users to opposing campaigns with a goal to maximize the expected number of users who are co-exposed both campaigns. In additon, [32] studies the problem of balancing the information exposure. These studies have far-reaching implications in product marketing, public health campaigns, and political candidates. Another major and increasingly important focus of research is optimizing some social phenomena, such maximizing the diversity
3 34
minimizing conflict [35 36), disagreement (37 38 g
and
polarization
39 38
Preliminaries
This section is devoted to a brief introduction to some useful notations and tools, in order to facilitate the description of problem formulation and algorithms.
Notations. We denote scalars in IR by normal lowercase letters like a, b, c, sets by normal uppercase letters like A, B, C. vectors by bold lowercase letters like a. b, c, and matrices by bold uppercase letters like A, B, C. We use 1 to denote the vector of appropriate dimensions with all entries being ones, and use e; to denote the 5th standard basis vector of appropriate dimension. Let a T and A' denote, respectively, transpose of vector a and matrix A. We write A(i, j) denote the entry row i and column j of A and we use aii) to denote the ,th element of vector a. Let amaxs amins and asam denote the maximum element, the minimum element, the mean of the elements in vector a and the sum of all elements in vector a, respectively.
Graph and Related Matrices. Let G (V, E) denote an directed graph with n = [ nodes and m = [E| edges. The existence of (v; 03) E E means that there is an edge from to ey. In what follows, Vi and i are used interchangeably to represent node Us when it clear from the context. For node E V, the in-neighbors of are given by (v) = (ul(u, v) E E), and the nei-nhigs of u are given by Nom(w) (u((s, u) E F). The connections of graph = (V, F)) are encoded in its adjacency matrix A (at mxn. with the element ai being 1 if (v,, vy) E E and 0 otherwise.

---

For node i E V, its out-degree d is defined as d Σj= asg, and its in in-degree d, is defined as dj = =i= 'j,.. The diagonal degree matrix of g is defined as diag(df (df di. ..... d We define L = D- A and P = D- A as the Laplacian matrix and the transition matrix of graph g.
Opinion Dynamic Model. In this work, we adopt an opinion formation model introduced by the work of DeGroot [19] and Friedkin and Johnsen [40]. which has been used in [4] 6 24]. In this model, each agent i is endowed with an internal opinion s; in [0, 1], where 0 and are polar opposites of opinions about a certain topic. Each agent also has a parameter that represents the susceptibility to persuasion, which we call the resistance coefficient a; E (0, 1]. The internal opinion s; reflects the intrinsic position of the agent i on a certain topic. A higher value on the resistance coefficient ag means that the agent less willing to conform to the opinions of the neighbors in the social network. According to the opinion dynamics model, the final opinion of each agent i is a function of the social network, the set of internal opinions, and the resistance coefficients, determined by computing the equilibrium state of dynamic opinion updating process. The social network is represented graph where edges capture influence relationships, with an edge from to j indicating that agent i is influenced by the expressed opinion of agent j. During the process of opinion evolution, the internal opinion 8; remains constant, while the expressed opinion 2; evolves at time I + 1 as follows:
++ = a48; + (1 - a.)) EjENom(0) 3j df
which can also be expressed in matrix form as 2 Rs + -I-IIIRREP R)P2'. This dynamic converges to unique equilibrium if a; > 0 for all E V [14]. The equilibrium opinion vector 2 is the solution linear system of equations:
Rs, where R Diag(a) is diagonal matrix called resistance matrix and entry i(i,i) corresponds to a;e. We call 2 z(i) the expressed opinion of agent i. Let M = (I -I R) R, we have 2 = M Note that M is a row-stochastic matrix such that M1
==
4 Problem Formulation
An important quantity for opinion dynamics is the overall expressed opinion or the average expressed opinion at equilibrium, the optimization problem for which has been addressed under different constraints 7
6 g 29 30). In this section, we propose a problem of maximizing overall expressed opinion in graph, and introduce an exact algorithm optimally solving the problem.
Overall Opinion and Structural Centrality. For the opinion dynamic model in graph G = (V, E). the overall expressed opinion is defined the sum 2sum of expressed opinions 2; of every node i E V at equilibrium. By Eq. (T), Zsum = 1 Ms. 8. Given the internal opinion vector s and the resistance matrix R, we use f( R, 8) to denote the overall expressed opinion. By definition,
SRR, 1 1 Ms
Σ> WEV VEV
M (u,v))((1
Eq. (2) tells us that the overall expressed opinion f(R, 8) is determined by three factors: the internal opinion and the resistance coefficient of every node, as well as the network structure characterizing interactions between nodes, all of which constitute the social structure of the opinion system. The first two are intrinsic property of each node, while the last one is a structure property of the network, both of which together determine the opinion dynamics system. Concretely, for the equilibrium expressed opinion x, = Eeev M (u, s)s(s)) of node u. M (u, v) indicates the convex combination coefficient or contribution of the internal opinion for node v. And the average value of the v-th column elements of M, denoted by P. A Evev M (u, v), measures the contribution of the internal opinion of node o to f( s). We call Pe as the structural centrality 42) of node v in the opinion dynamics model, since it catches the long-run structure influence of node e on the overall expressed opinion. Note that matrix M is row stochastic and 0 < M (u, v) < 1 for any pair of nodes u and v, 0 S Pv < n holds for every node u V. and Evev Pv
Using structural centrality, the overall expressed opinion f(R,s) is expressed SRR s)
Engy (u), which shows that the overall expressed opinion f(R, s) is a convex combination of the internal opinions of all nodes, with the weight for s, being the structural centrality Pa of node
3

---

Problem Statement. As shown above, for given graph G - EV, its node centrality remains fixed. For the FJ opinion dynamics model on G (V, with internal opinion vector and resistance matrix R. if we choose set T C V of l nodes and persuade them to change their internal opinions to 1, the overall equilibrium opinion, denoted by (T,R, 8), will increase. is clear that for T = 0. fo( R. s) fRR, s). Moreover, for two node sets H and T, if H CT S V then fr, 8) 2 fH (R, s). Then the problem OPINIONMAX of opinion maximization arises naturally: How to optimally select set 7' with fixed number of k nodes and change their internal opinions to 1, so that their influence on the overall equilibrium opinion is maximized. Let the vector A be the potential influence vector, where (t) p. si)) defines the potential influence of node i on the growth of the overall equilibrium opinion. Mathematically, it is formally stated as follows.
Problem 1. (OPINIONMAX) Given an unweighted graph 9 (V, E), an internal opinion vector 8, a resistance matrix R, and an integer parameter k: & n, we aim to find the set T C. V with [T] k nodes, and change the internal opinions of these chosen k nodes so that the overall equilibrium opinion is maximized. That is,
= arg max Su(R, 8) arg max UCV.
ΣA(1) UCK.U EE
Similarly, we can define the problem OPINIONMIN for minimizing the overall equilibrium opinion by optimally selecting set T of k nodes and changing their internal opinions to 0. The goal of problem OPINIONMIN is to drive the overall equilibrium opinion fr(R. s) towards the polar value O, while the goal of problem OPINIONMAX is to drive Sr R, 8) towards polar value 1. Although the definitions and formulations of problems OPINIONMAX and OPINIONMIN are different, we can prove that they are equivalent to each other. In the sequel, we only consider the OPINIONMAX problem in this paper.
The most naive and straightforward method for solving Problem D innolles directly computing by inverting the matrix 1 (I R) which has a complexity of O(n"). Identifying the top k elements using max-heap has a complexity of On log k). Therefore, the overall time complexity of the algorithm involving matrix inversion is O(n²). This impractical time complexity makes it infeasible for networks with only tens of thousands of nodes on single machine. In the following sections, We propose new interpretation and attempt to propose a new precise algorithm based on this explanation.
Optimal Solution.
5 Sampling Methods
In this section, apart from the algebraic definition, we give two novel interpretations and propose corresponding sampling algorithms to approximately solve Problem
Random Walk-Based Algorithm. Observing that the expression for the overall equilibrium opinion in Eq. 2 can be expanded as 1 C R. P) Rs via the Neumann series, we introduce the absorbing random walk. For a absorbing random walk starting from node 8, at each step where the current node is j. the walk either (i) is absorbed by node j with probability aj. or (ii) moves uniformly at random to neighboring node with probability 1 - aj, where the resistance coefficient aj of node j represented as the absorption probability of the random walk at node j.
Lemma 1. For an unweighted graph G (V, F., let P; E RRVV be the absorption probability vector of absorbing random walks starting at node V. The structural centrality of node is Pv = E P(())
Leveraging this connection between structural centrality and termination probabilities, we propose random walk- based algorithm RWB efficiently estimate structural centrality for all nodes and compute an approximate solution to Problem []] In algorithm RWB, we first simulate N runs of the absorbing random walk (Xth2o where each realization starts from node uniformly chosen from V. We then estimate the structural centrality Pj for each node j E V by scaling the empirical absorption frequency at j by n.
Lemma 2. Let G (V, E) be an unweighted graph with internal opinion vector and resistance matrix R. For any error tolerance (0, 1). if algorithm RWB simulates N O (²) log n)

---

independent random walks, then the estimated structural centrality P. of any node i E V satisfies Pr (lp: pal 2 5 :.
Theorem 1. Consider a graph 9 (V, with internal opinion vector 8 and resistance matrix R. Let Omin = minkev R(i,i) and Qmax = m R(i, Under the error guarantee of Lemma 2
algorithm RWB achieves a time complexity of O (hmaae (1 aawin) log
We now establish that algorithm RWB provides provable approximation guarantees for OPINIONMAX. While Lemma garimaaboure bounnd the error of individual P. estimates, the following result demonstrates that the collective quality of the selected set T is near-optimal:
Let pi be the estimator of pi from algorithm RWB with absolute error parameter e, and T be the optimal solution to Problem] For the set T consisting of the k nodes achieving arg - Eie Pi(1 - s.). we have: Lier Po si) 2 EiET. Pi s:) 2ke.
Corollary 1.
Forest Sampling Algorithm. For matrix Q + L, where Q is diagonal matrix, the elements its inverse can be interpreted combinatorially in terms of spanning converging forests in graph 43 44). In particular, by setting Q = D - R) R. we can reformulate Eq. (2) in terms of the fundamental matrix, thereby establishing a direct correspondence between the structural centrality and spanning converging forests.
Lemma 3. Let F be the set of all spanning converging forests of graph 9, and F S F be the sub- set where nodes and j are in the same converging tree rooted at node For forest F E F, let r r(F)
be the set of roots of F. Then the structural centrality of node i is Pt = Leev Exgri lluerrr) Q(u,0) EFEF llEErE) Quu,u)
This theoretical insight connects significantly with an extension of Wilson's 's algorithm. As shown in (30), Wilson's 's algorithm, based on loop-erased random walks, effectively simulates the probability distribution of rooted spanning trees when each node i E V is assigned a probability Q(i,)) 2) of being the root. Building upon this theoretical framework, we propose an algorithm FOREST. The experiment in (30) demonstrates that the algorithm can maintain good effectiveness with small number of samplings. More details are presented in Appendix B The following theorem provide its time complexity:
Theorem 2. When the number of samplings is I, the time complexity of algoritim FOREST is 0 Iln).
Oimin
Fast Exact-Selection Method via Asynchronous Updates
Sampling methods face challenges in identifying optimal size-k node sets with maximal potential influence, as their sample complexity scales as =2. In this section, we present deterministic asynchronous algorithm that provides rigorous error guarantees, enabling exact computation of the highest-influence node set without reliance on stochastic samplings. To maintain consistency, we present our derivation using unweighted graphs, noting that the corresponding algorithms can be readily extended to weighted graphs.
6.1 Asynchronous -ased Approximation
Let pd denote the residual vector time t, initialized as p 1, and updated recursively via ++1 P - R)r'. By unrolling this recurrence, we obtain r² = (PT(I- R))'1, which captures the distribution probability of a (-step absorbing random walk originating from uniformly chosen node. This probabilistic interpretation motivates our deterministic algorithm employing asynchronous computation. The asynchronous paradigm provides two fundamental advantages: First, it enables local computation where each node's 's residual evolves independently based on its neighborhoods; second, it supports node-specific termination through local convergence monitoring of individual node states. These properties collectively overcome the synchronization constraints of global methods while eliminating the sampling overhead of probabilistic approaches.
Global Influence Approximation. We propose an efficient asynchronous algorithm to compute the potential influence vector A for the OPINIONMAX problem. The algorithm maintains a residual vector Te initialized to 1, estimated potential influence vector Á initialized to O, and uses
5

---

boundary vector h = cl (which e E ()) the termination criterion. At each iteration, for every node! satisfying T (i) h()), the algorithm performs three key operations: (i) distributing (1-a:)/df (i) to each out-neighbor's residual ra (5) for j E (i) (ii) accumulating (1 ---s)aa;
(i()) to the node's 's own potential influence estimate A (t), and (iii) resetting Ta (i) to O. These updates managed asynchronously through first-in-firs--ou queue Q, processing nodes when they meet the residual threshold condition. The algorithm terminates when the residual condition r(e) S (v) holds for all nodes V. Each push operation maintains strict locality by only accessing direct neighbors, while the asynchronous execution enables efficient computation of the potential influence scores needed for opinion maximization. The pseudo code is provided in Algorithm 1
Algorithm 1: GLOBBLIINFAPPROX(
8,
Input :Graph G (V, B), resistance matrix R, internal opinion vector error parameter e. Output :Estimated potential influence vector Å and residue vector ra-
Initialize Á 0; Fa
2 while 3v E V s.f. To (V) > e do ((u) = ( + (1 s(v))a,
for each u E (v) do
ra(u)= ru(u)
1-an ra
di
(a(v)= =0
return Á, Ta
The correctness of the algorithm relies on the relationship between the residual vector and the estimation error, which is guaranteed by the following lemma.
Lemma 4. For any node i E V during the execution of Algorithm (1 - s(i)) e. M Ta holds.
the equality A (i) (i)
Using Lemma 4
we can further establish the relative error guarantees for the results returned upon termination the Algorithm [ as shown the following lemma.
Lemma For any parameter e E (0,1), the estimator À returned by Algorithm 1 satisfies the following relation: (1 - (1-6) (v) < ( < (v), Vu V.
Targeted Node Refinement. Algorithm ! provides solutions with rigorous relative error guarantees. As established in Lemma these precise error bounds allow to determine whether given node must necessarily belong to the size-k set with maximal potential influence. Furthermore, when the error tolerance becomes sufficiently small, that maximizes opinion influence. However, since each error threshold setting generates a distinct candidate set of boundary nodes, repeatedly computing global error bounds through Algorithm [ would incur unnecessary computational overhead. This motivates our key optimization: Can we focus computations exclusively on a reduced candidate set identified by Algorithm T improve efficiency?
completely identify the exact size-k node set
Algorithm 2: TARKETTDDNDDRREIINNG Ta, ra)
Input :Graph G = (V, E), forward residual vector initial residual vector r error
parameter e.
Output :Estimator Á and residue vector r..
Initialize Á = r, 0
2 while Eo E V s.f. (v) > Ea,, do
Â = A + (u) (v) for each u E (v) do
(u) (u) 1- (v)
(a(v)= 0
return Á,

---

The theoretical foundation comes from Lemma 4 which provides the exact decomposition for all nodes in the network. This decomposition directly motivates Algorithm 2 designed to approximate the influence propagation term (1 si)) e M ra for any given node The algorithm initializes with estimate Á = 0 and residual vector r, - r using - R1 as the boundary vector. For each node v satisfying (v) > hv), the algorithm updates Á by adding To(v) (r) and propagating residuals to in-neighbors before resetting r. rs(v) 0. The process repeats until (v(v) I h(o) for all nodes.
While Algorithm| 2 asynchronous operations do not maintain the random walk interpretation, its correctness is established through the following analysis.
Lemma 6. When Algorithm 2 initialized with r = a - s s())) the equality ( - (A(e)
Á) = rd M R 'r, holds throughout execution.
Building upon Lemma 6 can derive the following absolute error bound when specific initialization conditions are met.
Lemma For Algorithm 2 with initial residual r ar(1 s(v)) given any parameter
e E (0, 1), the estimator å satisfies the absolute ervor bound: ( e. (r())ssm
6.2 Fast Exact-Selection Algorithm
Let T C V be the set of nodes guaranteed to be contained in the optimal size-k node set with maximal value sequence a, and let C C \T' denote the candidate nodes that may belong to this optimal set when considering estimation errors. Given an estimator à with uniform error bounds (either absolute or relative), we can formally characterize these sets through the following lemma.
Lemma 8. Let à approximate with uniform error 0 < a(i) a(i) S Eb (i) for all i V, and let azi> denote the i-th largest value in à. Then,
a(i) a(i) s
Element i T either a(i) 2 ack+1> t or a(i) 2 @<k+1>/(0 ((1 - Eb);
Element i C if T and either a(i) ācks - En or a(i) à ācks (1 eb).
Let kgap denote the difference between the k-th and (k: + 1)-th largest values in the true potential influence vector A. When the absolute error e < kipa. we can guarantee exact identification of the optimal size-k node set. However, since kepa is typically unknown priori, we employ iterative refinement approach that progressively tightens the error bound e across successive iterations. This process leverages residual vectors from previous iterations as initial conditions. thereby reducing recomputation overhead through warm-start optimization. The algorithm operates through two computational phases. First, global relative error bounds are applied to identify small candidate set C. Then, Algorithm computes absolute error guarantees specifically for nodes in C' while
Algorithm 3: MAXIINELUENCCESELLECCCOO R, k,c,k)
Input :Graph G (V, F.), opinions s, parameter k. Output :Optimal node set T.
Initialize 0:
Á, GI.OBALIINFAPPROX/ R, 8,c)
Update and via Lemma with (A(u)) and enror Initialize a,, (1 8, c.,, Vu E C
for é' = 1 5...... 2n ... do
for v E C do
Â r. = TARGETEDNNDDEEENNE(, Tas To, To, (r.e(((()))m)
Á ((v) Â(v) +
Update and via Lemma with (Á(v) and error e' if [T] k then return T'
10
11
7

---

progressively shrinking the candidate set size. The procedure terminates when the error bound satisfies < kea and the candidate set becomes empty, at which point we obtain the exact optimal size-k set with maximal potential influence. The pseudo code is provided in Algorithm 3
Theoretical guarantees of this approach are established in the following theorem, which provides an upper bound on the time complexity.
Theorem 3. For sufficiently small the upper bound on the time complexity of Algorithm is
0 "max" log Ormin
Experiments
In this section, we experimentally evaluate our proposed three algorithms. Additional experimental results and analyses are presented in Appendix C
Machine. Our extensive experiments were conducted on Linux server equipped with 28-core 2.0GHz Intel(R) Xeo Gold 6330 CPU and ITB of main memory. All the algorithms we proposed implemented in Julia 10.7 using single-threaded execution.
Table I: Datasets
DBLPP
Google
YoutuheSnap
Pokec
Flixster
Liveloural
Twitter
SinaWeibo
Nodes
317,080
875,713
1,134,890
1,632,803
2,523,386
4,847,571
41,652,230
58,655,849
Edges
1, 1,049,866
5,105.039
2,987.624
30,622,564
7,918,801
68,993,773
1,468,365,
261,321,071
dynss 343
456
28.754
8,763
1,474 undirected
20,296
770,155
278.491
Type
undirected
directed
undirected
directed
directed
directed
undirected
Datasets and Metrics. We use 8 benchmark datasets that are obtained from the Koblenz Network Collection [55, SNAP [46] and Network Repository [47). [aable[[summrrii the key characteristics of the networks used our experiments, including network name, number of nodes, number of edges, maximum out-degree, and network type. The networks are listed in ascending order based on node count. A more detailed description of the datasets is provided in Appendix D On each dataset, employ the algorithm INFOBALIIEPPROX with relative error parameter 10 12 to compute the ground-truth structural centrality scores. This ensures that each ground truth value has most 10 relative error. We evaluate the maximum influence node selection problem for varying set sizes E {1, 2,, .,.., 1024). We evaluate the accuracy of each method using three metrics: overall opinion, along with two standard ranking measures, precision and Normalized Discounted Cumulative Gain (NDCG) 48). We initialize internal opinions with uniform distribution as their configuration does not significantly affect experimental results.
Methods. We present numerical results to evaluate the performance of our proposed algorithms, RWB. FOREST and MAXINFL LUNEEEEEE against existing baselines. For consistency, MAXINFLUENCEESET as MIS in the following text. In all experiments, we set the absolute error pa- rameters of RWB to 10-2 For algorithm FOREST, set the number of samplings / 4000. We set the initial error parameter of algorithm MIS to 10 To further demonstrate the effectiveness of our approach, compare against five widely-used benchmark algorithms: TOPRANDOM, TOPDEGREE, TOPCLOSENESS, BETEENNESSSSS, and TOPPAGERANK [49] across all networks.
abbreviate
Resistance Coefficient Distributions. In our experiments, resistance coefficient are generated using three distinct distributions: uniform, normal, and exponential. They are abbreviated as Unif., Norm., and Exp. in the figures. We set the minimum value of the resistance coefficient Omin 0.01 because a zero resistance coefficient would lead to non-convergent results. For the uniform distribution, each node i is assigned opinion s; uniformly sampled from the interval [Amin 1]. For the normal distribution, each node is assigned a sample 2; drawn from the standard normal distribution 2; (0, 1). These values are then normalized to the interval [ommiu 1]. For the exponential distribution, we generate n positive numbers r using the probability density function f(x) = where Tauin 0. These values are similarly normalized to the range [Amin: 1) to represent resistance coefficients.
Efficiency. Table 2 compares the execution time of three algorithms: RWB, FOREST, and our proposed MIS (with k = 64), under various resistance coefficient distributions. The direct matrix inversion based EXACT algorithm was excluded from the comparison as it failed to complete
8

---

Table 2: Running time with k = 64.
Time(s)
Name
RWB
FOREST
MIS
Unif.
Norm.
Exp.
Unif.
Norm.
Exp.
Unif.
Norm.
Exp.
DBLP
120.61
101.72
703.31
66.02
58.65
104.41
0.28
0.51
1.81
Google
344.02
326.83
1368.66
162.87
154.62
223.67
0.39
0.40
2.91
Youp
896.66
900.97
10495.42
196.53
208.92
312.03
1.03
0.87
6.85
Pokec
1037.87
1028.07
6562.19
467.81
493.82
784.69
3.72
3.21
24.68
Flixster
2342.12
2142.68
326.52
321.75
376.91
2.59
2.14
13.56
LiveJournal
3275.20
2580.90
1454.37
1472.17
2147.34
8.61
13.17
56.49
Twitter
12115.80
13230.32
13852,17
279.73
270.61
1841.55
Sina Weibo
10538.27
10749.41
11743.13
156.83
171.75
1712.25
MIS -B- RWB -a- FOREST -Q- TOPRANDOM -a- TORDRGRPE -4- TORCESSENESS -0- TOPBETWEENNESS
TOPPAGER ANK
1dF
10P
Overall opinion
7.02
1.82
7.56
5.6
Precision
0.5
0.5
NDCG
0.5
0.5
0.5
100
10a
10'
10
10
109
10
10
10a
100
10
10P
(a)DBLP
(b)Google
YoutuueeSSpup
(d)Pokec
Figure 1: Performance of algorithms in accuracy across four smaller graphs
even on the smallest DBLP network within the 6-hour time limit. Similarly, RWB executions exceeding 6 hours on large-scale networks with strict resistance distributions were terminated due to impractical runtime requirements. contrast, both FOREST and MIS demonstrated robust scalability, successfully processing networks with tens of millions of nodes across all distribution scenarios. The data reveals that FOREST consistently achieves faster execution than RWB, while MIS outperforms both algorithms by substantial margin in all test conditions. Notably, the execution time of RWB and MIS shows considerable sensitivity to resistance coefficient distributions, whereas FOREST maintains relatively stable performance in most cases despite distribution variations. As shown in Table 2 the excellent efficiency of our MIS algorithm can easily applied in large-scale networks containing tens of millions of nodes, whether directed or undirected. This performance advantage makes MIS feasible solution for large-scale network analysis tasks in the real world.
Accuracy. Figures D and presents comprehensive evaluation of opinion optimization per- formance, precision, and NDCG scores for all methods under uniformly distributed resistance coefficients. Due to excessively long running times, we omitted the performance of the RWB algo- rithm on the Twitter and Sina SeibWo networks Figure 2 Our experimental evaluation reveals that the proposed algorithms (RWB, FOREST, and MIS) consistently outperform all baseline methods across all evaluation metrics. This superior performance demonstrates the effectiveness our ap- proach in opinion optimization tasks. The result shows that while RWB and FOREST exhibit show measurable variations in precision under certain conditions, these fluctuations not substantially affect their overall opinion optimization performance. The robustness of these algorithms across

---

TOORANDOM
TOHDEGRBE
TOPCLOSENESS
TOCBETWEINNES
TOPPAGERANK
Overall opinioon
31
1.34
1.52
1:28
8-8-0-0
Precision
0.5
0.5
05
0.5
NDOG
(a)slixtter
(h)LiveJourna
(e)Twitter
(d)SinaWeiho
Figure 2: Performance of algorithms in accuracy across four larger graphs.
different network structures further confirms their practical utility. Notably, the MIS algorithm achieves perfect computational precision (exactly 1) while maintaining NDCG scores approaching 1, indicating both optimal opinion optimization results and accurate sequence ordering. When combined with its exceptional efficiency demonstrated in Table these results further underscore the superiority of the MIS algorithm in both accuracy and computational performance.
8 Limitations
Despite its advantages, our MIS algorithm has certain limitations. As formally established in Theo- remB] the algorithm remains sensitive to resistance coefficients ceeficients-paaticulaaly exhibiting prolonged runtime when these values are small. Furthermore, in exact optimization scenarios where boundary nodes contribute equally, the algorithm may encounter termination issues, though such cases are practically negligible. We note that this edge case can be effectively addressed by relaxing constraint conditions.
Conclusion
This paper proposes novel solutions for optimizing overall opinions in social networks by modifying the internal opinions of key nodes. As traditional matrix inversion methods face computational limitations in large-scale networks, introduce a random walk interpretation, we further develop a exact asynchronous update algorithm. This deterministic asynchronous approach provides guaranteed update operations and progressive refinement to efficiently and exactly identify nodes with the greatest potential influence. Extensive experiments demonstrate that compared baseline methods and our sampling approaches, this method achieves superior efficiency and accuracy while effectively scaling networks with tens of millions of nodes. Future research directions include extensions dynamic network configurations and multi-opinion optimization scenarios.
sampling- based algorithms. Building upon
bounds, leveraging asynchronous
Acknowledgments
This work was supported by the National Natural Science Foundation of China (No. 12)..
10

---

References
[1] H. Ledford. "How facebook, twitter and other data troves are revolutionizing social science," Nature, vol. 582, no. 7812, pp. 328-331, 2020.
[2] D. Notarmuzi, C. Castellano, A. Flammini, D. Mazzilli, and F. Radicchi, "Universality, criticality and complexity of information propagation in social media," Nature Communications, vol. 13, no. p. 1308, 2022.
[3] G. Pasi and R. R. Yager, "Modeling the concept of majority opinion in group decision making," " Information Sciences, vol. 176, no. 4, pp. 390-414. 2006.
[4] R. Abebe, J. Kleinberg, D. Parkes, and C. E. Tsourakakis, "Opinion dynamics with varying susceptibility to persuasion." in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 1089-1098.
[5] T. H. Chan, Z. Liang, and M. Sozio, "Revisiting opinion dynamics with varying susceptibility to persuasion via non-convex local search," in Proceedings of the World Wide Web Conference, 2019, pp. 173-183.
[6] R. Abebe, T.-H. H. Chan, J. Kleinberg, Z. Liang, D. Parkes, M. Sozio, and C. E. Tsourakakis, "Opinion dynamics optimization by varying susceptibility persuasion via non-convex local search," ACM Transactions on Knowledge Discovery from Data. vol. 16, no. 2, pp. 1-34, 2021.
[7] A. Gionis, E. Terzi, and P. Tsaparas, "Opinion maximization in social networks," in Proceedings of the 2013 SIAM International Conference on Data Mining, 2013, pp. 387-395.
[8] Z. Zhang, W. Xu, Z. Zhang, and G. Chen, "Opinion dynamics incorporating higher-order interactions," in 2020 IEEE International Conference on Data Mining, 2020, pp. 1430-1435.
[9] I.. Zhu, Q. Bao, and Z. Zhang, "Minimizing polarization and disagreement in social networks via link recommendation," Advances in Neural Information Processing Systems, vol. 34, pp. 2021.
[10] J. Klausen, C. E. Marks, and T. Zaman, "Finding extremists in online social networks," " Opera- tions Research, vol. 66, 4, pp. 957-976, 2018
[11] Jia, A. MirTabatabaei, N. E. Friedkin, and F. Bullo, "Opinion dynamics and the evolution of social power in influence networks," SIAM Review, vol. 57, no. 3, pp. 367-397, 2015.
[12] Y. Dong, M. Zhan, G. Kou, Z. Ding, and H. Liang, "A survey the fusion process in opinion dynamics," " Information Fusion, vol. 43, pp. 57-65, 2018.
[13] B. D. Anderson and M. Ye, "Recent advances in the modelling and analysis of opinion dynamics on influence networks." International Journal of Automation and Computing, vol. 16, no. 2, pp. 129- 1099-14,2200 2019.
[14] A. V. Proskurnikov and R. Tempo, "A tutorial on modeling and analysis of dynamic social networks. part I," Annual Reviews in Control, vol. 43, pp. 65-79, 2017.
[15] H. Hassani, R. Razavi-Far, M. Saif, F. Chiclana, O. Krejcar, and E. Herrera-Viedee Viedma, "Classical dynamic consensus and opinion dynamics models: survey of recent trends and methodologies," Information Fusion, vol. 88, pp. 22-40, 2022.
[16] H. Noorazar, K. R. Vixie, A. Talebanpour, and Y. Hu, "From classical to modern opinion dynamics," International Journal of Modern Physics C, vol. 31, no. 07, p. 2050101, 2020.
[17] M. Okawa and T. Iwata, "Predicting opinion dynamics via sociologically-infomeed neural networks," in Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2022, pp. 1306-1316.
[18] A. De, S. Bhattacharya, and N. Ganguly, "Shaping opinion dynamics in social networks." in Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, 2018, pp. 1336-1344.
11

---

[19] M. H. DeGroot "Reaching a consensus," Journal of the American Statistical Association. vol. 69, no. 345. pp. 118-122 121, 1974.
[20] N. E. Friedkin and E. C. Johnsen, "Social influence and opinions," Journal of Mathematical Sociology, vol. 15, no. 3-4, pp. 193-206, 1990.
[21] G. He, W. Zhang, J. Liu, and H. Ruan, "Opinion dynamics with the increasing peer pressure and prejudice on the signed graph." Nonlinear Dynamics, vol. 99, pp. 3421-3433, 2020.
[22] U. Chitra and C. Musco, "Analyzing the impact of filter bubbles social network polarization," in Proceedings of the 13th International Conference on Web Search and Data Mining. 2020, pp. 115-123.
[23] Semonsen, C. Griffin, A. Squicciarini, and S. Rajtmajer, "Opinion dynamics in the presence of increasing agreement pressure," IEEE Transactions Cybernetics, vol. 49, no. 4, pp. 1270-1278, 2018.
[24] A. Das, S. Gollapudi, R. Panigrahy, and M. Salek, "Debiasing social wisdom," in Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2013, pp. 500-508.
[25] D. Bindel, J. Kleinberg, and S. Oren, "How bad is forming your own opinion?" Games and Economic Behavior, vol. 92, pp. 248-265, 2015.
[26] G. Wang, R. Zhang, and Z. Zhang. "Efficient algorithms for relevant quantities of friedkin- johnsen opinion dynamics model," in Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2, 2025, pp. 2915-2926.
[27] C. Ravazzi, P. Frasca, R. Tempo, and H. Ishii, "Ergodic randomized algorithms and dynamics over networks," IEEE Transactions on Control of Network Systems, vol. 2, no. 1, pp. 78-87, 2014.
[28] J. Ghaderi and R. Srikant, "Opinion dynamics in social networks with stubborn agents: Equilib- rium and convergence rate," Automatica, vol. 50, no. 12, pp. 3209-3215, 2014.
[29] Y. Yi, T. Castiglia, and S. Patterson, "Shifting opinions in a social network through leader selection," IEEE Transactions on Control of Network Systems, vol. 8, no. 3, pp. 1116-1127, 2021.
[30] H. Sun and Z. Zhang, "Opinion optimization in directed social networks," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 4, 2023, pp. 4632-
[31] S. Tu, C. Aslay, and A. Gionis, "Co-exposure maximization in online social networks," Advances in Neural Information Processing Systems, vol. 33, pp. 3232-3243 2020.
[32] K. Garimella, A. Gionis, N. Parotsidis, and N. Tatti, "Balancing information exposure in social networks," Advances in Neural Information Processing Systems, vol. 30, 2017.
[33] E. Mackin and S. Patterson, "Maximizing diversity of opinion in social networks," in 2019 American Control Conference, 2019, pp. 2728-2734.
[34] A. Matakos, S. Tu, and A. Gionis, "Tell me something my friends do not know: Diversity maximization in social networks," Knowledge and Information Systems, vol. 62, pp. 3697-3726. 2020.
[35] X. Chen, J. Lijffijt, and T. De Bie, "Quantifying and minimizing risk of conflict in social networks," in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, 2018, pp. 1197-1205.
[36] Y. Wang and J. Kleinberg, "On the relationship between relevance and conflict in online social link recommendations." Advances Neural Information Processing Systems, vol. 36, pp. 36 708-06666 725, 2023.
12

---

[37] J. Gaitonde, J. Kleinberg, and E. Tardos, "Adversarial perturbations of opinion dynamics in networks," in Proceedings of the 21st ACM Conference on Economics and Computation, 2020, pp. 471-472.
[38] C. Musco, C. Musco, and C. E. Tsourakakis, "Minimizing polarization and disagreement in social networks," in Proceedings of the 2018 World Wide Web Conference, 2018, pp. 369-378.
[39] A. Matakos, E. Terzi, and P. Tsaparas, "Measuring and moderating opinion polarization in social networks," Data Mining and Knowledge Discovery, vol. 31, pp. 1480-1505, 2017.
[40] N. E. Friedkin and E. Johnsen, "Social influence networks and opinion change." Advances in group processes, vol. 16, no. 1, pp. 1-29, 1999.
[41] A. Ahmadinejad, S. Dehghani, M. Hajiaghayi, H. Mahini, S. Seddighin, and S. Yazdanbod, "Forming external behaviors by leveraging internal opinions," in 2015 IEEE Conference on Computer Communications, 2015, pp. 1849-1857.
[42] N. E. Friedkin, "A formal theory of reflected appraisals in the evolution of power." Administrative Science Quarterly, vol. 56, no. 4, pp. 501-529, 2011.
[43] W. Xu, L. Zhu, J. Guan, Z. Zhang, and Z. Zhang, "Effects stubbornness on opinion dynam- ies," in Proceedings of the 31 ACM International Conference Information & Knowledge Management, 2022, pp. 2321-2330.
[44] P. Chebotarev and E. Shamis, "Matrix-forest theorems," arXiv preprint math/0602575, 2006.
[45] J. Kunegis, "Konect: the koblenz network collection," in Proceedings of the 22nd International Conference on World Wide Web, 2013, pp. 1343-1350.
[46] Leskovee and R. Sosič, "Snap: A general-purpose network analysis and graph-mining library," ACM Transactions Intelligent Systems and Technology, vol. 8, no. 1, pp. 1-20, 2016.
[47] R. Rossi and N. Ahmed, "The network data repository with interactive graph analytics and visualization," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 29, no. 1, 2015.
[48] K. Järvelin and Kekäläinen, "Ir evaluation methods for retrieving highly relevant documents," in ACM SIGIR Forum, vol. 51, no. 2, 2017, pp. 243-250.
[49] L. Vassio, F. Fagnani, P. Frasca, and A. Ozdaglar, "Message passing optimization of harmonic influence centrality," IEEE Transactions on Control of Network Systems, vol. no. pp. 109-120, 2014.
[50] R. P. Agaev and P. Y. Chebotarev, "Spanning forests of digraph and their applications." Automation and Remote Control, vol. 62, pp. 443-466, 2001.
[51] P. Chebotarev and R. Agaev, "Forest matrices around the laplacian matrix," Linear Algebra and its Applications, vol. 356, no. 1-3, pp. 253-274, 2002.
[52] D. B. Wilson, "Generating random spanning trees more quickly than the cover time." in Proceedings of the twenty-eigtth annual ACM Symposium on Theory of Computing, 1996, pp. 296-303.
[53] L. Avena and A. Gaudillière, "Two applications of random spanning forests," Journal of Theoretical Probability, vol. 31, no. 4, pp. 1975-2004, 2018.
13

---

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]
The abstract and introduction accurately reflect the paper's contributions, in- cluding proposing efficient sampling- caapliig-basedd algorithms (RWB, FOREST) and deterministic asynchronous algorithm (MIS) for opinion maximization in large-scale networks. The claims align with theoretical analysis and experiments real-world datasets (Section 4-7).
Justification:
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 the paper and important assumptions and limitations. A No or
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 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 of the work performed by the authors?
Answer: [Yes]
Justification: The paper acknowledges limitations in scalability of traditional methods and mentions future extensions dynamic networks multi-opinion scenarios (Section 8).
Guidelines:
The answer NA means that the paper has 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 separate "Limitations" section in their paper.
The paper should point 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 on 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best 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.
3. Theory assumptions and proofs
14

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Theoretical assumptions (c.g., resistance coefficients E (0, 1) are clearly stated. Proofs for lemmas and theorems are provided Appendix with logical derivations.
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 referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to 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
Question: 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)?
Answer: [Yes]
The paper details the algorithm implementations (e.g.. RWB, FOREST, MIS), parameter settings. dataset sources, and hardware configurations in the Experiments section (Section 7). This information is sufficient for independent researchers to reproduce the main experimental results.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, 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 a dataset and/or model, the authors should describe the steps taken to 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, may be necessary to 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 good way to accomplish this, but reproducibility 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, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS 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 to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution 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).
15

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe 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 be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The experimental code has been packaged into ZIP files and submitted sup- plementary materials with the paper. Sufficient instructions are provided in the supplemental material faithfully reproduce the main experimental results, including details on dataset preparation, parameter settings, and execution steps.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpa://nips.co cc/
htwllicc/uiides/ooeeSubbbe otwooddeebbimssiooooooooooo ssionpolicy for more details.
While 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 open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (httpp:
7 ctlpp.scccppbllt gu des/ (ooeeubmisssi wssiiiooicccyyyy for more details.
The authors should provide instructions data access and preparation, including how to 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. 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 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental setup includes dataset statistics, machine specifications, parame- ter choices, and baseline methods. See Table and Section 7.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of 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, or 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]
16

---

The deterministic nature of the MIS algorithm ensures zero variance in its outputs. Furthermore, we provide rigorous mathematical definitions for all test distribu- tions (unforriioomml/eesonnntiaa and their parameters, with comprehensive experimental validation demonstrating consistent performance.
Justification:
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, at 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to 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 I-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 range (e.g. negative eтror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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 to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper provides complete computational resource specifications: (1) Dataset scales (nodes/edges) are detailed in Table I; (2) Execution times for all algorithms reported in Table 1 and Figure 2; (3) All experiments were conducted in single-threaded mode on a 28-core 2.0GHz Xeon server with ITB RAM, as specified in Section 7.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
inee?
Answer: [Yes]
Justification: This work is purely algorithmic and does not involve any research with human participants, crowdsourcing, or data collection from human subjects. All experiments are conducted publicly available benchmark datasets.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
17

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
The paper discusses both positive applications (c.g.. public health campaigns, political elections) and potential negative socictal impacts (e.g., opinion manipulation risks) in Sections and 8, fulfilling the requirement for broader impact analysis.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
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 intended and functioning correctly, harms that could arise when the technology is being used as 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 a 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]
This study belongs basic algorithm research and does not involve the publication of high-risk models or data (such as large language models or sensitive datasets), therefore, it is not subject to safeguard measures requirements.
Justification:
Guidelines:
Justification: The paper introduces new algorithmic implementations (e.g., RWB, FOREST, and MIS) part of its contributions. These assets well-ddcu in the Methods and Experiments sections (Sections 5-7), with detailed descriptions of the algorithms, parameter settings, and computational workflows. The code is released under the MIT License, and documentation is provided in the supplemental materials ensure reproducibility.
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.
18

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but 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]
The public datasets (Koblenz, SNAP, Network Repository) have been sourced, but specific licenses have been cited. The data source references (such as [42], [43], [44]) have been provided (Section 7).
Justification:
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.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com honndataseetss 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 it 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 paper introduces algorithmic implementations (e.g.. RWB, FOREST, and MIS) as part its contributions. These assets are well-documented in the Methods and Experiments sections (Sections 5-7), with detailed descriptions of the algorithms, parameter settings, and computational workflows. The code is released under the MIT License, and documentation is provided in the supplemental materials to ensure reproducibility.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
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)?
Question:
Answer: [NA]
19

---

Justification:
The work does not involve human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 to the NeurIPS Code of Ethics, workers involved 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: No human subjects are involved.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending 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 the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it 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, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLMs are not used in the core methodology. Writing/editing uses standard tools without LLM assistance.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy hate:s////eerrssscc/////oeerrrre for what should or should be described.
20

---

Appendix
A Omitted Proofs
A.1 Proof of Lemma
According to Neumann series, we have M (1- ((I R)P R. Let
p; e Ei=g ((I P)* represent the absorption probability vector of absorbing random
walks starting from node i. Hence, we have:
Pn. Σ M(
Σ E Σ ((I
R)P) Re, Ep(lo).
iEV
A.2 Proof of Lemma
Algorithm RWB simulates N independent of the absorbing random walk {X:)
where:
n, the i-th walk absorbed by v,
X;
0, otherwise.
The estimator P. N Σm X, has the following properties:
Elp.l
E[X,] = n
Epa(v) Pv.
Pu(v)=
N
N
Varlpu]
Var[X,]
[B[ - E[X,}²)
N2
N2
1=1
1=1
1
n2
Pe
pb
Po(n Po)
n²
N
n
N
4N
now apply the following Chernoff bound for bounded variables.
Lemma 9 (Chernoff Bound). Let X₁(1 I i S N) be independent random variables satisfying
X, < FXX.] + M for 1 < i S N. Let X E X; Assume that E and Var [X] are respectively the expectation and variance of X. Then we have
X²N 2Var + 2M1/3
Pr([X - 2 A) 2exp(
Applying this lemma with n and = E, we obtain
NN
2
Pr (r Pul e) 2exp
-eexp
2. IN + 2ne/3
n²
+ 2ne/3
2N
When N = log we have Pr Pr pol 2 E) 5
21

---

A.3 Proof of Theorem 1
We first prove the expected length of a random walk. Since Ei=l 1.1-11== have
(1-z)² for | < 1, we
Walk length starting from node u|
Σ
Pr(Walk length starting from node is /)
1=0
Σ
e ((I
R)P) R1
1(1
amin)aama
1=0
1=0
Omax
(1
amin
1(1
Omin
1111
0'max
ammnn)
Omin
According Lemma we have N log n, hence the upper bound of time complexity is
O Ormar (1 -Omin) n logn). n).
Paz
A.4 Proof of Lemma 3
We begin by establishing the representation M = (Q + L)- Starting from the definition of M,
we derive
M = (I - (I-R)P (I (I- R)D A) R (D(I R)- A) RRR R
=(D) LDD R A) - = QD= R
D A)
1=0
1=0
(D R
R - (Q + Q.
To prove Lemma we invoke a result from concerning spanning converging forests:
Lemma 10 (144). Let L-s be the matrix obtained from by deleting the rows and columns corresponding to the nodes in S V. and let Fs be the set of spanning converging forests of graph 9 with |S| components that diverge from the nodes of S. Then, the determinant det (L)( Erer, wFF), where w(F) represents the product of edge weights forest F. Furthermore, for any nodes i.j E VV S, the ccofaccootttor L = =E wFF).
Let Lg M Q - Q), We analyze det Ly) follows:
Let(Lg)) det Q 1-1) det + Q)
IIeev ((v,v) det Q)
n
det((_s)) II Q(u,u)
Ivev 2(
t=
SCV
MES
18T=1
1
1
w(F) II Qu,
IhEY Q(T,v)
PEFs
|ST=1
1
Σ
Σ w(F)
II
(u, u)
IIVEV 2(v,v)
SCV FEJs
WES
1
Σ
w(F)
Qu,
TvVv Q(v,v)
FEF
uEr(F)
22

---

For the coofacoo Ey, we similarly obtain
Q(i,))
det(Ly)) det((( det((L+ Q)
II.vv Q(u,0) det((L + Q)
Q(i,i)
n-1
Σ
de
s) II Q(u, u)
Iuvv ((1,))
t= SCV S|
WES
Q(i,i)
Σ
Σ
w(F) II WSS
(u,
ΠLev ((1,))
t= SC (CM) FEF
[S] =t
Q(i,i)
Σ
w(F) II
Quu,u) u)
ILLvv ((v,0)
SCV\(15) FEFLY SUC0 aES
Σ w(F) II uu,
ILev Q(u,v)
PEFU
mEr(F)
Since all edge weights in 9 are 1, the inverse In simplifies to
bn (i. = dot(L,)) EFERs: IHEERFY) Quu,u)
det(Ly) Erer IIEE(()) Q(u,
Finally, as a. = Evev M(r,i) = Evey , i), the expression for node i's structual centrality A follows
(v,
ErerU IIuEr(F) Q(u, u) ΣFEr IIuEr(P) Q(u, u)
P: Σ
This completes the proof of Lemma
3
A.5 Proof of Theorem
The time complexity of the algorithm depends on the times nodes are visited in loop-erased random walks. Thus, the time complexity of FOREST
Σ (I - ()))) = Tr((T - -1- S Tr(M)
Omin
VEV 1=0
Since M (i,j) < 1 for any i,j V, the final time complexity is obtained as O Dieiin
In).
A.6 Proof of Corollary !
Define the ground-truth utility of set T as U(T) = Eier P:(1 s;) and the estimated utility as Ü(T) = Eter (:(1 8;).
By the error condition |p: Pil S for any set T with [T'l k, we have:
(((T)-(())
Σ(e: - p1) - -s)
< Σ c(1 s1) S kc,
IET
TET
where the last inequality holds because 0 S - 8, S 1. This implies
U(T) + ke > Ú(T) 2 U(T) ke.
(4)
Since we select I to maximize (T), it satisfies
Ú(Í) 2 Ú(T*) 2 U(T*) ke,
(5)
23

---

Combining 4 and 1 we bound (T) as:
U(T) 2 (T)) ke (U(T)) - -e)-k)--
- ke = U(T*) - 2KE.
Thus,
Liet pi(l 84) >>)Er ((1-ss) 2ke, required.
A.7 Proof of Lemma
We demonstrate that the invariant holds by using induction. First, we verify that before any computa- tion has begun, the invariant is satisfied by the initialized values:
A Å -
0
M
Let r denote the residual vector before an update task for any node i, and let na residual vector after the update task. Then single update task corresponds to the following steps:
(++1) denote the
(I+1) = (1) s) Re,, (f+1) = (1) (1) + (1) -)- = r!
(1 PT (
A (9)
(0) (1- M T Ta it follows that
Assuming that
(t-1) I)
(t) T (1 (1-8)) 8 Rr!
A
A
A
(1 8) O M r! r! 8) 2 Re,
(1 0 M
(1+1) + 110 (i)(I PT(I R))e:) - (1) 8) @ Re;
(1 8) @ M r (1+1)
which completes the proof.
A.8 Proof of Lemma
On the one hand, since T. 2 O. by Lemma 4 we have A(v) > A(v), Ve E V; on the other hand, the condition in Line 2 of Algorithm Iidiicates that, after termination, the vector ra S e1, then we have that:
A Å = (1 8) M To I c(1 M
(6)
The equation above implies that (1 - ()) S Á (v), Vu e V. hence the estimator À returned by
Algorithm satisfies (1 E) A (v) < (v) S (u)).
A.9 Proof of Lemma
We demonstrate that the invariant holds by using induction. First, we verify that before any computa- tion has begun, the invariant satisfied by the initialized values for any node v E V:
A (u)) (A(v) + (v) (v)) -(-s(v)) e. M = AMR111
Let (t) denote the residual vector before an update task for any node and let r (t+1) denote the residual vector after the update task. Then a single update task corresponds to the following steps:
A (++1)_ Á (t) + +r(u)) (.f
(++1) (t) (0 (u)e, + ! (u) R)Pe, (0- (0) (I R)
Assuming that (v) - (A(v) A0) = r MR (0) it follows that
A (Uv) - ( (v) + Á ((+1)) A(v) ( (v) (1) +ra(w) (1)
= =T MR r(() ra(u) (u)
= =r.MRR.
r (t+1) + (1) - (I- (R)))))c.) - -ra(u) .:.
=r MR (ITR-1,((1)) (++1)
which completes the proof.
24

---

A.10 Proof of Lemmal 7
On the one hand, since rs 2 0, by Lemma 6 we have ( (A(v) + 2 0; on the other hand,
the condition in Line 2 of Algorithm 2 indicates that, after termination, the vector rs S eR1, then we have that
A (v) (v) + + = MR Ta S cr M1 (ra)sum-
Hence the estimator Á returned by Algorithm satisfies
A (v) (á(t) +)) ()
A.11 Proof of Lemma g
We present the proof for absolute errors; the relative error case follows analogously through error bound transformations and is thus omitted.
Let S denote the optimal size-k node set. We first show that any node i T must belong to S*. By definition of T, we have ( 2 ((++1) + c. Applying the error bound yields a(i) 2 a(i) 2
(K+1) + For any node j & S", it holds that
a(j) S (K+1) & ((tt) + a(i).
This shows (ii) a(j) for all j $ St, which implies S*.
Next, we prove that S* 7 C C. Suppose for contradiction that there exists E S* with & T TUC.
By definition of C, this requires a(i) (1) Using the error bound, we obtain
( S a(i) + @(2)-
However, since E S", optimality implies (1)) 2 (R) 2 a(y), which contradicts the above inequality. Therefore, S S C must hold.
A.12 Proof of Theorem 3
We first proof Lemma which explains the upper bound of the time complexity of Algorithm] 1
Lemma 11. An upper bound on the running time of Algorithmm / is O dmax log ).)
Proof. During the processing, we add a dummy node that does not actually exist. This node is initially placed the head of the queue and is re-appended to the queue each time is popped. The set of nodes in the queue when this dummy node processed for the (i + 1)-th time is regarded as
s(),, and the residue vector this time is regarded as (t) The sum of the vector (1) is denoted as (ra))um- The process of handling this set considered the (i + 1)-th iteration. In the context of the (i + 1)-th iteration, when node ((() is about to be processed, it holds that ra(e) 2 r (e). Upon completion of this operation, the sum of residual vector is decreased by a& Ta (v). Consequently,
by the conclusion of the (i + 1)-th iteration, the total reduction in the sum of residue vector amounts to:
(ra) (r))
(r,
(i+1)) (ra)sum
Σ (v) 2
Σ r (v).
VES
wES(9)
Given that the bound for any node v is obtain:
Evesto ra (((())
Enggoo (0)
2 and
Sc.
|SO)
IV S(0)
Therefore, it follows that:
Evegco (e)
Evegco (() + E ggg ((9(()) (v)
(r (0)
|St0] |St0] + IV Sti
25

---

Substituting the above expression into Eq. 77. we obtain
(ra
sum
(1+1)
- (raa)sun
O, (v) S (ra) Omin
(()
Σ
(
DES
rES()
amin
(g()) (r
amin
( (To)
sumu
n
t=0
By utilizing the fact that x S we obtain
(1+1) (ra)sum
S
exp
( Σ (5(i n.
(-aming
Amiin
(8)
Let = = |S(t] be defined as the total number of updates before the start of the (i + 1)-th iteration. According to Eq. (). to satisfy (ra)sum ((+
I en, it suffices to find the minimum number of
updates that meets the following conditions:
Omiu T(iit))
S cxp (- O'uin T-()) r())
cxp
n
n
Thus, obtain (
<
log < T(+11) Given the fact that T(++1) T(() =18(0| I n,
Omin
further derive
T(+1) < T + n log
n.
amin
For node v, the push operation reduces (ra)aum by ( Consequently, after incurring a total the reduction (Ta)sum at least ea.T. Hence starting from the state of (Ta)sum I en, the time cost T is bounded by O(n/amiin thereby constraining the overall time complexity of Algorithm to O S n log
number of updates
For the refinement stage, first proof the time complexity of Line 7 in Algorithm when the absolute error parameter e = 1. Assuming that estimating node is v E V, the contribution of r, at node V each time is (u). Due the existence of boundary h [ra]eom R1, its minimum value is Os., and the upper bound on the total contribution is (1 (u,)) v). Therefore, the upper bound on the number of updates node is the candidate set returned in Line 3 of Algorithm Bis Ca. the upper bound of the time complexity during the first round of execution
(Ca PPa)amm-111 (1-
Therefore, assuming that
Og
refinement stage
(Ta)sum (1 M v),
(ra)sum dmax
Σ
Σ
M(u,v) v)
Ommn
V WEV
WEV VEC.
(Ta)sum dyaxx
C dd
Σ
Σ Pu-
Pv
Omin
O'min
rECa
VEC.
Now we consider when absolute enror parameter 3.
..... We assume that the error
in one round of the process is c', so the error in the previous round of the process is 2c'. The upper bound of time complexity of this round is
Σ Σ
2e' (é/((r)sum (1 (()))
< Ommin VEC, NEV
2 E
(MM))W)) = -Call
2m
d'((r))uma
Oman
VEC. NEV
When the current error 1 the upper bound of the total time complexity from c' to 21 26m Hence, when e' < kigp. the upper bound of the total time complexity is [Cal Opgi-
24
is C
Ownn
26

---

Hence, the upper bound of time complexity of Algorithm iss
O d
max Omin
(log
+
Σ Po)
Ca m kgap Ommin
).
c VEC²
Under normal circumstances, when sufficiently small, we obtain [Cal as either 0 or a relatively small constant. Therefore, can derive the upper bound of time complexity O max" log EpppOkmnn the general case.
Omin
B Forest Sampling Algorithm
For a graph G = E), a spanning subgraph of G is a subgraph with node set V and edge set being subset of E. A converging tree is weakly connected graph where exactly one node, called the root, has out-degree O, while other nodes have out-degree 1. An isolated node is considered a trivial converging tree with itself the root. A spanning converging forest of G is spanning subgraph in which every weakly connected component a converging tree. This structure coincides with the notion of in-forest introduced by [50] and further studied by [5]]. Spanning converging forests are closely related to the fundamental matrix of our model. Following the Lemma ( and its Proof it can be shown that the any entry of the fundamental matrix can be represented in the form of spanning converging forest.
Wilson's ' algorithm [52) provides efficient method for generating uniform spanning trees by leveraging loop-erased absorbing random walks. For any graph G (V, E), Wilson's ' algorithm can be adapted generate uniform spanning converging forest, by using the method similar to that in
53 30
The details of the algorithm are presented in
Algorithm 4: RANDOMFOREST(C, R)
Input :graph G. resistance matrix R. Output :root index vector RootIndex.
for +-1 1 to do L InForest[i] < false; Next[i] + 11; RootIndex[i] 4 0;
for i to do <;;;; i;
while not InForest(u] do if RAND() I an then
InForest[u] f- true
Next[u] &- -1
RootIndex(ui <-
10
else
11
+ Next[u] + RANDOMSUCCESSOK(C, G)
12
RootNow <- RootIndex[u]
13
for u 5 i; not InForest[u]: u +- Next/uj do
14
InForest[u] <- true
15
RootIndex[u]] +- RootNow
16
return RootIndex
The Algorithm Ainitializes three vectors: InForest (marks nodes added to the spanning forest), Next (tracks random walk steps), and Rootindex (records root assignments), all set to false, -1, and respectively (Line 1). For each node in order (Line 3), it performs loop-erased absorbing random walk that terminates either: (1) with probability a (making a new root, Line 6-7), or (2) upon hitting existing forest nodes (Line 5). The walk's 's path is recorded in Next. After termination, the algorithm backtracks along the walk path (Line 13-14), adding all nodes to forest and assigning them current root index. This continues until all nodes are processed (Line 3), returning the RootIndex vector representing the sampled rooted spanning forest (Line 15). Then, based on Lemma 3 we obtained the implementation of our algorithm FOREST, and the pseudocode is shown in Algorithm
27

---

Algorithm 5: Forest(G, R. 1)
Input :graph 9, resistance matrix R, internal opinion vector sample count 1.
Output :the target set I'. Initialize ' + 0: p 2 for f- 1 to do
RootIndex for i <- 1 to n do RootIndex(i]
RANDOMFORESTCG R)
Pr Pu +1
+-= p/l
8 for i to do
arg of Po(1 s8))
Tu
return f
C Additional Experiments
C.1 Efficiency
Figure Jnn Table collectively present a comprehensive performance analysis our proposed MIS algorithm under different parameters and network conditions. Figure demonstrates the algorithm'ss 's runtime performance across all tested networks under various resistance coefficient distributions parameter varies. The results indicate that although fluctuations in the potential influence distribution near the k-th most influential node cause minor variations, MIS consistently maintains superior performance compared both RWB and FOREST algorithms in all test cases.
- uniform distribttion -o- normal distribation + exponential distribution
10a
10P
10
Time(s)
10a
10P
10-3
k
k
k
DBLP
(b)Google
(c) YoutubbSSuap
(d)Pokee
10a
10
10
Tine(s)
107
0-0-o-0-6
0-0-0-----0-0
10a
10P
10a
10P
10
10
10a
10
10a
10
10
10a
10"
10
10
k
k
k
k
Flisster
JouveaJll
Twiter
(h)Sina Weibo
Figure Running time algorithm MIS under different resistance coefficient distributions.
Complementing the runtime analysis, Table evaluates computational efficiency by examining the average number of updates per node during algorithm convergence under the specific parameter setting of k=64 and uniform resistance coefficients. The update ratios for all networks remain within a practical range of 27.06 to 249.28, with Twitter maintaining controllable levels despite largest scale while Google achieves optimal efficiency. These results confirm that the algorithm achieves near-linear time complexity in practice, with stable constant factors that do not increase significantly with network size, demonstrating strong scalability for large-scale network applications.
28

---

Table 3: Updates per node across networks.
Network
DBLP
Google
YoutubeSnap
Pokec
Flixster
LiveJournal
Twitter
Sina Weibo
Ratio
49.93
27.06
49.34
126.86
114.84
106.05
249.28
78.77
C.2 Accuracy
Extending the analysis from Figures and 2 we conduct a comprehensive evaluation of accuracy 55 performance under normal distribution conditions. Similarly, Figures 6 and demonstrate algorithm behavior under exponential distribution. The complete set of experimental results reveals several important findings. First, our proposed algorithms (RWB, FOREST, and MIS) consistently outperform all baseline methods across every tested condition. While the RWB algorithm fails complete execution within practical time limits for certain cases due to its computational complexity, the algorithms FOREST and MIS successfully deliver results all scenarios. More significantly, the MIS algorithm achieves exact solutions in every case while simultaneously maintaining perfeerfect accuracy (NDCG = 1) in sequence ordering. This combination of guaranteed precision and optimal ordering performance clearly establishes the superiority of our MIS approach over both baseline methods and our own alternative proposals.
performance across multiple experimental configurations.
-4- MBS -B- RWB -0- FORSST -Q- TOPRANDOM - TOPDEGRBE + TOPCLOSINESS -0- TOPBETWEENNESS -B- TOPPAGERANK
Overail opinion
1.64
62
7.00
1.02
7.0
7.38
1.8
7.30
8-0-0-6
Procision
0.5
05
NDCG
0.5
102
10
100
(nDDBLP
(bjGoogle
YoutubeSnpp
(d)Pokec
Figure 4: Performance of algorithms in accuracy under normal distribution.
MIS FOREST TOPRANDOM
TOEDEGRES
COOCEESESSS
TOEBETWEENNESS
TOPPAGERANK
10a
10
Overall opinion
2.58
3.00
2.57 1.3
180
2.50
2.20
Procision
NDOG
0-
(a)Flixster
(biLiveJournal
(eiTwitter
(d)Sina
Figure 5: Performance of algorithms in accuracy under normal distribution.
29

---

.104
10
Overal opinion
1.7
65
6.6
1.03
Precision
0.
85
NDOG
0.5
10
307
10
107
30
307
10
(a)DLLP
(b)Google
SoutubeeSnp
(d)Pokec
Figure Performance of algorithms in accuracy under exponential distribution.
- MIS -a- FORUST TOPRANDOM
COOCENSNN -Q- TUPBUTTHINNNS
TUPPAGERANK
Overall Overall opinion
1.4
3.1
1.78
15
1.3
14
Precision
NDOG
(a)Plixster
(biLivelournal
(eiTwitter
(diSinaWeibo
Figure 7: Performance of algorithms in accuracy under exponential distribution.
D Dataset Details
The study utilizes eight benchmark datasets obtained from the Koblenz Network Collection 45
SNAP 46 and Network Repository 47
DBLP an undirected co-authorship network where nodes represent authors and edges indicate co- authorship relationships. The dataset uses the largest connected component, with publication venues (conferences or journals) defining ground-truth communities, retaining the top 5,000 high-quality communities each containing at least three nodes. Google directed network where nodes represent web pages and edges represent hyperlinks, originating from the 2002 Google Programming Contest. YouTube an undirected social network where nodes represent users and edges represent friendships, with communities defined by user-created groups, similarly retaining the top 5,000 communities with least three nodes and using the largest connected component. Pokec is Slovak social network where nodes represent users and directed edges represent friendships, containing anonymized user attributes such as gender and age. Flixster is an undirected movie social network where nodes represent users and edges represent social connections. LiveJournal is a directed online community network where nodes represent users edges represent friend relationships. Twitter is directed social network where nodes represent users and edges represent follower relationships. SinaWeibo a directed microblogging social network where nodes represent users and edges represent social connections. Detailed statistical characteristics of each network are provided in Table [
30


Reviews:
[{"review_id": "NxqTd8nyMy", "reviewer": "Reviewer_dkDZ", "summary": "This paper proposes opinion maximization algorithms for linear dynamical system models for opinion dynamics. The authors build heavily on a previous paper reference [27] which is also for the same purpose. The authors propose an approximate algorithm for influence estimation algorithm 2 and then the max influence selector which is algorithm 3. The authors show results on Benchmark datasets.", "questions": "What is the speedup in terms of time complexity?\n\nHow exactly is this achieved, over say Forest? Showing this with some small networks will help.\n\nWhat is the performance hit?", "limitations": "There is no limitations section", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is clearly written, with some claimed algorithmic contributions\n- The problem itself is not very  novel but relevant.\n\nWeaknesses:\n- The main weakness is that the advantage of the proposed method over the baseline e.g. [27] is not clear. Algorithm 1 is from the baseline. How is algorithm 2 different? What is the time complexity of the proposed algorithm?\n\n- The second big weakness is that the paper does not connect very well to the existing literature. I think the basic problem of controlling linear dynamical systems has been tackled in great detail in the literature. Specifically in the context of opinion dynamics, see:\nhttps://dl.acm.org/doi/10.5555/3237383.3237899\nHow is the present algorithm better than the state of the art in that literature?\n\n- Finally, in experimental results it looks like MIS performs much more poorly than Forest.", "was_revised": true, "final_justification": "I still don't buy the argument that Degroot model is older and hence SLANT can't be compared against. According to my understanding the varying susecptibility model (reference [3]) is also a linear model, and hence can be controlled through linear dynamical systems. It is important that a comparison be made with this class of methods.\n\nAbout the experimental results in the performance, the graphs of MIS and Forest are overlapping. Hence, my confusion. Something should be done to improve the readability of that graph.", "rebuttal": "Thank you for the feedback and suggestions. Below are our response to your main concerns. \n\n**W1: Algorithm Advantages** \n\nThe baseline sampling algorithm relies on probabilistic approximation, meaning it can only provide probabilistic error guarantees and thus obtains an approximate optimal node set. According to Chernoff bound, its required sample size is directly proportional to $\\epsilon^{-2}$, which highlights its inherent limitations. In contrast, our algorithm employs deterministic derivation to provide exact error guarantees, enabling the identification of the precise optimal node set. As formally stated in Theorem 3, the time complexity of our algorithm MIS scales with  $\\epsilon$ as $\\log{(1/\\epsilon)}$, making it robust to the choice of error parameter $\\epsilon$ and ensuring superior efficiency. Experimental results in Table 1 show that our MIS algorithm consistently outperforms baseline methods in computational efficiency across all scenarios, while Figure 1 demonstrates its better performance quality, with additional advantages detailed in Appendix C.\n\nOur Algorithm 1 is inspired by absorbing random walk-based sampling methods, using asynchronous deterministic updates to screen candidate nodes from the entire graph. Algorithm 2 then performs reverse-direction asynchronous updates from individual node perspectives to refine this candidate set, ultimately converging to the exact optimal solution. The correctness of our approach is guaranteed by Lemma 8. The time complexity of MIS is formally presented in Theorem 3, with detailed complexity analysis for both Algorithm 1 and Algorithm 2 provided in its proof. Notably, the proof involves necessary bounding operations, meaning Theorem 3 provides an upper bound on the actual time complexity—our implementation consistently achieves better performance than this theoretical guarantee.\n\nIn summary, by leveraging deterministic asynchronous propagation methods and the mechanism formalized in Lemma 8, our algorithm efficiently obtains the exact optimal solution for Problem 1. MIS demonstrates significant advantages over baseline methods (RWB and Forest) in both computational efficiency and solution quality. Thank you.\n\n**W2: Literature Comparison**\n\nWe appreciate the reviewer’s feedback regarding the connection between our work and existing literature. While we acknowledge the foundational contributions of their work in the field of linear dynamical system control, we maintain that our contribution remains significant due to fundamental differences in models, research objectives, and scalability. Below, we provide a detailed clarification:\n\n1. **Model Differences**: The two papers employ distinct models—one uses the SLANT model, while ours is the model introduced in [3]. To our knowledge, the authors of SLANT only compared their model with the original DeGroot model, which has since undergone extensive developments (e.g., incorporating stubbornness coefficients, noise, etc.). Thus, it remains unclear whether SLANT is superior to the model we adopt.\n2. **Research Focus**: Our work aims to develop fast and efficient algorithms for solving the target problem, with our approach scalable to networks of tens of millions of nodes even in a single-threaded setting. In contrast, the referenced work primarily discusses a feasibility framework under the SLANT model, with limited attention to algorithmic design, computational complexity, or practical runtime. The largest real-world network they evaluated contains only 1,031 nodes, making it difficult to assess the scalability and real-world applicability of their method.\n3. **Target Set Differences**: As shown in their Figure 3, the target set in their work overlaps significantly with sets derived from common centrality measures. In our case, however, experimental results demonstrate that our target set differs substantially from those obtained via common centrality metrics. This indicates that our work pursues a distinct objective, potentially leading to different practical implications.\n4. **Theoretical and Practical Foundations**: As highlighted in our related work section, FJ-related models have recently seen widespread research and applications, further underscoring the value of our contributions.\n\nNevertheless, we will highlight the contributions of their work in the related work section to further ensure the comprehensiveness of our paper.\n\n**W3: Experimental Performance**\n\nWe appreciate the reviewer's attention to our experimental results. Regarding the comparison between MIS and Forest algorithms, we would like to clarify that in all tested scenarios, our algorithm MIS demonstrates consistently superior performance over Forest.\n\nSpecifically, as shown in Table 1, MIS achieves better computational efficiency than Forest across all test cases, with order-of-magnitude improvements in most scenarios. The results in Figure 1 further confirm that under identical experimental configurations, MIS not only maintains optimal performance but also achieves perfect accuracy (with precision metrics consistently at 1). Particularly in the large-scale graph tests shown in Figure 7 (with resistance coefficients following exponential distributions), while Forest exhibits noticeable difficulties in identifying optimal solutions, our MIS algorithm reliably produces perfectly accurate optimal node sets.\n\n In summary, our algorithm MIS significantly outperforms the Forest algorithm in terms of efficiency and accuracy. Thank you.\n\n**Q1: Time Complexity**\n\nAs shown in Theorem 3, our algorithm has a near-linear time complexity bound. Due to necessary proof simplifications, real-world performance is significantly better than this bound. Based on the suggestion of Reviewer vuNz, we will measure actual performance via residual update statistics to further demonstrate its efficiency advantages.\n\n**Q2: Simple Example**\n\nOur algorithm achieves its correctness guarantee through Lemma 8, which relies on the error bounds established in Lemmas 5 and 7. Based on this analysis, the MIS algorithm can compute exact optimal solutions with significantly higher efficiency compared to Forest and other sampling-based methods.\n\nConsider a two-node graph with adjacency matrix $\\boldsymbol{A} = \\begin{pmatrix}0&1\\\\\\1&0\\end{pmatrix}$, stubbornness matrix $\\boldsymbol{R} = \\begin{pmatrix}0.5&0\\\\\\0&0.5\\end{pmatrix}$, and initial opinion vector $\\boldsymbol{s} = (0.8, 0.6)^\\top$. With $k=1$ and $\\epsilon=0.5$ for Algorithm 1, the updates to $(\\tilde{\\boldsymbol{\\Delta}}, \\boldsymbol{r}_a)$ proceed as follows:\n\n| updates | node 1     | node 2      | queue       |\n| ------- | ---------- | ----------- | ----------- |\n| 0       | (0,1)      | (0,1)       | {1,2}       |\n| 1       | (0.1,0)    | (0,1.5)     | {2}         |\n| 2       | (0.1,0.75) | (0.3,0)     | {1}         |\n| 3       | (0.175,0)  | (0.3,0.375) | $\\emptyset$ |\n\nThe algorithm terminates after 3 updates when $\\epsilon=0.5$, producing $\\tilde{\\boldsymbol{\\Delta}}=(0.175,0.3)^\\top$ and $\\boldsymbol{r}_a = (0, 0.375)^\\top$. Applying Lemmas 5 and 8 gives $T = \\\\{v| \\tilde{\\boldsymbol{\\Delta}}(v) \\ge 0.35\\\\} = \\emptyset$ and $C = \\\\{v | 0.35 > \\tilde{\\boldsymbol{\\Delta}}(v) \\ge 0.15\\\\} = \\\\{1,2\\\\}$. In practice, $C$ typically contains very few nodes - for Twitter's 10M+ node network we observe $|C|<100$.\n\nFor convenience, we execute lines 5-11 of Algorithm 3 with $\\epsilon' = 0.375/2$  (where $\\epsilon'/(\\boldsymbol{r}_a) _{\\text{sum}} = 0.5$). Since no nodes in $C$ satisfy the starting condition of Algorithm 2, the vector $\\tilde{\\boldsymbol{\\Delta}}$ remains unchanged. By Lemmas 7 and 8, $T = \\\\{v| \\tilde{\\boldsymbol{\\Delta}}(v) \\ge 0.175 + (0.375)^2/2\\\\} = \\\\{2\\\\}$, and the algorithm terminates with the exact solution. This example demonstrates MIS requires just 3 updates for precise optimization, while Forest would need far more samples to achieve close precision. Both theoretical analysis and experimental results confirm the substantial advantage of MIS over Forest.\n\n**Q3: Algorithm Performance**\n\nAs stated above, we have demonstrated that Algorithm MIS achieves a near-linear time complexity upper bound. Experimental results confirm that MIS significantly outperforms baseline algorithms in both efficiency and accuracy. Thank you for your time and help."}, {"review_id": "jQ7GftP34S", "reviewer": "Reviewer_vuNz", "summary": "This paper studies the problem of maximizing opinions in social networks by modifying the internal opinions of key agents in a multi-agent network. The authors model opinion dynamics using a discrete-time linear system where each agent’s (time-varying) expressed opinion evolves based on its (fixed) internal opinion and the influence of others. At steady state, they derive a linear relationship between expressed and internal opinions, which forms the basis of their cost function measuring overall expressed opinion in the network. They analyze properties of this cost function and formulate the opinion maximization problem: selecting the top k agents whose internal opinions, if modified, would maximize overall expressed opinion. The authors propose sampling-based and asynchronous update-based methods to solve this problem and validate their approaches through comprehensive simulations on datasets including Google, Twitter, and DBLP.", "questions": "- There are many typing mistakes (e.g. “address” in line 2; “Equation” in line 112) and unclear sentences (e.g. “setting their expressed opinions…” in line 60); please correct them.\n- Is the model below line 99 DeGroot or Friedkin–Johnsen? It seems like equation (1) comes from the steady-state behavior of z(t+1)=Az(t)+s(t), for some matrix A and constant vector s(t); adding intermediate equations before (1) would help.\n- Please mention properties of f(R, s); is it non-negative, convex, and does Problem 1 fall under any known discrete or continuous optimization classes?\n- The theoretical results and time complexity are presented in terms of network dimension (n), but the simulations only report actual implementation times. This disconnect is misleading; I suggest reporting results that reflect and validate the theoretical scaling with n.", "limitations": "The authors mention limitations only briefly, with just a throw-off sentence, which is inadequate. The paper would be stronger if they explained why they did not compare their methods to other existing techniques or consider inversion methods for sparse matrices. Additionally, in the checklist, the authors state that they discuss potential negative societal impact in Sections 1 and 8, but I could not find any such discussion; it would be helpful if they made this explicit.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper is well written, clearly highlighting gaps in the literature and stating the problem with near mathematical precision. The algorithms and their time-complexity results, while not unexpected, are presented clearly and precisely. The theoretical results are supplemented with operational insights, emphasizing the probabilistic aspects and the role of network topology in the proposed algorithms. The experiments are thorough, covering networks from small to large scale to illustrate the time-complexity results effectively.\n\nWeaknesses: I list four main weaknesses to justify my rating: \n\n1) Despite the wealth of existing literature on opinion maximization, the authors unfortunately do not focus on how their algorithms compare with prior methods. This lack of fair comparison makes it hard to justify the merit of their research, in particular, how better are these methods (both qualitatively and qualitatively). \n2) The authors’ basic premise is that standard matrix inversion methods to find top k influential nodes require O(n^3) time, which is prohibitive. While this claim is true in general, given the advances in sparse matrix inversion methods – and considering that the datasets used appear to be sparse (although I might be wrong) – it is surprising that the authors did not consider or compare against such approaches. This omission represents a second lack of fair comparison.\n3) While the authors did a good job explaining the cost function in terms of central measures and other network parameters, the explanation of the optimization problem itself is weak. It does not clearly state what the optimization variables are or what it practically means to change internal opinions. Moreover, the role of network topology, such as the presence of cycles or other structural features, and how these affect optimization, is not adequately discussed. More focus is on the methods and tuning their performance than the problem itself. \n4) In the experiments, except of the names of networks, there is limited information about the nature of the social networks and how they relate to the opinion dynamics motivation. There is no clear explanation of what expressed or internal opinions represent in these datasets. This raises the concern that similar results might hold on random networks or GPS networks or road networks, making it unconvincing whether the theoretical results have any practical (social) benefit. Including a real-world social network dynamics example would have made the validation more substantive.", "was_revised": true, "final_justification": "I've not changed my score as the responses by the authors are not convincing to me.", "rebuttal": "We sincerely appreciate you for your positive and constructive feedback.\n\n**W1: Existing Works**\n\nExtensive literature exists on the influence maximization problem, yet most works primarily focus on alternative optimization strategies—such as modifying node resistance coefficients or adding edges—while approaches based on adjusting initial opinions remain relatively scarce due to their inherent complexity. Although some existing studies explore initial opinion modification for opinion maximization, many are tailored to specific scenarios (e.g., leader-driven settings [26]).\n\nThe work of [7] also addresses maximizing overall opinion through initial opinion adjustments but fundamentally relies on matrix inversion techniques. More recently, [27] proposed an approximate solution using forest sampling for this problem, employing matrix inversion as a baseline comparison. In our study, since the model incorporates the additional influence of resistance coefficients, we extend the method from [27] to accommodate our framework (Lines 185–202) and adopt it as a baseline for comparison. Notably, when fixing $\\alpha_i = \\frac{1}{1+d^+_i}$, our model naturally reduces to the formulations in [27] and [7]. Beyond forest sampling, we introduce an alternative approach based on absorbing random walks (Lines 157–184) and provide a comprehensive comparison between these methods.\n\nFor all proposed algorithms, we rigorously analyze their time complexity. Although the bound for Algorithm 3 may appear loose due to necessary proof simplifications, it still guarantees near-linear time complexity. Experimental results demonstrate that our MIS algorithm not only runs substantially faster than competing methods but also achieves superior performance, highlighting its efficiency and effectiveness.\n\n**W2: Sparse Matrix Inversion**\n\nWhile [27] establishes matrix inversion as its baseline and demonstrates significant time efficiency improvements over this baseline, our extended adaptation of the method in [27] (as our baseline) similarly achieves superior performance compared to matrix inversion, which we have empirically verified.\n\nWhen fixing $\\alpha_i = \\frac{1}{1+d^+_i}$, our model naturally reduces to the foundational model in [27]. Given this theoretical equivalence and [27]'s already established performance advantages over matrix inversion, we prioritized comparative analysis against the approach in [27] rather than directly including matrix inversion as an additional baseline.\n\nNevertheless, we acknowledge that practical sparse matrix inversion methods still exhibit suboptimal efficiency. As recommended, we will incorporate matrix inversion as an explicit baseline in the revised version to ensure comprehensive benchmarking. Thank you for your insightful feedback.\n\n**W3: Optimization Problem Clarity**\n\nOur optimization variables are the internal opinions $s_i$ of $k$ selected nodes (modified from their original values to 1), aimed at maximizing the overall equilibrium opinion. In practical applications, initial opinions typically originate from users' expressed opinion or predefined stance labels. Adjusting initial opinions effectively alters these nodes' intrinsic positions—such as converting neutral users into advocates—a common practice in marketing campaigns where persuading key users to shift product perceptions is critical.\n\nRegarding network topology, our rigorous theoretical proofs demonstrate that standard network characteristics (e.g., presence of cycles, directed/undirected edges, connectivity) do not compromise algorithmic correctness. This universality underscores our approach's robustness and scalability across diverse network structures, as empirically validated on real-world networks.\n\nWe acknowledge that the manuscript overly emphasizes theoretical derivations at the expense of applied context. The revision will incorporate necessary practical explanations and case-based evidence to address this gap.\n\n**W4: Experimental Validation**\n\nThe issues you raised are indeed critical, and we will address them through the following improvements:\n\nRegarding the insufficient dataset description, we will provide more comprehensive details about the datasets used. Specifically, the Twitter dataset represents a follower network capturing user follow relationships. In practical applications, initial opinions typically originate from users' expressed opinion or predefined stance labels, while the steady-state opinions reflect the final opinion distribution after social influence propagation. However, due to privacy constraints, publicly available datasets that simultaneously provide both network structures and ground-truth user opinions remain scarce, necessitating our use of generic networks. While our proposed algorithm conceptually applies to other network types (e.g., GPS or road networks), our research focus remains squarely on opinion dynamics within social networks. To strengthen validation, we plan to incorporate additional datasets with explicit opinion dynamics contexts—such as the real-world dataset from [33]—in the revised manuscript for more rigorous evaluation.\n\nThank you again for your insightful suggestion.\n\n**Q1: Writing Quality**\n\nThank you for your careful reading. We will check carefully the whole paper, correcting all grammatical errors and typos.\n\n**Q2: Opinion Dynamics Model**\n\nThis model evolves from the DeGroot and Friedkin-Johnsen frameworks, initially introduced in [3]. With advancements in opinion dynamics research, additional variables—such as stubbornness coefficients and noise terms—have been incorporated to enhance realism. Strictly speaking, given its incorporation of self-reinforcement through initial opinions, this model falls under the Friedkin-Johnsen framework.\n\nWe appreciate your insightful question. The revision will include:\n\n1. Detailed explanations clarifying the model's origin and theoretical classification;\n2. The explicit formulation $\\boldsymbol{z}^{t+1} = \\boldsymbol{R}\\boldsymbol{s} + (\\boldsymbol{I}-\\boldsymbol{R})\\boldsymbol{P}\\boldsymbol{z}^t$ preceding Equation (1) to improve conceptual accessibility.\n\n**Q3: Properties of $f(\\boldsymbol{R},\\boldsymbol{s})$**\n\nAs discussed in Lines 118-128, $f(\\boldsymbol{R},\\boldsymbol{s})$ represents a convex combination of all nodes' initial opinions with explicit non-negativity properties. When $\\boldsymbol{R}$ is fixed, the function exhibits convexity, classifying Problem 1 as a discrete combinatorial optimization problem.\n\n**Q4: Time Complexity Validation**\n\nThe time complexity analysis of MIS involves unavoidable bounding operations during the proof, resulting in a theoretical upper bound. In practical network scenarios, the empirical runtime consistently demonstrates significant improvements over this bound. To quantitatively demonstrate efficiency, we will supplement our analysis by tracking residual update counts, providing concrete metrics that directly reflect the algorithm's real-world efficiency and its alignment with the theoretical scaling with respect to $n$. Thank you again for your insightful suggestions.\n\n**Limitations:**\n\nRegarding limitations, our algorithm demonstrates clear advantages over sampling methods in both efficiency and accuracy, along with superior scalability. However, it is not without limitations. As formally established in Theorem 3, our approach remains influenced by resistance coefficients—particularly exhibiting prolonged runtime when these coefficients are small. Furthermore, in exact optimization scenarios where $k_\\text{gap}=0$ (i.e., boundary nodes contribute equally), the algorithm may fail to terminate gracefully, though such cases are practically negligible. We will address this by proposing relaxed constraints as a mitigation strategy, with limitations and future directions discussed in the concluding section.\n\nAs previously noted, our forest sampling algorithm extends the foundational work of [27]. To strengthen comparative analysis, we will incorporate matrix inversion benchmarks to highlight performance trade-offs.\n\nConcerning potential negative impacts, our method—designed to optimize overall opinions by modifying initial opinions—can yield positive societal benefits or commercial value. Nevertheless, it carries risks of opinion manipulation, including the propagation of harmful content [9]. We will prominently emphasize these dual-use considerations in the revised manuscript. Thank you for your suggestion!"}, {"review_id": "UpZKciDuyH", "reviewer": "Reviewer_TSx5", "summary": "The paper investigates the overall opinion optimization in online social networks by strategically altering the internal opinions of $k$ selected nodes to maximize global consensus. Recognizing the computational intractability of exact methods ($O(n^3)$), the authors explore two sampling-based algorithms and propose a novel asynchronous update algorithm. The goal is to identify a subset of influential nodes whose opinion modification will maximize the collective sentiment across the network. The proposed methods are evaluated on large-scale real-world networks, demonstrating superior performance over existing baselines in terms of effectiveness, efficiency, and scalability.", "questions": "It is not clear why the sampling algorithms are required. I guess that they give fast algorithms for calculating final optimized opinion, but fails to provide the optimal nodes. If finding the optimal nodes fast is the purpose of the paper, why are the sampling algorithms proposed then? What is the role of the algorithms in the bigger picture? It is discussed neither in the intro, nor in the paper.", "limitations": "Also I did not find any detail discussion on the limitations of this approach (the asynchronous update).", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. The paper addresses a problem with significant consequences, that is, optimizing public opinion in the context of online social networks. This problem has many impactful applications like elections, marketing, and health campaigns.\n\n2. Scalability of Proposed Algorithm: The asynchronous update algorithm shows scalability, offering a promising direction for handling massive graphs efficiently with exact results.\n\n3. Sufficient Evaluation: The authors conduct extensive experiments on real-world networks, providing empirical evidence for the advantages of their algorithms over standard baselines.\n\n\nWeaknesses\n\n1. Unclear Role and Justification of Sampling Algorithms: The purpose and necessity of the sampling algorithms are not clearly articulated in the introduction. It's not evident why sampling is needed in addition to or instead of optimization techniques. The paper lacks a discussion on the specific limitations sampling tries to overcome, and how it fits into the broader solution strategy.\n\n2. It is not clearly stated whether an edge from node $i$ to node $j$ implies that $i$ influences $j$ or vice versa. This is a crucial detail in opinion dynamics and should be explicitly defined to avoid confusion about how information flows in the model. Particularly, the equation following line 99, explaining opinion of a node seems unreasonable based on the direction of the edge. \n\n3. Forest Sampling algorithm requires an inverse operation, but the complexity of this computation is not discussed, nor are the limitations or trade-offs. Moreover, the merits of sampling algorithms are not well-articulated, and the paper fails to explain why sampling cannot directly solve the $k$-node selection optimally—this needs clearer theoretical or empirical justification.\n\n4. The paper is too mathematical and lacks intuitive motivations at places. People with insufficient domain knowledge would struggle to read this paper.", "was_revised": true, "final_justification": "I want to retain my score.", "rebuttal": "Thank you for your time and efforts. The following is our response to your concerns.\n\n**W1: Role of Sampling Algorithms**\n\nWe appreciate your insightful question. The sampling algorithms are included to ensure methodological completeness. Specifically:\n\n1. The absorbing random walk-based approach provides a probabilistic interpretation of the problem, while also serving as conceptual inspiration for our deterministic algorithm—Algorithm 1 can indeed be viewed as a deterministic asynchronous push variant of absorbing random walk probabilities.\n2. The forest sampling algorithm, an extension of [27], serves as a baseline since our model reduces to [27]'s formulation when fixing $\\alpha_i = \\frac{1}{1+d^+_i}$. This pre-existing method (developed prior to our MIS proposal) warrants inclusion to acknowledge foundational work.\n\nBy employing both algorithms as baselines, we demonstrate the superior efficiency and accuracy of our deterministic asynchronous approach. We will further clarify their necessity and connections to MIS in the revised manuscript.\n\n**W2: Edge Directionality in Opinion Dynamics**\n\nIn directed graphs, an edge from node $i$ to node $j$ signifies that node $i$ receives influence from node $j$—specifically, node $j$'s expressed opinion impacts node $i$'s expressed opinion. This causal relationship is well-established in directed graph-based opinion dynamics models [7, 27, 33].\n\nTo illustrate this logic: consider social platforms like YouTube where a follower relationship (node $a$ follows node $b$) creates a directed edge $(a,b)$. Here, content (e.g., videos) published by $b$ becomes visible to $a$, demonstrating how $b$'s opinions influence $a$. Consequently, the right-hand side of the equation after Line 99 mathematically captures the aggregated influence of nodes followed by $i$ on $i$'s opinions. This aligns perfectly with the described social mechanism, validating the equation's rationale.\n\nWe appreciate your suggestion and will provide additional clarifications  in the revised manuscript.\n\n**W3: Forest Sampling Algorithm**\n\nWe appreciate your insightful question. The forest sampling algorithm efficiently approximates elements of the fundamental matrix's inverse, streamlining our solution process. However, it's important to clarify that the algorithm itself doesn't involve explicit matrix inversion operations. Regarding the matrix $\\boldsymbol{Q} = \\boldsymbol{D}(\\boldsymbol{I}-\\boldsymbol{R})^{-1}\\boldsymbol{R}$ in Line 188: while its formulation appears to require matrix inversion, the special structure of the resistance matrix $\\boldsymbol{R}$ (defined as a diagonal matrix in Line 102) renders $(\\boldsymbol{I}-\\boldsymbol{R})^{-1}$ computationally tractable without complex inversion procedures.\n\nHistorically, before our deterministic asynchronous MIS algorithm, sampling methods provided practical advantages by mitigating time/space costs associated with high-complexity matrix inversions. Yet, as evidenced by Lemma 2, sampling only guarantees probabilistic error bounds (with probabilities <1), preventing exact problem-solving as formalized in Corollary 1. In contrast, our MIS algorithm—supported by Lemmas 5 and 7—provides exact error guarantees (probability=1), enabling optimal $k$-node selection as demonstrated in Section 6.\n\nWe hope this addresses your concerns. Detailed explanations will be incorporated  in the revised manuscript.\n\n**W4: Readability & Intuition**\n\nWe sincerely appreciate your valuable feedback. We regret that the extensive mathematical proofs may have compromised the paper's readability, despite their necessity for theoretical rigor. In the revised version, we will incorporate more intuitive explanations to enhance accessibility while maintaining mathematical precision. Thank you again for your constructive comments and for highlighting this important aspect of presentation.\n\n**Q1: Role of Sampling Algorithms**\n\nWe sincerely appreciate your question. As you rightly pointed out, sampling algorithms identify approximate optimal sets for optimizing the overall equilibrium opinion, but their inherent stochastic nature precludes deterministic guarantees on the optimal node set. As previously noted, sampling methods typically offer more intuitive interpretations of the underlying mechanisms.\n\nIn our work, the random-walk-based sampling algorithm served as conceptual inspiration for developing our asynchronous update framework. Regarding the forest sampling algorithm: since [27] originally proposed this method for a simplified model, and our model reduces to theirs under specific conditions (as demonstrated in our theoretical analysis), we extended their approach to our framework out of respect for prior work. This extension—coupled with its role as a baseline—enables direct comparison, further highlighting the efficiency and accuracy of our proposed asynchronous algorithm.\n\nWe deeply value your attention to this issue and will meticulously revise the manuscript to strengthen the justification for sampling algorithms' inclusion, improve narrative coherence between methods, and enhance overall readability. Thank you again for your constructive feedback.\n\n**Limitations:**\n\nOur algorithm demonstrates clear advantages over sampling methods in both efficiency and accuracy, along with superior scalability. However, it is not without limitations. As formally established in Theorem 3, our approach remains sensitive to resistance coefficients—particularly exhibiting prolonged runtime when these coefficients are small. Furthermore, in exact optimization scenarios where $k_\\text{gap}=0$ (i.e., boundary nodes contribute equally), the algorithm may fail to terminate gracefully, though such cases are practically negligible. To address this edge case, we propose mitigating the issue by relaxing constraint conditions. A dedicated discussion of limitations and future directions will be incorporated in the revised manuscript. Thank you again for your insightful suggestions."}, {"review_id": "TasZXaGW2h", "reviewer": "Reviewer_2WFV", "summary": "The paper deals with the problem of strategically governing the public opinion formation process in a social network in order to maximize the overall (average) opinion expressed by the agents. This is a fundamental problem in the opinion dynamics literature, and it has extensively studied under the lens of both social science and computer science lens.\nIn the literature several methods have been proposed to influence the opinion formation process, depending on the adopted opinion dynamics model. In this paper, a variation of the Friedkin-Jonsen opinion dynamics model is adopted, where each agent has a (fixed) internal opinion and an (variable) expressed opinion and at each step they decide to express an opinion that depends on their own internal opinion and the opinions expressed by their neighbors in the previous step. The technique used to influence the public opinion is to change the internal opinions of a selected set of nodes. \n\nThe paper addresses the optimization problem of determining a set of k nodes and have their internal opinions modified in order to maximize the overall opinion expressed at the equilibrium of the opinion dynamics. The paper focus is on the computational complexity and some efficient algorithms are proposed. The main result of the paper is a deterministic asynchronous algorithm that exactly identifies the optimal set of nodes through asynchronous update operations and progressive refinement, ensuring both efficiency and precision. \n\nAn extensive set of experiments on real-world datasets are presented to validate the efficiency of the proposed algorithms with respect to baseline approaches and show their scalability even on  \nnetworks with tens of millions of nodes.", "questions": "1.\tLines 80-81 and line 99: usually in opinion dynamics models such as DeGroot and FJ the graph is weighted, where weights represent the strength of the influence of an agent on a neighbour. Why do you adopt a non-weighted scenario? What does represent an edge in you model? Can your results hold even in the weighted case?\n2.\tLines 119-120: What is the meaning of M(u, v)? Is the influence of v on the expressed opinion of u?\n3.\tLine 138: As a matter of fact your optimization problem is to select a set T of k nodes that maximized the increment in the overall opinion. Thus, f_U(R, s) = f(R, s) + \\sum_{u\\in U} \\Delta(u) and you are looking for \\arg\\max_U f_U(R, s). \n\nOther comments/suggestions:\n\n1.\tLines 19-21, some references could be useful to support your statement of the importance of the overall opinion metric.\n2.\tLines 80-86: even if you do not specify if the graph is directed or undirected all your definitions are given for directed graphs (you are distinguishing between in-degree and out-degree). It could be better specify that definitions are given for directed graphs and can be easily extended to the undirected case.\n3.\tLine 113: I suggest to write f(R, s) = \\sum_v s_v \\sum_u M(u, v). Moreover, I would maintain for all the paper the notation of using u, v to denote nodes and use i only as index. You should also maintain the same notation for all the appendices.\n4.\tLine 163: a definition of the absorption probability vector of absorbing random walks starting at node i ∈ V could be useful.\n5.\tLine 190: as for the previous comment, a definition of a spanning converging forest could be helpful.\n6.\tLine 235: I guess something is missing in this sentence.\n7.\tLine 240: Lemma 8 is stated only in the following.\n8.\tLine 323: A more informative caption for figure 1 could be helpful.", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "STRENGHTS\nThe paper studies an important problem in the opinion dynamics literature, with significant practical applications. The argument is relevant and perfectly fits the scopus of the conference. \nThis is a theoretical solid paper, with interesting and original contributions. The paper also presents an extensive experimental analysis to validate efficiency, precision and scalability of the proposed algorithms on real-world datasets.\nThe organization of the paper is good and the presentation is sufficiently clear. \n\nWEAKNESSES\nA more careful reading of the paper would be necessary to fix several typos and solve inconsistencies in the notation, in particular between the main text and eppendices. \nAppendices A and B are a simple list of proofs of lemmas and theorems. Some comments could be helpful for the reader.", "was_revised": true, "final_justification": "I read other reviews and authors' rebuttal. I agree with issues related to connections of the paper to the existing literature but I think that authors answered satisfactorily and the final version of the paper could fix all these points.\nI confirm my positive feeling on the paper.", "rebuttal": "We sincerely appreciate your insightful feedback and the constructive suggestions provided.\n\n**W1: Writing Quality**\n\nWe have carefully reviewed your comments and will meticulously implement the necessary revisions in the final submission to address all identified issues. Thank you.\n\n**Q1: Weighted Graph Adaptation**\n\nIn our model, edges represent the direct connection strength between nodes. We focus on unweighted scenarios primarily because forest sampling algorithms face significant challenges in obtaining uniform samples from weighted graphs—this stems from the fact that forest weights are inherently tied to edge weights. To our knowledge, existing literature on forest sampling exclusively addresses unweighted graphs. Fortunately, our algorithm and its theoretical proofs can be seamlessly extended to weighted graphs, although no established baseline methods currently exist for weighted scenarios. For the sake of coherence and conciseness, we restrict our analysis to unweighted graphs in the main text.\n\nRegarding weighted graphs, let the edge weight from node $i$ to node $j$ be denoted as $w(i,j)$, and the out-degree of node $i$ be \n$d_i^+ = \\sum_{ j \\in N_{out}(i) } w(i,j)$. To adapt MIS for weighted graphs, the following modifications are required:\n\n- **Algorithm 1**: Replace the coefficient of $\\boldsymbol{r}_a(v)$ in Line 5 from $\\frac{1-\\alpha_v}{d^+_v}$ to $\\frac{(1-\\alpha_v)w(v,u)}{d^+_v}$.\n- **Algorithm 2**: Replace the coefficient of $\\boldsymbol{r}_s(v)$ in Line 5 from $\\frac{1-\\alpha_u}{d^+_u}$ to $\\frac{(1-\\alpha_u)w(u,v)}{d^+_u}$.\n- **Algorithm 3**: No modifications needed.\n\nAll theoretical proofs for MIS remain structurally identical to those in the unweighted case, requiring only straightforward extensions to account for edge weights. We sincerely appreciate your suggestion. In the final version, we will further elaborate on the advantages of our algorithm in handling weighted graphs, along with additional experiments to verify its correctness and effectiveness.\n\n**Q2: M(u,v) Interpretation**\n\nFor the equation $\\boldsymbol{z}(u) = \\sum_{v \\in V} \\boldsymbol{M}(u,v) \\boldsymbol{s}(v)$, since each term $\\boldsymbol{M}(u,v)$ is non-negative and satisfies $\\sum_{v\\in V}\\boldsymbol{M}(u,v) = 1$, the $u$-th row of matrix $\\boldsymbol{M}$ represents a convex combination of the elements in vector $\\boldsymbol{s}$ that determine $\\boldsymbol{z}(u)$. $\\boldsymbol{M}(u,v)$ quantifies the influence weight of node $v$'s internal opinion on node $u$'s expressed opinion. Specifically, for two nodes with identical initial opinions, a larger $\\boldsymbol{M}(u,v)$ value indicates a stronger influence of node $v$'s opinion on node $u$'s expressed opinion. We appreciate your question and will provide a more detailed explanation of this quantity in the revised manuscript.\n\n**Q3: Optimization Problem Restatement**\n\nYou are absolutely right. We will provide a detailed explanation of this issue in the revised version. Thank you very much for your insightful feedback!"}]

Author rebuttal:

Meta-review: The paper focus on maximizing opinions of users by leveraging Degroot model and linear dynamical system and designing a control system on top of it. They provide asynchronous update, which mimics reality and evaluate their method against several baselines, which shows that their method performs better.

The reviewers are generally positive about the paper. However, reviewer dkDz pointed out some related work and commented on novelty. I think the problem is not novel, however, their approach is novel and clearly placed in the paper. I recommend acceptance.
Decision: Accept (poster)