Scalable Fair Influence Maximization

Summary

The paper proposes an algorithm for fair influence maximization. The objective is defined as a sum of powers of a utility function for each cluster, indicating that each cluster should receive some influence. Reducing the exponent will bring the objective to a fairer distribution of influence. An algorithm based on max cover on reverse reachable sets is presented. Optimal number of sets are derived to guarantee $(1-1/e - \epsilon)$-approximation

Strengths

- The key idea to convert the powers into sums using the binomial theorem is elegant, as it helps with modifying the existing algorithm on influence maximization for the proposed objective. - Detailed derivations are presented.

Weaknesses

- Baselines: While the theoretical guarantee is the key contribution, the experiment part of the paper can be strengthened. How much do we gain from this algorithm compared to some simple heuristics? One may consider simple heuristics like degree. Better heuristics may also be generated, e.g., (1) picking high-degree nodes from each cluster, and (2) using the RR sets in Algorithm 1 but performing max-cover without Eq (5) [maybe similar to performing Influence Maximization independently in each cluster] - The derivation assumes that a fair solution exists, in the form of $b = \max \mathbf{u_c} (S^{\\#})$. The usage of this appears in the proofs, but some indication of how this would impact the main results could be discussed. - The symbol $n$ is overloaded. It is used as an index for the summation as well as the number of nodes. I think the paper will benefit from a table of symbols.

Questions

- Please see the issues raised in "Weaknesses" - Do we need the constraint $\alpha > 0$? My intuition is that the method will work with negative $\alpha$ as well, but it needs to be carefully analyzed.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Minor issue: A discussion on the impact of the assumptions could be included.

Summary

The authors apply fairness to the influence maximization problem (IM). On a social network, IM models which node subset should be used to trigger the spread of information to maximize its effects. A motivating application is the selection of leaders for natural disaster preparedness, where in existing methods, minority leaders are disproportionately underrepresented. They are not the first to do this, however they are the first to introduce efficient algorithms for solving IM with welfare fairness, which allows the user to parametrize an objection on sliding scale between total fairness and no fairness at all (i.e., maximum influence spread). They work in the Independent Cascade model of influence spreading, where each node has a given probability of influencing an adjacent node, and influence is randomly spread according to these probabilities across a number of timesteps. The influence spread, i.e. the objective, is the number of influenced nodes when the process converges. By submodularity, the unfair problem can be solved greedily to a (1-1/e) approximation factor. They assume the given graph is separated into a small number of communities to apply their fairness notion to. While this also admits a greedy approach via Monte Carlo methods, it requires too long to run. Their main contribution is a (1-1/e-epsilon) approximate and efficient solution to IM under welfare fairness. En route, they provide an unbiased estimator of the fair objective under a number of random seeds for which edges spread influence when. This is harder than the vanilla problem because the objective is raised to a power alpha in [0,1] as opposed to just 1. They show how to use a Taylor series to provide an unbiased estimator. This is used to then compute the marginal expected gain in influence of adding a vertex to their set and thus greedily select the best one. They also experimentally validate their results on five different, semi-synthetic data (e.g., for their Flixster data, they had to construct community information). They show that the price of fairness and effect of fairness both decrease as the alpha parameter increases, which makes sense since that decreases the fairness impact on the objective. They also show that adding more influence budget generally decreases the price and effect of fairness.

Strengths

To my knowledge, the theoretical results of this paper are substantial and original. It’s always interesting and practical to see how notions of fairness apply to different problems. They are the first to efficiently solve IM under welfare fairness, and their proposal of an unbiased estimator for the marginal influence spread of a vertex seems notable, though I am not particularly familiar with influence literature (e.g., it is possible these methods are pretty standard for influence spreading strategies). From my standpoint, it is a nice result with a solid place in fairness literature.

Weaknesses

While I think the paper is reasonably clear, it can be quite dense at times with its heavy use of notation. I found it particularly hard to follow in Section 3.4, when they pretty much state two lemmas and a theorem, deferring most proofs to the appendix. I think it’s better to explain these things at a high level more and defer formal statements to the end. It was hard to make much of it. In general, I would prefer the paper to undergo more edits for clarity, particularly in Section 3.4, before publication.

Questions

1. A big value of your work is that your algorithm is efficient. Do you have any experiments that evaluate the efficiency? 2. Can you give a high level discussion of the results from Section 3.4? 3. For someone not in the area of influence spreading, can you discuss how natural the welfare fairness metric is? It's somewhat unintuitive at a glance. 4. Big question: what is the runtime of your algorithm?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I do not see a limitations section. Most papers have limitations of one kind or another, even highly theoretical ones like this. However, I don’t think it is the most necessary in this case, as no subjects are involved and they are only suggesting a general tool.

Summary

The authors study a variant of the popular influence maximization problem that incorporates fairness constraints. Given a partition of the node set of the graph into communities, the goal is to select seeds subject to budget constraints that maximizes influence as well as reduces the influence gap between communities. The authors consider a particular notion of fairness called welfare fairness, where a single parameterized objective function can be used to achieve the desired balance between maximizing influence and maintaining fairness. The objective function is monotone submodular, and therefore, the greedy algorithm guarantees a constant approximation factor as in the case of the traditional influence maximization problem. Since the greedy algorithm is not scalable to large networks, this paper focuses on developing an efficient algorithm using the reverse influence sampling (RIS) approach. The main contributions are an unbiased estimator for the fractional power of the arithmetic mean using Taylor expansion, solving a main hurdle for using RIS approach for welfare fairness objective function, and an analysis of the greedy algorithm based on the RIS approach. Experiments are carried out on five social networks to study the trade-off between fairness and influence spread.

Strengths

The paper addresses an important topic of scalability in influence maximization with fairness. The unbiased estimator for the fractional power of the arithmetic mean is a significant contribution of this paper, which could be applicable to other problems as well. The paper addresses important computational and approximation related aspects. The paper is generally well written.

Weaknesses

The importance of/need for the unbiased estimator is not discussed. Firstly, in Section 3.1, it is pointed out that (\hat{u}_c)^\alpha is a biased estimator of u_c^\alpha. Suppose we were to use it, how bad would the outcome be? A second related issue is that the paper does not comment on the complexity of computing the unbiased estimate. When the number of RR sets is large, updating according to equation (5) can be compute intensive (Algorithm 2 line 11). Also, some approximation of equation (5) must be involved as the summation over n goes from 1 to infinity. The authors do not seem to discuss about the truncation of the Taylor series and its effect on the accuracy. In Theorem 1, the role of \epsilon is not clear. It does not seem to feature in the probability expression or have anything to do with the size of the RR set. In Lemma 4, it is mentioned, but again, its role is not at clear. Experiments section could be much stronger: Considering that the key problem addressed by the paper is scalability, the experiments section does not provide any analysis of the computation time of the algorithm and how it scales with the size of the networks. It also does not provide any analysis regarding how truncation of higher order terms in the Taylor series affect the performance. Thirdly, there is no analysis of how it scales with the size of the RR set. Minor comments: Line 82: "However, these notions can hardly ..." It would be better if this sentence was supported by references. Line 197: that covered ... -> that are covered ... Line 219: then it holds ... -> then the following holds: ... Line 231: ... holds at least ... -> holds with probability at least ...

Questions

There are some questions in the Weaknesses that need to be addressed. In algorithm 1, line 6, is it sample with replacement? In algorithm 1, line 9, what if c(v) is same as c(u)? In algorithm 2, line 20, what is \eta(v)? What is \Theta in Lemma 3? It is not defined anywhere.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Limitations not adequately addressed. No negative societal impact.

Summary

This paper aims to study the problem of fairness-aware influence maximization over a community structure under a welfare fairness notion that balances fairness level and influence spread using an exponentially-weighted sum over communities objective with an fractional exponent parameter α expressing inequality aversion. Given an unbiased estimator for the fractional powers from [27], a reverse-influence-sampling approach, adapted from previous works, is applied to the problem that turns the problem into a weighted maximum coverage problem. The number of reverse reachable (RR) samples needed to achieve a good approximation and an algorithm is given that achieves a 1 − 1/e − ε approximation.

Strengths

S1. Revisiting an important problem with an aim to efficiency. S2. Lucrative application of reverse influence sampling approach. S3. Approximation guarantees.

Weaknesses

W1. Limited novelty with respect to previous work in [7]. W2. Lack of discussion of the most basic problem case of full fairness. W3. Lack of discussion of and comparison to most recent related work.

Questions

The solution relies on a submodularity of the objective function and the accompanying analysis in [7]. However, there is no discussion of what happens in the most interesting case from the point of view of fairness, namely as α tends to 0. According to previous works, the objective is not submodular in exactly that case. This matter deserves discussion yet it is not addressed. The work pays no attention to more recents works in the area, such as [A, B]. There is no experimental comparison to the algorithms developed in those works, which, at least the ones in [A], also claim efficiency, and no discussion in terms of the framework presented in [B]. [A] Fish et al.: Gaps in information access in social networks? WWW 2019. [B] Farnadi et al.: A unifying framework for fairness-aware influence maximization. Companion of The Web Conference 2020.

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The paper offers a discussion on the ethical side of the objective aimed for.

We look forward to the reviewers' reply

We thank all the reviewers again for their insightful comments and constructive suggestions. We valued all the feedback and made a great effort in writing our responses. We want to kindly draw your attention that it has been a week since we submitted our responses, would you mind letting us know if our responses address your concerns? If you find there are other issues, please kindly let us know, we are happy to follow up with you before the discussion phase ends.

A comparison to the work of Fish et al. is due.

Thank you for your response. The fact that MMF is introduced in this paper does not constitute a valid reason to not discuss and not compare to [A]. On the contrary, is a comparison is due exactly for this reason.

Questions about Theorem 1

I thank the authors for carefully answering most of my questions in a satisfactory manner. I had two questions based on the response. 1. Shouldn't Theorem 1 have $\theta$ in the statement? All the guarantees hold only if you have adequate number of RR sets. $\theta$ should appear in Theorem 1 as it appears in the Lemmas. 2. In Lemmas 3 and 4, it seems like as $Q$ is increased, the number of RR sets required also increases. What is the intuition behind it? Smaller the $Q$, the less accurate the estimation. Wouldn't this mean that we need more RR sets to compensate for error in estimation?