Research map / Learning theory and algorithms / Fairness
Fairness in Social Influence Maximization via Optimal Transport
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes mutual fairness, an optimal-transport-based metric over the joint outreach distribution of groups in social influence maximization, plus a stochastic seed-selection algorithm (S3D) that optimizes a fairness-efficiency tradeoff.
Problem
Standard fairness metrics for social influence maximization use expected per-group outreach, which ignores the stochastic joint distribution of outreach across groups and can label highly unequal diffusion outcomes as fair.
Approach
Measure fairness as the optimal transport distance between the joint outreach distribution and the ideal point (1,1), with a transport cost that ignores movement along the diagonal (efficiency) and penalizes orthogonal displacement (group disparity); combine with efficiency via a beta-weighted cost and optimize seeds with a Metropolis-style search (S3D).
Key results
- On the AH dataset, S3D improved efficiency from 83.1% to 87.9% while also improving fairness over its label-blind baseline initialization.
- S3D achieves the highest fairness score in almost all cases across datasets, with generally slightly lower efficiency than baselines.
- The paper shows that equity-based metrics can classify highly stochastic, unfair outcomes (e.g., 50/50 flip between groups) as fair, while mutual fairness gives 0.5 for that case versus 1 for always-fair outcomes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use S3D_g instead of bas_g | Greedy-initialized seed selection · APS | fairness: 0.898 -> 0.945 | Helped |
| Use S3D_g instead of bas_g | Greedy-initialized seed selection · APS | efficiency: 0.318 -> 0.25 | Hurt |
| Use S3D_g instead of bas_g | Greedy-initialized seed selection · AV_0 | fairness: 0.926 -> 0.951 | Helped |
| Use S3D_g instead of bas_g | Greedy-initialized seed selection · AV_0 | efficiency: 0.3 -> 0.241 | Hurt |
| Use S3D_g instead of bas_g | Greedy-initialized seed selection · HS, p=0.01 | fairness: 0.938 -> 0.988 | Helped |
| Use S3D_g instead of bas_g | Greedy-initialized seed selection · HS, p=0.01 | efficiency: 0.08 -> 0.08 | No clear effect |
| Use S3D_g instead of bas_g | Greedy-initialized seed selection · HS, p=0.5 | fairness: 0.94 -> 0.96 | Helped |
| Use S3D_g instead of bas_g | Greedy-initialized seed selection · HS, p=0.5 | efficiency: 0.89 -> 0.87 | Hurt |
Surprising findings
- Equity fairness and mutual fairness show opposite trends as the conduction probability p varies in (0, 0.5) on the Indian Villages dataset.
- Label-blind greedy seed selection can produce highly unequal joint outreach outcomes even when expected per-group outreach is equal.
Limitations
- S3D is a random combinatorial search whose performance depends on the seedset initialization.
- No guaranteed bound on the number of iterations needed to reach a desired fairness level.
- Discretization into 100x100 bins can hide variance in dense graphs such as INS and DZ, producing concentrated distributions.
Experimental setup
Datasets: Add Health Antelope Valley APS Physics Deezer High School Indian Villages Instagram
Benchmarks: Add Health Antelope Valley APS Physics Deezer High School Indian Villages Instagram
Metrics: mutual fairness beta-fairness efficiency (normalized outreach) equity
Baselines: degree centrality greedy degree-central fair heuristic greedy fair heuristic
Builds on: independent cascade model equity fairness metric greedy influence maximization Metropolis sampling
Closest papers by meaning
- Improving Fairness in Information Exposure by Adding Links (AAAI 2023 · similarity 0.92)
- On the Cost of Demographic Parity in Influence Maximization (AAAI 2023 · similarity 0.91)
- Fair Influence Maximization: a Welfare Optimization Approach (AAAI 2021 · similarity 0.89)
- Scalable Fair Influence Maximization (NeurIPS 2023 · similarity 0.89)
- Unveiling Environmental Sensitivity of Individual Gains in Influence Maximization (NeurIPS 2025 · similarity 0.85)
- Fairness under Competition (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.