TCS+ Talk

Abstract:  In the subgraph counting problem, we are given a (large) graph G(V, E) and a (small) graph H (e.g., a triangle), and the goal is to estimate the number of occurrences of H in G. Our focus in this talk is on designing sublinear-time algorithms for approximately computing number of occurrences of H in G in the setting where the algorithm is given query access to G. This problem has been studied in several recent work which primarily focused on specific families of graphs H such as triangles, cliques, and stars. However, not much is known about approximate counting of arbitrary graphs H in the literature. This is in sharp contrast to the closely related subgraph enumeration problem in which the goal is to list all copies of the subgraph H in G. The AGM bound shows that the maximum number of occurrences of any arbitrary subgraph H in a graph G with m edges is O(m^{p(H)}), where p(H) is the fractional edge cover number of H, and enumeration algorithms with matching runtime are known for every H.

In this talk, we bridge this gap between the subgraph counting and subgraph enumeration problems and present a simple sublinear-time algorithm that estimates the number of occurrences of any arbitrary graph H in G, denoted by #H, to within a (1 ± ε)-approximation factor with high probability in O(m^{p(H)} /#H)·poly(log n,1/ε) time. Our algorithm is allowed the standard set of queries for general graphs, namely degree queries, pair queries and neighbor queries, plus an additional edge-sample query that returns an edge chosen uniformly at random. The performance of our algorithm matches those of Eden et al. [FOCS 2015, STOC 2018] for counting triangles and cliques and extend them to all choices of subgraph H under the additional assumption of edge-sample queries. Our results are also applicable to the more general problem of database join size estimation problem and for this slightly more general problem achieve optimal bounds for every choice of H.

Joint work with Michael Kapralov and Sanjeev Khanna.