0
$\begingroup$
  • Let $V$ be the set of datapoint and assume that each point can be represented by a vertex. Then, given a similarity matrix $ \mathbf{M}$, we define a graph $G = (V, \mathbf{M})$ generated using $k$-nearest neighbors.

  • Let $\mathbf{D}$ denote the diagonal degree matrix of $\mathbf{M}$. Then, we define the normalized weight matrix $\mathbf{W}$ using $\mathbf{D}$, so that

\begin{equation*} \mathbf{W}= \mathbf{D}^{-\frac{1}{2}} \mathbf{M} \mathbf{D}^{-\frac{1}{2}}. \end{equation*}

  • Therefore, we define the normalized Laplacian matrix of $G$ as \begin{equation*} \mathbf{L} = \mathbf{I} - \mathbf{W}= \mathbf{I}- \mathbf{D}^{-\frac{1}{2}} \mathbf{M} \mathbf{D}^{-\frac{1}{2}}, \end{equation*} where $\mathbf{I}$ is the identity matrix.

  • Since the normalized Laplacian matrix $\mathbf{L}$ is a positive semi-definite matrix, the matrix $\mathbf{L}$ is decomposed into an orthogonal set of eigenvectors $\mathbf{U}=[u_1,...u_n]$ and eigenvalues $\mathbf{\Lambda}=[\lambda_1,...,\lambda_n]$ represented as follows \begin{equation*} \mathbf{L}= \mathbf{U}\Lambda \mathbf{U}^{T}. \end{equation*}

In the graph setting, the eigenvalues of $ \mathbf{L}$ can be treated as graph frequencies, and are always situated in the interval $[0, 2]$ for $\mathbf{L}$.

......................

  • Now, let $\mathbf{H}=\mathbf{U} h(\mathbf{\Lambda}) \mathbf{U}^{T}$ where $h(\mathbf{\Lambda})$=diag$(h(\lambda_1),...,h(\lambda_n))$.

  • I assume that $h(\mathbf{\lambda})=1$ if $\lambda \leq \lambda_k$ and $h(\mathbf{\lambda})=0$ if not.

Therefore, $\mathbf{U} h(\mathbf{\Lambda}) \mathbf{U}^{T}= \boldsymbol{\chi} \boldsymbol{\chi}^T $, where $\boldsymbol{\chi} \in \mathbb{R}^{n\times k}$ contains the first $k$ eigenvectors of the normalized Laplacian $\mathbf{L}$.

My questions:

  1. I know that $UU^{T}=\mathbf{I}$ but what about $\boldsymbol{\chi} \boldsymbol{\chi}^T $ that contains the first $k$ eigenvectors of the normalized Laplacian $\mathbf{L}$ ?

  2. Assume that I sum up all elements of the matrix $\boldsymbol{\chi} \boldsymbol{\chi}^T $ (call it $S$). Is there any condition to ensure that the sum $S$ decreases or takes the smallest possible value?

  3. Is there any relation between $S$, $\boldsymbol{\chi} \boldsymbol{\chi}^T $ and the the topology of the graph?

$\endgroup$
7
  • $\begingroup$ Presumably, the columns of $\chi$ are meant to be unit vectors $\endgroup$ Jul 19, 2020 at 18:15
  • $\begingroup$ Also, when you say that the sum decreases, presumably you mean that the sum decreases for increasing values of $k$. Whether or not my guesses are correct, please make it clear what exactly you mean. $\endgroup$ Jul 19, 2020 at 18:18
  • $\begingroup$ @BenGrossmann sorry for not been clear. I just wanna know how the sum $S$ varies. I would like to know if there is an effect on $S$ if I choose properly the $k$ eigenvectors or the value of $k$. I used the word "decrease" because I am interested on the case where this sum is small. $\endgroup$
    – Lina
    Jul 19, 2020 at 18:23
  • $\begingroup$ For the sum $S$ to vary (or decrease more specifically), something about $\chi$ needs to be changed. What is it that you are changing? Is it $k$, or is it something else? $\endgroup$ Jul 19, 2020 at 18:25
  • $\begingroup$ I guess it could be $k$, but how to chose it if I want it to decrease $S$? or perhaps find a way to choose only eigenvectors that decreases $S$, but I don't know which ones. $\endgroup$
    – Lina
    Jul 19, 2020 at 18:29

1 Answer 1

0
$\begingroup$

know that $UU^{T}=\mathbf{I}$ but what about $\boldsymbol{\chi} \boldsymbol{\chi}^T $ that contains the first $k$ eigenvectors of the normalized Laplacian $\mathbf{L}$ ?

Because $\chi^T\chi = I_k$, $\chi\chi^T$ is the orthogonal projection onto the span of the columns of $\chi$, i.e. the first $k$ eigenvectors of L.

Assume that I sum up all elements of the matrix $\boldsymbol{\chi} \boldsymbol{\chi}^T $ (call it $S$). Is there any condition to ensure that the sum $S$ decreases or takes the smallest possible value?

Let $\chi_k$ denote the matrix $\chi$ constructed above with $k$ columns. Let $e = (1,1,\dots,1)^T$. The sum of the elements of $\chi_k\chi_k^T$ is equal to $$ S_k = e^T[\chi_k\chi_k^T]e = [e^T\chi_k][\chi_k^Te] = (\chi_k^Te)^T(\chi_k^Te) = \sum_{j=1}^k (e^Tv_j)^2, $$ where $v_j$ denotes the $j$th unit eigenvector (i.e. the $j$th column of $\chi_k$). Note that $e^Tv_j$ is the sum of the entries of $v_j$. With that, it is clear that $S$ increases as $k$ increases since each term in the sum is non-negative.

Is there any relation between $S$, $\boldsymbol{\chi} \boldsymbol{\chi}^T $ and the the topology of the graph?

There is no relation to the topology of the graph that I can see. If you're interested in a more thorough answer, then this question should probably be asked as its own, separate post.

$\endgroup$
11
  • $\begingroup$ Thank you for the answer. If I am not wrong, $UU^{T}=I$ but if I select only $k$ eigenvectors then $\chi \chi^{T} \neq I$. $\endgroup$
    – Lina
    Jul 19, 2020 at 18:36
  • $\begingroup$ @Lina Yes. If $k < n$, then $\chi\chi^T \neq I$. $\endgroup$ Jul 19, 2020 at 18:38
  • $\begingroup$ I though that the multiplicity of eigenvalues is important here. What I actually think is that if I chose for example only eigenvectors that correspond to the same eigenvalue, I will have a small values of $S$. But, if I chose only eigenvectors corresponding to different eigenvalues, the summer will approach 1. What do you think about that? $\endgroup$
    – Lina
    Jul 19, 2020 at 18:54
  • $\begingroup$ @Lina I just thought of something: does the normalized laplacian $L$ have zero row-sums (like the classical graph Laplacian)? If so, then we have $v_j^Te = 0$ for all $j > 1$. $\endgroup$ Jul 19, 2020 at 18:56
  • $\begingroup$ @Lina As for your comment, I don't have any reason to believe that the multiplicity of the eigenvalues should matter. $\endgroup$ Jul 19, 2020 at 18:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .