ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation. (arXiv:2102.06635v4 [cs.LG] UPDATED)

This paper studies the expressive power of artificial neural networks with
rectified linear units. In order to study them as a model of real-valued
computation, we introduce the concept of Max-Affine Arithmetic Programs and
show equivalence between them and neural networks concerning natural complexity
measures. We then use this result to show that two fundamental combinatorial
optimization problems can be solved with polynomial-size neural networks.
First, we show that for any undirected graph with $n$ nodes, there is a neural …

arxiv computation flow networks neural networks polynomial relu