{"id":"82f7ed16-f310-4e82-b525-eec2259b1a09","arxiv_id":"2504.18082","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"COMM-RAND creates community-aware randomized mini-batches for GNN training, cutting training time by 1.8x on average with negligible accuracy loss.","lead":"This paper introduces COMM-RAND, a way to build GNN training mini-batches that mixes graph community structure with randomness. It reports 1.8x average training speedup (up to 2.76x) with accuracy within about 0.4 percentage points of standard random mini-batching.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Headline speedup may be explained by reduced per-batch feature footprint rather than community-locality caching; no random baseline with matched subgraph size is tested.","rationale":"The paper is a careful empirical systems study: it includes a full knob sweep, averages over five seeds, tests sensitivity to L2 capacity and a software-managed cache, accounts for reordering overhead on reddit, and compares against LABOR and ClusterGCN. I do not see an internal inconsistency or a fraudulent claim. My concern is with the interpretation and generality of the headline speedups. The best knob configuration is selected on the same datasets used to report the headline, and the proposed mechanism is supported mainly by a correlation between per-epoch time and average feature size. Because p=1.0 restricts neighbor sampling to intra-community edges, the feature footprint shrinks by construction; without a random baseline matched on footprint, the paper cannot distinguish 'smaller subgraphs are faster' from 'community locality improves cache reuse.' Both are plausible, but the former would weaken the novelty and change the appropriate baseline for the accuracy comparison. This concern is concrete and testable, so the conditional verdict should be retained pending the matched-footprint experiment, but I would not move to accept or reject based on the current evidence.","tokens_in":18808,"tokens_out":10758,"duration_ms":121130,"concrete_test":"Run the uniform-random GraphSAGE baseline (RAND-ROOTS, p=0.5) with fanout reduced per dataset so that the average per-batch input feature footprint matches COMM-RAND (COMM-RAND-MIX-12.5%, p=1.0) on each of the four benchmarks. Compare per-epoch time, epochs-to-convergence, final validation accuracy, and total training time. If the reduced-fanout baseline reproduces the per-epoch speedups and has no worse accuracy at matched feature footprint, the speedup claim is not attributable to structure-aware caching; if it does not reproduce the speedups, the concern is refuted. The same experiment should also report per-seed error bars for the accuracy and speedup numbers.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline figure is obtained after sweeping the two COMM-RAND knobs on the same four datasets and then selecting the configuration with the best average total speedup, without reporting seed-level error bars on either the speedup or the accuracy gap. This makes the 1.8x/0.42pp headline harder to interpret as a reproducible default. More substantively, the paper's causal story in Section 6.1.1 is underdetermined: Figure 6 shows per-epoch time is nearly linear in average input feature size, but that size is itself a deterministic output of the sampling policy. With p=1.0, inter-community edges are given zero probability, so per-batch neighborhood expansion shrinks sharply; a uniform-random baseline with an equally reduced feature footprint (for example, lower fanout or smaller batches) would be expected, under the paper's own correlation, to show the same per-epoch time reduction. No such matched-footprint baseline is run. The reported speedup could therefore be a consequence of smaller subgraphs and less feature traffic rather than of community bias improving cache reuse, and the accuracy comparison against fanout=10 random mini-batching is not the comparison that isolates the contribution of structure awareness.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes COMM-RAND, a mini-batch construction method for GNN training that introduces community-structure bias into both root-node partitioning and neighborhood sampling, with two user-controlled knobs: k (number of communities mixed before randomization, as a percentage) and p (probability of sampling intra-community edges). The method is evaluated on four graph benchmarks (reddit, igb-small, ogbn-products, ogbn-papers100M) with 3-layer GraphSAGE, plus GCN and GAT on reddit. The authors report up to 2.76x (1.8x on average) total training speedup with accuracy within 1.79 percentage points (0.42 on average) of uniform random mini-batching, and include studies on hyperparameter tuning budgets, comparisons to LABOR and ClusterGCN, software-cache sensitivity, and L2 cache capacity sensitivity. The central claim is that a controlled mix of randomization and community structure improves per-epoch efficiency, mainly through reduced input feature footprint and improved cache reuse, without materially harming convergence or accuracy.","tokens_in":19057,"tokens_out":5621,"duration_ms":53625,"significance":"If validated, COMM-RAND would be a practical, low-effort optimization for GNN training on graphs with community structure, with immediate applicability in existing frameworks like DGL. The paper's strengths include a clean operationalization of the randomization-structure trade-off, extensive empirical coverage across datasets, models, ablations, a hyperparameter-budget experiment (Section 6.2) that accounts for tuning costs, and direct evidence of improved cache reuse in the software-cache miss rates of Section 6.5.1. The correlation-based mechanism story (Figures 6 and 7) is plausible, and the comparison to ClusterGCN correctly identifies a scalability weakness of partition-based mini-batching. However, the headline speedup is obtained after selecting the best knob configuration on the same four datasets used to report the number, no seed-level error bars are given, and the causal mechanism is confounded with subgraph size because no matched-footprint random baseline is tested. These issues must be addressed before the quantitative claims can be fully trusted.","major_comments":[{"comment":"The headline average total speedup of 1.8x is selected as the best among many knob combinations on the same four datasets used to report the headline, and no seed-level error bars are reported for either the speedup or the accuracy gap. Since the chosen configuration (k=12.5%, p=1.0) is a post-hoc maximum over the evaluation grid, the expected speedup of COMM-RAND under a fixed practical default is not established. Please report per-seed distributions, and either validate the selected configuration on held-out datasets or justify a fixed default configuration from the trade-off analysis rather than from the test-set maximum.","section":"Section 6.1.3, Figure 5"},{"comment":"The claim that COMM-RAND's per-epoch speedup comes from community-aware cache reuse is confounded by subgraph size. The average input feature size in Figure 6 is a deterministic output of the same knobs that define each configuration, and with p=1.0 the subgraph shrinks sharply because inter-community edges are given zero sampling probability. Under the paper's own near-linear correlation (r=0.90-0.99), a uniform-random baseline with a matched average feature footprint (for example, lower fanout or smaller batch size) would be expected to achieve the same per-epoch time reduction. No such matched-footprint baseline is run, so the observed speedup may be entirely attributable to reduced feature traffic rather than to structure-aware locality. Please add an ablation that matches the average feature size between uniform random mini-batching and COMM-RAND, or otherwise controls for subgraph size.","section":"Section 6.1.1, Figure 6"},{"comment":"The causal role of cache reuse is inferred from correlations with feature size, but the main experiments do not directly measure on-chip cache hit rates or memory traffic. The software-cache miss rates in Section 6.5.1 provide direct evidence for only ogbn-papers100M and a single cache configuration. To support the mechanism claim, please report cache miss rates or memory traffic for the main configurations across the other datasets, or otherwise test the cache-reuse mechanism independently of the subgraph-size effect.","section":"Section 6.1.1 and Section 6.5.1"}],"minor_comments":[{"comment":"The phrase 'provides the higher average total training speedups' is grammatically incorrect; it should be 'provides the highest average total training speedup' or similar.","section":"Section 6.1.3"},{"comment":"The accuracy subplots use truncated y-axes that start away from zero, which visually exaggerates the differences between configurations; please either use a full-scale axis or explicitly state the axis range in the caption to avoid misleading the reader.","section":"Figure 5"},{"comment":"The baseline for the ClusterGCN comparison runs on the original graph ordering while COMM-RAND runs on the community-reordered graph, so the per-epoch speedups in Table 4 conflate reordering benefits with the effect of COMM-RAND itself; please clarify how much of the speedup comes from reordering alone, especially since Section 3 reports that reordering alone gives only a 3% average training-time improvement.","section":"Section 6.3, Table 4"},{"comment":"The MIG-based L2 cache sensitivity study also changes the number of SMs and the memory bandwidth along with the L2 capacity; the authors acknowledge this, but a cleaner experiment such as a cache simulator or a configuration that isolates L2 capacity would make the claim about cache-capacity sensitivity more robust.","section":"Section 6.5.2"},{"comment":"References [32] and [33] appear to be the same paper with different formatting; please deduplicate them, and consider citing the original METIS paper rather than a multithreaded partitioning library as the source for METIS.","section":"References"},{"comment":"The column 'No. of Epochs' reports fractional values (641.8 and 987.6); please clarify whether these are averages over the five seeds, and if so, report the variance across seeds.","section":"Table 3"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid empirical systems contribution with a useful framing of the randomization-structure trade-off. The main revisions are focused: add error bars, validate the knob selection or use a principled default, and add a matched-footprint random baseline to isolate the cache-locality mechanism. If these are addressed, the paper could be suitable for publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Zeynep — quick take on 2504.18082 (COMM-RAND). It's a well-executed systems study of structure-aware randomized mini-batching for GNN training. The core contribution is two controllable knobs: mixing k% of communities when partitioning root nodes, and biasing neighborhood sampling toward intra-community edges with probability p. That construction is new relative to ClusterGCN, which randomizes at partition granularity but not within, and the paper is honest about the difference. The empirical sweep is broad: four datasets, three models, plus ablations on cache sensitivity, hyperparameter budget, and comparison to LABOR and ClusterGCN. The 1.8x average total training speedup with 0.42pp average accuracy loss is plausible and useful for practice.\n\nThe soft spots are real but not fatal. First, the headline configuration (MIX-12.5%, p=1.0) is selected by sweeping knobs on the same four benchmarks used to report it. They disclose other settings, so it's not hidden, but the best-case number shouldn't be treated as a default. No error bars on speedups or accuracy gaps either. Second, and more substantively, the mechanism claim in Section 6.1.1 is underdetermined. Figure 6 shows per-epoch time tracks the average feature size per batch. But feature size is a deterministic function of the sampling policy. With p=1.0, inter-community edges are never sampled, so the subgraph footprint shrinks; a uniform-random baseline with matched feature footprint (e.g., lower fanout or smaller effective neighborhood) would likely show a similar per-epoch reduction under the paper's own correlation. Without such a baseline, the speedup is not cleanly attributable to community bias improving cache reuse versus simply doing less feature fetch. This does not sink the contribution—a method that reduces work while preserving accuracy is still valuable—but it means the causal story is weaker than the paper implies.\n\nAlso, no code is released, which matters for a systems paper whose main evidence is empirical.\n\nWould I engage with it? Yes. The idea is clean, the evaluation is extensive, and the questions about matched baselines and error bars are exactly what a good referee would push on. It deserves a serious peer review with requests for a matched-footprint baseline, error bars, and code release. I'd bring it to the reading group as an example of a solid systems contribution whose evaluation could be tightened.","headline":"Solid systems paper with a clean two-knob idea; the headline speedup is credible but the mechanism claim is underdetermined by a missing matched-footprint baseline.","tokens_in":19555,"tokens_out":3066,"would_cite":true,"duration_ms":27475,"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":"The paper claims that COMM-RAND, a mini-batching scheme that biases randomization toward graph communities, cuts GNN training time by up to 2.76x (1.8x on average) while keeping final validation accuracy within 1.79 percentage points…","keywords":["graph neural networks","mini-batch training","community structure","graph reordering","cache locality","randomized batching","sampling bias","training speedup"],"falsifier":"Run the same comparison on a random graph with no community structure (where community-biased sampling cannot reduce the per-batch feature footprint). If per-epoch speedups remain large, the proposed mechanism is not the cause; alternatively, reduce the feature dimension to 1, which should collapse the correlation shown in Figure 6 and bring speedups down toward 1.0x.","tokens_in":18643,"feed_emoji":"🕸️","tokens_out":8533,"duration_ms":75775,"temperature":0.7,"pith_summary":"The paper claims that the randomization used in GNN mini-batch training can be made community-aware without sacrificing accuracy, and that doing so accelerates training substantially. It proposes COMM-RAND, which biases two steps—how root nodes are split into batches and how neighbors are sampled—so that batches mostly stay within graph communities. On four benchmarks, this reduces training time by up to 2.76x (1.8x average) with final accuracy within 1.79 percentage points (0.42 average) of uniform-random mini-batching. The practical promise is that practitioners can trade a small, controlled amount of randomness for large per-epoch speedups.","feed_headline":"Community-aware batching cuts GNN training up to 2.76x","feed_subtitle":"Biased mini-batching keeps accuracy within 1.79 points while shrinking per-batch feature footprint.","key_machinery":"The mechanism is community-aware biased randomization, applied to both steps of mini-batch construction. In root partitioning, each community is a block that is shuffled as a whole and internally; a knob mixes a percentage of communities into super-blocks to increase randomness. In neighborhood sampling, intra-community edges are sampled with probability p and inter-community edges with 1-p. What carries the argument is that these two biases shrink the average per-batch subgraph footprint, lowering the volume of input features fetched from memory; the paper shows a strong correlation (r=0.90–0.99) between that footprint and per-epoch time.","core_discovery":"COMM-RAND shows that the trade-off between randomized and structure-aware mini-batching is not binary. Root nodes are partitioned by shuffling community blocks (and optionally mixing a fixed percentage of communities into super-blocks), and neighbors are sampled with probability p for intra-community edges versus 1-p for inter-community edges. This constrained randomization keeps batches locally dense while still changing every epoch. The paper reports that, across four graphs, per-epoch time tracks the average size of the input feature matrix fetched per batch (Pearson r = 0.90–0.99), and the best knob setting yields total training speedups of 1.8x on average and up to 2.76x, with an average final-accuracy drop of 0.42 percentage points and a maximum drop of 1.79.","pith_inferences":["If feature-fetch cost is the true bottleneck, the same community-block shuffling idea could be exported to other subgraph-based models—graph transformers, heterogeneous GNNs—where 'communities' are replaced by any partition of the node set that improves cache reuse.","The paper leaves open whether the knobs can be set automatically; a natural testable extension is to use the per-epoch feature size as a cheap proxy objective and tune the knobs online during training.","Because the correlation between per-epoch time and feature footprint is so strong, the method's benefit should grow with feature dimensionality and graph locality; on datasets with tiny feature vectors or hardware with very large caches, the advantage is likely to shrink."],"forward_implications":["With a fixed wall-clock budget, COMM-RAND trains more epochs than uniform-random mini-batching and can end up with better test accuracy (shown on reddit: 1.54x more epochs, +0.27 points).","The speedup widens as the problem size relative to on-chip cache grows; smaller L2 partitions and software-managed caches both amplify COMM-RAND's advantage.","The benefit transfers beyond GraphSAGE: on reddit, GCN training is 2.03x faster overall and GAT 1.38x faster, with accuracy within 1 point.","Unlike prior graph-partitioning based mini-batching, COMM-RAND keeps its speedups when only a small fraction of nodes is labeled, because it only builds subgraphs from the training set's neighborhoods.","The two knobs define a continuum: users who care about fewest epochs can choose near-uniform settings, while users with tight compute budgets can push toward community-only batches and accept slightly slower convergence."],"supporting_citations":[{"why":"Its community-detection and reordering algorithm provides the node-to-community memberships that COMM-RAND's biased partitioning requires.","marker":"[5]"},{"why":"It is the prior structure-aware mini-batching method that COMM-RAND is compared against and shown to improve upon for small training sets.","marker":"[14]"},{"why":"It provides the neighbor-sampling interface with per-edge probabilities, which is how the biased intra/inter-community sampling is implemented.","marker":"[15]"},{"why":"It introduced uniform-random neighbor-sampling mini-batching, the baseline that COMM-RAND modifies and measures speedups against.","marker":"[24]"},{"why":"It is the source of two of the four evaluation graphs, including the large ogbn-papers100M graph.","marker":"[25]"},{"why":"It is the source of the reddit dataset used in the accuracy, convergence, and hyperparameter-tuning experiments.","marker":"[4]"}],"fun_headline_variants":["GNN training up to 2.76x faster with community batching","Community-random batching: 2.76x GNN speedup, tiny accuracy loss","Structure-aware mini-batching makes GNN training 2.76x quicker","Biased batching: 2.76x faster GNN training","Randomized structure batching speeds GNNs 2.76x"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The speedups rest on the assumption that per-epoch training time is dominated by the amount of input feature data fetched for each batch; if feature fetching is not the bottleneck on a given platform or graph, the speedups may shrink or disappear.","fun_headline_variants_meta":{"raw":{"variants":["GNN training up to 2.76x faster with community batching","Community-random batching: 2.76x GNN speedup, tiny accuracy loss","Structure-aware mini-batching makes GNN training 2.76x quicker","Biased batching: 2.76x faster GNN training","Randomized structure batching speeds GNNs 2.76x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000394,"raw_usage":{"total_tokens":2080,"prompt_tokens":970,"completion_tokens":1110,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":586,"completion_tokens_details":{"reasoning_tokens":1008}},"tokens_in":586,"tokens_out":1110,"duration_ms":9864,"temperature":1.0,"reasoning_tokens":1008,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:24:16.698390+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same comparison on a random graph with no community structure (where community-biased sampling cannot reduce the per-batch feature footprint). If per-epoch speedups remain large, the proposed mechanism is not the cause; alternatively, reduce the feature dimension to 1, which should collapse the correlation shown in Figure 6 and bring speedups down toward 1.0x.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Its community-detection and reordering algorithm provides the node-to-community memberships that COMM-RAND's biased partitioning requires."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It provides the neighbor-sampling interface with per-edge probabilities, which is how the biased intra/inter-community sampling is implemented."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It introduced uniform-random neighbor-sampling mini-batching, the baseline that COMM-RAND modifies and measures speedups against."},{"cited_title":"RedditDataset-DGL","cited_arxiv_id":null,"evidence_quote":"It is the source of the reddit dataset used in the accuracy, convergence, and hyperparameter-tuning experiments."}],"review_version":1}