\documentclass[landscape,dvips]{foils}

%\documentclass[a4paper,landscape,headrule]{foil


%\usepackage[latin1]{inputenc}
%\usepackage{graphicx}

%\MyLogo{Slide}

\usepackage{amsmath,amsthm,amssymb,amscd}
\usepackage{alltt}
\usepackage{epsf}
\usepackage{amsfonts}
\def\w{{\cal W}}
\usepackage{latexsym}
\usepackage{times}
\usepackage{bookman}
\usepackage{graphics}
\usepackage{color}
\usepackage{epsfig}
\usepackage{psfrag}
\usepackage[ps2pdf]{hyperref}
\usepackage{multicol}

\newcommand{\img}[2]{{\\epsfxsize=#1truecm\epsfbox{Images/PS/#2}}}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}


\usepackage{lipsum}
\newcounter{examplecounter}
\newenvironment{example}{\begin{quote}%
    \refstepcounter{examplecounter}%
  \textbf{Example \arabic{examplecounter}}%
  \quad
}{%
\end{quote}%
}


\def\basswidt{4.0in}
\def\gutter{0.2in}

\newenvironment{comment}{\setbox0=\vbox\bgroup}{\egroup}
\newenvironment{singlespace}{\def\baselinestretch{1.0}\large\normalsize}{\par}

%\setlength{\textheight}{8.5in}
%\setlength{\textwidth}{6in}
\setlength{\textheight}{8in}
\setlength{\textwidth}{9in}
\voffset=-0.9in

\newcommand{\ie}{{\sl i.e.}}

\newcommand{\support}{{\sigma}}
\newcommand{\freq}{{\xi}}
\newcommand{\minsup}{{\sigma^{*}}}
\newcommand{\minfreq}{{\xi^{*}}}
%\newcommand{\I}{{\cal{I}}}
%\newcommand{\T}{{\cal{T}}}
\newcommand{\A}{{\cal{A}}}
\newcommand{\G}{{\cal{G}}}
\newcommand{\F}{{\cal{F}}}
\newcommand{\E}{{\cal{E}}}
\newcommand{\V}{{\cal{V}}}
\newcommand{\La}{{\cal{L}}}
\newcommand{\lgraph}{{G=(V,E,\La)}}
\newcommand{\ugraph}{{\bar{G}=(\bar{V},\bar{E},\La)}}
\def\M{{\cal M}}
\def\N{{\cal N}}
\def\D{{\cal D}}
\def\vv{{\mathbf v}}
\def\uu{{\mathbf u}}

\newcommand{\blue}[1]{{\color{blue} #1}}
\newcommand{\green}[1]{{\color{green} #1}}
\newcommand{\red}[1]{{\color{red} #1}}
\newcommand{\stitle}[1]{\foilhead{\red{#1}}\vspace{-0.5in}}
\newcommand{\bigitem}[2]{\item{#1\begin{small}\begin{itemize}#2\end{itemize}\end{small}}}
\newcommand{\mcite}[3]{\small{\red{[#1, {\sl #2}, #3]}}}
\newcommand{\eg}{{\sl e.g.}}

\begin{document}

\title{
\red{Part 2: Scalable Analytics -- Large-Scale Dynamic Networks}
}

\author{
\blue{Ananth Grama} \\
\blue{Center for Science of Information and Computer Science} \\
\blue{Purdue University} \\ \\
Thanks to the US National Science Foundation.
}

\date{}

\maketitle

\thispagestyle{empty}


\stitle{Overview and Motivation}

\begin{itemize}
\item
Dynamic networks are one of the most important forms of ``Big Data''.
\item
Virtually all network data is dynamic.
\begin{itemize}
\item
Networks of social and economic transactions.
\item
Interactions in biological, physical, and engineered systems.
\item
Traffic, connectivity, and dependencies in computer/ communications systems.
\end{itemize}
\item
Analysing dynamic networks poses significant and diverse challenges.
\end{itemize}


\stitle{Characteristics of Dynamic Networks}

Instances of dynamic networks of interest are typically:
\begin{itemize}
\item
Large -- scaling to billions of nodes and interactions.
\item
Noisy -- with high rates of false positives and negatives.
\item
Multiscale -- incorporating interactions at vastly different levels of abstractions.
\item
Heterogeneous -- demonstrating high variability in characteristics over space and time.
Significant skews in degree distribution.
\item
Distributed -- data is typically collected and stored at distributed locations.
\item
Elastic -- data is typically elastic.
\end{itemize}


\stitle{Analysis of Dynamic Networks}

Analysis techniques for dynamic networks must:
\begin{itemize}
\item
Rely on suitable formulations -- results are typically probabilistic. Formulations
must quantify (and optimize) significance (statistical).
\begin{itemize}
\item
Deterministic formulations on noisy data are not meaningful.
\item
Distribution agnostic formulations (say, based on simple counts and frequencies) are
unlikely to work.
\end{itemize}
\item
Provide rigorously validated solutions -- garbage-in, garbage-out at scale.
\item
Must have efficient elastic distributed implementations (MapReduce type frameworks
have considerable issues with semantics, scope, and overhead).
\end{itemize}
These issues form the focus of our current research efforts in the area.




\stitle{Dynamic Network Analysis -- Problems (1)}

\begin{itemize}
\item
Characterization and Modeling of Dynamic State.
Study data-driven dynamic networks and characterize the evolution at micro-
as well as macro-scale. This includes node-,
link-, aggregate-, and network models.
\item
Mutual Information, Conservation. Models and methods for determining conserved
information in a set of networks states and its relation to overall network dynamics.
\item
Discriminant Analysis. Track evolution as a sequence of
discriminants across network snapshots.
\item
Spatio-Temporal Motifs. Define recurring patterns in both space and time.
\end{itemize}

\stitle{Dynamic Network Analysis -- Problems (2)}

\begin{itemize}
\item
Prediction of Network State. Predicting network state at micro- and macro-scales.
This is an essential aspect of resource allocation and provisioning.
\item
Noise, Robustness, and Approximations. Study the impact of noise and approximation
on our models and methods.
\item
Compression and Representation. Develop provably optimal compression and representation schemes
for dynamic networks.
\end{itemize}


\stitle{Models for Dynamic Networks}

Models for dynamic networks provide a means for generating networks of arbitrary
size and well-parametrized characteristics. Models have limited predictive capability,
however:

\begin{itemize}
\item
Models play a critical role in analyses, by providing a prior. Traditional
analytics methods do a poor job here.
\item
Models allow analytic methods for estimating significance of results.
\item
Models can be used for validation.
\item
Models allow coarse-grain understanding of fluxes in networks.
\end{itemize}

\stitle{Models for Dynamic Networks}

Models for dynamic networks are in relative infancy. Generation models for
static networks are often viewed as pseudo-dynamic models.

\begin{itemize}
\item
Erdos-Renyi, Preferential Attachment, and Copying models.
\item
Community guided attachment and forest fire.
\item
Kronecker graphs.
\item
Microscopic models.
\end{itemize}

There have also been some true dynamic generation models, most notably the
node time-series correlation model. Developing a class of true dynamic models
that lend themselves to analytic methods remains an open question.


\stitle{Analytics on Dynamic Networks: Conservation}

{\em Given a sequence of networks, identify sub-networks that are (statistically)
significantly conserved over evolution trajectories.} This poses several
problems from points of view of modeling and method development:

\begin{itemize}
\item
Model selection. Models must be true to priors, while being amenable to analytical
quantification of significance.
\item
Ideally, significance cutoff should be an analytics parameter. Valid methods
must identify all sub-networks that exceed this significance threshold. There
are no known methods capable of solving this problem even at small scale
(let alone large trajectories over large graphs).
\item
Conservation over longitudinal/ horizontally partitioned trajectories each pose
challenges for distributed computations.
\end{itemize}


\stitle{Analytics on Dynamic Networks: Discriminant Analysis}

{\em When does a network significantly diverge from the model? What are components
responsible for this divergence?} This is sometimes also called {\em break} analysis
or change analysis.

\begin{itemize}
\item
This poses a computational problem known to be NP-Hard.
\item
Approximations for different models must be developed and their performance quantified.
\item
Must deal with overfitting and noise.
\end{itemize}


\stitle{Data Management and Graph Compression}

{\em Develop compression schemes that lend themselves to indexing and analytics in
compressed form.}

\begin{itemize}
\item
Generalize our notion of graph entropy to temporal domain.
\item
Integrate graph rewriting/ grammars with compression/ indexing.
\item
Develop distortion measures for lossy compression to deal with inherent noise in data.
\item
Develop compression algorithms to operate at scale.
\end{itemize}




\stitle{Part 2: Prior Results in the Area}


\stitle{Function \& Topology in Networks}

How does function relate to network topology? \\
\centerline{\includegraphics[width=0.8\textwidth]{images/functionaltopology.eps}}

\stitle {Prior Work on Topology and Function}

\begin{itemize}
\item
Conservation [ISMB 04/Bioinf. 04]
\item
Alignment [RECOMB 05/JCB 06]
\item
Modularity [RECOMB 06/JCB 07]
\item
Inference [Bioinf. 06]
\item
Pathway Annotation [ISMB 07/Bioinf. 07, PSB 08]
\item
Network Abstractions/ Annotations [ECCB 08/ Bioinf. 08]
\item
Modularity and Domain Interactions [APBC 10/ BMC Bioinf. 10]
\item
Pathway Interaction Maps [PSB 12]
\item
Pathway Inference [ISMB 12]
\end{itemize}


%Slide
\stitle{Evolution of Interactions}

\begin{itemize}

\item{``Evolution thinks modular''\mcite{Vespignani}{Nature Gen.}{2003}}

\bigitem{Cooperative tasks require all participating units}
 {\item \green{Selective pressure} on preserving \blue{interactions} \& \blue{interacting proteins}}

\bigitem{\blue{Nodes} organized in cohesive patterns are highly \green{conserved}
\mcite{Wuchty et al.}{Nature Gen.}{2003}}
{\item \blue{Functional modules} are likely to be consistently conserved}

\bigitem{\green{Orthologs} of \blue{interacting nodes} are likely to interact
\mcite{Wagner}{Mol. Bio. Evol.}{2001}}
{\item Conservation of \blue{interactions} may provide clues on conservation of \blue{function}}

\item{\blue{Interacting nodes} follow similar \green{evolutionary trajectories}
\mcite{Pellegrini et al.}{PNAS}{1999}}
\end{itemize}

%Slide
\stitle{Computational Analysis of Biological Networks}

\begin{itemize}

\bigitem{\blue{Clustering}}
{\item \green{Interaction network:} Proteins in functional modules densely
       interact with each other
 \item \green{Gene expression:} Genes coding cooperating proteins are likely to be
co-regulated
 \item \green{Phylogenetic profiles:} Interacting proteins are likely to have co-evolved
}

\bigitem{\blue{Graph Mining}}
{
\item Common topological motifs and \red{frequent interaction patterns}
reveal conserved modularity
}

\bigitem{\blue{Graph Alignment}}
{
\item \red{Conservation/divergence} of pathways, complexes, and functional
modules
}

\end{itemize}


\stitle{Frequent Interaction Patterns: Computational Problem}

\begin{itemize}
\bigitem{Given a set of \blue{proteins} $V$ a set of
\green{interactions} $E$, and a \red{many-to-many} mapping from $V$ to
a set of \blue{ortholog groups} $\La=\{l_1,l_2,...,l_n\}$,
the corresponding interaction network is a \green{labeled graph}
$G=(V,E,\La)$.}
{
 \item $v \in V(G)$ is associated with a set of
ortholog groups $L(v) \subseteq \La$.
 \item $uv \in E(G)$ represents an interaction between $u$ and $v$.
}

\item
$S$ is a \green{sub-network} of  $G$, \ie, $S \sqsubseteq G$
if there is an \blue{injective} mapping  $\phi:V(S)\rightarrow V(G)$ such
that for all $v\in V(S)$, $L(v) \subseteq L(\phi(v))$ and for all
$uv \in E(S)$, $\phi(u)\phi(v)\in E(G)$.

\bigitem{\red{Maximal frequent sub-network discovery}}
{
\item
\blue{Instance:} A set of interaction networks
$\G=\{G_1=(V_1,E_1,\La),G_2=(V_2,E_2,\La),...,G_m=(V_m,E_m,\La)\}$,
each belonging to a different organism, and a \green{frequency} threshold
$\minsup$.
\item
\blue{Problem:} Let $H(S)=\{G_i:S\sqsubseteq G_i\}$ be the \green{occurrence} set
of graph $S$. Find all \blue{connected} subgraphs $S$ such that
$|H(S)|\geq \minsup$, \ie, $S$ is a \green{frequent} subgraph
in $\G$ and for all $S' \sqsupset S$, $H(S) \neq H(S')$, \ie,
$S$ is \red{maximal}.
}
\end{itemize}

%Slide
\stitle{Ortholog Contraction}

\begin{itemize}
\item {\blue{Contract orthologous nodes into a single node}}
\bigitem {\green{No} \red{subgraph isomorphism}}
{\item Graphs are \blue{uniquely identified} by their edge sets}
\bigitem{Frequent sub-networks are \green{preserved} $\Rightarrow$ \green{No} \red{information loss}}
{\item Sub-networks that are frequent in general graphs are also frequent in
       their ortholog-contracted representation}
\bigitem{Discovered frequent sub-networks are still \green{biologically interpretable}!}
{
\item Interaction between proteins becomes interaction between ortholog groups
\item Ortholog-contraction may be thought of as going back in evolutionary history (to what point?)
}

\end{itemize}
%\vspace{0.3in}
%\centerline{
%\epsfig{file=unique1.eps,width=4.5in}
%}

%Slide
\stitle{Ortholog Contraction in PPI Networks}

\begin{itemize}
\item Interaction between \blue{proteins} $\rightarrow$ Interaction between \green{ortholog groups} or \green{protein families}
\end{itemize}

\vspace{0.5in}
\centerline{\begin{psfrags}\begin{small}
\psfrag{Rrp4}[c][c]{Rrp4}
\psfrag{Rrp43}[c][c]{Rrp43}
\psfrag{Mtr3}[c][c]{Mtr3}
\psfrag{Ski6}[c][c]{Ski6}
\psfrag{Csr4}[c][c]{Csr4}
\psfrag{3013}[c][c]{\red{KOG3013}}
\psfrag{1613}[c][c]{{\color{yellow}KOG1613}}
\psfrag{1068}[c][c]{\green{KOG1068}}
\psfrag{3409}[c][c]{\blue{KOG3409}}
\epsfig{file=lgraph.eps,height=2.5in}
\end{small}\end{psfrags}}

%Slide
\stitle{Preservation of Sub-networks}

\blue{Theorem:} Let $\tilde{G}$ be the ortholog-contracted graph obtained
by contracting the orthologous nodes of network $G$. Then, \green{ if $S$
is a subgraph of $G$, $\tilde{S}$ is a subgraph of $\tilde{G}$}.

\blue{Corollary:} The ortholog-contracted representation of any frequent
sub-network is also frequent in the set of ortholog-contracted graphs.

\vspace{1in}
\centerline{\begin{psfrags}
\psfrag{G}[c][c]{$G$}
\psfrag{G2}[c][c]{$\tilde{G}$}
\epsfig{file=preserve.eps,height=2.5in}
\end{psfrags}}

%Slide
\stitle{Results: Mining PPI Networks}

\begin{itemize}
\bigitem{PPI networks for \blue{9 eukaryotic organisms} derived from BIND and DIP}
{\item {\sl A. thaliania, O. sativa, S. cerevisiae, C. elegans, D. melanogaster,
            H. sapiens, B. taurus, M. musculus, R. norvegicus}
 \item \# of \green{proteins} ranges from 288 ({\sl Arabidopsis}) to 8577 ({\sl fruit fly})
 \item \# of \green{interactions} ranges from 340 ({\sl rice}) to 28829 ({\sl fruit fly})
}
\bigitem{Ortholog contraction}
{\item Group proteins according to existing \blue{COG} ortholog clusters
 \item Merge \blue{Homologene} groups into COG clusters
 \item Cluster remaining proteins via \blue{BLASTCLUST}
 \item Ortholog-contracted {\sl fruit fly} network contains 11088 \green{interactions}
 between 2849 \green{ortholog groups}
}

\item {\sc Mule} is available at \\
\blue{\url{http://www.cs.purdue.edu/homes/koyuturk/mule/}}
\end{itemize}

\stitle{Frequent Protein Interaction Patterns}

\vspace{1in}
\centerline{
\begin{psfrags}
\scriptsize
\psfrag{Pattern}[c][c]{{\sl Pattern}}
\psfrag{CE}[lt][lt]{{\sl C. elegans}}
\psfrag{SC}[l][l]{{\sl S. cerevisiae}}
\psfrag{DM}[ct][ct]{{\sl D. melanogaster}}
\leavevmode
\epsfig{file=ribo.eps, width=4.5in}
\end{psfrags}
}
\vspace{0.5in}
\centerline{\blue{Small nuclear ribonucleoprotein complex} (\green{$p < 2e-43$})}

\stitle{Frequent Protein Interaction Patterns}

\vspace{1in}
\centerline{
\begin{psfrags}
\scriptsize
\psfrag{Pattern}[c][c]{{\sl Pattern}}
\psfrag{HS}[c][c]{{\sl H. sapiens}}
\psfrag{SC}[c][c]{{\sl S. cerevisiae}}
\psfrag{BT}[c][c]{{\sl B. taurus}}
\leavevmode
\epsfig{file=arp23.eps, width=4.5in}
\end{psfrags}
}
\vspace{0.5in}
\centerline{\blue{Actin-related protein Arp2/3 complex} (\green{$p < 9e-11$})}

\stitle{Frequent Protein Interaction Patterns}

\vspace{1in}
\centerline{
\begin{psfrags}
\scriptsize
\psfrag{Pattern}[c][c]{{\sl Pattern}}
\psfrag{HS}[c][c]{{\sl H. sapiens}}
\psfrag{DM}[c][c]{{\sl S. cerevisiae}}
\psfrag{SC}[l][l]{{\sl D. melanogaster}}
\leavevmode
\epsfig{file=vac.eps, width=6in}
\end{psfrags}
}
\vspace{0.5in}
\centerline{\blue{Endosomal sorting} (\green{$p < 1e-78$})}


\stitle{Modular Phylogenetics}

\begin{itemize}
\item Top eight groups of three organisms
that contain most frequent connected sub-networks and interactions
\end{itemize}

\begin{center}
\small{
\begin{tabular}{lcc}
\hline
 & \green{\# frequent} & \blue{\# frequent} \\
\red{Organism set} & \green{sub-networks} &  \blue{interactions} \\
\hline
{\sl C. elegans}, {\sl D. melanogaster}, {\sl H. sapiens} & 8 & 134\\
{\sl S. cerevisiae}, {\sl D. melanogaster}, {\sl H. sapiens} & 20 & 126\\
{\sl D. melanogaster}, {\sl H. sapiens}, {\sl M. musculus} & 17 & 86\\
{\sl S. cerevisiae}, {\sl C. elegans}, {\sl D. melanogaster} & 15 & 77\\
{\sl S. cerevisiae}, {\sl C. elegans}, {\sl H. sapiens} & 6 & 50\\
{\sl S. cerevisiae}, {\sl H. sapiens}, {\sl M. musculus} & 10 & 26\\
{\sl C. elegans}, {\sl H. sapiens}, {\sl M. musculus} & 5 & 23\\
{\sl H. sapiens}, {\sl M. musculus}, {\sl R. norvegicus} & 10 & 23\\
\hline
\end{tabular}
}
\end{center}

%Slide
\stitle{Runtime Characteristics}

\begin{center}
\blue{Comparison with isomorphism-based algorithms}\\
\green{FSG}~\mcite{Kuramochi \& Karypis}{ICDM}{2001}, \green{gSpan}~\mcite{Yan \& Han}{KDD}{2003}
%\begin{small}
\begin{scriptsize}
\begin{tabular}{lccccccccc}
\hline
        &             & \hspace{0.3cm} & \multicolumn{3}{c}{FSG} & \hspace{0.3cm} & \multicolumn{3}{c}{{\sc Mule}}\\
        & Minimum    &  & Runtime & Largest & Number of & & Runtime & Largest & Number of \\
Dataset & Support (\%)& & (secs.) & pattern & patterns  & & (secs.) & pattern & patterns \\
\hline
 & 20 & & 0.2 & 9 & 12 & & 0.01 & 9 & 12\\
 & 16 & & 0.7 & 10 & 14 & & 0.01 & 10 & 14\\
 Glutamate & 12 & & 5.1 & 13 & 39 & & 0.10 & 13 & 39\\
 & 10 & & 22.7 & 16 & 34 & & 0.29 & 15 & 34\\
 & 8 & & 138.9 & 16 & 56 & & 0.99 & 15 & 56\\
\hline
 & 24 & & 0.1 & 8 & 11 & & 0.01 & 8 & 11\\
 & 20 & & 1.5 & 11 & 15 & & 0.02 & 11 & 15\\
 Alanine & 16 & & 4.0 & 12 & 21 & & 0.06 & 12 & 21\\
 & 12 & & 112.7 & 17 & 25 & & 1.06 & 16 & 25 \\
 & 10 & & 215.1 & 17 & 34 & & 1.72 & 16 & 34\\
\hline
\end{tabular}
%\end{small}
\end{scriptsize}
\end{center}

\center{
\blue{Extraction of contracted patterns}
\begin{scriptsize}
\begin{tabular}{cccccccccc}
\hline
\multicolumn{4}{c}{{Glutamate metabolism, $\sigma=8\%$}} &\hspace{0.7cm} &\multicolumn{4}{c}{{Alanine metabolism, $\sigma=10\%$}}\\
Size of & \multicolumn{2}{c}{Extraction time} & Size of & & Size of & \multicolumn{2}{c}{Extraction time} & Size of \\
contracted &  \multicolumn{2}{c}{(secs.)} & extracted  & & contracted &  \multicolumn{2}{c}{(secs.)}  & extracted\\
pattern    & FSG & gSpan & pattern & & pattern & FSG & gSpan & pattern\\
\hline
15 & 10.8 & 1.12 & 16 & & 16 & 54.1 & 10.13 & 17 \\
14 & 12.8 & 2.42 & 16 & & 16 & 24.1 & 3.92  & 16 \\
13 & 1.7  & 0.31 & 13 & & 12 & 0.9  & 0.27  & 12 \\
12 & 0.9  & 0.30 & 12 & & 11 & 0.4  & 0.13  & 11 \\
11 & 0.5  & 0.08 & 11 &  & 8 & 0.1  & 0.01  & 8  \\
\hline
\multicolumn{4}{l}{Total number of patterns: 56} & & \multicolumn{4}{l}{Total number of patterns: 34}\\
\multicolumn{4}{l}{Total runtime of FSG alone: 138.9 secs.} & & \multicolumn{4}{l}{Total runtime of FSG alone :215.1 secs.}\\
\multicolumn{4}{l}{Total runtime of {\sc Mule}+FSG: 0.99+100.5 secs.} & & \multicolumn{4}{l}{Total runtime of {\sc Mule}+FSG: 1.72+160.6 secs.}\\
\multicolumn{4}{l}{Total runtime of {\sc Mule}+gSpan: 0.99+16.8 secs.} & & \multicolumn{4}{l}{Total runtime of {\sc Mule}+gSpan: 1.72+31.0 secs.}\\
\hline
\end{tabular}
\end{scriptsize}}


%Slide
\stitle{Pairwise Alignment of PPI Networks}

\begin{itemize}

\bigitem{Given two PPI networks that belong to two different organisms,
identify sub-networks that are \blue{similar} to each other}
{\item \blue{Biological meaning}
 \item \green{Mathematical modeling}}

\bigitem{Existing algorithms}
{\item PathBLAST aligns \blue{pathways} (linear chains) to simplify the problem while maintaining biological meaning
\mcite{Kelley et al.}{PNAS}{2004}
\item NetworkBLAST compares \blue{conserved complex model} with \green{null model} to identify significantly conserved subnets
\mcite{Sharan et al.}{J. Comp. Biol.}{2005}
}

\bigitem{Our approach~\mcite{Koyut\"urk, Kim, Topkara, Subramaniam, Szpankowski, \& Grama}{J. Comp. Biol.}{2006}}
{\item Guided by \blue{models of evolution}
 \item \blue{Scores} evolutionary events
 \item Identifies sets of proteins that induce \green{high-scoring sub-network pairs}
}

\end{itemize}

%Slide
\stitle{Evolution of PPI  Networks}

\begin{itemize}
\bigitem{\blue{Duplication}/\green{divergence} models for the evolution
of protein interaction networks}
{\item \blue{Interactions of duplicated proteins are also duplicated}
 \item \green{Duplicated proteins rapidly lose interactions through mutations}
}
\item Allows defining and scoring evolutionary events as graph-theoretical concepts
\end{itemize}

\vspace{0.6in}
\centerline{
\begin{psfrags}
\psfrag{u1}[c][c]{$u_1$}
\psfrag{u1p}[c][c]{$u_1'$}
\psfrag{u2}[c][c]{$u_2$}
\psfrag{u3}[c][c]{$u_3$}
\psfrag{Duplication}[c][c]{\blue{Duplication}}
\psfrag{Deletion}[c][c]{\red{Elimination}}
\psfrag{Insertion}[c][c]{\green{Emergence}}
\leavevmode
\epsfig{file=evolution.eps,width=8in}
\end{psfrags}}

%Slide
\stitle{Match, Mismatch, and Duplication}

\begin{itemize}
\bigitem{Evolutionary events as graph-theoretic concepts}
{\item A \green{match} $\in \M$ corresponds to two pairs of homolog proteins from each organism
       such that both pairs interact in both PPIs. A match is associated with
       \green{score} $\mu$.
\item A \red{mismatch} $\in \N$ corresponds to two pairs of homolog proteins from each organism such that
      only one pair is interacting. A mismatch is associated with
       \red{penalty} $\nu$.
\item A \blue{duplication} $\in D$ corresponds to a pair of homolog proteins that are in the same organism. A duplication is associated with \blue{score} $\delta$.
}
\end{itemize}

\centerline{
\begin{psfrags}
%\small
\psfrag{u1}[c][c]{$u_1$}
\psfrag{u2}[c][c]{$u_2$}
\psfrag{u3}[c][c]{$u_3$}
\psfrag{u4}[c][c]{$u_4$}
\psfrag{v1}[c][c]{$v_1$}
\psfrag{v2}[c][c]{$v_2$}
\psfrag{v3}[c][c]{$v_3$}
\psfrag{e1}[c][c]{$e_1$}
\psfrag{e2}[c][c]{$e_2$}
\psfrag{e3}[c][c]{$e_3$}
\psfrag{G}[c][c]{$G$:}
\psfrag{H}[c][c]{$H$:}
\leavevmode
\epsfig{file=alignment.eps, width=5in}
\end{psfrags}
}

%Slide
\stitle{Pairwise Alignment of PPIs as an Optimization Problem}

\begin{itemize}
\bigitem {\blue{Alignment score:}\\
$\sigma(\A(P))= \sum_{M \in \M}{\mu(M)} - \sum_{N \in \N}{\nu(N)}
           + \sum_{D \in \D}{\delta(D)}$}
{ \item Matches are rewarded for \green{conservatio}n of interactions
 \item Duplications are rewarded/penalized for functional \green{conservation}/\red{differentiation} after split
 \item Mismatches are penalized for functional \red{divergence} (what about experimental error?)
}

\item Scores are functions of similarity between associated proteins

\bigitem{\green{Problem:} Find all protein subset pairs with significant alignment score}
{\item High scoring protein subsets are likely to correspond to conserved
       modules}

\item A graph equivalent to BLAST
\end{itemize}


%Slide
\stitle{Weighted Alignment Graph}

\begin{itemize}
\item $\mathbf{G}(\mathbf{V},\mathbf{E}):$ $\mathbf{V}$ consists of all pairs of homolog proteins $\mathbf{v}=\{u\in U, v \in V\}$
\bigitem{An edge $\mathbf{vv'}=\{uv\}\{u'v'\}$ in $\mathbf{E}$ is a}
{\item \green{match edge} if $uu' \in E$ and $vv' \in V$, with weight
       $w(\mathbf{vv'})=\mu(uv,u'v')$
 \item \red{mismatch edge} if $uu' \in E$ and $vv' \notin V$ or vice versa, with weight
       $w(\mathbf{vv'})=-\nu(uv,u'v')$
 \item \blue{duplication edge} if $S(u,u') > 0$ or $S(v,v')>0$, with weight
       $w(\mathbf{vv'})=\delta(u,u')$ or $w(\mathbf{vv'})=\delta(v,v')$}

\end{itemize}

\vspace{0.3in}
\centerline{
\begin{psfrags}
\small
\psfrag{u1v1}[r][r]{$\{u_1,v_1\}$}
\psfrag{u2v1}[l][l]{$\{u_2,v_1\}$}
\psfrag{u3v3}[c][c]{$\{u_3,v_3\}$}
\psfrag{u4v2}[l][l]{$\{u_4,v_2\}$}
\psfrag{u4v4}[r][r]{$\{u_4,v_4\}$}
\psfrag{m}[c][c]{$\mu$}
\psfrag{n}[c][c]{-$\nu$}
\psfrag{d}[c][c]{-$\delta$}
\leavevmode
\epsfig{file=product.eps, height=3in}
\end{psfrags}
}

%Slide
\stitle{Maximum Weight Induced Subgraph Problem}

\begin{itemize}
\bigitem{\blue{Definition:} (\green{{\sc MaWISh}})}
{\item Given graph $\G(\V,\E)$ and a constant $\epsilon$,
find $\tilde{\V} \in \V$ such that
$\sum_{\vv,\uu \in \tilde{\V}}{w(\vv\uu)} \geq \epsilon$.
 \item NP-complete
}

\bigitem{\blue{Theorem:} (\green{{\sc MaWISh} $\equiv$ Pairwise alignment})}
{\item If $\tilde{\V}$ is a solution for the {\sc MaWISh} problem on $\G(\V,\E)$,
then $P=\{\tilde{U}, \tilde{V}\}$ induces an alignment
$\A(P)$ with $\sigma(\A) \geq \epsilon$ , where
$\tilde{\V} = \tilde{U} \times \tilde{V}$.}

\bigitem{\blue{Solution:} \green{Local} graph partitioning}
{
\item Greedy graph growing + iterative refinement
\item Linear-time heuristic
}

\item{Source code available at \\
\blue{\url{http://www.cs.purdue.edu/homes/koyuturk/mawish/}}}
\end{itemize}

\stitle{Alignment of Yeast and Fruit Fly PPI Networks}

\begin{center}
\begin{small}
\begin{tabular}{lcccccc}
\hline\hline
\blue{Rank} & \green{Score} & \red{$z$-score} & \blue{\# Proteins} & \green{\# Matches} & \red{\# Mismatches} & \blue{\# Dups.}\\
\hline\hline
1 & 15.97 & 6.6 & 18 (16, 5) & 28 & 6 & (4, 0)\\
 & \multicolumn{6}{l}{protein amino acid phosphorylation (69\%)}\\
  &  \multicolumn{6}{l}{JAK-STAT cascade (40\%)}\\
\hline
2 & 13.93 & 3.7 & 13 (8, 7) & 25 & 7 & (3, 1)\\
 & \multicolumn{6}{l}{endocytosis (50\%) / calcium-mediated signaling (50\%)}\\
\hline
5 & 8.22 & 13.5 & 9 (5, 3) & 19 & 11 & (1, 0)\\
 & \multicolumn{6}{l}{invasive growth (sensu Saccharomyces) (100\%)}\\
 &  \multicolumn{6}{l}{oxygen and reactive oxygen species metabolism (33\%)}\\
\hline
6 & 8.05 & 7.6 & 8 (5, 3) & 12 & 2 & (0, 1)\\
 & \multicolumn{6}{l}{ubiquitin-dependent protein catabolism (100\%)}\\
 &  \multicolumn{6}{l}{mitosis (67\%)}\\
\hline
21 & 4.36 & 6.2 & 9 (5, 4) & 18 & 13 & (0, 5)\\
 & \multicolumn{6}{l}{cytokinesis (100\%, 50\%)}\\
\hline
30 & 3.76 & 39.6 & 6 (3, 5) & 5 & 1 & (0, 6)\\
 & \multicolumn{6}{l}{DNA replication initiation (100\%, 80\%)}\\
\hline\hline
\end{tabular}
\end{small}
\end{center}

\stitle{Subnets Conserved in Yeast and Fruit Fly}

\vspace{0.5in}
\centerline{Proteosome regulatory particle subnet}
\vspace{0.2in}
\begin{psfrags}
\begin{scriptsize}
\psfrag{SC}[c][c]{{\sl S.Cerevisiae}}
\psfrag{DM}[c][c]{{\sl D.Melanogaster}}
\centerline{\epsfig{file=4932_7227_6.eps, width=5.0in}}
\end{scriptsize}
\end{psfrags}

\vspace{0.5in}
\centerline{Calcium-dependent stress-activated signaling pathway}
\vspace{0.2in}
\begin{psfrags}
\begin{scriptsize}
\psfrag{SC}[c][c]{{\sl S.Cerevisiae}}
\psfrag{DM}[c][c]{{\sl D.Melanogaster}}
\centerline{\epsfig{file=4932_7227_2.eps, width=5.0in}}
\end{scriptsize}
\end{psfrags}

%Slide

\stitle{Statistical Significance of Modularity}

\begin{itemize}
\bigitem{Existing techniques}
{
\item Mostly computational (\eg, Monte-Carlo simulations)
\item Compute probability that \red{the} pattern exists rather than
      \green{a} pattern with \blue{the property} (\eg, size, density) exists
\item \red{Overestimation of significance}
}

\bigitem{Random graph models} {
\item PPI networks generally exhibit \blue{power-law} property (or
exponential, geometric, etc.)
\item Analysis simplified through \green{independence} assumption
\item Independence assumption may cause problems for networks with
\red{arbitrary degree distribution}
\item $P(uv \in E) = d_ud_v/|E|$, where $d_u$ is expected degree
of $u$, but generally $d_{\max}^2 > |E|$ for PPI networks
 }

 \item Analytical techniques based on simplified
 models~\mcite{Koyut\"urk, Grama, \& Szpankowski}{RECOMB}{2006}
\end{itemize}

\stitle{Significance of Dense Subgraphs}
\begin{itemize}
\item{A subnet of $r$ proteins is said to be \blue{$\rho$-dense} if
$F(r) \geq \rho r^2$, where $F(r)$ is the number of interactions
between these $r$ proteins}

\bigitem{What is the expected size of the \green{largest}
$\rho$-dense subgraph in a \red{random graph}?} {\item Any
$\rho$-dense subgraph with \green{larger size} is
\blue{statistically significant}!}

\bigitem{$G(n,p)$ model}{
\item $n$ proteins, each interaction occurs with probability $p$
\item \blue{Simple} enough to facilitate rigorous analysis
\item If we let $p=d_{\max}/n$, largest $\rho$-dense subgraph in $G(n,p)$
\green{stochastically dominates} that in a graph with arbitrary
degree distribution }
\end{itemize}

\stitle{Largest Dense Subgraph}

\begin{itemize}
\item
\blue{Theorem:}
If $G$ is a random graph with $n$ nodes, where every edge exists
with probability $p$, then
\begin{equation}
~~~~~~~~~~~~~\lim_{n\rightarrow \infty} \frac{R_{\rho}}{\log n}=
\frac{1}{\kappa(p,\rho)}~~~~~~~~~~~~~~~~~~(pr.),
\end{equation}
where
\begin{equation}
\kappa(p,\rho) = \rho \log \frac{\rho}{p} + (1-\rho) \log
\frac{1-\rho}{1-p}.
\end{equation}
More precisely,
\begin{equation}
P(R_{\rho} \geq r_0) \leq  O\left(\frac{\log
n}{n^{1/\kappa(p,\rho)}}\right),
\end{equation}
where
\begin{equation}
r_0 = \frac{\log n -\log\log n + \log \kappa(p,\rho)}
{\kappa(p,\rho)} \label{eq:r0}
\end{equation}
for large $n$.
\end{itemize}

\stitle{Generalizing Results to Complex Models}
\begin{itemize}
\bigitem{Piecewise $G(n,p)$ model} {
\item \green{Few proteins} with \blue{many interacting partners}, \green{many proteins} with \blue{few interacting
partners}
\item Captures the basic characteristics of PPI networks
\item The size of largest dense subgraph is still proportional to
$\log n$ }

\bigitem{More general models} {
\item Increasing the number of pieces, we approach models with
characteristic degree distributions
\item Analysis of power-law graphs in progress}

\bigitem{Multiple networks: \blue{Conservation}}
{\item Superpose
graphs based on sequence homology}

\end{itemize}

\stitle{Algorithms Based on Statistical Significance}
\begin{itemize}
\item Identification of \green{topological modules}
\item Use \blue{statistical significance} as a \green{stopping
criterion} for graph clustering heuristics

\bigitem{HCS Algorithm~\mcite{Hartuv \& Shamir}{Inf. Proc.
Let.}{2000}} {
\item Find a minimum-cut bipartitioning of the network
\item If any of the parts is \blue{dense enough}, record it as a
dense cluster of proteins
\item Else, further partition them recursively
}

\bigitem{Use \green{statistical significance} to determine whether
a subgraph is sufficiently dense}{
\item For given number of proteins and interactions between them,
we can determine whether those proteins induce a significantly
dense subnet}
\end{itemize}

\stitle{Largest Dense Subgraph for Varying Density}

\vspace{1in}
\begin{psfrags}
\begin{scriptsize}
\psfrag{Density threshold}[t][t]{Density threshold} \psfrag{Size
of largest dense subgraph}[b][b]{Size of largest dense subgraph}
\psfrag{Size of largest conserved dense subgraph}[b][b]{Size of
largest conserved dense subgraph}
\centerline{
    \epsfig{file=scere.eps,width=4.5in}
    \hspace{0.5in}
    \epsfig{file=schs.eps,width=4.5in}
}
\end{scriptsize}
\end{psfrags}

\vspace{0.5in} \centerline{\hspace{0.8in}{\sl Yeast} PPI network
\hspace{1.6in} {\sl Yeast} \& {\sl Fruit Fly} PPI networks}



\stitle{Pathway Organization: Genetic Interactome}

Double mutants exhibit unexpected phenotypes, as compared to joint single mutations.

\begin{definition}
\begin{itemize}
\item {\color{red} \textbf{Negative Interactions}}: more severe phenotype than expected
\begin{itemize}
\item Also known as \textit{aggravating} or \textit{synergistic}
\end{itemize}

\item {\color{green} \textbf{Positive Interactions}}: Less severe phenotype than expected
\begin{itemize}
\item Also known as \textit{alleviating} or \textit{epistatic}
\end{itemize}
\end{itemize}
\end{definition}

Most commonly used:
\begin{description}
\item [Phenotype]: Growth rate
\item[Model]: Multiplicative null model
\end{description}



\stitle{Organization of Genetic Interactions}

\begin{definition}
\begin{itemize}
\item {Between-Pathway Model}
\begin{itemize}
\item Among genes participating in redundant functions
\end{itemize}
\item {Within-Pathway Model}
\begin{itemize}
\item Among genes with additive effect
\end{itemize}
\item {Indirect Effect}
\begin{itemize}
\item Among genes with distant functions that are not directly related
\end{itemize}
\end{itemize}
\end{definition}



\stitle{Between-Pathway Model (BPM)}

  \begin{multicols}{2}
  \begin{minipage}[t]{6.0in}
    %\column{.4\textwidth}
	\includegraphics[scale=.5]{figures/BPM}	
   \end{minipage}
  \begin{minipage}[t]{4.0in}
		\begin{itemize}
		\item Bi-cliquish structure
		\item Have been used to:		
		\begin{enumerate}
			\item Predict co-pathway membership of gene pairs
			\item Extract redundant pathways
		\end{enumerate}
	\end{itemize}
  \end{minipage}  
  \end{multicols}  




\stitle{KEGG Crosstalk Map}
  \begin{multicols}{2}
  \begin{minipage}[t]{0.55\textwidth}
	\includegraphics[width=\columnwidth, height=.8\textheight]{figures/KEGG_final}
  \end{minipage}
	  
  \begin{minipage}[t]{0.4\textwidth}
	\includegraphics[width=\columnwidth]{figures/Thresholding}
  \end{minipage}
  \end{multicols}  



\stitle{Interaction Port Case Study} {Crosstalk Between Protein Processing in ER and Proteasome}

     \includegraphics[width=\textwidth]{figures/ProtER}
	  


\stitle{The Interaction Map of Aging}
  
     \includegraphics[width=\textwidth]{Doc1}





\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{multicols}{2}
  \begin{minipage}[t]{3.0in}
        \vspace*{-6.0in}
        \includegraphics[scale=0.75]{figures/montecarlo.ps}
   \end{minipage}
  \hspace*{-1.0in}
  \begin{minipage}[t]{6.0in}         
      {\bf 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{minipage}     
\end{multicols}

}

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

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


  \vspace*{-1.0in}
\begin{minipage}{9in}
  \centering
  \raisebox{-0.5\height}{\includegraphics[height=4.0in]{figures/tau-TR-1000-crop.ps}}
  \hspace*{.2in}
  \raisebox{-0.5\height}{\includegraphics[height=4.0in]{figures/shared-LR-20-crop.ps}}
\end{minipage} \\

%\footnotesize{ 
%      \begin{figure}[h]
%        \includegraphics[width=4.0in]{figures/tau-TR-1000-crop.ps}
%      \end{figure}
%      \begin{figure}[h]
%        \includegraphics[width=4.0in]{figures/shared-LR-20-crop.ps}
%        \end{figure}
{\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]}







%\stitle{Experimental settings}
%We set the 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 $\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{
	\vspace*{-2.5in}
      \includegraphics[width=4.0in]{figures/match-graphs.ps}
      \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
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{center}
\begin{tabular}[h]{|l|l|l|}
\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 \\ \hline
\end{tabular}

\begin{tabular}[h]{|l|l|l|l|l|l|}
\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}
}

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












\stitle{Part 3: Systems Development}

In support of graph analytics, we have build extensive systems infrastructure for
programming at scale.

\begin{itemize}
\item
TransMR -- Transactional MapReduce that enables maps to operate on persistent
key-value stores while supporting well-defined semantics.
\item
TransDF   -- a Transactional Dynamic Dataflow environment that enables distributed
computations without heavy (three-copy) overheads, while supporting fault tolerance and
speculation.
\item
Concurrency management schemes for TransMR and TransDF.
\item
Distributed graph kernel library on TransMR.
\end{itemize}



\stitle{Acknowledgements}

\begin{itemize}
\item
To the US National Science Foundation for their funding.
\end{itemize}

\end{document}
