- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper studies how precisely a single transductive node classification benchmark can distinguish between the performance of two distinct models, given that predictive errors across test nodes are not independent. The paper argues that standard i.i.d. uncertainty estimates are not appropriate, as they can significantly underestimate variance. The paper proposes a graph-partition block bootstrap (GPBB) to estimate the dependency-aware uncertainty and use it to define the minimum resolvable gap (MRG). They apply the framework across 14 graph datasets and 22,400 trained models.
Critical strengths
-
The paper addresses an important problem in evaluating graph models for node classification. Nodes in a graph are not necessarily i.i.d., and evaluating these models as if they were operating on i.i.d. data can lead to misleading estimates of uncertainty. The distinction between within-graph uncertainty, training randomness, and superpopulation uncertainty (graph-to-graph) is useful.
-
The experimental suite is quite large, including both a large number of models, real-world datasets, and synthetic datasets where the true design-effect is known.
Critical weaknesses
-
The proposed GPBB doesn't seem well calibrated enough to support the paper's main quantitative conclusions. In the paper's own experiments, GPBB can be significantly below the nominal 95% target (reaching 49% for one dataset), raising the question of how reliable the reported MRG values can be interpreted.
-
The paper's presentation makes the contributions unnecessarily difficult to assess. The authors combine several distinct concepts (e.g., node-level dependence, variance inflation, design effect, etc.) all in the name of "statistical resolution", without clearly distinguishing between the corresponding quantities and claims. Further, the language is quite strong for what's being presented. For example, the 87% claim comes from a convenience sample of 86 gaps. Further, because MRG is defined using , falling below the 80%-power threshold for MRG does not imply the reported gap is insignificant.
-
The theoretical justification for GPBB is not entirely clear to me. The propositions require some conditional independence assumptions, which (as the authors admit) do not hold for spatially structured graph data. It is therefore unclear how well the theoretical dependence radius supports the block construction used in the experiments.
Questions for authors
(See weaknesses)
-
How reliable are the MRG estimates given that the bootstrap does not always achieve the expected coverage? How should we interpret a published performance gap that falls below the MRG?
-
How much do the results depend on how the graph is divided into blocks for the bootstrap?
-
How representative is the sample of 86 published performance gaps used in the literature analysis?
5 comments
Response to Reviewer 2G7s (2/2)
W2: presentation and strength of language. §3 opens with a "quantities at a glance" table (dependence → D → n_eff → MRG: what each is a property of, how it is estimated, which claim it supports). "Unresolvable" is replaced by "below the benchmark's resolution (underpowered)" throughout. The abstract calls the corpus a convenience sample, reports the range over reference models (41–77%) rather than one share, and names the part that is robust (rank-1-vs-2 gaps).
W3: theoretical justification for GPBB. GPBB does not rest on Prop. 1's exogenous-noise assumption; Prop. 1 only suggests a block scale. What GPBB estimates is fixed by Prop. 4, the expectation of the cluster-robust variance written out for GPBB: for a fixed partition and per-node statistics with a common mean (regional difficulty treated as a random effect), E[V̂] = (1 − 1/B)·Var(â) − m⁻² Σ_{b≠b'} Cov(U_b, U_b'). The relative bias vanishes when the cross-block covariance is small relative to D and B is large, the low-conductance condition of network cluster-robust inference (Leung, 2023). In 16 synthetic settings the identity predicts the bootstrap mean to Monte-Carlo error, and the cross-block share it isolates orders the topologies by coverage (CiteSeer 14–24%, Cora 29–54%, actor 72–89%).
Q2: dependence on the partition. Up to eleven alternative partitions per benchmark (B from 10 to 100, three BFS seeds, boundary refinement, spectral): the fixed recipe's paired MRG moves ≤ 17% on 11 of 14; the protocol-matched accuracy share ranges 67–78% (single-test-set share 85–89%) (App. N).
Q3: representativeness of the 86 gaps. A convenience sample, as the abstract now says. It is rule-based within each of ten sources (App. F, all now cited): rank-1-vs-2 and rank-1-vs-5 gaps within one table, never across papers, every printed row transcribed. The interval resamples the ten source papers; leaving out any one moves the fixed-recipe share between 74% and 82%. Two systematic samples: on the full ogbn-arxiv leaderboard 16–25 of the 25 state-of-the-art steps are below the protocol MRG across the reference sets (median step 0.17 points; 21 are below even the i.i.d. MRG, so these steps are small whatever the variance model), and in the complete tables of Platonov et al. 87–118 of the 144 adjacent-rank gaps are.
Response to Rebuttal
I appreciate the authors' efforts to address my concerns and provide a detailed rebuttal, but I still have some reservations regarding the following:
- GPBB still falls well below nominal coverage on eight of the fourteen topologies. Proposition 4 helps explain the bias, but I'm not convinced this resolves the reliability concerns or sufficiently supports the main quantitative conclusions.
- The clarification around MRG is helpful, but the results still vary quite a bit across reference models (41–77%). Along with the convenience sample of 86 gaps, this makes the broader conclusions difficult to assess.
- The additional analysis is useful, but I'm still unsure how well the theoretical arguments support the block construction in practice, particularly when there is substantial cross-block dependence.
Overall, while I appreciate the improvements, my main concerns remain. Thus, I will keep my original score.
Response to Reviewer 2G7s (1/2)
Thank you for a critical review; it prompted the analyses we think strengthen the paper most.
W1/Q1: calibration and the reliability of the MRG. Your concern is valid: GPBB does not attain nominal coverage everywhere. We now calibrate on all 14 benchmark topologies at the radius, block count and test size of the fixed-recipe audit (App. P). On the six with median block conductance ≤ 0.4 coverage is 0.886–0.934 (moderately below 0.95 on Cora); on the eight whose blocks lose most of their edges it is 0.33–0.79. GPBB beats the i.i.d. interval in all 28 cells. Table 2 flags the eight leaky rows; there GPBB underestimates D on average.
Prop. 4 says why: E[D̂] = (1 − 1/B)·D − κ×, so the expected error is −D/B − κ×, a finite-block term plus the covariance GPBB misses across block boundaries. It is an identity for the expectation, not a bound on any one estimate. κ× ≥ 0 for every field our generator can produce (non-negative smoothing, one threshold direction), and on roman-empire the bootstrap mean lies within the Monte-Carlo error of D. For a paired comparison the relevant field is the difference of the two correctness vectors; for ROC-AUC the identity holds for the linearized statistic. It does not make any audited gap conservative, and the revision no longer says so anywhere.
Do the conclusions depend on the leaky rows? On the six low-conductance topologies the audit gives 44/58 (fixed recipe), 32/58 (strong models from different implementations) and 23/58 (strong one-recipe pairs), in line with the overall shares. The stronger models' partitions are sized to their own receptive fields and lie outside the radius-4 calibration; we state this.
How to read a gap below the MRG. The benchmark, under the protocol that produced the gap, had less than 80% power to detect a true difference of that size. It does not mean the gap is non-significant: with the fixed recipe 55/86 are below the 5% threshold against 66/86 below the MRG. And the MRG depends on the pair compared: with the strongest, most alike reference pairs the share below it falls to 41% overall, while 63% of the rank-1-vs-2 gaps stay below it (§7.5).