{"id":"ddf48a15-844d-474c-80cf-711b33415660","arxiv_id":"1908.01393","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Snapshots of consensus dynamics with unknown parameters reveal the network Laplacian via covariance eigenvectors and ordered spectral templates.","lead":"This paper shows how to recover a network from a single snapshot of a spreading opinion process, even when the spreading speed and starting conditions are unknown. The methods use the spread of many independent snapshots and a sparsity search to reconstruct the connections.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4's ordering guarantee uses an unstated uniform spectral-separation condition that the problem setup does not ensure; with α_t arbitrarily small the condition fails and the stated asymptotic claim is not valid.","rationale":"I agree with the reader's overall CONDITIONAL verdict, but my load-bearing concern differs from the reader's weakest_assumption. The reader focused on Assumption 2 (white Gaussian input), which is indeed critical and explicitly tested in Fig. 1(c). However, that is an explicitly stated modeling assumption; the more internal correctness risk is Theorem 4, whose proof smuggles in a uniform spectral-separation condition that is not implied by the problem's assumptions. Since OrderedSpecTemp's ordering constraint (23d) is justified solely by Theorem 4, this undermines the 'theoretical performance guarantees' advertised for Problem 3. The concern is concrete: a valid parameter sequence (α_k→0) can make the guarantee fail. This is not merely a matter of consensus vs. non-consensus; it is a flaw in a stated theorem. I still do not move the verdict to REJECT because the algorithms show strong empirical performance, and the theorem might be repaired by adding a lower bound on the diffusion rates or a minimum eigenvalue gap, with a correspondingly weakened claim. Hence the paper remains conditionally acceptable pending a repair of Theorem 4 and its conditions.","tokens_in":24781,"tokens_out":9524,"duration_ms":100357,"concrete_test":"Construct a counterexample with N=3 and eigenvalues λ=(0,1,2). Let T_k=1 and α_k=1/(2k) for k=1,...,M, with white Gaussian inputs. Compute B^(M)=V^T S_M V for M=10^3,10^4,10^5,10^6 and record how often B_11>B_22>B_33. Because the mean gaps scale like (log M)/M while fluctuations scale like 1/√M, the order should fail on a non-negligible fraction of runs. Also compute τ(M)=min_{i<j,k≤M}(h_k(λ_i)-h_k(λ_j)) and show τ(M)→0, so the proof's required separation is absent.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim includes 'theoretical performance guarantees' for the proposed algorithms. For Problem 3, OrderedSpecTemp (Algorithm 3) relies on Theorem 4 to justify the eigenvalue-ordering constraint (23d). But Theorem 4's proof introduces an assumption that is not part of the problem statement: 'We further assume that h_k(λ_i)>h_k(λ_j)+τ when i<j for some τ>0, where τ does not depend on M.' This condition is not guaranteed by the consensus model in Section II-B, which only requires 0<α_t^(k)<1/λ_N and finite T_k. For a valid sequence of filters, e.g., T_k=1 and α_k=1/(k λ_N), the gap h_k(λ_i)-h_k(λ_j) is proportional to 1/k and tends to 0, so no uniform τ>0 exists. Consequently, the means e_i in (20) can be separated by O((log M)/M) while the fluctuations of B_ii are O(1/√M); the desired ordering B_11>B_22>... can fail with non-negligible probability for arbitrarily large M. Thus the proof of Theorem 4 is invalid as written, and the theoretical support for the key ordering constraint in OrderedSpecTemp is not established. The paper does not flag this as a limitation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the problem of inferring the weighted, undirected graph Laplacian of a network from snapshot observations of discrete-time consensus dynamics, under three increasingly uncertain parameter regimes: unknown input power only (Problem 1), additionally unknown but constant diffusion rate and observation time (Problem 2), and unknown, possibly different filter parameters per observation (Problem 3). The authors propose two-step procedures that first extract spectral information from the sample covariance of the snapshots and then solve a convex optimization problem to recover a sparse valid Laplacian. The main algorithms are InverseFilter and NearestCGL for Problem 1, OrderedSpecTemp for Problem 3, and a hybrid algorithm for Problem 2. The paper claims theoretical performance guarantees for the spectral estimation steps (Theorems 1-4) and supports the methods with synthetic experiments and two real-world case studies (temperature and senate roll-call data).","tokens_in":25036,"tokens_out":9322,"duration_ms":105877,"significance":"If the theoretical claims were fully valid, the paper would make a useful contribution to network inference from dynamical data: it formalizes a realistic hierarchy of parameter uncertainty, proposes scalable convex algorithms, provides explicit concentration bounds for eigenvector and eigenvalue estimates, and demonstrates practical performance on real-world data. The empirical evaluation is broad, including comparisons with the StructGLasso baseline, robustness checks beyond white Gaussian inputs, and a large-scale experiment on a political-blogs network. However, the central theoretical guarantee for the most general problem (Problem 3) rests on a theorem whose proof introduces an unstated additional assumption, and other guarantees apply only to idealized versions of the algorithms or to the spectral extraction steps rather than to the final Laplacian estimate. These issues do not destroy the empirical value of the paper, but they require substantial revision of the theoretical claims.","major_comments":[{"comment":"The theorem is stated without any condition of the form h_k(λ_i) > h_k(λ_j) + τ with τ independent of M, yet the proof requires exactly this condition to obtain e_i > e_j + σ²τ² in equation (20). Under the standing assumptions of Section II-B, this condition can fail for valid consensus filters: take T_k = 1 and α_k = 1/(k λ_N); then h_k(λ_i) − h_k(λ_j) = (λ_j − λ_i)/(k λ_N), which tends to 0, so no uniform τ > 0 exists. In such cases the means e_i in (20) can approach each other at rate (log M)/M while the fluctuations of B_ii are of order 1/√M, so the ordering (19) has non-negligible failure probability for arbitrarily large M. Thus Theorem 4 is not valid as stated, and the ordering constraint (23d) in OrderedSpecTemp lacks the promised theoretical support. The theorem should be restated with an explicit uniform spectral-separation assumption, or proved under a weaker condition, and the resulting limitation should be acknowledged.","section":"Section V, Theorem 4 (proof, page 8)"},{"comment":"Theorem 2 states the eigenvalue error bound under the assumption that σ is known, but Algorithm 1 estimates σ² as λ_max(S_M) in line 3. As written, the consistency claim for InverseFilter therefore does not follow for the algorithm that is actually proposed. Please either add a bound on |λ_max(S_M) − σ²| (for instance via Weyl's inequality) and propagate it through the root-finding step (10), or state explicitly that Theorem 2 applies only to an oracle version of Algorithm 1 with σ given.","section":"Section IV, Theorem 2 and Algorithm 1"},{"comment":"The proof applies the sub-exponential tail bound of Lemma 3 only in the regime 0 ≤ l ≤ ν_*²/b_*, and then takes the limit 'for small enough l > 0.' For a fixed l > 0, this condition need not hold as M grows, so the displayed probability bound does not establish the stated convergence B_ij → 0 for each off-diagonal entry. The theorem itself is plausible and can be repaired by a direct second-moment argument (since Var(B_ij) ≤ σ⁴/M), but the proof as written is incomplete; the second tail case in Lemma 3 or a Chebyshev-style bound should be used.","section":"Section V, Theorem 3 (proof)"},{"comment":"The abstract claims 'theoretical performance guarantees associated with these algorithms,' but Theorems 1-4 concern only the estimated eigenvectors, eigenvalues, and their ordering; they do not bound the distance between the final output L* of NearestCGL or OrderedSpecTemp and the true Laplacian. If the guarantee is meant to cover the final Laplacian estimate, this should be stated and proved; otherwise the claims should be explicitly scoped to the spectral extraction steps, which is what the theorems actually support.","section":"Abstract and Sections IV-V"}],"minor_comments":[{"comment":"The displayed exponent '−Ml²/(4σ²)' near the end of the proof is dimensionally inconsistent with the preceding bound '−Ml²/(2ν_*²)' and the estimate ν_*² ≤ 2σ⁴; it should read σ⁴ if the preceding bound is used.","section":"Section V, Theorem 3 (proof)"},{"comment":"The white Gaussian input assumption is load-bearing for all three problems, as the paper's own Figure 1(c) demonstrates: with Wishart-colored input, the recovery error does not converge to zero. This limitation is acknowledged in the experiments but could be stated more prominently in the assumptions section, since it is a verifiability concern in practice.","section":"Section III-A, Assumption 2"},{"comment":"The statement that 'the observed results are preserved' for white uniform inputs and other graph models is not supported by a figure or table; this claim should either be moved to a supplement or supported with quantitative results.","section":"Section VI-A, paragraph on robustness"}],"recommendation":"major_revision","confidential_remarks":"The core problem formulations and algorithms are interesting, but the theoretical content currently overclaims. The most serious issue is Theorem 4, where an unstated uniform spectral-separation assumption is needed; without it the theorem is false. If the authors are willing to add that assumption and clearly mark the limitation, the paper could become acceptable. I would also ask the editor to ensure the final version states that the guarantees cover spectral estimates rather than the final optimization output."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nThis paper is worth a serious look, but read Theorem 4 carefully before trusting the Problem 3 guarantees. The core idea—recover the eigenbasis from the sample covariance of consensus snapshots, then fit a sparse valid Laplacian to that spectral template—is sound for Problems 1 and 2, where the filter is shared across samples. The genuinely new parts are Problems 2 and 3 (unknown observation time/diffusion rate and heterogeneous dynamics), the ordering constraint (23d), and the hybrid T-search. Theorems 1–2 give clean, standard concentration bounds for the eigenvector/eigenvalue estimates in the known-filter case, and the experiments are thorough: synthetic ER/SBM/small-world graphs, sensitivity to colored inputs, and two real-world applications. The authors also honestly show that the white-Gaussian-input assumption is load-bearing—Fig. 1(c) demonstrates non-convergence for colored inputs.\n\nThe soft spots, in rough order of importance:\n\n1. Theorem 4, which justifies the eigenvalue-ordering constraint (23d), is not proved under the stated problem assumptions. The proof introduces an unstated condition: h_k(λ_i)>h_k(λ_j)+τ for all k and all i<j, with τ independent of M. The model only requires 0<α_t^(k)<1/λ_N and finite T_k, and valid filters can violate this—e.g., T_k=1, α_k=1/(kλ_N) makes the gap shrink like 1/k, so no uniform τ exists. As written, the theorem's conclusion can fail with non-negligible probability. This is a real gap, not a nitpick. The paper doesn't flag it as a limitation.\n\n2. Theorem 2 assumes σ is known, but Algorithm 1 estimates it from the largest sample eigenvalue. Likely fixable, but the stated guarantee doesn't cover the actual algorithm.\n\n3. The guarantees stop at the spectral estimates—the final convex-optimization output L* has no consistency theorem. The text says 'key steps,' so it's not a contradiction, but the abstract's 'theoretical performance guarantees' oversells slightly.\n\n4. In the experiments, β and ϵ are often chosen as the best values on a grid ('carefully selected'). The comparative claims against StructGLasso would be stronger with a principled selection rule or a sensitivity analysis.\n\n5. Minor: Theorem 3's proof has a typo—the tail exponent should be 4σ^4, not 4σ^2.\n\nOverall: the paper is clearly written, the methods are plausible, and the Problem 2/3 formulations advance prior work. It deserves peer review; a referee should focus on Theorem 4 and ask for either a proof under weaker conditions or an explicit separation assumption on the filters, plus the σ fix and parameter-selection discussion. If those land, it's a useful contribution to the GSP/network-inference community.","headline":"Solid extension of spectral-template network inference to consensus dynamics with unknown parameters, but the ordering guarantee in Problem 3 rests on an unstated filter-separation condition.","tokens_in":25572,"tokens_out":4627,"would_cite":true,"duration_ms":44752,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Consensus snapshots can reveal a network's structure even when the dynamics parameters are unknown.","keywords":["network topology inference","graph Laplacian estimation","consensus dynamics","graph signal processing","stationary graph process","spectral templates","convex optimization","sparse graph learning"],"falsifier":"Generate data exactly as in the paper but draw the initial conditions from a non-white Gaussian distribution with covariance $C_\\xi \\neq I$, then run NearestCGL or OrderedSpecTemp and see whether recovery error still vanishes as $M$ grows; the paper's Fig. 1(c) indicates it will plateau, which would confirm that the white-input covariance is the load-bearing assumption.","tokens_in":24554,"feed_emoji":"🕸️","tokens_out":13910,"duration_ms":119895,"temperature":0.7,"pith_summary":"This paper claims that the graph Laplacian of a weighted, undirected network can be recovered from a set of snapshots of consensus dynamics running on it—opinion updates or temperature diffusion—even when the diffusion rates, observation times, and input signal power are unknown. The key move is spectral: the covariance of the snapshots shares eigenvectors with the Laplacian and has eigenvalues that are a monotone function of the Laplacian's, so the network structure is encoded in second-order statistics even when dynamics parameters are not. The paper proposes a family of spectral-convex algorithms—InverseFilter, NearestCGL, OrderedSpecTemp, and a hybrid—for increasing uncertainty levels, with sample-size-dependent error bounds. If right, real-world network inference from observational snapshots no longer requires separate estimation of the dynamics parameters, and the authors demonstrate the idea on U.S. temperature and voting data.","feed_headline":"Consensus snapshots can map a network even when dynamics are unknown","feed_subtitle":"Algorithms infer a network's weighted structure from opinion or temperature snapshots alone, with no parameter tuning.","key_machinery":"The carrying object is the covariance identity $C_y = \\sigma^2 h(L)^2 = \\sigma^2 V h(\\Lambda)^2 V^\\top$, which converts the unknown Laplacian into a quantity directly readable from snapshot second moments. For the known-filter setting it yields $\\sigma^2$ as the largest eigenvalue of $C_y$ and each $\\lambda_i$ as the unique root of $\\sigma^2 \\prod_t (1-\\alpha_t \\lambda)^2 = \\lambda_i(C_y)$. For the unknown-filter setting, Theorems 3 and 4 supply the eigenvector alignment and inverse-eigenvalue ordering that OrderedSpecTemp converts into the convex constraints of problem (23): $L \\in \\mathcal{L}_c$, near-diagonalization by the sample-covariance eigenvectors, and an approximately increasing sequence $\\gamma$ with $\\gamma_N=1$ and $\\gamma_i \\le \\gamma_{i+\\eta}$.","core_discovery":"The central claim is that the combinatorial graph Laplacian $L$ is identifiable from independent realizations of consensus outputs $y = h(L)\\xi$ even when the filter $h$ and the input power $\\sigma^2$ are unknown. Because the input is white Gaussian, the output covariance is $C_y = \\sigma^2 h(L)^2 = \\sigma^2 V h(\\Lambda)^2 V^\\top$, so $C_y$ and $L$ share eigenvectors, and with known filter parameters each eigenvalue of $L$ can be recovered by inverting the monotone function $h(\\lambda)=\\prod_t (1-\\alpha_t\\lambda)$. When the filter is unknown, Theorem 3 shows that for large sample size $M$ the sample covariance $S_M$ is diagonalized by the same eigenbasis $V$, even if $S_M$ itself does not converge, and Theorem 4 shows the diagonal entries of $V^\\top S_M V$ appear in the inverse order of the eigenvalues of $L$. The paper's central discovery is that this order information, combined with the valid-Laplacian and sparsity constraints of a convex program, suffices to recover $L$ under three levels of parameter uncertainty.","pith_inferences":["A direct extension is to replace consensus filters with any nonnegative, decreasing filter response, such as heat diffusion $e^{-\\tau L}$; the order constraint should carry over unchanged, and a tailored treatment is a natural next step.","The colored-input failure suggests jointly estimating the input covariance $C_\\xi$ rather than the scalar power $\\sigma^2$ could widen the model to non-white inputs, at the cost of an identifiability analysis.","Because the value of eigenvector ordering grows with graph density in the paper's experiments, one could derive a quantitative criterion for when ordering constraints, rather than sparsity, are the primary source of identification.","A practical deployment rule follows from the paper's own stress test: before applying these methods to real data, certify that input snapshots are approximately white, or expect a non-vanishing bias."],"forward_implications":["The InverseFilter estimate is consistent: for $M \\ge N$ samples the spectral error decays as $1/\\sqrt{M}$ (Lemma 1 and Theorems 1–2).","NearestCGL's projection step guarantees the output is a valid combinatorial graph Laplacian and, with the $\\ell_1$ penalty, a sparse one, so downstream spectral graph analysis operates on a proper Laplacian.","In the heterogeneous-dynamics setting, the sample covariance need not converge to a fixed matrix, yet its eigenbasis still aligns with $L$ and the eigenvalue order still holds, making OrderedSpecTemp applicable when the dynamics are least controlled.","The hybrid Algorithm 4 estimates the unknown observation time $T$ by a line search and then refines $L$ with NearestCGL; the experiments place it close to an oracle that knows $T$ (Fig. 2b)."],"supporting_citations":[{"why":"Supplies the preliminary consensus-dynamics formulation and the sub-exponential product and square lemmas used in Theorems 3 and 4.","marker":"[1]"},{"why":"Introduces spectral-template network inference without eigenvalue order information; the baseline that OrderedSpecTemp extends with order constraints.","marker":"[21]"},{"why":"Closest prior work on graph learning from filtered signals; supplies the StructGLasso baseline and the InverseFilter-style first step.","marker":"[23]"},{"why":"Provides the sample-covariance concentration bound used in Lemma 1 and the $1/\\sqrt{M}$ error rates of Theorems 1 and 2.","marker":"[36]"},{"why":"Supplies the eigenvector perturbation inequality used in Theorem 1.","marker":"[37]"},{"why":"Supplies the eigenvalue perturbation inequality used to bound eigenvalue errors in Theorem 2.","marker":"[38]"},{"why":"Provides the sub-Gaussian and sub-exponential tail inequalities that drive the probabilistic parts of Theorems 3 and 4.","marker":"[52]"}],"fun_headline_variants":["Blind network recovery from consensus with unknown parameters","Infer graph Laplacian from consensus snapshots, no parameters known","Consensus echoes map hidden networks despite unknown dynamics","Recover weighted network structure from consensus without tuning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole spectral argument assumes the unknown initial conditions are white Gaussian noise with covariance $\\sigma^2 I$; if the inputs are colored, the snapshot covariance no longer shares eigenvectors with the Laplacian, and the paper's own experiments (Fig. 1c) show recovery error stops converging.","fun_headline_variants_meta":{"raw":{"variants":["Blind network recovery from consensus with unknown parameters","Infer graph Laplacian from consensus snapshots, no parameters known","Consensus echoes map hidden networks despite unknown dynamics","Recover weighted network structure from consensus without tuning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000268,"raw_usage":{"total_tokens":1598,"prompt_tokens":908,"completion_tokens":690,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":524,"completion_tokens_details":{"reasoning_tokens":626}},"tokens_in":524,"tokens_out":690,"duration_ms":7368,"temperature":1.0,"reasoning_tokens":626,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:14:08.760883+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Generate data exactly as in the paper but draw the initial conditions from a non-white Gaussian distribution with covariance $C_\\xi \\neq I$, then run NearestCGL or OrderedSpecTemp and see whether recovery error still vanishes as $M$ grows; the paper's Fig. 1(c) indicates it will plateau, which would confirm that the white-input covariance is the load-bearing assumption.","supporting_citations":[{"cited_title":"Network inference from consensus dynamics,","cited_arxiv_id":null,"evidence_quote":"Supplies the preliminary consensus-dynamics formulation and the sub-exponential product and square lemmas used in Theorems 3 and 4."},{"cited_title":"Graph learning from filtered signals: Graph system and diffusion kernel identification,","cited_arxiv_id":null,"evidence_quote":"Closest prior work on graph learning from filtered signals; supplies the StructGLasso baseline and the InverseFilter-style first step."},{"cited_title":"A useful variant of the Davis-Kahan theorem for statisticians,","cited_arxiv_id":null,"evidence_quote":"Supplies the eigenvector perturbation inequality used in Theorem 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the eigenvalue perturbation inequality used to bound eigenvalue errors in Theorem 2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the sub-Gaussian and sub-exponential tail inequalities that drive the probabilistic parts of Theorems 3 and 4."}],"review_version":1}