Better but more expensive methods for splitting a graph are based on finding a particular eigenvector of a sparse matrix which has the structure of the adjacency matrix of the graph, and using this eigenvector as a separator field [Barnes:82a], [Boppana:87a], [Pothen:89a].
Neural Net Model
For our discussion of eigenvector bisection, we use the concept of a computational neural net, based on the model of Hopfield and Tank [Fox:88tt], [Hopfield:85b]. When the graph is to be colored with two colors, these may be conveniently represented by the two states of a neuron, which we conventionally represent by the numbers -1 and +1. The Hopfield-Tank neural net finds the minimum of a ``computational energy,'' which is a negative-definite quadratic form over a space of variables which may take these values -1 and +1, and consequently is ideally suited to the two-processor load-balance problem. Rewriting the load balance cost function,
where the 
are
``neural firing rates,'' which are continuous variables during the
computation and tend to 1 as the computation progresses. The first
term of this expression is the communication part of the cost function,
the second term ensures equal numbers of the two colors if 
is
small enough, and the third term is zero when the 
are 1, but
pushes the 
away from zero during the computation. The latter
is to ensure that H is negative-definite, and the large but arbitrary
constant 
plays no part in the final computation. The firing rate
or output 
of a neuron is related to its activity 
by
a sigmoid function which we may take to be 
. The
constant 
adjusts the ``gain'' of the neuron as an amplifier. The
evolution equations to be solved are then:
where 
is a time constant for the system
and 
is the degree (number of neighbors) of the graph node e.
If the gain is sufficiently low, the stable solution of this set of
equations is that all the 
are zero, and as the gain becomes
large, the 
grow and the 
tend to either -1 or +1. The
neural approach to load balancing thus consists of slowly increasing
the gain from zero while solving this set of coupled nonlinear
differential equations.
Let us now linearize this set of equations for small values of 
, meaning
that we neglect the hyperbolic tangent, because for small x, 
. This linear set of equations may be written in terms of the
vector u of all the 
values and the adjacency matrix A of
the graph, whose element 
is 1 if and only if the distinct graph
nodes e and f are connected by an edge of the graph. We may write
where D is a diagonal matrix whose elements are the degrees of the
graph nodes, I is the identity matrix, and E is the matrix
with 1 in each entry. This linear set of equations may be solved exactly
from a knowledge of the eigenvalues and eigenvectors
of the symmetric matrix N. If 
is sufficiently large, all
eigenvalues of N are positive, and when 
is greater than a critical value, the eigenvector of N
corresponding to its largest eigenvalue grows exponentially. Of
course, when the neuron activities are no longer close to zero, the
growth is no longer exponential, but this initial growth determines the
form of the emerging solution.
If 
is sufficiently small, so that balance is strongly enforced, then
the eigenspectrum of N is dominated by that of E. The highest
eigenvalue of N must be chosen from the space of the lowest eigenvalue
of E. The lowest eigenvalue of E is zero, with eigenspace given
by those vectors with 
, which is just the balance condition. We
observe that multiples of the identity matrix make no difference to the
eigenvectors, and conclude that the dominant eigenvector s satisfies
and 
, where
is maximal. The matrix 
is the Laplacian
matrix
of the graph [Pothen:89a], and is positive semi-definite. The lowest
eigenvector of the Laplacian has eigenvalue zero, and is explicitly excluded
by the condition 
. Thus, it is the second eigenvector which we
use for load balancing.
In summary, we have set up the load balance problem for two processors as a neural computation problem, producing a set of nonlinear differential equations to be solved. Rather than solve these, we have assumed that the behavior of the final solution is governed by the eigenstate which first emerges at a critical value of the gain. This eigenstate is the second eigenvector of the Laplacian matrix of the graph.
If we split a connected graph in two equal pieces while minimizing the boundary, we expect each half to be a connected subgraph of the original graph. This is not true in all geometries, but is in ``reasonable cases.'' This intuition is supported by a theorem of Fiedler [Fiedler:75a;75b] that when we do the splitting by the second eigenvector of the Laplacian matrix, at least one-half is always connected.
To calculate this second eigenstate, we use the Lanczos method [Golub:83a], [Parlett:80a], [Pothen:89a]. We can explicitly exclude the eigenvector of value zero, because the form of this eigenvector is equal entries for each element of the vector. The accuracy of the Lanczos method increases quickly with the number of Lanczos vectors used. We find that 30 Lanczos vectors are sufficient for splitting a graph of 4000 nodes.
A closely related eigenvector method [Barnes:82a], [Boppana:87a] is based on the second highest eigenvector of the adjacency matrix of the graph, rather than the second lowest eigenvector of the Laplacian matrix. The advantage of the Laplacian method is in the implementation: The first eigenvector is known exactly (the vector of all equal elements), so that it can be explicitly deflated in the Lanczos method.
Figure 11.12 (Color Plate) shows eigenvector recursive bisection in action. A triangular mesh surrounding a four-element airfoil has already been split into eight pieces, with the pieces separated by gray lines. Each of these pieces is being split into two, and the plot shows the value of the eigenvector used to make the next split, shown by black lines. The eigenvector values range from large and positive in red through dark and light blue, green, yellow, and back to red. The eight eigenvector calculations are independent and are, of course, done in parallel.
Figure 11.12: A stage of eigenvalue recursive
bisection. A mesh has already been split into eight pieces, which are
separated by gray lines, and the eigenvector is depicted on each of these.
The next split (into sizteen pieces) is shown by the black lines.
Figure 11.13: Solution of the Laplace Equation Used to Test Load-Balancing
Methods. The outer boundary has voltage increasing linearly from 
to 
in the vertical direction, the light shade is voltage 1, and
the dark shade voltage -1.
The splitting is constructed by finding a median value for the eigenvector so that half the triangles have values greater than the median and half lower. The black line is the division between these.