Determine the modal vertices.
Raise the power of the graphs to some power k.
Normalize the modal rows.
Compare these rows for sufficiently high k.

If these distributions are the same then the graphs are similar.

Chris Durand