Visualizing graphs with Krylov subspaces

Visualizing large graphs is a difficult problem, and requires balancing of the need to express global structure and the need to preserve local detail. The commute-time embedding is an attractive choice for providing a geometric embedding for graph vertices, but is high-dimensional. Dimension reduction of the commute-time embedding may be accomplished with Krylov subspace methods, which can preserve local detail and have intuitive geometric interpretations. These reduced-dimension approximations are computationally inexpensive, and may be contrasted against the much more expensive application of principal components analysis dimension reduction.