How Graph Bias Scales: A Finite-Size Scaling Test for Fair Graph Neural Networks

Graph neural networks (GNNs) are models that build each node's representation by repeatedly averaging in information from its neighbors. On social and financial networks they leak demographic information even after the sensitive column is deleted. The reason is homophily: people link mostly to people like themselves, so a node's neighborhood acts as a proxy for its race or gender. Every fair-GNN method in the literature is judged on a single fixed graph, often a small one such as German Credit with about a thousand nodes, and reports a single number such as a statistical parity gap. Nobody knows whether those numbers survive when the same population is modeled at a million nodes. They might shrink, stay fixed, or flip because the graph crossed a threshold.

We propose to answer this with finite-size scaling. This is the physicist's tool for deciding, from a series of finite systems, whether a sharp change is a true transition or an artifact of small size. Applied here, it would measure how bias amplification depends on graph size, homophily strength, and network depth. The central claim is that sensitive-attribute leakage in a message-passing network is controlled by one scaling variable: depth measured against the graph's typical path length, which grows like $\log N$ in sparse graphs. Below a critical homophily the leakage collapses onto a curve that decays with $N$; above it the leakage stays finite. If this holds, fixed-size benchmarks systematically misstate how well debiasing methods work at deployment scale. It would also tell practitioners when a method's fixed design choices, such as keeping fewer than ten eigenvalues, must break.

Core Claim

Finite-size scaling says that near a continuous transition, an observable $O$ measured on a system of size $L$ depends on size only through the ratio of $L$ to a diverging correlation length. That gives $O = L^{-\rho/\nu} f(tL^{1/\nu})$, where $t$ is the distance from the critical point and $f$ is a universal curve. For a graph with $N$ nodes and mean degree $d$, the analog of linear size is the hop distance at which neighborhoods start to cover the graph, roughly $\log N/\log d$. Our hypothesis for the leakage $\Lambda$ is the following. Define $\Lambda$ as the AUC of a held-out linear probe predicting the sensitive attribute from frozen representations, minus 0.5. Then

$$\Lambda(h, \ell, N) = N^{-a}\, f\!\left((h-h_c)\,N^{1/\nu},\; \frac{\ell \log d}{\log N}\right).$$

Here $h$ is the edge homophily (the fraction of edges joining same-group nodes), $h_c$ is a critical homophily, $\ell$ is the number of message-passing layers, and $a, \nu$ are exponents to be fitted. The form comes from treating $\ell$-hop aggregation as a diffusion whose reach, relative to graph size, plays the role of $L/\xi$.

The hypothesis is falsifiable in three distinct ways. Curves at different $N$ may fail to collapse under any choice of exponents. The collapse may hold but with $a=0$ everywhere, meaning no threshold and only a size-independent crossover. Or the apparent threshold may drift with $N$ without sharpening. The last case would mirror the "false thresholds" that Eliminating false defect thresholds exposed in surface growth.

We do not treat symmetric mass generation (SMG) as a mechanism for fairness. In physics, SMG is a gap opening in interacting fermions without any symmetry being broken. We considered importing it as a debiasing design ("gap out the sensitive modes with multi-body couplings instead of penalties") and rejected it. We found nothing in the file that turns that analogy into a concrete objective that a reviewer could not replace with an ordinary invariance penalty.

SMG does supply the methodological template. Disorder Operator and Rényi Entanglement Entropy of Symmetric Mass Generation certified a transition that has no order parameter. It did so by tracking several scale-dependent probes (the single-particle gap, a disorder operator, and entanglement entropy) across lattice sizes, and it located the critical point at $V_c = 2.00(5)$ where these probes cross or peak. We borrow that discipline. A debiasing method that truly removes sensitive information without hurting utility is the graph analog of "gap without symmetry breaking." It should show leakage decaying with $N$ while task accuracy saturates, and several independent probes should agree on the location of any threshold. A single parity number at one size cannot establish this.

Prior Work and Its Role

Three papers motivate the gap. On Size Generalization in Graph Neural Networks shows that GNN accuracy degrades on larger graphs because the distribution of local neighborhood patterns shifts, and that deeper networks degrade faster. It measures only accuracy, never bias, and we extend its size axis to leakage. EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks argues that message passing is a low-pass filter, so structural bias lives in low frequencies. FUGNN: Harmonizing Fairness and Utility in Graph Neural Networks argues that sensitive attributes align with the largest-magnitude adjacency eigenvalues and keeps only $K<10$ of them.

The research file frames EDITS and FUGNN as contradictory. We think that framing is largely a sign convention, because top adjacency eigenvectors are the smoothest, lowest-frequency Laplacian modes. What remains genuinely open is how many such modes carry demographic signal as $N$ grows. In homophilous graphs the number of demographic communities resolvable by the spectrum can grow with size, and if it does, a fixed $K$ must eventually fail. This is a sharp, testable prediction that neither paper examines.

Three papers supply the method. Impact of single links in competitive percolation separated weakly discontinuous transitions ($\Delta C_{max}/N \sim N^{-\beta}$ with $\beta \approx 0.065$) from truly discontinuous ones ($\beta=0$) using sizes up to $2^{26}$. We reuse its largest-jump statistic to ask whether leakage jumps as $h$ varies. The Statistical Mechanics of k-Satisfaction supplies the rescaled control variable $y = N^{1/\nu}(\alpha-\alpha_c)/\alpha_c$ for collapsing threshold curves of combinatorial graph problems. Cascade of phase transitions in the training of energy-based models shows that this toolkit transfers to learned models. It found mean-field ($\gamma=1$) transitions in restricted Boltzmann machines, and it also warns that critical slowing down limits the reachable sizes.

Two further papers constrain the design. Towards Fair Graph Neural Networks via Graph Counterfactual (CAF) treats the graph as a causal collider between content and demographic environment. Its counterfactuals are drawn from the training set, so the supply of counterfactuals itself changes with $N$, and its measured gains may be size-dependent for that reason alone. Li et al. report that more expressive hypergraph models are less fair than non-relational baselines. This tells us to include an MLP reference at every size.

Research Program

The first component is a controlled synthetic system. We will generate degree-corrected two-group stochastic block graphs, in which nodes are assigned to groups and link within or across groups with set probabilities. Node features will be partly correlated with a task label that is itself only weakly correlated with group. Sizes run from $10^3$ to $10^6$ nodes at fixed mean degree, homophily $h$ is swept in fine steps, and the sensitive attribute is removed from the features. We will train two-layer to eight-layer GCN and GraphSAGE models, with many graph samples per point. For each model we record three probes, which play the role of the SMG paper's several probes:

  • probe leakage $\Lambda$;
  • the statistical parity gap $\Delta_{SP}$ on the task;
  • the share of representation variance lying in the span of the top-$K$ adjacency eigenvectors, at several values of $K$.

We then fit the scaling form by standard collapse-quality minimization and use bootstrap intervals on $h_c$, $a$, and $\nu$.

The second component carries the scaling analysis to real graphs. Pokec-z and Pokec-n are large enough to subsample. We will draw induced subgraphs at sizes spanning roughly two decades, matching German Credit's scale at the low end. Each size uses two samplers: uniform node sampling, and degree-preserving sampling. The comparison between samplers separates true size effects from the neighborhood-pattern shifts identified by Yehudai et al. On each subgraph we train the base GNN and each debiasing method with identical budgets and record leakage, $\Delta_{SP}$, and accuracy. That gives every method a curve over $N$ rather than a point.

The third component is the spectral test. We will measure the smallest $K(N)$ whose top eigenvectors capture 90% of the demographic signal in the representations. The question is whether $K(N)$ stays bounded, as FUGNN's design assumes, or grows with $N$.

Baselines

The naive reference is an unmodified GCN trained on features with the sensitive column deleted. Alongside it we run an MLP on the same features, which sees no graph and so isolates how much leakage the edges add. On Bail, Towards Fair Graph Neural Networks via Graph Counterfactual reports a GCN $\Delta_{SP}$ of 7.50 and a NIFTY $\Delta_{SP}$ of 5.74. We will reproduce these values at full size as a sanity check before scaling.

The strongest existing methods, run at every size, are the following:

  • CAF reports $\Delta_{SP}$ of 2.29 on Bail and the best average rank (1.75, runner-up 3.83) across its datasets. It is the strongest published competitor on parity.
  • FUGNN reports 80.18% accuracy on Income with $\Delta_{SP}$ cut from 25.90% to 1.43%, and a Pokec-z runtime drop from 3018 s to 10 s. That makes it the only strong method cheap enough to run at our largest sizes, and therefore the decisive competitor for the large-$N$ regime.
  • EDITS reports about 62% attribute-bias and 66% structural-bias reduction on German Credit. It is run where its transport computations remain feasible, and the size at which it stops being feasible is itself recorded.

Fairness of comparison means the same subgraphs, seeds, hidden sizes, and a fixed hyperparameter search budget per method per size. Hyperparameters are tuned on a validation split drawn from the same subgraph.

The ablation that isolates our key ingredient is a scaled-depth comparison. One arm holds depth fixed as $N$ grows; the other scales $\ell$ to keep $\ell\log d/\log N$ constant. If leakage tracks the scaling variable rather than raw depth, the receptive-field-to-graph-size ratio is the controlling quantity.

Our contribution is diagnostic rather than a new debiaser. "Beating" the baselines therefore means predicting their behavior. We succeed if a collapse fitted on sizes up to $10^4$ predicts each method's leakage and $\Delta_{SP}$ at the largest Pokec size within bootstrap error. The bar is that it must do better than simple extrapolation of the raw curves. A secondary success criterion is FUGNN at fixed $K$ losing parity relative to an $N$-adaptive $K$ at large $N$.

Why not just…?

Why not just evaluate each method at a few graph sizes and plot the curves? That is the naive reference, and we run it. Raw curves cannot distinguish three cases: a threshold that sharpens with size, a smooth crossover, and a drifting artifact. The percolation and surface-growth papers above show these are easy to confuse at accessible sizes. The collapse is what licenses extrapolation to sizes we cannot train on. If the raw curves are flat in $N$ for every method, finite-size scaling adds nothing. We would report that plainly as the outcome "fixed-size benchmarks are trustworthy."

Why not just rely on the theory of community detection in block models? Spectral detectability theory may well predict an $h_c$ for the synthetic graphs, and we will compare against it where it applies. It describes the best possible spectral estimator, however, not a trained nonlinear GNN optimizing a different task. It also says nothing about Pokec, whose degree structure and neighborhood patterns are not block-model-like. If our fitted $h_c$ matches the theoretical value on synthetic data, that is a validation of the method, not a reason to skip it.

Why not just fix size generalization with pattern-tree self-supervision? On Size Generalization in Graph Neural Networks raised average accuracy from 63.5% to 67.5% this way. It targets accuracy under neighborhood-pattern shift, and it could even increase leakage, because better neighborhood modeling is better proxy reconstruction. We include it as an extra arm. If it alone removes the size dependence of leakage, the scaling story reduces to pattern shift. The comparison between the two samplers is designed to detect exactly that.

Why not just build an SMG-inspired debiaser? A "symmetric gapping" layer would, on inspection, be an invariance penalty under a new name. Without a measurable analog of anomaly cancellation it would not be falsifiable, so we keep SMG as the template for multi-probe certification of a transition and do not offer it as a method.

Decisive Checks

The first decisive check is the synthetic collapse. Leakage curves for $N$ from $10^3$ to $10^6$ either collapse under a common $(h_c, a, \nu)$ with $a>0$, or they do not. The second is the jump test. The largest leakage change between adjacent $h$ values either scales away as $N^{-\beta}$ with $\beta>0$ or stays finite, which tells us whether bias onset is continuous or abrupt. The third is the spectral count: whether $K(N)$ grows on Pokec subgraphs. The fourth is held-out prediction, where a collapse fitted on small subgraphs must predict CAF, FUGNN, and EDITS at the largest size.

Any one of these can fail independently. The combination would tell practitioners whether the parity numbers reported on thousand-node graphs mean anything at deployment scale.