論文の概要: Experiments with graph convolutional networks for solving the vertex $p$-center problem

• arxiv url: http://arxiv.org/abs/2106.00357v1
• Date: Tue, 1 Jun 2021 10:06:31 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-02 21:41:16.245308
• Title: Experiments with graph convolutional networks for solving the vertex $p$-center problem
• Title（参考訳）: 頂点$p$-center問題の解法のためのグラフ畳み込みネットワークによる実験
• Authors: Elisabeth Gaar and Markus Sinnl
• Abstract要約: グラフ畳み込みネットワーク(GCN)は、グラフ上に定義されたNPハード最適化問題(COP)に取り組むために、機械学習コミュニティで人気のある研究方向となっている。 本稿では, 頂点p-center問題(PCP)の解法としてGCNを用いた予備的検討を行う。 得られた予備結果は,ネットワークアーキテクチャのアイデアの直接転送があまりうまくいかないことを示している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the last few years, graph convolutional networks (GCN) have become a popular research direction in the machine learning community to tackle NP-hard combinatorial optimization problems (COPs) defined on graphs. While the obtained results are usually still not competitive with problem-specific solution approaches from the operations research community, GCNs often lead to improvements compared to previous machine learning approaches for classical COPs such as the traveling salesperson problem (TSP). In this work we present a preliminary study on using GCNs for solving the vertex p-center problem (PCP), which is another classic COP on graphs. In particular, we investigate whether a successful model based on end-to-end training for the TSP can be adapted to a PCP, which is defined on a similar 2D Euclidean graph input as the usually used version of the TSP. However, the objective of the PCP has a min-max structure which could lead to many symmetric optimal, i.e., ground-truth solutions and other potential difficulties for learning. Our obtained preliminary results show that indeed a direct transfer of network architecture ideas does not seem to work too well. Thus we think that the PCP could be an interesting benchmark problem for new ideas and developments in the area of GCNs.
• Abstract（参考訳）: 過去数年間、グラフ畳み込みネットワーク(gcn)は、グラフ上で定義されたnp-hard combinatorial optimization problem(cops)に取り組むために、機械学習コミュニティで人気のある研究方向となっている。 得られた結果は、通常、オペレーションリサーチコミュニティの問題解決アプローチと競合しないが、GCNは、トラベルセールスパーソン問題(TSP)のような古典的なCOPに対する以前の機械学習アプローチと比べて改善されることが多い。 本稿では,グラフ上の別の古典的COPである頂点p中心問題(PCP)の解法としてGCNを用いた予備的検討を行う。 特に、TSPのエンド・ツー・エンドトレーニングに基づくモデルが、同様の2次元ユークリッドグラフ入力に基づいてTSPの通常使われるバージョンとして定義されたPCPに適応できるかどうかを検討する。 しかし、PCP の目的は min-max 構造であり、多くの対称最適解、すなわち、接地トラス解や学習の潜在的な困難をもたらす可能性がある。 得られた予備結果は,ネットワークアーキテクチャのアイデアの直接転送があまりうまくいかないことを示している。 したがって、我々はPCPがGCNの領域における新しいアイデアや開発のための興味深いベンチマーク問題になり得ると考えている。

関連論文リスト

• Quantum Annealing and Graph Neural Networks for Solving TSP with QUBO [0.0]
  本稿では、量子アニーリングアルゴリズムとグラフニューラルネットワークによるトラベリングセールスマン問題(TSP)の解法として、二次非拘束バイナリ最適化(QUBO)モデルの適用について検討する。 TSP(QGNN-TSP)のためのグラフニューラルネットワークソリューションを導入し、問題の基盤構造を学習し、QUBOに基づく損失関数の勾配降下による競合ソリューションを生成する。
  論文  参考訳（メタデータ） (2024-02-21T05:55:00Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning [59.14935871979047]
  本研究は, 深層強化学習(DRL)を用いた優先制約付きトラベリングセールスパーソン問題(TSPPC)の解を提案する。 これらのアプローチに共通しているのは、マルチヘッドアテンション層に基づくグラフモデルの利用である。
  論文  参考訳（メタデータ） (2022-07-04T14:31:47Z)
• GLAN: A Graph-based Linear Assignment Network [29.788755291070462]
  深層グラフネットワークに基づく学習可能な線形代入問題の解法を提案する。 合成データセットによる実験結果から,本手法は最先端のベースラインよりも優れていることがわかった。 また,提案手法を一般的なマルチオブジェクトトラッキング(MOT)フレームワークに組み込んで,エンド・ツー・エンドでトラッカーをトレーニングする。
  論文  参考訳（メタデータ） (2022-01-05T13:18:02Z)
• Feature Importance-aware Graph Attention Network and Dueling Double Deep Q-Network Combined Approach for Critical Node Detection Problems [61.48763653120301]
  クリティカルノード問題(Critical Node Problem, CNP)は、ネットワークから重要なノードの集合を見つけることを目的とした問題である。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• Graph Partner Neural Networks for Semi-Supervised Learning on Graphs [16.489177915147785]
  グラフ畳み込みネットワーク(GCN)は、グラフ構造化データを処理するのに強力であり、ノード分類、リンク予測、グラフ分類などのタスクで最先端のパフォーマンスを達成した。 グラフ畳み込み処理を繰り返した後にノードの表現が区別できない傾向にあるため、深いGCNが過度に滑らかな問題に悩まされることは避けられない。 本稿では,非パラメータ化GCNとパラメータ共有スキームを組み合わせたグラフパートナーニューラルネットワーク(GPNN)を提案する。
  論文  参考訳（メタデータ） (2021-10-18T10:56:56Z)
• Revisiting Graph Convolutional Network on Semi-Supervised Node Classification from an Optimization Perspective [10.178145000390671]
  グラフ畳み込みネットワーク(GCN)は、様々なグラフベースのタスクにおいて有望な性能を達成した。 しかし、より多くのレイヤを積み重ねる際には、過剰なスムーシングに悩まされる。 本稿では,この観測を定量的に研究し,より深いGCNに対する新たな洞察を開拓する。
  論文  参考訳（メタデータ） (2020-09-24T03:36:43Z)
• Simple and Deep Graph Convolutional Networks [63.76221532439285]
  グラフ畳み込みネットワーク(GCN)は、グラフ構造化データに対する強力なディープラーニングアプローチである。 その成功にもかかわらず、現在のGCNモデルは、エムの過度に滑らかな問題のため、ほとんどが浅くなっている。 本稿では,2つの単純かつ効果的な手法を用いて,バニラGCNモデルを拡張したGCNIIを提案する。
  論文  参考訳（メタデータ） (2020-07-04T16:18:06Z)
• Infinitely Wide Graph Convolutional Networks: Semi-supervised Learning via Gaussian Processes [144.6048446370369]
  グラフ畳み込みニューラルネットワーク(GCN)は近年,グラフに基づく半教師付き半教師付き分類において有望な結果を示した。 グラフに基づく半教師付き学習のためのGCN(GPGC)を用いたGP回帰モデルを提案する。 GPGCを評価するための広範囲な実験を行い、他の最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-02-26T10:02:32Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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