With a graph and a row-based algorithm, I would partition it using METIS or similar, then apply an RCM ordering within each block. This will give better locality of access to the vector x, which has been known (since at least the PETSc-FUN3D work in the late 90s) to be a major factor in SpMV performance.

I can just add that we (at Berkeley) also looked at SpMV ordering in the 90s. Sivan Toledo has a nice paper on it and a grad student made a PhD thesis in the topic ("Sparsity" package). Anyway we found that if you did something reasonable, RCM, Metis, performance was pretty similar (we used IBMs a lot also), and random ordering was about 3x slower. FWIW.