Source-linked AI summary
Structural Bias Beyond Homophily: A Study of Fairness in Link Prediction
Lilian Marey, Mathilde Perez, Tiphaine Viard, Charlotte Laclau
TL;DR
Fairness in link prediction is difficult to evaluate because structural bias in social graphs is often treated as homophily alone. The paper formalizes broader bias measures and uses controlled graph generation to show that topology strongly determines fairness outcomes, including for fairness-aware methods when homophily is held constant. It concludes that fair graph learning requires structurally grounded evaluation.
Problem
Structural bias in graphs is commonly analyzed through homophily alone, leaving the broader relationship between topology and fairness in link prediction insufficiently examined.
Method
The paper formalizes topological and flow-based bias measures and combines them with a controlled graph-generation process for exploring diverse structural configurations in link prediction.
Results
Fairness outcomes are strongly determined by graph topology, while heterogeneity, information unfairness, and power law exponent ratio independently and significantly affect classical and fairness-aware methods even at fixed homophily.
Takeaways & Limitations
Fairness evaluations of link prediction should account for structural biases beyond homophily.
Takeaways & Limitations
The generative process is limited to binary sensitive attributes and undirected graphs, and a fully formal causal treatment requires additional assumptions and methodology.
Abstract
from arXiv · showhide
Graph link prediction (LP) plays a critical role in socially impactful applications such as job recommendation and friendship formation, making fairness a critical concern in this task. While many fairness-aware methods manipulate graph structures to mitigate prediction disparities, the topological biases inherent to social graphs remain poorly understood and are consistently conflated with homophily alone. In this work, we study the relationship between structural biases and fairness outcomes in LP. To this end, we formalize a taxonomy of topological bias measures and introduce a graph generation method producing a diverse corpus of synthetic graphs with controlled structural properties. Using this corpus, we show empirically that fairness outcomes are strongly correlated with graph topology, and that current fairness-aware methods remain sensitive to structural biases beyond homophily. These findings highlight the need for structurally grounded evaluations in fair graph learning.
1 Introduction
The paper broadens fairness analysis in link prediction beyond homophily by formalizing structural biases and generating graphs with controlled topology. Experiments show that fairness-aware methods remain sensitive to these broader biases.
- The study examines how structural biases beyond homophily relate to fairness outcomes in link prediction.
- The controlled framework enables systematic exploration of structural configurations rather than relying only on correlational analyses.
- It formalizes topological and flow-based structural bias measures beyond homophily.
- A parametrizable generation process creates synthetic graphs with diverse, controlled structural biases across common link prediction settings.
- Fairness outcomes are strongly determined by graph topology, and fairness-aware methods remain sensitive to structural biases beyond homophily, even when homophily is fixed.
2 Related Works
Prior work addresses fairness and graph generation through several structural mechanisms, but commonly treats structural bias primarily through homophily. This paper instead combines broader bias measures with controlled graph generation to assess their specific contributions to fairness outcomes.
- Fairness interventions modify adjacency matrices, random-walk transitions, or GNN aggregation mechanisms, often reweighting edges using sensitive attributes.
- Classical graph generators reproduce properties such as communities and degree distributions but generally lack fairness-oriented control over structural parameters.
- Learning-based generators offer controllable community structures and attribute distributions, but their parameters are less interpretable for controlled structural intervention.
- Evaluation using few real-world datasets limits assessment across diverse structural configurations.
- The paper combines a broader structural-bias taxonomy with generative control to move beyond homophily-focused, correlational evaluation.
3 Structural Biases and Fairness in Link Prediction
The paper formalizes structural bias beyond homophily and develops a controlled graph-generation framework for studying its relationship with fairness in link prediction. This framework supports systematic variation of topology and shows why fairness analysis must consider multiple structural dimensions.
- Structural-bias taxonomy: The taxonomy separates node-level from group-level measures and topological from flow-based properties.It integrates classical graph metrics with fairness-oriented measures.
- Structural-bias taxonomy: Node-level measures capture structural prominence and neighborhood composition, including centrality, k-hop connectivity, density, and heterogeneity.These measures represent distinct dimensions of structural disadvantage across sensitive groups.
- Structural-bias taxonomy: The framework defines normalized differences in expected node-level measures across sensitive groups, where positive values indicate non-sensitive advantage and zero denotes parity.This provides a unified bias quantity for comparing structural measures.
- Structural-bias taxonomy: Group-level measures include assortativity, average mixed distance, power law exponent ratio, and flow-based information unfairness.Together they characterize within-group connectivity, cross-group proximity, degree-distribution concentration, and information-flow disparities.
- Controlled graph generation: The extended Barabási–Albert generator controls group imbalance, homophily, community attachment, and degree variability through modular parameters.α independently sets the fraction of non-sensitive nodes; β adjusts same-attribute attachment; ego-network attachment models community-driven growth; γ controls connectivity variance.
- Controlled graph generation: For fixed α and graph order n, expected assortativity increases monotonically with β, enabling direct intervention on assortativity while holding group imbalance fixed.The construction therefore supports controlled comparisons of structural bias and fairness outcomes.
4 Results
Across the experiments, fairness outcomes depend strongly on graph topology, and fairness-aware methods remain sensitive to structural biases beyond homophily. The results also show that topology can affect fairness much more than predictive performance.
- 4.1 Corpus Validation: Coverage of the Structural Bias Space: The synthetic corpus spans diverse structural configurations, with dispersed graphs and no principal axis dominated by a single bias measure.This validates coverage of the structural bias space across use cases.
- R2 Assort. %R2: R2 values consistently exceed 0.90 when predicting classical LP fairness outcomes from structural bias measures across use cases and models.Assortativity alone accounts for a substantial share of the explained variance.
- R2 Assort. %R2: Equal Opportunity regressions produce systematically lower R2 values than Statistical Parity regressions, reflecting more complex edge-conditioned structural dependencies.EO depends on the existence of edges, whereas SP is not conditioned in the same way.
- R2 Assort. %R2: Assortativity dominates feature importance in Opinion, whereas heterogeneity becomes more important in Friendship, showing that influential structural biases vary by use case.Some regressions distribute importance across multiple bias measures rather than one dominant feature.
- 4.3 Testing H2: Fairness-Aware LP Methods Under Structural Bias: Fairness outcomes vary more than performance outcomes across synthetic graphs, so small topological changes can produce very different fairness results despite limited accuracy effects.This pattern is observed across fair models and use cases in the evaluated corpus.
- 4.3 Testing H2: Fairness-Aware LP Methods Under Structural Bias: Fairness-aware methods are most effective when their interventions address the graph’s actual bias source, and non-assortativity biases remain significant when assortativity is fixed.The results support H2 and reject H3: homophily alone does not characterize the structural conditions governing fairness.
5 Conclusion
The study finds that fairness outcomes in link prediction are strongly determined by graph topology, including structural biases beyond homophily, while current methods lack robustness to these biases. It contributes a diagnostic framework and calls for structurally grounded evaluation, while acknowledging limits in graph scope and causal interpretation.
- Fairness outcomes are strongly determined by graph topology across use cases and models, even when homophily is held constant.Heterogeneity, information unfairness, and power law exponent ratio have independent statistically significant effects.
- The generative process is limited to binary sensitive attributes and undirected graphs, and formal causal treatment requires additional assumptions and methodology.
- Future work could extend the framework to intersectional bias and use structurally diverse graphs to design more robust fairness-aware methods.
- The taxonomy and modular graph-generation framework provide tools for diagnosing structural conditions under which fairness interventions succeed or fail.The work studies controlled structural variations across more than one thousand graphs per use case validated against real-world networks.
- None of the evaluated fairness-aware approaches achieves robustness to structural biases beyond homophily.
- The findings motivate more careful fairness evaluation in consequential applications such as job recommendation and friendship suggestion.Overlooking structural bias may produce fairness guarantees that do not generalize across diverse network topologies.
Computing Infrastructure
This section specifies graph-bias notation and node- and group-level measures, including centrality, connectivity, effective resistance, edge composition, and information flow.
- The study considers undirected graphs with binary sensitive attributes, assigning nodes to non-sensitive and sensitive groups.
- Node-based bias measures take a node as input and include centrality, shortest-path, neighborhood, density, and effective-resistance quantities.
- Effective resistance uses the graph Laplacian pseudoinverse to quantify pairwise resistance and derive node strength measures.
- Group-level measures characterize edge mixing, power-law degree exponents, and random-walk information flow between sensitive groups.
B.1 Proof of Proposition 1
The proof establishes that increasing the homophily parameter increases intra-group edge formation and expected assortativity, including when the anchor mechanism is active. The appendix also describes datasets and their structural contexts.
- B.1 Proof of Proposition 1: The probability of forming an intra-group edge at each growth step is strictly increasing in the homophily parameter β.The proof derives this monotonicity from same-group and different-group attachment probabilities.
- B.1 Proof of Proposition 1: The expected global proportion of intra-group edges is strictly increasing in β because it is a weighted average of stepwise intra-group probabilities.
- B.1 Proof of Proposition 1: Assortativity is strictly increasing in the intra-group edge proportion, yielding an expected assortativity that is strictly increasing in β.This conclusion follows by combining the monotonicity results from the three proof steps.
- B.1 Proof of Proposition 1: When anchor nodes are active, homophilic bias operates through anchor selection while preserving monotonicity in β.
- B.2 Dataset Description: The three use cases are opinion-blog recommendations, friendship networks, and scientific-collaboration recommendations with political affiliation or gender as sensitive attributes.
B.3 Additional results
Additional results show that β provides directional control over assortativity and that fitted synthetic graphs reproduce key structural properties of real-world graphs.
- Assortativity curves increase monotonically with β for balanced groups across all three use cases, then reach a saturation plateau.The curves confirm β’s intended directional control while reflecting structural differences among graph variants.
- Fitted synthetic graphs closely match real-world assortativity and reproduce degree-related measures such as average degree and density.Node counts and class imbalance are exactly replicated by construction.
C Structural Bias Heatmaps
Structural bias measures respond differently to class imbalance and homophily, and their profiles vary across use cases. Correlations among measures also vary by scenario, although degree and constraint remain consistently related.
- Structural bias evolution: Structural biases show distinct sensitivities: assortativity responds more to homophily β, whereas heterogeneity responds more to class imbalance α.Betweenness also varies substantially across use cases, indicating diverse topological profiles.
- Structural bias measures: The heatmaps cover closeness, betweenness, prestige, degree, constraint, density, heterogeneity, isolation, diameter, control, assortativity, average mixed distance, power exponent, and information unfairness across three use cases.Opinion, Friendship, and Collab. are shown in the left, middle, and right panels, respectively.
- Bias correlations: Bias-measure correlations differ across scenarios, with assortativity changing sign in its relationship with control.Only significant correlations with p-value < 0.01 are displayed in the correlation matrices.
- Bias correlations: Degree and constraint remain consistently correlated because both quantify node connectivity at different scales.This recurring relationship indicates that some structural properties are shared across the scenarios.
D Predictive Metrics Heatmaps
Predictive performance and fairness outcomes are examined across use cases, models, class imbalance, and homophily. Performance generally increases with homophily, while unfairness grows with both homophily and sensitive class imbalance.
- Predictive metric trends: Performance generally increases with homophily, whereas unfairness increases with both homophily β and sensitive class imbalance α.These parameters are identified as primary factors driving predictive disparities.
- Predictive metric trends: Models demonstrate strong performance across the evaluated settings, supporting the relevance of the fairness-metric results.The source characterizes this as an overall observation across the models involved.
- Structural-bias regressions: Feature-importance analyses compare structural-bias contributions to SP and EO for GCN, N2V, and SVD models across the three use cases.The figures separate the SP and EO regressions for each model family.
G Additional results for H3
Additional analyses examine partial correlations, assortativity control through the generation parameter β, principal components of structural biases, and outcome distributions across the synthetic corpus.
- Additional H3 analyses: Partial Spearman correlations relate the top-three structural biases to fairness and performance outcomes across models and use cases.Marker opacity encodes statistical significance at p < 0.05.
- Additional H3 analyses: Varying β changes assortativity across the three graph-generation processes while α is fixed at 0.5.Standard-deviation error bands are computed from 100 different seeds.
- Additional H3 analyses: Principal-component analysis summarizes the first two component loadings of structural bias measures over the generated corpus.The loadings are reported in Table 3.
- Additional H3 analyses: The synthetic graph corpus distributions report fairness and performance outcomes for each fair link-prediction model and use case.Each point is the mean over all synthetic graphs, with error bars showing ± standard deviation.
- Additional H3 analyses: Additional partial Spearman analyses assess relationships between structural biases and fairness or performance metrics across models and use cases.Figures 32 and 33 encode statistical significance through marker opacity at p < 0.05.