To perform spectral graph analysis (SGA), we start with the PCA kernel, X Xt and create a weight matrix W for spectral analysis: wij={xitxjifxitxj≥0,0otherwise,} where xi and xj are row vectors of X. These wij are the edge weights of the graph. Let di=∑j=1nwij be the degree of vertex i, and let D = diag(d1,...,dn) be a diagonal matrix. The normalized Laplacian matrix for W is defined as I – L where L = D−1/2W D−1/2. Let νi and ui be the eigenvalues and eigenvectors of I – L and let λi = max {0, 1 – νi}. Map the ith subject into the S-dimensional eigenmap using (1). The dimension of the eigenmap, S, is determined using the eigengap heuristic to test for the number of significant eigenvalues in L (not including the trivial dimension). Given the S-dimensional representation, we use Ward's algorithm to partition the data into large homogeneous clusters [12, 17]. A cluster is considered homogeneous provided the eigenvalues are not significant based on the eigengap heuristic [12]. SGA is available as an R library, SpectralGEM (www.r-project.org).
