Scalable Fair Influence Maximization
Authors: Xiaobin Rui
Zhixiao Wang
Jiayu Zhao
Lichao Sun
Wei Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: influence maximization
approximation algorithm
social fairness
TL;DR: Proposing a scalable fair influence maximization algorithm with a theoretical guarantee based on reverse sampling and an unbiased estimator.

Abstract: Given a graph $G$, a community structure $\mathcal{C}$, and a budget $k$, the fair influence maximization problem aims to select a seed set $S$ ($|S|\leq k$) that maximizes the influence spread while narrowing the influence gap between different communities. While various fairness notions exist, the welfare fairness notion, which balances fairness level and influence spread, has shown promising effectiveness. However, the lack of efficient algorithms for optimizing the welfare fairness objective function restricts its application to small-scale networks with only a few hundred nodes. In this paper, we adopt the objective function of welfare fairness to maximize the exponentially weighted summation over the influenced fraction of all communities. We first introduce an unbiased estimator for the fractional power of the arithmetic mean. Then, by adapting the reverse influence sampling (RIS) approach, we convert the optimization problem to a weighted maximum coverage problem. We also analyze the number of reverse reachable sets needed to approximate the fair influence at a high probability. Further, we present an efficient algorithm that guarantees $1-1/e - \varepsilon$ approximation.

Scalable Fair Influence Maximization
Xiaobin Rui
Zhixiao Wang"
China University Mining and Technology Xuzhou, Jiangsu, China ruixiaobine cunt www.t.eduuc....... edu.cn
China University of Mining and Technology Xuzhou, Jiangsu, China zhxwange cumt.
edu.cn www..edu.cc.....mmmmmmmo
Jiayu Zhao
Lichao Sun Lehigh University Bethlehem, PA, USA 1 1is2218lehige edu
China University of Mining and Technology Xuzhou, Jiangsu, China Chaojy@cunde edu.
Wei Chen" Microsoft Research Asia Beijing, China,
weic@microsoft.com
Abstract
Given a graph G, community structure C, and budget k. the fair influence maxi- mization problem aims to select seed set S ([S) S k) that maximizes the influence spread while narrowing the influence gap between different communities. While various fairness notions exist, the welfare faimess notion, which balances fairesss level and influence spread, has shown promising effectiveness. However, the lack efficient algorithms for optimizing the welfare faimess objective function restricts its application to small-scale networks with only a few hundred nodes. In this paper, adopt the objective function of welfare fairness to maximize the exponentially weighted summation over the influenced fraction introduce unbiased estimator for the fractional power of the arithmetic mean. Then, by adapting the reverse influence sampling (RIS) approach, we convert the optimization problem weighted maximum coverage problem. We also analyze the number of reverse reachable sets needed to approximate the fair influence a high probability. Further, we present an efficient algorithm that guarantees 1 - 1/e - e approximation.
communities. We first
Introduction
Influence maximization (IM) is a well-studied problem in the field of social network analysis. Given graph G' and positive integer k, the problem asks to find node set S (1S) k) which can spread certain information to trigger the largest expected number of remaining nodes. There have been various IM variants, such adaptive influence maximization [I], multi-round influence maximization (2]. competitive influence maximization [3), and time-critical influence maximization [4]. Influence maximization and these variants have important applications in viral marketing, rumor control, health interventions, etc S
Considering the situation that when disseminating public health interventions, for example, sui- cide/HIV prevention [6] or community preparedness against natural disasters, we can select individu- als who act as peer-leaders to spread such information to maximize the outreach following influence
Cooresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

maximization. However, it may lead to discriminatory solutions as individuals from racial minorities or LGBTQ communities may be disproportionately excluded from the benefits of the intervention 77. Therefore, derived from such significant social scenarios, fairness in influence maximization has become a focus of attention for many researchers
10
Generally, fair influence maximization aims to improve the influenced fraction inside some commu- nities where the coverage may get unfairly low. Currently a universally accepted definition of fair influence maximization remains elusive, and recent work has incorporated fairness into influence maximization by proposing various notions of faimess, such as maximin fairness [ diversity con- straints [8), demographic parity [II), and welfare faimess [7]. Among these notions, welfare faimess show several attractive features. Its objective function is the weighted sum (with community size as the weight) of the fractional power (a fraction) of the expected proportion of activated nodes within exponent every community. The fractional exponent a is the inequality aversion parameter, allowing one to
balance between fairnss and influence spread, with tending to for influence spread and a tending to O for fairness. The objective function enjoys both monotonicity and submodularity, enabling a greedy approach with 1 - 1/e- E approximation.
However, even though Rahmattalabi et al. (9] has given full analysis of welfare fairness, there is currently no efficient algorithm to optimize its objective function with provable guarantee, which restricts their applications to small-scale networks with only few hundred nodes. In this paper, we propose an efficient algorithm for maximizing the welfare fairesss based on reverse influence sampling (RIS)
The main challenges adapting the RIS approach to the welfare fairness objective include: (a) how to carry out the unbiased estimation of the fractional power of the expected proportion of activated nodes in each community, since simply obtaining an unbiased estimate of the expected proportion and then taking its fractional power is not an unbiased estimator: (b) how to integrate the unbiased estimation designed into the RIS framework. We address both challenges and propose a new scalable fair influence maximization with theoretical guarantees.
Our contributions can be summarized as follows:
We propose an unbiased estimator for the fractional power of the arithmetic mean by leveraging Taylor expansion techniques. The estimator enables us to accurately estimate the fair influence under welfare fairness.
Based on the above unbiased estimator, we adapt the RIS approach to approximate the fair influence with Reverse Reachable (RR) sets and propose the FIMM algorithm that works efficiently while guaranteeing the (1 1/e- - approxxmmmtaoonn solution. Our theoretical analysis needs to address the concentration of the unbiased estimator of the fractional power and thus is much more involved than the standard RIS analysis.
We carry out detailed experimental analysis on five real social networks to study the trade-off between fairness and total influence spread. We test different fairness parameters, influence probabilities, seed budget, and community structures to confirm the performance of our proposed algorithms.
Related Work Influence maximization (IM) is first studied as an algorithmic problem by Domingos and Richardson [5] 16). Kempe al. [17 mathematically formulate IM as a discrete optimization
problem and prove is hardard. They also provide a greedy algorithm with - 11/e approximation based on the submodularity and monotonicity of the problem. Hence, many works have been proposed
to improve the efficiency and scalability of influence maximization algorithms [8 19 20 21 22
12 13 [4] Among these methods, the most recent and the state of the art is the reverse influence sampling (RIS) approach 112 13 14 233,, where the IMM algorithm [14] is one of the representative algorithms. The idea of RIS approaches is to generate an adequate number of reverse reachable sets (a.k.a. RR sets), and then the influence spread can be approximated at high probability based on these RR sets Therefore, the greedy approach can be easily applied by iteratively selecting the node that could bring the maximal marginal gain in terms of influence spread as seed node.
Recent work has incorporated faimess directly into the influence maximization framework by relying on Rawlsian theory (9) game theoretic principles [8) and equity-based notion (24). Based on the Rawlsian theory, maximin fairness g g aims to maximize the influence fraction of the worst-off community. Inspired by the game theoretic notion of core, diversity constraints g require that every community obtains an influenced fraction higher than when it receives resources proportional to its size and allocates them internally. Equity- based notion 24 strives for equal influenced fraction

---

across all communities. However, these notions can hardly balance faimess and total influence and usually lead to a high influence reduction. Especially, strict equity [24 is rather hard to achieve in influence maximization. To address these shortcomings, Rahmattalabi et al. 7 propose the welfare fairness that can control the trade-off between fairness and total influence by an inequality aversion parameter. Based on the cardinal welfare theory (25], the objective function of welfare fairness is to maximize the weighted summation over the exponential influenced fraction of all communities. Fish et al. [26) also follow welfare functions and propose d-mean fairness, where the objective function becomes MMF when Φ = -00. However, they do not address the challenge of unbiased estimation of the fractional power. In addition, none of the above studies address the scalability of the algorithms. Thus, to the best of our knowledge, we are the first to study scalability in the context of fair influence maximization.
2 Model and Problem Definition
Information Diffusion Model In this paper, we adopt the well-studied Independent Cascade (IC) model as the basic information diffusion model. Under IC model, a social network is modeled as a directed influence graph G = E.),, where V is the set of vertices (nodes) and E' [ V x V is the set of directed edges that connect pairs of nodes. For an edge (vi, vU) E, p(e, 0ÿ) indicates the probability that i; influences ,, The diffusion of information or influence proceeds in discrete time steps. At time t = 0, the seed set S is selected to be active, denoted as Ag. At each time t 2 1, all nodes in A, try to influence their inactive neighbors following influence probability p. The set of activated nodes at step L is denoted as A, The diffusion process ends when there a time step. An important metric in influence maximization is the
no more node activated influence spread, denoted as or (S), which is defined as the expected number of active nodes when the propagation from the given seed set S ends. For the IC model, (SS) = Bl U A U A2 U... I]. We use ap(v, .S to represent the probability that node is activated given the seed set S. Then we have (S)) = -.ev ap(u,S). S).
Live-edge Graph Given the influence probability p. we can construct the live-edge graph L (V, E(L)), where each edge (v,, 0ÿ) is selected independently to be a live edge with the probability p(us, vy). The influence diffusion in the IC model is equivalent to the deterministic propagation via bread-first traversal in a random live-edge graph L. Let S) denote the set of nodes in graph G that can be reached from the node set S. By the above live-edge graph model, we have (SS) E, [I,,, E, Pr[L S)), where the expectation is taken over the distribution of live-edge graphs, and Pr[L[G] is the probability of sampling a live-edge graph in graph G.
Approximation Solution A set function f V + R is called submodular if for all S C T S V and u E V, C.Y.TfCC f(S {u))- 2 F(TU(u)) - -(T). Intuitively, submodularity characterizes the diminishing return property often occurring in economics and operation research. Moreover, set function f is called monotone if for all S C T C V. ((S) s spread (-) for the independent cascade model a monotone submodular function. A non negnnegtt monotone submodular function allows a greedy solution to its maximization problem with 1 - 1/c approximation 27 which provides the technical foundation for most influence maximization tasks.
f(T).
is shown in [17] that influence
Fair Inffuence Maximization For given graph G with ng nodes, the classic influence maximiza- tion problem is to choose a seed set S consisting of at most k seeds to maximize the influence spread (S, G). Assuming each node belongs to one of the disjoint communities E C= (1, ... 2,...... C), such that V U Vi2 U... U Vc = V where V. (n. = IVr)) denotes the set of nodes that belongs to community c. Generally, fair influence maxinization (FIM) aims to narrow the influence gap between different communities while maintaining the total influence spread as much as possible. In this paper, we adopt the fair notion proposed by Rahmattalabi et al. (7), where the welfare function is used to aggregate the cardinal utilities of different communities. The goal is to select at most k seed nodes, such that the objective function (S) (also referred to as fair influence in this paper) is maximized, where F, (S) = Σ Enge ne u.) 0 < a < 1. The utility (S) denotes the expected proportion of influenced nodes in the community e with the seed set S. Exponent a is the inequality aversion parameter that controls the trade-off between fairness and total influence, with a tending to 1 for influence spread and a tending to O for fairness. We thus define the fair influence maximization problem in this paper as follows:
3

---

The Fair Infiuence Maximization (FIM) under the independent cascade model is the optimization task where the imput includes the directed inftuence graph G (V, E, p). the non- overlapping community structure C, and the budget k. The goal is to find a seed set S to maximize the fair influence, i.e., S* argmaxs:|s155 (S)..
Definition 1.
According to 77.. the fair influence (S) is both monotone and submodular, which provides the theoretical basis for our efficient algorithm design, to be presented in the next section.
3 Method
The monotonicity and submodularity of the fair influence objective function enable a greedy approach for the maximization task. However, as commonly reported in influence maximization studies, naively implementing a greedy approach directly on the objective function will suffer a long running time. The reason that accurate function evaluation requires a large number of Monte-Carlo simulations. In this section, we aim to significantly speed the greedy approach by adapting the reverse influence sampling (RIS) 12 13 [4), which provides both theoretical guarantee and high efficiency, We propose the FIMM algorithm that is efficient when the number of communities is small, which is hopefully common situation such as gender and ethnicity.
For the convenience reading, we list most important symbols featured in this paper in Table !
Table I: Important symbols appeared in this paper.
Symbol
Explanation
G (V, P.p)
A network;
V
Node set of the network;
E
Edge set of the network;
The number of nodes in G. i.c. ng [V];
p(u;, Ug)
The probability that v; influence dy;
C= (21,0,,111
Community structure;
C
The number of communities in C;
Ve
The node set in community c;
ne
The number nodes in community e, i.e. ni, = Val: A seed set;
s
S*
The optimal seed set for fair influence maximization; The expected probability that v is activated by S;
ap(v,
(SS)
Influence spread of S, i.c. (S)) = Evev ap(u, S);
ue
The utility of (expected fraction of influenced nodes in c);
(S))
The fair influence of 5; A set of RR sets;
R
R.
The set of RR sets rooted in community G;
(S, R)
The unbiased estimator for fair influence of S based on R;
The total number of RR sets;
0-
The number of RR sets rooted in community
The aversion parameter regarding fairness;
Q
The approximation parameter for Taylor expansion;
8
The accuracy parameter;
L
The confidence parameter.
3.1 Unbiased Fair Influence
To estimate the influence spread, we may generate a number of live-edge graphs L (2,,L2, L.} as samples. Then, for a given seed set S, o(C, = I is an unbiased estimator of (S)) However, situations are completely different for fair influence. For each e community its fair influence is actually n. u. If we still generate a number of live-edge graphs and
estimate by (C. 5) = E [[,,, 8) n Val/ then ue but á,, 5) actually biased estimator of u for < a < 1. In fact, the value of u generally higher than the true value, which is revealed by Jensen's 's Inequality.
is an unbiased estimator for

---

Fact 1. (Jensen's 's Inequality) If X is random variable and ó is concave function, then [[o(X)] S ((E[)))
Therefore, our first challenge dealing with the welfare fairness objective provide an unbiased estimator for the fractional power value of ug. We meet this challenge by incorporating Taylor expansion in Lemma
Lemma 1. For a given seed set S and an inequality aversion parameter a, the fair influence
(S) = [ ne 1- an(n,a) (1-((()))))))
uc(s))))
.n(n, a)
1.
1,
(1-aX2-a))
n 2
m1
Proof. By Taylor expansion of binomial series, we have
a(a 1)...(a
(1 + x) = 1+ Σ x"
n!!
By definition of fair influence in Definition
we have
Fa(S) = Σ ne(1 + (uc(S) 1))
Σ
14
Σ
a (uc(S) -1) -1)"
LEC
EEC
n=l
Σ The
1 a
an, -uc(s)))
(I)
where
n1 = 1,
7(n a)
(1-a)(2-a)...n--1
2 2.
Thus concludes the proof.
Lemma] TemmaaTdemooee demonstrates that the calculation of fair influence with fractional powers can be transformed into the summation of integral powers. Further, can get unbiased estimator for integral powers of arithmetic mean as given in Lemma] 2
Lemma 2. (28) Suppose that a simple random sample of size m is to be drawn, with replacement, in order to estimate p². An unbiased estimator for μr' (n S m.) is
mm - n)) [ Zi, ... 2t, His + i2 ......
p
(2)
m!
where the summation extends over all permutations of all sets of n observations in sample subject only to the restriction noted.
3.2 Unbiased Fair Influence with RR sets
Many efficient influence maximization algorithms such as IMM 14] are based on the RIS approach, which generates a suitable number of reverse-reachable (RR) sets for influence estimation.
RR set An RR set RR(v) (rooted at node E V) can be generated by reversely simulating the influence diffusion process starting from the root v, and then adding nodes reached by reversed simulation into this RR set. In this way, RR(v) ()) is equivalent to collecting all nodes that can reach in the random live-edge graph L, denoted by [LL,, v). Intuitively, each node u E RR(v) if selected seed would activate in this random diffusion instance. We say that S covers RR set RR(()) if S RR()) + Ø. The expected activated probability ap(u, 5) is thus equivalent to the probability that S covers randomly generated u-rooted RR set. In the following, randomly generated RR set when v not specified, i.e., RR(v) = T(murP)) (L, v) where P, the space of all live-edge graphs and (d(-) denotes the uniform distribution.
RR(v) to represent
5

---

Let X. be the random event that indicates whether randomly selected node in community e would be influenced in a diffusion instance by the given seed S. As mentioned above, RR set maps to random diffusion instance. Assuming we generate R. consisting of 0 RR sets in total and each community e gets 0g RR sets. Let Re be the set of RR sets that are rooted the community c, then [R = 0e. Let X (i E [0.] be random variable for each RR set R E Re such that X if R. NS & Ø, and X 0 otherwise. Then, we have B[X.]
and [[X,] 1 Uc
Based Lemma
and Lemma 2 can get the unbiased estimator of [ through RR sets
E E 1
= 1 (n, 1EL1--E[XA -1- E(X.))"
1 7(n, a) (0c - n)!
Σ X X X."
(3)
Og!
n=1
Further, we can get the unbiased estimator of the fair influence Fa
(0. n)!
Fa(S,
Σ The
(n, a)
X
X
X!r
0g!
= Σ The
1 a
(n, 0
Tc
0e
CEC
n=1
<=0
where ne = =0 -a-- -EE X and
n1 = 1
(n, a)
(1
(1 -a) a) (n
n 2 2.
m1
In the following, we consider Eq. 4 as our objective function to deal with the fair IM problem.
3.3 FIMM
For a given seed set S, let sp[c] denote the number of all u-rooted (u E V.) RR sets covered by S, and k[u][c] denote the number of all u-rooted (u Vo) RR sets that covered by (u E V ()) but not by S, then the marginal fair influence gain of v is
0g k[v][c] - p/c -
Pa(u|S)= = Σ CEC
1 -
mn,
0.
n=l
1=0
11-1
0- plc -
Σ ne
1
7(n,0 ④
0.
REC
t=0
0.
old
0.
16
Kcu] - spc] -
Σ am cEC
nnn a)
(5)
1=0 0-
i
Therefore, when generating RR sets, we have to count k|j][c] which indicates the community-wise coverage for and record r/[e] which indicates the linked-list from all its covered RR sets, as shown in Algorithm [ As shown in lines 6~99, when generating random w-rooted RR set RR(v), we count all nodes u E RR)() and raise all k| k(u[[c(v)) by 1, where c(v) indicates e's community label. It should be noted that modifying si xi[u] [c(w]] can be accomplished simultaneously when generating RR(x) by reverse influence sampling.
Based on the RR sets generated by Algorithm 1 we present our FIMM algorithm (Algorithm) 2 select k seed nodes that maximize Fq. througgh greedy approach, ie., iteratively selecting node with the maximum alternative marginal fair influence gain as presented in Eq. 5 Apparently, it costs O(C') to calculate F S) for any v where C' is the number of communities. When C is small (i.e., constant), it would be efficient to compute F()SS) for all v e V in OCCng). Besides, since

---

Algorithm 1: RR-Generate: Generate RR sets
Input: Graph G (V, E, p), community C, budget k. number of RR sets for each community 0- Output: RR sets R. community coverage linked-list from nodes to covered RR sets Initialize x|v][c
for all E V, c C; Initialize 7|v] = E for all u E V;
3 R = Ø
for C do
for i to f do
Select random node in community c Sample random RR set R RR(0); for E R do
x|u][c[D]] = k[ul[c(u)] +1;
10
R = R U [R]:
7/0] 7|0| (R)
(S, R) is submodular and monotone, we can adopt a lazy-update strategy [8] that selects e with the maximal Fa (w([S) as a seed node Fa (v)S) is still the maximum after updating. This lazy-update strategy (lines 10~12) can down great amount of redundant time cost that be empirically up to 700 times faster than a simple greedy algorithm [8]]
There two vital counting arrays in Algorithm i.e., sp[c] and <lu][c]. spc] records and updates the number of RR sets covered by S in community wise. By lines 20-24,, x[v][c] keeps updating and always indicates the extra coverage of v on all u-rooted (u Vo) RR sets besides S. It establishes
-wise..
Algorithm 2: FIMM: Fair Influence Maximization
Input: Graph G EV, community C, budget approximation parameter Q Output: Seed set $
(R, K, 7)) AR-Generate(GG,C k, 0,)
Initialize p/c] = 0 for all e C; //indicating the number of covered RR sets rooted in
Initialize 7(v) according to 55 for all v V; //indicating initial marginal gain
Initialize covered R = false for all R R; //indicating whether R is covered
Initialize updated [v] Irue for all u E V: //indicatinng whether x(v] is updated
S 2;
for
do while true do
v = arg max y(u);
10
updaled((v) = false then
11
Updating ((v) according to ():
12
updated(()) = true;
else 13
14
S Su for V E V do
15
16
updated(v) = false;
17
break;
18
for e E do
19
L slc sp[c] + <[ui[c]:
for all R E n/fu A covered[R = false do
21
covered R = true;
r rool RR):
23
for all u E R A u # v do =[u][c(r)] xlu][c(r)] 1;

---

convenient way for updating plc) that only needs to increase xp(c) by x|u][c] where v is the newly selected node for all c C. we denote the original community-wise coverage as k', which means (me, Ki,, ~ -RR-Generate C, k; 0s), then it holds x' [v][[c] x[v][c] + s/c] for all E V and e E in Algorithm
3.4 Number of RR sets
In this subsection, we discuss the number of RR sets needed to approximate the fair influence with high probability. Let OPTr denote the optimal solution and S* denote the corresponding optimal seed set for the fair influence maximization problem defined in this paper, ie., OPT, (S() Lege (0 = Eeee ne (1 a Ex=1 (1 uz u=(S)))") Since this paper deals with the fair influence maximization problem, we thus assume that the maximal community utility mat u 2 maxeecue(S") of an arbitrary seed set 5# would not be too big.
Lemma Let 81 E (0,1), E1 E (0, 1), and 01 120² In(C/á1) where Q is the approximation =f(1-b]
parameter, b max(u, Ve E C, and S argmaxs;(s|s FS( denotes the optimal
solution for the FIM problem based on R, then Fa 2 (1- OPTP holds at least 1 - ò1 probability 0 2 CO
Lemma 4. Let 82 E 1). E2 = (6-))- and 02 xQ (oll)((("])bbb) where Q is the approxima- c)(1bbu)
tion parameter. by mar u. mar (S*)))) Vc where S could be an arbitrary solution. For each
bad S (which indicates (S) < (1 1/e-a) =) OPPP, Fa(S, RS 2 (1 (1--1/10 1/e)( - =1) -PTP
holds most 52/ ("x) probability if C#2.
Please refer to Appendix for the detailed proof of Lemma and Lemma
Theorem 1. For every 0, l 0, 0 < and Q 2, by setting dn 82 1/2nfa and 2 C max(01, 02), the output S of FIMM satisfies Fa (5) 2 (1 - 1/e - E) Fa(""), where S denotes the optimal solution with probability at least 1 - 1/ml
Proof. Combining Lemma and Lemma we have F. (5, R) 2 (1- 1/e OPTF at least 1 1- 81 - 52 probability based on the union bound. If we set d1 = 52 = 1/2n'g, then, following the standard analysis of IMM, our FIMM algorithm provides (1 1/e a)aaproxiimation with probability at least 1 - 1/ng-
If we set 61 = 82 2ng
and E =
where T1 = VIn lnng + In and
6-1
V3n1 2
T2 = r + (*xe then possible setting of 0 could be 0 = (5=1)2. c2(1
v
4
Experiments
4.1
Dataset
generated using email data from a large European research institution, where every node is member of the research institution and an directed edge (v, u) indicates that u has sent least one email. contains 1,005 nodes and 25,571 directed edges. Moreover, this dataset also contains "groonn--rutth" community memberships of nodes, where each member belongs to exactly one of departments at the research institute.
Email The Email dataset 29
Flixster The Flixster dataset (30 is a network of American social movie discovery services. To transform the dataset into weighted graph, each user is represented by node, and a directed edge from node u to is formed if u rates one movie shortly after u does so on the same movie. It contains 29,357 nodes and 212,614 directed edges. also provides the learned influence probability between each node pair, which can be incorporated into the IC model. Since it has no community information, we construct the biased community structure by categorizing individuals according to their susceptibility of being influenced to highlight the level of inequality and get 100 communities. Moreover, this dataset contains the learned influence probability between each node pair, which can be incorporated into the IC model.
8

---

Amazon The Amazon dataset [31] is collected based on Customers Who Bought This Item Also Bought feature of the Amazon website. If product i frequently co-purchased with product the graph contains an undirected edge between i to j. The dataset also provides the ground-truth community structure which indicates the product categories. 'he original network has 334,863 nodes and 925,872 undirected edges. After Pruning low-quality communities (whose size is no more than 10 nodes), the Amazon network tested in our experiments 12,698 nodes, 40,096 edges, and 509 communities.
network the video-sharing web site that includes social relationships. Users form friendship each other and users can create groups which other users can join. The friendship between users regarded as undirected edges and the user-defined groups are considered ground-truth communities. The original network has 1,134,890 nodes and 2.987.61 ,,624 undirected edges. After screening high-quality communities, it remains 30,696 nodes, 198,867 edges, and 1,157 communities.
Youtube The Youtube dataset 31
DBLP The DBLP dataset 31 is the co-authorship network where two authors are connected they ever published paper together. Publication venues, such journals conferences, defines an individual ground-truth community and authors who published to a certain journal or conference form a community. The original network has 717,080 nodes and 1.049,866 866 undirected edges. We also perform the network pruning and finally obtain 72,875 nodes, 268,346 edges, and 1,352 communities.
4.2 Eyaluation
Let S₁ denote the seed set returned by IMM 14, Sp denote the seed set returned by FIMM, the performance S towards fairness can be evaluated via the Price of Fairness (PoF) and the Effect of Fairness (EoF)
PoF = (S o(5)) EoF = (F((Sp) (s o(S)) k
Fa (S1) -
where |s, [Spl k, (-) denotes the influence spread and (- denotes the fair influence.
Intuitively, PoF implies how much price cost to access fairness and EoF implies to what extent
steps towards fairness.
4.3 Results
We test IMM and our proposed FIMM algorithm in the experiment. In all tests, we run 10,000 Monte-Carlo simulations evaluate both the influence spread and the fair influence under IC model. We also test influence probability p, inequality aversion parameter a and the seed budget
4.3.1 Email & Flixster
For the Email network, we set 0.5. Since the network is small, we apply the Uniformed IC model where the influence probability is the same across all edges. test different probabilities that range
60
80
50
- PoF
- PoF
FoF
- FoF
40
38. 30
8 40
20
20
10
0
0
0.001
0.003
(LOUS
0.007
01009
0.1
0.2
01.
0.4
0.5
066
(1.
08
2
(a) Email
(b) Flixster
Figure 1: Results of testing influence probability Email and aversion parameter a on Flixster.

---

from 0.001 to 0.01 with the step of 0.001. For the Flixster network, we test the inequality aversion parameter a which ranges from 0.1 0.9 with the step of 0.1. We set l 50 for both networks and the results are shown in Figure [
As the influence probability p increases, both PoF and EoF show downward trend. This may be attributed to the increased challenges faced by disadvantaged communities in being influenced when p is small. Similarly, both PoF and Eof' also show downward trend with the increase of the aversion parameter a. The reason lies that communities experience greater promotions in fair influence when the aversion parameter is smaller, resulting higher EoF and PoF. Moreover, there is hardly any faimess when 2 0.7 where the gap between u" and u is just too small.
4.3.2 Amazon, Youtube & DBLP
For Amazon, Youtube, and DBLP networks, we set = 0.5 and p(u;, 03) = [dda((:) where dan denotes the in-degree as the influence probability following the weighted IC model 17 We test different seed budget & that ranges from 5 to 50 with the step of 5. Results are shown in Figure 2
80
12
30
- PoF
- PoF
25-
- PaF
00
- RoF
- Fol
- Buf
8
20:
88 10-
g 15-
4
10-
20
0
50
k
k
(a) Amazon
(b) Youtube
(c) DBLP
Figure 2: Results of testing seed budget on Amazon, Youtube, and DBLP.
Generally, FIMM tends to produce a noticeably fairer output when small. reflects the idea that enforcing fairness constraint becomes casier when there is abundance of resources available. However, there are also some exceptions where smaller leads to a lower EoF, e.g., & = 20 Figure and k 15 in Figure This may be attributed the fact that the seed selection in FIMM follows a pattern of remedying the previously fair solutions in each round.
5
Conclusion
This paper focuses on the fair influence maximization problem with efficient algorithms. We first tackle the challenge of carrying out the unbiased estimation of the fractional power of the expected proportion of activated nodes in each community. Then, we deal with the challenge of integrating unbiased estimation into the RIS framework and propose an (1 1/e e) approximation algorithm FIMM. We further give theoretical analysis that addresses the concentration of the unbiased estimator of the fractional power. The experiments validate that our algorithm is both scalable and effective, which is consistent with our theoretical analysis.
There are several future directions from this research. One direction is to find some other unbiased estimators for the fair influence that would be easier to calculate through RIS Another direction is to explore a more efficient seed selection strategy. The fairness bound is also meaningful research direction.
The limitations our work are mainly two points. The first limitation is that our algorithm can only be efficient when the number of communities is small (e.g., a constant). The second limitation is that our algorithm based on the assumption that the minimal community utility of arbitrary seed set would not be too big.
Limitation
10

---

Acknowledgments and Disclosure of Funding
This work was supported by the Fundamental Research Funds for the Central Universities (No.2022QN1093),
References
[1] Binghui Peng and Wei Chen. Adaptive influence maximization with myopic feedback. In NeurlPS, pages 5575-5585 5584, 2019.
[2] Lichao Sun, Weiran Huang, Philip S. Yu, and Wei Chen. Multi-round influence maximization. In KDD, pages 2249-2258, 2018.
[3] Khurshed Ali, Chih-Ye Yu Wang, and Yi-Shin Chen. Leveraging transfer learning in reinforcement learning to tackle competitive influence maximization. Knowl. Inf. Syst., 64(8):2059-200 2090, 2022.
[4] Junaid Ali, Mahmoudreza Babaei, Abhijnan Chakraborty, Baharan Mirzasoleiman, Krishna P. Gummadi, and Adish Singla. On the faimesss of time-critical influence maximization in social networks. ICDE, pages 1541-1542, 2022.
[5] Yuchen Li, Ju Fan, Yanhao Wang, and Kian-Lee Tan. Influence maximization on social graphs: survey, IEEE Trans. Knowl. Data Eng., 30( 188-112882--1 2018.
[6] Bryan Wilder, Laura Onasch-Vers Juliana Hudson, Jose Luna, Nicole Wilson, Robin Petering, Darlene Woo, Milind Tambe, and Eric Rice. End-to-end influence maximization in the field. In AAMAS, pages 1414-1422) 2018.
[7] Aida Rahmattalabi, Shahin Jabbari, Himabindu Lakkaraju. Phebe Vayanos, Max Izenberg, Ryan Brown, Eric Rice, and Milind Tambe. Fair influence maximization: A welfare optimization approach. In AAAI, volume 35, pages 11630-11636 2021.
[8] Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. Group-fairness in influence maximization. IJCAI, pages 5997-6005, 2019.
[9] Aida Rahmattalabi, Phehe Vayanos, Anthony Fulginiti, Eric Rice, Bryan Wilder, Amulya Yadav, and Milind Tambe. Exploring algorithmic fairness in robust graph covering problems. In NeurlPS, pages 15750-15761, 2019.
[10] Ruben Becker, Gianlorenzo D Angelo, Sajjad Ghobadi, and Hugo Gilbert. Fairness in influence maximization through randomization. AAAI, pages 14684 14692, 2021.
[11] Muhammad Bilal Zafar, Isabel Valera, Manuel Godezz-odriguez, and Krishna P. Gummadi, Faimess constraints: Mechanisms for fair classification. In AISTA7S, volume 54, pages 962-970, 2017.
[12] Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier. Maximizing social influence in nearly optimal time. In SIAM, 2014.
[13] Youze Tang, Xiaokui Xiao, and Yanchen Shi. Influence maximization: near-optimal time complexity meets practical efficiency. In SIGMOD, 2014.
[14] Youze Tang, Yanchen Shi, and Xiaokui Xiao. Influence maximization in near-linear time: martingale approach. In SIGMOD, 2015.
[15] Pedro Domingos and Matthew Richardson. Mining the network value of customers. In KDD, 2001.
[16] Matthew Richardson and Pedro Domingos. Mining knowledge-sharing sites for viral marketing. In KDD, 2002.
[17] David Kempe, Jon M. Kleinberg, and Êva Tardos. Maximizing the spread of influence through social network. In KDD, 2003.

---

[18] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne M. VanBriesen, and Natalie S. Glance. Cost-effective outbreak detection in networks. In KDD, pages 420-429, 2007.
[19] Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In KDD, 2009.
[20] Wei Chen, Yifei Yuan, and Li Zhang. Scalable influence maximization in social networks under the linear threshold model. In ICDM, 2010.
[21] Chi Wang, Wei Chen, and Yajun Wang. Scalable influence maximization for independent cascade model in large-scale social networks. DMKD, 2012.
[22] Kyomin Jung, Wooram Heo, and Wei Chen. Irie: Scalable and robust influence maximization in social networks. In ICDM, 2012.
[23] Jing Tang, Xueyan Tang, Xiaokui Xiao, and Junsong Yuan. Online processing algorithms for influence maximization. In Proc. ACM SIGMOD, pages 991-1001, 2018.
[24] Ana-Andreea Stoica, Jessy Xinyi Han, and Augustin Chaintreau. Seeding network influence in biased networks and the benefits of diversity. In wwW. pages 2089-2098, 2020.
[25] Hervé Moulin. Fair division and collective welfare. 2004.
[26] Benjamin Fish, Ashkan Bashardoust, danah boyd. Sorelle A. Friedler, Carlos Scheidegger, and Suresh Venkatasubramaniian. Gaps information access in social networks? In WWW, pages 480-490, 2019.
[27] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14(1):265-294 1978.
[28] Gerald J Glasser. An unbiased estimator for powers of the arithmetic mean. Journal of the Royal Statistical Society: Series B (Methodological), 23(1):154 159, 1961.
[29] Hao Yin, Austin Benson, Jure Leskovec, and David F. Gleich. Local higher-order graph clustering. In KDD, pages 555-564, 2017.
[30] Nicola Barbieri, Francesco Bonchi, and Giuseppe Manco. Topic-aware social influence propa- gation models. In ICDM, pages 81-90, 2012.
[3]] Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. In ICDM, pages 745-754, 2012.
12

---

Appendix
A Proofs
Fact 2. (Chernoff bound) Let X1, X2...., Xn be R independent random variables with X; having
range [0, 11, and there exists J E [0, 1] making E[X;] = 1s for any E [R] Let Y = =Ei= X, for
any y > 0,
72
Pr(Y - tu 2 v- .tpp S exp(
tu).
2 + 37
For any 0 0<10 <21,
x2
Pr(Y tp S - ..ttpp tpp S exp( tpp).
Lemma Let o1 E (0,1), 01 E (0,1), and 02 12Q² lu(C)6))
where Q is the approximation
eq(1-bj
parameter. b max(ue Vc E C. and S argmaxs:jsssk (S) denotes the optimal
solution for the FIM problem based on R, then , R) 2 (1 (1-&1) E1) OPTp holds at least 1 - Ö1 probubility i 2 CO2-
Proof. Let X be the random variable for each R4 E R (R, rooted in c). such that X = if S n (i) # Ø, and X = 0 otherwise. Let ne = 0g - Σiepo X
Pr (S" ( R) < (1 - E1) OPTs} }
(0. n)!
= Pr
Σ The
1 1-a 0
(n, a)
X Xtn
(1 =1) 61)-
-PP(S)))))) Pa(5))
0g!
CEC
n=1
(0e -n)! n)!
Pr
Σ
The
1 1
in, a)
X
X Xan
<1 $1) Σ no (Sc
0g!
CEC
n=1
CEC
8
n- Te
Pr
nCe
1 a
(n, 0
<1 -E1) Σ nee
a
(n, a)(1 - -Sc()*)))
0g
LEC
R=1
CEC
n=1
< (1 - -&1) (1 1-a (1-0)
m(, () - (s()))))" " }}
-1 - II
1 Pr
1 -
(n,
ma -
Σ
0_
cEC
n=1
1=0
n=1
(6)
For each community c, let E = 1- Im a(na) (1- (i-) E1, thus e 2 E1 when a S 1/2, and
a 33 v(n (1 (-u=())))
Pr
1 - a
nnn O
Te
< (1 -1)
n(n, a) - "=)')) 1-a 2
0
n=l
n=l
1- 1
1-a Σ ((n,a) (11(())))()))) }
Pr
1
(
Te
i
< 1 a
Σ (1
0.
i
n=1
x=0
n=1
Pr
(1- (()))))) 1
1-a m a) ( {.(5)))*)
0
n=1
2=0
8
n-1
00
Pr
mn a))
II
me
> (1+ + $1)
Σ mn,, -1 (1=x)())))"
0g
1=0
n=1
Pr
m
n-1
Ne 0g
i
> (1 + E
Rv nln,
i=0
n=
13

---

Re
$ Pr
(( 2 (1 (1+ Σ
(1-
$ Pr Te (1 + +1)((1 u1())= {=(
Pr { Te - 2 (1 (1 }
Let +00= V1+
= =Pr Me 2 (1 s0)(1 uc(()))
I
= =Pr - 0o(1 uc(s))) 2 EOOo uc()))
c0 0. 0o un(s))) (-3
Sepp
(8)
Since
S 20
$
S & for S E e 1 and x 2 1, it holds
2x 2
81-c-1- Let
0₂ 2 o7
12 In( 2
(1
3ln(C/8,)
then < (1-
3ln(C/6,)
(
(</1+c|-1) (I-)())))
c 0c(1 -lcc(s)))
Eq. 8 eap
3
ci 3ln(C/61) (1 us())))
S eap
3 E0(1 u.(()))
= 81/C
(9)
Therefore,
Eq.06
< 1 - II (1 -1 (1-6)/ 01
(10)
cEC
To limit Eq 7 to the first Q (Q 2 2) terms, Eq.
becomes
n-1 Te i
Pr
nnn a)
> (1+ (1++1) E
(n, a) - (s())))" (S)
0. -
< Pr
(n, () Fe > (1 + +1)
Wn, a1 k²())))
#=1
#=1
< (1 (1+e1) ((+))(( o1
< Pr
S Pr (20) (1 -1 us))))))
Let 1 + E0 V1+
Pr Pr - (c [1 u. (S*)) 2 E00c (1 - (S*)))
2 (1 - un((5)))
$ seep
(T3 3
(11)
12Q² (C/1/)))
3ln(C/51)
3ln(C/81)
Let det
of us()) 2
- 1) (9/+
u. (S*)
(st))
8/1/O
(12)
Therefore,
Eg. 6 <d
(13)
indicates Pr Fa('", R) <1 (11-8))OPTT 2 6, thus concludes the proof.
14

---

Lemma 4. Let 82 E (0.1), 62 = (--1)= - and 02 = EQ (m()) e2
where Q is the approxima-
tion parameter, bo = ( Vc E C where S# could be an arbitrary fair solution. For each
bud S (which indicates (S) < (1 1/e - 8) OPTP, (S R) 2 (1 1/e) -1)) OPT
holds at most 52/ ("e) probability if 2 C02.
Proof. Let X be the random variable for each R₁ E R. (R; rooted in c), such that X = 1 if Sn Ro( # Ø, and X = otherwise. Let nec = Oe Eie Xz-
Pr
Fa (5) 2 (1 - (1--a)) OPTF
Pr
Fa (S, 2 (1+62) 62) (S)
8
121
Pr
Σ nee
1-a
(n, 0
2 2(1+ 82)
Σ ne
1-a a
n(n, a] uc()))")
0g -
REC
n=1
REC
n=1
S 11 - I|
1- Pr
1 1 a
mn, a)
n-1
Te -i
0g 2 (1)
1 1-a a
m(n - uo(s))) (1)o(()))
}}
dEC
n=1
1=0
n=1
(14)
1-a x(naa
((n.a) (1) "
For each community c, let 5/2
(-u,(s)) Eg, thus E/ 2 E2 when S 1/2, and
a E (())a)
R-1
Pr
a
(n,
Te
2 (1)
1-a Σ (1-
0
n=1
(=0
n=1
12
Pr
1
(n,
Te
i
2 1 - a
Σ
(n, uc(5))" +
1 1- a Σ
(1, a) (s))
0g i
1=1
t=0
n=1
n=1
Pr
((,,0) 0)
S
a
((, un(())) 82
1 -
nn, an, - us())))
0g
n=1
k=0
n=1
n=1
Pr
nn,
0g < (1 - +22 Σ (nn a) (s)) ())))(()))) k=0
To - i
x
(15)
(1-4.(8))
y02
To limit Eq.
to the first QQQQQQQ 2 2) terms, let y (Q+1)u.(ST
Eq. 15
becomes
8. ne 400
Q
n-
8
Pr
(n,
< (1-Eg Σ m(n a) =c(()))*
0
Pr
Te
(1
8
7(2, (l
mnn a)
n-1
II
Th - i
0g - S (1 +
Σ
Q
vo(s))"
0.
n=++1
1=0
Q
n-1
Q
< Pr
We
+
mnn
a))
me
< (1 - c))
Mn, (1, uc()))"
0
0 i
n=2
1=0
n=1
Q
Pr
(n,
< (1 -2))
uc())))
0 H
0
n=2
i=0
n=1
< Pr
a),
Te
Q + 0. Q
1
n s (1 (1- - +4) Σ
n(n, - uo(s))) }
(when x S Q Q-1)) 1)
+1
n=1
n=1
Te Q 1
> (1- - <5) - ((())
< Pr
0. - Q+1
15

---

Pr f ( Q+ 0 $ =2)=2)(11 ())
0. Q+1
Let
Ep // = +
Pr Te
0. Q +1 1 (1 - -1 =c(( (1)(11(()1))
(16)
Let %
50
Ne 8c QQ+1
6. 5. x--Q+1 Q+1 1,60 2 E -
me 0.- p
le x.-Q Q
Eq.
16
becomes
n 11
Pr
< (1 60) (1 -u.(S))
0. Q +
Pr
cec
$ (1
4e 0. Q +1
0g Te - Q + (0) (l(((()))
00
Ee 0. 0. Q+1 %))
Q+1
S eap
Oc(1 uc(5))
2
% 0c(1 - uc(S))
$ exp
2
8Q In (((()) )62)
(nn))( /02)
2ln(C(")))
Let
=2(1 - -u us))
(1 81 1/1-6) - (1 uc)
cB2 - us())
nG S dd//
(17)
k
Therefore.
II (1 62/0 ((T)) ) S d2/ (nG)
Eq.014 11 S 1
(18)
<EC
indicates Pr (S 2 (1 1/e) =1) OPTF } S d2/ ("(). thus concludes the proof.
B Additional Experiments
B.1 Running Time
The number of RR sets is mainly determined by both the size of the network and the number of communities. In the following, Note that our algorithm is currently implemented in Matlab 2022a, thus it costs more time to generate RR sets (generating RR sets in C++ could be at least 100 times faster). RRsets refers the time (seconds) used to generate RR sets, IMM and FIMM denote the time used to select seeds based on the generated RR sets for IMM and FIMM, respectively.
exhibit the runtime of our algorithm with the scale of networks.
Table 2: Running time (seconds).
Network
nG
C
RRsets
IMM
FIMM
Email
1,005
42
14.281
0.011
0.020
Amazon 12,698
509
82.204
0.028
0.283
Youtube
30,696
1,157
162.533
0.052
3.592
DBLP
72,875
1.352
735.755
0.063
18.259
Note that the proposed algorithm more suitable and could much more efficient under scenarios where the number of communities is rather limited (e.g., g,, constant).
16

---

B.2 Comparison with Equality- methods
Our proposed algorithm is based on the notion of welfare faimess,, which in favor of fair result-aware seeding. In this subsection, we aim to explore the difference between such results and community- aware seeding, which is based on the notion of equality. The Equality asks to divide the budget proportionally to the cluster sizes, Le., |S Val R k .n/ng. We adopt two strategies to select seeds under Equality: picking nodes with the highest degree per community and running IMM inside each community.
The dataset tested is the Email network (since the number of communities of other datasets is more than 50 and k is set to 50). The experiment settings are the same as the setting for Email in our 0.5 and p ranges from 0.001 0.01 with the step of 0.001). The Table below exhibits the results, where Sours. SC-HD and SC-MM refer to seeds selected by our method, seeds selected by community aware highest degree, and community-aware IMM, respectively. PoF and EoF are calculated w.r.t IMM in the classic influence maximization problem.
Section 4
Table 3: Comparison with equality- basee methods
PoF
EoF
Sours
SC-HD
SC-MM
S Sours
SCHDD
SC-IMM
0.001
21.77%
31.99%
21.56%
51.91%
45.08%
45.77%
0.002
16.92%
31.50%
20.56%
42.68%
37.31%
38.91%
0.003
12.11%
30.73%
20.76%
37.44%
31.76%
34.23%
0.004
10.08%
29.63%
19.11%
28.10%
20.97%
25.94%
0.005
9.22%
28.85%
17.63%
26.23%
16.49%
23.63%
0.006
6.31%
28.25%
17.96%
22.54%
3.82%
18.06%
0.007
5.48%
27.06%
16.21%
19.25%
N/A
13.57%
0.008
4.49%
26.03%
15.77%
17.11%
N/A
7.99%
0.009
3.70%
24.65%
14.88%
13.89%
N/A
N/A
0.01
2.57%
24.07%
15.64%
12.37%
N/A
N/A
As can seen from the results, both PoF (the lower the better) and RoF of Saurs (the higher the better) are always better than that of both SC-HD and SC-IM-- In other words, ScHED pays more price of fairness yet achieves a lower degree of fairness. Compared with SCHHD. SC-MM yields a better performance, Moreover, p increases, the fair influence of both Sc-HD and SC-IMM is even lower (leading to N/A of EoF) than that of IMM, which does not even contribute to fairness at all. The reason is that community-awer selection, while welfare fairness (also, MMF and DC) highlights fairness in the spreading results. The former could have an explicit fair distribution in seeding, but may still lead unfair results.
seeding highlights fairness in the process of seed allocation but not
17


Reviews:
[{"review_id": "F6sZTvdJ3n", "reviewer": "Reviewer_tPHQ", "summary": "This paper aims to study the problem of fairness-aware influence maximization over a community structure under a welfare fairness notion that balances fairness level and influence spread using an exponentially-weighted sum over communities objective with an fractional exponent parameter α expressing inequality aversion. Given an unbiased estimator for the fractional powers from [27], a reverse-influence-sampling approach, adapted from previous works, is applied to the problem that turns the problem into a weighted maximum coverage problem. The number of reverse reachable (RR) samples needed to achieve a good approximation and an algorithm is given that achieves a 1 − 1/e − ε approximation.", "questions": "The solution relies on a submodularity of the objective function and the accompanying analysis in [7]. However, there is no discussion of what happens in the most interesting case from the point of view of fairness, namely as α tends to 0. According to previous works, the objective is not submodular in exactly that case. This matter deserves discussion yet it is not addressed. The work pays no attention to more recents works in the area, such as [A, B]. There is no experimental comparison to the algorithms developed in those works, which, at least the ones in [A], also claim efficiency, and no discussion in terms of the framework presented in [B].\n\n[A] Fish et al.: Gaps in information access in social networks? WWW 2019.\n[B] Farnadi et al.: A unifying framework for fairness-aware influence maximization. Companion of The Web Conference 2020.", "limitations": "The paper offers a discussion on the ethical side of the objective aimed for.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. Revisiting an important problem with an aim to efficiency.\nS2. Lucrative application of reverse influence sampling approach.\nS3. Approximation guarantees.", "weaknesses": "W1. Limited novelty with respect to previous work in [7].\nW2. Lack of discussion of the most basic problem case of full fairness.\nW3. Lack of discussion of and comparison to most recent related work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **Response to Reviewer tPHQ**\n\nWe thank the reviewer for the insightful comments and suggestions. We reply to all your comments below.\n\n>**Weakness 1**: Limited novelty with respect to previous work in [7].\n\n**A1**: Literature [7] proposes a novel notion of fairness for influence maximization based on cardinal social welfare theory but gives no algorithm. In the field of influence maximization, designing efficient algorithms is also of high significance. Our work just adopts the objective function of cardinal welfare fairness proposed in [7] and **focuses on designing an efficient algorithm to maximize that objective function**. Therefore, the main contribution and key idea of our work are fundamentally different from those in [7].\n\n\n>**Weakness 2**: Lack of discussion of the most basic problem case of full fairness.\\\n>**Question 1**: The solution relies on a submodularity of the objective function and the accompanying analysis in [7]. However, there is no discussion of what happens in the most interesting case from the point of view of fairness, namely as $\\alpha$ tends to 0. According to previous works, the objective is not submodular in exactly that case. This matter deserves discussion yet it is not addressed.\n\n**A2**: According to [7], as long as $\\alpha<1$ and $\\alpha\\neq 0$, the objective function $W_\\alpha(u) = \\sum_{c \\in C} \\textbf{u}_c(S)^\\alpha$ satisfy 5 of their mentioned principles. Then, based on Lemma 1 in [7], any welfare function that satisfies their 5 principles is monotone and submodular in the influence maximization problem. Therefore, **the objective function adopted in our paper is still submodular in the influence maximization problem even as $\\alpha$ tends to 0**.\n\nIn addition, as you mentioned, the case of full fairness ($\\alpha$ tends to 0) is quite interesting. Under such a setting, any community $c$ that has $\\textbf{u}_c(S)>0$ would have a fair utility $\\textbf{u}_c(S)^\\alpha$ tends to 1. The problem would become a reachable problem that seeks to select a seed set $S$ that could reach the most number of communities. However, since $\\alpha>0$, it still satisfies submodularity, thus we did not further discuss it in our paper. \n\n\n>**Weakness 3**: Lack of discussion of and comparison to most recent related work.\\\n>**Question 2**:  The work pays no attention to more recent works in the area, such as [A, B]. There is no experimental comparison to the algorithms developed in those works, which, at least the ones in [A], also claim efficiency, and no discussion in terms of the framework presented in [B]. \n\n**A3**: As you mentioned, [A] and [B] are related to our work to some extent. However, due to the page limit, we did not to discuss them in the submitted version of our paper, the reasons of which are elaborated in the following.\n\n[A] proposes the $\\phi$-MEAN fairness where $\\mu_\\phi(S,V)=(\\frac{1}{|V|} \\sum_{v\\in V} p_v^\\phi)^{1/\\phi}$. They study the access gap over bipartitions and $k$-imbalance under different $\\phi$. In contrast, our paper addresses the problem of designing efficient algorithms with theoretical guarantees based on existing notions of fairness. Besides, [A] find that only $\\mu_{-\\infty}$ is balanced which corresponds to the **maximin fairness (MMF), which is also the only setting they test in experiments**. Therefore, we did not further discuss [A] in our paper as we already introduced MMF.\n\n[B] is an interesting work that develops a formalism which is general enough for specifying different notions of fairness. Their framework covers 4 fair notions, i.e., Equality, Equity, Maximin (MMF), and Diversity (DC). **These 4 fair notions are already introduced in our Related Work**. Our paper adopts the objective function of welfare fairness, which can better control the trade-off between fairness and total influence. Therefore, we did not further discuss [B] in our paper.\n\nBesides, for the most recent related work, such as MMF (the same in [A]) and DC, the comparison between those fair notions and welfare fairness (which is adopted in our paper) is already presented in [7]. The key idea of our work is to design an efficient algorithm for fair influence maximization based on welfare fairness. Datasets used in [B] contain only 5,00 nodes while our method could handle networks with more than 70,000 nodes efficiently.\n\nMoreover, regarding efficiency, [A] actually claims that **“since our goal in this paper is to introduce and validate a method for reducing access gaps, we will not focus on achieving the fastest implementations”**. In experiments, they show that their method is **\"prohibitively slow\"** with Greedy (costs more than 20 minutes on a network with only 1,294 nodes). Their method can only be efficient when adopting heuristics (such as Random, Gonzalez, and Naïve Myopic) with poor approximation ratios.\n"}, {"review_id": "E0HrYVVRTX", "reviewer": "Reviewer_ScbK", "summary": "The authors study a variant of the popular influence maximization problem\nthat incorporates fairness constraints. Given a partition of the node set\nof the graph into communities, the goal is to select seeds subject to\nbudget constraints that maximizes influence as well as reduces the\ninfluence gap between communities. The authors consider a particular notion\nof fairness called welfare fairness, where a single parameterized objective\nfunction can be used to achieve the desired balance between maximizing\ninfluence and maintaining fairness. The objective function is monotone\nsubmodular, and therefore, the greedy algorithm guarantees a constant\napproximation factor as in the case of the traditional influence\nmaximization problem. Since the greedy algorithm is not scalable to large\nnetworks, this paper focuses on developing an efficient algorithm using the\nreverse influence sampling (RIS) approach. The main contributions are an\nunbiased estimator for the fractional power of the arithmetic mean using\nTaylor expansion, solving a main hurdle for using RIS approach for welfare\nfairness objective function, and an analysis of the greedy algorithm based\non the RIS approach. Experiments are carried out on five social networks to\nstudy the trade-off between fairness and influence spread.", "questions": "There are some questions in the Weaknesses that need to be addressed.\n\nIn algorithm 1, line 6, is it sample with replacement?\n\nIn algorithm 1, line 9, what if c(v) is same as c(u)?\n\nIn algorithm 2, line 20, what is \\eta(v)?\n\nWhat is \\Theta in Lemma 3? It is not defined anywhere.", "limitations": "Limitations not adequately addressed.\n\nNo negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper addresses an important topic of scalability in influence\nmaximization with fairness. The unbiased estimator for the fractional power\nof the arithmetic mean is a significant contribution of this paper, which\ncould be applicable to other problems as well. The paper addresses\nimportant computational and approximation related aspects.\n\nThe paper is generally well written.", "weaknesses": "The importance of/need for the unbiased estimator is not discussed.\nFirstly, in Section 3.1, it is pointed out that (\\hat{u}_c)^\\alpha is a\nbiased estimator of u_c^\\alpha. Suppose we were to use it, how bad would\nthe outcome be? \n\nA second related issue is that the paper does not comment on the complexity\nof computing the unbiased estimate. When the number of RR sets is large,\nupdating according to equation (5) can be compute intensive (Algorithm 2\nline 11).\n\nAlso, some approximation of equation (5) must be involved as the summation\nover n goes from 1 to infinity. The authors do not seem to discuss about\nthe truncation of the Taylor series and its effect on the accuracy.\n\nIn Theorem 1, the role of \\epsilon is not clear. It does not seem to\nfeature in the probability expression or have anything to do with the size\nof the RR set. In Lemma 4, it is mentioned, but again, its role is not at\nclear.\n\nExperiments section could be much stronger: Considering that the key problem\naddressed by the paper is scalability, the experiments section does\nnot provide any analysis of the computation time of the algorithm and how\nit scales with the size of the networks. It also does not provide any\nanalysis regarding how truncation of higher order terms in the Taylor\nseries affect the performance. Thirdly, there is no analysis of how it\nscales with the size of the RR set. \n\nMinor comments:\nLine 82: \"However, these notions can hardly ...\" It would be better if this\nsentence was supported by references.\n\nLine 197: that covered ... -> that are covered ...\n\nLine 219: then it holds ... -> then the following holds: ...\n\nLine 231: ... holds at least ... -> holds with probability at least ...", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **Response to Reviewer ScbK**\n\nThank you for your thorough and insightful comments as well as acknowledging our theoretical analysis. We reply to all the points below.\n\n>**Weakness 1**: The importance of/need for the unbiased estimator is not discussed. Firstly, in Section 3.1, it is pointed out that $(\\hat{u}_c)^\\alpha$ is a biased estimator of $u_c^\\alpha$. Suppose we were to use it, how bad would the outcome be?\n\n**A1**: Thank you for addressing this interesting problem. As indicated by [r27] (ref [27] in our paper) which proposes an unbiased estimator for powers of the arithmetic mean, \"In any problem for which an unbiased estimator is thought desirable, the proposed unbiased estimator $\\hat{x}^m$ ($m=2,3,\\cdots$) is naturally preferable, although **the bias in $\\hat{x}^m$ may not be very large**. Furthermore, for many, if not most, of the populations that may be expected to arise in statistical work **the variance of $\\hat{x}^m$ will be smaller than the mean square of$\\bar{x}^m$**\".\n\nIn our paper, we propose an unbiased estimator for the fractional powers of the arithmetic mean based on Taylor expansion and the unbiased estimator for the integer powers of the arithmetic mean. Therefore, we can calculate both the variance of our proposed unbiased estimator and the mean square error of the biased $(\\hat{u}_c)^\\alpha$ following the analysis in section 3 of [r27].\n\nMoreover, though the outcome may not be too bad when using the biased estimator, our theoretical analysis cannot hold based on such a biased estimator and we will not able to give an lower-bound guarantee on our algorithm.\n\n[r27] Gerald J Glasser. An unbiased estimator for powers of the arithmetic mean. Journal of the Royal Statistical Society: Series B (Methodological), 23(1):154–159, 1961.\n\n>**Weakness 2**: A second related issue is that the paper does not comment on the complexity of computing the unbiased estimate. When the number of RR sets is large, updating according to equation (5) can be compute intensive (Algorithm 2 line 11).\n\n**A2**: As you mentioned, updating according to Eq.(5) can be computationally intensive when we compute the summation over $n$ from 1 to infnity. However, in experiments, we only keep the first two terms, which greatly reduces the computation cost. The reason that we truncate the Taylor series to the first two terms is detailed in the next response **A3**.\n\n>**Weakness 3**: Also, some approximation of equation (5) must be involved as the summation over n goes from 1 to infinity. The authors do not seem to discuss about the truncation of the Taylor series and its effect on the accuracy.\n\n**A3**: We were sorry that we did not make it clear in our main paper. Actually, the $Q$ (referred to as the approximation parameter) in Lemma 3 and Lemma 4 indicates the truncation of the Taylor series where we only keep the first $Q$-terms. Moreover, Theorem 1 shows that our algorithm is theoretically guaranteed for any $Q\\geq 2$.\n\n>**Weakness 4**: In Theorem 1, the role of \\epsilon is not clear. It does not seem to feature in the probability expression or have anything to do with the size of the RR set. In Lemma 4, it is mentioned, but again, its role is not at clear.\n\n**A4**: In general, $\\varepsilon$ is a tunable parameter that controls the approximation ratio ($1-1/e-\\varepsilon$) between the output of our algorithm and the optimal result. By setting $\\varepsilon$ (controls accuracy) and $\\ell$ (controls confidence), which are two standard parameters in IMM, we can determine the number of RR sets need. The smaller the $\\varepsilon$ is, the higher the approximation ratio can achieve, and the more RR sets should be generated. Besides, following the default setting of IMM, we set $\\varepsilon=0.1$ and $\\ell=1$ in our experiments.\n\n>**Weakness 5**: Experiments section could be much stronger: ......\n\n**A5**: The number of RR sets is mainly determined by both the size of the network and the number of communities. In the following, we exhibit the runtime of our algorithm with the scale of networks. Note that our algorithm is currently implemented in **Matlab**, thus it costs more time to generate RR sets (generating RR sets in **C++** could be more than 100 times faster). **RR sets** refers to the time (seconds) used to generate RR sets, **IMM** and **FIMM** denote the time used to select seeds based on the generated RR sets for IMM and FIMM, respectively.\n\n|Network|$n$|$C$|RRsets|IMM|FIMM|\n|--|--|--|--|--|--|\n|Email|1,005|42|14.281|0.011|0.020|\n|Amazon|12,698|509|82.204|0.028|0.283|\n|Youtube|30,696|1,157|162.533|0.052|3.592|\n|DBLP|72,875|1,352|735.755|0.063|18.259|\n\n>**Question 1**: In algorithm 1, line 6, is it sample with replacement?\n\n**A6**: Yes, it is randomly sampled with replacement, which means each node could be the root for multiple RR sets.\n\n>**Question 2**: In algorithm 1, line 9, what if c(v) is same as c(u)?\n\n**A7**: $\\kappa[v][c]$ is an indicator that implies the number of RR sets rooted in the community $c$ that is covered by $v$. Therefore, it still counts when $c(v)=c(u)$ in algorithm 1, line 9.\n\n>**Question 3**: In algorithm 2, line 20, what is \\eta(v)?\n\n**A8**: $\\eta(v)$ is a linked list from nodes to their covered RR sets. It is initialized when generating RR sets in algorithm 2, line 1, as an output from algorithm 1 (line 11).\n\n>**Question 4**: What is \\Theta in Lemma 3? It is not defined anywhere.\n\n**A9**: The $\\theta$ in Lemma 3 (and also Lemma 4) indicates the total number of RR sets. It is first introduced in line 187 of our paper.\n\nBesides, we are sorry for our carelessness in forgetting to mention that $\\theta = max( \\theta_1, \\theta_2)$ in Theorem 1.\n\n>**Limitations**: Limitations not adequately addressed.\n\n**A10**: The limitations of our work are mainly two points. The first limitation is that our algorithm can only be efficient when the number of communities is small (e.g., a constant). The second limitation is that our algorithm only works for networks with disjoint groups."}, {"review_id": "hJzV9na0pC", "reviewer": "Reviewer_RYE8", "summary": "The authors apply fairness to the influence maximization problem (IM). On a social network, IM models which node subset should be used to trigger the spread of information to maximize its effects. A motivating application is the selection of leaders for natural disaster preparedness, where in existing methods, minority leaders are disproportionately underrepresented. They are not the first to do this, however they are the first to introduce efficient algorithms for solving IM with welfare fairness, which allows the user to parametrize an objection on sliding scale between total fairness and no fairness at all (i.e., maximum influence spread).\n\nThey work in the Independent Cascade model of influence spreading, where each node has a given probability of influencing an adjacent node, and influence is randomly spread according to these probabilities across a number of timesteps. The influence spread, i.e. the objective, is the number of influenced nodes when the process converges. By submodularity, the unfair problem can be solved greedily to a (1-1/e) approximation factor. They assume the given graph is separated into a small number of communities to apply their fairness notion to. While this also admits a greedy approach via Monte Carlo methods, it requires too long to run. \n\nTheir main contribution is a (1-1/e-epsilon) approximate and efficient solution to IM under welfare fairness. En route, they provide an unbiased estimator of the fair objective under a number of random seeds for which edges spread influence when. This is harder than the vanilla problem because the objective is raised to a power alpha in [0,1] as opposed to just 1. They show how to use a Taylor series to provide an unbiased estimator. This is used to then compute the marginal expected gain in influence of adding a vertex to their set and thus greedily select the best one.\n\nThey also experimentally validate their results on five different, semi-synthetic data (e.g., for their Flixster data, they had to construct community information). They show that the price of fairness and effect of fairness both decrease as the alpha parameter increases, which makes sense since that decreases the fairness impact on the objective. They also show that adding more influence budget generally decreases the price and effect of fairness.", "questions": "1. A big value of your work is that your algorithm is efficient. Do you have any experiments that evaluate the efficiency?\n2. Can you give a high level discussion of the results from Section 3.4?\n3. For someone not in the area of influence spreading, can you discuss how natural the welfare fairness metric is? It's somewhat unintuitive at a glance.\n4. Big question: what is the runtime of your algorithm?", "limitations": "I do not see a limitations section. Most papers have limitations of one kind or another, even highly theoretical ones like this. However, I don’t think it is the most necessary in this case, as no subjects are involved and they are only suggesting a general tool.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "To my knowledge, the theoretical results of this paper are substantial and original. It’s always interesting and practical to see how notions of fairness apply to different problems. They are the first to efficiently solve IM under welfare fairness, and their proposal of an unbiased estimator for the marginal influence spread of a vertex seems notable, though I am not particularly familiar with influence literature (e.g., it is possible these methods are pretty standard for influence spreading strategies). From my standpoint, it is a nice result with a solid place in fairness literature.", "weaknesses": "While I think the paper is reasonably clear, it can be quite dense at times with its heavy use of notation. I found it particularly hard to follow in Section 3.4, when they pretty much state two lemmas and a theorem, deferring most proofs to the appendix. I think it’s better to explain these things at a high level more and defer formal statements to the end. It was hard to make much of it. In general, I would prefer the paper to undergo more edits for clarity, particularly in Section 3.4, before publication.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **Response to Reviewer RYE8**\n\nThank you for your insightful comments and suggestions. We reply to all your comments below.\n\n> **Weakness 1**: While I think the paper is reasonably clear, it can be quite dense at times with its heavy use of notation. I found it particularly hard to follow in Section 3.4, when they pretty much state two lemmas and a theorem, deferring most proofs to the appendix. I think it’s better to explain these things at a high level more and defer formal statements to the end. It was hard to make much of it. In general, I would prefer the paper to undergo more edits for clarity, particularly in Section 3.4, before publication.\\\n>**Question 2**: Can you give a high level discussion of the results from Section 3.4?\n\n**A1**: Thanks for your suggestion. The main idea of Section 3.4 is to analyze how many RR sets we need to generate, such that the proposed algorithm could have a good lower bound with theoretical guarantee.\n\nTo be exact, we find that when we generate $\\theta= \\frac{12Q(\\log{2}+\\log{CQ}+\\ell\\log{n})}{\\varepsilon^2(1-b_0)}\\geq max(\\theta_1, \\theta_2)$ RR sets, our algorithm can guarantee a $1-1/e-\\varepsilon$ approximation towards the optimal solution with a probability at least $1-1/n^\\ell$ for any $\\varepsilon>0$, $\\ell>0$, and $Q\\geq 2$.\n\nMoreover, we have summarized important symbols in our paper and presented them in the following Table:\n\n| Symbol | Explanation |\n|--|--|\n| $G=(V, E, p)$ | network |\n| $V$ | node set of the network |\n| $E$ | edge set of the network |\n| $n_G$ | number of nodes in $G$, i.e. $n_G=\\|V\\|$ |\n| $p(u,v)$ | probability that $u$ influence $v$ |\n| $S$ | seed set |\n| $S^*$ | the optimal seed set for fair influence maximization |\n| $ap(v,S)$ | the expected probability that $v$ is activated by $S$ |\n| $\\sigma(S)$  | influence spread of $S$, i.e. $\\sigma(S) = \\sum_{v\\in V} ap(v,S)$ |\n| $\\mathcal{C}=\\\\{c_1,c_2,c_3,\\cdots\\\\}$  | community structure |\n| $V_c$ | node set in community $c$ |\n| $n_c$ | number of nodes in community $c$, i.e. $n_c = \\|V_c\\|$ |\n| $\\bf{u}_c$ | utility of $c$ (expected fraction of influenced nodes in $c$) |\n| $F_\\alpha(S)$ | fair influence of $S$ |\n| $\\mathcal{R}$ | the set of RR sets |\n| $\\mathcal{R}_c$ | the set of RR sets rooted in community $c$ |\n| $\\hat{F}_\\alpha(S,\\mathcal{R})$ | the unbiased estimator for fair influence of $S$ based on $\\mathcal{R}$|\n| $\\theta$ | the number of RR sets |\n| $\\theta_c$ | the number of RR sets rooted in community $c$ |\n| $\\alpha$ | aversion parameter regarding fairness |\n| $Q$ | approximation parameter for Taylor expansion |\n| $\\varepsilon$ | accuracy parameter |\n| $\\ell$ | confidence parameter |\n\n\n>**Question 1**: A big value of your work is that your algorithm is efficient. Do you have any experiments that evaluate the efficiency?\\\n>**Question 4**: Big question: what is the runtime of your algorithm?\n\n**A2**: When the number of communities is small (e.g., a constant), then the time complexity of Algorithm 2 in our paper mainly depends on the number of generated RR sets $\\theta$. Furthermore, the value of $\\theta$ is mainly determined by both the size of the network and the number of communities.\n\nIn the following, we exhibit the runtime of our algorithm with the scale of networks where we set $\\alpha=0.5$, $k=50$, $\\varepsilon=0.1$, $\\ell=1$, and $Q=2$. Note that our algorithm is currently implemented in **Matlab**, thus it costs more time to generate RR sets (generating RR sets in C++ could be about 100 times faster). In the following Table, we test four networks with ground-truth community structure where **RR sets** refers to the time (seconds) used to generate RR sets, **IMM** and **FIMM** denote the time used to select seeds based on the generated RR sets for IMM and FIMM, respectively.\n\n|  Network | $n$ | $C$ | RR sets | IMM | FIMM |\n| --: | --: | --: | --: | --: | --: |\n| Email | 1,005 | 42 | 14.281  | 0.011 | 0.020 | \n| Amazon | 12,698 | 509 | 82.204 | 0.028 | 0.283 | \n| Youtube | 30,696 | 1,157 | 162.533  | 0.052  | 3.592  |\n| DBLP | 72,875 | 1,352 | 735.755  | 0.063 | 18.259 |\n\n\n>**Question 3**: For someone not in the area of influence spreading, can you discuss how natural the welfare fairness metric is? It's somewhat unintuitive at a glance.\n\n**A3**: Assuming we are trying to instruct a notice over a crowd consisting of three disjoint communities of the same size by selecting some influencers to spread the notice, the first solution leads to the influenced fraction in each community as 0.16, 0.16, and 0.81, and the second solution leads to that as 0.36, 0.36, and 0.36. Influence maximization would prefer the first solution since the total influenced fraction is 1.12, bigger than 1.08 as in the second solution. However, influence maximization with welfare fairness ($\\alpha=0.5$) would prefer the second solution since $0.36^{0.5}+0.36^{0.5}+0.36^{0.5} = 1.8$, bigger than $0.16^{0.5}+0.16^{0.5}+0.81^{0.5}=1.7$ as in the first solution.\n\nThe natural welfare fairness metric can also be described by the **Transfer Principle** mentioned in [r7] (ref [7] in our paper). Consider individuals $i$ and $j$ in utility vector $\\bf{u}$ such that $u_i<u_j$. Let $\\bf{u'}$ be another utility vector that is identical to $\\bf{u}$ in all elements except $i$ and $j$ where $u'_i = u_i + \\delta$ and $u'_j = u_j - \\delta$ for some $\\delta \\in (0, (u_j-u_i)/2)$. Then, $W(\\bf{u}) < W(\\bf{u'})$. Informally, transferring utility from a high-utility to a low-utility individual should increase social welfare.\n\nIn general, welfare fairness asks to find a solution that could lead to a fairer allocation (smaller gap) among different groups, with a limited sacrifice in the total influence.\n\n[r7] Aida Rahmattalabi, Shahin Jabbari, Himabindu Lakkaraju, Phebe Vayanos, Max Izenberg, Ryan Brown, Eric Rice, and Milind Tambe. Fair influence maximization: A welfare optimization approach. In AAAI, volume 35, pages 11630–11638, 2021.\n"}, {"review_id": "3kuH2cdfa2", "reviewer": "Reviewer_uZjd", "summary": "The paper proposes an algorithm for fair influence maximization. The objective is defined as a sum of powers of a utility function for each cluster, indicating that each cluster should receive some influence. Reducing the exponent will bring the objective to a fairer distribution of influence. An algorithm based on max cover on reverse reachable sets is presented. Optimal number of sets are derived to guarantee $(1-1/e - \\epsilon)$-approximation", "questions": "- Please see the issues raised in \"Weaknesses\"\n- Do we need the constraint $\\alpha > 0$? My intuition is that the method will work with negative $\\alpha$ as well, but it needs to be carefully analyzed.", "limitations": "Minor issue: A discussion on the impact of the assumptions could be included. ", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The key idea to convert the powers into sums using the binomial theorem is elegant, as it helps with modifying the existing algorithm on influence maximization for the proposed objective.\n- Detailed derivations are presented.", "weaknesses": "- Baselines: While the theoretical guarantee is the key contribution, the experiment part of the paper can be strengthened. How much do we gain from this algorithm compared to some simple heuristics? One may consider simple heuristics like degree. Better heuristics may also be generated, e.g., (1) picking high-degree nodes from each cluster, and (2) using the RR sets in Algorithm 1 but performing max-cover without Eq (5) [maybe similar to performing Influence Maximization independently in each cluster]\n\n- The derivation assumes that a fair solution exists, in the form of $b = \\max \\mathbf{u_c} (S^{\\\\#})$. The usage of this appears in the proofs, but some indication of how this would impact the main results could be discussed. \n\n- The symbol $n$ is overloaded. It is used as an index for the summation as well as the number of nodes. I think the paper will benefit from a table of symbols.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### **Response to Reviewer uZjd**\n\nThank you for your insightful comments and suggestions. We reply to all your comments below.\n\n> **Weakness 1**: Baselines: While the theoretical guarantee is the key contribution, the experiment part of the paper can be strengthened. How much do we gain from this algorithm compared to some simple heuristics? One may consider simple heuristics like degree. Better heuristics may also be generated, e.g., (1) picking high-degree nodes from each cluster, and (2) using the RR sets in Algorithm 1 but performing max-cover without Eq (5) [maybe similar to performing Influence Maximization independently in each cluster]\n\n**A1**: Thanks for addressing an interesting problem. However, this paper focuses on designing an efficient algorithm for the fair influence maximization problem based on the notion of welfare fairness. Therefore, adopting simple heuristics as degree can hardly achieve the fairness that the problem asks for. Besides, we have adopted IMM (just as using the RR sets in Algorithm 1 but performing max-cover without Eq (5)) as our baseline, which is how we calculate RoF and PoF. In other words, we test how much influence spread would cost to access fairness and to what extent our algorithm steps towards fairness, compared with IMM.\n\n>**Weakness 2**: The derivation assumes that a fair solution exists, in the form of $b_0=\\max \\bf{u}_c(S^\\\\#)$. The usage of this appears in the proofs, but some indication of how this would impact the main results could be discussed.\\\n>**Limitations**: Minor issue: A discussion on the impact of the assumptions could be included.\n\n**A2**: We were sorry for our previous sloppy expression that claims $S^\\\\#$ as a fair solution. Actually, we intend to assume that the $b_0=\\max \\bf{u}_c(S^\\\\#)$ would not be too large for an arbitrary solution $S^\\\\#$ under the fair influence maximization problem. The $b$ would impact the number of RR sets we need to generate to guarantee our algorithm. As shown in Lemma 4, the bigger the $b_0$, the more RR sets we need to generate. Therefore, we assume that $b_0$ should not be too large (e.g. $b_0\\leq 0.9$) for an arbitrary solution. We believe that our assumption is valid in the vast majority of cases when the seed budget $k$ is small (usually 50) and the network is large with a limited number of communities.\n\n\n>**Weakness 3**: The symbol $n$ is overloaded. It is used as an index for the summation as well as the number of nodes. I think the paper will benefit from a table of symbols.\n\n**A3**: Thanks for pointing out this issue as well as your kind suggestion. We maintain the index for summation as $n$ and change the number of nodes in $G$ to $n_G$.\n\nBesides, we have summarized important symbols in our paper and presented them in the following Table:\n\n| Symbol | Explanation |\n|--|--|\n| $G=(V, E, p)$ | network |\n| $V$ | node set of the network |\n| $E$ | edge set of the network |\n| $n_G$ | number of nodes in $G$, i.e. $n_G=\\|V\\|$ |\n| $p(u,v)$ | probability that $u$ influence $v$ |\n| $S$ | seed set |\n| $S^*$ | the optimal seed set for fair influence maximization |\n| $ap(v,S)$ | the expected probability that $v$ is activated by $S$ |\n| $\\sigma(S)$  | influence spread of $S$, i.e. $\\sigma(S) = \\sum_{v\\in V} ap(v,S)$ |\n| $\\mathcal{C}=\\\\{c_1,c_2,c_3,\\cdots\\\\}$  | community structure |\n| $V_c$ | node set in community $c$ |\n| $n_c$ | number of nodes in community $c$, i.e. $n_c = \\|V_c\\|$ |\n| $\\bf{u}_c$ | utility of $c$ (expected fraction of influenced nodes in $c$) |\n| $F_\\alpha(S)$ | fair influence of $S$ |\n| $\\mathcal{R}$ | the set of RR sets |\n| $\\mathcal{R}_c$ | the set of RR sets rooted in community $c$ |\n| $\\hat{F}_\\alpha(S,\\mathcal{R})$ | the unbiased estimator for fair influence of $S$ based on $\\mathcal{R}$|\n| $\\theta$ | the number of RR sets |\n| $\\theta_c$ | the number of RR sets rooted in community $c$ |\n| $\\alpha$ | aversion parameter regarding fairness |\n| $Q$ | approximation parameter for Taylor expansion |\n| $\\varepsilon$ | accuracy parameter |\n| $\\ell$ | confidence parameter |\n\n\n>**Question 1**: Do we need the constraint $\\alpha>0$? My intuition is that the method will work with negative $\\alpha$ as well, but it needs to be carefully analyzed.\n\n**A4**: Yes, we have to constraint $\\alpha>0$ in our paper. Though our method may work with a negative $\\alpha$, yet a negative $\\alpha$ will make the fair utility $\\textbf{u}_x(S)^{\\alpha}>\\textbf{u}_y(S)^{\\alpha}$ when $\\textbf{u}_x(S) < \\textbf{u}_y(S)$ where $x$ and $y$ are two communities. It means that the community with a lower utility will have a higher fair utility, i.e., monotone decreasing rather than monotone increasing. Then, the algorithm would encourage communities to pursue lower utility, which is contrary to the aim of influence maximization.\n\n"}]

Author rebuttal:

Meta-review: This paper studies a fair influence maximization problem on large-scale graphs. Three reviewers holds a weakly positive view of the paper. A fourth reviewer has, instead, an unfavorable view of the paper.
Given the reviews, the rebuttal, the subsequent discussions, and my own assessment of the paper, I concur with the positive reviewers --- I believe that this paper would be a nice addition to the NeurIPS program.
Decision: Accept (poster)