Graph neural networks (GNNs) are models that compute a representation for each node by repeatedly averaging information from its neighbors. They are expensive to train on large graphs. A common fix is to shrink the graph first, merging similar nodes into "super-nodes" and training on the smaller graph. A recent survey (A Comprehensive Survey on Graph Reduction) reports emerging evidence that such reduction can amplify biases against minority groups. It also notes that reduction methods are tuned almost entirely for accuracy. We propose a reason this happens and a fix. Existing guarantees for reduced graphs bound the average error the smaller graph introduces into neighbor-averaging. An average can be small while the error is concentrated on a minority group. Because neighborhoods already act as proxies for protected attributes, a merge that changes the demographic mix of what a node "hears" from its neighbors shifts that node's prediction in a group-correlated way.
The fix borrows the central idea of kernelization from parameterized complexity, the exact-preprocessing discipline that shrinks hard combinatorial instances using reduction rules proven not to change the answer. We build graph reduction rules that are safe with respect to a fairness-relevant quantity: each node's group exposure profile, meaning the share of its multi-hop neighbor signal that comes from each sensitive group. Some merges preserve these profiles exactly, such as merging nodes with identical neighborhoods, or folding a dangling degree-one node into a self-loop on its neighbor. These rules form an exact "kernel" of the graph. Approximate merges are allowed only within a tolerance $\epsilon$, and the size of the reduced graph is governed by how many distinct profiles exist at that tolerance. The claim to test is concrete. On standard fair-GNN benchmarks, group-safe reduction should match the compression and speed of accuracy-oriented coarsening while keeping the demographic parity gap at or below the full-graph level, where accuracy-oriented coarsening increases it.
Core Claim
Consider a linear message-passing model such as a simplified graph convolution, which applies the normalized adjacency $S$ to the features $K$ times. For a node $v$, define its exposure to group $g$ as
$$e_v^{(g)} = \left(S^K \mathbf{1}_g\right)_v ,$$
where $\mathbf{1}_g$ is the indicator vector of nodes in sensitive group $g$. In words, $e_v^{(g)}$ is the fraction of $v$'s propagated signal that originates in group $g$.
A reduction maps the graph to a smaller one with assignment matrix $Q$ and is lifted back to the nodes for prediction. Our hypothesis is that the change in the statistical parity gap $\Delta_{SP}$ caused by reduction is predicted by the gap between groups in exposure distortion. It is not predicted by the overall propagation error. For a linear model this has a simple justification. The prediction shift at node $v$ is linear in its propagation error. The parity gap compares group means of predictions. So $\Delta_{SP}$ moves by the difference between the group-averaged errors, and a node-averaged bound hides exactly that difference.
The method follows from this. Exact rules that leave every $e_v^{(g)}$ unchanged are applied first, the analogue of safe reduction rules. Approximate merges are permitted only between nodes whose exposure profiles agree within $\epsilon$. The reduced graph then has at most as many super-nodes as there are $\epsilon$-distinct profile classes. That number becomes the parameter, playing the role $k$ plays in classical kernel size bounds.
We are not claiming a polynomial kernel in the formal sense for an NP-hard decision problem. Kernelization supplies the design discipline here: rules that are safe by proof, applied exhaustively, with the remaining size bounded by a structural parameter. It does not supply a complexity-theoretic result.
How This Relates to Prior Work
The motivation comes from two places. The first is the survey above, which flags reduction-induced bias as open. The second is work showing topology is a bias channel. Towards Fair Graph Neural Networks via Graph Counterfactual (CAF) models the graph as a causal collider that creates spurious dependence between sensitive attribute and label. It debiases by pairing real counterfactual nodes, but it runs on the full, unreduced graph. On Generalized Degree Fairness in Graph Neural Networks shows high-degree hubs dominate message passing. That matters to us because merges near hubs reshape exposure for many low-degree nodes at once.
The closest technical predecessor is Graph Coarsening with Message-Passing Guarantees. It introduces the asymmetric coarsened propagation matrix $QSQ^+$ and bounds the resulting message-passing error, evaluated only for accuracy on citation graphs. We reuse its propagation matrix as the mechanism. What we change is the merge criterion and the guarantee: the bound is group-conditional and is enforced during merging.
Preprocessing debiasers change the graph but do not shrink it, and they offer no exactness. EDITS rewires edges by optimizing a neural estimate of Wasserstein distance between groups. Graphair learns fair edge and feature augmentations adversarially. FUGNN truncates the graph spectrum to the few eigenvalues it finds least correlated with sensitive features. Our goal is different. These methods try to remove bias. We guarantee that compression does not add bias, and we treat them as downstream methods that can run on our reduced graph.
The exact rules come from kernelization. Folding low-degree vertices into self-loops follows A Note on Max k-Vertex Cover. Degree-2 suppression follows The Linear Arrangement Problem Parameterized Above Guaranteed Value. The modulator idea from Polynomial Kernelization for Removing Induced Claws and Diamonds is to isolate a small vertex set so the rest of the graph is simple. We use it to protect hubs and cross-group bridge nodes from merging. Those papers prove equivalence for a combinatorial answer. We prove invariance of exposure profiles under the propagation operator, a different invariant.
Research Program
The first component is a measurement study. We take the coarsening of Joly and Keriven, plus random and feature-similarity merging, across many reduction ratios on fair-GNN benchmarks. For each reduction we record three things: the change in $\Delta_{SP}$ and equal-opportunity gap $\Delta_{EO}$ relative to the full graph, the node-averaged propagation error, and the group-conditional exposure distortion. This first establishes whether reduction amplifies bias on these datasets at all. The survey's claim has not been quantified on them. It then tests whether our quantity predicts the amplification better than the average error.
The second component is the rule set. Exact rules come first. We merge true and false twins whose neighborhoods are identical and carry the same group composition. We fold pendant vertices into weighted self-loops. We contract degree-2 chains whose endpoints share exposure. For each rule we prove that $e_v^{(g)}$ is unchanged for every remaining node under $QSQ^+$. We then report how much real graphs shrink under exact rules alone, an empirical analogue of a kernel size.
The approximate stage greedily merges nodes whose $K$-hop exposure profiles are within $\epsilon$. It is restricted to nodes outside a protected modulator made of the highest-degree hubs and nodes with mixed-group neighborhoods. We bound the parity shift by $\epsilon$ times a constant depending on the trained weights' norm, for linear models first, then test empirically on GCN and GraphSAGE. Exposure profiles are computed with $K$ sparse matrix products, one per group, so the cost scales linearly in edges for binary attributes.
Baselines
The naive reference point is a standard GCN trained on the full graph with sensitive attributes removed from features. It defines the bias level that reduction must not exceed. On Bail, the CAF paper reports a GCN parity gap of $\Delta_{SP} = 7.50$ (Towards Fair Graph Neural Networks via Graph Counterfactual). We will rerun it under our splits rather than rely on that figure.
The strongest competitor on the compression question is message-passing-guaranteed coarsening (Graph Coarsening with Message-Passing Guarantees). It holds the best existing guarantee for training on a reduced graph. The paper reports 78.5% accuracy on Cora at reduction ratio 0.7 with SGC, against 74.6% for naive coarsening and 81.6% on the full graph. For fair-GNN datasets, no reported result was found on Lacuna for this coarsening's effect on $\Delta_{SP}$, so we will produce that number ourselves.
For fairness, the strongest full-graph method in the file is CAF, with $\Delta_{SP} = 2.29$ on Bail, against NIFTY's 5.74 in the same paper. On Income, FUGNN reports 80.18% accuracy with $\Delta_{SP}$ reduced from 25.90% to 1.43% (FUGNN).
All reductions are compared at identical reduction ratios, with the same downstream GNN, splits, hyperparameter search budget, and seeds. Coarsening baselines get the same tuning budget over their own knobs as we give over $\epsilon$ and $K$.
Beating the coarsening baseline means two things at the same reduction ratio and comparable accuracy (within one point). First, our parity gap stays at or below the full-graph gap. Second, the coarsening baseline's gap is significantly higher across seeds.
We also test a second pipeline: reduce, then run CAF, EDITS, or FUGNN on the reduced graph. Success there means matching their full-graph fairness and accuracy at a fraction of the training time.
Two ablations isolate the key ingredient. The first, same-group-only merging, merges only nodes sharing a sensitive attribute and otherwise uses the coarsening objective. The second removes the protected modulator.
Why not just…?
Why not just merge only nodes from the same sensitive group? This is the most serious threat, because it is simple and plausibly fixes much of the problem. Our argument is that it is not enough. Two same-group nodes can sit in very different neighborhoods, for example 90% versus 30% same-group exposure. Merging them averages their exposure and moves both predictions. The same-group-only ablation tests this directly. If it matches our method on $\Delta_{SP}$ at equal reduction ratio, exposure profiles add nothing beyond group labels, and we would report the simpler rule as the result.
Why not just coarsen for accuracy and then run a fair GNN on the result? Fair methods cannot recover information the reduction destroyed. A minority subgroup absorbed into majority super-nodes is no longer visible to CAF's counterfactual pairing or EDITS's group distribution matching. The reduce-then-debias pipeline is run with both coarsening and our reduction. If accuracy-coarsening followed by CAF matches our reduction followed by CAF, the group-safe criterion is unnecessary whenever a debiaser is used downstream. That would narrow our contribution to the no-debiaser setting.
Why not just skip reduction and use a cheap fair method on the full graph? FUGNN already cuts Pokec-z runtime from 3018 to 10 seconds via truncated spectra (FUGNN). For fair node classification alone, full-graph methods may suffice. Our case rests on settings where reduction is used anyway, such as memory-bound training, repeated architecture search, and pipelines reused across models. There, an undocumented bias increase is the harm. We report wall-clock and memory for both routes and will state plainly where reduction is not worth it.
Proposed Experiments
The datasets are German Credit, Credit Defaulter, Bail, Pokec-z, Pokec-n, and NBA, all used by the fair-GNN papers above, with Pokec providing the large-graph setting. Cora and Citeseer serve only as a sanity check that we reproduce the coarsening baseline's accuracy. For degree-based groups we add Chameleon, Squirrel, and EMNLP with the degree fairness gaps from On Generalized Degree Fairness in Graph Neural Networks, treating low- and high-degree nodes as groups. Metrics are accuracy or AUC, $\Delta_{SP}$, $\Delta_{EO}$, exposure distortion per group, reduced-graph size, and wall-clock and peak memory.
There are four decisive checks. First, whether accuracy-oriented coarsening raises $\Delta_{SP}$ above the full-graph value on these benchmarks. If it does not, the motivating claim fails on standard data, and we report that. Second, whether group-conditional exposure distortion correlates with the $\Delta_{SP}$ change across hundreds of reductions much more strongly than node-averaged propagation error does. This is the core mechanistic claim. Third, whether exact rules alone yield nontrivial shrinkage on social graphs like Pokec, and how the $\epsilon$-relaxed reduction trades size against fairness drift relative to our bound. Fourth, whether the full method beats the same-group-only ablation and the coarsening baseline at matched reduction ratio and accuracy. A loss to the same-group ablation would be reported as the finding that group labels, not exposure profiles, are what reduction must respect.
References
- A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation
- Towards Fair Graph Neural Networks via Graph Counterfactual
- On Generalized Degree Fairness in Graph Neural Networks
- Graph Coarsening with Message-Passing Guarantees
- EDITS: Modeling and Mitigating Data Bias for Graph Neural Networks
- Learning Fair Graph Representations via Automated Data Augmentations
- FUGNN: Harmonizing Fairness and Utility in Graph Neural Networks
- A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation
- The Linear Arrangement Problem Parameterized Above Guaranteed Value
- Polynomial Kernelization for Removing Induced Claws and Diamonds