- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper addresses the aggregation errors caused by GNN neighbor sampling under limited computational budgets and proposes a bias–variance-aware sampling framework, termed BV-Sampler. Unlike existing methods that primarily focus on unbiased estimation or variance reduction, BV-Sampler directly optimizes the aggregation mean squared error (MSE) by jointly considering estimation bias and variance, while jointly investigating neighbor sampling probabilities and contribution weights. Theoretically, the authors derive the optimal contribution weights for a fixed sampling distribution and the optimal sampling distribution for fixed contribution weights, and further develop a practical diagonal approximation to reduce the computational cost of the exact solution. In addition, the paper constructs contrastive views through two independent neighbor-sampling processes and establishes a theoretical connection between sampling variance and view discrepancy, thereby enabling sampler-induced contrastive learning with unlabeled nodes. Experiments on Cora, PubMed, Reddit, OGBN-ArXiv, and PPI-large demonstrate that BV-Sampler achieves competitive performance under standard settings, with more pronounced improvements in sparse-label and sampled-inference scenarios.
Critical strengths
-
Compared to approaches that merely require the aggregated estimate to remain unbiased, this paper points out that appropriately introducing bias may reduce the overall MSE. Based on this, it simultaneously considers both the sampling probability and the contribution weights, thereby achieving a better integration between method design and theoretical analysis.
-
The paper not only derives the conditionally optimal solutions for the sampling probability and contribution weights but also further analyzes the propagation of sampling errors in multi-layer GNNs. For non-diagonal solutions with high computational costs, the authors explicitly introduce a diagonal surrogate rather than directly describing the approximate solution as the exact optimal solution.
-
The authors do not employ additional techniques such as edge dropping or feature masking; instead, they use two independent samplings to generate random views and prove that there is a direct relationship between the expected squared error of the uncoded views and the estimator variance, thereby establishing a strong connection between the contrastive learning module and the sampling mechanism described earlier.
Critical weaknesses
-
The feature-aware proposal adopted in this paper is closely related to existing importance sampling methods based on feature norms, and the authors acknowledge that norm-proportional proposals are a well-established technique. Therefore, it is necessary to further highlight the substantive innovations in this paper at the level of the actual sampling mechanism, in addition to the “unified bias–variance framework.”
-
Non-diagonal optimal solutions require high computational costs; therefore, the final algorithm employs a diagonal surrogate. However, this approximation neglects the interaction terms between features of different neighbors. Currently, there are no experiments demonstrating the exact extent of the MSE and prediction performance losses caused by this approximation.
-
The paper proves the relationship between sampling variance and view differences and their upper bounds; however, this result does not directly demonstrate that optimizing InfoNCE can reduce the variance of the original estimator. Therefore, the current theoretical framework serves more as a rational explanation for the module’s design rather than a direct optimization guarantee.
-
The core ablation experiments in Table 4 were primarily conducted on OGBN-arXiv, and the sampler-induced InfoNCE yielded only about a 0.65 percentage point improvement compared to removing this module. It is recommended to supplement these results with the same component ablation on at least one additional dataset to demonstrate that the contributions of feature-aware sampling, biased weighting, and contrastive learning are not specific to a single dataset.
Questions for authors
-
How significant is the gap between the diagonal substitution approach actually used and the theoretical, exact non-diagonal optimal solution? We recommend that the authors compare the two approaches on feasible datasets in terms of mean squared error (MSE), Micro-F1, and computational overhead, thereby demonstrating whether the current approximation strategy effectively preserves the advantages of the theoretical optimal solution.
-
The paper establishes a connection between sampler-induced view inconsistency and sampling variance through theoretical analysis, but the current experiments primarily demonstrate changes in prediction performance following the introduction of contrastive learning. Could the authors further report changes in sampling variance or aggregated mean squared error before and after incorporating sampler-induced contrastive learning to verify whether the theoretical analysis aligns with actual training results?
-
The performance improvements of BV-Sampler are primarily observed in sparse-label and sampling-based inference scenarios, whereas its advantages over existing methods are relatively limited in rich-label and full-graph inference settings. Could the authors further analyze the reasons behind this phenomenon and clarify whether the performance gains stem primarily from bias-variance-aware sampling or from the additional supervisory information provided by sampler-induced contrastive learning under sparse supervision?
2 comments
Rebuttal (2/2)
Q3 — Why gains concentrate, and are they mostly extra supervision?
In the rich-label and the full-graph inference setting, almost all of the methods are bounded by its vanilla backbone (GCN) without sampling strategy, dentoed as GCN (Full Graph). We do observe that some sampling methods may slightly perform better than GCN (Full Graph), but such performanc gain is very small. In our paper, we explored that our method can lead to large performance gain under sampled inference sparse-label setting as the existing methods usually fail to performance well due to the lack of enough label information and message passing mechnism does not work well due to the lack of neighbor information under sampling strategy.
Under rich supervision and full-graph inference, abundant labels provide a strong training signal, and evaluation uses complete neighborhoods. Consequently, reducing sampling error offers less room for performance improvement, and most methods achieve performance close to full-graph GCN. However, under sparse supervision and sampled inference, fewer labels limit model training, while incomplete neighborhoods introduce aggregation error directly into predictions. These conditions make both bias–variance-aware aggregation and learning from unlabeled nodes more useful. Here are the additional arXiv batch-evaluation results that help distinguish these contributions.
| Sampling proposal | Contribution weights | Auxiliary objective | Micro-F1 (%) |
|---|---|---|---|
| Structure-only | α = 1 | Sampler-induced CL | 58.96 ± 0.22 |
| Feature-aware | α = 1 | Sampler-induced CL | 59.33 ± 0.13 |
| Structure-only | Biased | Sampler-induced CL | 59.82 ± 0.55 |
| Feature-aware | Biased | GraphCL | 64.13 ± 0.65 |
| Feature-aware | Biased | DGI | 64.52 ± 0.41 |
| Feature-aware | Biased | Sampler-induced CL | 66.57 ± 0.23 |
With the contrastive objective fixed, combining feature-aware sampling and biased weighting improves Micro-F1 from 59.33% to 66.57%. This supports a substantial contribution from the sampling and weighting design beyond additional supervision alone. With sampling and weighting fixed, our objective further outperforms DGI and GraphCL by 2.05 and 2.44 points, respectively.
Rebuttal (1/2)
We thank the reviewer for recognizing how our bias–variance analysis guides the design of sampling probabilities and contribution weights, the distinction between the conditional optima and the practical diagonal surrogate, and our analysis of layer-wise error propagation and the link between estimator variance and disagreement between independently sampled views. We address the reviewer’s concerns and questions below in Q&A format.
W1 — What changes at the mechanism level?
W2 / Q1 — Exact versus diagonal solution.
W3 / Q2 — Could the authors further report changes in sampling variance or aggregated mean squared error before and after incorporating sampler-induced contrastive learning to verify whether the theoretical analysis aligns with actual training results?
W4 — Ablation beyond arXiv.