Stop Thinking, Just Do!

Article Source

• Andrew McGregor’s page

Graph Sketching, Streaming, and Sampling

Tutorial Slides (KDD 2018 version)

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

Other General Resources

• A survey about graph stream algorithms.
• Extended Tutorial Slides (3hrs) from Porto Winter School on Network Science 2018.
• Ten lectures on graph streams:
  • Graphs-1: Connectivity, k-connectivity, Spanners, Sparsification
  • Graphs-2: Connectivity via Sketching
  • Graphs-3: Sparsification via Sketching
  • Graphs-4: Insert-Only (Weighted) Matchings
  • Graphs-5: Planar Matchings
  • Graphs-6: Small Matchings
  • Graphs-7: Multiple-Pass Matchings via Multiplicative Weights
  • Graphs-8: Submodular Maximization
  • Graphs-9: Set-Cover and Max Coverage
  • Graphs-10: Correlation Clustering

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.
• Graph Coloring
  • Sublinear Algorithms for (Delta+1) Vertex Coloring ArXiv 2018 (S. Assadi, Y. Chen, S. Khanna)
  • SColoring in Graph Streams ArXiv 2018 (S. K. Bera, P. Ghosh)
• 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)