Influence maximization picks a small set of "seed" users in a social network so that a message they start reaches as many people as possible. It relies on knowing how likely each person is to pass the message to each neighbor, and those probabilities are estimated from historical logs of who adopted what, and when. Every such log stops at some date. A person who had not adopted by that date may never adopt, or may simply not have adopted yet. This is right-censoring: we only know that the event, if it happens, happens after the cutoff. Current practice either treats these people as non-adopters or assumes the transmission rates are already known. The estimation error this creates is not random noise. It is a systematic bias that grows as soon as a campaign is planned over a longer horizon than the log covers.
We propose to estimate diffusion models with a likelihood that correctly accounts for censoring. We then deliberately build an ensemble of diffusion models that disagree along the one direction the censored data cannot resolve, the trade-off between "this edge rarely transmits" and "this edge transmits slowly," and choose seeds that hold up across that disagreement. The claim is specific. When the planning horizon exceeds the logging window, most of the seed-selection regret comes from this identifiability gap. Ensembling a censoring-blind estimator cannot fix it, because all its members share the same bias. A censoring-correct point estimate cannot fix it either, because it commits to one arbitrary point on the gap.
Core Claim
Consider a diffusion model in which an infected user $u$ gets one chance to infect neighbor $v$. The attempt succeeds with probability $p_{uv}$ and arrives after a random delay with distribution $F(\cdot;\lambda_{uv})$. Here $\lambda_{uv}$ is a delay-rate parameter: larger values mean faster transmission. In a cascade observed until $T_{obs}$, a user $v$ who never activated contributes this factor to the likelihood:
$$\prod_{u \in \mathrm{infected}(v)} \big[\,1 - p_{uv}\, F(T_{obs} - t_u;\lambda_{uv})\,\big],$$
where $t_u$ is the observed activation time of the in-neighbor $u$. This is the censored-survival term in the standard form $f^{\Delta} S^{1-\Delta}$, extended with a "cure" mass $1-p_{uv}$ for edges that would never transmit. It is exactly the "never versus later" ambiguity flagged in Limitations of Binary Classification for Long-Horizon Diagnosis Prediction and Advantages of a Discrete-Time Time-to-Event Approach: Empirical Analysis.
When typical delays are comparable to the window, the product $p_{uv}F$ is well identified but $p_{uv}$ and $\lambda_{uv}$ separately are not. The likelihood has a ridge. Spread predictions at a deployment horizon $T_{dep} \le T_{obs}$ barely depend on where on the ridge the truth sits. Predictions at $T_{dep} \gg T_{obs}$ depend on it heavily. So the uncertainty that matters for planning is neither the hyper-rectangle of intervals used in Robust Influence Maximization nor a low-dimensional linear-in-features family as in Robust Influence Maximization for Hyperparametric Models. It is a data-determined, strongly correlated set whose width grows with the ratio $T_{dep}/T_{obs}$.
We do not claim that the censored likelihood itself is new. It is textbook survival analysis. The contribution is to show, and then exploit, three things: censoring turns parameter uncertainty in influence maximization into a structured bias-plus-ridge problem; the right ensemble spans that ridge; and robust seed selection over this ensemble beats both point-estimate planning and interval-based robust planning in the extrapolation regime.
Research Program
The first component is the estimator. For each edge we fit a cure-type delay model, meaning a transmission probability $p_{uv}$ plus a delay distribution, by maximizing the censored cascade likelihood above. Estimation strength is shared across edges through a flexible edge-feature model, a small neural network, rather than a generalized linear model. This avoids the linear link assumption that Robust Influence Maximization for Hyperparametric Models needs for its guarantees. We fit three delay families: exponential, which matches the continuous-time Markov-chain model of Influence Maximization in Continuous Time Diffusion Networks; Weibull; and log-normal. These families extrapolate beyond the window in different ways, and that difference is precisely the misspecification risk.
The second component is the ensemble. It has $M \approx 20$ members; Robust Influence Maximization for Hyperparametric Models reports needing "only about 20 sampled functions and 10 MWU iterations." Each member is obtained in one of three ways. The first is by resampling whole cascades, so that the dependence between users within a cascade is preserved. The second is by rotating the delay family. The third is by profiling along the ridge, that is, fitting with the ratio of $p$ to delay fixed at several values and keeping every fit whose likelihood falls within a chi-square threshold of the maximum. The third mechanism is what separates this ensemble from generic bagging. Bootstrap members cluster near one point on the ridge, whereas profile members span it by construction.
The third component is seed selection. We maximize the worst-case absolute spread by time $T_{dep}$ over ensemble members, using the multiplicative-weights (MWU) game from HIRO, in which weights shift toward the members where the current seeds do worst. We also report a softer variant that maximizes the average of the lowest 20% of member spreads. We deliberately do not optimize the robust ratio, because Robust Influence Maximization for Hyperparametric Models shows it can select seeds reaching one node while alternatives reach $\sqrt{n}$. Spread under each member is estimated with delay-constrained reverse-reachable sampling. Reverse-reachable sets are random samples of "who could have reached this node," here restricted to paths that arrive by $T_{dep}$. For larger graphs we reuse the incremental maintenance of Hyperparametric Robust and Dynamic Influence Maximization.
The analysis component decomposes regret as $T_{dep}/T_{obs}$ varies. We separate the loss due to censoring bias, measured as the gap between the naive and censored point estimates, from the loss due to ridge uncertainty, measured as the gap between the censored point estimate and a planner that knows the true ridge location. This tests the core claim directly.
Baselines
The naive reference point follows A Data-Based Approach to Social Influence Maximization. It treats users who have not adopted by the cutoff as non-adopters, estimates per-edge probabilities from the logs, and runs greedy selection. We also include Goyal's Credit Distribution model itself, run on identical truncated logs, because it is the standard data-driven approach. It reportedly reduced 50-seed selection on Flixster Small from 40 hours to 3 minutes, but it discards long-term influence through a pruning threshold. Beating this reference requires higher true spread at $T_{dep}$ at every horizon ratio above one.
The strongest point-estimate competitor pairs our own censored-likelihood estimator with INFLUMAX-style greedy selection under a deadline (Influence Maximization in Continuous Time Diffusion Networks). INFLUMAX reports reaching 20% to 30% more nodes than PMIA and SP1M on MemeTracker, but only with rates assumed known. The authors themselves note that performance may degrade when rates are noisy. Pairing INFLUMAX with a proper censored estimator gives it the best possible point estimate, so any gain we show must come from the ensemble.
The strongest robust competitor is HIRO (Robust Influence Maximization for Hyperparametric Models), with RIME (Hyperparametric Robust and Dynamic Influence Maximization) used on graphs above 1,000 nodes. RIME is reported to scale to a 100,000-node Weibo graph, whereas HIRO "failed to scale beyond 1,000 nodes." We give both methods their generalized linear model family fitted to the same censored likelihood and the same edge features. We run LUGreedy from Robust Influence Maximization on per-edge likelihood intervals. The file reports no robust-ratio or spread numbers for these methods on censored-log data. The closest reported figure is that ICS-RIM needs 33,000 samples per edge, versus 77,000 for uniform sampling, to reach a robust ratio of 0.8 on Flixster Topic 8. Those samples come from active intervention, which our offline setting does not allow. No reported result was found on Lacuna for robust influence maximization from right-censored offline logs.
All methods receive the same logs, the same edge features, the same number of spread-estimation samples, and an equal hyperparameter-search budget measured in fitted models. Wall-clock time is reported alongside. Three ablations isolate the key ingredient. The first uses a bootstrap-only ensemble with no ridge profiling. The second uses a single delay family. The third bootstraps the naive censoring-blind estimator.
Our method counts as winning if two conditions hold. First, at $T_{dep}/T_{obs} \ge 2$ it improves true worst-decile spread over the best competitor, with confidence intervals across graphs and seeds that exclude zero. Second, it does not lose median spread by more than a few percent at $T_{dep}/T_{obs} = 1$.
Why not just…?
Why not just fit the censored likelihood and plan on the point estimate? This is the most serious threat. If cascades are plentiful and delays are short relative to the window, the ridge collapses and the point estimate is sufficient. We expect exactly that at small $T_{dep}/T_{obs}$ and say so. The regret decomposition shows where this baseline stops being enough. Stability of influence maximization found that roughly 20% parameter error already distorts seed selection, so extrapolation along an unidentified direction should cross that threshold easily. If it does not, the ensemble is unnecessary and we will report that.
Why not just ensemble the existing estimator (bagging the naive fit)? Every bagged member inherits the same censoring bias, so their errors are correlated. Averaging reduces variance, not bias, and yields confident but wrong spread predictions. This is the correlated-blind-spot failure of ensembles. The bootstrapped-naive ablation measures this directly through the coverage of true spread by the ensemble's spread range.
Why not just widen the intervals and run LUGreedy? Hyper-rectangles ignore the fact that censoring couples $p_{uv}$ with delay and couples edges within a cascade. Widening them enough to cover the ridge makes the worst case needlessly pessimistic. Robust Influence Maximization itself shows the robust ratio falling rapidly as interval width grows on NetHEPT. The LUGreedy baseline shows whether this over-conservatism costs spread in practice.
Why not just a Bayesian posterior? Posterior samples are a legitimate way to build the same ensemble, and we include them as a variant. The ridge-profiling and family-rotation members exist because a posterior under one delay family cannot represent uncertainty about the family itself, and that uncertainty governs extrapolation.
Proposed Experiments
The first experiment is semi-synthetic and has ground truth. We take real topologies: NetHEPT, the Facebook graph and its 347-node subgraph, Flixster, Kronecker core-periphery graphs, and Weibo subgraphs for scale. On each we plant known transmission probabilities and delay distributions, drawn from all three families plus a mixture, so that no single family is correct. We generate cascades and censor them at $T_{obs}$. We vary three factors: the ratio $T_{dep}/T_{obs}$ from 1 to 5, the number of cascades, and whether censoring is independent or triggered by the cascade itself. The last condition mimics monitoring that stops when a cascade dies, which violates the independence assumption of Conformalized Survival Analysis for General Right-Censored Data and serves as a stress test. The metrics are three: true expected spread by $T_{dep}$ under the planted model, regret relative to the oracle greedy seed set, and worst-decile spread across planted-parameter redraws. We also measure calibration, meaning how often the ensemble's range of spread predictions contains the true spread.
The second experiment is a temporal holdout on real logs from MemeTracker and Flixster. We fit on logs truncated at an early cutoff and score each method's seed sets, and its predicted adoption curves, against adoptions that appear after the cutoff. This is the log-based evaluation style of A Data-Based Approach to Social Influence Maximization, extended beyond the window.
The decisive check is the interaction pattern. The claim holds if three results appear together. The censoring-blind estimator, bagged or not, degrades as $T_{dep}/T_{obs}$ grows. The censored point estimate matches our method at a ratio of 1 but falls behind at larger ratios. The bootstrap-only ablation recovers little of the gap that ridge profiling closes. If instead the censored point estimate matches the full method at every ratio, the ensemble adds nothing and the contribution reduces to the estimator. We would report that plainly.
References
- Limitations of Binary Classification for Long-Horizon Diagnosis Prediction and Advantages of a Discrete-Time Time-to-Event Approach: Empirical Analysis
- Robust Influence Maximization
- Robust Influence Maximization for Hyperparametric Models
- Influence Maximization in Continuous Time Diffusion Networks
- Hyperparametric Robust and Dynamic Influence Maximization
- A Data-Based Approach to Social Influence Maximization
- Stability of influence maximization
- Conformalized Survival Analysis for General Right-Censored Data