aboutsummaryrefslogtreecommitdiffstats
path: root/poster/WWW_poster
diff options
context:
space:
mode:
Diffstat (limited to 'poster/WWW_poster')
-rw-r--r--poster/WWW_poster/beamerthemeconfposter.sty184
-rw-r--r--poster/WWW_poster/poster.tex289
2 files changed, 473 insertions, 0 deletions
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}
generated by cgit v1.2.3-70-g09d2 (git 2.52.0) at 2025-12-21 15:45:20 +0000