How can abstract graphs be recognized by neural nets?
The OP's (i.e. my) assumption is wrong. It is not true that for almost all random graphs under no permutation a pattern is visible, as can be  seen in Tiago P. Peixoto's paper Bayesian stochastic blockmodeling, p. 4:

The opposite seems to be correct: For almost all random graphs there are permutations such that patterns are visible.