Source-linked AI summary
Group-Fairness in Influence Maximization
Alan Tsang, Bryan Wilder, Eric Rice, Milind Tambe, Yair Zick
TL;DR
Whether influence-maximization interventions distribute benefits fairly across groups remains an understudied question, particularly for smaller and marginalized groups. The paper formalizes fairness criteria and develops algorithms for them; its experiments find that diversity constraints reduce fairness violations at relatively little cost to overall utility.
Problem
Fair distribution of influence-maximization benefits across groups is understudied, despite the importance of avoiding disproportionate exclusion of smaller and marginalized groups.
Source: §1 · p. 1Method
The paper defines maximin fairness and diversity constraints, then develops algorithms that reduce fairness optimization to multi-objective submodular optimization.
Source: §1 · p. 1Results
Takeaways & Limitations
The price of fairness can be unbounded, so fair outcomes may carry a substantial cost relative to unconstrained influence maximization.
Source: §6 · p. 6The analogous construction for Maximin Fairness demonstrates a similar result only as p approaches 1/3 from below.
Source: §4 · p. 5
Abstract
from arXiv · showhide
Influence maximization is a widely used model for information dissemination in social networks. Recent work has employed such interventions across a wide range of social problems, spanning public health, substance abuse, and international development (to name a few examples). A critical but understudied question is whether the benefits of such interventions are fairly distributed across different groups in the population; e.g., avoiding discrimination with respect to sensitive attributes such as race or gender. Drawing on legal and game-theoretic concepts, we introduce formal definitions of fairness in influence maximization. We provide an algorithmic framework to find solutions which satisfy fairness constraints, and in the process improve the state of the art for general multi-objective submodular maximization problems. Experimental results on real data from an HIV prevention intervention for homeless youth show that standard influence maximization techniques oftentimes neglect smaller groups which contribute less to overall utility, resulting in a disparity which our proposed algorithms substantially reduce.
1 Introduction
The paper addresses whether influence-maximization interventions distribute benefits fairly across groups, including smaller or marginalized groups. It proposes fairness concepts and algorithms, analyzes the cost of fairness, and evaluates the approach on HIV-prevention networks.
1 Introduction
- Influence maximization selects k seed nodes to activate as many people as possible through successive neighbor-to-neighbor activation.The motivating applications include outreach such as HIV-safety information and health services for at-risk youth.Source: §1 · p. 1
- The paper introduces fair resource allocation in influence maximization through maximin fairness and diversity constraints.Maximin fairness seeks to maximize the minimum fraction of each group influenced; diversity constraints tie each group’s influence to its demand based on a seed allocation proportional to group size.Source: §1 · p. 1
- Fairness objectives become strongly non-submodular, so the paper reduces them to multi-objective submodular optimization and improves on the guarantee of Udwani [2018].The new method often has better runtime as well.Source: §1 · p. 1
- The price of group fairness—the reduction in social welfare relative to unconstrained influence maximization—can be high under both fairness concepts and across a range of settings.The paper analytically explores this cost.Source: §1 · p. 2
- The proposed framework reduces fairness violations found with standard influence-maximization techniques on real-world HIV-prevention networks, at relatively small cost to overall utility.The paper reports that standard techniques often neglect small groups.Source: §1 · p. 2
- Prior work had applied influence maximization in socially sensitive settings, but the authors report no previous work specifically considering fairness in influence maximization.Their fairness-optimization techniques relate to multi-objective submodular maximization outside the fairness context.Source: §1 · p. 2
2 Model
The model represents people as nodes, allows individuals to belong to overlapping groups, and models spread with the independent cascade process. It defines two fairness criteria: minimum proportional influence and group-specific influence benchmarks based on proportional seed allocations.
2 Model
- The independent cascade model starts with k activated seeds; each activated node independently attempts to activate inactive neighbors with probability p.Groups may overlap, allowing individuals to belong to multiple groups and represent intersectionality.Source: §2 · p. 2
- Influence I_G(A) is the expected number of nodes activated by seeding A.The model also defines group influence as the expected number of activated vertices belonging to a group.Source: §2 · p. 2
- Maximin fairness seeks to maximize the minimum influence received by any group in proportion to its population.This may require many seeds for a poorly connected group even when additional seeds have little impact.Source: §2 · p. 2
- Diversity constraints require each group to receive at least the influence it could generate within its own induced subgraph using a seed allocation proportional to its population.The allocation is rounded up: k_i = ceil(k|C_i|/|V|).Source: §2 · p. 3
3 Optimization
The section reduces group-fair influence objectives to multiobjective submodular maximization, then develops an improved algorithm for that problem’s continuous optimization step. Its guarantees approach the optimal asymptotic approximation under stated conditions, with efficient stochastic gradient oracles for influence maximization.
3 Optimization
- Both fairness objectives violate submodularity, so the standard greedy approach does not apply; each fairness concept is instead reduced to multiobjective submodular maximization.For diversity constraints, the objectives include each group’s influence and total influence, with targets set through feasibility search.Source: §3 · p. 3
- The practical algorithm improves the prior asymptotic approximation factor and has runtime comparable to, and often faster than, Udwani’s algorithm.The runtime advantage depends on oracle implementations and can be substantial when n grows faster than k, b, and c.Source: §3 · pp. 3–4
- MULTIFW improves the continuous optimization step, simultaneously optimizing multilinear extensions and using stochastic saddle-point mirror descent to find progress across active objectives.An objective remains active when its target value exceeds its current value by at least ϵ; the method uses stochastic gradients when exact gradients may be intractable.Source: §3 · pp. 3–4
- As k grows with m=o(k log^3 k), the approximation ratio can approach 1−1/e.Algorithm 1 also gives a guarantee for feasible target values, with its precise factor truncated in the supplied passage.Source: §3 · p. 4
- For influence maximization, the authors provide stochastic gradient oracles running in O(kn log n) time, versus O(n^2) for naive extensions of prior methods.The oracles use a randomized method to estimate many gradient entries simultaneously.Source: §3 · p. 4
4 Price of Fairness
The analysis shows that the price of fairness can be unbounded under both fairness definitions. It also demonstrates that overlapping group membership can worsen that price, even when only one node joins an additional group.
4 Price of Fairness
- Both fairness definitions can have an unbounded price of fairness; the Maximin result is stated in the appendix.For the Rational definition, the price diverges as n grows and p approaches zero.Source: §4 · p. 5
- Adding a single node to a second group can worsen the price of fairness by an arbitrarily large amount.The analysis uses undirected graphs, and the authors note the result also holds for directed graphs.Source: §4 · p. 5
- In a two-component, two-group setting with one seed, fair optimal seeding uses x2 for expected influence 1+ps; making x1 a member of both communities forces fair seeding of x1, yielding 1+p.Source: §4 · p. 5
- The Maximin construction demonstrates a similar unbounded-price result only as p approaches 1/3 from below.The passage characterizes this as a more technical construction.Source: §4 · p. 5
5 Experimental results
On homeless-youth networks, diversity constraints reduced fairness violations while retaining competitive minimum group influence at a relatively small price in overall influence. Results on simulated Antelope Valley networks were broadly similar, with exceptions for region and gender.
5 Experimental results
- Greedy produced the highest diversity-constraint violations and the lowest minimum influenced fraction, reaching near-zero maximin value for sexual orientation.Across the four homeless-youth networks, each had 60–70 nodes; the experiments fixed k = 15 seeds and averaged 30 runs per network.Source: §5 · pp. 5–6
- 55–65%: DC reduced diversity-constraint violations while remaining competitive on the maximin metric; fairness costs were 1.05–1.15 for both fair methods.Maximin generally achieved the best minimum group influence but performed worse on diversity-constraint violations, consistent with a focus on poorly connected groups with diminishing returns.Source: §5 · p. 6, Figure 1 · p. 6
- For overlapping race and birth-sex groups, constraint violations rose somewhat, while the price of fairness remained 1.07 for DC and 1.13 for Maximin.The experiment assigns each node to two groups.Source: §5 · p. 6
- On simulated Antelope Valley networks, results were broadly similar, but the maximin price of fairness exceeded 1.4 for region and stayed below 1.2 for the other attributes.Greedy had slightly higher gender maximin performance, likely because the network was well-mixed across genders and diversity-constraint violations were extremely low.Source: §5 · p. 6
6 Conclusions
The paper formalizes group fairness for influence maximization, develops algorithms for fairness-constrained solutions, and studies their price in social welfare. On real-world data, standard methods often neglect smaller groups, while diversity constraints substantially reduce violations at relatively little cost to overall utility.
6 Conclusions
- The paper concludes that diversity constraints can help smaller groups receive fair resource allocation at relatively little cost, despite standard influence maximization often neglecting them.The paper also establishes that the price of fairness can be unbounded and proposes an improved algorithm for multiobjective maximization.Source: §6 · p. 6
A Price of fairness
The analysis shows that both maximin and group-rational utilities are not submodular, and that maximin fairness can have an unbounded price of fairness. The constructions illustrate how group structure and seeding choices produce these results.
A Price of fairness
- Theorem 4.2 states that the price of maximin fairness is unbounded.In the construction, the optimal seed can leave one group with zero influence, whereas a maximin-fair seed gives positive influence to both groups and lower total influence.Source: A Price of fairness · p. 8
- Neither maximin utility nor group-rational utility is submodular.For maximin utility, adding x yields no gain in one configuration but raises utility from 1/2 to 1 in the other; group-rational utility likewise has a larger marginal gain after adding x to the larger set.Source: A Price of fairness · p. 8
- The section also presents a group-rational utility that is zero when its constraints fail and equals influence when they are satisfied.In the example, only seeding all vertices satisfies the group-rational constraints.Source: A Price of fairness · p. 8
- Adding a node to a second group can worsen the price of maximin fairness by an arbitrarily large amount.The result is illustrated by modifying group membership in the graph construction.Source: A Price of fairness · pp. 8–9
B Analysis of multiobjective submodular maximization problem
The appendix analyzes an algorithm for meeting multiple monotone submodular target values under a cardinality budget. It combines thresholding, a multiobjective optimization subroutine, and swap rounding, with guarantees approaching the 1 − 1/e approximation ratio as k grows when m = o(k log^3 k.
B Analysis of multiobjective submodular maximization problem
- The method is designed for monotone submodular objectives with target values and a cardinality budget, improving runtime and approximation ratio over Udwani [Udwani, 2018].Its feasibility formulation assumes a set meeting every target exists.Source: B Analysis of multiobjective… · p. 9
- The algorithm thresholds high-value items into S1, optimizes residual targets over a uniform matroid polytope, then swap-rounds and outputs S1 ∪ S2.The second step is identified as the key step for improving runtime and approximation ratio.Source: B Analysis of multiobjective… · p. 9
- The framework uses stochastic singleton-value, multilinear-extension gradient, and item-gradient oracles.The item-gradient oracle may be simulated from the gradient oracle, but can admit more efficient implementations.Source: B Analysis of multiobjective… · p. 9
- Theorem D guarantees a point meeting every target within multiplicative and additive error, with probability at least 1 − δ.The stated guarantee is Fi(xT) ≥ (1 − ϵ) … Wi − ϵ for all i; the supplied theorem text omits the factor following (1 − ϵ).Source: B Analysis of multiobjective… · p. 10
- As k grows, the algorithm’s approximation ratio can approach 1 − 1/e when m = o(k log^3 k.For feasible target values, Theorem E gives fi(S) ≥ (1 − …)Wi − ϵ with probability at least 1 − δ; the supplied theorem text omits the approximation factor inside the parentheses.Source: B Analysis of multiobjective… · p. 10
C Efficient stochastic gradient estimates
The section develops stochastic gradient estimates for group influence by sampling deterministic live-edge cascades. It gives separate implementations for estimating one item’s contribution and all nodes’ contributions, with stated runtime and accuracy guarantees.
C Efficient stochastic gradient estimates
- The independent-cascade objective is an expectation over deterministic live-edge spread functions, so sampled cascades can provide stochastic contribution estimates.For a fixed live-edge graph, spread is the number of nodes reachable from the seed set.Source: C Efficient stochastic gradient… · p. 11
- Aitem estimates one fixed item’s group contributions by counting reachability in a sampled cascade with and without that item.The passage gives O(|V| + |E|) time for this procedure.Source: C Efficient stochastic gradient… · p. 12
- Agrad estimates all node contributions together by removing nodes already reachable from S, assigning isolated nodes, and applying weighted size estimation to the remaining nodes.The weighted estimator gives group-i nodes weight 1 and other nodes weight 0.Source: C Efficient stochastic gradient… · p. 12
- Cohen’s estimator provides a relative-error tail bound for node contributions, and the resulting gradients satisfy the stated c_item and c_grad bounds with high probability.The bound is stated for 0 ≤ ε ≤ 1.Source: C Efficient stochastic gradient… · p. 12
- Agrad runs in O(k(|V| + |E|) log^2 |V|) time, succeeds with probability 1−δ, and guarantees c ≤2b when successful.The sampling strategy ensures each node is absent from at least one sample.Source: C Efficient stochastic gradient… · pp. 11–12
D Runtime comparison with previous work
The runtime comparison contrasts prior MWU-based greedy value-oracle calls with the paper’s gradient-oracle approach. The latter uses logarithmically many calls in n and can save O(n) runtime at the cost of worse dependence on k and b.
D Runtime comparison with previous work
- The previous algorithm uses an MWU second stage in which each iteration calls a greedy algorithm maximizing a weighted combination of the group objectives.The cited implementation requires value-oracle calls.Source: D Runtime comparison with previous work · p. 12
- The new algorithm makes only logarithmically many calls in n to its gradient oracles, Aitem and Agrad.These oracles can have runtime similar to value-oracle calls for common function classes, as shown for influence maximization.Source: D Runtime comparison with previous work · p. 12
- The new algorithm saves a factor O(n) runtime in exchange for worse dependence on k and b, often improving asymptotic runtime when n grows much faster than k or b.For influence maximization, the stochastic gradient oracle’s graph-size dependence matches a value-oracle call up to log factors.Source: D Runtime comparison with previous work · p. 12