Correcting Crawl Bias in Decoupled Heterophilous Graph Filters

Many of the graphs we most want to classify, such as social networks, the web, and transaction networks, are never seen whole. We see them through a crawler: a program that starts at some nodes and follows links, the way breadth-first search or a random walk does. Crawlers over-collect highly connected "hub" nodes and miss the sparse periphery (Towards Unbiased BFS Sampling, Subsampling in Large Graphs Using Ricci Curvature). Separately, the fastest graph learners for large graphs are decoupled: they run a fixed smoothing or sharpening operation over the graph once, offline, and then train a plain neural network on the resulting features. The decoupled methods that also handle heterophily, meaning graphs where linked nodes tend to have different labels, mix several such filters. These include LD2 (LD2) and ASGC (Simplified Graph Convolution with Heterophily). Some of their filters average over neighbors ("low-pass"), others subtract neighbors ("high-pass"). Both methods assume the full graph is available. No one has asked what happens when their offline filtering runs on a crawled graph.

This note argues that the damage from a crawl splits into two separable errors, and that the second has been overlooked. The first is distortion of the filter operator itself: missing edges and wrong degrees. The second is distortion of which filter gets chosen. A crawl that over-samples hubs changes the mix of node types the filter is fit on. Prior work shows hubs and low-degree "spoke" nodes need different amounts of smoothing (Two Sides of the Same Coin), so the fitted filter comes out wrong for the full graph. We propose to correct both errors with inverse-inclusion-probability weighting from survey statistics, and to measure which correction actually matters.

Core Claim

When a decoupled filter for heterophilous graphs is computed on a crawled graph, most of the accuracy loss on the full graph comes from biased filter selection, not from operator distortion. The filter selection includes the polynomial coefficients deciding how much low-pass versus high-pass signal to keep, plus the classifier trained on top. Two corrections follow. The first is cheap: weight each crawled node's training loss by the inverse of its probability of being crawled, the Horvitz–Thompson correction from survey statistics. The second is costlier: also reweight the edges inside the propagation operator. On low crawl budgets, the second correction adds variance that compounds with every hop, so it should help only for the first one or two hops.

The prediction is falsifiable in both directions. If full operator reweighting is what closes the gap, the claim is wrong. If simply renormalizing with the true degrees of crawled nodes closes the gap, the claim is also wrong. That would be a useful negative result.

The closest prior work plays three distinct roles here. Dirichlet Meets Horvitz and Thompson supplies the estimation technique. It shows that inverse-inclusion weighting recovers a graph's Dirichlet energy, a single number measuring how much a signal varies across edges and hence a proxy for homophily, from Bernoulli, uniform and traceroute samples, with bias typically at most $10^{-3}$ at 30% node observation. It stops at a scalar, though: it never trains a model or corrects a propagation operator.

GraphSAINT (GraphSAINT) supplies the closest learning-side analogue. Its aggregation and loss normalizers are inverse-inclusion weights for minibatches drawn from a fully known graph with computable inclusion probabilities. In a crawl, by contrast, the unobserved graph cannot be enumerated, and inclusion probabilities must be approximated from the crawler's mechanics. Large Scale Learning on Non-Homophilous Graphs constrains the design: subgraph sampling of the GraphSAINT kind loses 5–10% accuracy on non-homophilous graphs. A method that reweights locally sampled neighborhoods during training is therefore suspect. This is why we keep propagation decoupled and offline rather than per-minibatch.

Research Program

The pipeline has three stages. Each stage can be turned on or off independently, which makes the decomposition testable.

Stage 1: inclusion probabilities. We assume the realistic crawl setting in which visiting a node reveals its full neighbor list and therefore its true degree $d_i$. Under a simple random walk, the probability of visiting node $i$ is approximately proportional to $d_i$. Under breadth-first search, we use Kurant's characterization of degree bias (Towards Unbiased BFS Sampling). Under Bernoulli node sampling, the probability is the sampling rate. An edge is observed if either endpoint is visited, giving $\pi_{ij} \approx \pi_i + \pi_j - \pi_i\pi_j$. Because these probabilities are approximations, we also run a robustness arm that perturbs them.

Stage 2: operator correction, optional and hop-limited. We build the normalized propagation operator in ratio form. The edge sums are weighted by $1/\pi_{ij}$, and the degree normalizers use revealed true degrees rather than observed degrees. This is the operator-level analogue of the Horvitz–Thompson Dirichlet estimator. We expect variance to multiply roughly with each additional hop, since each power of the operator chains another product of inverse probabilities. So we apply the corrected operator only for hops $k \le k^\ast$ and use the uncorrected operator beyond that. The cutoff $k^\ast$ is chosen by a bootstrap estimate of feature variance over repeated crawls.

Stage 3: design-weighted filter and classifier fitting. We precompute LD2-style channels on the crawled graph: a 2-hop adjacency channel, a high-pass channel, and a low-pass channel. We also precompute an ASGC-style stack of features smoothed $0$ through $K$ times. We then fit the mixing coefficients $\theta$ and the classifier $f$ by minimizing

$$\sum_{i \in V_S} \frac{1}{\pi_i}\, \ell\Big(y_i,\; f\big(\textstyle\sum_{k=0}^{K} \theta_k (\hat S^{k} X)_i\big)\Big),$$

where $V_S$ is the set of labeled crawled nodes, $\pi_i$ their crawl probability, $\hat S$ the (optionally corrected) operator, $X$ the node features, and $\ell$ the classification loss. Weights are self-normalized and clipped at a high percentile to bound variance. This step is cheap. It changes nothing about precomputation cost, so the method keeps LD2's scalability, which LD2 reports as training on the 243M-edge wiki graph in under one minute with under 5GB of GPU memory.

Diagnostics. We explain why each correction helps rather than only reporting accuracy, using two diagnostics. The first stratifies accuracy by the relative degree from Two Sides of the Same Coin: a node's degree divided by the mean degree of its neighbors. Low relative degree is the "pseudo-heterophily" regime, where a node is swamped by hub neighbors. We expect crawl bias to hurt these nodes most. The second tracks the effective rank of the propagated features hop by hop on crawled versus full graphs, following Are we measuring oversmoothing in graph neural networks correctly?. Effective rank is an entropy measure of how many independent directions the features span, and it correlates at 0.91 with accuracy in that paper. It shows whether crawl bias speeds the collapse of features toward one direction, which is over-smoothing. Because that paper warns that high rank can be meaningless noise, we read effective rank only alongside accuracy, never alone.

Baselines

Do-nothing baseline. A feature-only multilayer perceptron trained on crawled labeled nodes. It ignores graph structure, so it is immune to crawl bias. Measuring and Improving the Use of Graph Information shows that neighbor averaging under heterophily can fall below it, so any graph method must beat it by a margin larger than across-crawl variation.

Naive reference. LD2 and ASGC run unchanged on the crawled graph. These isolate the cost of the crawl.

Oracle. The same models run on the full graph. This sets the ceiling, and we report the fraction of the oracle gap each method recovers.

Strongest existing competitor: LINKX. Large Scale Learning on Non-Homophilous Graphs embeds each node's adjacency row and its features with separate small networks. It reports 84.71% accuracy on Penn94 against 82.47% for a graph convolutional network (GCN), both on the full graph. It is the strongest competitor because it is the best large-scale non-homophilous method in the file and is robust to minibatching. On a crawl, its adjacency input is restricted to crawled node indices, and held-out nodes are encoded through their revealed links to crawled nodes. No crawled-graph LINKX number exists. For LD2, no reported per-dataset accuracy was found on Lacuna, so both will be rerun ourselves.

GraphSAINT-style normalization. We transplant GraphSAINT's normalizers into the decoupled pipeline, using the same Stage 1 probabilities. This tests whether our weighting is anything more than GraphSAINT's applied offline.

Ablations. These isolate the key ingredient. The first uses true-degree renormalization only. The second adds operator correction without loss weighting. The third uses loss weighting without operator correction. The fourth is the full method. The fifth uses full-depth operator correction with no hop cutoff, to expose variance blow-up.

Fairness. All arms share the same crawls, generated with five seeds per crawler and budget. They also share the same held-out nodes and the same hyperparameter search budget, with equal trials per method, on a single GPU. Beating the strongest competitor means higher mean accuracy than both LINKX and the naive LD2/ASGC on the uniform held-out set, outside the across-crawl standard deviation, on at least four of the six large datasets at budgets of 10% or less.

Why not just…?

Why not just use an MLP and ignore the biased graph? On the full graph, structure clearly carries signal: on Penn94 the reported LINKX and GCN results both rely on structure. Whether that signal survives a 5% crawl is genuinely open. If the MLP matches our method at low budgets, we will report that as the regime where crawled structure stops being worth using. The budget sweep is designed to locate that crossover.

Why not just use LINKX, which already handles non-homophilous graphs without message passing? LINKX is transductive: its input dimension is the number of nodes, and on a crawl that means only the nodes that happened to be crawled. A uniformly sampled held-out node that links mostly to uncrawled periphery has a nearly empty input. That is exactly the population crawlers miss. Our filters, by contrast, are computed from any node's revealed neighborhood. LINKX remains a real threat when held-out nodes are well connected to the crawl, so we report results stratified by how many crawled neighbors a test node has.

Why not just apply GraphSAINT's unbiased normalization? GraphSAINT's guarantee needs exact inclusion probabilities under a sampler run on a known graph. Lim et al. also report its 5–10% degradation on non-homophilous graphs. We nonetheless include it as an arm with our estimated probabilities. If it matches the full method, the honest conclusion is that the contribution reduces to "apply GraphSAINT's weights offline with crawler-derived probabilities." That is still a usable finding, but a smaller one.

Why not just renormalize with the true degrees that a crawl reveals? This is the most serious threat. Symmetric degree normalization already cancels much of the hub over-weighting identified in On Sampling Edges Almost Uniformly. It does not touch the biased node mix that filter fitting sees, which is the core claim's mechanism. It appears as the first ablation. If it recovers most of the oracle gap, the core claim fails.

Proposed Experiments

We simulate crawls on fully known graphs so the oracle is available. The graphs are Penn94, pokec, genius, twitch-gamers, arXiv-year and snap-patents from the non-homophilous suite of Lim et al. Chameleon and Squirrel serve for fast small-scale checks, and Cora and Pubmed act as homophilous controls, where we expect smaller gains. The crawlers are breadth-first search, simple random walk, snowball sampling, and Bernoulli node sampling, at node budgets of 5%, 10%, 20% and 30%. Test nodes are drawn uniformly from the full graph and enter through their revealed neighbor lists, so evaluation is not itself crawl-biased. Metrics are accuracy (ROC-AUC on genius), fraction of oracle gap recovered, accuracy by relative-degree quintile, and per-hop effective rank.

There are three decisive checks. First, in the factorial ablation, loss weighting alone should recover more of the gap than operator correction alone, especially under breadth-first search at 5–10% budgets. Second, gains should concentrate in the lowest relative-degree quintile, linking crawl bias to the pseudo-heterophily mechanism. Third, full-depth operator correction should show bootstrap feature variance rising with hop count and accuracy falling relative to the hop-limited version. A secondary check perturbs the approximate inclusion probabilities by ±50% to see whether the gains survive misspecification, as they must for real crawls where probabilities are never exact. If the second and third checks fail while gains persist, the mechanism story is wrong even if the method works, and we would say so.