the subset of vertices in one part. For a weighted graph
G = (V, w) and a subset of vertices S ⊂ V, we define
We say that G = (V, w) and = (V, ) are σ-cut similar if
for all S ⊂ V. Surprisingly, every graph is cut-similar to a
graph with average degree O(log n), and that graph can be
computed in polylogarithmic time.
Theorem 1 (Benczúr-Karger). For all ε > 0, every G = (V, E, w)
has a ( 1 + ε)-cut similar graph such that ⊆ E
and | | = O(n log n/ε2). Moreover can be computed in
O(m log3 n + m log n/ε2) time.
The sizes of cuts in a graph tell us a lot about its structure—
for starters, the weighted degrees of vertices are given by cuts
of size |S| = 1. Most ways of defining a cluster of vertices in
a graph involve comparing the number of edges in the cut
defined by the set of vertices to the number of edges internal
to that set.
2. 2. spectral similarity
Motivated by problems in numerical linear algebra and spectral graph theory, Spielman and Teng34 introduced a notion
of spectral similarity for two graphs. We will first describe it
as a generalization of cut similarity.
Given a weighted graph G = (V, w), we define the
Laplacian quadratic form of G to be the function QG from
RV to R given by
properties. For example, the effective resistance distances
between all pairs of vertices are similar in spectrally similar
graphs. The effective resistance distance is defined by view-
ing each edge in a graph as a resistor: an edge of weight w
becomes a resistor of resistance 1/w. The entire graph is
then viewed as a resistive circuit, and the effective resistance
between two vertices is just the electrical resistance in the
network between them. It equals the potential difference
induced between the vertices when a unit current is injected
at one and extracted at the other. In terms of the Laplacian
quadratic form, the effective resistance between vertices u
and v may be written as
an identity which follows from the well-known energy mini-
mizing property of electrical flows.
QG (x) = cutG (S).
QG (x) = x T LGx,
where LG is the Laplacian matrix of G. The Laplacian matrix
of a graph G = (V, w) is defined by
We say two graphs G = (V, w) and = (V, ) are σ-spectrally
similar if
The problem of solving systems of linear equations in
Laplacian matrices arises in many areas of computational
science and optimization. In fact, the spectral similarity
measure is identical to the concept of relative condition num-
ber in numerical linear algebra. If two graphs are spectrally
similar, then through the technique of preconditioning
one can use solutions to linear equations in the Laplacian
matrix of one graph to solve systems of linear equations in
the Laplacian of the other.
Thus, cut similarity can be viewed as the special case of
spectral similarity in which we only consider vectors x that
take values in {0, 1}.
It is possible to construct graphs that have very similar cuts, but which are highly dissimilar from the spectral
perspective; for instance, the n-vertex path is 2-cut similar
but only n-spectrally similar to the n-vertex cycle. Although
spectral similarity is strictly stronger than cut similarity, it is easier to check if two graphs are spectrally similar. In particular, one can estimate the spectral similarity
of two graphs to precision ε in time polynomial in n and
log(1/ε), but it is NP-hard to approximately compute the
cut-similarity of two graphs.
Graphs that are spectrally similar share many algebraic
2. 3. spectral similarity of matrices
For two symmetric matrices A and B in Rn × n, we write A B
to indicate that
We say A and B are σ-spectrally similar if
