用机器学习预测图的抓人者数量，高效且可解释。
Predicting The Cop Number Using Machine Learning
- 用树模型和图神经网络从图结构预测抓人者数
- 树模型在类别不平衡下仍达高精度，图神经网络无需人工特征工程
- 关键影响因素为节点连通性、聚类和团结构，适合图算法研究者
Cops and Robbers 是一个在图上进行的追逐逃逸游戏，最早由 Quilliot 与 Nowakowski-Winkler 在四十年前独立提出。近年来研究重点是确定各类图的抓人者数（cop number）。抓人者数 $c(G)$ 指保证能捕获逃犯所需的最少警力数。精确计算该值在计算上困难，现有算法通常仅适用于小规模图族。本文探讨经典机器学习方法与图神经网络能否基于图的结构属性准确预测其抓人者数，并识别影响最大的属性。实验表明，树模型在存在类别不平衡时仍具高预测精度，图神经网络则无需显式特征工程即可达到类似效果。可解释性分析显示，最具预测性的特征与节点连通性、聚类、团结构及宽度参数相关，符合已有理论结果。研究结果表明，机器学习可作为现有算法的补充，在计算不可行时提供可扩展的近似解。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。