{"id":"133c0bb5-153d-4f4f-9088-58f09b4c2d17","arxiv_id":"1908.03318","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A Bayesian MCMC sampler over graphs recovers network structure and edge probabilities from observed information cascades, outperforming a greedy baseline when data is scarce.","lead":"The paper presents a Bayesian MCMC method that samples likely network structures from observed information cascades, giving both a network estimate and a measure of uncertainty for each possible connection. It shows this approach can recover networks with limited cascade data where a common greedy baseline fails.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (1) lacks an indicator for t_v>t_u; the Theorem 1 determinant shortcut in §3.2 depends on zeroing backward-time edges, and without it P(c|G) counts invalid trees.","rationale":"The paper's strongest claim is that MCMC samples from the posterior P(G|C) and that posterior edge marginals beat NETINF when data are sparse. The most load-bearing step is therefore the likelihood P(C|G). I agree with the reader that the temporal-order assumption is the weak point, and I locate it precisely: the determinant simplification in §3.2 collapses to a product of diagonal Laplacian entries only under the ordering t_u<t_v for every weighted edge; otherwise the Laplacian is not upper triangular in a single fixed order. Equation (1) does not state this restriction, and the surrounding text's statement that inconsistent trees are zero does not identify which trees are inconsistent or how the zero enters Eq. (4). The concern is not merely about model misspecification or robustness to external influence; it is an internal consistency issue in the computation of the acceptance ratio. The suggested 3-node check can be done analytically and separates an expositional omission from an actual implementation error. If the authors confirm backward edges are zeroed, the central construction survives; if not, the posterior estimates in Section 4 are not P(G|C) under the stated model. I do not see a stronger objection than this one; the comparison with NETINF, while imperfect, is secondary because the method's own correctness would need to be established first. I recommend keeping the reader's CONDITIONAL verdict; no adjustment is needed.","tokens_in":12461,"tokens_out":6005,"duration_ms":67411,"concrete_test":"Take a 3-node cascade with activation times t1<t2<t3 and a graph containing edge (3,2) in addition to a valid path 1->2->3. Compute P(c|G) three ways: (i) brute-force enumeration of all time-respecting trees; (ii) determinant of the reduced Laplacian with weights w_{i,j}=exp(-(t_j-t_i)/alpha) set to 0 whenever t_j <= t_i; (iii) the same determinant using Eq. (1) with no zeroing. If (iii) exceeds (i) and (ii) by including the invalid term w_{1,3}*w_{3,2}, the likelihood as written is incorrect; then inspect the sampler output on this example to see whether posterior edge marginals also deviate. This settles whether the unflagged zeroing is harmless exposition or a real bias.","verdict_should_be":"UNCHANGED","load_bearing_attack":"At the core of the likelihood is the claim in §3.2 that, after applying Tutte's theorem, 'the determinant is upper triangular and so the adjacency matrix is the product of the diagonals.' This is true only if every edge (u,v) in a spanning tree satisfies t_u < t_v, because the Laplacian becomes upper triangular when nodes are ordered by activation time. Equation (1) defines P(u,v|c)=exp(-Delta/alpha) with no explicit restriction t_v > t_u; for t_v < t_u this expression exceeds 1 and is not a density. The text says 'if the tree is inconsistent with the observed data then P(c|T,G) is zero,' but the zeroing is never stated in the definition, and the tree-sum/determinant derivation does not show where inconsistent trees are excluded. If the implementation follows Eq. (1) literally, backward edges receive weight exp(+|Delta|/alpha)>1, and Theorem 1 sums over rooted directed spanning trees containing those invalid edges. For example, with times t1<t2<t3 and edges 1->3 and 3->2, the term w13*w32 is included and inflates P(c|G); such a tree cannot transmit cascade c. Since the MCMC acceptance ratio is the ratio of these likelihoods, any error here biases the posterior and the reported edge marginals. The paper's central claim—that the sampler recovers P(G|C)—therefore rests on an unflagged temporal-ordering assumption. This is fixable (add P(u,v|c)=0 unless t_v>t_u) but is not stated, and no code is provided to confirm the implementation actually zeroes backward edges.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12820,"tokens_out":10824,"duration_ms":117984,"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":[{"comment":"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.","section":"§3.1–3.2, Eq. (1), Theorem 1"},{"comment":"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.","section":"§3.2, Eq. (3), and §3.3"},{"comment":"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.","section":"§4.1.1, Fig. 2; §4.3, Table 2"}],"minor_comments":[{"comment":"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.","section":"§3.1, Eq. (1)"},{"comment":"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.","section":"§3.2"},{"comment":"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.","section":"§1, §2, §5"},{"comment":"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.","section":"§4"},{"comment":"For the email network experiments, please report the number of NETINF edges requested and the ground-truth edge count used to compute AUC.","section":"§4.3"}],"recommendation":"major_revision","confidential_remarks":"The central issue is fixable within the scope of a revision. The paper would benefit from releasing code to verify the temporal-ordering handling. I do not see a circularity problem in the synthetic evaluation, but the lack of code makes it hard to know whether the implementation matches the intended model. The manuscript's scope fits the journal, and the presentation needs proofreading."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid, practical method paper with one real gap that needs fixing. The core idea—use Tutte's directed matrix-tree theorem to compute P(c|G) exactly, then sample the graph posterior with TNT MCMC—works, and the empirical comparison to NETINF is largely fair. The missing piece is Eq. (1): the exponential weight exp(-Delta/alpha) is written without requiring t_v > t_u. The text later says inconsistent trees get zero probability, but the determinant simplification in Sec. 3.2 only holds if you zero backward-time edges before building the Laplacian. If the implementation does that, fine; if not, the tree sum includes invalid trees and the posterior is biased. Since no code ships, a referee needs to ask for this to be stated precisely. It is a fixable omission, not a conceptual collapse.\n\nWhat is actually new: unlike NETINF and its descendants, you get a full posterior over graphs, and the Tutte determinant makes the likelihood computable in polynomial time, so MCMC becomes feasible on 1000-node networks. The TNT proposal choice is sensible. The evaluation spans several synthetic network types and a real email network, and the sensitivity analysis for beta and p is exactly what a practitioner wants. The paper also honestly lists limitations: no missing data, static network, assumed-known parameters. Citation coverage is adequate; NetInf and Peixoto are positioned correctly.\n\nSoft spots beyond Eq. (1): NETINF requires the number of edges as input, so the head-to-head comparison is a bit apples-to-oranges; the real-network AUC numbers come without error bars, so the department-to-department differences may not be structural. The novelty relative to Peixoto's 2019 Bayesian reconstruction is incremental, but the determinant-based likelihood is a different, useful formulation.\n\nThis paper deserves a serious referee. Fix the temporal-ordering indicator, release code, and it's a publishable contribution. The math is sound where it matters; the paper just needs to be more careful about what the sum is over.","headline":"Useful Bayesian MCMC for network inference, but Eq. (1) omits the temporal-ordering indicator that the determinant shortcut depends on.","tokens_in":13340,"tokens_out":4698,"would_cite":true,"duration_ms":46907,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62F15","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"A Bayesian MCMC sampler can recover the network behind observed cascades, and keeps working when data are too scarce for NETINF.","keywords":["network inference","information cascades","Bayesian inference","Markov chain Monte Carlo","independent cascade model","uncertainty quantification","matrix-tree theorem","diffusion networks"],"falsifier":"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.","tokens_in":12262,"feed_emoji":"🕸️","tokens_out":12389,"duration_ms":116487,"temperature":0.7,"pith_summary":"This paper tries to establish that the hidden network over which information cascades spread can be inferred as a full posterior distribution over graphs, not just a single best guess, and that this probabilistic view pays off precisely when data are scarce. Using the independent cascade model with exponential waiting times, the authors build a Metropolis-Hastings sampler over adjacency matrices and report each edge's marginal posterior probability. They argue that these marginals recover the true network more accurately than the standard NETINF algorithm in the limited-data regime, and that the accompanying uncertainty estimates support decisions that a point estimate cannot. The experiments cover synthetic networks of several types and real email networks, with AUC values ranging from about 0.72 to 0.97 on the tested cases.","feed_headline":"Sampling the posterior beats NETINF when cascade data are scarce","feed_subtitle":"Each edge gets a posterior probability instead of a yes/no, so uncertainty is quantified and limited data still yield estimates.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the continuous-time independent cascade model, the matrix-tree determinant trick for the cascade likelihood, and the NETINF baseline that the new method is compared against.","marker":"[17]"},{"why":"Defines the independent cascade model of information propagation that the paper adopts as the diffusion mechanism.","marker":"[23]"},{"why":"Provides Tutte's directed version of Kirchhoff's matrix-tree theorem, which turns the sum over propagation trees into a determinant.","marker":"[42]"},{"why":"Introduces the TNT (tie/no-tie) sampler used as the MCMC proposal to improve mixing between edge and non-edge moves.","marker":"[22]"},{"why":"Supplies the real-world email communication network dataset used in the real-network experiments.","marker":"[28]"}],"fun_headline_variants":["Bayesian posterior sampling beats NETINF on scarce cascades","Cascades reveal networks: Bayesian MCMC outperforms greedy","Uncertainty-aware network inference from cascade data","Posterior edge probabilities improve cascade network inference","Bayesian network inference from cascades outperforms NETINF"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Bayesian posterior sampling beats NETINF on scarce cascades","Cascades reveal networks: Bayesian MCMC outperforms greedy","Uncertainty-aware network inference from cascade data","Posterior edge probabilities improve cascade network inference","Bayesian network inference from cascades outperforms NETINF"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000662,"raw_usage":{"total_tokens":2964,"prompt_tokens":820,"completion_tokens":2144,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":436,"completion_tokens_details":{"reasoning_tokens":2067}},"tokens_in":436,"tokens_out":2144,"duration_ms":15665,"temperature":1.0,"reasoning_tokens":2067,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:16:41.237492+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Inferring net- works of diffusion and influence","cited_arxiv_id":null,"evidence_quote":"Supplies the continuous-time independent cascade model, the matrix-tree determinant trick for the cascade likelihood, and the NETINF baseline that the new method is compared against."},{"cited_title":"Maximizing the spread of influence through a social network","cited_arxiv_id":null,"evidence_quote":"Defines the independent cascade model of information propagation that the paper adopts as the diffusion mechanism."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Tutte's directed version of Kirchhoff's matrix-tree theorem, which turns the sum over propagation trees into a determinant."},{"cited_title":"R., Handcock, M","cited_arxiv_id":null,"evidence_quote":"Introduces the TNT (tie/no-tie) sampler used as the MCMC proposal to improve mixing between edge and non-edge moves."},{"cited_title":"SNAP Datasets: Stanford large network dataset collection","cited_arxiv_id":null,"evidence_quote":"Supplies the real-world email communication network dataset used in the real-network experiments."}],"review_version":1}