Research map / Graph learning / Graph algorithms and clustering
Efficient Streaming Algorithms for Graphlet Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives semi-streaming algorithms (STREAM-UGS) for uniform k-graphlet sampling that preprocess a graph in O(log n) passes and draw Θ(M/k^O(k)) uniform graphlets in O(k) passes, plus near-optimal space lower bounds.
Problem
Uniformly sampling connected induced k-vertex subgraphs (k-graphlets) from a large graph when the graph cannot fit in memory and can only be read via sequential edge-list passes.
Approach
Adapts the UGS two-phase sampler to the semi-streaming model by computing an approximate degree-dominating (ϑ-DD) topological order via randomized peeling/shaving in O(log n) passes, a single-pass truncated-BFS test for non-empty buckets, and sharing stream passes across many parallel sampling instances.
Key results
- On Twitter (WWW) with k=4 and ε=1, the actual success probability is 100/31230 ≈ 0.0032, far above the worst-case bound 9.65e-5.
- Experiments on graphs up to 1.8 billion edges need around 30 passes to complete sampling tasks, with memory below the total edge-list size.
- Space lower bound: any p-pass streaming algorithm for Graphlet Sampling requires Ω(n/p) bits, showing near-optimal memory-pass tradeoff.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use APPROX-DD-HEURISTIC instead of APPROX-DD | STREAM-UGS preprocessing · NY Times | number of passes and memory usage | Helped |
| Use APPROX-DD-HEURISTIC instead of APPROX-DD | STREAM-UGS preprocessing · Dense | number of passes and memory usage | No clear effect |
| Increase ϵ | APPROX-DD preprocessing and STREAM-UGS sampling · NY Times and Dense | number of passes | Mixed |
| Vary ϵ | APPROX-DD-HEURISTIC · NY Times and Dense | number of passes and memory usage | No clear effect |
| Use STREAM-UGS sampling on Twitter (WWW) with ϵ = 1 and k = 4 | STREAM-UGS · Twitter (WWW) | sampling success probability versus the Lemma C.1 lower bound: 100/31230 ≈ 0.0032; 9.65 × 10−5 | Helped |
Surprising findings
- The heuristic variant APPROX-DD-HEURISTIC helps substantially on sparse graphs but gives no significant advantage on dense graphs.
Limitations
- Guarantees are vacuous unless k = o(log n) and all known methods pay a k^O(k) factor.
- Experiments are a Python implementation on a single 28GB-RAM server, with sampling success probability far better than worst-case bound.
- Approximate DD order (ϑ=1/(1+ϵ)) reduces acceptance probability by a factor ϑ^(k-1).
Experimental setup
Datasets: NY Times (KONECT) Twitter (WWW) (KONECT) Twitter (MPI) (KONECT) Friendster (KONECT) Dense (synthetic)
Benchmarks: NY Times Dense Twitter (WWW) Twitter (MPI) Friendster
Metrics: number of passes memory usage number of sampling trials to obtain 100 graphlets
Baselines: UGS MOTIVO APPROX-DD (non-heuristic)
Builds on: UGS MOTIVO color-coding
Closest papers by meaning
- New Parallel and Streaming Algorithms for Directed Densest Subgraph (NeurIPS 2025 · similarity 0.88)
- Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs (ICML 2024 · similarity 0.88)
- A Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs (ICLR 2024 · similarity 0.86)
- Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025 · similarity 0.85)
- Distribution Learning Meets Graph Structure Sampling (NeurIPS 2025 · similarity 0.85)
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.