Fair influence maximization picks a small set of people to seed with information, such as HIV-prevention messaging, so that every demographic group is reached reasonably well and not just the well-connected majority. Its guarantees assume the social graph is fully known. In practice it is pieced together from sparse traces like surveys, logs, and past sharing. Those traces are sparsest in exactly the communities fairness is meant to protect: small groups and people on the periphery of the network. The standard fix for sparse graphs is to fill in missing links with a learned link predictor, such as a graph neural network trained on observed edges. Recommendation research has shown that such models favour high-degree nodes. If that bias carries over, imputation would add links around hubs and leave the periphery as thin as before, or thinner.
This note proposes to measure, bound, and correct this compounding effect. The claim is that estimation error is not neutral noise. It is aimed at low-coverage groups, and welfare objectives with inequality aversion amplify it precisely there. The proposal is to treat the link predictor's popularity bias as a fairness problem upstream of the greedy seed selector. We would remove degree bias from the predictor and calibrate it per group before running welfare-fair greedy selection. Success means that welfare and worst-group reach, measured on the true graph, recover most of what is lost to sparse observation.
Core Claim
Fair influence maximization has one of the cleanest greedy stories in combinatorial optimization. Maximizing the spread of influence through a social network showed that expected reach under the Independent Cascade model is monotone submodular, a diminishing-returns property, so greedy seed selection is within $(1-1/e)$ of optimal. Fair Influence Maximization: a Welfare Optimization Approach kept this guarantee for fairness-aware objectives. It does so by maximizing an isoelastic welfare function. In that function, a parameter $\alpha \le 1$ moves the objective from total reach ($\alpha=1$) toward caring only about the worst-off group ($\alpha \to -\infty$). Scalable Fair Influence Maximization (FIMM) scaled this to graphs with tens of thousands of nodes. It uses reverse influence sampling (estimating reach by sampling which nodes could have activated a random target) and a Taylor expansion of the fractional powers. All of these guarantees hold with respect to the graph the algorithm is given.
Let $u_g(S)$ be the true fraction of group $g$ reached from seed set $S$, and let $\hat u_g(S)$ be the same fraction computed on an estimated graph. Let $n_g$ be the size of group $g$, and let $W(S)=\sum_g n_g\, u_g(S)^\alpha/\alpha$ be the welfare. A first-order expansion gives the following approximation:
$$|W(S)-\hat W(S)| \approx \sum_g n_g\, u_g(S)^{\alpha-1}\, |u_g(S)-\hat u_g(S)|.$$
Greedy run on a surrogate that is within $\epsilon$ of the true objective everywhere loses at most an additive term proportional to $k\epsilon$, where $k$ is the seed budget. This is the standard approximate-greedy argument. Combining the two, the welfare guarantee degrades by group estimation errors weighted by $u_g^{\alpha-1}$. When $\alpha<1$, that weight is largest for groups with the lowest coverage.
The work rests on two empirical hypotheses. First, the errors $|u_g-\hat u_g|$ are largest for the same groups. Second, off-the-shelf imputation makes them larger, because learned link predictors suffer degree bias. How Graph Convolutions Amplify Popularity Bias for Recommendation? shows that a node's influence on the training gradient of a graph convolution grows like $d^{3/2}$ in its degree $d$. Subramonian et al. prove a preferential-attachment bias in standard graph neural networks. The first deliverable is to state this bound precisely, including the conditions under which the estimated welfare stays submodular.
Research Program
The motivating evidence comes from the structural-bias literature. Fish et al. show that utilitarian seeding widens core-periphery information gaps. Becker et al. show that cascades fail to cross into the periphery. Espín-Noboa et al. prove that majority homophily, the tendency to link with similar people, suppresses minorities in importance rankings. Group-Fairness in Influence Maximization documents near-zero outreach to marginalized youth under standard greedy selection. None of these papers asks what happens when the periphery is also under-observed. That is the gap this program addresses.
The first component is diagnostic. On graphs with known ground truth, we hide edges using masks whose observation rate depends on group and degree. This simulates periphery-heavy sparsity. We then measure per-group reach error $|u_g-\hat u_g|$ under three conditions: no imputation, standard imputation, and debiased imputation. We also check whether the weighted error sum in the equation above predicts the realized welfare loss of greedy selection. The analysis covers several values of $\alpha$.
The second component is the estimator. It borrows its methods from popularity-bias mitigation in recommendation and transfers them from user-item graphs to social link prediction. The backbone is a LightGCN-style predictor. LightGCN is a simplified graph convolution that only averages neighbour embeddings. Its scores are made degree-neutral in two ways. One is embedding normalization with adaptive temperature, following Adap-τ, which shows that embedding length grows with interaction count and that a fixed temperature is fragile. The other is hypersphere-uniformity regularization, following SimGCL, which shows that contrastive learning helps mainly by spreading embeddings evenly. For low-degree nodes we test tail-directed transfer in the style of LAGCL. LAGCL learns to reconstruct the neighbourhoods of artificially thinned head nodes and applies that reconstruction to real tail nodes. The novel step is group-wise calibration. Predicted edge scores are mapped to propagation probabilities separately for each group pair, using held-out observed edges. This targets the error term in the bound directly, rather than accuracy averaged over all edges. A one-line correction to existing methods does not do this: DAP and MACR adjust item scores, not the group-conditional calibration of a graph that a downstream optimizer consumes.
The third component is selection. FIMM runs unchanged on the calibrated graph, so the $(1-1/e-\epsilon)$ guarantee holds relative to the estimate. The bound then accounts for the remaining gap to truth. We deliberately do not design a new optimizer. If the gains come from the estimator alone, the result is more useful, because any fair seeding algorithm can adopt it.
The closest prior work is Influence Maximization with Fairness at Scale. It addresses missing graphs by learning user representations from historical cascades and then runs fair lazy-greedy selection. It evaluates fairness on its own learned influence estimates. It neither asks whether estimation error correlates with group membership nor corrects for degree bias in the learned representation. Our work targets exactly those two questions.
Baselines
The naive reference point is FIMM on the observed sparse graph. It is run with the same seed budget, the same number of reverse-reachable samples, and the same $\alpha$ grid. Edges are simply missing. This isolates how much fairness the sparsity costs.
The strongest existing pipeline is imputation followed by FIMM, using the best accuracy-oriented predictor available here: SimGCL on a LightGCN backbone. The SimGCL paper reports that it improves Recall@20 by over 25% relative to LightGCN on Amazon-Book. LAGCL reports 61.8% Recall@20 and 63.4% NDCG@20 improvements over LightGCN on Amazon-Book. Both are recommendation results. We found no reported Lacuna result for either method on social-graph edge imputation feeding influence maximization. We therefore run both ourselves with identical embedding size, epochs, and hyperparameter search budget. That budget is tuned on held-out observed edges, never on true-graph welfare.
On the fairness side, the reference numbers come from prior work. Rahmattalabi et al. report fairness gains at a 5% to 10% efficiency loss on Sitka, versus over 40% for maximin. Tsang et al. report that diversity constraints cut fairness violations by 55-65% relative to greedy, with Price of Fairness between 1.05 and 1.15. These are full-information figures. Our oracle upper bound is FIMM on the true graph, and the target is to close most of the gap between the naive baseline and this oracle. We also run Feng et al.'s fairness-as-context method on the cascade datasets, where it was designed to operate.
We count the proposal as beating the field if three things hold. Its true-graph welfare and worst-group reach must exceed SimGCL-imputation plus FIMM at every $\alpha<1$, under periphery-heavy masks. Its total reach must stay within the 5–10% efficiency-loss band of the oracle. Its advantage must disappear under uniform masks, which is the control for whether the mechanism is the one we claim.
Two ablations isolate the key ingredients. One removes degree debiasing but keeps group calibration. The other keeps debiasing but removes calibration.
Why not just…?
Why not just run fair influence maximization on the observed graph and accept the sparsity? Under the bound above, every unit of reach underestimated for a low-coverage group costs $u_g^{\alpha-1}$ units of welfare. The fairer the objective, the worse this gets. The naive baseline measures this directly. If it lands close to the oracle under periphery-heavy masks, the premise fails, and we will report that.
Why not just impute missing edges with the best off-the-shelf link predictor? This is the most natural thing a practitioner would do, and our hypothesis is that it backfires. Chen et al. show that deeper graph convolutions collapse recall on low-degree nodes. Wei et al. show that graph propagation spreads hub influence. Imputed edges should therefore cluster near hubs, raising estimated total reach while leaving peripheral cascades truncated. The diagnostic study tests this claim by reporting imputed-edge recall broken down by group and degree. If SimGCL imputation already performs well on the periphery, the debiasing component is unnecessary, and we will say so.
Why not just turn up inequality aversion, lowering $\alpha$, on the observed graph? This would push seeds toward groups that look under-served. But it chooses seeds within those groups using the same wrong graph. By the bound, it also amplifies the effect of the very errors it is reacting to. We sweep $\alpha$ for every pipeline. The test is whether any $\alpha$ on the uncorrected graph matches our pipeline's worst-group reach at equal total reach.
Why not just rescale propagation probabilities per group, without any learned debiasing? This is the real threat. Group calibration alone corrects how many edges each group is missing. It does not correct where those edges are placed within the group: a calibrated but hub-biased predictor still routes peripheral influence through a few central members. The calibration-only ablation settles this. If calibration alone recovers most of the gain, the contribution narrows to the diagnosis, the bound, and a calibration recipe. That would still be a useful result, but a smaller one.
Proposed Experiments
The main testbed is the network suite from Scalable Fair Influence Maximization: Email, Flixster, Amazon product categories, Youtube, and DBLP. Group counts range from 42 to 1,352 communities. We add the Sitka network and the homeless-youth network used by Tsang et al. and Rahmattalabi et al., which carry real demographic attributes. On each graph we generate masks with observation rates tied to group size and degree. The settings range from mild to a regime where peripheral groups keep only a small fraction of their edges. A uniform-rate mask with the same overall density serves as a control. We impute, select $k$ seeds, and evaluate welfare, minimum group coverage, total reach, and Price of Fairness by Monte Carlo cascade simulation on the true graph. Results are reported with confidence intervals over masks and seeds.
The cascade datasets, Sina Weibo and Digg from Feng et al., provide a realistic split. We train on early cascades and evaluate on later ones. Here sparsity is natural rather than simulated, and Digg uses that paper's synthetic sensitive attributes.
Three outcomes decide the project. First, standard imputation must measurably worsen peripheral reach error relative to the observed graph, confirming that degree bias transfers to this setting. Second, the weighted error sum must track realized welfare loss across masks and $\alpha$ values. A rank correlation near zero would falsify the analysis. Third, the full pipeline must beat SimGCL imputation plus FIMM and the per-group rescaling ablation on worst-group true reach under periphery-heavy masks, with no advantage under uniform masks. If the first fails, the problem is milder than claimed, and the honest report is that sparsity, not imputation bias, is the issue. If the third fails while the first two hold, the bound and diagnosis stand as the contribution, and the correction becomes the open problem.
References
- Maximizing the spread of influence through a social network
- Fair Influence Maximization: a Welfare Optimization Approach
- Scalable Fair Influence Maximization
- How graph convolutions amplify popularity bias for recommendation?
- Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction
- Gaps in Information Access in Social Networks?
- Fairness in Influence Maximization through Randomization
- Inequality and inequity in network-based ranking and recommendation algorithms
- Group-Fairness in Influence Maximization
- LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation
- Adap-τ : Adaptively Modulating Embedding Magnitude for Recommendation
- Are Graph Augmentations Necessary?: Simple Graph Contrastive Learning for Recommendation
- Long-Tail Augmented Graph Contrastive Learning for Recommendation
- Influence Maximization with Fairness at Scale
- Model-Agnostic Counterfactual Reasoning for Eliminating Popularity Bias in Recommender System