Edited by author 04-16-2002 08:02 AM
Spectral partitioning algorithms are based on using eigenvalues of the affinity matrix of a graph.

For the case of an unweighted graph with n vertices.
The affinity matrix is a nxn matrix with the (i,j) entry

1 if vertices i and j are connected
and 0 if they are not connected.

This matrix is also referred to as the adjacency matrix.
The weighted generalization in which we associate weights with each edge in the graph instead of just 0 and 1 is referred to as the affinity matrix. It is called the affinity matrix since the edge weights are used to indicate similarity, higher magnitudes indicating high levels of similarity.

It is useful to read this paper independent of the computer vision background that it comes from .
For this purpose a very simple example is to consider a distribution of points in a two dimensional plane.

The affinity matrix is now calculated as:

exp(-d_ij^2/s^2)

here d_ij is the eucldeian distance between the points i and j.

s or sigma as its used in the paper is a measure of how sensitive you want to be to distances while constructing the affinity matrix.

I think the Ng & Jordan paper combined with the Shi and Malik paper serve as excellent background readings to make sense of this paper.