How Much of a Crawled Benchmark Score Is the Seed?

Many graph classifiers are scored on data gathered by a crawler: a program that starts from a few chosen nodes (the seeds) and follows links outward, as in social network or web crawls. When the class of interest is rare (fraud accounts, a small sub-population) and the graph is split into pieces or narrow bottlenecks, the crawler sees only what is reachable from its seeds. The score computed on that crawl therefore reflects where the seeds happened to land as much as what the classifier learned. Aggregate metrics hide this. A minority class that the crawl never reached cannot lower accuracy or AUROC, so the number looks fine.

We propose an estimator, and an accompanying study, that turns a crawl into an honest population-level estimate of class-balanced performance (per-class recall and balanced accuracy, the mean of per-class recalls). It does three things. It corrects the crawler's preference for high-degree nodes. It produces confidence intervals that remain valid even though crawled nodes are correlated. It reports explicitly how much of the uncertainty comes from graph regions the seeds never reached. The new ingredients are, first, choosing new seed groups during the crawl according to which class's recall is still most uncertain, and second, worst-case bounds that attribute the unreached mass to the score instead of silently dropping it.

Core Claim

The error in a crawl-based estimate of minority-class recall splits into three parts. The first is degree bias: random walks visit nodes in proportion to their number of links, and weighting each visit by one over degree fixes this. The second is correlation among samples taken in the same neighborhood, which makes naive confidence intervals far too narrow. The third is seed placement: which components and bottleneck-bounded regions the crawl can reach at all. Existing tools fix the first two. Nothing fixes the third, and our claim is that for rare classes on fragmented graphs the third part dominates. It is the graph-crawling form of the "seed lottery," the finding that changing only the seeds can swing results widely. A crawler-side seed allocation that targets minority-recall uncertainty, combined with partial-identification bounds for the unreached part of the graph, should shrink this seed-to-seed spread and restore nominal confidence-interval coverage. Neither degree reweighting nor random jumps achieves that alone.

What Prior Work Gives Us and Where It Stops

Two papers supply the method.

Should We Be Confident in Peer Effects Estimated From Social Network Crawls? introduces random walk tour sampling. Its building block is the tour: a walk that leaves a fixed seed set and stops when it returns to that set. Successive tours are independent and identically distributed, so ordinary bootstrap resampling over tours yields valid confidence intervals. On the Purdue Facebook network this restores coverage to 94–100% while querying about 15% of the graph, against near-zero coverage for BFS and plain random walks. We reuse tours directly. That paper, however, treats the seed set as given, estimates peer effects rather than classifier metrics, and never studies label imbalance. In particular, it does not address that a tour through a rare class may almost never happen.

Characterizing Directed and Undirected Networks via Multidimensional Walks with Jumps and Estimating and sampling graphs with multidimensional random walks supply coordinated walker fleets and random jumps that escape dead ends and disconnected pieces. We treat these as the strongest competitor, not as a component, because jumps presuppose that uniform node queries are affordable. The Frontier Sampling paper itself notes that this fails when the space of node IDs is sparse.

Three papers motivate the problem.

Web-Scale Distributional Similarity and Entity Set Expansion shows that across 30 seed sets for the same expansion task, precision differs by 42% between the best and worst seed set, with returns plateauing after 10–20 seeds. It does not ask whether graph topology causes the spread. Inducing Domain-Specific Sentiment Lexicons from Unlabeled Corpora bootstraps over seed subsets to obtain per-node confidence. Resampling seeds, however, cannot reach regions that no seed connects to, which is exactly the regime we target. Reply: metrics to assess machine learning models explains why AUROC absorbs large numbers of false positives under imbalance. Balanced Accuracy: The Right Metric for Evaluating LLM Judges - Explained through Youden's J statistic justifies balanced accuracy as the target quantity.

Three papers constrain the design.

ImVerde pushes walks away from over-visited majority hubs to improve minority representation, reaching AUC 0.95 against 0.85 for DeepWalk on Cora_7. It changes the training data, gives no estimator with valid uncertainty, and admits it cannot cross disconnected components. Pure Node Selection for Imbalanced Graph Node Classification shows that minority seeds surrounded by majority neighbors ("confusion nodes") destabilize over-sampling, and it filters them using full offline knowledge of the graph and its labels. Our crawler has only local visibility, so purity can be observed only along tours. Metrics for Evaluation of Word-level Machine Translation Quality Estimation warns that minority F1 alone rewards over-predicting the minority class. We therefore estimate per-class recall and precision jointly rather than any single minority score.

Research Program

The object of study is a fixed, already-trained node classifier, such as GCN-based PNS+GraphENS. It is evaluated by an agent that can query a node, see that node's neighbors and its true label (for example a profile attribute), and spend a fixed query budget.

The estimator runs tours from several disjoint seed groups. Each group acts as one merged node, as in tour sampling. For seed group $s$ with tours $T_1,\dots,T_K$, the recall estimate for class $c$ is

$$\hat R_c^{(s)} = \frac{\sum_{k=1}^{K}\sum_{v\in T_k} \mathbb{1}[y_v=c,\ \hat y_v=c]/d_v}{\sum_{k=1}^{K}\sum_{v\in T_k} \mathbb{1}[y_v=c]/d_v},$$

where $y_v$ is node $v$'s true label, $\hat y_v$ is the classifier's prediction, and $d_v$ is its degree. Because tours are independent, both sums are averages of independent tour totals. A bootstrap over tours, or the delta method, therefore gives a valid interval for this ratio within the region the group reaches.

Seed allocation is sequential. After each round, the next tour budget goes to the seed group whose contribution most reduces the width of the interval for the worst-estimated class. This is Neyman-style allocation, the classical rule of spending more samples where variance is highest. Using the wider interval of that class or the minimum over classes are variants we will compare. When tours reveal that a group's minority nodes are mostly confusion nodes, the agent spawns a new seed group at an observed minority node with higher local purity. This is an online, partial-information version of PNS's filter. Tours within a round remain independent given the seed group. We will verify empirically that adaptivity does not break coverage, and fall back to a split that holds out some rounds purely for estimation if it does.

The unreached part of the graph is handled with bounds. If the population size is known (platforms often publish it) or can be estimated from occasional uniform queries, the uncovered mass is $N_{\text{un}}$. The minority recall interval is then widened to the worst case over every possible count of minority nodes among the unreached nodes and every possible correctness rate for them. These are Manski-style partial-identification bounds: bounds that assume nothing about the unobserved part. They will often be wide. The point is that the reported number then says how much is unknown, and that the allocation strategy is judged partly by how quickly it shrinks this width.

The analysis reruns everything across 30 independently drawn seed sets per graph, matching Pantel et al.'s protocol. It measures the spread of estimated balanced accuracy and splits it into the three error sources above. Each source is isolated by switching off one correction at a time.

Baselines

The naive reference is what practitioners do now. Crawl with BFS or a simple random walk from the given seeds, then compute accuracy, AUROC, and balanced accuracy on the crawled nodes as if they were a random sample, with intervals from a standard binomial or bootstrap over nodes. It runs on the same budget and seeds. Beating it means coverage near the nominal 95% where it fails, and an estimate closer to the full-graph value. Yang et al. report near-zero coverage for this family on peer-effect estimation. No reported result was found on Lacuna for its coverage on classifier balanced accuracy, so we measure it.

The first strong baseline is a random walk with one-over-degree reweighting, with intervals from batch means. This is the standard fix for degree bias and needs no new machinery. It is run on the same budget with the same seeds. Beating it requires better minority-recall coverage on graphs with several components or low-conductance cuts. On well-connected graphs we expect it to tie, and we will report that outcome.

The second is plain tour sampling with a single fixed seed set, exactly as in Should We Be Confident in Peer Effects Estimated From Social Network Crawls?, applied to our ratio estimator. It is the strongest existing method with valid intervals. Its reported figure is coverage of 94–100% on the Purdue Facebook network for peer-effect estimates. No reported result was found on Lacuna for its coverage on minority-class recall. Beating it means equal or better coverage together with a substantially smaller spread across the 30 seed sets for minority recall.

The third is DUFS-style coordinated walkers with random jumps from Characterizing Directed and Undirected Networks via Multidimensional Walks with Jumps. Each jump is charged its true query cost, and we sweep the cost from cheap (dense ID space) to expensive (sparse ID space). This baseline gets the same tuning budget for its jump weight as we get for allocation rules.

The ablations isolate the key ingredients. The first keeps multiple seed groups but allocates the budget uniformly. The second keeps adaptive allocation but drops the purity-triggered respawning. The third removes the unreached-mass bounds. If uniform allocation over multiple groups matches the full method, the contribution reduces to "use more seed groups," and we will say so.

Why not just…?

Why not just compute balanced accuracy on the crawled nodes? Balanced accuracy removes the class base rate but not selection effects within a class. Crawled minority nodes are the high-degree, well-connected ones, and classifier correctness plausibly correlates with degree and neighbor purity, as PNS's confusion-node finding suggests. The naive baseline measures this bias directly against the full-graph ground truth. We expect it to fail most clearly on PubMed-LT and OGB-Arxiv, where the imbalance is extreme.

Why not just reweight random-walk visits by one over degree? This is the most serious simple threat. It removes stationary degree bias at zero cost. It cannot, however, assign weight to nodes the walk never visits, and it says nothing about correlated samples. On a single well-mixed component it may match our method, and the experiments are designed to show where that holds. The decisive comparison is on Flickr, which the file describes as having disconnected components, and on graphs where we deliberately cut bottlenecks.

Why not just add random jumps, as DUFS does? When uniform node queries are cheap, jumps reach every component and may make our seed allocation redundant. We treat this as a real possibility. The jump-cost sweep is meant to locate the crossover point. The method is useful only below that point, in API-limited crawls where Ribeiro and Towsley note that uniform queries have low hit rates.

Why not just use more seeds? Pantel et al. find that expansion plateaus after 10–20 seeds, and more seeds placed in the same region add no reach. Our multiple-groups-with-uniform-allocation ablation tests the stronger version of this objection: more seed groups, but without targeting. If that ablation matches the full method, targeting adds nothing.

Proposed Experiments

The graphs are those in the file that come with ground-truth labels and can be crawled in simulation. Cora-LT, PubMed-LT, and OGB-Arxiv (imbalance ratio 942) cover extreme label skew. The Purdue Facebook network allows direct comparison with tour sampling's reported coverage. Flickr supplies natural fragmentation. Friendster supplies demographic attributes at scale. On each graph we additionally create controlled variants by placing minority communities behind cuts of decreasing conductance (how many edges cross the cut relative to its size). This varies how hard the minority is to reach. Traversals use the samplers in Little Ball of Fur, extended with merged-seed tours, because that library assumes a single connected component.

The classifier under evaluation is a GCN with PNS+GraphENS trained on the full graph. That paper reports 79.94% accuracy on PubMed-LT against 76.90% for vanilla GraphENS. Its full-graph balanced accuracy and per-class recall serve as ground truth.

The metrics are four. Empirical coverage of nominal 95% intervals for balanced accuracy and minority recall, over 30 seed sets and repeated runs. Absolute error of the point estimate. The spread between the best and worst of the 30 seed sets. The width of the partial-identification bound as a function of budget.

The decisive checks are three. First, on fragmented or low-conductance graphs, our estimator must keep minority-recall coverage near 95% while single-seed-set tour sampling and degree-reweighted walks drop well below it. Second, the seed-to-seed spread of estimated balanced accuracy must shrink relative to uniform allocation over the same seed groups. Third, as minority communities become better connected, the advantage should disappear smoothly. If it persists on well-mixed graphs, something other than reach is driving it, and the claim is wrong. A further falsification test is the jump-cost sweep. If DUFS with realistically priced jumps dominates everywhere, the proposal collapses to a recommendation to use jumps, and we will report it that way.