{"id":"5f74c9c6-9ff9-4244-9763-067351212ae7","arxiv_id":"2510.19441","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Conditional entropy of heat diffusion on a connected graph starts at zero and increases monotonically to log N, with exact finite-time formulas for complete, path, and circulant graphs and a mean-field approximation for Erdős-Rényi graphs.","lead":"The paper defines conditional entropy for heat diffusion on graphs and proves it increases monotonically in time, an information-theoretic analogue of the second law, with exact curves for complete, path, and circulant graphs. Why read it: it gives rare finite-time formulas for entropy on networks and connects network diffusion to information theory.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.4 is sound; the real gap is the unproven pointwise path/complete bounding curves, which are asserted in Fig. 2 but only supported heuristically.","rationale":"I checked Theorem 3.4 independently. Its proof is a direct application of data processing for KL divergence: for each row distribution r_i(t), stationarity of the uniform π gives D_KL(r_i(t+τ)||π) ≤ D_KL(r_i(t)||π), and because π is uniform this is exactly log N − H_i(t) ≤ log N − H_i(t+τ). Averaging over the initial distribution then yields monotonicity for every Z(0). So the central claim — the 'second law' — is secure. A minor sign error appears in the proof of Prop. 3.3, but that proposition is not needed for Theorem 3.4 and the intended argument is recoverable.\n\nThe reader's weakest-assumption analysis identifies the same real soft spot: the pointwise bounding of entropy curves by path and complete graphs. The paper's own introduction says these bounds are 'heuristically established,' yet Fig. 2's caption presents them as a fact. Section 3.4 gives spectral-gap comparisons and asymptotic statements, but a pointwise statement about H(t) is much stronger. Spectral interlacing controls eigenvalues; it does not control the nonlinear entropy functional at finite times, which also depends on eigenvectors through the initial-condition weights. So the concern is legitimate.\n\nHowever, this concern is not load-bearing for the main theorem. The second-law result does not rely on the bounds; the exact formulas for complete, path, and circulant graphs are independent; and the mean-field approximation is explicitly labeled approximate. The overclaim in the figure caption and abstract should be fixed, and a numerical search would settle whether the bounds happen to hold. Since the reader already recommends CONDITIONAL, my assessment leaves the verdict unchanged.","tokens_in":20082,"tokens_out":20279,"duration_ms":165116,"concrete_test":"Enumerate all connected graphs on N=5,6,7 (and, if feasible, random samples for N=20,50) with uniform initial condition. For each graph G, compute H_G(t) = −(1/N) Σ_i Σ_j T_ij(t) log T_ij(t), where T(t)=e^{-tL_G}, on a log-spaced time grid from 1e-3 to 1e3. Check whether H_{P_N}(t) ≤ H_G(t) ≤ H_{K_N}(t) for every t. Record the first violation, if any. If a violation is found, the Fig. 2 caption and abstract's 'bounds' claim are false and must be qualified; if no violation is found, the heuristic is strengthened but a proof is still needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central monotonicity claim, Theorem 3.4, is correct. For each starting node i, the row r_i(t)=e_i^T e^{-Lt} evolves by the same stochastic kernel, and the uniform distribution π is stationary; data processing gives D_KL(r_i(t+τ)||π) ≤ D_KL(r_i(t)||π). Since π is uniform, H_i(t)=log N − D_KL(r_i(t)||π), so each row entropy is nondecreasing, and averaging over Z(0) preserves monotonicity. Thus the second-law result is not the weak point.\n\nThe load-bearing weakness is the pointwise bounding claim used in Figures 2 and 3: that every graph's entropy curve lies between the path-graph curve below and the complete-graph curve above. Section 3.4 proves only eigenvalue interlacing (Prop. 3.17), minimal algebraic connectivity of the path (Prop. 3.19), and asymptotic limits. None of these implies a pointwise ordering of H(t) at finite times: H(t) is a nonlinear function of the full spectrum and the eigenvectors, and a graph with a slightly larger spectral gap but larger prefactors could in principle cross the path curve. The introduction itself calls the bounds 'heuristically established,' yet the Fig. 2 caption states them as fact ('The entropy curves are bounded from below...'), and the abstract lists 'bounds' among the contributions. If a crossing exists at finite time, the bounding-reference interpretation and the 'bounds' claim fail, although the second law would remain intact.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the conditional entropy H(Z(t)|Z(0)) of the continuous-time heat-diffusion Markov chain on an undirected graph, i.e., the process with generator -L where L is the combinatorial Laplacian. The main theoretical claim is Theorem 3.4: for any initial distribution and any t1 <= t2, H(Z(t2)|Z(0)) >= H(Z(t1)|Z(0)). The proof uses the data-processing inequality for KL divergence row-wise and the fact that the uniform distribution is stationary. The paper also derives exact spectral formulas for complete graphs (Cor. 3.8), path graphs (Prop. 3.9), and circulant graphs (Props. 3.10--3.11); asymptotic limits (Props. 3.14--3.15); mixing-time estimates (Prop. 3.16); spectral interlacing bounds (Prop. 3.17, 3.19); a Pinsker-type inequality (Prop. 3.20); and a mean-field approximation for Erdős-Rényi graphs (Sect. 3.6). Simulations on Watts-Strogatz and ER graphs illustrate the behavior and compare against circulant references.","tokens_in":20434,"tokens_out":5443,"duration_ms":45041,"significance":"The monotonicity result, Theorem 3.4, is a clean and nontrivial information-theoretic statement: it extends the usual second-law analogy for Markov chains from stationary initial conditions to arbitrary initial conditions in the special case of heat diffusion on graphs. The proof is parameter-free and does not rely on any fitted constants. The exact formulas for complete, path, and circulant graphs are useful for fast computation, and the mean-field approximation for ER graphs is a reasonable engineering tool. If the pointwise bounding claims were properly justified or clearly labeled as conjectural, the paper would be a solid contribution to entropy-based network analysis. The paper is honest in labeling the bounds as heuristic in the introduction, but the figure caption and some abstract-level claims overstate them.","major_comments":[{"comment":"The pointwise bounding claim—that the conditional entropy curve of every graph lies between the path-graph curve from below and the complete-graph curve from above—is asserted in Fig. 2's caption ('The entropy curves are bounded from below by the path graph curve and above by the complete graph curve') and used to interpret the simulations. However, the paper only proves eigenvalue interlacing (Prop. 3.17) and minimal algebraic connectivity of the path (Prop. 3.19). These spectral inequalities do not imply a pointwise ordering of H(t), because H(t) is a nonlinear function of the full spectrum and the eigenvectors; a graph with a slightly larger spectral gap but different prefactors could in principle cross the path or complete curve at finite times. The introduction itself concedes these are 'heuristically established' bounds. Please either prove the pointwise ordering under stated condi","section":"§3.4 and Fig. 2"},{"comment":"In the mixing-time discussion, Eq. (3.52) writes 'lim_{t→∞} π^T - p(t)^T ≈ e^{-λ2 t} ...', and Prop. 3.16's proof uses an equality 'lim ||π - p(t)||_p = lim || e^{-λ2 t} ... ||_p'. Strictly, the omitted faster-decaying terms cannot be dropped inside the limit before taking the norm. The final conclusion that both limits are 0 is correct, but the presentation confuses an asymptotic equivalence with an equality. Please rewrite Eq. (3.52) and the proof of Prop. 3.16 using standard asymptotic notation (e.g., 'as t → ∞, π^T - p(t)^T = e^{-λ2 t} p(0)^T v^{(2)} v^{(2)T} + O(e^{-λ3 t})').","section":"§3.3, Eq. (3.52)"},{"comment":"In the computation for the complete graph, the second line contains a typo: the coefficient of the e^{-Nt} term in the second entropy contribution is written as (1/N + (N-1)/N)e^{-Nt}, whereas the correct expression is (1/N + (N-1)/N e^{-Nt}). This is presumably a typesetting slip, since the final formula (3.23) is correct, but the intermediate line is confusing and should be fixed.","section":"Appendix A, derivation of Cor. 3.8"}],"minor_comments":[{"comment":"The statement assumes a connected non-bipartite graph, but for heat diffusion with generator -L the transition semigroup e^{-Lt} is continuous-time and converges to the uniform distribution for every connected graph, including bipartite ones. The non-bipartite assumption is unnecessary in this context and may mislead readers.","section":"Prop. 3.14"},{"comment":"The proof writes 't1 > 0' when applying the data-processing inequality. The statement covers t1 = 0 as well; this case is trivial because H(Z(0)|Z(0)) = 0. Please mention this explicitly.","section":"Proof of Theorem 3.4"},{"comment":"The inequality is stated for every p ≥ 1, but the proof uses Pinsker's inequality in l1 and then the monotonicity of l_p norms. This is correct, but the phrase 'for every p ≥ 1' should appear in the proof to avoid the impression that Pinsker itself holds for arbitrary l_p norms.","section":"Prop. 3.20"},{"comment":"The text refers to 'Section 3.5 (A)' and 'Section 3.5 (B)' when meaning the panels of Fig. 3. Please use 'Fig. 3(A)' and 'Fig. 3(B)' for clarity.","section":"Fig. 3 and Sect. 3.5"}],"recommendation":"major_revision","confidential_remarks":"The main theorem and spectral derivations are sound and the paper makes a worthwhile contribution. The load-bearing issue is the pointwise bounding claim: it is presented as a result in the figure caption and abstract-level statements, while the formal support only covers asymptotic spectral facts. This is fixable by recalibrating the claims and labeling the bounds as conjectural/heuristic. The central monotonicity theorem should survive unchanged. I would be willing to see a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Christophe — quick take on 2510.19441. The central monotonicity claim, Theorem 3.4, is correct, but it is a direct consequence of the data-processing inequality for KL divergence applied row-wise; the proof is fine. What is actually new: the explicit conditional entropy formulas for complete, path, and circulant graphs, and the mean-field expression for Erdős–Rényi graphs. Those are worked out carefully and are correct (modulo a typo in Appendix A and a loose equality in Prop. 3.16). The authors also honestly label the mean-field as approximate and show that it overestimates the entropy. So there is real, if modest, content here.\n\nThe soft spots, in order. First, the paper claims upper and lower bounds on entropy curves using the complete and path graphs as the extremes, and the Fig. 2 caption asserts these bounds as fact. But the paper only proves eigenvalue interlacing and asymptotic limits — nothing that implies a pointwise ordering of H(t) at finite times. The introduction hedges with 'heuristically established,' so the authors seem aware, but the abstract and figure captions overstate it. This should be fixed, either by proving the bound (which may be true) or by softening the claim to an empirical observation. Second, the thermodynamic framing — 'first and second laws' — is more rhetorical than substantive. Conservation of probability is not a first law, and the second law here is just DPI. That is fine as an analogy, but it is presented as a result. Third, a few technical glitches: the Appendix A derivation has a coefficient typo (the final formula is correct, so it is cosmetic), and Proposition 3.16's proof writes a limit of a decaying term as if it were equality. None of these is load-bearing.\n\nThe paper is worth engaging with: the formulas are useful references, the mean-field approximation is a nice practical tool, and the numerical comparisons are sensible. Who is this for? Network scientists who want a quick way to compute entropy curves on structured graphs, and people working on physics-inspired network dynamics. It is not a breakthrough, but it is a solid, mostly correct contribution. I would send it to peer review. A good referee will push for the bounds to be either proved or demoted, and for the thermodynamic language to be toned down. I would also like to see the pointwise bounds tested numerically over many graphs — the authors have the code, so that is easy.","headline":"Theorem 3.4 is correct but is really just the data-processing inequality in disguise; the new material is the explicit finite-time formulas and the mean-field approximation, while the claimed path/complete bounds are unproven and the thermodynamic rhetoric overreaches.","tokens_in":20867,"tokens_out":3871,"would_cite":true,"duration_ms":30553,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C82","60J27","94A17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Heat diffusion on any connected graph makes conditional entropy grow monotonically over time.","keywords":["conditional entropy","heat diffusion","graph Laplacian","continuous-time Markov chain","second law of thermodynamics","mixing time","random graphs","spectral graph theory"],"falsifier":"Numerically compute the conditional entropy curve for a small connected graph, e.g., a path or a random 3-regular graph, starting from a single node and using a fine time grid; any time interval where the curve dips would disprove Theorem 3.4. The theorem predicts monotonic increase, so a single observed decrease is a concrete counterexample.","tokens_in":19963,"feed_emoji":"📈","tokens_out":4007,"duration_ms":49081,"temperature":0.7,"pith_summary":"This paper introduces conditional entropy as a measure of heat diffusion on graphs and proves that, for any connected undirected graph and any starting distribution, this quantity never decreases over time. That monotonicity mirrors the second law of thermodynamics, giving a physical intuition for how information spreads on networks. The authors derive exact entropy formulas for complete, path, and circulant graphs, an asymptotic limit of log(N) for all connected non-bipartite graphs, and a mean-field approximation for Erdős–Rényi graphs. The work offers a new lens for comparing graph structures: the entropy curve rises faster for denser or shorter-diameter graphs, and the complete and path graphs serve as practical (though not fully proven) upper and lower reference curves.","feed_headline":"Graph heat diffusion satisfies an information-theoretic second law","feed_subtitle":"Monotone entropy curves give network scientists a thermodynamic lens for comparing diffusion on any graph.","key_machinery":"The central object is the conditional entropy H(Z(t)|Z(0)) of the heat-diffusion continuous-time Markov chain, defined as the average over initial nodes of the Shannon entropy of each row of the transition matrix e^{-Lt}, where L is the combinatorial graph Laplacian. The key identity connecting entropy to the second law is H_i(t|0) = log(N) - D_KL(T_{i,:}(0,t) || π), with π the uniform stationary distribution; the data-processing inequality for KL divergence then forces each row entropy to increase. Exact formulas rely on the spectral decomposition of L: the graph Fourier transform for circulant graphs, the discrete cosine transform for path graphs, and a simple projection for complete graph","core_discovery":"The central claim is Theorem 3.4: for the heat-diffusion Markov chain on a connected graph, conditional entropy H(Z(t2)|Z(0)) is always at least H(Z(t1)|Z(0)) whenever t1 ≤ t2, regardless of the initial distribution. The proof shows row by row that the KL divergence from each row of the transition matrix to the uniform stationary distribution decreases over time, and because heat diffusion has a uniform stationary distribution, each row's entropy equals log(N) minus that KL divergence. This yields a clean information-theoretic 'second law' and justifies using conditional entropy curves as a fingerprint of network structure, with complete graphs diffusing fastest and path graphs slowest.","pith_inferences":["Editorial inference: the row-wise KL-divergence proof suggests the monotonicity is tied to the symmetry of the Laplacian (uniform stationary distribution); a directed or non-reversible diffusion would likely violate the second law, as the paper's own counterexample for general chains indicates.","Editorial inference: if the heuristic path–complete bounding is ever proven, it would imply that entropy curves are ordered by graph connectivity in a majorization sense, potentially linking conditional entropy to graph spectra beyond the asymptotic regime.","Editorial inference: the mean-field approximation for ER graphs could be extended to other random graph ensembles with known degree distributions, such as configuration models, by replacing the uniform mean-field Laplacian with a degree-corrected version.","Editorial inference: the monotonicity theorem may hold for any reversible Markov chain whose stationary distribution is uniform, which includes random walks on regular graphs; testing this on non-regular reversible chains could delineate the exact scope of the thermodynamic analogy."],"forward_implications":["Conditional entropy curves can be used to compare the mixing speed of different graphs of the same size, with denser and smaller-diameter graphs reaching the asymptotic log(N) limit faster.","The mean-field approximation for Erdős–Rényi graphs gives a closed-form entropy curve that becomes more accurate for larger and denser graphs, enabling fast estimates without simulation.","For disconnected graphs, the asymptotic conditional entropy is a weighted sum of log(component sizes), extending the formalism beyond the connected case.","The monotonicity result suggests that conditional entropy could serve as a robust statistical observable for detecting structural changes in temporal or multilayer networks.","Because the monotonicity holds for any initial condition, entropy-based methods need not assume stationarity of the starting distribution."],"fun_headline_variants":["Entropy rises for graph heat diffusion","Monotone entropy: a second law for networks","Conditional entropy fingerprints graph structure","Heat on graphs: entropy only goes up","Entropy arrow for diffusion on connected graphs"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof that conditional entropy never decreases relies on heat diffusion having a uniform stationary distribution on the graph, so that each row's entropy is exactly log(N) minus its KL divergence to uniformity; if the diffusion were not symmetric in this way, the monotonicity can fail.","fun_headline_variants_meta":{"raw":{"variants":["Entropy rises for graph heat diffusion","Monotone entropy: a second law for networks","Conditional entropy fingerprints graph structure","Heat on graphs: entropy only goes up","Entropy arrow for diffusion on connected graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000172,"raw_usage":{"total_tokens":1095,"prompt_tokens":714,"completion_tokens":381,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":458,"completion_tokens_details":{"reasoning_tokens":316}},"tokens_in":458,"tokens_out":381,"duration_ms":3949,"temperature":1.0,"reasoning_tokens":316,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T08:40:28.080323+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Numerically compute the conditional entropy curve for a small connected graph, e.g., a path or a random 3-regular graph, starting from a single node and using a fine time grid; any time interval where the curve dips would disprove Theorem 3.4. The theorem predicts monotonic increase, so a single observed decrease is a concrete counterexample.","supporting_citations":[],"review_version":1}