{"id":"0e1101e7-a993-49c9-a753-d9edf36eecad","arxiv_id":"2412.12900","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"Shift-invariant, bandlimited, and principal shift-invariant spaces of graph signals coincide on undirected finite graphs under a distinct-spectrum assumption, yielding an RKHS view and a finite Krylov sampling algorithm.","lead":"This paper proves that on undirected finite graphs, a signal space that is invariant under graph shifts is always a bandlimited space, and every bandlimited space is generated by one signal shifted repeatedly. It also introduces a finite-step spatial-domain reconstruction algorithm and tests it on synthetic and flight-delay data.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption II.1 is violated by the paper's own circulant-graph simulations, so the central equivalence does not cover the main numerical demonstration.","rationale":"The reader's conditional verdict is appropriate: the core theorems are internally consistent and proven under Assumption II.1, but that assumption sharply limits the scope. My stress test sharpens the reader's weakest-assumption point into a concrete internal mismatch: the paper's own circulant-graph simulations in Section VI-A use real symmetric circulant shifts, whose joint spectrum necessarily contains paired eigenvalues λλ(k)=λλ(N-k). Thus Assumption II.1 is not merely potentially violated; it is definitely violated in the numerical setup used to demonstrate the framework. This does not invalidate the conditional theorems, but it does undermine the unqualified framing and the direct transfer of the theory to the implemented experiments. A simple spectral count settles the point. Since the reader already judged the paper CONDITIONAL, and the concern reinforces that judgment rather than overturning it, the verdict remains unchanged.","tokens_in":19990,"tokens_out":10734,"duration_ms":108272,"concrete_test":"Compute, for the two shifts in Remark III.6 with N=100 and Q={1,3}, the set of joint eigenvalues {(λ_1(k), λ_2(k)) : k=0,...,99} and count its distinct elements. If the count is less than N (as expected, at most 51), then Assumption II.1 is violated in the Section VI-A experiments and the stated theorems do not justify the simulation; if instead the count were 100, the concern would be refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorems (III.1, III.2, IV.1) all rest on Assumption II.1: the N joint-spectrum vectors λλ(n) must be distinct. This assumption is not merely restrictive; it is false for the paper's own primary numerical example. In Remark III.6 and Section VI-A, the graph shifts S_l are real symmetric circulant matrices on C(N,Q). Any such matrix has eigenvalues satisfying λ_l(k)=λ_l(N-k) (indices mod N), so the joint spectrum satisfies λλ(k)=λλ(N-k). For N=100, Q={1,3}, the joint spectrum has at most 51 distinct points, not 100. Hence Assumption II.1 fails exactly where Algorithm V.1 is tested, and the proofs of Theorem III.1 (via p_n interpolation) and the uniqueness of the GFT do not apply. The assumption is also genuinely load-bearing, not a technicality: for a fixed GFT with repeated eigenvalues, take S=diag(1,1) and H=span{(1,1)^T}; H is shift-invariant but is not B_Ω for any Ω⊂{1,2} when U=I. The abstract's unqualified phrase 'on an undirected finite graph' therefore overstates the scope, and the numerical sections do not check the assumption before applying the framework.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces graph shift-invariant spaces (GSISs) for undirected finite graphs and, under Assumption II.1 (real symmetric commutative graph shifts with distinct joint spectrum), proves that a linear space is bandlimited iff it is shift-invariant iff it is finitely generated iff it is principal (Theorem III.1). Theorem III.2 gives an explicit single generator and a Krylov representation for each bandlimited space. The paper further characterizes shift-invariant reproducing kernel Hilbert spaces (Theorems IV.1 and IV.2), and proposes a finite-step Krylov sampling and reconstruction algorithm (Algorithm V.1), with numerical experiments on circulant graphs and a US flight-delay dataset.","tokens_in":20182,"tokens_out":7291,"duration_ms":65583,"significance":"If the results are evaluated under Assumption II.1, the paper gives a clean and useful unification of three notions common in graph signal processing. The proofs are elementary and transparent, and the constructive parts (explicit generator, Vandermonde-based Riesz bounds, nested Krylov structure, finite-step reconstruction) are valuable. The main weakness is that the abstract and introduction state the results for general undirected finite graphs, while the theorems require a distinct joint spectrum; moreover the circulant-graph numerical experiment in Section VI-A is not covered by that assumption. These issues are load-bearing and need to be addressed before the paper can be accepted.","major_comments":[{"comment":"The unqualified claim that every GSIS is bandlimited and every bandlimited space is principal is false without Assumption II.1. For example, take N=2, S1=diag(1,1), U=I, and H=span{(1,1)^T}; H is invariant under S1 but is not B_Omega for any subset Omega of {1,2}. The proof of (ii) implies (i) in Theorem III.1 uses the interpolating polynomials in (VII.1)-(VII.2), which require the joint-spectrum points in Assumption II.1 to be distinct. The abstract and introduction should either state this restriction explicitly or the theory must be extended to repeated joint-spectrum values.","section":"Abstract and Theorem III.1"},{"comment":"The circulant-graph numerical experiment violates Assumption II.1. For the shifts defined in Remark III.6, the eigenvalue relation lambda_l(N-k)=lambda_l(k) holds for every k, so the joint spectrum has at most floor(N/2)+1 distinct points; in particular, for N=100 and Q={1,3}, Assumption II.1 fails. Since the identification H(Phi)=B_Omega and the least-squares formula (V.6) rely on Theorem III.1, the numerical results in Section VI-A are not justified by the paper's theorems. The authors should either run the experiment on graphs satisfying Assumption II.1 or provide a separate analysis for the repeated-eigenvalue case.","section":"Section VI-A and Remark III.6"},{"comment":"The definition of the graph Fourier transform via (II.5) is only well-defined up to sign under Assumption II.1. With repeated eigenvalues, the orthogonal matrix U in (II.2) is not unique up to sign, so the spaces B_Omega in (III.3) depend on the choice of eigenvectors. This is another reason why the distinct-joint-spectrum assumption is load-bearing for the paper's central equivalence, and it should be stated as a hypothesis in every theorem and in the abstract rather than only in Assumption II.1.","section":"Section II-C"}],"minor_comments":[{"comment":"The arrows in the proof of Theorem III.1 appear as corrupted symbols such as '/Leftr⫯g⊸tl⫯ne⇒'; these should be replaced with proper LaTeX arrows.","section":"Throughout"},{"comment":"In the sentence 'For the noiseless scenario shown in the middle row of Figure 1...', the phrase 'the relative maximal sampling error RE(n, P)' should read 'SE(n, P)' to be consistent with the definition.","section":"Section VI-A, text after Figure 1"},{"comment":"The output field 'efinal = ∥y−Axout∥' is described as a scalar error, but in the pseudocode the variable 'e' is a residual vector and the output statement writes 'efinal = e'. Please clarify whether the output is the residual vector or its norm.","section":"Algorithm V.1"},{"comment":"The caption of Figure 2 mentions '29 August 2024' but the dataset is described as July-September 2014 and 2015; the year appears to be a typo.","section":"Section VI-B"}],"recommendation":"major_revision","confidential_remarks":"The paper relies on several results from the authors' own preceding work, especially the commutant-polynomial filter equivalence in [34, Theorem A.3] and the simultaneous diagonalization in [24]. This reliance is legitimate, but the authors should make the dependency more explicit in the introduction. If the distinct-joint-spectrum assumption cannot be relaxed, the title and abstract should be narrowed; otherwise the central equivalence is presented more broadly than the proofs support."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe central claim holds up. Under Assumption II.1 (distinct joint spectrum), the proof that shift-invariant, bandlimited, finitely generated, and principal spaces are all equivalent on undirected finite graphs is clean and correct. The interpolation argument at the joint spectral points is standard, and the careful statement of the generator condition in Theorem III.2 (nonzero Fourier support on all of Omega) is a genuine contribution. The RKHS equivalence is also coherent, and the finite-step Krylov sampling algorithm is a reasonable practical add-on. I found no circularity or hidden fitting in the theory; the formal results are honestly derived.\n\nThe soft spot is real and it is in the paper's own house. Assumption II.1 requires the N joint-spectrum vectors to be distinct. For the circulant graph shifts in Remark III.6 and Section VI-A, the eigenvalues satisfy lambda_l(k) = lambda_l(N-k), so for N=100, Q={1,3}, the joint spectrum has at most 51 distinct points, not 100. The numerical section never flags this. The main theorems III.1, III.2, and IV.1 simply do not apply to the simulations as stated. This is not a refutation of the theory under its assumption--the stress-test example with S=diag(1,1) shows the equivalence genuinely fails without distinctness, which the authors correctly exclude--but it does mean the abstract's unqualified phrase \"on an undirected finite graph\" overstates the scope, and the numerical evidence does not validate the framework where it matters most.\n\nOther soft spots are minor by comparison. Equation (VI.3) is asserted without proof, and the flight-delay comparison is entirely in-sample, with no error bars or out-of-sample check. Those affect the applied claims, not the math. I would also ask the authors to state explicitly, in the numerical section, when Assumption II.1 holds and when it does not, and to either restrict the circulant experiments to parameter regimes where the assumption holds (e.g., odd N with appropriately chosen Q) or else explain what happens with repeated eigenvalues.\n\nBottom line: the theoretical core is worth refereeing, but the paper needs revision before acceptance--the scope of the main theorem must be matched to the simulations. I would send it out, but I would tell the referee to check the circulant assumption carefully. I would not cite it for the numerical claims; I might cite the equivalence theorem if I needed that specific statement.","headline":"Solid theoretical equivalence under a distinct-spectrum assumption, but the paper's own circulant simulations violate that assumption and are not covered by the main theorem.","tokens_in":684,"tokens_out":1109,"would_cite":false,"duration_ms":28269,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A12","94A20","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that shift-invariance, bandlimitedness, and single-generator structure coincide for graph signals.","keywords":["graph shift-invariant spaces","bandlimited graph signals","principal shift-invariant spaces","reproducing kernel Hilbert spaces","shift-invariant kernels","sampling and reconstruction","Krylov subspaces","graph Fourier transform"],"falsifier":"On the 4-cycle with the adjacency matrix as the only graph shift, the eigenvalues are 2, 0, -2, 0, so the joint spectrum is not distinct. Take the two indices with eigenvalue 0 as $\\Omega$ and let phi0 = u_1 + u_3, the sum of the two corresponding Fourier basis vectors; then T^m phi0 = 0^m phi0 for every m, so the Krylov span has dimension 1, not #$\\Omega$ = 2. This calculation shows the distinctness condition is necessary; if a symmetric regular graph with repeated eigenvalues nevertheless satisfies the one-generator representation by grouping equal eigenvalues, the theorem's scope could be extended, and if not, the unqualified statement about undirected finite graphs would be false.","tokens_in":19720,"feed_emoji":"📡","tokens_out":7878,"duration_ms":77728,"temperature":0.7,"pith_summary":"On an undirected finite graph, this paper tries to collapse three seemingly different notions of a simple signal space into one. It introduces graph shift-invariant spaces (GSISs), linear spaces of graph signals closed under graph shifts, and proves that, under a distinct-joint-spectrum assumption on the shifts, a space is shift-invariant if and only if it is bandlimited, and every such space is generated by a single signal and a single shift as a Krylov subspace. It then shows that every GSIS with the standard Euclidean inner product is a reproducing kernel Hilbert space with a shift-invariant kernel, and that every such RKHS inner product is a diagonal weighting in the graph Fourier domain. The payoff is practical: because every bandlimited space has this one-generator nested Krylov structure, the paper gives a finite-step sampling and reconstruction algorithm and tests it on circulant graphs and US airport delay data.","feed_headline":"Graph shift-invariance equals bandlimitedness on finite graphs","feed_subtitle":"A new theorem collapses shift-invariant, bandlimited, and principal spaces into one, giving a finite-step sampling algorithm.","key_machinery":"The load-bearing object is the simultaneous diagonalization of the commutative graph shifts together with the polynomial filters built from them. Because Assumption II.1 makes the joint spectrum distinct, the paper can interpolate: for each frequency point there is a polynomial p_n with p_n evaluated at the joint spectrum equal to the Kronecker delta, so p_n of the shifts is the orthogonal projector onto the n-th graph Fourier basis vector. That same interpolation toolkit produces a scalar shift T as a linear combination of the graph shifts whose eigenvalues are distinct on the frequency set $\\Omega$, turning the bandlimited space into the Krylov space span{T^m phi0 : m = 0, ..., #$\\Omega$ - 1}. The nested Krylov spaces H_n(Phi) = span{S^$\\alpha$ phi : |$\\alpha$| <= n} then serve as the spatial-domain ladder on which the finite-step sampling and reconstruction algorithm operates.","core_discovery":"Under Assumption II.1, real symmetric commuting graph shifts whose joint spectrum has N distinct points, the paper's Theorem III.1 establishes that four classes of subspaces of RN are the same: bandlimited spaces B_Omega, shift-invariant spaces, finitely generated shift-invariant spaces, and principal shift-invariant spaces. The implication from shift-invariance to bandlimitedness is proved by polynomial interpolation: for each frequency n there is a polynomial p_n in the shifts whose Fourier multiplier is the diagonal projector onto that frequency, so a shift-invariant space splits into frequency axes and equals B_Omega with $\\Omega$ the union of the Fourier supports and #$\\Omega$ equal to the dimension. Theorem III.2 sharpens this: every bandlimited space equals span{T^m phi0 : 0 <= m <= #$\\Omega$ - 1}, where phi0 has nonzero Fourier coefficients exactly on $\\Omega$ and T is a linear combination of the graph shifts whose eigenvalues are distinct on $\\Omega$; the generator phi0 can be chosen as the inverse graph Fourier transform of the characteristic function of $\\Omega$, the graph analogue of the sinc function. The paper also proves that every GSIS with the Euclidean inner product is a reproducing kernel Hilbert space with a shift-invariant kernel, and that every such RKHS inner product is a diagonal Fourier-domain dot product.","pith_inferences":["The one-generator representation suggests a graph analogue of the classical sinc function, which could be used to derive explicit interpolation formulas and sampling theorems for bandlimited graph signals beyond the algorithmic reconstruction treated in the paper.","Because every GSIS is an RKHS with a diagonal Fourier-domain inner product, kernel selection on graphs can be reinterpreted as choosing both a bandlimited subspace and a diagonal weight, a viewpoint that may simplify comparisons between diffusion, regularization, and spline kernels.","The flight-delay experiment suggests a practical rule: when signal energy is spatially localized at a few hub vertices, a shift-invariant model with a small Krylov level may outperform low-frequency bandlimited modeling; this rule could be tested on other transportation or social networks.","A natural next step is to investigate whether the equivalence survives when repeated joint spectrum points are grouped into eigenspaces, since the polynomial interpolation argument would then need block projectors instead of individual frequency projectors."],"forward_implications":["Every linear space of graph signals closed under the graph shifts is a bandlimited space, so bandlimited sampling, projection, and reconstruction methods apply to every shift-invariant subspace without further assumptions.","Every bandlimited space has a one-generator description, so a space of dimension d can be represented by a generator and its first d shifts instead of by an arbitrary basis.","Shift-invariant spaces with the Euclidean inner product are reproducing kernel Hilbert spaces with shift-invariant kernels, and conversely every shift-invariant RKHS inner product is a diagonal weighting in the graph Fourier domain, connecting GSISs to kernel-based learning on graphs.","The Krylov nesting gives a finite-step algorithm that reconstructs a signal in a finitely generated GSIS from noisy samples, stops when the residual meets a threshold, and reaches the least-squares fit when the full space is reached.","The numerical experiments indicate that low Krylov levels suffice for well-localized signals on circulant graphs, and that US airport flight-delay data is better modeled by a GSIS with adaptively chosen generators than by a low-frequency bandlimited space."],"supporting_citations":[{"why":"Supplies the commutative multi-shift framework and the theorem that any filter commuting with the shifts is a polynomial filter, used to diagonalize shift-invariant kernels and justify the Krylov representation.","marker":"[34]"},{"why":"Establishes for a single shift that commutators with the shift are polynomial filters, serving as the base case for Proposition II.2.","marker":"[37]"},{"why":"Provides the polynomial interpolation theorem used to construct the projectors p_n(S) and the univariate interpolating polynomials q_n that prove Theorems III.1 and III.2.","marker":"[52]"},{"why":"Defines Paley-Wiener and bandlimited spaces on graphs and sampling in those spaces, the notion that Theorem III.1 unifies with shift-invariance.","marker":"[14]"},{"why":"Supplies the graph uncertainty principle used to show that a principal GSIS generated by a localized signal has large dimension (Proposition III.5).","marker":"[44]"},{"why":"Sets the sampling and reconstruction problem for bandlimited graph signals, including dynamic sampling, whose injectivity characterization Corollary V.3 extends.","marker":"[19]"}],"fun_headline_variants":["Shift-invariant graph spaces collapse to bandlimited","Graph shift-invariance equals bandlimitedness","Finite-step sampling for graph shift-invariant spaces","All graph shift-invariant spaces are bandlimited","New proof: shift-invariant equals bandlimited"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument relies on the graph shifts sharing a complete set of eigenvectors and on no two frequency labels carrying the same list of eigenvalues, so that polynomial interpolation can separate individual frequencies; when eigenvalues repeat, the proofs of the equivalences and of the one-generator representation are not established.","fun_headline_variants_meta":{"raw":{"variants":["Shift-invariant graph spaces collapse to bandlimited","Graph shift-invariance equals bandlimitedness","Finite-step sampling for graph shift-invariant spaces","All graph shift-invariant spaces are bandlimited","New proof: shift-invariant equals bandlimited"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000895,"raw_usage":{"total_tokens":3879,"prompt_tokens":991,"completion_tokens":2888,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":2816}},"tokens_in":607,"tokens_out":2888,"duration_ms":24624,"temperature":1.0,"reasoning_tokens":2816,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:37:52.056463+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On the 4-cycle with the adjacency matrix as the only graph shift, the eigenvalues are 2, 0, -2, 0, so the joint spectrum is not distinct. Take the two indices with eigenvalue 0 as $\\Omega$ and let phi0 = u_1 + u_3, the sum of the two corresponding Fourier basis vectors; then T^m phi0 = 0^m phi0 for every m, so the Krylov span has dimension 1, not #$\\Omega$ = 2. This calculation shows the distinctness condition is necessary; if a symmetric regular graph with repeated eigenvalues nevertheless satisfies the one-generator representation by grouping equal eigenvalues, the theorem's scope could be extended, and if not, the unqualified statement about undirected finite graphs would be false.","supporting_citations":[{"cited_title":"Polynomial graph filters of multiple shifts and distributed implementation of inverse filtering,","cited_arxiv_id":null,"evidence_quote":"Supplies the commutative multi-shift framework and the theorem that any filter commuting with the shifts is a polynomial filter, used to diagonalize shift-invariant kernels and justify the Krylov representation."},{"cited_title":"Discrete signal processing on graphs,","cited_arxiv_id":null,"evidence_quote":"Establishes for a single shift that commutators with the shift are polynomial filters, serving as the base case for Proposition II.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the polynomial interpolation theorem used to construct the projectors p_n(S) and the univariate interpolating polynomials q_n that prove Theorems III.1 and III.2."},{"cited_title":"Sampling in Paley-Wiener spaces on combinatorial graphs,","cited_arxiv_id":null,"evidence_quote":"Defines Paley-Wiener and bandlimited spaces on graphs and sampling in those spaces, the notion that Theorem III.1 unifies with shift-invariance."},{"cited_title":"On Graph Uncertainty Principle and Eigenvector Delocalization","cited_arxiv_id":"2306.15810","evidence_quote":"Supplies the graph uncertainty principle used to show that a principal GSIS generated by a localized signal has large dimension (Proposition III.5)."},{"cited_title":"Reconstruction of bandlimited graph signals from measurements,","cited_arxiv_id":null,"evidence_quote":"Sets the sampling and reconstruction problem for bandlimited graph signals, including dynamic sampling, whose injectivity characterization Corollary V.3 extends."}],"review_version":1}