Fairness in Social Influence Maximization via Optimal Transport

Authors: shubham  chowdary
giulia  de pasquale
nicolas  lanzetti
ana-andreea  stoica
florian  dörfler
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:57:10

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.

Main paper: 
 introduction: 
 Problem Description. Social networks play a fundamental role in the spread of information, as in the context of commercial products endorsement [18] , job vacancy advertisements [3] , public health awareness [27] , etc. Information, ideas, or new products can either go viral and potentially bring significant changes in a community or die out quickly. In this context, a fundamental algorithmic problem arises, known as Social Influence Maximization (SIM) [12, 13] . SIM studies how to strategically select a pre-specified small proportion of nodes in the social network, the early adopters or seeds so that the outreach generated by a diffusion process that starts at these early adopters is maximized. Consider, for example, a product endorsement campaign: the early adopters are strategically selected 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 to be an NP-hard problem [12] . 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 to ensure an equitable spreading of information. Indeed, real-world 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 [11, 25] .Related Work. The problem of SIM was first introduced in 2003 in Kempe et al. [12] , 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 a more recent history [6] . Several multiple group-level metrics of fairness have been proposed over the years [7] . They fall under the notions of equity [23, 10, 11] , equality [7] , max-min fairness [8, 30] , welfare [17] , 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. [10] optimize outreach under fairness 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. [7] 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 [8, 30] adopt a max-min strategy. Specifically, in Fish et al. [8] 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. [7] 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 fairness metrics and developing a new seed selection policy that strategically extracts and optimizes our proposed notion of fairness. Finally, 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 2 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 also common in real-world data and how our proposed framework can detect such undesired scenarios. This prompts us to study a novel fairness 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 a novel seeding algorithm that optimizes for both the group-wise total outreach (termed efficiency) and fairness. 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 a unifying framework that classifies the most celebrated information-spreading algorithms both in terms of fairness 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 β-fairness, with β being the tuning parameter for the fairness-efficiency trade-off. Finally, we design a new seedset selection algorithm that optimizes over the proposed β-fairness metric and enhances fairness with either a small trade-off or even improved efficiency. This novel approach provides a comprehensive evaluation and design tool that bridges the gap between fairness and efficiency in SIM problems. 
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 i ) i∈[m] the m groups of different sensitive attributes. In this paper, we consider m = 2 groups, noting that our framework is easily generalizable to more groups as discussed in Appendix B. We denote by ϕ G (S) the influence function of a seedset S over a network G, through some diffusion process. In other words, ϕ G (S) determines the set of nodes reached by the seedset under a diffusion process. Then, |ϕ G (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.), |ϕ G (S)| 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 a network G with two communities (C i ) i∈ [2] and a seedset S, we let x i , i ∈ [2] , denote the fraction of nodes in each community in the outreach ϕ G (S). The final configuration is the tuple (x 1 , x 2 ).In many definitions in the literature, fairness is operationalized as 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. [10] 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. 
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 1 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 information-spreading process via a probability distribution γ ∈ P([0, 1] × [0, 1]) over all possible final configurations. Informally, γ(x 1 , x 2 ) is the probability that a fraction x 1 of group 1 receives the information and a fraction x 2 of group 2 receives the information; e.g., γ(0.3, 0.4) represents the probability that 30% of group 1 and 40% of group 2 receive the information. We can marginalize γ to obtain the outreach probability distributions associated with each group; i.e., µ 1 ∈ P([0, 1]) and µ 2 ∈ P([0, 1]). Informally, we can write µ 1 (x 1 ) = x2 γ(x 1 , x 2 ). As in the example above, µ i (0.3) is the probability that 30% of group i receives the information.Motivating Example. Consider the SIM problem with nodes belonging to two groups, C 1 and C 2 , each group having the outreach probability distributionµ i = 1 2 δ 0 + 1 2 δ 1 , i ∈ {1, 2}, with δ k representing the delta distribution centered at k ∈ [0, 1].That is, in 50% of the cases all members in group i receive the information (i.e., we get x i = 1.0) and in 50% of the cases no one in group i receives the information (i.e., we get x i = 0.0). It is therefore tempting to say that this setting is fair since µ 1 and µ 2 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:γ a = 0.5 • δ (0,0) + 0.5 • δ (1,1) , γ b = 0.25 • δ (0,0) + 0.25 • δ (1,1) + 0.25 • δ (0,1) + 0.25 • δ (1,0) .with δ (i,j) , representing the delta distribution centered at (i, j) ∈ [0, 1] 2 . Interestingly, both γ a and γ b are "compatible" with µ 1 and µ 2 : If we compute their marginals, we obtain µ 1 and µ 2 . However,γ b γ a Figure 1: Illustration of the (γ a ,γ b ) example. % outreach group 2 % outreach group 1 (x 1 , x 2 ) (y 1 , y 2 ) z(x 1 , x 2 , y 1 , y 2 )Figure 2 : The transportation cost measures the length of the solid segment; shifts along the diagonal (dotted) are not considered for fairness and are only relevant for efficiency.γ a and γ b encode two fundamentally different final configurations. In γ a , the percentage of members of group 1 who get the information always coincides with the percentage of people of group 2.Conversely, in γ b , more outcomes are possible; in particular, there is a 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, γ a and γ b encode very different outcomes. We therefore argue that a fairness metric should be expressed in terms of joint probability distribution γ, and not solely based on its marginals µ 1 and µ 2 , as commonly done in the literature [23, 10] .Our motivating example prompts us to reason about fairness in terms of the joint probability measure γ, instead of its marginal distributions µ 1 and µ 2 . Since γ 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 c :([0, 1]×[0, 1])× ([0, 1] × [0, 1]) → R ≥0, the optimal transport discrepancy between two probability distributionsEQUATIONwhere Π(γ a , γ b ) is the set of probability distributions over([0, 1] × [0, 1]) × ([0, 1] × [0, 1]) so that its first marginal is γ a and its second marginal is γ b . Intuitively, the optimal transport problem quantifies the minimum transportation cost to morph γ a into γ b when transporting a unit of mass from (x 1 , x 2 ) to (y 1 , y 2 ) costs c((x 1 , x 2 ), (y 1 , y 2 )). The optimization variable π is called transportation plan and π((x 1 , x 2 ), (y 1 , y 2 )) indicates the amount of mass at (x 1 , x 2 ) displaced to (y 1 , y 2 ). Thus, its first marginal has to be γ a (x 1 , x 2 ) (that is, (x 1 , x 2 ) has to be transported to some (y 1 , y 2 )) and its second marginal must be γ b (y 1 , y 2 ) (that is, the mass at (y 1 , y 2 ) has to arrive from some (x 1 , x 2 )). If the transportation cost c is chosen to be a p ≥ 1 power of a distance d, then (W d p (•, •)) 1/p is a distance on the space of probability distributions. When the probability distributions are discrete (or the space [0, 1] is discretized), the transportation problem (1) is a finite-dimensional linear program and can therefore be solved efficiently [16] .Our proposed fairness metric. To operationalize the optimal transport problem (1), we therefore need to define (i) a transportation cost and (ii) a reference distribution γ * . To define the transportation cost, we start with the following two considerations. First, moving mass along the diagonal should have a cost of 0, as it does not affect fairness but only the efficiency (the proportion of population reached in respective groups). Second, moving mass orthogonally towards the diagonal should come at a price, since the difference in group proportion outreach between groups 1 and 2 decreases. We quantify this price as the Euclidean distance. This is 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 (x 1 , x 2 ) (e.g., belonging to γ a ) and (y 1 , y 2 ) (e.g., belonging to γ b ) into two components: one 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 costEQUATIONwhere z(x 1 , x 2 , y 1 , y 2 ) is the point indicated in green in Fig. 2 and ∥•∥ is the standard Euclidean norm. Thus, the "fairness distance" between two distributions γ a and γ b can be readily quantified by W c (γ a , γ b ). Since moving along the diagonal is free, we quantify the fairness of a given γ as its "fairness distance" from the "ideal" distribution γ * = δ (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 a network with communities (C i ) i∈ [2] , a SIM algorithm is said to be mutually fair if the algorithm propagation is such that it maximizesFAIRNESS(γ) := 1 - √ 2W c (γ, γ * ),where W c (γ, γ * ) is the optimal transport discrepancy, defined with the transportation cost (2), between the probability distribution γ and the desired probability distribution γ * defined as in (1) .The mutual fairness from Definition 3.1 can be seen as a normalized expression of W c (γ, γ * ) to contain its values in [0, 1]. Indeed, its lowest value is 0 and it is achieved with γ = δ (0,1) , for which is W c (γ, γ * ) = 1; its largest value is 1 and it is achieved with γ = γ * , for which W c (γ * , γ * ) = 0. Since γ * is a delta distribution, we can solve the transportation problem (1) in closed form toFAIRNESS(γ) = 1 - √ 2W c (γ, γ * ) = E (x1,x2)∼γ 1 -|x 1 -x 2 | , which reduces to FAIRNESS(γ) = 1 -1 N N i=1 |x 1,i -x 2,i | when the distribution γ is empirical with N samples {(x 1,i , x 2,i )} i∈[N ] .In particular, our fairness metric can also be interpreted in terms of the average distance between the outreach proportions within the two groups.Discussion. We note that while we considered two groups in the aforementioned definitions, our methodology readily extends the setting with m groups. We present this extension in Appendix B. Second, since moving mass "diagonally" is free, any distribution γ * supported on the diagonal yields the same fairness metric. In practice, it is often not the case that all the network members receive the information and the best one could hope for is to project γ onto the diagonal; since moving along the diagonal is free, the fairness cost is the same whether the ideal distribution is that projection or γ * . Moreover, it is easy to see that the "fairness distance" is symmetric, namely W c (γ a , γ b ) = W c (γ b , γ a ). Finally, our definition readily extends to any other distance function besides the standard Euclidean metric. Back to the motivating example. Armed with a definition of fairness that captures the nature of a diffusion process, we now revisit the motivating example in Fig. 1 . To start, we evaluate the "fairness distance" between γ a and γ b :W c (γ a , γ b ) = 1 4 • √ 2 2 + 1 4 • √ 2 2 = √ 2 4 ,which amounts to the cost of transporting the points (0, 1) and (1, 0), each with weight 1/4, to the diagonal. Notably, in contrast to simply computing the expected outreach of each group, our fairness metric distinguishes the two outcomes. Similarly, we can easily compute the fairness metric: FAIRNESS(γ a ) = 1 and FAIRNESS(γ b ) = 0.5. In particular, γ a achieves the highest fairness score. Indeed, its outcome will always be fair. Instead, FAIRNESS(γ b ) achieves lower fairness score, capturing the fact that in 50% of the cases the outcome is perfectly fair while in the remaining 50% it is largely unfair.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 (AV_{0-23}) [26] , APS Physics (APS) [14] , Deezer (DZ) [19] , High School Gender (HS) [15] , Indian Villages (IV) [1] , and Instagram (INS) [22] . Each dataset contains a social network with a chosen demographic dividing the population into two nonoverlapping 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 groupagnostic seed selection strategies as our baselines, namely degree centrality (bas_d), and greedy (bas_g), proposed by Kempe et al. [12] . 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 et al. [23] . To model the information spread, we use the Independent Cascade model (IC) for the diffusion of information [12] with a probability p ∈ [0, 1] for all edges. This process, being stochastic, is simulated R times in a 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-aware 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://github.com/nicolaslanzetti/fairness-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_g selection strategy and p = 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 ≥ 0.5 or p → 0), and cross-group interconnectivity (see Table 1 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 a 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 p = 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_0 dataset with p = 0.3, |S| = 4, and bas_g selection strategy. We observe a more stochastic outreach compared to Fig. 3b with variance spread along, but not on the diagonal, with a small bias towards one group. Also in this case, both the equity and the mutual fairness metrics characterize this outcome as fair, but mutual fairness is more informative as it requires outcomes to 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 a function of the conduction probability p. We consider the IV dataset as a 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 ∈ (0, 0.5), both metrics have an opposite trend: equity fairness increases to some extent whereas our metric suggests a huge fall in fairness in this region. For p ∈ (0.5, 0.7), there is a decrease in equity fairness, while our fairness evaluation remains relatively constant. We notice similar trends for both metrics only for p ∈ (0.8, 1.0). The significant difference in 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 Section 3.1 and Section 3.2. For more experiments on other datasets, we refer to Appendix D.2.To construct our fairness metric, we completely discarded the efficiency of the final configuration. For instance, the "fairness distance" between a configuration whereby no agent receives the information (i.e., γ = δ (0,0) ) and the "ideal" configuration whereby everyone receives the information (i.e., γ * ) is zero, as both probability distributions lay on the diagonal. As such, the fairness score of γ = δ (0,0) is 1 and therefore maximal. Thus, in practice, one seeks a fairness-efficiency tradeoff.In our setting, we can easily introduce the tradeoff in the transportation cost (2) . Specifically, we can define the transportation cost as a weighted sum of the "diagonal distance" (measuring difference in efficiency, dotted segment in Fig. 2 ) and the "orthogonal distance" (measures difference in fairness, solid segment in Fig. 2 ). Formally, for a given weight β ≥ 0, we define the transportation costEQUATIONWe refer to Fig. 5 for a heatmap of c β . In particular, for β = 1, we recover the transportation cost (2); for β = 0 one optimizes for efficiency, and the β-fairness collapses in the classical influence maximization problem. We can then proceed as in Section 3.1. The "β-fairness-efficiency distance" between γ a and γ b is W c β (γ a , γ b ) and the β-fairness metric can be then defined as follows.Definition 3.2 (β-Fairness) Consider a network with groups C 1 , C 2 , a SIM algorithm is said to be β-fair if the algorithm propagation is such that it maximizes The factors 1 and and √ 2/ max{1, 2 -2β} 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 yieldsEQUATIONβ-FAIRNESS(γ) = E (x1,x2)∼γ 1 - β|x 1 -x 2 | + (1 -β)|x 1 + x 2 -2| max{1, 2 -2β} .In particular, for β = 1, we recover the mutual fairness FAIRNESS(γ) in Definition 3.1 and for β = 0 we obtain the efficiency metricE (x1,x2)∼γ [1 -|x1+x2-2| 2 ].4 Improving Fairness 
fairness-promoting seed-selection algorithm: 
 Armed with a novel fairness metric, β-FAIRNESS, we now design an 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, E.3. For a given initial seedset, our algorithm explores new seeds and evaluates them on the efficiency-fairness metric β-FAIRNESS as in (4) for a desired value of the fairness-efficiency tradeoff parameter β (S3D_STEP() in Appendix E), to decide if the new seedset becomes a candidate for the optimized seedset. These seeds are searched for by iteratively sampling stochastically reachable nodes, up to a fixed depth, taken as a fraction of the graph diameter, from the current seedset (SEEDSET_REACH() in Appendix E) while making sure they contribute to a non-overlapping outreach (Algorithm 1::6-8). To prevent getting stuck at some local minima of the generally non-convex objective, the procedure allows for visiting inferior seedsets on β-FAIRNESS or even selecting completely random ones on rare occasions (Algorithm 1::12-18) using Metropolis Sampling [5] . Otherwise, a high β-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 β-FAIRNESS as the optimal seedset. For a sparse graph G(V, E), with E = O(V ),Are the outcomes more fair? We test our algorithm across a 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 of the resulting configuration. At the same time, efficiency either increases as well or suffers only a small decrease, as we investigate more in detail in our next experiment. Generally V S ← nodes reachable from S via cascade, using SEEDSET_REACH routine 4:Algorithm 1 Stochastic Seedset Selection Descent Input: Social Graph G(V G , E G ),S ′ ← {} 5:for |S| iterations do ▷ searching nearby states, V S ′ , to get S ′ (Appendix E.3) 6:S ′ ← S ′ ∪ {v} | v ∼ V S 7:V S ′ ← nodes reachable from S ′ in a fixed horizon, using SEEDSET_REACH 8:V S ← V S \ V S ′ 9:E S ← -BETA_FAIRNESS(S, β) ▷ expected potential energy defined on β-fairness 10:E S ′ ← -BETA_FAIRNESS(S ′ , β) 11:p accept ← min{1, e E S -E S ′ } ▷ S ′ acceptance on energy minimization Figure 6 : Demonstrate S3D (red) improvement over its label-blind baseline counter-part initializations (blue) for several datasets, propagation probabilities p, seed set cardinalities |S| and fairness-efficiency tradeoffs β. Fig. 6d provides the strongest evidence that, besides improving in fairness, our strategy can also be more efficient, from 83.1% to 87.9%.speaking, datasets with high cross-group connections (AH, DZ, INS) can already benefit a lot from label-blind seed selection to get moderately fair outreach. Similarly, for datasets with low cross-group connections (APS) a label-blind strategy, in order to maximize efficiency, selects a diverse population of seeds from which all communities are reached. Therefore, label-blind algorithms work similarly to S3D. In 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 for all datasets),. We consider the following algorithms: bas_d, bas_g, their fair heuristic counterparts, hrt_d, hrt_g, against our S3D_d, S3D_g, initialized via greedy and degree centrality baseline seeds, respectively. We show our results in Fig. 7 . S3D achieves in almost all cases the highest fairness score (y-axis) and generally a slightly lower efficiency score (x-axis), compared to others. Thus, our seed-selection mechanism leads to fairer outcomes with only a 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 is moderate, network topology starts playing a role, mainly through the number of cross-group edges (CE):CE% 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 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 in a fair outreach. Since bas_g already has proven near-optimal efficiency guarantees, it is unlikely that S3D performs significantly better than bas_g.CE% is moderate (5-30%, AV (datasets 0, 2, 16, 20), IV): These are the non-trivial cases not covered above. Here bas_g can not reliably leverage the existence of edges into group information. Hence, S3D usually outperforms the baseline, achieving similar efficiency scores while significantly improving fairness.The case where nodes interact more across groups than in their own groups was never observed. However, as long as the existence of edges does not reliably signal group information, we expect S3D to perform well based on a similar analysis.For graphs where |E| substantially exceeds |V |, the outreach variance across sample sub-graphs is too low to be captured in the discretized space we experimented (100×100 units in [0, 1] 2 ), even for moderate p. This leads to single-point concentrated joint-distribution plots, all of them leading to the same β-FAIRNESS. 
conclusions and limitations: 
 Conclusions. We propose a new fairness metric, called mutual fairness, in the context of SIM. Mutual fairness draws on optimal transport and captures various fairness-related aspects (e.g., when members of group 1 receive the information will members of group 2 receive it?) that are obscure to 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, is essentially a random combinatorial search in the 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. 
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, no one of group A receives the information and everyone in group B receives it 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 a new seed-selection algorithm that optimizes both outreach and our new fairness metric, and we 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 or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe 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)?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 releasing unsafe images.• We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: 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? 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 a 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 use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is 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 of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 as details about compensation (if any)? Answer: [NA] Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main 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. 
 
 Appendix: Definition A.1 (Expected outreach ratio) Given a network with communities C 1 , . . . , C m , the SIM algorithm expected outreach ratio in C i , xi , is the expected ratio of nodes reached in C i , namelyxi := E[|v reached |v ∈ C i |] |C i | , ∀i ∈ {1, . . . , m}.Definition A.2 (Equality [23] ) Given the groups C 1 , . . . , C m , a configuration is said to be equal, if the SIM algorithm chooses a seed set S in a way such that the proportion of all communities in the seed set is the same, namelyE[|v ∈ S|v ∈ C i |] |C i | = E[|v ∈ S|v ∈ C j |] |C j | ∀i, j ∈ {1, . . . , m}.The notion of equality focuses on the fair allocation of seeds to the groups proportional to the size of the group within the population. This notion of fairness applies, for example, in the context of advertising companies that aim at having a fair distribution of resources among groups.Definition A.3 (Equity [23] ) Given a network with communities C 1 , . . . , C m , a SIM algorithm that selects a seedset S is said to be equitable if the algorithm propagation reaches all communities in a balanced way, i.e. xi = xj , ∀i, j ∈ {1, . . . , m}.The notion of equity focuses on the outcome of 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 a calibrated way.Definition A.4 (Max-min fairness [7] ) Given the groups C 1 , . . . , C m , the max-min fairness criterion maximizes the minimum expected outreach ratio among all groups, namely max min i∈{1,...,m} xi .The goal of the maxmin fairness is to minimize the gap among different groups in the outreach. The SIM problem under maxmin constraints has been investigated in [7, 8, 30] .Definition A.5 (Diversity [7] ) Given the groups C 1 , . . . , C m , letk i = k • |Ci| |V | ,where k is the pre-specified total seed budget. Let x * i (C i ) := max S⊂Ci:|S|=ki xi . A configuration is said to be diverse if for each i ∈ {1, . . . , m} it holds xi ≥ x * i (C i ), where xi refers to the expected outreach ratio in C i 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 [7, 25] .In this section, we extend our definitions of mutual fairness and β-fairness to the setting of m groups.To do so, we first notice that, in the case of m groups, the outreach distribution is a probability distribution γ on the hypercube [0, 1] m ; i.e., γ now lives in P([0, 1] m ).We start with the definition of mutual fairness. We proceed as Section 3.1 and define mutual fairness via optimal transport, which, in turn, requires defining a reference distribution and a transportation cost. The reference distribution is again the "ideal" distribution γ * = δ (1,...,1) which encodes the case in which all members of all groups receive the information. As for the transportation cost, it suffices to generalize the transportation cost (2) to an m dimensional space. Specifically, it can be defined as the distance between any given point (x 1 , . . . , x m ) ∈ [0, 1] m in the hypercube and the diagonal line. For this, let z(x 1 , . . . , x m ) = argmin z=(y,...,y),y∈[0,1]∥(x 1 , . . . , x m ) -z∥ = x 1 + . . . + x m m (1, . . . , 1)be the closest point to (x 1 , . . . , x m ) on the diagonal. Then, the transportation cost can be defined as in (2) and the fairness metric readsFairness(γ) = 1 -αE (x1,...,xm)∼γ [∥z(x 1 , . . . , x m ) -(x 1 , . . . , x m )∥] = 1 -αE (x1,...,xm)∼γ min z∈[0,1] ∥(x 1 , . . . , x m ) -(z, . . . , z)∥ ,where the constant α > 0 is again chosen so that Fairness(γ) is between 0 and 1. Note that in the case of two groups, we have z = 1 2 (x 1 + x 2 ) andmin z∈[0,1] ∥(x 1 , . . . , x m ) -(z, . . . , z)∥ = √ 2 2 |x 1 -x 2 |,with which is precisely the mutual fairness of Definition 3.1.We now turn our attention to β-fairness. We can proceed analogously and obtainβ-FAIRNESS(γ) = 1 -αE (x1,...,xm)∼γ [β∥z(x 1 , . . . , x m ) -(x 1 , . . . , x m )∥ + (1 -β)∥z(x 1 , . . . , x m ) -(1, . . . , 1)∥],where α > 0 is again chosen to normalize the metric. Again, in the case of two groups, we have z = 1 2 (x 1 + x 2 ) and soβ-FAIRNESS(γ) = 1 -αE (x1,...,xm)∼γ β √ 2 2 |x 1 -x 2 | + (1 -β) √ 2 2 |x 1 + x 2 -2| ,which coincides with Definition 3.2.We conclude with two remarks on this extension to m groups. First, as in the case of two groups, there is no need to 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 multimarginal optimal transport problem, which might cause exponential complexity in the dimensionality.To associate the notion of fairness developed in Sections 3.1 and 3.3 with the datasets and the outcomes from experiments in Section 3.2 and 4.2, we summarize the dataset statistics in Table 1 . Minority Frac. is calculated as the fraction 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 a more homophilic network.Add Health (AH). The Add Health dataset consists of a social network of students in schools and a relation between them is represented by whether they nominated each other in the Add Health surveys. We select a school at random with 1, 997 students and use race as the sensitive attribute (white and non-white). 2Antelope 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 a fair comparison. The two sensitive attribute groups are male and female, self-reported in the dataset with binary attributes. APS Physics (APS), [14] . 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. [14] analyze, the dataset has high homophily, meaning that each subfield cites more papers in its own 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 two groups, for this study.Deezer (DZ), [19] . A social network from Europe with 18, 442 nodes, where each node has a self-reported attributed gender (male or female). Men are the minority (44.3%) and women are the majority (55.6%). The data has moderate homophily.High School (HS), [15] . A high school friendship network collected from Mastrandrea et al. [15] , with 133 nodes in its main connected component represented by students who self-identify as male or female. The majority are female (60%), and the network is 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 Mothertongue (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. [22] . An interaction network from Instagram containing 553, 628 nodes, where everyone has a labeled gender (45.57% men and 54.43% women). Each edge between two users represents a 'like' or 'comment' that one user gave another on a posted photo. The data has moderate homophily.We use R = 1000 throughout our experiments. For the outreach, we discretize the space [0, 1] × [0, 1] into 100 × 100 equal sized bins. For S3D (refer to Appendix E), we use constants, exploit_to_explore = 1.3, non_acceptance_retention_prob = 0.95, and shallow_horizon = 4.We report additional experiments in Figs. 8 to We provide more details on our algorithm, S3D, in two routines, Algorithm 2 and Algorithm 3. + R|V | + log R|V |) + 2(R(|V | + |E|) + R) + |S| log |V |) = O(|S| log |V | + R(|V | + |E|) + R|S| + R|S||V | + |S| log |V |) = O(|S| log |V | + R|S||V |) = O(R|S||V |).Here, we used the assumption that d avg = O(2E/V ) = O(1) for a sparse graph (E = O(V )). Now this S3D_STEP is run k times using S3D_ITERATE to find the best seedset in these k runs. Moreover, we avoid any redundant calculations and memorize β-fariness for any seedset we discover. Hence, the total runtime is O(kR|S||V |), as claimed.The S3D approach to β-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 t = 0, amongst exponentially many choices of actions, can lead a system to one of exponentially many states, for which we know the probability distribution of the system achieving one of these states and an associated, possibly non-convex, expected energy profile resulting from this stochastic state occupancy of the system at a 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 a gradual reduction of the expected potential energy of the resulting system using Metropolis Sampling/Simulated Annealing.In this study, the initial action at t = 0 is the initial seedset choice S, which leads to a distribution of states, called the Outreach distribution on final configuration (Theorem 2.1), that the system, a Social Network here, can reach to. Each such distribution corresponds to a bounded expected "potential energy" (keeping the ideally mutually fair distribution as reference) defined on β-fairness-a mutually fair configuration is defined to be a "stable", less "energetic" system, and S3D aims to achieve it via an optimal choice of S, S * .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.Let f : P(V ) → [0, 1] be the β-fairness set-evaluation function defined in the power-set of the graph vertex set V . The function can then evaluate any seedset, S ⊆ V for its β-fairness. Now for iterative optimization purposes, S3D defines a sampling process to define neighbors S ′ of S, based on similar outreaches V S ′ and V S . Then S3D essentially followsnon-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.While 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 ∈ [500, 1000] usually works well in practice. Hence any decaying temperature schedule that translates total iterations in this range should work fine.Consider the information spreading over the graph in Fig. 15 as an independent cascade model with probability p = 0.1, with blue and red nodes belonging to two different groups. A greedy strategy would choose the seed set as S g = 3, 5 (enlarged nodes) as shown in Fig. 15a , thus leading to the highly unfair outreach in Fig. 15b . On the contrary, our algorithm S3D promotes the choice S S3D = 1, 4 reflected in 15c, which gives the more fair outreach plotted in Fig. 15d , showing that it improves over greedy/sophisticated label-blind seed selection strategies. The enlarged nodes are selected seeds. Since the graph is small, the outreach discretization bucket have been granularized for improved readability.Referring to Fig. 7 , we mention 2σ symmetrical error 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 All experiments were performed on a local PC on a single CPU core 3.5 GHz. Except for datasets DZ, INS, all datasets were loaded and operated on a 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.10+, numpy, jupyter, and networkx [9] . Runtime for each non-S3D configured experiment on datasets except DZ, INS, was 10 -15 minutes. For DZ, INS, this was approximately 1 -2 hours. For S3D optimizations to be satisfactory, we ran each small dataset (except DZ, INS) for 1.5 hours additionally. For massive datasets DZ, INS, the compute cluster took ∼ 4 days for k = 10 steps. The total set of experiments made, including the failed and passed or submitted ones, roughly took the same order of resources separately.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).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 is currently directed by Robert A. Hummer and funded by the National Institute on Aging cooperative agreements U01 AG071448 (Hummer) and U01AG071450 (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 at the University of North Carolina at Chapel Hill. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: **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.

**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.

**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.

**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.

**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.
questions: questions: In addition to the weaknesses I mentioned above, I also have some minor concerns.

**Q1**: Please explain $\delta_{(i,j)}$ in the paper.

**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).

**Q3**: The authors should state clearly that which notion is $hrt_g$ based on, equity or equality?

**Q4**: In Figure 4, I believe that the y-axis should be $1-diff.$ in exp. outreach.

**Q5**: When $\beta=0$, does $\beta$-fairness degenerate to the classic IM problem?

**Q6**: Please explain the "fixed horizon" in Algorithm 1.

**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.

**Q8**: I am confused by the weird phenomenon where results in Figure 5(b-d) appear as discrete rectangles. Any explanation?
limitations: 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.
paper_summary: paper_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.

After 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.
strength_weakness: strength_weakness: 1) Lack of theoretical guarantees for the S3D algorithm.
questions: questions: Shouldn't $\gamma$ be $\pi$ in line 184, in the definition of mutual fairness?
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: How does the mutual fairness metric perform in extremely large networks, and what are the computational challenges associated with scaling the approach?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. In Definition 2.1, V is the network. Late in section 3.2, V is the set of nodes.

2. 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.

3. The generalizability from two groups to multi-groups should be demonstrated in detail.
questions: questions: I still don't understand why the example scenario is unfair.
limitations: limitations: Limitations are discussed.

Comments: title: Comment from Reviewer 1BeY disappeared
Accept
comment: Dear Area Chair, 

we wanted to notice you about  this comment 

"I thank the authors for providing clarification and the extra explanation on the generalizability to mullti-groups. The rebuttal solved most of my concerns. I still don't quite agree with Q1, but it is not critical in the paper. Thus, I would like to raise the score to 5."

 from reviewer 1BeY.  We are not sure if there is any technical problem on the platform but the comment is not visible to us anymore. However, we can still see the comment among our notifications.

Thank you very much for your help.

The Authors
The introduction of the mutual fairness metric represents a significant contribution. And, the author addressed my issue.