We show how to build hierarchical, reduced-rank representation for large stochastic matrices and use this representation to design an efficient algorithm for computing the largest eigenvalues, and the corresponding eigenvectors. In particular, the eigen problem is first solved at the coarsest level of the representation. The approximate eigen solution is then interpolated over successive levels of the hierarchy. A small number of power iterations are employed at each stage to correct the eigen solution. To show the effectiveness of this approximation, we present a multi-scale version of the EigenCuts algorithm, a graph-theoretic spectral clustering method previously reported. The goal here is to identify, and remove, bottlenecks between weakly coupled clusters in an automatic fashion. The multi-scale algorithm presents two significant advantages. First, it narrows down the search for the location of the bottlenecks to cut. Second, it eases the computational burden inherent to the EigenCuts procedure, where an eigen decomposition of the transition matrix has to be performed after every iteration of bottleneck cutting. We show that the clusters returned by the multi-scale algorithm are nearly identical to the ones derived by the basic version of the EigenCuts procedure.