
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
  \frametitle{Sidebar: 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}
}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{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.
}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{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}
}
\end{frame}

\begin{frame}
\frametitle{NSD: Parallelization [KKG JPDC'14 (to appear)]}

\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}

\end{frame}



