pattern. We showed that for every graph there is a traffic pattern that reveals a cut that is guaranteed to be within O( log n ) times optimal. This is proved through a geometric argument and is outlined in Section 3. An efficient algorithm to actually find such a traffic pattern, the routing of the flow, and the resulting cut was discovered by Arora, Hazan, and Kale. ² The resulting Õ(n²) implementation of an O ( log n ) approximation algorithm for sparse cuts is described in Section 4. Thus, one gets a better approximation factor relative to the Leighton–Rao approach without a running time penalty. Surprisingly, even faster algorithms have been discovered. ^{4, 12, 16} The running time of these algorithms is dominated by very few calls to a single commodity max-flow procedure which are significantly faster in practice than the multicommodity flows used in Section 4. These algorithms run in something like O(n^1.5) time, which is the best running time for graph partitioning among algorithms with proven approximation guarantees. We describe these algorithms and compare them to heuristics such as METIS in Section 5.

2. the GeometRic aPPRoach anD the aRV aLGoRithm In this Section, we describe in more detail the geometric approach for graph partitioning from our paper. ⁶ Henceforth refered to as the ARV algorithm. Before doing so, let us try to gain some more intuition about the geometric approach to graph partitioning. We will then realize that the well-known spectral approach to graph partitioning fits quite naturally in this setting.

2. 1. the geometric approach

In Section 1, we introduced the geometric approach by saying “We draw the graph in some geometric space (such as the two-dimensional Euclidean space ℜ²). . . .” Well, let us consider what happens if we draw the graph in an even simpler space, the real line (i.e., ℜ). This calls for mapping the vertices to points on the real line so that the sum of the ( Euclidean) distances between endpoints of edges is as small as possible, while maintaining an average unit distance between random pairs of points. If we could find such a mapping, then cutting the line at a random point would give an excellent partition. Unfortunately, finding such a mapping into the line is NP-hard and hence unlikely to have efficient algorithms.

The popular spectral method does the next best thing. Instead of Euclidean distance, it works with the square of the Euclidean distance—mapping the vertices to points on the real line so the sum of the squares of edge lengths is minimized, while maintaining average unit squared distance between a random pair of points. As before, we can partition the graph by cutting the line at a random point. Under the squared distance, the connection between the mapping and the quality of the resulting cut is not as straightforward, and indeed, this was understood in a sequence of papers starting with work in differential geometry in the 1970s, and continuing through more refined bounds through the 1980s and 1990s. ^{1, 8, 18} The actual algorithm for mapping the points to the line is simple enough

that it might be worth describing here: start by assigning
each vertex i a random point x in the unit interval. Each
i
point x in parallel tries to reduce the sum of the squares of
i
its distance to points corresponding to its adjacent verti-
ces in the graph, by moving to their center of mass. Rescale
all the x ’s so that the average squared distance between
i

random pairs is 1, and repeat. (To understand the process intuitively, think of the edges as springs, so the squared length is proportional to the energy. Now the algorithm is just relaxing the system into a low-energy state.) We note that this is called the spectral method (as in eigenvalue spectrum) because it really computes the second largest eigenvector of the adjacency matrix of the graph.

2. 2. the aRV algorithm

The algorithm described in Section 1. 1 may be viewed as a high-dimensional analog of the spectral approach outlined above. Instead of mapping vertices to the line, we map them to points on the surface of the unit sphere in n-dimensional Euclidean space. As in the spectral method, we work with the square of the distance between points and minimize the sum of the squares of the edge lengths while requiring that the square distance between the average pair of points is a fixed constant, say 1. The sum of squares of lengths of all edges is called the value of the embedding.

How closely does such an embedding correspond to a cut? The ideal embedding would map each graph vertex to one of two antipodal points on the sphere, thus corresponding to a cut in a natural way. In fact, the value of such an embedding is proportional to the number of edges crossing the cut. It follows that the minimum-value two-point embedding corresponds to an optimal partitioning of the graph.

Unfortunately, the actual optimal embedding is unlikely to look anything like a two-point embedding. This is because squaring is a convex function, and typically we should expect to minimize the sum of the squared lengths of the edges by just sprinkling the vertices more or less uniformly on the sphere. To reduce this kind of sprinkling, we require the embedding to satisfy an additional constraint (that we alluded to in Section 1. 1): the angle subtended by any two points on the third is not obtuse. The equivalent Py-thogorean way of saying this is that the squared distances must obey the triangle inequality: for any triple of points u,

figure 3: a graph and its embedding on the d-dimensional euclidean sphere. the triangle inequality condition requires that every two points subtend a non-obtuse angle on every other point.

Unit sphere in �^d

No obtuse angles