論文の概要: Contrastive Neural Algorithmic Reasoning for Graph Coloring

• arxiv url: http://arxiv.org/abs/2606.03923v1
• Date: Tue, 02 Jun 2026 17:14:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-03 22:00:05.207979
• Title: Contrastive Neural Algorithmic Reasoning for Graph Coloring
• Title（参考訳）: グラフカラー化のためのコントラストニューラルアルゴリズム推論
• Authors: Thien Le, Tianyu Zhao, Melanie Weber,
• Abstract要約: 我々は約$k$-coloringについて研究し、そこではモノクロエッジの数を最小限に抑えながら、最大$k$カラーの使用を目標としている。 この問題はグラフ理論の中心であり、スケジューリングや資源割り当てといった分野で応用されている。 我々は,同色ノードの埋め込みが整合する移動可能な色調構造を学習するコントラスト学習フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 12.647416546573588
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph coloring seeks to assigns colors to a graph's nodes so that adjacent nodes receive different colors, using as few colors as possible. Here, we study approximate $k$-coloring, where the goal is to use at most $k$ colors while minimizing the number of monochromatic edges. This problem is central to graph theory and has applications in areas such as scheduling and resource allocation. Recent unsupervised GNN approaches optimize each instance directly, precluding generalization across graph sizes and distributions. We instead propose a contrastive learning framework that learns transferable coloring geometry where the embeddings of same-color nodes align, while adjacent nodes' representations are pushed toward distinct directions. We analyze the resulting population objective over bounded-size graphs. For unit-norm embeddings, we show that its optima have a line-prototype structure: Representations of nodes of the same color collapse to a shared one-dimensional subspace, and edges connect orthogonal subspaces. This geometry yields stationarity conditions in the supervised setting and is preserved by projected subgradient dynamics under a balanced-coloring assumption. In an unnormalized variant, gradient descent has a max-margin bias governed by a quotient-graph hard-margin problem. Experiments on synthetic and real-world graphs show that contrastive GNN encoders generalize effectively and produce low-conflict colorings, matching and sometimes improving on greedy approaches.
• Abstract（参考訳）: グラフ色付けは、グラフのノードに色を割り当てて、隣接するノードができるだけ少ない色を使って異なる色を受け取るようにする。 ここでは,単色エッジの数を最小限に抑えつつ,最大で$k$のカラー化を目標とする,近似的な$k$-coloringについて検討する。 この問題はグラフ理論の中心であり、スケジューリングやリソース割り当てといった分野で応用されている。 最近の教師なしGNNアプローチでは、グラフのサイズや分布の一般化を前提として、各インスタンスを直接最適化している。 そこで我々は,同色ノードの埋め込みが一致し,隣接ノードの表現が異なる方向に向かってプッシュされるような移動可能な色付け幾何学を学習する対照的な学習フレームワークを提案する。 得られた人口目標を有界グラフ上で解析する。 単位ノルム埋め込みに対して、その最適形は線-原型構造を持つことを示す: 同じ色のノードの表現は1次元の共有部分空間に崩壊し、エッジは直交部分空間を連結する。 この幾何学は、教師付き設定における定常条件を導き、バランスの取れた色付けの仮定の下で、投影された下次力学によって保存される。 正規化されていない変種では、勾配降下は商グラフのハードマージン問題によって支配される極大偏差を持つ。 合成および実世界のグラフの実験では、対照的なGNNエンコーダが効果的に一般化し、低コンフリクトな着色、マッチング、時にはグリーディ的なアプローチを改善することが示されている。

関連論文リスト

• Neural Algorithmic Reasoning for Approximate $k$-Coloring with Recursive Warm Starts [5.645823801022895]
  ノードカラー化におけるグラフニューラルネットワーク(GNN)の利用について検討する。 我々は,軽量なグリーディ局所探索アルゴリズムを導入し,暖かいスタートに使用するために$(k-1)-coloringを使用することで,それを改善することを示す。 数値実験により、局所探索アルゴリズムは小さな入力に対して優れているが、GNN$はスケールにおいて優れた性能を示すことが示された。
  論文  参考訳（メタデータ） (2026-01-08T17:28:09Z)
• Improving Graph Neural Networks by Learning Continuous Edge Directions [0.0]
  グラフニューラルネットワーク(GNN)は、従来、非指向グラフ上の拡散に似たメッセージパッシング機構を採用している。 私たちのキーとなる洞察は、ファジィエッジ方向をグラフのエッジに割り当てることです。 ファジィエッジを持つグラフを学習するためのフレームワークとして,Continuous Edge Direction (CoED) GNNを提案する。
  論文  参考訳（メタデータ） (2024-10-18T01:34:35Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。 ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。 合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
  論文  参考訳（メタデータ） (2023-01-07T05:14:45Z)
• Rethinking Graph Neural Networks for the Graph Coloring Problem [14.102597635893083]
  我々は、最先端のGNNがグラフ彩色問題においてあまり成功していないことを観察する。 本稿では,一般的なGNNクラスである集約合成GNN(AC-GNN)に焦点を当てる。 本稿では,任意のAC-GNNが局所着色法であり,局所着色法はスパースランダムグラフ上の局所着色法の限界を探索することによって最適でないことを示す。
  論文  参考訳（メタデータ） (2022-08-15T02:24:26Z)
• Geometric Graph Representation Learning via Maximizing Rate Reduction [73.6044873825311]
  学習ノード表現は、コミュニティ検出やノード分類などのグラフ解析において、さまざまな下流タスクの恩恵を受ける。 教師なしの方法でノード表現を学習するための幾何学グラフ表現学習(G2R)を提案する。 G2R は異なるグループ内のノードを異なる部分空間にマッピングし、各部分空間はコンパクトで異なる部分空間が分散される。
  論文  参考訳（メタデータ） (2022-02-13T07:46:24Z)
• Graph Neural Networks with Feature and Structure Aware Random Walk [7.143879014059894]
  典型的な好適なグラフでは、エッジを指向する可能性があり、エッジをそのまま扱うか、あるいは単純に非指向にするかは、GNNモデルの性能に大きな影響を与える。 そこで我々は,グラフの方向性を適応的に学習するモデルを開発し,ノード間の長距離相関を生かした。
  論文  参考訳（メタデータ） (2021-11-19T08:54:21Z)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  逐次グラフ畳み込みネットワーク(GCN)を用いた新しいプールベースアクティブラーニングフレームワークを提案する。 少数のランダムなサンプル画像がシードラベル付き例であるので、グラフのパラメータを学習してラベル付きノードと非ラベル付きノードを区別する。 我々はGCNの特性を利用してラベル付けされたものと十分に異なる未ラベルの例を選択する。
  論文  参考訳（メタデータ） (2020-06-18T00:55:10Z)

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

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