論文の概要: Unsupervised Learning for the Elementary Shortest Path Problem

• arxiv url: http://arxiv.org/abs/2508.01557v1
• Date: Sun, 03 Aug 2025 03:03:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-05 18:25:21.938776
• Title: Unsupervised Learning for the Elementary Shortest Path Problem
• Title（参考訳）: 最短経路問題に対する教師なし学習
• Authors: Jingyi Chen, Xinyuan Zhang, Xinwu Qian,
• Abstract要約: プライマリ・ショート・パス問題(英語版) (ESPP) は、s から t への最小のコストパスを求め、それぞれを一度に訪問する。 本稿では,教師なしグラフニューラルネットワークによって実現された近似ESPPの確率的探索法を提案する。
• 参考スコア（独自算出の注目度）: 5.617211365270248
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Elementary Shortest-Path Problem(ESPP) seeks a minimum cost path from s to t that visits each vertex at most once. The presence of negative-cost cycles renders the problem NP-hard. We present a probabilistic method for finding near-optimal ESPP, enabled by an unsupervised graph neural network that jointly learns node value estimates and edge-selection probabilities via a surrogate loss function. The loss provides a high probability certificate of finding near-optimal ESPP solutions by simultaneously reducing negative-cost cycles and embedding the desired algorithmic alignment. At inference time, a decoding algorithm transforms the learned edge probabilities into an elementary path. Experiments on graphs of up to 100 nodes show that the proposed method surpasses both unsupervised baselines and classical heuristics, while exhibiting high performance in cross-size and cross-topology generalization on unseen synthetic graphs.
• Abstract（参考訳）: プライマリ・ショート・パス問題(英語版) (ESPP) は、各頂点を最大1回訪問する s から t までの最小コストパスを求める。 負のコストサイクルの存在は、NPハードの問題を引き起こす。 本稿では,ノード値の推定値とエッジ選択確率を協調的に学習する,教師なしグラフニューラルネットワークによって実現された近似ESPPの確率的探索法を提案する。 この損失は、負のコストサイクルを同時に減らし、所望のアルゴリズムアライメントを埋め込むことで、ほぼ最適のESPPソリューションを見つけるための高い確率証明を提供する。 推論時、復号アルゴリズムは学習したエッジ確率を基本経路に変換する。 最大100ノードのグラフ実験により,提案手法は教師なしベースラインと古典的ヒューリスティックを超越し,また,未知の合成グラフ上でのクロスサイズおよびクロストポロジーの一般化において高い性能を示した。

関連論文リスト

• Sparse Decomposition of Graph Neural Networks [20.768412002413843]
  本稿では,集約中に含まれるノード数を削減する手法を提案する。 線形変換された特徴の重み付け和を用いてノード表現の近似を学習し、スパース分解によりこれを実現できる。 提案手法は推論高速化のために設計された他のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-25T17:52:16Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Tightest Admissible Shortest Path [4.928034044959278]
  グラフにおける最短経路問題はAIの基本である。 本稿では,最適コストに縛られた最短経路である許容最短経路(TASP)の探索問題を紹介する。 我々は、ソリューションの品質を保証し、TASPを解くための完全なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-15T14:39:05Z)
• Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
  本稿では,候補アルゴリズムの集合に有効な手法を提案する。 内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。 提案手法は,他のアルゴリズムのスコアを大幅に改善する。
  論文  参考訳（メタデータ） (2023-05-26T21:49:37Z)
• A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs [19.873384058276713]
  A*Netは知識グラフ推論のためのスケーラブルなパスベースの手法である。 最短繰り返しパス問題に対するA*アルゴリズムにインスパイアされた我々のA*Netは、それぞれに重要なノードとエッジを選択する優先度関数を学習する。
  論文  参考訳（メタデータ） (2022-06-07T01:01:36Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• Scaling Up Graph Neural Networks Via Graph Coarsening [18.176326897605225]
  グラフニューラルネットワーク(GNN)のスケーラビリティは、マシンラーニングにおける大きな課題のひとつだ。 本稿では,GNNのスケーラブルなトレーニングにグラフ粗大化を用いることを提案する。 既成の粗大化法を単純に適用すれば,分類精度を著しく低下させることなく,ノード数を最大10倍に削減できることを示す。
  論文  参考訳（メタデータ） (2021-06-09T15:46:17Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
  第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
  論文  参考訳（メタデータ） (2020-08-28T14:46:56Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。 いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。 これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
  論文  参考訳（メタデータ） (2020-03-31T16:54:22Z)
• Resolving learning rates adaptively by locating Stochastic Non-Negative Associated Gradient Projection Points using line searches [0.0]
  ニューラルネットワークトレーニングにおける学習率は現在、高価なマニュアルや自動チューニングを使用したトレーニングの優先事項として決定されている。 本研究では,ニューラルネットワーク学習アルゴリズムの学習率を解くために,勾配のみの線探索を提案する。
  論文  参考訳（メタデータ） (2020-01-15T03:08:07Z)

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

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