1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
\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.29\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{Thibaut Horel, 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
\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}
\emph{How to recover an unknown network from the observation of contagion
cascades?}
\vspace{.5cm}
\begin{itemize}
\item {\bf Observe} $X^t_c$ (infections at time $t$ in cascade $c$)
\item {\bf Objective}: find $\{\theta_{ij}\}$ (graph weight matrix)
\end{itemize}
\end{block}
\vspace{1cm}
\begin{block}{\bf Contagion Model~\cite{}}
\begin{itemize}
\item Discrete time
\item Infections drawn indep.~for each node conditioned on previous step
\item Generalized Linear Model parametrization:
\begin{framed}
$$\mathbb{P}(X^{t+1}_j = 1 | X^t) = f(\Theta_j \cdot X^t)$$
\end{framed}
\end{itemize}
\end{block}
\begin{block}{MLE}
\begin{itemize}
\item Log-likelihood is concave for common contagion models (IC model): SGD
on $\{\theta_{ij}\}$
\end{itemize}
\vspace{1cm}
\begin{equation*}
\begin{split}
\hat{\theta}\in \arg\max_\theta \sum_{t}~& y^t\log f(\theta\cdot x^t)
\\ & + (1-y^t) \log \big(1 - f(\theta\cdot x^t)\big)
\end{split}
\end{equation*}
\end{block}
\begin{block}{Bayesian Framework}
\begin{figure}
\centering
\includegraphics[scale=3]{graphical.pdf}
\end{figure}
\begin{itemize}
\item $\phi$: fixed source distribution
\item capture uncertainty on each edge
\item encode expressive graph priors (tied parameters)
\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}{Active Learning}
\emph{Can we gain by choosing the source node? If so, how to best choose the
source node?}
\end{block}
\begin{block}{Heuristic 1 (Baseline)}
\end{block}
\begin{block}{Heuristic 2}
\begin{itemize}
\item Choose source to maximize mutual information
\begin{equation*}
\begin{split}
I(\bx ,\Theta | x^0 = i) = &
E_{\substack{\Theta \sim D_t \\ x |
\Theta, i \sim D'}}\log p(x|\Theta) \\ - & E_{\substack{\Theta
\sim D_t \\ x' | \Theta, i \sim D'}} \log p(x')
\end{split}
\end{equation*}
\end{itemize}
\end{block}
\end{column}
%-----------------------------------------------------------------------------
\begin{column}{\sepwid}\end{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}
|
