mlsanityData to 7 Oct 2026

A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Mining

arXiv 2601.12751 ↗First posted 19 Jan 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We propose a novel expressivity framework for Graph Neural Networks (GNNs) grounded in Boolean function theory, enabling a fine-grained analysis of their ability to capture complex subpopulation structures. We introduce the notion of textitSubpopulation Boolean Isomorphism (SBI) as an invariant that strictly subsumes existing expressivity measures such as Weisfeiler-Lehman (WL), biconnectivity-based, and homomorphism-based frameworks. Our theoretical results identify Fourier degree, circuit class (AC0, NC1), and influence as key barriers to expressivity in fairness-aware GNNs. We design a circuit-traversal-based fairness algorithm capable of handling subpopulations defined by high-complexity Boolean functions, such as parity, which break existing baselines. Experiments on real-world graphs show that our method achieves low fairness gaps across intersectional groups where state-of-the-art methods fail, providing the first principled treatment of GNN expressivity tailored to fairness.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 41 of its 59 references that are in the map. First posted on arXiv 19 Jan 2026.

Builds on

41 of 59 references.

References · 41

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  4. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  6. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  7. 2019Provably Powerful Graph Networkscited by 385
  8. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  9. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  10. 2020Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Informationcited by 168
  11. 2023On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topologycited by 163
  12. 2019On the Universality of Invariant Networkscited by 151
29 more
  1. 2021Towards a Unified Framework for Fair and Stable Graph Representation Learningcited by 128
  2. 2019Compositional Fairness Constraints for Graph Embeddingscited by 126
  3. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  4. 2022A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainabilitycited by 118
  5. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  6. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  7. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  8. 2021EDITS: Modeling and Mitigating Data Bias for Graph Neural Networkscited by 92
  9. 2022Fairness in Graph Mining: A Surveycited by 76
  10. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  11. 2022Improving Fairness in Graph Neural Networks via Mitigating Sensitive Attribute Leakagecited by 61
  12. 2022Ordered Subgraph Aggregation Networkscited by 57
  13. 2020DeBayes: a Bayesian Method for Debiasing Network Embeddingscited by 55
  14. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  15. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 38
  16. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  17. 2022FMP: Toward Fair Graph Message Passing against Topology Biascited by 35
  18. 2021CrossWalk: Fairness-enhanced Node Representation Learningcited by 34
  19. 2021Unbiased Graph Embedding with Biased Graph Observationscited by 28
  20. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  21. 2023Fairness-Aware Graph Neural Networks: A Surveycited by 22
  22. 2022A Survey on Fairness for Machine Learning on Graphscited by 20
  23. 2022FairEGM: Fair Link Prediction and Recommendation via Emulated Graph Modificationcited by 15
  24. 2024On the Expressive Power of Spectral Invariant Graph Neural Networkscited by 15
  25. 2021EqGNN: Equalized Node Opportunity in Graphscited by 7
  26. 2023Fairness-aware Message Passing for Graph Neural Networkscited by 7
  27. 2024FairWire: Fair Graph Generationcited by 6
  28. 2025Homomorphism Expressivity of Spectral Invariant Graph Neural Networkscited by 4
  29. 2020How hard is to distinguish graphs with graph neural networks?cited by 3

Built on by

Not cited yet.