Counting Subgraphs in Sublinear Time
summary
Shows concrete sublinear estimators and their costs: sampling √n uniform vertices gives a 2-approx for average degree (Feige), while an orientation by degree estimator yields a 1+ε mean-degree estimate in O(√n) queries. For triangles, an edge-oriented wedge sampler plus repetitions tied to min(deg(u),deg(v)) and the Chiba‑Nishizaki bound (∑_edges min(deg)=O(m3/2)) gives optimal m3/2/t and n/t1/3-style bounds. Also gives a practical simulate-uniform-edge-by-sampling-vertices trick and discusses implementation and modeling caveats.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 1:10Tribute
- 2:37Problem definition
- 6:53Average degree estimation
- 22:36Graph orientations
- 32:45Triangle counting
- 45:28Uniform edge sampling
- 51:10Sublinear algorithms
- 58:02Q&A
related talks
33mLinear and sublinear algorithms for graphlet sampling
01h 06mSampling in Query Evaluation 1
57mQuery Optimization and Evaluation 1: Output Size Bounds and Information Theory
35mDistributed Models for Private Analysis of Graph Data
25mErasure-Resilient Sublinear-Time Graph Algorithms
47mSublinear Time Eigenvalue Approximation via Random Sampling
43mResizable Sketches
26mCounting Subgraphs in Somewhere Dense Graphs