{"id":"2ca11a76-f521-4d86-b152-bf2eb089fc3b","arxiv_id":"2507.19181","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Graph signals are compressed with a patchwise, embedded samplet transform that achieves much sparser representations than Haar wavelets for manifold-structured data.","lead":"This paper builds a new wavelet-like transform for signals on graphs by cutting the graph into patches, embedding each patch in a low-dimensional space, and applying samplets, a tool for scattered data. The result is a graph basis with higher-order vanishing moments that compresses smooth graph signals much better than tree-Haar wavelets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The vanishing-moment property at the heart of Prop. 4.1 is not established for the L-Isomap pipeline actually used in the numerics; Prop. 5.2 bounds moment matrices but not samplet coefficients.","rationale":"The reader's weakest assumption correctly identifies the mismatch between the exact-Isomap theory and the L-Isomap practice, and the loss of meaning of the polynomial class when the embedding is poor. My concern is more specific: even granting the exact-Isomap error bound, the paper does not prove that the samplets constructed from perturbed coordinates approximately vanish on true monomials. Proposition 5.2 only controls the difference of moment matrix entries; it does not control the samplet coefficients after the QR step. This is a logical gap in the argument connecting the numerical pipeline to the decay theorem, and it is load-bearing because Proposition 4.1 is the paper's main theoretical justification for the compression gains. The concern is not a disagreement with the numerical evidence; the tables may still be correct, but the theoretical explanation is incomplete. I recommend keeping the CONDITIONAL verdict, since the gap is fixable with a perturbation analysis or by restricting the claims to regimes where the embedding is proven faithful, but the current manuscript does not supply that link.","tokens_in":14095,"tokens_out":15304,"duration_ms":157970,"concrete_test":"On a synthetic flat manifold with known ground-truth chart (e.g., the unit square with N=10^4 points), compute the samplet transform of a fixed polynomial p of degree <= s using (i) the ground-truth coordinates and (ii) the L-Isomap coordinates with the same landmark count as in the paper. For both transforms, compute the maximum absolute samplet coefficient of p over all levels. In case (i) the coefficients should be at machine precision; in case (ii), if the concern lands, they will be much larger, quantifying the lost vanishing moments. Compare this residual against the compression threshold epsilon=10^-2 used in the experiments. If the residual is not below epsilon, the practical pipeline does not satisfy the hypothesis of Proposition 4.1 and the theoretical decay guarantee cannot be invoked for the numerical results.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires that the samplets implemented in Section 6 annihilate the true coordinate monomials X^alpha = x^alpha o phi_r, as assumed in Proposition 4.1. The construction in Section 3 only guarantees vanishing moments with respect to the embedded coordinates returned by landmark Isomap. For exact Isomap, Proposition 5.2 bounds the difference between the moment matrices built from Isomap coordinates and from the true chart by O((log N/N)^{1/q}), but a bound on moment matrices does not imply that the QR-based samplet filters inherit vanishing moments for the true monomials. The QR factorization is not stable at singular-value degeneracies, and no perturbation theorem for the samplet basis is provided. Hence the decay estimate (4) is not rigorously connected to the algorithm actually run. The gap is wider for L-Isomap: Remark 5.3 states that all experiments use L-Isomap, while Propositions 5.1 and 5.2 apply only to exact Isomap. The reported 'lost energy' values in Tables 3-5, e.g., 0.36 for p=50, q=2, indicate substantial embedding distortion, so the theoretical guarantee likely does not hold in the benchmark settings. Additionally, the stated bound in Proposition 4.1 uses max_{vj in U} over the whole patch rather than over the cluster tau; as written it decays only as sqrt(|tau|) and loses the gamma-dependent rate, which is too weak for the claimed rapid decay unless this is a typo.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a multiresolution analysis framework for graph signals. The graph is partitioned into patches, each patch is embedded into a Euclidean space via Isomap or landmark Isomap, samplets are constructed in the coordinate domains using a moment-matrix QR construction, and the resulting bases are pulled back to the graph. The central theoretical claim is Proposition 4.1, which asserts that signals in a microlocal class C^gamma_G have samplet coefficients decaying with the cluster size, so that truncation of the expansion yields sparse approximations. The authors also present adaptive-tree and best-k-term compression strategies and report numerical experiments on a million-point embedded unit square, a Swiss roll, and the Stanford bunny, where they observe large compression gains over Haar wavelets.","tokens_in":14451,"tokens_out":8143,"duration_ms":85258,"significance":"If the theoretical decay estimate were rigorously connected to the implemented pipeline, this would be a valuable contribution: the construction of orthogonal, localized, higher-order vanishing-moment bases on graphs with an underlying manifold structure is clean, the assumptions are stated explicitly, and the numerical experiments are large-scale and consistent with the intended effect. The paper gives a self-contained derivation of vanishing moments from the moment-matrix QR step, and the comparison with Haar wavelets is clearly reported. However, there is a substantial gap between the theory, which works with exact chart coordinates, and the numerics, which use landmark Isomap, and Proposition 4.1 as stated is too weak to support the claimed rapid decay. These issues affect the central claim and need to be addressed before the paper can be recommended for publication.","major_comments":[{"comment":"The bound uses max_{v_j in U} d(v_j,v0)^gamma over the whole patch U rather than over the cluster tau that supports the samplet. As written, the factor max_U^gamma is independent of the level j, so the bound decays only as sqrt(|tau|) and does not establish the gamma-dependent rapid decay claimed in the abstract and in Section 7. Please correct the statement to use a maximum over tau, or introduce a localized version of Definition 2.1 that yields a scale-dependent error.","section":"Section 4.1, Eq. (4)"},{"comment":"Proposition 4.1 assumes that samplets annihilate the true coordinate monomials X^alpha = x^alpha o phi_r. In the implemented pipeline the moment matrix (3) is built from Isomap or landmark Isomap coordinates, and Proposition 5.2 only bounds the difference between the true and estimated moment matrices. A bound on moment matrices does not by itself control the inner products <psi_{j,k}, X^alpha> because the samplet filters are obtained through a QR factorization, and no perturbation or stability theorem for the samplet coefficients is provided. The paper should supply a perturbation estimate for the samplet filters, or the decay theorem cannot be applied to the algorithm whose results are reported in Section 6.","section":"Sections 3 and 5.3"},{"comment":"All numerical experiments use landmark Isomap, while Propositions 5.1 and 5.2 concern exact Isomap; this is an explicit gap. The authors should either extend the consistency analysis to landmark Isomap, provide a controlled comparison with exact Isomap, or state clearly that the numerical results are not covered by the theorem. The high lost-energy values in Table 3 (e.g., 0.36 at p=50, q=2) indicate substantial embedding distortion, so this is not a purely formal concern.","section":"Remark 5.3 and Section 6"},{"comment":"The minimization in Proposition 5.1 is over O(d), but the embedded points y_i and the exact coordinates z_i lie in R^q; the orthogonal group should be O(q). Please also verify that the exponent 1/q is the one supplied by the cited Corollary 4 of [2], since the dimensions of the domain and codomain affect the rate.","section":"Section 5.2, Proposition 5.1"}],"minor_comments":[{"comment":"The name \"Cauchy-Schwartz\" should be \"Cauchy-Schwarz\".","section":"Section 4.1"},{"comment":"The condition sum_{|beta|=floor(gamma)}|c_beta| != 0 is not used in Proposition 4.1 and is confusing when gamma < 1; please clarify its role or remove it.","section":"Definition 2.1"},{"comment":"The sentence explaining the QR step, \"Since R^T is a lower triangular matrix...\", is ambiguous about the dimensions of Q_Phi, Q_Psi, and R; a short description of the block structure would help the reader verify the vanishing-moments claim.","section":"Section 3"},{"comment":"For p=100, q=3, the reported lost energy is 6.78e-1, which is an order of magnitude larger than the neighboring entries and contradicts the text's statement that lost energy decreases from p=50 to p=100; please check this entry.","section":"Table 4"},{"comment":"The lost-energy metric is defined via the trace of the Gram matrix of landmark points, but the relation of this quantity to the embedding error in Proposition 5.1 is not explained; please state why this is a meaningful proxy for coordinate accuracy.","section":"Section 6"},{"comment":"The notation f o phi^{-1} is used although f is defined on vertices; consider writing the inner product directly as <psi_{j,k}, f> or clarifying the pullback notation.","section":"Proposition 4.1"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the manuscript fits the journal's scope and the core construction is sound, but the main theorem is currently not connected to the numerical pipeline. A major revision focused on the perturbation analysis for the samplet filters and on the statement of Proposition 4.1 is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know this paper before you read the abstract: it extends Euclidean samplets to graphs by cutting the graph into patches, embedding each patch with Isomap, building samplets in the coordinate domain, and pulling back. That's a sensible and novel idea, and the paper does the basic construction carefully: orthogonality, locality, and vanishing moments with respect to the embedded coordinates follow from the QR construction, and the graph microlocal spaces are a reasonable discrete analogue of Jaffard's classes.\n\nThe core advertised payoff is Proposition 4.1: that functions in these classes have rapidly decaying samplet coefficients. As written, the bound is |<ψ,f∘φ^{-1}>| ≤ C max_{v∈U} d(v,v0)^γ sqrt(|τ|). That max runs over the whole patch, so for finer clusters it does not shrink. You only get the sqrt(|τ|) factor, same as Haar. If that max was intended to run over the cluster τ, the proof would give the expected rate; but as written, the theorem does not establish the claimed improvement. This looks like a typo, but it is a load-bearing one, and it needs to be fixed before the compression story is credible.\n\nThere is a second gap, at least as serious. The practical pipeline uses landmark Isomap, while Propositions 5.1 and 5.2 only cover exact Isomap. Prop 5.2 bounds the difference between moment matrices, not the difference between the samplet basis vectors. A close moment matrix does not guarantee the QR-based annihilation of the true monomials. So even the weaker version of the theory (with exact Isomap) is not fully connected to the algorithm that produced the tables. The lost-energy numbers for the bunny (0.36 for p=50) suggest the embedding distortion is substantial, so this gap is not cosmetic.\n\nWhat is solid: the construction itself, the numerical evidence that higher vanishing moments reduce nonzero coefficients by orders of magnitude relative to Haar on these examples, and the honest remark that L-Isomap is used. But there is no code, no error bars, no comparison with other graph wavelet bases, and the benchmark is only against Haar. So the practical claim is plausible but not yet convincing.\n\nThis paper deserves a serious referee. The idea is new, the construction is nontrivial, and the gaps are fixable. I would send it to review, but with a clear request to repair the decay bound, extend the perturbation analysis to L-Isomap (or at least to samplet filters), and ideally release code.","headline":"A genuinely new construction of graph samplets with a clean idea, but the main decay bound is currently too weak to support the compression claims, and the experiments run on a pipeline the theory does not cover.","tokens_in":14962,"tokens_out":3111,"would_cite":false,"duration_ms":31805,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["42C40","65T60","94A12"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper transplants the Euclidean samplet transform to graphs by embedding each patch in Euclidean space, and proves that locally polynomial graph signals compress far more sparsely than with Haar wavelets.","keywords":["graph signal processing","multiresolution analysis","samplet transform","graph wavelets","vanishing moments","Isomap embedding","signal compression","manifold learning"],"falsifier":"On a 'Y'-shaped graph patch where three branches meet, construct samplets with the paper's pipeline and check whether a smooth signal's coefficients decay according to Proposition 4.1; if they do not, or if the representation is no sparser than Haar wavelets, the single-chart manifold premise has been violated.","tokens_in":13930,"feed_emoji":"📉","tokens_out":7022,"duration_ms":67758,"temperature":0.7,"pith_summary":"This paper tries to establish that the samplet transform, a discrete wavelet-like construction originally designed for scattered Euclidean data, can be carried over to graph signals. The strategy is to split the graph into patches, embed each patch into a low-dimensional Euclidean space, build samplets there, and pull them back to the graph. The resulting orthogonal, local basis has vanishing moments with respect to polynomials defined through the patch coordinates. The paper proves that graph signals which locally resemble polynomials, collected in the classes $C^\\gamma_G(C,v_0)$, have samplet coefficients decaying like $O(d(v,v_0)^\\gamma\\sqrt{|\\tau|})$, so they admit very sparse representations. If true, this gives graph signal processing a multiresolution tool that is much more powerful than Haar wavelets, which only have one vanishing moment.","feed_headline":"A new graph wavelet compresses signals up to 240x better than Haar","feed_subtitle":"Patchwise samplets give graph wavelets real vanishing moments, producing sparse 1% error representations.","key_machinery":"The load-bearing object is the samplet, a localized orthogonal discrete signed measure that annihilates all polynomials up to a fixed degree. The construction proceeds patch by patch: after embedding a patch into $\\mathbb{R}^q$, the algorithm builds a cluster tree by recursively splitting bounding boxes, forms the moment matrix $M^\\tau_j=[\\phi(v_i)^\\alpha]_{\\alpha,i}$, and QR-factorizes its transpose. The first $m_s=\\binom{s+q}{q}$ columns become scaling distributions and the remaining columns become samplets with $s+1$ vanishing moments. Pulling the basis back through the chart $\\phi^{-1}$ and assembling all patches block-diagonally yields an orthogonal transform that, for balanced trees, costs $O(N)$ and turns local polynomial smoothness into rapid coefficient decay.","core_discovery":"The central claim is that a patchwise samplet basis on a graph can annihilate pulled-back polynomials up to any chosen degree $s$, and that this vanishing-moment property is exactly what makes smooth graph signals compressible. For a signal $f$ in the graph microlocal class $C^\\gamma_G(C,v_0)$, Proposition 4.1 bounds any samplet coefficient at a cluster $\\tau$ containing $v_0$ by $C\\max_{v_j\\in U} d(v_j,v_0)^\\gamma\\sqrt{|\\tau|}$. Since the cluster size shrinks geometrically, coefficients decay quickly away from any singular point. The numerical experiments on an embedded unit square, a Swiss roll, and the Stanford bunny show that reconstructing such signals with $1\\%$ relative error needs orders of magnitude fewer nonzero coefficients than the Haar-wavelet baseline.","pith_inferences":["An implicit extension is that the patch chart need not come from Isomap: any embedding that approximately preserves local geometry could feed the same construction, and the decay estimate then becomes a measurable test of embedding quality.","Because the error analysis covers exact Isomap while the experiments use landmark Isomap, a natural testable extension is to compare empirical coefficient decay with the proposition's bound on patches where exact and landmark embeddings diverge.","On graphs that violate the single-chart manifold assumption, such as branched or self-intersecting patches, the samplet basis loses exact polynomial vanishing moments; whether useful compression survives is a question the paper leaves open."],"forward_implications":["Signals in the graph microlocal classes $C^\\gamma_G(C,v_0)$ have provably sparse samplet expansions with controlled error in the Euclidean norm.","Graph data sampled from a low-dimensional manifold can be compressed without suffering the curse of ambient dimensionality, because the polynomial spaces live in the intrinsic coordinate dimension $q$.","Both adaptive tree coarsening and best-$k$ thresholding on samplet coefficients yield reconstructions with a guaranteed relative error $\\varepsilon$ using far fewer coefficients than Haar wavelets.","The construction opens the way for graph versions of other samplet applications, such as compressed sensing and kernel learning, by providing a sparsifying basis for graph-structured signals."],"supporting_citations":[{"why":"Supplies the Euclidean samplet construction that this paper extends to graph patches.","marker":"[22]"},{"why":"Provides the Isomap embedding used to map each graph patch into low-dimensional coordinates.","marker":"[38]"},{"why":"Supplies the perturbation bound for Procrustes and classical scaling used to control the embedding error in Proposition 5.1.","marker":"[2]"},{"why":"Introduces landmark Isomap, the variant used in the numerical experiments instead of exact Isomap.","marker":"[15]"},{"why":"Supplies the MaxMin greedy landmark selection used by the landmark Isomap implementation.","marker":"[16]"},{"why":"Provides the adaptive tree coarsening algorithm that turns samplet coefficients into sparse subtrees for compression.","marker":"[9]"},{"why":"Supplies the Haar-wavelets-on-trees baseline and the (C,gamma)-Hölder classes that Definition 2.1 generalizes.","marker":"[19]"},{"why":"Defines the microlocal smoothness spaces whose graph analog appears as the classes $C^\\gamma_G$.","marker":"[27]"}],"fun_headline_variants":["Patchwise samplets beat Haar wavelets on graph compression","New graph wavelets use vanishing moments for sparse signal compression","Samplet transform on graphs yields far sparser approximations than Haar","Graph wavelets with vanishing moments compress smooth signals far better"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction assumes every graph patch is a faithful discretization of one smooth manifold patch with a single coordinate chart, and that the embedding recovers those coordinates closely enough that the pulled-back polynomial space retains its vanishing-moment meaning; if either fails, the decay estimate and the compression gains collapse.","fun_headline_variants_meta":{"raw":{"variants":["Patchwise samplets beat Haar wavelets on graph compression","New graph wavelets use vanishing moments for sparse signal compression","Samplet transform on graphs yields far sparser approximations than Haar","Graph wavelets with vanishing moments compress smooth signals far better"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000729,"raw_usage":{"total_tokens":3269,"prompt_tokens":952,"completion_tokens":2317,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":2249}},"tokens_in":568,"tokens_out":2317,"duration_ms":15606,"temperature":1.0,"reasoning_tokens":2249,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:59:11.528912+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a 'Y'-shaped graph patch where three branches meet, construct samplets with the paper's pipeline and check whether a smooth signal's coefficients decay according to Proposition 4.1; if they do not, or if the representation is no sparser than Haar wavelets, the single-chart manifold premise has been violated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Isomap embedding used to map each graph patch into low-dimensional coordinates."},{"cited_title":"Arias-Castro, A","cited_arxiv_id":null,"evidence_quote":"Supplies the perturbation bound for Procrustes and classical scaling used to control the embedding error in Proposition 5.1."},{"cited_title":"De Silva and J","cited_arxiv_id":null,"evidence_quote":"Introduces landmark Isomap, the variant used in the numerical experiments instead of exact Isomap."},{"cited_title":"De Silva and J","cited_arxiv_id":null,"evidence_quote":"Supplies the MaxMin greedy landmark selection used by the landmark Isomap implementation."},{"cited_title":"Binev and R","cited_arxiv_id":null,"evidence_quote":"Provides the adaptive tree coarsening algorithm that turns samplet coefficients into sparse subtrees for compression."},{"cited_title":"Gavish, B","cited_arxiv_id":null,"evidence_quote":"Supplies the Haar-wavelets-on-trees baseline and the (C,gamma)-Hölder classes that Definition 2.1 generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the microlocal smoothness spaces whose graph analog appears as the classes $C^\\gamma_G$."}],"review_version":2}