
\stitle {Functional PageRank (PR)}
\small{ 
{\bf Computing PageRank (PR)}
 \begin{itemize}
\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}
}

\small{
{\bf 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}
}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \stitle{Functional Rankings Through Multidamping [Kollias, Gallopoulos, AG, TKDE'13]}
%\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 $.
}

  \stitle{Multidamping and Computational Cost}

{\bf Advantages of multidamping}

\begin{itemize}
\item Interpretability and Design!
\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}




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

{\small
\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, compared to standard iterations of equivalent computational
cost/number of operations? \emph{[Left]}\\

\textbf{Approximate personalized ranking:}
 Run less than $n$ surfers to completion (each called a microstep, x-axis), 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 simple approach? \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]}






\subsection{Results and Discussion}

\stitle{Experimental settings}
We set the \alert{preference vector} as:
\begin{equation*}
e_{\mathcal{S}}(i) = \begin{cases} \frac{1}{|\mathcal{S}|} & \text{if $v_i \in \mathcal{S}$,}
\\
0 &\text{O.W.}
\end{cases}
\end{equation*}


for $\mathcal{S}$ being the subset of vertices in the yeast interactome corresponding to members of the TORC1 protein complex. The diameter of the network is computed to be $6$ and \alert{$\alpha$ parameter} is set to $\frac{d}{d+1}=\frac{6}{7} \sim 0.85$ accordingly to give all nodes a fair chance of being visited.






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \stitle{Network Alignment}
\small{
  \begin{columns}[h]
    \begin{column}{3.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}.
      \end{itemize}
    \end{column}
  \end{columns}
\begin{itemize}
\item
Let $\tilde{A}$ and $\tilde{B}$ be the normalized adjacency matrices of the graphs (normalized by columns),
$H_{ij}$ be the independently known similarity scores (preferences matrix) of nodes $i \in V_B$ and
$j \in V_A$, and $\mu$ be the fractional contribution of topological similarity.
\item To compute $X$, IsoRank iterates:
$$
X \leftarrow \mu \tilde{B} X {\tilde{A}}^{T} + (1-\mu) H
$$
\end{itemize}
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{Network Similarity Decomposition (NSD) 
[Kollias, Mohammadi, AG, TKDE'12]}
\small{
{\bf Network Similarity Decomposition (NSD)}
\begin{itemize}
\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 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; these are much cheaper than triple matrix products.
\end{itemize} 

We can then apply Primal-Dual or Greedy Matching (1/2 approximation) to extract the actual node pairs.
}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\stitle{NSD: Performance 
[Kollias, Madan, Mohammadi, AG, BMC RN'12]}
{\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 compute similarity matrices $X$ for various 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 We then extract node matches using PDM and GM.
\item
\emph{Three orders of magnitude speedup} from \textsf{NSD}-based approaches compared to \textsf{IsoRank}. 
\end{itemize}
}

\stitle{NSD: Parallelization [KKG JPDC'13, Submitted, KMSAG ParCo'13 Submitted]}

\textbf{Parallelization:}
NSD has been ported to parallel and distributed platforms.
\begin{itemize}
\item We have aligned up to million-node graph instances using over 3K cores.
\item We process graph pairs of over a billion nodes and twenty billion edges each (!), on MapReduce-based
distributed platforms.
\end{itemize}




