---
# System prepended metadata

title: Sanchit's notes about Learning the network from Cascades

---

# Sanchit's notes about Learning the network from Cascades

Meeting on 5/12:

Things to do:
1. Working out the algorithm proposed by Sanchit and figuring out conditions under which the underlying undirected graph can be recovered in polynomial time. 

2. How to find the edge parameters, given the underlying undirected graph? (See the algorithm of Caramanis et al. ). Even for the no-noise case. 

3. Is there some way of finding the underlying undirected graph even in the high degree regime: when the infection rate = $(\max \text{degree}) \times p_{\max}=\omega(\log n)$? Ideas? 
Or do the lower bounds say something here?

4. Varun Gupta paper?


Meeting 6/16

1. Understand Sanghavi & Netrapalli paper, Correlation decay condition, and see if pairwise algo works under correlation decay condition. 

2. Under correlation decay condition, does the greedy algo work (greedily add highest co-occurence).

3. Cascade samples in the stochastic block model.


Meeting 6/24
1. Study the noisy epidemic model with correlation decay? Can we get better guarantees? Can we do anything for arbitrary graphs under this assumption.

Meeting 6/25
1. Meka, Klivans paper for learning graphical models using MWU.

2. Distinguising between $K_4$ and $C_4$ using cascads of length $3$(three nodes)?

3. Can we do better using samples of length $2$ and $3$ v/s using only cascades of length $2$?

Problems:
1. SBM and cascades.

2. Clustering cascades and graph reconstruction

**Meeting on Aug 6th**
   
Sanchit presented the mixture of cascade models by Hoffmann, Caramanis, Goel etc.   

Questions:
1. Is there a tensor method that works?

2. Do you need a separation from all pairs.

3. Is there some natural condition under which I can cluster the cascades?

4. What about k of them?

5. Comparison with Varun's model. 
------------------------------------------

For undirected graphs (full noise setting):

1. Erdos-Renyi graphs, and other average-case distributions?

** Meeting on Aug 27th **

1. Figuring out why the correlation decay condition is needed in Netrapalli-Sanghavi. Can we replace it with a weaker condition?   

2. Can we get better sample complexity/ efficiency in the sparse regime i.e., d=O(1) or O(\log n) ? (even in the full noise/ no-timing-info setting) Does it help if it is a random graph or SBM?

3. Mixtures of Epidemic models. How does it relate to Gupta et al.? Can we use tensor decompositions here? 

4. Can we right down third moment, aggregate into tensor and decompose to find the probabilities?