怕忘，写一个记录一下。
The (symmetric) normalized Laplacian is defined as
\[L^{\mathrm{sym}}:=D^{-\frac{1}{2}} L D^{-\frac{1}{2}}=I-D^{-\frac{1}{2}} A D^{-\frac{1}{2}}.\]It is easy to verify that the normalized Laplacian is PSD, and hence all the eigenvalues of the normalized Laplacian are non-negative.
Property 1. The eigenvalues of the normalized Laplacian are less than 2.
consider an eigenvector $g$ of $L_{sym}$ with eigenvalue $\lambda$, and suppose $g=D^{\frac{1}{2}} f$, then:
\[\lambda=\frac{\left\langle g, L^{\mathrm{sym}} g\right\rangle}{\langle g, g\rangle}=\frac{\left\langle g, D^{-\frac{1}{2}} L D^{-\frac{1}{2}} g\right\rangle}{\langle g, g\rangle}=\frac{\langle f, L f\rangle}{\left\langle D^{\frac{1}{2}} f, D^{\frac{1}{2} f}\right\rangle}=\frac{\sum_{u \sim v}(f(u)-f(v))^{2}}{\sum_{v} f(v)^{2} d_{v}},\]where $\langle f, g\rangle=\sum_{v} f(v) g(v)$, a sum over all vertices v, and $\sum_{u \sim v}$ denotes the sum over all unordered pairs of adjacent vertices $\lbrace u,v\rbrace$. Hence, the biggest eigenvalue has the expression
\[\lambda_n=\sup_x\frac{\sum_{u\sim v}(f(u)-f(v))^2}{\sum_vf(v)^2d(v)}.\]Since $\big(f(u)-f(v)\big)^2\le2\big((f(u))^2+(f(v))^2\big)$, we have
\[\lambda_n=\sup_x\frac{\sum_{u\sim v}(f(u)-f(v))^2}{\sum_vf(v)^2d(v)} \leq 2\sup_x\frac{\sum_{u\sim v}(f(u))^2+(f(v))^2}{\sum_vf(v)^2d(v)}=2\sup_x\frac{\sum_vf(v)^2d(v)}{\sum_vf(v)^2d(v)}=2,\]which completes the proof.
This property is used in GCN 1 .
