\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{parskip}
\usepackage{mathtools,xparse}
\spacing{1.06}

\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}
}
\DeclarePairedDelimiter{\abs}{\lvert}{\rvert}
\DeclarePairedDelimiter{\norm}{\lVert}{\rVert}
\NewDocumentCommand{\normL}{ s O{} m }{%
  \IfBooleanTF{#1}{\norm*{#3}}{\norm[#2]{#3}}_{L_2(\Omega)}%
}

\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}{\textbf{E}}
\newcommand{\var}{\text{var}}

\begin{document}

\lecture{19 -- Sublinear algorithms for graphs}{Nov 12, 2015}{Instructor:\hspace{0.08cm}\emph{Alex Andoni}}{\emph{Parthiban Loganathan}}
\section{MST Cost in Bounding Degree}

The model we will consider is a graph $G$ with $n$ vertices and total degree $d = \sum_{i=1}^n d_i$ where $d_i$ are the degrees of vertex $v_i$. We represent it with an adjacency list where each vertex points to a list of vertices and weights of the edges. Let the edge weights $\in [M]$.

We assume the graph is connected. This means the MST is well-defined and Cost of the MST $\geq n-1$.

\begin{theorem}
We can estimate MST up to a 1+$\varepsilon$ factor in $O(M^4d/\varepsilon^3)$ queries.
\end{theorem}

For example, if $M = 2$, we first look at the connected components of cost 1. If we have $C_1$ connected components,

MST = $\underbrace{n-1}_\textrm{connecting all vertices} + \underbrace{C_1-1}_\textrm{connecting connected components}$
\\

\begin{fact}
Let $C_i$ be the number of connected components on graph on edges of weight $\leq i$. Then,

MST = $n-1 + \sum_{i=1}^M C_i-1$
\end{fact}

To estimate the MST cost, we need to estimate each $C_i$ up to $\delta n$ for $\delta  = \varepsilon/M$. Note the $C_i$ are independent.
\\

\begin{lemma}[Connected Components (CC) Lemma]
For any $i \in [M]$, we can design an estimator $\hat{C_i}$ such that:
\begin{description}
\item[(1)] $|C_i - \E[\hat{C_i}]| \leq \delta n$
\item[(2)] $\var(\hat{C_i}) \leq O(\delta^2 n(C_i + \delta n))$
\item[(3)] Number of queries $\leq O(M^3d/\varepsilon^3)$
\end{description}
\end{lemma}

\subsection*{MST Algorithm}
\begin{description}
\item[(1)] For $i = 1...M-1$, estimate $\hat{C_i}$
\item[(2)] Then $\hat{MST} = n-1 + \sum_{i=1}^M \hat{C_i}-1$
\end{description}

Now let us prove the above theorem.

\begin{proof}
\item[(1)]
\begin{flalign*}
	|\E[\hat{MST}] - MST| &\leq \sum_{i=1}^n |C_i - \E[\hat{C_i}]|&\\
	&\leq \delta nM&\\
	&= \big(\frac{\varepsilon}{M}\big)nM \tag{since $\delta = \varepsilon/M$}&\\
	&= \varepsilon n &\\
\end{flalign*}

\item[(2)] 
\begin{flalign*}
	\var(\hat{MST}) &\leq \sum_{i=1}^{M-1} \var(\hat{C_i})&\\
	&\leq O(\delta^2 n \big( \sum_{i=1}^M C_i + \delta n \big)) &\\
	&\leq O(\delta^2 n (nM)) &\\
	&= O(\varepsilon^2 n^2) &\\
\end{flalign*}

Finally apply Chebhyshev's Inequality to obtain a bound with constant probability.
\end{proof}

\begin{proof}
CC Lemma Proof:

Input is a graph $H$ ($= G$ on edges with cost $\leq i$). Output is $C = C_i = $ number of connected components in $H$. Our goal is to obtain an estimator $\hat{C} \approx C$.

Define vertex $v$ such that $\alpha_v = \frac{1}{\text{size of CC of v}}$

We sample $v$ in order to estimate $\alpha_v$. To compute $\alpha_v$, we need to find size of CC of $v$ which may be the entire graph making the algorithm linear. So instead, we estimate $\alpha_v$ by thresholding it.

$\hat{\alpha_v} = max\{\alpha_v, \delta\}$

$|\sum_v \hat{\alpha_v} - \sum_v \alpha_v| \leq \delta n$

\subsection*{Algorithm to compute each $\hat{C_i}$}

\begin{description}
\item[(1)] For $i = 1...k$ where $k = 1/\delta^2$ pick random $v_i$
\item[(2)] Compute $\hat{\alpha_{v_i}}$ via Breadth First Search stopping after we see $1/\delta$ vertices
\item[(3)] $\hat{C} = \frac{n}{k} \sum_{i=1}^k \hat{\alpha_{v_i}}$
\end{description}

\begin{description}
\item[(1)]
\begin{flalign*}
	\E[\hat{C}] &= \frac{n}{k} \sum_{i=1}^k \E[\hat{\alpha_{v_i}}]&\\
	&= \sum_{i=1}^n \hat{\alpha_{v_i}} &\\
\end{flalign*}

\item[(2)]
\begin{flalign*}
	\var(\hat{C}) &= \frac{n}{k} \sum_{i=1}^n \hat{\alpha_{v_i}}&\\
	&= \frac{n}{k} \sum_{i=1}^n \hat{\alpha_{v_i}} &\\
	&= \frac{n}{k} (\underbrace{C}_{\sum \alpha_v} + \underbrace{\delta n}_{\text{max difference between $\sum \alpha_v$ and $\sum \hat{\alpha_v}$}}) &\\
	&= \frac{n}{k} (C + \delta n) &\\
\end{flalign*}

\item[(3)]
Number of queries $\leq k \times depth \times d = \frac{1}{\delta^2} \frac{1}{\delta} d = dM^3/\varepsilon^3$
\end{description}
\end{proof}

The best known bound is $O(dM\varepsilon^{-3}\log{\frac{dM}{\varepsilon}})$ [Chazelle-Rubinfeld-Trevisen].

\section{Estimating Average Degree}

Problem statement:

\begin{description}
\item[(1)] $m = n\bar{d}$ where $\bar{d}$ is the average degree
\item[(2)] Degrees are unbounded
\item[(3)] $\bar{d} \geq 1$ (ie. at least $n$ edges in $G$)
\end{description}

The trivial solution uses $O(n)$ queries by simply iterating over all vertices and computing the sum of degrees in order to find the average. To do better, we will attempt to sample some subset of vertices in order to estimate $\bar{d}$.

First, we see that we can't compute $\bar{d}$ with constant number of queries. For example, consider a case where we do not sample a very "heavy" vertex with high degree that contributes a lot to $\bar{d}$. Or consider the case where we have $\sqrt{n}$ connected vertices and $n-\sqrt{n}$ unconnected ones. The query complexity is $\Omega(\sqrt{n})$.

\begin{theorem}
We can estimate average degree $\bar{d}$ up to a $1+\varepsilon$ factor in $O(\sqrt{n}/\varepsilon^2)$ queries.
\end{theorem}

\subsection*{Algorithm to compute $\bar{d}$}
\begin{description}
\item[(1)] Sample edges $e_1,...,e_k$ iid from distribution $\{p_e\}$
\item[(2)] Estimator $\hat{d} = \frac{1}{k} \sum \frac{1}{np_e}$
\end{description}

We sample $\{p_e\}$ as follows:
\begin{description}
\item[(1)] Sample random vertex $u$ and then sample a random neighbor $v$ along edge $e = (u,v)$.
\item[(2)] Estimator $\hat{d} = \frac{1}{k} \sum \frac{1}{np_e}$
\end{description}

Let $u$ and $v$ have degree $d_u$ and $d_v$ respectively. Probability of sampling a vertex $u$ is $1/n$. Probability of then sampling a neighbor is $1/d_u$. Hence $p_e = \frac{1}{nd_u} + \frac{1}{nd_v}$.

\begin{flalign*}
	p_e &= \frac{1}{nd_u} + \frac{1}{nd_v}&\\
	&\geq \frac{1}{n} \max\{1/d_u, 1/d_v\}&\\
	\implies &\frac{1}{p_e} \leq n \min\{d_u, d_v\}&\\
\end{flalign*}

Need to show:
\begin{description}
\item[(1)] $\E[\hat{d}] = \bar{d}$
\item[(2)] $\var(\hat{d}) = \frac{1}{k} \var(\frac{1}{np_e})$
\end{description}

\begin{flalign*}
	var\Big(\frac{1}{np_e}\Big) &\leq \E\Big[\Big(\frac{1}{np_e}\Big)^2\Big]&\\
	&= \frac{1}{n^2} \sum_{e} \frac{p_e}{p_e^2}&\\
	&= \frac{1}{n^2} \sum_{e} \frac{1}{p_e}&\\
	&\leq \frac{1}{n^2} n \sum_{e=(u,v)} \min\{d_u,d_v\}&\\
\end{flalign*}

Attempt 1: This does not work.

\begin{flalign*}
	var\Big(\frac{1}{np_e}\Big) &\leq \frac{1}{n} \sum_{e=(u,v)} \min\{d_u,d_v\}&\\
	&\leq \frac{1}{n} \sum_{u} d_u^2&\\
	&\leq \frac{1}{n} \big(\frac{m}{n}n^2\big) \tag{in the case where each vertex has degree $m$}&\\
	&= m&\\
\end{flalign*}

$\var(\hat{d}) = \frac{1}{k} \var(\frac{1}{np_e}) = \frac{m}{k}$

$\implies \hat{d} = \bar{d} \pm \sqrt{\frac{m}{k}}$

We want $\var(\hat{d}) \leq \varepsilon\bar{d}$

\begin{flalign*}
	\sqrt{\frac{m}{k}} &\leq \varepsilon \bar{d}&\\
	\implies k &\geq \frac{n\bar{d}}{\varepsilon^2 \bar{d}^2}&\\
	&= \frac{1}{\varepsilon^2} \frac{n}{\bar{d}}&\\
\end{flalign*}

If $\bar{d} = 10$ for example, $k \approx n$ and it's linear. Hence this attempt fails.

Attempt 2: There are at most $m/M$ vertices with degree $\geq M$. Let us call them heavy nodes.

\begin{flalign*}
	\var\Big(\frac{1}{np_e}\Big) &\leq \frac{1}{n} \sum_{e=(u,v)} \min\{d_u,d_v\}&\\
	&= \frac{1}{n} \sum_{u} \sum_{v} \min\{d_u,d_v\}&\\
	&= \frac{1}{n} \underset{\text{either $u$ or $v$ not heavy}}{\sum_{u} \sum_{v}} M + \frac{1}{n} \underset{v\text{ is heavy}}{\sum_{u} \sum_{v}} d_u&\\
	&\leq \frac{1}{n} mM + \frac{1}{n}\sum_{u} d_u \frac{m}{M}&\\
	&\leq \frac{m}{n}(M + \frac{m}{M})&\\
	&\leq \frac{m}{n}\sqrt{m}&\\
\end{flalign*}

If degree was constant $m = n$, $\var\Big(\frac{1}{np_e}\Big) \leq \sqrt{m}$.

In general, $\hat{d} = \bar{d} \pm \sqrt{\frac{m^{3/2}}{nk}} = \bar{d} \pm \varepsilon\bar{d}$ for $k = \frac{n}{\sqrt{m}\varepsilon^2}$.

\end{document}