論文の概要: Limits of message passing for node classification: How class-bottlenecks restrict signal-to-noise ratio

• arxiv url: http://arxiv.org/abs/2508.17822v1
• Date: Mon, 25 Aug 2025 09:25:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-26 18:43:45.707433
• Title: Limits of message passing for node classification: How class-bottlenecks restrict signal-to-noise ratio
• Title（参考訳）: ノード分類におけるメッセージパッシングの限界:クラス・ブートネックが信号・雑音比をいかに制限するか
• Authors: Jonathan Rubin, Sahil Loomba, Nick S. Jones,
• Abstract要約: メッセージパッシングニューラルネットワーク(MPNN)はノード分類の強力なモデルであるが、グラフのヘテロフィリーおよび構造的ボトルネックの下でのパフォーマンス制限に悩まされている。 本稿では,MPNN表現の信号対雑音比(SNR)を用いて,ヘテロフィリとボトルネックの関係を明らかにする。 高次ホモフィリーを最大化するための最適グラフ構造は、単クラスおよび二クラス二部体の解離結合であることを示す。 これにより、全てのホモフィリーにおけるほぼ完璧な分類精度を達成するグラフアンサンブルに基づく再配線アルゴリズムBRIDGEが得られる。
• 参考スコア（独自算出の注目度）: 0.6117371161379209
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Message passing neural networks (MPNNs) are powerful models for node classification but suffer from performance limitations under heterophily (low same-class connectivity) and structural bottlenecks in the graph. We provide a unifying statistical framework exposing the relationship between heterophily and bottlenecks through the signal-to-noise ratio (SNR) of MPNN representations. The SNR decomposes model performance into feature-dependent parameters and feature-independent sensitivities. We prove that the sensitivity to class-wise signals is bounded by higher-order homophily -- a generalisation of classical homophily to multi-hop neighbourhoods -- and show that low higher-order homophily manifests locally as the interaction between structural bottlenecks and class labels (class-bottlenecks). Through analysis of graph ensembles, we provide a further quantitative decomposition of bottlenecking into underreaching (lack of depth implying signals cannot arrive) and oversquashing (lack of breadth implying signals arriving on fewer paths) with closed-form expressions. We prove that optimal graph structures for maximising higher-order homophily are disjoint unions of single-class and two-class-bipartite clusters. This yields BRIDGE, a graph ensemble-based rewiring algorithm that achieves near-perfect classification accuracy across all homophily regimes on synthetic benchmarks and significant improvements on real-world benchmarks, by eliminating the ``mid-homophily pitfall'' where MPNNs typically struggle, surpassing current standard rewiring techniques from the literature. Our framework, whose code we make available for public use, provides both diagnostic tools for assessing MPNN performance, and simple yet effective methods for enhancing performance through principled graph modification.
• Abstract（参考訳）: メッセージパッシングニューラルネットワーク(MPNN)はノード分類の強力なモデルであるが、ヘテロフィリー(同クラスの接続性が低い)とグラフの構造的ボトルネックによるパフォーマンス制限に悩まされている。 本稿では,MPNN表現の信号対雑音比(SNR)を用いて,ヘテロフィリとボトルネックの関係を明らかにする。 SNRはモデル性能を特徴に依存しないパラメータと特徴に依存しない感度に分解する。 クラスワイド信号に対する感度は、古典的ホモフィリーからマルチホップ近傍への一般化である高次ホモフィリーによって境界付けられており、低次ホモフィリーが構造的ボトルネックとクラスラベル(クラスボトルネック)の間の相互作用として局所的に現れることを示す。 グラフアンサンブルを解析することにより、閉形式表現でボトルネックをより定量的に分解し、アンダーリーチング(奥行き指示信号の欠如)とオーバーシャッシング(より少ない経路で到着する広帯域指示信号の欠如)に分解する。 高次ホモフィリーを最大化するための最適グラフ構造は、単クラスおよび二クラス二部体の解離結合であることを示す。 BRIDGEはグラフアンサンブルに基づくリワイアリングアルゴリズムであり、MPNNが通常苦労する「中間ホモフィア・落とし穴」を排除し、既存の標準的なリワイアリング技術を上回ることで、すべてのホモフィア・レギュレーションを総合ベンチマークでほぼ完璧に分類し、実世界のベンチマークを大幅に改善する。 我々のフレームワークは、MPNNのパフォーマンスを評価するための診断ツールと、原則付きグラフ修正による性能向上のためのシンプルで効果的な方法の両方を提供している。

関連論文リスト

• ReDiSC: A Reparameterized Masked Diffusion Model for Scalable Node Classification with Structured Predictions [64.17845687013434]
  本稿では,構造化ノード分類のための構造拡散モデルであるReDiSCを提案する。 本稿では,ReDiSCが最先端のGNN,ラベル伝搬,拡散ベースラインと比較して,優れた,あるいは高い競争力を発揮することを示す。 特にReDiSCは、従来の構造化拡散法が計算制約によって失敗する大規模データセットに効果的にスケールする。
  論文  参考訳（メタデータ） (2025-07-19T04:46:53Z)
• Graph Structure Refinement with Energy-based Contrastive Learning [56.957793274727514]
  グラフの構造と表現を学習するための生成訓練と識別訓練のジョイントに基づく教師なし手法を提案する。 本稿では,ECL-GSR(Energy-based Contrastive Learning)によるグラフ構造再構成(GSR)フレームワークを提案する。 ECL-GSRは、主要なベースラインに対するサンプルやメモリの少ない高速なトレーニングを実現し、下流タスクの単純さと効率性を強調している。
  論文  参考訳（メタデータ） (2024-12-20T04:05:09Z)
• Optimality of Message-Passing Architectures for Sparse Graphs [12.42591017155152]
  スパース設定における特徴デコレーショングラフ上のノード分類問題、すなわちノードの期待次数がノード数で$O(1)$である場合について検討する。 局所ベイズ最適性(英語版)と呼ばれるノード分類タスクに対するベイズ最適性(英語版)の概念を導入する。 最適なメッセージパッシングアーキテクチャは,低グラフ信号のレギュレーションにおける標準と高グラフ信号のレギュレーションにおける典型とを補間することを示す。
  論文  参考訳（メタデータ） (2023-05-17T17:31:20Z)
• Mixed Graph Contrastive Network for Semi-Supervised Node Classification [63.924129159538076]
  我々はMixed Graph Contrastive Network(MGCN)と呼ばれる新しいグラフコントラスト学習手法を提案する。 本研究では,非摂動増強戦略と相関還元機構により,潜伏埋め込みの識別能力を向上する。 これら2つの設定を組み合わせることで、識別表現学習のために、豊富なノードと稀に価値あるラベル付きノードの両方から、豊富な監視情報を抽出する。
  論文  参考訳（メタデータ） (2022-06-06T14:26:34Z)
• Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation [6.071760028190454]
  本稿では,グラフに対する半教師付きノード分類において,グラフアルゴリズムのラベル伝搬と浅いニューラルネットワークを組み合わせることで,GNNに匹敵する性能が得られることを示す。 本稿では,ノードが反対クラスのノードに接続されることの多い低ホモフィリーグラフ上では,このアプローチが不十分であることを示す。 アルゴリズムはまずクラス互換行列を学習し、次にクラス適合性によって重み付けされたLPアルゴリズムを用いてラベル予測を集約する。
  論文  参考訳（メタデータ） (2022-05-19T08:34:34Z)
• Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs [28.77753005139331]
  半教師付きノード分類タスクにおけるグラフニューラルネットワークのヘテロフィリーまたは低ホモフィリー下での表現力について検討する。 多くの人気のあるGNNは、この設定を一般化することができず、グラフ構造を無視したモデルよりも優れています。 ヘテロフィリーの下でのグラフ構造からの学習を促進する重要な設計の集合を同定する。
  論文  参考訳（メタデータ） (2020-06-20T02:05:01Z)

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

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