Class imbalance in node classification is usually measured by counting: a minority class with 20 labeled nodes gets up-weighted or oversampled until it matches a majority class with 500. On a graph, though, labeled nodes are not independent draws. Suppose all 20 minority labels sit inside one tightly knit community that random walks rarely leave, a region the graph "mixes" through slowly. Then those labels largely repeat each other, and the model has closer to a handful of independent minority examples than to 20. We propose to measure this redundancy directly with a class-conditional effective sample size. It is computed from how much the propagation footprints of same-class labeled nodes overlap. The overlap is weighted by how strongly labels actually correlate at each walk distance, which makes the measure valid on both homophilic graphs (neighbors tend to share labels) and heterophilic graphs (neighbors tend to differ).
The practical payoff is a cheap change to the losses and oversamplers that imbalance methods already use. Loss weight inside a class is spread by inverse redundancy, not uniformly, and oversamplers choose interpolation partners that are informationally far apart, not nearest. The scientific payoff is a falsifiable claim. Minority-class error should track effective minority sample size, not the raw label count. The gap between the two should widen as the graph's mixing slows.
Core Claim
Minimax Sample Complexity of Graph Neural Networks proves an "effective sample size collapse" for balanced, homophilic graphs with weak spectral expansion (a small Laplacian spectral gap, meaning random walks mix slowly). In that regime, $n$ correlated labels carry only about $\log n$ independent pieces of information, and error decays like $1/\log n$. That paper assumes balanced classes and homophily, and it proposes no remedy. We move the same idea to the class-conditional, imbalanced setting, where it matters most. A minority class whose few labels share one slow-mixing community should suffer a collapse far worse than its label count suggests. Existing imbalance methods are blind to this. GraphSMOTE interpolates each minority node with its nearest minority neighbor, which is exactly the most redundant partner. Count-based re-weighting treats every minority label as equally informative.
We define the measure as follows. Let $P$ be the random-walk transition matrix. Let $\gamma_k$ be the empirical label autocorrelation between training nodes at walk distance $k$; this is a "correlogram," positive at $k=1$ on homophilic graphs and typically negative at $k=1$ but positive at $k=2$ on heterophilic ones. We define a propagation kernel and its normalized form
$$K = \sum_{k=0}^{T} \gamma_k^2 P^k, \qquad \rho_{ij} = \frac{K_{ij}}{\sqrt{K_{ii}K_{jj}}},$$
where $T$ is a truncation depth matched to the backbone's receptive field. Squaring $\gamma_k$ means that strong negative correlation also counts as shared information. For the labeled set $L_c$ of class $c$ with per-node weights $w_i$, the effective sample size follows the design-effect formula from survey sampling:
$$N_{\text{eff}}(c) = \frac{\left(\sum_{i\in L_c} w_i\right)^2}{\sum_{i,j\in L_c} w_i w_j \rho_{ij}}.$$
With independent labels, $\rho_{ij}=0$ for $i\neq j$ and $N_{\text{eff}}$ recovers the count. With fully redundant labels it falls to 1. This single quantity connects the three directions. Mixing time controls how slowly off-diagonal $\rho_{ij}$ decay inside communities. Homophily enters through $\gamma_k$. Imbalance is where a small $N_{\text{eff}}$ turns into a failure.
Research Program
The program has three parts.
Diagnostic. We compute $N_{\text{eff}}(c)$ for every class on standard imbalanced benchmarks. We then ask whether it predicts per-class recall better than the raw count $|L_c|$ does, across graphs and splits. Labeled sets are small (tens to low hundreds per minority class), so we compute the needed rows of $P^k$ by truncated sparse propagation from each labeled node, even on ogbn-arxiv. We deliberately avoid long random-walk estimators. Mixing Time Matters reports real-world mixing times above 10,000 steps, where walk-based estimates of global quantities become unreliable. The walk literature therefore motivates the quantity but does not supply our estimator. The correlogram $\gamma_k$ is estimated from all labeled nodes, majority included. Sparse-label estimation noise is a known problem for heterophily-aware methods, so we report bootstrap intervals and an ablation that estimates $\gamma_k$ from pseudo-labels.
Remedy. The remedy is two drop-in changes. The first is redundancy-aware weighting. Each class keeps equal total loss weight, as in class-balanced re-weighting. Within a class, weight is spread proportional to $1/\sum_j \rho_{ij}$, so labels inside a crowded, slow-mixing pocket share weight and isolated labels count fully. The second is diverse-partner synthesis. In GraphENS-style and GraphSMOTE-style mixing, the minority partner is sampled with probability decreasing in $\rho_{ij}$ with the anchor. Synthetic nodes are therefore interpolated across communities, not within them. Neither change touches the backbone, so both stack onto heterophily-aware encoders such as the two-channel filterbank of FB-GNN. We are honest about the limit here. Synthesis cannot create label information that is not there. We expect the weighting to carry most of the gain, and the synthesis change to matter mainly where GraphENS-style methods currently overfit to one neighborhood.
Theory (modest). We will state and test a class-conditional analogue of the spectral–homophily lower bound, in which minority error scales with $N_{\text{eff}}(c)$. We will attempt a proof only for a two-block stochastic block model, where $\rho_{ij}$ has a closed form in terms of the spectral gap.
Baselines
The naive reference point is a vanilla GCN trained with plain cross-entropy. GraphENS reports 62.72% balanced accuracy for it on Cora-LT. The second reference is the same GCN with inverse-class-frequency loss weights. This is the direct ablation of our key ingredient: it is identical to our method except that within-class weights are uniform.
The strongest homophilic-imbalance competitor is GraphENS, which synthesizes full 1-hop ego networks with saliency masking. It reports 72.94% balanced accuracy on Cora-LT, the strongest concrete number in our file. GraphSB adds structure enhancement and low-pass relation diffusion before oversampling. It reports 80.82% accuracy on PubMed and an average 4.57% gain as a plug-in, including on ogbn-arxiv at imbalance ratio 0.001.
The strongest competitor on heterophilic imbalance is GraphSANN. It mixes minority nodes with nodes of any class, extracts adaptive subgraphs, and encodes them with multiple filters. It is evaluated on Chameleon, Squirrel, and Film, but no reported result was found on Lacuna for its exact per-dataset scores, so we will rerun it. For shallow walk-based imbalance learning we include ImVerde, which reports AUC 0.95 on Cora_7 against 0.85 for DeepWalk.
All methods share identical splits and imbalance protocols: Cora-LT, step imbalance as in GraphSB, and 20 labels per minority class as in GraphSANN. All get the same backbone family and the same hyperparameter search budget of fixed trials per method on validation balanced accuracy, with ten seeds each. We re-run published baselines instead of copying numbers, and we report our reruns next to the cited figures.
Beating a baseline means one of two things. Adding our weighting and partner selection to that same baseline improves minority macro-F1 or balanced accuracy beyond seed variance. Or plain GCN or FB-GNN plus our weighting matches GraphENS or GraphSANN at a fraction of their cost. The within-class ablation is decisive. If $N_{\text{eff}}$-based weights do not beat count-based weights, the remedy has no reason to exist.
Why not just…?
Why not just re-weight by class frequency? This is the real threat, because our method is re-weighting. GraphSMOTE and GraphSB report that count-based re-weighting plateaus as imbalance grows. They attribute this to topology, but they never separate redundant labels from informative ones. Our ablation holds everything fixed except the within-class allocation. If that allocation does nothing, we will say so, and keep the diagnostic as the contribution.
Why not just use a topology-aware imbalance method like GraphSB or GraphENS? GraphSB's diffusion is low-pass and its added edges are constrained to latent-similar nodes. The file's own gap analysis argues this accelerates assimilation on heterophilic graphs. GraphENS works only within 1-hop ego networks, so it cannot see that two minority labels share a slow-mixing community several hops wide. Zhao et al. show that topology-level imbalance exists even under balanced labels. That motivates us, but it does not measure redundancy among the labeled set under the label correlogram. Our method is additive to all of these, so the test is whether stacking it on them helps.
Why not just switch to a heterophily-aware backbone such as MixHop or FB-GNN? MixHop and FB-GNN fix the filter, not the label budget. Wider receptive fields also raise the share of majority nodes around each minority node. We run FB-GNN with and without our weighting. If the backbone alone closes the minority gap on Chameleon and Squirrel, our effect is confined to homophilic graphs and we will report it that way.
Proposed Experiments
The decisive check is a placement experiment. On Cora, PubMed, Amazon-Computers, Chameleon, and Squirrel, we fix the minority label count at 20. We then choose those 20 labels either clustered (all inside one community found by spectral clustering) or spread across communities, holding every other label fixed. The core claim predicts three things. Clustered placement yields markedly lower minority recall at equal count. $N_{\text{eff}}$ explains that drop, while $|L_c|$ cannot. The clustered-versus-spread gap grows as the spectral gap shrinks. We test the last prediction in a controlled stochastic block model sweep over inter-community edge density, and across real graphs ordered by $\lambda_2$.
The second check is predictive. Across all benchmark splits, we regress per-class recall on $\log N_{\text{eff}}(c)$ versus $\log |L_c|$ and compare the held-out fit.
The third is the method comparison under the fair protocol above. It spans Cora-LT, step-imbalanced Citeseer and PubMed, GraphSANN's imbalanced heterophilic splits, naturally imbalanced Amazon-Computers, and ogbn-arxiv at ratio 0.001. We report balanced accuracy, macro-F1, and minority recall, plus the cost of computing $\rho$ in wall-clock time relative to GraphENS's saliency step.
We also include a failure-case check. On fast-mixing graphs where $\rho_{ij}$ is nearly uniform, our weighting should reduce to class-frequency weighting and give no gain. Observing gains there would suggest the effect is something other than what we claim.
References
- Minimax Sample Complexity of Graph Neural Networks: Lower Bounds and Structural Effects
- GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks
- Mixing Time Matters: Accelerating Effective Resistance Estimation via Bidirectional Method
- GraphENS: Neighbor-Aware Ego Network Synthesis for Class-Imbalanced Node Classification
- Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks
- GraphSB: Boosting Imbalanced Node Classification on Graphs through Structural Balance
- Imbalanced Node Classification Beyond Homophilic Assumption
- ImVerde: Vertex-Diminished Random Walk for Learning Imbalanced Network Representation
- TopoImb: Toward Topology-level Imbalance in Learning from Graphs
- MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing