論文の概要: Predicting The Cop Number Using Machine Learning

• arxiv url: http://arxiv.org/abs/2602.16600v1
• Date: Wed, 18 Feb 2026 16:52:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-19 15:58:30.655205
• Title: Predicting The Cop Number Using Machine Learning
• Title（参考訳）: 機械学習によるコップ数予測
• Authors: Meagan Mann, Christian Muise, Erin Meger,
• Abstract要約: グラフのコピー番号$c(G)$は、強盗の捕獲を保証するのに必要な最小の警官数として定義される。 本稿では,機械学習手法とグラフニューラルネットワークがグラフのコーパス数をその構造特性から正確に予測できるかどうかを考察する。
• 参考スコア（独自算出の注目度）: 6.865656740940774
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Cops and Robbers is a pursuit evasion game played on a graph, first introduced independently by Quilliot \cite{quilliot1978jeux} and Nowakowski and Winkler \cite{NOWAKOWSKI1983235} over four decades ago. A main interest in recent the literature is identifying the cop number of graph families. The cop number of a graph, $c(G)$, is defined as the minimum number of cops required to guarantee capture of the robber. Determining the cop number is computationally difficult and exact algorithms for this are typically restricted to small graph families. This paper investigates whether classical machine learning methods and graph neural networks can accurately predict a graph's cop number from its structural properties and identify which properties most strongly influence this prediction. Of the classical machine learning models, tree-based models achieve high accuracy in prediction despite class imbalance, whereas graph neural networks achieve comparable results without explicit feature engineering. The interpretability analysis shows that the most predictive features are related to node connectivity, clustering, clique structure, and width parameters, which aligns with known theoretical results. Our findings suggest that machine learning approaches can be used in complement with existing cop number algorithms by offering scalable approximations where computation is infeasible.
• Abstract（参考訳）: Cops and Robbers は、Quilliot \cite{quilliot 1978jeux} と Nowakowski と Winkler \cite{NOWAKOWSKI 1983235} によって40年以上前に独立に導入されたグラフ上の追跡回避ゲームである。 最近の文献の主な関心は、グラフファミリーのパトロール数を特定することである。 グラフの警官番号$c(G)$は、強盗の捕獲を保証するのに必要な最小の警官数として定義される。 警官数の決定は計算的に困難であり、これに対する正確なアルゴリズムは通常、小さなグラフファミリに制限される。 本稿では,従来の機械学習手法とグラフニューラルネットワークが,グラフのコーパス数をその構造特性から正確に予測し,どの特性がこの予測に最も強く影響するかを明らかにする。 古典的な機械学習モデルでは、木ベースのモデルはクラス不均衡にもかかわらず予測の精度が高いが、グラフニューラルネットワークは明示的な特徴工学なしで同等の結果が得られる。 解釈可能性分析は、最も予測可能な特徴は、既知の理論的結果と一致するノード接続、クラスタリング、斜め構造、幅パラメータに関連することを示している。 この結果から,計算が不可能なスケーラブルな近似を提供することにより,既存のコーパス数アルゴリズムを補完する機械学習手法が利用可能であることが示唆された。

関連論文リスト

• Exact Subgraph Isomorphism Network for Predictive Graph Mining [6.926467730065948]
  本稿では,厳密なサブグラフ列挙,ニューラルネットワーク,スパース正規化を組み合わせたエクササイズサブグラフ同型ネットワーク(EIN)を提案する。 EINは、標準的なグラフニューラルネットワークモデルと比較して十分に高い予測性能を持つ。
  論文  参考訳（メタデータ） (2025-09-25T23:49:26Z)
• Two Birds with One Stone: Enhancing Uncertainty Quantification and Interpretability with Graph Functional Neural Process [27.760002432327962]
  グラフニューラルネットワーク(GNN)は、グラフデータに強力なツールである。 しかし、それらの予測は誤校正され、解釈性に欠ける。 本稿では,新しい不確実性と解釈可能なグラフ分類モデルを提案する。
  論文  参考訳（メタデータ） (2025-08-23T17:48:05Z)
• Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs [49.547988001231424]
  効率的かつ適応的な予測を実現するために,ワンショットサブグラフリンク予測を提案する。 設計原理は、KG全体に直接作用する代わりに、予測手順を2つのステップに分離する。 5つの大規模ベンチマークにおいて,効率の向上と性能の向上を実現している。
  論文  参考訳（メタデータ） (2024-03-15T12:00:12Z)
• Generative Graph Neural Networks for Link Prediction [13.643916060589463]
  欠落したリンクを推測したり、観測されたグラフに基づいて急激なリンクを検出することは、グラフデータ分析における長年の課題である。 本稿では,GraphLPと呼ばれるネットワーク再構成理論に基づく,新しい,根本的に異なるリンク予測アルゴリズムを提案する。 リンク予測に使用される識別ニューラルネットワークモデルとは異なり、GraphLPは生成可能であり、ニューラルネットワークベースのリンク予測の新しいパラダイムを提供する。
  論文  参考訳（メタデータ） (2022-12-31T10:07:19Z)
• Privacy-Preserved Neural Graph Similarity Learning [99.78599103903777]
  本稿では,グラフ類似性学習のためのプライバシ保存型ニューラルグラフマッチングネットワークモデルPPGMを提案する。 再構成攻撃を防ぐため、提案モデルではデバイス間でノードレベルの表現を通信しない。 グラフプロパティに対する攻撃を軽減するため、両方のベクトルの情報を含む難読化機能は通信される。
  論文  参考訳（メタデータ） (2022-10-21T04:38:25Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  サブグラフマッチングは、グラフデータベース検索、バイオメディカル分析、ソーシャルグループ検索などにおける中核的な操作である。 本稿では,クエリと対象グラフのマッチング情報を動的に計算する,新しいエンコーダ・デコーダニューラルネットワークアーキテクチャを提案する。 5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
  論文  参考訳（メタデータ） (2022-07-21T04:47:21Z)
• Reinforced Causal Explainer for Graph Neural Networks [112.57265240212001]
  グラフニューラルネットワーク(GNN)の探索には説明可能性が不可欠である 我々は強化学習エージェントReinforced Causal Explainer (RC-Explainer)を提案する。 RC-Explainerは忠実で簡潔な説明を生成し、グラフを見えなくするより優れたパワーを持つ。
  論文  参考訳（メタデータ） (2022-04-23T09:13:25Z)
• Neighborhood Random Walk Graph Sampling for Regularized Bayesian Graph Convolutional Neural Networks [0.6236890292833384]
  本稿では,近隣ランダムウォークサンプリング(BGCN-NRWS)を用いたベイジアングラフ畳み込みネットワーク(Bayesian Graph Convolutional Network)を提案する。 BGCN-NRWSは、グラフ構造を利用したマルコフ・チェイン・モンテカルロ(MCMC)に基づくグラフサンプリングアルゴリズムを使用し、変分推論層を用いてオーバーフィッティングを低減し、半教師付きノード分類における最先端と比較して一貫して競合する分類結果を得る。
  論文  参考訳（メタデータ） (2021-12-14T20:58:27Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)

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

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