mlsanityData to 7 Oct 2026

Estimating Fair Graphs from Graph-Stationary Data

arXiv 2510.07536 ↗First posted 8 Oct 2025cs.LG eess.SPcited by 0

Not on the map. Why?

Abstract (arXiv)

We estimate fair graphs from graph-stationary nodal observations such that connections are not biased with respect to sensitive attributes. Edges in real-world graphs often exhibit preferences for connecting certain pairs of groups. Biased connections can not only exacerbate but even induce unfair treatment for downstream graph-based tasks. We therefore consider group and individual fairness for graphs corresponding to group- and node-level definitions, respectively. To evaluate the fairness of a given graph, we provide multiple bias metrics, including novel measurements in the spectral domain. Furthermore, we propose Fair Spectral Templates (FairSpecTemp), an optimization-based method with two variants for estimating fair graphs from stationary graph signals, a general model for graph data subsuming many existing ones. One variant of FairSpecTemp exploits commutativity properties of graph stationarity while directly constraining bias, while the other implicitly encourages fair estimates by restricting bias in the graph spectrum and is thus more flexible. Our methods enjoy high probability performance bounds, yielding a conditional tradeoff between fairness and accuracy. In particular, our analysis reveals that accuracy need not be sacrificed to recover fair graphs. We evaluate FairSpecTemp on synthetic and real-world data sets to illustrate its effectiveness and highlight the advantages of both variants of FairSpecTemp.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 80 of its 136 references that are in the map. First posted on arXiv 8 Oct 2025.

Builds on

80 of 136 references.

References · 80

  1. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  2. 2016Equality of Opportunity in Supervised Learningcited by 2,000
  3. 2014Certifying and removing disparate impactcited by 715
  4. 2016Fair prediction with disparate impact: A study of bias in recidivism prediction instrumentscited by 671
  5. 2017Graph Signal Processing: Overview, Challenges and Applicationscited by 409
  6. 2020Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Informationcited by 168
  7. 2016How to learn a graph from smooth signalscited by 146
  8. 2021Towards a Unified Framework for Fair and Stable Graph Representation Learningcited by 128
  9. 2019Fairness in Recommendation Ranking through Pairwise Comparisonscited by 127
  10. 2019Compositional Fairness Constraints for Graph Embeddingscited by 126
  11. 2018Learning graphs from data: A signal representation perspectivecited by 119
  12. 2018Connecting the Dots: Identifying Network Structure via Graph Signal Processingcited by 111
38 more
  1. 2018Convolutional Neural Network Architectures for Signals Supported on Graphscited by 94
  2. 2021EDITS: Modeling and Mitigating Data Bias for Graph Neural Networkscited by 92
  3. 2022Fairness in Graph Mining: A Surveycited by 76
  4. 2020Fairness-Aware Explainable Recommendation over Knowledge Graphscited by 74
  5. 2021Subgroup Generalization and Fairness of Graph Neural Networkscited by 69
  6. 2019Operationalizing Individual Fairness with Pairwise Fair Representationscited by 64
  7. 2016Network Topology Inference from Spectral Templatescited by 58
  8. 2022Learning Fair Node Representations with Graph Counterfactual Fairnesscited by 58
  9. 2020DeBayes: a Bayesian Method for Debiasing Network Embeddingscited by 55
  10. 2016Learning heat diffusion graphscited by 39
  11. 2016Stationary Graph Processes and Spectral Estimationcited by 35
  12. 2022FMP: Toward Fair Graph Message Passing against Topology Biascited by 35
  13. 2021CrossWalk: Fairness-enhanced Node Representation Learningcited by 34
  14. 2024FairGT: A Fairness-aware Graph Transformercited by 29
  15. 2016Stationary signal processing on graphscited by 28
  16. 2023On Generalized Degree Fairness in Graph Neural Networkscited by 28
  17. 2022Fair Node Representation Learning via Adaptive Data Augmentationcited by 27
  18. 2021Learning Graphs from Smooth and Graph-Stationary Signals with Hidden Variablescited by 20
  19. 2022Fairness Amidst Non-IID Graph Data: A Literature Reviewcited by 20
  20. 2020Exploring Algorithmic Fairness in Robust Graph Covering Problemscited by 19
  21. 2020Online Topology Inference from Streaming Stationary Graph Signals with Partial Connectivity Informationcited by 19
  22. 2020Joint Inference of Multiple Graphs from Matrix Polynomialscited by 19
  23. 2022Interpreting Unfairness in Graph Neural Networks via Training Node Attributioncited by 18
  24. 2021The KL-Divergence between a Graph Model and its Fair I-Projection as a Fairness Regularizercited by 17
  25. 2023Toward Degree Bias in Embedding-Based Knowledge Graph Completioncited by 17
  26. 2021Accelerated Graph Learning from Smooth Signalscited by 16
  27. 2022FairEGM: Fair Link Prediction and Recommendation via Emulated Graph Modificationcited by 15
  28. 2022On Structural Explanation of Bias in Graph Neural Networkscited by 15
  29. 2020Learning Undirected Graphs in Financial Marketscited by 13
  30. 2021A Graph-based Approach for Mitigating Multi-sided Exposure Bias in Recommender Systemscited by 13
  31. 2023Joint Network Topology Inference in the Presence of Hidden Nodescited by 13
  32. 2023FairGen: Towards Fair Graph Generationcited by 12
  33. 2022Enhanced graph-learning schemes driven by similar distributions of motifscited by 11
  34. 2023BeMap: Balanced Message Passing for Fair Graph Neural Networkcited by 11
  35. 2024FUGNN: Harmonizing Fairness and Utility in Graph Neural Networkscited by 11
  36. 2024FairGP: A Scalable and Fair Graph Transformer Using Graph Partitioningcited by 11
  37. 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
  38. 2022Graph Learning with Localized Neighborhood Fairnesscited by 10

50 most cited of 80 All 80 (JSON)

Built on by

Not cited yet.