Suppose a platform wants a correction to reach the people a false story has already reached. It has a limited budget of relay points: trusted accounts, edge caches, or community moderators who can hold content. It also knows the correction only "lands" if a user collects enough of it within a short window after exposure. Erasure coding answers the delivery half of this problem. With a maximum distance separable (MDS) code, a bundle is split into $k$ pieces and expanded into $n>k$ coded pieces, and any $k$ of them rebuild the whole bundle. A user therefore never stalls hunting for one specific missing chunk. What nobody has worked out is where to put the coded pieces when the contact structure is a real, bursty, heavy-tailed social cascade rather than the idealized random mobility under which coded placement was proven to work.
We propose to treat placement of coded pieces as a threshold coverage problem: a user succeeds if they harvest at least $k$ distinct pieces. We solve it on arbitrary graphs with a concave linear-programming relaxation followed by dependent rounding, which rounds fractional placements to whole ones while keeping the total budget exact. We then test whether this matters precisely where existing theory stops applying. Misinformation diffusion data from FakeNewsNet, TAGFN and FACTOID serve as the contact structures, and correction delivery is the motivating task. The main contribution is algorithmic and empirical. It is not a claim about how people respond to corrections.
Core Claim
The greedy placement rule that works for coded caching under Poisson mobility loses its guarantee on irregular graphs once $k\ge 2$. A relaxation-plus-dependent-rounding method keeps both hard budgets and a certificate of near-optimality there. The key reason is structural. Mobility-Aware Content Placement for Device-to-Device Caching Systems shows that under homogeneous Poisson arrivals and disc connectivity, placing MDS pieces is monotone submodular under a matroid, so greedy achieves $(1-1/e)$. On a general graph, however, "harvest at least $k$ pieces" is a threshold event. One additional piece is worthless until $k-1$ others are reachable, so marginal gains can be zero or increasing. Greedy then starts blind. This is the coupon-collector problem reappearing at the level of placement.
Our formulation works as follows. Let $x_v$ be the (possibly fractional) number of distinct coded pieces stored at relay $v$, with capacity $c_v$ and total budget $B$. Let $p_{uv}$ be the probability that exposed user $u$ contacts relay $v$ within the window after exposure, and let $w_u$ be a weight on user $u$. We solve
$$\max_{x}\ \sum_u w_u \min\Big(1,\ \tfrac{1}{k}\sum_v p_{uv}x_v\Big)\quad \text{s.t.}\ \sum_v x_v \le B,\ 0\le x_v\le c_v .$$
This is a linear program after the standard epigraph substitution. Because $\min(1,S/k)\ge \mathbf{1}[S\ge k]$ and the objective is concave, Jensen's inequality makes the LP optimum an upper bound on the expected recovery rate of any placement, randomized or not. That gives an instance-level optimality gap on every real graph. The fractional parts of $x$ are then rounded by swap or pipage rounding, the pairwise mass-transfer schemes of Randomized Pipage Rounding for Matroid Polytopes and Applications. These schemes preserve $\sum_v x_v$ exactly and yield negatively correlated integral placements. The negative correlation is what should make each user's harvested count concentrate near its fractional mean, via lower-tail Chernoff bounds under negative dependence, so the threshold is actually crossed. Independent coin-flip rounding would break the budget and add variance exactly where a threshold objective is most fragile.
Research Program
The first strand is the algorithm and its analysis. We will bound the loss from rounding as a function of $k$ and of how concentrated each user's contact mass is, and state explicitly when the bound degrades. Real cascades are bursty: FakeNewsNet reports sharp retweet bursts for fake news and roughly 22% bot spreaders on PolitiFact versus 9% for real news. Contacts in such cascades are correlated, not independent. Price of Dependence proves that continuous-greedy-plus-rounding guarantees degrade as item states become dependent, measured by its parameter $\kappa$, but gives no empirical evaluation. We use its dependence notion as a lens and estimate an empirical analogue of $\kappa$ per cascade. The question is whether the measured optimality gap tracks it. That paper constrains our claims: we do not expect worst-case guarantees to survive heavy correlation, only a measurable, certified gap.
The second strand is a robust variant. At placement time the platform does not know which cascade will unfold. We therefore maximize the worst case over a scenario set of historical cascades, $\min_i F_i(x)$. The minimum of submodular functions is not submodular, and our $F_i$ are not submodular to begin with. We solve this by replacing the multilinear step of EQUATOR, the method in Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure, with our concave LP surrogate. EQUATOR supplies the method: stochastic Frank–Wolfe on a smoothed minimum, then swap rounding. We differ in the objective (threshold recovery rather than coverage over a static security graph) and in the scenario structure (time-stamped cascades).
The third strand is the topology-generalization study, which is the empirical heart of the work. We build contact graphs from four sources. The first is Poisson-disc mobility, the regime of Song and Choi, as a control where greedy is known to be good. The second is Erdős–Rényi and scale-free synthetic graphs. The third is propagation trees with timestamps from TAGFN and FakeNewsNet's PolitiFact and GossipCop subsets. The fourth is reply-interaction graphs from FACTOID, which the FACTOID authors show cluster misinformation spreaders tightly.
In all cases the construction is the same. Exposed users are the nodes that shared the false item, candidate relays are nodes eligible to hold correction pieces, and $p_{uv}$ comes from the timestamped interaction within window $W$ after $u$'s exposure. That $p_{uv}$ is estimated from a training period and evaluated on held-out cascades, so estimation error is part of the test. Coded Caching in a Multi-Server System With Random Topology shows that on random bipartite user–server graphs, latency depends only on the degree "type". We test directly whether degree statistics alone predict the gap on non-bipartite, clustered cascades, or whether burstiness and clustering add explanatory power.
Baselines
The naive reference is uncoded placement with the budget spent on full copies. Under $k$-piece bundles this corresponds to a user needing all specific chunks, the regime in which MDS-Coded Distributed Caching for Low Delay Wireless Content Delivery reports a speed-up of "around 19" for a (15,5) MDS code over base-station-only download. Alongside it we report "do nothing", meaning zero relays, as the recovery floor.
The strongest existing method is the mobility-aware greedy of Song and Choi, applied to our coded objective with the same $p_{uv}$ estimates and the same budget. It is the strongest competitor because it is the only method in the file proven for coded piece placement, and its authors report it performs "nearly as well as an exhaustive search" under Poisson mobility. No reported result found on Lacuna for greedy or any coded placement method on cascade-derived contact graphs. We will therefore compare it against the LP certificate on every instance. Beating it means strictly higher held-out recovery at equal budget on the real-cascade graphs, with the advantage growing in $k$, while matching it on the Poisson control. For the robust variant, the reference is EQUATOR's reported performance of "within 4-8% of the global optimum" in its own domains. We will report whether our worst-case gap to the LP bound falls in or outside that band.
Two further competitors cover obvious shortcuts. A degree-hub heuristic places pieces on the highest-degree relays, which is natural on scale-free graphs. A learned policy follows the primal-dual graph neural network of Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networks. It is trained on synthetic graphs and the training period, and given at least the wall-clock compute our LP uses, summed over all instances. All methods share the same $p_{uv}$, budget, capacities and held-out cascades.
The ablation that isolates our key ingredient keeps the LP solution and swaps the rounding. We compare independent rounding (reporting budget violations and recovery after truncation), deterministic largest-fraction rounding, and swap/pipage rounding. A second ablation runs greedy on the concave surrogate itself instead of on the true threshold objective. That separates the value of the relaxation from the value of dependent rounding.
Why not just…?
Why not just run greedy, since it worked for coded caching before? On threshold objectives with $k\ge 2$, greedy's first steps can see zero marginal gain everywhere, and the submodularity behind Song and Choi's guarantee comes from their homogeneous Poisson model, not from coded placement in general. This is a real threat nonetheless. If real cascades give most users many contacts, greedy may recover. The surrogate-greedy ablation and the gap-versus-$k$ curves settle it. If greedy on the surrogate matches LP-plus-rounding on held-out cascades, we will report that the relaxation's value is only the certificate, not better placements.
Why not just send the whole correction uncoded, since corrections are short? For a single short text this is right, and at $k=1$ our method reduces to replication and should tie. Coding matters only when the bundle is multi-part (evidence, sources, images, in the spirit of the fine-grained evidence needs in MisSpans) and contact windows are short, which is the regime where Song and Choi show partial segments are necessary. We sweep $k$ and window length $W$ so the region where coding helps is measured rather than assumed.
Why not just put everything on hubs? On scale-free graphs, hubs may capture most contact mass, and this heuristic could come close to optimal. We expect it to fail on FACTOID-style clustered graphs, where exposed communities have local rather than global hubs. The LP certificate will show directly how far hub placement is from optimal on each graph class.
Why not just learn a placement policy with a graph neural network? Gao et al. needed primal-dual training precisely because learned policies do not satisfy hard constraints on their own, and they tested generalization only from 5 to 10 nodes. Out-of-distribution topology is the open problem in Direction 2. We test the network on graph classes it was not trained on and report both recovery and budget violations.
Proposed Experiments
The decisive check is a single figure per graph class. It plots held-out recovery rate against $k$ for all methods, together with the LP upper bound. The prediction is that on Poisson-disc graphs all non-naive methods sit close together and near the bound. On real cascades from TAGFN, FakeNewsNet and FACTOID, greedy and hub placement should fall away from the bound as $k$ grows, while LP-plus-swap-rounding stays within a small certified gap.
A second check regresses each method's certified gap on degree heterogeneity, clustering coefficient, burstiness, and the empirical dependence estimate inspired by Tang. The aim is to test whether Mital et al.'s "type depends only on degrees" picture extends to these graphs. A third check compares robust and average-case placement on cascades held out by time. The prediction is that the robust solution loses little on average and gains on the worst decile of cascades.
A result that would falsify the proposal is greedy matching LP-plus-rounding within noise on real cascades at $k\ge 3$. We will report that outcome as a positive finding about how well greedy generalizes.
References
- Mobility-Aware Content Placement for Device-to-Device Caching Systems
- Randomized Pipage Rounding for Matroid Polytopes and Applications
- FakeNewsNet: A Data Repository with News Content, Social Context, and Spatiotemporal Information for Studying Fake News on Social Media
- Price of dependence: stochastic submodular maximization with dependent items
- Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure
- TAGFN: A Text-Attributed Graph Dataset for Fake News Detection in the Age of LLMs
- FACTOID: A New Dataset for Identifying Misinformation Spreaders and Political Bias
- Coded caching in a multi-server system with random topology
- MDS-Coded Distributed Caching for Low Delay Wireless Content Delivery
- Resource Allocation via Graph Neural Networks in Free Space Optical Fronthaul Networks
- MisSpans: Fine-Grained False Span Identification in Cross-Domain Fake News