When a model makes decisions about people in a social network, such as recommending jobs or setting loan terms, two things are hard to deliver at once. The first is a guarantee that no downstream classifier can discriminate by a protected attribute like region or nationality. The second is a node representation whose meaning a human can read. Fair graph learning today mostly trains continuous embeddings with adversarial penalties. Those embeddings are opaque, the fairness is only measured on a test set, and a stronger downstream model can often recover the protected attribute anyway.
We propose to represent each node as a leaf of a shallow decision tree. The tree splits on cheap, human-readable graph descriptors: the node's hop distance to a few hundred landmark nodes ("anchors") and averages of its neighbours' features. It is grown with a splitting rule that rewards predicting the label and penalises separating the protected groups. Because every node lands in one of a small, finite set of cells, three things follow. Each cell is a short rule such as "within two hops of anchor 17, more than four hops from anchor 3, neighbour-average age above 30". The worst-case demographic disparity that any downstream classifier could achieve can be bounded with a confidence interval. And the parameter count does not grow with the number of nodes.
Core Claim
Fairness-certified, rule-readable node representations can be built for graphs by carrying a fairness-penalised splitting criterion from tabular trees over to anchor-distance and neighbour-aggregate descriptors. On the standard fair-graph benchmarks, we expect the accuracy cost relative to fair graph neural networks (GNNs) to be small enough to be worth the certificate.
The graph-specific part of the claim is that structure is where proxy bias lives in social networks. The fair-GNN survey Fairness-Aware Graph Neural Networks: A Survey separates bias that comes from homophilic structure, from features, and from neighbourhood aggregation. A fairness penalty applied only to node features would leave the first and third untouched. Making anchor distances and neighbour aggregates explicit split variables puts structural proxies under the same penalty as feature proxies, and makes them visible in the resulting rules.
Research Program
The method has four parts: descriptors, a splitting rule, a certificate, and an anchor-selection choice.
Descriptors. We pick a set $A$ of anchors, with $|A|$ in the hundreds. We run one breadth-first search from each anchor, which costs $O(|A|(N+E))$ for $N$ nodes and $E$ edges. This gives each node a truncated distance vector to all anchors, following the anchor tokenisation of NodePiece. NodePiece used such tokens with fewer than 10% of nodes as anchors to cut parameters 70x on WikiKG 2, but fed them to an opaque neural encoder. We append one- and two-hop neighbour averages of the raw node features. These are precomputed once, so training never runs message passing and memory is linear in $N$ with a small constant.
Splitting rule. At each candidate split $b$ of node set $T$, the tree scores
$$ \text{score}(T,b) = \Delta G_y(T,b) - \lambda\, \Delta G_s(T,b), $$
where $\Delta G_y$ is the normalised impurity reduction for the task label, $\Delta G_s$ is the impurity reduction for the protected attribute $s$, and $\lambda \ge 0$ trades the two. With $\lambda = 1$ this is the Fair Forests criterion, which reached empirical zero discrimination on German Credit and Heritage Health. Sweeping $\lambda$ connects it to the FairGini objective of FARE, which penalises how well the leaves let one infer the sensitive attribute. We reuse these criteria unchanged. The new element is the variable space they act on.
Certificate. The leaf index $c$ is the representation. For any classifier $h$ that sees only $c$, even a randomised one, the demographic parity gap is at most the total variation distance between the groups' cell distributions:
$$ \max_h \left| P(h=1 \mid s=0) - P(h=1 \mid s=1) \right| = \tfrac12 \sum_{c} \left| P(c \mid s=0) - P(c \mid s=1) \right|. $$
Following FARE, we upper-bound the right-hand side using Clopper–Pearson and Hoeffding intervals estimated on held-out nodes.
The graph-specific subtlety is that nodes are not independent draws. We address it directly. In the transductive setting the graph and tree are fixed once training ends, so the cell assignment is a deterministic function of each node. Held-out nodes are a uniform sample without replacement from a finite population, and Hoeffding's inequality still holds under that sampling. The certificate therefore covers the node population of the given graph. It does not cover new nodes arriving under a changed graph, and we will state that limit rather than hide it. Inductive certification on a held-out subgraph is a secondary experiment, reported as empirical only.
Anchor choice. NodePiece selects anchors by PageRank. In homophilic networks this may place most anchors inside majority-group communities. Minority nodes would then all look "far from everything", so their distance vectors would carry little information and their accuracy would suffer. We compare PageRank anchors with group-stratified anchors, which are PageRank-selected within each protected group in proportion to group size. We treat this as an ablation on accuracy disparity, not as a core claim.
Relation to Prior Work
Three groups of papers play different roles here.
Methods we reuse. Fair Forests, FairParTree (fairness penalties inside clustering-tree splits, with clusters explained by about four conditions) and FARE supply the splitting criteria and the certificate machinery. All three are evaluated only on tabular, independent rows. None defines what a split means on relational data or examines whether neighbourhood structure undermines a feature-level penalty.
Prior work that motivates the gap. FairGNN adds an adversary and covariance constraints to a GNN, and Distraction is All You Need for Fairness replaces the adversary with an internal maximin module. Both reach good empirical parity on Pokec and NBA but offer no guarantee against a stronger downstream model, and their embeddings have no readable axes.
Prior work that constrains the design. The interpretable-embedding line shows the cost of geometric interpretability. HM-LDM gets identifiable community coordinates from a simplex constraint, and node2coords gets them from a Wasserstein barycentre decoder. Both pay pairwise or optimal-transport costs that block scaling. We give up continuous geometry for discrete rules to avoid those costs.
Finally, there is a direct tension in the accuracy evidence. FARE reports an accuracy tax from discretisation. Relational Concept Bottleneck Models and Graph Concept Bottleneck Models report that structured bottlenecks match black boxes, with Graph CBMs reaching 77.95% versus 74.69% on CUB. Which of these holds for fair node classification is an empirical question that our experiments answer.
Baselines
Unconstrained GCN. The naive reference point is a plain graph convolutional network (GCN) with no fairness term. It shows how much bias the benchmarks contain and what accuracy is available. FairGNN reports 70.2% AUC with 9.9% statistical-parity gap (ASP) for GCN on Pokec-z.
FairGCN. The strongest existing method is FairGCN from the same paper, which reports 76.7% AUC with 0.5% ASP on Pokec-z. It is the target we must approach.
Distraction Module. We also run the Distraction Module with a GCN backbone, sweeping its trade-off parameter to trace a Pareto front. The file gives no Pokec number for it, so we will reproduce it ourselves.
Fair comparison. All methods share the same splits as the FairGNN protocol, the same node features, and the same hyperparameter budget. That budget is a fixed number of configurations chosen by validation AUC under an ASP ceiling. We report parity at matched AUC, not cherry-picked points.
What beating them means. Our method beats the fair GNNs if, at matched empirical ASP and ΔEO, its AUC is within two points of FairGCN while also providing a certified disparity bound for all downstream classifiers, which they cannot provide. Matching the empirical numbers without the certificate would be a loss.
Ablation of the key ingredient. The ablation that isolates our contribution grows the same tree on the same descriptors with the fairness penalty applied only to raw-feature splits. Anchor-distance and neighbour-aggregate splits stay unpenalised. If that tree's certificate is as tight as the fully penalised tree's, structural proxies were not the issue and our graph-specific claim fails.
Unpenalised tree. A tree with $\lambda = 0$ on the same descriptors separates the cost of discretisation from the cost of fairness.
Why not just…?
Why not just run FARE on neighbour-propagated features? This is the most serious threat, because it is our method without anchor distances. It would be built from FARE plus simplified-GCN-style feature smoothing and could plausibly perform as well. We run it as a baseline on identical splits. If it matches our accuracy and certificate tightness on Pokec and NBA, we will report that anchor distances add nothing for these tasks. The contribution would then shrink to "FARE transfers to graphs, with a valid transductive certificate". We would also check whether anchor distances still help for nodes with sparse or missing features.
Why not just apply FARE's tree to frozen GNN embeddings? This would likely give a valid certificate and possibly better accuracy, since the embeddings are richer. However, its cells are rules over opaque embedding coordinates, which Explaining Node Embeddings notes lack semantic meaning. It also inherits full-graph GNN memory costs. We run it and report its accuracy honestly. If it wins clearly on accuracy, our method's case rests on readability and scale, and we test readability directly as described below.
Why not just trust FairGNN's empirical parity? FARE's results show that empirically debiased continuous representations give no bound against an arbitrary downstream model. We test this directly by training a gradient-boosted attacker to predict the protected attribute from FairGCN embeddings. We then compare the parity it can induce with our certified bound.
Why not just rewire the graph first? The fair-GNN survey notes that exact neighbourhood balancing by edge editing is NP-hard, because editing one node's neighbourhood unbalances its neighbours'. Edge dropping also degrades sparse graphs. We therefore treat rewiring as orthogonal: it could be applied before our method, and it does not replace it.
Proposed Experiments
The main experiment covers Pokec-z, Pokec-n and NBA, using the FairGNN protocol with region or nationality as the protected attribute. We report accuracy, AUC, ASP, ΔEO, the certified demographic-parity upper bound at 95% confidence, the number of cells, and the average rule length.
Before the graph experiments, we reproduce FARE on German Credit. This confirms the certificate implementation before we trust it on graphs.
First decisive check. We plot the full $\lambda$ sweep as AUC against certified bound. Two curves are included: the "penalty on features only" ablation and FARE-on-propagated-features. The question is whether penalising structural splits tightens the certificate at fixed AUC.
Second decisive check. We compare the gap between certified and empirical disparity with the parity that the boosted attacker extracts from FairGCN embeddings. The certificate is only meaningful if it is tight. FARE reported bounds a few percentage points above empirical unfairness on tabular data, and we test whether graph data keeps that gap.
Third decisive check: anchors. We compare stratified and PageRank anchors on minority-group AUC. The hypothesis is that PageRank anchors widen the accuracy gap between groups.
Scaling. We run the descriptor computation and tree growth on the full Pokec network that Pokec-z and Pokec-n are sampled from. We report wall-clock time and peak memory against a mini-batched FairGCN. Fit time should be roughly linear in the number of edges for a fixed anchor count, since it is dominated by the per-anchor breadth-first searches.
Readability. We extract the top cells that most affect parity. We check whether their rules name structural proxies that FairTreeFIS-style signed importance (Fair Feature Importance Scores) also flags. Agreement between our rules and that independent attribution method is the evidence that the cells are not just readable but correct about where bias comes from.
References
- Fairness-Aware Graph Neural Networks: A Survey
- NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs
- Fair Forests: Regularized Tree Induction to Minimize Model Bias
- FARE: Provably Fair Representation Learning with Practical Certificates
- Balancing Fairness and Interpretability in Clustering with FairParTree
- Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information
- Distraction is All You Need for Fairness
- HM-LDM: A Hybrid-Membership Latent Distance Model
- node2coords: Graph Representation Learning with Wasserstein Barycenters
- Relational Concept Bottleneck Models
- Graph Concept Bottleneck Models
- Explaining Node Embeddings
- Fair Feature Importance Scores for Interpreting Decision Trees