Research map / Graph learning / GNN architectures
Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows theoretically and empirically that GCN link predictors with symmetric normalized filters carry a within-group preferential attachment bias, defines a within-group LP fairness metric, and proposes a fairness regularizer that reduces it.
Problem
GNN link prediction can amplify degree and power imbalances; prior fairness work on LP focuses on dyadic fairness and ignores within-group (intersectional) disparities and rich-get-richer dynamics from degree bias.
Approach
A spectral and first-order Taylor analysis of GCNs shows that symmetric-normalized GCN link scores within a social group are approximately proportional to the geometric mean of the incident nodes' within-group degrees (preferential attachment bias). This is linked to a new within-group LP unfairness metric, which is reduced by adding a regularizer to the training loss.
Key results
- Theoretic LP scores predict Phi_s GCN LP scores with generally low NRMSE and high PCC across 10 datasets (exception: EN).
- Fairness regularizer on DBLP-Fairness with lambda_fair=4.0 reduces mean within-group unfairness from 0.145 to 0.072 for Phi_s, with test AUC dropping from 0.778 to 0.741.
- For Phi_r, theoretic scores were not strong predictors of GCN scores, and the random walk filter showed unfairness empirically despite theory predicting none.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_s · NBA | average within-group unfairness: $0.013 \pm 0.005$ -> $0.000 \pm 0.001$ | Helped |
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_s · NBA | test AUC: $0.752 \pm 0.003$ -> $0.753 \pm 0.002$ | No clear effect |
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_s · DBLP-Fairness | average within-group unfairness: $0.145 \pm 0.020$ -> $0.072 \pm 0.018$ | Helped |
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_s · DBLP-Fairness | test AUC: $0.778 \pm 0.007$ -> $0.741 \pm 0.008$ | Hurt |
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_s · German | average within-group unfairness: $0.045 \pm 0.013$ -> $0.012 \pm 0.006$ | Helped |
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_s · German | test AUC: $0.912 \pm 0.009$ -> $0.876 \pm 0.017$ | Hurt |
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_r · NBA | average within-group unfairness: $0.000 \pm 0.000$ -> $0.000 \pm 0.000$ | No clear effect |
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_r · NBA | test AUC: $0.583 \pm 0.034$ -> $0.585 \pm 0.030$ | No clear effect |
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_r · DBLP-Fairness | average within-group unfairness: $0.090 \pm 0.028$ -> $0.053 \pm 0.015$ | Helped |
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_r · DBLP-Fairness | test AUC: $0.758 \pm 0.011$ -> $0.715 \pm 0.010$ | Hurt |
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_r · German | average within-group unfairness: $0.015 \pm 0.005$ -> $0.029 \pm 0.011$ | Hurt |
| Add fairness regularization (λ_fair=4.0) (ablation) | GCN Φ_r · German | test AUC: $0.883 \pm 0.009$ -> $0.830 \pm 0.024$ | Hurt |
Surprising findings
- The random walk normalized GCN (Phi_r) shows within-group unfairness empirically even though the theory predicts zero degree-induced unfairness for it.
- Phi_s can predict negative LP scores for same-group pairs, contrary to the theoretical non-negativity prediction.
Limitations
- Theory relies on linearization via first-order Taylor expansion and assumptions of independent path activation, with error terms that are only approximately zero.
- Theoretical predictions are weak for the random walk filter, and for high LP scores or low-degree/low-similarity pairs.
- Fairness regularizer requires retraining and is not applicable where model parameters cannot be retrained; only evaluated on GCNs and a few datasets.
Experimental setup
Datasets: Cora CiteSeer DBLP PubMed CS Physics LastFMAsia Twitch-DE Twitch-EN Twitch-FR NBA German credit
Benchmarks: Cora CiteSeer DBLP PubMed CS Physics LastFMAsia Twitch-DE Twitch-EN Twitch-FR NBA German
Metrics: test ROC-AUC NRMSE Pearson correlation coefficient within-group unfairness Delta
Baselines: GCN with random walk normalized filter (Phi_r)
Builds on: GCN PyTorch Geometric link prediction pipeline random walk analysis of GNN expressivity (Xu et al.-style path counting)
Closest papers by meaning
- Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks (NeurIPS 2024 · similarity 0.90)
- Implicit degree bias in the link prediction task (ICML 2025 · similarity 0.88)
- Fair Graph U-Net: A Fair Graph Learning Framework Integrating Group and Individual Awareness (AAAI 2025 · similarity 0.87)
- Chasing Fairness in Graphs: A GNN Architecture Perspective (AAAI 2024 · similarity 0.87)
- FairSIN: Achieving Fairness in Graph Neural Networks through Sensitive Information Neutralization (AAAI 2024 · similarity 0.87)
- FairWire: Fair Graph Generation (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.