\documentclass{beamer}

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

\mode<presentation>
{
  %% \usetheme[compress]{Ilmenau}
  
  %% yellow colortheme
  %% \usecolortheme{crane}
  
  %% ok
  %% \usetheme[compress]{Ilmenau}
  %% \usetheme[compress]{Berlin}

  %% ok, manual
  %% \useoutertheme[footline=authorinstitutetitle]{miniframes}
  
  %% ok, no bottom bar
  % \usetheme{JuanLesPins}
  % \usetheme{Antibes}
  
  %% too broad navigation bar
  %% \usetheme{Malmoe}
  %% \usetheme{Luebeck}
  \usetheme{Copenhagen}
  \setbeamercovered{transparent}
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\title[Approximate Graph Operations on Parallel Platforms]
{\textbf{Approximate Graph Operations on Parallel Platforms}}
\author[]{
%\textbf{G. Kollias, M. Sathe, O. Schenk, \underline{A. Grama}
%    \footnote{{\tiny Purdue University, USA (G. Kollias, A. Grama), University of Basel, Switzerland (M. Sathe, O. Schenk)}}}\\[0.4cm]
% \emph{Presented by} \textbf{Hasan Metin Aktulga\footnote{{\tiny Lawrence Berkeley National Labs, USA}}}
}
\date[]{}


\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \titlepage

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Overview}
  \begin{itemize}
  \item Computing similarity of nodes in two graphs
    \begin{itemize}
    \item Essentially ranking pairs of nodes
    \end{itemize}
  \item Network similarity decomposition \textsf{NSD}
    \begin{itemize}
    \item Algorithm
    \item Sequential implementation, experiments and applications
    \end{itemize}
  \item Parallel \textsf{NSD}-based computation of node similarity scores
    \begin{itemize}
    \item Algorithm, parallel implementation, experiments
    \item The alignment graph
    \end{itemize}
  \item Parallel \textsf{NSD}
    \begin{itemize}
    \item Algorithm, parallel implementation, auction matching
    \item Large scale experiments
    \item Strong and weak scaling results
    \end{itemize}  
  \item Conclusions and future work
  \end{itemize}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Graph similarity in figures}
  \begin{columns}[c]
    \begin{column}{5.8cm}
      \begin{block}{Protein-Protein Interaction (PPI)  networks for 2 species}
        \begin{center}
          \includegraphics[width=0.9\textwidth]{figures/bayati-species.jpg}
        \end{center}
      \end{block}
      
      \begin{center}
        \includegraphics[width=0.9\textwidth]{figures/bayati-graphs.jpg}
      \end{center}
    \end{column}
    
    \begin{column}{5.8cm}
      \begin{block}{Wikipedia categories and Library of Congress subject headings}
        \begin{center}
          \includegraphics[width=0.9\textwidth]{figures/bayati-categories.jpg}
        \end{center}
      \end{block}
      {\Large How similar are any two nodes of these networks? \footnote{figures from 
          M. Bayati, M.Gerritsen, D. Gleich, A. Saberi, and Y. Wang, Algorithms for Large, Sparse Network Alignment, ICDM 2009}}
    \end{column}
  \end{columns}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{An example of similarity of a graph with itself (self-similarity)}

  \begin{columns}[c]
    \begin{column}{5.0cm}
      {\footnotesize
        \begin{itemize}
        \item
          Applying the similarity pipeline presented here
        \item
          $(i,j)$ square denotes a matching of node $i$ to node $j$.
        \end{itemize}
      }
      \begin{block}{Example graph}
        \begin{figure}[th]
          \center
          \includegraphics[width=0.90\textwidth]{figures/graph10u.pdf}
        \end{figure}
      \end{block}
    \end{column}
    \begin{column}{6.0cm}
      \begin{block}{Allow matching a node to itself}
        \begin{figure}[!ht]
          \center
          \includegraphics[width=0.40\textwidth]{figures/match10u.pdf}
        \end{figure}
      \end{block}
      \begin{block}{Do not allow matching a node to itself}
        \begin{figure}[!ht]
          \center
          \includegraphics[width=0.40\textwidth]{figures/match10u-constrained.pdf}
        \end{figure}
      \end{block}
    \end{column}
  \end{columns}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Rank-inspired definition of similarity}
  \begin{block}{Node Ranking}
    A node is important if it is linked by other important nodes
  \end{block}
  \begin{block}{Graph Similarity}
    Two nodes are similar if they are linked by other similar node pairs
  \end{block}
  {\footnotesize
    \beamertemplatebookbibitems
    \begin{thebibliography}{10}
    \bibitem{BlondelGajardo.etal.04}
      V.D. Blondel, A.~Gajardo, M.~Heymans, P.~Senellart, and P.~{Van Dooren}.
      \newblock {A Measure of Similarity between Graph Vertices: Applications to
        Synonym Extraction and Web Searching}.   
      \newblock {\em SIAM Rev.}, 46(4):647--666, 2004.
    \bibitem{singh_global_2008}
      R.~Singh, J.~Xu, and B.~Berger.
      \newblock Global alignment of multiple protein interaction networks with
      application to functional orthology detection
      \newblock {\em Proceedings of the National Academy of Sciences}, 105(35):12763,
      2008.\\
    \end{thebibliography}
    {\emph{Singh's et al approach, \textsf{IsoRank}, is our focus, has been typically applied to undirected graphs}}
  }
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Notation}
  {\scriptsize
    \begin{itemize}
    \item $A$, $B$ the the adjacency matrices of input graphs $G_A$, $G_B$.
    \item $\tilde{A}$ is $A^{T}$ normalized by columns, i.e. $(\tilde{A})_{ij} = a_{ji} / \sum_{i=1}^{n_A}{a_{ji}}$; 
      similarly for $\tilde{B}$.
    \item $h=vec(H)$ a normalized vector where $H_{ij}$ are independently known similarity scores between 
      node sets,  $i \in V_B$ and  $j \in V_A$. 
    \item $vec(\cdot)$ operation for building a vector from a matrix (stacking its columns); $unvec(\cdot)$ is the 
      inverse operation.  
    \item $\alpha$: percentage of network data contribution in the algorithm.
    \item $\tilde{C} = \tilde{A \otimes B} = \tilde{A} \otimes \tilde{B}$ 
    \item Computed matrix $X$ contains similarity scores: $X_{ij}$ entry denotes how ``similar'' nodes $i \in V_B$ and  $j \in V_A$ are.
    \end{itemize}
  }
  \begin{block}{Reminder}
    Kronecker product $A \otimes B$ of two matrices:
    {\tiny
      $$
      A \otimes B
      = \begin{bmatrix} a_{1,1}B & a_{1,2}B & \cdots \\
        a_{2,1}B & a_{2,2}B \\
        \vdots  &         & \ddots
      \end{bmatrix}
      = \begin{bmatrix}
        a_{1,1}b_{1,1} & a_{1,1}b_{1,2} & \cdots & a_{1,2}b_{1,1} & a_{1,2}b_{1,2} & \cdots \\
        a_{1,1}b_{2,1} & a_{1,1}b_{2,2} &        & a_{1,2}b_{2,1} & a_{1,2}b_{2,2} \\
        \vdots       &              & \ddots \\
        a_{2,1}b_{1,1} & a_{2,1}b_{1,2} \\
        a_{2,1}b_{2,1} & a_{2,1}b_{2,2} \\
        \vdots
      \end{bmatrix}.
      $$
    }  
  \end{block}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{\textsf{IsoRank} algorithm}
  \begin{alertblock}{\textsf{IsoRank} iteration}
    \begin{itemize}  
    \item $x \leftarrow  \alpha \tilde{C} x + (1-\alpha) h$ 
    \end{itemize}
    until convergence.
  \end{alertblock}
  Alternatively $X \leftarrow \alpha \tilde{B} X {\tilde{A}}^{T} + (1-\alpha) H$ as the iteration kernel
  {\tiny
    \begin{itemize}
    \item Because $A X B = unvec((B^{T} \otimes A) x)$ (property of Kronecker products)
    \item \textsf{MAT3} (triple matrix product implementation of \textsf{IsoRank} idea)
    \end{itemize}
  }
  \begin{itemize}
  \item
    In IsoRank kernel  $x \leftarrow  \alpha \tilde{C} x + (1-\alpha) h$, set $x^{(0)} = h$
  \item
    Expanding, after $n$ steps
    $$ x^{(n)} = (1-\alpha) \sum_{k=0}^{n-1} \alpha^{k} \tilde{C}^{k} h + \alpha^{n} \tilde{C}^n h $$
  \item
    Alternatively
    $X^{(n)} = (1-\alpha) \sum_{k=0}^{n-1} \alpha^{k} \tilde{B}^{k} H (\tilde{A}^{T})^{k} + \alpha^{n} \tilde{B}^{n} H (\tilde{A}^{T})^{n}$
  \end{itemize}   
  \bf{\color{red}Similarity scores are sums of contributions from all k-hop neighbors (similarity score aggregation)} 
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{An example of similarity score aggregation in IsoRank}
  {\small
    \begin{itemize}
    \item Let $G_A$ and $G_B$ with nodes $\{a, b,c,d,e,f,g\}$ and $\{1,2,3,4,5,6\}$
    \item Suppose nodes $(b,1)$, $(f,4)$ and $(g,6)$ pairs are somewhat similar ($H$ information)
    \item Sum the contributions of all 1-hop, 2-hop, 3-hop,... neighbors in the two networks (along
      paths like $c-b-1-2$, $c-d-f-4-3-2$, $c-a-e-g-6-5-4-2$) with known or previously computed similarity)
    \end{itemize}
  }
  \begin{figure}[th]
    \center
    \includegraphics[width=0.40\textwidth]{figures/sim123.pdf}
  \end{figure}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
% \begin{frame}
%   \frametitle{A look into $\tilde{B} X {\tilde{A}}^{T}$ term ``mechanics''}
%   \begin{columns}[]
%     \begin{column}{5.8cm}
%       \begin{center}
%         \includegraphics[width=\textwidth]{figures/isorank-example.png} 
%       \end{center}
%     \end{column}
%     \begin{column}{5.8cm}
%       Top to bottom, left to right:
%       {\small   
%         \begin{itemize}
%         \item
%           Graphs $G_B$, $G_A$
%         \item
%           $\tilde{B}$, similarity matrix $X$ and ${\tilde{A}}^{T}$
%         \end{itemize}
%       }
%       \textbf{How to update similarity score between nodes $2$  of $G_B$ and $1$ in $G_A$, i.e. $X_{21}$ entry (green)?} 
%     \end{column}
%   \end{columns}
%   {\small
%     \begin{itemize}
%     \item
%       Node $2$ of $G_B$ can pull score from its neighbors $1$ and $3$
%     \item
%       It can do so in \emph{four} different ways because these neighbors are assumed connected with ``virtual links'' to every other of the \emph{four} nodes in the other network $G_A$, i.e. $y^{T} \leftarrow \tilde{B}_{2,all} X$
%     \item
%       However \emph{two} of these ways are relevant since node $1$ of $G_A$ can pull score from its \emph{two} neighbors, namely $2$ and $3$, i.e. 
%       $X_{21} \leftarrow y^{T} {{\tilde{A}}^{T}}_{all,1}$
%     \end{itemize}
%   }
% \end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Decomposing graphs: The \textsf{NSD} idea}
  In IsoRank, using $H$ as the initial condition ($X^{(0)}=H$), after $n$ steps we get 
  $X^{(n)} = (1-\alpha) \sum_{k=0}^{n-1} \alpha^{k} \tilde{B}^{k} H (\tilde{A}^{T})^{k} + \alpha^{n} \tilde{B}^{n} H (\tilde{A}^{T})^{n}$
  \begin{itemize}
  \item     
    Let $H=u v^T$ ($1$ component, i.e.  $1$ outer vector product). Two phases for computing $X$ then:
  \end{itemize}
  \begin{enumerate}
  \item
    $u^{(k)} = \tilde{B}^{k} u$ and $v^{(k)} = \tilde{A}^{k} v$ \emph{(preprocess/compute iterates)}
  \item
    $X^{(n)} = (1-\alpha) \sum_{k=0}^{n-1} \alpha^{k} u^{(k)}{v^{(k)}}^{T} + \alpha^{n}  u^{(n)}{v^{(n)}}^{T}$ \emph{(construct $X$)} 
  \end{enumerate}
  This extends to the case $H$ is approximated by $s$ components (sum of $s$ outer vector products): $H \sim \sum_{i=1}^{s} w_i z_i^{T}$.
  \begin{alertblock}{NSD key points}
    \begin{itemize}
    \item
      Instead of triple matrix products we compute sums of outer products of vectors 
    \item
      These vectors in turn are sparse matrix-vector iterates than can be computed independently 
    \end{itemize}
  \end{alertblock}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{\textsf{NSD}-based similarity matrix construction}
  {\small
    \begin{columns}[c]
      \begin{column}{5.8cm}
        \begin{algorithmic}[1]
          \STATE \COMMENT{Input: $A$, $B$, $\{w_i, z_i | i=1,\ldots,s\}$, $\alpha$ and $n$, Output: $X = X^{(n)}$}
          \STATE compute $\tilde{A}$, $\tilde{B}$ \COMMENT{phase 1}
          \FOR{$i=0$ to $s$}
          \STATE $w_i^{(0)} \leftarrow w_i$, $z_i^{(0)} \leftarrow z_i$  
          \FOR{$k=0$ to $n$}
          \STATE $w_i^{(k)} \leftarrow \tilde{B} w_i^{(k-1)}$
          \STATE $z_i^{(k)} \leftarrow \tilde{A} z_i^{(k-1)}$ 
          \ENDFOR
          \STATE {\color{blue} zero $X_i^{(n)}$ \COMMENT{phase 2 start}}
          \FOR{{\color{blue}$k=0$ to $n-1$}}
          \STATE {\color{blue} $X_i^{(n)} \leftarrow X_i^{(n)} + \alpha^{k} w_i^{(k)} {z_i^{(k)}}^{T}$}
          \ENDFOR
          \STATE {\color{blue} $X_i^{(n)} \leftarrow (1-\alpha) X_i^{(n)} + \alpha^{n} w_i^{(n)} {z_i^{(n)}}^{T}$}
          \ENDFOR
          \STATE {\color{blue} $X^{(n)} \leftarrow \sum_{i=1}^{s} X_i^{(n)}$}
        \end{algorithmic}
      \end{column}

      \begin{column}{5.8cm}
        \textbf{Remarks}
        \begin{itemize}
        \item Decomposition happens along the set of paths of succesively larger length $k$, however with increasing ``damping'' (because of the $(1-\alpha) \alpha^{k}$ factor with $\alpha \in [0,1]$) 
        \item The computation does not involve either explicitly building the product graph related $\tilde{C}$ or computing triple matrix products of the form $\tilde{B} X \tilde{A}^{T}$ at each step. Only computing outer vector products at the end. 
        \item (Sparse) matrix-vector products for the two graphs can be computed \emph{quite independently}
        \end{itemize}
      \end{column}
    \end{columns}
  }
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Block diagram of the decomposition approach}
  \begin{center}
    \includegraphics[width=0.7\textwidth]{figures/integration-blocks.png}
  \end{center}
  {\scriptsize
    \begin{enumerate}
    \item
      Input a network pair and its elemental similarities $H$ as component vectors; Preprocess/compute vector iterates 
    \item
      Construct similarity matrix $X$ by summing outer products of vectors
    \item
      Produce a set of pairs (matches) of nodes from one network that are ``most similar'' to nodes from the other: rows and columns of $X$     as nodes of a weighted bipartite graph, $X_{ij}$ its weights. 
      \begin{itemize}
      \item Matching algorithms used in experiments for this 3rd phase:
        Primal Dual Matching (\textsf{PDM}), Greedy Matching (1/2 approximation, \textsf{GM}), Hungarian, auction.
      \end{itemize}
    \end{enumerate}
  }
  {\tiny
    In the sequel \textsf{IsoRank} refers to the implementation of the \textsf{IsoRank} idea followed by the application of Hungarian and PDM algorithms to resulting $X$ (as available in Singh's binary code)}. 
  % \textcolor{red}{\emph{...build the alignment graph at the end}}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Protein-Protein Interaction (PPI) networks (sequential)}
  {\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{MAT3 (secs)} &  \textbf{PDM (secs)} & \textbf{GM (secs)} &  \textbf{IsoRank (secs)} \\ \hline
            celeg-dmela &	 \textbf{3.15}     &  64.20      &    152.12      &   7.29      &	783.48  \\ \hline	
            celeg-hsapi &    \textbf{3.28}     &  69.74      &    163.05      &   9.54      &	1209.28	\\ \hline
            celeg-scere &    \textbf{1.97}     &  44.61      &    127.70      &   4.16      &	949.58	\\ \hline
            dmela-ecoli &    \textbf{1.86}     &  37.79      &    86.80       &   4.78      &	807.93	\\ \hline
            dmela-hsapi &    \textbf{8.61}     &  211.19     &    590.16      &   28.10     &	7840.00	\\ \hline
            dmela-scere &    \textbf{4.79}     &  131.22     &    182.91      &   12.97     &	4905.00	\\ \hline
            ecoli-hsapi &    \textbf{2.41}     &  47.48      &    79.23       &   4.76      &	2029.56	\\ \hline
            ecoli-scere &    \textbf{1.49}     &  35.86      &    69.88       &   2.60      &	1264.24	\\ \hline
            hsapi-scere &    \textbf{6.09}     &  152.02     &    181.17      &   15.56     &	6714.00	\\ \hline
          \end{tabular}
        \end{center}
      \end{column}
    \end{columns}
  }
  {\scriptsize
    \begin{itemize}
    \item
      We computed the similarity matrices $X$ for various possible pairs of species using only PPI data (network data)
    \item
      $\alpha = 0.80$, uniform initial conditions (outer product of suitably normalized $\mathrm{1}$'s for each pair), $20$ iterations, 1 component.
    \end{itemize}
  }
  {\scriptsize
    \begin{alertblock}{Finding}
      1-3 orders of magnitude speedup of \textsf{NSD}-based approaches compared to comparable \textsf{MAT3}-based (with \textsf{PDM}, \textsf{GM}) and \textsf{IsoRank} ones (no parallelization yet). 
    \end{alertblock}
  }
  {\tiny
    \beamertemplatebookbibitems
    \begin{thebibliography}{10}
    \bibitem{serialNSD}
      G.~Kollias, S.~Mohammadi, and A.~Grama.
      \newblock {Network Similarity Decomposition (NSD): A Fast and Scalable Approach
        to Network Alignment}.
      \newblock {\em IEEE Transactions on Knowledge and Data Engineering}, 2011.\\
    \end{thebibliography}
  }
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Parallel \textsf{NSD}-based similarity matrix construction}
  
  {\scriptsize
    \begin{columns}[c]
      \begin{column}{5.8cm}
        {\tiny
          \textbf{Parallel \textsf{NSD}: Root process}
          \begin{algorithmic}
            \STATE compute $\tilde{A}$, $\tilde{B}$
            \FOR{$i=1$ to $s$}
            \STATE $w_i^{(0)} \leftarrow w_i$, $z_i^{(0)} \leftarrow z_i$  
            \FOR{$k=0$ to $n$}
            \STATE $w_i^{(k)} \leftarrow \tilde{B} w_i^{(k-1)}$
            \STATE $z_i^{(k)} \leftarrow \tilde{A} z_i^{(k-1)}$ 
            \ENDFOR
            \ENDFOR
            \FOR {$i=1,\ldots s, k=0,\ldots,n$}
            \STATE{Partition $w_i^{(k)}$ in $p$ fragments, $w_{i,1}^{(k)},\ldots,w_{i,p}^{(k)}$}
            \STATE{Partition $z_i^{(k)}$ in $q$ fragments, $z_{i,1}^{(k)},\ldots,z_{i,q}^{(k)}$}
            \ENDFOR
            \STATE{Send to every process $(r,u)$ in the process grid $p \times q$  its
              corresponding $w_{i,r}^{(k)}$, $z_{i,u}^{(k)}$ fragments, $\forall i=1,\ldots s, k=0,\ldots,n$ ($r=1,\ldots,p$, $u=1,\ldots,q$)}
          \end{algorithmic}
        }
      \end{column}
      
      \begin{column}{5.8cm}
        {\tiny  
          \textbf{Parallel \textsf{NSD}: Worker process $(r,u)$} 
          \begin{algorithmic}
            \STATE{Receive corresponding $w_{i,r}^{(k)}$, $z_{i,u}^{(k)}$ fragments, $\forall i=1,\ldots s, k=0,\ldots,n$ from the root process} 
            \FOR{$i=1$ to $s$}
            \STATE zero $X_{i,ru}^{(n)}$
            \FOR{$k=0$ to $n-1$}
            \STATE  $X_{i,ru}^{(n)} \leftarrow X_{i, ru}^{(n)} + \alpha^{k} w_{i,r}^{(k)} {z_{i,u}^{(k)}}^{T}$
            \ENDFOR
            \STATE  $X_{i,ru}^{(n)} \leftarrow (1-\alpha) X_{i,ru}^{(n)} + \alpha^{n} w_{i,r}^{(n)} {z_{i,u}^{(n)}}^{T}$
            \ENDFOR
            \STATE  $X_{ru}^{(n)} \leftarrow \sum_{i=1}^{s} X_{i,ru}^{(n)}$
          \end{algorithmic}
        }
        
        {\tiny  
          \begin{center}
            \begin{tabular}[h]{cllll} \hline
              &  \multicolumn{2}{c}{\textbf{dmela-hsapi}} & \multicolumn{2}{c}{\textbf{hsapi-scere}} \\ \hline
              \textbf{num cores} & \textbf{$t_{Iters}$} & \textbf{$t_{SimMat}$}  & \textbf{$t_{Iters}$} & \textbf{$t_{SimMat}$} \\ \hline
              4 	&	0.211 &	 28.103	    &       0.194 &  21.062 \\
              9	&	0.210 &  15.914     &       0.213 &  11.865 \\
              16	&	0.219 &  9.851      &       0.215 &  7.478  \\	
              25	&	0.202 &  7.072      &       0.195 &  5.283  \\	
              36	&	0.311 &  6.080      &       0.209 &  4.493  \\	
              49	&	0.193 &  5.809      &       0.240 &  4.233  \\	
              64	&	0.207 &  4.915      &       0.253 &  3.576  \\ 	
            \end{tabular}
          \end{center}
        }
      \end{column}
    \end{columns}
    \begin{itemize}  
    \item  
      \textsf{Java} implementation, \textsf{MPJ} for message passing, \textsf{csparsej} for sparse \textsf{matvec}'s 
    \item
      2 heterogeneous clusters ($40$ + $24$ cores) 
    \item  
      1 component, 20 iters, $\alpha=0.8$ (times in secs)
    \end{itemize}
  }
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{The alignment graph}
  {\scriptsize
    \begin{columns}[c]
      \begin{column}{6.2cm}
        \begin{alertblock}{Build the alignment graph}
          \begin{itemize}
          \item Nodes are pairs of matching nodes $(b_i/a_j)$ from the original networks $G_B$, $G_A$
          \item $(b_i/a_j)$ is connected to  $(b_p/a_q)$ iff $b_i$, $b_p$ and $a_j$, $a_q$ are neighbors in  $G_B$, $G_A$
          \end{itemize}
        \end{alertblock}
      \end{column}
      \begin{column}{5.8cm}
        \textbf{Topological quality of computed matchings?}
        \begin{itemize}
        \item Number of edges in the alignment graph (conserved edges)
        \item Size of the connected subgraphs in the alignment graph
        \end{itemize}
      \end{column}
    \end{columns}
    {\tiny
      \begin{itemize}
      \item Each conserved edge implies matching the corresponding edges connecting the elements of the matching pairs at its endpoints in the input networks.
      \item  These subgraphs are essentially matchings of substructures in the input networks (CCS, Common Connected Subgraphs).
      \end{itemize}      
    }
    \begin{center}
      \includegraphics[width=0.33\textwidth]{figures/G_H.pdf}\qquad
      \includegraphics[width=0.33\textwidth]{figures/dmela-scere-components-mat3-0000-20-080.pdf}
    \end{center}
    CCS for the alignment graph based on $H$ (sequence similarity) and $X$ (\textsf{MAT3} computed) for a PPI network pair (dmela-scere)
  }
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{CCS and $H$ approximation}
  \begin{center}
    \includegraphics[width=0.30\textwidth]{figures/dmela-scere-components-mm-0005-20-080.pdf}\qquad
    \includegraphics[width=0.30\textwidth]{figures/dmela-scere-components-mm-0010-20-080.pdf}\\\rule{0.8\textwidth}{1pt}
    \includegraphics[width=0.30\textwidth]{figures/dmela-scere-components-svd-0500-20-080.pdf}\qquad  
    \includegraphics[width=0.30\textwidth]{figures/dmela-scere-components-svd-1000-20-080.pdf}
    {\scriptsize
      \begin{itemize}
      \item
        \textsf{NSD} on the dominant $s=5$ and $s=10$ components of $H$ as
        computed by \textsf{NMF} (upper row) and  $s=500$ and $s=1000$ components as computed by \textsf{SVD} (lower row). 20 iters, $\alpha=0.8$ (dmela-scere)
      \item More components offer more opportunities for CCS development and thus more conserved edges; smaller CCS are favored over very large ones
      \end{itemize}
    }
  \end{center}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Parallel \textsf{NSD}: Matching $G_A$, $G_B$ network nodes in parallel}
  \textbf{Parallel NSD similarity matrix construction and parallel auction combined}
  {\small
    \begin{algorithmic}[1]
      \STATE \COMMENT{\emph{$\square$ = root process, no labels = all processes r}}
      \STATE $\square$ load adjacency matrices A, B and component vectors $w_i$, $z_i$;
      \STATE $\square$ compute  $\tilde{A}$, $\tilde{B}$;
      \STATE \texttt{broadcast} $\tilde{A}$, $w_i$, $z_i$;
      \STATE distribute $\tilde{B}$ by row blocks \COMMENT{each process r gets its  $\tilde{B}_{r}$ part};
      \STATE \COMMENT{for all components $i$ and steps $k$ ($z_i^{(0)}=z_i$, $w_i^{(0)}=w_i$)}
      \STATE compute vector iterates  $z_i^{(k)} \leftarrow \tilde{A} z_i^{(k-1)}$
      \STATE compute vector iterates  $w_{i,r}^{(k)} \leftarrow \tilde{B}_{r} w_i^{(k-1)}$,\texttt{gather} $w_i^{(k)}$ 
      (\texttt{// matvec});
      \STATE compute \emph{row-wise} the local similarity matrix $X_{r}$ (\emph{embarrassingly //})  
      \STATE \COMMENT{\texttt{NSD}-based, \emph{sparsify} if needed (sort row entries, keep largest ones)}; 
      \STATE compute  weighted matchings by \texttt{// auction}   
      \STATE \COMMENT{matching permutation lands on root};
      \STATE $\square$ compute number of conserved edges;
    \end{algorithmic}
  }
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}[fragile]
  \frametitle{Auction algorithm and experimental setup}
  \begin{columns}[c]
    \begin{column}{6.2cm}
      {\scriptsize
        \textbf{Auction algorithm (implemented in parallel)}
        \begin{algorithmic}[1]
          \STATE $M = \emptyset$; \COMMENT{current matching}
          \STATE $I = \{i: 1 \leq i \leq m\}$; \COMMENT{set of unassigned persons}
          \STATE $p_j \leftarrow 0$ for $j=1, \ldots, n$; \COMMENT{prices for the objects}
          \WHILE {$I \neq \emptyset$}
          \STATE \COMMENT{find object $j$ with best and second best profit};
          \STATE $j_i \leftarrow \arg \max_j\{ x_{ij} - p_j\}$;
          \STATE $v_i \leftarrow \max_j\{ x_{ij_{i}} - {p_j}_{i}\}$;
          \STATE $w_i \leftarrow \max_{j\neq j_i}\{ x_{ij_{i}} - {p_j}_{i}\}$;
          \STATE \COMMENT{update price with the bid $v_i - w_i + \epsilon$}
          \STATE ${p_j}_i \leftarrow {p_j}_i + v_i - w_i + \epsilon$;
          \STATE \COMMENT{assign person to the desired object};
          \STATE $M \leftarrow M \cup \{i, j_i\},\, I \leftarrow I \setminus \{i\}$;
          \STATE \COMMENT{free previous owner $k$ if available}
          \STATE $M \leftarrow M \setminus \{k, j_i\},\, I \leftarrow I \cup \{k\}$;
          \ENDWHILE
        \end{algorithmic}
      }
    \end{column}

    \begin{column}{5.4cm}
      {\scriptsize
        \begin{itemize}
        \item Based on the metaphor of buyers and objects
        \item Favors 1D distribution of row block in the parallel setting
        \item Actually a special \emph{adaptive} parallel auction variant is implemented providing faster convergence 
        \end{itemize}
      }

      \begin{block}{Setup}
        {\scriptsize
          \begin{itemize}
          \item constant nonzero entries/$X$ row: \emph{strong scaling} for \textsf{auction} 
          \item constant nonzero entries/core: \emph{weak scaling} for \textsf{auction}   
          \item \textsf{strong scaling} for similarity score computations 
          \item Up to $3,072$ cores (\textsf{CRAY XE6}, consists of 2-hexacore processors)
          \item Hybrid programming model (\textsf{C/MPI/OpenMP})
          \end{itemize}
        }
      \end{block}
    \end{column}
  \end{columns}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}[fragile]
  \frametitle{Summary of base timing results (1/2)}

  \begin{table}[t!]
    {\scriptsize {
        \begin{center}
          \setlength{\tabcolsep}{1.0pt}
          \begin{tabular}[width=0.4\linewidth]{|c|c|r|r|c|c|}
            \hline
            \textbf{Pair}&\textbf{Graph}& \textbf{\#Vertices}&  \textbf{\#Edges} & \textbf{Total time (s)} & \textbf{\#Cores}\\ \hline \hline
            \multirow{2}{*} {protein-protein} &\textsf{yeast} & $5,499$ & $31,898$ & \multirow{2}{*} {$75$} & \multirow{2}{*} {$1$}\\ 
            \nonumber &\textsf{fruitfly} & $7,518$	& $25,830$ & \nonumber & \nonumber\\ \hline \hline
            \multirow{2}{*}{net/pfinan} &\textsf{net4-1} & $88,343$ & $1,265,035$ & \multirow{2}{*} {$796$} & \multirow{2}{*} {$48$}\\ 
            \nonumber &\textsf{pfinan512} & $74,752$ & $335,872$& \nonumber& \nonumber\\ \hline
            \multirow{2}{*} {snapA} &\textsf{soc-slashdot090221} & $82,144$ & $549,202$ & \multirow{2}{*} {$2,688$}& \multirow{2}{*} {$48$}\\
            \nonumber &\textsf{soc-slashdot090216} & $81,871$	& $545,671$ & \nonumber& \nonumber\\ \hline     
            \multirow{2}{*} {snapB} &\textsf{soc-slashdot0902} & $82,168$ & $948,464$ & \multirow{2}{*} {$1,497$}& \multirow{2}{*} {$48$}\\ 
            \nonumber &\textsf{soc-slashdot0811} & $77,360$	& $905,468$ & \nonumber& \nonumber\\ \hline \hline
            \multirow{2}{*}{usroads} &\textsf{usroads} & $129,164$ & $165,435$ & \multirow{2}{*} {$281$}& \multirow{2}{*} {$384$}\\
            \nonumber &\textsf{usroads-48} & $126,146$ & $161,950$ & \nonumber& \nonumber\\ \hline
            \multirow{2}{*} {dnvs} &\textsf{halfb} & $224,617$ & $6,306,219$ & \multirow{2}{*} {$880$}& \multirow{2}{*} {$384$}\\ 
            \nonumber &\textsf{fullb} & $199,187$	& $5,953,632$& \nonumber& \nonumber\\ \hline 
            \multirow{2}{*} {b3} &\textsf{m133-b3} & $200,200$ & $800,800$ & \multirow{2}{*} {$1,593$}& \multirow{2}{*} {$384$}\\ 
            \nonumber &\textsf{shar\_te2-b3} & $200,200$ & $800,800$& \nonumber& \nonumber\\ \hline \hline
            \multirow{2}{*} {coAuthors} &\textsf{coAuthorsDBLP} & $299,067$ & $977,676$& \multirow{2}{*} {$659$} & \multirow{2}{*} {$768$}\\ 
            \nonumber &\textsf{coAuthorsCiteseer} & $227,320$& $814,134$& \nonumber& \nonumber\\ \hline 
            \multirow{2}{*} {notreDame} &\textsf{NotreDame\_www} & $325,729$ & $929,849$& \multirow{2}{*} {$764$}& \multirow{2}{*} {$768$}\\ 
            \nonumber &\textsf{web-NotreDame} & $325,729$	& $1,497,134$& \nonumber& \nonumber\\ \hline 
            \multirow{2}{*} {stanford} &\textsf{Stanford} & $281,903$ & $2,312,497$& \multirow{2}{*} {$615$}& \multirow{2}{*} {$768$}\\ 
            \nonumber &\textsf{web-Stanford} & $281,903$	& $2,312,497$& \nonumber& \nonumber\\ \hline
          \end{tabular}
        \end{center}}}
  \end{table}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Summary of base timing results (2/2)}
  \begin{table}[t!]
    {\scriptsize {
        \begin{center}
          \setlength{\tabcolsep}{1.0pt}
          \begin{tabular}[width=0.4\linewidth]{|c|c|r|r|c|c|}
            \hline
            \textbf{Pair}&\textbf{Graph}& \textbf{\#Vertices}&  \textbf{\#Edges} & \textbf{Total time (s)} & \textbf{\#Cores}\\ \hline \hline
            \multirow{2}{*}{amazon} &\textsf{amazon0505} & $410,236$ & $3,356,824$& \multirow{2}{*} {$558$}& \multirow{2}{*} {$3,072$}\\ 
            \nonumber &\textsf{amazon0601} & $403,394$	& $3,387,388$& \nonumber& \nonumber\\ \hline
            \multirow{2}{*}{delaunay} &\textsf{delaunay\_n19} & $524,288$ & $1,572,823$& \multirow{2}{*} {$938$}& \multirow{2}{*} {$3,072$}\\ 
            \nonumber &\textsf{delaunay\_n18} & $262,144$	& $786,396$ & \nonumber& \nonumber\\ \hline
            \multirow{2}{*}{authorsSelf} &\textsf{coAuthorsCiteseer} & $227,320$ & $814,134$& \multirow{2}{*} {$226$}& \multirow{2}{*} {$3,072$}\\ 
            \nonumber &\textsf{coAuthorsCiteseer} & $227,320$	& $814,134$ & \nonumber& \nonumber\\ \hline     
            \multirow{2}{*}{coPapers} &\textsf{coPapersDBLP} & $540,486$ & $15,245,729$& \multirow{2}{*} {$2,167$}& \multirow{2}{*} {$3,072$}\\ 
            \nonumber &\textsf{coPapersCiteseer} & $434,102$	& $16,036,720$ & \nonumber& \nonumber\\ \hline
            \multirow{2}{*}{papersSelf} &\textsf{coPapersCiteseer} & $434,102$	& $16,036,720$& \multirow{2}{*} {$1,630$}& \multirow{2}{*} {$3,072$} \\ 
            \nonumber &\textsf{coPapersCiteseer} & $434,102$	& $16,036,720$& \nonumber& \nonumber\\ \hline \hline
            \multirow{2}{*}{dbpedia1} &\textsf{dbpedia-3.0\_300k} & $300,000$ & $1,320,138$& \multirow{2}{*} {$17,382$}& \multirow{2}{*} {$128$}\\
            \nonumber &\textsf{dbpedia-3.5.1\_500k} & $500,000$	& $10,546,881$& \nonumber& \nonumber \\ \hline
            \multirow{2}{*}{eu/in} &\textsf{eu-2005\_300k} & $300,000$ & $10,835,193$& \multirow{2}{*} {$18,122$}& \multirow{2}{*} {$128$}\\
            \nonumber &\textsf{in-2004\_500k} & $500,000$	& $8,506,508$& \nonumber& \nonumber \\ \hline \hline
            \multirow{2}{*}{dbpedia2} &\textsf{dbpedia-3.0\_500k} & $500,000$ & $2,680,807$& \multirow{2}{*} {$16,838$}& \multirow{2}{*} {$256$}\\ 
            \nonumber &\textsf{dbpedia-3.5.1\_1500k} & $1,500,000$	& $26,794,451$ & \nonumber& \nonumber\\ \hline
            \multirow{2}{*}{euSelf} &\textsf{eu-2005} & $862,664$ & $19,235,140$& \multirow{2}{*} {$10,939$}& \multirow{2}{*} {$256$}\\
            \nonumber &\textsf{eu-2005} & $862,664$ & $19,235,140$& \nonumber& \nonumber\\ \hline

          \end{tabular}
        \end{center}}}
  \end{table}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Summary of speed improvements (1/2)}
  {\small
    \begin{itemize}
    \item Absolute values for the time ratio nominator part correspond to base timings   
    \item x-axis is the number of cores
    \item Speed improvements for both the two basic phases of the parallel similarity pipeline (similarity scores matrix construction followed by matching by auction) and the total procedure are depicted
    \end{itemize}
  }
  \begin{figure}[t!]
    \begin{minipage}{\textwidth}
      \centering
      \setlength{\tabcolsep}{0.5pt}
      \begin{tabular}{cc}
        \includegraphics[width=0.3075\textwidth]{figures/10k.pdf} & 
        \includegraphics[width=0.65\textwidth]{figures/100k.pdf} 
      \end{tabular}
    \end{minipage}
  \end{figure}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Summary of speed improvements (2/2)}
  \begin{figure}[t!]
    \begin{minipage}{\textwidth}
      \centering
      \setlength{\tabcolsep}{0.5pt}
      \begin{tabular}{cc}
        \includegraphics[width=0.479\textwidth]{figures/200k.pdf} & 
        \includegraphics[width=0.479\textwidth]{figures/300k.pdf}
      \end{tabular}

      {\footnotesize
        \begin{center}
          \setlength{\tabcolsep}{1.0pt}
          \begin{tabular}{|l|r|r|r|r|r|}
            \hline
            \textbf{Pair} & \textbf{amazon}& \textbf{delaunay} & \textbf{coPapers} & \textbf{papersSelf} & \textbf{authorsSelf}\\ 
            \hline \hline
            t\_similarityMatrix & $481.73$ & $935.04$ & $2,156.20$ & $1,620.30$ & $222.56$\\
            \hline
            t\_parallelAuction & $76.18$ & $2.61$ & $10.37$ & $9.47$ & $3.01$\\  
            \hline
            t\_total & $557.91$ & $937.65$ & $2,166.57$ & $1,629.77$ & $225.57$\\  
            \hline
          \end{tabular}
        \end{center}
      }
    \end{minipage}
  \end{figure}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Quality measurement indices}
  \begin{itemize}
  \item
    Conserved Edges (CE)
  \item
    Rate: Ratio of conserved edges over the minimum of the edges in the
    two networks 
  \end{itemize}

  \begin{table}[t!]
    {\footnotesize 
      \begin{columns}[c]
        \begin{column}{5.8cm}
          \begin{center}
            \begin{tabular}[width=0.4\linewidth]{|c|r|r|}
              \hline
              \textbf{Pair}& \textbf{\#CE} & \textbf{Rate}\\ \hline \hline
              protein-protein & $745$ & $0.03$\\ \hline \hline
              net/pfinan & $74,778$ & $0.22$\\ \hline
              snapA & $14,296$ & $0.02$\\ \hline 
              snapB & $77,617$ & $0.09$\\ \hline \hline
              usroads & $2,666$ & $0.02$\\ \hline
              dnvs & $1,750,799$ & $0.29$\\ \hline
              b3 & $29,217$ & $0.15$ \\ \hline \hline
              coAuthors & $85,437$ & $0.11$\\ \hline 
              notreDame & $113,992$ & $0.12$\\ \hline
              stanford & $107,968$ & $0.05$\\ \hline
            \end{tabular}
          \end{center}
        \end{column}
        
        \begin{column}{5.8cm}
          \begin{center}
            \begin{tabular}[width=0.4\linewidth]{|c|r|r|}
              \hline
              \textbf{Pair}& \textbf{\#CE} & \textbf{Rate}\\ \hline \hline
              amazon & $46,278$ & $0.01$\\ \hline 
              delaunay & $112,152$ & $0.14$\\ \hline 
              authorsSelf & $814,134$ & $1.00$\\ \hline
              coPapers & $3,520,545$ & $0.23$\\ \hline 
              papersSelf & $16,036,720$ & $1.00$\\ \hline \hline 
              dbpedia1 & $1,100$ & $0.004$\\ \hline
              eu/in & $80,884$ & $0.04$\\ \hline \hline
              dbpedia2 & $2,082$ & $0.007$\\ \hline 
              euSelf & $219,759$ & $0.26$\\ \hline
            \end{tabular}
          \end{center}
        \end{column}
      \end{columns}
    }
  \end{table}   
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Strong scaling experiments with (the small) PPI networks}
  \begin{block}{\textsf{dmela} and \textsf{scere}}
    {\tiny
      \begin{center}
        \begin{tabular}{|l|r|r|r|r|r|r|r|}
          \hline
          \textbf{Cores} & \textbf{1}& \textbf{2} & \textbf{4} & \textbf{8} & \textbf{16} & \textbf{32} & \textbf{64} \\ 
          \hline \hline
          t\_similarityMatrix & 11.73 & 6.10 & 2.94 & 1.46 & 0.73 & 0.36 & 0.18 \\
          \hline
          t\_parallelAuction & 62.68 & 34.02 & 17.61& 9.49 & 5.07 & 3.47 & 2.80\\  
          \hline
          t\_totalSimilarityProcess & 74.52 & 40.23 & 20.65 & 11.05 & 5.90 & 3.94 & 3.10\\  
          \hline \hline
          Conserved edges & 625& 691 & 688 & 737 & 745 & 668 & 658 \\
          \hline
        \end{tabular}
      \end{center}
    }
  \end{block}

  \begin{columns}
    \begin{column}{5.8cm}
      \begin{center}
        \includegraphics[width=\textwidth]{figures/ppi_graph.pdf}
      \end{center}
    \end{column}
    \begin{column}{5.8cm}
      \begin{itemize}
      \item roughly $3$ secs for getting matching pairs ($a=0.8$, $20$ iterations, $1$ component, $64$ cores); cf. over an hour ($4905$ secs) for the inherently sequential \textsf{IsoRank} 
      \item  nice scaling properties for the critical parallel \textsf{auction} phase
      \end{itemize}
    \end{column}
  \end{columns}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Strong scaling experiments}
  \begin{block}{\textsf{eu-2005\_300k} and \textsf{in-2004\_500k}}
    {\tiny
      \begin{center}
        \begin{tabular}{|l|r|r|r|r|}
          \hline
          \textbf{Cores} & \textbf{128}& \textbf{256} & \textbf{512} & \textbf{1024} \\ 
          \hline \hline
          t\_generateIterates & 5.07 & 5.04 & 5.33 & 6.13 \\
          \hline
          t\_generateRow & 16,450.88 & 8,152.49 & 4,030.19 & 1,224.77 \\
          t\_sort & 1,577.80 & 788.39 & 394.80 & 197.03 \\
          t\_similarityMatrix & 18,045.54 & 8,949.46 & 4,429.16 & 1,423.65 \\
          \hline
          t\_parallelAuction & 55.16 & 28.82 & 16.32 & 11.90\\  
          \hline
          t\_totalSimilarityProcess & 18,121.54 & 8,998.95 & 4,466.56 & 1,457.53\\  
          \hline \hline
          Conserved edges & 80,884 & 80,884 & 80,884 & 80,884  \\
          \hline
        \end{tabular}
      \end{center}
    }
  \end{block}

  \begin{block}{\textsf{dbpedia-3.0\_300k} and \textsf{dbpedia-3.5.1\_500k}}
    {\tiny
      \begin{center}
        \begin{tabular}{|l|r|r|r|r|}
          \hline
          \textbf{Cores} & \textbf{128}& \textbf{256} & \textbf{512} & \textbf{1024} \\ 
          \hline \hline
          t\_generateIterates & 11.00 & 11.19 & 11.53 & 12.36 \\
          \hline
          t\_generateRow &15,703.82  & 7,475.45 & 3,254.46 & 1,228.59 \\
          t\_sort & 1,606.47 & 802.44 & 400.97 & 200.69 \\
          t\_similarityMatrix & 17,327.27 & 8,286.56 & 3,659.58 & 1,431.17 \\
          \hline
          t\_parallelAuction & 31.97 & 19.78 & 14.37 & 14.93 \\  
          \hline
          t\_totalSimilarityProcess & 17,382.15 & 8,329.41 & 3,697.45 & 1,470.62\\  
          \hline \hline
          Conserved edges & 1,010/1,100 & 1,018/1,097 & 1,014/1,088 & 1,014/1,088 \\
          \hline
        \end{tabular}
      \end{center}
    }
  \end{block}
  \begin{itemize}
  \item Timings for various phases, number of conserved edges
  \item $a=0.8$, $20$ iterations, $10$ random components for all large scale experiments
  \end{itemize}
\end{frame}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Weak scaling experiments (for auction)}
  \begin{columns}[c]
    \begin{column}{5.8cm}
      \begin{block}{\textsf{dbpedia-3.0\_500k}, \textsf{dbpedia-3.5.1\_1500k}}
        \begin{center}
          \includegraphics[width=\textwidth]{figures/largewiki_graph.pdf}
        \end{center}
      \end{block}
    \end{column}
    \begin{column}{5.8cm}
      \begin{block}{Self-similarity for \textsf{eu-2005\_300k}}
        \begin{center}
          \includegraphics[width=\textwidth]{figures/selfweb_graph.pdf}
        \end{center}
      \end{block}
    \end{column}
  \end{columns}

  \begin{itemize}
  \item The expected almost ideal scaling properties of parallel matrix construction phase compensates for deviations from optimality of the auction phase in the total time speedup.
  \end{itemize}

\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Conclusions}
  \begin{itemize}
  \item Graph similarity computations can be \textbf{decomposed} with respect to
    \begin{itemize}
    \item the identical link patterns occuring in the graphs
    \item the rank-one terms building up the initial condition
    \item Interpretation insight
    \end{itemize}
  \item Graph similarity computations can be \textbf{uncoupled}
    \begin{itemize}
    \item Each graph is processed independently, sparse matrix-vector kernel
    \item Merging through outer products only at the end
    \item Speedup
    \end{itemize}
  \end{itemize}
  \begin{alertblock}{Highlights of NSD}
    \begin{itemize}
    \item
      Massive performance gains from Parallel NSD-based similarity matrix construction, no scale up limit (embarrassingly //).
    \item
      Parallel NSD is an integrated, performant approach for processing very large networks
    \end{itemize}
  \end{alertblock}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{frame}
  \frametitle{Future work}

  \begin{itemize}
  \item Evaluate the effect of more components on the quality of the 
    similarity scores for various application domains
  \item Develop and implement heuristics for parallel matching, suitable for different application domains  
  \end{itemize}
  
  \begin{alertblock}{}
    Weighted matching algorithm for matrices represented as sum of outers products of vectors?
  \end{alertblock}
\end{frame}

\end{document}

