論文の概要: LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation

• arxiv url: http://arxiv.org/abs/2205.10106v1
• Date: Fri, 20 May 2022 11:54:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-23 13:33:52.103136
• Title: LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation
• Title（参考訳）: LeNSE: 大規模コンビネーション最適化のためのグラフ埋め込みを学習
• Authors: David Ireland and Giovanni Montana
• Abstract要約: ユークリッド部分グラフの埋め込みを地図として用いて,可能な部分グラフの空間をナビゲートする方法を学習する強化学習アルゴリズムを提案する。 LeNSEは、グラフ全体への埋め込みの実行によって見いだされたソリューションに匹敵するソリューションをもたらす小さなサブグラフを識別するが、全体の実行時間のごく一部にはならない。
• 参考スコア（独自算出の注目度）: 6.316693022958222
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial Optimisation problems arise in several application domains and are often formulated in terms of graphs. Many of these problems are NP-hard, but exact solutions are not always needed. Several heuristics have been developed to provide near-optimal solutions; however, they do not typically scale well with the size of the graph. We propose a low-complexity approach for identifying a (possibly much smaller) subgraph of the original graph where the heuristics can be run in reasonable time and with a high likelihood of finding a global near-optimal solution. The core component of our approach is LeNSE, a reinforcement learning algorithm that learns how to navigate the space of possible subgraphs using an Euclidean subgraph embedding as its map. To solve CO problems, LeNSE is provided with a discriminative embedding trained using any existing heuristics using only on a small portion of the original graph. When tested on three problems (vertex cover, max-cut and influence maximisation) using real graphs with up to $10$ million edges, LeNSE identifies small subgraphs yielding solutions comparable to those found by running the heuristics on the entire graph, but at a fraction of the total run time.
• Abstract（参考訳）: 組合せ最適化問題はいくつかの応用領域で発生し、しばしばグラフで定式化される。 これらの問題の多くはNPハードであるが、正確な解は必ずしも必要ではない。 最適に近い解を提供するためにいくつかのヒューリスティックが開発されているが、グラフのサイズほどよくスケールしない。 本稿では,経験則を妥当な時間で実行し,大域的近似解を見つける確率の高い元グラフの(おそらくはるかに小さい)部分グラフを特定するための低複雑さアプローチを提案する。 提案手法のコアコンポーネントであるLeNSEは、ユークリッド部分グラフの埋め込みをマップとして使用して、可能な部分グラフの空間をナビゲートする方法を学ぶ強化学習アルゴリズムである。 CO問題を解決するため、LeNSEは元のグラフのごく一部だけを用いて既存のヒューリスティックスを用いて訓練された識別的埋め込みを備える。 最大100万ドルのエッジを持つ実グラフを用いて3つの問題(頂点被覆、最大カット、影響最大化)でテストした場合、LeNSEはグラフ全体においてヒューリスティックスを実行することで得られる解に匹敵する小さな部分グラフを、全体の実行時間のごく一部で特定する。

関連論文リスト

• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  問題解決のために,最初の完全同変モデルとトレーニングを導入する。 入力グラフのマルチスケール構造を捉えることが不可欠である。 本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
  論文  参考訳（メタデータ） (2023-10-24T06:22:20Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Can Language Models Solve Graph Problems in Natural Language? [51.28850846990929]
  大型言語モデル (LLM) は暗黙的なグラフィカル構造を持つ様々なタスクに採用されている。 自然言語をシミュレーションするグラフベース問題解決のベンチマークであるNLGraphを提案する。
  論文  参考訳（メタデータ） (2023-05-17T08:29:21Z)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。 提案手法は,複数のMOTデータセット上での最先端性能を実現する。 画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
  論文  参考訳（メタデータ） (2023-03-27T17:39:00Z)
• Improved Exact and Heuristic Algorithms for Maximum Weight Clique [1.2074552857379273]
  最大重量傾き問題の解法として,精度の向上とラベリングアルゴリズムを提案する。 提案アルゴリズムは, 局所グラフ構造を用いた新しいデータ削減規則を用いて, 成功した手法をインターリーブする。 我々は,アルゴリズムを合成および実世界のグラフで評価し,ほとんどの入力において,その技術の現状よりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-01T14:02:06Z)
• Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations [0.0]
  本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。 本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。 分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
  論文  参考訳（メタデータ） (2022-10-30T22:04:32Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time [12.43303621344215]
  専門知識のないグラフ上での最適化問題を解くための新しいフレームワークを開発する。 本手法は,グラフのラベル付きトレーニングセット上で強化学習を用いてグラフニューラルネットワークを訓練する。 最適性ギャップが 1 に近い 2 つのNP-ハード問題に対して,本手法がよく一般化可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-06T01:35:45Z)

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

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