Article Source

• Title: Graph Streams and Sketches
• Authors: Andrew McGregor

Graph Streams and Sketches

This webpage was set up to accompany a tutorial at ICML 2016.

Tutorial Slides

• Part I: Streaming, Sampling, and Sketching Andrew McGregor
• Part II: Space-Efficient Optimization Sudipto Guha

Other General Resources

• Presentations [Slides], [Video]
• A survey about graph stream algorithms

Bibliography

The following is not an exhaustive list of papers that are relevant to the topic but should include the most relevant and recent papers.

• Vertex and Edge Connectivity and Graph Sparsification
  • Single Pass Spectral Sparsification in Dynamic Streams FOCS 2014 (M. Kapralov, Y. T. Lee, C. Musco, C. Musco, A. Sidford)
  • Vertex and Hyperedge Connectivity in Dynamic Graph Streams PODS 2015 (S. Guha, A. McGregor, D. Tench)
  • Graph Sketches: Sparsfiers, Spanners, and Subgraphs PODS 2012 (K. Ahn, S. Guha, A. McGregor)
  • Analyzing Graph Structure via Linear Measurements SODA 2012 (K. Ahn, S. Guha, A. McGregor)
  • Spectral Sparsification of Dynamic Graph Streams APPROX 2013 (K. Ahn, S. Guha, A. McGregor)
• Matchings and Vertex Cover
  • Kernelization via Sampling with Applications to Dynamic Graph Streams SODA 2016 (R. Chitnis, G. Cormode, H. Esfandiari, M. Hajiaghayi, A. McGregor, M. Monemizadeh, S. Vorotnikova)
  • Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem SODA 2016. S. Assadi, S. Khanna, Y. Li.
• Triangle Counting, Frequent Subgraphs, Clustering Coefficients
  • Better Algorithms for Counting Triangles in Data Streams PODS 2016 (A. McGregor, S. Vorotnikova, H. Vu)
  • Colorful Triangle Counting and a MapReduce Implementation. Rasmus Pagh, Charalampos E. Tsourakakis
• Set Cover
  • Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem FOCS 2016. S. Assadi, S. Khanna, Y. Li.
  • Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover SODA 2016. A. Chakrabarti, A. Wirth.
  • Towards Tight Bounds for the Streaming Set Cover Problem PODS 2016. S. Har-Peled, P. Indyk, S. Mahabadi, A. Vakilian.
• Densest Subgraph
  • Densest Subgraph in Dynamic Graph Streams MFCS 2015 (A. McGregor, D. Tench, S. Vorotnikova, H. Vu)
  • See also: Dense subgraph discovery Tutorial KDD 2015. A. Gionis, C. Tsourakakis,
• Correlation Clustering
  • Correlation Clustering in Data Streams ICML 2015 (K. Ahn, G. Cormode, S. Guha, A. McGregor, A. Wirth)
  • See also: Correlation Clustering: from Theory to Practice KDD 2014. F. Bonchi, D. Garcia-Soriano, E. Liberty
• Bayesian Networks
  • Evaluating Bayesian Networks via Data Streams COCOON 2015. A. McGregor, H. T. Vu.
  • Graphical Model Sketch. B. Kveton, H. Bui, M. Ghavamzadeh, G. Theocharous, S. Muthukrishnan, S. Sun
• Other
  • Dynamic Graphs in the Sliding-Window Model ESA 2013 (M. Crouch, A. McGregor, D. Stubbs)