3.4. Fiedler Ordering

  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.