論文の概要: Halting Recurrent GNNs and the Graded $μ$-Calculus

• arxiv url: http://arxiv.org/abs/2505.11050v1
• Date: Fri, 16 May 2025 09:46:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-19 14:36:14.563632
• Title: Halting Recurrent GNNs and the Graded $μ$-Calculus
• Title（参考訳）: Halting Recurrent GNNs and the Graded $μ$-Calculus
• Authors: Jeroen Bollen, Jan Van den Bussche, Stijn Vansummeren, Jonni Virtema,
• Abstract要約: グラフニューラルネットワーク(GNN)は、グラフ構造化データを扱う機械学習モデルのクラスである。 現在のGNNの提案では、グラフのサイズがモデルに与えられるか、終了保証の欠如に悩まされていると仮定している。 本稿では,繰り返しGNNの停止機構を提案する。
• 参考スコア（独自算出の注目度）: 1.1662068132437746
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) are a class of machine-learning models that operate on graph-structured data. Their expressive power is intimately related to logics that are invariant under graded bisimilarity. Current proposals for recurrent GNNs either assume that the graph size is given to the model, or suffer from a lack of termination guarantees. In this paper, we propose a halting mechanism for recurrent GNNs. We prove that our halting model can express all node classifiers definable in graded modal mu-calculus, even for the standard GNN variant that is oblivious to the graph size. A recent breakthrough in the study of the expressivity of graded modal mu-calculus in the finite suggests that conversely, restricted to node classifiers definable in monadic second-order logic, recurrent GNNs can express only node classifiers definable in graded modal mu-calculus. To prove our main result, we develop a new approximate semantics for graded mu-calculus, which we believe to be of independent interest. We leverage this new semantics into a new model-checking algorithm, called the counting algorithm, which is oblivious to the graph size. In a final step we show that the counting algorithm can be implemented on a halting recurrent GNN.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフ構造化データを扱う機械学習モデルのクラスである。 その表現力は、次数二相性の下で不変である論理と密接に関連している。 現在のGNNの提案では、グラフのサイズがモデルに与えられるか、終了保証の欠如に悩まされていると仮定している。 本稿では,繰り返しGNNの停止機構を提案する。 我々は,グラフサイズに比例しない標準GNN変種であっても,次数付きモーダル法で定義可能なすべてのノード分類器を,停止モデルで表現できることを証明した。 有限の次数モジュラーム計算の表現性の研究における最近のブレークスルーは、逆に、モナディック二階述語論理で定義可能なノード分類器に制限された GNN が、階数モジュラーム計算で定義可能なノード分類器のみを表現できることを示唆している。 本研究の主な成果を実証するため,本研究では,無関心であると考えられる等級準数に対する近似的セマンティクスを新たに開発した。 我々はこの新たなセマンティクスを,グラフサイズに比例しないカウントアルゴリズムと呼ばれる,新しいモデルチェックアルゴリズムに活用する。 最後のステップでは、カウントアルゴリズムが停止繰り返しGNN上で実装可能であることを示す。

関連論文リスト

• Repetition Makes Perfect: Recurrent Sum-GNNs Match Message Passing Limit [2.2625389420008624]
  本稿では,有限精度パラメータを持つリカレントグラフニューラルネットワーク(リカレントGNN)の表現性について,第1の厳密なバウンダリを提供する。 累積アグリゲーションとReLUアクティベーションの繰り返しGNNが任意のグラフアルゴリズムをエミュレートできることを証明する。
  論文  参考訳（メタデータ） (2025-05-01T04:27:35Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• On the approximation capability of GNNs in node classification/regression tasks [4.141514895639094]
  グラフニューラルネットワーク(GNN)は、グラフ処理のための幅広い種類の接続モデルである。 GNNはノード分類/回帰タスクの確率の普遍近似であることを示す。
  論文  参考訳（メタデータ） (2021-06-16T17:46:51Z)
• On the Universality of Graph Neural Networks on Large Random Graphs [22.720758067273195]
  グラフニューラルネットワーク(GNN)の潜在位置乱数グラフに対する近似能力について検討する。 大きなグラフ極限では、GNNはc-GNNとして知られるある種の連続的なモデルに収束することが知られている。 我々は,c-SGNNが連続限界におけるc-GNNよりも厳格に強力なことを示す。
  論文  参考訳（メタデータ） (2021-05-27T12:52:36Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。 本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。 UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
  論文  参考訳（メタデータ） (2020-10-05T04:57:18Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。 標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。 本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。 我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
  論文  参考訳（メタデータ） (2020-10-02T19:53:05Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。 FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
  論文  参考訳（メタデータ） (2020-06-28T16:35:45Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データから実際に学習する上で、近年大きな進歩を遂げている。 回帰問題と二項分類問題の両方に隠れ層を持つGNNの理論的に基底的な一般化可能性解析を行う。
  論文  参考訳（メタデータ） (2020-06-25T00:45:52Z)

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

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