Finding a low-dimensional embedding of a graph of n nodes in Rd is an essential task in many applications.

For instance, maximum variance unfolding (MVU) is a well-known dimensionality reduction

method that involves solving this problem. The standard approach is to formulate the embedding problem

as a semidefinite program (SDP). However, the SDP approach does not scale well to large graphs. In

this paper, we exploit the fact that many graphs have an intrinsically low dimension, and thus the optimal

matrix resulting from the solution of the SDP has a low rank. This observation leads to a quadratic

reformulation of the SDP that has far fewer variables, but on the other hand, is a difficult convex maximization

problem. We propose an approach for obtaining a solution to the SDP by solving a sequence

of smaller quadratic problems with increasing dimension. Utilizing an augmented Lagrangian and an

interior-point method for solving the quadratic problems, we demonstrate with numerical experiments on

MVU problems that the proposed approach scales well to very large graphs.