論文の概要: A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Mining

• arxiv url: http://arxiv.org/abs/2601.12751v1
• Date: Mon, 19 Jan 2026 06:15:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-21 22:47:22.775291
• Title: A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Mining
• Title（参考訳）: GNNにおける表現性のためのブール関数理論フレームワークとそのグラフマイニングへの応用
• Authors: Manjish Pal,
• Abstract要約: 本稿ではブール関数理論に基づくグラフニューラルネットワーク(GNN)のための新しい表現性フレームワークを提案する。 SBIはWeisfeiler-Lehman (WL)、双連結性に基づくフレームワーク、準同型に基づくフレームワークなどの既存の表現度尺度を仮定する。 パリティのような複雑度の高いブール関数によって定義されるサブポピュレーションを処理できる回路トラバースベースフェアネスアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 本稿では,ブール関数理論に基づくグラフニューラルネットワーク(GNN)の表現性フレームワークを提案する。 我々は、Weisfeiler-Lehman (WL) や双連結性に基づくフレームワーク、および準同型に基づくフレームワークのような既存の表現度尺度を厳密に仮定する不変量として \textit{Subpopulation Boolean Isomorphism} (SBI) の概念を導入する。 理論的には、フーリエ次数、回路類(AC$^0$, NC$^1$)、およびフェアネスを意識したGNNにおける表現性に対する重要な障壁としての影響を同定する。 本研究では,パリティのような複雑度の高いブール関数によって定義されるサブポピュレーションを処理し,既存のベースラインを損なう回路トラバースベースのフェアネスアルゴリズムを設計する。 実世界のグラフ実験により, 最先端の手法が失敗する交差点群間での低公平性ギャップが達成され, フェアネスに合わせたGNN表現率の第一原理的処理が実現された。

関連論文リスト

• Improving LLM Reasoning with Homophily-aware Structural and Semantic Text-Attributed Graph Compression [55.51959317490934]
  大規模言語モデル(LLM)は、テキスト分散グラフ(TAG)理解において有望な能力を示している。 グラフは本来、構造情報や意味情報を豊富に含むものであり、それらの有効利用はLLMの推論性能の潜在的な利益を解放する可能性があると論じる。 グラフホモフィリーの活用を目的としたフレームワーク LLMs (HS2C) のホモフィリー対応構造とセマンティック圧縮を提案する。
  論文  参考訳（メタデータ） (2026-01-13T03:35:18Z)
• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
  グラフニューラルネットワーク(GNN)は、リレーショナルデータに対する学習と推論の標準的なアプローチとなっている。 本稿では,回路複雑性のレンズによるGNNの計算限界について検討する。 具体的には、共通GNNアーキテクチャの回路複雑性を分析し、定数層、線形またはサブ線形埋め込みサイズ、精度の制約の下で、GNNはグラフ接続やグラフ同型といった重要な問題を解くことができないことを証明している。
  論文  参考訳（メタデータ） (2025-01-11T05:54:10Z)
• Graph Classification with GNNs: Optimisation, Representation and Inductive Bias [0.6445605125467572]
  このような等価性は、付随する最適化問題を無視するものであり、GNN学習プロセスの全体像を提供するものではない、と我々は主張する。 理論的には、グラフ内のメッセージパッシング層は、識別サブグラフか、あるいはグラフ全体に分散した識別ノードの集合を探索する傾向にあることを証明している。
  論文  参考訳（メタデータ） (2024-08-17T18:15:44Z)
• Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes [4.23480641508611]
  グラフニューラルネットワーク(GNN)は理論上、1-Weisfeiler-Lehmanテストによって拘束される。 本研究では, トポロジ的メッセージパッシング過程において, グラフ内の単純な経路に着目し, 新たな視点を示す。
  論文  参考訳（メタデータ） (2023-08-13T19:45:20Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Equivariant Neural Network for Factor Graphs [83.26543234955855]
  因子同変ニューラルネットワーク(FE-NBP)と因子同変グラフニューラルネットワーク(FE-GNN)の2つの推論モデルを提案する。 FE-NBPは小さなデータセットで最先端のパフォーマンスを達成する一方、FE-GNNは大規模なデータセットで最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2021-09-29T06:54:04Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。