論文の概要: Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs

• arxiv url: http://arxiv.org/abs/2408.01503v1
• Date: Fri, 2 Aug 2024 18:02:51 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-06 19:49:47.546404
• Title: Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs
• Title（参考訳）: ニューラルネットワークによる効率的なグラフ色付け:大規模グラフに対する物理に着想を得たアプローチ
• Authors: Lorenzo Colantonio, Andrea Cacioppo, Federico Scarpati, Stefano Giagu,
• Abstract要約: 本稿では,特に大規模グラフにおいて,グラフニューラルネットワークを有効活用する新しいアルゴリズムを提案する。 本稿では,Erdos-Renyiグラフのデータセット上での手法の有効性を実証し,その適用性を示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The graph coloring problem is an optimization problem involving the assignment of one of q colors to each vertex of a graph such that no two adjacent vertices share the same color. This problem is NP-hard and arises in various practical applications. In this work, we present a novel algorithm that leverages graph neural networks to tackle the problem efficiently, particularly for large graphs. We propose a physics-inspired approach that leverages tools used in statistical mechanics to improve the training and performance of the algorithm. The scaling of our method is evaluated for different connectivities and graph sizes. Finally, we demonstrate the effectiveness of our method on a dataset of Erdos-Renyi graphs, showing its applicability also in hard-to-solve connectivity regions where traditional methods struggle.
• Abstract（参考訳）: グラフ着色問題は、隣接する2つの頂点が同じ色を共有することのないグラフの各頂点にq色の1つを割り当てることを含む最適化問題である。 この問題はNPハードであり、様々な応用に現れる。 本研究では,特に大規模グラフにおいて,グラフニューラルネットワークを有効活用する新しいアルゴリズムを提案する。 本稿では、統計力学で使用されるツールを活用して、アルゴリズムのトレーニングと性能を向上させる物理に着想を得た手法を提案する。 本手法のスケーリングは,異なる接続性およびグラフサイズに対して評価される。 最後に,Erdos-Renyiグラフのデータセット上での本手法の有効性を実証し,従来の手法が難解な接続領域においても適用可能であることを示す。

関連論文リスト

• Fast Semi-supervised Learning on Large Graphs: An Improved Green-function Method [93.04936336359502]
  グラフに基づく半教師付き学習において、グリーン関数法はグラフ空間におけるグリーン関数の計算によって機能する古典的な方法である。 そこで本研究では,最適化の観点から詳細な解析を行い,新しい手法を提案する。 従来の手法とは異なり,改良手法ではガウス除去法とアンコレッドグラフ法という2つの高速化手法を適用できる。
  論文  参考訳（メタデータ） (2024-11-04T04:27:18Z)
• 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 Graph Neural Network with Negative Message Passing for Graph Coloring [12.501032566933178]
  本稿では,グラフカラー化のためのグラフネットワークモデルを提案する。 我々は,より効果的な情報交換を行うために,提案したグラフニューラルネットワークに負のメッセージパッシングを導入する。 ノードの自己情報を考慮した新たな損失関数が提案され,学習プロセスが促進される。
  論文  参考訳（メタデータ） (2023-01-26T15:08:42Z)
• Graph Coloring with Physics-Inspired Graph Neural Networks [0.0]
  正準グラフ着色問題の解法としてグラフニューラルネットワークを用いる方法を示す。 マルチクラスノード分類問題としてグラフカラー化を行い,教師なし学習戦略を利用する。
  論文  参考訳（メタデータ） (2022-02-03T14:24:12Z)
• 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)
• Graph Coarsening with Neural Networks [8.407217618651536]
  本稿では、粗いアルゴリズムの品質を測定するためのフレームワークを提案し、目標に応じて、粗いグラフ上のLaplace演算子を慎重に選択する必要があることを示す。 粗いグラフに対する現在のエッジウェイト選択が準最適である可能性が示唆され、グラフニューラルネットワークを用いて重み付けマップをパラメータ化し、教師なし方法で粗い品質を改善するよう訓練する。
  論文  参考訳（メタデータ） (2021-02-02T06:50:07Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
  グラフ埋め込みは、高次元および非ユークリッド特徴空間でデータ構造を変換しエンコードする方法である。 CensNetは一般的なグラフ埋め込みフレームワークで、ノードとエッジの両方を潜在機能空間に埋め込む。 提案手法は,4つのグラフ学習課題における最先端のパフォーマンスを達成または一致させる。
  論文  参考訳（メタデータ） (2020-10-25T22:39:31Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Second-Order Pooling for Graph Neural Networks [62.13156203025818]
  グラフプーリングとして2次プールを提案するが、これは上記の課題を自然に解決する。 グラフニューラルネットワークによる2次プールの直接利用は、実用的な問題を引き起こすことを示す。 本稿では,2次プールに基づく2つの新しいグローバルグラフプーリング手法,すなわちバイリニアマッピングと2次プールを提案する。
  論文  参考訳（メタデータ） (2020-07-20T20:52:36Z)

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

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