small changes

5 files changed, 57 insertions, 12 deletions

diff --git a/paper/sections/experiments.tex b/paper/sections/experiments.tex
index 4876927..ceb2159 100644
--- a/paper/sections/experiments.tex
+++ b/paper/sections/experiments.tex
@@ -8,15 +8,30 @@
 \caption{Watts-Strogatz Model. 200 nodes, 20000 edges.}
 \end{figure}
 
-In this section, we validate empirically the results and assumptions of Section~\ref{sec:results} for different initializations of parameters ($n$, $m$, $\lambda$) and for varying levels of sparsity. We compare our algorithm to two different state-of-the-art algorithms: \textsc{Greedy} and \textsc{MLE} from \cite{Netrapalli:2012}. We introduce an approximate \textsc{Lasso} algorithm and validate its effectiveness empirically.
+\begin{figure}
+\includegraphics[scale=.4]{figures/barabasi_albert.pdf}
+\caption{Barabasi Model.}
+\end{figure}
+
+In this section, we validate empirically the results and assumptions of Section~\ref{sec:results} for different initializations of parameters ($n$, $m$, $\lambda$) and for varying levels of sparsity. We compare our algorithm to two different state-of-the-art algorithms: \textsc{greedy} and \textsc{mle} from \cite{Netrapalli:2012}. As an extra benchmark, we also introduce a new algorithm \textsc{lasso}, which approximates our \textsc{sparse mle} algorithm. We find empirically that \textsc{lasso} is highly robust, and can be computed more efficiently than both \textsc{mle} and \textsc{sparse mle} without sacrificing for performance.
 
 \paragraph{Experimental setup}
 
-We focus our analysis to synthetic graphs, which are known to exhibit the properties of real social networks. We therefore consider a Watts-Strogatz graph ($300$ nodes, $4500$ edges), a Barabasi-Albert graph ($300$ nodes, $16200$ edges), the Holme-Kim power law graph ($200$ nodes, $9772$ edges) \cite{Holme:2002}, and the recently introduced Kronecker graph ($256$ nodes, $10000$ edges) \cite{Leskovec:2010}. For every reported data point, we generate $n$ cascades from the Independent Cascade model for $n \in \{100, 500, 1000, 2000, 5000\}$, and compute the estimated graph $\hat {\cal G}$ for each algorithm. 
+We evaluate the performance of the algorithms on synthetic graphs, chosen for their similarity to real social networks. We therefore consider a Watts-Strogatz graph ($300$ nodes, $4500$ edges), a Barabasi-Albert graph ($300$ nodes, $16200$ edges), the Holme-Kim power law graph ($200$ nodes, $9772$ edges) \cite{Holme:2002}, and the recently introduced Kronecker graph ($256$ nodes, $10000$ edges) \cite{Leskovec:2010}. Undirected graphs are converted to directed graphs by doubling the edges.
 
-In the case of the \textsc{Lasso}, \textsc{MLE} and \textsc{Sparse MLE} algorithms, we construct the edges of $\hat {\cal G} : \cup_{j \in V} \{i : \Theta_{ij} > 0.1\}$. We report the F1-score$=2\frac{\text{precision}\cdot\text{recall}}{\text{precision}+\text{recall}}$. For each graph, the initial probability of a node being a source is fixed to $0.05$, i.e. an average of $15$ nodes source nodes per cascades.  Except when testing for approximately sparse graphs, all edge weights are chosen uniformly in the interval $[0.2, 0.7]$.
+For every reported data point, we generate $n$ cascades from the Independent Cascade model for $n \in \{100, 500, 1000, 2000, 5000\}$, and compute the estimated graph $\hat {\cal G}$ for each algorithm. The initial probability of a node being a source is fixed to $0.05$, i.e. an average of $15$ nodes source nodes per cascades for all experiments. All edge weights are chosen uniformly in the interval $[0.2, 0.7]$, except when testing for approximately sparse graphs (see paragraph on robustness).
+
+From the set of nodes that are infected at each time step over the $n$ cascades, we attempt to recover the graph ${\cal G}$. In the case of the \textsc{lasso}, \textsc{mle} and \textsc{sparse mle} algorithms, we construct the edges of $\hat {\cal G} : \cup_{j \in V} \{i : \Theta_{ij} > 0.1\}$, \emph{i.e} by thresholding. The parameter $\lambda$ is chosen to be of the order ${\cal O}(\sqrt{\log m / (\alpha n)})$. The true positives are the edges which appear both in ${\cal G}$ and $\hat {\cal G}$ and the true negatives are the edges which appear in neither. Finally, we report the F1-score$=2 \text{precision}\cdot\text{recall}/(\text{precision}+\text{recall})$, which considers the number of true edges recovered by the algorithm over the total number of edges returned by the algorithm (\emph{precision}) with the number of true edges recovered by the algorithm over the total number of edges it should have recovered (\emph{recall}).
 
 \paragraph{Comparison with other algorithms}
+
+Over all experiments, \textsc{sparse mle} achieves higher rates of precision, recall, and f1-score. \textsc{sparse mle} is also robust to approximate sparsity, and displays a faster convergence of the $\ell2$-norm than any other benchmark. Interestingly, both \textsc{mle} and \textsc{sparse mle} perform exceptionally well on the Watts-Strogatz graph. The recovery rate converges at around $5000$ cascades, which is more than $15$ times the number of nodes. By contrast, \textsc{sparse mle} achieves a reasonable $f1$-score of $.75$ for roughly $500$ observed cascades. We did not benchmark against other known algorithms (\textsc{netrate} and \textsc{first edge}) due to the discrete time assumption. These algorithms also suppose a single-source model, whereas \textsc{sparse mle}, \textsc{mle}, and \textsc{greedy} do not. Learning the graph in the case of a multi-source cascade model is intuitively harder but more realistic, since we rarely have access to ``patient 0'' in practice.
+
+\paragraph{The \textsc{lasso} algorithm}
+
+To achieve faster computation time, we can consider the following program:
+$\hat \theta \in \arg \min \|\|_2$. This algorithm has the merit of being easier and faster to optimize numerically than the other algorithms.
+
 \begin{itemize}
 \item Continuous time + single source -> no comparison with NETRATE...
 \item This is a modeling decision: in practice, we do not have access to the cascade's ``patient 0'', which makes learning the graph harder.
@@ -27,7 +42,6 @@ In the case of the \textsc{Lasso}, \textsc{MLE} and \textsc{Sparse MLE} algorith
 \paragraph{Quantifying robustness}
 
 
-
 \begin{itemize}
 \item Compare edge recovery to First Edge and Greedy as number of cascades grows on different types of graphs...
 \item Plot upper-bound of parameters in graph as number of cascades grows
diff --git a/paper/sections/results.tex b/paper/sections/results.tex
index 6fba6b2..cd0a5f8 100644
--- a/paper/sections/results.tex
+++ b/paper/sections/results.tex
@@ -20,8 +20,7 @@ a set $\mathcal{T}$ of observations. We will write $n\defeq |\mathcal{T}|$.
 \label{sec:main_theorem}
 
 In this section, we analyze the case where $\theta^*$ is exactly sparse. We
-write $S\defeq\text{supp}(\theta^*)$ and $s=|S|$. Our main theorem will rely
-on the now standard \emph{restricted eigenvalue condition}.
+write $S\defeq\text{supp}(\theta^*)$ and $s=|S|$. In our context, $S$ is the set of all nodes susceptible to influence our node $i$. In other words, if $\theta^*$ is exactly $s$-sparse, then node $i$ has at most $s$ parents. Our main theorem will rely on the now standard \emph{restricted eigenvalue condition}.
 
 \begin{definition}
     Let $\Sigma\in\mathcal{S}_m(\reals)$ be a real symmetric matrix and $S$ be
@@ -55,7 +54,7 @@ In the voter model, $\frac{f'}{f}(z) = \frac{1}{z}$ and $\frac{f'}{f}(1-z)
 1-\alpha$ for all $(i,j)\in E$. Similarly, in the Independent Cascade Model,
 $\frac{f'}{f}(z) = \frac{1}{1-e^z}$ and $\frac{f'}{1-f}(z) = -1$ and (LF) holds
 if $p_{i, j}\leq 1-\alpha$ for all $(i, j)\in E$. Remember that in this case we
-have $\Theta_{i,j} = \log(1-p_{i,j})$.
+have $\Theta_{i,j} = \log(1-p_{i,j})$. These assumptions are reasonable: if an edge has a weight very close to 0, then the ``infection'' will never happen along that edge for our set of observations and we can never hope to recover it.
 
 \begin{theorem}
 \label{thm:main}
diff --git a/src/cascade_creation.py b/src/cascade_creation.py
index a71fce7..cdf7484 100644
--- a/src/cascade_creation.py
+++ b/src/cascade_creation.py
@@ -70,6 +70,7 @@ class InfluenceGraph(nx.DiGraph):
                 self._mat = self.max_proba * np.random.rand(len(self), len(self)
                         ) * np.asarray(nx.adjacency_matrix(self).todense().T)
         if self.sparse_edges:
+            print("adding sparse edges to the graph")
             #Adding sparse non-edges to the graph!
             self._mat += .1 * np.random.rand(len(self), len(self)
                             ) * np.random.binomial(1, p=.33, size=(len(self), len(self)))
diff --git a/src/convex_optimization.py b/src/convex_optimization.py
index fce89b8..81bee2b 100644
--- a/src/convex_optimization.py
+++ b/src/convex_optimization.py
@@ -90,7 +90,7 @@ def diff_and_opt(M_val, w_val, f_x, f_xz):
 
     def F(x=None, z=None):
         if x is None:
-            return 0, cvxopt.matrix(-.7, (n,1))
+            return 0, cvxopt.matrix(-.01, (n,1))
         elif z is None:
             y, y_diff = f_x(x, M_val, w_val)
             return cvxopt.matrix(float(y), (1, 1)),\
diff --git a/src/make_plots.py b/src/make_plots.py
index 10fd657..d719337 100644
--- a/src/make_plots.py
+++ b/src/make_plots.py
@@ -34,7 +34,7 @@ def compute_graph(graph_name, n_cascades, lbda, passed_function, min_proba,
     """
     G = cascade_creation.InfluenceGraph(max_proba=max_proba,
                                         min_proba=min_proba,
-                                        sparse_edges=True)
+                                        sparse_edges=sparse_edges)
     G.import_from_file(graph_name)
     A = cascade_creation.generate_cascades(G, p_init=.05, n_cascades=n_cascades)
 
@@ -77,6 +77,37 @@ def plot_watts_strogatz_graph():
     plt.savefig("../paper/figures/"+"watts_strogatz.pdf")
 
 
+def plot_barabasi_albert_graph():
+    """
+    plot information in a pretty way
+    """
+    plt.clf()
+    fig = plt.figure(1)
+    labels = [50, 100, 500, 1000, 2000, 5000]
+    x = [np.log(50), np.log(100), np.log(500), 
+            np.log(1000), np.log(2000), np.log(5000)]
+    sparse_recov = [.35, .38, .58, .69, .79, .86]
+    max_likel = [.35, .38, .56, .68, .78, .85]
+    lasso = [.25, .3, .55, .67, .76, .83]
+    greedy = [.1, .13, .33, .47, .6, .75]
+
+    fig, ax = plt.subplots()
+
+    plt.axis((np.log(45), np.log(5500), 0, 1))
+    plt.xlabel("Number of Cascades")
+    plt.ylabel("F1 score")
+    plt.grid(color="lightgrey")
+    ax.plot(x, greedy, 'ko-', color="lightseagreen", label='Greedy')
+    ax.plot(x, lasso, 'ko-', color="orange", label="Lasso")
+    ax.plot(x, max_likel, 'ko-', color="cornflowerblue", label="MLE")
+    ax.plot(x, sparse_recov, 'ko-', color="k", label="Our Method")
+    plt.legend(loc="lower right")
+    ax.set_xticks(x)
+    ax.set_xticklabels(tuple(labels))
+    plt.savefig("../paper/figures/"+"barabasi_albert.pdf")
+
+
+
 def plot_ROC_curve(figure_name):
     """
     plot information in a pretty way
@@ -137,8 +168,8 @@ if __name__=="__main__":
             #convex_optimization.type_lasso)
     if 1:
         compute_graph("../datasets/kronecker_graph_256_cross.txt", 
-            n_cascades=1000, lbda=.001, min_proba=.2, max_proba=.7,
+            n_cascades=100, lbda=.01, min_proba=.2, max_proba=.7,
             passed_function=
-            convex_optimization.sparse_recovery, 
-            #convex_optimization.type_lasso,
+            #convex_optimization.sparse_recovery, 
+            convex_optimization.type_lasso,
             sparse_edges=False)
\ No newline at end of file