\documentclass{beamer}

%\usepackage{algorithmic,algorithm}
% \usepackage{color}
%\usepackage{latexsym,amsmath,amssymb,amsfonts}
\usepackage{graphics}
%\usepackage{url}
%\usepackage{listings}

\mode<presentation>
{
  \usetheme[]{Madrid}
  \setbeamercovered{transparent}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
%\lstset{columns=flexible, basicstyle=\tiny\itshape,
%  frame=tb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{}
\small{ 
\begin{block}{PageRank (PR)}
 \begin{itemize}
  \item \textbf{Q:} What makes a web page important? \textbf{A:} many important pages contain links to it; however a page containing many links has reduced impact on the importance of the pages it contains links to. This is the basic idea in \emph{PageRank} for ranking graph nodes.
\item PageRank as a \emph{random surfer process}: Start surfing from a random node and keep following links with probability $\mu$ restarting  with probability $1 - \mu$; the node for restarting will be selected based on a personalization vector $v$. The ranking value $x_i$ of a node $i$ is the probability of visiting this node during surfing.
\item PR can also be cast in power series representation as
$x =  (1-\mu) \sum_{j=0}^k \mu^{j} S^j v$; $S$ encodes column-stochastic adjacencies.
  \end{itemize}
\end{block}
}

\small{
\begin{block}{Functional rankings} 
 \begin{itemize}
 \item A general method to assign ranking values to graph nodes as $x =  \sum_{j=0}^k \zeta_j S^j v$. PR is a functional ranking, 
$\zeta_j = (1-\mu) \mu^j$.
\item Terms attenuated by outdegrees in $S$ \emph{and} damping coefficients $\zeta_j$.
  \end{itemize}
\end{block}
}
\end{frame}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{}
\textbf{Q:} Is there a way to encode functional rankings as surfing processes?\\
\textbf{A: Multidamping}
\small{
  \begin{columns}[t]    
    \begin{column}{4.cm}
      \begin{figure}[tbh]
        \centering
        \includegraphics[scale=0.5]{figures/montecarlo.pdf}
      \end{figure}
    \end{column}
   
    \begin{column}{7.2cm}
      \begin{block}{Computing $\mu_j$ in multidamping}
        Simulate a functional ranking by random surfers following emanating links with probability $\mu_j$ at step $j$ given by : \\
        
$\mu_{j} = 1  -\frac{1}{1+\frac{\rho_{k-j+1}}{1-\mu_{j-1}}}, j = 1, ..., k,$ \\
$\text{where } \mu_0 = 0$ and $\rho_{k-j+1} =
        \frac{\zeta_{k-j+1}}{\zeta_{k-j}}$
      \end{block}
    \end{column}
  \end{columns}
}

\footnotesize{
\textbf{Examples}\\
\emph{LinearRank (LR)}  
$ x^{\rm LR} =\sum_{j=0}^{k}  \frac{2(k+1-j)}{(k+1)(k+2)}  S^j v$ :
$\mu_j = \frac{j}{j+2}, j = 1, ..., k $.\\
\emph{TotalRank (TR)} 
$x^{\rm TR} = \sum_{j=0}^\infty \frac{1}{(j+1)(j+2)} S^j v$ :
$\mu_j = \frac{k-j+1}{k-j+2}, j =1, ..., k $.
}

\small{
\begin{block}{Advantages of multidamping}
\begin{itemize}
\item Reduced computational cost in \emph{approximating} functional rankings using the Monte Carlo approach. A random surfer terminates with probability $1 - \mu_j$ at step $j$.
\item Inherently parallel and synchronization free computation.
\end{itemize}
\end{block}
}

\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{}
\footnotesize{ 
 \begin{columns}[t]    
    \begin{column}{5.8cm}
      \begin{figure}[h]
        \includegraphics[width=1.0\textwidth]{figures/tau-TR-1000-crop.pdf}
      \end{figure}
    \end{column}
    \begin{column}{5.8cm}
      \begin{figure}[h]
        \includegraphics[width=1.0\textwidth]{figures/shared-LR-20-crop.pdf}
        \end{figure}
      \end{column}
  \end{columns}

\textbf{Approximate ranking:}
  Run $n$ surfers to completion for graph size $n$. 
  How well does the computed ranking capture the ``reference'' ordering for
$\texttt{top-}k$ nodes (Kendall $\tau$, y-axis) in comparison to the one calculated by standard iteration (for a number of steps, x-axis) of equivalent computational cost/number of operations? \emph{[Left]}\\

\textbf{Approximate personalized ranking:}
 Run $<n$ surfers to completion (each called a microstep, x-axis), but only from a selected node (personalized).
 How well can we capture the ``reference'' $\texttt{top-}k$ nodes, i.e. how many of them are shared (y-axis), compared to the iterative approach of equivalent computational load? \emph{[Right]}
}\\
\scriptsize{[\textsf{uk-2005}: $39,459,925$ nodes, $936,364,282$ edges. 
\textsf{in-2004}: $1,382,908$ nodes, $16,917,053$ edges]}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\small{
  \begin{columns}[h]
    \begin{column}{5.8cm}
      \includegraphics[width=\textwidth]{figures/match-graphs.pdf}
    \end{column}
    \begin{column}{5.8cm}
      \begin{itemize}
      \item
        \textbf{Node similarity:} Two nodes are similar if they are linked by other similar node pairs. By pairing similar nodes, the two graphs become \emph{aligned}.
      \item In \emph{IsoRank}, a state-of-the-art graph alignment method, first a matrix $X$ of similarity scores between the two sets of nodes is computed and then maximum-weight bipartite matching approaches extract the most similar pairs.
      \end{itemize}
    \end{column}
  \end{columns}
\begin{itemize}
\item
Let $\tilde{A}$, $\tilde{B}$ the adjacencies  $A^{T}$, $B^{T}$  of the two graphs normalized by columns (network data), $H_{ij}$ independently known similarity scores (preferences matrix) between nodes $i \in V_B$ and  $j \in V_A$ and $\mu$ the percentage of contribution of network data in the algorithm.
\item To compute $X$, IsoRank iterates:
$$
X \leftarrow \mu \tilde{B} X {\tilde{A}}^{T} + (1-\mu) H
$$
\end{itemize}
}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\small{
\begin{block}{Network Similarity Decomposition (NSD)}
\begin{itemize}
\item
We reformulate IsoRank iteration and gain speedup and parallelism.
\item
In $n$ steps of we reach
$X^{(n)} = (1-\mu) \sum_{k=0}^{n-1} \mu^{k} \tilde{B}^{k} H (\tilde{A}^{T})^{k} + \mu^{n} \tilde{B}^{n} H (\tilde{A}^{T})^{n}$ 
\item
Assume for a moment that $H=u v^T$ ($1$ component). Two phases for $X$:
\begin{enumerate}
\item
  $u^{(k)} = \tilde{B}^{k} u$ and $v^{(k)} = \tilde{A}^{k} v$ \emph{(preprocess/compute iterates)}
\item
  $X^{(n)} = (1-\mu) \sum_{k=0}^{n-1} \mu^{k} u^{(k)}{v^{(k)}}^{T} + \mu^{n}  u^{(n)}{v^{(n)}}^{T}$ \emph{(construct $X$)} 
\end{enumerate} 
This idea extends to $s$ components, $H \sim \sum_{i=1}^{s} w_i z_i^{T}$.
\item
NSD computes matrix-vector iterates and builds $X$ as a sum of outer products of vectors; these are much cheaper than triple matrix products.
\end{itemize} 
\end{block}
We can then apply Primal Dual Matching (\textsf{PDM}) or Greedy Matching (1/2 approximation, \textsf{GM}) to extract the actual node pairs.
 \begin{columns}[t]    
    \begin{column}{5.8cm}
      \begin{figure}[h]
        \includegraphics[width=0.8\textwidth]{figures/nsdblocks.pdf}
      \end{figure}
    \end{column}
    \begin{column}{5.8cm}
      \begin{figure}[h]
        \includegraphics[width=0.8\textwidth]{figures/isoblocks.pdf}
        \end{figure}
      \end{column}
  \end{columns}

}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{}
{\tiny
\begin{columns}[c]
\begin{column}{4cm}
\begin{center}
\begin{tabular}[h]{lll}
\hline
\textbf{Species}	& \textbf{Nodes} & \textbf{Edges} \\ \hline
celeg (worm) 	& 2805	 & 4572 \\
dmela (fly) 	& 7518	 & 25830 \\
ecoli (bacterium)	& 1821	 & 6849 \\
hpylo (bacterium)	& 706	 & 1414 \\
hsapi (human)	& 9633	 & 36386 \\
mmusc (mouse)	& 290	 & 254 \\
scere (yeast) & 5499	 & 31898 \\
\end{tabular}
\end{center}
\end{column}

\begin{column}{7.2cm}
\begin{center}
\begin{tabular}[h]{|l|p{0.5cm}|p{0.6cm}|p{0.6cm}|p{0.6cm}|p{1cm}|}
\hline
\textbf{Species pair}	& \textbf{NSD (secs)} &   \textbf{PDM (secs)} & \textbf{GM (secs)} &  \textbf{IsoRank (secs)} \\ \hline
celeg-dmela &	 \textbf{3.15}           &    152.12      &   7.29      &	783.48  \\ \hline	
celeg-hsapi &    \textbf{3.28}           &    163.05      &   9.54      &	1209.28	\\ \hline
celeg-scere &    \textbf{1.97}           &    127.70      &   4.16      &	949.58	\\ \hline
dmela-ecoli &    \textbf{1.86}           &    86.80       &   4.78      &	807.93	\\ \hline
dmela-hsapi &    \textbf{8.61}           &    590.16      &   28.10     &	7840.00	\\ \hline
dmela-scere &    \textbf{4.79}           &    182.91      &   12.97     &	4905.00	\\ \hline
ecoli-hsapi &    \textbf{2.41}           &    79.23       &   4.76      &	2029.56	\\ \hline
ecoli-scere &    \textbf{1.49}           &    69.88       &   2.60      &	1264.24	\\ \hline
hsapi-scere &    \textbf{6.09}           &    181.17      &   15.56     &	6714.00	\\ \hline
\end{tabular}
\end{center}
\end{column}
\end{columns}
}
{\footnotesize
\begin{itemize}
\item
We computed the similarity matrices $X$ for various possible pairs of species using Protein-Protein Interaction (PPI) networks. $\mu = 0.80$, uniform initial conditions (outer product of suitably normalized $\mathrm{1}$'s for each pair), $20$ iterations, one component. 
\item Then we extracted node matches using PDM and GM.
\item
\emph{3 orders of magnitude speedup} of \textsf{NSD}-based approaches compared to \textsf{IsoRank} ones. 
\end{itemize}

\textbf{Parallelization:}
NSD has also been ported to parallel/distributed platforms:
\begin{itemize}
\item We have aligned up to million-node graph instances using up to $3,072$ cores in a supercomputer installation.
\item We have managed to process graph pairs of over a billion nodes and twenty billion edges each, over MapReduce-based platforms.
\end{itemize}
}
\end{frame}

\end{document}

