\documentclass[12pt]{article}
\usepackage{epsfig}
\usepackage{url}
\usepackage{verbatim}

\title{Snowball Sampling a Large Graph}

\author{William Cohen\\ Modified by Ni Lao}
\date{Out March 20, 2012\\
Due Tuesday, March 27, 2012 via Blackboard}
%{\bf WARNING} you will need hours to run experiments}


\begin{document}

\maketitle

\section{Background}

A ``snowball sample'' of a graph starts with some set of seed nodes of
interest, and then repeatedly adds some neighbors of the seed nodes
and their incident edges.  The idea is to come up with some version of
the ``local neighborhood'' of a node so that one can do analysis of,
say, the Facebook friend graph of a small subcommunity.  Doing this is
unfortunately tricky for a large graph.  This assignment uses some of
the ideas in a 2006 FOCS paper ``Local graph partitioning using
PageRank vectors'' by Andersen, Chung, and Lang to do a sort of
snowball sampling of a large graph---one which you have on disk.

Some notation first.

\begin{itemize}

\item $G$ is a graph, $V$ the vertices, $E$ the edges, $n=|V|$, and $m=|E|$.

\item I'll use indices $i$ for vertices when convenient, so $v_i$ has index $i$.

\item $d(v)$ is the degree of $v\in{}V$, and $D$ is a matrix with $D_{i,i}=d(v_i)$.

\item $\chi_v$ is a unit (row) vector with all weight on vertex $v$.

\item $A$ is an adjacency matrix for $G$.

\item $W=\frac{1}{2}(I + D^{-1}A)$ is a
``lazy random walk'' matrix, where there is probability 1/2 of staying at vertex $v$,
and probability 1/2 of moving to some other vertex $u$ connected to $v$.

\item We consider a ``lazy'' version of personalized PageRank, which is the unique solution
to
\begin{equation} \label{eq:pr-def}
 pr(\alpha, s) = \alpha s + (1-\alpha) pr(\alpha, s)W
\end{equation}
where $s$ is a ``seed'' distribution (row vector), $\alpha$ is a ``teleportation constant''.
%, and with some overloading we define $pr(\alpha, )$ as a function to map a seed distribution to its personalized PageRank vector.

\item It is easy to see that $pr(\alpha, s)$ is a linear function of $s$
\begin{equation} \label{eq:alpha}
 pr(\alpha, s) =\alpha \sum_{t=0}^{\infty} (1-\alpha)^t s W^t=s [ \alpha \sum_{t=0}^{\infty} (1-\alpha)^t  W^t ] = s \alpha [I- (1- \alpha) W]^{-1}
\end{equation}

\item It's easy to show that
\begin{equation} \label{eq:push}
 pr(\alpha, s) = \alpha s + (1-\alpha)pr(\alpha, sW)
\end{equation}
Note the subtle difference from Eq~\ref{eq:pr-def} - this statement
is true, but not obvious.
\end{itemize}

\section{Approximating PageRank with ``pushes''}

The personalized PageRank (row) vector $pr(\alpha, s)$ can be incrementally approximated as the following.

We maintain a pair of vectors $p$ (the current approximation) and $r$ (the ``residual'').  Initially
$r=s$ and $p$ is an all-zeros vector. This guarantee that the following equality is satisfied
\begin{equation} \label{eq:equal}
 p + pr(\alpha, r) = pr(\alpha, s)
\end{equation}
Now we repeatedly apply Eq~\ref{eq:push} to move probability mass from $r$ to $p$, but maintain
the equality in Eq~\ref{eq:equal}.

We define a ${\it push}(u,p,r)$ operation as
\[ p' = p + \alpha r_u \]
\[ r' = r - r_u + (1-\alpha) r_u W
\]
where $u$ is a node with non-zero weight in $r$ and $r_u$ is a vector which is zero everywhere except with weight $r(u)$ on node $u$.
A push operation move $\alpha$ of $u$'s weight from $r$ to
$p$, and then distributing the remaining $(1-\alpha)$ weight within
$r$ as if a single step of the random walk associated with $W$ were
performed.
This operation maintains the equality in Eq~\ref{eq:equal}.
Notice that to do a ``push'' on $u$, we need to know $d(u)$ and the
neighbors of $u$, but we don't need to know anything else about the
graph.

Let $apr(\alpha,\epsilon,v_0)$ be an ``approximate PageRank'' which is the result
of performing ``pushes'' repeatedly, in any order, until there is no
vertex $u$ such that $r(u)/d(u) \geq \epsilon$ (and then using $p$ as
the approximation).  Then you can show that
\begin{itemize}
\item Computing $apr(\alpha,v_0)$ takes time $O(\frac{1}{\epsilon \alpha})$
\item $\sum_{v:p(v)>0} d(v) \leq \frac{1}{\epsilon \alpha}$
\end{itemize}
It can also be shown that if there is a small, low-conductance set of
vertices that contains $v_0$, then for an appropriately chosen
$\alpha$ and $\epsilon$, the non-zero elements of $p$ will contain
that set.

\section{Approximating PageRank on a very large graph}

This suggests a scheme for approximating PageRank on a very large
graph --- one too large for even a complete vertex-weight vector to fit
in memory.  Compute $apr(\alpha,\epsilon,v_0)$ by repeatedly scanning
through the adjacency-list of the graph.  Whenever you scan past a
node $u$ with neighbors $v_1,\ldots,v_k$ in the stream, push $u$ if
$r(u)/d(u)>\epsilon$, and otherwise ignode $u$.

In more detail, let the graph be stored in a file where each line contains
\[ u,d(u),v_1,\ldots,v_k \]
where the $v_i$'s are the neighbors of $u$.  The algorithm is then

\begin{itemize}
\item Let $p=0$ and $r=\chi_{v_0}$.
\item Repeat the following until no pushes are made in a complete scan:
  \begin{itemize}
     \item For each line in the graph file
     \begin{itemize}
	\item If $r(u)/d(u) > \epsilon$ then let $p,r={\it push}(u,p,r)$
     \end{itemize}
  \end{itemize}
\end{itemize}

Finally, take the nodes that have non-zero weight in $p$, and include
all the edges that are incident on these nodes. 
Since both $p$ and $r$ are sparse, they can be kept in memory.

\section{Building a low-conductance subgraph}

Some more notation:
\begin{itemize}

\item The ``volume'' of a set $S$ is the number of edges incident on $S$,
i.e.
\[ {\it volume}(S) = \sum_{u\in{}S} d(u)
\]

\item The ``boundary'' of a set $S$ are the edges from a node $u\in{}S$ to a node $v\not\in{}S$.
\[ {\it boundary}(S) \equiv \{(u,v) \in E : u\in{}S, v\not\in{}S\}
\]

\item The ``conductance of $S$'' for a small set $S$ is the fraction of edges in $S$ that are on the boundary.
\[ \Phi(S) = \frac{|{\it boundary}(S)|}{{\it volume}(S)}
\]
More generally
\[ \Phi(S) = \frac{|{\it boundary}(S)|}{\min({\it volume}(S), |E|-{\it volume}(S))}
\]
\end{itemize}

Intuitively, if a node $u$ is in a low-conductance set $S$ that contains a seed node $v_0$, then it's plausible that $u$
would have a high score in $pr(\alpha,\chi_{v_0})$.  If that's true one way to find such a set would be the following.

\begin{itemize}
\item Let $S=\{v_0\}$ and let $S^* = S$
\item For all nodes $u\not=v_0$, in decreasing order of the personalized PageRank score $p(u)$:
  \begin{itemize}
  \item Add $u$ to $S$.
  \item If $\Phi(S)<\Phi(S*)$, then let $S^*=S$.
  \end{itemize}
\item Return $S^*$.
\end{itemize}

Andersen, Chung and Lang call this is operation ``sweep'', and show
that it will find a small, low-conductance set $S$ if one exists.
Note that ${\it boundary}(S)$, and hence $\Phi(S)$, can be computed
incrementally: ${\it boundary}(S + \{u\})$ is the edges in ${\it
boundary}(S)$, after removing the set of edges that enter $u$, and
adding the edges from $u$ to any node $v\not\in{}S + \{u\}$.

\section{Data}
An adjacent matrix of wikipedia concepts is available at \url{/afs/cs.cmu.edu/project/bigML/wikiGraph}.
The file \url{outlink.adj} contains an adjacent matrix of wikipedia graph. 
Each line is a tab-separated list of wikipedia pages, where the first page has links to each one of the following pages.
For debug purpose we provide another file \url{test.adj}, which is an subset of wikipedia graph.


\section{Assignment}
In this assignment we are going to implement the snowball algorithm and visualize the result of a few seeds.
%It is ok to to implement it without hadoop if you don't have the computing resource.

A visualization software (Gephi) is available for download \footnote{https://gephi.org/users/download}. You may use other visualization tool as you like.
Figure~\ref{fg:ML} gives an example result by using ``Machine\_learning'' as seed node. 
You are expected to produce similar graph for this seed and other seeds.

\begin{figure}[htb]
  \begin{center} %\hspace{-0.3in}
    \includegraphics[width=6.5in, height=7in]{ML_a0_3_e1e-5_snowball.pdf}
  \end{center} \vspace{-0.3in}
  \caption{Snowball result for ``Machine\_learning'' with $\alpha=0.3$ $\epsilon=10^{-5}$. }\label{fg:ML} \vspace{-0.2in}
\end{figure} %\vspace{-0.1in}

Hint 1: to load data into gephi I find GDF format is the easiest\footnote{https://gephi.org/users/supported-graph-formats/gdf-format}

Hint 2: Gephi's UI is a little bit confusing. I find `ForceAtlas 2' with scaling=500 and gravity=500 gives reasonably good result. You can export figures from the preview tab.

Overall your program may have the following 4 steps:
\begin{itemize}
\item run approximated PageRank with a seed page $s$, and parameters $\alpha$, $\epsilon$.
\item create a subgraph that involves nodes in $pr(\alpha,s)$
\item do the ``sweep'' operation and find a small, low-conductance subgraph
\item convert the low-conductance subgraph into the GDF format required by Gephi. For a node $v$ use $max(1, \log(p(v)/\epsilon))$ as its node size.
\end{itemize}

\section{Deliverables}

Submit a compressed archive (zip, tar, etc) of your code.  With it, include a makefile so that
\begin{itemize}
\item The command \emph{make pagerank} generates PageRank vector $p$ for \url{test.adj}. 
Print out two tab-separated columns--- nodes with non-zero weights in $p$, and their weights. Here we use seed=``A'', $\alpha=0.3$ and $\epsilon=10^{-5}$. Don't include the data file in your archive.

\item The command \emph{make snowball} generates the snowball subgraph for \url{test.adj}.  
Print out two tab-separated columns-- nodes in the corresponding low-conductance subgraph, and their $p$ values.
\end{itemize}

In addition, please include a pdf document with the output of your ``make demo'' command. 
Also respond to the following questions
\begin{enumerate}
\item visualization for seed ``Machine\_learning'' with $\alpha=0.3$ and $\epsilon=10^{-5}$
\item visualization for two other seeds of your choice, with $\alpha$ and $\epsilon$ of your choice.
\end{enumerate}

BONUS question: how sensitive is the result graph to parameters $\alpha$ and $\epsilon$?


\section{Marking breakdown}
\begin{itemize}
\item Code correctness and makefile functionality {\bf [70 points]}.
\item Question 1, 2 {\bf [10+20 points]}
\item BONUS question  {\bf [10 points]}
\end{itemize}

\end{document}

