One Sparse Kernel for Every Cascade Model

Most fast influence-spread software silently assumes one particular model of how information moves through a network. Two models dominate. In the Independent Cascade (IC) model, each edge flips its own coin. In the Linear Threshold (LT) model, a person adopts once enough of their neighbors have. GPU systems for picking influential seed nodes are built around the first, coin-flipping model and do not run on the second. Separately, a large body of hardware work shows that sparse matrix operations, the natural language of graphs, rarely run fast on GPUs. Their irregular zero patterns waste the dense matrix units that modern chips are designed around.

This proposal connects the two problems through one rewriting. Both IC and LT, and also the susceptible-infected-recovered (SIR) epidemic model, can be written as the same computation. Each step multiplies one fixed sparse weight matrix by a dense block of many simulated cascades at once, then compares the result to per-node random thresholds. The models differ only in how the edge weights are transformed and which distribution the thresholds come from. The sparsity pattern is then the graph itself, identical for every sample, every model, and every round of an online algorithm where only edge weights change. Two things follow. Monte Carlo diffusion becomes a sparse-times-dense product that can use Tensor Cores (the GPU's dense matrix-multiply units). The expensive one-time reorganization that makes unstructured sparsity fast is paid once and reused across millions of simulations.

Core Claim

Take an LT simulation with thresholds $\theta_v \sim U[0,1]$ fixed per sample. Node $v$ is active once the summed weight $b_{uv}$ of its active in-neighbors reaches $\theta_v$. Now consider IC with edge probabilities $p_{uv}$. Define log-weights $w_{uv} = -\log(1-p_{uv})$ and draw one exponential threshold $\eta_v \sim \mathrm{Exp}(1)$ per node per sample. Then "$v$ is still inactive after active set $S$" has probability

$$\Pr\Big[\eta_v > \sum_{u\in S} w_{uv}\Big] = \prod_{u \in S}(1-p_{uv}),$$

which is exactly the IC probability. The exponential distribution is memoryless, so the step-by-step conditional probabilities also match IC. Thresholds are independent across nodes, as IC's coins are on disjoint incoming edge sets. Read this way, IC is a threshold model with a log-transformed weight matrix. This is in the spirit of the classical observation that IC is a special case of general threshold models. We use the calculation as a tool and do not claim it as the contribution.

Let $X_t \in \{0,1\}^{n \times R}$ hold the activation states of $n$ nodes across $R$ independent samples (columns). Let $W$ be the $n \times n$ sparse weight matrix, with entries $b_{uv}$ for LT or $w_{uv}$ for IC. Let $\Theta$ be the $n\times R$ threshold matrix. Then both models share one update:

$$X_{t+1} = X_t \lor \mathbb{1}\big[\,W^{\top} X_t \ge \Theta\,\big].$$

SIR fits the same form. Each infected node gets a fresh independent chance per step while infectious, so the input becomes $W^\top C_t$, where $C_t$ counts the infectious steps of each node so far.

The claim has three parts. First, every forward cascade simulation reduces to repeated SpMM with one matrix shared across all $R$ columns, followed by an elementwise compare. Second, because the matrix pattern never changes, blocked Tensor-Core layouts can be prepared once and amortized; their row reordering is otherwise a liability for dynamic workloads. Third, the resulting simulator has the same throughput profile across propagation models. Traversal-based GPU code cannot offer this, because its inner loop is a per-model graph walk.

The precise thing that would be new is this combination. A single, distributionally exact, model-agnostic Monte Carlo diffusion engine, built on a fixed-pattern Tensor-Core sparse product, whose preprocessing is amortized across samples, models and weight updates.

Research Program

The work has three layers.

Correctness layer. We give the short proof of distributional equivalence for IC, LT and SIR. We also bound the bias from low-precision arithmetic. Weights stored in FP16 carry relative rounding error of about $2^{-11}$, and accumulation is in FP32 on Tensor Cores. Per-edge probabilities therefore shift by roughly $p_{uv}\cdot 2^{-11}$. That is far below Monte Carlo noise at $R=10^4$ samples, whose standard error scales as $1/\sqrt{R}$, about one percent. Edges with $p_{uv}$ near 1 have unbounded log-weight and are clamped. We will measure the clamp's effect rather than assume it is harmless.

Kernel layer. We reuse the blocked compressed-sparse-row layout and similarity-based row reordering of SMaT. SMaT maps unstructured sparse matrices onto $16\times 8$ FP16 Tensor-Core tiles and beat dense cuBLAS at sparsity as low as 78%. Its authors evaluated only static scientific matrices and flagged the reordering cost as the obstacle for dynamic use. In our setting the reorder is computed once on the graph topology and reused. Changing $p_{uv}$, switching from IC to LT, or advancing an online learning round changes the values in the blocks, never their positions.

Two diffusion-specific additions are needed. The first is frontier-aware block skipping. Early in a cascade almost all of $X_t$ is zero, so the kernel will consume only the newly activated rows ($X_{t+1}-X_t$) and accumulate $W^\top$ incrementally. The second is hub-row splitting. SMaT reports straggler warps on power-law matrices, and social graphs are far more skewed than SuiteSparse matrices.

Algorithm layer. On top of the kernel we build three uses. The first is batched spread estimation $\sigma(S)$. The second is a lazy-greedy (CELF-style) seed selection in which candidate seeds and samples share the column dimension. The third is fast generation of the Monte Carlo labels that neural surrogates are trained on.

That third use matters. MONSTOR trains a graph network to predict IC influence on unseen graphs. DiffIM trains a graph-network surrogate and backpropagates through it to choose edges to delete for influence minimization. Both are restricted to IC. MONSTOR's authors attribute this to the lack of tight infection-probability bounds under LT. Both depend on ground-truth simulation for training and evaluation. We do not try to fix their LT bounds. We supply the exact simulator that any LT or SIR version of them would need, so the engine is the input to that line of work rather than a replacement for it.

Relation to Prior Work

The closest bridge work has three roles. Two papers motivate the gap; one supplies a constraint.

gIM ports reverse influence sampling to GPUs with warp-cooperative breadth-first search over a compressed-row graph. It reports 33x to 220x over CPU IMM and solves Orkut in 3.6 seconds. Its inner loop flips independent edge coins on CUDA cores, so it is IC-only and does not use Tensor Cores. We change the inner computation from a traversal into a matrix product. That product is unchanged when the cascade model changes.

MATI handles both IC and LT through deterministic, pruned path matrices. It stays within 2% of Greedy, runs on CPUs, and names memory footprint of its path matrices as future work. Its threshold pruning produces a sparsity pattern that depends on the seeds and the model. That is exactly the kind of pattern blocked GPU formats cannot amortize. We keep the graph's own pattern and move all model dependence into values and thresholds.

Maximizing Social Influence in Nearly Optimal Time gives reverse sampling its near-linear guarantee. It acts as a constraint: for pure IC seed selection, reverse sampling is asymptotically cheaper than forward simulation. We therefore do not claim to replace it there.

From the sparsity side, Learning N:M fine-grained structured sparse networks and tile-wise sparsity obtain speedups by forcing a pruning pattern onto learned weights. That option does not exist here: graph edges cannot be dropped to fit a hardware pattern without changing the diffusion. The SMaT route of reorganizing an arbitrary pattern is the only applicable one. RigL and dynamic sparse reparameterization both report that changing unstructured patterns give no wall-clock gain on GPUs. This is a constraint that motivates keeping the pattern fixed.

Finally, the dominance result of A Thorough Comparison Between Independent Cascade and SIR Models states $\sigma_{IC}(S)\ge\sigma_{SIR}(S)$ under matched probabilities. It gives a theorem-level sanity check that our IC and SIR instantiations must satisfy.

Baselines

The naive reference point is a straightforward GPU Monte Carlo simulator that assigns one cascade per thread block and flips explicit edge coins, written separately for IC, LT and SIR. A trusted CPU coin-flip simulator from the same codebase serves as ground truth for distributional checks. Beating the GPU version means higher simulated edge-samples per second at matched estimation error, on every model.

The strongest existing system is gIM. It reports Orkut seed selection in 3.6 seconds versus over 13 minutes for CPU IMM, and 33x to 220x speedups. No reported result was found on Lacuna for gIM on LT, because it does not support LT. We run it on Orkut, LiveJournal and the MATI networks, on the same GPU, with the same $k$ and $\epsilon$. We compare final spread, measured by our ground-truth simulator, against wall-clock time. On IC seed selection, matching gIM within a small constant factor would already be notable, given reverse sampling's asymptotic advantage. We do not expect to beat it outright.

For LT, the fair strong competitor is something we must build. Under the live-edge view of LT, each node keeps at most one incoming edge, so a reverse-reachable set is a random reverse walk. We implement this as a gIM-style random-walk sampler on CUDA cores. On LT, our engine beats it if it reaches equal spread in less wall-clock time.

For accuracy on small graphs, MATI is the reference, with its reported within-2%-of-Greedy result on NetHEPT, WikiVote, Epinions and Email-EuAll. Beating it means matching Greedy more closely at lower time.

For surrogate-label generation, the comparison is against the label budgets used by MONSTOR. It reports Pearson and Spearman correlation of 0.998 or higher on WannaCry, Celebrity and Extended. Success is retraining it with our labels at equal correlation in a fraction of the label-generation time.

Three kernel ablations isolate the key ingredient, holding the reformulation fixed. The first runs the reformulated update through cuSPARSE compressed-row SpMM with no reordering. The second uses dense cuBLAS GEMM, padded where memory allows. The third uses Tensor-Core blocking with reordering recomputed every round, which isolates the value of amortization. All variants share data, $R$, precision and thresholds.

Why not just…?

Why not just use gIM-style reverse sampling and port it to each model? For IC seed selection this is a real threat, and plausibly the better tool. Reverse sampling's guarantee from Borgs et al. is near-linear, while forward simulation pays per sample per step. Our engine's case rests elsewhere. It handles tasks reverse sampling does not directly serve: spread estimation for fixed seeds, influence minimization evaluation, SIR-style recovery, and surrogate labels. It also offers one code path where the alternative is a separate traversal per model. The head-to-head on Orkut and LiveJournal, plus the LT random-walk baseline, will show exactly where each wins. If ours loses even on LT, the claim narrows to estimation workloads.

Why not just run the same threshold reformulation through cuSPARSE? This could capture most of the benefit. The main gain may come from batching $R$ samples into dense columns, not from Tensor Cores. SMaT reports up to 125x over cuSPARSE on scientific matrices, but those matrices are far less skewed than social graphs. The cuSPARSE ablation answers this directly. If cuSPARSE is within about 1.5x of the blocked kernel on social graphs, we will report the reformulation as the contribution and the kernel as optional.

Why not just multiply densely with cuBLAS? On graphs like NetHEPT (15K nodes), a dense FP16 matrix fits easily in memory and dense GEMM may simply win. On Orkut-scale graphs it is infeasible in memory. We will report the crossover in node count and edge density, rather than claiming universality.

Why not just use a trained graph-network surrogate or a topology heuristic like LIR? LIR runs in linear time with stable spread across IC and LT, but it cannot evaluate a given seed set or an edge deletion. Its authors also note that propagation-based methods keep an edge on LT. Surrogates such as DiffIM are approximate and IC-only, and they consume exactly the simulations this engine produces. We include LIR in the seed-selection comparison, and treat surrogates as downstream consumers.

Proposed Experiments

Exactness first. On NetHEPT, WikiVote, Epinions and Email-EuAll, we draw $10^5$ cascades per model from both the reformulated engine and the CPU coin-flip simulator, for fixed random seed sets. We compare the full spread distributions with two-sample Kolmogorov–Smirnov tests. Failure to reject across models, and the per-step activation profiles, are the bar. We also check that the IC and SIR instantiations reproduce $\sigma_{IC}\ge\sigma_{SIR}$ on every graph and seed set. Precision is tested by comparing FP16-weight runs against FP64 runs and by sweeping the clamp on near-certain edges.

Throughput across models. On the MATI networks, Orkut, LiveJournal, the WannaCry, Celebrity and Extended cascade graphs, and R-MAT graphs of increasing skew, we measure simulated edge-samples per second. The decisive prediction is that our engine's IC/LT throughput ratio stays near one. The per-thread baseline should vary substantially across models. If our ratio drifts far from one, the "model-agnostic" claim fails.

Amortization. We report reordering time as a fraction of total time as samples accumulate. We also run an online setting in which edge probabilities are re-estimated each round, in the style of Fair Online Influence Maximization. The check is whether a single reorder holds its speedup across rounds where only weights change, against re-reordering every round.

End-to-end. Seed selection for $k\in\{10,50,100\}$ under IC, LT and SIR is compared against gIM, the LT random-walk sampler, MATI and LIR, on spread versus time. We also retrain MONSTOR with labels from our engine and measure label-generation time at matched correlation, extending it to LT labels as a demonstration that the missing ingredient is now available.

The proposal is confirmed if three things hold. The reformulated simulator is distributionally exact. Its speed is flat across cascade models. Its preprocessing cost vanishes over a realistic workload.