mlsanityData to 7 Oct 2026

Approximation Ratios of Graph Neural Networks for Combinatorial Problems

arXiv 1905.10261 ↗First posted 24 May 2019cs.LG stat.MLcited by 68

Not on the map. Why?

Abstract (arXiv)

In this paper, from a theoretical perspective, we study how powerful graph neural networks (GNNs) can be for learning approximation algorithms for combinatorial problems. To this end, we first establish a new class of GNNs that can solve a strictly wider variety of problems than existing GNNs. Then, we bridge the gap between GNN theory and the theory of distributed local algorithms. We theoretically demonstrate that the most powerful GNN can learn approximation algorithms for the minimum dominating set problem and the minimum vertex cover problem with some approximation ratios with the aid of the theory of distributed local algorithms. We also show that most of the existing GNNs such as GIN, GAT, GCN, and GraphSAGE cannot perform better than with these ratios. This paper is the first to elucidate approximation ratios of GNNs for combinatorial problems. Furthermore, we prove that adding coloring or weak-coloring to each node feature improves these approximation ratios. This indicates that preprocessing and feature engineering theoretically strengthen model capabilities.

Key facts. Cited by 68 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 May 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 17; 2023: 14; 2024: 8; 2025: 6; 2026: 9.

68 papers.

Sort:

  1. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  2. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  3. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  4. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  5. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  6. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  7. 2022Provably expressive temporal graph networkscited by 56
  8. 2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
  9. 2023How does over-squashing affect the power of GNNs?cited by 53
  10. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  11. 2022KerGNNs: Interpretable Graph Neural Networks with Graph Kernelscited by 50
  12. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
38 more
  1. 2022GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generationcited by 43
  2. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  3. 2023Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusioncited by 39
  4. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  5. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  6. 2021Sign Language Translation with Hierarchical Spatio-TemporalGraph Neural Networkcited by 26
  7. 2023Provably Powerful Graph Neural Networks for Directed Multigraphscited by 24
  8. 2022On Representing Mixed-Integer Linear Programs by Graph Neural Networkscited by 23
  9. 2023Going beyond persistent homology using persistent homologycited by 21
  10. 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 21
  11. 2021Bridging the Gap between Spatial and Spectral Domains: A Unified Framework for Graph Neural Networkscited by 18
  12. 2022Going Deeper into Permutation-Sensitive Graph Neural Networkscited by 15
  13. 2021Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problemscited by 13
  14. 2024Rethinking the Capacity of Graph Neural Networks for Branching Strategycited by 12
  15. 2023Are Graph Neural Networks Optimal Approximation Algorithms?cited by 10
  16. 2025Graph neural networks extrapolate out-of-distribution for shortest pathscited by 9
  17. 2023Lumos: Heterogeneity-aware Federated Graph Learning over Decentralized Devicescited by 6
  18. 2023NN-Steiner: A Mixed Neural-algorithmic Approach for the Rectilinear Steiner Minimum Tree Problemcited by 6
  19. 2021Can Graph Neural Networks Learn to Solve MaxSAT Problem?cited by 5
  20. 2022Optimizing Tensor Network Contraction Using Reinforcement Learningcited by 5
  21. 2022Learning Graph Algorithms With Recurrent Graph Neural Networkscited by 5
  22. 2024Training-free Graph Neural Networks and the Power of Labels as Featurescited by 5
  23. 2024Enhancing the Expressivity of Temporal Graph Networks through Source-Target Identificationcited by 5
  24. 2022Two-level Graph Neural Networkcited by 4
  25. 2022Asynchronous Neural Networks for Learning in Graphscited by 4
  26. 2023Graph Neural Networks can Recover the Hidden Features Solely from the Graph Structurecited by 4
  27. 2024A Unified Framework for Combinatorial Optimization Based on Graph Neural Networkscited by 4
  28. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  29. 2025Geometric Algorithms for Neural Combinatorial Optimization with Constraintscited by 4
  30. 2021Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Searchcited by 3
  31. 2022Graph Neural Networks with Precomputed Node Featurescited by 3
  32. 2022A Topological characterisation of Weisfeiler-Leman equivalence classescited by 3
  33. 2023How Graph Neural Networks Learn: Lessons from Training Dynamicscited by 3
  34. 2024Graph Neural Networks and Arithmetic Circuitscited by 3
  35. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  36. 2021Abelian Neural Networkscited by 2
  37. 2024Graph Pruning for Enumeration of Minimal Unsatisfiable Subsetscited by 2
  38. 2021Decentralized Statistical Inference with Unrolled Graph Neural Networkscited by 1

50 most cited of 68 All 68 (JSON)