Source-linked AI summary
Modeling Information Propagation with Survival Theory
Manuel Gomez Rodriguez, Jure Leskovec, Bernhard Schoelkopf
TL;DR
The paper tackles inference of hidden diffusion networks from observed contagion traces. It uses survival theory to build additive and multiplicative risk models that can be fitted efficiently, with the multiplicative form representing both positive and negative influence. The models generalize prior approaches and support network inference and prediction in synthetic and real cascade settings.
Problem
Hidden diffusion networks must be inferred from observed contagion infection times when the sources of influence are unobserved.
Method
The paper develops survival-theory-based additive and multiplicative hazard models and fits them efficiently by exploiting convexity.
Results
The additive model generalizes several existing approaches, while the multiplicative model represents nodes that increase or decrease another node’s activation risk.
Takeaways & Limitations
The framework infers network structure and influence signs from cascades while supporting prediction of future infections.
Takeaways & Limitations
The multiplicative model excludes interactions between node pairs that never appear together in a cascade to avoid unbounded optimal solutions.
Abstract
from arXiv · showhide
Networks provide a skeleton for the spread of contagions, like, information, ideas, behaviors and diseases. Many times networks over which contagions diffuse are unobserved and need to be inferred. Here we apply survival theory to develop general additive and multiplicative risk models under which the network inference problems can be solved efficiently by exploiting their convexity. Our additive risk model generalizes several existing network inference models. We show all these models are particular cases of our more general model. Our multiplicative model allows for modeling scenarios in which a node can either increase or decrease the risk of activation of another node, in contrast with previous approaches, which consider only positive risk increments. We evaluate the performance of our network inference algorithms on large synthetic and real cascade datasets, and show that our models are able to predict the length and duration of cascades in real data.
1. Introduction
The paper addresses network inference when contagion pathways are hidden, using survival theory to model propagation and recover influential links. It introduces additive and multiplicative risk models, including positive and negative influences, and fits them efficiently.
- Observed infection times can be used to infer edges in hidden networks underlying information, disease, rumor, and behavior diffusion.
- The framework models propagation with survival theory and identifies links by relating a node’s hazard rate to other nodes’ infection times.
- The additive risk model generalizes several existing network-inference approaches that treat previously infected nodes as increasing infection risk.
- The multiplicative risk model allows a node to either increase or decrease another node’s infection risk.
2. Modeling information propagation with survival analysis
The paper represents contagion cascades as infection-time processes and uses survival-analysis concepts to model each node’s hazard from previously infected nodes. The resulting hazard functions support both network discovery and prediction of future infections.
- A cascade records the infection times of all network nodes, using ∞ for nodes not infected during the observation window.
- Each node’s infection status is represented by a nondecreasing counting process, whose cumulative intensity and martingale components follow the Doob–Meyer decomposition.
- The intensity process uses covariates encoding previously infected nodes, while the hazard rate is conditional on those covariates and must remain nonnegative.
- A hazard depending on node j’s infection time indicates a directed edge from j to node i.
- The inferred hazard function both reveals incoming network edges and yields cumulative infection probabilities for predicting future infections.
- The framework supports additive and multiplicative hazards, positive and negative influence, and mixtures of both hazard types across nodes.
3. Additive risk model of information propagation
The additive risk model expresses each node’s hazard as a nonnegative sum of contributions from previously infected nodes, enabling hidden-network inference through convex maximum likelihood. It generalizes several existing diffusion models and yields sparse network solutions.
- The additive hazard is defined as a sum of nonnegative, parent-specific effects weighted by a shared time-shaping function.A nonzero parameter αji indicates an edge from node j to node i.
- The model computes cascade likelihoods from observed infection times, includes survival terms for nodes uninfected by the observation cutoff, and sums log-likelihoods across independent cascades.
- The resulting network inference problem is convex in A, with a unique and computable solution under the stated optimization formulation.
- L1-norm terms encourage sparse optimal networks, while the logarithmic likelihood weakly rewards having multiple infected parents.
- The continuous-time independent cascade model is an additive hazard model, and NetRate, InfoPath, KernelCascade, and moNet map to the general additive framework through suitable time-shaping functions or covariates.
4. Multiplicative risk model of information propagation
The multiplicative risk model represents each parent’s effect through multiplicative hazard factors, allowing positive or negative influence while retaining convex network inference. The formulation requires controls to avoid dense, unbounded solutions and adds sparsity regularization.
- The multiplicative hazard combines a baseline function with parent-specific factors βji, where βji > 1 increases risk, βji < 1 decreases risk, and βji = 1 indicates no edge.The baseline is independent of previously infected nodes and may be fixed or time varying.
- Cascade likelihoods are derived from cumulative infection likelihoods, factorized over infection events, augmented with survival terms for uninfected nodes, and reparameterized using αji = log(βji).
- Maximum-likelihood estimation over independent cascades produces a unique, computable solution, and the multiplicative network inference problem is convex in A.
- Without restrictions, the multiplicative optimum can be dense and unbounded because pairs never co-infected in a cascade may receive arbitrarily large negative influences.
- Restricting parameters to pairs observed in at least one common contagion avoids unbounded solutions, while L1 regularization further encourages sparsity.
- For equal network-recovery accuracy, the multiplicative model requires more cascades than the additive model, making parameter estimation harder than edge discovery.
5. Experimental evaluation
The evaluation compares additive and multiplicative network-inference models on synthetic and real cascade data, measuring recovery accuracy, parameter error, and prediction of cascade size and duration. The models are evaluated across network structures, observation windows, and real information topics.
- Experimental setup: The experiments evaluate additive and multiplicative inference methods on synthetic networks and a real dataset containing more than 10 million information cascades across 3.3 million websites.Synthetic networks mimic real-network structure, while real cascades cover a four-month period.
- Evaluation measures: Edge accuracy measures correctly inferred edges, while MSE measures error in estimated model parameters.These metrics assess network recovery and parameter estimation separately.
- Synthetic-data results: The multiplicative model requires more cascades than the additive model to infer networks at the same accuracy.Parameter estimation is harder than discovering edges and therefore needs additional cascades.
- Synthetic-data results: Longer observation windows improve estimates by exposing more infections, but gains become insignificant after the window is sufficiently large.This saturation is observed for the additive model with exponential time shaping.
- Real-data evaluation: Real-data evaluation fits models on 80% of topic-specific cascades and tests them on the remaining 20%, because true network models are unknown.The train and test sets are disjoint and randomly created.
- Real-data results: Synthetic cascade-size distributions are often very similar to empirical distributions, especially up to 10 infected nodes, although additive model A2 tends to underestimate cascade size.No model is a clear winner in similarity to the test sets.
- Real-data results: Cascade-duration prediction differs more across models than cascade-size prediction, with the additive inverse-linear model closest to empirical duration distributions.The comparison uses test distributions and synthetically generated cascades from trained models.
6. Conclusion
The paper contributes a general mathematical framework for information propagation over networks and flexible inference methods. It identifies extensions involving external influences, nonparametric baselines, additional covariates, dynamic networks, and goodness-of-fit testing.
- Conclusion: The work provides a general mathematical theory of information propagation over networks together with flexible inference methods.The conclusion presents this as the paper’s central contribution.
- Future work: Future extensions include external network influences, nonparametric multiplicative baselines, additional covariates, time-varying parameters, and goodness-of-fit tests.These extensions target richer models, dynamic networks, and more principled model selection.