{"id":"74380550-b5e3-4b9a-8ba6-f973a8192443","arxiv_id":"2412.13842","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"SGBGC compresses graphs by grouping same-label nodes into granular-balls and training GNNs on the coarsened graph, but its evaluation leaks test labels into the coarsening step.","lead":"This paper proposes a graph compression method that groups same-label nodes into clusters called granular-balls, then trains a graph neural network on the smaller cluster graph. The authors claim up to 20x compression without losing accuracy, but their evaluation uses all node labels, including test labels, when forming the clusters.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The coarsening algorithm uses the full label vector, including the 20% test split, to build both the partition and the training target; the reported accuracy gains therefore do not measure coarsening quality.","rationale":"I identify the same load-bearing concern as the reader: the empirical central claim is invalidated by test-label leakage. The evidence is in the algorithms themselves. Algorithm 3's input is 'labels Y', and its steps use Y to choose initial centers per label category and to split until purity T=1; this makes the entire coarsened graph a function of all node labels. Algorithm 1 then uses the same partition to compute \\tilde{Y}=argmax(PY) and trains the GNN on that target. With a 60/20/20 split, the 20% test labels therefore enter both the graph structure used for training and the supervised training signal. This is not a subtle evaluation bias; it is direct use of the test set labels and makes the accuracy comparisons against unsupervised baselines (VNGC, VEGC, JCGC, GSGC) and training-only baselines (GCOND, FGC, CMGC) unfair. I considered alternative concerns. The theoretical Theorem 1 is indeed circular because it assumes Lgb≈L and P^TP≈I, which is essentially the conclusion; a reader could reject the theory section on that basis. The fixed-ratio results also lack a described mechanism for matching a target coarsening ratio. However, neither of these is as load-bearing as the leakage: even a perfectly reproduced and theoretically sound version would still fail to establish the central claim if test labels are used during coarsening. The manuscript itself contains passages that support this reading, including the statement in the training details that 'our coarsening method relies heavily on label information' and that full-supervised classification is 'essential' - an implicit admission that the full label vector drives the method. Because the central empirical claim rests on this leakage, the REJECT verdict stands unchanged. I see no need to soften or strengthen the reader's verdict.","tokens_in":21155,"tokens_out":6016,"duration_ms":53981,"concrete_test":"Reproduce Table 1 with the same 60/20/20 splits, but mask the test labels before running Algorithm 3: pass only Y_train ∪ Y_val to SGBGC, hold out the 20% test nodes during center selection and purity-based splitting, assign them to the nearest granular-ball after the partition is built, and train exactly as in Algorithm 1. Compare Cora/Citeseer at r=0.1 and Co-CS/Co-Phy at r=0.05 to the reported entries (82.99/73.69 and 91.21/95.61). A material drop (e.g., more than 3-5 points) or a collapse of the Co-CS/Co-Phy advantage would confirm that test labels, not coarsening quality, drive the headline results.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing concern is direct label leakage in the coarsening pipeline. Algorithm 3 takes the full label vector Y as input and uses labels twice: initial centers are chosen 'within each label category' (Step 3), and splitting continues until every granular-ball reaches purity T=1 (Steps 8-11), so the partition of the graph is a function of the true labels of every node. Algorithm 1 then derives the training target on the coarsened graph as \\tilde{Y}=argmax(PY) (Step 4), with the same P built using test labels, so the GNN is trained on super-node labels that aggregate the 20% test labels. The experiments use a 60/20/20 'full-supervised' split for all five datasets. No baseline enjoys this advantage: VNGC, VEGC, JCGC, and GSGC are unsupervised, and GCOND, FGC, and CMGC are trained only on labeled training nodes. Consequently, the reported accuracy at r=0.1-0.05, including the headline 'up to 20 times without compromising test accuracy' and the SOTA claims on Co-CS/Co-Phy (e.g., 91.21% at r=0.05), measures how much information the test labels inject into the coarsened graph, not the quality of coarsening. The method might still be useful in a properly supervised setting, but the empirical case in this version is invalidated. Secondary weaknesses - Theorem 1 assumes Lgb≈L and P^TP≈I, and the fixed-ratio experiments are not reproducible from the adaptive algorithm - reinforce but do not replace this concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes Supervised Granular-Ball Graph Coarsening (SGBGC), a preprocessing method that partitions a graph into granular-balls using node labels and structural connectivity, aggregates node features and labels per ball, and then trains a GNN on the coarsened graph. The method is intended to be adaptive, requiring no preset coarsening ratio, and is evaluated on Cora, Citeseer, Pubmed, Co-CS, and Co-Phy against unsupervised and learned coarsening baselines, including a noise-robustness study and runtime/memory measurements. The paper's central claims are that SGBGC achieves accuracy comparable to full-graph training at coarsening ratios as low as 0.05 and state-of-the-art results on five benchmark datasets.","tokens_in":21471,"tokens_out":5389,"duration_ms":46774,"significance":"If the empirical claims were valid, SGBGC would be a practically attractive preprocessing method: it is fast, adaptive, and appears to give large compression without accuracy loss. The paper includes a broad comparison across many baselines, runtime and memory measurements, a robustness study, and a public code link. However, the evaluation as presented cannot support these claims. The coarsening algorithm consumes the full label vector, including test labels, so the reported accuracy gains are confounded by label leakage; the theoretical guarantee is an assumption restatement rather than a proof; and the procedure used for the fixed-ratio experiments in Table 1 is not documented. These issues affect the central claims, so the contribution in its current form is not acceptable.","major_comments":[{"comment":"Test-label leakage invalidates the experimental comparison. Algorithm 3 takes the full label vector Y as input and uses it in Step 3 (initial centers are chosen 'within each label category') and in Steps 8-11 (splitting continues until purity T=1), so the partition P is a function of every node's true label, including the 20% test split in the 60/20/20 'full-supervised' splits. Algorithm 1 then builds the training target \\tilde{Y}=argmax(PY) from this same P. The unsupervised baselines VNGC/VEGC/JCGC/GSGC do not use test labels to construct the coarsened graph, and the learned baselines GCOND/FGC/CMGC are trained only on labeled training nodes. Consequently, the accuracies reported in Table 1 and the abstract's 'up to 20 times without compromising test accuracy' claim measure information injected by test labels rather than coarsening quality; the same concern applies to the noise-robustness tables, where the noisy labels of all nodes, including test nodes, are used during coarsening.","section":"Algorithms 1 and 3; Experimental Setup / Training details"},{"comment":"Theorem 1 is circular and does not provide a spectral-preservation guarantee. The proof assumes P^T P \\approx I and L_gb \\approx L, but L_gb is defined as L_gb = P^T L P in Eq. (22), so assuming L_gb \\approx L is essentially equivalent to assuming the very property the theorem claims to establish. The additional approximation PL_gb P^T \\approx L in Eq. (32) is asserted without derivation, and no argument is given for why the granular-ball construction makes P approximately orthogonal or L_gb close to L. Thus the theorem does not support the method's central theoretical claim.","section":"Theoretical Foundations, Theorem 1 and proof"},{"comment":"The fixed-ratio experiments in Table 1 are not reproducible from the algorithm as described. Algorithm 3 splits adaptively until purity T=1 and has no coarsening-ratio parameter, yet Table 1 reports SGBGC results at r=0.5, 0.3, 0.1, and 0.05. The text states that other methods 'followed the adaptive coarsening ratio r achieved by SGBGC,' but it never specifies how SGBGC itself is forced to produce a target ratio, how the ratio is computed after isolated nodes are removed, or whether the fixed-ratio results come from thresholding the adaptive process. Without this procedure, the main comparison table cannot be reproduced and the claimed distinction between adaptive and fixed-ratio operation is unclear.","section":"Table 1 and Algorithm 3; Training details"}],"minor_comments":[{"comment":"The pseudocode says the two centers are chosen to 'maximize the diversity of labels,' but the surrounding text and Equations (6)-(8) specify that the centers are the two highest-degree nodes and assignment is by shortest path; these two descriptions are inconsistent and should be reconciled.","section":"Algorithm 3, Step 8 vs Equations (6)-(8)"},{"comment":"The sentence 'During the coarsening process, unlabelled isolated nodes were removed from the training and validation sets' is unclear, because the 60/20/20 split labels every node; if isolated nodes are indeed removed, the reported ratios r and accuracy values are computed on different node sets and need explicit explanation.","section":"Training details"},{"comment":"The claim of reducing graph size 'up to 20 times' is not tied to a specific dataset or protocol; Table 1 reports r=0.05 for Pubmed, Co-CS, and Co-Phy only, while Cora and Citeseer are not evaluated at that ratio, so the scope of the headline claim should be stated precisely.","section":"Abstract and Conclusion"},{"comment":"The Related Work section appears twice, once before 'Theoretical Foundations' and once after the reference list with a truncated GNN subsection; this duplication appears to be a formatting error and should be corrected.","section":"Appendix structure"},{"comment":"In Algorithm 3, the set GB_s is initialized as {\\emptyset} and the loop over GB_init only adds a granular-ball to GB_s when splitting stops; it is not clear whether the initial granular-balls that do not satisfy the purity condition are ever added to the returned set, and the pseudocode should be made unambiguous.","section":"Algorithm 3"}],"recommendation":"reject","confidential_remarks":"The decisive issue for rejection is the test-label leakage in the coarsening pipeline; this is not a stylistic or presentation concern but a flaw in the central empirical claim. If the authors can rerun the experiments with coarsening restricted to training labels and document the fixed-ratio protocol, a future submission addressing these points could be reconsidered. The paper may also benefit from closer scrutiny of whether the theoretical section should be removed or substantially reframed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The one thing you should know: the paper's central empirical claim is not supported, because the coarsening algorithm consumes the full label vector, and the experiments use a 60/20/20 split. Algorithm 3 selects initial centers \"within each label category\" and splits until purity T=1, so the graph partition is a function of the labels of every node, including the 20% held out for testing. Algorithm 1 then builds the training target on the coarsened graph as argmax(PY), with that same P. No baseline gets this advantage: VNGC, VEGC, JCGC, GSGC are unsupervised, and GCOND, FGC, CMGC are trained only on training labels. So the reported accuracy parity at r=0.1–0.05, including the \"up to 20 times without compromising test accuracy\" headline and the SOTA numbers on Co-CS/Co-Phy, mostly measures how much the test labels themselves are baked into the coarsened graph. That is a load-bearing flaw, not a minor one.\n\nWhat is genuinely new here is the combination of granular-ball computing with graph coarsening. The adaptive splitting by purity threshold without a predefined ratio is a real extension of the authors' earlier granular-ball work, and the algorithm is simple, local, and efficient. The paper also does a solid job on the empirical tour: multiple GNN backbones, noise injection, memory usage, parameter sensitivity, and released code. The efficiency gains at fixed ratios look plausible even setting aside the leakage.\n\nThe soft spots beyond leakage: the fixed-ratio experiments in Table 1 are not reproducible from the described method, since the adaptive algorithm produces whatever ratio it produces and the paper does not say how a target ratio is enforced. Theorem 1 is circular: it assumes L_gb ≈ L and P^T P ≈ I, which are exactly the spectral preservation properties the theorem is supposed to prove. The noise-robustness analysis is also affected by the leakage, so the robustness claims do not measure denoising ability.\n\nWho should read this? Anyone working on graph condensation or coarsening, mainly as a cautionary example of how label leakage can inflate coarsening results. The granular-ball idea itself might be salvageable with a properly supervised setup where only training labels guide the partition, but the version evaluated here cannot be accepted.\n\nMy recommendation: send it to review anyway, because the flaw is specific, identifiable, and fixable, and the underlying coarsening mechanism deserves a second look under a corrected protocol. But the current empirical claims should not survive contact with the referees.","headline":"The coarsening idea is real, but the headline accuracy claims are invalidated by test-label leakage in the coarsening step.","tokens_in":22031,"tokens_out":1803,"would_cite":false,"duration_ms":18183,"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":"SGBGC claims a label-guided granular-ball coarsening that shrinks graphs up to 20x with no test-accuracy loss, training GNNs far faster.","keywords":["graph coarsening","granular-ball computing","graph neural networks","node classification","scalability","adaptive coarsening","supervised coarsening"],"falsifier":"Hold out the 20% test labels when running Algorithm 3 on Cora and Citeseer — use only the 60% training labels for center selection and purity splitting — and compare the reported Table 1 accuracies; if accuracy drops by more than a few points, the central claim depends on label leakage.","tokens_in":20927,"feed_emoji":"🕸️","tokens_out":7303,"duration_ms":59096,"temperature":0.7,"pith_summary":"This paper claims that a graph can be shrunk to a small set of 'granular-ball' super-nodes, built by repeatedly splitting the graph until each ball contains nodes of a single class, and that a GNN trained on this tiny coarsened graph reaches the same test accuracy as one trained on the full graph. The proposed method, SGBGC, does not need a user-specified coarsening rate; the purity threshold drives the compression adaptively, reaching ratios as low as 0.05 (a 20x reduction) on the largest benchmarks. A sympathetic reading takes the central claim to be that label-guided structural coarsening preserves enough of the graph's spectral and feature information to make GNN training scalable without sacrificing accuracy. The significance, if true, is that costly message-passing on million-node graphs could be replaced by training on a few percent of the nodes, with the learned weights transferred back to the full graph.","feed_headline":"Graph coarsening cuts GNN graphs 20x with no accuracy loss","feed_subtitle":"Super-node graphs match full-graph accuracy on five benchmarks while training far faster.","key_machinery":"The load-bearing object is the graph granular-ball: a connected subgraph of the original graph whose center is its highest-degree node and whose purity T is the fraction of its nodes belonging to the most frequent label. The mechanism is iterative binary splitting — choose the two highest-degree nodes as new centers, assign every other node to the nearer center by shortest-path distance, and repeat until every ball has T = 1 — followed by contraction of each ball into a super-node with mean features and majority label. This replaces global distance computations with local shortest-path splits, giving O($N^{{3/2}}$ + M√N) coarsening and an adaptive coarsening rate set by the data itself rather than by a user-chosen ratio.","core_discovery":"The central discovery the paper asserts is that a purely structural-plus-label-driven coarsening — no gradient training, no spectral decomposition — can pack nodes into super-nodes whose mean features and dominant labels reproduce full-graph classification accuracy. SGBGC first picks α = √N high-degree seeds, distributed evenly across label categories, assigns every node to the nearest seed by shortest path, then recursively splits each granular-ball by its two highest-degree nodes until each child ball is label-pure (purity T = 1). The coarsened graph connects any two super-nodes whose original node sets share an edge, and training happens on that graph with the learned weights transferred to the original graph. On Cora, Citeseer, Pubmed, Co-CS and Co-Phy, the paper reports accuracy within 0.2–1.1 points of the full graph at adaptive ratios of roughly 0.36–0.49, and at forced ratios of 0.05–0.1 the method beats training-dependent condensers like GCOND and CMGC on most settings.","pith_inferences":["A fair evaluation would withhold the 20% test-split labels from Algorithm 3, because the reported numbers come from a 60/20/20 split in which all labels, including the test nodes', are used to seed centers and check purity.","The noise-injection experiments flip labels that the coarsening procedure itself consumes, so the observed robustness may reflect the graph being built from those noisy labels rather than structural denoising; a clean test would inject noise only after coarsening.","An immediate extension is to run the structural part of the split (degree centers, shortest-path assignment) without any label input on link prediction or graph classification, where no purity signal exists, to see whether the compression benefit survives without supervision.","The 20x compression claims are concentrated on Co-CS and Co-Phy, whose homophilic label structure makes purity-based splitting unusually easy; on label-heterogeneous graphs the adaptive ratio may remain close to 0.5, weakening the scalability claim."],"forward_implications":["GNN training on large graphs can be replaced by one cheap coarsening pass plus training on the compressed graph, with the learned weights transferred back to the full graph for inference.","Users no longer need to pick a coarsening rate; the purity threshold T = 1 determines the compression level automatically for each dataset.","Because coarsening happens before training, it composes with sampling and mini-batching strategies rather than competing with them.","If Theorem 1 holds, the coarsened graph approximately preserves the original Rayleigh quotient, so the compressed graph can stand in for the original in other spectral pipelines, not only node classification.","Purity-based splitting groups noisy nodes together, which acts as a label-noise filter before the GNN sees the data."],"supporting_citations":[{"why":"Supplies the granular-ball computing paradigm that the paper adapts to graphs.","marker":"Xia et al. 2019"},{"why":"The SCAL coarsening framework and experimental protocol that SGBGC compares against and extends.","marker":"Huang et al. 2021"},{"why":"Defines spectral coarsening methods VNGC and VEGC used as baselines.","marker":"Loukas 2019"},{"why":"Provides the relaxation-based coarsening schemes GSGC and JCGC used as baselines.","marker":"Ron, Safro, and Brandt 2011"},{"why":"GCOND, a training-dependent graph condensation baseline that SGBGC must beat.","marker":"Jin et al. 2021"},{"why":"FGC, the featured graph coarsening baseline with similarity guarantees.","marker":"Kumar et al. 2023"},{"why":"CMGC, the strongest training-dependent coarsening baseline compared in Table 1.","marker":"Dickens et al. 2024"},{"why":"Defines the GCN model and supplies the Cora, Citeseer, and Pubmed datasets.","marker":"Kipf and Welling 2016"},{"why":"Supplies the Co-CS and Co-Phy datasets and the evaluation split conventions.","marker":"Shchur et al. 2018"}],"fun_headline_variants":["Granular-ball coarsening: 20x smaller graphs, GNN accuracy intact","Adaptive graph coarsening: 20x smaller, accuracy preserved","Supervised granular-ball coarsening scales GNNs with no accuracy hit","Granular-ball coarsening adapts splitting, shrinks graphs 20x","Self-tuning coarsening: no preset ratio, GNNs speed up 20x"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm is given the labels of the very nodes it is later asked to predict, so its reported accuracy includes the effect of having seen the test answers during graph construction.","fun_headline_variants_meta":{"raw":{"variants":["Granular-ball coarsening: 20x smaller graphs, GNN accuracy intact","Adaptive graph coarsening: 20x smaller, accuracy preserved","Supervised granular-ball coarsening scales GNNs with no accuracy hit","Granular-ball coarsening adapts splitting, shrinks graphs 20x","Self-tuning coarsening: no preset ratio, GNNs speed up 20x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000859,"raw_usage":{"total_tokens":3733,"prompt_tokens":954,"completion_tokens":2779,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":2673}},"tokens_in":570,"tokens_out":2779,"duration_ms":18321,"temperature":1.0,"reasoning_tokens":2673,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:44:00.605804+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Hold out the 20% test labels when running Algorithm 3 on Cora and Citeseer — use only the 60% training labels for center selection and purity splitting — and compare the reported Table 1 accuracies; if accuracy drops by more than a few points, the central claim depends on label leakage.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines spectral coarsening methods VNGC and VEGC used as baselines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The SCAL coarsening framework and experimental protocol that SGBGC compares against and extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the relaxation-based coarsening schemes GSGC and JCGC used as baselines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"FGC, the featured graph coarsening baseline with similarity guarantees."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"CMGC, the strongest training-dependent coarsening baseline compared in Table 1."}],"review_version":1}