**Reading group on graphs**

This reading group happens on Thursdays (usually at 2pm, but check the times) in room 101 of the INRIA building. If you know of some papers on graphs that you would like to add and present send me an email (gemma dot garriga at inria dot fr).

**Next meetings**

24/05/2012, 2pm: |
We will discuss the paper Revisiting k-means: New Algorithms via Bayesian Nonparametrics by Brian Kulis and Michael Jordan. Presented by David Chatel. |

16/05/2012, 2pm: |
We will discuss the paper Latent spaces approaches to social networks by Hoff, P.D., Raftery, A.E., and Handcock, M.S. Presented by Antonino Freno. |

26/04/2012, 2pm: |
We will discuss the paper A unified view of Kernel k-means, Spectral clustering and graph cuts by I.Dhillon, Y.Guan and B.Kulis. Presented by David Chatel. |

12/01/2012, 11am: |
Complex output learning with kernels: from functional to structured data by Hachem Kadri. Room W11. |

08/12/2011, 2pm: |
Tutorial on Hadoop by Teresa Klatzer. |

01/12/2011, 2pm: |
We will discuss the paper Maximizing the spread of influence through a social network by D.Kempe, J.Kleinberg and E.Tardos. Presented by Gemma Garriga. |

10/11/2011, 2pm: |
We will continue the discussion of the previous week on graph-based semi-supervised learning for structured tagging models, by Marc Tommasi and Pascal Denis. |

04/11/2011, 11am: |
We will discuss the papers: Benefits of bias: towards better characterization of network sampling by Maiya and Berger-Wolf; presented by Remi Gilleron. Efficient graph-based semi-supervised learning of structured tagging models by Subramanya, Petrov and Pereira; presented by Marc Tommasi and Pascal Denis. |

20/10/2011, 2pm: |
Michal Valko will present results from his Thesis Adaptive graph-based algorithms for conditional anomaly detection and semi-supervised learning. Room W11. |

29/09/2011, 2pm: |
We will discuss the following papers: Predicting Thread Discourse Structure over Technical Web Forums, by L.Wang et al, at 2011 Conference on Empirical Methods in Natural Language Processing. Presented by Pascal Denis. |

15/09/2011, 9am: |
We will discuss the following papers: Pseudolikelihood Estimation for Social Networks, by D. Strauss, M.Ikeda, at Journal of the American Statistical Association, 1990; and Recent developments in exponential random graph (p*) models for social networks by Garry Robins and Tom Snijders and Peng Wang and Mark Handcock, at Social Networks, 2006. Presented by Antonino Freno. |

08/09/2011, 2pm: |
We will discuss the paper On node classification in dynamic content-based networks, by C. Aggarwal and N. Li. Presented by Remi Gilleron. |

14/04/2011, 2pm: |
We will discuss the paper Learning with Hypergraphs: Clustering, Classification and Embedding by Zhou et al. Presented by Thomas Ricatte. |

07/04/2011, 2pm: |
We will discuss results and tutorial on graph spectral clustering and spectra of graph, basic material from A tutorial on spectral clustering. Presented by Gemma Garriga. |

10/03/2011, 2pm |
We will continue the discussion of the paper from last week. Presented by Mikaela Keller. |

3/03/2011, 2pm: |
We will discuss the paper Link propagation: a fast semi-supervised learning algorithm for link prediction. Presented by Mikaela Keller. |

17/02/2011, 2pm: |
We will discuss the paper on Factorizing Personalized Markov Chains for Next-Basket recommendations by Rendle, Freudenthaler and Schmidt-Thieme, WWW 2010. Presented by Jeremie Mary. |

10/02/2011, 2pm: |
We will discuss graph construction methods for semi-supervised learning algorithms from the papers Large graph construction for scalable semi-supervised learning ICML 2010, and Graph construction and b-matching for semi-supervised learning ICML 2009. Presented by Gemma Garriga. |

27/01/2011, 2pm: |
We will discuss current open problems of machine learning on graphs and the current collaborations with industry in the subject of machine learning. |

20/01/2011, 2pm: |
We will discuss the ICML tutorial on Modeling Social and Information Networks: Opportunities for Machine Learning, by Jure Leskovec. It is necessary to have seen the tutorial at videolectures before. Presented by Marc Tommasi. |

09/12/2010, 2pm: |
We will discuss the paper Kronecker graphs: an approach to modeling networks by Leskovec, Chakrabarti, Kleinberg, Faloutsos and Ghahramani. Presented by Marc Tommasi. |

02/122010, 2pm: |
We will discuss the papers Sampling from large graphs and Sampling and estimation of network graphs. Presented by Gemma Garriga. |

25/10/2010, 2pm |
We will discuss the second part of the paper from the previous week. Presented by Antoine Ndione. |

18/10/2010, 2pm |
We will discuss the paper Property testing and its connection to learning and approximation. Presented by Antoine Ndione |

04/10/2010, 2pm |
Kick-off meeting |

**Reading list**

** Network models and statistics**

- Modeling social networks from sampled data. M.S.Handcock and K.Gile. The Annals of Applied Statistics, 2010.
- Statistical analysis of network data: methods and models. Eric D. Kolaczyk. Springer series in Statistics.

Note: Gemma has this book. - Part IV (web), V and VI (dynamics) of the book Networks, crowds and markets. D.Easley and J.Kleinberg.
- A survey of statistical network models. A.Goldenberg et al. Foundations and trends in Machine learning. 2009.
- Models and Methods in Social Network Analysis. Carrington, Scott and Wasserman (eds).

Note: Gemma has the book. - Maximum likelihood: extracting unbiased information from complex networks. D. Garlaschelli, M. I. Loffredo. Phys. Rev. E. 1998.
- Probability on trees and networks. R.Lyons and Y.Peres.

**Sampling**

- Sampling from large graphs. J.Leskovec and C.Faloutsos. KDD 2006.
- Sampling and estimation of network graphs. E.Kolaczyk. Statistical analysis of network data. Springer.
- Efficient and exact sampling of simple graphs with given arbitrary degree sequence. C. Del Genio et al. Plos ONE 2010.
- Commentary: Sampling in social networks. R. Rothenberg. 1995.
- Sampling techniques for large dynamic graphs. D.Stutzbach et al. IEEE Infocom 2006.
- Accuracy and Scaling Phenomena in Internet Mapping. Clauset and Moore. Phys. Rev. Lett. 1994

**Testing properties on graphs**

- Property testing and its connection to learning and approximation. O.Goldreich, S.Goldwasser and D.Ron. JACM 1998.
- Testing the diameter of graphs. M.Parnas and D.Ron. RANDOM 1999.
- A combinatorial characterization of the testable graph properties: it's all about regularity. N.Alon et al. STOC 2006.
- Efficient testing on large graphs. N.Alon et al. FOCS 1999.

**Streaming on graphs**

- Muthukrishnan: Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science, 1(2), 2005.
- On graph problems in a semi-streaming model. Theor. Comp. Sci. 2005.
- Graph distances in the streaming model: the value of space. ACM_SIAM Symp. on Discrete Algorithms, 2005.
- M. Zelke: Optimal per edge processing times in the semi-streaming model, Inf. Process. Lett., vol. 104, no. 3, pp. 106-112, 2007.
- Baswana, Surender: Streaming algorithm for graph spanners - single pass and constant processing time per edge. In: Inf. Process. Lett., volume 106(3):pp. 110-114, 2008.
- Thesis of M. Zelke. Algorithms for streaming graphs
- Yao, Mimno and McCallum. Efficient methods for topic model inference on streaming document collections. KDD 2009.

**Machine learning and applications on graphs**

- More efficient classification of web content using graph sampling. C. Bennett. IEEE CIDM 2007.
- Representative subgraph sampling using Markov Chain Monte Carlo methods. C. Hubler et al. Intl Workshop on MLG 2008.
- Output space sampling for graph patterns. M.Al Hasan and M. Zaki. VLDB 2009.
- Part V (Network dynamics) Networks, crowds and markets. D.Easley and J.Kleinberg.
- Temporal Link Prediction using Matrix and Tensor Factorizations. Daniel M. Dunlavy, Tamara G. Kolda, Evrim Acar.
- Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. Kleinberg, Tardos. FOCS 1999.
- A brief survey of machine learning methods for classification in networked data and an application to suspicion scoring. S.Macskassy and F.Provost. ICML 2006.
- Tutorial Modeling Social and Information Networks: Opportunities for Machine Learning. J.Leskovec. ICML 2009.
- Fast an optimal prediction on a labeled tree. N.Cesa-Bianchi, C.Gentile and F.Vitale. COLT 2009.
- Strategies for online inference of model-based clustering in large growing networks. H.Zanghi et al. 2010.
- Fast prediction on a tree. M.Herbster, M.Pontil and S.Rojas-Galeano. NIPS 2008.
- Exploiting cluster-structure to predict the labeling of a graph. M.Herbster. ALT 2008.
- Large graph construction for scalable semi-supervised learning. Liu, He and Chang. ICML 2010.
- Active learning for networked data. Bilgic, Mihalkova and Getoor. ICML 2010.
- Random spanning trees and the prediction of weighted graphs. Cesa-Bianchi, Gentile, Vitalle and Zapella. ICML 2010.
- Learning unknown graphs. Cesa-Bianchi, Gentile and Vitale. ALT 2009.
- Gossiping personalized queries. Bai et al. EDBT 2010.
- Factorizing personalized Markov chains for next-basket recommendation Rendle et al. WWW 2010.
- Algorithms and applications for approximate nonnegative matrix factorization Berry et al. Computational Statistics and Data Analysis 2007.

**Link prediction**

- New perspectives and methods in link prediction. KDD 2010.
- Human mobility, social ties and link prediction. KDD 2011.
- Link prediction based on local random walks. Weiping Liu, Linyuan Lu. Europhysics Letters. 2010.
- Transfer learning for collective link prediction in multiple heterogeneous domains B.Cao, N.Nan Liu and Q.Yang. ICML 2010.

** Other interesting links**

- Information Network Academic Research Center. Check the publications in the publication tab.
- Mining and Learning with Graphs Workshop 2011 at KDD 2011. Many interesting papers and invited talks in this graph mining workshop.