論文の概要: Learning-Based Heuristic for Combinatorial Optimization of the Minimum
Dominating Set Problem using Graph Convolutional Networks
- arxiv url: http://arxiv.org/abs/2306.03434v1
- Date: Tue, 6 Jun 2023 06:22:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 17:03:04.222489
- Title: Learning-Based Heuristic for Combinatorial Optimization of the Minimum
Dominating Set Problem using Graph Convolutional Networks
- Title（参考訳）: グラフ畳み込みネットワークを用いた最小支配集合問題の組合せ最適化のための学習ベースヒューリスティック
- Authors: Abihith Kothapalli, Mudassir Shabbir, Xenofon Koutsoukos
- Abstract要約: グラフ $mathcalG=(V, E) の支配集合は、支配集合の外側の頂点集合 $SsubseteqmathcalV setminus S$ の部分集合である。
本稿では,グラフ$畳み込みネットワークを用いた最小支配集合問題に対する学習に基づく新しい解法を提案する。
- 参考スコア（独自算出の注目度）: 1.5469452301122175
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A dominating set of a graph $\mathcal{G=(V, E)}$ is a subset of vertices
$S\subseteq\mathcal{V}$ such that every vertex $v\in \mathcal{V} \setminus S$
outside the dominating set is adjacent to a vertex $u\in S$ within the set. The
minimum dominating set problem seeks to find a dominating set of minimum
cardinality and is a well-established NP-hard combinatorial optimization
problem. We propose a novel learning-based heuristic approach to compute
solutions for the minimum dominating set problem using graph convolutional
networks. We conduct an extensive experimental evaluation of the proposed
method on a combination of randomly generated graphs and real-world graph
datasets. Our results indicate that the proposed learning-based approach can
outperform a classical greedy approximation algorithm. Furthermore, we
demonstrate the generalization capability of the graph convolutional network
across datasets and its ability to scale to graphs of higher order than those
on which it was trained. Finally, we utilize the proposed learning-based
heuristic in an iterative greedy algorithm, achieving state-of-the-art
performance in the computation of dominating sets.
- Abstract（参考訳）: グラフ $\mathcal{G=(V, E)}$ の支配集合は、頂点 $S\subseteq\mathcal{V}$ の部分集合であり、すべての頂点 $v\in \mathcal{V} \setminus S$ が集合内の頂点 $u\in S$ に隣接している。
最小支配集合問題は、最小濃度の支配集合を見つけ、NP-ハード組合せ最適化問題として確立された。
本稿では,グラフ畳み込みネットワークを用いた最小支配集合問題に対する学習に基づく新しいヒューリスティック手法を提案する。
本研究では,ランダムに生成したグラフと実世界のグラフデータセットを組み合わせることで,提案手法の広範な実験的評価を行う。
提案手法は,従来のグリーディ近似アルゴリズムよりも優れていることを示す。
さらに,データセットにまたがるグラフ畳み込みネットワークの一般化能力と,学習したグラフよりも上位のグラフにスケールする能力を示す。
最後に,提案する学習に基づくヒューリスティックを反復欲アルゴリズムで活用し,支配集合の計算において最先端の性能を実現する。
関連論文リスト
- Differentiable Proximal Graph Matching [40.41380102260085]
微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。
アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。
数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
論文 参考訳（メタデータ） (2024-05-26T08:17:13Z) - Bayesian Optimization of Functions over Node Subsets in Graphs [14.670181702535825]
グラフ上での最適化のための新しいフレームワークを提案する。
元のグラフの各$k$-nodeを、新しいグラフのノードにマップします。
人工環境と実環境環境の両方における実験により,提案したBOフレームワークの有効性が示された。
論文 参考訳（メタデータ） (2024-05-24T00:24:55Z) - Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。
まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。
補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
論文 参考訳（メタデータ） (2024-04-24T18:39:18Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Learning Heuristics for the Maximum Clique Enumeration Problem Using Low
Dimensional Representations [0.0]
本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。
本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。
分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
論文 参考訳（メタデータ） (2022-10-30T22:04:32Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。
マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。
本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文 参考訳（メタデータ） (2022-01-25T00:10:03Z) - A deep learning guided memetic framework for graph coloring problems [15.426481600285724]
グラフカラー化のための"古典的"メタヒューリスティックス(classical metaheuristics)の最高のツールと、ディープニューラルネットワークを組み合わせた新しいフレームワークを提案する。
アルゴリズムにおけるディープラーニングの寄与についての研究は、この問題に対するより良い解を得るのに有用な関連パターンを学習することが可能であることを強調している。
論文 参考訳（メタデータ） (2021-09-13T13:17:41Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。
提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
論文 参考訳（メタデータ） (2020-03-30T15:37:50Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳（メタデータ） (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。