Sublinear-time algorithms for counting star subgraphs via edge sampling

DOI10.1007/S00453-017-0287-3zbMATH Open1391.68120arXiv1601.04233OpenAlexW2586277680MaRDI QIDQ1709591FDOQ1709591

Authors: M. Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, Anak Yodpinyanee 

Publication date: 6 April 2018

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We study the problem of estimating the value of sums of the form $$ when one has the ability to sample $x_{i}geq0$ with probability proportional to its magnitude. When $p=2$, this problem is equivalent to estimating the selectivity of a self-join query in database systems when one can sample rows randomly. We also study the special case when $x_i$ is the degree sequence of a graph, which corresponds to counting the number of $p$-stars in a graph when one has the ability to sample edges randomly. Our algorithm for a $(1pmvarepsilon)$-multiplicative approximation of $S_p$ has query and time complexities $O(fracmloglognepsilo{n}^2{S}_p^{1/p})$. Here, $m=sum{x}_i/2$ is the number of edges in the graph, or equivalently, half the number of records in the database table. Similarly, $n$ is the number of vertices in the graph and the number of unique values in the database table. We also provide tight lower bounds (up to polylogarithmic factors) in almost all cases, even when $x_i$ is a degree sequence and one is allowed to use the structure of the graph to try to get a better estimate. We are not aware of any prior lower bounds on the problem of join selectivity estimation. For the graph problem, prior work which assumed the ability to sample only emph{vertices} uniformly gave algorithms with matching lower bounds [Gonen, Ron, and Shavitt. extit{SIAM J. Comput.}, 25 (2011), pp. 1365-1411]. With the ability to sample edges randomly, we show that one can achieve faster algorithms for approximating the number of star subgraphs, bypassing the lower bounds in this prior work. For example, in the regime where $S_{p}leqn$, and $p=2$, our upper bound is $ildeO(n/S_p^{1/2})$, in contrast to their $Omega(n/S_p^{1/3})$ lower bound when no random edge queries are available.

Full work available at URL: https://arxiv.org/abs/1601.04233

Recommendations

• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Counting stars and other small subgraphs in sublinear-time
• Counting stars and other small subgraphs in sublinear time
• Efficient and near-optimal algorithms for sampling connected subgraphs
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
• Faster algorithms for counting subgraphs in sparse graphs
• Faster Subgraph Counting in Sparse Graphs
• On counting and approximation variants of the subgraph connecting problem
• Estimating the number of connected components in a graph via subgraph sampling
• Graph characterization by counting sink star subgraphs

zbMATH Keywords

randomized algorithmsapproximate countingsubgraphssublinear-time algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Enumeration in graph theory (05C30) Database theory (68P15)

Cites Work

• The space complexity of approximating the frequency moments
• Optimal approximations of the frequency moments of data streams
• Finding and counting given length cycles
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Title not available (Why is that?)
• A sublinear-time approximation scheme for bin packing
• Faster algorithms for finding and counting subgraphs
• Title not available (Why is that?)
• Approximate counting of cycles in streams
• Counting arbitrary subgraphs in data streams
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Approximating average parameters of graphs
• The Parameterized Complexity of Counting Problems
• Research in Computational Molecular Biology
• Counting subgraphs via homomorphisms
• Counting stars and other small subgraphs in sublinear-time
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Simpler algorithm for estimating frequency moments of data streams
• An improved data stream algorithm for frequency moments
• Property testing lower bounds via communication complexity
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• Local Graph Partitions for Approximation and Testing
• Improved constant-time approximation algorithms for maximum matchings and other optimization problems
• Tracking join and self-join sizes in limited storage
• Estimating Sum by Weighted Sampling
• Approximately counting triangles in sublinear time
• Finding, minimizing, and counting weighted subgraphs
• Balanced hashing, color coding and approximate counting
• Motifs in evolving cooperative networks look like protein structure networks
• Selectivity and cost estimation for joins based on random sampling
• Discovering and Exploiting Statistical Properties for Query Optimization in Relational Databases: A Survey
• On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
• Testing probability distributions underlying aggregated data
• Approximating the number of network motifs

Cited In (9)

• Title not available (Why is that?)
• Motif estimation via subgraph sampling: the fourth-moment phenomenon
• Counting stars and other small subgraphs in sublinear-time
• Sublinear time estimation of degree distribution moments: the arboricity connection
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Lower bounds for approximating graph parameters via communication complexity
• Estimating the number of connected components in a graph via subgraph sampling
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
• Counting stars and other small subgraphs in sublinear time

Uses Software

• QPath

This page was built for publication: Sublinear-time algorithms for counting star subgraphs via edge sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709591)