Adaptive Seeding from Stale, Drifting Feedback

Influence campaigns such as product launches, public-health messaging, or corrections of misinformation work best when the campaigner seeds people in stages. You recruit a few people, watch who they reach, and spend the next seeds on parts of the network the message has not reached yet. This closed-loop approach, called adaptive influence maximization, can beat committing to all seeds upfront by large margins. The theory behind it quietly assumes two things. The first is that the campaigner sees the current state of the network: who has adopted, and how. The second is that the diffusion process, meaning the probabilities that one person passes the message to another, stays fixed. Neither holds on a real platform. Status checks are rate-limited, arrive late, and cover only a few users at a time. Platforms also change how content spreads in the middle of a campaign. The seeder therefore acts on a view that is partly old. When it later sees something unexpected, it cannot tell whether the cascade simply moved on while it wasn't looking, or whether the rules of spread have changed.

This note proposes to treat staleness as a measured quantity that shapes two decisions: whom to check next, and when to believe the world has changed. For each user, the seeder tracks the Age of Information (AoI), the time since that user's status was last observed. It uses that age to predict how uncertain the user's current status should be. It then uses the gap between prediction and observation to detect drift in the diffusion process. The decision rule is "check the users whose fresh status is most useful," and useful has two parts. A fresh status avoids wasting a seed on someone already reached. It also gives a sharp test of whether the diffusion model is still right.

Core Claim

The claim is that under a limited checking budget, adaptive seeding should not separate where to look from whether the model has drifted. The same observation serves both purposes, and how much it is worth depends on its age. Let the current diffusion model be $\theta$. For user $v$, last observed $a_v$ time steps ago, let $\hat p_v(\theta, a_v)$ be the model's predicted probability that $v$ is now active, obtained by simulating the cascade forward from that last observation. When a check returns status $y_v \in \{0,1\}$, the seeder scores it with an age-calibrated surprise. This is a standardized residual whose scale comes from the age-dependent prediction itself:

$$ z_v = \frac{(y_v - \hat p_v(\theta, a_v))^2}{\hat p_v(\theta,a_v)\,(1-\hat p_v(\theta,a_v))}, $$

These scores are accumulated in a cumulative-sum (CUSUM) test, which declares drift when the running total of excess surprise crosses a threshold.

Ignoring age does damage in two directions. A stale user's status is genuinely uncertain, so a "surprising" reading from that user mostly reflects missed cascade progress, and an age-blind detector raises false alarms. A freshly observed user whose status the model predicts confidently is the most diagnostic reading available, and wasting checks on stale users delays detection. A matching rule follows for choosing whom to check. Each candidate is scored by its expected seeding benefit plus the expected divergence between the "no drift" and "drift" hypotheses' predictions for that user at its current age. Both terms can be computed from the same forward simulations the seeder already runs.

Relation to Prior Work

The adaptive seeding line supplies the base algorithms and motivates the gap. Adaptive Influence Maximization in Dynamic Social Networks proves that waiting for each cascade to finish before seeding again is optimal. It reports adaptive seeding beating static greedy by 125% under the standard cascade model on NetHEPT, but it assumes known, fixed distributions and free observation. No Time to Observe shows that seeding mid-cascade breaks the property that justifies greedy guarantees. Its α-greedy policy waits for a fixed threshold, reporting a 52.6% gain over the non-adaptive baseline at α = 0.8. Time-constrained Adaptive Influence Maximization makes the point that "waiting is not free" under a deadline, and its Fast Foresight policy trades the gain of seeding now against the cost of delayed diffusion. All three assume that whatever is observed is current, and none detects drift. We reuse Fast Foresight as the seeding core and change only what it sees and when it re-estimates.

Online and non-stationary seeding is the closest competitor. Online Influence Maximization in Non-Stationary Social Networks (the RSB algorithm) tracks drifting influence through continual randomized exploration across rounds, without modeling cascades within a round and without detecting when a change occurs. Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization (MORIMA) learns a feature-based diffusion model from node-level feedback with regret guarantees, but it assumes stationary parameters and instantaneous observation. Its slow-switching rule re-plans on information growth, not on evidence of change. Online Submodular Maximization via Online Convex Optimization handles adversarial reward sequences but abstracts away cascade timing entirely. Our proposal differs from all of these in two ways. It works inside a single campaign with stale, budgeted checks, and it adapts by explicit detection rather than by uniform exploration.

The freshness and change-detection literature supplies method and constraints. Age Optimum Sampling in Non-Stationary Environment pairs a learned waiting time with a Kolmogorov–Smirnov change test on a single sensor link and resets on detection. This is the template for our reset logic, though it never asks how stale readings bias detection, because there is only one source. Fundamental Limits of Age-of-Information in Stationary and Non-stationary Environments shows that the simple "check whoever is oldest" (Max-Age) rule is only $O(N^2)$-competitive under adversarial channels. That constrains us: a pure Max-Age checker is a weak default, so we must beat a better one. STAR shows that surprise-triggered model updates can match turn-by-turn updating with 94% fewer model operations in a toy game. We borrow the idea of triggering on accumulated surprise and calibrate the surprise by age on a graph.

Research Program

The work has three parts. The first is a simulator and a problem definition. Seeding takes place on a graph under the Independent Cascade model, in which each newly activated user gets one chance to activate each neighbor with some edge probability. There is a global deadline $T$ and a seed budget $k$. At each step the seeder may check the status of at most $m$ users, and results return after a random delay. Edge probabilities change piecewise at unknown times. We will generate two kinds of shift: global rescaling, which mimics a platform-wide ranking change, and community-local shifts, which mimic a topic becoming hot in one cluster.

The second part is the method. The seeder keeps an ensemble of reverse-reachable-style forward samples under the current $\theta$. It uses them to compute $\hat p_v(\theta, a_v)$ for every user, and from the same samples it gets Fast Foresight's seeding scores. Checks are chosen greedily by the combined seeding-plus-detection value. A CUSUM test on $z_v$ decides when to re-estimate $\theta$ from post-change observations only, using maximum likelihood on the observed activations. A short trial period guards against transient noise, in the spirit of STAR's "hastiness" setting.

The third part is analysis. We aim for a modest but checkable result, namely detection delay as a function of the ages of the checked users. The intuition comes from standard CUSUM analysis, where expected detection delay scales inversely with the per-observation divergence between pre- and post-change predictions. That divergence shrinks as age grows, because predictions blur toward uninformative values. We do not claim approximation guarantees for the full non-submodular, non-stationary problem.

Baselines

The naive reference is static seeding: one-shot greedy selection of all $k$ seeds at time zero under the initial $\theta$, with no checks. It sets the floor and indicates how much adaptivity is worth in each regime.

The strongest existing method on this question is Fast Foresight from Time-constrained Adaptive Influence Maximization, because it is the only cited method designed for deadline-constrained mid-cascade seeding. We run it in two forms. The first gives it oracle access to full, fresh status and the true current $\theta$. This is an upper reference, not a competitor. The second is realistic: it receives the same $m$-per-step delayed checks and only the initial $\theta$. No reported result was found on Lacuna for Fast Foresight's spread values on Wiki, Reddit or Youtube. We will therefore reproduce it ourselves and tune its $\theta$ coefficient on held-out graphs with the same search budget as our hyperparameters.

The decoupled pipeline isolates our key ingredient. It uses Fast Foresight for seeding, Max-Age checking (check the oldest users), and a change detector with the same CUSUM test and threshold calibration but with age-blind surprise, where $\hat p_v$ is computed as if the observation were current. A second ablation keeps age-calibrated surprise but checks by Max-Age, which separates the value of calibration from the value of coupled check selection. A third ablation keeps everything except detection, so it never re-estimates.

We also include α-greedy from No Time to Observe with its α tuned, and adapted versions of RSB and MORIMA in a repeated-campaign variant, where their round-based design is fair. All methods share the same graphs, drift schedules, check budget, delay distribution, simulation sample count and wall-clock limit.

Beating Fast Foresight means higher spread at the deadline under drift, with confidence intervals over at least 50 drift realizations. Beating the decoupled pipeline means lower detection delay at a matched false-alarm rate and a measurable reduction in seeds wasted on already-active users. If we match it only on spread, we will report that the gain lies in detection alone.

Why not just…?

Why not just observe everyone and run Fast Foresight on fresh data? When checks are free and complete, this is the right answer, and our method should collapse to it. That is why the oracle variant serves as an upper reference. The proposal is only about the budgeted regime motivated by API limits and privacy, as noted for partial observability in Neighborhood Matters. We will sweep $m$ up to full coverage and report the budget at which our advantage vanishes. If that budget turns out to be tiny, the problem is less important than claimed.

Why not just use Max-Age checking plus a standard change test, with no coupling? This is the most serious threat, and it is why the decoupled pipeline is a baseline rather than a straw man. The evidence against Max-Age comes from wireless scheduling (Banerjee et al.), not from cascades, so it does not settle the question here. Our two ablations do. If age-calibrated surprise with Max-Age checking matches the full method, then coupled check selection adds nothing and we will say so. If the age-blind detector matches as well, the core claim fails.

Why not just use a non-stationary bandit like RSB across campaigns? RSB adapts between rounds through continual exploration, and its regret grows with network size (Online Influence Maximization in Non-Stationary Social Networks). It cannot react to a shift partway through one campaign. In the repeated-campaign experiment we run it directly. If drift is slow relative to campaign length, RSB may be competitive, and we will report the drift speed at which that happens.

Decisive Experiments

The graphs are NetHEPT (15,000 nodes) and Wiki (8,600 nodes) from the adaptive-seeding literature, Reddit and Youtube from the time-constrained study for scale, and the Tencent Weibo trace (4,257 users) used by RSB. The cycled 7-day Weibo trace provides naturally periodic drift alongside our injected piecewise shifts. Metrics are spread at the deadline, the fraction of seeds placed on already-active users, detection delay and false-alarm rate, the mean age of checked statuses, and runtime.

The first decisive check plots detection delay against false-alarm rate across thresholds. The age-calibrated detector should dominate the age-blind one, and the gap should widen as observation delay grows. Without that widening, the mechanism is wrong. The second check plots spread against check budget $m$. The proposal should beat realistic Fast Foresight and the decoupled pipeline at small $m$ and converge to the oracle as $m$ grows. The third check separates drift type. We expect the largest gains under community-local shifts, where coupled check selection should concentrate checks inside the drifting cluster while Max-Age spreads them evenly. Under a global rescaling, any checking order detects the change, and we expect little difference. Confirming that contrast would show the gain comes from where checks are placed, and not from extra re-estimation.