It's known that many problems (e.g. XOR) have the exact solutions represented by neural networks. The question is: *What kind of graph theory problems can be solved using neural networks*?



Solving graph theory problems using neural networks
Here is an example that has found a real-world application, in the context of [quantum error correction:](https://en.wikipedia.org/wiki/Quantum_error_correction) The decoding of [stabilizer codes](https://en.wikipedia.org/wiki/Stabilizer_code) is a problem of minimum weight-perfect matching on a [graph](https://en.wikipedia.org/wiki/Blossom_algorithm) (for the surface code or [toric code](https://en.wikipedia.org/wiki/Toric_code)) or a [hypergraph](https://en.wikipedia.org/wiki/3-dimensional_matching) (for the [color code](https://physics.stackexchange.com/questions/169176/quantum-error-correction-surface-code-vs-color-code)). [Recurrent neural networks](https://en.wikipedia.org/wiki/Recurrent_neural_network) offer a performance that is comparable or better than existing algorithms. Some pointers to the literature:


* [A neural decoder for
topological codes](https://arxiv.org/abs/1610.04238)
* [Decoding small surface codes
with feedforward neural networks](https://arxiv.org/abs/1705.00857)
* [Machine-learning-assisted correction of correlated qubit errors in a topological code](https://arxiv.org/abs/1705.07855)
* [Deep neural
network probabilistic decoder for stabilizer codes](https://arxiv.org/abs/1705.09334)


