\documentclass[11pt,epsf]{article}
\parindent 0in
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}

\newcommand{\handout}[5]{
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf 18.409 The Behavior of Algorithms in Practice} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer: #3}{Scribe: #4}{Lecture #1}}

\newcommand{\Kappa}{\kappa}

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

\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\parskip 1.5ex

\renewcommand{\baselinestretch}{1.25}

\begin{document}

\lecture{7}{5 March 2002}{Shang-Hua Teng}{Michael Korn}


\section{The Laplacian}

Given a simple graph $G = (V, E)$ with $n$ vertices, define the Laplacian $L(G)$ to be the $n$-by-$n$ matrix
with diagonal entries $d_i$ and off-diagonal entries $L_{i,j}$ such that $d_i$ is the degree of vertex $v_i$, 
and $L_{i,j}$ is $-1$ if $(i,j)$ is an edge, and $L_{i,j}$ is 0 otherwise.  Observe that $L(G)$ is a symmetric matrix.

$$\includegraphics{lect7/gr.eps}$$

The Laplacian for the above graph is

$$\begin{pmatrix}
2 & -1 & 0 & -1 & 0\\
-1 & 3 & -1 & 0 & -1\\
0 & -1 & 2 & 0 & -1\\
-1 & 0 & 0 & 2 & -1\\
0 & -1 & -1 & -1 & 3
\end{pmatrix}$$


Now let us define another matrix which encodes information from a graph.  For a simple graph $G = (V, E)$ with $n$
vertices and $m$ edges, define the {\it incidency matrix} $B(G)$ to be the $n$-by-$m$ matrix defined as follows.
Each column of $B$ corresponds to an edge $(i,j)$ of $G$.  In that column, put a 1 in the $i$th row, a $-1$ in the 
$j$th row, and zeros everywhere else.  (Notice that we equally well could have put a $-1$ in the $i$th row and a 1
in the $j$th row.  You could devise some rule for which row gets the 1 and which gets the $-1$, but for our purposes
it doesn't matter.)  For the graph above, the incidency matrix is

$$\begin{pmatrix}
1 & 1 & 0 & 0 & 0 & 0\\
-1 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & -1 & 0 & 1 & 0\\
0 & -1 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & -1 & -1 & -1
\end{pmatrix}$$

\begin{claim} $L(G) = B(G)(B(G))^T$ (where $^T$ denotes transpose).
\end{claim}
\begin{proof}
An entry of $B(G)(B(G))^T$ is the dot product of two rows of $B(G)$.  The dot product of
a row with itself is simply the number of nonzero entries in that row, which is equal to the
number of edges incident to that vertex.  The dot product of two different rows of $B(G)$ is 0 if there is no edge
between those two vertices, and is $-1$ if there is an edge.  So $B(G)(B(G))^T$ is in fact the Laplacian.
\end{proof}

Take a vector $x = (x_1, x_2, \ldots, x_n)^T \in R^n$.  Then we have

$$x^TLx = x^TB \cdot B^Tx = (x^TB) \cdot (x^TB)^T = \sum_{(i,j) \in E(G)} (x_i - x_j)^2$$

Let us list the facts we know about L(G).

$\ \ \ \ \ L = L^T$

$\ \ \ \ \ L = BB^T$

$\ \ \ \ \ x^TLx = \sum_{(i,j) \in E(G)}(x_i-x_j)^2, \forall x \in R^n$

$\ \ \ \ \ $All eigenvalues of $L$ are real and non-negative.  (This follows from the previous formula.)

\section{Eigenvalues of the Laplacian}

Let $\lambda_1, \lambda_2, \ldots, \lambda_n$ denote the eigenvalues of $L$, with
$\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$.  For starters, observe that $\lambda_1 = 0$,
corresponding to the eigenvector $(1,1,\ldots,1)^T$.  The eigenvalue of interest to us is $\lambda_2$.
It happens that $\lambda_2 = 0$ iff the graph $G$ is disconnected.

From here on, assume $G$ is connected.  Let us call $\lambda_2$ the {\it eigenvalue of the graph}.
Let $u = (u_1, u_2, \ldots, u_n)^T$ be an eigenvector corresponding to $\lambda_2$.  The eigenvectors of
a symmetric matrix are orthogonal, so we have $u \perp (1,1,\dots,1)^T$, so $\sum u_i = 0$.

\section{The Rayleigh quotient}

Let $x = (x_1, x_2, \ldots, x_n)^T$.  Define the {\it Rayleigh quotient} to be
$$ \phi_x = \frac{x^TLx}{x^Tx} = \frac{\sum_{(i,j) \in E(G)} (x_i-x_j)^2}{\sum x_i^2}$$
Observe that 
$$\lambda_1 = \min_{x \neq 0} \phi_x$$
and
$$\lambda_2 = \min_{x \perp (1,1,\ldots,1)^T} \phi_x.$$
Imagine we want to draw the graph $G$ along a line.  Place vertex $v_i$ at location $x_i$ on the line.
Then the numerator of the Rayleigh quotient is the sum of the squares of the lengths of the edges.
The denominator is a measure of how far from 0 we put our vertices.  If we don't make the restriction
$x \perp (1,1,\ldots,1)^T$, then we may put all of our vertices at the point 1 and get a quotient of 0.
With the restriction $x \perp (1,1,\ldots,1)^T$, the mean of the points' locations must be 0.  So 
$\lambda_2$ is a measure of how well we can place the vertices on a line so the vertices are far apart
but the total edge lengths stay relatively small.

\section{Spectral Partitioning}

The graph partitioning problem is to find a partition of the vertices of a graph into two sets $A$ and $B$
such that $E(A,B)$, the number of edges between $A$ and $B$, is small.  Without any other conditions, the problem
is trivial; just let $A$ be all of $V(G)$, and let $B$ be empty.  To avoid this sort of triviality, we generally
consider one of the following two versions of the problem.  In the {\it bisection} problem, we try to minimize 
$E(A,B)$ subject to the additional constraint that $|A| = |B| = n/2$.  Finding the best value of $E(A,B)$ for 
this problem is NP-complete, and good approximation algorithms are not known.   In the {\it ratio-partition} problem,
we allow any size sets $A$ and $B$, and we try to minimize
$$\phi(A,B) = \frac{E(A,B)}{\min(|A|, |B|)}.$$
The minimum value acheived by $\phi(A,B)$ is called the {\it isoperimetric number} of the graph.

Here's how we can use the Laplacian to find adequate solutions to these problems.  Compute $u$, the eigenvector 
of $L(G)$ corresponding to $\lambda_2$.  Treat $u$ as a one-dimensional
drawing of the graph $G$ (i.e., place vertex $v_i$ at location $u_i$ on the line).  Choose some real number
$s$, and consider the partition of the vertices given by $V_L = \{i: u_i \leq s\}$ and $V_R = \{i: u_i > s\}$.
If we want to solve the bisection problem, let $s$ be the median of the $u_i$'s.  To solve the ratio-partition
problem, consider all possible $s$ (of the $n+1$ inequivalent choices), and choose the one which gives the
best value.

\begin{theorem} [Spielman-Teng]

For all planar graphs $G$ with $n$ vertices with maximum degree $\Delta$, $\lambda_2(G) \leq \frac{8\Delta}{n}$.
\end{theorem}

\begin{theorem} [Mihail]

Let $G$ be a graph with $n$ nodes with maximum degree $\Delta$, and let $\phi$ be the isoperimetric number of G.
Then for all $x \in R^n$ with $x \perp (1,1,\ldots,1)^T$,
$$\frac{x^TLx}{x^Tx} \geq \frac{1}{2\Delta} \min_s \left(\frac{E(V_L,V_R)}{\min(|V_L|,|V_R|)}\right)^2 \geq \frac{\phi^2}{2\Delta}.$$
\end{theorem}

Putting these two results together tells us that spectral partitioning with ratio-cut when applied to a degree $\Delta$
planar graph finds a partition $(A, B)$ with $\phi(A,B) \leq \frac{4\Delta}{\sqrt{n}}$.  We'll see more about these theorems
in the next lecture.

\begin{theorem} [Lipton-Tarjan]

For any planar graph with $n$ vertices and degrees $d_i$, there exists a bisection $(A, B)$ with 
$E(A,B) \leq O(\sqrt{\sum d_i^2}) \leq \Delta\sqrt{n}$.
\end{theorem}

\begin{lemma}
Suppose $\psi$ is a monotonically decreasing function.  Suppose we have an algorithm $R$ which, for every subgraph
$G' \subset G$, finds a ratio cut of quality $\psi(|G'|)$.  Then we can use $R$ recursively to find a bisection of $G$
of size $\int_1^n \psi(x) dx$.
\end{lemma}

\begin{proof}
Imagine two buckets, each of which can hold $n/2$ vertices.  Perform a ratio-cut on the whole graph.  This cuts the graph
into two pieces, one of which contains $n/2$ or fewer vertices.  Put that chunk into one of the buckets.  Now do a
ratio-cut on the remaining piece.  Again we get two pieces; put the smaller piece in whichever bucket is less full.
Repeat this process until one bucket is full.  Put whatever is left into the other bucket.  This gives a bisection 
of the original graph $G$.

Now let us see what size cut this bisection gives us.  Let's say that the piece that gets put into a bucket on step $i$
contains $n_i$ vertices.  Let $m_i = n - \sum_{k=1}^{i-1} n_k$.  So $m_i$ is the size of the graph on which we perform a cut
on step $i$.  On step $i$, we perform a ratio cut with ratio $\psi(m_i)$ or better, and the smaller of the two pieces created
has size $n_i$.  So the number of edges that get severed on that step is at most $\psi(m_i)n_i$.  So the total number of edges
which get severed by all these cuts is at most $\sum \psi(m_i)n_i$.  The number of edges crossing our bisection is no more than
this.  And as the following picture shows, this quantity is no more than $\int_1^n \psi(x) dx$.

\includegraphics{lect7/int.eps}

\end{proof}

\section{Higher dimensional embeddings}

Recall that
$$\lambda_2 = \min_{x \perp (1,1,\ldots,1)^T} \frac{\sum_{(i,j) \in E(G)}(x_i-x_j)^2}{\sum x_i^2}.$$

Suppose instead we consider
$$\min \frac{\sum_{(i,j) \in E(G)}\|v_i-v_j\|^2}{\sum \|v_i\|^2},$$
where $v_i$ are $d$-dimensional vectors such that $\sum v_i = 0$.  We'll see next time that this also equals $\lambda_2$.
So instead of drawing our graph on a line, here we are trying to find the best way to draw our graph in $d$-space.  In the
next lecture, we'll see that the most natural way to think about planar graphs is in 3-dimensional space, on the surface
of a sphere.





\end{document}
