The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem

SIAM Review, 48(4):681-699, November 2006.

• fmmp.pdf

We consider a Markov process on a connected graph, with edges labeled with transition rates between the adjacent vertices. The distribution of the Markov process converges to the uniform distribution at a rate determinined by the second smallest eigenvalue of the Laplacian of the weighted graph. In this paper we consider the problem of assigning transition rates to the edges so as to maximize the second smallest eigenvalue, subject to a linear constraint on the rates. This is the problem of finding the fastest mixing Markov process (FMMP) on the graph. We show that the FMMP problem is a convex optimization problem, which can in turn be expressed as a semidefinite program, and therefore effectively solved numerically. We formulate a dual of the FMMP problem, and show that it has a natural geometric interpretation as a maximum variance unfolding (MVU) problem, i.e., the problem of choosing a set of points to be as far apart as possible, measured by their variance, while respecting local distance constraints. This MVU problem is closely related to a problem recently proposed by Weinberger and Saul as a method for ‘unfolding’ high dimensional data that lies on a low dimensional manifold. The duality between the FMMP and MVU problems sheds light on both problems, and allows us characterize, and, in some cases, find optimal solutions.