論文の概要: Higher-Order Graphon Neural Networks: Approximation and Cut Distance

• arxiv url: http://arxiv.org/abs/2503.14338v1
• Date: Tue, 18 Mar 2025 15:14:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-19 14:15:03.818867
• Title: Higher-Order Graphon Neural Networks: Approximation and Cut Distance
• Title（参考訳）: 高次グラフオンニューラルネットワーク - 近似とカット距離
• Authors: Daniel Herbst, Stefanie Jegelka,
• Abstract要約: グラノンの$k$-WLテストをグラノン信号空間に拡張し、信号重み付き準同型密度を鍵ツールとして導入する。 例として、不変グラフネットワーク(IGN)をグラフに一般化する。 次数 $k$ の IWN は、少なくとも$k$-WL テストと同じくらい強力であることを示し、$Lp$ 距離のグラフン符号に対する普遍近似結果を確立する。
• 参考スコア（独自算出の注目度）: 30.258169775217926
• License:
• Abstract: Graph limit models, like graphons for limits of dense graphs, have recently been used to study size transferability of graph neural networks (GNNs). While most literature focuses on message passing GNNs (MPNNs), in this work we attend to the more powerful higher-order GNNs. First, we extend the $k$-WL test for graphons (B\"oker, 2023) to the graphon-signal space and introduce signal-weighted homomorphism densities as a key tool. As an exemplary focus, we generalize Invariant Graph Networks (IGNs) to graphons, proposing Invariant Graphon Networks (IWNs) defined via a subset of the IGN basis corresponding to bounded linear operators. Even with this restricted basis, we show that IWNs of order $k$ are at least as powerful as the $k$-WL test, and we establish universal approximation results for graphon-signals in $L^p$ distances. This significantly extends the prior work of Cai & Wang (2022), showing that IWNs--a subset of their IGN-small--retain effectively the same expressivity as the full IGN basis in the limit. In contrast to their approach, our blueprint of IWNs also aligns better with the geometry of graphon space, for example facilitating comparability to MPNNs. We highlight that, while typical higher-order GNNs are discontinuous w.r.t. cut distance--which causes their lack of convergence and is inherently tied to the definition of $k$-WL--their transferability remains comparable to MPNNs.
• Abstract（参考訳）: 近年,グラフニューラルネットワーク(GNN)のサイズ伝達可能性の研究に,グラフリミットモデルなどのグラフリミットモデルが用いられている。 ほとんどの文献は、メッセージパッシングGNN(MPNN)に焦点を当てていますが、この作業では、より強力な高階GNNに取り組みます。 まず、グラノンの$k$-WLテスト(B\"oker, 2023)をグラノン信号空間に拡張し、信号重み付き準同型密度を鍵ツールとして導入する。 Invariant Graphon Networks (IWNs) は有界線型演算子に対応するIGN基底のサブセットを介して定義される。 この制限された基底であっても、$k$のIWNは少なくとも$k$-WLテストと同じくらい強力であることを示し、$L^p$距離のグラフン符号に対する普遍近似結果を確立する。 これは、カイ・アンド・ワング (2022) の以前の研究を著しく拡張し、IWNs は IGN-小部分集合であり、その極限において完全な IGN 基底と同じ表現性を持つことを示した。 彼らのアプローチとは対照的に、我々のIWNの青写真は、例えばMPNNとの互換性の促進など、グラドン空間の幾何学とよく一致している。 典型的な高次GNNは不連続なw.r.t.カット距離であり、収束の欠如を引き起こし、本質的に$k$-WLの定義に結びついている。

関連論文リスト

• On the Expressive Power of Subgraph Graph Neural Networks for Graphs with Bounded Cycles [17.29046077604317]
  この研究は、最大$k$までの距離を持つ隣人からの情報を集約する$k$-hopサブグラフGNNを調査します。 我々は、$k$ホップ部分グラフ GNN がグラフ上の置換不変/同変連続関数を任意の誤差許容範囲内で2k+1$以上のサイクルなしで近似できることを証明した。
  論文  参考訳（メタデータ） (2025-02-06T01:25:22Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。 我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
  論文  参考訳（メタデータ） (2022-10-27T16:00:45Z)
• From Local to Global: Spectral-Inspired Graph Neural Networks [28.858773653743075]
  グラフニューラルネットワーク(GNN)は、非ユークリッドデータのための強力なディープラーニング手法である。 MPNNは、局所グラフ地区の信号を集約して結合するメッセージパッシングアルゴリズムである。 MPNNは、過密や過密といった問題に悩まされる可能性がある。
  論文  参考訳（メタデータ） (2022-09-24T17:19:00Z)
• Transferability Properties of Graph Neural Networks [125.71771240180654]
  グラフニューラルネットワーク(GNN)は、中規模グラフでサポートされているデータから表現を学ぶのに成功している。 適度な大きさのグラフ上でGNNを訓練し、それらを大規模グラフに転送する問題について検討する。 その結果, (i) グラフサイズに応じて転送誤差が減少し, (ii) グラフフィルタは非線型性の散乱挙動によってGNNにおいて緩和されるような転送可能性-識別可能性トレードオフを有することがわかった。
  論文  参考訳（メタデータ） (2021-12-09T00:08:09Z)
• Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
  ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。 我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
  論文  参考訳（メタデータ） (2021-06-12T07:43:51Z)
• A Unified Lottery Ticket Hypothesis for Graph Neural Networks [82.31087406264437]
  本稿では,グラフ隣接行列とモデルの重み付けを同時に行う統一GNNスペーシフィケーション(UGS)フレームワークを提案する。 グラフ宝くじ(GLT)をコアサブデータセットとスパースサブネットワークのペアとして定義することにより、人気のある宝くじチケット仮説を初めてGNNsにさらに一般化します。
  論文  参考訳（メタデータ） (2021-02-12T21:52:43Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
  グラフニューラルネットワーク(GNN)は、グラフでサポートされている信号のための情報処理アーキテクチャである。 これらは、個々の層がグラフ畳み込みフィルタのバンクを含む畳み込みニューラルネットワーク(CNN)の一般化である。
  論文  参考訳（メタデータ） (2020-08-04T18:57:36Z)
• Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework [5.835421173589977]
  我々は、グラフ上に定義されたニューラルネットワークをメッセージパッシングニューラルネットワーク(MPNN)としてキャストした。 匿名MPNNと学位対応MPNNの2種類のMPNNについて検討する。 Wesfeiler-Lehman (WL)アルゴリズムの差分パワーの観点から,MPNNの差分パワーの下位値と上位値を求める。
  論文  参考訳（メタデータ） (2020-04-06T12:14:00Z)

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

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