- 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
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
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 t-tests (p<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.
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.