Fairness in Social Influence Maximization via Optimal Transport
Authors: Shubham Chowdhary
Giulia De Pasquale
Nicolas Lanzetti
Ana-Andreea Stoica
Florian Dorfler
Venue: NeurIPS 2024 poster (2024)
Keywords: Fairness
social influence maximization
optimal transport
Primary area: fairness

Abstract: We study fairness in social influence maximization, whereby one seeks to select
seeds that spread a given information throughout a network, ensuring balanced
outreach among different communities (e.g. demographic groups). In the literature,
fairness is often quantified in terms of the expected outreach within individual
communities. In this paper, we demonstrate that such fairness metrics can be
misleading since they overlook the stochastic nature of information diffusion
processes. When information diffusion occurs in a probabilistic manner, multiple
outreach scenarios can occur. As such, outcomes such as “In 50% of the cases, no
one in group 1 gets the information, while everyone in group 2 does, and in the
other 50%, it is the opposite”, which always results in largely unfair outcomes,
are classified as fair by a variety of fairness metrics in the literature. We tackle
this problem by designing a new fairness metric, mutual fairness, that captures
variability in outreach through optimal transport theory. We propose a new seed-
selection algorithm that optimizes both outreach and mutual fairness, and we show
its efficacy on several real datasets. We find that our algorithm increases fairness
with only a minor decrease (and at times, even an increase) in efficiency.

Fairness in Social Influence Maximization via Optimal Transport
Shubham Chowdhary
Giulia De Pasquale"
Nicolas Lanzetti' ETH Zürich
ETH Zürich schowdhary@ethz.cm ch
Eindhoven University of Technology
g.de de. pasquale@tue. .n1
Inicolas@ethz.c ch
Ana-Andreea Stoica
Florian Dörfler
Max Planck Institute, Tübingen
ETH Zürich
ana-andreea, htw.uddree..toocccttubeeeeeeeee mpg de
dorflerBethz.c ch
Abstract
We study fairness in social influence maximization, whereby one seeks to select seeds that spread given information throughout network, ensuring balanced outreach among different communities (e.g. demographic groups). In the literature, fairness is often quantified in terms of the expected outreach within individual communities. In this paper, we demonstrate that such fairness metrics can be misleading since they overlook the stochastic nature of information diffusion processes. When information diffusion occurs in probabilistic manner, multiple outreach scenarios can occur. As such, outcomes such as "In 50% of the cases, no one in group gets the information, while everyone in group 2 does, and in the other 50%, the opposite", which always results in largely unfair outcomes, are classified as fair by variety of faimess metrics in the literature. We tackle this problem by designing new fairness metric, mutual fairness, that captures variability in outreach through optimal transport theory. We propose new seed- selection algorithm that optimizes both outreach and mutual fairness, and we show its efficacy several real datasets. We find that our algorithm increases faimess with only a minor decrease (and at times, even an increase) in efficiency.
Introduction
Problem Description. Social networks play a fundamental role in the spread of information, as in the context of commercial products endorsement [17], job vacancy advertisements [3], public health awareness [27], etc. Information, ideas, or new products can either go viral and potentially bring significant changes in community die out quickly. In this context, a fundamental algorithmic prob- lem arises, known as Social Influence Maximization (SIM) [11, 12]. SIM studies how to strategically select pre-specified small proportion of nodes in the social network the early adopters seeds so that the outreach generated by a diffusion process that starts at these early adopters is maximized. Consider, for example, product endorsement campaign: the early adopters users who receive the product first to promote it to their friends. who in turn may or may not adopt it. The optimal selection of early adopters is known be an NP-hard problem [11]. Thus, many heuristic strategies have been proposed, based on iterative processes such as greedy algorithms or on network centrality measures. However, all these algorithms purely rely on the graph topology and are agnostic to users' demographics, which raises significant fairness concerns, especially in contexts of health awareness campaigns, education, and job advertisements, where one wants ensure an
strategically selected
Authors contributed equally.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

equitable spreading of information. Indeed, real-worid social networks are populated by different social groups based on gender, age, race, geography, etc., with different group sizes or connectivity patterns. Ignoring these aspects and focusing only on the outreach maximization process usually leads to the early adopters being the most central nodes. Consequently, low-interconnected minorities are often neglected from the diffusion process, thus causing fundamental inequity in the information propagation and biases exacerbation [10, 25].
Related Work. The problem of SIM was first introduced in 2003 in Kempe et al. [11], where the problem of optimally selecting a (limited) set of early adopters was proved to be NP-hard. The study of SIM under fairness guarantees has more recent history [5]. Several multiple group-level fairness metrics have been proposed over the years [6]. They fall under the notions of equity [23, 9. 10], equality [6], max-min fairness [7, 30]. welfare [16], and diversity [25]: all of them quantify the fair distribution of influence across groups. In particular, Stoica et al. [23] propose a new SIM algorithm that operates under the constraint that, in expectation, the same percentage of users in each category is reached. Junaid et al. [9] optimize outreach under fairess and time constraints, by ensuring that the expected fraction of influenced nodes in each group is the same within a prescribed time deadline. Farnadi et al. [6] propose a unifying framework that encodes all different definitions of fairness in the SIM process as constraints in a linear program that optimizes outreach. Several other works [7, 30] adopt a max-min strategy. Specifically, in Fish et al. [7] fairness is ensured by maximizing the minimum probability of a group receiving the information through modifications of the greedy algorithm. Zhu et al. [30] ensure that the outreach contains a pre-specified proportion of each group in a population. Finally, Tsang et al. [25] optimize outreach under the constraint that no group should be better off by leaving the influence maximization process with their proportional allocation of resources done internally. All these definitions involve a marginal expected value of fairness in groups, without considering the correlations or other higher-order moments - for the joint probability distribution of different groups adopting the information (see Farnadi et al. [6] for an overview). In contrast, our work introduces a novel formalism for taking into account the actual joint distribution of outreach among groups, thus considering all groups simultaneously, highlighting limitations of various faireess metrics and developing new seed selection policy that strategically extracts and optimizes our proposed notion of fairness. To conclude, our work is inspired by a recent line of work that draws on optimal transport theory [28] for fairness guarantees [2, 4, 21, 29, 20, 24). To our knowledge, this is the first work to develop novel metrics and seeding algorithms that leverage optimal transport for the SIM problem.
Motivation. Many models of diffusion processes in the SIM problem are inherently stochastic, meaning that who gets the information transmitted can vary greatly from one run to another. Consider, as an example, the case in which 50% of realizations over a diffusion process, no one in group 1 receives the information and everyone in group does, whereas in the other 50% it is the opposite. This circumstance would be classified as fair in expectation, even though it is commonly not perceived as "fair". We show how this phenomenon is common in real-world data and how our proposed framework can detect such undesired scenarios. This prompts us to study a novel faireess metric.
Contributions. Our main contribution is twofold: first, we propose a new fairness metric based on optimal transport, called mutual fairness, and second, we propose novel seeding algorithm that optimizes for both the group-wise total outreach (termed efficiency) and faimnsss. Our proposed fairness metric provides stronger fairness guarantees, and it reveals and overcomes known limitations of various other fairness metrics in the literature. Specifically, we leverage optimal transport theory to build mutual fairness, a metric that accounts for all groups simultaneously in terms of the distance between an ideal distribution where all groups receive the information in the same proportion. We leverage our proposed mutual fairness metric to provide unifying framework that classifies the most celebrated coormatiio-spreadinn algorithms both in terms of faimess and efficiency. All algorithms are tested on a variety of real-world datasets. We show how our approach unveils new insights into the role of network topology on fairness; in particular, we observe that selecting group-label blind seeds in networks with moderate levels of homophily induces inequality in information access. In contrast, very integrated or very segregated networks tend to have quite fair and efficient access to information across different groups upon greedy seedset selection. We then extend our mutual fairness metric to also account for efficiency, thus introducing the notion of f-fairness with 33 being the tuning parameter for the that optimizes over the proposed f-fairness metric and enhances fairesss with either small trade-off
tra Finally, we design a new seedset selection algorithm

---

or even improved efficiency. This novel approach provides a comprehensive evaluation and design tool that bridges the gap between faireess and efficiency in SIM problems.
2 Preliminaries
Notation. Given m N, we let [m]] denote the interval of integers from 1 to m. We denote by G a network, considered undirected, and by (C)) the m groups of different sensitive attributes. In this paper, we consider m groups, noting that our framework is easily generalizable to more groups as discussed in Appendix B. We denote by (c( the influence function of seedset S over a network G. through some diffusion process. In other words, (c( determines the set of nodes reached by the seedset under a diffusion process. Then, (0c(S)) is often referred to as the outreach, a measure of efficiency for the selection of a seedset S. Under a stochastic diffusion process (e.g.. independent cascade, linear threshold model, etc.), ( is a random variable, for which we are interested in the expected value and distribution. For a particular outreach, we define the final configuration at the end of a diffusion process as follows.
Definition 2.1 (Final configuration) For network G with two commumities (Ci)tet2) and a seedset S, we let z4, E [2], denote the fraction of nodes in each community in the outreach (S). The final configuration the tuple (#1, 322).
In many definitions in the literature, fairness is operationalized by measuring the expected value of the final configuration, where the expectation is taken over the diffusion process. In particular, the equity definition introduced by Stoica et al. [23], Junaid et al. [9] checks that the expected value of the proportions of each group reached in the outreach is the same for all groups. For a formal definition of equity and other fairness definitions in the literature, see Appendix A. We will show that relying solely on the expected value leads largely unfair outcomes to be classified as fair.
3 Mutual Fairness via Optimal Transport
In contrast to the literature, we propose using the joint outreach probability distribution, instead of its marginals, to capture simultaneous outreach between the two groups and therefore address questions like (i) When group receives the information, will group 2 also receive it? (ii) Even if the two groups have the same marginal outreach probability distributions will the final configuration always be fair? We argue that capturing these aspects is crucial for understanding and assessing fairness, as shown in the motivating example below.
Notation. We collect the output of the cnoemmttion-spreddiiin process via probability distribution Y E P[ 1] x [0, 1l) over all possible final configurations. Informally, 7(21, x22) is the probability that fraction x of group receives the information and a fraction 22 of group 2 receives the information; e.g., 70.33 represents the probability that 30% of group 1 and 40% of group 2 receive the information. We can marginalize 7 to obtain the outreach probability distributions associated with each group: i.e., μ1 E P(O0, 1]) and #2 E P(OO, 1)). Informally, we can write #1 (z1) = En,
my (2), As in the example above, pa (0.3) the probability that 30% of group i receives the information.
Motivating Example. Consider the SIM problem with nodes belonging to two groups, Ci and C2. each group having the outreach probability distribution μ4; _ + f01, E (1,2). with dū represent- ing the delta distribution at & E [0, 1]. That is, in 50% of the cases all members in group receive the information (i.e., get 2; 1.0) and in 50% of the cases no one in group receives the information (i.e., we get x; = 0.0). It is therefore tempting to say that this setting is fair since #1 and fl2 coincide and therefore share the same expected value. We argue that this information does not suffice to claim fairness. Indeed, consider the two following probability distributions over the final configurations:
Ta- = 0.5 -5.00) + 0.5 -(111);
7h = 0.25 0(0.0) + 0.25 5(1.1) + 0.25 &(..1) + 0.25 6(1,0))
with )(,,)), representing the delta distribution at (i.j) E [0, 1j.. Interestingly. both 7, and 76 are "compatible" with μn and #2: If we compute their marginals, we obtain μn and #22 However, To and 76 encode two fundamentally different final configurations. In Ya the percentage of members
3

---

(g1 y2)
% outreach group 2
% outreaa group 2
2 2 22 91, 92)
(01,
% outreach group
% outreach group 1
Figure 1: Illustration of the (7a:7b) example.
The transportation cost measures the length of the solid segment; shifts along the diag- onal (dotted) are not considered for faimess and are only relevant for efficiency.
Figure 2:
of group 1 who get the information always coincides with the percentage of people of group Con- versely, in 76, more outcomes are possible: in particular, there is probability of 0.25 + 0.25 = 0.5 that all members of one group receive the information and no member of the other group receives it (see Fig. 1). Thus, from a fairness perspective, % and % encode very different outcomes. We therefore argue that fairness metric should be expressed terms of joint probability distribution y, and not solely based on its marginals μl and μ2, as commonly done in the literature [23, 9].
3.1 A Fairness Metric Based on Optimal Transport
Our motivating example prompts to reason about fairness in terms of the joint probability measure y. instead of its marginal distributions μ4 and J/2. Since 7 is a probability distribution (over all possible final configurations), we can quantify fairness by computing its "distance" from an "ideal" reference distribution > along the diagonal, capturing the ideal situation in which both groups receive the information in the same proportion. We do so by using tools from optimal transport.
Background in optimal transport. For a given (continuous) transportation cost e ((0, 1]x (0, 1))x ((0, 1] x [0, 1]) + Rzo, the optimal transport discrepancy between two probability distributions Ta P([O, 1] x [0, 1J) and 76 P([0, 1]
[0, 11) is defined
WolTa:
min B(rr [c((21, (2))], =Ell(T.77))
(1)
where II()a; ()6 is the set of probability distributions over (fo. 1] x [0, 1)) (f0, 1] J0, 1]) that the first marginal is "/a and the second marginal is %6- Intuitively, the optimal transport problem quantifies the minimum transportation cost morph Ya into 7 when transporting unit of mass from (2), x22) to (y), 32) costs c((2) 22), (1h V2)). The optimization variable и is called transportation plan and ((11) W2), ); (y1, 32)) indicates the amount of mass at (x1, displaced (2), Thus, its first marginal has to be 7/a (21, (that is, (01, X2) has to be transported to some (y1, (2]) and its second marginal must be (B 322) (that is, the mass at (y1, U2) has to arrive from some x2)). If the transportation cost is chosen be p 2 power of distance d, then (War (:-)))))) )) is distance on the space of probability distributions. When the probability distributions are discrete (or the space [0, 1] discretized), the transportation problem (1) is finite-dimensional linear program and can therefore be solved efficiently [15].
Our proposed fairness metric. To operationalize the optimal transport problem (I), we therefore need to define (i) transportation cost and (ii) reference distribution y To define the transportation cost, we start with the following two considerations. First, moving mass along the diagonal should have zero cost, as it does not affect faimess but only efficiency (the proportion of population reached respective groups). Second, moving mass orthogonally towards the diagonal should come at a price, since the difference in group proportion outreach between groups and 2 decreases. We quantify this price as the Fuclidean distance. This illustrated in Fig. 2, which shows how the joint distribution captures unfairness, by depicting the percentage outreach in each group on each axis;

---

thus, the diagonal represents a "fair" line, where the probability of reaching a particular outreach percentage is the same for both groups.
These two insights suggest decomposing the distance between the initial configuration (21, F2) (e.g., belonging %aa) and (y1, 1/2 (e.g., belonging 7t)) into components: capturing efficiency and the other one being the fairness component (see Fig. 2). Since the aim of our metric is to measure fairness, we therefore obtain the transportation cost
V2 ((2g - -21) (v2 31 vn)l. 2
c((a11 (11, 32)) = []= 22, V1, v2) - x2)1l =
(2)
where 2(11, 22, 1/1, 1/2 the point indicated in green in Fig. and ||-|| is the standard Euclidean norm. Thus, the "fairess distance" between two distributions To and "6 can be readily quantified by Wo(To: 70). Since moving mass along the diagonal is free, we quantify the fairness of given as its "fairness distance" from the "ideal" distribution 7* = 6(1,1), which represents the case where all members of both groups receive the information. We can now formally introduce our proposed fairness metric.
Definition 3.1 (Mutual Fairness) Given network with communities (Ci) a SIM algorithm is said to mutually fair if the algorithm propagation is such that it maximizes
FAIRNESS(1) == = (0--22())))))
where Wo(7,7") is the optimal transport discrepancy, defined with the transportation cost (2),
between the probability distribution Y and the desired probability distribution "/ defined as in (1).
The mutual fairness from Definition 3.1 can seen as a normalized expression of We(1, ?²) to
contain its values in [0, 1]. Indeed, its lowest value is 0 and it is achieved with y ō(o, for which is W Wo(n, ?") 1; its largest value is I and it is achieved with y y", for which Wa(?", 0. Since y a delta distribution, we can solve the optimal transport problem (1) closed form to
FAIRNESS(?) = v2Wc(7,7") = (0 22)
1 - 10 x22
which reduces to FAIRNESS(7)) = 1 + Σm | - x2, when the distribution & is empirical with N samples { 22, x2,)) hE(N In particular, our faimess metric can also be interpreted in terms of the average distance between the outreach proportions within the two groups.
Discussion. note that, while we considered two groups in the aforementioned definition, our methodology readily extends the setting with groups. We present this extension in Appendix B. Sec- ond, since moving mass "diagonally" free, any distribution 7 supported on the diagonal yields the same fairesss metrie. In practice, it is often not the tion, and the best one could hope for is to project y onto the diagonal; since moving along the diagonal is free, the fairness cost is the same whether the ideal distribution is that projection y Moreover, it is easy to see that the "fairness distance" " is symmetric, namely Wa(Ya: %)) = Wa( 7a). Finally, definition readily extends any other distance function besides the standard Fuclidean metric.
that all network members receive the informa-
Back to the motivating example. Armed with definition of fairness that captures the nature of a diffusion process, we now revisit the motivating example Fig. To start, we evaluate the "fairness distance" between "a and yss
We Wa(Ta: 76) = 22
V2
/2
2
4
which amounts to the cost of transporting the points (0,1) and (1, each with weight 1/4, to the diagonal. Notably, in contrast to simply computing the expected outreach of each group, our fairnsss metric distinguishes the two outcomes. Similarly, we can easily compute the faimess metrie: (AI)NESS(TA) = and FAIRNESS(7E) = 0.5. In particular, 7a achieves the highest fairness score. Indeed, its outcome will always be fair. Instead, FAIRNESS(78) achieves lower fairness score, capturing the fact that 50% of the cases the outcome is perfectly fair, while in the remaining 50% it is largely unfair.
5

---

3.2 Mutual Fairness in Practice
We now investigate the use of our newly defined fairness metric across a variety of real-world datasets: Add Health (AH), Antelope Valley variants 0 to 23 (V-((--33) [26], APS Physics (APS) [13]. Deezer (DZ) [19], High School Gender (HS) [14]. Indian Villages (IV) [1], and Instagram (INS) [22]. Each dataset contains a social network with a chosen demographie partitioning the population into two groups (see Appendix C for details). We load the datasets as graphs G(V, E). We then select a seedset S of size 2-90 (depending on the dataset) using the following heuristics: two group-agnostic seed selection strategies as our baselines, namely degree centrality (bas_d), and greedy (bas_g), proposed by Kempe al. [11]. In addition, we implement two fair seed selection heuristics based on the equity metric, namely degree-central fair heuristic (hrt_d), _), and greedy fair heuristic (hrt_g) proposed by Stoica al. [23]. To model the information spread, we use the Independent Cascade model (IC) for the diffusion of information [11] with a probability p E [0, 1] for all edges. This process, being stochastic, simulated R times in Monte Carlo sampling process to achieve R. final configurations (Definition 2.1) plotted together as a joint outreach distribution, in Fig. 3. Then we apply our distribution-awarr notion of fairness from Section 3.1, mutual fairness. We keep R = 1, 000 throughout, but explore several values in p. |S| (mentioned per experiment in the figures below) and exhaustively recorded with other hyperparameters in Appendix D. All details related to computational resources and development environment are available in Appendix G. The code for all our numerical experiments is available at https: //ggttttt.../..//////// com www./ccoo//////ec.coo.oooooo...e aicolas as www.laattttttaaaeaaaa
sim-ot.
Are the outcomes fair? As a first experiment, we study the joint outreach probability distribution for different datasets. We identify four qualitatively different outcomes, shown in Fig. 3 for a few of the datasets. Additional experiments with different propagation probability and seed selection strategies can be found in Appendix D. Fig. 3a is obtained on AH with bas selection strategy and = 0.5. |S] = 10. We note how the joint outreach distribution is almost concentrated on the top right of the plane, i.e., the outcome is almost deterministic and highly fair and efficient. In turn, this trivializes both the expected value in the equity metric and the cost in the mutual fairness metric in Definition 3.1, which therefore essentially boils down to comparing the almost deterministic outreach fraction within each group. In these cases, our fairness metric does not provide additional insights. Such deterministic outcomes are typical of degree or greedy seedset outreach in dense graphs, such as AH, DZ, INS (refer to Appendix D), with extreme probability of conduction (p 2 0.5 or + 0), and cross-group interconnectivity (see Table in Appendix C). For moderate p (e.g.. 0.1), the outreach probability distribution is concentrated along the diagonal (Fig. 3b). Thus, both the equity metric and our fairness measure are maximal. Nonetheless, our fairness metric provides additional insights: not only does the expected outreach within each group coincide, but also the outreach at every realization coincides (see the example in Section 3). Thus, our fairness metric provides stronger certificate of fairness. As before, the same applies to AH, DZ, INS (see Appendix D). Intuitively, high cross-group interconnectivity in a dense graph already ensures fairness. Additionally, extreme p values ensure deterministic outreach (either the information dies out at the seedset, or reaches everyone in the population). When propagation happens with moderate propagation probabilities, p, outreach appears as in Fig. 3b. Fig. 3c represents APS for its hrt_g seedset outreach and 0.3, |S| = 6. Here, we observe a highly stochastic outcome, with many realizations for which almost no member of one group receives the information. Note that the phenomenon observed in Fig. 3c is the same as the one captured by our motivating example. We argue such an outcome should not be classified as fair, despite the expected value of the proportions being similar. Finally, Fig. 3d shows the AV O dataset with = 0.3, |S| = 4, and bas_ selection strategy. We observe a more stochastic outreach compared Fig. 3b with variance spread along, but not the diagonal, with small bias towards one group. Also in this case, both the equity and mutual fairness metrics characterize this outcome as fair, but mutual fairness is more informative as it requires outcomes be fair at each realization.
The impact of the conduction probability. As a second experiment, we investigate the difference between mutual fairness and equity (difference in the expected value of the proportions), as function of the conduction probability p. We consider the IV dataset as case study and select seeds using bas_g We show our results in Fig. 4. Our mutual fairness metric in Definition 3.1 shows a fundamentally different trend compared to the equity metric from Definition A.3. Importantly, for p E (0, 0.5), both metrics have an opposite trend: equity fairness increases to some extent whereas our metric suggests a significant fall in fairness in this region. For p E (0.5, 0.7), there is a decrease in equity fairness, while our faimesss evaluation remains relatively constant. We notice similar trends

---

AH, = 0.5
AR, p = 0.1
APS. p =
AV_ p 0.3
bas_g. [8| 10
bas_g. [S] = 20
brt_g. |S| =
bas bas_g. [S] =4
Eroup Z
outreach group 2
Re outteach group
0.4
26 outreach group
0.4
aulrnncn 26
0.2
% outreach group
% outreach group I
% outreach group
% outreach group
(a)
(b)
(c)
(d)
Figure 3: Joint outreach probability distribution for different datasets, different propagation probabili- ties p. and seedsets cardinalities (S).
bas_g.
Equity (I-diff. in outreach)
Mutual faimess
0.95
0.95
0.9
0.9
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Conduction Probability
Figure 4: Mutual fairness (left, red) and equity (right, blue) for the IV dataset p varies in [0, 1].
for both metries only for (0.8, 1.0). The significant difference in the trend of the two metrics confirms our previous finding that mutual fairness is more informative than the equity metric and that the equity metric fails to adequately capture changes in fairness, see Sections 3.1 and 3.2. For more experiments on other datasets, we refer to Appendix D.2.
3.3 Trading off Fairness and Efficiency
To construct our faimess metric, we completely discarded the efficiency of the final configuration. For instance, the "fairness distance" between configuration whereby no agent receives the information (i.e., = ((,,)) and the "ideal" configuration whereby everyone receives the information (i.e., 7²) is zero, as both probability distributions lay on the diagonal. As such, the fairness score of o(0.0) 1 and therefore maximal. Thus, in practice, one seeks fairness- -irress-efficiency tradeoff.
In setting, define the transportation cost as a weighted sum the "diagonal distance" (measuring the difference in efficiency, dotted segment in Fig. and the "orthogonal distance" (measuring the difference in fairness, solid segment in Fig. 2). Formally, for given weight 3 2 0, the transportation cost reads
easily introduce the tradeoff in the transportation cost (2). Specifically,
ca((a x2), (y), 32)) = [1]= 22, 3/, v2) (x), + (1 - =B)1[= 42, 21, v1, 92) (y1 y2)l
2 3 (x2 m1) - (12 ) + - V2 (x) + (y1 + 22)l. (3)
We refer to Fig. 5 for heatmap of cg. In particular, for 3 = 1, we recover the transportation cost (2); for one optimizes for efficiency, and the 3-fairness collapses in the classical influence maximization problem. We can then proceed as in Section 3. The "3-faimmss--fffciinne distance" between 7a and n Wey (Tay 76) and the 3-fairness metrie can be then defined as follows.
Definition 3.2 (8- FaFiiiness)) Consider network with groups C1. C2, SIM algorithm is said to be 8-fair if the algorithm propagation is such that maximizes
/2
3 FAIRNESS(7) = max 2 W (7))",
(4)
7

---

_ = 0.33
= 0.66
8
% outreach group 2
% outreach group 2
outreach group
66 outreach group
66 outreach group
% outreach group 1
% outreach group
% outreach group
Figure 5: Cost of transporting point (2)) to the "ideal" point (1, (i.e., everyone receives the information) for various values of /3 (i.e., we plot (I), (2) + ca cx((T1, 1))). Yellow denotes low transportation cost, whereas dark blue denotes a large cost. cost.
with We, (*) defined as in (1) with transportation cost as in (3) and ideal distribution y =(1.1)-
The terms and v max 2 23} in (4) ensure that the metric is non-negative and in [0, 1].
Again, the optimal transport problem can be solved in closed form, which yields
B|xr x2l + (1 3) [1
3 FAIRNESS(7) Beeeee))m
max (1.2 2 2
In particular, for 3 = 1, we recover the mutual fairness FAIRNESS(7) in Definition 3.1 and for 3 = 0
obtain the efficiency metric (() [xx t.2g
2
4 Improving Fairness
4.1 Fairness-promoting Seed-selection Algorithm
Armed with novel fairness metric, B-FAIRNESS, now design iterative seed-selection algorithm, which we call Stochastic Seedset Selection Descent (S3D), that strategically selects seeds taking into account all communities simultaneously. The pseudo-code is summarized in Algorithm 1. For its motivation and details, refer to Appendix E. For given initial seedset, our algorithm explores new seeds and evaluates them on the seficiency-fairness metric 3 FFFIIRNSSS as (4) for desired value of the fairness-efficiency tradeoff parameter 3 (S3D STEP () in Appendix E), to decide if the new seedset becomes candidate for the optimized seedset. These seeds are searched for by iteratively sampling stochastically reachable nodes, up to fixed depth, taken as a fraction of the graph diameter, from the current seedset (SEEDSET ( Appendix E) while making sure they contribute to non-overlapping outreach (Algorithm 1::6-8). To avoid local minima of the generally non-convex objective, the procedure allows for visiting inferior seedsets on 3-FAIRNESS or even selecting completely random ones on rare occasions (Algorithm 1:: 1::12-18) using Metropolis Sampling [18]. Otherwise, a high 3 FAIRNESS encourages opting for the new seedset with high probability. Finally, we revisit all the seedset candidates collected so far and pick the one with the largest B-FAIRNESS as the optimal seedset. For a sparse graph G(V, E). with E = O(V), choosing [S] seeds, averaging over R realizations to approximate outreach via Monte-Carlo sampling and exploring candidates using $3D_STER suggests a total running time upper bound of (( (see Appendix E for details). In practice, & E [500, 1000), R 1000 for S [2, 100] works well for all datasets.
4.2 Real-world Data
Are the outcomes more fair? We test our algorithm across variety of datasets (Appendix C) against our baselines (bas_d, bas_g). We initialize the S3D algorithm with the two baseline seedsets and hence include results from two separately optimized seedsets, S3D_d. S3D_g. Our results are shown in Fig. 6. Informally, we observe that our seed-selection mechanism "moves" the probability mass of the joint outreach probability distribution towards the diagonal, which ultimately increases the fairness the resulting configuration. the same time, efficiency either increases as well or suffers only small decrease, investigate more in detail in next experiment. Generally, datasets

---

Algorithm Stochastic Seedset Selection Descent
Input: Social Graph G(Va, Ea), initial seed set So. fairness weight, e-tolerance Output: Optimal seedset S*
1: S O, + 50
D initial collection of candidates, running seedset
2: for iterations do
D configurable
3: Vs < nodes reachable from S via cascade, using SEEDSET REACH routine
4: S'
+ 0
5:
for |S| iterations do
searching nearby states, Vsa, to get S' (Appendix E.3)
6:
S" + U fo} v~ Vs
7:
Vgi nodes reachable from S' in fixed horizon, using SEEDSET REACH expected potential energy defined on f-fairness
8:
Vg + Va Vss
9:
Es t BETA SAANAFAAINNSSSSSSS 3)
10:
És + BETA FAIRNESS(S",
11:
Pnecept min(1, eBs ees--By Es!
S" acceptance on energy minimization P Metropolis sampling get better seedset
12:
if (pacceep) then
S S
14:
else
if x B(() then
b for some small constant
16:
5* + (uil Vg
D random seedset
17:
else
18:
S+ S
> retain existing choice
19:
SU-S
S+
b for next iteration
21:
S S
BETA FAIT_FFAINNESSSS, () is maximum
via ITERATE
22:
return S*
APS, p 0.3
IV. 0.1
HS, p 0.01
HS, 0.5
bas_d, [S| 6,8 = 0.8
bas_g. [S] 2,
0.8
bas_g.
[S| 10, 8 = 0.5
bas_d, |S| = 6, = 0.8
0.6
0.2
0.2
2 damnn d
%: outreach group
outreach group
% outreach group
0.1
0.1
&
0.6
0.2
0.1
0.8
% outreach group
outreach group
outreach group
% outrcach group (d)
(a)
(b)
(c)
Figure 6: Demonstrate S3D (red) improvement over its label-blind baseline counter-pan part initializations (blue) for several datasets, propagation probabilities p, seed set cardinalities |S] and fairness- -afmess-efficiencyy tradeoffs B. Fig. 6d provides the strongest evidence that, besides improving in fairness, our strategy also be more efficient, from 83.1% 87.9%.
with high cross-group connections (AH, DZ, INS) yield moderately fair outreach with label-blind seed selection. Similarly, for datasets with low cross-group connections (APS) a label-blind strategy, in order to maximize efficiency, selects diverse population of seeds from which all communities are reached. Therefore, label-blind algorithms work similarly to S3D. other moderate cases (AV, HS, IV), instead, we observe significant improvements of S3D over label-blind strategies.
Classification of seed-selection algorithms. In our final experiments, we compare several algorithms along with ours in terms of efficiency and mutual fairness across various datasets (see Appendix C). We consider the following algorithms: bas_d d, bas_g, their fair heuristic counterparts, hrt_d, d, hrt_g, against our S3D_d, S3D_g. 23D_g. initialized greedy and degree centrality baseline seeds, respectively. We show our results in Fig. 7, S3D achieves in almost all cases the highest

---

APS. p 0.3 |S] = 6, 0.8
AV_O, P
HS, p = 0.01
HS, p = 0.5
[5] 4, = 0.8
||] 10, /
0.5
[|| 6,
0.8
Mutual faimess
Mutual faireess
Mutual faimess
0.98
Mutual faimess
0.98
0.95
0.94
0.94
0.02
0.85
0.8
0.52 0.
Efficiency
Efficiency
Efficiency
Efficiency
Figure 7: S3D trade-off and improvement against other label-aware and label-blind algorithms for several datasets, propagation probabilities p, seed set cardinalities |.] and fairness-efficieng tradeoffis
3. Filled markers refer to greedy-based algorithms: markers refer to degree- -ased algorithms: bas_d, S3D_d and hrt For statistical bounds, we refer to Appendix F.
bas_g,
S3D_g, and hrt_g. Empty
fairness score (y-axis) and generally slightly lower efficiency score (z-axis), compared to others. Thus, seed-selection mechanism leads fairer outcomes with only minor decrease in efficiency.
The impact of the network topology. To conclude, we discuss the impact of the network topology. In particular, when the conduction probability moderate, network topology starts playing role, mainly through the number of cross-grout edges (CE):
CH% is small (~ 5%, APS): Such datasets encode group interaction information in the edges them- selves, that is, an edge likely means nodes belong to the same group. In such cases, baseline greedy algorithms (bas_g) already perform well as they rely only edge connectivity. In such circumstances, S3D does not significantly improve on their selection, both in efficiency and fairness.
CE% is balanced (40-50%, HS, AH): These datasets reflect that groups interact well across each other and so any seedset selection largely ends up a fair outreach. Since bas_ already has proven near-optimal efficiency guarantees, it is unlikely that S3D performs significantly better than bas
CE% moderate (5-30%, (datasets 0, 2, 16. 20), IV): These are the non-trivial cases not covered above. Here bas can not reliably leverage the existence of edges into group information. Hence, S3D usually outperforms the baseline, achieving similar efficiency scores while significantly improving fairesss.
CE% is high (>50%): The case where nodes interact more across groups than in their group was never observed. However, as long as the existence of edges does not reliably signal group information, expect S3D to perform well based
similar analysis.
Moderate outreach in dense graphs (INS, DZ): For graphs where |E] substantially exceeds [V], the outreach variance across sample sub-graphs is too low to be captured in the discretized space experimented (100 x 100 units in [0, _J3), , even for moderate p. This leads to single-poin concentrated joint-distribution plots, all of them leading to the same FAIRNESS.
Conclusions and Limitations
Conclusions. We propose new fairness metric, called mutual fairness, in the context of SIM. Mutual faimess draws on optimal transport and captures various faimess-related aspects (e.g.. when members of group receive the information will members of group 2 receive it?) that obscure the fairness metrics in the literature. We also leverage our novel fairness metric to design a new seed selection strategy that tradeoffs fairness and efficiency. Across various real datasets, our algorithm yields superior fairness with a minor decrease (and in some cases even an increase) in efficiency.
Limitations. Our proposed algorithm, S3D, essentially a random combinatorial search in graph defining the social network. As such, its performance will generally depend on the quality of the seedset initialization. Moreover, there is no guaranteed bound on the number of iterations needed in S3D to achieve a desired level of fairness. Both aspects can be limiting in real-world applications.
10

---

Acknowledgments and Disclosure of Funding
We thank the reviewers for their constructive suggestions. This work was supported as part of NCCR Automation, National Centre of Competence in Research, funded by the Swiss National Science Foundation (grant number 51NF40 2211155.. A.-A. S. acknowledges support from the Tübingen Al Center.
References
[1]
Abhijit Banerjee, Arun G Chandrasekhar, Esther Duflo, and Matthew O Jackson. The diffusion of microfinance. Science, 541(6144); (6:144))12364988 1236498, 2013.
[2] Emily Black, Samuel Yeom, and Matt Fredrikson. Fliptest: fairness testing via optimal transport. Proceedings of the 2020 Conference on Fairness, Accountabilityy and Transparency 20), pages 111-121, 2020.
[3] Wei Chen, Wei Lu, and Ning Zhang. Time-critical influence maximization in social net- works with time-delayed diffusion process. In Proceedings of AAAI Conference of Artificial Intelligence, 26(1):1-7, 2012.
[4] Silvia Chiappa, Ray Jiang, Tom Stepleton, Aldo Pacchiano, Heinrich Jiang, and John Aslanides. A general approach to fairness with optimal transport. Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency (FAT'20), 20), pages 3633-3640, 2020.
[5] Tang Fangshuang, Qi Liu, Zhu Hengshu, Chen Enhong, and Feida Zhu. Diversified social influence maximization. 2014 IEEE/ACM International Conference Advances in Social Networks Analysis and Mining (ASONAM 2014), pages 455-459, 2014.
[6] Golnoosh Farnadi, Behrouz Babaki, and Michel Gendreau. A unifying framework for fairness- aware influence maximization. International World Wide Web Conference 2020, pages 714-722, 2020.
[7] Benjamin Fish, Ashkan Bashardoust, Danah Boyd, Sorelle Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. Gaps in information access in social networks? International World Wide Web Conference 2019, San Francisco, USA, pages 480-490 2020.
[8] Arie Hagberg, Pieter Swart, and Daniel Chult. Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th Python in Science Conference, 01 2008.
[9] Ali Junaid, Babaei Mahmoudreza, Abhijnan Chakraborty, Baharan Mirzasoleiman, Krishna P. Gummadi, and Adish Singla. On the fairness of time-critical influence maximization in social network. IEEE Transaction knowledge and data engineering, 35(3):480-490) 2023.
[10] Fariba Karimi, Mathieu Génois, Claudia Wagner, Philipp Singer, and Markus Strohmaier. Homophily influences ranking of minorities in social networks. Scientific reports, 8(1):11077, 2018.
[11] David Kempe, Jon Kleinberg, and Eva Tardos. Maximizing the spread of influence through a social network. Proceedingy of the 9th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 137-146, 2003.
[12] David Kempe, Jon Kleinberg, and Éva Tardos. Influential nodes in a diffusion model for social networks. In Automata, Languages and Programming: 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11 11-15, 2005. Proceedings 32, pages 1127-1138. Springer, 2005.
[13] Fun Lee, Fariha Karimi, Claudia Wagner, Hang-Hyun Jo, Markus Strohmaier, and Mirta Galesic. Homophily and minority-group size explain perception biases in social networks. Nature human behaviour, 3(10):0078-1083 2019.
[14] Rossana Mastrandrea, Julie Fournet, and Alain Barrat. Contact patterns in high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys. PloS one, 1019))70 2015.

---

[15] Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends Machine Learning. 11(5-6)335-607, 2019.
[16] 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 Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11630-11638, 2021.
[17] Matthew Richardson and Pedro Domingos. Mining knowledge-sharing sites for viral marketing. In Proceedings of 8th International Conference on Knowledge, Discovery and Data Mining, pages 61-70, 2002.
[18] Christian Robert, George Casella, Christian P Robert, and George Casella. The metropo- lis hastings algorithm. Monte Carlo statistical methods, pages 267-320, 2004.
[19] Benedek Rozemberczki and Rik Sarkar. Characteristic functions on graphs: Birds of feather, from statistical descriptors to parametric models. In Proceedings of the 29th ACM international conference information & knowledge management, pages 1325-1334, 2020.
[20] Yves Rychener, Bahar Taskesen, and Daniel Kuhn. Metrizing fairness. arXiv:2205. 2022.
arXiv preprint
[21] Nian Si, Karthyek Murthy, Jose Blanchet, and Viet Anh Nguyen. Testing group fairness via optimal transport projections. Proceedings of the 38th International Conference Machine Learning, pages 9649-9659, 2021.
[22] Ana-Andreea Stoica, Christopher Riederer, and Augustin Chaintreau. Algorithmic glass ceiling in social networks: The effects of social recommendations on network diversity. In Proceedings of the 2018 World Wide Web Conference, pages 923-932, 2018.
[23] Ana-Andreea Stoica, Jessy Xinyi Han, and Augustin Chaintreau. Seeding network influence in biased networks and the benefits of diversity. Pruceedings of The Web Conference 2020, pages 2089-2098, 2020.
[24] Bahar Taskesen, Jose Blanchet, Daniel Kuhn, and Viet Anh Nguyen. A statistical test for probabilistic fairness. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, pages 648-665, 2021.
[25] Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. faimmssairness in influence maximization. Proceedings of the Twenty-Eihhth International Joint Conference on Artificial Intelligence (IJCAI-19), pages 5997-6005, 2018
[26] Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, and Yair Zick. Group-fairness in influence maximization. Proceedings of the Twenty-Fight International Joint Conference on Artificial Intelligence (IJCAI-19), pages 5997-6005, 2019.
[27] Thomas W. Valente and Patchareeya Pumpuang. Identifying opinion leaders to promote behaviour change. Health, Education & Behaviour, 34(6):881-896. 2007.
[28] Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[29] Meike Zehlike, Alex Loosley, Håkan Jonsson, Emil Wiedemann, and Philipp Hacker. Beyond incompatibility: Trade-offs between mutually exclusive faimess criteria in machine learning and law. arXiv preprint arXiv:2212.0000 004669, 2022.
[30] Jianming Zhu, Smita Ghosh, and Weili Wu. Group influence maximization problem in social networks. IEEE Transactions on Computational Social Sciences, 6(6): (66:1156-11166 164, 2019.
12

---

A Existing Fairness Metrics
Definition A.1 (Expected outreach ratio) Given a network with communittess Ci.... Cno the SIM algorithm expected outreach ratio in C. Is, is the expected ratio of nodes reached in Cú namely
BiK reached lo C.Hl
E mI,...,m..
[ca]
Definition A.2 (Equality [23]) Given the groups C1s..., Cn, configuration is said be equal, if the SIM algorithm chooses a seed set S in way such that the proportion of all communities in the seed set the same, namely
Ell E SI
El E HiHll
Vi,j E ml.
|C|
|cyl
The notion of equality focuses the fair allocation of seeds the groups proportional the size of the group within the population. This notion of fairness applies, for example, in the context of advertising companies that aim having fair distribution resources among groups.
Definition A.3 (Equity [23]) Given a network with communities CI...., C.o SIM algorithm that selects seedset said be equitable the algorithm propagation reaches all communities in balanced way, i.e. E, 3, for all i. {1..... m.
The notion of equity focuses on the outcome the diffusion process, e-g. independent cascade, linear threshold model and it is suitable in contexts in which one aims to reach a diverse population in calibrated way.
Definition A.4 (Max-min fairness [6]) Given the groups C1,...,Cm the max-min fairness criterion maximizes the minimum expected outreach ratio among all groups, namely max (I..mm) Ti.
The goal of the maxmin fairesss is to minimize the gap among different groups in the outreach. The SIM problem under maxmin constraints has been investigated in [6, 7, 30J.
Definition A.5 (Diversity [6]) Given the groups Ci...., C.u let k2 [k- [. where le is the pre-specified total seed budget. Let F (C,) = ( T.. A configuration is said to be diverse if for each i {l...., m) it holds 2; > क (Ct), where ã, refers the expected outreach ratio in C, obtained from the seed set S, with S = k.
The notion of diversity ensures that each group receives influence at least equal to their internal spread of influence. The SIM problem under diversity constraints has been investigated in [6, 25).
B Extension to Multiple Groups
In this section, we extend our definitions of mutual fairness and 3-fairness to the setting of m groups. To do so, we first notice that, in the case of groups, the outreach distribution probability distribution y on the hypercube [0, 1]m"; i.c., now lives in P P(00,1] 1)
We start with the definition of mutual fairness. We proceed as in Section 3.1 and define mutual faireess via optimal transport, which, in turn, requires defining reference distribution and a transportation cost. The reference distribution is again the "ideal" distribution case in which all members of all groups receive the information. As for the transportation cost, suffices generalize the transportation cost (2) to dimensional space. Specifically, it can be
6 d(.....)) which encodes the
defined as the distance between any given point (I1,..., Rm) E [0, 11 in the hypercube and the diagonal line. For this, let
20 Fm) = argmin [[ z|1 == vE(o11
21 + ... + Im (1....,1)
13

---

be the closest point to .mm on the diagonal. Then, the transportation cost can be defined as in (2) and the fairness metric reads
FAIRNESS(?)
a (m Joyy
(............................... (011 Fm...
anlEE Joy
min 2c(0,1]
(II1, Fmm) - (Z....., e]|l
where the constant >> 0 is again chosen so that FAIRNESS(7) is between 0 and 1. Note that in the case of two groups, we have 2 (a1 + x2) and
v2 x2/
min [I Fm) ( 2) ==(0,1]
(,,...,))
41
2
which is precisely the mutual fairness of Definition 3.1.
We now turn our attention to f-fairness. We can proceed analogously and obtain
8 FAIRNESS(7) = - oB
-B (.. 101 Fmm) (f Fm)ll
+ +(1 - [)) 3m) - (1,..., .....,,,]I],, 1)]],
where a > 0 is again chosen to normalize the metric. Again, in the case of two groups, we have (I) + 22) and so
8 FAIRNESS()) =1 o. (1 3 v2 x1 x2l (1 33 v2 x1 D2 2 2
V2
which coincides with Definition 3.2.
We conclude with two remarks on this extension to m groups. First, as the case of two groups, there no need numerically solve optimal transport problems, as we provide a closed-form expression for the optimal transport problems. Second, we highlight that our extension to m groups does not resort to the so-called multi-marginal optimal transport problem, which might cause exponential complexity in the dimensionality.
C Description and Properties of Datasets
To associate the notion of fairness developed in Sections 3.1 and 3.3 with the datasets and the outcomes from experiments in Sections 3.2 and 4.2, we summarize the dataset statistics in Table 1. Minority % is calculated as the percentage of the minority group nodes in the entire population. Fraction of Cross Edges evaluates heterophily in the dataset, by calculating the fraction of edges that connect different groups. A higher value means a more heterophilic network, whereas a lower value means more homophilic network.
Add Health (AH). The Add Health dataset consists of social network of students in schools and relation between them represented by whether they nominated each other in the Add Health surveys. We select school at random with 1, 997 students and use race as the sensitive attribute (white and non-white),?
Antelope Valley (AV), [26]. We choose 4 random networks among the 24 available in the Antelope Valley dataset to compare our fairness-improving algorithm, S3D, against [26], which worked on the same dataset. We also run our baselines and other fair seed selection heuristics from [23] on these datasets to get fair comparison. The two sensitive attribute groups are male and female, self-reported the dataset with binary attributes.
"The Add Health project is funded by grant P01 HD31921 (Harris) from the Eunice Kennedy Shriver National Institute of Child Health and Human Development (NICHD). with cooperative funding from 23 other federal agencies and foundations. Add Health currently directed by Robert Hummer and funded by the National Institute on Aging cooperative agreements U01 AG071448 (Hummer) and 101AA001450 (Aiello and Hummer) at the University of North Carolina at Chapel Hill. Add Health was designed by J. Richard Udry. Peter S. Bearman, and Kathleen Mullan Harris the University of North Carolina at Chapel Hill.
14

---

Dataset
# Nodes
Edges
Avg. Degree
Diameter
Minority %
Frac. Cross Edges
AH
1997
8523
8.54
10
34.6
0.452
AV_0
500
969
3,87
12
49
0,189
AV 2
500
954
3.81
14
49.6
0.183
AV AV_16
500
949
3.8
13
47.6
0.210
AV_20
500
959
3.84
15
48.4
0.198
APS
1281
3064
4.78
31.8
0.056
DZ
18442
46172
5.00
25
44.4
0.476
HS
133
401
6.03
10
40.6
0.394
IV
90
238
5.29
13
26.7
0.265
INS
553628
652830
2.36
16
45.6
0.417
Table I: Summary statistics of datasets used.
APS Physics (APS), [13]. The APS citation network contains 1, 281 nodes, representing papers written in two main topics: Classical Statistical Mechanics (CSM), constituting 31.8% of the papers, and Quantum Statistical Mechanics (QSM), accounting for the rest. As Lee et al. [13] analyze, the dataset has high homophily, meaning that each subfield cites more papers in its field than in the other field. For simplicity, we use only the largest connected component in the full dataset (component stats in 1) between the groups. for this study.
Deezer (DZ), [19]. A social network from Europe with 18, 442 nodes, where each node has self-reported attributed gender (male female). Men are the minority (44.3%) and women the majority (55.6%). The dataset has moderate homophily.
High School (HS), [14]. A high school friendship network collected from Mastrandrea al. [14], with 133 nodes in its main connected component represented by students who self-identify as male female. The majority are female (60%), and the network homophilic.
Indian Villages (IV), [1]. The dataset contains different demographic attributes for the individual networks and the household networks collected in 77 Indian villages, from which we select Mother- tongue (Telugu or Kannada) as the sensitive attribute. We note that most villages contain a majority mother tongue, either Telugu or Kannada. We pick a random village with 90 individuals for our study.
Instagram (INS), [22]. An interaction network from Instagram containing 553, 628 nodes, where everyone has labeled gender (45.57% men and 54.43% women). Each edge between two users represents "like' or "comment' that one user gave another on posted photo. The dataset has moderate homophily.
D Details on the Experiments and Extended Results
We R 1000 throughout experiments. For the outreach, discretize the space [] x [0,1] into 100 x 100 equal sized bins. For S3D (refer to Appendix E), we use constants, amploit_to_explore shallow_horiee 4.
1.3, won.aaceptacceeeeetiioo
0.95, and
D.1 Outreach Distribution
We report additional experiments in Figs. 8 to 11.
15

---

AH, p 0.1
p 0.1
АH,
p 0.1
hrt d, |5|
8: [S]= 20
d, |8 20
8. [S] 20
% outreach group 2
% outreach group 2
% outreech group
% outreach group
0.2
0.2
0.2
0.2
0.2
% outreach group 1
% outreach group
% outreach group
% outreach group
AH, p = hrt d, [S]
AH, p 0.5
AH, = bas d, |S
AH, p 0.5
g: [S] 10
bas g: |S] 10
% outreach piron 2
2 droug
chno 2
% outreach group
%6 Feeee Stro
inttreeen So
Coseaniin %
0.8
0.8
% outreach group 1
% outreach group
% outreach group
% outreach group
APS, p 0.3
APS, = 0.3
APS, p = 0.3
APS, p= = 0.3
hrt_d. [S] =
hrt |S| = 6
bas_d, [S] = 6
baa_g. [S] =
0.6
2
0.6
0.8
0.6
56 outrcach group
% nuttresen Aiiaoo
0.4
0.4
0.4
0.4
36 Duu
%6 outreach group
&6 outreach group
96 outreach group
% outreach group
Figure 8: Outreach distribution.
16

---

AV_0, p 0.3
AV_O. p= 0.3
AV_O, p
OV_0. p 0.3
hrt_d, [S]
hrt_g. |S|
bas_d, [S]
bas_gg |S|
0.6
2 mooua tonanno g5
good 2
outreach group
outreach group
0.4
0-4
cocoome g8
0.2
0.2
0.3
0.2
0.2
0.4
0.0
0.2
0.4
0.6
0.2
0.4
0.6
0.2
0.4
0.8
%6 outreach group
% outreach group
outreach group
% outreach group
2v_2. p 0.2
_V_ p=
AV_2, p bas_d,
2. p 0.2
hrt_d, |S]
hrt_g. |S|
bas_g.
chous Z
06 cutteaan pepor 2
outreach group
% outreach group
0.4
%6 outreach group
% outreach group 1
% outreach group
% outreach group
AV_2. p = 0.2 hrt_d, [S| =
AV_2. p 0.2
AV_2. = 0.2
AV_2, p 0.2
hrt_g. |S]
bas_d. [S]
baa_g. [S]
Z drouu aomanno 25
S outreach group
2 outreach grounp
Ehous
% outreach group
% outreach group 1
% outreach group
% outreach group
AV_ AV_16, p = 0.1
AV AV_16, p 0.1
AV_16, p 0.1
6, p W_16,
0.1
hrt_d, 5] = 10
hrt_g. [S] =
bas_d, ||| 10
bas_g. S = 10
86 outreach group 2
% nutreach group 2
outtreach group 2
& outreacc coutreachggro goooo
0.2
0.2
0.2
% outreach group
% outreach group
&6 outreach group
% outreach group
_V_20, p = 0.5 hrt_d, [S] = 15
AV_20 20, p = 0.5
AV_ p = 0.5
AV_20, p = 0.5
hrt_g. [S] = 15
bas_d, [S] = 15
bas__ gg. [S] 15
de Couppe Z
%6 outreach group
% outreach group
0.8
0.8
0.8
0.8
Aeoeeee Commtree %%
0.4
0.4
% outreach group
& outreach group
% outreach group
% outreach group
Figure 9: Outreach distribution.
17

---

D2, 0.1
D2, p 0.1
D2, 0.1
D2, 0.1
hrt 4. [S| 90
hrt.g: [S| 90
bas ., |S 90
bas |S| 90
outreach group 2
% outreach group 2
% outreach group 2
% outreach group
0.2
0.2
0.2
0.2
outreach group
% outreach group
% outreach group
outreach group
p 0.01
HS, 0.01
HS, p bas.d,
0.01
HS, p 0.01
[S]
hrt.g; 10
8 [S] 10
% outreach group 2
Soooa 2
% outreach group
% outreach group
0.2
0.2
2 Intreau
0.2
0.2
0.2
0.2
% outreach group 1
% outreach group
% outreach group 1
% outreach group
HS, p brt.d, [S] =
HS, p
HS, =
HS, p 0.5
hrt g, [S]
bas d, |S|
bas g. [S] =
% outtreach Aanon 2
7
de outreach group
de outreech Ainoud
28 outreach chous
% outreach group 1 HS, = 0.1
% outreach group
% outreach group 1 HS, = 0.1
% outreach group
HS, p = 0.1
HS, p 0.1
hrt d, |S| =
hrt g, [S] 4
bas d, |S| =
bas g. |S| =
2 0.4
% outreeach group 2 0.4
0.4
% outreach group 2 0.4
outreach group
outreach group
0.2
0.2
0.2
0.2
outreach group
% outreach group
% outreach group 1
% outreach group
Figure Outreach distribution.
18

---

IV, 0.1
p 0.1
IV,
p 0.1
hrt_d, =
hrt S, [8] =
bas dd |S|=
bas.g. |S| =2
% outreech group 2
% outreach group 2
% outreach group
% outreach group
0.2
0.2
0.2
0.2
0.2
% outreach group 1
% outreach group
% outreach group 1
% outreach group
IV, = brt.d, |S|= 2
IV, p p= 0.1
IV, p=
IV, p 0.1
hrt 8, [S| =
bas d, |S| =
bas g: |S| =2
% resch group 2
soup 2
% outreach group
% outreach group
5% outreach gtoos
0.2
0.2
0.2
0.2
% outreach group 1
% outreach group
% outreach group 1
% outreach group
Figure 11: Outreach distribution.
19

---

D.2 The Impact of the Conduction Probability for Various Dataset We report additional experiments in Figs. 12 and 13.
AH, bas_g. [S] =
Equity (1-diff exp. outreach)
Mutual faimesss
0.98
0.98
0.96
0.96
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Conduction Probability
(a) bas _g seeds in [S]
APS. baa_d, [S]
15
Equity (1-difft in exp. outreach)
Mutual faimess
0.9
0.9
0.8
0.8
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Conduction Probability
(b) bas_d d seeds in APS, |S|
15
APS, bas_g.
Equityy I-diff. in exp. outrreuch)
Mutual faimess
0.95
0.9
0.9
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Conduction Probability
(c) bas_g seeds in APS, |S] = 15
Figure 12: Part 1:
Different definitions of faimess VS conduction probability on outreach distribution created by the bas_g or bas_d d heuristic.
20

---

AV_0. bas_g. g, [S] = 20
Equity (1-difft in exp. outreach
Mutual fairness
0.98
0.99
0.96
0.98
0.94
0.5
0.6
0.7
0.8
Conduction Probability
(a) bas__ seeds in AV_0, |S|
20
DZ. bas___ g. |)
Equity (1-diff. in cxp. outreacch)
Mutual fairnsss
0.98
0.98
0.96
0.96
0.91
0.94
0
0.1
0.2
0.3
0.1
0.5
0.6
0.7
0.8
0.9
Conduction Probability
(b) bas_ sceds in DZ, |S]
50
HS, bas_g.
Eiquity (1-diff: exp. outreach)
Mutual fairness
0.95
0.95
0.9
0.9
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
Conduction Probubility
(c) bas_ seeds HS, SS]
IV. bas_g. |S| = 2
Equity (1-diff. in outreach)
Mutual faireess
0.9
0.9
0.5 0.6 0.7
Conduction Probability
(d) bas_g sceds in IV, |S|
2
Figure 13: Part 2: Different definitions of fairness VS conduction probability on an outreach distribution created by the bas_g heuristic.
21

---

D.3
Fairness-Efficiency performance of seedset selection algorithms
We report more experiments in Fig. 14.
AH. p =
AH. p 0.5
APS. p
APS. p = 0.3
S 10, 8
0.8
[S] 10, 0.8
|||
6, = 0.5
[S] 6, 0.8
0.99
Fuirness
Fairness
Fairness
0.59
0.97
0.8
0.06
0.08
Efficiency
Efficiency
Efficiency
Efficiency
P 0.3 3 0.8
AV_2,p=
AV 2 0.2 4
AV_16, p1
||| 4 0.5
[|| =0
0.98
Faimess
Faimess
Faimess
0.94
0.98
0.98
0.948
10
0.92
0.06
0.96
0.96
0.2
0.25
0.3
0.35
0.06
0.08
0.1
0.06
0.08
0.1
0.02 O. 0. 0.06 0.08 0.1
Efficieney
Efficiency
Efficiency
Efficicncy
2__00.
0.5
D2.
0.1
HS.
0.01
HS.
0.5
15, 3 = 0.8
|S| = 90, 8 0.8
|5
10, 8
0.5
|
6, B 0.8
Falmesss
Faimess
Fairesss
Faireess
0.96
LE
0.96
0.90
0.04
0.04
0.92
0.92
0.9
0.99
0.9
0.9
0.0
0.06
0.7 0.78
0.8
0.06.008 0.1 0.120.14
0.06
0.08
0.1
0.8 0.52 0. 0.86 0.88 0.9
Efficiency
Efficiency
Efficiency
Etticiency
HS, =
IV. P 0.1
IV. = 0.1
INS, = 0.5
|S] = 4. = 0.8
[S] 2, 3 0.5
| = 2. 8 0.8
||| = 28, 3 = 0.8
0.98
0.98
0.98
Fairness
Fairness
Fairness
0.04
0.04
0.94
0.9
0.9
0.9
Efficiency
Efficiency
Efficiency
Etticiency
Figure 14: S3D trade-off and improvement against other label-aware and label-blind algorithms. Filled markers refer to greedy- based algorithms: bas__, S3D _. and hrt_g. Empty markers refer to degree-based algorithms: [ bas d, O S3D dd and & hrt_d.
E Details on the Algorithm
E.1 Pseudocode
We provide more details algorithm, S3D, in two routines, Algorithm 2 and Algorithm 3,
22

---

Algorithm 2 Seed Selection Stochastic Descent (S3D) Step: Pseudo Code
1: function SREEDSET_REACI((SES C, nodes reached from seedset until
horizon
2: realizations +- 1000
> for MCMC sampling, configurable
3: reach
4: while realizations do
5: reach <- reach+ INDERENDEN G, P, horizon) > collect
nodes reached
6:
realizations +- realizations
7:
return reach
> repetition of nodes reached
8:
function $3D__ STEP(seedset, G, P, Sair_to_efficat & each step yields seedset
9:
exploit_ to__tt_____________oo ttt__te____eeeeeeee +- 1.3
D experimentally chosen, configurable prob. of retaining set
10:
non_acceptance, pascepttane__reteetionn, wwweetiinnppetteeeee
0.95
11:
max_ max_horizon t- GET _IMM[D
horizon_factor + max max_ max__orrzon/
limit runtime
13:
shallov_horizon + max wwwax_horizoo/iae htw.://ooooooooooaaattoooo
14:
num_seeds + (en(seedset)
15:
seedset -- DISTINCT(sseedset)
16:
to size with random nodes reach SEEDSET REA.REEACHHSC... REACH(seedset, G, P, max_horizon) get first in candidate seedset
seedset - FIT_TO _O rr__siZE(seedset, num_seeds)
17:
18:
candidate_set + [SAMPLE(reach,
19:
while num_seeds
20:
last_seed <- candidate_seti
get latest seed
21:
> remove shallow reach of last seed from current reach
22:
reach reach- SEEDSET REACH(Iast__eeeeeeeeeeeeeeeeeeee G, p, shallow saallow_horizon) P extend new seedset
23:
candidate_sed set + cawdidate_esteeeeeocccaa + |SAMPLE(reach, 1)]
24:
jum_seeds num_ seeds
curr_score + -BTA BETAA_AAINNESSSSEEE www.AAAEESSSseeeesttteeesssssss
26:
candidate_scors + BETA -tw.D//A.FAARaSSaadddddttt.eeee
fair_to_efficayy
27:
Metropolis Sampling
28:
energy_haange curr_score candidate_score
29:
accept_prob +- CLIP(exp(exploix httpo/pppoottttttppppeeeeee tepppllotttt_eeooreeeeeeeeeeeeee onergy_changee [0,
nonce_1 <- 10
31:
if nonce_1 < accept_prob then
32:
return candidate_set.
D get better seedset
33:
else
34:
nonce 2 +- U0)
35:
if nonce 2 non_ hoa..accccpacc.rrtetttiooooooooo then
36:
return seedset
>> retain existing choice
37:
else
38:
random_sed < Cooees num_seede num_seeds) return random_set
39:
completely random selection rarely
E.2
Estimating Runtime
We estimate the running time of Algorithm and combined. For the S3D_STEP, lines 9-13 are constant operations and comprise dataset properties. Lines 14-15 cost O([S)). FIT_TO SIZE cost up to O(S) log Vl) for sampling new |S] nodes. SEEDSET REACH does repeated BFS, and so costs O O(R(VV)++ + El). Lines 19-24 cost follows.
O(IS (Rd + R|V|+++ log R(V))) avg
where daeg is the average degree of the graph, and Dmax is the largest diameter the graph. The first term here upper bounds the max computation in BFS for Dmax horizon. Other terms follow
23

---

Algorithm 3 S3D Iteration: Pseudo Code
1:
function 350__TTERATEsseedttt G, fair_to_efficape nun_iters: least_score, seedset se seedset
2:
3:
least_score +- -BEAE__ BETAA_AIRNESSS(eeddaeee
fair_to_efficacy)
4: while num_iters do
5: seedset +- S3D_ STEP(seedset, G, P, fair_to_ -etooffffccacy fair_to_efficacy?
6: score f -BETA SETTA_FAIRNES(Seeedee if score < least_ then
7:
least_seedset t- seedset 9: num_iters -- num_iters -
8:
10:
return least_seedset
from the remaining operations in the while loop. Now, lines 25-26 first create an outreach from the corresponding seedsets, costing O(R([V] + [E)) each, and then analytically calculate 8-fairness for all the R final configurations, costing O 1) each. In the worst case, we might additionally execute lines 37-39 costing O[[S) log [V). So, single S3D_STEP costs
[||||] + |S] log V + R(V | + F1) + (IS - ()) + R|V | + log R))
+ 2 + [ + R) + SS| log [V])
O(IS) log [V] + R[[V] Bl)
+ R|SS] + R V + log VI)
=O(I5) log [V + R(S
= -O(]SS]VV).
Here, we used the assumption that daye O(2E/V) O(1) for sparse graph (E O(V)). Now this S3D_STEP is run & times using S3D_ITERATE to find the best seedset in these k runs. Moreover, we avoid any redundant calculations and memorize B-fairness for any seedset we discover. Hence, the total runtime is (( as claimed.
E.3 Motivation and Extension to Generic Combinatorial Optimization
The S3D approach 3-fairness optimization in this setting is independently motivated and in general can be extended to any combinatorial optimization problem where each choice of initial action at time = amongst exponentially many choices of actions, can lead system one of exponentially many states, for which we know the probability distribution of the system achieving one of these states and associated, possibly non-convex, expected energy profile resulting from this stochastic state occupancy of the system at later time. S3D then boils down to iteratively trying different initial actions that lead to small changes in the state occupancy distribution that align well with the ideal occupancy distribution, leading to gradual reduction of the expected potential energy of the resulting system using Metropolis Sampling/Simulated Annealing.
In this study, the initial action at f = is the initial seedset choice S, which leads to a distribution of states, called the outreach distribution Network here, can reach to. Each such distribution corresponds to a bounded expected "potential energy" (keeping the ideally mutually fair distribution reference) defined on --fairness- mutually fair configuration defined to be "stable", ; less "energetic" system, and S3D aims to achieve it via an optimal choice of S. S*.
final configuration (Theorem 2.1), that the system, Social
E.4 Theoretical Guarantees of Convergence in S3D
The S3D algorithm is similar to non-convex optimization methods such as Simulated Annealing. Such algorithms do not have theoretical guarantees but have long history of empirical success.
Let f P(V) > [o. 1] be the 3-fairness set-evaluation function defined in the power set of the graph vertex set V. The function can then evaluate any seedset, S C V for its 3-fairness. Now for iterative optimization purposes, S3D defines a sampling process define neighbors S' of S, based on similar outreaches Vg. and Vs. Then S3D essentially follows non-convex optimization of f using Simulated
24

---

Annealing under Metropolis Sampling at constant temperature. While Simulated Annealing does have strict mathematical guarantees to find the global optimum in finite time, its empirical success is well understood in non-convex optimization.
While Simulated Annealing usually runs for finite iterations defined by empirically tested tem- perature schedule, we ran Simulated Annealing under several constant temperatures to estimate the performance of S3D against baselines and concluded that number of iterations [500, 1000] usu- ally works well in practice. Hence, any decaying temperature schedule that translates total iterations in this range should work fine.
E.5 Illustrative Example
Consider the information spreading the graph in Fig. 15 independent cascade model with probability = 0.1, with blue and red nodes belonging to two different groups. A greedy strategy would choose the seed set Sg 3, (enlarged nodes) shown in Fig. 15a, thus leading the highly unfair outreach Fig. 15b. In contrast, our algorithm S3D promotes the choice Se30 = 1, reflected in 15c, which gives the more fair outreach plotted in Fig. 15d, showing that it improves greedy/sophisticated label-blind seed selection strategies.
2D Histogram of groupwise normalized outreach
10
0.8
Fraction of Outreach in Group
0.6
0.4
0.0
Fraction Outreach Group
(a) Greedy Choice: Graph
(b) Greedy Choice: Outreach
2D Histogram of groupwise normalized outreach
1.0
0.8
Fraction of Outreach in Group
0.6
0.4
0.7
0.0
Fraction of Outreach in Group
(c) S3D Choice: Graph
(d) S3D Choice: Outreach
Figure 15: Toy example to show label-aware choice using S3D over label-blind seedset selection process.
The enlarged nodes are selected seeds. Since the graph is small, the outreach discretization bucket has been granularized for improved readability.
25

---

Error Bars on Fairness and Efficiency Experiments
Referring Fig. mention 2a symmetrical enror bars on 100 repetitions for each of the experiment pipelines, as follows. Since each experiment itself runs on R 1, 000 realizations, we take 100R 10 samples of each random graph encoded social network dataset.
Eff-Mean Efficiency- Berienncc---r-BEee Err-Bar (+20)
Fair-Mean
Faimess Err-ss--------e Bar-Bar (#22))
s3d_d 0.24
0.0022
0,94
0.002
hrt_d d
0.105
0.005
0.911
0,004
bas_d
0.173
0.0016
0.803
0.003
s3d_g
0.25
0.002
0.945
0.002
hrt_g
0.17
0.0058
0.868
0.006
bas_g
0.318
0.002
0.898
0.003
Table 2: APS.
Eff-Mean
Efficiency--Fi Bar (+22)
Fair-Mean
Fairness-Eree Err-Bar (#:20)
s3d_d d
0.241
0.005
0.95
0.002
hrt_d
0.227
0.005
0.951
0,002
bas_d
0.277
0.004
0.935
0,002
s3d_g
0.241
0.005
0,951
0,002
hrt-g 0.258
0.005
0,945
0,003
bas_g
0.3
0.004
0.926
0.003
Table 3: AV_0.
Eff-Mean
Efficiency-Eii -rrr Bar (#20)
Fair-Mean
Chirness-Err-ie (#:20)
s3d_d d
0.08
0,0004
0.99
0,0008
hrt_d
0.08
0.0004
0.967
0,0007
bas_d
0.08
0,0004
0.91
0.001
s3d_g
0.08
0.0004
0,988
0.0008
hrt_g 0.08
0,0004
0,965
0,0008
bas_ g
0.08
0.0004
0.938
0.0009
Table 4: HS, p 0.01.
26

---

Eff-Mean
Efficiency-Erree (+:20)
Fair-Mean
Shirness-Err-iee (#:2))
s3d_d
0.88
0.002
0,96
0,001
hrt_d 0.83
0.002
0,94
0,002
bas_d
0.83
0.002
0,94
0,002
s3d_g
0.87
0.002
0,96
0,002
hrt_g 0.86
0.002
0.935
0,002
bas_g
0.89
0.002
0.94
0.002
Table 5: HS, p 0.5.
G
Declaration of Computational Resources
All experiments were performed on local PC on a single CPU core 3.5 GHz. Except for datasets DZ, INS, all datasets were loaded and operated on local PC with 32 GB of RAM. For the largest datasets (DZ, INS), we used remote compute clusters with 64 GB memory and similar CPU capabilities. For the code development, we broadly used Python 3. 3.10+, numpy, jupyter, and networkx [8]. Runtime for each non-S3D configured experiment on datasets except DZ, INS, was 10 15 minutes. For DZ, INS, this was approximately each small dataset (except DZ, INS) for 1.5 hours additionally. For massive datasets DZ, INS, the cluster took ~ days for k 10 steps. The total set of experiments made, including the failed, passed or submitted ones, roughly took the same order of resources separately.
hours. For S3D optimizations be satisfactory, we ran
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The paper sheds light on the limitation of most of the fairness metrics used in the context of Social Influence Maximization. In particular, as mentioned in the Abstract, In the literature, fairness is often quantified terms of the expected outreach within individual communitties. In this paper, we demonstrate that such fairness metrics can be misleading since they overlook the stochastic nature of information diffusson processes. We propose a new metric that overcomes such limitations and, based on it, we propose new seed selection policy that strategically takes into account for mutual information. This made explicit in the abstract by saying We tackle this problem by designing new fairness metric that captures variability outreach through optimal transport theory. We propose new seed-selection algorithm that optimizes both outreach and our new fairness metric, and we show its efficacy on several real datasets. All these aspects are also mentioned in the Contributions paragraph of the Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Yes. Limitations are listed in the second paragraph of Section 5 entitled
Limitations.
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 out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect 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 on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
28

---

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 in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The construction and validity of our metric are theoretically and didactically
explained in the paper in Section 3.1 and Section 3.3. Also, Appendix E, provides formal proof for the complexity of our proposed seed-selection algorithm.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged 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 appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: To replicate our experiments, we (i) open-sourced our code, (ii) put a reference for each of the datasets used (see Section 3.2) (iii) provide a detailed pseudo-code for the seed-seles selection algorithm (See Appendix E), and (iv) give clear explanation of the diffusion process used (independent cascade) and the parameters choices (propagation probability, size of the seed set, etc., see Section 3.2).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary 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 one good way 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
29

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which 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 possible for other researchers have some path reproducing 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 faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our code is publicly available at fairness-sim-oft
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips.
wwwiissssiopiiiyoooc for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
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?
Question:
Answer: [Yes]
Justification: Yes, all the hyperparameters involved the experiments execution are specified in Section 3.2 and Appendix D.
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 a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
30

---

7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Plots requiring statistical significance are the ones in Fig. Plots in Fig. are associated with statistical bounds reported in Appendix F.
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 the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Computational resources are detailed in Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs 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 NeurIPS Code of Ethics https: httee://neeuipppee http///urrrs.ccpppuueee/e ctcc/uublc//hhicccuiieeee....
didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: The paper conforms with the NeurlPS code of ethics. All the datasets we tested our algorithm on preserve anonimity.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
31

---

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 is a special consid-
eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Yes, this is explicitly done in the Introduction and Abstract when we explicitly mention the limitation of the current approaches that we propose to overcome. For example we say: As such, outcomes such as "in 50% of the cases, one of group A receives the information and everyone group B receives and in other 50%, the opposite happens", which always results in largely unfair outcomes, are classified as fair by a variety of fairness metrics in the literature. We tackle this problem by designing a new fairness metric that captures variability in outreach through optimal transport theory. We propose new seed-selection algorithu that optimizes both outreach and our new fairness metric, and show its efficacy on several real datasets.
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 why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system Iearns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided relcasing unsafe images.
32

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Yes, all the sources of existing datasets and algorithms have been cited and can be found in the References.
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 (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.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 in the package should be provided. For popular datasets, paperswithcode. thcode. com datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- ee-aakaaeed both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: We documented the code with instructions in README files and dedicated comments in the code.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
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.
33

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or 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 equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "yXJPdLsHar", "reviewer": "Reviewer_wcrW", "summary": "This paper studies the problem of fairness in IM (Influence Maximization). They present a novel notion of fairness, namely, mutual fairness, which considers outreach distribution in different groups. Compared with previous notions, the proposed one could ensure a higher probability of fairness among groups by evaluating fairness via optimal transport. Based on mutual fairness, they propose the S3D (Stochastic Seedset Selection Descent) algorithm that shows better performance in experiments.", "questions": "In addition to the weaknesses I mentioned above, I also have some minor concerns.\n\n**Q1**: Please explain $\\delta_{(i,j)}$ in the paper.\n\n**Q2**: Eq. (2) has a mistake. I think the later part should be $\\sqrt(2)/2 \\cdot |(x_2-x_1)-(y_2-y_1)|$ rather than $|(x_2-x_1)-(y_1-y_2)|$ since it is Euclidean distance between $z$ and $(x_1,x_2)$. The sample problem also happens in Eq. (3).\n\n**Q3**: The authors should state clearly that which notion is $hrt_g$ based on, equity or equality?\n\n**Q4**: In Figure 4, I believe that the y-axis should be $1-diff.$ in exp. outreach.\n\n**Q5**: When $\\beta=0$, does $\\beta$-fairness degenerate to the classic IM problem?\n\n**Q6**: Please explain the \"fixed horizon\" in Algorithm 1.\n\n**Q7**: I suggest the authors use $S$ and $S_o$ for candidates and the initial seed set for a clearer presentation. The variant font of $S$ could easily lead to readers' confusion.\n\n**Q8**: I am confused by the weird phenomenon where results in Figure 5(b-d) appear as discrete rectangles. Any explanation?", "limitations": "The authors have addressed their limitations. However, I am wondering whether the method can be **easily** generalized to more groups, as I mentioned in Weakness.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "**S1**: Presenting a novel notion of fairness in IM which seems really appealing to me. \n\n**S2**: Evaluating the level of fairness via optimal transport.\n\n**S3**: Presenting the S3D algorithm.", "weaknesses": "**W1**: In this paper, the authors only consider $m=2$ groups and claim the framework is easily generalizable to more groups. I doubt about this in two aspects. On the one hand, the case would become much more complex (growing exponentially) when considering multiple variable probability distributions. On the other hand, the distance between two distributions can be easily calculated when there are only two groups. I wonder how to calculate such distance when the distribution contains $m$ groups.\n\n**W2**: The example in motivation and the motivating example seem to be rather extreme cases. I can understand such examples are only constructed to show the significance of mutual fairness, but these cases can hardly occur in real-world scenarios.\n\n**W3**: Since this paper evaluates fairness based on utility distribution, how to depict the ground-truth utility distribution with high approximation probability is of great importance. The authors should discuss this point. Besides, $R$ times of Monte Carlo simulation with $R=1000$ is far from enough in the field of IM. Please check related references.\n\n**W4**: The authors claim that \"the equity metric fails to adequately capture changes in fairness\" based on the results in Figure 4. However, the y-axis in Figure 4 only ranges from 0.9 to 1. Therefore, both metrics are already high enough to reflect their deep difference. Also, in Appendix C.2, the two metrics are even more similar. The benefit of using mutual fairness is not so obvious.\n\n**W5**: In Figure 5(d), the outreach of the proposed method is significantly higher than the Greedy. Does it really happen? Note that the Greedy has a theoretical guarantee of $(1-1/e-\\varepsilon$)-approximation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# W1\nWe agree that the multi-group case requires more detail. We will include a dedicated appendix. With $m$ groups, the outreach distribution is a distribution $\\gamma$ on $[0,1]^m$. The reference distribution is again the ``ideal'' distribution $\\gamma^\\ast=\\delta_{(1,\\ldots,1)}$ which encodes the case in which all members of all groups receive the information. As for the transportation cost, we can define it to be to distance between any given point $x=(x_1,\\ldots,x_m)$ and the diagonal line. We can call this distance $d(x)$. An expression of $d$ can be found via simple geometric arguments. Then, $$\\textsf{Fairness}(\\gamma)=1-a E_{x\\sim\\gamma}[d(x)]$$ where $a>0$ is so that the metric is between 0 and 1. Then, $\\beta$-fairness can be defined analogously. Since we have a closed-form expression, there is no need to numerically solve OT problems, as in the paper. Also, we do not resort to multimarginal OT, which would cause exponential complexity in $m$. \n# W2\nThe example we draw inspiration from to design our metric, however, is an actual occurrence in our experiments. For the APS dataset with greedy fair heuristic, which exploits the notion of equity (Fig 3c in the paper, Fig a in the PDF), the samples are distributed in a way such that a consistent percentage (~30%) of the members in group 1 receive the information and way fewer members of group 2 receive it, and vice-versa. We show in Fig 5a that our algorithm can counteract unfair occurrences by moving the distribution closer to the diagonal (Fig b in the PDF). We will put more emphasis on this in the final version.\n# W3\nWe agree that the $R$ leading to a statistically strong result depends on the dataset: the varied geometry of various subgraphs that the sampling of the edges produce, the exact complexity of the joint-outreach distribution (ground-utility distribution in this context), and the uncertainty of the quantities we sample/approximate throughout our experiments. App. E: Tab. 2-5 highlight the level of uncertainty, being < 3% in $2\\sigma$ error-bar. To generate these bars using the $R$ values, we run each configuration 100 times, leading to instances using $100R = 10^5$ independent subgraph samples, sufficiently more than/of the same order in the relevant literature. We will highlight this in the revision.\n# W4\nWe show earlier in the paper that our metric is more informative than the equity metric, both mathematically (Sec 3.1) and with a vast amount of experiments (Sec 3.2). Fig 4 confirms these findings by noticing that the two metrics show significantly different trends across different propagation probabilities, rather than their absolute closeness. E.g., in Fig 4, the higher conduction prob. makes the same setup \"relatively\" unfair when seen from our metric's lens, totally opposite of what expected outreach highlights, establishing a non-trivial and fundamental difference in them.\n# W5\nThe reviewer is correct. There was a mislabeling in Fig 5b-d. Fig 5b is a comparison between the greedy heuristics versus S3D with greedy baseline and Fig 5d is a comparison between the degree centrality heuristics versus S3D with degree centrality baseline. The behavior in Fig 5d is now in sync with the corresponding metric dots in Fig 6's last subfigure. This also agrees with our understanding that the greedy strategy already has a theoretic efficiency lower-bound guarantee, unlikely to be surpassed (see Fig. 6 last subfigure). What S3D achieves is a tradeoff for ~1% efficiency to get a >2% gain in fairness against greedy heuristics. Whereas against degree centrality heuristics, there is a substantial gain in both fairness and efficiency. We have corrected the figures in the PDF.\n# Q1\nIt is the delta distribution at $(i,j)\\in [0,1]^2$. We will mention this in the final version. \n# Q2\nThanks for pointing out this inaccuracy. Indeed, the transportation cost is $$\\Vert z(x_1,x_2,y_1,y_2)-x\\Vert=\\frac{\\sqrt{2}}{2}|(x_2-x_1)-(y_2-y_1)|.$$ The factor $\\sqrt{2}/2$ is then dropped for normalization purposes, to ensure that the metric is between 0 and 1. In our applications, the reference distribution lies on the diagonal ($y_1=y_2$) which (after normalization) yields the same expression $|x_1-x_2|$. Thus, this inaccuracy does not affect our experiments. We detailed the computations and fixed Eq (2)-(3) in the revision.\n# Q3\nThe alg. hrtg is based on equity. We will mention it in the paper.\n# Q4\nThe reviewer is correct. \n# Q5\nCorrect. We will mention this in the revision.\n# Q6\nWhen we consider information propagation from $S$ to generate the list $V_S$ of nodes reachable from $S$ (line 3), we use this $V_S$ to generate a candidate seedset $\\hat{S}$ using iteration in lines 5-8, adding a new seed per step. This seed in each step, $v \\sim V_S$, incrementally reduces the list $V_S$ by removing nodes from it that are reachable from $v$. Ideally, the reachability of $v$ alone is again defined by the nodes reachable via Independent Cascade (IC) starting from this seed. So, one might end up running IC $|S|$ many times, for all $v\\in\\hat{S}$. To approximately solve this problem, we create $V_{\\hat{S}}$ (line 7) only considering nearest neighbors up to a constant depth from $v$ (fixed iterations of BFS from $v$). This constant is a fraction of the largest graph diameter. \n# Q7\nWe appreciate the suggestion and will implement it.\n# Q8\nThis behavior can also be seen well in the example in Fig. 14, where the reasoning is instantly perceptible. For visualization/computation reasons, $[0,1]^2$ is discretized into 100x100 (real-world datasets) or 10x10 (Fig 14) blocks. Meanwhile, the possible outreach fraction realizations (rational numbers), depending on the graph geometry and the number of graph nodes and selected seeds, are bucketed into the closest buckets. So, the visualization may appear as a pattern of \"rectangles\" which represent the buckets of the discretized space. These are more prominent with smaller datasets.\n# Limitations\nPlease refer to W1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2mNWzMGKJX", "reviewer": "Reviewer_vnZX", "summary": "This paper studies the problem of Fair Social Influence Maximization (SIM). Specifically, it introduces a new notion of fairness for SIM. The current literature on Fair SIM studies defines fairness in terms of expected values, e.g., a solution is fair if the expected ratio of influenced nodes from each demographic group is the same. The paper at hand begins by demonstration scenarios where the aforementioned definitions of fairness fail to provide truly fair outcomes. Namely, scenarios where the expected values are not enough to capture fairness (50% chance of all red nodes getting influenced with 0 blue nodes influenced, and 50% chance of all blue nodes getting influenced with 0 red nodes influenced). To address and mitigate such obviously problematic cases, the authors introduce a novel fairness definition based on optimal transport. Fix the optimally fair joint distribution $\\gamma^*$, in which both groups always receive the same ratio of influenced nodes. Then a joint distribution $\\gamma$ is considered fair is it minimizes the transport distance to $\\gamma^*$. The cost function used in the transport distance is the natural choice of a Euclidean distance. The authors call this notion of fairness mutual fairness.\n\nAfter introducing mutual fairness, the authors proceed with an extensive experimental evaluation that demonstrates that algorithms which satisfy notions of expected fairness are not necessarily mutually fair. Moving forward, they show how the trade-off between fairness and efficiency (how many nodes are reached in total) can be naturally incorporated in their definition of mutual fairness; this gives rise to a new definition called $\\beta$-fairness where $\\beta$ is a parameter controlling the aforementioned trade-off. Finally, the authors present an algorithm that is specifically designed to optimize mutual fairness. Their experimental evaluation shows that this algorithm dominates existing baselines.", "questions": "Shouldn't $\\gamma$ be $\\pi$ in line 184, in the definition of mutual fairness?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) Very interesting novel concept of fairness for SIM. \n2) Solid results with extensive experimental evaluation.\n3) Excellent presentation.", "weaknesses": "1) Lack of theoretical guarantees for the S3D algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# W1: Lack of theoretical guarantees for the S3D algorithm\n\nWe thank the reviewer for the positive feedback. To first address the point regarding the lack of theoretical guarantees: The S3D algorithm is similar to non-convex optimization methods such as Simulated Annealing. Such algorithms do not have theoretical guarantees but do have a long history of empirical success. We think that obtaining theoretical guarantees would be an excellent avenue for future work. \n\nFor further details on S3D, let $f: \\mathcal{P}(V) \\rightarrow [0, 1]$ be the $\\beta$-fairness set-evaluation function defined in the power-set of the graph vertex set $V$. The function can then evaluate any seedset, $S \\subseteq V$ for its $\\beta$-fairness. Now for iterative optimization purposes, S3D Algorithm 1::3-8 defines a sampling process to define neighbors $\\hat{S}$ of $S$ through its outreach $V_S$. Then S3D essentially follows non-convex optimization of $f$ using Simulated Annealing under Metropolis Sampling at a constant temperature. While Simulated Annealing does not have strict mathematical guarantees to find the global optimum in finite time, its empirical success is well understood in non-convex optimization.\n\nWhile Simulated Annealing usually runs for finite iterations defined by an empirically tested temperature schedule, we ran Simulated Annealing under several constant temperatures to estimate the performance of S3D against baselines and concluded that a number of iterations $k \\in [500, 1000]$  usually works well in practice. Hence any decaying temperature schedule that translates total iterations in this range should work fine.\n\n# Q1\n\nThe optimal transport discrepancy $W(\\gamma,\\gamma^*)$, appearing in line 184, is computed between two probability distributions: the probability measure $\\gamma$ and the desired probability measure $\\gamma^*$. The symbol $\\pi$, instead, refers to the transportation plan and it is the optimization variable associated with the optimal transport problem. In line 184, the explicit expression of the solution of the optimization problem is already given, for this reason, $\\pi$ does not appear. The subscript $(x_1,x_2)\\sim \\gamma$, instead, indicates that the samples $x_1,x_2$ are drawn from the probability distribution $\\gamma$. We will further clarify these aspects in the text.\n\nWe thank the reviewer for the positive assessment of our paper and their constructive feedback.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JA48RtApH3", "reviewer": "Reviewer_rBPP", "summary": "The paper addresses the challenge of ensuring fairness in social influence maximization, where the goal is to select seed nodes in a social network to spread information equitably among different communities. The authors identify the limitations of existing fairness metrics, which often fail to account for the stochastic nature of information diffusion. To address this, they propose a new fairness metric, termed \"mutual fairness,\" based on optimal transport theory. The authors also develop a seed-selection algorithm that optimizes both outreach and mutual fairness. Empirical evaluations on several real-world datasets demonstrate the efficacy of the proposed approach.", "questions": "How does the mutual fairness metric perform in extremely large networks, and what are the computational challenges associated with scaling the approach?", "limitations": "Network Topology: Expand the experiments to include a wider variety of network topologies, providing insights into how different structures impact the fairness and efficiency of the approach.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1.Novel Fairness Metric: The introduction of the mutual fairness metric represents a significant contribution. This metric captures the variability in outreach and provides a more accurate assessment of fairness in stochastic diffusion processes.\n2.Practical Relevance: The proposed metric and algorithm are highly practical, addressing real-world issues in social influence maximization. The approach is shown to be effective across various datasets, making it a valuable tool for practitioners.\n3.Thorough Evaluation: The authors conduct extensive experiments on diverse real-world datasets, demonstrating that their approach not only enhances fairness but also maintains or even improves efficiency.", "weaknesses": "Potential Scalability Issues: While the proposed method performs well on the datasets tested, its scalability to very large networks or to scenarios with many groups is not fully explored. Further analysis on the computational complexity and scalability would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# W1(/Q1): Potential Scalability Issues\n\nWe thank the reviewer for the positive feedback and insightful comments. We first address both scalability aspects as follows:\n\n**Definition of fairness metric with $m$-groups**:\n\nWe agree with the reviewer that the multi-group case requires more detail. In future versions of the paper, we will include an appendix for the $m$-group case, which we summarize below. \n\nIn the case of $m$ groups, the outreach distribution is a probability distribution $\\gamma$ on the hypercube $[0,1]^m$. The reference distribution can again be taken to be the ``ideal'' distribution $\\gamma^\\ast=\\delta_{(1,\\ldots,1)}$ which encodes the case in which all members of all groups receive the information. As for the transportation cost, we can define it to be to distance between any given point $x=(x_1,\\ldots,x_m)$ in the hypercube and the diagonal line. We can call this distance $d(x)$. An expression of $d$ can be found via simple geometric arguments. With this the fairness metric becomes\n$$\\textsf{Fairness}(\\gamma)=1-a\\mathbb{E}_{x\\sim\\gamma}[d(x)],$$\nwhere the constant $a>0$ is again chosen so that $\\textsf{Fairness}(\\gamma)$ is between 0 and 1. Then, $\\beta$-$\\textsf{Fairness}(\\gamma)$ can be defined analogously. Finally, since we once again provide a closed-form expression, there is no need to numerically solve optimal transport problems, as in the 2D case presented in the paper. Also, note that we do not resort to the multimarginal optimal transport problem, which would indeed cause exponential complexity in the dimensionality. \n\n\n**Scaling with Large Graphs**\n\nAppendix D.2 details the computational complexity of the algorithm, assuming sparse graphs. Additionally, we tested on a range of datasets summarized in Appendix B::Tab. 1. When considering sparse datasets, we see a linear growth of the computational complexity with the number of graph nodes. While we still accommodate time-complexity growth with the growth of the seedset size $|S|$, the SIM problem in the literature usually keeps them small subject to its definition. $R=1000$ worked well across all datasets (see Appendix E::Tab. 2-5 for error-bars). Moreover, if the graphs aren't sparse (as we tested with dataset DZ), computation time grows additionally with $|E|$ as highlighted in App. D.2. \n\nIn practice, for datasets like INS with ~500,000 nodes and edges, generating a new seedset candidate can take around ~5 hours on computational resources declared in App. F, and is the usual bottleneck in the entire algorithm.\n\n**Computational precision in approximating joint distribution**\n\nApproximating outreach distribution is also limited by the extent to which we discretize the probability space. Added to this, if the graph is dense enough to present numerically close joint outreach sample points, we are forced to bucket them into a single support point in the probability space, trivializing the optimization problem and making similar seedset selections look equally fair and efficient.\n\nMoreover, one can see exponential growth in handling the discrete support space with the number of groups $m$, if we increase the precision/discrete bucket size of the support space. For our experiments, discretizing $[0, 1]^m, m=2$ space with $100$ buckets for each group meant handling $100^2=10^4$ points in probability space.\nNonetheless, since we provide a closed-form expression for the fairness metric, bypassing the computation of the optimal transport problem, its evaluation does not suffer from an increased discretization. \n\nWe will include a detailed discussion on time complexity and scalability in the final version of the paper.\n\n# L1: Network Topology\n\n**Network topology:** We discuss the impact of network topology in Sec. 3.2, and we will expand on this point in the final version of the paper. In short, when the conduction probability is too small or too large, network topology does not play a major role. When the conduction probability is moderate, network topology starts playing a role, mainly through the number of cross-group edges (CE): \n\nCE% is small (~5%, APS): Such datasets encode group interaction information in the edges themselves, that is, an edge likely means nodes belong to the same group. In such cases, baseline greedy algorithms (bas\\_g) already perform well as they rely only on the edge connectivity which is extremely reliable here. S3D does not significantly improve on their selection, both in efficiency and fairness.\n\nCE% is balanced (40-50%, HS, AH): These datasets reflect that groups interact well across each other and hence any seedset selection largely ends up getting a fair outreach. Since bas\\_g already has proven near-optimal efficiency guarantees too, S3D performing significantly better than bas\\_g is again unlikely.\n\nCE% is moderate (5-30%, AV (datasets ids $0, 2, 16, 20$), IV): These are the non-trivial cases not covered above. And here bas\\_g isn't lucky enough to reliably leverage the existence of edges into group information. Hence, S3D usually outperforms the baseline in these cases, achieving similar efficiency scores and significantly improving fair outreach through its seedset selection.\n\nCE\\% is high (>50%): This case was never observed where nodes interact more across groups than in their own groups. However, as long as the existence of edges doesn't reliably signal group information, we expect S3D to perform well based on a similar analysis.\n\n**Moderate outreach in dense graphs (\\INS, DZ):**\nGraphs where $|E|$ substantially exceeds $|V|$, the outreach variance across sample sub-graphs is too low to be captured in the discretized space we experimented in (100x100 units in  $[0,1]^2$), even for moderate $p$. This leads to single-point concentrated joint-distribution plots across several seedsets S3D tries to evaluate, all of them leading to the same OT score/$\\beta$-fairness.\n\nWe thank the reviewer for the positive assessment of our paper and their constructive feedback.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SPq8YfbrsL", "reviewer": "Reviewer_1BeY", "summary": "This paper proposed a new metric for fairness in social influence maximization, namely mutual fairness. It is based on optimal transport theory. A parameter \\beta is designed to achieve a balance between fairness and efficiency. When \\beta = 0, it ignores mutual fairness. When \\beta = 1, it enforces mutual fairness and ignores efficiency. A selection algorithm S3D is proposed based on the mutual fairness.", "questions": "I still don't understand why the example scenario is unfair.", "limitations": "Limitations are discussed.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The new metric for fairness in influence maximization is refreshing and innovative.\n\nExamples make the presentation easy to understand.", "weaknesses": "1. In Definition 2.1, V is the network. Late in section 3.2, V is the set of nodes.\n\n2. Consider two influence strategies, A and B, for a population of two groups, I and II. Strategy A always informs everyone in Group I while ignoring everyone in Group II. Strategy B is the opposite. The optimal transport discrepancy between the two probability measures is \\sqrt{2}. But they have the same mutual fairness score. This is a little counter-intuitive. Maybe try to modify it.\n\n3. The generalizability from two groups to multi-groups should be demonstrated in detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# W1\n\nThanks for pointing this out. We made the proposed correction in the manuscript.\n\n# W2\n\nStrategy A and Strategy B have the same mutual fairness score since they are equally (un)fair. Namely, they have the same distance from the diagonal. On the other hand, transporting Strategy A onto Strategy B has the highest cost as they are at a maximum (Euclidean) distance apart from each other. In a sense, the two strategies are ``symmetric'' in terms of unfairness. We would be glad to exemplify this further in the final version of the paper.\n\n# W3: The generalizability to multi-groups\n\nWe agree with the reviewer that the multi-group case requires more detail. In future versions of the manuscript, we will include a dedicated appendix for the $m$-group case, which we summarize below. \n\nIn the case of $m$ groups, the outreach distribution is a probability distribution $\\gamma$ on the hypercube $[0,1]^m$; i.e., $\\gamma$ now lives in $\\mathcal P([0,1]^m)$.\nThe reference distribution can again be taken to be the ``ideal'' distribution $\\gamma^\\ast=\\delta_{(1,\\ldots,1)}$ which encodes the case in which all members of all groups receive the information. As for the transportation cost, we can define it to be to distance between any given point $x=(x_1,\\ldots,x_m)$ in the hypercube and the diagonal line. We can call this distance $d(x)$. An expression of $d$ can be found via simple geometric arguments. With this the fairness metric becomes\n\\begin{equation*}\n    \\textsf{Fairness}(\\gamma)\n    =\n    1-\n    a\n    \\mathbb{E}_{x\\sim\\gamma}[d(x)],\n\\end{equation*}\nwhere the constant $a>0$ is again chosen so that $\\textsf{Fairness}(\\gamma)$ is between 0 and 1. Then, $\\beta$-$\\textsf{Fairness}(\\gamma)$ can be defined analogously. \n\nFinally, since we once again provide a closed-form expression, there is no need to numerically solve optimal transport problems, as in the 2D case presented in the paper. Also, note that we do not resort to the multimarginal optimal transport problem, which would indeed cause exponential complexity in the dimensionality. \n\n# Q1: I still don't understand why the example scenario is unfair.\n\nThe proposed example refers to the final configuration\n\\begin{equation*}\n    \\gamma_b = 0.25 \\cdot \\delta_{(0,0)} + 0.25 \\cdot \\delta_{(1,1)} + 0.25 \\cdot \\delta_{(0,1)} +0.25 \\cdot \\delta_{(1,0)} \n\\end{equation*}\nwhere $\\delta_{(i,j)}$ indicates the delta distribution centered at $(i,j)$, $i,j\\in[0,1]$.\nThe distribution $\\gamma_b$ encompasses the case in which in 25\\% of the cases anyone in Group 1 receives the information and none in Group 2 receives it ($0.25 \\cdot \\delta_{(1,0)} $) and in 25\\% of the cases anyone in Group 2 receives the information and none in Group 1 receives it ($0.25 \\cdot \\delta_{(0,1)} $). Therefore, in 50\\% of the cases, everyone in one group receives the information, as none in the other group receive it ($0.25 \\cdot \\delta_{(1,0)} + 0.25 \\cdot \\delta_{(0,1)}$).\n\nThis represents a highly unfair outcome: referring to the example proposed by the reviewer, this means that half of the time we are in the situation of Strategy A or Strategy B, namely half of the time, there is one group that has no access to the information spread. We hope we have been able to clarify the doubt.\n\nWe thank the reviewer for the time spent reviewing our paper and for their constructive feedback.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Dear Chairs, 

Dear Reviewers,


We thank you  for the thoughtful feedback on our manuscript.  
In the original submission, all four Reviewers found our results of interest to the wide readership of NeurIPS.
In particular, all reviewers agree on the fact that the proposed fairness metric is innovative and of practical relevance. 
The main reservation of the Reviewers concerns the extension of the new metric to multiple groups, which was originally limited to two groups and hampers its wide application to real-world complex systems.
Other suggestions to further improve the manuscript include clarification about the realism of the motivating example, the influence of the network topology, and practical scalability issues.

We have now revised the manuscript to address these and all other comments from the Reviewers.


In particular,

1) we have explicitly mentioned now how the method can be extended to multiple groups and, in particular, explained why our fairness metric does not suffer from exponential computational complexity in the number of groups, which one might expect from the multi-marginal formulation of optimal transport;
    
2) we have extensively listed how the cross-edge percentage affects fairness and efficiency compared to the baseline algorithms, by splitting the analysis into small, balanced, moderate, and high cross-edge percentages;

3) we have shown  how our motivating example indeed is a practical occurrence in the experiments;

4) we have elucidated what are the scalability issues of our algorithm when it comes to very large networks.


These revisions significantly improved the presentation of our fairness metric and seed selection strategy by making it clear how our method extends to multiple groups and how the strategy could be, in principle, implemented in practice.

Yours Sincerely,

The Authors

Meta-review: The paper studies fair influence maximization problem for influence propagation in social networks. It proposes a new metric, mutual fairness, to address the limitation of previous fairness matric under stochastic outcomes. The reviewers acknowledge the novelty of the proposed metric, as well as the technical contribution of applying the optimal transport theory to the task. The issues raised by the reviewers are mostly addressed by the authors during the rebuttal stage. I thus recommend acceptance to the paper.
Decision: Accept (poster)