論文の概要: Rethinking Graph Neural Networks for the Graph Coloring Problem

• arxiv url: http://arxiv.org/abs/2208.06975v1
• Date: Mon, 15 Aug 2022 02:24:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-16 13:07:46.121938
• Title: Rethinking Graph Neural Networks for the Graph Coloring Problem
• Title（参考訳）: グラフカラー化問題に対するグラフニューラルネットワークの再検討
• Authors: Wei Li, Ruxuan Li, Yuzhe Ma, Siu On Chan, David Pan, Bei Yu
• Abstract要約: 我々は、最先端のGNNがグラフ彩色問題においてあまり成功していないことを観察する。 本稿では,一般的なGNNクラスである集約合成GNN(AC-GNN)に焦点を当てる。 本稿では,任意のAC-GNNが局所着色法であり,局所着色法はスパースランダムグラフ上の局所着色法の限界を探索することによって最適でないことを示す。
• 参考スコア（独自算出の注目度）: 14.102597635893083
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph coloring, a classical and critical NP-hard problem, is the problem of assigning connected nodes as different colors as possible. However, we observe that state-of-the-art GNNs are less successful in the graph coloring problem. We analyze the reasons from two perspectives. First, most GNNs fail to generalize the task under homophily to heterophily, i.e., graphs where connected nodes are assigned different colors. Second, GNNs are bounded by the network depth, making them possible to be a local method, which has been demonstrated to be non-optimal in Maximum Independent Set (MIS) problem. In this paper, we focus on the aggregation-combine GNNs (AC-GNNs), a popular class of GNNs. We first define the power of AC-GNNs in the coloring problem as the capability to assign nodes different colors. The definition is different with previous one that is based on the assumption of homophily. We identify node pairs that AC-GNNs fail to discriminate. Furthermore, we show that any AC-GNN is a local coloring method, and any local coloring method is non-optimal by exploring the limits of local methods over sparse random graphs, thereby demonstrating the non-optimality of AC-GNNs due to its local property. We then prove the positive correlation between model depth and its coloring power. Moreover, we discuss the color equivariance of graphs to tackle some practical constraints such as the pre-fixing constraints. Following the discussions above, we summarize a series of rules a series of rules that make a GNN color equivariant and powerful in the coloring problem. Then, we propose a simple AC-GNN variation satisfying these rules. We empirically validate our theoretical findings and demonstrate that our simple model substantially outperforms state-of-the-art heuristic algorithms in both quality and runtime.
• Abstract（参考訳）: グラフカラー化は古典的で批判的なNPハード問題であり、接続ノードをできるだけ異なる色に割り当てる問題である。 しかし,現状のGNNはグラフカラー化問題においてあまり成功していない。 理由を2つの観点から分析する。 まず、ほとんどのgnnはホモフィリーの下でタスクをヘテロフィリー、すなわち接続されたノードが異なる色に割り当てられるグラフに一般化することができない。 第二に、GNNはネットワーク深さによって境界付けられており、最大独立集合(MIS)問題において最適でないことが証明された局所的な方法である。 本稿では,一般的なGNNクラスである集約合成GNN(AC-GNN)に焦点を当てる。 まず,色分け問題におけるAC-GNNのパワーを,ノードに異なる色を割り当てる能力として定義する。 この定義は、ホモフィリーの仮定に基づく以前の定義とは異なる。 我々は、AC-GNNが識別できないノード対を同定する。 さらに,任意のAC-GNNは局所着色法であり,任意の局所着色法はスパースランダムグラフ上の局所手法の限界を探索することにより,その局所特性によるAC-GNNの非最適性を示す。 そして,モデル深度とその彩色力との正の相関を証明した。 さらに,グラフの色同分散について検討し,固定前の制約など実用上の制約に取り組む。 上述の議論に続いて、色問題においてGNN色を不変かつ強力にする一連のルールを要約する。 そして,これらのルールを満たす簡単なAC-GNN変種を提案する。 理論的知見を実証的に検証し、我々の単純なモデルは、品質と実行時の両方で最先端のヒューリスティックアルゴリズムを大幅に上回っていることを示す。

関連論文リスト

• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる 本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。 我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
  論文  参考訳（メタデータ） (2024-05-27T17:52:12Z)
• Implicit Graph Neural Diffusion Networks: Convergence, Generalization, and Over-Smoothing [7.984586585987328]
  Inlicit Graph Neural Networks (GNN)は、グラフ学習問題に対処する上で大きな成功を収めた。 パラメータ化グラフラプラシアン演算子に基づく暗黙グラフ拡散層を設計するための幾何学的枠組みを提案する。 ディリクレエネルギー最小化問題の固定点方程式として, 暗黙のGNN層がどう見えるかを示す。
  論文  参考訳（メタデータ） (2023-08-07T05:22:33Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。 我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
  論文  参考訳（メタデータ） (2022-10-27T16:00:45Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• Transferability Properties of Graph Neural Networks [125.71771240180654]
  グラフニューラルネットワーク(GNN)は、中規模グラフでサポートされているデータから表現を学ぶのに成功している。 適度な大きさのグラフ上でGNNを訓練し、それらを大規模グラフに転送する問題について検討する。 その結果, (i) グラフサイズに応じて転送誤差が減少し, (ii) グラフフィルタは非線型性の散乱挙動によってGNNにおいて緩和されるような転送可能性-識別可能性トレードオフを有することがわかった。
  論文  参考訳（メタデータ） (2021-12-09T00:08:09Z)
• Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
  ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。 我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
  論文  参考訳（メタデータ） (2021-06-12T07:43:51Z)
• On the Universality of Graph Neural Networks on Large Random Graphs [22.720758067273195]
  グラフニューラルネットワーク(GNN)の潜在位置乱数グラフに対する近似能力について検討する。 大きなグラフ極限では、GNNはc-GNNとして知られるある種の連続的なモデルに収束することが知られている。 我々は,c-SGNNが連続限界におけるc-GNNよりも厳格に強力なことを示す。
  論文  参考訳（メタデータ） (2021-05-27T12:52:36Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
  グラフニューラルネットワーク(GNN)は、グラフでサポートされている信号のための情報処理アーキテクチャである。 これらは、個々の層がグラフ畳み込みフィルタのバンクを含む畳み込みニューラルネットワーク(CNN)の一般化である。
  論文  参考訳（メタデータ） (2020-08-04T18:57:36Z)
• Generalization and Representational Limits of Graph Neural Networks [46.20253808402385]
  ローカル情報に完全に依存するグラフニューラルネットワーク(GNN)では,いくつかの重要なグラフ特性を計算できないことを示す。 メッセージパッシングGNNに対する最初のデータ依存一般化境界を提供する。 私たちのバウンダリは、既存のVC次元ベースのGNN保証よりもはるかに厳格で、リカレントニューラルネットワークのRademacherバウンダリと同等です。
  論文  参考訳（メタデータ） (2020-02-14T18:10:14Z)
• Random Features Strengthen Graph Neural Networks [40.60905158071766]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフ学習タスクのための強力な機械学習モデルである。 本稿では,各ノードにランダムな特徴を加えるだけで,GNNが強力になることを示す。 本稿では, グラフ畳み込みネットワーク (GCN) やグラフ同型ネットワーク (GIN) など, 通常のGNNでは解けない様々な問題を, ランダムな特徴の追加によりGNNが解決できることを示す。
  論文  参考訳（メタデータ） (2020-02-08T12:47:29Z)

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

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