From 0f6b315caf29f67d89b876ee14178dc7b1db6254 Mon Sep 17 00:00:00 2001 From: jeanpouget-abadie Date: Fri, 15 May 2015 10:58:29 +0200 Subject: poster+beginning of experiments --- poster/CS284r_poster/beamerthemeconfposter.sty | 184 ++++++++ .../cracking_cascades_classposter.tex | 461 +++++++++++++++++++++ poster/WWW_poster/beamerthemeconfposter.sty | 184 ++++++++ poster/WWW_poster/poster.tex | 289 +++++++++++++ poster/beamerthemeconfposter.sty | 184 -------- poster/cracking_cascades_classposter.tex | 461 --------------------- poster/images/SEASLogo_RGB.png | Bin 0 -> 35972 bytes 7 files changed, 1118 insertions(+), 645 deletions(-) create mode 100644 poster/CS284r_poster/beamerthemeconfposter.sty create mode 100644 poster/CS284r_poster/cracking_cascades_classposter.tex create mode 100644 poster/WWW_poster/beamerthemeconfposter.sty create mode 100644 poster/WWW_poster/poster.tex delete mode 100644 poster/beamerthemeconfposter.sty delete mode 100644 poster/cracking_cascades_classposter.tex create mode 100644 poster/images/SEASLogo_RGB.png (limited to 'poster') diff --git a/poster/CS284r_poster/beamerthemeconfposter.sty b/poster/CS284r_poster/beamerthemeconfposter.sty new file mode 100644 index 0000000..bcba6a7 --- /dev/null +++ b/poster/CS284r_poster/beamerthemeconfposter.sty @@ -0,0 +1,184 @@ +%============================================================================== +% Beamer style for the poster template posted at +% www.nathanieljohnston.com/index.php/2009/08/latex-poster-template +% +% Created by the Computational Physics and Biophysics Group at Jacobs University +% https://teamwork.jacobs-university.de:8443/confluence/display/CoPandBiG/LaTeX+Poster +% Modified by Nathaniel Johnston (nathaniel@nathanieljohnston.com) in August 2009 +% ============================================================================= + +\ProvidesPackage{beamerthemeconfposter} +\RequirePackage{tikz} % for drawing the nice rounded boxes +\usetikzlibrary{arrows,backgrounds} +\RequirePackage[T1]{fontenc} +\RequirePackage{lmodern} +\RequirePackage{textcomp} +\RequirePackage{amsmath,amssymb} +\usefonttheme{professionalfonts} +\newcommand{\makeruleinbox}{{\usebeamercolor[bg]{block alerted title}\centering\hspace*{-0.7cm}\rule{\inboxrule}{0.5cm}}} +\usepackage{ragged2e} +\usepackage{wrapfig} +%----------------------------------------------------------- +% Define a whole bunch of custom colours and fonts +%----------------------------------------------------------- + +\definecolor{lgreen} {RGB}{180,210,100} +\definecolor{dblue} {RGB}{20,66,129} +\definecolor{ddblue} {RGB}{11,36,69} +\definecolor{lred} {RGB}{220,0,0} +\definecolor{nred} {RGB}{224,0,0} +\definecolor{norange}{RGB}{244,127,36} +\definecolor{nyellow}{RGB}{255,221,0} +\definecolor{ngreen} {RGB}{98,158,31} +\definecolor{dgreen} {RGB}{78,138,21} +\definecolor{nblue} {RGB}{28,130,185} +\definecolor{jblue} {RGB}{20,50,100} +\definecolor{jalpha} {RGB}{0,0,0} + +% set the basic colors +\setbeamercolor{palette primary} {fg=black,bg=white} +\setbeamercolor{palette secondary} {fg=black,bg=white} +\setbeamercolor{palette tertiary} {bg=jblue,fg=white} +\setbeamercolor{palette quaternary}{fg=black,bg=white} +\setbeamercolor{structure}{fg=jblue} +\setbeamercolor{titlelike} {bg=jblue,fg=white} +\setbeamercolor{frametitle} {bg=jblue!10,fg=jblue} +\setbeamercolor{cboxb}{fg=black,bg=jblue} +\setbeamercolor{cboxr}{fg=black,bg=red} + +% set colors for itemize/enumerate +\setbeamercolor{item}{fg=ngreen} +\setbeamercolor{item projected}{fg=white,bg=ngreen} + +% set colors for blocks +%\setbeamercolor{block title}{fg=ngreen,bg=white} +%\setbeamercolor{block body}{fg=black,bg=white} + +%set colors for alerted blocks (blocks with frame) +\setbeamercolor{block alerted title}{fg=white,bg=jblue} +\setbeamercolor{block alerted body}{fg=black,bg=jblue!10} + +% set the fonts +\setbeamerfont{section in head/foot}{series=\bfseries} +\setbeamerfont{block title}{series=\bfseries} +\setbeamerfont{block alerted title}{series=\bfseries} +\setbeamerfont{frametitle}{series=\bfseries} +\setbeamerfont{frametitle}{size=\Large} + +% set some beamer theme options +\setbeamertemplate{title page}[default][colsep=-4bp,rounded=true] +\setbeamertemplate{sections/subsections in toc}[square] +\setbeamertemplate{items}[circle] +\setbeamertemplate{blocks}[width=0.0] +\beamertemplatenavigationsymbolsempty + +% set bibliography style +\setbeamertemplate{bibliography item}[text] +\setbeamercolor{bibliography item}{fg=black,bg=white} +\setbeamercolor{bibliography entry author}{fg=black,bg=white} +\setbeamercolor{bibliography item}{fg=black,bg=white} + +% define some length variables that are used by the template +\newlength{\inboxwd} +\newlength{\iinboxwd} +\newlength{\inboxrule} +\makeatletter +\makeatother + +%============================================================================== +% build the poster title +%============================================================================== +\setbeamertemplate{headline}{ + \leavevmode + \begin{columns} + \begin{column}{.2\linewidth} + \vskip1cm + \centering + %\includegraphics[height=4in]{UIUC-logo} + \end{column} + \vspace{1cm} + \begin{column}{.6\linewidth} + \vskip1cm + \centering + \usebeamercolor{title in headline}{\color{jblue}\Huge{\textbf{\inserttitle}}\\[0.5ex]} + \usebeamercolor{author in headline}{\color{fg}\Large{\insertauthor}\\[1ex]} + \usebeamercolor{institute in headline}{\color{fg}\large{\insertinstitute}\\[1ex]} + \vskip1cm + \end{column} + \vspace{1cm} + \begin{column}{.2\linewidth} + \vskip1cm + \centering + %\includegraphics[height=4in]{graph500-logo} + \vskip1cm + \end{column} + \vspace{1cm} + \end{columns} + \vspace{0.5in} + \hspace{0.5in}\begin{beamercolorbox}[wd=47in,colsep=0.15cm]{cboxb}\end{beamercolorbox} + \vspace{0.1in} +} + +% Block definition +\setbeamertemplate{block begin} +{ + \par\vskip\medskipamount + \begin{beamercolorbox}[colsep*=0ex,dp={2ex},center]{block title} + \vskip-0.25cm + \usebeamerfont{block title}\large\insertblocktitle + \begin{flushleft} + \vskip-1cm + \begin{tikzpicture}[remember picture,overlay] + \shade [inner color=gray,outer color=white] + (0,0) rectangle (\textwidth,0.3cm); + \end{tikzpicture} + \end{flushleft} + \end{beamercolorbox} + {\parskip0pt\par} + \ifbeamercolorempty[bg]{block title} + {} + {\ifbeamercolorempty[bg]{block body}{}{\nointerlineskip\vskip-0.5pt}} + \usebeamerfont{block body} + \vskip-0.5cm + \begin{beamercolorbox}[colsep*=0ex,vmode]{block body} + \justifying +} + +\setbeamertemplate{block end} +{ + \end{beamercolorbox} + \vskip\smallskipamount +} + +% Alert block definition (with frame) +\setbeamertemplate{block alerted begin} +{ + \par\vskip\medskipamount + \begin{beamercolorbox}[sep=0ex,rounded=true,center,dp={2ex}]{block alerted title} + \vskip0.01cm + \usebeamerfont{block title}\large\insertblocktitle + \end{beamercolorbox} + {\parskip0pt\par} + \usebeamerfont{block body} + \vskip-0.8cm + \begin{beamercolorbox}[sep=0.5cm, rounded=true,center]{block alerted title} + \setlength{\inboxwd}{\linewidth} + \addtolength{\inboxwd}{-1cm} + \begin{beamercolorbox}[rounded=true,wd={\inboxwd},center]{block alerted body} + \setlength{\iinboxwd}{\inboxwd} + \setlength{\inboxrule}{\inboxwd} + \addtolength{\iinboxwd}{-0.5cm} + \addtolength{\inboxrule}{0.5cm} + \begin{center} + \begin{minipage}{\iinboxwd} + \justifying +} + +\setbeamertemplate{block alerted end} +{ + \end{minipage} + \end{center} + \end{beamercolorbox} + \end{beamercolorbox} + \vskip\smallskipamount +} \ No newline at end of file diff --git a/poster/CS284r_poster/cracking_cascades_classposter.tex b/poster/CS284r_poster/cracking_cascades_classposter.tex new file mode 100644 index 0000000..3f8204e --- /dev/null +++ b/poster/CS284r_poster/cracking_cascades_classposter.tex @@ -0,0 +1,461 @@ +\documentclass[final]{beamer} +\usepackage[utf8]{inputenc} +\usepackage[scale=1.6]{beamerposter} % Use the beamerposter package for laying out the poster + +\usetheme{confposter} % Use the confposter theme supplied with this template + +\usepackage{color, bbm} +\setbeamercolor{block title}{fg=dblue,bg=white} % Colors of the block titles +\setbeamercolor{block body}{fg=black,bg=white} % Colors of the body of blocks +\setbeamercolor{block alerted title}{fg=white,bg=dblue!70} % Colors of the highlighted block titles +\setbeamercolor{block alerted body}{fg=black,bg=dblue!10} % Colors of the body of highlighted blocks +% Many more colors are available for use in beamerthemeconfposter.sty + +%----------------------------------------------------------- +% Define the column widths and overall poster size +% To set effective sepwid, onecolwid and twocolwid values, first choose how many columns you want and how much separation you want between columns +% In this template, the separation width chosen is 0.024 of the paper width and a 4-column layout +% onecolwid should therefore be (1-(# of columns+1)*sepwid)/# of columns e.g. (1-(4+1)*0.024)/4 = 0.22 +% Set twocolwid to be (2*onecolwid)+sepwid = 0.464 +% Set threecolwid to be (3*onecolwid)+2*sepwid = 0.708 + +\newlength{\sepwid} +\newlength{\onecolwid} +\newlength{\twocolwid} +\newlength{\threecolwid} +\setlength{\paperwidth}{48in} % A0 width: 46.8in +\setlength{\paperheight}{40in} % A0 height: 33.1in +\setlength{\sepwid}{0.024\paperwidth} % Separation width (white space) between columns +\setlength{\onecolwid}{0.22\paperwidth} % Width of one column +\setlength{\twocolwid}{0.464\paperwidth} % Width of two columns +\setlength{\threecolwid}{0.708\paperwidth} % Width of three columns +\setlength{\topmargin}{-1in} % Reduce the top margin size +%----------------------------------------------------------- + +\usepackage{graphicx} % Required for including images + +\usepackage{booktabs} % Top and bottom rules for tables + + + +%---------------------------------------------------------------------------------------- +% TITLE SECTION +%---------------------------------------------------------------------------------------- + +\title{Sparse Recovery for Graph Reconstruction } % Poster title + +\author{Eric Balkanski, Jean Pouget-Abadie} % Author(s) + +\institute{Harvard University} % Institution(s) +%---------------------------------------------------------------------------------------- +\begin{document} +\addtobeamertemplate{block end}{}{\vspace*{2ex}} % White space under blocks +\addtobeamertemplate{block alerted end}{}{\vspace*{2ex}} % White space under highlighted (alert) blocks + +\setlength{\belowcaptionskip}{2ex} % White space under figures +\setlength\belowdisplayshortskip{2ex} % White space under equations + +\begin{frame}[t] % The whole poster is enclosed in one beamer frame + +\begin{columns}[t] % The whole poster consists of three major columns, the second of which is split into two columns twice - the [t] option aligns each column's content to the top + +\begin{column}{\sepwid}\end{column} % Empty spacer column + +\begin{column}{\onecolwid} % The first column + +%---------------------------------------------------------------------------------------- +% INTODUCTION +%---------------------------------------------------------------------------------------- + + +%\vspace{- 15.2 cm} +%\begin{center} +%{\includegraphics[height=7em]{logo.png}} % First university/lab logo on the left +%\end{center} + +%\vspace{4.6 cm} + +\begin{block}{Problem Statement} +\begin{center} +\bf{How can we reconstruct a graph on which observed cascades spread?} +\end{center} +\end{block} + + +%{\bf Graph Reconstruction}: + +%\begin{itemize} +%\item \{${\cal G}, \vec p$\}: directed graph, edge probabilities +%\item $F$: cascade generating model +%\item ${\cal M} := F\{{\cal G}, \vec p\}$: cascade +%\end{itemize} + +%{\bf Objective}: +%\begin{itemize} +%\item Find algorithm which computes $F^{-1}({\cal M}) = \{{\cal G}, \vec p\}$ w.h.p., i.e. recovers graph from cascades. +%\end{itemize} + +%{\bf Approach} +%\begin{itemize} +%\item Frame graph reconstruction as a {\it Sparse Recovery} problem for two cascade generating models. +%\end{itemize} + +%Given a set of observed cascades, the \textbf{graph reconstruction problem} consists of finding the underlying graph on which these cascades spread. We assume that these cascades come from the classical \textbf{Independent Cascade Model} where at each time step, newly infected nodes infect each of their neighbor with some probability. + +%In previous work, this problem has been formulated in different ways, including a convex optimization and a maximum likelihood problem. However, there is no known algorithm for graph reconstruction with theoretical guarantees and with a reasonable required sample size. + +%We formulate a novel approach to this problem in which we use \textbf{Sparse Recovery} to find the edges in the unknown underlying network. Sparse Recovery is the problem of finding the sparsest vector $x$ such that $\mathbf{M x =b}$. In our case, for each node $i$, we wish to recover the vector $x = p_i$ where $p_{i_j}$ is the probability that node $j$ infects node $i$ if $j$ is active. To recover this vector, we are given $M$, where row $M_{t,k}$ indicates which nodes are infected at time $t$ in observed cascade $k$, and $b$, where $b_{t+1,k}$ indicates if node $i$ is infected at time $t+1$ in cascade $k$. Since most nodes have a small number of neighbors in large networks, we can assume that these vectors are sparse. Sparse Recovery is a well studied problem which can be solved efficiently and with small error if $M$ satisfies certain properties. In this project, we empirically study to what extent $M$ satisfies the Restricted Isometry Property. + + +%--------------------------------------------------------------------------------- +%--------------------------------------------------------------------------------- + +\begin{block}{Voter Model} + +\begin{figure} +\centering +\includegraphics[width=0.6\textwidth]{images/voter.png} +\end{figure} + + + +\vspace{0.5 cm} +{\bf Description} + +\vspace{0.5 cm} + +\begin{itemize} +\item $\mathbb{P}$({\color{blue} blue} at $t=0) = p_{\text{init}}$ +\item $\mathbb{P}$({\color{blue} blue} at $t+1) = \frac{\text{Number of {\color{blue}blue} neighbors}}{\text{Total number of neighbors}}$ +\end{itemize} + +\vspace{0.5 cm} + +{\bf Sparse Recovery Formulation} + +\vspace{0.5 cm} + + +To recover the neighbors of $v_1$, observe which nodes are {\color{red} red} (1) or {\color{blue} blue} (0) at time step $t$: +\begin{align*} +&v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \hspace{0.2 cm} v_5 &\\ +\vspace{1 cm} +M = & \left( \begin{array}{cccc} +0 & 0 & 1 & 1 \\ +1 & 1 & 0 & 0 \\ +\end{array} \right) & \begin{array}{l} \hspace{ - 5cm} +\text{time step 0} \\ + \hspace{ - 5cm} \text{time step 1} \\ +\end{array} +\end{align*} + +and which color $v_1$ is at time step $t+1$ due to $M$: + +\begin{align*} +b_1 = & \left( \begin{array}{c} +1 \\ +1 \\ +\end{array} \right) & \begin{array}{l} \hspace{ - 5cm} +\text{time step 1} \\ + \hspace{ - 5cm} \text{time step 2} \\ + \end{array} +\end{align*} + +Then , + +\begin{equation} +\boxed{M \vec x_1 = \vec b_1 + \epsilon \nonumber} +\end{equation} + +where $(\vec x_{1})_j := \frac{\text{1}}{\text{deg}(i)} \cdot \left[\text{j parent of 1 in }{\cal G}\right] $ + + +\end{block} + + + + + +%--------------------------------------------------------------------------------- +%--------------------------------------------------------------------------------- + + +%--------------------------------------------------------------------------------- +%--------------------------------------------------------------------------------- + + + + + + +%--------------------------------------------------------------------------------- +%--------------------------------------------------------------------------------- + + + +\end{column} % End of the first column + +\begin{column}{\sepwid}\end{column} % Empty spacer column + +\begin{column}{\onecolwid} % The first column + +%---------------------------------------------------------------------------------------- +% CONSTRAINT SATISFACTION - BACKTRACKING +%---------------------------------------------------------------------------------------- +\begin{block}{Independent Cascades Model} +\begin{figure} +\centering +\includegraphics[width=0.6\textwidth]{images/icc.png} +\end{figure} + +\vspace{0.5 cm} + +{\bf Description} + +\vspace{0.5 cm} + +\begin{itemize} +\item Three possible states: {\color{blue} susceptible}, {\color{red} infected}, {\color{yellow} inactive } +\item $\mathbb{P}$(infected at t=0)$=p_{\text{init}}$ +\item Infected node $j$ infects its susceptible neighbors $i$ with probability $p_{j,i}$ independently +\end{itemize} + +\vspace{0.5 cm} + +{\bf Sparse Recovery Formulation} + +\vspace{0.5 cm} + +To recover the neighbors of $v_5$,observe which nodes are {\color{red} red} (1), {\color{blue} blue} (0), or {\color{yellow} yellow} (0) at time step $t$: +\begin{align*} +&v_1 \hspace{0.2 cm} v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \\ +\vspace{1 cm} +M = & \left( \begin{array}{cccc} +1 & 0 & 0 & 0 \\ +0 & 1 & 1 & 0 \\ +\end{array} \right) \begin{array}{l} \hspace{ 1cm} +\text{time step 0} \\ + \hspace{ 1cm} \text{time step 1} \\ + \end{array} +\end{align*} + +and if $M$ caused $v_5$ to be infected at time step $t+1$: + +\begin{align*} +b_5 = & \left( \begin{array}{c} +0 \\ +1 \\ +\end{array} \right) \begin{array}{l} \hspace{ 1cm} +\text{time step 1} \\ + \hspace{ 1cm} \text{time step 2} \\ + \end{array} +\end{align*} + + +Then, + +\begin{equation} +\boxed{e^{M \vec \theta_5} = (1 - \vec b_5) + \epsilon} \nonumber +\end{equation} + +where $(\vec \theta_5)_j := \log ( 1 - p_{j,5}) $ + +\vspace{1 cm} + + +This problem is a {\bf Noisy Sparse Recovery} problem, which has been studied extensively. Here, the vectors $\vec x_i$ are deg(i)-sparse. + + +\end{block} + +%---------------------------------------------------------------------------------------- + + + + + + + + + +%---------------------------------------------------------------------------------------- +% MIP +%---------------------------------------------------------------------------------------- + +% \begin{block}{RIP property} + +% %The Restricted Isometry Property (RIP) characterizes a quasi-orthonormality of the measurement matrix M on sparse vectors. + +% For all k, we define $\delta_k$ as the best possible constant such that for all unit-normed ($l$2) and k-sparse vectors $x$ + +% \begin{equation} +% 1-\delta_k \leq \|Mx\|^2_2 \leq 1 + \delta_k +% \end{equation} + +% In general, the smaller $\delta_k$ is, the better we can recover $k$-sparse vectors $x$! + +% \end{block} + +%---------------------------------------------------------------------------------------- + +\end{column} + +\begin{column}{\sepwid}\end{column} % Empty spacer column + +\begin{column}{\onecolwid} % The first column within column 2 (column 2.1) + + +%---------------------------------------------------------------------------------------- + + +\begin{block}{Algorithms} + +{\bf Voter Model} + +\begin{itemize} +\item Solve for each node i: +\begin{equation} +\min_{\vec x_i} \|\vec x_i\|_1 + \lambda \|M \vec x_i - \vec b_i \|_2 \nonumber +\end{equation} +\end{itemize} + +{\bf Independent Cascade Model} + +\begin{itemize} +\item Solve for each node i: +\begin{equation} +\min_{\vec \theta_i} \|\vec \theta_i\|_1 + \lambda \|e^{M \vec \theta_i} - (1 - \vec b_i) \|_2 \nonumber +\end{equation} +\end{itemize} + +\end{block} + +\begin{block}{Restricted Isometry Property (RIP)} +{\bf Definition} +\begin{itemize} +\item Characterizes a quasi-orthonormality of M on sparse vectors. + +\item The RIP constant $\delta_k$ is the best possible constant such that for all unit-normed ($l$2) and k-sparse vectors $x$: + +\begin{equation} +1-\delta_k \leq \|Mx\|^2_2 \leq 1 + \delta_k \nonumber +\end{equation} + +\item The smaller $\delta_k$ is, the better we can recover $k$-sparse vectors $x$. +\end{itemize} + + + + +\end{block} + +\begin{block}{Theoretical Guarantees} + +With small RIP constants $(\delta \leq 0.25)$ for $M$ and some assumption on the noise $\epsilon$: + +{\bf Theorem \cite{candes}} + +If node $i$ has degree $\Delta$ and $n_{\text{rows}}(M) \geq C_1 \mu \Delta \log n$, then, w.h.p., + +$$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{n_{\text{rows}}(M) }}$$ + + +\end{block} + + + + +%---------------------------------------------------------------------------------------- +% RESULTS +%---------------------------------------------------------------------------------------- + +\begin{block}{RIP Experiments} + +\begin{center} +\begin{table} +\begin{tabular}{c | c | c | c | c } +& $c$ = 100, &$c$ = 1000,& $c$ = 100, &$c$ = 1000,\\ +& $i$ = 0.1& $i$ = 0.1& $i$ = 0.05& $i$ = 0.05\\ + \hline + $\delta_4$ & 0.54 & 0.37 &0.43&0.23 \\ + \end{tabular} + \caption{RIP constant for a small graph. Here, $c$ is the number of cascades and $i$ is $p_{\text{init}}$.} +\end{table} +\end{center} + + +\end{block} + +%---------------------------------------------------------------------------------------- + + +\end{column} % End of the second column + +\begin{column}{\sepwid}\end{column} % Empty spacer column + +\begin{column}{\onecolwid} % The third column + +%---------------------------------------------------------------------------------------- +% IOVERALL COMPARISON +%---------------------------------------------------------------------------------------- + +%\vspace{- 14.2 cm} +%\begin{center} +%{\includegraphics[height=7em]{cmu_logo.png}} % First university/lab logo on the left +%\end{center} + +%\vspace{4 cm} + +\begin{alertblock}{Experimental Results} + + + + +\end{alertblock} + +%---------------------------------------------------------------------------------------- + + +%---------------------------------------------------------------------------------------- +% CONCLUSION +%---------------------------------------------------------------------------------------- + +\begin{block}{Conclusion} + +\begin{center} + + +{\bf Graph reconstruction can naturally be expressed as Sparse Recovery. Understanding properties of $M$, for example RIP, leads to theoretical guarantees on the reconstruction.} + +\end{center} + +\end{block} + +%---------------------------------------------------------------------------------------- +% REFERENCES +%---------------------------------------------------------------------------------------- + +\begin{block}{References} + +\begin{thebibliography}{42} + +\bibitem{candes} +Candès, E., and Plan, Y. +\newblock {\it A Probabilistic and RIPless Theory of Compressed Sensing} +\newblock Information Theory, IEEE Transactions on, 57(11): 7235--7254, +\newblock 2011. +\end{thebibliography} + +\end{block} + +%---------------------------------------------------------------------------------------- + +\end{column} % End of the third column + +\end{columns} % End of all the columns in the poster + +\end{frame} % End of the enclosing frame + + + +\end{document} diff --git a/poster/WWW_poster/beamerthemeconfposter.sty b/poster/WWW_poster/beamerthemeconfposter.sty new file mode 100644 index 0000000..bcba6a7 --- /dev/null +++ b/poster/WWW_poster/beamerthemeconfposter.sty @@ -0,0 +1,184 @@ +%============================================================================== +% Beamer style for the poster template posted at +% www.nathanieljohnston.com/index.php/2009/08/latex-poster-template +% +% Created by the Computational Physics and Biophysics Group at Jacobs University +% https://teamwork.jacobs-university.de:8443/confluence/display/CoPandBiG/LaTeX+Poster +% Modified by Nathaniel Johnston (nathaniel@nathanieljohnston.com) in August 2009 +% ============================================================================= + +\ProvidesPackage{beamerthemeconfposter} +\RequirePackage{tikz} % for drawing the nice rounded boxes +\usetikzlibrary{arrows,backgrounds} +\RequirePackage[T1]{fontenc} +\RequirePackage{lmodern} +\RequirePackage{textcomp} +\RequirePackage{amsmath,amssymb} +\usefonttheme{professionalfonts} +\newcommand{\makeruleinbox}{{\usebeamercolor[bg]{block alerted title}\centering\hspace*{-0.7cm}\rule{\inboxrule}{0.5cm}}} +\usepackage{ragged2e} +\usepackage{wrapfig} +%----------------------------------------------------------- +% Define a whole bunch of custom colours and fonts +%----------------------------------------------------------- + +\definecolor{lgreen} {RGB}{180,210,100} +\definecolor{dblue} {RGB}{20,66,129} +\definecolor{ddblue} {RGB}{11,36,69} +\definecolor{lred} {RGB}{220,0,0} +\definecolor{nred} {RGB}{224,0,0} +\definecolor{norange}{RGB}{244,127,36} +\definecolor{nyellow}{RGB}{255,221,0} +\definecolor{ngreen} {RGB}{98,158,31} +\definecolor{dgreen} {RGB}{78,138,21} +\definecolor{nblue} {RGB}{28,130,185} +\definecolor{jblue} {RGB}{20,50,100} +\definecolor{jalpha} {RGB}{0,0,0} + +% set the basic colors +\setbeamercolor{palette primary} {fg=black,bg=white} +\setbeamercolor{palette secondary} {fg=black,bg=white} +\setbeamercolor{palette tertiary} {bg=jblue,fg=white} +\setbeamercolor{palette quaternary}{fg=black,bg=white} +\setbeamercolor{structure}{fg=jblue} +\setbeamercolor{titlelike} {bg=jblue,fg=white} +\setbeamercolor{frametitle} {bg=jblue!10,fg=jblue} +\setbeamercolor{cboxb}{fg=black,bg=jblue} +\setbeamercolor{cboxr}{fg=black,bg=red} + +% set colors for itemize/enumerate +\setbeamercolor{item}{fg=ngreen} +\setbeamercolor{item projected}{fg=white,bg=ngreen} + +% set colors for blocks +%\setbeamercolor{block title}{fg=ngreen,bg=white} +%\setbeamercolor{block body}{fg=black,bg=white} + +%set colors for alerted blocks (blocks with frame) +\setbeamercolor{block alerted title}{fg=white,bg=jblue} +\setbeamercolor{block alerted body}{fg=black,bg=jblue!10} + +% set the fonts +\setbeamerfont{section in head/foot}{series=\bfseries} +\setbeamerfont{block title}{series=\bfseries} +\setbeamerfont{block alerted title}{series=\bfseries} +\setbeamerfont{frametitle}{series=\bfseries} +\setbeamerfont{frametitle}{size=\Large} + +% set some beamer theme options +\setbeamertemplate{title page}[default][colsep=-4bp,rounded=true] +\setbeamertemplate{sections/subsections in toc}[square] +\setbeamertemplate{items}[circle] +\setbeamertemplate{blocks}[width=0.0] +\beamertemplatenavigationsymbolsempty + +% set bibliography style +\setbeamertemplate{bibliography item}[text] +\setbeamercolor{bibliography item}{fg=black,bg=white} +\setbeamercolor{bibliography entry author}{fg=black,bg=white} +\setbeamercolor{bibliography item}{fg=black,bg=white} + +% define some length variables that are used by the template +\newlength{\inboxwd} +\newlength{\iinboxwd} +\newlength{\inboxrule} +\makeatletter +\makeatother + +%============================================================================== +% build the poster title +%============================================================================== +\setbeamertemplate{headline}{ + \leavevmode + \begin{columns} + \begin{column}{.2\linewidth} + \vskip1cm + \centering + %\includegraphics[height=4in]{UIUC-logo} + \end{column} + \vspace{1cm} + \begin{column}{.6\linewidth} + \vskip1cm + \centering + \usebeamercolor{title in headline}{\color{jblue}\Huge{\textbf{\inserttitle}}\\[0.5ex]} + \usebeamercolor{author in headline}{\color{fg}\Large{\insertauthor}\\[1ex]} + \usebeamercolor{institute in headline}{\color{fg}\large{\insertinstitute}\\[1ex]} + \vskip1cm + \end{column} + \vspace{1cm} + \begin{column}{.2\linewidth} + \vskip1cm + \centering + %\includegraphics[height=4in]{graph500-logo} + \vskip1cm + \end{column} + \vspace{1cm} + \end{columns} + \vspace{0.5in} + \hspace{0.5in}\begin{beamercolorbox}[wd=47in,colsep=0.15cm]{cboxb}\end{beamercolorbox} + \vspace{0.1in} +} + +% Block definition +\setbeamertemplate{block begin} +{ + \par\vskip\medskipamount + \begin{beamercolorbox}[colsep*=0ex,dp={2ex},center]{block title} + \vskip-0.25cm + \usebeamerfont{block title}\large\insertblocktitle + \begin{flushleft} + \vskip-1cm + \begin{tikzpicture}[remember picture,overlay] + \shade [inner color=gray,outer color=white] + (0,0) rectangle (\textwidth,0.3cm); + \end{tikzpicture} + \end{flushleft} + \end{beamercolorbox} + {\parskip0pt\par} + \ifbeamercolorempty[bg]{block title} + {} + {\ifbeamercolorempty[bg]{block body}{}{\nointerlineskip\vskip-0.5pt}} + \usebeamerfont{block body} + \vskip-0.5cm + \begin{beamercolorbox}[colsep*=0ex,vmode]{block body} + \justifying +} + +\setbeamertemplate{block end} +{ + \end{beamercolorbox} + \vskip\smallskipamount +} + +% Alert block definition (with frame) +\setbeamertemplate{block alerted begin} +{ + \par\vskip\medskipamount + \begin{beamercolorbox}[sep=0ex,rounded=true,center,dp={2ex}]{block alerted title} + \vskip0.01cm + \usebeamerfont{block title}\large\insertblocktitle + \end{beamercolorbox} + {\parskip0pt\par} + \usebeamerfont{block body} + \vskip-0.8cm + \begin{beamercolorbox}[sep=0.5cm, rounded=true,center]{block alerted title} + \setlength{\inboxwd}{\linewidth} + \addtolength{\inboxwd}{-1cm} + \begin{beamercolorbox}[rounded=true,wd={\inboxwd},center]{block alerted body} + \setlength{\iinboxwd}{\inboxwd} + \setlength{\inboxrule}{\inboxwd} + \addtolength{\iinboxwd}{-0.5cm} + \addtolength{\inboxrule}{0.5cm} + \begin{center} + \begin{minipage}{\iinboxwd} + \justifying +} + +\setbeamertemplate{block alerted end} +{ + \end{minipage} + \end{center} + \end{beamercolorbox} + \end{beamercolorbox} + \vskip\smallskipamount +} \ No newline at end of file diff --git a/poster/WWW_poster/poster.tex b/poster/WWW_poster/poster.tex new file mode 100644 index 0000000..eeee7b6 --- /dev/null +++ b/poster/WWW_poster/poster.tex @@ -0,0 +1,289 @@ +\documentclass[final]{beamer} +\usepackage[utf8]{inputenc} +\usepackage[scale=1.6]{beamerposter} % Use the beamerposter package for laying +\usetheme{confposter} % Use the confposter theme supplied with this template + +\usepackage{framed, amsmath, amsthm, amssymb} +\usepackage{color, bbm} +\setbeamercolor{block title}{fg=dblue,bg=white} % Colors of the block titles +\setbeamercolor{block body}{fg=black,bg=white} % Colors of the body of blocks +\setbeamercolor{block alerted title}{fg=white,bg=dblue!70} % Colors of the +\setbeamercolor{block alerted body}{fg=black,bg=dblue!10} % Colors of the body + +\newlength{\sepwid} +\newlength{\onecolwid} +\newlength{\twocolwid} +\newlength{\threecolwid} +\setlength{\paperwidth}{48in} % A0 width: 46.8in +\setlength{\paperheight}{40in} % A0 height: 33.1in +\setlength{\sepwid}{0.024\paperwidth} % Separation width (white space) between +\setlength{\onecolwid}{0.22\paperwidth} % Width of one column +\setlength{\twocolwid}{0.464\paperwidth} % Width of two columns +\setlength{\threecolwid}{0.708\paperwidth} % Width of three columns +\setlength{\topmargin}{-1in} % Reduce the top margin size +%----------------------------------------------------------- + +\usepackage{graphicx} +\usepackage{booktabs} + +%---------------------------------------------------------------------------------------- +% TITLE SECTION +%---------------------------------------------------------------------------------------- + +\title{Inferring Graphs from Cascades} % Poster title + +\author{Jean Pouget-Abadie, Thibaut Horel} % Author(s) + +\institute{Harvard University} % Institution(s) +%---------------------------------------------------------------------------------------- +\begin{document} +\addtobeamertemplate{block end}{}{\vspace*{2ex}} % White space under blocks +\addtobeamertemplate{block alerted end}{}{\vspace*{2ex}} % White space under + +\setlength{\belowcaptionskip}{2ex} % White space under figures +\setlength\belowdisplayshortskip{2ex} % White space under equations + +\begin{frame}[t] +\begin{columns}[t] +\begin{column}{\sepwid}\end{column} +\begin{column}{\onecolwid} % The first column + +%---------------------------------------------------------------------------------------- +% INTODUCTION +%---------------------------------------------------------------------------------------- + + +\vspace{- 12.2 cm} +\begin{center} +{\includegraphics[scale=2.5]{../images/SEASLogo_RGB.png}} +\end{center} + +\vspace{5 cm} + +\begin{block}{Problem Statement} + +\begin{itemize} + \item A {\bf diffusion process} describes the evolution of a behavior, which + is transmitted from node to node along the edges of a network. + \item If the network is {\bf unknown} and only the behaviors of nodes in time + is observed, for which diffusion processes can we recover the edges? In + how many measurements? +\end{itemize} + +{\bf Notation} +\begin{itemize} + \item $X^t_c \in {\{0,1\}}^n$ set of infected nodes at time $t$ in cascade $c$ + \item $p_{i,j}$: weight of directed edge $i\rightarrow j$ +\end{itemize} + +{\bf Objective} +\begin{itemize} + \item We observe $(c, t, X^t_c)$ + \item Find $\hat p$ such that $\|p - \hat p\|_2 \leq \epsilon$ +\end{itemize} + +\end{block} + +\begin{block}{Independent Cascade Model~\cite{Kempe:03}} + +\begin{figure} +\centering +\includegraphics[width=0.6\textwidth]{../images/voter.png} +\end{figure} + +\begin{itemize} + \item Probability that $j^{th}$ node gets infected: + \begin{framed} + \begin{align*} + \tag{IC} + \mathbb{P}\big[X^{t+1}_j = 1\,|\, X^{t}\big] + & = 1 - \prod_{i = 1}^m {(1 - p_{i,j})}^{X^t_i} \\ + & = 1 - \prod_{i = 1}^m e^{\Theta_{i,j}X^t_i} \\ + & = 1 - e^{\Theta_j \cdot X^t} + \end{align*} + \end{framed} + where $\Theta_{i,j} \equiv \log(1- p_{i,j})$ +\end{itemize} + +\end{block} + +\end{column} % End of the first column + +%----------------------------------------------------------------------------- +\begin{column}{\sepwid}\end{column} % Empty spacer column +%----------------------------------------------------------------------------- +\begin{column}{\onecolwid} % The first column + +\begin{block}{Voter Model} +\begin{figure} +\centering +\includegraphics[width=0.6\textwidth]{../images/icc.png} +\end{figure} + +\begin{itemize} + \item Probability that $j^{th}$ node gets infected: + \begin{framed} + \begin{equation*} + \tag{VT} + \mathbb{P}\big[X^{t+1}_j = 1\,|\, X^{t}\big] + = \sum_{i \in X^t} p_{i,j} = p_j \cdot X^t + \end{equation*} + \end{framed} +\end{itemize} + +\end{block} + + +\begin{block}{Reformulation} + +{\bf Generalized Linear Cascade Model} +\begin{itemize} + \item $f: \mathbb{R} \rightarrow [0,1]$: inverse link function + \item Probability depends on $f$-transform of scalar product: + \begin{framed} + $$\mathbb{P}(X^{t+1}_j = 1 | X^t) = f(\Theta_j \cdot X^t)$$ + \end{framed} +\end{itemize} + +{\bf Setup} +\begin{figure} + \centering + \includegraphics[scale=1.5]{../images/drawing.pdf} +\end{figure} + +{\bf Examples:} +\begin{itemize} + \item Independent Cascade (IC) Model: $f : z \mapsto 1-e^z$ + \item Voter model: $f : z \mapsto z$ + \item Discrete-version of continuous IC model~\cite{GomezRodriguez:2010} + \item Logistic cascades: $f: z\mapsto \frac{1}{1-e^z}$ +\end{itemize} + +\end{block} +\end{column} +%----------------------------------------------------------------------------- +\begin{column}{\sepwid}\end{column} +%----------------------------------------------------------------------------- + +\begin{column}{\onecolwid} + +\begin{block}{Sparse Recovery} + +\begin{itemize} + \item Solving for $A x = b$ when $A$ is non-degenerate is possible if + \begin{itemize} + \item $A$ is {\bf almost invertible} + \item $x$ is {\bf sparse} + \end{itemize} + \item If $x$ is solution to $\min L(x)$ where + $L$ is convex, then~\cite{Negahban:2009}~solve for: + \begin{equation*} + \min_x L(x) + \lambda \| x\| + \end{equation*} +\end{itemize} +\end{block} + +\begin{theorem} + {\bf Assumptions}: + \begin{itemize} + \item $f$ and $1-f$ are log-concave with log-gradient bounded by + $\frac{1}{\alpha}$ + \item $\nabla^2 {\cal L}$ verifies the $(S,\gamma)$-{\bf + RE} condition + \vspace{1cm} +\end{itemize} {\bf Algorithm}: + \begin{itemize} + \item Solve MLE program with $\lambda = 2\sqrt{\frac{\log m}{\alpha n}}$ + \begin{framed} + \begin{equation*} + \hat \theta_i \in \arg \max_{\theta} {\cal L}_i(\theta_i | x^1, + \dots x^n) - \lambda \|\theta_i\|_1 + \end{equation*} + \end{framed} + \end{itemize} + \vspace{1cm} + {\bf Guarantee} + With high probability: + \begin{framed} + \begin{equation*} + \|\hat \theta - \theta^*\|_2 \leq \frac{6}{\gamma} \sqrt{\frac{s \log + m}{\alpha n}} + \end{equation*} + \end{framed} + where $s$ is degree of node, $m$ is number of nodes, $n$ is the number of + observations +\end{theorem} + +\begin{block}{Restricted Eigenvalue Condition} + {\bf Definition} + \begin{itemize} + \item $C(S) \equiv \{ X :\|X_{\bar S}\|_1 \leq 3 \|X\|_1\}$ + \item Matrix $A$ verifies the $(\gamma, S)$-{(\bf RE)} condition if: + $$\forall X \in C({\cal S}), X^T A X \geq \gamma \|X\|_2^2$$ + \end{itemize} + + \vspace{1cm} + {\bf Hessian $\mapsto$ Gram Matrix} + \begin{itemize} + \item If $f$ and $1-f$ are $c$-strictly log-convex, we can replace the + condition on the $\nabla^2 {\cal L}$ by the same condition on the Gram + matrix $X^T X$. + \end{itemize} + \vspace{1cm} + {\bf Hessian $\mapsto$ Expected Hessian} + \begin{itemize} + \item If $\mathbb{E}[A]$ verifies the $(S, \gamma)$-{(\bf RE)} condition, + then $A$ verifies the $(S, \gamma/2)$-{(\bf RE)} + condition~\cite{vandegeer:2009} + \end{itemize} + +\end{block} + +\end{column} % End of the second column + +%----------------------------------------------------------------------------- +\begin{column}{\sepwid}\end{column} % Empty spacer column +%----------------------------------------------------------------------------- +\begin{column}{\onecolwid} % The third column + \begin{block}{Experimental validation} + \begin{figure} + \centering + \includegraphics[scale=1.2]{../images/watts_strogatz.pdf} + \caption{Watts-Strogatz, $300$ nodes, $4500$ edges, uniform edge weights, + constant $p_{init}$} + \end{figure} + \end{block} + + +\begin{block}{Conclusion} + \begin{itemize} + \item Introduce Generalized Linear Casacade model + \item Better finite sample guarantees~\cite{Netrapalli:2012, Abrahao:13, + Daneshmand:2014} + \item Interpretable conditions on Hessian + \item Lower bound+approximately sparse case developed in full + paper~\cite{Pouget:2015} + \end{itemize} +\end{block} + +%----------------------------------------------------------------------------- +% REFERENCES +%----------------------------------------------------------------------------- + +\begin{block}{References} + {\scriptsize + \bibliography{../../paper/sparse} +\bibliographystyle{plain}} +\end{block} + +%----------------------------------------------------------------------------- + +\end{column} % End of the third column + +\end{columns} % End of all the columns in the poster + +\end{frame} % End of the enclosing frame + + + +\end{document} diff --git a/poster/beamerthemeconfposter.sty b/poster/beamerthemeconfposter.sty deleted file mode 100644 index bcba6a7..0000000 --- a/poster/beamerthemeconfposter.sty +++ /dev/null @@ -1,184 +0,0 @@ -%============================================================================== -% Beamer style for the poster template posted at -% www.nathanieljohnston.com/index.php/2009/08/latex-poster-template -% -% Created by the Computational Physics and Biophysics Group at Jacobs University -% https://teamwork.jacobs-university.de:8443/confluence/display/CoPandBiG/LaTeX+Poster -% Modified by Nathaniel Johnston (nathaniel@nathanieljohnston.com) in August 2009 -% ============================================================================= - -\ProvidesPackage{beamerthemeconfposter} -\RequirePackage{tikz} % for drawing the nice rounded boxes -\usetikzlibrary{arrows,backgrounds} -\RequirePackage[T1]{fontenc} -\RequirePackage{lmodern} -\RequirePackage{textcomp} -\RequirePackage{amsmath,amssymb} -\usefonttheme{professionalfonts} -\newcommand{\makeruleinbox}{{\usebeamercolor[bg]{block alerted title}\centering\hspace*{-0.7cm}\rule{\inboxrule}{0.5cm}}} -\usepackage{ragged2e} -\usepackage{wrapfig} -%----------------------------------------------------------- -% Define a whole bunch of custom colours and fonts -%----------------------------------------------------------- - -\definecolor{lgreen} {RGB}{180,210,100} -\definecolor{dblue} {RGB}{20,66,129} -\definecolor{ddblue} {RGB}{11,36,69} -\definecolor{lred} {RGB}{220,0,0} -\definecolor{nred} {RGB}{224,0,0} -\definecolor{norange}{RGB}{244,127,36} -\definecolor{nyellow}{RGB}{255,221,0} -\definecolor{ngreen} {RGB}{98,158,31} -\definecolor{dgreen} {RGB}{78,138,21} -\definecolor{nblue} {RGB}{28,130,185} -\definecolor{jblue} {RGB}{20,50,100} -\definecolor{jalpha} {RGB}{0,0,0} - -% set the basic colors -\setbeamercolor{palette primary} {fg=black,bg=white} -\setbeamercolor{palette secondary} {fg=black,bg=white} -\setbeamercolor{palette tertiary} {bg=jblue,fg=white} -\setbeamercolor{palette quaternary}{fg=black,bg=white} -\setbeamercolor{structure}{fg=jblue} -\setbeamercolor{titlelike} {bg=jblue,fg=white} -\setbeamercolor{frametitle} {bg=jblue!10,fg=jblue} -\setbeamercolor{cboxb}{fg=black,bg=jblue} -\setbeamercolor{cboxr}{fg=black,bg=red} - -% set colors for itemize/enumerate -\setbeamercolor{item}{fg=ngreen} -\setbeamercolor{item projected}{fg=white,bg=ngreen} - -% set colors for blocks -%\setbeamercolor{block title}{fg=ngreen,bg=white} -%\setbeamercolor{block body}{fg=black,bg=white} - -%set colors for alerted blocks (blocks with frame) -\setbeamercolor{block alerted title}{fg=white,bg=jblue} -\setbeamercolor{block alerted body}{fg=black,bg=jblue!10} - -% set the fonts -\setbeamerfont{section in head/foot}{series=\bfseries} -\setbeamerfont{block title}{series=\bfseries} -\setbeamerfont{block alerted title}{series=\bfseries} -\setbeamerfont{frametitle}{series=\bfseries} -\setbeamerfont{frametitle}{size=\Large} - -% set some beamer theme options -\setbeamertemplate{title page}[default][colsep=-4bp,rounded=true] -\setbeamertemplate{sections/subsections in toc}[square] -\setbeamertemplate{items}[circle] -\setbeamertemplate{blocks}[width=0.0] -\beamertemplatenavigationsymbolsempty - -% set bibliography style -\setbeamertemplate{bibliography item}[text] -\setbeamercolor{bibliography item}{fg=black,bg=white} -\setbeamercolor{bibliography entry author}{fg=black,bg=white} -\setbeamercolor{bibliography item}{fg=black,bg=white} - -% define some length variables that are used by the template -\newlength{\inboxwd} -\newlength{\iinboxwd} -\newlength{\inboxrule} -\makeatletter -\makeatother - -%============================================================================== -% build the poster title -%============================================================================== -\setbeamertemplate{headline}{ - \leavevmode - \begin{columns} - \begin{column}{.2\linewidth} - \vskip1cm - \centering - %\includegraphics[height=4in]{UIUC-logo} - \end{column} - \vspace{1cm} - \begin{column}{.6\linewidth} - \vskip1cm - \centering - \usebeamercolor{title in headline}{\color{jblue}\Huge{\textbf{\inserttitle}}\\[0.5ex]} - \usebeamercolor{author in headline}{\color{fg}\Large{\insertauthor}\\[1ex]} - \usebeamercolor{institute in headline}{\color{fg}\large{\insertinstitute}\\[1ex]} - \vskip1cm - \end{column} - \vspace{1cm} - \begin{column}{.2\linewidth} - \vskip1cm - \centering - %\includegraphics[height=4in]{graph500-logo} - \vskip1cm - \end{column} - \vspace{1cm} - \end{columns} - \vspace{0.5in} - \hspace{0.5in}\begin{beamercolorbox}[wd=47in,colsep=0.15cm]{cboxb}\end{beamercolorbox} - \vspace{0.1in} -} - -% Block definition -\setbeamertemplate{block begin} -{ - \par\vskip\medskipamount - \begin{beamercolorbox}[colsep*=0ex,dp={2ex},center]{block title} - \vskip-0.25cm - \usebeamerfont{block title}\large\insertblocktitle - \begin{flushleft} - \vskip-1cm - \begin{tikzpicture}[remember picture,overlay] - \shade [inner color=gray,outer color=white] - (0,0) rectangle (\textwidth,0.3cm); - \end{tikzpicture} - \end{flushleft} - \end{beamercolorbox} - {\parskip0pt\par} - \ifbeamercolorempty[bg]{block title} - {} - {\ifbeamercolorempty[bg]{block body}{}{\nointerlineskip\vskip-0.5pt}} - \usebeamerfont{block body} - \vskip-0.5cm - \begin{beamercolorbox}[colsep*=0ex,vmode]{block body} - \justifying -} - -\setbeamertemplate{block end} -{ - \end{beamercolorbox} - \vskip\smallskipamount -} - -% Alert block definition (with frame) -\setbeamertemplate{block alerted begin} -{ - \par\vskip\medskipamount - \begin{beamercolorbox}[sep=0ex,rounded=true,center,dp={2ex}]{block alerted title} - \vskip0.01cm - \usebeamerfont{block title}\large\insertblocktitle - \end{beamercolorbox} - {\parskip0pt\par} - \usebeamerfont{block body} - \vskip-0.8cm - \begin{beamercolorbox}[sep=0.5cm, rounded=true,center]{block alerted title} - \setlength{\inboxwd}{\linewidth} - \addtolength{\inboxwd}{-1cm} - \begin{beamercolorbox}[rounded=true,wd={\inboxwd},center]{block alerted body} - \setlength{\iinboxwd}{\inboxwd} - \setlength{\inboxrule}{\inboxwd} - \addtolength{\iinboxwd}{-0.5cm} - \addtolength{\inboxrule}{0.5cm} - \begin{center} - \begin{minipage}{\iinboxwd} - \justifying -} - -\setbeamertemplate{block alerted end} -{ - \end{minipage} - \end{center} - \end{beamercolorbox} - \end{beamercolorbox} - \vskip\smallskipamount -} \ No newline at end of file diff --git a/poster/cracking_cascades_classposter.tex b/poster/cracking_cascades_classposter.tex deleted file mode 100644 index 3f8204e..0000000 --- a/poster/cracking_cascades_classposter.tex +++ /dev/null @@ -1,461 +0,0 @@ -\documentclass[final]{beamer} -\usepackage[utf8]{inputenc} -\usepackage[scale=1.6]{beamerposter} % Use the beamerposter package for laying out the poster - -\usetheme{confposter} % Use the confposter theme supplied with this template - -\usepackage{color, bbm} -\setbeamercolor{block title}{fg=dblue,bg=white} % Colors of the block titles -\setbeamercolor{block body}{fg=black,bg=white} % Colors of the body of blocks -\setbeamercolor{block alerted title}{fg=white,bg=dblue!70} % Colors of the highlighted block titles -\setbeamercolor{block alerted body}{fg=black,bg=dblue!10} % Colors of the body of highlighted blocks -% Many more colors are available for use in beamerthemeconfposter.sty - -%----------------------------------------------------------- -% Define the column widths and overall poster size -% To set effective sepwid, onecolwid and twocolwid values, first choose how many columns you want and how much separation you want between columns -% In this template, the separation width chosen is 0.024 of the paper width and a 4-column layout -% onecolwid should therefore be (1-(# of columns+1)*sepwid)/# of columns e.g. (1-(4+1)*0.024)/4 = 0.22 -% Set twocolwid to be (2*onecolwid)+sepwid = 0.464 -% Set threecolwid to be (3*onecolwid)+2*sepwid = 0.708 - -\newlength{\sepwid} -\newlength{\onecolwid} -\newlength{\twocolwid} -\newlength{\threecolwid} -\setlength{\paperwidth}{48in} % A0 width: 46.8in -\setlength{\paperheight}{40in} % A0 height: 33.1in -\setlength{\sepwid}{0.024\paperwidth} % Separation width (white space) between columns -\setlength{\onecolwid}{0.22\paperwidth} % Width of one column -\setlength{\twocolwid}{0.464\paperwidth} % Width of two columns -\setlength{\threecolwid}{0.708\paperwidth} % Width of three columns -\setlength{\topmargin}{-1in} % Reduce the top margin size -%----------------------------------------------------------- - -\usepackage{graphicx} % Required for including images - -\usepackage{booktabs} % Top and bottom rules for tables - - - -%---------------------------------------------------------------------------------------- -% TITLE SECTION -%---------------------------------------------------------------------------------------- - -\title{Sparse Recovery for Graph Reconstruction } % Poster title - -\author{Eric Balkanski, Jean Pouget-Abadie} % Author(s) - -\institute{Harvard University} % Institution(s) -%---------------------------------------------------------------------------------------- -\begin{document} -\addtobeamertemplate{block end}{}{\vspace*{2ex}} % White space under blocks -\addtobeamertemplate{block alerted end}{}{\vspace*{2ex}} % White space under highlighted (alert) blocks - -\setlength{\belowcaptionskip}{2ex} % White space under figures -\setlength\belowdisplayshortskip{2ex} % White space under equations - -\begin{frame}[t] % The whole poster is enclosed in one beamer frame - -\begin{columns}[t] % The whole poster consists of three major columns, the second of which is split into two columns twice - the [t] option aligns each column's content to the top - -\begin{column}{\sepwid}\end{column} % Empty spacer column - -\begin{column}{\onecolwid} % The first column - -%---------------------------------------------------------------------------------------- -% INTODUCTION -%---------------------------------------------------------------------------------------- - - -%\vspace{- 15.2 cm} -%\begin{center} -%{\includegraphics[height=7em]{logo.png}} % First university/lab logo on the left -%\end{center} - -%\vspace{4.6 cm} - -\begin{block}{Problem Statement} -\begin{center} -\bf{How can we reconstruct a graph on which observed cascades spread?} -\end{center} -\end{block} - - -%{\bf Graph Reconstruction}: - -%\begin{itemize} -%\item \{${\cal G}, \vec p$\}: directed graph, edge probabilities -%\item $F$: cascade generating model -%\item ${\cal M} := F\{{\cal G}, \vec p\}$: cascade -%\end{itemize} - -%{\bf Objective}: -%\begin{itemize} -%\item Find algorithm which computes $F^{-1}({\cal M}) = \{{\cal G}, \vec p\}$ w.h.p., i.e. recovers graph from cascades. -%\end{itemize} - -%{\bf Approach} -%\begin{itemize} -%\item Frame graph reconstruction as a {\it Sparse Recovery} problem for two cascade generating models. -%\end{itemize} - -%Given a set of observed cascades, the \textbf{graph reconstruction problem} consists of finding the underlying graph on which these cascades spread. We assume that these cascades come from the classical \textbf{Independent Cascade Model} where at each time step, newly infected nodes infect each of their neighbor with some probability. - -%In previous work, this problem has been formulated in different ways, including a convex optimization and a maximum likelihood problem. However, there is no known algorithm for graph reconstruction with theoretical guarantees and with a reasonable required sample size. - -%We formulate a novel approach to this problem in which we use \textbf{Sparse Recovery} to find the edges in the unknown underlying network. Sparse Recovery is the problem of finding the sparsest vector $x$ such that $\mathbf{M x =b}$. In our case, for each node $i$, we wish to recover the vector $x = p_i$ where $p_{i_j}$ is the probability that node $j$ infects node $i$ if $j$ is active. To recover this vector, we are given $M$, where row $M_{t,k}$ indicates which nodes are infected at time $t$ in observed cascade $k$, and $b$, where $b_{t+1,k}$ indicates if node $i$ is infected at time $t+1$ in cascade $k$. Since most nodes have a small number of neighbors in large networks, we can assume that these vectors are sparse. Sparse Recovery is a well studied problem which can be solved efficiently and with small error if $M$ satisfies certain properties. In this project, we empirically study to what extent $M$ satisfies the Restricted Isometry Property. - - -%--------------------------------------------------------------------------------- -%--------------------------------------------------------------------------------- - -\begin{block}{Voter Model} - -\begin{figure} -\centering -\includegraphics[width=0.6\textwidth]{images/voter.png} -\end{figure} - - - -\vspace{0.5 cm} -{\bf Description} - -\vspace{0.5 cm} - -\begin{itemize} -\item $\mathbb{P}$({\color{blue} blue} at $t=0) = p_{\text{init}}$ -\item $\mathbb{P}$({\color{blue} blue} at $t+1) = \frac{\text{Number of {\color{blue}blue} neighbors}}{\text{Total number of neighbors}}$ -\end{itemize} - -\vspace{0.5 cm} - -{\bf Sparse Recovery Formulation} - -\vspace{0.5 cm} - - -To recover the neighbors of $v_1$, observe which nodes are {\color{red} red} (1) or {\color{blue} blue} (0) at time step $t$: -\begin{align*} -&v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \hspace{0.2 cm} v_5 &\\ -\vspace{1 cm} -M = & \left( \begin{array}{cccc} -0 & 0 & 1 & 1 \\ -1 & 1 & 0 & 0 \\ -\end{array} \right) & \begin{array}{l} \hspace{ - 5cm} -\text{time step 0} \\ - \hspace{ - 5cm} \text{time step 1} \\ -\end{array} -\end{align*} - -and which color $v_1$ is at time step $t+1$ due to $M$: - -\begin{align*} -b_1 = & \left( \begin{array}{c} -1 \\ -1 \\ -\end{array} \right) & \begin{array}{l} \hspace{ - 5cm} -\text{time step 1} \\ - \hspace{ - 5cm} \text{time step 2} \\ - \end{array} -\end{align*} - -Then , - -\begin{equation} -\boxed{M \vec x_1 = \vec b_1 + \epsilon \nonumber} -\end{equation} - -where $(\vec x_{1})_j := \frac{\text{1}}{\text{deg}(i)} \cdot \left[\text{j parent of 1 in }{\cal G}\right] $ - - -\end{block} - - - - - -%--------------------------------------------------------------------------------- -%--------------------------------------------------------------------------------- - - -%--------------------------------------------------------------------------------- -%--------------------------------------------------------------------------------- - - - - - - -%--------------------------------------------------------------------------------- -%--------------------------------------------------------------------------------- - - - -\end{column} % End of the first column - -\begin{column}{\sepwid}\end{column} % Empty spacer column - -\begin{column}{\onecolwid} % The first column - -%---------------------------------------------------------------------------------------- -% CONSTRAINT SATISFACTION - BACKTRACKING -%---------------------------------------------------------------------------------------- -\begin{block}{Independent Cascades Model} -\begin{figure} -\centering -\includegraphics[width=0.6\textwidth]{images/icc.png} -\end{figure} - -\vspace{0.5 cm} - -{\bf Description} - -\vspace{0.5 cm} - -\begin{itemize} -\item Three possible states: {\color{blue} susceptible}, {\color{red} infected}, {\color{yellow} inactive } -\item $\mathbb{P}$(infected at t=0)$=p_{\text{init}}$ -\item Infected node $j$ infects its susceptible neighbors $i$ with probability $p_{j,i}$ independently -\end{itemize} - -\vspace{0.5 cm} - -{\bf Sparse Recovery Formulation} - -\vspace{0.5 cm} - -To recover the neighbors of $v_5$,observe which nodes are {\color{red} red} (1), {\color{blue} blue} (0), or {\color{yellow} yellow} (0) at time step $t$: -\begin{align*} -&v_1 \hspace{0.2 cm} v_2 \hspace{0.2 cm} v_3 \hspace{0.2 cm} v_4 \\ -\vspace{1 cm} -M = & \left( \begin{array}{cccc} -1 & 0 & 0 & 0 \\ -0 & 1 & 1 & 0 \\ -\end{array} \right) \begin{array}{l} \hspace{ 1cm} -\text{time step 0} \\ - \hspace{ 1cm} \text{time step 1} \\ - \end{array} -\end{align*} - -and if $M$ caused $v_5$ to be infected at time step $t+1$: - -\begin{align*} -b_5 = & \left( \begin{array}{c} -0 \\ -1 \\ -\end{array} \right) \begin{array}{l} \hspace{ 1cm} -\text{time step 1} \\ - \hspace{ 1cm} \text{time step 2} \\ - \end{array} -\end{align*} - - -Then, - -\begin{equation} -\boxed{e^{M \vec \theta_5} = (1 - \vec b_5) + \epsilon} \nonumber -\end{equation} - -where $(\vec \theta_5)_j := \log ( 1 - p_{j,5}) $ - -\vspace{1 cm} - - -This problem is a {\bf Noisy Sparse Recovery} problem, which has been studied extensively. Here, the vectors $\vec x_i$ are deg(i)-sparse. - - -\end{block} - -%---------------------------------------------------------------------------------------- - - - - - - - - - -%---------------------------------------------------------------------------------------- -% MIP -%---------------------------------------------------------------------------------------- - -% \begin{block}{RIP property} - -% %The Restricted Isometry Property (RIP) characterizes a quasi-orthonormality of the measurement matrix M on sparse vectors. - -% For all k, we define $\delta_k$ as the best possible constant such that for all unit-normed ($l$2) and k-sparse vectors $x$ - -% \begin{equation} -% 1-\delta_k \leq \|Mx\|^2_2 \leq 1 + \delta_k -% \end{equation} - -% In general, the smaller $\delta_k$ is, the better we can recover $k$-sparse vectors $x$! - -% \end{block} - -%---------------------------------------------------------------------------------------- - -\end{column} - -\begin{column}{\sepwid}\end{column} % Empty spacer column - -\begin{column}{\onecolwid} % The first column within column 2 (column 2.1) - - -%---------------------------------------------------------------------------------------- - - -\begin{block}{Algorithms} - -{\bf Voter Model} - -\begin{itemize} -\item Solve for each node i: -\begin{equation} -\min_{\vec x_i} \|\vec x_i\|_1 + \lambda \|M \vec x_i - \vec b_i \|_2 \nonumber -\end{equation} -\end{itemize} - -{\bf Independent Cascade Model} - -\begin{itemize} -\item Solve for each node i: -\begin{equation} -\min_{\vec \theta_i} \|\vec \theta_i\|_1 + \lambda \|e^{M \vec \theta_i} - (1 - \vec b_i) \|_2 \nonumber -\end{equation} -\end{itemize} - -\end{block} - -\begin{block}{Restricted Isometry Property (RIP)} -{\bf Definition} -\begin{itemize} -\item Characterizes a quasi-orthonormality of M on sparse vectors. - -\item The RIP constant $\delta_k$ is the best possible constant such that for all unit-normed ($l$2) and k-sparse vectors $x$: - -\begin{equation} -1-\delta_k \leq \|Mx\|^2_2 \leq 1 + \delta_k \nonumber -\end{equation} - -\item The smaller $\delta_k$ is, the better we can recover $k$-sparse vectors $x$. -\end{itemize} - - - - -\end{block} - -\begin{block}{Theoretical Guarantees} - -With small RIP constants $(\delta \leq 0.25)$ for $M$ and some assumption on the noise $\epsilon$: - -{\bf Theorem \cite{candes}} - -If node $i$ has degree $\Delta$ and $n_{\text{rows}}(M) \geq C_1 \mu \Delta \log n$, then, w.h.p., - -$$\| \hat x - x^* \|_2 \leq C (1 + \log^{3/2}(n))\sqrt{\frac{\Delta \log n}{n_{\text{rows}}(M) }}$$ - - -\end{block} - - - - -%---------------------------------------------------------------------------------------- -% RESULTS -%---------------------------------------------------------------------------------------- - -\begin{block}{RIP Experiments} - -\begin{center} -\begin{table} -\begin{tabular}{c | c | c | c | c } -& $c$ = 100, &$c$ = 1000,& $c$ = 100, &$c$ = 1000,\\ -& $i$ = 0.1& $i$ = 0.1& $i$ = 0.05& $i$ = 0.05\\ - \hline - $\delta_4$ & 0.54 & 0.37 &0.43&0.23 \\ - \end{tabular} - \caption{RIP constant for a small graph. Here, $c$ is the number of cascades and $i$ is $p_{\text{init}}$.} -\end{table} -\end{center} - - -\end{block} - -%---------------------------------------------------------------------------------------- - - -\end{column} % End of the second column - -\begin{column}{\sepwid}\end{column} % Empty spacer column - -\begin{column}{\onecolwid} % The third column - -%---------------------------------------------------------------------------------------- -% IOVERALL COMPARISON -%---------------------------------------------------------------------------------------- - -%\vspace{- 14.2 cm} -%\begin{center} -%{\includegraphics[height=7em]{cmu_logo.png}} % First university/lab logo on the left -%\end{center} - -%\vspace{4 cm} - -\begin{alertblock}{Experimental Results} - - - - -\end{alertblock} - -%---------------------------------------------------------------------------------------- - - -%---------------------------------------------------------------------------------------- -% CONCLUSION -%---------------------------------------------------------------------------------------- - -\begin{block}{Conclusion} - -\begin{center} - - -{\bf Graph reconstruction can naturally be expressed as Sparse Recovery. Understanding properties of $M$, for example RIP, leads to theoretical guarantees on the reconstruction.} - -\end{center} - -\end{block} - -%---------------------------------------------------------------------------------------- -% REFERENCES -%---------------------------------------------------------------------------------------- - -\begin{block}{References} - -\begin{thebibliography}{42} - -\bibitem{candes} -Candès, E., and Plan, Y. -\newblock {\it A Probabilistic and RIPless Theory of Compressed Sensing} -\newblock Information Theory, IEEE Transactions on, 57(11): 7235--7254, -\newblock 2011. -\end{thebibliography} - -\end{block} - -%---------------------------------------------------------------------------------------- - -\end{column} % End of the third column - -\end{columns} % End of all the columns in the poster - -\end{frame} % End of the enclosing frame - - - -\end{document} diff --git a/poster/images/SEASLogo_RGB.png b/poster/images/SEASLogo_RGB.png new file mode 100644 index 0000000..e29fc54 Binary files /dev/null and b/poster/images/SEASLogo_RGB.png differ -- cgit v1.2.3-70-g09d2