# Question on a claim in a paper

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.

• 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. Oct 15, 2019 at 20:28
• 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.
– Amin
Oct 16, 2019 at 3:57
• 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. Oct 16, 2019 at 7:53
• Definitely $t > 0$.
– Amin
Oct 16, 2019 at 9:33
• Thanks for your nice comment. Yes, I just confused by the sign.
– Amin
Oct 16, 2019 at 9:47

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}
• 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. Oct 13, 2019 at 23:01