用图神经网络预测图的支配数，精度远超传统卷积网络。
Graph Neural Networks vs Convolutional Neural Networks for Graph Domination Number Prediction
- 直接基于图结构消息传递，无需矩阵表示
- GNN在64顶点图上准确率高达98.7%（MAE=0.372）
- 适合需要快速估算图优化参数的研究者
我们研究了机器学习方法对图的支配数（最小支配集大小）的近似计算。该参数精确求解为NP难问题，限制了经典方法在大规模图上的应用。对比两种神经网络范式：基于邻接矩阵的卷积神经网络（CNNs）与直接从图结构学习的消息传递图神经网络（GNNs）。在2000个最多64个顶点的随机图上，GNNs表现显著优于CNNs（R²=0.987，MAE=0.372 vs R²=0.955，MAE=0.500）。两者均大幅超越精确求解器，其中GNNs实现超过200倍加速，同时保持近乎完美的保真度。结果表明GNNs可作为组合图不变量的实用代理，对可扩展图优化和数学发现具有重要意义。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。