PaperlayerView exact revision on arXiv

Source-linked AI summary

Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm

Hadi Daneshmand, Manuel Gomez-Rodriguez, Le Song, Bernhard Schoelkopf

arXiv:1405.2936v1cs.SIphysics.soc-phstat.ML

TL;DR

Cascade-based network inference lacks a thorough theoretical account of recovery conditions and required sample sizes. This paper uses ℓ1-regularized likelihood estimation and a soft-thresholding algorithm for continuous-time diffusion, establishing recovery guarantees under a natural incoherence condition. Under that condition, the method achieves exponentially decreasing error with O(d^3 log N) cascades.

  • Problem

    Prior cascade-inference work largely emphasized algorithms and experimental evaluation, while rigorous recovery conditions and cascade requirements remained underexplored.

    Source: §1 · p. 1

  • Method

    The paper combines ℓ1-regularized likelihood estimation for continuous-time diffusion with an efficient proximal-gradient algorithm using soft-thresholding.

    Source: §1 · p. 2, §7 · p. 7

  • Results

    With a natural incoherence condition, the method achieves exponentially decreasing error with O(d^3 log N) cascades.

    Source: §1 · p. 2, §9 · p. 8

  • Takeaways & Limitations

    The work contributes a theoretical foundation for network inference and an efficient implementation for sparse estimation.

    Source: §7 · p. 7, §9 · p. 8

    The analysis assumes all activations arise from network diffusion and are recorded, leaving missing observations and exogenous activations for future work.

    Source: §9 · p. 8

Abstract

from arXiv · show

Information spreads across social and technological networks, but often the network structures are hidden from us and we only observe the traces left by the diffusion processes, called cascades. Can we recover the hidden network structures from these observed cascades? What kind of cascades and how many cascades do we need? Are there some network structures which are more difficult than others to recover? Can we design efficient inference algorithms with provable guarantees? Despite the increasing availability of cascade data and methods for inferring networks from these data, a thorough theoretical understanding of the above questions remains largely unexplored in the literature. In this paper, we investigate the network structure inference problem for a general family of continuous-time diffusion models using an $l_1$-regularized likelihood maximization framework. We show that, as long as the cascade sampling process satisfies a natural incoherence condition, our framework can recover the correct network structure with high probability if we observe $O(d^3 \log N)$ cascades, where $d$ is the maximum number of parents of a node and $N$ is the total number of nodes. Moreover, we develop a simple and efficient soft-thresholding inference algorithm, which we use to illustrate the consequences of our theoretical results, and show that our framework outperforms other alternatives in practice.

1. Introduction

The paper addresses the gap between practical cascade-based network inference and a rigorous account of when hidden networks can be recovered. It develops a continuous-time, ℓ1-regularized approach with recovery guarantees under a natural incoherence condition.

Motivation

  • Earlier work mainly evaluated inference algorithms experimentally, leaving rigorous recovery conditions and cascade requirements largely unresolved.Network reconstruction matters for predicting information spread, maximizing product sales, or stopping infections.Source: §1 · p. 1

Overview of results

  • Under a natural incoherence condition, the ℓ1-regularized likelihood framework recovers network structure with O(d^3 log N) cascades and exponentially decreasing error.The condition depends on network structure, diffusion parameters, and cascade sampling; under an additional finite-sample condition, the overview reports O(d^2 log N) cascades.Source: §1 · p. 2
  • The paper pairs its theoretical framework with an efficient proximal-gradient algorithm whose soft-thresholding step yields sparse estimators.Experiments are reported to show that the framework typically outperforms other state-of-the-art algorithms.Source: §1 · p. 2
  • The recovery condition captures whether non-parent nodes co-occur with a target node less often than its parents do across cascades.Its satisfaction depends jointly on network structure, diffusion parameters, and the cascade sampling process.Source: §1 · p. 2

Related work

  • For general networks satisfying incoherence, the paper reports better rate and sample complexity than First-Edge and a bounded-degree-network algorithm.The related-work comparison describes First-Edge as using a slightly different continuous-time independent-cascade model.Source: §1 · p. 2

2. Continuous-Time Diffusion Model

The model represents diffusion as continuous-time transmissions along network edges, with observed cascades recording node infection times. Its likelihood combines survival and hazard contributions from those observations.

2. Continuous-Time Diffusion Model

  • Each edge has a transmission-time density parameterized by α_ji, rather than a fixed infection probability or round-by-round event generation.Events are sampled directly from edge transmission functions in continuous time.Source: §2 · p. 2

2.1. Cascade generative process

  • A cascade starts from a source drawn from P(s), and contagion propagates along outgoing edges through random transmission times.Transmission times are independent; if multiple neighbors infect a node, only the first is its true parent.Source: §2.1 · pp. 2–3
  • Each cascade is an N-dimensional vector of infection times, with ∞ marking nodes not infected during the observation window.The observation window is shared across cascades, and the clock resets to zero at the start of each cascade.Source: §2.1 · p. 3

2.2. Likelihood of a cascade

  • The cascade likelihood uses survival terms for uninfected nodes and survival and hazard terms for infected nodes; independent cascade likelihoods multiply across observations.The text defines S as a survival function and H as a hazard function.Source: §2.2 · p. 3

3. Network Inference Problem

Network inference is posed as estimating each node’s incoming edges and transmission parameters from cascade timing data. The likelihood separates by node, and ℓ1 regularization is introduced to support finite-sample recovery guarantees.

Network inference formulation

  • The inference target is the directed edges and associated parameters, using only cascade temporal information.A cascade source is drawn from P(s), and inferred edges correspond to nonzero estimated parameters.Source: §3 · p. 3
  • Maximum-likelihood inference decouples into independent per-node problems for estimating each node’s parents and incoming-edge parameters.For node i, the optimization is constrained to nonnegative transmission parameters.Source: §3 · p. 3
  • For a target node, nodes outside its super-neighborhood can be skipped because they cannot be infected before it and their estimated transmission rates are zero.The super-neighborhood combines upstream nodes and nodes reachable from at least one upstream node.Source: §3 · p. 3
  • The unregularized estimator is consistent as cascades grow, while adding an ℓ1 penalty provides finite-sample structure-recovery guarantees.With an appropriate regularization parameter, the solution recovers the network structure with probability approaching one exponentially fast in the number of cascades.Source: §3 · pp. 3–4

4. Consistency

With strictly positive source probability for every node, the maximum-likelihood estimator is consistent. The proof links identification to positive definiteness of the Hessian as the number of cascades grows.

  • Under the stated survival- and hazard-function conditions, the Hessian is a nonnegative diagonal matrix plus the hazard matrix times its transpose.The Hessian captures co-occurrence information among nodes in cascades.Source: §4 · p. 4
  • Strictly positive source probability for every node makes the maximum-likelihood estimator consistent.Consistency means that the estimator recovers the true network structure as the number of cascades grows.Source: §4 · p. 4
  • Identification follows when the Hessian is positive definite, which the proof establishes from full-row-rank hazard matrices as cascades grow.The proof also restricts the parameter space to a compact subset because the likelihood tends to negative infinity at zero and infinite parameter values.Source: §4 · p. 4

5. Recovery Conditions

Finite-sample recovery depends on conditions involving the network, diffusion parameters, and cascade sampling. In particular, non-parent nodes must co-occur less often with a node than its parent nodes do.

  • Recovery difficulty depends on network structure, diffusion parameters, and cascade sampling; incoherence requires non-parent nodes to co-occur less often than parent nodes.The condition captures whether cascade sampling distinguishes parent relationships from non-parent relationships.Source: §5 · p. 4
  • The dependency condition bounds the population Hessian’s eigenvalues, requiring connected nodes to co-occur reasonably often without being deterministically related.It sets positive lower and finite upper eigenvalue bounds for the parent-indexed Hessian block.Source: §5 · p. 4
  • Additional assumptions require Lipschitz-continuous hazard vectors and diagonal terms, plus bounded Hessian entries; exponential, Rayleigh, and power-law transmission likelihoods satisfy conditions 3 and 4.The paper also places boundedness conditions on the hazard vector and gradient at the true parameter.Source: §5 · pp. 4–5
  • For a chain, incoherence depends on source-node probabilities; for a directed tree, it holds under specified positive probabilities for particular source nodes.The chain example gives two inequalities involving source probabilities, while the tree example gives alternative positive-probability requirements.Source: §5 · p. 5
  • For a star with exponential transmission functions, a positive probability of the root being the source suffices for some incoherence margin, whose size depends on the time window and transmission parameters.For an infinite time window, the allowable margin also depends on the ratio of competing transmission parameters.Source: §5 · p. 5

6. Sample Complexity

Under the stated conditions, recovery requires a number of cascades polynomial in parent count and logarithmic in network size. The analysis uses a primal-dual construction to establish exact recovery of incoming edges.

6. Sample Complexity

  • When n > Ld^3 log p, each node’s ℓ1-regularized network-inference problem has a unique solution, and its estimated incoming-edge set includes all true edges and no false edges, with probability at least 1 − 2 exp(−Kλ_n^2 n).Source: §6 · p. 5
  • Under conditions 1 and 2 on the finite-sample Hessian, the required sample complexity improves to n > Ld^2 log p, with the other theorem statements unchanged.Source: §6 · p. 5
  • For recovery of the entire network, a union bound changes the dependence to d_max and the logarithmic term to 2 log N.Source: §6 · pp. 5–6

6.1. Outline of Analysis

  • The proof uses a primal-dual witness construction to satisfy the KKT conditions and match the optimizer’s sparsity pattern to the true parent set.That support match yields recovery of the node’s incoming edges.Source: §6.1 · p. 6
  • When conditions are imposed on the population Hessian, they transfer to the finite-sample Hessian with high probability; the last two lemmas still require n > Ld^3 log p for their error probabilities to vanish.Source: §6.1 · p. 7

7. Efficient soft-thresholding algorithm

The paper solves the network-recovery objective with a proximal gradient algorithm. Its proximal operator is soft-thresholding, yielding sparse solutions.

7. Efficient soft-thresholding algorithm

  • A proximal gradient algorithm addresses the unconstrained, non-smooth convex optimization problem used for network recovery.Source: §7 · p. 7
  • Each iteration computes the likelihood gradient and proximal operator, using either a constant step size or a simple line search.Source: §7 · p. 7
  • The proximal operator is the soft-thresholding operator (v − λ_nL_k)+, which yields a sparse optimal solution.Source: §7 · p. 7

8. Experiments

The experiments test recovery across synthetic network settings and compare the method with NETRATE and First-Edge. Results examine cascade counts, network parameters, regularization, and comparative accuracy.

Experimental Setup

  • The experiments use 128-node Forest Fire and Kronecker networks, simulate infection times, and evaluate recovery with success probability or F1-score.Edge transmission rates are drawn from U(0.5, 1.5); F1 combines precision and recall.Source: §8 · p. 8

Parameters (n, p, d)

  • Success-probability curves for different super-neighborhood sizes pi line up closely when cascade counts scale as n = 10^βd log p.The experiment holds in-degree at 3 and uses an exponential transmission model with T = 5.Source: §8 · p. 8, Figure 3 · p. 8

Regularization parameter λ_n

  • With 150 cascades, success probability flattens for sufficiently large regularization λ_n, but below one when the cascade count may not meet the theorem's conditions.The tested setting uses T = 5.Source: §8 · p. 8

Comparison with NETRATE and First-Edge

  • Our method outperforms NETRATE and First-Edge on a hierarchical Kronecker network with a power-law transmission model and a Forest Fire network with an exponential model.The comparison uses an observation window T = 10.Source: §8 · p. 8, Figure 4 · p. 8

9. Conclusions

The conclusion presents an incoherence-conditioned recovery guarantee and an efficient proximal-gradient implementation, while identifying settings left for future work. The appendix supplies proof arguments for Hessian definiteness and hazard-matrix nonsingularity.

9. Conclusions

  • The method achieves exponentially decreasing error with O(d^3 log N) cascades for general networks satisfying a natural incoherence condition.The paper proposes ℓ1-regularized maximum likelihood inference and an efficient proximal-gradient implementation for a continuous-time diffusion model.Source: §9 · p. 8
  • Missing observations and activations from exogenous factors are outside the stated setting; both are proposed directions for future work.The work assumes all activations arise from network diffusion and are recorded.Source: §9 · p. 8

A. Proof of Lemma 9

  • A non-singular hazard matrix is a sufficient condition for a positive-definite Hessian under the stated log-concavity and concavity assumptions.The proof decomposes the Hessian into a positive-semidefinite term and a positive-definite term.Source: A. Proof of Lemma 9 · p. 10

B. Proof of Lemma 10

  • Strictly positive source probabilities allow an ordering of nodes and cascades that makes the hazard matrix non-singular when the number of cascades is sufficiently large.The proof constructs an upper-triangular block with nonzero diagonal entries.Source: B. Proof of Lemma 10 · p. 10

C. Proof of Eq 7.

The proof uses a Lipschitz condition on the hazard vector to bound a normalized spectral-norm difference.

C. Proof of Eq 7.

  • A Lipschitz condition on the hazard vector is used to bound the spectral norm of the normalized difference between X_n(β) and X_n(α).The bound is stated over the specified parameter domain.Source: C. Proof of Eq 7 · p. 10

D. Proof of Lemma 3

The appendix develops proof bounds for regularized recovery, from optimization properties through concentration and confidence bounds. The supplied passages also outline the distinct roles of the six proof subsections.

D. Proof of Lemma 3

  • The ℓ1-constrained formulation makes the regularization parameter a Lagrange multiplier, and the proof uses KKT conditions to establish zero coefficients outside the active set and uniqueness on that set.Uniqueness follows when the Hessian submatrix on the active set is strictly positive definite.Source: D. Proof of Lemma 3 · pp. 10–11

E. Proof of Lemma 4

  • The Lemma 4 proof constructs a convex function minimized at the estimator and bounds it on a sphere to constrain the estimation error.The sphere radius is chosen as a function of λ_n and neighborhood size d.Source: E. Proof of Lemma 4 · p. 11

F. Proof of Lemma 5

G. Proof of Lemma 6

  • The Lemma 6 proof bounds terms using Cauchy inequalities, Lipschitz continuity, boundedness, and the dependency condition before applying the lemma with a regularization constraint.Source: G. Proof of Lemma 6 · pp. 12–13

H. Proof of Lemma 7

  • The Lemma 7 proof bounds the difference between population and sample Fisher-information matrices, using Hoeffding's inequality for matrix entries.Source: H. Proof of Lemma 7 · p. 13

I. Proof of Lemma 8

  • The Lemma 8 proof controls several terms using earlier bounds and the incoherence condition to obtain confidence bounds.The supplied proof passages also use a union bound over matrix entries.Source: §I · pp. 14–15

J. Additional experiments

Across experiments, Figure 5 curves align across different super-neighborhood sizes, whereas Figure 6 curves differ across in-degrees. The method typically outperforms NETRATE and First-Edge in accuracy against cascade count.

J. Additional experiments

  • For Figure 5, curves for different super-neighborhood sizes p_i line up quite well under cascade scaling n = 10^β d log p, as predicted by Theorem 2.The experiment uses an exponential transmission model and time window T = 10.Source: J. Additional experiments · p. 15
  • For Figure 6, different in-degrees d_i produce noticeably different curves under cascade scaling n = 10^β d log p, as predicted by Theorem 2.The experiment uses an exponential transmission model and time window T = 5.Source: J. Additional experiments · p. 15
  • Our method typically outperforms NETRATE and First-Edge; it needs O(d^3 log N) cascades for success approaching 1 exponentially fast, versus First-Edge's O(Nd log N) and polynomial rate.The comparison is reported for different network types and transmission models.Source: J. Additional experiments · p. 15
Loading 1405.2936v1…