Individual Fairness at the Edge of the Hierarchy

Individual fairness asks that similar people get similar decisions. In practice, every method that enforces or audits it starts by building a similarity graph: who counts as whose neighbor. That graph is almost always built from Euclidean distances, meaning straight-line distances in an ordinary flat feature space. Many populations that fairness work cares about are organized like trees. Occupations nest inside occupation families, social networks contain a few hubs and many thinly connected members, and credit histories branch into ever more specific profiles. Flat space has too little room for the leaves of such trees, so it packs people who sit deep in the hierarchy close to people from unrelated branches. We argue that this geometric crowding produces an individual fairness gap of its own. The individuals at the periphery of the hierarchy, who are often the same low-connectivity, under-represented people that group metrics already overlook, get neighborhoods made of the wrong comparators. Their consistency is checked against people who are not actually similar to them. Average consistency scores hide this, in the same way that group parity hides individual unfairness.

The proposal is to build the similarity graph in hyperbolic space instead. Hyperbolic space is a curved geometry whose volume grows exponentially with distance from the center, so it behaves like a continuous tree and has room for every leaf. We then measure and repair individual fairness as a function of depth in the hierarchy. The concrete deliverables are three. The first is a depth-stratified audit showing where Euclidean neighborhoods go wrong. The second is a hyperbolic version of graph-Laplacian post-processing that also works for individuals arriving after training. The third is a set of experiments built so that a tree-distance oracle, a wider Euclidean embedding, or simple degree reweighting can each falsify the claim that curvature is what matters.

Core Claim

The claim is specific. On data with tree-like structure, Euclidean k-nearest-neighbor similarity graphs have neighborhood contamination that grows with hierarchical depth. Contamination here means the fraction of an individual's graph neighbors that come from a different branch of the true hierarchy. Local individual fairness methods built on such graphs therefore do two harmful things at the periphery. They force consistency between dissimilar people, which over-smooths predictions and costs accuracy. They also fail to force consistency between genuinely similar people. Replacing Euclidean distance with hyperbolic geodesic distance (distance along the shortest path within the curved space) should lower contamination at the periphery. That in turn should raise the worst-depth individual consistency without lowering accuracy. A further prediction makes the claim testable: the size of the effect should track how tree-like a dataset is, and it should vanish on data that is not hierarchical.

This differs from the closest existing work in what it changes and what it measures. Post-processing for Individual Fairness introduced GLIF, which smooths a pretrained model's predictions over a similarity graph through a Laplacian penalty. GLIF supplies our repair mechanism. It treats the graph as given and Euclidean, it is transductive (test points must be in the graph at optimization time), and it reports aggregate consistency. Bridging the Fairness Divide (FairGI) enforces individual fairness within demographic groups using Euclidean graph networks. It motivates our within-group focus but never examines who inside a group is served badly. SenSeI defines fairness as invariance to sensitive perturbations in a flat space and is our strongest in-processing competitor. On the hyperbolic side, Poincaré Embeddings showed that distance from the origin encodes depth and that taxonomies embed with low distortion in very few dimensions. ASIL showed that hyperbolic space separates minority clusters in imbalanced graphs. Neither touches fairness. Despite its name, MAMO-fair uses only the scalar tanh function as a smooth surrogate for group-fairness indicators and involves no curved geometry. It is not prior work on this question.

Research Program

The first part is diagnostic and can be run with no new method. For each dataset we fix a reference hierarchy. In Bias in Bios this is the Bureau of Labor Statistics occupation classification that Bias in Bios already maps its 28 occupations onto, which gives major-group, minor-group, and occupation levels. For the graph datasets (NBA, Credit, Pokec_n) no taxonomy is given, so we use a hierarchy extracted from the graph itself by recursive community detection. We report the dataset's Gromov δ-hyperbolicity, a standard number that measures how close a metric space is to a tree. We then build Euclidean and hyperbolic kNN graphs at matched k and compute, for each individual, contamination and local consistency. Both are binned by depth, measured by hyperbolic radius or by tree level. The diagnostic result is a curve: contamination against depth for each geometry, stratified by protected group. If the Euclidean curve is flat, the proposal is wrong and we stop.

The second part is the repair. Individuals are embedded in the Poincaré ball, the open unit ball equipped with hyperbolic distance

$$d_{\mathbb{H}}(u,v)=\operatorname{arcosh}\!\left(1+\frac{2\|u-v\|^2}{(1-\|u\|^2)(1-\|v\|^2)}\right),$$

where $u,v$ are embedding vectors of norm below one. The embedding comes from a hyperbolic graph convolutional encoder (Hyperbolic Graph Convolutional Neural Networks) for graph data, or from a hyperbolic projection of a text encoder for Bios. We connect each person to their k nearest neighbors under $d_{\mathbb{H}}$, restricted to their own protected group in the FairGI sense. The edges get weights $W_{ij}=\exp(-d_{\mathbb{H}}(z_i,z_j)^2/\sigma^2)$, where $z_i$ is person $i$'s embedding and $\sigma$ is a bandwidth. Predictions are then post-processed as in GLIF:

$$\min_{y}\ \|y-\hat y\|^2+\lambda\, y^\top L y,$$

where $\hat y$ are the base model's scores, $L$ is the graph Laplacian of $W$, and $\lambda$ sets the smoothing strength. To remove GLIF's transductive limitation, a newly arriving individual is embedded by the frozen encoder and gets the one-point closed-form update $y_{\text{new}}=(\hat y_{\text{new}}+\lambda\sum_j W_{\text{new},j}y_j)/(1+\lambda\sum_j W_{\text{new},j})$ against already-smoothed neighbors. We will also test an optional variant motivated by the norm-as-depth property. Here edges are allowed only between individuals whose radii differ by less than a tolerance, so that smoothing never equates people at legitimately different levels of the hierarchy. Whether this helps beyond plain geodesic kNN is an empirical question. We include it as a variant, not as a central claim.

Implementation uses the Lorentz model internally, a second coordinate system for hyperbolic space that sidesteps the numerical blow-up near the ball's boundary. We convert to Poincaré coordinates only for distances. Baseline graph networks come from the twenty implementations in CMGNN.

Baselines

The naive reference point is the unconstrained base predictor with no fairness intervention. On Toxicity, SenSeI reports a prediction consistency of 0.621 for this baseline, and GLIF reports roughly 61%. Every method is reported against it on the same splits.

The strongest post-processing competitor is Euclidean GLIF, together with its normalized random-walk variant GLIF-NRW, which was designed specifically to keep dense regions from overpowering sparse ones. On Toxicity, GLIF reports raising prediction consistency from about 61% to over 84%. We run both variants on the same base predictors with the same k, the same λ grid, and the same validation budget, changing only the geometry of the embedding that defines neighbors. Beating GLIF means one of two things on the hierarchical datasets: higher worst-depth-decile consistency at equal or better balanced accuracy, or equal worst-decile consistency at higher accuracy. Matching GLIF in aggregate consistency is not enough on its own.

The strongest in-processing competitor on graphs is FairGI. On Credit it reports an individual fairness score of 1.84 against 13.84 for FairGNN. On NBA it reports a statistical parity gap of 0.43 against 1.19 for FairGNN, with accuracy within 1 to 2% of unconstrained models. We rerun FairGI with its released settings and give our hyperbolic encoder the same hidden size and tuning budget. Beating it means matching its Credit IF score and NBA parity gap while improving consistency in the lowest-degree and deepest decile of each protected group. No isolated scalar was found on Lacuna for FairGI on Pokec_n, so there we compare only against our own rerun. For text, SenSeI is the in-processing reference. Its reported Toxicity consistency is 0.773, with SenSR at 0.729 and CLP at 0.763. On Bios it reports the lowest Gap RMS without a scalar value, so no reported result was found on Lacuna for SenSeI's Bios numbers, and we rerun it.

Three ablations isolate the key ingredient. In the first, the same hyperbolic encoder is followed by Euclidean distances computed on its log-mapped tangent vectors, which separates "better encoder" from "curved distance". In the second, a Euclidean encoder is widened until its distortion on the reference hierarchy matches the low-dimensional hyperbolic one. The third is the tree-distance oracle, where neighbors are defined directly by the known hierarchy. We run the oracle only on Bios, because only Bios has a given taxonomy.

Why not just…?

Why not just use the known hierarchy's tree distance as the fairness metric? When a full taxonomy with each individual's position is available, this is a real threat, and it may match or beat our method. That is why we include it as an oracle on Bios. The tree only places people into 28 occupation leaves, though. It says nothing about similarity within a leaf, and it cannot place an individual whose position is unknown. On graph data no taxonomy exists at all. The decisive comparison is the gap between oracle and hyperbolic consistency at deep levels. If hyperbolic graphs recover most of the oracle's gain without access to the tree, the method earns its place. If not, the contribution shrinks to inductive deployment. We would report that honestly.

Why not just raise the Euclidean dimension? Polynomial volume growth means more dimensions delay crowding but do not remove it, and Poincaré Embeddings showed that hyperbolic space reaches low distortion in two or three dimensions. This argument concerns distortion, however, not fairness. Our distortion-matched wide Euclidean ablation settles the question directly. If a 512-dimensional Euclidean graph matches hyperbolic contamination and worst-depth consistency, curvature is not the cause, and we would recommend the simpler fix.

Why not just reweight peripheral nodes, as GLIF-NRW does? Reweighting changes how much each edge counts. It cannot change which people are connected. Our diagnosis is that peripheral individuals have the wrong neighbors, and no reweighting repairs a contaminated edge. GLIF-NRW is run as a baseline. If it closes the worst-depth gap as well as hyperbolic graphs do, the diagnosis is wrong. The contamination measurements in the first part tell us in advance which explanation to expect.

Why not just use a hyperbolic graph network and skip the fairness step? Sagun shows that Euclidean graph networks amplify disparity for poorly connected nodes within a group, and ASIL suggests curvature helps minority clusters. It is plausible that geometry alone already narrows the gap. We report the hyperbolic encoder without smoothing as its own row, so the size of the gain from geometry alone is visible and separable from the gain from local fairness smoothing.

Proposed Experiments

We use NBA, Credit, and Pokec_n for graph node classification, Bias in Bios for occupation prediction under pronoun swaps, and the Toxicity benchmark as a negative control, since identity-term perturbations there are not hierarchical. We also add Adult as a second tabular check. The metrics are standard ones: prediction consistency, the FairGI IF score, statistical parity gap, and balanced accuracy. Each is also reported per depth decile and per degree decile within each protected group, with the worst decile as the headline number.

Evaluation must avoid circularity. A method that builds hyperbolic graphs should not be judged by hyperbolic-graph consistency. Fairness is therefore measured against geometry-neutral comparators. On Bios and Toxicity these are ground-truth counterfactual pairs from pronoun and identity swaps. On Bios we also use tree-defined same-leaf pairs. On graphs we use held-out pairs whose similarity is defined from raw node attributes by a metric fixed before any embedding is trained.

Three checks decide the outcome. First, on Bios and the graph datasets, Euclidean contamination must rise with depth while hyperbolic contamination stays flatter. Second, the hyperbolic method's improvement in worst-decile consistency over GLIF-NRW must be positive, and it should grow with each dataset's tree-likeness, measured as low δ-hyperbolicity. Third, on Toxicity the two geometries should perform about the same. If the third check fails, with hyperbolic graphs helping even on non-hierarchical data, the gain is coming from something other than curvature, and we would have to explain it before claiming anything. Finally, the inductive update is tested by holding out 20% of nodes or documents at training time. It should keep the worst-decile gains within a small margin of the transductive solution, at a cost close to GLIF's reported sub-0.1-second runtime.