論文の概要: PF-GNN: Differentiable particle filtering based approximation of universal graph representations

• arxiv url: http://arxiv.org/abs/2401.17752v1
• Date: Wed, 31 Jan 2024 11:26:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-01 14:51:54.131376
• Title: PF-GNN: Differentiable particle filtering based approximation of universal graph representations
• Title（参考訳）: PF-GNN: 微分可能な粒子フィルタリングに基づく普遍グラフ表現の近似
• Authors: Mohammed Haroon Dupty, Yanfei Dong, Wee Sun Lee
• Abstract要約: グラフニューラルネットワーク(GNN)は、グラフ同型に対する1-WL色補正テストによって、表現力に制限があることが知られている。 本研究では,学習過程を厳密な同型解法で導くことによって,GNNを普遍化する手法を提案する。 我々のアルゴリズムはエンドツーエンドで微分可能であり、任意のGNNをバックボーンとして適用することができ、よりリッチなグラフ表現を線形に増加させて学習することができる。
• 参考スコア（独自算出の注目度）: 20.544160526945234
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Message passing Graph Neural Networks (GNNs) are known to be limited in expressive power by the 1-WL color-refinement test for graph isomorphism. Other more expressive models either are computationally expensive or need preprocessing to extract structural features from the graph. In this work, we propose to make GNNs universal by guiding the learning process with exact isomorphism solver techniques which operate on the paradigm of Individualization and Refinement (IR), a method to artificially introduce asymmetry and further refine the coloring when 1-WL stops. Isomorphism solvers generate a search tree of colorings whose leaves uniquely identify the graph. However, the tree grows exponentially large and needs hand-crafted pruning techniques which are not desirable from a learning perspective. We take a probabilistic view and approximate the search tree of colorings (i.e. embeddings) by sampling multiple paths from root to leaves of the search tree. To learn more discriminative representations, we guide the sampling process with particle filter updates, a principled approach for sequential state estimation. Our algorithm is end-to-end differentiable, can be applied with any GNN as backbone and learns richer graph representations with only linear increase in runtime. Experimental evaluation shows that our approach consistently outperforms leading GNN models on both synthetic benchmarks for isomorphism detection as well as real-world datasets.
• Abstract（参考訳）: メッセージパッシンググラフニューラルネットワーク(GNN)は、グラフ同型に対する1-WL色補正テストによって、表現力に制限があることが知られている。 他の表現力のあるモデルは計算コストが高いか、あるいはグラフから構造的特徴を抽出するために前処理が必要である。 本研究では,1-WLの停止時に非対称性を人工的に導入し,さらに色付けを洗練させる手法であるパーソナライズ・アンド・リファインメント(IR)のパラダイムに基づいて,学習過程を厳密な同型解法で導くことにより,GNNを普遍化することを提案する。 同型解法は、葉がグラフを独自に識別する色付けの探索木を生成する。 しかし、木は指数関数的に大きく成長し、学習の観点からは望ましくない手作りの刈り技術が必要である。 探索木の根から葉への複数の経路をサンプリングすることにより,確率的視点を採り,着色の探索木(組込み)を近似する。 識別表現をより詳しく知るために,逐次状態推定のための原理的アプローチである粒子フィルタ更新を用いて,サンプリングプロセスをガイドする。 アルゴリズムはエンドツーエンドで微分可能であり、任意のgnnをバックボーンとして適用でき、実行時の線形な増加だけでよりリッチなグラフ表現を学習できる。 実験により,本手法は実世界のデータセットだけでなく,同型検出のための合成ベンチマークにおいて,GNNモデルよりも一貫して優れていることが示された。

関連論文リスト

• SPGNN: Recognizing Salient Subgraph Patterns via Enhanced Graph Convolution and Pooling [25.555741218526464]
  グラフニューラルネットワーク(GNN)は、グラフやネットワークのような非ユークリッドデータ上での機械学習の分野に革命をもたらした。 本稿では,ノード表現をインジェクティブに更新する結合型グラフ畳み込み機構を提案する。 また,WL-SortPoolと呼ばれるグラフプーリングモジュールを設計し,重要なサブグラフパターンをディープラーニングで学習する。
  論文  参考訳（メタデータ） (2024-04-21T13:11:59Z)
• How Graph Neural Networks Learn: Lessons from Training Dynamics [80.41778059014393]
  グラフニューラルネットワーク(GNN)の関数空間におけるトレーニングダイナミクスについて検討する。 GNNの勾配勾配勾配最適化は暗黙的にグラフ構造を利用して学習関数を更新する。 この発見は、学習したGNN関数が一般化した時期と理由に関する新たな解釈可能な洞察を提供する。
  論文  参考訳（メタデータ） (2023-10-08T10:19:56Z)
• Structural Node Embeddings with Homomorphism Counts [2.0131144893314232]
  準同型は局所構造情報を捉えます 準同型数に基づくノード埋め込みの有効性を実験的に示す。 本手法は,有界木幅グラフクラスに対するグラフ準同型カウントの効率的な計算可能性に着目している。
  論文  参考訳（メタデータ） (2023-08-29T13:14:53Z)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。 Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
  論文  参考訳（メタデータ） (2023-05-18T07:27:18Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Graph Representation Learning with Individualization and Refinement [19.436520792345064]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データ上での表現学習の顕著なモデルとして登場した。 本研究では、個人化・再分極(IR)の古典的アプローチに従う。 我々の手法は、計算複雑性を管理しつつ、よりリッチなノード埋め込みを学習することを可能にする。
  論文  参考訳（メタデータ） (2022-03-17T07:50:48Z)
• Learning to Learn Graph Topologies [27.782971146122218]
  ノードデータからグラフ構造へのマッピングを学習する(L2O)。 このモデルは、ノードデータとグラフサンプルのペアを使ってエンドツーエンドでトレーニングされる。 合成データと実世界のデータの両方の実験により、我々のモデルは、特定のトポロジ特性を持つグラフを学習する際の古典的反復アルゴリズムよりも効率的であることが示された。
  論文  参考訳（メタデータ） (2021-10-19T08:42:38Z)
• Scaling up graph homomorphism for classification via sampling [1.662966122370634]
  グラフ準同型密度特徴を準同型数に対するスケーラブルな代替として使用することを検討する。 準同型密度の加法近似を計算する単純なサンプリングアルゴリズムの高性能な実装を提案する。
  論文  参考訳（メタデータ） (2021-04-08T20:25:37Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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