\documentclass[10pt]{article}
\newtheorem{define}{Definition}
\newcommand{\D}{\mathbf{D}}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{automata,positioning}
\usetikzlibrary{decorations.pathmorphing,shapes}
\usepackage{amssymb}
\usepackage{amsmath}




\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{3}{February 13, 2019}{Ronitt Rubinfeld}{Matthew Thomas Sturm}

%%%% body goes in here %%%%


\section{Outline}
Today we will continue discussing \textbf{estimating the average degree of a graph}:
\begin{itemize}
\item Setup and Review from Last Time
\item Estimate Average Degree: First Attempt (using only degree queries)
\item Estimate Average Degree: Second Attempt (now using neighbor queries as well)
\end{itemize}

\section{Setup and Review from Last Time}

The goal of this problem is to find an algorithm that will estimate the average degree of a graph in sublinear time. What we are given is a vector of the degrees of each node as well as the graph in adjacency list representation. Thus, our algorithm must sample the vector of degrees and the adjacency list to form its approximation. As a note about our adjacency list representation, we have the ability to not only query a node for a linked list of its neighbors, but we can query a node for an array of its neighbors, and thus are able to query the $j^{\text{th}}$ neighbor of a node in $O(1)$ time. As a reminder from last time, we provide the following definitions and assumptions:

\begin{definition}
The average degree of a graph $G = (V, E)$ is defined as
\[\overline{d} = \frac{\sum_{u\in V}d(u)}{n}.\]
\end{definition}

\begin{assumption}\label{asm: Setup}
We assume that $G$ is simple, i.e., that it has no parallel edges or self-loops. In addition, we will assume that $G$ has no nodes of degree zero/ no isolated nodes\footnote{The assumption that $G$ has no nodes of degree zero is not required for the analysis to follow but is included here for simplicity. The reader may remove this assumption and check that the analysis still goes through.}. Next, we assume that $G$ is not ``ultra-sparse'', i.e., we assume that the number of edges in $G$ is $\Omega(n)$. Finally, our representation for $G$ will allow the two following types of queries:
\begin{itemize}
    \item \textbf{Degree Queries:} We can query the degree of any node in $O(1)$ time. 
    \item \textbf{Neighbor Queries:} We can query the $j^{\textrm{th}}$ neighbor of any node in O(1) time. 
\end{itemize}
\end{assumption}

In order to approximate the degree, the first idea that might come to mind is simply Naive Sampling: sample $S$ nodes from $G$ and output $\frac{1}{S}\sum_{v\in S} d(v)$. The problem with this is that when using straightforward Chernoff/ Hoeffding analysis, we would need $\Omega(n)$ samples to get the estimates we want. 

\subsection{Estimating the Average Value of a Vector}

It is worth noting that in the general case, it is not possible to reasonably estimate the average value of a vector in linear time. For example, with a vector such as
\[\langle 0, 0, \cdots, n-1, \cdots, 0, 0\rangle,\]
while the average value is really approximately one, any estimate that runs in sublinear time will very likely conclude the average value is zero. 

However, the problem of estimating the average value of a graph \textit{is} possible because graphs must have additional structure that arbitrary vector may not. For example, while the vector of degrees might be 
\[\langle 1, 1, \cdots, n-1, \cdots, 1, 1 \rangle,\]
it is just not possible for the vector of degrees to be 
\[\langle 0, 0, \cdots, n-1, \cdots, 0, 0 \rangle;\]
if a node has high degree, then those edges must be accounted for on other nodes as well. Thus, this motivates the intuition that due to this extra structure that must exist in a graph, we might be able to achieve an estimate with something like a multiplicative error of two in sublinear time. 

\subsection{Lower Bounds}

\subsubsection{The ``Ultra-Sparse'' Case}

Suppose we needed to distinguish between a graph with no edges at all, and thus average degree zero, and a graph with a single edge, and thus average degree $2/n$. 

\begin{figure}[!htbp]
\centering
\begin{tikzpicture}[font=\sffamily]

        % Setup the style for the states
        \tikzset{node style/.style={state, 
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=gray!10!white}}

        % Draw the states
        \node[node style] at (0, 2.8)         (a)     {};
        \node[node style] at (-1, 2)     (b)     {};
        \node[node style] at (-1, 0.8)     (c)     {};
        \node[node style] at (0, 0)     (d)     {};
        \node[node style] at (1, 0.8)     (e)     {};
        \node[node style] at (1, 2)     (f)     {};
        \node[node style] at (0, 1.4)     (g)     {};
        \node[node style] at (6, 2.8)         (aa)     {};
        \node[node style] at (5, 2)     (bb)    {} ;
        \node[node style] at (5, 0.8)     (cc)     {};
        \node[node style] at (6, 0)     (dd)     {};
        \node[node style] at (7, 0.8)     (ee)     {};
        \node[node style] at (7, 2)     (ff)     {};
        \node[node style] at (6, 1.4)     (gg)     {};
        \draw[thick, line width=0.5mm,] (dd) -- (ee);
    \end{tikzpicture}
    \caption{\label{fig:ultra_sparse} We compare an ``ultra-spare'' graph with no edges to one with a single edge.}
\end{figure}

In the second case, we would clearly need $\Omega(n)$ time to find the edge, so any sublinear time algorithm would very likely approximate the degree to be zero, which not within any multiplicative factor of $2/n$. 

Thus, in the ``Ultra-Sparse'' case we would need $\Omega(n)$ time, which is why we require that $G$ is not ``ultra-sparse'' in Assumption \ref{asm: Setup}.

\subsubsection{Finding a $\sqrt{n}$-clique}

Suppose we need to distinguish between a graph that is just an $n$-cycle, and one that consists of a $n-c\sqrt{n}$ cycle and a $c\sqrt{n}$-clique.

\begin{figure}[!htbp]
\centering
\begin{tikzpicture}[font=\sffamily]

        % Setup the style for the states
        \tikzset{node style/.style={state, 
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=gray!10!white}}

        % Draw the states
        \node[node style] at (0.5, 3)         (a)     {};
        \node[node style] at (-0.5, 3)     (b)     {};
        \node[node style] at (-1.2, 2.4)     (c)     {};
        \node[node style] at (-1.5, 1.5)     (d)     {};
        \node[node style] at (-1.2, 0.6)     (e)     {};
        \node[node style] at (-0.5, 0)     (f)     {};
        \node[node style] at (0.5, 0)     (g)     {};
        \node[node style] at (1.2, 0.6)     (h)     {};
        \node[node style] at (1.5, 1.5)     (i)     {};
        \node[node style] at (1.2, 2.4)     (j)     {};
        \node[node style] at (6, 2.8)         (aa)     {};
        \node[node style] at (5, 2)     (bb)    {} ;
        \node[node style] at (5, 0.8)     (cc)     {};
        \node[node style] at (6, 0)     (dd)     {};
        \node[node style] at (7, 0.8)     (ee)     {};
        \node[node style] at (7, 2)     (ff)     {};
        \node[node style] at (8.2, 1)     (gg)     {};
        \node[node style] at (8.2, 0)     (hh)     {};
        \node[node style] at (9.2, 0)     (ii)     {};
        \node[node style] at (9.2, 1)     (jj)     {};
        \draw[thick, line width=0.5mm,] (a) -- (b);
        \draw[thick, line width=0.5mm,] (b) -- (c);
        \draw[thick, line width=0.5mm,] (c) -- (d);
        \draw[thick, line width=0.5mm,] (d) -- (e);
        \draw[thick, line width=0.5mm,] (e) -- (f);
        \draw[thick, line width=0.5mm,] (f) -- (g);
        \draw[thick, line width=0.5mm,] (g) -- (h);
        \draw[thick, line width=0.5mm,] (h) -- (i);
        \draw[thick, line width=0.5mm,] (i) -- (j);
        \draw[thick, line width=0.5mm,] (j) -- (a);
        \draw[thick, line width=0.5mm,] (aa) -- (bb);
        \draw[thick, line width=0.5mm,] (bb) -- (cc);
        \draw[thick, line width=0.5mm,] (cc) -- (dd);
        \draw[thick, line width=0.5mm,] (dd) -- (ee);
        \draw[thick, line width=0.5mm,] (ee) -- (ff);
        \draw[thick, line width=0.5mm,] (ff) -- (aa);
        \draw[thick, line width=0.5mm,] (gg) -- (hh);
        \draw[thick, line width=0.5mm,] (gg) -- (ii);
        \draw[thick, line width=0.5mm,] (gg) -- (jj);
        \draw[thick, line width=0.5mm,] (hh) -- (ii);
        \draw[thick, line width=0.5mm,] (hh) -- (jj);
        \draw[thick, line width=0.5mm,] (ii) -- (jj);
    \end{tikzpicture}
    \caption{\label{fig:sqrt_n_clique} We compare an $n$-cycle to  a $n-c\sqrt{n}$ cycle and a $c\sqrt{n}$-clique}
\end{figure}

While the $n$-cycle will have average degree of two, the $n-c\sqrt{n}$ cycle and $c\sqrt{n}$-clique will have average degree
\[\overline{d} = \frac{(n-c\sqrt{n})(2) + (c\sqrt{n})(c\sqrt{n} - 1)}{n} = 2 + c^2 - 3\frac{c}{\sqrt{n}} \approx 2 + c^2.\]
Thus, the two graphs differ in average degree by about $c^2$, and it will take $\Omega(\sqrt{n})$ time before we expect to sample nodes from the $c\sqrt{n}$-clique. Thus, any algorithm we find that approximating the average degree within a small multiplicative factor must run in $\Omega(\sqrt{n})$ time.

\subsection{Bucketing}

Because simply sampling random nodes will not work, we need another strategy. One of the main ideas of the algorithm to come is the technique of \textit{bucketing}; we create buckets that contain nodes of similar degree. Then, the goal of our algorithm will be to estimate the average degree by getting an estimate of the size of each bucket. One advantage here is that each group of nodes will now have bounded variance. 

More rigorously, we will define $t = O\left(\frac{\log n}{\epsilon}\right)$ buckets and let $\beta = \epsilon / c$ for some constant $c$. We then let bucket $B_i$ be defined as
\[B_i = \{v | (1+\beta)^{i-1} < d(v) \leq (1+\beta)^i\}\,\,\textrm{for}\,\,i\in\{0,\cdots,t-1\}.\]
We note that $B_1, B_2, \cdots$ may be empty for small $i$, but this is not a problem, and we will just be concerned with large enough values of $i$ such that $B_i$ is nonempty. 

Next, because we can say that the total degree of the nodes in $B_i$, call this $d_{B_i}$, satisfies 
\[(1+\beta)^{i-1}|B_i|\leq d_{B_i}\leq (1+\beta)^i|B_i|,\]
it follows that 
\[\sum_{i=0}^{t-1}(1+\beta)^{i-1}|B_i|\leq\sum_{u\in V}d(u)\leq \sum_{i=0}^{t-1}(1+\beta)^i|B_i|,\]
and further that
\[\frac{\sum_{i=0}^{t-1}(1+\beta)^{i-1}|B_i|}{n}\leq\overline{d} \leq \frac{\sum_{i=0}^{t-1}(1+\beta)^i|B_i|}{n}.\]
Thus, if we can estimate $|B_i|/n$, we can estimate $\overline{d}$.

\section{Estimate Average Degree: First Attempt (using only degree queries)}

Now that we have set up the problem, we present our first attempt at an algorithm to solve the problem:

\begin{algorithm}[!h]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{Vector of degrees $d$}
  \Output{$\hat{\overline{d}}$}
  Take sample $S$ from $d$ \;
  $S_i \leftarrow S\cap B_i$ \;
  $\rho_i \leftarrow |S_i|/|S|$ (estimate degree contribution from $B_i$) \;
  Return $\sum_{i=0}^t\rho_i(1+\beta)^{i-1}$
    \caption{Average Degree Approximator}
    \label{alg:try_1.1}
\end{algorithm}

Here we use the notation $\hat{\overline{d}}$ as our estimate for $\overline{d}$. As some notes about the algorithm, first note that 
\[E[\rho_i] = E\left[\frac{|S_i|}{|S|}\right] = \frac{1}{|S|}E\left[\sum_{j=1}^{|S|}X_j^{(i)}\right] = \frac{1}{|S|}\left(|S|\frac{|B_i|}{n}\right) = \frac{|B_i|}{n},\]
as we would hope (where $X_j^{(i)}$ is the Bernoulli random variable that equals one if the $j^{\textrm{th}}$ sample in $S$ is in bucket $B_i$). Note also that in choosing to output $\sum_{i=0}^t\rho_i(1+\beta)^{i-1}$, we will be underestimating $\overline{d}$.  

\subsection{The Problem with Small Buckets}

One problem that becomes apparent with this algorithm is that the size of very small buckets will likely be poorly estimated by $|S_i|$. To illustrate this, consider the following example. 

\begin{figure}[!htbp]
\centering
\begin{tikzpicture}[font=\sffamily]

        % Setup the style for the states
        \tikzset{node style/.style={state, 
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=gray!10!white}}

        % Draw the states
        \node[node style] at (0, 3)         (a)     {};
        \node[node style] at (0, 2)     (b)     {};
        \node[node style] at (0, 1)     (c)     {};
        \node[node style] at (0, -1)     (d)     {};
        \node[node style] at (2, 2)     (e)     {};
        \node[node style] at (2, 1)     (f)     {};
        \node[node style] at (2, 0)     (g)     {};

        \draw[thick, line width=0.5mm,] (a) -- (e);
        \draw[thick, line width=0.5mm,] (a) -- (f);
        \draw[thick, line width=0.5mm,] (a) -- (g);
        \draw[thick, line width=0.5mm,] (b) -- (e);
        \draw[thick, line width=0.5mm,] (b) -- (f);
        \draw[thick, line width=0.5mm,] (b) -- (g);
        \draw[thick, line width=0.5mm,] (c) -- (e);
        \draw[thick, line width=0.5mm,] (c) -- (f);
        \draw[thick, line width=0.5mm,] (c) -- (g);
        \draw[thick, line width=0.5mm,] (d) -- (e);
        \draw[thick, line width=0.5mm,] (d) -- (f);
        \draw[thick, line width=0.5mm,] (d) -- (g);

        \path (c) -- node[auto=false]{\Huge \vdots} (d);
    \end{tikzpicture}
    \caption{\label{fig:bipartite} We consider a complete bipartite graph with $n-3$ nodes on the left and three nodes on the right.}
\end{figure}

In the case of the complete bipartite graph with one group of $n-3$ nodes and the other with three, the average degree will be 
\[\overline{d} = \frac{(n-3)(3) + (3)(n-3)}{n} = 6 - \frac{18}{n} \approx 6.\]
However, our algorithm is very likely not going to sample the three nodes on the right and will estimate the average degree to three. In particular, let us choose $a$ to be the integer such that 
\[(1+\beta)^{a-1}<3\leq(1+\beta)^{a+1}\]
and $b$ such that 
\[(1+\beta)^{b-1}<n-3\leq(1+\beta)^{b+1}.\]
This will give us that $|B_a| = n-3$ and that $|B_b| = 3$ (and that $|B_i| = 0$ for all other $i$), and thus with high probability (with a sublinear sample size) our algorithm will set $\rho_a = 1$ and return $\hat{\overline{d}} = 3$. The problem here is that $B_b$ contributes $3(n-3)$ to the total degree of the graph, which is half of all edges, but won't be sampled at all! 

From this, we can get a sense that if we only use degree queries, we will not be able to do much better than a $2$-approximation. If we wish to do better, we will have to also use neighbor queries, which will be covered in the next section. 

\subsection{Addressing the Problem of Small Buckets}

We now present an updated version of algorithm \ref{alg:try_1.1} where we address the problem of small buckets. In particular, we simply set $\rho_i = 0$ if $|S_i|$ is ``small'' and argue that if some buckets are small enough, it is okay to ignore them (you can think of the intuition for setting $\rho_i = 0$ for ``small'' $|S_i|$ as a way to make the analysis easier, because we don't need to consider the very small buckets anyway). In addition, we now address how large we need to make $|S|$ with explanations and analysis to follow. 

\begin{algorithm}[H]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{Vector of degrees $d$}
  \Output{$\hat{\overline{d}}$}
  Take sample $S$ from $d$, where $|S| = \Theta(\sqrt{n} \cdot poly(\log n) \cdot poly(1/\epsilon))$\;
  $S_i \leftarrow S\cap B_i$ \;
  \For{all $i \in\{0,\cdots, t-1\}$} 	
    {\If{$|S_i| \geq \sqrt{\epsilon / n}|S|/(c\cdot t)$ ($|S_i|$ is not ``small'')}
      {$\rho_i \leftarrow |S_i|/ |S|$}
    \Else
      {$\rho_i \leftarrow 0$}}
  Return $\sum_{i=0}^t\rho_i(1+\beta)^{i-1}$
    \caption{Average Degree Approximator (updated)}
    \label{alg:try_1.2}
\end{algorithm}

\vspace{5mm}

We now justify why we chose the sample $S$ to be the size we did. In particular, we want the result that for all of the ``big'' buckets $B_i$, $|S_i|$ is a good approximation for $|B_i|$. More specifically, for $\gamma = \Theta(\epsilon)$, we would like 
\[(1-\gamma)\frac{|B_i|}{n}\leq \rho_i \leq (1+\gamma)\frac{|B_i|}{n}\]
with probability greater than $1 - 1/(\textrm{const}\cdot \log n)$ for $i$ such that $|S_i|$ is ``large''. In order to get this by union and Chernoff bound, it would suffice to have 
\[|S_i| \geq \Omega(poly(\log n)\cdot poly(1/\epsilon)).\]
Thus, if we need the cutoff between ``big'' and ``small'' to be
\[|S_i| \geq \sqrt{\epsilon / n}|S|/(c\cdot t)\]
as we set in the algorithm, we need 
\[|S| > t\sqrt{\frac{n}{\epsilon}},\]
and specifically may choose 
\[|S| = \Theta(\sqrt{n} \cdot poly(\log n) \cdot poly(1/\epsilon))\]
as we did. (Why we choose the cutoff between ``big'' and ``small'' for $|S_i|$ where we did will be seen in the analysis).

\subsection{Analysis}

\subsubsection{Output Not Too Large}

We will first argue that, with high probability, the output will not be too large. First, consider the unrealistic case where for all $i$, $\rho_i$ is a perfect estimate and $\rho_i = |B_i|/n$. Here, we will have that
\[\sum_{i=0}^{n-1}\rho_i(1+\beta)^{i-1} = \sum_{i=0}^{n-1}\frac{|B_i|}{n}(1+\beta)^{i-1} \leq \overline{d}.\]
However, recall that we chose the size of $|S|$ such that, with high probability, 
\[(1-\gamma)\frac{|B_i|}{n}\leq \rho_i \leq (1+\gamma)\frac{|B_i|}{n}.\]
Thus, we may suppose that in a realistic case we will have $\rho_i \leq (1+\gamma)\frac{|B_i|}{n}$ for all $i$, and thus will have that 
\[\sum_{i=0}^{n-1}\rho_i(1+\beta)^{i-1} \leq \sum_{i=0}^{n-1}(1+\gamma)\frac{|B_i|}{n}(1+\beta)^{i-1} \leq (1+\gamma)\overline{d},\]
i.e., that with high probability, our output is not more than a factor of $(1+\gamma)$ larger than the true average degree of the graph. 

\subsubsection{Output Not Too Small}

We next argue that, with high probability, the output will not be too small. First, we again consider the unrealistic case where for all $i$, $\rho_i$ is a perfect estimate and $\rho_i = |B_i|/n$. Here, we will have that
\[\sum_{i=1}^{t-1}\rho_i(1+\beta)^{i-1} = \sum_{i=1}^{t-1}\frac{|B_i|}{n}(1+\beta)^{i-1} \geq (1 - \beta)(1+\beta) \sum_{i=1}^{t-1}\frac{|B_i|}{n}(1+\beta)^{i-1} \geq (1 - \beta) \sum_{i=1}^{t-1}\frac{|B_i|}{n}(1+\beta)^{i} \geq (1-\beta)\overline{d}.\]
Now considering a realistic case, we first consider the buckets such that $|B_i|$ is ``large''. We again have that with high probability, due to our choice of the size of $|S|$, $\rho_i \geq (1-\gamma)|B_i|/n$ for all $i$ such that $|B_i|$ is large\footnote{If $|B_i|$ is ``large'', then we expect both that $|S_i|$ is large enough such that $|S_i|\geq \sqrt{\epsilon / n}|S|/(c\cdot t)$, setting $\rho_i\gets|S_i|/|S|$ rather than $\rho\gets 0$, and that $\rho_i \geq (1-\gamma)|B_i|/n$ specifically.}. Thus, if all nonempty buckets were ``large'', we would have that 
\[\sum_{i=1}^{t-1}\rho_i(1+\beta)^{i-1} \geq \sum_{i=1}^{t-1}(1-\gamma)\frac{|B_i|}{n}(1+\beta)^{i-1} \geq (1 - \beta) \sum_{i=1}^{t-1}(1-\gamma)\frac{|B_i|}{n}(1+\beta)^{i} \geq (1-\beta)(1-\gamma)\overline{d},\]
and we would be done. However, we must now consider the buckets that are ``small''. The danger is that by ignoring the ``small'' buckets, we may be undercounting too much and thus get a result that is too small. 

\subsubsection{How Much are We Undercounting?}

We will split our edges up into the following three groups\footnote{Here we mean that a bucket is ``big'' if the algorithm classified it as big by finding $|S_i| \geq \sqrt{\epsilon / n}|S|/(c\cdot t)$ for that particular sample, and small otherwise. Thus, the classification of an edge into one of these three groups could vary depending on the run of the algorithm.}:
\begin{itemize}
    \item \textbf{big-big:} Edges with both endpoints in ``big'' buckets
    \item \textbf{big-small} Edges with one endpoint in a ``big'' bucket and one is a ``small''
    \item \textbf{small-small} Edges with both endpoints in ``small'' buckets
\end{itemize}
Thus, we can see that our algorithm will count the big-big edges twice, count the big-small edges once, and miss the small-small edges entirely. Thus, if we are aiming for a factor of two estimate, the big-big and big-small edges are not a problem, but the small-small edges could cause trouble. 

To illustrate what these three categories of edges might look like, consider the following example. 

\clearpage

\begin{figure}[h!]
\centering
\begin{tikzpicture}[font=\sffamily]

        % Setup the style for the states
        \tikzset{node style/.style={state, 
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=gray!10!white}}

        % Draw the states
        \node[node style] at (0, 3)         (aa)     {};
        \node[node style] at (0, 2)     (bb)     {};
        \node[node style] at (0, 1)     (cc)     {};
        \node[node style] at (0, -1)     (dd)     {};
        \node[node style] at (0, -2)     (ee)     {};
        \node[node style] at (2, 1.5)     (ff)     {};
        \node[node style] at (2, 0.5)     (gg)     {};
        \node[node style] at (2, -0.5)     (hh)     {};
        
        \node[node style] at (4, -1)     (h)     {};
        \node[node style] at (5, -1)     (i)     {};
        \node[node style] at (3.7, -0.1)     (j)     {};
        \node[node style] at (5.3, -0.1)     (k)     {};
        \node[node style] at (4.5, 0.5)     (l)     {};

        \draw[thick, blue, line width=0.5mm,] (aa) -- (ff);
        \draw[thick, blue, line width=0.5mm,] (aa) -- (gg);
        \draw[thick, blue, line width=0.5mm,] (aa) -- (hh);
        \draw[thick, blue, line width=0.5mm,] (bb) -- (ff);
        \draw[thick, blue, line width=0.5mm,] (bb) -- (gg);
        \draw[thick, blue, line width=0.5mm,] (bb) -- (hh);
        \draw[thick, blue, line width=0.5mm,] (cc) -- (ff);
        \draw[thick, blue, line width=0.5mm,] (cc) -- (gg);
        \draw[thick, blue, line width=0.5mm,] (cc) -- (hh);
        \draw[thick, blue, line width=0.5mm,] (dd) -- (ff);
        \draw[thick, blue, line width=0.5mm,] (dd) -- (gg);
        \draw[thick, blue, line width=0.5mm,] (dd) -- (hh);
        \draw[thick, blue, line width=0.5mm,] (ee) -- (ff);
        \draw[thick, blue, line width=0.5mm,] (ee) -- (gg);
        \draw[thick, blue, line width=0.5mm,] (ee) -- (hh);
        \draw[thick, green, line width=0.5mm,] (aa) -- (bb);
        \draw[thick, green, line width=0.5mm,] (bb) -- (cc);
        \draw[thick, green, line width=0.5mm,] (dd) -- (ee);
        
        \draw[thick, red, line width=0.5mm,] (h) -- (i);
        \draw[thick, red, line width=0.5mm,] (h) -- (j);
        \draw[thick, red, line width=0.5mm,] (h) -- (k);
        \draw[thick, red, line width=0.5mm,] (h) -- (l);
        \draw[thick, red, line width=0.5mm,] (i) -- (j);
        \draw[thick, red, line width=0.5mm,] (i) -- (k);
        \draw[thick, red, line width=0.5mm,] (i) -- (l);
        \draw[thick, red, line width=0.5mm,] (j) -- (k);
        \draw[thick, red, line width=0.5mm,] (j) -- (l);
        \draw[thick, red, line width=0.5mm,] (k) -- (l);
        \draw[thick, green, line width=0.5mm,] (aa) to[out = 240, in = 120] (ee);

        \path (cc) -- node[auto=false]{\Huge \vdots} (dd);
    \end{tikzpicture}
    \caption{\label{fig:bipartite_plus_clique} We consider a graph that consists of a $5$-clique and a nearly bipartite graph with $n-8$ nodes on the left and three nodes on the right, where the $n-8$ nodes on the graph are also a cycle.}
\end{figure}

To put names to the buckets in the above example, let us choose $a$ to be the integer such that 
\[(1+\beta)^{a-1}<5\leq(1+\beta)^{a+1},\]
$b$ to be an integer such that  
\[(1+\beta)^{b-1}<n-8\leq(1+\beta)^{b+1},\]
and $c$ to be an integer such that 
\[(1+\beta)^{c-1}<4\leq(1+\beta)^{c+1}.\]
Thus, $|B_a|$ will consist of the $n-8$ nodes on the left, $|B_b|$ will consist of the three nodes in the main graph on the right, and $|B_c|$ will consist of the five nodes in the $5$-clique. Of these, it is clear that only $|B_a|$ will be considered ``big''. This will then give us that the green edges between nodes in $|B_a|$ will be big-big, the blue edges between nodes in $|B_a|$ and the nodes in $|B_b|$ will be big-small, an the red edges between the nodes in $|B_c|$ will be small-small. 

Thus, we will correctly count the green edges twice, we will only count the blue edges once, and we won't count the red edges at all. To get a sense of how much these small-small edges hurt our algorithm, we may calculate that the average degree of our graph is 
\[\overline{d} = \frac{(n-8)(5) + (3)(n-8) + (5)(4)}{n} = 8 - \frac{44}{n} \approx 8.\]
However, our algorithm will likely not sample any nodes from either $B_b$ or $B_c$, will set $\rho_a = 1$, $\rho_b = \rho_c = 0$, and will calculate the average number of nodes to be approximately five. Because five is within a factor of two of the true average degree, eight, we might hope that this means the small-small edges don't contribute much to the average degree. 

\subsubsection{Bounding How Much We Lose from the Small-Small Edges}

The good news is that the small buckets can't have too many nodes in them, and thus can't have too many small-small edges between them. To be more precise, we have that if $|B_i| > 2\sqrt{\epsilon\cdot n}/ (c\cdot t)$, then
\[E[|S_i|] = |S|\frac{|B_i|}{n}\geq |S|\cdot 2\sqrt{\frac{\epsilon}{n}}\frac{1}{c\cdot t}.\]
Because this is twice the threshold required for our algorithm to call $S_i$ ``big'', by Chernoff we can conclude that the algorithm will declare as such with high probability (it is this analysis that informed our choice of the threshold in the algorithm). Thus, we can assume that for any ``small'' $S_i$ that cause $\rho_i\gets 0$, that $|B_i|\leq 2\sqrt{\epsilon\cdot n}/ (c\cdot t)$. Thus, the total number of small-small edges, $T_{S}$, is upper bounded by
\[T_S\leq \left(\frac{2\sqrt{\epsilon\cdot n}}{c\cdot t}\cdot t\right)^2 = O\left(\frac{\epsilon\cdot n}{c^2}\right) = O(\epsilon\cdot n).\]
Thus, we may finally conclude that if we ignore these small-small edges, they may affect our estimation of average degree by at most a multiplicative factor\footnote{We must assume that the average degree of the graph is greater than or equal to one.} of $(1+\epsilon)$ or an additive factor of $\epsilon n$. 

\subsubsection{Bringing It All Together}

Finally, we may conclude that our algorithm gives us a $(2+\epsilon)$-multiplicative approximation, where the factor of two comes from us only counting the big-small edges once and the factor of $\epsilon$ comes from us not counting the small-small edges at all. 

Additionally, we observe that our algorithm runs in
\[\widetilde{O}\left(\frac{\sqrt{n}}{poly(\epsilon)}\right)\]
time, requiring that many degree queries (where the notation $\widetilde{O}$ indicates that we are dropping $\log$ terms).

\section{Estimate Average Degree: Second Attempt (now using neighbor queries as well)}

Now that we have seen an algorithm to estimate the average degree that only uses the degree queries, we want to see if we can do better if we use neighbor queries as well. The basic idea of this next approach is that in the first algorithm, most of our error came from only counting the big-small edges once, so we are going to now estimate the fraction of big-small edges and then add to our estimate to account for them. Specifically, our final algorithm is given below. 

\vspace{5mm}

\begin{algorithm}[H]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{Random access adjacency list $E$ and vector of degrees $d$}
  \Output{$\hat{\overline{d}}$}
  Take sample $S$ from $d$, where $|S| = \Theta(\sqrt{n} /\epsilon \cdot t)$\;
  $S_i \leftarrow S\cap B_i$ \;
  \For{all $i \in\{0,\cdots, t-1\}$} 	
    {\If{$|S_i| \geq \sqrt{\epsilon / n}|S|/(c\cdot t)$ ($|S_i|$ is not ``small'')}
      {$\rho_i \leftarrow |S_i|/ |S|$ \;
      \For{all $v\in S_i$}
        {Choose a random neighbor, $u$, of $v$ \;
        $X(v)\gets$ \{1 if $u$ is in a ``small'' bucket, 0 otherwise\}} 
        $\alpha_i\gets |\{v\in S_i|X(v) = 1\}| / |S_i|$}
    \Else
      {$\rho_i \leftarrow 0$}}
  Return $\sum_{i=0}^t\rho_i(1+\alpha_i)(1+\beta)^{i-1}$
    \caption{Average Degree Approximator (Final)}
    \label{alg:try_2}
\end{algorithm}

The main difference of this algorithm is that we estimate the factor $\alpha_i$, which is the fraction of edges in $B_i$ that are big-small, and then add the total $\sum_{i=0}^t\rho_i\alpha_i(1+\beta)^{i-1}$ to our estimate to account for the big-small edges that we only counted once. 

Before we continue, we will explain a new query that appears in algorithm \ref{alg:try_2}. In particular, we make use of a \textit{choose random neighbor} query. The way we implement this is that given a node $v$ and asked to choose a random neighbor, we 
\begin{itemize}
    \item Make a degree query for $v$, $d(v)$
    \item Choose a random number $i\in [1, \cdots, d(v)]$
    \item Make a neighbor query $(v, i)$
\end{itemize}

\subsection{Analysis}

The key piece of analysis that we must do is confirm that we are well estimating $\alpha_i$ using this sampling method and thus that we are well estimating $\overline{d}$. One worry is that we can not uniformly sample random edges from $B_i$.\footnote{Note that when sampling random edges from $B_i$, we mean random ``outgoing'' edges. Thus, an edge between two nodes in $B_i$ is considered two separate edges for the sake of this sampling.} Rather, we can sample random nodes from $B_i$ (by sampling nodes until we get one that is in $B_i$) and then sample a random edge from each of those nodes (using the choose random neighbor query defined above). If all nodes in $B_i$ had the same degree, then this would be a random sample of the edges in $B_i$, but they don't. However, all nodes in $B_i$ have similar degree, so we will argue that them being within a factor of $(1+\beta)$ is good enough. 

\subsubsection{The Easy Case}

In algorithm \ref{alg:try_2}, we attempt to estimate the number of big-small edges in $B_i$ by taking a random sample of nodes from $B_i$ (given by $S_i$) and then choosing a random neighbor, and thus a random edge, $e$, from each of those. In particular, let us define
\[ X_j^{(i)} =
  \begin{cases}
    1       & \quad \text{if } e \text{ is big-small}\\
    0  & \quad \text{if } e \text{ is big-big}
  \end{cases}
\]
for the $j^\text{th}$ edge we choose from $B_i$ and define 
\[\alpha_i=\sum_j X_j^{(i)} / |S_i|,\]
the average of the $X_j^{(i)}$s. 

To check whether this will give a good estimate, let us first optimistically assume that all nodes in $B_i$ have the same degree $d$. We then have that 
\[\Pr[\textrm{``big-small'' edge } e \textrm{ in } B_i \textrm{ is chosen}] = \frac{1}{|B_i|}\frac{1}{d},\]
where there is only a $1/|B_i|$ chance we choose a node adjacent to $e$ because only one end of the edge can be in $B_i$ given that $e$ is a big-small edge. We then have that  
\[\Pr[X_j^{(i)} = 1] = E[X_j^{(i)}] = \frac{T_i}{d\cdot |B_i|},\]
where $T_i$ is the number of big-small edges in $B_i$. Thus, $E[X_j^{(i)}]$ is exactly what we would want it to be, and thus $\alpha_i$ would be a good estimate for $\frac{T_i}{d\cdot |B_i|}$ given enough samples. 

\subsubsection{The General Case}

In general it is not true that all edges in $B_i$ have the same degree, but it is true that they are all within a factor of $(1+\beta)$. Thus, we have that 
\[\frac{1}{|B_i|}\frac{1}{(1+\beta)^{i}} \leq \Pr[\textrm{``big-small'' edge } e \textrm{ in } B_i \textrm{ is chosen}] \leq \frac{1}{|B_i|}\frac{1}{(1+\beta)^{i-1}},\]
and that
\[\frac{T_i}{|B_i|(1+\beta)^{i}} \leq E[X_j^{(i)}] \leq \frac{T_i}{|B_i|(1+\beta)^{i-1}},\]
which implies that 
\[E[X_j^{(i)}]|B_i|(1+\beta)^{i-1} \leq T_i \leq E[X_j^{(i)}]|B_i|(1+\beta)^{i}.\]
Thus, by estimating $E[X_j^{(i)}]$ within a factor of $(1+\epsilon)$ we can get an estimate of $T_i/n$ via $\alpha_i\rho_i(1+\beta)^{i-1}$ within a factor of $(1+\epsilon)(1 + \beta)$.

\subsubsection{Errors in Our Final Algorithm}

As a final count of errors in our last algorithm, we have
\begin{itemize}
    \item A multiplicative factor of $(1+\epsilon)$ from estimating the $\rho_i$ terms
    \item A multiplicative factor of $(1+\epsilon)$ from estimating the $\alpha_i$ terms
    \item An additive factor of $\epsilon n$ from not counting the small-small edges at all
\end{itemize}

\end{document}
