Graph Neural Networks vs Convolutional Neural Networks for Graph Domination Number Prediction
This provides a practical surrogate for combinatorial graph invariants, aiding scalable graph optimization and mathematical discovery, though it is incremental as it compares existing methods on a known problem.
The paper tackled the problem of approximating the domination number of graphs, an NP-hard task, by comparing Graph Neural Networks (GNNs) and Convolutional Neural Networks (CNNs), with GNNs achieving higher accuracy (R²=0.987, MAE=0.372) and over 200× speedup over exact solvers.
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.