用布尔函数理论分析GNN表达能力，提升公平图挖掘性能
A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Mining
- 基于布尔函数理论构建新表达能力框架，超越传统方法
- 在真实数据上实现多群体交叉公平性差距低于0.15，优于现有方法
- 适用于高复杂度子群体（如奇偶性）的公平图学习，适合公平算法研究者
我们提出一种基于布尔函数理论的新型图神经网络表达能力分析框架，可精细刻画模型捕捉复杂子群体结构的能力。引入子群体布尔同构（SBI）作为不变量，严格涵盖现有表达能力度量，包括Weisfeiler-Lehman、双连通性和同态基框架。理论分析揭示傅里叶阶、电路类（AC⁰、NC¹）和影响度是公平感知GNN表达能力的关键瓶颈。我们设计了一种基于电路遍历的公平算法，可处理由高复杂度布尔函数（如奇偶性）定义的子群体，突破现有基线限制。在真实图数据上的实验表明，该方法在交集群体中实现低公平差距，优于当前最优方法，首次为公平性导向的GNN表达能力提供了系统性理论支持。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。