Research map / Graph learning / Graph self-supervised learning
FairGP: A Scalable and Fair Graph Transformer Using Graph Partitioning
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.
Proposes FairGP, a scalable fairness-aware graph transformer that partitions the graph with METIS and zeroes inter-cluster attention, plus structural eigenvector features, to reduce sensitive-feature bias in node classification.
Problem
Graph Transformers show fairness issues against sensitive-feature subgroups and are memory-intensive on large graphs, so scalable and fair GT training is needed.
Approach
Graph partitioning reduces the influence of higher-order nodes' sensitive features on lower-order nodes; FairGP combines METIS partitioning, zeroing of inter-cluster attention, and eigenvector structure features, supported by a theoretical bound linking sensitive-feature similarity to attention between nodes with different sensitive features.
Key results
- On Pokec-z-R, FairGP reaches 68.50% ACC with Delta_SP 0.33% and Delta_EO 0.27%, versus 0.53% and 0.59% for the best baseline (FUGNN and FairSIN, respectively).
- On AMiner-L, FairGP achieves Delta_SP 4.44% and Delta_EO 2.97%, while FairGT and FairSIN run out of memory.
- Runtime on Pokec-z for 100 epochs is 6.88 s for FairGP versus 138.73 s for DIFFormer and 15.66 s for CoBFormer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use graph partitioning instead of vanilla GT | GT · Six datasets in Appendix A.1 | ΔSP and ΔEO | Mixed |
| Add structural features to the feature matrix (w/o FM → FairGP) (ablation) | FairGP · Pokec-z-R, Pokec-z-G, AMiner-L | ΔSP (%): 1.07 -> 0.33; 3.14 -> 1.18; 5.05 -> 4.44 | Helped |
| Add structural features to the feature matrix (w/o FM → FairGP) (ablation) | FairGP · Pokec-z-R, Pokec-z-G, AMiner-L | ΔEO (%): 0.65 -> 0.27; 2.47 -> 0.40; 3.18 -> 2.97 | Helped |
| Add graph partitioning (w/o GP → FairGP) (ablation) | FairGP · Pokec-z-R, Pokec-z-G, AMiner-L | ΔSP (%): 2.14 -> 0.33; 5.84 -> 1.18; 5.95 -> 4.44 | Helped |
| Add graph partitioning (w/o GP → FairGP) (ablation) | FairGP · Pokec-z-R, Pokec-z-G, AMiner-L | ΔEO (%): 5.44 -> 0.27; 4.99 -> 0.40; 3.32 -> 2.97 | Helped |
| Add attention optimization (w/o AO → FairGP) (ablation) | FairGP · Pokec-z-R, Pokec-z-G, AMiner-L | ΔSP (%): 2.44 -> 0.33; 2.37 -> 1.18; 5.06 -> 4.44 | Helped |
| Add attention optimization (w/o AO → FairGP) (ablation) | FairGP · Pokec-z-R, Pokec-z-G, AMiner-L | ΔEO (%): 1.19 -> 0.27; 1.85 -> 0.40; 4.29 -> 2.97 | Helped |
| Add structural features to the feature matrix (w/o FM → FairGP) (ablation) | FairGP · Pokec-z-R, Pokec-z-G, AMiner-L | ACC (%): 68.16 -> 68.50; 66.21 -> 66.82; 91.03 -> 91.35 | Helped |
| Add graph partitioning (w/o GP → FairGP) (ablation) | FairGP · Pokec-z-R, Pokec-z-G, AMiner-L | ACC (%): 66.45 -> 68.50; 64.83 -> 66.82; 89.47 -> 91.35 | Helped |
| Add attention optimization (w/o AO → FairGP) (ablation) | FairGP · Pokec-z-R, Pokec-z-G, AMiner-L | ACC (%): 68.20 -> 68.50; 66.52 -> 66.82; 90.47 -> 91.35 | Helped |
| Partition graphs into clusters | FairGP versus GT baselines · Pokec-z, Pokec-n, AMiner-L | runtime (s): 138.73 -> 6.88; 124.43 -> 6.14; 66.84 -> 32.77 | Helped |
Surprising findings
- Graph partitioning alone (w/o AO comparisons aside) improves fairness of vanilla GT, even over mini-batch training, which the authors interpret as evidence that partitioning itself reduces higher-order node bias.
- FairGP's AUC on Credit (60.05%) is lower than several baselines, showing a fairness-utility trade-off on that dataset.
Limitations
- Relies on access to the entire graph for partitioning, making it less suitable for privacy-sensitive settings.
- Only works when sensitive features are available for all nodes; limited to settings with sufficient sensitive features.
- Fairness-utility trade-off: AUC is not consistently best (e.g., Credit AUC 60.05%).
Experimental setup
Datasets: Credit Pokec-z Pokec-n AMiner-L
Benchmarks: Credit Pokec-z-R Pokec-z-G Pokec-n-R Pokec-n-G AMiner-L
Metrics: ACC AUC statistical parity (Delta_SP) equal opportunity (Delta_EO) runtime
Baselines: GCN GAT APPNP FairGNN FairSIN FMP FUGNN DIFFormer SGFormer Polynormer CoBFormer FairGT
Builds on: FairGT METIS FairGNN FMP
Closest papers by meaning
- Chasing Fairness in Graphs: A GNN Architecture Perspective (AAAI 2024 · similarity 0.90)
- Fair Graph U-Net: A Fair Graph Learning Framework Integrating Group and Individual Awareness (AAAI 2025 · similarity 0.88)
- FDGen: A Fairness-Aware Graph Generation Model (ICML 2025 · similarity 0.88)
- FairSIN: Achieving Fairness in Graph Neural Networks through Sensitive Information Neutralization (AAAI 2024 · similarity 0.88)
- Fairness-Aware Estimation of Graphical Models (NeurIPS 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.