# Recovering a partition from spectral properties of the graph Laplacian

Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph Laplacian.

Let $P$ be a partition of $V$. $|P|$ is the number of parts in $P$. For convenience, $P$ may be expressed as a binary $|V|\times|P|$ matrix $Y$, with 1s indicating membership. ($P$ and $Y$ aren't directly observed; our goal is to approximate them.)

Let $G_{[ij]}$ be the subgraph of $G$ containing just the vertices contained in two parts of $P$ --- $P_i$ and $P_j$ --- and just the edges between those vertices. Let $W_{[ij]}$ be the submatrix of $W$ that is the affinity matrix of $G_{[ij]}$. Let $L_{[ij]}$ be the graph Laplacian of $G_{[ij]}$. Let $Y_{[ij]}$ be the submatrix composed of the $i^\text{th}$ and $j^\text{th}$ columns of $Y$.

Let $z_{[ij]} = \arg \min_x x^T L_{[ij]}x$, where $x$ is a vector with $x \perp \mathbf 1$ and $x^Tx = 1$. The minimizer $z_{[ij]}$ is then the eigenvector of $L_{[ij]}$ corresponding to the smallest positive eigenvalue of $L_{[ij]}$. Suppose for all $i,j$, $z_{[ij]}$ is "good" at recovering parts $P_i$ and $P_j$, in the following sense: $\|z_{[ij]}-Y_{[ij]}c_{[ij]}\|^2_2 \le \epsilon_{ij}$, where $c_{[ij]}=(Y_{[ij]}^TY_{[ij]})^{-1}Y_{[ij]}^Tz_{[ij]}$ (i.e. each entry in the vector $c_{[ij]}$ is the mean of the elements of $z_{[ij]}$ corresponding to the vertices contained in a particular part of $P$).

How good then is $z = \arg \min_x x^T Lx=\arg \min_x \sum_{ij} W_{ij}(x_i - x_j)^2$ at recovering the parts of $P$? For instance, for $c =(Y^TY)^{-1}Y^Tz$, is there a non-trivial upper bound on $\|z - Yc\|^2_2$ in terms of the $\epsilon_{ij}$?

-
What is an entity? – Piotr Migdal Jun 13 '13 at 13:16
Sorry, I've revised the question, removing the term "entity". – Jeff Jun 13 '13 at 22:39