Research map / Learning theory and algorithms / Sample complexity
Estimating the Number of Induced Subgraphs from Incomplete Data and Neighborhood Queries
Dimitris Fotakis, Thanasis Pittas, Stratis Skoulakis
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase edge-estimator neighborhood queries from 0 to 100 (ablation) | One-sample edge estimator · as-caida20071105 | relative error (%): 2.51 -> 0.53 | Improved |
| Increase edge-estimator neighborhood queries from 0 to 100 (ablation) | One-sample edge estimator · wiki talk ar | relative error (%): 19.9 -> 0.31 | Improved |
| Increase edge-estimator neighborhood queries from 0 to 100 (ablation) | One-sample edge estimator · roadNet-PA | relative error (%): 0.06 -> 0.06 | No clear effect |
| Increase triangle-estimator neighborhood queries from 0 to 200 (ablation) | One-sample triangle estimator · as-caida20071105 | relative error (%): 14.10 -> 0.50 | Improved |
| Increase triangle-estimator neighborhood queries from 0 to 200 (ablation) | One-sample triangle estimator · wiki talk fr | relative error (%): 9.16 -> 1.66 | Improved |
| Increase triangle-estimator neighborhood queries from 0 to 200 (ablation) | One-sample triangle estimator · amazon0302 | relative error (%): 0.36 -> 0.29 | Improved |
| Use a one-sample estimator with filtering rather than the unfiltered one-sample variant (ablation) | Triangle estimation · as-caida20071105 | relative error (%) | Improved |
| Use the two-sample estimator rather than the one-sample estimator (ablation) | Triangle estimation · as-caida20071105 | relative error (%) | Mixed |
| Select high-degree vertices rather than random vertices for neighborhood queries (ablation) | Triangle estimation · as-caida20071105 | relative error (%) | Improved |
| Add neighborhood queries to the edge estimator (ablation) | Edge estimation on irregular networks · synthetic power-law graphs | relative error (%) | Improved |
| Add neighborhood queries to the edge estimator (ablation) | Edge estimation on regular networks · synthetic power-law graphs | relative error (%) | No clear effect |
| Use empirical visibility weights rather than correct weights (ablation) | One-sample triangle estimator · Sample with uniform pv | relative error (%) | No clear effect |
Closest papers by meaning
- On the Propagation of Low-Rate Measurement Error to Subgraph Counts in Large Networks (JMLR 2017 · similarity 0.88)
- Iterative Connecting Probability Estimation for Networks (NeurIPS 2021 · similarity 0.88)
- Query-Limited Community Recovery in Stochastic Block Models (NeurIPS 2026 · similarity 0.86)
- Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point (NeurIPS 2025 · similarity 0.85)
- Optimal community detection in dense bipartite graphs (NeurIPS 2025 · similarity 0.84)
- Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust (NeurIPS 2024 · similarity 0.84)
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.
