論文の概要: CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

• arxiv url: http://arxiv.org/abs/2502.18663v1
• Date: Tue, 25 Feb 2025 21:53:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-27 14:55:29.032859
• Title: CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs
• Title（参考訳）: CayleyPy RL:Cayleyグラフのパスフィニングと強化学習
• Authors: A. Chervov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii, V. Zamkovoy, L. Cheldieva, I. Koltsov, A. Sychev, M. Obozov, A. Eliseev, S. Nikolenko, N. Narynbaev, R. Turtayev, N. Rokotyan, S. Kovalev, A. Rozanov, V. Nelin, S. Ermilov, L. Shishina, D. Mamayeva, A. Korolkova, K. Khoruzhii, A. Romanov,
• Abstract要約: 本論文は,大規模グラフ上でのパスフィリングのための効率的な人工知能ベースのアプローチの開発に関する一連の研究の2番目である。 本稿では, 強化学習手法と, 第1報より直接拡散距離法を併用した新しい手法を提案する。 我々は、OEIS-A186783予想に対して、この直径が機械学習と数学的手法によりn(n-1)/2に等しいという強い支持を与える。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: This paper is the second in a series of studies on developing efficient artificial intelligence-based approaches to pathfinding on extremely large graphs (e.g. $10^{70}$ nodes) with a focus on Cayley graphs and mathematical applications. The open-source CayleyPy project is a central component of our research. The present paper proposes a novel combination of a reinforcement learning approach with a more direct diffusion distance approach from the first paper. Our analysis includes benchmarking various choices for the key building blocks of the approach: architectures of the neural network, generators for the random walks and beam search pathfinding. We compared these methods against the classical computer algebra system GAP, demonstrating that they "overcome the GAP" for the considered examples. As a particular mathematical application we examine the Cayley graph of the symmetric group with cyclic shift and transposition generators. We provide strong support for the OEIS-A186783 conjecture that the diameter is equal to n(n-1)/2 by machine learning and mathematical methods. We identify the conjectured longest element and generate its decomposition of the desired length. We prove a diameter lower bound of n(n-1)/2-n/2 and an upper bound of n(n-1)/2+ 3n by presenting the algorithm with given complexity. We also present several conjectures motivated by numerical experiments, including observations on the central limit phenomenon (with growth approximated by a Gumbel distribution), the uniform distribution for the spectrum of the graph, and a numerical study of sorting networks. To stimulate crowdsourcing activity, we create challenges on the Kaggle platform and invite contributions to improve and benchmark approaches on Cayley graph pathfinding and other tasks.
• Abstract（参考訳）: 本稿では,Cayleyグラフと数学的応用に着目した,非常に大きなグラフ(例えば10^{70}$ノード)をパスフィニングする,効率的な人工知能ベースのアプローチの開発に関する一連の研究の2番目である。 オープンソースのCayleyPyプロジェクトは、私たちの研究の中心的なコンポーネントです。 本稿では, 強化学習アプローチと, より直接拡散距離アプローチを併用した新しい手法を提案する。 私たちの分析では、ニューラルネットワークのアーキテクチャ、ランダムウォーク用のジェネレータ、ビームサーチパスフィニングといった、アプローチの重要なビルディングブロックに対するさまざまな選択肢をベンチマークします。 我々はこれらの手法を古典型計算機代数システムGAPと比較し、検討された例について「GAPを克服する」ことを実証した。 特に数学的な応用として、循環シフトおよび転位生成器を持つ対称群のケイリーグラフについて検討する。 我々は、OEIS-A186783予想に対して、この直径が機械学習と数学的手法によりn(n-1)/2に等しいという強い支持を与える。 予測された最長要素を特定し、所望の長さの分解を生成する。 我々は,n(n-1)/2-n/2の直径下界とn(n-1)/2+3nの上限を,与えられた複雑さでアルゴリズムを提示することによって証明する。 また、中心極限現象(ガンベル分布に近似した成長)の観測、グラフのスペクトルの均一分布、ソートネットワークの数値的研究など、数値実験によって動機付けられたいくつかの予想も提示する。 クラウドソーシング活動の促進を目的として,Kaggleプラットフォーム上での課題を作成し,Cayleyグラフパスフィニングなどのタスクに対するアプローチを改善するためのコントリビューションを募集する。

関連論文リスト

• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。 最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。 データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-03-11T06:34:05Z)
• General Graph Random Features [42.75616308187867]
  重み付き隣接行列の任意の関数の偏りのない推定のためのランダムウォークに基づく新しいアルゴリズムを提案する。 提案アルゴリズムは, ノード数に関して, グラフカーネル評価の厳密な3次スケーリングを克服し, 準四次時間的複雑性を享受する。
  論文  参考訳（メタデータ） (2023-10-07T15:47:31Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Hub-aware Random Walk Graph Embedding Methods for Classification [44.99833362998488]
  ノード分類問題に特化して設計されたランダムウォークに基づく2つの新しいグラフ埋め込みアルゴリズムを提案する。 提案手法は,実世界のネットワークの埋め込みを訓練した3つの分類アルゴリズムの分類性能を解析して実験的に評価する。
  論文  参考訳（メタデータ） (2022-09-15T20:41:18Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。 関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
  論文  参考訳（メタデータ） (2022-07-04T19:33:06Z)
• Sublinear Algorithms for Hierarchical Clustering [14.124026862687941]
  本稿では,3つの線形計算モデルに基づく大規模グラフの階層クラスタリングについて検討する。 すべてのモデルにおいて階層クラスタリングのためのサブ線形アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-06-15T16:25:27Z)
• Degree-Based Random Walk Approach for Graph Embedding [0.0]
  計算量が少なく,ノード接続性に配慮した一様サンプリング手法を提案する。 提案アルゴリズムの利点は,大規模グラフに適用した場合にさらに向上する。
  論文  参考訳（メタデータ） (2021-10-21T19:16:16Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  逆例は機械学習モデルにおいて広く研究されている現象である。 そこで本研究では,$k$-nearest 近傍分類の逆ロバスト性を評価するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-11-19T08:49:10Z)
• Clustering with Tangles: Algorithmic Framework and Theoretical Guarantees [10.992467680364962]
  本稿では,機械学習応用におけるトライアングルの実用可能性を示す。 任意のデータセットのカットの集合が与えられたとき、トライアングルはこれらのカットを密集構造の方向を指し示すために集約する。 タングルを用いたクラスタリングのためのアルゴリズムフレームワークを構築し、様々な設定で理論的保証を証明し、広範囲なシミュレーションとユースケースを提供する。
  論文  参考訳（メタデータ） (2020-06-25T14:23:56Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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