\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{listings}
\usepackage{setspace}
\usepackage{graphicx} %package to manage images
\graphicspath{ {images/} }

\spacing{1.06}


\lstset{
  basicstyle=\ttfamily,
  mathescape
}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS E6998-9:\hspace{0.12cm}Algorithmic
          Techniques for Massive Data} \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}{Scribe:\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}{\textbf{E}}
\newcommand{\var}{\text{var}}


\begin{document}

\lecture{6 : Counting triangles, Dynamic graphs \& sampling}{Sep 24, 2015}{Instructor:\hspace{0.08cm}\emph{Alex Andoni}}{\emph{Patanjali Vakhulabharanam}}

\section*{Plan}
\begin{itemize}
\item Counting triangles
\item Streaming for dynamic graphs
\end{itemize}

\section{Streaming for graphs(recap)}
Consider a graph with
\begin{itemize}
\item n vertices
\item m edges
\end{itemize}
which is represented as a stream of list of edges, stored somewhere like on a hard drive. We can sequentially access this data to generate a stream.
Number of edges m could be $O(n^2)$
If we have a limited working memory and are trying to process the edge stream, we would like to get an algorithm that uses space 
\begin{itemize}
\item $O(n)$
\item $O(n \log n)$ which is still much better than $O(n^2)$
\end{itemize}
Acheiving $<<n$ is usually not possible.
\subsection{Problems}
\begin{enumerate}
\item Connectivity
\begin{itemize}
\item Exact in $O(n)$ space
\end{itemize}
\item Distances
\begin{itemize}
\item $\alpha$ (odd) approximation in $O\left(n^{1+\frac{2}{\alpha + 1}}\right)$
\end{itemize}
\item Count \# of triangles
\end{enumerate}
\section{Triangle counting}
Let T = number of triangles in the graph\\
Physical motivation - To answer some questions like 
\begin{itemize}
\item How often do two friends of a person know each other
\end{itemize}
Define this fraction as 
$$F = \frac{T}{3\sum_v {deg(v) \choose 2}}$$\\
$F \in [0,1]$\\
\begin{itemize}
\item Denominator
\begin{itemize}
\item It is possible to measure the denominator by just counting the degrees of vertices
\item $O(n)$ space required to do this
\end{itemize}
\item Numerator T
\begin{itemize}
\item Measuring the numerator is harder
\item It is not possible to distinguish $T=0$ from $T=1$ in $<<m$ space
\item Suppose we have a lower bound $t \le T$
\end{itemize}
\end{itemize}
\subsection{Triangle counting : Approach}
Define a vector $x$ which has a coordinate $x_S$ for each subset $S$ of three nodes. The value of this coordinate is
\begin{itemize}
\item $x_S = $ number of edges among vertices in $S$
\item $T = $ number of coordinates in x that have value of 3
\end{itemize}
We had earlier defined frequencies as
\begin{itemize}
\item $F_p = \sum_S {x_{S}^{p}}$
\end{itemize}
{\em Claim :} $T = F_0 - 1.5F_1 + 0.5F_2$\\
This is equivalent to writing \\
$\sum_S { \chi [X_S \ne 0]} - 1.5\sum_S X_{S}^{1} + 0.5\sum_S X_{S}^{2} = \sum_S { \chi [X_S = 3]}$\\
{\em Proof}\\
\begin{itemize}
\item $X_S = 0$ contribute 0 to both LHS and RHS
\item $X_S = 1$ contribute 0 to both LHS and RHS
\begin{itemize}
\item LHS evaluates to $1-1.5*1+0.5*1^2 = 0$
\end{itemize}
\item $X_S = 2$ contribute 0 to both LHS and RHS
\begin{itemize}
\item LHS evaluates to $1-1.5*2+0.5*2^2 = 0$
\end{itemize}
\item $X_3 = 3$ contributes 1 to RHS
\begin{itemize}
\item LHS evaluates $1-1.5*3+0.5*3^2=1$
\end{itemize}
We can generate such a formula because of polynomial interpolation.
\begin{itemize}
\item We need a polynomial $f({X_S})$ that evaluates to 0 on $\{0,1,2\}$ and evaluates to 1 on $\{3\}$
\item Use polynomial interpolation!
\item We ideally need a polynomial of degree 3 but we get one degree of freedom from $F_0$ so 2 is enough.\\
\end{itemize}
\end{itemize}
{\em Algorithm}\\
\begin{itemize}
\item Let $\hat {F_0}, \hat {F_1}, \hat {F_2}$ be $1+\gamma$ estimates
\item Stream the edges to generate updates for $X_S$
\begin{itemize}
\item For each edge $e = (i,j)$
\item Generate S that contain these two nodes
\item For each $S = \{i,j,k\}$, set $X_S = X_S + 1$
\item This is the rule $(S,+1)$
\end{itemize}
\item Estimate $\hat T = \hat {F_0} - 1.5*{\hat F_1} + 0.5*{\hat F_2}$
\item The errors for each of the terms cannot be directly added. We use the following inequalities
\begin{itemize}
\item $|\hat {F_0} - F_0| < \gamma F_0$
\item $|\hat {F_1} - F_1| < \gamma F_1 \le 3\gamma F_0$
\item $|\hat {F_2} - F_2| < \gamma F_2 \le 9\gamma F_0$
\end{itemize}
\item Using the above, we get error in $\hat T = O(\gamma F_0) = O(\gamma mn)$
\item Therefore we can set $\gamma = \frac{O(t)}{\epsilon mn} $ for a $\pm \epsilon t$ additive error
\item Total space required is $$O(\gamma^{-2} \log n) = O\left(\left(\frac{mn}{\epsilon t}\right)^2 \log n \right)$$
\end{itemize}
{\em Algorithm 2} Let us consider an even simpler algorithm that the previous one
\begin{itemize}
\item Pick a few random $S_i$ for $i \in [k]$of 3 nodes
\item Compute $X_{S_i}$ for $i \in [k]$
\item Let c be the number of i such that $X_{S_i} = 3$
\item Estimate $R = \frac{M}{k}*c$ where $M = {n \choose 3}$
\item Mean of R is 
\begin{align*}
E[R] &= E[\frac{M}{k}*c] \\
&= E[\frac{M}{k}*\sum_S \left(\chi [X_S = 3]*\chi [S\; is\; sampled]\right)]\\
&= \frac{M}{k}*\frac{k}{M}*T\\
&= T
\end{align*}
\item Variance of R is
\begin{align*}
Var[R] &= \sum_S {Var[\frac{M}{k}*\chi[X_S = 3]*\chi[S\; is\; sampled]]}\\
&\le \sum_{S|X_S=3} {\left(\frac{M}{k}\right)^2*Probability(S\;is\;sampled)}\\
&= \frac{M^2}{k^2}*\frac{k}{M}*T\\
&= \frac{TM}{k}
\end{align*}
\item Using Chebyshev's inequality, we get $|R-T| \le O\left(\sqrt {\left (\frac{MT}{K} \right)} \right)$
\item We need $k = \frac{O(1)}{\epsilon ^2} * \frac{M}{t} = O\left(\frac{1}{\epsilon ^ 2} * \frac{n^3}{t}\right)$, since $M = O(n^3)$
\end{itemize}
{\em Algorithm 2+}
\begin{itemize}
\item The previous algorithm can be improved by choosing S more selectively rather than randomly.
\item Pick only those S for which $X_S \ge 1$
\item The size of this set will be $M' << M$
\item Using Chebyshev's inequality on this, we get
\begin{itemize}
\item $|R-T| \le O\left(\sqrt {\left (\frac{M'T}{K} \right)} \right)$
\end{itemize}
\item Using this and $M' = O(mn)$, we get
\begin{itemize}
\item $k = \frac{O(1)}{\epsilon ^2} * \frac{M'}{t} = O\left({\frac{1}{\epsilon ^2} * \frac{mn}{t}}\right)$
\end{itemize}
\end{itemize}
\section{Sampling in graphs}
\begin{itemize}
\item Setting 1
\begin{itemize}
\item Updates are only positive
\item Not linear
\end{itemize}
\item Setting 2
\begin{itemize}
\item General streaming : Also include negative updates
\item This is motivated by dynamic graphs were connections can get added as well as deleted
\end{itemize}
\end{itemize}
Dynamic grahps - Streams can contain both insertions and deletions of edges. There are several use cases for such graphs
\begin{itemize}
\item Use 1 : Log file of updates to the graph
\begin{itemize}
\item A graph of a social network can have people "unfriending"
\item A graph of webpage hyperlinks can have links being added as well as deleted, etc
\end{itemize}
\item Use 2 : Graph is distributed over a number of computers
\begin{itemize}
\item We will then want linear sketches
\item In general dynamic streams and linear sketches go together
\end{itemize}
\item Use 3 : If the algorithm is time efficient, it can also be considered a data structure. This makes it interesting to areas that are beyond just algorithms.
\end{itemize}
\section{Revisiting connectivity}
\begin{itemize}
\item Can we do connectivity in dynamic graphs using the algorithm from previous lecture?
\item No
\begin{theorem}
We can check s-t connectivity in dynamic graphs with $O(n log^5 n)$ space (with 90\% success probability)
\end{theorem}
\end{itemize}
Approach : Use sampling in (dynamic) graphs
We wll first look at a sub problem - dynamic sampling
\section{Dynamic sampling}
Problem
\begin{itemize}
\item General updates to a vector $x \in \{-1,0,1\}^n$
\begin{itemize}
\item This will also work for a general x
\end{itemize}
\item Goal : Output i with probability $\frac{|x_i|}{\sum_j|x_j|}$
\item Does standard sampling work?
\begin{itemize}
\item No : For instance consider this. After putting $x_i = 1$ for $n/2$ coordinates, add 1 more and delete the first $n/2$
\end{itemize}
\item Let $A = \{i such that x_i \ne 0\}$
\item Intuition
\begin{itemize}
\item Suppose $|A|=10$.
\begin{itemize}
\item How do we sample i with only non zero $x_i$
\item Notice that each of the $x_i$ which are non zero are $\frac{1}{10}$ heavy hitters 
\item Therefore using CountSketch, we can recover all of them
\item $O(\log n)$ space is required for this
\end{itemize}
\item Suppose $A = n/10$
\begin{itemize}
\item Downsample first - Pick a random subset $D \subset [n]$ of size $|D| \approx 100$
\item Focus on a substream $i \in D$ only and ignore the rest
\item $E[|A \cap D|] = 10$
\item Use CountSketch on the downsampled stream
\end{itemize}
\item In general, prepare for all levels
\end{itemize}
\end{itemize}
\end{document}