\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\usepackage{graphicx}
\usepackage[ruled,vlined]{algorithm2e}
\usepackage{tikz}
\usetikzlibrary{matrix}
\usepackage{dsfont}
\usepackage{tikz}
\spacing{1.06}
\usepackage{blkarray}% http://ctan.org/pkg/blkarray
\newcommand{\matindex}[1]{\mbox{\scriptsize#1}}% Matrix index

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-8:\hspace{0.12cm}Advanced
          Algorithms (Spring'21)} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{15: Laplacian, Drawing a Graph in 2D}{Mar 09,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Milen Ferev (mf3231)}}

\section{Introduction}
Last lecture we looked at the eigenvalues and eigenvectors of the augmented adjacency matrix and saw that the second eigenvalue gives us information if the graph is connected or not. In this lecture we formalize and explore this connection further, obtaining a relation between the value of the second eigenvalue and the connectivity of the graph using the notion of a Laplacian. 

\section{Recap}
Recall from last lecture
\begin{theorem}
    $\lambda_2 = 1$ iff graph G is disconnected
\end{theorem}
\begin{definition}[Normalized Adjacency Matrix]
\[\hat{A} = D^{-1/2}AD^{-1/2}\]
With eigenvalues $$\lambda_1 \geq \lambda_2 \geq \cdots \lambda_n$$  and eigenvectors $$v_1, v_2, \cdots v_n$$
\end{definition}

\section{Laplacian}
In this section we introduce the notion of a Laplacian and examine some of its properties.
\begin{definition}
[Laplacian of G] 
$$L_G = D - A = 
  \begin{bmatrix}
    d_{1} & -1& \\
    & \ddots & \\
    & & d_{r}
  \end{bmatrix}
$$
Where for an edge $(i,j) \in G$ we have $L_{ij}$ = -1 as shown above.
\end{definition}

We consider the following useful fact about the Laplacian:
\begin{fact}
\label{fact1}
\[
\forall x \in \mathbb{R}^n: x^TLx = \sum_{(i,j)\in E} (x_i - x_j)^2
\]
\end{fact}

\begin{proof}
Since the graph G is fixed we will omit writing $L_G$ and instead denote the Laplacian with $L$. We rewrite the Laplacian in the form of a sum of Laplacians of edges $L_e$ for  $e = (i,j) \in E$:
\[
L = \sum_{e\in E} L_e
\]
In particular, $L_e$ denotes the Laplacian of an edge $e = (i,j)$. $L_e$ is represented as the Laplacian of a graph consisting only of that edge. For $e = (i,j)$ we have the matrix:
\[
  L_e =\begin{blockarray}{ccc}
    \matindex{i} & \matindex{j} & \\
    \begin{block}{(cc)c}
      1 & -1 & \matindex{i} \\
      -1 & 1 & \matindex{j} \\
    \end{block}
  \end{blockarray}
\]
where the corresponding values for coordinates (i,j), (j,i), (i,i), (j,j) are shown. All other values are set to 0.
We can see that after computing the sum above we get the same matrix as $L_G$ from above.\\
Then using this representation we have:
\[
x^{T}Lx =  \sum_{e\in E} x^T L_e x = \sum_{e = (i,j)\in E} (x_{i}^{2} + x_{j}^{2} - 2x_ix_j) = \sum_{e = (i,j)\in E} (x_i - x_j)^2
\]
\end{proof}

\paragraph{Intuition.}\mbox{}\\
To gain an intuition of the expression we obtained above, consider the case of a circuit represented by a graph G where each node represents a potential and each edge a wire. We set $x_i$ to be the potential at node $i \in V$. Then the potential difference $V_{ij}$ is given by
\[
V_{ij} = x_i - x_j
\]
Then for each edge $e = (i,j)$ the energy loss per edge can be obtained by:
\[
I_{ij}V_{ij} = \frac{V_{ij}}{R_{ij}}V_{ij} = V_{ij}^2 = (x_i - x_j)^2
\]
Note that to derive this we applied Ohm's law and assumed $R_{ij} = 1$.

Then the total energy loss is given by:
\[
\sum_{e=(i,j)\in E} (x_i - x_j)^2 = x^T L x
\]

\paragraph{Properties of the Laplacian}\mbox{}\\
Consider the expression for $x^T L x$ form Fact \ref{fact1}:
\[
x^{T}Lx = \sum_{e = (i,j)\in E} (x_i - x_j)^2
\]

We can observe the following properties:
\begin{itemize}
    \item \textbf{Property 1}\\
    Notice that the expression implies that 
\[
x^T L x \geq 0
\]
From this we also know that all eigenvalues are also positive.
\item \textbf{Property 2}\\
If we take a vector x (which we will also denote by e) of the form
\[
x = (1,1,\cdots,1) = e\]
Then we have
\[
x^T L x = \sum_{(i,j)\in E} (x_i - x_j)^2 = 0
\]
Then for $\mu_1(L)$, which denotes the smallest eigenvalue of L we have:
\[
\mu_1(L) = 0
\]
\item \textbf{Property 3}\\
For the second smallest eigenvalue of the Laplacian we have the theorem:
\begin{theorem}
\label{mu2_theorem}
$\mu_2(L) = 0$ iff G is disconnected. 
\end{theorem}
\end{itemize}

\section{Drawing a Graph G in $\mathbb{R}^2$}
In this section we discuss the problem where given a graph $G=(V,E)$ we need to draw it in $\mathbb{R}^2$. To illustrate the problem we will take the following example.
\begin{example}[Graph corresponding to a square]
Take the graph $G = (V,E)$ that corresponds to a square.
\[V = \{1,2,3,4\} \]
\[E = \{(1,2),(2,3),(3,4),(4,1)\}\]
We need to find $f: V \to \mathbb{R}^2$ such that $f(i) = (x_i, y_i)$, where $(x_i, y_i)$ are the coordinates in $\mathbb{R}^2$. Our goal is to obtain a square given by those coordinates. 
\end{example}


The solution to this is regarded as a Spectral Drawing. 
\begin{definition}[Spectral Drawing]
The Spectral Drawing is given by:
\[f(i) = (v_{2i}, v_{3i})\]
Where $v_2$ is the second eigenvector of L and $v_3$ is the third eigenvector of L.\\
\end{definition}
Note that $v_1$ is given by:
\[v_1 = (1,1,\cdots,1)\]
To show this consider (Using the vector e from \textbf{Property 2} above):
\[L_{v_1} = (D-A)e = De - Ae = (d_1,d_2\cdots d_n) - (d_1,d_2\cdots d_n) = (0,0,\cdots,0) = 0\cdot v_1 \]

To see how we arrived at the solution for the Spectral Drawing, let us consider the drawing cases below. For the 1D cases we can represent our drawing by the vector $x = \mathbb{R}^n$ where each coordinate i in x corresponds to the coordinate of a node $i \in V$. For the 2D cases we take $x = \mathbb{R}^n$, $y = \mathbb{R}^n$.

\paragraph{Attempt 1 (1D):}
\[min_{x \in \mathbb{R}^n} \sum_{(i,j) \in E} (x_i - x_j)^2\]
Since in this case we are minimizing distance between nodes, the best x we get is
\[x = (0,0,0, \cdots, 0)\]

\paragraph{Attempt 2 (1D):}
\[min_{||x||_2 = 1} \sum_{(i,j) \in E} (x_i - x_j)^2\]
This condition is satisfied by taking an x such as the one below:
$$x = \left(\frac{1}{\sqrt{n}},\frac{1}{\sqrt{n}},\frac{1}{\sqrt{n}}, \cdots, \frac{1}{\sqrt{n}}\right)$$

\paragraph{Attempt 3 (1D):}
\[min \sum_{(i,j) \in E} (x_i - x_j)^2\]
subject to
\[||x||_2 = 1, \sum_{i} x_i = 0\]
In this case the solution is given by:
\[argmin \ x^T L x\]
subject to
\[||x||_2 = 1, e^T \cdot x = 0 \]
Which gives an answer $ x = v_2$ 

\paragraph{Attempt 4 (2D):}\mbox{}\\
For this case we have $x \in \mathbb{R}^n$, $y \in \mathbb{R}^n$
\[\min x^T L x + y^T L y \]
Subject to
\[||x||= 1, ||y|| = 1\]
\[e^T x = 0, e^T y = 0\]

Notice that the above is equivalent to the two cases below
\[\min \sum_{(i,j)\in E} (x_i + x_j)^2 + (y_i + y_j)^2 = \min x^T L x + \min y^T L y\]
Since we are minimizing both independently, the solution is given by:
$x = v_2, y = v_2$

\paragraph{Attempt 5 (2D):}\mbox{}\\
For this case we have $x \in \mathbb{R}^n$, $y \in \mathbb{R}^n$

\[\min x^T L x + y^T L y\]
Subject to
\[
||x||_2 = 1, ||y||_2 = 1\]
\[e^T x = 0, e^T y = 0\]
\[y^{T}\cdot x = 0\]
Notice that this is equivalent to computing
\[\left[\min y^T L y\right] + v_{2}^{T}Lv_2\]
Subject to
\[
||y||_2 = 1, e^T y = 0, x = v_2, y^{T}\cdot x = 0
\]
Using the Rayleigh quotient we have
\[\min R_L(y) + v_{2}^{T}Lv_2\]
Subject to
\[
||y||_2 = 1, e^T y = 0, v_{2}^{T}\cdot y = 0
\]
which gives us
\[
    v_{3}^{T}Lv_3 + v_{2}^{T}Lv_2
\]
Thus we have the solution $x = v_2$, $y = v_3$ (Notice that the values can also be switched).

\section{Cheeger Inequality and Spectral Clustering}
In this section we explore the connection between the second eigenvalue and the connectivity of the graph. We introduce the notion of the normalized Laplacian.
\begin{definition}
[Normalized Laplacian]
\[
\hat{L} = D^{-1/2}LD^{-1/2} = D^{-1/2}(D-A)D^{-1/2} = I - \hat{A}
\]
\end{definition}
Using this definition, suppose $(\lambda_i, v_i)$ are the eigenvalues and eigenvectors of $\hat{A}$. Then we have
\[
\hat{L}v_i = (I - \hat{A})v_i = v_i - \lambda_i\cdot v_i = (1 - \lambda_i)\cdot v_i
\]
From this it follows that $(1 - \lambda_i, v_i)$  gives the eigenvalues and eigenvectors of $\hat{L}$. Then from the properties of the eigenvalues of $\hat{A}$ we know that:
\[1 = \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n\]
Using what we derived for the eigenvalues of $\hat{L}$ we have:
\[0 = 1-\lambda_1 \leq 1-\lambda_2 \leq \cdots \leq 1-\lambda_n\]
We denote the eigenvalues of $\hat{L}$ as (also using that we have proven that $\lambda_n \geq -1$):
\[0 = \mu_1 \leq \mu_2 \leq \cdots \leq \mu_n \leq 2 \]

Considering Theorem \ref{mu2_theorem}, if we suppose $\mu_2 > 0$, we can consider it as an algebraic measure of connectivity.

\paragraph{Conductance}\mbox{}\\
We will now explore a combinatorial notion of connectivity using the concept of Conductance.
\begin{definition}[Cut]
Define a cut given by \[S \subset V\] 

\end{definition}
\begin{definition}[Volume]
Define Volume as the sum of degrees for $i \in S$:
\[vol(S) = \sum_{i \in S} d_i\]
\end{definition}

\begin{definition}[Conductance of S]
\[
\phi(S) = \frac{\partial S}{vol(S)}
\]
Where $\partial S$ is the edges crossing from S to $\bar{S}$
\[\partial S = \sum_{(i,j) \in E} \mathds{1}\left[ i \in S, j \notin S\right]\]
\end{definition}
\begin{definition}[Conductance of graph G]
\[\phi(G) = \min \phi(S)\]
Such that
\[S \neq \emptyset, vol(S) \leq \frac{1}{2}vol(V)\]
\end{definition}
Using the definition of Conductance, we can relate the value of $\mu_2$ to $\phi(G)$ by the following Theorem:
\begin{theorem}
[Cheeger]
\[\frac{\mu_2}{2} \leq \phi(G) \leq \sqrt{2\mu_2}\]
\end{theorem}

\end{document}