{"id":"ec9bcba3-bc77-410f-961e-aaad0c2543ba","arxiv_id":"2502.00038","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The barycentre graph of a graph dataset is reconstructed by pairing the mean Laplacian spectrum with Soules-basis eigenvectors aligned to communities, and for balanced stochastic block models this reconstruction is claimed to converge to the population mean.","lead":"To summarize a dataset of graphs, this paper computes the average spectrum of their normalized Laplacians and attaches eigenvectors from a special family of bases, chosen so the resulting summary graph keeps the community structure. The method recovers known classes in a primary-school contact network, and the mathematics is proven for idealized stochastic block models.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The a.a.s. convergence to the population mean is only proved when Algorithm 1 is given P, not the observed sample mean; no theorem shows the greedy Soules splits are stable to sample noise.","rationale":"The paper is transparent about its main limitation in Section 4.3, and the real-data recovery of classes is a genuinely useful empirical signal. But the headline claim is precisely the a.a.s. convergence of the barycentre to the population mean for SBM, and that requires showing the greedy Soules splits recover the true blocks when the input is the noisy sample mean bE_T[P], not merely when the input is the population matrix P. The reader's weakest_assumption identifies this same gap, and I agree with it. The proof of Lemma 5 depends on P being exactly piecewise constant; no argument transfers that conclusion to P plus noise. The secondary issue with Lemma 2's O(1) bound reinforces the concern: as written it does not establish convergence, and even the corrected vanishing norm bound from the proof does not give the exact equality stated in Eq. 13. The proposed Monte Carlo check directly tests the missing link by measuring split-recovery frequency as n grows. If that frequency tends to 1, the gap may be patchable with standard concentration arguments; if not, the advertised guarantee requires a different algorithm or an explicit T -> infinity assumption. Since the reader already assigned CONDITIONAL and my analysis does not move that assessment, the appropriate verdict adjustment is UNCHANGED.","tokens_in":25744,"tokens_out":8536,"duration_ms":86964,"concrete_test":"Run the released code (or a minimal reimplementation of Algorithm 1 with the same spectral-clustering preprocessing) on balanced SBM with p and q as in Section 6.1.2, for n = 128, 256, 512, 1024 and T = 1 and T = 10, over at least 100 independent trials per configuration. For each trial, record whether the first M splits returned by Algorithm 1 exactly coincide with the true block boundaries, and compute the normalized Frobenius error ||bmu_T^M - P||_F / n. If the fraction of exactly correct split vectors does not tend to 1 as n grows, or if the error does not vanish on trials with incorrect splits, the claimed a.a.s. convergence fails. An analytical companion would be to re-derive Lemma 9 with input P + E, where E = bE_T[P] - P, and identify a noise level under which the argmax alignment is preserved; if no such bound can hold for fixed T, the theorem needs a T -> infinity assumption.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The advertised guarantee (abstract and Eq. 13) is that for balanced SBM the algorithm returns a barycentre that converges asymptotically almost surely to the population mean P. The only results connecting Algorithm 1 to the true block geometry are Lemma 5 and Lemma 9, and both are proved for the population mean matrix P as input. Section 4.3 explicitly assumes this and defers finite-sample analysis. Consequently, the proof does not cover the actual algorithm, whose input is the noisy sample mean bE_T[P]. The greedy split selection is an argmax over |<psi psi^T, bE_T[P]>|^2; Lemma 7's alignment argument relies on P being exactly piecewise constant. Under noise, a slightly larger fluctuation inside a block can move the zero-crossing off the true boundary, especially when p-q is near the detection threshold, and no result controls this probability. The only numerical evidence reported for this point (Fig. 8-left) is a mean-squared error curve, not a split-recovery frequency. Separately, Lemma 2 states an O(1) Frobenius bound, which as written does not imply convergence; the proof's displayed computation would give a vanishing O(sqrt(log n / n)) bound if corrected, but even that is a norm bound, not the exact equality demanded by Eq. 13. The central claim is therefore unsupported at the exact point where the random data enter the algorithm.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines a barycentre graph for graph-valued data using a spectral pseudo-distance based on ordered normalized Laplacian eigenvalues, and addresses the missing-eigenvector problem by constraining the barycentre eigenvectors to lie in a Soules basis. For balanced stochastic block models, it claims in the abstract and in Section 1.6 that the proposed Algorithm 1 returns a barycentre converging asymptotically almost surely to the population mean. The theoretical sections prove block recovery for a greedy Soules split algorithm when the input is the population mean matrix P, and the experimental sections report Monte Carlo and real-data results.","tokens_in":26060,"tokens_out":12486,"duration_ms":115025,"significance":"If the main claim were fully established, this would be a useful contribution: the Soules-basis formulation is elegant, the inverse-eigenvalue framing is principled, and the public code and real-data demonstrations are valuable. The paper also makes a concrete, falsifiable prediction about the behaviour of a spectral barycentre under a balanced SBM. However, the advertised guarantee is currently proved only for an idealized oracle input, not for the sample mean matrix that Algorithm 1 actually receives, and the exact equality statement in Eq. (13) is not supported by the norm bounds that are proved. The contribution at this stage is therefore a promising heuristic algorithm with a partial theoretical analysis rather than a proven estimator.","major_comments":[{"comment":"The central convergence claim in the abstract and in Section 1.6 concerns Algorithm 1 run on T random realizations, but the only recovery results, Lemma 5 and Lemma 9, assume that Algorithm 1 is given the population mean matrix P, not the sample mean ĥ𝔼_T[ℙ]. Section 4.3 states this explicitly and defers finite-sample analysis to future work. Consequently, no argument controls the event that the greedy argmax splits in Algorithm 1 remain aligned with the true block boundaries under sample noise; the numerical evidence in Fig. 8-left is a mean-squared-error curve, not a split-recovery frequency. This is load-bearing because the random data enter the algorithm exactly at this split-selection step, and the spectral-clustering pre-processing of Section 4.2 is acknowledged to be imperfect.","section":"§4.3, Lemmas 5 and 9"},{"comment":"Lemma 2 states a Frobenius bound ||ĥL^M - L||_F = O(1) with probability converging to 1, and then concludes that Eq. (13) holds. An O(1) bound does not imply convergence, and even if the proof is corrected to the vanishing O(sqrt(log n / n)) rate that appears in Eq. (26), a high-probability norm bound does not imply the exact equality event in Eq. (13). The abstract's 'almost surely' is also stronger than the 'probability converging to 1' statements used in the proofs of Lemma 2 and Lemma 1.","section":"§2, Lemma 2 and §1.6"},{"comment":"Lemma 5 states that the first M Soules vectors returned by Algorithm 1 satisfy ∑_{k=1}^M ψ_kψ_k^T(i,j) = 1/|J_m| inside the recovered blocks, whereas Eq. (19) in Lemma 2 requires the value M/n. These two expressions agree only in the balanced case with equal block sizes. Corollary 1 therefore overclaims that Lemma 5 solves Eq. (19) for general SBM; the lemma's extension to unbalanced SBM is not compatible with the sufficient condition used in the main convergence lemma.","section":"Corollary 1 vs. Lemma 5"},{"comment":"The proof of Lemma 2 equates ĥL^M - L with ε_n, but the deterministic diagonal term arising from the identity-minus-block-projection in Eq. (24) has diagonal entries 1 - [(1-c)M + c]/n rather than 1, so the displayed equality in Eq. (25) is not correct as written. This discrepancy is O(1/sqrt n) in Frobenius norm and may not change the asymptotic rate, but it means the algebra in the central lemma must be repaired before the convergence statement can be accepted.","section":"§2, Eqs. (22)–(26)"}],"minor_comments":[{"comment":"The text 'an French primary school' should read 'a French primary school'.","section":"§1.8.3"},{"comment":"Algorithm 1 contains a malformed expression `coeff)` on line 15 and does not reset the loop variable i* for each block; the pseudocode as printed would not execute cleanly. Separately, the complexity claim of O(Mn) assumes only M levels are processed, while the pseudocode loops over all n-1 levels; the stated linear-in-n complexity needs clarification or correction.","section":"Algorithm 1 and §4.2.1"},{"comment":"The proof of Lemma 7 assumes p0 + p1 - 2q > 0 when concluding that the maximum occurs at i* = j; the statement should include the SBM condition p_m > q, since the squared objective can behave differently when that coefficient is negative.","section":"Lemma 7"},{"comment":"The symbol M is overloaded: it denotes the number of communities, the superscript in ĥbµ^M_T(ℙ), and the upper limit in the partial sum of Soules eigenprojectors. The paper would be easier to read with a distinct notation for at least one of these uses.","section":"Throughout"},{"comment":"The paper says the code is publicly shared and gives a repository URL, which is good, but the main theoretical claims are stated in the abstract without the caveat, explicitly acknowledged in Section 4.3, that the analysis applies to the population input P rather than the sample mean input ĥ𝔼_T[ℙ].","section":"§1.9 and §7"}],"recommendation":"major_revision","confidential_remarks":"The manuscript has a genuinely appealing algorithmic idea and the experimental section suggests the method works in practice, but the gap between the advertised guarantee and the proven statements is substantial: the split-selection algorithm is analyzed only on the population matrix, and the norm bounds proved in Lemma 2 do not deliver the exact equality of Eq. (13). I would encourage a revision that either supplies a finite-sample stability analysis for the greedy splits or visibly weakens the abstract's claim to a heuristic guarantee plus a population-level consistency result. The inconsistencies in Corollary 1 and in the diagonal term of Lemma 2 should also be fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new piece is the use of Soules bases as a search space for the eigenvector matrix in the spectral Fréchet mean problem, plus the structural constraint in Eq. (13) that forces the barycentre to inherit block structure. The algorithm is clearly specified, the paper is self-contained, and the code is public. The real-data experiment on the primary-school contact graphs is suggestive: the barycentre recovers classes that the raw sample mean blurs. That is a real result, and it is the kind of thing people in graph-valued statistics will want to build on.\n\nThe soft spot is exactly where the reader put it. The advertised guarantee—almost-sure convergence of the algorithm's output to the population mean—is not proved. Section 4.3 states that the analysis assumes the algorithm is fed P, not the sample mean bE_T[P], and Lemmas 5 and 9 are indeed proved only for P. The greedy split is an argmax over noisy inner products; no theorem controls the probability that noise moves a zero-crossing off the true boundary. Lemma 2 is also mis-stated: it claims an O(1) Frobenius bound, which cannot imply convergence; the proof actually derives O(sqrt(log n/n)), so the statement needs correcting. These are genuine gaps, but they are not fatal to the paper's value. The author is transparent about the population-input assumption, and the numerical evidence suggests the splits are stable in practice.\n\nOne smaller complaint: the Monte Carlo curves in Fig. 8 lack error bars and are reported as point estimates, which is fine for a first pass but weak for a convergence claim. The dependence on the spectral-clustering pre-step is also unanalysed.\n\nBottom line: the paper deserves a serious referee. It proposes a new, well-motivated construction and ships code and experiments; the central claim is overbroad relative to the proof, but that is a fixable gap. If I were the editor, I would send it out and ask the author to either provide a finite-sample analysis or revise the abstract and theorem statements to match what is actually proved.","headline":"A clever Soules-basis algorithm for spectral barycentres whose advertised convergence guarantee is only proved for the population matrix, not the sample input—worth refereeing but needs a finite-sample gap fixed.","tokens_in":26562,"tokens_out":2203,"would_cite":false,"duration_ms":19040,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","60B20","62H30"],"pacs":[],"model":"deepseek-v4-flash","headline":"A barycentre graph can be rebuilt from eigenvalues alone by choosing a greedy Soules basis; for balanced stochastic block models it converges almost surely to the population mean as the graph grows.","keywords":["barycentre graph","Fréchet mean","Soules basis","normalized graph Laplacian","spectral pseudo-distance","stochastic block model","graph-valued data","community structure"],"falsifier":"Two concrete checks would settle the claim. First, in Monte Carlo experiments on balanced stochastic block models, record the fraction of trials in which the first $M$ splits selected by Algorithm 1 from the sample mean $\\widehat{\\mathbb{E}}_T[P]$ coincide with the true block boundaries as $n$ grows: the claimed convergence requires this fraction to tend to one, while the deferred finite-sample analysis predicts a misalignment rate that should decay with $n$ and $T$. Second, measure $\\|\\widehat{L}_M - \\mathcal{L}\\|_F$ numerically at increasing $n$: the proof derives a decay of order $\\sqrt{\\log n / n}$, whereas the lemma as stated only promises $O(1)$, so the measured exponent settles which statement is true, and splits that systematically land off the block boundaries near the community-detection threshold would falsify the central claim.","tokens_in":25530,"feed_emoji":"🕸️","tokens_out":15667,"duration_ms":125538,"temperature":0.7,"pith_summary":"The paper attacks a practical obstacle in machine learning on graph-valued data: the natural spectral distance between graphs determines only the eigenvalues of the average graph, never its eigenvectors, so the 'barycentre graph' that minimizes that distance is not uniquely determined. The proposal is to pin down the missing eigenvectors with a structural constraint: choose an orthonormal basis from the library of Soules bases, greedily splitting index intervals so that each new vector's zero-crossing falls on a community boundary of the sample. The central claim is that for graphs drawn from a balanced stochastic block model, this recipe produces a barycentre whose normalized Laplacian matches the population mean, and the barycentre itself converges to the population mean adjacency matrix as the graph size grows, with probability tending to one. If true, this gives a fast, principled way to summarize a dataset of networks, recovering class or community structure that a plain entrywise average of adjacency matrices washes out.","feed_headline":"Spectral recipe recovers the mean graph, block structure intact","feed_subtitle":"A greedy Soules-basis search turns sample spectra into a barycentre that provably converges to the population mean.","key_machinery":"The machinery is the Soules basis: an orthonormal basis of $\\mathbb{R}^n$ generated recursively by splitting an index interval into two sub-intervals and creating a vector that is piecewise constant and changes sign exactly at the split. Every Soules basis satisfies $\\sum_{k=1}^n \\psi_k\\psi_k^T = I$ and, for decreasing eigenvalue sequences, $\\Psi\\operatorname{diag}(\\lambda)\\Psi^T$ has the sign pattern of a graph Laplacian, which makes the family a ready-made solution set for the inverse eigenvalue problem. The load-bearing property is the alignment of zero-crossings with block boundaries: Lemma 7 computes $|\\langle \\psi\\psi^T, P\\rangle|^2$ for a two-block edge-probability matrix and shows it is maximized exactly when the split point equals the block boundary, and Lemma 9 proves by induction that $M$ greedy splits of the population mean $P = \\sum_m (p_m-q)\\mathbf{1}_{B_m}\\mathbf{1}_{B_m}^T + qJ$ recover all $M$ blocks. A second component is the regularized spectrum: the $M$ smallest sample-mean eigenvalues are kept, while the noisy bulk eigenvalues are replaced by the deterministic limits $l_m = Mq/(p+(M-1)q)$ for $2 \\le m \\le M$ and $l_m = 1$ for $m > M$, so the reconstruction is driven by community structure rather than sampling noise.","core_discovery":"On the paper's own terms, the discovery is that the inverse problem behind the spectral barycentre — given the sample-mean eigenvalues $\\widehat{\\mathbb{E}}_T[\\lambda]$, find an orthonormal $\\Psi$ satisfying $\\Psi \\operatorname{diag}(\\widehat{\\mathbb{E}}_T[\\lambda])\\Psi^T = \\mathcal{L}$, the normalized Laplacian of the population mean — is solvable by a customized Soules basis. Algorithm 1 builds $\\Psi$ level by level: starting from $\\psi_1 = n^{-1/2}\\mathbf{1}$, each new Soules vector is the split of an existing index interval that maximizes $|\\langle \\psi \\psi^T, \\widehat{\\mathbb{E}}_T[P]\\rangle|^2$. Lemma 5 shows that when the input is the population mean $P$ of a stochastic block model, the first $M$ such vectors recover exactly the $M$ blocks; Lemma 2 shows that with the $n-M$ bulk eigenvalues replaced by their deterministic limits, the reconstructed Laplacian converges to $\\mathcal{L}$ with probability tending to one. The paper concludes that the barycentre $\\widehat{\\mu}^M_T = \\widehat{D}^{1/2}(I - \\widehat{L}_M)\\widehat{D}^{1/2}$ converges to $\\mathbb{E}[\\mathbb{P}]$ asymptotically almost surely for balanced stochastic block models.","pith_inferences":["A natural extension the paper explicitly defers is the finite-sample analysis: the reconstruction error should split into a spectral term of order $\\sqrt{\\log n/n}$ and a term driven by misaligned spectral clustering, and the outlier at $n=374$ in the paper's own convergence measurement is where the second term should show up.","Because the distance uses normalized-Laplacian eigenvalues, which live on the fixed interval $[0,2]$, the same construction could average graphs of different sizes by interpolating their spectra, making the barycentre independent of node correspondence — the paper mentions this direction but does not develop it.","The greedy Soules splitter is in effect a hierarchical community-detection procedure that maximizes spectral energy at each cut; if the block-recovery lemma is as robust as claimed, the same algorithm could serve as a consistency-certified graphon or stochastic-block-model estimator rather than only a barycentre routine.","The paper's convergence statement is asymptotic in graph size with the sample size $T$ held fixed; a check it does not perform is whether the barycentre also converges as $T \\to \\infty$ at fixed $n$, which is the regime most practitioners would actually encounter."],"forward_implications":["For a sample of graphs drawn from a balanced stochastic block model, the algorithm's barycentre converges to the population mean adjacency matrix as the graph size grows, with probability tending to one.","The eigenvector search runs in time linear in the number of vertices — about $Mn$ operations — so the barycentre can be computed for large graphs.","The regularization step, replacing the noisy bulk eigenvalues with their deterministic limits, is what keeps sampling noise from contaminating the reconstruction, and the paper's convergence proof relies on it.","On the primary-school contact graphs, the barycentre recovers the ten classes even though the entrywise sample-mean adjacency matrix washes the class structure out.","The same inverse-eigenvalue construction opens a route to spectral graph synthesis with theoretical guarantees, which the paper identifies as a payoff of the approach."],"supporting_citations":[{"why":"Supplies Lemma 1, the almost-sure eigenvalue estimates for the normalized Laplacian of a balanced stochastic block model, from which the regularized spectrum of the barycentre is built.","marker":"[54]"},{"why":"The original construction of Soules bases, the family of orthonormal matrices that Algorithm 1 searches over.","marker":"[70]"},{"why":"Supplies the Soules-basis properties (orthonormality, nonnegative partial sums, Laplacian sign patterns) that make the reconstructed matrix a valid normalized Laplacian.","marker":"[29]"},{"why":"The spectral clustering results behind the node-reordering preprocessing that aligns sample graphs into blocks before the greedy search.","marker":"[66]"},{"why":"Provides the face-to-face contact dataset used to test the barycentre on real graphs with known class structure.","marker":"[71]"},{"why":"Used to justify that only the M smallest sample eigenvalues carry community information while the rest form a noisy bulk.","marker":"[5]"}],"fun_headline_variants":["Soules basis solves graph barycentre, provably converges","Barycentre for graphs: spectral method converges to mean","Spectral barycentre: Soules search recovers population mean","Mean graph via Soules basis, asymptotically convergent"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that the greedy splits recover the true community blocks is run on the exact population mean of the random model, not on the noisy sample mean, so the claimed convergence stands or falls on the deferred finite-sample analysis showing that sampling noise cannot shift the splits.","fun_headline_variants_meta":{"raw":{"variants":["Soules basis solves graph barycentre, provably converges","Barycentre for graphs: spectral method converges to mean","Spectral barycentre: Soules search recovers population mean","Mean graph via Soules basis, asymptotically convergent"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000882,"raw_usage":{"total_tokens":3873,"prompt_tokens":1071,"completion_tokens":2802,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":687,"completion_tokens_details":{"reasoning_tokens":2735}},"tokens_in":687,"tokens_out":2802,"duration_ms":17778,"temperature":1.0,"reasoning_tokens":2735,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T14:20:40.289168+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Two concrete checks would settle the claim. First, in Monte Carlo experiments on balanced stochastic block models, record the fraction of trials in which the first $M$ splits selected by Algorithm 1 from the sample mean $\\widehat{\\mathbb{E}}_T[P]$ coincide with the true block boundaries as $n$ grows: the claimed convergence requires this fraction to tend to one, while the deferred finite-sample analysis predicts a misalignment rate that should decay with $n$ and $T$. Second, measure $\\|\\widehat{L}_M - \\mathcal{L}\\|_F$ numerically at increasing $n$: the proof derives a decay of order $\\sqrt{\\log n / n}$, whereas the lemma as stated only promises $O(1)$, so the measured exponent settles which statement is true, and splits that systematically land off the block boundaries near the community-detection threshold would falsify the central claim.","supporting_citations":[{"cited_title":"W.: Constructing symmetric nonnegative matrices","cited_arxiv_id":null,"evidence_quote":"The original construction of Soules bases, the family of orthonormal matrices that Algorithm 1 searches over."},{"cited_title":"Linear Algebra and its Applications 271(1-3), 323–343 (1998)","cited_arxiv_id":null,"evidence_quote":"Supplies the Soules-basis properties (orthonormality, nonnegative partial sums, Laplacian sign patterns) that make the reconstructed matrix a valid normalized Laplacian."},{"cited_title":"The Annals of Statistics pp","cited_arxiv_id":null,"evidence_quote":"The spectral clustering results behind the node-reordering preprocessing that aligns sample graphs into blocks before the greedy search."},{"cited_title":"PloS one 6(8), e23176 (2011)","cited_arxiv_id":null,"evidence_quote":"Provides the face-to-face contact dataset used to test the barycentre on real graphs with known class structure."}],"review_version":1}