{"id":"b81e3dd0-ba38-46a9-8bf3-254ee128a49f","arxiv_id":"2509.10874","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For linearized graph convolutional networks, the paper derives an exact expression for classification loss under partial noisy observations and uses it to design a greedy sampling scheme that can beat both random and reconstruction-optimal sampling.","lead":"This paper shows how classification error depends on which nodes are sampled when graph signals are noisy and incomplete, and it derives sampling rules aimed at classification instead of reconstruction. The main result is an exact formula for the error of a linearized graph neural network, along with evidence that reconstruction-optimal sampling can be worse than random sampling for classification.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is internally sound, but the proof of Corollary 1.1 contains a dimensionally wrong expansion of the node output error; the triangle relationship as stated does not follow and needs correction.","rationale":"I read Theorem 1 as the central claim. The Gaussian covariance computation in the proof checks out: f(X)_i and f(hat X)_i are zero-mean jointly Gaussian for fixed S, and the correlation formula follows from Lemma 1. So I cannot identify a flaw in the headline theorem. The load-bearing soft spot is an auxiliary theorem, Corollary 1.1, which the paper uses to compare classification and reconstruction error. Its proof expands the node output error incorrectly; this is an internal inconsistency, not merely a modeling assumption. This justifies the reader's CONDITIONAL verdict: the core theorem can stand, but the stated comparison result must be corrected before the paper is accepted. The model-assumption issue (known Gaussian Sigma and known linear f) is real but is explicitly stated in Section II-D; it limits applicability rather than invalidating the derivation. The reader's weakest_assumption focused on that explicit modeling condition, while the concrete mathematical error in Corollary 1.1 was noted in the reader's rationale but not made the primary concern; hence partial agreement.","tokens_in":8992,"tokens_out":27942,"duration_ms":239021,"concrete_test":"Re-derive the expansion in Corollary 1.1 from Theorem 1: let a = f(X)_i and b = f(hat X)_i, and compute E[(a−b)^2] = Var(a) + Var(b) − 2Cov(a,b) using definitions (9)–(12). Verify that Error_out,i = σ_i^2 + ν_i^2 − 2ρ_i σ_i ν_i and that the factor d does not appear. Then recheck Fig. 2: with side sqrt(Error_out,i / d), the law of cosines requires Error_out,i = d(σ_i^2 + ν_i^2 − 2ρ_i σ_i ν_i), not the printed expression. If the printed expression is used, the triangle is invalid unless σ_i = ν_i = 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Corollary 1.1's proof states Error_out,i = d·((σ_i(G))^2 + (ν_i(G))^2 − 2ρ_i(G)). Direct expansion from Theorem 1's own definitions gives E[(f(X)_i − f(hat X)_i)^2]/||w||^2 = σ_i(G)^2 + ν_i(G)^2 − 2ρ_i(G)σ_i(G)ν_i(G). The written version drops the σ_iν_i factor on the cross term and introduces a spurious factor d; ρ_i(G) is a dimensionless correlation, so the term 2ρ_i cannot have variance units unless σ_i = ν_i = 1. Consequently, the law-of-cosines statement in Fig. 2 does not follow as written, and the claim that these quantities always form a valid triangle is not proved. The inequality (14) is unaffected, and Theorem 1 is unaffected, but Corollary 1.1 is a stated result of the paper and needs correction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies graph signal sampling and reconstruction when the downstream task is binary node classification rather than reconstruction. The authors assume zero-mean Gaussian graph features with known covariance, linear reconstruction operators such as least-squares or feature propagation, and labels generated by a known linear function f(X)=GXw (a linearized GCN). Their main result (Theorem 1) gives an exact closed form for the expected classification loss—summed per-node misclassification probabilities—as (1/pi) arccos(rho_i(G)), where rho_i(G) is the correlation between the clean and reconstructed outputs at node i. Corollary 1.1 relates the corresponding output error to the classical reconstruction loss by an inequality and a claimed triangle relation. The paper then proposes a greedy sample selection scheme that directly minimizes the classification loss and compares it with random sampling and reconstruction-optimal (A-optimal) sampling on synthetic graphs and an FMRI dataset, finding that reconstruction-optimal sampling can underperform random sampling for classification.","tokens_in":9154,"tokens_out":18807,"duration_ms":158047,"significance":"Provided Theorem 1 is correct, this is a valuable contribution: it gives an exact, parameter-free characterization of how partial noisy observations affect a downstream linearized-GCN classifier, without running the classifier, and it applies to several reconstruction methods. The derivation is clean and internally consistent, and the assumptions are stated explicitly. The analytic curves in Figs. 3-6 are falsifiable predictions in the stated Gaussian model, and the empirical validation on synthetic data matches the analytic formula. The paper also makes a useful conceptual point that reconstruction loss and classification loss are different and can lead to very different sampling choices, and it supports this claim experimentally. However, the currently stated Corollary 1.1 contains mathematical errors, the 'optimal' sampling claim is stronger than what is proved, and the real-data experiment omits the specification of the label function f; these issues need correction before the paper is publishable.","major_comments":[{"comment":"The stated expression for Error_out,i is incorrect. Using the definitions in Theorem 1, E[(f(X)_i - f(hat X)_i)^2]/||w||^2 = (sigma_i(G))^2 + (nu_i(G))^2 - 2 c_i(G) = (sigma_i(G))^2 + (nu_i(G))^2 - 2 rho_i(G) sigma_i(G) nu_i(G). The proof's formula d*((sigma_i(G))^2 + (nu_i(G))^2 - 2 rho_i(G)) both introduces a spurious factor d (the output f(X)_i is scalar even when d>1) and drops the sigma_i nu_i factor on the cross term; since rho_i is dimensionless, the written expression is not dimensionally consistent and can be negative. Thus the triangle in Fig. 2 does not follow as stated. In addition, the proof's claim that rho_i(G) is the misclassification probability is false: rho_i(G) is the correlation coefficient, and Theorem 1 gives the misclassification probability as arccos(rho_i(G))/pi. The corrected relationship is a triangle with sides sigma_i(G), nu_i(G), and sqrt(Error_out,i), with the angle opposite sqrt(Error_out,i) equal to arccos(rho_i(G)); the misclassification probability is that angle divided by pi. Inequality (14) and Theorem 1 are unaffected, but Corollary 1.1 and Fig. 2 need to be revised.","section":"III-B, Corollary 1.1 and Fig. 2"},{"comment":"The paper repeatedly calls the proposed sample-selection procedure 'optimal' (Abstract: 'derive new optimal sampling methods'; Section III-C: 'minimising mean classification loss'). What is actually proposed in Section III-C is greedy minimization of the set function in Eq. (6). No optimality, near-optimality, or approximation guarantee is provided for this greedy scheme, and the submodularity/supermodularity properties that underlie known guarantees for reconstruction-based objectives are not established for Eq. (6). Please either add an analysis of the greedy procedure or qualify the language to 'task-specific greedy sampling' / 'greedy sampling for the classification objective.' The greedy algorithm itself and its computational cost should also be described.","section":"Abstract and III-C"},{"comment":"The real-world FMRI experiment is underspecified with respect to the label function f. Theorem 1 applies only when f(X)=GXw with a known G and w. Section IV-A4 constructs binary labels from the mean-subtracted signals, and Section IV-A5 states assumptions on the feature covariance and SNR, but it never states which G and w are used to compute the classification loss that the sampling schemes optimize. Without this, the experiment is not reproducible and it is not possible to verify that the analytic classification loss is being computed correctly. Please specify f (e.g., G=I and w equal to the averaging vector if labels are signs of the average signal, or a particular linearized GCN) and state the resulting C for the FMRI dataset.","section":"IV-A4-A5, Fig. 7"}],"minor_comments":[{"comment":"The notation sigma_i is overloaded: in Theorem 1, sigma_i(M) is a standard deviation via (sigma_i(M))^2, but the interpretive paragraph after Theorem 1 treats sigma_i as a variance in expressions such as sqrt(c_i/sigma_i). Please make the notation consistent throughout.","section":"III-A"},{"comment":"The proof divides by sqrt(1-rho^2), so the edge cases rho = +/-1 should be handled separately or by a limiting argument.","section":"Lemma 1, proof"},{"comment":"In the definition of Error_out,i, the quantity (f(X))_i is a scalar, so the use of ||.||_2 is unnecessary and may confuse readers; please clarify that this is the squared scalar difference.","section":"Eq. (13)"},{"comment":"The caption text 'Error_out,i * d^{-1}' is ambiguous; after correcting Corollary 1.1, please redraw the triangle and explicitly identify which side is sqrt(Error_out,i) and which angle is arccos(rho_i(G)).","section":"Fig. 2"},{"comment":"No error bars or number of Monte Carlo trials are reported, so the statement that the empirical and analytic losses 'largely agree' is not quantified; please add this information.","section":"IV-B"}],"recommendation":"major_revision","confidential_remarks":"The central theorem appears sound and the paper fits the scope of the journal; the main concerns are the incorrect Corollary 1.1/Fig. 2, the overclaimed optimality of the sampling heuristic, and the underspecified FMRI experiment. All appear addressable in revision, and I do not see a reason to doubt the core contribution. I would be willing to review a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a solid paper with one genuinely new result and one clear error in a stated corollary that the authors need to fix. Theorem 1, the exact expression for classification loss as a sum of arccos of per-node correlations, is derived cleanly from a standard Gaussian fact. The covariance computations check out, no fitted parameters enter the loss formula, and the synthetic experiments broadly confirm the analytic curves. That alone is worth a serious referee.\n\nWhat's new: the paper gives the first systematic theoretical treatment I know of for sampling with a downstream classification objective rather than reconstruction error, and it shows a surprising practical point: reconstruction-optimal (A-optimal) sampling can be beaten by random sampling on classification loss. The greedy classification-optimal sampler is a natural application, and the comparisons are plausible.\n\nWhere it gets soft: the proof of Corollary 1.1 is wrong as written. The expansion for Error_out,i should read sigma_i(G)^2 + nu_i(G)^2 - 2 rho_i(G) sigma_i(G) nu_i(G), not d*(sigma^2 + nu^2 - 2 rho). The dropped sigma*nu factor and the spurious d make the displayed formula dimensionally inconsistent, since rho is dimensionless. The 'triangle' in Fig. 2 therefore does not follow from the stated expansion, and the sentence in the proof calling rho_i(G) 'the probability of misclassification' is a misstatement (the probability is arccos(rho)/pi). Inequality (14) is unaffected, and Theorem 1 is unaffected; this is a contained error, but it is in a stated result and has to be fixed.\n\nOther, smaller soft spots: the abstract says 'optimal sampling methods' but the greedy scheme has no optimality guarantee; experiments report no error bars or significance tests; and the FMRI experiment depends on assumed covariance and noise level, so the real-world evidence is suggestive, not strong. None of these undercut the main theorem.\n\nThe Gaussian-feature and linear-label assumptions are restrictive, but they are stated up front and are the standard price for an exact closed form. The citation pattern looks fine; the self-citation to [32] is background context.\n\nBottom line: this deserves peer review. Send it out, and ask for a corrected Corollary 1.1 proof (and ideally error bars) before acceptance.","headline":"The classification-loss formula for linearized GCNs is a genuine new result, but Corollary 1.1 has a dimensional error in the stated proof and needs a correct rewrite before this is publishable.","tokens_in":9694,"tokens_out":2254,"would_cite":true,"duration_ms":18853,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For noisy partial observations of graph signals, the expected classification loss of a linearized graph convolutional network equals a sum of arc-cosine correlations, and this identity can be used to design sampling that minimizes…","keywords":["graph signal processing","sampling","reconstruction","classification loss","graph convolutional networks","Gaussian features","node classification","feature propagation"],"falsifier":"Take a real graph dataset whose features are visibly non-Gaussian (for example heavy-tailed fMRI signals or discrete attributes), fix a sample set, fit $G$ and $w$, and compare the closed-form prediction $\\sum_i \\frac{1}{\\pi}\\arccos(\\rho_i(G))$ to the empirical misclassification rate of the linearized GCN over many noise draws; a substantial systematic gap would show the Gaussian assumption is necessary, not incidental.","tokens_in":8743,"feed_emoji":"📊","tokens_out":9055,"duration_ms":63536,"temperature":0.7,"pith_summary":"Most graph signal processing work chooses where to sample nodes by minimizing how well the unobserved signal is reconstructed, even when the actual task is node classification. This paper asks whether that mismatch matters and shows it does: for binary classification with a linearized graph convolutional network whose labels are generated by $f(X)=GXw$ and whose features are jointly Gaussian, the per-node misclassification probability is exactly $\\frac{1}{\\pi}\\arccos$ of the correlation between the clean and reconstructed outputs. The paper proves this identity, uses it to build a greedy sampling scheme that directly minimizes classification loss, and reports that reconstruction-optimal sampling can underperform random sampling when judged by classification error. A sympathetic reader takes away a closed-form language for task-aware sampling on graphs, one in which the downstream loss, not the reconstruction loss, becomes the objective.","feed_headline":"For noisy graphs, classification loss is a sum of arc-cosine terms","feed_subtitle":"A new formula lets sampling be chosen to minimize classification error instead of reconstruction error.","key_machinery":"The load-bearing identity is Lemma 1, $P(\\operatorname{sign}(X)\\neq\\operatorname{sign}(Y)) = \\arccos(\\rho)/\\pi$ for zero-mean jointly Gaussian $(X,Y)$ with correlation $\\rho$. Theorem 1 extends it node-by-node: because $f(X)=GXw$ and $f(\\hat{X})$ are linear transformations of jointly Gaussian features, each pair $(f(X)_i, f(\\hat{X})_i)$ inherits joint Gaussianity, and the node's misclassification probability is exactly the arc-cosine of the correlation $\\rho_i(G)$. This correlation is the object that couples the graph filter $G$, the feature covariance, the sampling set $S$, the reconstruction operator $R_S$, and the noise level, and it is what allows classification loss to be optimized directly without running the classifier.","core_discovery":"The central object is Theorem 1. Under zero-mean jointly Gaussian feature columns with covariance $\\Sigma$ and labels $\\operatorname{sign}(f(X))$ with $f(X)=GXw$, the classification loss over sample set $S$ equals $\\sum_{i\\in V} \\frac{1}{\\pi}\\arccos(\\rho_i(G))$, where $\\rho_i(G)$ is the correlation between the clean output $f(X)_i$ and the reconstructed output $f(\\hat{X})_i$ built from noisy observations on $S$. The proof hinges on Lemma 1: two zero-mean jointly Gaussian scalars with correlation $\\rho$ have opposite signs with probability $\\arccos(\\rho)/\\pi$, which follows from rotational invariance of the standard bivariate Gaussian. Since both outputs are linear functions of the Gaussian features, their correlation is computable from $G$, the reconstruction operator $R_S$, the covariance of $Xw$, and the noise variance $\\eta^2$. The same correlation geometry gives a reconstruction-loss formula for scalar features and, for graph filters $G$ that are polynomials of the normalized augmented adjacency matrix, a bound in which reconstruction loss controls the summed normalized output error through $\\|G\\|^2$.","pith_inferences":["The same arc-cosine correlation mechanism should apply to any linear reconstruction operator whose output covariance can be written down; least-squares and feature propagation are the two worked examples, but the identity is not tied to them.","A natural plug-in extension would replace the Gaussian covariance with an empirical covariance estimated from data and use the same formula as an approximate classification-loss estimator; agreement on real data would show the identity is robust beyond its exact assumptions.","Because classification loss depends on correlations of clean versus reconstructed outputs, nodes where reconstruction is most uncertain (small correlation, large angle in the error triangle) are the natural targets for sampling, a principle that could transfer to active learning on graphs.","The triangle relation between output error, per-node variances, and misclassification probability suggests a geometric view of task-aware sampling: the sampling set should be chosen to shrink the angle, not just the magnitude, of the output error vector."],"forward_implications":["For any sample set $S$, the expected classification loss of a linearized GCN can be computed in closed form from the graph filter, feature covariance, and noise level, without Monte Carlo simulation or running the classifier.","Greedy sample selection can be driven by the true classification objective rather than by a reconstruction proxy; the paper derives such a scheme and shows it beats random and reconstruction-optimal sampling in synthetic and real-data experiments.","Reconstruction-optimal sampling can be worse than random sampling for classification, so the common practice of using reconstruction loss as a proxy is not harmless.","For polynomial graph filters with independent feature columns, the classification loss does not depend on the weight vector $w$, only on the filter's depth and the covariance model.","Reconstruction loss upper-bounds the summed normalized output error, but the nonlinear angle-to-error geometry shows that optimizing reconstruction loss is a poor proxy for per-node misclassification."],"supporting_citations":[{"why":"Supplies the bandlimited smooth-signal covariance model and the reconstruction-loss analysis that the problem setting and the $d=1$ loss formula build on.","marker":"[32]"},{"why":"Identifies $f(X)=p(\\tilde{A}_\\gamma)Xw$ with linearized graph convolutional networks and gives the $\\|\\tilde{A}_\\gamma\\|\\le 1$ bound used to upper-bound normalized output error by reconstruction loss.","marker":"[34]"},{"why":"Defines the feature propagation reconstruction operator treated as a second linear reconstruction method in Theorem 1 and in the experiments.","marker":"[29]"}],"fun_headline_variants":["Sample graphs to minimize classification loss, not reconstruction","Classification error on graphs: a sum of arccosines","New formula: pick samples to cut graph classification error","For noisy graphs, classification loss = arccosine sum","Optimal sampling for graph classification: error formula"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The features $X$ are jointly Gaussian with known covariance (for example bandlimited), and the labels are generated by a known linear map $f(X)=GXw$; if the real feature distribution or label function departs from this, the exact classification-loss formula and the sampling scheme built on it lose their theoretical guarantee.","fun_headline_variants_meta":{"raw":{"variants":["Sample graphs to minimize classification loss, not reconstruction","Classification error on graphs: a sum of arccosines","New formula: pick samples to cut graph classification error","For noisy graphs, classification loss = arccosine sum","Optimal sampling for graph classification: error formula"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000568,"raw_usage":{"total_tokens":2634,"prompt_tokens":838,"completion_tokens":1796,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":454,"completion_tokens_details":{"reasoning_tokens":1719}},"tokens_in":454,"tokens_out":1796,"duration_ms":357951,"temperature":1.0,"reasoning_tokens":1719,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:52:14.167891+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a real graph dataset whose features are visibly non-Gaussian (for example heavy-tailed fMRI signals or discrete attributes), fix a sample set, fit $G$ and $w$, and compare the closed-form prediction $\\sum_i \\frac{1}{\\pi}\\arccos(\\rho_i(G))$ to the empirical misclassification rate of the linearized GCN over many noise draws; a substantial systematic gap would show the Gaussian assumption is necessary, not incidental.","supporting_citations":[{"cited_title":"On the impact of sample size in reconstructing noisy graph signals: A theoretical characterisation,","cited_arxiv_id":null,"evidence_quote":"Supplies the bandlimited smooth-signal covariance model and the reconstruction-loss analysis that the problem setting and the $d=1$ loss formula build on."}],"review_version":2}