Let $\odot$ represents the point-wise product and $L$ is the Laplacian matrix (which is symmetric positive semidefinite matrix) and it can be diagonalized as $L = \Phi \Lambda\Phi^*$ and $\Phi = [\varphi_1, \ldots, \varphi_N]$ and $\Phi \Phi^* = \Phi^*\Phi = I$ and $\Lambda = Diag(\lambda_1, \ldots, \lambda_N)$ is the eigenvalue matrix such that $\lambda_i \geq 0$ for all $i$.

In this paper (page 3), the authors generalized a similarity notion on compact manifolds to the graph setting claiming that

$$ \alpha (\varphi_k,\varphi_\ell) \in [0,1]. $$ where $\varphi_k$ and $\varphi_\ell$ are the $k$-th and $\ell$-th eigenvectors of graph Laplacian matrix, respectively.

I am curious to write a rigorous mathematical reasoning for this. My derivations are as follows.

$$\alpha(\varphi_k,\varphi_\ell) = \frac{\|e^{-tL} (\varphi_k \odot \varphi_{\ell})\|}{\|\varphi_k \odot \varphi_{\ell}\|} \leq \frac{\|\Phi e^{-t\Lambda} \Phi^{*}\| \|\varphi_k \odot \varphi_{\ell}\|}{\|\varphi_k \odot \varphi_{\ell}\|} \leq \|e^{-t\Lambda}\| = e^{-t\lambda_{\min}}\leq 1, $$ where $\lambda_{\min}$ is the largest eigenvalue of $L$.

I just get confused about that. Would you please elaborate on this case?

Note: Based on the nice comment of @MaoWao, it is clear that the problem is about the "negative sign" in the definition of this metric.

Additional note: This question from the first concerning the graph setting (NOT the manifold - as the graph Laplcian matrix and its diagonalization are used and an example also provided for that). Moreover, the paper is actually about generalizing that concept from manifold to the graph setting addressing that equation when doing this generalization. Then the answer on manifold is not helpful and it is off-topic.

  • $\begingroup$ I think you just have some trouble with the signs. The $t$ in the definition of $\alpha(\phi_j,\phi_k)$ is the unique solution of $e^{t\lambda_j}+e^{t\lambda_k}=1$, which forces $t$ to be non-positive. Also, if $t<0$, then $\|e^{tL}\|=e^{t\lambda_{\min}}$, which is $\leq 1$ by assumption. $\endgroup$
    – MaoWao
    Oct 15, 2019 at 20:28
  • $\begingroup$ Of course, surely $t>0$ by the claim of paper. Moreover, I think all the eigenvalues are effective rather than just the two corresponding eigenvalues. $\endgroup$
    – Amin
    Oct 16, 2019 at 3:57
  • 1
    $\begingroup$ Tbh, I don't even see a proper definition of $\alpha(\phi_j,\phi_k)$ for graphs in the paper. In any case, you have to either take $e^{-tL}$ instead of $e^{tL}$ in the definition of $\alpha$ or take $t<0$. That's actually quite natural since $\Delta$ is a negative operator, so the correct analog of $\Delta$ on graphs would be $-L$ and not $L$. Finally, you need some defining equation for $t$ since $\alpha(\phi_j,\phi_k)$ does not depend on $t$. But whatever $t\leq0$ you choose, $0\leq \alpha(\phi_j\phi_k)$ will always hold. $\endgroup$
    – MaoWao
    Oct 16, 2019 at 7:53
  • $\begingroup$ Definitely $t > 0$. $\endgroup$
    – Amin
    Oct 16, 2019 at 9:33
  • $\begingroup$ Thanks for your nice comment. Yes, I just confused by the sign. $\endgroup$
    – Amin
    Oct 16, 2019 at 9:47

1 Answer 1


I have not read the paper carefully enough to understand what everything means, but this property might just follow by Cauchy-Schwarz. Because $p(t,x,\cdot)$ and $p(t,\cdot,y)$ are probability distributions, we have (using Fubini towards the end) \begin{align} \|e^{t\Delta}f\|_{L^2}^2 &= \int_M|e^{t\Delta}f(x)|^2\,dx = \int_M\left|\int_Mp(t,x,y)f(y)\,dy\right|^2\,dx\\ &\le \int_M\left(\int_Mp(t,x,y)\,dy\right)\left(\int_Mp(t,x,y)|f(y)|^2\,dy\right)\,dx\\ &= \int_M\int_Mp(t,x,y)|f(y)|^2\,dy\,dx\\ &= \int_M|f(y)|^2\int_Mp(t,x,y)\,dx\,dy\\ &=\|f\|_{L^2}^2. \end{align}

  • $\begingroup$ @Amin Why do you want to delete the question? $\endgroup$
    – amsmath
    Oct 13, 2019 at 15:06
  • $\begingroup$ @Amin No, actually I don't. I have thought about your problem for some time, read the paper, and also spent time on writing my answer. You could at least check it. Then I get the credits and can delete it. $\endgroup$
    – amsmath
    Oct 13, 2019 at 22:46
  • $\begingroup$ Actually I first checked your answer. That is related to the case on manifold but I need the discussion on graph rather than manifold. Totally different. $\endgroup$
    – Amin
    Oct 13, 2019 at 22:48
  • $\begingroup$ But the paper is on manifolds. So, the answer is legit. Just open a new question for graphs. $\endgroup$
    – amsmath
    Oct 13, 2019 at 22:50
  • 2
    $\begingroup$ Well, you edited your question yesterday when I already had given my answer. The only question in your first post was about $\alpha\in [0,1]$ on page 3 of the paper. I answered. If you have another question, open up another one. $\endgroup$
    – amsmath
    Oct 13, 2019 at 23:01

You must log in to answer this question.

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