A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Mining
This addresses fairness in graph mining by providing a principled expressivity framework for GNNs, though it is incremental in extending existing theoretical measures.
The paper tackles the problem of analyzing Graph Neural Networks' (GNNs) expressivity for capturing complex subpopulation structures, proposing a Boolean function-theoretic framework that introduces Subpopulation Boolean Isomorphism (SBI) and achieves low fairness gaps in experiments on real-world graphs where state-of-the-art methods fail.
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 \textit{Subpopulation 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 (AC$^0$, NC$^1$), 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.