{"id":"1326fbc1-0f56-48d4-a8ce-2cfaa612ba27","arxiv_id":"2412.15133","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A theoretical stability bound and a manifold-optimization algorithm for blind deconvolution of graph signals under small eigenbasis perturbations.","lead":"Graph signal processing usually assumes you know the network exactly, but in practice networks are estimated from data. This paper proves that a standard blind deconvolution method still works when the network's eigenvectors are slightly wrong, and offers a new algorithm that cleans up the eigenvectors while recovering the signal.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed equivalence between (13) and (14) in the Supplement is false for generic w and Δ, so the proof of Theorem 2 does not establish the central stability bound.","rationale":"The reader's CONDITIONAL verdict identified that the proof of Theorem 2 relies on an unstated equivalence between (13) and (14). My stress-test agrees this is the central issue, but goes further: the equivalence is not merely unstated, it is algebraically false. The supplementary derivation substitutes w = ˜g∘˜h0 and claims an exact identity with an E that does not depend on w; substituting the definitions gives different expressions unless Vp=V or D_w commutes with V^T Vp. Since Theorem 2 is the paper's main theoretical contribution, the central claim is not established as written. The reader's additional concern about dropping the (V−Δ) factor in ∥E∥_F is less damaging: if Vp is an orthonormal eigenbasis, left multiplication by Vp preserves the Frobenius norm, so that equality is justified under the natural eigenbasis assumption. I therefore do not adopt that part of the reader's weakest_assumption. The empirical section and reproducible code are positive and the RBDoGS algorithm may be useful, but the theory section needs a substantially corrected proof. Given the proof's central step is false, the appropriate disposition is REJECT rather than CONDITIONAL; a corrected proof or a reformulated theorem would allow reconsideration.","tokens_in":13573,"tokens_out":16336,"duration_ms":133374,"concrete_test":"Run a direct substitution test with N=2: set V=I, Vp = 90-degree rotation, D0=diag(2,3), w=(4,5), X0=ones(2,1), and Δ=V−Vp. Compute L = Vp*(diag(w)*D0)*Vp'*V*D0^{-1}*V'*X0 and R = V*diag(w)*V'*(X0 + (V−Δ)*(Δ' − D0*Δ'*V*D0^{-1}*V')*X0). If ∥L−R∥_F > 0, the equivalence used in the proof of Theorem 2 fails. Repeat for random orthogonal V,Vp with N=20 and random diagonal D0,w to confirm the mismatch is generic, not an artifact of the 2x2 example.","verdict_should_be":"REJECT","load_bearing_attack":"The most load-bearing step is the change of variables in the Supplement: with w = ˜g∘˜h0, the paper asserts Vp diag(˜g) Vp^T Y = P(w)[X0 + E], where E is independent of w. Direct algebra contradicts this. Let D0 = diag(˜g0), D_w = diag(w), and Q = V^T Vp = V^T(V−Δ). Then the left-hand side equals V Q D_w D0 Q^T D0^{-1} V^T X0, while P(w)(X0+E) equals V [D_w + D_w Q D0 Q^T D0^{-1} − D_w Q Q^T] V^T X0. These two expressions agree only in special cases, e.g., D_w = I and Vp orthonormal, not for general feasible w; even the first-order term in w around w = 1N differs unless D_w commutes with Q. Because the optimality inequality (18) and the bound (20) are derived for the supposed equivalent program (14), the proof does not control the actual estimator (3). The main-text norm equality ∥E∥_F = M2∥∆∥_F is less serious than the reader suggests: it follows when Vp is orthonormal. The invalid (13)−(14) equivalence is the real gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript considers blind deconvolution of graph signals when the graph shift operator's eigenbasis is known only approximately. It proposes to solve the convex program (3) with the perturbed basis Vp, claims a stability bound (Theorem 2) showing that the estimation error remains controlled for small eigenbasis perturbations, and introduces a block-coordinate algorithm RBDoGS that alternates between Huber-smoothed blind deconvolution and Riemannian gradient descent on the Stiefel manifold for eigenbasis denoising. Numerical experiments on Erdős-Rényi graphs with controlled and covariance-based perturbations report improved recovery over the non-robust baseline and over two prior perturbation-aware methods.","tokens_in":13786,"tokens_out":16872,"duration_ms":104261,"significance":"The problem addressed is relevant, since graph topology is often imperfectly known; a rigorous stability guarantee would strengthen the case for the convex approach to graph blind deconvolution. The algorithm is clearly stated, the code is released, and the experiments cover relevant baselines. However, the proof of Theorem 2, the main theoretical contribution, contains a false algebraic equivalence between (13) and (14) in the supplementary; as a result, the claimed stability bound is not established. The paper's value currently rests on the empirical demonstration, so the theoretical claims must be corrected or substantially qualified.","major_comments":[{"comment":"The claimed equivalence between (13) and (14) is not valid for generic w and Δ. With U = V^T Δ, A = I − U, D_g = diag(g), D_h = diag(h0), D = diag(w) = D_g D_h, and D_g0 = diag(g0), the left-hand side of the displayed equality equals V A D_g A^T D_h V^T X0, while the right-hand side equals V [D + D A(U^T − D_g0 U^T D_h)] V^T X0. Expanding the difference of the bracketed terms to first order in U and using the orthonormality of Vp, which implies U + U^T = O(∥U∥^2), gives a first-order term D U − U D (up to sign). This vanishes only if D commutes with U, which is not true for a generic diagonal D and a generic skew-symmetric U. Therefore the equality Vp diag(g) Vp^T Y = P(w)[X0 + E] fails to first order in the perturbation, so (14) is not equivalent to (13). Since the optimality inequality (18) and the bound (20) are derived for (14), they do not control the actual estimator (3). This is a load-bearing gap in the proof of Theorem 2.","section":"Supplementary Material, eqs. (13)-(14)"},{"comment":"The derivation of (16) invokes [20, Proposition 1] for the lower bound on ∥P(ŵ)(X0 + E(S))∥_{1,1}. The hypotheses of that proposition are not stated, and it is not demonstrated that the perturbed matrix X0 + E(S), which is no longer Bernoulli-Gaussian, satisfies them. Without a verification or a restatement of the proposition, the constants Q and C1 and hence the bound in Theorem 2 are not self-contained. This is an additional gap in the proof of the main theorem.","section":"Supplementary Material, inequality (16)"}],"minor_comments":[{"comment":"The equality ∥E∥_F = ∥[Δ^T − diag(g0)Δ^T H0]X0∥_F relies on Vp = V − Δ being orthonormal; please state this explicitly, since the reader cannot otherwise infer it from the text.","section":"Section III, after eq. (4)"},{"comment":"The parameter σ appearing in the definition of Q is not defined in the theorem statement; it is introduced later in the proof. Please either define σ or state explicitly that the bound holds with the value of σ ∈ [0,1] determined in the proof.","section":"Theorem 2"},{"comment":"The convergence claim for Algorithm 1 cites [28, Theorem 4] but does not verify the theorem's assumptions in the present setting (e.g., block-i Lipschitz smoothness of F, exact minimization in (9), and sufficient decrease of the Riemannian gradient step in (10)). A short verification would make the claim credible.","section":"Section IV"},{"comment":"M2 is defined using the normalized direction Δ/∥Δ∥_F, so the bound (6) depends on the perturbation direction. If the authors intend a uniform condition on ∥Δ∥_F, they should take the supremum of M2 over all unit-norm directions, or clarify that (6) is a per-realization bound.","section":"Equation (6)"},{"comment":"RBDoG is used where the algorithm is named RBDoGS; please harmonize the notation.","section":"Fig. 2 caption and text"},{"comment":"Kathri-Rao should be Khatri-Rao.","section":"Supplementary Material"}],"recommendation":"major_revision","confidential_remarks":"The main theoretical claim is not proven due to the false equivalence between (13) and (14). If the authors cannot repair this proof, the paper would reduce to an empirical study; the editor may wish to weigh whether that is sufficient for the journal. The dependence on the companion paper [20] for Theorem 1 and Proposition 1 should also be examined carefully, since the bound in Theorem 2 inherits conditions from [20] that are not reproduced."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the algorithm and experiments are worth a look, but the paper's headline stability theorem has a proof gap that looks structural, not cosmetic.\n\nThe problem is well chosen: source localization from an estimated graph eigenbasis is exactly where the perfect-V assumption of earlier work breaks. The robust algorithm RBDoGS—alternating the convex deconvolution with a Stiefel-manifold step to denoise the eigenbasis—is new, sensible, and the reported gains over BDoG and the RBD-G variants are consistent with the intuition. The code is public and the figures are reproducible. That part is solid.\n\nThe soft spot is Theorem 2. The main-text norm equality that the reader flags is actually fine: E is defined as Vp times a factor, and Vp is orthogonal, so the Frobenius norm is preserved. The real problem is in the supplementary. The change of variables w = ˜g∘˜h0 is claimed to give Vp diag(˜g) Vp^T Y = P(w)[X0+E]. Working through the algebra, this identity holds only in special cases—e.g., when w is proportional to the all-ones vector and Vp is orthonormal—not for the general feasible w that the optimality argument needs. The optimality inequality (18) and the final bound (20) are derived for the supposed equivalent program (14), so they don't control the actual estimator (3). That's a load-bearing gap: without a correct equivalence, the stability bound in the main text isn't established. It might be repairable—perhaps by defining the perturbed filter operator differently, or by adding a condition linking w and Δ—but it is not a missing detail; it's the core of the proof.\n\nThe convergence claim for Algorithm 1 leans on an external to-appear theorem; that's standard practice, but the authors should double-check the conditions are met.\n\nBottom line: this is a serious subfield contribution with a promising empirical method, and it deserves a fair referee. I would send it to peer review, but flag a mandatory major revision: fix the proof of Theorem 2 or state precisely the regime in which the equivalence holds, then confirm the bound. If I were citing it, I'd wait for the corrected version.","headline":"The algorithm and experiments are worth attention, but the stability theorem's proof has a load-bearing gap that needs fixing before the theory can be trusted.","tokens_in":14396,"tokens_out":7345,"would_cite":false,"duration_ms":45353,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a convex blind-deconvolution estimator for graph signals stays within a provable error bound under small eigenbasis perturbations, and that an alternating algorithm can denoise the eigenbasis to sharpen recovery.","keywords":["graph signal processing","blind deconvolution","graph perturbation","eigenbasis denoising","Stiefel manifold","sparse recovery","stability","convex optimization"],"falsifier":"For a small random undirected graph with $N=20$ nodes, sample a Bernoulli-Gaussian sparse input $X_0$ and an invertible filter so that the exact-recovery condition (2) holds, then form a perturbed eigenbasis $V_p$ by a skew-symmetric rotation perturbation with increasing magnitude. Compute both sides of the asserted equality $\\|E\\|_F = \\|[\\Delta^\\top - \\operatorname{diag}(\\tilde{g}_0)\\Delta^\\top H_0]X_0\\|_F$; any measurable discrepancy would disprove the equality used to derive (6). Then solve (3) and check whether the empirical error $\\|\\hat{\\tilde{g}}_p - \\tilde{g}_0\\|_2$ stays under the right-hand side of (4); a clear violation would indicate the proof's reformulation between (13) and (14) or the invoked companion proposition does not hold in this setting.","tokens_in":13264,"feed_emoji":"🕸","tokens_out":16818,"duration_ms":92063,"temperature":0.7,"pith_summary":"Given a network whose graph-shift operator is known only through a perturbed eigenbasis, the paper asks whether blind deconvolution of sparse signals on the graph still recovers the convolutional filter. It proves that the convex inverse-filter estimator is stable: the error $\\|\\hat{\\tilde{g}}_p - \\tilde{g}_0\\|_2$ is bounded by a rational function of the perturbation-dependent matrix $E(S^c)$, provided the perturbation is small enough to keep the denominator positive. It then formulates a joint, non-convex problem that alternates filter deconvolution with eigenbasis denoising on the Stiefel manifold, argues that this algorithm converges, and shows numerically that it outperforms both the non-robust convex baseline and existing perturbation-tolerant methods, especially when the eigenbasis error grows.","feed_headline":"Blind graph deconvolution tolerates small eigenbasis errors","feed_subtitle":"A convex estimator stays within a provable error bound while an alternating algorithm further denoises the eigenbasis.","key_machinery":"The argument's load-bearing object is the perturbation error matrix $E := (V-\\Delta)[\\Delta^\\top - \\operatorname{diag}(\\tilde{g}_0)\\Delta^\\top H_0]X_0$, which collects how the eigenbasis mismatch $\\Delta$ distorts the observations after the change of variables $w = \\tilde{g} \\circ \\tilde{h}_0$. The proof of Theorem 2 splits $E$ into the sparse-support part $E(S)$ and its complement $E(S^c)$, lower-bounds the contribution of the sparse part via a proposition from the cited reference, and upper-bounds the complement via the column-operator norm $\\|[E(S^c)]^\\top V \\odot V\\|_{1\\to 2}$; the final bound is a rational function whose denominator must stay positive, giving a quantitative meaning to 'small perturbation.' On the algorithmic side, the machinery is a block-coordinate descent that alternates an exact convex minimization for the filter taps with a single retraction-based Riemannian gradient step for the eigenbasis on the Stiefel manifold, using the Cayley transform, with convergence guaranteed by the cited manifold block-coordinate descent theorem.","core_discovery":"The central result is Theorem 2: under the same Bernoulli-Gaussian and filter-condition assumptions that guarantee exact recovery for a known eigenbasis, replacing $V$ by $V_p = V - \\Delta$ makes the convex estimator (3) err by at most $\\|\\hat{\\tilde{g}}_p - \\tilde{g}_0\\|_2 \\le \\frac{2\\sigma_{\\max}(\\operatorname{diag}(\\tilde{g}_0) - \\tilde{g}_0\\tilde{g}_0^\\top/N)\\,\\|E(S^c)\\|_{1,1}}{P Q - a_0\\|E(S^c)\\|_{1,1} - \\|[E(S^c)]^\\top V \\odot V\\|_{1\\to 2}}$, where the denominator must be positive. The paper interprets this as a quantitative statement that small eigenbasis errors cause only small recovery errors, with the threshold for 'small' governed by the filter's ill-conditioning measure $\\|P_1^\\perp \\tilde{g}_0\\|_2$: the closer $\\tilde{g}_0$ is to the all-ones vector, the larger the tolerated perturbation. The algorithmic claim is that the alternating RBDoGS method, built on a Huber-smoothed surrogate and a Riemannian gradient step on the Stiefel manifold per iteration, converges by the manifold block-coordinate descent theorem cited from the literature, and that in experiments it nearly corrects small eigenbasis perturbations and outperforms the baselines.","pith_inferences":["Editorial: The asserted equality $\\|E\\|_F = \\|[\\Delta^\\top - \\operatorname{diag}(\\tilde{g}_0)\\Delta^\\top H_0]X_0\\|_F$, used to turn the stability bound into the perturbation threshold (6), can be tested numerically; if it fails for random rotation-type perturbations $\\Delta$, the threshold needs a correction factor and the practical small-perturbation range would shift.","Editorial: The same perturbation-error decomposition could be applied to perturbations of the graph shift operator $S$ rather than of its eigenbasis directly, yielding a stability statement in terms of first-order eigenvector sensitivities.","Editorial: The denominator in (4) defines an implicit phase transition; locating it empirically by sweeping the perturbation magnitude in the paper's rotation model would give a practical criterion for when the eigenbasis-denoising step of RBDoGS becomes necessary.","Editorial: Combining the covariance-estimation setting of Remark 1 with the stability bound yields a finite-sample guarantee for blind deconvolution from raw observations, once the sample eigenvector error $\\|\\Delta\\|_F$ is bounded in probability."],"forward_implications":["Errors in the recovered inverse filter stay proportional to the size of the perturbation-induced contaminating term $E(S^c)$ rather than to the full dynamic range of the data.","Easier filtering problems, whose inverse frequency response $\\tilde{g}_0$ is close to the all-ones vector, tolerate larger eigenbasis errors before the error bound (4) breaks down.","The RBDoGS algorithm corrects small eigenbasis perturbations nearly perfectly and, for larger perturbations, recovers the support of the sparse inputs substantially better than the plain convex estimator and the node-domain perturbation-robust baselines.","When the eigenbasis is estimated from the sample covariance of the observations, as in Remark 1 of the paper, the stability result ties the number of available signals $P$ to the admissible deviation of the estimated eigenvectors."],"supporting_citations":[{"why":"Supplies the convex estimator (1) and (3) whose robustness to eigenbasis perturbations is the paper's main theoretical subject.","marker":"[18]"},{"why":"Provides Theorem 1 (exact recovery conditions) and Proposition 1, which the proof of Theorem 2 invokes to lower-bound the sparse-support term.","marker":"[20]"},{"why":"Provides the RBD-G and RBD-G-rew node-domain perturbation-robust blind deconvolution baselines that RBDoGS is compared against.","marker":"[26]"},{"why":"Justifies the eigenbasis-perturbation model by showing graph eigenvectors can be estimated from the sample covariance of diffused signals.","marker":"[27]"},{"why":"Supplies the block-coordinate descent convergence theorem cited to prove that Algorithm 1 (RBDoGS) converges.","marker":"[28]"}],"fun_headline_variants":["Blind graph deconvolution survives small eigenbasis mistakes","Provable error bound for blind graph deconvolution with noisy eigenbasis","Eigenbasis noise handled in blind graph deconvolution","Alternating algorithm gives robust blind deconvolution on perturbed graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The tolerable-perturbation bound (6) rests on an unproven equality, $\\|E\\|_F = \\|[\\Delta^\\top - \\operatorname{diag}(\\tilde{g}_0)\\Delta^\\top H_0]X_0\\|_F$, that drops a $(V-\\Delta)$ factor, and the proof of Theorem 2 treats the change-of-variables reformulation of the perturbed problem as an exact equivalence even though that equivalence is not derived; if either step gives way, the stated error bound does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Blind graph deconvolution survives small eigenbasis mistakes","Provable error bound for blind graph deconvolution with noisy eigenbasis","Eigenbasis noise handled in blind graph deconvolution","Alternating algorithm gives robust blind deconvolution on perturbed graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000674,"raw_usage":{"total_tokens":3073,"prompt_tokens":958,"completion_tokens":2115,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":2043}},"tokens_in":574,"tokens_out":2115,"duration_ms":13965,"temperature":1.0,"reasoning_tokens":2043,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:35:42.046502+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small random undirected graph with $N=20$ nodes, sample a Bernoulli-Gaussian sparse input $X_0$ and an invertible filter so that the exact-recovery condition (2) holds, then form a perturbed eigenbasis $V_p$ by a skew-symmetric rotation perturbation with increasing magnitude. Compute both sides of the asserted equality $\\|E\\|_F = \\|[\\Delta^\\top - \\operatorname{diag}(\\tilde{g}_0)\\Delta^\\top H_0]X_0\\|_F$; any measurable discrepancy would disprove the equality used to derive (6). Then solve (3) and check whether the empirical error $\\|\\hat{\\tilde{g}}_p - \\tilde{g}_0\\|_2$ stays under the right-hand side of (4); a clear violation would indicate the proof's reformulation between (13) and (14) or the invoked companion proposition does not hold in this setting.","supporting_citations":[{"cited_title":"Blind identification of invertible graph filters with sparse inputs,","cited_arxiv_id":null,"evidence_quote":"Supplies the convex estimator (1) and (3) whose robustness to eigenbasis perturbations is the paper's main theoretical subject."},{"cited_title":"Blind Deconvolution on Graphs: Exact and Stable Recovery","cited_arxiv_id":"2409.12164","evidence_quote":"Provides Theorem 1 (exact recovery conditions) and Proposition 1, which the proof of Theorem 2 invokes to lower-bound the sparse-support term."},{"cited_title":"Network topology inference from spectral templates,","cited_arxiv_id":null,"evidence_quote":"Justifies the eigenbasis-perturbation model by showing graph eigenvectors can be estimated from the sample covariance of diffused signals."}],"review_version":1}