{"id":"7065c5d7-3e2e-44a4-940e-98727c5e36ec","arxiv_id":"2608.02128","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"CoRe-GNN runs message passing both inside clusters and on a coarsened graph in parallel, letting scalable training keep long-range signal.","lead":"This paper proposes CoRe-GNN, a GNN that runs two message-passing streams in parallel: one inside graph clusters and one on a coarsened version of the whole graph. The goal is to combine the memory efficiency of cluster-based batching with the long-range information that only a global, coarsened view provides.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Batched training proxy (Algorithm 1, line 6) lacks any approximation guarantee; Theorem 2 covers only the unbatched update, so the scalability claim rests on an identified but unquantified approximation.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: the batched training proxy has no theoretical support, and Theorem 2 only covers the full, unbatched propagation. This is the most fragile point because the claimed scalability to millions of nodes relies entirely on this proxy. In good faith, the paper's core idea—parallel coarsened inter-cluster and local intra-cluster propagation—is sound and is a genuine architectural contribution. The experiments, while extensive, do not fully support the 'consistently outperforms' claim: CoRe-GNN loses to Coarsen-GNN on Cora and CiteSeer, and both CoRe-GNN variants lose to Cluster-GCN on ogbn-arxiv. These contradictions weaken the headline but not the central mechanism. The most concrete way to test whether the proxy actually matters is to compare full-batch and batched training on a graph where both are feasible. If the gap is small, the proxy is empirically validated; if large, the scalability results are misleading. Given that the paper is otherwise well-structured and the theoretical guarantee for the unbatched case is correct under its assumptions, a conditional acceptance remains appropriate, pending (a) a bound or systematic empirical validation of the proxy, and (b) softened claims about consistent outperformance. I thus recommend no change to the reader's verdict.","tokens_in":30741,"tokens_out":8814,"duration_ms":98685,"concrete_test":"Take ogbn-arxiv (N=169k) where full-batch CoRe-GNN fits on the A40. Train CoRe-GNN (Algorithm 3) and CoRe-GNN(b) (Algorithm 1) with identical hyperparameters and data splits (at least 3 seeds). Compute (i) test-accuracy gap; (ii) for a fixed checkpoint, run the batched forward pass and exact forward pass on the same weights and report the relative Frobenius difference of the final H^{(K)} for the test nodes, and the layer-wise accumulation. If the accuracy gap exceeds the 0.6-point margin by which Cluster-GCN beats CoRe-GNN(b) on ogbn-arxiv, or the representation difference exceeds a threshold (e.g., >10%), then the proxy degrades the learned model and the scalability claim is not established. Additionally, derive a simple bound for σ=identity and linear θ to see whether the proxy error can be controlled by ε and K.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central scalability claim is that CoRe-GNN(b) trains on graphs with millions of nodes. The batched forward pass replaces the intra-cluster update for non-batch super-nodes with a self-loop in coarsened space (Algorithm 1, line 6). This is the only component that makes training memory independent of N. Yet there is no theorem bounding the error between this proxy and the exact full CoRe-GNN propagation: Theorem 2 proves a bound for the unbatched model (Eq. 6 / Algorithm 3) under ker(L)-preservation assumptions, but does not address the proxy. Because H_c^{(l)} for non-batch super-nodes is reused in the next layer's inter-cluster term, the approximation can accumulate across layers and affect batch nodes via the lifted inter-cluster term. The paper also reports results that contradict the 'consistently outperforms' claim: on Cora and CiteSeer, Coarsen-GNN beats both CoRe-GNN and CoRe-GNN(b); on ogbn-arxiv, Cluster-GCN beats both. The empirical evidence for the proxy is indirect: on small datasets full-batch and batched differ by ≤0.8 accuracy, but this is not a systematic test on the large graphs where the proxy is necessary. The proxy is the load-bearing premise because if it materially changes the learned function, the reported large-scale results are not evidence for the full CoRe-GNN architecture.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes CoRe-GNN, a GNN architecture that runs two propagations in parallel at every layer: an inter-cluster propagation on a coarsened graph (capturing long-range structure) and an intra-cluster propagation on the original graph (preserving per-node discriminability). The authors give a unified matrix view of coarsening-based and cluster-based scalable GNNs, introduce a cluster batching scheme for training on graphs with millions of nodes, prove a propagation-approximation guarantee analogous to the one for coarsened GNNs (Theorem 2), and report extensive node-classification experiments on homophilic, heterophilic, large-scale, and long-range benchmarks. The paper is clearly written, the architecture is simple and appealing, and the experimental study is broad, with standard deviations and hyperparameter tables.","tokens_in":31130,"tokens_out":7727,"duration_ms":56737,"significance":"If the empirical claims hold, CoRe-GNN is a useful and conceptually clean combination of two complementary compression strategies, and its batched variant offers a practical memory-accuracy trade-off for large graphs. The unified propagation-matrix perspective is a nice didactic contribution, and the proof of Theorem 2 is a correct, though short, adaptation of the authors' earlier Theorem 1. The paper does not ship code or machine-checked proofs, but the experimental detail is relatively thorough. The main caveats are that the headline 'consistently outperforms' claim is false as stated, and the scalability of the batched variant rests on a self-loop proxy that has no accompanying approximation analysis.","major_comments":[{"comment":"The abstract and conclusion claim that CoRe-GNN 'consistently outperforms' Coarsen-GNN and Cluster-GCN. This is contradicted by the paper's own tables: Table 1 shows Coarsen-GNN beats CoRe-GNN on Cora (82.03 vs 81.67) and CiteSeer (73.86 vs 73.62); Table 2 shows Cluster-GCN beats CoRe-GNN and CoRe-GNN(b) on ogbn-arxiv (70.22 vs 70.03 and 69.56); on Amazon-ratings, CoRe-GNN(b) (45.48) is below both Coarsen-GNN (46.99) and Cluster-GCN (47.02). The body text at the homophilic paragraph acknowledges that Coarsen-GNN is best on Cora/CiteSeer, so the abstract and conclusion should be softened to 'competitive or best on most benchmarks' or supplemented with statistical significance tests.","section":"Abstract / §1 / §5"},{"comment":"The batched training forward pass replaces the intra-cluster update for non-batch super-nodes by the self-loop proxy H_c^{(l)}[\\bar B] <- σ(H_c^{(l-1)}[\\bar B] θ^{(l)}) + H_c^{(l)}[\\bar B]. This proxy is the only mechanism that makes memory O(K(n+b)d) and independent of N, but no theorem or rigorous analysis bounds its error. Theorem 2 and Algorithm 3 apply only to the full, unbatched propagation. The proxy's error can accumulate across layers and enter the next layer's inter-cluster term through H_c, so the million-node results are evidence for the batched heuristic, not for the exact CoRe-GNN architecture. I ask the authors to either prove an error bound for the proxy (e.g., under Lipschitz activations, in terms of the coarsening RSA constant and intra-cluster spectral properties) or add a systematic ablation on graphs where full-batch training fits, measuring both accuracy gap and rep","section":"§3.1 / Algorithm 1 and Algorithm 4"},{"comment":"Theorem 2 requires that Π and S_inter are both ker(L)-preserving and that S_inter is R-preserving. Unlike S, S_inter = S - S_intra is not a normalized adjacency-like matrix, and it is not clear when these assumptions hold; the paper refers to [16] for a discussion of the analogous assumptions for S, but does not discuss S_inter. If the assumptions are not satisfied, the guarantee may be vacuous. The authors should either give sufficient conditions under which S_inter inherits these properties from S, or provide empirical validation of the assumptions on the datasets used in the paper.","section":"§3.3 / Appendix A.1"},{"comment":"The large-scale comparisons are made only against the two compressed-graph baselines and full GCN. Since the paper's central claim is about scalability and long-range accuracy, the absence of standard scalable baselines such as GraphSAGE, GraphSAINT, or other long-range-oriented GNNs makes the relative significance hard to judge. At minimum, the authors should state whether these comparisons were omitted deliberately, and ideally include a few published reference numbers on the large-scale datasets where full GCN is OOM.","section":"§4 / Tables 1–2"}],"minor_comments":[{"comment":"Typo: 'thesamedecomposition' should be 'the same decomposition'.","section":"Abstract"},{"comment":"The label 'CoRE-GNN' is internally inconsistent with the body's 'CoRe-GNN'; unify capitalization.","section":"Tables 1 and 2"},{"comment":"The captions 'CΠ terms' and 'CS terms' are unclear; the first row appears to show the two bound constants separately, so reword to something like 'C_S and C_Π terms (left two panels)'.","section":"Figure 3 caption"},{"comment":"The CoRe-GNN time complexity expression O(K((E_c+E_intra)d + (n+N)d^2 + 2Nd)) has the 2Nd term inside the outer K factor; this is linear in N but the d is not squared. If the 2Nd comes from two projection operations, the expression is acceptable but should be clarified to avoid confusion with the d^2 terms.","section":"Appendix C.1, Table 3"},{"comment":"The sentence 'if we consider Frobenius norms instead we would easily have ||S_inter||_Fro ≤ ||S||_Fro, hinting that the constants are indeed improved' is not a proof for the L-operator norms used in the theorems. The authors should mark this clearly as an informal motivation, not a claim.","section":"§3.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is built directly on the authors' own prior work [16,17], and the Coarsen-GNN baseline is also their method. This is not disqualifying, but I recommend the editor ensure that the baseline is not unintentionally disadvantaged (e.g., the per-model selection of the best coarsening algorithm/ratio is reasonable but makes head-to-head comparisons less sharp). Also, despite the detailed hyperparameter tables, no code or reproducibility link is provided; I would encourage requiring it in a revision. The main requested changes are factual: fix the overstated 'consistently outperforms' claim, and address the unquantified batch proxy, which is the load-bearing component for the scalability claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"CoRe-GNN is worth a close look. The core idea is simple and sensible: instead of choosing between coarsening the graph and cutting it into clusters, run both propagations in parallel at each layer, a coarsened inter-cluster branch plus an intra-cluster branch. The paper also does the field a service by writing Coarsen-GNN and Cluster-GCN as complementary modifications of the same propagation matrix, which makes their limitations explicit. That framing is genuinely useful, and the architecture is new as far as I know.\n\nThe experimental work is extensive and honestly reported: ten datasets spanning homophilic, heterophilic, large-scale and long-range settings, standard deviations over ten runs, ablations for the design choices and hyperparameter grids. The headline empirical result, CoRe-GNN(b) reaching around 44.4% on London where GCN gets 32.4%, is a real gain on a task where local message passing struggles. On heterophilic datasets it also clears Coarsen-GNN by a large margin, which is exactly what the design promises.\n\nWhere does it wobble? Two places. First, the abstract and conclusion claim CoRe-GNN 'consistently outperforms' both baselines, but the paper's own tables contradict that: Coarsen-GNN beats it on Cora and CiteSeer, and Cluster-GCN beats it on ogbn-arxiv. The claim should be that it wins on heterophilic and long-range tasks, not a blanket statement. That is a fixable wording problem, not a fatal one.\n\nSecond, and more substantive, is the batched training proxy in Algorithm 1. Line 6 replaces the intra-cluster update of non-batch super-nodes with a self-loop. That is the only thing making memory independent of N, so it is load-bearing. But the paper proves no bound for it; Theorem 2 covers only the full unbatched propagation. The proxy state feeds into the next layer's inter-cluster term, so errors can accumulate. The small-dataset evidence that batched and full-batch differ by at most 0.8 accuracy is reassuring but indirect, and it does not systematically test the large graphs where the proxy is required. I do not think this kills the paper, but the authors need to either bound the proxy or explicitly present the large-scale results as being for the batched architecture with its own approximation, not as faithful to the exact CoRe-GNN propagation.\n\nMinor point: Theorem 2 is a direct substitution of S_inter into the prior theorem. That is fine, and the authors say so, but it should not be oversold as a new theoretical contribution.\n\nVerdict: this is a good paper for the scalable-GNN subfield. A serious referee will have plenty to work with, and the central architecture is worth engaging with. Recommend sending to peer review with a request that they soften the consistently-outperforms claim and address the batched proxy.","headline":"New two-branch coarsened/intra-cluster architecture with strong results on long-range graphs, but the batched training proxy and an overbroad 'consistently outperforms' claim need attention before publication.","tokens_in":31581,"tokens_out":2555,"would_cite":true,"duration_ms":20135,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that running coarsened long-range and local intra-cluster message passing in parallel at every layer fixes both the accuracy ceiling of graph coarsening and the long-range blindness of Cluster-GCN, with a spectral approxima","keywords":["graph neural networks","graph coarsening","Cluster-GCN","message passing","long-range dependencies","node classification","batching","spectral approximation"],"falsifier":"Train CoRe-GNN in full-batch and batched mode on a graph that fits in GPU memory (e.g., Cora or PubMed) with identical hyperparameters and measure test accuracy and training loss trajectories; if the batched variant's accuracy is substantially lower or its loss fails to track the full-batch run, the self-loop proxy is not harmless. A more direct check: compute the per-layer difference between the proxy update and the exact batched update for random cluster batches; if the error grows without bound as layers increase, the proxy does not preserve propagation.","tokens_in":30665,"feed_emoji":"🕸️","tokens_out":4332,"duration_ms":35150,"temperature":0.7,"pith_summary":"Training graph neural networks on large graphs is memory-heavy because each layer stores all node representations. The paper shows that two standard fixes—graph coarsening and Cluster-GCN—are complementary corruptions of the same propagation matrix: coarsening replaces it with a low-rank projection that gives spectral guarantees but makes all nodes in a cluster share one representation, while Cluster-GCN keeps only intra-cluster edges, enabling batching but cutting long-range information. CoRe-GNN performs both propagations in parallel each layer, adding a coarsened inter-cluster term to the local intra-cluster term, and proves an approximation guarantee for the combined propagation with the same restricted-spectral-approximation structure as graph coarsening. A cluster-based batching scheme keeps memory independent of total node count, and experiments show it beats both baselines on homophilic, heterophilic, large-scale, and long-range benchmarks. The upshot: if correct, the two scalability tricks are not an either/or—they can be combined without losing either property.","feed_headline":"Parallel message passing beats coarsening-only and cluster-only GNNs","feed_subtitle":"Combining coarsened long-range propagation with local intra-cluster updates keeps memory low and accuracy high on million-node graphs.","key_machinery":"The carrying mechanism is the matrix identity S ≈ S_intra + Q S_inter^c P, with P a well-partitioned reduction matrix (Moore-Penrose pseudoinverse of lifting Q), Q a lifting matrix with one nonzero per row, and S_inter^c = P S_inter Q the coarsened inter-cluster propagation. It decomposes one message-passing step into a local branch in original node space and a long-range branch in super-node space, coupled each layer. The proof machinery is Loukas's Restricted Spectral Approximation constant, which measures how well smooth signals survive reduce-lift cycles; Theorem 2 applies the same bound to S_inter. The batching extension uses a self-loop in coarsened space for super-nodes not in the cur","core_discovery":"The central claim is that the GCN propagation matrix S can be replaced by S_intra + Q S_inter^c P without losing the approximation guarantees that make coarsening attractive, while restoring per-node discriminability. Here P is the reduction to super-nodes, Q the lifting back, S_intra the intra-cluster block-diagonal part, and S_inter^c = P S_inter Q the coarsened inter-cluster part. The paper proves (Theorem 2) that for smooth signals the error of this combined propagation is bounded by the restricted-spectral-approximation constant times constants that now depend on S_inter, mirroring Theorem 1 for pure coarsening; empirically the mean propagation error is lower than Coarsen-GNN's across t","pith_inferences":["The self-loop proxy used for non-batch super-nodes at training time is an approximation without a stated guarantee; a natural test is to compare batched against full-batch CoRe-GNN on a mid-size graph where both fit, and if accuracy drops materially the scalability claim depends on an unvalidated proxy.","The two-branch structure is formally a template for asynchronous federated learning on graphs: the coarsened graph is a central aggregator and each cluster a client; the self-loop proxy is exactly a 'not reported back' placeholder. The paper gestures at this; making it concrete would require analyzing convergence under delayed updates.","Since Theorem 2's constants involve only S_inter, one can imagine designing coarsenings that explicitly minimize the inter-cluster RSA constant rather than the full coarsening, potentially tightening the bound further—the paper leaves this optimization as future work.","The architecture is agnostic to the coarsening algorithm and could be combined with learned or overlapping partitions; whether overlapping clusters would improve long-range reach without losing batching is untested."],"forward_implications":["Setting the inter-cluster weights to zero recovers Cluster-GCN exactly, so CoRe-GNN is a strict generalization; the intra branch adds per-node detail that coarsening alone flattens.","Because the theorem bounds propagation error by constants depending on the inter-cluster part, coarsening ratios can be pushed higher without the uniform-representation failure of Coarsen-GNN.","The batched memory cost is O(K(n+b)d), independent of the number of nodes N, so graphs that exhaust GPU memory for full GCN can be trained on a single GPU.","On long-range road networks (Paris, London), CoRe-GNN and its batched variant obtain the highest accuracies among the compared architectures, indicating the coarsened branch actually conveys long-range information.","On heterophilic graphs, CoRe-GNN outperforms Coarsen-GNN, consistent with the claim that intra-cluster propagation restores discriminability lost when neighboring nodes carry different labels."],"fun_headline_variants":["Coarsen plus cluster: best of both GNN worlds","Split GNN propagation: coarsened long-range plus local detail","Parallel propagations crack long-range GNN bottleneck","Hybrid GNN keeps memory low, long-range accuracy high","Two-speed GNN: coarsened and local passes in parallel"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The batched training procedure replaces the intra-cluster update for super-nodes outside the current batch with a self-loop in coarsened space; this proxy has no approximation guarantee, and Theorem 2 covers only the full, unbatched propagation, so the scalability claim rests on that proxy not corrupting learned representations.","fun_headline_variants_meta":{"raw":{"variants":["Coarsen plus cluster: best of both GNN worlds","Split GNN propagation: coarsened long-range plus local detail","Parallel propagations crack long-range GNN bottleneck","Hybrid GNN keeps memory low, long-range accuracy high","Two-speed GNN: coarsened and local passes in parallel"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000159,"raw_usage":{"total_tokens":1094,"prompt_tokens":801,"completion_tokens":293,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":545,"completion_tokens_details":{"reasoning_tokens":208}},"tokens_in":545,"tokens_out":293,"duration_ms":4367,"temperature":1.0,"reasoning_tokens":208,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T14:37:21.183982+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train CoRe-GNN in full-batch and batched mode on a graph that fits in GPU memory (e.g., Cora or PubMed) with identical hyperparameters and measure test accuracy and training loss trajectories; if the batched variant's accuracy is substantially lower or its loss fails to track the full-batch run, the self-loop proxy is not harmless. A more direct check: compute the per-layer difference between the proxy update and the exact batched update for random cluster batches; if the error grows without bound as layers increase, the proxy does not preserve propagation.","supporting_citations":[],"review_version":1}