{"id":"2673e27a-0f88-436f-b557-2d4bb76d16f6","arxiv_id":"2506.19224","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"GBGC uses granular-ball computing to coarsen graphs adaptively, achieving faster runtime and competitive classification accuracy on benchmark datasets.","lead":"This paper presents GBGC, a graph coarsening method that groups nodes into granular-balls using an adaptive coarse-to-fine splitting process, then treats each ball as a supernode in the coarsened graph. It reports large speedups over existing coarsening methods and classification accuracy that often matches or exceeds that of the full graph.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The spectral-preservation proof does not apply to GBGC: C is not nearly orthogonal and the coarsened Laplacian from Eq. (10) is not C^T L C, leaving the theoretical guarantee unsubstantiated.","rationale":"The reader's weakest assumption correctly identifies that the projection matrix in §3.1 does not satisfy C^T C ≈ I. My analysis confirms this and adds a further, equally serious defect: the graph built by Eq. (10) does not have Laplacian C^T L C, so even the formal relationship used in the proof is inconsistent with the algorithm. Thus Theorem 1 cannot support the claimed spectral preservation. This matters because spectral preservation is part of the paper's rationale for why coarse graphs retain key information. However, the central empirical claims of higher classification accuracy and lower runtime rest on Tables 2 and 3, which show GBGC generally ahead of baselines on the tested datasets, subject to caveats about significance testing and the fixed-ratio protocol. A flawed theoretical section does not by itself overturn those empirical results, but it does require correction or removal before the paper can be accepted. The conditional verdict is therefore appropriate; no change in verdict is needed.","tokens_in":13834,"tokens_out":9051,"duration_ms":99865,"concrete_test":"Run the released GBGC implementation on one small graph (e.g., a 5-cycle) with no further splitting, form the binary matrix C from §3.1, and compute (i) C^T C and (ii) the Laplacian of the Eq. (10) coarsened graph. Then check whether C^T C ≈ I and whether the Eq. (10) Laplacian equals C^T L C. If either check fails, Theorem 1 cannot be invoked for GBGC, and §3.3 should be corrected or removed. A second, quantitative check is to evaluate the Rayleigh quotient ratio Rc/Ro for the first nontrivial eigenvector of L; if it deviates from 1 by more than a small tolerance, the claimed approximation fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In §3.3, Theorem 1 rests on two assumptions that fail for the actual GBGC construction. First, C is defined in §3.1 by C_ij=1 when node i is assigned to supernode j, so C^T C = diag(|GB_1|,...,|GB_Nbar|). For any nontrivial coarsening each diagonal entry is at least 1 and typically >1, so the hypothesis C^T C ≈ I is false. Second, even setting orthogonality aside, the proof uses L = C^T L C as the relation between original and coarsened Laplacians, but the coarsened graph in Step 5 / Eq. (10) is constructed as an unweighted superedge whenever any inter-ball edge exists. That graph does not have C^T L C as its Laplacian: C^T L C would weight each superedge by the number of inter-ball edges and would include self-loops from intra-ball edges. Consequently, the Rayleigh-quotient approximation Rc ≈ Ro in Eq. (13) is not established for GBGC. The paper's claim of spectral preservation therefore has no valid formal support; it rests only on the empirical spectral-distance comparison, which is not equivalent to the theorem's statement.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GBGC, a graph coarsening method that adaptively partitions the original graph into granular-balls of varying sizes and uses these as supernodes in the coarsened graph. The authors claim that this multi-granularity approach preserves spectral properties, improves classification accuracy over the original graph and over six baseline coarsening methods, and runs orders of magnitude faster than prior methods, with claimed complexity O(N^{3/2} + E√N). The method is deterministic and code is provided. The main theoretical support is Theorem 1, which asserts Rayleigh-quotient preservation under a 'generalized orthogonality' assumption on the projection matrix C.","tokens_in":14124,"tokens_out":7029,"duration_ms":71015,"significance":"If the empirical results hold, GBGC has practical value as a fast, deterministic graph-coarsening preprocessing method: the reported speedups are large and the accuracy gains on most of the tested datasets are non-trivial. The paper also ships code, which is a strength for reproducibility. However, the central theoretical guarantee, Theorem 1, is invalid as stated because the required orthogonality assumption is false for the actual construction, and the coarsened graph defined in Eq. (10) does not have C^T L C as its Laplacian. The spectral-preservation claim therefore currently rests on an unproven theorem plus a limited empirical spectral-distance comparison. The empirical contribution is potentially salvageable, but the theory as written cannot support the paper's claims.","major_comments":[{"comment":"The hypothesis C^T C ≈ I is false for the projection matrix defined in §3.1. Since C_ij = 1 exactly when node i is assigned to granular-ball j, C^T C is the diagonal matrix diag(|GB_1|,...,|GB_Nbar|), whose entries are the sizes of the granular-balls. For any non-trivial coarsening these entries are integers greater than 1, so the assumption C^T C ≈ I does not hold. The proof of Eq. (13) therefore does not apply to GBGC. Moreover, the inference 'according to L = C^T L C, we obtain C L C^T ≈ L' is not valid: from C^T L C ≈ L one cannot conclude C L C^T ≈ L unless C C^T ≈ I, and C C^T is an N×N block-diagonal matrix of all-ones blocks, not an identity. Both steps of the proof fail for the actual construction.","section":"§3.3, Theorem 1; §3.1 definition of C"},{"comment":"The paper states in §3.1 that the coarsened Laplacian is L = C^T L C, but the coarsened graph constructed in Step 5 via Eq. (10) does not have C^T L C as its Laplacian. The graph in Eq. (10) has an unweighted edge between two supernodes whenever any inter-ball edge exists, and it has no self-loops. In contrast, C^T L C would assign to each superedge a weight equal to the number of inter-ball edges and would include diagonal entries corresponding to intra-ball edges. Therefore the relation L = C^T L C is not satisfied by the algorithm's output, and the Rayleigh-quotient approximation Rc ≈ Ro in Eq. (13) is not established for GBGC.","section":"§3.1 vs. §3.2 Step 5, Eq. (10)"},{"comment":"Even if one were to accept the generalized-orthogonality assumption, the theorem would be vacuous for the method being proposed. If C^T C ≈ I, then every granular-ball must have size approximately 1, meaning almost no coarsening occurs. A spectral-preservation guarantee that only holds when the algorithm does not coarsen cannot justify the adaptive multi-granularity splitting mechanism that is the paper's main contribution. The theorem therefore provides no formal support for the claim that GBGC preserves the spectral structure of the original graph.","section":"§3.3, Theorem 1 (triviality)"},{"comment":"Figure 3 is the only direct empirical evidence for spectral preservation, but it reports spectral distance only for six of the eleven datasets and does not show error bars or significance tests. The text states that spectral distance is computed by zero-padding the smaller eigenvalue vector, but it does not specify how many eigenvalues are retained or whether the comparison is sensitive to the padding convention. As written, this evidence is too weak to substitute for the invalid Theorem 1 as support for the spectral-preservation claim.","section":"§4.2, Figure 3"}],"minor_comments":[{"comment":"The same symbol L is used for the original Laplacian and the coarsened Laplacian, which makes Eqs. (11)–(13) confusing. The coarsened Laplacian should be denoted with a different symbol, e.g., L_c.","section":"§3.1 and §3.3"},{"comment":"The paper claims time complexity O(N^{3/2} + E√N) in the conclusion, but no derivation of this complexity bound is given anywhere in the main text. A formal analysis of the BFS-based initialization and the recursive splitting procedure is needed to substantiate the efficiency claim.","section":"§5, Conclusion"},{"comment":"The evaluation protocol for the classification experiments is incompletely specified in the main text: the classifier, training/validation split, hyperparameters, and the number of runs used to compute mean and standard deviation are not described. The reader is referred to an appendix that is not present in the submitted manuscript, making Table 2 difficult to reproduce.","section":"§4.1, Experimental setup"},{"comment":"The notation 'quality(GB_jA + GB_jB)' is ambiguous: the text says it denotes the sum of the qualities of the two child granular-balls, but the symbol '+' suggests a union operation. Since Eq. (8) compares a sum to the parent quality, the condition will often be satisfied trivially even when splitting is not beneficial; the authors should discuss whether a normalized or averaged comparison is more appropriate.","section":"§3.2, Eq. (8)"},{"comment":"The statement 'This computation ensures that the spectral properties of the original graph are preserved in the coarsened graph' is presented as a fact before Theorem 1 is introduced. In the revised version, this should be rephrased as a claim or as a consequence of the (to-be-proved) theorem.","section":"§3.1"}],"recommendation":"major_revision","confidential_remarks":"The theoretical flaw in Theorem 1 is serious and is not a simple gap that can be patched with a stronger assumption: the projection matrix used by GBGC is inherently non-orthogonal and the coarsened graph does not satisfy the Laplacian relation used in the proof. However, the empirical results, especially the speedups, suggest that the algorithmic idea may still be publishable if the paper is substantially revised to remove the invalid theorem and to reframe the spectral claim as an empirical observation. The authors should also provide a complete experimental protocol and a formal complexity analysis before resubmission. If the authors are unwilling to drop or replace the theoretical guarantee, I would recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. The algorithm itself is worth a look: GBGC applies granular-ball computing to graph coarsening for the first time, using an adaptive quality-based splitting rule that captures multi-granularity structure. The empirical story is strong on its own terms: on most of the eleven datasets it beats the spectral baselines on classification accuracy, often matches or beats the full graph, and the runtime advantages are very large (tens to hundreds of times faster on the bigger graphs). The method is simple, deterministic, and the code is posted. That is a real contribution, and I believe the empirical claims are likely to hold up in a fair re-run.\n\nThe soft spot is not small, though. The theoretical analysis in §3.3 is invalid. Theorem 1 assumes C^T C ≈ I, but C is defined as a partition matrix with C_ij=1 when node i maps to supernode j, so C^T C is the diagonal matrix of granular-ball sizes. For any nontrivial coarsening those entries are larger than 1, so the assumption is false. And the coarsened Laplacian is not C^T L C: Eq. (10) creates an unweighted superedge whenever any inter-ball edge exists, while C^T L C would count edge multiplicities and include self-loops from intra-ball edges. So the Rayleigh-quotient preservation result simply does not apply to GBGC. The stress-test note is right on both counts. This is not a one-line fix; the proof needs to be either corrected with a different argument (maybe relating to generalized eigenproblems or weighted aggregation) or dropped entirely and replaced with empirical spectral-distance evidence, which the paper already includes.\n\nThe evaluation also has a fairness problem. All baselines are run at the ratio ra that GBGC produces adaptively, which is fine if the baselines are allowed to tune their own ratios, but here they are not, so the comparison is tilted. There are no significance tests reported, and the claim that GBGC 'almost always' beats the original graph overstates what the tables show, since it loses on two datasets. The paper also titles the conclusion with 'standard graph data preprocessing method', which is overclaiming for a method tested only on graph classification.\n\nWho is this for? Someone working on scalable graph representation learning or preprocessing for GNNs will find the method useful and the speed compelling. The theoretical section should not be cited, but the algorithm and empirical results can be. This paper deserves a serious referee, but it needs major revision: fix or delete the theorem, redo baselines with a fair protocol, add significance tests, and tone down the claims. I would not desk-reject it; there is a good empirical paper underneath the broken theory.","headline":"A fast, adaptive graph coarsening heuristic with a genuinely new granular-ball splitting idea and impressive speedups, but the spectral-preservation theorem is broken and the evaluation protocol advantages GBGC; worth serious refereeing as an empirical paper.","tokens_in":14618,"tokens_out":1198,"would_cite":false,"duration_ms":13883,"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":"Graph coarsening by granular balls claims large speedups and preserved accuracy.","keywords":["graph coarsening","granular-ball computing","multi-granularity","graph classification","spectral distance","adaptive splitting","graph preprocessing","Laplacian spectrum"],"falsifier":"Run GBGC on any graph, pick a supernode containing at least two original nodes, and compute $C^T C$: its diagonal will contain that ball's size, contradicting $C^T C \\approx I$. To test the empirical accuracy claim rather than the proof, compute the true spectral distance between the original and coarsened graphs on a graph with known Laplacian eigenvalues and compare it with the paper's reported SD values.","tokens_in":13639,"feed_emoji":"⚡","tokens_out":9941,"duration_ms":90178,"temperature":0.7,"pith_summary":"The paper proposes that graph coarsening should follow the graph's own multi-granularity: start with the whole graph as one coarse unit, then adaptively split it into dense, tightly connected granular-balls, and treat each ball as a supernode of the coarsened graph. The authors claim this preserves the information that matters for graph classification better than spectrum-preserving coarsening does, and that classification on the coarsened graph is almost always at least as accurate as on the original full graph. They further claim speedups of tens to hundreds of times over existing coarsening methods, with time complexity $O(N^{3/2} + E\\sqrt{N})$. If these claims hold, GBGC offers a fast, adaptive, parameter-light preprocessing step for large graphs and graph neural networks.","feed_headline":"Granular-ball graph coarsening: 100x faster, often more accurate","feed_subtitle":"Merging similar nodes into supernodes cuts preprocessing time by orders of magnitude without losing accuracy.","key_machinery":"The carrying mechanism is the granular-ball, a connected subset of nodes contracted into one supernode, together with an adaptive binary-splitting loop. The algorithm initializes about $\\sqrt{N}$ balls by breadth-first search from high-degree centers, scores each ball by a quality function equal to average degree plus transitivity (the fraction of connected triples that close into triangles), and splits a ball into two child balls around its two highest-degree nodes whenever the children's summed quality beats the parent's. Global computation happens only at initialization; all later steps are local to a ball, which is what gives the claimed $O(N^{3/2} + E\\sqrt{N})$ time. The final balls become supernodes, and cross-ball edges become superedges.","core_discovery":"On its own terms, the paper's discovery is that a coarse-to-fine adaptive splitting into granular-balls — subsets of nodes chosen for high internal connectivity and triangle density — produces supernodes that keep the structure needed for classification, without solving an eigenvalue problem. Each granular-ball becomes one supernode; a superedge connects two supernodes whenever an original edge crosses between their balls. A split of a ball into two children is accepted only when the summed quality of the children exceeds the parent's quality, so the coarsening ratio adapts to local structure. The authors report that this representation is robust and generalizes, giving classification accuracy that is almost always higher than the original graph's, while the runtime is orders of magnitude lower than spectrum-preserving baselines.","pith_inferences":["Editorial inference: the frequent accuracy gain over the full graph suggests that contracting dense balls acts as a denoiser, so the advantage over FULL should shrink on graphs with little noise; the paper's own results on IMDB-BINARY and PROTEINS show that pattern.","Editorial inference: the split criterion uses only edge structure, not node features; adding feature agreement to the quality function is a natural next step for attributed graphs.","Editorial inference: because the initial $\\sqrt{N}$ balls are grown by breadth-first search from high-degree centers, the method is a form of topology-driven partitioning; comparing it against modularity-based or multilevel community detection would isolate what the granularity-adaptive criterion adds."],"forward_implications":["If the experimental results hold, graph classification can be run on a coarsened graph a fraction of the original size, with accuracy matching or exceeding the full graph; in the reported runs the fraction of nodes retained $r_a$ is roughly 0.2–0.4.","Because the split decision is adaptive, GBGC chooses a finer partition where the graph is locally complex and a coarser one where it is homogeneous, removing the need to tune a fixed coarsening ratio.","The claimed time complexity implies the method remains usable on graphs where spectral coarsening methods run out of memory; in the experiments MGC and KGC hit out-of-memory on the DD dataset while GBGC finished.","Being deterministic, GBGC can serve as a stable preprocessing step in pipelines where randomized coarsening introduces run-to-run variance."],"supporting_citations":[{"why":"supplies the granular-ball computing paradigm that GBGC adapts from discrete data to graphs.","marker":"[Xia et al., 2023b]"},{"why":"provides the empirical basis for choosing $\\sqrt{N}$ initial granular-balls.","marker":"[Xie et al., 2020a]"},{"why":"gives the bound on optimal cluster number cited for the $\\sqrt{N}$ initialization.","marker":"[Yu and Cheng, 2001]"},{"why":"supplies the global-precedence law that justifies starting from the whole graph as one coarse ball.","marker":"[Chen, 1982]"},{"why":"supports using the projection matrix $C$ to compare spectra of graphs with different node counts.","marker":"[Cai et al., 2021]"},{"why":"defines the spectrum-preserving coarsening framework and the VNGC/VEGC baselines GBGC is compared against.","marker":"[Loukas, 2019]"},{"why":"provides the MGC/SGC baselines and the spectral-distance objective that GBGC aims to outperform.","marker":"[Jin et al., 2020]"},{"why":"supplies the KGC baseline and the experimental setting used for hyperparameter sensitivity analysis.","marker":"[Chen et al., 2023]"},{"why":"defines spectral distance as the evaluation metric for structural similarity between original and coarsened graphs.","marker":"[Wilson and Zhu, 2008]"},{"why":"provides the DosCond baseline used in the classification comparison.","marker":"[Jin et al., 2022]"}],"fun_headline_variants":["Granular balls make graph coarsening 100x faster, smarter","Adaptive granular-ball coarsening: speed and accuracy up","Graph coarsening via granular balls: fast, adaptive, precise","Granular-ball coarsening: 100x speedup, accuracy boost","New granular-ball graph coarsening: faster and more accurate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that GBGC preserves the Laplacian spectrum assumes the contraction matrix $C$ satisfies $C^T C \\approx I$, but whenever a supernode contains more than one original node the corresponding diagonal entry of $C^T C$ is that supernode's size, which is larger than one, so the assumption fails for every nontrivial coarsening.","fun_headline_variants_meta":{"raw":{"variants":["Granular balls make graph coarsening 100x faster, smarter","Adaptive granular-ball coarsening: speed and accuracy up","Graph coarsening via granular balls: fast, adaptive, precise","Granular-ball coarsening: 100x speedup, accuracy boost","New granular-ball graph coarsening: faster and more accurate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000627,"raw_usage":{"total_tokens":2925,"prompt_tokens":997,"completion_tokens":1928,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":613,"completion_tokens_details":{"reasoning_tokens":1846}},"tokens_in":613,"tokens_out":1928,"duration_ms":13757,"temperature":1.0,"reasoning_tokens":1846,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T18:34:11.167246+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run GBGC on any graph, pick a supernode containing at least two original nodes, and compute $C^T C$: its diagonal will contain that ball's size, contradicting $C^T C \\approx I$. To test the empirical accuracy claim rather than the proof, compute the true spectral distance between the original and coarsened graphs on a graph with known Laplacian eigenvalues and compare it with the paper's reported SD values.","supporting_citations":[{"cited_title":"The upper bound of the optimal number of clusters in fuzzy clustering","cited_arxiv_id":null,"evidence_quote":"gives the bound on optimal cluster number cited for the $\\sqrt{N}$ initialization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the global-precedence law that justifies starting from the whole graph as one coarse ball."},{"cited_title":"Graph reduction with spec- tral and cut guarantees","cited_arxiv_id":null,"evidence_quote":"defines the spectrum-preserving coarsening framework and the VNGC/VEGC baselines GBGC is compared against."},{"cited_title":"Graph coarsening with preserved spectral properties","cited_arxiv_id":null,"evidence_quote":"provides the MGC/SGC baselines and the spectral-distance objective that GBGC aims to outperform."},{"cited_title":"A gromov–wasserstein geometric view of spectrum-preserving graph coarsening","cited_arxiv_id":null,"evidence_quote":"supplies the KGC baseline and the experimental setting used for hyperparameter sensitivity analysis."},{"cited_title":"A study of graph spectra for comparing graphs and trees.Pat- tern Recognition, 41(9):2833–2841,","cited_arxiv_id":null,"evidence_quote":"defines spectral distance as the evaluation metric for structural similarity between original and coarsened graphs."},{"cited_title":"Condensing graphs via one-step gradient matching","cited_arxiv_id":null,"evidence_quote":"provides the DosCond baseline used in the classification comparison."}],"review_version":2}