AI Paper Atlas

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

AAAI 2021 · Learning theory and algorithms › Sample complexity · approach: Distributed estimation under communication limits · 0 citations (OpenAlex)

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 changedWhereMeasuredEffect
Increase edge-estimator neighborhood queries from 0 to 100 (ablation)One-sample edge estimator · as-caida20071105relative error (%): 2.51 -> 0.53Improved
Increase edge-estimator neighborhood queries from 0 to 100 (ablation)One-sample edge estimator · wiki talk arrelative error (%): 19.9 -> 0.31Improved
Increase edge-estimator neighborhood queries from 0 to 100 (ablation)One-sample edge estimator · roadNet-PArelative error (%): 0.06 -> 0.06No clear effect
Increase triangle-estimator neighborhood queries from 0 to 200 (ablation)One-sample triangle estimator · as-caida20071105relative error (%): 14.10 -> 0.50Improved
Increase triangle-estimator neighborhood queries from 0 to 200 (ablation)One-sample triangle estimator · wiki talk frrelative error (%): 9.16 -> 1.66Improved
Increase triangle-estimator neighborhood queries from 0 to 200 (ablation)One-sample triangle estimator · amazon0302relative error (%): 0.36 -> 0.29Improved
Use a one-sample estimator with filtering rather than the unfiltered one-sample variant (ablation)Triangle estimation · as-caida20071105relative error (%)Improved
Use the two-sample estimator rather than the one-sample estimator (ablation)Triangle estimation · as-caida20071105relative error (%)Mixed
Select high-degree vertices rather than random vertices for neighborhood queries (ablation)Triangle estimation · as-caida20071105relative error (%)Improved
Add neighborhood queries to the edge estimator (ablation)Edge estimation on irregular networks · synthetic power-law graphsrelative error (%)Improved
Add neighborhood queries to the edge estimator (ablation)Edge estimation on regular networks · synthetic power-law graphsrelative error (%)No clear effect
Use empirical visibility weights rather than correct weights (ablation)One-sample triangle estimator · Sample with uniform pvrelative error (%)No clear effect

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy