論文の概要: Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2106.01854v1
• Date: Thu, 3 Jun 2021 13:57:32 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-04 19:39:59.202541
• Title: Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement Learning
• Title（参考訳）: 強化学習を用いた最適化に基づく代数的マルチグリッド粗大化
• Authors: Ali Taghibakhshi, Scott MacLachlan, Luke Olson, Matthew West
• Abstract要約: 線型方程式の系は未知の集合上のグラフを定義する。 多重グリッドソルバの各レベルは、粗グラフの適切な選択と、粗表現への写像と演算子を必要とする。 粗いグラフ選択を条件として、AMGと制限演算子を直接学習できることが示されている。 グラフニューラルネットワーク(GNN)に基づく強化学習エージェントを用いたスパース手法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large sparse linear systems of equations are ubiquitous in science and engineering, such as those arising from discretizations of partial differential equations. Algebraic multigrid (AMG) methods are one of the most common methods of solving such linear systems, with an extensive body of underlying mathematical theory. A system of linear equations defines a graph on the set of unknowns and each level of a multigrid solver requires the selection of an appropriate coarse graph along with restriction and interpolation operators that map to and from the coarse representation. The efficiency of the multigrid solver depends critically on this selection and many selection methods have been developed over the years. Recently, it has been demonstrated that it is possible to directly learn the AMG interpolation and restriction operators, given a coarse graph selection. In this paper, we consider the complementary problem of learning to coarsen graphs for a multigrid solver. We propose a method using a reinforcement learning (RL) agent based on graph neural networks (GNNs), which can learn to perform graph coarsening on small training graphs and then be applied to unstructured large graphs. We demonstrate that this method can produce better coarse graphs than existing algorithms, even as the graph size increases and other properties of the graph are varied. We also propose an efficient inference procedure for performing graph coarsening that results in linear time complexity in graph size.
• Abstract（参考訳）: 大きなスパース線形方程式系は、偏微分方程式の離散化から生じるような科学や工学においてユビキタスである。 代数的多重グリッド法(英語版)(AMG)はそのような線形系を解く最も一般的な方法の1つである。 線形方程式系は未知数の集合上のグラフを定義し、マルチグリッドソルバの各レベルは、粗い表現に写像する制限と補間演算子とともに適切な粗グラフの選択を必要とする。 マルチグリッドソルバの効率はこの選択に極めて依存しており、長年にわたって多くの選択法が開発されてきた。 近年,粗いグラフ選択を条件として,AMG補間および制限演算子を直接学習できることが実証されている。 本稿では,マルチグリッド解法において,グラフを粗いものにするための学習の相補的な問題を考える。 本稿では、グラフニューラルネットワーク(GNN)に基づく強化学習(RL)エージェントを用いて、小さなトレーニンググラフ上でグラフ粗化を学習し、非構造化の大きなグラフに適用する手法を提案する。 本手法は,グラフのサイズが増加し,グラフの他の特性が変化しても,既存のアルゴリズムよりも粗いグラフを生成できることを実証する。 また,グラフサイズの線形時間複雑性をもたらすグラフ粗さを効率的に推定する手法を提案する。

関連論文リスト

• Polynomial Graphical Lasso: Learning Edges from Gaussian Graph-Stationary Signals [18.45931641798935]
  本稿では,Nudal信号からグラフ構造を学習する新しい手法であるPolynomial Graphical Lasso (PGL)を紹介する。 我々の重要な貢献は、グラフ上のガウス的および定常的な信号であり、グラフ学習ラッソの開発を可能にすることである。
  論文  参考訳（メタデータ） (2024-04-03T10:19:53Z)
• HeteroMILE: a Multi-Level Graph Representation Learning Framework for Heterogeneous Graphs [13.01983932286923]
  異種グラフ上のノードのマルチレベル埋め込みフレームワーク(HeteroMILE)を提案する。 HeteroMILEは、グラフを埋め込む前に、グラフのバックボーン構造を保ちながら、大きなグラフを小さなサイズに繰り返し調整する。 その後、ヘテロジニアスグラフ畳み込みニューラルネットワークを用いて、元のグラフへの粗い埋め込みを洗練する。
  論文  参考訳（メタデータ） (2024-03-31T22:22:10Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。 我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
  論文  参考訳（メタデータ） (2022-10-27T16:00:45Z)
• A Unified Framework for Optimization-Based Graph Coarsening [5.720402020129441]
  大きなグラフが与えられたとき、グラフ粗化は、もともと与えられたグラフの特性を保ちながら、より小さく抽出可能なグラフを学習することを目的としている。 提案するフレームワークは,グラフ学習と次元減少の一体化にある。 学習された粗大化グラフは、元のグラフと類似した$epsin(0,1)$であることが確立されている。
  論文  参考訳（メタデータ） (2022-10-02T06:31:42Z)
• Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
  Graphonは任意のサイズでグラフを生成する非パラメトリックモデルであり、グラフから簡単に誘導できる。 解析可能でスケーラブルなグラフ生成モデルを構築するために,textitgraphon autoencoder という新しいフレームワークを提案する。 線形グルーポン分解モデルはデコーダとして機能し、潜在表現を活用して誘導されたグルーポンを再構成する。
  論文  参考訳（メタデータ） (2021-05-29T08:11:40Z)
• GL-Coarsener: A Graph representation learning framework to construct coarse grid hierarchy for AMG solvers [0.0]
  代数的多重グリッド法(英: Algebraic multi-grid method、AMG)は、方程式の大きな線形系を効率的に解くために用いられる数値法である。 本稿では,グラフ表現学習とクラスタリングアルゴリズムを利用した集約型粗大化フレームワークを提案する。 提案手法は,AMG研究分野に機械学習の能力を導入し,今後の研究への新たな視点を開く。
  論文  参考訳（メタデータ） (2020-11-19T17:49:09Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous Graph Neural Networks [39.370875358317946]
  現在のグラフニューラルネットワーク(GNN)は、多くのグラフ解析問題を解く際に、スケール(グラフサイズ、グラフ径、エッジウェイトなど)に関する一般化性に欠ける。 まず,グラフサイズに対する共通グラフ理論アルゴリズムの反復回数の依存性に着想を得て,GNNにおけるメッセージパッシングプロセスの終了を,進捗に応じて順応的に学習する。 第二に、多くのグラフ理論アルゴリズムがグラフの重みに関して均一であるという事実に着想を得て、一般のGを変換するために、普遍的同次関数近似器である同次変換層を導入する。
  論文  参考訳（メタデータ） (2020-10-26T12:57:28Z)
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings [53.58077686470096]
  グラフ構造とグラフ埋め込みを協調的かつ反復的に学習するための、エンドツーエンドのグラフ学習フレームワーク、すなわち、IDGL(Iterative Deep Graph Learning)を提案する。 実験の結果,提案したIDGLモデルは,最先端のベースラインを一貫して上回る,あるいは一致させることができることがわかった。
  論文  参考訳（メタデータ） (2020-06-21T19:49:15Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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