{"id":"5de88aed-7c26-437e-98ec-9905d2118cf7","arxiv_id":"1908.06672","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A graph Fourier basis defined by ℓ1 variation minimization has k-th vector with at most k distinct values, and a greedy grouping algorithm approximates the basis.","lead":"This paper proposes a new graph Fourier transform based on minimizing absolute (ℓ1) signal variation instead of the usual squared variation, and gives a greedy algorithm to compute it. The authors prove the new basis vectors can only take a limited number of distinct values, which could lead to faster and sparser graph signal processing.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Greedy basis lacks an approximation guarantee; for k=2 its merge rule maximizes raw W(A,B) instead of the normalized cut that defines the exact l1 u2, so the N<=8 geometric experiments do not establish the central algorithmic claim.","rationale":"The reader's CONDITIONAL verdict is appropriate. The theoretical necessary condition (Theorem 4) is internally sound: the reduction to a linear objective on an ellipsoid is valid, Q=V^T Lambda V is positive definite, and the l>=2 perturbation argument with r'^T c=0 yields a feasible lower-cost point. Corollary 5 follows correctly. The weakness is the bridge to the greedy algorithm. Theorem 9 only provides a necessary condition, which the authors acknowledge is not sufficient; the concrete mismatch at u2 shows the approximation claim is not merely missing a bound but has a plausible failure mechanism. The proposed enumeration test is feasible for N<=20 and would directly measure whether the mismatch occurs. If it does, the central practical contribution is conditional on graph class or requires a modified merge objective and additional analysis. This does not overturn the paper's theoretical contribution, so the verdict remains CONDITIONAL and unchanged from the reader's assessment.","tokens_in":11359,"tokens_out":13453,"duration_ms":144201,"concrete_test":"Generate random weighted Erdős-Rényi graphs and adversarial graphs with one heavy edge inside a large cluster for N=10..20. For each graph, enumerate all 2^{N-1} bipartitions (A,A^c) to compute the exact first nontrivial l1 basis vector u2 as the two-valued zero-mean unit-norm signal minimizing S, equivalently maximizing W(A,A^c)/sqrt(|A|(N-|A|)). Construct the greedy basis ~U from Definition 7 and compute r(~u2,u2)=(S(~u2)-S(u2))/S(u2). If the average or worst-case r exceeds a small threshold (say 5-10%) on these non-geometric graphs, the greedy algorithm does not approximate the l1 basis even at the first nontrivial frequency and the paper's algorithmic conclusion must be weakened.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is the paper's algorithmic central claim: the greedy basis ~U approximates the l1 basis U for large graphs. The only theoretical link, Theorem 9, shows the greedy partition matrix satisfies the necessary condition of Theorem 4, i.e. dim ker(~U_{k-1}^T M)=1; the authors explicitly note that this makes ~u_k a critical point, not necessarily a local minimum, and no error bound is given. The gap is concrete already at k=2. By Corollary 5, the exact u2 is two-valued. For x=a1_A+b1_{A^c} with zero mean and unit norm, S(x)=sqrt(N) W(A,A^c)/sqrt(|A|(N-|A|)), so u2 is the maximizer of the normalized cut W(A,A^c)/sqrt(|A||B|). The greedy rule (Definition 7, Eq. (18)) instead merges the two groups with largest raw weight W(A,B) at each step, and ~u2 is the final two-group partition produced by that hierarchy. On graphs where the heaviest raw bipartition has unbalanced sizes, or where early max-weight merges trap an off-optimal pair, the two objectives select different cuts and the relative variation error r(~u2,u2) can be large. Figure 4(a) only averages over N<=8 random geometric graphs, so this failure mode is not probed. Thus the practical claim that the greedy basis is a good l1 Fourier basis is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an ℓ1-norm-based graph Fourier basis defined by sequentially minimizing S(x)=∑_{i<j} w_{ij}|x_i-x_j| under orthogonality and unit-norm constraints (Definition 1, Eq. (4)). Its main theoretical result, Theorem 4, proves a necessary condition for local minima: for the k-th minimization, the partition matrix M of a local minimum satisfies dim ker(U^T M)=1, leading to Corollary 5 that the k-th ℓ1 basis vector has at most k distinct values. The paper then introduces a greedy algorithm (Definition 7) that hierarchically merges the two groups with maximum raw mutual weight W(A,B), constructs an orthonormal basis ~U from the resulting partitions (Theorem 8), and shows that this basis satisfies the same dimension condition (Theorem 9), though the paper explicitly notes this makes ~u_k a critical point, not necessarily a local minimum. Numerical experiments for N≤8 random geometric graphs compare the greedy basis to the exactly enumerated ℓ1 basis, and a second experiment compares n-term approximation errors for a simulated signal and a real temperature signal under the greedy and Laplacian bases.","tokens_in":11668,"tokens_out":4026,"duration_ms":44656,"significance":"If the greedy basis provably approximated the ℓ1 Fourier basis, the paper would offer a fast, deterministic alternative to Laplacian eigenvector computation for graph Fourier transforms. The theoretical core—Theorem 4 and Corollary 5—is self-contained and appears mathematically correct: the piecewise-linearization argument and the Lagrange-multiplier step are sound, and the finiteness of critical points (Theorem 6 and the set X_U^*) is a genuine structural insight. Theorem 9 is a useful observation that connects the greedy construction to the necessary condition. The O(N) computation of Fourier coefficients from the greedy tree (Section 4.3, Eqs. (25)-(27)) is a concrete practical advantage, and the n-term approximation experiments on a real temperature signal provide some empirical support. However, the central algorithmic claim—that the greedy basis approximates the ℓ1 basis on large graphs—is not established by any approximation guarantee or error bound, and the numerical evidence is limited to N≤8. This gap is load-bearing for the paper's stated purpose, so the result, while potentially valuable, requires substantial additional support before the central claim can be accepted.","major_comments":[{"comment":"The greedy partition sequence merges the two groups with maximum raw mutual weight W(A,B), but for k=2 the exact ℓ1 basis vector u_2, by Corollary 5 and the zero-mean unit-norm constraint, maximizes the normalized cut W(A,B)/sqrt(|A||B|) (equivalently sqrt(N)W(A,B)/sqrt(|A|(N-|A|))). These two objectives are not equivalent: on graphs where the heaviest raw bipartition is unbalanced in size, or where early max-weight merges trap the hierarchy in an off-optimal pair, the greedy two-group cut can have substantially larger S(~u_2)-S(u_2). Figure 4(a) reports only averages over 100 random geometric graphs with N≤8; it does not probe worst-case or structured graphs, and no error bound is given. Since the abstract and introduction claim that the greedy algorithm 'approximates' the ℓ1 basis, this lack of guarantee leaves the central practical claim unsupported.","section":"§4.2, Definition 7 (Eq. (18))"},{"comment":"Theorem 9 shows only that the greedy partition matrix M satisfies dim ker(~U_{k-1}^T M)=1, which places ~u_k in the critical-point set X^*_{~U_{k-1}}, not among the local minima X^{**}_{~U_{k-1}}. The paper itself states this explicitly. Because the sequential problem (4) is nonconvex (unit-sphere constraint), being a critical point gives no quantitative control over the gap S(~u_k)-S(u_k) to the global minimum; the paper provides no lower or upper bound on this gap, nor any convergence or stability result as N grows. Thus the only theoretical bridge from the greedy construction to the ℓ1 basis is a necessary condition, not an approximation guarantee. This is a load-bearing point for the paper's main claim and needs either a bound or a clearly weakened claim.","section":"§4.2, Theorem 9 and following remark"},{"comment":"The paper emphasizes that the greedy basis transform of a signal costs O(N) multiplications (Eqs. (25)-(27)), but it does not analyze the complexity of constructing the greedy hierarchy itself. In Definition 7, at each of the N-1 merging steps the algorithm must find the pair of current groups with maximum W(A,B); a naive implementation costs O(N^3) or more, and no data structure or amortized bound is given. Since the motivation is that 'computation of Laplacian eigenvectors is expensive when the graph is large,' the total cost of producing the greedy basis is relevant to the 'fast' claim. The absence of any complexity analysis for the construction step means the practical advantage over an eigensolver is not established.","section":"§4.3 and §5"}],"minor_comments":[{"comment":"The sentence 'We obtains a necessary condition' should read 'We obtain a necessary condition.'","section":"§6"},{"comment":"The phrase 'Most results can be generated to the directed case' should be 'generalized' rather than 'generated.'","section":"§2, Remarks"},{"comment":"The caption refers to red and blue lines; if the journal version is printed in grayscale, the distinct line styles should be indicated or labeled directly.","section":"Figure 4 caption"},{"comment":"The observation that r(~U,U) is below zero is interesting but should be discussed more carefully: since each u_k is only sequentially optimal, the sum of variations over the whole basis does not have to be minimized by the ℓ1 basis, so this fact does not contradict the definition.","section":"§5.1, Figure 4(b)"},{"comment":"The simulated signal is generated from its Laplacian-basis coefficients, which may bias the comparison in favor of the Laplacian basis; reporting results for a signal generated from greedy-basis coefficients or from a basis-independent random process would make the comparison more neutral.","section":"§5.2"},{"comment":"Reference [14] (Perraudin et al.) is formatted inconsistently with the other entries; the arXiv identifier and journal/volume information should be corrected.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper's theoretical results (Theorems 4, 6, and Corollary 5) are internally coherent and appear correct; the referee's concern is entirely with the strength of the algorithmic claim. The greedy algorithm is motivated by a plausible hierarchical-clustering heuristic, but the paper provides no approximation guarantee, and the only numerical validation for closeness to the ℓ1 basis is restricted to N≤8. I would be willing to consider a revised version that either (a) provides an error bound for the greedy basis under explicit graph conditions, (b) substantially expands the numerical evaluation to larger graphs with exact or reference ℓ1 solutions where available, or (c) explicitly reframes the contribution as a heuristic fast transform with empirical support rather than an approximant to the ℓ1 basis. The k=2 failure mode identified in the main review is a concrete test case that the revised version should address."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's real contribution is Theorem 4 / Corollary 5: the k-th vector in a sequential l1-variation-minimizing orthonormal basis must have at most k distinct values. The proof is correct, and this is a genuinely new necessary condition for a natural but hard problem. The finiteness of the critical set (around Theorem 6) is a nice byproduct. That part is worth knowing.\n\nThe rest of the paper is a greedy algorithm to approximate the l1 basis, and the evidence here is weaker than the claims. The algorithm merges groups with largest raw mutual weight and builds an orthonormal basis from the resulting hierarchy. Theorem 9 shows only that each greedy vector is a critical point of the relevant problem; the authors admit in the text that it need not be a local minimum. No error bound connects the greedy basis to the true l1 basis. Experiments are limited to N<=8 random geometric graphs, which do not probe failure modes like unbalanced clusters. For k=2, the exact u2 maximizes the normalized cut W(A,B)/sqrt(|A||B|), while the greedy partition comes from raw-weight merges. Those objectives differ, and a small relative variation error for small random graphs does not imply the greedy basis is close on larger or different graphs. The paper also skips any complexity analysis for building the greedy hierarchy (the O(N) transform applies only once the tree is known), and it does not compare against Sardellitti et al.'s SOC/PAMAL algorithms.\n\nSo the theoretical core is solid, but the central practical claim that the greedy basis is a good l1 Fourier basis is not backed by a proof or adequate experiments. I would still send this to peer review because the necessary condition is a real result and the algorithmic question matters, but the current version needs substantial revision, ideally with a study of where the raw-weight merge rule diverges from normalized cuts and a more convincing validation on larger, structured graphs.","headline":"A correct and clean necessary condition for an l1 graph Fourier basis, but the greedy algorithm's core claim is supported only by small-N experiments and has no approximation guarantee.","tokens_in":12172,"tokens_out":3145,"would_cite":false,"duration_ms":34110,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A12","05C50","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper defines an ℓ1-norm graph Fourier basis and proves its local minima have at most k distinct values, with a fast greedy basis.","keywords":["graph signal processing","graph Fourier transform","ℓ1 norm variation","greedy algorithm","orthogonal basis","signal variation","piecewise representation","network data analysis"],"falsifier":"Compute the exact global $\\ell_1$ basis for a connected weighted graph with nine or ten vertices, or for a known graph family, and compare the total $\\ell_1$ variation $S(\\tilde U)$ with $S(U)$; if the relative error is not small or grows with $N$, the greedy basis is not a reliable approximation. More directly, find a weighted graph on which some greedy basis vector $\\tilde u_k$ does not attain the minimum of $S$ over the sphere orthogonal to the earlier greedy vectors.","tokens_in":11149,"feed_emoji":"📉","tokens_out":5722,"duration_ms":51440,"temperature":0.7,"pith_summary":"The paper proposes a new definition of the graph Fourier transform whose basis vectors minimize $\\ell_1$ norm signal variation instead of the $\\ell_2$ variation that defines Laplacian eigenvectors. The central theoretical result is a necessary condition: at any local minimum of the $k$-th variation-minimization problem, the vector's entries take at most $k$ distinct values, so the $\\ell_1$ basis orders graph frequencies from low to high just as Laplacian eigenvalues do. The paper then replaces the expensive continuous problem with a greedy partition algorithm that merges the two groups of vertices with largest mutual weight at each step, producing an orthonormal basis whose Fourier coefficients are computable in $O(N)$ time. Numerical experiments on graphs with up to eight vertices show the greedy basis has total $\\ell_1$ variation close to the exact $\\ell_1$ basis, and on simulated and real temperature signals its $n$-term approximation error decays at nearly the same rate as the Laplacian basis.","feed_headline":"Graph Fourier transform gets a fast greedy ℓ1 basis","feed_subtitle":"Each k-th basis vector takes at most k distinct values; the tree-based transform runs in O(N) time.","key_machinery":"The load-bearing object is the piecewise representation $x=Ma$: every signal is written as a sum of indicator vectors of the distinct-value sets, so the $\\ell_1$ variation $S(x)$ becomes a locally linear function $f^{\\top}a$ with coefficients $f_i = \\sum_{j<i}W(A_i,A_j) - \\sum_{j>i}W(A_i,A_j)$. The necessary condition $\\dim\\ker(U^{\\top}M)=1$ is derived by linearizing $S$ around a local minimum and applying Lagrange multipliers on the sphere; it implies each local minimum is isolated and the search reduces to finitely many partition matrices. The greedy construction uses the partition sequence $\\tau_k$ defined by $W(A,B)=\\sum_{i\\in A, j\\in B} w_{ij}$, picking the pair with maximum mutual weight to merge, which yields a binary tree and an orthonormal basis with a fast $O(N)$ transform.","core_discovery":"The paper's central claim is that the $\\ell_1$ Fourier basis, defined by solving the sequence of problems (4), has a rigid combinatorial structure. Theorem 4 proves that if $x$ is a local minimum with piecewise representation $x=Ma$, where $M$ is the partition matrix, then $\\dim\\ker(U^{\\top}M)=1$; Corollary 5 then gives the $k$-th basis vector at most $k$ distinct component values. The paper further constructs the greedy basis $\\tilde U$ from a partition sequence that repeatedly merges the two existing groups with the largest mutual weight, proves in Theorems 8 and 9 that this basis is orthonormal and that each greedy vector is a critical point of the corresponding $\\ell_1$ problem, and presents experiments suggesting that the greedy basis is a good approximation to the exact $\\ell_1$ basis for $N\\le 8$ and has approximation decay comparable to the Laplacian basis.","pith_inferences":["The greedy merge rule is a one-pass hierarchical clustering of the graph by maximum mutual weight; one could test whether replacing the single merge criterion with a look-ahead or global-cut objective improves the basis for graphs with many vertices.","The necessary condition is not sufficient, so some critical points may have larger variation than the global minimum; a local-search step over nearby partitions might refine the greedy basis without losing its $O(N)$ transform.","The same piecewise-linear analysis should extend to the directed $\\ell_1$ variation $\\tilde S(x)=\\sum w_{ij}(x_i-x_j)_+$, giving a directed greedy basis; the paper states the extension is straightforward but does not prove it.","On large graphs, comparing the greedy basis's $n$-term approximation to wavelet or frame-based graph transforms would clarify where its fast $O(N)$ transform wins or loses against other sparse representations."],"forward_implications":["For small graphs ($N\\le 8$) the exact $\\ell_1$ Fourier basis can be obtained by enumerating the finite set $X^*_U$ of critical partition matrices, turning a continuous nonconvex problem into a discrete one.","The greedy basis transform costs $O(N)$ multiplications via the binary tree of merged groups, versus $O(N^2)$ for a dense Laplacian-basis transform, so it offers a faster spectral analysis for large graphs.","Because each greedy basis vector satisfies the same kernel-dimension condition as local minima, the greedy basis is a legitimate 'critical point' candidate for the $\\ell_1$ problem, not an arbitrary heuristic.","The at-most-$k$-values property gives a frequency interpretation: as $k$ grows the basis vectors can take more distinct values, so the basis orders signals from slowly varying to rapidly oscillating.","In the reported experiments the $n$-term approximation error of the greedy basis decays at nearly the same rate as the Laplacian basis, supporting use of the greedy basis in compression and denoising."],"supporting_citations":[{"why":"Supplies the spectral graph theory background and the Laplacian eigenvector basis against which the $\\ell_1$ basis is defined and compared.","marker":"[1]"},{"why":"Motivates the problem by introducing graph signals and the need for a graph Fourier transform.","marker":"[2]"},{"why":"Gives the directed variation functional and the earlier directed graph Fourier basis that motivates the $\\ell_1$ approach.","marker":"[3]"},{"why":"Provide iterative algorithms for orthogonality-constrained nonconvex problems, cited as the reason global minima are generally hard to obtain.","marker":"[12, 13]"},{"why":"Provides the Swiss temperature dataset used in the real-signal $n$-term approximation experiment.","marker":"[15]"}],"fun_headline_variants":["ℓ1 graph Fourier basis: greedy, fast, and piecewise constant","O(N) graph Fourier transform via ℓ1 greedy basis","ℓ1 variation min gives piecewise-constant Fourier basis","Greedy ℓ1 Fourier basis: at most k distinct values per k-th vector"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The greedy merge rule is assumed to produce a basis close to the true $\\ell_1$ Fourier basis on large graphs, but the paper tests this only by exhaustive search for graphs with at most eight vertices and gives no error bound.","fun_headline_variants_meta":{"raw":{"variants":["ℓ1 graph Fourier basis: greedy, fast, and piecewise constant","O(N) graph Fourier transform via ℓ1 greedy basis","ℓ1 variation min gives piecewise-constant Fourier basis","Greedy ℓ1 Fourier basis: at most k distinct values per k-th vector"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000569,"raw_usage":{"total_tokens":2659,"prompt_tokens":875,"completion_tokens":1784,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":491,"completion_tokens_details":{"reasoning_tokens":1706}},"tokens_in":491,"tokens_out":1784,"duration_ms":12508,"temperature":1.0,"reasoning_tokens":1706,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:37:36.797731+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the exact global $\\ell_1$ basis for a connected weighted graph with nine or ten vertices, or for a known graph family, and compare the total $\\ell_1$ variation $S(\\tilde U)$ with $S(U)$; if the relative error is not small or grows with $N$, the greedy basis is not a reliable approximation. More directly, find a weighted graph on which some greedy basis vector $\\tilde u_k$ does not attain the minimum of $S$ over the sphere orthogonal to the earlier greedy vectors.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the spectral graph theory background and the Laplacian eigenvector basis against which the $\\ell_1$ basis is defined and compared."},{"cited_title":"The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains","cited_arxiv_id":null,"evidence_quote":"Motivates the problem by introducing graph signals and the need for a graph Fourier transform."},{"cited_title":"On the graph fourier transform for directed graphs","cited_arxiv_id":null,"evidence_quote":"Gives the directed variation functional and the earlier directed graph Fourier basis that motivates the $\\ell_1$ approach."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Swiss temperature dataset used in the real-signal $n$-term approximation experiment."}],"review_version":1}