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

• URL: http://arxiv.org/abs/2601.12751v1
• Date: Mon, 19 Jan 2026 06:15:25 GMT
• Title: A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Mining
• Authors: Manjish Pal,
• Abstract summary: We propose a novel expressivity framework for Graph Neural Networks (GNNs) grounded in Boolean function theory.<n>We show that SBI subsumes existing expressivity measures such as Weisfeiler-Lehman (WL), biconnectivity-based, and homomorphism-based frameworks.<n>We design a circuit-traversal-based fairness algorithm capable of handling subpopulations defined by high-complexity Boolean functions, such as parity.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Improving LLM Reasoning with Homophily-aware Structural and Semantic Text-Attributed Graph Compression [55.51959317490934]
  Large language models (LLMs) have demonstrated promising capabilities in Text-Attributed Graph (TAG) understanding.<n>We argue that graphs inherently contain rich structural and semantic information, and that their effective exploitation can unlock potential gains in LLMs reasoning performance.<n>We propose Homophily-aware Structural and Semantic Compression for LLMs (HS2C), a framework centered on exploiting graph homophily.
  arXiv  Detail & Related papers  (2026-01-13T03:35:18Z)
• On the Relationship Between Robustness and Expressivity of Graph Neural Networks [7.161966906570077]
  Graph Neural Networks (GNNs) are vulnerable to bit-flip attacks (BFAs)<n>We introduce an analytical framework to study the influence of architectural features, graph properties, and their interaction.<n>We derive theoretical bounds for the number of bit flips required to degrade GNN expressivity on a dataset.
  arXiv  Detail & Related papers  (2025-04-18T16:38:33Z)
• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
  Graph Neural Networks (GNNs) have become the standard approach for learning and reasoning over relational data.<n>This paper explores the computational limitations of GNNs through the lens of circuit complexity.<n>Specifically, we analyze the circuit complexity of common GNN architectures and prove that under constraints of constant-depth layers, linear or sublinear embedding sizes, and precision, GNNs cannot solve key problems such as graph connectivity and graph isomorphism.
  arXiv  Detail & Related papers  (2025-01-11T05:54:10Z)
• Graph Classification with GNNs: Optimisation, Representation and Inductive Bias [0.6445605125467572]
  We argue that such equivalence ignores the accompanying optimization issues and does not provide a holistic view of the GNN learning process. We prove theoretically that the message-passing layers in the graph, have a tendency to search for either discriminative subgraphs, or a collection of discriminative nodes dispersed across the graph.
  arXiv  Detail & Related papers  (2024-08-17T18:15:44Z)
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness [35.409017863665575]
  Homomorphism expressivity measures the ability of GNN models to count graphs under homomorphism. By examining four classes of prominent GNNs as case studies, we derive simple, unified, and elegant descriptions of their homomorphism expressivity. Our results provide novel insights into a series of previous work, unify the landscape of different subareas in the community, and settle several open questions.
  arXiv  Detail & Related papers  (2024-01-16T17:23:23Z)
• Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes [4.23480641508611]
  Graph Neural Networks (GNNs) are theoretically bounded by the 1-Weisfeiler-Lehman test. Our study presents a novel perspective by focusing on simple paths within graphs during the topological message-passing process.
  arXiv  Detail & Related papers  (2023-08-13T19:45:20Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  We propose a simple yet efficient framework to make the homogeneous GNNs have adequate ability to handle heterogeneous graphs. Specifically, we propose Relation Embedding based Graph Neural Networks (RE-GNNs), which employ only one parameter per relation to embed the importance of edge type relations and self-loop connections.
  arXiv  Detail & Related papers  (2022-09-23T05:24:18Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• Equivariant Neural Network for Factor Graphs [83.26543234955855]
  We propose two inference models: Factor-Equivariant Neural Belief Propagation (FE-NBP) and Factor-Equivariant Graph Neural Networks (FE-GNN) FE-NBP achieves state-of-the-art performance on small datasets while FE-GNN achieves state-of-the-art performance on large datasets.
  arXiv  Detail & Related papers  (2021-09-29T06:54:04Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30:31Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  Graph auto-encoder (GAE) models are based on semi-supervised graph convolution networks (GCN) We design a specific GAE-based model for graph clustering to be consistent with the theory, namely Embedding Graph Auto-Encoder (EGAE) EGAE consists of one encoder and dual decoders.
  arXiv  Detail & Related papers  (2020-02-20T09:53:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.