> The catch is that this sparse subset of NN edge weights has no structure, so it doesn't get efficient execution

I you parallelize your computation along the training data dimension, the problem is embarrassingly parallel and the structure of your neural network does not matter on bit.