Stripping out the fluff: The authors proved that iterative methods for solving sparse linear systems can be guaranteed to be faster than the best methods of solving dense linear systems.
(I assume this is common knowledge or at least should be)
Like in an adjacency matrix for a graph, you may have a lot of sparsity, but if you're forced to consider neighbors of neighbors, the adjacency matrix you need is A^2. This can be dense even if A is quite sparse.
Typo: should be one-hot encoding scheme.
Sparsity of input isn't often relatively easy to achieve, as you suggest.
Sparsity of intermediate layers requires more work. (But is often a good regularization technique.)
This article (not the paper) definitely oversells the immediate practical applications; nobody is going to throw out their CG solver and pick this method up in practice to guarantee convergence in this manner.