  We perform a massive evaluation of neural networks with architectures
corresponding to random graphs of various types. We investigate various
structural and numerical properties of the graphs in relation to neural network
test accuracy. We find that none of the classical numerical graph invariants by
itself allows to single out the best networks. Consequently, we introduce a new
numerical graph characteristic that selects a set of quasi-1-dimensional
graphs, which are a majority among the best performing networks. We also find
that networks with primarily short-range connections perform better than
networks which allow for many long-range connections. Moreover, many resolution
reducing pathways are beneficial. We provide a dataset of 1020 graphs and the
test accuracies of their corresponding neural networks at
https://github.com/rmldj/random-graph-nn-paper
