Linear and sublinear algorithms for graphlet sampling

on YouTube ↗33m

" summary

Gives two concrete algorithms: one with linear-time preprocessing (compute a total order by repeatedly removing a max-degree vertex) that produces exactly uniform connected k-vertex induced subgraphs with expected O(log n) time per sample using rejection sampling and binary-searches in sorted adjacency lists; and one with sublinear preprocessing n log n that yields ε-uniform samples in constant time per sample (independent of n) at the cost of bad dependence on k. Implements cut-estimation, sampling-from-buckets, and works in semi-streaming and MPC with similar guarantees.

AI-written summary · about

" chapters (13)

1. 0:00Graphlet sampling intro
2. 1:12Problem and applications
3. 3:22Prior limitations
4. 5:32New algorithms overview
5. 7:01Rejection sampling
6. 11:02Linear preprocessing
7. 16:52Linear algorithm summary
8. 17:12Sublinear motivation
9. 23:22Sublinear challenges
10. 28:43Sublinear algorithm details
11. 30:33Streaming and MPC extensions
12. 31:18Open problems
13. 32:40Q&A

" related talks

• 01h 02mCounting Subgraphs in Sublinear TimeC. Seshadhri · Sublinear Algorithms Boot Camp 2024
• 25mErasure-Resilient Sublinear-Time Graph AlgorithmsSofya Raskhodnikova, Nithin Varma, Amit Levi, Ramesh Krishnan S. Pallavoor · ITCS 2021
• 01h 06mSampling in Query Evaluation 1Marcelo Arenas · Logic and Algorithms in Database Theory and AI Boot Camp
• 43mResizable SketchesRasmus Pagh · Sketching and Algorithm Design 2023
• 35mDistributed Models for Private Analysis of Graph DataAdam M. Smith · Trust in Decentralized Systems 2026
• 47mSublinear Time Eigenvalue Approximation via Random SamplingCameron Musco · Sketching and Algorithm Design 2023
• 32mAny-k: Ranked enumeration for Dynamic ProgrammingNikos Tziavelis · Logic and Algebra for Query Evaluation 2023
• 16mControlling Memory Footprint of Stateful Streaming Graph ProcessingKeval Vora, Pourya Vaziri · USENIX ATC '21