A recently proposed heuristic for the symmetric envelope minimization
problem involves sorting the rows/columns of the matrix by the values
of associated entries in the * Fiedler vector* of the graph of
nonzero entries. This approach was
proposed at about the same time by several different
researchers [BPS93,JM92,PMGM94a,PMGM94b], and seems to often
produce better orderings than more traditional combinatorial methods,
albeit at a somewhat increased cost. An analysis of
this approach based upon the quadratic assignment problem can be
found in [GP94]. In this section the symmetric matrix technique
is generalized to produce both row and column orderings for the
nonsymmetric problem.

Given a graph **G**, with vertex set **V** and weighted edges **E**, the heuristic
described in this section will use an eigenvector of **L**, the (weighted)
* Laplacian matrix* of **G**. If , then elements
and of **L** are set equal to . The diagonal is then
constructed to make row sums equal to zero. More formally,

The Laplacian matrix has a number of nice properties. It is symmetric and
positive semidefinite. The constant vector is an eigenvector with zero
eigenvalue, and if the graph is connected then all other eigenvalues are
positive. If the eigenvalues are sorted by increasing value,
an eigenvector of **L** corresponding to the second eigenvalue is
known as a * Fiedler vector* in recognition of the pioneering work of
Miroslav Fiedler [Fie73,Fie75]. The Fiedler vector has been used in
heuristics for a number of graph manipulations including
partitioning [PSL90], linear labeling [JM92] and envelope minimization
as alluded to above. For a survey of applications of the Fiedler vector,
see [Moh91,Moh92].

The Fiedler vector has a nice interpretation which helps to explain these
applications. Consider the problem of embedding a graph in the line
in such a way that all the edge lengths are kept short. That is, if
, then vertices **i** and **j** should be near each other;
particularly if the corresponding edge weight is large.
Letting be the location in the line of vertex **i**,
one way to express the embedding problem mathematically is to try
to minimize the following sum.

Merely minimizing **F** leads to a problem with an infinite number of
solutions since the minimum is invariant under translations. This can
be dealt with by making the average **x** value equal to zero; that is, adding
the constraint that . As posed, the problem now has a trivial
solution obtained by setting all the **x** values equal to zero. This can
be avoided by adding a normalization constraint on the **x** vector, leading
to the following problem.

It turns out that the solution to (5) is a Fiedler vector.
The objective function can be rewritten as , where **L** is the
Laplacian matrix of the graph. The first eigenvector is **e**, so it is
excluded by the first constraint. The solution is then seen to be the second
eigenvector.

The Fiedler vector approach also provides a plausible
heuristic for the symmetric envelope reduction problem. Consider the graph
of nonzeros of the symmetric matrix. This graph has a vertex for each row,
and an edge if element of the matrix is nonzero. Now
embed this graph the line via the Fiedler vector. Since edge lengths
are short, the edges incident to vertex **i** shouldn't connect to vertices
which are geometrically distant from **i**. Now order the rows (and columns)
of the matrix by sorting the corresponding values in the Fiedler vector.
Since adjacent vertices are near each other in the embedding, they should
be near each other in the ordering which is the goal of a small envelope
ordering. Although one can construct graphs for which this approach
works poorly [GM95], in practice it usually performs well.

It is now possible to describe a heuristic for reordering a term-by-document or hypertext matrix based upon the Fiedler vector. First, construct the bipartite graph of the hypertext (link-by-document) matrix. Embed this graph in the line with the Fiedler vector. This embedding will combine links and documents in such a way that terms try to be near the documents which include them, and documents are near the links they include. Note that if two links are shared by several documents then they are likely to land near each other in the embedding. Now order the links by sorting their values in the Fiedler vector and do the same for documents. Since links (documents) which share documents (links) are near each other in the embedding, they should be near each other in the ordering as desired. Table 6 illustrates the reordering using the derived Fiedler vector for the matrix defined in Table 2.

Michael W. Berry (berry@cs.utk.edu)

Mon Jan 29 14:30:24 EST 1996