論文の概要: Graph Learning for Combinatorial Optimization: A Survey of
State-of-the-Art
- arxiv url: http://arxiv.org/abs/2008.12646v3
- Date: Thu, 22 Apr 2021 02:07:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-24 21:12:47.546720
- Title: Graph Learning for Combinatorial Optimization: A Survey of
State-of-the-Art
- Title（参考訳）: 組合せ最適化のためのグラフ学習:現状調査
- Authors: Yun Peng, Byron Choi, Jianliang Xu
- Abstract要約: ほとんどのグラフ解析タスクは最適化(CO)問題であり、NPハードである。
最近の研究は、グラフベースのCO問題を解決するために機械学習(ML)を使用する可能性に重点を置いている。
グラフ学習に基づくCO法に関する最近の研究の概要について概説する。
- 参考スコア（独自算出の注目度）: 31.505197052553292
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graphs have been widely used to represent complex data in many applications.
Efficient and effective analysis of graphs is important for graph-based
applications. However, most graph analysis tasks are combinatorial optimization
(CO) problems, which are NP-hard. Recent studies have focused a lot on the
potential of using machine learning (ML) to solve graph-based CO problems. Most
recent methods follow the two-stage framework. The first stage is graph
representation learning, which embeds the graphs into low-dimension vectors.
The second stage uses ML to solve the CO problems using the embeddings of the
graphs learned in the first stage. The works for the first stage can be
classified into two categories, graph embedding (GE) methods and end-to-end
(E2E) learning methods. For GE methods, learning graph embedding has its own
objective, which may not rely on the CO problems to be solved. The CO problems
are solved by independent downstream tasks. For E2E learning methods, the
learning of graph embeddings does not have its own objective and is an
intermediate step of the learning procedure of solving the CO problems. The
works for the second stage can also be classified into two categories,
non-autoregressive methods and autoregressive methods. Non-autoregressive
methods predict a solution for a CO problem in one shot. A non-autoregressive
method predicts a matrix that denotes the probability of each node/edge being a
part of a solution of the CO problem. The solution can be computed from the
matrix. Autoregressive methods iteratively extend a partial solution step by
step. At each step, an autoregressive method predicts a node/edge conditioned
to current partial solution, which is used to its extension. In this survey, we
provide a thorough overview of recent studies of the graph learning-based CO
methods. The survey ends with several remarks on future research directions.
- Abstract（参考訳）: グラフは多くのアプリケーションで複雑なデータを表現するために広く使われている。
グラフベースのアプリケーションでは、効率的かつ効率的なグラフ分析が重要である。
しかし、ほとんどのグラフ解析タスクは、NPハードである組合せ最適化(CO)問題である。
最近の研究は、グラフベースのCO問題を解決するために機械学習(ML)を使用する可能性に重点を置いている。
最近の手法は2段階のフレームワークに従っている。
第1段階はグラフ表現学習であり、グラフを低次元ベクトルに埋め込む。
第2段階では、MLを使用して、第1段で学習したグラフの埋め込みを使用してCO問題を解決する。
第1段階の作業は、グラフ埋め込み(ge)メソッドとエンドツーエンド(e2e)学習メソッドの2つのカテゴリに分類できる。
GE法では、グラフ埋め込みの学習には独自の目的があるが、これは解決すべきCO問題に依存しない可能性がある。
CO問題は独立した下流タスクによって解決される。
E2E学習法では,グラフ埋め込みの学習には独自の目的はなく,CO問題を解くための学習過程の中間段階である。
第2段階の作品は、非自己回帰的方法と自己回帰的方法の2つのカテゴリに分類することもできる。
非自己回帰法は1ショットでCO問題の解を予測する。
非自己回帰法は、CO問題の解の一部である各ノード/エッジの確率を表す行列を予測する。
解は行列から計算できる。
自己回帰的手法は反復的に部分解を段階的に拡張する。
各ステップにおいて、自己回帰法は、その拡張に用いられる現在の部分解に条件付けられたノード/エッジを予測する。
本稿では,グラフ学習に基づくCO法に関する最近の研究の概要について概説する。
調査は、今後の研究方向性に関するいくつかの発言で終わる。
関連論文リスト
- Fast Semi-supervised Learning on Large Graphs: An Improved Green-function Method [93.04936336359502]
グラフに基づく半教師付き学習において、グリーン関数法はグラフ空間におけるグリーン関数の計算によって機能する古典的な方法である。
そこで本研究では,最適化の観点から詳細な解析を行い,新しい手法を提案する。
従来の手法とは異なり,改良手法ではガウス除去法とアンコレッドグラフ法という2つの高速化手法を適用できる。
論文 参考訳（メタデータ） (2024-11-04T04:27:18Z) - From Cluster Assumption to Graph Convolution: Graph-based Semi-Supervised Learning Revisited [51.24526202984846]
グラフベースの半教師付き学習(GSSL)は、長い間ホットな研究トピックだった。
グラフ畳み込みネットワーク (GCN) は, 有望な性能を示す主要な技術となっている。
論文 参考訳（メタデータ） (2023-09-24T10:10:21Z) - Efficiently Learning the Graph for Semi-supervised Learning [4.518012967046983]
共役勾配法を用いてスパース族から最良のグラフを効率的に学習する方法を示す。
我々の手法は、軽度な滑らかさの仮定の下で、オンラインのサブ線形後悔でグラフを効率的に学習するためにも利用できる。
提案手法を実装し,ベンチマークデータセット上の学習グラフを用いた半教師付き学習の先行研究に対して,大幅な(sim$10-100x)スピードアップを示す。
論文 参考訳（メタデータ） (2023-06-12T13:22:06Z) - Learning node embeddings via summary graphs: a brief theoretical
analysis [55.25628709267215]
グラフ表現学習は多くのグラフマイニングアプリケーションにおいて重要な役割を果たすが、大規模なグラフの埋め込みを学習することは依然として問題である。
最近の研究は、グラフの要約(つまり、より小さな要約グラフへの埋め込みを学習し、元のグラフのノード埋め込みを復元することでスケーラビリティを向上させる。
本稿では,導入したカーネル行列に基づく3つの特定の埋め込み学習手法について,詳細な理論的解析を行う。
論文 参考訳（メタデータ） (2022-07-04T04:09:50Z) - LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale
Combinatorial Optimisation [6.316693022958222]
ユークリッド部分グラフの埋め込みを地図として用いて,可能な部分グラフの空間をナビゲートする方法を学習する強化学習アルゴリズムを提案する。
LeNSEは、グラフ全体への埋め込みの実行によって見いだされたソリューションに匹敵するソリューションをもたらす小さなサブグラフを識別するが、全体の実行時間のごく一部にはならない。
論文 参考訳（メタデータ） (2022-05-20T11:54:03Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - Graph Sanitation with Application to Node Classification [41.311131936203715]
質問に答えるために,グラフ衛生問題を導入する。
マイニングモデルの入力の一部として、より良いグラフを学習することで、さまざまな環境でグラフマイニングの恩恵が期待できる。
特に、既存の堅牢なグラフニューラルネットワーク手法よりも25%パフォーマンスが向上する。
論文 参考訳（メタデータ） (2021-05-19T20:22:15Z) - 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) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳（メタデータ） (2020-10-29T09:58:02Z) - Contrastive Self-supervised Learning for Graph Classification [21.207647143672585]
オーバーフィッティングを緩和するために,コントラスト型自己教師学習(CSSL)に基づく2つのアプローチを提案する。
最初のアプローチでは、CSSLを使用して、人間が提供したラベルに頼ることなく、広く利用可能なラベル付きグラフ上のグラフエンコーダを事前訓練する。
第2のアプローチでは、CSSLに基づく正規化器を開発し、教師付き分類タスクと教師なしCSSLタスクを同時に解決する。
論文 参考訳（メタデータ） (2020-09-13T05:12:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。