acceptodds
Under review as a conference paper at ICLR 2027

BV-Sampler: Bias-Variance-Aware Sampling for Graph Neural Networks

Abstract

Neighborhood sampling enables scalable graph neural networks but introduces aggregation error under finite computation budgets. We propose BV-Sampler, a bias-variance-aware framework combining feature-aware sampling, contribution weighting, and sampler-induced contrastive learning under sparse supervision. We characterize optimal weights and proposals when the other is fixed, and develop an efficient diagonal surrogate. We also analyze layer-wise error accumulation and connect independent sampler-induced view disagreement to aggregation variance, yielding an encoded alignment bound. Experiments demonstrate competitive prediction across rich- and sparse-label settings, with the largest gains under sampled inference. On low-label OGBN-arXiv, BV-Sampler improves Micro-F1 by 6.77 percentage points over LABOR and 2.95 points over GraphSAINT with DGI. Ablations and direct diagnostics support the contributions of sampling and weighting and demonstrate reduced MSE through a bias–variance trade-off.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, optimization, importance sampling

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_mUGZOpenReview ↗
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
  1. 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.

  2. 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.

  3. 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
  1. 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.”

  2. 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.

  3. 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.

  4. 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
  1. 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.

  2. 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?

  3. 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
AuthorsOpenReview ↗

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?

Our mechanism adds per-neighbor contribution control derived from aggregation MSE: the exact solution retains feature interactions (Theorem 2.2), while the practical rule depends on expected sample count (Theorem 2.3). The fixed-sampler improvement in Table 8 isolates evidence for contribution weighting independently of a newly designed proposal.

W2 / Q1 — Exact versus diagonal solution.

The exact solution requires forming the neighbor Gram matrix in O(n2d)O(n^2d) and solving an n-dimensional system in O(n3)O(n^3), whereas Eq. (11) requires only a scalar calculation per contribution once probabilities are known. This explains the computational choice, but not its empirical approximation error. We compared the diagonal correction with the exact solution on PubMed dataset. Due to the high computational cost of BV-Sampler with exact solution, we only have results on PubMed dataset within a short time.

PubMed variantTest Micro-F1 (%, mean ± SD)Training Time per epoch
BV-Sampler with exact solution84.80 ± 0.200.4163
BV-Sampler with diagonal correction84.92 ± 0.190.0020

On PubMed dataset, the diagonal correction achieved similar test Micro-F1 to the exact solution across five runs, with a substantially lower training time per epoch.

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?

We trained our model on OGBN-arxiv dataset with/without incorporating sampler-induced contrastive learning under sparse-label setting. We used three paired seeds and held the architecture, data split, and sampling budget fixed. For each run, we evaluated the model every 50 iterations, restored the best-validation model weights and retained the end-of-training sampler cache. We estimated final-layer aggregation variance and MSE from 100 Monte Carlo draws on the same 500 validation nodes.

Metric (mean ± sample SD)No Contrastive lossWith Contrastive loss
Raw variance3.41957 ± 0.330272.61115 ± 0.34262
Raw MSE56.32950 ± 5.0233043.14230 ± 4.57329
Full-graph reference energy150.98803 ± 13.05657117.21717 ± 12.65429
Normalized variance0.02264 ± 0.000570.02224 ± 0.00057
Normalized MSE0.37301 ± 0.001520.36811 ± 0.00160

Raw variance and MSE fell by 23.6% and 23.4%, respectively, alongside a 22.4% decrease in reference energy. After normalization by reference energy, variance and MSE still decreased for all three seeds, by 1.8% and 1.3% on average, respectively. These results show a modest reduction in aggregation error relative to representation scale on OGBN-arXiv under the tested settings.

W4 — Ablation beyond arXiv.

The table below shows the additional experimental resutls for ablation study under sampled inference in the sparse-label setting:

Proposal / contribution weightOGBN-arXivPPI-large
Structure-only / α = 158.96 ± 0.22 (3)67.50 ± 0.41 (4)
Feature-aware / α = 159.33 ± 0.13 (3)68.77 ± 0.13 (4)
Structure-only / biased59.82 ± 0.55 (3)68.66 ± 0.10 (4)
Feature-aware / biased (full model)66.57 ± 0.23 (3)69.06 ± 0.02 (5)

The full model exceeds feature-aware sampling without correction by 7.24 points on arXiv and 0.29 on PPI-large.

AuthorsOpenReview ↗

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 proposalContribution weightsAuxiliary objectiveMicro-F1 (%)
Structure-onlyα = 1Sampler-induced CL58.96 ± 0.22
Feature-awareα = 1Sampler-induced CL59.33 ± 0.13
Structure-onlyBiasedSampler-induced CL59.82 ± 0.55
Feature-awareBiasedGraphCL64.13 ± 0.65
Feature-awareBiasedDGI64.52 ± 0.41
Feature-awareBiasedSampler-induced CL66.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.

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

The paper studies node-wise sampling in GNNs to approximate full-neighborhood aggregation. It combines different components.

  1. importance sampling with an additional factor α(u)\alpha(u), which introduces the bias while may improve the overall MSE. They separately show how to obtain the additional factor when the sampling probabilities are fixed (Theorem 2.2), and vice versa (Theorem 2.4).
  2. the computation of the exact factors are heavy. They propose approximate and efficient computation via a surrogate which removes some complex terms in the original MSE objective
  3. they additionally add another module, sampler-induced contrastive learning. Two independent samplings form the different views of a single node.

Experiments compare training with full-graph or sampled inference. A code repository is provided, but it has expired.

Critical strengths
  1. The paper formulates the exact aggregation MSE while retaining cross-neighbor feature interactions. They also clearly distinguish the optimal weights from the proposed surrogate.

  2. The paper conducts comprehensive experiments, pairing sampling proposals with contribution weighting, studying auxiliary objectives, the correction with a fixed MVS-GNN sampler, and bias--variance diagnostics.

Critical weaknesses
  1. Closely related sampling and weighting methods are missed, and thus the contribution is not sufficiently established.

    • A Biased Graph Neural Network Sampler with Near-Optimal Regret (NeurIPS 2021, Section 3.1), already uses the bias--variance decomposition to motivate biased GNN aggregation. Their Thanos sampler differs but directly precedes the motivation to relax unbiasedness. It is neither cited nor evaluated here.
    • Doubly Robust Off-Policy Evaluation with Shrinkage (ICML 2020, Section 3.1), derives importance-weight shrinkage by optimizing an MSE-related criterion. Subgaussian and Differentiable Importance Sampling for Off-Policy Evaluation and Learning (NeurIPS 2021, Definition 4.1 and Table 1), studies smooth weight corrections, including a harmonic form. These are from different estimation problems, but they are relevant because they similarly introduce additional factors in importance sampling.
    • Enhancing Sequential Recommendation with Graph Contrastive Learning (GCL4SR, IJCAI 2022, Section 4.1), already generates two views through neighborhood sampling and encodes them with shared GNNs for contrastive learning. Temporal Graph Contrastive Learning for Sequential Recommendation (TGCL4SR, AAAI 2024, Section 4.1) also constructs contrastive graph views through neighbor sampling. Neither work is cited. Their settings and sampling differ from this paper, but they reflect that sampling-induced contrastive learning is not a new paradigm in graph learning.

The remaining contribution, therefore, is the particular weight calculation, diagonal approximation, and combination of components.

  1. The approximation lacks a justification for real neighbor features.

Appendix C.10 candidly shows that the surrogate is not a general upper bound, but the paper does not sufficiently explain when the approximation should be useful in practice. Indeed, neighboring feature vectors can be strongly correlated.

In particular, the weighting comparisons in Tables 4 and 8 test the proposed correction against no correction, rather than against alternative ways of introducing bias. Why this particular rule is preferable is not justified.

  1. The connection between MSE minimization and contrastive learning is weak.

The variance identity in Proposition 2.8 does not concern aggregation accuracy. Instead, a successful CL will expect the two views to have some distinction, so the variance should be proper, not as small as possible. On the other hand, sampling can induce contrastive learning, while sampling + CL may be inferior to sampling + other auxiliary learning methods.

Moreover, Appendix D.3 invokes Theorem 2.7 (aggregation error) to explain inflated per-step gradient variance and failure to remain in a good optimization basin, where the logic chain may not hold: it is not guaranteed that aggregation error will lead to large gradient variance and poor optimization behavior.

  1. The uncertainty evidence in the empirical results (I quote some findings below)
  • Reliability of the incremental gains. In Table 4, adding contribution weighting to feature-aware sampling improves Micro-F1 by 0.42 percentage points, and the proposed auxiliary objective exceeds DGI by 0.40 points. The main tables report ± values, but do not specify their meaning, the main experiment repetition counts, or the seed-pairing procedure. Table 8 explicitly reports three paired seeds and a significance result for a separate experiment; this does not establish significance for the main comparisons. Thus, the reliability of the modest component gains cannot be assessed from the current reporting.
  • Consistency of the mechanism measurements. In Table 9, the first unweighted row reports squared bias 0.007, variance 1.510, and MSE 1.525, although the first two sum to 1.517. Similar discrepancies occur in the other unweighted rows and exceed rounding error. With standard empirical definitions on the same draws and a common normalization, the decomposition is exact. Different estimators or normalization procedures could explain the differences, but these are not documented. Because this table directly supports the proposed mechanism, the measurement definitions and underlying outputs are needed to interpret it confidently.
  1. The core sampling and training procedure is not even specified well (I quote some findings below)
  • The sampling distribution and contribution weights are mutually dependent, but their computation is unspecified. Theorem 2.4 gives an optimal proposal for fixed α\alpha, while Theorem 2.3 gives surrogate-optimal weights for fixed pp. Algorithm 1, line 7, simply instructs the reader to use p∗p^* and α∗\alpha^*. It does not specify an initialization, update order, or stopping rule, or identify whether the main experiments use a norm-based proposal followed by one correction, alternating updates, or the joint surrogate solution in Appendix C.11. These choices can produce different estimators. Appendix C.11 itself states that the experiment labeled “joint fixed point” must be tied to its implemented update and stopping rule before being identified with the theoretical solution. The conditional formulas therefore do not provide a complete definition of the evaluated sampler
  • The cache description does not resolve how feature-dependent probabilities are constructed at each layer. Section D.2 describes caching layer-0 feature norms, while Algorithm 1, line 12, overwrites C[u]C[u] with a visited hidden-feature norm ∥hu(l)∥\|h_u^{(l)}\|. The cache has no layer index in the pseudocode, and the paper does not explain whether separate layer-specific caches are maintained, which layer supplies each proposal, or when refreshed values become available to subsequent sampling. These details affect the actual distribution and its staleness, and are necessary to relate the practical procedure to the fixed-feature analysis.
  • The loss actually optimized is not fully defined. Equation 25 specifies a symmetric paired-view objective, but Section 2.5, lines 283–285, says the implementation uses a cross-view variant. The paper does not give the implemented loss formula, including its denominator and symmetrization. Since the contrastive component is one of the claimed contributions, readers need to know which objective generated its reported benefit. The variance identity for independently sampled views does not specify or validate that training objective.

The comparison protocol adds further uncertainty. Baseline-specific tuning, checkpoint selection, and the number of optimizer steps per epoch are insufficiently documented. The sampling budgets in Tables 6 and 11 are not connected, and Table 11 explicitly leaves its timing scope unconfirmed. It is also unclear whether full-graph inference retains the contribution correction. Consequently, the reported accuracy and efficiency cannot be confidently attributed to a fully specified procedure under comparable conditions.

The paper states that code is available, but the anonymous repository returned repository_expired when checked on 19 October 2026. No accessible implementation or figure/table reproduction scripts are available to resolve these gaps. Expiration alone does not imply incorrect results. However, the combination of incomplete algorithm definitions and unavailable artifacts prevents verification of the connection between the theoretical estimators, the trained model, and the reported results. Resolving this concern requires identifying the exact evaluated procedure and its supporting records, rather than only restoring a link or restating the conditional formulas.

Questions for authors

Some questions regarding confidence in the empirical results are listed below.

  1. Evaluated algorithm and protocol (Weakness 5). Which proposal and contribution-weight update were used to generate the reported results: a norm-based proposal with one correction, alternating updates, or the joint surrogate solution in Appendix C.11? Please specify the cache and contrastive-loss implementation, explain whether contribution weighting is retained during full-graph inference, and clarify how sampling budgets and training work are matched across methods. Could you restore the anonymous repository and identify the configurations and commands corresponding to the reported tables?
  2. Bias–variance diagnostics (Weakness 4). How were squared bias, variance, and MSE in Table 9 estimated and normalized? For example, the first unweighted row gives 0.007+1.510=1.5170.007+1.510=1.517, rather than the reported MSE of 1.525. Were the quantities computed from the same Monte Carlo draws and reference representations? Please explain the discrepancies and provide the calculation procedure or underlying diagnostic outputs.
  3. Uncertainty in the component gains (Weakness 4). What do the ± values represent, and how many independent runs were used for the main results and Table 4? Were the ablations paired by seed and data split? Please provide available run-level results or uncertainty estimates for the 0.42-point gain from contribution weighting and the 0.40-point gain over DGI, distinguishing these experiments from the three-seed study in Table 8.
  4. Evidence for the particular weighting rule (Weaknesses 1–2). Beyond comparison with α=1\alpha=1, do you have existing results comparing the proposed correction with a validation-selected scalar shrinkage or clipped importance weights, holding the proposal, sampling budget, network, and auxiliary objective fixed with comparable tuning opportunities? Please report any available evidence on both aggregation MSE and downstream performance. Separately, is there existing comparative evidence against Thanos from Zhang et al., A Biased Graph Neural Network Sampler with Near-Optimal Regret (NeurIPS 2021, paper), or a concrete protocol incompatibility that limits such a comparison? These questions concern available evidence for the specific design, rather than a request for an extensive new benchmark during rebuttal.
4 comments
AuthorsOpenReview ↗

Rebuttal (1/3)

We thank the reviewer for recognizing our exact aggregation-MSE formulation with cross-neighbor feature interactions, the distinction between the optimal weights and the practical surrogate, and the breadth of our experiments on proposal design, contribution weighting, auxiliary objectives, correction with a fixed MVS-GNN sampler, and bias–variance diagnostics. We address the reviewer’s concerns and questions below in Q&A format.

W1 — Missing related work and the boundary of novelty.

We thank the reviewer for these references and have discussed them explicitly in the related work in the new version. We do not claim that introducing bias, using norm-proportional sampling, or forming contrastive views through neighborhood sampling is new. Our contributions are summarized as follows: (i) we derive the contribution weights by minimizing the GNN aggregation MSE and its diagonal surrogate, rather than choosing a weight correction independently of this objective. The correction depends on the sampling budget k and requires no additional tuning parameter. Eq. (13) corresponds to the harmonic correction of Metelli et al. [3] with λ = 1/k, whereas their theoretical choice of λ depends on a Rényi divergence and a confidence level. Eq. (11) is our simplified surrogate solution. (ii) Theorem 2.2 gives the exact optimal contribution weights for a fixed proposal while retaining interactions between different neighbors' features. (iii) Keeping the MVS-GNN sampler unchanged and adding our contribution weights improves Micro-F1 from 82.10% to 83.43% (Table 8), showing that the weights can improve an existing sampler. Thanos [1] studies biased sampling through a bandit formulation, and Su et al. [2] study importance-weight shrinkage for off-policy evaluation; we have explained these connections alongside our derivation. We have cited all five papers [1-5] in the related work.

[1] Zhang, Qingru, David Wipf, Quan Gan, and Le Song. "A biased graph neural network sampler with near-optimal regret." Advances in Neural Information Processing Systems 34 (2021): 8833-8844.

[2] Su, Yi, Maria Dimakopoulou, Akshay Krishnamurthy, and Miroslav Dudík. "Doubly robust off-policy evaluation with shrinkage." In International Conference on Machine Learning, pp. 9167-9176. PMLR, 2020.

[3] Metelli, Alberto Maria, Alessio Russo, and Marcello Restelli. "Subgaussian and differentiable importance sampling for off-policy evaluation and learning." Advances in neural information processing systems 34 (2021): 8119-8132.

[4] Zhang, Yixin, Yong Liu, Yonghui Xu, Hao Xiong, Chenyi Lei, Wei He, Lizhen Cui, and Chunyan Miao. "Enhancing sequential recommendation with graph contrastive learning." arXiv preprint arXiv:2205.14837 (2022).

[5] Zhang, Shengzhe, Liyi Chen, Chao Wang, Shuangli Li, and Hui Xiong. "Temporal graph contrastive learning for sequential recommendation." In Proceedings of the AAAI conference on artificial intelligence, vol. 38, no. 8, pp. 9359-9367. 2024.

W2 — Why this correction, and when is the diagonal approximation useful?

For a fixed proposal, Eq. (11), α(u)=kp(u)/(1+kp(u))\alpha(u)=kp(u)/(1+kp(u)), minimizes the diagonal surrogate in Theorem 2.3 without an additional shrinkage hyperparameter. It attenuates contributions with low expected sample counts. On PubMed, applying the correction to MVS-GNN while holding the proposal fixed improved Micro-F1 from 82.10% to 83.43% (Table 9 in the new version).

We also compared the diagonal correction with the exact solution on PubMed dataset. Due to the high computational cost of BV-Sampler with exact solution, we only have results on PubMed dataset within a short time. On PubMed dataset, the diagonal correction achieved similar test Micro-F1 to the exact solution across five runs, with a substantially lower reported time.

PubMed variantTest Micro-F1 (%, mean ± SD)Reported time
BV-Sampler with exact solution84.80 ± 0.200.4163
BV-Sampler with diagonal correction84.92 ± 0.190.0020

Appendix C.10 shows that cross-neighbor correlations can invalidate the upper-bound interpretation of the diagonal surrogate. Equation (13) bounds the discrepancy in the diagonal case only. The PubMed comparison measures downstream accuracy and leaves the error from dropping cross-neighbor terms unquantified. We have clarified this distinction in the new version in Appendix D.7.

AuthorsOpenReview ↗

Rebuttal (2/3)

W3 — The connection between MSE minimization and contrastive learning is weak.

Proposition 2.8 characterizes the expected disagreement between two independent sampled views of the same node. Two views can agree closely and still share a bias relative to full-graph aggregation. The identity therefore motivates studying sampling noise in the positive pairs. It gives no criterion for how much view diversity is useful and no guarantee that minimizing InfoNCE reduces aggregation MSE.

We tested the connection empirically on OGBN-arXiv dataset under sparse-label setting. Across three paired seeds, we held the architecture, split, and sampling budget fixed and compared training with λc=0\lambda_c=0 and 0.50.5. We validate every 50 updates (instead of every update for the results in Table 1, 2 and 3) and restore the best-validation model weights. The results show that normalized aggregation variance and MSE decreased in all three pairs, with mean reductions of 1.8% and 1.3%, respectively. Raw variance and MSE fell by 23.6% and 23.4%, alongside a 22.4% decrease in full-graph reference energy.

Metric (mean ± sample SD)No Contrastive loss (λc=0\lambda_c=0)With Contrastive loss (λc=0.5\lambda_c=0.5)
Raw variance3.41957 ± 0.330272.61115 ± 0.34262
Raw MSE56.32950 ± 5.0233043.14230 ± 4.57329
Full-graph reference energy150.98803 ± 13.05657117.21717 ± 12.65429
Normalized variance0.02264 ± 0.000570.02224 ± 0.00057
Normalized MSE0.37301 ± 0.001520.36811 ± 0.00160
Test Micro-F1 (%)65.45 ± 0.2765.86 ± 0.27

We also held the proposal and contribution weighting fixed and varied the auxiliary objective under sampled inference. On OGBN-arXiv dataset, sampler-induced contrastive learning achieved 66.57% Micro-F1, compared with 64.52% for DGI and 64.13% for GraphCL. On PPI-large, it achieved 69.06%, compared with 68.80% for DGI. These comparisons support the choice of auxiliary objective in the tested settings. We have removed the explanation in Appendix D.3 that attributed the observed training trajectories to inflated gradient variance and departure from favorable optimization basins.

W4 / Q2 — Table 9's bias–variance inconsistency.

We want to clarify that the Table 9 (Table 10 in the new version) heading omitted the finite Monte Carlo correction applied to squared bias. For each frozen Cora model, we used the same 100 sampled forward passes on 500 fixed validation nodes to compute all three quantities. The reference for each node was its deterministic full-graph final-layer aggregation before the classifier.

For a node with sampled representations z1,…,zRz_1,\ldots,z_R, sample mean zˉ\bar{z}, and full-graph reference z⋆z_\star, we computed

V=\frac{1}{R}\sum_{r=1}^{R}||z_r-\bar{z}||_2^2, MSE=\frac{1}{R}\sum_{r=1}^{R}||z_r-z_{\star}||_2^2.$$ > > We averaged each quantity over the validation nodes and divided by the same mean reference energy for each run. The table’s bias column used $\max \{0,B_{raw}^{2} - V/(R-1)\}$ at each node before averaging. This subtracts an estimate of the contribution of Monte Carlo noise in $\bar z$ and clips negative estimates to zero. > > The identity $MSE=B_{raw}^{2}+V$ therefore holds for the empirical quantities. In the first unweighted row, the normalized means across seeds are $0.015329+1.509920=1.525249$. The reported squared bias of $0.007$ includes the correction. We have labeled the corrected estimate explicitly in the new version in Appendix D.5 (Table 10). **W4 / Q3 — Reliability of small gains.** > We thank the reviewer for pointing out the missing reporting details. We repeat the experiments in Tables 1–3 five times (with random seed from [41, 42, 43, 44, 45]) and Table 4 three times (with random seed from [41, 42, 43]), using different random seeds for initialization while keeping the data split and training settings fixed. Each reported score is obtained from the checkpoint with the best validation performance. We have added these details in Appendix D.2.
AuthorsOpenReview ↗

Rebuttal (3/3)

W5 / Q1 — Evaluated procedure and reproducibility.

All main results use a one-step update per training iteration, without an inner alternating-optimization loop. We initialize α(0)(u)=1\alpha^{(0)}(u)=1. At training step tt, we construct p(t)(u)∝Avu∣α(t−1)(u)∣Ct[u]p^{(t)}(u)\propto A_{vu}|\alpha^{(t-1)}(u)|C_t[u], normalize over candidate neighbors, and then compute α(t)(u)=kp(t)(u)1+kp(t)(u)\alpha^{(t)}(u)=\frac{kp^{(t)}(u)}{1+kp^{(t)}(u)}. We do not iterate these equations to convergence or directly solve Eq. (77). We have clarified this computation order in Algorithm 1. In algorithm 1, we use cache layer-0 feature norm for every node as the initailization, which is cheap in term of computational cost. In the algorithm, we only update the cache for the sampled nodes using the layer-l feature norm without any additional cost. The contrastive loss term is formulated as below: LInfoNCE=−1N∑vlog⁡exp⁡(⟨zv(1),zv(2)⟩/τ)∑v′≠vexp⁡(⟨zv(1),zv′(s)⟩/τ)\mathcal L_{\mathrm{InfoNCE}}=-\frac1{N}\sum_{v} \log\frac{\exp(\langle z_v^{(1)},z_v^{(2)}\rangle/\tau)} {\sum_{v'\ne v}\exp(\langle z_v^{(1)},z_{v'}^{(s)}\rangle/\tau)}. The key difference is how the postive pairs are constructed different. In our method, we use importance sampling method to construct two stochastic views instead of generating views from random masking or edge perturbation like GraphCL or GRACE. We have restored the anonymous repository with configurations and commands to reproduce the results in Table 1 - 4, 10 in the new version.

Q4 - Evidence for the particular weighting rule

For a fixed proposal, Eq. (11) minimizes the diagonal aggregation-MSE surrogate. It shrinks contributions according to their expected sample counts, kp(u)kp(u), without introducing a shrinkage coefficient to tune. We have two controlled comparisons with α=1\alpha=1. In the paired Cora diagnostics, changing only the evaluation weights on the same frozen model reduced depth-1 normalized aggregation MSE from 1.525 to 0.374. On PubMed, adding the correction to MVS-GNN with its proposal held fixed increased Micro-F1 from 82.10% to 83.43% (Table 8). In a separate PubMed comparison, the diagonal correction and exact solution achieved 84.92 ± 0.19% and 84.80 ± 0.20% Micro-F1, respectively, across five runs. As reported in our response to W2, the diagonal correction and the exact solution achieved 84.92 ± 0.19% and 84.80 ± 0.20% Micro-F1, respectively, across five PubMed runs. Table 11 provides complementary evidence on how BV-Sampler’s downstream performance changes as the sampling budget kk varies.

Thank you for the care and effort you put into the rebuttal, particularly the additional experiments and the release of the code. Your explanation of the Monte Carlo correction resolves my concern about the bias–variance decomposition in the revised Table 10.

The added references clarify where BV-Sampler overlaps with prior work. My main reservation is why a practitioner should choose this particular weighting rule. The comparison with α=1\alpha=1 tests whether applying the correction helps, and the PubMed experiment compares the diagonal approximation with the exact solution. Whether simple scalar shrinkage or clipping would achieve similar gains under the same proposal and budget remains open. A comparison with Thanos would also help establish the practical value of the full sampler relative to an existing biased GNN sampler.

I notice the removal of the earlier claim about gradient variance and optimization dynamics. The comparisons with DGI, GraphCL, and training without the auxiliary loss provide evidence for the contrastive objective in the tested settings. The simultaneous improvement in aggregation MSE and Micro-F1 still leaves open how much of the accuracy gain comes from coupling this objective with the proposed sampler.

Two issues affect my interpretation of the reported gains.

  • For the 0.42-point gain from weighting and the 0.40-point gain over DGI in Table 4, the per-method standard deviations leave the uncertainty in the paired differences unclear. In the released α=1\alpha=1 ablation, the bottom-layer multiplier is set to one, but the sampled adjacency has already been reweighted by an α\alpha-dependent factor. This makes it difficult to attribute the 0.42-point difference to switching the correction fully on or off.
  • The main script prints a full-graph test score after restoring the best checkpoint even when sampled inference is enabled, so its final output does not verify the sampled-inference results in Table 3.

Overall, my concerns are partially resolved, while I would maintain my original rating.

Reviewer_ugDtOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the bias-variance trade-off in GNN sampling. BV-Sampler combines feature-aware sampling, biased contribution weights, and two-view contrastive learning. The authors derive conditional MSE optima and a diagonal approximation. Experiments cover full-graph and sampled inference, with the largest gains under sparse labels and sampled inference.

Critical strengths

This paper provides a useful analysis of biased GNN sampling and reports good results under sampled inference.

  • The paper states the limits of its analysis. The diagonal approximation is not a general MSE upper bound, and the contrastive result only bounds alignment.

  • On sparse-label OGBN-arXiv, BV-Sampler reaches 66.57% Micro-F1 under sampled inference, versus 63.62% for GraphSAINT with DGI. The ablations and frozen-model diagnostics help explain the results.

Critical weaknesses

Motivation and design

  • Eqs. (11) and (15) make p and alpha depend on each other. Algorithm 1 does not specify whether it uses one-step correction, alternating updates, or the joint solution in Eq. (77).

  • Algorithm 1 replaces a layer-0 norm with a layer-l norm without specifying separate caches. Section 2.5 also says the implemented loss differs from Eq. (25). The actual sampler and loss need clearer definitions.

  • Full-graph GCN is feasible on the main datasets. What resource limits justify BV-Sampler? Please compare at fixed memory or time budgets, including cache updates, both contrastive views, and preparation costs.

Experiments

  • Five of the six sampling baselines are from 2017-2020; the newest is LABOR (2023). Comparison with recent methods such as TOP (ICLR 2025) is missing. Please use a compatible transductive protocol and the same backbone to assess whether BV-Sampler remains competitive.

  • Does "the same sampled mini-batch" in Appendix D.3 mean identical nodes or equal budgets? Table 6's budget unit is unclear. Some baselines decline after early peaks in Figure 1, so checkpoint selection and tuning ranges also need clarification.

  • Table 4 separates sampling and weighting only under full-graph inference. These ablations are needed under sampled inference, where the largest gains occur. Table 10 only varies the contrastive weight.

Questions for authors
  • The newest sampling baseline is LABOR (2023). How does BV-Sampler compare with more recent methods such as TOP (ICLR 2025), using a compatible protocol and the same backbone?

  • How do accuracy and total cost compare with these baselines at matched memory or time budgets? Please include preparation, cache updates, and both contrastive views.

  • Were baseline hyperparameters tuned on validation data, and were the best validation checkpoints used? Please clarify whether the sampled-inference budgets are matched.

2 comments
AuthorsOpenReview ↗

Rebuttal (1/2)

We thank the reviewer for recognizing the value of our analysis of biased GNN sampling, the clarity about its theoretical limits, and the strong sampled-inference results supported by our ablations and frozen-model diagnostics. We will address the reviewer’s concerns and questions below in Q&A format.

W1 - Eqs. (11) and (15) make p and alpha depend on each other.

We use a one-step construction, without alternating updates or solving the joint surrogate problem in Eq. (77). All main results use a one-step update per training iteration, without an inner alternating-optimization loop. We initialize α(0)(u)=1\alpha^{(0)}(u)=1. At training step tt, we construct p(t)(u)∝Avu∣α(t−1)(u)∣Ct[u]p^{(t)}(u)\propto A_{vu}|\alpha^{(t-1)}(u)|C_t[u], normalize over candidate neighbors, and then compute α(t)(u)=kp(t)(u)1+kp(t)(u)\alpha^{(t)}(u)=\frac{kp^{(t)}(u)}{1+kp^{(t)}(u)}. We do not iterate these equations to convergence or directly solve Eq. (77). We have updated this computation order highlighted in blue in Algorithm 1 in the new version.

W2 - Algorithm 1 replaces a layer-0 norm with a layer-l norm without specifying separate caches. Section 2.5 also says the implemented loss differs from Eq. (25). The actual sampler and loss need clearer definitions.

In algorithm 1, we use cache layer-0 feature norm for every node as the initailization, which is cheap in term of computational cost. In the algorithm, we only update the cache for the sampled nodes using the layer-l feature norm without any additional cost. The contrastive loss term is formulated as below: LInfoNCE=−1N∑vlog⁡exp⁡(⟨zv(1),zv(2)⟩/τ)∑v′≠vexp⁡(⟨zv(1),zv′(s)⟩/τ)\mathcal L_{\mathrm{InfoNCE}}=-\frac1{N}\sum_{v} \log\frac{\exp(\langle z_v^{(1)},z_v^{(2)}\rangle/\tau)} {\sum_{v'\ne v}\exp(\langle z_v^{(1)},z_{v'}^{(s)}\rangle/\tau)}. The key difference is how the postive pairs are constructed different. In our method, we use importance sampling method to construct two stochastic views instead of generating views from random masking or edge perturbation like GraphCL or GRACE.

W3 - Full-graph GCN is feasible on the main datasets. What resource limits justify BV-Sampler? Please compare at fixed memory or time budgets, including cache updates, both contrastive views, and preparation costs.

Our intended use case is limited-neighborhood computation, especially on the large-scale datasets, such as PPI-large (in table 3). The large scale graph makes the full-graph inference infeasible. In Table 3 on PPI-large dataset, BV-Sampler improves over LABOR from 68.08% to 69.06%, but takes 0.0478 versus 0.0364 seconds. To evaluate performance under a limited training budget, we gave all methods the same 60-second wall-clock budget on the 5% label split with full graph evaluation. Timing included local data loading, graph and model preparation, sampling, optimizer updates, and full-graph validation. For BV-Sampler, it also included cache initialization and updates and both contrastive views. We evaluated the checkpoint with the highest validation Micro-F1 within the budget once on the test set. The table below shows the mean F1 score with sample standard deviation across three seeds.

MethodTest Micro-F1 (%)
Full-graph GCN66.95 ± 0.22
BV-Sampler67.30 ± 0.33
FastGCN66.22 ± 0.96
LABOR60.16 ± 0.40
MVS-GNN39.41 ± 2.20
GraphSAINT55.98 ± 0.45
LADIES62.68 ± 0.41

BV-Sampler achieved the highest mean test Micro-F1 under this budget with 0.35% above full-graph GCN. We have added this result in Appendix D.7 in the new version.

W4 /Q1 - Comparison with TOP.

We added the experimental results for TOP in both rich label and sparse label settings. In the experiment, we use the same backbone, data split, and budget (batch size). The full experimental resutls are included in the updated paper in Tables 1, 2 and 3. Selected comparisons from the additional results are shown below and we report the mean Micro-F1 (%) and standard deviation with five different random seeds.

SettingTOPBV-Sampler
PubMed, sparse-label, full-graph inference84.01 ± 0.2784.92 ± 0.19
Reddit, sparse-label, full-graph inference92.97 ± 0.3193.32 ± 0.04
OGBN-arXiv, sparse-label, full-graph inference64.64 ± 0.6767.63 ± 0.30
OGBN-arXiv, sparse-label, sampled inference62.96 ± 0.6366.57 ± 0.23
PPI-large, sparse-label, sampled inference68.53 ± 0.2169.06 ± 0.02

Our method consistently outperforms TOP on these three datasets across both full-graph inference and sampeld inference settings. The new result is added in table 1, 2 and 3 highlighted in blue.

AuthorsOpenReview ↗

Rebuttal (2/2)

W5/Q3 - Does "the same sampled mini-batch" in Appendix D.3 mean identical nodes or equal budgets? Table 6's budget unit is unclear. Some baselines decline after early peaks in Figure 1, so checkpoint selection and tuning ranges also need clarification. Were baseline hyperparameters tuned on validation data, and were the best validation checkpoints used? Please clarify whether the sampled-inference budgets are matched.

In Appendix D.3, “the same sampled mini-batch” refers to a shared sampling budget. Each method sampled its own neighbors using its own strategy. We have clarified Table 6 by distinguishing the number of target nodes per mini-batch from the neighborhood sampling budget. For each dataset, we fixed the target batch size, hidden feature dimension, and dropout rate across methods. These shared settings were held fixed for the comparison. Figure 1 shows training trajectories, including declines after early peaks. As for checkpoint selection protocol, we select the best checkpoint with the highest Micro-F1 score on the validation set and then evalute the performance on the test set. For the hyperparameter of the baseline method, we select the best hyperparameters reported in the their papers. If no hyperparameter is reported, we use the default one.

W6 - Table 4 separates sampling and weighting only under full-graph inference. These ablations are needed under sampled inference, where the largest gains occur.

The table below shows the additional experimental resutls for ablation study under sampled inference in the sparse-label setting:

Proposal / contribution weightOGBN-arXivPPI-large
Structure-only / α = 158.96 ± 0.22 (3)67.50 ± 0.41 (4)
Feature-aware / α = 159.33 ± 0.13 (3)68.77 ± 0.13 (4)
Structure-only / biased59.82 ± 0.55 (3)68.66 ± 0.10 (4)
Feature-aware / biased (full model)66.57 ± 0.23 (3)69.06 ± 0.02 (5)

The full model exceeds feature-aware sampling without correction by 7.24 points on arXiv and 0.29 on PPI-large.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.