Spectral clustering revisited: Information hidden in the Fiedler vector

Figure 1.  A graph with two communities that have strong inter-connectedness but very few edges between them

Figure 2.  A two-dimensional domain with Neumann boundary condition and the second Laplacian eigenfunction

Figure 3.  A stochastic block graph: $n = 500$, $p = 0.05$ and $q = 0.0001$. Two clusters that are barely connected; the cluster on the left has a somewhat more 'ambiguous' region; this ambiguity should be reflected in the size of the entries of the eigenvector ${\bf{v_2}}$

Figure 4.  (top) The deviation from expected in-group affinity ($ c $, defined in Equation 2) for the vertices of a stochastic block model with $ (n,p,q) = (2000, 0.6, 0.4) $. Vertices are plotted in increasing order of the corresponding $ {\bf{v_2}} $ entry. (mid) Values of $ {\bf{v_2}} $ for corresponding vertices, ordered in increasing value. (bottom) Plot showing linear relationship between $ \Delta/\sqrt{n} $ and $ \left|{\bf{v_2}}\right| $, in accordance with the main theorem

Figure 5.  Error rates on subsets of vertices with extremal $ {\bf{v_2}} $ value, compared with the global $ {\bf{v_2}} $ label-estimation error rate. Subsets were chosen by taking the nodes with $ \varepsilon\cdot n $ largest magnitude $ {\bf{v_2}} $ entries, as in Corollary 1. This figure was generated by randomly sampling 500 independent stochastic block models, $ n = 200 $, $ p = 0.55, $ and $ q = 0.45 $

Figure 6.  Visualization of clustering experiments performed using MNIST dataset. Three hundred images of 3's and three hundred images of 8's were chosen at random from the original MNIST dataset. Pixel values were normalized and rounded to take binary values. A graph was constructed, with a vertex corresponding to each image, and an edge between two vertices if one of the vertices was within the 10% nearest neighbors of the other, using Euclidean distance. The vector $ {\bf{v_2}} $ and values of $ c $ (see Equation 3) were calculated for each vertex. The top figure was generated without noise. In the bottom figure, each pixel's binary value was reversed with independent probability $ \rho = 0.5 $, and the same calculations were performed

Figure 7.  Comparing how $ {\bf{v_2}} $ can inform seed set expansion methods. We replicate the method described in [5], and compare the overall error rate when using the five nodes corresponding to the five largest entries of $ {\bf{v_2}} $ as our seed set (shown in blue), versus five nodes selected uniformly at random from within a single community (shown in orange). Errorbars indicate one standard deviation. Using $ {\bf{v_2}} $ to inform the initial seed set consistently outperforms use of a random seed set. We emphasize that the random seed set is selected from within a single community: this means that not only are $ {\bf{v_2}} $-extremal vertices likely to be in their correct community, as reflected in Figure 5, but that these vertices are "preferable" to others within the same community