論文の概要: Neural Algorithmic Reasoning for Approximate $k$-Coloring with Recursive Warm Starts

• arxiv url: http://arxiv.org/abs/2601.05137v1
• Date: Thu, 08 Jan 2026 17:28:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-09 17:01:53.301969
• Title: Neural Algorithmic Reasoning for Approximate $k$-Coloring with Recursive Warm Starts
• Title（参考訳）: Recursive Warm Startsを用いた近似$k$-Coloringのニューラルネットワーク推論
• Authors: Knut Vanderbush, Melanie Weber,
• Abstract要約: ノードカラー化におけるグラフニューラルネットワーク(GNN)の利用について検討する。 我々は,軽量なグリーディ局所探索アルゴリズムを導入し,暖かいスタートに使用するために$(k-1)-coloringを使用することで,それを改善することを示す。 数値実験により、局所探索アルゴリズムは小さな入力に対して優れているが、GNN$はスケールにおいて優れた性能を示すことが示された。
• 参考スコア（独自算出の注目度）: 5.645823801022895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Node coloring is the task of assigning colors to the nodes of a graph such that no two adjacent nodes have the same color, while using as few colors as possible. It is the most widely studied instance of graph coloring and of central importance in graph theory; major results include the Four Color Theorem and work on the Hadwiger-Nelson Problem. As an abstraction of classical combinatorial optimization tasks, such as scheduling and resource allocation, it is also rich in practical applications. Here, we focus on a relaxed version, approximate $k$-coloring, which is the task of assigning at most $k$ colors to the nodes of a graph such that the number of edges whose vertices have the same color is approximately minimized. While classical approaches leverage mathematical programming or SAT solvers, recent studies have explored the use of machine learning. We follow this route and explore the use of graph neural networks (GNNs) for node coloring. We first present an optimized differentiable algorithm that improves a prior approach by Schuetz et al. with orthogonal node feature initialization and a loss function that penalizes conflicting edges more heavily when their endpoints have higher degree; the latter inspired by the classical result that a graph is $k$-colorable if and only if its $k$-core is $k$-colorable. Next, we introduce a lightweight greedy local search algorithm and show that it may be improved by recursively computing a $(k-1)$-coloring to use as a warm start. We then show that applying such recursive warm starts to the GNN approach leads to further improvements. Numerical experiments on a range of different graph structures show that while the local search algorithms perform best on small inputs, the GNN exhibits superior performance at scale. The recursive warm start may be of independent interest beyond graph coloring for local search methods for combinatorial optimization.
• Abstract（参考訳）: ノードカラー化は、グラフのノードに色を割り当てて、2つの隣接ノードが同じ色を持たないようにし、可能な限り少ない色を使用するタスクである。 これはグラフの着色とグラフ理論における中心的な重要性の最も広く研究されている例であり、主な結果は四色定理やハドヴィガー・ネルソン問題の研究である。 スケジューリングやリソース割り当てといった古典的な組合せ最適化タスクの抽象化として、実用的な応用にも富んでいる。 ここでは、グラフのノードに最大$k$色を割り当てるタスクである$k$-coloring(近似$k$-coloring)という緩和版に焦点を当て、頂点が同じ色を持つエッジの数がほぼ最小となるようにした。 古典的なアプローチは数学的プログラミングやSATソルバを利用するが、最近の研究では機械学習の利用について検討されている。 この経路に従い、ノードカラー化におけるグラフニューラルネットワーク(GNN)の利用について検討する。 まず、直交ノード特徴の初期化と、エンドポイントが高次であるときに競合するエッジをより過度にペナルティ化するロス関数による、Schuetzらによる事前アプローチを改善する最適化可能な微分可能アルゴリズムを提案する。 次に, 軽量な局所探索アルゴリズムを導入し, ウォームスタートに使用するために$(k-1)$-coloringを再帰的に計算することで, 改善できることを示す。 そして、このような再帰的なウォームスタートをGNNアプローチに適用すると、さらなる改善がもたらされることを示す。 様々なグラフ構造に関する数値実験により、局所探索アルゴリズムは小さな入力に対して優れた性能を示す一方、GNNは大規模に優れた性能を示すことが示された。 再帰的なウォームスタートは、組合せ最適化のための局所探索方法のグラフカラー化以外にも、独立した関心を持つかもしれない。

関連論文リスト

• Efficient hybrid variational quantum algorithm for solving graph coloring problem [4.4739537033766705]
  本稿では,グラフ頂点の$k$-coloring問題を解くために,ハイブリッド変分量子アルゴリズムを提案する。 フィードバック修正とコンフリクト解決を統合した階層的なフレームワークを使用して、$k$-coloringを実現しています。 提案手法を用いて、地下鉄の交通ネットワークのスケジューリングを最適化し、高い公平性を実証する。
  論文  参考訳（メタデータ） (2025-04-30T05:45:15Z)
• Node Classification and Search on the Rubik's Cube Graph with GNNs [55.2480439325792]
  本研究では3x3x3ルービックのルービック問題を解くための深部幾何学モデルの応用に焦点を当てた。 まず、立方体のグラフ表現と距離をモデルの最適化目的として定義することから始める。 距離近似タスクはノード分類問題として再構成され、グラフニューラルネットワーク(GNN)を用いて効果的に処理される。
  論文  参考訳（メタデータ） (2025-01-30T18:52:43Z)
• Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs [0.0]
  本稿では,特に大規模グラフにおいて,グラフニューラルネットワークを有効活用する新しいアルゴリズムを提案する。 本稿では,Erdos-Renyiグラフのデータセット上での手法の有効性を実証し,その適用性を示す。
  論文  参考訳（メタデータ） (2024-08-02T18:02:51Z)
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race [4.416484585765029]
  Weisfeiler-Lemanアルゴリズムは、グラフ学習には基本的であり、グラフカーネルやグラフニューラルネットワークの成功には中心となる。 本研究では, 着色速度を緩やかに収束させることができる, 漸進的な地区改良のための枠組みを提案する。 提案手法は,既存のグラフカーネルの新しい変種を導出し,最適割り当てによるグラフ編集距離を近似するために用いられる。
  論文  参考訳（メタデータ） (2022-09-19T14:37:35Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  本研究では,各ノードの階層的近傍をシーケンスに変換するためにNeighbor2Seqを提案する。 1100万以上のノードと160億のエッジを持つ大規模グラフ上で,本手法の評価を行った。 その結果,提案手法は大規模グラフに対してスケーラブルであり,大規模グラフと中規模グラフにまたがる優れた性能を実現する。
  論文  参考訳（メタデータ） (2022-02-07T16:38:36Z)
• A deep learning guided memetic framework for graph coloring problems [15.426481600285724]
  グラフカラー化のための"古典的"メタヒューリスティックス(classical metaheuristics)の最高のツールと、ディープニューラルネットワークを組み合わせた新しいフレームワークを提案する。 アルゴリズムにおけるディープラーニングの寄与についての研究は、この問題に対するより良い解を得るのに有用な関連パターンを学習することが可能であることを強調している。
  論文  参考訳（メタデータ） (2021-09-13T13:17:41Z)
• Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem [15.45783225341009]
  エッジを現在のグラフに追加する動的設定について検討する。 次に、ランダム化された検索の予測時間を分析し、高品質な解を再計算する。
  論文  参考訳（メタデータ） (2021-05-26T13:00:31Z)
• 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)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  逐次グラフ畳み込みネットワーク(GCN)を用いた新しいプールベースアクティブラーニングフレームワークを提案する。 少数のランダムなサンプル画像がシードラベル付き例であるので、グラフのパラメータを学習してラベル付きノードと非ラベル付きノードを区別する。 我々はGCNの特性を利用してラベル付けされたものと十分に異なる未ラベルの例を選択する。
  論文  参考訳（メタデータ） (2020-06-18T00:55:10Z)

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

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