When a rumor, an infection, or a news story spreads, we usually see only when each node became active, not who passed it to whom. Reconstructing the hidden "who-infected-whom" network from those timestamps is a well-studied problem. When the spreading model is known, convex methods solve it well. When the model is wrong, which is the usual case in practice (the delays follow an unknown distribution, a node adopts only after several exposures, or an outside shock activates many nodes at once), those methods can collapse. We propose to learn the inference procedure itself. The procedure is a message-passing algorithm, a routine in which candidate edges and observed infections repeatedly exchange small local updates. We train it on simulated cascades over small networks of 50 to 100 nodes and run it unchanged on networks with thousands of nodes. The design choice that makes this work is to constrain each learned update to be a contraction: every step pulls any two message states closer together by a fixed factor, and that factor does not depend on network size. This guarantees that the procedure settles to a single answer instead of oscillating. It also makes it safe to run more iterations on larger graphs.
In two sentences: inferring a transmission network is, at its core, repeated "explaining away" (deciding which of several earlier-active nodes actually caused an infection), and loopy belief propagation is the natural algorithm for that. We learn its update rule on small graphs and force it to be a size-independent contraction, so it converges and transfers zero-shot to large graphs under spreading models that no hand-derived likelihood captures.
Why this intersection, and what is already done
Classical latent network inference is strong when its assumptions hold. NETRATE models cascades with continuous-time survival analysis under a chosen delay kernel and shows that the log-likelihood is convex in the transmission rates. It recovers more than 95% of edges on synthetic networks and scales to 16,000 nodes. ConNIe reaches a similar convex program through a change of variables. MultiTree-style submodular inference marginalizes over spanning trees and uses greedy selection with a $(1-1/e)$ guarantee. These papers constrain our proposal. Any learned method must match them in the regime where their model is correct, or it has no reason to exist.
The evidence that motivates the proposal comes from misspecification. Diffusion Network Inference for Cross-layer Cascades shows that when cascades mix an observed layer with a hidden low-rank layer, NetRate and MMRate drop to roughly 0.18–0.21 topology accuracy, while its purpose-built mixture model exceeds 0.84. That fix is itself model-specific: a two-layer EM with parametric kernels. The file lists further failure modes of the classical line that no existing method in it handles: complex contagion, shared external shocks, and inhibition.
The neural inverse-map line learns to propose graphs from dynamics. GraIP pairs a discrete graph proposer with a forward simulator. MTGNN and GLCN learn adjacency jointly with a downstream task. All of these fix the node set at training time, and none asks whether the message passing they run converges. The cross-scale line shows that size transfer is achievable when the computation is local and the per-step state stays in-distribution. BQ-NCO keeps the solver inside its training distribution by reducing the state to the remaining subproblem. IREM transfers from 10- to 30-node shortest paths by spending more descent steps at test time. Both assume the graph is given.
The belief propagation (BP) literature supplies both the method and a warning. On a graph with cycles, BP's messages can circulate and double-count evidence, oscillate, or stall (Frey et al., Wan et al.). On the other hand, max-product BP for Noisy-OR networks recovers latent bipartite structure where mean-field variational inference fails outright, because BP keeps the explaining-away logic. It reports 0.99 IOU on blind deconvolution, and the mean-field method fails completely. BP-AMP for spreading processes runs BP over infection pathways, but on a known contact graph. From Fields to Random Trees sidesteps loopy BP's failures by solving exactly on sampled spanning trees, again on a given graph.
The closest combination in the file is therefore split across papers. BP is used for spreading on known graphs. Neural inverse maps infer graphs at fixed size. Size-transfer methods assume known graphs. No work learns a convergent, size-transferable inference procedure for the latent network itself. That is the gap we target.
Core Claim
Inferring a cascade network can be written as inference on a factor graph, a bipartite structure of variables and the local constraints that link them. The variables are candidate directed edges. There is one factor for each (cascade, infected node) pair, encoding "at least one earlier-active candidate parent transmitted, by this time." Additional factors record survival, meaning the node was exposed but stayed uninfected. The factor graph is loopy because the same edge appears in many cascades. Its local structure, however, is size-independent: each factor sees only the candidate parents that activated before its node in one cascade.
We claim that a learned update on this factor graph, trained under a distribution of spreading models, can do three things when it is constrained to be a contraction whose rate is independent of network size. It can match NETRATE when NETRATE's model is correct. It can clearly beat NETRATE under misspecification. And it can transfer from training networks of about 100 nodes to test networks of about 5,000 nodes with little loss.
The contraction condition is the part we add. Let $m$ be the vector of all edge-to-factor and factor-to-edge messages, and $\Phi_\theta$ the learned update. We require
$$\|\Phi_\theta(m) - \Phi_\theta(m')\|_\infty \le \gamma\,\|m - m'\|_\infty,\quad \gamma<1,$$
where $\gamma$ must not grow with the number of nodes $N$, the number of cascades, or the factor degree (the number of candidate parents). We obtain this by bounding the Lipschitz constant of each per-message network, the factor that says how much its output can change per unit change in its input. We keep that constant below $\gamma$ through spectral normalization. The aggregation over a factor's incoming messages is degree-normalized, an average-type pooling rather than a sum. In the $\ell_\infty$ norm the global Lipschitz constant is then the maximum over single messages, so it cannot grow with graph size. This is why the approach should transfer. A bigger graph changes how many messages exist, not how much any one update can amplify disagreement, so the fixed point exists, is unique, and is reached geometrically. On larger or denser graphs we simply run more iterations until the fixed-point residual falls below a tolerance, which is IREM's test-time compute knob with a convergence guarantee attached.
Research Program
The system has three parts.
The first is a candidate-edge generator that avoids the $O(N^2)$ blowup. A directed pair $j\to i$ is kept only if $j$ activates before $i$ within a delay window in at least $r$ cascades. This gives a sparse candidate set whose size grows roughly with $N$ times the typical cascade overlap. We report the recall ceiling this imposes, so no downstream gain is attributable to a lenient filter.
The second is the learned contractive message passing on the factor graph above. Edge-node inputs are delay histograms and co-activation counts. Factor-node inputs are the set of candidate-parent delays. The outputs are edge posteriors and rate estimates.
The third is a training distribution meant to force the update to learn inference rather than memorize one model. We simulate cascades on Kronecker, Forest Fire, Erdős–Rényi, and scale-free graphs of 30–120 nodes. The delay kernels are exponential, power-law, and Rayleigh, plus mixtures of these. The spreading models include independent-cascade transmission, two-exposure threshold contagion, Poisson external shocks that activate random node sets, and a hidden-layer mixture in the style of the cross-layer paper. Training unrolls a fixed number of iterations, applies a loss on edge posteriors at the final iterate, and adds a fixed-point residual penalty so the model is not rewarded for a lucky transient.
We will also run an analysis. We will measure how often an unconstrained learned update and hand-derived damped BP fail to converge as graphs grow and short cycles become denser, and whether those failures predict edge errors. We will also look for an analogue of the algorithmic "hard phase" that BP-AMP reported for source inference: a range of cascade counts where the edges are statistically recoverable, shown by a large-budget exact-likelihood estimator on the true model, yet message passing fails. A contraction guarantees convergence, not correctness. If such a regime exists, the contraction will converge to a wrong unique answer there, and we want to know where that happens.
Baselines
The naive reference point is co-activation ranking. It scores each candidate edge by how often $j$ precedes $i$ within the delay window, normalized by $j$'s activity, and thresholds at the true edge count. It uses the same candidate set as our method, so any gain above it comes from inference, not filtering.
The strongest well-specified competitor is NETRATE. The file reports that it recovers "more than 95% of the edges" on synthetic networks with "less than 25% error" on rates, and discovers "over 60% of the real hyperlink edges" on MemeTracker. We run it with the kernel family chosen by held-out likelihood among its three kernels, so it is not handicapped, and on the same cascades. We restrict its candidates to our set and also run it unrestricted, to confirm that the filter does not hurt it. ConNIe reports precision–recall break-even points of "over 0.85 to 0.95" on 512-node synthetic scale-free and Erdős–Rényi graphs, and we replicate that setting directly. The submodular tree method is the speed reference, reported at about 12ms per edge added on 200,000 nodes.
In the hidden-layer regime the strongest competitor is the cross-layer mixture model, with reported topology accuracy "over 0.84" against 0.18–0.21 for NetRate and MMRate. For point-process data we use the Hawkes network model.
The strongest neural competitor is an unstructured amortized inverse map in the style of GraIP. It is a GNN over the candidate graph that reads the same features and outputs edge probabilities, without the factor-graph structure. It gets the same training simulator, the same parameter count, and the same tuning budget. We use 30 random-search trials for every learned method, and the classical methods get a matching grid over their regularization and kernel choices.
Three further comparisons isolate the key ingredient. The first is our architecture without the spectral and degree-normalization constraints, trained identically. The second is hand-derived damped loopy BP under the true generative model, available only in simulation, which is an oracle for "does learning the update help beyond knowing the model." The third is our architecture trained directly at the target size, as an upper bound on what transfer loses.
We count it as a win in three cases. The first is matching NETRATE's break-even point within 0.02 in its well-specified regime. The second is beating it and the unstructured GNN by at least 0.10 break-even in the complex-contagion, shock, and mixed-kernel regimes. The third is losing less than 0.03 break-even when moving from training size to 50× larger test graphs, while the unconstrained ablation loses clearly more.
Why not just…?
Why not just run NETRATE or ConNIe, which are convex and already scale? In their own model class they are hard to beat, and we expect only to tie there. That tie is a required result, not a failure. Their weakness is that the likelihood is fixed in advance. The cross-layer paper's 0.18–0.21 accuracy for NetRate under a hidden layer shows how badly a wrong likelihood can fail. Complex contagion and shared shocks have no convex surrogate in the file. If NETRATE with kernel selection stays within 0.05 of our method in the misspecified regimes, the proposal's premise is wrong, and the experiment reports that plainly.
Why not just train an unstructured GNN inverse map, as in GraIP or MTGNN? Such a map can learn misspecified models too. The question is whether it transfers across scale and resolves indirect transmission. On larger graphs the number of alternative indirect paths A→C→B grows. Handling that requires explaining away, which is what BP preserves and mean-field methods lose, per the Noisy-OR results. The head-to-head at matched parameters and training data, stratified by how many indirect paths exist per false-positive edge, settles this directly.
Why not just run ordinary damped loopy BP on a hand-derived likelihood? If the model is known, this oracle may well win, and we include it to find out. When the model is unknown there is no likelihood to derive. Damping also offers no guarantee against the oscillations documented by Wan et al.. The comparison between the learned constrained update and oracle BP measures what learning buys and what it costs.
Why not just train at the target scale? For synthetic data this is feasible up to a few thousand nodes, and we run it as the upper bound. The case for transfer is that real deployments do not match any training size, and simulation-plus-training cost grows with $N$ and cascade length. BQ-NCO shows how badly neural solvers without a size-invariant design do off-size, with gaps often exceeding 20–40% on TSP-1000. If direct training at size is cheap and clearly better, transfer is a convenience rather than a contribution, and we will say so.
Proposed Experiments
The first experiment is synthetic. We use Kronecker, Forest Fire, Erdős–Rényi, and scale-free graphs, including the 512-node, 1024-edge ConNIe configuration, and test at 500, 1,000, and 5,000 nodes after training at 30–120. We cross network size with four spreading regimes: well-specified single kernel, mixed kernels, two-exposure contagion, and external shocks, plus the hidden-layer mixture. Metrics are precision–recall break-even, rate MAE, iterations to reach a residual of $10^{-4}$, and the fraction of runs that never reach it.
The real-data experiment uses the MemeTracker top-1,000 sites with hyperlinks as ground truth, where NETRATE's 60% is the reference, and the email (593 nodes), collaboration (379), and recommendation (275) networks from ConNIe. It also uses the 104-department sociology topic diffusion data from the cross-layer paper, where the 0.84 accuracy is the reference. As a downstream check in the spirit of Learn to Vaccinate, we minimize spectral radius, the largest eigenvalue of the adjacency matrix that governs epidemic spread, on each inferred graph. We then measure time to extinction under SIS dynamics on the true graph. That paper found vaccination efficacy plateaus early, so we treat this as a secondary check, not a headline.
Three results would be decisive. First, as synthetic graphs grow 50×, the unconstrained ablation's non-convergence rate should rise and its break-even should fall, while the contractive model's should not. If both behave identically, the contraction constraint is not doing the work we claim. Second, in the misspecified regimes, our method should beat both NETRATE with kernel selection and the matched unstructured GNN by the stated margin. Third, the hard-phase scan should show whether there is a band of cascade counts where the fixed point is unique but wrong. That result tells us where convergence guarantees stop being enough, and it is worth reporting whichever way it comes out.
References
- Uncovering the Temporal Dynamics of Diffusion Networks
- On the Convexity of Latent Social Network Inference
- Submodular Inference of Diffusion Networks from Multiple Trees
- Diffusion Network Inference for Cross-layer Cascades
- GraIP: A Benchmarking Framework for Neural Graph Inverse Problems
- Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks
- Semi-Supervised Learning With Graph Learning-Convolutional Networks
- BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
- Learning Iterative Reasoning through Energy Minimization
- A Revolution: Belief Propagation in Graphs with Cycles
- H3DFact: Heterogeneous 3D Integrated CIM for Factorization with Holographic Perceptual Representations
- Learning Noisy OR Bayesian Networks with Max-Product Belief Propagation
- Inference in Spreading Processes with Neural-Network Priors
- From Fields to Random Trees
- Discovering Latent Network Structure in Point Process Data
- Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control