Analysis of large graphs is critical to the ongoing growth of search engines and social networks. One class of queries centers around node affinity, often quantified by random-walk distances between node pairs. This paper studies whether random-walk distances can be embedded into a coordinate space for constant-time queries.