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

📄 arXiv: 2601.12751v1 📥 PDF

作者: Manjish Pal

分类: cs.LG

发布日期: 2026-01-19

💡 一句话要点

提出基于布尔函数理论的GNN表达性框架，应用于公平图挖掘。

🎯 匹配领域: 支柱五：交互与反应 (Interaction & Reaction)

关键词: 图神经网络 表达性 公平性 布尔函数 子群体 图挖掘

📋 核心要点

  1. 现有GNN表达性度量方法（如WL测试）无法充分捕捉复杂子群体结构，限制了其在公平图挖掘中的应用。
  2. 论文提出基于布尔函数理论的子群体布尔同构(SBI)概念，作为更严格的GNN表达性度量标准。
  3. 设计了基于电路遍历的公平算法，能有效处理由高复杂度布尔函数定义的子群体，并在真实图数据上验证了其有效性。

📝 摘要（中文）

本文提出了一种基于布尔函数理论的图神经网络(GNN)表达性新框架，能够细粒度地分析GNN捕获复杂子群体结构的能力。我们引入了“子群体布尔同构”(SBI)的概念，作为一种严格包含现有表达性度量(如Weisfeiler-Lehman (WL)、基于双连通性和基于同态的框架)的不变量。我们的理论结果确定了傅里叶度、电路类(AC$^0$, NC$^1$)和影响作为公平感知GNN表达性的关键障碍。我们设计了一种基于电路遍历的公平算法，能够处理由高复杂度布尔函数(如奇偶校验)定义的子群体，这些子群体会打破现有的基线。在真实世界图上的实验表明，我们的方法在最先进的方法失败的交叉群体中实现了较低的公平性差距，为针对公平性的GNN表达性提供了第一个原则性处理。

🔬 方法详解

问题定义：现有GNN在处理公平图挖掘任务时，难以有效识别和处理由复杂布尔函数定义的子群体，导致公平性差距。现有表达性度量方法，如WL测试，无法充分捕捉这些复杂子群体结构，成为GNN公平性的瓶颈。

核心思路：论文的核心思路是将GNN的表达能力与布尔函数理论联系起来，通过分析GNN能够表示的布尔函数的复杂性，来评估其捕捉子群体结构的能力。引入子群体布尔同构(SBI)作为一种更强的表达性度量，并以此为基础设计公平算法。

技术框架：该框架包含以下几个主要部分：1) 定义子群体布尔同构(SBI)的概念，作为GNN表达性的度量标准。2) 分析GNN能够表示的布尔函数的复杂性，例如傅里叶度、电路类等。3) 设计基于电路遍历的公平算法，用于处理由高复杂度布尔函数定义的子群体。4) 在真实图数据上进行实验，验证所提出方法的有效性。

关键创新：最重要的技术创新点在于将GNN的表达性与布尔函数理论联系起来，并提出了子群体布尔同构(SBI)的概念。与现有方法相比，SBI能够更准确地评估GNN捕捉复杂子群体结构的能力，从而为公平图挖掘提供更有效的工具。

关键设计：论文的关键设计包括：1) SBI的定义，它基于子群体之间的布尔函数关系来判断图是否同构。2) 基于电路遍历的公平算法，该算法通过遍历电路来识别和处理由高复杂度布尔函数定义的子群体。3) 实验中使用的真实图数据集和评估指标，用于验证所提出方法的有效性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，所提出的基于电路遍历的公平算法在真实图数据上能够有效降低公平性差距，尤其是在处理由高复杂度布尔函数定义的子群体时，优于现有基线方法。例如，在某些数据集上，该方法能够将交叉群体的公平性差距降低到现有方法的1/2甚至更低，证明了其在公平图挖掘方面的有效性。

🎯 应用场景

该研究成果可应用于社交网络分析、推荐系统、金融风控等领域，尤其是在需要考虑公平性的场景下。例如，在信贷评估中，可以利用该方法识别并消除对特定子群体（如少数族裔）的歧视，从而提高信贷评估的公平性。该研究为设计更公平、更可靠的GNN模型提供了理论基础和实践指导。

📄 摘要（原文）

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.