# Graph Neural Networks vs Convolutional Neural Networks for Graph Domination Number Prediction

arXiv: https://arxiv.org/abs/2511.18150 · HTML: https://mlsanity.com/paper/2511.18150/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 18 references that are in the map.
- First posted on arXiv 22 Nov 2025.

## Builds on (most cited first, 8 of 8)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Estimating the stability number of a random graph using convolutional neural networks](https://mlsanity.com/paper/2407.07827/) (2024)

## Abstract (arXiv)

We investigate machine learning approaches to approximating the 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 (R2=0.987, MAE =0.372) than CNNs (R2=0.955, MAE =0.500). Both models offer substantial speedups over exact solvers, with GNNs delivering more than 200× 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.