REVIEW 3 major objections 5 minor 45 references
Bayesian inference of network structure from information cascades
T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read A Bayesian MCMC sampler can recover the network behind observed cascades, and keeps working when data are too scarce for NETINF.
desk verdict Useful Bayesian MCMC for network inference, but Eq. (1) omits the temporal-ordering indicator that the determinant shortcut depends on. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the cascade likelihood written as a sum over directed propagation trees. Each node in a cascade has a single parent, so a cascade on a graph is a tree; the paper expresses $P(c|G)$ as a weighted sum over all trees consistent with the observed activation times, with edge weights $w_{u,v}=P(u,v|c)=\exp(-\Delta_{u,v}/\alpha)$ and a factor $\beta^q(1-\beta)^r$ for transmission and non-transmission events. Tutte's directed matrix-tree theorem turns this super-exponential sum into the determinant of a reduced graph Laplacian, making the Metropolis-Hastings acceptance ratio a ratio of determinants computable in polynomial time. The TNT proposal distribution, which alternately proposes edge additions and removals, supplies the mixing needed for MCMC on sparse graphs.
What would settle it
Enumerate all directed trees consistent with a small cascade on a graph with $n\le 5$ nodes and compare the exact weighted sum from Eq. (4) with the determinant formula used in the sampler; if the determinant counts trees whose edges point backward in time, the two numbers will differ, showing that the sampler targets a different likelihood than the stated model.
Extended reading notes
Core claim
On its own terms, the central claim is that the posterior distribution $P(G|C)$ of networks conditioned on a set of observed cascades can be sampled by MCMC, and that the resulting edge marginal probabilities $q_{ij}=P((i,j)\in E|C)$ are an accurate and uncertainty-aware estimate of the true network. The claim includes a specific performance assertion: with limited cascade data, this Bayesian method produces estimates where NETINF, a greedy submodular-optimization baseline, cannot return the requested number of edges, and it improves ROC AUC and false-positive alarm rates on both synthetic and real email networks.
Load-bearing premise
The inference is only as good as the assumption that cascades really were generated by the independent cascade model with a known transmission probability and exponential waiting times, and that every activation was observed with no missing data or outside influence.
Editorial extensions
If this is right
- With scarce cascade data, the method yields edge-probability estimates and uncertainty bounds in settings where greedy NETINF fails to produce any result at all.
- The full posterior lets practitioners set decision thresholds according to the cost of false positives, for example reporting the true-positive rate at a 1% false-positive alarm, which point-estimate methods cannot do.
- Because the likelihood machinery only requires that the cascade model's likelihood be evaluable, the same MCMC framework extends to discrete-time IC, epidemiological, Hawkes, and power-law waiting-time models.
- Approximate knowledge of the transmission probability $\beta$ and the prior edge probability $p$ changes the density of the inferred graphs but does not greatly change the relative edge probabilities, so exact parameter estimates are not needed for good ranking.
- On the tested real email networks the method reaches AUC values from 0.74 to 0.95 across departments, compared with roughly 0.5 for NETINF on the same data.
Reading between the lines
- The authors do not test this, but the posterior marginals could drive active data collection: a practitioner could choose which cascades to observe next by picking those expected to shrink the entropy of $P(G|C)$ the most.
- A likely, untested failure mode follows from the paper's stated no-missing-data assumption: unobserved activations or outside sources could make the posterior overconfident and push probability onto false edges, and deleting 10–20% of activations in a simulated cascade set would map how much bias that introduces.
- A concrete check implied by the equations: a faithful implementation must assign zero weight to edges whose transmission times contradict the observed activation order, and exact tree enumeration on small graphs can verify that the determinant formula does so.
- The spread of results across email departments hints that the method's advantage is largest on sparse networks; if that pattern generalizes, its practical niche is sparse, poorly observed networks rather than dense ones.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a Bayesian MCMC method for inferring the posterior distribution P(G|C) of a network from observed information cascades under a continuous-time independent cascade model. The likelihood P(c|G) is written as a weighted sum over spanning trees and evaluated in polynomial time using Tutte's directed matrix-tree theorem; an Erdős-Rényi prior and a tie/no-tie proposal are used in a Metropolis-Hastings sampler. Posterior edge marginal probabilities are used as point and uncertainty estimates, and experiments on synthetic (ER, Forest Fire, core-periphery, hierarchical) and email networks compare the method with NETINF, claiming improved recovery especially with limited data.
Significance. If the temporal-ordering gap described below is fixed, the paper makes a useful contribution: it provides a principled Bayesian alternative to NETINF with quantified uncertainty, exploits a classical determinant theorem to avoid exponential tree sums, and includes a sensitivity analysis for the parameters β and p. The synthetic evaluation uses the same generative model for simulation and inference, which is standard and not circular because the ground-truth network is not used to set parameters. The paper is also honest about assuming no missing data and known generative parameters. The principal correctness concern—the missing indicator t_v>t_u in Eq. (1)—directly affects the likelihood used in every MCMC acceptance ratio, and therefore must be resolved before the central claim can be accepted. With that fixed, the contribution should be of interest to the network-inference community; without it, the reported posterior marginals are not guaranteed to correspond to the stated posterior.
major comments (3)
- [§3.1–3.2, Eq. (1), Theorem 1] Equation (1) defines P(u,v|c)=exp(-Δ/α) with no indicator t_v>t_u. For t_v<t_u this quantity exceeds 1 and is not a density; more importantly, the claim in §3.2 that the determinant is 'upper triangular so the adjacency matrix is the product of the diagonals' is valid only when backward-time edges receive zero weight. The following sentence, 'if the tree is inconsistent with the observed data then P(c|T,G) is zero,' is not reflected in the definition of P(u,v|c) or in the Tutte-determinant calculation. If Eq. (1) is used literally, the determinant sums rooted directed spanning trees with edges that point backward in time, inflating P(c|G) by invalid terms; since every Metropolis–Hastings acceptance ratio contains P(c|G), the posterior and the reported edge marginals are biased. Please define P(u,v|c)=0 for t_v≤t_u, include the 1/α normalization if Eq. (1) is to be a density, and explain explicitly how the determinant excludes temporally inconsistent trees.
- [§3.2, Eq. (3), and §3.3] The failure product in Eq. (3) runs over all edges in E\E_T without conditioning on t_u<t_x. In the continuous-time IC model, a node u activated after x cannot fail to infect x, because x is already active; such edges should not contribute a (1-β) factor. The r count used in the acceptance ratio inherits this ambiguity, and the paper's use of out-degree d_out(u) in an undirected setting requires an explicit statement of how undirected edges are oriented in the Laplacian. Please specify the exact edge set over which the stopped-transmission product runs and justify it against the generative model.
- [§4.1.1, Fig. 2; §4.3, Table 2] The NETINF comparison is under-specified. The paper does not state how the requested number of edges e was swept, whether β was fixed to the same value used for simulation, how ties in NETINF's greedy selections were broken, or how ROC points were computed when NETINF returns fewer than e edges. Since the abstract and introduction claim superiority over NETINF under limited data, these details are needed to make the comparison reproducible and fair.
minor comments (5)
- [§3.1, Eq. (1)] The normalization constant 1/α is omitted from Eq. (1); although it cancels in the MCMC ratio for fixed cascade node sets, the equation should be labeled as a density only after adding it.
- [§3.2] The sentence 'if the tree is inconsistent with the observed data then P(c|T,G) is zero' should be made precise: specify that the product P(u,v|c) is zero for t_v≤t_u, and that the Laplacian is built on the subgraph induced by cascade nodes.
- [§1, §2, §5] There are numerous typos, e.g., 'may are invisible' (§1), 'bene ts' (abstract), 'probabiltiy' (Algorithm 1), 'Higherдamma' (§5), and 'Bernoullli' (§2). A careful proofread is needed.
- [§4] No code, data, or detailed MCMC diagnostics are provided; please include burn-in, thinning, chain length, and convergence checks to support the claim that posterior samples are representative.
- [§4.3] For the email network experiments, please report the number of NETINF edges requested and the ground-truth edge count used to compute AUC.
Circularity Check
No significant circularity: the derivation is a self-contained Bayesian application of the independent cascade model with known parameters; no fitted quantity is renamed as a prediction and no load-bearing self-citation chain is present.
full rationale
The paper's derivation chain is not circular. The likelihood P(c|G) is built directly from the IC model (Eq. 1) and Tutte's directed matrix-tree theorem, neither of which is defined in terms of the target posterior P(G|C). The Metropolis-Hastings ratio then combines this likelihood with an Erdős-Rényi prior; the prior and the transmission parameters beta, p, and alpha are assumed known or varied in a sensitivity analysis, not fitted to the edge marginals that are later reported. Evaluation cascades are simulated from the same IC model, which is standard synthetic benchmarking: the ground-truth network is not used to set the inference parameters, so this is not a fit-then-predict construction. The paper's self-citations ([18], [19], [33]) are background or proposal-mechanism references and are not load-bearing for the central claim. One genuine issue is flagged for correctness rather than circularity: Eq. (1) states P(u,v|c)=exp(-Delta/alpha) without an explicit indicator requiring t_v > t_u, while the determinant simplification in Section 3.2 relies on summing only over temporally consistent directed acyclic trees. This is an omitted condition that can bias the likelihood, but it is not a case of a prediction reducing to its inputs by construction; it is a soundness gap in an otherwise self-contained derivation. Accordingly, the circularity score is 0.
Assumptions & free parameters
free parameters (3)
- beta (transmission probability) =
0.4 for synthetic, 0.2 for email
- p (ER prior edge probability) =
Chosen from assumed edge density
- alpha (waiting time scale) =
1 for synthetic data
assumptions (4)
- standard math Tutte's directed matrix-tree theorem
- domain assumption Continuous-time independent cascade model is the true generative process
- ad hoc to paper Zero weight for backward-time edges is implicitly assumed
- domain assumption Complete observation of all activations with no missing data
Cite this review
Pith. "Pith review of Bayesian inference of network structure from information cascades." pith.science (2026). https://pith.science/paper/GYZAK4VI
@misc{pith2026190803318,
author = {Pith},
title = {Pith review of: Bayesian inference of network structure from information cascades},
year = {2026},
howpublished = {\url{https://pith.science/paper/GYZAK4VI}},
note = {Machine review of arXiv:1908.03318}
}
read the original abstract
Contagion processes are strongly linked to the network structures on which they propagate, and learning these structures is essential for understanding and intervention on complex network processes such as epidemics and (mis)information propagation. However, using contagion data to infer network structure is a challenging inverse problem. In particular, it is imperative to have appropriate measures of uncertainty in network structure estimates, however these are largely ignored in most machine-learning approaches. We present a probabilistic framework that uses samples from the distribution of networks that are compatible with the dynamics observed to produce network and uncertainty estimates. We demonstrate the method using the well known independent cascade model to sample from the distribution of networks P(G) conditioned on the observation of a set of infections C. We evaluate the accuracy of the method by using the marginal probabilities of each edge in the distribution, and show the bene ts of quantifying uncertainty to improve estimates and understanding, particularly with small amounts of data.
Figures
Reference graph
Works this paper leans on
-
[1]
Elementary linear algebra: applications version
Anton, H., and Rorres, C. Elementary linear algebra: applications version. John Wiley & Sons, 2010
work page 2010
-
[2]
The origin of bursts and heavy tails in human dynam- ics
Barabasi, A.-L. The origin of bursts and heavy tails in human dynam- ics. Nature 435, 7039 (2005), 207. 9
work page 2005
-
[3]
Braunstein, A., Ingrosso, A., and Muntoni, A. P. Network recon- struction from infection cascades. Journal of the Royal Society Interface 16, 151 (2019), 20180844
work page 2019
-
[4]
Bayesian inference for stochastic epi- demics in populations with random social structure
Britton, T., and O’Neil, P. Bayesian inference for stochastic epi- demics in populations with random social structure. Scandinavian Journal of Statistics 29 (12 2002), 375 – 390
work page 2002
-
[5]
Butts, C. T. Network inference, error, and informant (in)accuracy: a Bayesian approach. social networks 25, 2 (2003), 103–140
work page 2003
-
[6]
Butts, C. T. A perfect sampling method for exponential family random graph models. The Journal of Mathematical Sociology 42 , 1 (2018), 17– 36
work page 2018
-
[7]
Bayesian inference for exponential random graph models
Caimo, A., and Friel, N. Bayesian inference for exponential random graph models. Social Networks 33, 1 (2011), 41 – 55
work page 2011
-
[8]
Submodular Variational Inference for Network Reconstruction
Chen, L., Crawford, F. W., and Karbasi, A. Submodular variational inference for network reconstruction. arXiv preprint arXiv:1603.08616 (2016)
work page Pith review arXiv 2016
Show all 45 references
-
[9]
Clauset, A., Moore, C., and Newman, M. E. Hierarchical structure and the prediction of missing links in networks. Nature 453, 7191 (2008), 98
2008
-
[10]
The flip Markov chain for connected regular graphs
Cooper, C., Dyer, M., Greenhill, C., and Handley, A. The flip Markov chain for connected regular graphs. Discrete Applied Mathe- matics 254 (2019), 56–79
2019
-
[11]
Crawford, F. W. Hidden network reconstruction from information diffusion. In 2015 18th International Conference on Information Fusion (Fusion) (2015), IEEE, pp. 180–185
2015
-
[12]
Bayesian inference of spread- ing processes on networks
Dutta, R., Mira, A., and Onnela, J.-P. Bayesian inference of spread- ing processes on networks. Proceedings of the Royal Society A: Mathe- matical, Physical and Engineering Sciences 474 , 2215 (2018), 20180129
2018
-
[13]
R., Pasumarthi, R
Embar, V. R., Pasumarthi, R. K., and Bhattacharya, I. A Bayesian framework for estimating properties of network diffusions. In Proceed- ings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, NY, USA, 2014), KDD ’14, ACM, pp. 1216–1225
2014
-
[14]
R., and Strandburg-Peshkin, A
Farine, D. R., and Strandburg-Peshkin, A. Estimating uncertainty and reliability of social network data using Bayesian inference. Royal Society open science 2 , 9 (2015), 150367
2015
-
[15]
In Advances in Neural Information Processing Systems (2018), pp
Ghalebi, E., Mirzasoleiman, B., Grosu, R., and Leskovec, J.Dynamic network model from partial observations. In Advances in Neural Information Processing Systems (2018), pp. 9862–9872
2018
-
[16]
Uncovering the temporal dynamics of diffusion networks
Gomez-Rodriguez, M., Balduzzi, D., and Schölkopf, B. Uncovering the temporal dynamics of diffusion networks. In Proceedings of the 28th International Conference on Machine Learning (2011)
2011
-
[17]
Inferring net- works of diffusion and influence
Gomez-Rodriguez, M., Leskovec, J., and Krause, A. Inferring net- works of diffusion and influence. ACM Transactions on Knowledge Discovery from Data (TKDD) 5 , 4 (Feb. 2012), 21:1–21:37
2012
-
[18]
Super-blockers and the effect of network structure on information cascades
Gray, C., Mitchell, L., and Roughan, M. Super-blockers and the effect of network structure on information cascades. In Companion Proceedings of the The Web Conference 2018 (Switzerland, 2018), WWW ’18, International World Wide Web Conferences Steering Committee, pp. 1435–1441
2018
-
[19]
Generating connected random graphs
Gray, C., Mitchell, L., and Roughan, M. Generating connected random graphs. Journal of Complex Networks (2019)
2019
-
[20]
Hawkes, A. G. Spectra of some self-exciting and mutually exciting point processes. Biometrika 58, 1 (1971), 83–90
1971
-
[21]
Not enough data?: Joint inferring multiple diffusion networks via network generation priors
He, X., and Liu, Y. Not enough data?: Joint inferring multiple diffusion networks via network generation priors. In Proceedings of the 10th ACM International Conference on Web Search and Data Mining (2017), ACM, pp. 465–474
2017
-
[22]
R., Handcock, M
Hunter, D. R., Handcock, M. S., Butts, C. T., Goodreau, S. M., and Morris, M. ERGM: A package to fit, simulate and diagnose exponential-family models for networks. Journal of Statistical Software 24, 3 (2008), 1–29
2008
-
[23]
Maximizing the spread of influence through a social network
Kempe, D., Kleinberg, J., and Tardos, E. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, NY, USA, 2003), KDD ’03, ACM, pp. 137–146
2003
-
[24]
H., Robins, G
Koskinen, J. H., Robins, G. L., W ang, P., and Pattison, P. E.Bayesian analysis for partially observed network data, missing ties, attributes and actors. Social Networks 35, 4 (2013), 514–527
2013
-
[25]
Effects of missing data in social networks
Kossinets, G. Effects of missing data in social networks. Social networks 28, 3 (2006), 247–268
2006
-
[26]
Kronecker graphs: An approach to modeling net- works
Leskovec, J., Chakrabarti, D., Kleinberg, J., Faloutsos, C., and Ghahramani, Z. Kronecker graphs: An approach to modeling net- works. Journal of Machine Learning Research 11 , Feb (2010), 985–1042
2010
-
[27]
Graph evolution: Den- sification and shrinking diameters
Leskovec, J., Kleinberg, J., and Faloutsos, C. Graph evolution: Den- sification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD) 1 , 1 (2007), 2
2007
-
[28]
SNAP Datasets: Stanford large network dataset collection
Leskovec, J., and Krevl, A. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014
2014
-
[29]
Discovering latent network structure in point process data
Linderman, S., and Adams, R. Discovering latent network structure in point process data. In International Conference on Machine Learning (2014), pp. 1413–1421
2014
-
[30]
Learning influence from het- erogeneous social networks
Liu, L., Tang, J., Han, J., and Y ang, S. Learning influence from het- erogeneous social networks. In Data Mining and Knowledge Discovery (2012), vol. 25, pp. 511–544
2012
-
[31]
Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications
Lusher, D., Koskinen, J., and Robins, G. Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications . Struc- tural Analysis in the Social Sciences. Cambridge University Press, 2012
2012
-
[32]
D., Stouffer, D
Malmgren, R. D., Stouffer, D. B., Motter, A. E., and Amaral, L. A. A Poissonian explanation for heavy tails in e-mail communication. Proceedings of the National Academy of Sciences 105 , 47 (2008), 18153– 18158
2008
-
[33]
Nguyen, G., and Bean, N
Mathews, P., Gray, C., Mitchell, L., T. Nguyen, G., and Bean, N. SMERC: Social media event response clustering using textual and temporal information. In 2018 IEEE International Conference on Big Data (Big Data) (12 2018), pp. 3695–3700
2018
-
[34]
Learning the graph of epidemic cascades
Netrapalli, P., and Sanghavi, S. Learning the graph of epidemic cascades. In ACM SIGMETRICS Performance Evaluation Review (2012), vol. 40, pp. 211–222
2012
-
[35]
Newman, M. E. J. Estimating network structure from unreliable mea- surements. Physical Review E 98 (2018), 062321
2018
-
[36]
Reconstructing networks with unknown and heteroge- neous errors
Peixoto, T. Reconstructing networks with unknown and heteroge- neous errors. Physical Review X 8 (2018)
2018
-
[37]
Peixoto, T. P. Network reconstruction and community detection from dynamics. arXiv preprint arXiv:1903.10833 (2019)
2019 arXiv
-
[38]
Dani: A fast diffusion aware network inference algorithm
Ramezani, M., Rabiee, H., Tahani, M., and Rajabi, A. Dani: A fast diffusion aware network inference algorithm. ACM Transactions on Knowledge Discovery from Data (TKDD) (06 2017)
2017
-
[39]
Bayesian inference of diffusion networks with unknown infection times
Shaghaghian, S., and Coates, M. Bayesian inference of diffusion networks with unknown infection times. 2016 IEEE Statistical Signal Processing Workshop (SSP) (2016), 1–5
2016
-
[40]
Shaghaghian, S., and Coates, M. J. Online Bayesian inference of diffusion networks. IEEE Transactions on Signal and Information Pro- cessing over Networks 3 (2017), 500–512
2017
-
[41]
Motif-aware diffusion network inference
Tan, Q., Liu, Y., and Liu, J. Motif-aware diffusion network inference. In Advances in Knowledge Discovery and Data Mining (Cham, 2018), D. Phung, V. S. Tseng, G. I. Webb, B. Ho, M. Ganji, and L. Rashidi, Eds., Springer International Publishing, pp. 638–650
2018
-
[42]
Tutte, W. T. The dissection of equilateral triangles into equilateral triangles. Mathematical Proceedings of the Cambridge Philosophical Society 44, 4 (1948), 463–482
1948
-
[43]
Identification of missing links using susceptible-infected-susceptible spreading traces
V ajdi, A., and Scoglio, C. Identification of missing links using susceptible-infected-susceptible spreading traces. IEEE Transactions 10 on Network Science and Engineering (2018)
2018
-
[44]
S., and Li, Z
W ang, S., Hu, X., Yu, P. S., and Li, Z. MMRate: Inferring multi-aspect diffusion networks with multi-pattern cascades. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (2014), ACM, pp. 1246–1255
2014
-
[45]
Proceedings of the National Academy of Sciences 99 , 9 (2002), 5766–5771
W atts, D.A simple model of global cascades on random networks. Proceedings of the National Academy of Sciences 99 , 9 (2002), 5766–5771. 11
2002
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.