論文の概要: Graph Neural Networks vs Convolutional Neural Networks for Graph Domination Number Prediction

• arxiv url: http://arxiv.org/abs/2511.18150v1
• Date: Sat, 22 Nov 2025 18:34:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:24.653859
• Title: Graph Neural Networks vs Convolutional Neural Networks for Graph Domination Number Prediction
• Title（参考訳）: グラフ支配数予測のためのグラフニューラルネットワークと畳み込みニューラルネットワーク
• Authors: Randy Davila, Beyzanur Ispir,
• Abstract要約: 本稿では,グラフのエンフェドミネーション数,支配集合の最小サイズを近似する機械学習手法について検討する。 我々は、隣接行列表現で動作する畳み込みニューラルネットワーク(CNN)と、グラフ構造からメッセージパッシングを通じて直接学習するグラフニューラルネットワーク(GNN)の2つのニューラルネットワークパラダイムを比較した。 どちらのモデルも正確な解法よりも大幅にスピードアップし、GNNは200ドル以上の加速を実現し、ほぼ完全な忠実さを維持している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate machine learning approaches to approximating the \emph{domination number} of graphs, the minimum size of a dominating set. Exact computation of this parameter is NP-hard, restricting classical methods to small instances. We compare two neural paradigms: Convolutional Neural Networks (CNNs), which operate on adjacency matrix representations, and Graph Neural Networks (GNNs), which learn directly from graph structure through message passing. Across 2,000 random graphs with up to 64 vertices, GNNs achieve markedly higher accuracy ($R^2=0.987$, MAE $=0.372$) than CNNs ($R^2=0.955$, MAE $=0.500$). Both models offer substantial speedups over exact solvers, with GNNs delivering more than $200\times$ acceleration while retaining near-perfect fidelity. Our results position GNNs as a practical surrogate for combinatorial graph invariants, with implications for scalable graph optimization and mathematical discovery.
• Abstract（参考訳）: 本稿では,グラフの「emph{domination number}」を近似する機械学習手法について検討する。 このパラメータの厳密な計算はNPハードであり、古典的なメソッドを小さなインスタンスに制限する。 我々は、隣接行列表現で動作する畳み込みニューラルネットワーク(CNN)と、グラフ構造からメッセージパッシングを通じて直接学習するグラフニューラルネットワーク(GNN)の2つのニューラルネットワークパラダイムを比較した。 最大64頂点を持つ2000個のランダムグラフに対して、GNNはCNNよりもはるかに高い精度(R^2=0.987$, MAE $=0.372$)を達成する(R^2=0.955$, MAE $=0.500$)。 どちらのモデルも正確な解法よりも大幅にスピードアップし、GNNは200ドル以上の加速を実現し、ほぼ完全な忠実さを維持している。 その結果,GNNを組合せグラフ不変量の実用的なサロゲートとして位置づけ,拡張性のあるグラフ最適化と数学的発見に寄与した。

関連論文リスト

• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。 我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
  論文  参考訳（メタデータ） (2022-10-27T16:00:45Z)
• Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
  ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。 我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
  論文  参考訳（メタデータ） (2021-06-12T07:43:51Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  本稿では,このグラフからBernoulliをサンプリングしたグラフ上でGNNをトレーニングすることで,WNN(Graphon Neural Network)を学習する問題を考察する。 これらの結果から着想を得た大規模グラフ上でGNNを学習するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-07T15:05:59Z)
• A Unified Lottery Ticket Hypothesis for Graph Neural Networks [82.31087406264437]
  本稿では,グラフ隣接行列とモデルの重み付けを同時に行う統一GNNスペーシフィケーション(UGS)フレームワークを提案する。 グラフ宝くじ(GLT)をコアサブデータセットとスパースサブネットワークのペアとして定義することにより、人気のある宝くじチケット仮説を初めてGNNsにさらに一般化します。
  論文  参考訳（メタデータ） (2021-02-12T21:52:43Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Random Features Strengthen Graph Neural Networks [40.60905158071766]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフ学習タスクのための強力な機械学習モデルである。 本稿では,各ノードにランダムな特徴を加えるだけで,GNNが強力になることを示す。 本稿では, グラフ畳み込みネットワーク (GCN) やグラフ同型ネットワーク (GIN) など, 通常のGNNでは解けない様々な問題を, ランダムな特徴の追加によりGNNが解決できることを示す。
  論文  参考訳（メタデータ） (2020-02-08T12:47:29Z)

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

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