論文の概要: A deep learning guided memetic framework for graph coloring problems

• arxiv url: http://arxiv.org/abs/2109.05948v1
• Date: Mon, 13 Sep 2021 13:17:41 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-14 22:47:59.274037
• Title: A deep learning guided memetic framework for graph coloring problems
• Title（参考訳）: グラフカラー化問題のための深層学習誘導型memeticフレームワーク
• Authors: Olivier Goudet, Cyril Grelier and Jin-Kao Hao
• Abstract要約: グラフカラー化のための"古典的"メタヒューリスティックス(classical metaheuristics)の最高のツールと、ディープニューラルネットワークを組み合わせた新しいフレームワークを提案する。 アルゴリズムにおけるディープラーニングの寄与についての研究は、この問題に対するより良い解を得るのに有用な関連パターンを学習することが可能であることを強調している。
• 参考スコア（独自算出の注目度）: 15.426481600285724
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given an undirected graph $G=(V,E)$ with a set of vertices $V$ and a set of edges $E$, a graph coloring problem involves finding a partition of the vertices into different independent sets. In this paper we present a new framework which combines a deep neural network with the best tools of "classical" metaheuristics for graph coloring. The proposed algorithm is evaluated on the weighted graph coloring problem and computational results show that the proposed approach allows to obtain new upper bounds for medium and large graphs. A study of the contribution of deep learning in the algorithm highlights that it is possible to learn relevant patterns useful to obtain better solutions to this problem.
• Abstract（参考訳）: 有向グラフ $G=(V,E)$ と頂点の集合 $V$ と辺の集合 $E$ が与えられたとき、グラフ彩色問題は、頂点の異なる独立集合への分割を見つけることである。 本稿では,グラフカラー化のための「古典的」メタヒューリスティクスの優れたツールと,ディープニューラルネットワークを組み合わせた新しいフレームワークを提案する。 提案アルゴリズムは重み付きグラフ着色問題に基づいて評価され,計算結果から,提案手法が中大グラフの新たな上界の獲得を可能にすることが示された。 アルゴリズムにおけるディープラーニングの寄与についての研究は、この問題に対するより良い解を得るのに有用な関連パターンを学習できることを強調している。

関連論文リスト

• Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs [0.0]
  本稿では,特に大規模グラフにおいて,グラフニューラルネットワークを有効活用する新しいアルゴリズムを提案する。 本稿では,Erdos-Renyiグラフのデータセット上での手法の有効性を実証し,その適用性を示す。
  論文  参考訳（メタデータ） (2024-08-02T18:02:51Z)
• Learning-Based Heuristic for Combinatorial Optimization of the Minimum Dominating Set Problem using Graph Convolutional Networks [1.5469452301122175]
  グラフ $mathcalG=(V, E) の支配集合は、支配集合の外側の頂点集合 $SsubseteqmathcalV setminus S$ の部分集合である。 本稿では,グラフ$畳み込みネットワークを用いた最小支配集合問題に対する学習に基づく新しい解法を提案する。
  論文  参考訳（メタデータ） (2023-06-06T06:22:42Z)
• Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks [5.620334754517149]
  本稿では,グラフカラー化の競争的構築を見つけるために,深層強化学習が有効かどうかを検討する。 提案手法であるReLColでは,深層Q-ラーニングとグラフニューラルネットワークを用いて特徴抽出を行う。 グラフカラー化問題のさらなる研究には,強化学習が有望な方向であることを実証する。
  論文  参考訳（メタデータ） (2023-04-08T15:41:01Z)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。 提案手法は,複数のMOTデータセット上での最先端性能を実現する。 画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
  論文  参考訳（メタデータ） (2023-03-27T17:39:00Z)
• A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource [87.7460720701592]
  本稿では, この分野における公式定義, 評価, 開発について紹介する。 ディープグラフクラスタリング手法の分類は,グラフタイプ,ネットワークアーキテクチャ,学習パラダイム,クラスタリング手法など,4つの異なる基準に基づいて提示される。 コンピュータビジョン、自然言語処理、レコメンデーションシステム、ソーシャルネットワーク分析、バイオインフォマティクス、医学を含む6分野におけるディープグラフクラスタリング手法の適用について述べる。
  論文  参考訳（メタデータ） (2022-11-23T11:31:11Z)
• Graph Coloring with Physics-Inspired Graph Neural Networks [0.0]
  正準グラフ着色問題の解法としてグラフニューラルネットワークを用いる方法を示す。 マルチクラスノード分類問題としてグラフカラー化を行い,教師なし学習戦略を利用する。
  論文  参考訳（メタデータ） (2022-02-03T14:24:12Z)
• Learning Combinatorial Node Labeling Algorithms [8.687178298010968]
  強化学習を用いてグラフカラー化を学習するグラフニューラルネットワークを提案する。 我々の学習した決定論は古典的な次数に基づく欲求よりも優れた解を与える。
  論文  参考訳（メタデータ） (2021-06-07T13:21:09Z)
• 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)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)

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

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