acceptodds
Under review as a conference paper at ICLR 2027

LabStA: Label- and Structure-Aware Mini-Batch Sampling for Node Classification with Graph Transformers

Abstract

Scalability is a major challenge in graph representation learning, as training on large-scale graphs may require processing millions of nodes that do not fit within limited GPU memory. For Graph Neural Networks (GNNs), mini-batch training provides a practical alternative to full-graph training, typically using connectivity-oriented sampling methods that preserve local connectivity for message passing. However, mini-batch construction for Graph Transformers (GTs) remains underexplored, and many prior works rely on simple random node sampling, which can lead to suboptimal performance. In this work, we motivate two key objectives for mini-batch sampling in GT-based node classification: reducing class-distribution discrepancy and increasing edge retention rate. Based on these objectives, we propose LabStA, a Label- and Structure-Aware mini-batch sampling method that augments graph partitions with informative virtual nodes to jointly improve class-distribution alignment and edge preservation. Experiments on diverse node classification benchmarks show that LabStA outperforms existing sampling baselines on most dataset–backbone pairs, especially on heterophilous graphs.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Transformers, Graph Sampling, Mini-Batch Training, Scalable Graph Learning, Node Classification

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_TL5rOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the challenge of large-scale graph mini-batch training for Graph Transformers (GT) by proposing LabStA, a label- and structure-aware sampling method. The authors point out that GT relies on both global self-attention and local message passing; therefore, the sampling process must take into account both the class distribution and the graph structure. To this end, LabStA introduces virtual nodes based on the ClusterGCN graph partitioning method. By reducing the category distribution discrepancy (CDD) between the mini-batch and the full graph and improving the edge retention rate (ERR), LabStA enhances the category and structural information within the mini-batch. Experiments were conducted across various matched and mismatched datasets and multiple GT backbones. The results demonstrate that this method outperforms existing sampling strategies in most settings and exhibits a more pronounced advantage on mismatched graphs.

Critical strengths

· This paper investigates the mini-batch sampling problem for Graph Transformers, rather than directly adopting sampling strategies designed for traditional message-passing GNNs. By using CDD and ERR to address the requirements of global self-attention and local message passing, respectively, the research motivation is quite clear.

· The design of LabStA is relatively simple and offers a degree of generality. The method does not require modifications to the Graph Transformer’s network architecture; instead, it adds virtual nodes to the ClusterGCN partition, allowing it to be directly applied to different architectures such as GraphGPS, SGFormer, and Polynormer.

· The experimental setup is comprehensive. The paper considers both matched and mismatched graphs as well as large-scale graphs, and validates the method on multiple GT backbones. Furthermore, the authors verify the roles of each component of the method through CDD/ERR analysis, sensitivity experiments on the virtual-node ratio, and ablation experiments such as CDD-only and ERR-only.

Critical weaknesses

· The core methodological innovations of LabStA are relatively limited. The overall framework is still based on the graph partitioning of ClusterGCN, with the main improvement being the addition of virtual nodes to existing partitions based on class deficits and node-partition connectivity. Therefore, compared to ClusterGCN, its primary innovations are concentrated in partition augmentation and node selection strategies; the novelty at the algorithmic level needs to be further enhanced.

· The method relies heavily on class information. LabStA calculates the class deficit for each partition based on the class distribution across the entire graph, while for validation and test nodes, it generates pseudo-labels based on their distance from the training class feature centers. When training labels are very sparse, classes are severely imbalanced, or node features exhibit weak class separability, the estimation of class distributions and the generation of pseudo-labels may be unreliable; however, current experiments have not fully analyzed this issue.

· The performance gains in some experimental results are modest. On mismatched graphs, LabStA’s average improvement over ClusterGCN is only 1.02, 0.38, and 0.96 percentage points on GraphGPS, SGFormer, and Polynormer, respectively; on some matched datasets, LabStA also does not achieve the best results—for example, on GraphGPS, its performance on Cora and CiteSeer is significantly lower than that of GraphSAINT. Therefore, the conclusion that the model is “widely applicable to different GTs” should be interpreted with caution.

· Large-scale experiments do not sufficiently validate the model’s generality. Although the paper conducted experiments on ogbn-arxiv, ogbn-products, and pokec, these experiments used only GraphGPS, while the previously mentioned SGFormer and Polynormer were not included in the large-scale experiments. Therefore, it cannot yet be fully demonstrated that LabStA possesses stable scalability and performance advantages across all combinations of “large-scale graphs + different GT architectures.”

Questions for authors

· LabStA uses trained node classes and pseudo-labels generated based on class feature centers to estimate class deficit and select virtual nodes. Is CDD optimization still effective when the labeling rate is further reduced or the accuracy of pseudo-labels is low? We recommend that the authors conduct additional experiments under different labeling rates and analyze the impact of pseudo-label quality on the final performance.

· LabStA’s performance gains are relatively limited on some datasets; for example, on the Heterogeneous Graph dataset, the average improvement over ClusterGCN ranges from approximately 0.38 to 1.02 percentage points across different backbones. Could the authors provide further statistical significance analysis and clarify whether these improvements consistently exceed the fluctuations caused by random seeds?

· The paper emphasizes that LabStA is a model-agnostic GT sampling method, but the experiments on the three large-scale datasets only used GraphGPS. Could the authors supplement the analysis with large-scale experiments on at least one other GT backbone (such as SGFormer or Polynormer) to further validate the method’s model-agnostic nature and scalability?

2 comments
AuthorsOpenReview ↗

Author response to reviewer TL5r

We thank the reviewer for the constructive feedback.

W1. Methodological contribution

While LabStA builds upon ClusterGCN's graph partitioning framework, its methodological contribution lies in jointly addressing two key sampling objectives, CDD and ERR, through class-aware partition augmentation and connectivity-aware node selection. Unlike more sophisticated methods that rely on model-specific attention or hierarchical components [1,2], LabStA employs simple, architecture-independent mechanisms that can be applied to diverse GT backbones without modification. We believe that this combination of targeted sampling objectives, simplicity, and broad applicability constitutes a meaningful methodological contribution, as recognized by other reviewers.

W2/Q1. Labeling rate vs. CDD

We thank the reviewer for suggesting an additional experiment to evaluate the effectiveness of CDD optimization across different labeling rates. Figure 8 (App. E.6) compares CDD between ClusterGCN and LabStA across labeling rates of $\lbrace 0.01,0.02,0.05,0.1,0.2,0.5\rbrace $. Although the CDD gap narrows as the label ratio decreases, LabStA consistently achieves lower CDD than ClusterGCN, suggesting that it effectively reduces CDD even with limited training labels.

Furthermore, the main results on Cora, CiteSeer, and PubMed (Tab. 1) provide evidence of LabStA's effectiveness even with limited labeled data. Under the official semi-supervised splits (20 labeled nodes per class), LabStA outperforms ClusterGCN across all settings. These improvements are consistent with the benefits of CDD reduction, as connectivity-oriented sampling can result in high CDD on homophilous graphs (Fig. 5).

W3/Q2. Statistical significance

On the five heterophilous datasets, LabStA achieves higher mean accuracy than Random, GraphSAINT, and ClusterGCN in 15/15, 15/15, and 14/15 dataset–backbone settings, with average gains of +5.80%p, +4.39%p, and +0.79%p, respectively. Two-sided Welch's tt-tests (p<0.05p<0.05) based on 10 runs per setting identify significant improvements in 11, 11, and 3 settings, respectively. These results show statistically significant improvements over Random and GraphSAINT in many settings. While gains over ClusterGCN are less frequently significant, the higher mean accuracy in 14/15 settings supports LabStA's effectiveness on heterophilous graphs.

W4/Q3. Large-scale experiments

Originally, our large-scale experiments take a very long time, primarily due to the cost of full-graph inference. To address this, we are conducting additional experiments with SGFormer and Polynormer using a reduced training budget of 500 epochs. We will update our response as the remaining results become available.

Table A. Large-scale experiments on SGFormer and Polynormer.

ModelSamplerogbn-arxivogbn-productspokec
SGFormerRandom59.51 ± 0.2867.51 ± 0.2056.47 ± 4.66
GraphSAINT65.84 ± 0.2176.13 ± 0.1854.74 ± 1.58
ClusterGCN65.51 ± 0.5475.73 ± 0.4860.32 ± 0.60
LabStA (ours)67.05 ± 0.4776.83 ± 0.9561.49 ± 0.22
PolynormerRandom66.65 ± 0.43―63.94 ± 0.26
GraphSAINT71.54 ± 0.38―73.10 ± 1.03
ClusterGCN70.73 ± 0.51―78.01 ± 0.65
LabStA (ours)71.92 ± 0.21―79.35 ± 1.12

Current results on ogbn-arxiv and pokec show that LabStA outperforms all evaluated baseline samplers with both SGFormer and Polynormer. Partial results on ogbn-products with SGFormer further support the effectiveness of LabStA across different GT backbones.

References

[1] Zaixi Zhang, Qi Liu, Qingyong Hu, and Chee-Kong Lee. Hierarchical Graph Transformer with Adaptive Node Sampling. NeurIPS, 2022.

[2] Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C. Bayan Bruss, and Tom Goldstein. GOAT: A Global Transformer on Large-scale Graphs. ICML, 2023.

AuthorsOpenReview ↗

Gentle Follow-up on Author Response

Dear Reviewer,

Thank you again for your constructive feedback on our submission.

As the author–reviewer discussion period is approaching its end, we would greatly appreciate it if you could review our rebuttal and share any remaining questions or concerns.

We would be happy to provide further clarification if needed.

Thank you for your time and consideration.

Best regards,
The Authors

Reviewer_16qSOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates mini-batch construction for Graph Transformers that combine global attention with local message passing. It motivates two sampling objectives: reducing class-distribution discrepancy (CDD) between mini-batches and the full graph, and increasing edge retention rate (ERR). The proposed LabStA method augments ClusterGCN partitions with existing graph nodes treated as virtual context nodes. These nodes are selected from underrepresented classes, with selection probabilities favoring strong connectivity to the target partition. Unlabeled nodes receive pseudo-labels based on their distances to training-class feature means, and augmented nodes participate in propagation but are excluded from the supervised loss.

Experiments cover ten small- and medium-scale datasets with three GT backbones, plus three large-scale datasets with GraphGPS. LabStA generally improves over ClusterGCN and achieves the strongest average performance in most reported settings.

The problem is practically relevant, the method is simple, and the empirical coverage is substantial. However, important details concerning label-distribution estimation, the connection between the theoretical analysis and actual mini-batch computation, pseudo-label robustness, and resource efficiency remain insufficiently established.

Critical strengths

Useful distinction between attention and message-passing requirements. The paper identifies a meaningful tension: preserving local connectivity does not necessarily produce representative attention contexts. The controlled experiments provide useful motivation for considering both CDD and ERR.

Simple and reusable design. LabStA operates at the sampling level without requiring architectural changes to the evaluated GT backbones. Using augmented nodes as context rather than additional supervised targets is a sensible design choice.

Broad evaluation and relevant controls. The paper includes homophilous, heterophilous, and million-node graphs; reports repeated runs; and evaluates random, CDD-only, and ERR-only augmentation. The supplementary analysis of cases where GraphSAINT performs better is also appreciated.

Critical weaknesses
  1. The operational estimation of class distributions is not sufficiently specified.

The method seeks to match each partition to the full-graph class distribution, but the stated transductive setting provides labels only for training nodes. Section 5 explains how pseudo-labels are assigned to unlabeled candidate nodes, yet it does not clearly specify how the target full-graph distribution and the initial partition-level class histograms are estimated. Are these statistics computed from training labels only, from training labels combined with pseudo-labels, or from another estimator? This distinction matters when the labeled subset is small or has a different class distribution from the full graph. The paper should also distinguish the statistics available to the sampler from true-label CDD values used only for post-hoc evaluation.

Please provide explicit equations or pseudocode for the class-deficit calculation, allocation of the virtual-node budget across deficient classes, and treatment of insufficient candidates. These are central algorithmic details, not merely implementation choices. The concern is not the use of unlabeled-node features or edges, which is consistent with the transductive setting, but the provenance of the label statistics used to construct batches.

  1. Practical efficiency and resource-matched comparisons are insufficient.

Scalability is a central motivation, but the paper reports accuracy and asymptotic preprocessing complexity without measured preprocessing time, training throughput, peak memory, or time to a selected validation checkpoint.

Table 3’s random-augmentation control already helps rule out a simple “more nodes” explanation for the selection strategy. However, practical comparisons with ClusterGCN still require accuracy–time and accuracy–memory measurements under matched budgets. Full-graph CPU inference costs should be reported separately, since Appendix C identifies them as a substantial evaluation overhead.

Questions for authors

How are the target class prior and partition histograms estimated without access to validation/test ground-truth labels?

How closely do CDD and union-based ERR track actual per-node discrepancies between mini-batch and full-graph computation?

3 comments
AuthorsOpenReview ↗

Author response to reviewer 16qS

We thank the reviewer for the constructive feedback.

W1/Q1. Algorithmic details

We apologize for omitting important algorithmic details from the original submission. To address this, we have added pseudocode for the overall LabStA algorithm (Alg. 1) in Appendix F.

We clarify the requested details below, with line references to Alg. 1.

  • Class estimation (lines 5–7 and 10):

The target class prior and partition histograms are derived from training-label frequencies:

πc=∣Tc∣∣Vtr∣,(Tc={v∈Vtr:yv=c}),\pi_c = \frac{|T_c|}{|V_{tr}|}, \quad (T_c = \lbrace v\in V_{tr}:y_v=c\rbrace ),

np,c=∣Vp∩Tc∣,(Vp: node set of partition p).n_{p,c} = |V_p \cap T_c|, \quad (V_p:\text{ node set of partition }p).

We acknowledge that the training-label distribution may differ from the full-graph class distribution, particularly when the labeled subset is small. Nevertheless, Figure 8 (App. E.6) shows that LabStA consistently achieves lower CDD than ClusterGCN across varying label ratios, suggesting that it effectively reduces CDD even with limited training labels.

  • Budget allocation (lines 9 and 11–20):

The virtual-node budget is allocated proportionally to positive class deficits:

Dp=∑cdp,c,rp,c=bpdp,cDp(Dp>0).D_p = \sum_c d_{p,c}, \qquad r_{p,c} = \frac{b_p d_{p,c}}{D_p} \quad (D_p\gt 0).

Integer rounding is performed using the largest remainder method:

kp,c=⌊rp,c⌋,m=bp−∑ckp,c,k_{p,c} = \lfloor r_{p,c}\rfloor, \qquad m = b_p-\sum_c k_{p,c},

Cm=TopKc:dp,c>0(rp,c−⌊rp,c⌋,m).C_m = TopK_{c:d_{p,c}\gt 0} (r_{p,c}-\lfloor r_{p,c}\rfloor,m).

kp,c←kp,c+1(c∈Cm).k_{p,c}\gets k_{p,c}+1 \quad(c\in C_m).

  • Insufficient candidates (lines 27–33):

We first sample same-class nodes from outside the partition, using their positive connectivity scores as sampling weights:

a=min⁡{kp,c,∣A∣},S=SampleWOR⁡(A,a; wv=sp(v)).a=\min\lbrace k_{p,c},|A|\rbrace , \qquad S=\operatorname{SampleWOR}(A,a;\,w_v=s_p(v)).

If these candidates are insufficient, we fill the remaining slots with zero-connectivity nodes, where available:

z=min⁡{kp,c−∣S∣,∣Z∣},U=SampleWOR⁡(Z,z; wv=1).z=\min\lbrace k_{p,c}-|S|,|Z|\rbrace , \qquad U=\operatorname{SampleWOR}(Z,z;\,w_v=1).

Q2. Per-node discrepancies

To assess how closely CDD and ERR track per-node computational discrepancies, we adapt the experimental settings of Figures 2 and 3 to measure differences between mini-batch and full-graph node representations. Specifically, we train a model on the full graph and freeze its parameters. We then construct mini-batches with varying CDD or ERR values using the sampling methods described in Section 4 and compare the resulting node representations with their full-graph counterparts.

Figure 7 (App. E.3) shows how representation discrepancies (DrepD_{rep}) in GraphGPS vary with CDD and ERR. As CDD increases, DrepD_{rep} increases, consistent with greater mismatch in global self-attention candidates. Similarly, as ERR decreases, DrepD_{rep} increases, consistent with greater mismatch in local message-passing neighborhoods. These results suggest that CDD and ERR capture meaningful differences between mini-batch and full-graph computation, further supporting their use as mini-batch sampling objectives for GT-based node classification.

W2. Scalability analysis

To assess the practical efficiency of LabStA, we have added a scalability analysis in Section 6.6. Table 4 compares the preprocessing time, per-epoch training time, and peak memory of ClusterGCN and LabStA across large-scale benchmarks under matched resource budgets. Relative to ClusterGCN, LabStA increases preprocessing time by an average of 22.1% while reducing per-epoch training time by 1.7%. Although preprocessing incurs additional overhead, its contribution to total execution time is minor because it is performed only once before training. Peak GPU memory usage changes by +1.1% (ogbn-arxiv), -17.4% (ogbn-products), and +0.8% (pokec), indicating that LabStA does not consistently increase memory consumption under matched node budgets.

In addition to the time and memory measurements, we conduct an experiment comparing ClusterGCN and LabStA under matched resource budgets. Table 12 (App. E.5) compares the two methods using GraphGPS with $q \in \lbrace 1,2,4,8\rbrace $, 500 training epochs, and evaluation every 50 epochs, with results averaged over three runs. LabStA outperforms ClusterGCN on most datasets under matched total node budgets, supporting our claim that its gains are not simply due to larger mini-batches.

Thank you for the clarifications and additional experiments. Overall, my main concerns are substantially alleviated, and I raise my recommendation to Weak acceptance.

Dear Reviewer,

Thank you for taking the time to consider our rebuttal and for your positive reassessment of our work. We sincerely appreciate your thoughtful feedback and engagement throughout the review process.

Best regards,
The Authors

Reviewer_zNWWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates mini-batch construction for graph Transformers with local message passing. It motivates two statistics: class-distribution discrepancy (CDD) and edge retention rate (ERR). LabStA augments graph partitions with existing nodes that participate in attention and message passing but are excluded from the supervised loss. Candidates are restricted to underrepresented classes, using feature-prototype pseudo-labels for unlabeled nodes, and sampled according to connectivity to the partition. Experiments cover three backbones on ten small/medium benchmarks and GraphGPS on three large graphs. Reported improvements over ClusterGCN average 0.380.38–1.021.02 percentage points across the heterophilous datasets, with a 0.790.79-point average gain on the large-graph suite. Appendix A provides conditional perturbation bounds for attention and message passing.

Critical strengths
  1. A relevant sampling problem with a clear architectural motivation. The paper distinguishes the candidate-distribution requirements of global attention from the edge requirements of local propagation. The comparison of GAT, a pure Transformer, and GraphGPS in Figs. 2–3 is a useful way to investigate these effects. This provides a concrete reason to study sampling beyond transferring an existing GNN sampler unchanged.

  2. A simple method evaluated across several backbones and graph scales. The augmentation can be applied without modifying the backbones, and Tables 1–2 show broadly positive results, including million-node graphs. Table 3 includes random, CDD-only, and ERR-only virtual-node controls, so the paper makes an effort to distinguish joint selection from merely adding nodes. The theoretical discussion also explicitly acknowledges that its bounds do not imply monotonic accuracy improvement.

Critical weaknesses
  1. The operational definition of label-distribution alignment is incomplete. Section 5.1 and Fig. 4 define the deficit relative to the full-graph class distribution, while Section 3.1 assumes that only training labels are observed. The paper explains how it assigns pseudo-labels to validation/test candidates, but does not give an explicit estimator for the full-graph distribution or a formula for the per-class deficit under the fixed virtual-node budget. It also leaves unclear whether partition histograms use observed labels, pseudo-labels, or a combination, and how shortages in a deficient class are handled. These are central algorithmic choices, especially when training and full-graph class proportions differ. The true-label CDD used for evaluation can be a legitimate diagnostic, but it must be distinguished from the quantities available to the sampler. I cannot determine from the manuscript alone whether the implemented procedure follows one unambiguous, training-label-only specification.

  2. The practical gain under a matched resource budget is insufficiently established. Scalable training is the motivation, but the experiments provide accuracy and asymptotic preprocessing complexity without measured preprocessing time, training time, or peak memory. Appendix C states that batch size is fixed across samplers, while Section 5 describes augmentation and Table 3 tests enlarged batches; the accounting of original versus virtual nodes needs to be explicit. Table 3 is valuable but reports single accuracy values without run variability, and the large-scale comparison uses only GraphGPS. Given the relatively modest gains over ClusterGCN, it remains unclear whether the joint selection improves the accuracy–cost trade-off at fixed total tokens/edges or fixed memory, including the O(∣V∣ ∣C∣ d)O(|V|\,|\mathcal{C}|\,d) pseudo-labeling stage. This evidence is needed to assess whether the accuracy gains justify the additional sampling cost.

Questions for authors
  1. Clarification: estimating the global class distribution. How is the full-graph class distribution used in Section 5.1 estimated when only training labels are observed? Is it computed from training-label frequencies, pseudo-labels over the graph, or another estimator? Please distinguish the quantities available to the sampler from the true-label CDD used only for offline evaluation.

  2. Clarification: the exact augmentation rule. Please provide the formulas or pseudocode for computing partition class histograms and class deficits, allocating the finite virtual-node budget across deficient classes, and handling integer rounding and insufficient candidates. These choices are central to reproducing the proposed label-distribution alignment procedure.

  3. Evidence request: reliability of the pseudo-label-based selection. How accurate is the feature-prototype pseudo-label assignment on the evaluated datasets, particularly the heterophilous graphs where LabStA shows its strongest gains? Does reducing discrepancy according to the sampler's estimated labels also reduce CDD measured using held-out ground truth? This would establish whether the intended alignment mechanism operates despite pseudo-label errors.

  4. Clarification: batch-size accounting. Does the fixed mini-batch size BB in Appendix C include the virtual nodes added with ratio ϵ=0.2\epsilon=0.2? Please report the actual numbers of original nodes, virtual nodes, and supervised training nodes per batch for LabStA and the sampling baselines. This is needed to determine whether the comparisons use equivalent computational and supervision budgets.

  5. Evidence request: measured scalability costs. On the existing large-scale benchmarks, what are the preprocessing time, training time, and peak memory of LabStA relative to ClusterGCN at matched total batch-node or memory budgets? Please include the feature-prototype assignment stage, whose cost is O(∣V∣ ∣C∣ d)O(|V|\,|\mathcal{C}|\,d) before treating class count and feature dimension as constants. These measurements would determine whether the accuracy gains justify the additional cost.

  6. Evidence request: uncertainty in the joint-selection ablation. Table 3 reports accuracy without run variability. What are the paired differences and uncertainty intervals across runs between LabStA and the random, CDD-only, and ERR-only virtual-node variants under the same augmentation budget? This is particularly relevant where the reported margins are small and would establish whether joint selection provides a consistent advantage.

3 comments
AuthorsOpenReview ↗

Author response to reviewer zNWW (1)

We thank the reviewer for the constructive feedback.

W1/Q1/Q2. Algorithmic details

We apologize for omitting important algorithmic details from the original submission. To address this, we have added pseudocode for the overall LabStA algorithm (Alg. 1) in Appendix F.

We clarify the requested details below, with line references to Alg. 1.

  • Estimating the global class distribution (lines 5–7):

We estimate the target class prior from training-label frequencies:

πc=∣Tc∣∣Vtr∣,(Tc={v∈Vtr:yv=c}).\pi_c = \frac{|T_c|}{|V_{tr}|}, \quad (T_c = \lbrace v\in V_{tr}:y_v=c\rbrace ).

  • The exact augmentation rule (lines 9–20 and 27–33):

Partition class histograms and class deficits are likewise computed using only training labels:

np,c=∣Vp∩Tc∣,n_{p,c} = |V_p \cap T_c|,

dp,c=[πc(∑jnp,j+bp)−np,c]+(bp=⌊ε∣Vp∣⌋).d_{p,c} = \lbrack \pi_c (\sum_j n_{p,j} + b_p) - n_{p,c} \rbrack _+ \quad (b_p = \left\lfloor \varepsilon |V_p| \right\rfloor).

The virtual-node budget is allocated proportionally to positive class deficits:

Dp=∑cdp,c,rp,c=bpdp,cDp(Dp>0).D_p = \sum_c d_{p,c}, \qquad r_{p,c} = \frac{b_p d_{p,c}}{D_p} \quad (D_p\gt 0).

Integer rounding is performed using the largest remainder method:

kp,c=⌊rp,c⌋,m=bp−∑ckp,c,k_{p,c} = \lfloor r_{p,c}\rfloor, \qquad m = b_p-\sum_c k_{p,c},

Cm=TopKc:dp,c>0(rp,c−⌊rp,c⌋,m).C_m = TopK_{c:d_{p,c}\gt 0} (r_{p,c}-\lfloor r_{p,c}\rfloor,m).

kp,c←kp,c+1(c∈Cm).k_{p,c}\gets k_{p,c}+1 \quad(c\in C_m).

We first sample same-class nodes from outside the partition, using their positive connectivity scores as sampling weights:

a=min⁡{kp,c,∣A∣},S=SampleWOR⁡(A,a; wv=sp(v)).a=\min\lbrace k_{p,c},|A|\rbrace , \qquad S=\operatorname{SampleWOR}(A,a;\,w_v=s_p(v)).

If these candidates are insufficient, we fill the remaining slots with zero-connectivity nodes, where available:

z=min⁡{kp,c−∣S∣,∣Z∣},U=SampleWOR⁡(Z,z; wv=1).z=\min\lbrace k_{p,c}-|S|,|Z|\rbrace , \qquad U=\operatorname{SampleWOR}(Z,z;\,w_v=1).

Q3. Pseudo-label assignment

We have added an analysis of feature-prototype-based pseudo-label assignment in Appendix E.4 (Tab. 11). Pseudo-label accuracy ranges from 0.2034 to 0.7961, reflecting differences in pseudo-labeling performance across datasets. Despite this variation, Table 11 shows that LabStA reduces both estimated and ground-truth CDD across all ten datasets. The transfer rate, defined as the proportion of partitions with reduced ground-truth CDD among those with reduced estimated CDD, ranges from 61.3% to 100.0%. These results suggest that LabStA effectively improves ground-truth class-distribution alignment despite imperfect pseudo-label assignments.

Q4. Batch-size accounting

For a mini-batch of size BB, ClusterGCN uses BB original nodes, whereas LabStA adds up to ϵB\epsilon B virtual nodes. However, virtual nodes are excluded from loss computation (Sec. 5.1), ensuring that both methods use the same supervision budget.

Q5. Measured scalability costs

We have added a scalability analysis in Section 6.6. Table 4 compares the preprocessing time, per-epoch training time, and peak memory of ClusterGCN and LabStA across large-scale benchmarks under matched total node budgets. Here, we additionally report the runtime of the feature-prototype assignment stage: 0.15 s (ogbn-arxiv), 4.43 s (ogbn-products), and 1.16 s (pokec).

Relative to ClusterGCN, LabStA increases preprocessing time by an average of 22.1% while reducing per-epoch training time by 1.7%. Although preprocessing incurs additional overhead, its contribution to total execution time is minor because it is performed only once before training. Moreover, pseudo-labeling accounts for only 2.95% of total preprocessing time on average, implying that its computational overhead is minimal. Peak GPU memory usage changes by +1.1% (ogbn-arxiv), −17.4% (ogbn-products), and +0.8% (pokec), indicating that LabStA does not consistently increase memory consumption under matched node budgets.

Q6. Uncertainty in joint-selection ablation

We have added standard deviations to the ablation study (Tab. 3). LabStA achieves higher mean accuracy than random, CDD-only, and ERR-only selection on all five datasets, with average gains of +0.96%p, +1.11%p, and +0.67%p, respectively. Two-sided Welch's tt-tests (p<0.05p<0.05) based on 10 runs per setting identify significant improvements on 2/5, 4/5, and 2/5 datasets, respectively. While the improvements are not consistently statistically significant, the higher mean accuracy across all five datasets supports the effectiveness of jointly optimizing CDD and ERR.

AuthorsOpenReview ↗

Author response to reviewer zNWW (2)

W2. Matched resource budget

While we address the specific concerns raised in W2 in our responses to Q3–Q6, we conduct an additional experiment comparing ClusterGCN and LabStA under matched resource budgets. Table 12 (App. E.5) compares the two methods using GraphGPS with $q \in \lbrace 1,2,4,8\rbrace $, 500 training epochs, and evaluation every 50 epochs, with results averaged over three runs. LabStA outperforms ClusterGCN on most datasets under matched total node budgets, supporting our claim that its gains are not simply due to larger mini-batches.

AuthorsOpenReview ↗

Gentle Follow-up on Author Response

Dear Reviewer,

Thank you again for your constructive feedback on our submission.

As the author–reviewer discussion period is approaching its end, we would greatly appreciate it if you could review our rebuttal and share any remaining questions or concerns.

We would be happy to provide further clarification if needed.

Thank you for your time and consideration.

Best regards,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.