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. 2 The resulting Õ(n2) 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(n1.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. 6 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 ℜ2). . . .” 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