Fairness in Social Influence Maximization via Optimal Transport

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.

Strengths

The new metric for fairness in influence maximization is refreshing and innovative. Examples 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. 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

I still don't understand why the example scenario is unfair.

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

Limitations are discussed.

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.

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

Questions

How does the mutual fairness metric perform in extremely large networks, and what are the computational challenges associated with scaling the approach?

Rating

8

Confidence

5

Soundness

4

Presentation

4

Contribution

4

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.

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.

Strengths

1) Very interesting novel concept of fairness for SIM. 2) Solid results with extensive experimental evaluation. 3) Excellent presentation.

Weaknesses

1) Lack of theoretical guarantees for the S3D algorithm.

Questions

Shouldn't $\gamma$ be $\pi$ in line 184, in the definition of mutual fairness?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

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.

Strengths

**S1**: Presenting a novel notion of fairness in IM which seems really appealing to me. **S2**: Evaluating the level of fairness via optimal transport. **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. **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

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?

Rating

5

Confidence

5

Soundness

3

Presentation

2

Contribution

3

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.